Mineração de Dados
Clusterização
Felipe Carvalho – UFES 2009/2
Visão Geral
• Como vimos na seção anterior, métodos de classificação são baseados na
análise de itens previamente classificados (i.e., exemplos de treinamento),
ou seja, todas as classes possíveis são conhecidas e só precisamos
encontrar uma forma de diferenciar entre si os itens pertencentes a cada
uma delas. No entanto, há situações em que as classes possíveis não são
conhecidas de antemão e, portanto, não podemos usar classificação. Nestas
situações, precisamos de um método que nos permita agrupar os itens,
levando em conta apenas suas características intrínsecas: a análise de
cluster.
• Formalmente, a clusterização de um conjunto de itens D = {x1, x2, …, xn}
produz uma partição C = {C1, C 2, …, Ck}, tal que:
– Ci está contido em D é um cluster não vazio, para 1 <= i <= k
– C1 U C U U … U Ck = D
– Ci interseção Cj = vazio, para 1 <= i < j <= k
Visão Geral
• Para medir a similaridade entre itens, a análise de cluster se baseia na
proximidade entre os valores de seus atributos. Mapeando cada atributo
em uma coordenada unidimensional, itens compostos por m atributos
podem ser representados como pontos em um espaço euclidiano mdimensional e, assim, podemos medir a distância entre eles.
• A distância euclidiana entre dois pontos p = (p1,p2,…, pm) e q =
(q1,q2,…,qm) é definida como:
Exemplo
• Por exemplo, considere o conjunto de itens compostos pelos atributos
idade e renda, representando pessoas, apresentado na Tabela abaixo. A
partir dos valores dos atributos destes itens, podemos formar o gráfico
bidimensional apresentado na Figura, em que cada ponto representa um
item (ou pessoa) da Tabela.
Exemplo
• Como podemos observar na Figura, identificamos os agrupamentos pela
proximidade entre os pontos que representam seus itens, do mesmo
modo que um algoritmo de clusterização o faria. Para usar esses clusters
como classes, precisamos antes identificá-los e nomeá-los
adequadamente. Por exemplo:
– c1: “Crianças”. Nesse cluster temos apenas crianças, que não podem
trabalhar, portanto sua renda é nula.
– c2: “Jovens Iniciando a Carreira”. Nesse cluster temos pessoas com
idade próxima da idade mínima para poder trabalhar e, como
provavelmente não possuem formação superior nem experiência,
estas têm uma renda relativamente baixa.
Exemplo
– c3: “Profissionais com Curso Superior”. Nesse cluster temos pessoas
que já têm experiência e pelo patamar salarial provavelmente também
possuem formação superior.
– c4: “Altos Executivos”. Nesse cluster temos pessoas de certa idade que,
para ter uma renda tão alta em tal faixa etária, provavelmente fazem
parte do alto escalão gerencial.
– c5: “Profissionais sem Curso Superior”. Nesse cluster temos pessoas de
certa idade que, por terem uma renda relativamente baixa,
provavelmente não possuem curso superior.
• Obviamente, essa identificação e nomeação são apenas aproximadas e
ilustrativas. Após a identificação e nomeação dos clusters (ou classes),
podemos associar a cada item sua respectiva classe, de acordo com o
resultado da clusterização, e usar esses dados como exemplos de
treinamento para um algoritmo de classificação.
Principais categorias de métodos
de análise de cluster
• Métodos partitivos
• Métodos hierárquicos
• Métodos baseados em densidade
DBSCAN
• Seja R o raio que determina a região
de proximidade, ou vizinhança, ao
redor de um ponto representando
um item num espaço mdimensional. Se dois pontos p e q
são separados por uma distância
menor ou igual a e, então p e q são
ditos vizinhos (Figura abaixo).
DBSCAN
• Seja min a quantidade mínima de itens na vizinhança de um item p para
que este seja considerado um item central. Dados dois itens distintos p, q
pertencentes a D, dizemos que p está diretamente ao alcance de q, se p
está dentro da vizinhança de q e q é um item central. Por exemplo, supondo
min = 5 na Figura do slide anterior, temos que p está diretamente ao
alcance de q; porém, q não está diretamente ao alcance de p, pois este
último não é um item central. A menos que estejamos considerando dois
itens centrais, esta é uma relação assimétrica.
DBSCAN
• Dados dois itens distintos p, q
pertencentes a D, dizemos que p
está indiretamente ao alcance de q,
se existir uma seqüência de itens
p1,…, pn, sendo p1 = p e pn = q, de
forma que pi esteja diretamente ao
alcance de pi+1, para 1 <= i < n e pi
pertencente a D (Figura ao lado).
Esta é uma relação transitiva e, a
menos que p seja um item central,
esta relação também é assimétrica.
DBSCAN
• Dados dois itens distintos p, q pertencentes a D, dizemos que p está
conectado a q, se existe um item o pertencente a D tal que tanto p quanto q
estejam indiretamente ao alcance de o (Figura abaixo). Esta é uma relação
simétrica.
Algoritmo DBScan –
Formalmente Definido
•
•
•
•
•
•
DBSCAN(D, e, min){
i = 0;
Para cada item p de D {
– Se p não foi avaliado então {
• Marcar p como avaliado;
• Se número de vizinhos de p > min então {
– i = i + 1;
– Ci = Ci + p;
– Chamar expCluster (D, e, min, Ci, p);
• };
– };
};
retornar Ui Ci;
};
•
•
•
•
•
•
expCluster (D, e, min, Ci, p) {
Para cada vizinho v de p {
– O = O + v;
– Se v diferente Ci então Ci = Ci + v;
};
Para cada item q de O {
– Se q não foi avaliado então {
• Marcar q como avaliado;
• Se número de vizinhos de q >= min
então
• Chamar expCluster (D, e, min, Ci, q);
– };
};
};