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.

/* avalia Finicial por meio de uma medida independente M

*/

3

γmelhor ← avalia(Finicial, X, M );

4

repita

/* Gerar um subconjunto de atributos para avaliação */

5

F ∗ = gerar(X);

/* avalia o subconjunto F ∗ por meio de M

*/

6

γ ← avalia(F ∗, X, M );

7

se γ > γmelhor então

8

γmelhor ← γ;

9

Fmelhor ← F ∗;

10

fim

11

até δ ser atingido;

12

retorna Fmelhor

13 fin

avalia(F ∗, X, M) (linhas 3 e 6), diferentes técnicas baseadas em filtros, podem ser desenvol-

vidas. A abordagem baseada em filtro utiliza um critério de avaliação que não faz uso de

informações sobre a qualidade da partição, encontrada por um algoritmo de agrupamento de

dados, para a seleção dos atributos mais relevantes. Como resultado, não possui nenhum viés

em relação a uma técnica de agrupamento de dados (Liu & Yu, 2005).

A abordagem wrapper é exemplificada no Algoritmo 2.3. Essa abordagem é semelhante a

abordagem baseada em filtro, exceto que é utilizado um algoritmo de agrupamento de dados

pré-definido A, ao invés de uma medida M , independente de um modelo descritivo, como um

agrupamento de dados, para a avaliação do subconjunto de atributos.

Nessa abordagem, cada subconjunto de atributos F ∗ é avaliado por meio da aplicação de um

algoritmo de agrupamento de dados e da avaliação de sua influência na qualidade do agrupa-

mento de dados gerado. Ao variar a estratégia de busca (função gerar(X), linha 5) e o algoritmo

de agrupamento A (linhas 3 e 6), é possível gerar diferentes conjuntos de atributos utilizando

uma abordagem baseada em wrapper. Como algoritmos de agrupamentos são utilizados para

controlar a seleção dos subconjuntos de atributos, essa abordagem tende a ser computacional-

mente mais custosa do que a abordagem baseada em filtro (Liu & Yu, 2005).

Para aproveitar as vantagens das técnicas baseadas nas abordagens wrapper e em filtro,

utilizou-se uma abordagem híbrida, generalizada no Algoritmo 2.4. Essa abordagem utiliza uma medida independente e um algoritmo de agrupamento de dados para selecionar um sub-22

Capítulo 2. Trabalhos relacionados

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

Algoritmo 2.3: Generalização de uma técnica baseada em wrapper

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;

/* avalia Finicial por meio de um algoritmo de agrupamento A

*/

3

γmelhor ← avalia(Finicial, X, A);

4

repita

/* Gerar um subconjunto de atributos para avaliação */

5

F ∗ = gerar(X);

/* avalia o subconjunto F ∗ por meio de A

*/

6

γ ← avalia(F ∗, X, A);

7

se γ > γmelhor então

8

γmelhor ← γ;

9

Fmelhor ← F ∗;

10

fim

11

até δ ser atingido;

12

retorna Fmelhor

13 fin

conjunto de atributos. Como critério de parada, é utilizada a qualidade da partição gerada por

um algoritmo de agrupamento de dados (Liu & Yu, 2005).

Na literatura, é possível encontrar técnicas que se enquadram em um desses modelos. Mir-

kin (1999) propôs uma versão “dividir para conquistar” do algoritmo K-means. Além da partição dos dados, o algoritmo também define a contribuição de cada atributo na geração des-

ses agrupamentos, o que enquadra essa técnica como baseada na abordagem wrapper. Essa

contribuição é utilizada para definir quais atributos devem ser selecionados. Apesar de apre-

sentar bons resultados, seu desempenho foi avaliado apenas experimentos com conjuntos de

dados pequenos: Iris (matriz 150x4), Soybean (matriz 47x35) ambas do repositório Asuncion

& Newman (2007) e Disorder (matriz 44x17, descrita em (Mirkin, 1999)). Por ser uma técnica baseada wrapper, existe uma dependência do algoritmo de agrupamento utilizado, nesse caso,

uma variante do algoritmo de agrupamento K-means.

Dash & Liu (2000) propuseram uma técnica baseada em wrapper que utiliza a entropia para identificar atributos de ruído e sem importância em um conjunto de dados. A influência de um

dado atributo d é calculada a partir da entropia do conjunto de dados sem o atributo d. Dash

& Liu (2000) definem a entropia a partir da similaridade, Si

(Equação 2.12), de modo que a

1,i2

similaridade Si

entre dois objetos X

1,i2

1 e X2 é alta se os objetos estão próximos e baixa quando

esses objetos estão distantes. A Entropia Ei

(Equação 2.13) é baixa se S

for alto ou baixo

1,i2

i1,i2

e Ei

será alta caso contrário. Isso significa que a entropia apresenta valores baixos quando

1,i2

23

Algoritmo 2.4: Generalização de uma técnica de seleção de atributos híbrida

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

Entrada: Subconjunto de busca inicial: Finicial

Saída: Subconjunto de atributos ótimo: Fmelhor

1 inicio

2

Fmelhor ← Finicial;

/* Calcula a cardinalidade de Finicial

*/

3

c0 = card(Finicial);

/* avalia Finicial por meio de uma medida independente M

*/

4

γmelhor ← avalia(Finicial, X, M );

/* avalia Finicial por meio de um algoritmo de agrupamento A

*/

5

θmelhor ← avalia(Finicial, X, A);

6

para c ← c0 + 1 até p hacer

7

para i ← 0 até p − c hacer

/* gera um subconjunto com cardinalidade c para

avaliação

*/

8

F ∗ ← Fmelhor ∪ {fi};

/* avalia o subconjunto F ∗ por meio da medida M

*/

9

γ ← avalia(F ∗, X, M );

10

se γ > γmelhor então

11

γmelhor ← γ;

12

F

← F ∗;

melhor

13

fim

14

fin

/* avalia F

por meio do algoritmo A

melhor

*/

15

θ = avalia(F

, X, A);

melhor

16

se θ > θmelhor então

17

θmelhor ← θ;

18

F

← F ∗;

melhor

19

senão

/* Interrompe a execução e retorna Fmelhor como

resultado

*/

20

retorna Fmelhor

21

fim

22

fin

23

retorna Fmelhor

24 fin

24

Capítulo 2. Trabalhos relacionados

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

X1 e X2 têm alguma relação e elevados quando esses atributos não estão relacionados.

Si

= eα×Di1,i2

(2.12)

1,i2

Ei

= −S

log S

− (1 − S

× log (1 − S

))

(2.13)

1,i2

i1,i2

i1,i2

i1,i2

i1,i2

A similaridade (Equação 2.12) é baseada na distância Di

e pode ser aplicada tanto a

1,i2

valores numéricos quanto categóricos. Para dados numéricos, Dash & Liu (2000) utilizam a distância Euclideana. para dados categóricos, a distância de Hamming é utilizada. O valor de α

é calculado, automaticamente, ao atribuir 0.5 na equação ¯

S = e−α× ¯

D , o que significa entropia

máxima; tem-se α = − ln 0.5

¯

em que ¯

D é a média das distâncias entre os exemplos.

D

Para definir um ranking dos atributos, calcula-se a entropia de cada atributo. Se a remoção

do atributo A1 causar mais desordem que a remoção do atributo A2 então a EA > E , em que

1

A2

EA e E

representam a entropia após a remoção dos atributos A

1

A2

1 e A2, respectivamente. A

definição de quantos atributos serão selecionados é feita a partir da verificação da qualidade do

resultado do algoritmo K-means. O critério de parada para definir quantos atributos devem ser

utilizados é definido visualmente, com base na curva gerada pela qualidade da partição gerada

pelo K-means.

Posteriormente, Dash et al. (2002) evoluíram o trabalho de Dash & Liu (2000) e propuseram uma solução baseada em filtros para selecionar os atributos mais relevantes. A entropia

é utilizada para identificar grupos nos dados. A entropia é, também, utilizada como uma me-

dida para comparar subconjuntos de atributos, pois seu valor independe da cardinalidade do

subconjunto. Nesse caso, baixos valores de entropia representam subconjunto de agrupamentos

bem formados e altos valores de entropia, o contrário. A principal desvantagem é a falta de

consenso na avaliação dos agrupamentos. Por ser uma técnica baseado em filtros, Dash et al.

(2002) desenvolveram uma técnica que não necessita de informação a priori sobre o conjunto de dados.

Outro método de seleção de atributos para dados não rotulados é o FSSEM (Feature Subset

Selection using EM Clustering) (Dy & Brodley, 2000a,b, 2004) que faz uso do modelo de mistura Gaussiana para identificar subconjuntos de atributos que melhor descobrem agrupamentos

naturais nos dados. O FSSEM é uma técnica baseada em wrapper (Dy & Brodley, 2000a). Para a busca no espaço de atributos, Dy & Brodley (2000b) fazem uma busca incremental, iniciando com zero atributos e, sequencialmente, adicionando um atributo de cada vez. O atributo

adicionado é aquele que provê o maior valor quando combinado com os atributos previamente

escolhidos. A busca é interrompida quando, ao adicionar novos atributos, o critério de seleção

não melhora. Por ser baseada em wrapper, ela utiliza um algoritmo de agrupamento de dados,

nesse caso, o EM clustering. Dois critérios de seleção são empregados para o subconjunto de

atributos utilizados, são eles: Scatter Separability e Maximum Likelihood.

• Scatter Separability: a separação dos agrupamentos é definida pela Scatter Separability.

25

Sw (Equação 2.14) é a matriz de espalhamento intra-cluster e Sb a matriz de espalhamento entre agrupamentos.

k

Sw =

πjE (X − µj) (X − µj)T |ωj

(2.14)

j=1

k

Sb =

πj (µj − M0) (µj − M0)T

(2.15)

j=1

k

M0 = E{X} =

πjµj

(2.16)

j=1

em que πj é a probabilidade de um exemplo pertencer ao grupo ωj, X é um vetor de

atributos representando um exemplo do conjunto de dados, k é o número de grupos, µj

é a média dos exemplos do grupo ωj, M0 é média de todos os exemplos e E[.] é o valor

esperado do operador. Dy & Brodley (2004) escolhem o critério trace(S1 S

S

w

b).

S1w b

é Sb normalizado pela covariância média do grupo. Logo, quanto maior for o valor de

trace(S1 S

w

b), maior é a distância normalizada entre os grupos, o que resulta em uma

melhor discriminação dos grupos.

• Maximum Likelihood: Ao utilizar o algoritmo de agrupamento de dados EM, Dy & Bro-

dley (2000b) supõem que cada grupo encontrado é uma Gaussiana. Esse critério descreve o quanto o modelo (uma mistura de Gaussianas) se ajusta aos dados. Os melhores grupos,

nesse caso, são os agrupamentos naturais, isto é, os grupos que são Gaussianas.

Ao procurar pelo melhor subconjunto de atributos, o número de grupos k, depende do sub-

conjunto de atributos avaliados (Dy & Brodley, 2004; Li et al., 2007). O FSSEM-k (Dy & Bro-

dley, 2004) procura por um valor de k para um subconjunto de atributos utilizando o método de Bouman (Dy & Brodley, 2004). para mesclar grupos e adicionar um termo de penalização usando o critério de informação Bayesiana. A penalização é necessária pois o Maximum Likelihood aumenta à medida em que o número de grupos aumenta e procura-se evitar o caso trivial

em que cada exemplo é um grupo (Dy & Brodley, 2004).

A técnica SPEC (Spectral Feature Selection) (Zhao & Liu, 2007, 2012) pode ser utilizada tanto para problemas supervisionados quanto não-supervisionados. Neste trabalho a técnica

SPEC é utilizada como uma abordagem baseada em filtro para seleção de atributos em um

contexto não-supervisionado. Ao construir uma matriz de similaridade S a partir do conjunto

de dados X, os autores afirmam que a dispersão das instâncias pode ser estudada ao analisar o

espectro do grafo G, que é induzido a partir da matriz S.

Ao considerar um contexto não-supervisionado, os rótulos de classe não são utilizados para

gerar a matriz S e o grafo G. Entretanto, os rótulos de classe apresentam uma semelhança

com a estrutura do grafo G. Um atributo consistente com a estrutura do grafo atribui valores

26

Capítulo 2. Trabalhos relacionados

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

similares a instâncias que estão próximas no grafo G (Zhao & Liu, 2007). Diversas variantes da técnica SPEC podem ser definidas ao adotar diferentes matrizes de similaridade. Para o caso

não-supervisionado, a função de kernel gaussiano, definida na Equação 2.17 é utilizada por

Zhao & Liu (2007). Nessa equação, xi e xj representam o i−ésimo e o j−ésimo exemplo do conjunto de dados X, respectivamente. Como S é simétrico, o grafo G não é direcionado.

||xi−xj ||2

Sij = e−

2σ2

(2.17)

Em seguida, calcula-se a matriz de graus D, definida na Equação 2.18. Onde di é definido na Equação 2.19 e n é a quantidade de exemplos no conjunto de dados X.

di

if i = j

Di,j =

(2.18)

0

caso contrário.

n

Si,j

(2.19)

j=1

A partir da matriz de graus D e da matriz de similaridade S, os autores obtiveram a matriz

Laplaciana L e a matriz Laplaciana normalizada L∗ (Equações 2.20 e 2.21, respectivamente).

L = D − S

(2.20)

L∗ = D− 12 LD− 12

(2.21)

Com a matriz Laplaciana normalizada L∗, os autores calcularam a decomposição espectral

1

(λi, ξi) para definir o valor de ranking para o atributo fi (Equação 2.22). Onde ξ0 = D 2 e e αj = cosθj, com thetaj sendo o ângulo entre ˆ

fi e ξj; e ˆ

fi vetor de atributos ponderados

1

definido por D 2 fi .

1

||D 2 fi||

n−1 α2λ

ˆ

j

j

f T (L∗) ˆ

f

ϕ(f

j=1

i

i

i) =

=

.

(2.22)

n−1 α2

1 − ˆ

f T ξ

j=1

j

i

0

O Algoritmo 2.5 apresenta um pseudo-código para a criação do ranking de atributos utilizando a técnica SPEC. A quantidade de atributos a serem selecionados é definido pelo usuário

a partir do resultado do algoritmo.

Variações da técnica SPEC aqui apresentada podem ser encontradas em (Zhao & Liu, 2012).

Essas variações consideram diferentes funções de similaridade e de ranking.

Mitra et al. (2002) propuseram um método de seleção de atributos baseado filtros. Esse método envolve duas etapas, são elas: particionamento do conjunto de atributos em um número

de subconjuntos homogêneos (grupos) e a seleção de atributos representativos de cada grupo.

O particionamento dos atributos é baseado no princípio do kNN , utilizando como medida

de similaridade o índice de compressão máxima da informação (λ2), definido na Equação 2.23,

27

Algoritmo 2.5: SPEC – Spectral Feature Selection

Entrada: Conjunto de dados X

Entrada: Número de exemplos: n

Saída: Ranking dos atributos: RankF

1 inicio

2

Gerar matriz de similaridade S a partir do conjunto de dados X;

3

Gerar grafo G a partir de matriz S;

4

Gerar a matriz de graus D a partir da matriz G;

5

Definir L e L∗ de acordo com as Equações 2.20 e 2.21;

6

para cada vetor de atributos fi hacer

1

ˆ

2 fi

7

fi ← D

;

1

||D 2 fi||

8

Fi ← ϕ(fi);

9

fin

10

RankF ← ranking ordenado de maneira decrescente dos valores Fi;

11

retorna RankF ;

12 fin

onde var(fi) é a variância de fi e /rho(fi, fj), o é coeficiente de correlação entre fi e fj

(Equação 2.24) (Mitra et al., 2002).

2λ2(fi, fj) = (var(fi) + var(fj)) −

ξ2 − 4var(fi)var(fj)(1 − ρ(fi, fj)2)

(2.23)

cov(f

ρ(f

i, fj )

i, fj ) =

(2.24)

var(fi)var(fj)

Considerando a similaridade apresentada, o primeiro passo do método é calcular os k vizi-

nhos mais próximos de cada um dos atributos. Dentre esses, o atributo que contém o subcon-

junto mais compacto (determinado pela distância do vizinho mais distante) é selecionado e a k

vizinhança de atributos é descartada. O processo é repetido para os atributos restantes até que

todos sejam selecionados ou descartados (Mitra et al., 2002).

Durante a execução do algoritmo, um limiar de erro constante ( ) é definido como a distância

do k-ésimo vizinho mais próximo do atributo selecionado na primeira iteração. Esse limiar é

utilizado para controlar o valor de k no decorrer das iterações, de modo que se o valor de γ2 for

maior do que

o valor de k é decrementado.

O valor inicial do kNN é informado pelo usuário. Segundo Mitra et al. (2002), esse parâ-

metro pode ser útil para controlar a representação dos dados considerando diferentes níveis de

detalhamento. Os resultados apresentados em (Mitra et al., 2002) mostram que esse filtro tem um desempenho superior aos métodos branch and bound(Devijver & Kittler, 1982), sequential floating forward search(Pudil et al., 1994), sequencial forward search(Devijver & Kittler, 1982)

e stepwise clustering(King, 1967), tanto em tempo de execução quanto em termos de qualidade.

28

Capítulo 2. Trabalhos relacionados

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

No entanto, definir um valor para esse parâmetro pode ser uma tarefa difícil de ser reali-

zada na prática (Covões & Hruschka, 2011), pois resta ao usuário estimar um parâmetro crítico do algoritmo. A complexidade desse método é definida como O(M 2N ), onde M eN representam a quantidade de atributos e exemplos, respectivamente, para um determinado valor de

kNN (Mitra et al., 2002). Caso o valor de kNN seja desconhecido, esse pode variar no intervalo [kNN

, k

]. Ao realizar análise considerando k

= 1 e k

= M − 1, a

min

N Nmax

N Nmin

N Nmax

complexidade do algoritmo pode chegar a O(M 2N + M 3).

Li et al. (2006) propuseram uma abordagem híbrida baseada nos trabalhos de Dash & Liu

(2000); Dash et al. (2002). Essa abordagem ordena os atributos de acordo com a importância para a partição encontrada por um algoritmo de agrupamento de dados. Para isso, é necessário

apenas o cálculo de n valores e a ordenação desses valores. O índice de ordenação utiliza a en-

tropia exponencial. Seja Sp,q a similaridade entre dois objetos Xp e Xq, e seja |D| a quantidade

de exemplos em que o índice de ranking é calculado. Esse índice é definido de acordo com a

Equação 2.25.

|D| |D|

H =

Sp,q × e(1−Sp,q) + (1 − Sp,q × eSp,q

(2.25)

p=1 q=1

Em que Sp,q admite valores entre [0.0 − 1.0]. Quando Sp,q → 0(1), H diminui. Entretanto,

Sp,q → 0, 5, H aumenta. O modo de calcular o ranking é o mesmo utilizado por Dash &

Liu (2000). Para identificar quantos atributos são escolhidos, Li et al. (2006) utilizam uma abordagem em dois passos, um utiliza uma técnica baseada em filtro e o outro uma técnica

baseada em wrapper, o que define a abordagem como híbrida. O primeiro passo é encontrar um

conjunto de atributos utilizando o Fuzzy Feature Evaluation Index (FFEI). Como um mecanismo

para remover atributos potencialmente redundantes não foi definido, o segundo passo consiste

em refinar o resultado e utilizar uma abordagem mais sofisticada para procurar um conjunto de

atributos mais compacto. Isso é feito utilizando o algoritmo de agrupamento de dados Fuzzy

C-Means (Bezdek, 1981) e avaliando a qualidade do resultado.

Uma outra abordagem híbrida é a técnica Simplified Silhouette Filter (SSF) (Covões et al.,

2009; Covões & Hruschka, 2011). Essa técnica particiona o conjunto de atributos F em uma coleção CX = {C1, C2, · · · , Cy}, formada por y subconjuntos disjuntos de atributos correlacionados Ci de F . Posteriormente, são selecionados atributos de cada um desses grupos.

Assim como no agrupamento de exemplos, atributos em um mesmo grupo são mais seme-

lhantes entre si do que atributos pertencentes a grupos distintos. Para calcular a similaridade

(correlação) entre os atributos, os autores utilizaram medidas de correlação definidas por Mitra

et al. (2002), Maximal Information Compression Index (Equação 2.23), e por Au et al. (2005),

Interdependence Redundancy Measure.

A técnica SSF utiliza um procedimento heurístico, baseado no critério da Silhueta Simplifi-

cada (Hruschka et al., 2004, 2006), para encontrar o número de grupos e a partição de atributos correspondente.

29

A Silhueta Simplificada baseia-se no cálculo das distâncias entre atributos e o centroide do

grupo, especificamente Covões & Hruschka (2011) utilizam medoides ao invés de centroides.

Para a Silhueta Simplificada (Hruschka et al., 2004, 2006), a dissimilaridade média d(fi, Gj) de um atributo fi é calculada considerando-se a distância entre o atributo fi e o medoide de

grupo Gj, Equações 2.26 e 2.27, onde f (c(fi, fj)) é uma medida de dissimilaridade calculada em função da correlação entre atributos c(fi, fj) e ηj é o medoide do grupo Gj.

d(fi, Gj) = f (c(fi, ηj))

(2.26)

ηj = arg min

f (c(fv, fu))

(2.27)

fv∈Gj

fu∈Gj

Covões & Hruschka (2011) utilizam o algoritmo k-medoids (Algoritmo 2.6) para obter as partições que serão avaliadas pela Silhueta Simplificada.

Algoritmo 2.6: Algoritmo k-medoids

Entrada: Quantidade de grupos k

Saída: Partição de atributos

1 inicio

2

Crie uma partição inicial aleatória de atributos com k grupos não-vazios;

3

repita

4

Calcule a medoide do grupo, utilizando a equação 2.27, da partição atual;

5

Conecte cada atributo ao grupo com a medoide mais próxima;

6

até não haver alteração nas medoides por duas iterações seguidas;

7

retorna Partição de atributos

8 fin

A Silhueta Simplificada é um critério numérico que permite estimar automaticamente o

número de grupos, o que possibilita a reduzir o impacto da limitação do k-medoids, que é definir

a priori a quantidade k de grupos. A estratégia de amostragem, descrita no Algoritmo 2.7,

apresenta o método utilizado para estimar o valor de k∗ de acordo com a Silhueta Simplificada,

bem como encontrar a partição de atributos correspondente a esse k∗ (Covões et al., 2009;

Covões & Hruschka, 2011).

De acordo com os resultados apresentados por Covões & Hruschka (2011), os autores su-gerem que dois atributos de cada grupo sejam utilizados. Esses atributos são: o que representa

a medoide do grupo e o atributo de menor correlação com a medoide.

Em seu pior caso, a complexidade do filtro SSF é O(M 3), quando se faz necessária uma

busca exploratória considerando todas as possíveis quantidades de grupos de atributos, ou seja,

para todo k ∈ 2, · · · , M − 1. Entretanto, a complexidade estimada pode ser reduzida caso

algum conhecimento de domínio esteja disponível (Covões & Hruschka, 2011).

30

Capítulo 2. Trabalhos relacionados

2.5. Considerações Finais

Algoritmo 2.7: Estratégia de amostragem para o k-medoids

Entrada: Quantidade mínima e máxima de grupos, kmin e kmax respectivamente.

Entrada: Quantidade de partições iniciais (np) para o k-medoid

Saída: SSV e seu correspondente grupo de atributos k∗

1 inicio

/* SSV = Valor da Silhueta Simplificada

*/

2

SSV ← − inf;

3

para cada k ∈ {kmin, kmin + 1, · · · , kmax} hacer

4

Crie aleatoriamente np partições de atributos iniciais em k grupos não-vazios;

5

para cada Partição a criada hacer

6

Execute o k-medoids e calcule a sua silhueta simplificada;

7

M V ← melhor valor obtido dentre todas as partições;

8

fin

9

se M V > SSV então

10

SSV ← M V ;

11

k∗ ← k;

12

Armazene a partição correspondente para k∗;

13

fim

14

fin

15

retorna SSV e a partição de atributos correspondente k∗

16 fin

2.5

Considerações Finais

Nesta Tese, a Teoria do Caos serviu de base para a definição da técnica proposta, que utiliza

uma modificação do algoritmo de falsos vizinhos mais próximos.

Para comparar a técnica proposta nesta Tese, três técnicas foram selecionadas. São elas:

MitraFS(Mitra et al., 2002), FSSEM-k(Dy & Brodley, 2004) e SSF(Covões & Hruschka, 2011),

que são abordagens baseada em filtro, wrapper e híbrida, respectivamente.

O algoritmo K-means e os índices de validação Silhueta e CR são utilizados para avaliar e

comparar os resultados das técnicas.

31

Capítulo

3

Técnica FQFNN: Feature

Quantification by False Nearest

neighbors

3.1

Considerações Iniciais

A seleção de atributos pode ser formalmente definida da seguinte forma: 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 ao modelo original (que utiliza F ), ao mesmo

tempo em que se reduz o tempo de processamento.

Em geral, a seleção de atributos está relacionada com problemas supervisionados. Como

esse tipo de problema não é foco deste trabalho, para maiores informações sugere-se a leitura

de (Zongker & Jain, 1996; Guyon & Elisseeff, 2003; Liu & Motoda, 2007).

No caso de problemas não-supervisionados, a definição da qualidade do modelo induzido

por F ∗ é dada pela aplicação de uma medida de qualidade ao modelo, por exemplo, a Silhueta

(Rousseeuw, 1987; Kaufman & Rousseeuw, 1990).

A seleção de atributos não-supervisionada pode ser dividida em duas etapas, que são bem

definidas pelas duas perguntas a seguir:

1. Quais atributos são mais importantes?

2. Quantos atributos devem ser utilizados?

33

Em geral, as técnicas existentes na literatura procuram resolver as duas questões simultane-

amente (Covões & Hruschka, 2011; Li et al., 2007; Mitra et al., 2002; Dy & Brodley, 2004),

definindo quais atributos serão selecionados ao mesmo tempo em que definem quantos serão

utilizados.

A primeira questão está ligada à definição da relevância do atributo, que varia de acordo com

a técnica utilizada. A segunda questão, que diz respeito à quantidade de atributos a selecionar,

apresenta uma tendência a ser definida pelo usuário. Podendo ser tanto de maneira direta (Dash

& Liu, 2000; Zhao & Liu, 2007; Li et al., 2007), por meio da definição de um limiar ou da intervenção direta do usuário, quanto de maneira indireta (Dy & Brodley, 2004; Mitra et al.,

2002; Covões & Hruschka, 2011), por meio de um parâmetro existente na técnica.

Na presente Tese é proposta uma técnica de definição automática da quantidade de atributos

selecionados.

3.2

Falsos vizinhos mais próximos aplicado a conjuntos de

dados

Técnicas baseadas em teoria do caos dão suporte ao estudo do comportamento de séries tem-

porais. Por exemplo, o método de falsos vizinhos mais próximos (FNN, do inglês False Nearest

Neighbors é utilizado para determinar a dimensão embutida, isto é, quantas dimensões ou eixos

são necessários para desdobrar o comportamento de uma série, permitindo o seu estudo. De

modo complementar, a Auto Informação Mútua calcula a dimensão de separação, permitindo a

extração das regras geradoras da série temporal.

Embora os teoremas de imersão de Whitney e Takens sejam geralmente aplicados no con-

texto de sistemas dinâmicos, com o intuito de estudar séries temporais, órbitas e tendências, es-

ses teoremas são ferramentas matemáticas desenvolvidas para embutir manifolds m-dimensionais

em espaços de maior dimensão. Ao permitir o desdobramento de atributos, é possível que esses

teoremas, especificamente o último, possam ser usados como base para a seleção de atributos

não-supervisionado. Para tanto, é investigado o uso da técnica de falsos vizinhos mais próximos

para a seleção de atributos.

A dimensão embutida é capaz de identificar o número de dimensões necessárias para des-

dobrar o comportamento de uma série temporal. Esse desdobramento utiliza o algoritmo de

falsos vizinhos mais próximos, que analisa a relação entre dois pontos para diferentes números

de dimensões. Para ilustrar o funcionamento desse método, considere um conjunto de dados X,

que contém n exemplos, cada um com p atributos. Suponha que n = τ e os atributos alinhados

como mostrado na Figura 3.1 (no exemplo, m = 2 e τ = n = 3). Ao utilizar esse atraso e aplicando o teorema de imersão como descrito por Takens (1980) para identificar a dimensão embutida (m), o que se está comparando é a relação entre atributos.

Portanto, é possível utilizar o algoritmo de falsos vizinhos mais próximos, que tem como

34

Capítulo 3. Técnica FQFNN: Feature Quantification by False Nearest neighbors

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

f1,1

f1,1

f1,2

f1,2

f2,1

f2,2

f2,1

f3,1

f3,2

f2,2

f3,1

f3,2

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

3).

base o trabalho de Kennel et al. (1992a) e Takens (1980), para identificar o número de atributos para selecionar.

A técnica FNN produz como resultado a fração de falsos vizinhos, que tem um forte rela-

cionamento com as distâncias entre exemplos reconstruídos no espaço m-dimensional. Quanto

menor a fração para um dado m, melhor é a reconstrução em m dimensões. Ao utilizar essa

fração, é possível analisar como o conjunto de dados está organizado e o quão informativo ele é,

de acordo com número de dimensões (atributos). De acordo com Kennel et al. (1992a), quando a fração de falsos vizinhos atinge 0, nenhuma mudança significativa na distância dos pontos foi

identificada. Assim, existe informação suficiente para desdobrar e entender o comportamento

do que está sendo estudado.

A fração de falsos vizinhos mais próximos (Cd) para uma dada dimensão d é definida pela

Equação 3.1, onde τ é o número de atributos (ou o atraso) e Rtol é o limiar que define se a po-sição relativa entre dois exemplos apresentou mudanças significativas. A variação de distância

V d , definida na Equação 3.2, é a variação da distância entre dois pontos ou exemplos quando i,j

diferentes números de dimensões são usadas. Nessa variação R2(.) d R2

(.) representam a

d

d+1

distância entre dois exemplos considerando d e d + 1 dimensões, como definido nas Equações

2.3 e 2.4, respectivamente.

τ −1

τ

sign[V d − R

i,j

tol]

i=1 j>i

Cd =

(3.1)

τ (τ −1)

2

R2

(xi, xj) − R2(xi, xj)

V d =

d+1

d

(3.2)

ij

R2(x

d

i, xj )

Assim, o FNN supõe inicialmente a dimensão embutida m = 1, avaliando quão distantes

exemplos, considerando

1

R , estão de seus vizinhos ao calcular as distâncias entre fi,1 e fj,1

∀ i = j. Quando a dimensão embutida é igual a m = 2, o FNN calcula as distâncias entre os

pares (fi,1, fi,2) e (fj,1, fj,2) ∀ i = j. Generalizando, quando a dimensão embutida é τ , o FNN

calcula as distâncias entre todos os pares (fi,1, . . . , fi,τ ) e (fj,1, . . . , fj,τ ) ∀ i = j.

Quando comparado com a ideia básica de comparar a distância média entre diferentes nú-

meros de dimensões, o FNN tem a vantagem de levar em consideração como esses exemplos

35

Tabela 3.1: Conjunto de dados de exemplo

F1

F2

F3

F4

F5

F6

A

2

3

26

3

1

12

B

3

5

25

6

2

12

C

5

15

12

13

3

12

D

12

17

8

15

11

12

E

13

16

22

18

12

12

F

15

6

17

6

13

12

G

21

7

1

8

20

12

H

22

8

2

6

21

12

Tabela 3.2: Distâncias – F1

A

B

C

D

E

F

G

H

A

0, 00

1, 00

3, 00

10, 00

11, 00

13, 00

19, 00

20, 00

B

1, 00

0, 00

2, 00

9, 00

10, 00

12, 00

18, 00

19, 00

C

3, 00

2, 00

0, 00

7, 00

8, 00

10, 00

16, 00

17, 00

D

10, 00

9, 00

7, 00

0, 00

1, 00

3, 00

9, 00

10, 00

E

11, 00

10, 00

8, 00

1, 00

0, 00

2, 00

8, 00

9, 00

F

13, 00

12, 00

10, 00

3, 00

2, 00

0, 00

6, 00

7, 00

G

19, 00

18, 00

16, 00

9, 00

8, 00

6, 00

0, 00

1, 00

H

20, 00

19, 00

17, 00

10, 00

9, 00

7, 00

1, 00

0, 00

se relacionam entre si. Essa relação, que não pode ser expressada pela distância média, é o

que torna o método FNN uma ferramenta poderosa para identificar o número de atributos para

selecionar.

3.3

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

Para ilustrar o funcionamento do método de falsos vizinhos mais próximos, considere a

Tabela 3.1. Nessa tabela foi definido um conjunto de dados que contém 6 atributos e 8 exemplos.

Os quatro primeiros atributos (F 1, F 2, F 3 e F 4) contêm informação útil. O atributo F 5 é

redundante e seu comportamento é semelhando ao do atributo F 1. Por último, o atributo F 6

apresenta um valor constante.

A partir desse conjunto de dados, o método FNN é aplicado para definir os atributos que

serão selecionados. Considere Rtol = 2, conforme indicam Kennel et al. (1992a).

Inicialmente, é necessário calcular as distâncias entre os exemplos do conjunto de dados,

considerando o atributo F 1 (Tabela 3.2). Em seguida, o atributo F 2 também passa a ser considerado. As distâncias entre os exemplos utilizando F 1 e F 2 são apresentadas na Tabela 3.3.

De acordo com método FNN, após calcular as distâncias entre exemplos considerando F 1

e F 1, F 2, se faz necessário avaliar a quantidade de falsos vizinhos por meio da equação 3.1.

Para esse cálculo, apenas o vizinho mais próximo de cada exemplo é considerado. Assim,

temos que os pares de exemplos (B, C) e (E, F ) são falsos vizinhos, pois V 1

= 2, 35 > R

BC

tol

36

Capítulo 3. Técnica FQFNN: Feature Quantification by False Nearest neighbors

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

Tabela 3.3: Distâncias – F1F2

A

B

C

D

E

F

G

H

A

0,00

1,12

6,18

8,60

8,51

6,67

9,71

10,31

B

1,12

0,00

5,10

7,50

7,43

6,02

9,06

9,62

C

6,18

5,10

0,00

3,64

4,03

6,73

8,94

9,19

D

8,60

7,50

3,64

0,00

0,71

5,70

6,73

6,73

E

8,51

7,43

4,03

0,71

0,00

5,10

6,02

6,02

F

6,67

6,02

6,73

5,70

5,10

0,00

3,04

3,64

G

9,71

9,06

8,94

6,73

6,02

3,04

0,00

0,71

H

10,31

9,62

9,19

6,73

6,02

3,64

0,71

0,00

Tabela 3.4: Distâncias – F1F2F3

A

B

C

D

E

F

G

H

A

0,00

0,82

6,23

8,30

5,83

5,36

10,55

10,55

B

0,82

0,00

5,51

7,56

5,06

4,82

10,02

9,99

C

6,23

5,51

0,00

2,77

4,28

4,78

7,00

6,98

D

8,30

7,56

2,77

0,00

4,69

4,84

5,06

4,91

E

5,83

5,06

4,28

4,69

0,00

3,79

8,07

7,78

F

5,36

4,82

4,78

4,84

3,79

0,00

5,71

5,56

G

10,55

10,02

7,00

5,06

8,07

5,71

0,00

0,58

H

10,55

9,99

6,98

4,91

7,78

5,56

0,58

0,00

e V 1

= 2, 35 > R

EF

tol, o que significa que a análise deve prosseguir considerando mais um

atributo, no caso F 3.

Na segunda iteração, onde m = 2, é necessário calcular as distâncias entre os exemplos

considerando 3 atributos (Tabela 3.4).

Analisando os vizinhos mais próximos considerando F 1, F 2 e calculando a variação da

distância segundo a Equação 3.1, descobre-se que o par (D, E) é uma falsa vizinhança, pois V 2

= 6, 56 > R

DE

tol. Portanto é necessário continuar o processo analisando o atributo F 4.

Na terceira iteração, m = 3, as distâncias entre os exemplos considerando 4 atributos são

calculadas (Tabela 3.5). Analisando os pares de vizinhos mais próximos, verificou-se que todos são vizinhos verdadeiros, ou seja V 2

< R

x

tol em todos os casos. Assim, é possível afirmar

i,xj

que o atributo F 4 não adiciona novas informações e que apenas m = 3 atributos são suficientes

para descrever o conjunto de dados.

Considerando o F 6 como o quarto atributo a ser analisado (Tabela 3.6), o mesmo resultado é obtido, ou seja, todos os pares de vizinhos mais próximos não apresentaram variação na

distância relativa.

Entretanto, se a ordem de análise dos atributos não for favorável, o FNN pode apresentar

resultados errôneos. Sabe-se que três atributos (F 1, F 2, F 3) foram a quantidade ótima a ser

considerada, porém se o segundo atributo a ser avaliado for o F 5, um atributo redundante, o

FNN apresenta um resultado errado.

A Tabela 3.7 apresenta as distâncias considerando os atributos F 1 e F 5. Avaliando os pares 37

Tabela 3.5: Distâncias – F1F2F3F4

A

B

C

D

E

F

G

H

A

0,00

0,97

5,30

6,91

5,76

4,09

8,01

7,95

B

0,97

0,00

4,49

6,10

4,83

3,61

7,53

7,50

C

5,30

4,49

0,00

2,14

3,45

3,99

5,40

5,52

D

6,91

6,10

2,14

0,00

3,60

4,27

4,18

4,32

E

5,76

4,83

3,45

3,60

0,00

4,13

6,55

6,56

F

4,09

3,61

3,99

4,27

4,13

0,00

4,31

4,17

G

8,01

7,53

5,40

4,18

6,55

4,31

0,00

0,66

H

7,95

7,50

5,52

4,32

6,56

4,17

0,66

0,00

Tabela 3.6: Distâncias – F1F2F3F6

A

B

C

D

E

F

G

H

A

0,00

0,61

4,67

6,22

4,37

4,02

7,91

7,91

B

0,61

0,00

4,13

5,67

3,79

3,61

7,52

7,50

C

4,67

4,13

0,00

2,08

3,21

3,59

5,25

5,23

D

6,22

5,67

2,08

0,00

3,52

3,63

3,79

3,68

E

4,37

3,79

3,21

3,52

0,00

2,84

6,05

5,84

F

4,02

3,61

3,59

3,63

2,84

0,00

4,28

4,17

G

7,91

7,52

5,25

3,79

6,05

4,28

0,00

0,43

H

7,91

7,50

5,23

3,68

5,84

4,17

0,43

0,00

de vizinhos, tem-se que V 1

< R

x

tol para todos os pares de exemplos. Ou seja, por essa análise,

i,xj

apenas F 1 é suficiente para descrever o conjunto de dados, o que não é verdade. De maneira

similar, considerando F 6 como o segundo atributo a ser avaliado (distâncias na Tabela 3.8),

chega-se à mesma conclusão.

Portanto, se não dispusermos de informações sobre os atributos, é necessário avaliar todas as

possíveis permutações do conjunto para que se possa chegar a um resultado válido. No entanto,

essa análise tem um alto custo pois apresenta um comportamento exponencial.

Tabela 3.7: Distâncias – F1F5

A

B

C

D

E

F

G

H

A

0,00

0,71

1,80

7,07

7,78