एचसीएस क्लस्टरिंग एल्गोरिदम: Difference between revisions

From Vigyanwiki
(Created page with "{{Infobox Algorithm |class=Cluster analysis (on a similarity graph) |image= |caption = |data=Graph |time=<big>''O''(2N x f(n,m))</big> }} [http...")
 
No edit summary
Line 7: Line 7:
}}
}}


[https://www.researchgate.net/publication/222648006_A_clustering_algorithm_आधारित_on_graph_connectivity HCS (अत्यधिक कनेक्टेड सबग्राफ) क्लस्टरिंग एल्गोरिदम]<ref>{{Citation | doi=10.1016/S0020-0190(00)00142-3| title=A clustering algorithm based on graph connectivity | year=2000 | last1=Hartuv | first1=E. | last2=Shamir | first2=R. | journal=Information Processing Letters| volume=76 | issue=4–6 | pages=175–181}}</ref> (एचसीएस एल्गोरिदम के रूप में भी जाना जाता है, और अन्य नाम जैसे हाईली कनेक्टेड क्लस्टर/कंपोनेंट्स/कर्नेल) [[क्लस्टर विश्लेषण]] के लिए ग्राफ़ कनेक्टिविटी पर आधारित एक एल्गोरिदम है। यह एक [[समानता ग्राफ]]़ में समानता डेटा का प्रतिनिधित्व करके और फिर सभी अत्यधिक जुड़े उपग्राफ़ों को ढूंढकर काम करता है। यह समूहों की संख्या पर कोई पूर्व धारणा नहीं बनाता है। यह एल्गोरिदम 2000 में इरेज़ हार्टुव और [[रॉन शमीर]] द्वारा प्रकाशित किया गया था।
[https://www.researchgate.net/publication/222648006_A_clustering_algorithm_आधारित_on_graph_connectivity एचसीएस (अत्यधिक कनेक्टेड सबग्राफ) क्लस्टरिंग एल्गोरिदम]<ref>{{Citation | doi=10.1016/S0020-0190(00)00142-3| title=A clustering algorithm based on graph connectivity | year=2000 | last1=Hartuv | first1=E. | last2=Shamir | first2=R. | journal=Information Processing Letters| volume=76 | issue=4–6 | pages=175–181}}</ref> (एचसीएस एल्गोरिदम के रूप में भी जाना जाता है, और अन्य नाम जैसे हाईली कनेक्टेड क्लस्टर/कंपोनेंट्स/कर्नेल) [[क्लस्टर विश्लेषण]] के लिए ग्राफ़ कनेक्टिविटी पर आधारित एक एल्गोरिदम है। यह एक [[समानता ग्राफ]]़ में समानता डेटा का प्रतिनिधित्व करके और फिर सभी अत्यधिक जुड़े उपग्राफ़ों को ढूंढकर काम करता है। यह समूहों की संख्या पर कोई पूर्व धारणा नहीं बनाता है। यह एल्गोरिदम 2000 में इरेज़ हार्टुव और [[रॉन शमीर]] द्वारा प्रकाशित किया गया था।


एचसीएस एल्गोरिदम एक क्लस्टरिंग समाधान देता है, जो एप्लिकेशन डोमेन में स्वाभाविक रूप से सार्थक है, क्योंकि प्रत्येक समाधान क्लस्टर का व्यास 2 होना चाहिए जबकि दो समाधान क्लस्टर के मिलन का व्यास 3 होगा।
एचसीएस एल्गोरिदम एक क्लस्टरिंग समाधान देता है, जो एप्लिकेशन डोमेन में स्वाभाविक रूप से सार्थक है, क्योंकि प्रत्येक समाधान क्लस्टर का व्यास 2 होना चाहिए जबकि दो समाधान क्लस्टर के मिलन का व्यास 3 होगा।
Line 13: Line 13:
== समानता मॉडलिंग और प्रीप्रोसेसिंग ==
== समानता मॉडलिंग और प्रीप्रोसेसिंग ==


क्लस्टर विश्लेषण का लक्ष्य तत्वों के बीच समानता के आधार पर तत्वों को अलग-अलग उपसमूहों या समूहों में समूहित करना है, ताकि एक ही क्लस्टर में तत्व एक-दूसरे के समान (समरूपता) हों, जबकि विभिन्न समूहों के तत्वों में एक-दूसरे के प्रति कम समानता हो। (पृथक्करण). समानता ग्राफ़ तत्वों के बीच समानता का प्रतिनिधित्व करने वाले मॉडलों में से एक है, और बदले में क्लस्टर बनाने की सुविधा प्रदान करता है। समानता डेटा से एक समानता ग्राफ बनाने के लिए, तत्वों को शीर्षों के रूप में प्रस्तुत करें, और शीर्षों के बीच किनारों को प्राप्त करें जब उनके बीच समानता मान कुछ सीमा से ऊपर हो।
क्लस्टर विश्लेषण का लक्ष्य तत्वों के बीच समानता के आधार पर तत्वों को अलग-अलग उपसमूहों या समूहों में समूहित करना है, जिससे एक ही क्लस्टर में तत्व एक-दूसरे के समान (समरूपता) हों, जबकि विभिन्न समूहों के तत्वों में एक-दूसरे के प्रति कम समानता हो। (पृथक्करण). समानता ग्राफ़ तत्वों के बीच समानता का प्रतिनिधित्व करने वाले मॉडलों में से एक है, और बदले में क्लस्टर बनाने की सुविधा प्रदान करता है। समानता डेटा से एक समानता ग्राफ बनाने के लिए, तत्वों को शीर्षों के रूप में प्रस्तुत करें, और शीर्षों के बीच किनारों को प्राप्त करें जब उनके बीच समानता मान कुछ सीमा से ऊपर हो।


== एल्गोरिथम ==
== एल्गोरिथम ==


समानता ग्राफ में, दिए गए शीर्षों की संख्या के लिए जितने अधिक किनारे मौजूद होते हैं, शीर्षों का ऐसा सेट एक दूसरे के बीच उतना ही अधिक समान होता है। दूसरे शब्दों में, यदि हम किनारों को हटाकर एक समानता ग्राफ़ को डिस्कनेक्ट करने का प्रयास करते हैं, तो ग्राफ़ के डिस्कनेक्ट होने से पहले हमें जितने अधिक किनारों को हटाने की आवश्यकता होगी, इस ग्राफ़ में शीर्ष उतने ही अधिक समान होंगे। न्यूनतम कट किनारों का एक न्यूनतम सेट है जिसके बिना ग्राफ़ डिस्कनेक्ट हो जाएगा।
समानता ग्राफ में, दिए गए शीर्षों की संख्या के लिए जितने अधिक किनारे उपस्थित होते हैं, शीर्षों का ऐसा सेट एक दूसरे के बीच उतना ही अधिक समान होता है। दूसरे शब्दों में, यदि हम किनारों को हटाकर एक समानता ग्राफ़ को अलग करने का प्रयास करते हैं, तो ग्राफ़ के डिस्कनेक्ट होने से पहले हमें जितने अधिक किनारों को हटाने की आवश्यकता होगी, इस ग्राफ़ में शीर्ष उतने ही अधिक समान होंगे। न्यूनतम कट किनारों का एक न्यूनतम सेट है जिसके बिना ग्राफ़ डिस्कनेक्ट हो जाएगा।


{{See also|Connectivity (graph_theory)}}
{{See also|कनेक्टिविटी (ग्राफ_सिद्धांत)}}


एचसीएस क्लस्टरिंग एल्गोरिदम एन शीर्षों वाले सभी सबग्राफ को ऐसे ढूंढता है कि उन सबग्राफ के न्यूनतम कट में एन/2 से अधिक किनारे होते हैं, और उन्हें क्लस्टर के रूप में पहचानता है। ऐसे सबग्राफ को [[अत्यधिक कनेक्टेड सबग्राफ]] (एचसीएस) कहा जाता है। एकल शीर्षों को क्लस्टर नहीं माना जाता है और उन्हें सिंगलटन सेट एस में समूहीकृत किया जाता है।
एचसीएस क्लस्टरिंग एल्गोरिदम n शीर्षों वाले सभी सबग्राफ को ऐसे ढूंढता है कि उन सबग्राफ के न्यूनतम कट में n/2 से अधिक किनारे होते हैं, और उन्हें क्लस्टर के रूप में पहचानता है। ऐसे सबग्राफ को [[अत्यधिक कनेक्टेड सबग्राफ]] (एचसीएस) कहा जाता है। एकल शीर्षों को क्लस्टर नहीं माना जाता है और उन्हें सिंगलटन सेट s में समूहीकृत किया जाता है।


{{See also|Minimum cut}}
{{See also|न्यूनतम कट}}


एक समानता ग्राफ जी (वी, ई) को देखते हुए, एचसीएस क्लस्टरिंग एल्गोरिदम जांच करेगा कि क्या यह पहले से ही अत्यधिक जुड़ा हुआ है, यदि हां, तो जी लौटाता है, अन्यथा जी के न्यूनतम कट का उपयोग जी को दो सबग्राफ एच और एच 'में विभाजित करने के लिए करता है, और पुनरावर्ती रूप से चलाता है एच और एच' पर एचसीएस क्लस्टरिंग एल्गोरिदम।
एक समानता ग्राफ G(V,E) को देखते हुए, एचसीएस क्लस्टरिंग एल्गोरिदम जांच करेगा कि क्या यह पहले से ही अत्यधिक जुड़ा हुआ है, यदि हां, तो G लौटाता है, अन्यथा G के न्यूनतम कट का उपयोग G को दो सबग्राफ H और H' 'में विभाजित करने के लिए करता है, और पुनरावर्ती रूप से चलाता है H और H' पर एचसीएस क्लस्टरिंग एल्गोरिदम है।


== उदाहरण ==
== उदाहरण ==
Line 34: Line 34:


== स्यूडोकोड ==
== स्यूडोकोड ==
 
<syntaxhighlight>
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
</syntaxhighlight>
  फलन HCS(G(V, E)) है
  फलन HCS(G(V, E)) है
     यदि ''जी'' अत्यधिक जुड़ा हुआ है तो
     यदि ''जी'' अत्यधिक जुड़ा हुआ है तो
Line 49: Line 59:
== जटिलता ==
== जटिलता ==


एचसीएस क्लस्टरिंग एल्गोरिदम का चलने का समय सीमित है {{var|N}} × एफ(एन, एम). f(n, m) n शीर्षों और m किनारों वाले ग्राफ़ में न्यूनतम कट की गणना करने की समय जटिलता है, और {{var|N}} पाए गए समूहों की संख्या है। कई अनुप्रयोगों में एन << एन।
एचसीएस क्लस्टरिंग एल्गोरिदम का चलने का समय सीमित है <var>N</var> × f(n, m). f(n, m) शीर्षों और m किनारों वाले ग्राफ़ में न्यूनतम कट की गणना करने की समय जटिलता है, और {{var|N}} पाए गए समूहों की संख्या है। कई अनुप्रयोगों में N << n.


बिना भारित ग्राफ़ में न्यूनतम कट खोजने के लिए तेज़ एल्गोरिदम के लिए: {{See also|Karger's algorithm}}
बिना भारित ग्राफ़ में न्यूनतम कट खोजने के लिए तेज़ एल्गोरिदम के लिए: {{See also|कार्गर का एल्गोरिदम}}


==गुणों का प्रमाण ==
==गुणों का प्रमाण ==
Line 61: Line 71:
''प्रमाण:'' मान लीजिए n=|G| यदि G का शीर्ष x डिग्री <= n/2 के साथ है, तो G के पास न्यूनतम कट है (जो x को अलग करता है) किनारों <= n/2 के साथ, इसलिए G अत्यधिक जुड़ा नहीं है। इसलिए यदि G अत्यधिक जुड़ा हुआ है, तो प्रत्येक शीर्ष पर डिग्री >= n/2 है। ग्राफ सिद्धांत में एक प्रसिद्ध प्रमेय है जो कहता है कि यदि प्रत्येक शीर्ष की डिग्री >= n/2 है, तो G का व्यास (किसी भी दो नोड्स के बीच सबसे लंबा पथ) <= 2 है।
''प्रमाण:'' मान लीजिए n=|G| यदि G का शीर्ष x डिग्री <= n/2 के साथ है, तो G के पास न्यूनतम कट है (जो x को अलग करता है) किनारों <= n/2 के साथ, इसलिए G अत्यधिक जुड़ा नहीं है। इसलिए यदि G अत्यधिक जुड़ा हुआ है, तो प्रत्येक शीर्ष पर डिग्री >= n/2 है। ग्राफ सिद्धांत में एक प्रसिद्ध प्रमेय है जो कहता है कि यदि प्रत्येक शीर्ष की डिग्री >= n/2 है, तो G का व्यास (किसी भी दो नोड्स के बीच सबसे लंबा पथ) <= 2 है।


{{See also|Distance (graph theory)}}
{{See also|दूरी (ग्राफ सिद्धांत)}}


प्रमेय 2 (ए) अत्यधिक जुड़े ग्राफ में किनारों की संख्या द्विघात है। (बी) एचसीएस एल्गोरिथ्म के प्रत्येक पुनरावृत्ति द्वारा हटाए गए किनारों की संख्या अधिकतम रैखिक है।
प्रमेय 2 (a) अत्यधिक जुड़े ग्राफ में किनारों की संख्या द्विघात है। (b) एचसीएस एल्गोरिथ्म के प्रत्येक पुनरावृत्ति द्वारा हटाए गए किनारों की संख्या अधिकतम रैखिक है।


''प्रमाण:'' (ए) प्रमेय 1 से हम जानते हैं कि प्रत्येक शीर्ष की डिग्री >=n/2 है। इसलिए, अत्यधिक जुड़े ग्राफ़ में किनारों की संख्या कम से कम (n × n/2)/2 होनी चाहिए, जहां हम प्रत्येक शीर्ष की डिग्री का योग करते हैं और 2 से विभाजित करते हैं।
''प्रमाण:'' (a) प्रमेय 1 से हम जानते हैं कि प्रत्येक शीर्ष की डिग्री >=n/2 है। इसलिए, अत्यधिक जुड़े ग्राफ़ में किनारों की संख्या कम से कम (n × n/2)/2 होनी चाहिए, जहां हम प्रत्येक शीर्ष की डिग्री का योग करते हैं और 2 से विभाजित करते हैं।


(बी) परिभाषा के अनुसार, प्रत्येक पुनरावृत्ति <= n/2 किनारों के साथ एक न्यूनतम कटौती हटाती है।
(b) परिभाषा के अनुसार, प्रत्येक पुनरावृत्ति <= n/2 किनारों के साथ एक न्यूनतम कटौती हटाती है।


प्रमेय 1 और 2ए अंतिम क्लस्टर की एकरूपता का एक मजबूत संकेत प्रदान करते हैं। बेहतर करना उस मामले तक पहुंचता है जहां क्लस्टर के सभी कोने जुड़े हुए हैं, जो बहुत कठोर है और क्लिक समस्या|एनपी-हार्ड भी है।
प्रमेय 1 और 2a अंतिम क्लस्टर की एकरूपता का एक मजबूत संकेत प्रदान करते हैं। बेहतर करना उस स्थितियों तक पहुंचता है जहां क्लस्टर के सभी कोने जुड़े हुए हैं, जो बहुत कठोर है और क्लिक समस्या NP-हार्ड भी है।


प्रमेय 2बी अलगाव को इंगित करता है क्योंकि किन्हीं दो अंतिम समूहों सी1 और सी2 को तब तक अलग नहीं किया जा सकता था जब तक कि उनके बीच अधिकतम ओ(सी1+सी2) किनारे न हों (क्लस्टर के भीतर द्विघात किनारों के विपरीत)।
प्रमेय 2b अलगाव को इंगित करता है क्योंकि किन्हीं दो अंतिम समूहों c1 और c2 को तब तक अलग नहीं किया जा सकता था जब तक कि उनके बीच अधिकतम O(C1+C2) किनारे न हों (क्लस्टर के अन्दर द्विघात किनारों के विपरीत) है।


==विविधताएं==
==विविधताएं==
Line 84: Line 94:
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.</ref> सरणीकृत सीडीएनए में सिंथेटिक ऑलिगोन्यूक्लियोटाइड्स का संकरण प्रत्येक सीडीएनए क्लोन के लिए एक फिंगरप्रिंट उत्पन्न करता है। इन उंगलियों के निशान पर एचसीएस एल्गोरिदम चलाकर एक ही जीन के अनुरूप क्लोन की पहचान की जा सकती है।
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.</ref> सरणीकृत सीडीएनए में सिंथेटिक ऑलिगोन्यूक्लियोटाइड्स का संकरण प्रत्येक सीडीएनए क्लोन के लिए एक फिंगरप्रिंट उत्पन्न करता है। इन उंगलियों के निशान पर एचसीएस एल्गोरिदम चलाकर एक ही जीन के अनुरूप क्लोन की पहचान की जा सकती है।
* [http://www.cs.utoronto.ca/~natasha/book_chpt5_GT_NP.pdf पीपीआई नेटवर्क संरचना खोज]<ref>Jurisica, Igor, and Dennis Wigle. Knowledge Discovery in Proteomics. Vol. 8. CRC press, 2006.</ref> पीपीआई में घने उप-नेटवर्क का पता लगाने के लिए एचसीएस क्लस्टरिंग का उपयोग करना जिसका जैविक अर्थ हो सकता है और जैविक प्रक्रियाओं का प्रतिनिधित्व कर सकता है।
* [http://www.cs.utoronto.ca/~natasha/book_chpt5_GT_NP.pdf पीपीआई नेटवर्क संरचना खोज]<ref>Jurisica, Igor, and Dennis Wigle. Knowledge Discovery in Proteomics. Vol. 8. CRC press, 2006.</ref> पीपीआई में घने उप-नेटवर्क का पता लगाने के लिए एचसीएस क्लस्टरिंग का उपयोग करना जिसका जैविक अर्थ हो सकता है और जैविक प्रक्रियाओं का प्रतिनिधित्व कर सकता है।
* क्लस्टरिंग एल्गोरिदम का सर्वेक्षण। तंत्रिका नेटवर्क, आईईईई लेनदेन <ref>Xu, Rui, and Donald Wunsch. "Survey of clustering algorithms." Neural Networks, IEEE Transactions on 16, no. 3 (2005): 645-678.</ref>
* क्लस्टरिंग एल्गोरिदम का सर्वेक्षण। तंत्रिका नेटवर्क, IEEE लेनदेन <ref>Xu, Rui, and Donald Wunsch. "Survey of clustering algorithms." Neural Networks, IEEE Transactions on 16, no. 3 (2005): 645-678.</ref>
* क्लिक क्लस्टरिंग एल्गोरिदम<ref>{{Citation |  title=CLICK: A Clustering Algorithm with Applications to Gene Expression Analysis | year=2000 | last1=Sharan | first1=R. | last2=Shamir | first2=R. | journal=Proceedings ISMB '00| volume=8 | pages=307–316C| pmid=10977092 }}</ref> भारित समानता ग्राफ़ पर एचसीएस एल्गोरिदम का एक अनुकूलन है, जहां वजन को संभाव्यता स्वाद के साथ निर्दिष्ट किया जाता है।
* क्लिक क्लस्टरिंग एल्गोरिदम<ref>{{Citation |  title=CLICK: A Clustering Algorithm with Applications to Gene Expression Analysis | year=2000 | last1=Sharan | first1=R. | last2=Shamir | first2=R. | journal=Proceedings ISMB '00| volume=8 | pages=307–316C| pmid=10977092 }}</ref> भारित समानता ग्राफ़ पर एचसीएस एल्गोरिदम का एक अनुकूलन है, जहां वजन को संभाव्यता स्वाद के साथ निर्दिष्ट किया जाता है।
* https://www.researchgate.net/publication/259350461_Partitioning_Biological_Networks_into_Highly_Connected_Clusters_with_Maximum_Edge_Coverage अधिकतम एज कवरेज के साथ अत्यधिक जुड़े समूहों में जैविक नेटवर्क का विभाजन]<ref>{{Citation |
* https://www.researchgate.net/publication/259350461_Partitioning_Biological_Networks_into_Highly_Connected_Clusters_with_Maximum_Edge_Coverage अधिकतम एज कवरेज के साथ अत्यधिक जुड़े समूहों में जैविक नेटवर्क का विभाजन]<ref>{{Citation |

Revision as of 18:25, 22 July 2023

एचसीएस क्लस्टरिंग एल्गोरिदम
ClassCluster analysis (on a similarity graph)
Data structureGraph
Worst-case performanceO(2N x f(n,m))

एचसीएस (अत्यधिक कनेक्टेड सबग्राफ) क्लस्टरिंग एल्गोरिदम[1] (एचसीएस एल्गोरिदम के रूप में भी जाना जाता है, और अन्य नाम जैसे हाईली कनेक्टेड क्लस्टर/कंपोनेंट्स/कर्नेल) क्लस्टर विश्लेषण के लिए ग्राफ़ कनेक्टिविटी पर आधारित एक एल्गोरिदम है। यह एक समानता ग्राफ़ में समानता डेटा का प्रतिनिधित्व करके और फिर सभी अत्यधिक जुड़े उपग्राफ़ों को ढूंढकर काम करता है। यह समूहों की संख्या पर कोई पूर्व धारणा नहीं बनाता है। यह एल्गोरिदम 2000 में इरेज़ हार्टुव और रॉन शमीर द्वारा प्रकाशित किया गया था।

एचसीएस एल्गोरिदम एक क्लस्टरिंग समाधान देता है, जो एप्लिकेशन डोमेन में स्वाभाविक रूप से सार्थक है, क्योंकि प्रत्येक समाधान क्लस्टर का व्यास 2 होना चाहिए जबकि दो समाधान क्लस्टर के मिलन का व्यास 3 होगा।

समानता मॉडलिंग और प्रीप्रोसेसिंग

क्लस्टर विश्लेषण का लक्ष्य तत्वों के बीच समानता के आधार पर तत्वों को अलग-अलग उपसमूहों या समूहों में समूहित करना है, जिससे एक ही क्लस्टर में तत्व एक-दूसरे के समान (समरूपता) हों, जबकि विभिन्न समूहों के तत्वों में एक-दूसरे के प्रति कम समानता हो। (पृथक्करण). समानता ग्राफ़ तत्वों के बीच समानता का प्रतिनिधित्व करने वाले मॉडलों में से एक है, और बदले में क्लस्टर बनाने की सुविधा प्रदान करता है। समानता डेटा से एक समानता ग्राफ बनाने के लिए, तत्वों को शीर्षों के रूप में प्रस्तुत करें, और शीर्षों के बीच किनारों को प्राप्त करें जब उनके बीच समानता मान कुछ सीमा से ऊपर हो।

एल्गोरिथम

समानता ग्राफ में, दिए गए शीर्षों की संख्या के लिए जितने अधिक किनारे उपस्थित होते हैं, शीर्षों का ऐसा सेट एक दूसरे के बीच उतना ही अधिक समान होता है। दूसरे शब्दों में, यदि हम किनारों को हटाकर एक समानता ग्राफ़ को अलग करने का प्रयास करते हैं, तो ग्राफ़ के डिस्कनेक्ट होने से पहले हमें जितने अधिक किनारों को हटाने की आवश्यकता होगी, इस ग्राफ़ में शीर्ष उतने ही अधिक समान होंगे। न्यूनतम कट किनारों का एक न्यूनतम सेट है जिसके बिना ग्राफ़ डिस्कनेक्ट हो जाएगा।

See also: कनेक्टिविटी (ग्राफ_सिद्धांत)

एचसीएस क्लस्टरिंग एल्गोरिदम n शीर्षों वाले सभी सबग्राफ को ऐसे ढूंढता है कि उन सबग्राफ के न्यूनतम कट में n/2 से अधिक किनारे होते हैं, और उन्हें क्लस्टर के रूप में पहचानता है। ऐसे सबग्राफ को अत्यधिक कनेक्टेड सबग्राफ (एचसीएस) कहा जाता है। एकल शीर्षों को क्लस्टर नहीं माना जाता है और उन्हें सिंगलटन सेट s में समूहीकृत किया जाता है।

See also: न्यूनतम कट

एक समानता ग्राफ G(V,E) को देखते हुए, एचसीएस क्लस्टरिंग एल्गोरिदम जांच करेगा कि क्या यह पहले से ही अत्यधिक जुड़ा हुआ है, यदि हां, तो G लौटाता है, अन्यथा G के न्यूनतम कट का उपयोग G को दो सबग्राफ H और H' 'में विभाजित करने के लिए करता है, और पुनरावर्ती रूप से चलाता है H और H' पर एचसीएस क्लस्टरिंग एल्गोरिदम है।

उदाहरण

निम्नलिखित एनीमेशन दिखाता है कि कैसे एचसीएस क्लस्टरिंग एल्गोरिदम एक समानता ग्राफ को तीन समूहों में विभाजित करता है।

HCS Algorithm.gif

स्यूडोकोड

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
फलन HCS(G(V, E)) है
    यदि जी अत्यधिक जुड़ा हुआ है तो
        वापसी (जी)
    अन्य
        (एच1, एच2, सी) ← मिनिममकट(जी)
        एचसीएस(एच1)
        एचसीएस(एच2)
    अगर अंत
अंत समारोह

ग्राफ़ पर न्यूनतम कट ज्ञात करने का चरण G एक सबरूटीन है जिसे इस समस्या के लिए विभिन्न एल्गोरिदम का उपयोग करके कार्यान्वित किया जा सकता है। रैंडमाइजेशन का उपयोग करके न्यूनतम कट खोजने के लिए एक उदाहरण एल्गोरिथ्म के लिए नीचे देखें।

जटिलता

एचसीएस क्लस्टरिंग एल्गोरिदम का चलने का समय सीमित है N × f(n, m). f(n, m) शीर्षों और m किनारों वाले ग्राफ़ में न्यूनतम कट की गणना करने की समय जटिलता है, और N पाए गए समूहों की संख्या है। कई अनुप्रयोगों में N << n.

बिना भारित ग्राफ़ में न्यूनतम कट खोजने के लिए तेज़ एल्गोरिदम के लिए:

See also: कार्गर का एल्गोरिदम

गुणों का प्रमाण

एचसीएस क्लस्टरिंग एल्गोरिदम द्वारा उत्पादित क्लस्टर में कई गुण होते हैं, जो समाधान की एकरूपता और पृथक्करण को प्रदर्शित कर सकते हैं।

प्रमेय 1 प्रत्येक अत्यधिक जुड़े ग्राफ का व्यास अधिकतम दो है।

प्रमाण: मान लीजिए n=|G| यदि G का शीर्ष x डिग्री <= n/2 के साथ है, तो G के पास न्यूनतम कट है (जो x को अलग करता है) किनारों <= n/2 के साथ, इसलिए G अत्यधिक जुड़ा नहीं है। इसलिए यदि G अत्यधिक जुड़ा हुआ है, तो प्रत्येक शीर्ष पर डिग्री >= n/2 है। ग्राफ सिद्धांत में एक प्रसिद्ध प्रमेय है जो कहता है कि यदि प्रत्येक शीर्ष की डिग्री >= n/2 है, तो G का व्यास (किसी भी दो नोड्स के बीच सबसे लंबा पथ) <= 2 है।

See also: दूरी (ग्राफ सिद्धांत)

प्रमेय 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] पीपीआई में घने उप-नेटवर्क का पता लगाने के लिए एचसीएस क्लस्टरिंग का उपयोग करना जिसका जैविक अर्थ हो सकता है और जैविक प्रक्रियाओं का प्रतिनिधित्व कर सकता है।
  • क्लस्टरिंग एल्गोरिदम का सर्वेक्षण। तंत्रिका नेटवर्क, IEEE लेनदेन [4]
  • क्लिक क्लस्टरिंग एल्गोरिदम[5] भारित समानता ग्राफ़ पर एचसीएस एल्गोरिदम का एक अनुकूलन है, जहां वजन को संभाव्यता स्वाद के साथ निर्दिष्ट किया जाता है।
  • https://www.researchgate.net/publication/259350461_Partitioning_Biological_Networks_into_Highly_Connected_Clusters_with_Maximum_Edge_Coverage अधिकतम एज कवरेज के साथ अत्यधिक जुड़े समूहों में जैविक नेटवर्क का विभाजन][6]
  • आर कार्यान्वयन
  • पायथन कार्यान्वयन

संदर्भ

  1. ↑ 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
  2. ↑ 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.
  3. ↑ Jurisica, Igor, and Dennis Wigle. Knowledge Discovery in Proteomics. Vol. 8. CRC press, 2006.
  4. ↑ Xu, Rui, and Donald Wunsch. "Survey of clustering algorithms." Neural Networks, IEEE Transactions on 16, no. 3 (2005): 645-678.
  5. ↑ Sharan, R.; Shamir, R. (2000), "CLICK: A Clustering Algorithm with Applications to Gene Expression Analysis", Proceedings ISMB '00, 8: 307–316C, PMID 10977092
  6. ↑ 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
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=एचसीएस_क्लस्टरिंग_एल्गोरिदम&oldid=235202’