Come calcolare il valore soglia per gli attributi numerici nell'algoritmo C4.5 di Quinlan?

Question

Sto cercando di scoprire in che modo l'algoritmo C4.5 determina il valore soglia per gli attributi numerici. Ho cercato e non riesco a capire, nella maggior parte dei casi ho trovato queste informazioni:

I campioni di addestramento vengono prima ordinati sui valori dell'attributo Y in considerazione. Ci sono solo un numero finito di questi valori, quindi denotiamoli nell'ordine ordinato come {v1, v2, ..., vm}. Qualsiasi valore di soglia compreso tra vi e vi + 1 avrà lo stesso effetto di dividere i casi in quelli il cui valore dell'attributo Y si trova in {v1, v2, ..., vi} e quelli il cui valore è in {vi + 1, vi + 2, ..., vm}. Ci sono quindi solo m-1 possibili divisioni su Y, che dovrebbero essere esaminate sistematicamente per ottenere una divisione ottimale.

È normale scegliere il punto medio di ciascun intervallo: (vi + vi + 1)/2 come soglia rappresentativa. C4.5 sceglie come soglia un valore minore vi per ogni intervallo {vi, vi + 1}, piuttosto che il punto medio stesso.

Sto studiando un esempio di Play/Dont PLAY (value table) e non capiscono come si ottiene il numero 75 (tree generated) per l'umidità attributo quando lo stato è di sole in quanto i valori di umidità al stato solare sono {70,85,90,95}.

Qualcuno sa?

Answer 1

Come implica l'immagine dell'albero generato, si considerano gli attributi in ordine. Il tuo 75 esempio appartiene a outlook = sunny branch. Se filtri i tuoi dati in base a outlook = soleggiato, ottieni la seguente tabella.

outlook temperature humidity windy play 
sunny 69   70   FALSE yes 
sunny 75   70   TRUE yes 
sunny 85   85   FALSE no 
sunny 80   90   TRUE no 
sunny 72   95   FALSE no 

Come si può vedere, la soglia per l'umidità è "< 75" per questa condizione.

j4.8 è successivo a ID3 algorithm. Usa il guadagno di informazioni e l'entropia per decidere la migliore divisione. Secondo wikipedia

The attribute with the smallest entropy 
is used to split the set on this iteration. 
The higher the entropy, 
the higher the potential to improve the classification here. 

Answer 2

Non sono del tutto sicuro di J48, ma assumendo la sua base a C4.5 sarebbe calcolare il guadagno per tutte le possibili scissioni (vale a dire, in base ai valori possibili per la funzione). Per ogni divisione, calcola il guadagno di informazioni e sceglie la divisione con il maggior guadagno di informazioni. Nel caso di {70,85,90,95} calcolerebbe il guadagno di informazioni per {70 | 85,90,95} contro {70,85 | 90,95} contro {70,85,90 | 95} e scegli il migliore.

Il libro di Quinlan sul libro C4.5 è un buon punto di partenza (https://goo.gl/J2SsPf). Vedi in particolare pagina 25.