Instability and cluster stability variance for real clusterings

Robustness is an important concept when dealing with clustering algorithms. While most literature directed to this concept discusses robustness with respect to changes in the given data set, this paper focuses on robustness with respect to changes in the initial conditions. We build on our previous work, where we introduced the concepts of instability and cluster stability variance to measure the robustness in terms of initial conditions. Results from previous work are extended to a much broader class of clusterings, and we introduce the notion of structure-preserving data element. It is proven that removing a structure-preserving unstable data element from the data set increases the robustness of the considered clustering algorithm, as measured by its instability, while the structure of the given data set is conserved. The practical significance of detecting structure-preserving unstable data elements is also discussed.