关键词: 树编辑距离, 层次聚类, 属性相似性, 数据挖掘

Abstract: In order to recognize the false status which has been forged and tempered by suspects,a new method is proposed to compute attribute similarities based on tree edit distance,and its mathematical properties are proved. The paper proposes a new clustering algorithm based on hierarchical encoding method named HCTED（Hierarchical Clustering Algorithm Based on Tree Edit Distance）. This method uses tree edit distance to compute attribute similarities with minimum cost,overcomes the shortage of traditional clustering algorithms and improves the precision of clustering according to the predefined threshold. Experiments demonstrate that the new method is accurate and efficient in identity recognition,discuss the effects of different experimental parameters,and show that HCTED is more accurate and faster than traditional clustering algorithms. The new algorithm has been used in data analysis of transient population for public security successfully.

Key words: tree edit distance, hierarchical clustering, attribute similarity, data mining