एचसीएस क्लस्टरिंग एल्गोरिदम
| Class | Cluster analysis (on a similarity graph) |
|---|---|
| Data structure | Graph |
| Worst-case performance | O(2N x f(n,m)) |
एचसीएस (अत्यधिक कनेक्टेड उपग्राफ) क्लस्टरिंग एल्गोरिदम[1] (एचसीएस एल्गोरिदम के रूप में भी जाना जाता है, और अन्य नाम जैसे हाईली कनेक्टेड क्लस्टर/कंपोनेंट्स/कर्नेल) क्लस्टर विश्लेषण के लिए ग्राफ़ कनेक्टिविटी पर आधारित एल्गोरिदम है। यह समानता ग्राफ में समानता डेटा का प्रतिनिधित्व करके और फिर सभी अत्यधिक जुड़े उपग्राफ़ों को ढूंढकर काम करता है। यह समूहों की संख्या पर कोई पूर्व धारणा नहीं बनाता है। यह एल्गोरिदम 2000 में इरेज़ हार्टुव और रॉन शमीर द्वारा प्रकाशित किया गया था।
एचसीएस एल्गोरिदम क्लस्टरिंग समाधान देता है, जो एप्लिकेशन डोमेन में स्वाभाविक रूप से सार्थक है, क्योंकि प्रत्येक समाधान क्लस्टर का व्यास 2 होना चाहिए जबकि दो समाधान क्लस्टर के मिलन का व्यास 3 होगा।
समानता मॉडलिंग और प्रीप्रोसेसिंग
क्लस्टर विश्लेषण का लक्ष्य तत्वों के बीच समानता के आधार पर तत्वों को अलग-अलग उपसमूहों या समूहों में समूहित करना है, जिससे एक ही क्लस्टर में तत्व एक-दूसरे के समान (समरूपता) हों, जबकि विभिन्न समूहों के तत्वों में एक-दूसरे के प्रति कम समानता हो। (पृथक्करण) समानता ग्राफ़ तत्वों के बीच समानता का प्रतिनिधित्व करने वाले मॉडलों में से एक है, और बदले में क्लस्टर बनाने की सुविधा प्रदान करता है। समान डेटा से एक समान ग्राफ बनाने के लिए, तत्वों को शीर्षों के रूप में प्रस्तुत करें, और शीर्षों के बीच किनारों को प्राप्त करें जब उनके बीच समानता मान कुछ सीमा से ऊपर हो।
एल्गोरिथम
समानता ग्राफ में, दिए गए शीर्षों की संख्या के लिए जितने अधिक किनारे उपस्थित होते हैं, शीर्षों का ऐसा सेट एक दूसरे के बीच उतना ही अधिक समान होता है। दूसरे शब्दों में, यदि हम किनारों को हटाकर समानता ग्राफ़ को अलग करने का प्रयास करते हैं, तो ग्राफ़ के डिस्कनेक्ट होने से पहले हमें जितने अधिक किनारों को हटाने की आवश्यकता होगी, इस ग्राफ़ में शीर्ष उतने ही अधिक समान होंगे। न्यूनतम कट किनारों का न्यूनतम सेट है जिसके बिना ग्राफ़ डिस्कनेक्ट हो जाएगा।
एचसीएस क्लस्टरिंग एल्गोरिदम n शीर्षों वाले सभी उपग्राफ को ऐसे ढूंढता है कि उन उपग्राफ के न्यूनतम कट में n/2 से अधिक किनारे होते हैं, और उन्हें क्लस्टर के रूप में पहचानता है। ऐसे उपग्राफ को अत्यधिक कनेक्टेड उपग्राफ (एचसीएस) कहा जाता है। एकल शीर्षों को क्लस्टर नहीं माना जाता है और उन्हें सिंगलटन सेट s में समूहीकृत किया जाता है।
समानता ग्राफ G(V,E) को देखते हुए, एचसीएस क्लस्टरिंग एल्गोरिदम जांच करेगा कि क्या यह पहले से ही अत्यधिक कनेक्टेड है, यदि हां, तो G लौटाता है, अन्यथा G के न्यूनतम कट का उपयोग G को दो उपग्राफ H और H' 'में विभाजित करने के लिए करता है, और पुनरावर्ती रूप से चलाता है। H और H' पर एचसीएस क्लस्टरिंग एल्गोरिदम है।
उदाहरण
निम्नलिखित एनीमेशन दिखाता है कि कैसे एचसीएस क्लस्टरिंग एल्गोरिदम समानता ग्राफ को तीन समूहों में विभाजित करता है।
स्यूडोकोड
function HCS(G(V, E)) is
if G is highly connected then
return (G)
else
(H1, H2, C) ← MINIMUMCUT(G)
HCS(H1)
HCS(H2)
end if
end function
ग्राफ़ पर न्यूनतम कट ज्ञात करने का चरण G सबरूटीन है जिसे इस समस्या के लिए विभिन्न एल्गोरिदम का उपयोग करके कार्यान्वित किया जा सकता है। रैंडमाइजेशन का उपयोग करके न्यूनतम कट खोजने के लिए उदाहरण एल्गोरिथ्म के लिए नीचे देखें।
जटिलता
एचसीएस क्लस्टरिंग एल्गोरिदम का चलने का समय सीमित है। N × f(n, m). f(n, m) शीर्षों और m किनारों वाले ग्राफ़ में न्यूनतम कट की गणना करने की समय जटिलता है, और N पाए गए समूहों की संख्या है। कई अनुप्रयोगों में N << n है।
बिना भारित ग्राफ़ में न्यूनतम कट खोजने के लिए तेज़ एल्गोरिदम के लिए:
गुणों का प्रमाण
एचसीएस क्लस्टरिंग एल्गोरिदम द्वारा उत्पादित क्लस्टर में कई गुण होते हैं, जो समाधान की एकरूपता और पृथक्करण को प्रदर्शित कर सकते हैं।
प्रमेय 1 प्रत्येक अत्यधिक जुड़े ग्राफ का व्यास अधिकतम दो है।
प्रमाण: मान लीजिए n=|G|। यदि G का शीर्ष x डिग्री <= n/2 के साथ है, तो G के पास न्यूनतम कट है (जो x को अलग करता है) किनारों <= n/2 के साथ, इसलिए G अत्यधिक कनेक्टेड नहीं है। इसलिए यदि G अत्यधिक कनेक्टेड है, तो प्रत्येक शीर्ष पर डिग्री >= n/2 है। ग्राफ सिद्धांत में प्रसिद्ध प्रमेय है जो कहता है कि यदि प्रत्येक शीर्ष की डिग्री >= n/2 है, तो G का व्यास (किसी भी दो नोड्स के बीच सबसे लंबा पथ) <= 2 है।
प्रमेय 2 (a) अत्यधिक जुड़े ग्राफ में किनारों की संख्या द्विघात है। (b) एचसीएस एल्गोरिथ्म के प्रत्येक पुनरावृत्ति द्वारा हटाए गए किनारों की संख्या अधिकतम रैखिक है।
प्रमाण: (a) प्रमेय 1 से हम जानते हैं कि प्रत्येक शीर्ष की डिग्री >=n/2 है। इसलिए, अत्यधिक जुड़े ग्राफ़ में किनारों की संख्या कम से कम (n × n/2)/2 होनी चाहिए, जहां हम प्रत्येक शीर्ष की डिग्री का योग करते हैं और 2 से विभाजित करते हैं।
(b) परिभाषा के अनुसार, प्रत्येक पुनरावृत्ति <= n/2 किनारों के साथ न्यूनतम कटौती हटाती है।
प्रमेय 1 और 2a अंतिम क्लस्टर की एकरूपता का दृढ संकेत प्रदान करते हैं। बेहतर करना उस स्थितियों तक पहुंचता है जहां क्लस्टर के सभी कोने जुड़े हुए हैं, जो बहुत कठोर है और क्लिक समस्या NP-हार्ड भी है।
प्रमेय 2b अलगाव को इंगित करता है क्योंकि किन्हीं दो अंतिम समूहों c1 और c2 को तब तक अलग नहीं किया जा सकता था जब तक कि उनके बीच अधिकतम O(C1+C2) किनारे न हों (क्लस्टर के अन्दर द्विघात किनारों के विपरीत) है।
विविधताएं
सिंगलटन को अपनाना: प्रारंभिक क्लस्टरिंग प्रक्रिया द्वारा सिंगलटन के रूप में छोड़े गए तत्वों को क्लस्टर की समानता के आधार पर क्लस्टर द्वारा अपनाया जा सकता है। यदि किसी विशिष्ट क्लस्टर में पड़ोसियों की अधिकतम संख्या अत्यधिक बड़ी है, तो इसे उस क्लस्टर में जोड़ा जा सकता है।
निम्न डिग्री शीर्षों को हटाना: जब इनपुट ग्राफ़ में कम डिग्री वाले शीर्ष होते हैं, तो यह एल्गोरिदम चलाने के योग्य नहीं है क्योंकि यह कम्प्यूटेशनल रूप से बहुमूल्य है और सूचनात्मक नहीं है। वैकल्पिक रूप से, एल्गोरिदम का परिशोधन पहले निश्चित सीमा से कम डिग्री वाले सभी शीर्षों को हटा सकता है।
एचसीएस उपयोग के उदाहरण
- जीन अभिव्यक्ति विश्लेषण[2] सरणीकृत सीडीएनए में सिंथेटिक ऑलिगोन्यूक्लियोटाइड्स का संकरण प्रत्येक सीडीएनए क्लोन के लिए फिंगरप्रिंट उत्पन्न करता है। इन उंगलियों के चिन्ह पर एचसीएस एल्गोरिदम चलाकर एक ही जीन के अनुरूप क्लोन की पहचान की जा सकती है।
- पीपीआई नेटवर्क संरचना खोज[3] पीपीआई में घने उप-नेटवर्क का पता लगाने के लिए एचसीएस क्लस्टरिंग का उपयोग करना जिसका जैविक अर्थ हो सकता है। और जैविक प्रक्रियाओं का प्रतिनिधित्व कर सकता है।
- "क्लस्टरिंग एल्गोरिदम का सर्वेक्षण।" तंत्रिका नेटवर्क, आईईईई लेनदेन है।[4]
- क्लिक क्लस्टरिंग एल्गोरिदम[5] भारित समानता ग्राफ़ पर एचसीएस एल्गोरिदम का अनुकूलन है, जहां वजन को संभाव्यता स्वाद के साथ निर्दिष्ट किया जाता है।
- https://www.researchgate.net/publication/259350461_Partitioning_Biological_Networks_into_Highly_Connected_Clusters_with_Maximum_Edge_Coverage अधिकतम एज कवरेज के साथ अत्यधिक जुड़े समूहों में जैविक नेटवर्क का विभाजन है।[6]
- आर कार्यान्वयन
- पायथन कार्यान्वयन
संदर्भ
- ↑ Hartuv, E.; Shamir, R. (2000), "A clustering algorithm based on graph connectivity", Information Processing Letters, 76 (4–6): 175–181, doi:10.1016/S0020-0190(00)00142-3
- ↑ E Hartuv, A O Schmitt, J Lange, S Meier-Ewert, H Lehrach, R Shamir. "An algorithm for clustering cDNA fingerprints." Genomics 66, no. 3 (2000): 249-256.
- ↑ Jurisica, Igor, and Dennis Wigle. Knowledge Discovery in Proteomics. Vol. 8. CRC press, 2006.
- ↑ Xu, Rui, and Donald Wunsch. "Survey of clustering algorithms." Neural Networks, IEEE Transactions on 16, no. 3 (2005): 645-678.
- ↑ Sharan, R.; Shamir, R. (2000), "CLICK: A Clustering Algorithm with Applications to Gene Expression Analysis", Proceedings ISMB '00, 8: 307–316C, PMID 10977092
- ↑ Huffner, F.; Komusiewicz, C.; Liebtrau, A; Niedermeier, R (2014), "Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage", IEEE/ACM Transactions on Computational Biology and Bioinformatics, 11 (3): 455–467, CiteSeerX 10.1.1.377.1900, doi:10.1109/TCBB.2013.177, PMID 26356014, S2CID 991687
