داده شده است که با توجه به رفتار هر مجموعه داده گاهي اوقات يک روش خوشه‌بندي خاص پيدا مي‌شود که دقت بهتري از براي بعضي از مجموعه داده‌ها مي‌دهد [54]. اما الگوريتم به دليل سادگي و توانايي مناسب در خوشه‌بندي همواره به عنوان انتخاب اول در خوشه‌بندي ترکيبي مورد مطالعه قرار گرفته است. نكته مهمي كه در انتخاب الگوريتم‌ها بايد به آن دقت كرد اين است كه الگوريتم‌هايي همانند که بر اساس فاصله اقليدسي تمامي ويژگي‌ها كار مي‌کنند، در صورتي که حتي يک ويژگي يک نمونه داراي يک مقدار غيرمنتظره باشد، نمونه به طور نادرست دسته‌بندي مي‌شود. با توجه به اين مسئله مي‌توان از روش‌هايي مشابه اين الگوريتم‌ها كه مقاوم در برابر نويز هستند جهت رسيدن به پايداري و كيفيت بيشتر استفاده كرد. نكته ديگري كه در انتخاب الگوريتم‌هاي پايه بايد به آن توجه كرد اين است كه برخي از روش‌ها همانند الگوريتم‌هاي سلسله مراتبي پيوندي89 همواره با تكرار مكرر روي يك داده يك جواب منحصربه‌فرد ايجاد مي‌کنند كه در صورت ايجاد نتايج با اين‌گونه الگوريتم‌ها بايد فقط يكي از هر نوع آن را در ساخت نتايج نهايي استفاده كرد.
2-۳-1-2. تغيير پارامترهاي اوليه خوشه‌بندي ترکيبي
يکي ديگر از راه‌هاي افزايش پراکندگي تغيير پارامترهاي اوليه الگوريتم‌هاي خوشه‌بندي مي‌باشد. براي مثال در الگوريتم مي‌توان با تغيير تعداد خوشه‌ها در الگوريتم، يا تعداد دفعات تكرار90 اجراي الگوريتم و يا تغيير نمونه‌هاي اوليه91 الگوريتم ميزان پراكندگي را افزايش داد. در شکل 2-16 اثر نمونه‌هاي اوليه در خوشه‌بندي نهايي به وضوح قابل‌مشاهده مي‌باشد. در شکل زير در سمت چپ ابتدا نحوه توزيع نمونه‌ها92 نمايش داده شده است و سپس نتايج سه بار اجراي مختلف الگوريتم با سه نمونه شروع مختلف نمايش داده شده است [2, 6].
شکل2-16. نمونه‌هاي اوليه در نتايج الگوريتم . شکل‌ها به ترتيب از چپ به راست 1) نمايش فضايي14 نمونه پراکنده در فضا. 2) نتايج به دست آمده با نمونه‌هاي اوليه 1 و 8. 3)نتايج به دست آمده با نمونه‌هاي اوليه 2 و 3 . 4)نتايج به دست آمده با نمونه‌هاي اوليه 1 و 13 [2].
2-۳-1-3. انتخاب يا توليد ويژگي‌هاي جديد
استفاده از برخي از ويژگي‌هاي کل فضاي مجموعه داده و يا توليد ويژگي‌هاي جديد يکي ديگر از راه‌کارهاي افزايش پراکندگي در خوشه‌بندي ترکيبي مي‌باشد. بسياري از مطالعات در حيطه طبقه‌بندي اطلاعات اقدام به انتخاب زيرمجموعه‌اي از ويژگي‌ها مي‌نمايد که باعث افزايش ميزان پراکندگي، کاهش حجم محاسبات و بالا بردن دقت طبقه‌بندي کننده مي‌شود [54]. ولي به دليل ماهيت بدون ناظر بودن مسئله در خوشه‌بندي، انتخاب زيرمجموعه‌اي از ويژگي‌ها کمتر مورد توجه بوده است و بيشتر سعي در توليد ويژگي‌هاي جديد بوده است. روش‌هاي گوناگوني براي توليد ويژگي و استفاده از آن در خوشه‌بندي ترکيبي وجود دارد که ساده‌ترين آن‌ها نرمال سازي داده‌ها مي‌باشد. معمولاً داده‌هاي مسائلي که از فاصله اقليدسي براي خوشه‌بندي آن‌ها استفاده مي‌شود نرمال مي‌شوند. نتايج تجربي نشان داده است که عليرغم اينکه نرمال سازي داده‌ها در بعضي مواقع موجب بهبود کار مي‌شود در بعضي موارد موجب افت کارايي يک روش مي‌شود [12].
2-۳-1-4. انتخاب زيرمجموعه‌اي از مجموعه داده اصلي
يکي از راه‌هاي به دست آوردن اين پراکندگي استفاده از تعداد محدودي از نمونه‌ها به جاي کل نمونه‌ها مي‌باشد که اين امر دو مزيت دارد اول کاهش ميزان محاسبات و دوم افزايش پراکندگي. روش‌هاي متعددي تاکنون براي ايجاد زيرمجموعه‌ها پيشنهاد گرديده است. در روش‌هاي معمولي، شانس نمونه‌ها براي انتخاب شدن در زيرمجموعه برابر () مي‌باشد [57]. يكي از روش‌هاي معروف در انتخاب زيرمجموعه‌اي از مجموعه داده اصلي نمونه‌برداري93 مي‌باشد كه مي‌تواند با جايگزيني يا بدون جايگزيني و يا با انتخاب تصادفي94 باشد.
2-۳-2. تركيب نتايج با تابع توافقي
تركيب نتايج خوشه‌بندي‌هاي اوليه (پايه) و دست‌يابي به نتيجه نهايي يکي از مهم‌ترين مراحل خوشه‌بندي ترکيبي مي‌باشد. روش‌هاي گوناگوني براي ترکيب نتايج خوشه‌بندي‌هاي اوليه مختلف و ايجاد خوشه‌بندي نهايي وجود دارد که در زير به معرفي چند روش جديد و معروف در اين زمينه مي‌پردازيم ولي به طور كل مي‌توان آن‌ها را در سه گروه مبتني بر ابر گراف‌ها، روش رأي‌گيري و روش‌هاي مبتني بر ماتريس همبستگي دسته‌بندي كرد.
2-۳-2-1. روش مبتني بر مدل مخلوط
اين روش توسط تاپچي و همکاران [57] معرفي شده است. فرض کنيد يک دسته تايي از نقاط داده و يک دستهتايي افراز از اشياي داريم. افرازهاي متفاوت از براي هر نقطه از يک مجموعه از برچسب‌ها را برمي‌گرداند:
(2-31) ،
در اينجا، خوشه‌بندي مختلف نشان داده شده است و نشان‌دهنده برچسب تخصيص‌يافتهتوسط الگوريتم j-ام است. روش مدل مخلوط95، با استفاده از تعداد محدودي از مدل‌هاي مخلوط شده با توجه به احتمال وقوع برچسب‌هاي خوشه از الگو يا اشياء روشي براي حل تابع توافقي پيشنهاد مي‌دهد. فرض اصلي در اين روش اين است که برچسب‌هاي مدلي از ترسيمم تغييرهاي تصادفي96 از يک توصيف توزيع احتمال97 در يک مخلوط از مؤلفه‌هاي متراکم چند متغيره است.
(2-32)
در رابطه 2-32 مؤلفه توسط پارامتر تعريف شده است. مؤلفه در مخلوط با خوشه‌هاي افراز توافقي شناسايي مي‌شوند. ضريب مخلوط متناظر با احتمالات قبلي از خوشه‌ها تعيين مي‌شود. در اين مدل نقاط داده بر اساس توليد دو مرحله ذيل فرض مي‌شود: اول، براي طراحي مؤلفه بر اساس احتمال جرم تابع و پس از آن ساده‌سازي يک نقطه از توزيع . تمام داده به صورت مستقل و به صورت يکسان توزيع‌شده فرض مي‌شوند. اين امر اجازه مي‌دهد تا براي تعيين پارامترهاي در مجموعه داده از نمايش تابع احتمال لگاريتمي رابطه 2-33 استفاده کنيم.
(2-33)
با اين کار هدف خوشه‌بندي توافقي به يک مسئله تخمين احتمال حداکثر فرموله شده است. براي پيدا کردن بهترين چگالي مخلوط مناسب براي داده، بايد تابع احتمال نسبت به پارامتر ناشناس بيشينه شود. رابطه 2-34 نشان‌دهنده اين مسئله مي‌باشد:
(2-34)
مرحله مهم بعدي مشخص کردن تراکم مولفه-شرطي است. توجه داشته باشيد، که مسئله اصلي در خوشه‌بندي در فضاي داده با کمک الگوريتم‌هاي متعدد به فضاي ويژگي‌هاي جديد چند متغيره تبديل شده است. براي ساده‌سازي بيشتر مسئله، يک استقلال مشروط براي ساخت مؤلفه‌هاي بردار فرض مي‌شود، براي مثال احتمال شرطي زير را مي‌توان براي در نظر گرفت.
(2-35)
در توجيه اين کار، مي‌توان ذکر کرد که حتي اگر الگوريتم‌هاي خوشه‌بندي متفاوت (که با شاخص گذاري مي‌شوند) واقعاً مستقل نباشند، تقريب به وجود آمده در (2-21) را مي‌تواند با کارايي عالي در طبقه‌بندي بيز ساده در حوزه‌هاي گسسته توجيه کرد [43]. هدف نهايي تخصيص برچسب‌هاي مجزا به دادهاز طريق مسيريابي غيرمستقيم برآورد چگالي است. الگوهاي تخصيص‌يافته به خوشه‌ها درحساسيت کمتري به تقريب استقلال شرطي که با مقادير احتمال محاسبه مي‌شود دارد. آخرين مرحله از مدل مخلوط انتخاب احتمال چگالي براي مؤلفه‌هاي بردارهاي است. تا موقع‌هايي که متغيرهاي داراي ارزش اسمي از يک دسته از برچسب‌هاي خوشه در افراز باشد، طبيعي است که آن‌ها را به عنوان نتايج حاصل از يک آزمايش چندجمله‌اي زير فرض کنيم:
(2-36)
در اينجا، بدون، فراموش کردن اصل کلي، برچسب‌هاي خوشه‌ها در توسط اعداد صحيح در انتخاب مي‌شود. براي وضوح بيشتر اين مطلب، بايد توجه داشته باشيد که احتمال نتايج توسط تعريف مي‌شود و نتايج حاصل شامل همه مقادير ممکن از برچسب‌هاي در افراز است. همچنين، خلاصه احتمالات به صورت زير است:
(2-37)
به عنوان مثال، اگر j-امين افراز فقط شامل دو خوشه باشد، و برچسب‌هاي ممکن و باشند، آنگاه رابطه (2-37) مي‌تواند به صورت زير ساده شود:
(2-38)
بيشينه کردن مسئله احتمال98 در رابطه (2-38) عموماً موقع‌هايي که تمام پارامترهاي معلوم نباشند، نمي‌تواند بافرم بسته حل شود. ليکن، تابع احتمال رابطه (2-38) مي‌تواند با به‌کارگيري الگوريتم بهينه شود. به منظور اتخاذ الگوريتم، داده پنهان و احتمال کل داده‌هاي فرض مي‌شود. توزيع بايد مطابق با مقادير مشاهده شده باشد:
(2-39)
اگر مقدار معلوم باشد آنگاه مي‌توان فوراً گفت که مؤلفه‌ي مخلوطي در توليد نقطهاستفاده شده است. اين به اين معني است که به ازاي هر نقطه مشاهده‌شده، يک متغير بردار پنهان وجود دارد به طوري که اگر متعلق به m-امين مؤلفه باشد و در غير اين صورت مي‌باشد. براي نوشتن احتمال داده کامل رابطه زير مناسب است:
(2-40) مطابق با روش عمومي، بايد تابع کمکي که به عنوان يک حد پايين از مشاهده احتمال داده در رابطه (2-33) به کار گرفته مي‌شود تعريف کنيم:
(2-41)
در روش کلاسيک تحليل همگرايي الگوريتم [16, 45]، رابطه بيشينه سازي تابع با توجه به معادل افزايش تابع احتمال مشاهده‌شده در رابطه (2-33) است. ارزيابي اولين مرحله الگوريتم است. جايگزين رابطه (2-40) در تعريف برابر است با:
(2-42)
در رابطه بالا براي تخمين زدن پارامترهاي ما نياز به تعريف به صورت زير داريم:
(2-43)
اينجا، حدس اوليه در مورد پارامترهاي براي محاسبه مقادير مورد انتظار استفاده مي‌شود. با توجه به نوع تراکم چگالي مؤلفه شرطي در رابطه (2-35) و (2-36)، ما براي E-امين مرحله از الگوريتم رابطه زير را تعيين مي‌کنيم:
(2-44)
M-امين مرحله از مقادير بيشينه تابع در رابطه (2-42) توسط پارامترهاي ، با توجه به ارزش مقادير مورد انتظار از متغير در E-امين مرحله آن در رابطه (2-44) برابر است با:
(2-45)
دو بخش سمت راست معادله مي‌تواند به طور مستقل بهينه شود. ضريب به راحتي با استفاده از ضرايب لاگرانژ و محدوديت به صورت زير محاسبه شود:
(2-46)
(2-47)
به همين ترتيب، با فرض مستقل بودن چگالي مؤلفه شرطي از متغيرهاي که در رابطه (2-33) شرح داده شده است به دست آوردن مقادير بهينه ، را تسهيل مي‌کنيم. باز هم، محدوديت طبيعي و ضريب لاگرانژ مورد استفاده قرار مي‌گيرد:
(2-48)
(2-49)
به طور خلاصه الگوريتم با حدس مقادير در چگالي مخلوط شروع مي‌شود. بعد از آن، گام‌هاي و آن قدر تکرار مي‌شود تا همگرايي معيار پوشش داده شود. پس از آن، با توجه به رابطه (2-43) مرحله براي متغير محاسبه مي‌شود. سپس محاسبه بهترين تخمين براي پارامترها مطابق رابطه (2-47،33-49) جهت بيشينه سازي احتمال استفاده مي‌شود. معيار همگرايي مي‌تواند بر اساس افزايش مقدار در تابع احتمال بين دو نتيجه‌ي مرحله يا تخصيص پايدار نقاط، يا متناظر آن در. در واقع معيار پايداري مناسب‌ترين گزينه براي خوشه‌بندي است. راه حل توافقي خوشه‌بندي توسط يک بازبيني ساده از مقادير مورد انتظار متغيرهاي، با توجه با اينکه که نشان‌دهنده احتمال الگوي که توسط M-امين مؤلفه مخلوط توليد شده است، به دست مي‌آيد. پس از همگرايي به دست آمده، يک الگوي که بزرگ‌ترين مقدار از برچسب پنهان است به مؤلفه تخصيص داده مي‌شود. به طور مستقيم، در اصل هر يک از مرحله برابر با يک رويه بيز ساده است. ضمناً، M-مرحله براي تعيين سهم الگوي چگالي مؤلفه مشروط در مقايسه با تخمين حداکثر احتمال با ناظر، از ارزش اعضاي خوشه استفاده مي‌کند. اين روش
