k-মানে অ্যালগরিদম ইনপুট প্যারামিটার, k তৈরি করে এবং n অবজেক্টের একটি গ্রুপকে k ক্লাস্টারে বিভক্ত করে যাতে ফলস্বরূপ ইন্ট্রাক্লাস্টার সাদৃশ্য বড় কিন্তু ইন্টারক্লাস্টার সাদৃশ্য কম। ক্লাস্টার সাদৃশ্য একটি ক্লাস্টারে বস্তুর গড় মান সম্পর্কে গণনা করা হয়, যেটিকে ক্লাস্টারের সেন্ট্রোয়েড বা মাধ্যাকর্ষণ কেন্দ্র হিসাবে দেখা যেতে পারে।
k-মানে অ্যালগরিদম নিম্নরূপ এগিয়ে যায়। প্রথমত, এটি এলোমেলোভাবে অবজেক্টের k বেছে নিতে পারে, যার প্রত্যেকটি মূলত একটি ক্লাস্টার গড় বা কেন্দ্র সংজ্ঞায়িত করে। অবশিষ্ট অবজেক্টগুলির প্রতিটির জন্য, ক্লাস্টারে একটি বস্তু তৈরি করা হয় যার সাথে এটি একই, অবজেক্ট এবং ক্লাস্টার গড়ের মধ্যে দূরত্বের উপর নির্ভর করে।
এটি প্রতিটি ক্লাস্টারের জন্য নতুন গড় গণনা করতে পারে। নীতি ফাংশন একত্রিত না হওয়া পর্যন্ত এই পর্বটি পুনরাবৃত্তি হয়। সাধারণত, বর্গাকার-ত্রুটির মানদণ্ড −
হিসাবে উপস্থাপিত হয়$$\mathrm{E=\displaystyle\sum\limits_{i=1}^k\displaystyle\sum\limits_{p\epsilon C_{i}}|p-m_{i}|^2}$$
যেখানে E হল ডেটা সেটের কিছু বস্তুর জন্য মোট বর্গাকার ত্রুটি। p হল একটি নির্দিষ্ট বস্তু এবং mi সংজ্ঞায়িত করে স্থানের বিন্দু Ci ক্লাস্টারের গড় (p এবং mi উভয়ই বহুমাত্রিক)। বিশেষ করে, প্রতিটি ক্লাস্টারের প্রতিটি বস্তুর জন্য, বস্তু থেকে তার ক্লাস্টার কেন্দ্রের দূরত্ব বর্গ করা হয়, এবং দূরত্বগুলি অনুমান করা হয়। এই মানদণ্ডের ফলে k ক্লাস্টারগুলি কমপ্যাক্ট এবং প্রযোজ্য হিসাবে স্বাধীন হিসাবে তৈরি করার চেষ্টা করে৷
অ্যালগরিদম: k- মানে − পার্টিশনের জন্য k- মানে অ্যালগরিদম, যেখানে প্রতিটি ক্লাস্টারের কেন্দ্র ক্লাস্টারের বস্তুর গড় মান দ্বারা সংজ্ঞায়িত করা হয়।
ইনপুট -
k: the number of clusters, D: a data set including n objects.
আউটপুট -
A set of k clusters.
পদ্ধতি -
-
মূল ক্লাস্টার কেন্দ্র হিসাবে D থেকে নির্বিচারে k অবজেক্ট নির্বাচন করুন;
-
পুনরাবৃত্তি করুন
-
(পুনরায়) প্রতিটি বস্তুকে ক্লাস্টারে বরাদ্দ করুন যেখানে বস্তুটি একই, ক্লাস্টারে থাকা বস্তুর গড় মানের উপর নির্ভর করে;
-
ক্লাস্টার মানে আপডেট করুন, অর্থাৎ, প্রতিটি ক্লাস্টারের জন্য বস্তুর গড় মান গণনা করুন;
-
পরিবর্তন না হওয়া পর্যন্ত;
এটি তিনটি বস্তুকে নির্বিচারে তিনটি মূল ক্লাস্টার কেন্দ্র হিসাবে নির্বাচন করতে ব্যবহৃত হয়, যেখানে ক্লাস্টার কেন্দ্রগুলিকে "+" দ্বারা চিহ্নিত করা হয়। প্রতিটি বস্তু একটি ক্লাস্টারে বিতরণ করা হয় তা নির্ভর করে ক্লাস্টার কেন্দ্রের উপর যেখানে এটি সুবিধাজনক৷
এর পরে, ক্লাস্টার কেন্দ্রগুলি আপডেট করা হয়। প্রতিটি ক্লাস্টারের গড় মান ক্লাস্টারে বিদ্যমান বস্তুর উপর ভিত্তি করে পুনরায় গণনা করা হয়। নতুন ক্লাস্টার কেন্দ্রগুলি ব্যবহার করে, বস্তুগুলি ক্লাস্টারগুলিতে পুনরায় বিতরণ করা হয় তা নির্ভর করে কোন ক্লাস্টার কেন্দ্র সংলগ্ন তার উপর। এই ধরনের একটি পুনর্বন্টন কাঠামো ড্যাশ কার্ভ দ্বারা বেষ্টিত নতুন সিলুয়েট।
বিভাজন বাড়ানোর জন্য ক্লাস্টারগুলিতে পুনরাবৃত্তভাবে অবজেক্টগুলিকে পুনরায় বরাদ্দ করার পর্যায়টিকে পুনরাবৃত্তিমূলক স্থানান্তর হিসাবে সংজ্ঞায়িত করা হয়। কোন ক্লাস্টারে বস্তুর কোন পুনঃবন্টন নেই, এবং তাই প্রক্রিয়াটি সরানো হয়। ফলস্বরূপ ক্লাস্টারগুলি ক্লাস্টারিং ফেজ দ্বারা পুনরুদ্ধার করা হয়।
