2010: Agrupamento Evolutivo de Dados

Universidade Presbiteriana MackenzieFaculdade de Computação e Informática e Programa de Pós-Graduação em Engenharia Elétrica

Agrupamento Evolutivo de Dados1. Introdução.............................................................................................................2

1.1. Componentes da Tarefa de Agrupamento....................................................61.2. Complexidade da Tarefa de Agrupamento.................................................101.3. Agrupamento x Classificação.....................................................................121.4. Medidas de Proximidade............................................................................131.5. Tipos de Métodos de Agrupamento...........................................................15

2. Agrupamento Evolutivo de Dados.....................................................................182.1. Codificação.................................................................................................212.2. Operadores..................................................................................................242.3. Funções de Fitness......................................................................................30

3. Exemplo: Um Algoritmo Imunoevolutivo para Agrupamento de Dados..........343.1. Codificação e Refinamento dos Agrupamentos.........................................363.2. Mutação......................................................................................................363.3. Função de Fitness, Afinidade, Supressão...................................................393.4. Avaliação de Desempenho.........................................................................42

4. Discussão............................................................................................................50Material desenvolvido com base nas seguintes referências: WITTEN, I.H.; FRANK, E. Data Mining: Practical Machine Learning Tools and Techniques. Morgan Kaufmann Publishers, 2005. HAN, J.; KAMBER, M. Data Mining, Concepts and Techniques. Morgan Kaufmann, 2001. EVERITT, B. S.; LANDAU, S.; LEESE, M. (2001), Cluster Analysis. 4th Ed., Arnold. HRUSCHKA ET AL., “A Survey of Evolutionary Algorithms for Clustering”, IEEE Trans. on Syst., Man, and Cyb. – Part C, 39(2), PP. 133-155, 2009. Há também contribuições obtidas a partir de trabalhos do Prof. Dr. Eduardo Raul Hruschka.

Agrupamento Evolutivo de Dados - Leandro Nunes de Castro 1


1. Introdução

Uma das habilidades mais básicas dos organismos vivos é a capacidade de agrupar

objetos similares para produzir uma classificação.

A ideia de organizar coisas similares em categorias é bastante antiga e reflete a

capacidade de identificar características similares em alguns objetos, como forma,

cor, cheiro, posição, altura, etc.

Análise de grupos é um termo genérico usado para designar um amplo espectro de

métodos numéricos de análise de dados multivariados com o objetivo de descobrir

grupos ou clusters homogêneos de objetos.

O agrupamento de objetos em diferentes grupos ou clusters pode simplesmente

representar uma forma conveniente de organizar grandes bases de dados de

maneira que elas sejam mais facilmente compreendidas ou pesquisadas, como



também para realizar tarefas muito mais sofisticadas como tomada de decisão em

processos críticos.

Exemplos de aplicações potenciais:

o Medicina: identificação de categorias de diagnósticos, pacientes, remédios, etc.;

o Biologia: propor taxonomia para animais e plantas;

o Marketing: identificar grupos de clientes, produtos, serviços, etc.;

o Arqueologia: investigar relações entre diferentes tipos de objetos;

o Finanças: identificar o perfil de clientes fraudadores ou transações fraudulentas,

etc.

É importante salientar que, na maioria dos casos, há diferentes agrupamentos

possíveis para a mesma base de dados e, portanto, a utilidade de um agrupamento

depende do propósito da análise.

o Por exemplo, um conjunto de carros pode ser agrupado de acordo com a cor, o

consumo de combustível, o continente de fabricação, a fábrica, o peso, etc.



A análise de clusters, também denominada de agrupamento de dados (data

clustering), é a organização de um conjunto de objetos (normalmente

representados como vetores de características, ou seja, pontos em um espaço

multidimensional) em grupos baseado na similaridade.

Dito de outra forma, agrupar dados é o processo de particionar um conjunto de

dados em subconjuntos (clusters) de forma que os dados em cada cluster

(idealmente) compartilhem características comuns – normalmente proximidade em

relação a alguma medida de distância.

O agrupamento de dados é uma técnica comum em análise estatística de dados que

é usada em diversas áreas, incluindo aprendizagem de máquina, mineração de

dados, reconhecimento de padrões, análise de imagens e bioinformática.

Diversas outras nomenclaturas possuem significado similar, como taxonomia

numérica, análise de clusters, reconhecimento de padrões não-supervisionado e

análise tipológica.



Intuitivamente, objetos pertencentes ao mesmo grupo são mais similares entre si do

que a objetos pertencentes a grupos distintos.

Um cluster pode ser definido com base na coesão interna (homogeneidade) e

isolamento externo (separação) de seus objetos (Figura 1).

Figura 1: Exemplos de grupos de dados.

A variedade de técnicas para representar os dados, avaliar a proximidade

(similaridade) entre os dados e agrupar os dados produziu uma grande riqueza de

métodos de agrupamento.



Embora as técnicas de agrupamento possam ser usadas em diferentes contextos, é

importante que uma quantidade mínima de hipóteses sobre os dados seja usada

durante o processo de agrupamento, para que a análise não seja polarizada***.

1.1. Componentes da Tarefa de Agrupamento

A análise de grupos normalmente envolve as seguintes etapas:

1. Pré-processamento dos dados: correspondente a preparação dos dados para

agrupamento, podendo envolver limpeza, transformação, seleção de atributos,

etc.;

2. Definição da medida de proximidade: normalmente avaliada por uma função de

distância entre pares de objetos;

3. Agrupamento: pode ser efetuado por diferentes métodos e os grupos são hard

(cada objeto pertence a um único grupo) ou fuzzy (cada objeto possui um grau de

pertinência variável a um ou mais grupos).



4. Abstração dos dados: é o processo de extrair uma representação simples e

compacta do conjunto de dados. Por exemplo, uma abstração típica dos dados é

a descrição dos clusters através de protótipos, ou padrões representativos dos

clusters, como seu centroide.

5. Avaliação da saída: a avaliação da saída de um algoritmo de agrupamento

depende do contexto e dos objetivos da análise. Por exemplo, em uma análise

exploratória de uma base de dados de imóveis, objetos pertencentes ao mesmo

grupo podem permitir a identificação de perfis de moradores de um determinado

bairro. A saída do algoritmo de agrupamento também pode ser avaliada em

relação à validade do agrupamento; o que pode ser feito através de uma

avaliação externa, ou seja, os grupos encontrados são comparados com uma

estrutura conhecida a priori; uma avaliação interna, ou seja, tenta-se determinar

se a estrutura encontrada pelo algoritmo é apropriada aos dados; e uma



avaliação relativa, que compara duas estruturas avaliando o mérito relativo de

cada uma delas.

É importante salientar que nenhuma técnica de agrupamento é universalmente

aplicável e, além disso, diferentes técnicas podem permitir a extração de diferentes

informações de uma mesma base de dados.

Isso é consequência do fato de que muitos algoritmos assumem, implicitamente,

características específicas para as bases de dados.

Para ilustrar, considere o problema apresentado na Figura 2. Este problema,

conhecido como problema das duas espirais, não é resolvido corretamente por

grande parte dos métodos de agrupamento quando são usadas coordenadas

retangulares (apresentado na figura) para representar os dados. Porém, quando são

usadas coordenadas polares para os dados o problema torna-se facilmente

resolvível pela maioria dos algoritmos de agrupamento.



Figura 2: Problema das duas espirais representado em coordenadas retangulares.

É essencial, portanto, que o usuário de um algoritmo de agrupamento tenha um

bom conhecimento do método a ser empregado, saiba detalhes do processo de

aquisição e pré-processamento dos dados, e tenha um bom conhecimento de

domínio.



1.2. Complexidade da Tarefa de Agrupamento

A maioria dos algoritmos de agrupamento se concentra em obter k grupos de

objetos semelhantes de acordo com algum critério pré-estabelecido.

O número de possibilidades de se classificar N objetos em k grupos é dado por:

N(N,k) = (1)

Por exemplo, existem N(25,5) = 2.436.684.974.110.751 formas de classificar 25

objetos em 5 grupos.

Dessa maneira, pode-se perceber a complexidade de se agrupar corretamente uma

base de dados de 25 objetos em 5 grupos.

Ao considerar que o valor de k é desconhecido, o número total de maneiras de se

agrupar N objetos em k grupos é:

(2)



De uma maneira mais formal, o problema de se encontrar uma solução ótima para

a separação de N objetos em k grupos é NP-difícil e, devido ao fato de que o

número de separações possíveis desses N objetos em k grupos aumenta

aproximadamente na razão kN/k!, a tentativa de se encontrar uma solução ótima

globalmente é usualmente inviável sob o ponto de vista computacional.

Por outro lado, a escolha do valor de k é uma tarefa complicada, pois alguns desses

valores não implicam em partições naturais.

Nesse sentido, pode-se rodar o algoritmo de agrupamento diversas vezes, variando-

se o valor de k, para depois escolher a solução cujas características se parecem

melhores ou, ainda, aquelas soluções que forneçam a interpretação mais

significativa dos dados. Esta estratégia frequentemente assume um certo

conhecimento de domínio.

Uma alternativa se constitui em escolher a melhor solução – valor mais adequado

de k – de acordo com algum critério numérico.



A determinação do número ótimo de grupos em um conjunto de dados é um dos

mais difíceis aspectos do processo de agrupamento.

1.3. Agrupamento x Classificação

É importante perceber a diferença entre agrupamento e classificação de dados.

Na classificação os dados de entrada do algoritmo são rotulados, sendo que a

tarefa do algoritmo de classificação é identificar a classe à qual um novo dado,

ainda não visto, pertence.

Normalmente, os dados rotulados são apresentados ao algoritmo de classificação

(ou estimação) para que ele seja treinado, ou seja, para criar um ‘modelo’ capaz de

classificar (estimar) corretamente novos dados.

No caso do agrupamento, o problema consiste em agrupar um conjunto de dados

não-rotulados em grupos (ou clusters) que tenham algum significado ou utilidade

prática.



De certa forma, os rótulos dos dados estão associados aos grupos, porém eles serão

obtidos apenas a partir do algoritmo de agrupamento e não serão usados durante o

processo de treinamento do algoritmo.

1.4. Medidas de Proximidade

Um elemento central no processo de identificação de grupos é a avaliação da

‘proximidade’ entre objetos.

A maioria dos métodos de agrupamento assume, como ponto de partida, uma

matriz de dados de dimensão N L que representa N objetos de dimensão L cada:

, (3)

onde cada objeto da base de dados está representado por um vetor linha xi de

dimensão L, i = 1, ... , N.

Uma outra estrutura de dados muito comum é a matriz de dissimilaridade, com

dimensão N N, na qual cada elemento da matriz corresponde a uma medida



quantitativa da proximidade (ou equivalentemente da dissimilaridade d(i,j) ou dij)

entre pares de objetos:

(4)

A matriz de dados também é denominada de matriz de dois-modos (as linhas

representam elementos distintos das colunas), enquanto a matriz de dissimilaridade

também é denominada de matriz de um-modo (ambas linhas e colunas representam

dissimilaridade).

Grande parte dos algoritmos de agrupamento utiliza medidas de dissimilaridade

para avaliar, indiretamente, a proximidade entre objetos.

Para isso, é preciso identificar primeiramente se a base de dados possui dados do

tipo categórico, numérico ou ambos.



1.5. Tipos de Métodos de Agrupamento

Há diversos algoritmos de agrupamento na literatura e a escolha de um deles

depende da aplicação e do tipo de dados disponíveis.

Considere uma base de dados X = {x1, x2, ..., xN} com N objetos, onde xj, j = 1, ...,

N, corresponde a um vetor de dados com L atributos. Uma partição dos dados é

uma coleção C = {C1, C2, ..., Ck} de k subconjuntos, Ci , tal que C1 C2

... Ck = X.

De forma abrangente os métodos podem ser divididos em:

1. Hierárquicos: os métodos hierárquicos criam uma decomposição hierárquica

dos dados. Estes métodos podem ser aglomerativos ou divisivos, baseado em

como o processo de decomposição é efetuado.

a. Os métodos aglomerativos começam com cada objeto pertencendo a um

grupo e unem sucessivamente objetos em grupos de acordo com a



proximidade entre eles até que um critério de parada seja atingido (por

exemplo, houver um único grupo contendo todos os objetos).

b. Os métodos divisivos começam com todos os objetos fazendo parte do

mesmo grupo e particionam sucessivamente os grupos em grupos

menores, até que um critério de parada seja atingido (por exemplo, cada

objeto pertença a um grupo distinto);

2. Particionais: dado um conjunto com N objetos, um método particional constrói

k partições dos dados, sendo que cada partição representa um cluster (k N).

Dado o número k de partições, um método particional cria uma partição inicial e

emprega um algoritmo de realocação iterativa que tem por objetivo melhorar o

particionamento movendo objetos entre grupos.

3. Não-Exclusivos (overlapping): dado um conjunto com N objetos, os métodos

não-exclusivos permitem que um objeto pertença completamente (soft) ou

parcialmente (fuzzy) a mais de um grupo simultaneamente.



Outras características dos algoritmos também podem ser usadas para classificá-los

como:

1. Monotéticos x Politéticos: corresponde ao uso sequencial ou simultâneo dos

atributos no processo de agrupamento. A maioria dos algoritmos é politética, ou

seja, todos os atributos são usados para calcular a distância entre os objetos;

2. Hard x Fuzzy: em um agrupamento hard cada objeto pertence a um único grupo,

Ci Cj = ; enquanto um agrupamento fuzzy atribui graus de pertinência aos

grupos para cada um dos objetos da base, neste caso a condição Ci Cj = é

relaxada;

3. Determinístico x Estocástico: métodos determinísticos apresentam sempre o

mesmo agrupamento, independentemente de parâmetros do algoritmo e/ou

condição inicial; os algoritmos estocásticos podem apresentar diferentes

soluções dependendo dos parâmetros e/ou condição inicial. Obs.: outros fatores

podem influenciar, como a ordem de apresentação dos objetos.



2. Agrupamento Evolutivo de Dados

Sob uma perspectiva de otimização, o agrupamento pode ser considerado um tipo

específico de problema NP-hard (Seção 1.2).

Essa característica tem estimulado o desenvolvimento de algoritmos eficientes de

busca e otimização para resolver o problema de agrupamento de dados, incluindo a

pesquisa sobre métodos heurísticos de propósito geral.

Particularmente, os algoritmos evolutivos se constituem em heurísticas

amplamente aplicadas e, muitas vezes, efetivas na solução de problemas NP-hard,

fornecendo soluções quase-ótimas para esta classe de problemas em tempo

aceitável.

Sob essa perspectiva, uma vasta gama de algoritmos evolutivos para agrupamento

de dados tem sido proposta na literatura e estes são baseados na otimização de

alguma função objetivo, conhecida como função de custo ou função de fitness.



Os algoritmos evolutivos essencialmente evoluem soluções de agrupamento

através de operadores que usam regras probabilísticas para processar partições de

dados amostradas a partir de um espaço de busca.

o De forma simples, partições com melhores valores de fitness possuem maiores

probabilidades de serem amostradas.

o Assim, a busca evolutiva é polarizada pelas melhores soluções de agrupamento e

tende a realizar uma exploração mais eficiente do espaço de busca do que os

métodos tradicionais de amostragem aleatória, por exemplo, múltiplas

inicializações do k-means.

o Além disso, a utilização de uma função de custo explícita permite,

diferentemente do caso dos algoritmos apresentados anteriormente, avaliar a

qualidade relativa das soluções de agrupamento sendo propostas e melhorá-las

iterativamente visando maximizar a performance do algoritmo de agrupamento

sob a ótica da função-objetivo proposta.



Essa seção faz uma revisão de alguns algoritmos evolutivos para agrupamento de

dados, considerando os seguintes elementos:

o Representação das soluções candidatas (codificação);

o Operadores;

o Função de fitness.

Para ilustrar os algoritmos em estudo, considere a seguinte base de dados

hipotética:

x1 = (1,1), C1.

x2 = (1,2), C1.

x3 = (2,1), C1.

x4 = (2,2), C1.

x5 = (10,1), C2.

x6 = (10,2), C2.

x7 = (11,1), C2.

x8 = (11,2), C2.

x9 = (5,5), C3.

x10 = (6,6), C3.



2.1. Codificação

Os três principais tipos de codificação propostos na literatura para agrupamento de

dados com algoritmos evolutivos são: binário, inteiro e real.

o Codificação binária: cada solução de agrupamento (partição) é normalmente

representada por uma cadeia binária de comprimento N, sendo N a quantidade

de objetos da base. Cada posição da cadeia corresponde a um objeto da base e o

valor do gene i é 1 se o objeto i for um protótipo e 0 caso contrário. Esse tipo de

representação leva a um algoritmo do tipo baseado em medoides, pois um objeto

da base torna-se um protótipo do grupo ou não.

Ex.: Se assumirmos que os objetos 1, 5 e 9 são protótipos da base numa solução

candidata qualquer, então temos a seguinte representação para este genótipo:

[1000100010].

Uma representação binária alternativa envolve o uso de uma matriz de dimensão

k × N para cada indivíduo, sendo que as linhas representam os grupos e as



colunas representam os objetos. Neste caso, se o j-ésimo objeto pertence ao i-

ésimo grupo, então o valor 1 é colocado no i-ésimo elemento da j-ésima coluna

do genótipo, enquanto os demais valores permanecem em 0.

Ex.: Se assumirmos a partição original da base de dados (objetos 1 a 4 C1,

objetos 5 a 8 C2, e objetos 9 e 10 C3), então temos a seguinte representação

para este genótipo:

1 1 1 1 0 0 0 0 0 00 0 0 0 1 1 1 1 0 00 0 0 0 0 0 0 0 1 1

o Codificação inteira: Numa possível codificação inteira para as soluções de

agrupamento, um genótipo é um vetor inteiro de N posições (N = número de

objetos da base), sendo cada posição correspondente ao rótulo do grupo ao qual

um objeto particular pertence.



Ex.: Se assumirmos a partição original da base de dados (objetos 1 a 4 C1,

objetos 5 a 8 C2, e objetos 9 e 10 C3), então temos a seguinte representação

para este genótipo: [1111222233]. Note que essa codificação é naturalmente

redundante e, portanto, o tamanho do espaço de busca é muito maior que o

espaço original de possíveis soluções.

Uma representação inteira alternativa envolve o uso de um arranjo de k

elementos numa representação baseada em medoides, sendo que cada elemento

do vetor corresponde ao número do objeto que é o medoide do grupo k.

Ex.: Se assumirmos que os objetos 2, 6 e 10 são os medoides dos grupos, então

o vetor que representa os protótipos (soluções candidatas) é: [2 6 10].

o Codificação real: Na codificação real, os genótipos correspondem a números

reais que representam as coordenadas dos protótipos dos grupos. Se o genótipo

codifica k grupos em um espaço de dimensão L, então o comprimento de cada

genótipo é L.k.



Ex.: O genótipo [1.5 1.5 10.5 1.5 5.5 5.0] codifica os protótipos (1.5 1.5), (10.5

1.5), (5.5 5.0).

2.2. Operadores

Quando operadores genéticos tradicionais de cruzamento e mutação são utilizados

em problemas de agrupamento, eles simplesmente manipulam os valores dos genes

sem considerar suas interrelações.

No entanto, no contexto de agrupamento de dados, as interrelações entre genes

devem constituir o objetivo primário do processo de otimização.

Portanto, é importante se atentar para a necessidade de desenvolver operadores

genéticos orientados à tarefa de agrupamento de dados.

Vamos considerar alguns operadores específicos com base nos três principais tipos

de codificação:



Operador de Cruzamento (Crossover)

o Codificação binária: Um operador tipicamente usado para codificação binária é

o crossover uniforme, através do qual os genótipos dos pais trocam bits. Note

que, caso k seja fixo, esse operador pode levar ao surgimento de soluções

candidatas com um número de protótipos maior ou menor que k.

o Codificação inteira: Uma maneira de combinar soluções de agrupamento

advindas de diferentes genótipos é: dados dois genótipos G1 e G2 com,

respectivamente, k1 e k2 grupos, um número c, c {1, 2, ..., k1}, de grupos é

selecionado aleatoriamente de G1 e copiado para G2. Os grupos de G2 que não

sofrem alteração são mantidos e aqueles mudados têm seus objetos não afetados

alocados nos grupos mais próximos. Dessa forma obtemos o descendente G3 e,

similarmente, obtemos o descendente G4.

Ex.: Para ilustrar esse procedimento, considere os seguintes genótipos:

G1 = 1123245125432533424



G2 = 1212332124423221321

Vamos assumir que os grupos {2, 3} de G1 foram aleatoriamente selecionados:

G1 = 1123245125432533424

Quando estes grupos são copiados para G2, eles modificam os grupos 1, 2 e 3 de

G2, enquanto o grupo 4 não é alterado.

G2 = 1223232124432233321

As posições sublinhadas, que correspondem aqueles genes indiretamente

afetados pelos grupos 2 e 3 de G1 agora são mudados para 0:

G3 = 0023200024432033020

Os genes setados em zero deverão ser colocados nos grupos mais próximos já

codificados por G3. O mesmo procedimento é aplicado para se obter um

descendente G4, exceto pelos grupos selecionados para serem copiados em G1.

Estes grupos agora são os grupos de G2 inicialmente mudados para gerar o

descendente G3, ou seja, 1, 2 e 3.



o Codificação real: Operadores de crossover de um ponto ou dois pontos (single-

point ou two-points) não são sensíveis a contexto, ou seja, não consideram as

interrelações entre os grupos no momento do cruzamento. Isso pode gerar,

dentre outras coisas, soluções inválidas, particionamentos com dois centroides

iguais, etc. Operadores de cruzamento específicos podem ser pensados, como:

Crossover aleatório: selecione aleatoriamente k/2 centroides de cada um dos

pais e troque entre si; centroides duplicados são substituídos por sorteios

aleatórios.

Distância do centroide: os grupos são inicialmente ordenados com base na

distância deles ao centroide da base de dados. Os grupos mais próximos deste

centroide global são denominados de grupos centrais e os demais de grupos

remotos. Um descendente é criado tomando-se os grupos centrais de um dos

pais e os grupos remotos do outro pai.



Crossover par a par: os grupos codificados em diferentes pais são pareados de

acordo com a similaridade de seus centroides. Um descendente é gerado

tomando-se aleatoriamente um centroide de cada par de grupos.

Crossover par a par por vizinho mais próximo (pairwise nearest neighbor

crossover): os 2k centroides de dois pais podem ser agrupados em k grupos

que formarão o descendente.

Operador de Mutação

o Codificação binária: Uma forma de mutar genótipos binários codificados como

visto anteriormente é simplesmente alternar bits do genótipo, o que corresponde

a deletar protótipos existentes ou inserir novos protótipos.

o Codificação inteira: No caso de uma codificação inteira na qual cada posição do

genótipo representa o rótulo de um objeto da base, diferentes tipos de

operadores de mutação podem ser empregados:

Troca aleatória do rótulo de objetos probabilisticamente selecionados;



Troca do valor de um gene dependendo da distância dos centroides dos

grupos em relação ao objeto correspondente. Especificamente, a

probabilidade de trocar o valor de um gene de um dado objeto é maior se o

centroide do grupo correspondente está mais próximo do objeto.

Para a representação alternativa baseada nos medoides, é possível selecionar

aleatoriamente um medoide e substituí-lo por outro objeto da base, de acordo

com uma probabilidade pré-determinada.

Nota: Nos casos em que o algoritmo evolutivo permite a determinação

automática do número k de grupos da base, é comum o uso de operadores de

mutação que permitem a criação de novos grupos (rótulos), a remoção de

grupos e a mudança de grupo de um determinado objeto. Um caso desses será

apresentado posteriormente.

o Codificação real: Para este tipo de codificação também é possível projetar

diferentes tipos de operadores de mutação:



Perturbar suavemente os centroides codificados em cada genótipo;

Substituir protótipos por objetos da base de dados, o que aumenta a

probabilidade de se criar ou eliminar grupos através da mutação.

2.3. Funções de Fitness

Muitos critérios de validação de agrupamentos podem ser usados para avaliar

partições contendo um número k de grupos.

Vários destes critérios podem ser adaptados e usados como função de fitness de

algoritmos evolutivos para agrupamento.

Portanto, as funções de fitness usadas em algoritmos evolutivos representam

apenas um subconjunto das possíveis funções de fitness a serem usadas. Vejamos

algumas delas:

o Representação baseada em medoide:



Soma das distâncias intra-cluster : Minimização da soma das distâncias entre

os objetos da base X = {x1, x2, ..., xN} e os medoides do conjunto {m1, m2, ...,

mk} {x1, x2, ..., xN}. Para isso é definido o critério de fitness:

, (5)

onde m representa o medoide mais próximo do objeto xi, d(xi,m) = minj

d(xi,mj) e d(,) corresponde a medida de distância.

o Representação baseada em centroide:

Soma das distâncias intra-cluster : Minimização da soma das distâncias entre

os objetos da base X = {x1, x2, ..., xN} e os centroides dos grupos {c1, c2, ...,

ck}. Para isso é definido o critério de fitness:

, (6)

onde {C1, ..., Ck} é o conjunto de k grupos codificados no genótipo, xi é um

objeto da base e cj é o centroide do grupo Cj.



o Independente de representação:

MaxInter-MinIntra : A função de fitness abaixo maximiza a distância

intergrupo dinter enquanto minimiza a distância intragrupo dintra e está associada

a cada genótipo:

(7)

onde dinter(Cj) é a distância entre o grupo Cj e o conjunto de todos os outros

grupos e dintra(Cj) é a distância intragrupo de Cj, e w é um peso associado a

distância integrupo definido pelo usuário.

Silhueta : Seja um objeto xi pertencente a um grupo A e a dissimilaridade

média entre os outros objetos de A em relação a xi denotada por a(xi). Seja

outro grupo C; a dissimilaridade do objeto i em relação aos objetos de C é

denotada por d(xi,C). Após o cálculo de d(xi,C) para todos os grupos C ≠ A, o

de menor valor é escolhido, ou seja, b(xi) = min d(xi,C), C ≠ A. Este valor

representa o valor do objeto xi para o grupo mais próximo:



(8).

O valor s(xi) [1, +1], sendo que quanto maior o valor de s(xi) maior é a

proximidade do objeto xi com um dado grupo. Se o valor de s(xi) for zero,

então não é possível definir claramente se este objeto xi deveria estar no grupo

atual ou em outro grupo próximo. Se um grupo A possui apenas um valor

então s(xi) não é definida e é considerada zero. O critério da Silhueta é dado

pela média de s(xi), i = 1, ..., N e a melhor forma de agrupamento é encontrada

maximizando esta função.

3. Exemplo: Um Algoritmo Imunoevolutivo para Agrupamento de Dados

Os algoritmos evolutivos possuem sua inspiração na Teoria da Evolução das

espécies de Charles Darwin.



Esses algoritmos são capazes de encontrar boas soluções em tempo computacional

razoável e, por este motivo, eles são utilizados como opção para a solução de

problemas complexos.

O princípio da evolução é o conceito primário que liga todos os seres vivos em

uma corrente singular de eventos.

Cada espécie presente nesta corrente é produto de um conjunto de eventos

específicos sobre uma pressão seletiva aplicada pelo ambiente nos organismos.

Ao longo de gerações, seleção natural e variações formam-se os indivíduos melhor

adaptados ao ambiente.

A ocopt-aiNet é um algoritmo imunoevolutivo proposto para combinar conceitos

de sistemas imunológicos artificiais e algoritmos evolutivos capaz de encontrar

particionamentos ótimos em bases de dados que apresentam grupos naturais de

dados.



O algoritmo ocopt-aiNet foi desenvolvido com o objetivo de minimizar alguns dos

inconvenientes encontrados nos algoritmos clássicos de agrupamento, a saber, a

proposição de uma única solução de agrupamento a cada execução, a necessidade

de especificação a priori do número de grupos da base, e a busca local em torno de

uma região específica do espaço.

Sendo assim, o algoritmo ocopt-aiNet apresenta as seguintes características:

o Determinação automática do número de grupos da base;

o Ampla exploração do espaço de busca;

o Geração de múltiplos particionamentos simultâneos para a base de dados,

permitindo uma análise mais exploratória e multimodal da base.

3.1. Codificação e Refinamento dos Agrupamentos

A codificação do algoritmo ocopt-aiNet incorpora o rótulo de cada grupo da base

de dados na codificação. Exemplo:

Célula 1- [111122221133333]



Após a geração da população inicial é utilizado o algoritmo k-médias para o

refinamento (busca local) dos grupos codificados pelas células.

O objetivo desse refinamento é o de executar uma aproximação do objetivo do

algoritmo de encontrar agrupamentos ótimos de dados, manipulando cada célula da

rede para uma melhor organização.

3.2. Mutação

São utilizados três operadores de mutação no algoritmo ocopt-aiNet: Exclusão,

Divisão e Transformação. Apenas um operador de mutação pode ser aplicado para

cada célula, com probabilidade 1 – f(i).

Os Operadores de Exclusão e Divisão tem probabilidade Pm = 25% de serem

aplicados, enquanto o Operador de Transformação tem probabilidade Pm = 50%

de ser aplicado.

Operador de Exclusão

Célula 1 – [113413422134433]



Operador de Divisão

Célula 2 – [113413413134433]



Operador de Transformação

Esse operador verifica se o objeto correspondente à posição encontra-se no grupo

correto.



Para isso é verificada a similaridade do objeto aos centroides dos grupos formados

pela célula:

o Caso ele esteja no grupo correto, ou seja, tenha similaridade maior com o

centroide de seu próprio grupo do que com os dos outros, seu rótulo é

mantido;

o Caso exista um centroide de outro grupo com o qual este objeto tenha maior

similaridade do que com o centroide do grupo a que ele está alocado, então o

rótulo é alterado para o desse centroide com maior similaridade.

3.3. Função de Fitness, Afinidade, Supressão

A função de fitness usada na ocopt-aiNet foi a Silhoueta, apresentada

anteriormente.

No algoritmo imunológico a afinidade tem como objetivo principal suprimir

células que apresentem codificações de agrupamentos semelhantes.



Para o algoritmo ocopt-aiNet a afinidade das células mantidas para a próxima

geração é calculada a partir da quantidade de objetos rotulados para um mesmo

grupo em duas células de memória, mesmo que rótulos distintos sejam usados para

codificar os mesmos grupos.

na qual Af(a,b) é o valor da afinidade entre as Células a e b, Ni representa o total

de objetos rotulados em um mesmo grupo nas Células a e b e N representa o

número total de objetos de uma célula.



1. Iniciar a população com N células aleatoriamente.2. Enquanto valor médio do número de grupos de w tem diferença menor que

, faça2.1. *Aplicar refinamento de agrupamentos as células da rede.2.2. Avaliar cada célula de acordo com seu fitness.2.3. Aplicar normalização linear no fitness.2.4. Gerar um número Nc de clones para cada célula pai.2.5. Aplicar mutação proporcional o fitness da célula pai, mantendo

célula pai.2.6. Determinar o fitness de todas as células da população.2.7. Para cada clone, selecionar o de maior fitness e calcular o fitness

médio da população selecionada.2.8. Se diferença entre fitness médio da população em relação ao fitness

médio da iteração anterior for menor que , continuar. Senão, voltar ao Passo 2.

2.9. Determinar a afinidade de todas as células na população. Suprimir as células com afinidade menor que o limiar de supressão ().

2.10. Introduzir um percentual d% de células geradas aleatoriamente e retornar ao Passo 2.

3. Fim Enquanto.



3.4. Avaliação de Desempenho

Parâmetros do algoritmo

o N = 20; Nc = 10; k = 10.

o = 0.001; = 0.001; w = 20.

o = 0.1; d = 10%.

o k-médias: max_it = 5.

Bases de dados: Auto MPG, Animais, Ruspini, Yeast.

Base Auto MPG:

FUNÇÃO OBJETIVO

Max Méd Min Desvio

ocopt-aiNet v1 0,74347 0,73004 0,66453 0,02317

ocopt-aiNet v2 0,73714 0,72536 0,71330 0,00795

EAC 0,77486 0,77486 0,77486 ---

k-médias 0,77486 0,49982 0,42565 0,13564Função objetivo para a base Auto MPG.



DIVERSIDADE NRO. DE INDIVÍDUOS

Max Méd Min Desvio Max Méd Min Desvio

ocopt-aiNet v1 0,5116 0,4890 0,466 0,0178 13,00 11,4 9,0 1,174

ocopt-aiNet v2 0,5187 0,4365 0,365 0,0397 41,00 30,5 26,0 4,089

EAC 0,0000 0,0000 0,000 --- 1,00 1,00 1,0 ---

k-médias 0,3705 0,2542 0,000 0,1294 --- --- --- ---

Diversidade e número de soluções para a base Auto MPG.

NÚMERO DE GRUPOS

Max Méd Min Desvio

ocopt-aiNet v1 5,33333 5,22984 5,00000 0,09249

ocopt-aiNet v2 7,87500 7,40105 6,82758 0,28392

EAC 2,00000 2,00000 2,00000 ---

k-médias 6,60000 4,30000 2,00000 1,74814

Número de grupos nas soluções para a base Auto MPG.



TEMPO COMPUTACIONAL (hh:mm:ss)

Max Méd Min Desvio

ocopt-aiNet v1 00:46:58 00:17:49 00:03:21 00:14:11

ocopt-aiNet v2 02:12:36 00:55:04 00:11:06 00:41:13

EAC 00:35:39 00:31:50 00:30:19 00:01:32

k-médias 00:00:00 00:00:00 00:00:00 ---

Tempo computacional para a base Auto MPG.

Grupo Carro MPG Cil. Desl. Pot. Peso Aceleração Ano Origem

1

Ford 20,2 6 200 88 3060 17,1 81 1

Chrysler 17,6 6 225 85 3465 16,6 81 1

Chevrolet 15 8 400 150 3761 9,5 70 1

Buick 14 8 455 225 3086 10 70 1

2

Toyota 24 4 113 95 2372 15 70 3

Datsun 27 4 97 88 2130 14,5 70 3

Volkswagen 26 4 97 46 1835 20,5 70 2

Peugeot 25 4 110 87 2672 17,5 70 2



Agrupamento da base Auto MPG pelo EAC.

Grupo Carro MPG Cil. Desl. Pot. Peso Aceleração Ano Origem

1

Datsun 32 4 85 70 1990 17 76 3Toyota 28 4 97 75 2155 16,4 76 3Honda 31,5 4 98 68 2045 18,5 77 3Renault 36 4 79 58 1825 18,6 77 2

2

Dodge 28 4 98 80 2164 15 72 1Ford 19 4 122 85 2310 18,5 73 1

Chevrolet 25 4 140 75 2542 17 74 1Dodge 28 4 90 75 2125 14,5 74 1

3

Ford 21 6 200 85 2587 16 70 1Amc 21 6 199 90 2648 15 70 1

Plymouth 22 6 198 95 2833 15,5 70 1Amc 18 6 199 97 2774 15,5 70 1

4

Datsun 27 4 97 88 2130 14,5 70 3Peugeot 25 4 110 87 2672 17,5 70 2

Volkswagen 26 4 97 46 1835 20,5 70 2Toyota 24 4 113 95 2372 15 70 3

5

Chevrolet 18 8 307 130 3504 12 70 1Buick 15 8 350 165 3693 11,5 70 1

Blymouth 18 8 318 150 3436 11 70 1Amc 16 8 304 150 3433 12 70 1



Agrupamento da base Auto MPG pelo algoritmo ocopt-aiNet v2.

1 2 3 4 5G1 G1 G1 G1 G1

Pombo Pombo Pombo Pombo PomboGalinha Galinha Galinha Ganso GalinhaPato Pato Pato G2 G2Ganso Ganso Ganso Galinha PatoCoruja Coruja Coruja Pato GansoGavião Gavião Gavião G3 G3Águia Águia Águia Coruja Coruja

G2 G2 G2 Gavião GaviãoRaposa Raposa Raposa G4 G4Cão Cão Gato Águia ÁguiaLobo Lobo G3 G5 G5Gato Gato Cão Raposa RaposaTigre G3 Lobo Gato GatoLeão Tigre G4 G6 G6Cavalo Leão Tigre Cão CãoZebra G4 Leão Lobo LoboVaca Cavalo G5 G7 G7 Zebra Cavalo Tigre Tigre G5 Zebra Leão Leão Vaca G6 G8 G8 Vaca Cavalo Cavalo Zebra Zebra G9 G9


Agrupamentos da base Animais pela ocopt-aiNet v2.


Vaca Vaca0,79921 0,79645 0,80709 0,80001 0,80001

Base Ruspini:

Fitness: 0,89381



Fitness: 0,87405



Fitness: 0,87988



4. Discussão O termo mineração de dados, ou data mining surgiu do interesse em se utilizar

grandes bancos de dados de uma maneira inteligente.

A ideia é descobrir conhecimento em grandes conjuntos de dados, que corresponde

a uma tarefa significativamente difícil e desafiadora, requerendo ativa participação

de engenheiros de conhecimento, analistas de sistemas, analistas de dados,

especialistas do domínio, usuários do sistema, estatísticos, etc.

É, portanto, uma tarefa interdisciplinar e multidisciplinar, centralizada na

participação ativa do ser humano.

De um modo mais formal, pode-se dizer que a mineração de dados se refere a uma

classe de métodos utilizados em alguns passos que abrangem o processo de

descoberta de conhecimento em bancos de dados (Knowledge Discovery in

Databases – KDD).



Este termo, cunhado em 1989, se refere ao processo, interativo e iterativo, de

descoberta de conhecimento em conjuntos de dados, incorporando conhecimento

de domínio e interpretação de resultados, com ênfase na aplicação dos métodos de

mineração de dados.

Pode-se definir a descoberta de conhecimento em bancos de dados como sendo o

processo não trivial de identificação de padrões válidos, novos, potencialmente

úteis e compreensíveis em grandes bancos de dados.



Figura 3: Processo de KDD. (Fonte: Fayyad et al., 1996).



Figura 4: Multidisciplinaridade da mineração de dados.

Agrupamento de dados é uma das tarefas mais importantes do processo de KDD e

algoritmos evolutivos podem ser usados para, efetivamente, resolver problemas de

agrupamento de dados.

Encontrar diversidade em bases de dados é uma capacidade importante para

auxiliar na tomada de decisão por parte do usuário, permitindo uma análise mais

ampla das relações existentes entre os objetos pertencentes à base.



Agradecimento

O autor agradece a Universidade Presbiteriana Mackenzie pelo permanente e

dedicado apoio às atividades de pesquisa, ao programa Mackpesquisa, ao CNPq e à

Fapesp pelos apoios financeiros.


Technology

2010: Agrupamento Evolutivo de Dados