GRAPH-THEORETICAL METHODS FOR DETECTING AND DESCRIBING GESTALT CLUSTERS
GRAPH-THEORETICAL METHODS FOR DETECTING AND DESCRIBING GESTALT CLUSTERS
复制标题
DOI：
10.1109/t-c.1971.223083
复制
发表时间：
1971-01-01
影响因子：
3.7
通讯作者：
ZAHN, CT
中科院分区：
文献类型：
--
作者：
ZAHN, CT
基于最小生成树的一族图论算法能够检测任意点集中的多种簇结构；在某些情况下，通过方法的扩展可以描述检测到的簇。这些聚类算法的开发基于二维空间的示例，因为我们想要复制人类对格式塔或点分组的感知。另一方面，所考虑的所有方法都适用于更高维空间，甚至适用于一般度量空间。这些方法的优点包括确定性、易于解释结果簇、符合感知组织的格式塔原则以及点间距离单调变换下结果的不变性。简要讨论了聚类检测在分类学中的应用以及模式识别中良好特征空间的选择。通过文字和图形说明了几个平面簇检测问题的详细分析。著名的Fisher虹膜数据在四维空间中也可以用这些方法进行分析。实现最小生成树方法的PL/1程序已经完全调试完毕。
A family of graph-theoretical algorithms based on the minimal spanning tree are capable of detecting several kinds of cluster structure in arbitrary point sets; description of the detected clusters is possible in some cases by extensions of the method. Development of these clustering algorithms was based on examples from two-dimensional space because we wanted to copy the human perception of gestalts or point groupings. On the other hand, all the methods considered apply to higher dimensional spaces and even to general metric spaces. Advantages of these methods include determinacy, easy interpretation of the resulting clusters, conformity to gestalt principles of perceptual organization, and invariance of results under monotone transformations of interpoint distance. Brief discussion is made of the application of cluster detection to taxonomy and the selection of good feature spaces for pattern recognition. Detailed analyses of several planar cluster detection problems are illustrated by text and figures. The well-known Fisher iris data, in four-dimensional space, have been analyzed by these methods also. PL/1 programs to implement the minimal spanning tree methods have been fully debugged.