सहसंबंध क्लस्टरिंग: Difference between revisions

Revision as of 11:36, 24 July 2023

क्लस्टरिंग डेटा बिंदुओं को उनकी समानता के आधार पर समूहों में विभाजित करने की समस्या है। सहसंबंध क्लस्टरिंग वस्तुओं के एक समुच्चय को पहले से उस संख्या को निर्दिष्ट किए बिना क्लस्टर की इष्टतम संख्या में क्लस्टर करने की एक विधि प्रदान करता है।^[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 )$ काटे गए सभी किनारों को प्रायः मल्टीकट कहा जाता है^[3] का $G$ .

न्यूनतम लागत मल्टीकट समस्या क्लस्टरिंग खोजने की समस्या है $\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-अनुमानीकरण एल्गोरिथ्म का प्रस्ताव करें।

सीसी-धुरी(जी=(वी,ई⁺,ई⁻))
    यादृच्छिक धुरी i ∈ V चुनें
    तय करना  $C=\{i\}$ , वी'=Ø
    सभी j ∈ V, j ≠ i के लिए;
        यदि (i,j) ∈ E⁺फिर
            C में j जोड़ें
        अन्यथा (यदि (i,j) ∈ E⁻)
            J को V' में जोड़ें
    मान लीजिए G' V' से प्रेरित उपग्राफ है
    रिटर्न क्लस्टरिंग सी,सीसी-पिवोट(जी')

लेखक बताते हैं कि उपरोक्त एल्गोरिथम सहसंबंध क्लस्टरिंग के लिए 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]

@@ Line 1: / Line 1: @@
-क्लस्टरिंग डेटा बिंदुओं को उनकी समानता के आधार पर समूहों में विभाजित करने की समस्या है। सहसंबंध क्लस्टरिंग वस्तुओं के एक सेट को पहले से उस संख्या को निर्दिष्ट किए बिना क्लस्टर की इष्टतम संख्या में क्लस्टर करने की एक विधि प्रदान करता है।<ref>Becker, Hila, [http://www.cs.columbia.edu/~hila/clustering.pdf "A Survey of Correlation Clustering", 5 May 2005]</ref>
+क्लस्टरिंग डेटा बिंदुओं को उनकी समानता के आधार पर समूहों में विभाजित करने की समस्या है। सहसंबंध क्लस्टरिंग वस्तुओं के एक समुच्चय को पहले से उस संख्या को निर्दिष्ट किए बिना क्लस्टर की इष्टतम संख्या में क्लस्टर करने की एक विधि प्रदान करता है।<ref>Becker, Hila, [http://www.cs.columbia.edu/~hila/clustering.pdf "A Survey of Correlation Clustering", 5 May 2005]</ref>
 ==समस्या का विवरण==
 {{main article|Cluster analysis}}
-[[ यंत्र अधिगम ]] में, सहसंबंध क्लस्टरिंग या क्लस्टर संपादन एक ऐसे परिदृश्य में संचालित होता है जहां वस्तुओं के वास्तविक प्रतिनिधित्व के बजाय वस्तुओं के बीच संबंधों को जाना जाता है। उदाहरण के लिए, एक [[भारित ग्राफ]]़ दिया गया है <math>G=(V,E)</math> जहां किनारे का वजन इंगित करता है कि क्या दो नोड समान हैं (सकारात्मक किनारे का वजन) या अलग (नकारात्मक किनारे का वजन), कार्य एक क्लस्टरिंग ढूंढना है जो या तो समझौतों को अधिकतम करता है (क्लस्टर के भीतर सकारात्मक किनारे के वजन का योग और योग का पूर्ण मूल्य) समूहों के बीच नकारात्मक किनारे के वजन का) या असहमति को कम करता है (एक क्लस्टर के भीतर नकारात्मक किनारे के वजन के योग का पूर्ण मूल्य और समूहों में सकारात्मक किनारे के वजन का योग)। अन्य क्लस्टरिंग एल्गोरिदम के विपरीत, इसमें डेटा सेट में क्लस्टर की संख्या निर्धारित करने की आवश्यकता नहीं होती है <math>k</math> अग्रिम में क्योंकि उद्देश्य, कटे हुए किनारों के वजन के योग को कम करना, समूहों की संख्या से स्वतंत्र है।
+मशीन लर्निंग ([[ यंत्र अधिगम |यंत्र अधिगम]]) में, सहसंबंध क्लस्टरिंग या क्लस्टर संपादन एक ऐसे परिदृश्य में संचालित होता है जहां वस्तुओं के वास्तविक प्रतिनिधित्व के बजाय वस्तुओं के बीच संबंधों को जाना जाता है। उदाहरण के लिए, एक भारित ग्राफ <math>G=(V,E)</math> दिया गया है जहां कोर का वजन इंगित करता है कि क्या दो नोड समान हैं (धनात्मक कोर का वजन) या अलग (ऋणात्मक कोर का वजन), कार्य एक क्लस्टरिंग ढूंढना है जो या तो समझौतों को अधिकतम करता है (क्लस्टर के भीतर धनात्मक कोर के वजन का योग और समूहों के बीच ऋणात्मक कोर के वजन के योग का पूर्ण मूल्य) या असहमति को कम करता है (क्लस्टर के भीतर ऋणात्मक कोर के वजन के योग का पूर्ण मूल्य और समूहों में धनात्मक कोर के वजन का योग)। अन्य क्लस्टरिंग एल्गोरिदम के विपरीत, इसके लिए पहले से क्लस्टर <math>k</math> की संख्या चुनने की आवश्यकता नहीं होती है क्योंकि कटे हुए किनारों के वजन के योग को कम करने का उद्देश्य, क्लस्टर की संख्या से स्वतंत्र है।
-एक संपूर्ण क्लस्टरिंग ढूंढना संभव नहीं हो सकता है, जहां सभी समान आइटम एक क्लस्टर में होते हैं जबकि सभी असमान आइटम अलग-अलग क्लस्टर में होते हैं। यदि ग्राफ़ वास्तव में एक पूर्ण क्लस्टरिंग स्वीकार करता है, तो बस सभी नकारात्मक किनारों को हटाकर शेष ग्राफ़ में जुड़े घटकों को ढूंढने से आवश्यक क्लस्टर वापस आ जाएंगे।
-लेकिन, सामान्य तौर पर एक ग्राफ़ में पूर्ण क्लस्टरिंग नहीं हो सकती है। उदाहरण के लिए, दिए गए नोड्स ए, बी, सी जैसे कि ए, बी और ए, सी समान हैं जबकि बी, सी असमान हैं, एक पूर्ण क्लस्टरिंग संभव नहीं है। ऐसे मामलों में, कार्य एक क्लस्टरिंग ढूंढना है जो समझौतों की संख्या को अधिकतम करता है (क्लस्टर के अंदर + किनारों की संख्या और समूहों के बीच - किनारों की संख्या) या असहमति की संख्या को कम करता है (क्लस्टर के अंदर - किनारों की संख्या प्लस संख्या) समूहों के बीच + किनारों का)। समझौतों को अधिकतम करने की यह समस्या एनपी-पूर्ण है (मल्टीवे कट समस्या भारित समझौतों को अधिकतम करने और त्रिकोणों में विभाजन की समस्या को कम करती है)<ref>{{Cite conference
+एक संपूर्ण क्लस्टरिंग ढूंढना संभव नहीं हो सकता है, जहां सभी समान वस्तुएं एक क्लस्टर में होती हैं जबकि सभी असमान वस्तुएं अलग-अलग क्लस्टर में होती हैं। यदि ग्राफ़ वास्तव में एक आदर्श क्लस्टरिंग स्वीकार करता है, तो बस सभी नकारात्मक किनारों को हटाकर शेष ग्राफ़ में जुड़े हुए घटकों को ढूंढने से आवश्यक क्लस्टर वापस आ जाएंगे।
+लेकिन, सामान्य तौर पर एक ग्राफ़ में पूर्ण क्लस्टरिंग नहीं हो सकती है। उदाहरण के लिए, दिए गए नोड्स ए, बी, सी जैसे कि ए, बी और ए, सी समान हैं जबकि बी, सी असमान हैं, एक पूर्ण क्लस्टरिंग संभव नहीं है। ऐसे मामलों में, कार्य एक क्लस्टरिंग ढूंढना है जो समझौतों की संख्या को अधिकतम करता है (क्लस्टर के अंदर + किनारों की संख्या और समूहों के बीच - किनारों की संख्या) या असहमति की संख्या को कम करता है (क्लस्टर के अंदर - किनारों की संख्या प्लस संख्या) समूहों के बीच + किनारों का)। समझौतों को अधिकतम करने की यह समस्या एनपी-पूर्ण है (मल्टीवे कट समस्या भारित समझौतों को अधिकतम करने और त्रिकोणों में विभाजन की समस्या को कम करती है) बिना भारित संस्करण में घटाया जा सकता है)।
+लेकिन, सामान्य तौर पर, एक ग्राफ़ में एक आदर्श क्लस्टरिंग नहीं हो सकती है। उदाहरण के लिए, दिए गए नोड्स ''a,b,c'' जैसे कि ''a,b,'' और ''a,c'' समान हैं जबकि ''b,c'' असमान हैं, सही क्लस्टरिंग संभव नहीं है। ऐसे मामलों में, कार्य एक क्लस्टरिंग ढूंढना है जो समझौतों की संख्या को अधिकतम करता है (क्लस्टर के अंदर + किनारों की संख्या और क्लस्टर के बीच - किनारों की संख्या) या असहमति की संख्या को कम करता है (क्लस्टर के अंदर - किनारों की संख्या और क्लस्टर के बीच + किनारों की संख्या)। समझौतों को अधिकतम करने की यह समस्या एनपी-पूर्ण है (मल्टीवे कट समस्या भारित समझौतों को अधिकतम करने के लिए कम हो जाती है और त्रिकोणों में विभाजन की समस्या<ref>{{Cite conference
   | author=Garey, M. and Johnson, D (W.H. Freeman and Company).
   | title=Computers and Intractability: A Guide to the Theory of NP-Completeness
   | year=2000
-}}</ref> बिना भारित संस्करण में घटाया जा सकता है)।
+}}</ref> को बिना भारित संस्करण में कम किया जा सकता है)।
 ==औपचारिक परिभाषाएँ==
-होने देना <math>G=(V,E)</math> नोड्स के साथ एक ग्राफ़ बनें <math>V</math> और किनारे <math>E</math>. का एक समूहन <math>G</math> इसके नोड सेट का एक विभाजन है <math>\Pi=\{\pi_1,\dots,\pi_k\}</math> साथ <math>V=\pi_1 \cup \dots \cup \pi_k</math> और <math>\pi_i \cap \pi_j = \emptyset</math> के लिए <math>i \neq j</math>.
+होने देना <math>G=(V,E)</math> नोड्स के साथ एक ग्राफ़ बनें <math>V</math> और कोर <math>E</math>. का एक समूहन <math>G</math> इसके नोड समुच्चय का एक विभाजन है <math>\Pi=\{\pi_1,\dots,\pi_k\}</math> साथ <math>V=\pi_1 \cup \dots \cup \pi_k</math> और <math>\pi_i \cap \pi_j = \emptyset</math> के लिए <math>i \neq j</math>.
 किसी दिए गए क्लस्टरिंग के लिए <math>\Pi</math>, होने देना <math>\delta(\Pi) = \{\{u,v\} \in E \mid \{u, v\} \not \subseteq \pi \;\forall \pi \in \Pi\}</math> के किनारों के उपसमुच्चय को निरूपित करें <math>G</math> जिनके समापन बिंदु क्लस्टरिंग के विभिन्न उपसमूहों में हैं <math>\Pi</math>.
-अब चलो <math>w\colon E \to \R_{\geq 0} </math> एक ऐसा फ़ंक्शन बनें जो ग्राफ़ के प्रत्येक किनारे पर एक गैर-नकारात्मक भार निर्दिष्ट करता है और चलो <math>E = E^+ \cup E^- </math> किनारों का एक विभाजन आकर्षक हो (<math>E^+</math>) और प्रतिकारक (<math>E^-</math>) किनारे।
+अब चलो <math>w\colon E \to \R_{\geq 0} </math> एक ऐसा फलन बनें जो ग्राफ़ के प्रत्येक कोर पर एक गैर-ऋणात्मक भार निर्दिष्ट करता है और चलो <math>E = E^+ \cup E^- </math> किनारों का एक विभाजन आकर्षक हो (<math>E^+</math>) और प्रतिकारक (<math>E^-</math>) कोर।
 न्यूनतम असहमति सहसंबंध क्लस्टरिंग समस्या निम्नलिखित अनुकूलन समस्या है:
@@ Line 24: / Line 27: @@
 &\underset{\Pi}{\operatorname{minimize}}& & \sum_{e \in E^+ \cap \delta(\Pi)} w_e + \sum_{e \in E^- \setminus \delta(\Pi)} w_e \;.
 \end{align}</math>
-यहाँ, सेट <math>E^+ \cap \delta(\Pi)</math> इसमें आकर्षक किनारे शामिल हैं जिनके समापन बिंदु क्लस्टरिंग के संबंध में विभिन्न घटकों में हैं <math>\Pi</math> और सेट <math>E^- \setminus \delta(\Pi) </math> इसमें प्रतिकारक किनारे शामिल हैं जिनके समापन बिंदु क्लस्टरिंग के संबंध में एक ही घटक में हैं <math>\Pi</math>.
+यहाँ, समुच्चय <math>E^+ \cap \delta(\Pi)</math> इसमें आकर्षक कोर सम्मिलित हैं जिनके समापन बिंदु क्लस्टरिंग के संबंध में विभिन्न घटकों में हैं <math>\Pi</math> और समुच्चय <math>E^- \setminus \delta(\Pi) </math> इसमें प्रतिकारक कोर सम्मिलित हैं जिनके समापन बिंदु क्लस्टरिंग के संबंध में एक ही घटक में हैं <math>\Pi</math>.
-इन दोनों सेटों में वे सभी किनारे शामिल हैं जो क्लस्टरिंग से असहमत हैं <math>\Pi</math>.
+इन दोनों समुच्चय में वे सभी कोर सम्मिलित हैं जो क्लस्टरिंग से असहमत हैं <math>\Pi</math>.
 न्यूनतम असहमति सहसंबंध क्लस्टरिंग समस्या के समान, अधिकतम सहमति सहसंबंध क्लस्टरिंग समस्या को इस प्रकार परिभाषित किया गया है
@@ Line 31: / Line 34: @@
 &\underset{\Pi}{\operatorname{maximize}}& & \sum_{e \in E^+ \setminus \delta(\Pi)} w_e + \sum_{e \in E^- \cap \delta(\Pi)} w_e \;.
 \end{align}</math>
-यहाँ, सेट <math>E^+ \setminus \delta(\Pi)</math> इसमें आकर्षक किनारे शामिल हैं जिनके समापन बिंदु क्लस्टरिंग के संबंध में एक ही घटक में हैं <math>\Pi</math> और सेट <math>E^- \cap \delta(\Pi) </math> इसमें प्रतिकारक किनारे शामिल हैं जिनके समापन बिंदु क्लस्टरिंग के संबंध में विभिन्न घटकों में हैं <math>\Pi</math>.
+यहाँ, समुच्चय <math>E^+ \setminus \delta(\Pi)</math> इसमें आकर्षक कोर सम्मिलित हैं जिनके समापन बिंदु क्लस्टरिंग के संबंध में एक ही घटक में हैं <math>\Pi</math> और समुच्चय <math>E^- \cap \delta(\Pi) </math> इसमें प्रतिकारक कोर सम्मिलित हैं जिनके समापन बिंदु क्लस्टरिंग के संबंध में विभिन्न घटकों में हैं <math>\Pi</math>इन दोनों समुच्चय में वे सभी कोर सम्मिलित हैं जो क्लस्टरिंग से सहमत हैं <math>\Pi</math>.
-इन दोनों सेटों में वे सभी किनारे शामिल हैं जो क्लस्टरिंग से सहमत हैं <math>\Pi</math>.
+सहसंबंध क्लस्टरिंग समस्या को गैर-ऋणात्मक कोर भार और किनारों के आकर्षक और प्रतिकारक किनारों में विभाजन के संदर्भ में तैयार करने के बजाय, किनारों के समुच्चय को स्पष्ट रूप से विभाजित किए बिना धनात्मक और ऋणात्मक कोर लागत के संदर्भ में भी समस्या तैयार की जाती है।
-सहसंबंध क्लस्टरिंग समस्या को गैर-नकारात्मक किनारे भार और किनारों के आकर्षक और प्रतिकारक किनारों में विभाजन के संदर्भ में तैयार करने के बजाय, किनारों के सेट को स्पष्ट रूप से विभाजित किए बिना सकारात्मक और नकारात्मक किनारे लागत के संदर्भ में भी समस्या तैयार की जाती है।
+दिए गए वज़न के लिए <math>w\colon E \to \R_{\geq 0} </math> और एक दिया गया विभाजन <math>E = E^+ \cup E^- </math> किनारों को आकर्षक और प्रतिकारक किनारों में, कोर की लागत को परिभाषित किया जा सकता है
-दिए गए वज़न के लिए <math>w\colon E \to \R_{\geq 0} </math> और एक दिया गया विभाजन <math>E = E^+ \cup E^- </math> किनारों को आकर्षक और प्रतिकारक किनारों में, किनारे की लागत को परिभाषित किया जा सकता है
+<math display="block">\begin{align}
- <math display=block>\begin{align}
 c_e =
 \begin{cases}
@@ Line 46: / Line 49: @@
 एक किनारा जिसके अंतिम बिंदु अलग-अलग समूहों में होते हैं उसे काटा हुआ कहा जाता है।
-सेट <math>\delta(\Pi)</math> काटे गए सभी किनारों को अक्सर मल्टीकट कहा जाता है<ref>{{Cite journal
+समुच्चय <math>\delta(\Pi)</math> काटे गए सभी किनारों को प्रायः मल्टीकट कहा जाता है<ref>{{Cite journal
   | doi = 10.1287/moor.17.4.981
   | journal = Mathematics of Operations Research
@@ Line 58: / Line 62: @@
 न्यूनतम लागत मल्टीकट समस्या क्लस्टरिंग खोजने की समस्या है <math>\Pi</math> का <math>G</math> जैसे कि किनारों की लागत का योग जिनके समापन बिंदु विभिन्न समूहों में हैं न्यूनतम है:
-<math display=block>\begin{align}
+<math display="block">\begin{align}
 &\underset{\Pi}{\operatorname{minimize}}& & \sum_{e \in \delta(\Pi)} c_e \;.
 \end{align}</math>
@@ Line 77: / Line 81: @@
 ==एल्गोरिदम==
-बंसल एट अल.<ref>{{Cite journal | doi = 10.1023/B:MACH.0000033116.57574.95| title = सहसंबंध क्लस्टरिंग| journal = Machine Learning| volume = 56| issue = 1–3| pages = 89–113| year = 2004| last1 = Bansal | first1 = N. | last2 = Blum | first2 = A. | last3 = Chawla | first3 = S. | author3-link= Shuchi Chawla | doi-access = free}}</ref> एनपी-पूर्णता प्रमाण पर चर्चा करें और इस सेटिंग में क्लस्टर खोजने के लिए एक निरंतर कारक सन्निकटन एल्गोरिथ्म और [[बहुपद-समय सन्निकटन योजना]] दोनों प्रस्तुत करें। ऐलोन एट अल.<ref>{{Cite conference | doi = 10.1145/1060590.1060692| chapter = Aggregating inconsistent information| title = Proceedings of the thirty-seventh annual ACM symposium on Theory of computing – STOC '05| pages = 684| year = 2005| last1 = Ailon | first1 = N. | last2 = Charikar | first2 = M. | last3 = Newman | first3 = A. | isbn = 1581139608}}</ref> समान समस्या के लिए एक यादृच्छिक 3-अनुमानीकरण एल्गोरिथ्म का प्रस्ताव करें।
+बंसल एट अल.<ref>{{Cite journal | doi = 10.1023/B:MACH.0000033116.57574.95| title = सहसंबंध क्लस्टरिंग| journal = Machine Learning| volume = 56| issue = 1–3| pages = 89–113| year = 2004| last1 = Bansal | first1 = N. | last2 = Blum | first2 = A. | last3 = Chawla | first3 = S. | author3-link= Shuchi Chawla | doi-access = free}}</ref> एनपी (NP)-पूर्णता प्रमाण पर चर्चा करें और इस समुच्चयिंग में क्लस्टर खोजने के लिए एक निरंतर कारक सन्निकटन एल्गोरिथ्म और [[बहुपद-समय सन्निकटन योजना]] दोनों प्रस्तुत करें। ऐलोन एट अल.<ref>{{Cite conference | doi = 10.1145/1060590.1060692| chapter = Aggregating inconsistent information| title = Proceedings of the thirty-seventh annual ACM symposium on Theory of computing – STOC '05| pages = 684| year = 2005| last1 = Ailon | first1 = N. | last2 = Charikar | first2 = M. | last3 = Newman | first3 = A. | isbn = 1581139608}}</ref> समान समस्या के लिए एक यादृच्छिक 3-अनुमानीकरण एल्गोरिथ्म का प्रस्ताव करें।
   सीसी-धुरी(जी=(वी,ई<sup>+</sup>,ई<sup>−</sup>))

Anonymous

Search

सहसंबंध क्लस्टरिंग: Difference between revisions

Namespaces

More

Page actions

Revision as of 11:36, 24 July 2023

Contents

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

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

एल्गोरिदम

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

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

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

सहसंबंध क्लस्टरिंग: Difference between revisions

Revision as of 11:36, 24 July 2023

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

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

एल्गोरिदम

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

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

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories