謝霖銓 徐浩 陳希邦

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

關(guān)鍵詞：決策樹算法;ID3;PCA算法

DOI：10. 11907/rjdk. 182908 開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

中圖分類號：TP312文獻標(biāo)識碼：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ā)展產(chǎn)生了重要影響，隨著海量數(shù)據(jù)信息的不斷更新，數(shù)據(jù)庫管理系統(tǒng)受到越來越多人的重視。面對錯綜復(fù)雜的數(shù)據(jù)信息，如何對其進行高效利用成為人們亟待解決的問題。在大量數(shù)據(jù)信息中，包含著人們難以從表面發(fā)現(xiàn)的聯(lián)系，如果得不到及時利用便會很快丟失，因此迫切需要采用新的計算技術(shù)與工具挖掘數(shù)據(jù)中的含義，使數(shù)據(jù)發(fā)揮其最大價值。數(shù)據(jù)庫領(lǐng)域的知識發(fā)現(xiàn)（Knowledge Discovery in Database）及數(shù)據(jù)挖掘（DM——Data Mining）技術(shù)應(yīng)運而生[1]。

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

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

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

1 相關(guān)工作

1.1 決策樹算法簡介

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

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

1.2 PCA算法簡介

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

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

2 實驗過程

2.1 算法流程

原算法流程如下：

設(shè)當(dāng)前樣本條件屬性集為A，訓(xùn)練集為D，決策樹屬性為C。

1. 選擇訓(xùn)練決定分類屬性Ak;

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

3. 如果當(dāng)前考慮的數(shù)據(jù)隸屬于同一類，則此時N為決策樹樹葉，并在樹葉上標(biāo)記所屬的類;

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

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

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

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

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

步驟2：對數(shù)據(jù)進行標(biāo)準(zhǔn)化處理，標(biāo)準(zhǔn)化是為了將不同量綱的數(shù)據(jù)放入同一矩陣中，使數(shù)據(jù)平均值為0，標(biāo)準(zhǔn)差為1。數(shù)據(jù)標(biāo)準(zhǔn)化公式為：

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

（2）決定分類屬性。

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

（4）如果數(shù)據(jù)都屬于同一個類，N即是樹葉，在樹葉上標(biāo)出所屬的類。

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

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

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

2.2 實驗測試

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

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

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

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

3 結(jié)語

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

參考文獻：

[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]. 計算機工程與設(shè)計，2016，37（5）：1265-1270，1361.

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

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

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

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

[8] 王永梅，胡學(xué)鋼. 基于用戶興趣度和MID3決策樹改進方法[J]. 計算機工程與應(yīng)用，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] 韓松來，張輝，周華平. 基于關(guān)聯(lián)度函數(shù)的決策樹分類算法[J]. 計算機應(yīng)用，2005（11）：2655-2657.

[11] 葉明全，胡學(xué)鋼. 一種基于灰色關(guān)聯(lián)度的決策樹改進算法[J]. 計算機工程與應(yīng)用，2007（32）：171-173.

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

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

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

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

[16] 王江宇，陳煥新，劉江巖，等. 基于PCA-DT的多聯(lián)機制冷劑充注量故障診斷[J]. 華中科技大學(xué)學(xué)報：自然科學(xué)版，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] 毛國君，段立娟，王實，等. 數(shù)據(jù)挖掘原理與算法[M]. 北京：清華大學(xué)出版社，2005：117-121.

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

[22] 謝妞妞，劉於勛. 決策樹屬性選擇標(biāo)準(zhǔn)的改進[J]. 計算機工程與應(yīng)用，2010，46（34）：115-118.

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

（責(zé)任編輯：黃 ?。?/p>