স্পার্সিফিকেশন (Sparsification)
m ডেটা পয়েন্টের জন্য m x m প্রাক্সিমিটি ম্যাট্রিক্সকে একটি ডেন্স গ্রাফ হিসেবে সংজ্ঞায়িত করা যায় যেখানে প্রতিটি নোড অন্য সব নোডের সাথে সংযুক্ত এবং যেকোনো দুটি নোডের মধ্যে এজের ওজন তাদের জোড়ার প্রাক্সিমিটি অনুসরণ করে। যদিও প্রতিটি অবজেক্টের অন্য সব অবজেক্টের সাথে কোনো না কোনো সাদৃশ্য থাকে, কিন্তু অধিকাংশ ডেটাসেটে, অবজেক্টগুলো শুধু কয়েকটি অবজেক্টের সাথে বেশি সাদৃশ্যপূর্ণ এবং অধিকাংশ অন্যান্য অবজেক্টের সাথে দুর্বল সাদৃশ্যপূর্ণ।
এই বৈশিষ্ট্যটি প্রাক্সিমিটি গ্রাফ (ম্যাট্রিক্স) স্পার্সিফাই করতে ব্যবহার করা যেতে পারে, যাতে ক্লাস্টারিং প্রসেস শুরু করার আগে কম-সাদৃশ্য (উচ্চ-বিসাদৃশ্য) মানগুলোকেও ০ করে দেওয়া হয়। স্পার্সিফিকেশন বাস্তবায়ন করা যেতে পারে, উদাহরণস্বরূপ, সাব থ্রেশহোল্ডের নিচে সাদৃশ্য (অথবা উপরে বিসাদৃশ্য) থাকা সকল লিংক কাটিয়ে, অথবা একটি পয়েন্টের k নিকটতম নেইবরের লিংক মাত্র রাখা। এই পদ্ধতিটি k-নিকটতম নেইবর গ্রাফ তৈরি করে।
স্পার্সিফিকেশনের সুবিধা
ডেটা আকার কমানো (Data size is reduced)
ডেটা ক্লাস্টার করার জন্য প্রক্রিয়া করার ডেটার পরিমাণ অত্যন্ত কমে যায়। স্পার্সিফিকেশন প্রাক্সিমিটি ম্যাট্রিক্সের ৯৯% এরও বেশি এন্ট্রি দূর করতে পারে। ফলে, হ্যান্ডেল করা যাওয়া সমস্যার আকার বৃদ্ধি পায়।
ক্লাস্টারিং ভালো কাজ করতে পারে (Clustering may work better)
স্পার্সিফিকেশন কৌশলগুলো একটি অবজেক্টের তার নিকটতম নেইবরের সাথে লিংক রাখে কিন্তু আরও ভিন্ন অবজেক্টের সাথে সংযোগ কেটে দেয়। এটি নিকটতম নেইবর সিদ্ধান্তের সাথে সอดরশী যে একটি অবজেক্টের নিকটতম নেইবররা অবজেক্টটির মতো একই ক্লাস (ক্লাস্টার) এর অন্তর্ভুক্ত। এটি নয়েজ ও আউটলায়ারর প্রভাব কমানো এবং ক্লাস্টারগুলির মধ্যে পার্থক্য স্পষ্ট করে।
গ্রাফ পার্টিশনিং অ্যালগরিদম ব্যবহার করা যায় (Graph partitioning algorithms can be used)
স্পার্স গ্রাফের মিন-কাট পার্টিশনিং খুঁজে বের করার হিউরিস্টিক অ্যালগরিদমের ওপর প্রচুর কাজ হয়েছে, বিশেষ করে প্যারালেল কম্পিউটিং এবং ইন্টিগ্রেটেড সার্কিট ডিজাইনের ক্ষেত্রে। প্রাক্সিমিটি গ্রাফের স্পার্সিফিকেশন গ্রাফ পার্টিশনিং অ্যালগরিদমকে ক্লাস্টারিং ফেজে ব্যবহার করার জন্য উপযুক্ত করে তোলে যেমন Opossum এবং Chameleon গ্রাফ পার্টিশনিং ব্যবহার করে।
প্রাক্সিমিটি গ্রাফের স্পার্সিফিকেশনকে প্রকৃত ক্লাস্টারিং অ্যালগরিদম প্রয়োগ করার আগে একটি প্রারম্ভিক ধাপ হিসেবে বিবেচনা করা উচিত। একটি ভালো স্পার্সিফিকেশন প্রাক্সিমিটি ম্যাট্রিক্সকে সংযুক্ত উপাদানগুলিতে ভাগ করতে পারে যা ইচ্ছিত ক্লাস্টারর সাথে সম্পর্কিত, কিন্তু প্র্যাকটিসে এটি হয়।
একটি একক এজ দুটি ক্লাস্টার সংযুক্ত করতে পারে বা একটি একক ক্লাস্টার একাধিক ডিসকানেক্টেড সাব-ক্লাস্টারে ভাগ হতে পারে। আসলে, যখন জারভিস-প্যাট্রিক এবং SNN ঘনত্ব-ভিত্তিক ক্লাস্টারিং ব্যবহার করে, স্পার্স প্রাক্সিমিটি গ্রাফকে পরিবর্তন করা হয় একটি নতুন প্রাক্সিমিটি গ্রাফ তৈরি করতে। এই নতুন প্রাক্সিমিটি গ্রাফকেও স্পার্সিফাই করা যেতে পারে। ক্লাস্টারিং অ্যালগরিদম সেই প্রাক্সিমিটি গ্রাফের সাথে কাজ করে যা এই সব প্রিপ্রসেসিং স্টেপের ফলাফল।
