（新疆財經大學，烏魯木齊市，830012） 吳珍珍

關鍵字 J48（C4.5）算法；Na?ve Bayes算法；對比分析

分類是數(shù)據(jù)挖掘中一項非常重要的任務，在現(xiàn)實生活中有非常廣泛的應用。例如，根據(jù)某一天的天氣狀況判斷這一天是否適合出門游玩；根據(jù)病人各項檢查指標判斷是否患有某種疾??；根據(jù)電子郵件的標題和內容判斷其是否為垃圾郵件等，以上這些實例都體現(xiàn)出了分類的重要性。

而構造分類器的方法有很多，常見的方法有決策樹、規(guī)則歸納、貝葉斯學習、神經網(wǎng)絡、支持向量機以及Ensemble方法等。在這些方法中決策樹因為其易理解、效率較高的優(yōu)點占有重要的地位，其中作為決策樹方法中經典算法的ID3算法的改進算法C4.5能夠有效地揭示需要進行分類數(shù)據(jù)的結構化信息。除此之外，樸素貝葉斯方法因為其對不確定知識表達形式的特別以及綜合了先驗知識的優(yōu)質特性成為一種簡單高效的分類算法，在數(shù)據(jù)挖掘中應用廣泛。

1 數(shù)據(jù)挖掘分類規(guī)則的基礎理論

構造分類器的方法有很多，這里主要對決策樹方法中的ID3改進算法C4.5以及樸素貝葉斯算法的基礎理論和其算法基本原理作簡要介紹。

1.1 C4.5算法基本原理

ID3算法是由羅斯昆（J.Ross Quinlan）于1975年在悉尼大學提出的一種分類預測算法。該算法以信息論為基礎，其核心是“信息熵”，通過計算每個屬性的信息增益，認為信息增益高的是好的屬性，每次劃分選取信息增益最高的屬性作為劃分標準，并重復這個過程，最后實現(xiàn)對數(shù)據(jù)的歸納分類，生成一個能夠完美分類訓練集的決策樹。

設D是一個包含｜D｜個數(shù)據(jù)樣本的集合，C為分類屬性，｜C｜為分類類別數(shù)目，A為一個屬性，Da為D中滿足條件A=a的樣本集合，PD(Ci)和分別表示D和Da中屬于類別C（ii=1,2,…，｜C｜）的樣本數(shù)所占百分比。那么由信息熵的定義得出樣本集合D對于的信息熵為：

利用屬性A對樣本集合D中進行劃分所對應的信息熵為：

因此，屬性A在樣本集合D中為分類所提供的信息量即信息增益為：

而C4.5算法是由羅斯昆（J.Ross Quinlan）提出的對ID3算法的一個改進算法，它繼承了ID3算法的優(yōu)點，并且利用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多屬性的不足，且在構造決策樹的過程中能對其進行剪枝，使得產生的分類規(guī)則易于理解，準確率較高。

C4.5算法利用增益比率來克服ID3算法用信息增益選擇屬性偏向選擇取值多的屬性作為決策樹樹根的問題，那么就有：

因此，屬性A在樣本集合D中為分類所提供的信息量占比即信息增益率為：

一般情況下認為信息增益率高的是好的屬性，每次劃分選取信息增益率最高的屬性為劃分標準，并重復這個過程，直至生成一個能夠完美分類訓練集的決策樹。

1.2 樸素貝葉斯方法基本原理

樸素貝葉斯方法是基于貝葉斯定理與特征條件獨立假設的一種分類方法，故有這種方法構造的貝葉斯分類器基于一個簡單的假定，即給定目標值時屬性之間相互條件獨立。和決策樹相比，樸素貝葉斯方法構造分類器發(fā)源于古典數(shù)學理論，有更加堅實的數(shù)學基礎，以及更穩(wěn)定的分類效率。

設為最大可能后驗概率，D是一個包含｜D｜個數(shù)據(jù)樣本的集合，V為假設空間，為假設H的事前概率，為D的事前概率，這對于假設H而言是一個常數(shù)定值，假設H在樣本集D下出現(xiàn)的條件概率。那么樸素貝葉斯算法根據(jù)貝葉斯定理，在基于給定目標值時屬性之間相互條件獨立的簡單假設前提下，來預測屬性分類的結果就有：

假設樣本集D有n個屬性，記為A1,A2,…,An，其對應的屬性值記為a1,a2,…,an；C為分類屬性，｜C｜為分類類別數(shù)目。并且可以預測樣本D屬于類Ci當且僅當有p( Ci|D )＞p(Cj|D )，其中i≠j，且i，j=1,2,…,｜C｜。

而根據(jù)貝葉斯定理可以得到p(C i|D )=，這里p(D)對于所有類均為常數(shù)，故只需要最大化p( D|Ci)p(Ci)即可。如果所屬類別的先驗概率p(Ci)未知，則通常假設p(Ci)=p( Cj)，這里≠j,且i,j=1,2,…,｜C｜，所以在給定目標值時屬性之間相互條件獨立的假設前提下有p( D|Ci)=，從而得出樣本D應屬類別。

2 基于C4.5及樸素貝葉斯算法的實例解析

Bank Matketing Data Set中共有4 119條數(shù)據(jù)，其中規(guī)定其含有訓練數(shù)據(jù)集2 719條，測試數(shù)據(jù)集1 400條，分類的目標屬性為存款（定期）意愿，記為y。根據(jù)年齡（age）、工作類型（job）、婚姻狀況（marital）、教育程度（education）、拖欠款狀況（default）、房貸（housing）、個人貸（loan）等屬性來判斷其存款傾向（y）是否有意愿。

在進行分析之前，由于weka部分分類分析算法要求屬性必須是nominal類型，故需要將數(shù)據(jù)集中原本是numeric類型的屬性進行離散化，將其轉換成nominal類型，例如年齡（age）屬性我們定義小于等于20的記為“young”,大于50的記為“old”，大于20且小于等于50的記為“wrinkly”，從而完成了數(shù)據(jù)的轉換。（詳見表1）

2.1 算法分類結果將數(shù)據(jù)集

以.csv的格式導入weka軟件中去，使用J48（C4.5）以及樸素貝葉斯等三種分類算法對該數(shù)據(jù)集進行分類。（詳見表2）

從分類結果中可以看出，Na?ve Bayes算法的分類效果在準確率與誤差率上要比J48（C4.5）算法有微小優(yōu)勢差距，且其算法分類所需要的時間也要比J48（C4.5）算法有著較明顯的優(yōu)勢。

2.2 算法分類結果分析

2.2.1 J48（C4.5）算法結果分析

根據(jù)weka軟件運行結果，J48（C4.5）算法具體分類結果（即Confusion Matrix）見表3。從表3可知，沒有存定期款傾向意愿且分類結果也將其劃分為沒有意愿的實例個數(shù)為1 238個；沒有存定期款傾向意愿但分類結果將其劃分為有意愿的實例個數(shù)為0個；有存定期款傾向意愿且分類結果也將其劃分為有意愿的實例個數(shù)為0個；有存定期款傾向意愿但分類結果將其劃分為沒有意愿的實例個數(shù)為162個。

表1 部分數(shù)據(jù)集情況

表2 不同算法針對Bank Marketing數(shù)據(jù)集的分類結果

表3 J48（C4.5）算法對Bank Marketing數(shù)據(jù)集的分類結果

表4 J48（C4.5）算法在對Bank Marketing數(shù)據(jù)集的分類效果

表5 J48（C4.5）置信因子調節(jié)對分類精度的影響情況

由上，分類正確的實例個數(shù)為1 238個，分類錯誤的實例個數(shù)為162個。所以分類的準確率為88.4286%，分類的錯誤率為11.5 714%。下面再給出J48（C4.5）算法分類的正確率、召回率和F-measure指標的值，結果如表4所示。

由表4可知，正確率（Precision）表示實際上存定期款傾向真實有意愿（真實沒意愿）的實例個數(shù)占分類成有存定期款傾向意愿（沒意愿）的實例個數(shù)的比例；召回率（Recall）表示正確分類成有存定期款意愿（沒有存定期款意愿）的實例個數(shù)占總的有存定期款意愿（沒有存定期款意愿）的實例個數(shù)的比例；F-measure指標則將正確率與召回率結合起來，揭示兩者間的關系，衡量兩者的平衡性能，且一般情況下，計算F-measure有公式：

綜上，作為ID3算法改進的J48（C4.5）算法，在對Bank Marketing數(shù)據(jù)集的分類預測中，J48（C4.5）的準確率達到了88.4 286%，分類的速度為0.03秒，它增加了樹枝的修剪，克服了關于數(shù)據(jù)缺失和噪音數(shù)據(jù)的缺點，該算法應用在該數(shù)據(jù)集上所得的結果是可以接受的。但是，weka中J48（C4.5）算法有置信因子及新分類的葉子節(jié)點上需要含有的實例個數(shù)這兩個參數(shù)可以調節(jié)。調節(jié)其中一個參數(shù)：置信因子，此時得到的分類結果如下表5所示：

由表3～5,可以得到：隨著置信因子的增加，J48算法的運行速度、正確率都有所上升，這主要是因為置信因子的增加將減少對樹的修剪，從而獲得一棵更加特殊的樹。

2.2.2 Na?ve Bayes算法結果分析

根據(jù)weka軟件運行結果，Na?ve Bayes算法具體分類結果（即Confusion Matrix）如表6所示：

從表6中，可以得到：沒有存定期款傾向意愿且分類結果也將其劃分為沒有意愿的實例個數(shù)為1 227個；沒有存定期款傾向意愿但分類結果將其劃分為有意愿的實例個數(shù)為11個；有存定期款傾向意愿且分類結果也將其劃分為有意愿的實例個數(shù)為0個；有存定期款傾向意愿但分類結果將其劃分為沒有意愿的實例個數(shù)為150個。

表6 Na?ve Bayes算法對Bank Marketing數(shù)據(jù)集的分類結果

表7 Na?ve Bayes算法在對Bank Marketing數(shù)據(jù)集的分類效果

表8 Bank Marketing數(shù)據(jù)集上不同算法的比較情況

由上，分類正確的實例個數(shù)為1239個，分類錯誤的實例個數(shù)為161個。所以分類的準確率為88.5%，分類的錯誤率為11.5%。下面再給出Na?ve Bayes算法分類的正確率、召回率和F-measure指標的值，結果如表7所示。

2.3 J48（C4.5）與Na?ve Bayes算法結果的比較分析

數(shù)據(jù)挖掘中算法的性能比較一般可以從以下幾個方面，包括分類速度、準確率、可伸縮性、強壯性以及可理解性等進行比較?？缮炜s性表示對于數(shù)據(jù)量很大的數(shù)據(jù)集能有效構造模型的能力，樸素貝葉斯算法因其獨特的特質對數(shù)據(jù)量極大且數(shù)據(jù)集樣本屬性之間關聯(lián)盡量小的數(shù)據(jù)集進行分類的效果具有很大的優(yōu)勢；強壯性表示模型對噪聲數(shù)據(jù)或空缺值數(shù)據(jù)正確預測的能力，從對基礎理論的介紹中我們已經知道了J48（C4.5）算法對這方面的處理更好。因此，表8對所采用的算法進行了一個簡單的比較。

由表8可以得到，Na?ve Bayes算法相較J48（C4.5）算法不僅分類速度更快，對數(shù)據(jù)集分類的準確率也更優(yōu)勝一籌。除此之外，對于樣本空間容量巨大的數(shù)據(jù)集也能夠比較有效的進行分類，雖然其對數(shù)據(jù)值缺失及噪音數(shù)據(jù)等問題的處理能力比不上J48（C4.5）算法，但在缺失數(shù)據(jù)量不大的情況下，對由于數(shù)據(jù)值缺失及噪音數(shù)據(jù)所引起的問題是可以容忍的。因此，可以得出樸素貝葉斯Na?ve Bayes算法要比J48（C4.5）算法的分類效果更好。

3 總結

隨著信息化步伐的加快，面對龐雜的數(shù)據(jù)，如何提取出這些數(shù)據(jù)中未知的且具有潛在價值的信息就顯得尤為重要。利用數(shù)據(jù)挖掘技術對有用知識進行提取能夠為人類提供有決策意義的信息。在介紹數(shù)據(jù)挖掘中分類技術基礎理論的基礎上，基于weka平臺，利用分類算法中的J48（C4.5）及Na?ve Bayes算法對Bank Marketing數(shù)據(jù)集進行分類實驗分析，并從運行速度、正確率、可伸縮性、強壯性等方面對兩種算法的分類效果進行了對比分析，得出了Na?ve Bayes算法相較J48（C4.5）算法能得到更有效的分類結果的結論。這為銀行在對客戶相關信息的了解基礎上判斷該客戶是否具有存定期存款傾向的意愿具有重要意義，從而有針對性的增加意愿存定期款客戶數(shù)量，提高該銀行在銀行市場的競爭力。