基于主成分分析樸素貝葉斯和決策樹比較

摘要:樸素貝葉斯和決策樹由于其較高的分類性能和簡單性得到了廣泛的使用，許多學者都在研究如何在分類前對數據進行處理以提升它們的分類性能。該文首先使用主成分分析提取特征數據，然后對處理后的數據上利用樸素貝葉斯和決策樹進行分類，并對實驗結果進行分析，比較主成分分析對它們分類性能的影響。

關鍵詞:樸素貝葉斯分類器;決策樹;分類;主成分分析

中圖分類號:TP274文獻標識碼:A文章編號:1009-3044(2010)01-222-03

The comparison of Naive Bayesian and Decision Tree Based on Principal Component Analysis

ZHANG Lin， SHI Hong-bo

(Information Management， Shanxi University of Finance Economics， Taiyuan 030006， China)

Abstract: Naive Bayes and decision tree classifications have been widely used due to their high performance and simplicity， and many scholars are studying how to process the data before classification in order to enhance the performance of their classification. This article first extracted feature data using principal component analysis， and then processed the data on the use of naive Bayes and decision tree classifications，and experimental results were analyzed and compared the impact of the principal component analysis on their classification performance.

Key words: na?觙ve bayesian classifier; decision tree; classify; principal components analysis

分類是數據挖掘中的一個重要研究課題，分類的目的是生成分類函數或分類模型，并把數據庫中的數據項映射到某個給定類別中，從而實現對數據的分類。目前有許多分類方法和技術用于構造分類模型，如決策樹、決策表、神經網絡、支持向量機、遺傳算法、樸素貝葉斯方法等。樸素貝葉斯分類模型[1-3]假定特征向量的各分量相對于決策屬性是相對獨立的(即條件獨立性假設)且屬性重要性相等。決策樹分類模型[4-6]根據屬性的信息增益構建樹模型，利用樹模型對新樣本分類。在實際的應用中，由于各屬性之間具有明顯的依賴性，并且各個屬性的重要性是不相等的，這在一定程度上限制了樸素貝葉斯分類模型的使用范圍。

人們通過各種途徑來研究改善樸素貝葉斯和決策樹的分類性能，但是很少有人研究對數據集先壓縮然后應用樸素貝葉斯分類和決策樹的方法，本文研究了對原始數據進行主成分分析，通過變換達到屬性約簡和減小屬性相關性的目的，突破了屬性重要性相等的限制，利用樸素貝葉斯分類算法和決策樹算法對原始數據集和變換后數據集分別分類，并對實驗結果進行分析討論。

1 主成分分析

1.1 主成分分析的基本思想

主成分分析[7-10](principal components analysis)是由Hotelling于1933年首先提出的。主成分分析的思想:通過線性組合的方式，快速的提取多個相關屬性地信息。當第一個線性組合不能提取更多的信息時，再考慮用第二個線性組合繼續快速提取的過程，直到所提取的信息與原指標最接近時為止。一般說來，在主成分分析適用的場合中，用較少的主成分就可以得到較多的信息量。以各個主成分為分量，就得到一個更低維的隨機向量;因此，通過主成分既可以降低數據“維數”又保留了原數據的大部分信息。

1.2 主成分分析的數學模型

原始數據矩陣X的p個屬性X1，…，Xp作線性組合如下:

矩陣表示為:

Y=UX

這里

且滿足:

1)矩陣U的每一行都是單位行向量，即

，(i=1，2，…，p)

2)Yi與Yj(i≠j，i，j=1，2，…，p)之間不相關;

3)Y1是X1，…，Xp的一切線性組合(系數滿足條件(1))中方差最大的，Y2是與Y1不相關的X1，…，Xp的一切線性組合中方差最大的，Yp是與Y1，Y2，…，Yp-1都不相關的X1，…，Xp的一切線性組合中方差最大的;

4)Y1，…，Yp的方差之和等于X1，…，Xp的方差之和。

2.3 主成分的求解

主成分的求解過程也就是求解轉換矩陣U的過程。這里舍棄復雜的數學推導，僅不加證明地給出求解主成分的一般步驟:

1)計算原始數據的協差陣∑。

2)計算協差陣∑的特征根為λ1≥…≥λp≥0，相應的單位特征向量為T1，T2，…，Tp，由這些向量構成的矩陣記為T，即有正交矩陣

T=(T1，T2，…，Tp)

則可以證明:所要求的轉換矩陣U就是特征向量矩陣T的轉置，即U=T'。也就是說，所求的矩陣U的第i行就是樣本協差陣∑的第i個特征根對應的單位特征向量Ti。

同時可以證明:第i個主成分Yi的方差等于樣本協差陣∑的第i大特征根λi。

2 分類器模型

2.1 樸素貝葉斯模型

樸素貝葉斯分類模型(Na?觙ve Bayesian Classifier)是以貝葉斯方法為理論基礎的一種最簡單，有效的而且在實際使用中很成功的分類模型。樸素貝葉斯分類模型假定特征向量的各分量相對于決策屬性是相對獨立的(即條件獨立性假設)且屬性重要性相等。

貝葉斯分類是基于貝葉斯公式，即:

其中P(C|Z)為條件Z下的后驗概率，P(C)為C的先驗概率，P(Z|C)為條件C下Z的后驗概率，P(Z)表示Z的先驗概率。為敘述方便，用大寫字母表示屬性:C表示類別屬性，A表示屬性，假定共有m個屬性，;

用小寫字母表示屬性取值:表示類別屬性，表示屬性的值域，S表示待分樣本集，表示待分類樣本，R表示訓練樣本集，表示訓練實例。在樸素貝葉斯中假設各屬性相對于類別的條件是獨立的，則有:，從而后驗概率公式為:，測試樣本(E)被分在后驗概率最大的類中，由于P(s)為一常數，則樸素貝葉斯分類模型為:

考慮到主成分分析是對數值型屬性進行分析的，因此，本文只討論取值連續的數值型屬性。假定數值型屬性服從正態分布，則:

其中，Sj是類Cj的數據集，nj是數據集Sj中的樣本個數。

2.2 決策樹模型

決策樹(decision tree)是一種類似于流程圖的樹結構，其中，每個內部節點(非葉子節點)表示在一個屬性上的測試，每個分枝代表一個測試輸出，而每個樹葉節點(或終節點)存放一個類標號。

ID3算法采用自上而下，分而治之，不回溯的遞歸方式來構造決策樹，用信息增益的方法來選擇各個結點屬性，使得每個非葉子結點在測試時能獲得最大的類別信息。該算法理論清晰，算法簡單，學習能力較強，分類速度快，適合處理大規模的學習問題，但也有邏輯能力差，泛化能力差，處理噪聲能力差等缺點。

3 實驗

3.1 實驗數據集

實驗數據取自UCI[11] 機器學習數據庫，本文共選取了20個數據集，并在機器學習平臺Weka上進行了實驗。

3.2 實驗步驟及結果

1)數據預處理。由于決策樹不能處理缺失數據和數值型數據，故首先對數據集中缺失數據使用屬性均值替換，然后對處理后的數據進行離散化處理。

2)主成分分析。利用weka系統的主成分分析方法對數據進行主成分分析。對分析后的數據另行保存，以便利用分類方法測試。

3)分類測驗。對處理后的原始數據和進行主成分分析后得到的數據分別利用ID3和Na?觙ve Bayes進行分類，實驗只列出分類準確率，實驗結果見表1。

表1的第1列為20個數據集，第2列和第3列分別給出了決策樹和樸素貝葉斯對原始數據分類得到的準確率。第4、5列分別給出了基于PCA的決策樹和基于PCA的樸素貝葉斯的實驗數據。所有數據集的測試均采用10重交叉驗證。

3.3 分析與討論

從實驗結果可以看出，對原始數據進行主成分分析后再進行決策樹分類，Glass、hungarian-14-heart-diseas、iris和zoo的分類精度有了較大的提高，其它數據集的分類精度都有了不同程度的降低;對原始數據進行主成分分析后再進行樸素貝葉斯分類，只有ionosphere、vote的分類精度有了較大的提高，其它數據集的分類精度都有了不同程度的降低。總的看來，主成分分析對決策樹分類的和樸素貝葉斯分類都有一定的影響，但對決策樹的影響更大，也就是說主成分分析更有利于提升決策樹的分類性能。 對實驗的結果和數據集的結構分析可以得出，樸素貝葉斯分類方法假設屬性之間是相互獨立的，倘若屬性之間存在依賴關系，在分類器構造過程中，將會強行去掉實際存在的依賴關系。因此，如果屬性是相互獨立的，即不僅線性不相關，而且不存在非線性依賴關系，則采用樸素貝葉斯分類將是非常適合的;如果屬性線性不相關，但存在某種非線性依賴關系，則樸素貝葉斯分類方法將無法利用其中的依賴關系，從而可能導致分類精度的損失。同樣對于決策樹來說，決策樹分類需要屬性是nominal性，且其分類的依據是屬性的信息增益，也就是說屬性之間的相關性。如果屬性之間相對獨立那么分類效果將有所下降。反之，如果屬性之間相關性較強，那么分類效果將明顯改善。

4 總結

樸素貝葉斯分類器和決策樹由于它們簡單而較高的性能得到了廣泛的研究。但是樸素貝葉斯由于其苛刻的條件獨立性假設限制了它的進一步應用。同樣對于決策樹而言，對數據屬性之間關系的處理也是研究的熱點。本文研究了基于主成分分析的屬性轉換方法對這兩種算法分類性能的影響，新的屬性集間存在較好的條件獨立性關系，并通過試驗對基于PCA的樸素貝葉斯和基于PCA的決策樹的分類精度進行了比較。雖然經過主成分分析只是在某些數據集上改善了樸素貝葉斯和決策樹的分類性能，但也可以發現相對于樸素貝葉斯來說，主成分分析對提升決策樹的分類性能更有效。

參考文獻:

[1] LANGLEYP SAGES Induction of selective Bayesian classifiers.Proceedings of the Tenth Conference On Uncertainty in Artificial Intelligence[C].Margan kaufmann，1994:399-406.

[2] 宮秀軍，劉少輝，史忠植.一種增量貝葉斯分類模型[J].計算機學報，2002(6).

[3] 程克非，張聰.基于特征加權的樸素貝葉斯分類器[J].計算機仿真，2006(10).

[4] Murthy SK.Automatic construction ofdecision trees from da-ta:A multidisciplinary survey.DataMining and Knowl-edge Discovery 1998，4(2):345-389.

[5] 劉小虎，李生.決策樹的優化算法[J].軟件學報，1998，9(1O):797-800.

[6] 王靜紅，李筆.基于決策樹的一種改進算法[J].電訊技術，2OO4，(5):175-178.

[7] Vidal R，Ma Y，Sastry S.Generalized principal component analysisGPCA[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence.2005(27):1945-1959.

[8] 張崇甫，陳述云.成分數據主成分分析及其應用[J].數理統計與管理，1996(4).

[9] 閻慈琳.關于用主成分分析做綜合評價的若干問題[J].數理統計與管理，1998(2).

[10] 朱建平.應用多元統計分析[M].北京:科學出版社，2006.