কল্পনা করো, তোমার টেবিলে হাজার হাজার এলোমেলো খেলনা ছড়িয়ে আছে। তুমি চোখ মুদে হাত বুলিয়ে বললে, “এগুলোকে রঙ অনুযায়ী গ্রুপ করে দাও!” — আর হুড়মুড় করে সব লাল একপাশে, নীল আরেকপাশে চলে গেল! এই জাদু করেই K-Means Clustering! নেটফ্লিক্স তোমার পছন্দের মুভি ঠিকনা করে, অ্যামাজন তোমাকে “এটা কিনলে এটাও কিনো” বলে — সবার পেছনে এই অ্যালগরিদমের খেলা।
১. Clustering কী জিনিস? (সহজ করে বলি)
Clustering মানে এলোমেলো ডেটাকে তাদের মিলের ভিত্তিতে দলে ভাগ করা।
মেশিন লার্নিংয়ের ভাষায়: এটি Unsupervised Learning-এর একটি পদ্ধতি।
Supervised Learning: যেখানে টিচার বা লেবেল থাকে (যেমন: ইনপুট = আপেল ছবি, আউটপুট = “আপেল”)।
Unsupervised Learning: এখানে কোনো লেবেল নেই। ডেটাগুলো এলোমেলো ছড়িয়ে থাকে। অ্যালগরিদমকে নিজে থেকেই প্যাটার্ন খুঁজে বের করতে হয়।
বাস্তব উদাহরণ :
কাস্টমার গ্রুপিং: তোমার দোকানে কেউ সোনার গয়না কিনে, কেউ চিপস-বিস্কুট। K-Means বলবে, “এই ১০ জন ‘লাক্সারি ক্রেজি’, ওই ৫০ জন ‘বাজেট হান্টার’!”
নিউজ সর্টিং: হাজার নিউজ হেডলাইন মিশে আছে? এটা স্পোর্টস, ওটা পলিটিক্সে ভাগ করে দেয়।
ইমেজ ম্যাজিক: ডাক্তারের ছবিতে টিউমারটা আলাদা করে বের করে!
Classification-এর সাথে পার্থক্য? Classification-এ আগে থেকে বলা “এটা আপেল বা কমলা”। Clustering-এ বলো না, “দেখি কী কী গ্রুপ বানায়!”
Clustering vs Classification:
Classification: আগে থেকেই জানি কী কী ক্লাস আছে (যেমন: স্প্যাম বা নট-স্প্যাম)।
Clustering: আমরা জানি না কয়টি গ্রুপ হবে বা তাদের নাম কী।
২. Types of Clustering
Clustering অ্যালগরিদম অনেক ধরনের হয়, তবে প্রধান ৩টি হলো:
১. K-Means Clustering: এটি কেন্দ্রবিন্দু (Centroid) নির্ভর। সবচেয়ে জনপ্রিয় এবং দ্রুত।
২. Hierarchical Clustering: এটি গাছের মতো শাখা-প্রশাখা (Dendrogram) তৈরি করে গ্রুপিং করে।
৩. DBSCAN: এটি ডেটার ঘনত্ব (Density) এর ওপর ভিত্তি করে ক্লাস্টার তৈরি করে (যেকোনো শেইপের জন্য ভালো)।
৩. K-Means কেন রাজা?
Clustering-এর অনেক ধরন, কিন্তু K-Means সবচেয়ে জনপ্রিয় কারণ:
সহজ, দ্রুত, বিশাল ডেটাতেও চলে।
অন্যরা: Hierarchical (গাছের মতো ধীর), DBSCAN (ঘনত্ব দেখে, শেপ যাই হোক)।
K-Means তোমার ডেটাকে Kটা দলে ভাগ করে, প্রতি দলের মাঝখানে একটা ‘লিডার’ (Centroid) রাখে।
৪. Mathematical Foundation of K-Means
Dataset Representation
ধরো, আমাদের n-টা ডেটা পয়েন্ট আছে:
X = {x₁, x₂, …, xₙ}
প্রতিটি xᵢ একটা ভেক্টর। যদি 2D হয় (বয়স, আয়):
x₁ = (25, 50000), x₂ = (30, 75000), ইত্যাদি।
Choosing K
আগেই ঠিক করো কয়টা গ্রুপ চাও: K = 3 (ধরি ৩টা ক্লাস্টার)।
সঠিক K খুঁজতে Elbow Method ব্যবহার করব পরে।
Centroid Definition
প্রতি ক্লাস্টারের একটা “লিডার” থাকে — Centroid (μ):
C = {μ₁, μ₂, …, μₖ}
উদাহরণ: μ₁ = (28, 60000) — প্রথম গ্রুপের “গড় মানুষ”।
Distance Calculation
Euclidean Distance (পিথাগোরাস সূত্র):
d(x, μ) = √[ (x₁ — μ₁)² + (x₂ — μ₂)² + … + (x_d — μ_d)² ]
কিন্তু K-Means-এ সাধারণত Squared Distance ব্যবহার করে (√ বাদ দেয়):
||x — μ||² = (x₁ — μ₁)² + (x₂ — μ₂)² + …
উদাহরণ: x=(3,4), μ=(1,1)
||x — μ||² = (3–1)² + (4–1)² = 4 + 9 = 13
Cluster Assignment Step
প্রতিটি xᵢ কোন গ্রুপে যাবে?
যে μⱼ এর কাছে সবচেয়ে কম দূরত্ব:
||xᵢ — μⱼ||² ≤ ||xᵢ — μₖ||² (সব k ≠ j এর জন্য)
অর্থাৎ: xᵢ যাবে সবচেয়ে কাছের centroid-এর গ্রুপে।
Centroid Update Step
সবাই গ্রুপে জয়েন করার পর, নতুন লিডার = গ্রুপের গড়:
μⱼ = (1/|Cⱼ|) × Σ{xᵢ | xᵢ ∈ Cⱼ}
যেখানে:
|Cⱼ| = j-তম গ্রুপে মোট সদস্য সংখ্যা
Σxᵢ = সেই গ্রুপের সব পয়েন্টের যোগফল
উদাহরণ: গ্রুপে ৩টা পয়েন্ট — (2,3), (4,5), (1,1)
μ = [(2+4+1)/3, (3+5+1)/3] = (7/3, 9/3) = (2.33, 3)
Objective Function
K-Means এর মেইন গোল: WCSS কমানো
J = Σⱼ₌₁ᴷ Σ₍ₓᵢ∈𝒞ⱼ₎ ||xᵢ — μⱼ||²
Intuition: প্রতিটি পয়েন্ট তার নিজ গ্রুপের centroid-এর
যত কাছাকাছি থাকবে, J তত ছোট হবে = ক্লাস্টারিং তত ভালো!
J কমতে কমতে স্থির হলে → Algorithm Stop!
Algorithm Flow
র্যান্ডম K-টা centroid বেছে নাও (μ₁, μ₂, …, μₖ)
WHILE (J পরিবর্তন হচ্ছে বা max iteration < 100):
a. ASSIGNMENT: প্রতিটি xᵢ → সবচেয়ে কাছের μⱼ
b. UPDATE: নতুন μⱼ = গ্রুপ Cⱼ-এর গড়
c. J calculate করো
- J স্থির হলে STOP → Final clusters + centroids
Example & Implementation:
Formula:
Press enter or click to view image in full size
Iteration ১: Initial Centroids
𝜇1=(1,1) 𝜇2=(2,1)
**
**
Clusters: C1: {A}, C2: {B,C,D}
Update Centroids:
New m1: যেহেতু শুধু A আছে, তাই (1, 1)।
New m2: B, C, D এর গড়।
x-avg: (2+4+5)/3 = 3.67
y-avg: (1+3+4)/3 = 2.67
New m2 = (3.67, 2.67)
WCSS: 26.0
Iteration ২: Continue
নতুন 𝜇1=(1,1)), 𝜇2=(3.67,2.67)
Distances:
Clusters: C1: {A,B}, C2: {C,D}
Update Centroids:
𝜇1=(1+22,1+12)=(1.5,1)
𝜇2=(4+52,3+42)=(4.5,3.5)
WCSS: 4.78 (আগের থেকে অনেক কম!)
Iteration ৩: Convergence
নতুন centroids দিয়ে assign করলে clusters একই থাকে। Centroids আর বড় পরিবর্তন নেই, WCSS ~4.5-এ স্থিতিশীল। Stop!
Pseudocode
1. Initialize μ = random K points from X
2. While not converged:
a. For each x_i in X:
cluster[i] = argmin_j ||x_i — μ_j||²
b. For j=1 to K:
μ_j = mean({x_i | cluster[i]=j})
c. If centroids unchanged or J < epsilon: break
3. Return clusters, μ
এটা লুপ চালিয়ে WCSS minimize করে।
৫. Scratch Implementation
Output: Final centroids: [[1.5 1. ] [4.5 3.5]], Labels: [0 0 1 1], WCSS: ~4.5।
৬. সঠিক K কীভাবে খুঁজব? Elbow Method! 🏃♂️
K=1 থেকে 10 চালিয়ে WCSS প্লট করো। গ্রাফটা কনুইয়ের মতো বাঁক নেবে — সেখানেই সেরা K!
৭. ভালো-খারাপ দিক + কখন ফেল করে?
✅ সুপারহিরো পাওয়ার: দ্রুত, সহজ, বিশাল ডেটায় চলে।
❌ দুর্বলতা:
- আউটলায়ারে টলে যায়,
- শুরুর লিডার ভুল হলে খারাপ রেজাল্ট,
- শুধু গোল-গোল ডেটায় ভালো। (রিং-আকারে ফেল করে!)
Implementation of K-means Clustering
🔹 সেকশন ১: লাইব্রেরি ইমপোর্ট করা
K-Means এর জন্য আমাদের ডেটা হ্যান্ডলিং (Pandas), ম্যাথমেটিক্যাল ক্যালকুলেশন (NumPy), ভিজ্যুয়ালাইজেশন (Matplotlib, Seaborn) এবং মেশিন লার্নিং টুলস (Scikit-learn) প্রয়োজন।
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score
🔹 সেকশন ২ ও ৩: ডেটাসেট লোড ও এক্সপ্লোর করা
এখানে আমরা গ্রাহকদের বার্ষিক আয় এবং খরচ করার স্কোর (Spending Score) ব্যবহার করবো।
# ডেটা লোড করা
url = “https://raw.githubusercontent.com/mwaskom/seaborn-data/master/mall_customers.csv"
df = pd.read_csv(url)
# ডেটা দেখা
print(df.head())
print(df.shape)
print(df.columns)
🔹 সেকশন ৪ ও ৫: ফিচার সিলেকশন ও স্কেলিং
K-Means অ্যালগরিদম ইউক্লিডীয় দূরত্বের (Euclidean distance) ওপর ভিত্তি করে কাজ করে। যদি একটি ফিচারের মান অনেক বড় (যেমন: আয়) এবং অন্যটির মান ছোট হয়, তবে বড় মানটি ফলাফলকে প্রভাবিত করবে। তাই StandardScaler দিয়ে সব ফিচারকে একই স্কেলে আনা জরুরি।
🔹** সেকশন ৬: Elbow Method (সঠিক ‘k’ খুঁজে বের করা)**
আমরা জানি না কয়টি ক্লাস্টার করলে সবচেয়ে ভালো হবে। তাই আমরা ১ থেকে ১০ পর্যন্ত ক্লাস্টার সংখ্যা দিয়ে পরীক্ষা করবো এবং Inertia (ক্লাস্টারের ভেতরের দূরত্বের যোগফল) বের করবো।
inertia = []``
K_range = range(1, 11)
for k in K_range:
kmeans = KMeans(n_clusters=k, random_state=42, n_init=10)
kmeans.fit(X_scaled)
inertia.append(kmeans.inertia_)
# প্লট করা
plt.figure(figsize=(8, 5))
plt.plot(K_range, inertia, marker=’o’, linestyle=’ — ‘)
plt.xlabel(‘Number of Clusters (k)’)
plt.ylabel(‘Inertia’)
plt.title(‘Elbow Method to find Optimal k’)
plt.show()
🔹 সেকশন ৭ ও ৮: মডেল ট্রেইনিং ও ভিজ্যুয়ালাইজেশন
সাধারণত এলবো প্লটে যেখানে গ্রাফটি হঠাৎ বাঁক নেয় (কনুইয়ের মতো), সেটিই সেরা k। ধরুন আমাদের ক্ষেত্রে এটি ৫।
# k=5 ধরে মডেল তৈরি
kmeans = KMeans(n_clusters=5, random_state=42, n_init=10)
clusters = kmeans.fit_predict(X_scaled)
# অরিজিনাল ডেটাফ্রেমে ক্লাস্টার লেবেল যোগ করা
df[‘Cluster’] = clusters
# ভিজ্যুয়ালাইজেশন
plt.figure(figsize=(10, 6))
sns.scatterplot(x=’annual_income’, y=’spending_score’, hue=’Cluster’, data=df, palette=’viridis’, s=100)
plt.title(‘Customer Segments (K-Means)’)
plt.show()
🔹 সেকশন ৯: এভালুয়েশন (Silhouette Score)
সিলুয়েট স্কোর বলে দেয় ক্লাস্টারগুলো একে অপরের থেকে কতটা আলাদা। এর মান ১ এর যত কাছে হবে, ক্লাস্টারিং তত ভালো হয়েছে।
score = silhouette_score(X_scaled, clusters)
print(f”Silhouette Score: {score:.2f}”)
মন্তব্য: সাধারণত ০.৫ এর উপরে স্কোর থাকলে সেটি ভালো ক্লাস্টারিং হিসেবে ধরা হয়।
🔹 সেকশন ১০: Reflection Questions
১. কেন স্কেলিং বাধ্যতামূলক?
K-Means দূরত্বের ওপর নির্ভর করে। স্কেলিং না করলে যে ফিচারের মান বড় (যেমন ১,০০,০০০ টাকা আয়), সেটি ছোট মানের ফিচারের (যেমন ১-১০০ স্কোর) চেয়ে বেশি প্রাধান্য পাবে, যা ভুল ফলাফল দেবে।
২. k এর মান খুব বেশি হলে কী হবে?
যদি k খুব বড় হয় (যেমন ডেটা পয়েন্টের সমান), তবে প্রতিটি পয়েন্ট নিজেই একটি ক্লাস্টার হয়ে যাবে। একে Overfitting বলে। এতে ডেটার আসল প্যাটার্ন বোঝা যায় না।
৩. K-Means কি সব ডেটাসেটের জন্য উপযোগী?
না। এটি কেবল গোলাকার (spherical) ক্লাস্টার এবং সমান ঘনত্বের ডেটার জন্য ভালো কাজ করে। যদি ডেটা খুব জটিল বা আঁকাবাঁকা (Non-linear) হয়, তবে K-Means ভালো ফলাফল দেয় না।
Top comments (0)