Digitala Vetenskapliga Arkivet

Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Modern multiway spectral partitioning algorithms
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
2025 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Moderna spektrala partitioneringsalgoritmer (Swedish)
Abstract [en]

Spectral clustering, as a particular method in unsupervised learning, has been successfully applied in many fields due to its ability to capture complicated structures in data through graph-based representations. Traditionally, spectral clustering relies on the Kmeans algorithm to post-process the eigenvectors of the standard graph Laplacian. In this thesis, we investigate and compare several advanced clustering algorithms applied to the spectral embeddings derived from both the standard Laplacian and the generalized non-linear graph p-Laplacian. The first algorithm uses the column-pivoted QR (CPQR) factorization to select representative coordinate directions encoded in the eigenvectors of the graph Laplacian. The second constructs an indicator matrix from the eigenvector matrix by solving a minimization problem. These methods are designed to address limitations of the conventional Kmeans approach, particularly its sensitivity to initialization and its poor performance on non-convex structures. The theoretical background of these algorithms are briefly explained, and we evaluate these methods across synthetic and real-world benchmark datasets, analyzing clustering quality and computational complexity. The results demonstrate that these algorithms outperforms the standard Kmeans algorithm for standard graph Laplacian. Applying them to the graph p-Laplacian can significantly improve clustering performance in datasets with non-convex structures, but the improvement over Kmeans becomes minimal. Furthermore, it suffers from a much higher computational cost due to the procedure of solving a nonlinear eigenvalue problem.

Abstract [sv]

Spektral klustring, som är en specifik metod inom oövervakad inlärning, har framgångsrikt tillämpats inom många områden tack vare dess förmåga att fånga komplexa strukturer i data genom grafbaserade representationer. Traditionellt förlitar sig spektral klustring på Kmeans-algoritmen för att efterbehandla egenvektorerna från den standardiserade graf-Laplacianen. I detta projekt undersöker och jämför vi flera avancerade klustringsalgoritmer som tillämpas på spektrala inbäddningar härledda både från standard-Laplacianen och från den generaliserade icke-linjära graf-p-Laplacianen. Den första algoritmen använder kolumnpivoterad QR-faktorisering (CPQR) för att välja representativa koordinatriktningar som kodas i egenvektorerna för graf-Laplacianen. Den andra algoritmen konstruerar en indikator-matris från egenvektormatrisen genom att lösa ett minimeringsproblem. Dessa metoder är utformade för att hantera begränsningarna hos den konventionella Kmeans-metoden, särskilt dess känslighet för initialisering och dess svaga prestanda på icke-konvexa strukturer. Den teoretiska bakgrunden till dessa algoritmer förklaras kortfattat, och vi utvärderar metoderna på syntetiska och verkliga benchmark-dataset, med fokus på klustringskvalitet och beräkningskomplexitet. Resultaten visar att dessa algoritmer överträffar den traditionella Kmeans-metoden när de används med standard-Laplacianen. Att tillämpa dem på graf-p-Laplacianen kan förbättra klustringsprestandan avsevärt i dataset med icke-konvexa strukturer, men förbättringen jämfört med Kmeans är då marginell. Dessutom drabbas metoden av en betydligt högre beräkningskostnad på grund av behovet av att lösa ett icke-linjärt egenvärdesproblem.

Place, publisher, year, edition, pages
2025. , p. 38
Series
TRITA-SCI-GRU ; 2025:355
National Category
Other Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-368732OAI: oai:DiVA.org:kth-368732DiVA, id: diva2:1990571
Subject / course
Scientific Computing
Educational program
Master of Science - Applied and Computational Mathematics
Supervisors
Examiners
Available from: 2025-08-20 Created: 2025-08-20 Last updated: 2025-08-20Bibliographically approved

Open Access in DiVA

fulltext(1094 kB)115 downloads
File information
File name FULLTEXT01.pdfFile size 1094 kBChecksum SHA-512
a20e300ca0249f8c0e7e464a164a3bc7c6f85b4222db95f30550f431f8d943258b754d545bff65ab897637c3afd514ed34041a73d051c599a655b6309891df60
Type fulltextMimetype application/pdf

By organisation
Mathematics (Div.)
Other Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 118 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 1245 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf