Erabaki-zuhaitzen bidezko ikaskuntza

Erabaki-zuhaitzen bidezko ikaskuntza eredu iragarle moduan erabaki-zuhaitza erabiltzen duen teknika da. Estatistikan, datu-meatzaritzan eta ikasketa automatikoan asko erabiltzen den eredu iragarlea da. Erabaki-aldagaia (edo klase-aldagaia) diskretua denean (balio kopuru finitua hartzen duenean) erabaki-zuhaitzak sailkatze-zuhaitz izena hartzen du eta jarraia denean (aldagaiak balio erreala hartzen duenean), erregresio-zuhaitz izena.

Artikulu hau datu-meatzaritzan erabiltzen diren erabaki-zuhaitzei buruzkoa da.

Orokorra

Erabaki-zuhaitz baten adibidea.

Erabaki-zuhaitzen bidezko ikaskuntza datu-meatzaritzan oso erabilia den teknika bat da^[1]. Eredu iragarlea izanik, kasu (instantzia, prototipo) berri baten aurrean bere klase-aldagaiaren balioari buruzko iragarpena egiteko balioko duen eredua sortzea da helburua. Kasuei buruzko informazioa aldagai iragarleek jasotzen dute. Eskuineko irudian erabaki-zuhaitz baten adibidea ikus daiteke. Barne-erpin bakoitza aldagai iragarle bati egiten zaion testari dagokio. Hosto bakoitzean klase-aldagairako iragarritako balioa zehazten da. Sailkatu beharreko kasu berri baten aurrean, aldagai iragarleen balioen arabera hosto batera edo bestera iritsi eta klase-aldagairako balio bat edo beste iragarriko dira.

Erabaki-zuhaitzen bidezko ikaskuntza gainbegiratutako sailkatzaileen artean dagoen teknikarik eraginkorrenetakoa da. Datu-multzo batetik abiatuz, ikaskuntza fasean zuhaitza entrenatu egiten dela esaten da (entrenamendu fasea). Horretarako, hasierako datu-multzoaren partizio bat sortuko da (hainbat azpi-multzo disjuntu) aldagai iragarleei (atributuei) egindako test-en bitartez. Prozesu hori behin eta berriz errepikatuko da modu errekurtsiboan datuen azpimultzo bakoitzarentzat. Azpimultzoko datu guztiek klase-aldagaian balio bera dutenean errekurtsiotik irten eta hostoa kokatuko da (klase-aldagaiarentzat balio jakin bat). Sailkapen-zuhaitzen indukziorako algoritmoari erabaki-zuhaitzen goitik-beherako indukzioa edo top-down induction of decision trees (TDIDT) deitzen zaio. Algoritmo irenskorra^[2] da; erpinetan lokalki optimoak diren erabakiak hartzen dira, baina hortik ezin da ondorioztatu optimoa den zuhaitza induzituko denik.

Zuhaitz-motak

Datu-meatzaritzan erabiltzen diren erabaki-zuhaitzak bi mota nagusitan bereiz daitezke:

• Sailkatze-zuhaitza: erabaki-aldagaia (klase-aldagaia) diskretua duen erabaki-zuhaitza da.
• Erregresio-zuhaitza: erabaki-aldagaia jarraia duen erabaki-zuhaitza da.

Ingelesezko Classification And Regression Tree (CART) termino orokorrak bi motako erabaki-zuhaitzak biltzen ditu, haien artean badituztelako antzekotasunak, baina baita desberdintasun nabariak ere (adarkatzeko baldintzetan, adibidez)^[3].

Bestalde, badira erabaki-zuhaitz bat baino gehiago induzitzeko teknikak. Hona hemen horietako batzuk:

• Bagging (Bootstrap aggregating) metodoak erabiliz hainbat erabaki-zuhaitz eraikitzen dira, entrenamendurako bootstrap bidez lortutako hainbat lagin desberdinetan oinarrituz. Test fasean, zuhaitzen iragarpenak bozketa bidez konbinatzen dira^[4].
  • Random Forests sailkatzailea Bagging teknikaren sortutako erabaki-zuhaitzen adibide bat da.
• Boosting teknikaren bidez zuhaitzak modu inkrementalean eraikitzen dira, iterazio bakoitzean pisuak esleituz aurreko iterazioan iragarpen okerra jaso duten kasuak indartzeko. Adibide ezagun bat AdaBoost algoritmoa da. Metodo honek bi zuhaitz motetarako balio du^[5][6].

Erabaki-zerrenda erabaki-zuhaitz berezi bat da. Zuhaitz-mota horretan barne-erpin bakoitzak zehazki bi ume ditu: hosto bat eta beste barne-erpin bat (erpin sakonenak izan ezik, horrek hosto bat besterik ez du izango haren ume izango dena). Erabaki-zerrenda zuhaitz sinplea dela esan daiteke eta entrenamendu-metodo ez-irenskorrak erabiltzea posiblea gertatzen da.

Zuhaitzen indukziorako algoritmoak

Sailkatze-zuhaitzen indukzioa entrenamendu fasean egiten den prozesua da. Horretarako beharrezkoa da datu-multzoan klasea esleitua duten kasuak izatea. Kasu horiek hainbat aldagai iragarleren bidez deskribatuak agertzen dira datu-basean. Erabaki-zuhaitzeko barne-erpin bakoitzak aldagai iragarleei egindako test bat adierazten du eta bertatik ateratzen den adar bakoitzak testaren emaitza diren balio posibleak dira. Hostoek klase-aldagairako balio bat finkatzen dute.

Zuhaitzak sortzeko indukzio-algoritmoek urrats bakoitzean datu-multzoa ondoen banatzen duten aldagai iragarlea aukeratzen dute. Banaketa hori ondoen egiten duen aldagai iragarlea zein den erabakitzeko garaian, algoritmoek metrika desberdinak erabiltzen dituzte. Metrika hori eta inausketarako estrategiak izan ohi da indukzio-algoritmoen arteko desberdintasun nabarmenena.

Erabaki-zuhaitzak induzitzeko hainbat algoritmo existitzen dira. Hona hemen ezagunenetako batzuk:

• ID3 algoritmoa (Iterative Dichotomiser 3)
• C4.5 algoritmoa (ID3-ren ondorengoa)
• CART (Classification And Regression Trees)
• CHAID (CHI-squared Automatic Interaction Detector).

ID3 eta CART modu independentean asmatu ziren 1970eko hamarkadan, baina antzeko metodoak dira.

Abantailak

Datu-meatzaritzako beste metodoekin alderatuta, erabaki-zuhaitzek hainbat abantaila dituzte:

• Ulertzen eta interpretatzen errazak dira. Zuhaitzen portaera ulertzea erraza da; ez dute ia azalpenik behar.
• Datuen aurre-prozesamendu txikia behar dute. Beste teknika batzuk erabiltzeko datuak aurre-prozesatu egin behar izaten dira, normalizatu edo aldagai birtualak sortu, adibidez.
• Zenbakizko aldagaiekin eta aldagai kualitatiboekin lan egiteko gai dira, beste teknika batzuk ez bezala. Neurona-sareek adibidez zenbakizko aldagaiekin egiten dute lan.
• Kutxa zuriko eredua erabiltzen dutela esaten da; ereduan ikusten den edozein gertaera logika boolearraren bidez erraz azal daiteke. Beste eredu batzuen portaera azaltzea oso zaila izaten da (neurona-sareena, adibidez).
• Test estatistikoen bidez eredua balida daiteke ereduaren fidagarritasuna estimatzeko.
• Zuhaitzak sendoak dira.
• Datu-base handiekin lan egiteko egokiak dira. Datu-multzo handien analisia egin daiteke konputagailu bidez denbora ez oso luzean.

Desabantailak

• Erabaki-zuhaitz optimoa induzitzearen arazoa NP-osoa da; oso ebazpen zailekoa. Hori dela eta, indukziorako algoritmoak heuristiketan oinarritzen dira. Algoritmo irenskorrak horren adibidea dira: erpinetan lokalki optimo diren erabakiak hartzen dira baina ezin dute bermatu globalki optimoa den zuhaitza eraikiko denik. Algoritmo irenskorren desabantailak murrizteko hainbat metodo proposatu izan dira, adibidez, informazio bikoitzeko distantzia erabiltzea.
• Indukzio-algoritmo batzuk konplexuegiak diren zuhaitzak sor ditzakete. Ondorioz, kasu berriak eredu horretara ondo ez egokitzea gerta daiteke. Ingelesez Overfitting deritzo efektu horri. Halako arazoak ekiditeko zuhaitzen kimaketa (Pruning) egin ohi da.
• Badira entrenatzen zailak diren kontzeptuak, erabaki-zuhaitzek modu errazean adierazi ezin dituzten problemak, XOR (Exclusive or), paritate-bita edo multiplexorea, adibidez. Halakoetarako induzitutako erabaki-zuhaitza izugarri handia izatea gerta daiteke.
• Aldagai iragarle desberdinek balio posible kopuru desberdinak dituztenean, informazio-kantitatearen metrikak balio posible gehiago dituzten aldagaiei lehentasuna ematen die. Indukzio-algoritmo batzuk arazo hori ebaztea lortu dute, Baldintzazko Inferentzia aplikatuz. C4.5 algoritmoan metrika desberdin bat erabiltzen da informazio-kantitatea neurtzeko, balio posible handiagoko aldagaien aldera alboratua ez dagoena.

Inplementazioak

Datu-meatzaritzarako software-pakete askok eskaintzen dituzte erabaki-zuhaitzen indukzio-algoritmoen inplementazioak. Software libre batzuk: Weka (software libreko datu-meatzaritzako suite bat, erabaki zuhaitzak induzitzeko algoritmo anitz eskaintzen ditu), scikit-learn (software libreko ikaskuntza liburutegi bat Python programazio-lengoaiarako), R programazio-lengoaia (konputazio estatistikorako software ingurune bat), Orange, KNIME, etab. Pribatibo batzuk: Matlab, RapidMiner.

Erreferentziak

1. (Ingelesez) Lior., Rokach,. (2008). Data mining with decision trees : theory and applications. World Scientific ISBN 9789812771711..
2. (Ingelesez) Quinlan., J.R,. (1986). Induction of Decision Trees.  doi:10.1007/bf00116251.pdf..
3. (Ingelesez) Breiman, Leo. (1993). Classification and regression trees. Chapman & Hall ISBN 9780412048418..
4. (Ingelesez) Breiman, Leo. (2017-11-30). «Bagging Predictors» Machine Learning 24 (2): 123–140.  doi:10.1023/A:1018054314350. ISSN 0885-6125..
5. (Ingelesez) Friedman, Jerome H.. (1999). Stochastic Gradient Boosting. .
6. (Ingelesez) Friedman, Jerome; Hastie, Trevor; Tibshirani, Robert. (2009). The Elements of Statistical Learning. .

Kanpo estekak