陈炳鑫 ,陈黎飞*

（1.福建师范大学数学与信息学院，福州，350117；2.数字福建环境监测物联网实验室，福建师范大学，福州，350117）

符号序列（symbolic sequences）通常由有限个离散型符号按照特定的规律排列而成，当前许多数据挖掘的应用都基于符号序列的表现形式.例如在生物信息学中，由{'A'，'T'，'G'，'C'} 等代表不同碱基符号构成的基因即为一种符号序列.对基因进行分析是生物信息学极其重要的研究内容之一，生物学家对不同功能的基因进行分类，可以进一步研究同源序列之间的进化关系［1-2］.由于符号序列长短不一，且具有特殊的时空顺序关系等特点，针对向量型数据的经典方法无法直接运用于符号序列分类任务中，因此对其进行挖掘仍存在挑战性.目前已经提出了多种序列的分类方法［3］，其中基于距离的分类方法因其简单而得到了广泛的研究.

现有的序列距离度量方法大致可分两种：一种是序列对齐（alignment based）方法，如基于动态规划［4-5］或编辑距离［6］等思想进行符号序列的分类挖掘.尽管该方法常用于符号序列分类，但其通常基于较高的计算复杂度.另一种是非对齐（non-alignment）的方法，该方法采取表征学习［7-10］的手段构造出序列的特征.其中子序列法［3］是一种常见的方法，通过一些重要的短子序列来表示序列的特征.但该方法得到的是序列的局部结构特征，且生成的特征维度较高，同时子序列法得到的特征在某些情况下并非统计独立［11］，降低了欧几里得距离等度量的有效性.相比……