◆曹安林

?

基于ID3算法的質(zhì)量保證體系數(shù)據(jù)關(guān)聯(lián)度研究

◆曹安林

（南京機(jī)電職業(yè)技術(shù)學(xué)院 江蘇 211135）

高等職業(yè)院校建立質(zhì)量保證體系是社會(huì)主義市場(chǎng)經(jīng)濟(jì)發(fā)展的需求，是區(qū)域經(jīng)濟(jì)發(fā)展和行業(yè)企業(yè)發(fā)展總趨勢(shì)。為社會(huì)培育大量高素質(zhì)應(yīng)用型技能人才是高等職業(yè)院校最基本的人才培養(yǎng)方案和目標(biāo)。目前，基于網(wǎng)絡(luò)的綜合教學(xué)管理信息系統(tǒng)得到了各高等職業(yè)院校的廣泛應(yīng)用，在這些管理信息系統(tǒng)的使用過(guò)程中，積累了大量的原始數(shù)據(jù)，然而這些數(shù)據(jù)只是靜態(tài)的儲(chǔ)存在數(shù)據(jù)庫(kù)中，沒(méi)有進(jìn)行深層次的分析并有效利用，不能不說(shuō)是一種浪費(fèi)。如何從這些原始數(shù)據(jù)中發(fā)現(xiàn)并提煉出有用的信息，精準(zhǔn)的對(duì)數(shù)據(jù)進(jìn)行分析，并將分析結(jié)果加工成有效的信息供管理層決策使用，已經(jīng)成為了高職院校質(zhì)量管理與控制體系的應(yīng)用需求。

ID3算法；質(zhì)量保證；數(shù)據(jù)關(guān)聯(lián)

0 前言

目前，基于網(wǎng)絡(luò)的綜合教學(xué)管理信息系統(tǒng)越來(lái)越廣泛的應(yīng)用在高職院校，系統(tǒng)中數(shù)據(jù)基本涵蓋了《高等職業(yè)學(xué)校設(shè)置標(biāo)準(zhǔn)（暫行）》（教發(fā)〔2000〕41號(hào)）規(guī)定的所有辦學(xué)指標(biāo)。單純就某一所高職院校來(lái)說(shuō)，利用人工計(jì)算和比對(duì)的方式核準(zhǔn)辦學(xué)指標(biāo)相對(duì)容易，一旦數(shù)據(jù)中包含了大量院校信息時(shí)，人工方式將很難保證準(zhǔn)確性和完整性。因此本文以南京機(jī)電職業(yè)技術(shù)學(xué)院為案例，將數(shù)據(jù)挖掘技術(shù)的ID3算法歸納決策樹(shù)擴(kuò)展到建立高職院校的質(zhì)量管理與控制體系，達(dá)到應(yīng)用創(chuàng)新的目的。主要研究?jī)?nèi)容如下：

1 科學(xué)的對(duì)基本數(shù)據(jù)庫(kù)中數(shù)據(jù)進(jìn)行預(yù)處理

如何對(duì)基本數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行預(yù)處理，主要采用決策樹(shù)的算法分析。決策樹(shù)是數(shù)據(jù)挖掘分類(lèi)算法的一個(gè)重要方法，是在已知各種情況發(fā)生概率的基礎(chǔ)上，通過(guò)構(gòu)成決策樹(shù)來(lái)求取凈現(xiàn)值的期望值大于等于零的概率，評(píng)價(jià)項(xiàng)目風(fēng)險(xiǎn)，判斷其可行性的決策分析方法，是直觀運(yùn)用概率分析的一種圖解法。

生成決策樹(shù)是采用自上而下的遞歸構(gòu)造方法。它的輸入是一組帶有類(lèi)別標(biāo)記的訓(xùn)練數(shù)據(jù)集合，結(jié)果是一棵二叉樹(shù)或多叉樹(shù)。決策樹(shù)如果依靠數(shù)學(xué)的計(jì)算方法可以取得相對(duì)更加理想的效果。例如：

決策樹(shù)的生成過(guò)程主要是依據(jù)對(duì)于數(shù)據(jù)源的采集分析，對(duì)數(shù)據(jù)源進(jìn)行分類(lèi)測(cè)試，在整個(gè)過(guò)程中進(jìn)行單一方向的或者是多個(gè)類(lèi)別的測(cè)試和修剪，當(dāng)一個(gè)數(shù)據(jù)決策樹(shù)不能再進(jìn)一步分割或修剪的時(shí)候，對(duì)于數(shù)據(jù)來(lái)說(shuō)整個(gè)生成過(guò)程也就完成了，也達(dá)到了基本數(shù)據(jù)預(yù)處理的目標(biāo)。

2 ID3算法下的決策樹(shù)的剪枝

通常在實(shí)際應(yīng)用中，直接生成的決策樹(shù)并不能立即用于對(duì)未知樣本來(lái)進(jìn)行分類(lèi)和應(yīng)用。由于訓(xùn)練數(shù)據(jù)集合存在噪聲，無(wú)法實(shí)現(xiàn)對(duì)新樣本的合理分析，這種條件下，必須要對(duì)決策樹(shù)進(jìn)行后期處理——即決策樹(shù)的剪枝處理。這樣才能有效的控制和掌握決策樹(shù)的發(fā)展規(guī)模，進(jìn)而提高預(yù)測(cè)精度，同時(shí)也變得更容易理解。

當(dāng)系統(tǒng)的信息熵降為0時(shí)，就沒(méi)有必要再往下構(gòu)造決策樹(shù)了，此時(shí)葉節(jié)點(diǎn)都是純的——這是理想情況。最壞的情況下，決策樹(shù)的高度為屬性（決策變量）的個(gè)數(shù)，葉節(jié)點(diǎn)不純（這意味著我們要以一定的概率來(lái)做出決策）。

高職院校的質(zhì)量管理與控制體系數(shù)據(jù)覆蓋面比較廣，包含種類(lèi)較多，然其中大部分?jǐn)?shù)據(jù)指標(biāo)以定性屬性為主，即離散型訓(xùn)練數(shù)據(jù)集合為主，計(jì)算量相對(duì)來(lái)說(shuō)并不是很大。選用ID3算法歸納決策樹(shù)方法用于質(zhì)量保證體系數(shù)據(jù)挖掘系統(tǒng)是較為合適的算法。

3 基于ID3算法的質(zhì)量保證數(shù)據(jù)關(guān)聯(lián)分析

ID3采用自頂向下不回溯的策略搜索全部的屬性空間，它建立決策樹(shù)的算法簡(jiǎn)單，深度小，分類(lèi)速度快，相對(duì)適宜計(jì)算量較小的培訓(xùn)數(shù)據(jù)集合。其關(guān)鍵在于選取“各個(gè)決策屬性中可對(duì)訓(xùn)練數(shù)據(jù)集合進(jìn)行最佳分類(lèi)的屬性”，自上而下的歸納成一組if_then規(guī)則，所以計(jì)算各個(gè)決策屬性的信息增益并加以比較是ID3算法的關(guān)鍵步驟。其基本算法如下偽代碼描述：

Define：Decision_Tree（samples，attribute_list）；

Input：具有離散型屬性的訓(xùn)練數(shù)據(jù)集合samples、決策屬性集合attribute_list

Output：一棵決策樹(shù)。

Function：

（1）創(chuàng)建根節(jié)點(diǎn)N；

（2）if samples同為類(lèi)C then；

（3）return N作為葉節(jié)點(diǎn)，以C標(biāo)記；

（4）if attribute_list = null then;

（5）return N作為葉節(jié)點(diǎn)，標(biāo)記為samples中最普通的類(lèi)；

（6）選擇attribute_list中具有最大信息增益的決策樹(shù)性test_attribute；

（7）標(biāo)記N為test_attribute；

（8）switch case each test_attribute中已知的值；

（9）節(jié)點(diǎn)N生長(zhǎng)出一個(gè)條件為test_attribute的分支；

（10）設(shè)置Si為samples中test_attribute=Ai樣本的集合；

（11）if Si=null then；

（12）生成一個(gè)葉節(jié)點(diǎn)，標(biāo)記為samples中最普通的類(lèi)；

（13）else加入由Decision_Tree（Si，test_attribute）返回的節(jié)點(diǎn)。ID3通過(guò)不斷的遞歸方式，逐步精確決策樹(shù)，直到找到一棵完全正確的決策樹(shù)。

其數(shù)學(xué)理論依據(jù)：

（5）信息增益度是兩個(gè)信息量之間的差值，其中一個(gè)信息量是需確定T的一個(gè)元素的信息量，另一個(gè)信息量是在已得到的屬性X的值后需確定的T一個(gè)元素的信息量，信息增益度公式為：

出來(lái)的分支。根據(jù)有A劃分成子集的熵為：

分類(lèi)后，分類(lèi)的信息量計(jì)算公式為：

其中：

綜上所述，信息增益為：

根據(jù)貪心算法，為使下一步所需的信息量最小，則要求每一次都選擇信息增益最大的屬性作為決策樹(shù)的新節(jié)點(diǎn)。

下面，通過(guò)一個(gè)具體實(shí)例來(lái)說(shuō)明其具體應(yīng)用過(guò)程。學(xué)校部分專(zhuān)任教師信息數(shù)據(jù)：

表1 專(zhuān)任教師信息表

選取部分專(zhuān)任教師職稱(chēng)作為類(lèi)別標(biāo)識(shí)屬性，其他屬性為決策屬性，圖1是一棵關(guān)于“專(zhuān)任職教師是否具有高級(jí)職稱(chēng)”的決策樹(shù)的子樹(shù)示意圖：

圖1“專(zhuān)任教師是否具有高級(jí)職稱(chēng)”決策樹(shù)示意圖

設(shè)訓(xùn)練數(shù)據(jù)集合S，S中共有14條記錄，其中職稱(chēng)分為初級(jí)、中級(jí)、高級(jí)（含副高級(jí)）三種，決策屬性數(shù)據(jù)量相對(duì)較為平均，所以套用公式3計(jì)算S的期望信息量：

接下來(lái)根據(jù)公式9計(jì)算每個(gè)一個(gè)決策屬性的信息量，也就是熵，以年齡為例，將年齡分為30～40之間、40～50之間、50以上三個(gè)區(qū)間，當(dāng)年齡為30～40之間時(shí)：

當(dāng)年齡為40～50之間時(shí)：

當(dāng)年齡為50以上時(shí)：

由此得到年齡的熵為：

所以根據(jù)公式11年齡的信息增益G（Age）為：

同理可得性別信息增益G（Sex）=0.0266、學(xué)歷信息增益G（Education）=0.4926，當(dāng)訓(xùn)練數(shù)據(jù)集合擴(kuò)大到全校400名教職、教輔員工時(shí)得到的性別信息增益G（Sex）為0.0054，而對(duì)于其他的決策屬性大小次序未發(fā)生改變，由此可以看出性別對(duì)于教師的職稱(chēng)屬性幾乎不存在影響，所以在對(duì)圖1所示的決策樹(shù)中刪除性別決策屬性，因?yàn)镚（Age）值最大，所以選擇年齡作為決策樹(shù)的根節(jié)點(diǎn)，對(duì)每一個(gè)分支進(jìn)行遞歸計(jì)算，進(jìn)行剪枝，剪枝后的決策樹(shù)如圖2所示：

4 總結(jié)

利用ID3算法對(duì)高等職業(yè)院校的教育教學(xué)進(jìn)行質(zhì)量的管控分析，并不是提出改進(jìn)算法為目的。因此如何通過(guò)ID3算法構(gòu)造一棵最簡(jiǎn)決策樹(shù)是整個(gè)項(xiàng)目中最核心的部門(mén)，同時(shí)決策樹(shù)的剪枝問(wèn)題是決策樹(shù)技術(shù)中一個(gè)重要的部分。ID3算法能利用直觀的算法描述、數(shù)學(xué)描述ID3在構(gòu)造決策樹(shù)以及剪枝的詳細(xì)過(guò)程，同時(shí)結(jié)合案例進(jìn)行實(shí)例化操作，對(duì)建立學(xué)院質(zhì)量保證體系關(guān)鍵數(shù)據(jù)的確立起到很大的指引作用。

圖2 對(duì)決策屬性Sex剪枝后的決策樹(shù)示意圖

[1]李榮俠.高職院校教學(xué)質(zhì)量監(jiān)控與評(píng)價(jià)體系研究[D].南京理工大學(xué)碩士學(xué)位論文，2007.

[2]彭慧伶，劉發(fā)升.關(guān)聯(lián)規(guī)則挖掘與分類(lèi)規(guī)則挖掘的比較研究[J].計(jì)算機(jī)與現(xiàn)代化.2006.

[3]張保華.數(shù)據(jù)挖掘現(xiàn)狀及常規(guī)分類(lèi)算法[J].科技創(chuàng)新導(dǎo)報(bào)，2008.

[4]季桂樹(shù)，決策樹(shù)分類(lèi)算法研究綜述[J]科技廣場(chǎng)，2007.

本文系江蘇省高校哲學(xué)社會(huì)科學(xué)研究基金（專(zhuān)題）項(xiàng)目-基于數(shù)據(jù)挖掘高職院校質(zhì)量保證體系的研究 （2017SJB0708） 項(xiàng)目負(fù)責(zé)人：曹安林。