Clustering Categorial Data

(1)

Clustering Categorial Data

Daniele Contarino

University of Catania

Department of Mathematics and Computer Science (DMI)

(2)

Executive summary

 Categorial Custering

 Scopo e obiettivi

 Metriche di misura della distanza

 Applicazioni negli algoritmi di clustering per dati categoriali

(3)

 Dati numerici

• Proprietà di ordinabilità;

• Distanza euclidea;

• Ampia scelta di algoritmi (K-means, Hierachical, DB, etc.);

 Dati Categoriali

• Data structure differente rispetto ai dati numerici;

• Funzioni di distanza diverse da quella euclidea;

• Gli algoritmi conosciuti vanno rivisitati.

Categorial vs. Continuos data

(4)

Una variabile categoriale è una variabile che può assumere uno dei limitati (e

solitamente fissati) possibili valori.

e.g. nazionalità, colore dei capelli, grado di istruzione.

In un DBMS questo dato lo inseriremo in un campo di tipo ENUM.

Categorial Variable

(5)

Il dato categorico è un tipo di dato statistico che viene

rappresentato da una o più variabili categoriali, oppure variabili categoriali miste a variabili non categoriali.

Categorial Data

Continuous Variables Categorical Variable

(6)

 Forma tabellare

Matrice m-attributi X n-osservazioni

 Spatial Density-Based

Gli m-attributi vengono mostrati come un ‘cubo’ m-dimensionale.

Categorical Data Space

(7)

Ogni singola cella del ‘cubo’

(o ipercubo se m>3)

rappresenta una singola osservazione , mentre la

posizione rispetto all’origine indica il valore per l’asse di appartenenza.

Spatial DB for Categorical Data

(8)

Spatial DB for Categorical Data

P 1 h: 190 cm w: 80 kg c: Castano

P 2 h: 160 cm w: 120 kg c: Biondo

(9)

 Ogni singolo elemento viene

posizionato in base ai valori e/o categorie

 I cluster saranno dei cubi che formeranno dei sottospazi ad alta densità, separati da

sottospazi a bassa densità

Spatial DB for Categorical Data

(10)

1. Valori degli attributi non ordinabili

Celle non ordinabili

2. La ricerca viene effettuata con un raggio

definito dall’utente. Si posso definire diversi raggi per ogni attributo;

Challenges

(11)

1. In sottospazi densi le informazioni non posso mancare

ricerca ‘cell-by-cell’ con raggio = 1

2. In sottospazi sparsi è preferibile aggregare le informazioni

ricerca con alto raggio

Dense & Sparse Subspace

(12)

Quando usare raggi bassi o alti?

Radii choose

Usare bassi raggi

all’inizio della ricerca e aumentare man mano!

(13)

Raggio dello spazio dei dati categoriali

≠

Raggio dello spazio euclideo

Radii choose

(14)

Executive summary

 Categorial Custering

 Scopo e obiettivi

 Metriche di misura della distanza

(15)

 Campi di applicabilità del Clustering Categoriale maggiore rispetto al Clustering Continuo

 Numerose problematiche su una grande casistica disponibile

 Occorrono alcune caratteristiche di base desiderabili

Features of Categorical Clustering

(16)

 Scalabilità

La memoria richiesta non aumenta esponenzialmente;

 Robustezza

Riconoscere gli outliers, se essi sono distanti dagli oggetti;

 Invariante all’ordine

Le variabili categoriali non godono della proprietà di ordinabilità → algoritmo invariante all’ordine di

inserimento;

Features of Categorical Clustering

(17)

 Parametri in input richiesti all’utente ridotto

‘Less is more’

 Dati misti

Gli oggetti posso avere degli attributi numerici e/o discreti (categoriali)

 Ammissibilità punto percentuale

Oggetti duplicati e re-clustering non devono dare risultati differenti

Features of Categorical Clustering

(18)

In base a quali parametri

possiamo valutare la qualità di un algoritmo di clustering

categoriale?

Quality measure

(19)

 Precision/Recall del gold standard;

𝑝𝑟𝑒𝑐 = # 𝑐𝑜𝑝𝑝𝑖𝑒 𝑠𝑖𝑚𝑖𝑙𝑖 𝑑𝑒𝑙 𝑐𝑙𝑢𝑠𝑡𝑒𝑟

# 𝑐𝑜𝑝𝑝𝑖𝑒 𝑑𝑒𝑙 𝑐𝑙𝑢𝑠𝑡𝑒𝑟 𝑟𝑒𝑐𝑎𝑙𝑙 = # 𝑐𝑜𝑝𝑝𝑖𝑒 𝑠𝑖𝑚𝑖𝑙𝑖 𝑑𝑒𝑙 𝑐𝑙𝑢𝑠𝑡𝑒𝑟

# 𝑐𝑜𝑝𝑝𝑖𝑒 𝑠𝑖𝑚𝑖𝑙𝑖

 Entropia dei cluster

minimizzare lo spread intra-cluster e massimizzare lo spread inter-cluster

 Riproducibilità

 Rand index o Hubert-Arabie Index

misura la similarità tra due raggruppamenti di dati

Quality measure

(20)

Sia:

N → # di oggetti (o osservazioni)

k → # di cluster

m → # di attributi dell’oggetto (solitamente N>>m)

D

_i

il dominio di ogni singolo attributo

Clustering Road Map

(21)

Clustering Road Map

(22)

Executive summary

 Scopo e obiettivi

 Metriche di misura della distanza

(23)

"Measurement is the process of ... assigning numbers to objects or events."

(S. Siegel, 1956)

Similarity Measures

(24)

Il concetto di similarità per i dati categoriali non è intuitivo come per i dati numerici continui.

Per quanto due dati tra di essi possa essere comparabili, non lo sono

direttamente con la relazione di minore o maggiore

Similarity Measures

(25)

Per ogni coppia di dati categoriali, si contano gli attributi che differiscono tra di loro.

Il risultato è una stringa binaria lunga m

Hamming Distance

(26)

e.g. Zoo dataset

Hamming Distance

(27)

Pro

 Bassa complessità temporale di calcolo;

Contro

 Gli attributi vengono pesati tutti in maniera identica

 Non tiene conto degli attributi che co-variano più o meno raramente

Hamming Distance

(28)

Uso della probabilità nel considerare la

corrispondenza dei valori degli attributi presi.

 Goodall

 Smirnov

 Anderberg

Probabilistic Measures

(29)

Goodall

Si considera la probabilità che un valore di somiglianza venga osservato in un campione casuale tra due record categoriali.

Probabilistic Measures

(30)

Smirnov

Misura probabilistica dei matches e mismatches. Questa misura considera sia la frequenza dei valori sia la

distribuzione degli altri valori per lo stesso attributo. La somiglianza è più alta in un match, se i valori riscontrati sono sparsi ma gli altri valori per quel attributo sono riscontrati frequentemente.

Probabilistic Measures

(31)

Anderberg

Similmente a Smirnov, considera sia i matches che

mismatches. In questo approccio, i match su valori rari indicano una forte somiglianza, mentre i mismatch sui valori rari dovrebbero essere trattati distintamente e devono indicare inferiore somiglianza.

Probabilistic Measures

(32)

Provenienti dalla teoria dell’informazione, questi approcci sono usati per valutare il peso degli

attributi.

Già la teoria dell’informazione si occupa di individuare i dati più informativi tra i dati meno

osservati

Information-Theoretic Measures

(33)

Burnaby

 valore di somiglianza alto con mismatch sui valori frequenti;

 valore di somiglianza basso con mismatch sui valori rari.

Information-Theoretic Measures

(34)

Lin

 valore di somiglianza alto con match sui valori frequenti;

 valore di somiglianza basso con mismatch sui valori rari.

Information-Theoretic Measures

(35)

le misure basate sul contesto valutano la

somiglianza tra due oggetti esaminando i contesti in cui appaiono.

e.g. distanza tra due clienti bibite (Coca-Cola e Pepsi)

Context-Based Similarity Measures

(36)

Come si definisce la distanza tra due vettori di

attributi booleani o categoriali in uno spazio di m attributi (nel nostro caso che corrispondo a

clienti Coca Cola e clienti Pepsi)?

Context-Based Similarity Measures

(37)

Soluzione proposta:

Date le distanze tra tutte le coppie di attributi m nel dataset, si calcola iterativamente le distanze tra le sotto relazioni (ad esempio

clienti Coca Cola e clienti Pepsi);

poi si calcola di nuovo le distanze tra tutti gli

attributi.

Context-Based Similarity Measures

(38)

Executive summary

 Scopo e obiettivi

 Metriche di misura della distanza

 Applicazioni negli algoritmi di clustering per dati categoriali

(39)

Clustering Algorithms

 Partition-Based

k-Modes, Fuzzy k-Modes

 Hierarchical

ROCK, LIMBO

 Density-Based

CLICKS, HIERDENC

 Model-Based

AutoClass,SVM

(40)

 Simile al k-Means;

 a posto di usare la funzione media, usa la funzione moda;

 La moda rappresenta la massima frequenza con cui viene osservato

un determinato valore;

 Rimuove la limitazione sull’utilizzo dei soli dati numerici.

k-Modes

(41)

1. usa una misura di dissimilarità per gli oggetti categoriali invece che la distanza euclidea;

2. che sostituisce il punto medio del cluster con la moda;

3. viene utilizzato un metodo basato su frequenza per trovare i modi.

k-Modes vs. k-Means

(42)

1. Seleziona k modi iniziali, una per ogni cluster;

2. Assegna un oggetto al cluster con la moda più vicina, usando una misura di distanza.

Aggiornare la moda per ogni nuovo oggetto aggiunto al cluster;

k-Modes Algorithm

(43)

3. Dopo che tutti gli oggetti sono stati assegnati a un cluster, riverificare le dissimilarità con le

mode correnti. Se un oggetto si trova più vicino ad un altro cluster, esso viene riassegnato;

4. Ritornare al punto 1 finché nessun oggetto cambia cluster di appartenenza

k-Modes Algorithm

(44)

Qual è la misura di distanza usata?

k-Modes Algorithm

La Distanza di Hamming

(45)

Pro

 Veloce convergenza

 Distanza di Hamming veloce da calcolare

Contro

 Ottimi locali ma non globali

 Le soluzioni sono dipendenti dalla

selezione delle mode iniziali e dall’ordine degli oggetti

k-Modes Algorithm

(46)

 Simile al Fuzzy k-Means;

 Esattamente come il k-Modes usa la moda a posto della media;

 A posto di usare valori booleani (dentro o fuori), si usa un

grado di credenza compreso tra 0 e 1.

Fuzzy k-Modes

(47)

L’obiettivo del Fuzzy k-Means è di minimizzare, di volta in volta, la funzione costo cosi calcolata

Fuzzy k-Modes

𝐹 𝑤, 𝑋, 𝑍 = 𝑤_𝑙𝑖^𝛼

𝑛 𝑖=1 𝑘

𝑙=1

𝑑(𝑋_𝑖, 𝑍_𝑙)

con d(X_i, Z_l) misura di distanza calcolata

𝑑 𝑋_𝑖, 𝑍_𝑗 = 𝛿 𝑋_𝑖𝑙, 𝑍_𝑗𝑙

𝑘 𝑙=1

; 𝛿 𝑋_𝑖𝑙, 𝑍_𝑗𝑙 = 0, 𝑋_𝑖𝑙 = 𝑍_𝑗𝑙 1, 𝑋_𝑖𝑙 ≠ 𝑍_𝑗𝑙

(48)

Altri algoritmi basati sul partizionamento

 k-Prototypes

 Squeezer

 COOLCAT

Partition-Based algorithm

(49)

Clustering Algorithms

 Partition-Based

 Hierarchical

ROCK, LIMBO

 Density-Based

CLICKS, HIERDENC

 Model-Based

AutoClass,SVM

(50)

 Struttura dati ad albero;

 Ogni nodo rappresenta un cluster;

 Creazione del clustering

 Bottom-up (agglomerativo)

 Top-down (partitivo)

Hierarchical Clustering

(51)

 Clustering di tipo bottom-up;

 Vengono uniti i nodi in maniera tale

da aumentare la similarità intra-cluster;

 La misura della somiglianza è data

dal # di coppie di oggetti simili all’interno del cluster;

 Si definisce link tra due oggetti la somiglianza maggiore di una soglia fissata

ROCK

(52)

Siano tre oggetti A, B e C e sia:

 B e C sono vicini tra loro, e A e B sono collegati tra loro (anche se non vicini);

 Stesso cluster  gli oggetti hanno molti vicini in comune;

ROCK

(53)

Si definisco le funzioni sim(A, C) e link(A,B)

sim(A, C) è la funzione di somiglianza con valori di ritorno compresi tra 0 e 1 e può essere

qualsiasi metrica, anche euclidea.

link(A,B) definisce la somma dei vicini comuni a A e B

Neighbors & Links

(54)

Nel agglomerare i cluster, si considera la funzione di bontà

Goodness function

(55)

 Clustering di tipo top-down;

 Struttura ad albero;

 Ogni nodo (cluster) contiene statistiche degli oggetti;

una statistica è Entropy and Information Bottleneck FW

 I nuovi oggetti vengono aggiunti

 Trovando il miglior nodo

 Inserendo un nuovo nodo

LIMBO

(56)

LIMBO riassume gli oggetti nei cluster usando la Distributional Cluster Feature (DCF)

DCF (c) = (p (c), p (A | c)) P(c) è la probabilità di un cluster c

P(A | c) è la prob. cond. che il valore dell’attributo A sia afferente al cluster c

Distributional Cluster Feature

(57)

Altri algoritmi basati sull’approccio gerarchico

 COBWEB

Hierarchical algorithm

(58)

Clustering Algorithms

 Partition-Based

 Hierarchical

ROCK, LIMBO

 Density-Based

CLICKS, HIERDENC

 Model-Based

AutoClass,SVM

(59)

 Clustering dei sottospazi;

 Struttura dati : grafo;

 I nodi sono gli attributi;

 Gli archi sono le co- occorenze di valori in un oggetto

 Il grafo è modellato sui attributi

CLICKS

(60)

 Base probabilistica

 Nessun re-clustering richiesto

 Insensibilità all’ordine di inserimento dei dati

 Nessun parametro in input fornito dall’utente

 Trova cluster, sub-cluster e outliers

 Richiesto un raggio massimo di dissomiglianza

 Cluster partono dai sottospazi più densi del cubo

HIERDENC

(61)

Sia:

HIERDENC

 𝑆 𝑑𝑎𝑡𝑎𝑠𝑒𝑡 𝑐𝑜𝑛 𝑁 𝑟𝑖𝑔ℎ𝑒

 𝑋 = 𝑋₁, … , 𝑋_𝑚 ∈ 𝑆^𝑚

Definiamo l’ipercubo HIERCENC C(x₀, r)  S^m

𝐶 𝑥₀, 𝑟 = {𝑥: 𝑥 ∈ 𝑆^𝑚 𝑎𝑛𝑑 𝑑𝑖𝑠𝑡 𝑥, 𝑥₀ ≤ 𝑟 𝑎𝑛𝑑 𝑓𝑟𝑒𝑞 𝑥 > 0}

(62)

HIERDENC

𝐶 𝑥₀, 𝑟 = {𝑥: 𝑥 ∈ 𝑆^𝑚 𝑎𝑛𝑑 𝑑𝑖𝑠𝑡 𝑥, 𝑥₀ ≤ 𝑟 𝑎𝑛𝑑 𝑓𝑟𝑒𝑞 𝑥 > 0}

 dist(x, x₀) può essere qualsiasi funzione di distanza (anche di Hamming)

 freq(x) indica il numero di oggetti presenti in quelle coordinate (valori di attributi)

(63)

Density function

𝑑𝑒𝑛𝑠𝑖𝑡𝑦 𝑋 = _𝑐∈𝑋 𝑓𝑟𝑒𝑞(𝑐) 𝑆

Grazie alla funzione freq(x) possiamo dare la definizione density(x).

Tale funzione può essere vista come la probabilità che un oggetto casuale sia contenuto nell’ipercubo S

(64)

Clustering Categorial Data DMI – University of Catania

HIERDENC Algorithm

1. Si ottiene l’ipercubo C più denso con raggio r

Si controlla che 𝑑𝑒𝑛𝑠𝑖𝑡𝑦 𝐶 𝑥₀, 𝑟 > ¹_𝑆

r viene incrementato se C è vuoto o con solo un oggetto;

2. Crea una nuova foglia con r  1, partendo da una foglia esistente;

3. Tenta di aggregare le a foglia con un ipercubo più denso di raggio vicino ad r

4. Il cluster si espande, raccogliedo le celle dell’ipercubo

(65)

Altri algoritmi basati sull’approccio gerarchico

 Projected (Subspace) Clustering

 CACTUS

 STIRR

 CLOPE

 MULIC

Density-Based algorithm

(66)

Clustering Algorithms

 Partition-Based

 Hierarchical

ROCK, LIMBO

 Density-Based

CLICKS, HIERDENC

 Model-Based

AutoClass,SVM

(67)

 Gli oggetti seguono un modello;

 Il modello spesso corrisponde a una distribuzione statistica;

 L’utente specifica il modello

 Il modello può cambiare durante il clustering

 Alto grado di complessità

Model-Based

(68)

Clustering Categorial Data DMI – University of Catania

 Determina le classi ottimali in base alle distribuzioni precedenti;

 Analisi a priori sugli attributi;

 L’utente seleziona la distribuzione di probabilità;

 AutoClass fornisce una set di raggruppamenti

probabili; ogni oggetto è assegnato a un cluster in base alle distribuzioni di probabilità degli attributi.

 Iterativamente AutoClass indaga su diversi cluster

 L’iterazione finisce quando le distribuzioni di probabilità degli attributi non sono stabilizzati

AutoClass

(69)

Esempio

𝑋 = {𝑒𝑡à: 28; 𝑔𝑟𝑢𝑝𝑝𝑜 − 𝑠𝑎𝑛𝑔𝑢𝑖𝑔𝑛𝑜: 𝐴; 𝑝𝑒𝑠𝑜: 73𝑘𝑔}

Età e peso sono dati continui

Distribuzione normale (gaussiana)

Gruppo Sanguigno è un dato categoriale {A | B | 0}

Distribuzione di Bernoulli

AutoClass

(70)

SVM è un insieme di metodi di apprendimento supervisionato usati in pattern recognition per la classificazione

 Famiglia dei classificatori lineari

 Chiamati anche classificatori di massimo regime

 Per dati categoriali posso essere usati

SVM (Support Vector Machines)

(71)

 Approccio non supervisionato

 Assegna casualmente gli oggetti ai cluster

 Iterazione del calcolo dell’iperpiano di separazione

 L’algoritmo si arresta quando converge

nell’assegnazione degli oggetti ai cluster e dll’iperpiano

SVM for Categorical Data

(72)

Algoritmi basati sull’approccio Modellistico

 BILCOM Empirical Bayesian

Model-Based Algorithms

(73)

Caratteristiche richieste

 Velocità

 Parametri minimi

 Robustenza al rumore e outliers

 Indipendenza dall’ordine (dinserimento)

 Gestione della rindondanza

Conclusion

Tipologie di algoritmi

 Partizionale

 Gerarchico

 Basato sulla densità

 Basato sui modelli

La Misura di Distanza ha un ruolo di primaria importanza

(74)

Conclusion

 Abbinare gli algoritmi alle esigenze

dell’applicazione

 Algoritmo veloce



perdita di precisione del risultato

(75)

1. Bill Andreopoulos, Clustering Categorical Data, Data Clustering: Algorithms and Applications, CRC PRESS, 2013

2. S. Boriah V. Chandola V. Kumar, Similarity Measures for Categorical Data: A Comparative Evaluation,

University of Minnesota, 2008

3. D. Kim K. Lee D. Lee, Fuzzy clustering of categorical data using fuzzy centroids, KAIST, South Korea, 2004

References

(76)