謝霖銓 徐浩 陳希邦

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

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

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

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

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

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

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

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

1 相關(guān)工作

1.1 決策樹算法簡(jiǎn)介

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

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

1.2 PCA算法簡(jiǎn)介

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

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

2 實(shí)驗(yàn)過(guò)程

2.1 算法流程

原算法流程如下：

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

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

2. 建立一個(gè)節(jié)點(diǎn)N;

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

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

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

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

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

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

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

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

（2）決定分類屬性。

（3）建立一個(gè)節(jié)點(diǎn) N。

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

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

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

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

2.2 實(shí)驗(yàn)測(cè)試

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

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

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

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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