El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Algoritmes de Clustering

Següent ►
►

Introducció

Els algoritmes de clustering són tècniques d'aprenentatge automàtic no supervisat que agrupen un conjunt de dades en clústers (o grups) de manera que els elements dins d'un mateix clúster siguin més similars entre ells que amb els elements d'altres clústers. Aquestes tècniques són àmpliament utilitzades en anàlisi de dades, mineria de dades, reconeixement de patrons i moltes altres aplicacions.

Conceptes Bàsics

Abans d'entrar en els detalls dels diferents algoritmes de clustering, és important entendre alguns conceptes bàsics:

  • Distància: Mesura de la similitud entre dos punts de dades. Les mesures de distància més comunes són la distància euclidiana, la distància de Manhattan i la distància cosinus.
  • Centroid: El punt central d'un clúster, sovint calculat com la mitjana dels punts de dades dins del clúster.
  • Inèrcia: Mesura de la dispersió dels punts de dades dins dels seus respectius clústers. Una inèrcia més baixa indica clústers més compactes.

Algoritmes de Clustering

K-means

Descripció

K-means és un dels algoritmes de clustering més populars i senzills. L'objectiu és dividir un conjunt de dades en K clústers, on K és un paràmetre predefinit.

Procediment

  1. Inicialitzar K centroids aleatòriament.
  2. Assignar cada punt de dades al centroid més proper.
  3. Recalcular els centroids com la mitjana dels punts assignats a cada clúster.
  4. Repetir els passos 2 i 3 fins que els centroids no canviïn significativament.

Exemple de Codi

from sklearn.cluster import KMeans
import numpy as np

# Generar dades aleatòries
X = np.random.rand(100, 2)

# Aplicar K-means
kmeans = KMeans(n_clusters=3, random_state=0).fit(X)

# Obtenir les etiquetes dels clústers
labels = kmeans.labels_

# Obtenir els centroids
centroids = kmeans.cluster_centers_

Avantatges i Desavantatges

Avantatges:

  • Senzill i fàcil d'implementar.
  • Escalable per a grans conjunts de dades.

Desavantatges:

  • Necessita especificar K.
  • Sensible a la inicialització dels centroids.
  • No funciona bé amb clústers de formes no esfèriques.

Algoritme de Clustering Jeràrquic

Descripció

El clustering jeràrquic construeix una jerarquia de clústers. Pot ser aglomeratiu (bottom-up) o divisori (top-down).

Procediment

  1. Aglomeratiu:

    • Comença amb cada punt de dades com un clúster individual.
    • Fusiona els clústers més propers iterativament fins que només quedi un clúster.

  2. Divisori:

    • Comença amb tots els punts de dades en un sol clúster.
    • Divideix iterativament els clústers fins que cada punt de dades estigui en el seu propi clúster.

Exemple de Codi

from scipy.cluster.hierarchy import dendrogram, linkage
import matplotlib.pyplot as plt

# Generar dades aleatòries
X = np.random.rand(100, 2)

# Aplicar clustering jeràrquic
Z = linkage(X, 'ward')

# Dibuixar el dendrograma
plt.figure()
dendrogram(Z)
plt.show()

Avantatges i Desavantatges

Avantatges:

  • No necessita especificar el nombre de clústers.
  • Proporciona una representació visual (dendrograma).

Desavantatges:

  • No és escalable per a grans conjunts de dades.
  • Les decisions de fusió/divisió són irreversibles.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

Descripció

DBSCAN és un algoritme de clustering basat en la densitat que pot trobar clústers de formes arbitràries i identificar punts de soroll.

Procediment

  1. Seleccionar un punt no visitat i trobar tots els punts dins d'un radi ε (epsilon).
  2. Si el nombre de punts dins del radi és superior a un mínim predefinit (minPts), es crea un nou clúster.
  3. Expandir el clúster agregant punts densament connectats.
  4. Repetir fins que tots els punts hagin estat visitats.

Exemple de Codi

from sklearn.cluster import DBSCAN

# Generar dades aleatòries
X = np.random.rand(100, 2)

# Aplicar DBSCAN
dbscan = DBSCAN(eps=0.1, min_samples=5).fit(X)

# Obtenir les etiquetes dels clústers
labels = dbscan.labels_

Avantatges i Desavantatges

Avantatges:

  • No necessita especificar el nombre de clústers.
  • Pot trobar clústers de formes arbitràries.
  • Identifica punts de soroll.

Desavantatges:

  • Sensible als paràmetres ε i minPts.
  • No funciona bé amb dades de densitat variable.

Exercicis Pràctics

Exercici 1: Aplicar K-means

  1. Genera un conjunt de dades aleatòries amb 200 punts en 2 dimensions.
  2. Aplica l'algoritme K-means amb K=4.
  3. Visualitza els clústers i els centroids.

Solució

import matplotlib.pyplot as plt

# Generar dades aleatòries
X = np.random.rand(200, 2)

# Aplicar K-means
kmeans = KMeans(n_clusters=4, random_state=0).fit(X)
labels = kmeans.labels_
centroids = kmeans.cluster_centers_

# Visualitzar els clústers
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis')
plt.scatter(centroids[:, 0], centroids[:, 1], s=300, c='red')
plt.show()

Exercici 2: Aplicar DBSCAN

  1. Genera un conjunt de dades aleatòries amb 300 punts en 2 dimensions.
  2. Aplica l'algoritme DBSCAN amb ε=0.05 i minPts=5.
  3. Visualitza els clústers i els punts de soroll.

Solució

# Generar dades aleatòries
X = np.random.rand(300, 2)

# Aplicar DBSCAN
dbscan = DBSCAN(eps=0.05, min_samples=5).fit(X)
labels = dbscan.labels_

# Visualitzar els clústers
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis')
plt.show()

Resum

En aquesta secció, hem explorat diversos algoritmes de clustering, incloent K-means, clustering jeràrquic i DBSCAN. Hem après els conceptes bàsics, avantatges i desavantatges de cada algoritme, i hem aplicat aquests algoritmes a conjunts de dades aleatòries mitjançant exemples de codi en Python. Els exercicis pràctics proporcionats ajuden a reforçar els conceptes apresos i a desenvolupar habilitats pràctiques en l'aplicació d'algoritmes de clustering.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats