सहसंबंध क्लस्टरिंग

क्लस्टरिंग डेटा बिंदुओं को उनकी समानता के आधार पर समूहों में विभाजित करने की समस्या है। सहसंबंध क्लस्टरिंग वस्तुओं के एक समुच्चय को पहले से उस संख्या को निर्दिष्ट किए बिना क्लस्टर की इष्टतम संख्या में क्लस्टर करने की एक विधि प्रदान करता है।^[1]

समस्या का विवरण

मशीन लर्निंग (यंत्र अधिगम) में, सहसंबंध क्लस्टरिंग या क्लस्टर संपादन एक ऐसे परिदृश्य में संचालित होता है जहां वस्तुओं के वास्तविक प्रतिनिधित्व के बजाय वस्तुओं के बीच संबंधों को जाना जाता है। उदाहरण के लिए, एक भारित ग्राफ $G=(V,E)$ दिया गया है जहां कोर का वजन इंगित करता है कि क्या दो नोड समान हैं (धनात्मक कोर का वजन) या अलग (ऋणात्मक कोर का वजन), कार्य एक क्लस्टरिंग ढूंढना है जो या तो समझौतों को अधिकतम करता है (क्लस्टर के भीतर धनात्मक कोर के वजन का योग और समूहों के बीच ऋणात्मक कोर के वजन के योग का पूर्ण मूल्य) या असहमति को कम करता है (क्लस्टर के भीतर ऋणात्मक कोर के वजन के योग का पूर्ण मूल्य और समूहों में धनात्मक कोर के वजन का योग)। अन्य क्लस्टरिंग एल्गोरिदम के विपरीत, इसके लिए पहले से क्लस्टर $k$ की संख्या चुनने की आवश्यकता नहीं होती है क्योंकि कटे हुए कोरों के वजन के योग को कम करने का उद्देश्य, क्लस्टर की संख्या से स्वतंत्र है।

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

लेकिन, सामान्य तौर पर, एक ग्राफ़ में एक आदर्श क्लस्टरिंग नहीं हो सकती है। उदाहरण के लिए, दिए गए नोड्स a,b,c जैसे कि a,b, और a,c समान हैं जबकि b,c असमान हैं, सही क्लस्टरिंग संभव नहीं है। ऐसे मामलों में, कार्य एक क्लस्टरिंग ढूंढना है जो समझौतों की संख्या को अधिकतम करता है (क्लस्टर के अंदर + कोरों की संख्या और क्लस्टर के बीच - कोरों की संख्या) या असहमति की संख्या को कम करता है (क्लस्टर के अंदर - कोरों की संख्या और क्लस्टर के बीच + कोरों की संख्या)। समझौतों को अधिकतम करने की यह समस्या एनपी-पूर्ण है (मल्टीवे कट समस्या भारित समझौतों को अधिकतम करने के लिए कम हो जाती है और त्रिकोणों में विभाजन की समस्या^[2] को बिना भारित संस्करण में कम किया जा सकता है)।

औपचारिक परिभाषाएँ

मान लीजिए $G=(V,E)$ नोड्स के साथ एक ग्राफ़ बनें $V$ और कोर $E$ . का एक समूहन $G$ इसके नोड समुच्चय का एक विभाजन है $\Pi =\{\pi _{1},\dots ,\pi _{k}\}$ साथ $V=\pi _{1}\cup \dots \cup \pi _{k}$ और $\pi _{i}\cap \pi _{j}=\emptyset$ के लिए $i\neq j$ है।

किसी दिए गए क्लस्टरिंग के लिए $\Pi$ , मान लीजिए $\delta (\Pi )=\{\{u,v\}\in E\mid \{u,v\}\not \subseteq \pi \;\forall \pi \in \Pi \}$ के कोरों के उपसमुच्चय को निरूपित करें $G$ जिनके समापन बिंदु क्लस्टरिंग के विभिन्न उपसमूहों में हैं $\Pi$ . अब चलो $w\colon E\to \mathbb {R} _{\geq 0}$ एक ऐसा फलन बनें जो ग्राफ़ के प्रत्येक कोर पर एक गैर-ऋणात्मक भार निर्दिष्ट करता है और चलो $E=E^{+}\cup E^{-}$ कोरों का एक विभाजन आकर्षक हो ( $E^{+}$ ) और प्रतिकारक ( $E^{-}$ ) कोर है।

न्यूनतम असहमति सहसंबंध क्लस्टरिंग समस्या निम्नलिखित अनुकूलन समस्या है:

{\begin{aligned}&{\underset {\Pi }{\operatorname {minimize} }}&&\sum _{e\in E^{+}\cap \delta (\Pi )}w_{e}+\sum _{e\in E^{-}\setminus \delta (\Pi )}w_{e}\;.\end{aligned}}

यहाँ, समुच्चय

E^{+}\cap \delta (\Pi )

इसमें आकर्षक कोर सम्मिलित हैं जिनके समापन बिंदु क्लस्टरिंग के संबंध में विभिन्न घटकों में हैं

\Pi

और समुच्चय

E^{-}\setminus \delta (\Pi )

इसमें प्रतिकारक कोर सम्मिलित हैं जिनके समापन बिंदु क्लस्टरिंग के संबंध में एक ही घटक

\Pi

में हैं .

इन दोनों समुच्चय में वे सभी कोर सम्मिलित हैं जो क्लस्टरिंग से असहमत हैं $\Pi$ .

न्यूनतम असहमति सहसंबंध क्लस्टरिंग समस्या के समान, अधिकतम सहमति सहसंबंध क्लस्टरिंग समस्या को इस प्रकार परिभाषित किया गया है

 ${\begin{aligned}&{\underset {\Pi }{\operatorname {maximize} }}&&\sum _{e\in E^{+}\setminus \delta (\Pi )}w_{e}+\sum _{e\in E^{-}\cap \delta (\Pi )}w_{e}\;.\end{aligned}}$

यहाँ, समुच्चय $E^{+}\setminus \delta (\Pi )$ इसमें आकर्षक कोर सम्मिलित हैं जिनके समापन बिंदु क्लस्टरिंग के संबंध में एक ही घटक में हैं $\Pi$ और समुच्चय $E^{-}\cap \delta (\Pi )$ इसमें प्रतिकारक कोर सम्मिलित हैं जिनके समापन बिंदु क्लस्टरिंग के संबंध में विभिन्न घटकों में हैं $\Pi$ इन दोनों समुच्चय में वे सभी कोर सम्मिलित हैं जो क्लस्टरिंग $\Pi$ से सहमत हैं .

सहसंबंध क्लस्टरिंग समस्या को गैर-ऋणात्मक कोर भार और कोरों के आकर्षक और प्रतिकारक कोरों में विभाजन के संदर्भ में तैयार करने के बजाय, कोरों के समुच्चय को स्पष्ट रूप से विभाजित किए बिना धनात्मक और ऋणात्मक कोर लागत के संदर्भ में भी समस्या तैयार की जाती है।

दिए गए वज़न के लिए $w\colon E\to \mathbb {R} _{\geq 0}$ और एक दिया गया विभाजन $E=E^{+}\cup E^{-}$ कोरों को आकर्षक और प्रतिकारक कोरों में, कोर की लागत को परिभाषित किया जा सकता है

{\begin{aligned}c_{e}={\begin{cases}\;\;w_{e}&{\text{if }}e\in E^{+}\\-w_{e}&{\text{if }}e\in E^{-}\end{cases}}\end{aligned}}

सभी के लिए

e\in E

.

एक किनारा जिसके अंतिम बिंदु अलग-अलग समूहों में होते हैं उसे अंश हुआ कहा जाता है।

समुच्चय $\delta (\Pi )$ काटे गए सभी कोरों को प्रायः मल्टीकट का $G$ कहा जाता है।^[3]

न्यूनतम लागत मल्टीकट समस्या क्लस्टरिंग खोजने की समस्या है $\Pi$ का $G$ जैसे कि कोरों की लागत का योग जिनके समापन बिंदु विभिन्न समूहों में हैं न्यूनतम है:

{\begin{aligned}&{\underset {\Pi }{\operatorname {minimize} }}&&\sum _{e\in \delta (\Pi )}c_{e}\;.\end{aligned}}

न्यूनतम लागत मल्टीकट समस्या के समान, भारित ग्राफ गेम में गठबंधन संरचना निर्माण^[4] क्लस्टरिंग खोजने की समस्या इस प्रकार है कि जिन कोरों को नहीं अंश गया है उनकी लागत का योग अधिकतम है:

{\begin{aligned}&{\underset {\Pi }{\operatorname {maximize} }}&&\sum _{e\in E\setminus \delta (\Pi )}c_{e}\;.\end{aligned}}

यह दिखाया जा सकता है कि ऊपर बताई गई सभी चार समस्याएं समतुल्य हैं। इसका अर्थ यह है कि एक क्लस्टरिंग जो चार उद्देश्यों में से किसी एक के संबंध में इष्टतम है, वह सभी चार उद्देश्यों के लिए इष्टतम है।

एल्गोरिदम

बंसल एट अल.^[5] एनपी (NP)-पूर्णता प्रमाण पर चर्चा करें और इस समुच्चयिंग में क्लस्टर खोजने के लिए एक निरंतर कारक सन्निकटन एल्गोरिथ्म और बहुपद-समय सन्निकटन योजना दोनों प्रस्तुत करें। ऐलोन एट अल.^[6] समान समस्या के लिए एक यादृच्छिक 3-अनुमानीकरण एल्गोरिथ्म का प्रस्ताव करें।

CC-Pivot(G=(V,E⁺,E⁻))
    Pick random pivot i ∈ V
    Set  $C=\{i\}$ , V'=Ø
    For all j ∈ V, j ≠ i;
        If (i,j) ∈ E⁺ then
            Add j to C
        Else (If (i,j) ∈ E⁻)
            Add j to V'
    Let G' be the subgraph induced by V'
    Return clustering C,CC-Pivot(G'

लेखक बताते हैं कि उपरोक्त एल्गोरिथम सहसंबंध क्लस्टरिंग के लिए 3-सन्निकटन एल्गोरिथम है। इस समस्या के लिए इस समय ज्ञात सबसे अच्छा बहुपद-समय सन्निकटन एल्गोरिथ्म एक रैखिक कार्यक्रम को पूर्णांकित करके ~2.06 सन्निकटन प्राप्त करता है, जैसा कि शुचि चावला, माकार्यचेव, श्राम और ग्रिगोरी यारोस्लावत्सेव द्वारा दिखाया गया है।^[7]

कारपिंस्की और शूडी^[8] पूर्ण ग्राफ़ और क्लस्टर की निश्चित संख्या पर उस समस्या के लिए एक बहुपद समय सन्निकटन योजना (पीटीएएस) का अस्तित्व साबित हुआ।

क्लस्टरों की इष्टतम संख्या

2011 में, इसे बैगन और गैलुन द्वारा दिखाया गया था^[9] सहसंबंध क्लस्टरिंग कार्यात्मकता का अनुकूलन प्रसिद्ध असतत अनुकूलन विधियों से निकटता से संबंधित है। अपने काम में उन्होंने अंतर्निहित अंतर्निहित मॉडल का एक संभाव्य विश्लेषण प्रस्तावित किया जो सहसंबंध क्लस्टरिंग कार्यात्मक को क्लस्टर की अंतर्निहित संख्या का अनुमान लगाने की अनुमति देता है। इस विश्लेषण से पता चलता है कि कार्यात्मकता उनके समूहों की संख्या की परवाह किए बिना सभी संभावित विभाजनों पर एक समान पूर्व मानती है। इस प्रकार, समूहों की संख्या से पहले एक गैर-समानता उभरती है।

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

सहसंबंध क्लस्टरिंग (डेटा माइनिंग)

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

विशेषताओं के उपसमूहों के बीच सहसंबंध के परिणामस्वरूप समूहों के विभिन्न स्थानिक आकार बनते हैं। इसलिए, क्लस्टर वस्तुओं के बीच समानता को स्थानीय सहसंबंध पैटर्न को ध्यान में रखकर परिभाषित किया गया है। इसी धारणा के साथ यह शब्द प्रस्तुत किया गया है ^[10] ऊपर चर्चा की गई धारणा के साथ-साथ। इस प्रकार के सहसंबंध क्लस्टरिंग के विभिन्न तरीकों पर चर्चा की गई है ^[11] और विभिन्न प्रकार के क्लस्टरिंग के संबंध पर चर्चा की गई है।^[12] उच्च-आयामी डेटा क्लस्टरिंग भी देखें।

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

संदर्भ

↑ Becker, Hila, "A Survey of Correlation Clustering", 5 May 2005
↑ Garey, M. and Johnson, D (W.H. Freeman and Company). (2000). Computers and Intractability: A Guide to the Theory of NP-Completeness.{{cite conference}}: CS1 maint: multiple names: authors list (link)
↑ Deza, M.; Grötschel, M.; Lautent M. (1992). "Clique-Web Facets for Multicut Polytopes". Mathematics of Operations Research. 17 (4): 981–1000. doi:10.1287/moor.17.4.981.{{cite journal}}: CS1 maint: multiple names: authors list (link)
↑ Bachrach, Yoram; Kohli, Pushmeet; Kolmogorov, Vladimir; Zadimoghaddam, Morteza (2013). "Optimal coalition structure generation in cooperative graph games". Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 27. pp. 81–87.{{cite conference}}: CS1 maint: multiple names: authors list (link)
↑ Bansal, N.; Blum, A.; Chawla, S. (2004). "सहसंबंध क्लस्टरिंग". Machine Learning. 56 (1–3): 89–113. doi:10.1023/B:MACH.0000033116.57574.95.
↑ Ailon, N.; Charikar, M.; Newman, A. (2005). "Aggregating inconsistent information". Proceedings of the thirty-seventh annual ACM symposium on Theory of computing – STOC '05. p. 684. doi:10.1145/1060590.1060692. ISBN 1581139608.
↑ Chawla, Shuchi; Makarychev, Konstantin; Schramm, Tselil; Yaroslavtsev, Grigory. "पूर्ण और पूर्ण के-पार्टाइट ग्राफ़ पर सहसंबंध क्लस्टरिंग के लिए इष्टतम एलपी राउंडिंग एल्गोरिदम के करीब". Proceedings of the 46th Annual ACM on Symposium on Theory of Computing.
↑ Karpinski, M.; Schudy, W. (2009). "Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems". Proceedings of the 41st annual ACM symposium on Symposium on theory of computing – STOC '09. p. 313. arXiv:0811.3244. doi:10.1145/1536414.1536458. ISBN 9781605585062.
↑ Bagon, S.; Galun, M. (2011) "Large Scale Correlation Clustering Optimization" arXiv:1112.2903v1
↑ Böhm, C.; Kailing, K.; Kröger, P.; Zimek, A. (2004). "Computing Clusters of Correlation Connected objects". Proceedings of the 2004 ACM SIGMOD international conference on Management of data – SIGMOD '04. p. 455. CiteSeerX 10.1.1.5.1279. doi:10.1145/1007568.1007620. ISBN 978-1581138597. S2CID 6411037.
↑ Zimek, A. (2008). Correlation Clustering (Text.PhDThesis). Ludwig-Maximilians-Universität München.
↑ Kriegel, H. P.; Kröger, P.; Zimek, A. (2009). "उच्च-आयामी डेटा को क्लस्टर करना". ACM Transactions on Knowledge Discovery from Data. 3: 1–58. doi:10.1145/1497577.1497578. S2CID 17363900.

[1] Becker, Hila, "A Survey of Correlation Clustering", 5 May 2005

[2] Garey, M. and Johnson, D (W.H. Freeman and Company). (2000). Computers and Intractability: A Guide to the Theory of NP-Completeness.{{cite conference}}: CS1 maint: multiple names: authors list (link)

[3] Deza, M.; Grötschel, M.; Lautent M. (1992). "Clique-Web Facets for Multicut Polytopes". Mathematics of Operations Research. 17 (4): 981–1000. doi:10.1287/moor.17.4.981.{{cite journal}}: CS1 maint: multiple names: authors list (link)

[4] Bachrach, Yoram; Kohli, Pushmeet; Kolmogorov, Vladimir; Zadimoghaddam, Morteza (2013). "Optimal coalition structure generation in cooperative graph games". Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 27. pp. 81–87.{{cite conference}}: CS1 maint: multiple names: authors list (link)

[5] Bansal, N.; Blum, A.; Chawla, S. (2004). "सहसंबंध क्लस्टरिंग". Machine Learning. 56 (1–3): 89–113. doi:10.1023/B:MACH.0000033116.57574.95.

[6] Ailon, N.; Charikar, M.; Newman, A. (2005). "Aggregating inconsistent information". Proceedings of the thirty-seventh annual ACM symposium on Theory of computing – STOC '05. p. 684. doi:10.1145/1060590.1060692. ISBN 1581139608.

[7] Chawla, Shuchi; Makarychev, Konstantin; Schramm, Tselil; Yaroslavtsev, Grigory. "पूर्ण और पूर्ण के-पार्टाइट ग्राफ़ पर सहसंबंध क्लस्टरिंग के लिए इष्टतम एलपी राउंडिंग एल्गोरिदम के करीब". Proceedings of the 46th Annual ACM on Symposium on Theory of Computing.

[8] Karpinski, M.; Schudy, W. (2009). "Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems". Proceedings of the 41st annual ACM symposium on Symposium on theory of computing – STOC '09. p. 313. arXiv:0811.3244. doi:10.1145/1536414.1536458. ISBN 9781605585062.

[9] Bagon, S.; Galun, M. (2011) "Large Scale Correlation Clustering Optimization" arXiv:1112.2903v1

[10] Böhm, C.; Kailing, K.; Kröger, P.; Zimek, A. (2004). "Computing Clusters of Correlation Connected objects". Proceedings of the 2004 ACM SIGMOD international conference on Management of data – SIGMOD '04. p. 455. CiteSeerX 10.1.1.5.1279. doi:10.1145/1007568.1007620. ISBN 978-1581138597. S2CID 6411037.

[11] Zimek, A. (2008). Correlation Clustering (Text.PhDThesis). Ludwig-Maximilians-Universität München.

[12] Kriegel, H. P.; Kröger, P.; Zimek, A. (2009). "उच्च-आयामी डेटा को क्लस्टर करना". ACM Transactions on Knowledge Discovery from Data. 3: 1–58. doi:10.1145/1497577.1497578. S2CID 17363900.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]