Open Access Open Access  Restricted Access Subscription or Fee Access

Affinity Propagation Clustering with Background Knowledge using Pair Wise Constraints

M. Yoga, R. Vadivu

Abstract


The pairwise constraints specifying whether a pair of samples should be grouped together or not have been successfully incorporated into the conventional clustering methods such as k-means and spectral clustering for the performance enhancement. Nevertheless, the issue of pairwise constraints has not been well studied in the recently proposed MMC (Maximum Margin Clustering), which extends the MMC in supervised learning for clustering and often shows a promising performance. In clustering process, semi-supervised learning is a class of machine learning techniques that make use of small amount of labeled and large amount of unlabeled data for training .This affinity propagation is aimed in making the effective clustering process by performing word wise comparison and overcomes the problem of overlapping that is encountered in K-mean and reduces the memory space required.

Keywords


Affinity Propagation, Pair wise Constraints, Semi Supervised Learning, Word Pair Process, MMC

Full Text:

PDF

References


B. Kulis, S. Basu, I. Dhillon, and R. Mooney, ―Semi-Supervised Graph Clustering: A Kernel Approach,‖ Proc. Int’l Conf. Machine Learning, pp. 457-464, 2005.

M. Ester, R. Ge, B.J. Gao, Z. Hu, and B. Ben-Moshe, ―Joint Cluster Analysis of Attribute Data and Relationship Data: The Connected

K-Center Problem,‖ Proc. SIAM Int’l Conf. Data Mining, pp. 25-46, 2006.

E.P. Xing, A.Y. Ng, M.I. Jordan, and S. Russell, ―Distance Metric Learning with Application to Clustering with Side-Information,‖ Advances in Neural Information Processing Systems, vol. 15, pp. 521-528, 2003.

S.C.H. Hoi, W. Liu, M.R. Lyu, and W.Y. Ma, ―Learning Distance Metrics with Contextual Constraints for Image Retrieval,‖ Proc. IEEE CS Conf. Computer Vision and Pattern Recognition, pp. 2072- 2078, 2006.

M. Bilenko, S. Basu, and R.J. Mooney, ―Integrating Constraints and Metric Learning in Semi-Supervised Clustering,‖ Proc. Int’l Conf. Machine Learning, pp. 81-88, 2004.

K. Wagstaff, C. Cardie, and S. Schroedl, ―Constrained K-Means Clustering with Background Knowledge,‖ Proc. Int’l Conf. Machine Learning, pp. 577-584, 2001.

Hong Zeng, and Yiu-Ming Cheung, ―Semi supervised maximum margin clustering with pairwise constraints‖ ,2012.

Z. Lu and M.A. Carreira-Perpinan, ―Constrained Spectral Clustering through Affinity Propagation,‖ Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 1-8, 2008.

L. Xu, J. Neufeld, B. Larson, and D. Schuurmans, ―Maximum Margin Clustering,‖ Advances in Neural Information Processing Systems, vol. 17, pp. 1537-1544, 2005.

H. Valizadegan and R. Jin, ―Generalized Maximum Margin Clustering and Unsupervised Kernel Learning,‖ Advances in Neural Information Processing Systems, vol. 19, pp. 1417-1424, 2007.

Y.F. Li, I.W. Tsang, J.T. Kwok, and Z.H. Zhou, ―Tighter and Convex Maximum Margin Clustering,‖ Proc. Int’l Conf. Artificial Intelligence and Statistics, pp. 344-351, 2009.

Y. Hu, J. Wang, N. Yu, and X.S. Hua, ―Maximum Margin Clustering with Pairwise Constraints,‖ Proc. IEEE Int’l Conf. Data Mining, pp. 253-262, 2008.

N. Nguyen and R. Caruana, ―Improving Classification with PairwiseConstraints: A Margin-Based Approach,‖ Proc. European Conf. Machine Learning and Knowledge Discovery in Databases,pp. 113-124, 2008.

K. Weinberger, J. Blitzer, and L. Saul, ―Distance Metric Learning for Large Margin Nearest Neighbor Classification,‖ Advances in Neural Information Processing Systems, vol. 18, pp. 1473-1480, 2006.

A. Strehl and J. Ghosh, ―Cluster Ensembles-A Knowledge Reuse Framework for Combining Multiple Partitions,‖ J. Machine Learning Research, vol. 3, pp. 583-617, 2003.

N. Shental, T. Hertz, D. Weinshall, and M. Pavel, ―Adjustment Learning and Relevant Component Analysis,‖ Proc. European Conf.Computer Vision, pp. 776-792 , 2002.

S. Basu, M. Bilenko, and R.J. Mooney, ―A Probabilistic Framework for Semi-Supervised Clustering,‖ Proc. ACM SIGKDD Int’l Conf.Knowledge Discovery and Data Mining, pp. 59-68, 2004.

N. Kumar and K. Kummamuru, Semi supervised Clustering with Metric Learning Using Relative Comparisons,‖ IEEE Trans. Knowledge and Data Eng., vol. 20, no. 4, pp. 496-503, Apr. 2008.

K. Zhang, I.W. Tsang, and J.T. Kwok, ―Maximum Margin Clustering Made Practical,‖ Proc. Int’l Conf. Machine Learning, pp. 1119-1126, 2007.

S.C.H. Hoi, R. Jin, and M.R. Lyu, ―Learning Nonparametric Kernel Matrices from Pairwise Constraints,‖ Proc. Int’l Conf. Machine Learning, pp. 361-368, 2007.

C. Domeniconi and D. Gunopulos. Adaptive nearest neighbor classification using support vector

Bar-Hillel, A., Hertz, T., Shental, N., Weinshall, D.: Learning distance functions using equivalence relations. In: Proceedings of the 20th International Conferenceon Machine Learning. (2003)

Cohn, D., Caruana, RMc Callum, A.: Semi-supervised clustering with user feed-back. In: Cornell University Technical Report TR2003-1892. (2003)

Bilenko, M., Basu, S., Mooney, R.J.: Integrating constraints and metric learning in semi-supervised clustering. In: Proceedings of 21th International Conference on Machine Learning. (2004)

Bellot, P., & El-Beze, M. (1999). A clustering method for information retrieval (Technical Report IR-0199). Laboratoire d'Informatique d'Avignon,France.

Cardie, C. (1993). A case-based approach to knowledge acquisition for domain-speci_csentence analysis.Proceedings of the Eleventh National Conference on Arti_cial Intelligence (pp. 798{803). Washington,DC: AAAI Press / MIT Press.

T. Joachims, ―Training Linear SVMs in Linear Time,‖ Proc. ACM SIGKDD Int’l Conf. Knowledge Discovery and Data Mining, pp. 217-226, 2006.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.