Lēmumu koki: kā optimizēt manu lēmumu pieņemšanas procesu?

Iedomāsimies, ka jūs spēlējat divdesmit jautājumu spēli. Jūsu pretinieks ir slepeni izvēlējies tēmu, un jums ir jāizdomā, ko viņš / viņa izvēlējās. Katrā piegājienā jūs varat uzdot jautājumu “jā” vai “nē”, un pretiniekam ir jāatbild patiesi. Kā uzzināt noslēpumu pēc iespējas mazāk jautājumu?

Būtu skaidrs, daži jautājumi ir labāki nekā citi. Piemēram, uzdot jautājumu “Vai tas var lidot?”, Jo tavs pirmais jautājums, visticamāk, būs neauglīgs, turpretī jautāt “Vai tas ir dzīvs?” Ir nedaudz noderīgāk. Intuitīvi jūs vēlaties, lai katrs jautājums ievērojami sašaurinātu iespējamo noslēpumu telpu, galu galā novedot pie jūsu atbildes.

Tā ir lēmumu koku pamatideja. Katrā brīdī jūs apsverat jautājumu kopumu, kas var sadalīt jūsu datu kopu. Jūs izvēlaties jautājumu, kas nodrošina vislabāko sadalījumu, un atkal atradīsit labākos jautājumus nodalījumiem. Jūs pārtraucat, kad visi punkti, kurus apsverat, ietilpst vienā klasē. Tad klasifikācijas uzdevums ir viegls. Jūs varat vienkārši paķert kādu punktu un notriekt to pa koku. Jautājumi vadīs to attiecīgajā klasē.

Svarīgi noteikumi

Lēmumu koks ir uzraudzīta mācību algoritma tips, ko var izmantot gan regresijas, gan klasifikācijas problēmās. Tas darbojas gan kategoriskiem, gan nepārtrauktiem ieejas un izejas mainīgajiem.

Nosakīsim svarīgu terminoloģiju lēmumu kokā, apskatot attēlu iepriekš:

  • Saknes mezgls apzīmē visu populāciju vai izlasi. Tālāk tas tiek sadalīts 2 vai vairāk viendabīgās kopās.
  • Sadalīšana ir mezgla sadalīšanas process 2 vai vairāk apakšmezglos.
  • Kad apakšmezgls sadalās turpmākajos apakšmezglos, to sauc par lēmuma mezglu.
  • Mezglus, kas nesadalās, sauc par termināla mezglu vai lapu.
  • Noņemot lēmumu mezgla apakšmezglus, šo procesu sauc par atzarošanu. Atzarošanas pretstats ir sadalīšana.
  • Visa koka apakšnodaļu sauc par zaru.
  • Mezglu, kas ir sadalīts apakšmezglos, sauc par apakšmezglu vecāku mezglu; tā kā apakšmezglus sauc par vecāku mezglu bērnu.

Kā tas strādā

Šeit es runāju tikai par klasifikācijas koku, kas tiek izmantots, lai prognozētu kvalitatīvu reakciju. Kvantitatīvo vērtību prognozēšanai izmanto regresijas koku.

Klasifikācijas kokā mēs prognozējam, ka katrs novērojums pieder visbiežāk sastopamajai apmācību novērojumu klasei reģionā, kuram tas pieder. Interpretējot klasifikācijas koka rezultātus, mēs bieži esam ieinteresēti ne tikai klases prognozēšanā, kas atbilst noteiktam termināla mezgla reģionam, bet arī klases proporcijās starp apmācību novērojumiem, kas ietilpst šajā reģionā. Klasifikācijas koka audzēšanas uzdevums balstās uz vienu no šīm trim metodēm kā kritēriju bināro sadalījumu veidošanai:

1 - klasifikācijas kļūdu līmenis: “trāpījuma biežumu” var definēt kā treniņu novērojumu daļu noteiktā reģionā, kas nepieder pie visizplatītākās klases. Kļūdu rada šis vienādojums:

E = 1 - argmax_ {c} (π̂ mc)

kurā π̂ mc apzīmē apmācības datu daļu R_m reģionā, kas pieder c klasei.

2 - Džini indekss: Džini indekss ir alternatīva kļūdu metrika, kas paredzēta, lai parādītu, cik “tīrs” ir reģions. “Tīrība” šajā gadījumā nozīmē to, cik liela daļa apmācības datu konkrētajā reģionā pieder vienai klasei. Ja reģionā R_m ir dati, kas lielākoties ir no vienas c klases, tad Džini indeksa vērtība būs maza:

3 - Cross-Entropy: Trešā alternatīva, kas ir līdzīga Džini indeksam, ir pazīstama kā Cross-Entropy vai Deviance:

Krusteniskā entropija iegūst vērtību, kas ir tuvu nullei, ja visi π̂ mc ir tuvu 0 vai ir tuvu 1. Tāpēc, tāpat kā Džini indeksam, krusteniskā entropija iegūs nelielu vērtību, ja m-tais mezgls ir tīrs. Faktiski izrādās, ka Džini indekss un krusteniskā entropija skaitliski ir diezgan līdzīgi.

Veidojot klasifikācijas koku, konkrēta sadalījuma kvalitātes novērtēšanai parasti tiek izmantots Džini indekss vai krusteniskā entropija, jo tie ir jutīgāki pret mezglu tīrību nekā klasifikācijas kļūdu līmenis. Koka atzarošanā var izmantot jebkuru no šīm trim pieejām, taču klasifikācijas kļūdu līmenis ir vēlams, ja mērķis ir galīgā atzarojuma koka prognozēšanas precizitāte.

Īstenošana no nulles

Apmeklēsim lēmumu pieņemšanas koka veidošanas algoritmu ar visām tā smalkajām detaļām. Lai izveidotu lēmumu koku, mums ir jāpieņem sākotnējais lēmums par datu kopu, lai diktētu, kura funkcija tiek izmantota datu sadalīšanai. Lai to noteiktu, mums ir jāizmēģina visas funkcijas un jāmēra, kurš sadalījums dos mums vislabākos rezultātus. Pēc tam mēs sadalīsim datu kopu apakšgrupās. Pēc tam apakšgrupas šķērsos pirmā lēmuma mezgla filiāles. Ja dati par filiālēm ir viena un tā pati klase, tad mēs to esam pareizi klasificējuši un mums nav jāturpina to sadalīšana. Ja dati nav vienādi, tad mums ir jāatkārto sadalīšanas process šajā apakškopā. Lēmums par šīs apakškopas sadalīšanu tiek veikts tāpat kā sākotnējais datu kopums, un mēs atkārtojam šo procesu, līdz esam klasificējuši visus datus.

Kā mēs sadalām savu datu kopu? Viens veids, kā organizēt šo nekārtību, ir informācijas izmērīšana. Izmantojot informācijas teoriju, mēs varam izmērīt informāciju pirms un pēc dalīšanas. Informācijas izmaiņas pirms un pēc sadalīšanas ir zināmas kā informācijas ieguvums. Kad mēs zinām, kā aprēķināt informācijas ieguvumu, mēs varam sadalīt savus datus pa visām funkcijām, lai redzētu, kurš sadalījums dod mums visaugstāko informācijas ieguvumu. Sadalījums ar visaugstāko informācijas ieguvumu ir mūsu labākais risinājums.

Lai aprēķinātu informācijas ieguvumu, mēs varam izmantot Šenona entropiju, kas ir visas informācijas paredzamā vērtība par visām mūsu klases iespējamām vērtībām. Apskatīsim tā Python kodu:

Kā redzat, vispirms mēs aprēķinām gadījumu skaitu datu kopā. Tad mēs izveidojam vārdnīcu, kuras atslēgas ir vērtības pēdējā kolonnā. Ja atslēga iepriekš nav bijusi, tā tiek izveidota. Katrai atslēgai mēs sekojam, cik reizes šī etiķete parādās. Visbeidzot, mēs izmantojam visu dažādo etiķešu biežumu, lai aprēķinātu šīs etiķetes varbūtību. Šī varbūtība tiek izmantota, lai aprēķinātu Šenonas entropiju, un mēs to summējam visām etiķetēm.

Pēc tam, kad esam izdomājuši veidu, kā izmērīt datu kopas entropiju, mums ir nepieciešams sadalīt datu kopu, izmērīt entropiju dalītajās kopās un redzēt, vai tā sadalīšana bija pareizā rīcība. Šis ir kods, kas to var izdarīt:

Šim kodam ir trīs ievades dati: sadalāmie dati, sadalāmā funkcija un atgrieztās funkcijas vērtība. Katru reizi sākumā izveidojam jaunu sarakstu, jo mēs šai funkcijai vairākas reizes piezvanīsim uz vienu un to pašu datu kopu, un mēs nevēlamies, lai sākotnējā datu kopa tiktu modificēta. Mūsu datu kopa ir sarakstu saraksts; iterējot katru saraksta vienību un ja tajā ir meklētā vērtība, mēs to pievienosim jaunizveidotajam sarakstam. If paziņojuma iekšpusē mēs izgriezām funkciju, kuru mēs sadalījām.

Tagad mēs apvienosim 2 funkcijas: ShannonEntropy un splitDataset, lai pārvietotos pa datu kopu un izlemtu, kuru funkciju vislabāk sadalīt.

Ātri pārbaudīsim kodu:

  • Mēs aprēķinām visas datu kopas Šenonas entropiju pirms jebkādas sadalīšanas un piešķiram vērtību mainīgajai baseEntropy.
  • Pirmais - cilpu cilpām, kas attiecas uz visām mūsu datu funkcijām. Mēs izmantojam saraksta izpratni, lai izveidotu visu datu i-to ierakstu vai visu iespējamo vērtību, kas atrodas datos, sarakstu (featList).
  • Pēc tam mēs izveidojam jaunu kopu no saraksta, lai iegūtu unikālās vērtības (uniqueVals).
  • Pēc tam mēs izpētīsim visas šīs funkcijas unikālās vērtības un sadalīsim datus par katru funkciju (subData). Jaunā entropija tiek aprēķināta (newEntropy) un tiek summēta visām šīs funkcijas unikālajām vērtībām. Informācijas ieguvums (infoGain) ir entropijas samazinājums (baseEntropy - newEntropy).
  • Visbeidzot, mēs salīdzinām informācijas ieguvumu starp visām funkcijām un atgriežam labākās funkcijas indeksu, kuru sadalīt (bestFeature).

Tagad, kad mēs varam izmērīt, cik organizēta ir datu kopa un mēs varam sadalīt datus, ir pienācis laiks to visu salikt un izveidot lēmumu koku. No datu kopas mēs to sadalījām, pamatojoties uz labāko sadalāmo atribūtu. Pēc sadalīšanas dati pārvietojas pa koka zariem uz citu mezglu. Pēc tam šis mezgls atkal sadalīs datus. Lai to apstrādātu, mēs izmantosim rekursiju.

Mēs apstāsimies tikai šādos apstākļos: (1) beidzas atribūti, kurus sadalīt, vai (2) visi filiāles gadījumi ir viena un tā pati klase. Ja visiem gadījumiem ir viena klase, mēs izveidosim lapas mezglu. Visi dati, kas sasniedz šo lapu mezglu, tiek uzskatīti par piederīgiem šīs lapas mezglam.

Šis ir kods mūsu lēmumu koku veidošanai:

Mūsu kods satur 2 ievadus: datus un etiķešu sarakstu:

  • Vispirms mēs izveidojam visu klases etiķešu sarakstu datu kopā un izsaucam šo classList. Pirmais apstāšanās nosacījums ir tāds, ka, ja visas klases etiķetes ir vienādas, tad mēs šo etiķeti atdodam. Otrais apstāšanās nosacījums ir gadījums, kad vairs nav sadalāmo funkciju. Ja mēs neatbilstam apstāšanās nosacījumiem, tad, lai izvēlētos labāko funkciju, mēs izmantojam funkciju selectBestFeatureToSplit.
  • Lai izveidotu koku, mēs to uzglabāsim vārdnīcā (myTree). Tad mēs iegūstam visas unikālās vērtības no mūsu izvēlētās funkcijas (bestFeat) datu kopas. Unikālajā vērtības kodā tiek izmantotas kopas (uniqueVals).
  • Visbeidzot mēs atkārtojam visas mūsu izvēlētās funkcijas unikālās vērtības un rekursīvi izsaucam createTree () katram datu kopas sadalījumam. Šī vērtība tiek ievietota myTree vārdnīcā, tāpēc mēs iegūstam daudz ligzdotu vārdnīcu, kas attēlo mūsu koku.

Ieviešana caur Scikit-Learn

Tagad, kad mēs zinām, kā algoritmu ieviest no jauna, izmantosim “scikit-learning”. Jo īpaši mēs izmantosim ClassTreeClassifier klasi. Strādājot ar varavīksnenes datu kopu, vispirms datus importējam un sadalām apmācības un testa daļā. Tad mēs izveidojam modeli, izmantojot noklusējuma iestatījumu, lai pilnībā attīstītu koku (koku audzē, līdz visas lapas ir tīras). Mēs kokā fiksējam random_state, kas tiek izmantots iekšējā kaklasaites sadalīšanai:

Palaižot modeli, testa komplekta precizitātei vajadzētu sasniegt 95%, kas nozīmē, ka modelis pareizi paredzēja klasi 95% testa datu kopas paraugu.

Stiprās un vājās puses

Lēmumu koku izmantošanas galvenā priekšrocība ir tā, ka tos intuitīvi ir ļoti viegli izskaidrot. Tie precīzi atspoguļo cilvēku lēmumu pieņemšanu, salīdzinot ar citām regresijas un klasifikācijas metodēm. Tos var attēlot grafiski un ar tiem var viegli rīkoties, izmantojot kvalitatīvos prognozētājus, neradot fiktīvus mainīgos.

Vēl viena milzīga priekšrocība ir tāda, ka algoritmi ir pilnīgi nemainīgi datu mērogošanā. Tā kā katrs līdzeklis tiek apstrādāts atsevišķi un iespējamie datu sadalījumi nav atkarīgi no mērogošanas, lēmumu koka algoritmiem nav nepieciešama tāda pirmapstrāde kā funkciju normalizēšana vai standartizācija. Jo īpaši lēmumu pieņemšanas koki darbojas labi, ja mums ir funkcijas, kuru mērogs ir pilnīgi atšķirīgs, vai arī bināru un nepārtrauktu funkciju sajaukums.

Tomēr lēmumu pieņemšanas kokiem parasti nav tāda pati paredzamā precizitātes pakāpe kā citām pieejām, jo ​​tie nav diezgan robusti. Nelielas datu izmaiņas var izraisīt lielas izmaiņas galīgajā aprēķinātajā kokā. Pat izmantojot iepriekšēju atzarošanu, tie mēdz pārmērīgi izmantot un nodrošina sliktu vispārināšanas sniegumu. Tāpēc lielākajā daļā lietojumprogrammu, apvienojot daudzus lēmumu pieņemšanas kokus, izmantojot tādas metodes kā maisīšana, nejauši audzēti meži un uzlabojot, lēmumu koku paredzamo sniegumu var ievērojami uzlabot.

Atsauces avoti:

  • Ievads statistikas apguvē, ko veikuši Gareth James, Daniela Witten, Trevor Hastie un Robert Tibshirani (2014)
  • Pītera Harringtona mašīnmācība darbībā (2012)
  • Sāras Guido un Andreasa Mullera ievads mašīnu apguvē ar Python (2016)

- -

Ja jums patika šis skaņdarbs, es labprāt to darītu, ja jūs nospiestu aplaudēšanas pogu , lai citi varētu to paklupt. Manu kodu var atrast vietnē GitHub, kā arī vairāk par manu rakstu un projektiem vietnē https://jameskle.com/. Jūs varat arī sekot man Twitter, nosūtīt man pa e-pastu vai atrast mani LinkedIn.