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

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

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

1. Избягване на пренастройването на данните

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

Недостатъчно оборудване

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

Прекомерно оборудване

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

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

Дефиниция — Overfit: Като се има предвид пространство на хипотеза H, се казва, че хипотеза h ∈ H препълва данните за обучение, ако съществува някаква алтернативна хипотеза h' ∈ H, така че h има по-малка грешка от h' в примерите за обучение, но h' има по-малка грешка от h в цялото разпределение на екземплярите.

Фигурата по-долу илюстрира въздействието на пренастройването в типично приложение на обучение в дървото на решенията. В този случай алгоритъмът ID3 се прилага към задачата да се научи кои медицински пациенти имат форма на диабет.

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

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

‹Слънчево, Горещо, Нормално, Силно, -›, Примерът е шумен, защото правилният етикет е +.
Предвид оригиналните безгрешни данни, ID3 създава дървото на решенията, показано на фигурата.

Въпреки това, добавянето на този неправилен пример сега ще накара ID3 да конструира по-сложно дърво. По-конкретно, новият пример ще бъде сортиран във втория листов възел отляво в наученото дърво от горната фигура, заедно с предишните положителни примери D9 и D11.
Тъй като новият пример е етикетиран като отрицателен пример, ID3 ще търси допълнителни уточнения на дървото под този възел. Резултатът е, че ID3 ще изведе дърво на решенията (h), което е по-сложно от оригиналното дърво от горната фигура (h’). Разбира се, h ще пасне идеално на колекцията от примери за обучение, докато по-простото h’ не. Въпреки това, като се има предвид, че новият възел за решение е просто следствие от напасването на примера за шумно обучение, очакваме h да надмине h' спрямо последващи данни, извлечени от същото разпространение на екземпляри.
Горният пример илюстрира как случаен шум в примерите за обучение може да доведе до пренатоварване.

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

Избягване на прекомерното оборудване —

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

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

Критерий, използван за определяне на правилния окончателен размер на дървото

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

Първият от горните подходи е най-разпространеният и често се нарича подход за набор от обучение и валидиране. Обсъждаме двата основни варианта на този подход по-долу. При този подход наличните данни се разделят на два набора от примери: набор за обучение, който се използва за формиране на научената хипотеза, и отделен набор за валидиране, който се използва за оценка на точността на тази хипотеза спрямо последващи данни и, в по-специално, за да се оцени въздействието на съкращаването на тази хипотеза. Мотивацията е следната: въпреки че обучаемият може да бъде подведен от случайни грешки и случайни закономерности в рамките на набора за обучение, наборът за валидиране е малко вероятно да покаже същите случайни колебания. Следователно може да се очаква комплектът за валидиране да осигури проверка на безопасността срещу пренастройване на фалшивите характеристики на комплекта за обучение. Разбира се, важно е наборът за валидиране да бъде достатъчно голям, за да осигури статистически значима извадка от случаите. Една обща евристика е да се задържи една трета от наличните примери за набора за валидиране, като се използват другите две трети за обучение.

1. Намаляване на грешките подрязване

Как точно можем да използваме набор за валидиране, за да предотвратим пренастройване? Един подход, наречен съкращаване с намалена грешка (Quinlan 1987), е да се счита всеки от възлите за вземане на решения в дървото като кандидати за съкращаване.

  • Съкращаване с намалена грешка е да се счита всеки от възлите за вземане на решение в дървото като кандидати за съкращаване
  • Подрязването на възел за решение се състои от премахване на поддървото, вкоренено в този възел, превръщането му в листен възел и присвояването му на най-често срещаната класификация на примерите за обучение, свързани с този възел
  • Възлите се премахват само ако полученото съкратено дърво се представя не по-лошо от оригинала спрямо набора за валидиране.
  • Намаленото изрязване на грешки води до това, че всеки листов възел, добавен поради съвпадащи закономерности в набора за обучение, вероятно ще бъде отрязан, тъй като същите тези съвпадения е малко вероятно да възникнат в набора за валидиране

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

Като по-ранна фигура на точността спрямо размера на дървото, точността на дървото е показана измерена върху примери за обучение и тестови примери.

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

Използването на отделен набор от данни за насочване на съкращаването е ефективен подход, при условие че е налично голямо количество данни. Една обща евристика е: наборът за обучение съставлява 60% от всички данни, наборът за валидиране 20%, а наборът за тестване 20%. Основният недостатък на този подход е, че когато данните са ограничени, задържането на част от тях за набора за валидиране намалява още повече броя на примерите, налични за обучение.

Следващият раздел представя алтернативен подход за съкращаване, който се оказа полезен в много практически ситуации, когато данните са ограничени. Бяха предложени и много допълнителни техники, включващи разделяне на наличните данни няколко различни пъти по множество начини, след което осредняване на резултатите.

2. Правило за последваща резитба

Правилото за последващо подрязване включва следните стъпки:

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

За илюстрация, разгледайте отново дървото на решенията, показано на горната фигура. При правило след подрязване се генерира едно правило за всеки листов възел в дървото. Всеки тест на атрибут по пътя от корена до листа се превръща в предшестващо правило (предварително условие), а класификацията в листовия възел става следствие на правило (последусловие). Например, най-лявата пътека на дървото на фигурата се преобразува в правилото

АКО (Изглед = Слънчево) ^ (Влажност = Висока)
ТОГАВА PlayTennis = Не

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

(Изглед = Слънчево) и (Влажност = Висока)

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

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

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

2. Включване на атрибути с непрекъсната стойност

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

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

2. Атрибутите, тествани във възлите за вземане на решения на дървото, също трябва да имат дискретна стойност.

Това второ ограничение може лесно да бъде премахнато, така че атрибутите на решение с непрекъснати стойности да могат да бъдат включени в наученото дърво. За атрибут A, който е с непрекъсната стойност, алгоритъмът може динамично да създаде нов булев атрибут A, който е true, ако A ‹ c, и false в противен случай. Единственият въпрос е как да изберете най-добрата стойност за прага c.

Илюстрация: Да предположим, че искаме да включим атрибута с непрекъсната стойност Temperature. Да предположим освен това, че примерите за обучение, свързани с определен възел в дървото на решенията, имат следните стойности за температура и целевия атрибут PlayTennis.

Какъв булев атрибут, базиран на праг, трябва да се дефинира въз основа на температура?

  • Изберете праг, c, който произвежда най-голяма печалба от информация. Като сортираме примерите според непрекъснатия атрибут A, след което идентифицираме съседни примери, които се различават в тяхната целева класификация, ние може да генерира набор от кандидат прагове по средата между съответните стойности на A. Може да се покаже, че стойността на c, която максимизира печалбата от информация, трябва винаги да лежи на такава граница. След това тези прагове на кандидатите могат да бъдат оценени чрез изчисляване на притока на информация, свързан с всеки от тях.
  • В настоящия пример има два кандидат-прага, съответстващи на стойностите на температурата, при които се променя стойността на PlayTennis: (48 + 60)/2 и (80 + 90)/2.
  • След това усилването на информацията може да бъде изчислено за всеки от кандидатстващите атрибути, Температура ›54 и Температура ›85 и може да бъде избран най-добрият (Температура ›54)
  • Този динамично създаден булев атрибут може след това да се конкурира с другите кандидат-атрибути с дискретни стойности, налични за разрастване на дървото на решенията.

3. Алтернативни мерки за избор на атрибути

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

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

Алтернативна мярка-1

Една алтернативна мярка, която е използвана успешно, е коефициентът на печалба (Quinlan 1986). Мярката за коефициент на усилване наказва атрибути като дата, като включва термин, наречен информация за разделяне, който е чувствителен към това колко широко и равномерно атрибутът разделя данните:

където S1 до Sc са c подмножества от примери, получени от разделянето на S чрез c-стойностния атрибут A. Обърнете внимание, че Splitlnformation всъщност е ентропията на S по отношение на стойностите на атрибут A. Това е в контраст с предишните ни употреби на ентропия, в която разгледахме само ентропията на S по отношение на целевия атрибут, чиято стойност трябва да бъде предсказана от наученото дърво.

Мярката за коефициент на усилване се определя от гледна точка на по-ранната мярка за усилване, както и тази информация за разделяне, както следва

Терминът Splitlnformation обезсърчава избора на атрибути с много равномерно разпределени стойности (напр. Дата).

Един практически проблем, който възниква при използването на GainRatio вместо Gain за избор на атрибути, е, че знаменателят може да бъде нула или много малък, когато |Si| ≈ |S| за един от Si. Това или прави GainRatio недефиниран или много голям за атрибути, които случайно имат една и съща стойност за почти всички членове на S. За да избегнем избирането на атрибути само на тази основа, можем да приемем някаква евристика, като например първо да изчислим Gain на всеки атрибут, след това прилагане на теста GainRatio само като се вземат предвид онези атрибути с над средното усилване (Quinlan 1986).

Алтернативна мярка-2

Алтернатива на GainRatio, предназначена за директно справяне с горната трудност, е мярка, базирана на разстоянието, въведена от Лопес де Мантарас през 1991 г. Тази мярка се основава на определяне на показател за разстояние между дяловете на данните. Всеки атрибут се оценява въз основа на разстоянието между дяла на данните, който създава, и идеалния дял (т.е. дялът, който перфектно класифицира данните за обучение). Избира се атрибутът, чийто дял е най-близо до перфектния дял. Той не е предубеден към атрибути с голям брой стойности и точността на прогнозиране на индуцираните дървета не се различава значително от тази, получена с мерките за печалба и съотношение на печалба. Въпреки това, тази мярка за разстояние избягва практическите трудности, свързани с мярката GainRatio, и в него тя създава значително по-малки дървета в случай на набори от данни, чиито атрибути имат много различен брой стойности.

4. Обработка на липсващи стойности на атрибути

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

Разгледайте ситуацията, в която Gain(S, A) трябва да се изчисли във възел n в дървото за вземане на решения, за да се оцени дали атрибутът A е най-добрият атрибут за тестване в този възел за вземане на решения. Да предположим, че (x, c(x)) е един от примерите за обучение в S и че стойността A(x) е неизвестна.

Метод-1

Една стратегия за справяне с липсващата стойност на атрибута е да му се присвои стойността, която е най-често срещана сред примерите за обучение във възел n. Като алтернатива можем да му присвоим най-често срещаната стойност сред примерите във възел n, които имат класификацията c(x). Разработеният пример за обучение, използващ тази прогнозна стойност за A(x), може след това да се използва директно от съществуващия алгоритъм за обучение на дървото на решенията.

Метод-2

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

Например, при даден булев атрибут A, ако възел n съдържа шест известни примера с A = 1 и четири с A = 0, тогава бихме казали, че вероятността A(x) = 1 е 0,6, а вероятността A(x ) = 0 е 0,4.

Дробна 0,6 от екземпляра x сега се разпределя надолу по клона за A = 1, а дробна 0,4 от x надолу по другия клон на дървото. Тези дробни примери се използват за целите на изчисляване на усилването на информацията и могат да бъдат допълнително подразделени в следващите клонове на дървото, ако трябва да се тества втора стойност на липсващ атрибут. Същото фракциониране на примери може да се приложи и след обучение, за класифициране на нови екземпляри, чиито стойности на атрибути са неизвестни. В този случай класификацията на новия екземпляр е просто най-вероятната класификация, изчислена чрез сумиране на теглата на фрагментите на екземпляра, класифицирани по различни начини в листовите възли на дървото.

Този метод за обработка на стойности на липсващи атрибути се използва в C4.5

5. Боравене с атрибути с различни разходи

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

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

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

Метод-1

Тан и Шлимер (1990) и Тан (1993) описват един такъв подход и го прилагат към задача за възприемане на робот, при която роботът трябва да се научи да класифицира различни обекти според начина, по който могат да бъдат хванати от манипулатора на робота. В този случай атрибутите съответстват на различни показания на сензори, получени от подвижен сонар на робота. Цената на атрибута се измерва с броя секунди, необходими за получаване на стойността на атрибута чрез позициониране и работа със сонара. Те демонстрират, че се научават по-ефективни стратегии за разпознаване, без да се жертва точността на класификацията, като се замени мярката за избор на атрибут за придобиване на информация със следната мярка

Метод-2

Nunez (1988) описва подобен подход и приложението му за изучаване на медицински диагностични правила. Тук атрибутите са различни симптоми и лабораторни изследвания с различна цена. Неговата система използва малко по-различна мярка за избор на атрибут, където w ∈ [0, 1] е константа, която определя относителното значение на разходите спрямо печалбата от информация.

Благодаря за четенето ………