خوشه‌بندی تک‌پیوندی

خوشه‌بندی‌های تجمعی احتمالاً یکی از پرمصرف‌ترین روش‌های خوشه‌بندی سلسله‌مراتبی هستند. در این نوع از خوشه‌بندی‌ها هر داده‌ای در ابتدا خود یک خوشه، سپس به صورت پیاپی در هر مرحله دو خوشه با یک‌دیگر ادغام شده و خوشه‌ای بزرگ‌تر تشکیل می‌دهند و این روند ادامه پیدا می‌کند تا تنها یک خوشه باقی بماند. نتیجهٔ چنین خوشه‌بندی ای معمولاً به صورت یک دندروگرام نمایش داده می‌شود و با برش دندروگرام در سطحی دلخواه از میزان شباهت یک خوشه‌بندی ایجاد می‌شود.

تفاوت روش‌های مختلف خوشه‌بندی تجمعی در نحوه انتخاب شدن آن دو خوشه‌ای است که در هر مرحله برای ادغام شدن انتخاب می‌شوند. در خوشه‌بندی تک پیوندی فاصلهٔ دو خوشه را نزدیک‌ترین جفت داده (که هر کدام در یکی از خوشه‌ها باشد) تعیین می‌کند.

به صورت ریاضی تابع فاصله خوشه‌ها به شکل ${\displaystyle D(X,Y)=\underset{x\in X,y\in Y}{min}d(x,y)}$

در هر مرحله از این الگوریتم دو خوشه‌ای که کمترین فاصله را با یک‌دیگر دارند با هم ترکیب می‌شوند و فاصله خوشه حاصل از ادغام شدن ${\displaystyle X}$

${\displaystyle D(X\cup Y,Z)=min(D(X,Z),D(Y,Z))}$

این الگوریتم مانند الگوریتم روش جفت گروه بدون وزن با میانگین حسابی است که شبه کد آن در زیر آمده‌است:

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

فرض می‌کنیم ۵ داده ${\displaystyle (a,b,c,d,e)}$

نزدیک‌ترین خوشه‌ها (a) و (b) با فاصله ۲ هستند. این دو خوشه با یک دیگر ادغام کرده و خوشهٔ (u = (a, b حاصل می‌شود.

قرار می‌دهیم: ${\displaystyle \delta (u,a)=\delta (u,b)=0.5\times 2=1}$

فاصله خوشه جدید با خوشه‌های دیگر را به شکل زیر محاسبه می‌کنیم.

${\displaystyle D((a,b),c)=min(D(a,c),D(b,c))=5}$

${\displaystyle D((a,b),d)=min(D(a,d),D(b,d))=9}$

${\displaystyle D((a,b),e)=min(D(a,e),D(b,e))=8}$

ماتریس فاصله جدید(${\displaystyle D_2}$

حال نزدیک‌ترین خوشه‌ها (d) و (e) با فاصله ۳ هستند. این دو خوشه با یک دیگر ادغام کرده تا خوشهٔ (v = (d,e حاصل شود.

قرار می‌دهیم: ${\displaystyle \delta (v,d)=\delta (v,e)=0.5\times 3=1.5}$

فاصله خوشه جدید با خوشه‌های دیگر را به شکل زیر محاسبه می‌کنیم.

${\displaystyle D((d,e),c)=min(D(d,c),D(e,c))=4}$

${\displaystyle D((d,e),(a,b))=min(D(d,(a,b)),D(e,(a,b)))=8}$

ماتریس ${\displaystyle D_3}$

در این مرحله نزدیک‌ترین خوشه‌ها که با هم ترکیب می‌شوند خوشه‌های (c) و (d, e) به فاصلهٔ ۴ هستند و خوشه (w = (c, d, e از ترکیب‌شان به وجود می‌آید.

می‌دانیم ${\displaystyle \delta (w,c)=\delta (w,d)=\delta (w,e)=0.5\times 4=2}$

و هم چنین داریم ${\displaystyle D((c,(d,e)),(a,b))=min(D(c,(d,e)),D((d,e),(a,b)))=5}$

در نهایت نیز این دو خوشه باقیمانده با یک‌دیگر ادغام می‌شوند و خوشه (r = (a, b, c, d, e حاصل می‌شود.

می‌دانیم ${\displaystyle \delta (r,a)=\delta (r,b)=\delta (r,c)=\delta (r,d)=\delta (r,e)=0.5\times 5=2.5}$

دندروگرام حاصل به شکل زیر است: