Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Partition-Based Clustering Using Constraint Optimization

  • Chapter
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNAI,volume 10101))

  • 1640Accesses

Abstract

Partition-based clustering is the task of partitioning a dataset in a number of groups of examples, such that examples in each group are similar to each other. Many criteria for what constitutes a good clustering have been identified in the literature; furthermore, the use of additional constraints to find more useful clusterings has been proposed. In this chapter, it will be shown that most of these clustering tasks can be formalized using optimization criteria and constraints. We demonstrate how a range of clustering tasks can be modelled in generic constraint programming languages with these constraints and optimization criteria. Using the constraint-based modeling approach we also relate the DBSCAN method for density-based clustering to the label propagation technique for community discovery.

Siegfried Nijssen can currently be reached at the Institute of Information and Communication Technologies, Electronics and Applied Mathematics, UC Louvain, Belgium.

Tias Guns can currently be reached at the Vrije Universiteit Brussel.

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 EPUB and 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

Similar content being viewed by others

References

  1. Aggarwal, C.C., Reddy, C.K.: Data Clustering: Algorithms and Applications, 1st edn. Chapman & Hall/CRC, Boca Raton (2013)

    MATH  Google Scholar 

  2. Babaki, B., Guns, T., Nijssen, S.: Constrained clustering using column generation. In: Simonis, H. (ed.) CPAIOR 2014. LNCS, vol. 8451, pp. 438–454. Springer, Heidelberg (2014). doi:10.1007/978-3-319-07046-9_31

    Chapter  Google Scholar 

  3. Basu, S., Davidson, I., Wagstaff, K., Clustering, C.: Advances in Algorithms, Theory, and Applications, 1st edn. Chapman & Hall/CRC, Boca Raton (2008)

    Google Scholar 

  4. Berthold, M.R., Borgelt, C., Hppner, F., Klawonn, F.: Guide to Intelligent Data Analysis: How to Intelligently Make Sense of Real Data, 1st edn. Springer, Heidelberg (2010)

    Book MATH  Google Scholar 

  5. Coscia, M., Giannotti, F., Pedreschi, D.: A classification for community discovery methods in complex networks. Stat. Anal. Data Min.4(5), 512–546 (2011)

    Article MathSciNet  Google Scholar 

  6. Dao, T., Duong, K., Vrain, C.: A filtering algorithm for constrained clustering with within-cluster sum of dissimilarities criterion. In: 2013 IEEE 25th International Conference on Tools with Artificial Intelligence, Herndon, VA, USA, 4–6 November 2013, pp. 1060–1067 (2013)

    Google Scholar 

  7. Dao, T.-B.-H., Duong, K.-C., Vrain, C.: A declarative framework for constrained clustering. In: Blockeel, H., Kersting, K., Nijssen, S., Železný, F. (eds.) ECML PKDD 2013. LNCS (LNAI), vol. 8190, pp. 419–434. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40994-3_27

    Chapter  Google Scholar 

  8. Dao, T.-B.-H., Duong, K.-C., Vrain, C.: Constrained clustering by constraint programming. Artif. Intell. (2015)

    Google Scholar 

  9. Davidson, I., Ravi, S.: The complexity of non-hierarchical clustering with instance and cluster level constraints. Data Min. Knowl. Disc.14(1), 25–61 (2007)

    Article MathSciNet  Google Scholar 

  10. Davidson, I., Ravi, S.S.: Clustering with constraints: feasibility issues and the k-means algorithm. In: Proceedings of the 2005 SIAM International Conference on Data Mining, SDM 2005, Newport Beach, CA, USA, 21–23 April 2005, pp. 138–149 (2005)

    Google Scholar 

  11. du Merle, O., Hansen, P., Jaumard, B., Mladenovic, N.: An interior point algorithm for minimum sum-of-squares clustering. SIAM J. Sci. Comput.21(4), 1485–1505 (1999)

    Article MathSciNet MATH  Google Scholar 

  12. Ester, M., Kriegel, H.-P., Sander, J., Xu, X.: A density-based algorithm for discovering clusters in large spatial databases with noise. In: Simoudis, E., Han, J., Fayyad, U.M. (eds.) KDD, pp. 226–231. AAAI Press, Menlo Park (1996)

    Google Scholar 

  13. Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci.38, 293–306 (1985)

    Article MathSciNet MATH  Google Scholar 

  14. Hansen,P., Aloise, D.: A survey on exact methods for minimum sum-of-squares clustering, pp. 1–2, January 2009.http://www.math.iit.edu/Buck65files/msscStLouis.pdf

  15. Jain, A.K., Murty, M.N., Flynn, P.J.: Data clustering: a review. ACM Comput. Surv.31(3), 264–323 (1999)

    Article  Google Scholar 

  16. Mueller, M., Kramer, S.: Integer linear programming models for constrained clustering. In: Pfahringer, B., Holmes, G., Hoffmann, A. (eds.) DS 2010. LNCS (LNAI), vol. 6332, pp. 159–173. Springer, Heidelberg (2010). doi:10.1007/978-3-642-16184-1_12

    Chapter  Google Scholar 

  17. Raghavan, U.N., Albert, R., Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E76(2), 036106+ (2007)

    Article  Google Scholar 

  18. Wagstaff, K., Cardie,C.: Clustering with instance-level constraints. In: Proceedings of the Seventeenth International Conference on Machine Learning (ICML 2000), Stanford University, Stanford, CA, USA, June 29–July 2 2000, pp. 1103–1110 (2000)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Pisa, Pisa, Italy

    Valerio Grossi & Anna Monreale

  2. ISTI - CNR, Pisa, Italy

    Mirco Nanni

  3. DTAI, KU Leuven, Leuven, Belgium

    Tias Guns & Siegfried Nijssen

  4. LIACS, Universiteit Leiden, Leiden, The Netherlands

    Siegfried Nijssen

Authors
  1. Valerio Grossi

    You can also search for this author inPubMed Google Scholar

  2. Tias Guns

    You can also search for this author inPubMed Google Scholar

  3. Anna Monreale

    You can also search for this author inPubMed Google Scholar

  4. Mirco Nanni

    You can also search for this author inPubMed Google Scholar

  5. Siegfried Nijssen

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toSiegfried Nijssen.

Editor information

Editors and Affiliations

  1. Université Montpellier 2, Montpellier, France

    Christian Bessiere

  2. KU Leuven, Heverlee, Belgium

    Luc De Raedt

  3. University of British Columbia, Vancouver, British Columbia, Canada

    Lars Kotthoff

  4. Université Catholique de Louvain, Louvain-la-Neuve, Belgium

    Siegfried Nijssen

  5. University College Cork, Cork, Ireland

    Barry O'Sullivan

  6. University of Pisa, Pisa, Italy

    Dino Pedreschi

Rights and permissions

Copyright information

© 2016 Springer International Publishing AG

About this chapter

Cite this chapter

Grossi, V., Guns, T., Monreale, A., Nanni, M., Nijssen, S. (2016). Partition-Based Clustering Using Constraint Optimization. In: Bessiere, C., De Raedt, L., Kotthoff, L., Nijssen, S., O'Sullivan, B., Pedreschi, D. (eds) Data Mining and Constraint Programming. Lecture Notes in Computer Science(), vol 10101. Springer, Cham. https://doi.org/10.1007/978-3-319-50137-6_11

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 EPUB and 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