K- মানে ক্লাস্টারিং হল সবচেয়ে সাধারণ পার্টিশনিং অ্যালগরিদম৷ কে-মানে গঠিত নতুন ক্লাস্টারগুলির একটিতে ডেটাসেটের প্রতিটি ডেটা পুনরায় বরাদ্দ করে৷ দূরত্ব বা সাদৃশ্যের পরিমাপ ব্যবহার করে একটি রেকর্ড বা ডেটা পয়েন্ট নিকটতম ক্লাস্টারে বরাদ্দ করা হয়৷
k-মানে অ্যালগরিদম ইনপুট প্যারামিটার, k তৈরি করে এবং n অবজেক্টের একটি গ্রুপকে k ক্লাস্টারে বিভক্ত করে যাতে ফলস্বরূপ ইন্ট্রাক্লাস্টার সাদৃশ্য বড় কিন্তু ইন্টারক্লাস্টার সাদৃশ্য কম। ক্লাস্টার সাদৃশ্য একটি ক্লাস্টারে বস্তুর গড় মান সম্পর্কে গণনা করা হয়, যেটিকে ক্লাস্টারের সেন্ট্রয়েড বা মাধ্যাকর্ষণ কেন্দ্র হিসাবে দেখা যেতে পারে।
কে-মানে ক্লাস্টারিং-এ নিম্নলিখিত ধাপগুলি ব্যবহার করা হয়েছে -
-
এটি K প্রাথমিক ক্লাস্টার সেন্ট্রোয়েড c1 নির্বাচন করতে পারে , c2 , c3 …. . ck .
-
এটি এস ক্লাস্টারে প্রতিটি ইনস্ট্যান্স x বরাদ্দ করতে পারে যার সেন্ট্রোয়েড x এর সবচেয়ে কাছাকাছি।
-
প্রতিটি ক্লাস্টারের জন্য, সেই ক্লাস্টারে কোন উপাদানগুলি রয়েছে তার উপর ভিত্তি করে তার সেন্ট্রোয়েড পুনরায় গণনা করুন৷
-
কনভারজেন্স সম্পূর্ণ না হওয়া পর্যন্ত (b) এ যান।
-
এটি অবজেক্টকে (ডেটা পয়েন্ট) কে ক্লাস্টারে আলাদা করতে পারে।
-
এটি ক্লাস্টার সেন্টার (সেন্ট্রয়েড) =ক্লাস্টারের সমস্ত ডেটা পয়েন্টের গড় হিসাবে ব্যবহৃত হয়।
-
এটি প্রতিটি পয়েন্টকে ক্লাস্টারে বরাদ্দ করতে পারে যার সেন্ট্রোয়েড সবচেয়ে কাছের (দূরত্ব ফাংশন ব্যবহার করে)।
উপায়ের জন্য মূল মান নির্বিচারে অনুমোদিত হয়. এগুলি এলোমেলোভাবে বরাদ্দ করা যেতে পারে বা সম্ভবত প্রথম k ইনপুট আইটেমগুলি থেকে মানগুলি ব্যবহার করতে পারে৷ কনভারজেন্স উপাদানটি বর্গক্ষেত্র ত্রুটির উপর ভিত্তি করে হতে পারে, কিন্তু সেগুলি না হওয়া প্রয়োজন৷ উদাহরণস্বরূপ, অ্যালগরিদম বিভিন্ন ক্লাস্টারে বরাদ্দ করা হয়। অন্যান্য সমাপ্তি কৌশলগুলি কেবল একটি নির্দিষ্ট সংখ্যক পুনরাবৃত্তিতে লক করা হয়েছে। কনভারজেন্স ছাড়াই কেনাকাটা নিশ্চিত করতে সর্বাধিক সংখ্যক পুনরাবৃত্তি অন্তর্ভুক্ত করা যেতে পারে।
অ্যালগরিদম
ইনপুট −
D = {t1 t2 … tn} // Set of elements k // Number of desired clusters
আউটপুট −
K // Set of clusters
K- মানে অ্যালগরিদম −
assign initial values for means m1 m2 … . . mk repeat assign each item ti to the cluster which has the closest mean calculate the new mean for each cluster until convergence criteria are met
এটি তিনটি বস্তুকে নির্বিচারে তিনটি মূল ক্লাস্টার কেন্দ্র হিসাবে নির্বাচন করতে ব্যবহৃত হয়, যেখানে ক্লাস্টার কেন্দ্রগুলিকে "+" দ্বারা চিহ্নিত করা হয়। প্রতিটি বস্তুকে ক্লাস্টার কেন্দ্রের উপর নির্ভর করে একটি ক্লাস্টারে বিতরণ করা হয় যেখানে এটি সুবিধাজনক।
এর পরে, ক্লাস্টার কেন্দ্রগুলি আপডেট করা হয়। প্রতিটি ক্লাস্টারের গড় মান ক্লাস্টারে বিদ্যমান বস্তুর উপর ভিত্তি করে পুনরায় গণনা করা হয়। নতুন ক্লাস্টার কেন্দ্রগুলি ব্যবহার করে, কোন ক্লাস্টার কেন্দ্র সংলগ্ন তার উপর নির্ভর করে বস্তুগুলি ক্লাস্টারগুলিতে পুনরায় বিতরণ করা হয়। এই ধরনের একটি পুনর্বন্টন কাঠামো ড্যাশ কার্ভ দ্বারা বেষ্টিত নতুন সিলুয়েট।
বিভাজন উন্নত করার জন্য পুনরাবৃত্তভাবে বস্তুগুলিকে ক্লাস্টারে পুনরায় তৈরি করার পদ্ধতিটিকে পুনরাবৃত্তিমূলক স্থানান্তর হিসাবে সংজ্ঞায়িত করা হয়। প্রদর্শিত কোনো ক্লাস্টারে বস্তুর কোনো পুনঃবন্টন নেই, এবং তাই প্রক্রিয়াটি সরিয়ে ফেলা হয়। ফলস্বরূপ ক্লাস্টারগুলি ক্লাস্টারিং ফেজ দ্বারা পুনরুদ্ধার করা হয়।