An Adaptive Mutual K-nearest Neighbors Clustering Algorithm based on Maximizing Mutual Information

Yizhang Wang, Wei Pang, Zhixiang Jiao

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)
33 Downloads (Pure)


Clustering based on Mutual K-nearest Neighbors (CMNN) is a classical method of grouping data into different clusters. However, it has two well-known limitations: (1) the clustering results are very much dependent on the parameter k; (2) CMNN assumes that noise points correspond to clusters of small sizes according to the Mutual K-nearest Neighbors (MKNN) criterion, but some data points in small size clusters are wrongly identified as noises. To address these two issues, we propose an adaptive improved CMNN algorithm (AVCMNN), which consists of two parts: (1) improved CMNN algorithm (abbreviated as VCMNN) and (2) adaptive VCMNN algorithm (abbreviated as AVCMNN). Specifically, the first part is VCMNN algorithm, we first reassign the data points in some small-size clusters by a novel voting strategy because some of them are wrongly identified as noise points, and the clustering results are improved. Then, the second part is AVCMNN, we use maximizing mutual information to construct an objective function to optimize the parameters of the proposed method and finally obtain the better parameters values and clustering results. We conduct extensive experiments on twenty datasets, including six synthetic datasets, ten UCI datasets, and four image datasets. The experimental results show that VCMNN and AVCMNN outperforms three classical algorithms (i.e., CMNN, DPC, and DBSCAN) and six state-of-the-art (SOTA) clustering algorithms in most cases.
Original languageEnglish
Article number109273
JournalPattern Recognition
Early online date20 Dec 2022
Publication statusPublished - May 2023


  • Adaptive clustering
  • Maximizing mutual information
  • Mutual K-nearest neighbors

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence


Dive into the research topics of 'An Adaptive Mutual K-nearest Neighbors Clustering Algorithm based on Maximizing Mutual Information'. Together they form a unique fingerprint.

Cite this