Linearized cluster assignment via spectral ordering

摘要: Spectral clustering uses eigenvectors of the Laplacian similarity matrix. They are most conveniently applied to 2-way problems. When applying multi-way clustering, either spectral is recursively or an embedding space done and some other methods used cluster points. Here we propose study a K-way assignment method. The method transforms problem find valleys peaks 1-D quantity called crossing, which measures symmetric overlap across cut point along linear ordering data can determine K clusters in one shot split current into several smaller ones. We show that based on distance sensitive objective has continuous solution eigenvector Laplacian, showing close relationship between ordering. relies connectivity matrix constructed as truncated expansion matrix, useful for revealing structure. newsgroups illustrate introduced concepts; experiments it outperforms recursive standard K-means clustering.