خوشهبندی طیفی (Spectral Clustering)
- معرفیشده توسط
- Ng, A. Y.; Jordan, M. I.; Weiss, Y.
- سال
- 2002
- نوع
- Graph-based clustering (spectral method)
این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید
چه کاری انجام میدهد؟
خوشهبندی طیفی یک الگوریتم یادگیری بدون نظارت مبتنی بر گراف است که در سال ۲۰۰۲ توسط Ng، Jordan و Weiss فرموله شد. این الگوریتم نقاط داده را به یک فضای ویژه کمبعد که از لاپلاسین گراف شباهت مشتق شده است، نگاشت میکند و سپس از الگوریتم k-means استفاده میکند. این جاسازی طیفی امکان بازیابی خوشههایی با شکل دلخواه — حلقهها، هلالیها، مارپیچهای درهمتنیده — را فراهم میکند که روشهای مبتنی بر فاصله اقلیدسی به طور مداوم در تفکیک آنها شکست میخورند.
شهود پشت روش
الگوریتم استاندارد k-means فضا را بر اساس فاصله خط مستقیم تقسیمبندی میکند، بنابراین فقط میتواند تودههای محدب و تقریباً کروی را پیدا کند. خوشهبندی طیفی با در نظر گرفتن دادهها به عنوان یک شبکه، از این محدودیت عبور میکند: هر نقطه یک گره است و یالهای بین گرهها وزنی را حمل میکنند که نشاندهنده میزان شباهت دو نقطه است. خوشهها متناظر با مناطقی از شبکه هستند که از نظر داخلی متراکم و از نظر خارجی به طور ضعیف به هم متصل هستند. ماتریس لاپلاسین گراف ساختار اتصال این شبکه را رمزگذاری میکند و کوچکترین بردارهای ویژه آن مانند یک سیستم مختصات هموار عمل میکنند که دادهها را طوری کشش میدهند که خوشههای به خوبی جدا شده حتی زمانی که در فضای اصلی در هم تنیده بودند، از هم دور قرار گیرند. سپس یک مرحله ساده k-means در آن سیستم مختصات جدید، آنها را به وضوح جدا میکند.
تاریخ
مبانی نظری خوشهبندی طیفی به کار Fiedler در سال ۱۹۷۳ در مورد اتصال گراف و مقدار ویژه اتصال جبری بازمیگردد. Shi و Malik (۲۰۰۰) این رویکرد را از طریق معیار نرمالشده برش (normalized-cuts) خود برای بخشبندی تصویر به بینایی کامپیوتر آوردند. Ng، Jordan و Weiss (۲۰۰۲) یک الگوریتم تمیز و عمومی در NIPS ارائه کردند — الگوریتمی که اکنون بیشتر مورد استناد قرار میگیرد — همراه با تحلیلی مبتنی بر اغتشاش که توضیح میدهد این روش چه زمانی و چرا کار میکند. مقاله مروری Von Luxburg در سال ۲۰۰۷ در Statistics and Computing فرمولبندیهای رقیب را یکپارچه کرد، نقش نرمالسازی لاپلاسین را روشن ساخت و به مرجع استاندارد برای دستاندرکاران تبدیل شد. خوشهبندی طیفی اکنون جایگاه مرکزی در برنامه درسی یادگیری ماشین اشغال کرده و موضوع تحقیقاتی فعالی باقی مانده است، با کارهای جاری بر روی تقریبهای مقیاسپذیر، هستههای مقاوم و بسطها برای گرافها و منیفولدها.
چه زمانی استفاده شود
خوشهبندی طیفی زمانی مناسب است که خوشهها در دادهها غیرمحدب، غیرخطی قابل تفکیک، یا با پلهای نازک به هم متصل باشند که روشهای پارتیشنبندی اقلیدسی قادر به تشخیص آنها نیستند — نمونههای رایج شامل خوشههای حلقهای شکل، مارپیچهای درهمتنیده و بخشهای تصویر است. این روش زمانی مناسب است که شباهت دوتایی بین نقاط را بتوان به طور معنیداری محاسبه کرد (چه از طریق یک هسته بر روی ویژگیهای خام و چه از طریق یک ماتریس وابستگی از پیش ارائه شده)، و زمانی که تعداد خوشهها k معلوم باشد یا بتوان آن را از هیوریستیک شکاف ویژه تخمین زد. این روش هیچ فرض توزیعی بر شکل خوشهها ندارد. محدودیتهای عملی شامل حافظه درجه دوم نسبت به تعداد نقاط (برای ماتریس وابستگی کامل) و زمان درجه سوم برای تجزیه ویژه است که فرمولبندی استاندارد را برای بیش از حدود ۱۰,۰۰۰ نقطه پرهزینه میکند. روشهای تقریبی (Nystrom، گرافهای پراکنده، SVD تصادفی) دامنه کاربرد آن را به مجموعه دادههای بزرگتر گسترش میدهند.
محدودیتها و ملاحظات
- ساخت ماتریس وابستگی کامل n در n نیازمند حافظه O(n^2) و زمان O(n^3) برای تجزیه ویژه است، که الگوریتم خام را برای مجموعه دادههای بزرگ غیرقابل اجرا میکند.
- نتایج به انتخاب پهنای باند هسته sigma و استراتژی ساخت گراف حساس هستند؛ انتخابهای نادرست میتوانند خوشهها را ادغام یا تقسیم کنند.
- مقداردهی اولیه k-means در جاسازی طیفی، تصادفی بودن را معرفی میکند؛ اجراهای مختلف ممکن است پارتیشنهای متفاوتی تولید کنند.
- بدون انتخاب دقیق هسته، به خوبی به فضاهای ویژگی با ابعاد بسیار بالا مقیاسپذیر نیست.
- فقط برچسبهای خوشه را ارائه میدهد؛ هیچ مدل مولدی و هیچ بسط طبیعی خارج از نمونه برای نقاط جدید ارائه نمیدهد.
شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.
نقاط قوت
- خوشههایی با شکل دلخواه، از جمله پیکربندیهای غیرمحدب و غیرخطی قابل تفکیک را که k-means و مدلهای مخلوط گوسی را شکست میدهند، تشخیص میدهد.
- میتواند بر روی هر ماتریس شباهت دوتایی عمل کند، نه فقط فواصل اقلیدسی، که آن را برای گرافها، رشتهها و سایر دادههای ساختاریافته قابل استفاده میکند.
- هیوریستیک شکاف ویژه، راهنمایی اصولی مبتنی بر داده برای انتخاب تعداد خوشهها k ارائه میدهد.
- بر اساس نظریه غنی گراف طیفی بنا شده است که امکان تحلیل رسمی همگرایی و کیفیت خوشه را فراهم میکند.
- مفهوم ساده و با استفاده از کتابخانههای استاندارد جبر خطی به راحتی قابل پیادهسازی است.
کاربردها
- بخشبندی تصویر: تقسیم پیکسلها یا سوپرپیکسلها به نواحی منسجم ادراکی با استفاده از شباهت ویژگی در سطح پیکسل.
- تشخیص جامعه در شبکههای اجتماعی و بیولوژیکی که در آن اتصال دوتایی به جای بردارهای ویژگی، ساختار را تعریف میکند.
- بیوانفورماتیک: گروهبندی ژنها یا پروتئینها بر اساس شباهت پروفایل بیان، که در آن خوشههای بیان به ندرت در فضای ژن محدب هستند.
- پردازش زبان طبیعی: خوشهبندی اسناد یا جملات با استفاده از هستههای شباهت معنایی.
- بینایی کامپیوتر: بخشبندی حرکت و پارتیشنبندی ابر نقاط که در آن مرزهای خوشه نامنظم هستند.
- تحلیل اکتشافی دادهها: آشکارسازی ساختار خوشه غیرواضح قبل از اعمال روشهای تأییدی.
چگونه کار میکند
چگونه کار میکند
یک ماتریس شباهت (وابستگی) دوتایی W از دادهها ساخته میشود. رایجترین انتخاب، هسته گوسی (RBF) است که وزن بالایی به جفتهای نزدیک و وزنی نزدیک به صفر به جفتهای دور اختصاص میدهد. پارامتر پهنای باند sigma کنترل میکند که شباهت با فاصله با چه سرعتی کاهش مییابد؛ انتخاب صحیح آن حیاتی است. به طور جایگزین، میتوان از گراف k-نزدیکترین همسایه برای نمایشهای پراکندهتر در مجموعه دادههای بزرگ استفاده کرد.
فرمول
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)ماتریس درجه D، ماتریس قطری است که درایه i-ام آن مجموع سطر i-ام W است. از W و D، لاپلاسین گراف نرمالشده (متقارن) L_sym تشکیل میشود. این ماتریس ساختار اتصال کامل گراف شباهت را ثبت میکند؛ طیف مقادیر ویژه آن نشان میدهد که دادهها حاوی چند خوشه طبیعی هستند و چقدر به خوبی از هم جدا شدهاند.
فرمول
L_{\mathrm{sym}} = D^{-1/2}(D - W)D^{-1/2} = I - D^{-1/2}W D^{-1/2}k بردار ویژه متناظر با k کوچکترین مقادیر ویژه L_sym محاسبه میشوند. این بردارها ستونهای ماتریس جاسازی U را تشکیل میدهند که در آن هر سطر مربوط به یک نقطه داده است. در این فضای ویژه k-بعدی، نقاطی که به یک خوشه تعلق دارند حتی اگر در فضای ویژگی اصلی در هم تنیده بودند، به هم نزدیک کشیده میشوند.
فرمول
L_{\mathrm{sym}}\, u = \lambda u \quad \Rightarrow \quad U = [u_1,\, u_2,\, \ldots,\, u_k]هر سطر U برای پرتاب نقاط جاسازی شده بر روی ابرکره واحد، بر نرم اقلیدسی آن تقسیم میشود. این نرمالسازی، که توسط Ng، Jordan و Weiss معرفی شد، تفاوتهای مقیاس ناخواسته بین بردارهای ویژه را حذف میکند و تضمین میکند که مرحله k-means بعدی بر ساختار زاویهای جاسازی تمرکز کند نه بر اندازه.
فرمول
T_{ij} = U_{ij} \Big/ \left(\sum_{j'} U_{ij'}^2\right)^{1/2}خوشهبندی استاندارد k-means بر روی سطرهای ماتریس جاسازی نرمالشده T اعمال میشود. از آنجایی که جاسازی طیفی هندسه خوشه را از قبل باز کرده است، k-means حتی برای اشکال خوشه غیرمحدب نیز پارتیشنهای معنیداری پیدا میکند. سپس برچسبهای خوشه به نقاط داده اصلی نگاشت میشوند.
دامهای رایج
- انتخاب sigma بدون اعتبارسنجی متقابل اصولی یا خودتنظیمی؛ پهنای باندی که خیلی کوچک است یک گراف جدا شده ایجاد میکند، در حالی که پهنای باند خیلی بزرگ خوشههای متمایز را ادغام میکند.
- نادیده گرفتن مرحله نرمالسازی سطرهای ماتریس وابستگی قبل از k-means (مرحله نرمالسازی سطر Ng و همکاران برای پایداری ضروری است).
- نادیده گرفتن شکاف ویژه: استفاده از k ثابت بدون بررسی طیف مقادیر ویژه اغلب منجر به تقسیمبندی کم یا بیش از حد میشود.
- اعمال الگوریتم کامل بر روی مجموعه دادههایی با دهها هزار نقطه بدون تغییر به یک نوع تقریبی یا پراکنده.
- اشتباه گرفتن لاپلاسینهای نرمالنشده (L = D - W) و نرمالشده (L_sym, L_rw) که میتواند تخصیص خوشهها را به طور قابل توجهی تغییر دهد.
پرسشهای متداول
چگونه تعداد خوشهها k را انتخاب کنم؟
هیوریستیک شکاف ویژه راهنمایی استاندارد است: مقادیر ویژه لاپلاسین نرمالشده را به ترتیب صعودی محاسبه کنید و به دنبال بزرگترین شکاف بین مقادیر ویژه متوالی باشید. شاخصی که این شکاف در آن رخ میدهد، تعداد طبیعی خوشهها را نشان میدهد. هنگامی که شکاف ویژه مبهم است، رویکردهای مبتنی بر پایداری — اجرای الگوریتم برای چندین مقدار k و مقایسه تخصیص خوشهها در طول اغتشاشات — میتواند کمک کند.
چگونه پهنای باند هسته گوسی sigma را تنظیم کنم؟
یک هیوریستیک رایج، میانه فواصل دوتایی در مجموعه دادهها، یا یک طرح خودتنظیمی نزدیکترین همسایه (Zelnik-Manor & Perona, 2004) است که به هر نقطه یک پهنای باند محلی اختصاص میدهد. در عمل، sigma باید با بررسی اتصال گراف وابستگی حاصل، اعتبارسنجی شود: هر نقطه باید حداقل چند همسایه با وزن بالا داشته باشد و گراف نباید به اجزای جدا شده تقسیم شود.
چرا مرحله نرمالسازی سطر ضروری است؟
بردارهای ویژه لاپلاسین میتوانند از نظر مقیاس به طور قابل توجهی متفاوت باشند. بدون نرمالسازی هر سطر ماتریس جاسازی به طول واحد، مرحله k-means ممکن است تحت سلطه بردارهای ویژه با مقادیر بزرگ قرار گیرد و اجزای آموزنده اما با مقیاس کوچکتر را نادیده بگیرد. نرمالسازی سطر معرفی شده توسط Ng، Jordan و Weiss همه نقاط را بر روی کره واحد نگاشت میکند تا k-means به هندسه زاویهای جاسازی پاسخ دهد نه به اندازه.
آیا خوشهبندی طیفی میتواند مجموعه دادههای بسیار بزرگ را مدیریت کند؟
در شکل خام خود، نه، زیرا نیازمند حافظه O(n^2) و زمان تجزیه ویژه O(n^3) است. برای n بزرگ، راهحلهای استاندارد عبارتند از: ساخت یک گراف پراکنده k-نزدیکترین همسایه به جای یک ماتریس وابستگی کامل؛ استفاده از تقریب Nystrom برای تخمین بردارهای ویژه از یک زیرنمونه؛ یا اعمال SVD تصادفی. این روشهای تقریبی بیشتر دقت را با کسری از هزینه بازیابی میکنند.
روشهای مرتبط
منابع
Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002). On Spectral Clustering: Analysis and an Algorithm. Advances in Neural Information Processing Systems, 14, 849–856.
باز کردن مرجع انتشارکپی شد.von Luxburg, U. (2007). A Tutorial on Spectral Clustering. Statistics and Computing, 17, 395–416.
باز کردن مرجع DOIکپی شد.Shi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905.
باز کردن مرجع DOIکپی شد.