论文部分内容阅读
数据挖掘已经成为一项利用这些数据的重要的科技手段,对这个技术领域的科学研究也正在以越来越快的速度蓬勃发展。关联规则挖掘又称频繁项集挖掘,是数据挖掘科研领域的一个热门研究方向,它的主要目的是找到所有的项的集合,并且这些集合满足在数据库中出现的次数不小于一个最小支持度阈值的条件。关联规则挖掘在现实生活中具有很多应用场景,例如图的分类,恶意软件检测,顾客消费行为分析,社区关系查找等等。很多研究工作都致力于高效地找出所有的频繁项集,从大量的数据当中发掘出有用的信息。可是,传统的频繁项集挖掘算法忽视了数据库中不同事务或者事件之间的前后时间顺序的重要性,无法提供和事件发生的先后顺序有关的有用信息。在生物信息科技,在线学习,文本数据分析和智能家居中的节能等诸多领域,都需要将事件发生的前后顺序和传统的数据挖掘结合起来,以提供更多具有实际应用意义的模式。最近几年,很多学者提出的新的算法,都将事件的时间顺序考虑了进去,并且成功在实际中加以应用。其中非常重要的一个分支就是序列模式挖掘,将频繁项集挖掘和时间序列相结合,找到那些频繁出现的子序列。然而,序列模式挖掘算法无法挖掘出那些周期性出现的模式,而周期模式却在分析顾客消费行为,基因序列分析,网站功能区设计等众多领域具有很大的作用。例如牛奶面包这个消耗品组合在网上超市当中的购买量一般都很大,而对于单个顾客来说,他可能每隔一段时间就需要网上购买一些牛奶面包。分析顾客的这种周期性发生的行为有助于更精准的为他们提供推荐服务,促进消费。又比如,在基因序列的分析当中,DNA分子的不同排列顺序携带了完全不同的基因信息。而如果一些DNA分子组合序列在整个基因序列当中周期性地出现的话,这些组合序列也会呈现出不同的表达形式,从而为人类基因分析工作提供一些新的可能和研究方向。因此,近几年来,周期模式挖掘渐渐成为关联规则挖掘当中的一个热门研究方向,针对周期模式挖掘已经有很多学者做了充分的研究。但是,先前的周期模式挖掘算法都是针对单个时间序列进行挖掘,而现实中遇到的数据大多都为多个序列组成的序列数据库。据我们所知,在我们之前,仅有一篇发表于2017年的论文曾做过多序列的周期模式挖掘的研究工作。这篇论文提出了一种新的被表示为PHUPSM的算法,用来挖掘多个序列中的周期性高效用项集。然而,这个算法仅仅将多个序列当做一个序列来进行处理,而忽视了单个序列之内的模式的周期性,导致挖掘出的模式不具有太大的实际意义。所以,之前所提出的算法都不适合用于很多序列组成的数据库的周期模式挖掘。为解决这个问题,本课题致力于基于多个时间序列的周期频繁模式挖掘算法的研究。这篇论文定义了两个新的衡量方法,分别称为周期标准差和序列周期率。周期标准差是用来挖掘单个时间序列中的周期模式。之前的研究中采用的最大周期数的衡量方法条件太过苛刻。当最大周期数被设定为一个较大的数值时,挖掘出的模式很多都是无用的信息;而这个阈值被设定为一个较小的数值时,又会丢失大量周期时间长的周期模式。所以,合适的最大周期数的阈值总是难以确定。而本论文提出的周期标准差方法很好的解决了这个问题,使得最大周期数可以被设置为一个较大的值,而通过周期标准差来过滤那些非周期模式。并且,通过这个方法挖掘出来的模式的周期差别也可以被控制在一个很小的范围之内。序列周期率则代表数据库中的模式在序列中具有周期性的序列个数的最小阈值,用来确保挖掘出的模式在多个序列中都具有周期性行为。通过这两种衡量方法,数据库中同时在多个序列中都具备周期性行为的所有模式就都能被挖掘出来。为了更加高效地挖掘出这些周期模式,本课题项目提出了两种算法,分别表示为MPFPSBFS和MPFPSDFS。这两种算法分别采用了广度优先搜索和深度优先搜索的空间搜索方式。广度优先搜索列举出所有的项集集合,之后再判断这些项集是否具有频繁性和周期性。例如,对于一个包含了a,b和c这三个不同的项的数据库来说,广度优先搜索策略首先判断这三个项是否满足频繁性和周期性地要求,之后再进行两两组合得到包含了两个项的项集{a,b},{a,c}和{b,c}。然后,再对这三个项集进行判断,再之后产生包含了三个项的项集{a,b,c}……广度优先搜索则采用了另外一种搜索策略。首先判断a是否满足条件。然后,产生a的所有包含了两个项的父集{a,b}和{a,c},再判断频繁性和周期性。最后产生a的所有包含了三个项的父集{a,b,c},再进行判断。对于b和c采取同样的操作。这样就保证所有的项集集合都被检查了一遍,没有遗漏。然而,无论是广度优先搜索还是深度优先搜索,挖掘周期频繁模式的搜索空间都极大。对于含有n个不同项的数据库来说,这些项组合形成的项集个数则为2n-1.如果对这个指数级大小的搜索空间直接进行挖掘,算法的效率将会十分的低下。另一方面,新提出的序列周期率方法并不满足单调性或是反单调性,也就无法直接用来对搜索空间进行剪枝。为了解决搜索空间过大的问题,本论文提出了一种被表示为boundRa的新参数和两个基于boundRa的剪枝策略。boundRa实际上是序列周期率的一个上界,满足向下闭包的特性。提出的两个剪枝策略都是基于这个特性。第一个策略的理论基础是,假设最小序列周期率的值为minRa,对于一个项集X’,如果boundRa（X’）BFS和MPFPSDFS都具有四个参数,分别是minSup,maxStd,minRa和maxPr。实验结果表明这四个参数都有助于过滤那些不满足频繁性和周期性的项集。所以,这两个算法可以用来找出所有的周期频繁模式,并且挖掘出的模式数量也可以被控制在一定的范围之内。另外,结果表明这些参数也可以被用来减少降低算法运行的时间和占用的空间。如何来设置这些参数则需要根据不同数据库来具体问题具体分析。因为不同的数据库中的模式的周期长度都不尽相同,周期变化的幅度大小也各不一样。从结果中可以发现,参数minSup对算法的结果输出以及性能的影响很小,故而本论文建议将minSup设置为一个较小的值,只在性能受到很大影响时才改为一个较大的值。同时,鉴于maxPr这个参数本身条件太过严苛,本论文建议将其设置为一个相对来讲非常大的数值,以过滤掉那些周期太大的周期模式。因此,综合来看,maxStd和minRa这两个新提出的参数在整个周期频繁模式挖掘的过程当中具有更加重要的作用。前者允许指定周期频繁模式随时间变化的周期的最大范围值,对于一个模式来说,只要它的周期的标准差在这个范围之内,那么它的周期性就呈现出了一个非常固定的趋势。后者指定了一个模式呈现出周期性的序列在整个序列数据库中的最小比例值。此参数将可被用来找到在多个序列中呈现出周期性的所有模式。综上所述,本论文在这几年研究成果比较多的周期模式挖掘方面,提出了一个新的问题,即在多个序列当中挖掘出所有的呈现出周期性的频繁模式。针对这个问题提出了两个新的衡量方法,分别是周期标准差和序列周期率。因为序列周期率这个方法不满足向下闭包的特性,故而设计出一个新的参数boundRa。在这个参数的基础上提出了两个剪枝策略,对周期模式挖掘中的庞大的搜索空间进行剪枝,以提升算法效率。最后设计了两个算法MPFPSBFS和MPFPSDFS,实验结果表明这两个算法具有很好的时间效率和空间效率。另外,由于MPFPSDFS采用的是深度优先的搜索策略,因而通过剪枝所带来的性能的提升相较MPFPSBFS来说更加巨大,所以性能和可扩展性都更好。在参数设置的值比较严格时,将会产生百倍以上的性能差距。