ROCK এর অর্থ হল রবাস্ট ক্লাস্টারিং লিঙ্ক ব্যবহার করে। এটি একটি শ্রেণিবদ্ধ ক্লাস্টারিং অ্যালগরিদম যা শ্রেণীবদ্ধ বৈশিষ্ট্য সহ ডেটার জন্য লিঙ্কের ধারণা (দুটি বস্তুর মধ্যে সাধারণ প্রতিবেশীর সংখ্যা) বিশ্লেষণ করে। এটি দেখায় যে এই ধরনের দূরত্বের ডেটা ক্লাস্টারিক্যাল তথ্য ক্লাস্টার করার সময় উচ্চ-মানের ক্লাস্টারে নিয়ে যেতে পারে না।
তদুপরি, বেশিরভাগ ক্লাস্টারিং অ্যালগরিদমগুলি ক্লাস্টার করার সময় পয়েন্টগুলির মধ্যে কেবলমাত্র মিল তৈরি করে যেমন, প্রতিটি ধাপে, পয়েন্টগুলিকে একক ক্লাস্টারে একত্রিত করা হয়। এই "স্থানীয়" পদ্ধতি বাগ প্রবণ. উদাহরণস্বরূপ, দুটি স্বতন্ত্র ক্লাস্টারের কাছে কয়েকটি বিন্দু বা আউটলায়ার থাকতে পারে; এইভাবে, ক্লাস্টারিং সিদ্ধান্তগুলি তৈরি করার জন্য পয়েন্টগুলির মধ্যে সাদৃশ্যের উপর নির্ভর করে দুটি ক্লাস্টারকে একত্রিত করার জন্য তৈরি করতে পারে৷
ROCK একক জোড়া পয়েন্টের আশেপাশের এলাকাগুলিকে চিকিত্সা করে ক্লাস্টারিং করার জন্য আরও বিশ্বব্যাপী পদ্ধতি গ্রহণ করে। যদি দুটি অনুরূপ বিন্দুতেও একই আশেপাশের এলাকা থাকে, তাহলে দুটি পয়েন্ট সম্ভবত একই ক্লাস্টারের অন্তর্গত এবং তাই একত্রিত করা যেতে পারে৷
দুটি পয়েন্ট আছে, pi এবং pj , sim(pi হলে প্রতিবেশী , pj ) ≥ θ, যেখানে sim একটি মিল ফাংশন এবং θ একটি ব্যবহারকারী-নির্দিষ্ট থ্রেশহোল্ড। এটি একটি দূরত্ব মেট্রিক বা এমনকি একটি ননমেট্রিক হিসাবে সিম নির্বাচন করতে পারে যা স্বাভাবিক করা হয় যাতে এর মানগুলি 0 এবং 1 এর মধ্যে পড়ে, উচ্চতর মানগুলি নির্দেশ করে যে পয়েন্টগুলি আরও একই।
pi এর মধ্যে সংযোগের সংখ্যা এবং pj pi-এর মধ্যে সাধারণ প্রতিবেশীর সংখ্যা হিসাবে উপস্থাপিত হয় এবং pj . যদি দুটি পয়েন্টের মধ্যে লিঙ্কের সংখ্যা বেশি হয়, তবে সম্ভবত তারা একই ক্লাস্টারের অন্তর্গত। পয়েন্টের পৃথক গোষ্ঠীর মধ্যে সম্পর্কের ক্ষেত্রে প্রতিবেশী ডেটা পয়েন্টগুলিকে চিকিত্সা করার মাধ্যমে, ROCK স্ট্যান্ডার্ড ক্লাস্টারিং পদ্ধতিগুলির চেয়ে শক্তিশালী যা শুধুমাত্র পয়েন্টের সাদৃশ্যকে লক্ষ্য করে৷
শ্রেণীবদ্ধ বৈশিষ্ট্য সহ ডেটার একটি উদাহরণ হল বাজারের ঝুড়ি তথ্য। এই ধরনের ডেটা লেনদেনের একটি ডাটাবেস অন্তর্ভুক্ত করে, যেখানে প্রতিটি লেনদেন আইটেমগুলির একটি গ্রুপ। লেনদেনগুলিকে বুলিয়ান অ্যাট্রিবিউট সহ ডেটা গণ্য করা হয়, প্রতিটি একক আইটেমের সাথে সম্পর্কিত, রুটি বা পনির সহ।
একটি লেনদেনের ডেটাতে, একটি আইটেমের সাথে সম্পর্কিত বৈশিষ্ট্যটি সঠিক যদি লেনদেনে আইটেমটি অন্তর্ভুক্ত থাকে; অন্যথায়, এটা মিথ্যা। শ্রেণীবদ্ধ বৈশিষ্ট্য সহ বেশ কয়েকটি ডেটা সেট একই পদ্ধতিতে পরিচালনা করা যেতে পারে। ROCK-এর প্রতিবেশীদের শর্তাবলী এবং লিঙ্ক দুটি "পয়েন্ট" বা লেনদেনের মধ্যে একই, Ti এবং Tj , জ্যাকার্ড সহগ দ্বারা
হিসাবে উপস্থাপন করা হয়$$\mathrm{sim(T_{i},T_{j})=\frac{|T_{i} \cap T_{j}|}{|T_{i} \cup T_{j}|}}$ $
ROCK প্রথমে একটি সাদৃশ্য থ্রেশহোল্ড এবং ভাগ করা প্রতিবেশীদের দৃষ্টিভঙ্গি ব্যবহার করে একটি প্রদত্ত ডেটা সাদৃশ্য ম্যাট্রিক্স থেকে একটি স্পার্স গ্রাফ তৈরি করে। এটি স্পার্স গ্রাফে সমষ্টিগত শ্রেণিবিন্যাস ক্লাস্টারিং প্রয়োগ করতে পারে। একটি ভালতা পরিমাপ ক্লাস্টারিং গণনা করতে পারেন. এলোমেলো নমুনা উচ্চ ডেটা সেট পর্যন্ত স্কেলিং করার জন্য ব্যবহার করা যেতে পারে।
ROCK-এর সবচেয়ে খারাপ ক্ষেত্রে সময় জটিলতা হল O(n 2 + nmm ma + n 2 লগn ) যেখানে mm এবং ma প্রতিবেশীর সর্বোচ্চ এবং গড় সংখ্যা, সেই অনুযায়ী, হল এবং n হল বস্তুর সংখ্যা।
