CE3: A three-way clustering method based on mathematical morphology

摘要

Many existing clustering methods produce clusters with clear and sharp boundaries, which does not truly reflect the fact that a cluster may not necessarily have a well-defined boundary in many real world situations. In this paper, by combining ideas of erosion and dilation from mathematical morphology and principles of three-way decision, we propose a framework of a contraction-and-expansion based three-way clustering called CE3. A three-way cluster is defined by a nested pair of sets called the core and the support of the cluster, respectively. A stronger relationship holds between objects in the core and a weaker relationship holds between objects in the support. Given a cluster obtained from a hard clustering method, CE3 uses a contraction operation to shrink the cluster into the core of a three-way cluster and uses an expansion operation to enlarge the cluster into the support. The difference between the support and the core is called the fringe region, representing an unsharp boundary of a cluster. Within the CE3 framework, we can define different types of contraction and expansion operations. We can apply the CE3 framework on the top of any existing clustering method. As examples for demonstration, we introduce a pair of neighbor-based contraction and expansion operations and apply the CE3 framework on the top of k-means and spectral clustering, respectively. We use one synthetic data set, five UCI data sets, and three USPS data sets to evaluate experimentally the performance of CE3. The results show that CE3 is in fact effective in revealing cluster structures.