Optimization Online


Clustering via Minimum Volume Ellipsoids

Romy Shioda (rshioda***at***uwaterloo.ca)
Levent Tuncel (ltuncel***at***math.uwaterloo.ca)

Abstract: We propose minimum volume ellipsoids (MVE) clustering as an alternate clustering technique to k-means clustering for Gaussian data points and explore its value and practicality. MVE clustering allocates data points into clusters that minimizes the total volumes of each cluster's covering ellipsoids. Motivations for this approach include its scale-invariance, its ability to handle asymmetric and unequal clusters, and our ability to formulate it as a mixed-integer semidefinite programming problem that can be solved to global optimality. We present some preliminary empirical results that illustrate MVE clustering as an appropriate method for clustering data from mixtures of Gaussian distributions and compare its performance with the k-means clustering algorithm.


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

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Research Report CORR 2005--12, Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, Canada, May 2005.

Download: [Compressed Postscript][PDF]

Entry Submitted: 06/01/2005
Entry Accepted: 06/01/2005
Entry Last Modified: 06/01/2005

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 Programming Society