সমষ্টিগত শ্রেণিবিন্যাস ক্লাস্টারিং হল একটি বটম-আপ ক্লাস্টারিং পদ্ধতি যেখানে ক্লাস্টারগুলিতে সাব-ক্লাস্টার থাকে, যার ধারাবাহিকভাবে সাব-ক্লাস্টার ইত্যাদি থাকে। এটি প্রতিটি বস্তুকে তার ক্লাস্টারে সনাক্ত করে শুরু করে এবং তারপর এই পারমাণবিক ক্লাস্টারগুলিকে উচ্চতর এবং উচ্চতর ক্লাস্টারে একত্রিত করে যতক্ষণ না কিছু বস্তু না হয়। একটি একক ক্লাস্টারে বা যতক্ষণ না এটি একটি নির্দিষ্ট পরিসমাপ্তি শর্ত প্রয়োজন। এই ধরণের জন্য বেশ কিছু শ্রেণিবদ্ধ ক্লাস্টারিং পদ্ধতি ব্যবহার করা হয়। তারা শুধুমাত্র তাদের মধ্যে ক্লাস্টার সাদৃশ্যের বর্ণনায় আলাদা।
উদাহরণস্বরূপ, AGNES (Agglomerative Nesting) নামক একটি পদ্ধতির জন্য একক-লিঙ্ক কৌশল প্রয়োজন এবং নিম্নরূপ কাজ করে। একটি আয়তক্ষেত্রে স্থাপন করা বস্তুর গ্রুপ আছে বিবেচনা করুন. প্রাথমিকভাবে, প্রতিটি বস্তুর নিজস্ব একটি ক্লাস্টারে অবস্থিত। তাই ক্লাস্টারগুলিকে ক্লাস্টারের সবচেয়ে কাছের বস্তুগুলির মধ্যে ন্যূনতম ইউক্লিডীয় দূরত্বের সাথে ক্লাস্টারগুলিকে একত্রিত করার কিছু নীতি অনুসারে ধাপে ধাপে একত্রিত করা হয়৷
শ্রেণিবদ্ধ ক্লাস্টারিংকে গ্রাফিকভাবে দেখানো হয় একটি গাছের মতো ডায়াগ্রাম যা ডেনড্রোগ্রাম নামে পরিচিত, যা ক্লাস্টার-সাবক্লাস্টার অ্যাসোসিয়েশন এবং ক্লাস্টারগুলিকে যে ক্রমে একত্রিত করা হয়েছিল (সমষ্টিগত দৃষ্টিভঙ্গি) বা বিভক্ত (বিভাজনমূলক দৃশ্য) উভয়ই দেখায়।
মৌলিক সমষ্টিগত শ্রেণিবিন্যাস ক্লাস্টারিং অ্যালগরিদম।
-
প্রয়োজনে প্রক্সিমিটি ম্যাট্রিক্স গণনা করুন।
-
পুনরাবৃত্তি করুন
-
নিকটতম দুটি ক্লাস্টার মার্জ করুন৷
৷ -
নতুন ক্লাস্টার এবং প্রাথমিক ক্লাস্টারগুলির মধ্যে প্রক্সিমিটি প্রতিফলিত করতে প্রক্সিমিটি ম্যাট্রিক্স রিফ্রেশ করুন৷
-
যতক্ষণ না শুধুমাত্র একটি ক্লাস্টার অবশিষ্ট থাকে।
ক্লাস্টার প্রক্সিমিটি সাধারণত একটি নির্দিষ্ট ধরনের ক্লাস্টার দিয়ে সংজ্ঞায়িত করা হয়। উদাহরণস্বরূপ, MIN, MAX এবং গ্রুপ গড় সহ বেশ কয়েকটি সমষ্টিগত শ্রেণিবদ্ধ ক্লাস্টারিং কৌশলগুলি ক্লাস্টারগুলির একটি গ্রাফ-ভিত্তিক দৃশ্য থেকে আসে৷
MIN ক্লাস্টার প্রক্সিমিটিকে একাধিক ক্লাস্টারে থাকা দুটি বিন্দুর মধ্যে প্রক্সিমিটি হিসাবে সংজ্ঞায়িত করে, অথবা গ্রাফ পদ্ধতি ব্যবহার করে, নোডের কয়েকটি উপসেটে দুটি নোডের মধ্যে সবচেয়ে ছোট প্রান্ত।
বিকল্পভাবে, MAX ক্লাস্টার প্রক্সিমিটি বা গ্রাফ পদ্ধতি ব্যবহার করে একাধিক ক্লাস্টারের সবচেয়ে দূরবর্তী দুটি বিন্দুর মধ্যে প্রক্সিমিটি নেয়, নোডের বিভিন্ন উপসেটে দুটি নোডের মধ্যে সর্বোচ্চ প্রান্ত।
উপস্থাপিত ধারণা সমষ্টিগত শ্রেণিবিন্যাস ক্লাস্টারিং অ্যালগরিদমের জন্য একটি প্রক্সিমিটি ম্যাট্রিক্স প্রয়োজন। এর জন্য প্রয়োজন $\mathrm{\frac{1}{2}m^2}$ প্রক্সিমিটি (প্রক্সিমিটি ম্যাট্রিক্সকে সিমেট্রিক বিবেচনা করে) যেখানে m হল একাধিক ডেটা পয়েন্ট। ক্লাস্টারগুলির ট্র্যাক বজায় রাখার জন্য প্রয়োজনীয় স্থানটি একাধিক ক্লাস্টারগুলির সমানুপাতিক, যা m-1, সিঙ্গলটন ক্লাস্টারগুলি বাদ দিয়ে। অতএব, মোট স্থান জটিলতা হল $\mathrm{O(m^2)}$।
মৌলিক সমষ্টিগত শ্রেণিবিন্যাস ক্লাস্টারিং অ্যালগরিদমের বিশ্লেষণ গণনাগত জটিলতার বিষয়েও সহজ। প্রক্সিমিটি ম্যাট্রিক্স গণনা করতে $\mathrm{O(m^2)}$ সময় প্রয়োজন। সেই ধাপের পরে, m - 1 পুনরাবৃত্তি রয়েছে যেখানে ধাপ 3 এবং 4 রয়েছে কারণ শুরুতে m ক্লাস্টার রয়েছে এবং প্রতিটি পুনরাবৃত্তির সময় দুটি ক্লাস্টার একত্রিত হয়।
