The GridOPTICS clustering algorithm

Article type: Research Article

Authors: Vágner, Anikó

Affiliations: Faculty of Informatics, University of Debrecen, 26 Kassai Str, Debrecen 4028, Hungary. E-mail: vagner.aniko@inf.unideb.hu

Abstract: The OPTICS algorithm is a hierarchical density-based clustering method. It creates reachability plots to identify all clusters in the point set. Nevertheless, it has limitation, namely it is very slow for large data sets. We introduce the GridOPTICS algorithm, which builds a grid structure to reduce the number of data points, then it applies the OPTICS clustering algorithm on the grid structure. In order to get the clusters, the algorithm uses the reachability plots of the grid structure, then it determines to which cluster the original input points belong. The experimental results show that our new algorithm is faster than the OPTICS, the speed-up can be one or two orders of magnitude or more, which depends mainly on the τ parameter of the GridOPTICS algorithm. At the end of the article, we give some advice to which point set you can apply the GridOPTICS algorithm.

Keywords: Clustering, large data set, OPTICS, grid

DOI: 10.3233/IDA-160856

Journal: Intelligent Data Analysis, vol. 20, no. 5, pp. 1061-1084, 2016