k-মিনস অ্যালগরিদম ইনপুট প্যারামিটার k নেয় এবং n অবজেক্টের একটি সেটকে k ক্লাস্টারে বিভক্ত করে যাতে ফলে ইন্ট্রা-ক্লাস্টার সাদৃশ্য বেশি হয় কিন্তু ইন্টার-ক্লাস্টার সাদৃশ্য কম। ক্লাস্টার সাদৃশ্য একটি ক্লাস্টারের অবজেক্টগুলির গড় মান (mean value) সংক্রান্তে গণনা করা হয়, যা ক্লাস্টারের সেন্ট্রয়েড বা কেন্দ্র হিসেবে বিবেচিত হতে পারে।
k-মিনস অ্যালগরিদমের ধাপসমূহ
- আরম্ভিকরণ: D থেকে যাদুকরীভাবে k অবজেক্ট বেছে নেওয়া হয়, যারা প্রাথমিকভাবে প্রতিটি ক্লাস্টারের গড় বা কেন্দ্র নির্ধারণ করে।
- অসাইনমেন্ট: বাকি অবজেক্টগুলোকে তাদের সবচেয়ে কাছের ক্লাস্টারের মানে (cluster mean) অনুযায়ী ক্লাস্টারে বরাদ্দ করা হয়।
- আপডেট: প্রতিটি ক্লাস্টারের জন্য নতুন গড় (mean) গণনা করা হয়।
- পুনরাবৃত্তি: ধাপ ২ এবং ৩ পুনরাবৃত্তি করা হয় যতক্ষণ না সমাধান ফাংশন কনভার্জ করে (অর্থাৎ আর কোনো পরিবর্তন হয় না)।
সর্বনিম্ন বর্গ ত্রুটি κριটেরিয়ন
সাধারণত স্কোয়ার-এরর κριটেরিয়ন (square-error criterion) ব্যবহার করা হয়:
$$\mathrm{E=\displaystyle\sum\limits_{i=1}^k\displaystyle\sum\limits_{p\epsilon C_{i}}|p-m_{i}|^2}$$
যেখানে E হল ডেটাসেটের সব অবজেক্টের জন্য বর্গ ত্রুটির যোগফল। p হল একটি অবজেক্টকে প্রতীকীकरणকারী স্পেসে পয়েন্ট এবং mᵢ হল ক্লাস্টার Cᵢ-এর গড় (p এবং mᵢ উভয়ই মাল্টিডাইমেনশনাল)। নির্দিষ্টভাবে, প্রতিটি ক্লাস্টারের প্রতিটি অবজেক্টের জন্য, অবজেক্ট থেকে এর ক্লাস্টার কেন্দ্র পর্যন্ত দূরত্ব বর্গ করা হয় এবং দূরত্বগুলো যোগ করা হয়। এই κριটেরিয়ন ফলস্বরূপ k ক্লাস্টারগুলিকে যত möjব 콤্প্যাক্ট এবং স্বাধীন করার চেষ্টা করে।
অ্যালগরিদম: k-মিনস
ইনপুট: k: ক্লাস্টারের সংখ্যা, D: n অবজেক্ট ধারণকারী একটি ডেটাসেট।
আউটপুট: k ক্লাস্টারের একটি সেট।
পদ্ধতি:
- D থেকে যাদুকরীভাবে k অবজেক্ট বেছে নিন প্রাথমিক ক্লাস্টার কেন্দ্র হিসেবে;
- পুনরাবৃত্তি করুন:
- প্রতিটি অবজেক্টকে সেটি যেটি সবচেয়ে সাদৃশ্যমান (ক্লাস্টারের অবজেক্টগুলির গড় মান অনুযায়ী) সে ক্লাস্টারে (পুনরায়) বরাদ্দ করুন;
- ক্লাস্টার গড়গুলো আপডেট করুন, অর্থাৎ প্রতিটি ক্লাস্টারের অবজেক্টগুলির গড় মান গণনা করুন;
- যতক্ষণ না কোনো পরিবর্তন হয় না;
দৃষ্টান্ত
তিনটি অবজেক্ট যাদুকরীভাবে তিনটি প্রাথমিক ক্লাস্টার কেন্দ্র হিসেবে বেছে নেওয়া হয়, যেখানে ক্লাস্টার কেন্দ্রগুলো "+" চিহ্নিত। প্রতিটি অবজেক্ট সেটি যেটি সবচেয়ে নিকটবর্তী সেটা অনুযায়ী একটি ক্লাস্টারে বরাদ্দ করা হয়।
এরপর, ক্লাস্টার কেন্দ্রগুলো আপডেট করা হয়। বর্তমান ক্লাস্টারের অবজেক্টগুলোর ওপর ভিত্তি করে প্রতিটি ক্লাস্টারের গড় মান পুনরায় গণনা করা হয়। নতুন ক্লাস্টার কেন্দ্র ব্যবহার করে, অবজেক্টগুলো পুনরায় বরাদ্দ করা হয় কোন ক্লাস্টার কেন্দ্র সবচেয়ে নিকট আশেপাশে। এতে ড্যাশড কভারের ভেতরে নতুন সিলুয়েট গঠন হয়।
বস্তুগুলিকে ক্লাস্টারগুলিতে পুনরায় বরাদ্দ করে পার্টিশনিং উন্নত করার এই পুনরাবৃত্তিমূলক ধাপকে ইটেরেটিভ রিলোকেশন (iterative relocation) বলা হয়। কোনো ক্লাস্টারে অবজেক্টের কোনো পুনর্বিন্যাস ঘটে না, এবং তাই প্রক্রিয়াটি থামে। ফলস্বরূপ ক্লাস্টারগুলো ক্লাস্টারিং ফেজ দ্বারা ফেরত দেওয়া হয়।
