Data Mining 1 - Appunti

K NEAREST NEIGHBORS

I classificatori DecisionTree e Rule-based sono esempi di EAGER LEARNERS, perché sono strutturati per apprendere un modello che mappa attributi di input in un'etichetta di classe appena sono disponibili i dati di training. Una strategia opposta sarebbe ritardare il processo di modellazione dei dati di training fino a quando non sarà necessario classificare esempi di test.

Le tecniche che utilizzano questa strategia sono noti come LAZY LEARNERS. Un esempio è il classificatore Rote, che memorizza tutti i dati di training ed esegue la classificazione solo se gli attributi dell'istanza di test corrispondono esattamente con uno degli esempi di training. Chiaramente, ci saranno records di test che non saranno mai classificati per mancanza di corrispondenza.

Un modo per rendere questo approccio più flessibile è trovare tutti gli esempi di training che sono relativamente simili agli attributi dell'esempio di test. Questi esempi

Chiamati NEAREST NEIGHBORS, sono usati per determinare la classe dell'esempio di test. Un classificatore nearest-neighbor rappresenta ogni esempio come un punto in uno spazio d-dimensionale, dove d è il numero di attributo. Dato un esempio di test, si calcola la sua "prossimità" con il resto dei punti nel training set. I k-nearest neighbors di un dato esempio z si riferiscono ai k punti più "vicini" con z. In figura, possiamo vedere i vicini (1-, 2-, 3-nearest neighbors) di un punto localizzato al centro del cerchio. Il punto viene classificato sulla base dell'etichetta dei suoi vicini. Nel caso che i vicini abbiano più di un'etichetta, viene assegnata quella di maggioranza del vicinato. Nel caso in cui non abbiamo una classe di maggioranza, possiamo scegliere randomicamente (o attuare delle politiche diverse). Nel caso con k=3 e pesi uniformi, il punto viene classificato (supponendo che sia della classe negativa) come positivo, perché ha...

unitaria.

CARATTERISTICHE Nearest-Neighbor

(Potremmo dire che funziona bene quando abbiamo una determinata concentrazione minima di punti nel vicinato)- Una classificazione Nearest-Neighbor fa parte di una tecnica più generale chiamata apprendimento instance-based, che usa specifiche istanze di training per fare previsioni senza mantenere un'astrazione/modello derivato dai dati.

- I lazy learners non richiedono tempo per la costruzione di un modello, però sono costosi per il calcolo delle prossimità quando bisogna etichettare un esempio di test. Gli eager learners spendono risorse computazionali per la costruzione di un modello, ma classificano velocemente nuovi records.

- I classificatori Nearest-Neighbor fanno le predizioni sulla base di informazioni locali, mentre i decision tree (e i classificatori rule-based) tentano di trovare un modello globale adatto all'intero spazio di input. Quindi, poiché le decisioni di classificazione sono fatte localmente, i

classificatori nearest-neighbor sonoabbastanza suscettibili al rumore (per piccoli valori di k)- I classificatori nearest-neighbor possono produrre decision boundaries di forma arbitraria, i qualiforniscono una rappresentazione del modello più flessibile rispetto al decision tree spesso vincolato dadecision boundaries rettilinei. Aumentare il k potrebbe ridurre la variabilità dei decision boundaries.

- I classificatori nearest-neighbor possono produrre predizioni errate a meno che non vengano definitemisure di prossimità appropriate e di preprocessare i dati. Ad esempio, se volessimo classificare ungruppo di persone sulla base dell’altezza (misurata in metri) e del peso (in libbre), vedremmo chel’attributo altezza ha una bassa variabilità nel range 1.5m, 1.85m, mentre il peso può variare da 90lb a250lb. Se non viene presa in considerazione la scala degli attributi, la misura di prossimità può esseredominata dai pesi.

PEBLS

“olistica” su tutti gli attributi, quindi anche se uno ècasuale entrerà comunque in gioco. A volte il casuale influirà poco, alle volte di più e potrebbe buttarevicino punti lontani e viceversa. Il DecisionTree invece non si fida di nessuno e va a verificare se servonoa qualcosa gli attributi prima di “usarli”. Morale: il KNN non è robusto alle variabili poco informative eridondanti, cioè a dati correlati (in questo caso l’attributo ridondante vale 2 volte); inoltre gli outlierspossono far diventare i vicini inaffidabili.Quindi, la dimensionalità del dataset è un problema solo per il knn.Il Preprocessing del KNN sarà: eliminazione features categoriche, e normalizzazione/standardizzazionedelle variabili continue. 28/****** MISURE DI SIMILARITÀ E DISSIMILARITÀ ********\Definizione – Similarity: la similarità tra due oggetti è una misura numerica del grado con

dati con distribuzioni normali. Distanza euclidea e correlazioni utili per dati densi come le timeseries o punti a due dimensioni. Jaccard e cosine similarity utili per dati sparsi come documenti.

29DM1 – PARTE4 – ASSOCIATION ANALYSIS

L'analisi del carrello della spesa nasce quando ci si è resi conto che sarebbe stato interessante osservare cosa veniva acquistato da ogni persona, quindi cosa ci fosse in ogni cestino della spesa; quindi guardare le abitudini d'acquisto dei clienti trovando associazioni e correlazioni tra diversi articoli acquistati dai clienti. Questo ha portato allo sviluppo della Association Analysis.

Association Analysis: è l'analisi fatta per trovare relazioni interessanti e nascoste nei dati, per esempio trovare dei prodotti che vengono spesso acquistati insieme. Oltre ad applicazioni con fini economici come quella del supermercato, l'Association Analysis è utile anche nelle applicazioni biologiche.

delletelecomunicazioni (dove vediamo ogni cliente come una transazione contenente un set di chiamate),fenomeni atmosferici (dove vediamo ogni intervallo di tempo, ad esempio un giorno, come unatransazione contenente un set di eventi osservati come pioggia, neve, …) oppure in campo medico (pervedere se ci sono gruppi di geni con determinate variazioni spesso presenti in concomitanza con una certamalattia).

MARKET BASKET ANALYSIS

Dato un database di customer transactions, dove ogni transazione è un insieme di oggetti, si cerca ditrovare quali gruppi di oggetti vengono frequentemente comprati insieme. Il problema è di difficilecomputazione perché il numero di combinazioni possibili tra i prodotti è molto elevato. L’obiettivo dellaMarket Basket Analysis è estrarre informazioni dai comportamenti d’acquisto dei clienti. Le informazioniutili possono suggerire nuovi layouts dello store (quali prodotti sistemare vicini, diversi assortimenti,