• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

J4 ›› 2013, Vol. 35 ›› Issue (7): 156-163.

• 论文 • 上一篇    下一篇

一种新的不确定树模式聚类算法

颜一鸣,郭鑫   

  1. (吉首大学软件服务外包学院,湖南 张家界 427000)
  • 收稿日期:2012-08-10 修回日期:2012-11-02 出版日期:2013-07-25 发布日期:2013-07-25
  • 基金资助:

    湖南省工业支撑计划项目(2012GK2006);湖南省教育厅科学研究资助项目(12C0291);吉首大学校级科研资助项目(11JD051)

A novel clustering algorithm for uncertain tree          

YAN Yiming,GUO Xin   

  1. (School of Software Service Outsourcing,Jishou University,Zhangjiajie 427000,China)
  • Received:2012-08-10 Revised:2012-11-02 Online:2013-07-25 Published:2013-07-25

摘要:

不确定树模式聚类是数据挖掘领域中的一个重要问题,提出了一种新的不确定树模式聚类算法,有效地解决了因数据的不确定性而导致的无法聚类的问题。为了更加准确地度量树模式之间的相似性,提出了一种语义相似度计算方法与结构相似度计算方法。设计了一个动态聚类过程,自适应获取聚类阈值,较大程度上减少了人为干扰导致聚类结果不准确的影响,使得具有相似结构的子树聚集在同一个相似分组中,不同分组之间的子树相似度达到最小化。通过模拟数据和真实环境两部分实验表明,算法有效可行,聚类结果较准确且具有较好的运行效率。

关键词: 数据挖掘, 有序树, 频繁子树, 相似度, 不确定树, 聚类

Abstract:

Uncertain tree clustering is an important problem in data mining domain. In this paper, a new uncertain tree clustering algorithm is proposed. The algorithm effectively resolves the clustering problems for uncertain data. In order to improve accurate measurement on the similarities among trees, the method of semantic similarity and structural similarity are presented. A dynamic clustering process is designed in which selfadaptive threshold be applied so as to greatly reduce the jamming impact on the result accuracy. This process can cluster subtrees of similar structure within similar groups , minimizing the similarity of subtree groups. Both simulation and real experiments show that the algorithm is effective and efficient and the clustering result is accurate.

Key words: data mining;ordered tree;frequent subtree;similarity;uncertain tree;clustering