www.wikidata.uk-ua.nina.az

Дерево ухвалення рішень У Вікіпедії є статті про інші значення цього терміна Рішення також можуть називатися деревами кл

Дерево ухвалення рішень

У Вікіпедії є статті про інші значення цього терміна: Рішення.

Дерево ухвалення рішень (також можуть називатися деревами класифікацій або регресійними деревами) — використовується в галузі статистики та аналізу даних для прогнозних моделей. Структура дерева містить такі елементи: «листя» і «гілки». На ребрах («гілках») дерева ухвалення рішення записані атрибути, від яких залежить цільова функція, в «листі» записані значення цільової функції, а в інших вузлах — атрибути, за якими розрізняються випадки. Щоб класифікувати новий випадок, треба спуститися по дереву до листа і видати відповідне значення. Подібні дерева рішень широко використовуються в інтелектуальному аналізі даних. Мета полягає в тому, щоб створити модель, яка прогнозує значення цільової змінної на основі декількох змінних на вході.

Кожен лист являє собою значення цільової змінної, зміненої в ході руху від кореня по листа. Кожен внутрішній вузол відповідає одній з вхідних змінних. Дерево може бути також «вивчено» поділом вихідних наборів змінних на підмножини, що засновані на тестуванні значень атрибутів. Це процес, який повторюється на кожному з отриманих підмножин. Рекурсія завершується тоді, коли підмножина в вузлі має ті ж значення цільової змінної, таким чином, воно не додає цінності для пророкувань. Процес, що йде «згори донизу», індукція дерев рішень (TDIDT), є прикладом поглинаючого «жадібного» алгоритму, і на сьогодні є найбільш поширеною стратегією дерев рішень для даних, але це не єдина можлива стратегія. В інтелектуальному аналізі даних, дерева рішень можуть бути використані як математичні та обчислювальні методи, щоб допомогти описати, класифікувати і узагальнити набір даних, які можуть бути записані таким чином:

Залежна змінна Y є цільовою змінною, яку необхідно проаналізувати, класифікувати й узагальнити. Вектор х складається з вхідних змінних , , тощо, які використовуються для виконання цього завдання.

Основні визначення Редагувати

В аналізі рішень «дерево рішень» використовуються як візуальний і аналітичний інструмент підтримки ухвалення рішень, де розраховуються очікувані значення (або очікувана корисність) конкуруючих альтернатив.

Дерево рішень складається з трьох типів вузлів:

  • Вузли рішення — зазвичай представлені квадратами
  • Імовірнісні вузли — представляються у вигляді кола
  • Замикаючі вузли — представляються у вигляді трикутника

На малюнку, представленому вище, дерево рішень слід читати зліва направо. Дерево рішень не може містити в собі циклічних елементів, тобто кожен новий лист згодом може лише розщеплюватися, відсутні сходження шляхів. Таким чином, при конструюванні дерева вручну, ми можемо зіткнутися з проблемою його розмірності, тому, як правило, дерево рішення ми можемо отримати за допомогою спеціалізованих комп'ютерних програм. Зазвичай дерево рішень представляється у вигляді символічної схеми, завдяки якій його простіше сприймати і аналізувати.

Типологія дерев Редагувати

Дерева рішень, використовувані в Data Mining, бувають двох основних типів:

  • Аналіз дерева класифікації, коли прогнозований результат є класом, до якого належать дані;
  • Регресійний аналіз дерева, коли прогнозований результат можна розглядати як дійсне число (наприклад, ціна на будинок, або тривалість перебування пацієнта в лікарні).

Згадані вище терміни вперше були використані Брейманом та ін. Перераховані типи мають деякі подібності, а також деякі відмінності, такі, як процедура, що використовується для визначення місця, де розбивати. Деякі методи дозволяють побудувати більше одного дерева рішень:

  1. Дерево рішень «мішок», найбільш раннє дерево рішень, будує кілька дерев рішень, неодноразово інтерполюючи дані із заміною, і дерева голосувань для прогнозу консенсусу;
  2. Випадковий класифікатор «лісовий» використовує ряд дерев рішень, з метою поліпшення ставки класифікації;
  3. «Підвищені» дерева можуть бути використані для регресійного типу та класифікації типу проблем.
  4. «Обертання лісу» — дерева, в яких кожне дерево рішень аналізується першим застосуванням методу головних компонент (PCA) на випадкові підмножини вхідних функцій.

Алгоритми побудови дерева Редагувати

Загальна схема побудови дерева ухвалення рішень за тестовими прикладам виглядає таким чином:

  • Вибираємо черговий атрибут , поміщаємо його в корінь.
  • Для всіх його значень :
    • Залишаємо з тестових прикладів тільки ті, у яких значення атрибута дорівнює
    • Рекурсивно будуємо дерево в цьому нащадку

Основне питання: як вибирати черговий атрибут?

Є різні способи вибирати черговий атрибут:

  • Алгоритм ID3, де вибір атрибута відбувається на підставі приросту інформації (англ. Gain), або на підставі Коефіцієнту Джині.
  • Алгоритм C4.5 (поліпшена версія ID3), де вибір атрибута відбувається на підставі нормалізованого приросту інформації (англ. Gain Ratio).
  • Алгоритм CART[ru] і його модифікації — IndCART, DB-CART.
  • Автоматичний детектор взаємодії Хі-квадрат (CHAID). Виконує багаторівневий поділ при розрахунку класифікації дерев;
  • MARS: розширює дерева рішень для поліпшення обробки цифрових даних.

На практиці в результаті роботи цих алгоритмів часто виходять занадто деталізовані дерева, які при їх подальшому застосуванні дають багато помилок. Це пов'язано з явищем перенавчання. Для скорочення дерев використовується відсікання гілок (англ. pruning).

Регулювання глибини дерева Редагувати

Регулювання глибини дерева — це техніка, яка дозволяє зменшувати розмір дерева рішень, видаляючи ділянки дерева, які мають маленьку вагу.

Одне з питань, яке виникає в алгоритмі дерева рішень — це оптимальний розмір кінцевого дерева. Так, невелике дерево може не охопити ту чи іншу важливу інформацію щодо вибіркового простору. Тим не менше, важко сказати, коли алгоритм повинен зупинитися, тому що неможливо спрогнозувати, додавання якого вузла дозволить значно зменшити помилку. Ця проблема відома як «ефект горизонту». Тим не менш, загальна стратегія обмеження дерева зберігається, тобто видалення вузлів реалізується в разі, якщо вони не дають додаткової інформації.

Необхідно зазначити, що регулювання глибини дерева повинно зменшити розмір навчальної моделі дерева без зменшення точності її прогнозу або за допомогою перехресної перевірки. Є багато методів регулювання глибини дерева, які відрізняються вимірюванням оптимізації продуктивності.

Методи регулювання Редагувати

Скорочення дерева може здійснюватися зверху вниз або знизу вгору. Зверху вниз — обрізка починається з кореня, знизу вгору — скорочується число листя дерева. Один з найпростіших методів регулювання — зменшення помилки обмеження дерева. Починаючи з листя, кожен вузол замінюється на найпопулярніший клас. Якщо на точність передбачення це не впливає, то зміна зберігається.

Приклад завдання Редагувати

Припустімо, що нас цікавить, чи виграє наша улюблена футбольна команда наступний матч. Ми знаємо, що це залежить від ряду параметрів; перераховувати їх всі — завдання безнадійне, тому обмежимося основними:

  • Чи вище перебуває суперник по турнірній таблиці;
  • Чи вдома проходить матч;
  • Чи пропускає матч хтось із лідерів команди;
  • Чи йде дощ.

У нас є деяка статистика на цей рахунок:

Суперники Граємо Лідери Дощ Перемога
Вище Вдома На місці Так Ні
Вище Вдома На місці Ні Так
Вище Вдома Пропускають Ні Ні
Нижче Вдома Пропускають Ні Так
Нижче У гостях Пропускають Ні Ні
Нижче Вдома Пропускають Так Так
Вище У гостях На місці Так Ні
Нижче У гостях На місці Ні ???

Хочеться зрозуміти, чи виграє наша команда в черговій грі.

Див. також Редагувати

Примітки Редагувати

  1. ↑ Breiman, Leo; Friedman, J. H., Olshen, R. A., & Stone, C. J. (1984). Classification and regression trees. Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software. ISBN 978-0-412-04841-8.
  2. Breiman, L. (1996). Bagging Predictors. «Machine Learning, 24»: pp. 123–140.
  3. Friedman, J. H. (1999). Stochastic gradient boosting. Stanford University.
  4. Hastie, T., Tibshirani, R., Friedman, J. H. (2001). The elements of statistical learning: Data mining, inference, and prediction. New York: Springer Verlag.
  5. Kass, G. V. (1980). «An exploratory technique for investigating large quantities of categorical data». Applied Statistics 29 (2): 119–127. DOI: 10.2307/2986296. JSTOR 2986296.
  6. Fast, Bottom-Up Decision Tree Pruning Algorithm

Посилання Редагувати

Література Редагувати

  • Паклин Н.Б., Орешков В.И. Глава 9. // Бизнес-аналитика: от данных к знаниям(+CD): Учебное пособие. 2-е изд. — ISBN 978-5-459-00717-6.
  • Ананій В. Левітін. Глава 10. Обмеження потужності алгоритмів: Дерева прийняття рішення // Алгоритми: введення в розробку й аналіз = Introduction to The Design and Analysis of Aigorithms. — ISBN 0-201-74395-7.
В іншому мовному розділі є повніша стаття Decision tree(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою перекладу з англійської.
  • Дивитись автоперекладену версію статті з мови «англійська».
  • Перекладач повинен розуміти, що відповідальність за кінцевий вміст статті у Вікіпедії несе саме автор редагувань. Онлайн-переклад надається лише як корисний інструмент перегляду вмісту зрозумілою мовою. Не використовуйте невичитаний і невідкоригований машинний переклад у статтях української Вікіпедії!
  • Машинний переклад Google є корисною відправною точкою для перекладу, але перекладачам необхідно виправляти помилки та підтверджувати точність перекладу, а не просто скопіювати машинний переклад до української Вікіпедії.
  • Не перекладайте текст, який видається недостовірним або неякісним. Якщо можливо, перевірте текст за посиланнями, поданими в іншомовній статті.
  • Докладні рекомендації: див. Вікіпедія:Переклад.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
U Vikipediyi ye statti pro inshi znachennya cogo termina Rishennya Derevo uhvalennya rishen takozh mozhut nazivatisya derevami klasifikacij abo regresijnimi derevami vikoristovuyetsya v galuzi statistiki ta analizu danih dlya prognoznih modelej Struktura dereva mistit taki elementi listya i gilki Na rebrah gilkah dereva uhvalennya rishennya zapisani atributi vid yakih zalezhit cilova funkciya v listi zapisani znachennya cilovoyi funkciyi a v inshih vuzlah atributi za yakimi rozriznyayutsya vipadki Shob klasifikuvati novij vipadok treba spustitisya po derevu do lista i vidati vidpovidne znachennya Podibni dereva rishen shiroko vikoristovuyutsya v intelektualnomu analizi danih Meta polyagaye v tomu shob stvoriti model yaka prognozuye znachennya cilovoyi zminnoyi na osnovi dekilkoh zminnih na vhodi Kozhen list yavlyaye soboyu znachennya cilovoyi zminnoyi zminenoyi v hodi ruhu vid korenya po lista Kozhen vnutrishnij vuzol vidpovidaye odnij z vhidnih zminnih Derevo mozhe buti takozh vivcheno podilom vihidnih naboriv zminnih na pidmnozhini sho zasnovani na testuvanni znachen atributiv Ce proces yakij povtoryuyetsya na kozhnomu z otrimanih pidmnozhin Rekursiya zavershuyetsya todi koli pidmnozhina v vuzli maye ti zh znachennya cilovoyi zminnoyi takim chinom vono ne dodaye cinnosti dlya prorokuvan Proces sho jde zgori donizu indukciya derev rishen TDIDT ye prikladom poglinayuchogo zhadibnogo algoritmu i na sogodni ye najbilsh poshirenoyu strategiyeyu derev rishen dlya danih ale ce ne yedina mozhliva strategiya V intelektualnomu analizi danih dereva rishen mozhut buti vikoristani yak matematichni ta obchislyuvalni metodi shob dopomogti opisati klasifikuvati i uzagalniti nabir danih yaki mozhut buti zapisani takim chinom x Y x 1 x 2 x 3 x k Y displaystyle x Y x 1 x 2 x 3 dots x k Y Zalezhna zminna Y ye cilovoyu zminnoyu yaku neobhidno proanalizuvati klasifikuvati j uzagalniti Vektor h skladayetsya z vhidnih zminnih x 1 displaystyle x 1 x 2 displaystyle x 2 x 3 displaystyle x 3 tosho yaki vikoristovuyutsya dlya vikonannya cogo zavdannya Zmist 1 Osnovni viznachennya 2 Tipologiya derev 3 Algoritmi pobudovi dereva 4 Regulyuvannya glibini dereva 4 1 Metodi regulyuvannya 5 Priklad zavdannya 6 Div takozh 7 Primitki 8 Posilannya 9 LiteraturaOsnovni viznachennya RedaguvatiV analizi rishen derevo rishen vikoristovuyutsya yak vizualnij i analitichnij instrument pidtrimki uhvalennya rishen de rozrahovuyutsya ochikuvani znachennya abo ochikuvana korisnist konkuruyuchih alternativ Derevo rishen skladayetsya z troh tipiv vuzliv Vuzli rishennya zazvichaj predstavleni kvadratami Imovirnisni vuzli predstavlyayutsya u viglyadi kola Zamikayuchi vuzli predstavlyayutsya u viglyadi trikutnika nbsp Na malyunku predstavlenomu vishe derevo rishen slid chitati zliva napravo Derevo rishen ne mozhe mistiti v sobi ciklichnih elementiv tobto kozhen novij list zgodom mozhe lishe rozsheplyuvatisya vidsutni shodzhennya shlyahiv Takim chinom pri konstruyuvanni dereva vruchnu mi mozhemo zitknutisya z problemoyu jogo rozmirnosti tomu yak pravilo derevo rishennya mi mozhemo otrimati za dopomogoyu specializovanih komp yuternih program Zazvichaj derevo rishen predstavlyayetsya u viglyadi simvolichnoyi shemi zavdyaki yakij jogo prostishe sprijmati i analizuvati nbsp Tipologiya derev RedaguvatiDereva rishen vikoristovuvani v Data Mining buvayut dvoh osnovnih tipiv Analiz dereva klasifikaciyi koli prognozovanij rezultat ye klasom do yakogo nalezhat dani Regresijnij analiz dereva koli prognozovanij rezultat mozhna rozglyadati yak dijsne chislo napriklad cina na budinok abo trivalist perebuvannya paciyenta v likarni Zgadani vishe termini vpershe buli vikoristani Brejmanom ta in 1 Pererahovani tipi mayut deyaki podibnosti a takozh deyaki vidminnosti taki yak procedura sho vikoristovuyetsya dlya viznachennya miscya de rozbivati 1 Deyaki metodi dozvolyayut pobuduvati bilshe odnogo dereva rishen Derevo rishen mishok najbilsh rannye derevo rishen buduye kilka derev rishen neodnorazovo interpolyuyuchi dani iz zaminoyu i dereva golosuvan dlya prognozu konsensusu 2 Vipadkovij klasifikator lisovij vikoristovuye ryad derev rishen z metoyu polipshennya stavki klasifikaciyi Pidvisheni dereva mozhut buti vikoristani dlya regresijnogo tipu ta klasifikaciyi tipu problem 3 Obertannya lisu dereva v yakih kozhne derevo rishen analizuyetsya pershim zastosuvannyam metodu golovnih komponent PCA na vipadkovi pidmnozhini vhidnih funkcij 4 Algoritmi pobudovi dereva RedaguvatiZagalna shema pobudovi dereva uhvalennya rishen za testovimi prikladam viglyadaye takim chinom Vibirayemo chergovij atribut Q displaystyle Q nbsp pomishayemo jogo v korin Dlya vsih jogo znachen i displaystyle i nbsp Zalishayemo z testovih prikladiv tilki ti u yakih znachennya atributa Q displaystyle Q nbsp dorivnyuye i displaystyle i nbsp Rekursivno buduyemo derevo v comu nashadkuOsnovne pitannya yak vibirati chergovij atribut Ye rizni sposobi vibirati chergovij atribut Algoritm ID3 de vibir atributa vidbuvayetsya na pidstavi prirostu informaciyi angl Gain abo na pidstavi Koeficiyentu Dzhini Algoritm C4 5 polipshena versiya ID3 de vibir atributa vidbuvayetsya na pidstavi normalizovanogo prirostu informaciyi angl Gain Ratio Algoritm CART ru i jogo modifikaciyi IndCART DB CART Avtomatichnij detektor vzayemodiyi Hi kvadrat CHAID Vikonuye bagatorivnevij podil pri rozrahunku klasifikaciyi derev 5 MARS rozshiryuye dereva rishen dlya polipshennya obrobki cifrovih danih Na praktici v rezultati roboti cih algoritmiv chasto vihodyat zanadto detalizovani dereva yaki pri yih podalshomu zastosuvanni dayut bagato pomilok Ce pov yazano z yavishem perenavchannya Dlya skorochennya derev vikoristovuyetsya vidsikannya gilok angl pruning Regulyuvannya glibini dereva RedaguvatiRegulyuvannya glibini dereva ce tehnika yaka dozvolyaye zmenshuvati rozmir dereva rishen vidalyayuchi dilyanki dereva yaki mayut malenku vagu Odne z pitan yake vinikaye v algoritmi dereva rishen ce optimalnij rozmir kincevogo dereva Tak nevelike derevo mozhe ne ohopiti tu chi inshu vazhlivu informaciyu shodo vibirkovogo prostoru Tim ne menshe vazhko skazati koli algoritm povinen zupinitisya tomu sho nemozhlivo sprognozuvati dodavannya yakogo vuzla dozvolit znachno zmenshiti pomilku Cya problema vidoma yak efekt gorizontu Tim ne mensh zagalna strategiya obmezhennya dereva zberigayetsya tobto vidalennya vuzliv realizuyetsya v razi yaksho voni ne dayut dodatkovoyi informaciyi 6 Neobhidno zaznachiti sho regulyuvannya glibini dereva povinno zmenshiti rozmir navchalnoyi modeli dereva bez zmenshennya tochnosti yiyi prognozu abo za dopomogoyu perehresnoyi perevirki Ye bagato metodiv regulyuvannya glibini dereva yaki vidriznyayutsya vimiryuvannyam optimizaciyi produktivnosti Metodi regulyuvannya Redaguvati Skorochennya dereva mozhe zdijsnyuvatisya zverhu vniz abo znizu vgoru Zverhu vniz obrizka pochinayetsya z korenya znizu vgoru skorochuyetsya chislo listya dereva Odin z najprostishih metodiv regulyuvannya zmenshennya pomilki obmezhennya dereva Pochinayuchi z listya kozhen vuzol zaminyuyetsya na najpopulyarnishij klas Yaksho na tochnist peredbachennya ce ne vplivaye to zmina zberigayetsya Priklad zavdannya RedaguvatiPripustimo sho nas cikavit chi vigraye nasha ulyublena futbolna komanda nastupnij match Mi znayemo sho ce zalezhit vid ryadu parametriv pererahovuvati yih vsi zavdannya beznadijne tomu obmezhimosya osnovnimi Chi vishe perebuvaye supernik po turnirnij tablici Chi vdoma prohodit match Chi propuskaye match htos iz lideriv komandi Chi jde dosh U nas ye deyaka statistika na cej rahunok Superniki Grayemo Lideri Dosh PeremogaVishe Vdoma Na misci Tak NiVishe Vdoma Na misci Ni TakVishe Vdoma Propuskayut Ni NiNizhche Vdoma Propuskayut Ni TakNizhche U gostyah Propuskayut Ni NiNizhche Vdoma Propuskayut Tak TakVishe U gostyah Na misci Tak NiNizhche U gostyah Na misci Ni Hochetsya zrozumiti chi vigraye nasha komanda v chergovij gri Div takozh RedaguvatiRandom forest klasifikator zasnovanij na zastosuvanni komitetiv z virishalnih derev Perenavchannya Mashinne navchannya Tablicya uhvalennya rishen en Primitki Redaguvati a b Breiman Leo Friedman J H Olshen R A amp Stone C J 1984 Classification and regression trees Monterey CA Wadsworth amp Brooks Cole Advanced Books amp Software ISBN 978 0 412 04841 8 Breiman L 1996 Bagging Predictors Machine Learning 24 pp 123 140 Friedman J H 1999 Stochastic gradient boosting Stanford University Hastie T Tibshirani R Friedman J H 2001 The elements of statistical learning Data mining inference and prediction New York Springer Verlag Kass G V 1980 An exploratory technique for investigating large quantities of categorical data Applied Statistics 29 2 119 127 DOI 10 2307 2986296 JSTOR 2986296 Fast Bottom Up Decision Tree Pruning AlgorithmPosilannya RedaguvatiKonspekt lekciyi po derevah uhvalennya rishen Arhivovano 2 kvitnya 2022 u Wayback Machine Algoritmi pobudovi derev rishen Arhivovano 15 bereznya 2015 u Wayback Machine BaseGroup Labs Decision trees applet provides several sample data sets of examples to learn and classifyLiteratura RedaguvatiPaklin N B Oreshkov V I Glava 9 Biznes analitika ot dannyh k znaniyam CD Uchebnoe posobie 2 e izd ISBN 978 5 459 00717 6 Ananij V Levitin Glava 10 Obmezhennya potuzhnosti algoritmiv Dereva prijnyattya rishennya Algoritmi vvedennya v rozrobku j analiz Introduction to The Design and Analysis of Aigorithms ISBN 0 201 74395 7 V inshomu movnomu rozdili ye povnisha stattya Decision tree angl Vi mozhete dopomogti rozshirivshi potochnu stattyu za dopomogoyu perekladu z anglijskoyi Divitis avtoperekladenu versiyu statti z movi anglijska Perekladach povinen rozumiti sho vidpovidalnist za kincevij vmist statti u Vikipediyi nese same avtor redaguvan Onlajn pereklad nadayetsya lishe yak korisnij instrument pereglyadu vmistu zrozumiloyu movoyu Ne vikoristovujte nevichitanij i nevidkorigovanij mashinnij pereklad u stattyah ukrayinskoyi Vikipediyi Mashinnij pereklad Google ye korisnoyu vidpravnoyu tochkoyu dlya perekladu ale perekladacham neobhidno vipravlyati pomilki ta pidtverdzhuvati tochnist perekladu a ne prosto skopiyuvati mashinnij pereklad do ukrayinskoyi Vikipediyi Ne perekladajte tekst yakij vidayetsya nedostovirnim abo neyakisnim Yaksho mozhlivo perevirte tekst za posilannyami podanimi v inshomovnij statti Dokladni rekomendaciyi div Vikipediya Pereklad Otrimano z https uk wikipedia org w index php title Derevo uhvalennya rishen amp oldid 40321360