অগ্লোমেরেটিভ ক্লাস্টারিং অ্যালগরিদম কী?

অগ্লোমেরেটিভ ক্লাস্টারিং অ্যালগরিদম (Agglomerative Clustering Algorithm)

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

উদাহরণস্বরূপ, AGNES (Agglomerative Nesting) নামে একটি পদ্ধতি, সিংগেল-লিংক কৌশল প্রয়োজন এবং নিম্নরূপ কাজ করে। একটি আয়তক্ষেত্রে অবজেক্ট গোষ্ঠী থাকা অনুমান করুন। প্রাথমিকভাবে, প্রতিটি অবজেক্টকে তার নিজস্ব ক্লাস্টারে রাখা হয়। অতএব ক্লাস্টারগুলি ধাপে ধাপে একত্রিত হয় কিছু নীতির মতে যেমন ক্লাস্টারের মধ্যে সবচেয়ে নিকটবর্তী অবজেক্টের মধ্যে ন্যূনতম ইউক্লিডিয়ান দূরত্বের ক্লাস্টার একত্রিত করা।

K-মিন্স পদ্ধতি ক্লাস্টারিং-এ একটি নির্দিষ্ট ক্লাস্টার সংখ্যার সাথে শুরু হয় এবং সকল ডেটাকে ঠিক সেই সংখ্যক ক্লাস্টারে বরাদ্দ করে। অন্য একটি ক্লাস পদ্ধতি অগ্লোমেরেশন (agglomeration) দিয়ে কাজ করে। এই পদ্ধতিগুলো প্রতিটি ডেটা পয়েন্ট তার নিজস্ব ক্লাস্টার গঠন দিয়ে শুরু করে এবং ধীরে ধীরে সেগুলোকেও একত্রিত করে 점점 বড় বড় ক্লাস্টারে যতক্ষণ না সব পয়েন্ট একটি বড় ক্লাস্টারে একত্রিত হয়।

প্রথম প্রক্রিয়া হল একটি সিমিলারিটি ম্যাট্রিক্স তৈরি করা। সিমিলারিটি ম্যাট্রিক্স হল কিছু জোড়ার দূরত্ব বা সাদৃশ্যের ডিগ্রির একটি টেবিল ক্লাস্টারগুলির মধ্যে। প্রাথমিকভাবে, সিমিলারিটি ম্যাট্রিক্স একক জোড়া রেকর্ডের মধ্যে জোড়ার দূরত্ব ধারণ করে।

রেকর্ডের মধ্যে সাদৃশ্যের বেশ কিছু মাপ রয়েছে, যেমন ইউক্লিডিয়ান দূরত্ব, ভেক্টরের মধ্যে কোণ, এবং কানেক্টিং এবং নন-কানেক্টিং ক্যাটাগরিক্যাল ফিল্ডের অনুপাত।

দেখা যেতে পারে N অরিজিনাল ক্লাস্টার N ডেটা পয়েন্টের জন্য, N² মেজারমেন্ট কম্পিউটেশন প্রয়োজন দূরত্ব টেবিল তৈরি করতে। যদি সিমিলারিটি মাপ একটি সত্য দূরত্ব মেট্রিক হয়, তবে তার অর্ধেকই যথেষ্ট কারণ কিছু সত্য দূরত্ব মেট্রিক এই নিয়ম মেনে চলে যে Distance(X, Y) = Distance(Y, X)।

গণিতের ভাষায়, সিমিলারিটি ম্যাট্রিক্স লোয়ার ট্রाए্যাঙ্গুলার। পরবর্তী প্রক্রিয়া হল সিমিলারিটি ম্যাট্রিক্সে সবচেয়ে ছোট মান খুঁজে বের করা। এটি সনাক্ত করে যে দুটি ক্লাস্টার যেগুলো একে অপরের সাথে সবচেয়ে বেশি সাদৃশ্যপূর্ণ। এই দুটি ক্লাস্টারকে একটি নতুন ক্লাস্টারে একত্রিত করা হয় এবং সিমিলারিটি ম্যাট্রিক্স আপডেট করা হয় দুটি সারি যেগুলো প্যারেন্ট ক্লাস্টার বর্ণনা করত 第三者 দিয়ে প্রতিস্থাপন করে যা মের্জড ক্লাস্টার এবং বাকি ক্লাস্টারগুলির মধ্যে দূরত্ব বর্ণনা করে।

এখন N - 1 ক্লাস্টার এবং N - 1 সারি থাকে সিমিলারিটি ম্যাট্রিক্সে। মের্জ স্টেপ N - 1 বার ইটারেট করা যেতে পারে, যাতে সকল ডেটা একই বড় ক্লাস্টারের অন্তর্গত হয়। প্রতিটি ইটারেশন চিহ্নিত করে কোন ক্লাস্টারগুলো একত্রিত হয়েছে এবং তাদের মধ্যে দূরত্ব। এই তথ্যটি নির্ধারণ করতে পারে কোন ধরনের ক্লাস্টারিং ব্যবহার করা উচিত।