📊 statistics

Hierarchical Aggregation Clustering Algorithms Derived from the Bi-partial Objective Function

This paper establishes a general theoretical framework connecting hierarchical aggregation clustering algorithms to the bi-partial objective function, thereby providing these methods with a deeper optimization-based justification, quality evaluation metrics, and explicit stopping criteria.

Original authors: Jan W. Owsiński

Published 2026-02-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jan W. Owsiński

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a teacher trying to organize a chaotic classroom of 30 students into study groups. You want the students in the same group to be friends (similar) and the students in different groups to be strangers (dissimilar).

This is the core problem of clustering in data science. For decades, scientists have had many ways to do this, but they often felt like they were guessing. They would group the kids, then look at the result and say, "Hmm, that looks okay," or "Maybe I should cut the groups here." They lacked a clear rulebook or a "scorecard" to prove their grouping was the best possible one.

This paper, written by Jan W. Owsiński, introduces a new way to think about this problem. It proposes a "Master Scorecard" (called the Bi-Partial Objective Function) that balances two competing desires, and then shows how to build a step-by-step game plan (an algorithm) to find the best groups based on that scorecard.

Here is the breakdown using simple analogies:

1. The Two Sides of the Coin (The Bi-Partial Function)

The author suggests that every time we try to group things, we are balancing two opposing forces:

The "Huddle" Factor (Internal Similarity): We want people in the same group to be close together. Think of this as the warmth of a campfire; everyone huddles close to stay warm.
The "Distance" Factor (Inter-Group Separation): We want different groups to be far apart. Think of this as different camps in a large field; you don't want Camp A and Camp B to be so close that they merge into one big, confused mess.

The "Bi-Partial" function is like a scale. On one side, you put the "Huddle" score; on the other, the "Distance" score. The goal is to find the perfect balance where the groups are tight-knit but clearly separated from each other.

2. The "Merge" Game (Hierarchical Aggregation)

Most traditional clustering algorithms work like a game of musical chairs, but in reverse.

Start: Imagine every student is standing alone in the middle of the gym.
The Move: The teacher looks around and says, "Who are the two people closest to each other? You two, join hands!"
The Repeat: Now you have 29 groups (28 singles, 1 pair). The teacher looks again, finds the next closest pair (or a single person and the pair), and says, "Join them!"
The Tree: If you draw a line every time two groups merge, you get a family tree called a dendrogram. It looks like a tree with branches merging into bigger branches until everyone is in one giant group at the top.

The Problem: Traditional methods stop at a random point. "Okay, let's cut the tree here." But why there? The paper asks: "What if we could calculate exactly when to stop to get the best score?"

3. The Magic Formula (Deriving the Rules)

The author's big breakthrough is showing that these "merge" games aren't just random rules; they can be mathematically derived from that "Master Scorecard."

Imagine you are slowly turning a dial on a machine.

At Dial 0, the machine only cares about keeping everyone separate. So, everyone stays alone.
As you slowly turn the dial toward Dial 1, the machine starts caring more about huddling together.
The author figured out a formula that tells you exactly at what setting of the dial two specific people should merge.

This is like having a GPS for your grouping. Instead of guessing, the math says: "At this exact moment, merging these two groups improves the overall score the most."

4. Why This Matters (The "Aha!" Moment)

Before this paper, if you used a popular algorithm (like "Single Linkage" or "Ward's Method"), you were essentially following a recipe without knowing the ingredients. You didn't know if you were optimizing for "tightest groups" or "widest gaps."

This paper says: "Here is the recipe, and here is the exact math that proves why this recipe works."

It justifies the method: It proves that these common algorithms are actually trying to solve a specific, well-defined math problem.
It gives a stopping rule: It tells you exactly when to stop merging. You don't have to guess. You stop when the "score" starts getting worse or when the math says the groups are as good as they can get.
It improves quality: It allows us to evaluate if a grouping is actually good, rather than just accepting whatever the computer spits out.

5. Real-World Examples

The paper shows how this works for different scenarios:

The "Facility Location" Analogy: Imagine opening new coffee shops. You want them close to customers (huddle) but not so close that they compete with each other (distance). The math helps decide where to open the next shop.
The "K-Means" Upgrade: K-Means is a very famous, fast way to group data. Usually, you have to guess how many groups you want (e.g., "Let's try 5 groups"). This paper provides a way to let the math tell you the best number of groups automatically, without guessing.

Summary

Think of this paper as the instruction manual for the "Grouping Game."
Previously, we had a bunch of players who knew how to move the pieces (merge the clusters) but didn't know the winning strategy. This paper writes down the winning strategy (the Bi-Partial Objective Function) and shows that the moves the players were making were actually the right steps to win, provided they know exactly when to stop playing.

It turns clustering from a "black box" magic trick into a transparent, logical process with a clear goal and a clear finish line.

1. Problem Statement

The paper addresses a fundamental gap in cluster analysis: the disconnect between hierarchical aggregation algorithms (procedural methods like Single Linkage, Ward's, etc.) and optimization objectives.

The Issue: Traditional hierarchical algorithms are defined procedurally (e.g., "merge the two closest clusters") rather than as solutions to a specific optimization problem. While they are intuitive, they lack a rigorous mathematical justification regarding what specific objective function they are optimizing.
The Limitation: Existing methods often require "external" criteria (post-hoc indices like silhouette scores or AIC) to determine the optimal number of clusters or to evaluate the quality of a partition. These external criteria are not derived from the algorithm's own logic.
The Goal: To establish a direct, explicit link between a general class of objective functions (specifically "bi-partial" functions) and the derivation of hierarchical aggregation algorithms, thereby providing a theoretical basis for the algorithms, a criterion for stopping the merging process, and a method for evaluating partition quality.

2. Methodology

The author proposes a framework based on the Bi-partial Objective Function, which treats clustering as an optimization problem balancing two competing goals:

Internal Cohesion ( $Q_S$ ): Maximizing similarity (or minimizing distance) between objects within the same cluster.
External Separation ( $Q_D$ ): Maximizing distance (or minimizing similarity) between objects in different clusters.

The Core Framework

The methodology involves parameterizing the objective function $Q(P, r)$ with a weight parameter $r \in [0, 1]$ :
$\max_P Q(P, r) = r Q_S(P) + (1-r) Q_D(P)$
(Note: The paper also discusses a minimization dual form).

$P$ : Represents a partition of the data set.
$r$ : A weight parameter.
- At $r=0$ , the function prioritizes separation ( $Q_D$ ), resulting in a partition where every object is its own cluster ( $P=I$ ).
- At $r=1$ , the function prioritizes cohesion ( $Q_S$ ), resulting in a single cluster containing all objects.
- The "true" clustering solution is sought at $r = 0.5$ (or a specific optimal $r$ ).

Derivation of Algorithms

The paper demonstrates how to derive a progressive merger algorithm from this function:

Start: Begin with $r=0$ (all objects separate).
Iterative Step: Increase $r$ gradually. Identify the specific value $r_t$ at which the current partition $P_{t-1}$ is no longer optimal and a new partition $P_t$ (formed by merging two clusters) becomes superior.
Merger Rule: The algorithm selects the pair of clusters to merge that minimizes the required $r$ to switch the optimal partition. This leads to a greedy selection rule analogous to classical hierarchical methods.
Stopping Criterion: The process stops when the calculated threshold $r_t$ exceeds the target weight (e.g., $r_t > 0.5$ ), indicating that further mergers would degrade the overall objective function.

3. Key Contributions

A. Theoretical Unification

The paper provides the first explicit, general connection between the bi-partial objective function and hierarchical aggregation algorithms. It proves that classical algorithms (like Average Linkage) can be mathematically derived as sub-optimization procedures of specific forms of the bi-partial function.

B. Derivation of Merger Rules

The author derives a general formula for the merger threshold $r_t$ :
$r_t = \frac{Q_D(P_{t-1}) - Q_D(P_t)}{Q_D(P_{t-1}) - Q_D(P_t) + Q_S(P_t) - Q_S(P_{t-1})}$
This formula shows that the decision to merge is based on the trade-off between the gain in internal similarity and the loss in inter-cluster separation.

C. Specific Algorithmic Examples

The paper illustrates how different definitions of $Q_S$ and $Q_D$ yield different known algorithms:

Average Linkage: Derived when $Q_S$ and $Q_D$ are defined as sums of similarities and distances (matching the Ducimetière connection).
Facility Location: Modeled by adding a constant cost per cluster to the objective function.
Bi-partial k-means: A novel adaptation of k-means where the objective function includes both intra-cluster variance ( $Q_D$ ) and a measure of inter-cluster separation ( $Q_S$ ). This allows k-means to determine the optimal number of clusters internally without external criteria.

D. Stopping Criterion and Quality Evaluation

Unlike traditional hierarchical clustering, which produces a full dendrogram requiring an arbitrary "cut," this approach provides a natural stopping point. The algorithm stops when the marginal benefit of merging no longer outweighs the cost relative to the weight parameter $r$ . This offers an intrinsic measure of partition quality.

4. Results and Illustrations

Theoretical Validation: The paper mathematically demonstrates that the greedy merger strategy (minimizing $r_t$ ) leads to a sub-optimal solution of the global bi-partial objective function.
k-means Case Study:
- The author applied the bi-partial approach to a synthetic dataset ( $n=60$ ).
- Result: The objective function $Q_{DS}(p)$ (sum of intra-cluster distance and inter-cluster similarity) showed a clear global minimum at $p=4$ clusters, correctly identifying the underlying structure of the data.
- Comparison: Standard k-means requires external criteria (like Calinski-Harabasz) to find $p=4$ . The bi-partial method found it directly through the optimization of the combined function.
- Nested Partitions: The method successfully identified "nested" quasi-optimal partitions, revealing hierarchical structures within the data that standard methods might miss.
Generalizability: The framework was shown to be flexible enough to accommodate various distance metrics (Manhattan, Euclidean) and similarity transformations.

5. Significance and Implications

Justification of Heuristics: It transforms hierarchical clustering from a set of heuristic rules into a rigorous optimization framework.
Elimination of External Criteria: It reduces reliance on post-hoc statistical indices to determine the number of clusters, as the objective function itself dictates the optimal partition.
Algorithm Design: It provides a blueprint for designing new clustering algorithms tailored to specific data characteristics by simply defining appropriate $Q_S$ and $Q_D$ components.
Computational Trade-off: The author acknowledges that while the approach is theoretically sound, the computational cost (calculating full distance matrices) remains high for large datasets. Therefore, the paper suggests using these bi-partial rules in hybrid approaches (e.g., using k-means for initial coarse clustering, then applying bi-partial hierarchical merging for refinement).

Conclusion

Jan W. Owsiński's paper successfully bridges the gap between the procedural nature of hierarchical clustering and the theoretical rigor of optimization. By deriving aggregation algorithms from a general bi-partial objective function, the paper offers a unified framework that justifies existing algorithms, enables the creation of new ones, and provides intrinsic mechanisms for evaluating cluster quality and determining the optimal number of clusters.