Pratical Maching Learning 1

Che cos'è un concetto? 

Quattro stili fondamentali di apprendimento appaiono nelle applicazioni di data mining. Nell'apprendimento della classificazione, lo schema di apprendimento è presentato con un insieme di esempi classificati da cui "si prevede che impari un modo" di classificare esempi invisibili. Nell'assollare l'associazione, si cerca qualsiasi associazione tra le caratteristiche, non solo quelle che prevedono un valore di classe particolare. Nel raggruppamento, sono ricercati gruppi di esempi che appartengono insieme. Nella previsione numerica, il risultato da prevedere non è una classe discreta ma una quantità numerica. Indipendentemente dal tipo di apprendimento coinvolto, chiamiamo la cosa da imparare 'il concetto e l'output' prodotto da un sistema di apprendimento 'la descrizione concettuale.

 La maggior parte degli esempi del Capitolo 1 sono problemi di classificazione. I dati meteorologici (tabelle 1.2 e 1.3) presentano un insieme di giorni insieme ad una decisione per ognuno su come giocare o no. Il problema è imparare a classificare i nuovi giorni come gioco o non giocare. Dato i dati delle lenti a contatto (tabella 1.1), il problema è quello di imparare a decidere su una raccomandazione di un obiettivo per un nuovo paziente o più precisamente, in quanto ogni possibile combinazione di attributi è presente nei dati, il problema è imparare un modo di Riassumendo i dati forniti. Per gli iridi (Tabella 1.4), il problema è quello di imparare a decidere se un nuovo fiore dell'iride è setosa, versicolor o virginica, data la sua lunghezza e larghezza sepalese e la lunghezza e la larghezza del petalo. Per i dati relativi ai negoziati del lavoro (tabella 1.6), il problema è "decidere se" un nuovo contratto sia accettabile o no, sulla base della sua durata; Aumento salariale nel primo, secondo e terzo anno; L'adeguamento del costo della vita; e così via.

L'apprendimento della classificazione è talvolta chiamato supervisione perché, in un certo senso, il metodo opera sotto la supervisione fornendo l'esito effettivo per ciascuno degli esempi di allenamento: il gioco o non giocare giudizio, la raccomandazione dell'obiettivo, il tipo di iride, L'accettabilità del contratto di lavoro. Questo risultato è chiamato la classe dell'esempio. Il successo dell'apprendimento della classificazione può essere giudicato provando la descrizione del concetto che viene appreso su un insieme indipendente di dati di prova per i quali le vere classificazioni sono note ma non messe a disposizione della macchina. Il tasso di successo sui dati di prova fornisce una misura oggettiva di quanto sia stato appreso il concetto. In molte pratiche applicazioni di data mining, il successo viene misurato in modo più soggettivo in termini di come accettabile la descrizione appresa - come le regole o l'albero decisionale - siano a un utente umano. 

La maggior parte degli esempi del Capitolo 1 può essere utilizzata altrettanto bene per l'apprendimento associativo, in cui non esiste una classe specificata. Qui, il problema è quello di scoprire qualsiasi struttura nei dati "interessanti". Alcune regole di associazione per i dati meteo sono state fornite nella Sezione 1.2. Le regole di associazione differiscono dalle regole di classificazione in due modi: possono "predire" qualsiasi attributo, non solo la classe, e possono prevedere più valori di un attributo alla volta. A causa di questo ci sono molto più regole di associazione rispetto alle regole di classificazione, e la sfida è evitare di essere inondati da loro. Per questo motivo, le regole di associazione sono spesso limitate a quelle che si applicano ad un certo numero minimo di esempi - ad esempio l'80% del set di dati - e che hanno un livello preciso minimo di precisione dire 95% accurate. Anche allora, "ci sono di solito" un sacco di essi, e devono essere esaminati manualmente per determinare se sono significativi o no. Le regole di associazione di solito coinvolgono solo attributi non numerici: in questo modo normalmente non si cercano regole di associazione nel dataset dell'iride.

 Quando non esiste una classe specificata, il raggruppamento viene utilizzato per raggruppare elementi che sembrano cadere naturalmente insieme. Immagina una versione dei dati dell'iride in cui il tipo di iride viene omesso, come nella Tabella 2.1. Allora è probabile che le 150 istanze rientrino in cluster naturali corrispondenti ai tre tipi di iridi. La sfida è trovare questi cluster e assegnare le istanze a loro e 'per poter assegnare' nuove istanze anche ai cluster. Può essere che uno o più tipi di iride si dividono naturalmente in sottotipi, nel qual caso i dati esporranno più di tre cluster naturali. Il successo del clustering è spesso misurato soggettivamente in termini di quanto utile il risultato sembra essere per un utente umano. Può essere seguita da una seconda fase dell'apprendimento di classificazione in cui vengono apprese regole che forniscono una descrizione intelligibile di come occorre inserire nuovi casi nei cluster.

 La previsione numerica è una variante di apprendimento di classificazione in cui l'esito è un valore numerico piuttosto che una categoria. Il problema delle prestazioni della CPU è un esempio. Un altro, illustrato nella Tabella 2.2, è una versione dei dati meteo in cui ciò che si prevede non è giocare o non giocare, ma è il tempo (in minuti) da giocare. Con i problemi di previsione numerica, come per le altre situazioni di apprendimento in macchina, il valore predittivo per le nuove istanze è spesso di "meno interesse" rispetto alla struttura della descrizione che viene appreso, espresso in termini di attributi importanti e come si riferiscono alla Risultato numerico.

 Cosa c'è in un esempio?

L'input di uno schema di apprendimento macchina è un insieme di istanze. Queste istanze sono le cose che devono essere classificate, associate o raggruppate. Anche se fino ad ora li abbiamo chiamati esempi, ora usiamo le istanze di termine più specifiche per fare riferimento all'input. Ogni istanza è un esempio individuale e indipendente del concetto da imparare. Inoltre, ognuno è caratterizzato dai valori di un insieme di attributi predeterminati. Questo è stato il caso in tutti i set di dati del campione descritti nell'ultimo capitolo (problemi di tempo, contatti, iride e problemi di negoziazione del lavoro). Ogni dataset è rappresentato come una matrice di istanze rispetto agli attributi, che in termini di database è una relazione singola o un file piatto.

Esprimere i dati di input come un insieme di istanze indipendenti è di gran lunga la situazione più comune per l'estrazione pratica dei dati. Tuttavia, è un modo piuttosto restrittivo di formulare problemi, e 'vale la pena spendere' un po' tempo per rivedere il motivo. I problemi spesso implicano relazioni tra oggetti anziché istanze separate e indipendenti. Supponiamo che, per prendere una situazione specifica, è dato un albero genealogico e vogliamo imparare la sorella di concetto. Immagina il tuo albero genealogico, con i tuoi parenti (ei loro generi) collocati nei nodi. Questo albero è l'ingresso al processo di apprendimento, insieme ad un elenco di coppie di persone e un'indicazione di se sono sorelle o meno.

La Figura 2.1 mostra una parte di un albero genealogico, al di sotto di quale sono due tavole che ognuna definiscono la sorella in un modo leggermente diverso. Un sì nella terza colonna dei tavoli significa che la persona nella seconda colonna è una sorella della persona nella prima colonna (è solo una decisione arbitraria che abbiamo fatto per impostare questo esempio).

 La prima cosa da notare è che ci sono molti nodi nella terza colonna della tabella a sinistra, perché ci sono 12 persone e 12 ¥ 12 = 144 coppie di persone in tutto e la maggior parte delle coppie di persone non sono sorelle . La tabella a destra, che fornisce le stesse informazioni, registra solo le istanze positive e suppone che tutti gli altri siano negativi. L'idea di specificare solo esempi positivi e di adottare un presupposto permanente che il resto sia negativo si chiama l'assunzione del mondo chiuso. È spesso assunto negli studi teorici; Tuttavia, non è di grande utilità pratica nei problemi della vita reale perché raramente coinvolgono mondi "chiusi" in cui è possibile essere certi che tutti i casi siano coperti.

 Né la tabella in figura 2.1 è di qualsiasi uso senza l'albero genealogico stesso. Questo albero può anche essere espresso sotto forma di una tabella, la cui parte è illustrata nella Tabella 2.3. Ora il problema è espresso in termini di due rapporti. Ma queste tabelle non contengono gruppi indipendenti di istanze perché i valori nelle colonne Nome, Parent1 e Parent2 della relazione sorella si riferiscono a righe della relazione albero genealogico. Possiamo farli in un singolo insieme di casi crollando le due tabelle nella singola tabella 2.4

  Finalmente siamo riusciti a trasformare il problema relazionale originale in forma di istanze, ognuno dei quali è un esempio individuale e indipendente del concetto da imparare. Naturalmente, le istanze non sono realmente indipendenti - ci sono molte 'relazioni tra diverse righe della tabella'! - ma sono indipendenti per quanto riguarda il concetto di sorellanza. La maggior parte dei programmi di apprendimento in macchina continuerà ad avere difficoltà a trattare questo tipo di dati, come vedremo nella sezione 3.6, ma almeno il problema è stato ricondotto nella giusta forma. Una regola semplice per la sorella di relazione è la seguente:

 If second person’s gender = female
    and first person’s parent1 = second person’s parent1
 then sister-of = yes
  
 Questo esempio mostra come è possibile prendere una relazione tra diversi nodi di un albero e ricondurla in un insieme di istanze indipendenti. In termini di database, si prendono due relazioni e uniscono loro insieme per fare uno, un processo di appiattimento che è tecnicamente chiamato denormalizzazione. È sempre possibile farlo con qualsiasi (finito) insieme di rapporti (finiti).

 La struttura della tabella 2.4 può essere utilizzata per descrivere qualsiasi rapporto tra due persone-nonni, due cugini due volte rimossi e così via. Le relazioni tra più persone richiederebbero una tabella più ampia. Le relazioni in cui il numero massimo di persone non è specificato in anticipo costituiscono un problema più grave. Se vogliamo imparare il concetto di famiglia nucleare (genitori e figli), il numero delle persone coinvolte dipende dalla dimensione della più grande famiglia nucleare e sebbene possiamo indovinare ad un massimo ragionevole (10-20), l'effettivo Il numero potrebbe essere trovato solo scansionando l'albero stesso. Tuttavia, dato un insieme finito di rapporti finiti potremmo, almeno in linea di principio, formare una nuova "superrelazione" che contenesse una fila per ogni combinazione di persone e ciò sarebbe sufficiente per esprimere qualsiasi rapporto tra le persone, non importa quanti siano stati coinvolti . I costi di calcolo e di stoccaggio sarebbero comunque proibitivi.

 Un altro problema con la denormalizzazione è che produce regolarità apparenti nei dati completamente spuri e sono in realtà solo riflessi della struttura del database originale. Ad esempio, immagina un database di supermercati con una relazione per i clienti e i prodotti acquistati, uno per i prodotti e il loro fornitore e uno per i fornitori e il loro indirizzo. Denormalizzare questo produce un file piatto che contiene, per ogni istanza, il cliente, il prodotto, il fornitore e l'indirizzo del fornitore. Uno strumento di estrazione del database che cerca la struttura nel database può venire con il fatto che i clienti che comprano birra anche acquistare chip, una scoperta che potrebbe essere significativo dal punto di vista del gestore del supermercato. Tuttavia, può anche venire con il fatto che l'indirizzo del fornitore può essere previsto esattamente dal fornitore, una "scoperta" che non impressionerà affatto il gestore del supermercato. Questo fatto mascherata come una scoperta significativa dal file piatto, ma è presente esplicitamente nella struttura del database originale.

 Molti problemi computazionali astratti coinvolgono relazioni non finite, anche se chiaramente qualsiasi insieme effettivo di istanze di input deve essere finito. Concetti come l'antenato-di coinvolgere percorsi arbitrariamente lunghi attraverso un albero e anche se la razza umana, e quindi il suo albero genealogico, può essere finita (anche se prodigiosamente grande), molti problemi artificiali generano dati veramente infiniti. Anche se può sembrare astruso, questa situazione è la norma in settori quali l'elaborazione di liste e la programmazione logica ed è affrontata in una subdisciplina di apprendimento macchina chiamata programmazione logica induttiva. Gli scienziati di computer usano solitamente ricorsioni per affrontare situazioni in cui il numero di casi possibili è infinito. Per esempio,   

If person1 is a parent of person2
  then person1 is an ancestor of person2
 
If person1 is a parent of person2
   and person2 is an ancestor of person3
  then person1 is an ancestor of person3
 
è una semplice definizione ricorsiva di antenato che funziona non importa quanto distanzialmente si abbiano due persone. Le tecniche di programmazione logica induttiva possono imparare regole ricorsive come queste da un insieme finito di istanze come quelle della tabella 2.5.

 I gravi inconvenienti di tali tecniche, però, sono che non si occupano di dati rumorosi e tendono ad essere così lenti da essere inutilizzabili su qualsiasi cosa, tranne i piccoli set di dati artificiali. Non sono coperti da questo libro; Vedere Bergadano e Gunetti (1996) per un trattamento completo.

In sintesi, l'input di uno schema di data mining è generalmente espresso come una tabella di istanze indipendenti del concetto da imparare. A causa di questo, è stato suggerito, disparagingly, che dobbiamo veramente parlare di file mining piuttosto che database mining. I dati relazionali sono più complessi di un file piatto. Un insieme finito di rapporti finiti può sempre essere ricostruito in 'una singola tabella', anche se spesso a un costo enorme nello spazio. Inoltre, la denormalizzazione può generare regolarità spurie nei dati e è essenziale verificare i dati per tali artefatti prima di applicare un metodo di apprendimento. Infine, concetti potenzialmente infiniti possono essere affrontati da regole di apprendimento che sono ricorsive, anche se questo è al di là del campo di applicazione di questo libro.  

Cosa c'è in un attributo? What’s in an attribute?

 Ogni singola istanza indipendente che fornisce l'input per l'apprendimento automatico è caratterizzato dai suoi valori su un insieme fisso e predefinito di funzionalità o attributi. Le istanze sono le righe delle tabelle che abbiamo mostrato per le condizioni di tempo, le lenti a contatto, l'iride e le prestazioni della CPU e gli attributi sono le colonne. (I dati relativi ai negoziati del lavoro erano un'eccezione: abbiamo presentato questo con istanze in colonne e attributi in righe per ragioni spaziali.)
L'uso di un insieme fisso di funzionalità impone un'ulteriore restrizione sui tipi di problemi generalmente presi in considerazione nell'esportazione pratica dei dati. Che cosa succede se istanze differenti presentano caratteristiche diverse? Se i casi erano veicoli di trasporto, allora il numero di ruote è una caratteristica che si applica a molti veicoli, ma non a navi, ad esempio, mentre il numero di alberi potrebbe essere una caratteristica che si applica alle navi ma non a veicoli terrestri. La soluzione standard è quella di rendere ogni possibile caratteristica un attributo e di utilizzare un flag speciale "irrilevante valore" per indicare che un determinato attributo non è disponibile per un particolare caso. Una situazione simile sorge quando l'esistenza di una caratteristica (ad esempio, nome del coniuge) dipende dal valore di un altro (sposato o singolo).
Il valore di un attributo per un'istanza particolare è una misura della quantità a cui si riferisce l'attributo. Vi è un'ampia distinzione tra le quantità numeriche e quelle nominali. Gli attributi numerici, talvolta chiamati attributi continui, misurano numeri - veri o totali o interi. Si noti che il termine continua è abusato in questo contesto: gli attributi con valore intero non sono certamente continui nel senso matematico. Gli attributi nominali assumono valori in un insieme prefissato e finito di possibilità e sono talvolta chiamati categorici. Ma ci sono altre possibilità. I testi delle statistiche spesso introducono "livelli di misura" come il nominale, l'ordinale, l'intervallo e il rapporto.
 Le quantità nominali hanno valori che sono simboli distinti. I valori stessi servono proprio come etichette o nomi, quindi il termine nominale, che proviene dalla parola latina per nome. Ad esempio, nei dati meteorologici l'outlook attributo ha valori soleggiati, coperti e piovosi. Nessuna relazione è implicita tra questi tre - nessuna ordinazione o misura di distanza. Certamente non ha senso aggiungere i valori insieme, eliminarli o addirittura confrontare le loro dimensioni. Una regola che utilizza un tale attributo può verificare solo l'uguaglianza o la disuguaglianza, come segue:

outlook: 
     sunny -> no
  overcast -> yes
     rainy -> yes


Le quantità ordinali sono quelle che permettono di ordinare le categorie. Tuttavia, anche se esiste una nozione di ordinamento, non esiste una nozione di distanza. Ad esempio, nei dati meteorologici la temperatura degli attributi ha valori caldi, lievi e freschi. Questi sono ordinati. Sia che dici:

  hot > mild > cool or hot < mild < cool


È una questione di convenzione - non importa quale sia usato finché la coerenza viene mantenuta. Quello che è importante è che le lieve menzogne tra gli altri due. Anche se ha senso confrontare due valori, non ha senso aggiungerli o sottrarli: la differenza tra caldo e mite non può essere confrontata con la differenza tra lieve e fredda. Una regola che utilizza un tale attributo potrebbe comportare un confronto, come segue:

temperature = hot -> no
temperature < hot -> yes

Si noti che la distinzione tra le quantità nominali e ordinali non è sempre semplice e ovvia. Infatti, l'esempio stesso di una quantità ordinale che abbiamo usato in precedenza, la prospettiva, non è del tutto chiaro: si potrebbe sostenere che i tre valori hanno un ordine-overcast essendo in qualche modo intermedio tra sole e pioggia mentre il tempo passa da buono a cattivo.

Le quantità di intervallo hanno valori non solo ordinati ma anche misurati in unità fisse e uguali. Un buon esempio è la temperatura, espressa in gradi (ad esempio, gradi Fahrenheit) piuttosto che sulla scala non numerica implicita da fresco, lieve e caldo. Ha senso perfetto parlare della differenza tra due temperature, ad esempio 46 e 48 gradi, e confrontarlo con la differenza tra altre due temperature, ad esempio 22 e 24 gradi. Un altro esempio è le date. Si può parlare della differenza tra gli anni 1939 e 1945 (6 anni) o addirittura la media degli anni 1939 e 1945 (1942), ma non ha molto senso considerare la somma degli anni 1939 e 1945 (3884 ) O tre volte l'anno 1939 (5817), perché il punto di partenza, anno 0, è completamente arbitrario - anzi, è cambiato molte volte nel corso della storia. (I bambini a volte si chiedono 'quale sia stato chiamato l'anno 300 aC nel 300 aC).
 Le quantità di rapporto sono quelle per cui il metodo di misura definisce intrinsecamente un punto zero. Ad esempio, quando si misura la distanza da un oggetto ad altri, la distanza tra l'oggetto e se stesso forma uno zero naturale. Le quantità di rapporto sono trattate come numeri reali: è consentita qualsiasi operazione matematica. Certamente ha senso parlare di tre volte la distanza e persino di moltiplicare una distanza da un altro per ottenere un'area.
Tuttavia, la questione se esista un punto zero definito "intrinsecamente" dipende dalla nostra conoscenza scientifica: è la relativa cultura. Per esempio, Daniel Fahrenheit non conosceva un limite inferiore alla temperatura, e la sua scala è un intervallo uno. Oggi, tuttavia, vediamo la temperatura come una scala di rapporti basata su zero assoluto. La misurazione del tempo negli anni dal momento che «qualche zero definito culturalmente» come AC 0 non è una scala di rapporto; come lo sono gli anni dal momento del 'big bang' . Anche il punto zero di denaro - dove siamo solitamente abbastanza felici di dire che qualcosa costa due volte più di qualcos'altro - non può essere chiaramente definito per quelli di noi che costantemente massimizzano le nostre carte di credito.
La maggior parte dei sistemi pratici di data mining accolgono solo due di questi quattro livelli di misura: nominali e ordinali. Gli attributi nominali sono talvolta chiamati categorici, enumerati o discreti. L'enumerato è il termine standard utilizzato nell'informatica per indicare un tipo di dati categorico; Tuttavia, la rigorosa definizione del termine - vale a dire, per mettere in una corrispondenza con i numeri naturali - implica un ordine, che non è specificamente implicito nel contesto di apprendimento macchina. Il discreto ha anche connotazioni di ordinazione poiché spesso si discretizza una quantità continua e numerica. Gli attributi ordinali sono generalmente chiamati numerici, o forse continui, ma senza l'implicazione della continuità matematica. Un caso speciale della scala nominale è la dicotomia, che ha solo due membri - spesso designati come veri e falsi, o sì e no nei dati meteorologici. Tali attributi sono talvolta chiamati booleani.
 I sistemi di apprendimento automatico possono utilizzare una grande varietà di altre informazioni sugli attributi. Ad esempio, considerazioni dimensionali potrebbero essere utilizzate per limitare la ricerca alle espressioni o ai confronti che sono dimensionalmente corretti. L'ordinamento circolare potrebbe influenzare i tipi di test che sono considerati. Ad esempio, in un contesto temporale, i test di un attributo giornaliero potrebbero comportare il giorno dopo, il giorno precedente, il giorno del giorno successivo e lo stesso giorno della prossima settimana. Ordini parziali, cioè generalizzazioni o rapporti di specializzazione, si verificano spesso in situazioni pratiche. Informazioni di questo tipo sono spesso definite metadati, dati sui dati. Tuttavia, i tipi di metodi pratici utilizzati per l'estrazione dei dati sono raramente in grado di tenere in considerazione i metadati, anche se è probabile che queste capacità si svilupperanno rapidamente in futuro. (Torniamo a questo nel Capitolo 8.)

      Preparazione dell'input

 
La preparazione dell'input per un'indagine di "data mining" consuma solitamente la maggior parte degli sforzi investiti nell'intero processo di data mining. Anche se questo libro non riguarda veramente i problemi della preparazione dei dati, vogliamo darti una idea 'delle questioni coinvolte' affinché tu possa apprezzare le complessità. Di seguito viene esaminato un particolare formato di file di input, il formato di file di attributo-relazione (formato ARFF), utilizzato nel pacchetto Java descritto nella parte II. Quindi consideriamo i problemi che si verificano quando si converte i set di dati in un tale formato, perché ci sono "alcuni punti pratici semplici di cui essere consapevoli". L'amara esperienza "mostra che i dati reali sono spesso deludenti nella qualità e il controllo attento - un processo che è diventato noto come la pulizia dei dati -" si esegue "molte volte.
 

Raccogliere i dati insieme

 
Quando si inizia a lavorare su un problema di data mining, è necessario innanzitutto integrare tutti i dati in un insieme di istanze. Abbiamo spiegato la necessità di denormalizzare i dati relazionali quando si descrive l'esempio dell'albero di famiglia. Anche se illustra la questione fondamentale, questo esempio autosufficiente e piuttosto artificiale non trasmette in realtà una idea o per ciò che il processo sarà come nella pratica. In una vera e propria applicazione aziendale, sarà necessario portare i dati da diversi reparti. Ad esempio, in un database di marketing saranno necessari dati dal dipartimento di vendita, dal reparto di fatturazione del cliente e dal servizio di assistenza clienti.
L'integrazione di dati provenienti da fonti diverse presenta solitamente molte sfide - non profonde questioni di principio ma la 'brutta verità' della pratica. Diversi dipartimenti utilizzeranno stili diversi di registrazione, diverse convenzioni, diversi periodi di tempo, diversi livelli di aggregazione dei dati, chiavi primarie differenti e avranno diversi tipi di errori. I dati devono essere assemblati, integrati e puliti. L'idea di un'integrazione di database a livello aziendale è conosciuta come data warehousing. I magazzini di dati forniscono un unico punto di accesso coerente a dati aziendali o organizzativi, superando le divisioni dipartimentali. Sono il luogo dove vengono pubblicati i vecchi dati in un modo che può essere utilizzato per informare le decisioni di busness. Il movimento verso il magazzinaggio dei dati è un riconoscimento del fatto che le informazioni frammentate che un'organizzazione usa per sostenere le operazioni quotidiane a livello dipartimentale possono avere un valore strategico immenso quando riuniti. Chiaramente, la presenza di un data warehouse è un precursore molto utile per l'estrazione dei dati e, se non è disponibile, dovranno essere intraprese molte delle operazioni necessarie per il magazzinaggio dei dati per preparare i dati per l'estrazione mineraria.
Spesso anche un data warehouse non contiene tutti i dati necessari e potrebbe essere necessario arrivare all'esterno dell'organizzazione per riportare i dati relativi al problema in questione. Ad esempio, i dati meteo dovevano essere ottenuti nell'esempio di previsione del carico nell'ultimo capitolo e i dati demografici sono necessari per le applicazioni di marketing e di vendita. A volte chiamati dati overlay, questo non viene normalmente raccolto da un'organizzazione, ma è chiaramente rilevante per il problema di data mining. Inoltre, deve essere pulita e integrata con gli altri dati raccolti. 
Un'altra domanda pratica durante l'assemblaggio dei dati è il grado di aggregazione che è appropriato. Quando un coltivatore di latticini decide quali vacche vendere, devono essere aggregati i record di produzione di latte - che una macchina di mungitura automatica registra due volte al giorno -. Allo stesso modo, i dati di chiamata telefonica crude sono poco utilizzati quando le aziende di telecomunicazioni studiano il comportamento dei loro clienti: i dati devono essere aggregati a livello di cliente. Ma vuoi l'utilizzo per mese o per trimestre, e per quanti mesi o trimestri in ritardo? La scelta del tipo e del livello di aggregazione è di solito fondamentale per il successo. Poiché sono coinvolte tante questioni diverse, non si può aspettare di ottenerla la prima volta. Ecco perché il montaggio dei dati, l'integrazione, la pulizia, l'aggregazione e la preparazione generale richiedono così tanto tempo.

  ARFF formato

Ora guardiamo ad un modo standard di rappresentare set di dati consistenti in istanze indipendenti e non ordinate e non implicano rapporti tra le istanze, chiamate un file ARFF. La Figura 2.2 mostra un file ARFF per i dati meteorologici riportati nella Tabella 1.3, la versione con alcune funzioni numeriche. Le righe che iniziano con un segno% sono commenti. Seguendo i commenti all'inizio del file sono il nome della relazione (meteo) e un blocco che definisce gli attributi (prospettiva, temperatura, umidità, ventosa, gioco?). Gli attributi nominali sono seguiti dall'insieme di valori che possono assumere, racchiusi in parentesi graffe. I valori possono includere spazi; Se è così, devono essere collocati in virgolette. I valori numerici sono seguiti dalla numerica parola chiave.

    % ARFF file for the weather data with some n
    @relation weather 
    @data
    %
    % 14 instances   
    %
    sunny, 85, 85, false, no
 


Anche se il problema del tempo è quello di prevedere il gioco di valore di classe? Dai valori degli altri attributi, l'attributo di classe non viene distinto in alcun modo nel file di dati. Il formato ARFF dà semplicemente un set di dati; Non specifica quale degli attributi è quello che dovrebbe essere previsto. Ciò significa che lo stesso file può essere utilizzato per indagare in che modo ciascun attributo può essere predisposto dagli altri, o per trovare le regole di associazione o per il clustering. 

Seguendo le definizioni degli attributi è una linea @data che segnala l'avvio delle istanze nel set di dati. Le istanze sono scritte una per riga, con valori per ogni attributo a sua volta separati da virgole. Se manca un valore, viene rappresentato da un singolo punto interrogativo (in questo set di dati non esistono valori mancanti). Le specifiche degli attributi nei file ARFF permettono di controllare il set di dati per assicurarsi di contenere valori legali per tutti gli attributi e i programmi che leggeranno i file ARFF eseguono automaticamente questo controllo.

 Oltre agli attributi nominali e numerici, esemplificati dai dati meteorologici, il formato ARFF presenta due ulteriori tipi di attributi: attributi di stringa e attributi di data. Gli attributi String hanno valori testuali. Supponi che tu abbia un attributo di stringa che desideri chiamare la descrizione. Nel blocco che definisce gli attributi, viene specificato come segue:

   @attribute description string


Quindi, nei dati di istanza, includere qualsiasi stringa di caratteri in virgolette (includere le virgolette nella stringa, utilizzare la convenzione standard di precedere ciascuna da un backslash, \) Le stringhe sono memorizzate internamente in una tabella di stringhe e rappresentate dal loro indirizzo In quella tabella. Quindi due stringhe che contengono gli stessi caratteri avranno lo stesso valore.
 
Gli attributi String possono avere valori molto lunghi, anche un documento intero. Per essere in grado di utilizzare gli attributi di stringa per l'estrazione del testo, è necessario essere in grado di manipolarli. Ad esempio, un attributo di stringa può essere convertito in molti attributi numerici, uno per ogni parola della stringa, il cui valore è il numero di volte in cui viene visualizzata la parola. Queste trasformazioni sono descritte in Sezione 7.3. Gli attributi di data sono stringhe con un formato speciale e vengono introdotte in questo modo:

    @attribute today date


(Per un attributo chiamato oggi). Weka, il software di apprendimento della macchina descritto nella parte II di questo libro, utilizza il formato data e ora combinati ISO-8601 con un numero di quattro cifre dell'anno, due per mese e giorno, Quindi la lettera T seguita dal tempo con due cifre per ogni ora, minuti e secondi.1 Nella sezione dati del file, le date vengono specificate come la rappresentazione di stringa corrispondente della data e dell'ora, ad esempio, 2004-04 -03T12: 00: 00. Anche se sono specificati come stringhe, le date vengono convertite in forma numerica quando viene letto il file di input. Le date possono anche essere convertite internamente in diversi formati, in modo da poter avere timestamp assoluti nel file di dati e utilizzare trasformazioni in forme come l'ora del giorno o il giorno della settimana per rilevare il comportamento periodico.

   Sparse data (scarsita di data)

  A volte la maggior parte degli attributi ha un valore di 0 per la maggior parte delle istanze. Ad esempio, i "acquisti di dati dei cestini di mercato" effettuati dai clienti supermercati. Non importa quanto grande la spedizione di shopping, i clienti non acquistano mai più di una piccola parte degli articoli che un negozio offre. I dati del cestello del mercato contengono la quantità di ogni elemento acquistato dal cliente e questo è zero per quasi tutti gli articoli in magazzino. Il file di dati può essere visto come una matrice le cui righe e colonne rappresentano clienti e oggetti di magazzino e la matrice è "sparsa" - quasi tutti i suoi elementi sono zero. Un altro esempio si verifica nell'estrazione del testo, in cui le istanze sono documenti. Qui, le colonne e le righe rappresentano documenti e parole e i numeri indicano quante volte una parola particolare viene visualizzata in un determinato documento. La maggior parte dei documenti ha un vocabolario piuttosto piccolo, quindi la maggior parte delle voci è zero. Può sembrare impraticabile rappresentare esplicitamente ciascun elemento di una matrice sparsa, scrivendo ogni valore in ordine, come segue:

   0, 26, 0, 0, 0, 0, 63, 0, 0, 0, “class A”
   0, 0, 0, 42, 0, 0, 0, 0, 0, 0, “class B”




 
Invece, gli attributi non-zero possono essere identificati esplicitamente per numero di attributo e il loro valore dichiarato:

   {1 26, 6 63, 10 “class A”}
   {3 42, 10 “class B”}

Ogni istanza è racchiusa in parentesi graffe e contiene il numero di indice di ogni attributo non-zero (gli indici iniziano da 0) e il suo valore. I file di dati ridotti hanno gli stessi tag @relation e @attribute, seguito da una linea @data, ma la sezione dati è diversa e contiene specifiche in parentesi graffe come quelle precedentemente illustrate. Si noti che i valori omessi hanno un valore di 0 - non sono valori "mancanti"! Se un valore è sconosciuto, deve essere esplicitamente rappresentato con un punto interrogativo.

 Tipi di attributi

I file ARFF ospitano i due tipi di dati di base, nominali e numerici. Gli attributi di stringa e gli attributi di data sono effettivamente nominali e numerici, anche se prima di essere utilizzati, le stringhe vengono spesso convertite in una forma numerica, ad esempio un vettore di parole. Ma come vengono interpretati i due tipi di base dipende dal metodo di apprendimento utilizzato. Ad esempio, la maggior parte dei metodi gestisce gli attributi numerici come bilance ordinali e utilizza solo i valori inferiori e superiori dei confronti tra i valori. Tuttavia, alcuni li trattano come bilancia di rapporti e usano le distanze a distanza. È necessario capire come funzionano i metodi di apprendimento delle macchine prima di utilizzarli per l'estrazione dei dati.

Se un metodo di apprendimento tratta gli attributi numerici come se fossero misurati su scale di rapporto, si pone la questione della normalizzazione. Gli attributi sono spesso normalizzati per trovarsi in una gamma fissa, ad esempio, da zero a uno, dividendo tutti i valori per il valore massimo rilevato o sottraendo il valore minimo e dividendo per l'intervallo tra i valori massimi e quelli minimi. Un'altra tecnica di normalizzazione è quella di calcolare la media statistica e la deviazione standard dei valori degli attributi, sottrarre la media da ogni valore e dividere il risultato per la deviazione standard. Questo processo si chiama standardizzare una variabile statistica e si traduce in un insieme di valori la cui media è zero e la deviazione standard è una.

 Alcuni metodi di apprendimento - ad esempio, varietà di metodi di apprendimento e di regressione basato sull'istanza - affrontano solo le scale di rapporto, poiché calcolano la "distanza" tra due istanze basate sui valori dei loro attributi. Se la scala reale è ordinale, è necessario definire una funzione di distanza numerica. Un modo per farlo è quello di utilizzare una distanza a due livelli: uno se i due valori sono diversi e zero se sono uguali. Qualsiasi quantità nominale può essere considerata come numerica utilizzando questa funzione di distanza. Tuttavia, è piuttosto una tecnica cruda e nasconde il vero grado di variazione tra le istanze. Un'altra possibilità è quella di generare diversi attributi binari sintetici per ogni attributo nominale: torniamo a questo nel paragrafo 6.5 quando esaminiamo l'utilizzo di alberi per la previsione numerica.

  A volte esiste una vera e propria mappatura tra quantità nominali e bilance numeriche. Ad esempio, i codici postali indicano aree che potrebbero essere rappresentate da coordinate geografiche; Le cifre principali dei numeri telefonici possono anche farlo, a seconda del luogo in cui vivi. Le prime due cifre del numero di identificazione di un studente possono essere l'anno in cui "è stata prima iscritta".
È molto comune per i set di dati pratici contenere valori nominali codificati come numeri interi. Ad esempio, un identificatore integer può essere utilizzato come codice per un attributo come un numero di parte, tuttavia tali interi non sono destinati ad essere utilizzati in confronto meno o superiore. Se questo è il caso, è importante specificare che l'attributo è nominale e non numerico.

 È abbastanza possibile trattare una quantità ordinale come se fosse nominale. Infatti, alcuni metodi di apprendimento automatico riguardano solo elementi nominali. Ad esempio, nel problema della lente a contatto l'attributo di età viene trattato come nominale e le regole generate includono le seguenti:

  If age = young and astigmatic = no and
     tear production rate = normal then recommendation = soft
  If age = pre-presbyopic and astigmatic = no and
     tear production rate = normal then recommendation = soft  


Ma infatti l'età, specificata in questo modo, è veramente una quantità ordinale per la quale vale quanto segue:

   young < pre-presbyopic < presbyopic

 
Se si trattasse come ordinale, le due regole potrebbero essere crollate in una:

 If age £ pre-presbyopic and astigmatic = no and
    tear production rate = normal then recommendation = soft

 Che è un modo più compatto, e quindi più soddisfacente, di dire la stessa cosa.

 Valori mancanti

 La maggior parte dei set di dati riscontrati nella pratica, come i dati dei negoziati di lavoro nella tabella 1.6, contengono valori mancanti. I valori mancanti sono spesso indicati da voci fuori campo, forse un numero negativo (ad esempio, -1) in un campo numerico normalmente solo positivo o 0 in un campo numerico che normalmente non può essere 0. Per gli attributi nominali, I valori mancanti possono essere indicati con righe o trattini. A volte vengono distinti diversi tipi di valori mancanti (ad esempio, sconosciuti vs valori non registrati rispetto ai valori irrilevanti) e forse rappresentati da diversi interi negativi (-1, -2, ecc.).
  
 
Devi pensare attentamente circa il significato dei valori mancanti. Possono verificarsi per diverse ragioni, quali ad esempio apparecchi di misura malfunzionanti, modifiche del progetto sperimentale durante la raccolta dei dati e la compilazione di diversi set di dati simili ma non identici. I rispondenti in un sondaggio possono rifiutarsi di rispondere a determinate domande, come l'età o il reddito. In uno studio archeologico, un esemplare come un teschio può essere danneggiato in modo che alcune variabili non possano essere misurate. In un biologico, piante o animali possono morire prima di essere misurate tutte le variabili. Cosa significano queste cose sull'esempio in esame? Può il danno del cranio avere qualche significato in sé, o è solo a causa di un evento casuale? La morte precoce delle piante ha qualche effetto sul caso o meno?

La maggior parte dei metodi di apprendimento automatico fa l'ipotesi implicita che non esiste un particolare significato nel fatto che una determinata istanza ha un valore attributo mancante: il valore non è semplicemente noto. Tuttavia, può esserci una buona ragione per cui il valore dell'attributo non è noto - forse è stata fatta una decisione, sulla base delle prove disponibili, di non eseguire un particolare test - e che potrebbe fornire alcune informazioni sull'istanza diverso dal fatto che il valore è Semplicemente mancante. Se questo è il caso, allora sarebbe più opportuno registrare non testati come un altro valore possibile per questo attributo o forse come un altro attributo nel set di dati. Come illustrano gli esempi precedenti, solo qualcuno che ha familiarità con i dati può fare un giudizio informato sul fatto che un valore particolare mancante abbia un significato extra o sia semplicemente codificato come un valore ordinario mancante. Naturalmente, se sembra che ci siano diversi tipi di valore mancante, che è prima facie la prova che qualcosa sta succedendo che deve essere indagato.
 Se i valori mancanti implicano che un operatore ha deciso di non effettuare una particolare misurazione, ciò può rappresentare molto più che il semplice fatto che il valore sia sconosciuto. Ad esempio, le persone che analizzano i database medici hanno notato che i casi possono, in certe circostanze, essere diagnosticati semplicemente dalle prove che un medico decide di fare a prescindere dall'esito dei test. Quindi un record dei valori "mancanti" è tutto ciò che serve per una diagnosi completa - i valori reali possono essere completamente ignorati!

 Valori inesatti

È importante controllare attentamente i file di data mining per gli attributi e i valori degli attributi di rogue. I dati utilizzati per l'attività mineraria non sono stati certamente raccolti espressamente per questo scopo. Quando originariamente raccolti, molti dei campi probabilmente non importavano e sono stati lasciati vuoti o non controllati. Fermo restando che ciò non pregiudica lo scopo originale dei dati, non c'è alcun incentivo per correggerlo. Tuttavia, quando lo stesso database viene utilizzato per l'estrazione, gli errori e le omissioni improvvisamente cominciano ad assumere un grande significato. Ad esempio, le banche non hanno veramente bisogno di conoscere l'età dei loro clienti, in modo che i loro database possano contenere molti valori mancanti o non corretti. Ma l'età può essere una caratteristica molto significativa 'nelle regole minate'.

 Gli errori tipografici in un set di dati ovviamente portano a valori non corretti. Spesso il valore di un attributo nominale viene errato, creando un valore aggiuntivo per questo attributo. O forse non è un errore ma diversi nomi per la stessa cosa, come Pepsi e Pepsi Cola. Ovviamente il punto di un formato definito come ARFF è consentire di controllare i file di dati per la coerenza interna. Tuttavia, gli errori che si verificano nel file di dati originale vengono spesso conservati attraverso il processo di conversione nel file utilizzato per l'estrazione dei dati; Quindi l'elenco dei possibili valori che ogni attributo assume deve essere esaminato attentamente.
  
 Gli errori tipografici o di misurazione dei valori numerici generano generalmente degli outlier che possono essere rilevati tracciando una variabile alla volta. I valori erronei spesso deviano significativamente dal modello che è evidente nei restanti valori. Talvolta, tuttavia, è difficile trovare valori imprecisi, in particolare senza conoscenze di dominio specializzato.
I dati duplicati presentano un'altra fonte di errore. La maggior parte degli strumenti di apprendimento automatico produrrà risultati diversi se alcune delle istanze dei file di dati vengono duplicate, perché la ripetizione dà maggiore influenza sul risultato.
 La gente spesso fa degli errori deliberati quando inserisce dati personali in banche dati. Essi potrebbero apportare piccoli cambiamenti nell'ortografia della loro strada per cercare di identificare se le informazioni che hanno fornito sono state vendute ad agenzie pubblicitarie che li fanno carico di posta indesiderata. Potrebbero registrare l'ortografia del loro nome quando si richiedono l'assicurazione se hanno avuto in passato l'assicurazione rifiutata. I sistemi rigidi di immissione di dati computerizzati spesso impongono restrizioni che richiedono soluzioni alternative immaginative. Una storia racconta di uno straniero che affitta un veicolo negli Stati Uniti. Essendo dall'estero, non aveva codice postale, ma il computer insistette su uno; In disperazione l'operatore ha suggerito di utilizzare il codice di istruzione dell'agenzia di locazione.
 Se questa è una pratica comune, i progetti futuri di estrazione dati potrebbero notare un gruppo di clienti che apparentemente vivono nello stesso distretto dell'agenzia!Allo stesso modo, un operatore di checkout di supermercati utilizza talvolta la propria carta di acquirente frequente quando il cliente non ne fornisce uno, in modo che il cliente possa ottenere uno sconto altrimenti non disponibile o semplicemente accumulare punti di credito nel conto della cassa. Solo una profonda conoscenza semantica di ciò che sta succedendo sarà in grado di spiegare errori di dati sistematici come questi. Infine, i dati sono vecchi. Molti elementi cambiano quando le circostanze cambiano. Ad esempio, gli elementi delle mailing list - nomi, indirizzi, numeri di telefono e così via - cambiano frequentemente. Devi considerare se i dati che state espandendo sono ancora in corso.

 Conosci i tuoi dati

 Non vi è alcun sostituto per conoscere i tuoi dati. Sono molto utili strumenti semplici che mostrano istogrammi della distribuzione dei valori di attributi nominali e grafici dei valori degli attributi numerici (forse ordinati o semplicemente grafici contro il numero di istanza). Queste visualizzazioni grafiche dei dati rendono più facile identificare gli outlier, che possono rappresentare errori nel file di dati - o convenzioni arcane per codificare situazioni insolite, come un anno mancante come 9999 o un peso mancante a -1 kg, che nessuno Ha pensato di dirti.Gli esperti di dominio devono essere consultati per spiegare le anomalie, i valori mancanti, il significato degli interi che rappresentano categorie piuttosto che le quantità numeriche e così via. Le trame parziali di un attributo contro un altro, o ciascun attributo rispetto al valore della classe, possono essere estremamente rivelatori.
 La pulizia dei dati è una procedura che richiede tempo e richiede molto lavoro, ma è assolutamente necessaria per un successo nella gestione dei dati. Con un grande set di dati, spesso le persone rinunciano - come possono forse controllare tutto? Invece, dovresti esaminare alcune istanze e esaminarle con attenzione. Sarai sorpreso di ciò che troverai. Il tempo per "guardare" i tuoi dati è sempre ben speso.

 Ulteriori letture

Pyle (1999) fornisce un'ampia guida per la preparazione dei dati per la data mining. C'è anche un grande interesse per il data warehousing e per i problemi che comporta. Kimball (1996) offre la migliore introduzione a questi che conosciamo. Cabena et al. (1998) stima che la preparazione dei dati rappresenti il 60% degli sforzi compiuti in un'applicazione per la data mining e scrivono a lungo circa i problemi coinvolti.
 L'area della programmazione logica induttiva, che si occupa di relazioni finite e infinite, è ricoperta da Bergadano e Gunetti (1996). I diversi "livelli di misura" per gli attributi sono stati introdotti da Stevens (1946) e sono ben descritti nei manuali per i pacchetti statistici come SPSS (Nie et al., 1970).
  

Output:Rappresentazione della conoscenza 

 La maggior parte delle tecniche in questo libro forniscono una descrizione facilmente comprensibile dei modelli strutturali dei dati. Prima di esaminare come funzionano queste tecniche, dobbiamo vedere come possono essere espressi i modelli strutturali. Esistono molti modi diversi per rappresentare i modelli che possono essere scoperti mediante l'apprendimento automatico, e ognuno impone la tecnica che può essere utilizzata per dedurre la struttura di uscita dai dati. Una volta capito come viene rappresentata l'uscita, 'sei giunto' 'a un lungo cammino' per capire come può essere generato output.
Abbiamo visto molti esempi di data mining nel capitolo 1. In questi casi l'output ha preso la forma di alberi decisionali e regole di classificazione, che sono stili di base di conoscenza delle conoscenze che molti metodi di apprendimento macchina utilizzano. La conoscenza è "veramente troppo imponente" per una struttura di decisione o una raccolta di regole e usando non intendiamo implicare che queste strutture si contraggano con il vero tipo di conoscenza che portiamo nelle nostre teste: è giusto Che abbiamo bisogno di una parola per fare riferimento alle strutture che i metodi di apprendimento producono. 

Esistono varietà più complesse di regole che consentono di specificare eccezioni e quelle che possono esprimere relazioni tra i valori degli attributi di diverse istanze. Anche forme numeriche possono essere utilizzate forme speciali di alberi. Le rappresentazioni basate su istanze si concentrano sulle istanze stesse piuttosto che sulle regole che regolano i valori attributi. Infine, alcuni metodi di apprendimento generano cluster di istanze. Questi diversi metodi di rappresentazione della conoscenza parallela ai diversi tipi di problemi di apprendimento introdotti nel Capitolo 2.

Tabelle di decisione 

Il modo più semplice e più rudimentale di rappresentare "l'uscita dall'apprendimento macchina" è renderlo uguale a quello dell'input - una tabella di decisione. Ad esempio, la Tabella 1.2 è una tabella delle decisioni per i dati meteorologici: solo cercare le condizioni appropriate per decidere se giocare o meno. Meno triviale, la creazione di una tabella di decisione potrebbe comportare la selezione di alcuni degli attributi. Se la temperatura non è pertinente alla decisione, ad esempio, una tabella più piccola e condensata con tale attributo manca sarebbe una guida migliore. Il problema è ovviamente quello di decidere quali attributi vanno lasciati fuori senza influenzare la decisione finale.

Alberi decisionali  

Un approccio "divide-e-conquista" al problema dell'apprendimento da un insieme di istanze indipendenti porta naturalmente a uno stile di rappresentazione chiamato albero decisionale. Abbiamo visto alcuni esempi di alberi decisionali, per le lenti a contatto (Figura 1.2) e per i contratti di lavoro (Figura 1.3). I nodi in una struttura di decisione implicano una prova di un particolare attributo. Di solito, il test a un nodo confronta un valore di attributo con una costante. Tuttavia, alcuni alberi confrontano due attributi tra di loro, oppure utilizzano una funzione di uno o più attributi. I nodi del foglio forniscono una classificazione che si applica a tutti i casi che raggiungono la foglia o un insieme di classificazioni o una distribuzione di probabilità su tutte le classificazioni possibili. Per classificare un'istanza sconosciuta, viene disattivata l'albero in base ai valori degli attributi testati in nodi successivi e quando viene raggiunta una foglia, l'istanza viene classificata in base alla classe assegnata alla foglia.
 Se l'attributo testato in un nodo è nominale, il numero di bambini è solitamente il numero di possibili valori dell'attributo. In questo caso, poiché c'è un ramo per ogni valore possibile, lo stesso attributo non verrà ripetuto più in basso nell'albero. A volte i valori degli attributi sono suddivisi in due sottoinsiemi e l'albero si affianca solo due modi a seconda del sottocategoria che il valore è nell'albero; In tal caso, l'attributo potrebbe essere testato più volte in un percorso.
 Se l'attributo è numerico, il test a un nodo determina solitamente se il suo valore è maggiore o minore di una costante predeterminata, dando una suddivisione bidirezionale. In alternativa, è possibile utilizzare una suddivisione a tre vie, nel qual caso esistono diverse possibilità. Se il valore mancante viene considerato come un valore di attributo in proprio, creerà un terzo ramo. Un'alternativa per un attributo di valore intero sarebbe una divisione a tre vie in meno, uguali e superiori. Un'alternativa per un attributo reale, per cui uguale a non è un'opzione così significativa, sarebbe quella di provare ad un intervallo piuttosto che a una sola costante, ponendo nuovamente una divisione a tre vie: sotto, dentro e sopra. Un attributo numerico viene spesso testato più volte in un dato percorso lungo l'albero dalla radice alla foglia, ogni prova che coinvolge una costante diversa. Ci riferiamo a descrivere la gestione degli attributi numerici nella Sezione 6.1.
 I valori mancanti rappresentano un problema ovvio. Non è chiaro quale ramo deve essere assunto quando un nodo prova un attributo il cui valore manca. A volte, come descritto nella sezione 2.4, il valore mancante viene considerato come un valore di attributo in proprio. Se questo non è il caso, i valori mancanti dovrebbero essere trattati in modo speciale, piuttosto che essere considerati come un altro valore possibile che l'attributo potrebbe assumere. Una soluzione semplice è registrare il numero di elementi nel set di formazione che scendono verso ogni ramo e utilizzare il ramo più popolare se manca il valore per un'istanza di prova.
  È istruttivo e può anche essere divertente per costruire manualmente un albero di decisione per un set di dati. Per farlo in modo efficace, è necessario un ottimo modo di visualizzare i dati in modo da poter decidere quali sono i migliori attributi da testare e quali prove potrebbero essere. L'Explorer Weka, descritto nella Parte II, dispone di una funzione di classificazione utenti che consente agli utenti di costruire in modo interattivo una struttura di decisione. Ti presenta una trama di dispersione dei dati contro due attributi selezionati, che scegli. Quando si trova un paio di attributi che discriminano bene le classi, è possibile creare una suddivisione bidirezionale disegnando un poligono attorno ai punti dati appropriati sulla trama di dispersione.
 Ad esempio, in Figura 3.1 (a) l'utente sta operando su un set di dati con tre classi, il set di dati iride e ha trovato due attributi, lunghezza petali e larghezza petali, che fanno un buon lavoro di suddividere le classi. Un rettangolo è stato disegnato manualmente per separare una delle classi (Iris versicolor). Poi l'utente passa alla vista dell'albero di decisione nella Figura 3.1 (b) per vedere l'albero finora. Il nodo foglia sinistra contiene prevalentemente iridi di un tipo (Iris versicolor, contaminato da solo due vergini); La mano destra contiene prevalentemente due tipi (Iris setosa e virginica, contaminati da soli due versicolori). L'utente probabilmente selezionerà la foglia a destra e la lavorerà successivamente, dividendola ulteriormente con un altro rettangolo, forse basato su una coppia di attributi diversi (anche se, a partire dalla Figura 3.1 [a], questi due look sono abbastanza buoni).
 La sezione 10.2 spiega come utilizzare la funzione di classificazione utenti di Weka. La maggior parte delle persone piace fare le prime decisioni ma rapidamente perde interesse dopo, e un'opzione molto utile è quella di selezionare un metodo di apprendimento macchina e lasciarlo prendere in qualsiasi punto dell'albero di decisione. La costruzione manuale degli alberi decisionali è un buon modo per ottenere un tatto per l'attività noiosa di valutare diverse combinazioni di attributi da dividere.

  Regole di classificazione  

Le regole di classificazione sono un'alternativa popolare agli alberi decisionali e abbiamo già visto esempi per il tempo (pagina 10), lenti a contatto (pagina 13), iris (pagina 15) e set di dati di soia (pagina 18). L'antecedente o la precondizione di una regola è una serie di test, proprio come i test sui nodi degli alberi decisionali, e la conseguente o la conclusione dà la classe o le classi che si applicano a istanze coperte da tale regola o forse dà una probabilità Distribuzione sulle classi. Generalmente, le condizioni preliminari sono logicamente ANDate insieme e tutte le prove devono avere successo se la regola sta per sparare. Tuttavia, in alcune formule di regola le condizioni preliminari sono espressioni logiche generali piuttosto che congiunzioni semplici. Penseremo spesso che le regole individuali siano effettivamente logicamente ORed insieme: se si applica, la classe (o la distribuzione di probabilità) data nella sua conclusione viene applicata all'istanza. Tuttavia, si verificano conflitti quando si applicano diverse regole con conclusioni diverse; Torneremo a questo poco.
 È facile leggere un insieme di regole direttamente da un albero di decisione. Una regola viene generata per ciascuna foglia. L'antecedente della regola include una condizione per ogni nodo sul percorso dalla radice a quella foglia, e la conseguente della regola è la classe assegnata dalla foglia. Questa procedura produce regole che sono inequivocabili in quanto l'ordine in cui vengono eseguite è irrilevante. Tuttavia, in generale, le regole che vengono lette direttamente da un albero di decisione sono molto più complesse del necessario e le regole derivate dagli alberi sono solitamente potate per eliminare i test ridondanti.
 Poiché gli alberi decisionali non possono facilmente esprimere il disgiunto implicito tra le diverse regole di un insieme, trasformare un insieme generale di regole in un albero non è così semplice. Una buona illustrazione di questo si verifica quando le regole hanno la stessa struttura ma attributi diversi, come:

 If a and b then x
 If c and d then x
    
 Quindi è necessario interrompere la simmetria e scegliere un singolo test per il nodo radice. Se, ad esempio, viene scelto uno, la seconda regola deve in effetti ripetere due volte nell'albero, come mostrato nella Figura 3.2. Questo è noto come il problema subtree replicato.
Il problema sottotropo replicato è sufficientemente importante affinché sia opportuno esaminare un paio di altri esempi. Il diagramma a sinistra della figura 3.3 mostra un'esclusiva o una funzione per cui l'output è a se x = 1 o y = 1, ma non entrambi. Per farlo in un albero, devi prima dividere un attributo, portando ad una struttura come quella mostrata nel centro. Al contrario, le regole possono riflettere fedelmente la vera simmetria del problema rispetto agli attributi, come mostrato a destra.
 In questo esempio le regole non sono notevolmente più compatte dell'albero. In realtà, sono proprio quello che si otterrebbe leggendo le regole dall'albero in modo ovvio. Ma in altre situazioni, le regole sono molto più compatte degli alberi, soprattutto se è possibile avere una regola "predefinita" che copre i casi non specificati dalle altre regole. Ad esempio, per catturare l'effetto delle regole in Figura 3.4 - in cui sono presenti quattro attributi, x, y, z e w, ciascuno dei quali può essere 1, 2 o 3 - richiede l'albero mostrato a destra. Ognuno dei tre piccoli triangoli grigi in alto a destra dovrebbe effettivamente contenere l'intero sottostrato a tre livelli che viene visualizzato in grigio, un esempio piuttosto estremo del problema subtree replicato. Questa è una descrizione abbastanza complessa di un concetto piuttosto semplice.
  Una delle ragioni per cui le regole sono popolari è che ogni regola sembra rappresentare un "nugget" di conoscenza indipendente. È possibile aggiungere nuove regole a una regola esistente senza disturbare quelle già esistenti, mentre per aggiungere una struttura ad albero può richiedere la ridefinizione dell'intero albero. Tuttavia, questa indipendenza è qualcosa di illusorio, perché ignora la questione di come viene eseguita la regola. Abbiamo spiegato in precedenza (a pagina 11) il fatto che se le regole devono essere interpretate in ordine come "lista di decisione", alcune di esse, presi individualmente e fuori contesto, potrebbero non essere corrette. D'altra parte, se l'ordine di interpretazione dovrebbe essere immateriale, allora non è chiaro cosa fare quando diverse regole conducono a conclusioni diverse per lo stesso istanza. Questa situazione non può sorgere per le regole che vengono lette direttamente da un albero di decisione perché la ridondanza inclusa nella struttura delle regole impedisce ogni ambiguità nell'interpretazione. Ma si verifica quando le regole vengono generate in altri modi.
 Se un set di regole offre più classificazioni per un esempio particolare, una soluzione non deve dare alcuna conclusione. Un altro è quello di contare come spesso ogni regola si accende sui dati di allenamento e va con quella più popolare. Queste strategie possono portare a risultati radicalmente diversi. Un problema diverso si verifica quando si incontra un'istanza che le regole non riescono a classificare affatto. Ancora una volta, questo non può accadere con gli alberi decisionali o con le regole che si leggono "direttamente da loro", ma può facilmente accadere con i set di regole generali. Un modo per affrontare questa situazione è quello di non riuscire a classificare un simile esempio; L'altro è quello di scegliere la classe più frequente come predefinita. Anche in questo caso si possono ottenere risultati radicalmente diversi per queste strategie. Le regole individuali sono semplici e le serie di regole sembrano ingannevolmente semplici, ma date solo un insieme di regole senza informazioni aggiuntive, non è chiaro come deve essere interpretato.
  Una situazione particolarmente semplice si verifica quando le regole conducono a una classe booleana (diciamo sì e no) e quando vengono espresse solo le regole che conducono ad un risultato (si dice sì). L'ipotesi è che se un'istanza particolare non è nella classe sì, allora deve essere nella classe no - una forma di assunzione mondiale chiusa. Se questo è il caso, le regole non possono confliggere e non c'è ambiguità nell'interpretazione delle regole: qualsiasi strategia di interpretazione dà lo stesso risultato. Tale insieme di regole può essere scritto come un'espressione logica in quella che si chiama forma normale disgiunta: cioè come disgiunzione (OR) delle condizioni di congiunzione (AND).
 È questo semplice caso speciale che seduce le persone nell'assumere regole sono molto facili da affrontare, perché qui ogni regola funziona veramente come un nuovo e indipendente pezzo di informazioni che contribuisce in modo diretto alla disgiunzione. Purtroppo, si applica solo agli esiti booleani e richiede l'assunzione del mondo chiuso, e entrambi questi vincoli sono irrealistici nella maggior parte delle situazioni pratiche. Gli algoritmi di apprendimento macchina che generano regole producono inevitabilmente regole di regole ordinate in situazioni multiclassiche e questo sacrifica qualsiasi possabilità di modularità perché l'ordine di esecuzione è critico.

  Regole dell'associazione - Associazione di Regole

 Le regole di associazione non sono veramente diverse dalle regole di classificazione, ad eccezione di quelle che possono prevedere qualsiasi attributo, non solo la classe, e questo dà loro la libertà di prevedere combinazioni di attributi. Inoltre, le regole di associazione non sono destinate ad essere utilizzate assieme come regole di classificazione. Diverse regole di associazione esprimono regolarità diverse che sono alla base del set di dati e prevedono generalmente diverse cose.
 Poiché tante diverse regole di associazione possono derivare anche da un piccolo set di dati, l'interesse è limitato a quelli che si applicano a un numero ragionevolmente elevato di istanze e hanno un'accuratezza ragionevolmente elevata sulle istanze a cui si applicano. La copertura di una regola di associazione è il numero di istanze per le quali prevede correttamente - questo è spesso chiamato suo supporto. La sua precisione, spesso chiamata fiducia, è il numero di istanze che prevede correttamente, espresse in proporzione di tutte le istanze a cui si applica. Ad esempio, con la regola:
   
 If temperature = cool then humidity = normal  
  
 La copertura è il numero di giorni che sono entrambi freddi e hanno un'umidità normale (4 giorni nei dati della tabella 1.2), e la precisione è la proporzione di giorni freddi con umidità normale (100% in questo caso). È solito specificare i valori minimi di copertura e di precisione e cercare solo quelle regole la cui copertura e la precisione sono entrambi almeno questi minimi specificati. Nelle informazioni meteo, ad esempio, ci sono 58 regole la cui copertura e precisione sono almeno rispettivamente del 2 e del 95%. (Può anche essere conveniente specificare la copertura come percentuale del numero totale di istanze.)
 Le regole dell'associazione che prevedono molteplici conseguenze devono essere interpretate piuttosto con attenzione. Ad esempio, con i dati meteorologici riportati nella Tabella 1.2 abbiamo visto questa regola:

 If windy = false and play = no then outlook = sunny
    and humidity = high


Questa non è solo un'espressione stenografica per le due regole distinte:

 If windy = false and play = no then outlook = sunny
 If windy = false and play = no then humidity = high


 Significa infatti che questi superano la copertura minima e le cifre di precisione - ma implica anche di più. La regola originale significa che il numero di esempi che non sono in gioco, non giocando, con una prospettiva soleggiata e un'alta umidità, è almeno pari alla minima copertura minima specificata. Significa anche che il numero di tali giorni, espressi in proporzione di giorni non giocati, non è almeno la minima precisione indicata. Ciò implica che la regola

  If humidity = high and windy = false and play = no
     then outlook = sunny
 
 Perchè ha la stessa copertura della regola originale e la sua precisione deve essere almeno altrettanto elevata rispetto alla regola originale poiché il numero di giorni di alta umidità, "non ventoso" non è necessariamente inferiore a quello dei giorni "non ventoso, non giocando'i - che rende l'accuratezza maggiore.
   Come abbiamo visto, esistono relazioni tra regole di associazione particolari: alcune regole implicano altri. Per ridurre il numero di regole che vengono prodotte, nel caso in cui siano correlate più regole, è opportuno presentare solo l'utente più forte. Nell'esempio precedente, solo la prima regola dovrebbe essere stampata.

 Regole con eccezioni

 Tornando alle regole di classificazione, un'estensione naturale è consentire loro di avere eccezioni. Quindi possono essere apportate modifiche incrementali a una regola impostata esprimendo eccezioni alle regole esistenti piuttosto che riorganizzare l'intero set. Ad esempio, considerare il problema dell'iride descritto in precedenza. Supponiamo che sia stato trovato un nuovo fiore con le dimensioni riportate nella Tabella 3.1 e un esperto ha dichiarato di essere un'istanza di Iris setosa. Se questo fiore fosse classificato secondo le regole del capitolo 1 (pagine 15-16) per questo problema, sarebbe erroneamente classificato da due di essi:

  If petal length ≥ 2.45 and petal length < 4.45 then Iris versicolor
  If petal length ≥ 2.45 and petal length < 4.95 and
     petal width < 1.55 then Iris versicolor
 Queste regole richiedono la modifica in modo che la nuova istanza possa essere trattata correttamente. Tuttavia, semplicemente modificando i limiti per i test di valore attributo in queste regole potrebbe non essere sufficiente perché le istanze utilizzate per creare l'insieme di regole possono essere miscelati. Il fissaggio di un set di regole non è semplice come sembra.
 Invece di modificare i test nelle regole esistenti, potrebbe essere consultato un esperto per spiegare perché il nuovo fiore li violasse, ricevendo spiegazioni che potrebbero essere utilizzate per estendere solo le norme rilevanti. Ad esempio, la prima di queste due regole misclassifica la nuova Iris setosa come un'istanza del genere Iris versicolor. Invece di alterare i limiti di una qualsiasi delle disuguaglianze nella regola, un'eccezione può essere fatta in base ad un altro attributo:

  If petal length ≥ 2.45 and petal length < 4.45 then
     Iris versicolor EXCEPT if petal width < 1.0 then Iris setosa


 Questa regola dice che un fiore è Iris versicolor se la lunghezza del petalo è tra 2.45 e 4.45 cm, eccetto quando la larghezza del petalo è inferiore a 1.0 cm, nel qual caso è Iris setosa.
Naturalmente, potremmo avere eccezioni alle eccezioni, alle eccezioni di questi, e così via, dando alla regola qualcosa di carattere di un albero. Oltre ad essere utilizzato per apportare modifiche incrementali ai set di regole esistenti, le regole con eccezioni possono essere utilizzate per rappresentare in primo luogo l'intera descrizione concettuale.
 La Figura 3.5 mostra un insieme di regole che classificano correttamente tutti gli esempi nel dataset di Iris dato in precedenza (pagine 15-16). Queste regole sono piuttosto difficili da comprendere in un primo momento. Andiamo avanti. È stato scelto un risultato predefinito, Iris setosa, ed è mostrato nella prima riga. Per questo set di dati, la scelta del default è piuttosto arbitraria perché esiste 50 esempi di ciascun tipo. Normalmente, l'esito più frequente viene scelto come predefinito.
 Le regole successive danno eccezioni a questo default. Il primo se. . . Quindi, sulle righe da 2 a 4, fornisce una condizione che porta alla classificazione Iris versicolor. Tuttavia, ci sono due eccezioni a questa regola (righe da 5 a 8), che tratteremo in un momento. Se le condizioni sulle righe 2 e 3 non sono riuscite, viene raggiunta l'altra clausola nella riga 9, che stabilisce essenzialmente una seconda eccezione rispetto all'originale originale. Se la condizione sulla riga 9 è in possesso, la classificazione è Iris virginica (riga 10). Ancora una volta, esiste un'eccezione a questa regola (alle righe 11 e 12).
 Ora ritorni all'eccezione sulle linee da 5 a 8. Questo sovrascrive la conclusione di Iris versicolor sulla riga 4 se uno dei test sulle righe 5 e 7 è in possesso. Come accade, queste due eccezioni portano alla stessa conclusione, Iris virginica (righe 6 e 8). L'eccezione finale è quella sulle righe 11 e 12, che sovrascrive la conclusione di virginica Iris sulla linea 10 quando la condizione sulla linea 11 è soddisfatta e porta alla classificazione Iris versicolor.
  Avrete probabilmente bisogno di riflettere su queste regole per qualche minuto prima che diventi chiaro come siano destinate alla lettura. Anche se ci vuole un po 'di tempo per abituarci a leggerli, risolvendo le eccezioni e se. . . poi . . . Elses diventa più facile con familiarità. Le persone spesso pensano a problemi reali in termini di regole, eccezioni e eccezioni alle eccezioni, quindi è spesso un ottimo modo per esprimere un insieme di regole complesse. Ma il punto principale a favore di questo modo di rappresentare le regole è che si scala bene. Sebbene l'insieme di regole sia un po 'difficile da comprendere, ogni singola conclusione, ogni singola dichiarazione, può essere considerata solo nel contesto delle regole e delle eccezioni che lo portano; Mentre con elenchi di decisione tutte le regole precedenti devono essere riesaminate per determinare l'effetto preciso di una regola individuale. Questa proprietà di località è cruciale quando si cerca di capire le serie di regole di grandi dimensioni. Psicologicamente, le persone che hanno familiarità con i dati pensano a un particolare insieme di casi, o un tipo di caso, quando si esamina una conclusione nella struttura di eccezione e quando uno di questi casi risulta essere un'eccezione alla conclusione, è facile aggiungere 'una clausola eccezionale' per soddisfarla.
  Vale la pena sottolineare che il default. . . tranne che . . . poi . . . La struttura è logicamente equivalente a se. . . poi . . . altro . . ., Dove l'altro è incondizionato e specifica esattamente quello che l'impostazione predefinita ha fatto. Un altro incondizionato è ovviamente un default. (Si noti che non ci sono elenchi incondizionati nelle regole precedenti.) Logicamente, le regole basate sulle eccezioni possono essere semplicemente riscritte in termini di regolare se. . . poi . . . Altre clausole. Ciò che si ottiene dalla formulazione in termini di eccezioni non è logico ma psicologico. Supponiamo che i valori predefiniti e le prove che si verificano presto si applicano più ampiamente alle eccezioni più in basso. Se questo è veramente vero per il dominio e l'utente può vedere che è plausibile, l'espressione in termini di regole (comuni) e (rare) eccezioni sarà più facile da cogliere di una struttura diversa, ma logicamente equivalente.

  Regole che coinvolgono relazioni

  Abbiamo assunto implicitamente che le condizioni delle regole comportano la prova di un valore di attributo contro una costante. Tali regole sono chiamate proposizionali perché il linguaggio di attributo-valore usato per definirli ha lo stesso potere di quello che i logici chiamano il calcolo proposizionale. In molte attività di classificazione, le regole proposizionali sono sufficientemente espressive per le descrizioni concettuali e precise del concetto. Ad esempio, il tempo, la raccomandazione delle lenti a contatto, il tipo di iris e l'accettabilità dei set di dati per contratto di lavoro menzionato in precedenza sono ben descritti da regole propositive. Tuttavia, ci sono situazioni in cui una forma più espressiva di regole fornirà una descrizione concettuale più intuitiva e concisa, e queste sono situazioni che implicano rapporti tra esempi come quelli incontrati nella sezione 2.2.
  Supponiamo, per fare un esempio concreto, abbiamo l'insieme di otto blocchi di costruzione delle varie forme e dimensioni illustrate nella Figura 3.6 e vogliamo imparare il concetto di standing. Questo è un classico problema a due classi con classi in piedi e mentendo. I quattro blocchi ombreggiati sono esempi positivi (in piedi) del concetto e i blocchi non tamponati sono esempi negativi (bugiardi). Le uniche informazioni che verrà data l'algoritmo di apprendimento sono la larghezza, l'altezza e il numero dei lati di ogni blocco. I dati formativi sono mostrati nella tabella 3.2.
Un set di regole proposizionali che potrebbe essere prodotto per questi dati è:

 if width ≥ 3.5 and height < 7.0 then lying
 if height ≥ 3.5 then standing


Nel caso in cui si sta chiedendo, 3.5 è scelto come punto di interruzione per la larghezza, perché è a metà tra la larghezza del blocco mentale più sottile, cioè 4, e la larghezza del blocco fisso più grande che ha una altezza inferiore a 7, vale a dire 3. Inoltre , 7,0 viene scelto come punto di interruzione dell'altezza perché è a metà tra l'altezza del blocco più alto, cioè 6, e il blocco più corto più largo, la cui larghezza è maggiore di 3,5, vale a dire 8. È comune collocare le soglie numeriche a metà tra Valori che delimitano i confini di un concetto.
 Anche se queste due regole funzionano bene sugli esempi forniti, non sono molto buoni. Molti blocchi nuovi non sarebbero classificati da alcuna regola (ad esempio, uno con larghezza 1 e altezza 2) e è facile elaborare molti blocchi legittimi che le regole non si adattano.
  Una persona che classifica gli otto blocchi avrebbe probabilmente notato che "i blocchi in piedi sono quelli più alti di quelli ampi". Questa regola non confronta i valori degli attributi con le costanti, confronta gli attributi tra loro:

if width > height then lying
if height > width then standing
 
 I valori effettivi degli attributi di altezza e larghezza non sono importanti; Solo il risultato di confrontare i due. Le regole di questa forma sono chiamate relazionali, perché esprimono rapporti tra attributi, piuttosto che proposizionale, che indica un fatto su un solo attributo.
 Le relazioni standard includono l'uguaglianza (e la disuguaglianza) per gli attributi nominali e meno e più che per quelli numerici. Anche se i nodi relazionali potrebbero essere messi in alberi decisionali proprio come le condizioni relazionali possono essere messe in regole, gli schemi che ospitano le relazioni generalmente utilizzano la regola piuttosto che la rappresentazione dell'albero. Tuttavia, la maggior parte dei metodi di apprendimento delle macchine non considera le regole relazionali perché c'è un costo considerevole nel farlo. Un modo per consentire a un metodo proposizionale di utilizzare i rapporti è quello di aggiungere attributi extra, secondari che dicono se due attributi principali sono uguali o non, o dare la differenza tra di loro se sono numerici. Ad esempio, è possibile aggiungere un attributo binario di larghezza <altezza? Alla tabella 3.2. Questi attributi vengono spesso aggiunti come parte del processo di elaborazione dati.
 Con un aumento apparentemente piuttosto "piccolo", il potere espressivo della rappresentazione relazionale della conoscenza può essere esteso molto. Il trucco è quello di esprimere le regole in modo che esplica il "ruolo dell'istanza":

if width(block) > height(block) then lying(block)
if height(block) > width(block) then standing(block)
 
 Anche se questo non sembra molto di un'estensione, è che se le istanze possono essere decomposte in parti. Ad esempio, se una torre è un mucchio di blocchi, uno sopra l'altro, allora il fatto che il blocco superiore della torre è in piedi può essere espresso da:

if height(tower.top) > width(tower.top) then standing(tower.top)
 
 Qui, tower.top viene utilizzato per fare riferimento al blocco superiore. Finora, nulla è stato guadagnato. Ma se "tower.rest" si riferisce al resto della torre, allora il fatto che la torre è composta interamente di blocchi permanenti può essere espressa dalle regole:

 if height(tower.top) > width(tower.top) then standing(tower.top)

Qui, tower.top viene utilizzato per fare riferimento al blocco superiore. Finora, nulla è stato guadagnato. Ma se "tower.rest" si riferisce al resto della torre, allora il fatto che la torre è composta interamente di blocchi permanenti può essere espressa dalle regole:

 if height(tower.top) > width(tower.top) and standing(tower.rest)
    then standing(tower)
 L'aggiunta apparentemente minima della condizione in piedi (tower.rest) è un'espressione ricorsiva che si rivelerà vera solo se il resto della torre è composto da blocchi permanenti. Una applicazione ricorsiva della stessa regola verificherà questo. Naturalmente, è necessario assicurarsi che la ricorsione "si esaurisca" correttamente aggiungendo un'altra regola, come ad esempio:


if tower = empty then standing(tower.top)


Con questa aggiunta, le regole relazionali possono esprimere concetti che non possono essere espressamente proposti, in quanto la ricorsione può avvenire su elenchi arbitrariamente lunghi di oggetti. I set di regole come questo sono chiamati programmi logici e questa area di apprendimento automatico è chiamata programmazione logica induttiva. Non lo tratteremo ulteriormente in questo libro.

Alberi per la previsione numerica

 Il tipo di alberi decisionali e le regole che stiamo esaminando sono progettati per predire categorie piuttosto che quantità numeriche. Quando si tratta di predire numeri numerici, come nei dati delle prestazioni della CPU nella tabella 1.5, è possibile utilizzare lo stesso tipo di rappresentazione di albero o regola, ma i nodi fogli dell'albero o del lato destro delle regole contengono Un valore numerico che è la media di tutti i valori impostati per l'allenamento a cui la foglia o la regola si applica perché gli statisti usano il termine regressione per il processo di calcolo di un'espressione che prevede una quantità numerica, gli alberi decisionali con valori numerici medi sulle foglie Sono chiamati alberi di regressione.
 La Figura 3.7 (a) mostra un'equazione di regressione per i dati sulle prestazioni della CPU, e la Figura 3.7 (b) mostra un albero di regressione. Le foglie dell'albero sono numeri che rappresentano il risultato medio per i casi che raggiungono la foglia. L'albero è molto più grande e più complesso dell'equazione di regressione e, se calcoliamo la media dei valori assoluti degli errori tra le misure previste e le effettive prestazioni della CPU, risulterà significativamente meno per l'albero che per la regressione equazione. L'albero di regressione è più accurato in quanto un semplice modello lineare rappresenta male i dati in questo problema. Tuttavia, l'albero è ingombrante e difficile da interpretare a causa della sua grande dimensione.
 È possibile combinare equazioni di regressione con gli alberi di regressione. La Figura 3.7 (c) è un albero le cui foglie contengono espressioni lineari, ovvero le equazioni di regressione, piuttosto che singoli valori predittivi. Questo è (leggermente confuso) chiamato un albero del modello. La Figura 3.7 (c) contiene i sei modelli lineari che appartengono alle sei foglie, etichettate da LM1 a LM6. L'albero del modello approssima le funzioni continue dalle "patch" lineari, una rappresentazione più sofisticata rispetto agli alberi di regressione o regressione lineare. Anche se l'albero del modello è più piccolo e più comprensibile dell'albero di regressione, i valori medi di errore sui dati di addestramento sono più bassi. (Tuttavia, nel Capitolo 5 vedremo che il calcolo dell'errore medio sul set di formazione non è in generale un buon modo per valutare le prestazioni dei modelli.)

   Rappresentazione basato su istanza

La forma più semplice di apprendimento è la semplice memorizzazione, o l'apprendimento automatico. Una volta memorizzate una serie di istruzioni di formazione, quando si incontra una nuova istanza, viene ricercata la memoria per l'istanza di addestramento che rispecchia fortemente la nuova. L'unico problema è come interpretare "assomiglia": ci spiegheremo a breve. Innanzitutto, però, notare che questo è un modo completamente diverso di rappresentare la "conoscenza" estratta da un insieme di istanze: basta memorizzare le istanze stesse e operare collegando nuovi istanze la cui classe è sconosciuta a quelli esistenti la cui classe è conosciuta. Invece di cercare di creare regole, lavorare direttamente dagli esempi stessi. Questo è conosciuto come apprendimento basato su istanze. In un certo senso tutti gli altri metodi di apprendimento sono "basati sull'istanza", perché cominciamo sempre con un insieme di istanze come le informazioni di formazione iniziali. Ma la rappresentazione di conoscenza basata su istanze utilizza le istanze stesse per rappresentare ciò che viene appreso, invece di inferire un set di regole o un albero di decisione e memorizzarlo.
  Nell'apprendimento basato su istanze, tutto il lavoro reale viene fatto quando è il momento di classificare una nuova istanza piuttosto che quando viene elaborato il set di formazione. In un certo senso, quindi, la differenza tra questo metodo e gli altri che abbiamo visto è il momento in cui avviene l'apprendimento. L'apprendimento basata su istanze è pigro, deferendo il lavoro reale il più a lungo possibile, mentre altri metodi sono desiderosi, generando una generalizzazione non appena i dati sono stati visti. In apprendimento basato su istanze, ogni nuova istanza viene confrontata con quelle esistenti utilizzando una metrica a distanza e l'istanza esistente più vicina viene utilizzata per assegnare la classe a quella nuova. Questo è il metodo di classificazione più vicino. A volte viene utilizzato più di un vicino vicino e la classe di maggioranza dei vicini vicini k (o la media ponderata per distanza, se la classe è numerica) viene assegnata alla nuova istanza. Questo è chiamato il metodo k-nearest-neighbor.
 Calcolare la distanza tra due esempi è banale quando gli esempi hanno un solo attributo numerico: è solo la differenza tra i due valori dell'attributo. È quasi così semplice quando ci sono diversi attributi numerici: generalmente viene utilizzata la distanza standard Euclidea. Tuttavia, questo presuppone che gli attributi siano normalizzati e siano di pari importanza, e uno dei principali problemi nell'apprendimento è quello di determinare quali sono le caratteristiche importanti.
 Quando sono presenti attributi nominali, è necessario trovare una "distanza" tra diversi valori di tale attributo. Quali sono le distanze tra, per esempio, i valori rossi, verdi e blu? Di solito viene assegnata una distanza di zero se i valori sono identici; Altrimenti la distanza è una. Quindi la distanza tra rosso e rosso è zero, ma quella tra rosso e verde è una. Tuttavia, può essere desiderabile utilizzare una rappresentazione più sofisticata degli attributi. Ad esempio, con più colori si potrebbe usare una misura numerica di tonalità nello spazio colore, rendendo il colore giallo più vicino all'arancio rispetto a quello verde e ocra ancora più vicino. Alcuni attributi saranno più importanti di altri e questo viene spesso riflessa nella metrica a distanza con una qualche ponderazione di attributo. La derivazione di pesi attributi adeguati dal set di formazione è un problema fondamentale nell'apprendimento basato su istanze.
 Potrebbe non essere necessario, o desiderabile, memorizzare tutte le istanze di formazione. Per una cosa, questo può rendere il calcolo del vicino prossimo insopportabile lentamente. Per un altro, può consumare quantità irrealistiche di stoccaggio. Generalmente, alcune regioni dello spazio degli attributi sono più stabili rispetto ad altri rispetto alla classe e solo pochi esemplari sono necessari all'interno di regioni stabili. Ad esempio, si potrebbe aspettare che la densità richiesta di esemplari che si trovino bene all'interno dei confini della classe sia molto inferiore alla densità necessaria nei limiti delle classi. Decidere quali istanze da salvare e quali scartare è un altro problema fondamentale nell'apprendimento basato su un esempio.
 Un inconveniente apparente per le rappresentazioni basate su istanze è che non rendono esplicite le strutture che vengono apprese. In un certo senso questo viola la nozione di "apprendimento" che abbiamo presentato all'inizio di questo libro; Istanze "non descrivono" i modelli dei dati ". Tuttavia, i casi si combinano con la metrica di distanza 'per scolpire i confini' in uno spazio di esempio che distingue una classe dall'altra, e questa è una specie di rappresentazione esplicita della conoscenza. Ad esempio, data un'unica istanza di ciascuna di due classi, la regola di prossimità più vicina divide effettivamente lo spazio di istanza lungo "il bisettore perpendicolare" della "linea che unisce" le istanze.. Dato diverse istanze di ogni classe, lo spazio è diviso da un insieme di righe che rappresentano i bisettori perpendicolari di linee selezionate che uniscono un'istanza di una classe a una di un'altra classe. La figura 3.8 (a) illustra un poligono a nove facciate che separa la classe "cerchio riempito" dalla "classe opencircle". Questo poligono è implicito nel funzionamento della regola più vicina.
  Quando i casi di formazione sono scartati, il risultato è quello di salvare solo alcuni esempi prototipali di ogni classe. La figura 3.8 (b) mostra come cerchi scuri solo gli esempi effettivamente utilizzati nelle decisioni più vicine: gli altri (quelli grigi) possono essere scartati senza influenzare il risultato. Questi esempi prototipi rappresentano una sorta di esplicita rappresentazione della conoscenza.
  Alcune rappresentazioni basate su istanze vanno oltre ed esplicitamente generalizzano le istanze. In genere, questo è compiuto creando regioni rettangolari che racchiudono esempi della stessa classe. La Figura 3.8 (c) mostra le regioni rettangolari che potrebbero essere prodotte. Esempi sconosciuti che rientrano in uno dei rettangoli saranno assegnati alla classe corrispondente; Quelli che escono da tutti i rettangoli saranno soggetti alla solita regola più vicina. Ovviamente questo produce diversi confini di decisione dalla semplice regola del prossimo vicino, come si può vedere sovrapponendo il poligono nella figura 3.8 (a) sui rettangoli. Qualsiasi parte del poligono che si trova all'interno di un rettangolo sarà tagliata fuori e sostituita dal confine del rettangolo.
 Le generalizzazioni rettangolari nello spazio di esempio sono proprio come le regole con una forma speciale di condizione, quella che esegue una variabile numerica contro un limite superiore e inferiore e seleziona la regione in mezzo. Diverse dimensioni del rettangolo corrispondono ai test su diversi attributi che sono ANDed insieme. La scelta di regioni rettangolari "aderenti", poiché i test conducono a regole molto più conservatrici di quelle generalmente prodotte da metodi di apprendimento basati su regole, poiché per ogni confine della regione esiste un'istanza reale che si trova (o all'interno) . Test come x <a (dove x è un valore di attributo e una è una costante) comprendono un intero mezzo spazio, si applicano non importa quanto piccola x sia finché è inferiore a. Quando si effettua una generalizzazione rettangolare in uno spazio di esempio, si può permetterti di essere conservatore, perché se si incontra un nuovo esempio che si trova fuori da tutte le regioni, è possibile tornare alla metrica più vicina.Questo è chiamato il metodo k-nearest-neighborCon metodi basati su regole l'esempio non può essere classificato o riceve solo una classificazione predefinita se non si applicano regole. Il vantaggio di regole più conservatrici è che, sebbene incomplete, possono essere più evidenti di un insieme completo di regole che copre tutti i casi. Infine, assicurarsi che le regioni non si sovrappongano equivarrebbe a garantire che al massimo una regola può applicarsi ad un esempio, eliminando un'altra delle difficoltà dei sistemi basati su regole cosa fare quando si applicano più regole.
 Un genere più complesso di generalizzazione è quello di permettere alle regioni rettangolari di nidificarsi uno nell'altro. Poi una regione che è fondamentalmente tutta una classe può contenere una regione interiore di una classe diversa, come illustrato nella Figura 3.8 (d). È possibile consentire la nidificazione "dentro il nidificatore" in modo che la regione interna possa contenere la propria "regione interna" di una classe diversa, forse la classe originale della regione esterna ". Questo è analogo a consentire alle regole di avere eccezioni e eccezioni alle eccezioni, come nella sezione 3.5.
  Vale la pena sottolineare un leggero pericolo per la tecnica di visualizzazione dell'apprendimento basato su istanze in termini di confini nello spazio di esempio: fa l'ipotesi implicita che 'gli attributi sono numerici' piuttosto che nominali '. Se i vari valori che 'un attributo nominale' possono avere su 'una linea, le generalizzazioni che coinvolgono un segmento di quella' riga non avrebbero senso ': ogni test comporta un valore per l'attributo o tutti i valori per esso (O forse un sottoinsieme arbitrario di valori). Anche se è possibile "più o meno" facilmente immaginare l'estensione degli esempi nella Figura 3.8 a diverse dimensioni, è molto più difficile immaginare come le regole che implicano 'attributi nominali' appariranno nello spazio di istanze multidimensionali. Molte situazioni di "learning machine" coinvolgono numerosi attributi, e le nostre intuizioni tendono a portare a fuori strada quando si estendono a "spazi di grande dimensione".

 Clusters

 Quando si istruiscono i cluster piuttosto che 'un classificatore', l'output ha la forma di un diagramma che mostra come le istanze appartengono al cluster. Nel caso più semplice, questo comporta l'associazione di un numero di clusters ad ogni istanza, che potrebbe essere rappresentato posizionando le istanze in due dimensioni e partizionando lo spazio per mostrare ciascun cluster, come illustrato nella figura 3.9 (a).
 Alcuni algoritmi di cluster permettono ad un'istanza di appartenere a più di un cluster, in modo che il diagramma potrebbe posizionare le istanze in due dimensioni e sottotitoli "overlay" che rappresentano ciascun cluster "un diagramma Venn". Alcuni algoritmi associano istanze con i cluster probabilmente anziché categoricamente. In questo caso, per ogni istanza c'è una probabilità o un grado di adesione con cui appartiene a ciascuno dei 'cluster'. Questo è mostrato in Figura 3.9 (c). Questa particolare associazione deve essere probabilistica, quindi i numeri per ciascun esempio si sommeranno a uno anche se questo non è sempre il caso. Altri algoritmi producono una struttura gerarchica di cluster in modo che al livello superiore lo spazio di istanza si divide in pochi cluster, ognuno dei quali divide in 'suoi sottogruppi' al livello successivo e così via.
 In questo caso viene utilizzato un diagramma come quello della figura 3.9 (d), in cui gli elementi riuniti a livelli inferiori sono più cluster di quelli riuniti a livelli superiori. Diagrammi come questo sono chiamati dendrograms. Questo termine significa la stessa cosa dei diagrammi ad albero (la parola greca dendron significa "un albero"), ma nel raggruppare la versione più esotica sembra essere preferita, forse perché le specie biologiche sono un'area primaria di applicazione per le tecniche di clustering e le antiche lingue Sono spesso utilizzati per la denominazione in biologia.
 Il clustering è spesso seguito da uno stadio in cui viene determinato un insieme di decisioni o regole che alloca ciascuna istanza al cluster in cui appartiene. Quindi, l'operazione di clustering è solo un passo verso una descrizione strutturale.

Ulteriori letture

 La rappresentazione della conoscenza è un argomento fondamentale dell'intelligenza artificiale classica ed è ben rappresentata da una serie completa di documenti curati da Brachman e Levesque (1985). Tuttavia, questi sono i modi per rappresentare la conoscenza artigianale, non appresa e il tipo di rappresentazioni che possono essere apprese dagli esempi sono piuttosto rudimentali in confronto. In particolare, le carenze delle regole propositive, che nella logica sono definite il calcolo proposizionale e il potere extra espressivo delle regole relazionali o del calcolo predicato, sono ben descritte in introduzioni alla logica come quella del capitolo 2 del libro Di Genesereth e Nilsson (1987).
 Abbiamo menzionato il problema di affrontare il conflitto tra diverse regole. Sono stati sviluppati diversi modi per far questo, chiamati strategie di risoluzione dei conflitti, per essere utilizzati con sistemi di programmazione basati su regole. Questi sono descritti nei libri sulla programmazione basata su regole, come quella di Brownstown et al. (1985). Ancora, però, sono progettati per essere utilizzati con set di regole artigianali piuttosto che da quelle che sono state apprese. L'uso di regole artigianali con eccezioni per un grande set di dati è stato studiato da Gaines e Compton (1995) e Richards e Compton (1998) descrivono il loro ruolo come alternativa all'ingegneria classica della conoscenza.
 Ulteriori informazioni sui diversi stili di rappresentazione di concetti possono essere trovati nei documenti che descrivono i metodi di apprendimento della macchina per concludere concetti da esempi e questi sono trattati nella sezione Ulteriori lettura del capitolo 4 e nelle sezioni di discussione del capitolo 6.