Journal
TSINGHUA SCIENCE AND TECHNOLOGY
Volume 27, Issue 5, Pages 777-784Publisher
TSINGHUA UNIV PRESS
DOI: 10.26599/TST.2021.9010051
Keywords
Correlation; Clustering algorithms; Machine learning; Approximation algorithms; Biology; Partitioning algorithms; Data mining; balanced clustering; $k$-correlation clustering; positive edge dominant graphs; approximation algorithm
Categories
Funding
- National Natural Science Foundation of China [12131003, 12101594, 11771386, 11728104, 11201333]
- Beijing Natural Science Foundation Project [Z200002]
- China Postdoctoral Science Foundation [2021M693337]
- Natural Sciences and Engineering Research Council of Canada (NSERC) [06446]
Ask authors/readers for more resources
This paper introduces a significant application of the Correlation Clustering Problem, which is a clustering problem based on the similarity of data. A new variant of the problem is described and a polynomial time algorithm is presented. The effectiveness of the algorithm is verified through numerical experiments.
The Correlation Clustering Problem (CorCP) is a significant clustering problem based on the similarity of data. It has significant applications in different fields, such as machine learning, biology, and data mining, and many different problems in other areas. In this paper, the Balanced 2-CorCP (B2-CorCP) is introduced and examined, and a new interesting variant of the CorCP is described. The goal of this clustering problem is to partition the vertex set into two clusters with equal size, such that the number of disagreements is minimized. We first present a polynomial time algorithm for the B2-CorCP on $M$-positive edge dominant graphs ($M\geqslant 3$). Then, we provide a series of numerical experiments, and the results show the effectiveness of our algorithm.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available