Ц4.5 алгоритам

Ц4.5 је алгоритам који генерише дрво одлучивања и који је развио Росс Qуинлан. Ц4.5 је унапређење у односу на ИД3 алгоритам који је такође пронашао Qуинлан. Дрво одлучивања генерисано помоћу Ц4.5 алгоритма се користити за класификацију због чега се често назива и статистички класификатор.

Алгоритам

Ц4.5 прави дрво одлучивања из скупа тренинг података на исти начин на који то ради и ИД3 алгоритам, користећи концепт ентропије. Тренинг подаци су скуп $S={s_{1},s_{2},...}$ од већ класификованих узорака. Сваки узорак $s_{i}$ састоји се од п-димензионалног вектора $(x_{1,i},x_{2,i},...,x_{p,i})$, где $x_{j}$ представља атрибуте или функције узорка, као и класу којој $s_{i}$ припада.

У сваком чвору дрвета, Ц4.5 бира атрибут који најефикасније раздваја скуп узорака у подскупове повећавајући квалитет у једној или другој класи. Критеријум по којем се раздваја је нормализована информациона добит. Атрибути који имају највећу нормализовану информациону добит бирају се за доношење одлуке. Ц4.5 алгоритам се онда рекурзивно примењује на мањим подлистама.

Овај алгоритам има неколико основних случајева.

• Сви узорци припадају истој класи. Када се ово догоди, креирамо лист у дрвету одлучивања који нам говори да одаберемо дату класу.
• Ниједна карактеристика не обезбеђује никакву информациону добит. У овом случају, Ц4.5 креира одлуку на чвору вишег нивоа користећи очекивану вредност класе.
• Појављује се инстанца класе која претходно није разматрана. Ц4.5 опет креира одлуку на чвору вишег нивоа користећи очекивану вредност класе.

Псеудокод

Општи алгоритам за прављење дрвета одлучивања је:

1. Проверити базне случајеве
2. За сваки атрибут а
   1. Пронаћи нормализовану информациону добит приликом раздвајања по а
3. Поставити да а_макс буде атрибут који има највећу нормализовану информациону добит
4. Креирати чвор који се дели по атрибуту а_макс
5. Применити рекурзију на подлисте (које су добијене раздвајањем по атрибуту а_макс) и додати те чворове као децу датог чвора

Имплементација

Ј48 је Јава имплементација Ц4.5 алгоритма отвореног кода у Wека алату за истаживање података. ТимеСлеутх проширује употребу Ц4.5 алгоритма коришћењем привремених и узрочних открића. ТимеСлеутх такође допушта конверзију Ц4.5 правила у Пролог исказе.

Побољшања у односу на ИД3 алгоритам

Ц4.5 је направио низ побољшања у односу на ИД3. Нека од побољшања су:

• Подржавање и континуираних и дискретних атрибута - Да би подржао континуиране атрибуте, Ц4.5 креира праг и онда дели листе на оне чија вредност атрибута је изнад прага и на оне чија је вредност атрибута мања или једнака прагу.
• Подржавање тренинг података са недостајућим вредностима атрибута - Ц4.5 дозвољава да вредност атрибута буде означена са ? уколико недостаје. Недостајућа вредност се једноставно не користи у израчунавањима добити и ентропије.
• Подржавање атрибута са различитим трошковима.
• Поткресивање дрвета након креирања - Ц4.5 алгоритам после креирања дрвета одлучивања се враћа кроз дрво и покушава да уклони гране које нису од користи замењујући их за лист.

Побољшања у Ц5.0/Сее5 алгоритму

Qуинлан је радио и на стварању Ц5.0/Сее5 (Ц5.0 за Униx/Линуx, Сее5 за Wиндоwс) алгоритма који ће бити комерцијалан. Алгоритам Ц5.0 нуди низ унапређења у односу на Ц4.5. Нека од унапређења су:

• Брзина - Ц5.0 је значајно бржи од Ц4.5 (неколико редова величине)
• Употреба меморије - Ц5.0 је много меморијски ефикаснији од Ц4.5
• Мање дрво одлучивања - Ц5.0 добија сличне резултате као и Ц4.5 али са знатно мањим дрветом одлучивања.
• Подршка за боостинг - побољшава дрвеће и даје им већу тачност.
• Ц5.0 има могућност да аутоматски уклони атрибуте који му нису од помоћи.

Изворни код за Линуx верзију алгоритма Ц5.0 је доступан под ГНУ лиценцом.