مقاله "خوشه بندی طیفی نیمه نظارتی برای طبقه بندی"

این مقاله توسط عارف محمود و همکارش در سال 2014 تهیه شده است. در این مقاله آنها یک الگوریتم طبقه بندی از طریق خوشه بندی CVC[1] را معرفی می کنند که در آن از شیوه های موجود در خوشه بندی برای استفاده در مسائل طبقه بندی استفاده شده و کارآمدی آن را نشان می دهند. در CVC، داده های آموزش و تست به صورت کلاسی است و از توزیع خوشه های کلاس برای یافتن برچسب داده های آزمون استفاده می شود. برای تعیین تعداد خوشه کافی از یک الگوریتم سلسله مراتبی نیمه نظارت شدهSHC[2]  استفاده شده است. خوشه ها با استفاده از سلسله مراتبی از NCut دو طرفه به دست می آیند. برای این منظور، الگوریتم محاسبات بردار مستقیم فیدلر پیشنهاد شده است. برش گراف براساس ساختار داده هاست و برچسب ها را در نظر نمی گیرد. از برچسب ها فقط برای تعریف معیار توقف برای برش گراف استفاده می شود. برای تست سیستم از پنج مجموعه داده های استاندارد استفاده شده است.

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

با وجود پیشرفت های قابل توجه، خوشه بندی و طبقه بندی دو ساختار متفاوت هستند. شکل ذیل مقادیر خوشه بندی را با الگوریتم  Kmeans، SCC[3] و SKMS[4] را نشان می دهد.

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

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

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

قدم سوم استفاده از الگوریتم DFVC[5]  است که بر مبنای روش تکرار معکوس می باشد. خوشه بندی طیفی سلسله مراتبی قبلا به عنوان یک گزینه قابل قبول محسوب نمی شد، زیرا همه بردارها نیاز به محاسبه داشتند، در حالی که تنها دومین معیار (بردار فیدلر ) مهم می باشد.
الگوریتم پیشنهاد شده DFVC این مشکل را حل می کند. برای طبقه بندی الگوریتم های پیشنهادی را بر تصاویر اعمال می کنیم که در آن کلاس های آموزشی و کلاس آزمون از مجموعه ای از تصاویر تشکیل شده است. الگوریتم های پیشنهادی را می توان به طور مستقیم بر روی  داده های خام مورد استفاده قرار داد. آنها برای خوشه بندی از فضای  Grassmannian استفاده کرده تا پیچیدگی محاسباتی را کاهش دهند. با استفاده از چندمنظورهای گراسمن،  می توانیم مجموعه ای از طبقه بندی های طیفی را ایجاد کنیم که هر کدام براساس ابعاد مختلف چند جمله ای است. یک مرور کلی از رویکرد این مقاله در شکل ذیل نشان داده شده است.

همانمگونه که در شکل ملاحظه می شود تمام ورودی های ویژه محاسبه شده  و داده ها را به دو یا چند دسته تقسیم کرده و از یک الگوریتم محاسبات بردار تصادفی فیدلر DFVC  به منظور اجتناب از محاسبه همه ورودی های ویژه استفاده می شود.

آزمایشات بر روی مجموعه تصویر صورت استاندارد Honda، CMU Mobo ، مشاهیر یوتیوب  و دسته بندی شی  ETH 80 و مجموعه تصاویر دست کمبریج  انجام شده است. تکنیک پیشنهادی دقت بیشتری در تمام مجموعه داده ها نسبت به سایر روش ها را دارا می باشد و در بهتررین حالت 11.03 درصد دقت بیشتر را دارد.

لینک دانلود مقاله

---

[1] Classification Via Clustering

[2] Semi-supervised Hierarchical Clustering

[3] Sparse Subspace Clustering

[4] Semi-supervised Kernel Mean Shift

[5] Direct Fiedler Vector Computation