একটি বিভাজন ক্লাস্টারিং পদ্ধতি পছন্দনীয় কারণ এটি সেট এবং তাদের ক্লাস্টার কেন্দ্রগুলির মধ্যে দূরত্ব কমিয়ে দেয়। যদি এটি k-means পদ্ধতি বেছে নিতে পারে, তাহলে বাধার অস্তিত্বের কারণে একটি ক্লাস্টার কেন্দ্র পাওয়া যাবে না।
উদাহরণস্বরূপ, ক্লাস্টারটি একটি হ্রদের কেন্দ্রে হতে পারে। অন্য কথায়, k-medoids পদ্ধতি ক্লাস্টারের ভিতরে একটি কেন্দ্র হিসাবে একটি বস্তুকে বেছে নেয় এবং এইভাবে গ্যারান্টি দেয় যে কোনও সমস্যা দেখা যাবে না।
প্রতিটি সময় একটি নতুন মেডয়েড নির্বাচন করা হয়, প্রতিটি বস্তু এবং তার নতুন নির্বাচিত ক্লাস্টার কেন্দ্রের মধ্যে দূরত্ব পুনরায় গণনা করতে হবে। যেহেতু দুটি বস্তুর মধ্যে বাধা থাকতে পারে, তাই দুটি বস্তুর মধ্যে দূরত্ব জ্যামিতিক গণনা (যেমন, ত্রিভুজাকরণ জড়িত) দ্বারা প্রাপ্ত করা যেতে পারে।
বিপুল সংখ্যক বস্তু এবং প্রতিবন্ধকতা থাকলে গণনামূলক খরচ বেশি হতে পারে। একটি গ্রাফিকাল বর্ণনা ব্যবহার করে বাধা সমস্যা সহ ক্লাস্টারিং সংজ্ঞায়িত করা যেতে পারে। প্রথমত, একটি বিন্দু, p, অন্য বিন্দু থেকে স্পষ্ট হয়, q, অঞ্চলে, R, যদি সরলরেখা সংলগ্ন p এবং q কিছু বাধাকে ছেদ না করে।
একটি দৃশ্যমানতা গ্রাফ হল গ্রাফ, V G =(V, E), বাধাগুলির প্রতিটি শীর্ষবিন্দু সহ V এবং দুটি নোডে একটি সমতুল্য নোড রয়েছে, v1 এবং v2 , V-তে E-এর একটি প্রান্ত দ্বারা মিলিত হয় যদি এবং শুধুমাত্র যদি তারা সংজ্ঞায়িত সমতুল্য শীর্ষবিন্দুগুলি একে অপরের কাছে দৃশ্যমান হয়।
VG' =(V', E') V'-তে দুটি অতিরিক্ত বিন্দু, p এবং q সন্নিবেশ করে VG থেকে তৈরি একটি দৃশ্যমানতা গ্রাফ হতে দিন। যদি দুটি পয়েন্ট যৌথভাবে দৃশ্যমান হয় তাহলে V0 তে দুটি পয়েন্ট যোগ করে E' একটি প্রান্ত অন্তর্ভুক্ত করে৷
যেকোন দুই সেট অবজেক্ট বা পয়েন্টের মধ্যে দূরত্ব গণনার খরচ কমাতে এটি ব্যবহার করা যেতে পারে, একাধিক প্রিপ্রসেসিং এবং অপ্টিমাইজেশন পদ্ধতি ব্যবহার করা যেতে পারে। একটি অ্যাপ্রোচ গ্রুপ পয়েন্ট রয়েছে যা মাইক্রোক্লাস্টারের কাছাকাছি রয়েছে। এটি প্রথমে R অঞ্চলটিকে ত্রিভুজে ত্রিভুজ করে এবং তারপর অনুরূপ ত্রিভুজের কাছাকাছি বিন্দুগুলিকে মাইক্রোক্লাস্টারে একত্রিত করে, BIRCH বা DBSCAN-এর অনুরূপ পদ্ধতি ব্যবহার করে সম্পন্ন করা যেতে পারে।
একক পয়েন্টের পরিবর্তে মাইক্রোক্লাস্টার প্রক্রিয়াকরণ করে, সম্পূর্ণ গণনা হ্রাস করা হয়। এর পরে, দুটি ধরণের যোগ সূচক তৈরি করার জন্য পূর্ব গণনা কার্যকর করা যেতে পারে যা সংক্ষিপ্ততম পথগুলির গণনার উপর নির্ভর করে -
-
VV সূচক, কিছু জোড়া বাধা শীর্ষবিন্দুর জন্য।
-
MV সূচক, কিছু জোড়া মাইক্রোক্লাস্টার এবং বাধা শীর্ষবিন্দুর জন্য। এটি সূচকগুলিকে আরও সামগ্রিক কর্মক্ষমতাকে আরও অপ্টিমাইজ করতে সহায়তা করে৷
এই ধরনের পূর্ব গণনা এবং অপ্টিমাইজেশানের মাধ্যমে, যেকোনো দুটি বিন্দুর মধ্যে দূরত্ব (মাইক্রোক্লাস্টারের গ্রানুলারিটি পদ্ধতিতে) কার্যকরভাবে গণনা করা যেতে পারে। তাই, ক্লাস্টারিং প্রক্রিয়াটি CLARANS সহ একটি সাধারণ কার্যকরী কে-মিডয়েড অ্যালগরিদমের অনুরূপভাবে প্রয়োগ করা যেতে পারে এবং বিশাল ডেটা সেটের জন্য সেরা ক্লাস্টারিং গুণমান অর্জন করতে পারে।
