От списък с правила към дърво от въпроси
Миналия час записахте правила в таблица и бяхте машината за извод. Сигурно сте забелязали нещо неудобно: при всеки нов клиент минавате целия списък отгоре надолу и проверявате условия, които изобщо не са нужни. Специалистът не работи така. Той задава един въпрос, и според отговора — следващия. Това е играта на „двадесет въпроса“, а картинката ѝ е решаващо дърво (decision tree).
Решаващо дърво
Схема, в която всеки вътрешен възел е въпрос, всяко ребро — отговор, а всяко листо — извод. Отговорът на потребителя определя по кое ребро се слиза надолу, докато се стигне до листо.
В урок 15 ще видите, че такова дърво може да се научи от данни. Днес го проектирате на ръка — както инженерите го правят за диагностика, за правила на обслужване и за всяка задача, в която знанието е ясно, а грешката трябва да може да се обясни.
Кой въпрос е първи
Един и същ набор от изводи може да се подреди в много различни дървета. Добрият въпрос за корена има три свойства:
- Отговорим — потребителят може да отговори веднага, без уред и без експерт. „Вали ли?“ е добър; „Каква е влажността на въздуха?“ — не.
- Ясен — „да/не“ или няколко точно изброени отговора. Без „горе-долу“.
- Най-полезен — отхвърля най-много възможности наведнъж, тоест дели изводите на възможно най-равни части.
Защо равни части? Защото всеки въпрос „да/не“ в най-добрия случай намалява възможностите наполовина. Двадесет такива въпроса стигат за 2²⁰ — над милион — различни отговора. Ако обаче първият въпрос отделя една възможност от останалите десет, в девет от десет случая не сте научили почти нищо.
| Кандидат за корен | „да“ оставя | „не“ оставя | Полезност |
|---|---|---|---|
| Растението е на пряко слънце? | 1 диагноза | 5 диагнози | слаба |
| Почвата е мокра? | 2 диагнози | 4 диагнози | средна |
| Проблемът е по листата? | 3 диагнози | 3 диагнози | най-добра |
Пълнота, противоречия и излишни въпроси
- Пълнота — за всеки възможен отговор на всеки въпрос има ребро надолу, което завършва в листо. Ако след „не“ няма нищо, дървото мълчи — същата непълнота, която видяхте при правилата.
- Противоречие — един и същ вход води до два различни извода. В списък от правила това се случва лесно. В дърво е невъзможно по построение: всеки вход минава по точно един път и стига до едно листо.
- Излишен въпрос — двата му отговора водят до един и същ извод. Махнете го; той само бави потребителя.
- Дълбочина — най-дългият път от корена до листо е броят въпроси в най-лошия случай. Дърво с добре подредени въпроси е плитко.
Дърво и правила са едно и също
Прочетете дървото от фигурата път по път — от корена до всяко листо. Всеки път е правило, чието условие са отговорите по пътя, свързани с „и“:
АКО под 2 км и вали ТОГАВА автобус
АКО под 2 км и не вали ТОГАВА пеша
АКО не под 2 км и има пряк автобус ТОГАВА градски транспорт
АКО не под 2 км и няма пряк автобус и бързате ТОГАВА такси
АКО не под 2 км и няма пряк автобус и не бързате ТОГАВА колелоПет листа — пет правила. Обратното също работи: ако имате списък от правила, изберете условие, което се среща в много от тях, за корен, и разделете правилата според него.
| Списък от правила | Решаващо дърво | |
|---|---|---|
| Ред на въпросите | няма — проверяват се всички условия | вграден — следващият въпрос зависи от отговора |
| Противоречия | възможни, трудно се забелязват | невъзможни по построение |
| Ново знание | още един ред | ново листо или пренареден клон |
| Четимост | добра при малко правила | добра дори при десетки листа |
Следващия час дървото става програма. Погледнете колко прилича на вложени условия — формата на кода е формата на дървото:
if (podDvaKm)
{
if (vali) savet = "автобус";
else savet = "пеша";
}
else
{
if (imaPryakAvtobus) savet = "градски транспорт";
else if (barzate) savet = "такси";
else savet = "колело";
}Какво трябва да запомниш
- Възел = въпрос, ребро = отговор, листо = извод. Входът минава по точно един път.
- Най-отгоре стои въпросът, който отхвърля най-много възможности — дели изводите най-равно.
- Пълнота: всяко ребро свършва в листо. Излишен въпрос: двата му отговора водят до едно и също.
- Дървото не може да си противоречи; списъкът от правила може.
- Всеки път от корена до листо е едно правило „ако – тогава“; дърво с N листа = N правила.
- В код дървото са вложени
if/else— темата на урок 7.