Hierarchical Grouping to Optimize an Objective Function

Иерархическое группирование для оптимизации целевой функции
Joe H. Ward
1963-03-01

agglomerative merginghierarchical groupinglarge-scale groupingloss estimationobjective function optimization
A procedure for forming hierarchical groups of mutually exclusive subsets, each of which has members that are maximally similar with respect to specified characteristics, is suggested for use in large-scale (n > 100) studies when a precise optimal solution for a specified number of groups is not practical. Given n sets, this procedure permits their reduction to n − 1 mutually exclusive sets by considering the union of all possible n(n − 1)/2 pairs and selecting a union having a maximal value for the functional relation, or objective function, that reflects the criterion chosen by the investigator. By repeating this process until only one group remains, the complete hierarchical structure and a quantitative estimate of the loss associated with each stage in the grouping can be obtained. A general flowchart helpful in computer programming and a numerical example are included.
1
At each iteration the method considers all n(n−1)/2 pairwise unions and selects the union that maximizes a user-specified objective function reflecting chosen similarity criteria.
2
Introduces a hierarchical grouping procedure that forms mutually exclusive subsets by iteratively merging pairs to reduce n sets to one when exact optimization is impractical for large n (>100).
3
Repeating the pairwise-maximizing merges yields a complete hierarchical structure and provides quantitative estimates of the loss associated with each grouping stage.
4
The paper provides a general flowchart for implementation and a numerical example to illustrate the procedure and assist computer programming.

Procedure for forming hierarchical groups of mutually exclusive subsets (hierarchical grouping algorithm)

Optimization of an objective function via iterative agglomeration of set pairs to form hierarchical grouping, including quantifying loss at each stage

Publication Details
Publication Date
1963-03-01
Journal
Publisher
ISSN
Cited by
21391
Access Type
Author Information
Authors
Joe H. Ward
Explore further
Open the scid.ai AI chat with a ready-made request: it will find papers on a similar topic and help build a literature review.
Find similar papers in the chat →
Make a presentation
100%