অগ্লোমেরেটিভ হায়ারার্কিক্যাল ক্লাস্টারিং
অগ্লোমেরেটিভ হায়ারার্কিক্যাল ক্লাস্টারিং একটি বটম-আপ ক্লাস্টারিং পদ্ধতি যেখানে ক্লাস্টারগুলোর সাব-ক্লাস্টার থাকে, যারা lầnক্রমে সাব-ক্লাস্টার রাখে, ইত্যাদি। এটি প্রতিটি অবজেক্টকে তার নিজস্ব ক্লাস্টারে রাখতে শুরু করে এবং তারপর এই পারমাণবিক ক্লাস্টারগুলোকেও 점점 বড় বড় ক্লাস্টারে একত্রিত করে যতক্ষণ না সব অবজেক্ট একটি একক ক্লাস্টারে আছেন অথবা একটি নির্দিষ্ট টার্মিনেশন শর্ত পূরণ হয়। অনেক হায়ারার্কিক্যাল ক্লাস্টারিং পদ্ধতি এই ধরনের ব্যবহার করে। সেগুলো শুধুমাত্র তাদের ইন্টার-ক্লাস্টার সাদৃশ্যের সংজ্ঞায়িতে ভিন্ন।
উদাহরণস্বরূপ, AGNES (Agglomerative Nesting) নামে একটি পদ্ধতি সিংগেল-লিংক কৌশল ব্যবহার করে এবং নিম্নরূপ কাজ করে: একটি আয়তক্ষেত্রে অবজেক্ট গোষ্ঠী থাকা অনুমান করুন। প্রাথমিকভাবে, প্রতিটি অবজেক্টকে তার নিজস্ব ক্লাস্টারে রাখা হয়। অতএব ক্লাস্টারগুলি ধাপে ধাপে একত্রিত হয় ক্লাস্টারের মধ্যে সবচেয়ে নিকটবর্তী অবজেক্টগুলির মধ্যে ন্যূনতম ইউক্লিডিয়ান দূরত্বের নীতির উপর ভিত্তি করে।
হায়ারার্কিক্যাল ক্লাস্টারিং গ্রাফিক্যালি একটি ডেন্ড্রোগ্রাম (dendrogram) নামে ট্রি-সদৃশ ডায়াগ্রাম দিয়ে দেখানো হয়, যা ক্লাস্টার-সাবক্লাস্টার সম্পর্ক এবং ক্লাস্টারগুলোর একত্রিত হওয়ার ক্রম (অগ্লোমেরেটিভ ভিউ) বা বিভক্ত হওয়ার ক্রম (ডিভিসিভ ভিউ) উভয়ই দেখায়।
মূল অগ্লোমেরেটিভ হায়ারার্কিক্যাল ক্লাস্টারিং অ্যালগরিদম
প্রাক্সিমিটি ম্যাট্রিক্স গণনা করুন, যদি প্রয়োজন হয়।
রিপিট করুন
সবচেয়ে নিকটবর্তী দুটি ক্লাস্টার একত্রিত করুন।
নতুন ক্লাস্টার এবং মূল ক্লাস্টারগুলির মধ্যে প্রাক্সিমিটি প্রতিফলিত করার জন্য প্রাক্সিমিটি ম্যাট্রিক্স আপডেট করুন।
যতক্ষণ না শুধুমাত্র একটি ক্লাস্টার থাকে।
ক্লাস্টার প্রাক্সিমিটি সাধারণত একটি নির্দিষ্ট ধরনের ক্লাস্টারের সাথে সংজ্ঞায়িত হয়। উদাহরণস্বরূপ, অনেক অগ্লোমেরেটিভ হায়ারার্কিক্যাল ক্লাস্টারিং কৌশল (MIN, MAX, এবং গ্রুপ অ্যাভারেজ) গ্রাফ-ভিত্তিক ক্লাস্টার দৃষ্টিভঙ্গি থেকে আসে।
MIN ক্লাস্টার প্রাক্সিমিটি সংজ্ঞায়িত করে দুটি ক্লাস্টারে থাকা সবচেয়ে নিকটবর্তী দুটি পয়েন্টের প্রাক্সিমিটি হিসেবে, অথবা গ্রাফ পদ্ধতিতে, দুটি ভিন্ন নোড সাবসেটের মধ্যে সবচেয়ে ছোট এজ হিসেবে।
বিপরীতভাবে, MAX দুটি ভিন্ন ক্লাস্টারের মধ্যে সবচেয়ে দূরবর্তী দুটি পয়েন্টের প্রাক্সিমিটিকে ক্লাস্টার প্রাক্সিমিটি হিসেবে নেয়, অথবা গ্রাফ পদ্ধতিতে, ভিন্ন নোড সাবসেটের মধ্যে সবচেয়ে বড় এজ।
প্রস্তুত অগ্লোমেরেটিভ হায়ারার্কিক্যাল ক্লাস্টারিং অ্যালগরিদম একটি প্রাক্সিমিটি ম্যাট্রিক্স দরকার। এটিকে ½m² প্রাক্সিমিটি স্টোরেজ দরকার (প্রাক্সিমিটি ম্যাট্রিক্স সিমেট্রিক ধরে নিয়ে) যেখানে m হল ডেটা পয়েন্টের সংখ্যা। ক্লাস্টার ট্র্যাক রাখতে স্পেস m-1 এর অনুপাতিক, সিঙ্গলটন ক্লাস্টার বাদ দিয়ে। তাই মোট স্পেস কমপ্লেক্সিটি O(m²)।
মূল অগ্লোমেরেটিভ হায়ারার্কিক্যাল ক্লাস্টারিং অ্যালগরিদমের কম্পিউটেশনাল কমপ্লেক্সিটি পক্ষে বিশ্লেষণও সহজ। প্রাক্সিমিটি ম্যাট্রিক্স গণনার জন্য O(m²) সময় লাগে। তারপর m-1 ইটারেশন থাকে যাতে স্টেপ ৩ এবং ৪ রয়েছে কারণ শুরুতে m ক্লাস্টার থাকে এবং প্রতিটি ইটারেশনে দুটি ক্লাস্টার মের্জ হয়।
