ক্লাস্টারিং অ্যালগরিদমগুলোর মধ্যে সবচেয়ে সহজ এবং সবচেয়ে পপুলার হল K-means clustering algorithm. এই আর্টিকালে যা থাকছে –
- K-means Clustering কি?
- K-means Clustering এর অ্যালগরিদম স্টেপ বাই স্টেপ
- K-means Clustering এর নিউমেরিক সল্ভ
- K-means Clustering এর লিমিটেশন
K-means Clustering কি?: K-means clustering algorithm হল একটা unsupervised learning algorithm। এইটা একটা partitioning algorithm, ডাটাসেটকে ‘k’ পার্টিশনে ভাগ করে। এই পার্টিশনগুলোই ক্লাস্টার হয়। ক্লাস্টার গঠনের সময় কোন একটা পার্টিশনিং ক্রাইটেরিয়াকে অপটিমাইজ করা হয় যেন একই ক্লাস্টারের মধ্যে অবজেক্টগুলোর মধ্যে ‘similarity’ বেশি থাকে এবং ভিন্ন ভিন্ন ক্লাস্টারের মধ্যে অবজেক্টগুলোর মধ্যে ‘dissimilarity’ বেশি থাকে। K-means এর ক্ষেত্রে এই পার্টিশনিং ক্রাইটেরিয়া হল Euclidean distance function।
ধরি দুইটা বিন্দু i এবং j, এদের p নিউমেরিক অ্যাট্রিবিউট আছে।
i = (xi1, xi2, xi3,…., xip) , j = (xj1, xj2, xj3,…., xjp), এদের মধ্যে ইউক্লিডিন ডিসটেন্স হবে –
যাদের ইউক্লিডিন ডিসটেন্স কম, তারা মিলে একটা ক্লাস্টার গঠন করবে। K-means clustering algorithm-এ ক্লাস্টারের সেন্টারকে centroid বলা হয়। ক্লাস্টারের মধ্যে সব অবজেক্টগুলোর mean ক্যালকুলেট করে এই সেন্ট্রয়েড বের করা হয়। এখন তাহলে K-means নিয়ে একটু ডিটেইলে দেখা যাক।
K-means Clustering এর অ্যালগরিদম স্টেপ বাই স্টেপ: ধরি একটি ডাটাসেট D যেইখানে n সংখ্যক ডাটা আছে। এদেরকে k ক্লাস্টারে যেইভাবে ভাগ করতে পারি –
১। র্যান্ডমলি D থেকে kটা পয়েন্ট সিলেক্ট করে তাদেরকে ইনিশিয়াল সেন্ট্রয়েড ধরে নেওয়া হয়।
২। প্রত্যেক অবজেক্ট থেকে সেন্ট্রয়েডের দুরুত্ব বের করতে হবে। যেই সেন্ট্রয়েডের সাথে দুরুত্ব সবচেয়ে কম, আমরা অবজেক্টটিকে ঐ ক্লাস্টারে অ্যাসাইন করব।
৩। প্রত্যেক ক্লাস্টারের মিন ক্যালকুলেট করে সেন্ট্রয়েড আপডেট করতে হবে।
৪। আপডেট করার পর যদি নতুন সেন্ট্রয়েড পাই, তাহলে (৩), (৪) রিপিট করতে হবে। যদি একই সেন্ট্রয়েড থাকে তাহলে এইটাই হবে আমাদের ফাইনাল সেন্ট্রয়েড এবং ক্লাস্টার।
এই কাজটা আরেকটু ভাল করে বুঝার চেষ্টা করি আমরা-
এখন আমাদের কাছে একটা D ডাটাসেট আছে যেইখানে 8 টা ডাটাপয়েন্ট আছে। এইটাকে 3 টা ক্লাস্টারে ভাগ করতে হবে।
প্রথমে র্যান্ডমলি 3 টা পয়েন্টকে সেন্ট্রয়েড ধরে নিলাম।
এরপর প্রত্যেক অবজেক্ট থেকে সেন্ট্রয়েডের দুরুত্ব বের করব আমরা। দুরুত্বের ভিত্তিতে প্রত্যেক অবজেক্টের ক্লাস্টার অ্যাসাইন করা হবে। তো একটা পয়েন্ট নেই, এই পয়েন্ট থেকে সবগুলা সেন্ট্রয়েডের দুরুত্ব বের করি।
যেই সেন্ট্রয়েডের দুরুত্ব সবচেয়ে কম হবে, এই ডাটাপয়েন্টকে ঐ ক্লাস্টারে অ্যাসাইন করে দিব। এইভাবে সবগুলো ডাটা পয়েন্টকে এইভাবে একটা ক্লাস্টারে অ্যাসাইন করে দিব। অ্যাসাইন করার পর আমরা এমন 3 টা ক্লাস্টার পাই।
এখন এই ক্লাস্টারগুলোর মিন বের করে সেন্ট্রয়েড আপডেট করে দিব।
প্রত্যেক ডাটা পয়েন্টকে আবার রি-অ্যাসাইন করতে হবে।
এই একই প্রসেসে সেন্ট্রয়েড আপডেট এবং প্রত্যেক ডাটা পয়েন্টকে রি-অ্যাসাইন করতে হবে যতক্ষণ পর্যন্ত না আমাদের টার্মিনেশন ক্রাইটেরিয়া পূরণ করে। সাধারণত এই ক্রাইটেরিয়া সেট করা হয় যে আপডেটের পর সেন্ট্রয়েড একই থেকে যায়। এছাড়াও আমরা কয়েকটা নির্দিষ্ট ইটারেশনের পর টার্মিনেট করে ডিতে পারি। সর্বশেষ আমরা তাহলে এই 3 টা ক্লাস্টার পাই।
এইটাই আমাদের ফাইনাল রেজাল্ট, এই 3 টা ক্লাস্টার।
K-means Clustering এর নিউমেরিক সল্ভ: এখন একটা নিউমেরিক উদাহরণ দিয়ে দেখা যাক ব্যাপারটা। ধরি ডাটাসেটে 8 টা ডাটাপয়েন্ট দেওয়া আছে –
A1(2,10), A2(2,5), A3(8,4), B1(5,8), B2(7,5), B3(6,4), C1(1,2), C2(4,9)
দেওয়া আছে আমাদের ইনিশিয়াল সেন্ট্রয়েড A1, B1, C1
1st iteration:
প্রত্যেক পয়েন্ট থেকে সেন্ট্রয়েডগুলোর ইউক্লিডিন দুরুত্ব বের করতে হবে। এখন দুইটা 2D পয়েন্টের মধ্যে ইউক্লিডিন ডিসটেন্স হবে –
| X1 = (2, 10) | X2 = (5, 8) | X3 = (1, 2) | |
|---|---|---|---|
| A1 | 0 | 3.60 | 8.06 |
| A2 | 5.00 | 4.24 | 3.16 |
| A3 | 8.40 | 5.00 | 7.28 |
| B1 | 3.60 | 0 | 7.21 |
| B2 | 7.07 | 3.60 | 6.70 |
| B3 | 7.21 | 4.12 | 5.38 |
| C1 | 8.06 | 7.21 | 0 |
| C2 | 2.23 | 1.41 | 7.61 |
এখন প্রত্যেক পয়েন্টকে একটা ক্লাস্টারে অ্যাসাইন করব। এইখানে A1 নিজে একটা সেন্ট্রয়েড, এইটা নিয়ে Cluster 1 হল। A2 থেকে X3 এর দুরুত্ব সবচেয়ে কম, তাইলে A2 কে Cluster 3 তে অ্যাসাইন করা হল। A3 থেকে X2 এর দুরুত্ব কম, তাই A3 কে Cluster 2 তে অ্যাসাইন করা হল। এইভাবে সব পয়েন্টকে অ্যাসাইন করার পর আমরা পাই-
Cluster 1 = { A1 }
Cluster 2 = { A3, B1, B2, B3, C2 }
Cluster 3 = { A2, C1 }
সেন্ট্রয়েড আপডেট: প্রত্যেক ক্লাস্টারের মিন বের করে নতুন সেন্ট্রয়েড আপডেট করতে হবে।
X1 = (2, 10)
X2 = ( 8+5+7+6+4/5, 4+8+5+4+9/5 ) = (6,6)
X3 = ( 2+1/2, 5+2/2 ) = (1.5, 3.5)
2nd iteration:
এখন আপডেটেড সেন্ট্রয়েড দিয়ে আবার ইউক্লিডিন দুরুত্ব বের করে পয়েন্টগুলোকে ক্লাস্টারে অ্যাসাইন করতে হবে।
| X1 = (2, 10) | X2 = (6, 6) | X3 = (1.5, 3.5) | |
|---|---|---|---|
| A1 | 0 | 5.65 | 6.51 |
| A2 | 5.00 | 4.12 | 1.58 |
| A3 | 8.48 | 2.82 | 6.51 |
| B1 | 3.60 | 2.23 | 5.7 |
| B2 | 7.07 | 1.41 | 5.70 |
| B3 | 7.21 | 2.00 | 4.52 |
| C1 | 8.06 | 6.40 | 1.58 |
| C2 | 2.23 | 3.60 | 6.04 |
Cluster 1 = { A1, C2 }
Cluster 2 = { A3, B1, B2, B3 }
Cluster 3 = { A2, C1 }
সেন্ট্রয়েড আপডেট:
X1 = (3, 9.5)
X2 = (6.5, 5.25)
X3 = (1.5, 3.5)
3rd iteration:
| X1 = (3, 9.5) | X2 = (6.5, 5.25) | X3 = (1.5, 3.5) | |
|---|---|---|---|
| A1 | 1.11 | 6.54 | 6.51 |
| A2 | 4.60 | 4.50 | 1.58 |
| A3 | 7.43 | 1.95 | 6.51 |
| B1 | 2.50 | 3.13 | 5.7 |
| B2 | 6.02 | 0.55 | 5.70 |
| B3 | 6.26 | 1.34 | 4.52 |
| C1 | 7.76 | 6.38 | 1.58 |
| C2 | 1.11 | 4.5 | 6.04 |
Cluster 1 = { A1, B1, C2 }
Cluster 2 = { A3, B2, B3 }
Cluster 3 = { A2, C1 }
সেন্ট্রয়েড আপডেট:
X1 = (3.67, 9)
X2 = (7, 4.33)
X3 = (1.5, 3.5)
4th iteration:
| X1 = (3.67, 9) | X2 = (7, 4.33) | X3 = (1.5, 3.5) | |
|---|---|---|---|
| A1 | 1.94 | 7.55 | 6.51 |
| A2 | 4.33 | 5.04 | 1.58 |
| A3 | 6.61 | 1.05 | 6.51 |
| B1 | 1.66 | 4.17 | 5.70 |
| B2 | 5.20 | 0.67 | 5.70 |
| B3 | 5.51 | 1.05 | 4.52 |
| C1 | 7.49 | 6.43 | 1.58 |
| C2 | 0.33 | 5.55 | 6.04 |
Cluster 1 = { A1, B1, C2 }
Cluster 2 = { A3, B2, B3 }
Cluster 3 = { A2, C1 }
সেন্ট্রয়েড আপডেট:
X1 = (3.67, 9)
X2 = (7, 4.33)
X3 = (1.5, 3.5)
খেয়াল করলে দেখা যাচ্ছে যে 4th iteration এর পর সেন্ট্রয়েডের কোন পরিবর্তন হয়নাই। তাহলে আমরা এইখানেই টার্মিনেট করতে পারি। এইটাই আমাদের ফাইনাল ক্লাস্টার।
K-means Clustering এর লিমিটেশন:
১। সহজে নয়েজ এবং আউটলায়ার দ্বারা প্রভাবিত হয়। K-means ডাটাপয়েন্টগুলোর মিন ক্যালকুলেট করে সেন্ট্রয়েড পাওয়া যায়। তাই যদি কোন নয়েজ বা আউটলায়ার উপস্থিত থাকে ডাটাসেটে, তখন সেইগুলোসহ মিন ক্যালকুলেট হয়ে যায়। ফলে দেখা যায় যে ভুল সেন্ট্রয়েড বের হয় এবং আল্টিমেটলি ভুল ক্লাস্টার তৈরি হয়।
উপরের যে উদাহরণ নিয়ে আলোচনা হল, সেইখানে যদি আউটলায়ার থাকলে উপরের চিত্রের মত হবে। সেন্ট্রয়েড সরে মাঝে চলে আসছে এবং আউটলায়ার সহ ক্লাস্টার গঠন করে।
২। আগে থেকে k (ক্লাস্টার সংখ্যা) এর ভ্যালু বলে দিতে হয়। সবসময় তো আমরা নাও জানতে পারি যে আমাদের কয়টা ক্লাস্টার লাগবে। আমরা চাইতে পারি যে অ্যালগোরিদম নিজ থেকে ডিটেক্ট করুক যে কয়টা ক্লাস্টার হবে।
৩। ইনিশিয়ালি আমরা কোন ডাটাপয়েন্টগুলোকে সেন্ট্রয়েড ধরছি, সেইটার উপর অনেকটা নির্ভর করে আমরা কেমন ক্লাস্টার পাব। কারণ মিন ক্যালকুলেট করেই করেই তো আমরা আগাই। একেক সেট অফ পয়েন্ট এর জন্য একেক মিন পাব, অর্থাৎ ভিন্ন ভিন্ন সেন্ট্রয়েড পাব। এইভাবে ভিন্ন ভিন্ন ক্লাস্টার পাব।
৪। শুধু স্ফেরিকাল আকৃতির ক্লাস্টার করতে পারে। এর বাইরে ভিন্ন আকৃতির ক্লাস্টার ধরতে পারেনা।
৫। ডাটা যদি কন্টিনুয়াস n-ডাইমেনশন স্পেসে ডিফাইন করা যায়, তাহলেই k-means ব্যাবহার করা যায়। উপরে যে উদাহরণ দেওয়া হয়েছে তা 2D স্পেসে ডিফাইন করা এবং এদের মিন ক্যালকুলেট করা যায়। ক্যাটাগরিকাল ডাটা হলে k-means এর পরিবর্তে k-modes মেথড ব্যাবহার করতে হবে।
আরও পড়তে চাইলে:
- https://towardsdatascience.com/understanding-k-means-clustering-in-machine-learning-6a6e67336aa1
- https://towardsdatascience.com/k-means-clustering-algorithm-applications-evaluation-methods-and-drawbacks-aa03e644b48a
- https://www.analyticsvidhya.com/blog/2019/08/comprehensive-guide-k-means-clustering/
- https://www.geeksforgeeks.org/k-means-clustering-introduction/
- https://blogs.oracle.com/ai-and-datascience/post/introduction-to-k-means-clustering
- https://www.javatpoint.com/k-means-clustering-algorithm-in-machine-learning
- https://sites.google.com/site/dataclusteringalgorithms/k-means-clustering-algorithm