ISSN:
1432-1343
Keywords:
Partition
;
Split
;
Dendrogram
;
Dual graph
;
Complexity
;
Polynomial algorithm
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Description / Table of Contents:
Résumé SoientN objets à classifier et une matrice de dissimilarit és entre paires de ces objets. L'écart d'une classe est la plus petite dissimilarité entre un objet de cette classe et un objet en dehors d'elle. L'algorithme du lien simple fournit des partitions enM classes dont le plus petit écart est maximum. On étudie l'écart moyen des classes, ou, ce qui est équivalent, la somme des écarts. On propose un algorithme en Θ(N 2) pour déterminer des partitions enM classes dont la somme des écarts est maximum pourM allant deN − 1 à 2, basé sur le graphe dual du dendrogramme de la méthode du lien simple.
Notes:
Abstract ConsiderN entities to be classified, and a matrix of dissimilarities between pairs of them. The split of a cluster is the smallest dissimilarity between an entity of this cluster and an entity outside it. The single-linkage algorithm provides partitions intoM clusters for which the smallest split is maximum. We study here the average split of the clusters or, equivalently, the sum of splits. A Θ(N 2) algorithm is provided to determine maximum sum-of-splits partitions intoM clusters for allM betweenN − 1 and 2, using the dual graph of the single-linkage dendrogram.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01908598
Permalink
