授課教授：交通大學 交通運輸研究所 陳穆臻 教授
參考書籍：Introduction to Data Mining, Tan, P. T., Steinbach, M., Kumar,. Vipin
１. Rule-Based Classifier 規則分類的間接方法（Indirect Method）
２. Rule-Based Classifier 規則分類的優點（Advantages）
３. Instance-Based Classifiers 案例式分類（Instance Based Classifiers）
４. Instance-Based Classifiers 案例式分類 第k個最鄰近法（k-Nearest-Neighbor）
５. 課後作業
１. Rule-Based Classifier 規則分類的間接方法（Indirect Method）
上都提過，規則分類有直接與間接兩種方法，本周上課換介紹間接的方法（Indirect Method）。
所謂的間接方法，就不是直接拿資料去跑出規則集，而是換其他方式來生出規則集，比方說決策樹（Decision Tree）、類神經網路（Neural networks）
如下圖，就是由Decision Tree 轉 Rule-Based
像C4.5Rules就是一種間接的方法，先利用C4.5建立出完整未修剪的決策樹，在利用規則分類的修剪方式進行修剪動作。
而C4.5Rules規則產生的步驟如下：
1.假設每個規則都是 r: A → y
2.經過條件篩檢後的規則為，r':A'→ y
3.比較修剪前後的悲觀估計（回顧）
4.如果有比較低的悲觀估計誤差的話，則修剪掉
5.重複上述步驟，直到不再改善悲觀估計誤差。
而C4.5Rules的規則生成後，再來就要考慮規則的排序了。主要以規則為排序（Rule-based ordering）的方式（回顧），相同分類的規則會放在同一個規則子集合中，在分別計算每個子集合的總描述長度（Description length），以遞增方式做排序。
規則總長度的計算方式如下：
其中，L（exception）是指錯誤分類的資料（Misclassified example）所需的編碼長度；g是一個調整參數（Tuning parameter），一般預設是0.5；而 L（model）整個模型的編碼長度。
２. Rule-Based Classifier 規則分類的優點（Advantages）
所以綜合上面所有有關規則分類的介紹，我們也可以做個小總結，對其優點列表
１.規則分類與決策樹有差不多水準的高表現性
２.很容易詮釋與解釋
３.很容易的去產生
４.可以用來作預測新案例或記錄
５.效率可以媲美決策樹
３. Instance-Based Classifiers 案例式分類（Instance Based Classifiers）
案例式分類，就是採用案例的資料集做分類的意思。當今天有一個新的Record進來，接著比較他跟案例資料集中哪個案例相同，就將其分類在相同案例的一類。
今天這個新案例進來，因為他的屬性與鴨子的相似度最高，故我們就將他分類到鴨子。
案例式分類，是一種懶惰的學習方式，他總是等到資料進來後才會開始進行分析的動作，之前我們所學的規則分類或是決策樹分類，都是積極型的學習方式，在資料進來之前，就已經進行所謂的建模。因此，懶惰學習方式起初並不會花費太多的時間，只有等到資料進入時才會開始動作，所以當資料有相當多比的時候，就會花費相當多的時間了。
４. Instance-Based Classifiers 案例式分類 第k個最鄰近法（k-Nearest-Neighbor）
最近鄰居法，是指在資料集裡頭與新資料最相近的那筆資料，而第k個最鄰近法是指，在資料集裡頭與新資料最接近的k筆資料。
這是一個k＝3的最鄰近法，而鄰不鄰近最主要就是看與距離啦，距離越近就越鄰近。
一般可採用歐式距離：
而新案例的分類，就是看最鄰近的幾個點是什麼分類，通常以多數為決定。故上述案例就是3個＋，沒有－，所以分類為＋。
而上面這張圖，分別為K=1鄰近、K=2鄰近、K＝3鄰近，但未知的X要怎麼分類呢？K＝1的時候很明顯是「－」，K＝3是「+」，但K＝2的時候通常會採用隨機方式來決定。
再來，上圖中，未知案例X明明離"－"比較近，就算你有兩個"＋"，還是會讓人產生疑慮，因此除了多數決定的方法外，還有對距離下權重的方式。通常來說權重會是
但是，當我們的案例庫如果太多雜訊的時候，K太小時分類的決定就容易受到雜訊影響。可是K太大時，又容易包含太多雜點產生誤判問題（如下圖）
接著我們討論關於K-NN最鄰近法的屬性縮放問題，因為有些屬性資料差距相當大，會導致原本相近的案例，因為一個不起眼的屬性而造成相當大的差異。
比方說：
身高的差異大致上是，140～185公分
體重的差異就有可能是，45公斤～120公斤
換到收入來說，就會變成，1萬元～100萬元的差異
因此，正規化屬性值，也是K-NN最鄰近法一個相當重要的前處理步驟。
R：B → ＋ （覆蓋了30的Positive以及10個Negative）試問
1.正確率＝30/40＝0.75
2.FOIL's 資訊獲得量：30*［Log（30/(30+10),2）－ Log（(100/100+400),2）］=57.207
3.Likelihood ratio：2*［30*Log（30/(100*40/500) ,2）＋10*Log（10/(400*40/500) ,2］= 80.85
4.Laplace measure： （30+1）/（40+2）＝31/42
5.M-estimate（K=2, P+=0.2）：（30+(2*0.2)）/（40+2）＝0.7619
3.比較修剪前後的悲觀估計（回顧）
4.如果有比較低的悲觀估計誤差的話，則修剪掉
5.重複上述步驟，直到不再改善悲觀估計誤差。
而C4.5Rules的規則生成後，再來就要考慮規則的排序了。主要以規則為排序（Rule-based ordering）的方式（回顧），相同分類的規則會放在同一個規則子集合中，在分別計算每個子集合的總描述長度（Description length），以遞增方式做排序。
規則總長度的計算方式如下：
２. Rule-Based Classifier 規則分類的優點（Advantages）
所以綜合上面所有有關規則分類的介紹，我們也可以做個小總結，對其優點列表
１.規則分類與決策樹有差不多水準的高表現性
２.很容易詮釋與解釋
３.很容易的去產生
４.可以用來作預測新案例或記錄
５.效率可以媲美決策樹
３. Instance-Based Classifiers 案例式分類（Instance Based Classifiers）
案例式分類，就是採用案例的資料集做分類的意思。當今天有一個新的Record進來，接著比較他跟案例資料集中哪個案例相同，就將其分類在相同案例的一類。
舉例說明：
案例式分類，是一種懶惰的學習方式，他總是等到資料進來後才會開始進行分析的動作，之前我們所學的規則分類或是決策樹分類，都是積極型的學習方式，在資料進來之前，就已經進行所謂的建模。因此，懶惰學習方式起初並不會花費太多的時間，只有等到資料進入時才會開始動作，所以當資料有相當多比的時候，就會花費相當多的時間了。
４. Instance-Based Classifiers 案例式分類 第k個最鄰近法（k-Nearest-Neighbor）
最近鄰居法，是指在資料集裡頭與新資料最相近的那筆資料，而第k個最鄰近法是指，在資料集裡頭與新資料最接近的k筆資料。
一般可採用歐式距離：
而新案例的分類，就是看最鄰近的幾個點是什麼分類，通常以多數為決定。故上述案例就是3個＋，沒有－，所以分類為＋。
再來，上圖中，未知案例X明明離"－"比較近，就算你有兩個"＋"，還是會讓人產生疑慮，因此除了多數決定的方法外，還有對距離下權重的方式。通常來說權重會是
比方說：
身高的差異大致上是，140～185公分
體重的差異就有可能是，45公斤～120公斤
換到收入來說，就會變成，1萬元～100萬元的差異
因此，正規化屬性值，也是K-NN最鄰近法一個相當重要的前處理步驟。
５. 課後作業
有一個訓練資料集，其中包含100的Positive例子以及400個Negative例子。下面為篩選規則R：B → ＋ （覆蓋了30的Positive以及10個Negative）試問
1.正確率＝30/40＝0.75
2.FOIL's 資訊獲得量：30*［Log（30/(30+10),2）－ Log（(100/100+400),2）］=57.207
3.Likelihood ratio：2*［30*Log（30/(100*40/500) ,2）＋10*Log（10/(400*40/500) ,2］= 80.85
4.Laplace measure： （30+1）/（40+2）＝31/42
5.M-estimate（K=2, P+=0.2）：（30+(2*0.2)）/（40+2）＝0.7619
