陳全園 侯帥琳 李雅琪

摘 要：通過對ID3算法的深入研究，發(fā)現(xiàn)其存在多值偏向、計(jì)算復(fù)雜和效率不高等問題。為了解決這些問題，文章對ID3算法模型進(jìn)行了優(yōu)化，并提出了一種基于向量相似度的改進(jìn)ID3算法。在計(jì)算信息增益時(shí)，首先使用二階麥克勞林公式簡化了原始公式，從而減少了ID3算法在log函數(shù)上的運(yùn)算時(shí)間和復(fù)雜程度。然后通過構(gòu)造樣本結(jié)構(gòu)相似矩陣，并引入向量相似度作為權(quán)重，極大程度上避免了多值偏向的問題。通過實(shí)例驗(yàn)證對比，文章證明了這種優(yōu)化在不影響后續(xù)運(yùn)算并保證結(jié)果可靠的前提下，能夠簡化計(jì)算過程，并使得生成的決策樹的各個(gè)分支點(diǎn)更加合理。

關(guān)鍵詞：ID3算法;樣本結(jié)構(gòu)相似矩陣;向量相似度

中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-9699（2023）06-0009-07

20 世紀(jì)80 年代，Quinlan[1]提出了的ID3 算法，它是將信息增益作為非葉節(jié)點(diǎn)的標(biāo)準(zhǔn)，計(jì)算樣本數(shù)據(jù)庫的信息增益，選擇信息增益屬性值最大的作為分裂節(jié)點(diǎn)，進(jìn)行構(gòu)造決策樹。由于ID3算法構(gòu)建的決策樹結(jié)構(gòu)清晰直觀、易于理解，可以有效地降低數(shù)據(jù)噪聲，是一個(gè)很好的處理離散型數(shù)據(jù)的算法模型。但是ID3算法依舊存在著不可忽視的缺點(diǎn)：（a）多值偏向性。ID3算法計(jì)算信息增益時(shí)傾向于選擇信息熵最大的屬性值作為根節(jié)點(diǎn)，在數(shù)據(jù)量偏少或者噪點(diǎn)多的情況下，信息熵最大的并不是最優(yōu)的。（b）計(jì)算量大。在數(shù)據(jù)量很大的情況下，其計(jì)算量太大，并且存在一定的繁余計(jì)算，影響數(shù)據(jù)生成時(shí)間，效率不高[2-3]。

針對ID3算法以上不足，一些學(xué)者對此進(jìn)行了相關(guān)的改進(jìn)。文獻(xiàn)[4-5]將用戶興趣度引入信息熵的計(jì)算公式中來降低多值偏向的影響;文獻(xiàn)[6]引用權(quán)值進(jìn)行改進(jìn)信息增益公式來解決多值依賴問題;文獻(xiàn)[7]利用等價(jià)無窮小的性質(zhì)來加快信息增益的計(jì)算效率;文獻(xiàn)[8]運(yùn)用泰勒公式和麥克勞林公式，對ID3算法公式進(jìn)行了化簡。

文獻(xiàn)都在一定程度上解決了多值偏向的問題，但主觀性較強(qiáng)，會影響到客觀結(jié)果，文章通過構(gòu)造樣本結(jié)構(gòu)相似矩陣，引入向量相似度為其加入權(quán)重，從而避免多值偏向的問題，這樣有效地避免了人為主觀對數(shù)據(jù)的影響，同時(shí)也對ID3算法的信息增益計(jì)算進(jìn)行優(yōu)化，提高計(jì)算效率。

1 ID3算法

ID3算法是一種以信息熵和增益作為構(gòu)造決策樹節(jié)點(diǎn)屬性的學(xué)習(xí)算法。選擇信息增益最大的屬性作為分類屬性，從而構(gòu)造決策樹[1，9]。

“收入”為“低”的記錄有4條，之前已經(jīng)計(jì)算“收入”為“低”的熵H （S低）=0.295，接下來，根據(jù)相似結(jié)構(gòu)矩陣和優(yōu)化信息增益的中的計(jì)算方式，得到“收入”為“低”的條件下各描述屬性的優(yōu)化信息增益Gain'（A）：

Gain'（喜歡的季節(jié)）=0;

Gain'（是否商務(wù)人）=0.75;

Gain'（駕車水平）=0.5。

對比以上優(yōu)化信息增益值，描述屬性“喜歡的季節(jié)”具有最小的數(shù)值，因此選擇“喜歡的季節(jié)”作為“低”的葉子節(jié)點(diǎn)。以“喜歡的季節(jié)”的屬性值“春”“夏”“秋”和“冬”為分支節(jié)點(diǎn)的分類屬性，計(jì)算各描述屬性的條件熵及優(yōu)化信息增益，劃分出以屬性“收入”為“低”的決策樹分支。對于屬性“收入”為“中”的決策樹分支，按照以上規(guī)則，用遞歸的方法對其計(jì)算熵值并進(jìn)行分裂屬性的選擇，最終得到的基于樣本結(jié)構(gòu)向量相似度的ID3算法生成的決策樹，如圖2所示。

4.2.3 實(shí)例分析與總結(jié)

由圖1可知，將ID3算法的信息增益的計(jì)算公式進(jìn)行優(yōu)化化簡后，新生成的決策樹和原公式生成的決策樹完全一致。這表明化簡之后的公式，在提高了計(jì)算效率，簡化計(jì)算過程的基礎(chǔ)上并沒有對結(jié)果造成影響，保證了結(jié)果的可靠性。

根據(jù)圖1得出，因?yàn)槎嘀灯虻娜秉c(diǎn)使得“喜歡的季節(jié)”成為決策樹的第一個(gè)根節(jié)點(diǎn)，但數(shù)據(jù)表明這個(gè)因素并不能成為購車的決定性因素。反而是優(yōu)化過后的，如圖2所示，“收入”這一屬性更符合現(xiàn)實(shí)邏輯。由圖2可知，基于樣本結(jié)構(gòu)向量相似度的ID3算法在一定程度上克服了多值偏向問題，使得分類結(jié)果更加符合實(shí)際認(rèn)知。

5 結(jié)論

ID3算法是決策樹算法中的一種具有代表性的算法，文章利用樣本結(jié)構(gòu)相似度矩陣的概念，提出了一種基于樣本結(jié)構(gòu)向量相似度的ID3算法。樣本結(jié)構(gòu)向量相似度的優(yōu)點(diǎn)在于它不受屬性個(gè)數(shù)多少的影響，也不需要人為經(jīng)驗(yàn)判斷，可以反映出描述屬性和分類屬性之間的相似程度，即由描述屬性和分類屬性構(gòu)成的結(jié)構(gòu)相似矩陣，其兩個(gè)列向量在正空間中的夾角，反映了該描述屬性對決策的重要程度，夾角越大，兩向量越無關(guān)，也就是說該描述屬性能夠很好地對決策進(jìn)行分類，大大降低數(shù)據(jù)總體的信息熵，將其引入信息增益的計(jì)算，使得決策樹根節(jié)點(diǎn)的選擇更加合理。基于樣本結(jié)構(gòu)向量相似度的ID3算法使用客觀數(shù)據(jù)完成建模，得出向量相似度值，克服了ID3算法的多值偏向問題。而二階麥克勞林對公式的簡化，消除函數(shù)中復(fù)雜的對數(shù)運(yùn)算，提高算法執(zhí)行效率，沒有降低原本的精度，對后續(xù)的運(yùn)算結(jié)果并無影響，保證了結(jié)果的可靠性。

兩種改進(jìn)的結(jié)合，有效地解決了計(jì)算復(fù)雜，效率低的問題，也一定程度上克服了ID3算法的多值偏向問題。

參考文獻(xiàn)：

[1]Quinlan J R.Induction of decision trees[J].Machinelearning，1986，1：81-106.

[2]王利軍.決策樹ID3 算法的優(yōu)化[J].菏澤學(xué)院學(xué)報(bào)，2020，42（5）：15-19，30.

[3]于海平，朱玉全，陳耿，等.一種基于粗糙集理論的決策樹構(gòu)造方法[J].計(jì)算機(jī)應(yīng)用與軟件，2011，28（2）：80-82.

[4]王永梅，胡學(xué)鋼.基于用戶興趣度和MID3決策樹改進(jìn)方法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（27）：155-157.

[5]王睿，鐘守銘，楊景浩.關(guān)于用戶興趣度的判定樹算法的優(yōu)化[J].計(jì)算機(jī)與數(shù)字工程，2006，34（2）：24-25，35.

[6]韓松來，張輝，周華平.基于關(guān)聯(lián)度函數(shù)的決策樹分類算法[J].計(jì)算機(jī)應(yīng)用，2005，25（11）：2655-2657.

[7]黃愛輝，陳湘濤.決策樹ID3算法的改進(jìn)[J].計(jì)算機(jī)工程與科學(xué)，2009，31（6）：109-111.

[8]王苗.決策樹ID3算法的改進(jìn)研究[D].遼寧：遼寧工程技術(shù)大學(xué)，2011.

[9]Hssina B， Merbouha A， Ezzikouri H， et al.A comparativestudy of decision tree ID3 and C4.5[J].International Journal ofAdvanced Computer Science and Applications，2014，4（2）：13-19.

[10]Cha S-H， Yoon S， Tappert C C. Enhancing binaryfeature vector similarity measures [J].CSIS TechnicalReports，2005（210）：1-18.

[11]張睿.ID3決策樹算法分析與改進(jìn)[D].蘭州：蘭州大學(xué)，2010.

[12]Xia P， Zhang L， Li F. Learning similarity with cosinesimilarity ensemble[J].Information sciences，2015，307：39-52.

[13]陳文，余本功.一種基于多向量相似度的聚類分析方法研究[J].隴東學(xué)院學(xué)報(bào)，2023，34（2）：38-43.

[14]王秀慧，許彩欣.決策樹在貸款客戶信用評估中的應(yīng)用[J].現(xiàn)代計(jì)算機(jī)（專業(yè)版），2011（9）：20-22.

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

[16]孟雅蕾，周千明，師紅宇，等.基于改進(jìn)ID3算法的數(shù)據(jù)分類方法[J].計(jì)算機(jī)仿真，2022，39（5）：329-332，417.

責(zé)任編輯：肖祖銘