ROCK क्या है?

ROCK का अर्थ है Robust Clustering using links (लिंक्स का उपयोग करके मजबूत क्लस्टरिंग)। यह एक पदानुक्रमित क्लस्टरिंग एल्गोरिदम है जो श्रेणीबद्ध विशेषताओं वाले डेटा के लिए लिंक्स की अवधारणा (दो ऑब्जेक्ट्स के बीच सामान्य पड़ोसियों की संख्या) का विश्लेषण करता है। यह दर्शाता है कि ऐसी दूरी डेटा श्रेणीबद्ध जानकारी क्लस्टर करते समय उच्च-गुणवत्ता वाले क्लस्टर्स का नेतृत्व नहीं कर सकती।

इसके अलावा, अधिकांश क्लस्टरिंग एल्गोरिदम क्लस्टरिंग करते समय केवल बिंदुओं के बीच समानता पर विचार करते हैं यानी, प्रत्येक चरण पर, बिंदुओं को एक ही क्लस्टर में जोड़ा जाता है। यह "स्थानीयकृत" विधि बग्स के लिए प्रवण है। उदाहरण के लिए, दो अलग-अलग क्लस्टर्स के कुछ बिंदु या बाहरी मान निकट हो सकते हैं; इस प्रकार, क्लस्टरिंग निर्णय लेने के लिए बिंदुओं के बीच समानता पर भरोसा करने से दो क्लस्टर्स को जोड़ा जा सकता है।

ROCK व्यक्तिगत जोड़े के बिंदुओं के पड़ोस पर विचार करके क्लस्टरिंग के लिए एक अधिक वैश्विक दृष्टिकोण लेता है। यदि दो समान बिंदुओं के भी समान पड़ोस हैं, तो दो बिंदु संभवतः समान क्लस्टर से संबंधित हैं और इसलिए जोड़े जा सकते हैं।

दो बिंदु, p_i और p_j, पड़ोसी हैं यदि sim(p_i, p_j) ≥ θ, जहां sim एक समानता फ़ंक्शन है और θ एक उपयोगकर्ता-निर्दिष्ट सीमा है। यह दूरी मेट्रिक या यहां तक कि एक गैर-मेट्रिक चुन सकता है जिसे सामान्यीकृत किया गया है ताकि इसके मूल्य 0 और 1 के बीच हों, उच्च मूल्य यह दर्शाते हैं कि बिंदु अधिक समान हैं।

p_i और p_j के बीच कनेक्शन की संख्या को p_i और p_j के बीच सामान्य पड़ोसियों की संख्या के रूप में दर्शाया जाता है। यदि दो बिंदुओं के बीच लिंक्स की संख्या अधिक है, तो यह अधिक संभावना है कि वे समान क्लस्टर से संबंधित हैं। व्यक्तिगत बिंदुओं के समूह के बीच संबंध में पड़ोसी डेटा बिंदुओं पर विचार करके, ROCK मानक क्लस्टरिंग विधियों की तुलना में शक्तिशाली है जो केवल बिंदु समानता पर ध्यान केंद्रित करती हैं।

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

एक लेनदेन के डेटा में, एक आइटम से मेल खाने वाली विशेषता सही है यदि लेनदेन में आइटम शामिल है; अन्यथा, यह गलत है। श्रेणीबद्ध विशेषताओं वाले कई डेटा सेट्स को इसी तरह से प्रबंधित किया जा सकता है। ROCK के पड़ोसियों और लिंक्स की शर्तें दो "पॉइंट्स" या लेनदेन, T_i और T_j के बीच जैकार्ड गुणांक के साथ दर्शाई जाती हैं:

$$\mathrm{sim(T_{i},T_{j})=\frac{|T_{i} \cap T_{j}|}{|T_{i} \cup T_{j}|}}$$

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

ROCK की सबसे खराब स्थिति समय जटिलता O(n² + nm_mm_a + n²log_n) है जहां m_m और m_a क्रमशः अधिकतम और औसत पड़ोसियों की संख्या हैं, और n ऑब्जेक्ट्स की संख्या है।