Beyond pairwise clustering
Publikation: Bidrag til tidsskrift › Konferenceartikel › Forskning › fagfællebedømt
We consider the problem of clustering in domains where the affinity relations are not dyadic (pairwise), but rather triadic, tetradic or higher. The problem is an instance of the hypergraph partitioning problem. We propose a two-step algorithm for solving this problem. In the first step we use a novel scheme to approximate the hypergraph using a weighted graph. In the second step a spectral partitioning algorithm is used to partition the vertices of this graph. The algorithm is capable of handling hyperedges of all orders including order two, thus incorporating information of all orders simultaneously. We present a theoretical analysis that relates our algorithm to an existing hypergraph partitioning algorithm and explain the reasons for its superior performance. We report the performance of our algorithm on a variety of computer vision problems and compare it to several existing hypergraph partitioning algorithms.
Originalsprog | Engelsk |
---|---|
Tidsskrift | Proceedings - 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2005 |
Sider (fra-til) | 838-845 |
Antal sider | 8 |
DOI | |
Status | Udgivet - 2005 |
Eksternt udgivet | Ja |
Begivenhed | 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2005 - San Diego, CA, USA Varighed: 20 jun. 2005 → 25 jun. 2005 |
Konference
Konference | 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2005 |
---|---|
Land | USA |
By | San Diego, CA |
Periode | 20/06/2005 → 25/06/2005 |
Sponsor | IEEE Computer Society |
ID: 302055002