پیش‌نویس:الگوریتم خوشه‌بندی طیفی

در آمار چند متغیره، تکنیک‌های خوشه‌بندی طیفی از طیف یا اسپکتروم ماتریس شباهت داده‌ها برای انجام کاهش ابعاد قبل از خوشه‌بندی استفاده می‌کنند. ماتریس مشابهت به عنوان ورودی ارائه می شود و شامل یک ارزیابی کمی از شباهت نسبی هر جفت نقطه در مجموعه داده است.این خوشه‌بندیْ خود در نهایت از الگوریتم‌های خوشه‌بندی مانند KMeans استفاده می‌کند، ولی قبل از آن یک سری تغییر در ساختار داده‌ها به وجود می‌آورد.

تعریف

در روش خوشه‌بندی طیفی، ابتدا بر اساس ویژگی‌های موجود در داده‌ها، یک ماتریس وزن ساخته می‌شود. سپس با استفاده ازماتریس مشابهت (Similarity Matrix) به صورت یک ماتریس متقارن مانند A تعریف میشود که $A_{ij}\ge 0$ و مشابهت را بین داده‌هایی با اندیس‌های i و j اندازه میگیرد. ویژگی اصلی الگوریتم خوشه بندی طیفی این است که در نهایت روی بردار‌های ویژه ماتریس لاپلاسین که از A ساخته شده از روش های متداول خوشه‌بندی مانند KMeans استفاده میکند.راه های مختلفی برای تعریف لاپلاسین وجود دارد که تعریف ریاضی متفاوتی دارند و بنابراین خوشه بندی نیز تعریف‌های متفاوتی خواهد داشت.

الگوریتم

در این روش ابتدا گراف مربوط به داده‌ها را ساخته و سپس با استفاده از روش‌های مختلفی این گراف را به دو بخش تقسیم می‌کنیم، به گونه‌ای که داده‌های هر بخش از یکدیگر متمایز باشند.

توضیح مرحله به مرحله الگوریتم پایه:

۱- ابتدا ماتریس لاپلاسین را محاسبه کنید.

۲ - اولین k بردار ویژه (بردارهای ویژه مربوط به k کوچکترین مقادیر ویژه L) را محاسبه کنید.

۳ - ماتریس تشکیل شده توسط اولین بردارهای ویژه k را در نظر بگیرید. ردیف l ویژگی های گره گراف l را مشخص می کند.

۴ - گره های گراف را بر اساس این ویژگی ها خوشه بندی کنید.

خوشه‌بندی طیفی ارتباط نزدیکی با کاهش ابعاد غیرخطی دارد و تکنیک‌های کاهش ابعاد مانند تعبیه خطی موضعی (locally-linear embedding) می‌تواند برای کاهش خطاهای ناشی از نویز یا نقاط پرت استفاده شود.

مقایسه ‌خوشه بندی طیفی با دیگر الگوریتم‌های خوشه بندی

اما در مقایسه با دیگر الگوریتم‌ها، خوشه‌بندی طیفی دارای ویژگی‌هایی است که آن را به یک روش قدرتمند و مفید برای خوشه‌بندی داده‌های پیچیده تبدیل کرده است. برای مثال، خوشه‌بندی طیفی می‌تواند با داده‌هایی که در فضای بزرگ و پیچیده قرار دارند، به خوبی کار کند. همچنین، این الگوریتم می‌تواند با داده‌هایی که توزیع غیرخطی دارند، به خوبی کار کند و می‌تواند خوشه‌هایی را شناسایی کند که در الگوریتم‌های دیگر شناسایی نمی‌شوند.

بنابراین، با توجه به ویژگی‌های خاص خوشه‌بندی طیفی، این الگوریتم می‌تواند به عنوان یکی از الگوریتم‌های اصلی در خوشه‌بندی داده‌ها مورد استفاده قرار گیرد. هر چند که انتخاب الگوریتم مناسب برای خوشه‌بندی به عوامل مختلفی بستگی دارد، اما با در نظر گرفتن ویژگی‌های خاص خوشه‌بندی طیفی، می‌توان آن را به عنوان یک گزینه قوی در برنامه‌های خوشه‌بندی داده‌ها در نظر گرفت.

خوشه بندی طیفی در مقابل k-means

خوشه بندی طیفی با استفاده از ماتریس وابستگی داده‌ها، به داده‌هایی با ساختار پیچیده و غیرخطی بهتر عمل می‌کند. اما K-Means با توجه به مراکز خوشه‌ها، برای داده‌هایی با ساختار خطی و ساده، بهتر عمل می‌کند همچنین در خوشه‌بندی طیفی، برای محاسبه ماتریس وابستگی، نیاز به محاسبه ماتریس نزدیکی داده‌ها و ماتریس گراف وجود دارد، در حالی که در K-Means تنها نیاز به محاسبه فاصله داده‌ها تا مراکز خوشه‌هاست و برای حل مسئله خوشه‌بندی، از روش‌های انتقال پذیری و تجزیه مقادیر ویژه استفاده می‌شود، در حالی که در K-Means از روش انتقال وزنی استفاده می‌شود.

خوشه بندی طیفی در مقابل DBSCAN

در مقابل، در روش خوشه‌بندی طیفی، برای محاسبه ماتریس وابستگی داده‌ها، نیاز به محاسبه ماتریس نزدیکی و ماتریس گراف داریم، در حالی که در DBSCAN فاصله داده‌ها به هم نسبت به یک شعاع تعیین شده است و نیازی به محاسبه این ماتریس‌ها نداریم همچنین در DBSCAN، داده‌های نویزی نیز شناسایی و از خوشه‌بندی خارج می‌شوند. اما در خوشه‌بندی طیفی، داده‌هایی که دورتر از خوشه‌ها هستند، به عنوان داده‌هایی که به هیچ یک از خوشه‌ها تعلق ندارند، شناخته می‌شوند و به عنوان داده‌هایی جداگانه محسوب می‌شوند.

هزینه محاسباتی

اولین هزینه محاسبه شده در الگوریتم خوشه‌بندی طیفی، هزینه محاسبه ماتریس همبستگی است. برای محاسبه ماتریس همبستگی، باید هر نقطه داده‌ای را با سایر نقاط داده‌ای در فضای بعد بالا مقایسه کرد که هزینه زمانی بسیار بالا دارد. بنابراین، برای داده‌های بزرگ، اجرای الگوریتم خوشه‌بندی طیفی هزینه بسیار بالایی دارد.

دومین هزینه محاسبه شده برای الگوریتم خوشه‌بندی طیفی، هزینه محاسبه بردارهای ویژه است. برای محاسبه بردارهای ویژه، باید ماتریس لاپلاسین را محاسبه کرد که همچنین هزینه زمانی بسیار بالایی دارد. همچنین، اگر تعداد نقاط داده‌ای بسیار زیاد باشد، حافظه لازم برای ذخیره بردارهای ویژه نیز بسیار بالاست.

به عنوان یک راه حل برای این مشکلات، می‌توان از تکنیک‌هایی مانند تقریب ماتریس همبستگی و یا تقریب بردارهای ویژه استفاده کرد. این روش‌ها، هزینه محاسبه الگوریتم خوشه‌بندی طیفی را کاهش می‌دهند، اما دقت را کاهش میدهند.

سومین هزینه محاسبه شده برای الگوریتم خوشه‌بندی طیفی، هزینه محاسبه خوشه‌ها است. برای محاسبه خوشه‌ها، باید بردارهای ویژه و ماتریس اولویت را محاسبه کرد و سپس الگوریتم خوشه‌بندی را اعمال کرد. همچنین، باید یک آستانه تعیین کرد که نقاطی که در بردارهای ویژه ضعیف‌تر هستند، به کدام خوشه تعلق می‌گیرند. این هزینه نیز برای داده‌های بزرگ بسیار بالاست.

آخرین هزینه محاسبه شده برای الگوریتم خوشه‌بندی طیفی، هزینه حافظه است. برای محاسبه بردارهای ویژه و ماتریس اولویت، باید حافظه زیادی را برای ذخیره آن‌ها در نظر گرفت. این مشکل برای داده‌های بزرگ بسیار واضح‌تر است.

در کل، الگوریتم خوشه‌بندی طیفی معمولاً در مقایسه با الگوریتم‌های خوشه‌بندی دیگر مانند k-means، هزینه زمانی و حافظه بیشتری دارد. اما در مقابل، این الگوریتم به خوبی با داده‌های غیر خطی و یا داده‌هایی که شکل‌های خوشه‌های آن‌ها پیچیده هستند، سازگاری دارد. همچنین، این الگوریتم قابلیت تشخیص تعداد خوشه‌ها را نیز دارد که در برخی موارد بسیار مهم است. در نهایت، انتخاب الگوریتم خوشه‌بندی باید بر اساس خصوصیات داده‌ها و هدف مورد نظر از خوشه‌بندی صورت گیرد.

منابع

۱.spectral clustring wikipedia