Na čem je založeno ID3?

Algoritmus rozhodovacího stromu je stěžejní technologií v dolování klasifikace dat a algoritmus ID3 (Iterativní dichotomizér 3) je slavný, který dosáhl dobrých výsledků v oblasti dolování klasifikací. Přesto existují určité nevýhody ID3, jako jsou atributy zkreslující více hodnot, vysoká složitost, velká měřítka atd. V tomto článku je navržen vylepšený algoritmus ID3, který kombinuje zjednodušenou informační entropii založenou na různých vahách se stupněm koordinace v hrubé sadě. teorie. Tradiční algoritmus ID3 a navrhovaný algoritmus jsou spravedlivě porovnány pomocí tří běžných vzorků dat a také klasifikátorů rozhodovacího stromu. Je ukázáno, že navrhovaný algoritmus má lepší výkon v době běhu a stromové struktuře, ale ne v přesnosti než algoritmus ID3, pro první dvě sady vzorků, které jsou malé. U třetí sady vzorků, která je velká, navrhovaný algoritmus zlepšuje algoritmus ID3 pro celou dobu běhu, stromovou strukturu a přesnost. Experimentální výsledky ukazují, že navržený algoritmus je efektivní a životaschopný.

1. Úvod

V databázi je uloženo velké množství dat, která obsahují mnoho potenciálních a cenných informací. Pokud lze z databáze vytáhnout velké množství skrytých informací, vytvoří se další potenciální hodnota. Tváří v tvář výzvě výše uvedeného problému se objevily technologie dolování dat [1,2] a ukázaly silnou vitalitu. Data mining zahrnuje několik důležitých technologií, jako je klasifikace [3], shlukování [4], regrese [5] atd. Technologie klasifikačního dolování se mezi technologiemi data miningu stává nejaktivnějším a nejvyspělejším směrem výzkumu umožňujícím úspěšné aplikace. Klasifikační dolování [6] lze použít k objevování užitečných informací z velkého množství dat uložených ve velkém počtu oborů, jako jsou nemocnice, akcie, bankovnictví atd. Pro nemocnici je například důležité přesně předvídat délku pobytu. (LOS) a Ref. [7] ukázaly, že klasifikační těžební technologie byla nejen přínosná pro řešení omezených lůžkových zdrojů, ale byla také užitečná pro personál nemocnice při implementaci lepšího plánování a řízení nemocničních zdrojů. V Ref. [8], aby bylo možné snadno získat výnosy akcií na akciovém trhu, byly v predikci akciového trhu použity různé klasifikátory a přesnost predikce byla běžně splněna. Ref. [9] použili k predikci výnosů akcií dva typy souborů klasifikátorů. Problém rozpoznávání bankovek je pro zaměstnance banky velmi důležitý. Ref. [10] představili neuroklasifikátory k řešení velkého problému. Ref. [11] představili přístup klasifikace ANN, který by mohl být použit k detekci včasných varovných signálů potenciálních selhání bankovních sektorů.

Metody rozhodovacího stromu [12,13], metody neuronové sítě [14] a statistické metody [15,16] jsou běžné klasifikační algoritmy používané výzkumníky v oblasti dolování klasifikací. V různých oblastech se používá velké množství algoritmů rozhodovacího stromu, jako je Iterative Dichotomizer 3 (ID3) [17], C4.5 [18] a Classification And Regression Tree (CART) [19]. Většina metod rozhodovacího stromu je vyvinuta z metody ID3. Například metoda C4.5 [20] představila optimální atribuční výběrový standard (gain ratio) [21] namísto optimálního atribučního výběrového standardu (informační zisk) v ID3; Metoda CART převzala Giniho index [22] jako výběrový standard optimální atribuce. Přestože tyto vylepšené metody rozhodovacího stromu přináší mnoho výhod, existuje také velký prostor pro zlepšení.

Algoritmus ID3 se používá jako obecná klasifikační funkce a má mnoho výhod, jako jsou srozumitelná rozhodovací pravidla a intuitivní model. Nicméně ID3 má také některé nevýhody, například: (1) existuje problém vícehodnotového zkreslení v procesu výběru atributu [23], ale atribuce, která má více hodnot, není vždy optimální; (2) není snadné vypočítat informační entropii [24,25] pomocí logaritmických algoritmů, což stojí mnoho času; a (3) velikost stromu se obtížně kontroluje [26] a strom s velkou velikostí vyžaduje mnoho dlouhých klasifikačních pravidel.

Za účelem vyřešení výše uvedených problémů je zde navrženo optimalizované schéma založené na metodě ID3. Za prvé, aby se vyřešil defekt vícehodnotového zkreslení způsobeného rovnicí informačního zisku v ID3, zvolil C4.5 místo rovnice informačního zisku poměr zesílení, ale tato metoda zahrnovala mnoho logaritmických operací, které ovlivní celé představení. Tento článek představuje novou metodu přímým přidáním různých vah pro rovnici zisku informace pro každou atribuci kandidáta, a tento způsob nejen činí výběr optimálního atributu rozumnějším, ale má také malý vliv na rychlost běhu. Za druhé, jak všichni víme, ve dvou ekvivalentních vzorcích (např. logaritmický výraz a čtyři aritmetické operace) je rychlost výpočtu logaritmického výrazu pomalejší než u čtyř aritmetických operací, které zahrnují pouze sčítání, odečítání, násobení a dělení. [27]. Tento článek tedy mění logaritmické vyjádření informačního zisku ID3 do podoby čtyř aritmetických operací zavedením Taylorova vzorce pro vývoj v reálném čase. Za třetí, tento článek zavádí stupeň koordinace [28,29] v hrubé teorii množin [30] pro řízení velikosti rozhodovacího stromu o jeden krok, protože většina současných metod rozhodovacího stromu používá strategii prořezávání ke zjednodušení stromové struktury, což může dokončit celý proces. ve dvou krocích. Nakonec tento článek navrhuje novou metodu pro sestavení stručnějšího a rozumnějšího modelu rozhodovacího stromu s nižší výpočetní složitostí. Výsledky experimentu nakonec ukazují, že navrhovaný algoritmus má lepší výkon než ID3.

Zbytek tohoto dokumentu je uspořádán následovně: Část 2 popisuje kroky budování rozhodovacího stromu založeného na algoritmu ID3 a také některé výhody a nevýhody algoritmu ID3. Část 3 se zabývá některými nevýhodami metody ID3 navrhovaného algoritmu, který kombinuje zjednodušenou informační entropii se stupněm koordinace v hrubé teorii množin. Část 4 představuje algoritmus hodnocení použitý v tomto článku. V části 5 jsou rozdíly mezi tradičním algoritmem ID3 a navrženým algoritmem porovnány a analyzovány pomocí experimentů. Závěrečné komentáře a závěry jsou uvedeny v části 6.

2. Popis algoritmu ID3

Algoritmus ID3, tradiční algoritmus klasifikace rozhodovacího stromu, představil Ross Quinlan [31] v roce 1986. ID3 využívá získávání informací jako metodu výběru atributů. Hlavní struktura budování rozhodovacího stromu založeného na algoritmu ID3 je shrnuta v Algoritmu 1.

Uveďme některé zápisy. Informační entropie a informační zisk jsou definovány:
E n t ( D ) = − ∑ d = 1 κ p k log 2 p k ,
G a i n ( D , a ) = E n t ( D ) − ∑ v = 1 V D V D , E n t ( D V )

kde D = ( x 1 , y 1 ), ( x 2 , y 2 ) , ⋯ , ( x m , y m ) představuje sadu trénovacích vzorků a D představuje počet trénovacích vzorků. A = a 1 , a 2 , ⋯ , ad označuje množinu atributů D a d = 1 , 2 , ⋯ , κ . p k ( k = 1 , 2 , ⋯ , D ) představuje pravděpodobnost , že n -tice v trénovací množině S patří do třídy C i . Homogenní soubor dat se skládá pouze z jedné třídy. V homogenním souboru dat je pk 1 a log2(pk) je nula. Entropie homogenního souboru dat je tedy nulová. Za předpokladu, že existuje V různých hodnot (V = a1, a2, ⋯, aV) v atributu ai, Di představuje podmnožiny vzorků každé hodnoty a Di představuje počet aktuálních vzorků.

Model rozhodovacího stromu, stromový graf znázorněný na obrázku 1, lze získat metodou ID3 popsanou v Algoritmu 1 a model rozhodovacího stromu obecně zahrnuje jeden kořenový uzel, několik vnitřních uzlů a několik listových uzlů, kde kořenový uzel představuje celou ukázkovou sadu, vnitřní uzel představuje atribut a listový uzel představuje označení třídy. Cesta od kořenového uzlu ke každému listovému uzlu odpovídá určené sekvenci.

Klasifikace velkého množství dat pomocí algoritmu ID32 má mnoho výhod [3], jako je silná intuitivní povaha, snadná rozložitelnost a tak dále, ale algoritmus ID3 má také některé nevýhody, například:

Při použití informačního zisku jako metody výběru atributu má ID3 tendenci vybrat si atribut, který má více hodnot [33], protože hodnota rovnice informačního zisku tohoto typu atribuce bude větší než u ostatních.

Jak je všem známo, pokud jsou logaritmický výraz a čtyři aritmetické operace dva ekvivalentní výrazy jedné funkce, je doba běhu čtyř aritmetických operací rychlejší než u logaritmického výrazu [34]. V metodě ID3 existuje mnoho logaritmických výpočtů v procesu výběru optimální atribuce, což zabere mnoho času pro výpočet informačního zisku. Pokud se logaritmický výraz změní čtyřmi aritmetickými operacemi, doba běhu v celém procesu stavebního stromu se rychle zlepší.

Je těžké řídit velikost stromu v procesu vytváření rozhodovacího stromu. V současné době většina vylepšených metod používá metody prořezávání [35], aby se zabránilo jevu nadměrného přizpůsobení, což povede k tomu, že celý proces vytváření modelů rozhodovacích stromů bude dokončen ve dvou krocích (tj. modelování a prořezávání). Pokud je stručný rozhodovací strom vytvořen v jednom kroku, ušetří to mnoho času.

Záměrem příspěvku je vyřešit výše uvedené nevýhody a navrhnout vylepšenou metodu pro sestavení modelu rozhodovacího stromu. Vylepšený algoritmus ID3 je navržen tak, aby generoval stručnější model rozhodovacího stromu v kratším čase a aby zvolil rozumnější optimální atribut v každém interním uzlu.

3. Vylepšený algoritmus ID3

Tato část představuje odpovídající řešení založená na výše uvedených problémech. Je navržena nová metoda, která spojuje tato tři řešení dohromady a lze ji použít k vytvoření výstižnějšího rozhodovacího stromu za kratší dobu než ID3. Tabulka 1 je malá sada trénovacích vzorků, která se používá k podrobnému zobrazení rozdílů mezi tradičním algoritmem ID3 a navrhovaným.

3.1. Řešení zjednodušení získávání informací

3.1.1. Odvozovací proces zjednodušování informační entropie

Volba optimálního atributu v algoritmu ID3 je založena na rovnici (2), ale logaritmický algoritmus zvyšuje složitost výpočtu. Pokud najdeme jednodušší výpočetní vzorec, rychlost vytváření rozhodovacího stromu by byla rychlejší. Proces zjednodušení je organizován takto:

Jak je všem známo, ve dvou ekvivalentních výrazech je rychlost běhu logaritmického výrazu pomalejší než u čtyř aritmetických operací. Pokud je logaritmický výraz v rovnici (2) nahrazen čtyřmi aritmetickými operacemi, rychlost běhu celého procesu vytváření rozhodovacího stromu se rychle zlepší.

Podle teorie diferenciace v pokročilé matematice může význam Taylorova vzorce zjednodušit komplexní funkce. Taylorův vzorec je v libovolném bodě rozšířená forma a Maclaurinův vzorec je funkce, kterou lze v bodě nula rozšířit do Taylorovy řady. Obtížnost při výpočtu informační entropie o algoritmu ID3 lze snížit na základě aproximačního vzorce Maclaurinova vzorce, který je užitečný pro vytvoření rozhodovacího stromu v krátkém časovém období. Taylorův vzorec je dán takto:

f ( x ) = f ( x 0 ) + f ( 1 ) ( x 0 ) ( x − x 0 ) + o ( x − x 0 ) .

Za okolností x = 0 se rovnice (3) změní do následujícího tvaru (také nazývaného Maclaurinův vzorec):

f ( x ) = f ( 0 ) + f ( 1 ) ( 0 ) x + f ( 2 ) ( 0 ) 2 ! x 2 + , ⋯ , + f ( n ) ( 0 ) n ! x n + R ( x ),