Mass Distribution versus Density Distribution in the Context of Clustering Journal: Artificial Intelligence

Kai Ming Ting 🖂, Ye Zhu, Hang Zhang 🖂, Tianrun Liang · 2026

Read Mass Distribution versus Density Distribution in the Context of Clustering Journal: Artificial Intelligence by Kai Ming Ting 🖂, Ye Zhu, Hang Zhang 🖂, Tianrun Liang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-10759.txt.

Introduction

Kai Ming Ting, Ye Zhu, Hang Zhang, and Tianrun Liang compare two ways to describe data for clustering. Density distribution has been the default lens since the early days of statistics. It says where points pile up thickly. Mass distribution takes a different view of the same points. The authors test the two lenses head to head.

They show that density has a built-in flaw: a high-density bias, no matter which clustering algorithm is used. Clusters in sparse regions can be swamped by dense ones. The finding reframes a step most data work takes for granted. Practitioners who group data, from images to genomes, get a reason to rethink their basic descriptor.

Catalog record

CREATORKai Ming Ting 🖂, Ye Zhu, Hang Zhang 🖂, Tianrun Liang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE109 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-10759

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Mass Distribution versus Density Distribution in the Context of Clustering Journal: Artificial Intelligence Kai Ming Ting 🖂, Ye Zhu, Hang Zhang 🖂, Tianrun Liang Abstract This paper investigates two fundamental descriptors of data, i.e., density distribution versus mass distribution, in the context of clustering. Density distribution has been the de facto descriptor of data distribution since the introduction of statistics. We show that density distribution has its fundamental limitation—high-density bias, irrespective of the algorithms used to perform clustering. Existing density-based clustering algorithms have employed different algorithmic means to counter the effect of the high-density bias with some success, but the fundamental limitation of using density distribution remains an obstacle to discovering clusters of arbitrary shapes, sizes and densities. Using the mass distribution as a better foundation, we propose a new algorithm which maximizes the total mass of all clusters, called mass-maximization clustering (MMC). The algorithm can be easily changed to maximize the total density of all clusters in order to examine the fundamental limitation of using density distribution versus mass distribution. The key advantage of the MMC over the density-maximization clustering is that the maximization is conducted without a bias towards dense clusters. 1 Introduction and motivation Density-based clustering [ 16 , 22 , 44 ] has its appeal because it can discover clusters of arbitrary shapes and sizes which match the distribution of the given dataset in high density regions. However, it has two key shortcomings. First, in terms of clustering outcomes, density-based clustering has been ‘haunted’ by the difficulty of discovering clusters of low density in the presence of high-density clusters. Despite various improvements (e.g., [ 1 , 7 , 14 , 9 , 28 , 45 , 67 ] ), the issue of bias towards dense clusters has merely shifted from one form to another, solving the problem in an early version of algorithm but creating a new problem in the new version. Examples are given in Table 1 , where the four density-based clustering algorithms fail to detect all clusters in at least one of the four datasets having different clusters of varied densities. That is, DBSCAN [ 16 ] could succeed on Jain and AC only; DP [ 44 ] could succeed on AC and 3G only; LGD [ 28 ] failed on AC though succeeded on others; and a new density-based algorithm called DMC introduced here succeeded on all datasets, except 3G. Table 1: Examples in which no single density-based clustering algorithm (out of DBSCAN, DP, LGD & DMC) can successfully discover all clusters in all four datasets having different clusters of varied densities. The ones with a yellow frame indicate perfect or near-perfect clustering outcomes. The number shown under each subfigure is the clustering outcome result in terms of F1. DBSCAN DP LGD DMC Description RingG Two dense Gaussian clusters & two sparse ring clusters 0.67 0.96 1 1 Jain Sparse top arc cluster & dense bottom arc cluster 1 0.74 1 1 AC Dense-centered arc cluster & sparse circle cluster 1 1 0.90 1 3G Two dense Gaussian clusters & one sparse Gaussian cluster 0.57 0.98 0.97 0.73 Second, density-based clustering algorithms have at least quadratic time complexity 1 1 1 The term ‘time complexity’ refers to the worst-case time complexity with respect to the dataset size. because they must use a density estimator in order to estimate the density for every point in the given dataset. Recent works [ 58 , 57 , 42 ] have revealed that the first key shortcoming is a result of using density distribution—a fundamental limitation that can be rectified by using mass distribution instead. They demonstrate the different clustering outcomes due to density distribution versus mass distribution using the same DBSCAN algorithm by simply replacing Euclidean distance with a mass-based similarity or a data dependent kernel. Though the effect of using a data-dependent/data-independent measure is clear, these works do not provide an explanation to this effect. Our work here fills in this gap in giving a new understanding in terms of cluster cohesiveness that has a wider impact on all clustering algorithms. Our analysis further reveals that the first key shortcoming is a result of an additional fundamental limitation of the point-based linking process in existing density-based clustering algorithms, for which the improvements thus far have failed to recognize and address. By addressing these two limitations, we show that the bias towards dense clusters can be eliminated. In addition, the solution has a significant efficiency gain—creating an algorithm having linear time complexity with respect to the dataset size, where existing density-based clustering algorithms have at least quadratic time complexity . Our contributions are: 1. Making explicit that the aim of clustering is to discover clusters of arbitrary shapes, sizes and densities in a given dataset. This means that a clustering algorithm shall find all clusters, irrespective of their shapes, sizes and densities. As the use of density-distribution leads to the high-density bias, density-based clustering algorithms have an inherent weakness in finding low-density clusters. 2. Targeting to address both the two fundamental limitations of existing density-based clustering algorithms: (a) The use of density distribution to describe the data distribution; and (b) the use of point-to-point linking process to form the final clusters. 3. Proposing an integrated means that (i) uses mass distribution to describe the data distribution; (ii) represents each cluster as a distribution via a kernel; and (iii) finds a representative sample of every cluster as the means to assign each point in the dataset to its most similar distribution/cluster. 4. Enacting a kernel mass estimator for the first time based on a recent data dependent kernel called Isolation Kernel (IK). Its density counterpart is kernel density estimator which typically uses the data independent Gaussian kernel. We show that IK guarantees the cohesiveness of every cluster to be approximately the same; and this produces a representative sample for every cluster. Density-based clustering has high-density bias because the low-density clusters are significantly less cohesive than high-density clusters. (See the definition of cohesiveness in Section 3.2 .) 5. Establishing that mass distribution, via representative samples, enables clusters of arbitrary shapes, sizes and densities in a dataset to be discovered, without the high-density bias. 6. Creating a new clustering algorithm, called Mass-Maximization Clustering (MMC), which maximizes the total mass of all clusters. It is a generic algorithm which can be easily converted to one that maximizes the total density of all clusters in order to examine the fundamental limitation of using density distribution versus mass distribution. Its density counterpart is called Density-Maximization Clustering (DMC). 7. Showing that (a) MMC has superior clustering outcomes than its density counterpart DMC as well as existing density-based algorithms; and (b) both MMC and DMC have linear time complexity whereas existing density-based clustering algorithms have at least quadratic time complexity. The proposed clustering algorithm is a new class of clustering which has two key steps. First, it finds initial clusters which are the representative samples of the distributions for individual clusters. Second, it assigns each point in the given dataset to its most similar initial cluster, as measured via a kernel, aiming to maximize the total mass (or density) of all clusters. Both steps ensure that both the initial and final clusters discovered

Read the complete text