1- مقدمه[1]

در دهه‌های اخیر، الگوریتم‌های خوشه‌بندی طیفی^[1] به ‌عنوان ابزارهای قدرتمند برای شناسایی ساختارهای پیچیده و غیرخطی در داده‌ها مورد توجه قرار گرفته‌اند. این الگوریتم‌ها با استفاده از ماتریس لاپلاسین گراف و تجزیۀ مقادیر ویژه، داده‌ها را به فضای ویژگی‌های جدیدی منتقل می‌کنند که در آن، خوشه‌ها واضح‌تر قابل تفکیک هستند. با این حال، محاسبۀ مقادیر ویژه برای ماتریس‌های بزرگ ممکن است از نظر محاسباتی پرهزینه باشد.

یک الگوریتم ساده برای خوشه‌بندی طیفی ارائه شده است که از بردارهای ویژۀ ماتریس لاپلاسین نرمال‌شدۀ گراف شباهت داده‌ها استفاده می‌کند ]1[. این الگوریتم با بهره‌گیری از نظریۀ اختلال ماتریس، شرایطی را تحلیل می‌کند که تحت آن می‌تواند خوشه‌بندی مؤثری انجام دهد. الگوریتم خوشه‌بندی طیفی، با وجود توانایی در شناسایی ساختارهای پیچیده در داده‌ها، دارای معایبی است. یکی از مهم‌ترین چالش‌ها پیچیدگی محاسباتی زیاد است. همچنین، خوشه‌بندی طیفی ممکن است در شناسایی خوشه‌هایی با اندازه‌ها یا چگالی‌های متفاوت دچار مشکل شود و به حضور نویز و داده‌های پرت حساس باشد که ممکن است بر کیفیت نتایج تأثیر منفی بگذارد. در نهایت، تعیین تعداد مناسب خوشه‌ها برای خوشه‌بندی طیفی دشوار است و نیاز به دانش قبلی یا آزمایش‌های متعدد دارد.

الگوریتم k میانگین^[2] استاندارد توسط جیمز مک‌کوئین در مقاله‌ای با عنوان «برخی روش‌ها برای طبقه‌بندی و تحلیل مشاهدات چندمتغیره» معرفی شد که در سال ۱۹۶۷ در مجموعه مقالات پنجمین سمپوزیوم برکلی دربارۀ آمار و احتمال ریاضی منتشر شد ]2[. در این روش، مک‌کوئین الگوریتمی را برای تقسیم داده‌ها به k خوشه ارائه داد که هدف آن کمینه‌سازی واریانس درون‌خوشه‌ای است. الگوریتم با انتخاب تصادفی مراکز اولیۀ خوشه‌ها آغاز می‌شود و سپس، به ‌صورت تکراری، هر داده به نزدیک‌ترین مرکز خوشه اختصاص می‌یابد و مراکز خوشه‌ها بر اساس میانگین داده‌های اختصاص‌یافته به آن‌ها به‌روز می‌شوند. این فرایند تا زمانی ادامه می‌یابد که مراکز خوشه‌ها تغییر نکنند یا تغییرات آنها به حداقل برسد. مک‌کوئین در این مقاله ویژگی‌های آماری الگوریتم و کاربردهای آن در تحلیل داده‌های چندمتغیره را بررسی کرد.

خوشه‌بندی k میانگین هستۀ پراکنده چالش‌های خوشه‌بندی داده‌های پیچیده و غیرخطی را بررسی می‌کند. روش‌های سنتی مانند k میانگین در شناسایی ساختارهای غیرخطی محدودیت دارند؛ بنابراین، تکنیک‌های جایگزین مانند k میانگین هسته و خوشه‌بندی طیفی توسعه یافته‌اند. با این حال، حضور متغیرهای نامربوط در داده‌ها می‌تواند عملکرد این الگوریتم‌ها را کاهش دهد ]3[. برای مقابله با این مشکل، روش‌های انتخاب متغیر مانند فیلتر، پوششی و جاسازی شده معرفی شده‌اند. الگوریتم k میانگین هستۀ یک روش انتخاب متغیر جاسازی‌شده با استفاده از فضای ضرب تانسوری و هستۀ تحلیل واریانس عمومی برای خوشه‌بندی غیرخطی است. این رویکرد با استفاده از فضای ضرب تانسوری، تعاملات پیچیدۀ بین ویژگی‌ها را مدل‌سازی می‌کند و با اعمال هستۀ تحلیل واریانس، ساختارهای غیرخطی در داده‌ها را بهتر شناسایی می‌کند ]3[.

الگوریتم خوشه­بندی بر اساس آمار هاپکینز و k میانگین، محدودیت‌های الگوریتم سنتی k میانگین در خوشه‌بندی داده‌هایی با ساختارهای نامنظم را بررسی می‌کند و با استفاده از آمار هوپکینز^[3] و مفهوم جفت نزدیک‌ترین همسایه طراحی شده ­است. در مرحلۀ اول، داده‌ها به زیرمجموعه‌های کروی و نسبتاً یکنواخت تقسیم می‌شوند. سپس، با تعیین روابط مجاورت بین این زیرمجموعه­ها، زیرمجموعه‌های مجاور و به‌هم‌پیوسته تا رسیدن به تعداد خوشه‌های مدنظر k ادغام می‌شوند. آمار هوپکینز در فرایند تقسیم‌بندی داده‌ها برای ارزیابی تمایل به خوشه‌بندی استفاده می‌شود، در حالی که مفهوم جفت نزدیک‌ترین همسایه در فرایند ادغام زیرمجموعه‌ها به کار می‌رود ]4[.

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

ساختار این مقاله به شرح زیر سازمان‌دهی شده است. بخش 2 مروری بر الگوریتم‌های خوشه‌بندی مبتنی بر چگالی و هندسه دارد و نقاط قوت و محدودیت‌های آنها را برجسته می‌کند. در بخش 3، الگوریتم پیشنهادی را معرفی می‌کنیم که هستۀ آپولونیوس را با ماتریس لاپلاسین و k میانگین برای خوشه­بندی داده­ها ادغام می‌کند. بخش 4 نتایج تجربی را ارائه و مورد بحث قرار می‌دهد و توانایی بهبودیافتۀ روش پیشنهادی را در شناسایی ساختارهای پیچیده و غیرخطی در مقایسه با تکنیک‌های خوشه‌بندی سنتی و پیشرفته نشان می‌دهد. در نهایت، بخش 5 نتیجه‌گیری مقاله را نشان می‌دهد.

2- کارهای مرتبط

الگوریتم سادۀ چندفیلتری مبتنی بر k میانگین با استفاده از معیار هم‌ترازی هسته در محیط بدون نظارت، ترکیب فیلتر‌ها برای خوشه‌بندی را بهینه‌سازی می‌کند. با فرموله‌کردن مسئله به صورت بهینه‌سازی نرم، الگوریتم قادر به حل مؤثر آن با استفاده از روش نزول گرادیان کاهش‌یافته است ]5[.

روش یادگیری ساختار متقابل برای خوشه­بندی‌های چندگانه[4] با یادگیری هم‌زمان ساختارهای زوجی و خوشه‌ای، ماتریس تقسیم‌بندی برای خوشه‌بندی را بهبود می‌دهد. با استفاده از گراف شباهت تبعیض‌آمیز در فضای هسته و هم‌ترازی با تقسیم‌بندی‌های پایه، ساختارهای مختلف به صورت یکپارچه یاد گرفته می‌شوند ]6[.  الگوریتم ابتدا یک گراف شباهت تبعیض‌آمیز در فضای هسته می‌سازد که با استفاده از هسته‌های پایۀ مختلف، شباهت‌های بین نمونه‌ها را به صورت دقیق‌تر مدل می‌کند. سپس، با هم‌ترازی این گراف با تقسیم‌بندی‌های پایه، ساختارهای مختلف به صورت یکپارچه یاد گرفته می‌شوند. یکی از ویژگی‌های این الگوریتم استفاده از منظم‌سازی لاپلاسین[5] است که به حفظ ساختار زوجی در ماتریس تقسیم‌بندی کمک می‌کند و در عین حال، اطلاعات ساختار خوشه­ای را در گراف شباهت تزریق می‌کند. این روش به ‌ویژه در کاربردهایی مانند تحلیل داده‌های چندمنظوره، پردازش تصاویر و شناسایی الگوهای پیچیده در داده‌های بزرگ، پتانسیل زیادی دارد.

در روش جدید مبتنی بر تابع آپولونیوس و خوشه‌بندی قلۀ چگالی، کرنل جدید برای ماشین بردار پشتیبان [6] معرفی شده است که بر پایۀ تابع آپولونیوس است. این رویکرد با هدف بهبود عملکرد طبقه‌بندی در داده‌های پیچیده و غیرخطی ارائه شده است ]7[. در این رویکرد، تابع آپولونیوس برای مدل‌سازی دقیق‌تر روابط هندسی بین نقاط داده استفاده می‌شود، در حالی که خوشه‌بندی قله‌های چگالی به شناسایی ساختارهای محلی و نقاط مرکزی در داده‌ها کمک می‌کند. این ترکیب باعث می‌شود کرنل آپولونیوس به صورت تطبیقی با ساختارهای مختلف داده‌ها سازگار شود و عملکردی بهتر در طبقه‌بندی داده‌های پیچیده نسبت به کرنل‌های سنتی مانند کرنل گاوسی ارائه دهد. در روش پیشنهادی، برای خوشه­بندی از این کرنل برای افزایش دقت استقاده شده است.

 الگوریتم خوشه­بندی طیفی بر اساس عملکرد کرنل گاوسی بهبودیافته و جست‌وجوی آنتن سوسک با ضریب میرایی با بهبود تابع کرنل گاوسی و استفاده از الگوریتم جست‌وجوی شاخک سوسک با عامل میرایی، مشکلات مربوط به پارامترهای مقیاس و پایداری نتایج در خوشه‌بندی طیفی را حل می‌کند ]8[. در این الگوریتم، برای ساخت ماتریس شباهت، از یک تابع کرنل گاوسی بهبودیافته بهره‌برداری می‌شود که با استفاده از اطلاعات فاصلۀ برخی از نزدیک‌ترین همسایگان، به ‌طور تطبیقی پارامتر مقیاس را انتخاب می‌کند. این رویکرد به حل مشکل انتخاب پارامتر مقیاس در کرنل گاوسی کمک می‌کند. در مرحلۀ خوشه‌بندی، از الگوریتم جست‌وجوی شاخک سوسک با ضریب میرایی استفاده می‌شود تا بر مشکل ناپایداری نتایج خوشه‌بندی غلبه کند.

خوشه‌بندی طیفی به نام SC-NR [7] روشی برای بهبود ماتریس شباهت است که از ترکیب فاصلۀ اقلیدسی وزن‌دار با تابع کرنل گاوسی استفاده می‌کند. وزن‌ها بر اساس ترتیب همسایگان نزدیک تنظیم می‌شوند تا روابط واقعی بین نقاط بهتر بازتاب یابند. با این حال، تابع کرنل گاوسی با استفاده از فاصلۀ اقلیدسی و یک پارامتر ثابت سیگما، شباهت بین نقاط داده را اندازه‌گیری می‌کند. استفاده از یک سیگما ثابت می‌تواند به نتایج نادرست در خوشه‌بندی منجر شود، زیرا فاصلۀ اقلیدسی به‌تنهایی قادر به بازتاب ساختار واقعی داده‌ها نیست. برای مثال، ممکن است نقاطی از خوشه‌های مختلف دارای فاصلۀ اقلیدسی یکسانی باشند که در نتیجه، تابع کرنل گاوسی شباهتی یکسان برای آنها محاسبه می‌کند و این امر ممکن است به خوشه‌بندی نادرست منجر شود ]9[.

در الگوریتم «K میانگین استاندارد هستۀ پراکنده برای انتخاب ویژگی در خوشه‌بندی غیرخطی»[8] ]3[. نویسندگان چارچوبی برای خوشه‌بندی غیرخطی همراه با انتخاب متغیر پراکنده ارائه کرده‌اند که بر پایۀ گسترش الگوریتم K میانگین استاندارد کرنل با استفاده از کرنل ANOVA بنا شده است. این روش با تجزیۀ کرنل به مؤلفه­های مربوط به اثرات اصلی و تعامل متغیرها و اعمال قیدهای ترکیبی بر ضرایب وزنی، امکان حذف ویژگی‌های بی‌اهمیت را فراهم می‌کند و هم‌زمان، ساختارهای غیرخطی پیچیده در داده را مدل می‌سازد. الگوریتم SKKM از بهینه‌سازی تناوبی برای به‌روزرسانی خوشه­ها و وزن­های ویژگی استفاده می‌کند. این رویکرد یکی از نخستین تلاش‌ها برای تلفیق یادگیری غیرخطی و انتخاب متغیر در چارچوبی یکپارچه است.

3- روش پیشنهادی

مرحلۀ اول: ساخت گراف شباهت با استفاده از هستۀ آپولونیوس

در این مرحله، ابتدا داده‌ها را نرمال‌سازی می‌کنیم تا مقیاس ویژگی‌ها یکسان شود. سپس، با ضرب ویژگی‌ها در وزن‌های مشخص‌شده، اهمیت هر ویژگی را تنظیم می‌کنیم. در ادامه، یک گراف  kنزدیک‌ترین همسایگان با استفاده از فاصلۀ اقلیدسی بین نقاط ساخته می‌شود. برای محاسبۀ شباهت بین نقاط ]10، 11[. از هستۀ آپولونیوس که بر اساس ساخت دایرۀ آپولونیوس است ]12، 13[ استفاده می‌کنیم که به صورت فرمول (1) تعریف می‌شود:

که در آن، اپسیلون یک مقدار ثابت کوچک است که از تقسیم بر صفر جلوگیری می‌کند (پارامتر اپسیلون نقش فیلتر نرم‌کننده[9] را دارد تا از تقسیم بر صفر جلوگیری و حساسیت شباهت به فواصل خیلی کوچک را کنترل کند). شباهت محاسبه‌شده با ماتریس k نزدیک‌ترین همسایگان ضرب می‌شود تا فقط اتصالات همسایگان نزدیک حفظ شوند.

مرحلۀ دوم: ساخت ماتریس لاپلاسین گراف

در این مرحله، ماتریس درجه را محاسبه می‌کنیم که هر قطر آن نشان‌دهندۀ مجموع وزن‌های یال‌های متصل به گره مربوط است. سپس، ماتریس لاپلاسین گراف را با استفاده از فرمول (2) محاسبه می‌کنیم:

که در آن، D ماتریس درجه و W ماتریس شباهت است. این ماتریس نمایانگر ساختار گراف و روابط بین نقاط داده است.

مرحلۀ سوم: تجزیۀ طیفی و کاهش ابعاد

در این مرحله، تجزیۀ مقادیر ویژۀ ماتریس لاپلاسین انجام می‌شود تا مقادیر ویژه و بردارهای ویژۀ آن به ‌دست آیند. سپس، بردارهای ویژۀ متناظر با کوچک‌ترین مقادیر ویژه را انتخاب می‌کنیم و آ‌نها را به صورت ماتریسی با ابعاد n×k (که در آن k تعداد خوشه‌ها و n تعداد نمونه­های ذخیره‌شده است) نشان می­دهیم. این ماتریس ویژگی‌هایی جدید را برای داده‌ها فراهم می‌کند که در فضای کاهش­‌یافته قرار دارند و خوشه‌ها در آن واضح‌تر قابل تفکیک هستند.

مرحلۀ چهارم: خوشه‌بندی با استفاده از k میانگین

در این مرحله، الگوریتم k میانگین را بر روی ماتریس ویژگی‌های به‌دست‌آمده از مرحلۀ قبلی اعمال می‌کنیم. در این الگوریتم، ابتدا مراکز اولیۀ خوشه‌ها به صورت تصادفی انتخاب می‌شوند. سپس، هر داده به نزدیک‌ترین مرکز خوشه اختصاص می‌یابد و مراکز خوشه‌ها بر اساس میانگین داده‌های اختصاص‌یافته به آنها به‌روز می‌شوند. این فرایند تا زمانی ادامه می‌یابد که مراکز خوشه‌ها تغییر نکنند یا تغییرات آنها به حداقل برسد ]2 .[

4-  نتایج

ارزیابی عملکرد روش پیشنهادی

برای ارزیابی کیفیت خوشه­بندی از شاخص­هایی مختلف همچونARI ، Accuracy (دقت) و NMI استفاده می‌کنیم. شاخص ARI میزان شباهت بین خوشه‌بندی به‌دست‌آمده و برچسب‌های واقعی داده‌ها را اندازه‌گیری می‌کند. مقدار ARI بین 1- و 1 متغیر است که مقدار 1 نشان‌دهندۀ تطابق کامل بین خوشه‌بندی و برچسب‌های واقعی است. معیار اطلاعات متقابل نرمال‌شده NMI بر پایۀ نظریۀ اطلاعات است و میزان اشتراک اطلاعات بین برچسب‌های واقعی و برچسب‌های پیش‌بینی‌شده توسط الگوریتم خوشه‌بندی را اندازه‌گیری می‌کند. NMI بین 0 و 1 مقدار می‌گیرد؛ مقدار 1 نشان‌دهندۀ تطابق کامل بین خوشه‌بندی و برچسب‌های واقعی است، در حالی که مقدار 0 نشان‌دهندۀ عدم تطابق کامل است. یکی از ویژگی‌های مهم NMI این است که مستقل از تعداد خوشه‌ها و برچسب‌ها عمل می‌کند و به همین دلیل، برای مقایسۀ الگوریتم­های مختلف خوشه‌بندی مناسب است.

معیار دقت^[10] خوشه‌بندی بر اساس فرمول (3)، نسبت تعداد نمونه‌هایی را که به‌درستی خوشه‌بندی شده­اند به کل نمونه‌ها محاسبه می‌کند (برای محاسبۀ معنادارِ دقت در مسائل خوشه‌بندی لازم است ابتدا یک نگاشت یک‌به‌یک بین برچسب­های خوشه­ای و برچسب‌های واقعی کلاس پیدا شود). از آنجا که در خوشه‌بندی، برچسب‌های پیش‌بینی‌شده ممکن است با برچسب‌های واقعی از نظر نام‌گذاری متفاوت باشند، قبل از محاسبۀ دقت، معمولاً یک نگاشت بین برچسب‌های پیش‌بینی‌شده و واقعی انجام می‌شود تا بیشترین تطابق حاصل شود. دقت خوشه‌بندی نیز بین 0 و 1 مقدار می‌گیرد؛ مقدار 1 نشان‌دهندۀ تطابق کامل است.

بر اساس فرمول (3)،  نشان‌دهندۀ برچسب واقعی کلاس است و شمارۀ برچسب خوشه‌ای است که از فرایند خوشه‌بندی به ‌دست آمده است. تابع  یک تابع شاخص [11]است که در صورت برابری دو برچسب، مقدار 1 و در غیر این صورت، مقدار 0 می‌گیرد. بهترین نگاشت بین برچسب‌های خوشه و برچسب‌های واقعی کلاس با استفاده از الگوریتم Hungarian یا Munkres تعیین می‌شود تا بیشترین تطابق ممکن بین خوشه‌ها و کلاس‌های واقعی حاصل شود.

استفادۀ هم‌زمان از NMI و دقت می‌تواند دیدی جامع‌تر از عملکرد الگوریتم خوشه‌بندی ارائه دهد، زیرا هر یک از این معیارها جنبه­هایی متفاوت از کیفیت خوشه‌بندی را بررسی می‌کنند.

ارزیابی عملکرد الگوریتم پیشنهادی و سایر الگوریتم­ها با مجموعه‌داده‌های واقعی

مجموعه‌داده‌های واقعی در جدول (1)[12]، مانند Iris، Wine، Digits، Breast، Cancer، Diabetes و Olivetti Faces، به ‌طور گسترده‌ برای ارزیابی و آموزش الگوریتم‌های مختلف استفاده می‌شوند. مجموعه دادۀ Iris شامل 150 نمونه از سه گونۀ گل زنبق است که هر نمونه دارای 4 ویژگی است. مجموعه دادۀ Wine شامل 178 نمونه از سه نوع نوشیدنی با 13 ویژگی شیمیایی است. مجموعه دادۀ Digits شامل 1797 تصویر 8×8 از ارقام دست‌نویس 0 تا 9 است که هر تصویر به یک بردار 64بُعدی تبدیل شده است. مجموعه دادۀ Cancer شامل 569 نمونه با 30 ویژگی عددی برای تشخیص سرطان سینه است. مجموعه دادۀ Diabetes شامل 768 نمونه با 8 ویژگی برای پیش‌بینی ابتلا به دیابت است. مجموعه دادۀ Olivetti Faces شامل 400 تصویر چهره از 40 فرد مختلف است که هر تصویر به صورت یک بردار 4096بُعدی (64×64 پیکسل) نمایش داده می‌شود. این مجموعه‌داده‌ها به‌ عنوان معیارهای استاندارد در پژوهش‌های علمی شناخته می‌شوند و برای مسائل مختلف مانند طبقه‌بندی، خوشه‌بندی و کاهش ابعاد داده‌ها کاربرد دارند.

جدول (1): مجموعه‌داده‌های واقعی

جدول (2): ارزیابی الگوریتم پیشنهادی در مجموعه‌داده‌های واقعی

جدول (3): ارزیابی الگوریتم پیشنهادی، الگوریتم SKKM و k میانگین استاندارد در مجموعه‌داده­های واقعی

 جدول (2) نتایج عملکرد الگوریتم پیشنهادی مبتنی بر گراف آپولونیوسی را در چند مجموعه دادۀ واقعی به همراه پارامترهای بهینه و نوع لاپلاسیَن به‌کاررفته نشان می‌دهد. همان‌گونه که در ستون‌های NMI و دقت مشاهده می‌شود، الگوریتم پیشنهادی در بیشتر مجموعه‌داده‌ها نتایجی پایدار داشته و در مقایسه با روش‌های کلاسیک، توانسته است ساختارهای درونی داده‌ها را به شکلی دقیق‌تر شناسایی کند. در مجموعه‌دادۀ Iris، مقدار NMI برابر 460/0 و دقت برابر 687/0به ‌دست آمده است که با استفاده از لاپلاسیَن غیرنرمال‌شده (L) حاصل شده است. بررسی طیف ویژۀ لاپلاسیَن نشان داد شکاف قابل ملاحظه‌ای میان λ₃ و λ₄ وجود دارد که وجود سه خوشۀ متمایز را در این داده تأیید می‌کند. این یافته نشان می‌دهد الگوریتم پیشنهادی قادر است ساختار خوشه‌ای داده‌های کم‌بعد و نسبتاً منظم را به‌خوبی بازیابی کند. در مجموعه‌دادۀ Wine، نمایش مقادیر حاصل 0٫853=NMI و دقت 955/0 نشان‌دهندۀ عملکرد بسیار مطلوب الگوریتم در داده‌های با ویژگی‌های پیوسته و خوشه‌های هم‌پوشان است. استفاده از لاپلاسیَن نرمال‌شدۀ متقارن  موجب پایداری نتایج شده است، زیرا این نوع لاپلاسیَن توانسته اثر تفاوت در اندازۀ خوشه­ها را تعدیل کند. در مقابل، در مجموعه‌دادۀ Digits که دارای ساختار غیرخطی و چندخوشه‌ای است، الگوریتم با انتخاب لاپلاسیَن نرمال‌شدۀ تصادفی مقدار 892/0NMI= و دقت 892/0 را به ‌دست آورده است.

در مجموعه‌دادۀ Breast Cancer، الگوریتم پیشنهادی با 0٫645=NMI و دقت 935/0 توانسته است عملکردی پایدار ارائه دهد، هرچند به نویز حساس است. این داده نشان می‌دهد در حضور ویژگی‌های همبسته و نویزی، استفاده از لاپلاسیَن غیرنرمال‌شده می‌تواند خوشه‌بندی معناداری ایجاد کند. در مجموعه‌دادۀ Diabetes، مقدار NMI زیاد (793/0) در کنار دقت کمتر (379/0) مشاهده می‌شود که نشان می‌دهد الگوریتم توانسته است ساختارهای نسبی خوشه­ها را تشخیص دهد، اما به ‌دلیل هم‌پوشانی زیاد بین داده­ها، برچسب‌های نهایی دقت کمتری دارند. در اینجا، استفاده از لاپلاسیَن متقارن باعث بهبود پایداری نسبت به حالت غیرنرمال‌شده شده است. در نهایت، در مجموعه‌دادۀ Olivetti Faces که از تصاویر چهره تشکیل شده، مقادیر 0٫793=NMI و دقت 552/0 نشان‌دهندۀ توانایی الگوریتم در بازنمایی روابط چهره‌هاست. استفاده از لاپلاسیَن تصادفی و افزایش k تا 15 موجب بهبود پایداری تعبیه شده است.

به طور کلی، میانگین نتایج در تمام مجموعه‌داده­ها با NMI برابر 739/0±22/0 و دقت برابر 733/0±214/0 نشان می‌دهد الگوریتم پیشنهادی از نظر میانگین عملکرد و پایداری دارد. تحلیل پارامترها مشخص می‌کند بازۀ بهینه برای k حدود 10 تا 15 است. همچنین، نوع لاپلاسیَن باید با ساختار داده تطبیق یابد که برای داده‌های هم‌تراز و L ساده مناسب است. به ‌طور کلی، این نتایج اثبات می‌کنند ترکیب کرنل آپولونیوس با روش تعبیۀ طیفی می‌تواند یک چارچوب انعطاف‌پذیر و دقیق برای خوشه‌بندی داده‌های پیچیده فراهم کند.

جدول (3) عملکرد الگوریتم پیشنهادی را در مقایسه با روش‌های پایه شامل k میانگین استاندارد بر اساس معیارهای NMI و دقت و الگوریتم SKKM بر اساس ARI روی مجموعه‌داده‌های مختلف نشان می‌دهد. نتایج NMI و دقت k میانگین استاندارد با میانگین‌های نسبتاً کم (به ‌ترتیب 472/0 و 635/0) و انحراف معیارهای زیاد بیانگر این است که k میانگین استاندارد در برابر ساختارهای پیچیده و داده‌های با توزیع غیرخطی کارایی محدودی دارد. در مقابل، مقدار ARI الگوریتم پیشنهادی در چهار مجموعه‌دادۀ مشترک از جمله Iris، Wine، Digits و Breast Cancer میانگین 788/0±071/0 را نشان می‌دهد که بیانگر عملکرد باثبات و دقیق در بازیابی ساختار واقعی خوشه‌هاست. این مقدار اندکی بیشتر از الگوریتم SKKM با میانگین 783/0±061/0 است که نشان می‌دهد روش پیشنهادی نه فقط در بیشتر مجموعه‌داده‌ها عملکرد مشابه یا بهتر نسبت به SKKM دارد، بلکه توانایی استخراج ویژگی‌های ساختاری عمیق‌تری از داده‌ها را نیز ارائه می‌دهد. همچنین، نبود مقدار ARI برای مجموعه‌داده‌های Diabetes و Olivetti Faces به دلیل ابعاد یا ویژگی‌های خاص آنهاست که در این آزمایش‌ها لحاظ نشده‌اند. در مجموع، جدول (3) نشان می‌دهد الگوریتم پیشنهادی از نظر پایداری، دقت خوشه‌بندی و توانایی تفکیک ساختارهای درهم‌تنیده، نسبت به روش‌های پایه و حتی SKKM برتری نسبی دارد.

شکل (1): دادۀ واقعی Wine در دو خروجی اصلی و خروجی با الگوریتم پیشنهادی

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

جدول (4): ارزیابی خوشه­بندی طیفی در مجموعه‌داده­های واقعی

مقایسۀ عملکرد الگوریتم پیشنهادی با الگوریتم خوشه‌بندی طیفی بر روی مجموعه‌داده‌های مختلف در جدول (2) و (4) نشان می‌دهد الگوریتم پیشنهادی در برخی از مجموعه‌داده­ها عملکردی بهتر دارد. برای مثال، در مجموعه‌داده‌های Wine و Digits، الگوریتم پیشنهادی با NMI برابر 853/0 و 892/0 و دقت‌های برابر 955/0 و 892/0، نسبت به خوشه‌بندی طیفی که NMI 40/0 و 55/0 و دقت‌های 73/0 و 70/0 دارد، عملکردی بهتر نشان داده است. این بهبود می‌تواند به دلیل استفاده از تکنیک‌های پیشرفته‌تر در الگوریتم پیشنهادی باشد که ساختارهایی پیچیده‌تر را در داده‌ها شناسایی می‌کند.

از سوی دیگر، در مجموعه‌داده‌هایی مانند Iris، Breast و Cancer، الگوریتم خوشه‌بندی طیفی عملکردی بهتر نسبت به الگوریتم پیشنهادی دارد. برای مثال، در مجموعه‌دادۀIris ، خوشه‌بندی طیفی با 0٫76=NMI و دقت 0٫90، نسبت به الگوریتم پیشنهادی با 0٫460=NMI و دقت 0٫687، نتایجی بهتر ارائه داده­ است. این به دلیل سادگی ساختار مجموعه داده­ها‌ ‌است که الگوریتم‌های مبتنی بر طیف قادر به شناسایی خوشه‌ها با دقت بیشتری باشند.

ارزیابی عملکرد الگوریتم پیشنهادی و سایر الگوریتم‌ها با مجموعه‌داده‌های مصنوعی

دیتاست Blobs مجموعه‌ای از داده‌هاست که به صورت خوشه‌های گوسی در فضای ویژگی‌ها توزیع شده‌اند. ابعاد قابل تنظیم به ‌طور پیش‌فرض 2بُعدی هستند. تعداد نمونه‌ها به ‌طور پیش‌فرض 100 نمونه است. تعداد خوشه‌ها به‌ طور پیش‌فرض 3 خوشه است.

شکل (2): دادۀ مصنوعی Blobs

دیتاست Moons شامل دو نیم‌دایرۀ درهم‌تنیده است که به شکل دو هلال ماه در فضای دو‌بُعدی قرار دارند. این ساختار غیرخطی برای آزمایش الگوریتم‌هایی مناسب است که توانایی شناسایی مرزهای پیچیده را دارند. این داده دوبُعدی است. تعداد نمونه­ها به ‌طور پیش‌فرض 100 نمونه است. تعداد خوشه‌ها 2 خوشه است. نقاط داده در دو نیم‌دایرۀ درهم‌تنیده با امکان افزودن نویز گوسی توزیع می‌شوند.

شکل‌های (2) و (3) اثربخشی الگوریتم خوشه‌بندی پیشنهادی را بیشتر نشان می‌دهند و عملکرد خوشه‌بندی بی‌نقصی را در دو مجموعه‌دادۀ مصنوعی متنوع Blobs و Moons نشان می‌دهند. همۀ معیارهای ارزیابی به حداکثر مقادیر خود رسیده‌اند که این امر نشان می‌دهد الگوریتم با موفقیت ساختارهای خوشه‌بندی اساسی را حتی در توزیع‌های دادۀ پیچیده و غیرمحدب بدون خطا شناسایی می‌کند. این امر سازگاری الگوریتم پشنهادی را در مدیریت انواع اشکال داده برجسته می‌کند.

شکل (3): دادۀ مصنوعی Moons

 جدول (5): ARI در مجموعه‌داده‌های مصنوعی

 جدول (6): NMI در مجموعه‌داده­های مصنوعی

 جدول (7): دقت در مجموعه‌داده­های مصنوعی

برای مقایسه عملکرد الگوریتم‌های خوشه‌بندی بر روی مجموعه‌داده‌های مصنوعی R15، Blobs و Moonsدر جدول‌های (5)، (6) و (7)، سه معیار ارزیابیARI ، NMI و دقت بررسی شده‌اند. نتایج نشان می‌دهد الگوریتم پیشنهادی، الگوریتم خوشه‌بندی طیفی و الگوریتم k میانگین استاندارد در هر یک از این مجموعه‌داده‌ها عملکردی متفاوت دارند.

در مجموعه‌دادۀ R15، الگوریتم پیشنهادی با ARIبرابر 88/0، NMI برابر 94/0 و دقت برابر 92/0، عملکردی بهتر نسبت به الگوریتم‌های دیگر داشته ­است. الگوریتم خوشه‌بندی طیفی با ARI برابر 64/0، NMI برابر 71/0 و دقت برابر 91/0 در رتبۀ دوم قرار دارد، در حالی که الگوریتم k میانگین استاندارد با ARI برابر 57/0، NMI برابر 57/0 و دقت برابر 87/0 کمترین عملکرد را نشان داده است. این نتایج نشان می‌دهد الگوریتم پیشنهادی در شناسایی خوشه­های پیچیده‌تر موفق‌تر عمل کرده ­است. مجموعه‌دادۀ Blobs در این مجموعه‌داده، الگوریتم‌ خوشه‌بندی طیفی و k میانگین استاندارد هر دو با ARI و NMI برابر 1 و دقت برابر 1، عملکردی بسیار خوب داشته‌اند. الگوریتم پیشنهادی با ARI برابر 676/0، NMI برابر 759/0 و دقت برابر 860/0، عملکردی کمتر نسبت به دو الگوریتم دیگر داشته است. این نتایج نشان می‌دهد در داده‌هایی با ساختار ساده‌تر، الگوریتم‌های سنتی‌تر مانند k میانگین می‌توانند عملکردی مناسب داشته باشند. مجموعه‌دادۀ Moons در این مجموعه‌داده، الگوریتم پیشنهادی و الگوریتم خوشه‌بندی طیفی هر دو با ARI و NMI برابر 1 و دقت برابر 1، عملکردی بسیار خوب داشته­اند. الگوریتم kمیانگین استاندارد با ARI برابر 1، NMI برابر 38/0 و دقت برابر 78/0، عملکردی با دقت کمتر نسبت به دو الگوریتم دیگر داشته است. این نتایج نشان می‌دهد در داده­هایی با ساختار غیرخطی و پیچیده‌تر، الگوریتم‌های پیشرفته‌تر مانند خوشه‌بندی طیفی می‌توانند عملکردی بهتر داشته باشند.

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

تحلیل آماری کیفی (Wilcoxon & Friedman)

نتایج در جدول (8) نشان می‌دهد الگوریتم پیشنهادی در مقایسه با دو روش دیگر، یعنی خوشه‌بندی طیفی و  K میانگین استاندارد، عملکردی بسیار بهتر از خود نشان داده­است. در بخش میانگین NMI، مقدار به‌دست‌آمده برای روش پیشنهادی بیشتر از دو روش دیگر است که نشان می‌دهد الگوریتم پیشنهادی توانسته است ساختارهای درونی داده‌ها را بهتر شناسایی کند و خوشه‌هایی با شباهت درونی بیشتر ایجاد کند. همچنین، مقدار انحراف معیار کمتر بیانگر پایداری بهتر این روش در میان تکرارهای مختلف و بر روی مجموعه‌داده‌های گوناگون است. این نتایج نشان می‌دهد روش پیشنهادی علاوه بر دقت بیشتر، از نظر پایداری و سازگاری نیز برتر است.

در ادامه، آزمون Wilcoxon Signed-Rank برای مقایسۀ زوجی الگوریتم‌ها انجام شده است. بر اساس مقادیرp ، اختلاف میان روش پیشنهادی با هر دو الگوریتم دیگر در سطح اطمینان 95 درصد معنادار است؛ به ‌طوری که مقدار p بین روش پیشنهادی و خوشه‌بندی طیفی برابر 031/0 و بین روش پیشنهادی و  Kمیانگین استاندارد برابر 016/0 بوده است. این بدان معناست که روش پیشنهادی به طور آماری در شاخص NMI عملکردی بهتر دارد. تنها تفاوت بین خوشه‌بندی طیفی و K میانگین از نظر آماری معنادار نیست که نشان می‌دهد عملکرد این دو روش در سطحی مشابه قرار دارد.

نتایج آزمون Friedman نیز این یافته‌ها را تأیید می‌کند. مقدار آمارۀ χ² برابر 33/10 است و همچنین p برابر 0057/0است که نشان‌دهندۀ وجود تفاوت معنادار در عملکرد سه الگوریتم است. میانگین رتبه‌های فریدمن نشان می‌دهد الگوریتم پیشنهادی با رتبۀ 17/1 بهترین عملکرد را دارد، در حالی که خوشه‌بندی طیفی و K میانگین استاندارد به‌ ترتیب با رتبه‌های 00/2 و 83/2 در جایگاه دوم و سوم قرار گرفته‌اند. در آزمون Nemenyi Post-hoc نیز تفاوت بین روش پیشنهادی و  K میانگین استاندارد از نظر آماری معنادار است ، اما اختلاف بین روش پیشنهادی و خوشه‌بندی طیفی معنادار نیست. بنابراین، در سطح اطمینان 95 درصد، روش پیشنهادی نسبت به K میانگین استاندارد برتری آشکار دارد و در مقایسه با خوشه‌بندی طیفی نیز عملکردی بهتر، ولی نه به صورت معنادار از نظر آماری نشان می‌دهد. در مجموع، می‌توان نتیجه گرفت الگوریتم پیشنهادی پایدارترین و دقیق‌ترین روش خوشه‌بندی در این آزمایش‌ها بوده است.

جدول (8): تحلیل آماری الگوریتم‌ها بر اساس شاخص NMI

جدول (9): مطالعۀ ابلیشن الگوریتم پیشنهادی در داده‌های واقعی

نتایج جدول (9) نشان می‌دهد هستۀ آپولونیوس نقشی کلیدی در عملکرد مدل دارد. جایگزینی آن با هستۀ گوسی باعث کاهش میانگین NMI از 739/0 به 691/0 شده است. این افت به ‌ویژه در داده‌هایی با ساختار غیرخطی (مانند Digits و Olivetti Faces) بیشتر بوده­ است، زیرا کرنل آپولونیوس حساسیت کمتری به تغییرات محلی دارد و روابط فاصله‌ای را در بازه‌های طولانی‌تر به صورت دقیق‌تر مدل می‌کند.

تغییر نوع لاپلاسیَن از غیرنرمال‌شده به نرمال‌شدۀ متقارن تأثیر کمی بر میانگین عملکرد گذاشت (حدود 2 درصد کاهش)، اما در داده‌های نامتوازن مانند Diabetes، پایداری بیشتری در همگرایی خوشه‌ها ایجاد کرد. در مقابل، تغییر ساختار گراف از kNN متقابل به kNN ساده باعث افت محسوس عملکرد شد. گراف متقابل باعث حذف یال‌های غیرمعنادار می‌شود و در نتیجه، ساختار خوشه‌ای تمیزتری به ‌دست می‌دهد.

در نهایت، مهم‌ترین بخش مطالعۀ ابلیشن مربوط به گام تعبیۀ طیفی است. اجرای مستقیم Kمیانگین استاندارد در فضای اصلی منجر به افت شدید (در NMI از 739/0 به 552/0) شد. این امر نشان می‌دهد فضای تعبیۀ طیفی با کاهش نویز و آشکارسازی ساختارهای غیرخطی، برای خوشه‌بندی ضروری است.

در مجموع، آزمایش‌ها نشان می‌دهند هر چهار مؤلفۀ کرنل آپولونیوس، لاپلاسیَن مناسب، گراف متقابل و تعبیۀ طیفی، در کنار هم، موجب افزایش چشمگیر دقت و پایداری الگوریتم پیشنهادی شده­اند.

تحلیل پیچیدگی زمانی الگوریتم پیشنهادی

در الگوریتم خوشه‌بندی طیفی بدون استفاده از PCA، ابتدا داده‌ها نرمال‌سازی می‌شوند که هزینه‌ای در حد  دارد. سپس، فاصلۀ زوجی بین تمام نمونه‌ها در بُعد d محاسبه می‌شود که یکی از پرهزینه‌ترین مراحل است و زمان اجرای آن  است. ساخت گراف k-نزدیک‌ترین همسایه ­ها نیز معمولاً همان مرتبۀ پیچیدگی را دارد، مگر از روش‌های سریع‌تر استفاده شود. تشکیل ماتریس شباهت و محاسبۀ لاپلاسیان گراف نیز به ترتیب نیازمند زمان و حافظه‌ای در حدود  است. مرحلۀ بعدی تجزیۀ ویژۀ لاپلاسیان است که اگر روی ماتریس چگال انجام شود، پیچیدگی زمانی و حافظه‌ای  دارد. در پایان، الگوریتم K میانگین استاندارد روی embedding حاصل اجرا می‌شود که در هر تکرار هزینه‌ای در حد  (که در tتکرار  r=k-1) دارد. در مجموع، پیچیدگی کلی الگوریتم برابر  است.

5-  نتیجه­ گیری

الگوریتم پیشنهادی با استفاده از هستۀ آپولونیوس و ساختار گراف، در برخی از مجموعه‌داده‌ها عملکردی بهتر نسبت به خوشه‌بندی طیفی دارد، اما در برخی دیگر، خوشه‌بندی طیفی نتایجی بهتر ارائه می‌دهد. بنابراین، انتخاب الگوریتم مناسب به ویژگی‌های داده‌ها و ساختار آنها بستگی دارد. بررسی عملکرد الگوریتم پیشنهادی مبتنی بر هستۀ آپولونیوس در مقایسه با خوشه‌بندی طیفی نشان می‌دهد این الگوریتم در برخی از مجموعه‌داده‌ها مانندWine و Digits عملکردی بهتر دارد. برای مثال، در مجموعه‌دادۀ Wine، الگوریتم پیشنهادی با NMIبرابر 853/0 و دقت برابر 955/0، نسبت به خوشه‌بندی طیفی با NMI برابر 45/0 و دقت 73/0، نتایجی بهتر ارائه داده است. این بهبود ممکن است ناشی از استفاده از هستۀ آپولونیوس در ساخت گراف شباهت باشد که ساختارهای محلی و غیرخطی داده‌ها را بهتر مدل‌سازی می‌کند. با این حال، در مجموعه‌داده‌هایی مانندIris ، Cancer وBreast ، خوشه‌بندی طیفی عملکردی بهتر نسبت به الگوریتم پیشنهادی دارد. برای مثال، در مجموعه‌دادۀIris ، خوشه‌بندی طیفی با NMI (76/0) و دقت 90/0، نسبت به الگوریتم پیشنهادی با NMI (460/0) و دقت 687/0، نتایجی بهتر ارائه داده ­است. این امر ممکن است به دلیل سادگی ساختار داده­های این مجموعه­ها باشد که در آن، الگوریتم‌های مبتنی بر طیف قادر به شناسایی خوشه‌ها با دقت بیشتری هستند.

[1] تاریخ ارسال مقاله: 08/04/1404

تاریخ پذیرش مقاله: 05/02/1405

نام نویسنده مسئول: شهین پوربهرامی

نشانی نویسنده مسئول: ایران، تهران، دانشگاه ملی مهارت، گروه مهندسی کامپیوتر

[1] Spectral Clustering

[2] k-Means

[3] Hopkins Statistic

[4] MSL-MKC

[5] Laplacian regularization

[6] Support Vector Machines (SVM)

[7] Spectral Clustering with Neighbor Relations

[8]Sparse Kernel k-Means for Feature Selection in Nonlinear Clustering (SKKM)

[9] smoothing factor

[10] Accuracy

[11] Indicator Function

[12] https://archive.ics.uci.edu

https://www.kaggle.com