Hybrid Partitioning-Density Algorithm for K-Means Clustering of Distributed Data Utilizing OPTICS

Introduction

We live in an era in which the amount of data generated globally in two days can reach 1.8ZB (where a ZB is 10²¹ B) (Chen et al., 2014). The analysis of large and multi-aspect datasets can enable data-driven decision making, thus improving certain business models for companies, allowing for important insights about our society, helping in the invention of new drugs, etc. This data, which needs to be analyzed, is not only generated in large volumes but is originating from heterogeneous sources of data - in terms of volume, velocity, variety (Zikopoulos & Eaton, 2011) and very often from distributed data sources (Takaishi et al., 2014). Analysis of such data may encounter several obstacles, such as hardware, software and network bottlenecks (Chen et al., 2014). Hardware limitations are now often addressed using MapReduce frameworks; however, in the near future, a collection of all the data to be analyzed into one place may become impossible, due to privacy and network capacity issues. For example, a single building in a smart city can generate as much as 275 GB per day, meaning that a small city can generate millions of GB per day (Cisco, 2018). Hence, development is needed for data analysis methods that work on distributed data and that can enable analysis without the need to transfer the data. Distributed processing is a natural method for improving the performance and overall quality of processing for large volumes of data and it is superior to local processing. Nevertheless, in order to make distributed processing effective and practical, we can only operate on raw data using small models; the transfer of raw data is impractical due to transfer overload and violates data privacy on the network (Jagannathan et al., 2006; Sheikhalishahi & Martinelli, 2017; Kantarcioglu & Clifton, 2004). In this article, we address the widely known data mining problem of clustering the distributed data.

Clustering large amounts of data located in distributed data centers have become a challenging issue (Chen et al., 2014; Takaishi et al., 2014; Hashem et al., 2015). Every study [e.g. (Berta et al., 2014; Datta et al., 2006)] of the clustering problem in large datasets has confirmed that the communication cost must not outweigh the potential profit of such processing. One of the possible approaches to the communication-neutral clustering of distributed data involves constructing a global clustering model using small local models received from local clustering statistics (Januzaj et al., 2004). This approach outperforms the classical non-distributed approaches since it avoids the need to download an entire dataset to the central processing unit. This task is not trivial, as it may cause a significant loss of clustering quality and is highly susceptible to uneven data dispersion. However, in addition to the communication cost, the quality of the results must not be significantly worse than locally performed processing, as shown in (Berta et al., 2014; Datta et al., 2006).

The very few approaches that have so far been presented in the literature focus on performance and the quality of the results. Moreover, most approaches focus on partitioning methods, as these are easier to apply to distributed data than density-based algorithms. However, distributed partitioning methods are easily stymied when the expected number of clusters differs from those found on local nodes and do not perform well under conditions of uneven data dispersion. Therefore, we propose a distributed hybrid algorithm that uses the best aspects of both partitioning and density-based approaches. This hybrid approach shows significantly better-quality performance and is much easier to use since it allows for flexibility in specifying the final number of clusters over the entire distributed dataset, which can be adjusted by analyzing the density features of local clustering results.