To search, Click below search items. |
| All Published Papers Search Service |
|
|
|
Title |
Complete Discovery of Weighted Frequent Subtrees in Tree-Structured Datasets |
|
Author |
Rahman AliMohammadzadeh , Ashkan Zarnani, Masoud Rahgozar, Mostafa H. Chehreghani |
| Citation |
Vol. 6 No. 8 pp. 188-196 |
|
Abstract |
Mining frequent subtree patterns has many useful applications in XML mining, bioinformatics, network routing, etc. Most of the frequent subtree mining algorithms (such as FREQT, TreeMiner and CMTreeMiner) use anti-monotone property in the phase of candidate subtree generation. However, none of these algorithms seems to verify the correctness of this property in all kinds of tree structured data. In this paper, we investigate the correctness of anti-monotone property for the problem of weighted frequent subtree mining and use multiple examples to elaborate on our finding about this issue. It is shown that anti-monotonicity does not generally hold, when using weighed support in tree pattern discovery. Consequently, the tree mining algorithms that are based on this property would miss some of the valid frequent subtree patterns if one considers weighted support. We propose also a novel algorithm named W3-Miner that uses new data structures and techniques for full extraction of frequent subtrees. The experimental results confirm that W3-Miner finds some frequent subtrees that the previously proposed algorithms would not discover when if weighted support is required. |
|
Keywords |
Semi-Structured Data Mining, Anti-Monotone Property, Frequent Subtree Mining |
|
URL |
