{"id":"53fe436b-27bd-4d4b-a0dd-6c1174b1f484","arxiv_id":"2502.07081","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Bisecting K-Modes initializes K-Modes clustering via hierarchical splitting and shows promising speed and quality on large categorical datasets, but the experimental validation is limited.","lead":"The paper proposes Bisecting K-Modes, a method that builds K initial cluster centers for K-Modes clustering by repeatedly splitting the most spread-out cluster in half. On three large categorical datasets, it often produces better clustering quality and runs faster than random or Cao-style initialization, though the tests lack statistical rigor.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Need to assess claim that BK-Modes reliably improves K-Modes quality/efficiency; biggest gap is that reported quality gains are not established as robust because results lack variance estimates and use baselines (random, Cao) that themselves vary widely run-to-run.","rationale":"The reader identified the unproven design heuristic (largest-sum-of-distances cluster selection and farthest-point Two-Modes initialization) as the weakest assumption. I agree that the heuristic is unanalyzed, but the more load-bearing concern for the paper's central claim is empirical robustness: even the submitted single runs show the proposed method losing to the best random run on Dataset 3 at all K values, and losing to best random on Dataset 1 K=300 by a small margin (7.07 vs 7.22 is close). The reported comparisons are single runs without error bars, so the claimed systematic advantage over random and Cao is not established. This is not an internal inconsistency; it is a call for more evidence. The design heuristic concern is real but secondary: even if the specific selection rule is heuristic, a properly repeated experimental comparison could establish the method's practical merit. Conversely, the empirical robustness issue directly determines whether the conclusion 'reliable high-performance method' is supportable. Hence my verdict remains CONDITIONAL, matching the reader, but with a different emphasis: the condition is statistical evidence of superiority, not proof of optimality of the selection heuristic. My disagreement is partial because the reader's weakest assumption is valid and worth listing, but I would weight the missing variance/resampling evidence as the primary blocker.","tokens_in":9502,"tokens_out":1798,"duration_ms":15099,"concrete_test":"Run each method (random×5, Cao, proposed) at K=100 and K=300 on the three datasets for at least 30 independent runs (random starts varied; BK-Modes run with varied tie-breaking if any, and with random sub-centers as a control), and report mean SD, SD of SD, min SD, and total time. If the proposed method's mean SD is not statistically significantly lower (paired/matched comparison) than the best-of-5-random and Cao means, or if its min SD is worse than best random min SD, the paper's quality claim should be weakened. Also report a breakdown of BK-Modes bisection time vs K-Modes refinement time.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim is that using BK-Modes centers to initialize K-Modes yields lower SD and fewer iterations than random or Cao initialization. The load-bearing assumption is that the reported single-run SD values reflect systematic advantage. Tables 1–3 show high variance in random initialization: e.g., Table 1 K=100 random SD ranges 8.22–9.18, with the best random run (8.22) close to Cao (8.89) and not far from proposed (8.06); Table 1 K=300 random SD ranges 7.22–8.19, with best random SD 7.22 vs proposed 7.07. With a single run per condition for proposed/Cao and no error bars, the proposed method's advantage over the best-of-five random starts is small in several settings. Table 3 also shows proposed losing to random: K=30 proposed SD 23.85 vs best random 23.68; K=100 proposed 22.07 vs best random 21.93; K=300 proposed 20.65 vs best random 20.53. Thus the headline 'high clustering quality' depends on averaging over random runs and not comparing against the best achievable random start. Since K-Modes SD is non-increasing in iterations and can converge to different local optima, the reported values are single local-optimum samples. Without repeated runs of BK-Modes itself (whose Two-Modes bisections are deterministic given data, but whose cluster selection and bisection order can still depend on tie-breaking) and without statistical summaries, the claim that proposed is reliably better than the surveyed best method is not supported by the data as presented. Also, the efficiency claim is mostly driven by K-Modes needing fewer iterations; this is plausible but should be checked against total wall-clock including BK-Modes overhead, which is not separately reported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":1671,"tokens_out":1673,"duration_ms":42025,"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":[{"comment":"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.","section":"§4.4, Tables 1–3"},{"comment":"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.","section":"§4.3 and §4.4, time columns in Tables 1–3"},{"comment":"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.","section":"§3, Algorithms 8 and 9"}],"minor_comments":[{"comment":"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.","section":"§2.4, Algorithm 2"},{"comment":"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.","section":"§2.5.3, Algorithm 5"},{"comment":"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.","section":"§2.7, Algorithm 7"},{"comment":"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.","section":"Throughout"},{"comment":"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.","section":"§4.4, Table 3"},{"comment":"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.","section":"§5, Conclusion"}],"recommendation":"major_revision","confidential_remarks":"The paper is written like a workshop or short-paper contribution and does not provide code or a precise description of the PUF dataset generation, which limits reproducibility. The experimental section is the core of the paper, and the missing repeated-run statistics is the main blocker. I would be willing to look at a revision that adds error bars and statistical comparisons, even if only for a subset of the configurations."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: Bisecting K-Modes is a direct adaptation of bisecting k-means to categorical data, and the two design heuristics (largest-sum-of-distances cluster selection, mode + farthest-point initialization) are reasonable but not tested against alternatives. What's genuinely new is the application to K-Modes and the experiments on three datasets with millions of rows; that's real work and the efficiency numbers are striking.\n\nThe paper does a few things well. The survey of K-Modes initialization methods is useful. The algorithm is simple to state and deterministic given tie-breaking, so repeatedly running BK-Modes itself isn't the main ask. The wall-clock results are consistent: on all three datasets, at all K, the proposed method converges in few iterations and the total time is one to two orders of magnitude below random and Cao. That is a solid, reproducible finding.\n\nSoft spots: (1) Only Cao et al. is used as a non-random baseline, even though the survey covers a dozen methods, so the 'best of existing methods' claim is not tested. (2) The quality numbers are less one-sided than the conclusion suggests. On Dataset 3, the proposed SD is slightly worse than the average of the five random runs at every K (e.g., 20.65 vs 20.64 at K=300), and it also loses to the best random run. On Datasets 1 and 2, proposed beats average random and Cao, but by margins that, with single runs and no variance summaries, are not established as systematic. (3) The paper reports no statistical tests, no external cluster-quality metrics, no code/data. (4) The conclusion overstates: 'reliable high-performance method' goes beyond what the evidence supports. The honest claim is: BK-Modes is robustly faster and gives comparable-or-better SD on two of three large datasets.\n\nOne thing I'd tell the authors: several of the paragraph-long references to your own deep-learning clustering papers in the intro are padding; trim them. The stress-test worry about error bars on proposed is partly misplaced—the method is deterministic—but a referee should ask for mean/median/best summaries of the random baseline and standard errors around Cao.\n\nBottom line: incremental but not trivial. The method is plausible, the experiments are on serious scale, and the efficiency result is worth reporting. With a revision that adds baselines, statistics, and a tempered conclusion, it would be a fine niche paper. I would send it to peer review.","headline":"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.","tokens_in":10412,"tokens_out":6040,"would_cite":false,"duration_ms":52674,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["bisecting K-modes","initial cluster centers","categorical data","Hamming distance","K-modes","large-scale clustering","sum of distances","mode"],"falsifier":"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.","tokens_in":9294,"feed_emoji":"🗂️","tokens_out":6525,"duration_ms":53639,"temperature":0.7,"pith_summary":"This paper claims that the initial cluster centers for K-Modes can be obtained cheaply and reliably by recursive bisection: start with the whole categorical dataset as one cluster, repeatedly split the cluster with the largest sum of distances into two using a two-mode variant of K-Modes, until K clusters exist, and then run K-Modes from those K centers. On three large categorical datasets with millions of points, the paper reports that this Bisecting K-Modes initialization reaches a lower final sum of distances and fewer K-Modes iterations than random initialization and than a surveyed density-distance initialization in most tested settings, often with much shorter total runtime. If the claim holds, it gives practitioners a parameter-free way to make K-Modes on big categorical data both faster and more stable. The load-bearing mechanism is the bisection rule, not a new distance or objective.","feed_headline":"Bisecting K-Modes seeds K-Modes to faster, better big-data clustering","feed_subtitle":"Bisection-start K-Modes reaches lower distortion in a few iterations, often in minutes, on three million-point datasets.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Establishes that the mode minimizes the sum of Hamming distances, which is the theoretical basis for both K-Modes and the Two-Modes initialization used in each bisection.","marker":"Huang [1997]"},{"why":"Introduces the K-Modes algorithm for categorical data, which is the method that the proposed initialization is designed to improve.","marker":"Huang [1998]"},{"why":"Provides the surveyed density-distance initialization method that serves as the primary baseline in the experiments.","marker":"Cao et al. [2009]"},{"why":"Introduces the bisecting K-means idea that the paper extends to categorical data and the mode-based center.","marker":"Steinbach et al. [2000]"},{"why":"Implements limited-iteration bisecting K-means for fast large-scale clustering, the immediate numerical-data predecessor of this work.","marker":"Zhuang et al. [2016]"},{"why":"Farthest-point heuristic that motivates the choice of the farthest point from the mode as the second initial center in each Two-Modes split.","marker":"Gonzalez [1985]"}],"fun_headline_variants":["Bisecting K-Modes seeds K-Modes for faster, better categorical clustering","Splitting data smartly improves K-Modes speed and quality on big data","Two-way splits prime K-Modes for large categorical datasets","BK-Modes: smarter initialization for K-Modes on big categorical data"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Bisecting K-Modes seeds K-Modes for faster, better categorical clustering","Splitting data smartly improves K-Modes speed and quality on big data","Two-way splits prime K-Modes for large categorical datasets","BK-Modes: smarter initialization for K-Modes on big categorical data"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000647,"raw_usage":{"total_tokens":2979,"prompt_tokens":960,"completion_tokens":2019,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":576,"completion_tokens_details":{"reasoning_tokens":1939}},"tokens_in":576,"tokens_out":2019,"duration_ms":13105,"temperature":1.0,"reasoning_tokens":1939,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T13:51:07.135576+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"A fast clustering algorithm to cluster very large categorical data sets in data mining","cited_arxiv_id":null,"evidence_quote":"Establishes that the mode minimizes the sum of Hamming distances, which is the theoretical basis for both K-Modes and the Two-Modes initialization used in each bisection."},{"cited_title":"Extensions to the k-means algorithm for clustering large data sets with categorical values","cited_arxiv_id":null,"evidence_quote":"Introduces the K-Modes algorithm for categorical data, which is the method that the proposed initialization is designed to improve."},{"cited_title":"A new initialization method for categorical data clustering","cited_arxiv_id":null,"evidence_quote":"Provides the surveyed density-distance initialization method that serves as the primary baseline in the experiments."},{"cited_title":"A comparison of document clustering techniques","cited_arxiv_id":null,"evidence_quote":"Introduces the bisecting K-means idea that the paper extends to categorical data and the mode-based center."},{"cited_title":"A limited-iteration bisecting k-means for fast clustering large datasets","cited_arxiv_id":null,"evidence_quote":"Implements limited-iteration bisecting K-means for fast large-scale clustering, the immediate numerical-data predecessor of this work."},{"cited_title":"Clustering to minimize the maximum intercluster distance","cited_arxiv_id":null,"evidence_quote":"Farthest-point heuristic that motivates the choice of the farthest point from the mode as the second initial center in each Two-Modes split."}],"review_version":1}