شده است. نشان را به عنوان فرا خوشه اول در نظر بگيريد. با جداسازي ابر لبه‌ها، شي وزن‌دار فرا لبه با بردار اجماع حاصل مي‌شود. متعاقباً، فرا خوشه در رقابت براي تخصيص رئوس/ اشياي و برنده مي‌شود و بنابراين خوشه در نتايج خوشه‌بندي جامع نشان داده مي‌شود. الگوريتم فرا خوشه‌بندي براي اين مثال روي خروجي‌هاي که يکي از شش خوشه‌بندي بهينه مي‌باشد و برابر با خوشه‌بندي‌هاي و است استوار است. عدم قطعيت در برخي از اشياء به ترتيب در اطمينان، ، ، ، ، و براي اشياي تا منعکس شده است.
2-۳-2-3. روش‌هاي مبتني بر ماتريس همبستگي
Input: D – the input data set N points
B – number of partitions to be combined
M – number of clusters in the final partition, σ
k – number of clusters in the components of the combination
Γ – a similarity-based clustering algorithm
for j=1 to B
Draw a random pseudosample Xj
Cluster the sample Xj: π (i)←K-means({Xj})
Update similarity values (co-association matrix) for all patterns in Xj
end
Combine partitions via chosen Γ: σ ←Γ (P)
Validate final partition, σ (optional)
return σ // consensus partition
شکل2-23. الگوريتم خوشه‌بندي تركيبي مبتني بر ماتريس همبستگي و با استفاده از توابع توافقي مختلف مبتني بر شباهت
در روش ماتريس همبستگي112 شباهت بين نقاط (مقادير همبستگي)، مي‌تواند با تعداد خوشه‌هاي به اشتراك گذاشته‌شده بين دو نقطه، در همه افرازهاي يك تركيب، تخمين زده شود . ساختار اين نوع از الگوريتم‌هاي خوشه‌بندي تركيبي در شكل 2-23 نشان داده شده است.
2-۳-2-3-1. الگوريتم‌هاي سلسله مراتبي تراكمي
فرض کنيد مجموعه داده شامل نقطه (نمونه) در فضاي بعدي است. داده‌هاي ورودي را مي‌توان به صورت يک ماتريس الگوي و يا يک ماتريس عدم تشابه در نظر گرفت. فرض کنيد مجموعه‌ي زيرمجموعه نمونه‌هاي ماست که از نمونه‌هاي اوليه استخراج‌شده‌اند. هر يک از الگوريتم‌هاي انتخابي هنگامي‌که بر روي زيرمجموعه نمونه‌هاي موجود در X اجرا شوند نتايج را توليد مي‌کنند. هر مجموعه‌اي از خوشه‌هاست. يا به عبارت ديگر و به ازاي هر داريم به طوري که تعداد خوشه‌ها در i امين خوشه‌بندي است. اولين يك الگوريتم پايه (براي مثال) را بر روي اجرا مي‌کنيم تا بتوانيم با استفاده از هاي توليدشده ماتريس همبستگي را به صورت زير به دست آوريم:
(2-52)
(2-53)
در رابطه 2-52، تابع در صورتي كه دو عنصر و در خوشه‌بندي در يك خوشه قرارگرفته باشند، مقدار يك و در غير اين صورت مقدار صفر برمي‌گرداند. مقدار پارامتر نمايانگر تعداد زيرمجموعه‌هاست و يا به بيان ديگر تعداد دفعات تكرار الگوريتم پايه است. معمولاً از الگوريتم‌هاي سلسله مراتبي پيوندي (منفرد، كامل، ميانگين و بخشي) براي تركيب از روي ماتريس همبستگي استفاده مي‌شود [33]. سه اشكال اصلي روش‌هاي مبتني بر ماتريس همبستگي عبارت‌اند از:
1- يك پيچيدگي محاسباتي درجه دوم در تعداد الگوها و ويژگي‌ها دارند.
2- هيچ راهنمايي براي اينكه كدام الگوريتم خوشه‌بندي بايد به‌کاربرده شود، وجود ندارد. به عنوان مثال پيوندي منفرد يا پيوندي كامل.
يك تركيب با يك تعداد كوچك از افرازها، ممكن است يك تخمين مطمئن از مقادير همبستگي را فراهم نكند.
2-۳-2-3-2. الگوريتم افرازبندي گراف با تکرار
در روش‌هاي معمول خوشه‌بندي ترکيبي پس از تشکيل ماتريس همبستگي حتماً بايد تعداد خوشه‌هاي نتيجه ترکيب را تعيين کرد. روشي که توسط [50] به تازگي معرفي شده است، راه‌حلي جهت تشخيص بهترين تعداد خوشه در ترکيب نهايي را به صورت خودکار معرفي مي‌کند. در اين روش ابتدا ماتريس همبستگي که در اينجا به آن ماتريس قضاوت مي‌گويند را تشکيل مي‌دهيم، سپس توسط الگوريتم افرازبندي تکراري مبتني بر گراف به صورت خودکار تعداد خوشه‌هاي نهايي را تشکيل مي‌دهيم. نتايج تجربي در [50] نشان مي‌دهد که هميشه فراهم کردن نتايج بهينه با تعيين تعداد خوشه نهايي به صورت ثابت امکان‌پذير نيست. در اين روش يک فرآيند افرازبندي گراف تکراري هر بار مقادير ماتريس همبستگي را يک درجه کاهش مي‌دهد به طوري که به تدريج اتصال ميان نقاط داده شکسته شود. افرازبندي گراف اصلي (که گراف معادل ماتريس همبستگي است) را به زير گراف‌ها تقسيم مي‌کند. براي تشخيص تعداد خوشه نتيجه نهايي کافي است تا تعداد زير گراف‌ها را بشماريم. الگوريتم افرازبندي گراف با تکرار دو مرحله کلي دارد، ابتدا کاهش درجه ماتريس و سپس شمارش تعداد زير گراف‌ها.
کاهش ماتريس‌ها يک رويه جهت کاهش ماتريس همبستگي به يک درجه کمتر در يک مرحله تکراري است، اين رويه تا جايي تکرار مي‌شود تا تمام موجوديت‌ها شروع به صفر شدن کنند. اين رويه به صورت رابطه زير نمايش داده مي‌شود.
(2-54)
در اين رابطه ماتريس کسر يک بر روي هر ورودي در ماتريس پيشين است. رويه کاهش ماتريس پيشنهادشده به تدريج ارتباطات سست بين نقاط داده را مي‌شکند.
شمارش زير گراف‌ها يک رويه براي شمارش تعداد زير گراف‌هاي متصل در هر ماتريس کاهش يافته است و براي ارزيابي شرايط خوشه‌بندي در طول فرآيند کاهش استفاده مي‌شود. الگوريتم پيمايشي گراف براي شمارش گراف از ماتريس پياده‌سازي شده است، به عنوان مثال الگوريتم113 که به صورت زير محاسبه مي‌شود:
(2-55)
ماتريس همبستگي که از متريک مشاهده‌اي جمع‌آوري شده است به عنوان ورودي فرآيند افرازبندي گراف عمل مي‌کند. در طول هر مرحله از کاهش، يک ماتريس جديد و گراف مجاورت آن توليد مي‌شود. هر شامل تعدادي از زير گراف‌ها مي‌باشد. تعداد اين زير گراف‌ها در واقع تعداد خوشه در نتيجه نهايي مي‌باشد. فرآيند افرازبندي تا وقتي که تمامي ورودي‌هاي صفر شوند ادامه پيدا مي‌کند. الگوريتم افرازبندي گراف با تکرار در شبه کد شکل (2-24) نشان داده شده است.
Input: A judgment matrix
BSF_traversal();
Do
Decreasing ()
BSF_traversal ()
ClusterNumber[n] = getSubGraphNumber();
Until (all entries in previous are )
Return and
Output: An array of cluster numbers-ClusterNumber[n] and a set of
شکل2-24. الگوريتم افرازبندي با تکرار
شکل (2-25) قسمتي از فرآيند کاهش و محاسبه را به تصوير مي‌کشد. گراف مجاورت ماتريس همبستگي اصلي قسمت (الف) شکل (2-25) نشان داده شده است. در اين مورد نشان داده شده است که تمامي نقاط داده متصل شده‌اند و بنابراين آن‌ها متعلق به تنها يک خوشه هستند. در بخش (ب) شکل (2-25) سه زير گراف پس از چند تکرار افرا بندي گراف نشان داده شده است، که در آن اتصالات بين سه زير گراف قطع شده است. اين بدان مفهوم مي‌باشد که اتصالات اين نقاط داده به طور مقايسه‌اي ضعيف تر از ساير نقاط متصل مي‌باشد. از اين رو در اين مرحله سه خوشه شناسايي شده است. در قسمت (ج) و (د) شکل (2-25) چهار و پنج خوشه بعد از تکرا الگوريتم افرازبندي گراف پيداشده‌اند. اگر اين فرآيند مطابق بخش (هـ) و (و) ادامه پيدا کند مي‌توان تعداد بيشتري از زير گراف‌ها را پيدا کرد. به عنوان نتيجه هر مرحله کاهش و شمارش اتصالات زير گراف‌ها را قطع کرده و يک تعداد از نتايج خوشه‌بندي پيدا مي‌شود. با اين وجود، بايد به اين سؤال پاسخ داد که چگونه نتايج نهايي خوشه‌بندي و تعداد دلخواه خوشه‌بندي به دست مي‌آيد.
(الف)
(ب)
(ج)
(د)
(هـ)
(و)
شکل2-25. نمايش گراف مجاورت در مراحل کاهش درجه ماتريس و شمارش آن [50].
در اين روش، هر تکرار از فرآيند افرازبندي گراف تعدادي از زير گراف‌ها را توليد مي‌کند، و تعداد زير گراف‌ها دقيقاً برابر با تعداد خوشه‌هاي آن تکرار مي‌باشد. در توزيع عددي زير گراف همان طور که در شکل (2-26) نشان داده شده است تعداد زير گراف‌ها ممکن است براي تعدادي از تکرارها ثابت باقي بماند سپس يک تغيير قابل‌لمس را پس از مرحله ثبات شاهد هستيم. تعداد مطلوب خوشه بر اين اساس به صورت باثبات‌ترين تعداد زير گراف در توزيع تعريف شده است، به اين دليل که تحت اين تعداد زير گراف اتصالات نقاط داده در زير گراف‌ها سخت‌ترين و قويي‌ترين در مقابله با شکستن هستند. شکل (2-26) مثالي از توزيع تعداد زير گراف و نتايج ترکيب نهايي را نشان مي‌دهد. در شکل (2-26) بديهي است که عدد چهار تعداد مطلوب مي‌باشد که هم در شکل پايداري توزيع (لف) و هم در تعداد خوشه‌ها (ب) نمايان است.
(الف)
(ب)
شکل2-26. مثال روند تغيير توزيع تعداد خوشه [50].
الگوريتم افرازبندي گراف با تکرار يک راه حل تطبيق‌پذير را دنبال مي‌کند زير آن مي‌تواند به راحتي با الگوريتم‌هاي خوشه‌بندي ديگر براي به دست آوردن نتايج قابل‌اتکا و شناسايي تعداد خوشه‌بندي دلخواه کار کند. شبه کد شکل (2-27) يک جريان کار عمومي براي پياده‌سازي الگوريتم افرازبندي گراف با تکرار در الگوريتم‌هاي ديگر را به تصوير مي‌کشد.
Input: A data set in n-dimensional space
1. Using OCA to cluster the data set Y with cluster number ranging from 2 to k;
2. Every clustering result can be represented by a vector , where if both and belongs to the cluster;
3. An observation matrix O can be computed from the vector L according to
4. A judgment matrix J can be obtained as the sum of observation matrices O,
5. The adjacency graph of J is iteratively partitioned so as to identify the desired cluster number and clustering results according to the distribution of the number of sub-graphs.
Output: The desired cluster number and final clustering result.
شکل2-27. جريان کار عمومي براي پياده‌سازي الگوريتم افرازبندي گراف
2-3-3. الگوريتم‌هاي خوشه‌بندي تركيبي كامل
الگوريتم‌هاي خوشه‌بندي تركيبي كامل114 روشي كاربردي و ساده جهت ايجاد خوشه‌بندي تركيبي است. در اين روش ما تمامي نتايج اوليه به دست آمده را بدون هيچ شرطي باهم توسط يك تابع توافقي ادغام مي‌کنيم. روش انباشت مدارک115 (EAC) يكي از روش‌هاي خوشه‌بندي كامل است كه توسط فرد و جين معرفي شد است. در اين روش معمولاً براي ايجاد نتايج اوليه خوشه‌بندي از استفاده مي‌شود و تابع توافقي آن روش الگوريتم‌هاي سلسله مراتبي تراكمي مي‌باشد. در روش انباشت مدارک ابتدا بر اساس رابطه (2-56) ماتريس همبستگي را تشکيل مي‌دهيم و سپس روي اين ماتريس همانند يک ماتريس شباهت/تفاوت ساده توسط الگوريتم سلسله مراتبي يک خوشه‌بندي انجام مي‌دهيم [19].
(2-56)
در رابطه (2-56) پارامتر تعداد دفعاتي است که جفت نمونه‌هاي و باهم در يک خوشه گروه‌بندي شده‌اند و تعداد نمونه‌برداري‌هايي است که هر دوي اين جفت نمونه‌ها به طور همزمان در آن ظاهرشده‌اند.
2-4. خوشه‌بندي تركيبي مبتني بر انتخاب
اولين بار فرن و لين در [23] خوشه‌بندي تركيبي مبتني بر انتخاب116 را با اين عنوان بر اساس ايده‌‌ي حادجي‌تودوروو117 و همکاران [84] معرفي کردند. که در آن اين نظريه مطرح مي‌شود که تعدادي از افرازها و يا خوشه‌هاي ارزيابي‌شده در مجموعه افرازهاي خوشه‌بندي ترکيبي مي‌تواند جواب نهايي بهتري نسبت به ترکيب کامل تمامي اعضاي مجموعه توليد کند. در اين روش علاوه بر چالش‌هاي پيشين مطرح‌شده در خوشه‌بندي ترکيبي (نحوي ساخت نتايج اوليه و نحوي ترکيب آن‌ها براي توليد نتيجه‌ي نهايي) دو مسئله‌ي ارزيابي نتايج اوليه و راهکار118 انتخاب مجموعه منتخب از نتايج ارزيابي‌شده مطرح خواهد شد. در سال‌هاي اخير برخي از مقالات راهکار‌هايي جهت حل دو چالش مطرح‌شده بيان کرده‌اند. اولين راه حل در اين روش توسط فرن و لين در [23] بيان شده است که اين تحقيق آن را خوشه‌بندي ترکيبي مبتني بر انتخاب فرن و لين نام‌گذاري مي‌کند. علاوه بر آن چندين روش
