一种基于DOM树的XML数据频繁模式挖掘算法

由于XM L数据具有半结构化特性,使得面向XM L数据的数据挖掘不同于面向关系数据库的数据挖掘,它具有更复杂的层次结构。研究基于DOM树的XM L数据频繁模式挖掘算法,提出面向XM L数据的频繁模式增量式挖掘算法F reqtT ree。该算法首先将XM L数据转化成DOM树,然后从DOM树挖掘所有频繁模式。F reqtT ree算法采用最右扩展技术,只在树的最右分支上增加新结点生成新树。同时充分利用已生成的频繁模式信息,使得产生的候选模式数量较少。F reqtT ree算法利用频繁k-1模式的支持数计算候选k模式的支持数,该算法只对DOM树遍历一次,具有较高的效率。采用多组数据对此算法的性能进行检验,并与其他算法作对比实验,实验结果表明该算法高效可行。

DOM-Based Algorithm of Mining Frequent Patterns from XML Data

Data mining in XML data has a more complicated hierarchical data structure because of the semi-structured data feature,and it quite differs from the rational database-based mining.This paper presents an efficient mining algorithm FreqtTree for discovering all frequent patterns from XML data.Firstly,the algorithm transfers XML data into a DOM tree,and then adopts an incremental method to mine all frequent patterns from the DOM tree.The key of the algorithm FreqtTree is the notion of the rightmost expansion to increase a tree by attaching new nodes only on the rightmost branch.The number of candidate patterns is small because of utilizing the information of the frequent patterns discovered in the pervious iteration.In addition,the algorithm FreqtTree sufficiently uses the support of frequent(k-1) patterns to compute the support of candidate k pattern.Combining the above techniques,the algorithm traverses the DOM tree only once.Finally,a group of XML data is applied to test the performance of the algorithm and the experimental result is compared with other algorithms.Experimental results show that the algorithm is effective.