k-means algoritmus

Magyar

Kiejtés

IPA: [ ˈkmɛɒnʃɒlɡoritmuʃ]

Főnév

k-means algoritmus

(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.

Algoritmus működése

Bemenet:

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

Kimenet:

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

Lépések

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.
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).
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: $c_{j}={\frac {1}{|S_{j}|}}\sum _{x_{i}\in S_{j}}x_{i}$
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.

Matematikai megfogalmazás

A K-means célja a következő célfüggvény minimalizálása: $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.

Időbonyolultság

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ó.

Előnyök

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

Hátrányok

K klaszterek számának előzetes megadása:
- Az algoritmusnak tudnia kell, hogy hány klasztert keressen.
É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ó.
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.
Zajra érzékeny:
- A k-means nem kezeli jól a zajos adatokat vagy az outliereket.

K-means Pythonban

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[:, 0], X[:, 1], c=y_kmeans, cmap='viridis', marker='o')
plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], s=200, c='red', marker='X')
plt.title("K-means klaszterezés")
plt.xlabel("X tengely")
plt.ylabel("Y tengely")
plt.show()

K-means C++-ban

#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[i] - b[i]) * (a[i] - b[i]);
    }
    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[0].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[i] = data[rand() % n];
    }

    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[i], centroids[j]);
                if (dist < min_dist) {
                    min_dist = dist;
                    labels[i] = 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[i];
            for (int j = 0; j < d; ++j) {
                new_centroids[cluster][j] += data[i][j];
            }
            counts[cluster]++;
        }

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

        centroids = new_centroids;
    }

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

Alkalmazások

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

Összegzés

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.

További információk

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)