Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (15): 160-164.

• 数据库、信号与信息处理 • Previous Articles     Next Articles

Efficient uncertain tree mining algorithm

YAN Yiming1,2,GUO Xin2,LI Renfa1   

  1. 1.Department of Computer and Communication,Hunan University,Changsha 410082,China
    2.Department of Information Management and Engineering,Jishou University,Zhangjiajie,Hunan 427000,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-05-21 Published:2011-05-21

一种非确定树模式挖掘算法

颜一鸣1,2,郭 鑫2,李仁发1   

  1. 1.湖南大学 计算机与通信学院,长沙 410082
    2.吉首大学 信息管理与工程学院,湖南 张家界 427000

Abstract: Uncertain tree mining has become an important research subject and has been caused concerns to more and more scholars.In this paper,an uncertain tree mining algorithm is proposed.Uncertain tree mining is an algorithm which can effectively deal with uncertain problems in practical application,the main idea of the algorithm is as follows:The algorithm proposes conceptions of uncertain tree inclusive set,uncertain tree probability and uncertain tree expectation support etc.It raises uncertain tree expectation support as tree support,and gives the calculation method of uncertain tree support.The algorithm utilizes the characteristics of hash table to reduce tree isomorphism hours when calculating expectation support.It brings forward the level search space for uncertain tree mining,which makes uncertain tree mining fast and accurate.The final adoption of a large number of experiments shows that uncertain tree mining proposed in this article is effective and feasible and has significant operating efficiency.

Key words: data mining, tree mining, frequent subtree, uncertain tree, order tree

摘要: 非确定树模式挖掘已经成为一个重要的研究课题,提出一种非确定树模式挖掘算法,有效地解决了在实际应用中树的非确定性问题。其基本思想为:提出非确定树蕴含集、确定树概率和非确定期望支持度等概念,提出将非确定树的期望支持度作为树的支持度,提出非确定树支持度计算方法,利用哈希表能快速匹配的特性降低求解期望支持度过程中树同构判定的时间复杂度,提出非确定树挖掘层次搜索空间,使得非确定树挖掘快速而精确。实验结果表明,提出的非确定树挖掘算法有效可行且具有显著的运行效率。

关键词: 数据挖掘, 树挖掘, 频繁子树, 非确定树, 有序树