k-means algoritmus

• IPA:

k-means algoritmus

1. (matematika, algoritmusok) A K-means egy egyszerű, mégis hatékony klaszterezési algoritmus, amelyet széles körben használnak adatbányászatban és gépi tanulásban. Az algoritmus célja az adatok (K) darab klaszterre bontása úgy, hogy a klasztereken belüli pontok távolsága minimális legyen a klaszter középpontjától.

• Egy adathalmaz (${\textstyle X=\{x_{1},x_{2},...,x_{n}\}}$),
• A klaszterek kívánt száma K.

• (K) klaszter, amelyhez minden adatpont tartozik,
• A klaszterek középpontjai.

1. Inicializáció:
   • Válassz (K) klaszterközéppontot (${\textstyle c_{1},c_{2},...,c_{K}}$). Ezeket véletlenszerűen választhatod az adathalmazból, vagy speciális módszerekkel, például k-means++-szal.
2. Hozzárendelés:
   • Minden adatpontot ((x_i)) rendelj ahhoz a klaszterhez, amelynek középpontja a legközelebb van ${\textstyle d(x_{i},c_{j})}$ alapján, ahol d általában az euklideszi távolság).
3. Középpont frissítése:
   • Számítsd újra minden klaszter középpontját úgy, hogy az a klaszterbe tartozó pontok centroidja legyen: $${\displaystyle c_{j}={\frac {1}{|S_{j}|}}\sum _{x_{i}\in S_{j}}x_{i}}$$
4. Ismétlés:
   • Ismételd a hozzárendelést és a középpontfrissítést, amíg a klaszterközéppontok nem változnak, vagy el nem éred a maximális iterációszámot.

A K-means célja a következő célfüggvény minimalizálása: $${\displaystyle J=\sum _{j=1}^{K}\sum _{x_{i}\in S_{j}}||x_{i}-c_{j}||^{2}}$$ ahol: - ${\textstyle S_{j}}$: A ${\textstyle j}$-edik klaszterhez tartozó pontok halmaza, - ${\textstyle c_{j}}$: A ${\textstyle j}$-edik klaszter középpontja.

• Legrosszabb eset: ${\textstyle O(n\cdot K\cdot T\cdot d)}$, ahol:
  • (n): Adatpontok száma,
  • (K): Klaszterek száma,
  • (T): Iterációk száma,
  • (d): Adatdimenzió.

1. Egyszerű és gyors:
   • Könnyen érthető és gyorsan fut kis és közepes méretű adathalmazokon.
2. Jól működik gömb alakú klasztereken:
   • Ha az adatok természetesen gömb alakú klaszterekre oszlanak, az algoritmus hatékony.
3. Párhuzamosítás:
   • Könnyen párhuzamosítható a nagy adathalmazok hatékony feldolgozására.

1. K klaszterek számának előzetes megadása:
   • Az algoritmusnak tudnia kell, hogy hány klasztert keressen.
2. Érzékeny az inicializációra:
   • A véletlenszerű inicializáció rossz eredményekhez vezethet. Ennek javítására használható a k-means++ inicializáció.
3. Csak gömb alakú klaszterekre működik jól:
   • Nem jól kezeli a nem lineárisan elválasztott klasztereket vagy különböző méretű klasztereket.
4. Zajra érzékeny:
   • A k-means nem kezeli jól a zajos adatokat vagy az outliereket.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans

# Mintaadatok generálása
X, y = make_blobs(n_samples=300, centers=4, cluster_std=0.6, random_state=0)

# K-means futtatása
kmeans = KMeans(n_clusters=4, init='k-means++', max_iter=300, n_init=10, random_state=0)
y_kmeans = kmeans.fit_predict(X)

# Eredmények vizualizálása
plt.scatter(X, X, c=y_kmeans, cmap='viridis', marker='o')
plt.scatter(kmeans.cluster_centers_, kmeans.cluster_centers_, s=200, c='red', marker='X')
plt.title("K-means klaszterezés")
plt.xlabel("X tengely")
plt.ylabel("Y tengely")
plt.show()

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <limits>

using namespace std;

// Euklideszi távolság számítása
double euclidean_distance(const vector<double>& a, const vector<double>& b) {
    double sum = 0.0;
    for (size_t i = 0; i < a.size(); ++i) {
        sum += (a - b) * (a - b);
    }
    return sqrt(sum);
}

// K-means algoritmus
void kmeans(const vector<vector<double>>& data, int k, int max_iterations) {
    int n = data.size();       // Adatpontok száma
    int d = data.size();    // Dimenziók száma

    vector<vector<double>> centroids(k, vector<double>(d));  // Középpontok
    vector<int> labels(n);                                  // Klaszter címkék

    // Középpontok inicializálása véletlenszerűen
    for (int i = 0; i < k; ++i) {
        centroids = data;
    }

    for (int iter = 0; iter < max_iterations; ++iter) {
        // Hozzárendelés lépés
        for (int i = 0; i < n; ++i) {
            double min_dist = numeric_limits<double>::max();
            for (int j = 0; j < k; ++j) {
                double dist = euclidean_distance(data, centroids);
                if (dist < min_dist) {
                    min_dist = dist;
                    labels = j;
                }
            }
        }

        // Középpont frissítés lépés
        vector<vector<double>> new_centroids(k, vector<double>(d, 0.0));
        vector<int> counts(k, 0);

        for (int i = 0; i < n; ++i) {
            int cluster = labels;
            for (int j = 0; j < d; ++j) {
                new_centroids += data;
            }
            counts++;
        }

        for (int j = 0; j < k; ++j) {
            for (int l = 0; l < d; ++l) {
                new_centroids /= counts;
            }
        }

        centroids = new_centroids;
    }

    // Eredmények kiírása
    for (int i = 0; i < n; ++i) {
        cout << "Adatpont: ";
        for (double val : data) {
            cout << val << " ";
        }
        cout << " -> Klaszter: " << labels << endl;
    }
}

int main() {
    vector<vector<double>> data = {
        {1.0, 2.0}, {1.5, 1.8}, {5.0, 8.0}, {8.0, 8.0},
        {1.0, 0.6}, {9.0, 11.0}, {8.0, 2.0}, {10.0, 2.0}, {9.0, 3.0}
    };
    int k = 3;
    int max_iterations = 100;

    kmeans(data, k, max_iterations);
    return 0;
}

1. Adatcsoportosítás:
   • Kép- és hangadatok klaszterezése.
2. Piaci szegmentáció:
   • Vásárlói viselkedés alapján klaszterek azonosítása.
3. Tömörítés:
   • Kép- és videótömörítési technikák.
4. Anomáliaérzékelés:
   • Outlierek azonosítása az adathalmazban.

A K-means egy hatékony és gyors klaszterezési algoritmus, amely ideális jól elkülönülő gömb alakú klaszterek azonosítására. Bár korlátai vannak, mint például az érzékenység az inicializációra és az outlierekre, továbbfejlesztett változatai, például a K-means++, jelentős javulást nyújtanak. Széles körben alkalmazzák adatbányászati és gépi tanulási problémákban.

• k-means algoritmus - Értelmező szótár (MEK)
• k-means algoritmus - Etimológiai szótár (UMIL)
• k-means algoritmus - Szótár.net (hu-hu)
• k-means algoritmus - DeepL (hu-de)
• k-means algoritmus - Яндекс (hu-ru)
• k-means algoritmus - Google (hu-en)
• k-means algoritmus - Helyesírási szótár (MTA)
• k-means algoritmus - Wikidata
• k-means algoritmus - Wikipédia (magyar)