An enhanced Wu-Huberman algorithm with pole point selection strategy. (English) Zbl 1272.68345

Summary: The Wu-Huberman clustering is a typical linear algorithm among many clustering algorithms, which illustrates data points relationship as an artificial “circuit” and then applies the Kirchhoff equations to get the voltage value on the complex circuit. However, the performance of the algorithm is crucially dependent on the selection of pole points. In this paper, we present a novel pole point selection strategy for the Wu-Huberman algorithm (named as PSWH algorithm), which aims at preserving the merit and increasing the robustness of the algorithm. The pole point selection strategy is proposed to filter the pole point by introducing sparse rate. Experiments results demonstrate that the PSWH algorithm is significantly improved in clustering accuracy and efficiency compared with the original Wu-Huberman algorithm.


68T05 Learning and adaptive systems in artificial intelligence
68T10 Pattern recognition, speech recognition
68T30 Knowledge representation
Full Text: DOI


[1] Wang, F.; Zhang, C., Label propagation through linear neighborhoods, IEEE Transactions on Knowledge and Data Engineering, 20, 1, 55-67 (2008) · doi:10.1109/TKDE.2007.190672
[2] Sun, Y.; Tang, Y. Y.; Yang, L. Z., An adaptive selection strategy and separation measure for improving the Wu-Huberman clustering, ICIC Express Letters B, 3, 6, 1531-1536 (2012)
[3] Saul, L. K.; Weinberger, K. Q.; Sha, F.; Ham, J.; Lee, D. D., Spectral Methods for Dimensionality Reduction (2006), MIT Press
[4] Cui, W. H.; Wang, W.; Liu, X. B.; Wang, J. S., An improved clustering algorithm for product family design of paper currency sorter, IICIC Express Letters B, 3, 4, 909-915 (2012)
[5] Cheng, C.; Zhang, D.; Yu, Z.; Li, H., High speed data streams clustering algorithm based on improved SS tree, ICIC Express Letters B, 3, 1, 207-212 (2012)
[6] Wang, F.; Zhang, C.; Li, T., Clustering with local and global regularization, IEEE Transactions on Knowledge and Data Engineering, 21, 12, 1665-1678 (2009) · Zbl 1224.35228 · doi:10.1109/TKDE.2009.40
[7] Wang, X.; Wang, X.; Wilkes, D. M., A divide-and-conquer approach for minimum spanning tree-based clustering, IEEE Transactions on Knowledge and Data Engineering, 21, 7, 945-958 (2009) · doi:10.1109/TKDE.2009.37
[8] Chang, D. X.; Zhang, X. D.; Zheng, C. W., A genetic algorithm with gene rearrangement for K-means clustering, Pattern Recognition, 42, 7, 1210-1222 (2009) · doi:10.1016/j.patcog.2008.11.006
[9] Jing, L.; Ng, M. K.; Huang, J. Z., An entropy weighting k-means algorithm for subspace clustering of high-dimensional sparse data, IEEE Transactions on Knowledge and Data Engineering, 19, 8, 1026-1041 (2007) · doi:10.1109/TKDE.2007.1048
[10] Ng, M. K.; Li, M. J.; Huang, J. Z.; He, Z., On the impact of dissimilarity measure in \(κ\)-modes clustering algorithm, IEEE Transactions on Pattern Analysis and Machine Intelligence, 29, 3, 503-507 (2007) · doi:10.1109/TPAMI.2007.53
[11] Wang, M. H.; Tseng, Y. F.; Chen, H. C.; Chao, K. H., A novel clustering algorithm based on the extension theory and genetic algorithm, Expert Systems with Applications, 36, 4, 8269-8276 (2009) · Zbl 1288.92028 · doi:10.1016/j.eswa.2008.10.010
[12] Žalik, K. R., An efficient k′-means clustering algorithm, Pattern Recognition Letters, 29, 9, 1385-1391 (2008) · doi:10.1016/j.patrec.2008.02.014
[13] Belkin, M.; Niyogi, P.; Sindhwani, V., Manifold regularization: a geometric framework for learning from labeled and unlabeled examples, Journal of Machine Learning Research, 7, 11, 2399-2434 (2006) · Zbl 1222.68144
[14] Ding, C. H. Q.; He, X.; Zha, H.; Gu, M.; Simon, H. D., A min-max cult algorithm for graph partitioning and data clustering, Proceedings of the 1st IEEE International Conference on Data Mining (ICDM ’01)
[15] Shi, J.; Malik, J., Normalized cuts and image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 22, 8, 888-905 (2000) · doi:10.1109/34.868688
[16] Wu, F.; Huberman, B. A., Finding communities in linear time: a physics approach, European Physical Journal B, 38, 2, 331-338 (2004) · doi:10.1140/epjb/e2004-00125-x
[17] Schaeffer, S. E., Graph clustering, Computer Science Review, 1, 1, 27-64 (2007) · Zbl 1302.68237 · doi:10.1016/j.cosrev.2007.05.001
[18] Boccaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwang, D.-U., Complex networks: structure and dynamics, Physics Reports, 424, 4-5, 175-308 (2006) · Zbl 1371.82002 · doi:10.1016/j.physrep.2005.10.009
[19] Chapelle, O.; Sindhwani, V.; Keerthi, S.; Scholkopf, B.; Platt, J.; Hoffman, T., Branch and bound for semi-supervised support vector machines, Advances in Neural Information Processing Systems, 19 (2007), Cambridge, Mass, USA: MIT Press, Cambridge, Mass, USA
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.