Примери за алгоритъм на дървото на решения в извличането на данни

decision tree algorithm examples data mining

Този задълбочен урок обяснява всичко за алгоритъма на дървото за вземане на решения при извличането на данни. Ще научите за примери за дърво на решенията, алгоритъм и класификация:

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

Добиването на дърво на решенията е вид техника за извличане на данни, която се използва за изграждане на класификационни модели. Той изгражда класификационни модели под формата на дървовидна структура, точно както името му. Този вид копаене принадлежи към контролирано обучение в клас.

При контролирано обучение целевият резултат вече е известен. Дърветата на решенията могат да се използват както за категорични, така и за цифрови данни. Категоричните данни представляват пол, семейно положение и др., Докато числените данни представляват възраст, температура и др.

c ++ произволно число между 0 и 10

Пример за дърво за решения с набора от данни е показан по-долу.

(изображение източник )

Какво ще научите:

• Каква е ползата от дървото за вземане на решения?
• Класификационен анализ
• Регресионен анализ
• Как работи дървото на решенията?
• Алгоритъм за индукция на дървото на решенията
• Индукция на дървото на решенията
• КОШИЦА
• Индукция на дървото на решенията за машинно обучение: ID3
• Какво е алчното рекурсивно бинарно разделяне?
• Как да изберем атрибути за създаване на дърво?
  • # 1) Увеличаване на информацията
  • # 2) Коефициент на печалба
  • # 3) Индекс на Джини
• Пренастройване в дърветата за вземане на решения
• Какво представлява резитбата на дървета?
• Какво е прогнозно моделиране?
• Предимства на класификацията на дървото на решенията
• Недостатъци на класификацията на дървото на решенията
• Заключение
• Препоръчително четене

Каква е ползата от дървото за вземане на решения?

Дървото на решенията се използва за изграждане на класификационни и регресионни модели. Използва се за създаване на модели на данни, които ще предсказват етикети на класове или стойности за процеса на вземане на решение. Моделите са изградени от набора от данни за обучение, подаван към системата (контролирано обучение).

Използвайки дърво за решения, можем да визуализираме решенията, които улесняват разбирането и по този начин това е популярна техника за извличане на данни.

Класификационен анализ

Класификацията на данните е форма на анализ, която изгражда модел, който описва важни променливи на класа.Например, модел, създаден за категоризиране на заявленията за банкови заеми като безопасни или рискови. Методите за класификация се използват при машинно обучение и разпознаване на образци.

Прилагането на класификация включва откриване на измами, медицинска диагноза, целеви маркетинг и др. Резултатът от проблема с класификацията се приема като „Режим“ на всички наблюдавани стойности на терминалния възел.

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

1. В първата стъпка, т. Е. Обучение: Изграден е класификационен модел, базиран на данни за обучение.
2. Във втората стъпка, т.е. Класификация, се проверява точността на модела и след това моделът се използва за класифициране на нови данни. Представените тук етикети на класове са под формата на дискретни стойности като „да“ или „не“, „безопасно“ или „рисковано“.

Общият подход за изграждане на класификационни модели е даден по-долу:

(изображение източник )

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

Регресионният анализ се използва за прогнозиране на числови атрибути.

Числовите атрибути се наричат ​​още непрекъснати стойности. Модел, създаден за предсказване на непрекъснати стойности вместо етикети на класове, се нарича регресионен модел. Резултатът от регресионния анализ е „Средната стойност“ на всички наблюдавани стойности на възела.

Как работи дървото на решенията?

Дървото на решенията е контролиран учебен алгоритъм, който работи както за дискретни, така и за непрекъснати променливи. Той разделя набора от данни на подмножества въз основа на най-значимия атрибут в набора от данни. Как дървото на решенията идентифицира този атрибут и как се извършва това разделяне се решава от алгоритмите.

Най-значимият предиктор е определен като основен възел, разделянето се извършва, за да се образуват подвъзли, наречени възли за вземане на решения, а възлите, които не се разделят допълнително, са крайни или листни възли.

В дървото за решения наборът от данни е разделен на хомогенни и неприпокриващи се региони. Той следва подход отгоре надолу, тъй като горният регион представя всички наблюдения на едно място, което се разделя на два или повече клона, които допълнително се разделят. Този подход се нарича още a алчен подход тъй като разглежда само текущия възел между обработените, без да се фокусира върху бъдещите възли.

Алгоритмите на дървото за вземане на решения ще продължат да работят, докато не бъдат достигнати критерии за спиране като минималния брой наблюдения и т.н.

След като се изгради дърво за решения, много възли могат да представляват отклонения или шумни данни. Методът за подрязване на дървета се прилага за премахване на нежелани данни. Това от своя страна подобрява точността на класификационния модел.

За да се намери точността на модела, се използва тестов набор, състоящ се от тестови кортежи и етикети на класове. Процентите на тестовите комплекти са правилно класифицирани от модела, за да се идентифицира точността на модела. Ако се установи, че моделът е точен, той се използва за класифициране на комплектите данни, за които етикетите на класа не са известни.

Някои от алгоритмите на дървото за вземане на решения включват алгоритъм на Hunt, ID3, CD4.5 и CART.

Пример за създаване на дърво за решения

(Примерът е взет от Концепции за извличане на данни: Хан и Кимбър)

# 1) Стъпка на обучение: Данните за обучение се подават в системата, за да бъдат анализирани чрез алгоритъм за класификация. В този пример етикетът на класа е атрибут, т.е. „решение за заем“. Моделът, изграден от тези данни за обучение, е представен под формата на правила за вземане на решения.

# 2) Класификация: Тестовият набор от данни се подава към модела, за да се провери точността на правилото за класификация. Ако моделът дава приемливи резултати, тогава той се прилага към нов набор от данни с неизвестни променливи на класа.

Алгоритъм за индукция на дървото на решенията

Индукция на дървото на решенията

Индукцията на дървото за вземане на решения е методът за изучаване на дърветата за вземане на решения от учебния набор. Комплектът за обучение се състои от атрибути и етикети на класове. Приложенията за индукция на дървото на решения включват астрономия, финансов анализ, медицинска диагностика, производство и производство.

Дървото за вземане на решения е структура, подобна на дървовидна диаграма, която е направена от обучителни комплекти. Наборът от данни е разделен на по-малки подмножества и присъства под формата на възли на дърво. Дървесната структура има корен възел, вътрешни възли или възли за вземане на решения, листен възел и клонове.

Коренният възел е най-горният възел. Той представлява най-добрият атрибут, избран за класификация. Вътрешните възли на възлите за решение представляват тест на атрибут на листовия възел на набора от данни или терминален възел, който представлява класификацията или етикета за решение. Клоновете показват резултата от извършения тест.

Някои дървета за решения имат само двоични възли , това означава точно два клона на възел, докато някои дървета за вземане на решения са не двоични.

Изображението по-долу показва дървото за решения за набора от данни на Titanic, за да се предскаже дали пътникът ще оцелее или не.

(изображение източник )

КОШИЦА

Модел CART, т.е. Модели за класификация и регресия е алгоритъм на дървото за вземане на решения за изграждане на модели. Модел на дървото на решения, където целевите стойности имат дискретна природа, се нарича класификационни модели.

Дискретна стойност е краен или брояемо безкраен набор от стойности, Например, възраст, размер и др. Моделите, при които целевите стойности са представени с непрекъснати стойности, обикновено са числа, които се наричат ​​модели на регресия. Непрекъснатите променливи са променливи с плаваща запетая. Тези два модела заедно се наричат ​​CART.

CART използва Gini Index като класификационна матрица.

Индукция на дървото на решенията за машинно обучение: ID3

В края на 70-те и началото на 80-те години J.Ross Quinlan е изследовател, който изгражда алгоритъм на дървото за решения за машинно обучение. Този алгоритъм е известен като ID3, Итеративен дихотомайзер . Този алгоритъм е продължение на концепцията за системи за обучение, описана от Е. Б. Хънт, Дж и Марин.

По-късно ID3 стана известен като C4.5. ID3 и C4.5 следват алчен подход отгоре надолу за изграждане на дървета за решения. Алгоритъмът започва с набор от данни за обучение с етикети на класове, които се разделят на по-малки подмножества, докато се изгражда дървото.

# 1) Първоначално има три параметъра, т.е. списък с атрибути, метод за избор на атрибут и дял на данните . Списъкът с атрибути описва атрибутите на наборите от обучителни комплекти.

# две) Методът за избор на атрибут описва метода за избор на най-добрия атрибут за дискриминация между кортежи. Методите, използвани за избор на атрибут, могат да бъдат или повишаване на информацията, или индекс на Джини.

# 3) Структурата на дървото (двоично или не двоично) се определя от метода за избор на атрибут.

# 4) Когато се конструира дърво за решения, то започва като единичен възел, представляващ кортежите.

# 5) Ако кортежите на кореновия възел представляват различни етикети на класове, той извиква метод за избор на атрибут, за да разделя или разделя кортежите. Стъпката ще доведе до формирането на клонове и възли за вземане на решения.

# 6) Методът на разделяне ще определи кой атрибут трябва да бъде избран за разделяне на кортежите с данни. Той също така определя клоните, които трябва да се отглеждат от възела според резултата от теста. Основният мотив на критериите за разделяне е, че дялът на всеки клон на дървото за вземане на решения трябва да представлява един и същ етикет на класа.

Пример за разделяне на атрибут е показан по-долу:

а. Порцията по-горе е с дискретна стойност.

б. Порцията по-горе е за непрекъсната стойност.

# 7) Горните стъпки за разделяне се следват рекурсивно, за да се формира дърво за вземане на решения за наборите от обучителни набори от данни.

# 8) Разделянето спира само когато са направени или всички дялове, или когато останалите кортежи не могат да бъдат разделени допълнително.

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

Какво е алчното рекурсивно бинарно разделяне?

При двоичния метод на разделяне, кортежите се разделят и се изчислява всяка функция на цената на разделяне. Избира се най-ниското разделяне на разходите. Методът на разделяне е двоичен, който се формира като 2 клона. Той има рекурсивен характер, тъй като същият метод (изчисляване на разходите) се използва за разделяне на останалите кортежи от набора от данни.

Този алгоритъм се нарича толкова алчен, тъй като се фокусира само върху текущия възел. Той се фокусира върху намаляване на себестойността си, докато останалите възли се игнорират.

Как да изберем атрибути за създаване на дърво?

Мерките за избор на атрибути се наричат ​​още правила за разделяне, за да се реши как ще се разделят кортежите. Критериите за разделяне се използват за най-добро разделяне на набора от данни. Тези мерки осигуряват класиране на атрибутите за разделяне на учебните кортежи.

Най-популярните методи за избор на атрибут са печалба на информация, индекс на Джини.

# 1) Увеличаване на информацията

Този метод е основният метод, който се използва за изграждане на дървета за вземане на решения. Намалява информацията, необходима за класифициране на кортежите. Намалява броя на тестовете, които са необходими за класифициране на даден кортеж. Избран е атрибут с най-голяма печалба на информация.

Оригиналната информация, необходима за класификация на кортеж в набор от данни D, се дава от:

Където p е вероятността кортежът да принадлежи на клас C. Информацията се кодира в битове, следователно се използва log to the base 2. E (s) представлява средното количество информация, необходимо за откриване на етикета на класа на набор от данни D. Това повикване на информация също се нарича Ентропия .

Информацията, необходима за точна класификация след порциониране, се дава по формулата:

c ++ двойно свързан списък

Където P (c) е теглото на преградата. Тази информация представлява информацията, необходима за класифициране на набора от данни D при порциониране от X.

Информационната печалба е разликата между оригиналната и очакваната информация, която е необходима за класифициране на групите от набор от данни D.

Печалба е намаляването на информацията, което се изисква, като се знае стойността на X. Атрибутът с най-голяма печалба на информация се избира като „най-добър“.

# 2) Коефициент на печалба

Печалбата от информация понякога може да доведе до порциониране, безполезно за класификация. Съотношението Gain обаче разделя набора от данни за обучение на дялове и отчита броя на кортежите на резултата по отношение на общите кортежи. Атрибутът с коефициент на максимална печалба се използва като атрибут за разделяне.

# 3) Индекс на Джини

Индексът на Джини се изчислява само за двоични променливи. Той измерва примесите в обучителните купчини от набор от данни D, както

P е вероятността кортежът да принадлежи към клас C. Индексът на Gini, който се изчислява за двоичен разделен набор от данни D чрез атрибут A, се дава от:

Където n е n-ият дял на набора от данни D.

Намаляването на примесите се дава чрез разликата в индекса Gini на оригиналния набор от данни D и индекса Gini след разделяне по атрибут A.

Максималното намаляване на примесите или максималният индекс на Джини е избран като най-добрият атрибут за разделяне.

Пренастройване в дърветата за вземане на решения

Пренастройването се случва, когато дървото за решения се опитва да бъде възможно най-съвършено, като увеличава дълбочината на тестовете и по този начин намалява грешката. Това води до много сложни дървета и води до преоборудване.

Прекаленото оборудване намалява предсказуемия характер на дървото за вземане на решения. Подходите за избягване на прекомерно монтиране на дърветата включват предварителна резитба и след резитба.

Какво представлява резитбата на дървета?

Подрязването е методът за премахване на неизползваните клони от дървото за решения. Някои клонове на дървото за решения могат да представляват отклонения или шумни данни.

Подрязването на дърветата е методът за намаляване на нежеланите клони на дървото. Това ще намали сложността на дървото и ще помогне за ефективен прогнозен анализ. Намалява пренастройката, тъй като премахва маловажните клони от дърветата.

Има два начина за подрязване на дървото:

# 1) Подготовка : При този подход изграждането на дървото за решения се спира рано. Това означава, че е решено да не се разделят допълнително клоните. Последният изграден възел се превръща в листовия възел и този листен възел може да съдържа най-често срещания клас сред кортежите.

Мерките за избор на атрибути се използват за установяване на тежестта на разделянето. Праговите стойности са предписани, за да се реши кое разделяне се счита за полезно. Ако разделянето на възела води до разделяне чрез падане под прага, тогава процесът се спира.

# 2) Отстраняване : Този метод премахва отклонените клони от напълно израснало дърво. Нежеланите клони се премахват и заменят с листен възел, обозначаващ най-често срещания етикет на класа. Тази техника изисква повече изчисления, отколкото предварителна обработка, но е по-надеждна.

Подрязаните дървета са по-прецизни и компактни в сравнение с неподрязаните дървета, но имат недостатък на репликация и повторение.

Повторението се случва, когато един и същ атрибут се тества отново и отново по клон на дърво. Репликация възниква, когато дублираните поддървета присъстват в дървото. Тези проблеми могат да бъдат решени чрез многомерни разделяния.

Изображението отдолу показва неподрязано и подрязано дърво.

Пример за алгоритъм на дървото за решения

Пример Източник

Изграждане на дърво за решения

Нека вземем пример за набора от данни за последните 10 дни с атрибути outlook, температура, вятър и влажност. Променливата на резултата ще играе крикет или не. Ще използваме алгоритъма ID3 за изграждане на дървото за решения.

Етап 1: Първата стъпка ще бъде създаването на корен възел.

Стъпка 2: Ако всички резултати са 'да', тогава връщащият възел 'да' ще бъде върнат, в противен случай ще бъде върнат листният възел 'не'.

Стъпка 3: Разберете Ентропията на всички наблюдения и ентропията с атрибут “x”, който е E (S) и E (S, x).

Стъпка 4: Разберете информационната печалба и изберете атрибута с висока информационна печалба.

Стъпка 5: Повторете горните стъпки, докато се покрият всички атрибути.

Изчисляване на ентропията:

да не

9 5

Ако ентропията е нула, това означава, че всички членове принадлежат към един и същ клас, а ако ентропията е един, това означава, че половината от кортежите принадлежат към един клас, а един от тях принадлежи към друг клас. 0.94 означава справедливо разпределение.

Намерете атрибут за печалба на информация, който дава максимална печалба за информация.

Например “Вятър”, отнема две стойности: Силна и Слаба, следователно, x = {Силна, Слаба}.

Разберете H (x), P (x) за x = слаб и x = силен. H (S) вече е изчислено по-горе.

Слаб = 8

Силен = 8

За „слаб” вятър 6 от тях казват „Да”, за да играят крикет, а 2 от тях казват „Не”. Така че ентропията ще бъде:

За „силен“ вятър 3 казаха „Не“ за игра на крикет, а 3 казаха „Да“.

Това показва перфектна произволност, тъй като половината елементи принадлежат към един клас, а останалата половина принадлежат на други.

Изчислете печалбата на информация,

По същия начин печалбата на информация за други атрибути е:

Атрибутът outlook има най-висока информационна печалба от 0,246, като по този начин се избира за корен.

Облачно има 3 стойности: слънчево, облачно и дъждовно. Облачно с крикет за игра винаги е „Да“. Така че завършва с листен възел, „да“. За останалите стойности „Слънчево“ и „Дъжд“.

Таблица за Outlook като „Слънчево“ ще бъде:

Ентропия за “Outlook” “Sunny” е:

Информационната печалба за атрибутите по отношение на Sunny е:

как да стартирам jar файл -

Информационният прираст за влажност е най-висок, поради което той е избран за следващия възел. По същия начин Ентропията се изчислява за Дъжд. Вятърът дава най-висок прираст на информация .

Дървото на решенията ще изглежда по-долу:

Какво е прогнозно моделиране?

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

Когато в модела се подава набор от данни с неизвестни етикети на класове, той автоматично ще му присвои етикета на класа. Този метод за прилагане на вероятността за прогнозиране на резултатите се нарича прогнозно моделиране.

Предимства на класификацията на дървото на решенията

По-долу са изброени различните достойнства на класификацията на дървото на решенията:

1. Класификацията на дървото за вземане на решения не изисква никакви познания в областта, следователно е подходяща за процеса на откриване на знания.
2. Представянето на данни под формата на дървото е лесно разбираемо от хората и е интуитивно.
3. Той може да обработва многоизмерни данни.
4. Това е бърз процес с голяма точност.

Недостатъци на класификацията на дървото на решенията

По-долу са дадени различните недостатъци на класификацията на дървото на решенията:

1. Понякога дърветата за вземане на решения стават много сложни и те се наричат ​​свръхмонтирани дървета.
2. Алгоритъмът на дървото за решения може да не е оптимално решение.
3. Дърветата за решения могат да върнат предубедено решение, ако някакъв етикет на клас го доминира.

Заключение

Дърветата за вземане на решения са техники за извличане на данни за класификация и регресионен анализ.

Понастоящем тази техника обхваща много области като медицинска диагностика, целеви маркетинг и др. Тези дървета се изграждат, следвайки алгоритъм като ID3, CART. Тези алгоритми намират различни начини за разделяне на данните на дялове.

Това е най-широко известната техника на контролирано обучение, която се използва при машинно обучение и анализ на модели. Дърветата за решения предсказват стойностите на целевата променлива чрез изграждане на модели чрез учене от набора за обучение, предоставен на системата.

Надяваме се, че сте научили всичко за копаенето на дървета за решения от този информативен урок !!

PREV Урок | СЛЕДВАЩ урок

Препоръчително четене

• Примери за извличане на данни: Най-често срещаните приложения на извличането на данни 2021
• Техники за извличане на данни: Алгоритъм, методи и най-добрите инструменти за извличане на данни
• Извличане на данни: процес, техники и основни проблеми при анализа на данните
• Структура на данните от B Tree и B + Tree в C ++
• Структура на данните на двоичното дърво в C ++
• Процес на извличане на данни: Включени модели, стъпки и предизвикателства
• Структура на данните за дърво и купчина AVL в C ++
• Извличане на данни срещу машинно обучение срещу изкуствен интелект срещу дълбоко обучение