सर्वसम्मति क्लस्टरिंग

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

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

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

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

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

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

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

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

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

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

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

$C(i,j)=\left({\frac {\textstyle \sum _{h=1}^{H}M^{h}(i,j)\displaystyle }{\sum _{h=1}^{H}I^{h}(i,j)}}\right)$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

संदर्भ

• 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, 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.