Divisive Clustering

Divisive clustering, also called top-down clustering, is a hierarchical clustering method that begins with all data points in a single cluster and recursively splits that cluster into smaller subclusters. The process continues until each observation occupies its own cluster, or until a predefined stopping criterion is satisfied. This approach contrasts with agglomerative clustering (bottom-up clustering), which starts with individual data points and merges them iteratively. Divisive clustering is a form of unsupervised learning: it discovers structure in unlabeled data without predefined categories.

The "splinter group" principle that underlies divisive analysis was introduced in a 1964 Nature paper, "Dissimilarity Analysis: A New Technique of Hierarchical Sub-Division," by Macnaughton-Smith, Williams, Dale, and Mockett ^[14]. Divisive methods are sometimes preferred when analysts are primarily interested in the broad, high-level structure of a dataset because the most meaningful partitions are produced during the earliest splitting steps. The best-known divisive algorithm is DIANA (DIvisive ANAlysis), introduced by Leonard Kaufman and Peter J. Rousseeuw in 1990 ^[1]. Other popular divisive strategies include bisecting k-means ^[2] and Principal Direction Divisive Partitioning (PDDP) ^[3].

Explain like I'm 5 (ELI5)

Imagine you have a big pile of colored blocks. Divisive clustering is like starting with the whole pile and splitting it into two groups: maybe all the warm-colored blocks (red, orange, yellow) in one pile and all the cool-colored blocks (blue, green, purple) in another. Then you look at each pile and split it again. You keep splitting until every single block has its own spot. It is the opposite of putting blocks together one by one into groups; instead, you start big and break things apart.

How does divisive clustering work?

The general divisive clustering procedure can be described in the following steps:

1. Initialization. Place all n data points into a single cluster.
2. Select the cluster to split. Choose the cluster that is most heterogeneous according to some criterion (for example, the cluster with the largest diameter, highest variance, or greatest number of points).
3. Split the selected cluster. Divide the chosen cluster into two subclusters using a splitting strategy. Different algorithms use different strategies: DIANA uses a dissimilarity-based heuristic ^[1], bisecting k-means applies the k-means algorithm with k=2 ^[2], and PDDP projects data onto the first principal component ^[3].
4. Repeat. Return to step 2 and continue splitting until a stopping criterion is met.
5. Termination. The algorithm stops when the desired number of clusters has been reached, when each cluster contains only a single observation, or when some other quality threshold (such as a minimum cluster diameter) is satisfied.

The result is a hierarchy of nested clusters, which can be represented as a dendrogram ^[7]. The root of the dendrogram corresponds to the initial single cluster containing all observations, and the leaves correspond to individual data points.

Monothetic vs. polythetic splitting

Divisive clustering methods can be classified by how they use features during the splitting step ^[5]:

• Monothetic methods use a single variable at each split. The algorithm selects the variable that best separates the data and divides the cluster based on a threshold or category in that variable. Monothetic methods produce interpretable splits because each division can be described by a simple rule on one feature. The DIVCLUS-T algorithm (Chavent, 2007) is a well-known monothetic divisive method ^[4].
• Polythetic methods consider all variables simultaneously. They typically rely on a distance metric or dissimilarity matrix computed from all features. DIANA and bisecting k-means are both polythetic methods. Polythetic approaches generally produce higher-quality clusters because they capture the full multivariate structure of the data, but the resulting splits are harder to describe with simple rules.

What is the DIANA algorithm?

DIANA (DIvisive ANAlysis) was introduced by Leonard Kaufman and Peter J. Rousseeuw in their 1990 book Finding Groups in Data: An Introduction to Cluster Analysis ^[1]. It is the most widely cited divisive clustering algorithm and is implemented in the R programming language through the diana() function in the cluster package ^[15]. The R documentation notes that DIANA "is probably unique in computing a divisive hierarchy, whereas most other software for hierarchical clustering is agglomerative" ^[15]. The algorithm operationalizes the splinter-group method of Macnaughton-Smith et al. (1964) ^[14].

Algorithm details

DIANA constructs a hierarchy of clusters from the top down through the following procedure ^[1]:

1. Start with one cluster containing all n observations.

2. Select the cluster with the largest diameter. The diameter of a cluster is defined as the maximum dissimilarity between any two observations in that cluster.

3. Identify the most disparate observation. Within the selected cluster, find the observation with the largest average dissimilarity to all other members. This observation is removed from the cluster and placed into a new group called the "splinter group." The remaining observations form the "old party."

4. Reassign observations. For each observation i still in the old party, compute the difference:

   D(i) = [average dissimilarity of i to all observations in the old party] - [average dissimilarity of i to all observations in the splinter group]

   If the largest D(i) is positive, move that observation from the old party to the splinter group. Repeat this step until all remaining D(i) values are negative, meaning every remaining observation is closer (on average) to the old party than to the splinter group.

5. Record the split. The selected cluster has now been divided into two subclusters.

6. Repeat from step 2 until every cluster contains a single observation.

The divisive coefficient

DIANA produces a quality measure called the divisive coefficient (DC). For each observation i, let d(i) be the diameter of the last cluster to which it belonged before being separated as a singleton, divided by the diameter of the entire dataset. The divisive coefficient is then computed as:

DC = (1/n) * sum of (1 - d(i)) for all observations i

The R documentation defines the measure precisely: "For each observation i, denote by d(i) the diameter of the last cluster to which it belongs (before being split off as a single observation), divided by the diameter of the whole dataset. The dc is the average of all 1 - d(i)" ^[15].

DC values range from 0 to 1. A value close to 1 indicates strong clustering structure, while a value close to 0 suggests that the data lacks clear group separation. The DC is analogous to the agglomerative coefficient (AC) used in agglomerative methods ^[1].

The banner plot

DIANA also provides a visualization called the banner plot, which displays the order in which clusters are split ^[1]. Each observation is represented by a horizontal bar whose length corresponds to the diameter of the cluster from which it was last separated. The banner plot offers an intuitive view of the hierarchical splitting process and helps analysts assess the clustering structure.

DIANA example in R

The diana() function in R's cluster package computes the full divisive hierarchy, the divisive coefficient, and the banner plot ^[15]:

library(cluster)

# Run DIANA on the USArrests dataset
res.diana <- diana(USArrests, stand = TRUE)

# View the divisive coefficient
res.diana$dc
# [1] 0.8514  (example value)

# Plot the dendrogram
plot(res.diana, which.plots = 2, main = "DIANA Dendrogram")

# Cut the dendrogram into 4 clusters
clusters <- cutree(as.hclust(res.diana), k = 4)

What is bisecting k-means?

Bisecting k-means is a divisive clustering algorithm that combines the hierarchical top-down strategy with the flat partitioning approach of k-means clustering. It was popularized by Steinbach, Karypis, and Kumar in their 2000 paper A Comparison of Document Clustering Techniques ^[2].

Algorithm details

The bisecting k-means procedure works as follows ^[2]:

1. Start with one cluster containing all data points.
2. Select the cluster to bisect. Common selection criteria include choosing the cluster with the most data points (largest cluster) or the cluster with the highest sum of squared errors (biggest inertia).
3. Bisect the selected cluster. Apply the standard k-means algorithm with k=2 to the selected cluster, splitting it into two subclusters.
4. Repeat steps 2 and 3 until the desired number of clusters k is reached.

To improve robustness, the bisection step is often repeated multiple times with different random initializations, and the split that produces the best result (lowest total sum of squared errors) is kept.

Advantages of bisecting k-means

• Efficiency. Bisecting k-means runs in approximately O(n * k * t) time, where n is the number of data points, k is the target number of clusters, and t is the number of iterations per bisection. This is significantly faster than DIANA's O(n^2) space and time requirements.
• Quality. Steinbach, Karypis, and Kumar (2000) concluded that bisecting k-means "is better than the standard K-means approach and as good or better than the hierarchical approaches" they tested, as measured by entropy and F-measure; they attributed the result to bisecting k-means producing clusters of relatively uniform size, whereas regular k-means tends to produce clusters of widely differing sizes ^[2].
• Robustness to initialization. Unlike standard k-means, bisecting k-means is less sensitive to the initial placement of centroids because each bisection involves only two clusters.
• No empty clusters. The hierarchical splitting process guarantees that every cluster contains at least one data point.

Software implementations

Bisecting k-means is available in several major libraries and frameworks:

Scroll sideways for more →

In scikit-learn ^[13], the BisectingKMeans class was added in version 1.1 and supports two bisecting strategies via the bisecting_strategy parameter: "biggest_inertia" (the default, which selects the cluster with the highest sum of squared errors) and "largest_cluster" (which selects the cluster with the most points and generally runs faster) ^[16].

What is Principal Direction Divisive Partitioning (PDDP)?

PDDP is a divisive clustering algorithm introduced by Daniel Boley in 1998 in Data Mining and Knowledge Discovery ^[3]. Instead of using distance-based heuristics or k-means, PDDP splits clusters by projecting data onto the first principal component (the direction of greatest variance) and dividing along a hyperplane perpendicular to that direction.

Key characteristics of PDDP

• At each step, the cluster with the largest variance is selected for splitting.
• Data points are projected onto the leading eigenvector of the cluster's covariance matrix.
• A hyperplane orthogonal to this eigenvector, passing through the centroid, splits the cluster in two.
• PDDP is particularly effective for high-dimensional data such as document-term matrices because it exploits the sparsity of the data.
• The algorithm scales well with both dataset size and dimensionality.

PDDP has been applied extensively in text mining and information retrieval, where documents are represented as high-dimensional sparse vectors. A 2004 comparative analysis by Savaresi and Boley found that bisecting k-means and PDDP are closely related divisive schemes whose relative performance depends on the geometry of the data ^[9].

How computationally expensive is divisive clustering?

The computational cost of divisive clustering depends on the specific algorithm used and the splitting strategy employed ^[6].

Scroll sideways for more →

The exhaustive approach evaluates all 2^(n-1) - 1 possible ways to divide a cluster of n points into two nonempty subsets, which is computationally infeasible for any nontrivial dataset. This is why all practical divisive algorithms use heuristics to select the split.

How does divisive clustering differ from agglomerative clustering?

Divisive and agglomerative clustering are the two main families of hierarchical clustering. They produce dendrograms that look similar, but their construction processes differ, which leads to distinct strengths and weaknesses.

Scroll sideways for more →

A 2018 comparative study by Maurice Roux in the Journal of Classification evaluated 12 divisive algorithms against their agglomerative counterparts across a hundred random data tables and three real datasets, ranking results with the Goodman-Kruskal correlation coefficient. Roux found that split-evaluation criteria based on ratio-type formulas, specifically the Silhouette, Dunn, and Mollineda formulas, produced the best hierarchies ^[8].

One practical advantage of divisive methods is that analysts who are interested only in the top few partitions can stop early and obtain a useful result without running the algorithm to completion. In agglomerative clustering, the full dendrogram must typically be built before meaningful large-scale structure is visible.

Conversely, agglomerative methods tend to handle outliers more gracefully. In divisive clustering, an outlier may be separated into its own cluster during an early split, which can distort the remaining hierarchy.

What are the stopping criteria for divisive clustering?

Divisive clustering algorithms require a stopping criterion to determine when to stop splitting. Common approaches include:

• Target number of clusters. Specify the desired number of clusters k in advance. The algorithm stops after producing k clusters.
• Minimum cluster size. Stop splitting a cluster once it contains fewer than a specified number of observations.
• Maximum number of splits. Limit the total number of divisive steps.
• Cluster quality threshold. Stop when the diameter, variance, or inertia of every remaining cluster falls below a predefined threshold.
• Dendrogram cut height. Build the full dendrogram and then cut it at a specified height to obtain the desired granularity.
• Validation metrics. Use internal validation measures such as the silhouette score ^[12] or the Calinski-Harabasz index to determine the optimal number of clusters.

What is divisive clustering used for?

Divisive clustering methods have been applied across a wide range of domains:

Text mining and document clustering

Divisive methods are well-suited for organizing large collections of documents into hierarchical topic taxonomies. Bisecting k-means, in particular, has been shown to perform well for document clustering because the top-down approach naturally produces a browsable hierarchy. Steinbach et al. (2000) demonstrated that bisecting k-means outperformed both standard k-means and several agglomerative methods on document clustering benchmarks ^[2], a finding reinforced by Zhao and Karypis (2004) in their study of criterion functions for document clustering ^[11]. PDDP was also designed specifically with text data in mind and takes advantage of the sparse, high-dimensional nature of document-term matrices ^[3].

Bioinformatics and gene expression analysis

Hierarchical clustering is widely used in bioinformatics to group genes with similar expression profiles. Divisive methods can produce dendrograms that reveal the major functional categories of genes before showing finer subcategories. The MITree (Matrix Incision Tree) algorithm, introduced by Kim, Ohno-Machado, and Kohane in 2001, is a divisive method specifically designed for gene expression data that uses geometric space-partitioning to determine optimal splitting hyperplanes for DNA microarray datasets ^[17]. Divisive approaches have also been used for phylogenetic tree construction and protein sequence clustering.

Image segmentation

In computer vision, divisive clustering can be used to segment images by recursively partitioning pixel groups based on color, texture, or spatial features. The top-down approach can quickly separate an image into foreground and background regions before refining smaller segments.

Social network analysis

Divisive methods can partition social networks into communities by recursively splitting the network graph. The Girvan-Newman algorithm, while not a traditional clustering algorithm, follows a divisive logic by iteratively removing edges with the highest betweenness centrality to split the network into communities ^[10].

Urban planning and transportation

DIANA has been applied to GPS data for classifying urban street segments based on traffic characteristics and level-of-service criteria. In a 2016 study published in the Alexandria Engineering Journal, Patnaik, Bhuyan, and Rao used DIANA together with silhouette validation to classify free-flow-speed data collected from five major urban corridors in Mumbai into four level-of-service classes, demonstrating the algorithm's utility in spatial data analysis ^[18].

What are the strengths and limitations of divisive clustering?

Strengths

• Global perspective. By starting with the entire dataset, divisive methods make initial splits based on the overall structure of the data rather than local neighborhood relationships.
• Hierarchical output. The resulting dendrogram allows analysts to examine the data at multiple levels of granularity without rerunning the algorithm.
• Early termination. Analysts interested in only a few broad clusters can stop the algorithm early, saving computation.
• Large cluster detection. Divisive methods are better at identifying large, well-separated groups than agglomerative methods, which may struggle to merge smaller clusters correctly at higher levels.

Limitations

• Irreversible splits. Once a split is made, it cannot be undone. If an early split is suboptimal, all subsequent splits in those subclusters will be affected.
• Computational cost. DIANA requires O(n^2) space for the dissimilarity matrix and O(n^3) time in the worst case, making it impractical for very large datasets ^[1].
• Sensitivity to outliers. Outliers may be isolated into their own clusters during early splits, wasting splitting steps and potentially distorting the hierarchy.
• Limited software support. Compared to agglomerative methods, divisive clustering algorithms are implemented in fewer machine learning libraries; the R documentation notes that DIANA "is probably unique in computing a divisive hierarchy" among common tools ^[15].
• Splitting strategy dependence. The quality of the results depends heavily on the heuristic used to choose and execute splits.

Variants and extensions

Several extensions and variants of divisive clustering have been proposed:

• Bisecting k-medoids. Similar to bisecting k-means but uses medoids instead of centroids, making it more robust to outliers and applicable to non-Euclidean distance metrics.
• DIVCLUS-T. A monothetic divisive method proposed by Chavent (2007) that splits clusters using one variable at a time, producing highly interpretable results ^[4].
• Divisive information-theoretic clustering. Uses information-theoretic criteria such as mutual information or entropy to determine the best split at each step.
• Spectral divisive methods. Use the eigenvectors of a graph Laplacian or similarity matrix to determine splits, combining ideas from spectral clustering with the divisive framework.
• SOTA (Self-Organizing Tree Algorithm). Originally proposed for phylogenetic reconstruction, SOTA produces a divisive hierarchical binary tree using a neural network approach.

See also

• Hierarchical clustering
• Agglomerative clustering
• K-means clustering
• Clustering
• Dendrogram
• Silhouette score
• Principal component analysis
• Unsupervised learning

References

1. Kaufman, L., & Rousseeuw, P. J. (1990). *Finding Groups in Data: An Introduction to Cluster Analysis*. John Wiley & Sons. Chapter 6: Divisive Analysis (Program DIANA). ↩
2. Steinbach, M., Karypis, G., & Kumar, V. (2000). A Comparison of Document Clustering Techniques. *KDD Workshop on Text Mining*, University of Minnesota Technical Report #00-034. ↩
3. Boley, D. (1998). Principal Direction Divisive Partitioning. *Data Mining and Knowledge Discovery*, 2(4), 325-344. ↩
4. Chavent, M. (2007). DIVCLUS-T: A monothetic divisive hierarchical clustering method. *Computational Statistics & Data Analysis*, 52(2), 687-701. ↩
5. Jain, A. K., Murty, M. N., & Flynn, P. J. (1999). Data clustering: A review. *ACM Computing Surveys*, 31(3), 264-323. ↩
6. Xu, R., & Wunsch, D. (2005). Survey of clustering algorithms. *IEEE Transactions on Neural Networks*, 16(3), 645-678. ↩
7. Manning, C. D., Raghavan, P., & Schutze, H. (2008). *Introduction to Information Retrieval*. Cambridge University Press. Chapter 17: Hierarchical Clustering. ↩
8. Roux, M. (2018). A comparative study of divisive and agglomerative hierarchical clustering algorithms. *Journal of Classification*, 35(2), 345-366. ↩
9. Savaresi, S. M., & Boley, D. L. (2004). A comparative analysis on the bisecting k-means and the PDDP clustering algorithms. *Intelligent Data Analysis*, 8(4), 345-362. ↩
10. Girvan, M., & Newman, M. E. J. (2002). Community structure in social and biological networks. *Proceedings of the National Academy of Sciences*, 99(12), 7821-7826. ↩
11. Zhao, Y., & Karypis, G. (2004). Empirical and theoretical comparisons of selected criterion functions for document clustering. *Machine Learning*, 55(3), 311-331. ↩
12. Rousseeuw, P. J. (1987). Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. *Journal of Computational and Applied Mathematics*, 20, 53-65. ↩
13. Pedregosa, F., et al. (2011). Scikit-learn: Machine learning in Python. *Journal of Machine Learning Research*, 12, 2825-2830. ↩
14. Macnaughton-Smith, P., Williams, W. T., Dale, M. B., & Mockett, L. G. (1964). Dissimilarity Analysis: A New Technique of Hierarchical Sub-Division. *Nature*, 202, 1034-1035. ↩
15. Maechler, M., Rousseeuw, P., Struyf, A., Hubert, M., & Hornik, K. (2023). cluster: Cluster Analysis Basics and Extensions. R package, `diana()` (DIvisive ANAlysis Clustering) documentation. ↩
16. scikit-learn developers. sklearn.cluster.BisectingKMeans. scikit-learn documentation (class added in version 1.1). ↩
17. Kim, J. H., Ohno-Machado, L., & Kohane, I. S. (2001). Unsupervised Learning From Complex Data: The Matrix Incision Tree Algorithm. *Pacific Symposium on Biocomputing (PSB)*, 6, 30-41. ↩
18. Patnaik, A. K., Bhuyan, P. K., & Rao, K. V. K. (2016). Divisive Analysis (DIANA) of hierarchical clustering and GPS data for level of service criteria of urban streets. *Alexandria Engineering Journal*, 55(1), 407-418. ↩