Convex Programming Based Spectral Clustering
Clustering is a fundamental task in data analysis, and spectral clustering has been recognized as a promising approach to it. Given a graph describing the relationship between data, spectral clustering explores the underlying cluster structure in two stages. The first stage embeds the nodes of the graph in real space, and the second stage groups the embedded nodes into several clusters. The use of the $k$-means method in the grouping stage is currently standard practice. We present a spectral clustering algorithm that uses convex programming in the grouping stage and study how well it works. This algorithm is designed based on the following observation. If a graph is well-clustered, then the nodes with the largest degree in each cluster can be found by computing an enclosing ellipsoid of the nodes embedded in real space, and the clusters can be identified by using those nodes. We show that, for well-clustered graphs, the algorithm can find clusters of nodes with minimal conductance. We also give an experimental assessment of the algorithm's performance.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Spectral Clustering in Convex and Constrained Settings
Spectral clustering methods have gained widespread recognition for their effectiveness in clustering high-dimensional data. Among these techniques, constrained spectral clustering has emerged as a prominent approach, dem…
ClusteringConvex Sparse Spectral Clustering: Single-view to Multi-view
Spectral Clustering (SC) is one of the most widely used methods for data clustering. It first finds a low-dimensonal embedding $U$ of data by computing the eigenvectors of the normalized Laplacian matrix, and then perfor…
ClusteringTree-Guided $L_1$-Convex Clustering
Convex clustering is a modern clustering framework that guarantees globally optimal solutions and performs comparably to other advanced clustering methods. However, obtaining a complete dendrogram (clusterpath) for large…
ClusteringComputational EfficiencyDistributed ComputingThe SpectACl of Nonconvex Clustering: A Spectral Approach to Density-Based Clustering
When it comes to clustering nonconvex shapes, two paradigms are used to find the most suitable clustering: minimum cut and maximum density. The most popular algorithms incorporating these paradigms are Spectral Clusterin…
ClusteringClustering Algorithms EvaluationCertifying Global Optimality of Graph Cuts via Semidefinite Relaxation: A Performance Guarantee for Spectral Clustering
Spectral clustering has become one of the most widely used clustering techniques when the structure of the individual clusters is non-convex or highly anisotropic. Yet, despite its immense popularity, there exists fairly…
Clustering