ক্লাস্টার অ্যানালাইসিস পরিসংখ্যানের একটি শাখা যেটি বহুবর্ষ ধরে ব্যাপকভাবে অধ্যয়ন করা হয়েছে। এই টেকনিক ব্যবহারের সুবিধা হলো কোনো ব্যাকগ্রাউন্ড নলেজ (যেন কনসেপ্ট হায়ারার্কি) ব্যবহার ছাড়া সরাসরি ডেটা থেকে আকর্ষণীয় কাঠামো বা ক্লাস্টার আবিষ্কার করা সম্ভব।
পরিসংখ্যানে ব্যবহৃত ক্লাস্টারিং অ্যালগরিদম যেন PAM বা CLARA, কম্পিউটেশনাল কমপ্লেক্সিটি দৃষ্টিকোণ থেকে অকার্যকর রিপোর্ট করা হয়েছে। দক্ষতা নিয়ে চিন্তায়, CLARANS (Clustering Large Applications based upon Randomized Search) নামে একটি নতুন অ্যালগরিদম ক্লাস্টার অ্যানালাইসিসের জন্য উন্নত করা হয়েছিল।
PAM (Partitioning around Medoids)
ধরা যাক n অবজেক্ট আছে, PAM k ক্লাস্টার খুঁজে বের করে প্রথমে প্রতিটি ক্লাস্টারের জন্য একটি প্রতিনিধিত্বমূলক অবজেক্ট খুঁজে বের করে। এমন একটি প্রতিনিধিত্ব, যা ক্লাস্টারের কেন্দ্রে অবস্থিত পয়েন্ট, তাকে মেডয়েড (medoid) বলা হয়।
k মেডয়েড সিলেক্ট করার পর, অ্যালগরিদম বারবার সব সম্ভাব্য অবজেক্ট যুগ্ম বিশ্লেষণ করে মেডয়েডের সেরা চয়ন তৈরি করার চেষ্টা করে যেন একটি অবজেক্ট মেডয়েড এবং অন্যটি নয়। ক্লাস্টারিং কোয়ালিটির মেজার প্রতিটি যুগ্মের জন্য ক্যালকুলেট করা হয়।
এক ইটারেশনে সেরা পয়েন্টের চয়নটি পরবর্তী ইটারেশনের জন্য মেডয়েড হিসেবে নির্বাচিত হয়। একক ইটারেশনের খরচ O(k(n−k)2)। তাই বড় n এবং k-র জন্য এটি কম্পিউটেশনালি অনেক অকার্যকর।
CLARA (Clustering Large Applications)
PAM এবং CLARA অ্যালগরিদমের পার্থক্য হলো পরেরটি স্যাম্পলিং-ভিত্তিক। রিয়াল ডেটার শুধু একটি ছোট অংশ রিপ্রেজেন্টেটিভ হিসেবে সিলেক্ট করা হয় এবং PAM ব্যবহার করে এই স্যাম্পল থেকে মেডয়েড সিলেক্ট করা হয়।
আইডিয়া হলো যদি স্যাম্পল যথার্থ র্যান্ডমলি সিলেক্ট করা হয়, তবে সেটি পুরো ডেটাসেটকে সঠিকভাবে প্রতিনিধিত্ব করে এবং তাই, প্রতিনিধিত্বমূলক অবজেক্ট (মেডয়েড) যেগুলো নির্বাচিত হবে সেগুলো পুরো ডেটাসেট থেকে নির্বাচিত হতো এমনকি একই হবে।
CLARA একাধিক স্যাম্পল ড্র করে এবং এই স্যাম্পলগুলোর মধ্যে সেরা ক্লাস্টারিং আউটপুট করে। CLARA PAM-র চেয়ে বড় ডেটাসেট ডিল করতে পারে। প্রতিটি ইটারেশনের কমপ্লেক্সিটি এখন O(kS2+k(n−k)), যেখানে S হলো স্যাম্পলের আকার।
CLARANS (Clustering Large Applications based upon RANdomized Search)
CLARANS অ্যালগরিদম PAM এবং CLARA দুটোই কম্বাইন করে শুধু ডেটাসেটের একটি সাবসেট সার্চ করে এবং এটি কোনো নির্দিষ্ট স্যাম্পলে নিজেকে সীমাবদ্ধ করে না যেকোনো সময়। CLARA যেন প্রতিটি সার্চ ফেজে একটি কনস্ট্যান্ট স্যাম্পল রাখে, CLARANS প্রতিটি সার্চ ফেজে কিছু র্যান্ডমনেসের সাথে একটি স্যাম্পল ড্র করে।
ক্লাস্টারিং ফেজকে একটি গ্রাফ সার্চ হিসেবে প্রেজেন্ট করা যায় যেখানে প্রতিটি নোড একটি সম্ভাব্য সমাধান, অর্থাৎ k মেডয়েডের একটি সেট। একটি সিঙ্গল মেডয়েড রিপ্লেস করার পর প্রাপ্ত ক্লাস্টারিংকে কারেন্ট ক্লাস্টারিং-এর নেইঘবর বলা হয়।
