Journal article
EFFICIENT APPROXIMATION ALGORITHMS FOR PAIRWISE DATA CLUSTERING AND APPLICATIONS
International journal of computational geometry & applications, Vol.14(1n02), pp.85-104
04/2004
DOI: 10.1142/S0218195904001378
Abstract
Data clustering is an important theoretical topic and a sharp tool for various
applications. It is a task frequently arising in geometric computing. The main
objective of data clustering is to partition a given data set into clusters
such that the data items within the same cluster are "more" similar to each
other with respect to certain measures. In this paper, we study the pairwise
data clustering problem with pairwise similarity/dissimilarity measures that
need not satisfy the triangle inequality. By using a criterion, called the
minimum normalized cut, we model the general pairwise data clustering
problem as a graph partition problem. The graph partition problem based on
minimizing the normalized cut is known to be NP-hard. For an undirected
weighted graph of n vertices, we present a
((4+o(1))Inn)-approximation polynomial time algorithm for the
minimum normalized cut problem; this is the first provably good approximation
polynomial time algorithm for the problem. We also give a more efficient
algorithm for this problem by sacrificing the approximation ratio slightly.
Further, our scheme achieves a ((2+o(1))Inn)-approximation
polynomial time algorithm for computing the sparsest cuts in edge-weighted
and vertex-weighted undirected graphs, improving the previously best known
approximation ratio by a constant factor. Some applications and implementation
work of our approximation normalized cut algorithms are also discussed.
Details
- Title: Subtitle
- EFFICIENT APPROXIMATION ALGORITHMS FOR PAIRWISE DATA CLUSTERING AND APPLICATIONS
- Creators
- XIAODONG WU - University of Texas–Pan AmericanDANNY Z Chen - University of Notre DameJAMES J Mason - University of Notre DameSTEVEN R Schmid - University of Notre Dame
- Resource Type
- Journal article
- Publication Details
- International journal of computational geometry & applications, Vol.14(1n02), pp.85-104
- Publisher
- World Scientific Publishing Company
- DOI
- 10.1142/S0218195904001378
- ISSN
- 0218-1959
- eISSN
- 1793-6357
- Language
- English
- Date published
- 04/2004
- Academic Unit
- Electrical and Computer Engineering; Radiation Oncology; The Iowa Institute for Biomedical Imaging
- Record Identifier
- 9984197451502771
Metrics
8 Record Views