K-sets+: a Linear-time Clustering Algorithm for Data Points with a Sparse Similarity Measure
In this paper, we first propose a new iterative algorithm, called the K-sets+ algorithm for clustering data points in a semi-metric space, where the distance measure does not necessarily satisfy the triangular inequality. We show that the K-sets+ algorithm converges in a finite number of iterations and it retains the same performance guarantee as the K-sets algorithm for clustering data points in a metric space. We then extend the applicability of the K-sets+ algorithm from data points in a semi-metric space to data points that only have a symmetric similarity measure. Such an extension leads to great reduction of computational complexity. In particular, for an n * n similarity matrix with m nonzero elements in the matrix, the computational complexity of the K-sets+ algorithm is O((Kn + m)I), where I is the number of iterations. The memory complexity to achieve that computational complexity is O(Kn + m). As such, both the computational complexity and the memory complexity are linear in n when the n * n similarity matrix is sparse, i.e., m = O(n). We also conduct various experiments to show the effectiveness of the K-sets+ algorithm by using a synthetic dataset from the stochastic block model and a real network from the WonderNetwork website.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringStochastic Block ModelSimilar Papers 제목 키워드 기반
Synchronization Clustering based on a Linearized Version of Vicsek model
This paper presents a kind of effective synchronization clustering method based on a linearized version of Vicsek model. This method can be represented by an Effective Synchronization Clustering algorithm (ESynC), an Imp…
ClusteringAlmost-linear Time Approximation Algorithm to Euclidean $k$-median and $k$-means
Clustering is one of the staples of data analysis and unsupervised learning. As such, clustering algorithms are often used on massive data sets, and they need to be extremely fast. We focus on the Euclidean $k$-median an…
ClusteringLinear Time Algorithms for k-means with Multi-Swap Local Search
The local search methods have been widely used to solve the clustering problems. In practice, local search algorithms for clustering problems mainly adapt the single-swap strategy, which enables them to handle large-scal…
Linear density-based clustering with a discrete density model
Density-based clustering techniques are used in a wide range of data mining applications. One of their most attractive features con- sists in not making use of prior knowledge of the number of clusters that a dataset con…
ClusteringNatural Hierarchical Cluster Analysis by Nearest Neighbors with Near-Linear Time Complexity
We propose a nearest neighbor based clustering algorithm that results in a naturally defined hierarchy of clusters. In contrast to the agglomerative and divisive hierarchical clustering algorithms, our approach is not de…
Clustering