[en] CLUSTERING UNDER CONSTRAINTS: EXPLAINABILITY VIA DECISION TREES AND SEPARABILITY WITH MINIMUM SIZE - LUCAS SAADI MURTINHO (2025)
[pt] Investigamos dois métodos de clusterização com restrições nas partições geradas: a clusterização explicável, em que a partição deve ser induzida por uma árvore de decisão binária (ou seja, por cortes paralelos aos eixos); e a clusterização de tamanho mínimo, na qual todos os clusters devem ter pelo menos um número predeterminado de elementos. Para a clusterização explicável, apresentamos algoritmos e garantias teóricas para as funções de custo k-centers, k-medians, k-means e espaçamento mínimo. Introduzimos também três algoritmos práticos para a popular função de custo k-means: ExGreedy, com resultados geralmente melhores do que os de algoritmos comparáveis na literatura; ExShallow, com um termo de penalidade relacionado à profundidade da árvore que induz a partição, permitindo um equilíbrio entre desempenho (redução da função de custo) e explicabilidade (geração de árvores mais rasas); e ExBisection, que, até onde sabemos, é o primeiro algoritmo de clusterização explicável baseado em árvores de decisão para a função de custo k-means que constrói uma partição explicável do zero (ou seja, sem usar uma partição irrestrita como ponto de partida). Para a clusterização de tamanho mínimo, focamos em medidas interclusterização. Mostramos que Single-Linkage, o algoritmo que maximiza o espaçamento mínimo, também maximiza o custo da árvore de geração mínima de um grafo induzido pela partição gerada por ele; no entanto, este algoritmo tende a gerar muitos clusters pequenos, o que motiva a busca por algoritmos com bons resultados para essas funções de custo que garantam um número mínimo de elementos por cluster. Introduzimos um algoritmo de aproximação para cada função de custo e apresentamos os resultados de experimentos que mostram que eles produzem partições com melhores resultados do que o popular algoritmo k-means para essas instâncias do problema de clusterização.