King's College London

Research portal

Spectral clustering using the kNN-MST similarity graph

Research output: Chapter in Book/Report/Conference proceedingConference paper

Original languageEnglish
Title of host publication2016 8th Computer Science and Electronic Engineering Conference, CEEC 2016 - Conference Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages222-227
Number of pages6
ISBN (Print)9781509020508
DOIs
StatePublished - 27 Jan 2017
Event8th Computer Science and Electronic Engineering Conference, CEEC 2016 - Colchester, United Kingdom
Duration: 28 Sep 201630 Sep 2016

Conference

Conference8th Computer Science and Electronic Engineering Conference, CEEC 2016
CountryUnited Kingdom
CityColchester
Period28/09/201630/09/2016

Documents

  • Spectral Clustering Using the kNN-MST_VEENSTRA_Published27June2017_GREEN AAM

    KNNMSTPaper.pdf, 352 KB, application/pdf

    19/05/2017

    Accepted author manuscript

    “© 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted.

King's Authors

Abstract

Spectral clustering is a technique that uses the spectrum of a similarity graph to cluster data. Part of this procedure involves calculating the similarity between data points and creating a similarity graph from the resulting similarity matrix. This is ordinarily achieved by creating a k-nearest neighbour (kNN) graph. In this paper, we show the benefits of using a different similarity graph, namely the union of the kNN graph and the minimum spanning tree of the negated similarity matrix (kNN-MST). We show that this has some distinct advantages on both synthetic and real datasets. Specifically, the clustering accuracy of kNN-MST is less dependent on the choice of k than kNN is.

Download statistics

No data available

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454