IEEE Transactions on Network Science and Engineering

IEEE Transactions on Network Science and Engineering (TNSE) is now accepting manuscript submissions. To submit your manuscript, please use the ScholarOne Manuscripts manuscript submission site. Read the full scope of TNSE

From the January-March 2016 issue

A Mathematical Theory for Clustering in Metric Spaces

By Cheng-Shang Chang, Wanjiun Liao, Yu-Sheng Chen, and Li-Heng Liou

Featured articleClustering is one of the most fundamental problems in data analysis and it has been studied extensively in the literature. Though many clustering algorithms have been proposed, clustering theories that justify the use of these clustering algorithms are still unsatisfactory. In particular, one of the fundamental challenges is to address the following question: What is a cluster in a set of data points? In this paper, we make an attempt to address such a question by considering a set of data points associated with a distance measure (metric). We first propose a new cohesion measure in terms of the distance measure. Using the cohesion measure, we define a cluster as a set of points that are cohesive to themselves. For such a definition, we show there are various equivalent statements that have intuitive explanations. We then consider the second question: How do we find clusters and good partitions of clusters under such a definition? For such a question, we propose a hierarchical agglomerative algorithm and a partitional algorithm. Unlike standard hierarchical agglomerative algorithms, our hierarchical agglomerative algorithm has a specific stopping criterion and it stops with a partition of clusters. Our partitional algorithm, called the $K$ -sets algorithm in the paper, appears to be a new iterative algorithm. Unlike the Lloyd iteration that needs two-step minimization, our $K$ -sets algorithm only takes one-step minimization. One of the most interesting findings of our paper is the duality result between a distance measure and a cohesion measure. Such a duality result leads to a dual $K$ -sets algorithm for clustering a set of data points with a cohesion measure. The dual $K$ -sets algorithm converges in the same way as a sequential version of the classical kernel $K$ -means algorithm. The key difference is that a cohesion measure does not need to be positive semi-definite.

download PDF View the PDF of this article       csdl View this issue in the digital library

Editorials and Announcements


  • We are pleased to announce that Ali Jadbabaie, a professor at University of Pennsylvania, Philadephia, has been appointed as the inaugural EIC for the IEEE Transactions on Network Science and Engineering, effective immediately.


Reviewers List

Annual Index

Call for Papers

General Call for Papers

General TNSE call for papers. View PDF.

Access recently published TNSE articles

Mail Sign up for the Transactions Connection newsletter.

Access TNSE Preprints in the Computer Society digital library

TNSE is financially cosponsored by:

IEEE Computer SocietyIEEE Circuits and Systems Society IEEE Comunications Society


TNSE is technically cosponsored by:

IEEE Control Systems SocietyIEEE Signal Processing Society