Using Micro-Processor Vector Instructions to Optimize Unsupervised Machine Learning K-Means Algorithm
Jose Somarribas, Adrian Loteanu · 2020
The K-Means clustering algorithm is a widely used unsupervised learning technique for data analysis that is still relevant decades after it was originally published. The algorithm is capable of splitting a given multi dimensional input of data points into a given number of clusters based on a measure of proximity. The iterative algorithm creates k partitions by finding their cluster centers and then assigning each of the points to the nearest center from a given input data set. This method of unsupervised clustering has become widely utilized in applications like data mining and statistical data analysis were large data sets are processed in order to extract key information about trends in the data. Apache SPARK is one of the most used big data and data analytics frameworks and it includes an implementation of the K-Means algorithm. In this work we characterize the SPARK implementation of K-Means, analyze its performance bottlenecks and suggest improvements that can help it achieve up to 33x higher throughput by using vector capabilities available on many modern server processors.