EFFICIENT ALGORITHMS FOR AGGLOMERATIVE HIERARCHICAL-CLUSTERING METHODS
EFFICIENT ALGORITHMS FOR AGGLOMERATIVE HIERARCHICAL-CLUSTERING METHODS
复制标题
DOI：
10.1007/bf01890115
复制
发表时间：
1984-01-01
影响因子：
2
通讯作者：
EDELSBRUNNER, H
中科院分区：
文献类型：
--
作者：
DAY, WHE;EDELSBRUNNER, H
当每个对象都具有两两不相似矩阵的特征时，它们可以通过一系列顺序、凝聚、分层、非重叠（SAHN）聚类方法中的任何一种聚类。这些SAHN聚类方法是由一个范例算法定义的，在最坏的情况下，通常需要0（n3）时间来聚类对象。一种改进的算法（Anderberg 1973），虽然仍然需要0（n3）个最坏情况时间，但可以合理地期望表现出0（n2）个预期行为。相比之下，我们描述了在最坏情况下需要0（n2logn）时间的SAHN聚类算法。当SAHN聚类方法表现出合理的空间畸变特性时，进一步的改进是可能的。我们采用了一种基于最近邻链高效构造的SAHN聚类算法，得到了在最坏情况下需要0（n2）时间和空间的合理通用的SAHN聚类算法。当每个对象都用实数元组来表征时，它们可以用任何一类质心SAHN聚类方法聚类。这些方法基于一种几何模型，其中聚类由墨水维真实空间的点表示，被聚集的点由单个（质心）点代替。针对该模型，我们解决了一类涉及点对称凸对象的特殊包装问题，并利用它设计了一种高效的质心聚类算法。具体来说，我们描述了一种质心SAHN聚类算法，在最坏的情况下，对于固定地的一系列不相似度量，包括曼哈顿，欧几里得，切比切夫和所有其他闵可夫斯基度量，该算法需要0（n2）时间。
Whenevernobjects are characterized by a matrix of pairwise dissimilarities, they may be clustered by any of a number of sequential, agglomerative, hierarchical, nonoverlapping (SAHN) clustering methods. These SAHN clustering methods are defined by a paradigmatic algorithm that usually requires 0(n3) time, in the worst case, to cluster the objects. An improved algorithm (Anderberg 1973), while still requiring 0(n3) worst-case time, can reasonably be expected to exhibit 0(n2) expected behavior. By contrast, we describe a SAHN clustering algorithm that requires 0(n2logn) time in the worst case. When SAHN clustering methods exhibit reasonable space distortion properties, further improvements are possible. We adapt a SAHN clustering algorithm, based on the efficient construction of nearest neighbor chains, to obtain a reasonably general SAHN clustering algorithm that requires in the worst case 0(n2) time and space.Whenevernobjects are characterized byk-tuples of real numbers, they may be clustered by any of a family of centroid SAHN clustering methods. These methods are based on a geometric model in which clusters are represented by points ink-dimensional real space and points being agglomerated are replaced by a single (centroid) point. For this model, we have solved a class of special packing problems involving point-symmetric convex objects and have exploited it to design an efficient centroid clustering algorithm. Specifically, we describe a centroid SAHN clustering algorithm that requires 0(n2) time, in the worst case, for fixedkand for a family of dissimilarity measures including the Manhattan, Euclidean, Chebychev and all other Minkowski metrics.