K-means ক্লাস্টারিং হলো সবচেয়ে সাধারণ পার্টিশনিং অ্যালগরিদম। K-means ডেটাসেটের প্রতিটি ডেটাকে নতুন গঠিত ক্লাস্টারগুলোয় শুধু একটিয় রি-অ্যাসাইন করে। একটি রেকর্ড বা ডেটা পয়েন্ট ডিস্ট্যান্স বা সিমিলারিটি মেজার ব্যবহার করে নিকটতম ক্লাস্টারের কাছে অ্যাসাইন করা হয়।
K-means অ্যালগরিদম ইনপুট প্যারামিটার k নেয় এবং n অবজেক্টের একটি গোষ্ঠীকে k ক্লাস্টারে পার্টিশন করে যাতে ফলস্বরূপ ইন্ট্রাক্লাস্টার সিমিলারিটি বেশি হয় কিন্তু ইন্টারক্লাস্টার সিমিলারিটি কম। ক্লাস্টার সিমিলারিটি ক্লাস্টারের অবজেক্টগুলোর মিন ভ্যালু রিগার্ডিং হিসাব করা হয়, যা ক্লাস্টারের সেন্ট্রয়েড বা গ্রেভিটির সেন্টার হিসেবে দেখা যায়।
K-means ক্লাস্টারিং-এ নিচের ধাপগুলো অনুসরণ করা হয়:
Kটি প্রাথমিক ক্লাস্টার সেন্ট্রয়েড c1, c2, c3… ck নির্বাচন করা।
প্রতিটি ইন্সট্যান্স x কে S ক্লাস্টারে অ্যাসাইন করা যেন এর সেন্ট্রয়েড x-র নিকটতম।
প্রতিটি ক্লাস্টারের জন্য, সেটে কী এলিমেন্ট আছে সেটি ভিত্তিক করে এর সেন্ট্রয়েড রি-কম্পিউট করা।
কনভার্জেন্স পূর্ণ হওয়া পর্যন্ত ধাপ (b) এ ফিরে যাওয়া।
অবজেক্ট (ডেটা পয়েন্ট) কে K ক্লাস্টারে বিভক্ত করা।
ক্লাস্টার সেন্টার (সেন্ট্রয়েড) = ক্লাস্টারের সকল ডেটা পয়েন্টের গড়।
প্রতিটি পয়েন্টকে সেটি ক্লাস্টারে অ্যাসাইন করা যেন এর সেন্ট্রয়েড নিকটতম (ডিস্ট্যান্স ফাংশন ব্যবহার করে)।
মিনের প্রারম্ভিক মানগুলো ارবিট্রেরিলি অনুমোদিত। এগুলো র্যান্ডমলি অ্যাসাইন করা যায় বা হয় প্রথম k ইনপুট আইটেমের ভ্যালু থেকে নেওয়া যায়। কনভার্জেন্স এলিমেন্ট স্কোয়ার্ড এরর ভিত্তিক হতে পারে, কিন্তু সেটি বাধ্যতামূলক নয়। উদাহরণস্বরূপ, অ্যালগরিদম বিভিন্ন ক্লাস্টারে অ্যাসাইন করা হয়ে থামতে পারে। অন্যান্য টার্মিনেশন টেকনিক শুধু একটি ফিক্সড নম্বর ইটারেশনে লক করে দেয়। কনভার্জেন্স ছাড়াও টার্মিনেশন নিশ্চিত করতে সর্বোচ্চ ইটারেশনের সংখ্যা যোগ করা যায়।
অ্যালগরিদম
ইনপুট —
D = {t1 t2 … tn} // এলিমেন্টের সেট k // কাঙ্ক্ষিত ক্লাস্টার সংখ্যা
আউটপুট —
K // ক্লাস্টার সেট
K-means অ্যালগরিদম —
mean m1 m2 … mk এর জন্য প্রাথমিক মান অ্যাসাইন repeat প্রতিটি আইটেম ti কে সেটি ক্লাস্টারে অ্যাসাইন যেন এর মিন নিকটতম প্রতিটি ক্লাস্টারের জন্য নতুন মিন ক্যালকুলেট until কনভার্জেন্স κριটেরিয়া পূরণ হয়
তিনটি অবজেক্ট ارবিট্রেরিলি তিনটি প্রাথমিক ক্লাস্টার সেন্টার হিসেবে সিলেক্ট করা হয়, যেখানে ক্লাস্টার সেন্টার + চিহ্ন দিয়ে ডিনোট করা হয়। প্রতিটি অবজেক্ট ক্লাস্টার সেন্টারের নিকটতমের ওপর ভিত্তি করে একটি ক্লাস্টারে ডিস্ট্রিবিউট করা হয়।
পরবর্তীতে, ক্লাস্টার সেন্টারগুলো আপডেট হয়। প্রতিটি ক্লাস্টারের মিন ভ্যালু বর্তমান ক্লাস্টারের অবজেক্টের ওপর ভিত্তি করে রি-কম্পিউট করা হয়। নতুন ক্লাস্টার সেন্টার ব্যবহার করে, অবজেক্টগুলো পুনরায় ক্লাস্টারে রিডিস্ট্রিবিউট করা হয় কোন ক্লাস্টার সেন্টার নিকটতম তার ওপর ভিত্তি করে। এতে ড্যাশড কার্ভ দ্বারা ঘিরে নতুন সিলহুয়েট গঠিত হয়।
পার্টিশনিং উন্নত করার জন্য অবজেক্টগুলোকে ক্লাস্টারে পুনরাবৃত্তিমূলক রি-অ্যাসাইন করার প্রক্রিয়াকে রিপিটিটিভ রিলোকেশন বলা হয়। যেকোনো ক্লাস্টারে অবজেক্টের রিডিস্ট্রিবিউশন না হলে প্রসেস থামে। ফলস্বরূপ ক্লাস্টারগুলো ক্লাস্টারিং ফেজ দ্বারা ফাইনাল হয়।
