Mineração de DadosClusterizaçã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 m-dimensional 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.

• Métodos partitivos

• Métodos hierárquicos

• Métodos baseados em densidade

Principais categorias de métodos de análise de cluster

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 m-dimensional. 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);

– };• };• };