King's College London

Research portal

Spectral clustering using the kNN-MST similarity graph

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

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


Conference8th Computer Science and Electronic Engineering Conference, CEEC 2016
Country/TerritoryUnited Kingdom


  • Spectral Clustering Using the kNN-MST_VEENSTRA_Published27June2017_GREEN AAM

    KNNMSTPaper.pdf, 353 KB, application/pdf

    Uploaded date:19 May 2017

    Version: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


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

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