Abstract

We study a number of open issues in spectral clustering: (i) Selecting the appropriate scale of analysis, (ii) Handling multi-scale data, (iii) Clustering with irregular background clutter, and,(iv) Finding automatically the number of groups. We first propose that a ‘local’ scale should be used to compute the affinity between each pair of points. This local scaling leads to better clustering especially when the data includes multiple scales and when the clusters are placed within a cluttered background. We further suggest exploiting the structure of the eigenvectors to infer automatically the number of groups. This leads to a new algorithm in which the final randomly initialized k-means stage is eliminated

چکیده

ما تعدادی مساله در خوشه بندی طیفی را مطالعه می کنیم: (i) انتخاب مقیاس مناسب تحلیل، (ii) مدیریت داده های چندمقیاسه، (iii) خوشه بندی با پارازیت زمینه ی نامنظم، و (iv) پیدا کردن اتوماتیک تعداد گروه ها. ابتدا پیشنهاد می دهیم که یک مقیاس محلی برای محاسبه ی وابستگی بین هر جفت از نقطه ها مورد استفاده قرار گیرد.

این مقیاس بندی محلی منجر به خوشه بندی بهتر می شود مخصوصا زمانیکه داده ها مقیاس های مختلفی دارند و گروه ها در یک پیش زمینه ی پارازیت دار قرار دارند. سپس استفاده از ساختار بردارهای ویژه برای استنتاج اتوماتیک تعداد خوشه ها را پیشنهاد می دهیم. با این کار یک الگوریتم جدید حاصل می شود که در آن مرحله ی نهایی که در آن k-means  ها بطور تصادفی مقداردهی اولیه می شود حذف می شود.

-1مقدمه

خوشه بندی یکی از بلوک های سازنده ی روش های مدرن تحلیل داده است. دو روش رایج برای این کار k-means و یادگیری یک مدل مخلوط با استفاده از EM می باشد. این روش ها، بر اساس تحمین مدل های صریح داده ها هستند و وقتی داده ها طبق مدل های مفروض سازماندهی شوند، نتایجی با کیفیت بالا ارائه می دهند. ولی وقتی به شکل های پیچیده تر و ناشناخته تر سازماندهی می شوند، این روش ها خوب عمل نمی کنند. یک روش گروه بندی جایگزین برای چنین داده هایی روش خوشه بندی طیفی است. این روش به تخمین مدل صریحی از توزیع داده ها نیاز ندارد بلکه بیشتر به تحلیل طیفی ماتریس شباهت های نقطه به نقطه نیاز دارد…