Central partition for a partition-distance and strong pattern graph

Abstract

When several clustering algorithms are applied to a dataset E or the same algorithm with different parameters, we get several different partitions of the dataset. In this paper we consider the problem of finding a consensus partition between the set of these partitions. This consensus partition, called central partition, minimises the average number of disagreements between all of the partitions and has been considered for instance in [14, 5] in a different context from ours. We consider it in the context of partition-distance defined in [7]. We focus our attention in two particular distance functions between partitions and then do an experimental comparison between the two corresponding central partitions. In addition, by using the concept of strong patterns (maximal subset of elements that are always clustered together in all partitions), we define a new graph where the nodes are the strong patterns. This graph contains essentially the same information as the partition graph corresponding to the set E defined in [7], but is much simpler as the number of strong patterns is expected to be much smaller than the cardinal of E. Then, some properties of this new graph are proved.