Please enable JavaScript.
Coggle requires JavaScript to display documents.
Other Classification Error - Coggle Diagram
Other Classification
Error
Rule Based
Classifier
-
Mutually exclusive rules
classificatore contiene regole mutually exclusive
se le regole sono indipendenti tra loro
ogni record è coperto da almeno una regola
Exhaustive rules
classificatori hanno una copertura esaustiva se tiene conto di ogni possibile combinazione dei valori degli attributi
ogni record è coperto da almeno una regola
Semplificazione Regola
non più mutually exlusive
ordina il rule set
Rule ordering scheme
rule-based: classificate sulla loro qualità
Class-based: regole che appartengono alla stessa classe appaiono assieme
assegna un record alla classe per la quale vengono attivate la maggiore delle regole
non più esaustive
usa default class
Costruzione
regole di classificazione
Metodo diretto
estrae regole direttamente dai dati
RIPPER, CN2, Holte's 1R
Metodo Indiretto
estrae regole da altri modelli di classificazione
(decision trees, neural networks,etc...)
C4.5 rules
Metodo Diretto:
copertura sequenziale
inizi da una regola vuota
crei una regola usando
la funzione Learn One Rule
rimuovi training records
coperti dalla regola
ripeti gli ultimi due
fino allo stopping criterion
Learn One Rule
estrae una regola di classificazione che copre tutti gli esempi positivi e nessuno degli esempi negativi
2 strategie comuni
general to specific
specific to general
Aspetti copertura sequenziale
Rule Growing
in Ripper
-inizi da una regola vuota
-agginungi congiunzioni che massimizzano
misure FOIL's information gain
FoilGain(R0,R1)=p1(log p1/(p1+n1) - log p0/(p0+n0)
log base 2
Instance Elimination
Rule Evaluation
accuracy nc/n
laolace nc+1/n+k
M-estimate nc+kp/n+k
nc= numero di istanze correttamente classificate
k è il numero di classi
p è 1/k se le distribuzione è uniforme
Stopping Criterion
Calcolo guadagno
se non significante, scarto la nuova regola
Rule Pruning
similare al post pruning
dei decision tree
Reduced Error Pruning
rimuovi uno delle congiunzioni
nella regola
compara il tasso di errore
nel validation set prima e dopo il pruning
se l'errore migliora, pruna
la congiunzione
Metodo diretto:
RIPPER
basato sulla copertura sequenziale
-
per problemi a 2 classi
scegli una delle classi come positiva,
l'altra negativa
per problemi multiclasse
ordina le classi in base a increasing class prevalence
impara la rule set per le classi più piccole prima,tratta il resto come classi negative
ripeta con le prossime classi più piccole come positive
growing rule
regola vuota
aggiungi congiunzioni
(vedi FOIL)
pruni la regola immediatamente
usando errore di pruning incrementale
misura di pruning v=(p-n)/(p+n)
metodo di pruning: cancelli la congiunzione la quale eliminazione massimizza v
Metodi Indiretti
possibile trasformare decision tree in un set di regole
Nearest Neighbour Classifier
richiede 3 cose:
il set di record registrati
metrica di distanza per analizzare la distanza tra record
valore di k, n° di vicini da recuperare
per classificare un record sconosciuto:
calcola distanza record di training
identifica i k più vicini
usa etichette di classe del più vicino vicino per determinare l'etichetta di classe di record sconosciuti
se k è troppo piccolo, è sensibile ai noise points
se k è troppo grande, il vicinato può includere punti di altre classi
Scaling issues:
gli attributi potrebbero dover essere scalati per prevenire che le misure di distanza vengano dominate da uno degli attributi
caratteristiche
non richiede costruzione di un modello
rappresentazione modello più flessibile
richiede una misura di prossimità
fa predizioni basata su informazioni locali ed è
suscettibile al rumore
Produce predizioni sbagliate se la scala degli attributi non è presa in considerazione
la classificazione può essere costosa senza opportune strutture dati
Naive Bayes
Classifier
teorema di bayes:
P(Y|X)=P(X|Y)P(Y)/P(X)
naive bayes assumption:
se X1 e X2 conditionally indipendent
P(X1,X2|Y)=P(X1|Y)P(X2|Y)
possiamo stimare P(Xj|Yj)
dai dati di train
nuovi record sono classificati in Yj se P(Yj) PIi P(Xi|Yi) è massimale
stimare probabilità
per valori continui
discretizzazione
probability density estimation
problemi
se una probabilità condizionale è 0, tutta la espressione diventa 0
bisogno di altre stime di prob cond oltre a semplici frazioni
per esempio stime di laplace