史巧碩，周慧霞，李楊，李娟

（1.河北工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300401；2.河北工業(yè)大學(xué)控制科學(xué)與工程學(xué)院，天津 300401）

回歸方法估算最長(zhǎng)頻繁模式長(zhǎng)度

史巧碩1，周慧霞1，李楊2，李娟1

（1.河北工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300401；2.河北工業(yè)大學(xué)控制科學(xué)與工程學(xué)院，天津 300401）

周期間隙的序列模式挖掘是一種滿(mǎn)足Apriori-like性質(zhì)的序列模式挖掘，其中一項(xiàng)重要工作就是預(yù)測(cè)最長(zhǎng)頻繁模式的長(zhǎng)度．以往需要人為估計(jì)，本文采用回歸方法解決這個(gè)問(wèn)題．本文提出一種有效的特征抽取的方法，以獲取訓(xùn)練和測(cè)試數(shù)據(jù)．之后分別采用BP神經(jīng)網(wǎng)絡(luò)、最小二乘支持向量機(jī)和極限學(xué)習(xí)機(jī)進(jìn)行訓(xùn)練和測(cè)試．在DNA序列上進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果表明，ELM具有良好的泛化性能，從而驗(yàn)證了方法的可行性．

序列模式挖掘；BP神經(jīng)網(wǎng)絡(luò)；最小二乘支持向量機(jī)；極限學(xué)習(xí)機(jī)

machine

0 引言

隨著序列模式應(yīng)用領(lǐng)域越來(lái)越細(xì)化，傳統(tǒng)的序列模式挖掘技術(shù)已經(jīng)不能滿(mǎn)足新的挖掘和分析的需求，具有間隙約束的序列模式挖掘是一種特殊形式的序列模式挖掘，是在給定的序列中挖掘出形如a1[M，N]a2[M，N]…am-1[M，N]am的頻繁模式，并使其支持率大于給定的閾值[1]，其中M和N分別代表模式中兩個(gè)字符之間允許的最小間隔和最大間隔，間隔中的字符可以為任意字符，因此這是一種較傳統(tǒng)的通配符“？”和“*”更加靈活的通配符[2-3]，因?yàn)槿绻鸐與N相同，則可以表示M個(gè)“？”；如果M與N分別為0和∞，則可以表示一個(gè)“*”．這種間隙約束的存在，一方面使得用戶(hù)可根據(jù)自身的需要，靈活地設(shè)定挖掘模式的條件；另一方面可以避免大量無(wú)意義的模式被挖掘[1]．由于周期間隙約束的序列模式挖掘能夠有效地發(fā)現(xiàn)具有周期特性的頻繁模式，因而吸引了人們的廣泛關(guān)注，并成為序列模式挖掘的一個(gè)重要的研究方向，并且在生物基因序列、Bug挖掘、商業(yè)領(lǐng)域、運(yùn)動(dòng)模式分析等方面都有著廣泛的應(yīng)用[4-5]．這類(lèi)模式挖掘不僅處理難度更高，而且復(fù)雜度多變，目前存在3種形式：一次性條件[1]、無(wú)重疊條件[6]和無(wú)特殊條件[7-8]．盡管基于一次性條件和無(wú)重疊條件的周期間隙序列模式挖掘滿(mǎn)足Apriori性質(zhì)，但是由于不能精確地計(jì)算一個(gè)模式在序列中的支持?jǐn)?shù)[1,6]，因而都屬于一種近似挖掘算法；無(wú)特殊條件的周期間隙序列模式挖掘（簡(jiǎn)稱(chēng)周期間隙序列模式挖掘）雖然可以精確地計(jì)算一個(gè)模式在序列中的支持?jǐn)?shù)，是一種精確挖掘，但是需要采用Apriori-like性質(zhì)進(jìn)行挖掘[7-8]，需先驗(yàn)地估計(jì)序列的最長(zhǎng)頻繁模式長(zhǎng)度，如果最長(zhǎng)頻繁模式估計(jì)過(guò)短，則會(huì)有更長(zhǎng)頻繁模式不能被挖掘；如果最長(zhǎng)頻繁模式估計(jì)過(guò)長(zhǎng)，則會(huì)進(jìn)行大量的無(wú)效挖掘，降低算法的挖掘速度．為了有效地克服人為估計(jì)的不足，本文采用機(jī)器學(xué)習(xí)的方法對(duì)最長(zhǎng)頻繁模式長(zhǎng)度進(jìn)行回歸估計(jì)研究．

本文結(jié)構(gòu)如下：第1節(jié)給出了序列模式挖掘的定義，之后介紹了本文的特征提取方法；第2節(jié)簡(jiǎn)要的介紹了本文所使用的3種回歸算法；第3節(jié)給出了實(shí)驗(yàn)結(jié)果與分析；第4節(jié)得出本文結(jié)論．

1 序列模式挖掘和特征提取

1.1 周期間隙的序列模式挖掘

定義1（目標(biāo)序列）把從中提取頻繁模式的字符序列S=s1s2…sn稱(chēng)為目標(biāo)序列[7-8]．令∑表示所有可能出現(xiàn)在目標(biāo)序列中的字母表．例如若∑={a，g，t，c}對(duì)應(yīng)于DNA序列，而對(duì)于蛋白質(zhì)序列，∑表示的是20種氨基酸．

定義2（模式[1-3]）1個(gè)模式P=a1[M，N]a2[M，N]…am-1[M，N]am是由字符和間隙組成的序列，其中1≤i≤m，ai∈∑，M和N分別表示兩個(gè)字符間通配符可以通配的最小間隙和最大間隙，m是模式P的長(zhǎng)度．

定義3（偏移序列）偏移序列是1個(gè)下標(biāo)序列D=＜d1，d2，…，dm＞，該序列滿(mǎn)足模式P的間隙約束，偏移序列總數(shù)ofs(P，S)是P在S中的最大可能數(shù)．

定義4（出現(xiàn)，支持?jǐn)?shù)）出現(xiàn)I=＜i1，…，ij，…，im＞是在偏移序列基礎(chǔ)上，滿(mǎn)足Sij=pj（1≤j≤m and 0≤ij≤n）．支持?jǐn)?shù)sup(P，S)是P在S中的出現(xiàn)總數(shù)．

定義5（頻繁模式）如果模式P的支持率r P,S=sup P,S/ofs P,S不小于用戶(hù)給定的閾值，那么P是1個(gè)頻繁模式，否則P是1個(gè)非頻繁模式．

例如給定序列S=agttt，模式P=a[0，3]g，P的超模式Q=T[0，3]C[0，3]G．可知P和Q的出現(xiàn)分別為＜1，2＞及＜1，2，3＞，＜1，2，4＞和＜1，2，5＞，即sup(P，S)=1和sup(Q，S)=3．所以1個(gè)模式的支持?jǐn)?shù)小于其超模式的支持?jǐn)?shù)．P在S中的偏移序列為＜1，2＞，＜1，3＞，＜1，4＞，＜1，5＞，＜2，3＞，＜2，4＞，＜2，5＞，＜3，4＞，＜3，5＞和＜4，5＞，Q在S中的偏移序列為＜1，2，3＞，＜1，2，4＞，＜1，2，5＞，＜1，3，4＞，＜1，3，5＞，＜1，4，5＞，＜2，3，4＞，＜2，3，5＞，＜2，4，5＞和＜3，4，5＞，ofs(P，S)和ofs(Q，S)均為10，因此r(P，S)＜r(Q，S)．因此周期間隙約束的序列模式挖掘需要采用Apriori-like性質(zhì)挖掘頻繁模式．這需要預(yù)先對(duì)序列的最長(zhǎng)頻繁模式的長(zhǎng)度進(jìn)行人為估計(jì)，如果該值小于實(shí)際最長(zhǎng)頻繁模式長(zhǎng)度，會(huì)導(dǎo)致最長(zhǎng)頻繁模式不能被挖掘；如果該值大于實(shí)際最長(zhǎng)頻繁模式長(zhǎng)度，則會(huì)有大量候選模式被檢測(cè)，進(jìn)而導(dǎo)致挖掘速度的下降．為了避免人為估計(jì)的不足，采用機(jī)器學(xué)習(xí)的方法解決此問(wèn)題．下面小節(jié)將要介紹本文使用的特征提取方法．

1.2 特征提取

本文擬解決的問(wèn)題是在給定兩個(gè)整數(shù)間隙M和N，在指定字符序列S上估算最長(zhǎng)頻繁模式P的長(zhǎng)度m．而機(jī)器學(xué)習(xí)方法不能直接對(duì)字符序列進(jìn)行回歸，需要依據(jù)S，M和N進(jìn)行特征提取，為了最大限度保證提取的特征與求解的問(wèn)題相吻合，本文提出了統(tǒng)計(jì)長(zhǎng)度為2的所有模式在序列中出現(xiàn)數(shù)的形式作為問(wèn)題的特征．具體求解步驟如下

1）統(tǒng)計(jì)模式a1M,N a2在序列中的出現(xiàn)次數(shù)F a1M,N a2，這里F函數(shù)表示子模式在序列中的出現(xiàn)次數(shù)，其計(jì)算公式如下．

其中：模式a1i a2是兩個(gè)字符a1和a2之間有i個(gè)通配符；F a1i a2是模式a1i a2在序列S中的出現(xiàn)次數(shù)．

3）第|∑|*|∑|+1維特征向量采用序列模式挖掘的頻繁度閾值；

4）回歸的目標(biāo)為采用MAPD算法[7]挖掘到的頻繁模式獲得最長(zhǎng)頻繁模式長(zhǎng)度（該算法可從http:// wuc.scse.hebut.edu.cn/msppwg/index.html獲?。?/p>

例如在DNA序列中，∑是由{a，g，t，c}共4種字符所構(gòu)成的，因此在DNA序列上，前4×4=16維向量采用上述步驟1）和2）獲得，下面舉例說(shuō)明特征提取方法．

給定目標(biāo)序列S=ttcctccgcgaaggctcctt，設(shè)定間隙[M,N]為[0，3]．

首先掃描目標(biāo)序列S，得到aa，a·a，a·a，a··a（其中‘·’表示通配符）在S中出現(xiàn)的次數(shù)分別為1、0、0和0，將此4個(gè)數(shù)值累加得到a[0，3]a在S中出現(xiàn)的次數(shù)為1．

然后，依次統(tǒng)計(jì)a[0，3]g，a[0，3]t，a[0，3]c，g[0，3]a，g[0，3]g，g[0，3]t，g[0，3]c，t[0，3]a，t[0，3]g，t[0，3]t，t[0，3]c，c[0，3]a，c[0，3]g，c[0，3]t，c[0，3]c在S中出現(xiàn)的次數(shù)，分別為4、1、2、4、4、2、6、0、1、6、10、3、7、8和11．這樣就得到了16維的模式長(zhǎng)度為2的一組統(tǒng)計(jì)數(shù)據(jù){1，4，1，2，4，4，2，6，0，1，6，10，3，7，8，11}，當(dāng)間隙M和N變化時(shí)，這16維數(shù)據(jù)會(huì)相應(yīng)發(fā)生改變．而數(shù)據(jù)的第17維和回歸目標(biāo)分別按照步驟3）和4）獲得．

2 3種回歸算法

2.1 BP神經(jīng)網(wǎng)絡(luò)

基于梯度下降法的BP存在以下缺點(diǎn)：1）訓(xùn)練速度慢．因?yàn)樾枰啻蔚牡?，所以時(shí)間消耗很長(zhǎng)；2）參數(shù)選擇很敏感，必須選取合適的初值，才能取得理想的結(jié)果．若太小，算法收斂很慢，而太大，算法不太穩(wěn)定甚至不再收斂；3）局部最小值．由于E W非凸，因此在下降過(guò)程中可能會(huì)陷入局部最小點(diǎn)，無(wú)法達(dá)到全局最??；4）過(guò)渡擬合．在有限樣本上訓(xùn)練時(shí)，僅以訓(xùn)練誤差最小為目標(biāo)的訓(xùn)練可能導(dǎo)致過(guò)渡擬合．2.2最小二乘支持向量機(jī)（LS-SVM）

最小二乘支持向量機(jī)[9]是對(duì)標(biāo)準(zhǔn)SVM的一種擴(kuò)展．與傳統(tǒng)的SVM不同，它是將傳統(tǒng)的支持向量機(jī)中的不等式約束改為等式約束，且將誤差平方和損失函數(shù)作為訓(xùn)練集的經(jīng)驗(yàn)損失，這樣LS-SVM算法就將SVM的求解從二次規(guī)劃問(wèn)題轉(zhuǎn)換為求解線(xiàn)性方程組問(wèn)題，提高了SVM的求解效率，降低了SVM的學(xué)習(xí)難度．

2.3 極限學(xué)習(xí)機(jī)（ELM）

為了解決BP出現(xiàn)問(wèn)題，Huang等人[10-11]提出了ELM算法，ELM算法是一種新型的單隱層反饋網(wǎng)絡(luò)．與SVM和傳統(tǒng)神經(jīng)網(wǎng)絡(luò)相比，ELM的訓(xùn)練速度非?？欤枰斯じ蓴_較少，對(duì)于異質(zhì)的數(shù)據(jù)集其泛化能力很強(qiáng)．該方法通過(guò)設(shè)置合適的隱藏層結(jié)點(diǎn)數(shù)，為輸入權(quán)和隱藏層偏差進(jìn)行隨機(jī)賦值，然后輸出層權(quán)值通過(guò)最小二乘法得到，整個(gè)過(guò)程一次完成，無(wú)需迭代，因而具有較快的學(xué)習(xí)速度[11-12]，其網(wǎng)絡(luò)輸出函數(shù)可表示為：

其中：G x,aj,bj為第j個(gè)隱層結(jié)點(diǎn)的輸出函數(shù)；j為第j個(gè)隱層結(jié)點(diǎn)到輸出結(jié)點(diǎn)的連接權(quán)值．與其他多種機(jī)器學(xué)習(xí)方法相似，ELM的隱層結(jié)點(diǎn)輸出函數(shù)可以有多種類(lèi)型，如加性結(jié)點(diǎn)和徑向基函數(shù)（RBF）結(jié)點(diǎn)等．

3 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)數(shù)據(jù)是從生物信息中心網(wǎng)站下載的人類(lèi)DNA序列（AX829174，AL158070，AB038490），實(shí)驗(yàn)數(shù)據(jù)可分別從http://www.ncbi.nlm.nih.gov/nuccore/AX829174，http://www.ncbi.nlm.nih.gov/nuccore/AL158070.11和http://www.ncbi.nlm.nih.gov/nuccore/AB038490下載．實(shí)驗(yàn)運(yùn)行環(huán)境為Intel（R）core（TM）i3CPU，2.00GB內(nèi)存的計(jì)算機(jī)上．本文通過(guò)不同長(zhǎng)度變化，將上述三組DNA序列變化為11個(gè)DNA序列，其中S1～S5序列取自AX829174序列，長(zhǎng)度分別為1 000、2 000、4 000、8 000以及AX829174序列的實(shí)際長(zhǎng)度10 011；S68序列取自AL158070序列，長(zhǎng)度分別為20 000、40 000和80 000；S911序列取自AB038490序列，長(zhǎng)度分別為15 000、30 000和60 000．

3.1 閾值與間隙變化下回歸最長(zhǎng)頻繁模式長(zhǎng)度的實(shí)驗(yàn)結(jié)果分析

通過(guò)采用1.2節(jié)的特征抽取方法，依據(jù)給定閾值和間隙約束，在S1序列上獲得了數(shù)據(jù)集F1，該數(shù)據(jù)集共有150條數(shù)據(jù)，隨機(jī)選擇其中的100條數(shù)據(jù)用于訓(xùn)練，剩余的50條數(shù)據(jù)用于測(cè)試．對(duì)于S2～S11序列，采用同種方法隨機(jī)產(chǎn)生50條測(cè)試數(shù)據(jù)，用于驗(yàn)證F1數(shù)據(jù)集的學(xué)習(xí)模型是否可以應(yīng)用到其它序列中，S2～S11序列產(chǎn)生的測(cè)試數(shù)據(jù)集分別為F2，F(xiàn)3，…，F(xiàn)11．

利用3種回歸算法在F1數(shù)據(jù)集上測(cè)試結(jié)果如圖1和表1所示，在F2～F11數(shù)據(jù)集上進(jìn)行測(cè)試的均方誤差如表2所示．

圖1 F1數(shù)據(jù)集測(cè)試絕對(duì)誤差圖Fig.1Testing absolute error of data set F1

從圖1和表1可以看出，BP神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)效果最好，但訓(xùn)練時(shí)間將近是其它兩種算法的2000倍，而且從F1數(shù)據(jù)集的測(cè)試結(jié)果來(lái)看，由于BP神經(jīng)網(wǎng)絡(luò)的不穩(wěn)定性，它測(cè)試的均方誤差比ELM大15倍，這說(shuō)明不能用BP神經(jīng)網(wǎng)絡(luò)來(lái)預(yù)測(cè)最長(zhǎng)頻繁模式長(zhǎng)度，它嚴(yán)重不符合實(shí)際值．說(shuō)明BP神經(jīng)網(wǎng)路陷入過(guò)學(xué)習(xí)問(wèn)題．而ELM算法具有較好學(xué)習(xí)速度，并且泛化能力強(qiáng)．從表1中看出，ELM的訓(xùn)練時(shí)間僅為11.083ms，而且測(cè)試的均方誤差僅為0.582，說(shuō)明ELM算法具有很好的穩(wěn)定性．不僅如此，在表2中ELM算法在其余10個(gè)測(cè)試集合上測(cè)試均方誤差均好于其他兩種學(xué)習(xí)算法，反應(yīng)出ELM算法具有良好的穩(wěn)定性．

表13 種算法在F1數(shù)據(jù)集的訓(xùn)練與測(cè)試比較表Tab.1Comparison of the training and testing results of 3 algorithms on data set F1

表2 F2～F11數(shù)據(jù)集在F1學(xué)習(xí)模型上的測(cè)試均方誤差對(duì)比表%Tab.2Comparison of testing measure square error of data sets F2～F11 on learning model F1

3.2 閾值與序列變化下回歸最長(zhǎng)頻繁模式長(zhǎng)度的實(shí)驗(yàn)結(jié)果分析

為了探究閾值和序列變化對(duì)最長(zhǎng)頻繁模式長(zhǎng)度的影響，對(duì)[9，12]這個(gè)間隙下產(chǎn)生的數(shù)據(jù)集進(jìn)行了學(xué)習(xí)和測(cè)試，為了驗(yàn)證這一學(xué)習(xí)模型，又分別用[0，4]，[3，9]，[5，10]，[8，11]，[10，13]對(duì)其進(jìn)行測(cè)試．

設(shè)定間隙為[9，12]，保持不變，在S1～S11共11個(gè)序列上，通過(guò)閾值和序列變化利用MAPD算法進(jìn)行序列模式挖掘，再利用1.2節(jié)的特征提取，隨機(jī)產(chǎn)生50條訓(xùn)練數(shù)據(jù)和20條測(cè)試數(shù)據(jù)，得到實(shí)驗(yàn)所需的數(shù)據(jù)集F9_12，與3.1節(jié)的數(shù)據(jù)集相類(lèi)似，3.1節(jié)的數(shù)據(jù)集是閾值和間隙變化，而本小節(jié)實(shí)驗(yàn)中的數(shù)據(jù)集是閾值和序列變化，最后還是要預(yù)測(cè)最長(zhǎng)頻繁模式長(zhǎng)度．為了驗(yàn)證該學(xué)習(xí)模型，分別用[0，4]，[3，9]，[5，10]，[8，11]，[10，13]這5個(gè)間隙進(jìn)行測(cè)試，通過(guò)閾值和序列變化，在每個(gè)間隙下隨機(jī)產(chǎn)生20條測(cè)試數(shù)據(jù)組成5組測(cè)試數(shù)據(jù)集，分別為F0_4，F(xiàn)3_9，F(xiàn)5_10，F(xiàn)8_11，F(xiàn)10_13．F9_12數(shù)據(jù)集的學(xué)習(xí)和測(cè)試結(jié)果如圖2和表3所示，F(xiàn)0_4，F(xiàn)3_9，F(xiàn)5_10，F(xiàn)8_11，F(xiàn)10_13數(shù)據(jù)集在[9，12]數(shù)據(jù)集上進(jìn)行測(cè)試的結(jié)果如表4所示．

圖2 F9_12數(shù)據(jù)集測(cè)試絕對(duì)誤差圖Fig.2Testing absolute error of data set F9_12

從圖2和表3與表4可以看出，與上一小節(jié)的實(shí)驗(yàn)結(jié)果相似，ELM算法無(wú)論是在訓(xùn)練時(shí)間上和泛化能力方面均好于BP神經(jīng)網(wǎng)絡(luò)以及LS-SVM算法，并能夠有效地避免過(guò)學(xué)習(xí)問(wèn)題．從表3中可以看出，ELM算法的訓(xùn)練速度大大高于其他兩種方法，其訓(xùn)練時(shí)間僅為5ms左右，而其他兩種算法分別9000ms和17ms左右．此外ELM算法不僅在F9_12數(shù)據(jù)集上測(cè)試均方誤差好于其他兩種算法，而且從表4中可以看出，其在其他多種測(cè)試集上均好于其他兩種算法，例如在F0_4數(shù)據(jù)上，ELM算法測(cè)試均方誤差為1.1，而其他兩種算法均高于此值．這充分地說(shuō)明了采用機(jī)器學(xué)習(xí)方法可以有效地估算最長(zhǎng)頻繁模式長(zhǎng)度．

表33 種算法在F9_12數(shù)據(jù)集的訓(xùn)練與測(cè)試比較表Tab.3Comparison of the training and testing results of 3 algorithms on data set F9_12

表4 其他數(shù)據(jù)集在F9_12學(xué)習(xí)模型上的測(cè)試均方誤差對(duì)比表%Tab.4Comparison of testing measure square error of data sets on learning model F9_12

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

為了有效地解決周期間隙的序列模式挖掘中最長(zhǎng)頻繁模式長(zhǎng)度需要人為估算的問(wèn)題，本文采用機(jī)器學(xué)習(xí)的方法有效地估算最長(zhǎng)頻繁模式．本文采取了統(tǒng)計(jì)長(zhǎng)度為2的模式串在序列中出現(xiàn)數(shù)的方式，實(shí)現(xiàn)對(duì)字符序列進(jìn)行有效地特征提取，然后分別采用BP神經(jīng)網(wǎng)絡(luò)、LS-SVM和ELM共3種機(jī)器學(xué)習(xí)算法實(shí)現(xiàn)對(duì)最長(zhǎng)頻繁模式長(zhǎng)度進(jìn)行了訓(xùn)練及測(cè)試．在DNA序列上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，采用ELM算法具有良好的學(xué)習(xí)速度和泛化能力，有效地解決了人為估計(jì)最長(zhǎng)頻繁模式長(zhǎng)度問(wèn)題．

為了進(jìn)一步提高估算的準(zhǔn)確率，未來(lái)將嘗試新的特征提取方法，如將長(zhǎng)度為3的模式子串的出現(xiàn)數(shù)也作為特征的方式進(jìn)行特征提?。?/p>

[1]吳信東，謝飛，黃詠明，等．帶通配符和One-Off條件的序列模式挖掘[J]．軟件學(xué)報(bào)，2013，24（8）：1804-1815．

[2]武優(yōu)西，劉亞偉，郭磊，等．子網(wǎng)樹(shù)求解一般間隙和長(zhǎng)度約束嚴(yán)格模式匹配[J]．軟件學(xué)報(bào)，2013，24（5）：915-932．

[3]武優(yōu)西，吳信東，江賀，等．一種求解MPMGOOC問(wèn)題的啟發(fā)式算法[J]．計(jì)算機(jī)學(xué)報(bào)，2011，34（8）：1452-1462．

[4]XuanJ，JiangH，HuY，etal．Towardseffectivebugtriagewithsoftwaredatareductiontechniques[J]．IEEE TransactionsonKnowledgeandData Engineering，2015，27（1）：264-280．

[5]Yen S J，Lee Y S．Mining non-redundant time-gap sequential patterns[J]．Applied Intelligence，2013，39（4）：727-738．

[6]Ding B，LoD，Han J，et al．Efficient miningof closedrepetitivegappedsubsequences from asequence database[C]．In：IEEE 25thInternational Conference on Data Engineering（ICDE'2009），Shanghai，China，2009：1024-1035．

[7]Wu Y，Wang L，Ren J，et al．Mining sequential patterns with periodic wildcard gaps[J]．Applied Intelligence，2014：41（1）：99-116．

[8]ZhangM，KaoB，CheungD，etal．Miningperiodicpatternswithgaprequirementfromsequences[J]．ACM TransactionsonKnowledgeDiscovery from Data（TKDD），2007，1（2）：7-es．

[9]Suykens J A K，Vandewalle J．Least squares support vector machine classifiers[J]．Neural processing letters，1999，9（3）：293-300．

[10]Huang GB，Zhu QY，Siew CK．Extreme learning machine：Theory and applications[J]．Neurocomputing，2006，70（1-3）：489-501．

[11]HuangGB．Learningcapabilityandstoragecapacityoftwohidden-layerfeedforwardnetworks[J]．IEEETransactionsonNeuralNetworks，2003，14（2）：274-281．

[12]鄧萬(wàn)宇，鄭慶華，陳琳，等．神經(jīng)網(wǎng)絡(luò)極速學(xué)習(xí)方法研究[J]．計(jì)算機(jī)學(xué)報(bào)，2010，33（2）：279-287．

[責(zé)任編輯 田豐夏紅梅]

Using regression methods to estimate the length of the longest frequent patterns

SHI Qiaoshuo1，ZHOU Huixia1，LI Yang2，LI Juan1

(1.School of Computer Science and Engineering,Hebei University of Technology,Tianjin 300401,China;2.School of Control Science and Engineering,Hebei University of Technology,Tianjin 300401,China)

Predicting thelength of longestfrequentpatternsisan importanttask of sequential patterns miningwith periodic wildcard gaps which satisfies the Apriori-like property.The traditional method is to estimate the length artificially.To tackle this problem,the regression methods are employed.An effective method for feature selection is presented to obtain the training and testing data sets.Then BP neural network,Least Squares Support Vector Machines(LS-SVM),and Extreme Learning Machine(ELM)are employed respectively for the data training and testing.Experiments on DNAsequences confirm that ELM has better performance than other competitive algorithms and experimental results show the method is feasible.

sequential patterns mining;BP neural network;least squares support vector machine;extreme learning

TP319

A

1007-2373(2015)05-0045-06

10.14081/j.cnki.hgdxb.2015.05.009

2015-01-03

河北省自然科學(xué)基金（F2013202138）；河北省教育廳重點(diǎn)項(xiàng)目（ZH2012038）；河北省教育廳青年基金（QN2014192）

史巧碩（1974-），女（漢族），副教授．

數(shù)字出版日期：2015-10-19數(shù)字出版網(wǎng)址：http://www.cnki.net/kcms/detail/13.1208.T.20151019.1031.010.html