7 Diskusjon
7.4 Hvilke kriterier ligger til grunne for legitimeringen av matematikken?
Este capítulo apresenta três métodos determinísticos para gerar o conjunto de centros iniciais dos grupos no FCM e que podem ser aplicados em suas variantes. A utilização de tais métodos pelo algoritmo FCM ou variantes na etapa de inicialização dão origem a novas versões destes algoritmos.
4.1
Método I
A ideia deste método é utilizar a posição ocupada no espaço de atributos por cada atributo do conjunto de dados para obter uma estimativa do grupo ao qual um deter- minado dado deve pertencer. Para cada grupo estimado calcula-se o ponto médio. Este ponto será o centro inicial do grupo.
Passo 1: Dado um conjunto de dados X = {x1, x2, ..., xn} e o número de grupos k (cor-
responde ao mesmo k que representa o número de grupos passado como parâmetro para o algoritmo FCM) no qual deseja-se dividir X, onde xi = [xi1, xi2, ..., xis] ∈ Rs
é um vetor de atributos e aj, j = 1, ..., s, representa o j-ésimo atributo de X, tal que
aj = [x1j, x2j, ..., xnj]. Crie uma matriz de estimativa En×s vazia. Defina j = 1, onde
j é um contador para o número de atributos de xi;
Passo 2: Para o atributo aj na matriz de dados X, encontre o valor mínimo aminj e máximo
amax
j do atributo aj;
Passo 3: Divida o espaço formado a partir de amin
j até amaxj em k regiões, de forma
que cada região tenha tamanho (amax
j - aminj )/k, onde cada região k representa
um grupo;
Passo 4: Atribua na posição i, j da matriz E, i = 1, ..., n, o número da região k na qual cada valor do atributo aj está localizado;
Passo 5: Se j < s, incremente j em 1 e vá para o passo 2; Passo 6: Defina C = {C1, ..., Ck}, onde Cj, j = 1, ..., k, é um grupo;
Passo 7: Percorra cada linha i da matriz E, verifique o número da região k mais recorrente e atribua o elemento xi ∈ X ao grupo Ck. Se houver empate entre o número de
ocorrências de k, atribua o elemento xi ao grupo Ck com menor quantidade de
elementos;
Passo 8: Para cada grupo Cj, j = 1, ..., k, calcule a média de seus elementos para obter
os centros correspondentes.
Um problema deste método é o fato de ser sensível a outliers nos dados, ou seja, objetos isolados dos demais objetos do conjunto de dados. Quando existe outlier nos dados, o método I pode gerar um centro muito distante dos objetos do conjunto de dados e consequentemente nenhum objeto será atribuído ao grupo que possui este centro. Assim, este método de inicialização não é recomendado para bases de dados com outliers, é possível utilizá-lo se os outliers forem eliminados usando técnicas de pré-processamento no conjunto de dados.
4.1.1
Exemplo
Dado o seguinte conjunto de dados X contendo 6 objetos, descritos por 4 atributos, o qual deseja-se dividir em 2 grupos:
Tabela 6: Conjunto de dados X x1 5.1 3.5 1.4 0.2 x2 4.9 3.0 1.4 0.2 x3 4.7 3.2 1.3 0.2 x4 6.5 3.0 5.2 2.0 x5 6.2 3.4 5.4 2.3 x6 5.9 3.0 5.1 1.8
Passo 1: É criada uma matriz E6×4 vazia:
Passo 2: Para o atributo a1, isto é, a coluna 1 da matriz de dados X. Procura-se o
mínimo amin
1 e o máximo amax1 . Obtendo os valores amin1 = x31 = 4.7 e o valor de amax1 =
Passo 3: O espaço do atributo a1, ou seja, o vetor [5.1, 4.9, 4.7, 6.5, 6.2, 5.9] é dividido
em uma quantidade de regiões igual ao número de grupos, ou seja, k = 2 regiões, onde cada região tem tamanho 0.9 = (6.5 − 4.7)/2, como mostra a Figura 9:
Figura 9: Espaço do atributo a1 dividido em 2 regiões.
Passo 4: Para cada valor do atributo a1, é verificada em qual região k = 1 ou k = 2
este valor está localizado e o número da região é atribuído à posição i1 da matriz E. Ao final deste passo, a coluna 1 da matriz E conterá os valores mostrados na Tabela 7:
Tabela 7: Matriz E 1 1 1 2 2 2
Passo 5: Como o contador j = 1 é menor que o número de atributos s = 4, isto é, j < s é verdadeiro, então j é incrementado em 1. E retorna-se ao passo 2.
Agora o espaço amostral do atributo a2, ou seja, a coluna 2 da matriz de dados X é
dividido em 2 regiões, onde cada região tem tamanho 0.2 = (3.5 − 3.0)/2:
Figura 10: Espaço do atributo a2 dividido em 2 regiões.
Em seguida para cada valor de a2, é verificado a qual região o valor pertence e este
valor é atribuído à matriz E na linha i e coluna 2. Ao final deste passo, a matriz E vai conter os valores:
Tabela 8: Matriz E 1 2 1 1 1 1 2 1 2 2 2 1
O processo é repetido até a matriz E ser completamente preenchida. A matriz E final é mostrada abaixo: Tabela 9: Matriz E 1 2 1 1 1 1 1 1 1 1 1 1 2 1 2 2 2 2 2 2 2 1 2 2 Passo 6: Defina C = {C1, C2}.
Passo 7: Para cada linha i da matriz E, i = 1, ..., 6, é verificado o número da região mais recorrente, k = 1 ou k = 2 e o elemento xi, i = 1, ..., 6, é atribuído ao grupo C1
ou C2. Ao final do processo, têm-se os elementos de X agrupados em 2 grupos, como
mostram as Tabelas 10 e 11: Tabela 10: Grupo C1 x1 5.1 3.5 1.4 0.2 x2 4.9 3.0 1.4 0.2 x3 4.7 3.2 1.3 0.2 Tabela 11: Grupo C2 x4 6.5 3.0 5.2 2.0 x5 6.2 3.4 5.4 2.3 x6 5.9 3.0 5.1 1.8
Passo 8: Agora para encontrar os centros dos grupos C1 e C2 basta calcular a média
de seus elementos. Então têm-se os centros c1 e c2 com os valores mostrados na Tabela
12.
Tabela 12: Centros iniciais c1 4.9 3.2 1.4 0.2
c2 6.2 3.1 5.2 2.0
4.2
Método II
A ideia deste método II é utilizar a média dos valores de cada atributo do conjunto de dados para obter uma aproximação dos centros iniciais dos grupos. Tendo obtido esta aproximação, o próximo passo consiste em calcular a distância entre cada objeto do conjunto de dados e os centros iniciais aproximados. Cada objeto é atribuído ao grupo com centro aproximado mais próximo. Finalmente, os centros inciais são calculados utilizando a média dos objetos de cada grupo.
Passo 1: Dado um conjunto de dados X = {x1, x2, ..., xn} e o número de grupos k (cor-
responde ao mesmo k que representa o número de grupos passado como parâmetro para o algoritmo FCM) no qual deseja-se dividir X, onde xi = [xi1, xi2, ..., xis] ∈ Rs
é um vetor de atributos e aj, j = 1, ..., s representa o j-ésimo atributo de X, tal que
aj = [x1j, x2j, ..., xnj]. Crie uma matriz vazia de centros iniciais CI com k linhas e s
colunas. Defina j = 1, onde j é um contador para o número de atributos s de xi;
Passo 2: Para o atributo aj na matriz de dados X, encontre o valor mínimo aminj e máximo
amax
j do atributo aj;
Passo 2.1: Divida o espaço formado a partir de amin
j até amaxj em k regiões, de
forma que cada região tenha tamanho (amax
j - aminj )/k, onde cada região rl,
com l = 1, ..., k, representa um grupo.
Passo 2.2: Para cada uma das regiões rl encontre o ponto médio e o defina como o
atributo da matriz de centros CIlj;
Passo 3: Se j < s, incremente j em 1 e volte ao Passo 2;
Passo 4: Defina C = {C1, ..., Ck} e tome cl ∈ CI como centro do grupo Cl, l = 1, ..., k.
dos grupos em C (utilizando a distância Euclidiana) e adicione o objeto xi ao grupo
mais próximo;
Passo 5: Para cada grupo Cl, onde l = 1, ..., k, calcule a média de seus elementos para
obter os centros correspondentes.
4.2.1
Exemplo
Dado o seguinte conjunto de dados X, com n = 6, s = 4 e k = 2: Tabela 13: Conjunto de dados X
x1 5.1 3.5 1.4 0.2 x2 4.9 3.0 1.4 0.2 x3 4.7 3.2 1.3 0.2 x4 6.5 3.0 5.2 2.0 x5 6.2 3.4 5.4 2.3 x6 5.9 3.0 5.1 1.8
Passo 1: Define-se uma matriz vazia de centros CI2×4;
Tabela 14: Matriz de centros CI CI1
CI2
Passo 2: Para o atributo a1, encontra-se o amin1 = 4.7 e o amax1 = 6.5;
Passo 2.1: Para este exemplo o primeiro atributo de X é a1 = (5.1, 4.9, 4.7, 6.5, 6.2, 5.9).
O espaço de a1 é dividido em k = 2 regiões, onde cada região tem tamanho 0.9 =
(6.5 − 4.7)/2, como mostra a Figura 11:
Figura 11: Espaço do atributo a1 dividido em 2 regiões.
Passo 2.2: Calcula-se o ponto médio de cada região, obtendo para a região 1 o valor 5.15 e para a região 2 o valor 6.05 que são colocados na matriz CI atribuindo CI11= 5.15
Tabela 15: Matriz de centros CI CI1 5.15
CI2 6.05
Passo 3: Como j = 1 < s = 4, incrementa-se j em 1 e retorna-se ao Passo 2;
Agora o espaço amostral do atributo a2 é dividido em k = 2 regiões, onde cada região
tem tamanho 0.2 = (3.5 − 3.0)/2, como mostra a Figura 12:
Figura 12: Espaço do atributo a2 dividido em 2 regiões.
Calcula-se o ponto médio de cada região e é feita a atribuição CI21= 3.125 e CI22=
3.375 como mostra a Tabela 16:
Tabela 16: Matriz de centros CI CI1 5.15 3.125
CI2 6.05 3.375
Este processo é repetido para todos os atributos, como mostra a Figura 13, até a matriz de centros CI ser totalmente preenchida. O resultado é mostrado na Tabela 17.
Tabela 17: Matriz de centros CI CI1 5.15 3.125 2.325 0.725
CI2 6.05 3.375 4.375 1.775
Passo 4: Define-se C = {C1, C2} e toma-se o valor CI1 = (5.15, 3.125, 2.325, 0.725)
como centro do grupo C1 e CI2 = (6.05, 3.375, 4.375, 1.775) como centro do grupo C2.
Para cada objeto do conjunto de dados X = {x1, x2, ..., x6} , calcula-se sua distância aos
centros dos grupos C1 e C2 (utilizando a distância Euclidiana), tendo como resultado os
valores mostrados na Tabela 18. Em seguida os objetos {x1, x2, ..., x6} são atribuídos ao
grupo mais próximo, obtendo os grupos mostrados na Tabela 19: Tabela 18: Matriz das distâncias entre X e CI
CI1 d(x1; CI1) 1.128882 d(x2; CI1) 1.099716 d(x3; CI1) 1.238699 d(x4; CI1) 3.424818 d(x5; CI1) 3.621378 d(x6; CI1) 3.071543 CI2 d(x1; CI2) 3.499911 d(x2; CI2) 3.576923 d(x3; CI2) 3.713405 d(x4; CI2) 1.036521 d(x5; CI2) 1.161626 d(x6; CI2) 0.830286 Tabela 19: Grupos C1 e C2 x1 5.1 3.5 1.4 0.2 x2 4.9 3.0 1.4 0.2 x3 4.7 3.2 1.3 0.2 x4 6.5 3.0 5.2 2.0 x5 6.2 3.4 5.4 2.3 x6 5.9 3.0 5.1 1.8
Passo 5: Calcule-se a média dos elementos do grupo Cl e C2, obtendo os centros cl e
c2, mostrados na Tabela 20 que são os centros iniciais.
Tabela 20: Matriz de centros finais c1 4.90 3.2 1.37 0.20
4.3
Método III
Para obter o conjunto de centros iniciais esta proposta consiste em primeiro lugar calcular a distância entre cada objeto e o ponto médio do conjunto de dados. Em seguida, os objetos originais são ordenados de acordo com tais distâncias e particionados em k conjuntos iguais, onde k representa o número de grupos passado como parâmetro ao algoritmo FCM. Em cada conjunto, os pontos médios são tomados como centros iniciais (ARNALDO; BEDREGAL, 2013, 2014).
Este método de inicialização dos centros é descrito nos seguintes passos: Passo 1 : Calcule a média x do conjunto de dados X = {x1, x2, ..., xn};
Passo 2 : Para cada objeto de X, calcule a distância entre xi e o ponto médio x;
Passo 3 : Ordene os objetos de X de acordo com as distâncias ao ponto x;
Passo 4 : Particione os objetos ordenados em k conjuntos iguais, X = {X1, ..., Xk}, no
número de elementos;
Passo 5 : Em cada conjunto Xi, tome o ponto médio como o centro inicial.
4.3.1
Exemplo
Dado o número de grupos k = 2 e o seguinte conjunto de dados X: Tabela 21: Conjunto de dados X
x1 5.1 3.5 1.4 0.2 x2 4.9 3.0 1.4 0.2 x3 4.7 3.2 1.3 0.2 x4 6.5 3.0 5.2 2.0 x5 6.2 3.4 5.4 2.3 x6 5.9 3.0 5.1 1.8
Passo 1: Calcula-se a média x do conjunto de dados X que é mostrada na Tabela 22: Tabela 22: Média x
Passo 2: Calcula-se as distâncias entre os objetos x1, x2, x3, x4, x5, x6 e o ponto médio
x = (5.6, 3.2, 3.3, 1.1). O resultado é mostrado na Tabela 23 : Tabela 23: Matriz de distâncias
d(x1; x) 2.1802 d(x2; x) 2.2150 d(x3; x) 2.3586 d(x4; x) 2.3079 d(x5; x) 2.5059 d(x6; x) 1.9655
Passo 3: Ordena-se os objetos x1, x2, x3, x4, x5 e x6 em ordem crescente de acordo com
suas distância ao ponto médio x = (5.6, 3.2, 3.3, 1.1). O resultado é apresentado na Tabela 24:
Tabela 24: Conjunto de dados X ordenado d(x6; x) 1.9655 d(x1; x) 2.1802 d(x2; x) 2.2150 d(x4; x) 2.3079 d(x3; x) 2.3586 d(x5; x) 2.5059 x6 5.9 3.0 5.1 1.8 x1 5.1 3.5 1.4 0.2 x2 4.9 3.0 1.4 0.2 x4 6.5 3.0 5.2 2.0 x3 4.7 3.2 1.3 0.2 x5 6.2 3.4 5.4 2.3
Passo 4: Particiona-se o conjunto de dados ordenado em 2 conjuntos, resultando nos conjuntos X1 e X2 mostrados na Tabela 25:
Tabela 25: Conjuntos de dados X1 e X2
x6 5.9 3.0 5.1 1.8 x1 5.1 3.5 1.4 0.2 x2 4.9 3.0 1.4 0.2 x4 6.5 3.0 5.2 2.0 x3 4.7 3.2 1.3 0.2 x5 6.2 3.4 5.4 2.3
Passo 5: Para X1 e X2 o ponto médio é tomado como centro de cada grupo, obtendo
os centros c1 e c2:
Tabela 26: Centros c1 e c2
4.4
Considerações Finais
A inicialização do FCM pode ser feita de duas formas: inicializando a matriz de pertinência com valores aleatórios no intervalo [0, 1] ou inicializando os centros iniciais dos grupos com valores aleatórios no intervalo do conjunto de dados. Em razão do FCM ser um procedimento estocástico, é necessário realizar várias execuções do algoritmo para se ter bons agrupamentos. Neste capítulo foram propostos três métodos determinísticos para gerar os centros iniciais dos grupos no FCM, eliminando a aleatoriedade na etapa de inicialização e consequentemente eliminando a necessidade de executar o FCM várias vezes. Estes métodos também podem ser aplicados em variantes do FCM. Os passos dos três métodos propostos foram descritos em detalhes utilizando exemplos de execução.
A ideia do método I é utilizar a distribuição espacial de cada atributo do conjunto de dados para obter uma estimativa do grupo ao qual um determinado dado deve pertencer. Para cada grupo estimado calcula-se o ponto médio. Este ponto será o centro inicial do grupo. A ideia do método II é utilizar a média dos valores de cada atributo do conjunto de dados para obter uma aproximação dos centros iniciais dos grupos. Tendo obtido essa aproximação, o próximo passo consiste em calcular a distância entre cada objeto do conjunto de dados e os centros iniciais aproximados. Cada objeto é atribuído ao grupo com centro aproximado mais próximo. Finalmente, os centros inciais são calculados utilizando a média dos objetos de cada grupo.
No método III para obter o conjunto de centros iniciais em primeiro lugar deve- se calcular a distância entre cada objeto e o ponto médio do conjunto de dados. Em seguida, os objetos originais são ordenados de acordo com tais distâncias e particionados em k conjuntos iguais, onde k representa o número de grupos no agrupamento. Em cada conjunto, os pontos médios são tomados como centros iniciais (ARNALDO; BEDREGAL, 2013).
No capítulo 5 serão descritos os experimentos realizados para testar a eficiência dos métodos propostos na identificação de grupos em bases de dados reais e artificiais. Essas bases serão descritas em detalhes.