基于PCA的決策樹優(yōu)化算法

謝霖銓 徐浩 陳希邦

摘 要：為了改善傳統(tǒng)ID3算法在分類屬性選擇上存在多值偏向性的不足，提出基于PCA的決策樹優(yōu)化算法。在普通基于PCA 的決策樹改進算法中，存在數據經降維處理后代表性不強的問題，導致算法需經過多次數據運行后，準確率才能小幅提升。在ID3算法基礎上，在分類前兩次提取屬性特征值，并計算了需要分類的數據量，也即對原始數據進行最重要的屬性選擇。在子樹建立之后，再進行數據的降維合并選擇。采用UCI數據庫中的3個數據集對改進算法進行驗證，結果表明改進算法的平均準確率達到94.6%，相比傳統(tǒng)ID3算法與普通PCA決策樹優(yōu)化算法分別提升了1.6%和0.6%。因此，基于PCA的決策樹算法能在一定程度上提升結果準確率，具備一定的應用價值。

關鍵詞：決策樹算法;ID3;PCA算法

DOI：10. 11907/rjdk. 182908 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312文獻標識碼：A 文章編號：1672-7800（2019）009-0069-03

PCA-based Decision Tree Optimization Algorithm

XIE Lin-quan， XU Hao， CHEN Xi-bang， ZHAO Nan

（College of Science， Jiangxi University of Science and Technology，Ganzhou 341000， China）

Abstract： In this paper， the problem of the multi-valued bias of the traditional ID3 algorithm in classification attribute selection is improved. A PCA-based decision tree optimization algorithm is proposed. In the ordinary PCA-based decision tree improvement algorithm， there are data after dimension reduction processing. The problem of low representation is that the improved algorithm needs to pass through multiple data to bring the accuracy to increase slightly. Therefore， based on the ID3 algorithm， the feature values are extracted twice before classification， and the classification needs to be calculated. The amount of data， that is， the most important attribute selection for the original data， after the subtree is established， the data is reduced and merged and selected. In the experimental stage， the improved algorithm was verified by three data sets in the UCI database. The results showed that the average accuracy rate in the three data sets reached 94.6%， and the traditional ID3 algorithm and the ordinary PCA decision tree optimization algorithm were improved by 1.6% and 0.6%， which proves the algorithm has certain practical significance.

Key Words： decision tree algorithm; ID3; PCA algorithm

0 引言

如今，信息化潮流對世界發(fā)展產生了重要影響，隨著海量數據信息的不斷更新，數據庫管理系統(tǒng)受到越來越多人的重視。面對錯綜復雜的數據信息，如何對其進行高效利用成為人們亟待解決的問題。在大量數據信息中，包含著人們難以從表面發(fā)現的聯系，如果得不到及時利用便會很快丟失，因此迫切需要采用新的計算技術與工具挖掘數據中的含義，使數據發(fā)揮其最大價值。數據庫領域的知識發(fā)現（Knowledge Discovery in Database）及數據挖掘（DM——Data Mining）技術應運而生[1]。

分類算法是數據挖掘算法中的一種重要算法[2]。在傳統(tǒng)ID3決策樹算法中，通常以樣本集中最大信息增益的屬性作為樹的分裂節(jié)點，且按照從大到小的信息增益取值作為依次劃分點，即樣本集中分裂屬性個數為樣本集個數，與此同時對應樣本集節(jié)點生長出新的葉子節(jié)點。但經過后續(xù)研究發(fā)現，Quinlan的熵函具有一定弊端，其在屬性選擇時存在多值傾向性問題，因此在后續(xù)提出的C4.5算法中，通過計算信息增益率，并以此為屬性分裂標準，從而在一定范圍內避免了屬性的多值傾向性[3]。此外，文獻[4]-[6]通過引入粗糙集，利用粗糙集屬性依賴的特性，選擇決策屬性中的核屬性，以避免多值傾向問題;文獻[7]-[9]通過增加屬性重要度，可在某些程度上克服元算法的多值傾向問題，但該算法具有一定局限性，需要使用人員具有一定專業(yè)背景，且用戶主觀傾向也會對實驗結果造成極大影響;文獻[10]通過引入概率統(tǒng)計上的關聯函數對ID3算法進行優(yōu)化，可對原算法的多值傾向性問題起到一定優(yōu)化作用，但在具體計算中，其忽視了信息熵的概念，因而影響了運算準確率;文獻[11]在ID3算法中引入灰色關聯度概念，但在實際應用中難以確定范圍，且無法很好地確定屬性取值個數;文獻[12]-[13]通過對樸素貝葉斯與ID3算法的優(yōu)化融合，提升了原算法執(zhí)行效率;文獻[14]通過采用皮爾遜相關系數計算屬性間的相關性，避免了多值傾向問題，提升了算法準確率，但皮爾遜相關系數所需的數據變量是定量性質的，且服從正態(tài)分布，如果不符合該要求，計算結果的可靠性則會降低;文獻[15]-[17] 融合使用PCA方法與傳統(tǒng)決策樹方法，但由于數據降維之后代表性不足，導致多次運行才能小幅提升算法準確率。

以上方法雖然都在一定程度上解決了ID3算法的多值傾向性問題，但仍存在一定不足，也有研究結合使用PCA算法與ID3算法，但也只是簡單融合，并未進行PCA算法的多步驟計算。

本文在ID3算法基礎上，在分類前兩次提取屬性特征值，并計算需要分類的數據量，也即對原始數據進行最重要的屬性選擇，在子樹建立后再進行數據降維合并選擇，從而得到更好的結果。

1 相關工作

1.1 決策樹算法簡介

決策樹構建過程就是對數據不斷劃分的過程，每次計算都對應一個問題進行劃分，與此對應的即是決策樹節(jié)點。所以構造一個好的決策樹，需要注重切分點劃分，即準確、合理地選擇決策樹分裂屬性。

1986年，機器學習研究者Quinlan[18]將Shannon的信息論引入決策樹算法中，提出了ID3 算法。ID3算法具體計算過程如下[19-22]：設存在一個樣本集E，其中包含樣本訓練集類數為C，而C類訓練集中每項樣本數為[Pi]，i=1，2，…C。如果以屬性A作為測試屬性，屬性A的V個不同值為{[V1]，[V2]，…，[Vv]}，可以用屬性A將E劃分成V個子集{[E1]，[E2]，…，[Ev]}。假定[Ei]中含有第j類樣本個數為[Pij]，j=1，2，…C ，則子集[Ei]的熵為[12]：

1.2 PCA算法簡介

主成分分析法 （Principal Components Analysis，PCA）在1933年由霍特林首次提出[23]，PCA算法以降維為運算思路，也即在保證原數據集中信息損失較少的前提下，將多方面指標信息轉化為更少的綜合指標，從而提升對主要目標尋找的準確性。計算后得到的綜合指標被稱為主成分，任意主成分都是原數據集中變量的線性組合，且保持獨立關系。通過相關計算得到的主成分在一定程度上對原問題進行了簡化，提升了算法分析效率。

為了解決ID3原算法在分類屬性上存在的多值傾向性問題，本文融合了PCA算法與決策樹算法，在屬性分類前對數據集中的數據進行主成分分析，然后進行壓縮，選擇更重要的特性進行分類，并在子樹建立之后再次運用PCA算法進行整合。實驗結果證明，該方法在一定程度上提高了算法準確率。

2 實驗過程

2.1 算法流程

原算法流程如下：

設當前樣本條件屬性集為A，訓練集為D，決策樹屬性為C。

1. 選擇訓練決定分類屬性Ak;

2. 建立一個節(jié)點N;

3. 如果當前考慮的數據隸屬于同一類，則此時N為決策樹樹葉，并在樹葉上標記所屬的類;

4. 如果當前所考慮的數據中沒有其它屬性可以分析，則此時N也是樹葉，并按照少數服從多數的原則在樹葉上標記所屬類別;

5. 否則計算平均信息期望值，并根據屬性期望值選出一個最佳屬性作為節(jié)點N的測試屬性。

本算法主要是基于原ID3決策樹的算法，主要思想流程如下：

（1）選擇數據集合A，將數據集先采用PCA算法進行壓縮，選擇重要特性。此時采用PCA算法壓縮數據并構造決策樹時，往往面臨眾多變量，變量之間會存在一定相關性，說明其之間存在起控制作用的共同因素。本文利用該項數據特性，對原始數據中的變量相關矩陣或協方差矩陣中的內部結構進行分析研究，并采用以下步驟構造相關系數矩陣。

步驟1：將需要處理的數據進行矩陣初始化處理，構建完整的數據矩陣[Xm*n]，m表示數據條數，n表示數據記錄維數。

步驟2：對數據進行標準化處理，標準化是為了將不同量綱的數據放入同一矩陣中，使數據平均值為0，標準差為1。數據標準化公式為：

接著利用對原始變量線性組合的方式得到一些綜合指標，也即主成分。對主成分的分析過程還需對矩陣結構進行分析，找到求解的特征值。

（2）決定分類屬性。

（3）建立一個節(jié)點 N。

（4）如果數據都屬于同一個類，N即是樹葉，在樹葉上標出所屬的類。

（5）使用PCA算法對已選定的類進行再次壓縮，選擇重要特性。

（6）如果數據中沒有其它屬性可以考慮，則N也是樹葉，按照少數服從多數的原則在樹葉上標出所屬類別。

（7）否則根據平均信息期望值選出一個最佳屬性作為節(jié)點N的測試屬性。

2.2 實驗測試

為了驗證本文提出的優(yōu)化算法，選用來自UCI機器學習數據庫中的數據進行試驗。首先選取的是wine數據集，wine數據集包含178個樣本個數，13個屬性個數。原ID3算法以及本文優(yōu)化算法運行結果對比如圖1所示。

從圖1中可以清晰看出，在原ID3算法下共存在5個不重合的點，在優(yōu)化之后只存在兩個不重合的點，證明優(yōu)化算法的準確率高于原算法。

此外，本文還測試了另外兩個數據集，分別是adult及car數據集，并與普通的PCA結合ID3算法進行比較，對比結果如表1所示。

從表1中可以發(fā)現，在所對比的數據集之下，本文算法相比原ID3算法及普通的PCA結合ID3算法，在準確率上都表現得更為出色，因此本文算法具有更好的優(yōu)化效果。為了使結果更加清晰，將對比結果以圖片形式進行展示，如圖2所示。

3 結語

本文通過對原ID3算法進行優(yōu)化，提出一種基于PCA的決策樹優(yōu)化算法。實驗結果表明，改進算法在準確率上得到了一定提升。本文算法主要采用雙重PCA壓縮數據集，在一定程度上解決了原ID3算法的多值傾向問題，改善了決策樹分類規(guī)則。之后還會將該算法運用到具體案例中，以對其作進一步改進，從而使其具備更好的實際應用價值。

參考文獻：

[1] FAYYAD，USAMA M. Advances in knowledge discovery and data mining[M]. Cambridge：AAAl /The MIT Press，1996.

[2] ZHU S W. Decision tree mining technology and development trends [J]. Computer Engineering，2002，28（8）：77-78.

[3] 黃秀霞，孫力. C4.5算法的優(yōu)化[J]. 計算機工程與設計，2016，37（5）：1265-1270，1361.

[4] 朱付保，霍曉齊，徐顯景. 基于粗糙集的ID3決策樹算法改進[J]. 鄭州輕工業(yè)學院學報：自然科學版，2015，30（1）：50-54.

[5] 王子京，劉毓. 決策樹ID3新屬性選擇方法[J]. 現代電子技術，2018，41（23）：9-12.

[6] 胡煜，鄭娟. 基于粗糙集理論的ID3算法的改進與應用[J]. 貴陽學院學報：自然科學版，2015，10（1）：16-20.

[7] 李建，付小斌，吳媛媛. 基于優(yōu)化ID3的井漏類型分類算法[J]. 計算機工程，2019，45（2）：290-295.

[8] 王永梅，胡學鋼. 基于用戶興趣度和MID3決策樹改進方法[J]. 計算機工程與應用，2011，47（27）：155-157.

[9] LUO H，CHEN Y，ZHANG W. An improved ID3 algorithm based on attribute importance-weighted[C]. International Workshop on Database Technology and Applications.IEEE， 2010：1-4.

[10] 韓松來，張輝，周華平. 基于關聯度函數的決策樹分類算法[J]. 計算機應用，2005（11）：2655-2657.

[11] 葉明全，胡學鋼. 一種基于灰色關聯度的決策樹改進算法[J]. 計算機工程與應用，2007（32）：171-173.

[12] 黃宇達，王迤冉. 基于樸素貝葉斯與ID3算法的決策樹分類[J]. 計算機工程，2012，38（14）：41-43，47.

[13] 黃春華，陳忠偉，李石君. 貝葉斯決策樹方法在招生數據挖掘中的應用[J]. 計算機技術與發(fā)展，2016，26（4）：114-118.

[14] 董躍華，劉力. 基于相關系數的決策樹優(yōu)化算法[J]. 計算機工程與科學，2015，37（9）：1783-1793.

[15] 孟凡榮，蔣曉云，田恬，等. 基于主成分分析的決策樹構造方法[J]. 小型微型計算機系統(tǒng)，2008（7）：1245-1249.

[16] 王江宇，陳煥新，劉江巖，等. 基于PCA-DT的多聯機制冷劑充注量故障診斷[J]. 華中科技大學學報：自然科學版，2016，44（7）：1-4.

[17] LI M. Application of CART decision tree combined with PCA algorithm in intrusion detection[C]. Beijing：2017 8th IEEE International Conference on Software Engineering and Service Science，2017.

[18] QUINLAN J R. Induction of decision tree[J]. Machine Learning，1986（1）：81-106.

[19] LIU Y，XIE N. Improved ID3 algorithm[C]. International Conference on Computer Science and Information Technology，2010：465-468.

[20] 毛國君，段立娟，王實，等. 數據挖掘原理與算法[M]. 北京：清華大學出版社，2005：117-121.

[21] 謝妞妞. 決策樹算法綜述[J]. 軟件導刊，2015，14（11）：63-65.

[22] 謝妞妞，劉於勛. 決策樹屬性選擇標準的改進[J]. 計算機工程與應用，2010，46（34）：115-118.

[23] 何曉群. 多元統(tǒng)計分析[M]. 北京：中國人民大學出版社，2004.

（責任編輯：黃 ?。?/p>