11.3 Métodos não hierárquicos (de particionamento)

11.3.1 K-médias

K-médias (k-means) é um nome genérico para métodos derivados dos algoritmos de (Lloyd 1957), (Forgy 1965), (MacQueen 1967), (Hartigan 1975) e (Hartigan and Wong 1979). A ideia básica é encontrar grupos similares, de maneira a minimizar a soma de distâncias euclidianas ao quadrado. As distâncias são calculadas entre os pontos e as médias de cada um dos \(k\) grupos, chamadas centróides.

Em relação ao modo de busca podem ser classificados como algoritmos de comutação, em que objetos devem ser particionados em \(k\) de grupos. Uma partição inicial é dada de forma arbitrária, onde se definem \(k\) centróides. Calcula-se a distância euclidiana ao quadrado entre as observações e os \(k\) centróides. O centróide mais próximo define o grupo ao qual uma observação pertence. Recalculam-se os novos centróides, e novas partições são obtidas com a alternância dos objetos entre os grupos. O algoritmo encerra quando nenhuma comutação adicional reduz a soma de quadrados intra-grupo, ou quando outro critério de parada é atingido.

São algoritmos relativamente rápidos na execução, mas são afetados pela incerteza da partição inicial. Há sempre a possibilidade de que partições iniciais distintas possam levar a partições finais superiores a outras.

A variação quadrática intra-grupo (\(VQI_{j}\)) do \(j\)-ésimo grupo é dada pela Equação (11.4). \[\begin{equation} VQI_{j} = \sum_{x_i \in G_j} (x_i - \mu_j)^2 \tag{11.4} \end{equation}\]

  • \(x_i\) é o \(i\)-ésimo elemento pertencente ao grupo \(G_j\)
  • \(\mu_j\) é o ponto médio do grupo \(G_j\)
  • \(j \in \{2, \ldots, k\}\)

A soma de quadrados total (\(SQT\)) é dada pela Equação (11.5). \[\begin{equation} SQT = \sum_{i=1}^{k} VQI_{i} \tag{11.5} \end{equation}\]

Cada observação \(x_i\) é atribuída a um grupo de forma que a \(SQT\) seja mínima a cada iteração. É recomendado que seja feita a padronização dos dados, de maneira a controlar o impacto da escala na definição dos grupos.

ALGORITMO DAS K-MÉDIAS

PASSO 1 Especifique o número \(k\) de grupos a serem criados.

PASSO 2 Selecione arbitrariamente \(k\) pontos como centros dos grupos (centróides).

PASSO 3 Atribua cada observação ao grupo de centróide mais próximo, baseado na distância euclidiana entre a observação e os centróides.

PASSO 4 Recalcule os centróides com os pontos atribuídos a cada grupo. O centróide do \(j\)-ésimo grupo é um vetor de comprimento \(p\) contendo as médias das \(p\) variáveis, calculadas com todos os pontos atribuídos ao \(j\)-ésimo grupo.

PASSO 5 Repita os passos 3 e 4 até que as atribuições não mais reduzam a soma de quadrados intra-grupo, ou que o número máximo de iterações (ou qualquer outro critério de parada) seja atingido.

Seleção inicial dos centróides

(Hartigan 1975) sugere que a seleção inicial dos centróides seja baseada na soma dos casos \(S\), que tem um valor mínimo \(minS\) e um máximo \(maxS\). Para obter \(k\) grupos iniciais, propõe atribuir o \(i\)-ésimo caso ao \(j\)-ésimo grupo, onde \(j\) é a parte inteira de

\[\begin{equation} k \left( \dfrac{S-minS}{maxS-minS} \right) + 1 \tag{11.6} \end{equation}\]

Uma adaptação será feita, multiplicando 1.01 a \(maxS\) para evitar encontrar \(j>k\).

iris2 <- scale(iris[-5])
S <- rowSums(iris2)
k <- 2
zab <- k*(S - min(S))/(1.01*max(S)-min(S)) + 1 # atribuição de Zabala (2019) baseada em Hartigan (1975)
(g <- floor(zab)) # grupos
##   [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##  [48] 1 1 1 2 2 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 1 1 1 2 1 1 1 2 2 2 2 2 1 1 1 1 2 1 2 2 1 1 1 1 2 1 1
##  [95] 1 1 1 1 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
## [142] 2 2 2 2 2 2 2 2 2
table(g)
## g
##  1  2 
## 83 67
(centroide <- by(iris2, g, colMeans))
## INDICES: 1
## Sepal.Length  Sepal.Width Petal.Length  Petal.Width 
##  -0.70707156   0.03984126  -0.68805740  -0.70250780 
## -------------------------------------------------------------------------- 
## INDICES: 2
## Sepal.Length  Sepal.Width Petal.Length  Petal.Width 
##   0.87592447  -0.04935559   0.85236961   0.87027086
summary(iris2)
##   Sepal.Length       Sepal.Width       Petal.Length      Petal.Width     
##  Min.   :-1.86378   Min.   :-2.4258   Min.   :-1.5623   Min.   :-1.4422  
##  1st Qu.:-0.89767   1st Qu.:-0.5904   1st Qu.:-1.2225   1st Qu.:-1.1799  
##  Median :-0.05233   Median :-0.1315   Median : 0.3354   Median : 0.1321  
##  Mean   : 0.00000   Mean   : 0.0000   Mean   : 0.0000   Mean   : 0.0000  
##  3rd Qu.: 0.67225   3rd Qu.: 0.5567   3rd Qu.: 0.7602   3rd Qu.: 0.7880  
##  Max.   : 2.48370   Max.   : 3.0805   Max.   : 1.7799   Max.   : 1.7064

Exercício 11.5 Utilize a Equação (23) sem a correção de Zabala e observe o resultado em iris2. \(\\\)

Exercício 11.6 Utilize a Equação (23) com a correção de Zabala para criar uma função que defina os centróides iniciais para um valor genérico \(k\) de grupos em uma base de dados numérica. Teste em iris2 e outros bancos de dados já trabalhados.

Implementando no R

No R pode-se utilizar a função stats::kmeans para definir os grupamentos através das k-médias. Por padrão, esta função utiliza 10 como valor padrão para o número máximo de iterações e inicia com \(k\) centróides aleatórios.

km <- function(dados,grupos){
  k <- kmeans(dados,grupos)
  print(table(iris$Species, k$cluster))
  plot(dados, col=k$cluster)
}
km(iris2,2)
##             
##               1  2
##   setosa     50  0
##   versicolor  0 50
##   virginica   0 50

km(iris2,3)
##             
##               1  2  3
##   setosa      0  0 50
##   versicolor 11 39  0
##   virginica  36 14  0

km(iris2,4)
##             
##               1  2  3  4
##   setosa      0 49  0  1
##   versicolor  2  0 29 19
##   virginica  27  0 21  2

O pacote factoextra fornece uma série de melhorias para a análise de k-means. Além de gráficos mais sofisticados utilizando ggplot2, associa métodos hierárquicos e métodos de particionamento.

km2 <- function(dados,grupos){
  k <- kmeans(dados,grupos)
  fviz_cluster(k, iris2, repel = T)
}
km2(iris2,2)

km2(iris2,3)

km2(iris2,4)

Número de grupos

A função factoextra::fviz_nbclust fornece métodos para a escolha de um número ótimo de grupos. O método wss (total within sum of square), busca um número de grupos que traga um bom custo-benefício entre o número de grupos (\(k\)) e a soma de quadrados total (\(SQT\)). Este custo-benefício é indicado onde a curva muda sua declividade, ou no ‘cotovelo’ (elbow) ou ‘joelho’ (knee) do gráfico de \(k\) por \(SQT\). Tem suas origens no trabalho de (R. L. Thorndike 1953).

fviz_nbclust(iris2, kmeans, method = 'wss')

O método silhouette busca o número de grupos que maximize o tamanho médio da silhueta. É baseado em uma medida sugerida por (Rousseeuw and Kaufman 1990), dada por

\[\begin{equation} s(i) = \dfrac{b(i)-a(i)}{max\{ a(i),b(i) \}} \tag{11.7} \end{equation}\]

  • \(-1 \le s(i) \le 1\)
  • \(a(i)\): dissimilaridade média do elemento \(i\) em relação a todos os demais elementos do seu grupo \(A\)
  • \(d(i,C)\): dissimilaridade média do elemento \(i\) em relação a todos os elementos do grupo \(C \ne A\)
  • \(b(i) = \underset{C \ne A}{\mathrm{min}} \; d(i,C)\)
fviz_nbclust(iris2, kmeans, method = 'silhouette')

Proposto por (Tibshirani, Walther, and Hastie 2001), o método gap_stat (gap statistic) compara variação total intra-grupo para diferentes valores de k com seus valores esperados sob alguma distribuição de referência. A estimativa dos clusters ótimos será o valor que maximiza a estatística de gap (isto é, que gera a maior estatística de gap).

\[\begin{equation} \mathrm{Gap}_{n}(k) = E^{*} \{ \mathrm{log}(W_k) \} - \mathrm{log}(W_k) \tag{11.8} \end{equation}\]

  • \(E^{*}\) é o valor esperado sob uma amostra de tamanho \(n\) da distribuição de referência
  • \(W_k = \sum_{j=1}^{k} \dfrac{1}{2n_j} D_j\)
  • \(D_j = \sum_{i,i' \in C_j} d_{ii'}\)
  • \(n_j = |C_j|\)
fviz_nbclust(iris2, kmeans, method = 'gap_stat')
## Clustering k = 1,2,..., K.max (= 10): .. done
## Bootstrapping, b = 1,2,..., B (= 100)  [one "." per sample]:
## .................................................. 50 
## .................................................. 100

11.3.2 K-medianas

Existem extensões do método de k-médias, utilizando medianas para fazer os grupamentos. O pacote Gmedian de (Cardot 2021) traz a função kGmedian, que realiza o agrupamento rápido de k-medianas com base em algoritmos de gradiente estocástico ponderado recursivo (Cardot, Cénac, and Monnez 2012), (Cardot et al. 2013). O procedimento é semelhante à técnica de agrupamento stats::kmeans realizada recursivamente com o algoritmo de (MacQueen 1967). A vantagem do algoritmo kGmedian em relação à estratégia de MacQueen é que ele lida com soma de normas ao invés de soma de normas quadradas, garantindo um comportamento mais robusto contra valores extremos (outliers).

library(Gmedian)

iris2 = scale(iris[-5])

cl.kmeans <- kmeans(iris2, 2)
cl.kmedian <- kGmedian(iris2, 2)

par(mfrow=c(1,2))
plot(iris2, col = cl.kmeans$cluster, main = 'kmeans')
points(cl.kmeans$centers, col = 1:2, pch = 8, cex = 2)
plot(iris2, col = cl.kmedian$cluster, main = 'kGmedian')
points(cl.kmedian$centers, col = 1:2, pch = 8, cex = 2)

11.3.3 K-medóides

https://www.datanovia.com/en/lessons/k-medoids-in-r-algorithm-and-practical-examples/
https://cran.r-project.org/web/packages/ClusterR/vignettes/the_clusterR_package.html

O algoritmo k-medóides proposto por (Kaufman and Rousseeuw 1987) é um algoritmo de particionamento relacionado ao algoritmo de k-médias. Assim como nas k-médias o objetivo é minimizar a distância entre os pontos e o centróide de um grupo. Ao contrário das k-médias o algoritmo dos k-medóides define necessariamente um ponto observado como centro.

# library(ClusterR)
# 
# iris2 <- scale(iris[-5])
# 
# cm = Cluster_Medoids(iris2, clusters = 2, swap_phase = TRUE, verbose = F)

11.3.4 k-modas

O algoritmo das k-modas executa o particionamento de dados categóricos. O pacote klaR (Weihs et al. 2005) traz a função kmodes baseada em (MacQueen 1967) e (Huang 1997).

library(klaR)

## generate data set with two groups of data:
set.seed(1)
x <- rbind(matrix(rbinom(250, 2, 0.25), ncol = 5),
           matrix(rbinom(250, 2, 0.75), ncol = 5))
colnames(x) <- c('a', 'b', 'c', 'd', 'e')

## run algorithm on x:
(cl <- kmodes(x, 2))
## K-modes clustering with 2 clusters of sizes 44, 56
## 
## Cluster modes:
##   a b c d e
## 1 1 2 1 0 2
## 2 2 0 2 1 0
## 
## Clustering vector:
##   [1] 2 2 2 2 2 1 2 1 1 1 1 2 1 2 2 2 1 1 2 1 2 2 2 2 1 2 2 2 2 1 1 1 2 1 1 1 2 2 2 2 2 1 1 2 1 2 2
##  [48] 2 1 1 2 1 1 1 1 2 1 2 1 1 1 2 2 1 1 2 2 1 1 2 2 2 1 2 2 2 2 1 2 2 2 1 1 2 2 2 1 1 2 2 2 2 1 2
##  [95] 2 1 1 1 2 1
## 
## Within cluster simple-matching distance by cluster:
## [1] 105 142
## 
## Available components:
## [1] "cluster"    "size"       "modes"      "withindiff" "iterations" "weighted"
## and visualize with some jitter:
plot(jitter(x), col = cl$cluster)
points(cl$modes, col = 1:5, pch = 8)

11.3.5 ROCK

Assim como as k-modas, o algoritmo Rock executa o particionamento de dados categóricos. O pacote cba (Buchta and Hahsler 2019) traz a função rockCluster baseada em (Guha, Rastogi, and Shim 2000).

library(cba)
(cluster.results <- rockCluster(x, 2))
## Clustering:
## computing distances ...
## computing links ...
## computing clusters ...
##  data: x 
##  beta: 0.5 
## theta: 0.5 
##   fun: dist 
##  args: list("binary") 
##  1  2 
## 96  4
# cluster.output <- cbind(x,cluster.results$cl)
# plot(jitter(cluster.output), col = cl$cluster)
# points(cluster.output, col = 1:5, pch = 8)

Referências

Buchta, Christian, and Michael Hahsler. 2019. Cba: Clustering for Business Analytics. https://CRAN.R-project.org/package=cba.
Cardot, Hervé. 2021. Gmedian: Geometric Median, k-Medians Clustering and Robust Median PCA. https://CRAN.R-project.org/package=Gmedian.
Cardot, Hervé, Peggy Cénac, and Jean-Marie Monnez. 2012. “A Fast and Recursive Algorithm for Clustering Large Datasets with k-Medians.” Computational Statistics & Data Analysis 56 (6): 1434–49. https://doi.org/10.1016/j.csda.2011.11.019.
Cardot, Hervé, Peggy Cénac, Pierre-André Zitt, et al. 2013. “Efficient and Fast Estimation of the Geometric Median in Hilbert Spaces with an Averaged Stochastic Gradient Algorithm.” Bernoulli 19 (1): 18–43. https://projecteuclid.org/download/pdfview_1/euclid.bj/1358531739.
Forgy, Edward W. 1965. “Cluster Analysis of Multivariate Data: Efficiency Versus Interpretability of Classifications.” Biometrics 21: 768–69.
Guha, Sudipto, Rajeev Rastogi, and Kyuseok Shim. 2000. ROCK: A Robust Clustering Algorithm for Categorical Attributes.” Information Systems 25 (5): 345–66. https://doi.org/10.1016/S0306-4379(00)00022-3.
Hartigan, John A. 1975. Clustering Algorithms. John Wiley & Sons, Inc.
Hartigan, John A, and Manchek A Wong. 1979. “Algorithm AS 136: A k-Means Clustering Algorithm.” Journal of the Royal Statistical Society. Series C (Applied Statistics) 28 (1): 100–108. https://www.labri.fr/perso/bpinaud/userfiles/downloads/hartigan_1979_kmeans.pdf.
Huang, Zhexue. 1997. “A Fast Clustering Algorithm to Cluster Very Large Categorical Data Sets in Data Mining.” DMKD 3 (8): 34–39. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.134.83&rep=rep1&type=pdf.
Kaufman, P., and P. J. Rousseeuw. 1987. “Clustering by Means of Medoids.” https://www.researchgate.net/publication/243777819_Clustering_by_Means_of_Medoids.
Lloyd, Stuart P. 1957. “Least Squares Quantization in PCM.” Tecnical Note at Bell Laboratories in 1957, Published After in IEEE Transactions on Information Theory in 1982 28 (2): 129–37. https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1056489.
MacQueen, James. 1967. “Some Methods for Classification and Analysis of Multivariate Observations.” In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, 1:281–97. 14. Oakland, CA, USA. https://sci2s.ugr.es/keel/pdf/algorithm/congreso/1967-MacQueen-MSP.pdf.
Rousseeuw, Peter J, and L Kaufman. 1990. “Finding Groups in Data.” Hoboken: Wiley Online Library. https://onlinelibrary.wiley.com/doi/pdf/10.1002/9780470316801.
Thorndike, Robert L. 1953. “Who Belongs in the Family?” Psychometrika 18 (4): 267–76. https://link.springer.com/content/pdf/10.1007%2FBF02289263.pdf.
Tibshirani, Robert, Guenther Walther, and Trevor Hastie. 2001. “Estimating the Number of Clusters in a Data Set via the Gap Statistic.” Journal of the Royal Statistical Society: Series B (Statistical Methodology) 63 (2): 411–23. http://web.stanford.edu/~hastie/Papers/gap.pdf.
Weihs, Claus, Uwe Ligges, Karsten Luebke, and Nils Raabe. 2005. “klaR Analyzing German Business Cycles.” In Data Analysis and Decision Support, edited by D. Baier, R. Decker, and L. Schmidt-Thieme, 335–43. Berlin: Springer-Verlag.