Induksi Decision Tree menggunakan konsep Entropy

 

Ross Quinlan
Ross Quinlan Pengembang algoritma ID3 pada akhir dekade 70-an¹, dalam upaya mewujudkan suatu sistem pakar yang mampu belajar dari kumpulan contoh. [CS 346 Spring 00]

Quinlan memperbaiki algoritma ID3 menjadi C4.5 pada tahun 1993, yang hari ini banyak digunakan. [CS 346 Spring 00]

Jauh hari sebelumnya, Hunt dan koleganya dari disiplin Pshychology menggunakan metode pencarian penuh pada decision tree untuk memodelkan belajar konsep pada manusia pada tahun 60-an. [CS 346 Spring 00]

ID3
Singkatan dari Iterative Dichotomiser 3², Induction of Decision "3" (Tree)³.

Mungkin merupakan algoritma Machine Learning yang paling banyak digunakan dalam literatur-literatur  science dan sistem software komersil. ID3 dikenal memiliki tahap belajar yang cepat; time complexity yang rendah dan ketelitian klasifikasi yang tinggi, termasuk untuk training examples yang memiliki noise. Versi original ID3 hanya menangani nilai-nilai attribute yang sedikit dan diskret, tetapi modifikasi selanjutnya mampu menangani nilai attribute yang ordered dan continuous.Variasi algoritma ID3 lainnya memiliki kemampuan untuk menangani noise.[Solheim96]

Termasuk kategori Concept Learning, yang tujuannya mendeskripsikan "Konsep umum apakah yang digunakan?" (Lihat Gambar)

Tujuan ID3: Mendapatkan decision tree yang terbaik. [CS 346 Spring 00]

ID3 merupakan Sistem belajar tersupervisi yang membentuk rule-rule untuk klasifikasi dalam bentuk sebuah decision tree. [Solheim96]

Decision tree adalah salah satu bentuk "Classification Models".⁴ [Ingargiola]

Masalahnya adalah upaya untuk mendapatkan decision tree terbaik (baca: minimal) yang konsisten dengan sekumpulan data yang telah disediakan termasuk dalam kategori algoritma NP-Hard (Completeness). [CS 346 Spring 00]

Konstruksi decision tree dilakukan secara top-down, diawali dengan pertanyaan: "Attribute mana yang harus diperiksa pada root dari decision tree?" [Mitchell97]

Decision tree dibentuk dengan mempartisi training examples. [Solheim96]

Kekuatan ID3 yang terutama adalah pada fungsi heuristik information gain untuk memilih attribute terbaik yang akan digunakan [Solheim96]

Konsep Entropy yang digunakan untuk mengukur "seberapa informatifnya" sebuah node (yang biasanya disebut seberapa baiknya), diperkenalkan oleh Claude Shannon dalam Information Theory. [Ingargiola]
ID3 adalah algoritma greedy, sehingga pemilihan yang keliru pada sebuah atribut akan memberikan efek pada hasil akhirnya. [Solheim96] Dalam hal ini algoritma tidak pernah melakukan backtracking untuk merevisi keputusan pemilihan attribute yang telah dilakukan sebelumnya. [Mitchell97]

Recursive Algorithm mewujudkan Greedy Heuristic Search: Hill-Climbing tanpa backtracking. [CS 346 Spring 00]

Tidak menjamin menghasilkan decision tree yang selalu --walaupun biasanya-- optimal. [CS 346 Spring 00]

Beberapa Terms
Examples (S), adalah training examples yang ditunjukkan oleh tabel di bawah ini:

Target attribute adalah PlayTennis yang memiliki value yes atau no, selama 14 minggu pada setiap Sabtu pagi. Attribute adalah Outlook, Temperature, Hunidity, dan Wind.

Algoritma

PROCEDURE ID3(Examples, TargetAttribute, Attributes)5

Examples are the training examples. Target-attribute is the attribute whose value is to be

predicted by the tree. Attributes is a list of other attributes that may be tested by the

learned decision tree. Returns a decision tree that correctly classifies the given Examples.

• Create a Root node for the tree
• If all Examples are positive, Return the single-node tree Root, with label = +
• If all Examples are negative, Return the single-node tree Root, with label = -
• If Attributes is empty, Return the single-node tree Root, with label = most common
  value of Target_attribute in Examples
• Otherwise Begin
  
  • A <--- the attribute from Attributes that best* classifies Examples
  • The decision attribute for Root <--- A
  • For each possible value, vi, of A,
  • Add a new tree branch below Root, corresponding to the test A = vi
  • Let Examplesvi be the subset of Examples that have value vi for A
  • If Examplesvi is empty
  • Then below this new branch add a leaf node with label = most common
  • value of Target_attribute in Examples
  • Else below this new branch add the subtree
  • Call ID3 (Examples, Target_attribute, Attributes - {A}))
• End
• Return Root

The best attribute is the one with highes information gain, as defined in Equation: 

S adalah koleksi dari 14 contoh dengan 9 contoh positif dan 5 contoh negatif, ditulis dengan

notasi [9+,5-]. Entropy dari S adalah:

 

Entropy([9+,5-]) = - (9/14)log2(9/14) - (5/14)log2(5/14)
                           = 0.94029
Catatan:

• Entropy(S)=0, jika semua contoh pada S berada dalam kelas yang sama.
• Entropy(S)=1, jika jumlah contoh positif dan jumlah contoh negatif dalam S adalah sama.
• 0<Entropy(S)<1, jika jumlah contoh positif dan negatif dalam S tidak sama.

Gain(S,A) adalah Information Gain dari sebuah attribute A pada koleksi contoh S.6

Values(Wind)          = Weak, Strong

SWeak                   = [6+,2-]

SStrong                 = [3+,3-]

Gain(S,Wind)        = Entropy(S) - (8/14)Entropy(SWeak) - (6/14)Entropy(SStrong)

     = 0.94029 - (8/14)0.81128 - (6/14)1.0000

     = 0.04813

Values(Humidity) = High, Normal

SHigh                     = [3+,4-]

SNormal                = [6+,1-]

Gain(S,Humidity) = Entropy(S) - (7/14)Entropy(SHigh) - (7/14)Entropy(SNormal)

   = 0.94029 - (7/14)0.98523 - (7/14)0.59167

   = 0.15184

Values(Temperature) = Hot, Mild, Cool

SHot                       = [2+,2-]

SMild                     = [4+,2-]

SCool                     = [3+,1-]

Gain(S,Temperature) = Entropy(S) - (4/14)Entropy(SHot) - (6/14)Entropy(SMild)- (4/14)Entropy(SCool)

= 0.94029 - (4/14)1.00000 - (6/14)0.91830 - (4/14)0.81128

= 0.02922

Values(Outlook) = Sunny, Overcast, Rain

SSunny                  = [2+,3-]

SOvercast              = [4+,0-]

SRain                     = [3+,2-]

Gain(S,Outlook) = Entropy(S) - (5/14)Entropy(SSunny) - (4/14)Entropy(SOvercast)
                             -(5/14)Entropy(SRain)

= 0.94029 - (5/14)0.97075 - (4/14)1.000000 - (5/14)0.97075

= 0.24675

Jadi, information gain untuk 4 atribut yang ada adalah:

Gain(S,Wind)                     = 0.04813

Gain(S,Humidity)                = 0.15184

Gain(S,Temperature)          = 0.02922

Gain(S,Outlook)                = 0.24675

Dari perhitungan tersebut, tampak bahwa attribute Outlook akan menyediakan prediksi terbaik

untuk target attribute PlayTennis.

 Untuk branch node Outlook=Sunny,
SSunny = [D1, D2, D8, D9, D11]

 

Values(Temperature) = Hot, Mild, Cool

SHot                        = [0+,2-]

SMild                       = [1+,1-]

SCool                      = [1+,0-]

Gain(SSunny, Temperature) = Entropy(SSunny) - (2/5)Entropy(SHot) - (2/5)Entropy(SMild)

- (1/5)Entropy(SCold)

                               = 0.97075 - (2/5)0.00000 - (2/5)1.00000 - (1/5)0.00000

                               = 0.57075

Values(Humidity) = High, Normal

SHigh                  = [0+,3-]

SNormal             = [2+,0-]

Gain(SSunny, Humidity) = Entropy(SSunny) - (3/5)Entropy(SHigh) - (2/5)Entropy(SNormal)

                         = 0.97075 - (3/5)0.00000 - (2/5)1.00000

                         = 0.97075

Values(Wind) = Weak, Strong

SWeak          = [1+,2-]

SStrong         = [1+,1-]

Gain(SSunny, Wind) = Entropy(SSunny) - (3/5)Entropy(SWeak) - (2/5)Entropy(SStrong)

= 0.97075 - (3/5)0.91830 - (2/5)1.00000

= 0.01997

 Untuk branch node Outlook=Rain,
SRain = [D4, D5, D6, D10, D14]

 

Values(Temperature) = Mild, Cool {Tidak ada lagi temperature=hot saat ini}

SMild                       = [2+,1-]

SCool                       = [1+,1-]

Gain(SRain, Temperature) = Entropy(SRain) - (3/5)Entropy(SMild) - (2/5)Entropy(SCold)

                = 0.97075 - (3/5)0.91830 - (2/5)1.00000

                = 0.01997

Values(Humidity) = High, Normal

SHigh                  = [1+,1-]

SNormal              = [2+,1-]

Gain(SRain, Humidity) = Entropy(SRain) - (2/5)Entropy(SHigh) - (3/5)Entropy(SNormal)

           = 0.97075 - (2/5)1.00000 - (3/5)0.91830

           = 0.01997

 Values(Wind) = Weak, Strong

SWeak           = [3+,0-]

SStrong           = [0+,2-]

Gain(SRain, Wind) = Entropy(SRain) - (3/5)Entropy(SWeak) - (2/5)Entropy(SStrong)

= 0.97075 - (3/5)0.00000 - (2/5)0.00000

= 0.97075

 

Rule-Rule yang telah Dipelajari, dengan memperhatikan decision tree yang dihasilkan
adalah:

• IF Outlook = Sunny AND Humidity = High THEN PlayTennis = No
• IF Outlook = Sunny AND Humidity = Normal THEN PlayTennis = Yes
• IF Outlook = Overcast THEN PlayTennis = Yes
• IF Outlook = Rain AND Wind = Strong THEN PlayTennis = No
• IF Outlook = Rain AND Wind = Weak THEN PlayTennis = Yes

Sumber dari: Diktat Kuliah Data Mining - Magister Teknologi Informasi STTS Semester Genap 2007/2008 - Maret 2008 Sub Materi: ID3: Induksi Decision Tree

Semoga materi ini bermanfaat bagi teman-teman, keberkahan bagi pembuat materi, instansi, dan yang menyebarluarkannya. Amin

Endro A

 ---------------------

1 Machine Learning Course Notes ELEG 867 - Decision Trees. Menyebutkan Quinlan

mengembangkan ID3 pada tahun 1986.

2 Knowledge Acquisition for Expert Systems, Anna Hart, Kogan Page, 1989, p. 125.

3 Helge Grenager Solheim, http://www.pvv.unit.no/~hgs/project/report/node36.html, 4 Mei 1996. 

4 Building Classification Models: ID3 and C4.5, Ingargiola, http://www.cis.temple.edu/~ingargio/cis587/readings/id3-c45.html.  

5 Machine Learning, Tom M. Mitchell, The McGraw-Hill Companies, Inc., International Edition,

1997, p. 56.