خوشه‌بندی تک‌پیوندی کیست؟ توضیح بده.
خوشه‌بندی تک‌پیوندی یکی از روش‌های خوشه‌بندی سلسله‌مراتبی است که با رویکرد از پایین به بالا یک سلسله‌مراتب از خوشه‌ها ایجاد می‌کند. خوشه‌بندی تجمعی که به نام "تکنیک نزدیک‌ترین همسایه" نیز شناخته می‌شود برای اولین بار در سال ۱۹۵۱ توسط فلورک مطرح شد. مبنای کار این روش آن است که در هر مرحله از اجرا، دو خوشه‌ای که کمترین فاصله از یک‌دیگر را دارند با هم ادغام می‌کند و فاصلهٔ یک خوشه از خوشه‌ای دیگر برابر با کمترین فاصله از هر یک از اعضای آن خوشه با هر یک از اعضای خوشه دیگر تعریف می‌شود.یکی از معایب این روش نسبت به خوشه‌بندی کامل پیوند آن است که خوشه‌بندی کامل پیوند خوشه‌های منسجم‌تری به وجود می‌آورد درحالی که در روش خوشه بندی تک‌پیوندی تعداد کمی داده که با فاصله اندک از یک‌دیگر که به شکل یک پل بین دو خوشه قرار داشته باشند موجب ادغام شدن آن دو خوشه می‌شوند و این خاصیت «اثر زنجیره‌ای» نامیده می‌شود. اما یکی از مزایای این روش تطبیق‌پذیری بیشتر آن و حفظ کارایی خود روی مجموعه داده‌های مختلف است.تعریف.خوشه‌بندی‌های تجمعی احتمالاً یکی از پرمصرف‌ترین روش‌های خوشه‌بندی سلسله‌مراتبی هستند. در این نوع از خوشه‌بندی‌ها هر داده‌ای در ابتدا خود یک خوشه، سپس به صورت پیاپی در هر مرحله دو خوشه با یک‌دیگر ادغام شده و خوشه‌ای بزرگ‌تر تشکیل می‌دهند و این روند ادامه پیدا می‌کند تا تنها یک خوشه باقی بماند. نتیجهٔ چنین خوشه‌بندی ای معمولاً به صورت یک دندروگرام نمایش داده می‌شود و با برش دندروگرام در سطحی دلخواه از میزان شباهت یک خوشه‌بندی ایجاد می‌شود.تفاوت روش‌های مختلف خوشه‌بندی تجمعی در نحوه انتخاب شدن آن دو خوشه‌ای است که در هر مرحله برای ادغام شدن انتخاب می‌شوند. در خوشه‌بندی تک پیوندی فاصلهٔ دو خوشه را نزدیک‌ترین جفت داده (که هر کدام در یکی از خوشه‌ها باشد) تعیین می‌کند.به صورت ریاضی تابع فاصله خوشه‌ها به شکل formula_1 تعریف می‌شود که formula_2 و formula_3 خوشه‌ها و formula_4 فاصله دو داده formula_5 و formula_6 را نمایش می‌دهد.در هر مرحله از این الگوریتم دو خوشه‌ای که کمترین فاصله را با یک‌دیگر دارند با هم ترکیب می‌شوند و فاصله خوشه حاصل از ادغام شدن formula_2 و formula_3 و خوشه دیگر formula_9 به صورت زیر محاسبه می‌شود:formula_10الگوریتم.این الگوریتم مانند الگوریتم روش جفت گروه بدون وزن با میانگین حسابی است که شبه کد آن در زیر آمده‌است:Single-Linkage(D, n) Clusters ← n single-element clusters labeled 1, ... , n construct a graph T with n isolated nodes labeled by single elements 1, ... , n for every node v in T Age(v) ← 0 while there is more than one cluster find the two closest clusters Ci and Cj merge Ci and Cj into a new cluster Cnew with |Ci| + |Cj| elements add a new node labeled by cluster Cnew to T connect node Cnew to Ci and Cj by directed edges Age(Cnew) ← D(Ci, Cj) / 2 remove the rows and columns of D corresponding to Ci and Cj remove Ci and Cj from Clusters add a row and column to D for Cnew by computing D(Cnew, C) for each C in Clusters add Cnew to Clusters root ← the node in T corresponding to the remaining cluster for each edge (v, w) in T length of (v, w) ← Age(v) - Age(w) return Tمثال.فرض می‌کنیم ۵ داده formula_11 با ماتریس فاصله formula_12 داریم.نزدیک‌ترین خوشه‌ها (a) و (b) با فاصله ۲ هستند. این دو خوشه با یک دیگر ادغام کرده و خوشهٔ (u = (a, b حاصل می‌شود.قرار می‌دهیم: formula_13فاصله خوشه جدید با خوشه‌های دیگر را به شکل زیر محاسبه می‌کنیم.formula_14formula_15formula_16ماتریس فاصله جدید(formula_17) را با حذف سطر و ستون‌های مربوط به خوشه‌های (a) و (b) از formula_12 و اضافه کردن سطر و ستون متناظر با خوشه (a, b) به دست می‌آوریم.حال نزدیک‌ترین خوشه‌ها (d) و (e) با فاصله ۳ هستند. این دو خوشه با یک دیگر ادغام کرده تا خوشهٔ (v = (d,e حاصل شود.قرار می‌دهیم: formula_19فاصله خوشه جدید با خوشه‌های دیگر را به شکل زیر محاسبه می‌کنیم.formula_20formula_21ماتریس formula_22 به شکل زیر خواهد شد:در این مرحله نزدیک‌ترین خوشه‌ها که با هم ترکیب می‌شوند خوشه‌های (c) و (d, e) به فاصلهٔ ۴ هستند و خوشه (w = (c, d, e از ترکیب‌شان به وجود می‌آید.می‌دانیم formula_23 بنابراین formula_24و هم چنین داریم formula_25 و ماتریس formula_22 به شکل زیر خواهد شد:در نهایت نیز این دو خوشه باقیمانده با یک‌دیگر ادغام می‌شوند و خوشه (r = (a, b, c, d, e حاصل می‌شود.می‌دانیم formula_27 پس formula_28 و formula_29دندروگرام حاصل به شکل زیر است: