Simple and scalable constrained clustering: a generalized spectral method
We present a simple spectral approach to the well-studied constrained clustering problem. It captures constrained clustering as a generalized eigenvalue problem with graph Laplacians. The algorithm works in nearly-linear time and provides concrete guarantees for the quality of the clusters, at least...
| Main Author: | |
|---|---|
| Format: | Conference item |
| Published: |
Microtome Publishing
2016
|
| _version_ | 1826265710604582912 |
|---|---|
| author | Cucuringu, M |
| author_facet | Cucuringu, M |
| author_sort | Cucuringu, M |
| collection | OXFORD |
| description | We present a simple spectral approach to the well-studied constrained clustering problem. It captures constrained clustering as a generalized eigenvalue problem with graph Laplacians. The algorithm works in nearly-linear time and provides concrete guarantees for the quality of the clusters, at least for the case of 2-way partitioning. In practice this translates to a very fast implementation that consistently outperforms existing spectral approaches both in speed and quality. |
| first_indexed | 2024-03-06T20:27:56Z |
| format | Conference item |
| id | oxford-uuid:3007d1ea-0b98-43a8-83e5-5c60364d60f7 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T20:27:56Z |
| publishDate | 2016 |
| publisher | Microtome Publishing |
| record_format | dspace |
| spelling | oxford-uuid:3007d1ea-0b98-43a8-83e5-5c60364d60f72022-03-26T12:59:06ZSimple and scalable constrained clustering: a generalized spectral methodConference itemhttp://purl.org/coar/resource_type/c_5794uuid:3007d1ea-0b98-43a8-83e5-5c60364d60f7Symplectic Elements at OxfordMicrotome Publishing2016Cucuringu, MWe present a simple spectral approach to the well-studied constrained clustering problem. It captures constrained clustering as a generalized eigenvalue problem with graph Laplacians. The algorithm works in nearly-linear time and provides concrete guarantees for the quality of the clusters, at least for the case of 2-way partitioning. In practice this translates to a very fast implementation that consistently outperforms existing spectral approaches both in speed and quality. |
| spellingShingle | Cucuringu, M Simple and scalable constrained clustering: a generalized spectral method |
| title | Simple and scalable constrained clustering: a generalized spectral method |
| title_full | Simple and scalable constrained clustering: a generalized spectral method |
| title_fullStr | Simple and scalable constrained clustering: a generalized spectral method |
| title_full_unstemmed | Simple and scalable constrained clustering: a generalized spectral method |
| title_short | Simple and scalable constrained clustering: a generalized spectral method |
| title_sort | simple and scalable constrained clustering a generalized spectral method |
| work_keys_str_mv | AT cucuringum simpleandscalableconstrainedclusteringageneralizedspectralmethod |