DBSCAN
Főnév
DBSCAN (tsz. DBSCANs)
- (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.
Algoritmus alapelvei
- 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.
- Paraméterek:
- : 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.
- Ponttípusok:
- Magpont (Core Point): Egy pont, amelynek -sugarú környezetében legalább (MinPts) adatpont található.
- Határpont (Border Point): Egy pont, amely nem magpont, de egy magpont -sugarú környezetében van.
- Zajos pont (Noise Point): Egy pont, amely nem esik egy klaszterhez sem.
DBSCAN működése
- Adott pontok inicializálása:
- Kezdj minden pontot címkézetlenül.
- Minden pont elemzése:
- Vizsgáld meg a pont -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.
- Klaszterek növelése:
- Ha egy pont magpont, iteratívan hozzárendelj minden szomszédos pontot a klaszterhez.
- Zajos pontok kezelése:
- Azokat a pontokat, amelyek nem illenek klaszterbe, zajos pontként jelöli meg.
Időbonyolultság
- Legrosszabb eset: , ha a szomszédságot lineárisan számítjuk minden pont esetén.
- Optimális eset: , ha hatékony térbeli indexelési struktúrákat (pl. KD-fa vagy R-fa) használunk.
Előnyök
- Nem igényel előzetes klaszterszám-meghatározást.
- Klaszterek tetszőleges alakúak lehetnek (ellentétben például a k-means-szel, amely gömb alakú klasztereket keres).
- Zajos adatok kezelése: Az algoritmus zajos pontokat külön osztályoz.
Hátrányok
- Paraméterérzékenység:
- A () és (MinPts) paraméterek megválasztása jelentősen befolyásolja a klaszterezést.
- Nagy dimenziójú adatok:
- Nagy dimenziók esetén nehéz optimális ()-t választani, és az algoritmus kevésbé hatékony.
- 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.
Python implementáció
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[:, 0], X[:, 1], c=labels, cmap='viridis', marker='o')
plt.title("DBSCAN klaszterezés")
plt.xlabel("X tengely")
plt.ylabel("Y tengely")
plt.show()
C++ implementáció
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[i] - b[i]) * (a[i] - b[i]);
}
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[i] != -1) continue;
// Szomszédok keresése
vector<int> neighbors;
for (size_t j = 0; j < n; ++j) {
if (euclidean_distance(points[i], points[j]) <= eps) {
neighbors.push_back(j);
}
}
if (neighbors.size() < static_cast<size_t>(minPts)) {
labels[i] = -1; // Zajos pont
continue;
}
// Új klaszter
++cluster_id;
labels[i] = cluster_id;
// Expand klaszter
size_t idx = 0;
while (idx < neighbors.size()) {
int neighbor = neighbors[idx];
if (labels[neighbor] == -1) {
labels[neighbor] = cluster_id;
} else if (labels[neighbor] != 0) {
++idx;
continue;
}
labels[neighbor] = cluster_id;
// Új szomszédok keresése
vector<int> new_neighbors;
for (size_t j = 0; j < n; ++j) {
if (euclidean_distance(points[neighbor], points[j]) <= 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[i] << 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
Alkalmazások
- Adatok klaszterezése:
- Tetszőleges alakú klaszterek felismerése.
- Kép- és hangfeldolgozás:
- Zajos adatok eltávolítása.
- GPS-adatok:
- Geolokációs csoportok és mintázatok azonosítása.
- Bioinformatika:
- Génkifejezési adatok klaszterezése.
Összegzés
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.