خوشه‌بندی کامل پیوند
خوشه بندی کامل پیوند یکی از روش‌های مختلف خوشه‌بندی‌سلسله‌مراتبی است. در ابتدای فرایند، هر عنصر در خوشه ای از خود قرار دارد. سپس خوشه‌ها به صورت گروهی به گروه‌های بزرگتر تقسیم می‌شوند تا زمانی که تمام عناصر در خوشه قرار گیرند. این روش همچنین به عنوان دورترین خوشه همسایه نیز شناخته می‌شود. نتیجه خوشه بندی را می‌توان به عنوان یک دندروگرام تجسم کرد، که نشان می‌دهد که توالی خوشه‌های همجوشی و فاصله ای که در هر همجوشی اتفاق می‌افتد.
در هر مرحله، دو خوشه ای که توسط کوتاه‌ترین فاصله جدا می‌شوند ترکیب می‌شوند. تعریف «کوتاهترین فاصله» چیزی است که بین روشهای مختلف خوشه بندی زنجیرهای متفاوت است. در خوشه بندی پیوندی کامل، پیوند میان دو خوشه شامل تمام جفت‌های عنصر است و فاصله بین خوشه‌ها برابر فاصله بین دو عنصر (یکی در هر خوشه) است که دورتر از یکدیگر هستند. کوتاهترین این پیوندها که در هر مرحله باقی می‌مانند، موجب همپوشانی دو خوشه می‌شود که عناصر آن درگیر هستند. از نظر ریاضی تابع پیوند کامل — فاصله (D(X,Y بین خوشه X و Y — توسط عبارت روبه‌رو شرح داده شده‌است: formula_1
(d(x,y فاصله بین عناصر x عضو X و y عضو Y است.
X و Y دو مجموعه از عناصر (خوشه‌ها) هستند.
الگوریتم زیر یک تابع agglomerative است که ردیف‌ها و ستون‌ها را در یک ماتریس مجاورت پاک می‌کند و به عنوان خوشه‌های قدیمی به صورت‌های جدید ادغام می‌شوند. D ماتریس نزدیکی N در N، شامل تمام فاصله‌های (d(i,j. خوشه‌ها به شماره متوالی ۱، ۲، …، n اختصاص داده می‌شوند و (L(k، سطح kام خوشه‌بندی هست. یک خوشه با شماره متوالی m مشخص شده‌است و نزدیکی بین خوشه‌های (r) و (s) با [(d[(r),(s مشخص می‌شود.
الگوریتم از مراحل زیر تشکیل شده‌است:
۱.شروع خوشه بندی با در نظر گرفتن سطح L (0) = ۰ و شماره‌های متوالی m = ۰.
۲.یافتن جفت خوشه ای مشابه در خوشه بندی فعلی، مانند جفت‌های (r) و (s) که طبق اینکه [(d[(r),(s برابر [(max d[(i),(j است در جایی که بیش از همه جفت خوشه در خوشه فعلی است.
۳.افزایش شماره متوالی: m = m + 1 و خوشه‌های (r) و (s) را به یک خوشه واحد برای تشکیل خوشه بندی بعدی m بپیوندانید. سطح این خوشه بندی را به [(L(m) = d[(r),(s تنظیم کنید.
۴.به روز رسانی ماتریس مجاورت D، با حذف سطر و ستون مربوط به خوشه (r) و (s) و با اضافه کردن یک سطر و ستون مربوط به خوشه تازه شکل گرفته انجام می‌شود. نزدیکی بین خوشه جدید، نشان داده شده با (r, s) و خوشه قدیمی با (k) به عنوان [( d[("k"), ("r","s" )] = max "d"[("k"),("r")], "d"[("k"),("s است".
۵.اگر تمام اجسام در یک خوشه قرار داشته باشند، متوقف شوند و بعد به مرحله ۲ بروید.
الگوریتم توضیح داده شده در بالا آسان است اما پیچیدگی formula_2را دارد.در ماه مه ۱۹۷۶، D. Defays یک الگوریتم بهینه کارآمد با پیچیدگی formula_2پیشنهاد کرد که با عنوان شناخته شده به CLINK است (منتشر شده در سال 1977) و با الگوریتم SLINK الگوریتم مشابه برای خوشه‌بندی‌تک‌لینک است.
مثال عملی بر اساس ماتریس فاصله ژنتیکی JC69 محاسبه شده از 5S ribosomal RNA که تراز توالی پنج باکتری است محاسبه شده‌است: (Bacillus subtilis (a و (Bacillus stearothermophilus (b و (Lactobacillus viridescens (c و (Acholeplasma modicum (d و (Micrococcus luteus (e.فرض کنیم که ما پنج عنصر formula_4 و ماتریس formula_5 فاصله جفتی بین آنها است:
در این مثال، formula_6 کوچکترین مقدار formula_5هست، بنابراین ما به عناصر a و b می‌پیوندیم.
فرض کنید formula_8نشان دهنده گره ای است که به آن a و b وصل شده‌است. formula_9 تضمین می‌کند که عناصر formula_10 و formula_11 برابر formula_8 برابر است. این مربوط به انتظار از فرضیه ultrametricity است؛ بنابراین شاخه پیوستن formula_10و formula_11 به formula_8، formula_16طول دارد.
سپس ماتریس formula_5 ماتریس مجاورت ماتریس اولیه را در یک ماتریس مجاور جدید formula_18(به پایین نگاه کنید) به روز رسانی می‌کنیم، به دلیل خوشه بندی a با b، اندازه یک سطر و یک ستون کاهش می‌یابد. مقادیر پررنگ در formula_18 با فاصله‌های جدید مطابقت دارند، که با حفظ حداکثر فاصله بین هر عنصر خوشه اول formula_20و هر یک از عناصر باقی مانده محاسبه می‌شود:formula_21
formula_22
formula_23
ارزش خمیده در formula_18 با به روز رسانی ماتریس تحت تأثیر قرار نمی‌گیرند زمانی که آنها را به فاصله بین عناصر در خوشه اول درگیر نیست مطابقت دارد.اکنون ما سه مرحله قبلی را دوباره شروع می‌کنیم، از ماتریس فاصله جدید formula_25شروع می‌کنیم:
اینجا، formula_26پایین‌ترین مقدار formula_25را دارد، بنابراین به خوشه formula_28با عنصر formula_29می‌پیوندیم.
فرض کنید formula_8نشان دهنده گره ای است که به آن formula_31 و formula_29 وصل شده‌اند. به دلیل محدودیت ultraetricity، شاخه‌های پیوستن formula_33یا formula_34به formula_35 و formula_29 به formula_35، مساوی هستند و طول کل زیر را دارند:
formula_38
ما طول شاخه گمشده را می‌بینیم: formula_39
سپس در جهت به روز رسانی ماتریس formula_25ماتریس به یک ماتریس فاصله جدید formula_41 (پایین را ببینید) به روز رسانی می‌کنیم، در اندازه یک سطر و یک ستون به دلیل خوشه بندی formula_42با formula_29 کاهش می‌یابد:
formula_44
formula_45ما دوباره سه گام قبلی را، با شروع از ماتریس فاصله formula_46 به روز شده، تکرار می‌کنیم:
اینجا،formula_47کوچکترین مقدار ماتریس formula_46هست، بنابراین ما به عناصر c , d می‌پیوندیم.
فرض کنید formula_49نشان دهنده گره ای است که به formula_50و formula_51وصل شده‌است؛ بنابراین شاخه‌های formula_50و formula_51 به formula_49طول می‌پیوندند: formula_55
یک ورودی برای به روز رسانی وجود دارد: formula_56
ماتریس نهایی formula_57برابر است با:
بنابراین ما خوشه‌های formula_58 و formula_59 پیوند می‌دهیم.
فرض کنید formula_60(سر راس) نشان دهنده گره ای است که به formula_58 و formula_59 وصل شده‌است.
شاخه‌های پیوستگی formula_58 و formula_59به formula_60می‌پیوندند که دارای طول عبارت پایین هستند:
formula_66
ما دو طول شاخه باقی مانده را می‌بینیم:
formula_67
formula_68
این نمودار که اکنون کامل شده‌است، یک ultrametric است. به دلیل تمام رنوک‌های formula_69برابر با r است:
formula_70
این نمودار توسط r ریشه شده‌است، این گره عمیق‌ترین گره نمودار است.
طرح‌های جایگزین پیوند شامل خوشه بندی تک اتصال و خوشه بندی پیوند متوسط است - پیاده‌سازی پیوندهای مختلف در الگوریتم ساده است، صرفاً استفاده از فرمول‌های مختلف برای محاسبه فاصله بین خوشه ای در محاسبه اولیه ماتریس مجاورت و در مرحله ۴ از بالا الگوریتم است. یک الگوریتم بهینه کارآمد است با این حال برای ارتباط خودسرانه در دسترس نیست. فرمول که باید تنظیم شود با استفاده از متن جسور برجسته شده‌است.
خوشه بندی کامل پیوند، از روش پیوند تک جایگزین اجتناب می‌کند - پدیده به اصطلاح زنجیره ای، جایی که خوشه‌ها از طریق خوشه بندی پیوندی یکپارچه تشکیل داده‌اند، به دلیل اینکه عناصر مجاور نزدیک به یکدیگر هستند، حتی اگر بسیاری از عناصر در هر خوشه ممکن است بسیار دور از هم باشد. پیوند کامل برای یافتن خوشه‌های فشرده تقریباً یکسان است.