Примери алгоритма стабла одлука у рударству података

decision tree algorithm examples data mining

Овај продубљени водич објашњава све о алгоритму стабла одлучивања у рударству података. Научићете о примерима стабла одлучивања, алгоритму и класификацији:

Погледали смо неколико Примери за рударење подацима у нашем претходном водичу у Бесплатна серија обуке за рударење подацима .

Рудање стабла одлука је врста технике рударења података која се користи за изградњу класификационих модела. Она гради моделе класификације у облику структуре налик дрвету, баш као и њено име. Ова врста рударства припада надгледаном предавању.

У учењу под надзором, циљни резултат је већ познат. Стабла одлучивања могу се користити и за категоричке и за нумеричке податке. Категорички подаци представљају пол, брачно стање итд., Док нумерички подаци представљају старост, температуру итд.

случајни број ц ++ између 0 и 10

Пример стабла одлука са скупом података приказан је у наставку.

(слика извор )

Шта ћете научити:

• Која је употреба стабла одлучивања?
• Анализа класификације
• Регресиона анализа
• Како функционише стабло одлука?
• Алгоритам индукције стабла одлука
• Индукција стабла одлучивања
• ЦАРТ
• Индукција стабла одлучивања за машинско учење: ИД3
• Шта је похлепно рекурзивно бинарно цепање?
• Како одабрати атрибуте за стварање дрвета?
  • # 1) Добијање информација
  • # 2) Однос добитка
  • # 3) Гини индекс
• Прекомерно уклапање у стабла за одлучивање
• Шта је обрезивање дрвета?
• Шта је предиктивно моделирање?
• Предности класификације стабла одлучивања
• Недостаци класификације стабла одлучивања
• Закључак
• Препоручено читање

Која је употреба стабла одлучивања?

Дрво одлуке користи се за изградњу модела класификације и регресије. Користи се за стварање модела података који ће предвидети ознаке класа или вредности за процес доношења одлука. Модели су изграђени од скупа података о обуци који се уносе у систем (учење под надзором).

Користећи стабло одлука, можемо визуализовати одлуке које олакшавају разумевање, па је то популарна техника рударења података.

Анализа класификације

Класификација података је облик анализе који гради модел који описује важне променљиве класе.На пример, модел изграђен за категоризацију захтева за банкарске зајмове као безбедне или ризичне. Методе класификације се користе у машинском учењу и препознавању образаца.

Примена класификације укључује откривање превара, медицинску дијагнозу, циљни маркетинг итд. Резултат проблема класификације узима се као „Начин“ свих уочених вредности терминалног чвора.

Слиједи поступак у два корака за изградњу модела класификације.

1. У првом кораку, односно учењу: Изграђен је модел класификације заснован на подацима о обуци.
2. У другом кораку, односно класификацији, проверава се тачност модела, а затим се модел користи за класификацију нових података. Ознаке класа које су овде представљене су у облику дискретних вредности као што су „да“ или „не“, „сигурно“ или „ризично“.

Општи приступ за моделе класификације зграда дат је у наставку:

(слика извор )

Регресиона анализа

Регресијска анализа користи се за предвиђање нумеричких атрибута.

Нумерички атрибути се називају и континуираним вредностима. Модел изграђен за предвиђање континуираних вредности уместо ознака класе назива се регресијски модел. Резултат регресионе анализе је „средина“ свих посматраних вредности чвора.

Како функционише стабло одлука?

Стабло одлука је надгледани алгоритам учења који ради и за дискретне и за континуалне променљиве. Скуп података дели на подскупове на основу најзначајнијег атрибута у скупу података. Како стабло одлуке идентификује овај атрибут и како се врши ово раздвајање, одлучују алгоритми.

Најзначајнији предиктор одређен је као коријенски чвор, раздвајање се врши како би се формирали под-чворови који се називају чворови за одлучивање, а чворови који се не дијеле даље су терминални или лисни чворови.

У стаблу одлука скуп података је подељен на хомогене и непреклапајуће регионе. Следи приступ одозго према доле, јер горњи регион приказује сва запажања на једном месту које се дели на две или више грана које се даље деле. Овај приступ се такође назива а похлепан приступ јер узима у обзир само тренутни чвор између обрађених без фокусирања на будуће чворове.

Алгоритми стабла одлука наставиће да се изводе док се не постигну критеријуми заустављања као што је минимални број посматрања итд.

Једном када се изгради стабло одлуке, многи чворови могу представљати одступања или бучне податке. За уклањање нежељених података примењује се метода обрезивања дрвета. То, пак, побољшава тачност класификационог модела.

Да би се пронашла тачност модела, користи се тест сет који се састоји од испитних корпица и ознака класа. Проценти корпица испитних скупова су правилно класификовани по моделу да би се утврдила тачност модела. Ако се утврди да је модел тачан, онда се користи за класификацију скупова података за које ознаке класа нису познате.

Неки од алгоритама стабла одлучивања укључују Хунт-ов алгоритам, ИД3, ЦД4.5 и ЦАРТ.

Пример креирања стабла одлука

(Пример је преузет из концепата рударења података: Хан и Кимбер)

# 1) Корак учења: Подаци о обуци се уносе у систем који се анализира алгоритмом класификације. У овом примеру ознака класе је атрибут, тј. „Одлука о зајму“. Модел изграђен на основу ових података о обуци представљен је у облику правила одлучивања.

# 2) Класификација: Скупови података за тестирање доводе се до модела ради провере тачности правила класификације. Ако модел даје прихватљиве резултате, примењује се на нови скуп података са непознатим променљивим класе.

Алгоритам индукције стабла одлука

Индукција стабла одлучивања

Индукција стабла одлучивања је метода учења стабала одлучивања из сета тренинга. Сет обуке састоји се од атрибута и ознака класа. Примене индукције стабла одлучивања укључују астрономију, финансијску анализу, медицинску дијагнозу, производњу и производњу.

Стабло одлуке је структура налик стаблу дијаграма тока која је направљена од корпица постављених у обуку. Скуп података је подељен на мање подскупове и присутан је у облику чворова стабла. Структура стабла има коријенски чвор, унутрашње чворове или чворове одлуке, чвор листа и гране.

Коренски чвор је највиши чвор. Представља најбољи атрибут одабран за класификацију. Интерни чворови чворова одлуке представљају тест атрибута чвора чвора или терминалног чвора скупа који представља класификацију или ознаку одлуке. Гране приказују исход обављеног теста.

Нека стабла одлучивања имају само бинарни чворови , то значи тачно две гране чвора, док су нека стабла одлучивања небинарна.

Слика испод приказује стабло одлуке за сет података Титаниц да предвиди да ли ће путник преживети или не.

(слика извор )

ЦАРТ

ЦАРТ модел, тј. Модели класификације и регресије су алгоритам стабла одлучивања за изградњу модела. Модел стабла одлучивања где циљне вредности имају дискретну природу назива се класификацијски модел.

Дискретна вредност је коначан или бројиво бесконачан скуп вредности, На пример, старост, величина итд. Модели у којима су циљне вредности представљене континуираним вредностима обично су бројеви који се називају регресијски модели. Непрекидне променљиве су променљиве са покретном зарезом. Ова два модела заједно се називају ЦАРТ.

ЦАРТ користи Гини индекс као матрицу класификације.

Индукција стабла одлучивања за машинско учење: ИД3

Крајем 1970-их и почетком 1980-их, Ј.Росс Куинлан је био истраживач који је изградио алгоритам стабла одлучивања за машинско учење. Овај алгоритам је познат као ИД3, Итеративни дихотомизер . Овај алгоритам био је продужетак концепта система учења који су описали Е.Б Хунт, Ј и Марин.

ИД3 је касније познат као Ц4.5. ИД3 и Ц4.5 следе похлепни приступ од врха према доле за изградњу дрвећа одлука. Алгоритам започиње са низом података о обуци са ознакама класе које су раздељене у мање подскупове током израде стабла.

# 1) У почетку постоје три параметра тј. листа атрибута, метода избора атрибута и партиција података . Листа атрибута описује атрибуте корпица скупа тренинга.

#два) Метода избора атрибута описује методу за одабир најбољег атрибута за дискриминацију међу корпицама. Методе које се користе за одабир атрибута могу бити Пораст информација или Гини индекс.

# 3) О структури стабла (бинарном или небинарном) одлучује се методом избора атрибута.

# 4) Када се конструише стабло одлуке, оно започиње као један чвор који представља корпе.

# 5) Ако коријени коријенски чворови представљају различите ознаке класа, тада позива метод избора атрибута да би подијелио или подијелио корпе. Корак ће довести до формирања грана и чворова за одлучивање.

# 6) Метода раздвајања ће одредити који атрибут треба одабрати за партиционирање корпица података. Такође одређује гране које ће се узгајати од чвора према исходу теста. Главни мотив критеријума раздвајања је да партиција на свакој грани стабла одлуке представља исту ознаку класе.

Пример атрибута раздвајања приказан је испод:

а. Горњи део је дискретне вредности.

б. Горњи део је за непрекидну вредност.

# 7) Горе наведени кораци партиционирања слиједе се рекурзивно како би се формирало стабло одлука за корпе скупа података обуке.

како покренути јар датотеку на Виндовс 10

# 8) Дијељење се зауставља само када су направљене или све партиције или када се преостале корпе не могу даље партиционирати.

# 9) Сложеност алгоритма описује н * | Д | * дневник | Д | где је н број атрибута у скупу података Д и | Д | је број коријена.

Шта је похлепно рекурзивно бинарно цепање?

У бинарном методу цепања, корпе се деле и израчунава се свака функција трошкова поделе. Одабран је најнижи расцеп трошкова. Метода цепања је бинарна која се формира као 2 гране. По својој природи је рекурзивна, јер се иста метода (израчунавање трошкова) користи за поделу осталих корпица скупа података.

Овај алгоритам назива се похлепним јер се фокусира само на тренутни чвор. Фокусира се на смањење трошкова, док се остали чворови игноришу.

Како одабрати атрибуте за стварање дрвета?

Мере за одабир атрибута називају се и правилима цепања да би се одлучило како ће се цепови цепати. Критеријуми подјеле користе се за најбоље дијељење скупа података. Ове мере дају ранг према атрибутима за поделу торби за обуку.

Најпопуларније методе избора атрибута су добијање информација, Гини индекс.

# 1) Добијање информација

Ова метода је главна метода која се користи за изградњу стабала одлучивања. Смањује информације потребне за класификацију корпица. Смањује број тестова који су потребни за класификацију датог комплета. Одабран је атрибут са највећим прикупљањем информација.

Оригиналне информације потребне за класификацију набора у скупу података Д дају:

Где је п вероватноћа да корпица припада класи Ц. Информације се кодирају у битовима, па се користи лог на базу 2. Е (с) представљају просечну количину информација потребних за сазнавање ознаке класе скупа података Д. Такође се назива и добијање информација Ентропија .

Подаци потребни за тачну класификацију након порционирања дају се формулом:

Где је П (ц) тежина преграде. Ове информације представљају информације потребне за класификацију скупа података Д на порционирање од стране Кс.

Добијање информација је разлика између оригиналних и очекиваних информација које су потребне за класификацију низова скупа података Д.

Добитак је смањење информација које је потребно познавањем вредности Кс. Атрибут са највећим прирастом информација бира се као „најбољи“.

# 2) Однос добитка

Добијање информација може понекад резултирати дељењем бескорисних за класификацију. Међутим, однос добитка дели скуп података о тренингу на партиције и узима у обзир број корпица исхода у односу на укупне корпе. Атрибут са односом максималног добитка користи се као атрибут раздвајања.

# 3) Гини индекс

Гини индекс се израчунава само за бинарне променљиве. Мери нечистоћу у тренинзима за скуп података Д, као

П је вероватноћа да торта припада класи Ц. Гинијев индекс који се израчунава за бинарни сплит Д скуп података помоћу атрибута А дат је са:

Где је н н-та партиција скупа података Д.

Смањење нечистоће дато је разликом Гинијевог индекса оригиналног скупа података Д и Гинијевог индекса након поделе атрибутом А.

Максимално смањење нечистоће или мак Гини индекс је одабран као најбољи атрибут за цепање.

Прекомерно уклапање у стабла за одлучивање

Прекомерно прилагођавање се дешава када стабло одлуке покушава да буде што савршеније повећањем дубине тестова и на тај начин смањује грешку. То резултира врло сложеним дрвећем и доводи до прекомерне опреме.

Прекомерна опремљеност смањује предиктивну природу стабла одлучивања. Приступи за избегавање прекомерне опреме дрвећа укључују пре и након обрезивања.

Шта је обрезивање дрвета?

Резидба је метода уклањања неискоришћених грана са стабла одлучивања. Неке гране стабла одлука могу представљати одступања или бучне податке.

Резидба дрвета је метода за смањење нежељених грана дрвета. Ово ће смањити сложеност стабла и помоћи у ефикасној предиктивној анализи. Смањује прекомерно опремање јер уклања неважне гране са дрвећа.

Постоје два начина обрезивања дрвета:

# 1) Припрема : У овом приступу, изградња стабла одлука се зауставља рано. То значи да је одлучено да се гране не деле даље. Последњи изграђени чвор постаје лисни чвор и овај чвор може садржати најчешћу класу међу корпицама.

Мере за одабир атрибута користе се да би се утврдила тежина поделе. Граничне вредности су прописане да би се одлучило који се делови сматрају корисним. Ако дијељење чвора резултира цијепањем падом испод прага, тада се поступак зауставља.

# 2) Постпрунинг : Овом методом уклањају се одвојене гране са потпуно пораслог стабла. Нежељене гране се уклањају и замењују лиснатим чвором који означава најчешће ознаку класе. Ова техника захтева више прорачуна него припремање, али је поузданија.

Орезана стабла су прецизнија и компактнија у поређењу са необрезаним дрвећем, али имају недостатак репликације и понављања.

Понављање се дешава када се исти атрибут поново и поново тестира дуж гране дрвета. Репликација се јавља када су дупликати подстабла присутни унутар стабла. Ова питања се могу решити мултиваријантним поделама.

На слици испод је приказано необрезано и орезано дрво.

Пример алгоритма стабла одлучивања

Пример Извор

Конструисање стабла одлуке

Узмимо пример примера података о времену за последњих 10 дана са атрибутима изглед, температура, ветар и влажност. Варијабла исхода ће бити играње крикета или не. За израду стабла одлучивања користићемо алгоритам ИД3.

Корак 1: Први корак биће стварање коренског чвора.

Корак 2: Ако су сви резултати да, тада ће се вратити чвор листа „да“, у супротном ће се вратити чвор листа „не“.

Корак 3: Откријте Ентропију свих посматрања и ентропију са атрибутом „к“ који је Е (С) и Е (С, к).

Корак4: Пронађите информатичку добит и одаберите атрибут са високом информатичком добити.

Корак5: Понављајте горње кораке док сви атрибути нису покривени.

Прорачун ентропије:

да не

9 5

Ако је ентропија нула, то значи да сви чланови припадају истој класи, а ако је ентропија једна, то значи да половина корпица припада једној класи, а један од њих другој класи. 0,94 значи поштена расподела.

Пронађите атрибут добијања информација који даје максималан добитак информација.

На пример „Ветар“, узима две вредности: Снажан и слаб, дакле, к = {Снажан, слаб}.

Откријте Х (к), П (к) за к = слабо и к = јако. Х (С) је већ израчунат горе.

Слабо = 8

Јака = 8

За „слаб“ ветар, њих 6 каже „Да“ да би играло крикет, а двоје њих каже „Не“. Дакле, ентропија ће бити:

За „јак“ ветар, 3 су рекла „Не“ да играју крикет, а 3 „Да“.

шта је безбедносни кључ за вифи

Ово показује савршену случајност јер половина предмета припада једној класи, а преостала половина припада другој.

Израчунајте добитак информација,

Слично томе, добитак информација за друге атрибуте је:

Атрибут оутлоок има највећи информативни добитак од 0,246, па је стога изабран за корен.

Облачно има 3 вредности: Сунчано, Облачно и Киша. Наоблачење са крикетом за игру увек је „Да“. Тако се завршава чвором листа, „да“. За остале вредности „Сунчано“ и „Киша“.

Табела за Оутлоок као „Сунчана“ биће:

Ентропија за „Оутлоок“ „Сунни“ је:

Добитак информација за атрибуте у односу на Сунни је:

Добитак информација за влажност ваздуха је највећи, па је одабран као следећи чвор. Слично томе, ентропија се израчунава за кишу. Ветар даје највећи информативни добитак .

Стабло одлуке би изгледало доле:

Шта је предиктивно моделирање?

Класификациони модели могу се користити за предвиђање исхода непознатог скупа атрибута.

Када се скуп података са непознатим ознакама класе унесе у модел, тада ће му аутоматски доделити ознаку класе. Овај метод примене вероватноће за предвиђање исхода назива се предиктивно моделирање.

Предности класификације стабла одлучивања

У наставку су наведене разне заслуге класификације стабла одлучивања:

1. Класификација стабла одлука не захтева никакво знање из домена, стога је прикладна за процес откривања знања.
2. Приказивање података у облику дрвета људима је лако разумљиво и интуитивно је.
3. Може да обрађује вишедимензионалне податке.
4. То је брз процес са великом тачношћу.

Недостаци класификације стабла одлучивања

Доље су дати различити недостаци класификације стабла одлучивања:

1. Понекад стабла одлучивања постају врло сложена и она се називају пренамјештеним стаблима.
2. Алгоритам стабла одлучивања можда није оптимално решење.
3. Стабла одлука могу вратити пристрасно решење ако нека ознака класе доминира над њим.

Закључак

Стабла одлучивања су технике руковања подацима за класификацију и регресиону анализу.

Ова техника се сада простире у многим областима попут медицинске дијагнозе, циљног маркетинга, итд. Ова стабла се израђују пратећи алгоритам као што је ИД3, ЦАРТ. Ови алгоритми проналазе различите начине за поделу података на партиције.

То је најпознатија надгледана техника учења која се користи у машинском учењу и анализи образаца. Стабла одлучивања предвиђају вредности циљне променљиве градећи моделе кроз учење из сета обуке који се пружа систему.

Надамо се да сте из овог информативног водича научили све о рударству на стаблима одлука !!

ПРЕВ Туториал |. | СЛЕДЕЋА Лекција

Препоручено читање

• Примери рударства података: Најчешћа примена рударства података 2021
• Технике рударства података: алгоритам, методе и врхунски алати за минирање података
• Рударство података: процес, технике и главни проблеми у анализи података
• Структура података Б Трее и Б + Трее у Ц ++
• Структура података бинарног стабла у језику Ц ++
• Процес рударења података: Укључени модели, кораци процеса и изазови
• Структура података АВЛ стабла и гомиле у Ц ++
• Дата Мининг вс Мацхине Леарнинг вс Артифициал Интеллигенце вс Дееп Леарнинг