ID3
ID3(粵拼:aai1 di1 saam1;取自英文全名 Iterative Dichotomiser 3,呢個全名係疊代二分器 3 噉解)係機械學習上一種用嚟建構決策樹嘅演算法。虛擬碼如下[1][2]:
計吓成個數據庫嘅 information entropy(資訊熵;簡單啲講就係指柞數據有幾接近完全隨機)
For 每一個用嚟做預測嘅變數
計吓用咗佢分類之後嘅總 entropy
計吓用咗佢分類之後嘅總 entropy 同成個數據庫嘅 entropy 差幾多(information gain)
揀 information gain 最高嗰個變數嚟分類
For 每一個分咗嘅類,用嗰個類內嘅個案做數據庫,做多次上述嘅過程,直至用嗮所有用嚟做預測嘅變數,或者到咗指定嘅分枝數上限為止。
基本概念
編輯舉個實際應用例子,想像依家要將手上嘅病人分類,數據庫入面有一個個病人個案,每個個案(1 2 3 4...)都記錄咗嗰位病人「有冇發燒」、「有冇見咳」同埋「係咪真係中咗新型流感」... 等嘅資訊。研究者跟住就叫部電腦用 ID3 建立決策樹,用嚟將啲病人分類,部電腦會[3]
- 將啲可以用嚟分類嘅變數—「有冇發燒」、「有冇見咳」—逐個逐個攞嚟睇,睇吓邊個最能夠(例如)令資訊熵下降;
- 例如家陣發覺「有冇發燒」係最能夠令資訊熵下降嘅,將班病人按「有冇發燒」嚟分做兩大組;
- 同每一個子節點,搵下一個可以用嚟分類嘅變數;
- 一路係噉做上述嘅過程,直至(例如)可以用嚟分類嘅變數用晒為止。
最後得出嘅決策樹,就會容許研究者作出類似噉嘅決策過程:「首先,睇吓一位病人有冇發燒;如果有發燒,就睇吓位病人有冇咳,如果有...(省略);而如果冇發燒,就睇吓位病人唞氣有冇困難,如果有...(省略)」而有咗呢一樖決策樹,研究者就可以例如教 AI 做睇病嘅工作[4]。
相關嘅文
編輯參考資料
編輯- ↑ Chapter 4: Decision Trees Algorithms.
- ↑ Decision Trees: ID3 Algorithm Explained. Towards Data Science.
- ↑ Decision Trees: ID3 Algorithm Explained. Towards Data Science.
- ↑ Azar, A. T., & El-Metwally, S. M. (2013). Decision tree classifiers for automated medical diagnosis. Neural Computing and Applications, 23, 2387-2403.