數據挖掘- 分類算法比較

隨著計算能力、存儲、網絡的高速發展，人類積累的數據量正以指數速度增長。對于這些數據，人們迫切希望從中提取出隱藏其中的有用信息，更需要發現更深層次的規律，對決策，商務應用提供更有效的支持。為了滿足這種需求，數據挖掘技術的得到了長足的發展，而分類在數據挖掘中是一項非常重要的任務，目前在商業上應用最多。本文主要側重數據挖掘中分類算法的效果的對比，通過簡單的實驗（采用開源的數據挖掘工具 -Weka）來驗證不同的分類算法的效果，幫助數據挖掘新手認識不同的分類算法的特點，并且掌握開源數據挖掘工具的使用。

分類算法是解決分類問題的方法，是數據挖掘、機器學習和模式識別中一個重要的研究領域。分類算法通過對已知類別訓練集的分析，從中發現分類規則，以此預測新數據的類別。分類算法的應用非常廣泛，銀行中風險評估、客戶類別分類、文本檢索和搜索引擎分類、安全領域中的入侵檢測以及軟件項目中的應用等等。

分類算法介紹

以下介紹典型的分類算法。

Bayes

貝葉斯分類器的分類原理是通過某對象的先驗概率，利用貝葉斯公式計算出其后驗概率，即該對象屬于某一類的概率，選擇具有最大后驗概率的類作為該對象所屬的類。目前研究較多的貝葉斯分類器主要有四種，分別是：Naive Bayes、 TAN、BAN 和 GBN。

貝葉斯網絡（BayesNet）

貝葉斯網絡是一個帶有概率注釋的有向無環圖，圖中的每一個結點均表示一個隨機變量 , 圖中兩結點間若存在著一條弧，則表示這兩結點相對應的隨機變量是概率相依的，反之則說明這兩個隨機變量是條件獨立的。網絡中任意一個結點 X 均有一個相應的條件概率表 Conditional Probability Table，CPT) ，用以表示結點 X 在其父結點取各可能值時的條件概率。若結點 X 無父結點 , 則 X 的 CPT 為其先驗概率分布。貝葉斯網絡的結構及各結點的 CPT 定義了網絡中各變量的概率分布。應用貝葉斯網絡分類器進行分類主要分成兩階段。第一階段是貝葉斯網絡分類器的學習，即從樣本數據中構造分類器，包括結構學習和 CPT 學習；第二階段是貝葉斯網絡分類器的推理，即計算類結點的條件概率，對分類數據進行分類。這兩個階段的時間復雜性均取決于特征值間的依賴程度，甚至可以是 NP 完全問題，因而在實際應用中，往往需要對貝葉斯網絡分類器進行簡化。根據對特征值間不同關聯程度的假設，可以得出各種貝葉斯分類器。

樸素貝葉斯（NaiveBayes）

樸素貝葉斯模型（NBC）發源于古典數學理論，有著堅實的數學基礎，以及穩定的分類效率。同時，NBC 模型所需估計的參數很少，對缺失數據不太敏感，算法也比較簡單。NBC 模型假設屬性之間相互獨立，這個假設在實際應用中往往是不成立的，這給 NBC 模型的正確分類帶來了一定影響。在屬性個數比較多或者屬性之間相關性較大時，NBC 模型的分類效率比不上決策樹模型。而在屬性相關性較小時，NBC 模型的性能最為良好。

Lazy Learning

相對其它的 Inductive Learning 的算法來說，Lazy Learning 的方法在訓練是僅僅是保存樣本集的信息，直到測試樣本到達時才進行分類決策。也就是說這個決策模型是在測試樣本到來以后才生成的。相對與其它的分類算法來說，這類的分類算法可以根據每個測試樣本的樣本信息來學習模型，這樣的學習模型可能更好的擬 合局部的樣本特性。kNN 算法的思路非常簡單直觀：如果一個樣本在特征空間中的 k 個最相似 ( 即特征空間中最鄰近 ) 的樣本中的大多數屬于某一個類別，則該樣本也屬于這個類別。其基本原理是在測試樣本到達的時候尋找到測試樣本的 k 臨近的樣本，然后選擇這些鄰居樣本的類別最集中的一種作為測試樣本的類別。在 weka 中關于 kNN 的算法有兩個，分別是 IB1，IBk。

IB1 即 1 近鄰

IB1 是通過它的一個鄰居來判斷測試樣本的類別

IBk 即 K 近鄰

IBk 是通過它周圍的 k 個鄰居來判斷測試樣本的類別

在樣本中有比較多的噪音點是（noisy points）時，通過一個鄰居的效果很顯然會差一些，因為出現誤差的情況會比較多。這種情況下，IBk 就成了一個較優的選項了。這個時候有出現了一個問題，k 這個值如何確定，一般來說這個 k 是通過經驗來判斷的。

Trees

即決策樹算法，決策樹是對數據進行分類，以此達到預測的目的。該決策樹方法先根據訓練集數據形成決策樹，如果該樹不能對所有對象給出正確的分類，那么選擇一些例外加入到訓練集數據中，重復該過程一直到形成正確的決策集。決策樹代表著決策集的樹形結構。決策樹由決策結點、分支和葉子組成。決策樹中最上面 的結點為根結點，每個分支是一個新的決策結點，或者是樹的葉子。每個決策結點代表一個問題或決策，通常 對應于待分類對象的屬性。每一個葉子結點代表一種可能的分類結果。沿決策樹從上到下遍歷的過程中，在每個結點都會遇到一個測試，對每個結點上問題的不同的 測試輸出導致不同的分支，最后會到達一個葉子結點，這個過程就是利用決策樹進行分類的過程，利用若干個變量來判斷所屬的類別。

1. Id3 即決策樹 ID3 算法

   ID3 算法是由 Quinlan 首先提出的。該算法是以信息論為基礎，以信息熵和信息增益度為衡量標準，從而實現對數據的歸納分類。

   以下是一些信息論的基本概念：

   定義 1：若存在 n 個相同概率的消息，則每個消息的概率 p 是 1/n，一個消息傳遞的信息量為 Log2(n)

   定義 2：若有 n 個消息，其給定概率分布為 P=(p1,p2 … pn)，則由該分布傳遞的信息量稱為 P 的熵，記為

   I (p) =-(i=1 to n 求和 ) piLog2(pi) 。

   定義 3：若一個記錄集合 T 根據類別屬性的值被分成互相獨立的類 C1C2..Ck，則識別 T 的一個元素所屬哪個類所需要的信息量為 Info (T) =I (p) ，其中 P 為 C1C2 … Ck 的概率分布，即 P= (|C1|/|T| … |Ck|/|T|)

   定義 4：若我們先根據非類別屬性 X 的值將 T 分成集合 T1,T2 … Tn，則確定 T 中一個元素類的信息量可通過確定 Ti 的加權平均值來得到，即 Info(Ti) 的加權平均值為：

   Info(X, T) = (i=1 to n 求和 ) ((|Ti|/|T |) Info (Ti))

   定義 5：信息增益度是兩個信息量之間的差值，其中一個信息量是需確定 T 的一個元素的信息量，另一個信息量是在已得到的屬性 X 的值后需確定的 T 一個元素的信息量，信息增益度公式為：

   Gain(X, T) =Info (T)-Info(X, T)

2. J48 即決策樹 C4.5 算法

3. C4.5 算法一種分類決策樹算法 , 其核心算法是 ID3 算法。C4.5 算法繼承了 ID3 算法的優點，并在以下幾方面對 ID3 算法進行了改進：用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足； 在樹構造過程中進行剪枝； 能夠完成對連續屬性的離散化處理； 能夠對不完整數據進行處理。 C4.5 算法有如下優點：產生的分類規則易于理解，準確率較高。其缺點是：在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，因而導致算法的低效。

Rule

1. Decision Table 即決策表

   決策表 (Decision Table)，是一中使用表的結構，精確而簡潔描述復雜邏輯的方式。

2. JRip 即 RIPPER 算法

   規則歸納學習從分類實例出發能夠歸納出一般的概念描述。其中重要的算法為 IREP 算法和 RIPPER 算法。重復增量修枝（RIPPER）算法生成一條規則，隨機地將沒有覆蓋的實例分成生長集合和修剪集合，規定規則集合中的每個規則是有兩個規則來生成：替代規則和修訂規則。

Meta

1. AdaBoostM1 即 AdaBoosting 算法

   Adaboost 是一種迭代算法，其核心思想是針對同一個訓練集訓練不同的分類器 ( 弱分類器 ) ，然后把這些弱分類器集合起來，構成一個更強的最終分類器 ( 強分類器 ) 。其算法本身是通過改變數據分布來實現的，它根據每次訓練集之中每個樣本的分類是否正確，以及上次的總體分類的準確率，來確定每個樣本的權值。將修改過權值的新數據集送給下層分類器進行訓練，最后將每次訓練得到的分類器最后融合起來，作為最后的決策分類器。

2. Bagging 即 Bagging 方法

   Bootstrps bagging boosting 都屬于集成學習方法，將訓練的學習器集成在一起。原理來源于 PAC 學習模型（Probably Approximately CorrectK）。其中的 Bagging 是 bootstrap aggregating 的縮寫，是最早的 Ensemble 算法之一，它也是最直接容易實現，又具有不錯的效果的算法之一。Bagging 中的多樣性是由有放回抽取訓練樣本來實現的，用這種方式隨機產生多個訓練數據的子集，在每一個訓練集的子集上訓練一個同種分類器，最終分類結果是由多個分類器的分類結果多數投票而產生的。

Weka 中分類算法的參數解釋

Correlation coefficient (= CC) ： 相關系數

Root mean squared error (= RMSE) ： 均方根誤差

Root relative squared error (= RRSE) ： 相對平方根誤差

Mean absolute error (= MAE) ： 平均絕對誤差

Root absolute error (= RAE) ： 平均絕對誤差平方根

Combined: (1-abs (CC)) + RRSE + RAE： 結合的

Accuracy (= ACC) ： 正確率

注意，Correction coefficient 只適用于連續值類別，Accuracy 只適用于離散類別

Kappa statistic：這個指標用于評判分類器的分類結果與隨機分類的差異度。

絕對差值（Mean absolute error）：這個指標用于評判預測值與實際值之間的差異度。把多次測得值之間相互接近的程度稱為精密度，精密度用偏差表示，偏差指測得值與平均值之間的差值，偏差越小，精密度則越高。

中誤差（Root mean square error：RMSE）：帶權殘差平方和的平均數的平方根，作為在一定條件下衡量測量精度的一種數值指標。中誤差是衡量觀測精度的一種數字標準，亦稱“標準差”或“均方根差”。在相同觀測條件下的一組真誤差平方中數的平方根。因真誤差不易求得 , 所 以通常用最小二乘法求得的觀測值改正數來代替真誤差。它是觀測值與真值偏差的平方和觀測次數 n 比值的平方根。中誤差不等于真誤差，它僅是一組真誤差的代表值。中誤差的大小反映了該組觀測值精度的高低，因此，通常稱中誤差為觀測值的中誤差。

分類算法的評價標準

預測的準確率：這涉及到模型正確地預測新的或先前沒見過的數據的類 標號能力。

速度：涉及到產生和使用模型的計算花費。

強壯性：這涉及給定噪聲數據或具有空缺值的數據，模型正確預測的能力。

可伸縮性：這涉及給定大量的數據，有效的構造模型的能力。

可解釋性：這涉及學習模型提供的理解和洞察的層次。

分類算法的比較

以下主要采用兩種數據集（Monk's Problems 和 Satimage）來分別運行不同的分類算法，采用的是 Weka 數據挖掘工具。

Monk's Problems 數據集特點

1. 屬性全部為 nominal 類型

2. 訓練樣本較少

圖 1. 訓練數據集

3. 訓練集數據的可視化圖，該圖根據直方圖上方一欄所選擇的 class 屬性（attr6）來著色。

圖 2. 訓練數據集可視化圖

各分類器初步分類效果分析

各分類器不做參數調整，使用默認參數進行得到的結果。

表 1. 分類器初步結果比較 分類器比較

預測的準確率比較

采用基于懶惰學習的 IB1、IBk 的分類器的誤差率較低，采用基于概率統計的 BayesNet 分類器的誤差率較高，其他的基于決策樹和基于規則的分類器誤差居于前兩者之間，這是因為在樣本較少的情況下，采用 IB1 時，生成的決策模型是在測試樣本到來以后才生成，這樣的學習模型可能更好的擬合局部的樣本特性。采用統計學分類方法的 BayesNet 之所以準確度較低，可能是由于貝葉斯定理的成立本身需要很強的獨立性假設前提，而此假設在實際情況中經常是不成立的。但是一般地，統計分類算法趨于計算量大。

進一步比較分類結果的散點圖（其中正確分類的結果用叉表示，分錯的結果用方框表示），發現 BayesNet 分類器針對屬性 6（attr6）的預測結果分錯的結果明顯比 IB1 的分錯結果要多些，而這些錯誤的散點中，又以屬性 6 的取值為 2 的散點中錯誤的數目較多。

圖 3. BayesNet 的分類結果散點圖

圖 4. IB1 分類結果散點圖

分類速度比較

Adaboost 的分類花了 0.08 秒，Bagging 的分類花了 0.03 秒，相對于其他的分類器，這兩個分類器速度較慢。這是因為這兩個算法采用迭代，針對同一個訓練集，訓練多種分類器，然后把這些分類器集合起來，所以時間消耗較長。

分類器參數調優

IBK 調優

【 KNN 】：6

擴大鄰近學習的節點范圍，降低異常點的干擾（距離較大的異常點）

? 【 DistanceWeighting 】：Weight by 1/distance

通過修改距離權重，進一步降低異常點的干擾（距離較大的異常點）

圖 5. IBk 分類調優

IBk 調優結果

調優后準確率從 60.65% 上升到 63.43%。

表 2. IBk 調優結果 J48 調優

【 binarySplits 】：True

采用 2 分法，生成決策樹。

圖 6. J48 分類調優

J48 調優結果

調優后準確率從 59.72% 上升到 64.35%，但是分類模型建立時間從 0 延長到了 0.31 秒

表 3. J48 調優結果

Salmage 數據集特點

1. 屬性為 numeric 類型 , 共 37 個屬性

2. 訓練數據各類不平衡，測試數據各類不平衡

圖 7. 訓練數據集可視化圖

各分類器初步分類效果分析

各分類器不做參數調整，使用默認參數得到的結果如下：

表 4. 分類器初步結果比較 分類器比較

預測的準確率比較

采用基于懶惰學習的 IB1、IBk 的分類器的準確率都較高，為 90.36%，采用 基于決策樁的 AdaBoostM 分類器的準確率較低，為 43.08%，貝葉斯分類器的準確 率較之前的數據集（Monk ’ s problem）有明顯的提高，從 49% 到了 80% 左右，這主 要是因為樣本空間的擴大，其他的分類器準確率也處于 80% 左右。

分類速度比較

DecisionTable 的分類花了 4.33 秒，Bagging 的分類花了 3.92 秒，J48 的分類模型建立花了 2.06 秒，相對于其他的分類器，這三個分類器速度較慢。

分類器參數調優

IBK 調優

【 KNN 】：6

擴大鄰近學習的節點范圍，降低異常點的干擾（距離較大的異常點）

? 【 DistanceWeighting 】：Weight by 1/distance

通過修改距離權重，進一步降低異常點的干擾（距離較大的異常點）

IBK 調優結果

調優后準確率從 90.36% 上升到 90.98%, 準確度有略微提升，說明通過擴大鄰近學習的節點范圍不能明顯提高分類器的性能。

表 5. IBk 調優結果

J48 調優
【 binarySplits 】：True

采用 2 分法，生成決策樹。

J48 調優結果

分類性能沒有提升。說明采用 2 分法對分類沒有影響。相反，時間比原來的算法有略微延長。

表 6. J48 調優結果

改進和建議

本文給出的調優方法只是一個簡單的示例，實際上根據合理的參數調整，這些分類算法的效果還能得到更大的提升。