Movatterモバイル変換


[0]ホーム

URL:


Skip to main content

Advertisement

Springer Nature Link
Log in

Privacy Preserving Clustering: Ak-Means Type Extension

  • Conference paper

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

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Jain, A., Murty, M., Flynn, P.: Data clustering: A review. ACM Computing Surveys 31(3), 264–323 (1999)

    Article  Google Scholar 

  2. Basu, S., Davidson, I., Wagstaff, K.: Constrained Clustering: Advances in Algorithms, Theory, and Applications. Chapman & Hall (2008)

    Google Scholar 

  3. 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)

    Google Scholar 

  4. Sweeney, L.: Uniqueness of simple demographics in the U.S. population (2000),http://privacy.cs.cmu.edu/

  5. Aggarwal, C., Yu, P.: Privacy-Preserving Data Mining: Models and Algorithms. Springer (2008)

    Google Scholar 

  6. Froomkin, A.: The death of privacy? Stanford Law Review 52 (2000)

    Google Scholar 

  7. Sweeney, L.: k-anonymity: A model for protecting privacy. Int. J. Uncertainty Fuzziness Knowledge Based Syst. 10(5) (2002)

    Google Scholar 

  8. Meyerson, A., Williams, R.: On the complexity of optimal K-anonymity. In: Proceedings of PODS 2004. ACM (2004)

    Google Scholar 

  9. Yu, T., Jajodia, S. (eds.): Secure Data Management in Decentralized Systems, vol. 33. Springer (2007)

    Google Scholar 

  10. 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)

    Google Scholar 

  11. 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)

    Google Scholar 

  12. 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)

    Chapter  Google Scholar 

  13. Peng, J., Wei, Y.: Approximating k-means-type clustering via semidefinite programming. SIAM Journal on Optimization 18(1) (2007)

    Google Scholar 

  14. Lisser, A., Rendl, F.: Graph partitioning using linear and semidefinite programming. Mathematical Programming 95(1) (2003)

    Google Scholar 

  15. Riedel, S., Clarke, J.: Incremental integer linear programming for non-projective dependency parsing. In: Proceedings of EMNLP 2006 (2006)

    Google Scholar 

  16. Xing, E., Jordan, M.: On semidefinite relaxation for normalized k-cut and connections to spectral clustering. Technical report, University of California, Berkeley (2003)

    Google Scholar 

  17. 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)

    Google Scholar 

  18. 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)

    Chapter  Google Scholar 

  19. Asuncion, A., Newman, D.: UCI machine learning repository (2007)

    Google Scholar 

  20. Frey, B.J., Dueck, D.: Clustering by passing messages between data points. Science 315 (2007)

    Google Scholar 

  21. 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)

    Google Scholar 

  22. 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)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Macao Polytechnic Institute, Rua de Luís Gonzaga, Macao SAR, China

    Wenye Li

Authors
  1. Wenye Li

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Artificial Intelligence, Faculty of Computer Science and Information Technology Building, University of Malaya, 50603, Kuala Lumpur, Malaysia

    Chu Kiong Loo

  2. Department of Electronics and Communication Engineering, College of Engineering, Universiti Tenaga Nasional, Jalan IKRAM-UNITEN, 43009, Kajang, Selangor, Malaysia

    Keem Siah Yap

  3. School of Engineering and Information Technology, Murdoch University, South St., 6150, Murdoch, Western Australia, Australia

    Kok Wai Wong

  4. Department of Electrical and Electronics Engineering, Yonsei University, 50 Yonsei-ro, Seodaemun-gu, 120-749, Seoul, South Korea

    Andrew Teoh

  5. 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

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only


[8]ページ先頭

©2009-2025 Movatter.jp