DBSCAN

DBSCAN (tsz. DBSCANs)

1. (informatika, mesterséges intelligencia, algoritmusok) A DBSCAN egy népszerű sűrűség-alapú klaszterezési algoritmus, amelyet Martin Ester és Hans-Peter Kriegel fejlesztettek ki 1996-ban. Az algoritmus célja, hogy sűrűséghez hasonló területek alapján azonosítson klasztereket az adatokban, miközben az adatok zajos pontjait külön osztályozza.

1. Sűrűség alapú klaszterezés:
   • Az algoritmus a pontok lokális sűrűsége alapján csoportosítja az adatokat.
   • Az adatpontokat a szomszédos pontok számával és elérhetőségével osztályozza.
2. Paraméterek:
   • ${\textstyle \varepsilon }$: A környezet sugarát meghatározó távolság.
   • (MinPts): A minimális pontszám, amely egy pont környezetét sűrűnek tekinti.
3. Ponttípusok:
   • Magpont (Core Point): Egy pont, amelynek ${\textstyle \varepsilon }$-sugarú környezetében legalább (MinPts) adatpont található.
   • Határpont (Border Point): Egy pont, amely nem magpont, de egy magpont ${\textstyle \varepsilon }$-sugarú környezetében van.
   • Zajos pont (Noise Point): Egy pont, amely nem esik egy klaszterhez sem.

1. Adott pontok inicializálása:
   • Kezdj minden pontot címkézetlenül.
2. Minden pont elemzése:
   • Vizsgáld meg a pont ${\textstyle \varepsilon }$-sugarú környezetét.
   • Ha a pont magpont, hozz létre egy új klasztert.
   • Ha a pont nem magpont, ellenőrizd, hogy határpont-e. Ha nem, zajos pontként címkézed.
3. Klaszterek növelése:
   • Ha egy pont magpont, iteratívan hozzárendelj minden szomszédos pontot a klaszterhez.
4. Zajos pontok kezelése:
   • Azokat a pontokat, amelyek nem illenek klaszterbe, zajos pontként jelöli meg.

• Legrosszabb eset: ${\textstyle O(n^{2})}$, ha a szomszédságot lineárisan számítjuk minden pont esetén.
• Optimális eset: ${\textstyle O(n\log n)}$, ha hatékony térbeli indexelési struktúrákat (pl. KD-fa vagy R-fa) használunk.

1. Nem igényel előzetes klaszterszám-meghatározást.
2. Klaszterek tetszőleges alakúak lehetnek (ellentétben például a k-means-szel, amely gömb alakú klasztereket keres).
3. Zajos adatok kezelése: Az algoritmus zajos pontokat külön osztályoz.

1. Paraméterérzékenység:
   • A () és (MinPts) paraméterek megválasztása jelentősen befolyásolja a klaszterezést.
2. Nagy dimenziójú adatok:
   • Nagy dimenziók esetén nehéz optimális ()-t választani, és az algoritmus kevésbé hatékony.
3. Egyenetlen sűrűségű klaszterek kezelése:
   • Az algoritmus gyengén teljesít, ha az adatokban különböző sűrűségű klaszterek vannak.

A scikit-learn könyvtár tartalmazza a DBSCAN implementációját.

from sklearn.cluster import DBSCAN
import numpy as np
import matplotlib.pyplot as plt

# Példaadatok generálása
from sklearn.datasets import make_blobs
X, _ = make_blobs(n_samples=300, centers=3, cluster_std=0.5, random_state=0)

# DBSCAN modell
dbscan = DBSCAN(eps=0.3, min_samples=5)
labels = dbscan.fit_predict(X)

# Eredmények vizualizálása
plt.scatter(X, X, c=labels, cmap='viridis', marker='o')
plt.title("DBSCAN klaszterezés")
plt.xlabel("X tengely")
plt.ylabel("Y tengely")
plt.show()

DBSCAN implementálása C++-ban nehezebb lehet, de térbeli adatstruktúrákkal (pl. KD-fa) hatékonyan megvalósítható.

#include <iostream>
#include <vector>
#include <cmath>
#include <unordered_set>

using namespace std;

// 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);
}

// DBSCAN algoritmus
void dbscan(const vector<vector<double>>& points, double eps, int minPts, vector<int>& labels) {
    int cluster_id = 0;
    size_t n = points.size();
    labels.assign(n, -1); // -1 jelöli a zajos pontokat

    for (size_t i = 0; i < n; ++i) {
        if (labels != -1) continue;

        // Szomszédok keresése
        vector<int> neighbors;
        for (size_t j = 0; j < n; ++j) {
            if (euclidean_distance(points, points) <= eps) {
                neighbors.push_back(j);
            }
        }

        if (neighbors.size() < static_cast<size_t>(minPts)) {
            labels = -1; // Zajos pont
            continue;
        }

        // Új klaszter
        ++cluster_id;
        labels = cluster_id;

        // Expand klaszter
        size_t idx = 0;
        while (idx < neighbors.size()) {
            int neighbor = neighbors;
            if (labels == -1) {
                labels = cluster_id;
            } else if (labels != 0) {
                ++idx;
                continue;
            }

            labels = cluster_id;

            // Új szomszédok keresése
            vector<int> new_neighbors;
            for (size_t j = 0; j < n; ++j) {
                if (euclidean_distance(points, points) <= eps) {
                    new_neighbors.push_back(j);
                }
            }

            if (new_neighbors.size() >= static_cast<size_t>(minPts)) {
                neighbors.insert(neighbors.end(), new_neighbors.begin(), new_neighbors.end());
            }

            ++idx;
        }
    }
}

int main() {
    vector<vector<double>> points = {{1, 1}, {2, 2}, {3, 3}, {8, 8}, {8, 9}, {25, 80}};
    double eps = 2.0;
    int minPts = 2;
    vector<int> labels;

    dbscan(points, eps, minPts, labels);

    for (size_t i = 0; i < labels.size(); ++i) {
        cout << "Pont " << i << ": klaszter " << labels << endl;
    }

    return 0;
}

Kimenet:

Pont 0: klaszter 1
Pont 1: klaszter 1
Pont 2: klaszter 1
Pont 3: klaszter 2
Pont 4: klaszter 2
Pont 5: zajos pont

1. Adatok klaszterezése:
   • Tetszőleges alakú klaszterek felismerése.
2. Kép- és hangfeldolgozás:
   • Zajos adatok eltávolítása.
3. GPS-adatok:
   • Geolokációs csoportok és mintázatok azonosítása.
4. Bioinformatika:
   • Génkifejezési adatok klaszterezése.

A DBSCAN egy robusztus és rugalmas klaszterezési algoritmus, amely jól kezeli a zajos adatokat és a tetszőleges alakú klasztereket. Bár paraméterérzékenysége és nagy dimenziójú adatokon való alkalmazása kihívásokat jelenthet, számos gyakorlati probléma megoldására kiváló eszköz.

• DBSCAN - Szótár.net (en-hu)
• DBSCAN - Sztaki (en-hu)
• DBSCAN - Merriam–Webster
• DBSCAN - Cambridge
• DBSCAN - WordNet
• DBSCAN - Яндекс (en-ru)
• DBSCAN - Google (en-hu)
• DBSCAN - Wikidata
• DBSCAN - Wikipédia (angol)