王翠青, 楊曉彤, 陳未如

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

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

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

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

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

1.1 基本概念

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

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

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

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

由表1可以看出，序列(Ma)(Oa)(Xa)和(Na)(Qb)(Yb)同時(shí)出現(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 %時(shí)，挖掘序列模式得到的長(zhǎng)度≥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ù)庫(kù),SP={sp1,sp2,…,spm}是序列模式挖掘階段在給定的最小支持度minsup下得到的序列模式集合.

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

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

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

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

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

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

算法描述：

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

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

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

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

(3) 調(diào)用BVCON(1)，求得并發(fā)集.若Count(BV)表示計(jì)算分支向量BV中1的個(gè)數(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)

//若同時(shí)存在兩個(gè)序列模式

BVCON(k+1);

c--;

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

BVCON(k+1);

}

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

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

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

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

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

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

1.3 算法驗(yàn)證

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

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

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

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

2 學(xué)生成績(jī)的挖掘?qū)嶒?yàn)

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

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

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

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

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

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

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

表7 成績(jī)等級(jí)劃分Table 7 The hierarchy of results

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語(yǔ)

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