Constrained clustering with Minkowski Weighted K-Means

In this paper we introduce the Constrained Minkowski Weighted K-Means. This algorithm calculates cluster specific feature weights that can be interpreted as feature rescaling factors thanks to the use of the Minkowski distance. Here, we use an small amount of labelled data to select a Minkowski exponent and to generate clustering constrains based on pair-wise must-link and cannot-link rules. We validate our new algorithm with a total of 12 datasets, most of which containing features with uniformly distributed noise. We have run the algorithm numerous times in each dataset. These experiments ratify the general superiority of using feature weighting in K-Means, particularly when applying the Minkowski distance. We have also found that the use of constrained clustering rules has little effect on the average proportion of correctly clustered entities. However, constrained clustering does improve considerably the maximum of such proportion.

I. Introduction

The aim of any clustering algorithm is to partition a dataset into groups of homogeneous entities creating a partition . These algorithms are rather popular and they have been used to tackle the most diverse problems, such as: summarizing data [1], detecting anomalous patterns [2], clustering mental tasks [3], clustering malware by its behaviour [4] and etc.