را به صورت پایین به بالا بسازند، الگوریتم‌های خوشه‌بندی سلسله مراتبی تراکمی38 نامیده می‌شوند. همچنین، اگر آن‌ها دندوگرام را به صورت بالا به پایین بسازند، الگوریتم‌های خوشه‌بندی سلسله مراتبی تقسیم‌کننده39 نامیده می‌شوند [26]. مهم‌ترین روش‌های خوشه‌بندی سلسله مراتبی الگوریتم‌های سری پیوندی می‌باشد که در این بخش تعدادی از کاراترین آن‌ها مورد بررسی قرار خواهند گرفت که عبارت‌اند از:
1- الگوریتم پیوندی منفرد40
2- الگوریتم پیوندی کامل41
3- الگوریتم پیوندی میانگین42
4- الگوریتم پیوندی بخشی43
2-2-1-1-1. تعاریف و نماد‌ها
شکل 2-2. ماتریس مجاورت
قبل از معرفی این الگوریتم‌ها، در ابتدا نمادها و نحوه نمایش مسئله نمایش داده خواهد شد. فرض کنید که یک ماتریس مجاورت متقارن داریم. وارده در هر سمت قطر اصلی قرار دارد که شامل یک جای گشت اعداد صحیح بین 1 تا است. ما مجاورت‌ها را عدم شباهت در نظر می‌گیریم. به این معنی است که اشیاء 1 و 3 بیشتر از اشیاء 1 و 2 به هم شبیه‌اند. یک مثال از ماتریس مجاورت معمول برای است که در شکل 2-2 نشان داده شده است. یک گراف آستانه44، یک گراف غیر جهت‌دار و غیر وزن‌دار، روی گره، بدون حلقه بازگشت به خود45 یا چند لبه است. هر نود یک شیء را نمایش می‌دهد. یک گراف آستانه برای هر سطح عدم شباهت به این صورت تعریف می‌شود: اگر عدم شباهت اشیاء و از حد آستانه کوچک‌تر باشد، با واردکردن یک لبه بین نودهای ویک گراف آستانه تعریف می‌کنیم.
(2-1)if and only if
شکل 2-3 یک رابطه دودویی به دست آمده از ماتریس مربوط به شکل 2-2 را برای مقدار آستانه 5 نشان می‌دهد. نماد “*” در موقعیت ماتریس، نشان می‌دهد که جفت متعلق به رابطه دودویی می‌باشد. شکل 2-4، گراف‌های آستانه برای ماتریس را نمایش می‌دهد.
شکل 2-3. رابطه دودویی و گراف آستانه برای مقدار آستانه 5.
شکل 2-4. گراف‌های آستانه برای ماتریس
2-2-1-1-2. الگوریتم پیوندی منفرد
این الگوریتم روش کمینه و روش نزدیک‌ترین همسایه نیز نامیده می‌شود [26]. اگر و خوشه‌ها باشند، در روش پیوندی منفرد، فاصله آن‌ها برابر خواهد بود با:
(2-2)
که نشان‌دهنده فاصله (عدم شباهت) بین نقاط 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