第5章分类技术ppt课件.ppt

《第5章分类技术ppt课件.ppt》由会员分享，可在线阅读，更多相关《第5章分类技术ppt课件.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2008台灣培生教育出版(PearsonEducationTaiwan)第5章分类技术ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望2008台灣培生教育出版(PearsonEducationTaiwan)規則為基礎的分類方法規則為基礎的分類方法l用if-then 子句來描述分類結果l分類規則的描述：l規則的左邊表示規則的前提假設，其條件如下：l分類規則的品質可以用以下幾種指標來評量像是覆蓋率（coverage）：覆蓋率是指在資料集D 中，有多少記錄是滿

2、足規則r 的條件正確率（accuracy）：指有多少滿足r 條件的資料集合也同時屬於y 類別2008台灣培生教育出版(PearsonEducationTaiwan)以規則為基礎的分類技術原理以規則為基礎的分類技術原理l以規則分類為基礎的方法所產生的規則：互斥規則（mutually exclusive rule）：所有資料都儘可能至多在一個規則中被歸類出來窮盡規則（exhaustive rules）：每個資料都至少有一個規則來進行分類l若規則並非戶斥的解決方法：規則的排序：這個方法中，規則集合中的規則都以優先順序為遞減的方式進行排序未排序規則的方法：這個方法允許一個測試資料觸發多個分類規則，而且

3、能夠考慮每個規則的結果，並且視為該特定類別的得票數，然後再依得票數的高低決定其歸類2008台灣培生教育出版(PearsonEducationTaiwan)規則排序的方法規則排序的方法l以規則為基礎的排序方法：根據一些判定規則品質的衡量方式來決定其順序l以別為基礎的排序方法：屬於同一個類別的規則會放在同一個規則集合R 中，然後再根據別的資訊進行排序2008台灣培生教育出版(PearsonEducationTaiwan)以規則為基礎的分類技術以規則為基礎的分類技術l直接法：直接從資料中萃取分類規則最常用來萃取規則的演算法就是逐漸覆蓋（sequential covering）演算法，這些規則是以某種

4、評估指標為主所形成，而且是以貪婪漸近（greedy fashion）的方式來成長l間接法：從其他分類模式中進行分類規則的萃取，像是決策樹以及類神經網路2008台灣培生教育出版(PearsonEducationTaiwan)逐漸覆蓋演算法之實例逐漸覆蓋演算法之實例2008台灣培生教育出版(PearsonEducationTaiwan)Learn-one-rule 函數函數l目的在於萃取分類規則，而這個分類規則可以包含很多正例，而且沒有（或是非常少）負例lLearn-one-rule函數藉由利用貪婪漸近的方式來產生規則l其本身就是一個指數型搜尋空間的問題l它一開始會產生規則r，然後再逐步的修正規則

5、，直到符合停止條件為止2008台灣培生教育出版(PearsonEducationTaiwan)Learn-one-rule 函數之規則成長策函數之規則成長策(1)l演繹法（general-to-specific）：先產生一個初始的規則r:y左邊是空集合，右邊則包含目標類別規則包含所有訓練資料，所以分類品質是很差l歸納法（specific-to-general）：先隨機選取一筆正例做為後續規則成長的基礎在修正的階段中，規則將不斷的移除本身的一個結合來使得它可以包含更多的正例2008台灣培生教育出版(PearsonEducationTaiwan)Learn-one-rule 函數之規則成長策函數之

6、規則成長策(2)2008台灣培生教育出版(PearsonEducationTaiwan)Learn-one-rule 函數之規則評估函數之規則評估l規則評估的指標，在於決定那一個結合應該在規則成長的過程當中被增加或是移除l正確率可衡量那些訓練資料可以被正確的歸類l利用正確率來評估的方法卻沒有考慮到覆蓋率利用統計檢定來刪除一些覆蓋率較差的規則同時考慮規則覆蓋率考量規則被用到的支持個數（support count）其中一個衡量的公式是FOIL 資訊獲利2008台灣培生教育出版(PearsonEducationTaiwan)RIPPER 演算法演算法l能處理的資料量約和訓練範例的多寡呈線性關係l適用

7、在類別中的資料量不平均的情況，也適用於雜訊值較多的資料中l所使用的驗證資料可以避免模式的過度學習l規則的成長：屬於演繹法的規則成長策略，會利用FOIL 資訊獲利來選取最好的結合，然後將它加入到前提條件中，直到所形成的規則包含反例為止l規則的建：在產生規則後，所有包含在規則中的正例與反例都會被刪除掉，接著只要是沒有滿足停止條件的話，就會增加到規則集合中2008台灣培生教育出版(PearsonEducationTaiwan)間接法的規則萃取間接法的規則萃取l每個決策樹從根節點到葉節點的路徑都是一個分類規則l規則產生：分類規則是每一條由根節點到葉節點的路徑中所萃取出來的l規則的排序：相同分類將歸到一

8、個子集合下，每個子集合的總長度將分別被計算出來，而且會依照總長度來進行遞增的排序2008台灣培生教育出版(PearsonEducationTaiwan)最近鄰近點分類法最近鄰近點分類法l可以用來決定測試資料的類別步驟一：利用歸納法從資料中形成分類模式步驟二：利用演繹法將模式應用到測試資料中l選擇k 個鄰近點的重要性k 太小，鄰近點分類技術可能會因為訓練資料的雜訊過多，有過度學習的問題k 太大，可能會因為樣本點離鄰近點太遠而產生誤判的問題2008台灣培生教育出版(PearsonEducationTaiwan)貝氏分類法貝氏分類法l貝氏理論（Bayes theorem），它是一個從資料當中結合類別

9、知識的方法。l將介紹兩個貝氏分類法：單純貝氏分類法（Nave Bayes）貝氏信念網路（Bayesian belief network，BBN）2008台灣培生教育出版(PearsonEducationTaiwan)單純貝氏分類法單純貝氏分類法(1)l單純貝氏分類法是假設在類別y 中，其屬性間具有條件獨立的特性來計算機率值l其條件獨立的公式為：l其中屬性集合X=X1,X2,Xd 包含d 個屬性l為了要分類測試資料，單純貝氏分類法要計算每個類別Y 的事後機率：2008台灣培生教育出版(PearsonEducationTaiwan)單純貝氏分類法單純貝氏分類法(2)l單純貝氏分類法的特性可以處理雜

10、訊資料的問題，而且也可以在模式建立以及分類的時候忽略掉遺漏值可以處理不相關的屬性關聯度高的屬性可能會因為沒有滿足條件獨立的假設，而使得誤判率提高2008台灣培生教育出版(PearsonEducationTaiwan)貝氏信念網路貝氏信念網路(1)l貝氏信念網路簡稱貝氏網路l提供以圖形的方式來表示隨機變數間機率關係l貝氏網路的兩個重要元素是：用直接的非循環圖表示變數間的相依關係機率表的內容為每個節點和它的父節點間的關聯性l貝氏網路如果在父節點未知的情形下，其非子孫的節點具有條件獨立的特性。圖用直接非循環圖來表示機率關係2008台灣培生教育出版(PearsonEducationTaiwan)貝氏信

11、念網路貝氏信念網路(2)l模式建立的兩個步驟：1.建立網路結構2.形成每個節點與節點關聯的機率表l貝氏信念網路的特性提供一個利用圖形模式從特定的領域當中獲取知識的方法，而這個網路可以用來表示變數間的因果關係要建立一個網路也許需要耗費大量的時間；但網路模式建立後，就可很快的增加新變數適合用來處理不完整的資料問題。而如果資料本身具有遺漏值的話，也可以藉由彙整、或是整合所有屬性的可能值，來處理這個問題資料是結合事前知識的機率，可避免模式過度學習2008台灣培生教育出版(PearsonEducationTaiwan)類神經網路類神經網路(1)l類神經網路（Artificial Neural Netwo

12、rk，ANN）的研究源起於想要模擬生物的神經系統l人類的大腦是很多的神經元細胞所組成的，這些稱為神經元（neurons）l神經元會彼此透過神經軸（axon）相互連結l神經軸用來轉換神經元至其他被刺激的神經間的脈衝l一個神經元會經由突觸（dendrites）連結至另一個神經軸l人類大腦的學習可藉由突觸在神經元間連結的重覆刺激所改變的長度而獲得學習l類神經網路是很多內部的節點間的相互連結所組成的結構2008台灣培生教育出版(PearsonEducationTaiwan)類神經網路類神經網路(2)l感知機網路，由兩種節點所組成。輸入節點表示輸入屬性；輸出節點表示輸出結果l這個生物神經系統會讓感知機網

13、路不斷的調整連結的權重值，直到輸入與輸出的對應關係符合原來的訓練資料為止2008台灣培生教育出版(PearsonEducationTaiwan)類神經網路類神經網路(3)l多層網路：允許輸入與輸出層中間再存在節點，我們稱為中間層，又稱為隱藏層多層前向式架構類神經網路2008台灣培生教育出版(PearsonEducationTaiwan)類神經網路類神經網路(4)lANN 學習演算法的目的在於決定權重w，然後得到最小的誤差值平方lANN 網路的特性如下：多層類神經網路至少有一個隱藏層具有普遍逼近（universal approximators）的性質ANN 可以用來處理多餘的特徵值類神經網對於具

14、有雜訊的訓練資料問題會非常敏感最陡坡降法可用來學習ANN 中的權重值要訓練ANN 網路是很耗時的，尤其是當隱藏層節點很多的情形，不過一旦模式建立之後，就能夠很快的針對測試資料進行歸類2008台灣培生教育出版(PearsonEducationTaiwan)支援向量機支援向量機l支援向量機（support vector machine，SVM）的分類技術起源於統計學習理論lSVM 也能夠處理高維度資料的問題l可以使用訓練範例的子集合來表示決策界限，就是支援向量（support vector）2008台灣培生教育出版(PearsonEducationTaiwan)最大邊際超平面最大邊際超平面l可找到

15、一個超平面（hyperplane），將兩個類別的資料分開B1的邊大於B2，在這個例子中，B1是具有最大邊界的超平面2008台灣培生教育出版(PearsonEducationTaiwan)線性的支援向量機：可分割的例子線性的支援向量機：可分割的例子l線性支援向機：可分割的情況支援向量機的學習方式可以正式化成以下的限制最佳化的問題：l線性資料可分割的例子2008台灣培生教育出版(PearsonEducationTaiwan)線性支援向量機：不可分割的情形線性支援向量機：不可分割的情形l支援向量機在不可分割類別問題的決策界限l不可分割資料的差額變數2008台灣培生教育出版(PearsonEducat

16、ionTaiwan)非線性的支援向量機非線性的支援向量機l將原屬於同類空間x 中的資料轉換成新的空間 ，如此線性決策界限就可在轉換後的空間中分割資料l非線性的支援向量機：非線性的支援向量機的學習可以用以下最佳化問題來表示：2008台灣培生教育出版(PearsonEducationTaiwan)kernel trick方法方法lkernel trick 是一個在轉換空間中使用原始屬性集合來計算相似度的方法l可用在非線性的支援向量機的問題上不用知道正確的對映函數使用kernel函數計算點乘積比起使用轉換後的屬性集合來得容易因在原始的空間中進行計算，可避免維度問題l使用多項式kernel 函數的非線

17、性決策界限2008台灣培生教育出版(PearsonEducationTaiwan)支援向量機的特性支援向量機的特性l支援向量機的學習問題可以轉變成凸型最佳化的問題，可以用來找到目標函數的全域最佳化l支援向量機可藉由最大化決策界限的邊界來執行容量的控制（capacity control）l支援向量機可以針對每個類別屬性變數建立虛擬變數，使得支援向量機可以應用在類別型資料上l可處理二元與多元分類的問題2008台灣培生教育出版(PearsonEducationTaiwan)整合法整合法l藉由整合多種分類方法以改善分類正確性的方法l這些技術我們稱為整合法或是分類技術的結合法l根據每個分類方法對訓練資料

18、預測結果的投票所建立的整合分類方法l整合分類法的結果比基本分類法好的兩個必要條件基本分類法間要彼此獨立基本分類法應該要比隨機猜測的結果要好才行2008台灣培生教育出版(PearsonEducationTaiwan)基本分類法與整合分類法錯誤率的比較基本分類法與整合分類法錯誤率的比較2008台灣培生教育出版(PearsonEducationTaiwan)建立整合分類法的過程建立整合分類法的過程2008台灣培生教育出版(PearsonEducationTaiwan)整合的方法整合的方法l藉由處訓資：可根據樣本分配的狀況，另外產生一些相似的樣本。樣本的分配將決定所要選取的資料要和訓練資料有多相似，而

19、且有可能和其他訓練資料不一樣l藉由處輸入的特徵：輸入特徵將被隨機選取、或是經由領域專家的推薦而獲得l藉由處別標籤：可用在類別個數太多的情形，其訓練資料可以藉由隨機將類別分到兩個子集合（A0 及A1）中，將這類問題轉成二元分類l藉由處學習演算法：很多學習演算法可以在同一個訓練資料上用很多次，而這種做法就會產生不同的模式2008台灣培生教育出版(PearsonEducationTaiwan)誤差變異數的分割誤差變異數的分割(1)l誤差變異數的分割（Bias-Variance Decomposition）是用來分析預測模式誤判的方法2008台灣培生教育出版(PearsonEducationTaiwa

20、n)誤差變異數的分割誤差變異數的分割(2)l從相同的訓練資料中所產生的兩個具有不同複雜度的決策樹2008台灣培生教育出版(PearsonEducationTaiwan)誤差變異數的分割誤差變異數的分割(3)l比較決策樹與一個最近鄰近點分類法的決策界限2008台灣培生教育出版(PearsonEducationTaiwan)Bagging(1)lBagging 就是bootstrap aggregating 方法l根據均一機率分配，然後從資料集合中重覆產生樣本資料的技術l每一個bootstrap樣本的大小都和原始資料一樣l因為樣本在產生之後會取代原資料，所以有一些樣本也許會重覆很多次，同時有一些資

21、料也許會因此被刪掉2008台灣培生教育出版(PearsonEducationTaiwan)Bagging(2)l可藉由縮減基本分類法的變異改善錯誤率l其效果視基本分類法的穩定性而定基本分類法不穩定，bagging可用隨機變動的方法來降低錯誤率基本分類法很穩定，像是對於一些雜訊值較不敏感，那麼整合分類法的錯誤將僅是決定於基本分類法的誤差值l每個樣本都有相同被選取的機率，因此bagging 無法強調特定的訓練資料，因此在處理雜訊資料時較不易受影響而有過度學習的問題2008台灣培生教育出版(PearsonEducationTaiwan)Boosting(1)lBoosting 是一個重覆用來適應訓練

22、資料分配改變的程序，所以可以用來處理一些基本分類法很難處理的分類問題lboosting 可指定每個訓練資料的權重，也可以在每次boosting 結束時適當地改變權重l改變訓練資料權重值的方法如下：可以從原始資料中拿出部分bootstrap 樣本來做為抽樣的分配可以藉由基本分類法學習模式2008台灣培生教育出版(PearsonEducationTaiwan)Boosting(2)lboosting 演算法的差異在每次boosting 後要更新訓練資料的權重值每個分類法的預測結果要如何結合lboosting 演算法：AdaBoost方法2008台灣培生教育出版(PearsonEducationTa

23、iwan)隨機林隨機林(1)l隨機林（random forests）是一個特別設計給決策樹分類法使用的整合分類方法l它結合多個決策樹的預測結果，而每個樹都是根據隨機林的隨機向量的值所建立的lBagging 使用決策樹是隨機林中的一個特例，其將隨機選取N個例子來取代原始訓練資料，然後加入模式建立的程序中2008台灣培生教育出版(PearsonEducationTaiwan)隨機林隨機林(2)2008台灣培生教育出版(PearsonEducationTaiwan)隨機林隨機林(3)l每個決策樹都使用固定機率分配所產生的隨機向量，其隨機向量可以用很多方法加到樹的成長過程中1.Forest-RI：在每

24、個節點上隨機選取F 輸入特徵來進行分割，所要分割的節點是由所選取的F 特徵中決定出來的，然後樹將持續成長而不用修改2.Forest-RC：在每個節點上，隨機結合新特徵F，再從這些特徵當中選出最適合分割的節點3.在每個節點上隨機從F 個最好的分割點中選取一個來產生隨機樹2008台灣培生教育出版(PearsonEducationTaiwan)分類不均的問題分類不均的問題l專門處理分類不均的演算法，以改善少量資料的預測效果ROC 分類成本敏感（cost-sensitive）學習法抽樣為主的方法（sampling-based methods）2008台灣培生教育出版(PearsonEducationT

25、aiwan)不同的評估方法不同的評估方法l確（precision）：指在所有模式預測為正類別的資料中，有多少比例恰好是正類別的資料，其值愈高，表示被誤判的比例愈低l回覆（recall）：指實際上為正類別的資料中，同時也被模式判為正類別的比例，回覆率的值愈高，表示誤判的比例也較低2008台灣培生教育出版(PearsonEducationTaiwan)接收器操作指標接收器操作指標(1)l接收器操作指標（Receiver Operating Characteristic，ROC）曲線是一個顯示真陽性比率（TPR）、及偽陽性比率（FPR）兩個值之間相互取捨的圖形lROC 曲線上有三個重要的點，分別解釋

26、如下：（TPR=0 及FPR=0）表示模式將每個資料都預測為負類別（TPR=1 及FPR=1）表示模式將每個資料都預測為正類別（TPR=1 及FPR=0）表示理想模式2008台灣培生教育出版(PearsonEducationTaiwan)接收器操作指標接收器操作指標(2)lROC 曲線下方面積（AUC）提供評估模式的方法AUC接近1：模式很好AUC接近0.5：模式比隨機猜測的結果好一點l兩種不同分類法的ROC曲線2008台灣培生教育出版(PearsonEducationTaiwan)產生產生ROC曲線曲線1.假設我們將連續型的輸出值定義成正類別，然後將測試資料的輸出值依遞增排序2.選擇排序最低

27、的測試資料，將選出的資料、以及比所選出的資料有更高排序的資料指定成正類別3.從排序清單中選取下一個測試資料，將所選出的資料、以及比所選出的資料有更高排序的資料指定成正類別，同時低於這些排序的資料視為負類別。然後藉由檢查之前所選的資料的真實類別來更新真陽性及偽陽性的總和4.重覆步驟3，並且更新真陽性及偽陽性，直到最高排序的測試資料被選取為止5.繪出分類法的真陽性比例和偽陽性比例2008台灣培生教育出版(PearsonEducationTaiwan)成本敏感度學習成本敏感度學習(1)l成本敏感度分類技術是在模式建立期間將成本矩陣考慮進去，使得所產生的模式有較低的成本l有多種將成本資訊加入分類演算法

28、的方法，例如，在決策樹中，成本資料可以用來：選擇最好的屬性以分割資料決定是否要修剪子樹處理訓練資料的權重，如此一來學習演算法可以使決策樹收斂，並有最小成本在每個樹葉節點中修改決策規則2008台灣培生教育出版(PearsonEducationTaiwan)成本敏感度學習成本敏感度學習(2)l修正決策界限（從B1 到B2），以降低實際上為正類別的資料中，被模式誤判的比例2008台灣培生教育出版(PearsonEducationTaiwan)抽樣的方法抽樣的方法(1)l抽樣是另一個常被用來處理分類不均問題的方法，主要在於修改資料的分配，使得資料較少的類別可以有好的表現l可行的抽樣技術抽樣不足（und

29、ersampling）過度抽樣（oversampling）混合抽樣2008台灣培生教育出版(PearsonEducationTaiwan)抽樣的方法抽樣的方法(2)l對少量類別資料過度抽樣的效果2008台灣培生教育出版(PearsonEducationTaiwan)抽樣的方法抽樣的方法(3)l混合方法在於將多數類別進行抽樣不足，以及針對少數類別進行過度抽樣的作法，以使類別中的資料量能夠平均。l抽樣不足可以用隨機或是強迫副抽樣不足法（forced subsampling）來處理l過度抽樣可以複製已經存在的正例、或是在已經存在的正例附近產生新的正例，後面的做法必須先決定每個已經存在正例的k 個最近

30、鄰近點2008台灣培生教育出版(PearsonEducationTaiwan)多元類別問題多元類別問題l多元分類方法1 對多（one-against-rest，1r）方法：將多元分類的問題分割成K 個位元問題1 對1（one-againe-one，11）：其建構k(k1)/2 個二元分類法，而每個分類法都用來區別兩個類別(yi,yj)2008台灣培生教育出版(PearsonEducationTaiwan)錯誤更新的輸出編碼錯誤更新的輸出編碼l在錯誤更新的輸出編碼（error-correcting output coding，ECOC）方法，處理多元分類問題的方法l將訊息透過雜訊通道來傳送l多傳送一個代碼至傳訊的訊息中，如此接收器會在接受到訊息時偵測到錯誤，若錯誤率很小時則恢復至回來的訊息l每個類別都可以編碼成成單獨的位元字串，然後訓練n 個位元分類來預測每個代碼字串中的位元，測試資料的預測類別將可以用漢明距離（Hamming distance）來計算