Universidade Técnica de Lisboa
INSTITUTO SUPERIOR DE ECONOMIA E GESTÃO
Informática e Sistemas de Informação Aplicados em Economia
Descoberta de Conhecimento em Bases de Dados.
Pesquisa de Clusters
Descoberta de conhecimento em bases e dados.
Pesquisa de Clusters
- A análise de Clusters
- Étapas da análise de Clusters
- Métodos da análise de clusters
- Medidas de distância e semelhança
-
Critérios para agregação e desagregação de casos
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
2
A Análise de Clusters
Dado um conjunto de n indivíduos para os quais existe informação
sobre a forma de p variáveis, o método de Análise de Clusters
procede ao agrupamento dos indivíduos em função da informação
existente, de tal modo que
1. os indivíduos pertencentes a um mesmo grupo sejam tão
semelhantes quanto possível e
2. sempre mais semelhantes aos elementos do mesmo grupo do
que a elementos dos restantes grupos.
In: Estatística Multivariada Aplicada
Elizabeth Reis
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
3
Etapas da análise de clusters
- A selecção de indivíduos ou de uma amostra de indivíduos a
serem agrupados;
- A definição de variáveis a partir das quais será obtida a
informação necessária ao agrupamento dos indivíduos;
- A definição de uma medida de semelhança ou distância entre
cada dois indivíduos;
- A escolha de um critério de agregação ou desagregação dos
indivíduos, isto é, a definição de um algoritmo de partição /
classificação;
- Por último, a validação dos resultados encontrados.
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
4
A Selecção das Variáveis
Tem de atender a um duplo problema:
1. Escolher de entre os dados disponíveis quais os mais
significativos na abordagem do problema: conhecimento prévio
do investigador sobre o assunto a estudar;
2. Atender ao tipo de variáveis utilizadas (contínuas, rácios,
ordinais, nominais ou binárias), sobretudo quando estas estão
definidas em diferentes unidades de medida.
ESTANDARDIZAÇÃO
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
prévia
5
Os Métodos de Análise de Clusters
1. Técnicas de optimização: definido um critério de agrupamento,
a optimização indica qual deverá ser o grupo onde cada caso
será incluído; pressupõe que os casos pertencem a um número
k predeterminado de grupos;
2. Técnicas hierárquicas: que se podem subdividir em técnicas
aglomerativas e divisivas, ambas partindo de uma matriz de
semelhanças ou dissemelhanças (distâncias) entre os casos;
estes métodos conduzem a uma hierarquia de partições
P1,P2,...,Pn do conjunto de n objectos em 1, 2,..., n grupos.
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
6
Os Métodos de Análise de Clusters
3. Técnicas de densidade (density or mode-seeking): os grupos
são formados através da procura de regiões que contenham
uma concentração relativamente densa de casos.
4. Outras técnicas: que incluem aquelas em que se permite que
haja sobreposição dos grupos (fuzzy clusters) e todas as
restantes que não foram incluidas nas anteriores
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
7
Propriedades das Medidas de Semelhança /
Distância
1. Simetria: dados dois objectos, x e y, a distância entre eles
verifica a propriedade
d(x,y) = d(y,x) > o
2. Desigualdade triangular: dados três objectos, x, y e z, as
distâncias entre eles satisfazem a propriedade:
d(x,y) < d(x,z) + d(z,y)
3. Diferenciabilidade de não idênticos: dados dois objectos, x e y
d(x, y) ≠ 0 ⇒ x ≠ y
4. Indiferenciabílidade
idênticos, x e x'
de
idênticos:
dados
dois
objectos
d(x,x') = 0
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
8
Classificação dos Índices de (Dis)Semelhança
- Coeficientes de correlação
- Medidas de distância
- Coeficientes de associação
- Medidas de semelhança probabilística.
Todas estas medidas têm vantagens e desvantagens,
mas os mais utilizados nas ciências sociais são os dois primeiros
tipos.
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
9
Medidas de distância (1)
1. Distância Euclideana: a distância entre dois casos (i e j) é a raiz
quadrada do somatório dos quadrados das diferenças entre valores
de i e j para todas as variaveis (v = 1 2, , p)
p
∑ ( Xiv − Xjv)
dij =
2
v =1
2. Quadrado da Distância Euclideana: a distância entre dois
casos (i e j) é definida como o somatório dos quadrados das
diferenças entre os valores de i e j para todas as variáveis (V = 1, 2,
, p)
p
d
2
ij
=
∑ ( Xiv − Xjv)
2
v =1
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
10
Medidas de distância (2)
3. Distância absoluta ou City - Block Metric: a distância entre
dois elementos (í e j) é a soma dos valores absolutos das diferenças
entre os valores das variáveis (v = 1, 2...
p) para aqueles dois
casos:
p
dij =
∑ Xiv − Xjv
v =1
4. Distância de Minkowski: definida a partir da medida anterior,
pode ser considerada como a generalização da distância Euclideana
(as duas coincidem quando r=2):
1
r

r
dij = ∑ Xiv − Xjv 
 v =1

Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
p
11
Medidas de distância (3)
5. Distância
de
Mahalanobis
ou
distância
generalizada.
Considera a matriz de covanância X para o cálculo das distâncias:
onde Xi e Xj são os vectores de valores das variáveis para os
Dij=(Xi - Xj)' Σ-1 (Xi - Xj)
∼ ∼
∼ ∼
indivíduos i e j.
6. Distância de Chebishev: a distância entre dois casos i e j é o
valor máximo para todas as variáveis, das diferenças entre esses
dois indivíduos.
Dij = max | Xiv - Xjv |
v
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
12
Coeficientes de Associação (1)
Particularmente úteis para definir a semelhança entre indivíduos
caracterizados por variáveis qualitativas de tipo booleano:
0 - ausência da característica para determinado indivíduo e
1 - presença da característica.
Mais de trinta coeficientes de associação foram já propostos. Alguns
deles merecem tratamento particular:
- os coeficientes de emparelhamento simples,
- os coeficientes de Jaccard e de Gower,
- e o coeficiente de correlação para variáveis binárias.
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
13
Coeficientes de Associação (2)
Considerem-se os indivíduos i e j caracterizados por p variáveis
binárias e construa-se uma tabela de contingência do seguinte
modo:
INDIVÍDUO I
Totais
1
0
1
a
b
a+b
0
c
d
c+d
a+c
b+d
p=a+b+c+d
INDIVÍDUO J
Totais
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
14
Coeficientes de Associação (2)
"a" número de características que assumem o valor 1 em ambos os
indivíduos,
"b" o número de características com valor 1 no indivíduo j e 0 no
indivíduo i,
"c" o número de características presentes em i mas ausentes em j,
e
"d" as características simultaneamente ausentes em i e j.
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
15
Coeficientes de Emparelhamento Simples
(a + d )
Sij =
(a + b + c + d )
(b + c)
Dij =
(a + b + c + d )
- Sij é a relação entre o número de características presentes e ausentes
simultaneamente para os dois individuos e o número total de características, varia entre 0 e 1 e mede a semelhança entre cada dois indivíduos;
- Dij é o quociente entre o número de características presentes num dos
indivíduos e ausentes no outro e o número total de características, varia
entre 0 e 1 e mede a distância entre dois indivíduos.
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
16
Coeficientes de Jaccard
a
sij =
a +b+c
ou
b+c
dij =
a+b+c
evitam a contribuição da ausência conjunta de uma característica
para o cálculo da semelhança ou distância entre dois individuos.
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
17
Coeficientes Johnson e Wichern
COEFICIENTE
JUSTIFICAÇÃO
1) 2(a+d) / (2(a+d)+b+c) Peso duplo às presenças e ausências
simultâneas.
2) (a+d) / (a+d + 2(b+c)) Peso duplo às situações discordantes,
inclusão das ausências simultãneas
3) 2a / (2a + b + c)
Peso duplo às presenças simultâneas,
exclusão das ausências simultâneas.
4) a / (a + 2 (b + c)
Peso duplo às situações discordantes,
exclusão das ausências simultâneas
5) a / (b + c)
Quociente entre pesenças simultâneas e
situações discordantes, exclusão das
ausências simultâneas
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
18
O coeficiente de Gower
p
sij = ∑ s
v =1
ijv
/
p
∑w
ijv
v =1
sijv é o valor da semelhança entre os indivíduos i e j para a variável
v e Wijv é a ponderação a afectar à variável v e que será:
- 1 se a comparação para a variável v for considerada válida;
- 0 se a comparação não for considerada válida, por exemplo,
quando pelo menos um dos indivíduos apresenta uma nãoresposta para a variável em causa.
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
19
Agregação e Desagregação dos Casos (1)
Os vários métodos pretendem responder, de forma diferente, às seguintes
questões:
- distância entre indivíduos do mesmo grupo e distância entre indivíduos
de grupos diferentes;
- dispersão dos indivíduos dentro do grupo;
- densidade dos indivíduos dentro e fora dos grupos.
Diferem no modo como estimam distâncias entre grupos já formados e
outros grupos ou indivíduos por agrupar. O processo de agrupamento de
indivíduos já agrupados depende da distância entre os grupos. Portanto,
diferentes definições destas distâncias poderão resultar em diferentes
soluções finais.
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
20
Agregação e Desagregação dos Casos (2)
Não existe aquilo a que se possa chamar o melhor critério de
(des)agregação dos casos em análise de clusters.
É prática comum utilizar vários critérios e fazer a comparação dos
resultados. Se estes forem semelhantes, é possível concluir que se
obtiveram resultados com elevado grau de estabilidade e, portanto,
fiáveis.
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
21
Agregação e Desagregação dos Casos (3)
Os critérios de agregação mais utilizados são os seguintes:
1. Single linkage ou critério do vizinho mais próximo
2. Complete linkage ou critério do vizinho mais afastado
3. Critério da média dos grupos
4. Critério do centróide
5. Critério de Ward
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
22
Single Linkage ou Critério do Vizinho mais
Próximo
A semelhança entre dois grupos corresponde à semelhança máxima
entre dois casos quaisquer pertencentes a esses grupos, ou dito de
outro modo,
DOIS GRUPOS SÃO REAGRUPADOS NUM SÓ
DE ACORDO COM A DISTÂNCIA ENTRE OS SEUS CASOS MAIS PRÓXIMOS
Dados dois grupos (i, j) e (k), a distância entre os dois é a menor
das distâncias entre os elementos dos dois grupos:
d(i,j)k = min { dik; djk}
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
23
Complete Linkage ou Critério do Vizinho mais
Afastado
A distância entre dois grupos é agora definida como sendo a
distância entre os seus elementos mais afastados ou menos
semelhantes.
Dados dois grupos (i, j) e (k), a distância entre eles é a maior das
distâncias entre os seus elementos:
d(i,i)k = max (dik; djk)
O conjunto de elementos em cada grupo é mais semelhante a todos
os restantes elementos do grupo do que a qualquer dos elementos
dos restantes grupos.
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
24
Critério da Média dos Grupos
Esta estratégia de agrupamento define a distância entre dois
grupos, i e j, como sendo a média das distâncias entre todos os
pares de indivíduos constituídos por elementos dos dois grupos.
Vantagem: evitar valores extremos e tomar em consideração toda a
informação dos grupos. Um grupo passa a ser definido como um
conjunto de indivíduos no qual cada um tem mais semelhanças, em
média, com todos os membros do mesmo grupo do que com todos
os elementos de qualquer outro grupo.
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
25
Critério do Centróide
A distância entre dois grupos e definida como a distância entre os
seus centróides, pontos definidos pelas médias das variáveis
caracterizadoras dos indivíduos de cada grupo, isto é, o método do
centróide calcula a distância entre dois grupos como a diferença
entre as suas médias, para todas as variáveis.
Uma desvantagem deste método é que se os dois grupos forem
muito diferentes em termos de dimensão, o centróide do novo
agrupamento estará mas próximo daquele que for maior e as
características do grupo menor tenderão a perder-se.
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
26
Critério de Ward
Baseia-se na perda de informação resultante do agrupamento dos
indivíduos e medida através da soma dos quadrado dos desvios das
observações individuais relativamente à s médias do grupos em que
são classificadas.
Etapas:
- calcular as médias das variáveis para cada grupo;
- calcular o quadrado da distância Euclideana entre essas médias e
os valores das variáveis para cada indivíduo;
- somar as distâncias para todos os indivíduos;
- optimizar a variância mínima dentro dos grupos.
Descoberta de conhecimentos em bases de dados. Pesquisa de Clusters
27