一种模糊频繁趋势挖掘新算法:算法工程师是啥专业

　　摘要:本文在Chun-Hao Chen等人的基础上,将模糊频繁趋势挖掘转换为序列模式挖掘并利用序列模式挖掘中的GSP算法生成候选序列模式并进行剪枝,能够更有效减少候选序列模式数量,从而高效的挖掘模糊频繁趋势,提高算法的效率。
　　关键词:时间序列 序列模式挖掘 GSP算法 频繁趋势 模糊频繁趋势
　　中图分类号: 文献标识码:A文章编号:1007-9416(2010)05-0000-00
　　
　　1 概述
　　时序数据是和时间相关的数据。在实际应用中时序数据往往是指用数字或符号表示的时间序列。时间序列在人类社会的各个领域中都广泛存在,如金融证券市场中每天的股票价格变化;商业零售行业中,某项商品每天的销售额;气象预报研究中,某一地区的每天气温与气压的读数;以及在生物医学中,某一症状病人在每个时刻的心跳变化等等[1]。序列模式挖掘(Frequent Sequential Pattern Mining)是由 Rakesh Agrawl等人[2]提出的又一个重要的KDD研究课题,是从序列数据库中发现相对时间或者其他顺序所出现的高频率子序列。其最初动机是想通过在带有交易时间属性的交易数据库中发现频繁项目序列以发现一时间段客户的购买活动规律。近年来序列模式挖掘已经成为数据挖掘的一个重要方向,其应用范围不局限于交易数据库,在Web访问模式、科学实验过程分析、自然灾害预测、疾病治疗、药物检测、入侵检测、DNA分析以及顾客购物行为分析等领域中具有十分广泛的应用前景。
　　从时序数据中发现有用的模式一直被视为重要而有意义的过程。Indyk[3] 等人关注于通过对时间序列一段时间的观察识别不严格周期和平均趋势这样的典型趋势,首先通过多项式卷积产生一个图像模板集,每一个图像都是一个低维向量,然后用其代替每一个间隔时间来发现典型的趋势。Patel[4]等人提出一个基于欧氏距离的挖掘时间序列中频繁模式的算法,首先将时间序列数据规范化,随后利用近似分段集降低数据维数,离散化数据,从中挖掘频繁发生的模式。Ageawal[5] 等人提出通过简单转换从历史时序数据库中获得图形的算法。首先将每两个相邻点的数据值转换为一个预先定义好的类,例如增加、剧增、剧减、减少、无变化和零值。同一时间序列可以有很多标签。转换后的标签序列可用作结果的查询。Keogh[6] 等人提出了一种结合后缀树和隐马尔科夫模型挖掘模式的挖掘算法。上面的几种方法,通常需要预先定义每个类别的间隔,而且需要掌握一定的领域知识并且依赖实际的应用,Udechukwu[7]等人提出了一个领域无关的趋势编码方法挖掘频繁趋势,他们首先将相邻数据点的不同数据值转换为一个角度,以此代替数据值本身,角度的范围在-90°到90°之间,并将该区间分为52个角度类,分别用52个字母加以表示,其中用小写字母表示正角,大写字母表示负角,然后用数据结构中的后缀树来挖掘最大重复子模式,即频繁趋势,这样可以避免领域知识对数据预处理的影响。2008年Chun-Hao Chen[8]等人在此基础上,引进模糊概念处理数据值分解问题,并利用滑动窗口生成角度的子序列,通过Apriori算法结合简单的剪枝处理得到模糊频繁趋势。本文将模糊频繁趋势挖掘转化为对角度子序列的频繁序列模式挖掘,并利用序列挖掘中的GSP算法挖掘经过模糊处理的子序列,从而产生模糊频繁序列模式作为模糊频繁趋势。
　　
　　2 模糊频繁趋势挖掘
　　2.1 模糊集合概念
　　模糊集合的概念是美国科学家扎德(L.A.Zadeh)1965年提出的,用于处理人类日常推理中固有的模糊性和不精确性,现已广泛应用在各个领域。我们所使用的概念都具有一定的内涵和外延,内涵是概念所代表的事物的本质属性,在模糊集论中等价于集合的定义。外延是具有该本质属性的一切事物,在模糊集论中等价于组成该集合的一切元素。这里通过使用内涵和外延的概念来定义模糊集。
　　定义:如果一个集合有清晰的内涵和外延,则为普通集。例如一个班级中的所有男生,这个集合就是一个普通集。
　　定义:如果一个集合无清晰的内涵和外延,则为模糊集。例如一个班级中的高个子,这个集合就是一个模糊集。
　　模糊集合的特征函数定义为: 等于[0,1]中的任一值, 称为隶属度。通常用符号A代表模糊集合,x1,x2…xn是其中的元素, 1, 2… n分别是它们在模糊集A中的隶属函数,则A可以有如下表示:
　　这里需要说明的是“+”并不是求和,而是表示个元素和特征函数对应关系的总括。
　　模糊集合A的 ―截集是一个硬集合 定义为:
　　定义:在有限通用集合X上的模糊集A中所有元素隶属度的和即为A的势
　　两个模糊集合之间的运算,实际上是对特征函数作相应的运算,其中最常用的有补集、交集和并集。
　　补集:
　　交集:
　　并集:
　　2.2 GSP算法
　　GSP(Generalized Sequential Patterns)算法是一种非常有效的序列模式挖掘算法,该算法使用一种称作为逐层搜索的迭代方法,首先找出频繁1-序列模式的集合SL1,SL1用于寻找频繁2-序列模式SL2,SL2用于寻找频繁3-序列模式SL3,…,如此下去,直到不能找到频繁序列模式为止。GSP算法的执行过程与类Apriori相似,最大的不同在于GSP引入了时间约束、滑动时间窗和分类技术,增加了扫描的约束条件,有效地减少了需要扫描的候选序列的数量,同时还克服了基本序列模型的局限性,更切合实际,减少多余的无用模式的产生,另外GSP利用哈希树来存储候选序列,减少了需要扫描的序列数量,同时对数据序列的表示方法进行转换,这样就可以有效地发现一个候选项是否是数据序列的子序列,效率比类Apriori要高出2到20倍。
　　序列模式挖掘算法GSP
　　输入:序列数据库SD;最小支持度阈值minsup。
　　输出:序列数据库SD中的频繁序列模式。
　　方法:
　　SL1={频繁1-序列模式};//扫描序列数据库SD一次便可得到SL1
　　For(k=2;SLk-1≠ ;k++) do begin //循环迭代,直到不能找到频繁k-序列模式为止
　　SCk= Generate(SLk-1);//由频繁(k-1)-序列模式生成候选频繁k-序列模式集
　　扫描序列数据库SD,计算SCk中各序列模式的支持数;
　　SLk={sc∈SCk�Sup(sc)≥minsup};//生成频繁k-序列模式集SLk
　　End
　　GSP需要多次扫描序列数据库,在第一次扫描中,对所有的单个项目(1-序列模式)进行计数。利用频繁1-序列模式生成候选频繁2-序列模式,进行第二次扫描并求候选频繁2-序列模式的支持数。使用频繁2-序列模式生成候选频繁3-序列模式,重复以上过程,直到找出所有的频繁序列模式。算法中的两个主要步骤是:
　　①Generate(SLk-1)给定频繁(k-1)-序列模式SLk-1,在SLk-1中的频繁序列模式之间做join运算,产生候选频繁k-序列模式SCk,并删除SCk中至少有一个(k-1)-子序列为非频繁序列模式的候选k-序列模式(因为频繁序列模式的任何子序列模式均为频繁序列模式)。
　　设参加join运算的两个序列模式为s1,s2∈SLk-1,设s1=,s2=,s11=(x11,x12,…x1p),s2m=(x21,x22,…x2q),s11′=(x12,…x1p),s2m′=(x22,…x2(q-1)),即s11′为删除s11中第一个项目后的结果,s2m′为删除s2m中最后一个项目后的结果,则s1和s2必须满足的join准则是:
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文 　　如果q=1,且=成立,那么生成候选频繁k-序列模式s12,s12=,即将s2的最后一个项目集插入到s1中。
　　如果q>1,且=成立,那么生成候选频繁k-序列模式s12,s12=,即将s2的最后一个项目插入到s1的最后一个项目集的最后一个元素。
　　如s1和s2不满足上述两种情况之一,那么无需考虑s1和s2的结合。
　　②计算SCk中各候选序列模式的支持数。其基本思路与关联规则挖掘中的支持数计算方法相一致。对序列数据库SD中的序列数据sd,找到sd的所有候选序列模式,产生sd的所有k-子序列模式,对于每个子序列模式用hash索引查找,如果hash树上的候选序列模式与子模式匹配,则候选序列模式的支持数加1。
　　2.3 模糊频繁趋势挖掘算法
　　本算法基于模糊集,GSP算法和时间序列的概念来挖掘模糊频繁趋势。首先将数据值转换为角度,然后利用滑动窗口在角度序列中生成连续的子模式。随后利用GSP算法生成模糊频繁趋势。
　　算法描述如下
　　输入:有m个数据点的时间序列S,一组隶属函数h,最小支持度α,滑动窗口长度l。
　　输出:模糊频繁趋势集
　　1:将S中相邻两个点的数据值转化为角度,设原来S=(d1,d2,d3,…dm),则转换后的角序列为S’=(a1,a2,a3,…am-1),ai是数据值di指向di+1的角度。
　　2:根据滑动窗口长度l将角序列S’转换为一个子序列集合W(S’),即
　　W(S’)={Sp�Sp=(ap,ap+1,…ap+l-1), p=1 to l-w },其中ap是S’中第p个角度的值。
　　3:将每个子序列中元素vpj根据给出的模糊函数转化为模糊模糊集fpj,有如下表示 ,Rjk为每个子序列中第j个数据的第k个模糊区域,h是模糊隶属函数的个数,fpjk是区域Rjk中vpj的模糊隶属度。Rjk即为一个模糊组。
　　4:计算每个模糊组Rjk的标量势。
　　5:所有的模糊组构成候选1-模式集C1。
　　6:计算C1中每个模糊组的支持度,support(Rjk)=countjk/(m-l),若support(Rjk)≥α,将其放入1-频繁模式集L1中。即
　　L1={Rjk�countjk≥α,1≤j≤p+l-1 且1≤k≤h}
　　7:若L1非空,则进行如下操作,否则退出算法。
　　8:r=1,r用于表示正待处理的模糊集中模糊组数。利用GSP算法连接Lr产生候选(r+1)-模式集Cr+1,注意由相同两个数据点产生的位于不同子序列的项不能同时存在于Cr+1。此外根据GSP算法,若候选序列模式的某个子序列不是序列模式,则此候选序列模式不可能是序列模式,将它从候选序列模式中删除。
　　9:对每个Cr+1中新生成的、模糊组为(I1,I2,…Ir+1)的(r+1)-模式I的做如下操作:
　　 (1)计算每个子序列中I的模糊度
　　其中 是Sp中模糊模式Ij的隶属度。根据模糊集合的交集运算定义,有 。
　　(2)计算所有子序列中I的计数
　　(3)若I的支持度大于等于最小支持度α,将I放入Lr+1。
　　10:若Lr+1为空,进行下一步操作,否则,令r=r+1,重复步骤8、9。
　　11:将每个模式(I1,I2,…Iq),q≥2,转换为(I1′,I2′,…Iq′),具体操作是将I1模糊区域Rjk转换为I1′中的R1k,将其他项Rit转换为R(i-j+1)t,这里Rjk是子序列中第j个数据的第k个模糊区域。通过转换,可以发现频繁模式集中的重复模式。
　　12:将多余重复模式移除频繁模式集。
　　13:输出最大频繁模式集作为模糊频繁趋势。
　　
　　3 实验及结果分析
　　这里将通过实验验证模糊频繁趋势挖掘算法。算法采用Java语言编程,运行环境为Windows XP,Pentium4,主频3.2GHz,内存512MB。
　　3.1 实验数据
　　本实验采用The UCI KDD Archive中的合成控制图表数据集,该数据集包括600个由控制图产生的例子,有6个不同类别的控制图:正常、循环、增加趋势、下降趋势、上移、下移。数据存储在ASCII文件中,有600行,60列,每行有一个单一的图表。数据组织如下:1-100为正常,101-200为循环,201-300为增加趋势,301-400为下降趋势,401-500为上移,501到600为下移。每个时间序列有60个时间点。
　　3.2 实验过程及结果分析
　　(1)以属性为下降趋势的数据集为例,在最小支持度为1.5%(依据先前经验给出),滑动窗口大小为10的情况下,通过实验可以发现下降趋势的模糊频繁趋势为:Z z W W x S Y。
　　(2)实验进一步对Apriori-based算法和GSP算法在生成的频繁项集的数量方面进行对比,通过图5.1可以看出GSP算法在后期的剪枝工作效果是显著的,能够有效减少候选项集的数量,实现算法的高效性。
　　(3)进一步实验探讨滑动窗口大小与其相应产生的模糊频繁趋势的个数关系,如图5.2所示,可以得到的结论是当窗口增大时,相应产生的模糊频繁项集的个数也会增多。
　　
　　4 结论与展望
　　提出了将趋势分析转换为序列模式挖掘的新思路:将原序列通过角度变换和滑动窗口的使用转换为一系列联系的角序列,通过GSP算法对角序列进行模式挖掘得到最大频繁模式,即频繁趋势。实验表明,该算法在剪枝方面优势明显,有效提高算法的效率,并且能够准确挖掘出模糊频繁趋势。另外使用了模糊概念处理边界值情况,是结果准确性得以进一步提高,最后通过实验和实验数据证明了该算法的可行性。当然本文提到的算法还是有很多需要解决的难题,比如滑动窗口的选取,支持度的选取,这些将是我今后研究工作的方向。
　　
　　参考文献
　　[1] 肖辉.时间序列的相似性查询与异常检测:(博士学位论文).上海:复旦大学,2005
　　[2] Agrawal R, Srikant R. Mining sequential pattern.Proc of the 11th International conference on Date Engineering. Taipei,1995.
　　[3] Indyk P,Koudas N,Muthukrishnan S.Identifying representative trends in massive time series data sets using sketches.In The 26thinternational conference on very large data bases,2000:363-372.
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文