程鈴鈁，郭躬德，陳黎飛

(1.福建農(nóng)林大學 金山學院，福州 350002； 2.福建師范大學 數(shù)學與計算機科學學院，福州 350117) (*通信作者電子郵箱clfei@fjnu.edu.cn)

符號序列多階Markov分類

程鈴鈁1，郭躬德2，陳黎飛2*

(1.福建農(nóng)林大學 金山學院，福州 350002； 2.福建師范大學 數(shù)學與計算機科學學院，福州 350117) (*通信作者電子郵箱clfei@fjnu.edu.cn)

針對基于固定階Markov鏈模型的方法不能充分利用不同階次子序列結(jié)構(gòu)特征的問題，提出一種基于多階Markov模型的符號序列貝葉斯分類新方法。首先，建立了基于多階次Markov模型的條件概率分布模型；其次，提出一種附后綴表的n-階子序列后綴樹結(jié)構(gòu)和高效的樹構(gòu)造算法，該算法能夠在掃描一遍序列集過程中建立多階條件概率模型；最后，提出符號序列的貝葉斯分類器，其訓練算法基于最大似然法學習不同階次模型的權(quán)重，分類算法使用各階次的加權(quán)條件概率進行貝葉斯分類預測。在三個應(yīng)用領(lǐng)域?qū)嶋H序列集上進行了系列實驗，結(jié)果表明：新分類器對模型階數(shù)變化不敏感；與使用固定階模型的支持向量機等現(xiàn)有方法相比，所提方法在基因序列與語音序列上可以取得40%以上的分類精度提升，且可輸出符號序列Markov模型最優(yōu)階數(shù)參考值。

符號序列；Markov鏈模型；多階模型；貝葉斯分類；后綴樹

0 引言

符號序列是一種由類屬型(離散型)符號組成的線性鏈，許多應(yīng)用領(lǐng)域的數(shù)據(jù)挖掘?qū)ο笠赃@種復雜類型的數(shù)據(jù)表示。例如，在銀行信用卡客戶管理中，用一些離散符號表示客戶行為時，客戶在一段時間內(nèi)的行為即構(gòu)成一條符號序列。本文研究符號序列分類問題，通過序列中各種符號及其順序關(guān)系的監(jiān)督學習，預測數(shù)據(jù)對象的類別標號，在基于行為序列的銀行客戶破產(chǎn)風險預測等領(lǐng)域具有廣泛的應(yīng)用[1-2]。

文獻中已提出多種分類方法，包括決策樹、近鄰(Nearest Neighbour, NN)分類、支持向量機(Support Vector Machine, SVM)及基于概率模型的分類等機器學習方法[3-4]，以及人工神經(jīng)網(wǎng)絡(luò)等智能計算方法[5-6]。盡管這些方法已得到廣泛研究和應(yīng)用，但它們多針對向量型數(shù)據(jù)，即假設(shè)每個數(shù)據(jù)對象都已經(jīng)映射為某個定義完好的特征空間中的向量。有兩種途徑可以將現(xiàn)有方法用于挖掘含有結(jié)構(gòu)信息的符號序列：一種方案提取符號序列的結(jié)構(gòu)特征，以構(gòu)造序列的向量空間模型[1-2,7]；另一種方案定義能夠體現(xiàn)序列結(jié)構(gòu)特征的序列距離度量[8-9]、概率模型[10-11]等，從而可以將相關(guān)方法推廣到符號序列。

現(xiàn)有兩類主要方法用于提取序列的結(jié)構(gòu)特征：子序列法和概率模型法。前者以n-gram(n-元組)為代表[1-2,7,12]，目的是提取蘊含在序列中的局部結(jié)構(gòu)信息，后者通過Markov模型(馬爾可夫模型)[10,13-14]、隱Markov模型[15]等概率模型刻畫序列中的全局結(jié)構(gòu)信息。所述n-gram是序列中n個連續(xù)符號構(gòu)成的短子序列——實際上，相當于n-階Markov模型中的前綴子序列[16]。從這個意義上說，n-gram方法是Markov模型的一種應(yīng)用[13]。當前，基于Markov模型的分類器已成為符號序列分類的主要工具之一[1-2,10,13-15]。

實際進行符號序列Markov分類時，需要面對如何確定模型階數(shù)n等難題[10-11,13]。由于階數(shù)n與所提取的序列結(jié)構(gòu)特征息息相關(guān)，該重要參數(shù)的選擇將直接影響分類器的性能。文獻中已提出少量的估計方法，例如文獻[17]給出的最長公共子序列期望長度估計，但該方法僅針對DNA和蛋白質(zhì)序列，且僅作用于序列對而非整個序列集。由于當前尚缺乏給定序列集最優(yōu)模型階數(shù)的有效估計方法[13,16]，在實際應(yīng)用中，通常由用戶經(jīng)驗地設(shè)定n或基于交叉驗證法等“試錯”機制，在一定范圍內(nèi)選擇產(chǎn)生最高分類質(zhì)量的特定值。事實上，在現(xiàn)有方法中，一旦給定了n，就僅利用固定階次的子序列(n-階Markov模型)進行序列分類，這意味著忽略其他階次子序列中的結(jié)構(gòu)信息，必然影響符號序列Markov分類的性能。

本文提出一種符號序列的多階Markov分類方法。新方法基于多階Markov模型，同時利用了1,2,…,n-階子序列，以提高符號序列的分類性能。在新提出的“階加權(quán)”貝葉斯分類器(Order-Weighting Bayesian Classifier， OWBC)中，訓練算法學習各階次條件概率分布模型及各階次的權(quán)重，分類算法則基于加權(quán)的多階條件概率進行貝葉斯推斷。在來自不同應(yīng)用領(lǐng)域的實際序列集上進行了實驗驗證，實驗結(jié)果表明，新分類器對模型的預設(shè)階數(shù)n是魯棒的，與現(xiàn)有采用固定階Markov模型的方法相比，有效提高了分類精度。

1 相關(guān)工作

首先約定全文使用的記號。令Tr表示由N個樣本構(gòu)成的訓練數(shù)據(jù)集，每個樣本是一個二元組(S,k)，其中S表示符號序列，k∈[1,K]是序列S的類別標號，K為類別數(shù)。序列S的長度記為L，即S由L個符號排列而成，表示為S=s1s2…sl…sL。所有符號的集合記為X，|X|表示其中的符號數(shù)；因此，sl∈X(l=1,2,…,L)。

(1)

(2)

其中fk(t)表示子序列t在第k個訓練類別包括的所有序列中出現(xiàn)的次數(shù)。

文獻中有兩種主要方式在序列挖掘中應(yīng)用上述Markov鏈模型。第一種方式基于Markov模型定義序列間的相似性度量，繼而進行基于相似性的序列挖掘。一種常見的實現(xiàn)方式是計算兩個序列S和S′間的距離為概率分布P(S)和P(S′)間的差異，涉及的度量包括K-L(Kullback-Leible)散度、Hellinger距離[10,13]等；另一種間接利用Markov模型的實現(xiàn)是構(gòu)造序列的n-gram表示模型[1-2,12-13]：先將每個序列映射為(以n-gram為特征的)向量空間的一個向量，再以向量間的歐幾里得距離等衡量序列間的差異[7]?；谶@樣的表示模型，近鄰(Nearest Neighbor, NN)分類器[1,3]、SVM[4]等基于距離的方法可以運用于符號序列分類。

第二種方式是建立基于概率模型的分類器[10,13-15]，其基本原理是根據(jù)式(1)和(2)估計待分類序列S′隸屬于第k類的概率P(S|k)，k=1,2,…,K，進而將S′分類到概率最大的類。這種方法的實質(zhì)是將式(1)和(2)視為序列的生成模型(generative model)，具有分類效率高、分類模型可解釋性好等優(yōu)點。本文提出的符號序列貝葉斯分類器(2.2節(jié))即屬于該類型。

上述兩種應(yīng)用方式都面臨如何確定n(在Markov鏈模型中是模型階數(shù)，在n-gram模型中對應(yīng)于元組或子序列長度)的難題[10,13,16]。與使用固定階模型的現(xiàn)有方法不同，本文提出的多階Markov模型集1階～n階模型于一體，通過設(shè)定一個較大的n克服不準確模型階數(shù)帶來的影響，提高符號序列Markov分類的精度。

2 貝葉斯分類算法

本章提出基于多階Markov模型的符號序列分類方法。首先描述多階Markov模型及其高效計算方法，接著，提出一種新的貝葉斯分類器，并分析其模型訓練算法。

2.1 符號序列多階Markov模型

基于上述假設(shè)，序列S相對于第k類的先驗概率P(S|k)用下式估計：

s.t. ?i:wi>0

(3)

(4)

以下稱式(4)為階權(quán)的歸一化約束條件。

2.2 多階模型的構(gòu)造算法

圖1 從序列“ABAAABBAB”和“BBABABA”構(gòu)造的

如圖1所示，n-STS首先是一棵后綴樹，其每一條從葉子到根的路徑上的n個節(jié)點按序排列成一個n-gram，稱為n-元前綴子序列。在這個例子中，序列“ABAAABBAB”和“BBABABA”由′A′和′B′兩個符號組成，以′A′為后綴的3-gram有“□□A”“AAA”“BAA”“ABA”和“BBA”，對應(yīng)樹上的5條路徑；其次，樹的每個節(jié)點附有一個后綴表，記錄序列中以該節(jié)點對應(yīng)的子序列為前綴的符號計數(shù)。例如，在序列“ABAAABBAB”和“BBABABA”中，3-元前綴子序列“BBA”之后符號′B′出現(xiàn)了2次，但未出現(xiàn)符號′A′，如圖1中標注為TABB的表格所示。每個非葉子節(jié)點也附有這樣的后綴表，記錄更短的前綴子序列的后綴符號計數(shù)。以圖1標注為TAB的表格為例，該表對應(yīng)2-元前綴子序列“BA”(是“BBA”的后綴子序列，因而其節(jié)點是“BBA”對應(yīng)的葉子節(jié)點的父節(jié)點)，從序列“ABAAABBAB”和“BBABABA”易知，以“BA”為前綴的符號′A′和′B′的計數(shù)分別為1和3。

算法1n-STS樹構(gòu)造算法。

b)將Node所附后綴表中符號sl的計數(shù)加1。

End

算法1所示的n-STS樹構(gòu)造算法僅需掃描序列集一次，即可構(gòu)造出K棵n-STS樹。算法的時間復雜度為O(n×M)，其中，M表示Tr中所有序列的總長度。

2.3 新的貝葉斯分類器

本節(jié)描述基于多階Markov模型的符號序列貝葉斯分類器OWBC。給定訓練集Tr以及由算法1生成的K棵n-STS樹，OWBC訓練階段算法從中學習優(yōu)化的階權(quán)集合W={wi|i=1,2,…,n}。這里，采用最大似然學習法，即假設(shè)最優(yōu)階權(quán)最大化下列目標函數(shù)(使用了對數(shù)似然)：

代入式(3)并使用拉格朗日乘子法引入歸一化約束條件式(4)的乘子λ，目標函數(shù)變?yōu)椋?/p>

其中：

(5)

這里，序列S的長度表示為LS。

對于待分類序列S′，OWBC分類階段算法根據(jù)下式預測其類別k′：

(6)

式(6)基于貝葉斯變換并根據(jù)式(3)計算S′相對于第k類的先驗概率P(S′|k)，其中P(k)=|{S|(S,k)∈Tr}|/N為類別k的概率，用訓練集中第k類訓練樣本的占比來估計。

對于長度為L的序列S，上述計算n個條件概率的時間復雜度為O(n×L)，因此，OWBC分類序列S的算法時間復雜度為O(n×L)。在訓練階段，OWBC根據(jù)式(5)學習n個階權(quán)，時間復雜度達到O(n2×M)。另一方面，2.2節(jié)分析表明構(gòu)造n-STS樹的時間復雜度為O(n×M)。綜上，OWBC訓練算法的時間復雜度為O(n2×M)。

3 實驗

本章在實際序列集上驗證新分類器OWBC及其多階Markov模型的性能，并與若干相關(guān)工作作比較。所有實驗在配置1.7 GHz i5 CPU和4 GB RAM的個人計算機上進行。

3.1 實驗數(shù)據(jù)與實驗設(shè)置

實驗在6個實際數(shù)據(jù)集上進行，詳細信息參見表1。如表1所示，6個數(shù)據(jù)集來自3個實際應(yīng)用領(lǐng)域，其中簡稱為BS1和BS2的兩個序列集是客戶交易序列，其目的是預測客戶行為類型，數(shù)據(jù)特點是組成序列的符號數(shù)少(反映客戶的3種行為)、序列長度短(10或12)。相較而言，DNA序列集GS1和GS2以及語音序列集SS1和SS2中的序列長度較長，前者分別取自NCBI基因庫(http://www.ncbi.nlm.nih.gov)和PBIL微生物同源基因家族庫(http://pbil.univ-lyon1.fr)[18]，后者是分別命名為locmslovoy和locfmtrvoy的語音序列[19]，由5個法語元音(“a”“e”“i”“o”“u”)的音頻信號分箱取樣而來。如表1所示，語音序列集SS1和SS2的符號數(shù)明顯多于其他類型的序列。

表1 實驗使用的實際序列集

3.2 分類性能評估

實驗采用了5-折交叉驗證法。通過隨機抽樣將每個序列集均分為5個子集,每次選擇其中的4個子集為訓練數(shù)據(jù),剩余的第5個子集為測試數(shù)據(jù)。對每個序列集，分別進行20次這樣的5-折交叉驗證，因此，可以獲得100組預測結(jié)果。表2匯總了各分類器在每個序列集上100組預測結(jié)果的平均精度，以分類精度“平均值±1個標準差”的形式表示。

一般而言，階數(shù)n越大，從序列中提取的n-元子序列越能反映蘊含在序列中的局部結(jié)構(gòu)特征[20]，因此，在這組實驗中，設(shè)置n=8(注意到BS1中的序列長度只有10)；OWBC的性能隨n變化情況見3.3節(jié)。表2還列出了從各序列集提取的8-gram的數(shù)目。如表2所示，與客戶交易序列相比，DNA序列集GS1和GS2以及語音序列集SS1和SS2的子序列數(shù)目劇增，這導致1-NN和SVM使用的向量空間模型具有相當高的維度。為降低空間的維度，更重要地，為減少“非重要”子序列對分類器性能的影響，本組實驗還使用了基于頻度的子序列約簡方法[16]：給定頻度閾值ε，刪除那些頻度小于ε的子序列。實驗設(shè)定ε=2，約簡后各序列集n-gram的數(shù)目列在表2的“#n-gram/R”欄中；相應(yīng)地，1-NN和SVM在約簡后向量空間模型上取得的平均分類精度如表中“1-NN/R”和“SVM/R”欄所示。

表2 各實際序列集上不同分類器取得的平均分類精度及n-gram數(shù)(n=8)

表2顯示，除了n-gram數(shù)目最小的BS1序列集，1-NN和SVM的平均分類精度明顯低于兩個貝葉斯分類器。主要原因在于數(shù)據(jù)的高維性以及在這樣的高維空間中特征之間存在的顯著相關(guān)性[10]。從表2還可以看出，對客戶交易序列集BS1和BS2，特征約簡前后1-NN和SVM的平均分類精度基本保持不變；在GS1、GS2和SS2上SVM的平均分類精度略有提高；但在SS1上，二者的精度顯著下降。這個結(jié)果表明，對固定階數(shù)子序列特征簡單的約簡處理并不能有效提高符號序列的分類精度。本文提出的OWBC分類器采用的階加權(quán)方法可以看作是一種“軟”(soft)特征約簡過程，但是，與上述面向固定階次子序列的傳統(tǒng)方法不同，這種約簡是針對不同階次的子序列進行的。圖2顯示OWBC訓練算法從6個序列集上學習到的各階次前綴子序列的權(quán)重分布。

如圖2所示，不同長度(階次)的子序列對序列類別預測都有貢獻，但貢獻程度并不相同。OWBC分類器在一個統(tǒng)一的模型中，通過階加權(quán)實現(xiàn)了不同階次子序列的“軟”選擇；由于同時使用了i∈[1,n]階模型，分類器性能得以提高。如表2所示，在GS1和SS1上，OWBC取得了近100%的分類精度，與基于固定階Markov模型的BC分類器相比，在除GS2的實際序列集上，OWBC都取得了顯著的精度提升。從圖2還可以觀察到一個有趣的現(xiàn)象：對于客戶交易序列和DNA序列，隨階次提高，前綴子序列對貝葉斯分類的貢獻表現(xiàn)出逐漸增加的趨勢；但這個結(jié)果并不適用于語音序列數(shù)據(jù)。圖2顯示，對于語音序列集SS1和SS2，貢獻最大的是3階子序列。這為確定符號序列Markov模型最優(yōu)階數(shù)提供了一種參考依據(jù)。

3.3 預設(shè)階數(shù)n的影響

本節(jié)評估階數(shù)n的不同設(shè)置對OWBC分類器性能的影響。首先分析n與OWBC時間效率之間的關(guān)系。根據(jù)3.2節(jié)的分析結(jié)果，OWBC預測階段算法的時間復雜度為O(n×M)，與預設(shè)階數(shù)n和序列總長度M均呈線性關(guān)系，而訓練算法的復雜度達到O(n2×M)；因此，本組實驗著重于后者。圖3顯示在3個領(lǐng)域?qū)嶋H序列集上OWBC訓練算法占用的CPU時間隨n從2到8的變化情況。結(jié)果顯示，隨n增加，算法所需CPU時間呈多項式增長態(tài)勢，與預期相吻合。盡管如此，由于在實際應(yīng)用中n?M，OWBC具有較高的學習效率。如圖3所示，在實驗使用的6個實際序列集上，OWBC都可以在小于1 s的時間內(nèi)完成訓練任務(wù)。

其次，通過實驗分析OWBC對階數(shù)n的敏感性。圖4顯示在3個應(yīng)用領(lǐng)域?qū)嶋H序列集上OWBC的平均分類精度隨n從2到8的變化情況。同3.2節(jié)，本組實驗采用了5-折交叉驗證法。從圖4上可以看出，在客戶交易序列集BS1和BS2上，OWBC的平均分類精度在n>6時略有下降(下降幅度為2～3%)；而在兩個DNA序列集上，其平均分類精度隨n變大反而略有增加；在語音序列集上，OWBC保持了接近100%的高分類精度?？傮w而言，OWBC對預設(shè)階數(shù)n的變化是魯棒的。通過預設(shè)一個較大的階數(shù)(如本實驗設(shè)置的8)，OWBC使用的多階Markov模型加權(quán)融合機制，可以抵消不正確模型階數(shù)設(shè)置對分類器性能的影響，在不同應(yīng)用領(lǐng)域的實際序列集上取得高質(zhì)量的分類結(jié)果。

圖2 由OWBC學習的不同應(yīng)用領(lǐng)域?qū)嶋H序列數(shù)據(jù)的階權(quán)分布(n=8)

圖3 實際序列集上OWBC訓練時間隨預設(shè)模型階數(shù)n的變化情況

4 結(jié)語

現(xiàn)有符號序列Markov分類普遍基于固定階Markov模型(n-階Markov模型)，存在最優(yōu)階次n難以估計及忽視其他階次子序列等問題。本文提出多階Markov模型，在一個統(tǒng)一的模型中同時使用1～n-階Markov鏈模型化符號序列。為構(gòu)造多階模型，提出了一種稱為n-STS的后綴樹結(jié)構(gòu)以及構(gòu)造n-STS樹的高效算法。在此基礎(chǔ)上，提出了一種新的貝葉斯分類器。新分類器的訓練算法不但學習各符號不同階次的條件概率，還優(yōu)化不同階次的權(quán)重(稱為階權(quán))；分類算法使用加權(quán)條件概率預測符號序列的類別標號。在3個實際應(yīng)用領(lǐng)域的序列集上進行了實驗，驗證了新分類器的有效性和對預設(shè)階數(shù)n的魯棒性。

下一步工作將擴展本文方法多維序列分析，并推廣多階模型及其學習方法到無監(jiān)督學習領(lǐng)域，開展符號序列多階Markov聚類等無監(jiān)督學習方法研究。

圖4 實際序列集上OWBC平均分類精度與預設(shè)模型階數(shù)n之間的關(guān)系

References)

[1] XING Z, PEI J, KEOGH E. A brief survey on sequence classification [J]. ACM SIGKDD Explorations Newsletter, 2010, 12(1): 40-48.

[2] DONG G, PEI J. Sequence Data Mining [M]. Berlin: Springer, 2007: 47-65.

[3] 郭躬德,陳黎飛,李南.近鄰分類方法及其應(yīng)用[M].廈門:廈門大學出版社,2013:29-97.(GUO G D, CHEN L F, LI N. Nearest Neighbour Classification Method and Its Applications [M]. Xiamen: Xiamen University Press, 2013: 29-97.)

[4] CRISTIANINI N, SCHOLKOPF B. Support vector machines and kernel methods: the new generation of learning machines [J]. Artificial Intelligence, 2002, 23(3): 31-41.

[5] THEODORIDIS S. Machine Learning: A Bayesian and Optimization Perspective [M]. San Diego: Academic Press, 2015: 876-902.

[6] 敖麗敏,羅存金.基于神經(jīng)網(wǎng)絡(luò)集成的DNA序列分類方法研究[J].計算機仿真,2012,29(6):171-175.(AO L M, LUO C J. DNA series classification based on ensemble neural networks [J]. Computer Simulation, 2012, 29(6): 171-175.)

[7] 袁銘.標度曲線擬合與金融時間序列聚類[J].計算機應(yīng)用,2015,34(11):3344-3347.(YUAN M. Fitting of scaling curve and financial time series clustering [J]. Journal of Computer Applications, 2015, 34(11): 3344-3347.)

[8] KELIL A, WANG S. SCS: A new similarity measure for categorical sequences [C]// Proceedings of the 8th IEEE International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2008: 343-352.

[9] HERRANZ J, NIN J, SOLE M. Optimal symbol alignment dis-tance: a new distance for sequences of symbols [J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(10): 1541-1554.

[10] YAKHNENKO O, SILVESCU A, HONAVAR V. Discriminatively trained Markov model for sequence classification [C]// Proceedings of the 5th IEEE International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2005: 498-505.

[11] 楊一鳴,潘嶸,潘嘉林,等.時間序列分類問題的算法比較[J].計算機學報,2007,30(8):1259-1266.(YANG Y M, PAN R, PAN J L, et al. A comparative study on time series classification [J]. Chinese Journal of Computers, 2007, 30(8): 1259-1266.)

[12] KONDRAK G. N-gram similarity and distance [C]// Proceedings of the 12th International Conference on String Processing and Information Retrieval. Berlin: Springer, 2005: 115-126.

[13] FINK G A. Markov Models for Pattern Recognition: From Theory to Applications [M]. Berlin: Springer, 2008: 95-111.

[14] TSCHUMITSCHEW K, NAUCK D, KLAWONN F. A classifica-tion algorithm for process sequences based on Markov chains and Bayesian networks [C]// Proceedings of the 14th International Conference on Knowledge-based and Intelligent Information and Engineering Systems. Berlin: Springer, 2010: 141-147.

[15] 尹銳,李雄飛,李軍,等.基于線性分段與HMM的時間序列分類算法[J].模式識別與人工智能,2011,24(4):574-581.(YIN R, LI X F, LI J, et al. Time series classification algorithm based on linear segmentation and HMM [J]. Pattern Recognition & Artificial Intelligence, 2011, 24(4): 574-581.)

[16] XIONG T, WANG S, JIANG Q, et al. A novel variable-order Markov model for clustering categorical sequences [J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(10): 2339-2353.

[17] KARLIN S, GHANDOUR G. Comparative statistics for DNA and protein sequences: single sequence analysis [J]. Proceedings of the National Academy of Sciences, 1985, 82(17): 5800-5804.

[18] WEI D, JIANG Q, WEI Y, et al. A novel hierarchical clustering algorithm for gene sequences [J]. BMC Bioinformatics, 2012, 13(1): 174.

[19] LOISELLE S, ROUAT J, PRESSNITZER D, et al. Exploration of rank order coding with spiking neural networks for speech recognition [C]// Proceedings of the 2005 IEEE International Joint Conference on Neural Networks. Washington, DC: IEEE Computer Society, 2005: 2076-2080.

[20] NAMIKI Y, ISHIDA T, AKIYAMA Y. Acceleration of sequence clustering using longest common subsequence filtering [J]. BMC Bioinformatics, 2013, 14(Suppl 8): S7.

This work is supported by the National Natural Science Foundation of China (61672157).

CHENGLingfang, born in 1983, M. S., lecturer. Her research interests include machine learning, pattern recognition.

GUOGongde, born in 1965, Ph. D., professor. His research interests include artificial intelligence, data mining.

CHENLifei, born in 1972, Ph. D., professor. His research interests include statistical machine learning, data mining, pattern recognition.

Classificationofsymbolicsequenceswithmulti-orderMarkovmodel

CHENG Lingfang1, GUO Gongde2, CHEN Lifei2*

(1.JinshanCollegeofFujianAgricultureandForestryUniversity,FuzhouFujian350002,China;2.SchoolofMathematicsandComputerScience,FujianNormalUniversity,FuzhouFujian350117,China)

To solve the problem that the existing methods based on the fixed-order Markov models cannot make full use of the structural features involved in the subsequences of different orders, a new Bayesian method based on the multi-order Markov model was proposed for symbolic sequences classification. First, a Conditional Probability Distribution (CPD) model was built based on the multi-order Markov model. Second, a suffix tree forn-order subsequences with efficient suffix-tables and its efficient construction algorithm were proposed, where the algorithm could be used to learn the multi-order CPD models by scanning once the sequence set. A Bayesian classifier was finally proposed for the classification task. The training algorithm was designed to learn the order-weights for the models of different orders based on the Maximum Likelihood (ML) method, while the classification algorithm was defined to carry out the Bayesian prediction using the weighted conditional probabilities of each order. A series of experiments were conducted on real-world sequence sets from three domains and the results demonstrate that the new classifier is insensitive to the predefined order change of the model. Compared with the existing methods such as the support vector machine using the fixed-order model, the proposed method can achieve more than 40% improvement on both gene sequences and speech sequences in terms of classification accuracy, yielding reference values for the optimal order of a Markov model on symbolic sequences.

symbolic sequence; Markov chain model; multi-order model; Bayesian classification; suffix tree

TP311; TP18

:A

2017- 01- 13;

:2017- 03- 05。

國家自然科學基金資助項目(61672157)。

程鈴鈁(1983—)，女，山東滕州人，講師，碩士，主要研究方向：機器學習、數(shù)據(jù)挖掘； 郭躬德(1965—)，男，福建龍巖人，教授，博士，主要研究方向：人工智能、數(shù)據(jù)挖掘； 陳黎飛(1972—)，男，福建長樂人，教授，博士，主要研究方向：統(tǒng)計機器學習、數(shù)據(jù)挖掘、模式識別。

1001- 9081(2017)07- 1977- 06

10.11772/j.issn.1001- 9081.2017.07.1977