পার্টিশনাল অ্যালগরিদমের ধরন
পার্টিশনাল অ্যালগরিদমের দুটি ধরন রয়েছে:
K-মিন্স ক্লাস্টারিং (K-means clustering)
K-মিন্স ক্লাস্টারিং সবচেয়ে সাধারণ পার্টিশনিং অ্যালগরিদম। K-মিন্স ডেটাসেটের প্রতিটি ডেটাকে নতুন তৈরি ক্লাস্টারগুলির শুধুমাত্র একটির কাছে পুনর্বরাদ্দ করে। একটি রেকর্ড বা ডেটা পয়েন্টকে দূরত্ব বা সাদৃশ্যের মাপ ব্যবহার করে নিকটতম ক্লাস্টারের কাছে বরাদ্দ করা হয়। K-মিন্স ক্লাস্টারিং-এ ব্যবহৃত ধাপসমূহ:
K প্রাথমিক ক্লাস্টার সেন্ট্রয়েড c1, c2, c3 ... ck নির্বাচন করুন।
প্রতিটি ইনস্ট্যান্স x কে S ক্লাস্টারে বরাদ্দ করুন যার সেন্ট্রয়েড x-এর নিকটতম।
প্রতিটি ক্লাস্টারের জন্য, এর সেন্ট্রয়েড পুনর্গণনা করুন যেসব এলিমেন্ট সেটি ধারণ করে তার ওপর ভিত্তি করে।
স্টেপ (b) এ ফিরে যান যতক্ষণ না কনভার্জেন্স সম্পন্ন হয়।
অবজেক্ট (ডেটা পয়েন্ট)গুলোকেও K ক্লাস্টারে আলাদা করুন।
ক্লাস্টার সেন্টার (সেন্ট্রয়েড) = ক্লাস্টারের সকল ডেটা পয়েন্টের গড়।
প্রতিটি পয়েন্টকে সেই ক্লাস্টারের কাছে বরাদ্দ করুন যার সেন্ট্রয়েড নিকটতম (দূরত্ব ফাংশন ব্যবহার করে)।
গড়ের প্রাথমিক মান গুলো যাচ্ছে arbitrarily বরাদ্দ করা হয়। এগুলো র্যান্ডমলি বরাদ্দ করা যেতে পারে বা হয়তো প্রথম k ইনপুট আইটেমের মান থেকেও নেওয়া যেতে পারে। কনভার্জেন্স এলিমেন্ট বর্গ ত্রুটির ওপর ভিত্তি করে হতে পারে, কিন্তু বাধ্যতামূলক নয়। উদাহরণস্বরূপ, অ্যালগরিদমটি ভিন্ন ক্লাস্টারে বরাদ্দ করা হয়। অন্যান্য টার্মিনেশন কৌশল শুধু একটি নির্দিষ্ট ইটেরেশন সংখ্যায় লক করা থাকে। একটি সর্বোচ্চ ইটেরেশন সংখ্যা যোগ করা যেতে পারে কনভার্জেন্স না হলেও শপিং নিশ্চিত করতে।
অ্যালগরিদম
ইনপুট (Input)
D = {t1t2 ... tn} // এলিমেন্টের সেট k // ইচ্ছিত ক্লাস্টার সংখ্যা
আউটপুট (Output)
K // ক্লাস্টার সেট
K-মিন্স অ্যালগরিদম -
প্রাথমিক মান বরাদ্দ করুন গড়ের জন্য m1m2... mk
রিপিট
প্রতিটি আইটেম ti কে সেই ক্লাস্টারে বরাদ্দ করুন যেটির সবচেয়ে নিকটতম গড় রয়েছে
প্রতিটি ক্লাস্টারের জন্য নতুন গড় গণনা করুন
যতক্ষণ না কনভার্জেন্স κρι্টেরিয়া পূরণ হয়
নিয়ারেস্ট নেইবর অ্যালগরিদম (Nearest neighbour algorithm)
সিংগেল লিংক কৌশলের সমান একটি অ্যালগরিদমকে নিয়ারেস্ট নেইবর অ্যালগরিদম বলা হয়। এই সিরিয়াল অ্যালগরিদমে, আইটেমগুলো পুনরাবৃত্তিমূলকভাবে বর্তমান ক্লাস্টারগুলোর সাথে একত্রিত হয় যেগুলো সবচেয়ে নিকট। এই অ্যালগরিদমে, একটি থ্রেশহোল্ড t নির্ধারণ করে যে আইটেমগুলো বিদ্যমান ক্লাস্টারে যোগ করা হবে কি না নতুন ক্লাস্টার তৈরি হবে।
অ্যালগরিদম
ইনপুট (Input)
D = {t1t2 ... tn} // এলিমেন্টের সেট A // অ্যাডজেসেন্সি ম্যাট্রিক্স যেটি এলিমেন্টের মধ্যে দূরত্ব দেখায়
আউটপুট (Output)
K // ক্লাস্টার সেট নিয়ারেস্ট নেইবর অ্যালগরিদম K1 = {t1}; K = {K1}; k = 1; for i = 2 to n do find the tm in some cluster Km in K such that dis {ti, tm} is the smallest; If dis {ti, tm} ≤ t then Km = Km ∪ ti else k = k + 1; Kk = {ti}
