CciMST: A Clustering Algorithm Based on Minimum Spanning Tree and Cluster Centers

The minimum spanning tree- (MST-) based clustering method can identify clusters of arbitrary shape by removing inconsistent edges. The definition of the inconsistent edges is a major issue that has to be addressed in all MST-based clustering algorithms. In this paper, we propose a novel MST-based cl...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical problems in engineering 2018-01, Vol.2018 (2018), p.1-14
Main Authors: Huang, Hui, He, Xiaofu, Ma, Yan, Lv, Xiaobo, Yang, Jie
Format: Article
Language:English
Subjects:
Algorithms
Artificial intelligence
Boundaries
Clustering
Datasets
Gene expression
Graph theory
Methods
Pattern recognition
Shortest-path problems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The minimum spanning tree- (MST-) based clustering method can identify clusters of arbitrary shape by removing inconsistent edges. The definition of the inconsistent edges is a major issue that has to be addressed in all MST-based clustering algorithms. In this paper, we propose a novel MST-based clustering algorithm through the cluster center initialization algorithm, called cciMST. First, in order to capture the intrinsic structure of the data sets, we propose the cluster center initialization algorithm based on geodesic distance and dual densities of the points. Second, we propose and demonstrate that the inconsistent edge is located on the shortest path between the cluster centers, so we can find the inconsistent edge with the length of the edges as well as the densities of their endpoints on the shortest path. Correspondingly, we obtain two groups of clustering results. Third, we propose a novel intercluster separation by computing the distance between the points at the intersection of clusters. Furthermore, we propose a new internal clustering validation measure to select the best clustering result. The experimental results on the synthetic data sets, real data sets, and image data sets demonstrate the good performance of the proposed MST-based method.
ISSN:1024-123X
1563-5147
DOI:10.1155/2018/8451796