【作者】 马海兵；

【导师】 胡运发；

【作者基本信息】 复旦大学 ， 计算机软件与理论， 2005， 博士

【摘要】 随着计算机与信息技术的普及及大容量存储技术的发展,人们在日常事务处理和科学研究中积累了大量宝贵的数据。如何从中提取或“挖掘”用户所需要的信息,是当前信息科学和技术领域面临的一大挑战。频繁模式挖掘是数据挖掘领域的一个基本问题,研究内容一般包括事务、序列、树和图。其方法被广泛应用于许多其它数据挖掘任务中,如相关性分析,周期分析,最大模式,闭合模式,查询,分类,索引等等。由于问题本身的基础性和内在复杂性,频繁模式挖掘方法成为许多研究者关注的课题。 本文对频繁模式挖掘相关技术进行了研究。重点研究了以下几个问题:将互关联后继树模型引入频繁模式挖掘方法;利用静态IS树高效挖掘频繁项集和频繁闭合项集;利用模式增长方法在有序树构成的森林中挖掘嵌入式频繁子树;在无序树构成的森林中挖掘直接频繁子树;及相关的实现技术等。本文研究内容和创新工作主要包括以下五个方面: 1)基于IS~+-树模型的频繁模式挖掘 互关联后继树模型是一种新型的全文存储索引模型。这种模型充分利用了字符序列的有序性和冗余性,适用于海量的全文存储和索引。互关联后继树模型是一种通用的模型。本文扩展了互关联后继树模型的应用领域,首次提出一种基于间接互关联后继树模型(IS~+-树)的频繁模式挖掘算法。算法特点是:挖掘任务只局部关联于一棵根树;动态更新性好,仅做增量变化:算法简单实用。与传统方法相比,该算法具有较好的挖掘效率。 2)基于静态IS-树的频繁模式挖掘 间接互关联后继树在强调了通用性的同时损失了效率。本文进一步提出一种基于静态IS-树专用模型的频繁项集挖掘算法IS-mine。IS—mine直接构造频繁项集,不进行候选集产生与测试操作;算法采用深度优先,模式增长的策略,挖掘任务只在一棵静态的IS-树上进行,避免代价较高的动态树的构建;针对不同特征的数据集,算法采用不同的过滤技术缩小搜索空间。实验与理论分析表明,对于稠密和稀疏数据两类数据集,算法都具有较好的时空效率。 3)高效频繁闭合模式 频繁闭合模式提供了完全频繁模式的所有信息,但数量却可以少几个数量级。本文提出一种基于静态IS-树的频繁闭合项集有效算法IS-Close。算法采用静态投影,模式增长的方法;用多种策略,尽量在算法运行的早期利用闭合项集的各种更多还原

【Abstract】 With the popularity of computer and information technology, and with the great development of storage technique with high capacity, a great amount of data is accumulated in daily work and in scientific research. How to extract or "mine" useful information from these data is a great challenge for today’s research workers in information science. Frequent pattern mining is a basic problem of data mining, including mining transactions, sequences, trees and graphs. The algorithm for it has been prevalently used in many other data mining task, such as association analysis, period’s analysis, maximal and closed patterns, query, classification and index technology etc. Since it lays groundwork for other problem and its intrinsic complexity, the algorithm for frequent pattern miming has become the focus of many research workers.Some relevant techniques about frequent pattern mining are addressed in the thesis, which covers the intruduction of Inter-Relevant Successive Trees into the algorithm for frequent pattern mining, mining frequent itemsets and frequent closed itemsets by using static IS-tree, mining embedded frequent trees in a forest of ordered trees by pattern growth method, mining induced frequent trees in a forest of unordered trees, and therelevant implementation technique. Major contributions of this thesis include:1) Frequent Pattern Mining Based on IS+-TreeIS-tree is a novel mathematical model presented recently, which has been successfully applied to full-text index and storage in text database. In this thesis, its application is extended to data mining and an algorithm is presented for mining frequent patterns based on IS+-tree. The algorithm scans the transaction database only once. The mining process is only associated with one root tree. And, IS+-tree can be dynamically updated by increments. Performance comparison study shows that the algorithm isefficient.2) Mining Frequent Patterns Based on Static IS-treeIS+-tree lay emphasis on its generalization, with the loss of efficiency. Thus, a specific static IS-tree is proposed to efficiently mining frequent patterns. The algorithm builds frequent patterns directly, instead of using high-cost candidate sets generation-and-test method used by Apriori. It generates frequent patterns by depth first and pattern growth approach, and works on a static IS-tree, rather than the costly dynamic trees adopted by FP-growth. In order to reduce search space, it uses different更多还原