বিসেক্টিং K-মিন্স অ্যালগরিদম
বিসেক্টিং K-মিন্স অ্যালগরিদম বেসিক K-মিন্স অ্যালগরিদমের একটি সহজ 확장이 যা একটি সহজ ধারণার ওপর ভিত্তি: K ক্লাস্টার পেতে, সমস্ত পয়েন্টের সেটকে দুটি ক্লাস্টারে ভাগ করুন, 그중 একটি ক্লাস্টার বেছে নিয়ে আবার ভাগ করুন, ইত্যাদি, যতক্ষণ না K ক্লাস্টার তৈরি হয়।
K-মিন্স অ্যালগরিদম ইনপুট প্যারামিটার k গ্রহণ করে এবং n অবজেক্টের সেটকে k ক্লাস্টারে ভাগ করে যাতে ফলাফলস্বরূপ ইন্ট্রা-ক্লাস্টার সাদৃশ্য বেশি কিন্তু ইন্টার-ক্লাস্টার সাদৃশ্য কম থাকে। ক্লাস্টার সাদৃশ্য একটি ক্লাস্টারের অবজেক্টের গড় মান (সেন্ট্রয়েড বা গ্র্যাভিটি সেন্টার) পক্ষে পরিমাপ করা হয়।
গড়ের প্রাথমিক মান들 স্বेच্ছায় বরাদ্দ করা হয়। এগুলো র্যান্ডমলি বরাদ্দ করা যেতে পারে বা প্রথম k ইনপুট আইটেমের মান থেকেও নেওয়া যেতে পারে। কনভার্জেন্স κρι্টেরিয়া বর্গ ত্রুটির ওপর ভিত্তি করে হতে পারে, কিন্তু বাধ্যতামূলক নয়। উদাহরণস্বরূপ, অ্যালগরিদমকে নির্দিষ্ট ক্লাস্টার সংখ্যায় বাধ্য করা যেতে পারে। অন্যান্য টার্মিনেশন কৌশল শুধু একটি নির্দিষ্ট ইটেরেশন সংখ্যায় লক করা থাকে। কনভার্জেন্স না হলেও শপিং নিশ্চিত করার জন্য একটি সর্বোচ্চ ইটেরেশন সংখ্যা যোগ করা যেতে পারে।
বিসেক্টিং K-মিন্স অ্যালগরিদম
ক্লাস্টারের তালিকা ইনিশিয়ালাইজ করুন যাতে সমস্ত পয়েন্ট ধারণকারী ক্লাস্টার থাকে।
রিপিট করুন
ক্লাস্টার তালিকা থেকে একটি ক্লাস্টার সরান।
{নির্বাচিত ক্লাস্টারের একাধিক "ট্রায়াল" বাইसेকশন বাস্তবায়ন করুন।}
for i : 1 to number of trials do
বেসিক K-মিন্স ব্যবহার করে নির্বাচিত ক্লাস্টারকে বাইসেক্ট করুন।
end for
সবচেয়ে ছোট মোট SSE থাকা বাইসেকশনের দুটি ক্লাস্টার বেছে নিন।
এই দুটি ক্লাস্টারকে ক্লাস্টার তালিকায় যোগ করুন।
তব্দে ক্লাস্টার তালিকায় K ক্লাস্টার থাকা পর্যন্ত।
কোন ক্লাস্টার ভাগ করা হবে সেটি বেছে নেওয়া
প্রতিটি ধাপে কোন ক্লাস্টার ভাগ করা হবে সেটি বেছে নেওয়ার বেশ কিছু উপায় রয়েছে। প্রতিটি ধাপে সবচেয়ে বড় ক্লাস্টার বেছে নেওয়া যেতে পারে, সবচেয়ে বড় SSE ওালা বেছে নেওয়া যেতে পারে, অথবা আকার এবং SSE উভয়ের ওপর ভিত্তি করে একটি মানদণ্ড ব্যবহার করা যেতে পারে। ভিন্ন নির্বাচন ভিন্ন ক্লাস্টার ফলাফল দেয়।
ফলাফলস্বরূপ ক্লাস্টারগুলোর সেন্ট্রয়েডগুলোকে বেসিক K-মিন্স অ্যালগরিদমের প্রাথমিক সেন্ট্রয়েড হিসেবে ব্যবহার করে আউটপুট ক্লাস্টারগুলোর উন্নতি করা যেতে পারে। এটি জরুরি কারণ যদিও K-মিন্স অ্যালগরিদম SSE পক্ষে একটি স্থানীয় ন্যূনতম উপস্থাপনকারী ক্লাস্টারিং খুঁজে বের করার গ্যারান্টি দেয়, কিন্তু বিসেক্টিং K-মিন্স-এ K-মিন্স অ্যালগরিদমটি "স্থানীয়ভাবে" ব্যবহার করা হয়, অর্থাৎ একক ক্লাস্টার বাইসেক্ট করার জন্য। অতএব, চূড়ান্ত ক্লাস্টার সেট মোট SSE পক্ষে একটি স্থানীয় ন্যূনতম উপস্থাপন করে না।
শেষ পর্যন্ত, K-মিন্স ক্লাস্টার বাইসেক্ট করার সাথে সাথে তৈরি ক্লাস্টারিং সিরিজ রেকর্ড করে বিসেক্টিং K-মিন্সকে হায়ারার্কিক্যাল ক্লাস্টারিং তৈরির জন্যও ব্যবহার করা যেতে পারে।
