একটি পার্টিশনিং ক্লাস্টারিং পদ্ধতি বাঞ্ছনীয় কারণ এটি সেট এবং তাদের ক্লাস্টার কেন্দ্রের মধ্যে দূরত্ব ন্যূনতম করে। যদি k-মিনস পদ্ধতি বেছে নেওয়া হয়, বাধার অস্তিত্বে একটি ক্লাস্টার কেন্দ্র অনুপলব্ধ হতে পারে।
উদাহরণস্বরূপ, ক্লাস্টার একটি হ্রদের মাঝপথে পড়তে পারে। অন্য কথায়, k-মেডয়েডস (k-medoids) পদ্ধতি ক্লাস্টারের ভেতর থেকে একটি অবজেক্টকে কেন্দ্র হিসেবে বেছে নেয় এবং এইভাবে সমস্যা অপ্রতিহত থাকতে পারে না বলে নিশ্চিত করে।
দূরত্ব গণনা এবং বাধা
প্রতিবার একটি নতুন মেডয়েড বেছে নেওয়া হলে, প্রতিটি অবজেক্ট এবং তার নতুন বরাদ্দ করা ক্লাস্টার কেন্দ্রের মধ্যে দূরত্ব পুনরায় গণনা করতে হয়। যেহেতু দুটি অবজেক্টের মধ্যে বাধা থাকতে পারে, দুটি অবজেক্টের মধ্যে দূরত্ব জ্যামিতিক গণনা (যেমন ট্রায়্যাঙ্গুলেশন) দ্বারা প্রাপ্ত হতে পারে।
যদি বড় সংখ্যক অবজেক্ট এবং বাধা থাকে, কম্পিউটেশনাল খরচ বেশি হতে পারে। বাধাসহ ক্লাস্টারিং সমস্যাটি একটি গ্রাফিক্যাল বর্ণনা ব্যবহার করে সংজ্ঞায়িত করা যায়।
দৃষ্ট্য গ্রাফ (Visibility Graph)
প্রথমে, একটি পয়েন্ট p, অঞ্চল R-এ অন্য একটি পয়েন্ট q-থেকে দৃশ্যমান (visible) যদি p এবং q-কে সংযুক্ত রেখা কোনো বাধা ছেদ করে না।
একটি দৃষ্ট্য গ্রাফ হল গ্রাফ VG = (V, E), যেখানে বাধার প্রতিটি ভার্টেক্সের সমতুল্য একটি নোড V-এ থাকে এবং দুটি নোড v₁ এবং v₂ V-এ একটি এজ E-তে সংযুক্ত থাকে যদি এবং কেবল যদি তাদের প্রতীকীకరণ করা ভার্টেক্সগুলো একে অপরের কাছে দৃশ্যমান হয়।
VG' = (V', E') কে VG থেকে দুটি অতিরিক্ত পয়েন্ট p এবং q V'-এ যোগ করে তৈরি একটি দৃষ্ট্য গ্রাফ মনে করুন। E' V' এর দুটি পয়েন্ট সংযুক্ত করার একটি এজ ধারণ করে যদি দুটি পয়েন্ট পারস্পরিকভাবে দৃশ্যমান হয়।
অপ্টিমাইজেশন পদ্ধতি
যেকোনো দুটি অবজেক্ট বা পয়েন্ট সেটের মধ্যে দূরত্ব গণনার খরচ কমাতে, একাধিক প্রিপ্রসেসিং এবং অপ্টিমাইজেশন পদ্ধতি ব্যবহার করা যায়। একটি পদ্ধতিতে কোনদিকটে পয়েন্টগুলিকে মাইক্রোক্লাস্টারে গোষ্ঠীভুক্ত করা হয়। এটি প্রথমে অঞ্চল R-কে ট্রায়্যাঙ্গুলেট করে ট্রায়্যাঙ্গেলে ভাগ করে, এবং তারপর একই ট্রায়্যাঙ্গেলে আশেপাশের পয়েন্টগুলিকে BIRCH বা DBSCAN-सদৃশ পদ্ধতি ব্যবহার করে মাইক্রোক্লাস্টারে একত্রিত করে।
একক পয়েন্টের বদলে মাইক্রোক্লাস্টার প্রক্রিয়া করে teljes গণনা হ্রাস করা যায়। এরপর, প্রিকম্পিউটেশন প্রয়োগ করা হয় দুটি ধরনের জয়েন ইন্ডেক্স তৈরি করতে ছোটতম পথের গণনাের ওপর ভিত্তি করে —
- VV ইন্ডেক্স: বাধা ভার্টেক্সের যেকোনো যুগলের জন্য।
- MV ইন্ডেক্স: মাইক্রোক্লাস্টার এবং বাধা ভার্টেক্সের যেকোনো যুগলের জন্য। এটি আরও সমগ্র পারফরম্যান্স অপ্টিমাইজ করতে সাহায্য করে।
এই প্রিপ্রেসেশন এবং অপ্টিমাইজেশনের সাথে, যেকোনো দুটি পয়েন্টের মধ্যে দূরত্ব (মাইক্রোক্লাস্টারের গ্র্যানুলারিটিতে) কার্যকরভাবে গণনা করা যায়। তাই, ক্লাস্টারিং প্রক্রিয়া একটি সাধারণ কার্যকর k-মেডয়েডস অ্যালগরিদম (যেমন CLARANS) এর সদৃশভাবে বাস্তবায়ন করা যায় এবং বড় ডেটাসেটের জন্য সেরা ক্লাস্টারিং গুণমান অর্জন করা যায়।
