论文摘要
随着信息技术尤其是网络技术的快速发展,人们收集、存储和传输数据的能力不断提高,各类应用领域的数据量大量产生,数据挖掘日益成为数据分析和决策支持的一种重要工具。频繁模式挖掘是数据挖掘领域内的一个基本问题,它被广泛应用到多种领域和挖掘任务中,例如Web挖掘、零售业数据挖掘、科学研究、关联规则挖掘、序列模式挖掘、路径分析等。在传统的频繁模式挖掘方法中,事务数据库（Transaction Database,TDB）中的每个项都被看成是同等重要的,而在实际应用中,每个项通常具有不同的重要性。为解决这个问题,本文研究了加权频繁模式挖掘（Weighted Frequent Pattern Mining,WFPM）问题,其主要特征就是在挖掘过程中通过给TDB中各个项目赋予不同的权值来体现它们的重要性不同。经过十几年的研究,已经奠定了较成熟的频繁模式挖掘算法理论基础,但对于加权频繁模式挖掘算法及其应用的研究工作尚处在初始阶段,值得深入研究和探讨。在加权事例中,加权支持度度量不再满足向下闭合特性（亦称反单调性（Antimonotonicity））,传统的频繁模式挖掘算法已经不再适用,因此在加权频繁模式算法中,研究的主要关注点是如何使加权支持度或兴趣度度量满足向下闭合特性（Downward Closure Property）,以便高效地剪枝搜索空间。本文主要以基于Web频繁遍历路径模式挖掘和零售业数据挖掘为实例,详细阐述了基于加权有向图（Weighted Directed Graph,WDG）的加权频繁遍历模式挖掘和加权强相关频繁模式挖掘的有关思想。图遍历模式挖掘一直是数据挖掘研究的热点之一,图及其遍历可广泛地模拟现实世界的多种数据访问形式,比较有代表性的实例就是Web路径访问,Web结构可被抽象为一个加权有向图:顶点代表网页或站点,有向边代表网页间的网页或站点间的超级链接,权值代表Web结构元素的不同重要性,然而传统的遍历模式挖掘算法仅仅考虑了非加权的遍历模式挖掘。为解决加权遍历模式挖掘问题,本文主要从以下几个方面做了深入研究:归纳了加权频繁遍历模式挖掘（Weighted Frequent Traversai Pattern Mining,WFTPM）的种类,将Web加权频繁遍历模式挖掘,从用户类型角度分为个体加权频繁遍历模式挖掘（IndividualWFTPM,IWFTPM）和整体加权频繁遍历模式挖掘（Holistic WFTPM,HWFTPM）;从采取的挖掘方法角度分为普通遍历模式挖掘和序列遍历模式挖掘。提出了加权有向图模型,总结了加权有向图的种类,提出了两类加权有向图——顶点加权有向图（Vertex-Weighted Directed Graph,VWDG）和边加权有向图（Edge-Weighted Directed Graph,EWDG）,并详细阐述了两类WDG间的转换方法,简化了基于加权有向图的频繁遍历模式挖掘问题,完善了基于图遍历的模式挖掘问题的理论基础。基于加权有向图模型,本文做了以下几方面工作。针对挖掘IWFTPM问题,提出了加权遍历模式间的一种新颖特性——可拓展特性,把对候选模式的剪枝问题转化为判断候选模式的可扩展性问题。基于加权模式间的可拓展特性,提出了一种基于加权有向图结构的频繁遍历模式挖掘算法——WFTPMiner（Weighted Frequent Traversal PatternMiner）算法,并提出了实现该算法的两种策略——EGTG（Evaluated by Global Topology of Graph）策略和ELTG（Evaluated by Local Topology of Graph）策略。当最小支持度阈值较小时,用算法WFTPMiner挖掘加权频繁模式将导致效率低下,为克服以上不足,提出了一种修订的加权支持度表示法,然后利用加权FP-tree模式增长方法,提出了两种高效的基于加权有向图的频繁遍历模式挖掘算法:CWFTPMiner（Closed Weighted Frequent TraversalPattern Miner）和WTMaxMiner（Weighted Traversal-based Maximal frequent pattern Miner）,前者用于挖掘闭合加权频繁遍历模式,后者用于挖掘最大加权频繁遍历模式。此外,在实现这两种算法的过程中,详细分析了闭合约束和加权约束的不同结合顺序可能造成的信息丢失现象,提出了两种约束的正确结合顺序。对加权FP-tree模式增长算法的弊端和遍历路径中相关项目的连续性特点,把遍历模式看作是序列模式,提出了一种基于图遍历的加权序列模式挖掘算法WTSPMiner（Weighted Traversal-basedSequential Pattern Miner）,该算法采用一种改进的加权前缀投影模式增长方法,运用分而治之策略,把挖掘原来加权序列数据库的任务分解成一组挖掘局部加权投影数据库的小任务,通过将加权约束添加到挖掘过程中,实现加权频繁序列遍历模式的挖掘。为解决HWFTP挖掘问题,提出了一种挖掘基于统计理论的加权频繁遍历模式挖掘算法SWFTPMiner（Statistical theory-based Weighted Frequent Traversal Pattern Miner）,该算法利用统计理论中的置信度概念,首先清除掉原始遍历数据库T中带有噪声权值的“异常点”（Outlier）,从而得到能反映整体绝大多数用户遍历行为的修订加权有向图Gr及遍历数据库Tr,然后具体提出了两种从修订的Tr中挖掘WFTPs的策略方法——逐层挖掘策略和分而治之挖掘策略。此外,本文以零售业为例,提出了一种加权强相关频繁模式挖掘算法WHFPMiner（WeightedHighly-correlated Frequent Pattern Miner）,在算法中,提出了一种新的目标兴趣度度量标准——加权h-置信度,通过采用修订的加权支持度,证明了加权h-置信度具有反单调性和交叉加权支持性,最终基于加权FP-tree模式增长方法,利用加权h-置信度的两种特性快速地挖掘出包含有相似加权支持度水平的项目的加权频繁模式。广泛的实验性能分析表明,本文提出的算法是高效的和可伸缩的,能够有效的完成各自的加权频繁挖掘任务。更重要的是,本文中提到的很多算法具有广阔的应用领域,例如,基于加权有向图的频繁遍历模式挖掘算法可以很方便地应用到很多能够被建模为加权有向图的实际应用中。
论文目录
相关论文文献
标签：数据挖掘论文; 加权有向图论文; 频繁遍历模式论文; 加权论文; 可扩展性论文; 频繁闭合模式论文; 最大频繁模式论文; 统计理论论文; 噪声数据论文; 强相关模式论文;