Abstract:Traditional clustering algorithms can split the dataset into different clusters, whereas these clusters are usually difficult to explain. Iterative mistake minimization (IMM) is a common explainable clustering algorithm, which constructs a threshold tree from a single feature, and each cluster can be explained by feature-threshold pairs on the path from the root node to the leaf node. However, the threshold tree only considers the feature-threshold pair with the fewest errors when dividing the data in each round, and this greedy method is easy to lead to the local optimal solution. To solve this problem, this study introduces beam search, which slows local optimization by retaining a predetermined number of states in each round of division, thereby improving the consistency between the clustering provided by the threshold tree and the initial clustering. Finally, the effectiveness of the algorithm is verified by experiments.