基于樣本結構向量相似度的ID3算法改進

陳全園 侯帥琳 李雅琪

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

關鍵詞：ID3算法;樣本結構相似矩陣;向量相似度

中圖分類號：TP301.6 文獻標識碼：A 文章編號：2095-9699（2023）06-0009-07

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

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

文獻都在一定程度上解決了多值偏向的問題，但主觀性較強，會影響到客觀結果，文章通過構造樣本結構相似矩陣，引入向量相似度為其加入權重，從而避免多值偏向的問題，這樣有效地避免了人為主觀對數據的影響，同時也對ID3算法的信息增益計算進行優化，提高計算效率。

1 ID3算法

ID3算法是一種以信息熵和增益作為構造決策樹節點屬性的學習算法。選擇信息增益最大的屬性作為分類屬性，從而構造決策樹[1，9]。

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

Gain'（喜歡的季節）=0;

Gain'（是否商務人）=0.75;

Gain'（駕車水平）=0.5。

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

4.2.3 實例分析與總結

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

根據圖1得出，因為多值偏向的缺點使得“喜歡的季節”成為決策樹的第一個根節點，但數據表明這個因素并不能成為購車的決定性因素。反而是優化過后的，如圖2所示，“收入”這一屬性更符合現實邏輯。由圖2可知，基于樣本結構向量相似度的ID3算法在一定程度上克服了多值偏向問題，使得分類結果更加符合實際認知。

5 結論

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

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

參考文獻：

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

[2]王利軍.決策樹ID3 算法的優化[J].菏澤學院學報，2020，42（5）：15-19，30.

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

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

[5]王睿，鐘守銘，楊景浩.關于用戶興趣度的判定樹算法的優化[J].計算機與數字工程，2006，34（2）：24-25，35.

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

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

[8]王苗.決策樹ID3算法的改進研究[D].遼寧：遼寧工程技術大學，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決策樹算法分析與改進[D].蘭州：蘭州大學，2010.

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

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

[14]王秀慧，許彩欣.決策樹在貸款客戶信用評估中的應用[J].現代計算機（專業版），2011（9）：20-22.

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

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

責任編輯：肖祖銘