CURE (Clustering Using REpresentatives)
CURE অর্থাৎ Clustering Using Representatives। এটি একটি ক্লাস্টারিং অ্যালগরিদম যা একাধিক কৌশল ব্যবহার করে এমন একটি পদ্ধতি তৈরি করে যা বড় ডেটাসেট, আউটলায়ার, এবং গোলাকার নয় এমন আকৃতি ও অ-ঐকিক আকারের ক্লাস্টার হ্যান্ডেল করতে পারে। CURE একটি ক্লাস্টারকে ক্লাস্টার থেকে অনেক রিপ্রেজেন্টেটিভ পয়েন্ট ব্যবহার করে সংজ্ঞায়িত করে।
এই পয়েন্টগুলো ক্লাস্টারর জ্যামিতি ও কাঠামো ধারণ করবে। প্রথম রিপ্রেজেন্টেটিভ পয়েন্টটি নির্বাচন করা হয় ক্লাস্টারর মাঝপথ থেকে সবচেয়ে দূরবর্তী পয়েন্ট হিসেবে, বাকি পয়েন্টগুলো নির্বাচন করা হয় যাতে সেগুলো আগে নির্বাচিত সব পয়েন্ট থেকে সবচেয়ে দূরে থাকে। এই পদ্ধতিতে, রিপ্রেজেন্টেটিভ পয়েন্টগুলো সম্পর্কে ভালোভাবে বিতরণ করা হয়। পয়েন্টের সংখ্যা একটি প্যারামিটার, কিন্তু দেখা গেছে ১০ বা তার বেশি মান ভালো কাজ করে।
রিপ্রেজেন্টেটিভ পয়েন্টগুলো নির্বাচনের পরে, সেগুলোকেও ফ্যাক্টর α দিয়ে সেন্টারের দিকে সिकोঁচিত করা হয়। এটি আউটলায়ারর প্রভাব মernel করতে সাহায্য করে, যারা সাধারণত সেন্টার থেকে বেশি দূরে থাকে এবং তাই বেশি সিকुड़ে। উদাহরণস্বরূপ, একটি রিপ্রেজেন্টেটিভ পয়েন্ট যা সেন্টার থেকে ১০ ইউনিট দূরে ছিল সেটি ৩ ইউনিট পরিবর্তিত হতে পারে (α = 0.7 জন্য), যখন ১ ইউনিট দূরত্বে থাকা একটি পয়েন্ট শুধু ০.৩ ইউনিট পরিবর্তিত হবে।
আউটলায়ার দূর করা (Outlier Removal)
CURE হায়ারার্কিক্যাল ক্লাস্টারিং প্রসেসের নির্দিষ্ট বৈশিষ্ট্যগুলোর সুবিধা নিয়ে ক্লাস্টারিং ফেজে দুটি ভিন্ন বিন্দুতে আউটলায়ার দূর করে। প্রথমে, যদি একটি ক্লাস্টার ধীরে বৃদ্ধি পায়, তবে এর মানে সেটি অধিকাংশ আউটলায়ার ধারণ করে, কারণ সংজ্ঞা অনুযায়ী, আউটলায়ার অন্যদের থেকে দূরে থাকে এবং অন্যান্য পয়েন্টের সাথে খুব কম একত্রিত হয়।
CURE-এ, আউটলায়ার দূর করার এই প্রথম প্রক্রিয়া সাধারণত তখন ঘটে যখন ক্লাস্টার সংখ্যা প্রাথমিক পয়েন্ট সংখ্যার ১/৩ হয়। আউটলায়ার দূর করার দ্বিতীয় প্রক্রিয়া ঘটে যখন ক্লাস্টার সংখ্যা K (ইচ্ছিত ক্লাস্টার সংখ্যা)ার কোটির ওপর হয়। এই সময়, ছোট ক্লাস্টারগুলোকেও দূর করা হয়।
কমপ্লেক্সিটি এবং গতি বাড়ানো
যেহেতু CURE-এর ওয়ার্স্ট-কেস কমপ্লেক্সিটি O(m²log m), তাই এটি বড় ডেটাসেটের জন্য সরাসরি ব্যবহার করা যায় না। CURE ক্লাস্টারিং প্রসেস দ্রুত করার জন্য দুটি কৌশল ব্যবহার করে। প্রথম কৌশলে একটি র্যান্ডম স্যাম্পল নেওয়া হয় এবং স্যাম্পল করা ডেটা পয়েন্টের ওপর হায়ারার্কিক্যাল ক্লাস্টারিং বাস্তবায়ন করা হয়। এরপর একটি ফাইনাল পাসে ডেটাসেটের বাকি প্রতিটি পয়েন্টকে ক্লাস্টারের সাথে বরাদ্দ করা হয় সবচেয়ে নিকটবর্তী রিপ্রেজেন্টেটিভ পয়েন্ট বেছে নিয়ে।
কিছু ক্ষেত্রে, ক্লাস্টারিং-এর জন্য প্রয়োজনীয় স্যাম্পল বড় হয় এবং একটি দ্বিতীয় কৌশল দরকার। এই পরিস্থিতিতে, CURE স্যাম্পল ডেটাকে পার্টিশন করে এবং প্রতিটি পার্টিশনের পয়েন্টগুলোকেও ক্লাস্টার করে। এই প্রি-ক্লাস্টারিং প্রসেসের পর মধ্যবর্তী ক্লাস্টারগুলোর ক্লাস্টারিং এবং একটি ফাইনাল পাস হয় যা ডেটাসেটের প্রতিটি পয়েন্টকে ক্লাস্টারের সাথে বরাদ্দ করে।
