Definição automática da quantidade de atributos selecionados em tarefas de agrupamento de dados por José Augusto Andrade Filho - Versão HTML

ATENÇÃO: Esta é apenas uma visualização em HTML e alguns elementos como links e números de página podem estar incorretos.
Faça o download do livro em PDF, ePub, Kindle para obter uma versão completa.

Definição automática da quantidade de

atributos selecionados em tarefas de

agrupamento de dados

José Augusto Andrade Filho

SERVIÇO DE PÓS-GRADUAÇÃO DO ICMC-USP

Data de Depósito:

Assinatura:________________________

Definição automática da quantidade de

atributos selecionados em tarefas de

agrupamento de dados

José Augusto Andrade Filho

Orientador: Prof. Dr. André Carlos Ponce de Leon Ferreira de Carvalho

Tese apresentada ao Instituto de Ciências Matemáticas

e de Computação - ICMC-USP, como parte dos

requisitos para obtenção do título de Doutor em

Ciências - Ciências de Computação e Matemática

Computacional. VERSÃO REVISADA

USP – São Carlos

Novembro de 2013

Ficha catalográfica elaborada pela Biblioteca Prof. Achille Bassi

e Seção Técnica de Informática, ICMC/USP,

com os dados fornecidos pelo(a) autor(a)

Andrade Filho, José Augusto

AAN553

Definição automática da quantidade de atributos

d

selecionados em tarefas de agrupamento de dados /

José Augusto Andrade Filho; orientador André Carlos

Ponce de Leon Ferreira de Carvalho. -- São Carlos,

2013.

73 p.

Tese (Doutorado - Programa de Pós-Graduação em

Ciências de Computação e Matemática Computacional) --

Instituto de Ciências Matemáticas e de Computação,

Universidade de São Paulo, 2013.

1. Seleção de atributos. 2. Agrupamento de dados.

3. Definição de quantidade. I. de Carvalho, André

Carlos Ponce de Leon Ferreira, orient. II. Título.

A meus pais

Agradecimentos

Queria agradecer a todas as pessoas que me auxiliaram de alguma maneira neste doutorado.

A meu orientador, prof. Dr. André Carlos Ponce de Leon Ferreira de Carvalho, pela dedi-

cação ao me orientar, por todo o apoio e pela abertura que me foi dada para discutir propostas,

técnicas e caminhos.

Ao meu supervisor durante o estágio sanduíche, prof. Dr. Huan Liu, por ter me recebido

bem e pela ajuda na definição do escopo do trabalho.

A meus colegas e amigos da USP, em especial ao Paulo, Rosane e ao prof. Rodrigo Mello

pela importante ajuda e apoio durante a realização deste trabalho e pelos importantes momentos

de confraternização.

A meus pais, Vilma e Guga, pelo apoio incondicional em todas as horas, por serem um

modelo de conduta.

A minhas irmãs, Mônica e Shirley, pelos momentos divertidos e pela cooperação e apoio

em todas as horas.

A minhas avós, tios (em especial a meu padrinho Chico), primos (em especial a Jéssica

e Andrezza) e amigos (Stella, Tadeu, Jean, Fernanda e Mike) que tanto me apoiaram nessa

jornada.

A CNPq, pelo apoio financeiro durante o doutorado e a CAPES pelo apoio financeiro que

permitiu a realização do estágio sanduíche.

iii

“As far as the laws of mathematics

refer to reality, they are not certain;

and as far as they are certain, they

do not refer to reality.”

Albert Einstein

Resumo

Conjuntos de dados reais muitas vezes apresentam um grande número de atributos preditivos

ou de entrada, o que leva a uma grande quantidade de informação. Entretanto, essa quantidade

de informação nem sempre significa uma melhoria em termos de desempenho de técnicas de

agrupamento. Além disso, alguns atributos podem estar correlacionados ou adicionar ruído,

reduzindo a qualidade do agrupamento de dados. Esse problema motivou o desenvolvimento de

técnicas de seleção de atributos, que tentam encontrar um subconjunto com os atributos mais

relevantes para agrupar os dados. Neste trabalho, o foco está no problema de seleção de atributos

não supervisionados. Esse é um problema difícil, pois não existe informação sobre rótulos das

classes. Portanto, não existe um guia para medir a qualidade do subconjunto de atributos. O

principal objetivo deste trabalho é definir um método para identificar quanto atributos devem ser

selecionados (após ordená-los com base em algum critério). Essa tarefa é realizada por meio da

técnica de Falsos Vizinhos Mais Próximos, que tem sua origem na teoria do caos. Resultados

experimentais mostram que essa técnica informa um bom número aproximado de atributos a

serem selecionados. Quando comparado a outras técnicas, na maioria dos casos analisados,

enquanto menos atributos são selecionados, a qualidade da partição dos dados é mantida.

vii

Abstract

Real-world datasets commonly present high dimensional data, what leads to an increased

amount of information. However, this does not always imply on an improvement in terms of

clustering techniques performance. Furthermore, some features may be correlated or add unex-

pected noise, reducing the data clustering performance. This problem motivated the develop-

ment of feature selection techniques, which attempt to find the most relevant subset of features

to cluster data. In this work, we focus on the problem of unsupervised feature selection. This

is a difficult problem, since there is no class label information. Therefore, there is no guide to

measure the quality of the feature subset. The main goal of this work is to define a method to

identify the number of features to select (after sorting them based on some criterion). This task

is carried out by means of the False Nearest Neighbor, which has its root in the Chaos Theory.

Experimental results show that this technique gives an good approximate number of features

to select. When compared to other techniques, in most of the analyzed cases, while selecting

fewer features, it maintains the quality of the data partition.

ix

Lista de Figuras

2.1

Exemplo de Manifold (Mello, 2009) . . . . . . . . . . . . . . . . . . . . . . .

6

2.2

Saída da função Logística – Primeiras 100 observações . . . . . . . . . . . . .

7

2.3

Observações da função Logística reconstruída (dimensão embutida 2 e de sepa-

ração 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.4

Atrator de Lorenz: Amostra de observações . . . . . . . . . . . . . . . . . . .

8

2.5

Atrator de Lorenz reconstruído no espaço de coordenadas de atraso (dimensão

embutida 2 e de separação 5) (Mello, 2009) . . . . . . . . . . . . . . . . . . .

8

2.6

Atrator de Lorenz reconstruído no espaço de coordenadas de atraso (dimensão

embutida 3 e de separação 5) (Mello, 2009) . . . . . . . . . . . . . . . . . . .

8

2.7

Atrator de Lorenz – Auto-Mutual Information . . . . . . . . . . . . . . . . . .

10

2.8

Atrator de Lorenz – Encontrado dimensões embutidas . . . . . . . . . . . . . .

11

2.9

Grupo bem separado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

2.10 Grupo baseado em centro.

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

2.11 Grupo contínuo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.12 Grupo baseado em densidade.

. . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.13 Etapas do processo de agrupamento de dados . . . . . . . . . . . . . . . . . .

14

2.14 Taxonomia de algoritmos de Agrupamento de Dados (Jain et al., 1999). . . . .

16

3.1

Redefinindo um conjunto de dados como uma série temporal (n = 2 and τ =

m = 3). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

4.1

Planejamento dos experimentos

. . . . . . . . . . . . . . . . . . . . . . . . .

46

4.2

Conjunto de dados Iris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

4.3

Conjunto de dados Breast Tissue . . . . . . . . . . . . . . . . . . . . . . . . .

48

4.4

Conjunto de dados Soybean . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

4.5

Conjunto de dados Yeast . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

4.6

Conjunto de dados Ecoli . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

4.7

Conjunto de dados Glass . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

4.8

Conjunto de dados Swissbank

. . . . . . . . . . . . . . . . . . . . . . . . . .

50

xi

4.9

Conjunto de dados Lung cancer

. . . . . . . . . . . . . . . . . . . . . . . . .

51

4.10 Conjunto de dados WDBC . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

4.11 Conjunto de dados AR10P . . . . . . . . . . . . . . . . . . . . . . . . . . . .

56

4.12 Conjunto de dados PIE10P . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

4.13 Conjunto de dados CLL-SUB-111 . . . . . . . . . . . . . . . . . . . . . . . .

57

4.14 Conjunto de dados GLI-85 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

xii

Lista de Tabelas

2.1

Atrator de Lorenz – Dados originais . . . . . . . . . . . . . . . . . . . . . . .

12

2.2

Atrator de Lorenz – Dados reconstruídos de acordo com as dimensões embuti-

das e de separação (m = 3 and τ = 5) . . . . . . . . . . . . . . . . . . . . . .

12

3.1

Conjunto de dados de exemplo . . . . . . . . . . . . . . . . . . . . . . . . . .

36

3.2

Distâncias – F1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

3.3

Distâncias – F1F2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

3.4

Distâncias – F1F2F3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

3.5

Distâncias – F1F2F3F4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

3.6

Distâncias – F1F2F3F6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

3.7

Distâncias – F1F5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

3.8

Distâncias – F1F6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

4.1

Principais parâmetros utilizados nos experimentos . . . . . . . . . . . . . . . .

46

4.2

Conjuntos de dados do Grupo I . . . . . . . . . . . . . . . . . . . . . . . . . .

47

4.3

Resultados CR – Base comparativa – Grupo I . . . . . . . . . . . . . . . . . .

52

4.4

Resultados CR – FQFNN e rankings – Grupo I

. . . . . . . . . . . . . . . . .

52

4.5

Resultados Silhueta – Base comparativa – Grupo I . . . . . . . . . . . . . . . .

53

4.6

Resultados Silhueta – FQFNN e rankings – Grupo I . . . . . . . . . . . . . . .

53

4.7

Resultado da avaliação do teste de hipótese – CR – Grupo I . . . . . . . . . . .

54

4.8

Resultado da avaliação do teste de hipótese – Silhueta – Grupo I . . . . . . . .

54

4.9

Diferença entre a quantidade de atributos selecionados pela técnica FQFNN+SPEC

– Grupo I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

4.10 Similaridade entre os atributos selecionados pela técnica FQFNN+SPEC – Grupo

I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

56

4.11 Conjuntos de dados do Grupo II . . . . . . . . . . . . . . . . . . . . . . . . .

56

4.12 Resultados CR – Base comparativa – Grupo II . . . . . . . . . . . . . . . . . .

58

4.13 Resultados CR – FQFNN e rankings – Grupo II . . . . . . . . . . . . . . . . .

59

4.14 Resultados Silhueta – Base comparativa – Grupo II . . . . . . . . . . . . . . .

59

xiii

4.15 Resultados Silhueta – FQFNN e rankings – Grupo II

. . . . . . . . . . . . . .

60

4.16 Resultado da avaliação do teste de hipótese – CR – Grupo II . . . . . . . . . .

60

4.17 Resultado da avaliação do teste de hipótese – Silhueta – Grupo II . . . . . . . .

61

4.18 Diferença entre a quantidade de atributos selecionados com FQFNN+SPEC –

Grupo II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

4.19 Similaridade entre os atributos selecionados com FQFNN+SPEC – Grupo II . .

62

4.20 Conjuntos de dados do Grupo III . . . . . . . . . . . . . . . . . . . . . . . . .

62

4.21 Resultados para o conjunto de dados de espécies endêmicas . . . . . . . . . . .

63

4.22 Avaliação de Silhueta para o conjunto de dados de espécies endêmicas – 2 grupos 63

xiv

Lista de Algoritmos

2.1

Funcionamento básico do K-means . . . . . . . . . . . . . . . . . . . . . . . .

18

2.2

Generalização de uma técnica baseada em Filtro . . . . . . . . . . . . . . . . .

22

2.3

Generalização de uma técnica baseada em wrapper . . . . . . . . . . . . . . . .

23

2.4

Generalização de uma técnica de seleção de atributos híbrida . . . . . . . . . . .

24

2.5

SPEC – Spectral Feature Selection . . . . . . . . . . . . . . . . . . . . . . . . .

28

2.6

Algoritmo k-medoids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

2.7

Estratégia de amostragem para o k-medoids . . . . . . . . . . . . . . . . . . . .

31

3.1

Algoritmo da técnica FQFNN . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

3.2

Pseudo-código da técnica SPECMI . . . . . . . . . . . . . . . . . . . . . . . .

42

3.3

Pseudo-código da geração do ensamble . . . . . . . . . . . . . . . . . . . . . .

42

xv

Lista de Símbolos

X

Conjunto de exemplos.

πe

Partição resultante de um algoritmo de agrupamento aplicado a um con-

junto de X.

Gw

Grupo w de uma partição π.

xi

i-ésimo exemplo do conjunto de dados X.

n

Número de exemplos. No contexto desta tese, n = τ

τ

Dimensão de separação (time-delay). No contexto desta tese, τ = n

F

Conjunto de atributos que compõe um exemplo xi.

p

Número de atributos em um conjunto de dados.

fj

j-ésimo atributo de um exemplo xi.

F ∗

Subconjunto de F .

m

Dimensão embutida, resultado da técnica de falsos vizinhos.

xvii

Sumário

1

Introdução

1

1.1

Contextualização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.3

Estrutura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2

Trabalhos relacionados

5

2.1

Considerações Iniciais

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.2

Teoria do Caos

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.3

Agrupamento de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

2.3.1

Algoritmos de Agrupamento de Dados . . . . . . . . . . . . . . . . . .

15

2.3.2

Algoritmo K-means . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.3.3

Índices de Validação . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

2.4

Seleção de Atributos para Agrupamento de Dados . . . . . . . . . . . . . . . .

21

2.5

Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

3

Técnica FQFNN: Feature Quantification by False Nearest neighbors

33

3.1

Considerações Iniciais

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

3.2

Falsos vizinhos mais próximos aplicado a conjuntos de dados . . . . . . . . . .

34

3.3

Análise da interação entre as distâncias . . . . . . . . . . . . . . . . . . . . . .

36

3.4

Técnica FQFNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

3.5

Técnicas para ranking de atributos . . . . . . . . . . . . . . . . . . . . . . . .

41

3.6

Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

4

Experimentos e resultados

45

4.1

Considerações Iniciais

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

4.2

Planejamento dos Experimentos . . . . . . . . . . . . . . . . . . . . . . . . .

45

4.3

Grupo I: conjuntos de dados da UCI . . . . . . . . . . . . . . . . . . . . . . .

47

4.4

Grupo II: Conjunto de dados de imagens e microarray

. . . . . . . . . . . . .

55

4.5

Grupo III: Conjunto de dados de Espécies Endêmicas . . . . . . . . . . . . . .

59

xix

4.6

Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

62

5

Conclusão

65

5.1

Considerações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

5.2

Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

5.3

Publicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

5.4

Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

Referências

69

xx

Capítulo

1

Introdução

1.1

Contextualização

Conjuntos de dados reais, muitas vezes apresentam um alto número de dimensões, isto é,

com um grande número de atributos preditivos ou de entrada (Liu & Motoda, 2007; Jain, 2010).

Esses conjuntos podem ser encontrados em dados de diversas áreas, como medicina, biologia,

climatologia, física, química etc (Asuncion & Newman, 2007). Dentre esses atributos, é fácil encontrar aqueles que estão correlacionados a outros, que são irrelevantes ou que apresentam

ruído. Atributos com esses problemas podem prejudicar, ou não influenciar no desempenho

de uma técnica de aprendizado. Além disso, um número elevado de atributos, de acordo com

a maldição da dimensionalidade (curse of dimensionality), leva à necessidade de um grande

número de exemplos (Aggarwal et al., 2001). A seleção de um subconjunto dos atributos que contivesse os mais relevantes, poderia reduzir a ocorrência dos problemas previamente aponta-dos. A investigação e o desenvolvimento de técnicas para selecionar os atributos mais relevantes

podem melhorar a qualidade do modelo criado a partir da técnica de aprendizado, bem como

reduzir o tempo necessário para induzir tal modelo.

A tarefa de seleção de atributos pode ser formalmente definida do seguinte modo: considere

um conjunto de dados X contendo n exemplos, X = {x1, x2, · · ·, xn}. Cada exemplo xi pode

ser descrito como um conjunto F = {f1, f2, · · ·, fp} de atributos de entrada de tamanho p. A

hipótese principal do processo de seleção de atributos é que existe um subconjunto F ∗ ⊂ F ,

onde |F ∗| < |F |, que descreve X, de tal maneira que o modelo induzido por F ∗ melhora, ou

mantém, a qualidade medida quando comparado com o modelo original (que usa F ), ao mesmo

tempo em que se reduz o tempo de processamento.

A seleção de atributos é geralmente associada com o aprendizado supervisionado (Devaney

& Ram, 1997). Nesse caso, os rótulos de classe dos exemplos, os atributos alvo, podem ser 1

utilizados para determinar a qualidade do modelo induzido com o subconjunto de atributos.

Entretanto, no cenário não-supervisionado, não existe informação para guiar a avaliação de

qualidade do subconjunto de atributos, o que torna a tarefa de seleção de atributos mais difícil

(Devaney & Ram, 1997; Dy & Brodley, 2000b; Dash et al., 2002). Outro problema associado com a seleção de atributos no cenário não-supervisionado é que, mesmo que se conheça, de

antemão, quais os atributos relevantes, ainda é difícil definir quantos desses atributos devem ser

selecionados.

Diversas abordagens foram propostas na literatura para o problema de seleção de atributos

no contexto não-supervisionado (Liu & Motoda, 2007). Elas são classificadas em três catego-rias: wrappers, filtros e híbridos. As abordagens baseadas em wrappers utilizam o desempenho

de um determinado modelo preditivo para selecionar um subconjunto de atributos relevantes.

Para isso, avaliam para um dado subconjunto, qual o efeito desse subconjunto no desempenho

preditivo do modelo (Dy & Brodley, 2004; Boutsidis et al., 2009). As abordagens baseadas em filtros, por outro lado, selecionam subconjuntos de atributos utilizando apenas os valores dos

atributos de entrada dos objetos no conjunto de dados, procurando, por exemplo, identificar cor-

relações entre atributos de entrada (Zhao & Liu, 2007; Liu & Yu, 2005; Dash et al., 2002). Por fim, as abordagens híbridas incorporam características das duas abordagens anteriores (Covões

& Hruschka, 2011).

Como as abordagens baseadas em wrappers dependem de um modelo específico, eles são

computacionalmente mais custosas do que as baseadas em filtros. Além disso, abordagens base-

adas em wrappers possuem um viés que tende a privilegiar o modelo utilizado para a seleção de

atributos. Por essas razões, abordagens baseadas em filtros são mais utilizadas, especialmente,

em problemas que envolvem uma grande quantidade de dados (big data problems). Apesar

disso, foi empiricamente mostrado que abordagens baseadas em wrappers, na maioria dos ca-

sos, tendem a gerar modelos melhores para a seleção de atributos do que abordagens baseadas

em filtros (Liu & Yu, 2005; Dash et al., 2002).

Para utilizar os aspectos positivos das duas abordagens, foi proposta a abordagem híbrida,

que combina características dos métodos baseados em wrappers e dos baseados em filtros.

Métodos híbridos utilizam métricas independentes e técnicas de indução de modelos para de-

terminar a relevância de um subconjunto de atributos (Covões & Hruschka, 2011).

Outra diferença entre as diversas técnicas utilizadas para seleção de atributos diz respeito

à ordem com que os atributos são selecionados. Em uma abordagem gulosa, os atributos são

selecionados sequencialmente. O primeiro atributo é o mais relevante. O segundo, é o próximo

mais relevante, e assim por diante. Essa relevância pode ser absoluta, considerando todo o

conjunto de atributos, ou relativa, mais relevante dados os atributos que já foram selecionados.

Um problema dessa abordagem é que ela pode selecionar atributos correlacionados. A segunda

abordagem, aqui chamada de combinatorial, procura selecionar de uma única vez o subconjunto

de atributos que, juntos, formam o subconjunto mais relevante. O problema dessa abordagem é

que, para um número grande de atributos, o número de possíveis subconjuntos pode ser muito

2

Capítulo 1. Introdução

1.2. Objetivo

grande, tornando difícil a seleção do subconjunto.

Com base nos trabalhos encontrados na literatura, observou-se que a definição do número

de atributos a serem selecionados é feita a partir do resultado da própria técnica, por meio de

um limiar (threshold) (Dash et al., 2002; Dy & Brodley, 2004), ou pela pela definição de um percentual de atributos a serem utilizados (Zhao & Liu, 2007). Isso pode tornar a definição do tamanho do subconjunto dependente da técnica de seleção ou um processo subjetivo, pois um

limiar ou percentagem bom para um conjunto de dados, não necessariamente é bom para outro.

Para lidar com essa deficiência, é proposto nesta Tese um método para a definição da

quantidade de atributos a serem utilizados na tarefa de seleção de atributos no contexto não-

supervisionado, que utilize apenas informações do conjunto de dados. Para esse fim, uma téc-

nica baseada em teoria do caos é utilizada. O teorema de imersão de Whitney (1936), que posteriormente foi estendido por Takens (1980), é a base teórica deste trabalho. O teorema de

Whitney (1936) mapeia uma série de observações em um espaço de maior dimensão. Poste-

riormente, Takens (1980) estendeu o teorema de Whitney e formalizou como observações em um espaço de menor dimensão podem ser organizadas para serem mapeadas em um espaço de

maior dimensão. Nesse mapeamento, Takens observou que as distâncias entre observações per-

manecem iguais, mesmo quando o número de dimensões aumenta. Isso acontece porque, após

mapear as observações no número correto de dimensões, não há necessidade de aumentá-las.

Portanto, nesse espaço de maior dimensão, a informação está melhor representada. Para tanto,

Takens (1980) considera os conceitos de dimensão embutida e de separação. O cálculo da dimensão embutida é feito por meio da técnica FNN (False Nearest Neighbor), que foi proposta

por Kennel et al. (1992a), com base no trabalho de Takens (1980)

No contexto desta Tese, é utilizado o mesmo princípio para identificar o número de atributos

(dimensões) que melhor representa um conjunto de dados. Ao medir a variação das distâncias

entre exemplos, considerando diferentes números de dimensões, é possível identificar quando

novas informações não são adicionadas.

Para avaliar o desempenho da técnica proposta, duas medidas são utilizadas. A primeira, é

uma medida de avaliação interna, silhueta (Kaufman & Rousseeuw, 1990), que tem como objetivo representar como os exemplos estão dispostos nas partições. A segunda, Corrected Rand

(CR) (Hubert & Arabie, 1985), é uma medida de avaliação externa que, neste trabalho, compara a partição resultante de um algoritmo de agrupamento com as classes reais (atributos alvo).

Uma outra comparação é feita e leva em consideração a quantidade de atributos selecionados

pelas técnicas avaliadas.

1.2

Objetivo

O principal objetivo desta Tese é propor e investigar uma técnica para definição automática

do número de atributos a serem selecionados, quando os dados não são rotulados. Para isso, é

realizado um estudo da interação dos exemplos em um conjunto de dados ao variar a quantidade

3

de atributos, para, assim, sugerir quantos atributos devem ser utilizados.

Para realizar esse estudo, é desenvolvida uma adaptação da técnica de falsos vizinhos mais

próximos (False Nearest Neighbors – FNN) (Kennel et al., 1992a), que é baseada nos conceitos definidos no teorema de imersão de Whitney (1936) e Takens (1980).

1.3

Estrutura

O texto desta Tese está estruturado da seguinte forma: no Capítulo 2 são descritos os principais conceitos e definições úteis ao entendimento deste trabalho nos temas de agrupamento

de dados e teoria do caos. Esse capítulo também contém uma análise de técnicas de seleção

de atributos em problemas de agrupamento de dados. O Capítulo 3 apresenta a definição da proposta, bem como um caso de estudo que exemplifica a utilização da técnica proposta. Os

experimentos realizados para a validação da técnica proposta e os resultados obtidos, são apre-

sentados no Capítulo 4. Finalmente, o Capítulo 5 explicita as conclusões obtidas a partir dos resultados e aponta direções para trabalhos futuros.

4

Capítulo

2

Trabalhos relacionados

2.1

Considerações Iniciais

Esse capítulo apresenta conceitos que serão úteis na leitura deste trabalho. Inicialmente,

é feita uma rápida introdução à teoria do caos, focando no teorema de imersão de Whitney

(1936) e, principalmente, no algoritmo de falsos vizinhos mais próximos, proposto por Kennel

et al. (1992a). Em seguida, conceitos básicos de agrupamentos de dados são expostos. Essa seção tem por objetivo uniformizar os termos de agrupamentos de dados que são utilizados

no decorrer desta Tese. Por último, a Seção 2.4 descreve trabalhos relacionados à seleção de atributos em agrupamento de dados, tema desta Tese.

2.2

Teoria do Caos

A Teoria do Caos pode ser utilizada para extrair o comportamento de uma série temporal

(Whitney, 1936; Takens, 1980). Se ao invés de uma série temporal, for utilizado um conjunto de dados convencional, estático, é possível utilizar as ferramentas dessa teoria com o intuito de

auxiliar a identificação de atributos relevantes em um conjunto de dados. Essa seção apresenta

conceitos que são utilizados nesta proposta. Essa seção apresenta alguns conceitos de teoria do

caos.

Whitney (1936) utilizou manifolds, ou variedades, diferenciáveis como forma de reconstruir funções por meio de transformações para o espaço Euclideano multidimensional. Manifolds,

utilizados com frequência na geometria e topologia diferencial, representam um espaço ma-

temático. Matematicamente, é possível dizer que M ⊂

k

R é um manifold diferenciável de

dimensão m se, para cada ponto p ∈ M , existe uma vizinhança U ⊂ M de p e um homeomor-

fismo x : U → U

m

k

0, U0 é um aberto de R

, como o homeomorfismo inverso x−1 : U0 → U ⊂ R

5

index-30_1.png

Figura 2.1: Exemplo de Manifold (Mello, 2009)

é uma imersão da classe Cinf . Ou seja, para cada u ∈ U

m

k

0, a derivada dx−1(u) : R

→ R é

biunívoca. Portanto, sob essas circunstâncias, diz-se que (x, U ) é uma carta local ao redor de p,

e U é uma vizinhança coordenada de p (Palis Jr. & Melo, 1978; Mello, 2009).

A Figura 2.1 mostra um exemplo de parametrização de um plano

m−1

k

R

× R+ para outro R .

Dado um ponto q , é possível , utilizando φq : H0 → H ∩M , encontrar um ponto correspondente

de q em M . O mesmo acontece com p . Entretanto, nessa situação, obtém-se uma região nos

limites de M . Esse exemplo ilustra o mapeamento de um ponto e sua vizinhança em um espaço

de maior dimensão (Mello, 2009).

Whitney (1936) observou que esse mapeamento permite o entendimento de comportamen-

tos não-observáveis ou pouco-representativos quando descritos como um espaço de menor di-

mensão. A partir disso, o autor propôs o teorema de imersão, em que qualquer manifold de

n-dimensões pode ser mapeado em um espaço com 2n + 1-dimensões.

Baseado no teorema de imersão de Whitney (1936), Takens (1980) provou que, ao invés de mapear os estados de um sistema dinâmico em um espaço de 2n + 1-dimensões, o sistema pode

ser reconstruído considerando atrasos (time delays). De acordo com o teorema de imersão de

Takens (1980), uma série temporal x0, x1, ..., xn−1 pode ser reconstruída em um espaço multidimensional xn(m, τ ) = (xn, xn+τ , . . . , xn+(m−1)τ ), também chamado espaço de coordenadas

de atraso, onde m é a dimensão embutida e τ representa o atraso (ou dimensão de separação).

Esse mapeamento, ou técnica de reconstrução, permite transformar observações de um sistema

dinâmico (ou regras de saída) em um conjunto de pontos em um espaço Euclideano de m-

dimensões. Essa reconstrução suporta a obtenção de regras para o sistema dinâmico. Como

consequência, a reconstrução simplifica o estudo de comportamentos e seus usos sob diferentes

circunstâncias, como o estudo de órbitas, tendências e predições (Alligood et al., 1997; Mello,

2009).

Para melhor entender as dimensões embutida (número de dimensões) e de separação (atraso

ou time delay), considere a saída da função Logística definida na Equação 2.1, reconstruída em 6

index-31_1.png

index-31_2.png

Capítulo 2. Trabalhos relacionados

2.2. Teoria do Caos

um espaço multidimensional onde m = 2 e τ = 1, o que resulta em pares de pontos (xt, xt+1)

(Figura 2.3). Após a reconstrução, o comportamento da função Logística, que se comportava como caminhada aleatória (Figura 2.2), pode ser estudada, entendida e modelada de um modo mais simples. Após a regressão dos dados, é possível obter a regra do sistema dinâmico e,

portanto, entender transições, estimar e predizer observações. Com essa regra e um xt inicial,

pode-se, por exemplo, definir a próxima série de observações, xt+1, que serve como entrada

para gerar xt+2, e assim por diante (Mello, 2009).

xt+1 = b · xt · (1, 0 − xt)

(2.1)

Figura 2.2: Saída da função Logística – Primeiras 100 observações

Figura 2.3: Observações da função Logística reconstruída (dimensão embutida 2 e de separa-

ção 1)

A dimensão embutida basicamente define o número de eixos para o espaço de coordenadas

atraso. Isso determina o número de dimensões necessárias para desdobrar a série reconstruída.

7

index-32_1.png

index-32_2.png

index-32_3.png

Nesse caso, a série requer duas dimensões, outras situações podem precisar de mais. Esse

comportamento é, por exemplo, observado no atrator de Lorenz cujas amostras de observação

são apresentadas na Figura 2.4.

Figura 2.4: Atrator de Lorenz: Amostra de observações

Figura 2.5: Atrator de Lorenz reconstruído no espaço de coordenadas de atraso (dimensão

embutida 2 e de separação 5) (Mello, 2009)

Figura 2.6: Atrator de Lorenz reconstruído no espaço de coordenadas de atraso (dimensão

embutida 3 e de separação 5) (Mello, 2009)

8

Capítulo 2. Trabalhos relacionados

2.2. Teoria do Caos

Ao considerar a reconstrução da série utilizando a dimensão embutida igual a 2, obtém-

se um espaço de coordenadas de atraso similar ao ilustrado pela Figura 2.5. Entretanto, após adicionar uma nova dimensão e reconstruí-la, logo, com m = 3, o comportamento completo

da série é desdobrado, o que simplifica seu estudo e compreensão (Figura 2.6). É encerrado o processo de adicionar novas dimensões quando não existe nenhum novo comportamento; nessa

situação, o processo é interrompido com m = 3, o que representa a melhor dimensão para o

atrator de Lorenz (Mello, 2009).

Além da dimensão embutida, ainda existe a de separação, que permite a extração do com-

portamento periódico da série. Essa dimensão informa o atraso das observações históricas a

serem modeladas e analisadas de modo a predizer eventos futuros (basicamente permite apon-

tar quão longe deve-se observar para obter um relacionamento de causa-consequência na série).

Por exemplo, para predizer a temperatura para uma dada região do mundo no dia 12 de de-

zembro de 2009, pode-se observar o relacionamento ou dinâmica dessa série sobre o tempo.

Baseando-se nessa dinâmica, encontra-se o atraso (time delay) que auxilia a desdobrar o com-

portamento mais dissimilar em um sistema dinâmico. Dissimilaridades auxiliam a desdobrar

os diferentes estados do sistema que são relacionados por uma regra (ou conjunto de equações)

(Mello, 2009).

As dimensões embutida e de separação permitem o estudo das séries. Entretanto, é neces-

sário encontrar essas dimensões para uma série qualquer, incluindo aquelas geradas por dados

experimentais.

Fraser & Swinney (1986) estudaram e confirmaram que a técnica Auto-Mutual Information (AMI) apresenta melhores resultados ao estimar a dimensão de separação. Para obter a separa-

ção da série, aplica-se a AMI sob diferentes atrasos. Posteriormente, plota-se a curva em função

dos atrasos (começando de 1 e aumentando) e adota-se o primeiro mínimo como dimensão de

separação (Mello, 2009).

A informação mútua média é dada pela Equação 2.2, onde X e Y seguem, respectivamente, a funções de densidade de probabilidade PX e PY , e X e Y acontecem em pares com densidade

combinada PXY (Kennel, 2002). Aplicando essa técnica na base de dados do atrator de Lorenz, previamente apresentada, obtém-se a Figura 2.7, de onde pode-se encontrar o primeiro mínimo em 5, confirmando os resultados apresentados em (Lorenz, 1963; Kennel et al., 1992b).

P

I(X; Y ) =

P

XY (x, y)

XY (x, y) log

dxdy

(2.2)

2 PX(x)PY (y)

Após definir a dimensão de separação, é necessário encontrar a dimensão embutida. Takens

(1980) e Mañé (1980) estudaram e confirmaram que o limite superior da dimensão embutida D

+

e ∈ Z

pode ser estimado utilizando a dimensão fractal Df , como De > 2.0 · Df . Entretanto,

a dimensão resultante desse método geralmente é maior que o necessário. Por exemplo, a

dimensão fractal do atrator de Lorenz é 2.06 (Medio & Gallo, 1993), consequentemente, o limite superior da dimensão embutida é De > 2.0 · 2.06, o que resulta em 5. Embora, de

9

index-34_1.png

Figura 2.7: Atrator de Lorenz – Auto-Mutual Information

acordo com Kennel et al. (1992b), o atrator pode ser desdobrado em De = 3. Do ponto de vista matemático (Kennel et al., 1992a,b), pode-se modelar esse sistema utilizando 3 ou 5 dimensões, pois, uma vez que todos os possíveis estados são encontrados, pode-se conduzir a análise de

comportamento. Porém, ao trabalhar desnecessariamente com dimensões a mais, adiciona-se

complexidade e tempo de processamento às etapas de modelagem e análise (Kennel et al.,

1992b).

Uma alternativa para obter-se a dimensão embutida mínima é pela computação de sistema

invariantes (como o expoente de Lyapunov (Alligood et al., 1997)) para diferentes dimensões, com a observação do resultado de saturação. A complexidade dessa abordagem motivou Kennel

et al. (1992b) a propor o método de Falsos Vizinhos Mais Próximos (FNN - False Nearest Neighbor), que calcula os vizinhos mais próximos para cada ponto, no espaço de coordenadas

de atraso (iniciando com dimensão embutida igual a 1). Em seguida, uma nova dimensão é

adicionada e as distâncias entre os vizinhos mais próximos é novamente calculada. Quando a

distância aumenta, os pontos são considerados falsos vizinhos, o que evidencia a necessidade

de mais dimensões para desdobrar o comportamento da série (Mello, 2009).

Kennel et al. (1992b) consideram a dimensão embutida d onde o r-ésimo vizinho mais

próximo de y(n) é dada por y(r)(n). A distância Euclideana entre os pontos y(n) e seu r-ésimo

vizinho mais próximo é dada pela Equação 2.3. Ao adicionar um nova dimensão, reconstrói-se a série em um espaço d + 1 e são adicionadas as coordenadas (d + 1) em cada vetor y(n),

que é incluído na equação de distância Euclideana (componente x(n + dT ) da Equação 2.4).

Desse modo, o critério de medida da variação de distância após adicionar uma nova dimensão

é descrito na Equação 2.5.

d−1

R2(n, r) =

(x(n + kT ) − x(r)(n + kT ))2

(2.3)

d

k=0

10

index-35_1.png

Capítulo 2. Trabalhos relacionados

2.2. Teoria do Caos

R2

(n, r) = R2(n, r) + (x(n + dT ) − x(r)(n + dT ))2

(2.4)

d+1

d

R2

(n, r) − R2(n, r)

|x(n + dT ) − x(n)(n + dT )|

V

d+1

d

n,r =

=

(2.5)

R2(n, r)

R2(n, r)

d

d

De acordo com os autores, se Vn,r > Rtol, os pontos são considerados falsos vizinhos, onde

Rtol é um limite.

Figura 2.8: Atrator de Lorenz – Encontrado dimensões embutidas

Aplicando o método FNN nos dados do atrator de Lorenz (utilizando dimensão de separação

5, previamente obtida), obtém-se o resultado apresentado na Figura 2.8. Essa figura apresenta a fração de falsos vizinhos por diferentes dimensões embutidas. Quando essa fração é igual a

zero, encontra-se a melhor dimensão embutida. Nesse caso, a dimensão embutida é 3, o que

confirma o resultado apresentado por Kennel et al. (1992b).

Após definir ambas as dimensões, aplica-se o teorema de Takens (1980), como previamente apresentado, onde a série temporal x0, x1, · · · , xn−1 é reconstruída em um espaço multidimensional, ou espaço de coordenadas de atraso, xn(m, τ ) = (xn, xn+τ , . . . , xn+(m−1)τ ) (o compo-

nente m representa a dimensão embutida, isto é, o número de dimensões para desdobrar a série,

e τ é a de separação, ou seja, o atraso para considerar observações históricas). A reconstrução

desdobra completamente o sistema dinâmico que permite a obtenção da regra. Para exempli-

ficar esse desdobramento, considere os dados do atrator de Lorenz apresentado na Tabela 2.1.

Após reconstruir os dados com dimensão embutida 3 e separação 5, obtém-se a Tabela 2.2 (a curva resultante dessa reconstrução é apresentada na Figura 2.6) 1 (Mello, 2009).

Essa reconstrução permite desdobrar o comportamento da série e obter sua regra de compor-

tamento, ou seja, o conjunto de equações que definem a órbita sobre o tempo. Após a obtenção

1Essa tabela mostra mais observações que a Tabela 2.1. Isso é apenas um exemplo de desdobramento para obter a regra, ou função, o que gera esse sistema dinâmico.

11

Tabela 2.1: Atrator de Lorenz – Dados originais

Dimensão 1

−9.6559617

−6.9902085

−4.9834927

−3.5773619

−2.6589215

−2.1120568

−1.8411753

−1.7784935

−1.8834828

−2.1397586

−2.5521791

−3.1453527

−3.9638112

−5.0733551

−6.5619076

−8.5356685

−11.100864

−14.311700

−18.056232

−21.873802

−24.819411

Tabela 2.2: Atrator de Lorenz – Dados reconstruídos de acordo com as dimensões embutidas e

de separação (m = 3 and τ = 5)

Dimensão 1

Dimensão 2

Dimensão 3

−9.655962

−2.112057

−2.552179

−6.990209

−1.841175

−3.145353

−4.983493

−1.778494

−3.963811

−3.577362

−1.883483

−5.073355

−2.658921

−2.139759

−6.561908

−2.112057

−2.552179

−8.535668

−1.841175

−3.145353

−11.100864

−1.778494

−3.963811

−14.311700

−1.883483

−5.073355

−18.056232

−2.139759

−6.561908

−21.873802

−2.552179

−8.535668

−24.819410

desse esse conjunto, é possível estudar seus pontos fixos estáveis e instáveis, compreender suas

tendências e também predizer observações futuras.

12

index-37_1.png

index-37_2.png

Capítulo 2. Trabalhos relacionados

2.3. Agrupamento de Dados

2.3

Agrupamento de Dados

O agrupamento de dados é considerado o problema mais importante no aprendizado não-

supervisionado (Kononenko & Kukar, 2007). Seu objetivo é encontrar alguma estrutura em uma base de dados, sem conhecimento prévio (Jain & Dubes, 1988; Mitchell, 1997; Kononenko &

Kukar, 2007). Nessa estrutura, os objetos pertencentes a cada grupo (cluster) compartilham alguma característica ou propriedade relevante para o domínio do problema em estudo (Jain &

Dubes, 1988; Faceli et al., 2011). A definição do que é um grupo é intuitiva, assim, não existe uma formalização única e precisa para esse conceito. Ao contrário, existe uma grande variedade

de definições na literatura e isso é resultado das diferentes visões/objetivos dos pesquisadores

que trabalham com técnicas de agrupamento. Dentre essas definições, podem ser encontradas

(Barbara, 2000; Faceli et al., 2011):

• Grupo bem separado: é um conjunto de pontos, onde qualquer ponto em um grupo A está

mais próximo (ou é mais similar) a cada outro ponto nesse grupo A, do que a qualquer

ponto que não pertença a A (Figura 2.9).

Figura 2.9: Grupo bem separado.

• Grupo baseado em centro: é um conjunto de pontos onde qualquer ponto em um dado

grupo A está mais próximo (ou é mais similar) ao centro do grupo A do que ao centro

de qualquer outro grupo. O centro de um grupo pode ser representado como a média

aritmética dos pontos desse grupo, ou pelo ponto mais representativo (Figura 2.10).

Figura 2.10: Grupo baseado em centro.

• Grupo contínuo: é um conjunto de pontos onde qualquer ponto em um grupo A está mais

próximo (ou é mais similar) a um dos pontos nesse grupo do que a qualquer ponto não

pertencente a A (Figura 2.11).

• Grupo baseado em densidade: é uma região densa de pontos, separada de outras regiões

de alta densidade por regiões de baixa densidade (Figura 2.12).

13

index-38_1.png

index-38_2.png

index-38_3.png

Figura 2.11: Grupo contínuo.

Figura 2.12: Grupo baseado em densidade.

A partir das definições de grupo é possível definir um critério de agrupamento, isto é, de

qual maneira selecionar a estrutura dos grupos que seja adequada a um conjunto de dados.

Os algoritmos de agrupamento são baseados em um critério para agrupar os dados e utilizam

medidas de proximidade juntamente com um método de busca para encontrar uma estrutura

ótima ou subótima, de modo que, dado um critério de agrupamento, seja possível descrever o

conjunto de dados (Jiang et al., 2004).

O processo de agrupamento de dados compreende várias etapas. Essas etapas estão ilustra-

das na Figura 2.13, que é baseada nas informações apresentadas por Jain et al. (1999), Barbara

(2000) e Faceli et al. (2011).

Figura 2.13: Etapas do processo de agrupamento de dados

Preparação

A representação de um objeto (físico ou noção abstrata) é comumente chamada de pa-

drão, exemplo, amostra, instância ou ponto. A preparação dos dados para o agrupamento

14

Capítulo 2. Trabalhos relacionados

2.3. Agrupamento de Dados

envolve vários aspectos relacionados ao seu pré-processamento e à forma de representa-

ção apropriada para a utilização em um algoritmo de agrupamento (Faceli et al., 2011).

Neste trabalho, o termo exemplo é utilizado.

Durante o pré-processamento, normalizações, conversões de tipos e reduções do número

de atributos por meio de seleção ou extração de características podem ser utilizadas (Jain

et al., 1999).

Para a representação, os objetos a serem agrupados são, geralmente, representados por

uma matriz de objetos Xn×p = {x1, x2, · · · , xn}, onde xi = {f1, f2, · · · , fp}, n é o

número de exemplos e p é o número de atributos que representam os exemplo, ou seja, a

dimensionalidade dos objetos.

Proximidade

Consiste na definição de uma medida de proximidade apropriada ao domínio da aplica-

ção. Essa medida pode ser de similaridade ou de dissimilaridade entre dois objetos. As

medidas de proximidade, em geral, consideram todos os atributos igualmente importan-

tes.

Jain & Dubes (1988) descrevem as medidas de proximidade mais adequadas para cada

tipo de escala de atributo possível. Uma das medidas de proximidade mais comum é a

distância Euclideana.

Agrupamento

Essa etapa representa a aplicação de um determinado algoritmo de agrupamento de dados.

Uma taxonomia, baseada em Jain et al. (1999) é apresentada na seção 2.3.1. O algoritmo k-means, utilizado nos experimentos, é detalhado na seção 2.3.2.

Validação

Nessa etapa, o resultado de um algoritmo de agrupamento (etapa Agrupamento) é avali-

ado. Essa avaliação, de forma objetiva, determina se os agrupamentos são significativos,

isto é, se a solução é representativa para o conjunto de dados. A seção 2.3.3 apresenta os índices utilizados neste trabalho.

Interpretação

O objetivo dessa etapa é examinar cada agrupamento formado com o objetivo de rotulá-

lo, descrevendo a natureza desse agrupamento. Em geral, essa etapa é realizada por um

especialista, que pode ter interesse em encontrar diferenças semânticas de acordo com os

objetos e os valores em cada agrupamento (Faceli et al., 2011).

2.3.1

Algoritmos de Agrupamento de Dados

Jain et al. (1999) definem uma taxonomia dos algoritmos de agrupamento de dados. Essa taxonomia é apresentada na Figura 2.14 e descrita a seguir.

15

index-40_1.png

Figura 2.14: Taxonomia de algoritmos de Agrupamento de Dados (Jain et al., 1999).

Hierárquico Um algoritmo de agrupamento hierárquico tem como resultado um dendrograma.

Esse dendrograma representa o agrupamento dos exemplos e os níveis de similaridade em

que o agrupamento é modificado. Um dendrograma pode ser considerado em diversos ní-

veis, cada nível representa os possíveis agrupamentos. Em geral, os métodos hierárquicos

são variantes dos algoritmos Ligação simples e Ligação completa (Jain et al., 1999). Em ambos os casos, dois grupos são fundidos para formar um grupo maior, baseando-se no

critério de distância mínima.

• Ligação-simples: A distância entre dois grupos é a menor das distâncias entre todos

os pares de exemplos desses grupos. Essa técnica tem uma tendência de gerar grupos

alongados.

• Ligação-completa: Diferente do Ligação-simples, a distância entre dois grupos é a

máxima entre pares de exemplos desses dois grupos. Essa técnica, em geral, fornece

agrupamentos compactos.

Particional Um algoritmo de agrupamento particional tem como resultado uma partição dos

dados. Técnicas particionais geralmente produzem grupos por meio da otimização de

um critério, que pode ser definido localmente (em um subconjunto de exemplos) ou glo-

balmente (considerando todos os exemplos). De modo geral, esse tipo de algoritmo é

executado diversas vezes para diferentes estados iniciais. A melhor configuração é uti-

lizada como saída desse algoritmo de agrupamento. Dentre os critérios utilizados em

algoritmos particionais, podem ser citados (Jain et al., 1999):

• Erro quadrático: o mais intuitivo e frequente critério é o erro quadrático, que tende

a ter bons resultados com agrupamentos isolados e compactos.

• Teoria dos grafos: utiliza como critério o cálculo da Minimal Spanning Tree (MST)

dos dados e na exclusão das arestas da MST com as maiores dimensões, para iden-

tificar diferentes grupos.

• Modelo de Mistura e Mode Seeking: As abordagens Modelo de Misturas e Mode

Seeking podem ser utilizadas de diversas maneiras. A premissa básica é que os

16

Capítulo 2. Trabalhos relacionados

2.3. Agrupamento de Dados

exemplos a serem agrupados são escolhidos a partir de uma dentre várias distribui-

ções de probabilidade. O objetivo é identificar os parâmetros de cada distribuição

e seus valores. A maioria dos trabalhos supõe que os componentes individuais da

mistura são Gaussianas.

Além das técnicas presentes na taxonomia, outros aspectos precisam ser levados em con-

sideração pois, podem ser utilizados em diversos ramos da taxonomia (Jain et al., 1999). São eles:

• Aglomerativo vs. Divisivo: Um algoritmo aglomerativo inicia com cada exemplo em um

agrupamento distinto e, sucessivamente, combina agrupamentos até que um critério de

parada seja atingido. Um método divisivo inicia com todos os exemplos em um único

agrupamento e realiza divisões até atingir um critério de parada.

• Hard vs. Fuzzy: Em um método de agrupamento Hard, os exemplos pertencem a apenas

um agrupamento. Em um método Fuzzy, são definidos graus de pertinência de cada

exemplo para todos os agrupamentos. Um método Fuzzy pode ser convertido em um

método Hard, ao atribuir cada padrão ao agrupamento com maior grau de pertinência.

• Determinístico vs. Estocástico: Esse aspecto é mais relevante para abordagens particio-

nais que otimizam uma função de erro quadrático. Essa otimização pode ser alcançada

utilizando técnicas tradicionais, ou por meio de uma busca aleatória do espaço de estados,

que compreende todas as possibilidades de rotulação.

Para mais informações sobre o processo de agrupamento de dados, sugere-se a leitura dos

materiais publicados em Jain & Dubes (1988) e em Faceli et al. (2011).

2.3.2

Algoritmo K-means

O algoritmo K-means é um algoritmo particional que requer a definição do número de

agrupamentos k como entrada. Esse algoritmo utiliza uma técnica de realocação interativa

que encontra um ótimo local. Devido a sua simplicidade e variadas implementações é um

algoritmo comumente utilizado, apesar da limitação de definir o número de grupos k previa-

mente(Simovici, 2007).

O K-means tem como objetivo minimizar o erro quadrático, definido na Equação 2.6, onde µj é o vetor centróide do grupo Gj e d(xi, µj) é a distância Euclideana entre xi e µj, ou seja,

o critério seguido pelo K-means é minimizar a distância entre cada ponto e o centróide do

agrupamento ao qual o ponto pertence.

k

E =

d(xi, µj)

(2.6)

j=1 xi∈Gw

17

Para realizar a tarefa de agrupamento de dados, o algoritmo K-means, que tem como parâ-

metros o conjunto de dados X e número de grupos k e seu funcionamento básico é mostrado

no Algoritmo 2.1. O critério utilizado pelo K-means é minimizar o erro quadrático entre os exemplos e o centroide do grupo ao qual o exemplo pertence. Portanto, o K-means tem como

resultado uma partição formada por grupos de formato hiperesférico de mesmo tamanho, ou

por grupos bem separados.

Algoritmo 2.1: Funcionamento básico do K-means

Entrada: Conjunto de dados X

Entrada: Número de grupos k

Saída: Partição do conjunto X em k grupos

1 inicio

2

Definir aleatoriamente k centroides de grupos;

3

repita

4

para cada exemplo xi ∈ X e cada grupo Gw, w = 1, · · · k hacer

5

Calcular a distância entre xi e o centroide do grupo Gw;

6

fin

7

para cada exemplo xi hacer

8

Associar xi ao grupo com centroide mais próximo;

9

fin

10

para cada grupo Gw hacer

11

Recalcular o centroide;

12

fin

13

até que nenhuma alteração nas associações de exemplos a grupos seja realizada;

14

retorna Partição formada pelo Gk grupos

15 fin

Os critérios de parada do K-means mais comumente utilizados são: execução de um deter-

minado número de iterações, e estabilização dos centroides. Esses critérios de parada podem

ser utilizados em conjunto ou individualmente. Vale ressaltar que o resultado desse algoritmo

depende de como os centroides são definidos inicialmente.

A complexidade do algoritmo K-means é O(knp), onde p é o número de atributos do con-

junto de dados X (Simovici, 2007).

2.3.3

Índices de Validação

Para validar uma partição, em geral, utilizam-se índices estatísticos que julgam, de uma

maneira quantitativa e objetiva, o mérito das estruturas encontradas. Um índice quantifica a

qualidade de uma partição, com base em alguma informação. Um critério de validação define

como um determinado índice é aplicado para validar uma partição. Portanto, um critério de vali-

dação é uma estratégia para validar uma estrutura de agrupamento e um índice é uma estatística

pela qual a validade é testada (Jain & Dubes, 1988).

18

Capítulo 2. Trabalhos relacionados

2.3. Agrupamento de Dados

Jain & Dubes (1988) definiram três tipos de critérios para investigar a validade de agrupamentos:

• Critérios Relativos: comparam diversas partições para decidir qual delas é melhor, de

acordo com algum critério. Esses critérios podem ser utilizados na comparação de algo-

ritmos de agrupamento ou na definição do melhor valor para um parâmetro. Por exemplo,

decidir qual o melhor valor de k dado um conjunto de partições com diferentes valores de

k para o K-means, ou seja, quantos grupos devem ser considerados.

• Critérios Internos: utilizados para medir a qualidade de partições geradas com base

apenas nos dados originais.

• Critérios Externos: avaliam uma partição com base em uma estrutura pré-identificada,

que reflete o conhecimento prévio do pesquisador sobre a organização dos dados.

Neste trabalho, para a seleção de atributos é avaliado o índice interno Silhueta, bem como

a correspondência da partição gerada com a partição real, por meio do índice externo Rand

Corrigido (CR – Corrected Rand), ambos descritos a seguir.

Índice Silhueta

O índice de validação Silhueta é calculado para cada exemplo em um grupo. Esse índice

avalia a qualidade das partições baseando-se na proximidade entre padrões de um grupo e na

distância dos padrões de um grupo em relação ao grupo mais próximo (Kaufman & Rousseeuw,

1990).

Silhuetas identificam quais padrões estão bem situados em seus grupos e quais estão fora

de um grupo apropriado. Podem ser utilizadas medidas de similaridades quanto de dissimilari-

dades (distâncias) (Faceli et al., 2011). Dados a(xi), a dissimilaridade média do padrão xi em relação a todos os outros padrões do grupo Gi, d(xi, Gj), a dissimilaridade média do padrão

xi em relação aos padrões do agrupamento Cj e b(xi), a menor dissimilaridade média de xi

em relação a todos os demais agrupamentos, dada pela Equação 2.7, a silhueta de um padrão s(xi), empregando dissimilaridade, é dada pela Equação 2.8 (Rousseeuw, 1987; Kaufman &

Rousseeuw, 1990).

b(xi) = min d(xi, Cj)

(2.7)

Ci=Cj

1 − a(x

i)/b(xi),

a(xi) < b(xi)

s(xi) =

0,

a(x

(2.8)

i) = b(xi)

b(xi)/a(xi) − 1,

a(xi) > b(xi)

19

Para a utilização de similaridades, utilizam-se a (xi) e d (xi, Cj), as respectivas similarida-

des médias, b (xi), dada pela Equação 2.9, e s(xi), dada pela Equação 2.10.

b (xi) = min d (xi, Cj)

(2.9)

Ci=Cj

1 − b (x

i)/a (xi),

a (xi) > b (xi)

s(xi) =

0,

a (x

(2.10)

i) = b (xi)

a (xi)/b (xi) − 1,

a (xi) < b (xi)

Um exemplo bem situado dentro do grupo tem uma silhueta com valor próximo de 1 e um

valor −1 indica que um exemplo deveria ser associado a outro grupo.

A silhueta depende apenas da partição dos dados, não dependendo do algoritmo de agrupa-

mento utilizado. Esse índice de validação é apropriado nos casos em que a proximidade está

em uma escala de proporção, como a distância Euclideana, e para a identificação de grupos

compactos e bem separados (Rousseeuw, 1987).

Nesta Tese, foi utilizada a implementação de Silhueta disponível no pacote fpc do software

R, que é uma implementação do índice definido em Rousseeuw (1987) e Kaufman & Rousse-

euw (1990).

Índice Rand Corrigido – CR

O Rand Corrigido (CR – Corrected Rand) (Hubert & Arabie, 1985) é um índice de validação externa que não é sensível ao número de agrupamentos (Jain & Dubes, 1988). O CR é um dos índices de validação externa mais usado em avaliações e comparações de algoritmos de

agrupamento (Faceli, 2006).

Esse índice determina a similaridade entre duas partições πa e πb pela concordância, positiva

ou negativa, na associação de pares de exemplos aos grupos, ou seja, o índice penaliza associ-

ações diferentes de pares de exemplos nas duas partições. De maneira geral, se dois exemplos

x1 e x2 são associados ao mesmo grupo em πa e a grupos distintos em πb, o valor do índice é

diminuído.

O índice CR é uma correção estatística do índice Rand e é dado pela Equação 2.11 (Hubert

& Arabie, 1985), onde gij é o número de exemplos comuns aos grupos Gi de πe e Gj de πr, gi.

é o número de exemplos no grupo Gi de πe, g.j é o número de exemplos no grupo Gj de πr e

20

Capítulo 2. Trabalhos relacionados

2.4. Seleção de Atributos para Agrupamento de Dados

ke e kr representam a quantidade de grupos nas partições πe e πr, respectivamente.

ke

kr

ke

kr

gij

g

g

n

i.

.j

/

2

2

2

2

i=1 j=1

i=1

j=1

CR(πeπr) =

(2.11)

ke

kr

ke

kr

gi.

g

g

g

n

+

.j

/2 −

i.

.j

/

2

2

2

2

2

i=1

j=1

i=1

j=1

O índice Rand corrigido varia no intervalo [−1, 1], apresentando valores próximos ou me-

nores que 0 quando a semelhança se deve ao acaso e valor 1 quando as partições são idênticas

(Hubert & Arabie, 1985). Esse índice apresenta um valor mínimo de −1, que não é atingido.

Em geral, partições muito diferentes resultam em um valor próximo de 0. Como valores meno-

res que 0 não têm aplicação prática (Hubert & Arabie, 1985), a normalização para o intervalo apresenta vantagens. Nesta Tese, a implementação do índice CR utilizada está presente no

pacote fpc do software R.

2.4

Seleção de Atributos para Agrupamento de Dados

Técnicas de seleção de atributos estão geralmente relacionadas ao aprendizado supervisi-

onado (Devaney & Ram, 1997; Dash et al., 2002), pois, a informação da classe, em geral, é utilizada para guiar a seleção dos atributos relevantes (Dash et al., 2002). Entretanto, em problemas de agrupamento de dados, a informação da classe não está disponível, o que dificulta a

seleção de atributos relevantes.

Em geral, as técnicas de seleção de atributos em agrupamentos de dados são classificadas em

abordagens baseadas em wrapper, baseadas em filtros e técnicas híbridas. Técnicas baseadas

na abordagemwrapper utilizam o resultado de algoritmos de agrupamento para identificar quais

atributos são importantes. As técnicas baseadas em filtros utilizam informações do conjunto de

dados para calcular a importância de um determinado atributo. As técnicas híbridas utilizam

tanto informações do conjunto de dados, quanto o resultado de algoritmos de agrupamento

(Dash & Liu, 2000; Liu & Yu, 2005; Covões & Hruschka, 2011).

Uma generalização da abordagem baseada em filtros é apresentada no Algoritmo 2.2. Nessa abordagem, para um dado conjunto de dados X, o algoritmo inicia a busca a partir de um subconjunto Finicial (que pode ser um conjunto vazio, o conjunto completo ou um conjunto alea-

tório de atributos) e faz uma varredura pelo espaço de atributos utilizando uma dada estratégia

de busca. Cada subconjunto de atributos F ∗ é avaliado por uma medida independente M e,

em seguida, comparado com o melhor valor até então. Se melhor, F ∗ passa a ser considerado

o melhor subconjunto de atributos. A busca é finalizada quando um determinado critério de

parada δ é atingido.

Ao variar a estratégia de busca e a medida de avaliação, nas etapas gerar(X) (linha 5) e

21

Algoritmo 2.2: Generalização de uma técnica baseada em Filtro

Entrada: Conjunto de dados de treinamento com p atributos: X = f0, f1, · · · , fp

Entrada: Subconjunto de busca inicial: Finicial

Entrada: Critério de parada: δ

Saída: Subconjunto de atributos ótimo: Fmelhor

1 inicio

2

Fmelhor ← Finicial;