论文部分内容阅读
在数字经济时代,数据型态丰富、复杂而量大,如何挖掘出数据中蕴含着的“效用特征”,是数据科学领域中关键而有挑战性的问题。基于效用驱动的数据挖掘比传统的数据挖掘有着更广泛的应用前景和需求,对于理论研究与工程应用都具有重要意义。在大数据时代,基于效用驱动的模式挖掘理论与技术是数据挖掘领域中的前沿研究课题。基于效用驱动的挖掘理论与技术,其相关研究对社会学、经济学、计算机科学、数据挖掘以及数据库等学科有着重要的科学意义,同时在购物篮分析、风险分析与预测、行为分析、推荐系统等领域有着许多应用前景。效用挖掘受到了广泛的关注与研究,但是诸多关键技术与难点有待深入研究,目前存在的问题包括:第一、效用模式的衡量准则单一。如何定义模式的效用函数,提高效用挖掘结果的可用性,让挖掘得到的结果更好?这是一个关键的基本科学问题。第二、适用处理的数据型态比较单一,应用性不够广。现有的效用挖掘模型和算法大多数针对各式各样的事务型数据,部分针对序列数据。第三、效用挖掘研究的理论与技术不够成熟。如何定义适用于不同型态数据的通用化效用挖掘模型,如何定义其效用计算模型,如何求解通用化的基于效用值的高估上界值,是重要的科学问题。因此,本文主要开展以下研究工作,进一步扩大效用挖掘的内涵与外延,如下所述:在事务数据的层面,针对效用挖掘中效用函数衡量方式存在不足的问题,本文提出了一个基于效用占有(Utility Occupancy)的新衡量准则和高效用占有模式挖掘(High-Utility Occupancy Pattern Mining,HUOPM)算法。该算法提出了两个高度压缩的数据结构:效用占有度列表(Utility-Occupancy list,UO-list)和频率效用表(Frequency-Utility table,FU-table),用于存储事务数据的频度和效用信息。此外,剩余效用占有的概念有助于快速计算出上界值,从而缩减实际的搜索空间。基于所提出的多种修剪策略,HUOPM算法仅需要扫描数据库两次,直接构建UO-list,然后直接从频率效用树中挖掘出结果。HUOPM算法不仅可以成功解决从事务数据中挖掘出高效用占有模式的新研究问题,而且能保证挖掘结果完整不遗漏,挖掘性能表现好。在序列数据的层面,针对高效用序列模式挖掘中存在的挖掘性能差和消耗内存大等问题,本文提出一种紧凑的数据结构,即基于序列的效用阵列(Utility-Array),用于存储被处理序列数据库中的关键信息(例如序列的效用、剩余效用、位置、时间顺序等)。Pro UM(Projection-based Utility Mining)算法通过运用投影机制,可以快速构建出某个序列的扩展序列所对应的效用阵列,能避免采用以往算法中常用的耗时操作:先构建投影序列数据库,再进行扫描处理。本文还提出了序列最大扩展效用值(Sequence Extension Utility),该高估上界值能用于修剪搜索空间,并且保证最终的高效用序列结果的完整性。因此,Pro UM算法可以及早过滤掉大量无希望的序列模式,并快速地在挖掘过程中返回高效用序列模式。大量的实验结果表明,Pro UM算法明显优于目前最先进的高效用序列模式挖掘算法,例如USpan算法和HUS-Span算法,其运行时间更快、消耗内存更少、可扩展性更好。在复杂事件序列的层面,针对现有的高效用情节挖掘算法中存在的挖掘性能差和结果不完整等问题,本文提出了UMEpi(Utility Mining of High-Utility Episodes)算法,用于从复杂事件序列中挖掘出完整的、正确的高效用情节。本文首次提出了基于情节的剩余效用概念和正确的情节加权效用值(Episode-Weighted Utilization,EWU),在此基础上提出基于EWU策略的高效用情节挖掘算法。此外,进一步提出了两个优化的过滤策略,大大提高了基于前缀扩展机制的高效用情节挖掘的性能。相关实验结果表明,UMEpi算法成功解决了目前的高效用情节挖掘算法中存在的缺乏正确的高估上界值和有效的修剪搜索空间的策略等问题。它不仅有效地保证了高效用情节挖掘的完整性和正确性,并且在处理长事件序列或密集型事件序列时具有很好的可扩展性。在挖掘结果的评估层面,提出基于零事务不变相关性的效用挖掘问题,并提出了两种基于不同挖掘机制的算法:Co HUIM算法和Co UPM算法。如何更好地评估效用挖掘的结果,如何让效用挖掘的结果更好、更有实用性,是效用挖掘领域中关键的基础问题。通过衡量相关因子,本文所提的两个算法其挖掘出来的模式不仅是高效用的,而且具有很高的正相关性,它们可以为高效用模式挖掘带来切实可行的效果。Co HUIM算法基于投影技术和Kulc相关性度量的排序向下封闭特性;Co UPM算法基于效用列表的挖掘框架,其挖掘性能更优。大量的实验表明,基于相关性的效用模式比以往算法挖掘出来的单纯高效用的模式,更具相关性,对于推荐和交叉销售等更具实用性。这两个算法研究了如何从事务数据中挖掘出具有相关性的高效用项集,其相关的研究理论与技术可以扩展到处理其他型态数据(例如时序数据、事件序列)的效用挖掘分支,例如挖掘出具有强相关性的高效用情节。