सर्वसम्मति क्लस्टरिंग: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(6 intermediate revisions by 3 users not shown)
Line 1: Line 1:
'''सर्वसम्मति क्लस्टरिंग''' कई [[क्लस्टरिंग एल्गोरिथ्म]] से परिणामों को एकत्र करने (संभावित रूप से परस्पर विरोधी) की एक विधि है। इसे क्लस्टर एन्सेम्बल भी कहा जाता है<ref name=StrehlEnsembles>{{cite journal|last1=Strehl|first1=Alexander|authorlink1=Alexander Strehl|author2=Ghosh, Joydeep|title=Cluster ensembles – a knowledge reuse framework for combining multiple partitions|journal=Journal on Machine Learning Research (JMLR)|date=2002|volume=3|pages=583–617|url=http://www.jmlr.org/papers/volume3/strehl02a/strehl02a.pdf|doi=10.1162/153244303321897735|quote=This paper introduces the problem of combining multiple partitionings of a set of objects into a single consolidated clustering without accessing the features or algorithms that determined these partitionings. We first identify several application scenarios for the resultant 'knowledge reuse' framework that we call cluster ensembles. The cluster ensemble problem is then formalized as a combinatorial optimization problem in terms of shared [[mutual information]]}}</ref> या क्लस्टरिंग (या विभाजन) का एकत्रीकरण, यह उस स्थिति को संदर्भित करता है जिसमें एक विशेष डेटासेट के लिए कई अलग-अलग (इनपुट) क्लस्टरिंग प्राप्त किए गए हैं और यह एक एकल (सर्वसम्मति) क्लस्टरिंग खोज वांछित है जो कुछ में उत्तम रूप से फिट हो जाती है उपस्थित क्लस्टरिंग की तुलना में अधिक समझदारी होती है <ref name=RuizSurvey2011>{{cite journal|last=VEGA-PONS|first=SANDRO|author2=RUIZ-SHULCLOPER, JOSÉ|s2cid=4643842|journal=International Journal of Pattern Recognition and Artificial Intelligence|date=1 May 2011|volume=25|issue=3|pages=337–372|doi=10.1142/S0218001411008683|title=A Survey of Clustering Ensemble Algorithms}}</ref> इस प्रकार सर्वसम्मति क्लस्टरिंग विभिन्न स्रोतों से या एक ही एल्गोरिदम के विभिन्न रनों से आने वाले एक ही डेटा सेट के बारे में क्लस्टरिंग जानकारी को समेटने की समस्या है। जब अनुकूलन समस्या के रूप में डाला जाता है, तो सर्वसम्मति क्लस्टरिंग को मध्य विभाजन के रूप में जाना जाता है, और इसे एनपी-पूर्ण दिखाया गया है,<ref name=Filkov2003>{{cite book|last=Filkov|first=Vladimir|title=Proceedings. 15th IEEE International Conference on Tools with Artificial Intelligence|chapter=Integrating microarray data by consensus clustering|journal=In Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence.|year=2003|pages=418–426|doi=10.1109/TAI.2003.1250220|isbn=978-0-7695-2038-4|citeseerx=10.1.1.116.8271|s2cid=1515525}}</ref> तब भी जब इनपुट क्लस्टरिंग की संख्या तीन होती है।<ref name=Bonizzoni2008>{{cite journal|last=Bonizzoni|first=Paola|author2=Della Vedova, Gianluca| author3= Dondi, Riccardo| author4= Jiang, Tao| title=सहसंबंध क्लस्टरिंग और सर्वसम्मति क्लस्टरिंग के अनुमान पर|journal=Journal of Computer and System Sciences|volume=74|number=5|year=2008|pages=671–696|doi=10.1016/j.jcss.2007.06.024|doi-access=free}}</ref> बिना पर्यवेक्षित शिक्षण के लिए सर्वसम्मति क्लस्टरिंग पर्यवेक्षित शिक्षण में सामूहिक शिक्षण के समान है।
'''सर्वसम्मति क्लस्टरिंग''' कई [[क्लस्टरिंग एल्गोरिथ्म]] से परिणामों को एकत्र करने (संभावित रूप से परस्पर विरोधी) की एक विधि है। इसे क्लस्टर एन्सेम्बल भी कहा जाता है <ref name=StrehlEnsembles>{{cite journal|last1=Strehl|first1=Alexander|authorlink1=Alexander Strehl|author2=Ghosh, Joydeep|title=Cluster ensembles – a knowledge reuse framework for combining multiple partitions|journal=Journal on Machine Learning Research (JMLR)|date=2002|volume=3|pages=583–617|url=http://www.jmlr.org/papers/volume3/strehl02a/strehl02a.pdf|doi=10.1162/153244303321897735|quote=This paper introduces the problem of combining multiple partitionings of a set of objects into a single consolidated clustering without accessing the features or algorithms that determined these partitionings. We first identify several application scenarios for the resultant 'knowledge reuse' framework that we call cluster ensembles. The cluster ensemble problem is then formalized as a combinatorial optimization problem in terms of shared [[mutual information]]}}</ref> या क्लस्टरिंग (या विभाजन) का एकत्रीकरण, यह उस स्थिति को संदर्भित करता है जिसमें एक विशेष डेटासेट के लिए कई अलग-अलग (इनपुट) क्लस्टरिंग प्राप्त किए गए हैं और यह एक एकल (सर्वसम्मति) क्लस्टरिंग खोज वांछित है जो कुछ में उत्तम रूप से फिट हो जाती है उपस्थित क्लस्टरिंग की तुलना में अधिक समझदारी होती है <ref name=RuizSurvey2011>{{cite journal|last=VEGA-PONS|first=SANDRO|author2=RUIZ-SHULCLOPER, JOSÉ|s2cid=4643842|journal=International Journal of Pattern Recognition and Artificial Intelligence|date=1 May 2011|volume=25|issue=3|pages=337–372|doi=10.1142/S0218001411008683|title=A Survey of Clustering Ensemble Algorithms}}</ref> इस प्रकार सर्वसम्मति क्लस्टरिंग विभिन्न स्रोतों से या एक ही एल्गोरिदम के विभिन्न रनों से आने वाले एक ही डेटा सेट के बारे में क्लस्टरिंग जानकारी को समेटने की समस्या है। जब अनुकूलन समस्या के रूप में डाला जाता है, तो सर्वसम्मति क्लस्टरिंग को मध्य विभाजन के रूप में जाना जाता है, और इसे एनपी-पूर्ण दिखाया गया है,<ref name=Filkov2003>{{cite book|last=Filkov|first=Vladimir|title=Proceedings. 15th IEEE International Conference on Tools with Artificial Intelligence|chapter=Integrating microarray data by consensus clustering|journal=In Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence.|year=2003|pages=418–426|doi=10.1109/TAI.2003.1250220|isbn=978-0-7695-2038-4|citeseerx=10.1.1.116.8271|s2cid=1515525}}</ref> तब भी जब इनपुट क्लस्टरिंग की संख्या तीन होती है।<ref name=Bonizzoni2008>{{cite journal|last=Bonizzoni|first=Paola|author2=Della Vedova, Gianluca| author3= Dondi, Riccardo| author4= Jiang, Tao| title=सहसंबंध क्लस्टरिंग और सर्वसम्मति क्लस्टरिंग के अनुमान पर|journal=Journal of Computer and System Sciences|volume=74|number=5|year=2008|pages=671–696|doi=10.1016/j.jcss.2007.06.024|doi-access=free}}</ref> जिससे पर्यवेक्षित शिक्षण के लिए सर्वसम्मति क्लस्टरिंग पर्यवेक्षित शिक्षण में सामूहिक शिक्षण के समान है।


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


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


पुनरावृत्त वंश क्लस्टरिंग विधियां, जैसे कि [[स्व-संगठित मानचित्र]] और [[ k-मतलब क्लस्टरिंग | k-मतलब क्लस्टरिंग]] , एकतरफा परिभाषित क्लस्टर और क्लस्टर सीमाओं को प्रदान करके [[पदानुक्रमित क्लस्टरिंग]] की कुछ कमियों को दूर करती हैं। सर्वसम्मति क्लस्टरिंग एक ऐसी विधि प्रदान करती है जो डेटा में क्लस्टर की संख्या निर्धारित करने और खोजे गए क्लस्टर की स्थिरता का आकलन करने के लिए क्लस्टरिंग एल्गोरिदम के कई रनों में सर्वसम्मति का प्रतिनिधित्व करती है। विधि का उपयोग यादृच्छिक पुनरारंभ (जैसे के-मीन्स, मॉडल-आधारित बायेसियन क्लस्टरिंग, एसओएम इत्यादि) के साथ क्लस्टरिंग एल्गोरिदम के कई रनों पर आम सहमति का प्रतिनिधित्व करने के लिए भी किया जा सकता है, जिससे प्रारंभिक स्थितियों के प्रति इसकी संवेदनशीलता को ध्यान में रखा जा सकत्र है। यह क्लस्टर संख्या, सदस्यता और सीमाओं का निरीक्षण करने के लिए विज़ुअलाइज़ेशन उपकरण के लिए डेटा प्रदान कर सकता है। चूँकि उनमें पदानुक्रमित क्लस्टरिंग डेंड्रोग्राम की सहज और दृश्य अपील का अभाव है, और समूहों की संख्या को प्राथमिकता से चुना जाना चाहिए।
पुनरावृत्त वंश क्लस्टरिंग विधियां, जैसे कि [[स्व-संगठित मानचित्र]] और [[ k-मतलब क्लस्टरिंग |k-मैटलैब क्लस्टरिंग]] , एकतरफा परिभाषित क्लस्टर और क्लस्टर सीमाओं को प्रदान करके [[पदानुक्रमित क्लस्टरिंग]] की कुछ कमियों को दूर करती हैं। सर्वसम्मति क्लस्टरिंग एक ऐसी विधि प्रदान करती है जो डेटा में क्लस्टर की संख्या निर्धारित करने और खोजे गए क्लस्टर की स्थिरता का आकलन करने के लिए क्लस्टरिंग एल्गोरिदम के कई रनों में सर्वसम्मति का प्रतिनिधित्व करती है। विधि का उपयोग यादृच्छिक पुनरारंभ (जैसे के-मीन्स, मॉडल-आधारित बायेसियन क्लस्टरिंग, एसओएम इत्यादि) के साथ क्लस्टरिंग एल्गोरिदम के कई रनों पर आम सहमति का प्रतिनिधित्व करने के लिए भी किया जा सकता है, जिससे प्रारंभिक स्थितियों के प्रति इसकी संवेदनशीलता को ध्यान में रखा जा सकत्र है। यह क्लस्टर संख्या, सदस्यता और सीमाओं का निरीक्षण करने के लिए विज़ुअलाइज़ेशन उपकरण के लिए डेटा प्रदान कर सकता है। चूँकि उनमें पदानुक्रमित क्लस्टरिंग डेंड्रोग्राम की सहज और दृश्य अपील का अभाव है, और समूहों की संख्या को प्राथमिकता से चुना जाना चाहिए।


==मोंटी सर्वसम्मति क्लस्टरिंग एल्गोरिदम==
==मोंटी सर्वसम्मति क्लस्टरिंग एल्गोरिदम                                                                                                                         ==
मोंटी सर्वसम्मति क्लस्टरिंग एल्गोरिदम<ref>{{Cite journal|last1=Monti|first1=Stefano|last2=Tamayo|first2=Pablo|last3=Mesirov|first3=Jill|last4=Golub|first4=Todd|date=2003-07-01|title=Consensus Clustering: A Resampling-Based Method for Class Discovery and Visualization of Gene Expression Microarray Data|journal=Machine Learning|language=en|volume=52|issue=1|pages=91–118|doi=10.1023/A:1023949509487|issn=1573-0565|doi-access=free}}</ref> सबसे लोकप्रिय सर्वसम्मति क्लस्टरिंग एल्गोरिदम में से एक है और इसका उपयोग क्लस्टर की संख्या निर्धारित करने के लिए किया जाता है, <math>K</math> क्लस्टर के लिए <math>K</math> कुल अंकों के डेटासेट को देखते हुए, यह एल्गोरिदम डेटा को फिर से नमूनाकरण और क्लस्टरिंग द्वारा काम करता है , प्रत्येक <math>K</math> और <math>N \times N</math> सर्वसम्मति आव्यूह की गणना की जाती है, जहां प्रत्येक तत्व एक साथ क्लस्टर किए गए दो नमूनों के समय के अंश का प्रतिनिधित्व करता है। एक पूरी तरह से स्थिर आव्यूह में पूरी तरह से शून्य और एक सम्मिलित होंगे, जो सभी नमूना जोड़े को सभी पुन: नमूनाकरण पुनरावृत्तियों पर सदैव एक साथ क्लस्टर करते हैं या एक साथ नहीं दर्शाते हैं। सर्वसम्मति आव्यूह की सापेक्ष स्थिरता का उपयोग इष्टतम <math>K</math> का अनुमान लगाने के लिए किया जा सकता है।
मोंटी सर्वसम्मति क्लस्टरिंग एल्गोरिदम <ref>{{Cite journal|last1=Monti|first1=Stefano|last2=Tamayo|first2=Pablo|last3=Mesirov|first3=Jill|last4=Golub|first4=Todd|date=2003-07-01|title=Consensus Clustering: A Resampling-Based Method for Class Discovery and Visualization of Gene Expression Microarray Data|journal=Machine Learning|language=en|volume=52|issue=1|pages=91–118|doi=10.1023/A:1023949509487|issn=1573-0565|doi-access=free}}</ref> सबसे लोकप्रिय सर्वसम्मति क्लस्टरिंग एल्गोरिदम में से एक है और इसका उपयोग क्लस्टर की संख्या निर्धारित करने के लिए किया जाता है, <math>K</math> क्लस्टर के लिए <math>K</math> कुल अंकों के डेटासेट को देखते हुए, यह एल्गोरिदम डेटा को फिर से प्रतिरूप और क्लस्टरिंग द्वारा कार्य करता है , प्रत्येक <math>K</math> और <math>N \times N</math> सर्वसम्मति आव्यूह की गणना की जाती है, जहां प्रत्येक तत्व एक साथ क्लस्टर किए गए दो प्रतिरूपों के समय के अंश का प्रतिनिधित्व करता है। एक पूरी तरह से स्थिर आव्यूह में पूरी तरह से शून्य और एक सम्मिलित होंगे, जो सभी प्रतिरूप जोड़े को सभी पुन: प्रतिरूप पुनरावृत्तियों पर सदैव एक साथ क्लस्टर करते हैं या एक साथ नहीं दर्शाते हैं। सर्वसम्मति आव्यूह की सापेक्ष स्थिरता का उपयोग इष्टतम <math>K</math> का अनुमान लगाने के लिए किया जा सकता है।


अधिक विशेष रूप से, क्लस्टर के लिए बिंदुओं का एक सेट दिया गया है, <math>D=\{e_1,e_2,...e_N\}</math> मान लीजिए कि <math>D^1,D^2,...,D^H</math> मूल डेटासेट <math>D</math> के <math>H</math>परेशान (पुन: नमूना) डेटासेट की सूची है, और <math>M^h</math> परिणामस्वरूप <math>N \times N</math> कनेक्टिविटी आव्यूह को दर्शाता है डेटासेट <math>D^h</math> पर क्लस्टरिंग एल्गोरिदम प्रयुक्त करना <math>M^h</math> की प्रविष्टियाँ इस प्रकार परिभाषित की गई हैं:
अधिक विशेष रूप से, क्लस्टर के लिए बिंदुओं का एक सेट दिया गया है, <math>D=\{e_1,e_2,...e_N\}</math> मान लीजिए कि <math>D^1,D^2,...,D^H</math> मूल डेटासेट <math>D</math> के <math>H</math>परेशान (पुन: प्रतिरूप) डेटासेट की सूची है, और <math>M^h</math> परिणामस्वरूप <math>N \times N</math> कनेक्टिविटी आव्यूह को दर्शाता है डेटासेट <math>D^h</math> पर क्लस्टरिंग एल्गोरिदम प्रयुक्त करना <math>M^h</math> की प्रविष्टियाँ इस प्रकार परिभाषित की गई हैं:


<math>M^h(i,j)= \begin{cases} 1, & \text{if}\text{ points i and j belong to the same cluster} \\ 0, & \text{otherwise} \end{cases}</math>
<math>M^h(i,j)= \begin{cases} 1, & \text{if}\text{ points i and j belong to the same cluster} \\ 0, & \text{otherwise} \end{cases}                            
                                                                                                                                                                                                                               
                                                                                                                                                                                                                                  </math>                                                                            


मान लीजिए कि <math>I^h</math> <math>N \times N</math> पहचानकर्ता आव्यूह है, जहां <math>(i,j)</math>-वीं प्रविष्टि 1 के समान है यदि बिंदु <math>i</math> और <math>j</math> एक ही विकृत डेटासेट <math>D^h</math> में हैं, और 0 अन्यथा। सूचक आव्यूह का उपयोग यह ट्रैक करने के लिए किया जाता है कि सामान्यीकरण चरण के लिए प्रत्येक पुन: नमूनाकरण पुनरावृत्ति के समय कौन से नमूने चुने गए थे। सर्वसम्मति आव्यूह <math>C</math> को सभी परेशान डेटासेट के सभी कनेक्टिविटी आव्यूह के सामान्यीकृत योग के रूप में परिभाषित किया गया है और प्रत्येक <math>K</math> के लिए एक अलग गणना की जाती है।
मान लीजिए कि <math>I^h</math> <math>N \times N</math> पहचानकर्ता आव्यूह है, जहां <math>(i,j)</math>-वीं प्रविष्टि 1 के समान है यदि बिंदु <math>i</math> और <math>j</math> एक ही विकृत डेटासेट <math>D^h</math> में हैं, और 0 अन्यथा सूचक आव्यूह का उपयोग यह ट्रैक करने के लिए किया जाता है कि सामान्यीकरण चरण के लिए प्रत्येक पुन: प्रतिरूप पुनरावृत्ति के समय कौन से प्रतिरूप चुने गए थे। सर्वसम्मति आव्यूह <math>C</math> को सभी परेशान डेटासेट के सभी कनेक्टिविटी आव्यूह के सामान्यीकृत योग के रूप में परिभाषित किया गया है और प्रत्येक <math>K</math> के लिए एक अलग गणना की जाती है।


<math>C(i,j)=\left ( \frac{\textstyle \sum_{h=1}^H M^h(i,j) \displaystyle}{\sum_{h=1}^H I^h(i,j)} \right )</math>
<math>C(i,j)=\left ( \frac{\textstyle \sum_{h=1}^H M^h(i,j) \displaystyle}{\sum_{h=1}^H I^h(i,j)} \right )</math>


अथार्त सर्वसम्मति आव्यूह में प्रविष्टि <math>(i,j)</math>बिंदुओं की संख्या <math>i</math> और <math>j</math> को एक साथ क्लस्टर किए जाने की संख्या को उनके एक साथ चुने जाने की कुल संख्या से विभाजित किया जाता है। आव्यूह सममित है और प्रत्येक तत्व को सीमा <math>[0,1]</math> के अंदर परिभाषित किया गया है। परीक्षण किए जाने वाले प्रत्येक <math>K</math> के लिए एक सर्वसम्मति आव्यूह की गणना की जाती है और प्रत्येक आव्यूह की स्थिरता अर्थात आव्यूह सही स्थिरता (केवल शून्य और एक) के आव्यूह की ओर कितनी दूर है, का उपयोग इष्टतम <math>K</math> को निर्धारित करने के लिए किया जाता है। मात्रा निर्धारित करने का एक तरीका <math>K</math>वें सर्वसम्मति आव्यूह की स्थिरता इसके सीडीएफ वक्र की जांच कर रही है (नीचे देखें)।
अथार्त सर्वसम्मति आव्यूह में प्रविष्टि <math>(i,j)</math>बिंदुओं की संख्या <math>i</math> और <math>j</math> को एक साथ क्लस्टर किए जाने की संख्या को उनके एक साथ चुने जाने की कुल संख्या से विभाजित किया जाता है। आव्यूह सममित है और प्रत्येक तत्व को सीमा <math>[0,1]</math> के अंदर परिभाषित किया गया है। परीक्षण किए जाने वाले प्रत्येक <math>K</math> के लिए एक सर्वसम्मति आव्यूह की गणना की जाती है और प्रत्येक आव्यूह की स्थिरता अर्थात आव्यूह सही स्थिरता (केवल शून्य और एक) के आव्यूह की ओर कितनी दूर है, का उपयोग इष्टतम <math>K</math> को निर्धारित करने के लिए किया जाता है। मात्रा निर्धारित करने का एक विधि <math>K</math>वें सर्वसम्मति आव्यूह की स्थिरता इसके सीडीएफ वक्र की जांच कर रही है (नीचे देखें)।


==मोंटी सर्वसम्मति क्लस्टरिंग एल्गोरिदम की अति-व्याख्या क्षमता==
==मोंटी सर्वसम्मति क्लस्टरिंग एल्गोरिदम की अति-व्याख्या क्षमता                                                       ==
[[File:PACexplained.png|400px|thumb|पीएसी माप (अस्पष्ट क्लस्टरिंग का अनुपात) समझाया गया। इष्टतम K न्यूनतम PAC मान वाला K है।]]मोंटी सर्वसम्मति क्लस्टरिंग समूहों की पहचान करने के लिए एक शक्तिशाली उपकरण हो सकता है, किंतु इसे सावधानी के साथ प्रयुक्त करने की आवश्यकता है जैसा कि सेनबाबाओग्लू एट अल द्वारा दिखाया गया है। <ref name="SenbabaogluSREP" /> यह दिखाया गया है कि मोंटी सर्वसम्मति क्लस्टरिंग एल्गोरिदम एक यूनिमॉडल वितरण से खींचे गए अशक्त डेटासेट के अवसर `विभाजन की स्पष्ट स्थिरता का प्रमाण करने में सक्षम है, और इस प्रकार एक वास्तविक अध्ययन में क्लस्टर स्थिरता की अधिक व्याख्या करने की क्षमता है।<ref name=SenbabaogluSREP>{{cite journal|last=Şenbabaoğlu|first=Y.|author2=Michailidis, G. |author3=Li, J. Z. |title=वर्ग खोज में सर्वसम्मति क्लस्टरिंग की महत्वपूर्ण सीमाएँ|journal=Scientific Reports|date=2014|doi=10.1038/srep06207|volume=4|pages=6207|pmid=25158761|pmc=4145288|bibcode=2014NatSR...4E6207.}}</ref><ref name=SenbabaogluRXV>{{cite bioRxiv|last=Şenbabaoğlu|first=Y.|author2=Michailidis, G. |author3=Li, J. Z. |title=वर्ग खोज के लिए सर्वसम्मति क्लस्टरिंग का पुनर्मूल्यांकन|date=Feb 2014|biorxiv=10.1101/002642}}</ref> यदि समूहों को अच्छी तरह से अलग नहीं किया गया है, तो आम सहमति क्लस्टरिंग किसी को स्पष्ट संरचना का निष्कर्ष निकालने के लिए प्रेरित कर सकती है जब कोई नहीं है, या सूक्ष्म होने पर क्लस्टर स्थिरता की घोषणा कर सकता है। पूरे क्लस्टर अनुसंधान में लाई सकारात्मक समूहों की पहचान करना एक आम समस्या है,<ref name=":0">{{Cite journal|last1=Liu|first1=Yufeng|last2=Hayes|first2=David Neil|last3=Nobel|first3=Andrew|last4=Marron|first4=J. S.|date=2008-09-01|title=Statistical Significance of Clustering for High-Dimension, Low–Sample Size Data|journal=Journal of the American Statistical Association|volume=103|issue=483|pages=1281–1293|doi=10.1198/016214508000000454|s2cid=120819441|issn=0162-1459}}</ref> और इसे सिगक्लस्ट जैसी विधियों द्वारा संबोधित किया गया है<ref name=":0" /> और गैप-सांख्यिकी <ref>{{Cite journal|last1=Tibshirani|first1=Robert|last2=Walther|first2=Guenther|last3=Hastie|first3=Trevor|date=2001|title=अंतराल आँकड़ों के माध्यम से डेटा सेट में समूहों की संख्या का अनुमान लगाना|journal=Journal of the Royal Statistical Society, Series B (Statistical Methodology)|language=en|volume=63|issue=2|pages=411–423|doi=10.1111/1467-9868.00293|s2cid=59738652 |issn=1467-9868}}</ref> चूँकि ये विधियाँ शून्य मॉडल के लिए कुछ मान्यताओं पर निर्भर करती हैं जो सदैव उपयुक्त नहीं हो सकती हैं।
[[File:PACexplained.png|400px|thumb|पीएसी माप (अस्पष्ट क्लस्टरिंग का अनुपात) समझाया गया। इष्टतम K न्यूनतम PAC मान वाला K है।]]मोंटी सर्वसम्मति क्लस्टरिंग समूहों की पहचान करने के लिए एक शक्तिशाली उपकरण हो सकता है, किंतु इसे सावधानी के साथ प्रयुक्त करने की आवश्यकता है जैसा कि सेनबाबाओग्लू एट अल द्वारा दिखाया गया है। <ref name="SenbabaogluSREP" /> यह दिखाया गया है कि मोंटी सर्वसम्मति क्लस्टरिंग एल्गोरिदम एक यूनिमॉडल वितरण से खींचे गए अशक्त डेटासेट के अवसर `विभाजन की स्पष्ट स्थिरता का प्रमाण करने में सक्षम है, और इस प्रकार एक वास्तविक अध्ययन में क्लस्टर स्थिरता की अधिक व्याख्या करने की क्षमता है।<ref name=SenbabaogluSREP>{{cite journal|last=Şenbabaoğlu|first=Y.|author2=Michailidis, G. |author3=Li, J. Z. |title=वर्ग खोज में सर्वसम्मति क्लस्टरिंग की महत्वपूर्ण सीमाएँ|journal=Scientific Reports|date=2014|doi=10.1038/srep06207|volume=4|pages=6207|pmid=25158761|pmc=4145288|bibcode=2014NatSR...4E6207.}}</ref><ref name=SenbabaogluRXV>{{cite bioRxiv|last=Şenbabaoğlu|first=Y.|author2=Michailidis, G. |author3=Li, J. Z. |title=वर्ग खोज के लिए सर्वसम्मति क्लस्टरिंग का पुनर्मूल्यांकन|date=Feb 2014|biorxiv=10.1101/002642}}</ref> यदि समूहों को अच्छी तरह से अलग नहीं किया गया है, तो सामान्य सहमति क्लस्टरिंग किसी को स्पष्ट संरचना का निष्कर्ष निकालने के लिए प्रेरित कर सकती है जब कोई नहीं है, या सूक्ष्म होने पर क्लस्टर स्थिरता की घोषणा कर सकता है। पूरे क्लस्टर अनुसंधान में लाई सकारात्मक समूहों की पहचान करना एक आम समस्या है,<ref name=":0">{{Cite journal|last1=Liu|first1=Yufeng|last2=Hayes|first2=David Neil|last3=Nobel|first3=Andrew|last4=Marron|first4=J. S.|date=2008-09-01|title=Statistical Significance of Clustering for High-Dimension, Low–Sample Size Data|journal=Journal of the American Statistical Association|volume=103|issue=483|pages=1281–1293|doi=10.1198/016214508000000454|s2cid=120819441|issn=0162-1459}}</ref> और इसे सिगक्लस्ट जैसी विधियों द्वारा संबोधित किया गया है <ref name=":0" /> और गैप-सांख्यिकी <ref>{{Cite journal|last1=Tibshirani|first1=Robert|last2=Walther|first2=Guenther|last3=Hastie|first3=Trevor|date=2001|title=अंतराल आँकड़ों के माध्यम से डेटा सेट में समूहों की संख्या का अनुमान लगाना|journal=Journal of the Royal Statistical Society, Series B (Statistical Methodology)|language=en|volume=63|issue=2|pages=411–423|doi=10.1111/1467-9868.00293|s2cid=59738652 |issn=1467-9868}}</ref> चूँकि ये विधियाँ शून्य मॉडल के लिए कुछ मान्यताओं पर निर्भर करती हैं जो सदैव उपयुक्त नहीं हो सकती हैं।


सेनबाबाओग्लू एट अल<ref name="SenbabaogluSREP" /> ने खराब प्रदर्शन करने वाले मोंटी एल्गोरिदम में K को तय करने के लिए मूल डेल्टा <math>K</math> मीट्रिक का प्रदर्शन किया, और उनके सीडीएफ वक्रों का उपयोग करके सर्वसम्मति आव्यूह की स्थिरता को मापने के लिए एक नया उत्तम मीट्रिक प्रस्तावित किया जाता है । सर्वसम्मति आव्यूह के सीडीएफ वक्र में, निचला बायां भाग नमूना जोड़े का प्रतिनिधित्व करता है जो संभवतः ही कभी एक साथ क्लस्टर होते हैं, ऊपरी दायां भाग उन लोगों का प्रतिनिधित्व करता है जो लगभग सदैव एक साथ क्लस्टर होते हैं, जबकि मध्य खंड अलग-अलग क्लस्टरिंग रन में अस्पष्ट असाइनमेंट वाले लोगों का प्रतिनिधित्व करता है। अस्पष्ट क्लस्टरिंग (पीएसी) स्कोर माप का अनुपात इस मध्य खंड की मात्रा निर्धारित करता है; और इसे अंतराल (u<sub>1</sub>, u<sub>2</sub>) ∈ [0, 1] में आने वाले सर्वसम्मति सूचकांकों के साथ नमूना जोड़े के अंश के रूप में परिभाषित किया गया है, जहां u<sub>1</sub> 0 के समीप का मान है और u<sub>2</sub>1 के समीप का मान है (उदाहरण के लिए u<sub>1</sub> =0.1 और u<sub>2</sub>=0.9). पीएसी का कम मूल्य एक सपाट मध्य खंड को इंगित करता है, और क्रमबद्ध क्लस्टरिंग रन में असंगत असाइनमेंट की कम दर को इंगित करता है। इसलिए सबसे कम पीएसी वाले K मान से क्लस्टर की इष्टतम संख्या का अनुमान लगाया जा सकता है।<ref name="SenbabaogluSREP" /><ref name="SenbabaogluRXV" />
सेनबाबाओग्लू एट अल <ref name="SenbabaogluSREP" /> ने खराब प्रदर्शन करने वाले मोंटी एल्गोरिदम में K को तय करने के लिए मूल डेल्टा <math>K</math> मीट्रिक का प्रदर्शन किया, और उनके सीडीएफ वक्रों का उपयोग करके सर्वसम्मति आव्यूह की स्थिरता को मापने के लिए एक नया उत्तम मीट्रिक प्रस्तावित किया जाता है । सर्वसम्मति आव्यूह के सीडीएफ वक्र में, निचला बायां भाग प्रतिरूप जोड़े का प्रतिनिधित्व करता है जो संभवतः ही कभी एक साथ क्लस्टर होते हैं, ऊपरी दायां भाग उन लोगों का प्रतिनिधित्व करता है जो लगभग सदैव एक साथ क्लस्टर होते हैं, जबकि मध्य खंड अलग-अलग क्लस्टरिंग रन में अस्पष्ट असाइनमेंट वाले लोगों का प्रतिनिधित्व करता है। अस्पष्ट क्लस्टरिंग (पीएसी) स्कोर माप का अनुपात इस मध्य खंड की मात्रा निर्धारित करता है; और इसे अंतराल (u<sub>1</sub>, u<sub>2</sub>) ∈ [0, 1] में आने वाले सर्वसम्मति सूचकांकों के साथ प्रतिरूप जोड़े के अंश के रूप में परिभाषित किया गया है, जहां u<sub>1</sub> 0 के समीप का मान है और u<sub>2</sub>1 के समीप का मान है (उदाहरण के लिए u<sub>1</sub> =0.1 और u<sub>2</sub>=0.9). पीएसी का कम मूल्य एक सपाट मध्य खंड को इंगित करता है, और क्रमबद्ध क्लस्टरिंग रन में असंगत असाइनमेंट की कम दर को इंगित करता है। इसलिए सबसे कम पीएसी वाले K मान से क्लस्टर की इष्टतम संख्या का अनुमान लगाया जा सकता है।<ref name="SenbabaogluSREP" /><ref name="SenbabaogluRXV" />
==संबंधित कार्य==
==संबंधित कार्य==
#क्लस्टरिंग पहनावा (स्ट्रेहल और घोष): उन्होंने समस्या के लिए विभिन्न सूत्रीकरण पर विचार किया गया, जिनमें से अधिकांश समस्या को [[हाइपर-ग्राफ]] विभाजन समस्या में बदल देते हैं। अपने एक सूत्रीकरण में उन्होंने सहसंबंध क्लस्टरिंग समस्या के समान ग्राफ़ पर विचार किया। उन्होंने जो समाधान प्रस्तावित किया है वह ग्राफ़ के सर्वोत्तम ''k''-विभाजन की गणना करना है, जो दूर स्थित दो नोड्स के विलय के लिए शास्ति को ध्यान में नहीं रखता है।<ref name=StrehlEnsembles/>  
#क्लस्टरिंग पहनावा (स्ट्रेहल और घोष): उन्होंने समस्या के लिए विभिन्न सूत्रीकरण पर विचार किया गया, जिनमें से अधिकांश समस्या को [[हाइपर-ग्राफ]] विभाजन समस्या में बदल देते हैं। अपने एक सूत्रीकरण में उन्होंने सहसंबंध क्लस्टरिंग समस्या के समान ग्राफ़ पर विचार किया। उन्होंने जो समाधान प्रस्तावित किया है वह ग्राफ़ के सर्वोत्तम ''k''-विभाजन की गणना करना है, जो दूर स्थित दो नोड्स के विलय के लिए शास्ति को ध्यान में नहीं रखता है।<ref name=StrehlEnsembles/>  
#क्लस्टरिंग एकत्रीकरण (फ़र्न और ब्रोडली): उन्होंने क्लस्टरिंग एकत्रीकरण विचार को यादृच्छिक अनुमानों द्वारा प्राप्त [[नरम क्लस्टरिंग]] के संग्रह पर प्रयुक्त किया गया था। उन्होंने एक समूहीकृत एल्गोरिदम का उपयोग किया और असमान नोड्स को विलय करने के लिए शास्ति नहीं किया।<ref>{{cite journal|author1=Fern, Xiaoli |author2= Brodley, Carla|year=2004|title=Cluster ensembles for high dimensional clustering: an empirical study|journal=J Mach Learn Res|volume=22|url=https://www.researchgate.net/publication/228476517}} </ref>
#क्लस्टरिंग एकत्रीकरण (फ़र्न और ब्रोडली): उन्होंने क्लस्टरिंग एकत्रीकरण विचार को यादृच्छिक अनुमानों द्वारा प्राप्त [[नरम क्लस्टरिंग]] के संग्रह पर प्रयुक्त किया गया था। उन्होंने एक समूहीकृत एल्गोरिदम का उपयोग किया और असमान नोड्स को विलय करने के लिए शास्ति नहीं किया।<ref>{{cite journal|author1=Fern, Xiaoli |author2= Brodley, Carla|year=2004|title=Cluster ensembles for high dimensional clustering: an empirical study|journal=J Mach Learn Res|volume=22|url=https://www.researchgate.net/publication/228476517}} </ref>
#फ़्रेड और जैन: उन्होंने ''k''-मीन्स एल्गोरिथम के एकाधिक रन को संयोजित करने के लिए एकल लिंकेज एल्गोरिथम का उपयोग करने का प्रस्ताव रखा।<ref>{{cite journal | last1=Fred | first1=Ana L.N. | last2=Jain | first2=Anil K. | title=साक्ष्य संचय का उपयोग करके कई क्लस्टरिंग का संयोजन| journal=IEEE Transactions on Pattern Analysis and Machine Intelligence | publisher=Institute of Electrical and Electronics Engineers (IEEE) | volume=27 | issue=6 | year=2005 | issn=0162-8828 | doi=10.1109/tpami.2005.113 | pages=835–850|pmid= 15943417| s2cid=10316033 |url=http://dataclustering.cse.msu.edu/papers/TPAMI-0239-0504.R1.pdf}}</ref>
#फ़्रेड और जैन: उन्होंने ''k''-मीन्स एल्गोरिथम के एकाधिक रन को संयोजित करने के लिए एकल लिंकेज एल्गोरिथम का उपयोग करने का प्रस्ताव रखा।<ref>{{cite journal | last1=Fred | first1=Ana L.N. | last2=Jain | first2=Anil K. | title=साक्ष्य संचय का उपयोग करके कई क्लस्टरिंग का संयोजन| journal=IEEE Transactions on Pattern Analysis and Machine Intelligence | publisher=Institute of Electrical and Electronics Engineers (IEEE) | volume=27 | issue=6 | year=2005 | issn=0162-8828 | doi=10.1109/tpami.2005.113 | pages=835–850|pmid= 15943417| s2cid=10316033 |url=http://dataclustering.cse.msu.edu/papers/TPAMI-0239-0504.R1.pdf}}</ref>
#डाना क्रिस्टोफ़ोर और डैन सिमोविसी: उन्होंने क्लस्टरिंग एकत्रीकरण और श्रेणीबद्ध चर के क्लस्टरिंग के बीच संबंध देखा। उन्होंने सूचना सैद्धांतिक दूरी के उपायों का प्रस्ताव दिया था , और उन्होंने सर्वोत्तम एकत्रीकरण समाधान खोजने के लिए आनुवंशिक एल्गोरिदम का प्रस्ताव दिया गया था।<ref>रेफरी>{{cite journal|author=Dana Cristofor, Dan Simovici|title=सूचना-सैद्धांतिक-आधारित आनुवंशिक एल्गोरिदम का उपयोग करके माध्यिका विभाजन ढूँढना|journal=Journal of Universal Computer Science|volume=8|issue=2|pages=153–172|url=https://www.jucs.org/jucs_8_2/finding_median_partitions_using/Cristofor_D.pdf|date=February 2002|doi=10.3217/jucs-008-02-0153}}<nowiki></ref></nowiki></ref>
#डाना क्रिस्टोफ़ोर और डैन सिमोविसी: उन्होंने क्लस्टरिंग एकत्रीकरण और श्रेणीबद्ध चर के क्लस्टरिंग के बीच संबंध देखा। उन्होंने सूचना सैद्धांतिक दूरी के उपायों का प्रस्ताव दिया था और उन्होंने सर्वोत्तम एकत्रीकरण समाधान खोजने के लिए आनुवंशिक एल्गोरिदम का प्रस्ताव दिया गया था।<ref>रेफरी>{{cite journal|author=Dana Cristofor, Dan Simovici|title=सूचना-सैद्धांतिक-आधारित आनुवंशिक एल्गोरिदम का उपयोग करके माध्यिका विभाजन ढूँढना|journal=Journal of Universal Computer Science|volume=8|issue=2|pages=153–172|url=https://www.jucs.org/jucs_8_2/finding_median_partitions_using/Cristofor_D.pdf|date=February 2002|doi=10.3217/jucs-008-02-0153}}<nowiki></ref>
#टॉपची और अन्य: उन्होंने क्लस्टरिंग एकत्रीकरण को अधिकतम संभावना अनुमान समस्या के रूप में परिभाषित किया, और उन्होंने सर्वसम्मति क्लस्टरिंग खोजने के लिए एक [[ईएम एल्गोरिदम]] प्रस्तावित किया गया था।<ref>संदर्भ>अलेक्जेंडर टॉपची, अनिल के. जैन, विलियम पंच। [http://dataclustering.cse.msu.edu/papers/TPAMI-ClusteringEnsembles.pdf क्लस्टरिंग एन्सेम्बल्स: सर्वसम्मति और कमजोर विभाजन के मॉडल]। डेटा माइनिंग पर आईईईई अंतर्राष्ट्रीय सम्मेलन, आईसीडीएम 03 और डेटा माइनिंग पर एसआईएएम अंतर्राष्ट्रीय सम्मेलन, एसडीएम 04<nowiki></ref></nowiki></ref>
#टॉपची और अन्य: उन्होंने क्लस्टरिंग एकत्रीकरण को अधिकतम संभावना अनुमान समस्या के रूप में परिभाषित किया, और उन्होंने सर्वसम्मति क्लस्टरिंग खोजने के लिए एक [[ईएम एल्गोरिदम]] प्रस्तावित किया गया था।<ref>संदर्भ>अलेक्जेंडर टॉपची, अनिल के. जैन, विलियम पंच। [http://dataclustering.cse.msu.edu/papers/TPAMI-ClusteringEnsembles.pdf क्लस्टरिंग एन्सेम्बल्स: सर्वसम्मति और कमजोर विभाजन के मॉडल]। डेटा माइनिंग पर आईईईई अंतर्राष्ट्रीय सम्मेलन, आईसीडीएम 03 और डेटा माइनिंग पर एसआईएएम अंतर्राष्ट्रीय सम्मेलन, एसडीएम 04<nowiki></ref>
== कठिन पहनावा क्लस्टरिंग ==
== कठिन पहनावा क्लस्टरिंग ==


स्ट्रेहल और घोष का यह दृष्टिकोण इन विभाजनों को निर्धारित करने वाली सुविधाओं या एल्गोरिदम तक पहुंच के बिना वस्तुओं के एक समूह के कई विभाजनों को एक एकल समेकित क्लस्टरिंग में संयोजित करने की समस्या का परिचय देता है। वे उच्च गुणवत्ता वाले सर्वसम्मति कार्यों को प्राप्त करने के लिए इस समस्या को हल करने की दिशा में तीन दृष्टिकोणों पर चर्चा करते हैं। उनकी तकनीकों की कम्प्यूटेशनल निवेश कम है और इससे नीचे चर्चा की गई प्रत्येक तकनीक का मूल्यांकन करना और उद्देश्य फ़ंक्शन के विरुद्ध परिणामों की तुलना करके सर्वोत्तम समाधान पर पहुंचना संभव हो जाता है।
स्ट्रेहल और घोष का यह दृष्टिकोण इन विभाजनों को निर्धारित करने वाली सुविधाओं या एल्गोरिदम तक पहुंच के बिना वस्तुओं के एक समूह के कई विभाजनों को एक एकल समेकित क्लस्टरिंग में संयोजित करने की समस्या का परिचय देता है। वे उच्च गुणवत्ता वाले सर्वसम्मति कार्यों को प्राप्त करने के लिए इस समस्या को हल करने की दिशा में तीन दृष्टिकोणों पर चर्चा करते हैं। उनकी तकनीकों की कम्प्यूटेशनल निवेश कम है और इससे नीचे चर्चा की गई प्रत्येक तकनीक का मूल्यांकन करना और उद्देश्य फलन के विरुद्ध परिणामों की तुलना करके सर्वोत्तम समाधान पर पहुंचना संभव हो जाता है।


=== कुशल सर्वसम्मति कार्य ===
=== कुशल सर्वसम्मति कार्य ===


#क्लस्टर-आधारित समानता विभाजन एल्गोरिदम (सीएसपीए): सीएसपीए में दो डेटा-बिंदुओं के बीच समानता को उस समूह के घटक क्लस्टरिंग की संख्या के सीधे आनुपातिक के रूप में परिभाषित किया गया है जिसमें वे एक साथ क्लस्टर किए गए हैं। अंतर्ज्ञान यह है कि दो डेटा-बिंदु जितने अधिक समान होंगे, उतनी ही अधिक संभावना होगी कि घटक क्लस्टरिंग उन्हें एक ही क्लस्टर में रखेगी। सीएसपीए सबसे सरल अनुमान है, किंतु इसकी कम्प्यूटेशनल और संचयन समिष्टता दोनों ''n'' में द्विघात हैं। [http://bioconductor.org/packages/release/bioc/html/SC3.html SC3] सीएसपीए प्रकार के एल्गोरिदम का एक उदाहरण है।<ref>{{Cite journal|last1=Kiselev|first1=Vladimir Yu|last2=Kirschner|first2=Kristina|last3=Schaub|first3=Michael T|last4=Andrews|first4=Tallulah|last5=Yiu|first5=Andrew|last6=Chandra|first6=Tamir|last7=Natarajan|first7=Kedar N|last8=Reik|first8=Wolf|last9=Barahona|first9=Mauricio|last10=Green|first10=Anthony R|last11=Hemberg|first11=Martin|date=May 2017|title=SC3: consensus clustering of single-cell RNA-seq data|journal=Nature Methods|language=en|volume=14|issue=5|pages=483–486|doi=10.1038/nmeth.4236|issn=1548-7091|pmc=5410170|pmid=28346451}}</ref> निम्नलिखित दो विधियाँ कम्प्यूटेशनल रूप से कम मूल्यवान हैं:
#क्लस्टर-आधारित समानता विभाजन एल्गोरिदम (सीएसपीए): सीएसपीए में दो डेटा-बिंदुओं के बीच समानता को उस समूह के घटक क्लस्टरिंग की संख्या के सीधे आनुपातिक के रूप में परिभाषित किया गया है जिसमें वे एक साथ क्लस्टर किए गए हैं। अंतर्ज्ञान यह है कि दो डेटा-बिंदु जितने अधिक समान होंगे, उतनी ही अधिक संभावना होगी कि घटक क्लस्टरिंग उन्हें एक ही क्लस्टर में रखेगी। सीएसपीए सबसे सरल अनुमान है, किंतु इसकी कम्प्यूटेशनल और संचयन समिष्टता दोनों ''n'' में द्विघात हैं। [http://bioconductor.org/packages/release/bioc/html/SC3.html SC3] सीएसपीए प्रकार के एल्गोरिदम का एक उदाहरण है।<ref>{{Cite journal|last1=Kiselev|first1=Vladimir Yu|last2=Kirschner|first2=Kristina|last3=Schaub|first3=Michael T|last4=Andrews|first4=Tallulah|last5=Yiu|first5=Andrew|last6=Chandra|first6=Tamir|last7=Natarajan|first7=Kedar N|last8=Reik|first8=Wolf|last9=Barahona|first9=Mauricio|last10=Green|first10=Anthony R|last11=Hemberg|first11=Martin|date=May 2017|title=SC3: consensus clustering of single-cell RNA-seq data|journal=Nature Methods|language=en|volume=14|issue=5|pages=483–486|doi=10.1038/nmeth.4236|issn=1548-7091|pmc=5410170|pmid=28346451}}</ref> निम्नलिखित दो विधियाँ कम्प्यूटेशनल रूप से कम मूल्यवान हैं:
#हाइपर-ग्राफ विभाजन एल्गोरिदम (एचजीपीए): एचजीपीए एल्गोरिदम पिछली पद्धति की तुलना में सर्वसम्मति क्लस्टरिंग को खोजने के लिए एक बहुत अलग दृष्टिकोण अपनाता है। क्लस्टर एन्सेम्बल समस्या को न्यूनतम संख्या में हाइपरएज को विभाजित हाइपरग्राफ को विभाजित करने के रूप में तैयार किया गया है। वे [http://glaros.dtc.umn.edu/gkhome/metis/hmetis/overview hMETIS] का उपयोग करते हैं जो एक हाइपरग्राफ विभाजन पैकेज सिस्टम है।
#हाइपर-ग्राफ विभाजन एल्गोरिदम (एचजीपीए): एचजीपीए एल्गोरिदम पिछली पद्धति की तुलना में सर्वसम्मति क्लस्टरिंग को खोजने के लिए एक बहुत अलग दृष्टिकोण अपनाता है। क्लस्टर एन्सेम्बल समस्या को न्यूनतम संख्या में हाइपरएज को विभाजित हाइपरग्राफ को विभाजित करने के रूप में तैयार किया गया है। वे [http://glaros.dtc.umn.edu/gkhome/metis/hmetis/overview मेटीस] का उपयोग करते हैं जो एक हाइपरग्राफ विभाजन पैकेज सिस्टम है।
#मेटा-क्लस्टरिंग एल्गोरिदम (एमसीएलए): मेटा-क्लस्टरिंग एल्गोरिदम (एमसीएलए) क्लस्टरिंग क्लस्टर पर आधारित है। सबसे पहले, यह क्लस्टर पत्राचार समस्या को हल करने का प्रयास करता है और फिर डेटा-बिंदुओं को अंतिम सर्वसम्मति क्लस्टर में रखने के लिए वोटिंग का उपयोग करता है। क्लस्टर पत्राचार समस्या को समूह के अलग-अलग समूहों में पहचाने गए समूहों को समूहीकृत करके हल किया जाता है। क्लस्टरिंग [http://glaros.dtc.umn.edu/gkhome/views/metis METIS] और स्पेक्ट्रल क्लस्टरिंग का उपयोग करके की जाती है।
#मेटा-क्लस्टरिंग एल्गोरिदम (एमसीएलए): मेटा-क्लस्टरिंग एल्गोरिदम (एमसीएलए) क्लस्टरिंग क्लस्टर पर आधारित है। सबसे पहले, यह क्लस्टर पत्राचार समस्या को हल करने का प्रयास करता है और फिर डेटा-बिंदुओं को अंतिम सर्वसम्मति क्लस्टर में रखने के लिए वोटिंग का उपयोग करता है। क्लस्टर पत्राचार समस्या को समूह के अलग-अलग समूहों में पहचाने गए समूहों को समूहीकृत करके हल किया जाता है। क्लस्टरिंग [http://glaros.dtc.umn.edu/gkhome/views/metis मेटीस] और स्पेक्ट्रल क्लस्टरिंग का उपयोग करके की जाती है।


== नरम क्लस्टरिंग समूह ==
== नरम क्लस्टरिंग समूह ==


पुनेरा और घोष ने हार्ड क्लस्टरिंग पहनावे के विचार को सॉफ्ट क्लस्टरिंग परिदृश्य तक बढ़ाया था जो नरम संयोजन में प्रत्येक उदाहरण को घटक क्लस्टरिंग एल्गोरिदम से प्राप्त आर पोस्टीरियर सदस्यता संभाव्यता वितरण के संयोजन द्वारा दर्शाया जाता है। हम कुल्बैक-लीब्लर डाइवर्जेंस या कुल्बैक-लीब्लर (केएल) डाइवर्जेंस का उपयोग करके दो उदाहरणों के बीच दूरी माप को परिभाषित कर सकते हैं, जो दो संभाव्यता वितरणों के बीच की दूरी की गणना करता है।<ref>Kunal Punera, Joydeep Ghosh. [https://web.archive.org/web/20081201150950/http://www.ideal.ece.utexas.edu/papers/2007/punera07softconsensus.pdf Consensus Based Ensembles of Soft Clusterings]</ref>
पुनेरा और घोष ने हार्ड क्लस्टरिंग पहनावे के विचार को सॉफ्ट क्लस्टरिंग परिदृश्य तक बढ़ाया था जो नरम संयोजन में प्रत्येक उदाहरण को घटक क्लस्टरिंग एल्गोरिदम से प्राप्त आर पोस्टीरियर सदस्यता संभाव्यता वितरण के संयोजन द्वारा दर्शाया जाता है। हम कुल्बैक-लीब्लर डाइवर्जेंस या कुल्बैक-लीब्लर (केएल) डाइवर्जेंस का उपयोग करके दो उदाहरणों के बीच दूरी माप को परिभाषित कर सकते हैं, जो दो संभाव्यता वितरणों के बीच की दूरी की गणना करता है।<ref>Kunal Punera, Joydeep Ghosh. [https://web.archive.org/web/20081201150950/http://www.ideal.ece.utexas.edu/papers/2007/punera07softconsensus.pdf Consensus Based Ensembles of Soft Clusterings]</ref>
#sCSPA: समानता आव्यूह की गणना करके सीएसपीए का विस्तार करता है। प्रत्येक वस्तु को आयामी स्थान में एक बिंदु के रूप में देखा जाता है, प्रत्येक आयाम एक क्लस्टर से संबंधित होने की संभावना के अनुरूप होता है। यह तकनीक पहले वस्तुओं को एक लेबल-स्पेस में बदल देती है और फिर वस्तुओं का प्रतिनिधित्व करने वाले वैक्टरों के बीच [[डॉट उत्पाद]] को उनकी समानता के रूप में व्याख्या करती है।
#एससीएसपीए: समानता आव्यूह की गणना करके सीएसपीए का विस्तार करता है। प्रत्येक वस्तु को आयामी स्थान में एक बिंदु के रूप में देखा जाता है, प्रत्येक आयाम एक क्लस्टर से संबंधित होने की संभावना के अनुरूप होता है। यह तकनीक पहले वस्तुओं को एक लेबल-स्पेस में बदल देती है और फिर वस्तुओं का प्रतिनिधित्व करने वाले वैक्टरों के बीच [[डॉट उत्पाद]] को उनकी समानता के रूप में व्याख्या करती है।
#sMCLA: सॉफ्ट क्लस्टरिंग को इनपुट के रूप में स्वीकार करके एमसीएलए का विस्तार करता है। एसएमसीएलए की कार्यप्रणाली को निम्नलिखित चरणों में विभाजित किया जा सकता है:
#एसएमसीएलए: सॉफ्ट क्लस्टरिंग को इनपुट के रूप में स्वीकार करके एमसीएलए का विस्तार करता है। एसएमसीएलए की कार्यप्रणाली को निम्नलिखित चरणों में विभाजित किया जा सकता है:
#* क्लस्टरों का सॉफ्ट मेटा-ग्राफ़ बनाएं
#* क्लस्टरों का सॉफ्ट मेटा-ग्राफ़ बनाएं
#* क्लस्टरों को मेटा-क्लस्टरों में समूहित करें
#* क्लस्टरों को मेटा-क्लस्टरों में समूहित करें
#* वेटिंग का उपयोग करके मेटा-क्लस्टर को संक्षिप्त करें
#* वेटिंग का उपयोग करके मेटा-क्लस्टर को संक्षिप्त करें
#* वस्तुओं के लिए प्रतिस्पर्धा करें
#* वस्तुओं के लिए प्रतिस्पर्धा करें
#sHBGF: समूहों और उदाहरणों को नोड्स के रूप में एक [[द्विदलीय ग्राफ]] के रूप में दर्शाता है, और उदाहरणों और जिन समूहों से वे संबंधित हैं, उनके बीच किनारों को दर्शाता है।<ref>Solving cluster ensemble problems by bipartite graph partitioning, Xiaoli Zhang Fern and [[Carla Brodley]], Proceedings of the twenty-first international conference on Machine learning</ref> इस दृष्टिकोण को नरम संयोजनों पर विचार करने के लिए तुच्छ रूप से अनुकूलित किया जा सकता है क्योंकि ग्राफ़ विभाजन एल्गोरिथ्म मेटिस विभाजित होने वाले ग्राफ़ के किनारों पर भार स्वीकार करता है। sHBGF में, ग्राफ़ में n+t शीर्ष हैं, जहां t अंतर्निहित समूहों की कुल संख्या है।
#एसएचबीजीएफ: समूहों और उदाहरणों को नोड्स के रूप में एक [[द्विदलीय ग्राफ]] के रूप में दर्शाता है, और उदाहरणों और जिन समूहों से वे संबंधित हैं, उनके बीच किनारों को दर्शाता है।<ref>Solving cluster ensemble problems by bipartite graph partitioning, Xiaoli Zhang Fern and [[Carla Brodley]], Proceedings of the twenty-first international conference on Machine learning</ref> इस दृष्टिकोण को नरम संयोजनों पर विचार करने के लिए तुच्छ रूप से अनुकूलित किया जा सकता है क्योंकि ग्राफ़ विभाजन एल्गोरिथ्म मेटिस विभाजित होने वाले ग्राफ़ के किनारों पर भार स्वीकार करता है। एसएचबीजीएफ में, ग्राफ़ में n+t शीर्ष हैं, जहां t अंतर्निहित समूहों की कुल संख्या है।
#'बायेसियन सर्वसम्मति क्लस्टरिंग (बीसीसी)': नरम सर्वसम्मति क्लस्टरिंग के लिए पूरी तरह से बायेसियन संभाव्यता मॉडल को परिभाषित करता है जिसमें विभिन्न इनपुट डेटा या विभिन्न संभाव्यता मॉडल द्वारा परिभाषित एकाधिक स्रोत क्लस्टरिंग को आम सहमति क्लस्टरिंग के लिए शिथिल रूप से पालन करने के लिए माना जाता है।<ref name=LockBCC>{{cite journal|last=Lock|first=E.F.|author2=Dunson, D.B.  |title=बायेसियन सर्वसम्मति क्लस्टरिंग|journal=Bioinformatics|date=2013|doi=10.1093/bioinformatics/btt425|pmid=23990412|pmc=3789539|volume=29|number=20|pages=2610–2616|arxiv=1302.7280|bibcode=2013arXiv1302.7280L}}</ref> अलग-अलग क्लस्टरिंग और सर्वसम्मति क्लस्टरिंग के लिए पूर्ण पश्च भाग का अनुमान [[ गिब्स नमूनाकरण ]] के माध्यम से एक साथ लगाया जाता है।
#'बायेसियन सर्वसम्मति क्लस्टरिंग (बीसीसी)': नरम सर्वसम्मति क्लस्टरिंग के लिए पूरी तरह से बायेसियन संभाव्यता मॉडल को परिभाषित करता है जिसमें विभिन्न इनपुट डेटा या विभिन्न संभाव्यता मॉडल द्वारा परिभाषित एकाधिक स्रोत क्लस्टरिंग को आम सहमति क्लस्टरिंग के लिए शिथिल रूप से पालन करने के लिए माना जाता है।<ref name=LockBCC>{{cite journal|last=Lock|first=E.F.|author2=Dunson, D.B.  |title=बायेसियन सर्वसम्मति क्लस्टरिंग|journal=Bioinformatics|date=2013|doi=10.1093/bioinformatics/btt425|pmid=23990412|pmc=3789539|volume=29|number=20|pages=2610–2616|arxiv=1302.7280|bibcode=2013arXiv1302.7280L}}</ref> अलग-अलग क्लस्टरिंग और सर्वसम्मति क्लस्टरिंग के लिए पूर्ण पश्च भाग का अनुमान [[ गिब्स नमूनाकरण |गिब्स प्रतिरूप]] के माध्यम से एक साथ लगाया जाता है।
#एनसेंबल क्लस्टरिंग फ़ज़िफिकेशन मीन्स (ईसीएफ-मीन्स): ईसीएफ-मीन्स एक क्लस्टरिंग एल्गोरिदम है, जो चुने हुए एल्गोरिदम ([[ k-साधन ]]) के विभिन्न रन द्वारा प्राप्त किए गए अलग-अलग क्लस्टरिंग परिणामों को एक ही अंतिम क्लस्टरिंग कॉन्फ़िगरेशन में जोड़ता है।<ref name=ZazzECF>{{cite journal|last=Zazzaro|first=Gaetano|author2=Martone, Angelo |title=ईसीएफ-साधन - एन्सेम्बल क्लस्टरिंग फ़ज़िफिकेशन साधन। क्लस्टरिंग एकत्रीकरण, फ़ज़िफ़िकेशन और अनुकूलन के लिए एक नया एल्गोरिदम|journal=IMM 2018: The Eighth International Conference on Advances in Information Mining and Management|date=2018}} [https://www.thinkmind.org/articles/immm_2018_2_10_50010.pdf]</ref>
#एनसेंबल क्लस्टरिंग फ़ज़िफिकेशन मीन्स (ईसीएफ-मीन्स): ईसीएफ-मीन्स एक क्लस्टरिंग एल्गोरिदम है, जो चुने हुए एल्गोरिदम ([[ k-साधन ]]) के विभिन्न रन द्वारा प्राप्त किए गए अलग-अलग क्लस्टरिंग परिणामों को एक ही अंतिम क्लस्टरिंग कॉन्फ़िगरेशन में जोड़ता है।<ref name=ZazzECF>{{cite journal|last=Zazzaro|first=Gaetano|author2=Martone, Angelo |title=ईसीएफ-साधन - एन्सेम्बल क्लस्टरिंग फ़ज़िफिकेशन साधन। क्लस्टरिंग एकत्रीकरण, फ़ज़िफ़िकेशन और अनुकूलन के लिए एक नया एल्गोरिदम|journal=IMM 2018: The Eighth International Conference on Advances in Information Mining and Management|date=2018}} [https://www.thinkmind.org/articles/immm_2018_2_10_50010.pdf]</ref>
== संदर्भ ==
== संदर्भ ==


Line 67: Line 67:
* Hongjun Wang, Hanhuai Shan, Arindam Banerjee. [http://www.siam.org/proceedings/datamining/2009/SDM09_022_wangh.pdf Bayesian Cluster Ensembles]{{Dead link|date=November 2019 |bot=InternetArchiveBot |fix-attempted=yes }}, SIAM International Conference on Data Mining, SDM 09
* Hongjun Wang, Hanhuai Shan, Arindam Banerjee. [http://www.siam.org/proceedings/datamining/2009/SDM09_022_wangh.pdf Bayesian Cluster Ensembles]{{Dead link|date=November 2019 |bot=InternetArchiveBot |fix-attempted=yes }}, SIAM International Conference on Data Mining, SDM 09
*{{cite conference | last1=Nguyen | first1=Nam | last2=Caruana | first2=Rich | title=Seventh IEEE International Conference on Data Mining (ICDM 2007) | chapter=Consensus Clusterings | publisher=IEEE | year=2007 | pages=607–612 | doi=10.1109/icdm.2007.73 | isbn=978-0-7695-3018-5 |quote=...we address the problem of combining multiple clusterings without access to the underlying features of the data. This process is known in the literature as clustering ensembles, clustering aggregation, or consensus clustering. Consensus clustering yields a stable and robust final clustering that is in agreement with multiple clusterings. We find that an iterative EM-like method is remarkably effective for this problem. We present an iterative algorithm and its variations for finding clustering consensus. An extensive empirical study compares our proposed algorithms with eleven other consensus clustering methods on four data sets using three different clustering performance metrics. The experimental results show that the new ensemble clustering methods produce clusterings that are as good as, and often better than, these other methods.}}
*{{cite conference | last1=Nguyen | first1=Nam | last2=Caruana | first2=Rich | title=Seventh IEEE International Conference on Data Mining (ICDM 2007) | chapter=Consensus Clusterings | publisher=IEEE | year=2007 | pages=607–612 | doi=10.1109/icdm.2007.73 | isbn=978-0-7695-3018-5 |quote=...we address the problem of combining multiple clusterings without access to the underlying features of the data. This process is known in the literature as clustering ensembles, clustering aggregation, or consensus clustering. Consensus clustering yields a stable and robust final clustering that is in agreement with multiple clusterings. We find that an iterative EM-like method is remarkably effective for this problem. We present an iterative algorithm and its variations for finding clustering consensus. An extensive empirical study compares our proposed algorithms with eleven other consensus clustering methods on four data sets using three different clustering performance metrics. The experimental results show that the new ensemble clustering methods produce clusterings that are as good as, and often better than, these other methods.}}
[[Category: क्लस्टर विश्लेषण]]


[[Category: Machine Translated Page]]
[[Category:All articles with dead external links]]
[[Category:Articles with dead external links from November 2019]]
[[Category:Articles with permanently dead external links]]
[[Category:CS1 English-language sources (en)]]
[[Category:Created On 10/07/2023]]
[[Category:Created On 10/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Templates Vigyan Ready]]
[[Category:क्लस्टर विश्लेषण]]

Latest revision as of 16:44, 29 July 2023

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

उपस्थित क्लस्टरिंग तकनीकों के साथ उद्देश्य

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

सर्वसम्मति क्लस्टरिंग का उपयोग करने का औचित्य

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

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

मोंटी सर्वसम्मति क्लस्टरिंग एल्गोरिदम

मोंटी सर्वसम्मति क्लस्टरिंग एल्गोरिदम [5] सबसे लोकप्रिय सर्वसम्मति क्लस्टरिंग एल्गोरिदम में से एक है और इसका उपयोग क्लस्टर की संख्या निर्धारित करने के लिए किया जाता है, क्लस्टर के लिए कुल अंकों के डेटासेट को देखते हुए, यह एल्गोरिदम डेटा को फिर से प्रतिरूप और क्लस्टरिंग द्वारा कार्य करता है , प्रत्येक और सर्वसम्मति आव्यूह की गणना की जाती है, जहां प्रत्येक तत्व एक साथ क्लस्टर किए गए दो प्रतिरूपों के समय के अंश का प्रतिनिधित्व करता है। एक पूरी तरह से स्थिर आव्यूह में पूरी तरह से शून्य और एक सम्मिलित होंगे, जो सभी प्रतिरूप जोड़े को सभी पुन: प्रतिरूप पुनरावृत्तियों पर सदैव एक साथ क्लस्टर करते हैं या एक साथ नहीं दर्शाते हैं। सर्वसम्मति आव्यूह की सापेक्ष स्थिरता का उपयोग इष्टतम का अनुमान लगाने के लिए किया जा सकता है।

अधिक विशेष रूप से, क्लस्टर के लिए बिंदुओं का एक सेट दिया गया है, मान लीजिए कि मूल डेटासेट के परेशान (पुन: प्रतिरूप) डेटासेट की सूची है, और परिणामस्वरूप कनेक्टिविटी आव्यूह को दर्शाता है डेटासेट पर क्लस्टरिंग एल्गोरिदम प्रयुक्त करना की प्रविष्टियाँ इस प्रकार परिभाषित की गई हैं:

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

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

मोंटी सर्वसम्मति क्लस्टरिंग एल्गोरिदम की अति-व्याख्या क्षमता

पीएसी माप (अस्पष्ट क्लस्टरिंग का अनुपात) समझाया गया। इष्टतम K न्यूनतम PAC मान वाला K है।

मोंटी सर्वसम्मति क्लस्टरिंग समूहों की पहचान करने के लिए एक शक्तिशाली उपकरण हो सकता है, किंतु इसे सावधानी के साथ प्रयुक्त करने की आवश्यकता है जैसा कि सेनबाबाओग्लू एट अल द्वारा दिखाया गया है। [6] यह दिखाया गया है कि मोंटी सर्वसम्मति क्लस्टरिंग एल्गोरिदम एक यूनिमॉडल वितरण से खींचे गए अशक्त डेटासेट के अवसर `विभाजन की स्पष्ट स्थिरता का प्रमाण करने में सक्षम है, और इस प्रकार एक वास्तविक अध्ययन में क्लस्टर स्थिरता की अधिक व्याख्या करने की क्षमता है।[6][7] यदि समूहों को अच्छी तरह से अलग नहीं किया गया है, तो सामान्य सहमति क्लस्टरिंग किसी को स्पष्ट संरचना का निष्कर्ष निकालने के लिए प्रेरित कर सकती है जब कोई नहीं है, या सूक्ष्म होने पर क्लस्टर स्थिरता की घोषणा कर सकता है। पूरे क्लस्टर अनुसंधान में लाई सकारात्मक समूहों की पहचान करना एक आम समस्या है,[8] और इसे सिगक्लस्ट जैसी विधियों द्वारा संबोधित किया गया है [8] और गैप-सांख्यिकी [9] चूँकि ये विधियाँ शून्य मॉडल के लिए कुछ मान्यताओं पर निर्भर करती हैं जो सदैव उपयुक्त नहीं हो सकती हैं।

सेनबाबाओग्लू एट अल [6] ने खराब प्रदर्शन करने वाले मोंटी एल्गोरिदम में K को तय करने के लिए मूल डेल्टा मीट्रिक का प्रदर्शन किया, और उनके सीडीएफ वक्रों का उपयोग करके सर्वसम्मति आव्यूह की स्थिरता को मापने के लिए एक नया उत्तम मीट्रिक प्रस्तावित किया जाता है । सर्वसम्मति आव्यूह के सीडीएफ वक्र में, निचला बायां भाग प्रतिरूप जोड़े का प्रतिनिधित्व करता है जो संभवतः ही कभी एक साथ क्लस्टर होते हैं, ऊपरी दायां भाग उन लोगों का प्रतिनिधित्व करता है जो लगभग सदैव एक साथ क्लस्टर होते हैं, जबकि मध्य खंड अलग-अलग क्लस्टरिंग रन में अस्पष्ट असाइनमेंट वाले लोगों का प्रतिनिधित्व करता है। अस्पष्ट क्लस्टरिंग (पीएसी) स्कोर माप का अनुपात इस मध्य खंड की मात्रा निर्धारित करता है; और इसे अंतराल (u1, u2) ∈ [0, 1] में आने वाले सर्वसम्मति सूचकांकों के साथ प्रतिरूप जोड़े के अंश के रूप में परिभाषित किया गया है, जहां u1 0 के समीप का मान है और u21 के समीप का मान है (उदाहरण के लिए u1 =0.1 और u2=0.9). पीएसी का कम मूल्य एक सपाट मध्य खंड को इंगित करता है, और क्रमबद्ध क्लस्टरिंग रन में असंगत असाइनमेंट की कम दर को इंगित करता है। इसलिए सबसे कम पीएसी वाले K मान से क्लस्टर की इष्टतम संख्या का अनुमान लगाया जा सकता है।[6][7]

संबंधित कार्य

  1. क्लस्टरिंग पहनावा (स्ट्रेहल और घोष): उन्होंने समस्या के लिए विभिन्न सूत्रीकरण पर विचार किया गया, जिनमें से अधिकांश समस्या को हाइपर-ग्राफ विभाजन समस्या में बदल देते हैं। अपने एक सूत्रीकरण में उन्होंने सहसंबंध क्लस्टरिंग समस्या के समान ग्राफ़ पर विचार किया। उन्होंने जो समाधान प्रस्तावित किया है वह ग्राफ़ के सर्वोत्तम k-विभाजन की गणना करना है, जो दूर स्थित दो नोड्स के विलय के लिए शास्ति को ध्यान में नहीं रखता है।[1]
  2. क्लस्टरिंग एकत्रीकरण (फ़र्न और ब्रोडली): उन्होंने क्लस्टरिंग एकत्रीकरण विचार को यादृच्छिक अनुमानों द्वारा प्राप्त नरम क्लस्टरिंग के संग्रह पर प्रयुक्त किया गया था। उन्होंने एक समूहीकृत एल्गोरिदम का उपयोग किया और असमान नोड्स को विलय करने के लिए शास्ति नहीं किया।[10]
  3. फ़्रेड और जैन: उन्होंने k-मीन्स एल्गोरिथम के एकाधिक रन को संयोजित करने के लिए एकल लिंकेज एल्गोरिथम का उपयोग करने का प्रस्ताव रखा।[11]
  4. डाना क्रिस्टोफ़ोर और डैन सिमोविसी: उन्होंने क्लस्टरिंग एकत्रीकरण और श्रेणीबद्ध चर के क्लस्टरिंग के बीच संबंध देखा। उन्होंने सूचना सैद्धांतिक दूरी के उपायों का प्रस्ताव दिया था और उन्होंने सर्वोत्तम एकत्रीकरण समाधान खोजने के लिए आनुवंशिक एल्गोरिदम का प्रस्ताव दिया गया था।[12]
  5. टॉपची और अन्य: उन्होंने क्लस्टरिंग एकत्रीकरण को अधिकतम संभावना अनुमान समस्या के रूप में परिभाषित किया, और उन्होंने सर्वसम्मति क्लस्टरिंग खोजने के लिए एक ईएम एल्गोरिदम प्रस्तावित किया गया था।[13]

कठिन पहनावा क्लस्टरिंग

स्ट्रेहल और घोष का यह दृष्टिकोण इन विभाजनों को निर्धारित करने वाली सुविधाओं या एल्गोरिदम तक पहुंच के बिना वस्तुओं के एक समूह के कई विभाजनों को एक एकल समेकित क्लस्टरिंग में संयोजित करने की समस्या का परिचय देता है। वे उच्च गुणवत्ता वाले सर्वसम्मति कार्यों को प्राप्त करने के लिए इस समस्या को हल करने की दिशा में तीन दृष्टिकोणों पर चर्चा करते हैं। उनकी तकनीकों की कम्प्यूटेशनल निवेश कम है और इससे नीचे चर्चा की गई प्रत्येक तकनीक का मूल्यांकन करना और उद्देश्य फलन के विरुद्ध परिणामों की तुलना करके सर्वोत्तम समाधान पर पहुंचना संभव हो जाता है।

कुशल सर्वसम्मति कार्य

  1. क्लस्टर-आधारित समानता विभाजन एल्गोरिदम (सीएसपीए): सीएसपीए में दो डेटा-बिंदुओं के बीच समानता को उस समूह के घटक क्लस्टरिंग की संख्या के सीधे आनुपातिक के रूप में परिभाषित किया गया है जिसमें वे एक साथ क्लस्टर किए गए हैं। अंतर्ज्ञान यह है कि दो डेटा-बिंदु जितने अधिक समान होंगे, उतनी ही अधिक संभावना होगी कि घटक क्लस्टरिंग उन्हें एक ही क्लस्टर में रखेगी। सीएसपीए सबसे सरल अनुमान है, किंतु इसकी कम्प्यूटेशनल और संचयन समिष्टता दोनों n में द्विघात हैं। SC3 सीएसपीए प्रकार के एल्गोरिदम का एक उदाहरण है।[14] निम्नलिखित दो विधियाँ कम्प्यूटेशनल रूप से कम मूल्यवान हैं:
  2. हाइपर-ग्राफ विभाजन एल्गोरिदम (एचजीपीए): एचजीपीए एल्गोरिदम पिछली पद्धति की तुलना में सर्वसम्मति क्लस्टरिंग को खोजने के लिए एक बहुत अलग दृष्टिकोण अपनाता है। क्लस्टर एन्सेम्बल समस्या को न्यूनतम संख्या में हाइपरएज को विभाजित हाइपरग्राफ को विभाजित करने के रूप में तैयार किया गया है। वे मेटीस का उपयोग करते हैं जो एक हाइपरग्राफ विभाजन पैकेज सिस्टम है।
  3. मेटा-क्लस्टरिंग एल्गोरिदम (एमसीएलए): मेटा-क्लस्टरिंग एल्गोरिदम (एमसीएलए) क्लस्टरिंग क्लस्टर पर आधारित है। सबसे पहले, यह क्लस्टर पत्राचार समस्या को हल करने का प्रयास करता है और फिर डेटा-बिंदुओं को अंतिम सर्वसम्मति क्लस्टर में रखने के लिए वोटिंग का उपयोग करता है। क्लस्टर पत्राचार समस्या को समूह के अलग-अलग समूहों में पहचाने गए समूहों को समूहीकृत करके हल किया जाता है। क्लस्टरिंग मेटीस और स्पेक्ट्रल क्लस्टरिंग का उपयोग करके की जाती है।

नरम क्लस्टरिंग समूह

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

  1. एससीएसपीए: समानता आव्यूह की गणना करके सीएसपीए का विस्तार करता है। प्रत्येक वस्तु को आयामी स्थान में एक बिंदु के रूप में देखा जाता है, प्रत्येक आयाम एक क्लस्टर से संबंधित होने की संभावना के अनुरूप होता है। यह तकनीक पहले वस्तुओं को एक लेबल-स्पेस में बदल देती है और फिर वस्तुओं का प्रतिनिधित्व करने वाले वैक्टरों के बीच डॉट उत्पाद को उनकी समानता के रूप में व्याख्या करती है।
  2. एसएमसीएलए: सॉफ्ट क्लस्टरिंग को इनपुट के रूप में स्वीकार करके एमसीएलए का विस्तार करता है। एसएमसीएलए की कार्यप्रणाली को निम्नलिखित चरणों में विभाजित किया जा सकता है:
    • क्लस्टरों का सॉफ्ट मेटा-ग्राफ़ बनाएं
    • क्लस्टरों को मेटा-क्लस्टरों में समूहित करें
    • वेटिंग का उपयोग करके मेटा-क्लस्टर को संक्षिप्त करें
    • वस्तुओं के लिए प्रतिस्पर्धा करें
  3. एसएचबीजीएफ: समूहों और उदाहरणों को नोड्स के रूप में एक द्विदलीय ग्राफ के रूप में दर्शाता है, और उदाहरणों और जिन समूहों से वे संबंधित हैं, उनके बीच किनारों को दर्शाता है।[16] इस दृष्टिकोण को नरम संयोजनों पर विचार करने के लिए तुच्छ रूप से अनुकूलित किया जा सकता है क्योंकि ग्राफ़ विभाजन एल्गोरिथ्म मेटिस विभाजित होने वाले ग्राफ़ के किनारों पर भार स्वीकार करता है। एसएचबीजीएफ में, ग्राफ़ में n+t शीर्ष हैं, जहां t अंतर्निहित समूहों की कुल संख्या है।
  4. 'बायेसियन सर्वसम्मति क्लस्टरिंग (बीसीसी)': नरम सर्वसम्मति क्लस्टरिंग के लिए पूरी तरह से बायेसियन संभाव्यता मॉडल को परिभाषित करता है जिसमें विभिन्न इनपुट डेटा या विभिन्न संभाव्यता मॉडल द्वारा परिभाषित एकाधिक स्रोत क्लस्टरिंग को आम सहमति क्लस्टरिंग के लिए शिथिल रूप से पालन करने के लिए माना जाता है।[17] अलग-अलग क्लस्टरिंग और सर्वसम्मति क्लस्टरिंग के लिए पूर्ण पश्च भाग का अनुमान गिब्स प्रतिरूप के माध्यम से एक साथ लगाया जाता है।
  5. एनसेंबल क्लस्टरिंग फ़ज़िफिकेशन मीन्स (ईसीएफ-मीन्स): ईसीएफ-मीन्स एक क्लस्टरिंग एल्गोरिदम है, जो चुने हुए एल्गोरिदम (k-साधन ) के विभिन्न रन द्वारा प्राप्त किए गए अलग-अलग क्लस्टरिंग परिणामों को एक ही अंतिम क्लस्टरिंग कॉन्फ़िगरेशन में जोड़ता है।[18]

संदर्भ

  1. 1.0 1.1 Strehl, Alexander; Ghosh, Joydeep (2002). "Cluster ensembles – a knowledge reuse framework for combining multiple partitions" (PDF). Journal on Machine Learning Research (JMLR). 3: 583–617. doi:10.1162/153244303321897735. This paper introduces the problem of combining multiple partitionings of a set of objects into a single consolidated clustering without accessing the features or algorithms that determined these partitionings. We first identify several application scenarios for the resultant 'knowledge reuse' framework that we call cluster ensembles. The cluster ensemble problem is then formalized as a combinatorial optimization problem in terms of shared mutual information
  2. VEGA-PONS, SANDRO; RUIZ-SHULCLOPER, JOSÉ (1 May 2011). "A Survey of Clustering Ensemble Algorithms". International Journal of Pattern Recognition and Artificial Intelligence. 25 (3): 337–372. doi:10.1142/S0218001411008683. S2CID 4643842.
  3. Filkov, Vladimir (2003). "Integrating microarray data by consensus clustering". Proceedings. 15th IEEE International Conference on Tools with Artificial Intelligence. pp. 418–426. CiteSeerX 10.1.1.116.8271. doi:10.1109/TAI.2003.1250220. ISBN 978-0-7695-2038-4. S2CID 1515525. {{cite book}}: |journal= ignored (help)
  4. Bonizzoni, Paola; Della Vedova, Gianluca; Dondi, Riccardo; Jiang, Tao (2008). "सहसंबंध क्लस्टरिंग और सर्वसम्मति क्लस्टरिंग के अनुमान पर". Journal of Computer and System Sciences. 74 (5): 671–696. doi:10.1016/j.jcss.2007.06.024.
  5. Monti, Stefano; Tamayo, Pablo; Mesirov, Jill; Golub, Todd (2003-07-01). "Consensus Clustering: A Resampling-Based Method for Class Discovery and Visualization of Gene Expression Microarray Data". Machine Learning (in English). 52 (1): 91–118. doi:10.1023/A:1023949509487. ISSN 1573-0565.
  6. 6.0 6.1 6.2 6.3 Şenbabaoğlu, Y.; Michailidis, G.; Li, J. Z. (2014). "वर्ग खोज में सर्वसम्मति क्लस्टरिंग की महत्वपूर्ण सीमाएँ". Scientific Reports. 4: 6207. Bibcode:2014NatSR...4E6207.. doi:10.1038/srep06207. PMC 4145288. PMID 25158761.
  7. 7.0 7.1 Şenbabaoğlu, Y.; Michailidis, G.; Li, J. Z. (Feb 2014). "वर्ग खोज के लिए सर्वसम्मति क्लस्टरिंग का पुनर्मूल्यांकन". bioRxiv 10.1101/002642.
  8. 8.0 8.1 Liu, Yufeng; Hayes, David Neil; Nobel, Andrew; Marron, J. S. (2008-09-01). "Statistical Significance of Clustering for High-Dimension, Low–Sample Size Data". Journal of the American Statistical Association. 103 (483): 1281–1293. doi:10.1198/016214508000000454. ISSN 0162-1459. S2CID 120819441.
  9. Tibshirani, Robert; Walther, Guenther; Hastie, Trevor (2001). "अंतराल आँकड़ों के माध्यम से डेटा सेट में समूहों की संख्या का अनुमान लगाना". Journal of the Royal Statistical Society, Series B (Statistical Methodology) (in English). 63 (2): 411–423. doi:10.1111/1467-9868.00293. ISSN 1467-9868. S2CID 59738652.
  10. Fern, Xiaoli; Brodley, Carla (2004). "Cluster ensembles for high dimensional clustering: an empirical study". J Mach Learn Res. 22.
  11. Fred, Ana L.N.; Jain, Anil K. (2005). "साक्ष्य संचय का उपयोग करके कई क्लस्टरिंग का संयोजन" (PDF). IEEE Transactions on Pattern Analysis and Machine Intelligence. Institute of Electrical and Electronics Engineers (IEEE). 27 (6): 835–850. doi:10.1109/tpami.2005.113. ISSN 0162-8828. PMID 15943417. S2CID 10316033.
  12. रेफरी>Dana Cristofor, Dan Simovici (February 2002). "सूचना-सैद्धांतिक-आधारित आनुवंशिक एल्गोरिदम का उपयोग करके माध्यिका विभाजन ढूँढना" (PDF). Journal of Universal Computer Science. 8 (2): 153–172. doi:10.3217/jucs-008-02-0153.<nowiki>
  13. संदर्भ>अलेक्जेंडर टॉपची, अनिल के. जैन, विलियम पंच। क्लस्टरिंग एन्सेम्बल्स: सर्वसम्मति और कमजोर विभाजन के मॉडल। डेटा माइनिंग पर आईईईई अंतर्राष्ट्रीय सम्मेलन, आईसीडीएम 03 और डेटा माइनिंग पर एसआईएएम अंतर्राष्ट्रीय सम्मेलन, एसडीएम 04<nowiki>
  14. Kiselev, Vladimir Yu; Kirschner, Kristina; Schaub, Michael T; Andrews, Tallulah; Yiu, Andrew; Chandra, Tamir; Natarajan, Kedar N; Reik, Wolf; Barahona, Mauricio; Green, Anthony R; Hemberg, Martin (May 2017). "SC3: consensus clustering of single-cell RNA-seq data". Nature Methods (in English). 14 (5): 483–486. doi:10.1038/nmeth.4236. ISSN 1548-7091. PMC 5410170. PMID 28346451.
  15. Kunal Punera, Joydeep Ghosh. Consensus Based Ensembles of Soft Clusterings
  16. Solving cluster ensemble problems by bipartite graph partitioning, Xiaoli Zhang Fern and Carla Brodley, Proceedings of the twenty-first international conference on Machine learning
  17. Lock, E.F.; Dunson, D.B. (2013). "बायेसियन सर्वसम्मति क्लस्टरिंग". Bioinformatics. 29 (20): 2610–2616. arXiv:1302.7280. Bibcode:2013arXiv1302.7280L. doi:10.1093/bioinformatics/btt425. PMC 3789539. PMID 23990412.
  18. Zazzaro, Gaetano; Martone, Angelo (2018). "ईसीएफ-साधन - एन्सेम्बल क्लस्टरिंग फ़ज़िफिकेशन साधन। क्लस्टरिंग एकत्रीकरण, फ़ज़िफ़िकेशन और अनुकूलन के लिए एक नया एल्गोरिदम". IMM 2018: The Eighth International Conference on Advances in Information Mining and Management. [1]
  • Aristides Gionis, Heikki Mannila, Panayiotis Tsaparas. Clustering Aggregation. 21st International Conference on Data Engineering (ICDE 2005)
  • Hongjun Wang, Hanhuai Shan, Arindam Banerjee. Bayesian Cluster Ensembles[permanent dead link], SIAM International Conference on Data Mining, SDM 09
  • Nguyen, Nam; Caruana, Rich (2007). "Consensus Clusterings". Seventh IEEE International Conference on Data Mining (ICDM 2007). IEEE. pp. 607–612. doi:10.1109/icdm.2007.73. ISBN 978-0-7695-3018-5. ...we address the problem of combining multiple clusterings without access to the underlying features of the data. This process is known in the literature as clustering ensembles, clustering aggregation, or consensus clustering. Consensus clustering yields a stable and robust final clustering that is in agreement with multiple clusterings. We find that an iterative EM-like method is remarkably effective for this problem. We present an iterative algorithm and its variations for finding clustering consensus. An extensive empirical study compares our proposed algorithms with eleven other consensus clustering methods on four data sets using three different clustering performance metrics. The experimental results show that the new ensemble clustering methods produce clusterings that are as good as, and often better than, these other methods.