Uma proposta para determinar o número de clusters

Trabalho de Conclusão de Curso

Allan Vieira
Orientador - Prof. Dr. André Cançado

Sumário



  1. Introdução

  2. Metodologia

  3. Algoritmo

  4. Resultados

  5. Conclusões

  6. Referências

Introdução

  • agrupar objetos/indivíduos/coisas \(\rightarrow\) inerente aos seres humanos:


  • Agrupamentos também são muito usados na Ciência:
    • Task View CRAN para a palavra cluster: \(\pm\) 100 pacotes (jun. de 2018)
    • hype de Machine Learning
  • Mas...

O problema de estudo...




  • algoritmos \(\rightarrow\) restrições:
    • "shape" dos dados vs algoritmo empregado
    • (...)
    • definição a priori do número k de clusters


  • técnicas diferentes com o mesmo k \(\rightarrow\) soluções diferentes para o mesmo conjunto de dados
    • maioria dos algoritmos utilizam funções uniobjetivo (Handl e Knowles, 2007)

Objetivo



  • Desenvolver um algoritmo para determinar o número de clusters utilizando uma função multiobjetivo;

  • Porém... "Não acho que quem ganhar ou quem perder, nem quem ganhar nem perder, vai ganhar ou perder. Vai todo mundo perder." (Dilma Roussef)

  • No Free Lunch Theorems

Metodologia ...

Descrição geral do método



  • aplicar uma técnica de clusterização (MST) nos dados reais para \(k=2,...,n\) \(\space\) clusters;
  • obter duas estatísticas de teste (conectividade e SSwt) para cada solução;
  • repetir o procedimento para dados simulados (hipercubos);
  • comparar as soluções obtidas em ambos os casos para definir o valor de \(k\);
  • ideia \(\rightarrow\) espera-se que soluções espúrias de agrupamentos nos dados apresentem valores de estatísticas de teste próximos aos das simulações.

Minimum Spanning Trees (MST)

Hipercubos - Distribuição de Referência

inspiração: Cubic Clustering Criterion (CCC)

Estatísticas de Teste - SS.wt



  • Soma de quadrados total intra-cluster: \[SS.wt = \sum_{i=1}^{k}SSw_i,\]

    onde \(SSw_i\) é a soma de quadrados dentro do cluster \(i\).

Estatísticas de Teste - conn

  • \(N\): número de pontos no dataset;
  • \(L\) (ou \(n\_neig\)): cardinalidade do conjunto de vizinhos mais próximos para avaliar conectividade;
  • \(V_{L_{i}}\): conjunto de vizinhos mais próximos do ponto \(i\);
  • \(C_k\): conjunto (cluster) de pontos de rótulo \(k\).


\[conn = \sum_{i=1}^{N}\left(\sum_{j=1}^{L}x_{j,i}\right),\]

\[x_{j,i} = \begin{cases} \frac{1}{j}, \; & \text{se} \; \nexists C_k: i \in C_k \land j \in C_k. \\ 0, & \text{caso contrário}. \end{cases}\]

Otimalidade de Pareto - Função Multi-objetivo

Algoritmo (1)

Algoritmo (2)

Uma demonstração ...

Alguns resultados ...

Resultados (1)

id type dim N n_neig n_sim clust result
1 elipse 2d 66 8 100 3 k=3
2 elipse 2d 236 8 400 2 k=2
3 elipse 2d 30 3 400 2 k=2
4 elipse 2d 100 8 100 2 k=2
5a elipse 2d 1050 8 100 2 k=2
5b elipse 2d 1050 3 400 2 k=2
6 elipse 2d 620 10 1000 3 fail.MST
7 elipse 2d 750 25 100 3 k=3
8 elipse 3d 315 8 400 3 k=3
9 elipse 3d 520 7 400 4 fail.MST
10 elipse 3d 633 7 400 4 k=4
11a elipse 3d 383 5 400 4 k $\ge$ 6
11b elipse 3d 383 5 1000 4 k $\ge$ 6
11c elipse 3d 383 7 1000 4 k=4

Resultados (2)

id type dim N n_neig n_sim clust result
12a elipse 10d 838 3 400 4 k $\ge$ 5
12b elipse 10d 838 7 1000 4 fail.MST
12a circ.+elip. 2d 550 7 1000 2 k=4
12b circ.+elip. 2d 550 25 1000 2 k=4
14a circ.+elip. 2d 1000 25 400 4 k $\ge$ 5
14b circ.+elip. 2d 1000 10 1000 4 k=5
15a espiral 2d 1000 7 400 3 k=4
15b espiral 2d 300 20 300 3 k=2
15c espiral 2d 300 15 300 3 k=3
15d espiral 2d 300 15 1000 3 k=3
16 espiral 2d 300 20 300 3 k=2
17 alongado 2d 300 30 300 4 k=4
18 along.+elip. 2d 750 25 100 3 k=3

Resultados (3)

Resultados (4)

Resultados (5)

Conclusões

  • MST:

    • bom desempenho do algoritmo MST based clustering
    • resolver problemas com outliers

  • Algoritmo geral:

    • dificuldades em dados com grupos circulares (herda do ccc) e com outliers (herda do MST)
    • especificar n_neig é uma restrição
    • bom funcionamento no geral

  • Para estudos futuros:

    • aprimorar os algoritmos e implementar pacotes

Referências

  • CURTIN, R. R. et al. Mlpack: A scalable C++ machine learning library. Journal of Machine Learning Research , v. 14, 2013.

  • EVERITT, B. S. et al. Cluster Analysis. 5th edition. ed. [S.l.: s.n.], 2011.

  • HANDL, J.; KNOWLES, J. An evolutionary approach to objective clustering. IEEE Transactions on Evolutionary Computation, v. 11, n. 1, Feb 2007. 2

  • MARCH, W. B.; RAM, P.; GRAY, A. G. Fast euclidian minimum spanning tree: algorithm analysis, and applications. 16th ACM SIGKDD international conference on Knowledge discovery and data mining , July 25-28 2010. Washington, DC, USA.

  • SARLE, W. S. Cubic Clustering Criterion. [S.l.], 1983. v. 46, n. A-108. Cary, NC.: SAS Institute, 1983, 56 pp.

Obrigado!!