wikillm

Paper · 2025-01-26 · cs.LG

Estimating the Optimal Number of Clusters in Categorical Data Clustering by Silhouette Coefficient

k-SCC picks the number of clusters for categorical data. It runs a k-means-style clustering for each k from 2 to 10, with kernel-density cluster centres and an information-theoretic dissimilarity, and keeps the k with the highest average silhouette. On Sake wine data it picks k=3 (silhouette 0.2811, author-reported) and beats three baselines on most settings.

Clustering evaluationk-means clusteringclusteringcategorical-datamodel-selection

arXivPDFCodeMarkdown11 min read

AI-compiled by claude-haiku-5-5 on 2026-11-12, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.

In plain words

Clustering sorts items into groups, but most methods need you to say in advance how many groups to look for. This paper is about that choice for data made of labels rather than numbers, such as "colour = red" or "size = large", where the usual averaging tricks do not work.

The authors run a k-means-style grouping for every candidate group count in a small range. Each group gets a "typical member" that is a soft mix of the labels seen in it. After each grouping they score how well every item fits its own group compared with the nearest other group, and they keep the group count with the best average score.

The method is meant for categorical data in general, and the authors test it on UCI and synthetic datasets as well as a 68-sample wine dataset. Every candidate group count needs its own full clustering run.

TL;DR

  • k-SCC chooses k for categorical data by maximising the average silhouette over candidate k values §4 eq. 19.
  • Each clustering uses kernel-density cluster centres and an information-theoretic dissimilarity §3 eq. 10 eq. 12.
  • The paper reports that k-SCC gives the highest average silhouette on the Sake wine case study at k=3 tab. 4.
  • All numbers are author-reported. The paper's own code reproduces only the Sake case study.
  • Practical caveats (dissimilarity formula, seeding, centre bookkeeping) are listed under Pitfalls.

Problem

Partitional clustering such as k-means needs the number of clusters k, and choosing it wrongly distorts the result §1. k-means itself works on numeric data only, and the k-modes-style alternatives for categorical data also take k as an input §2. The authors state that, to their knowledge, no earlier work used the silhouette coefficient to estimate k for categorical data §2.

Method

The method has three parts: a probabilistic cluster centre, a distance between an object and such a centre, and a silhouette-based choice of k.

  1. Data and categories. A categorical dataset is an n × m table, where attribute j has a finite set of categories O_j §3. Relative frequencies are defined within a cluster eq. 3 and over the whole dataset eq. 4.
  2. Probabilistic centre. The centre of cluster C_l is, for each attribute j, a probability distribution over the categories seen in that cluster §3 [def. 5] eq. 8 eq. 9. Each category gets a kernel-density estimate that mixes a uniform term and the observed frequency, weighted by a bandwidth λ_l eq. 6 eq. 10. The paper notes that this is a Bayes-type estimator with a uniform prior and the frequency as posterior §3.
  3. Bandwidth. λ_l is set per cluster and per iteration by least-squares cross-validation, in closed form eq. 7. It is not a fixed hyperparameter.
  4. Kernel form. The paper's Aitchison-and-Aitken-style kernel gives the observed category weight 1 − (|O|−1)/|O| × λ and every other category λ/|O| eq. 5.
  5. Dissimilarity between categories. Two categories in attribute j get an information-theoretic dissimilarity built from a joint frequency term and the two marginal frequencies eq. 11 eq. 12. Object dissimilarity is the sum over attributes eq. 13.
  6. Object-to-centre distance. The distance is the probability-weighted sum of category dissimilarities over the centre's distribution, summed over attributes eq. 14 eq. 15. The clustering objective is the sum of these distances eq. 16 under a hard-assignment constraint eq. 17.
  7. Silhouette. For each object, a(x) is its mean dissimilarity to its own cluster and b(x) its smallest mean dissimilarity to another cluster §3 [def. 9]. The silhouette is (b − a) / max(a, b) eq. 18, and the average over all objects is s_k eq. 19 [def. 10].
  8. Choosing k. For each k in the candidate range, run the clustering, compute s_k and keep the k with the largest s_k §4 alg. 1.

The clustering loop for one k is described in Algorithm 1 alg. 1. The outer loop over k is the same algorithm, with the average silhouette appended to SilSet for each k alg. 1.

Pseudocode
# k-SCC: choose k by average silhouette  [alg. 1]
# Input:  data (n objects, m categorical attributes); k_min, k_max
# Output: k_opt and the clustering for k_opt

def k_scc(data, k_min, k_max):
    # Pairwise object dissimilarity matrix  [alg. 1 l.2] [eq. 13]
    dissim_matrix = pairwise_dissimilarity(data)    # (n, n)
    avg_silhouettes = []
    clusterings = []
    for k in range(k_min, k_max + 1):
        # Clustering for this k, best of several restarts  [alg. 1 l.4-9] [§5]
        labels = best_clustering(data, k)
        # Average silhouette over all objects  [alg. 1 l.10] [eq. 19]
        avg_silhouettes.append(average_silhouette(dissim_matrix, labels))
        clusterings.append(labels)
    # Keep the k whose average silhouette is largest  [alg. 1 l.12]
    k_opt = argmax_over_k(avg_silhouettes) + k_min
    return k_opt, clusterings[k_opt - k_min]
Pseudocode
# One clustering for a fixed k  [alg. 1 l.4-9]
# Input:  data, k
# Output: labels (one cluster index per object)

def clustering_for_k(data, k):
    # Start from k objects, one per cluster  [alg. 1 l.4]
    centres = random_distinct_objects(data, k)
    # labels is None before the first pass; that counts as not converged
    labels = None
    while not partitions_converged(labels):
        # Keep the centres fixed and reassign each object  [alg. 1 l.7] [eq. 15]
        labels = assign_by_dissimilarity(data, centres)
        # Keep the labels fixed and recompute each centre  [alg. 1 l.8] [eq. 8]
        centres = [probabilistic_centre(data, labels, c) for c in range(k)]
    return labels
Pseudocode
# Probabilistic centre of one cluster  [eq. 3] [eq. 7] [eq. 10]
# Input:  data, labels, cluster c
# Output: one category distribution per attribute

def probabilistic_centre(data, labels, c):
    members = rows_of_cluster(data, labels, c)
    centre = []
    for j in range(m):
        # Relative frequency of each category in the cluster  [eq. 3]
        freq = category_frequencies(members, j)
        # Number of distinct categories in this cluster  [§3] [def. 3]
        n_categories = len(freq)
        # Bandwidth for the cluster, shared by its attributes  [eq. 7]
        lam = bandwidth(members)
        # Smoothed probability: lam / |O| + (1 - lam) * freq  [eq. 10]
        centre.append(
            {o: lam / n_categories + (1 - lam) * f
             for o, f in freq.items()})
    return centre
Pseudocode
# Distance between an object and a centre  [eq. 14] [eq. 15]
# Input:  x (m categories), centre (per attribute: category -> probability)

def object_centre_dissim(x, centre):
    total = 0.0
    for j in range(m):
        # Probability-weighted sum over the centre's categories  [eq. 14]
        for o, p in centre[j].items():
            total += p * category_dissim(x[j], o, j)
    return total
Pseudocode
# Silhouette value of one object  [§3] [def. 9] [eq. 18]
# Input:  i (object index), labels, dissim_matrix

def silhouette(i, labels, dissim_matrix):
    # a: mean dissimilarity to the other members of its cluster  [def. 9]
    a = mean_dissim_within_cluster(i, labels, dissim_matrix)
    # b: smallest mean dissimilarity to any other cluster  [def. 9]
    b = min_mean_dissim_to_other_clusters(i, labels, dissim_matrix)
    return (b - a) / max(a, b)

Key equations, as printed in the paper:

\lambda_l = \frac{1}{n_l - 1}\cdot \frac{\sum_{j=1}^{m}\bigl(1 - \sum_{o \in \mathcal{O}_j^l} [f_l(o)]^2\bigr)} {\sum_{j=1}^{m}\bigl(\sum_{o \in \mathcal{O}_j^l} [f_l(o)]^2 - \frac{1}{|\mathcal{O}_j^l|}\bigr)} eq. 7

P_j^l(o) = \begin{cases} \lambda_l \dfrac{1}{|\mathcal{O}_j^l|} + (1 - \lambda_l) f_l(o) & o \in \mathcal{O}_j^l \\ 0 & \text{otherwise} \end{cases} eq. 10

\mathrm{dsim}_j(o_{ij}, o_{i'j}) = 1 - \frac{2 \log f(o_{ij}, o_{i'j})}{\log f(o_{ij}) + \log f(o_{i'j})} eq. 12

s_k = \frac{\sum_{i=1}^{n} s(x_i)}{n} eq. 19

Hyperparameters

NameValueWhereNotes
Candidate range for k2 to 10 in the experiments; default k_min, k_max in [2, n−1]§4 §5.1 sake_kscc_it.pyThe code runs only 2 to 10
Random restarts100 per algorithm; the best run is kept§5 sake_kscc_it.py"Best" is not defined in the paper; the code uses lowest total cost sake_kscc_it.py
Bandwidth λ_lcomputed per clustereq. 7No fixed value; a zero denominator is undefined in the paper and returns 0 in code sake_kscc_it.py
Sake discretisationfive grades: very low, low, neither, high, very high§5.2Per-attribute mapping of the TS-5000Z values
Sake size68 samples, 8 features§5.2Initial taste: 6 features; aftertaste: 2 features
Convergenceno further reassignmentalg. 1 l.6Code also stops when the total cost stops falling sake_kscc_it.py
HardwareIntel Xeon Gold 6130 2.1 GHz (16 cores × 2), 64 GB RAM, CentOS 7.2§5Cluster node
SoftwarePython, PyCharm§5Repository says Python 3.6 README.md

Results

Author-reported. Setup: UCI and synthetic datasets, plus the Sake wine data as a case study. Baselines are k-modes §2, Modified-3 (k-representatives with kernel-density centres, §2) and k-SCC+, which is k-SCC with simple-matching dissimilarity §5.

Datasets used for the comparison tab. 3:

Dataset#instances#attributes#classesType
Car Evaluation1,72864Real-life
Chess3,196362Real-life
Connect-410,000423Real-life
Nursery12,96085Real-life
Soybean (small)47354Real-life
Spect Heart267222Real-life
Tic-Tac-Toe95892Real-life
SD5K5,00064Synthetic
SD10K10,00062Synthetic

On the UCI and synthetic datasets, the paper reports average silhouette curves for k from 2 to 10 fig. 2. The curves are not tabulated, so no numbers are given here. The text says k-SCC has higher average silhouette than the other three methods on all datasets §5.1. The text names the k values with the largest silhouettes per dataset, for example two to four clusters for Car Evaluation §5.1.

Sake wine case study, average silhouette by k tab. 4:

kk-modesModified-3k-SCC+k-SCC
20.14610.25010.20140.2501
30.14050.27440.20960.2811
40.15620.22520.15840.2585
50.13510.25110.19230.2451
60.17360.21350.18790.2200
70.17780.25560.21280.2328
80.15120.20280.22040.2217
90.11680.21680.19680.2288
100.14120.14690.21480.1924

The highest k-SCC value is at k=3 (0.2811), with k=4 second (0.2585) tab. 4. The paper concludes that the Sake samples can be classified into three or four clusters §5.2. For the complete-linkage dendrogram, cutting at heights eight, nine and ten gives four (with one outlier), three and two clusters respectively fig. 3 §5.2. Modified-3 is higher than k-SCC at k=5 and k=7, and k-SCC+ is higher at k=10 tab. 4.

Paper vs code

Official code: https://github.com/taiduydinh/k-SCC, at commit a5ea94b1d4211539a0edc2741d7a74372cb70f8a. It is owned by the first author's account, taiduydinh, which matches the first author's name; the paper links it. The repository has no LICENSE file, so its code cannot be quoted; this card cites the code by path and line only. The repository contains the Sake data and Python scripts for k-SCC and the baselines, but not the UCI and synthetic datasets of tab. 3. Only Code/lib/kscc_unsupervised.py and Code/sake_kscc_it.py were read in full. The baseline scripts (Code/sake_kmodes.py, Code/sake_kscc_sm.py, Code/lib/kmodes.py, Code/lib/dissim.py) were not reviewed.

  • Dissimilarity. Paper: joint frequency term defined as the frequency of "two categorical objects ... that receive the value belonging to {o, o'}" §3 eq. 11. Code: for different categories uses 2·log(f(x) + f(y)) in the numerator; for equal categories uses 2·log f(x) sake_kscc_it.py. These agree when the two categories never occur in the same object, but the paper's text does not say so.
  • Dissimilarity with a certain value. If both categories occur in every object (frequency 1.0), the code returns 0 sake_kscc_it.py. The paper does not mention this case.
  • Centre probabilities. Paper: |O_j^l| counts the categories that occur in the cluster §3 eq. 10. Code: moving an object decrements its old category count to 0 but keeps the key sake_kscc_it.py. Later, the number of categories is taken from all keys sake_kscc_it.py and sake_kscc_it.py, so categories with count 0 are counted and given mass λ/|O| sake_kscc_it.py. The paper's P is 0 for categories not in the cluster eq. 10.
  • Bandwidth. The formula matches eq. 7 sake_kscc_it.py, but the code takes the number of categories from the same keys, so it inherits the zero-count issue. The code returns 0 when the denominator is 0 or the cluster has one member sake_kscc_it.py.
  • Seeding. Paper: k objects chosen randomly, one per cluster alg. 1 l.4. Code: indices sampled with replacement, so duplicates are possible sake_kscc_it.py. Empty clusters are refilled with a random object from the largest cluster sake_kscc_it.py sake_kscc_it.py, which the paper does not describe.
  • First assignment. Paper: assignment by the object–centre distance eq. 15 inside the loop alg. 1 l.7. Code: the first assignment uses simple matching against the raw seed objects sake_kscc_it.py.
  • Update scheme. Paper: all objects are assigned, then all centres are updated, in passes alg. 1 l.6-9. Code: objects are moved one at a time, and the two affected centres are updated immediately sake_kscc_it.py.
  • Stopping rule. Paper: stop when partitions stop changing alg. 1 l.6. Code: also stop when the total cost stops decreasing sake_kscc_it.py.
  • Choice among restarts. Paper: "the best one was selected", criterion not stated §5. Code: lowest total cost sake_kscc_it.py.
  • Singleton silhouette. The code scores singleton clusters 0 and says this is "according to the paper" kscc_unsupervised.py. The paper's text does not say this.
  • Choice of k. The paper selects k by maximum average silhouette alg. 1 l.12. The script loops over k = 2 to 10 and writes the averages to a file sake_kscc_it.py sake_kscc_it.py. It does not pick the maximum. The candidate range is fixed at 2 to 10 and is not an argument.
  • Global state. The dissimilarity reads a module-level frequency table that is set during fitting sake_kscc_it.py. The silhouette distance matrix uses the table from the last fit sake_kscc_it.py.

No discrepancy was checked for the baseline scripts.

Pitfalls

  • Dissimilarity formula is under-specified. Eq. 11 does not define the joint frequency f(o, o') precisely. The paper's Table 2 (pairwise dissimilarities of the Table 1 example) is the only worked check tab. 1 tab. 2. A hand recomputation of the pair x1–x2 with the code's form gives about 4.46 (sum over six attributes, using the counts in Table 1), against the printed 4.3518 tab. 2. This was a hand calculation, not an executed check, so verify it before relying on it.
  • Smoothing mass on empty categories. A naive implementation that keeps zero-count categories (as the code does) gives them mass λ/|O| and inflates |O|. Remove categories whose count reaches 0 when you compute the centre and the bandwidth. This is inferred from the code, not stated in the paper.
  • Bandwidth denominator. The denominator of eq. 7 can be 0, for example for a single-category attribute in a cluster. The paper gives no fallback; the code returns 0.
  • Seeding with duplicates and empty clusters. Sampling seeds with replacement, or recovering empty clusters by moving a random object, changes the starting point and the restart statistics. Keep the paper's distinct seeds unless you intend to match the code.
  • Restart selection. Choosing the best of 100 runs by lowest dissimilarity cost (the code) is not the same as choosing by silhouette, which is what the method is about. The paper does not say which criterion it used.
  • Quadratic cost. The silhouette needs an n × n dissimilarity matrix eq. 13 and each clustering runs once per k. The authors state the high cost on large data §6; plan memory and time accordingly.
  • Silhouette values depend on the dissimilarity. The authors state that the average silhouette depends on the dissimilarity and clustering scheme §6. Results with simple matching (k-SCC+) differ noticeably tab. 4.
  • Results beyond Sake are plots. The UCI and synthetic results appear only as curves fig. 2, so a reproduction has to read values from the figures or rerun the experiments; the repository does not contain those datasets.
  • Restricted scope. The authors state that the method is a partitional one that ends at a local optimum, and that it is not extended to mixed data yet §6.

Lineage

  • Builds on: k-centers, which uses kernel-density probabilistic centres for categorical clustering §2 §3 (cited as ref. [4] in the paper); Modified-3 and the information-theoretic dissimilarity from earlier k-representatives work §2 (refs. [15], [11]); and the silhouette coefficient §2 (ref. [17]).
  • Compared against: k-modes §2 (ref. [8], [9]), Modified-3 §5 (ref. [15]), and k-SCC+ (the authors' own simple-matching variant) §5.
  • Superseded by: not known from the content of this wiki.

Source and license

Adapted from “Estimating the Optimal Number of Clusters in Categorical Data Clustering by Silhouette Coefficient” by Duy-Tai Dinh, Tsutomu Fujinami, Van-Nam Huynh (arXiv:2501.15542), used under CC BY 4.0. Changes: condensed and restructured for implementation, with tables, equations and algorithms taken from the paper and its code, each cited to its source. Not affiliated with or endorsed by the authors. Code citations refer to https://github.com/taiduydinh/k-SCC at commit a5ea94b1d421 (none (no LICENSE file in the repository)). Any quoted code is shown under that license.