ROCK,लिंक का उपयोग करके मजबूत क्लस्टरिंग के लिए खड़ा है। यह एक पदानुक्रमित क्लस्टरिंग एल्गोरिथ्म है जो श्रेणीबद्ध विशेषताओं वाले डेटा के लिए लिंक की अवधारणा (दो वस्तुओं के बीच आम पड़ोसियों की संख्या) का विश्लेषण करता है। यह प्रदर्शित करता है कि श्रेणीबद्ध जानकारी को क्लस्टर करते समय इस तरह की दूरी के डेटा से उच्च गुणवत्ता वाले क्लस्टर नहीं बन सकते हैं।
इसके अलावा, अधिकांश क्लस्टरिंग एल्गोरिदम क्लस्टरिंग करते समय बिंदुओं के बीच केवल समानता बनाते हैं, यानी प्रत्येक चरण में, ऐसे बिंदु जो एक क्लस्टर में संयुक्त होते हैं। यह "स्थानीयकृत" विधि बग के लिए प्रवण है। उदाहरण के लिए, दो अलग-अलग समूहों में कुछ बिंदु या आउटलेयर हो सकते हैं जो निकट हैं; इस प्रकार, क्लस्टरिंग निर्णय लेने के लिए बिंदुओं के बीच समानता पर भरोसा करने से दो समूहों को जोड़ा जा सकता है।
ROCK एकल जोड़े बिंदुओं के पड़ोस का इलाज करके क्लस्टरिंग के लिए एक अधिक वैश्विक तरीका अपनाता है। यदि दो समान बिंदुओं के पड़ोस भी समान हैं, तो संभवतः दो बिंदु समान क्लस्टर से संबंधित हैं और इसलिए उन्हें जोड़ा जा सकता है।
दो बिंदु हैं, pi और पी<उप>जे , पड़ोसी हैं अगर सिम(pi , पी<उप>जे ) , जहां सिम एक समानता फ़ंक्शन है और θ एक उपयोगकर्ता द्वारा निर्दिष्ट सीमा है। यह सिम को एक दूरी मीट्रिक या यहां तक कि एक गैर-मीट्रिक के रूप में भी चुन सकता है जिसे सामान्यीकृत किया जाता है ताकि इसके मान 0 और 1 के बीच आ जाएं, जिसमें उच्च मान इंगित करते हैं कि अंक अधिक समान हैं।
pi . के बीच कनेक्शन की संख्या और पी<उप>जे pi . के बीच आम पड़ोसियों की संख्या के रूप में दर्शाया गया है और पी<उप>जे . यदि दो बिंदुओं के बीच लिंक की संख्या अधिक है, तो यह अधिक संभावना है कि वे समान क्लस्टर से संबंधित हों। बिंदुओं के अलग-अलग समूह के बीच संबंध में पड़ोसी डेटा बिंदुओं का इलाज करके, ROCK मानक क्लस्टरिंग विधियों की तुलना में शक्तिशाली है जो केवल बिंदु समानता पर लक्षित होते हैं।
श्रेणीबद्ध विशेषताओं सहित डेटा का एक उदाहरण बाजार टोकरी जानकारी है। इस तरह के डेटा में लेनदेन का एक डेटाबेस शामिल होता है, जहां प्रत्येक लेनदेन वस्तुओं का एक समूह होता है। लेन-देन को बूलियन विशेषताओं वाला डेटा माना जाता है, जिनमें से प्रत्येक ब्रेड या चीज़ सहित एक ही आइटम से संबंधित होता है।
लेन-देन के डेटा में, किसी आइटम से संबंधित विशेषता सही होती है यदि लेन-देन में आइटम शामिल होता है; अन्यथा, यह असत्य है। श्रेणीबद्ध विशेषताओं वाले कई डेटा सेट एक ही तरीके से प्रबंधित किए जा सकते हैं। ROCK की पड़ोसियों और लिंक की शर्तें दो "बिंदुओं" या लेन-देन के बीच समान हैं, Ti और टी<उप>जे , को जैककार्ड गुणांक के साथ
. के रूप में दर्शाया गया है$$\mathrm{sim(T_{i},T_{j})=\frac{|T_{i} \cap T_{j}|}{|T_{i} \कप T_{j}|}}$ $
रॉक पहले एक समानता सीमा और साझा पड़ोसियों के दृष्टिकोण का उपयोग करके किसी दिए गए डेटा समानता मैट्रिक्स से एक स्पैस ग्राफ उत्पन्न करता है। यह विरल ग्राफ पर एग्लोमेरेटिव पदानुक्रमित क्लस्टरिंग को लागू कर सकता है। एक अच्छाई उपाय क्लस्टरिंग की गणना कर सकता है। उच्च डेटा सेट तक स्केलिंग के लिए यादृच्छिक नमूनाकरण का उपयोग किया जा सकता है।
ROCK की सबसे खराब समय जटिलता O(n 2 . है + एनएम<उप>एम मी<उप>ए + n 2 लॉग<उप>एन ) जहां एम<उप>एम और ma तदनुसार, पड़ोसियों की अधिकतम और औसत संख्या है और n वस्तुओं की संख्या है।