• 🏡 Home
  • 🚨 GDPR Compliant
  • ⚡️ Data Science
  • 📌 Machine Learning
  • 🔒 Privacy Preserving
  • 🏡 Home
  • 🚨 GDPR Compliant
  • ⚡️ Data Science
  • 📌 Machine Learning
  • 🔒 Privacy Preserving
Data Science

Mean-Shift Clustering

Mean-Shift Clustering

Cos’è il Mean-Shift Clustering? Il Mean-Shift Clustering è un algoritmo di raggruppamento a scorrimento di finestra di lettura (sliding-window-based), basato sui centroidi (centroid-based).

Questo post fa parte di una serie sugli algoritmi di Clustering che analizza i 5 migliori algoritmi di clustering. Oltre al Mean-Shift troviamo:

  • K-Means Clustering
  • DBSCAN
  • Expectation–Maximization (EM) Clustering using Gaussian Mixture Models (GMM)
  • Agglomerative Hierarchical Clustering

Cerchiamo di capire fin da subito il funzionamento del Mean Shift Clustering!

Lasciami ragionare con te sul significato delle parole.

Sappiamo che, trattandosi di un metodo di clustering, l’obiettivo ultimo è quello di definire dei clusters o grupppi all’interno di un dataset.

Il fatto che venga definito Mean-Shift, significa che dobbiamo aspettarci uno spostamento della media.

Mi spiego meglio.

L’obiettivo è quello d’individuare il punto centrale di ogni gruppo, cluster o classe: è il goal di ogni metodo di clustering, quindi nessuna sorpresa.

Tuttavia è il come questo avvenga a meravigliarci.

Definiamo la dimensione della finestra di lettura, e prendiamo un punto a caso.

Dapprima procediamo identificando quei punti che costituiscono la media all’interno della finestra.

I candidati sono poi filtrati in una fase successiva eliminando i duplicati vicini, formando così un set finale di punti centrali, associati ai loro rispettivi cluster.

Questo qui sotto è il semplice esempio di funzionamento su un solo cluster:

  • L’area rossa è quella che definiamo finestra a scorrimento
  • I punti rossi sono i candidati scelti in progressione come centroidi

Come funziona il Mean-Shift Clustering?

Vediamo ora più nello specifico come funziona il Mean-Shift Clustering.

Per farlo, tieni a mente che stiamo considerando uno set di punti in uno spazio bidimensionale come nell’illustrazione precedente.

Potrebbero essere stati generati a partire da un dataset con tecniche di riduzione della dimensionalità, come la PCA.

Il Mean Schift Clustering è un algoritmo di hill climbing, una tecnica di ottimizzazione matematica che appartiene alla famiglia della ricerca locale.

Contrariamente a un algoritmo di Gradient Descent che segue e ricerca la discesa dell’elevazione, quello di Hill Climbing si muove continuamente nella direzione di maggiore elevazione, terminando l’esecuzione al raggiungimento del picco massimo o quando nessun valore più alto è presente.

Come funziona il mean-Shift Clustering? Il Mean-Shift Clustering funziona allora così:

  1. Definiamo il kernel come una finestra a scorrimento circolare (circular sliding window) centrata in un punto C scelto casualmente (randomly selected) e con raggio R.
  2. A ogni iterazione, il kernel è mosso verso la regione di più alta densità, ricalcolando il punto medio sulla base di quelli presenti all’interno della finestra. La densità è quindi riferita al numero di osservazioni all’interno del kernel.
  3. Il processo iterativo termina quando non ci sono più direzioni verso cui muovere il kernel affinché il numero di elementi al suo interno cresca ulteriormente: si è raggiunto il picco.

Il processo da 1 a 3 può essere compiuto con molteplici finestre, finché tutti i punti non cadano in una sola finestra.

I clusters sono quindi calcolati sulla base dell’appartenenza dei singoli punti alle rispettive finestre.

Quando più finestre si sovrappongono, la precedenza è data alla finestra che contiene il maggior numero di elementi.

Ecco una visualizzazione del processo:

Codice in Python

In python la libreria di riferimento è scikit-learn. Il link, questo.

Per il momento è tutto.

Per aspera, ad astra.

Un caldo abbraccio, Andrea

Written by Andrea Provino - Dicembre 3, 2020
Tags | data science, teoria

You Might Also Like

deep-learning

Let’s start Deep Learning | 6.S191 – Machine Learning

Febbraio 21, 2020

DBSCAN: Density-based spatial clustering of applications with noise

Novembre 13, 2019
folium-python-tutorial-geospatial-data-representation-data-analysis-tutorial-python-guide

Folium: geospatial data python

Novembre 12, 2019

No Comment

Please Post Your Comments & Reviews
Annulla risposta

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

Next Post
Previous Post

Una pubblicità che non vedi se usi AdBlock

EXPAND YOUR KNOWLEDGE

  • Blockchain

    Patricia Merkle Trie

    Maggio 30, 2023
  • Artistic representation of a tree Blockchain

    Tree Data Structure: cos’è un Merkle Tree

    Maggio 26, 2023
  • Cover image for Bitcoin UTXO explanation post Blockchain

    UTXO: come funziona il modello Unspent Transaction Outputs

    Maggio 23, 2023
  • Blockchain

    Cos’è Ethereum

    Maggio 15, 2023
  • Blockchain Developer

    Circuito aritmetico

    Novembre 1, 2022
  • machine-learning

    Un nuovo inizio

    Settembre 4, 2021
  • Zero Knwoledge Proof Article Privacy Preserving

    Zero Knowledge Proof: zk-SNARK e zk-STARK | Prova a conoscenza zero

    Luglio 8, 2021
  • oblivious-transfer-spiegazione-italiano-ot-explanation Privacy Preserving

    Oblivious Transfer (OT)

    Luglio 6, 2021
  • Aleo Studio Website Preview machine-learning

    Aleo Studio: un IDE per Zero-Knowledge Proofs Applications

    Luglio 1, 2021
  • privacy-enhancing-technologies-data-machine-learning-data-science Privacy Preserving

    Perché il Privacy Tech è un vantaggio competitivo micidiale

    Giugno 17, 2021

Quello che Google pensa ti possa piacere

Prodotti che i Cookie dicono potresti trovare interessanti

AI Blog - © 2019-2021 Andrea Provino