বড় ডেটা সেটে k-medoids অ্যালগরিদমের দক্ষতা
PAM-এর মতো ক্লাসিক k-medoids পার্টিশনিং অ্যালগরিদম ছোট ডেটা সেটের জন্য দক্ষতার সাথে কাজ করে কিন্তু বিশাল ডেটা সেটের জন্য ভালো স্কেল করে না। আরও বড় ডেটা সেট হ্যান্ডেল করতে, একটি স্যাম্পলিং-ভিত্তিক পদ্ধতি, যাকে CLARA (Clustering Large Applications) বলা হয়, ব্যবহার করা যেতে পারে।
CLARA-এর পদ্ধতি:
CLARA-এর পেছনের ধারণা হলো: যদি স্যাম্পলটি যথাযথ র্যান্ডমভাবে বেছে নেওয়া হয়, তবে এটি মূল ডেটা সেটকে নিকটতা থেকে রিপ্রেজেন্ট করবে। নির্বাচিত প্রতিনিধি অবজেক্ট (medoids) সেসব অবজেক্টের মতো হবে যেগুলো পুরো ডেটা সেট থেকে নির্বাচিত হত। CLARA ডেটা সেটের একাধিক স্যাম্পল টেনে, প্রতিটি স্যাম্পলে PAM প্রয়োগ করে, এবং এর সেরা ক্লাস্টারিং আউটপুট হিসেবে ফেরত দেয়।
CLARA-এর পারফরম্যান্স স্যাম্পল সাইজের ওপর নির্ভরশীল। দেখা গিয়েছে যে PAM একটি দিয়ে দিয়ে ডেটা সেট থেকে সেরা k medoids খোঁজে, আর CLARA নির্বাচিত স্যাম্পলগুলোর মধ্য থেকে সেরা k medoids খোঁজে। CLARANS (Clustering Large Applications based upon RANdomized Search) নামে একটি k-medoids টাইপ অ্যালগরিদম প্রস্তাবিত হয়েছিল। এটি স্যাম্পলিং মেথডকে PAM-এর সাথে সংযুক্ত করতে পারে। CLARA যেহেতু প্রতিটি সার্চ স্টেজে একটি ফিক্সড স্যাম্পল রাখে, CLARANS প্রতিটি সার্চ ফেজে কিছু র্যান্ডমনেসের সাথে স্যাম্পল টেনে।
ক্লাস্টারিং প্রসেসকে একটি গ্রাফ সার্চ হিসেবে দেখা যেতে পারে, যেখানে প্রতিটি নোড একটি সম্ভাব্য সমাধান (k medoids সেট)। দুটি নোড হলো neighbour (বিশেষভাবে, গ্রাফে একটি আর্ক দ্বারা লিঙ্কড) যদি তাদের সেট শুধু একটি অবজেক্টের দ্বারা ভিন্ন হয়। প্রতিটি নোডকে একটি কস্ট অ্যাসাইন করা যেতে পারে যা প্রতিটি অবজেক্ট এবং এর ক্লাস্টারর medoids-এর মধ্যে মোট dissimilarity দ্বারা রিপ্রেজেন্ট করা হয়।
প্রতিটি ধাপে, PAM বর্তমান নোডের সব নেইবর নির্ধারণ করে এর মিনিমাম কস্ট সমাধানের জন্য সার্চে। বর্তমান নোডটি তারপর সবচেয়ে বড় descent in costs-वाले নেইবর দ্বারা রিপ্লেস করা হয়। কারণ CLARA পুরো ডেটা সেটের একটি স্যাম্পলে অপারেট করে, এটি কম নেইবর নির্ধারণ করে এবং সার্চকে ছোট সাবগ্রাফে সীমাবদ্ধ করে যা প্রাথমিক গ্রাফের চেয়ে ছোট।
CLARANS eksperimentalভাবে PAM এবং CLARA উভয়ের চেয়ে বেশি দক্ষ সাবিত হয়েছে। এটি সিলুয়েট কোইফিসিয়েন্ট (একটি অবজেক্টের প্রোপার্টি যা বলে অবজেক্টটি কতটুকু ক্লাস্টারের সাথে সত্যিকারের মত ফিট করে) ব্যবহার করে সবচেয়ে "প্রাকৃতিক" ক্লাস্টার সংখ্যা আবিষ্কার করতে পারে। CLARANS আউটলায়ার আবিষ্কার করতে সক্ষম।
CLARANS-এর কম্পিউটেশনাল কমপ্লেক্সিটি O(n²) যেখানে n হলো অবজেক্টের সংখ্যা। കൂടാതে, এর ক্লাস্টারিং কোয়ালিটি স্যাম্পলিং মেথডের ওপর নির্ভরশীল। CLARANS-এর ডিস্কে অবস্থিত ডেটা অবজেক্ট হ্যান্ডেল করার ক্ষমতা আরও উন্নত করা যেতে পারে স্পেশিয়াল ডেটা স্ট্রাকচার এক্সপ্লোর করার মেথডে ফোকাস করে, যার মধ্যে R*-trees রয়েছে।
