Získání informací v rozhodovacích stromech - Information gain in decision trees

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Zisk informací v rozhodovacích stromech"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Prosince 2009) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v teorie informace a strojové učení, zisk informací je synonymem pro Kullback – Leiblerova divergence; the množství informací získal asi a náhodná proměnná nebo signál z pozorování jiné náhodné proměnné. V kontextu rozhodovacích stromů se však tento termín někdy používá synonymně s vzájemné informace, který je podmíněná očekávaná hodnota Kullback – Leiblerovy divergence univariate rozdělení pravděpodobnosti jedné proměnné z podmíněné rozdělení této proměnné daný ten druhý.

Informační zisk náhodné proměnné X získané z pozorování a náhodná proměnná A brát hodnotu ${ displaystyle A = a}$ je definováno

Kullback – Leiblerova divergence předchozí distribuce ${ displaystyle P_ {X} {(x | I)}}$ pro x z zadní distribuce ${ displaystyle P_ {X | A} {(x | a)}}$ pro X daný A.

The očekávaná hodnota informačního zisku je vzájemné informace ${ displaystyle I (X; A)}$ z X a A - tj. Snížení entropie z X dosaženo učením se stavu náhodná proměnná A.

Ve strojovém učení lze tento koncept použít k definování preferované posloupnosti atributů, které se mají zkoumat, aby se nejrychleji zúžil stav X. Taková posloupnost (která závisí na výsledku vyšetřování předchozích atributů v každé fázi) se nazývá a rozhodovací strom a aplikovány v oblasti strojového učení známé jako učení rozhodovacího stromu. Obvykle by měl být preferován atribut s vysokou vzájemnou informací před jinými atributy.^{[proč? ]}

Obecná definice

Obecně lze říci, že očekávaný informační zisk je změna v informační entropie Η z předchozího stavu do stavu, který bere určité informace, jak jsou uvedeny:

${ displaystyle IG (T, a) = mathrm {H} {(T)} - mathrm {H} {(T | a)},}$

kde ${ displaystyle mathrm {H} {(T | a)}}$ je podmíněná entropie z ${ displaystyle T}$ vzhledem k hodnotě atribut ${ displaystyle a}$.

Formální definice

Nechat ${ displaystyle T}$ označit a soubor příkladů školení, každý z formulářů ${ displaystyle ({ textbf {x}}, y) = (x_ {1}, x_ {2}, x_ {3}, ..., x_ {k}, y)}$ kde ${ displaystyle x_ {a} ve vals (a)}$ je hodnota ${ displaystyle a ^ { text {th}}}$ atribut nebo Vlastnosti z příklad ${ displaystyle { textbf {x}}}$ a y je odpovídající označení třídy. Získání informací pro atribut ${ displaystyle a}$ je definován v pojmech Shannonova entropie ${ displaystyle mathrm {H} (-)}$ jak následuje. Pro hodnotu ${ displaystyle v}$ převzato atributem ${ displaystyle a}$, nechť

být definován jako soubor tréninkových vstupů ${ displaystyle T}$ pro který atribut ${ displaystyle a}$ je rovný ${ displaystyle v}$. Pak získají informace ${ displaystyle T}$ pro atribut ${ displaystyle a}$ je rozdíl mezi apriórní Shannonovou entropií ${ displaystyle mathrm {H} (T)}$ výcvikové sady a podmíněná entropie ${ displaystyle mathrm {H} {(T | a)}}$.

${ displaystyle IG (T, a) = mathrm {H} (T) - mathrm {H} (T | a)}$

The vzájemné informace se rovná celkové entropii pro atribut, pokud je pro každou z hodnot atributu jedinečná klasifikace lze provést pro atribut result. V tomto případě jsou relativní entropie odečtené od celkové entropie 0. Konkrétně hodnoty ${ displaystyle v ve vals (a)}$ definuje a rozdělit údajů tréninkové sady ${ displaystyle T}$ do vzájemně se vylučující a all-inclusive podmnožiny, vyvolání a kategorické rozdělení pravděpodobnosti ${ textový styl P_ {a} {(v)}}$ na hodnotách ${ textstyle v ve vals (a)}$ atributu ${ displaystyle a}$. Je uvedeno rozdělení ${ textstyle P_ {a} {(v)}: = { frac {| S_ {a} {(v)} |} {| T |}}}$. V této reprezentaci získává informace ${ displaystyle T}$ daný ${ displaystyle a}$ lze definovat jako rozdíl mezi bezpodmínečnou Shannonovou entropií z ${ displaystyle T}$ a očekávaná entropie ${ displaystyle T}$ podmíněno ${ displaystyle a}$, Kde očekávaná hodnota se bere s ohledem na indukované rozdělení na hodnotách ${ displaystyle a}$.

Nevýhody

Ačkoli je zisk informací obvykle dobrým měřítkem pro rozhodování o relevantnost atributu, není to dokonalé. Pozoruhodný problém nastává, když je zisk informací aplikován na atributy, které mohou nabývat velkého počtu odlišných hodnot. Předpokládejme například, že se buduje rozhodovací strom pro některá data popisující zákazníky firmy. Získání informací se často používá k rozhodnutí, které z atributů jsou nejrelevantnější, takže je lze otestovat poblíž kořene stromu. Jedním ze vstupních atributů může být číslo kreditní karty zákazníka. Tento atribut má vysoké vzájemné informace, protože jednoznačně identifikuje každého zákazníka, ale my ano ne chcete zahrnout do rozhodovacího stromu: rozhodnutí, jak zacházet se zákazníkem na základě čísla jejich kreditní karty, je nepravděpodobné, že by se zobecnilo na zákazníky, které jsme ještě neviděli (nadměrné vybavení ).

Abychom tomuto problému čelili, Ross Quinlan místo toho zvolit atribut s nejvyšší poměr zisku informací z atributů, jejichž informační zisk je průměrný nebo vyšší.^[1] To upřednostňuje rozhodovací strom proti zvažování atributů s velkým počtem odlišných hodnot, aniž by to poskytovalo nespravedlivou výhodu atributům s velmi nízkou informační hodnotou, protože informační hodnota je vyšší nebo rovná informačnímu zisku.^[2]

Příklad

Použijme tuto tabulku jako datovou sadu a použijeme získaný údaj ke klasifikaci, pokud je pacient nemocný nemocí. Pacienti klasifikovaní jako True (T) jsou nemocní a pacienti klasifikovaní jako False (F) nejsou nemocní. Aktuálně jsme v kořenovém uzlu stromu a musíme zvážit všechny možné rozdělení pomocí dat.

Datová sada pro školení

Trpěliví	Příznak A	Příznak B	Příznak C.	Klasifikace
1	T	T	T	F
2	T	F	T	T
3	F	F	T	T
4	F	T	T	F
5	F	T	F	T

Rozdělení kandidátů se určuje na základě pohledu na každou proměnnou, která tvoří pacienta, a na to, jaké mohou být jeho stavy. V tomto příkladu mohou být všechny příznaky buď True (T) nebo False (F).

Rozdělení kandidátů

Rozdělit	Dětské uzly
1	Příznak A = T, Příznak A = F
2	Příznak B = T, příznak B = F
3	Příznak C = T, Příznak C = F

Nyní pro rozdělení č. 1 určujeme entropii před rozdělením, které se zjistí pomocí klasifikace každého pacienta.

${ displaystyle H (T) = - 3/5 log _ {2} (3/5) -2/5 log _ {2} (2/5) = 0,971}$

Podmíněná entropie rozdělení # 1 je určena vyhledáním entropie každého stavu symptomu A a jejich kombinací.

${ Displaystyle H (T | a) = 2/5 (-1/2 log _ {2} (1/2) -1/2 log _ {2} (1/2)) + 3/5 ( -2/3 log _ {2} (2/3) -1/3 log _ {2} (1/3)) = 2/5 (1) +3/5 (0,918) = 0,951}$

Zisk informace lze poté určit nalezením rozdílu v předchozí entropii a podmíněné entropii.

${ displaystyle IG (T, a) = H (T) -H (T | a) = 0,971-0,951 = 0,02}$

Tyto kroky se opakují pro všechny rozdělení kandidátů, aby se získal jejich informační zisk. Všechny rozdělení kandidátů na uzel používá stejnou hodnotu pro ${ displaystyle H (T)}$.

Zisk informací o rozdělení kandidátů

Rozdělit	Zisk informací
1	0.020
2	0.419
3	0.171

Rozdělení kandidátů č. 2 má nejvyšší zisk informací, takže to bude nejpříznivější rozdělení pro kořenový uzel. V závislosti na spolehlivosti klasifikace podřízených uzlů lze na podřízené uzly použít zisk informací, ale nelze použít stejné rozdělení kandidátů.

Viz také

• Informační zisk šířeji
• Učení rozhodovacího stromu
• Informační obsah, výchozí bod teorie informace a základ Shannonova entropie
• Poměr zisku informací
• Algoritmus ID3
  • Algoritmus C4.5
• Průzkumná analýza

Reference

Další čtení

• Mitchell, Tom M. (1997). Strojové učení. Mc-Graw-Hill Companies, Inc. ISBN  978-0070428072.