计算机应用   2017, Vol. 37 Issue (7): 1977-1982  DOI: 10.11772/j.issn.1001-9081.2017.07.1977
0

引用本文 

程铃钫, 郭躬德, 陈黎飞. 符号序列多阶Markov分类[J]. 计算机应用, 2017, 37(7): 1977-1982.DOI: 10.11772/j.issn.1001-9081.2017.07.1977.
CHENG Lingfang, GUO Gongde, CHEN Lifei. Classification of symbolic sequences with multi-order Markov model[J]. Journal of Computer Applications, 2017, 37(7): 1977-1982. DOI: 10.11772/j.issn.1001-9081.2017.07.1977.

基金项目

国家自然科学基金资助项目(61672157)

通信作者

陈黎飞, E-mail:clfei@fjnu.edu.cn

作者简介

程铃钫(1983-), 女, 山东滕州人, 讲师, 硕士, 主要研究方向:机器学习、数据挖掘;
郭躬德(1965-), 男, 福建龙岩人, 教授, 博士, 主要研究方向:人工智能、数据挖掘;
陈黎飞(1972-), 男, 福建长乐人, 教授, 博士, 主要研究方向:统计机器学习、数据挖掘、模式识别

文章历史

收稿日期:2017-01-13
修回日期:2017-03-05
符号序列多阶Markov分类
程铃钫1, 郭躬德2, 陈黎飞2    
1. 福建农林大学 金山学院, 福州 350002;
2. 福建师范大学 数学与计算机科学学院, 福州 350117
摘要: 针对基于固定阶Markov链模型的方法不能充分利用不同阶次子序列结构特征的问题,提出一种基于多阶Markov模型的符号序列贝叶斯分类新方法。首先,建立了基于多阶次Markov模型的条件概率分布模型;其次,提出一种附后缀表的n-阶子序列后缀树结构和高效的树构造算法,该算法能够在扫描一遍序列集过程中建立多阶条件概率模型;最后,提出符号序列的贝叶斯分类器,其训练算法基于最大似然法学习不同阶次模型的权重,分类算法使用各阶次的加权条件概率进行贝叶斯分类预测。在三个应用领域实际序列集上进行了系列实验,结果表明:新分类器对模型阶数变化不敏感;与使用固定阶模型的支持向量机等现有方法相比,所提方法在基因序列与语音序列上可以取得40%以上的分类精度提升,且可输出符号序列Markov模型最优阶数参考值。
关键词: 符号序列    Markov链模型    多阶模型    贝叶斯分类    后缀树    
Classification of symbolic sequences with multi-order Markov model
CHENG Lingfang1, GUO Gongde2, CHEN Lifei2     
1. Jinshan College of Fujian Agriculture and Forestry University, Fuzhou Fujian 350002, China;
2. School of Mathematics and Computer Science, Fujian Normal University, Fuzhou Fujian 350117, China
Abstract: 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 for n-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.
Key words: symbolic sequence    Markov chain model    multi-order model    Bayesian classification    suffix tree    
0 引言

符号序列是一种由类属型(离散型)符号组成的线性链,许多应用领域的数据挖掘对象以这种复杂类型的数据表示。例如,在银行信用卡客户管理中,用一些离散符号表示客户行为时,客户在一段时间内的行为即构成一条符号序列。本文研究符号序列分类问题,通过序列中各种符号及其顺序关系的监督学习,预测数据对象的类别标号,在基于行为序列的银行客户破产风险预测等领域具有广泛的应用[1-2]

文献中已提出多种分类方法,包括决策树、近邻(Nearest Neighbour, NN)分类、支持向量机(Support Vector Machine, SVM)及基于概率模型的分类等机器学习方法[3-4],以及人工神经网络等智能计算方法[5-6]。尽管这些方法已得到广泛研究和应用,但它们多针对向量型数据,即假设每个数据对象都已经映射为某个定义完好的特征空间中的向量。有两种途径可以将现有方法用于挖掘含有结构信息的符号序列:一种方案提取符号序列的结构特征,以构造序列的向量空间模型[1-2, 7];另一种方案定义能够体现序列结构特征的序列距离度量[8-9]、概率模型[10-11]等,从而可以将相关方法推广到符号序列。

现有两类主要方法用于提取序列的结构特征:子序列法和概率模型法。前者以n-gram(n-元组)为代表[1-2, 7, 12],目的是提取蕴含在序列中的局部结构信息,后者通过Markov模型(马尔可夫模型)[10, 13-14]、隐Markov模型[15]等概率模型刻画序列中的全局结构信息。所述n-gram是序列中n个连续符号构成的短子序列——实际上,相当于n-阶Markov模型中的前缀子序列[16]。从这个意义上说,n-gram方法是Markov模型的一种应用[13]。当前,基于Markov模型的分类器已成为符号序列分类的主要工具之一[1-2, 10, 13-15]

实际进行符号序列Markov分类时,需要面对如何确定模型阶数n等难题[10-11, 13]。由于阶数n与所提取的序列结构特征息息相关,该重要参数的选择将直接影响分类器的性能。文献中已提出少量的估计方法,例如文献[17]给出的最长公共子序列期望长度估计,但该方法仅针对DNA和蛋白质序列,且仅作用于序列对而非整个序列集。由于当前尚缺乏给定序列集最优模型阶数的有效估计方法[13, 16],在实际应用中,通常由用户经验地设定n或基于交叉验证法等“试错”机制,在一定范围内选择产生最高分类质量的特定值。事实上,在现有方法中,一旦给定了n,就仅利用固定阶次的子序列(n-阶Markov模型)进行序列分类,这意味着忽略其他阶次子序列中的结构信息,必然影响符号序列Markov分类的性能。

本文提出一种符号序列的多阶Markov分类方法。新方法基于多阶Markov模型,同时利用了1, 2, …, n-阶子序列,以提高符号序列的分类性能。在新提出的“阶加权”贝叶斯分类器(Order-Weighting Bayesian Classifier,OWBC)中,训练算法学习各阶次条件概率分布模型及各阶次的权重,分类算法则基于加权的多阶条件概率进行贝叶斯推断。在来自不同应用领域的实际序列集上进行了实验验证,实验结果表明,新分类器对模型的预设阶数n是鲁棒的,与现有采用固定阶Markov模型的方法相比,有效提高了分类精度。

1 相关工作

首先约定全文使用的记号。令Tr表示由N个样本构成的训练数据集,每个样本是一个二元组(S, k),其中S表示符号序列,k∈[1, K]是序列S的类别标号,K为类别数。序列S的长度记为L,即SL个符号排列而成,表示为S=s1s2slsL。所有符号的集合记为X,|X|表示其中的符号数;因此,slX(l=1, 2, …, L)。

符号序列的Markov链模型基于如下假设:任一序列S中符号sl与其前缀子序列s0s1sl-1密切相关,其中s0表示序列的起点,可以看作一个虚拟符号(用“□”表示);采用n-阶Markov模型时,前缀子序列被截断为δl(n)=sl-nsl-1,其中j < 0的符号sjs0代替,因此,n-阶Markov模型中的前缀子序列具有固定的长度n,用上标“(n)”标识。这样,序列S的概率P(S)就可以通过一系列条件概率的乘积来估计,即:

$ P(S) = \prod\limits_{l = 1}^L {P({s_l}|\delta _l^{(n)})} $ (1)

式(1) 表示的模型也称为符号序列的条件概率分布(Conditional Probability Distribution,CPD)模型[13, 16]。用于分类时,式中的条件概率根据训练数据集中符号的条件分布估计;显然,这种条件分布随训练类别的不同而有所差异。记符号sl相对于第k个训练类别的条件概率为pk(sl|δl(n)),通常使用如下Laplace校正估计:

$ {p_k}({s_l}|\delta _l^{(n)}) = [{f_k}(\delta _l^{(n)}{s_l}) + 1]/[{f_k}(\delta _l^{(n)}) + |X|] $ (2)

其中fk(t)表示子序列t在第k个训练类别包括的所有序列中出现的次数。

文献中有两种主要方式在序列挖掘中应用上述Markov链模型。第一种方式基于Markov模型定义序列间的相似性度量,继而进行基于相似性的序列挖掘。一种常见的实现方式是计算两个序列SS′间的距离为概率分布P(S)和P(S′)间的差异,涉及的度量包括K-L(Kullback-Leible)散度、Hellinger距离[10, 13]等;另一种间接利用Markov模型的实现是构造序列的n-gram表示模型[1-2, 12-13]:先将每个序列映射为(以n-gram为特征的)向量空间的一个向量,再以向量间的欧几里得距离等衡量序列间的差异[7]。基于这样的表示模型,近邻(Nearest Neighbor, NN)分类器[1, 3]、SVM[4]等基于距离的方法可以运用于符号序列分类。

第二种方式是建立基于概率模型的分类器[10, 13-15],其基本原理是根据式(1) 和(2) 估计待分类序列S′隶属于第k类的概率P(S|k),k=1, 2, …, K,进而将S′分类到概率最大的类。这种方法的实质是将式(1) 和(2) 视为序列的生成模型(generative model),具有分类效率高、分类模型可解释性好等优点。本文提出的符号序列贝叶斯分类器(2.2节)即属于该类型。

上述两种应用方式都面临如何确定n(在Markov链模型中是模型阶数,在n-gram模型中对应于元组或子序列长度)的难题[10, 13, 16]。与使用固定阶模型的现有方法不同,本文提出的多阶Markov模型集1阶~n阶模型于一体,通过设定一个较大的n克服不准确模型阶数带来的影响,提高符号序列Markov分类的精度。

2 贝叶斯分类算法

本章提出基于多阶Markov模型的符号序列分类方法。首先描述多阶Markov模型及其高效计算方法,接着,提出一种新的贝叶斯分类器,并分析其模型训练算法。

2.1 符号序列多阶Markov模型

如前所述,在一个n-阶Markov模型中,序列S中符号sl的条件概率定义在长度固定为n的前缀子序列δl(n)=sl-nsl-1上。对于一个给定的序列集,理想的模型阶数可能是1, 2, …,具体取值应与序列结构有关。鉴于估计最优模型阶数的困难,本文提出多阶模型方案,基于如下假设:1) 给定一个较大的n,序列集最优Markov模型的阶数i∈[1, n];2) 任何阶数为i∈[1, n]的模型都是可能的,但各模型的“可能性”不同。对于序列S中的符号sl,事实上,其n-阶Markov模型下的前缀子序列δl(n)已经包含了所有i∈[1, n]阶前缀子序列δl(i)=sl-isl-1。注意到δl(i)δl(n)的后缀子序列,这为构造融合i∈[1, n]阶的多阶模型提供了基础。

基于上述假设,序列S相对于第第k类的先验概率P(S|k)用下式估计:

$ \begin{array}{l} P(S|k) = {\prod\limits_{l = 1}^L {\prod\limits_{i = 1}^n {\left[{{p_k}({s_l}|\delta _l^{(i)})} \right]} } ^{\frac{1}{{{w_i}}}}}\\ {\rm{s}}{\rm{.t}}{\rm{.}}\quad \forall i{\rm{:}}\;{w_i} > 0 \end{array} $ (3)

S中的符号sl,式(3) 涉及n个条件概率pk(sl|δl(i)),i∈[1, n]。不同阶次条件概率的贡献度用“阶次权重”(order-weights,以下简称“阶权”)w1-1, w2-1, …, wn-1表示,衡量各阶次Markov模型的“可能性”。显然,若wn=1且其他i∈[1, n)阶的权重为0,式(3) 退化为单阶条件概率模型(n-阶Markov模型)。另一方面,从优化的角度看,当所有权重均为0时P(S|k)取最大值,但此时,对所有阶次iwi→ +∞,这意味着所有阶次模型具有相同的“可能性”。为避免此“平凡解”并区分不同阶次的贡献,需要为式(3) 施加进一步的约束条件:

$ \sum\limits_{i = 1}^n {{w_i}} = 1 $ (4)

以下称式(4) 为阶权的归一化约束条件。

2.2 多阶模型的构造算法

为建立式(3) 所示的多阶模型,需要为每条序列S中的每个符号sl计算n个条件概率pk(sl|δl(i)),i∈[1, n]。为提高计算效率,本节提出一种高效算法,目的是在一遍扫描序列集的过程中获得上述所有条件概率。该算法使用一种新的数据结构,称为“附后缀表的n-gram后缀树”,简称n-STS(n-gram Suffix Tree with Suffix-tables)。图 1显示一个例子。

图 1 从序列“ABAAABBAB”和“BBABABA”构造的以′A′为后缀的n-STS子树(n=3) Figure 1 An example of n-STS subtree corresponding to n-gram with the suffix ′A′, obtained from sequences "ABAAABBAB"and"BBABABA"with n=3

图 1所示,n-STS首先是一棵后缀树,其每一条从叶子到根的路径上的n个节点按序排列成一个n-gram,称为n-元前缀子序列。在这个例子中,序列“ABAAABBAB”和“BBABABA”由′A′和′B′两个符号组成,以′A′为后缀的3-gram有“□□A”“AAA”“BAA”“ABA”和“BBA”,对应树上的5条路径;其次,树的每个节点附有一个后缀表,记录序列中以该节点对应的子序列为前缀的符号计数。例如,在序列“ABAAABBAB”和“BBABABA”中,3-元前缀子序列“BBA”之后符号′B′出现了2次,但未出现符号′A′,如图 1中标注为TABB的表格所示。每个非叶子节点也附有这样的后缀表,记录更短的前缀子序列的后缀符号计数。以图 1标注为TAB的表格为例,该表对应2-元前缀子序列“BA”(是“BBA”的后缀子序列,因而其节点是“BBA”对应的叶子节点的父节点),从序列“ABAAABBAB”和“BBABABA”易知,以“BA”为前缀的符号′A′和′B′的计数分别为1和3。

节点所附后缀表有一个重要性质:后缀表所有计数之和正是所对应前缀子序列在序列集中的计数,因此,利用n-STS树和式(2),可以容易地计算每个符号的条件概率。例如,对于2-元前缀子序列δl(2)=“BA”,查询后缀表TAB可知fk(“BAA”)=1和fk(“BAB”)=3,那么,fk(“BA”)=fk(“BAA”)+fk(“BAB”)=4;据式(2),估计条件概率为pk(′A′|δl(2))=(1+1)/(4+2)≈0.33和pk(′B′|δl(2))=(3+1)/(4+2)≈0.67。上述计算过程在n-STS树的每个层次i∈[1, n]上进行,就可以得到式(3) 所需的所有阶次的条件概率。

给定训练集Tr和初始模型阶数n,可以为每个类k的序列构造一棵n-STS树,各树的根节点分别用Rk表示,k=1, 2, …, K;每棵树最多有|X|棵如图 1所示的子树,树的每个节点以X中的一个符号标记;一棵n-STS树的高度为n+1,层次编号用0(根所在层次), 1, 2, …, n表示。算法扫描每条序列S,为其上每个符号sl提取其n-元前缀子序列δl(n),插入n-STS树,并更新每个节点的后缀表。算法过程描述如下。

算法1  n-STS树构造算法。

输入:训练集Tr,阶数n

输出:Kn-STS树。

Begin

  1) 创建Kn-STS树的根节点Rk(k=1, 2, …, K);

  2) 对每条序列S∈{S′|(S′, k)∈Tr},按序提取slδl(n)=sl-nsl-1(j < 0时符号sjs0代替),l=1, 2, …, L;初始化当前节点Node=Rk,令i表示树的层次,对i=1, 2, …, n重复如下操作:

    a) 检查Node是否存在标记为符号sl-i的子节点,若不存在,则为Node创建一个子节点,用符号sl-i标记;修改Node为该子节点。

    b) 将Node所附后缀表中符号sl的计数加1。

End

算法1所示的n-STS树构造算法仅需扫描序列集一次,即可构造出Kn-STS树。算法的时间复杂度为O(n×M),其中,M表示Tr中所有序列的总长度。

2.3 新的贝叶斯分类器

本节描述基于多阶Markov模型的符号序列贝叶斯分类器OWBC。给定训练集Tr以及由算法1生成的Kn-STS树,OWBC训练阶段算法从中学习优化的阶权集合W={wi|i=1, 2, …, n}。这里,采用最大似然学习法,即假设最优阶权最大化下列目标函数(使用了对数似然):

$ {J_0}(W) = \sum\limits_{(S, k) \in Tr} {\ln P(S|k)} $

代入式(3) 并使用拉格朗日乘子法引入归一化约束条件式(4) 的乘子λ,目标函数变为:

$ J(W) = \sum\limits_{i = 1}^n {\frac{1}{{{w_i}}}} \sum\limits_{(S, k) \in Tr} {\sum\limits_{l = 1}^L {\ln {p_k}({s_l}|\delta _l^{(i)})} } + \lambda \left( {1-\sum\limits_{i = 1}^n {{w_i}} } \right) $

因此,最优的归一化阶权wi应令$ \frac{{\partial J}}{{\partial {w_i}}} = 0 $$ \frac{{\partial J}}{{\partial \lambda }} = 0 $i=1, 2, …, n。经过推导,有

$ {w_i} = {\tilde w_i}/\sum\limits_{j = 1}^n {{{\tilde w}_j}} $

其中:

$ {\tilde w_i} = \sqrt {-\sum\limits_{(S, k) \in Tr} {\sum\limits_{l = 1}^{{L_S}} {\ln {p_k}({s_l}|\delta _l^{(i)})} } } $ (5)

这里,序列S的长度表示为LS

对于待分类序列S′,OWBC分类阶段算法根据下式预测其类别k′:

$ \begin{align} & {k}{'}=\underset{k=1,2,\cdots ,K}{\mathop{\arg \ \max }}\,P(k|{S}{'})=\underset{k=1,2,\cdots ,K}{\mathop{\arg \ \max }}\,P(k)P({S}{'}|k)= \\ & \ \ \ \ \ \ \underset{k=1,2,\cdots ,K}{\mathop{\arg \ \max }}\,P(k)\prod\limits_{l=1}^{L}{{{\prod\limits_{i=1}^{n}{\left[ {{p}_{k}}\left( {{{{s}{'}}}_{l}}|{\delta }{'}_{l}^{(i)} \right) \right]}}^{\frac{1}{{{w}_{i}}}}}} \\ \end{align} $ (6)

式(6) 基于贝叶斯变换并根据式(3) 计算S′相对于第第k类的先验概率P(S′|k),其中P(k)=|{S|(S, k)∈Tr}|/N为类别k的概率,用训练集中第第k类训练样本的占比来估计。

计算式(5) 和(6) 都涉及某序列S中每个符号sln个条件概率pk(sl|δl(i)),i∈[1, n]。后者通过搜索算法1构造的n-STS树得到。具体地,首先提取sln-元前缀子序列δl(n)=sl-nsl-1(j < 0时符号sjs0代替),并令i=1表示树的起始搜索层次和Node=Rk表示起始树节点,定位到Node上标记为符号sl-i的子节点,按2.2节所述方法查询该节点的后缀表获得fk(δl(i)sl)和fk(δl(i)),再据式(2) 计算pk(sl|δl(i));接着,修改Node为该子节点,并令i=i+1,重复上述过程,直到i=n。计算过程中发现子节点不存在时(意味着待分类序列包含了未出现在训练集中的子序列),设定fk(δl(j)sl)=fk(δl(j))=0计算pk(sl|δl(j)),j∈[i, n]。

对于长度为L的序列S,上述计算n个条件概率的时间复杂度为O(n×L),因此,OWBC分类序列S的算法时间复杂度为O(n×L)。在训练阶段,OWBC根据式(5) 学习n个阶权,时间复杂度达到O(n2×M)。另一方面,2.2节分析表明构造n-STS树的时间复杂度为O(n×M)。综上,OWBC训练算法的时间复杂度为O(n2×M)。

3 实验

本章在实际序列集上验证新分类器OWBC及其多阶Markov模型的性能,并与若干相关工作作比较。所有实验在配置1.7 GHz i5 CPU和4 GB RAM的个人计算机上进行。

3.1 实验数据与实验设置

实验在6个实际数据集上进行,详细信息参见表 1。如表 1所示,6个数据集来自3个实际应用领域,其中简称为BS1和BS2的两个序列集是客户交易序列,其目的是预测客户行为类型,数据特点是组成序列的符号数少(反映客户的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的符号数明显多于其他类型的序列。

表 1 实验使用的实际序列集 Table 1 Real-world sequence sets used in experiments

实验采用了基于单阶Markov模型的贝叶斯分类器为对比方法(简称为BC),如2.1节所述,BC分类器[14]可以看作OWBC的一个特例:当wn固定为1且in:wi-1=0时,OWBC退化为BC。为对比不同Markov分类器的性能,实验还使用了1-NN(近邻数为1的近邻分类器[3])和SVM为对比方法,二者都使用了基于n-gram的符号序列向量表示模型。为提高分类性能,实验所用1-NN分类器预测类别时采用了加权投票方法;SVM分类器为C-SVC[4],采用了LIBSVM的实现(http://www.csie.ntu.edu.tw/~cjlin/libsvm)。以“分类精度”指标评估各种分类器的性能。分类精度(CA)定义为预测结果与真实类别相符的样本占全体待分类样本的比例,计算公式如下:

$ CA = \frac{1}{{|Ts|}}\sum\limits_{S \in Ts} {I({k_S} = k{'_S})} $

其中:I是取值0或1的指示函数,kSk′S分别表示测试序列S真实类别标号和分类器预测的类别标号,Ts表示测试序列集,|Ts|为测试序列的数量。显然,CA的值越大表示分类器具有越好的分类性能。

3.2 分类性能评估

实验采用了5-折交叉验证法。通过随机抽样将每个序列集均分为5个子集, 每次选择其中的4个子集为训练数据, 剩余的第5个子集为测试数据。对每个序列集,分别进行20次这样的5-折交叉验证,因此,可以获得100组预测结果。表 2汇总了各分类器在每个序列集上100组预测结果的平均精度,以分类精度“平均值±1个标准差”的形式表示。

表 2 各实际序列集上不同分类器取得的平均分类精度及n-gram数(n=8) Table 2 Average classification accuracy obtained by different classifiers on each real-world sequence set and number of n-gram extracted from sequences (n=8)

一般而言,阶数n越大,从序列中提取的n-元子序列越能反映蕴含在序列中的局部结构特征[20],因此,在这组实验中,设置n=8(注意到BS1中的序列长度只有10);OWBC的性能随n变化情况见3.3节。表 2还列出了从各序列集提取的8-gram的数目。如表 2所示,与客户交易序列相比,DNA序列集GS1和GS2以及语音序列集SS1和SS2的子序列数目剧增,这导致1-NN和SVM使用的向量空间模型具有相当高的维度。为降低空间的维度,更重要地,为减少“非重要”子序列对分类器性能的影响,本组实验还使用了基于频度的子序列约简方法[16]:给定频度阈值ε,删除那些频度小于ε的子序列。实验设定ε=2,约简后各序列集n-gram的数目列在表 2的“#n-gram/R”栏中;相应地,1-NN和SVM在约简后向量空间模型上取得的平均分类精度如表中“1-NN/R”和“SVM/R”栏所示。

表 2显示,除了n-gram数目最小的BS1序列集,1-NN和SVM的平均分类精度明显低于两个贝叶斯分类器。主要原因在于数据的高维性以及在这样的高维空间中特征之间存在的显著相关性[10]。从表 2还可以看出,对客户交易序列集BS1和BS2,特征约简前后1-NN和SVM的平均分类精度基本保持不变;在GS1、GS2和SS2上SVM的平均分类精度略有提高;但在SS1上,二者的精度显著下降。这个结果表明,对固定阶数子序列特征简单的约简处理并不能有效提高符号序列的分类精度。本文提出的OWBC分类器采用的阶加权方法可以看作是一种“软”(soft)特征约简过程,但是,与上述面向固定阶次子序列的传统方法不同,这种约简是针对不同阶次的子序列进行的。图 2显示OWBC训练算法从6个序列集上学习到的各阶次前缀子序列的权重分布。

图 2 由OWBC学习的不同应用领域实际序列数据的阶权分布(n=8) Figure 2 Order-weight distributions learned by OWBC for real-world sequences from various domains with n=8

图 2所示,不同长度(阶次)的子序列对序列类别预测都有贡献,但贡献程度并不相同。OWBC分类器在一个统一的模型中,通过阶加权实现了不同阶次子序列的“软”选择;由于同时使用了i∈[1, n]阶模型,分类器性能得以提高。如表 2所示,在GS1和SS1上,OWBC取得了近100%的分类精度,与基于固定阶Markov模型的BC分类器相比,在除GS2的实际序列集上,OWBC都取得了显著的精度提升。从图 2还可以观察到一个有趣的现象:对于客户交易序列和DNA序列,随阶次提高,前缀子序列对贝叶斯分类的贡献表现出逐渐增加的趋势;但这个结果并不适用于语音序列数据。图 2显示,对于语音序列集SS1和SS2,贡献最大的是3阶子序列。这为确定符号序列Markov模型最优阶数提供了一种参考依据。

3.3 预设阶数n的影响

本节评估阶数n的不同设置对OWBC分类器性能的影响。首先分析n与OWBC时间效率之间的关系。根据3.2节的分析结果,OWBC预测阶段算法的时间复杂度为O(n×M),与预设阶数n和序列总长度M均呈线性关系,而训练算法的复杂度达到O(n2×M);因此,本组实验着重于后者。图 3显示在3个领域实际序列集上OWBC训练算法占用的CPU时间随n从2到8的变化情况。结果显示,随n增加,算法所需CPU时间呈多项式增长态势,与预期相吻合。尽管如此,由于在实际应用中nM,OWBC具有较高的学习效率。如图 3所示,在实验使用的6个实际序列集上,OWBC都可以在小于1 s的时间内完成训练任务。

图 3 实际序列集上OWBC训练时间随预设模型阶数n的变化情况 Figure 3 Change in training time of OWBC with respect to the predefined n on real-world sequence sets

其次,通过实验分析OWBC对阶数n的敏感性。图 4显示在3个应用领域实际序列集上OWBC的平均分类精度随n从2到8的变化情况。同3.2节,本组实验采用了5-折交叉验证法。从图 4上可以看出,在客户交易序列集BS1和BS2上,OWBC的平均分类精度在n>6时略有下降(下降幅度为2~3%);而在两个DNA序列集上,其平均分类精度随n变大反而略有增加;在语音序列集上,OWBC保持了接近100%的高分类精度。总体而言,OWBC对预设阶数n的变化是鲁棒的。通过预设一个较大的阶数(如本实验设置的8),OWBC使用的多阶Markov模型加权融合机制,可以抵消不正确模型阶数设置对分类器性能的影响,在不同应用领域的实际序列集上取得高质量的分类结果。

图 4 实际序列集上OWBC平均分类精度与预设模型阶数n之间的关系 Figure 4 Relationship between average classification accuracy of OWBC and the predefined n on real-world sequence sets
4 结语

现有符号序列Markov分类普遍基于固定阶Markov模型(n-阶Markov模型),存在最优阶次n难以估计及忽视其他阶次子序列等问题。本文提出多阶Markov模型,在一个统一的模型中同时使用1~n-阶Markov链模型化符号序列。为构造多阶模型,提出了一种称为n-STS的后缀树结构以及构造n-STS树的高效算法。在此基础上,提出了一种新的贝叶斯分类器。新分类器的训练算法不但学习各符号不同阶次的条件概率,还优化不同阶次的权重(称为阶权);分类算法使用加权条件概率预测符号序列的类别标号。在3个实际应用领域的序列集上进行了实验,验证了新分类器的有效性和对预设阶数n的鲁棒性。

下一步工作将扩展本文方法多维序列分析,并推广多阶模型及其学习方法到无监督学习领域,开展符号序列多阶Markov聚类等无监督学习方法研究。

参考文献(References)
[1] XING Z, PEI J, KEOGH E. A brief survey on sequence classification[J]. ACM SIGKDD Explorations Newsletter, 2010, 12(1): 40-48. DOI:10.1145/1882471
[2] DONG G, PEI J. Sequence Data Mining[M]. Berlin: Springer, 2007: 47-65.
[3] 郭躬德, 陈黎飞, 李南. 近邻分类方法及其应用[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] 敖丽敏, 罗存金. 基于神经网络集成的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]. 计算机应用, 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. DOI:10.1109/TKDE.2010.190
[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. DOI:10.1109/TKDE.2013.104
[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. DOI:10.1073/pnas.82.17.5800
[18] WEI D, JIANG Q, WEI Y, et al. A novel hierarchical clustering algorithm for gene sequences[J]. BMC Bioinformatics, 2012, 13(1): 174. DOI:10.1186/1471-2105-13-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. DOI:10.1186/1471-2105-14-S8-S7