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