نوع مقاله : مقاله پژوهشی فارسی
نویسنده
استادیار گروه مهندسی کامپیوتر، دانشگاه ملی مهارت، تهران، ایران
چکیده
کلیدواژهها
موضوعات
عنوان مقاله [English]
نویسنده [English]
In this study, a novel clustering algorithm based on the Apollonius kernel is presented. By utilizing the graph Laplacian matrix and the k-means algorithm, this method outperforms traditional approaches in separating clusters. In the first step, the data are normalized to standardize the feature scales. Then, by computing the Euclidean distance between points and applying the Apollonius kernel, the pairwise similarity matrix is constructed. Using the k-nearest neighbor graph, only the connections of the nearest neighbors are retained. Next, the graph Laplacian matrix is obtained as the difference between the degree matrix and the similarity matrix. This matrix represents the relationships between data points. By performing eigenvalue decomposition on the Laplacian matrix, the eigenvectors corresponding to the smallest eigenvalues are selected. The data are then projected onto a reduced space where the clusters are more clearly distinguishable. Then, the k-means algorithm is applied to the reduced data to determine the clusters. Finally, accuracy and other standard clustering validation metrics are used to evaluate the quality of the clustering. Experimental results show that this algorithm performs better than traditional methods, especially on datasets with nonlinear structures. Furthermore, the use of the Apollonius kernel in constructing the similarity graph improves the accuracy of identifying local structures in the data.
کلیدواژهها [English]
در دهههای اخیر، الگوریتمهای خوشهبندی طیفی[1] به عنوان ابزارهای قدرتمند برای شناسایی ساختارهای پیچیده و غیرخطی در دادهها مورد توجه قرار گرفتهاند. این الگوریتمها با استفاده از ماتریس لاپلاسین گراف و تجزیۀ مقادیر ویژه، دادهها را به فضای ویژگیهای جدیدی منتقل میکنند که در آن، خوشهها واضحتر قابل تفکیک هستند. با این حال، محاسبۀ مقادیر ویژه برای ماتریسهای بزرگ ممکن است از نظر محاسباتی پرهزینه باشد.
یک الگوریتم ساده برای خوشهبندی طیفی ارائه شده است که از بردارهای ویژۀ ماتریس لاپلاسین نرمالشدۀ گراف شباهت دادهها استفاده میکند ]1[. این الگوریتم با بهرهگیری از نظریۀ اختلال ماتریس، شرایطی را تحلیل میکند که تحت آن میتواند خوشهبندی مؤثری انجام دهد. الگوریتم خوشهبندی طیفی، با وجود توانایی در شناسایی ساختارهای پیچیده در دادهها، دارای معایبی است. یکی از مهمترین چالشها پیچیدگی محاسباتی زیاد است. همچنین، خوشهبندی طیفی ممکن است در شناسایی خوشههایی با اندازهها یا چگالیهای متفاوت دچار مشکل شود و به حضور نویز و دادههای پرت حساس باشد که ممکن است بر کیفیت نتایج تأثیر منفی بگذارد. در نهایت، تعیین تعداد مناسب خوشهها برای خوشهبندی طیفی دشوار است و نیاز به دانش قبلی یا آزمایشهای متعدد دارد.
الگوریتم k میانگین[2] استاندارد توسط جیمز مککوئین در مقالهای با عنوان «برخی روشها برای طبقهبندی و تحلیل مشاهدات چندمتغیره» معرفی شد که در سال ۱۹۶۷ در مجموعه مقالات پنجمین سمپوزیوم برکلی دربارۀ آمار و احتمال ریاضی منتشر شد ]2[. در این روش، مککوئین الگوریتمی را برای تقسیم دادهها به k خوشه ارائه داد که هدف آن کمینهسازی واریانس درونخوشهای است. الگوریتم با انتخاب تصادفی مراکز اولیۀ خوشهها آغاز میشود و سپس، به صورت تکراری، هر داده به نزدیکترین مرکز خوشه اختصاص مییابد و مراکز خوشهها بر اساس میانگین دادههای اختصاصیافته به آنها بهروز میشوند. این فرایند تا زمانی ادامه مییابد که مراکز خوشهها تغییر نکنند یا تغییرات آنها به حداقل برسد. مککوئین در این مقاله ویژگیهای آماری الگوریتم و کاربردهای آن در تحلیل دادههای چندمتغیره را بررسی کرد.
خوشهبندی k میانگین هستۀ پراکنده چالشهای خوشهبندی دادههای پیچیده و غیرخطی را بررسی میکند. روشهای سنتی مانند k میانگین در شناسایی ساختارهای غیرخطی محدودیت دارند؛ بنابراین، تکنیکهای جایگزین مانند k میانگین هسته و خوشهبندی طیفی توسعه یافتهاند. با این حال، حضور متغیرهای نامربوط در دادهها میتواند عملکرد این الگوریتمها را کاهش دهد ]3[. برای مقابله با این مشکل، روشهای انتخاب متغیر مانند فیلتر، پوششی و جاسازی شده معرفی شدهاند. الگوریتم k میانگین هستۀ یک روش انتخاب متغیر جاسازیشده با استفاده از فضای ضرب تانسوری و هستۀ تحلیل واریانس عمومی برای خوشهبندی غیرخطی است. این رویکرد با استفاده از فضای ضرب تانسوری، تعاملات پیچیدۀ بین ویژگیها را مدلسازی میکند و با اعمال هستۀ تحلیل واریانس، ساختارهای غیرخطی در دادهها را بهتر شناسایی میکند ]3[.
الگوریتم خوشهبندی بر اساس آمار هاپکینز و k میانگین، محدودیتهای الگوریتم سنتی k میانگین در خوشهبندی دادههایی با ساختارهای نامنظم را بررسی میکند و با استفاده از آمار هوپکینز[3] و مفهوم جفت نزدیکترین همسایه طراحی شده است. در مرحلۀ اول، دادهها به زیرمجموعههای کروی و نسبتاً یکنواخت تقسیم میشوند. سپس، با تعیین روابط مجاورت بین این زیرمجموعهها، زیرمجموعههای مجاور و بههمپیوسته تا رسیدن به تعداد خوشههای مدنظر k ادغام میشوند. آمار هوپکینز در فرایند تقسیمبندی دادهها برای ارزیابی تمایل به خوشهبندی استفاده میشود، در حالی که مفهوم جفت نزدیکترین همسایه در فرایند ادغام زیرمجموعهها به کار میرود ]4[.
در این راستا، الگوریتم پیشنهادی ما با بهرهگیری از هستۀ آپولونیوس برای ساخت گراف شباهت، ماتریس لاپلاسین را تشکیل و سپس با استفاده از تجزیۀ طیفی و الگوریتم k میانگین، خوشهبندی دادهها را انجام میدهد. این رویکرد با تمرکز بر ساختارهای محلی دادهها و کاهش هزینههای محاسباتی، میتواند عملکردی بهتر در شناسایی خوشههای پیچیده و غیرخطی ارائه دهد.
ساختار این مقاله به شرح زیر سازماندهی شده است. بخش 2 مروری بر الگوریتمهای خوشهبندی مبتنی بر چگالی و هندسه دارد و نقاط قوت و محدودیتهای آنها را برجسته میکند. در بخش 3، الگوریتم پیشنهادی را معرفی میکنیم که هستۀ آپولونیوس را با ماتریس لاپلاسین و k میانگین برای خوشهبندی دادهها ادغام میکند. بخش 4 نتایج تجربی را ارائه و مورد بحث قرار میدهد و توانایی بهبودیافتۀ روش پیشنهادی را در شناسایی ساختارهای پیچیده و غیرخطی در مقایسه با تکنیکهای خوشهبندی سنتی و پیشرفته نشان میدهد. در نهایت، بخش 5 نتیجهگیری مقاله را نشان میدهد.
الگوریتم سادۀ چندفیلتری مبتنی بر k میانگین با استفاده از معیار همترازی هسته در محیط بدون نظارت، ترکیب فیلترها برای خوشهبندی را بهینهسازی میکند. با فرمولهکردن مسئله به صورت بهینهسازی نرم، الگوریتم قادر به حل مؤثر آن با استفاده از روش نزول گرادیان کاهشیافته است ]5[.
روش یادگیری ساختار متقابل برای خوشهبندیهای چندگانه[4] با یادگیری همزمان ساختارهای زوجی و خوشهای، ماتریس تقسیمبندی برای خوشهبندی را بهبود میدهد. با استفاده از گراف شباهت تبعیضآمیز در فضای هسته و همترازی با تقسیمبندیهای پایه، ساختارهای مختلف به صورت یکپارچه یاد گرفته میشوند ]6[. الگوریتم ابتدا یک گراف شباهت تبعیضآمیز در فضای هسته میسازد که با استفاده از هستههای پایۀ مختلف، شباهتهای بین نمونهها را به صورت دقیقتر مدل میکند. سپس، با همترازی این گراف با تقسیمبندیهای پایه، ساختارهای مختلف به صورت یکپارچه یاد گرفته میشوند. یکی از ویژگیهای این الگوریتم استفاده از منظمسازی لاپلاسین[5] است که به حفظ ساختار زوجی در ماتریس تقسیمبندی کمک میکند و در عین حال، اطلاعات ساختار خوشهای را در گراف شباهت تزریق میکند. این روش به ویژه در کاربردهایی مانند تحلیل دادههای چندمنظوره، پردازش تصاویر و شناسایی الگوهای پیچیده در دادههای بزرگ، پتانسیل زیادی دارد.
در روش جدید مبتنی بر تابع آپولونیوس و خوشهبندی قلۀ چگالی، کرنل جدید برای ماشین بردار پشتیبان [6] معرفی شده است که بر پایۀ تابع آپولونیوس است. این رویکرد با هدف بهبود عملکرد طبقهبندی در دادههای پیچیده و غیرخطی ارائه شده است ]7[. در این رویکرد، تابع آپولونیوس برای مدلسازی دقیقتر روابط هندسی بین نقاط داده استفاده میشود، در حالی که خوشهبندی قلههای چگالی به شناسایی ساختارهای محلی و نقاط مرکزی در دادهها کمک میکند. این ترکیب باعث میشود کرنل آپولونیوس به صورت تطبیقی با ساختارهای مختلف دادهها سازگار شود و عملکردی بهتر در طبقهبندی دادههای پیچیده نسبت به کرنلهای سنتی مانند کرنل گاوسی ارائه دهد. در روش پیشنهادی، برای خوشهبندی از این کرنل برای افزایش دقت استقاده شده است.
الگوریتم خوشهبندی طیفی بر اساس عملکرد کرنل گاوسی بهبودیافته و جستوجوی آنتن سوسک با ضریب میرایی با بهبود تابع کرنل گاوسی و استفاده از الگوریتم جستوجوی شاخک سوسک با عامل میرایی، مشکلات مربوط به پارامترهای مقیاس و پایداری نتایج در خوشهبندی طیفی را حل میکند ]8[. در این الگوریتم، برای ساخت ماتریس شباهت، از یک تابع کرنل گاوسی بهبودیافته بهرهبرداری میشود که با استفاده از اطلاعات فاصلۀ برخی از نزدیکترین همسایگان، به طور تطبیقی پارامتر مقیاس را انتخاب میکند. این رویکرد به حل مشکل انتخاب پارامتر مقیاس در کرنل گاوسی کمک میکند. در مرحلۀ خوشهبندی، از الگوریتم جستوجوی شاخک سوسک با ضریب میرایی استفاده میشود تا بر مشکل ناپایداری نتایج خوشهبندی غلبه کند.
خوشهبندی طیفی به نام SC-NR [7] روشی برای بهبود ماتریس شباهت است که از ترکیب فاصلۀ اقلیدسی وزندار با تابع کرنل گاوسی استفاده میکند. وزنها بر اساس ترتیب همسایگان نزدیک تنظیم میشوند تا روابط واقعی بین نقاط بهتر بازتاب یابند. با این حال، تابع کرنل گاوسی با استفاده از فاصلۀ اقلیدسی و یک پارامتر ثابت سیگما، شباهت بین نقاط داده را اندازهگیری میکند. استفاده از یک سیگما ثابت میتواند به نتایج نادرست در خوشهبندی منجر شود، زیرا فاصلۀ اقلیدسی بهتنهایی قادر به بازتاب ساختار واقعی دادهها نیست. برای مثال، ممکن است نقاطی از خوشههای مختلف دارای فاصلۀ اقلیدسی یکسانی باشند که در نتیجه، تابع کرنل گاوسی شباهتی یکسان برای آنها محاسبه میکند و این امر ممکن است به خوشهبندی نادرست منجر شود ]9[.
در الگوریتم «K میانگین استاندارد هستۀ پراکنده برای انتخاب ویژگی در خوشهبندی غیرخطی»[8] ]3[. نویسندگان چارچوبی برای خوشهبندی غیرخطی همراه با انتخاب متغیر پراکنده ارائه کردهاند که بر پایۀ گسترش الگوریتم K میانگین استاندارد کرنل با استفاده از کرنل ANOVA بنا شده است. این روش با تجزیۀ کرنل به مؤلفههای مربوط به اثرات اصلی و تعامل متغیرها و اعمال قیدهای ترکیبی بر ضرایب وزنی، امکان حذف ویژگیهای بیاهمیت را فراهم میکند و همزمان، ساختارهای غیرخطی پیچیده در داده را مدل میسازد. الگوریتم SKKM از بهینهسازی تناوبی برای بهروزرسانی خوشهها و وزنهای ویژگی استفاده میکند. این رویکرد یکی از نخستین تلاشها برای تلفیق یادگیری غیرخطی و انتخاب متغیر در چارچوبی یکپارچه است.
مرحلۀ اول: ساخت گراف شباهت با استفاده از هستۀ آپولونیوس
در این مرحله، ابتدا دادهها را نرمالسازی میکنیم تا مقیاس ویژگیها یکسان شود. سپس، با ضرب ویژگیها در وزنهای مشخصشده، اهمیت هر ویژگی را تنظیم میکنیم. در ادامه، یک گراف kنزدیکترین همسایگان با استفاده از فاصلۀ اقلیدسی بین نقاط ساخته میشود. برای محاسبۀ شباهت بین نقاط ]10، 11[. از هستۀ آپولونیوس که بر اساس ساخت دایرۀ آپولونیوس است ]12، 13[ استفاده میکنیم که به صورت فرمول (1) تعریف میشود:
که در آن، اپسیلون یک مقدار ثابت کوچک است که از تقسیم بر صفر جلوگیری میکند (پارامتر اپسیلون نقش فیلتر نرمکننده[9] را دارد تا از تقسیم بر صفر جلوگیری و حساسیت شباهت به فواصل خیلی کوچک را کنترل کند). شباهت محاسبهشده با ماتریس k نزدیکترین همسایگان ضرب میشود تا فقط اتصالات همسایگان نزدیک حفظ شوند.
مرحلۀ دوم: ساخت ماتریس لاپلاسین گراف
در این مرحله، ماتریس درجه را محاسبه میکنیم که هر قطر آن نشاندهندۀ مجموع وزنهای یالهای متصل به گره مربوط است. سپس، ماتریس لاپلاسین گراف را با استفاده از فرمول (2) محاسبه میکنیم:
که در آن، D ماتریس درجه و W ماتریس شباهت است. این ماتریس نمایانگر ساختار گراف و روابط بین نقاط داده است.
مرحلۀ سوم: تجزیۀ طیفی و کاهش ابعاد
در این مرحله، تجزیۀ مقادیر ویژۀ ماتریس لاپلاسین انجام میشود تا مقادیر ویژه و بردارهای ویژۀ آن به دست آیند. سپس، بردارهای ویژۀ متناظر با کوچکترین مقادیر ویژه را انتخاب میکنیم و آنها را به صورت ماتریسی با ابعاد n×k (که در آن k تعداد خوشهها و n تعداد نمونههای ذخیرهشده است) نشان میدهیم. این ماتریس ویژگیهایی جدید را برای دادهها فراهم میکند که در فضای کاهشیافته قرار دارند و خوشهها در آن واضحتر قابل تفکیک هستند.
مرحلۀ چهارم: خوشهبندی با استفاده از k میانگین
در این مرحله، الگوریتم k میانگین را بر روی ماتریس ویژگیهای بهدستآمده از مرحلۀ قبلی اعمال میکنیم. در این الگوریتم، ابتدا مراکز اولیۀ خوشهها به صورت تصادفی انتخاب میشوند. سپس، هر داده به نزدیکترین مرکز خوشه اختصاص مییابد و مراکز خوشهها بر اساس میانگین دادههای اختصاصیافته به آنها بهروز میشوند. این فرایند تا زمانی ادامه مییابد که مراکز خوشهها تغییر نکنند یا تغییرات آنها به حداقل برسد ]2 .[
ارزیابی عملکرد روش پیشنهادی
برای ارزیابی کیفیت خوشهبندی از شاخصهایی مختلف همچون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): مجموعهدادههای واقعی
|
مجموعهداده |
تعداد خوشهها |
تعداد ابعاد |
تعداد دادهها |
|
Iris |
3 |
4 |
150 |
|
Wine |
3 |
13 |
178 |
|
Digits |
10 |
64 |
1797 |
|
Breast Cancer (Wisconsin Breast Cancer Diagnostic (WBCD)) |
2 |
30 |
569 |
|
Diabetes |
2 |
8 |
768 |
|
Olivetti Faces |
40 |
4096 |
400 |
جدول (2): ارزیابی الگوریتم پیشنهادی در مجموعهدادههای واقعی
|
مجموعهداده |
NMI الگوریتم پیشنهادی |
دقت الگوریتم پیشنهادی |
پارامتر k |
نوع لاپلاسیَن |
نکتۀ کلیدی عملکرد |
|
Iris |
460/0 |
687/0 |
10 |
L غیرنرمالشده |
شکاف طیفی بین λ₃ و λ₄ نشانگر سه خوشه است. |
|
Wine |
853/0 |
955/0 |
12 |
L_sym نرمالشده متقارن |
حساس به انتخاب k، عملکرد پایدار با k برابر 12 است. |
|
Digits |
892/0 |
829/0 |
15 |
L_rw نرمالشده تصادفی |
تعبیه با d=k عملکردی بهتر از شکاف طیفی دارد. |
|
Breast Cancer |
645/0 |
935/0 |
10 |
L غیرنرمالشده |
خوشهبندی پایدار، اما حساس به نویز. |
|
Breast Cancer (PCA) |
658/0 |
938/0 |
10 |
L غیرنرمالشده |
نتیجه بعد از اعمال کاهش ابعاد با PCA. |
|
Diabetes |
793/0 |
379/0 |
8 |
L_sym |
داده با همپوشانی زیاد، دقت کمتر ولی NMI زیاد. |
|
Olivetti Faces |
795/0 |
552/0 |
15 |
L_rw |
افزایش k باعث بهبود پایداری تعبیه شد. |
|
Olivetti Faces (PCA) |
809/0 |
618/0 |
15 |
L_rw |
نتیجه بعد از اعمال کاهش ابعاد با PCA |
|
SD ± میانگین عملکرد الگوریتم پیشنهادی |
739/0±22/0 |
733/0±214/0 |
— |
— |
— |
جدول (3): ارزیابی الگوریتم پیشنهادی، الگوریتم SKKM و k میانگین استاندارد در مجموعهدادههای واقعی
|
مجموعهدادهها |
NMI |
دقت |
ARI |
ARI |
|
k میانگین استاندارد |
k میانگین استاندارد |
الگوریتم پیشنهادی |
الگوریتم SKKM |
|
|
Iris |
74/0 |
78/0 |
70/0 |
74/0 |
|
Wine |
31/0 |
64/0 |
87/0 |
86/0 |
|
Digits |
50/0 |
37/0 |
83/0 |
81/0 |
|
Breast Cancer |
73/0 |
83/0 |
75/0 |
72/0 |
|
Diabetes |
005/0 |
65/0 |
- |
- |
|
Olivetti Faces |
55/0 |
54/0 |
- |
- |
|
SD ± میانگین |
255/0±472/0 |
158/0±635/0 |
071/0±788/0 |
061/0±783/0 |
جدول (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): ارزیابی خوشهبندی طیفی در مجموعهدادههای واقعی
|
مجموعهدادهها |
NMI (الگوریتم خوشهبندی طیفی) |
دقت (الگوریتم خوشهبندی طیفی) |
|
Iris |
0٫76 |
0٫90 |
|
Wine |
0٫46 |
0٫73 |
|
Digits |
0٫55 |
0٫70 |
|
Breast Cancer |
0٫75 |
0٫96 |
|
Diabetes |
0٫02 |
0٫68 |
|
Olivetti Faces |
0٫58 |
0٫60 |
|
SD ± میانگین |
0٫510±0٫266 |
762/0 ±135/0 |
مقایسۀ عملکرد الگوریتم پیشنهادی با الگوریتم خوشهبندی طیفی بر روی مجموعهدادههای مختلف در جدول (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 در مجموعهدادههای مصنوعی
|
روش پیشنهادی |
الگوریتم خوشهبندی طیفی |
k میانگین استاندارد |
مجموعهدادهها |
|
88/0 |
64/0 |
57/0 |
R15 |
|
676/0 |
1 |
1 |
Blobs |
|
1 |
1 |
1 |
Moons |
|
854/0±167/0 |
880/0 ±166/0 |
857/0±203/0 |
SD ± میانگین |
جدول (6): NMI در مجموعهدادههای مصنوعی
|
روش پیشنهادی |
الگوریتم خوشهبندی طیفی |
k میانگین استاندارد |
مجموعهدادهها |
|
94/0 |
71/0 |
57/0 |
R15 |
|
7/0 |
1 |
1 |
Blobs |
|
1 |
96/0 |
38/0 |
Moons |
|
90/0±122/0 |
890/0±155/0 |
650/0±318/0 |
SD ± میانگین |
جدول (7): دقت در مجموعهدادههای مصنوعی
|
روش پیشنهادی |
الگوریتم خوشهبندی طیفی |
k میانگین استاندارد |
مجموعهدادهها |
|
928/0 |
91/0 |
87/0 |
R15 |
|
860/0 |
1 |
1 |
Blobs |
|
1 |
97/0 |
38/0 |
Moons |
|
929/0±071/0 |
960/0±045/0 |
750/0 ± 296/0 |
SD ± میانگین |
برای مقایسه عملکرد الگوریتمهای خوشهبندی بر روی مجموعهدادههای مصنوعی 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
|
شاخص/آزمون |
معیار |
الگوریتم پیشنهادی |
خوشهبندی طیفی |
K میانگین استاندارد |
نتیجۀ آماری/تفسیر |
|
میانگین NMI واقعی |
میانگین ± انحراف معیار |
62/0±29/0 |
51/0±27/0 |
47/0±26/0 |
روش پیشنهادی بیشترین مقدار میانگین را دارد |
|
Wilcoxon Signed-Rank Test |
p(Proposed vs Spectral) |
— |
— |
— |
p برابر 031/0 → اختلاف معنادار به نفع الگوریتم پیشنهادی |
|
p(Proposed vs K-Means) |
— |
— |
— |
p برابر 016/0 → اختلاف معنادار به نفع الگوریتم پیشنهادی |
|
|
p(Spectral vs K-Means) |
— |
— |
— |
p برابر 313/0 →
اختلاف معنادار نیست |
|
|
Friedman Test |
χ² برابر 33/10و p برابر 0057/0 |
— |
— |
— |
تفاوت معنادار بین الگوریتمها→ p کمتر از 01/0 |
|
میانگین رتبۀ فریدمن |
رتبه (1=بهتر) |
17/1 |
00/2 |
83/2 |
الگوریتم پیشنهادی بهترین میانگین رتبه را دارد |
|
Nemenyi Post-hoc |
Rank (Proposed–Spectral) |
83/0 |
— |
— |
CD کمتر از 85/0 → تفاوت معنادار نیست |
|
Rank (Proposed–K-Means) |
66/1 |
— |
— |
CD بیشتر از 85/0→ تفاوت معنادار |
|
|
Critical Difference (CD) |
مقدار |
— |
— |
— |
CD برابر 85/0 در سطح اطمینان 95 درصد |
|
نتیجۀ نهایی |
تفسیر کلی |
الگوریتم پیشنهادی بهترین عملکرد کلی |
مشابه الگوریتم پیشنهادی در برخی از دادهها |
ضعیفتر در تمام دادهها |
الگوریتم پیشنهادی از K- Means به طور معنادار بهتر و از Spectral کمی بهتر است |
جدول (9): مطالعۀ ابلیشن الگوریتم پیشنهادی در دادههای واقعی
|
تغییر اعمالشده |
توضیح مؤلفۀ جایگزین |
NMI SD ± میانگین |
دقت SD ± میانگین |
تغییر عملکرد نسبت به مدل اصلی |
تحلیل کیفی |
|
مدل اصلی آپولونیوس + L + kNN متقابل + تعبیه طیفی |
پیکربندی پایۀ الگوریتم پیشنهادی |
739/0±22/0 |
733/0±214/0 |
— |
بهترین عملکرد، پایداری زیاد |
|
جایگزینی کرنل آپولونیوس با کرنل گوسی |
691/0±19/0 |
684/0±21/0 |
5/6%- |
افت جزئی در دادههای پیچیده، کرنل آپولونیوس به فواصل بلند حساستر است |
|
|
تغییر لاپلاسیَن از L به L_sym |
نرمالسازی متقارن |
726/0±20/0 |
724/0±20/0 |
1/2%- |
پایدارتر در دادههای نامتوازن، اما بدون بهبود معنادار |
|
تغییر گراف kNN متقابل ↔ ساده |
حذف شرط تقارن در همسایگی |
705/0±18/0 |
693/0±19/0 |
4/7-% |
کاهش پایداری به ویژه در دادههای نویزی |
|
اجرای Kمیانگین استاندارد در فضای اصلی (بدون تعبیۀ طیفی) |
حذف گام طیف نگاری |
552/0±23/0 |
541/0±21/0 |
24/1%- |
افت شدید عملکرد، تأیید اهمیت تعبیۀ طیفی |
|
اجرای Kمیانگین استاندارد پس از تعبیۀ طیفی (مدل کامل) |
پیکربندی نهایی الگوریتم |
739/0±22/0 |
733/0±214/0 |
— |
بهینهترین ترکیب از دید NMI و ACC |
نتایج جدول (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) دارد. در مجموع، پیچیدگی کلی الگوریتم برابر است.
الگوریتم پیشنهادی با استفاده از هستۀ آپولونیوس و ساختار گراف، در برخی از مجموعهدادهها عملکردی بهتر نسبت به خوشهبندی طیفی دارد، اما در برخی دیگر، خوشهبندی طیفی نتایجی بهتر ارائه میدهد. بنابراین، انتخاب الگوریتم مناسب به ویژگیهای دادهها و ساختار آنها بستگی دارد. بررسی عملکرد الگوریتم پیشنهادی مبتنی بر هستۀ آپولونیوس در مقایسه با خوشهبندی طیفی نشان میدهد این الگوریتم در برخی از مجموعهدادهها مانند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
)