Sequential clustering with radius and split criteria |
| |
Authors: | Nenad Mladenovic Pierre Hansen Jack Brimberg |
| |
Institution: | 1.Brunel University,London,UK;2.GERAD,HEC Montreal,Montreal,Canada;3.Royal Military College,Kingston,Canada |
| |
Abstract: | Sequential clustering aims at determining homogeneous and/or well-separated clusters within a given set of entities, one at a time, until no more such clusters can be found. We consider a bi-criterion sequential clustering problem in which the radius of a cluster (or maximum dissimilarity between an entity chosen as center and any other entity of the cluster) is chosen as a homogeneity criterion and the split of a cluster (or minimum dissimilarity between an entity in the cluster and one outside of it) is chosen as a separation criterion. An O(N 3) algorithm is proposed for determining radii and splits of all efficient clusters, which leads to an O(N 4) algorithm for bi-criterion sequential clustering with radius and split as criteria. This algorithm is illustrated on the well known Ruspini data set. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|