بخشی از مقاله
مروری بر معیار شباهت در خوشهبندی طیفی
چکیده
در سالهای اخیر خوشهبندی طیفی برای تجزیه و تحلیل دادهها، بسیار مورد توجه قرار گرفته است. زیرا میتواند بصورت کارآمد توسط ابزارهای استاندارد جبرخطی حل شود و مشکل بهینه محلی را تحمل نکند. با این وجود در خوشهبندی طیفی انتخاب پارامتر مقیاس مناسب در معیار شباهت هسته گوسی مشکل است. هدف از این مطالعه، مروری بر عملکرد الگوریتمهای موجود خوشهبندی طیفی با معیار شباهت گوناگون است. معایب و مزایای هر الگوریتم عنوان شده است تا در کارهای مختلف، الگوریتم مناسب با توجه به شرایط و نیازهای ممکن استفاده شود. در نهایت بر اساس نتایج آزمایشات، الگوریتم مناسب در خوشهبندی طیفی برای مجموعه دادههای مختلف عنوان شده است، تا الگوریتم مناسب برای کاربردهای مختلف استفاده شود.
در چند سال گذشته، الگوریتم امیدوارکنندهای برای مشکل گروه بندی با عنوان الگوریتم خوشهبندی طیفی بوجود آمده است .[6][5][4] این روش به علت کارایی بالا در خوشهبندی داده و سادگی در پیادهسازی توجه زیادی را به خود جلب کرده است.
الگوریتم خوشهبندی طیفی، دستهبندی داده را با استفاده از بردار مشخصه، از ماتریس شباهت نرمال شده برای دادههای بدست آمده انجام میدهد و با موفقیت برای محاسبات موازی [7]، طراحی [8] VLSI، تقسیم بندی تصویر [10][9][6] تفکیک گفتار [12][11] و غیره بکار برده شده است .[3] در مقابل الگوریتمهای سنتی، خوشهبندی طیفی میتواند بصورت کارآمدی توسط ابزارهای جبر خطی حل شود و مشکل بهینه محلی را نمیتواند تحمل کند. خوشهبندی طیفی میتواند به عنوان مسئله گراف پارتیشن مشاهده شود .[14][13]
کلمات کلیدی
خوشهبندی، خوشهبندی طیفی، معیار شباهت، تابع شباهت، خوشهبندی Fuzzy، تقسیم بندی تصویر.
.1 مقدمه
خوشهبندی یکی از گستردهترین تکنیکهای مورد استفاده برای تجزیه و تحلیل داده و تصمیمگیری در اکثر برنامه-های کاربردی میباشد .[1] خوشهبندی، تکنیک خوشهبندی بدون نظارت است و بطور گسترده در تحلیل داده از قبیل داده کاوی، تشخیص الگو و پردازش تصویر استفاده میشود. در چند دهه گذشته، بیشتر الگوریتمهای خوشهبندی توسعه یافتهاند [2] که بطور عمده شامل سلسله مراتب (از قبیل لینک تکی، لینک کامل و غیره) هستند، و تقسیم بندی خوشهبندی (از قبیل K-means، Fuzzy c-means، Gaussian M ixture و تخمین چگالی و غیره) هستند .[3]
خوشهبندی طیفی از دو مرحله تشکیل شده است: (1) ساخت ماتریس یا گراف وابستگی با یک نوع معیار شباهت؛ (2) یافتن دستهبندی خوب از گراف. پیشرفت قابل ملاحظهای به آدرس دوم ایجاد شده است [16][15][5][4]، در حالیکه در مطالعات گذشته کار کمی انجام شده است .[17][16]
متاسفانه به دلیل محدودیت ماتریس شباهت که معمولا توسط تابع هسته گوسی بر اساس فاصله اقلیدوسی در فضای ورودی ایجاد شده است، در اینجا هنوز بعضی چالشهای باز در خوشهبندی طیفی وجود دارند، ابتدا الگوریتم خوشهبندی نیاز به تنظیم پارامتر مقیاس مناسب در اندازه گیری شباهت هسته گوسی برای ایجاد ماتریس شباهت دارد، و نتایج بدست آمده ممکن است در اثر برخی پارامترهای مقیاس ناپایدار باشد. ثانیا، هنگامی که برای تقسیم بندی تصویر بکار برده میشود، الگوریتم خوشهبندی طیفی نیاز به اتخاذ استراتژی پراکنده مناسب برای ذخیره ماتریس شباهت S دارد که Sij، دو به دو شباهت بین پیکسلهای i و j است .[3]
اولین کار ایجاد ماتریس وابستگی مناسب است، که تا حد زیادی عهده دار عملکرد الگوریتم خوشهبندی طیفی را نشان می-دهد .[18 ] بیشتر روشهای خوشهبندی طیفی [6][5] تابع هسته گوسی را به عنوان تابع شباهت پذیرفتهاند، از اینرو از آن برای
1
محاسبه ساده و نتایج آن در ماتریس شباهت معین مثبت که ساده کننده تحلیل مقادیر مشخصه است استفاده میشود ..[6] با اینحال، در بررسی شرایط پیچیده، به عنوان مثال با مجموعه داده چند مقیاسی مشکلاتی دارد. علاوه بر این، پارامتر مقیاسگذاری بصورت دستی تعیین میشود. بطور کلی پیدا کردن یک مقدار بهینه برای پارامتر غیر بدیهی است. M anor و همکاران پیشنهاد به استفاده از یک پارامتر مقیاس محلی برای هر نقطه داده به جای یک ثابت سراسری را میدهند .[16] با اینحال، این فاصله محلی از شباهت مطلع است، که هنوز کمک کوچکی به مشخص کردن خصوصیات دستههای واقعی و ناموفق روی مجموعه دادههای واقعی نکرده است .[19] شباهت استفاده شده در خوشهبندی مبتنی بر مسیر بر ارتباط نقاط داده از طریق واسط عناصر به جای شباهت متقابل تاکید دارد. در حالیکه به نظر میرسد برای تاثیر روی بعضی وظایف خوشهبندی، می-خواهیم نشان دهیم که عملکرد آن روی بعضی مجموعه دادههای
واقعی خیلی خوب نیست .[2]
همانند فرض قبلی از سازگاری، که اغلب در آموزش نیمه نظارت شده استفاده شده است [20]، یک معیار شباهت خوب برای خوشهبندی باید نگهداشته شود، در زیر دو فرض از پایداری آورده شده است: (1) پایداری محلی: نقاط مجاور در فضا باید شباهت بالا داشته باشند؛ (2) پایداری سراسری: نقاط در دسته-های یکسان باید شباهت بالا داشته باشند. بر اساس این فرضیات، مطلوب است که با فاصله اقلیدوسی یکسان، دو نقطه در دسته یکسان باید شباهت بالایی نسبت به دو نقطه در دستههای متفاوت داشته باشند، این فرض دستهبندی است. هیچ یک از این دو تابع هسته گوسی سنتی با شباهت اندازهگیری شده محلی در ارضا فرض خوشهبندی نقیض نیستند .[16]
با این معیار شباهت، نقاط فاصله اقلیدوسی کوچک در دستههای متفاوت، اغلب گراف الگوریتم دستهبندی در مرحله دوم گیج کننده است، و منجر به نتایج ضعیف خوشهبندی می-شود. باید توجه داشت که دو نقطه داده به سوی دستههای یکسان میروند نه تنها به این دلیل که در فضا بهم نزدیک هستند، در بیشتر موارد به این دلیل است که آنها در ناحیه چگالی بالای یکسان هستند .[2]
.2 روشهای خوشهبندی طیفی موجود
در این مشکلات، هدف ارائه یک خانواده از الگوریتمهای خوشهبندی طیفی است .[3] یک معیار که همسایه نزدیک عمومی (CNN) نامیده میشود پیشنهاد شده است که چگالی
محلی بین دو نقطه داده را منعکس میکند. معیار CNN برای اندازهگیری برای درک اثر بهم چسبیدگی استفاده شده است. با این فاکتور اندازهگیری، شباهت جدید قابل تطبیق به چگالی محلی و ارضای فرض دستهبندی است. که آن از تقویت شباهت درون دسته اثر دارد، ایجاد ماتریس وابستگی بطور آشکار قطر را مسدود میکند. هر دو نتایج تجربی روی مجموعه داده ترکیبی و مجموعه دادههای واقعی نشان میدهند که خوشهبندی طیفی با شباهت تطبیقی چگالی محلی (SC-DA) نسبت به خوشهبندی سنتی (SC)، الگوریتم خوشهبندی مبتنی بر مسیر (SC-PB) و خوشهبندی خود تنظیم با پارامتر مقیاس محلی (SC-ST) عملکرد بهتری دارد. علاوه بر این، الگوریتم FSSC حساسیت
کمتری به پارامتر دارد، که بکار بردن آن را آسانتر میکند
.[16]
Zelnik-manor و p erona الگوریتم خوشهبندی خود تنظیم (SSC) که پارامتر مقیاس محلی را برای هر نقطه داده برای حل کردن چالش حساس از پارامتر مقیاس محاسبه میکند را پیشنهاد دادهاند .[21] محاسبه پارامتر مقیاس محلی میتواند مطالعه آمار محلی از همسایگی هر نقطه را انجام دهد. Chang و Yeung الگوریتم خوشهبندی طیفی مبتنی بر مسیر تنومند را با استفاده از M تخمین آمار در معیار شباهت مبتنی بر مسیر تنومند توسعه دادهاند .[22] درست برای حل محاسبات و مشکلات حافظه، چندین روش [23] برای بدست آوردن ماتریس شباهت پراکنده، از قبیل ε همسایگی و استراتژی پراکنده K نزدیکترین همسایه استفاده شده است. علاوه بر این Fowlkesetal راه حل تقریبی از جزءبندی طیفی بر اساس توسعه Ny strom برای اجتناب از کل محاسبات ماتریس شباهت ارائه دادهاند .[24] این روش با موفقیت برای تقسیم بندی تصویر و فیلم بکار برده شده است.[3]
Hegan و Kahng روشهای طیفی با نسبت برش تابع هدف برای پارتیشن بندی لیستهای شبکه مدار در طراحی VLSI پیشنهاد دادهاند. آنها نشان دادند که کوچکترین مقدار مشخصه یک ماتریس بدست آمده از لیست شبکه معین بطور قابل اثبات یک تقریب خوبی از نسبت مطلوب هزینه برش پارتیشن میدهد. در برش نسبت، اگر چه اندازه زیرمجموعه گراف توسط تعداد رئوس شماره شده است، که لزوماً به شباهت درون دسته مربوط نیست. برای حل این مشکل Shi و M alik معیار برش نرمال شده را پیشنهاد دادهاند که میتواند بصورت کارآمد هر دو تفاوت کل بین دستههای مختلف را بخوبی شباهت بین دستهها اندازهگیری کنند .[6] آنها روش خود را برای تقسیمبندی
تصاویر ایستا و توالیهای حرکت استفاده کردند. نتایج تجربی دلگرم کننده هستند.
M elia و Shi خوشهبندی طیفی را از مشاهده گامزنی-های تصادفی روی گراف شباهت توضیح دادهاند .[25] همچنین آنها ثابت کردند که روش برش نرمال شده بطور طبیعی از چارچوب و ارائه الگوریتم N برش (Ncut) اصلاح شده ناشی می-شود. در نهایت مشخصه موارد هنگامی که الگوریتم برش نرمال شده به درستی انجام میشود ارائه شده است. همچنین نویسندگان مشابه روش اصولی برای آموزش تابع شباهت چنانچه ترکیب ویژگیها برای تقسیم بندی تصویر باشد [26] را ارائه کردهاند. پس از آن، M elia، k روش برش نرمال شده وابسته به قسمتهای یگ گراف را تعریف کرد و بر اساس اصل موضوع چند برش که در آن میتوانیم همه k دسته را در یک گراف تک گذره پیدا کنیم را ارائه داده است .[27]
علاوه بر این، Ng و همکاران الگوریتم خوشهبندی طیفی دیگری با استفاده از ماتریس تئوری انحراف ارائه دادند که بردارهای مشخصه را در مقایسه روش کمی متفاوت با روش چند برش انتخاب میکنند .[28] آنها نتایج تجربی خوبی را روی تعداد مسائل دستهبندی چالش برانگیز نشان دادند. یک ماتریس با استفاده از شباهت بین اشیاء ساخته شده است و بعنوان ماتریس مجاورت از نمایش گراف استفاده شده است .[29] قلب این روش مدل مارکوف است که گراف روی این ساخته شده است. این چارچوب میتواند بصورت کارآمد برای پیدا کردن بخشهای مجزا در مجموعه داده استفاده شود.
کلید برای خوشهبندی طیفی انتخاب معیار فاصله است که با ملاحظه ساختار اصلی از نقاط داده یکنواخت خواهد شد. داده در گروههای یکسان باید شباهت بالا و به دنبال آن پایداری فاصله داشته باشد. در حالیکه برخورد با مجموعه داده پیچیده، اگرچه بر اساس شباهت به سادگی روی فاصله اقلیدوسی نمی-تواند توزیع داده را منعکس کند و به نوبه خود عملکرد ضعیف خوشهبندی طیفی را نتیجه میدهد. در این مقاله، یک معیار شباهت حساس چگالی پیشنهاد شده است، که فواصل میتوانند در نواحی با چگالی بالا تراکم داشته باشند در حالیکه در نواحی با چگالی کم گسترده شدهاند. در نهایت، یک الگوریتم خوشهبندی حساس چگالی با تعیین تعداد دسته بصورت اتوماتیک ارائه شده است و میتواند عملکرد بهتری را بدست آورد در حالیکه دسته برای بیشتر مجموعه دادههای واقعی است .[1]
3
در خوشهبندی طیفی با معیار شباهت Fuzzy هدف توسعه معیار شباهت پایدار است [3]، که معیار شباهت Fuzzy را برای الگوریتم خوشهبندی طیفی پیشنهاد داده است. معیار شباهت جدید نمونههای اولیه دسته را مورد استفاده قرار داده است و ماتریس جزءبندی بدست آمده توسط الگوریتم خوشهبندی (FCM ) Fuzzy c-means را برای ایجاد ارتباط میان نقاط داده مورد استفاده قرار داده است .[30] علاوه بر این، استراتژی پراکنده K نزدیکترین همسایه را بر طبق ویژگیهای پیکسل بافت برای ایجاد ماتریس شباهت Fuzzy پذیرفته است و روش خود را برای تقسیم بندی تصویر بافت بکار گرفته است .[3]
.3 مقایسه الگوریتمهای خوشهبندی طیفی
آزمایشات گسترده روی ارزیابی تاثیر الگوریتم خوشهبندی طیفی روی مجموعه دادههای ترکیبی، به خوبی مجموعه داده-های واقعی هدایت شده است .[1] برای مقایسه، دو الگوریتم خوشهبندی طیفی دیگر به ترتیب با معکوس فاصله اقلیدوسی و تابع هسته گوسی به عنوان تابع شباهتشان پیاده سازی شده است. نتایج نشان میدهد که الگوریتم موجود ممکن است معقولانه بخوبی روی بیشتر مجموعه دادهها انجام شود. سه الگوریتم طیفی با توابع شباهت مختلف روی 4 مجموعه داده ترکیبی دو بعدی بکار برده شده است (شکل (1، بعضی هم به عنوان مسئله خوشهبندی چالش برانگیز مطرح شده است. نتایج اعمال خوشهبندی طیفی با تابع شباهت بر اساس فاصله اقلیدوسی (E-SC) نشان میدهد که تابع شباهت بر اساس فاصله اقلیدوسی نمیتواند به توصیف متعدد پیچیده تطبیق داده شود.
نتایج اعمال خوشهبندی طیفی با تابع شباهت بر اساس هسته گوسی (G-SC) نشان میدهد که چنین الگوریتمی نمی-تواند دستهها را به درستی پیدا کند، به این دلیل که تابع شباهت گوسی برای مشکل چند مقیاسی تطبیق داده نشده است. نتایج اعمال خوشهبندی طیفی با تابع شباهت تعریفی (D-SC) نشان میدهد که این الگوریتم میتواند دستههای صحیح را روی تمام مجموعه دادهها بدست آورد و بصورت موثر با دریافت یک محدوده بزرگ از مقادیر برای انجام شود. بدیهی است که با استفـاده از متـریک فاصلـه حسـاس چگــالی عملکـرد الگـوریتم موجود میتواند بیشتر فراهم شود و کیفیت خوشهبندی بالاتری روی مجموعه دادههای پیچیده بدست آورد.
