Capítulo XIII. Análise de Cluster


Os próximos dois capítulos abordam questões de classificação de duas perspectivas diferentes. Ao considerar grupos de objetos em um conjunto de dados multivariado, duas situações podem surgir. Dado um conjunto de dados contendo medidas de indivíduos, em alguns casos queremos ver se existem alguns grupos naturais ou classes de indivíduos e em outros casos queremos classificar os indivíduos de acordo com um conjunto de grupos existentes.

A análise de agrupamento ou análise de cluster desenvolve ferramentas e métodos para o primeiro caso, ou seja, dada uma matriz de dados contendo medidas multivariadas sobre um grande número de indivíduos ou objetos, o objetivo é construir alguns subgrupos naturais ou agrupamentos de indivíduos. Isso é feito agrupando indivíduos que são semelhantes de acordo com algum critério apropriado. Uma vez que os agrupamentos são obtidos, geralmente é útil descrever cada grupo usando alguma ferramenta descritiva para melhor compreensão das diferenças que existem entre os grupos formulados.

A análise de cluster é aplicada em muitas áreas, como ciências naturais, ciências médicas, economia, marketing, etc. Em marketing, por exemplo, é útil construir e descrever os diferentes segmentos de um mercado a partir de uma pesquisa com consumidores em potencial. Uma companhia de seguros, por outro lado, pode estar interessada na distinção entre classes de clientes potenciais para que possa obter preços ótimos para seus serviços. Outros exemplos são fornecidos abaixo.

Análise discriminante apresentada no capítulo seguinte aborda a outra questão de classificação. Concentra-se em situações em que os diferentes grupos são conhecidos a priori. As regras de decisão são fornecidas na classificação de uma observação multivariada em um dos grupos conhecidos. A Seção XIII.1 apresenta o problema da análise de agrupamento onde o critério escolhido para medir a similaridade entre objetos claramente desempenha um papel importante. A Seção XIII.2 mostra como medir com precisão a proximidade entre objetos. Por fim, Seção XIII.3 fornece alguns algoritmos. Vamos nos concentrar em algoritmos hierárquicos apenas onde o número de clusters não é conhecido antecipadamente.


XIII.1. O problema


A análise de cluster é um conjunto de ferramentas para construir grupos (clusters) a partir de objetos de dados multivariados. O objetivo é construir grupos com propriedades homogêneas a partir de grandes amostras heterogêneas. Os grupos ou agrupamentos devem ser o mais homogêneos possível e as diferenças entre os vários grupos o maior possível. A análise de cluster pode ser dividida em duas etapas fundamentais.

  1. Escolha de uma medida de proximidade: Cada par de observações (objetos) verifica a similaridade de seus valores. Uma medida de similaridade (proximidade) é definida para medir a proximidade dos objetos. Quanto mais próximos estiverem, mais homogêneos eles são.

  2. Escolha do algoritmo de construção de grupos: Com base nas medidas de proximidade, os objetos atribuídos aos grupos, de modo que as diferenças entre os grupos se tornem grandes e as observações em um grupo se tornem o mais próximo possível.

Em marketing, por exemplo, a análise de cluster é usada para selecionar mercados de teste. Outras aplicações incluem a classificação de empresas de acordo com suas estruturas organizacionais, tecnologias e tipos. Na psicologia, a análise de cluster é usada para encontrar tipos de personalidades com base em questionários. Na arqueologia, é aplicado para classificar objetos de arte em diferentes períodos de tempo. Outros ramos científicos que utilizam a análise de cluster são a medicina, a sociologia, a linguística e a biologia. Em cada caso, uma amostra heterogênea de objetos é analisada com o objetivo de identificar subgrupos homogêneos.


XIII.2. A proximidade entre objetos


O ponto de partida de uma análise de cluster é uma matriz \(n\times p\) de dados \(X\), com \(n\) medidas (objetos) de \(p\) variáveis. A proximidade (semelhança) entre objetos é descrita por uma matriz \(n\times n\) \[ D = \begin{pmatrix} d_{11} & d_{12} & \cdots & d_{1n} \\ d_{21} & d_{22} & \cdots & d_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ d_{n1} & d_{n2} & \cdots & d_{nn} \end{pmatrix}\cdot \]

A matriz \(D\) contém medidas de similaridade ou dissimilaridade entre os \(n\) objetos. Se os valores \(d_{ij}\) são distâncias, então eles medem dissimilaridade. Quanto maior a distância, menos semelhantes são os objetos. Se os valores \(d_{ij}\) são medidas de proximidade, então o oposto é verdadeiro, ou seja, quanto maior o valor de proximidade, mais semelhantes são os objetos.

Uma matriz de distância, por exemplo, pode ser definida pela norma \(L_2: d_{ij} =|| x_i- x_j||_2\), onde \(x_i\) e \(x_j\) denotam as linhas da matriz de dados \(X\). Distância e similaridade são, obviamente, duais. Se \(d_{ij}\) é uma distância, então \(d'_{ij}=\max_{i,j} \{d_{ij}\}-d_{ij}\) é uma medida de proximidade.

A natureza das observações desempenha um papel importante na escolha da medida de proximidade. Valores nominais, como variáveis binárias, geralmente levam a valores de proximidade, enquanto valores métricos levam, em geral, a matrizes de distância. Apresentamos primeiro possibilidades para \(D\) no caso binário e depois consideramos o caso contínuo.


XIII.2.1. Semelhança de objetos com estrutura binária


Para medir a similaridade entre objetos sempre comparamos pares de observações \((x_i,x_j)\) sendo que \(x_i^\top=(x_{i1},\cdots,x_{ip})\}\), \(x_j^\top =(x_{j1},\cdots,x_{jp})\) e \(x_{ik},x_{jk}\in\{0,1\}\). Obviamente, existem quatro casos: \[ x_{ik}= x_{jk}=1, \qquad x_{ik}=0, \; x_{jk}=1, \qquad x_{ik}= 1, \; x_{jk}=0, \qquad x_{ik}= x_{jk}=0\cdot \]

Defina: \[ a_1=\sum_{k=1}^p \pmb{1}(x_{ik}= x_{jk}=1), \]

\[ a_2=\sum_{k=1}^p \pmb{1}(x_{ik}=0, \; x_{jk}=1), \] \[ a_3=\sum_{k=1}^p \pmb{1}(x_{ik}=1, \; x_{jk}=0), \]

\[ a_4=\sum_{k=1}^p \pmb{1}(x_{ik}= x_{jk}=0)\cdot \]

Observe que cada \(a_l\), \(l=1,\cdots,4\), depende dos pares \((x_i,x_j)\).

As seguintes medidas de proximidade são usadas na prática: \[ d_{ij}=\dfrac{a_1+\delta a_4}{a_1+\delta a_4+\lambda(a_2+a_3)}, \]

onde \(\delta\) e \(\lambda\) são fatores de ponderação. A Tabela XIII.1 mostra algumas medidas de similaridade para determinados fatores de ponderação.

\[ \begin{array}{l|c|c} \mbox{Nome} & \delta & \lambda & \mbox{Definição}\\\hline \mbox{Jaccard} & 0 & 1 & \dfrac{a_1}{a_1+a_2+a_3} \\\hline \mbox{Tanimoto} & 1 & 2 & \dfrac{a_1+a_4}{a_1+2(a_2+a_3)+a_4} \\ \hline \mbox{Correspondência simples (M)} & 1 & 1 & \dfrac{a_1+a_4}{p} \\\hline \mbox{Russel and Rao (RR)} & - & - & \dfrac{a_1}{p} \\\hline \mbox{Dice} & 0 & 0.5 & \dfrac{2a_1}{2a_1+(a_2+a_3)} \\\hline \mbox{Kulczynski} & - & - & \dfrac{a_1}{a_2+a_3} \\ \end{array} \]

TABELA XIII.1. Coeficientes de similaridade comuns.

Essas medidas fornecem formas alternativas de ponderação de incompatibilidades e correspondências positivas, ou seja, presença de um caractere comum ou negativas, ausência de um caractere comum. Em princípio, poderíamos também considerar a distância euclidiana. No entanto, a desvantagem dessa distância é que ela trata as observações 0 e 1 da mesma maneira. Se \(x_{ik}=1\) denota, digamos, conhecimento de um determinado idioma, então, ao contrário, \(x_{ik}=0\) não conhecer o idioma, deve eventualmente ser tratado de forma diferente.


Exemplo XIII.1

Vamos considerar variáveis binárias calculadas a partir do conjunto de dados dos carros, Exemplo I.2.. Definimos os novos dados binários por \[ y_{ik}=\left\{ \begin{array}{lc} 1, & \mbox{se} \; x_{ik}> \overline{x}_k \\ 0, & \mbox{caso contrário}\end{array} \right., \] para \(i=1,\cdots,n\) e \(k=1,\cdots,p\).

Isso significa que transformamos as observações da \(k\)-ésima variável para 1 se ela for maior que o valor médio de todas as observações da \(k\)-ésima variável. Consideremos apenas os pontos de dados 17 a 19, Renault 19, Rover e Toyota Corolla, que levam seguintes às matrizes \(3\times 3\) de distância.

A medida de Jaccard fornece a matriz de similaridade \[ D = \begin{pmatrix} 1.000 & 0.000 & 0.400 \\ & 1.000 & 0.167 \\ & & 1.000 \end{pmatrix}, \] a medida de Tanimoto rende \[ D = \begin{pmatrix} 1.000 & 0.000 & 0.455 \\ & 1.000 & 0.231 \\ & & 1.000 \end{pmatrix}, \]

enquanto a medida de Correspondência Simples (M) fornece \[ D = \begin{pmatrix} 1.000 & 0.000 & 0.625 \\ & 1.000 & 0.375 \\ & & 1.000 \end{pmatrix}\cdot \]



XIII.2.2. Medidas de distância para variáveis contínuas


Uma grande variedade de medidas de distância pode ser gerada pelas normas \(L_r\), \(r\geq 1\), \[ d_{ij}=|| x_i-x_j||_r = \left( \sum_{k=1}^p |x_{ik}-x_{jk}|^r\right)^{1/r}\cdot \]

Aqui \(x_{ik}\) denota o valor da \(k\)-ésima variável no objeto \(i\). É claro que \(d_{ii}=0\) para \(i=1,\cdots,n\).

A classe de distâncias acima para valores de \(r\) mede a dissimilaridade de diferentes pesos. A métrica \(L_1\), por exemplo, dá menos peso aos valores discrepantes do que a norma \(L_2\), norma euclidiana. É comum considerar a norma \(L_2\) ao quadrado.


Exemplo XIII.2

Suponha que temos \(x_1=(0,0)\), \(x_2=(1,0)\) e \(x_3=(5,5)\). Então a matriz de distância para a norma \(L_1\) é \[ D_1 =\begin{pmatrix} 0 & 1 & 10 \\ & 0 & 9 \\ & & 0 \end{pmatrix} \]

e para o quadrado da norma \(L_2\) ou norma euclidiana \[ D_2=\begin{pmatrix} 0 & 1 & 50 \\ & 0 & 41 \\ & & 0 \end{pmatrix}\cdot \] Pode-se ver que a terceira observação \(x_3\) recebe muito mais peso na norma \(L_2\) ao quadrado do que na norma \(L_1\).


Uma suposição subjacente na aplicação de distâncias baseadas em normas \(L_r\) é que as variáveis são medidas na mesma escala. Se este não for o caso, uma padronização deve ser aplicada primeiro. Isso corresponde ao uso de uma norma \(L_2\) ou euclidiana mais geral com uma métrica \(A\), onde \(A > 0\): \[ d_{ij}^2=|| x_i-x_j||_A = (x_i-x_j)^\top A (x_i-x_j)\cdot \]

As normas \(L_2\) são dadas por \(A=\mbox{I}_p\), mas se uma padronização for desejada, então a matriz de peso \[ A=\mbox{diag}\big( s_{X_1X_1}^{-1},\cdots,s_{X_pX_p}^{-1}\big) \] pode ser adequado. Lembre-se de que \(s_{X_kX_k}\) é a variância do \(k\)-ésimo componente. Daí temos \[ d_{ij}^2=\sum_{k=1}^p \dfrac{(x_{ik}-x_{jk})^2}{s_{X_kX_k}}\cdot \] Aqui cada componente tem o mesmo peso no cálculo das distâncias e as distâncias não dependem de uma escolha particular das unidades de medida.


Exemplo XIII.3

Considere os gastos com alimentos franceses, Exemplo X.1. Utilizando a norma \(L_2\) ao quadrado, ou seja, distância euclidiana obtemos como matriz de distância \(10^4\) vezes \[ D= \begin{pmatrix} 0.00 & 5.8 & 58.2 & 3.5 & 5.1 & 151.4 & 16.9 & 36.1 & 148.0 & 51.8 & 102.6 & 271.8 \\ & 0.0 & 41.7 & 4.5 & 2.9 & 120.6 & 13.5 & 25.4 & 116.3 & 43.7 & 76.8 & 226.9 \\ & & 0.0 & 44.1 & 40.1 & 24.1 & 29.9 & 8.2 & 25.6 & 20.8 & 20.3 & 88.6 \\ & & & 0.0 & 0.8 & 127.8 & 5.6 & 21.7 & 125.0 & 31.2 & 732.0 & 231.6 \\ & & & & 0.0 & 121.0 & 5.7 & 19.8 & 118.8 & 30.8 & 67.4 & 220.7 \\ & & & & & 0.0 & 96.6 & 48.2 & 1.8 & 60.5 & 28.9 & 29.6 \\ & & & & & & 0.0 & 9.2 & 94.9 & 11.1 & 42.1 & 179.8 \\ & & & & & & & 0.0 & 46.9 & 6.2 & 18.8 & 113.0 \\ & & & & & & & & 0.0 & 61.1 & 29.6 & 31.9 \\ & & & & & & & & & 0.0 & 15.8 & 116.1 \\ & & & & & & & & & & 0.0 & 53.8 \\ & & & & & & & & & & & 0.0 \end{pmatrix}\cdot \]

Tomando o peso matriz \(A=\mbox{diag}\big( s_{X_1X_1}^{-1},\cdots,s_{X_7X_7}^{-1}\big)\), obtemos a matriz de distância, norma \(L_2\) ao quadrado: \[ D= \begin{pmatrix} 0.00 & 6.9 & 10.0 & 1.7 & 2.7 & 24.9 & 8.3 & 8.6 & 24.6 & 21.5 & 30.7 & 57.5 \\ & 0.0 & 13.1 & 6.6 & 3.7 & 20.1 & 13.1 & 12.4 & 15.9 & 31.5 & 25.6 & 46.6 \\ & & 0.0 & 8.0 & 7.3 & 5.0 & 9.3 & 3.9 & 7.5 & 14.9 & 15.1 & 26.9 \\ & & & 0.0 & 0.6 & 20.1 & 2.8 & 3.8 & 19.6 & 12.8 & 19.3 & 45.0 \\ & & & & 0.0 & 17.0 & 3.5 & 3.8 & 15.8 & 15.0 & 16.9 & 39.9 \\ & & & & & 0.0 & 17.5 & 9.8 & 1.6 & 21.3 & 11.4 & 13.4 \\ & & & & & & 0.0 & 1.8 & 17.9 & 4.4 & 9.9 & 33.6 \\ & & & & & & & 0.0 & 10.5 & 5.7 & 8.0 & 24.4 \\ & & & & & & & & 0.0 & 24.7 & 11.0 & 13.1 \\ & & & & & & & & & 0.0 & 9.1 & 29.8 \\ & & & & & & & & & & 0.0 & 9.4 \\ & & & & & & & & & & & 0.0 \end{pmatrix}\cdot \]


Quando aplicado a tabelas de contingência, uma métrica \(\chi^2\) é adequada para comparar e agrupar linhas e colunas de uma tabela de contingência.

Se \(X\) é uma tabela de contingência, a linha \(i\) é caracterizada pela distribuição de frequência condicional \(x_{ij}/x_{i\bullet}\), onde \(x_{i\bullet}=\sum_{j=1}^p x_{ij}\) indica as distribuições marginais sobre as linhas: \(x_{i\bullet}/x_{\bullet\bullet}=\sum_{i=1}^n x_{i\bullet}\).

Da mesma forma, a coluna \(j\) de \(X\) é caracterizada pelas frequências condicionais \(x_{ij}/x_{\bullet j}\), onde \(x_{\bullet j}=\sum_{i=1}^n x_{ij}\). As frequências marginais das colunas são \(x_{\bullet j}/x_{\bullet\bullet}\).

A distância entre duas linhas, \(i_1\) e \(i_2\), corresponde à distância entre suas respectivas distribuições de frequência. É comum definir essa distância usando a métrica \(\chi^2\): \[ d^2(i_1,i_2)=\sum_{j=1}^p \dfrac{1}{\left( \dfrac{x_{\bullet j}}{x_{\bullet\bullet}}\right)}\left( \dfrac{x_{i_1 j}}{x_{i_1 \bullet}}-\dfrac{x_{i_2 j}}{x_{i_2 \bullet}}\right)^2\cdot \]

Observe que isso pode ser expresso como uma distância entre os vetores \(x_1=x_{i_1 j}/x_{\bullet\bullet}\) e \(x_2=x_{i_2 j}/x_{\bullet\bullet}\), com matriz de ponderações \[ A =\left\{\mbox{diag}\Big( \dfrac{x_{\bullet j}}{x_{\bullet\bullet}}\Big) \right\}^{-1}\cdot \]

Da mesma forma, se estivermos interessados em clusters entre as colunas, podemos definir: \[ d^2(j_1,j_2)=\sum_{i=1}^n \dfrac{1}{\left( \dfrac{x_{i\bullet}}{x_{\bullet\bullet}}\right)}\left( \dfrac{x_{i j_1}}{x_{\bullet j_1}}-\dfrac{x_{i j_2}}{x_{\bullet j_2}}\right)^2\cdot \]

Além das medidas de norma euclidiana e \(L_r\), pode-se usar uma medida de proximidade, como o coeficiente de correlação \(Q=(q_{ij})\), definidos como \[ q_{ij}=\dfrac{\displaystyle \sum_{k=1}^p (x_{ik}-\overline{x}_i)(x_{jk}-\overline{x}_j)}{\displaystyle \sum_{k=1}^p (x_{ik}-\overline{x}_i)^2 \sum_{k=1}^p (x_{jk}-\overline{x}_j)^2}\cdot \]

Aqui \(\overline{x}_i\) denota a média sobre as variáveis \((x_{i1},\cdots,x_{ip})\).


XIII.3. Algoritmos de cluster


Existem essencialmente dois tipos de métodos de agrupamento: algoritmos hierárquicos e algoritmos de particionamento. Os algoritmos hierárquicos podem ser divididos em procedimentos aglomerativos e de divisão. O primeiro tipo de agrupamento hierárquico começa a partir da melhor partição possível, cada observação forma um agrupamento e os agrupa. O segundo tipo começa com a partição mais grosseira possível: um cluster contém todas as observações. Ele prossegue dividindo o cluster único em clusters de tamanho menor.

Os algoritmos de particionamento partem de uma determinada definição de grupo e prosseguem trocando elementos entre os grupos até que uma determinada pontuação seja otimizada. A principal diferença entre as duas técnicas de agrupamento é que, no agrupamento hierárquico, uma vez que os grupos são encontrados e os elementos são atribuídos aos grupos, essa atribuição não pode ser alterada. Em técnicas de particionamento, por outro lado, a atribuição de objetos em grupos pode mudar durante a aplicação do algoritmo.


XIII.3.1. Algoritmos hierárquicos, técnicas aglomerativas


Algoritmos aglomerativos são usados com bastante frequência na prática. O algoritmo consiste nos seguintes passos:

Se dois objetos ou grupos \(P\) e \(Q\), estão unidos, calcula-se a distância entre este novo grupo (objeto) \(P\cup Q\) e o grupo \(R\) usando a seguinte função de distância: \[ d(R, P\cup Q)=\delta_1 d(R,P)+\delta_2 d(R,Q)+\delta_3 d(P,Q)+\delta_4 | d(R,P)- d(R,Q)|\cdot \]

Os \(\delta_j\)’s são fatores de ponderação que levam a diferentes algoritmos aglomerativos conforme descrito na Tabela XIII.2. Aqui \[ n_P= \sum_{i=1}^n \mbox{I}(x_i\in P) \] é o número de objetos no grupo \(P\). Os valores de \(n_Q\) e \(n_R\) são definidos analogamente.

\[ \begin{array}{l|c|c|c|c} \mbox{Nome} & \delta_1 & \delta_2 & \delta_3 & \delta_4 \\ \hline \mbox{Ligação única} & 1/2 & 1/2 & 0 & -1/2 \\ \hline \mbox{Ligação completa} & 1/2 & 1/2 & 0 & 1/2 \\ \hline \mbox{Ligação média (não ponderada)} & 1/2 & 1/2 & 0 & 0 \\ \hline \mbox{Ligação média (ponderada)} & \dfrac{n_P}{n_P+n_Q} & \dfrac{n_Q}{n_P+n_Q} & 0 & 0 \\ \hline \mbox{Centroide} & \dfrac{n_P}{n_P+n_Q} & \dfrac{n_Q}{n_P+n_Q} & -\dfrac{n_Pn_Q}{(n_P+n_Q)^2} & 0 \\\hline \mbox{Mediana} & 1/2 & 1/2 & -1/4 & 0 \\ \hline \mbox{Ala (ward)} & \dfrac{n_R+n_P}{n_R+n_P+n_Q} & \dfrac{n_R+n_Q}{n_R+n_P+n_Q} & -\dfrac{n_R}{(n_R+n_P+n_Q)^2} & 0 \\ \end{array} \]

TABELA XIII.2. Cálculos de distâncias entre grupos.

Para as ligações mais comuns: simple e completa, abaixo estão os passos do algoritmo aglomerativo modificado. Como em vez de calcular novas matrizes de distância a cada passo, uma busca linear na matriz de distância original é suficiente para agrupar no algoritmo modificado é mais eficiente na prática.


Exemplo XIII.4

Vamos examinar o algoritmo aglomerativo para os três pontos do Exemplo XIII.2, \(x_1=(0,0)\), \(x_2=(1,0)\) e \(x_3=(5,5)\) e a matriz de distância euclidiana quadrada com ponderação de ligação simples. O algoritmo começa com \(N=3\) clusters: \(P=\{x_1\}\), \(Q=\{x_2\}\) e \(R=\{x_3\}\). A matriz de distâncias \(D_2\) é dada no Exemplo XIII.2. A menor distância em \(D_2\) é aquela entre os clusters \(P\) e \(Q\).

Portanto, aplicando o passo 4 no algoritmo acima, combinamos esses clusters para formar \(P\cup Q =\{x_1,x_2\}\). A distância de ligação única entre os dois clusters restantes é dada Tabela XIII.2 igual a \[ \begin{array}{rcl} d(R,P\cup Q) & = & \dfrac{1}{2}d(R,P)+\dfrac{1}{2}d(R,Q)-\dfrac{1}{2}\left| d(R,P)-d(R,Q)\right| \\ & = & \dfrac{1}{2}d_{13}+\dfrac{1}{2}d_{23}-\dfrac{1}{2}|d_{13}-d_{23}| \, = \, \dfrac{50}{2}+\dfrac{41}{2}-\dfrac{1}{2}|50-41| \, = \, 41\cdot \end{array} \] A matriz de distância reduzida é então \(\begin{pmatrix} 0 & 41 \\ 41 & 0 \end{pmatrix}\). O próximo e último passo é unir os clusters \(R\) e \(P\cup Q\) em um único cluster \(X\), a matriz de dados original.

Quando há mais pontos de dados do que no exemplo acima é desejável uma visualização da implicação dos clusters. Uma representação gráfica da sequência de agrupamento é chamada de dendrograma. Ele exibe as observações, a sequência de clusters e as distâncias entre os clusters. O eixo vertical exibe os índices dos pontos, enquanto o eixo horizontal dá a distância entre os clusters. Grandes distâncias indicam a aglomeração de grupos heterogêneos. Assim, se optarmos por cortar a árvore no nível desejado, os galhos descrevem os agrupamentos correspondentes.


Exemplo XIII.5

Como exemplo, selecionamos aleatoriamente 20 observações dos dados das cédulas bancárias e aplicamos a técnica de Ward (ala) usando distâncias euclidianas. A figura mostra o dendrograma. 

library(mclust)
set.seed(265)
dd <- dist(banknote[sample(1:nrow(banknote), 20, replace=FALSE),], method = "euclidean")
hc <- hclust(dd)
plot(hc)
box()


Uma outra forma de apresentar o dendograma. 

library(ape)
plot(as.phylo(hc), type = "unrooted", cex = 0.6, no.margin = TRUE)

plot(as.phylo(hc), type = "radial")



Exemplo XIII.6

Considere os gastos com comida francesa, Exemplo X.1. Como anteriormente, usamos dados padronizados que equivalem a usar \(A=\mbox{diag}\big( s_{X_1X_1}^{-1},\cdots,s_{X_pX_p}^{-1}\big)\) como a matriz de peso na norma \(L_2\). O dendrograma obtido usando o algoritmo Ward é mostrado na figura abaixo.

Se o objetivo fosse ter apenas três grupos, como pode ser visto no dendograma, eles seriam \[ \{CA4,CA3, CA2, EM4, MA4, MA5\}, \quad \{EM3, MA3, MA2, EM2\}, \quad \{CA5, EM5\}\cdot \] Se estivéssemos interessados em quatro grupos, obteríamos \[ \{CA4, CA3, CA2\}, \quad \{EM4,MA4,MA5\}, \quad \{EM3,MA3,MA2,EM2\}, \quad \{CA5,EM5\}\cdot \]

Este agrupamento mostra um equilíbrio entre níveis socioprofissionais e tamanho das famílias na determinação dos clusters. Os quatro grupos estão claramente bem representados no dendograma. 

FrenchFood = read.table(file = "http://leg.ufpr.br/~lucambio/MSM/FrenchFood.txt", sep = "")
library(caret)
preObj <- preProcess(FrenchFood, method=c("center", "scale"))
newData <- predict(preObj, FrenchFood)
ddFF <- dist(newData, method = "euclidean")
hcFF <- hclust(ddFF)
library(ggdendro)
ggdendrogram(hcFF, rotate = TRUE, theme_dendro = FALSE)



XIII.4. Comparando dois dendrogramas


Uma dendlist, no pacote dendextend, é uma função que produz a classe dendlist. Ele aceita vários dendrogramas e/ou objetos dendlist e os encadeia todos juntos. Esta função visa auxiliar na usabilidade da comparação de dois ou mais dendrogramas. 

library(dendextend)


Usaremos o seguinte para os próximos exemplos: 

dend1 <- newData %>% dist %>% hclust("com") %>% as.dendrogram
dend2 <- newData %>% dist %>% hclust("single") %>% as.dendrogram
dend3 <- newData %>% dist %>% hclust("ave") %>% as.dendrogram
dend4 <- newData %>% dist %>% hclust("centroid") %>% as.dendrogram
dend1234 <- dendlist("Complete" = dend1, "Single" = dend2, "Average" = dend3, "Centroid" = dend4)
par(mfrow = c(2,2))
plot(dend1, main = "Complete")
plot(dend2, main = "Single")
plot(dend3, main = "Average")
plot(dend4, main = "Centroid")

A função all.equal.dendrogram faz uma comparação global de duas ou mais árvores de dendrogramas. 

all.equal(dend1, dend1)
## [1] TRUE
all.equal(dend1, dend2)
## [1] "Difference in branch heights -  Mean relative difference: 0.4233225"
all.equal(dend1, dend2, use.edge.length = FALSE)
## [1] "Dendrograms contain diffreent edges (i.e.: topology). Unique edges in target: | 2, 6, 13, 14, 19 | Unique edges in current: 3, 9, 11, 13, 15"
all.equal(dend1, dend2, use.edge.length = FALSE, use.topology = FALSE)
## [1] TRUE
all.equal(dend2, dend4, use.edge.length = TRUE)
## [1] "Difference in branch heights -  Mean relative difference: 0.1261739"
all.equal(dend2, dend4, use.edge.length = FALSE)
## [1] "Dendrograms contain diffreent edges (i.e.: topology). Unique edges in target: | 9, 13 | Unique edges in current: 7, 13"
all.equal(dendlist(dend1, dend1, dend1))
## [1] TRUE
all.equal(dend1234)
##                                                                  1==2 
## "Difference in branch heights -  Mean relative difference: 0.4233225" 
##                                                                  1==3 
## "Difference in branch heights -  Mean relative difference: 0.1871149" 
##                                                                  1==4 
## "Difference in branch heights -  Mean relative difference: 0.3815751" 
##                                                                  2==3 
## "Difference in branch heights -  Mean relative difference: 0.4364853" 
##                                                                  2==4 
## "Difference in branch heights -  Mean relative difference: 0.1261739" 
##                                                                  3==4 
## "Difference in branch heights -  Mean relative difference: 0.2534605"
all.equal(dend1234, use.edge.length = FALSE)
##                                                                                                                                           1==2 
## "Dendrograms contain diffreent edges (i.e.: topology). Unique edges in target: | 2, 6, 13, 14, 19 | Unique edges in current: 3, 9, 11, 13, 15" 
##                                                                                                                                           1==3 
##   "Dendrograms contain diffreent edges (i.e.: topology). Unique edges in target: | 2, 5, 6, 13, 14 | Unique edges in current: 3, 4, 7, 13, 15" 
##                                                                                                                                           1==4 
## "Dendrograms contain diffreent edges (i.e.: topology). Unique edges in target: | 2, 6, 13, 14, 19 | Unique edges in current: 3, 7, 11, 13, 15" 
##                                                                                                                                           2==3 
##                  "Dendrograms contain diffreent edges (i.e.: topology). Unique edges in target: | 5, 9, 11 | Unique edges in current: 4, 7, 8" 
##                                                                                                                                           2==4 
##                       "Dendrograms contain diffreent edges (i.e.: topology). Unique edges in target: | 9, 13 | Unique edges in current: 7, 13" 
##                                                                                                                                           3==4 
##                "Dendrograms contain diffreent edges (i.e.: topology). Unique edges in target: | 4, 8, 13 | Unique edges in current: 5, 11, 13"


Podemos recolher galhos em um nível de tolerância usando a função collapse_branch: 

dend <- as.dendrogram(hcFF, method = "average")
par(mfrow = c(1,3))
dend %>% ladderize %>%  plot(horiz = TRUE); abline(v = 2, col = 2, lty = 2, lwd = 3)
grid()
box()
dend %>% collapse_branch(tol = 2) %>% ladderize %>% plot(horiz = TRUE)
grid()
box()
dend %>% collapse_branch(tol = 2) %>% ladderize %>% hang.dendrogram(hang = 0) %>% plot(horiz = TRUE)
grid()
box()


XIII.4.1. Matriz de distância


A função dist.dendlist calcula a distância Robinson-Foulds, também conhecida como diferença simétrica, entre dois dendrogramas. Esta é a soma das arestas em ambas as árvores com rótulos que existem em apenas uma das duas árvores. 

dist.dendlist(dend1234)
##          Complete Single Average
## Single         10               
## Average        10      6        
## Centroid       10      4       6


Tanto o Índice Gama de Baker (BK) quanto a correlação cofenética, que serão introduzidos em breve, podem ser calculados para criar uma matriz de correlação usando a função cor.dendlist, o método padrão é a correlação cofenética: 

cor.dendlist(dend1234)
##           Complete    Single   Average  Centroid
## Complete 1.0000000 0.7667324 0.6802689 0.5475042
## Single   0.7667324 1.0000000 0.8826974 0.8750081
## Average  0.6802689 0.8826974 1.0000000 0.9308297
## Centroid 0.5475042 0.8750081 0.9308297 1.0000000


A biblioteca corrplot oferece uma boa visualização: 

library(corrplot)
corrplot(cor.dendlist(dend1234), "pie", "lower")


O que nos diz facilmente que <Single, Average e Centroid fornecem resultados semelhantes, enquanto completo é um pouco diferente. 

dend1234 %>% tanglegram(which = c(2,3)) 


dend1234 %>% tanglegram(which = c(1,2), common_subtrees_color_branches = TRUE)


XIII.4.2. Índice Gama de Baker


O Índice Gama de Baker, veja o artigo Baker (1974), é uma medida de associação ou semelhança entre duas árvores de agrupamento hierárquico ou dendrogramas. É definida como a correlação de classificação entre os estágios em que os pares de objetos se combinam em cada uma das duas árvores.

Ou mais detalhado: é calculado pegando dois itens e vendo qual é o nível mais alto possível de \(k\), o número de grupos de clusters criados ao cortar a árvore, para o qual os dois itens ainda pertencem à mesma árvore. Esse \(k\) é retornado e o mesmo é feito para esses dois itens para a segunda árvore. Existem \(n\) mais de 2 combinações desses pares de itens dos itens da árvore e todos esses números são calculados para cada uma das duas árvores. Em seguida, esses dois conjuntos de números, um conjunto para os itens em cada árvore, são emparelhados de acordo com os pares de itens comparados e uma correlação de Spearman é calculada.

O valor pode variar entre -1 e 1. Com valores próximos de 0, significa que as duas árvores não são estatisticamente semelhantes. Para o \(p\)-valor exato, deve-se usar um teste de permutação. Uma dessas opções será permutar os rótulos de uma árvore muitas vezes, calculando a distribuição sob a hipótese nula, mantendo as topologias das árvores constantes.

Observe que esta medida não é afetada pela altura de um galho, mas apenas por sua posição relativa em comparação com outros galhos. 

cor_bakers_gamma(dend1, dend2)
## [1] 0.7015666


Mesmo que possamos alcançar o emaranhamento perfeito, a Gama de Baker nos mostra que a topologia da árvore não é idêntica. Ao contrário da correlação de uma árvore consigo mesma: 

dend01 <- dend1 %>% set("labels", rownames(FrenchFood)[order(rownames(FrenchFood))]) %>% match_order_by_labels(dend1)
cor_bakers_gamma(dend1, dend01)
## [1] -0.09388874


dend101 <- dendlist("No.1" = dend1, "No.01" = dend01)
dend101 %>% tanglegram(which = c(1,2))


Como as observações que criam o Índice Gama de Baker de tal medida são correlacionadas, precisamos realizar um teste de permutação para o cálculo da significância estatística do índice. Vejamos a distribuição do Índice Gama de Baker sob a hipótese nula, assumindo topologias de árvore fixas. Isso será diferente para diferentes estruturas e tamanhos de árvores.

Aqui estão os resultados quando a árvore comparada é ela mesma, depois de embaralhar seus próprios rótulos e ao comparar a árvore 1 com a árvore embaralhada 2: 

set.seed(23235)
the_cor <- cor_bakers_gamma(dend1, dend01)
the_cor2 <- cor_bakers_gamma(dend01, dend1)
the_cor
## [1] -0.09388874
R <- 100
cor_bakers_gamma_results <- numeric(R)
dend_mixed <- dend1
for(i in 1:R) {
   dend_mixed <- sample.dendrogram(dend_mixed, replace = FALSE)
   cor_bakers_gamma_results[i] <- cor_bakers_gamma(dend1, dend_mixed)
}
plot(density(cor_bakers_gamma_results),
     main = expression(paste("Distribuição da Gama de Baker sob ", H[0])),
     xlim = c(-1,1))
abline(v = 0, lty = 2)
abline(v = the_cor, lty = 2, col = 2)
abline(v = the_cor2, lty = 2, col = 4)
legend("topleft", legend = c("cor", "cor2"), fill = c(2,4))
round(sum(the_cor2 < cor_bakers_gamma_results)/ R, 4)
## [1] 0.65
title(sub = paste("One sided p-value:",
                  "cor =",  round(sum(the_cor < cor_bakers_gamma_results)/ R, 4),
                  " ; cor2 =",  round(sum(the_cor2 < cor_bakers_gamma_results)/ R, 4)
                  ))
grid()


Podemos ver que não temos evidências suficientes de que dend1 e dend01 são significativamente semelhantes, ou seja, com uma correlação maior que 0.

Também podemos construir um intervalo de confiança bootstrap, usando sample.dendrogram, para a correlação. Esta função pode ser muito lenta para árvores maiores, portanto, certifique-se de usá-la com cuidado: 

set.seed(23801)
R <- 100
dend1_labels <- labels(dend1)
dend2_labels <- labels(dend2)
cor_bakers_gamma_results <- numeric(R)
for(i in 1:R) {
   sampled_labels <- sample(dend1_labels, replace = TRUE)
   # members needs to be fixed since it will be later used in nleaves
   # os elementos precisam ser fixados pois serão usado posteriormente em folhas
   dend_mixed1 <- sample.dendrogram(dend1, 
                                    dend_labels=dend1_labels,
                                    fix_members=TRUE,fix_order=TRUE,fix_midpoint=FALSE,
                                    replace = TRUE, sampled_labels=sampled_labels
                                      )
   dend_mixed2 <- sample.dendrogram(dend2, dend_labels=dend2_labels,
                                    fix_members=TRUE,fix_order=TRUE,fix_midpoint=FALSE,
                                    replace = TRUE, sampled_labels=sampled_labels
                                      )                                    
   cor_bakers_gamma_results[i] <- cor_bakers_gamma(dend_mixed1, dend_mixed2, warn = FALSE)
}
par(mar=c(1,1,1,1))
tanglegram(dend1, dend2)


Podemos ver que não temos evidências suficientes de que dend1 e dend2 sejam significativamente semelhantes, ou seja, com uma correlação maior que 0.

Também podemos construir um intervalo de confiança bootstrap, usando sample.dendrogram, para a correlação. Esta função pode ser muito lenta para árvores maiores, portanto, certifique-se de usá-la com cuidado: 

dend1 <- dend1
dend2 <- dend01
set.seed(23801)
R <- 100
dend1_labels <- labels(dend1)
dend2_labels <- labels(dend2)
cor_bakers_gamma_results <- numeric(R)
for(i in 1:R) {
   sampled_labels <- sample(dend1_labels, replace = TRUE)
   dend_mixed1 <- sample.dendrogram(dend1, 
                                    dend_labels=dend1_labels,
                                    fix_members=TRUE,fix_order=TRUE,fix_midpoint=FALSE,
                                    replace = TRUE, sampled_labels=sampled_labels
                                      )
   dend_mixed2 <- sample.dendrogram(dend2, dend_labels=dend2_labels,
                                    fix_members=TRUE,fix_order=TRUE,fix_midpoint=FALSE,
                                    replace = TRUE, sampled_labels=sampled_labels
                                      )                                    
   cor_bakers_gamma_results[i] <- cor_bakers_gamma(dend_mixed1, dend_mixed2, warn = FALSE)
}
tanglegram(dend1, dend2)


# E aqui está o tanglegram para uma amostra de nossas árvores:
dend_mixed1 <- rank_order.dendrogram(dend_mixed1)
dend_mixed2 <- rank_order.dendrogram(dend_mixed2)
dend_mixed1 <- fix_members_attr.dendrogram(dend_mixed1)
dend_mixed2 <- fix_members_attr.dendrogram(dend_mixed2)
tanglegram(dend_mixed1, dend_mixed2)


cor_bakers_gamma(dend_mixed1, dend_mixed2, warn = FALSE)
## [1] 1
CI95 <- quantile(cor_bakers_gamma_results, probs=c(.025,.975))
CI95
##        2.5%       97.5% 
## -0.01881772  1.00000000


par(mfrow = c(1,1))
plot(density(cor_bakers_gamma_results),
     main = "Distribuição bootstrap Gama Baker",
     xlim = c(-1,1))
abline(v = CI95, lty = 2, col = 3)
abline(v = cor_bakers_gamma(dend1, dend2), lty = 2, col = 2)
legend("topleft", legend =c("95% CI", "Baker's Gamma Index"), fill = c(3,2))


A amostragem bootstrap pode fazer coisas estranhas com pequenas árvores. Neste caso tivemos muitas vezes que as duas árvores obtiveram correlação perfeita. O uso e a interpretação devem ser feitos com cuidado!


XIII.4.3. Correlação cofenética


A distância cofenética entre duas observações que foram agrupadas é definida como a dissimilaridade intergrupo na qual as duas observações são combinadas primeiro em um único agrupamento. Essa distância tem muitos vínculos e restrições. A correlação cofenética (ver Sokal, 1962) é a correlação entre duas matrizes de distância cofenética de duas árvores.

O valor pode variar entre -1 e 1. Com valores próximos de 0 significa que as duas árvores não são estatisticamente semelhantes. Para o \(p\)-valor exato, deve-se resultar em um teste de permutação. Uma dessas opções será permutar os rótulos de uma árvore muitas vezes e calcular a distribuição sob a hipótese nula, mantendo as topologias das árvores constantes. 

cor_cophenetic(dend1, dend2)
## [1] -0.02165874


A função cor_cophenetic é mais rápida que cor_bakers_gamma e pode ser preferida por esse motivo.


XIII.4.4. O índice de Fowlkes-Mallows e o gráfico \(B_k\)


O Índice Fowlkes-Mallows (ver Fowlkes, 1983) ou FM Index ou gráfico Bk é uma medida de similaridade entre dois agrupamentos. O índice FM varia de 0 a 1, um valor maior indica maior similaridade entre os dois clusters.

O pacote dendextend permite o cálculo do FM-Index, sua esperança e variância sob a hipótese nula e a criação de permutações do FM-Index sob \(H_0\). Graças ao pacote profdpm, temos outro exemplo de cálculo do FM (embora não ofereça a expectativa e a variação em H0): 

Bk(dend1, dend2, k = 3)
## $`3`
## [1] 0.2727273
## attr(,"E_FM")
## [1] 0.3333333
## attr(,"V_FM")
## [1] 0.006845313


No método Bk calculamos o índice de Fowlkes-Mallows (Bk) para cada \(k=2,3,\cdots,n-1\), número de clusters, dando a associação entre as duas árvores quando cada uma é cortada para ter \(k\) grupos. A semelhança entre dois dendrogramas de agrupamento hierárquico, pode ser investigada, usando o gráfico \((k,B_k)\): Para cada nível de divisão dos dois dendrogramas que produz \(k\) agrupamentos em cada árvore, o gráfico mostra o número Bk e portanto, permite a investigação de nuances potenciais na estrutura de similaridade.

O Bk mede o número de pares de itens que estão no mesmo cluster em ambos os dendrogramas, um dos clusters em uma das árvores e um dos clusters na outra árvore, dividido pela média geométrica do número de pares de itens que estão no mesmo cluster em cada árvore.

Sejam, \(a_{uv}=1\) ou \(b_{uv}=1\) se os itens \(u\) e \(v\) estão no mesmo cluster na primeira árvore e segunda árvore, quando é cortado para dar \(k\) clusters, caso contrário 0: \[ FM_K = B_k =\dfrac{\displaystyle \sum a_{uv}b_{uv}}{\displaystyle \sqrt{\sum a_{uv}\sum b_{uv}}}\cdot \]

A medida \(B_k\) pode ser mostrada para cada valor de \(k\), exceto \(k=n\), para criar o gráfico \((k,B_k)\). O gráfico compara a semelhança das duas árvores para diferentes cortes. A média e a variância de \(B_k\), sob a hipótese nula de que as duas árvores não são semelhantes e sob a suposição de que as margens da matriz correspondente são fixas, são dadas em Fowlkes and Mallows, ver Fowlkes (1983). Eles permitem inferir se os resultados obtidos são diferentes do que seria esperado sob a hipótese nula, de agora particular ordem dos rótulos das árvores.

As funções Bk e Bk_plot permitem o cálculo do índice de Fowlkes-Mallows para um intervalo de \(k\) valores em duas árvores. Aqui temos um exemplo: 

Bk_plot(dend1, dend2)
grid()


XIII.5. Boston Housing


As técnicas multivariadas apresentadas agora são aplicadas aos dados da Boston Housing. Concentramos nossa atenção em 14 variáveis transformadas e padronizadas. 

Boston.dataset = read.table("http://leg.ufpr.br/~lucambio/MSM/Bostondataset.txt", header = TRUE, sep = "")
Mediana = median(Boston.dataset$MEDV)
Boston.dataset$fMEDV <- factor(I(Boston.dataset$MEDV>Mediana), 
                               levels = c("TRUE","FALSE"), labels = c(1,0))
Boston.dataset[,16] = log(Boston.dataset[,1])
Boston.dataset[,17] = Boston.dataset[,2]/10
Boston.dataset[,18] = log(Boston.dataset[,3])
Boston.dataset[,19] = Boston.dataset[,4]
Boston.dataset[,20] = log(Boston.dataset[,5])
Boston.dataset[,21] = log(Boston.dataset[,6])
Boston.dataset[,22] = Boston.dataset[,7]^2.5/10000
Boston.dataset[,23] = log(Boston.dataset[,8])
Boston.dataset[,24] = log(Boston.dataset[,9])
Boston.dataset[,25] = log(Boston.dataset[,10])
Boston.dataset[,26] = exp(0.4*Boston.dataset[,11])/1000
Boston.dataset[,27] = Boston.dataset[,12]/100
Boston.dataset[,28] = sqrt(Boston.dataset[,13])
Boston.dataset[,29] = log(Boston.dataset[,14])
library(caret)
preObj <- preProcess(Boston.dataset[,16:29], method=c("center", "scale"))
newData <- predict(preObj, Boston.dataset[,16:29])
colnames(newData) <- colnames(Boston.dataset[,1:14])
par(mar=c(4,2,1,1), mfrow=c(1,7))
boxplot(newData[,1] ~ Boston.dataset$fMEDV, ylim = c(-5.1,4.0), 
        xlab = expression(paste(X[1])), col = c("red","cyan"))
grid()
boxplot(newData[,2] ~ Boston.dataset$fMEDV, ylim = c(-5.1,4.0), 
        xlab = expression(paste(X[2])), col = c("red","cyan"))
grid()
boxplot(newData[,3] ~ Boston.dataset$fMEDV, ylim = c(-5.1,4.0), 
        xlab = expression(paste(X[3])), col = c("red","cyan"))
grid()
boxplot(newData[,4] ~ Boston.dataset$fMEDV, ylim = c(-5.1,4.0), 
        xlab = expression(paste(X[4])), col = c("red","cyan"))
grid()
boxplot(newData[,5] ~ Boston.dataset$fMEDV, ylim = c(-5.1,4.0), 
        xlab = expression(paste(X[5])), col = c("red","cyan"))
grid()
boxplot(newData[,6] ~ Boston.dataset$fMEDV, ylim = c(-5.1,4.0), 
        xlab = expression(paste(X[6])), col = c("red","cyan"))
grid()
boxplot(newData[,7] ~ Boston.dataset$fMEDV, ylim = c(-5.1,4.0), 
        xlab = expression(paste(X[7])), col = c("red","cyan"))
grid()

par(mar=c(4,2,1,1), mfrow=c(1,7))
boxplot(newData[,8] ~ Boston.dataset$fMEDV, ylim = c(-5.1,4.0), 
        xlab = expression(paste(X[8])), col = c("red","cyan"))
grid()
boxplot(newData[,9] ~ Boston.dataset$fMEDV, ylim = c(-5.1,4.0), 
        xlab = expression(paste(X[9])), col = c("red","cyan"))
grid()
boxplot(newData[,10] ~ Boston.dataset$fMEDV, ylim = c(-5.1,4.0), 
        xlab = expression(paste(X[10])), col = c("red","cyan"))
grid()
boxplot(newData[,11] ~ Boston.dataset$fMEDV, ylim = c(-5.1,4.0), 
        xlab = expression(paste(X[11])), col = c("red","cyan"))
grid()
boxplot(newData[,12] ~ Boston.dataset$fMEDV, ylim = c(-5.1,4.0), 
        xlab = expression(paste(X[12])), col = c("red","cyan"))
grid()
boxplot(newData[,13] ~ Boston.dataset$fMEDV, ylim = c(-5.1,4.0), 
        xlab = expression(paste(X[13])), col = c("red","cyan"))
grid()
boxplot(newData[,14] ~ Boston.dataset$fMEDV, ylim = c(-5.1,4.0), 
        xlab = expression(paste(X[14])), col = c("red","cyan"))
grid()


O dendrograma para as 14 variáveis usando o método Ward é exibido abaixo. Observa-se dois clusters dominantes. Um refinamento adicional de, digamos, três clusters, poderia ser considerado em um nível mais baixo de distância. 

ddBoston <- dist(newData[Boston.dataset$fMEDV==0,1:14], method = "euclidean")
hcBoston <- hclust(ddBoston)
plot(hcBoston, axes=FALSE)
rect.hclust(hc,k=4, border = 3:4)
abline(h=5)
grid()
box()


hcdBoston = as.dendrogram(hcBoston)
plot(cut(hcdBoston, h = 5)$upper, main = "Árvore superior no corte em h = 5", type = "triangle")
grid()
box()


hcdBoston = as.dendrogram(hcBoston)
plot(cut(hcdBoston, h = 9)$upper, main = "Árvore superior no corte em h = 7")
grid()
box()


hc <- hclust(ddBoston)
par(cex=0.7, mar=c(5, 8, 4, 1))
plot(hc, xlab="", ylab="", main="", sub="", axes=FALSE, type = "fan")
par(cex=1)
title(xlab="", ylab="", main="Boston Housing")
axis(2)
rect.hclust(hc,k=4, border = 3:4)
grid()
box()


library(sparcl)
# # coloreando as folhas de um dendrograma
y = cutree(hc, 3)
ColorDendrogram(hc, y = y, labels = names(y), main = "Boston Housing", 
    branchlength = 80)
grid()
box()


XIII.6. Exercícios


  1. Repita o exemplo das notas bancárias, Exemplo XIII.6, com outro algoritmo de agrupamento.

  2. Repita o exemplo das notas bancárias, Exemplo XIII.6 ou o exemplo de 8 pontos, Exemplo XIII.5, com a norma \(L_1\).