Parallel Iterative Mistake Minimization (IMM) clustering algorithm for shared-memory systems

This paper addresses the problem of deriving explanations in the form of compact decision trees for cluster assignments made by the well-known K-means method. It introduces two versions of the Iterative Mistake Minimization (IMM) algorithm, both parallelized using the OpenMP standard. The first version mirrors the reference implementation by parallelizing the outer loop that iterates over the training set's features. The second version employs OpenMP nested parallelism to additionally parallelize the process of finding the optimal cut for a given feature. The algorithms were tested on nine synthetic datasets using single 48-core nodes of a compute cluster. The results indicate that the approach utilizing nested parallelism significantly surpasses the other two versions in performance. Depending on the dimension of the feature space, it is 1.3 to 15 times faster than our re-implementation of the reference version. Its parallel efficiency relative to the single-threaded variant ranges from 54% to 78%.