ক্লাস্টারিং টেকনিকস: K-means ক্লাস্টারিং, Mean Shift সেগমেন্টেশন

ক্লাস্টারিং টেকনিকস: K-means ক্লাস্টারিং, Mean Shift সেগমেন্টেশন

ক্লাস্টারিং একটি অতি গুরুত্বপূর্ণ অনসুপারভাইজড লার্নিং (unsupervised learning) টেকনিক যা বিভিন্ন ডেটা পয়েন্ট বা অবজেক্টকে একই শ্রেণীতে (cluster) ভাগ করতে ব্যবহৃত হয়। এটি ইমেজ সেগমেন্টেশন, ডেটা মাইনিং, প্যাটার্ন রিকগনিশন, এবং বিভিন্ন বৈজ্ঞানিক গবেষণায় ব্যবহার করা হয়। ক্লাস্টারিং টেকনিকের মাধ্যমে ডেটার মধ্যে ছড়িয়ে থাকা প্যাটার্ন এবং সম্পর্কগুলি খুঁজে বের করা যায়।

এখানে দুটি জনপ্রিয় ক্লাস্টারিং টেকনিক নিয়ে আলোচনা করা হচ্ছে:

1. K-means ক্লাস্টারিং (K-means Clustering)
2. Mean Shift সেগমেন্টেশন (Mean Shift Segmentation)

১. K-means ক্লাস্টারিং (K-means Clustering)

K-means ক্লাস্টারিং হল একটি জনপ্রিয় ক্লাস্টারিং অ্যালগরিদম যা ডেটা পয়েন্টগুলিকে Kটি গ্রুপে ভাগ করে, যেখানে প্রতিটি গ্রুপের মধ্যে পয়েন্টগুলির মধ্যে সর্বনিম্ন ভ্যারিয়েশন থাকে। এটি একটি অ্যাডভান্সড অনসুপারভাইজড মেথড, যেখানে আপনাকে প্রথমে ক্লাস্টারের সংখ্যা K নির্ধারণ করতে হয়।

K-means ক্লাস্টারিং-এর পদক্ষেপ:

1. Kটি সেন্ট্রয়েড বেছে নিন: প্রথমে Kটি সেন্ট্রয়েড (centroids) র‍্যান্ডমলি বাছাই করা হয়।
2. পয়েন্টগুলোকে সেন্ট্রয়েডের সাথে অ্যাসাইন করুন: প্রতিটি ডেটা পয়েন্টকে সেন্ট্রয়েডের সাথে কাছাকাছি পয়েন্টের ক্লাস্টারে অ্যাসাইন করা হয়।
3. সেন্ট্রয়েড আপডেট করুন: প্রতিটি ক্লাস্টারের নতুন সেন্ট্রয়েড হিসাব করা হয়, যা ক্লাস্টারের সব পয়েন্টের গড় অবস্থান।
4. পুনরায় পয়েন্ট অ্যাসাইন এবং সেন্ট্রয়েড আপডেট করুন: এই পদক্ষেপটি পুনরাবৃত্তি করা হয় যতক্ষণ না ক্লাস্টার পরিবর্তন না হয় বা কনভার্জ না হয়।

K-means ক্লাস্টারিং ফর্মুলা:

1. ক্লাস্টারগুলির জন্য ক্যালকুলেট করা হয়:
   \[
   \text{Centroid}k = \frac{1}{N_k} \sum{i=1}^{N_k} X_i
   \]
   যেখানে \( N_k \) হল ক্লাস্টার \( k \) এর মধ্যে ডেটা পয়েন্টের সংখ্যা এবং \( X_i \) হল সেই পয়েন্টের অবস্থান।
2. পুনরায় অ্যাসাইনমেন্ট:
   \[
   \text{Distance}(X_i, C_k) = \sqrt{\sum_{j=1}^{d} (X_{ij} - C_{kj})^2}
   \]
   যেখানে \( X_i \) হল ডেটা পয়েন্ট এবং \( C_k \) হল ক্লাস্টার সেন্ট্রয়েড।

Java কোড উদাহরণ (K-means ক্লাস্টারিং):

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class KMeans {
    static class Point {
        double x, y;
        Point(double x, double y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) {
        List<Point> dataPoints = new ArrayList<>();
        // ডেটা পয়েন্ট তৈরি করুন
        dataPoints.add(new Point(1, 2));
        dataPoints.add(new Point(2, 3));
        dataPoints.add(new Point(3, 4));
        // আরো ডেটা পয়েন্ট যোগ করুন
        
        int K = 2;  // ক্লাস্টারের সংখ্যা
        List<Point> centroids = initializeCentroids(dataPoints, K);
        
        List<List<Point>> clusters = new ArrayList<>();
        for (int i = 0; i < K; i++) {
            clusters.add(new ArrayList<>());
        }

        boolean changed;
        do {
            changed = false;
            // পয়েন্টগুলোকে ক্লাস্টারে অ্যাসাইন করা
            for (Point p : dataPoints) {
                int closestCluster = getClosestCentroid(p, centroids);
                clusters.get(closestCluster).add(p);
            }

            // সেন্ট্রয়েড আপডেট করা
            for (int i = 0; i < K; i++) {
                Point newCentroid = computeCentroid(clusters.get(i));
                if (!newCentroid.equals(centroids.get(i))) {
                    centroids.set(i, newCentroid);
                    changed = true;
                }
            }
        } while (changed);
        
        // ক্লাস্টার প্রিন্ট করুন
        System.out.println("Clustering Complete!");
    }

    // সেন্ট্রয়েড গণনা
    public static Point computeCentroid(List<Point> cluster) {
        double sumX = 0, sumY = 0;
        for (Point p : cluster) {
            sumX += p.x;
            sumY += p.y;
        }
        return new Point(sumX / cluster.size(), sumY / cluster.size());
    }

    // সর্বাধিক কাছের সেন্ট্রয়েড পেতে
    public static int getClosestCentroid(Point p, List<Point> centroids) {
        int closest = 0;
        double minDist = Double.MAX_VALUE;
        for (int i = 0; i < centroids.size(); i++) {
            double dist = Math.sqrt(Math.pow(p.x - centroids.get(i).x, 2) + Math.pow(p.y - centroids.get(i).y, 2));
            if (dist < minDist) {
                closest = i;
                minDist = dist;
            }
        }
        return closest;
    }

    // র্যান্ডম সেন্ট্রয়েড নির্বাচন
    public static List<Point> initializeCentroids(List<Point> dataPoints, int K) {
        Random rand = new Random();
        List<Point> centroids = new ArrayList<>();
        for (int i = 0; i < K; i++) {
            centroids.add(dataPoints.get(rand.nextInt(dataPoints.size())));
        }
        return centroids;
    }
}

২. Mean Shift সেগমেন্টেশন (Mean Shift Segmentation)

Mean Shift একটি শক্তিশালী ক্লাস্টারিং অ্যালগরিদম যা মূলত একটি নন-প্যারামেট্রিক অ্যালগরিদম। এটি একটি ডেটা পয়েন্টের ঘনত্ব ম্যাপ ব্যবহার করে সেন্ট্রয়েড বা মাঝামাঝি অবস্থান বের করে। Mean Shift সেগমেন্টেশন এর মধ্যে কনভলিউশনাল শিফট ব্যবহার করে ডেটার কেন্দ্রীয় ট্রেন্ড বের করার চেষ্টা করা হয়।

Mean Shift Algorithm:

1. এটা প্রথমে একটি পয়েন্টের জন্য ঘরোয়া বেলন (kernel) তৈরি করে।
2. এরপর ঐ পয়েন্ট থেকে গড় অবস্থান বের করে (shift) এবং পরবর্তী অবস্থানে গিয়ে একই প্রক্রিয়া চালায়।
3. এই প্রক্রিয়া পুনরাবৃত্তি হয় যতক্ষণ না গড় অবস্থান পরিবর্তন না হয় (convergence)।

Mean Shift পদ্ধতি বিভিন্ন ধরনের সিগন্যাল এবং ইমেজ সেগমেন্টেশনে ব্যবহৃত হয়, কারণ এটি কোন নির্দিষ্ট প্যারামিটার যেমন ক্লাস্টারের সংখ্যা নির্ধারণ করার প্রয়োজন হয় না, এটি শুধু ডেটার ঘনত্ব অনুসরণ করে।

Java কোড উদাহরণ (Mean Shift Algorithm):

import java.util.*;

public class MeanShiftSegmentation {
    // Mean Shift Implementation
    public static void main(String[] args) {
        // উদাহরণ ডেটা পয়েন্ট
        List<Point> points = new ArrayList<>();
        points.add(new Point(1, 2));
        points.add(new Point(2, 3));
        points.add(new Point(3, 3));
        points.add(new Point(8, 8));
        points.add(new Point(9, 9));

        double bandwidth = 2.0; // ব্যান্ডউইথ (kernel width)

        // Mean Shift সেগমেন্টেশন
        List<Point> shiftedPoints = meanShift(points, bandwidth);

        // ফলস্বরূপ পয়েন্টগুলি প্রিন্ট করুন
        for (Point p : shiftedPoints) {
            System.out.println("Shifted Point: " + p.x + ", " + p.y);
        }
    }

    // Mean Shift ফাংশন
    public static List<Point> meanShift(List<Point> points, double bandwidth) {
        List<Point> shiftedPoints = new ArrayList<>();
        for (Point p : points) {
            Point shifted = meanShiftForPoint(p, points, bandwidth);
            shiftedPoints.add(shifted);
        }
        return shiftedPoints;
    }

    // পয়েন্টের জন্য Mean Shift
    public static Point meanShiftForPoint(Point p, List<Point> points, double bandwidth) {
        Point meanShift = new Point(p.x, p

.y);
        double threshold = 0.01;
        boolean converged = false;

        while (!converged) {
            double sumX = 0, sumY = 0;
            double weightSum = 0;
            for (Point point : points) {
                double dist = Math.sqrt(Math.pow(point.x - meanShift.x, 2) + Math.pow(point.y - meanShift.y, 2));
                double weight = Math.exp(-dist * dist / (2 * bandwidth * bandwidth));
                sumX += weight * point.x;
                sumY += weight * point.y;
                weightSum += weight;
            }
            Point newMean = new Point(sumX / weightSum, sumY / weightSum);

            if (Math.abs(meanShift.x - newMean.x) < threshold && Math.abs(meanShift.y - newMean.y) < threshold) {
                converged = true;
            } else {
                meanShift = newMean;
            }
        }
        return meanShift;
    }

    static class Point {
        double x, y;
        Point(double x, double y) {
            this.x = x;
            this.y = y;
        }
    }
}

সারসংক্ষেপ:

1. K-means ক্লাস্টারিং:
   • K-means একটি জনপ্রিয় ক্লাস্টারিং অ্যালগরিদম যা ডেটা পয়েন্টগুলিকে Kটি গ্রুপে ভাগ করে। এটি ক্লাস্টারের সেন্ট্রয়েড এবং পয়েন্টগুলির মধ্যে সর্বনিম্ন দূরত্ব ভিত্তিক কাজ করে।
2. Mean Shift সেগমেন্টেশন:
   • Mean Shift একটি নন-প্যারামেট্রিক ক্লাস্টারিং অ্যালগরিদম যা ডেটার ঘনত্ব অনুসারে সেন্ট্রয়েড বা মাঝামাঝি অবস্থান বের করে এবং ক্লাস্টারিং করে। এটি কোনো প্যারামিটার (যেমন K) নির্ধারণ ছাড়াই কাজ করতে পারে।

এই দুটি ক্লাস্টারিং টেকনিক অত্যন্ত কার্যকরী এবং বিভিন্ন ডেটা সেগমেন্টেশনে ব্যাপকভাবে ব্যবহৃত হয়, বিশেষ করে ইমেজ সেগমেন্টেশন এবং ডেটা মাইনিং অ্যাপ্লিকেশনগুলিতে।