一種混合算法在學(xué)習(xí)歷程數(shù)據(jù)分析中的應(yīng)用研究*

張 穎，劉建煒，張艷紅

(1.福州建筑工程職業(yè)中專學(xué)校計(jì)算機(jī)教研室，福建福州350013; 2.福建幼兒師范高等?？茖W(xué)校人文科學(xué)系，福建福州350013)

一種混合算法在學(xué)習(xí)歷程數(shù)據(jù)分析中的應(yīng)用研究*

張 穎1，劉建煒2，張艷紅1

(1.福州建筑工程職業(yè)中專學(xué)校計(jì)算機(jī)教研室，福建福州350013; 2.福建幼兒師范高等?？茖W(xué)校人文科學(xué)系，福建福州350013)

該文嘗試混合運(yùn)用K－means、ID3等算法，并加以改進(jìn)，得出了一種混合改進(jìn)算法.在實(shí)際應(yīng)用中，它能夠高效的對學(xué)生的學(xué)習(xí)歷程數(shù)據(jù)進(jìn)行深入的分析與挖掘，最終發(fā)現(xiàn)在海量的學(xué)習(xí)歷程數(shù)據(jù)中蘊(yùn)藏的有價值的信息，并以此為職業(yè)院校的人才培養(yǎng)與決策提供數(shù)據(jù)支持.

算法;預(yù)測;K－means;ID3

在教育信息化浪潮中，職業(yè)院校大量的關(guān)于學(xué)生學(xué)習(xí)歷程的原始數(shù)據(jù)沉積了下來，它涉及到學(xué)生日常學(xué)習(xí)、生活的方方面面.這類數(shù)據(jù)是學(xué)校辦學(xué)過程中積累的最寶貴的財富之一，大數(shù)據(jù)對學(xué)校教育教學(xué)改革與人才培養(yǎng)可起到支持作用.本文通過混合運(yùn)用多種數(shù)據(jù)挖掘算法，對學(xué)校的海量學(xué)生學(xué)習(xí)歷程數(shù)據(jù)進(jìn)行分析研究，并得到在這類數(shù)據(jù)中蘊(yùn)藏的有價值的知識和規(guī)則.進(jìn)而運(yùn)用這些知識規(guī)則，嘗試對在校生的德育行為進(jìn)行預(yù)測，進(jìn)而為學(xué)生工作者、校領(lǐng)導(dǎo)的工作開展與決策提供數(shù)據(jù)支持.［1－2］

1 本文所采用的行為分析算法研究

1.1 K－means聚類算法及改進(jìn)

通常采用分類、聚類、關(guān)聯(lián)規(guī)則等算法對學(xué)生學(xué)習(xí)歷程數(shù)據(jù)進(jìn)行分析.在數(shù)據(jù)分析過程中，特別關(guān)注兩類現(xiàn)象，一類是“群體”現(xiàn)象，另一類是“離群”現(xiàn)象.而K－means聚類算法可以進(jìn)行聚類運(yùn)算，同時也可以根據(jù)算法尋找到孤立數(shù)據(jù).但是，通過樣本數(shù)據(jù)的測試發(fā)現(xiàn)，傳統(tǒng)的K－means聚類算法在學(xué)生學(xué)習(xí)歷程數(shù)據(jù)的分析中存在運(yùn)行效率與準(zhǔn)確度較低的現(xiàn)象.［3］而影響該算法準(zhǔn)確性的關(guān)鍵之一是集合中心點(diǎn)的選擇計(jì)算，結(jié)合領(lǐng)域知識，根據(jù)學(xué)生群體的學(xué)習(xí)歷程數(shù)據(jù)特征，創(chuàng)建特定的中心點(diǎn)選擇算法，以此對學(xué)生學(xué)習(xí)歷程數(shù)據(jù)的分析過程中所使用的K－means聚類算法進(jìn)行改進(jìn)，以適應(yīng)學(xué)習(xí)歷程數(shù)據(jù)分析的具體情況.該算法的核心思想如下:

定義一:集合Pij(pi1，pi2，pi3，…pin)，其中i表示樣本點(diǎn)，j表示維度.則集合Pij的中心點(diǎn)計(jì)算方式如下［4－5］:

步驟1:根據(jù)定義一計(jì)算出傳統(tǒng)K－means算法所得出的集合{Pi}的中心點(diǎn)Center(Pi);［6－8］

步驟2:雙中心點(diǎn)計(jì)算，根據(jù)步驟1計(jì)算出的中心點(diǎn)，計(jì)算出離該點(diǎn)最近與最遠(yuǎn)的兩個點(diǎn)作為雙中心，分別記為Max(Pi)、Min(Pi)，且置n=2;

步驟3:判斷用戶輸入k＞n是否成立:如果不成立則算法退出，并且把n作為中心點(diǎn)數(shù)進(jìn)行聚類劃分;如果成立，則計(jì)算中心點(diǎn)集合的中心位置Center(Ci)，并計(jì)算出距離該位置最遠(yuǎn)的數(shù)據(jù)作為下一個聚類中心，且設(shè)置n=n+1;

步驟4:重復(fù)執(zhí)行步驟3，直到算法退出.

1.2 ID3決策樹算法及改進(jìn)

ID3算法是一種常用的基于信息熵的分類算法，通過遞歸計(jì)算出分類樹.但是在對學(xué)生學(xué)習(xí)歷程數(shù)據(jù)的計(jì)算過程中，由于遞歸重復(fù)計(jì)算導(dǎo)致運(yùn)算效率低下，計(jì)算成本較高.傳統(tǒng)的解決方式是簡化熵計(jì)算的方式，即應(yīng)用泰勒公式和麥克勞林公式進(jìn)行降維處理，從而降低ID3算法的時間復(fù)雜度.［9－11］

公式1:

通過應(yīng)用上述公式ID3算法的計(jì)算效率有所提高，但該改進(jìn)算法在學(xué)習(xí)歷程數(shù)據(jù)分析過程中的效果并不理想.根據(jù)學(xué)生學(xué)習(xí)歷程數(shù)據(jù)的特點(diǎn)，這類數(shù)據(jù)中有很多數(shù)據(jù)項(xiàng)具有強(qiáng)關(guān)聯(lián)關(guān)系，由此課題組嘗試引入Apriori關(guān)聯(lián)規(guī)則算法，通過對原始數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則清洗:對參與計(jì)算的數(shù)據(jù)進(jìn)行強(qiáng)關(guān)聯(lián)規(guī)則計(jì)算，從中發(fā)現(xiàn)它們之間的強(qiáng)關(guān)聯(lián)關(guān)系，并以此為依據(jù)進(jìn)行數(shù)據(jù)屬性的約減，從而約減參與ID3分類計(jì)算的數(shù)據(jù)規(guī)模，進(jìn)而有效提高計(jì)算效率.

2 基于K－means、ID3等算法的學(xué)生行為預(yù)測數(shù)據(jù)挖掘

樣本數(shù)據(jù)來自于歷年來學(xué)校學(xué)生沉積的學(xué)習(xí)歷程數(shù)據(jù)，有教學(xué)管理、心理測評、德育考評等方面的數(shù)據(jù)來源，初始數(shù)據(jù)如下表1所示:

表1 學(xué)生月度情況一覽表

表1說明:戶籍={城關(guān)=1、農(nóng)村=2};…;處分情況={無處分=1，警告/記過=2，留校察看= 3、開除=4}.

2.1 基于K－means改進(jìn)算法的學(xué)生學(xué)習(xí)歷程數(shù)據(jù)的分析

為了分析學(xué)生的心理因素對德育行為的影響，課題組將心理測評與德育積分作為研究分析對象，把K值置為4，即分為四類，分別為:優(yōu)秀、良好、中等、差.根據(jù)改進(jìn)后的K－Means算法計(jì)算結(jié)果如表2所示:

表2 各分組情況

各分組的學(xué)生人數(shù)占比，如表3:

表3 各分組人數(shù)所占百分比

二維坐標(biāo)數(shù)據(jù)分布示意圖如圖1:

圖1 心理與德育積分分析示意圖

同時，我們從數(shù)據(jù)樣本中抽取具有代表性的若干字段進(jìn)行分類匯總，如表4:

應(yīng)用K－means算法的分析結(jié)果，得到以下信息:第一組的學(xué)生屬于學(xué)習(xí)中等的學(xué)生，但是他們的綜合表現(xiàn)良好，出勤率高、課堂表現(xiàn)優(yōu)異、學(xué)習(xí)態(tài)度端正、積極參與集體活動等，且大部分屬于粘液質(zhì)的氣質(zhì)類型;第二組同學(xué)平時表現(xiàn)一般，但成績較為突出，這是一個值得深入研究的現(xiàn)象.而讓我們更為關(guān)注的是系統(tǒng)檢測出的離群信息，學(xué)生6:該學(xué)生即為我們傳統(tǒng)上說的問題學(xué)生，例如學(xué)習(xí)態(tài)度不端正，愛出小差，與同學(xué)關(guān)系緊張，參加集體活動很消極、較為孤立，學(xué)習(xí)成績也是不理想.這類學(xué)生的數(shù)據(jù)是我們關(guān)注的重點(diǎn)，需要進(jìn)一步深入挖掘的對象，通過下面的進(jìn)一步挖掘，以期得出這類學(xué)生更有價值的信息，為學(xué)生工作者及相關(guān)領(lǐng)導(dǎo)提供更為有效的決策支持.

表4 按分組進(jìn)行字段分類匯總表

2.2 基于ID3改進(jìn)算法的學(xué)生德育行為數(shù)據(jù)分析為了對上述得出的感興趣的數(shù)據(jù)進(jìn)行進(jìn)一步分析挖掘，繼續(xù)抽取學(xué)生的學(xué)習(xí)歷程數(shù)據(jù)進(jìn)行分析研究，經(jīng)過二次數(shù)據(jù)清洗得到數(shù)據(jù)如表5(部分).

表5 學(xué)生信息表C

(1)ID3算法計(jì)算過程演練.表5是采集樣本數(shù)據(jù)集R，一共選取了8個字段進(jìn)行計(jì)算，“處分”字段是作為分類算法的標(biāo)識字段.在進(jìn)行ID3分類算法計(jì)算之前，應(yīng)用Apriori算法對源數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘，從而挖掘出符合要求的強(qiáng)關(guān)聯(lián)屬性集.并以此為依據(jù)，對這類屬性進(jìn)行屬性約減得到數(shù)據(jù)集R'，然后再應(yīng)用ID3分類算法對R'進(jìn)行分類計(jì)算，以此提高分類計(jì)算的效率.具體演算步驟如下:

步驟1:對參與演算的源數(shù)據(jù)集合C(表5數(shù)據(jù))進(jìn)行清洗，設(shè)置Apriori算法計(jì)算相關(guān)參數(shù):最小支持度α=4，最小置信度β=0.8，計(jì)算得到以下強(qiáng)關(guān)聯(lián)規(guī)則:

1{活動情況、心理狀態(tài)}=＞{氣質(zhì)類型} 置信度=83.33%

2{活動情況、氣質(zhì)類型}=＞{心理狀態(tài)} 置信度=71.43%

3{氣質(zhì)類型、心理狀態(tài)}=＞{活動情況} 置信度=71.43%

4{心理狀態(tài)、氣質(zhì)類型}=＞{活動情況} 置信度=100%

5{缺勤情況、氣質(zhì)類型}=＞{戶籍性質(zhì)} 置信度=100%

6{戶籍性質(zhì)、氣質(zhì)類型}=＞{缺勤情況} 置信度=83.33%

根據(jù)上述得出的強(qiáng)關(guān)聯(lián)規(guī)則，篩選出可以約減的屬性為:“活動、戶籍”，因?yàn)檫@兩個屬性可以分別由“氣質(zhì)、心理”與“氣質(zhì)、缺勤”所替代，故可以約減這兩個屬性，得到集合C'，如表6所示:

表6 新數(shù)據(jù)集合C'

步驟2:應(yīng)用ID3分類算法對新得到的數(shù)據(jù)集合C'進(jìn)行分類計(jì)算:設(shè)定“處分”作為分類標(biāo)識字段，則有K=20、m=4;K表示為集合C'的記錄數(shù)，此處共計(jì)20條記錄，故K=20;m表示為屬性取值數(shù)量，此處“處分”的值域?yàn)閧無處分、警告記過、留校察看、開除}合計(jì)有4種類型，故m=4.

步驟3:計(jì)算信息熵，首先根據(jù)m=4設(shè)定“處分”屬性值為“無處分”的類記為C1;“處分”屬性值為“警告記過”的類記為C2;“處分”屬性值為“留校察看”的類記為C3;“處分”屬性值為“開除”的類記為C4.則，C1=5，C2=3，C3=3，C4=9，且有:P1= 5/20，P2=3/20，P3=3/20，P4=9/20，對于C'的期望值計(jì)算如下:

步驟4:依次計(jì)算其余屬性的熵值，先計(jì)算“學(xué)習(xí)”屬性的熵，對于“學(xué)習(xí)=優(yōu)”的類別標(biāo)號，有:C11=5，C21=0，C31=0，C41=0;則有:P11=5/5，P21=0，P31=0，P41=0，計(jì)算熵值如下:

再計(jì)算“學(xué)習(xí)=良”的情況，有:C12=1，C22= 2，C32=0，C45=0;則有:P12=1/3，P22=2/3，P32=0，P42=0，計(jì)算熵值如下:

再計(jì)算“學(xué)習(xí)=中”的情況，有:C13=0，C23= 1，C33=1，C43=1;則有:P12=0，P22=1/3，P32= 1/3，P42=1/3，計(jì)算熵值如下:

最后計(jì)算“學(xué)習(xí)=差”的情況，有:C14=1，C24=5，C34=2，C44=1;則有:P12=1/9，P22=5/9，P32=2/9，P42=1/9，計(jì)算熵值如下:

綜合以上計(jì)算結(jié)果，設(shè)定以“學(xué)習(xí)”字段進(jìn)行分組劃分，其期望值結(jié)果計(jì)算如下:

即可以計(jì)算出“學(xué)習(xí)”字段的期望值:

Gain(學(xué)習(xí)成績)=I(C1，C2，C3，C4)－E(學(xué)習(xí)成績)=0.2230

重復(fù)執(zhí)行公式4，分別計(jì)算出“德育、缺勤、心理、氣質(zhì)”等屬性的期望值，結(jié)果如下:

Gain(德育)=I(C1，C2，C3，C4)－E(德育)= 0.2645

Gain(缺勤)=I(C1，C2，C3，C4)－E(缺勤)= 0.0345

Gain(心理)=I(C1，C2，C3，C4)－E(心理)= 0.1005

Gain(氣質(zhì))=I(C1，C2，C3，C4)－E(氣質(zhì))= 0.1085

步驟5:根據(jù)步驟4計(jì)算出了數(shù)據(jù)集合C'所有屬性的期望值，其中得出Gain(德育)的期望值最大，以此作為分類劃分的依據(jù)，并創(chuàng)建決策樹，并進(jìn)行相應(yīng)的標(biāo)記.得出本次計(jì)算以“德育”字段作為分類測試的字段，創(chuàng)建決策樹節(jié)點(diǎn)，并計(jì)算出以此為節(jié)點(diǎn)的其他分支.

步驟6:對步驟5生成的相應(yīng)分支，重復(fù)步驟1 ～5的相關(guān)操作，直到整個決策樹的生成.

本次對數(shù)據(jù)集合C的計(jì)算，生成的完整決策樹，如下圖2所示:

圖2 完全決策樹

應(yīng)用“IF…THEN…”表達(dá)式可以抽取出圖2決策樹所包含的知識，即可得到以下的規(guī)則:

① IF德育積分=“優(yōu)”AND學(xué)習(xí)成績=“優(yōu)”THEN處分情況=“無處分”;

② IF德育積分=“優(yōu)”AND學(xué)習(xí)成績=“中”THEN處分情況=“無處分”;

③ IF德育積分=“優(yōu)”AND學(xué)習(xí)成績=“良”AND氣質(zhì)類型=“膽汁質(zhì)”THEN處分情況=“無處分”;

④ IF德育積分=“優(yōu)”AND學(xué)習(xí)成績=“良”AND氣質(zhì)類型=“多血質(zhì)”THEN處分情況=“無處分”;

⑤ IF德育積分=“優(yōu)”AND學(xué)習(xí)成績=“良”AND氣質(zhì)類型=“粘液質(zhì)”THEN處分情況=“無處分”;

⑥ IF德育積分=“優(yōu)”AND學(xué)習(xí)成績=“良”AND氣質(zhì)類型=“抑郁質(zhì)”THEN處分情況=“警告記過”;

⑦ IF德育積分=“優(yōu)”AND學(xué)習(xí)成績=“差”AND心理狀態(tài)=“從無”THEN處分情況=“警告記過”;

⑧ IF德育積分=“優(yōu)”AND學(xué)習(xí)成績=“差”AND心理狀態(tài)=“輕度”THEN處分情況=“無處分”;

⑨ IF德育積分=“優(yōu)”AND學(xué)習(xí)成績=“差”AND心理狀態(tài)=“中度”THEN處分情況=“警告記過”;

⑩ IF德育積分=“優(yōu)”AND學(xué)習(xí)成績=“差”AND心理狀態(tài)=“重度”THEN處分情況=“警告記過”;

? IF德育積分=“良”AND學(xué)習(xí)成績=“優(yōu)”THEN處分情況=“無處分”;

? IF德育積分=“良”AND學(xué)習(xí)成績=“良”THEN處分情況=“留校察看”;

? IF德育積分=“良”AND學(xué)習(xí)成績=“中”THEN處分情況=“留校察看”;

? IF德育積分=“良”AND學(xué)習(xí)成績=“差”THEN處分情況=“留校察看”;

? IF德育積分=“中”THEN處分情況=“警告記過”;

? IF德育積分=“差”AND氣質(zhì)類型=“膽汁質(zhì)”AND缺勤情況=“較輕”THEN處分情況=“留校察看”;

? IF德育積分=“差”AND氣質(zhì)類型=“膽汁質(zhì)”AND缺勤情況=“嚴(yán)重”THEN處分情況=“開除”;

? IF德育積分=“差”AND氣質(zhì)類型=“膽汁質(zhì)”AND缺勤情況=“正常”THEN處分情況=“開除”;

? IF德育積分=“差”AND氣質(zhì)類型=“多血質(zhì)”AND缺勤情況=“正常”THEN處分情況=“留校察看”;

? IF德育積分=“差”AND氣質(zhì)類型=“多血質(zhì)”AND缺勤情況=“較輕”THEN處分情況=“留校察看”;

? IF德育積分=“差”AND氣質(zhì)類型=“多血質(zhì)”AND缺勤情況=“嚴(yán)重”THEN處分情況=“警告記過”;

? IF德育積分=“差”AND氣質(zhì)類型=“粘液質(zhì)”THEN處分情況=“警告記過”;

? IF德育積分=“差”AND氣質(zhì)類型=“抑郁質(zhì)”THEN處分情況=“警告記過”.

(2)規(guī)則分析與應(yīng)用.知識1:通過分析規(guī)則①②③④⑤⑥可以得出以下有用的知識結(jié)論，即學(xué)習(xí)成績在中等以上且德育成績優(yōu)秀的學(xué)生受到的學(xué)校處分較少，這部分學(xué)生占了在校學(xué)生的絕大多數(shù)，屬于中堅(jiān)力量，充分表明了學(xué)生的在校表現(xiàn)與學(xué)生取得的學(xué)校成績呈正態(tài)分布的實(shí)際情況.

知識2:通過分析規(guī)則⑦⑧⑨⑩發(fā)現(xiàn)在學(xué)習(xí)成績較差的學(xué)生中，心理狀態(tài)是影響學(xué)生在校德育表現(xiàn)的重要影響因素.例如，有部分心理表現(xiàn)為重度、中度的學(xué)生在校德育表現(xiàn)較差，有出現(xiàn)違紀(jì)受到處分的記錄.

知識3:通過分析規(guī)則????發(fā)現(xiàn)，這部分學(xué)生群體德育表現(xiàn)中等，但有一些違紀(jì)記錄.這類學(xué)生如果能夠加以引導(dǎo)，讓其專注于學(xué)習(xí)，將大幅降低這類學(xué)生德育違紀(jì)相關(guān)事件發(fā)生的概率.

知識4:通過分析規(guī)則?????????發(fā)現(xiàn)，這部分學(xué)生屬于學(xué)生工作者較為頭疼的“后進(jìn)生”.根據(jù)數(shù)據(jù)分析結(jié)果表明，這類學(xué)生較為沖動，屬于典型的膽汁質(zhì)性格特質(zhì)的學(xué)生較多.上述通過聚類算法挖掘出的離群學(xué)生就是出自這類學(xué)生，這類學(xué)生應(yīng)當(dāng)成為學(xué)生工作者重點(diǎn)關(guān)注與預(yù)防的對象.

3 系統(tǒng)實(shí)現(xiàn)

通過應(yīng)用上述改進(jìn)的K－means、ID3算法，并實(shí)驗(yàn)驗(yàn)證了其有效性及效率的提升，最終實(shí)現(xiàn)了系統(tǒng)的開發(fā)與應(yīng)用.系統(tǒng)共分為數(shù)據(jù)采集模塊、數(shù)據(jù)預(yù)處理模塊、規(guī)則挖掘模塊、離群分析模塊、規(guī)則生成模塊等5大部分組成.如圖3～圖5展示了系統(tǒng)的部分功能模塊.

4 總結(jié)

圖3 數(shù)據(jù)預(yù)處理模塊

通過對學(xué)生學(xué)習(xí)歷程數(shù)據(jù)進(jìn)行聚類分析，有效地發(fā)現(xiàn)離群信息，并通過分類算法對學(xué)生的行為進(jìn)行分析和預(yù)測.實(shí)驗(yàn)結(jié)果顯示，改進(jìn)后的算法提高了決策樹算法的分類效率，分類效果良好.同時，根據(jù)分類結(jié)果生成的規(guī)則知識，在一定程度上能夠有效地對學(xué)生行為分析及預(yù)測，在學(xué)生管理工作中具有重要的指導(dǎo)意義.

圖4 離群信息發(fā)現(xiàn)

圖5 生成的決策樹

［1］余輝，呂揚(yáng)生.數(shù)據(jù)挖掘技術(shù)在生物醫(yī)學(xué)領(lǐng)域的應(yīng)用［J］.國外醫(yī)學(xué).生物醫(yī)學(xué)工程分冊，2003，26(2):54－59.

［2］王軒.數(shù)據(jù)挖掘熱點(diǎn)和研究方向淺析［J］.黑龍江科技信息，2012(27):105.

［3］高尚，楊靜寧.一種新的基于例子群算法的聚類方法［J］.南京航空航天大學(xué)學(xué)報，2006，(B07):62－65.

［4］崔丹丹.K－Means聚類算法的研究與改進(jìn)［D］.合肥:安徽大學(xué)，2012.

［5］黃繼超.K－Means算法若干改進(jìn)和應(yīng)用［D］.長沙:中南大學(xué)，2012:22－29.

［6］ZhouTao，Lu Huiling.Clustering algorithm research advances on data mining［J］.Computer Engineering and Applications，2012(12).

［7］陸聲鏈，林士敏.基于距離的孤立點(diǎn)檢測研究［J］.計(jì)算機(jī)工程與應(yīng)用，2004，40(33):73－75.

［8］李金宗.模式識別導(dǎo)論［M］.北京:高等教育出版社，1994: 294－356.

［9］何化玲.基于ID3決策樹算法的改進(jìn)研究［D］.鄭州:華北水利水電學(xué)院，2011.

［10］姜晗，賈涑.基于聚類的孤立點(diǎn)檢測算法［J］.計(jì)算機(jī)與現(xiàn)代，2012(11):37－39.

［11］(印度)MARGARETHDUNHAM.數(shù)據(jù)挖掘教程［M］.郭崇慧，田鳳占，曉明等譯.北京:清華大學(xué)出版社，2005.

(責(zé)任編輯:王前)

TP274

A

1008－7974(2016)06－0010－06

10.13877/j.cnki.cn22－1284.2016.12.004

2016－06－23

福建省教育廳科技A類項(xiàng)目(JA15735)

張穎，女，福建南平人，講師.