A Novel Architecture for k-means Clustering Algorithm

Abstract

Technological advancements in todays information age has helped the researchers to capture digital footprints of humans with regards to their daily activities. These logs of information posses valuable information for the data analytics who process it to find hidden pattern and unique behavior. Among the many algorithms k-means clustering is one of the very popular and widely used algorithm in the field of data mining and machine learning. k-means provides natural segments of dataset provided for clustering. It uses proximity to assign data points to a specific cluster, here the criteria of allocation is the minimum distance from the cluster center. Unfortunately, the rate of data growth has not been met by the speed of the algorithms. A number of hardware based solutions have been proposed to increase the processing power of different algorithms. In this paper, we present a novel algorithm for k-mean clustering which exploits the data redundancy occurring in the dataset. The proposed algorithm performs computations for the available unique items in the dataset and uses its frequency to finalize the results. Furthermore, FPGA based hardware architecture for the proposed algorithm is also presented in the paper. The performance of the proposed algorithm and its hardware implementation is evaluated using execution time, speedup and throughput. The proposed architecture provides speedup of 23 times and 2600 times against sequential hardware architecture and software implementation with a very small area requirement.

Keywords Data mining, Data redundancy, FPGA based hardware architecture