КРИМИНАЛИСТИЧКО ПОЛИЦИЈСКА АКАДЕМИЈА
СМЕР
: Информатика и рачунарство
СЕМИНАРСКИ РАД
ПРЕДМЕТ: Аналитика података
ТЕМА: Алгоритми машинског учења и Стабла одлучивања
Професор:
Драган Ранђеловић
Земун, 2017.г.
ID3
Аутор ID3 (Iteratice Dichotomister Tree) je Роса Кинлана. Овај алгоритам је
намењена за решавање проблема класификације, а ради само са категоричним подацима.
Ова врста лагоритама извршава се у три корака, где се други и трећи корак
итеративно понављају:
1. Рачунање ентропије скупа случајева
2. Избор променљиве за гранање
3. Критеријума заустављања.
Да би се изабрала поменљива за гранање користи се Шенонов образац за ентропију.
Полази се од претпоставке да је најбоље иѕабрати променљиву која губи најмање
информација односно највише смањује ентропију система.
Шенанова образац за ентропију је:
H(S)=
Где је H(S) ентропија скупа случајева S, представља вероватноћу да ће одлука i
бити донесена, а n број различитих одлука које могу бити донете.
С обзиром да је овај алгоритам прилично једноставан, најлакше ћемо га приказати
кроз пример из следеће табеле.
Дан
Врем. прилике
Температура Влажност
Ветар
Играти?
1
sunčano
vruće
visoka
slab
NE
2
sunčano
vruće
visoka
jak
NE
3
oblačno
vruće
visoka
slab
DA
4
kišovito
toplo
visoka
slab
DA
5
kišovito
hladno
normalna
slab
DA
6
kišovito
hladno
normalna
jak
NE
7
oblačno
hladno
normalna
jak
DA
8
sunčano
toplo
visoka
slab
NE
2
9
sunčano
hladno
normalna
slab
DA
10
kišovito
toplo
normalna
slab
DA
11
sunčano
toplo
normalna
jak
DA
12
oblačno
toplo
visoka
jak
DA
13
oblačno
vruće
normalna
slab
DA
14
kišovito
toplo
visoka
jak
NE
У овој табели дати су неки случајеви из прошлости где се на основу временских
прилика одлучивало да ли ће се нека игра играти (на отвореном терену). У овој табели
атрибути
(колоне) описују компоненте временских прилика сваког случаја (реда). А
атрибут
играти?
представља одлуку у датом случају и назива се
атрибут одлуке
.
На почетку израчунавамо почетну ентропију која ће нам касније требати.
Напомињемо да овде можемо поједноставити логаритам:
Након израчунавања почетне ентропије, рачунамо ентропију за сваки атрибут
посебно, како би одлучили који ће од њих бити почетни чвор.
Као пример приказивања како се рачуна ентропија промењиве узећемо атрибут
ветар.
Функција за израчунавање ентропије промењиве израчунава се по следећој
формули:
У овој формули
представља број елемената са особином, односно категоријом
Х
i
,
укупан број случајева у скупу S, а H S
i
ентропија подскупа случајева категорије Х
i
.
3
Из приложеног видимо да највећу информациону добит има атрибут
временске
прилике.
Тако да ће се прво гранање извршити на том атрибуту, а почетак стабла
одлучивања ће изгледати као на следећој слици:
Из приложене табеле можемо закључити да када ког је временска прилика била
облачно, игра се играла. Тако да је почетна ентропија једнака нули, тако да гранање није
потребно. Док ће се за сунце и кишу поступак понављати све док не испуни критеријум
заустављања.
Да би стабло престало да се итеративно понавља користе се одређена правила:
1. Када чвор постане чист, односно сви случајеви припадају истој класи излазног
атрибута чвор неће бити даље дељен.
2. Ако је величина чвора (број случајева у подстаблу) мања од минималне
кориснички дефинисане вредности, чвор неће настати.
3. Ако атрибут има информациону добит од унапред задате вредности, атрибут неће
бити изабран као чвор.
Даље у решавању проблема правимо подскуп за атрибут сунце, као што је приказано у
следећој табели
5
