基于自适应k近邻的时间序列异常模式识别

时间序列作为数据的典型代表,被广泛应用于许多研究领域.时间序列异常模式代表了一种特殊情况的出现,在许多领域都具有重要意义.现有的时间序列异常模式识别算法大多只是单纯检测异常子序列,忽略了异常子序列的类别区分问题,且许多参数都需要人为设置.为此提出了一种基于自适应k近邻的异常模式识别算法(anomaly pattern recognitionalgorithm based on adaptive k nearest neighbor,APAKN).首先,确定各子序列的自适应k近邻值,引入自适应距离比计算子序列的相对密度,确定异常分数;然后提出一种基于最小方差的自适应阈值方法确定异常阈值,检测出所有异常子序列;最后,对异常子序列进行聚类,所得聚类中心即为具有不同变化趋势的异常模式.整个算法过程在无需设置任何参数的情况下,不仅解决了密度不平衡问题,还精简了传统基于密度异常子序列检测算法的步骤,实现良好的异常模式识别效果.在时间序列数据集合UCR的10个数据集上的实验结果表明,提出算法在无需设置参数的情况下,在异常子序列检测和异常子序列聚类问题中都表现良好.

会话流中Top-k闭序列模式的挖掘

在会话流中挖掘Top-k闭序列模式,存在因相关比率ρ的大小而导致的内存消耗和挖掘精度之间的冲突。基于False-Negative方法,提出Tstream算法,制定2种约束策略限制ρ。基于该策略设计加权调和计数函数,渐进计算每个模式的支持度。实验结果证明了该算法的有效性。

基于不确定数据的可能频繁闭序列模式挖掘

对于不确定数据的频繁序列模式挖掘,会导致可能频繁模式数量的指数级出现,其中有些无用的挖掘结果会引起频繁序列的冗余。针对上述不足,提出了可能频繁闭序列模式(p-FCSPs)的定义,以及一种基于不确定数据的可能频繁闭序列挖掘算法U-FCSM。此算法中,基于一种元组不确定数据模型计算序列的可能频繁性,应用BIDE算法的闭序列思想判断可能频繁序列是否是可能频繁闭序列模式;为了减少搜索空间与避免冗余的计算,应用了几个剪枝与边界技术。U-FCSM算法的有效性与效率通过大量的实验得以表明。

基于Spark的Top-k对比序列模式挖掘

对比序列模式(distinguishing sequential pattern,DSP)指在目标类序列集合中频繁出现,而在非目标类序列集合中不频繁出现的序列.对比序列模式能够描述2个序列集合间的差异,有着广泛的应用,例如:构建序列分类器,识别DNA序列的生物特征,特定人群行为分析.与挖掘满足支持度阈值要求的对比序列模式相比,挖掘对比度top-k对比序列模式能避免用户设置不恰当的支持度阈值.因而,更易于用户使用.但是现有的top-k对比序列模式挖掘算法难以处理大规模序列数据.对此,设计了一种基于Spark的top-k对比序列模式并行挖掘算法,称为SP-kDSP-Miner.此外,为了提高SP-kDSPMiner的效率,针对Spark结构的特点,设计了候选模式生成策略和若干剪枝策略,以及候选模式对比度的并行计算方法.通过在真实数据集与合成数据集上的实验,验证了SP-kDSP-Miner的有效性、执行效率和可扩展性.

基于包含索引的频繁闭序列模式挖掘的新算法

频繁闭序列模式惟一确定全体频繁序列模式,且规模小得多。传统的闭序列模式挖掘算法对每个频繁项目都进行扩展,往往会产生大量的非闭合序列。为解决这一问题,提出了一种新的基于包含索引的频繁闭序列模式挖掘算法,其主要思想是只对闭项集进行扩展,大大减少了非闭合序列的产生。首先,论证了闭序列模式只能由闭项集组成;其次,说明了如何利用包含索引来快速发现闭项集;最后,给出了一种深度优先的挖掘频繁闭序列模式的新算法。实验结果表明,该算法具有较高的效率。

InClosPan:大型数据库中闭序列模式的增量挖掘

许多现实数据库都以增量形式增长,不希望在每次更新了数据库之后,又重新挖掘完整数据库,增量算法成为必需。研究了当初始数据库中增加了新的事务或增加了新的顾客时,增量挖掘闭序列模式的问题。给出了一个新的频繁闭序列模式增量挖掘算法InClosPan,该算法利用已得到的结果进行增量挖掘,减少了重新挖掘数据库的费用。

数据流中基于滑动窗口的闭序列模式挖掘算法

为了能够有效地利用滑动窗口技术来挖掘数据流当中的频繁闭序列模式,通过构建CST树(closed sequence tree)来保存频繁闭序列模式及其序列之间的关联关系,研究了滑动窗口在流数据上滑动时,窗口内序列属性以及CST树节点相互关系的变化性质,提出了基于滑动窗口的数据流闭序列模式挖掘算法ECSW(efficient closed sequential pattern mining over streamsliding window)。ECSW充分利用CST树内节点的相互关系,减少了对数据库的扫描,并且能够在不借助其他辅助结构的情况下完成CST树节点的更新。比较了ECSW与SeqStream在不同实验参数下的挖掘效果,实验结果表明,在平均闭序列长度不长时,ECSW有着比SeqStream更好的运行效果。

基于K线序列相似性搜索的股票价格预测

现有K线模式主要是通过人工观察方式(即人工相似性搜索)获得的。针对现有K线模式在股票预测中预测效果一般,且部分学者否认K线模式具有预测能力的现状,采用计算机技术和数据挖掘等方法,重新对K线序列相似性搜索预测进行研究。首先,定义K线序列的相似性度量模型,包括K线序列的形态相似性和位置相似性,来解决K线序列的相似性匹配问题;接着,基于K线序列的相似性度量模型,定义K线滑动搜索算法,来解决K线序列的相似性搜索问题;最后,基于K线序列的相似性搜索结果,提出了两种股票价格预测方法:普通序列相似性搜索预测法和模式序列相似性搜索预测法。在实验中,普通序列和模式序列两种方法的预测准确率分别可以达到72.5%和77.8%。实验结果表明,K线模式具有预测能力,且K线模式较普通序列的预测效果更好;提出的两种股票预测方法,均可以较好地应用于股票预测与投资。

基于相似性匹配和聚类的K线模式可盈利性研究

K线模式是股票短期投资中最常用的技术分析工具,但学术界却对K线模式的可盈利性存在争议。为了客观评价K线模式的可盈利性,提出从数据挖掘的角度出发,采用模式识别、模式聚类和模式知识挖掘的方法来对K线模式的盈利能力进行研究。为此,首先定义了K线序列的相似性匹配模型来解决K线模式的相似性匹配问题;然后,定义了K线序列的最近邻聚类算法来解决K线模式的聚类问题;最后,定义了K线模式盈利能力度量模型来对K线模式不同形态的利能力进行分析。实验采用近11年上证180指数成份股的数据作为测试数据集,对白三兵和黑三鸦这两个模式的盈利能力进行分析。实验结果表明:同一个K线模式的不同形态的盈利能力差别很大,有时甚至完全相反,这是K线模式可盈利性产生争议的一个主要原因。为了解决这一争议并提高基于K线模式的股票投资效果,亟需根据形态特征对现有的每一个K线模式做进一步分类,并提供更加严谨的模式定义。

基于模糊K线序列比对的股市技术分析模型

提出一种新的股市技术分析模型,该模型利用模糊逻辑理论及生物序列比对方法的思想,加以改进,应用于传统的K线图理论,将单位时间的开盘、收盘、最高、最低价格编码成模糊K线图,通过模糊序列比对,来对K线图进行模式识别。以上海和深圳自1990年开市以来到2006年的所有数据作为比对数据库,以2007年、2008年的数据作为测试对象,对上海和深圳股票市场中的部分股票中的K线图模式及未来趋势作了分析和预测,取得了可观的结果。统计结果表明,一些K线模式序列的未来趋势分布具有涨跌信号预警的功能;而另一些模式则为平凡的序列匹配,它们未来趋势的分布不具有预警的功能。

度量空间的序列商,k-映象

本文给出了度量空间序列商 ,k 映象的一些内部刻画 ,证明了空间X是度量空间的序列商 ,k 映象当且仅当X具有紧有限k 闭cs 覆盖列的点星sn 网 ,当且仅当X具有紧有限k 闭覆盖列的点星网 .作为上述结果的一个推论 ,不仅得到了空间X是度量空间序列商 ,k 映象当且仅当X是度量空间的k 映象 ,而且还证明了空间X是度量空间当且仅当X具有局部有限 (紧有限 )闭 (k 闭 )覆盖列的点星弱邻域网 .这里“闭”(“k闭”)

挖掘频繁闭序列的一种改进算法

由于频繁闭序列在数量上要远小于频繁序列且与频繁序列有着相同的表达能力在近几年倍受关注.频繁闭序列挖掘过程中最耗时同时也是最关键的步骤是序列间的包容关系检查,作者分析了频繁闭序列自身的特点以及已有的频繁闭序列挖掘算法,提出了一个挖掘频繁闭序列的算法FCSeq,该算法通过引入快速包含检查策略大大减少了不必要的包容关系判断,对提高算法的性能有着显著的作用,实验表明该算法有效.

微博用户特征量增长规律研究

根据抓取到的新浪微博实际用户数据,分析了粉丝数、关注数和微博数3个特征量的增长模式,发现这3个特征量整体上都随时间线性增长,取整后的增长率服从幂律分布.用户特征量增长模式主要呈持续增长和爆发式增长,其中爆发式增长用户按增长的不同阶段又可以划分为前期、中期、后期和阶跃式4种增长模式.使用基于向量余弦距离相似性的K-means聚类算法,对不同排序和不同初始规模实际用户特征量的时间序列进行聚类分析,统计得到不同增长模式的用户数量.发现用户特征量中增速高的用户增长主要以爆发式增长为主,而规模高的用户增长以持续式增长为主.通过对用户粉丝数爆发式增长的过程分析,对比用户微博被转发和被评论二者的增长关系,提出了导致用户粉丝数爆发式增长的原因.

基于序列划分的压缩序列模式挖掘算法

研究了静态数据库当中挖掘压缩序列模式的问题,提出了一个压缩序列模式挖掘算法.该算法通过对闭序列模式全集进行划分处理,降低了序列的比对空间,并结合δ-dominant序列检测机制,有效的挖掘出了压缩序列模式集.实验表明,该算法具有较好的运行效率.