支援向量机.PPT

(C) Vipin Kumar, Parallel Issues in Data Mining, VECPAR 2002 (C) Vipin Kumar, Parallel Issues in Data Mining, VECPAR 2002 規則為基礎的分類方法 用if-then 子句來描述分類結果 分類規則的描述： 規則的左邊表示規則的前提假設，其條件如下： 分類規則的品質可以用以下幾種指標來評量 像是覆蓋率（coverage）：覆蓋率是指在資料集D 中，有多少記錄是滿足規則r 的條件 正確率（accuracy）：指有多少滿足r 條件的資料集合也同時屬於y 類別 以規則為基礎的分類技術原理 以規則分類為基礎的方法所產生的規則： 互斥規則（mutually exclusive rule）：所有資料都儘可能至多在一個規則中被歸類出來 窮盡規則（exhaustive rules）：每個資料都至少有一個規則來進行分類 若規則並非戶斥的解決方法： 規則的排序：這個方法中，規則集合中的規則都以優先順序為遞減的方式進行排序 未排序規則的方法：這個方法允許一個測試資料觸發多個分類規則，而且能夠考慮每個規則的結果，並且視為該特定類別的得票數，然後再依得票數的高低決定其歸類 規則排序的方法 以規則為基礎的排序方法：根據一些判定規則品質的衡量方式來決定其順序 以類別為基礎的排序方法：屬於同一個類別的規則會放在同一個規則集合R 中，然後再根據別的資訊進行排序 以規則為基礎的分類技術 直接法：直接從資料中萃取分類規則 最常用來萃取規則的演算法就是逐漸覆蓋（sequential covering）演算法，這些規則是以某種評估指標為主所形成，而且是以貪婪漸近（greedy fashion）的方式來成長 間接法：從其他分類模式中進行分類規則的萃取，像是決策樹以及類神經網路 逐漸覆蓋演算法之實例 Learn-one-rule 函數 目的在於萃取分類規則，而這個分類規則可以包含很多正例，而且沒有（或是非常少）負例 Learn-one-rule函數藉由利用貪婪漸近的方式來產生規則 其本身就是一個指數型搜尋空間的問題 它一開始會產生規則r，然後再逐步的修正規則，直到符合停止條件為止 Learn-one-rule 函數之規則成長策略(1) 演繹法（general-to-specific）： 先產生一個初始的規則r:{}→y 左邊是空集合，右邊則包含目標類別 規則包含所有訓練資料，所以分類品質是很差 歸納法（specific-to-general）： 先隨機選取一筆正例做為後續規則成長的基礎 在修正的階段中，規則將不斷的移除本身的一個結合來使得它可以包含更多的正例 Learn-one-rule 函數之規則成長策略(2) Learn-one-rule 函數之規則評估 規則評估的指標，在於決定那一個結合應該在規則成長的過程當中被增加或是移除 正確率可衡量那些訓練資料可以被正確的歸類 利用正確率來評估的方法卻沒有考慮到覆蓋率 利用統計檢定來刪除一些覆蓋率較差的規則 同時考慮規則覆蓋率 考量規則被用到的支持個數（support count）其中一個衡量的公式是FOIL 資訊獲利 RIPPER 演算法 能處理的資料量約和訓練範例的多寡呈線性關係 適用在類別中的資料量不平均的情況，也適用於雜訊值較多的資料中 所使用的驗證資料可以避免模式的過度學習 規則的成長：屬於演繹法的規則成長策略，會利用FOIL 資訊獲利來選取最好的結合，然後將它加入到前提條件中，直到所形成的規則包含反例為止 規則的建立：在產生規則後，所有包含在規則中的正例與反例都會被刪除掉，接著只要是沒有滿足停止條件的話，就會增加到規則集合中 間接法的規則萃取 每個決策樹從根節點到葉節點的路徑都是一個分類規則 規則產生：分類規則是每一條由根節點到葉節點的路徑中所萃取出來的 規則的排序：相同分類將歸到一個子集合下，每個子集合的總長度將分別被計算出來，而且會依照總長度來進行遞增的排序 最近鄰近點分類法 可以用來決定測試資料的類別 步驟一：利用歸納法從資料中形成分類模式 步驟二：利用演繹法將模式應用到測試資料中 選擇k 個鄰近點的重要性 k 太小，鄰近點分類技術可能會因為訓練資料的雜訊過多，有過度學習的問題 k 太大，可能會因為樣本點離鄰近點太遠而產生誤判的問題 貝氏分類法 貝氏理論（Bayes theorem），它是一個從資料當中結合類別知識的方法。 將介紹兩個貝氏分類法： 單純貝氏分類法（Na?ve Bayes ） 貝氏信念網路（Bayesian belief network，BBN） 單純貝氏分類法(1) 單純貝氏分類法是假設在類別y 中，其屬性間具有條件獨立的特性來計算機率值 其條