查看文章

K-means clustering algorithm aims to partition data elements of an input dataset into K clusters in which each data element belongs to the cluster with the nearest centroid. The algorithm may take long time to process large datasets. In this paper, a fast and area-efficient hardware implementation of the K-means algorithm for clustering one-dimensional data is proposed. In the proposed design, centroids update equations are rewritten to calculate the new centroids recursively. New centroids are calculated using the current centroid value and the change in this value that results from adding or removing one data element to or from the cluster. In the new equations, the division operation appears only in the term that represents this change. The proposed design approximates only the value of this change by replacing the slow and area-consuming division operation with a shift operation. New centroids are also calculated without the need to accumulate the summation of all data elements in each cluster, as in the conventional accumulation-based design of the algorithm. Experimental results show that the approximation adopted in the proposed design results in a more area-efficient hardware implementation without affecting the quality of clustering results. Experimental results also show that the algorithm converges faster using less number of iterations as a result of continuously updating clusters centroids compared to the general update approach used in the conventional design.