Przejdź do głównej zawartości

dbscan

czym jest DBSCAN? ⭐​

  • DBSCAN (Density-Based Spatial Clustering of Applications with Noise) to algorytm klasteryzacji oparty na gęstości.
  • Automatycznie określa liczbę klastrów na podstawie gęstości danych.
  • Może wykrywać klastry o dowolnym kształcie (nie tylko sferyczne).
  • Automatycznie identyfikuje punkty odstające (outliers) jako szum.
  • Jest szczególnie skuteczny dla danych z nieregularnymi wzorcami.

jak działa DBSCAN? ⭐​

Parametry:​

  • eps (ε): Maksymalna odległość między punktami w tym samym klastrze.
  • min_samples: Minimalna liczba punktów wymagana do utworzenia klastra.

Algorytm:​

  1. Znajdowanie punktów rdzeniowych: Punkty z co najmniej min_samples sąsiadami w promieniu eps.
  2. Rozszerzanie klastrów: Dodawanie punktów granicznych do klastrów.
  3. Identyfikacja szumu: Punkty, które nie należą do żadnego klastra.

Typy punktów:​

  • Core points: Punkty rdzeniowe (wystarczająco dużo sąsiadów).
  • Border points: Punkty graniczne (należą do klastra, ale nie są rdzeniowe).
  • Noise points: Punkty szumu (outliers).

przykładowy kod (DBSCAN)​

import pandas as pd
import numpy as np
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score
import matplotlib.pyplot as plt
import seaborn as sns

# Generowanie danych z nieregularnymi kształtami
np.random.seed(42)
n_samples = 500

# Kształt półksiężyca
t = np.linspace(0, np.pi, n_samples//2)
moon1_x = np.cos(t) + np.random.normal(0, 0.1, n_samples//2)
moon1_y = np.sin(t) + np.random.normal(0, 0.1, n_samples//2)

moon2_x = 2 + np.cos(t) + np.random.normal(0, 0.1, n_samples//2)
moon2_y = -0.5 + np.sin(t) + np.random.normal(0, 0.1, n_samples//2)

# Dodanie punktów odstających
outliers_x = np.random.uniform(-2, 4, n_samples//10)
outliers_y = np.random.uniform(-2, 2, n_samples//10)

# Łączenie danych
X = np.vstack([
    np.column_stack([moon1_x, moon1_y]),
    np.column_stack([moon2_x, moon2_y]),
    np.column_stack([outliers_x, outliers_y])
])

# Tworzenie DataFrame
data = pd.DataFrame(X, columns=['feature1', 'feature2'])

print("Rozmiar danych:", data.shape)
print("Przykładowe dane:")
print(data.head())

# Wizualizacja oryginalnych danych
plt.figure(figsize=(12, 4))
plt.subplot(1, 3, 1)
plt.scatter(data['feature1'], data['feature2'], alpha=0.6)
plt.title('Oryginalne dane (kształt półksiężyca)')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.grid(True, alpha=0.3)

1. podstawowy DBSCAN​

# Skalowanie danych
scaler = StandardScaler()
X_scaled = scaler.fit_transform(data)

# Trenowanie DBSCAN
dbscan = DBSCAN(eps=0.3, min_samples=5)
dbscan.fit(X_scaled)

# Przewidywanie klastrów
labels = dbscan.labels_
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = list(labels).count(-1)

print(f"Liczba klastrów: {n_clusters}")
print(f"Liczba punktów szumu: {n_noise}")
print(f"Liczba wszystkich punktów: {len(labels)}")

# Dodanie etykiet do danych
data['cluster'] = labels

print("\nRozkład klastrów:")
print(data['cluster'].value_counts().sort_index())

# Wizualizacja wyników
plt.subplot(1, 3, 2)
colors = plt.cm.Set1(np.linspace(0, 1, n_clusters + 1))

# Rysowanie klastrów
for i in range(-1, n_clusters):
    cluster_data = data[data['cluster'] == i]
    if i == -1:
        plt.scatter(cluster_data['feature1'], cluster_data['feature2'], 
                   c='black', alpha=0.6, label='Szum', s=20)
    else:
        plt.scatter(cluster_data['feature1'], cluster_data['feature2'], 
                   c=[colors[i]], alpha=0.6, label=f'Klaster {i}')

plt.title(f'DBSCAN (eps=0.3, min_samples=5)')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.legend()
plt.grid(True, alpha=0.3)

2. wpływ parametrów na wyniki​

# Testowanie różnych parametrów
eps_values = [0.1, 0.3, 0.5]
min_samples_values = [3, 5, 10]

plt.figure(figsize=(15, 10))

for i, eps in enumerate(eps_values):
    for j, min_samples in enumerate(min_samples_values):
        plt.subplot(len(eps_values), len(min_samples_values), i * len(min_samples_values) + j + 1)
        
        # DBSCAN z różnymi parametrami
        dbscan_test = DBSCAN(eps=eps, min_samples=min_samples)
        dbscan_test.fit(X_scaled)
        
        labels_test = dbscan_test.labels_
        n_clusters_test = len(set(labels_test)) - (1 if -1 in labels_test else 0)
        
        # Wizualizacja
        for k in range(-1, n_clusters_test):
            cluster_mask = labels_test == k
            if k == -1:
                plt.scatter(X[cluster_mask, 0], X[cluster_mask, 1], 
                           c='black', alpha=0.6, s=20)
            else:
                plt.scatter(X[cluster_mask, 0], X[cluster_mask, 1], 
                           c=plt.cm.Set1(k), alpha=0.6)
        
        plt.title(f'eps={eps}, min_samples={min_samples}\nKlastrów: {n_clusters_test}')
        plt.grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

# Analiza wpływu parametrów
print("Analiza wpływu parametrów:")
for eps in eps_values:
    for min_samples in min_samples_values:
        dbscan_test = DBSCAN(eps=eps, min_samples=min_samples)
        dbscan_test.fit(X_scaled)
        
        labels_test = dbscan_test.labels_
        n_clusters_test = len(set(labels_test)) - (1 if -1 in labels_test else 0)
        n_noise_test = list(labels_test).count(-1)
        
        print(f"eps={eps}, min_samples={min_samples}: "
              f"Klastrów={n_clusters_test}, Szum={n_noise_test}")

3. porównanie z K-means​

from sklearn.cluster import KMeans

# K-means dla porównania
kmeans = KMeans(n_clusters=2, random_state=42, n_init=10)
kmeans.fit(X_scaled)
kmeans_labels = kmeans.labels_

# DBSCAN
dbscan_compare = DBSCAN(eps=0.3, min_samples=5)
dbscan_compare.fit(X_scaled)
dbscan_labels = dbscan_compare.labels_

# Wizualizacja porównania
plt.figure(figsize=(12, 4))

# K-means
plt.subplot(1, 3, 1)
for i in range(2):
    cluster_mask = kmeans_labels == i
    plt.scatter(X[cluster_mask, 0], X[cluster_mask, 1], 
               c=plt.cm.Set1(i), alpha=0.6, label=f'Klaster {i}')

plt.title('K-means (K=2)')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.legend()
plt.grid(True, alpha=0.3)

# DBSCAN
plt.subplot(1, 3, 2)
n_clusters_dbscan = len(set(dbscan_labels)) - (1 if -1 in dbscan_labels else 0)
for i in range(-1, n_clusters_dbscan):
    cluster_mask = dbscan_labels == i
    if i == -1:
        plt.scatter(X[cluster_mask, 0], X[cluster_mask, 1], 
                   c='black', alpha=0.6, label='Szum', s=20)
    else:
        plt.scatter(X[cluster_mask, 0], X[cluster_mask, 1], 
                   c=plt.cm.Set1(i), alpha=0.6, label=f'Klaster {i}')

plt.title('DBSCAN')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.legend()
plt.grid(True, alpha=0.3)

# Porównanie metryk
plt.subplot(1, 3, 3)
comparison_data = {
    'Algorytm': ['K-means', 'DBSCAN'],
    'Liczba klastrów': [2, n_clusters_dbscan],
    'Punkty szumu': [0, list(dbscan_labels).count(-1)]
}

comparison_df = pd.DataFrame(comparison_data)
print("\nPorównanie algorytmów:")
print(comparison_df)

# Wizualizacja porównania
plt.bar(comparison_df['Algorytm'], comparison_df['Liczba klastrów'])
plt.title('Porównanie liczby klastrów')
plt.ylabel('Liczba klastrów')
plt.grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

4. analiza punktów rdzeniowych i granicznych​

# Funkcja do analizy punktów DBSCAN
def analyze_dbscan_points(X, labels, eps, min_samples):
    """Analiza typów punktów w DBSCAN"""
    from sklearn.neighbors import NearestNeighbors
    
    # Znajdowanie sąsiadów dla każdego punktu
    nbrs = NearestNeighbors(n_neighbors=min_samples).fit(X)
    distances, indices = nbrs.kneighbors(X)
    
    # Analiza typów punktów
    core_points = []
    border_points = []
    noise_points = []
    
    for i, label in enumerate(labels):
        if label == -1:
            noise_points.append(i)
        else:
            # Sprawdzenie czy punkt jest rdzeniowy
            neighbors_in_eps = np.sum(distances[i] <= eps)
            if neighbors_in_eps >= min_samples:
                core_points.append(i)
            else:
                border_points.append(i)
    
    return core_points, border_points, noise_points

# Analiza punktów
core_points, border_points, noise_points = analyze_dbscan_points(
    X_scaled, dbscan_labels, eps=0.3, min_samples=5
)

print(f"Analiza punktów DBSCAN:")
print(f"Punkty rdzeniowe: {len(core_points)}")
print(f"Punkty graniczne: {len(border_points)}")
print(f"Punkty szumu: {len(noise_points)}")

# Wizualizacja typów punktów
plt.figure(figsize=(10, 4))

plt.subplot(1, 2, 1)
plt.scatter(X[core_points, 0], X[core_points, 1], 
           c='red', alpha=0.8, label='Punkty rdzeniowe', s=50)
plt.scatter(X[border_points, 0], X[border_points, 1], 
           c='blue', alpha=0.6, label='Punkty graniczne', s=30)
plt.scatter(X[noise_points, 0], X[noise_points, 1], 
           c='black', alpha=0.8, label='Punkty szumu', s=20)

plt.title('Typy punktów w DBSCAN')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.legend()
plt.grid(True, alpha=0.3)

5. DBSCAN dla danych wielowymiarowych​

# Generowanie danych wielowymiarowych
np.random.seed(42)
n_samples_multi = 300
n_features = 3

# Trzy klastry w 3D
cluster1_3d = np.random.multivariate_normal([0, 0, 0], np.eye(3), n_samples_multi//3)
cluster2_3d = np.random.multivariate_normal([3, 3, 3], np.eye(3), n_samples_multi//3)
cluster3_3d = np.random.multivariate_normal([0, 3, 0], np.eye(3), n_samples_multi//3)

# Dodanie punktów odstających
outliers_3d = np.random.uniform(-2, 5, (n_samples_multi//10, 3))

X_3d = np.vstack([cluster1_3d, cluster2_3d, cluster3_3d, outliers_3d])
data_3d = pd.DataFrame(X_3d, columns=[f'feature_{i+1}' for i in range(n_features)])

# Skalowanie
scaler_3d = StandardScaler()
X_3d_scaled = scaler_3d.fit_transform(data_3d)

# DBSCAN dla danych 3D
dbscan_3d = DBSCAN(eps=0.5, min_samples=5)
dbscan_3d.fit(X_3d_scaled)

# Analiza wyników
data_3d['cluster'] = dbscan_3d.labels_
n_clusters_3d = len(set(dbscan_3d.labels_)) - (1 if -1 in dbscan_3d.labels_ else 0)

print(f"DBSCAN dla danych 3D:")
print(f"Liczba klastrów: {n_clusters_3d}")
print(f"Punkty szumu: {list(dbscan_3d.labels_).count(-1)}")

# Wizualizacja 3D
from mpl_toolkits.mplot3d import Axes3D

fig = plt.figure(figsize=(12, 4))

ax1 = fig.add_subplot(131, projection='3d')
for i in range(-1, n_clusters_3d):
    cluster_mask = dbscan_3d.labels_ == i
    if i == -1:
        ax1.scatter(X_3d[cluster_mask, 0], X_3d[cluster_mask, 1], X_3d[cluster_mask, 2], 
                   c='black', alpha=0.6, s=20, label='Szum')
    else:
        ax1.scatter(X_3d[cluster_mask, 0], X_3d[cluster_mask, 1], X_3d[cluster_mask, 2], 
                   c=plt.cm.Set1(i), alpha=0.6, label=f'Klaster {i}')

ax1.set_title('DBSCAN 3D')
ax1.set_xlabel('Feature 1')
ax1.set_ylabel('Feature 2')
ax1.set_zlabel('Feature 3')
ax1.legend()

# Wizualizacja 2D (pierwsze 2 wymiary)
plt.subplot(1, 3, 2)
for i in range(-1, n_clusters_3d):
    cluster_mask = dbscan_3d.labels_ == i
    if i == -1:
        plt.scatter(X_3d[cluster_mask, 0], X_3d[cluster_mask, 1], 
                   c='black', alpha=0.6, s=20, label='Szum')
    else:
        plt.scatter(X_3d[cluster_mask, 0], X_3d[cluster_mask, 1], 
                   c=plt.cm.Set1(i), alpha=0.6, label=f'Klaster {i}')

plt.title('DBSCAN 3D - projekcja 2D')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.legend()
plt.grid(True, alpha=0.3)

# Statystyki klastrów
plt.subplot(1, 3, 3)
cluster_stats = data_3d.groupby('cluster').size()
plt.bar(range(len(cluster_stats)), cluster_stats.values)
plt.title('Rozkład klastrów')
plt.xlabel('Klaster')
plt.ylabel('Liczba punktów')
plt.xticks(range(len(cluster_stats)), cluster_stats.index)

plt.tight_layout()
plt.show()

6. praktyczne zastosowania​

# Przykład: Analiza ruchu w sieci
np.random.seed(42)
n_users = 1000

# Symulacja danych użytkowników sieci
session_duration = np.random.exponential(30, n_users)  # minuty
pages_visited = np.random.poisson(15, n_users)
bounce_rate = np.random.beta(2, 5, n_users)  # 0-1
time_on_page = np.random.exponential(2, n_users)  # minuty

# Tworzenie klastrów użytkowników
user_data = pd.DataFrame({
    'session_duration': session_duration,
    'pages_visited': pages_visited,
    'bounce_rate': bounce_rate,
    'time_on_page': time_on_page
})

# Skalowanie
scaler_users = StandardScaler()
user_data_scaled = scaler_users.fit_transform(user_data)

# DBSCAN dla segmentacji użytkowników
dbscan_users = DBSCAN(eps=0.5, min_samples=10)
dbscan_users.fit(user_data_scaled)

# Analiza segmentów
user_data['segment'] = dbscan_users.labels_
n_segments = len(set(dbscan_users.labels_)) - (1 if -1 in dbscan_users.labels_ else 0)

print(f"Segmentacja użytkowników:")
print(f"Liczba segmentów: {n_segments}")
print(f"Użytkownicy odstający: {list(dbscan_users.labels_).count(-1)}")

# Charakterystyka segmentów
segment_analysis = user_data.groupby('segment').agg({
    'session_duration': ['mean', 'std'],
    'pages_visited': ['mean', 'std'],
    'bounce_rate': ['mean', 'std'],
    'time_on_page': ['mean', 'std']
}).round(2)

print("\nCharakterystyka segmentów:")
print(segment_analysis)

# Nazwanie segmentów
segment_names = {
    -1: 'Użytkownicy odstający',
    0: 'Aktywni użytkownicy',
    1: 'Przeciętni użytkownicy',
    2: 'Pasywni użytkownicy'
}

user_data['segment_name'] = user_data['segment'].map(segment_names)

print("\nPodsumowanie segmentacji:")
for segment in range(-1, n_segments):
    segment_data = user_data[user_data['segment'] == segment]
    print(f"\n{segment_names.get(segment, f'Segment {segment}')}:")
    print(f"  Liczba użytkowników: {len(segment_data)}")
    print(f"  Średni czas sesji: {segment_data['session_duration'].mean():.1f} min")
    print(f"  Średnia liczba stron: {segment_data['pages_visited'].mean():.1f}")
    print(f"  Średni bounce rate: {segment_data['bounce_rate'].mean():.3f}")

praktyczne ćwiczenia​

  1. Eksperymentuj z parametrami - przetestuj różne wartości eps i min_samples.

  2. Porównaj z innymi algorytmami - porównaj DBSCAN z K-means i hierarchiczną klasteryzacją.

  3. Analiza punktów - przeanalizuj punkty rdzeniowe, graniczne i szum.

  4. Feature engineering - dodaj nowe cechy i sprawdź wpływ na klastry.

  5. Real-world data - zastosuj DBSCAN do rzeczywistych problemów.

dobre praktyki​

  • Skalowanie: Zawsze skaluj dane przed DBSCAN.
  • Wybór eps: Użyj k-plot do wyboru optymalnego eps.
  • Interpretacja: Analizuj charakterystykę klastrów i punktów szumu.
  • Walidacja: Sprawdź stabilność wyników.

wady i zalety​

Zalety:

  • Automatycznie określa liczbę klastrów
  • Wykrywa klastry o dowolnym kształcie
  • Automatycznie identyfikuje outliers
  • Nie wymaga założenia o kształcie klastrów

Wady:

  • Wrażliwy na parametry eps i min_samples
  • Trudny w wyborze parametrów
  • Wolniejszy niż K-means
  • Problemy z klastrami o różnej gęstości

polecane źródła​