A Combinatorial Approach to Assess the Separability of Clusters

Separability of clusters is an issue that arises in many different areas, and is often used in a rather vague and subjective manner. We introduce a combinatorial notion of interiority to derive a global view on separability of a set of entities. We develop this approach further to evaluate the overall separability of a partition in the context of cluster analysis. Our approach captures combinatorial and geometrical aspects of data and provides, in addition to numerical evaluations, graphical representations particularly useful when data are not easily visualized. We illustrate the methodology on some real and simulated datasets.