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

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

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

Main article: Cluster analysis

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

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

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

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

होने देना $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$.

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

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

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

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

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

एल्गोरिदम

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

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

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

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

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

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

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

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

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

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