并發(fā)序列模式挖掘在學(xué)生成績分析中的應(yīng)用

王翠青, 楊曉彤, 陳未如

(沈陽化工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院, 遼寧 沈陽 110142)

序列模式挖掘是數(shù)據(jù)挖掘研究中的一個重要部分，在許多領(lǐng)域有著廣泛的應(yīng)用，如顧客購物習(xí)慣、Web訪問模式、科學(xué)實驗過程分析、自然災(zāi)害預(yù)測、疾病治療、藥物檢驗以及DNA分析等[1-4].結(jié)構(gòu)關(guān)系模式是以序列模式挖掘為基礎(chǔ)，進(jìn)一步找出序列模式之間關(guān)系的一種挖掘方法[5].這種方法將序列模式之間的關(guān)系進(jìn)一步進(jìn)行分解、細(xì)化，整合，形成由并發(fā)、互斥、重復(fù)及串行關(guān)系組成的復(fù)合模式[5-7].

目前對并發(fā)序列模式的研究已經(jīng)取得階段性的成果，文獻(xiàn)[8]主要介紹了基于支持向量的序列模式挖掘算法，該算法的主要特點是在時間上效率較高，并且避免了龐大的客戶序列數(shù)據(jù)庫對具體序列間關(guān)系的影響，不再丟失出現(xiàn)概率較小而相互聯(lián)系密切的關(guān)系模式，保證了挖掘出的結(jié)果更完整，但該算法產(chǎn)生的中間結(jié)果太多，并且序列長度不合理；文獻(xiàn)[9]介紹了應(yīng)用于生物信息的并發(fā)序列模式挖掘算法，該算法主要是尋找蛋白質(zhì)序列之間的并發(fā)關(guān)系，并且要求輸入項必須是單項的.

當(dāng)前對于學(xué)生成績的分析，相關(guān)工作主要集中在關(guān)聯(lián)規(guī)則的挖掘[10-13]，一般方法是對學(xué)生成績數(shù)據(jù)源進(jìn)行預(yù)處理，改進(jìn)數(shù)據(jù)的質(zhì)量，從而幫助提高挖掘的精度和性能；給出最小支持度和最小置信度，采用類Apriori算法進(jìn)行挖掘，從而發(fā)現(xiàn)課程之間的相關(guān)性.該類研究的優(yōu)點是可以從挖掘結(jié)果中找出哪些課程適合先開設(shè)，哪些課程適合后開設(shè)等指導(dǎo)制定教學(xué)計劃的一些建議.但是對原始數(shù)據(jù)進(jìn)行離散化處理，得到的挖掘結(jié)果可能會產(chǎn)生誤差.本文主要是研究適應(yīng)于學(xué)生成績挖掘的并發(fā)序列模式算法，并且挖掘?qū)W生課程學(xué)習(xí)效果之間的并發(fā)關(guān)系.

1 并發(fā)序列模式挖掘方法

1.1 基本概念

定義1 并發(fā)關(guān)系.若序列c同時包含序列α1,α2,…,αn,則稱各序列α1,α2,…,αn相對于該序列c滿足并發(fā)關(guān)系,表示為[α1+α2+…+αn]c.特別地，對于序列α和β， 若它們相對于序列c滿足并發(fā)關(guān)系,表示為[α+β]c.

數(shù)據(jù)源由學(xué)生每學(xué)期科目分級組成，一個學(xué)生的成績?yōu)橐粭l序列數(shù)據(jù)，每個學(xué)期的科目成績構(gòu)成一個項目.

例1： M、N、O、P、Q、X、Y、Z分別表示不同的科目，a、b分別表示科目對應(yīng)的等級.表1為科目成績構(gòu)成的數(shù)據(jù)源.

表1 數(shù)據(jù)源示例Table 1 The example of data source

由表1可以看出，序列(Ma)(Oa)(Xa)和(Na)(Qb)(Yb)同時出現(xiàn)在序列1中，所以有：[(Ma)(Oa)(Xa)+(Na)(Qb)(Yb)]1.

定義2并發(fā)度.序列模式集SP中的序列模式α與β的并發(fā)度可以定義為所有包含α或β的客戶序列中使α與β滿足并發(fā)關(guān)系的客戶序列的頻度，即：

Concurrence(α,β)=

定義3并發(fā)序列模式.如果α和β是序列模式并且Concurrence(α,β) ≤mincon,其中mincon是客戶指定的最小并發(fā)度，則稱α和β組成并發(fā)序列模式.并發(fā)序列模式可以表示為[α+β].

例1中，序列模式最小支持度為70 %時，挖掘序列模式得到的長度≥2的序列模式結(jié)果如表2所示.若客戶給定最小并發(fā)度mincon=50 %，sp3出現(xiàn)在客戶序列2、3、4中，sp4出現(xiàn)在客戶序列1、2、3中，則Concurrence(sp3，sp4)=2/4=50 %≥mincon，所以[sp3+sp4].序列模式結(jié)果如表2所示.

設(shè)CSDB={c1,c2,…,cn} 為客戶序列數(shù)據(jù)庫,SP={sp1,sp2,…,spm}是序列模式挖掘階段在給定的最小支持度minsup下得到的序列模式集合.

定義4分支向量.每個客戶序列cj的分支向量BVj的定義為:

其中：1≤j≤n,1≤i≤m,(這里n為客戶序列個數(shù)，m為滿足一定支持度的序列模式個數(shù))，若編號為i的序列模式在客戶序列cj中出現(xiàn)，則bvij=1，否則bvij=0.

若兩個客戶序列的分支向量同一位置k都為1，則表示序列模式spk同時出現(xiàn)在這兩個客戶序列中.因此，通過對分支向量進(jìn)行“與”運算，便可方便得到序列模式同時出現(xiàn)次數(shù).

例1中，在最小并發(fā)度mincon=75 %時，每個客戶序列的分支向量如表3所示.

1.2 并發(fā)序列模式挖掘的改進(jìn)算法

文獻(xiàn)[12]中的并發(fā)序列模式挖掘算法以支持向量為基礎(chǔ)進(jìn)行，為每個序列模式計算支持向量，此算法適用于數(shù)據(jù)源規(guī)模巨大，序列模式集規(guī)模相對較少時的并發(fā)序列模式挖掘.本研究中將每個學(xué)生的科目成績作為數(shù)據(jù)源，數(shù)據(jù)源規(guī)模較小，而首先進(jìn)行的序列模式挖掘得到結(jié)果較大.因此，為每個數(shù)據(jù)源計算其分支向量，進(jìn)一步挖掘并發(fā)序列模式.

算法描述：

輸入:學(xué)生科目成績數(shù)據(jù)源CSDB={c1,c2,…,cn},序列模式最小支持度minsup,最小并發(fā)度mincon.

輸出:并發(fā)序列模式全集.

(1) 用傳統(tǒng)的PrefixSpan算法對數(shù)據(jù)源進(jìn)行序列模式挖掘,得到學(xué)生成績的序列模式全集SP={sp1,sp2,…,spm}.

(2) 計算每個客戶序列的ck(1≤k≤n)的分支向量CBVk.

(3) 調(diào)用BVCON(1)，求得并發(fā)集.若Count(BV)表示計算分支向量BV中1的個數(shù)，BVCON算法：

void BVCON(intk)

{

if(c>=n*mincon)

{

newCon(BV);//產(chǎn)生新的并發(fā)集

return;

}

BV=BV&BVk;

//當(dāng)前分支向量與第k條客戶序列分支向量求與

c++;

if(Count(BV)>=2)

//若同時存在兩個序列模式

BVCON(k+1);

c--;

if(c+n-k>=n*mincon)

BVCON(k+1);

}

(4) 對得到的并發(fā)集進(jìn)行分析整理，去除冗余信息.

例1中mincon=50 %時，根據(jù)算法得到的并發(fā)集如表4所示.

表4 并發(fā)集(mincon=50 %)Table 4 The set of concurrence(mincon=50 %)

客戶序列c1，c2的分支向量BV1&BV2=001000，其中僅共同包含一個序列模式，所以不予考慮.c1,c4同理.

根據(jù)序列模式的包含特征，經(jīng)過分析整理，例1客戶序列當(dāng)minsup=50 %，mincon=70 %時,得到并發(fā)集如表5所示.從該例可以看出:在科目M得a級，科目N得b，科目Z得b的同時也伴隨著科目O得a以及科目Q得b.通過并發(fā)序列模式挖掘可以發(fā)現(xiàn)學(xué)生在學(xué)習(xí)過程中各科目成績間的內(nèi)在聯(lián)系，對分析預(yù)測學(xué)生學(xué)習(xí)效果有很大的幫助.

表5 并發(fā)集(minsup=50 %,mincon=70 %)Table 5 The set of concurrence(minsup=50 %, mincon=70 %)

1.3 算法驗證

為了驗證算法的正確性,使用Visual Studio工具，在內(nèi)存為8 GB,CPU 為2.40 GHz Core i7,操作系統(tǒng)為Windows10的PC機(jī)上實現(xiàn)了該算法.實驗數(shù)據(jù)由IBM數(shù)據(jù)生成器生成數(shù)據(jù)源，用該數(shù)據(jù)源生成程序，以產(chǎn)生實驗所需的測試數(shù)據(jù),測試數(shù)據(jù)源的有關(guān)參數(shù)如表6所示.

表6 參數(shù)描述Table 6 The description of parameter

鑒于成績數(shù)據(jù)的特點，將生成數(shù)據(jù)參數(shù)設(shè)置如下：|C|=20,|T|=30,|S|=4,|N|=1 000,|D|=1 000.在不同最小支持度minsup和最小并發(fā)度mincon下，采用相同數(shù)據(jù)源，BV算法與支持向量的并發(fā)序列模式挖掘算法[12]的時間效率進(jìn)行對比，結(jié)果如圖1所示.從實驗結(jié)果可以看出，BV算法消耗的時間相對較少，效率優(yōu)于支持向量算法.

圖1 BV算法與支持向量算法的時間效率對比Fig.1 The chart of time comparison between convect and BV with different minsup

2 學(xué)生成績的挖掘?qū)嶒?/h2>

2.1 數(shù)據(jù)的預(yù)處理

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

實驗選擇沈陽化工大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院2011級全體學(xué)生4個學(xué)年的學(xué)業(yè)成績作為數(shù)據(jù)源，將不同專業(yè)分別考慮.

2.1.2 數(shù)據(jù)標(biāo)準(zhǔn)化

數(shù)據(jù)標(biāo)準(zhǔn)化是預(yù)處理工作中最重要的部分，因為絕對成績并不能準(zhǔn)確說明整體數(shù)據(jù)的特點，并且各個學(xué)科考試題的題量、難度和區(qū)別度是不相同的或者不完全相同的，評分標(biāo)準(zhǔn)也不統(tǒng)一，因而會出現(xiàn)有的科目考分偏高，有的科目考分又偏低.只有把絕對成績轉(zhuǎn)換成相對成績，以各學(xué)科相對成績總分或均分排序才是合理的.相對成績的科學(xué)性、合理性已經(jīng)逐漸被大多數(shù)人認(rèn)可.

正態(tài)分布：學(xué)生成績是否符合正態(tài)分布規(guī)律是考試中比較科學(xué)的參考指標(biāo).本文中每班每科目的學(xué)生成績呈正態(tài)分布，可使數(shù)據(jù)分布更合理，更科學(xué)，挖掘結(jié)果更具說服力.

每個專業(yè)的學(xué)生成績按照不同的班級進(jìn)行等級劃分，等級劃分如表7所示.

表7 成績等級劃分Table 7 The hierarchy of results

源數(shù)據(jù)：1條源數(shù)據(jù)由1個學(xué)生每個學(xué)期所修課程成績組成.即1條記錄有8個元素.每一列數(shù)據(jù)代表1個同學(xué)8個學(xué)期的所有課程.

2.2 算法應(yīng)用與結(jié)果分析

不同專業(yè)的學(xué)生在不同的最小支持度minsup和最小并發(fā)度mincon下(本實驗中minsup=mincon)，挖掘不同成績等級下的并發(fā)序列模式結(jié)果曲線如圖2所示.從圖2可以看出：不同專業(yè)的學(xué)生，在不同的并發(fā)度和支持度下，挖掘得到的課程成績并發(fā)序列模式的并發(fā)趨勢大體相同，隨著并發(fā)度和支持度的不斷增大，在某一取值處達(dá)到峰值，然后逐漸減少.在并發(fā)度較小時，序列模式挖掘得到的序列模式數(shù)比較多；當(dāng)并發(fā)度較大時,由于序列模式挖掘階段得到序列模式數(shù)相對減少，變化趨勢減弱.從圖2(d)可以看出，信息專業(yè)的學(xué)生成績按三級制分級時，在并發(fā)度為0.2處取得峰值，在并發(fā)度為0.4處再次取得峰值.這是因為在此支持度下，序列模式挖掘得到的序列模式數(shù)比較多，從而導(dǎo)致再次出現(xiàn)峰值.

軟件專業(yè)共111人，在最小支持度minsup=0.2,最小并發(fā)度 mincon=0.2，成績等級五級制時，挖掘得到的并發(fā)序列模式數(shù)相對較多，結(jié)果比較有代表性，挖掘結(jié)果如圖3所示，這些并發(fā)序列模式揭示了不同科目取得成績之間的關(guān)系.

圖2 不同專業(yè)的并發(fā)序列模式數(shù)變化曲線Fig.2 The CPS chart of different specialty

圖3 軟件專業(yè)成績并發(fā)關(guān)系Fig.3 The concurrent relation of software

上述實驗結(jié)果說明，日常教學(xué)活動中BV算法在學(xué)生成績中的應(yīng)用可以得到有指導(dǎo)意義的結(jié)論，即提高學(xué)生成績應(yīng)該采用以下教學(xué)措施：

(1) 計算機(jī)網(wǎng)絡(luò)和操作系統(tǒng)安排在同一學(xué)期，計算機(jī)組成原理安排在二者之后，或者計算機(jī)網(wǎng)絡(luò)和計算機(jī)組成原理安排在前，操作系統(tǒng)安排在后.這是因為在計算機(jī)網(wǎng)絡(luò)得B，操作系統(tǒng)得B時，會同時出現(xiàn)計算機(jī)組成原理得B.

(2) 同理可知，數(shù)據(jù)結(jié)構(gòu)、C語言程序設(shè)計和C語言實踐應(yīng)該安排在同一學(xué)期，JAVA語言和J2EE安排在后面的學(xué)期，或者數(shù)據(jù)結(jié)構(gòu)、JAVA語言和J2EE安排在同一學(xué)期，C語言程序設(shè)計安排在后一學(xué)期.

(3) 大學(xué)外語3和編譯原理安排在同一學(xué)期，離散數(shù)學(xué)安排在后一學(xué)期，或者大學(xué)外語3和離散數(shù)學(xué)安排在同一學(xué)期，編譯原理安排在后一學(xué)期.

(4) 高數(shù)2和離散數(shù)學(xué)安排在同一學(xué)期，組件技術(shù)安排在后一學(xué)期，或者高數(shù)2和組件技術(shù)安排在同一學(xué)期，離散數(shù)學(xué)安排在后一學(xué)期.

(5) 高數(shù)2和計算機(jī)科學(xué)導(dǎo)論安排在同一學(xué)期，C語言程序設(shè)計和C語言實踐安排在后一學(xué)期，或者C語言程序設(shè)計和C語言實踐安排在同一學(xué)期，高數(shù)2和計算機(jī)科學(xué)導(dǎo)論后一學(xué)期.

3 結(jié)束語

并發(fā)性是研究系統(tǒng)行為的重要特性，本研究將并發(fā)序列模式挖掘應(yīng)用于高校學(xué)生成績分析，有助于發(fā)現(xiàn)學(xué)生成績背后所隱藏的有價值信息，從而進(jìn)一步深化教學(xué)改革.同時，研究出了BV并發(fā)算法，與現(xiàn)有算法相比，在算法效率上有了更進(jìn)一步的提高，并且找到學(xué)生課程學(xué)習(xí)效果之間的并發(fā)關(guān)系，更加完善了成績預(yù)測模型.