Three-way clustering: Foundations, survey and challenges

Clustering, as an unsupervised data mining technique, allows us to classify similar objects into the same cluster according to certain criteria. It helps us identify patterns between objects, reveal the associations between objects, and discover hidden structures. Traditional two-way clustering (2W clustering) algorithms represent one cluster by one set and only two types of relationships are considered between a sample and a cluster, namely, belonging to and not belonging to. Two-way decision is not always feasible especially in situations that are characterized by uncertainty and lack of information. Guided by the principle of three-way decision (3WD) as thinking in threes, three-way clustering (3W clustering) addresses the information uncertainty problem using core and the fringe regions to character a cluster. The universe is split into three sections by these two sets, which capture three kinds of relationships between objects and a cluster, namely, belonging to, partially belonging to, and not belonging-to. Compared with 2W clustering methods, 3W clustering incorporates the fringe region to describe the uncertain relationship between objects and clusters, which provides more information about the clustering structure. This survey points out the historical developments of three-way clustering and makes an overview of the achievements in the field of three-way clustering. In addition, to reap a clearer grasp of the development and research significance of three-way clustering, we divide the existing three-way clustering approaches into two categories and present the bibliometric analysis of related approaches. Finally, we point out some challenges and future research topics in three-way clustering. It is hoped that this review can serve as a reference and provide convenience for scholars and practitioners in the field of three-way clustering.