A Tree-to-Tree Distance and Its Application to Cluster Analysis
A Tree-to-Tree Distance and Its Application to Cluster Analysis
复制标题
树间距离及其在聚类分析中的应用
DOI：
10.1109/tpami.1979.6786615
复制
发表时间：
1979
影响因子：
23.6
通讯作者：
Shin
中科院分区：
文献类型：
--
作者：
Shin
提出了两棵树之间的距离度量。使用语言转换的想法，可以通过一系列转换来从另一棵树中得出一棵树。两棵树之间的距离是转化的最小成本序列。基于此定义，提出了一种生成任何两棵树距离的算法。讨论了由树结构代表的模式的聚类分析。使用树对树的距离，模式之间的相似性是根据其树表示之间的距离来衡量的。提出了有关字符模式聚类的说明性示例。
A distance measure between two trees is proposed. Using the idea of language transformation, a tree can be derived from another by a series of transformations. The distance between the two trees is the minimum-cost sequence of transformations. Based on this definition, an algorithm that generates the distance for any two trees is presented. Cluster analysis for patterns represented by tree structures is discussed. Using a tree-to-tree distance, the similarity between patterns is measured in terms of distance between their tree representations. An illustrative example on clustering of character patterns is presented.