李 志

(中國人民警察大學，河北 廊坊 065000)

0 引言

隨著信息技術(shù)的迅速發(fā)展和互聯(lián)網(wǎng)技術(shù)的廣泛應用，移動互聯(lián)、大數(shù)據(jù)、云計算等新技術(shù)迅速崛起并逐步融入人們的學習、生活和工作。近年來，微課、慕課、私播課、翻轉(zhuǎn)課堂、雨課堂等新的教學形式迅速興起，掀起了高校在線教育改革的新浪潮。

目前，各高校均已開設(shè)計算機類公共基礎(chǔ)課程，對該課程的重視程度越來越高。由于全國各地經(jīng)濟文化發(fā)展還很不平衡，城鄉(xiāng)教育存在不容忽視的差距，對信息技術(shù)課程的重視程度不一，致使高校新生的計算機水平參差不齊。學生之間的個體差異，為計算機教學帶來很大困難，各高校對計算機分級教學的呼聲越來越高，國內(nèi)許多高校也陸續(xù)對計算機分級教學進行了有益嘗試。然而，由于傳統(tǒng)教學形式的限制，課上授課、討論，課下練習等一系列學習過程依然需要遵循教師的時間安排進行，無法把時間和學習的自主性真正交還給學生。慕課的興起，為分級教學提供了更加靈活的空間，為實現(xiàn)真正的“因材施教”提供了可能。

慕課是一種特定的在線課程，其以靈活、獨特的方式，為計算機教學尤其是計算機分級教學，注入了新鮮的活力。慕課既解決了教學條件受限的問題，也可以實現(xiàn)學習者的個性化學習，從而擺脫傳統(tǒng)課堂教學進度的束縛，便于差異化教學的實施。

分級教學按教學過程分為學生分級、教學目標分級、評價分級等。其中，學生分級的客觀性和有效性，是分級教學成功實施的重要前提。慕課平臺環(huán)境下，問卷、學習過程、測試等數(shù)據(jù)采集便利，為利用數(shù)據(jù)挖掘技術(shù)進行學生分級提供可能。

1 ID3算法描述

決策樹方法是用于分類和預測的重要技術(shù)。1986年，J.Ross.Quinlan提出的ID3算法，是最經(jīng)典的決策樹挖掘算法，并為后來許多決策樹其他算法的研究和改進打下理論基礎(chǔ)[1]。

ID3決策樹算法引入了信息論中的一些概念，將信息熵和信息增益作為選擇測試屬性的標準，通過決策樹內(nèi)部結(jié)點各個屬性間信息增益的比較，自頂而下，遞歸建立樣本數(shù)據(jù)集的決策樹，以用來對未知的數(shù)據(jù)集進行分類。

1.1 信息熵

熵是物理學中的一個名詞，常用來表示某些物質(zhì)系統(tǒng)狀態(tài)的一種度量。信息熵是信息論中的概念，稱為平均信息量，指信息的不確定性，是對被傳送的信息進行度量所采用的一種平均值。

設(shè)S是具有k個樣本數(shù)據(jù)的集合，S中的類別屬性共有m個不同的取值，可以將S分為m個不同類，即Ci(i=1，2，…，m)。設(shè)si是S中屬于類Ci的樣本數(shù)據(jù)數(shù)，則對于樣本集合S分類所需的信息熵為：

1.2 條件熵

條件熵也叫作期望熵。假設(shè)S樣本集合中屬性X共有n個不同的取值，可以將S分為n個不同的子集，即Cj(j=1，2，…，n)。設(shè)sj是S中屬性X取值為Xj的樣本數(shù)據(jù)數(shù)，則屬性A的條件熵為：

1.3 信息增益

信息增益用來度量屬性劃分樣本數(shù)據(jù)集所帶來的信息或者信息熵的有效減少量值，根據(jù)它能夠確定在什么層次上選擇什么樣的變量來分類，以此為依據(jù)構(gòu)建樹。

S樣本集合中屬性X的信息增益為：

Gain(X)=I(s1，s2，…，sm)-E(X)

ID3算法選擇信息增益最大的屬性為決策樹的根結(jié)點，使得對結(jié)果劃分中的樣本分類所需信息量最小。然后，使用遞歸的方法確定其他分支，直到構(gòu)建出整棵決策樹。在決策樹中每一個非葉子結(jié)點對應著一個非類別屬性，這個屬性不同的值分別為下一級樹枝。在下一級再對其他屬性進行信息增益的計算，以確定下一級分類結(jié)點，最終都到葉子結(jié)點結(jié)束。一個葉子結(jié)點代表一個分類結(jié)果，其從根結(jié)點到該葉子結(jié)點之間的路徑記錄著所屬的類別。

ID3決策樹算法的流程如圖1所示。

ID3決策樹算法通過圖1中步驟的不斷循環(huán)，對決策樹逐步求精，直到找到一個完全正確的決策樹為止。該算法構(gòu)造的決策樹，整體看起來從頂向下形成一組類似于IF…THEN的規(guī)則。ID3算法的原始程序只能區(qū)分兩個類別的數(shù)據(jù)，即布爾值真或假。隨著算法的完善和發(fā)展，目前該算法允許用于多個類別的決策。

1.4 ID3算法的優(yōu)缺點

ID3算法自誕生以來，作為一種經(jīng)典算法經(jīng)久不衰。ID3算法按人們處理事情的常規(guī)辦法，自頂而下、從簡單到復雜建立決策樹。該算法從一顆空樹開始，遞歸選擇最大信息增益屬性構(gòu)造當前結(jié)點，最終搜索到一棵能正確分類數(shù)據(jù)集的決策樹。ID3算法基礎(chǔ)理論清晰、方法簡單、決策樹易于構(gòu)造、學習能力較強，是獲取知識的有用工具，也是數(shù)據(jù)挖掘和機器學習領(lǐng)域中的一個好的范例[2]。

圖1 ID3算法流程

但是，ID3算法也有缺陷。首先，由于ID3算法以信息增益作為分裂屬性選擇標準，偏向于選擇取值較多的屬性，但是該屬性并不一定是最優(yōu)的屬性，某些情況下，這類屬性并不能提供太多有價值的信息。其次，ID3算法只能處理離散型的屬性，而不適合處理連續(xù)型的屬性，因此，在分類前必須對連續(xù)型的屬性進行離散化。再次，ID3算法中用到的訓練集中正反例的比例應該與實例中的比例一致。

由于ID3決策樹算法存在多值偏向的缺陷，因此，當用于決策樹的屬性過多時，可能會造成其算法過于繁雜甚至無效。關(guān)聯(lián)規(guī)則的應用，可以從樣本事務(wù)數(shù)據(jù)庫中找出與分類屬性關(guān)聯(lián)最為緊密的屬性集，同時將這些屬性作為待選屬性應用到ID3決策樹中。這樣，可以快速有效地篩選無關(guān)屬性，盡量避免ID3算法多值偏向造成的復雜性和無效性。

2 ID3算法在學生分級中的應用

2.1 研究對象和目標

以選報“計算機基礎(chǔ)應用”慕課課程的普通本科學生172人，成人本科學生303人相關(guān)信息為研究對象。其中，將普通本科學生172人、成人本科學生200人相關(guān)信息作為樣本數(shù)據(jù)庫，成人本科學生103人相關(guān)信息留作測試數(shù)據(jù)庫。目標是希望通過對樣本數(shù)據(jù)庫中篩選信息完整、分級效果良好學生的摸底成績、調(diào)查問卷進行分析，結(jié)合學生自我分級意愿，借助關(guān)聯(lián)規(guī)則，選取用于學生分級的關(guān)鍵元素，建立決策樹，以指導今后計算機分級教學慕課中的學生分級，并以測試數(shù)據(jù)庫檢驗該分級模型。

2.2 數(shù)據(jù)采集

數(shù)據(jù)的采集來源于5部分:(1)摸底測試，由考試系統(tǒng)直接生成，包含選擇、判斷、打字、Windows基本操作、Word、Excel、PowerPoint、網(wǎng)絡(luò)和E-mail幾部分。(2)新生計算機水平調(diào)查問卷，由慕課平臺發(fā)布并收集，包括籍貫、家庭情況、計算機學習情況、計算機技能掌握情況、計算機技能拓展情況、上網(wǎng)情況、興趣判斷、入學前工作性質(zhì)、入學前最高學歷、是否大學生入伍、是否計算機相關(guān)專業(yè)等信息[3]。(3)學生在對自己基礎(chǔ)能力認知的前提下提出的分級意愿，同樣由慕課平臺發(fā)布并收集。(4)分級實施后，登記確定的分級結(jié)果。(5)最終結(jié)課考試，由考試系統(tǒng)直接生成。

2.3 數(shù)據(jù)預處理

采集到的原始數(shù)據(jù)往往存在數(shù)據(jù)不完整、含有噪聲、不一致等問題，因此不能直接用于數(shù)據(jù)挖掘，需要對原始數(shù)據(jù)進行預處理，以保證用于挖掘的數(shù)據(jù)準確性，提高數(shù)據(jù)挖掘的精度。

2.3.1 數(shù)據(jù)清理

由于成績數(shù)據(jù)來源于考試系統(tǒng)，而其他數(shù)據(jù)多通過慕課平臺采集，從一定程度上避免了原始數(shù)據(jù)的不一致性。因此，數(shù)據(jù)清理的主要任務(wù)是解決數(shù)據(jù)中空缺值的問題。

某些學生因故未能參加摸底測試或結(jié)課考試，此時可以采用忽略元組的方法將成績表中缺失成績的記錄予以刪除。新生計算機水平調(diào)查問卷由教師組織，學生自主填寫，可能會存在學生對某些項出現(xiàn)理解偏差或者理解不了的情況，也可能出現(xiàn)漏填等情況。缺少多個屬性值的記錄，在很大程度上失去了挖掘的意義，可以直接予以刪除。而對于缺少個別屬性值的記錄，可以選擇該屬性中最可能的值進行填充、完善。

2.3.2 數(shù)據(jù)集成

數(shù)據(jù)集成的過程是合并多個數(shù)據(jù)源中的數(shù)據(jù)并將其置于一個一致的數(shù)據(jù)存儲中。從集成后的數(shù)據(jù)集中選擇與挖掘有關(guān)的數(shù)據(jù)，可以在確保數(shù)據(jù)語義完整和正確的前提下，適當降低數(shù)據(jù)量的大小，直接提高挖掘效率。

所有數(shù)據(jù)表中均有“學號”和“姓名”字段，但這兩個字段對挖掘過程沒有任何意義，只是起到對記錄進行標識的作用。分級教學主要針對總分進行分級，因此在摸底成績表和結(jié)課成績表中，只對總分進行挖掘分析。

5個數(shù)據(jù)表中，前4個數(shù)據(jù)表主要用于決策的生成過程，而最后一個數(shù)據(jù)表主要用于篩選樣本數(shù)據(jù)集。雖然結(jié)構(gòu)比較相似，但其目的和對象均不完全相同，因此不應在此將多個數(shù)據(jù)表進行合并，應在去除字段屬性的冗余、完成數(shù)據(jù)離散化后，將其置于一個數(shù)據(jù)庫中，待應用具體算法前再根據(jù)需要進行合并。

2.3.3 數(shù)據(jù)離散化

數(shù)據(jù)離散化就是將屬性值劃分為區(qū)間，在進行分析時使用區(qū)間的標號代替實際數(shù)據(jù)的處理方法。數(shù)據(jù)離散化主要是為數(shù)據(jù)挖掘服務(wù)的，通過數(shù)據(jù)離散化技術(shù)可以減少連續(xù)屬性值的個數(shù)[4]，簡化數(shù)據(jù)，最終目的是使數(shù)據(jù)挖掘結(jié)果更加簡潔和易于理解，減少系統(tǒng)開銷。

在摸底成績表中，將總分以50分和70分為界線分為三段，即[0，50)，[50，70)，[70，100]。

對入學前工作性質(zhì)進行匯總整理，根據(jù)工作性質(zhì)與計算機接觸幾率分析，將入學前工作性質(zhì)分成“計算機相關(guān)”和“計算機無關(guān)”。為簡化算法，進一步將其抽象為邏輯變量“計算機相關(guān)工作”，其值分別取Y或N。

2.4 決策樹的應用

為避免ID3算法多值偏向造成的復雜性和無效性，利用關(guān)聯(lián)規(guī)則篩選無關(guān)屬性，提取用于決策樹的屬性共4個，分別為：計算機相關(guān)專業(yè)、通過計算機等級考試、自我興趣判斷及計算機相關(guān)工作且大學生入伍。部分數(shù)據(jù)記錄如表1所示。

2.4.1 分類屬性信息熵

統(tǒng)計得知，分類屬性“分級”共200條記錄，值為“A”的有45條記錄，值為“B”的有110條記錄，值為“C”的有45條記錄。因此，分類屬性“分級”的信息熵為：

2.4.2 各條件熵

2.4.2.1 計算機相關(guān)工作且大學生入伍屬性的熵

計算機相關(guān)工作且大學生入伍屬性包括“Y”“N”兩種取值。

表1 決策樹樣本數(shù)據(jù)集部分數(shù)據(jù)

計算機相關(guān)工作且大學生入伍為“N”的熵為：

計算機相關(guān)工作且大學生入伍屬性的熵為：

E(計算機相關(guān)工作且大學生入伍)

2.4.2.2 計算機相關(guān)專業(yè)屬性的熵

計算機相關(guān)專業(yè)屬性包括“Y”“N”兩種取值。

計算機相關(guān)專業(yè)為“Y”的熵為：

計算機相關(guān)專業(yè)為“N”的熵為：

計算機相關(guān)專業(yè)屬性的熵為：

當李莉把交了兩個月租金的出租屋讓給許峰，自己投奔梅子的時候，梅子指著她的腦袋痛心疾首：“世界上最傻的女人就是你，許峰那個白眼狼，一看就是個攀高枝的。他騙你騙得高段啊，你走得那個順溜啊?！?/p>

2.4.2.3 通過計算機等級考試屬性的熵

通過計算機等級考試屬性包括“Y”“N”兩種取值。

通過計算機等級考試為“Y”的熵為：

通過計算機等級考試為“N”的熵為：

通過計算機等級考試屬性的熵為：

2.4.2.4 自我興趣判斷屬性的熵

自我興趣判斷屬性包括“A”“B”“C”三種取值。

自我興趣判斷為“A”的熵為：

自我興趣判斷為“B”的熵為：

自我興趣判斷為“C”的熵為：

自我興趣判斷屬性的熵為：

2.4.3 各屬性信息增益

Gain(計算機相關(guān)工作且大學生入伍)=1.4428-1.3904=0.0524

Gain(計算機相關(guān)專業(yè))=1.4428-1.4027=0.0401

Gain(通過計算機等級考試)=1.4428-1.3716=0.0712

Gain(自我興趣判斷)=1.4428-1.3353=0.1075

由此可以得出，自我興趣判斷屬性的信息增益最大，可選擇該屬性作為決策樹的根結(jié)點。

2.4.4 生成決策樹

依次進行一級、二級、三級分支結(jié)點的計算，得到?jīng)Q策樹如圖2所示。

圖2 初步生成分級教學決策樹

2.4.5 完善決策樹

為降低ID3算法多值偏向，計算前對訓練數(shù)據(jù)集中各屬性進行了簡化，因此，其得出的決策樹并未完成對所有記錄的分級。此時，需要借助最簡單的分數(shù)分級方法繼續(xù)完善得到的決策樹。完善后的決策樹如圖3所示。

3 結(jié)束語

慕課的開設(shè)，使大規(guī)模授課成為可能。隨著選報人數(shù)的增多，用于學生分級的數(shù)據(jù)激增，也更具有多樣性和復雜性。決策樹的應用，可以將教師從大量數(shù)據(jù)分析工作中解放出來，以更充沛的精力投入教學，同時保證了分級的客觀性和有效性。當然，學生的分級僅僅是分級教學的第一步，還涉及到教學模式、教學方法、教學目標、教學評價等的分級。數(shù)據(jù)挖掘在分級教學中的應用也不僅限于學生的分級，還可以用于教學動態(tài)分析、個性化教學策略、教學效果評價等方面。

圖3 完善后最終生成決策樹