পূর্বে উল্লিখিত হিসাবে, অনেক ক্লাস্টারিং অ্যালগরিদম মেশিন লার্নিং-এ ব্যবহৃত ডেটাসেটের সাথে পরিমাপ করে না, যার প্রায়ই লক্ষ লক্ষ উদাহরণ থাকে। উদাহরণস্বরূপ, সমষ্টিগত বা বিভাজনীয় শ্রেণিবদ্ধ ক্লাস্টারিং অ্যালগরিদমগুলি সমস্ত জোড়া বিন্দুর দিকে নজর দেয় এবং যথাক্রমে \(O(n^2 log(n))\) এবং \(O(n^2)\)এর জটিলতা রয়েছে।
এই কোর্সটি কে-মানে ফোকাস করে কারণ এটি \(O(nk)\)হিসাবে স্কেল করে, যেখানে \(k\)হল ব্যবহারকারীর দ্বারা নির্বাচিত ক্লাস্টারের সংখ্যা। এই অ্যালগরিদমটি প্রতিটি বিন্দু এবং এর ক্লাস্টারের সেন্ট্রোয়েডের মধ্যে দূরত্ব কমিয়ে\(k\) ক্লাস্টারে পয়েন্ট করে (চিত্র 1 দেখুন)।
ফলস্বরূপ, কে-অর্থ কার্যকরভাবে ডেটাকে মোটামুটিভাবে বৃত্তাকার বিতরণের একটি সংখ্যার সমন্বয়ে গণ্য করে এবং এই বিতরণগুলির সাথে সম্পর্কিত ক্লাস্টারগুলি খুঁজে বের করার চেষ্টা করে। কিন্তু বাস্তব-বিশ্বের তথ্যে আউটলিয়ার এবং ঘনত্ব-ভিত্তিক ক্লাস্টার রয়েছে এবং k-মানে অন্তর্নিহিত অনুমানের সাথে নাও মিলতে পারে।
k- মানে ক্লাস্টারিং অ্যালগরিদম
অ্যালগরিদম এই পদক্ষেপগুলি অনুসরণ করে:
\(k\)এর জন্য একটি প্রাথমিক অনুমান প্রদান করুন, যা পরে সংশোধন করা যেতে পারে। এই উদাহরণের জন্য, আমরা \(k = 3\)নির্বাচন করি।
এলোমেলোভাবে \(k\) centroids নির্বাচন করুন।
চিত্র 1: কে-এর অর্থ আরম্ভ করা। \(k\) প্রারম্ভিক ক্লাস্টার পেতে নিকটতম সেন্ট্রয়েডের কাছে প্রতিটি পয়েন্ট বরাদ্দ করুন।
চিত্র 2: প্রাথমিক ক্লাস্টার। প্রতিটি ক্লাস্টারের জন্য, ক্লাস্টারের সমস্ত পয়েন্টের গড় অবস্থান গ্রহণ করে একটি নতুন সেন্ট্রোয়েড গণনা করুন। চিত্র 4-এর তীরগুলি সেন্ট্রোয়েড অবস্থানের পরিবর্তন দেখায়।
চিত্র 3: পুনরায় গণনা করা সেন্ট্রোয়েড। প্রতিটি পয়েন্টকে নিকটতম নতুন সেন্ট্রোয়েডে পুনরায় বরাদ্দ করুন।
চিত্র 4: পুনরায় নিয়োগের পরে ক্লাস্টার। 4 এবং 5 ধাপগুলি পুনরাবৃত্তি করুন, সেন্ট্রোয়েড এবং ক্লাস্টার সদস্যতা পুনঃগণনা করে, যতক্ষণ না পয়েন্টগুলি আর ক্লাস্টার পরিবর্তন না করে। বড় ডেটাসেটের ক্ষেত্রে, আপনি অন্যান্য মানদণ্ডের উপর ভিত্তি করে কনভারজেন্সের আগে অ্যালগরিদম বন্ধ করতে পারেন।
যেহেতু সেন্ট্রোয়েড পজিশনগুলি প্রাথমিকভাবে এলোমেলোভাবে বেছে নেওয়া হয়, k-মানগুলি ধারাবাহিক রানে উল্লেখযোগ্যভাবে ভিন্ন ফলাফল দিতে পারে। এই সমস্যাটি সমাধান করতে, k-মানে একাধিকবার চালান এবং সেরা মানের মেট্রিক্সের সাথে ফলাফল চয়ন করুন। (আমরা এই কোর্সে পরে গুণমানের মেট্রিক্স বর্ণনা করব।) আরও ভাল প্রাথমিক সেন্ট্রয়েড পজিশন বেছে নেওয়ার জন্য আপনার k-means-এর একটি উন্নত সংস্করণের প্রয়োজন হবে।
যদিও গণিতের গভীর বোঝার প্রয়োজন নেই, যারা কৌতূহলী তাদের জন্য k-মান হল প্রত্যাশা-সর্বোচ্চকরণ অ্যালগরিদমের একটি বিশেষ ক্ষেত্রে। UPenn থেকে এই বিষয়ে লেকচার নোট দেখুন।