改進(jìn)的決策樹ID3算法及應(yīng)用

葛璐瑤

摘要 本文利用數(shù)據(jù)挖掘決策樹ID3算法，以校園一卡通數(shù)據(jù)庫(kù)中數(shù)據(jù)挖掘在高校貧困認(rèn)定領(lǐng)域的應(yīng)用為實(shí)例，通過對(duì)簡(jiǎn)單高效的ID3算法的改進(jìn)，先排除掉其他因素的影響，再構(gòu)建最優(yōu)決策樹，從而加強(qiáng)數(shù)據(jù)結(jié)果的可靠性。

【關(guān)鍵詞】ID3算法 構(gòu)建決策樹 數(shù)據(jù)挖掘恩格爾系數(shù)

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

1 決策樹ID3算法的描述

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

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

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

2 特征提取實(shí)例

電子支付平臺(tái)是面向在校師生提供的一系列電子支付服務(wù)的網(wǎng)絡(luò)平臺(tái)，在高校管理過程中，電子支付平臺(tái)會(huì)生成海量數(shù)據(jù)，這些數(shù)據(jù)含有潛在的意義，需要我們挖掘發(fā)現(xiàn)其中的隱含信息，以學(xué)生校園一卡通數(shù)據(jù)庫(kù)中的信息為例，我們可以選取其中學(xué)生校園卡充值交易額、校園卡使用次數(shù)最為數(shù)據(jù)源，經(jīng)過多次實(shí)驗(yàn)測(cè)試得到劃分標(biāo)準(zhǔn)，應(yīng)用于高校貧困學(xué)生認(rèn)定中。具體過程如下：

2.1 確定數(shù)據(jù)挖掘?qū)ο?/p>

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

2.2 生成決策樹

通過學(xué)生基本信息表，選擇“貧困判定結(jié)果”為劃分屬性，訓(xùn)練樣本含有7個(gè)“貧困”和5個(gè)“非貧困”，對(duì)應(yīng)于信息值Info（[7，5]）=- （7/12） log2 （7/12） - （5/12） log2（ 5/12） =0.98。

在評(píng)估“家庭收入水平”屬性時(shí)，對(duì)應(yīng)于“貧困”和“非貧困”類的個(gè)數(shù)分別為[4，1]、[2-2]、[2，1]，他們的信息值分別是：Info（[4，1]）=0.72， Info（[2，2]）=l，Info（[2，1]）=0 92，那么“家庭收入水平”相對(duì)于“貧困判定結(jié)果”的信息值為：

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

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

由上述計(jì)算得“學(xué)生生活費(fèi)用總額”信息增益值最大，因此選擇“學(xué)生生活費(fèi)用總額”為決策樹根節(jié)點(diǎn)的劃分屬性，創(chuàng)建如圖l所示決策樹。

2.3 改進(jìn)ID3算法

2.3.1 恩格爾系數(shù)

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

恩格爾系數(shù)A=食物支出金額/總支出金額

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

改進(jìn)的恩格爾系數(shù)五=校園卡充值金/學(xué)生生活費(fèi)用總額

從公式不難看出，系數(shù)越小，說明學(xué)生越富裕，貧困程度當(dāng)然越小。

2.3.2 添加判定系數(shù)的判定方案

因此在利用決策樹ID3算法判定學(xué)生貧困程度時(shí)，可以加入恩格爾系數(shù)，給定一個(gè)貧困程度的標(biāo)準(zhǔn)值五，計(jì)算每個(gè)申請(qǐng)貧困的學(xué)生的改進(jìn)恩格爾系數(shù)A_i.。

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

若A_i>A，則初步判定貧困，構(gòu)建決策樹，確認(rèn)最終結(jié)果。

3 結(jié)束語

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

參考文獻(xiàn)

[1]嚴(yán)坤.數(shù)據(jù)挖掘技術(shù)研究[J].電腦迷，2017 （10）：185.

[2]光峰，姚程寬，盧燦舉，曹立勇，詹喆.數(shù)據(jù)挖掘經(jīng)典算法研究[J]，商丘師范學(xué)院學(xué)報(bào)，2016，32 （03）： 44-47.

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

[4]楊洋.決策樹ID3算法及其改進(jìn)[J].軟件導(dǎo)刊，2016 （08）： 46-48.

[5]田麗，智慧校園環(huán)境下的校園一卡通建設(shè)[J].華東師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2015 （Sl）：530-535.

[6]劉星，恩格爾系數(shù)、基尼系數(shù)與經(jīng)濟(jì)增長(zhǎng)關(guān)系研究[J].統(tǒng)計(jì)與決策，2014 （02）： 87- 89.