Comparing Partitions by Subset Similarities

摘要

Comparing partitions is an important issue in classification and clustering when comparing results from different methods, parameters, or initializations. A well-established method for comparing partitions is the Rand index but this index is suitable for crisp partitions only. Recently, the Hiillermeier-Rifqi index was introduced which is a generalization of the Rand index to fuzzy partitions. In this paper we introduce a new approach to comparing partitions based on the similarities of their clusters in the sense of set similarity. All three indices, Rand, Hiillermeier-Rifqi, and subset similarity, are reflexive, invariant against row permutations, and invariant against additional empty subsets. The subset similarity index is not a generalization of the Rand index, but produces similar values. Subset similarity yields more intuitive similarities than Hiillermeier-Rifqi when comparing crisp and fuzzy partitions, and yields smoother nonlinear transitions. Finally, the subset similarity index has a lower computational complexity than the Hiillermeier-Rifqi index for large numbers of objects.