Data Mining (parte teorica)

Formattazione del testo

T(x) = - + logδ x μ μ μ πk k k kk2^(x)

Dalle stime possiamo calcolare δk(x) = (x)δ δℓk 1 1−1 −1 −1 −1Σ Σ Σ ΣT T T T− = − con =x μ μ μ x μ μ μ k lk k l lk l2 2

Lda cerca di approssimare il classificatore di bayese il classificatore di bayes cerca di minimizzare il bayes rate. Il bayes rate è una misura generale di accuratezza e non mira a migliorare performance su determinate classi di un problema. LDA utilizza la stessa soglia del classificatore di bayes nel caso di k= 2 e quindi 0.5. Volendo si può ridurre la soglia se si ha a che fare con uno sbilanciamento delle numerosità per ogni classe.

QDA Σ assume che ogni classe ha la sua matrice di varianza covarianza riferita alla k-esima classe. Quindi si ha che x verrà assegnata a k per il valore più alto di:1 1−1T Σ Σ(x) = − ( − ) ( − ) −

log ∣ ∣ + logδ x μ x μ πk k k k kk2 21 1 1−1 −1 −1Σ Σ Σ ΣT T T= − + − − log ∣ ∣ + logx x x μ μ μ πk k k kkk k k2 2 2

Nel QDA è necessario calcolare una matrice di varianza-covarianza per ogni classe avendo così un numero di+ 1)/2coefficienti da calcolare pari a . In LDA la matrice di varianza covarianza è considerata inKp(pcomune tra tutti le classi K, coefficienti sono .KpLDA è meno flessibile di QDA ed ha quindi minore varianza. Ma c'è un trade-off: se l'assunto di LDA che leclassi condividano la stessa matrice di varianza-covarianza è totalmente errato, c'è un bias elevato. E'migliore lda quando ci sono poche osservazioni nel training e ridurre la variabilità è cruciale.Qda si consiglia se il training è molto grande o se l'assunzione di una matrice di covarainza comune per leclassi è

chiaramente insostenibile.

Data Mining 10

Confronto

Sia la regressione logistica che l'analisi descriminante lineare individuano linee di confine lineari. L'unica differenza è da come sono trovati i parametri di interesse nei due modelli. Nella regressione logistica i parametri beta vengono stimati con la massima verosimiglianza. Nell'LDA c0 e c1 sono calcolati usando le stime di media e varianza della distribuzione normale. LDA assume che le osservazioni provengano da una normale con una comune covf. Se tali ipotesi sono soddisfatte, LDA è più affidabile di regressione logistica, altrimenti si invertono.

KNN è un approccio non parametrico dove non vengono fatte assunzioni sulla forma della linea di decisione. È meglio degli altri due quando le linee di confine sono altamente non lineari. Non permette l'interpretazione delle variabili d'interesse più significative.

QDA è un compromesso tra KNN e LDA/reglog. Le linee di decisione sono quadratiche.

possono essere adatte ad un numero maggiore di problemi differentemente di quanto succede per la linea di decisione di bayes è linea di decisione di X1 e X2 sono generate da una lineare bayes è lineare tstudent (simile a normale ma punti più lontani dalla media) le 2 classi sono bilanciate le 2 classi sono bilanciate linea di decisione di bayes è NON le osservazioni all'interno di lineare ogni classe sono non le osservazioni correlate e distribuite all'interno di ogni le 2 classi sono bilanciate casualmente come una classe hanno Ogni classe ha propria media normale correlazione -0.5 Ogni classe ha propria media Ogni classe ha propria media

Data Mining 11 linea di decisione di bayes è linea di decisione di bayes linea di decisione di bayes è NON lineare è NON lineare NON lineare le 2 classi sono bilanciate le 2 classi sono bilanciate le 2 classi sono bilanciate Dati sono generati da una dati sono generati con dati dati sono generati con dati

osservazioni che condividono caratteristiche simili sulla base di precisi criteri

Un metodo di unsupervised learning - non sono disponibili esempi di come i dati dovrebbero essere raggruppati

Un metodo di data exploration - uno strumento per individuare patterns di interesse

Bisogna organizzare i dati in modo tale che ci sia alta somiglianza entro in gruppi e bassa tra gruppi.

Il clustering è una divisione dei dati in gruppi di oggetti simili. Ogni gruppo ( = cluster) consiste in oggetti che sono simili tra loro e dissimili con oggetti di altri gruppi.

La distanza (similarità e dissimilarità) tra O1 e O2 è un numero reale denominato . Proprietà:

Non-negativity: D(O O1 2≥0

Reflectivity: D(x, y)= 0 if and only if x = y

Symmetry: D(x, y) = D(y, x) ≥ 0

Triangle inequality: D(x, z) ≤ D(z, y) + D(x, y)

Se la seconda proprietà di riflettività non è soddisfatta, D è chiamata pseudo-metrica.

Una misura di dissimilarità è una

funzione tale per cui se e solo se x è meno simile di y

f(x, y) = f(w, z) che w di z (misura pair-wise)

Data Mining 13

Distanza euclidea

Correlazione lineare di Pearson ha valori sempre compresi tra -1 e 1. È una misura di similarità e può essere trasformata in misura di dissimilarità nel seguente modo:

ρ(x, y) = 1 - ρ(x, y)

Σ(x - ˉx)(y - ˉy) / √(Σ(x - ˉx)^2 * Σ(y - ˉy)^2)

Hierarchical Algorithms: Crea una decomposizione gerarchica dei nostri oggetti

Partitional Algorithms: Costruisce una serie di partizioni e ne valuta la qualità

Hierarchical Algorithms

Per valutare gli approcci gerarchici viene utilizzato il dendrogramma. La similarità tra due oggetti in un dendrogramma è rappresentata dall'altezza del più basso nodo interno che condividono.

Bottom-up (agglomerativo): Ogni osservazione è considerata un cluster,

1. Allo step successivo la migliore coppia di osservazioni (minor distanza) finisce dentro un nuovo cluster. Ripetuto fino a che si ha un solo cluster.
2. Top-Down (divisivo): Tutte le osservazioni sono considerate come un unico cluster. Si individua un metodo di separazione e si va avanti fino a che non si ha n cluster di una sola osservazione l'uno.
3. Come definire la distanza tra due cluster? δ = × , ∈
4. Assumiamo essere la matrice di dissimilarità tra due oggetti due cluster con

Data Mining 14

Complete linkage: la distanza tra clusters è determinata dalla più grande distanza tra ogni coppia nei due differenti clusters. ( , ) = max ( ( , ) ∈ )d C C d c c D1 2 1i 2j

Single linkage: la distanza tra clusters è determinata dalla più piccola distanza tra ogni coppia nei due differenti clusters ( , ) = min ( ( , ) ∈ )d C C d c c D1 2 1i 2j

Group average linkage: la distanza è determinata dalla distanza media tra

tutte le coppie nei due clusters n n1 ∑ ∑, ) = ∣ ∣ ∣ ∣ ( , ) ∈d(C C C C d c c D1 2 1 2 1i 2j∣ ∣ ∣ ∣C C1 2 i=1 j=1

Ad ogni step vengono uniti i due gruppi dalla cui fusione deriva il minimo incremento possibile della devianza

intra: p pn n∑ ∑ ∑ ∑2 2= ( − ˉ ) = ( − ˉ )DEV x x x xT is s is ss=1 i=1 i=1 s=1

è la media del gruppo. Tale devianza può essere cojmposta come segue:

xs devinanza intra-gruppo riferita alle p variabili cong p ni∑ ∑ ∑ ˉ2 riferimento al gruppo k, dove è la media dellax= ( − ˉ )DEV x x s,kIN is s,k variabile s con riferimento al gruppo k.s=1 i=1k=1 Devianza tra i gruppi.p g∑ ∑ 2= (xˉ − ˉ )DEV x nOU T s,k s ks=1 k=1= + . Nel passare da k+ 1 gruppi a k gruppi la devianza intra aumenta mentre

DEV DEV DEVT IN OU Tquella tra i gruppi diminuisce. Ad ogni passo del metodo di ward si aggregano i gruppi per cui vi è il minor incremento della devianza

intra-gruppo.

Partitional Clustering

Bisogna fissare il numero di clusters K

K può essere interpretato come il punto di taglio del dendogramma in un cluster gerarchico

Data Mining 15, … , {1, … ,Kmeans approach: Definiamo un insieme di gruppi contenenti le osservazioni .

C1, C2, … , Ck = {1, … ,n}

Questo insieme di gruppi deve soddisfare le seguenti proprietà:

C1 ∩ C2 ∩ … ∩ Ck = ∅

In Kmeans una buona suddivisione delle osservazioni è quella per cui la variazione intra cluester, è

minimize (Wk{∑Kminimize (Wk)}) minima.

Wk = ∑Ck{∑(x-x')^2}

Una delle misure più utilizzate è la distanza euclida quadratica:

minimize (∑∑∑(x-x')^2)

K1, … , K' ∈ C1, … , Ck

Kmeans, una volta definito K, si procede come segue:

1. Assegnare casualmente ad ogni osservazione un valore da 1 a K