Clustering as physically inspired energy minimization

Huiguang Yang, Narendra Ahuja

Research output: Contribution to journalArticle

Abstract

We formulate the task of density based clustering as energy minimization, using both binary/pairwise energy term and unary/data energy term (the latter was largely ignored in previous clustering methods). Binary energy is defined in terms of inhomogeneity in local point density. While most previous methods use binary/pairwise energy only, the unary/data energy can represent the natural tendency of a given point belonging to a given cluster, which is also crucial for the clustering. Since our energy is expressed as the sum of a unary (data) term and a binary (pairwise or smoothness) term, we can thus make a perfect analogy with the energy model used in vision and borrow everything (such as the optimization algorithms) from vision field to clustering under this mapping. This correspondence provides an entirely new view point in handling the clustering problem, and in fact many mature methods and algorithms are already provided in the vision field and can be adopted by the clustering field readily. During our energy optimization, a sequence of energy minima are found to recursively partition the points, and thus find a hierarchical embedding of clusters that are increasingly homogeneous in density. Disjoint clusters with the same density are identified separately. Our clustering method is totally unsupervised (which is superior to most existing methods, as those listed below). It does not need any user input parameters (say number of segments, any bandwidth parameter, cutoff distance/scale, etc.), except one can specify the homogeneity criterion — the degree of acceptable fluctuation in density within a cluster (which is target-related), or let it be specified automatically in a hierarchical way. We conduct experiments on both synthetic datasets and real-image tasks. Experimental results on synthetic datasets show that our method is able to handle clusters of different shapes, sizes and densities. We present the performance of our approach using the commonly used energy optimization algorithms from vision such as ICM, LBP, Graph-cut, Mean field theory algorithm, as well as the integer programming algorithm. We also contrast our performance with several other commonly used clustering algorithms, such as k-means, fussy c-means, DBSCAN, as well as a recent state-of-the-art clustering method as reported in [40]. Our experiments on real-image tasks further validate the performance of the method. In addition, we show that the family of commonly used spectral, graph clustering algorithms (such as Normalized-cut) uses only the binary energy term while ignoring the unary energy term; therefore, their energy model is incomplete compared with ours.

LanguageEnglish (US)
Pages265-280
Number of pages16
JournalPattern Recognition
Volume86
DOIs
StatePublished - Feb 1 2019

Fingerprint

Clustering algorithms
Mean field theory
Integer programming
Experiments
Bandwidth

Keywords

  • Connected component analysis
  • Energy minimization
  • Image segmentation
  • Integer programming
  • Ising model
  • Local density
  • Normalized-cut
  • Statistical physics
  • Unary/data energy
  • Unsupervised/hierarchical clustering

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence

Cite this

Clustering as physically inspired energy minimization. / Yang, Huiguang; Ahuja, Narendra.

In: Pattern Recognition, Vol. 86, 01.02.2019, p. 265-280.

Research output: Contribution to journalArticle

@article{560e9e9b943743f9828386a5197c7977,
title = "Clustering as physically inspired energy minimization",
abstract = "We formulate the task of density based clustering as energy minimization, using both binary/pairwise energy term and unary/data energy term (the latter was largely ignored in previous clustering methods). Binary energy is defined in terms of inhomogeneity in local point density. While most previous methods use binary/pairwise energy only, the unary/data energy can represent the natural tendency of a given point belonging to a given cluster, which is also crucial for the clustering. Since our energy is expressed as the sum of a unary (data) term and a binary (pairwise or smoothness) term, we can thus make a perfect analogy with the energy model used in vision and borrow everything (such as the optimization algorithms) from vision field to clustering under this mapping. This correspondence provides an entirely new view point in handling the clustering problem, and in fact many mature methods and algorithms are already provided in the vision field and can be adopted by the clustering field readily. During our energy optimization, a sequence of energy minima are found to recursively partition the points, and thus find a hierarchical embedding of clusters that are increasingly homogeneous in density. Disjoint clusters with the same density are identified separately. Our clustering method is totally unsupervised (which is superior to most existing methods, as those listed below). It does not need any user input parameters (say number of segments, any bandwidth parameter, cutoff distance/scale, etc.), except one can specify the homogeneity criterion — the degree of acceptable fluctuation in density within a cluster (which is target-related), or let it be specified automatically in a hierarchical way. We conduct experiments on both synthetic datasets and real-image tasks. Experimental results on synthetic datasets show that our method is able to handle clusters of different shapes, sizes and densities. We present the performance of our approach using the commonly used energy optimization algorithms from vision such as ICM, LBP, Graph-cut, Mean field theory algorithm, as well as the integer programming algorithm. We also contrast our performance with several other commonly used clustering algorithms, such as k-means, fussy c-means, DBSCAN, as well as a recent state-of-the-art clustering method as reported in [40]. Our experiments on real-image tasks further validate the performance of the method. In addition, we show that the family of commonly used spectral, graph clustering algorithms (such as Normalized-cut) uses only the binary energy term while ignoring the unary energy term; therefore, their energy model is incomplete compared with ours.",
keywords = "Connected component analysis, Energy minimization, Image segmentation, Integer programming, Ising model, Local density, Normalized-cut, Statistical physics, Unary/data energy, Unsupervised/hierarchical clustering",
author = "Huiguang Yang and Narendra Ahuja",
year = "2019",
month = "2",
day = "1",
doi = "10.1016/j.patcog.2018.09.008",
language = "English (US)",
volume = "86",
pages = "265--280",
journal = "Pattern Recognition",
issn = "0031-3203",
publisher = "Elsevier Limited",

}

TY - JOUR

T1 - Clustering as physically inspired energy minimization

AU - Yang, Huiguang

AU - Ahuja, Narendra

PY - 2019/2/1

Y1 - 2019/2/1

N2 - We formulate the task of density based clustering as energy minimization, using both binary/pairwise energy term and unary/data energy term (the latter was largely ignored in previous clustering methods). Binary energy is defined in terms of inhomogeneity in local point density. While most previous methods use binary/pairwise energy only, the unary/data energy can represent the natural tendency of a given point belonging to a given cluster, which is also crucial for the clustering. Since our energy is expressed as the sum of a unary (data) term and a binary (pairwise or smoothness) term, we can thus make a perfect analogy with the energy model used in vision and borrow everything (such as the optimization algorithms) from vision field to clustering under this mapping. This correspondence provides an entirely new view point in handling the clustering problem, and in fact many mature methods and algorithms are already provided in the vision field and can be adopted by the clustering field readily. During our energy optimization, a sequence of energy minima are found to recursively partition the points, and thus find a hierarchical embedding of clusters that are increasingly homogeneous in density. Disjoint clusters with the same density are identified separately. Our clustering method is totally unsupervised (which is superior to most existing methods, as those listed below). It does not need any user input parameters (say number of segments, any bandwidth parameter, cutoff distance/scale, etc.), except one can specify the homogeneity criterion — the degree of acceptable fluctuation in density within a cluster (which is target-related), or let it be specified automatically in a hierarchical way. We conduct experiments on both synthetic datasets and real-image tasks. Experimental results on synthetic datasets show that our method is able to handle clusters of different shapes, sizes and densities. We present the performance of our approach using the commonly used energy optimization algorithms from vision such as ICM, LBP, Graph-cut, Mean field theory algorithm, as well as the integer programming algorithm. We also contrast our performance with several other commonly used clustering algorithms, such as k-means, fussy c-means, DBSCAN, as well as a recent state-of-the-art clustering method as reported in [40]. Our experiments on real-image tasks further validate the performance of the method. In addition, we show that the family of commonly used spectral, graph clustering algorithms (such as Normalized-cut) uses only the binary energy term while ignoring the unary energy term; therefore, their energy model is incomplete compared with ours.

AB - We formulate the task of density based clustering as energy minimization, using both binary/pairwise energy term and unary/data energy term (the latter was largely ignored in previous clustering methods). Binary energy is defined in terms of inhomogeneity in local point density. While most previous methods use binary/pairwise energy only, the unary/data energy can represent the natural tendency of a given point belonging to a given cluster, which is also crucial for the clustering. Since our energy is expressed as the sum of a unary (data) term and a binary (pairwise or smoothness) term, we can thus make a perfect analogy with the energy model used in vision and borrow everything (such as the optimization algorithms) from vision field to clustering under this mapping. This correspondence provides an entirely new view point in handling the clustering problem, and in fact many mature methods and algorithms are already provided in the vision field and can be adopted by the clustering field readily. During our energy optimization, a sequence of energy minima are found to recursively partition the points, and thus find a hierarchical embedding of clusters that are increasingly homogeneous in density. Disjoint clusters with the same density are identified separately. Our clustering method is totally unsupervised (which is superior to most existing methods, as those listed below). It does not need any user input parameters (say number of segments, any bandwidth parameter, cutoff distance/scale, etc.), except one can specify the homogeneity criterion — the degree of acceptable fluctuation in density within a cluster (which is target-related), or let it be specified automatically in a hierarchical way. We conduct experiments on both synthetic datasets and real-image tasks. Experimental results on synthetic datasets show that our method is able to handle clusters of different shapes, sizes and densities. We present the performance of our approach using the commonly used energy optimization algorithms from vision such as ICM, LBP, Graph-cut, Mean field theory algorithm, as well as the integer programming algorithm. We also contrast our performance with several other commonly used clustering algorithms, such as k-means, fussy c-means, DBSCAN, as well as a recent state-of-the-art clustering method as reported in [40]. Our experiments on real-image tasks further validate the performance of the method. In addition, we show that the family of commonly used spectral, graph clustering algorithms (such as Normalized-cut) uses only the binary energy term while ignoring the unary energy term; therefore, their energy model is incomplete compared with ours.

KW - Connected component analysis

KW - Energy minimization

KW - Image segmentation

KW - Integer programming

KW - Ising model

KW - Local density

KW - Normalized-cut

KW - Statistical physics

KW - Unary/data energy

KW - Unsupervised/hierarchical clustering

UR - http://www.scopus.com/inward/record.url?scp=85054093472&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85054093472&partnerID=8YFLogxK

U2 - 10.1016/j.patcog.2018.09.008

DO - 10.1016/j.patcog.2018.09.008

M3 - Article

VL - 86

SP - 265

EP - 280

JO - Pattern Recognition

T2 - Pattern Recognition

JF - Pattern Recognition

SN - 0031-3203

ER -