خوشه‌بندی کامل پیوند

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

روش خوشه بندی

در هر مرحله، دو خوشه ای که توسط کوتاه‌ترین فاصله جدا می‌شوند ترکیب می‌شوند. تعریف «کوتاهترین فاصله» چیزی است که بین روشهای مختلف خوشه بندی زنجیرهای متفاوت است. در خوشه بندی پیوندی کامل، پیوند میان دو خوشه شامل تمام جفت‌های عنصر است و فاصله بین خوشه‌ها برابر فاصله بین دو عنصر (یکی در هر خوشه) است که دورتر از یکدیگر هستند. کوتاهترین این پیوندها که در هر مرحله باقی می‌مانند، موجب همپوشانی دو خوشه می‌شود که عناصر آن درگیر هستند. از نظر ریاضی تابع پیوند کامل — فاصله (D(X,Y بین خوشه X و Y — توسط عبارت روبه‌رو شرح داده شده‌است: $D(X,Y)=\max _{x\in X,y\in Y}d(x,y)$

(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 است.

۵.اگر تمام اجسام در یک خوشه قرار داشته باشند، متوقف شوند و بعد به مرحله ۲ بروید.

طرح مطلوب کارآمد

الگوریتم توضیح داده شده در بالا آسان است اما پیچیدگی $O(n^{3})$

را دارد.در ماه مه ۱۹۷۶، D. Defays یک الگوریتم بهینه کارآمد با پیچیدگی

O(n^{3})

پیشنهاد کرد که با عنوان شناخته شده به CLINK است (منتشر شده در سال 1977) و با الگوریتم SLINK الگوریتم مشابه برای خوشه‌بندی‌تک‌لینک است.

مثال عملی

مثال عملی بر اساس ماتریس فاصله ژنتیکی JC69 محاسبه شده از 5S ribosomal RNA که تراز توالی پنج باکتری است محاسبه شده‌است: (Bacillus subtilis (a و (Bacillus stearothermophilus (b و (Lactobacillus viridescens (c و (Acholeplasma modicum (d و (Micrococcus luteus (e.

گام اول

خوشه اول

فرض کنیم که ما پنج عنصر $(a,b,c,d,e)$

و ماتریس

D_{1}

فاصله جفتی بین آنها است:


e	d	c	b	a
۲۳	۳۱	۲۱	۱۷	۰	a
۲۱	۳۴	۳۰	۰	۱۷	b
۳۹	۲۸	۰	۳۰	۲۱	c
۴۳	۰	۲۸	۳۴	۳۱	d
۰	۴۳	۳۹	۲۱	۲۳	e

در این مثال، ${\displaystyle D_{1}(a,b)=17}$

کوچکترین مقدار

D_{1}

هست، بنابراین ما به عناصر a و b می‌پیوندیم.

ارزیابی طول شاخه اول

فرض کنید $u$

نشان دهنده گره ای است که به آن a و b وصل شده‌است.

\delta (a,u)=\delta (b,u)=D1(a,b)/2

تضمین می‌کند که عناصر

a

و

b

برابر

u

برابر است. این مربوط به انتظار از فرضیه ultrametricity است؛ بنابراین شاخه پیوستن

a

و

b

به

u

،

\delta (a,u)=\delta (b,u)=17/2=8.5

طول دارد.

اولین بروزرسانی ماتریس فاصله

سپس ماتریس $D_{1}$

ماتریس مجاورت ماتریس اولیه را در یک ماتریس مجاور جدید

D_{2}

(به پایین نگاه کنید) به روز رسانی می‌کنیم، به دلیل خوشه بندی a با b، اندازه یک سطر و یک ستون کاهش می‌یابد. مقادیر پررنگ در

D_{2}

با فاصله‌های جدید مطابقت دارند، که با حفظ حداکثر فاصله بین هر عنصر خوشه اول

(a,b)

و هر یک از عناصر باقی مانده محاسبه می‌شود:

{\displaystyle D_{2}((a,b),c)=max(D_{1}(a,c),D_{1}(b,c))=max(21,30)=30}

${\displaystyle D_{2}((a,b),d)=max(D_{1}(a,d),D_{1}(b,d))=max(31,34)=34}$

${\displaystyle D_{2}((a,b),e)=max(D_{1}(a,e),D_{1}(b,e))=max(23,21)=23}$

ارزش خمیده در $D_{2}$

با به روز رسانی ماتریس تحت تأثیر قرار نمی‌گیرند زمانی که آنها را به فاصله بین عناصر در خوشه اول درگیر نیست مطابقت دارد.

گام دوم

خوشه دوم

اکنون ما سه مرحله قبلی را دوباره شروع می‌کنیم، از ماتریس فاصله جدید ${\displaystyle D_{2}}$

شروع می‌کنیم:


e	d	c	(a,b)
۲۳	۳۴	۳۰	۰	(a,b)
۳۹	۲۸	۰	۳۰	c
۴۳	۰	۲۸	۳۴	d
۰	۴۳	۳۹	۲۳	e

اینجا، ${\displaystyle D_{2}((a,b),e)=23}$

پایین‌ترین مقدار

{\displaystyle D_{2}}

را دارد، بنابراین به خوشه

{\displaystyle (a,b)}

با عنصر

{\displaystyle e}

می‌پیوندیم.

ارزیابی طول شاخه دوم

فرض کنید $u$

نشان دهنده گره ای است که به آن

{\displaystyle (a,b)}

و

{\displaystyle e}

وصل شده‌اند. به دلیل محدودیت ultraetricity، شاخه‌های پیوستن

{\displaystyle a}

یا

{\displaystyle b}

به

{\displaystyle v}

و

{\displaystyle e}

به

{\displaystyle v}

، مساوی هستند و طول کل زیر را دارند:

${\displaystyle \delta (a,v)=\delta (b,v)=\delta (e,v)=23/2=11.5}$

ما طول شاخه گمشده را می‌بینیم: ${\displaystyle \delta (u,v)=\delta (e,v)-\delta (a,u)=\delta (e,v)-\delta (b,u)=11.5-8.5=3}$

به روز رسانی دوم ماتریس فاصله

سپس در جهت به روز رسانی ماتریس ${\displaystyle D_{2}}$

ماتریس به یک ماتریس فاصله جدید

{\displaystyle D_{3}}

(پایین را ببینید) به روز رسانی می‌کنیم، در اندازه یک سطر و یک ستون به دلیل خوشه بندی

{\displaystyle (a,b)}

با

{\displaystyle e}

کاهش می‌یابد:

${\displaystyle D_{3}(((a,b),e),c)=max(D_{2}((a,b),c),D_{2}(e,c))=max(30,39)=39}$

${\displaystyle D_{3}(((a,b),e),d)=max(D_{2}((a,b),d),D_{2}(e,d))=max(34,43)=43}$

گام سوم

خوشه سوم

ما دوباره سه گام قبلی را، با شروع از ماتریس فاصله $D_{3}$

به روز شده، تکرار می‌کنیم:


d	c	(a,b),e))
۴۳	۳۹	۰	(a,b),e))
۲۸	۰	۳۹	c
۰	۲۸	۴۳	d

اینجا، ${\displaystyle D_{3}(c,d)=28}$

کوچکترین مقدار ماتریس

D_{3}

هست، بنابراین ما به عناصر c , d می‌پیوندیم.

ارزیابی طول شاخه سوم

فرض کنید $w$

نشان دهنده گره ای است که به

c

و

d

وصل شده‌است؛ بنابراین شاخه‌های

c

و

d

به

w

طول می‌پیوندند:

{\displaystyle \delta (c,w)=\delta (d,w)=28/2=14}

به روز رسانی سوم ماتریس فاصله

یک ورودی برای به روز رسانی وجود دارد: ${\displaystyle D_{4}((c,d),((a,b),e))=(D_{3}(c,((a,b),e)),D_{3}(d,((a,b),e)))=(39,43)=43}$

گام نهایی

ماتریس نهایی $D_{4}$

برابر است با:


(c,d)	(a,b),e))
۴۳	۰	(a,b),e))
۰	۴۳	(c,d)

بنابراین ما خوشه‌های ${\displaystyle ((a,b),e)}$

و

{\displaystyle (c,d)}

پیوند می‌دهیم.

فرض کنید $r$

(سر راس) نشان دهنده گره ای است که به

{\displaystyle ((a,b),e)}

و

{\displaystyle (c,d)}

وصل شده‌است.

شاخه‌های پیوستگی ${\displaystyle ((a,b),e)}$

و

{\displaystyle (c,d)}

به

r

می‌پیوندند که دارای طول عبارت پایین هستند:

${\displaystyle \delta (((a,b),e),r)=\delta ((c,d),r)=43/2=21.5}$

ما دو طول شاخه باقی مانده را می‌بینیم:

${\displaystyle \delta (v,r)=\delta (((a,b),e),r)-\delta (e,v)=21.5-11.5=10}$

${\displaystyle \delta (w,r)=\delta ((c,d),r)-\delta (c,w)=21.5-14=7.5}$

نمودار پیوند کامل

این نمودار که اکنون کامل شده‌است، یک ultrametric است. به دلیل تمام رنوک‌های $({\displaystyle a},{\displaystyle e})$

برابر با r است:

${\displaystyle \delta (a,r)=\delta (b,r)=\delta (e,r)=\delta (c,r)=\delta (d,r)=21.5}$

این نمودار توسط r ریشه شده‌است، این گره عمیق‌ترین گره نمودار است.

مقایسه با دیگر پیوندها

طرح‌های جایگزین پیوند شامل خوشه بندی تک اتصال و خوشه بندی پیوند متوسط است - پیاده‌سازی پیوندهای مختلف در الگوریتم ساده است، صرفاً استفاده از فرمول‌های مختلف برای محاسبه فاصله بین خوشه ای در محاسبه اولیه ماتریس مجاورت و در مرحله ۴ از بالا الگوریتم است. یک الگوریتم بهینه کارآمد است با این حال برای ارتباط خودسرانه در دسترس نیست. فرمول که باید تنظیم شود با استفاده از متن جسور برجسته شده‌است.

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

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

خوشه بندی تک لینک	خوشه بندی پیوند کامل	خوشه بندی میانگین اتصال: WPGMA	خوشه بندی میانگین اتصال: UPGMA

جستارهای وابسته

منابع

↑ Sorensen T (1948). "A method of establishing groups of equal amplitude in plant sociology based on similarity of species and its application to analyses of the vegetation on Danish commons". Biologiske Skrifter. 5: 1–34.
↑ Legendre P, Legendre L (1998). Numerical Ecology (Second English ed.). p. 853.
↑ Everitt, Brian S.; Landau, Sabine; Leese, Morven (2001). Cluster Analysis (Fourth ed.). London: Arnold. ISBN 0-340-76119-9. ;
↑ Defays D (1977). "An efficient algorithm for a complete link method" (PDF). The Computer Journal. British Computer Society. 20 (4): 364–366. doi:10.1093/comjnl/20.4.364.
↑ Erdmann VA, Wolters J (1986). "Collection of published 5S, 5.8S and 4.5S ribosomal RNA sequences". Nucleic Acids Research. 14 Suppl (Suppl): r1-59. PMC 341310. PMID 2422630.
↑ Olsen GJ (1988). "Phylogenetic analysis using ribosomal RNA". Methods in Enzymology. 164: 793–812. PMID 3241556.
↑ Everitt, Landau and Leese (2001), pp. 62-64.

برای مطالعهٔ بیشتر

Späth H (1980). Cluster Analysis Algorithms. Chichester: Ellis Horwood.

[1] Sorensen T (1948). "A method of establishing groups of equal amplitude in plant sociology based on similarity of species and its application to analyses of the vegetation on Danish commons". Biologiske Skrifter. 5: 1–34.

[2] Legendre P, Legendre L (1998). Numerical Ecology (Second English ed.). p. 853.

[3] Everitt, Brian S.; Landau, Sabine; Leese, Morven (2001). Cluster Analysis (Fourth ed.). London: Arnold. ISBN 0-340-76119-9. ;

[4] Defays D (1977). "An efficient algorithm for a complete link method" (PDF). The Computer Journal. British Computer Society. 20 (4): 364–366. doi:10.1093/comjnl/20.4.364.

[Erdmann1986-5] Erdmann VA, Wolters J (1986). "Collection of published 5S, 5.8S and 4.5S ribosomal RNA sequences". Nucleic Acids Research. 14 Suppl (Suppl): r1-59. PMC 341310. PMID 2422630.

[Olsen1988-6] Olsen GJ (1988). "Phylogenetic analysis using ribosomal RNA". Methods in Enzymology. 164: 793–812. PMID 3241556.

[7] Everitt, Landau and Leese (2001), pp. 62-64.