论文部分内容阅读
从海量的数据中挖掘出有价值的模式是非常重要的研究领域。数据挖掘的早期研究主要集中在频繁模式挖掘，目标是识别出在事务数据库中出现次数较多的项目集。这些频繁的模式能够帮助企业更好的理解数据并且提供决策支持。然而随着数据丰富度的增加，模式的频次信息不能满足工业界的应用需求，因此面对复杂的数据类型和多样的属性信息，许多基于频繁模式挖掘的拓展研究被相继提出。其中，高效用序列模式挖掘是近年来重要的研究领域之一。高效用序列模式挖掘支持在数据中找到重要的模式，并且使用数值型的“效用”度量来评估模式的重要性。例如，在交易型数据库中，“效用”为企业盈利的度量，企业可分析消费者购买产品的时间和习惯，挖掘出能够带来高额利润的高效用模式来预测消费者的未来购买行为并作出合理的推荐；虽然高效用序列模式挖掘在生活中有着广泛的应用，但是同时它也存在一个不可忽视的局限：“效用”度量通常不足以真正的或者客观的评价模式的实用性。传统的高效用序列模式挖掘只对模式可能提供的效益进行了评估，但是却忽略了实际使用这些模式的所需成本，比如时间投入，资源投入等等。以医院场景举例，通常情况下，患者们会接受不同的治疗方案，每一套治疗方案被记录为以时间顺序排列的事件列表，而效用代表患者是否被医治成功（或者是医治成功的概率）。那么在此类日志记录数据库中应用高效用序列模式挖掘可以发现一些高效的治疗方案，比如模式，代表着许多患者通过该治疗模式得到了康复。尽管挖掘出的模式在帮助医治患者上有一定的指导意义，但是它们的价值也受到另一重要因素的影响，即在实际应用模式时所需要付出的时间，金钱和资源成本。应用高效用序列模式挖掘算法会挖掘出很多能够产生高效用但是同时具有非常高成本代价的方案；同样的，它也可能会错过一些具有较好效用并且产生较小成本的模式。显然，以上两种情况都是不理想的。
为解决这一局限，本文提出了在事件日志数据库中挖掘低成本高效用模式。本文针对实际生活中存在的不同应用场景，即事件日志数据库中的效用类型分别为数值型和二分类类型，提出了两类算法挖掘相应的低成本高效用模式。此外，针对两种不同的应用场景，本研究设计并应用了相应的统计度量用以评价模式，因此可根据评价结果对挖掘出的模式按照重要程度进行排序。最后,本研究设计并提出了效果显著的剪枝策略和搜索策略，提高了算法的运行效率以及減少了内存用量。
序列事件日志(SEL)由若干序列记录组成，SE L=.一个序列记录包括若干事件按照时间顺序排列的列表和该记录的效用，Ss=<{e1[c1],e2[c2],...em[cm]}|Utilit y>；其中ei代表事件（按照时间顺序排列），ci代表事件的成本，Utilit y代表该序列Ss的效用，其中一种为数值型，另一种是二分类类型（表示为?or+,代表负例和正例）。模式p=由按照时间排序的事件列表组成。模式p在某一序列的代价等于此模式中的事件成本总和，c(p,Ss)=∑ei∈f irst(p,Ss)c(ei,Ss)如果p?Ss，否则等于0；模式p在整个日志记录中的成本等于它所在不同序列中的成本总和的均值，c(p)=∑p?Ss∧Ss∈SEL c(p,Ss)。比如在Table3-1中，在第一个序列中，模式的代价为c(,S1)=2+4=6。假设用户以花费的钱数（美元）作为成本度量，那么应用模式的成本为6美元；那么模式在整个数据库中成本均值为为9美元，c()=(c(,S1)+c(,S3)+c(,S4))/3=((2+4)+(5+8)+(3+5))/3=9。以上信息对用户非常有帮助，因为他们可以规避占用太多资源的模式。
本文首先研究当效用类型为二分类类型时挖掘产生较小成本并能产生正向结果（+）的模式。在用户设置的最大代价maxcost和最小支持度minsup阈值的条件下，挖掘出支持度不小于mingsup并且成本不大于maxcost的模式。此外，因为满足上述条件的模式可随机分布在具有正例和负例效用的序列中，所以模式与二分类效用之间的因果关系不能唯一确定。因此为解决这一问题，本文提出了一个统计度量，该度量根据模式分别在正例和负例中出现的频次以及它们所消耗的成本分布差异来评估这些模式与正向结果的关联度。关联度的测量公式为cor(p)=ac(D+p)?ac(D?p)/Std√sup(D+p)/|Dp|supD(D?p)/|Dp|，其中ac(D+p)和ac(D?p)分别代表模式p在正例序列集合和负例序列集合中的均值代价,Std是模式p在整个数据库中代价的方差，sup(D+p)和sup(D?p)代表模式p分别在正例序列集合和负例序列集合中的支持度。它的结果所在的范围为[?1,1],如果结果越趋近于+1，那么该模式与理想结果(+)的关联度越强；相反，若结果越趋近于?1，那么该模式与负向结果(?)的关联度越强。例如，在线学习的事件日志数据库中会记录学生的学习路径，比如观看视频，阅读材料，参与小测，参加讨论等等，以及学生在每个资源上使用的时间以及他们在最后测验中的考试结果(pass或者f ail)。学习路径的选择以及在每个资源上花费时间的多少都会影响学生在测验中取得的成绩。模式p=用时5小时，它的关联度度量为cor(p)=0.85；而另一模式p′=用时2小时，它的关联度度量为cor(p)=?0.56。那么，模式p与通过考试之间有更紧密的联系，相反，模式p′会降低学生通过考试的概率。
本文针对效用类型为数值型的应用场景研究了高效率(trade-off)模式挖掘。其中，模式p的效用定义为模式所在的序列的效用总和的平均值,u(p)=∑p?Ss∧Ss∈SEL su(Ss)/|sup(p)|，其中su(Ss)代表序列Ss的效用值。挖掘出的模式要同时满足：支持度不小于misup,代价不大于maxcost以及效用不小于minutility。此外，当成本和效用都是数值类型的变量时，本文提出了能够反映成本和效用两者之间权衡大小的统计度量用以评价模式的重要程度。统计度量的定义为模式的平均成本与平均效用之比，t f(p)=∑p?Ss∧Ss∈SEL(c(p,Ss)/su(Ss))。它的结果在(0,∞]之间，且权衡值的大小反映出模式的效率，如果一个模式的权衡值越趋近于0，则表明它可以在花费较小成本的同时提供可观的效用;相反，如果一个模式的权衡值较大，则表明它是低效的，因为它需要付出很多的成本却取得了微小的效用。例如，一个具有较小权衡值的模式意味着学生能够付出相对较少的时间获得一个较高的分数。例如模式p1=,所有学生平均花费24小时，最终在统一测验中平均获得了90/100分,那么它的权衡值t f(p1)=0.24;而模式p2=,所有学生平均花费50小时，平均获得60/100分，那么t f(p2)=0.83，所以模式p1比p2更高效。
在算法设计方面，本文研究并设计了三个高效的算法在庞大的搜索空间中挖掘满足条件的模式。本文提出的三个算法以Prefixspan算法的搜索过程为原型，在搜索过程中首先考虑由单个事件组成的模式，并通过递归地附加事件获得候选项集。为了减少搜索过程中因为创建和存储投影数据库而导致运行时间和内存的大量消耗，本文提出并应用了投影数据库缓存数组。在算法执行深度优先搜索时，通过覆盖掉已经搜索完成的空间占用内存以达到节约内存的目标。此外，在缓存数组中加入了搜索索引，这也加快了计算候选模式的效用、成本等属性信息，从而整体上提高算法的运行效率。算法的性能通过在四个标准的基准数据集，Bible,BMS,SIGN和FIFA上的表现进行评估。因为四个数据集拥有不同的特征，密集，稀疏，长序列和短序列，因此实验结果可以客观的反映出算法的性能。实验结果表明所提出的优化方法以及提出的基于下界的剪枝策略可以将算法的运行效率提高10倍，而在内存节约方面，在不同的数据集中的提升大小有所差异，但是均有提升。此外，本研究提出的算法被应用在实际生活中在线学习平台的数据集上。通过对挖掘出的模式可视化分析以及与测验考试中的覆盖知识点的比对分析，表明本研究提出的算法能够挖掘出有指导意义的低成本高效用模式。这些模式能够为学生和老师提供关于如何更加高效地使用学习材料的建议帮助。
为解决这一局限，本文提出了在事件日志数据库中挖掘低成本高效用模式。本文针对实际生活中存在的不同应用场景，即事件日志数据库中的效用类型分别为数值型和二分类类型，提出了两类算法挖掘相应的低成本高效用模式。此外，针对两种不同的应用场景，本研究设计并应用了相应的统计度量用以评价模式，因此可根据评价结果对挖掘出的模式按照重要程度进行排序。最后,本研究设计并提出了效果显著的剪枝策略和搜索策略，提高了算法的运行效率以及減少了内存用量。
序列事件日志(SEL)由若干序列记录组成，SE L=
本文首先研究当效用类型为二分类类型时挖掘产生较小成本并能产生正向结果（+）的模式。在用户设置的最大代价maxcost和最小支持度minsup阈值的条件下，挖掘出支持度不小于mingsup并且成本不大于maxcost的模式。此外，因为满足上述条件的模式可随机分布在具有正例和负例效用的序列中，所以模式与二分类效用之间的因果关系不能唯一确定。因此为解决这一问题，本文提出了一个统计度量，该度量根据模式分别在正例和负例中出现的频次以及它们所消耗的成本分布差异来评估这些模式与正向结果的关联度。关联度的测量公式为cor(p)=ac(D+p)?ac(D?p)/Std√sup(D+p)/|Dp|supD(D?p)/|Dp|，其中ac(D+p)和ac(D?p)分别代表模式p在正例序列集合和负例序列集合中的均值代价,Std是模式p在整个数据库中代价的方差，sup(D+p)和sup(D?p)代表模式p分别在正例序列集合和负例序列集合中的支持度。它的结果所在的范围为[?1,1],如果结果越趋近于+1，那么该模式与理想结果(+)的关联度越强；相反，若结果越趋近于?1，那么该模式与负向结果(?)的关联度越强。例如，在线学习的事件日志数据库中会记录学生的学习路径，比如观看视频，阅读材料，参与小测，参加讨论等等，以及学生在每个资源上使用的时间以及他们在最后测验中的考试结果(pass或者f ail)。学习路径的选择以及在每个资源上花费时间的多少都会影响学生在测验中取得的成绩。模式p=
本文针对效用类型为数值型的应用场景研究了高效率(trade-off)模式挖掘。其中，模式p的效用定义为模式所在的序列的效用总和的平均值,u(p)=∑p?Ss∧Ss∈SEL su(Ss)/|sup(p)|，其中su(Ss)代表序列Ss的效用值。挖掘出的模式要同时满足：支持度不小于misup,代价不大于maxcost以及效用不小于minutility。此外，当成本和效用都是数值类型的变量时，本文提出了能够反映成本和效用两者之间权衡大小的统计度量用以评价模式的重要程度。统计度量的定义为模式的平均成本与平均效用之比，t f(p)=∑p?Ss∧Ss∈SEL(c(p,Ss)/su(Ss))。它的结果在(0,∞]之间，且权衡值的大小反映出模式的效率，如果一个模式的权衡值越趋近于0，则表明它可以在花费较小成本的同时提供可观的效用;相反，如果一个模式的权衡值较大，则表明它是低效的，因为它需要付出很多的成本却取得了微小的效用。例如，一个具有较小权衡值的模式意味着学生能够付出相对较少的时间获得一个较高的分数。例如模式p1=
在算法设计方面，本文研究并设计了三个高效的算法在庞大的搜索空间中挖掘满足条件的模式。本文提出的三个算法以Prefixspan算法的搜索过程为原型，在搜索过程中首先考虑由单个事件组成的模式，并通过递归地附加事件获得候选项集。为了减少搜索过程中因为创建和存储投影数据库而导致运行时间和内存的大量消耗，本文提出并应用了投影数据库缓存数组。在算法执行深度优先搜索时，通过覆盖掉已经搜索完成的空间占用内存以达到节约内存的目标。此外，在缓存数组中加入了搜索索引，这也加快了计算候选模式的效用、成本等属性信息，从而整体上提高算法的运行效率。算法的性能通过在四个标准的基准数据集，Bible,BMS,SIGN和FIFA上的表现进行评估。因为四个数据集拥有不同的特征，密集，稀疏，长序列和短序列，因此实验结果可以客观的反映出算法的性能。实验结果表明所提出的优化方法以及提出的基于下界的剪枝策略可以将算法的运行效率提高10倍，而在内存节约方面，在不同的数据集中的提升大小有所差异，但是均有提升。此外，本研究提出的算法被应用在实际生活中在线学习平台的数据集上。通过对挖掘出的模式可视化分析以及与测验考试中的覆盖知识点的比对分析，表明本研究提出的算法能够挖掘出有指导意义的低成本高效用模式。这些模式能够为学生和老师提供关于如何更加高效地使用学习材料的建议帮助。