Аннотация:

Clustering is one of the basic tasks in unsupervised machine learning and data mining. The clustering process consists of partitioning data items from a dataset so that similar items are grouped into non-overlapping clusters. The so-called center-based clustering approach remains one of the most popular ones to formalize the clustering problem. In this case, partitioning data items into clusters performed by identifying the fixed number of so-called representatives (centers) of clusters. Then, clusters are formed by assigning each data item to the closest center.

The $k$-means (minimum sum-of-squares) and $k$-medoids (minimum sum-of-stars) problems are the most well-known center-based clustering problems and perhaps the most popular clustering models at all. Despite their simplicity and popularity, $k$-medoids and $k$-means algorithms are both suitable for clustering relatively small datasets due to their high-computational complexity. The most time-consuming operation in these algorithms is the calculation of distances (measures of dissimilarity) between data items.  To make the complex and consuming mathematical computations of such type, recently the Neural Processing Unit (NPU) was designed and optimized as a highly specialized processor to carry out AI challengers.

We proposed and developed special variants of well-known $k$-medoids and $k$-means algorithms accelerated by NPU and parallel implementation. The algorithms realized outperform not only the CPU but also the GPU in terms of performance, effectiveness and efficiency, which is proved by computational simulations.