近似保序序列模式挖掘_刘锦.pdf

小 型 微 型 计 算 机 系 统 ：年 月 第 期 收稿日期：收修改稿日期：基金项目：国家自然科学基金项目（）资助 作者简介：刘锦，男，年生，硕士研究生，会员，研究方向为序列模式挖掘；武优西（通讯作者），男，年生，博士，教授，会员，研究方向为数据挖掘和机器学习；王月华，女，年生，博士研究生，会员，研究方向为数据挖掘和机器学习；李 艳，女，年生，博士，副教授，研究方向为数据挖掘和供给链管理近似保序序列模式挖掘刘 锦，武优西，王月华，李 艳（河北工业大学 人工智能学院，天津）（河北工业大学 经济管理学院，天津）：摘 要：保序序列模式挖掘旨在时间序列中挖掘保序模式完全相同（最精确）的子序列，其可以用来进行疾病发展趋势预测 但只挖掘最精确的保序模式往往会遗漏一些重要信息 有些保序模式虽然不完全相同，但它们之间仍具有很高的相似性 有鉴于此，本文提出了一种近似保序序列模式挖掘算法（：），该算法能根据输入参数值的不同而挖掘出近似程度不同的保序模式 在候选模式生成方面，算法采用了基于前后缀拼接的模式融合策略，减少了无意义候选模式的数量 在模式支持度计算方面，算法首选获取候选模式的全部候选序列，然后在进行模式匹配 本文通过在真实数据集上进行对比实验，验证了 算法的完备性和高效性关 键 词：模式挖掘；时间序列；保序序列；（）距离；模式匹配中图分类号：文献标识码：文 章 编 号：（），（，）（，）：（），（，），：；（）；引 言序列模式挖掘是数据挖掘的一个热门领域，在近年来获得了信息产业的极大关注 随着网络信息技术的飞速发展，序列模式挖掘在大数据时代的重要性和必要性日益凸显，由于序列模式挖掘具有高效、可解释性强的特性，目前已被广泛应用在生物信息学、疾病检测，、市场营销、网络安全，等领域 时间序列数据作为一种常见而重要的数据，广泛存在于人类的生产生活中，与字符序列不同，时间序列数据是按照时间顺序排列而成的数值序列，蕴含着大量的规律信息，为了快速有效地获得其中有价值的信息，研究者们提出了诸多时间序列分析方法，如序列模式挖掘方法、离散短时傅里叶变换法和逻辑回归法等然而在一些实际应用中，有时元素值的变化趋势要比元素值本身更有意义 例如在股票分析中，股票的变化趋势要比股票的实际价格更值得研究；在气温预测方面，气温的变化显然比气温数值的大小更有意义，因此保序序列模式挖掘应运而生 保序序列模式挖掘是序列模式挖掘的一个新的分支，它适用于时间序列，关注的是元素值的变化趋势而不是数值大小，所以它能挖掘出现频率较高的趋势图 保序序列模式挖掘保证了时间序列的连续性，挖掘出的代表性趋势使得人们可以更好地认识事物的内在变化规律 为了可以灵活地挖掘保序模式，本文提出基于（）距离的近似保序序列模式挖掘算法（，），用来挖掘近似程度不同的保序模式 下面通过例 来说明近似保序序列模式挖掘问题例 时间序列 （，），图 时间序列 的趋势变化图 若采用近似保序序列模式挖掘算法，可以挖掘出时间序列 中频繁出现的趋势图（如图 所示）如当 ，时，可以挖掘出两个子序列（，）和（，），它们的保序模式完全相同，都为（，）当 ，时，则可以挖掘出更长的保序模式，如两个子序列（，）和（，），它们的保序模式分别为（，）和（，）和 的保序模式虽然不完全相同，但与保序模式（，）具有很高的相似性，这是因为 和 与它在每个位置的局部误差都满足，总误差满足 ，可以认为保序模式（，）的相似趋势在 中出现了两次，满足最小支持度阈值，因此（，）是一个频繁的近似保序模式本文的贡献如下：）为了可以灵活地挖掘保序序列模式，提出了局部误差不超过 且整体误差不超过 的近似保序模式挖掘问题）为了完备地解决这个问题，我们提出了 算法在生成候选模式方面，采用了前后缀拼接的模式融合策略，不会生成无意义的候选模式，减少了候选模式的范围 在模式支持度计算方面，首选获取候选模式的全部候选序列，然后在进行模式匹配）在真实的时间序列数据集上进行了对比实验，验证了 算法的完备性和高效性本文剩余部分安排如下：第 节总结相关工作；第 节给出了 问题的相关定义；第 节提出 算法，并分析算法的时空复杂度；第 节验证 算法的性能；第 节得出了本文结论 相关工作序列模式挖掘作为当前的研究热点之一旨在快速找出满足用户特定需求的模式，针对不同问题，已经衍生出多种形式的挖掘方法，如间隙约束挖掘方法，、负序列挖掘方法、高效用挖掘方法、序列规则挖掘方法等 序列模式挖掘方法可以采用多种形式进行划分，如模式支持度计算方式的不同和挖掘数据性质的不同等角度进行划分根据模式支持度计算方式的不同，可以将序列模式挖掘分为精确序列模式挖掘和近似序列模式挖掘 等人采用 方法将时间序列进行分段并对求每段的平均值，然后再挖掘其中的频繁模式；等人根据数据波动将数字时间序列转换为字符型序列，并运用在具有弱通配符间隙的模式挖掘中，这些研究都属于精确序列模式挖掘 而 等人利用效用容忍因子计算模式的可信效用，进而从噪声数据库中提取鲁棒的高效用模式则属于近似序列模式挖掘根据挖掘数据性质的不同，又可以将序列模式挖掘分为字符序列模式挖掘和时间序列挖掘 字符序列模式挖掘主要针对 序列和基因序列等由字符构成的字符型序列，挖掘字符序列通常是为了解决生物信息学中的问题 时间序列挖掘的对象则是由连续变化的数值构成的数值型序列，通常首先采用 算法将时间序列符号化，然后在使用不同的方法进行挖掘，如计算时间序列的先验移动平均的方法、线性回归的方法等 保序模式挖掘的对象就是时间序列，通过挖掘其中频繁出现的趋势图，可以帮助人们进行分析和预测，如股票市场的股价波动分析，某个地点的气温变化分析以及用户行为分析等由于时间序列具有高维性、连续性等特点，直接对其进行挖掘是非常困难的，需要通过一系列转换将原始的数值型数据转换为其它域的数据再进行挖掘，转换的实质就是对时间序列模式来进行重新表示 保序模式匹配问题就与时间序列的次序关系表示紧密相关，基于次序关系的表示与数值型表示并不相同，数值型表示是原始的时间序列数据，而次序关系则是用元素在序列中的秩次进行表示的，所以有相对顺序的概念 等人首先将元素之间的次序关系定义为二元关系（，），并提出了相对顺序的前缀表示和最近邻表示，但没有考虑元素间数值相等的情况 然而两个数值之间的次序关系实际上是三元（，）的，因此 等人对其进行了扩展，将二元关系扩展为三元关系，并设计了一种即使存在元素相等的情况，也能判断两个字符串是否顺序同构的算法 它要求模式与子序列的相对顺序完全相同，能快速定位与已知模式趋势变化完全相同的子序列，为此，等人提出了保序模式挖掘算法，用来发现时间序列中的隐藏规律 上述研究属于精确匹配的研究 而在一定数据噪音存在的场景下，需要研究近似模式匹配，如 等人允许模式和匹配子序列之间存在数据噪声，提出了一种带长度约束的（）近似预测方法，用来找到更加有价值的模式 又如 等人提出基于 距离度量相似度的匹配的精确度，若两个字符串在相同位置删除最多 个元素后具有相同的相对顺序则匹配成功，但该问题的匹配结果存在偏差，因为无法度量子序列与模式之间的局部近似度 等人提表 相关研究工作对比 相关工作研究类型精确 近似数据性质 等人模式匹配精确数值型 等人模式匹配精确数值型 等人模式匹配近似数值型 等人模式匹配近似数值型 等人模式挖掘精确数值型本文模式挖掘近似数值型出基于（）距离的相似度度量方法改善了此问题，采用局部 整体约束，提高了匹配的精确度 表 给出了相关研究工作对比从表 可以看出：文献与本文的研究最为相近，不 期 刘 锦 等：近似保序序列模式挖掘 同之处在于文献是精确的保序模式挖掘，而本文是保序模式的近似挖掘 文献是基于（）距离的保序模式匹配，而本文研究的是保序模式挖掘 文献是基于 距离的保序模式匹配，而本文是（）距离近似 本文将（）保序匹配引入到保序模式挖掘中来，挖掘不同约束条件下的频繁趋势图，适应了更多的应用领域，更好地帮助人们进行分析和预测 相关定义 定义 时间序列：由 个有序的连续数值构成的时间序列可以表示为 （），其中 可以称为元素 定义 秩次：元素 在长度为 的模式 （）中的秩次记作（），定义 相对顺序和保序模式：长度为 的模式 的相对顺序为（）（）（）（），由相对顺序所表示的模式就是保序模式例 给定模式 （，），由于元素 在模式 中第 小，因此其秩次（）；类似的，元素 在模式 中最小，因此（）进而其保序模式（）（，）定义 和：给定两个长度 的序列 和，它们的保序模式分别（）（）（）（）和（）（）（）（）模式 和 的 距离是对应位置相对次序之差的界限，即（，）（）（）；模式 和 的 距离是所有的 距离之和的界限，即（，）（）（）（）（）定义 （）保序出现：对于一个长度为 的保序模式，若在时间序列 中能找到一个长度也为 的子序列，使得 与 的保序模式（）满足（）距离约束，则称 是保序模式 在时间序列 中的一次（）保序出现，其中 和 是两个给定的非负整数 定义 频繁保序模式：如果保序模式 在时间序列 中的（）保序出现数不小于用户给定的最小支持度阈值（），则称 为一个频繁的（）保序模式例 给定 ，（，），（，）在时间序列 中可以找到子序列 （，），将 转化为保序模式后得（）（，），与（）进行（）保序匹配：，；，因此，和 满足（）距离约束，为 在时间序列 中的一次（）保序出现 同理，在时间序列 中的另外 个（）保序出现分别为 （，），（，），（，）定义 近似保序模式挖掘：用户通过自定义参数值，在给定的时间序列 中找到所有满足最小支持度阈值的频繁保序模式例 时间序列 （，），挖掘出所有的频繁（）保序模式在时间序列 中挖掘得到的频繁近似保序模式集 （，），（，），（，），（，），（，），（，），（，），（，）（，），（，），（，）当 时，近似保序序列模式挖掘转化为精确保序序列模式挖掘，因此本文研究是更具一般性研究 对于近似保序模式挖掘，关键的两个步骤是候选模式的生成和（）保序模式支持度的计算 节介绍了候选模式生成策略；节介绍了候选模式支持度计算策略；节介绍了 算法；节对 算法及其对比算法进行了时空复杂度分析 候选模式生成 枚举策略枚举策略是一一列出所有可能出现的情况的策略，假设一个长度为（）的频繁（）保序模式，在其末尾生成一个元素数值，这个元素的数值大小有 种可能性，所以也就可以生成 个候选模式例 长度为 的频繁模式集合 （，），（，），采用枚举策略生成长度为 的候选模式集，结果如下表 所示表 基于枚举策略生成候选模式集 （，）（，），（，），（，），（，）（，）（，），（，），（，），（，）以模式（，）为例，生成长度为 的候选模式有以下 种情形：）新增加的元素小于原始的 个元素时则生成候选模式（，）；）新增加的元素的数值只比第一个大则生成候选模式（，）；）新增加的元素比最小的两个元素数值都大则生成候选模式（，）；）新增加的元素大于原始的 个元素时则生成候选模式（，）由于每个模式可以生成 个候选模式，那么 个频繁模式就可以产生出 个候选模式显然候选模式数量越多，挖掘速度越慢 下一小节中，本文将提出更加高效的模式融合策略减少候选模式的生成 模式融合策略 定义 前缀子模式和保序前缀子模式、后缀子模式和保序后缀子模式：给定序列模式 （），除去最后一个元素 后剩余的子模式 （）就是模式 的前缀子模式，保序前缀子模式就是前缀子模式的保序模式，记做（）；除去第一个元素 后剩余的子模式 （）就是模式 的后缀子模式，保序后缀子模式就是后缀子模式的模式，记做（）定义 模式融合：假设有两个长度都为 的模式 （）和 （），当模式 的后缀子模式的保 小 型 微 型 计 算 机 系 统 年序模式与模式 的前缀子模式的保序模式一致时，即（）（），则 和 就可以拼接生成长度为 的超模式；这里存在 种情况：情况 此时产生一个超模式，其中 ，然后将（）与 进行比较，若 ，那么 ，否则，情况 此时产生两个超模式 和，在拼接为模式 （）时，首先令 ，然后将（）与 进行比较，若 ，那么 ，否则，；在拼接为模式 （）时，然后将（）与