English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Spectral clustering is one of the most popular clustering algorithms that hasstood the test of time. It is simple to describe, can be implemented usingstandard linear algebra, and often finds better clusters than traditionalclustering algorithms like $k$-means and $k$-centers. The foundationalalgorithm for two-way spectral clustering, by Shi and Malik, creates ageometric graph from data and finds a spectral cut of the graph.  In modern machine learning, many data sets are modeled as a large number ofpoints drawn from a probability density function. Little is known about whenspectral clustering works in this setting -- and when it doesn't. Pastresearchers justified spectral clustering by appealing to the graph Cheegerinequality (which states that the spectral cut of a graph approximates the``Normalized Cut''), but this justification is known to break down on largedata sets.  We provide theoretically-informed intuition about spectral clustering onlarge data sets drawn from probability densities, by proving when a continuousform of spectral clustering considered by past researchers (the unweightedspectral cut of a probability density) finds good clusters of the underlyingdensity itself. Our work suggests that Shi-Malik spectral clustering works wellon data drawn from mixtures of Laplace distributions, and works poorly on datadrawn from certain other densities, such as a density we call the `square-roottrough'.  Our core theorem proves that weighted spectral cuts have low weightedisoperimetry for all probability densities. Our key tool is a new Cheeger-Buserinequality for all probability densities, including discontinuous ones.

Spectral Clustering on Large Datasets: When Does it Work? Theory from Continuous Clustering and Density Cheeger-Buser