REVIEW 3 major objections 6 minor 42 references
Fast Clustering of Categorical Big Data
T0 review · 3 major / 6 minor · reviewed 2026-08-08 · deepseek-v4-flash
Pith's one-line read Bisecting K-Modes, which repeatedly splits the highest-cost cluster into two using two-mode K-Modes and then uses the resulting K modes to initialize K-Modes, is claimed to make initial centers for categorical big-data clustering both…
desk verdict Bisecting K-Modes is a plausible incremental adaptation of bisecting k-means that delivers a solid efficiency win on large categorical datasets, but the quality claims are partially overstated and the evaluation lacks statistical rigor. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the Two-Modes algorithm, K-Modes restricted to K=2, combined with a greedy split rule. Its two initial centers are the mode of the cluster to be split and the farthest data point from that mode, an analogue of the farthest-point heuristic for K-means. At each bisection the cluster chosen for splitting is the one with the largest sum of Hamming distances to its center. The mode's exact minimizing property for the sum of Hamming distances is what makes each two-mode split a natural categorical analogue of the mean-based bisecting K-means, and the paper uses the final K modes of the bisection tree only as starting points for a standard K-Modes refinement.
What would settle it
One could run K-Modes on the same three datasets using centers produced by variants of the rule: for instance, bisecting the largest cluster by population instead of the one with the largest sum of distances, or initializing each bisection with two random points rather than the mode and farthest point. If any simpler variant matches or beats the proposed initialization's final sum of distances and runtime, the specific rule is not what carries the reported advantage.
Extended reading notes
Core claim
Working in the setting of categorical data with Hamming distance, where the mode of a cluster minimizes the within-cluster sum of distances, the paper's discovery is that a sequence of two-cluster K-Modes splits can supply good initial centers for the full K-cluster K-Modes problem. Concretely, the paper proposes Bisecting K-Modes: starting from the whole dataset, at each step select the existing cluster with the largest sum of distances, initialize two sub-centers as the cluster's mode and the data point farthest from that mode, run K-Modes with those two centers until convergence, and repeat until K clusters have been formed; the resulting K modes then initialize a final K-Modes run. Across the reported experiments, this produces equal or lower final sum of distances than random starts or the surveyed density-distance alternative in most configurations, with K-Modes converging in as few as five to eleven iterations on the largest datasets, and total runtime reduced by factors of roughly three to twenty in the larger K cases.
Load-bearing premise
The method's advantage rests on an unproven heuristic that the specific selection rule — always split the cluster with the largest sum of distances, and start the two sub-clusters with the mode and the farthest point from it — is a good way to find K well-placed initial centers; the paper gives no analysis or ablation comparing this rule with alternatives such as splitting the largest cluster or starting from two random modes.
Editorial extensions
If this is right
- Using BK-Modes centers as K-Modes initialization yields lower final sum of distances than random initialization and the surveyed density-distance method in most tested dataset/K combinations.
- K-Modes converges in far fewer iterations with BK-Modes initialization (for example, 5 to 11 iterations at K=300) than with random starts, reducing total runtime on million-point datasets from hours to minutes in several cases.
- The initialization itself is parameter-free, unlike many surveyed alternatives that require subsampling sizes or probability thresholds.
- On the PUF dataset, random starts and the density-distance method sometimes match BK-Modes in sum of distances but take much longer, so the efficiency gain holds even when the quality gain is modest.
Reading between the lines
- Our extension: the same bisection idea should transfer to k-medians or k-medoids with the componentwise median or medoid as the cluster representative, since those also minimize sum-of-distances objectives; a test on numerical data would separate the benefit of bisection from the choice of categorical mode.
- Our extension: the paper does not analyze the approximation ratio of the greedy largest-sum-of-distances rule, so a natural next step is to compare the final K centers against a full K-modes run from all data modes, or against centers obtained by repeated random bisection trees, to quantify how much of the quality comes from the tie-breaking of the split order.
- Our extension: one could make the method adaptive on the fly, choosing at each step between largest-sum-of-distances and largest-population splits based on a cheap estimate of cluster diameter, and test whether that reduces variance across datasets.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes Bisecting K-Modes (BK-Modes), a successive-bisection initialization scheme for the K-Modes algorithm on large categorical datasets. BK-Modes repeatedly selects the current cluster with the largest sum of Hamming distances to its mode, splits it into two clusters via a two-mode variant of K-Modes, and stops when K clusters are obtained; the K resulting modes are then used as initial centers for a final K-Modes run. The authors report experiments on three large categorical datasets (US Census, KDD Cup 1999, and a binary PUF challenge set), comparing K-Modes with random initialization, with Cao et al.'s density-and-distance initialization, and with their proposed BK-Modes initialization. They conclude that BK-Modes yields lower sum-of-distances and fewer iterations than the baselines in most tested settings, making it a reliable high-performance method.
Significance. If the reported advantages were statistically robust, the paper would offer a practical, parameter-free initialization for K-Modes that scales to million-point categorical datasets. The algorithmic idea is a natural extension of bisecting K-Means and is easy to implement. However, the paper provides no theory, no released code, and, as detailed below, the empirical evidence does not yet support the strong conclusion of reliability. The surveyed related work is useful as a compact overview, and the authors are explicit that Cao et al. is their only implemented competing initialization, which is a commendable simplification of scope.
major comments (3)
- [§4.4, Tables 1–3] The central claim that BK-Modes reliably improves K-Modes quality is not supported by the data as presented because every reported SD for the proposed method and for Cao et al. comes from a single run, with no variance estimates, no error bars, and no statistical tests. This matters because the five random runs themselves show large spread, and the best random run is often close to or better than the proposed method: in Table 1 (K=100) the best random SD is 8.22 versus proposed 8.06; in Table 1 (K=300) the best random SD is 7.22 versus proposed 7.07; and in Table 3 the proposed method is strictly worse than the best random run at K=30 (23.85 vs 23.68), K=100 (22.07 vs 21.93), and K=300 (20.65 vs 20.53). The conclusion that BK-Modes is a 'reliable' high-performance method therefore rests on a comparison against the average of random runs, not against the best achievable random initialization, and single local-optimum samples cannot establish a systematic advantage.
- [§4.3 and §4.4, time columns in Tables 1–3] The efficiency claim is similarly based on single-run wall-clock times, and the reported times are inconsistent with a clear advantage: in Table 3 (K=100), random Set3 finishes in 3 minutes with SD 22.44, while the proposed method takes 5 minutes with SD 22.07; in Table 1 (K=100), random Set4 finishes in 8 minutes with SD 8.22, versus 5 minutes for proposed SD 8.06. Since K-Modes iteration count and runtime are highly variable across random initializations, the paper needs repeated runs of each method (including the proposed method and Cao et al.) with summary statistics (mean, standard deviation, and ideally a paired test over multiple seeds) before the efficiency advantage can be taken as established.
- [§3, Algorithms 8 and 9] The specific heuristic choices — selecting the cluster with the largest sum of distances for bisection, and initializing the two sub-clusters with the cluster mode and the farthest point from it — are introduced without any analysis or ablation. Since these choices are the entire content of the proposed method, the absence of comparisons to alternative selection rules (e.g., bisecting the largest cluster, or using random two-mode starts) leaves open the possibility that the observed improvements come from the general bisecting framework rather than from these particular decisions, and that a simpler or cheaper rule would perform equally well. The authors should either provide a small ablation study on at least one dataset or explicitly discuss why these choices are canonical.
minor comments (6)
- [§2.4, Algorithm 2] The nested-loop variables x and y in the evidence-accumulation pseudocode are not reset between the outer and inner while loops; as written, the inner loop consumes x and y and the procedure terminates after one pass over the coordinates. The intended logic presumably uses for-loops over x=1..K and y=1..m.
- [§2.5.3, Algorithm 5] The formula for Dens(x) reads 'Dens(x) =− 1/n sum d(x,y)', which contains a misplaced minus sign and likely does not express the intended density measure; PosEx and other notation are also not formally defined in the text.
- [§2.7, Algorithm 7] The weighted matching distance formula uses 'δ(x, y)' with an undefined y; presumably it should be 'δ(x_a, vj_a)' or a per-attribute mismatch indicator against the current center vj.
- [Throughout] The paper uses 'K-Mode' and 'K-Modes' inconsistently (e.g., 'The K-Mode algorithm' in the introduction vs 'K-Modes' elsewhere); please standardize the terminology.
- [§4.4, Table 3] Several random runs in Dataset 3 converge in only 2 iterations (e.g., K=30 Set1, K=100 Set3, K=300 Set2), which suggests that the dataset has a very strong cluster structure; this should be discussed because it affects the generality of the reported gains in iteration count.
- [§5, Conclusion] The concluding sentence that BK-Modes is 'a reliable high-performance method' overstates the evidence in Tables 1–3, which lack repeated trials and statistical tests; please temper the conclusion or add the missing evidence.
Circularity Check
No significant circularity: the proposed BK-Modes initialization is fully specified and evaluated against external benchmarks, with no prediction that reduces to its inputs by construction.
full rationale
The paper's derivation chain is: define BK-Modes (Algorithm 8) as iterative bisection using a largest-sum-of-distances selection rule and a Two-Modes split (Algorithm 9), then use the resulting K centers as K-Modes initialization and measure SD and time on three large datasets. No parameter is fitted to the test data and then renamed as a prediction; the reported SD values are post-convergence outcomes of K-Modes, not outputs of the initialization by construction. The selection metric (sum of distances) coincides with the evaluation metric (Equation 4), but this is objective alignment for an initialization heuristic, not equivalence of input and output: the final K-Modes still runs to convergence from the proposed centers and is compared against random and Cao initializations. The paper includes self-citations to prior work by the authors, including Zhuang et al. 2016 for the bisecting K-Means template, but these are not load-bearing: the method is restated completely in Algorithms 8-9, and the evaluation is self-contained with external datasets and baseline methods. A legitimate concern, outside circularity, is that Tables 1-3 report single runs for the proposed method and best-of-five random runs, and in Table 3 the best random SD is slightly better than the proposed SD for every K; that is a statistical-support issue, not a circular-reasoning issue.
Assumptions & free parameters
assumptions (3)
- standard math The mode of a dataset minimizes the sum of Hamming distances to all points in the dataset.
- domain assumption K-Modes converges to a local minimum of the sum of distances objective.
- domain assumption Sum of distances (SD) is an appropriate measure of clustering quality for categorical data.
Cite this review
Pith. "Pith review of Fast Clustering of Categorical Big Data." pith.science (2026). https://pith.science/paper/JOJDAPN6
@misc{pith2026250207081,
author = {Pith},
title = {Pith review of: Fast Clustering of Categorical Big Data},
year = {2026},
howpublished = {\url{https://pith.science/paper/JOJDAPN6}},
note = {Machine review of arXiv:2502.07081}
}
read the original abstract
The K-Modes algorithm, developed for clustering categorical data, is of high algorithmic simplicity but suffers from unreliable performances in clustering quality and clustering efficiency, both heavily influenced by the choice of initial cluster centers. In this paper, we investigate Bisecting K-Modes (BK-Modes), a successive bisecting process to find clusters, in examining how good the cluster centers out of the bisecting process will be when used as initial centers for the K-Modes. The BK-Modes works by splitting a dataset into multiple clusters iteratively with one cluster being chosen and bisected into two clusters in each iteration. We use the sum of distances of data to their cluster centers as the selection metric to choose a cluster to be bisected in each iteration. This iterative process stops when K clusters are produced. The centers of these K clusters are then used as the initial cluster centers for the K-Modes. Experimental studies of the BK-Modes were carried out and were compared against the K-Modes with multiple sets of initial cluster centers as well as the best of the existing methods we found so far in our survey. Experimental results indicated good performances of BK-Modes both in the clustering quality and efficiency for large datasets.
Figures
Reference graph
Works this paper leans on
-
[1]
Some methods for classification and analysis of multivariate observations
James MacQueen et al. Some methods for classification and analysis of multivariate observations. In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, volume 1, pages 281--297. Oakland, CA, USA, 1967
1967
-
[2]
A fast clustering algorithm to cluster very large categorical data sets in data mining
Zhexue Huang. A fast clustering algorithm to cluster very large categorical data sets in data mining. DMKD, 3 0 (8): 0 34--39, 1997
work page 1997
-
[3]
Extensions to the k-means algorithm for clustering large data sets with categorical values
Zhexue Huang. Extensions to the k-means algorithm for clustering large data sets with categorical values. Data mining and knowledge discovery, 2 0 (3): 0 283--304, 1998
work page 1998
-
[4]
A new initialization method for categorical data clustering
Fuyuan Cao, Jiye Liang, and Liang Bai. A new initialization method for categorical data clustering. Expert Systems with Applications, 36 0 (7): 0 10223--10228, 2009
work page 2009
-
[5]
Cluster center initialization algorithm for k-modes clustering
Shehroz S Khan and Amir Ahmad. Cluster center initialization algorithm for k-modes clustering. Expert Systems with Applications, 40 0 (18): 0 7444--7456, 2013
work page 2013
-
[6]
Fast global k-means clustering based on local geometrical information
Liang Bai, Jiye Liang, Chao Sui, and Chuangyin Dang. Fast global k-means clustering based on local geometrical information. Information Sciences, 245: 0 168--180, 2013
work page 2013
-
[7]
An iterative initial-points refinement algorithm for categorical data clustering
Ying Sun, Qiuming Zhu, and Zhengxin Chen. An iterative initial-points refinement algorithm for categorical data clustering. Pattern Recognition Letters, 23 0 (7): 0 875--884, 2002
work page 2002
-
[8]
Refining initial points for k-means clustering
Paul S Bradley and Usama M Fayyad. Refining initial points for k-means clustering. In ICML, volume 98, pages 91--99. Citeseer, 1998
work page 1998
Show all 42 references
-
[9]
A new initialization method for clustering categorical data
Shu Wu, Qingshan Jiang, and Joshua Zhexue Huang. A new initialization method for clustering categorical data. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 972--980. Springer, 2007
2007
-
[10]
An initialization method to simultaneously find initial cluster centers and the number of clusters for clustering categorical data
Liang Bai, Jiye Liang, and Chuangyin Dang. An initialization method to simultaneously find initial cluster centers and the number of clusters for clustering categorical data. Knowledge-Based Systems, 24 0 (6): 0 785--795, 2011
2011
-
[11]
A global k-modes algorithm for clustering categorical data
BAI Tian, CA Kulikowski, GONG Leiguang, YANG Bin, HUANG Lan, and ZHOU Chunguang. A global k-modes algorithm for clustering categorical data. Chinese Journal of Electronics, 21 0 (3): 0 460--465, 2012
2012
-
[12]
Initialization of k-modes clustering using outlier detection techniques
Feng Jiang, Guozhu Liu, Junwei Du, and Yuefei Sui. Initialization of k-modes clustering using outlier detection techniques. Information Sciences, 332: 0 167--183, 2016
2016
-
[13]
UCI machine learning repository, 2017
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://archive.ics.uci.edu/ml
2017
-
[14]
An evaluation of statistical approaches to text categorization
Yiming Yang. An evaluation of statistical approaches to text categorization. Information retrieval, 1 0 (1-2): 0 69--90, 1999
1999
-
[15]
Cluster analysis for applications accademic press
MR Anderberg. Cluster analysis for applications accademic press. New York and London, 1973
1973
-
[16]
A comparison of document clustering techniques
Michael Steinbach, George Karypis, Vipin Kumar, et al. A comparison of document clustering techniques. In KDD workshop on text mining, volume 400, pages 525--526. Boston, 2000
2000
-
[17]
A limited-iteration bisecting k-means for fast clustering large datasets
Yu Zhuang, Yu Mao, and Xin Chen. A limited-iteration bisecting k-means for fast clustering large datasets. In 2016 IEEE Trustcom/BigDataSE/ISPA, pages 2257--2262. IEEE, 2016
2016
-
[18]
Computation of initial modes for k-modes clustering algorithm using evidence accumulation
Shehroz S Khan and Shri Kant. Computation of initial modes for k-modes clustering algorithm using evidence accumulation. In IJCAI, volume 7, pages 2784--2789, 2007
2007
-
[19]
A cluster centers initialization method for clustering categorical data
Liang Bai, Jiye Liang, Chuangyin Dang, and Fuyuan Cao. A cluster centers initialization method for clustering categorical data. Expert Systems with Applications, 39 0 (9): 0 8022--8029, 2012
2012
-
[20]
A linear method for deviation detection in large databases
Andreas Arning, Rakesh Agrawal, and Prabhakar Raghavan. A linear method for deviation detection in large databases. In KDD, volume 1141, pages 972--981, 1996
1996
-
[21]
Lof: identifying density-based local outliers
Markus M Breunig, Hans-Peter Kriegel, Raymond T Ng, and J \"o rg Sander. Lof: identifying density-based local outliers. In Proceedings of the 2000 ACM SIGMOD international conference on Management of data, pages 93--104, 2000
2000
-
[22]
Pabitra Mitra, CA Murthy, and Sankar K. Pal. Density-based multiscale data condensation. IEEE Transactions on pattern analysis and machine intelligence, 24 0 (6): 0 734--747, 2002
2002
-
[23]
Computing initial points using density based multiscale data condensation for clustering categorical data
Shehroz S Khan and Amir Ahmad. Computing initial points using density based multiscale data condensation for clustering categorical data. In 2nd International Conference on Applied Artificial Intelligence, ICAAI, volume 3. Citeseer, 2003
2003
-
[24]
Data clustering using evidence accumulation
Ana LN Fred and Anil K Jain. Data clustering using evidence accumulation. In Object recognition supported by user interaction for service robots, volume 4, pages 276--280. IEEE, 2002
2002
-
[25]
Farthest-point heuristic based initialization methods for k-modes clustering
Zengyou He. Farthest-point heuristic based initialization methods for k-modes clustering. arXiv preprint cs/0610043, 2006
2006 arXiv
-
[26]
Clustering to minimize the maximum intercluster distance
Teofilo F Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical computer science, 38: 0 293--306, 1985
1985
-
[27]
A fast deep learning method for security vulnerability study of xor pufs
Khalid T Mursi, Bipana Thapaliya, Yu Zhuang, Ahmad O Aseeri, and Mohammed Saeed Alkatheiri. A fast deep learning method for security vulnerability study of xor pufs. Electronics, 9 0 (10): 0 1715, 2020
2020
-
[28]
A hybrid-optimizer-enhanced neural network method for the security vulnerability study of multiplexer arbiter pufs
Khalid T Mursi, Bipana Thapaliya, and Yu Zhuang. A hybrid-optimizer-enhanced neural network method for the security vulnerability study of multiplexer arbiter pufs. In Journal of Physics: Conference Series, volume 1729, page 012010. IOP Publishing, 2021
-
[29]
Extensive examination of xor arbiter pufs as security primitives for resource-constrained iot devices
Khalid T Mursi, Yu Zhuang, Mohammed Saeed Alkatheiri, and Ahmad O Aseeri. Extensive examination of xor arbiter pufs as security primitives for resource-constrained iot devices. In 2019 17th International Conference on Privacy, Security and Trust (PST), pages 1--9. IEEE, 2019
2019
-
[30]
A machine learning-based security vulnerability study on xor pufs for resource-constraint internet of things
Ahmad O Aseeri, Yu Zhuang, and Mohammed Saeed Alkatheiri. A machine learning-based security vulnerability study on xor pufs for resource-constraint internet of things. In 2018 IEEE International Congress on Internet of Things (ICIOT), pages 49--56. IEEE, 2018
2018
-
[31]
A conceptual version of the k-means algorithm
Henri Ralambondrainy. A conceptual version of the k-means algorithm. Pattern Recognition Letters, 16 0 (11): 0 1147--1157, 1995
1995
-
[32]
Symbolic clustering using a new dissimilarity measure
K Chidananda Gowda and Edwin Diday. Symbolic clustering using a new dissimilarity measure. pattern recognition, 24 0 (6): 0 567--578, 1991
1991
-
[33]
Rock: A robust clustering algorithm for categorical attributes
Sudipto Guha, Rajeev Rastogi, and Kyuseok Shim. Rock: A robust clustering algorithm for categorical attributes. Information systems, 25 0 (5): 0 345--366, 2000
2000
-
[34]
Ecgn: A cluster-aware approach to graph neural networks for imbalanced classification
Bishal Thapaliya, Anh Nguyen, Yao Lu, Tian Xie, Igor Grudetskyi, Fudong Lin, Antonios Valkanas, Jingyu Liu, Deepayan Chakraborty, and Bilel Fehri. Ecgn: A cluster-aware approach to graph neural networks for imbalanced classification. arXiv preprint, 2024 a . doi:10.48550/ARXIV...
-
[35]
Calhoun, and Jingyu Liu
Bishal Thapaliya, Robyn Miller, Jiayu Chen, Yu Ping Wang, Esra Akbas, Ram Sapkota, Bhaskar Ray, Pranav Suresh, Santosh Ghimire, Vince D. Calhoun, and Jingyu Liu. Dsam: A deep learning framework for analyzing temporal and spatial dynamics in brain networks. Medical Image Analys...
2025
-
[36]
Graph-based deep learning models in the prediction of early-stage alzheimers
Bishal Thapaliya, Zundong Wu, Ram Sapkota, Bhaskar Ray, Pranav Suresh, Santosh Ghimire, Vince Calhoun, and Jingyu Liu. Graph-based deep learning models in the prediction of early-stage alzheimers. In 2024 46th Annual International Conference of the IEEE Engineering in Medicine...
2024
-
[37]
Calhoun, and Jingyu Liu
Bishal Thapaliya, Esra Akbas, Jiayu Chen, Ram Sapkota, Bhaskar Ray, Pranav Suresh, Vince D. Calhoun, and Jingyu Liu. Brain networks and intelligence: A graph neural network based approach to resting state fmri data. Medical Image Analysis, 101: 0 103433, April 2025 b . ISSN 13...
2025
-
[38]
Unsupervised deep embedding for clustering analysis, 2015
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis, 2015. URL https://arxiv.org/abs/1511.06335
2015 arXiv
-
[39]
Clustering with deep learning: Taxonomy and new methods, 2018
Elie Aljalbout, Vladimir Golkov, Yawar Siddiqui, Maximilian Strobel, and Daniel Cremers. Clustering with deep learning: Taxonomy and new methods, 2018. URL https://arxiv.org/abs/1801.07648
2018 arXiv
-
[40]
Nina Mishra, Robert Schreiber, Isabelle Stanton, and Robert E. Tarjan. Clustering Social Networks, page 56–67. Springer Berlin Heidelberg. ISBN 9783540770039. doi:10.1007/978-3-540-77004-6_5. URL http://dx.doi.org/10.1007/978-3-540-77004-6_5
-
[41]
Self-clustering graph transformer approach to model resting-state functional brain activity
Bishal Thapaliya, Esra Akbas, Ram Sapkota, Bhaskar Ray, Vince Calhoun, and Jingyu Liu. Self-clustering graph transformer approach to model resting-state functional brain activity. arXiv preprint, 2025 c . doi:10.48550/ARXIV.2501.16345. URL https://arxiv.org/abs/2501.16345
-
[42]
Deep learning for community detection: Progress, challenges and opportunities
Fanzhen Liu, Shan Xue, Jia Wu, Chuan Zhou, Wenbin Hu, Cecile Paris, Surya Nepal, Jian Yang, and Philip S Yu. Deep learning for community detection: Progress, challenges and opportunities. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intellige...
2020 doi
Reviewed August 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.