Space-contracting, space-dilating, and positive admissible clustering algorithms

摘要

G. N. Lance and W. T. Williams (Comput. J. 9, 373–380 (1967)) proposed an infinite parameterized family of agglomerative clustering algorithms. This family is interesting because it contains most common agglomerative algorithms. This paper provides necessary and sufficient conditions for Lance and Williams' algorithms to be admissible in each of three senses: space-contracting, space-dilating, and positive. The space-contracting and space-dilating properties of agglomerative algorithms were introduced in Lance and Williams, while positive admissibility is new.