A Fast Partitional Clustering Algorithm based on Nearest Neighbours Heuristics

Debasis Ganguly

doi:10.1016/j.patrec.2018.07.017

A Fast Partitional Clustering Algorithm based on Nearest Neighbours Heuristics

2018-09-01

6

PRE

AI

D

Debasis Ganguly *

DOI：10.1016/j.patrec.2018.07.017

原文链接

原文求助

摘要

En 中文

K-means, along with its several other variants, is the most widely used family of partitional clustering algorithms. Generally speaking, this family of algorithm starts by initializing a number of data points as cluster centres, and then iteratively refines these cluster centres based on the current partition of the dataset. Given a set of cluster centres, inducing the partition over the dataset involves finding the nearest (or most similar) cluster centre for each data point, which is an O(NK) operation, N and K being the number of data points and the number of clusters, respectively. In our proposed approach, we avoid the explicit computation of these distances for the case of sparse vectors, e.g. documents, by utilizing a fundamental operation, namely TOP (x), which gives a list of the top most similar vectors with respect to the vector x. A standard way to store sparse vectors and retrieve the top most similar ones given a query vector, is with the help of the inverted list data structure. In our proposed method, we use the TOP (x) function to first select cluster centres that are likely to be dissimilar to each other. Secondly, to obtain the partition during each iteration of K-means, we avoid the explicit computation of the pairwise similarities between the centroid and the non-centroid vectors. Thirdly, we avoid recomputation of the cluster centroids by adopting a centrality based heuristic. We demonstrate the effectiveness of our proposed algorithm on TREC-2011 Microblog dataset, a large collection of about 14 M tweets. Our experiments demonstrate that our proposed method is about 35x faster and produces more effective clusters in comparison to the standard K-means algorithm. (c) 2018 Elsevier B.V. All rights reserved.

Keyword:

Tweet clustering

Scalable K-means

Inverted index

A Fast Partitional Clustering Algorithm based on Nearest Neighbours Heuristics

摘要

AI总结

期刊

机构

引用论文