改進的決策樹ID3算法及應用

葛璐瑤

摘要 本文利用數據挖掘決策樹ID3算法，以校園一卡通數據庫中數據挖掘在高校貧困認定領域的應用為實例，通過對簡單高效的ID3算法的改進，先排除掉其他因素的影響，再構建最優決策樹，從而加強數據結果的可靠性。

【關鍵詞】ID3算法 構建決策樹 數據挖掘恩格爾系數

數據挖掘即在海量數據中通過特殊算法，從而挖掘出有效的、先前未知的信息，利用數據庫、人工智能和數理統計等多方面的技術，是一類深層次的數據分析方法。常用的數據挖掘算法有很多，譬如CART分類算法、NaIveBayes樸素貝葉斯算法、EM最大期望算法等，不同的算法在數據挖掘領域用處也不盡相同。針對高校管理過程中生成的海量數據，可以對其挖掘利用，典型的即提取利用學生校園一卡通中的交易數據，對比分類，應用于高校貧困評定中。眾所周知，高校在校生絕大部分的消費均在校園內完成，而隨著數字化校園的構建，校園一卡通己成為高校內部消費購物的唯一途徑，因此校園一卡通的充值金額、刷卡次數等可以在很大程度上衡量一個學生的消費水準，從而判定其財富程度。本文提出用決策樹ID3算法處理校園一卡通中數據，但ID3算法仍存在許多弊端，因此提出采用改進的決策樹ID3算法。

1 決策樹ID3算法的描述

決策樹ID3算法，它是一種通過對一個訓練樣集Es遞歸構造決策樹的算法，在這個訓練樣集里選擇一個屬性劃分類別，Es屬性的取值為Cl、C2、C3…Cn概率值值為Pl、P2、P3 …Pn，定義一個函數稱作信息值或熵：

Info（[Cl、C2".Cn]）=Entropy （Pl、P2--Pn）= - Pllog2Pl- P21092P2-"'Pnlog2Pn，若使用另一個樣集里的屬性M對樣集Es分組，那么新的信息值，定義為：

Entropy （Es， M）=∑，（IEsi/Esl）Entropy （Es），M相對于Es的信息增益Gam（Es，M）定義為：Gain （Es，M）= Entropy（Es） - Entropy （Es，M），且信息增益越大，訓練樣集越容易實現簡單分類。雖然利用上述的ID3算法可以很簡單方便生成一棵決策樹，但是使用ID3算法仍然存在許多問題，最典型問題即ID3算法只針對于當前屬性值取最優分類，忽略全局其他因素[4]，所以需要對ID3算法進行進一步的改進，既要利用ID3算法的簡單方便與直接，又要從長遠考慮，綜合其他因素生成最優決策樹。因此，在原ID3算法的基礎上加以改進，即判斷最優分類屬性時不僅考慮各個屬性的信息增益，同時考慮其他干擾影響因素。

2 特征提取實例

電子支付平臺是面向在校師生提供的一系列電子支付服務的網絡平臺，在高校管理過程中，電子支付平臺會生成海量數據，這些數據含有潛在的意義，需要我們挖掘發現其中的隱含信息，以學生校園一卡通數據庫中的信息為例，我們可以選取其中學生校園卡充值交易額、校園卡使用次數最為數據源，經過多次實驗測試得到劃分標準，應用于高校貧困學生認定中。具體過程如下：

2.1 確定數據挖掘對象

為了更好的認定學生貧困程度，不僅調取學生的校園一卡通交易數據，同時走訪調查各個學生的附加信息，如家庭收入水平、學生每月生活費用等，表1為部分學生的每個月的基本信息，包括學生的家庭收入水平、學生生活費用總額、校園卡充值金額、校園卡交易次數、貧困判定結果，這些基本信息是高校貧困認定中有著重要意義的數據信息，在此信息的基礎上，利用數據挖掘中決策樹ID3算法，生成一棵簡易決策樹。

2.2 生成決策樹

通過學生基本信息表，選擇“貧困判定結果”為劃分屬性，訓練樣本含有7個“貧困”和5個“非貧困”，對應于信息值Info（[7，5]）=- （7/12） log2 （7/12） - （5/12） log2（ 5/12） =0.98。

在評估“家庭收入水平”屬性時，對應于“貧困”和“非貧困”類的個數分別為[4，1]、[2-2]、[2，1]，他們的信息值分別是：Info（[4，1]）=0.72， Info（[2，2]）=l，Info（[2，1]）=0 92，那么“家庭收入水平”相對于“貧困判定結果”的信息值為：

Info（[4，1]，[2，2]，[2，1]）=（5/12）Info（[4，1]）+（4/12）1nfo（[2，2]）+（3/12）Info（[2，1]）=0.86，那么“家庭收入水平”相對于“貧困判定結果”的信息增益為：

Gain（家庭收入水平）=Info（[7，5]）-Info（[4，1]，[2，2][2，1]）=O.l2，同理可以求出其他屬性的信息增益：Gain（學生生活費用總額）=0.41，Gam（校園卡充值金額）=0.06，Gain（校園卡交易次數）=0.30

由上述計算得“學生生活費用總額”信息增益值最大，因此選擇“學生生活費用總額”為決策樹根節點的劃分屬性，創建如圖l所示決策樹。

2.3 改進ID3算法

2.3.1 恩格爾系數

恩格爾系數（Engel's Coefficient）指居民家庭中食物支出占消費總支出的比重，恩格爾系數是用來衡量家庭富足程度的重要指標。

恩格爾系數A=食物支出金額/總支出金額

本文利用恩格爾系數的作用，在判定貧困程度過程中可以把校園一卡通的充值金額認定為食物支出金額，把學生生活費用認定為總支出金額，利用下式：

改進的恩格爾系數五=校園卡充值金/學生生活費用總額

從公式不難看出，系數越小，說明學生越富裕，貧困程度當然越小。

2.3.2 添加判定系數的判定方案

因此在利用決策樹ID3算法判定學生貧困程度時，可以加入恩格爾系數，給定一個貧困程度的標準值五，計算每個申請貧困的學生的改進恩格爾系數A_i.。

若A_i≤A，則非貧困，不予考慮

若A_i>A，則初步判定貧困，構建決策樹，確認最終結果。

3 結束語

雖然本文利用改進的ID3算法對學生貧困程度認定過程增加了限制條件，使判定過程更可靠，但是貧困認定并非一成不變，在認定過程中，每個學生的實際情況可能有所不同，認定選項也不是絕對有效的，因此上述算法的提出只能起到輔助性作用，真正的判定還需要結合更多方面，因此，在判定過程中仍然需要添加更多因素及條件，從而使判定結果更加有效可靠。

參考文獻

[1]嚴坤.數據挖掘技術研究[J].電腦迷，2017 （10）：185.

[2]光峰，姚程寬，盧燦舉，曹立勇，詹喆.數據挖掘經典算法研究[J]，商丘師范學院學報，2016，32 （03）： 44-47.

[3]李會，胡笑梅，決策樹中ID3算法與C4.5算法分析與比較[J].水電能源科學，2008 （02）：129-132+163.

[4]楊洋.決策樹ID3算法及其改進[J].軟件導刊，2016 （08）： 46-48.

[5]田麗，智慧校園環境下的校園一卡通建設[J].華東師范大學學報（自然科學版），2015 （Sl）：530-535.

[6]劉星，恩格爾系數、基尼系數與經濟增長關系研究[J].統計與決策，2014 （02）： 87- 89.