Shallow decision trees for explainable k-means clustering. (May 2023)

• Record Type: Journal Article
• Authors: Laber, Eduardo; Murtinho, Lucas; Oliveira, Felipe
• Is Part Of: Pattern recognition. Volume 137(2023)
• Publication Date: 2023-05
• Subjects: Clustering -- Explainability -- K-means -- Decision trees; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2022.109239
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: First explainable clustering algorithm for k-means sensitive to the tree's depth. Superior results to similar algorithms in experiments with 16 datasets. Parameter calibration allows exploration of trade-off between cost and explainability. Abstract: A number of recent works have employed decision trees for the construction of explainable partitions that aim to minimize the k -means cost function. These works, however, largely ignore metrics related to the depths of the leaves in the resulting tree, which is perhaps surprising considering how the explainability of a decision tree depends on these depths. To fill this gap in the literature, we propose an efficient algorithm with a penalty term in its loss function to favor the construction of shallow decision trees – i.e., trees whose leaves are not very deep, which translate to clusters that are defined by a small number of attributes and are therefore easier to explain. In experiments on 16 datasets, our algorithm yields better results than decision-tree clustering algorithms recently presented in the literature, typically achieving lower or equivalent costs with considerably shallower trees.