نقاط a و b در ماتريس مجاورت است. شكل 2-5 اين الگوريتم را نمايش مي‌دهد. شكل 2-6 دندوگرام حاصل از روش پيوندي منفرد را براي ماتريس ، را نشان مي‌دهد.
Step 1. Begin with the disjoint clustering implied by threshold graph, which contains no edges and which places every object in a unique cluster, as the current clustering. Set.
Step 2. From threshold graph.
If the number of comonents (maximally connected subgraphs) in, is less than the number of clusters in the current clustering, redefiene the current clustering by naming each component of as a cluster.
Step 3. If consists of a single connected graph, stop. Else, setand go to step 2.
شكل 2-5. الگوريتم خوشه‌بندي سلسله مراتبي تراكمي پيوندي منفرد
شكل 2-6. دندوگرام پيوندي منفرد براي ماتريس
2-2-1-1-3. الگوريتم پيوندي کامل
اين الگوريتم روش بيشينه يا روش دورترين همسايه نيز ناميده مي‌شود. الگوريتم پيوندي كامل مي‌گويد كه وقتي دو خوشه و شبيه به هم هستند كه بيشينه روي تمام ها در و كوچك باشد. به عبارت ديگر، در اين الگوريتم، براي يكي كردن دو خوشه، همه جفت‌ها در دو خوشه بايد شبيه به هم باشند [26]. اگر و خوشه‌ها باشند، در روش پيوندي كامل، فاصله آن‌ها برابر خواهد بود با:
(2-3)
كه نشان‌دهنده فاصله(عدم شباهت) بين نقاط a و در ماتريس مجاورت است. شكل 2-7 اين الگوريتم و شكل 2-8 دندوگرام حاصل از اين روش را براي ماتريس ، را نشان مي‌دهد.
Step 1. Begin with the disjoint clustering implied by threshold graph, which contains no edges and which places every object in a unique cluster, as the current clustering. Set.
Step 2. From threshold graph.
If two of the current clusters from a clique (maximally complete sub graph) in, redefine the current clustering by merging these two clusters into a single cluster.
Step 3. If, so that is the complete graph on the nodes, stop. Else, set and go to step 2.
شكل 2-7. الگوريتم خوشه‌بندي سلسله مراتبي تراكمي پيوندي كامل
شكل 2-8. دندوگرام پيوندي كامل براي ماتريس
2-2-1-1-4. الگوريتم پيوندي ميانگين
الگوريتم پيوندي منفرد اجازه مي‌دهد تا خوشه‌ها به صورت دراز و نازك رشد كنند. اين در شرايطي است كه الگوريتم پيوندي كامل خوشه‌هاي فشرده‌تري توليد مي‌کند. هر دو الگوريتم مستعد خطا با داده‌هاي خارج از محدوده46 هستند. الگوريتم خوشه‌بندي پيوندي ميانگين، يك تعادلي بين مقادير حدي الگوريتم‌هاي پيوندي منفرد و كامل است. الگوريتم پيوندي ميانگين همچنين، روش جفت-گروه بدون وزن با استفاده از ميانگين حسابي47 ناميده مي‌شود. اين الگوريتم، يكي از پركاربردترين الگوريتم‌هاي خوشه‌بندي سلسله مراتبي مي‌باشد [26]. اگر يك خوشه با تعداد تا عضو، و يك خوشه ديگر با تعداد تا عضو باشند، در روش پيوندي ميانگين، فاصله آن‌ها برابر خواهد بود با:
(2-4)
كه نشان‌دهنده فاصله(عدم شباهت) بين نقاط a و در ماتريس مجاورت است.
2-2-1-1-5. الگوريتم پيوندي بخشي
روش پيوندي بخشی که از مربع مجموع خطا‌های (SSE) خوشه‌های يک افراز برای ارزيابی استفاده می‌کند، يکی ديگر از روش‌های سلسله مراتبی می‌باشد [60]. اگر يك خوشه با تعداد تا عضو، و يك خوشه ديگر با تعداد تا عضو باشند و نماد به معناي فاصله اقليدسي و و مراكز خوشه‌هاي و باشد آنگاه در روش پيوندي بخشي، فاصله آن‌ها برابر خواهد بود با:
(2-5)
2-2-1-2. الگوريتم‌هاي افرازبندي
يك خاصيت مهم روش‌هاي خوشه‌بندي سلسله مراتبي، قابليت نمايش دندوگرام است كه تحليل‌گر را قادر مي‌سازد تا ببيند كه چگونه اشياء در سطوح متوالي مجاورت، در خوشه‌ها به هم پيوند مي‌خورند يا تفكيك مي‌شوند. همان طور كه اشاره شد، هدف الگوريتم‌هاي افرازبندي، تقسيم داده‌ها در خوشه‌ها، به گونه‌اي است كه داده‌هاي درون يك خوشه بيش‌ترين شباهت را به همديگر داشته باشند؛ و درعين‌حال، بيش‌ترين فاصله و اختلاف را با داده‌هاي خوشه‌هاي ديگر داشته باشند. آن‌ها يك افراز منفرد از داده را توليد مي‌کنند و سعي مي‌کنند تا گروه‌هاي طبيعي حاضر در داده را كشف كنند. هر دو رويكرد خوشه‌بندي، دامنه‌هاي مناسب كاربرد خودشان را دارند. معمولاً روش‌هاي خوشه‌بندي سلسله مراتبي، نياز به ماتريس مجاورت بين اشياء دارند؛ درحالي‌که روش‌هاي افرازبندي، به داده‌ها در قالب ماتريس الگو نياز دارند. نمايش رسمي مسئله خوشه‌بندي افرازبندي مي‌تواند به صورت زير باشد:
تعيين يك افراز از الگوها در گروه، يا خوشه، با داشتن الگو در يك فضاي d-بعدي؛ به طوري كه الگوها در يك خوشه بيش‌ترين شباهت را به هم داشته و با الگوهاي خوشه‌هاي ديگر بيش‌ترين، تفاوت را داشته باشند. تعداد خوشه‌ها،، ممكن است كه از قبل مشخص‌شده نباشد، اما در بسياري از الگوريتم‌هاي خوشه‌بندي افرازبندي، تعداد خوشه‌ها بايد از قبل معلوم باشند. در ادامه برخي از معروف‌ترين و پرکاربردترين الگوريتم‌هاي افرازبندي مورد بررسي قرار خواهند گرفت.
2-2-1-2-1. الگوريتم K-means
در الگوريتم مراكز خوشه‌ها بلافاصله بعد از اينكه يك نمونه به يك خوشه مي‌پيوندد محاسبه مي‌شوند. به طور معمول بيشتر روش‌هاي خوشه‌بندي تركيبي از الگوريتم جهت خوشه‌بندي اوليه خود استفاده مي‌کنند [37, 47, 57]. اما مطالعات اخير نشان داده‌اند كه با توجه به رفتار هر مجموعه داده، گاهي اوقات يك روش خوشه‌بندي خاص پيدا مي‌شود كه دقت بهتري از براي بعضي از مجموعه داده‌ها مي‌دهد [1, 54]. اما الگوريتم به دليل سادگي و توانايي مناسب در خوشه‌بندي همواره به عنوان انتخاب اول مطالعات خوشه‌بندي تركيبي مورد مطالعه قرار گرفته است. در شكل 2-10 شبه كد الگوريتم را مشاهده مي‌کنيد:
1. Place K points into the space represented by the objects that are being clustered.
These points represent initial group centroids.
2. Assign each object to the group that has the closest centroid.
3. When all objects have been assigned, recalculate the positions of the K centroids.
4. Repeat Steps 2 and 3 until the centroids no longer move. This produces a separation
of the objects into groups from which the metric to be minimized can be calculated
شكل 2-9. الگوريتم خوشه‌بندي افرازبندي
مقادير مراکز اوليه‌ي متفاوت براي الگوريتم مي‌تواند منجر به خوشه‌بندي‌هاي مختلفي شود. به خاطر اينكه اين الگوريتم مبتني بر مربع خطا است، مي‌تواند به کمينه محلي همگرا شود، مخصوصاً براي خوشه‌هايي كه به طور خيلي خوبي از هم تفكيك نمي‌شوند، اين امر صادق است. نشان داده شده است كه هيچ تضميني براي همگرايي يك الگوريتم تكراري به يك بهينه سراسري نيست [33]. به طور خلاصه مي‌توان ويژگي‌هاي الگوريتم را به صورت زير برشمرد:
1- بر اساس فاصله اقليدسي تمامي ويژگي‌ها مي‌باشد.
2- منجر به توليد خوشه‌هايي به صورت دايره، كره و يا ابر کره مي‌شود.
3- نسبت به روش‌هاي ديگر خوشه‌بندي، ساده و سريع است.
4- همگرايي آن به يك بهينه محلي اثبات شده است، اما تضميني براي همگرايي به بهينه سراسري وجود ندارد.
5- نسبت به مقداردهي اوليه مراكز خوشه‌ها خيلي حساس است.
2-2-1-2-2. الگوريتم FCM
الگوريتم FCM48 اولين بار توسط دون [13] ارائه شد. سپس توسط بزدك [66] بهبود يافت. اين متد ديدگاه جديدي را در خوشه‌بندي بر اساس منطق فازي [62] ارائه مي‌دهد. در اين ديدگاه جديد، به جاي اينكه داده‌ها در يك خوشه عضو باشند، در تمامي خوشه‌ها با يك ضريب عضويت كه بين صفر و يك است، عضو هستند و ما در اين نوع خوشه‌بندي، دنبال اين ضرايب هستيم. در روش‌هاي معمول در جايي كه ما داده داشته باشيم، جواب نهايي ماتريس خواهد بود كه هر خانه شامل برچسب خوشه‌ي داده‌ي نظير آن مي‌باشد. ولي در اين روش در صورت داشتن خوشه، جواب نهايي يك ماتريس خواهد بود كه در آن هر رديف شامل ضرايب عضويت داده‌ي نظير به آن خوشه است. بديهي است كه جمع افقي هر رديف (ضرايب عضويت يك داده خاص) برابر با يك خواهد بود. يك روش معمول جهت رسيدن به جواب‌هايي غير فازي بر اساس نتايج نهايي الگوريتم فازي، برچسب‌زني داده بر اساس آن ضريبي كه مقدار حداكثر را در اين داده دارد، مي‌باشد. رابطه 2-6 معادله پايه در روش فازي است: [66]
(2-6) ,
در رابطه 2-6 متغيرm يك عدد حقيقي بزرگ‌تر از يك و درجه عضويت داده در خوشه j-ام می‌باشد، كه خود ، i-امين داده d-بُعدي از داده‌ي مورد مطالعه مي‌باشد و مركز d-بعدي خوشه j-ام است و هر روش معمول جهت اندازه‌گيري شباهت ميان داده و مركز خوشه مي‌باشد. در روش خوشه‌بندي فازي مراكز خوشه () و درجه عضويت () با تكرار مكرر به ترتيب بر اساس رابطه‌هاي 2-7 و 2-8 به‌روزرساني مي‌شوند، تا زماني كه شرط توقف درست در آيد. در اين شرط مقدار يك مقدار توافقي بسيار کوچک‌تر از يك مي‌باشد كه مطابق با نوع داده و دقت خوشه‌بندي قابل جايگذاري خواهد بود. بديهي است كه هر چقدر اين مقدار به سمت صفر ميل كند درجه عضويت دقيق‌تر و مقدار زمان اجرا بيشتر خواهد بود [66].
(2-7)
(2-8)
مراحل اجراي الگوريتم در شبه كد شكل 2-11 شرح داده شده است:
1.Initialize matrix,
2.At k-step: calculate the centers vectors with
3.Update ,
4. If then STOP; otherwice returen to step 2.
شكل 2-10. الگوريتم فازي خوشه‌بندي
2-2-1-2-3. الگوريتم طيفي
روش خوشه‌بندي طيفي49 كه بر اساس مفهوم گراف طيفي [11] مطرح شده است، از ماتريس شباهت براي كاهش بعد داده‌ها در خوشه‌بندي استفاده مي‌کند. در اين روش يك گراف وزن‌دار بدون جهت به نحوی توليد می‌شود كه رئوس گراف نشان‌دهنده‌ي مجموعه نقاط و هر يال وزن‌دار نشان‌دهنده‌ي ميزان شباهت جفت داده‌هاي متناظر باشد. بر خلاف روش‌هاي كلاسيك، اين روش، روي داده‌ای پراکنده در فضايي با شکل هندسي غير محدب، نتايج مطلوبي توليد مي‌کند [63]. كاربرد اين روش در محاسبات موازي50 [69, 70]، تنظيم بار51 [15]، طراحي VLSI52 [28]، طبقه‌بندي تصاوير53 [35] و بيوانفورماتيك54 [31, 59] مي‌باشد.
در خوشه‌بندي طيفي از بردارهاي ويژگي در ماتريس شباهت براي افراز مجموعه داده استفاده مي‌شود. در اغلب اين روش‌ها، مقدار ويژه اولويت بردارها را تعيين مي‌کند. ولي اين نحوه‌ي انتخاب، انتخاب بهترين بردارها را تضمين نمي‌دهد. در اولين تحقيقي كه در اين زمينه توسط ژيانگ و گنگ [61] انجام شد، مسئله‌ي انتخاب بردارهاي ويژگي مناسب جهت بهبود نتايج خوشه‌بندي پيشنهاد گرديد. در روش پيشنهادي آن‌ها شايستگي هر يك از بردارهاي با استفاده از تابع چگالي احتمال هر بردار تخمين زده مي‌شود. وزني به بردارهايي كه امتياز لازم را به دست آورندگ، اختصاص يافته و براي خوشه‌بندي از آن‌ها استفاده مي‌شود. در كاري ديگر كه توسط ژائو [64] انجام شده است، هر يك از بردارهاي ويژه به ترتيب حذف مي‌شوند و مقدار آنتروپي مجموعه بردارهاي باقي‌مانده محاسبه مي‌شود. برداري كه حذف آن منجر به افزايش آنتروپي و ايجاد بي‌نظمي بيشتر در مجموعه داده شود، اهميت بيشتري داشته و در رتبه بالاتري قرار مي‌گيرد. سپس زيرمجموعه‌اي از مناسب‌ترين بردارها براي خوشه‌بندي مورد استفاده قرار مي‌گيرند. الگوريتم خوشه‌بندي طيفي داراي متدهاي متفاوتي جهت پياده‌سازي است، كه الگوريتم‌هاي برش نرمال، NJW، SLH وPF از آن جمله مي‌باشد. در تمامي اين روش‌ها، بخش اول، يعني توليد گراف، مشترك مي‌باشد. ما در ادامه ابتدا به بررسي بخش مشترك اين روش‌ها مي‌پردازيم.
