موضوع مقاله: خوشه‌بندی کامل پیوند | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # خوشه‌بندی کامل پیوند | مقدمه: سپس خوشه‌ها به صورت گروهی به گروه‌های بزرگتر تقسیم می‌شوند تا زمانی که تمام عناصر در خوشه قرار گیرند. | ## بخش 1: خوشه‌بندی کامل پیوند | نتیجه خوشه بندی را می‌توان به عنوان یک دندروگرام تجسم کرد، که نشان می‌دهد که توالی خوشه‌های همجوشی و فاصله ای که در هر همجوشی اتفاق می‌افتد. روش خوشه بندی در هر مرحله، دو خوشه ای که توسط کوتاه‌ترین فاصله جدا می‌شوند ترکیب می‌شوند. تعریف «کوتاهترین فاصله» چیزی است که بین روشهای مختلف خوشه بندی زنجیرهای متفاوت است. در خوشه بندی پیوندی کامل، پیوند میان دو خوشه شامل تمام جفت‌های عنصر است و فاصله بین خوشه‌ها برابر فاصله بین دو عنصر (یکی در هر خوشه) است که دورتر از یکدیگر هستند. کوتاهترین این پیوندها که در هر مرحله باقی می‌مانند، موجب همپوشانی دو خوشه می‌شود که عناصر آن درگیر هستند. الگوریتم‌ها طرح نایاب الگوریتم زیر یک تابع agglomerative است که ردیف‌ها و ستون‌ها را در یک ماتریس مجاورت پاک می‌کند و به عنوان خوشه‌های قدیمی به صورت‌های جدید ادغام می‌شوند. خوشه‌ها به شماره متوالی ۱، ۲، …، n اختصاص داده می‌شوند و (L(k، سطح kام خوشه‌بندی هست. یک خوشه با شماره متوالی m مشخص شده‌است و نزدیکی بین خوشه‌های (r) و (s) با d r),(s مشخص می‌شود. | ## بخش 2: خوشه‌بندی کامل پیوند | الگوریتم از مراحل زیر تشکیل شده‌است: ۱.شروع خوشه بندی با در نظر گرفتن سطح L (0) = ۰ و شماره‌های متوالی m = ۰. ۲.یافتن جفت خوشه ای مشابه در خوشه بندی فعلی، مانند جفت‌های (r) و (s) که طبق اینکه d r),(s برابر max d i),(j است در جایی که بیش از همه جفت خوشه در خوشه فعلی است. ۳.افزایش شماره متوالی: m = m + 1 و خوشه‌های (r) و (s) را به یک خوشه واحد برای تشکیل خوشه بندی بعدی m بپیوندانید. ۴.به روز رسانی ماتریس مجاورت D، با حذف سطر و ستون مربوط به خوشه (r) و (s) و با اضافه کردن یک سطر و ستون مربوط به خوشه تازه شکل گرفته انجام می‌شود. ۵.اگر تمام اجسام در یک خوشه قرار داشته باشند، متوقف شوند و بعد به مرحله ۲ بروید. طرح مطلوب کارآمد الگوریتم توضیح داده شده در بالا آسان است اما پیچیدگی را دارد.در ماه مه ۱۹۷۶، D. گام اول خوشه اول فرض کنیم که ما پنج عنصر و ماتریس فاصله جفتی بین آنها است: +edcba۲۳۳۱۲۱۱۷۰a۲۱۳۴۳۰۰۱۷b۳۹۲۸۰۳۰۲۱c۴۳۰۲۸۳۴۳۱d۰۴۳۳۹۲۱۲۳e در این مثال، کوچکترین مقدار هست، بنابراین ما به عناصر a و b می‌پیوندیم. اولین بروزرسانی ماتریس فاصله سپس ماتریس ماتریس مجاورت ماتریس اولیه را در یک ماتریس مجاور جدید (به پایین نگاه کنید) به روز رسانی می‌کنیم، به دلیل خوشه بندی a با b، اندازه یک سطر و یک ستون کاهش می‌یابد. | ## بخش 3: خوشه‌بندی کامل پیوند | مقادیر پررنگ در با فاصله‌های جدید مطابقت دارند، که با حفظ حداکثر فاصله بین هر عنصر خوشه اول و هر یک از عناصر باقی مانده محاسبه می‌شود: ارزش خمیده در با به روز رسانی ماتریس تحت تأثیر قرار نمی‌گیرند زمانی که آنها را به فاصله بین عناصر در خوشه اول درگیر نیست مطابقت دارد. گام دوم خوشه دوم اکنون ما سه مرحله قبلی را دوباره شروع می‌کنیم، از ماتریس فاصله جدید شروع می‌کنیم: +edc(a,b)۲۳۳۴۳۰۰(a,b)۳۹۲۸۰۳۰c۴۳۰۲۸۳۴d۰۴۳۳۹۲۳e اینجا، پایین‌ترین مقدار را دارد، بنابراین به خوشه با عنصر می‌پیوندیم. به دلیل محدودیت ultraetricity، شاخه‌های پیوستن یا به و به ، مساوی هستند و طول کل زیر را دارند: ما طول شاخه گمشده را می‌بینیم: به روز رسانی دوم ماتریس فاصله سپس در جهت به روز رسانی ماتریس ماتریس به یک ماتریس فاصله جدید (پایین را ببینید) به روز رسانی می‌کنیم، در اندازه یک سطر و یک ستون به دلیل خوشه بندی با کاهش می‌یابد: گام سوم خوشه سوم ما دوباره سه گام قبلی را، با شروع از ماتریس فاصله به روز شده، تکرار می‌کنیم: +dc(a,b),e ۴۳۳۹۰(a,b),e ۲۸۰۳۹c۰۲۸۴۳d اینجا،کوچکترین مقدار ماتریس هست، بنابراین ما به عناصر c , d می‌پیوندیم. ارزیابی طول شاخه سوم فرض کنید نشان دهنده گره ای است که به و وصل شده‌است؛ بنابراین شاخه‌های و به طول می‌پیوندند: به روز رسانی سوم ماتریس فاصله یک ورودی برای به روز رسانی وجود دارد: گام نهایی ماتریس نهایی برابر است با: +(c,d a,b),e ۴۳۰(a,b),e ۰۴۳(c,d) بنابراین ما خوشه‌های و پیوند می‌دهیم. به دلیل تمام رنوک‌های برابر با r است: این نمودار توسط r ریشه شده‌است، این گره عمیق‌ترین گره نمودار است. مقایسه با دیگر پیوندها طرح‌های جایگزین پیوند شامل خوشه بندی تک اتصال و خوشه بندی پیوند متوسط است - پیاده‌سازی پیوندهای مختلف در الگوریتم ساده است، صرفاً استفاده از فرمول‌های مختلف برای محاسبه فاصله بین خوشه ای در محاسبه اولیه ماتریس مجاورت و در مرحله ۴ از بالا الگوریتم است. | ## جمع‌بندی | خوشه بندی کامل پیوند، از روش پیوند تک جایگزین اجتناب می‌کند - پدیده به اصطلاح زنجیره ای، جایی که خوشه‌ها از طریق خوشه بندی پیوندی یکپارچه تشکیل داده‌اند، به دلیل اینکه عناصر مجاور نزدیک به یکدیگر هستند، حتی اگر بسیاری از عناصر در هر خوشه ممکن است بسیار دور از هم باشد.