決策樹(shù)ID3算法在高校管理信息化中的應(yīng)用分析

　　摘 要： ID3算法是決策樹(shù)算法中最經(jīng)典的一個(gè)算法。本文根據(jù)高校管理信息化的特殊性將模糊集理論知識(shí)與ID3算法相結(jié)合，應(yīng)用到高校管理中，提高了ID3決策樹(shù)分類(lèi)的正確性，與ID3原算法相比，易于理解，決策樹(shù)的構(gòu)造更加準(zhǔn)確和快速。
　　關(guān)鍵詞： 決策樹(shù) ID3 模糊集 高校信息化 應(yīng)用
　　
　　1.引言
　　自20世紀(jì)60年代以來(lái)，決策樹(shù)方法在機(jī)器學(xué)習(xí)、知識(shí)發(fā)現(xiàn)等諸多領(lǐng)域有著廣泛應(yīng)用。J.R.Quinlan in在1979年提出的ID3決策樹(shù)算法是最有影響的一種決策樹(shù)生成算法，其思想是運(yùn)用信息熵理論，選擇當(dāng)前樣本集中具有最大信息增益值的屬性作為測(cè)試屬性，樣本集的劃分則依據(jù)測(cè)試屬性的取值進(jìn)行，測(cè)試屬性有多少不同取值，就將樣本集劃分為多少子樣本集。用迭代的方法在相應(yīng)的樣本子集的節(jié)點(diǎn)上生長(zhǎng)出新的葉子節(jié)點(diǎn)，直到無(wú)可分樣本，無(wú)剩余屬性或樣本同屬于一個(gè)類(lèi)時(shí)結(jié)束。但此方法的決策樹(shù)的知識(shí)表示沒(méi)有規(guī)則易于理解。而且ID3算法信息增益的方法往往偏向于選擇取值較多的屬性，影響的分類(lèi)預(yù)測(cè)的高效性。因此，我們對(duì)原有的ID3算法進(jìn)行了改進(jìn)，將模糊理論知識(shí)應(yīng)用到ID3算法之中，提出一個(gè)新的從數(shù)值數(shù)據(jù)中生成一個(gè)決策樹(shù)狀圖的算法。
　　我在此以某高校學(xué)生課程信息系統(tǒng)為基礎(chǔ)，對(duì)其中積累的海量數(shù)據(jù)運(yùn)用數(shù)據(jù)挖掘技術(shù)，實(shí)現(xiàn)挖掘算法——決策樹(shù)ID3改進(jìn)算法，并抽取規(guī)則知識(shí)，對(duì)高校中的學(xué)生的成績(jī)進(jìn)行了深入的分析和比較，找出影響學(xué)生學(xué)習(xí)的潛在因素和潛在有用價(jià)值，為教學(xué)管理和保持學(xué)生良好狀態(tài)，提高學(xué)生成績(jī)，促進(jìn)學(xué)生全面發(fā)展提供參考，從而可以更好地開(kāi)展學(xué)生工作，提高教學(xué)質(zhì)量，促進(jìn)學(xué)校發(fā)展。
　　2.ID3決策樹(shù)算法
　　ID3決策樹(shù)算法的核心思想是利用信息熵原理選擇信息增益最大的屬性為屬性分類(lèi)的標(biāo)準(zhǔn)，使用貪心算法遞歸地拓展決策樹(shù)的分枝，進(jìn)行決策樹(shù)的構(gòu)造［３］。
　　假設(shè)數(shù)據(jù)集空間中的正例集和反例集的大小分別為p和n，ID3算法基于以下兩個(gè)基本假設(shè)：
　　（1）在數(shù)據(jù)集空間H上的一棵正確決策樹(shù)對(duì)任意測(cè)試數(shù)據(jù)的分類(lèi)概率同H中正反例的概率一致；
　　（2）一棵決策樹(shù)能對(duì)測(cè)試集做出正確類(lèi)別判斷所需的信息量為：
　　I（p，n）=-ln-ln
　　如果以屬性R作為決策樹(shù)的根，R具有V個(gè)值（V，V，…，V），它將H分為V個(gè)子集（H，H，…，H），假設(shè)H中含有p個(gè)正例和n個(gè)反例，子集H的信息熵E（H）為：
　　E（H）=-ln-ln
　　以屬性R為根分類(lèi)的信息熵為E（R）：
　　Gain（R）=I（p，n）-E（R）
　　ID3選擇使E（R）最小的屬性作為根節(jié)點(diǎn)，對(duì)R的不同取值對(duì)應(yīng)的H的V個(gè)子集H遞歸調(diào)用上述過(guò)程，生成R的子節(jié)點(diǎn)。
　　判定樹(shù)歸納的基本算法是貪心算法，它采用自上而下、分而治之的遞歸方式來(lái)構(gòu)造一個(gè)決策樹(shù)。ID3算法是一種著名的判定樹(shù)歸納算法。
　　3.模糊ID3決策樹(shù)算法
　　ID3算法根據(jù)數(shù)據(jù)集的屬性生成一棵決策樹(shù)狀圖來(lái)進(jìn)行數(shù)據(jù)的分類(lèi)，我們的算法稱(chēng)為模糊ID3算法，應(yīng)用了數(shù)據(jù)模糊集來(lái)生成一棵模糊決策樹(shù)，模糊數(shù)據(jù)集是由用戶(hù)為所有屬性定義的模糊集。一棵模糊決策樹(shù)狀圖包括測(cè)試值的節(jié)點(diǎn)，
　　由用戶(hù)定義模糊集的測(cè)試值分支的邊緣和決定等級(jí)名稱(chēng)必然性的葉片。
　　我們的算法與ID3算法非常相似，但I(xiàn)D3算法基于信息增益來(lái)選擇測(cè)試屬性，
　　若我們有一組數(shù)據(jù)D，每個(gè)數(shù)據(jù)有各個(gè)屬性數(shù)值A(chǔ)，A，…，A和一個(gè)分類(lèi)的C={C，C，…，C}與屬性A的模糊集。D為類(lèi)C上一個(gè)模糊子集，|D|表示數(shù)據(jù)D模糊集的所有屬性成員值的之和。則生成模糊決策樹(shù)圖的算法如下：
　　（1）生成具有所有數(shù)據(jù)集的根節(jié)點(diǎn)，和所有屬性的數(shù)據(jù)模糊集。
　　（2）如果一個(gè)數(shù)據(jù)的模糊集的節(jié)點(diǎn)滿(mǎn)足如下條件：
　　①C的數(shù)據(jù)集的比例大于或等于閾值，≥θ；
　　②數(shù)據(jù)集的數(shù)目少于閾值，|D|＜θ；
　　③沒(méi)有屬性值進(jìn)行分類(lèi)。
　　然后它就是一個(gè)葉節(jié)點(diǎn)，并用類(lèi)名分配。
　　（3）若不滿(mǎn)足上述條件，那就不是一個(gè)葉片并且測(cè)試節(jié)點(diǎn)生成如下：
　　對(duì)于A計(jì)算出Gain（A，D），并且選擇測(cè)試屬性的A來(lái)使之最大化；
　　根據(jù)A把D分成模糊子集，D數(shù)據(jù)信息值就是產(chǎn)生D信息值和A的F；
　　為模糊子集生成新的節(jié)點(diǎn)并且把模糊集列為節(jié)點(diǎn)之間聯(lián)系的邊緣；
　　用D（j=1，2，…，m）代替D并且重復(fù)步驟2。
　　其中，Gain（A，D）=I（D）-E（A，D），E（A，D）=（p?I（D）），P=p=
　　算法結(jié)束。
　　4.分析決策樹(shù)的構(gòu)造及比較
　　本部分以某職業(yè)技術(shù)學(xué)校2010級(jí)所開(kāi)課程成績(jī)作為測(cè)試數(shù)據(jù)。表1是經(jīng)過(guò)數(shù)據(jù)清理后的學(xué)生考試成績(jī)情況信息的訓(xùn)練集。
　　使用模糊ID3算法，最終得出決策樹(shù)如圖2所示。
　　從根到樹(shù)葉每條路徑創(chuàng)建一個(gè)規(guī)則，可以很清楚地看出“不是重修、是必修課、試卷難度中等、成績(jī)是中等的記錄，而且該種記錄占了所有記錄一半以上”等分類(lèi)知識(shí)。此外研究修正后的決策樹(shù)，我們可以很清晰地看到每個(gè)課程類(lèi)型分類(lèi)的關(guān)鍵，以及把研究問(wèn)題通過(guò)量化體現(xiàn)。這些知識(shí)對(duì)于決策是有幫助的，如可對(duì)課程類(lèi)型I的學(xué)生加強(qiáng)專(zhuān)項(xiàng)題和綜合題的訓(xùn)練，提高學(xué)生解題能力。而在選修課的重點(diǎn)分配方面，要加大學(xué)生對(duì)此門(mén)功課的相對(duì)分配時(shí)間和動(dòng)手能力培養(yǎng)。
　　5.結(jié)語(yǔ)
　　改進(jìn)的ID3算法充分運(yùn)用了信息論在決策樹(shù)分類(lèi)中的優(yōu)越性，結(jié)合模糊集合知識(shí)把原有的ID3決策樹(shù)狀圖改進(jìn)為一個(gè)可理解的模糊決策樹(shù)狀圖來(lái)解決分類(lèi)問(wèn)題。我們提出一個(gè)新的從數(shù)值數(shù)據(jù)中生成一個(gè)決策樹(shù)狀圖的新的算法，通過(guò)使用模糊集。最后，我們將其應(yīng)用于高職院校信息管理系統(tǒng)中，對(duì)學(xué)生成績(jī)和選課之間進(jìn)行分析，找出了影響學(xué)生成績(jī)的關(guān)鍵因素，為學(xué)生培養(yǎng)提供了參考依據(jù)。
　　參考文獻(xiàn)：
　　［1］Inmon W H，Hackathorn R.Using the Data Warehouse.John Wiley &Sons，1994.
　　［2］Inmon W H.Building the Data Warehouse.QED Technical Publishing Group.
　　［3］Vipin Kumar，Mahesh V.Joshi，Eui-Hong Sam Han，et al HighPerformance Data Mining［M］.Lecture Notes in Computer Science 2003.8：63-88.
　　［4］毛國(guó)君，段立娟，王實(shí)，石云.數(shù)據(jù)挖掘原理與算法［M］.北京:清華大學(xué)出版社，2005：64-105.
　　［5］戴永群.數(shù)據(jù)挖掘在教學(xué)中的應(yīng)用［J］.福建電腦，2005.9.
　　［6］張震.數(shù)據(jù)挖掘技術(shù)分析及其在高校管理決策中的決策［J］.遠(yuǎn)程教育雜志，2005，6（171）.
　　［7］鄧廷等.高校科研決策支持系統(tǒng)中關(guān)聯(lián)規(guī)則挖掘的應(yīng)用［J］.沈陽(yáng)師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2004.1，VOL22，（1）.
　　［8］谷文祥，殷明浩.數(shù)據(jù)挖掘中決策樹(shù)加權(quán)模糊嫡算法［J］.計(jì)算技術(shù)與自動(dòng)化，2002，（03）.