Příklady algoritmu rozhodovacího stromu při dolování dat

decision tree algorithm examples data mining

Tento podrobný výukový program vysvětluje vše o algoritmu rozhodovacího stromu při dolování dat. Dozvíte se o příkladech rozhodovacího stromu, algoritmu a klasifikaci:

Podívali jsme se na pár Příklady dolování dat v našem předchozím tutoriálu v Série školení pro těžbu dat zdarma .

Těžba rozhodovacích stromů je typ techniky dolování dat, která se používá k vytváření klasifikačních modelů. Vytváří klasifikační modely ve formě stromové struktury, stejně jako její název. Tento typ těžby patří k výuce pod dohledem třídy.

V kontrolovaném učení je cílový výsledek již známý. Rozhodovací stromy lze použít pro kategorická i číselná data. Kategorické údaje představují pohlaví, rodinný stav atd., Zatímco číselné údaje představují věk, teplotu atd.

dvojnásobně propojená implementace seznamu c ++

Níže je uveden příklad rozhodovacího stromu s datovou sadou.

(obraz zdroj )

Co se naučíte:

• Jaké je použití rozhodovacího stromu?
• Klasifikační analýza
• Regresní analýza
• Jak funguje rozhodovací strom?
• Algoritmus indukce rozhodovacího stromu
• Indukce rozhodovacího stromu
• VOZÍK
• Indukce rozhodovacího stromu pro strojové učení: ID3
• Co je chamtivé rekurzivní binární rozdělení?
• Jak vybrat atributy pro vytvoření stromu?
  • # 1) Získávání informací
  • # 2) Zisk poměr
  • # 3) Giniho index
• Přetížení rozhodovacích stromů
• Co je to prořezávání stromů?
• Co je prediktivní modelování?
• Výhody klasifikace rozhodovacích stromů
• Nevýhody klasifikace rozhodovacích stromů
• Závěr
• Doporučené čtení

Jaké je použití rozhodovacího stromu?

Rozhodovací strom se používá k vytváření klasifikačních a regresních modelů. Používá se k vytváření datových modelů, které budou předpovídat štítky tříd nebo hodnoty pro rozhodovací proces. Modely jsou sestaveny z datové sady školení dodávané do systému (supervizované učení).

Pomocí rozhodovacího stromu můžeme vizualizovat rozhodnutí, která usnadňují pochopení, a jedná se tedy o populární techniku ​​dolování dat.

Klasifikační analýza

Klasifikace dat je forma analýzy, která vytváří model, který popisuje důležité proměnné třídy.Například, model vytvořený tak, aby kategorizoval žádosti o bankovní půjčky jako bezpečné nebo riskantní. Metody klasifikace se používají při strojovém učení a rozpoznávání vzorů.

Aplikace klasifikace zahrnuje detekci podvodů, lékařskou diagnózu, cílový marketing atd. Výstup problému klasifikace je považován za „režim“ všech sledovaných hodnot koncového uzlu.

Sleduje se dvoustupňový proces, kterým se vytvoří model klasifikace.

1. V prvním kroku, tj. Učení: Je sestaven klasifikační model založený na tréninkových datech.
2. Ve druhém kroku, tj. Klasifikaci, se zkontroluje přesnost modelu a poté se model použije ke klasifikaci nových dat. Zde uvedené štítky tříd mají podobu diskrétních hodnot, například „ano“ nebo „ne“, „bezpečné“ nebo „riskantní“.

Obecný přístup k modelům klasifikace budov je uveden níže:

(obraz zdroj )

Regresní analýza

Regresní analýza se používá pro predikci numerických atributů.

Číselné atributy se také nazývají spojité hodnoty. Model vytvořený k předpovědi spojitých hodnot namísto štítků tříd se nazývá regresní model. Výstupem regresní analýzy je „průměr“ všech pozorovaných hodnot uzlu.

Jak funguje rozhodovací strom?

Rozhodovací strom je supervizovaný učební algoritmus, který funguje jak pro diskrétní, tak pro spojité proměnné. Rozdělí datovou sadu na podmnožiny na základě nejvýznamnějšího atributu v datové sadě. O tom, jak rozhodovací strom identifikuje tento atribut a jak se toto rozdělení děje, rozhodují algoritmy.

Nejvýznamnější prediktor je označen jako kořenový uzel, rozdělení se provádí za účelem vytvoření subuzlů nazývaných rozhodovací uzly a uzly, které se dále nerozdělují, jsou terminální nebo listové uzly.

V rozhodovacím stromu je datová sada rozdělena na homogenní a nepřekrývající se oblasti. Sleduje přístup shora dolů, protože horní oblast prezentuje všechna pozorování na jednom místě, které se rozděluje na dvě nebo více větví, které se dále dělí. Tento přístup se také nazývá a chamtivý přístup protože bere v úvahu pouze aktuální uzel mezi zpracovanými bez zaměření na budoucí uzly.

Algoritmy rozhodovacího stromu budou pokračovat v provozu, dokud nebude dosaženo kritérií zastavení, jako je minimální počet pozorování atd.

Jakmile je vytvořen rozhodovací strom, mnoho uzlů může představovat odlehlé hodnoty nebo hlučná data. K odstranění nežádoucích dat se používá metoda prořezávání stromů. To zase zlepšuje přesnost klasifikačního modelu.

K zjištění přesnosti modelu se používá testovací sada skládající se z testovacích n-tic a štítků tříd. Procenta n-tic testovací sady jsou podle modelu správně klasifikovány, aby bylo možné určit přesnost modelu. Pokud se zjistí, že model je přesný, pak se používá ke klasifikaci datových n-tic, pro které nejsou známé popisky tříd.

Některé z algoritmů rozhodovacího stromu zahrnují Hunt's Algorithm, ID3, CD4.5 a CART.

Příklad vytvoření rozhodovacího stromu

(Příklad je převzat z konceptů dolování dat: Han a Kimber)

# 1) Krok učení: Údaje o tréninku jsou vloženy do systému, který má být analyzován klasifikačním algoritmem. V tomto příkladu je označení třídy atribut, tj. „Rozhodnutí o půjčce“. Model vytvořený z těchto tréninkových dat je reprezentován ve formě rozhodovacích pravidel.

# 2) Klasifikace: Testovací datová sada se přivádí do modelu, aby se zkontrolovala přesnost pravidla klasifikace. Pokud model poskytuje přijatelné výsledky, použije se na novou datovou sadu s neznámými proměnnými třídy.

Algoritmus indukce rozhodovacího stromu

Indukce rozhodovacího stromu

Indukce rozhodovacího stromu je metoda učení rozhodovacích stromů z tréninkové sady. Výcviková sada se skládá z atributů a štítků tříd. Aplikace indukce rozhodovacího stromu zahrnují astronomii, finanční analýzu, lékařskou diagnózu, výrobu a výrobu.

Rozhodovací strom je struktura podobná vývojovému diagramu, která je vytvořena z tréninkových n-tic. Datová sada je rozdělena na menší podmnožiny a je přítomna ve formě uzlů stromu. Stromová struktura má kořenový uzel, vnitřní uzly nebo rozhodovací uzly, listový uzel a větve.

Kořenový uzel je nejvyšší uzel. Představuje nejlepší atribut vybraný pro klasifikaci. Interní uzly rozhodovacích uzlů představují test atributu uzlu listu datové sady nebo koncového uzlu, který představuje označení klasifikace nebo rozhodnutí. Větve ukazují výsledek provedeného testu.

Některé rozhodovací stromy pouze mají binární uzly , To znamená přesně dvě větve uzlu, zatímco některé rozhodovací stromy jsou nebinární.

Obrázek níže ukazuje rozhodovací strom datové sady Titanic, který předpovídá, zda cestující přežije nebo ne.

(obraz zdroj )

VOZÍK

Model CART, tj. Modely klasifikace a regrese, je algoritmus rozhodovacího stromu pro vytváření modelů. Model rozhodovacího stromu, kde mají cílové hodnoty diskrétní povahu, se nazývá klasifikační modely.

Diskrétní hodnota je konečná nebo spočetně nekonečná množina hodnot, Například, věk, velikost atd. Modely, kde jsou cílové hodnoty reprezentovány spojitými hodnotami, jsou obvykle čísla, která se nazývají regresní modely. Spojité proměnné jsou proměnné s plovoucí desetinnou čárkou. Tyto dva modely se společně nazývají CART.

CART používá Gini Index jako klasifikační matici.

Indukce rozhodovacího stromu pro strojové učení: ID3

Na konci 70. a začátku 80. let byl J.Ross Quinlan výzkumníkem, který vytvořil algoritmus rozhodovacího stromu pro strojové učení. Tento algoritmus je známý jako ID3, Iterativní dichotomizátor . Tento algoritmus byl rozšířením koncepčních systémů učení popsaných E.B Huntem, J. a Marinem.

ID3 později přišel být známý jako C4.5. ID3 a C4.5 se při konstrukci rozhodovacích stromů řídí chamtivým přístupem shora dolů. Algoritmus začíná tréninkovou datovou sadou s popisky tříd, které jsou při vytváření stromu rozděleny do menších podmnožin.

# 1) Zpočátku existují tři parametry, tj. seznam atributů, metoda výběru atributů a datový oddíl . Seznam atributů popisuje atributy n-tic tréninkové sady.

#dva) Metoda výběru atributu popisuje metodu pro výběr nejlepšího atributu pro diskriminaci mezi n-ticemi. Metody používané pro výběr atributů mohou být buď Informační zisk nebo Gini index.

# 3) O struktuře stromu (binární nebo nebinární) rozhoduje metoda výběru atributů.

# 4) Při konstrukci rozhodovacího stromu začíná jako jediný uzel představující n-tice.

jak odstranit prvek z pole java

# 5) Pokud n-tice kořenového uzlu představují štítky různých tříd, volá metodu výběru atributů k rozdělení nebo rozdělení n-tic. Krok povede k vytvoření větví a rozhodovacích uzlů.

# 6) Metoda rozdělení určí, který atribut by měl být vybrán k rozdělení datových n-tic. Určuje také větve, které mají být pěstovány z uzlu podle výsledku testu. Hlavním motivem kritérií rozdělení je, že oddíl v každé větvi rozhodovacího stromu by měl představovat stejný štítek třídy.

Níže je uveden příklad rozdělení atributu:

A. Výše uvedené rozdělení je diskrétní.

b. Výše uvedené rozdělení je pro průběžné oceňování.

# 7) Výše uvedené kroky rozdělení jsou rekurzivně sledovány, aby se vytvořil rozhodovací strom pro n-tice tréninkových datových sad.

# 8) Rozdělení se zastaví, pouze když jsou vytvořeny všechny oddíly nebo když zbývající n-tice nelze dále rozdělit.

# 9) Složitost algoritmu popisuje n * | D | * log | D | kde n je počet atributů ve výcvikové datové sadě D a | D | je počet n-tic.

Co je chamtivé rekurzivní binární rozdělení?

V metodě binárního rozdělení se n-tice rozdělují a počítá se každá funkce rozdělení nákladů. Je vybráno nejnižší rozdělení nákladů. Metoda rozdělení je binární, která je vytvořena jako 2 větve. Má rekurzivní povahu, protože stejná metoda (výpočet nákladů) se používá k rozdělení ostatních n-tic datové sady.

Tento algoritmus se nazývá chamtivý, protože se zaměřuje pouze na aktuální uzel. Zaměřuje se na snížení nákladů, zatímco ostatní uzly jsou ignorovány.

Jak vybrat atributy pro vytvoření stromu?

Opatření pro výběr atributů se také nazývají pravidla rozdělení, která rozhodují o rozdělení n-tic. Kritéria rozdělení se používají k nejlepšímu rozdělení datové sady. Tato opatření poskytují pořadí atributů pro rozdělení tréninkových n-tic.

Nejpopulárnějšími metodami výběru atributu jsou zisk informací, Giniho index.

# 1) Získávání informací

Tato metoda je hlavní metodou, která se používá k vytváření rozhodovacích stromů. Snižuje informace potřebné ke klasifikaci n-tic. Snižuje počet testů, které jsou potřebné ke klasifikaci dané n-tice. Je vybrán atribut s nejvyšším ziskem informací.

Originální informace potřebné pro klasifikaci n-tice v datové sadě D jsou dány:

Kde p je pravděpodobnost, že n-tice patří do třídy C. Informace jsou kódovány v bitech, proto se použije log do báze 2. E (s) představuje průměrné množství informací požadovaných pro zjištění označení třídy datové sady D. Tento informační zisk se také nazývá Entropie .

Informace potřebné k přesné klasifikaci po porcování jsou dány vzorcem:

Kde P (c) je hmotnost přepážky. Tato informace představuje informace potřebné ke klasifikaci datové sady D při rozdělení podle X.

Informační zisk je rozdíl mezi původní a očekávanou informací, který je vyžadován ke klasifikaci n-tice datové sady D.

Zisk je redukce informace, která je vyžadována znalostí hodnoty X. Atribut s nejvyšším ziskem informací je vybrán jako „nejlepší“.

# 2) Zisk poměr

Zisk informací může někdy vyústit v rozdělení zbytečné pro klasifikaci. Poměr zisku však rozděluje tréninkovou datovou sadu na oddíly a zohledňuje počet n-tic výsledku vzhledem k celkovým n-ticím. Atribut s poměrem maximálního zisku se používá jako atribut rozdělení.

# 3) Giniho index

Giniho index se počítá pouze pro binární proměnné. Měří nečistotu v tréninkových n-ticích datové sady D, as

P je pravděpodobnost, že n-tice patří do třídy C. Giniho index, který se počítá pro binární rozdělené datové sady D atributem A, je dán vztahem:

Kde n je n-tý oddíl datové sady D.

Snížení nečistoty je dáno rozdílem Giniho indexu původní datové sady D a Giniho indexu po rozdělení podle atributu A.

Jako nejlepší atribut pro rozdělení je vybráno maximální snížení nečistoty nebo maximální index Gini.

Přetížení rozhodovacích stromů

Overfitting se stane, když se rozhodovací strom snaží být co nejdokonalejší zvýšením hloubky testů a tím snižuje chybu. To má za následek velmi složité stromy a vede k nadměrnému vybavení.

Overfitting snižuje prediktivní povahu rozhodovacího stromu. Přístupy, jak se vyhnout nadměrnému vybavení stromů, zahrnují preřezávání a prořezávání.

Co je to prořezávání stromů?

Prořezávání je metoda odstraňování nepoužívaných větví z rozhodovacího stromu. Některé větve rozhodovacího stromu mohou představovat odlehlé hodnoty nebo hlučná data.

Prořezávání stromů je metoda snižování nežádoucích větví stromu. To sníží složitost stromu a pomůže při efektivní prediktivní analýze. Snižuje nadměrné vybavení, protože odstraňuje nedůležité větve ze stromů.

Existují dva způsoby prořezávání stromu:

# 1) Předběžná úprava : V tomto přístupu je výstavba rozhodovacího stromu zastavena dříve. To znamená, že je rozhodnuto větve dále nerozdělovat. Poslední zkonstruovaný uzel se stane listovým uzlem a tento listový uzel může držet nejčastější třídu mezi n-ticemi.

K určení váhy rozdělení se používají míry výběru atributů. Prahové hodnoty jsou předepsány k rozhodnutí, která rozdělení jsou považována za užitečná. Pokud má rozdělení uzlu za následek rozdělení snížením pod prahovou hodnotu, proces je zastaven.

# 2) Postpruning : Tato metoda odstraní odlehlé větve z plně dospělého stromu. Nežádoucí větve jsou odstraněny a nahrazeny listovým uzlem označujícím nejběžnější označení třídy. Tato technika vyžaduje více výpočtů než předběžné prořezávání, je však spolehlivější.

Prořezané stromy jsou přesnější a kompaktnější ve srovnání s neořezanými stromy, ale mají nevýhodu replikace a opakování.

Opakování nastává, když je stejný atribut testován znovu a znovu podél větve stromu. Replikace nastane, když jsou ve stromu duplicitní podstromy. Tyto problémy lze vyřešit vícerozměrným rozdělením.

Obrázek níže ukazuje neořezaný a prořezaný strom.

Příklad algoritmu rozhodovacího stromu

Příklad Zdroj

Vytvoření rozhodovacího stromu

Vezměme si příklad datové sady počasí za posledních 10 dní s atributy výhled, teplota, vítr a vlhkost. Výsledná proměnná bude hrát kriket nebo ne. K vytvoření rozhodovacího stromu použijeme algoritmus ID3.

Krok 1: Prvním krokem bude vytvoření kořenového uzlu.

Krok 2: Pokud jsou všechny výsledky ano, bude vrácen listový uzel „ano“, jinak bude vrácen listový uzel „ne“.

Krok 3: Zjistěte entropii všech pozorování a entropii s atributem „x“, který je E (S) a E (S, x).

Krok 4: Zjistěte zisk informací a vyberte atribut s vysokým ziskem informací.

Krok 5: Výše uvedené kroky opakujte, dokud nebudou pokryty všechny atributy.

Výpočet entropie:

Ano ne

9 5

Pokud je entropie nula, znamená to, že všichni členové patří do stejné třídy, a pokud je entropie jedna, znamená to, že polovina n-tic patří do jedné třídy a jedna z nich do jiné třídy. 0,94 znamená spravedlivé rozdělení.

Najděte atribut zisk informací, který poskytuje maximální zisk informací.

Například „Vítr“, má dvě hodnoty: Silný a Slabý, tedy x = {Silný, Slabý}.

html otázky a odpovědi pro osvěžovače

Zjistěte H (x), P (x) pro x = slabý a x = silný. H (S) je již vypočítán výše.

Slabé = 8

Silný = 8

Pro „slabý“ vítr říká 6 z nich „Ano“ pro hraní kriketu a 2 z nich „Ne“. Takže entropie bude:

Pro „silný“ vítr 3 řekli „Ne“, aby hráli kriket, a 3 řekli „Ano“.

To ukazuje dokonalou náhodnost, protože polovina položek patří do jedné třídy a zbývající polovina patří ostatním.

Vypočítejte zisk informací,

Podobně je zisk informací pro další atributy:

Atribut výhled má nejvyšší zisk informací 0,246, je tedy vybrán jako root.

Zataženo má 3 hodnoty: slunečno, zataženo a déšť. Zataženo při hraní kriketu je vždy „Ano“. Takže to skončí uzlem listu, „ano“. Pro ostatní hodnoty „Sunny“ a „Rain“.

Tabulka pro Outlook jako „Sunny“ bude:

Entropie pro „Outlook“ „Sunny“ je:

Informační zisk pro atributy s ohledem na Sunny je:

Zisk informace pro vlhkost je nejvyšší, proto je vybrán jako další uzel. Podobně se entropie počítá pro déšť. Vítr poskytuje nejvyšší zisk informací .

Rozhodovací strom by vypadal níže:

Co je prediktivní modelování?

Klasifikační modely lze použít k předpovědi výsledků neznámé sady atributů.

Když je do modelu vložena datová sada s neznámými popisky tříd, automaticky k ní přiřadí popisek třídy. Tato metoda aplikace pravděpodobnosti k předpovědi výsledků se nazývá prediktivní modelování.

Výhody klasifikace rozhodovacích stromů

Níže jsou uvedeny různé výhody klasifikace rozhodovacího stromu:

1. Klasifikace rozhodovacího stromu nevyžaduje žádné znalosti domény, a proto je vhodná pro proces zjišťování znalostí.
2. Reprezentace dat ve formě stromu je člověku snadno srozumitelná a je intuitivní.
3. Může zpracovávat vícerozměrná data.
4. Je to rychlý proces s velkou přesností.

Nevýhody klasifikace rozhodovacích stromů

Níže uvádíme různé nevýhody klasifikace rozhodovacích stromů:

1. Někdy se rozhodovací stromy stávají velmi složitými a tyto stromy se nazývají přeplněné.
2. Algoritmus rozhodovacího stromu nemusí být optimálním řešením.
3. Rozhodovací stromy mohou vrátit zaujaté řešení, pokud mu dominuje nějaký štítek třídy.

Závěr

Rozhodovací stromy jsou techniky dolování dat pro klasifikaci a regresní analýzu.

Tato technika nyní zahrnuje mnoho oblastí, jako je lékařská diagnostika, cílový marketing atd. Tyto stromy jsou konstruovány podle algoritmu, jako je ID3, CART. Tyto algoritmy nacházejí různé způsoby, jak rozdělit data na oddíly.

Jedná se o nejznámější techniku ​​učení pod dohledem, která se používá při strojovém učení a analýze vzorů. Rozhodovací stromy předpovídají hodnoty cílové proměnné vytvářením modelů učením se z tréninkové sady poskytované systému.

Doufáme, že jste se z tohoto informativního tutoriálu dozvěděli vše o těžbě rozhodovacího stromu !!

Výukový program PREV | DALŠÍ výuka

Doporučené čtení

• Příklady dolování dat: Nejběžnější aplikace dolování dat 2021
• Techniky dolování dat: Algoritmus, metody a nejlepší nástroje pro dolování dat
• Těžba dat: Proces, techniky a hlavní problémy v analýze dat
• Datová struktura stromu B a stromu B + v C ++
• Struktura dat binárního stromu v C ++
• Proces dolování dat: zúčastněné modely, procesní kroky a výzvy
• Datová struktura stromu AVL a haldy v C ++
• Data Mining vs. Machine Learning vs. Artificial Intelligence vs. Deep Learning