এই পৃষ্ঠাটি Cloud Translation API অনুবাদ করেছে।

ক্লাস্টারিং অ্যালগরিদম চালান

মেশিন লার্নিং-এ, আপনি কখনও কখনও এমন ডেটাসেটের মুখোমুখি হন যার লক্ষ লক্ষ উদাহরণ থাকতে পারে। ML অ্যালগরিদমগুলিকে অবশ্যই এই বৃহৎ ডেটাসেটে দক্ষতার সাথে স্কেল করতে হবে। যাইহোক, অনেক ক্লাস্টারিং অ্যালগরিদম স্কেল করে না কারণ তাদের সমস্ত জোড়া পয়েন্টের মধ্যে সাদৃশ্য গণনা করতে হবে। এর অর্থ হল তাদের রানটাইমগুলি পয়েন্টের সংখ্যার বর্গ হিসাবে বৃদ্ধি পায়, যাকে $O(n^2)$হিসাবে চিহ্নিত করা হয়। উদাহরণস্বরূপ, সমষ্টিগত বা বিভাজনীয় শ্রেণিবদ্ধ ক্লাস্টারিং অ্যালগরিদমগুলি সমস্ত জোড়া বিন্দুর দিকে নজর দেয় এবং যথাক্রমে l10n $O(n^2 log(n))$ এবং $O(n^2)$placeholder3 এর জটিলতা রয়েছে।

এই কোর্সটি কে-মানে ফোকাস করে কারণ এটি $O(nk)$হিসাবে স্কেল করে, যেখানে $k$হল ক্লাস্টারের সংখ্যা। k-এর অর্থ বিন্দু এবং তাদের ক্লাস্টারের সেন্ট্রয়েডের মধ্যে দূরত্ব কমিয়ে $k$ ক্লাস্টারে বিন্দুগুলিকে গোষ্ঠীভুক্ত করে (নিচের চিত্র 1-এ দেখা গেছে)। একটি ক্লাস্টারের সেন্ট্রোয়েড হল ক্লাস্টারের সমস্ত বিন্দুর গড়।

যেমন দেখানো হয়েছে, k- মানে মোটামুটি বৃত্তাকার ক্লাস্টার খুঁজে পায়। ধারণাগতভাবে, এর অর্থ হল k-অর্থ কার্যকরভাবে ডেটাকে মোটামুটিভাবে বৃত্তাকার বিতরণের একটি সংখ্যা হিসাবে গণ্য করে এবং এই বিতরণগুলির সাথে সম্পর্কিত ক্লাস্টারগুলি খুঁজে বের করার চেষ্টা করে। বাস্তবে, ডেটাতে আউটলিয়ার রয়েছে এবং এই ধরনের মডেলের সাথে মানানসই নাও হতে পারে।

k-means চালানোর আগে, আপনাকে অবশ্যই ক্লাস্টারের সংখ্যা নির্বাচন করতে হবে, $k$। প্রাথমিকভাবে, $k$এর জন্য একটি অনুমান দিয়ে শুরু করুন। পরে, আমরা আলোচনা করব কিভাবে এই সংখ্যাটি পরিমার্জন করা যায়।

k- মানে ক্লাস্টারিং অ্যালগরিদম

$k$ ক্লাস্টারে ডেটা ক্লাস্টার করতে, k-মানে নীচের ধাপগুলি অনুসরণ করে:

শুরুতে k-এর গ্রাফ মানে — **চিত্র 1: কে-এর অর্থ আরম্ভ করা।**

প্রথম ধাপ

অ্যালগরিদম এলোমেলোভাবে প্রতিটি ক্লাস্টারের জন্য একটি সেন্ট্রোয়েড বেছে নেয়। আমাদের উদাহরণে, আমরা 3টির মধ্যে একটি $k$ বেছে নিই, এবং সেইজন্য অ্যালগরিদম এলোমেলোভাবে 3টি সেন্ট্রোয়েড বেছে নেয়।

ধাপ দুই

$k$ প্রারম্ভিক ক্লাস্টার পেতে অ্যালগরিদম প্রতিটি বিন্দুকে নিকটতম সেন্ট্রোয়েডের জন্য বরাদ্দ করে।

ধাপ তিন

প্রতিটি ক্লাস্টারের জন্য, অ্যালগরিদম ক্লাস্টারের সমস্ত পয়েন্টের গড় নিয়ে সেন্ট্রোয়েডের পুনরায় গণনা করে। সেন্ট্রোয়েডের পরিবর্তনগুলি তীর দ্বারা চিত্র 3-এ দেখানো হয়েছে। যেহেতু সেন্ট্রোয়েডগুলি পরিবর্তিত হয়, তখন অ্যালগরিদম পয়েন্টগুলিকে নিকটতম সেন্ট্রোয়েডগুলিতে পুনরায় বরাদ্দ করে৷ চিত্র 4 পুনরায় নিয়োগের পরে নতুন ক্লাস্টারগুলি দেখায়।

**চিত্র 4: পুনরায় নিয়োগের পরে ক্লাস্টার।**

ধাপ চার

পয়েন্ট ক্লাস্টার পরিবর্তন করা বন্ধ না হওয়া পর্যন্ত অ্যালগরিদম সেন্ট্রোয়েডের গণনা এবং পয়েন্টের অ্যাসাইনমেন্টের পুনরাবৃত্তি করে। বড় ডেটাসেটগুলি ক্লাস্টার করার সময়, আপনি কনভারজেন্সে পৌঁছানোর আগে অ্যালগরিদম বন্ধ করে দেন, পরিবর্তে অন্যান্য মানদণ্ড ব্যবহার করে৷

এই কোর্সের জন্য আপনাকে k-এর পিছনের গণিত বোঝার দরকার নেই। যাইহোক, আপনি যদি কৌতূহলী হন তবে গাণিতিক প্রমাণের জন্য নীচে দেখুন।

গাণিতিক প্রমাণের জন্য প্লাস আইকনে ক্লিক করুন

প্রদত্ত $n$ উদাহরণগুলি $k$ ক্লাস্টারগুলিতে বরাদ্দ করা হয়েছে, তাদের সেন্ট্রোয়েডগুলির উদাহরণগুলির দূরত্বের যোগফল কমিয়ে দিন৷ কোথায়:

$A_{nk} = 1$ যখন $n$তম উদাহরণটি $k$তম ক্লাস্টারে বরাদ্দ করা হয়, এবং অন্যথায় 0
$\theta_k$ হল ক্লাস্টার $k$এর সেন্ট্রয়েড

আমরা নিম্নোক্ত অভিব্যক্তিটি ছোট করতে চাই:$$\min_{A,\theta} \sum_{n=1}^N \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n ||^2$$বিষয়:$$A_{nk} \in \{0,1\} \forall n,k$$এবং$$\sum^{K}_{k=1}A_{nk}=1 \forall n$$ক্লাস্টার সেন্ট্রোয়েড l10n-placeholder22-এর সাপেক্ষে অভিব্যক্তিটি ছোট করতে, $\theta_k$এর ক্ষেত্রে $\theta_k$ এর ক্ষেত্রে ডেরিভেটিভ নিন।$$f(\theta) = \sum^{N}_{n=1} \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n||^2$$$$\frac{\partial f}{\partial \theta_k} = 2 \sum_{n=1}^{N} A_{nk}(\theta_k - x_n) = 0$$$$\implies \sum_{n=1}^{N} A_{nk}\theta_{k} = \sum^N_{n=1} A_{nk}x_{n}$$$$\theta_k \sum_{n=1}^{N} A_{nk} = \sum_{n=1}^{N} A_{nk} x_n$$$$\theta_k = \frac{\sum^N_{n=1} A_{nk} x_n}{\sum^N_{n=1} A_{nk}}$$লব হল ক্লাস্টারের সমস্ত উদাহরণ-কেন্দ্রীয় দূরত্বের সমষ্টি। হর হল ক্লাস্টারে উদাহরণের সংখ্যা। সুতরাং, ক্লাস্টার সেন্ট্রোয়েড$\theta_k$ হল ক্লাস্টারের উদাহরণ-কেন্দ্রীয় দূরত্বের গড়। তাই প্রমাণিত।

যেহেতু সেন্ট্রোয়েড পজিশনগুলি প্রাথমিকভাবে এলোমেলোভাবে বেছে নেওয়া হয়, k-মানগুলি ধারাবাহিক রানে উল্লেখযোগ্যভাবে ভিন্ন ফলাফল দিতে পারে। এই সমস্যাটি সমাধান করতে, k-মানে একাধিকবার চালান এবং সেরা মানের মেট্রিক্সের সাথে ফলাফল চয়ন করুন। (আমরা এই কোর্সে পরে গুণমানের মেট্রিক্স বর্ণনা করব।) আরও ভাল প্রাথমিক সেন্ট্রয়েড পজিশন বেছে নেওয়ার জন্য আপনার k-means-এর একটি উন্নত সংস্করণের প্রয়োজন হবে।