पूर्ण-लिंकेज क्लस्टरिंग

For genetics, see Complete linkage

पूर्ण-सहलग्न गुच्छन संकुल पदानुक्रमिक गुच्छन की कई विधियों में से एक है। प्रक्रिया की शुरुआत में, प्रत्येक अवयव अपने स्वयं के गुच्छ में होते है। तब गुच्छों को क्रमानुसार बड़े गुच्छों में संयोजित किया जाता है जब तक कि सभी अवयव एक ही गुच्छ में न हो जाएं। इस विधि को सुदूर पड़ोसी गुच्छन के रूप में भी जाना जाता है। गुच्छन के परिणाम को डेंड्रोग्राम के रूप में देखा जा सकता है, जो गुच्छ फ्यूजन के अनुक्रम और प्रत्येक फ्यूजन की दूरी को दर्शाता है।

गुच्छन प्रक्रिया

प्रत्येक चरण में, लघुतम दूरी से अलग किए गए दो गुच्छों को संयोजित किया जाता है। 'लघुतम दूरी' की परिभाषा ही विभिन्न संकुलन गुच्छन विधियों के बीच अवकलन करती है। पूर्ण-सहलग्न गुच्छन में, दो गुच्छों के बीच के सहलग्‍न में सभी अवयव युग्म होते हैं, और गुच्छों के बीच की दूरी उन दो अवयवों (प्रत्येक गुच्छ में एक) के बीच की दूरी के बराबर होती है जो एक दूसरे से सबसे दूर हैं। इनमें से सबसे छोटा सहलग्‍न जो किसी भी चरण पर बना रहता है, उन दो गुच्छों के संलयन का कारण बनता है जिनके अवयव सम्मिलित होते हैं।

गणितीय रूप से, पूर्ण सहलग्न फलन - गुच्छों $X$ और $Y$ के बीच की दूरी D(X,Y) - निम्नलिखित व्यंजकों द्वारा वर्णित है:

$D(X,Y)=\max _{x\in X,y\in Y}d(x,y)$

जहां

• $d(x,y)$ अवयवों के बीच की दूरी $x\in X$ और $y\in Y$ है;
• $X$ और $Y$ अवयवों (गुच्छों) के दो समुच्चय हैं।

कलन विधि

सरल पद्धति

निम्नलिखित कलन विधि एक संकुलन गुच्छन पद्धति है जो सामीप्य आव्यूह में पंक्तियों और स्तंभों को मिटा देती है क्योंकि पुराने गुच्छ नए में विलयित हो जाते हैं। $N\times N$ सामीप्य आव्यूह D में सभी दूरियाँ d(i,j) सम्मिलित हैं। गुच्छनों को अनुक्रम संख्याएँ 0,1,......, (n − 1) समनुदिष्‍ट की गई है और L(k) kth गुच्छनों का स्तर है। अनुक्रम संख्या m वाले गुच्छ को (m) से दर्शाया गया है और गुच्छों (r) तथा (s) के बीच सामीप्य को d[(r),(s)] से दर्शाया गया है।

पूर्ण सहलग्न गुच्छन कलन विधि में निम्नलिखित चरण सम्मिलित हैं:

1. स्तर $L(0)=0$ और अनुक्रम संख्या $m=0$ वाले असंयुक्त गुच्छन से शुरू करें।
2. वर्तमान गुच्छन में गुच्छों के सबसे समान युग्म खोजे, युग्म $(r),(s)$ मान ले, $d[(r),(s)]=\min d[(i),(j)]$ के अनुसार जहां न्यूनतम वर्तमान गुच्छन में गुच्छों के सभी युग्मों पर है।
3. अनुक्रम संख्या बढ़ाएँ: $m=m+1$ | अगले गुच्छन $m$ बनाने के लिए गुच्छों $(r)$ और $(s)$ को एक गुच्छ में मिलाएं। इस गुच्छन का स्तर $L(m)=d[(r),(s)]$ पर समुच्चय करें|
4. गुच्छों $(r)$ और $(s)$ के अनुरूप पंक्तियों और स्तंभों को हटाकर और नवगठित गुच्छ के अनुरूप एक पंक्ति और स्तंभ जोड़कर सामीप्य आव्यूह, D को अद्यतन करें। नए गुच्छ, जिसे $(r,s)$ से दर्शाया गया है, और पुराने गुच्छ $(k)$ के बीच सामीप्य को इस प्रकार परिभाषित किया गया है
5. $d[(r,s),(k)]=\max\{d[(k),(r)],d[(k),(s)]\}$ |
6. यदि सभी वस्तुएं एक गुच्छ में हैं, तो रुकें। अन्यथा, चरण 2 पर जाएँ |

इष्टतम दक्ष पद्धति

ऊपर बताए गए एल्गोरिदम को समझना सरल है लेकिन सम्मिश्रता $O(n^{3})$ है| मई 1976 में, डी. डिफ़ेज़ ने केवल सम्मिश्रता $O(n^{2})$ का एक इष्टतम दक्ष एल्गोरिदम प्रस्तावित किया जिसे क्लीनक (प्रकाशित 1977) के रूप में जाना जाता है, जो एकल सहलग्न गुच्छन के लिए समान एल्गोरिदम स्लिंक से प्रेरित है।

कार्यकारी उदाहरण

कार्यकारी उदाहरण, पांच बैक्टीरियों के 5S राइबोसोमल RNA अनुक्रम संरेखण से गणना की गई JC69 आनुवंशिक दूरी आव्यूह पर आधारित है: बेसिलस सुबटिलिस ($a$), बैसिलस स्टीयरोथर्मोफिलस ($b$), वीसेल्ला विरिडेसेंस ($c$), अकोलेप्लाज्मा मोडिकम ($d$), और माइक्रोकॉकस ल्यूटस ($e$) |

पहला चरण

• पहला गुच्छन

आइए मान लें कि हमारे पास पाँच अवयव $(a,b,c,d,e)$ और उनके बीच युग्‍मानूसार दूरी का निम्नलिखित आव्यूह $D_{1}$ है:

	a	b	c	d	e
a	0	17	21	31	23
b	17	0	30	34	21
c	21	30	0	28	39
d	31	34	28	0	43
e	23	21	39	43	0

इस उदाहरण में, $D_{1}(a,b)=17$, $D_{1}$का सबसे छोटा मान है, इसलिए हम अवयवों $a$ और $b$ को जोड़ते हैं |

• पहले शाखा की लंबाई का आकलन

मान लीजिए $u$ उस नोड को दर्शाता है जिससे $a$ और $b$ अब जोड़ते हैं|$\delta (a,u)=\delta (b,u)=D_{1}(a,b)/2$ समुच्चयन करने से यह सुनिश्चित होता है कि अवयव $a$ और $b$, $u$ से समान दूरी पर हैं। यह अल्ट्रामेट्रीसिटी परिकल्पना की अपेक्षा से मेल खाता है। $a$ और $b$ को $u$ से जोड़ने वाली शाखाओं की लंबाई $\delta (a,u)=\delta (b,u)=17/2=8.5$ होती है (अंतिम डेंड्रोग्राम देखें)

• 'पहला दूरी आव्यूह अद्यतन'

फिर हम प्रारंभिक सामीप्य आव्यूह $D_{1}$ को एक नए सामीप्य आव्यूह $D_{2}$ (नीचे देखें) में अद्यतन करने के लिए आगे बढ़ते हैं, जिसका आकार $a$ साथ $b$ के गुच्छन कारण एक पंक्ति और एक कॉलम से कम हो गया है। $D_{2}$ में बोल्ड मान नई दूरियों के अनुरूप हैं, जिनकी गणना पहले गुच्छ के प्रत्येक अवयव $(a,b)$ और शेष प्रत्येक अवयव के बीच अधिकतम दूरी को बनाए रखकर की जाती है:

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

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

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

$D_{2}$ में इटालिक मान आव्यूह अद्यतन से प्रभावित नहीं होते हैं क्योंकि वे पहले गुच्छ में सम्मिलित नहीं होने वाले अवयवों के बीच की दूरी के अनुरूप होते हैं।

दूसरा चरण

• दूसरा गुच्छन

अब हम नए दूरी आव्यूह $D_{2}$से शुरू करते हुए, पिछले तीन चरणों को दोहराते हैं:

	(a,b)	c	d	e
(a,b)	0	30	34	23
c	30	0	28	39
d	34	28	0	43
e	23	39	43	0

यहाँ, $D_{2}((a,b),e)=23$ $D_{2}$का न्यूनतम मान है, इसलिए हम गुच्छ $(a,b)$ को अवयव $e$ के साथ जोड़ते हैं।

• दूसरी शाखा की लंबाई का आकलन

मान लीजिए $v$ उस नोड को दर्शाता है जिससे $(a,b)$ और $e$ अब जुड़े हुए हैं| अल्ट्रामेट्रिकिटी प्रतिबंध के कारण, $a$ या $b$ से $v$, तथा $e$ और $v$ को जोड़ने वाली शाखाएं बराबर होती हैं और उनकी कुल लंबाई निम्नलिखित होती है:$\delta (a,v)=\delta (b,v)=\delta (e,v)=23/2=11.5$

हम लुप्त शाखा की लंबाई निकालते हैं:$\delta (u,v)=\delta (e,v)-\delta (a,u)=\delta (e,v)-\delta (b,u)=11.5-8.5=3$ (अंतिम डेंड्रोग्राम देखें)

• दूसरी दूरी आव्यूह अद्यतन

फिर हम $D_{2}$ आव्यूह को एक नए दूरी आव्यूह में $D_{3}$ (नीचे देखें) में अघतन करने के लिए आगे बढ़ते हैं, जिसका आकार $e$ के साथ $(a,b)$ के गुच्छन के कारण एक पंक्ति और एक स्तम्भ से कम हो गया है:

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

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

तीसरा चरण

• तीसरा गुच्छन

हम अद्यतन दूरी आव्यूह $D_{3}$ से शुरू करते हुए, पिछले तीन चरणों को फिर से दोहराते हैं|

	((a,b),e)	c	d
((a,b),e)	0	39	43
c	39	0	28
d	43	28	0

यहाँ, $D_{3}(c,d)=28$ $D_{3}$ का सबसे छोटा मान है , इसलिए हम अवयवों को $c$ और $d$ से जोड़ते हैं|

• तीसरी शाखा की लंबाई का आकलन

मान लीजिए कि $w$ उस नोड को दर्शाता है जिससे $c$ और $d$ अब जुड़े हुए हैं। वह शाखाओं $c$ और $d$ को $w$ से जोड़ती हैं तो उनकी लंबाई $\delta (c,w)=\delta (d,w)=28/2=14$ होती है (अंतिम डेंड्रोग्राम देखें)

• तीसरी दूरी आव्यूह अद्यतन

अद्यतन करने के लिए एक ही प्रविष्टि है:$D_{4}((c,d),((a,b),e))=max(D_{3}(c,((a,b),e)),D_{3}(d,((a,b),e)))=max(39,43)=43$

अंतिम चरण

अंतिम $D_{4}$ आव्यूह है:

	((a,b),e)	(c,d)
((a,b),e)	0	43
(c,d)	43	0

इसलिए हम गुच्छों को $((a,b),e)$ और $(c,d)$ से जोड़ते हैं।

मान लीजिए $r$ उस (रूट) नोड को दर्शाता है जिससे $((a,b),e)$ और $(c,d)$ अब जुड़े हुए हैं| $((a,b),e)$ और $(c,d)$ को r से जोड़ने वाली शाखाओं की लंबाई होती है:

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

हम शेष दो शाखाओं की लंबाई निकालते हैं:

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

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

पूर्ण-सहलग्न डेंड्रोग्राम

डेंड्रोग्राम अब पूर्ण हो गया है। यह अल्ट्रामेट्रिक है क्योंकि यह सभी समांतराली ($a$ से $e$), $r$ से समान दूरी पर हैं:

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

इसलिए डेंड्रोग्राम को इसके सबसे गहरे नोड $r$ द्वारा रूट किया जाता है।

अन्य सहलग्नों के साथ तुलना

वैकल्पिक सहलग्न पद्धतियों में एकल सहलग्न गुच्छन और औसत सहलग्न गुच्छन सम्मिलित हैं - अनुभवहीन कलन विधि में एक अलग सहलग्न को लागू करना, सामीप्य आव्यूह की प्रारंभिक गणना और उपरोक्त कलन विधि के चरण 4 में अंतर-गुच्छ दूरी की गणना करने के लिए एक अलग सूत्र के उपयोग करने की स्थिति है। हालाँकि, स्वेच्छ सहलग्नों के लिए एक इष्टतम कुशल कलन विधि उपलब्ध नहीं है। जिस सूत्र को समायोजित किया जाना चाहिए उसे बोल्ड टेक्स्ट का उपयोग करके हाइलाइट किया गया है।

पूर्ण सहलग्न गुच्छन वैकल्पिक एकल सहलग्न गुच्छन विधि की कमी से बचाता है - तथाकथित शृंखलन परिघटना, जहां एकल सहलग्न गुच्छन के माध्यम से बने गुच्छों के एकल अवयवों को एक-दूसरे के सटीक होने के कारण एक साथ प्रणोदित किया जा सकता है, समान रूप से प्रत्येक गुच्छ में कई अवयव एक दूसरे से बहुत दूर हो सकते हैं। पूर्ण सहलग्न से लगभग समान व्यास के सघन (कॉम्पैक्ट) गुच्छ मिलते हैं।

समान दूरी आव्यूह से विभिन्न गुच्छन विधियों के अंतर्गत प्राप्त डेंड्रोग्राम की तुलना।

एकल-सहलग्न गुच्छन |	पूर्ण-सहलग्न गुच्छन |	औसत सहलग्न गुच्छन: डब्ल्यूपीजीएमए।	औसत सहलग्न गुच्छन: यूपीजीएमए |

यह भी देखें

• गुच्छ विश्लेषण
• पदानुक्रमिक गुच्छन
• आणविक कालद
• एकल-सहलग्न गुच्छन
• यूपीजीएमए
• डब्ल्यूपीजीएमए

अग्रिम पठन

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