1. Rule-Based Classifier 規則分類
2. Rule-Based Classifier 規則分類的排序
3. Rule-Based Classifier 規則分類的建立
4. Rule-Based Classifier 規則分類的連續覆蓋(Sequential Covering)
5. Rule-Based Classifier 規則分類的RIPPER(Direct Method: RIPPER)
1. Rule-Based Classifier 規則分類
規則分類法(Rule-Based Classifier)主要採用"If...Then"的方式對記錄做分類的動作。
一般的習慣寫法是:(條件)→ y ,意思是當資料的條件成立時,則屬於y
舉例來說:
(體溫=溫血)且(卵生=是)→ 鳥類
意思是當資料的屬性「體溫」是溫血,且是「卵生動物」,則歸類為鳥類
所以,一筆記錄X能夠符合規則R的條件的話,我們就稱作這條件R能覆蓋(Covers)紀錄X
接著就是規則在一個資料集裡頭的覆蓋率(Coverage)與正確率(Accuracy)。
以上面例子而言,我們設了一個規則「當狀況=單身,Class應該是 No」
即為 R:{Status = Sigle}→ No
其中條件是(狀況=單身),符合條件的10筆中有4筆,故覆蓋率為4/10,所以是40%。
而4筆當中,屬於 Class 是 No的,只有2個,故規則的正確率是 2/4 所以是50%。
既然了解了規則的大致上定義,那規則在資料集裡是怎麼運作的呢?
比方說我們今天有五條規則如下:
R1: (Give Birth = no) 且 (Can Fly = yes) → Birds
R2: (Give Birth = no) 且 (Live in Water = yes) → Fishes
R3: (Give Birth = yes) 且 (Blood Type = warm) → Mammals
R4: (Give Birth = no) 且 (Can Fly = no) → Reptiles
R5: (Live in Water = sometimes) → Amphibians
資料集:
所以記錄「Lemur」被R3覆蓋了,所以他的Class就是 Mammals
記錄「Turtle」被 R4 與 R5 覆蓋了,但他是?
記錄「Dogfish shark」沒有被任何條件覆蓋,所以他是?
這樣引申了兩個問題,(1)記錄被條件重複覆蓋。(2)記錄沒有被任何條件覆蓋。
所以,在Rule-Based Classifier有兩個特徵
(1)互斥(Mutually exclusive):
規則間應該是互斥的,所以每個記錄只被一個規則覆蓋。
(2)周延、窮盡(Exhaustive rules):
規則應當非常詳盡的去覆蓋所有記錄,因此所有每個記錄至少要被一個規則覆蓋。
所以,我們必須幫規則做先後的排序,也就是決定列表(Decision List),再來,當一筆資料進來後,該怎麼分類呢?
我們應該從順序高的規則開始,有符合就直接歸類,沒有符合就換到下一條規則。當都沒有符合任何條件時,則分類到「預設(Default)」的分類。
在回到上述資料集,Turtle應該被分在哪個類別勒?因為他先符合R4,故歸在 Reptiles。
2. Rule-Based Classifier 規則分類的排序
既然要規則要做排序,那該怎麼排序勒?排序的方式有兩種
(1)以規則為排序(Rule-based ordering):依照規則本身的品質排序,品質越好排序越高。
(2)以分類為排序(Class-based ordering):同一類別(Class)的規則會放在一起排序,在根據個資訊進行排序。
左邊,就是先依照相同左邊規則(Rule)排序。右邊則是依照相同右邊類別(Class)
3. Rule-Based Classifier 規則分類的建立
再來,我們要如何建立分類規則呢?建立的方式分成兩種
(1)直接(Direct Method):
直接從資料集中使用連續覆蓋(sequential covering)找尋規則並以貪婪(Greedy)方式成長,像是RIPPER,CN2
(2)間接(Indirect Method):從其他的分類方式(決策樹、類神經網路),像是C4.5Rules
直接法之「連續覆蓋(Sequential Covering)」成長步驟:
(1)先預設一個空的規則
(2)透過學習規則(Learn-One-Rule)長出一個規則
*學習規則是目的在於萃取分類規則,而這個分類規則可以包含很多正例,而且沒有(或是非常少)負例。
(3)刪除學習規則所包含的訓練記錄
(4)不斷重複(2)、(3)兩步驟,直到滿足條件
如下圖所示:
4. Rule-Based Classifier 規則分類直接方式的連續覆蓋(Direct Method: Sequential Covering)
接著連續覆蓋的簡介共有五個:
1.規則的生長(Rule Growing)
2.記錄的削減(Instance Elimination)
3.規則的評估(Rule Evaluation)
4.生長停止的標準(Stopping Criterion)
5.規則的修剪(Rule Pruning)
簡介1.規則的生長(Rule Growing)
規則的生長可以分成演繹法(general-to-specific)與歸納法(specific-to-general)兩種,這用圖比較好解釋。
而其中,演繹法是採用一個空集合,在慢慢改善選取目標。歸納法則是隨機挑選一個目標Class的資料作為基礎,在慢慢修正
補充:
CN2演算法的步驟是
1.先建立一個空的規則,r:{} → y
2.開始加入規則條件進入,挑選最小Entropy的條件
3.確定規則後,挑選能覆蓋最多目標Class的規則
PIPPER演算法的步驟是(之後會在詳細介紹)
1.同樣建立一個空的規則,r:{} → y
2.開始加入規則條件進入,挑選最大FOIL's Information Gain的。
R0: {} => class (initial rule)
R1: {A} => class (rule after adding conjunct)
Gain(R0, R1) = t [ log (p1/(p1+n1)) – log (p0/(p0 + n0)) ]
where t: number of positive instances covered by both R0 and R1
p0: number of positive instances covered by R0
n0: number of negative instances covered by R0
p1: number of positive instances covered by R1
n1: number of negative instances covered by R1
1.在做連續覆蓋時為什麼要把記錄給消除掉呢?
因為如果不刪除的話,下一個規則會重複覆蓋到。
2.為什麼要刪除目標Class(Positive)的記錄?
確保下一個規則是不同一個的。(還是跟上面理由差不多)
3.為什麼也要刪除不是目標Class(Negative)的記錄?
防止規則被低估了精確性。
如下圖所式:
上頭共有,29個 + 與 21個 -,我們選出了三個規則,
R1,初始正確率:12/15(80%)
R2,初始正確率:7/10(70%)
R3,初始正確率:8/12(66.7%)
很清楚看到R1是最好的策略,必須將R1所覆蓋的資料全部移除,進而繼續挑選下一個規則。
接著,R3因為R1資料的移除,故R3的正確率就變成了6/8(75%),高於R2,故我們選R3。
也就是說,如果我們不刪除R1的覆蓋的資料,R3就會重複覆蓋R1的也覆蓋的資料。另外如果不移除R1所覆蓋的+,我們可能會高估了R3的正確性,或者我們不移除R1覆蓋的-,也可能會低估了R3的正確性。
規則的評估,當然還是用計量的方式,總共有以下幾種
1.正確性(Accuracy):
2. Laplace法:
3. M-estimate法:
其中,
N 是規則能夠覆蓋多少記錄
Nc 是規則能夠覆蓋多少目標Class記錄
k 是總共有多少的組數
p 是事前機率(Prior probability)
簡介4與5.生長停止的標準(Stopping Criterion)與 規則的修剪(Rule Pruning)
停止生長的標準在於Gain值有沒有改善,如果沒有改善就停止
而規則的修剪,很像決策樹的減少錯誤修剪(回顧 Reduced Error Pruning),步驟很像
1.先移除一個規則中的條件
2.套入驗證資料計算移除前與移除後的比率
3.如果移除後有改善則移除,則修剪這個規則
5. Rule-Based Classifier 規則分類直接方式的 RIPPER(Direct Method: RIPPER)
RIPPER演算法,這也是一個在直接方式中常用的演算法,屬於演繹法(general-to-specific)的成長策略,也是基於連續覆蓋(Sequential Covering)且利用FOIL's Information Gain,來挑選最好的組合。
用在二元分類問題上:先選擇一個目標類別做為「正面(Positive)」,其他類別就是「負面(Negative)」,學習的規則就依照類別Positive的紀錄,Negative記錄就當做預設類別。
用在多元分類問題上:學習的規則開始於Class數量最少的開始,會有較好的精準度,其餘的為Negative。接著,最少的選擇完後,在找第二少的開始,依此類推。
RIPPER演算法 規則的成長:
1.開始於一個空的規則 R{} → y
2.開始加入條件,只要能夠改善 FOIL's Information Gain
3.停止條件在於條件開始覆蓋Negative的資料
4.接著立即將驗證案例導入做REP(Reduced Error Pruning)測試
5.以下面的公式來決定規則是否要進行修剪:V= (p-n) / (p+n)
p是規則能夠覆蓋多少個驗證資料集的Positive資料
n是規則能夠覆蓋多少個驗證資料集的Negative資料
6.如果有所改善,則刪除規則中最後一個加入的條件
比方說有一規則 R{A,B,C,D}→ y,則先考慮刪除D、再來是CD、再來BCD,依此類推