خوشه‌بندی طیفی چیست؟ آموزش Spectral Clustering از مبانی تا کاربردها

1. چکیده

در مسائل خوشه‌بندی سنتی، مفروضاتِ مبنی بر “کروی بودن” یا “توزیع‌های محدب” خوشه‌ها، کارایی الگوریتم‌هایی نظیر K-Means را در مواجهه با داده‌های پیچیده محدود می‌کند. خوشه‌بندی طیفی (Spectral Clustering) به‌عنوان راهکاری مبتنی بر تئوری گراف، این محدودیت را با تبدیل فضای ویژگی به فضایی مبتنی بر “اتصال‌پذیری” (Connectivity) مرتفع می‌سازد. این الگوریتم با تجزیه طیفی ماتریس لاپلاسین گرافِ مجاورت، خوشه‌ها را بر اساس ساختار توپولوژیک داده‌ها شناسایی می‌کند. در این مقاله، ضمن تبیین بنیان‌های ریاضی این روش، به بررسی دقیق نحوه نگاشت بردارهای ویژه، تنظیم ابرپارامترها و کاربردهای صنعتی آن می‌پردازیم.

.

2. مقدمه

در فضای یادگیری بدون نظارت (Unsupervised Learning)، خوشه‌بندی یکی از چالش‌های بنیادین است. با رشد حجم و پیچیدگی داده‌ها، روش‌های کلاسیک که صرفاً بر فواصل اقلیدسی میان نقاط متکی هستند، در شناسایی ساختارهای غیرخطی (مانند حلقه‌ها یا خوشه‌های درهم‌تنیده) با شکست مواجه می‌شوند. روش‌های طیفی با الهام از فیزیک و هندسه محاسباتی، نگاهی نو به مسئله خوشه‌بندی دارند: داده‌ها نه صرفاً به عنوان نقاطی در فضای Rd ، بلکه به عنوان گره‌هایی در یک گراف متصل دیده می‌شوند. هدف این مقاله، بازخوانی انتقادی و فنی خوشه‌بندی طیفی است؛ به گونه‌ای که خواننده علاوه بر درک چرایی ریاضی این روش، نقشه راه اجرای آن را برای مسائل واقعی به دست آورد.

.

3. تعاریف و مفاهیم پایه

در Spectral Clustering ابتدا بررسی می‌کنیم که هر داده چقدر به داده‌های دیگر شبیه است. سپس از روی این شباهت‌ها یک شبکه یا گراف می‌سازیم. بعد با استفاده از ابزارهای جبر خطی، داده‌ها را به فضایی جدید منتقل می‌کنیم؛ فضایی که در آن گروه‌ها بهتر از هم جدا می‌شوند. در پایان، معمولاً از k-means برای خوشه‌بندی داده‌ها در این فضای جدید استفاده می‌کنیم.

یک بیان بسیار ساده:

Spectral Clustering ابتدا «رابطه میان داده‌ها» را یاد می‌گیرد، سپس داده‌ها را در فضایی بازنمایی می‌کند که خوشه‌های پنهان بهتر دیده شوند.

برای درک عمیق خوشه‌بندی طیفی، باید با تعاریف زیر مانوس باشیم:

• گراف مجاورت (Affinity Graph): نمایشی گراف‌گونه از داده‌ها که در آن هر نقطه xi​ یک گره است و وزن یال بین دو گرهwij ​، میزان شباهت (Similarity) آن‌ها را نشان می‌دهد. گرافی که در آن هر نمونه داده یک گره و شباهت بین نمونه‌ها وزن یال‌هاست
• Affinity Matrix   :  ماتریس شباهت بین همه جفت نمونه‌ها
• ماتریس وزن (Weight Matrix W): ماتریسی که شباهت زوجی تمام نقاط را در خود جای داده است.
• ماتریس درجه (Degree Matrix D): ماتریسی قطری که مجموع وزن‌های یال‌های متصل به هر گره را نشان می‌دهد؛ dii​=∑j​ wij
• تجزیه طیفی (Spectral Decomposition): فرآیند یافتن مقادیر ویژه (λ) و بردارهای ویژه (v) یک ماتریس که ویژگی‌های ساختاری آن را نمایان می‌کند.
• نگاشت ویژه (Eigenmap): تبدیلی که داده‌ها را از فضای اصلی به فضای برداریِ جدید (متشکل از بردارهای ویژه) می‌برد، به طوری که نقاط مشابه در فضای جدید، مجاورت بیشتری داشته باشند. فاصله بین مقادیر ویژه متوالی که می‌تواند برای تعیین تعداد خوشه‌ها استفاده شود.

.

4. مسئله‌ای که این روش حل می‌کند؛ اهمیت و ضرورت

بسیاری از الگوریتم‌های خوشه‌بندیِ مبتنی بر مرکز (Centroid-based)، مانند K-Means، به دلیل تابع هدف خود، تمایل دارند خوشه‌هایی با چگالی یکنواخت و شکل کروی تولید کنند. اما در جهان واقعی، داده‌ها اغلب ساختارهای غیرمحدب دارند؛ برای مثال، دو دایره هم‌مرکز یا دو ساختار مارپیچی در هم تنیده. در چنین مسائلی، فواصل اقلیدسی به تنهایی بیانگر حقیقتِ ساختاری داده نیستند.

خوشه‌بندی طیفی مسئله خوشه‌بندی را به یک مسئله برش گراف (Graph Cut) تبدیل می‌کند. در این رویکرد، هدف یافتن پارتیشنی از گراف است که یال‌های بین خوشه‌ها دارای کمترین وزن و یال‌های درون خوشه‌ها دارای بیشترین وزن باشند (Min-Cut). اهمیت این روش در این است که به جای تمرکز بر هندسه مطلق (Absolute Geometry)، بر هندسه نسبی (Relative Geometry) تمرکز دارد و می‌تواند “اتصال” را حتی در اشکال بسیار پیچیده و ناپیوسته شناسایی کند. این روش ضرورتی در تحلیل سیستم‌های دینامیک، تحلیل شبکه‌های اجتماعی و تشخیص ناهنجاری در داده‌های سری زمانی دارد.

.

5. مبانی نظری و ریاضی

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

به بیان ریاضی، اگر مجموعه داده به‌صورت زیر باشد:

X={x₁,x₂,…,x_n}

ابتدا یک گراف وزندار G = (V,E) ساخته می‌شود که در آن هر نمونه یک گره است. وزن یال بین دو گره i و j معمولاً با یک تابع شباهت تعریف می‌شود:

با استفاده از ماتریس درجه D و ماتریس شباهت A، لاپلاسیَن گراف ساخته می‌شود و بردارهای ویژه آن برای بازنمایی جدید داده‌ها استفاده می‌گردند.

ماتریس درجه

ماتریس درجه D یک ماتریس قطری است:

Dii=∑Aij

بنابراین Dii​ نشان می‌دهد که گره i در مجموع چقدر به سایر گره‌ها متصل است.

انواع لاپلاسیَن گراف

سه نوع لاپلاسیَن رایج عبارت‌اند از:

نوع لاپلاسیَن	فرمول
Unnormalized Laplacian	L=D−A
Symmetric Normalized Laplacian	Lsym​=I−(D^−1/2)A(D^−1/2)
Random Walk Laplacian	Lrw​=I−(D^−1)A

در نسخه Ng, Jordan, Weiss معمولاً از ماتریس زیر استفاده می‌شود:

D^−1/2AD^−1/2

که از نظر بردارهای ویژه، با لاپلاسیَن نرمال‌شده رابطه مستقیم دارد.

شهود الگوریتم

حال شهود اصلی Spectral Clustering این است که اگر داده‌ها واقعاً دارای k خوشه مجزا باشند، گراف شباهت نیز تقریباً به k مؤلفه متصل جداگانه تبدیل می‌شود. در حالت ایده‌آل، بردارهای ویژه لاپلاسیَن می‌توانند این مؤلفه‌ها را آشکار کنند.

به‌صورت شهودی:

• اگر دو نقطه به‌شدت شبیه باشند، در گراف با یال قوی به هم متصل می‌شوند.
• نقاط متعلق به یک خوشه، شبکه‌ای متراکم‌تر می‌سازند.
• نقاط متعلق به خوشه‌های مختلف، اتصال ضعیف‌تری دارند.
• eigenvectors لاپلاسیَن، این ساختار اتصال را در قالب مختصات جدید آشکار می‌کنند.

بنیان ریاضی خوشه‌بندی طیفی بر ماتریس لاپلاسین گراف (Graph Laplacian) استوار است. برای یک گراف با ماتریس وزن W و ماتریس درجه D، ماتریس لاپلاسین به صورت زیر تعریف می‌شود:

L=D−W

این ماتریس ویژگی‌های بنیادی گراف را در دل خود دارد. با این حال، در کاربردهای عملی معمولاً از ماتریس لاپلاسین نرمال‌شده (Normalized Laplacian) استفاده می‌شود تا پایداری عددی افزایش یابد. دو نوع رایج آن عبارتند از:

۱. لاپلاسین متقارن:

۲. لاپلاسین تصادفی (Random Walk):

تحلیل متغیرها:

• L: ماتریس لاپلاسین.
• W: ماتریس وزن (معمولاً محاسبه شده با هسته RBF:

• D: ماتریس قطری درجات.
• I: ماتریس واحد (Identity Matrix).
• σ: پارامتر پهنای باند (Bandwidth) که مقیاس محلی بودن شباهت را تعیین می‌کند.

قضیه اساسی در اینجا بیان می‌کند که کوچک‌ترین مقادیر ویژه (Eigenvalues) ماتریس لاپلاسین، اطلاعات کلیدی درباره ساختار جوامع (Communities) گراف را در خود دارند. بردار ویژه متناظر با کوچک‌ترین مقدار ویژه غیرصفر (که برای گراف‌های متصل همیشه صفر است)، نشان‌دهنده نحوه تقسیم بهینه گراف به دو بخش است. در واقع، این روش با انتقال داده‌ها به فضای برداری (Embedding)، مسئله را به یک فضای خطی منتقل می‌کند که در آن جداسازی خوشه‌ها به سادگیِ یک برش ساده (مثلاً با K-Means) امکان‌پذیر است.

.

6. مراحل گام‌به‌گام اجرای الگوریتم

خوشه‌بندی طیفی فرآیندی است که داده‌ها را از فضای ویژگی اولیه به یک فضای نهفته (Latent Space) منتقل می‌کند تا جداسازی خوشه‌های غیرخطی ممکن شود. گام‌های اجرایی به شرح زیر است:

1. ساخت ماتریس شباهت (Affinity Matrix W): ابتدا ماتریس وزن‌ها (W) را برای کل نقاط تشکیل می‌دهیم. رایج‌ترین روش، استفاده از تابع هسته گاوسی (RBF) است:

در اینجا σ نقش پارامتر مقیاس‌گذاری را دارد.

2. محاسبه ماتریس درجه و لاپلاسین: ماتریس درجه (D) را محاسبه کرده و سپس ماتریس لاپلاسین (معمولاً نوع متقارن Lsym) را تشکیل می‌دهیم.

3.تجزیه طیفی: مقادیر ویژه و بردارهای ویژه ماتریس لاپلاسین را محاسبه می‌کنیم.

4.انتخاب ابعاد (Embedding): بر اساس تعداد خوشه‌های مورد نظر (k)، k بردار ویژه اول (متناظر با کوچک‌ترین مقادیر ویژه) را انتخاب کرده و ماتریس   U∈ R n×k  را می‌سازیم که ستون‌های آن، این بردارهای ویژه هستند.

5.نرمال‌سازی (Normalization): برای اطمینان از عملکرد بهینه K-Means، سطرها را در ماتریس U به طول واحد (Unit Norm) نرمال می‌کنیم.

6.خوشه‌بندی نهایی: هر سطر از ماتریس نرمال‌شده را به عنوان یک نقطه جدید در فضای R^k در نظر گرفته و با الگوریتم K-Means، آن‌ها را به k خوشه دسته‌بندی می‌کنیم.

خلاصه نسخه کلاسیک Ng, Jordan, Weiss را می‌توان به‌صورت زیر بیان کرد:

گام	شرح
۱	دریافت داده‌ها x1,x2,…,xn​
۲	ساخت ماتریس شباهت A
۳	ساخت ماتریس درجه D
۴	ساخت ماتریس نرمال‌شده L=(D^−1/2)A(D^−1/2)
۵	استخراج k بردار ویژه اصلی
۶	تشکیل ماتریس embedding
۷	نرمال‌سازی سطری ماتریس embedding
۸	اجرای k-means روی سطرهای embedding
۹	انتساب برچسب خوشه‌ها به داده‌های اصلی

.

7.مثال‌های عددی

برای درک بهتر، یک مثال ساده را در نظر بگیرید. فرض کنید ۴ نقطه داریم که دو خوشه درهم‌تنیده را تشکیل می‌دهند: A,B نزدیک هم هستند و C,D نزدیک هم، اما بین زوج {A,B} و {C,D} فاصله زیادی وجود دارد.

• گام ۱: ماتریس W با وزن‌دهی نزدیک به ۱ برای جفت‌های {A,B} و {C,D} و وزن نزدیک به ۰ برای تقاطع‌ها تشکیل می‌شود.
• گام ۲: ماتریس لاپلاسین L محاسبه می‌شود.
• گام ۳: کوچک‌ترین بردار ویژه غیرصفر (v1​) استخراج می‌شود. برای این داده‌ها، این بردار احتمالاً مقادیر منفی برای {A,B} و مقادیر مثبت برای {C,D} خواهد داشت.
• گام ۴: نگاشت در فضای یک‌بعدی (k=1): نقاط در فضای برداری جدید به گونه‌ای قرار می‌گیرند که {A,B} در یک سمت محور (مقادیر منفی) و {C,D} در سمت دیگر (مقادیر مثبت) قرار گیرند.
• گام ۵: حالا کافی است یک برش در نقطه صفر روی محور انجام دهیم تا خوشه‌ها دقیقاً تفکیک شوند. این همان کاری است که K-Means روی بردارهای ویژه انجام می‌دهد.

.

مثال عددی ۱: جداسازی دو نقطه دور از هم (پایه نظری)

در این مثال بسیار ساده، هدف درک نحوه تشکیل ماتریس لاپلاسین و استخراج بردار ویژه برای تفکیک است. فرض کنید دو نقطه x1​ و x2​ داریم که شباهت آن‌ها بسیار کم است w12​=0.1.

• گام ۱: تشکیل ماتریس شباهت (W)

چون فقط دو نقطه داریم و شباهت هر نقطه با خودش ۱ است:

• گام ۲: تشکیل ماتریس درجه (D) و لاپلاسین (L)

مجموع سطرهای W مقادیر قطر D را می‌سازند: d11​=1+0.1=1.1

• گام ۳: محاسبه مقادیر ویژه (λ) و بردارهای ویژه (v)

معادله مشخصه:

• λ1​=0 (همیشه برای لاپلاسین صفر است) با بردار ویژه

• λ2​=0.2 با بردار ویژه

• تحلیل گام نهایی:

برای خوشه‌بندی، از v2 استفاده می‌کنیم. نقطه اول مقدار 1 و نقطه دوم مقدار 1− می‌گیرد. چون علامت‌ها متفاوت است، الگوریتم K-Means به راحتی این دو را در دو خوشه مجزا قرار می‌دهد.

.

مثال عددی ۲: خوشه‌های زنجیره‌ای (قدرت غیرخطی)

فرض کنید سه نقطه روی یک خط داریم: A(1), B(2) و C(10). می‌خواهیم ببینیم چرا Spectral Clustering متوجه می‌شود A و B یک خوشه هستند.

• گام ۱: محاسبه شباهت (با هسته RBF و σ=1)

• گام ۲: ماتریس لاپلاسین ساده شده

• گام ۳: تحلیل بردارهای ویژه

در اینجا ماتریس بلوکی است. یکی از بردارهای ویژه (متناظر با کوچکترین مقادیر ویژه غیر صفر) روی نقاط A و B متمرکز می‌شود و نقطه C را در مختصات کاملاً متفاوتی قرار می‌دهد. این نشان می‌دهد که حتی اگر C در همان فضای اقلیدسی باشد، به دلیل «عدم اتصال» (Zero Affinity)، از نظر طیفی کاملاً ایزوله می‌شود.

.

مثال عددی ۳: گراف دو بخشی و برش کمینه (Ratio Cut)

این مثال بر مبنای تئوری گراف است. گرافی با ۴ گره را در نظر بگیرید که دو بخش {1,2} و {3,4} درون خود کاملاً متصل (وزن یال = ۱) و بین خود فقط یک یال ضعیف (وزن = ۰.۱) دارند.

• گام ۱: ماتریس مجاورت وزنی (W)

• گام ۲: تشکیل لاپلاسین متقارن (Lsym​)

ابتدا D را محاسبه می‌کنیم: D=diag(1.1,1,1.1,1)

سپس Lsym​=I−(D^−1/2)W(D^−1/2)  با انجام محاسبات:

• گام ۳: استخراج بردار فیدلر (Fiedler Vector)

بردار ویژه دوم (v2)که به بردار فیدلر معروف است، در اینجا مقدار تقریبی زیر را خواهد داشت:

v2=[0.5,0.5,−0.5,−0.5]^T

• گام ۴: نگاشت و خوشه‌بندی

1. نقاط ۱ و ۲ به مقدار 0.5منتقل می‌شوند.
2. نقاط ۳ و ۴ به مقدار 0.5− منتقل می‌شوند.
3. الگوریتم K-Means در این فضای یک‌بعدی جدید، نقطه برش را روی صفر قرار داده و دو خوشه{1,2} و {3,4} را با دقت ۱۰۰٪ تفکیک می‌کند.

نتیجه‌گیری راه حل:

در هر سه مثال، مشاهده شد که جادوی اصلی در تغییر بازنمایی (Representation) نهفته است. داده‌هایی که در فضای اصلی ممکن بود همپوشانی داشته باشند یا جداسازی‌شان دشوار باشد، در فضای بردارهای ویژه به صورت خطی تفکیک‌پذیر (Linearly Separable) می‌شوند.

.

8. کاربردهای واقعی

خوشه‌بندی طیفی به دلیل توانایی در شناسایی ساختارهای غیرمحدب، در حوزه‌های زیر کاربرد گسترده‌ای دارد:

• بخش‌بندی تصاویر (Image Segmentation): پیکسل‌های یک تصویر اغلب خوشه‌های غیرخطی پیچیده تشکیل می‌دهند. گراف‌های پیکسل-به-پیکسل برای جداسازی اشیاء از پس‌زمینه از این روش بهره می‌برند.
• تشخیص جوامع در شبکه‌های اجتماعی (Community Detection): کاربران یک شبکه اجتماعی که ارتباطات متراکم دارند، خوشه‌هایی را تشکیل می‌دهند که با روش‌های هندسی سنتی قابل شناسایی نیستند.
• تحلیل داده‌های بیوانفورماتیک: خوشه‌بندی بیان ژن‌ها که دارای الگوهای همبستگی پیچیده و غیرخطی هستند.
• تشخیص ناهنجاری (Anomaly Detection): در سیستم‌های حساس که ناهنجاری‌ها ساختارهای جداافتاده (Outlier) در فضای غیرخطی تشکیل می‌دهند.

در جدول زیر بعضی از کاربردها تعریف شده است:

حوزه	کاربرد
Computer Vision	image segmentation، object grouping
Bioinformatics	clustering ژن‌ها، پروتئین‌ها، سلول‌ها
Social Network Analysis	community detection
Document Mining	خوشه‌بندی اسناد بر اساس شباهت معنایی
Recommender Systems	کشف گروه‌های کاربران یا آیتم‌ها
Medical Imaging	segmentation بافت یا ناحیه آسیب
Graph Mining	partitioning گراف‌های بزرگ
Pattern Recognition	تشخیص الگوهای پیچیده و غیرخطی

.

9.مزایا

• انعطاف‌پذیری هندسی: توانایی شناسایی خوشه‌هایی با اشکال غیرمحدب، مارپیچی و اشکال پیچیده توپولوژیک.
• پایداری نظری: مبتنی بر تئوری طیفی گراف است که تضمین‌های ریاضی قوی‌تری نسبت به روش‌های اکتشافی (Heuristic) دارد.
• استقلال از مرکز: برخلاف K-Means، نیازی به محاسبه مرکزِ خوشه (Centroid) ندارد که برای داده‌های غیرمحدب تعریف‌نشده است.
• سازگاری با هر نوع Similarity: هر معیاری که بتواند “شباهت” را کمی‌سازی کند (مانند شباهت معنایی در NLP)، در این الگوریتم قابل استفاده است.

به اختصار مزایا در جدول زیر لیست شده است:

مزیت	توضیح
توانایی کشف خوشه‌های غیرمحدب	برای nested circles و moon-shaped data مناسب است
استفاده از ساختار گرافی	روابط محلی و جهانی را در نظر می‌گیرد
انعطاف در تعریف شباهت	می‌توان از RBF، kNN یا affinity سفارشی استفاده کرد
مبنای نظری قوی	مبتنی بر graph cut، spectral graph theory و relaxation
کاربرد وسیع	vision، bioinformatics، networks، text mining
قابل‌ترکیب با روش‌های جدید	GNN، multi-view learning، graph structure learning

 10.محدودیت‌ها و معایب

• هزینه محاسباتی: تجزیه طیفی ماتریس n×n دارای پیچیدگی محاسباتی O(n^3) است که مقیاس‌پذیری آن را برای مجموعه‌داده‌های بسیار بزرگ (Big Data) محدود می‌کند.
• حساسیت به انتخاب پارامتر σ: انتخاب نادرست پهنای باند (σ) می‌تواند منجر به گراف‌های بیش از حد متصل (Disconnected) یا گسسته شود که خروجی را کاملاً مختل می‌کند.
• نیاز به تعیین k: همانند سایر الگوریتم‌های خوشه‌بندی، تعیین تعداد خوشه‌ها (k) پیش از اجرا ضروری است که خود چالشی مستقل است.
• حساسیت به نویز: در داده‌های با نویز بالا، ماتریس شباهت ممکن است یال‌های کاذب زیادی ایجاد کند که ساختار واقعی گراف را مخدوش می‌کند.

بخشی از محدودیت‌ها در جدول زیر به اختصار توضیح داده شده است:

محدودیت	توضیح
هزینه محاسباتی بالا	eigendecomposition برای داده‌های بزرگ سنگین است
حافظه زیاد	affinity matrix کاملO(n^2) حافظه می‌خواهد
حساسیت به پارامترها	σ ، γ ، k، و نوع affinity بسیار مهم‌اند
وابستگی به کیفیت گراف	graph construction بد، خروجی بد تولید می‌کند
نیاز به تعداد خوشه‌ها	معمولاً باید k از قبل مشخص شود
حساسیت به noise	نویز می‌تواند ساختار طیفی را مخدوش کند
دشواری تفسیر	embedding طیفی همیشه به‌سادگی قابل‌تفسیر نیست

.

11.ابرپارامترها و تنظیم

تنظیم صحیح این الگوریتم کلید موفقیت در پروژه‌های عملی است:

• تعداد خوشه‌ها (k): معمولاً با تحلیل “شکاف طیفی” (Eigengap Heuristic) انتخاب می‌شود؛ یعنی شکاف بزرگ بین مقادیر ویژه متوالی، معمولاً نشان‌دهنده تعداد بهینه خوشه‌هاست.
• پارامتر مقیاس (σ):
• اگر σ خیلی کوچک باشد، گراف به مولفه‌های متصلِ بیش از حد کوچک تبدیل می‌شود.
• اگر σ خیلی بزرگ باشد، گراف کاملاً متصل می‌شود و ساختار خوشه‌ها گم می‌شود.
• راهبرد: استفاده از روش “Self-tuning” برای تعیین σ به صورت محلی برای هر نقطه.
• انتخاب نوع ماتریس لاپلاسین: لاپلاسین نرمال‌شده معمولاً نسبت به لاپلاسین ساده (L=D−W) برای داده‌های با توزیع نابرابر در خوشه‌ها عملکرد پایدارتری دارد.
•  

ابرپارامتر	تعریف	اثر	روش تنظیم
k یا n_clusters	تعداد خوشه‌ها	تعیین ابعاد embedding و تعداد خوشه‌ها	eigengap، silhouette، دانش دامنه
σ	پهنای kernel گاوسی	کنترل میزان محلی یا جهانی بودن شباهت	grid search، heuristic، cross-validation
γ	ضریب kernel در RBF	هرچه بیشتر باشد، شباهت سریع‌تر افت می‌کند	معمولاً γ=1/(2σ^2)
affinity	نوع ساخت ماتریس شباهت	اثر بسیار زیاد بر خروجی	RBF، kNN، precomputed
n_neighbors	تعداد همسایگان در گراف kNN	کنترل sparsity گراف	آزمون حساسیت
eigen_solver	روش محاسبه بردارهای ویژه	اثر بر سرعت و پایداری	ARPACK، LOBPCG، AMG
assign_labels	روش انتساب برچسب	اثر بر پایداری خروجی	k-means، discretize، cluster_qr
n_init	تعداد اجرای k-means	کاهش حساسیت به مقداردهی اولیه	افزایش برای پایداری بیشتر

12.مقایسه با روش‌های مشابه

برای درک جایگاه خوشه‌بندی طیفی، مقایسه آن با سایر الگوریتم‌های پرکاربرد خوشه‌بندی ضروری است. در حالی که الگوریتم‌های مبتنی بر مرکز (مانند K-Means) بر هندسه اقلیدسی تمرکز دارند، روش‌های طیفی بر توپولوژی و اتصال‌یافتگی گراف تأکید می‌کنند.

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

معیار مقایسه	خوشه‌بندی طیفی (Spectral)	K-Means	DBSCAN
فرض هندسی	غیرمحدب و پیچیده	کروی (محدب)	چگالی‌محور
پیچیدگی محاسباتی	O(n^3)	O(n⋅k⋅I)	O(nlogn)
مقیاس‌پذیری	پایین (برای داده‌های بزرگ)	بسیار بالا	بالا
نیاز به تعیین k	بله (تعداد خوشه‌ها)	بله (تعداد خوشه‌ها)	خیر (پارامتر شعاع)
حساسیت به نویز	متوسط	بالا	پایین

همان‌طور که مشاهده می‌شود، انتخاب بین این روش‌ها یک موازنه (Trade-off) بین «دقت در هندسه‌های پیچیده» (نقطه قوت طیفی) و «هزینه محاسباتی» است.

تفاوت‌ها و شباهت‌ها با بعضی از الگوریتم‌ها در جدول زیر توضیح داده شده است:

الگوریتم	شباهت	تفاوت اصلی
k-means	مرحله نهایی بسیاری از نسخه‌های SC	k-means مستقیم روی داده خام اجرا می‌شود
Kernel k-means	استفاده از نگاشت غیرخطی	Spectral Clustering بر graph Laplacian متکی است
DBSCAN	مناسب برای خوشه‌های غیرمحدب	نیاز به چگالی دارد، نه eigendecomposition
Agglomerative Clustering	استفاده از شباهت/فاصله	سلسله‌مراتبی است
Affinity Propagation	مبتنی بر شباهت جفتی	تعداد خوشه‌ها را متفاوت تعیین می‌کند
Community Detection	مبتنی بر گراف	بیشتر برای شبکه‌ها و modularity
Graph Partitioning	تقسیم گراف	Spectral Clustering صورت یادگیری ماشینی آن است

.

13.نوآوری‌ها و چشم‌انداز آینده

در سال‌های اخیر، تحقیقات متعددی برای رفع محدودیت مقیاس‌پذیری و ارتقای دقت خوشه‌بندی طیفی انجام شده است:

• روش‌های مبتنی بر Nyström: برای غلبه بر پیچیدگیO(n^3) ، استفاده از تقریب‌های ماتریسی مانند Nyström یا روش‌های هسته پراکنده (Sparse Kernels) رایج شده است که اجازه می‌دهد خوشه‌بندی طیفی بر روی داده‌های بسیار بزرگ نیز اجرا شود.
• خوشه‌بندی طیفی عمیق (Deep Spectral Clustering): تلفیق معماری شبکه‌های عصبی (مانند Autoencoders) با روش‌های طیفی. در این رویکرد، شبکه عصبی، فضای نهفته (Embedding) را یاد می‌گیرد و همزمان نگاشت طیفی را بهینه می‌کند.
• شبکه‌های عصبی گراف (GNNs): خوشه‌بندی طیفی را می‌توان به نوعی “پدربزرگ” الگوریتم‌های فعلی GNN دانست. امروزه لایه‌های کانولوشن گراف (Graph Convolutional Layers) عملاً نوعی پیاده‌سازی یادگیری‌شده از فیلترهای لاپلاسین هستند که آینده این حوزه را رقم می‌زنند.

انواع Spectral Clustering

نوع	توضیح
Unnormalized Spectral Clustering	استفاده از L=D−A
Normalized Spectral Clustering	استفاده از لاپلاسیَن نرمال‌شده
Normalized Cut	تمرکز بر تقسیم متوازن گراف
Ratio Cut	معیار کلاسیک‌تر برای graph cut
Random Walk Spectral Clustering	تفسیر بر اساس زنجیره مارکوف روی گراف
Kernel Spectral Clustering	استفاده از kernel برای ساخت affinity
Multi-view Spectral Clustering	ترکیب چند نمای داده
Approximate Spectral Clustering	روش‌های تقریبی برای داده‌های بزرگ
Anchor-Based Spectral Clustering	استفاده از نقاط anchor برای کاهش هزینه
Graph Structure Learning-Based SC	یادگیری هم‌زمان یا اصلاح ساختار گراف

پیشرفت‌های پژوهشی جدید از ۲۰۲۲ به بعد

محور پژوهشی	توضیح
Graph Structure Learning	بهبود یا یادگیری ماتریس affinity به‌جای تعریف دستی آن
Scalable Spectral Clustering	کاهش هزینه محاسباتی برای داده‌های بزرگ
Anchor-Based Methods	استفاده از نقاط نماینده برای کاهش ابعاد گراف
Multi-view Spectral Clustering	ترکیب چند نوع ویژگی یا چند منبع داده
Deep Spectral Clustering	ترکیب neural networks با اهداف طیفی
GNN-Based Spectral Methods	استفاده از ایده‌های spectral در graph neural networks
Robust Spectral Clustering	افزایش مقاومت در برابر نویز و outlier
Self-supervised Graph Clustering	ترکیب contrastive learning و graph clustering

ترندهای آینده

روند آینده	توضیح
spectral clustering برای big data	توسعه solverهای سریع‌تر و تقریبی‌تر
ترکیب با deep learning	یادگیری embeddingهای عمیق با قیود طیفی
یادگیری خودکار graph construction	کاهش وابستگی به انتخاب دستی affinity
خوشه‌بندی چندنمایی	استفاده از داده‌های چندمنبعی
کاربرد در GNNها	pooling، graph coarsening، و community discovery
روش‌های online و streaming	پردازش داده‌های پویا
explainable spectral clustering	تفسیرپذیر کردن خوشه‌ها و eigenvectors

.

14.جمع‌بندی

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

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

.

15.منابع

برای مطالعه بیشتر و ارجاع علمی، منابع زیر هسته اصلی دانش خوشه‌بندی طیفی را تشکیل می‌دهند:

Aggarwal, C. C., & Reddy, C. K. (Eds.). (2013/2014). Data Clustering: Algorithms and Applications. CRC Press.

Alpaydin, E. (2020). Introduction to Machine Learning. MIT Press.

Belkin, M., & Niyogi, P. (2003). Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6), 1373-1396.

Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer.

Cai, D., & Chen, X. (2011). Document clustering using locality preserving indexing. IEEE Transactions on Knowledge and Data Engineering, 23(12), 1779-1791.

Chung, F. R. K. (1997). Spectral Graph Theory. American Mathematical Society.

Duda, R. O., Hart, P. E., & Stork, D. G. (2000). Pattern Classification. Wiley.

Fowlkes, C., Belongie, S., Chung, F., & Malik, J. (2004). Spectral grouping using the Nyström method. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2), 214-225.

Géron, A. (2019/2022). Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow. O’Reilly.

Han, J., Kamber, M., & Pei, J. (2012). Data Mining: Concepts and Techniques (3rd ed.). Morgan Kaufmann.

Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed.). Springer.

hi, J., & Malik, J. (2000). Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905. https://doi.org/10.1109/34.868688

Kipf, T. N., & Welling, M. (2017). Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations.

Meilă, M., & Shi, J. (2001). A random walks view of spectral segmentation. Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics.

Meilă, M., & Shi, J. (2001). A random walks view of spectral segmentation. Proceedings of AISTATS.

.

Murphy, K. P. (2022). Probabilistic Machine Learning: An Introduction. MIT Press.

Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002). On spectral clustering: Analysis and an algorithm. Advances in Neural Information Processing Systems (pp. 849-856).

Pedregosa, F., et al. (2011). Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12, 2825-2830.

Shi, J., & Malik, J. (2000). Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888-905.

Spielman, D. A., & Teng, S. H. (2004). Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. Proceedings of the 36th Annual ACM Symposium on Theory of Computing.

Tan, P.-N., Steinbach, M., & Kumar, V. (2019). Introduction to Data Mining. Pearson.

von Luxburg, U. (2007). A tutorial on spectral clustering. Statistics and Computing, 17, 395–416. https://doi.org/10.1007/s11222-007-9033-z

von Luxburg, U., Belkin, M., & Bousquet, O. (2008). Consistency of spectral clustering. The Annals of Statistics, 36(2), 555–586.

Weiss, Y. (1999). Segmentation using eigenvectors: A unifying view. Proceedings of the Seventh IEEE International Conference on Computer Vision.

Xie, J., Girshick, R., & Farhadi, A. (2016). Unsupervised deep embedding for clustering analysis. International Conference on Machine Learning.

Zhang, X., et al. (2019). Deep spectral clustering. Proceedings of the 28th International Joint Conference on Artificial Intelligence.

Zhou, D., & Schölkopf, B. (2004). Learning from labeled and unlabeled data using random walks. Pattern Recognition.

مستندات رسمی و فنی

scikit-learn. SpectralClustering documentation.

scikit-learn. Clustering User Guide.

SciPy. Sparse linear algebra and eigenvalue solvers.

NumPy. Linear algebra documentation.

PyTorch Geometric. Graph neural network pooling and graph operations documentation.

16.تمرین‌های پیشنهادی پایان فصل

• تمرین‌های مفهومی

1. توضیح دهید چرا k-means روی داده‌های دو حلقه تو در تو عملکرد ضعیفی دارد.
2. نقش ماتریس affinity در Spectral Clustering چیست؟
3. تفاوت بین L، Lsym​، و Lrw​ را توضیح دهید.
4. چرا Normalized Cut نسبت به cut خام مناسب‌تر است؟
5. مفهوم eigengap را توضیح دهید و کاربرد آن را در تعیین تعداد خوشه‌ها بیان کنید.

• تمرین‌های محاسباتی

1. برای یک مجموعه داده ۵ نقطه‌ای، ماتریس شباهت RBF را محاسبه کنید.
2. برای ماتریس affinity داده‌شده، degree matrix و Laplacian را به‌دست آورید.
3. eigenvalues یک لاپلاسیَن کوچک را محاسبه و تفسیر کنید.
4. اثر تغییر σ را روی ماتریس affinity بررسی کنید.

• تمرین‌های پیاده‌سازی

1. الگوریتم Spectral Clustering را روی داده two moons با Python اجرا کنید.
2. خروجی k-means و Spectral Clustering را روی nested circles مقایسه کنید.
3. پارامتر gamma را تغییر دهید و اثر آن را روی خوشه‌ها تحلیل کنید.
4. سه روش assign_labels=’kmeans’، discretize و cluster_qr را مقایسه کنید.
5. با استفاده از affinity=’nearest_neighbors’ اثر n_neighbors را بررسی کنید.