সফ্টওয়্যার ইঞ্জিনিয়ার হিসাবে, আমরা সব সময় ক্লাস্টারিং অ্যালগরিদম ব্যবহার করি। এটি অনুরূপ ব্যবহারকারীদের গোষ্ঠীবদ্ধ করা, বিষয়বস্তুকে শ্রেণীবদ্ধ করা বা ডেটাতে প্যাটার্ন সনাক্ত করা হোক না কেন, ক্লাস্টারিং প্রতারণামূলকভাবে সহজ বলে মনে হচ্ছে: ঠিক একই জিনিসগুলিকে একসাথে গোষ্ঠীবদ্ধ করুন, তাই না? আপনি হয়ত k-means, DBSCAN, বা agglomerative ক্লাস্টারিং ব্যবহার করেছেন, এই ভেবে যে আপনার ব্যবহারের ক্ষেত্রে আপনাকে সঠিক অ্যালগরিদম বেছে নিতে হবে।
কিন্তু বেশিরভাগ টিউটোরিয়াল আপনাকে যা বলবে না তা এখানে: আপনার বেছে নেওয়া প্রতিটি ক্লাস্টারিং অ্যালগরিদম মৌলিকভাবে ত্রুটিপূর্ণ। দুর্বল বাস্তবায়ন বা ভুল প্যারামিটারের কারণে নয়, বরং গণিতের কারণে। 2002 সালে, জন ক্লেইনবার্গ (এ কাগজ NIPS 2002-এ প্রকাশিত) এমন কিছু প্রমাণ করেছে যা প্রতিটি বিকাশকারীকে বিরতি দিতে হবে: কোনো ক্লাস্টারিং অ্যালগরিদমের পক্ষে তিনটি বৈশিষ্ট্য থাকা অসম্ভব যা আমরা স্বাভাবিকভাবেই চাই।
হিসাবে এটা চিন্তা CAP উপপাদ্য ক্লাস্টারিং এর যেমন বিতরণ করা সিস্টেমগুলি আপনাকে ধারাবাহিকতা, প্রাপ্যতা এবং পার্টিশন সহনশীলতার মধ্যে বেছে নিতে বাধ্য করে, ক্লেনবার্গ দেখিয়েছেন যে ক্লাস্টারিং অ্যালগরিদমগুলি আপনাকে স্কেল ইনভেরিয়েন্স, সমৃদ্ধি এবং ধারাবাহিকতার মধ্যে বেছে নিতে বাধ্য করে। আপনার তিনটিই থাকতে পারে না – কখনও, এটি একটি গাণিতিক অসম্ভব।
আপনি উত্পাদনে আপনার পরবর্তী ক্লাস্টারিং সমাধান স্থাপন করার আগে, আপনি কী ছেড়ে দিচ্ছেন তা বুঝতে হবে। আসুন এই তিনটি বৈশিষ্ট্যের মধ্যে ডুব দেওয়া যাক এবং কেন আপনাকে সর্বদা কী বলি দিতে হবে তা বেছে নিতে হবে।
আমরা উপপাদ্য সম্পর্কে কথা বলার আগে, আমাদের ক্লাস্টারিংয়ের একটি সুনির্দিষ্ট সংজ্ঞা প্রয়োজন। কাগজটি এটিকে ডেটা পয়েন্টের সেট এবং দূরত্ব ফাংশনের পরিপ্রেক্ষিতে সংজ্ঞায়িত করে যা নীচে সংজ্ঞায়িত করা হয়েছে:
আমরা সেট হিসাবে ক্লাস্টার করা ডেটা উল্লেখ করি S n পয়েন্টের।
ক্লাস্টারিং সঞ্চালনের জন্য, ক্লাস্টারিং মডেলটিকে প্রতিটি ডেটা পয়েন্টের মধ্যে যুগলভাবে দূরত্ব গণনা করতে হবে এবং এর জন্য এটির একটি দূরত্ব ফাংশন প্রয়োজন।
দূরত্ব ফাংশন একটি গাণিতিক ফাংশন যা দুটি ডেটা পয়েন্ট নেয় i এবং j পরামিতি হিসাবে, এবং তাদের মধ্যে দূরত্ব গণনা করে। যদি পরামিতি i এবং j একই ডেটা পয়েন্ট হলে এই ফাংশন দ্বারা গণনা করা তাদের মধ্যে দূরত্ব 0 হওয়া উচিত।
অবশেষে, কাগজটি ক্লাস্টারিংকে দূরত্ব ফাংশনের একটি ফাংশন হিসাবে সংজ্ঞায়িত করে dএবং ডেটা পয়েন্টের সেট S যেমন এটা পার্টিশন S ছোট উপসেটে যেখানে প্রতিটি উপসেট একটি ক্লাস্টার প্রতিনিধিত্ব করে। গাণিতিকভাবে বলতে গেলে:
দূরত্ব ফাংশন d এর পরিপ্রেক্ষিতে, ক্লাস্টারিং ফাংশনটিকে একটি ফাংশন ƒ হিসাবে সংজ্ঞায়িত করা যেতে পারে যা S এ একটি দূরত্ব ফাংশন d নেয় এবং S-এর Γ পার্টিশন প্রদান করে।
উদাহরণস্বরূপ, k-মানে অ্যালগরিদম k ক্লাস্টারের সংখ্যা নেয়, একটি দূরত্ব ফাংশন (যেমন ইউক্লিডীয় দূরত্ব ফাংশন), এবং ইনপুট হিসাবে ডেটা পয়েন্টের সেট এবং এর আউটপুট হিসাবে k ক্লাস্টারের ফলাফল। এই k ক্লাস্টারগুলি মূলত মূল ডেটাসেটের একটি বিভাজন S.
আমরা চাই আমাদের ক্লাস্টারিং অ্যালগরিদম তিনটি পছন্দসই বৈশিষ্ট্য প্রদর্শন করুক, যেগুলোকে স্কেল-ইনভেরিয়েন্স, সমৃদ্ধি এবং ধারাবাহিকতা বলা হয়। আসুন বুঝতে পারি এই বৈশিষ্ট্যগুলির অর্থ কী।
স্কেল ইনভেরিয়েন্স এমন একটি সম্পত্তি যা প্রায় খুব সুস্পষ্ট শোনাচ্ছে: আপনি যদি আপনার ডেটা পয়েন্টগুলি নেন এবং একই ফ্যাক্টর দ্বারা তাদের মধ্যে সমস্ত দূরত্ব স্কেল করেন তবে আপনার ক্লাস্টারগুলি পরিবর্তন করা উচিত নয়।
উদাহরণস্বরূপ, যদি ডেটাসেটে যেকোনো দুটি বিন্দু i,j থাকে তাহলে তাদের মধ্যকার দূরত্ব হবে d(i,j)। তারপর, যদি আমরা এই দূরত্বটিকে একটি ফ্যাক্টর 𝛼 দ্বারা পরিমাপ করি যে এটি 𝛼.d(i,j) হয়ে যায় তাহলে ক্লাস্টারিং ফলাফল অপরিবর্তিত থাকবে। এর মানে হল যে ক্লাস্টারিং অ্যালগরিদম স্কেলের সাথে অপরিবর্তনীয়।
বাস্তব জগতে, এটি আপনার ভাবার চেয়ে বেশি গুরুত্বপূর্ণ। আপনি কি কখনও:
-
আপনার পরিমাপের ইউনিট পরিবর্তন করেছেন (যেমন ফুট থেকে মিটার)
-
আপনার ডেটা ভিন্নভাবে স্বাভাবিক করা হয়েছে
-
শুধুমাত্র আপনার ক্লাস্টারিং ফলাফল সম্পূর্ণরূপে পরিবর্তিত খুঁজে পেতে আপনার বৈশিষ্ট্যগুলিতে একটি ভিন্ন স্কেলিং প্রয়োগ করেছেন? আপনার অ্যালগরিদম স্কেল অপরিবর্তনীয় না হলে এটিই ঘটে।
সমৃদ্ধি হল সম্ভাবনার বিষয় — একটি ক্লাস্টারিং অ্যালগরিদম আপনার ডেটার জন্য বোধগম্য হতে পারে এমন যেকোনো গ্রুপিং তৈরি করতে সক্ষম হওয়া উচিত।
কল্পনা করুন আপনি আপনার পোশাক বাছাই করছেন। কখনও কখনও আপনি রঙ অনুসারে (অনেক ক্লাস্টার তৈরি করে), অন্য সময় ঋতু অনুসারে (চার ক্লাস্টার) বা কেবল ‘এখনই পরিধান করুন’ এবং ‘স্টোর অ্যাওয়ে’ (দুটি ক্লাস্টার) অনুসারে পোশাকগুলিকে গ্রুপ করতে চাইতে পারেন। একটি সত্যিকারের সমৃদ্ধ ক্লাস্টারিং অ্যালগরিদম এই সমস্ত সম্ভাবনাগুলি পরিচালনা করতে সক্ষম হওয়া উচিত, আপনাকে পূর্বনির্ধারিত সংখ্যক গোষ্ঠীতে বাধ্য করবে না।
কিন্তু অনেক জনপ্রিয় অ্যালগরিদম এই প্রয়োজনীয়তা ব্যর্থ করে। উদাহরণস্বরূপ, কে-মান নিন। যে মুহুর্তে আপনি k=3 নির্দিষ্ট করেছেন, আপনি ইতিমধ্যেই দুটি ক্লাস্টার বা চারটি ক্লাস্টার খুঁজে পাওয়ার কোনো সম্ভাবনা বাতিল করে দিয়েছেন, এমনকি যদি আপনার ডেটা স্বাভাবিকভাবেই প্রস্তাব করে। এটি আপনার পোশাককে ঠিক তিনটি দলে বিভক্ত করার মতো, এমনকি যদি এটি আপনার পোশাকের জন্য অর্থপূর্ণ না হয়।
গাণিতিকভাবে বলতে গেলে: যদি f আমাদের ক্লাস্টারিং ফাংশন এবং S আমাদের ডেটাসেট, সমৃদ্ধি মানে f এর যেকোনো সম্ভাব্য পার্টিশন তৈরি করতে সক্ষম হওয়া উচিত S. অন্য কথায়, range(f) বিভাজন করার সমস্ত সম্ভাব্য উপায়ের সেটের সমান হওয়া উচিত S.
যদিও এই নমনীয়তা তত্ত্বে দুর্দান্ত শোনাচ্ছে, আপনি সম্ভবত দেখতে পাচ্ছেন কেন অনেক ব্যবহারিক অ্যালগরিদম এটিকে উৎসর্গ করে। আপনি যখন বাস্তব ডেটা বিশ্লেষণ করছেন, আপনি প্রায়শই ফলাফলগুলিকে ব্যাখ্যাযোগ্য করতে ক্লাস্টারের সংখ্যা নিয়ন্ত্রণ করতে চান
তৃতীয় বৈশিষ্ট্য, সামঞ্জস্যতা, এর অর্থ হল আপনার বিদ্যমান ক্লাস্টারগুলি ভাল হলে, অনুরূপ পয়েন্টগুলিকে আরও একই রকম এবং বিভিন্ন পয়েন্টগুলিকে আরও আলাদা করে এই ক্লাস্টারগুলিকে পরিবর্তন করা উচিত নয়।
আসুন একটি সহজ উদাহরণ দিয়ে এটি ভেঙে দেওয়া যাক। কল্পনা করুন যে আপনি সিনেমাগুলিকে তাদের বৈশিষ্ট্যের উপর ভিত্তি করে জেনারে ক্লাস্টার করেছেন। এখন:
-
দুটি অ্যাকশন মুভি আরও বেশি বিস্ফোরক দৃশ্য যুক্ত করে, তাদের একে অপরের সাথে আরও বেশি সাদৃশ্যপূর্ণ করে তোলে
-
এদিকে, একটি রোমান্টিক মুভিতে আরো রোমান্টিক দৃশ্য যুক্ত করা হয়, এটিকে অ্যাকশন মুভি থেকে আরও বেশি আলাদা করে তোলে
সামঞ্জস্যতার মানে হল যে এই পরিবর্তনগুলি যদি শুধুমাত্র বিদ্যমান গ্রুপিংকে শক্তিশালী করে, আপনার ক্লাস্টারিং অ্যালগরিদম হঠাৎ করে গ্রুপগুলিকে পুনর্গঠিত করার সিদ্ধান্ত নেবে না।
গাণিতিকভাবে বলতে গেলে: যদি Γ দূরত্ব ফাংশন ব্যবহার করে পয়েন্টগুলির একটি ক্লাস্টারিং dএবং আমরা একটি নতুন দূরত্ব ফাংশন তৈরি করি d' কোথায়:
-
যেকোনো দুই পয়েন্টের জন্য
i,jএকই ক্লাস্টারে:d'(i,j) < d(i,j)(অনুরূপ জিনিস আরো অনুরূপ হয়ে) -
যেকোনো দুই পয়েন্টের জন্য
i,jবিভিন্ন ক্লাস্টারে:d'(i,j) > d(i,j)(বিভিন্ন জিনিস আরও আলাদা হয়ে যায়)
তারপর একটি সামঞ্জস্যপূর্ণ ক্লাস্টারিং অ্যালগরিদম একই ক্লাস্টারিং তৈরি করা উচিত Γ সঙ্গে d' যেমনটি দিয়েছিল d. এই নতুন দূরত্ব ফাংশন d' বলা হয় a Γ রূপান্তর d.
কোন ক্লাস্টারিং ফাংশন নেই যা তিনটি বৈশিষ্ট্যকে সন্তুষ্ট করে: স্কেল-ইনভেরিয়েন্স, সমৃদ্ধি এবং ধারাবাহিকতা.
ক্লেইনবার্গ গাণিতিকভাবে এটি প্রমাণ করার সময় (সম্পূর্ণ প্রমাণের জন্য তার কাগজটি দেখুন), আসুন দেখি কীভাবে এই ‘তিনটির মধ্যে দুটি বাছাই করুন’ সীমাবদ্ধতা আপনি আজ ব্যবহার করছেন এমন অ্যালগরিদমগুলিতে দেখায়।
একক সংযোগ হল শ্রেণিবদ্ধ ক্লাস্টারিংয়ের একটি রূপ। এটি সহজ শুরু হয়: প্রতিটি বিন্দু তার নিজস্ব ক্লাস্টার, এবং আমরা ধীরে ধীরে নিকটতম ক্লাস্টারগুলিকে একত্রিত করি। আকর্ষণীয় অংশটি কীভাবে অ্যালগরিদম বন্ধ করবেন তা নির্ধারণ করছে। তিনটি সাধারণ মাপকাঠির মধ্যে একটি অ্যালগরিদম বন্ধ করতে ব্যবহৃত হয় এবং প্রতিটিরই অসম্ভবতা উপপাদ্যের মূলে রয়েছে।
-
আমরা কি করি: k ক্লাস্টার থাকার পর ক্লাস্টার করা বন্ধ করুন
-
আমরা যা বলি: সমৃদ্ধি
-
কেন? আমরা ঠিক k গ্রুপে নিজেদের লক করেছি। আমাদের অ্যালগরিদম কখনই k এর থেকে ছোট বা বড় আকারের অন্য কোনও গ্রুপিং আবিষ্কার করবে না।
-
আমরা যা করি: আমরা ক্লাস্টারগুলিকে একত্রিত করতে থাকি যতক্ষণ না তাদের দূরত্ব <= কিছু দূরত্ব r। যখন সমস্ত ক্লাস্টার r থেকে বড় দূরত্বে থাকে, তখন অ্যালগরিদম স্বয়ংক্রিয়ভাবে বন্ধ হয়ে যায়।
-
আমরা যা বলি: স্কেল-ইনভেরিয়েন্স
-
কেন? যদি আমরা আমাদের ডেটাকে 2x (বা অন্য কিছু ফ্যাক্টর) দ্বারা স্কেল করি, তাহলে যে ক্লাস্টারগুলি আগে একত্রিত করা যায় সেগুলি হঠাৎ করে অনেক দূরে এবং একত্রিত হবে না। এটি ক্লাস্টারিং আউটপুট পরিবর্তন করে।
-
আমরা যা করি: আমরা সর্বাধিক জোড়া অনুযায়ী দূরত্ব গণনা করি
ρকিছু দূরত্ব ফাংশন ব্যবহার করে আমাদের ডেটাসেটের মধ্যেd1. এর পরে আমরা শুধুমাত্র দুটি ক্লাস্টারকে একত্রিত করব যদি তাদের দূরত্ব <= হয়αρযেখানেα< 1। -
আমরা যা বলি: ধারাবাহিকতা
-
কেন? ধরা যাক আমরা আমাদের দূরত্ব ফাংশন থেকে পরিবর্তন করি
d1থেকেd2যেমন d2 অনুরূপ বিন্দুগুলিকে আরও অনুরূপ করে এবং ভিন্ন বিন্দুগুলিকে আরও ভিন্ন করে তোলে। আরো আনুষ্ঠানিকভাবে,d2একটিΓরূপান্তরd1. তারপর সংজ্ঞা দ্বারা, সর্বোচ্চ জোড়াওয়ালা দূরত্ব ব্যবহার করে প্রাপ্তd2থেকে বড় হবেρএবং ফলস্বরূপ ক্লাস্টারিং আউটপুট ব্যবহার করে প্রাপ্তd2এছাড়াও মূল ক্লাস্টারিং থেকে খুব আলাদা হবে।
সেন্ট্রোয়েড ভিত্তিক ক্লাস্টারিং সাধারণত ব্যবহৃত বোঝায় k- মানে এবং k-মিডিয়ান অ্যালগরিদম যেখানে আমরা একটি পূর্বনির্ধারিত দিয়ে শুরু করি k নির্বাচন করে ক্লাস্টার সংখ্যা k সেন্ট্রোয়েড হিসাবে ডেটাতে পয়েন্টগুলি এবং তারপর প্রতিটি পয়েন্টকে তাদের নিকটতম ক্লাস্টারে বরাদ্দ করা। অ্যালগরিদম পুনরাবৃত্তিমূলকভাবে k ক্লাস্টারের সেন্ট্রোয়েডগুলিকে অপ্টিমাইজ করে প্রতিটি ক্লাস্টারের গড় (বা মধ্যক) গণনা করে, এবং তারপর তাদের নিকটতম ক্লাস্টার সেন্ট্রোয়েডের উপর ভিত্তি করে বিন্দুগুলিকে পুনরায় বিতরণ করে। ক্লাস্টারগুলি স্থিতিশীল হয়ে গেলে অ্যালগরিদম সাধারণত বন্ধ হয়ে যায়।
এই অ্যালগরিদম সন্তুষ্ট না সমস্যা সঙ্গে ভোগা সমৃদ্ধি সম্পত্তি কারণ যত তাড়াতাড়ি আমরা ক্লাস্টার k সংখ্যা ঠিক করি, স্বয়ংক্রিয়ভাবে এটি আউটপুট হিসাবে সমস্ত সম্ভাব্য ক্লাস্টারিং অর্জনের সম্ভাবনাকে বাদ দেয়।
কাগজটি প্রমাণ করে যে এই অ্যালগরিদমগুলি সন্তুষ্ট করে না ধারাবাহিকতা পাশাপাশি সম্পত্তি। উদাহরণস্বরূপ, k=2-এর জন্য, k-মানে X এবং Y ক্লাস্টারের সাথে আসতে পারে। যাইহোক, যদি আমরা X এবং Y-এর মধ্যে বিন্দুর মধ্যে দূরত্ব কমিয়ে X এবং Y বিন্দুর মধ্যে দূরত্ব বাড়াই, তাহলে অ্যালগরিদম এর আউটপুট হিসাবে দুটি সম্পূর্ণ ভিন্ন ক্লাস্টার নিয়ে আসতে পারে। কাগজটিতে এই নির্দিষ্ট উদাহরণের জন্য একটি আনুষ্ঠানিক প্রমাণ রয়েছে যা k > 2 কেও সাধারণীকরণ করে।
এখন আপনি জানেন কেন ক্লাস্টারিং অ্যালগরিদম আপনাকে ত্যাগ স্বীকার করতে বাধ্য করে। এটি বাস্তবায়নের একটি ত্রুটি বা একটি সীমাবদ্ধতা নয় যা আমরা শেষ পর্যন্ত কাটিয়ে উঠব – এটি গাণিতিকভাবে অসম্ভব। প্রতিটি ক্লাস্টারিং অ্যালগরিদমকে অবশ্যই স্কেল-ইনভেরিয়েন্স, সমৃদ্ধি বা ধারাবাহিকতা ত্যাগ করতে হবে। এই মৌলিক বাণিজ্য বন্ধ থেকে কোন রেহাই নেই.
কিন্তু একবার আপনি বুঝতে পারবেন যে আপনি কী ছেড়ে দিচ্ছেন, আপনি এই সীমাবদ্ধতাটিকে আপনার জন্য কাজ করতে পারেন। প্রকৌশলীরা যেমন বিতরণ করা সিস্টেমে ধারাবাহিকতা এবং উপলব্ধতার মধ্যে বেছে নেন, আপনি কৌশলগতভাবে বেছে নিতে পারেন কোন ক্লাস্টারিং সম্পত্তি বলি দিতে হবে:
-
স্কেল নির্বিশেষে ডেটা পরিচালনা করার জন্য আপনার অ্যালগরিদম প্রয়োজন? আপনাকে ঐশ্বর্য ত্যাগ করতে হতে পারে।
-
কোন সম্ভাব্য গ্রুপিং আবিষ্কার করার নমনীয়তা চান? স্কেল-ইনভেরিয়েন্স হারাতে প্রস্তুত থাকুন।
-
ক্লাস্টার নিদর্শন আরো উচ্চারিত হয়ে স্থিতিশীল থাকার ফলাফল প্রয়োজন? আপনি সম্ভবত ঐশ্বর্য ত্যাগ করব.
এই সীমাবদ্ধতাগুলির সাথে লড়াই করার পরিবর্তে, এগুলিকে গাইড হিসাবে ব্যবহার করুন। নিজেকে জিজ্ঞাসা করুন:
-
আপনার নির্দিষ্ট ব্যবহারের ক্ষেত্রে কোন সম্পত্তি সবচেয়ে গুরুত্বপূর্ণ?
-
কোন ট্রেড-অফ আপনার আবেদন সহ্য করতে পারে?
-
এই অন্তর্নিহিত সীমাবদ্ধতাগুলি জেনে আপনি কীভাবে আপনার সিস্টেমটি ডিজাইন করতে পারেন?
ক্লেইনবার্গের উপপাদ্য বোঝা আপনাকে কেবল একজন ভাল তাত্ত্বিক করে না – এটি আপনাকে আরও কার্যকর প্রকৌশলী করে তোলে। কারণ বাস্তব জগতে, সাফল্য নিখুঁত ক্লাস্টারিং অ্যালগরিদম খোঁজার বিষয়ে নয় (এটি বিদ্যমান নেই)। এটি আপনার নির্দিষ্ট প্রয়োজনের জন্য সঠিক ত্যাগ বেছে নেওয়ার বিষয়ে।
আপনি যদি আমার কাজকে আকর্ষণীয় এবং মূল্যবান মনে করেন, আপনি একটি অর্থপ্রদানের সদস্যতা বেছে নিয়ে আমাকে সমর্থন করতে পারেন (এটি $6 মাসিক/$60 বার্ষিক)। বোনাস হিসেবে আপনি মাসিক লাইভ সেশন এবং অতীতের সমস্ত রেকর্ডিংগুলিতে অ্যাক্সেস পাবেন।
অনেক লোক ব্যর্থ অর্থপ্রদানের রিপোর্ট করে, বা পুনরাবৃত্ত সদস্যতা চায় না। তার জন্য আমিও ক মেকফি পাতা কিনুন. যেখানে আপনি আমাকে কফি কিনতে পারেন বা সদস্য হতে পারেন। আমি আপনাকে এখানে সমতুল্য সময়ের জন্য একটি প্রদত্ত সাবস্ক্রিপশনে আপগ্রেড করব।
আমার একটি GitHub স্পনসর পৃষ্ঠাও আছে। আপনি এখানে একটি স্পনসরশিপ ব্যাজ পাবেন, এবং একটি পরিপূরক অর্থপ্রদানের সদস্যতাও পাবেন।
