基于XML数据的频繁模式挖掘算法*

结合XML文档的特点,采用XML数据模型XOEM和压缩结构树的存储结构,提出了一种高效的XML数据的频繁模式挖掘算法──AFPMX算法,并从理论和实验两方面证明了该算法是可行和有效的。     

XML快速关联规则挖掘算法的研究

本文研究如何快速有效地从XML数据中挖掘频繁模式,提出了从XML数据中挖掘频繁模式的增量式算法FreqtTree.该算法首先将XML文档转化成DOM树,然后从DOM树中挖掘所有频繁模式.FreqtTree算法采用最右扩展技术,对DOM树仅遍历一次,因此具有很高的效率.在此基础上详细描述了基于DOM树的关联规则挖掘算法DFreqtTree.最后将本文提出的算法用Java语言实现,并进行性能分析,结果表明算法是高效可行的.     

PFTM：一种基于投影的频繁子树挖掘算法

频繁子树在Web挖掘、XML文档分析、生物信息处理等领域有着重要的应用。提出了一种新的基于投影的频繁子树挖掘算法(PFTM)，通过对数据库和候选节点集进行投影，并采用递推式候选节点集更新技术来有效地压缩搜索空间。以高效地从森林中挖掘出频繁子树。PFTM不需要产生候选子树。性能对比实验表明，PFTM是有效和可扩展的，而在算法效率上，PFTM要比FREQT平均高出40％左右。     

基于递推式右路径扩展的XML频繁模式树挖掘

在分析现有的频繁模式树挖掘的经典算法FREQT和FreqtTree基础上,提出一种新的基于递推式右路径扩展的XML频繁模式树挖掘算法。该算法采用最右路径扩展的思想,利用递推式的候选节点集更新技术来压缩候选节点集,产生数量较少的候选模式,并且在计算候选模式树的支持数时,采用增量式技术,提高算法效率。从理论上证明该算法的正确性,并对通过具体实验验证算法的高效性。     

基于序列前缀技术的XML频繁路径挖掘算法

XML文档是半结构化数据,对其进行频繁路径挖掘可以分为两步：XML文档序列化和序列挖掘阶段. 现有的序列化方式将XML文档表示为Xpath路径集合,其中有大量的节点冗余;序列挖掘阶段采用的类Apriori算法需要多次扫描数据库并产生大量的候选集,采用的PrefixSpan算法会产生大量的投影数据库,占用较大的内存. 针对以往XML频繁路径挖掘算法存在的不足,本文提出一种高效的挖掘算法——基于序列前缀技术的XML频繁路径挖掘算法（PXFP,Prefix-based XML Frequent Path Mining Algorithm）. PXFP算法以广度优先方式遍历XML文档树并将每个节点表示为“节点：父节点”的形式,这种序列化的方式减少了节点冗余. 在序列挖掘阶段借鉴PrefixSpan 算法中前缀的概念,但不产生投影数据库,仅得到直接后缀（即前缀的子节点）,通过记录频繁子路径的位置信息逐渐扩大频繁模式的长度,位置信息的引入减少了对数据库的扫描. 实验结果表明,PXFP算法取得了比PrefixSpan算法更高的时间和空间效率.     

XML空间频繁变化结构挖掘方法

XML数据在实际使用过程中不断发生改变,针对XML数据动态可变的特点,提出一种根据XML数据变化过程挖掘XML空间频繁变化结构SFCS(Spatial Frequently Changing Structure)的方法,首先提出XML子结构空间度量方法,通过结构空间变化度SSCD、版本空间变化度VSCD和空间变化程度SCD这3个度量值衡量XML子结构的空间变化频繁性并提出SFCS定义.进一步,提出一种用于保存XML空间变化信息和发现SFCS的数据模型SC-DOM,论证了XML编辑操作对子结构空间的影响并据此提出SC-DOM状态动态迁移方式,最后提出根据SC-DOM发现SFCS的算法并讨论算法复杂度.实验结果表明SFCS是频繁变化的结构,使用SC-DOM模型进行SFCS挖掘是有效且可扩展的.     

极小负co-location模式及有效的挖掘算法

空间co-location(并置)模式是指实例在空间中频繁关联的一组空间特征的子集。在空间数据挖掘中,现有算法主要针对的是正模式的挖掘,而空间中还存在着具有强负相关性的模式,如负co-location模式,这类模式的挖掘在一些应用中同样具有重要的意义。现有的负co-location模式挖掘算法的时间复杂度较高,挖掘到的模式数量巨大。针对该问题,探索了负co-location模式的向上包含性质,提出了极小负co-location模式,证明了极小负co-location模式可推导出所有频繁负co-location模式。在负co-location模式挖掘中,计算模式的表实例是制约挖掘效率的根本因素,为此提出了3个剪枝策略有效地提高了算法的效率。在真实和合成数据集上的大量实验,验证了提出方法的正确性和高效性。特别地,大量实验结果表明极小负co-location模式可将频繁负co-location模式数量压缩80%以上。     

极大频繁子树挖掘及其应用

极大频繁子树挖掘在Web挖掘、HTML/XML文档分析、生物医学信息处理等领域有着重要的应用,可用于解决这些领域的自同构问题.本文提出了一种极大频繁子树挖掘算法(MFTM).MFTM基于最右路径扩展技术,在搜索过程中,采用覆盖定理进行裁剪,压缩搜索空间,从而极大地加快了算法的收敛速度.性能实验表明,极大频繁挖掘等算法是有效和可伸缩的.     

一种基于排序的基因表达数据频繁闭合模式挖掘算法

频繁闭合模式是频繁模式的无损压缩,因此采用频繁闭合模式的挖掘来代替频繁模式挖掘,可以适当的压缩计算和存储开销。文中针对已有的面向基因表达数据集频繁闭合模式挖掘算法CARPENTER多次扫描数据集转置表带来巨大开销的缺陷,提出了基于排序的频繁闭合模式挖掘算法SFCP。在真实数据集上的实验结果表明,该算法效率比CARPENTER算法高。     

基于改进FP-树的最大模式挖掘算法

频繁模式挖掘是数据挖掘领域中的一个非常重要的分支,但是由于其内在的计算复杂性,挖掘密集型数据的频繁模式完全集非常困难而且数量往往大得惊人,难以理解和应用。最大频繁模式(最大模式)压缩隐含了所有的频繁模式,存储所占用的空间远远小于完全集,因而最大模式挖掘具有十分重要的意义。该文改进了传统的FP-树结构并提出了一种有效的基于改进FP-树的最大模式挖掘算法IFP-M ax;通过引入后缀子树的概念,算法在挖掘过程中不用生成最大频繁模式候选集,从而大大提高了算法的时间效率和空间可伸缩性。实验表明,IFP-M ax的挖掘速度比M AFIA和GenM ax大约快一个数量级。     

基于事务映射区间求交的高效频繁模式挖掘算法

关联规则挖掘是数据挖掘重要研究课题,大数据处理对关联规则挖掘算法效率提出了更高要求,而关联规则挖掘的最耗时的步骤是频繁模式挖掘。针对当前频繁模式挖掘算法效率不高的问题,结合Apriori算法和FP-growth算法,提出一种基于事务映射区间求交的频繁模式挖掘算法IITM（interval interaction and transaction mapping）,只需扫描数据集两次来生成FP树,然后扫描FP树将每个项的ID映射到区间中,通过区间求交来进行模式增长。该算法解决了Apriori算法需要多次扫描数据集,FP-growth算法需要迭代地生成条件FP树来进行模式增长而带来的效率下降的问题。在真实数据集上的实验显示,在不同的支持度下IITM算法都要要优于Apriori、FP-growth以及PIETM算法。     

一种启发式XML结构重构算法

基于海量XML文档查询时信息关联和服务请求多样性的需求,提出一个重构XML结构的频繁向量选择增量模式树(XFP-tree)算法。该算法以XML键为基础,利用向量矩阵处理方法、投影频繁模式树实现XML结构的分裂、合并、更改与取消等操作,同时讨论XML键向量矩阵频繁项集的划分规则及相应启发式策略与支持度阈值。对比其他关联算法,一系列仿真实验表明所提出算法具有一定的有效性及合理性,是重构XML结构的一种有效尝试。     

在FP-树中挖掘频繁模式而不生成条件FP-树

FP-growth算法是目前已发表的最有效的频繁模式挖掘算法之一．然而，由于在挖掘频繁模式时需要递归地生成大量的条件FP-树，其时空效率仍然不够高．改进了FP-树结构，提出了一种基于被约束子树挖掘频繁项集的有效算法．改进的FP-树是单向的，每个结点只保留指向父结点的指针，这大约节省了三分之一的树空间．通过引入被约束子树(可以用3个很小的数组表示)，算法在挖掘频繁模式时不生成条件FP-树，从而大大提高了频繁模式挖掘的时空效率．实验表明，与FP-growth算法相比，算法的挖掘速度提高了1倍以上，而所需的存储空间减少了一半．此外，随着数据库规模的增大，算法具有很好的可伸缩性．对于稠密数据集，算法也具有良好的性能．     

一种基于模式树的频繁项集快速挖掘算法

模式树是目前频繁项集挖掘最常用的数据结构,使用模式树可以有效地将数据库压缩于内存,并在内存中完成对频繁项集的挖掘。为了进一步提高频繁项集挖掘算法的可扩展性,本文对模式树进行了细致的研究,在此基础上提出了一种挖掘频繁项集的新算法,FP-DFS算法。该算法通过对模式树的各种操作简化了对频繁项集的搜索过程。实验表明,该算法对于频繁项集挖掘具有比较高的效率。     

基于B-list的快速频繁模式挖掘算法

针对现有的频繁模式挖掘算法存在建树复杂、挖掘效率低等问题,提出一种基于构造链表（B-list）的频繁模式挖掘（BLFPM）算法。BLFPM使用一种新的数据结构B-list表示频繁项集,通过连接两个k-1-频繁项集的B-list可以快速得到k-项集的支持度,避免了多次扫描数据库;针对连接两个B-list时间复杂度高的问题,给出了一种线性时间复杂度的连接方法,提高了BLFPM的时间效率;同时,BLFPM采用集合枚举树代表搜索空间,并使用子集非频繁剪枝策略,减小了频繁模式挖掘的搜索空间,提高了算法的执行速度。实验结果表明,与NSFI算法和prepost算法相比,BLFPM的时间效率提高约12%到29%,空间效率提高约10%到24%,对稀疏数据库或稠密数据库进行频繁模式挖掘均可以得到良好的效果。     

改进的并行关联规则增量挖掘算法

针对大数据环境下基于Can树(canonical order tree)的增量关联规则算法存在树结构空间占用过大、频繁模式挖掘效率不佳以及MapReduce集群并行化性能不足等问题,提出了一种基于粗糙集和归并剪枝方法改进的并行关联规则增量挖掘算法MR-PARIRM(MapReduce-based parallel association rules incremental mining algo-rithm using rough set and merge pruning).首先,设计了一种基于粗糙集的相似项合并策略RS-SIM(rough set based similar item merge)对数据集的相似项进行合并处理,并根据合并后的数据进行Can树构造,从而降低树结构的空间占用;其次,提出了一种归并剪枝策略MPS(merge pruning strategy)对树结构中的传播路径进行修剪合并,通过压缩频繁模式搜索空间来加快频繁项挖掘;最后,通过动态调度策略DSS(dynamic scheduling strategy)对异构式MapReduce集群中的计算任务进行动态调度,实现了负载均衡,有效提升了集群的并行化运算能力.最终的实验仿真结果表明,MR-PARIRM在大数据环境下具有相对较好的性能表现,适用于对大规模数据进行并行化处理.     

基于改进FP-Tree的最大频繁项集高效挖掘算法

基于FP-T ree的FP-M ax算法在挖掘最大频繁集时需多次递归建立条件模式树耗费大量存储空间,这大大降低了算法的挖掘效率。提出了一种基于改进FP-T ree的最大频繁集快速挖掘算法-FP-EM ax算法。该算法无需建立条件模式库大大减少了存储空间开销,采用预剪枝策略减少条件模式树的构造次数及子集检测次数,从而算法的挖掘效率大大提高。最后通过实验证明FP-EM ax算法在支持度较小的情况下较之于FP-M ax及同类算法具有更好的性能。     

Bottom-up discovery of frequent rooted unordered subtrees

In the past decade, XML has emerged as the standard language for information exchanging over the Internet. Due to its tree-structure paradigm, XML is superior for its capability of storing, querying, and manipulating complex data. Therefore, discovering frequent tree patterns over tree-structured data has become an interesting topic for XML data management. In this paper, we propose a tree mining algorithm, named BUXMiner, for finding a special class of frequent trees, called rooted unordered trees, from a tree-structured database. BUXMiner employs an efficient bottom-up approach to enumerate all candidate trees over a compact global tree guide and computes the frequent trees based on the tree guide. In addition to BUXMiner, we also propose a mining approach called BUMXMiner to discover the maximal frequent rooted unordered trees. We compare BUXMiner with previous tree-structure mining algorithms, namely XQPMinerTID and FastXMiner, which were also proposed to discover rooted unordered trees. The experimental results show that our algorithm outperforms XQPMinerTID and FastXMiner in terms of efficiency. The performance results from real-world applications also indicate the usefulness of our proposed tree mining algorithms in a variety of web applications, such as analysis of web page access patterns and mining frequent XML query patterns for caching.     

Efficient Mining of Frequent Closed XML Query Pattern

Previous research works have presented convincing arguments that a frequent pattern mining algorithm should not mine all frequent but only the closed ones because the latter leads to not only more compact yet complete result set but also better efficiency. Upon discovery of frequent closed XML query patterns, indexing and caching can be effectively adopted for query performance enhancement. Most of the previous algorithms for finding frequent patterns basically introduced a straightforward generate-and-test strategy. In this paper, we present SOLARIA＊, an efficient algorithm for mining frequent closed XML query patterns without candidate maintenance and costly tree-containment checking. Efficient algorithm of sequence mining is involved in discovering frequent tree-structured patterns, which aims at replacing expensive containment testing with cheap parent-child checking in sequences. SOLARIA＊ deeply prunes unrelated search space for frequent pattern enumeration by parent-child relationship constraint. By a thorough experimental study on various real-life data, we demonstrate the efficiency and scalability of SOLARIA＊ over the previous known alternative. SOLARIA＊ is also linearly scalable in terms of XML queries＇ size.     

基于前缀树的高效频繁项集挖掘算法

针对频繁项集挖掘时间与空间效率低的问题,提出一种基于前缀树的高效频繁项集挖掘算法,通过对事务集进行预处理,创建索引表并分配索引编号,保证前缀树中事务顺序的一致性,根据索引编号等信息创建紧凑的前缀树,采用自底向上的挖掘与投影的方式挖掘出频繁项集。实验结果表明,该算法挖掘效率高、占用空间少。