Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 8835))
Included in the following conference series:
2484Accesses
Abstract
We study the problem ofr-anonymized clustering and give ak-means type extension. The problem is partition a set of objects intok different groups by minimizing the total cost between objects and cluster centers subject to a constraint that each cluster contains at leastr objects. Previous work has reported an approach when the cluster centers are constrained to be a real member of the objects. In this paper, we release the constraint and allow a center to be the mean of the objects in its group, similar to the settings of the classicalk-means clustering model. To address the inherent computational difficulty, we exploit linear program relaxation to find high quality solutions in an efficient manner. We conduct a series of experiments and confirm the effectiveness of the method as expected.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Jain, A., Murty, M., Flynn, P.: Data clustering: A review. ACM Computing Surveys 31(3), 264–323 (1999)
Basu, S., Davidson, I., Wagstaff, K.: Constrained Clustering: Advances in Algorithms, Theory, and Applications. Chapman & Hall (2008)
MacQueen, J.: Some methods for classification and analysis of multivariate observations. In: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1. University of California Press (1967)
Sweeney, L.: Uniqueness of simple demographics in the U.S. population (2000),http://privacy.cs.cmu.edu/
Aggarwal, C., Yu, P.: Privacy-Preserving Data Mining: Models and Algorithms. Springer (2008)
Froomkin, A.: The death of privacy? Stanford Law Review 52 (2000)
Sweeney, L.: k-anonymity: A model for protecting privacy. Int. J. Uncertainty Fuzziness Knowledge Based Syst. 10(5) (2002)
Meyerson, A., Williams, R.: On the complexity of optimal K-anonymity. In: Proceedings of PODS 2004. ACM (2004)
Yu, T., Jajodia, S. (eds.): Secure Data Management in Decentralized Systems, vol. 33. Springer (2007)
Aggarwal, G., Feder, T., Kenthapadi, K., Khuller, S., Panigrahy, R., Thomas, D., Zhu, A.: Achieving anonymity via clustering. In: Proceedings of PODS 2006. ACM (2006)
Wieland, S., Cassa, C., Mandl, K., Berger, B.: Revealing the spatial distribution of a disease while preserving privacy. Proc. Natl. Acad. Sci. USA 105(46) (2008)
Li, W.:r-anonymized clustering. In: Huang, T., Zeng, Z., Li, C., Leung, C.S. (eds.) ICONIP 2012, Part I. LNCS, vol. 7663, pp. 455–464. Springer, Heidelberg (2012)
Peng, J., Wei, Y.: Approximating k-means-type clustering via semidefinite programming. SIAM Journal on Optimization 18(1) (2007)
Lisser, A., Rendl, F.: Graph partitioning using linear and semidefinite programming. Mathematical Programming 95(1) (2003)
Riedel, S., Clarke, J.: Incremental integer linear programming for non-projective dependency parsing. In: Proceedings of EMNLP 2006 (2006)
Xing, E., Jordan, M.: On semidefinite relaxation for normalized k-cut and connections to spectral clustering. Technical report, University of California, Berkeley (2003)
Li, W., Schuurmans, D.: Modular community detection in networks. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence, pp. 1366–1371. AAAI (2011)
Li, W.: Modularity segmentation. In: Lee, M., Hirose, A., Hou, Z.-G., Kil, R.M. (eds.) ICONIP 2013, Part II. LNCS, vol. 8227, pp. 100–107. Springer, Heidelberg (2013)
Asuncion, A., Newman, D.: UCI machine learning repository (2007)
Frey, B.J., Dueck, D.: Clustering by passing messages between data points. Science 315 (2007)
Li, W., Xu, L., Schuurmans, D.: Facility locations revisited: An efficient belief propagation approach. In: 2010 IEEE International Conference on Automation and Logistics, pp. 408–413. IEEE (2010)
Li, W.: Clustering with uncertainties: An affinity propagation-based approach. In: Huang, T., Zeng, Z., Li, C., Leung, C.S. (eds.) ICONIP 2012, Part V. LNCS, vol. 7667, pp. 437–446. Springer, Heidelberg (2012)
Author information
Authors and Affiliations
Macao Polytechnic Institute, Rua de Luís Gonzaga, Macao SAR, China
Wenye Li
- Wenye Li
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
Department of Artificial Intelligence, Faculty of Computer Science and Information Technology Building, University of Malaya, 50603, Kuala Lumpur, Malaysia
Chu Kiong Loo
Department of Electronics and Communication Engineering, College of Engineering, Universiti Tenaga Nasional, Jalan IKRAM-UNITEN, 43009, Kajang, Selangor, Malaysia
Keem Siah Yap
School of Engineering and Information Technology, Murdoch University, South St., 6150, Murdoch, Western Australia, Australia
Kok Wai Wong
Department of Electrical and Electronics Engineering, Yonsei University, 50 Yonsei-ro, Seodaemun-gu, 120-749, Seoul, South Korea
Andrew Teoh
Department of Electrical and Electronic Engineering, Xi’an Jiaotong-Liverpool University, Ren’ai Road 111, SIP 215123, Suzhou, Jiangsu Province, China
Kaizhu Huang
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Li, W. (2014). Privacy Preserving Clustering: Ak-Means Type Extension. In: Loo, C.K., Yap, K.S., Wong, K.W., Teoh, A., Huang, K. (eds) Neural Information Processing. ICONIP 2014. Lecture Notes in Computer Science, vol 8835. Springer, Cham. https://doi.org/10.1007/978-3-319-12640-1_39
Download citation
Publisher Name:Springer, Cham
Print ISBN:978-3-319-12639-5
Online ISBN:978-3-319-12640-1
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative