Mixed-integer models for complete-linkage clustering
提出一组线性不等式来描述完全链接聚类产生的所有树状图，允许加入目标函数从中选出最优树状图，并扩展到单链接聚类，通过计算实验展示了五种目标函数的效果。
Abstract Dendrograms are graphical representations of hierarchical clustering. Different definitions of the distance between two clusters in hierarchical clustering lead to different dendrograms. In this paper we focus on the dendrograms obtained when this distance is assumed to be the maximum of the distances between the elements of one cluster and the elements of the other cluster, known as complete-linkage dendrograms. For initial data where some elements are at the same distance as others, the number of different complete linkage dendrograms, which corresponds to the number of different ways to break ties for equal distances, can be large. We propose a system of linear inequalities whose set of solutions is the entire set of complete linkage dendrograms. Such a system of inequalities allows the inclusion of an objective function to select the best dendrogram among all these dendrograms according to some criteria, which may not be possible with classical dendrogram computation algorithms. We also adapt the system of inequalities to single-linkage dendrograms, where the distance between two clusters is the minimum distance between an element of one cluster and an element of the other cluster. The benefits of describing complete-linkage dendrograms through a system of inequalities are illustrated in a computational study in which five different objective functions are proposed.