Qərar ağacları: qərar vermə müddətimi necə optimallaşdırıram?

İyirmi sual oyunu oynadığınızı təsəvvür edək. Rəqibiniz gizli şəkildə bir mövzu seçdi və nə seçdiyini öyrənməlisiniz. Hər bir hərəkətdə "hə-ya-yox" sualını verə bilərsiniz və rəqibiniz dürüst cavab verməlidir. Ən az sualda sirri necə öyrənirsiniz?

Bəzi sualların digərlərindən daha yaxşı olduğu açıq olmalıdır. Məsələn, “uça bilərmi?” Sualı, ilk sualınızın steril olma ehtimalı olduğu üçün, “canlıdır?” Sualıdır. Bir şey daha faydalıdır. İntuitiv olaraq, hər bir sualın mümkün sirlərin aralığını əhəmiyyətli dərəcədə daraltmasını və nəticədə cavabınıza səbəb olmasını istəyirsən.

Qərar ağaclarının arxasındakı əsas fikir budur. Hər nöqtədə, məlumat dəstinizi sıradan çıxara biləcək bir sıra suallara baxırsınız. Ən yaxşı bölməni təklif edən sualı seçib bölmələr üçün ən yaxşı sualları yenidən axtarırsınız. Düşündüyünüz bütün əşyalar eyni sinifdə olan kimi çıxın. Sonra təsnifat vəzifəsi asandır. Yalnız bir nöqtəni tutub ağacın üstünə atmaq olar. Suallar onu uyğun sinifinə yönəldir.

vacib şərtlər

Qərar ağacı, həm reqressiya, həm də təsnifat problemləri ilə istifadə edilə bilən, nəzarət olunan bir öyrənmə alqoritmi növüdür. Həm kategorik, həm də davamlı giriş və çıxış dəyişənləri üçün işləyir.

Yuxarıdakı şəkildən istifadə edərək qərar ağacında əsas terminologiyanı müəyyənləşdirək:

  • Kök node bütün populyasiyanı və ya nümunəni təmsil edir. Bundan əlavə 2 və ya daha çox homojen dəstə bölünür.
  • Bölmə, bir düyünün iki və ya daha çox alt qovluğa bölünməsidir.
  • Bir alt qovluq digər alt qovşaqlara bölünürsə, buna qərar düyünü deyilir.
  • Bölünməmiş qovşaqlara terminal qovşaqları və ya yarpaqlar deyilir.
  • Bir qərar qovşağının alt qovluqlarını çıxardığınızda bu proses təmizlənmə olaraq bilinir. Budamağın əksi parçalanmaqdır.
  • Bütün bir ağacın alt hissəsinə budaq deyilir.
  • Alt qovşaqlara bölünən bir qovşağa alt qovşaqların ana adı deyilir. halbuki alt qovşaqlar ana düyünün uşağı adlanır.

Bu necə işləyir

Yalnız keyfiyyət cavabını proqnozlaşdırmaq üçün istifadə olunan təsnifat ağacından bəhs edirəm. Reqressiya ağacı kəmiyyət dəyərlərini proqnozlaşdırmaq üçün istifadə olunur.

Bir təsnifat ağacında, hər bir müşahidənin aid olduğu bölgədəki ən çox görülən təlim müşahidələri sinfinə aid olduğunu təxmin edirik. Bir təsnifat ağacının nəticələrini şərh edərkən, tez-tez yalnız müəyyən bir terminal düyün bölgəsinə uyğun gələn sinif proqnozu ilə deyil, həm də bu bölgəyə düşən təlim müşahidələri arasındakı sinif nisbətləri ilə maraqlanırıq. Təsnifat ağacının yaradılması vəzifəsi ikili bölmələrin yaradılması meyarı kimi bu üç metoddan birini istifadə etməyə əsaslanır:

1 - Təsnifat Xətası Oranı: "vuruş dərəcəsini" müəyyən bir bölgədəki təlim müşahidələrinin ən çox yayılmış sinfə aid olmayan hissəsi kimi təyin edə bilərik. Səhv aşağıdakı tənlikdən yaranır:

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

burada π̂ mc, R_m bölgəsindəki təlim məlumatlarının c sinifinə aid olan hissəsini təmsil edir.

2 - Gini indeksi: Gini indeksi bölgənin nə qədər “təmiz” olduğunu göstərən alternativ bir səhv ölçüsüdür. Bu vəziyyətdə "saflıq" müəyyən bir bölgədəki təlim məlumatlarının nə qədərinin tək bir sinifə aid olduğunu göstərir. R_m aralığında əsasən bir c sinifindən olan məlumatlar varsa, Gini indeksi kiçikdir:

3 - Çapraz Entropiya: Cini indeksinə bənzər üçüncü bir alternativ Çapraz Entropiya və ya Sapma kimi tanınır:

Eninə entropiya, π̂ mc hamısı 0-a və ya 1-ə yaxın olduqda sıfıra yaxın bir dəyər alır. Buna görə də, Gini indeksi kimi, eninə entropiya da m-düyün təmiz olduqda kiçik bir dəyər alır. Əslində, Gini indeksi və çapraz entropiyanın say baxımından olduqca oxşar olduğu ortaya çıxdı.

Tipik olaraq, bir təsnifat ağacı qurarkən, müəyyən bir bölmənin keyfiyyətini qiymətləndirmək üçün ya Gini indeksi ya da çarpaz entropiya istifadə olunur, çünki təsnifat səhv nisbətindən daha çox düyün təmizliyinə həssasdırlar. Bu üç yanaşmadan hər hansı biri ağacın budanmasında istifadə edilə bilər, lakin son budanmış ağacın proqnozlaşdırılan dəqiqliyi hədəf olduğu zaman təsnifat səhv dərəcəsi üstünlük təşkil edir.

Sıfırdan tətbiqetmə

Qərar ağacı qurma alqoritmini bütün incə detallarında nəzərdən keçirək. Bir qərar ağacını yaratmaq üçün əvvəlcə məlumatları bölmək üçün hansı funksiyanı istifadə edəcəyimizi müəyyənləşdirmək üçün verilənlər bazasında qərar verməliyik. Bunu müəyyən etmək üçün hər bir xüsusiyyəti sınamalı və parçalanmanın ən yaxşı nəticəni verdiyi yeri ölçməliyik. Sonra məlumat dəstini alt qruplara böldük. Alt hissələr daha sonra ilk qərar qovşağının budaqlarından keçir. Filiallardakı məlumatlar eyni sinifdədirsə, biz onları düzgün şəkildə təsnif etdik və daha da bölüşdürməyə ehtiyac yoxdur. Tarixlər eyni deyilsə, həmin alt üçün bölmə əməliyyatını təkrarlamalıyıq. Bu alt hissəni necə bölmək barədə qərar orijinal məlumat dəsti ilə eyni şəkildə qəbul edilir. Bu proses bütün məlumatlar təsnif edilənə qədər təkrarlanır.

Datasımızı necə bölürük? Bu qarışıqlığı təşkil etməyin bir yolu da məlumatı ölçməkdir. İnformasiya nəzəriyyəsindən istifadə edərək, məlumat bölünmədən əvvəl və sonra ölçə bilərik. Bölünmədən əvvəl və sonra məlumat dəyişikliyinə məlumat qazancı deyilir. Məlumat qazancının necə hesablandığını bilsək, məlumatlarınızı hər xüsusiyyətə bölə bilərik ki, hansı qəzanın ən yüksək məlumat qazandığını görək. Ən yüksək məlumat qazanma bölgüsü ən yaxşı seçimdir.

Məlumat qazancını hesablamaq üçün sinifimizdəki bütün mümkün dəyərlərin bütün məlumatlarının gözlənilən dəyəri olan Shannon entropiyasından istifadə edə bilərik. Bunun üçün Python koduna baxaq:

Gördüyünüz kimi əvvəlcə verilənlər dəstindəki nümunələrin sayını hesablayırıq. Sonra açarları son sütundakı dəyərlər olan bir lüğət yaradırıq. Əvvəllər heç bir açar tapılmadıqda, bir açar yaradılacaqdır. Bu etiketin hər düymə üçün nə qədər baş verdiyini qeyd edirik. Nəhayət, bu etiketin ehtimalını hesablamaq üçün bütün fərqli etiketlərin tezliyini istifadə edirik. Bu ehtimal Shannon entropisini hesablamaq üçün istifadə olunur və bunu bütün etiketlər üçün ümumiləşdiririk.

Veri dəstinin entropiyasını necə ölçəcəyimizi düşündükdən sonra, verilənlər dəstini bölməli, bölmə dəstlərindəki entropiyanı ölçməli və bölünmənin doğru bir şey olub olmadığını görməliyik. Bunun kodu:

Bu kod 3 giriş tələb edir: verilənlərin bölünməsi, bölünmə xüsusiyyətinin və qayıtma xüsusiyyətinin dəyəri. Hər dəfə başlamaq üçün yeni bir siyahı hazırlayırıq, çünki eyni qeyd üçün bu funksiyanı dəfələrlə çağırırıq və orijinal qeydin dəyişdirilməsini istəmirik. Məlumat dəstimiz siyahıların siyahısıdır; Siyahıdakı hər bir maddəni təkrarladığımızda və axtardığımız dəyəri özündə cəmləşdirdiyimizdə, onu yeni yaradılan siyahımıza əlavə edəcəyik. İf ifadəsində bölüşdürdüyümüz xüsusiyyəti kəsdik.

İndi iki funksiyanı birləşdirəcəyik: ShannonEntropy və splitDataset verilənlər bazasını gəzmək və hansı funksiyaya daha yaxşı bölünməsinə qərar vermək üçün.

Kodu tez nəzərdən keçirək:

  • Bütün məlumat dəstinin Shannon entropisini bölüşdürmədən əvvəl hesablayırıq və baseEntropy dəyişəninə dəyər veririk.
  • Döngü üçün ilk məlumatlarımızdakı bütün funksiyalardan keçir. Veridəki bütün girişlərin siyahısını (featList) və ya məlumatdakı bütün mümkün dəyərləri tərtib etmək üçün siyahı anlama istifadə edirik.
  • Sonra benzersizValları təyin etmək üçün siyahıdan yeni bir dəst yaradırıq.
  • Sonra həmin xüsusiyyətin bütün unikal dəyərlərini nəzərdən keçiririk və hər xüsusiyyət (alt məlumat) üçün məlumatları bölürük. Yeni entropiya (newEntropy) hesablanır və bu xüsusiyyətin bütün unikal dəyərləri üçün cəmlənir. Məlumat qazancı (infoGain) entropiyanın azalmasıdır (baseEntropy - newEntropy).
  • Nəhayət, məlumat qazancını bütün xüsusiyyətlər arasında müqayisə edirik və bölünəcək ən yaxşı xüsusiyyət indeksini qaytarırıq (bestFeature).

İndi bir məlumat dəstinin nə dərəcədə mütəşəkkil olduğunu ölçə bildiyimiz və məlumatları parçalaya bildiyimiz üçün bütün bunları bir araya gətirmək və qərar ağacını yaratmaq vaxtı gəldi. Bir verilənlər bazasından bölmək üçün ən yaxşı atributa əsasən bölünürük. Bölündükdən sonra məlumatlar ağacın budaqlarını başqa bir düyünə keçir. Bu qovşaq daha sonra məlumatları yenidən bölür. Bunun üçün rekursiyadan istifadə edəcəyik.

Yalnız aşağıdakı şərtlər altında dayanacağıq: (1) bölüşmək üçün artıq kifayət qədər xüsusiyyət yoxdur və ya (2) filialdakı bütün nümunələr eyni sinifdir. Bütün nümunələr eyni sinifdə olduqda, bir yarpaq nodu yaradırıq. Bu yarpaq düyününə çatan bütün məlumatlar bu yarpaq nodunun sinfinə aiddir.

Qərar ağaclarımızı yaratmaq üçün kod:

Kodumuza 2 giriş tələb olunur: tarixlər və etiket siyahısı:

  • Əvvəlcə verilənlər bazasındakı bütün sinif etiketlərinin siyahısını yaradırıq və bu sinif siyahısını çağırırıq. İlk dayanma şərti, bütün etiketlər eyni olduqda bu etiketi qaytarmaqdır. İkinci dayanma şərti, bölünməyə daha çox xüsusiyyət olmadıqda. Dayanma şərtlərinə cavab vermiriksə, ən yaxşısını seçmək üçün selectBestFeatureToSplit funksiyasından istifadə edirik.
  • Ağac yaratmaq üçün onu lüğətdə saxlayırıq (myTree). Sonra seçilmiş xüsusiyyət (bestFeat) üçün məlumat dəstindən bütün unikal dəyərləri alırıq. Unikal dəyər kodu miqdarlardan (uniqueVals) istifadə edir.
  • Nəhayət, seçdiyimiz funksiyanın bütün unikal dəyərlərini nəzərdən keçiririk və verilənlər bazasının hər bölməsi üçün rekursiv olaraq CreateTree () çağırırıq. Bu dəyər myTree lüğətinə qoyulur ki, ağacımızı təşkil edən çox sayda içəri lüğət var.

Scikit-Learn vasitəsilə tətbiqetmə

Alqoritmi sıfırdan necə tətbiq edəcəyimizi bildiyimiz üçün scikit-learn istifadə edə bilərsiniz. Xüsusilə, DecisionTreeClassifier sinifindən istifadə edirik. Iris məlumat dəsti ilə işləyirik, əvvəlcə məlumatları idxal edirik və təlim hissəsinə və test hissəsinə bölürük. Sonra ağacı tam inkişaf etdirmək üçün standart parametr ilə bir model qururuq (ağac bütün yarpaqlar təmizlənənə qədər böyüyür). Bağdakı qırılma üçün daxili olaraq istifadə olunan ağacdakı random_state vəziyyətini düzəldirik:

Modelin işlədilməsi test dəstinin 95% dəqiqliyini verməlidir, yəni model test dəstindəki nümunələrin 95% -i üçün sinfi düzgün proqnozlaşdırmışdır.

Güclü və zəif tərəflər

Qərar ağaclarını istifadə etməyin əsas üstünlüyü, onları intuitiv izah etmək çox asandır. Digər regresiya və təsnifat yanaşmalarına nisbətən insan seçimlərini dəqiq şəkildə əks etdirirlər. Bunlar qrafik olaraq göstərilə bilər və keyfiyyətli proqnozlaşdırıcılar, saxta dəyişənlər yaratmağa ehtiyac olmadan asanlıqla idarə edilə bilər.

Başqa bir böyük üstünlük, məlumatların miqyası üçün alqoritmlərin tamamilə dəyişməz olmasıdır. Hər bir xüsusiyyət ayrıca işləndiyindən və məlumatların mümkün bölgüsü miqyaslandırmadan asılı olmadığından, qərar ağacı alqoritmləri üçün xüsusiyyətlərin normallaşdırılması və ya standartlaşdırılması kimi əvvəlcədən işləmə tələb olunmur. Xüsusən qərar ağacları, xüsusiyyətlər tamamilə fərqli tərəzidə olduqda və ya ikili və davamlı xüsusiyyətlərin qarışığı olduqda yaxşı işləyir.

Ancaq qərar ağacları ümumiyyətlə digər yanaşmalarla eyni dəqiqlik səviyyəsinə malik deyillər, çünki çox möhkəm deyillər. Verilərdəki kiçik bir dəyişiklik, son təxmin edilən ağacda böyük bir dəyişiklik ilə nəticələnə bilər. Əvvəlcədən budamadan istifadə etdikdə belə, həddən artıq uyğunlaşma və zəif ümumiləşdirmə performansına meyllidirlər. Buna görə də, əksər tətbiqetmələrdə qərar ağaclarının proqnozlaşdırıcı performansı sallanma, təsadüfi meşələr və gücləndirmə kimi metodlardan istifadə edərək bir çox qərar ağacını toplayaraq əhəmiyyətli dərəcədə yaxşılaşdırıla bilər.

İstinad mənbələri:

  • Gareth James, Daniela Witten, Trevor Hastie və Robert Tibshirani tərəfindən Statistik Öyrənməyə giriş (2014)
  • Fəaliyyətdə Maşın Öyrənmə Peter Harrington (2012)
  • Sarah Guido və Andreas Müller tərəfindən Python ilə maşın öyrənilməsinə giriş (2016)

- -

Bu parçanı bəyəndinsə, başqalarının üstündən keçə bilməsi üçün əl çalma düyməsini bassan çox istərdim. GitHub-da öz kodumu və daha çox məqalə və layihəni https://jameskle.com/ saytında tapa bilərsiniz. Siz də Twitter-də məni izləyə, birbaşa e-poçt göndərə və ya LinkedIn-də tapa bilərsiniz.