Not Logged In

Clustering High Dimensional Data: A Graph-Based Relaxed Optimization Approach

Clustering is one of the most studied data mining tasks. In this paper we propose a novel graph-based algorithm "GBR", whose formulation involves relaxing the global optimization of the well known clustering algorithm, Normalized Cuts. This relaxed objective has an analytical solution (unlike the iterative methods used by many other graph- based approaches) and yields encouraging cluster results for high dimensional data. Experiments on synthetic and real data sets show that our GBR produces high quality clusters. Our key contributions are: (1) an efficient non-iterative analytical solution to solve the global clustering task; (2) a very simple implementation using existing optimization packages; and (3) an effective clustering algorithm requiring less computation time than many other methods.

Citation

C. Lee, O. Zaiane, H. Park, J. Huang, R. Greiner. "Clustering High Dimensional Data: A Graph-Based Relaxed Optimization Approach". Information Sciences, 178(23), pp 4501-4511, May 2008.

Keywords: machine learning, clustering
Category: In Journal

BibTeX

@article{Lee+al:08,
  author = {Chi-Hoon Lee and Osmar R. Zaiane and Ho-Hyun Park and Jiayuan Huang
    and Russ Greiner},
  title = {Clustering High Dimensional Data: A Graph-Based Relaxed Optimization
    Approach},
  Volume = "178",
  Number = "23",
  Pages = {4501-4511},
  journal = {Information Sciences},
  year = 2008,
}

Last Updated: October 31, 2019
Submitted by Sabina P

University of Alberta Logo AICML Logo