Optimization Online


Global Solution of the Clustering Problem via Graph Theoretical Approach

Tomas Bajbar(tomas.bajbar***at***gmail.com)
Peter Kirst(peter-kirst***at***web.de)
Mario Merkel(merkel-mario***at***gmx.de)

Abstract: In this article we consider clustering problems which we model as a non-convex continuous minimization problem with the maximum norm representing the distance measure. We then reformulate this continuous problem in light of graph theoretical instances which enables us to construct a bisection algorithm converging to the globally minimal value of the original clustering problem by establishing valid upper and lower bounding procedures. Our numerical results indicate that our method performs well on data sets exhibiting clear cluster-pattern structure even for bigger data instances while still guaranteeing the global optimality of the computed solution. We compare our approach with k-means algorithm and also discuss the limits and challenges of the proposed procedure.

Keywords: clustering problem, global optimization, maximal clique, unsupervised learning

Category 1: Global Optimization (Applications )

Category 2: Applications -- Science and Engineering (Data-Mining )


Download: [PDF]

Entry Submitted: 01/26/2020
Entry Accepted: 01/30/2020
Entry Last Modified: 01/26/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society