[en] CLUSTERING UNDER CONSTRAINTS: EXPLAINABILITY VIA DECISION TREES AND SEPARABILITY WITH MINIMUM SIZE

[pt] CLUSTERIZAÇÃO SOB RESTRIÇÕES: EXPLICABILIDADE VIA ÁRVORES DE DECISÃO E SEPARABILIDADE COM TAMANHO MÍNIMO

[pt] LUCAS SAADI MURTINHO

[pt] ARVORE DE DECISAO

[pt] EXPLICABILIDADE

[pt] SEPARABILIDADE

[pt] CLUSTERIZACAO

[en] DECISION TREE

[en] EXPLAINABILITY

[en] SEPRABILITY

[en] CLUSTERING

[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.

[en] We investigate two methods of clustering with constraints on the partitions being generated: explainable clustering, in which the partition must be induced by a binary decision tree (i.e., by cuts that are parallel to the axes); and minimum-size clustering, in which all clusters must have at least a predetermined number of elements. For explainable clustering, we present theoretical algorithms and bounds for the k-centers, k-medians, k-means, and minimum-spacing cost functions. We also introduce three practical algorithms for the popular k-means cost function: ExGreedy, which presents results generally better than comparable algorithms in the literature; ExShallow, with a penalty term related to the depth of the tree that induces the partition, allowing for a trade-off between performance (reducing the cost function) and explainability (generating shallower trees); and ExBisection, to our knowledge the first explainable clustering algorithm based on decision trees for the k-means cost function that builds an explainable partition from scratch (i.e., without starting from an unrestricted partition). For minimum-size clustering, our focus is on inter-clustering measures. We show that Single-Linkage, the algorithm that maximizes the minimum spacing, also maximizes the minimum-spanning-tree cost of a graph induced by the partition it generates; however, it is also prone to generating small clusters, which motivates the search for algorithms that perform well for these cost functions without suffering from this tendency. We introduce one approximation algorithm for each cost function, and present the results of experiments showing that they produce partitions that perform better than the popular k-means algorithm for these instances of the clustering task.

EDUARDO SANY LABER

MARCO SERPA MOLINARO

EDUARDO SANY LABER

EDWARD HERMANN HAEUSLER

DIEGO PARENTE PAIVA MESQUITA

DANIEL RATTON FIGUEIREDO

2025-03-18

2024-08-23

[pt] TEXTO

application/pdf

INGLÊS

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=69655@1

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=69655@2

https://doi.org/10.17771/PUCRio.acad.69655