Event Details
Fast and Area-Efficient Hardware Implementation of the K-Means Clustering Algorithm
Presenter: Awos Kanan
Supervisor:
Date: Thu, January 11, 2018
Time: 13:00:00 - 00:00:00
Place: EOW 430
ABSTRACT
ABSTRACT
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 work, a fast and area-efficient hardware implementation of the K-means algorithm for clustering one-dimensional data is proposed. In the proposed implementation, 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/removing one data element to/from a 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 implementation of the algorithm. Experimental results show that the approximation adopted in the proposed architecture results in a more area-efficient hardware implementation while maintaining 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 implementation.