Algorytm ID3 - ID3 algorithm

Potencjalne drzewo decyzyjne generowane przez ID3. Atrybuty są uporządkowane jako węzły dzięki możliwości klasyfikowania przykładów. Wartości atrybutów są reprezentowane przez gałęzie.

W uczeniu się drzew decyzyjnych , ID3 ( Iterative Dichotomiser 3 ) to algorytm wynaleziony przez Rossa Quinlana, używany do generowania drzewa decyzyjnego na podstawie zbioru danych. ID3 jest prekursorem algorytmu C4.5 i jest zwykle używany w domenach uczenia maszynowego i przetwarzania języka naturalnego .

Algorytm

Algorytm ID3 zaczyna się od oryginalnego zestawu jako węzła głównego . Przy każdej iteracji algorytmu iteruje on przez każdy nieużywany atrybut zbioru i oblicza entropię lub zysk informacyjny tego atrybutu. Następnie wybiera atrybut, który ma najmniejszą wartość entropii (lub największy przyrost informacji). Zbiór jest następnie dzielony lub partycjonowany według wybranego atrybutu w celu utworzenia podzbiorów danych. (Na przykład węzeł można podzielić na węzły potomne na podstawie podzbiorów populacji, których wiek jest krótszy niż 50, między 50 a 100 i większymi niż 100.) Algorytm kontynuuje powtarzanie dla każdego podzbioru, biorąc pod uwagę tylko atrybuty nigdy wybrane wcześniej. ${\ displaystyle S}$ ${\ displaystyle S}$ ${\ displaystyle \ mathrm {H} {(S)}}$ ${\ Displaystyle IG (S)}$ ${\ displaystyle S}$

Rekurencja w podzbiorze może zostać zatrzymana w jednym z następujących przypadków:

każdy element w podzbiorze należy do tej samej klasy; w takim przypadku węzeł zostaje przekształcony w węzeł liścia i oznaczony klasą przykładów.
nie ma więcej atrybutów do wybrania, ale przykłady nadal nie należą do tej samej klasy. W tym przypadku węzeł jest węzłem liścia i jest oznaczony najpopularniejszą klasą przykładów w podzbiorze.
w podzbiorze nie ma przykładów , co ma miejsce, gdy nie znaleziono żadnego przykładu w zestawie nadrzędnym pasującym do określonej wartości wybranego atrybutu. Przykładem może być nieobecność osoby w populacji powyżej 100 lat. Następnie tworzony jest węzeł liścia i oznaczany najpopularniejszą klasą przykładów w zestawie węzłów nadrzędnych.

W całym algorytmie budowane jest drzewo decyzyjne, w którym każdy węzeł nieterminalny (węzeł wewnętrzny ) reprezentuje wybrany atrybut, według którego dane zostały podzielone, a węzły końcowe (węzły liściaste) reprezentują etykietę klasy ostatniego podzbioru tej gałęzi.

Podsumowanie

Oblicz entropię każdego atrybutu zbioru danych . ${\ displaystyle a}$ ${\ displaystyle S}$
Podziel („split”) zbiór na podzbiory za pomocą atrybutu, dla którego uzyskana entropia po podziale jest zminimalizowana ; lub, równoważnie, zysk informacji jest maksymalny . ${\ displaystyle S}$
Utwórz węzeł drzewa decyzyjnego zawierający ten atrybut.
Powtarzaj na podzbiorach przy użyciu pozostałych atrybutów.

Pseudo kod

ID3 (Examples, Target_Attribute, Attributes)
    Create a root node for the tree
    If all examples are positive, Return the single-node tree Root, with label = +.
    If all examples are negative, Return the single-node tree Root, with label = -.
    If number of predicting attributes is empty, then Return the single node tree Root,
    with label = most common value of the target attribute in the examples.
    Otherwise Begin
        A ← The Attribute that best classifies examples.
        Decision Tree attribute for Root = A.
        For each possible value,  $v i$ , of A,
            Add a new tree branch below Root, corresponding to the test A =  $v i$ .
            Let Examples( $v i$ ) be the subset of examples that have the value  $v i$  for A
            If Examples( $v i$ ) is empty
                Then below this new branch add a leaf node with label = most common target value in the examples
            Else below this new branch add the subtree ID3 (Examples( $v i$ ), Target_Attribute, Attributes – {A})
    End
    Return Root

Nieruchomości

Drzewo decyzyjne generowane przez ID3 używane do określenia, czy dana para nukleotydów w sekwencji pre-mRNA odpowiada miejscu splicingu mRNA. Wykazano, że to drzewo ma 95% poprawny współczynnik prognozowania.

ID3 nie gwarantuje optymalnego rozwiązania. Może zbiegać się z lokalną optymalnością . Wykorzystuje zachłanną strategię , wybierając najlepszy lokalnie atrybut do podziału zestawu danych w każdej iteracji. Na optymalność algorytmu można poprawić za pomocą Backtracking podczas poszukiwania drzewa decyzyjnego optymalnym kosztem możliwie trwa dłużej.

ID3 może przekroczyć dane szkoleniowe. Aby uniknąć nadmiernego dopasowania, należy preferować mniejsze drzewa decyzyjne, a nie większe. Algorytm ten zwykle tworzy małe drzewa, ale nie zawsze tworzy najmniejsze możliwe drzewo decyzyjne.

ID3 jest trudniejsze w użyciu na danych ciągłych niż na danych faktoryzowanych (dane faktoryzowane mają dyskretną liczbę możliwych wartości, co zmniejsza liczbę możliwych punktów rozgałęzienia). Jeśli wartości któregokolwiek z atrybutów są ciągłe , to jest o wiele więcej miejsc, w których można podzielić dane dotyczące tego atrybutu, a poszukiwanie najlepszej wartości do podziału może być czasochłonne.

Stosowanie

Algorytm ID3 jest używany przez uczenie na zestawie danych w celu utworzenia drzewa decyzyjnego, które jest przechowywane w pamięci . W czasie wykonywania to drzewo decyzyjne jest używane do klasyfikowania nowych przypadków testowych ( wektorów cech ) poprzez przechodzenie przez drzewo decyzyjne przy użyciu cech odniesienia, aby dotrzeć do węzła liścia. Klasa tego węzła końcowego to klasa, do której klasyfikowany jest przypadek testowy. ${\ displaystyle S}$

Metryki ID3

Entropia

Entropia jest miarą wielkości niepewności w zbiorze ( danych) (tj. Entropia charakteryzuje zbiór (danych) ). ${\ displaystyle \ mathrm {H} {(S)}}$ ${\ displaystyle S}$ ${\ displaystyle S}$

{\ Displaystyle \ mathrm {H} {(S)} = \ suma _ {x \ w X} {- p (x) \ log _ {2} p (x)}}

Gdzie,

${\ displaystyle S}$ $S$ - Bieżący zbiór danych, dla którego obliczana jest entropia
- Zmienia się to na każdym etapie algorytmu ID3, albo na podzbiór poprzedniego zestawu w przypadku podziału atrybutu, albo na „siostrzaną” partycję rodzica w przypadku wcześniejszego zakończenia rekurencji.
${\ displaystyle X}$ - Zestaw zajęć w ${\ displaystyle S}$
${\ Displaystyle p (x)}$ - The odsetek od liczby elementów w klasie do liczby elementów w zestawie ${\ displaystyle x}$ ${\ displaystyle S}$

Kiedy zbiór jest doskonale sklasyfikowany (tzn. Wszystkie elementy są tej samej klasy). ${\ Displaystyle \ mathrm {H} {(S)} = 0}$ ${\ displaystyle S}$ ${\ displaystyle S}$

W ID3 entropia jest obliczana dla każdego pozostałego atrybutu. Atrybut o najmniejszej entropii jest używany do podziału zestawu w tej iteracji. Entropia w teorii informacji działań, jak jest dużo informacji oczekiwanych można zyskać na pomiar jest zmienną losową ; jako taki może również służyć do ilościowego określenia kwoty, do której rozkład wartości ilości jest nieznany. Stałą ilość wynosi zero entropii, a ich rozmieszczenie jest doskonale znane . Natomiast zmienna losowa o równomiernym rozkładzie ( jednorodna dyskretnie lub w sposób ciągły ) maksymalizuje entropię. Dlatego im większa entropia w węźle, tym mniej informacji jest znanych na temat klasyfikacji danych na tym etapie drzewa; a zatem, tym większy potencjał poprawy klasyfikacji w tym miejscu. ${\ displaystyle S}$

Jako takie, ID3 jest chciwy heurystyczny wykonując najpierw najlepszy wyszukiwania dla lokalnie optymalnych wartości entropii. Jego dokładność można poprawić, wstępnie przetwarzając dane.

Zdobywanie informacji

Zysk informacyjny jest miarą różnicy w entropii od okresu przed podziałem zbioru na atrybut . Innymi słowy, ile niepewności zostało zmniejszone po rozdzieleniu ustawionym na atrybut . ${\ Displaystyle IG (A)}$ ${\ displaystyle S}$ ${\ displaystyle A}$ ${\ displaystyle S}$ ${\ displaystyle S}$ ${\ displaystyle A}$

{\ Displaystyle IG (S, A) = \ operatorname {H} {(S)} - \ suma _ {T \ w T} p (t) \ operatorname {H} {(t)} = \ operatorname {H} {(S)} - \ mathrm {H} {(S | A)}.}

Gdzie,

${\ Displaystyle \ mathrm {H} (S)}$ - Entropia zbioru ${\ displaystyle S}$
${\ displaystyle T}$ - Podzbiory utworzone z podziału zestawu według atrybutu takie, że ${\ displaystyle S}$ ${\ displaystyle A}$ ${\ displaystyle S = \ bigcup _ {t \ in T} t}$
${\ displaystyle p (t)}$ - stosunek liczby elementów do liczby elementów w zestawie ${\ displaystyle t}$ ${\ displaystyle S}$
${\ Displaystyle \ mathrm {H} (t)}$ - Entropia podzbioru ${\ displaystyle t}$

W ID3 można obliczyć zysk informacji (zamiast entropii) dla każdego pozostałego atrybutu. Atrybut z największym zyskiem informacyjnym służy do dzielenia zestawu w tej iteracji. ${\ displaystyle S}$

Zobacz też

Bibliografia

^ Quinlan, JR 1986. Indukcja drzew decyzyjnych. Mach. Uczyć się. 1, 1 (marzec 1986), 81–106
^ Taggart, Allison J; DeSimone, Alec M; Shih, Janice S; Filloux, Madeleine E; Fairbrother, William G (2012-06-17). „Mapowanie na dużą skalę punktów rozgałęzienia w transkryptach ludzkiego pre-mRNA in vivo” . Nature Structural & Molecular Biology . 19 (7): 719–721. doi : 10.1038 / nsmb.2327 . ISSN 1545-9993 . PMC 3465671 . PMID 22705790 .

Dalsza lektura

Mitchell, Tom Michael (1997). Uczenie maszynowe . Nowy Jork, NY: McGraw-Hill. str. 55 -58. ISBN 0070428077 . OCLC 36417892 .
Grzymala-Busse, Jerzy W. (luty 1993). „Wybrane algorytmy uczenia maszynowego na podstawie przykładów” (PDF) . Fundamenta Informaticae . 18 (2): 193–207 - przez ResearchGate.

Zewnętrzne linki

Seminaria - http://www2.cs.uregina.ca/
Opis i przykłady - http://www.cise.ufl.edu/
Opis i przykłady - http://www.cis.temple.edu/
Drzewa decyzyjne i klasyfikacja partii politycznych

[1] Quinlan, JR 1986. Indukcja drzew decyzyjnych. Mach. Uczyć się. 1, 1 (marzec 1986), 81–106

[2] Taggart, Allison J; DeSimone, Alec M; Shih, Janice S; Filloux, Madeleine E; Fairbrother, William G (2012-06-17). „Mapowanie na dużą skalę punktów rozgałęzienia w transkryptach ludzkiego pre-mRNA in vivo” . Nature Structural & Molecular Biology . 19 (7): 719–721. doi : 10.1038 / nsmb.2327 . ISSN 1545-9993 . PMC 3465671 . PMID 22705790 .

Languages

In other projects