Gravitational Inspired Spectral Clustering with Constraint

SUN Liping; LUO Yonglong; ZHENG Xiaoyao; LV Jun

doi:10.1049/cje.2015.07.008

Volume 24 Issue 3

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2015 > 24(3): 487-491

SUN Liping, LUO Yonglong, ZHENG Xiaoyao, et al., “Gravitational Inspired Spectral Clustering with Constraint,” Chinese Journal of Electronics, vol. 24, no. 3, pp. 487-491, 2015, doi: 10.1049/cje.2015.07.008

Citation:

SUN Liping, LUO Yonglong, ZHENG Xiaoyao, et al., “Gravitational Inspired Spectral Clustering with Constraint,” Chinese Journal of Electronics, vol. 24, no. 3, pp. 487-491, 2015, doi: 10.1049/cje.2015.07.008

Citation:

PDF( 677 KB)

Gravitational Inspired Spectral Clustering with Constraint

doi: 10.1049/cje.2015.07.008

1.
College of National Territorial Resources and Tourism, Anhui Normal University, Wuhu 241000, China;
2.
College of Mathematics and Computer Science, Anhui Normal University, Wuhu 241000, China

Funds: This work is supported by National Natural Science Foundation of China (No.61370050), and Research Program of Anhui Province Education Department (No.KJ2014A088).

More Information

Corresponding author: LUO Yonglong (corresponding author) was born in 1972. He received his Ph.D. degree on Computer Science and Technology in 2005. Currently, he is the professor and Ph.D. supervisor of Anhui Normal University. His research interests include information security and spatial data processing. (Email: ylluo@ustc.edu.cn)
Received Date: 2014-11-14
Rev Recd Date: 2015-01-21
Publish Date: 2015-07-10

Abstract

Abstract

Spectral clustering with pairwise constraints (i.e. mustlink and cannotlink) has been a hot topic in the machine learning community in recent years. Its performances are significantly influenced by utilizing the constraints. To make full use of the constraints' effect, pairwise constraints are integrated into an affinity matrix based on the gravitational method. In the data set as input, each point has mass property, and interacts with each other according to the universal law of gravitation. A Gravitational inspired constrained spectral clustering (GCSC) algorithm is proposed in this paper. Our algorithm is evaluated on multiple benchmark classification datasets. Compared with the existing approaches, experimental results demonstrate the effectiveness of our presented algorithm.
- Spectral clustering,
- Gravitation model,
- Affinity matrix,
- Pairwise constraint

FullText(HTML)

References(27)

References

A. Adhikari and P.R. Rao, "Efficient clustering of databases induced by local patterns", Decision Support Systems, Vol.44, No.4, pp.925-943, 2008.

M. Andrecut, "Data clustering and visualization via energy minimization", Physics Letters A, Vol.375, No.40, pp.3499-3503, 2011.

V. Deufemia, M. Risi and G. Tortora, "Sketched symbol recognition using latent-dynamic conditional random fields and distance-based clustering", Pattern Recognition, Vol.47, No.3, pp.1159-1171, 2014.

J.C. Bezdek and R.J. Hathaway, "Clustering with relational c-means partition from pairwise distance data", Mathematical Modelling, Vol.9, No.6, pp.435-439, 1987.

I.A. Maraziotis, "A semi-supervised fuzzy clustering algorithm applied to gene expression data", Pattern Recognition, Vol.45, No.1, pp.637-648, 2012.

H.P. Lai, M. Visani, A. Boucher and J.M. Ogier, "A new interactive semi-supervised clustering model for large image database indexing", Pattern Recognition Letters, Vol.37, pp.94- 106, 2014.

N. Grira, M. Crucianu and N. Boujemaa, "Unsupervised and semi-supervised clustering: A brief survey", A Review of Machine Learning Techniques for Processing Multimedia Content,Report of the MUSCLE European Network of Excellence (FP6), 2004.

M.S. Baghshah and S.B. Shouraki, "Semi-supervised metric learning using pairwise constraints", Proc. of 2009 International Joint Conference on Artificial Intelligence, California, pp.1217-1222, 2009.

K.Wagstaff and C. Cardie, "Clustering with Instance-level Constraints", Proc. of the Seventeenth International Conference on Machine Learning, Citeseer, pp.1103-1110, 2000.

H. Xu and Z. Tian, "An optimal spectral clustering approach based on Cauchy-Schwarz divergence", Chinese Journal of Electronics, Vol.18, No.1, pp.105-108, 2009.

X.Y. Li and L.J. Guo, "Constructing affinity matrix in spectral clustering based on neighbor propagation", Neurocomputing, Vol.97, pp.125-130, 2012.

M. Beauchemin, "A density-based similarity matrix construction for spectral clustering", Neurocomputing, Vol.151, pp.835- 844, 2015.

T. Xia, J. Cao, Y.D. Zhang and J.T. Li, "On defining affinity graph for spectral clustering through ranking on manifolds", Neurocomputing, Vol.72, No.13, pp.3203-3211, 2009.

W.E. Wright, "Gravitational clustering", Pattern Recognition, Vol.9, No.3, pp.151-166, 1977.

Y.J. Oyang, C.Y. Chen and T.W. Yang, "A study on the hierarchical data clustering algorithm based on gravity theory", Proc. of 5th European Conference on Principles of Data Mining and Knowledge Discovery, Freiburg, Germany, pp.350-361, 2001.

J. Gomez, D. Dasgupta and O. Nasraoui, "A new gravitational clustering algorithm", Proc. of the Third SIAM International Conference on Data Mining, pp.83-94, 2003.

J. Gomez, O. Nasraoui and E. Leon, "RAIN: Data clustering using randomized interactions between data points", Proc. of 2004 International Conference on Machine Learning and Applications, pp.250-255, 2004.

J. Gomez, E. Leon, O. Nasraoui and F. Giraldo, "The parameter-less randomized gravitational clustering algorithm with online clusters structure characterization", Progress in Artificial Intelligence, pp.1-20, 2014.

A.H. Sadeghian and H. Nezamabadi-pour, "Gravitational ensemble clustering", Proc. of 2014 Iranian Conference on Intelligent Systems (ICIS), pp.1-6, 2014.

U. Von Luxburg, "A tutorial on spectral clustering", Statistics and computing, Vol.17, No.4, pp.395-416, 2007.

P. Schroeder, "Gravity from the ground up", Proc. of the NPA, pp.498-503, 2010.

I. Newton, Philosophiæ Naturalis Principia Mathematica (Mathematical Principles of Natural Philosophy), Cambridge Digital Library, London, 1687.

G. Carpaneto and P. Toth, "Algorithm 548: Solution of the assignment problem", ACM Transactions on Mathematical Software, Vol.6, No.1, pp.104-111, 1980.

D. Klein, S.D. Kamvar and C.D. Manning, "From instance-level constraints to space-level constraints: Making the most of prior knowledge in data clustering", Proc. of the 19th International Conference on Machine Learning, Sydney, pp.307-314, 2002.

W.M. Rand, "Objective criteria for the evaluation of clustering methods", Journal of the American Statistical association, Vol.66, No.336, pp.846-850, 1971.

K. Wagstaff, C. Cardie, S. Rogers and S. Schroedl, "Constrained K-means clustering with background knowledge", Proc. of the Eighteenth International Conference on Machine Learning, pp.577-584, 2001.

Q. Xu and M. Desjardins, "Constrained Spectral Clustering under a Local Proximity Structure Assumption", Proc. of the 18th International Conference of the Florida Artificial Intelligence Research Society, pp.866-867, 2005.

Relative Articles

Supplements(0)

Cited By

Proportional views