Implementação do método de classificação contínua
fuzzy k-médias no ambiente TerraLib
Isabela Neves Drummond
Estrutura da apresentação



Introdução
Fuzzy x Geoprocessamento
Classificação (Agrupamento)






k-médias
fuzzy k-médias
Implementação: Tefcm
Testes
Resultados
Conclusão
Introdução





Motivação
Objetivo: implementação do método de
classificação fuzzy k-médias
Linguagem: C++
Ambiente: TerraLib
Visualização: TerraView
Fuzzy x Geoprocessamento

Teoria dos conjuntos fuzzy


Caracterizado por uma função de pertinência
A(x)  [0, 1]
Sistemas de Informação Geográfica (SIG) – aplicação

exemplo
Classificação

SIG – subsistemas





coleta, entrada e verificação de dados
armazenamento e gerenciamento
processamento e visualização dos resultados
Processo de classificação: definição de classe com
vistas à redução de variedade, ordenando e
simplificando
Métodos:


supervisionados
não-supervisionados
Classificação: k-médias
1. Determinar posições iniciais dos k centros
2. Para cada elemento, colocá-lo no cluster do centróide
mais próximo
3. Recalcular os centros a partir dos elementos
alocados
4. Repetir passos 2 e 3 segundo algum critério de
convergência
Classificação: fuzzy k-médias
1. Determinar posições iniciais dos k centros e o valor m
do coeficiente fuzzy
2. Associar cada elemento aos clusters através de uma
função de pertinência (função de distância). Assim,
cada elemento irá possuir um grau de pertinência
com relação a cada cluster
3. Recalcular os centros com base nos valores de
pertinência
4. Atualizar os graus de pertinência
5. Repetir passos 2 a 4 segundo algum critério de
convergência
k-médias x fuzzy k-médias
X  { x1, x 2 ,..., x n }
n

(U ik ) m  x k
v i  k 1
n
(U ik )
k 1

m
U ik ( x )  [0,1], i  1,...,c
U ik 
1
c

j 1
d
( ik ) 2 /(m 1)
d jk
k-médias x fuzzy k-médias
m 1
Implementação: ambiente


Linguagem C++ / Compilador Microsoft Visual C++ 6.0
TerraLib: biblioteca de classes




Paradigmas:



Kernel
Functions
Contrib
Orientação a objeto
Programação genérica
Apresentação visual: TerraView
Implementação: Tefcm













template<typename It, typename C, typename M, typename T>
void
TeFcm
(It begin, It end, C& result, M& u, double conv, T&
maxIter, double expo)
...
Initialize(centroides[i], minValue, maxValue);
TeInitfcm(u);
...
while ((!converge) && (numIter < maxIter))
{
TeStepfcm(begin, end, expo, centroides, u);
converge = CheckConvergence(centroides, centr_aux, conv);
centr_aux = centroides;
++numIter;
}
U  [ ]k
x atrib
Implementação: Tefcm

TerraView

Interface: QT designer
Validação

Rotina que associa cada polígono a sua classe, ou
seja, os setores que se encontram na mesma classe
são preenchidos com a mesma cor

Testes empregando diferentes “shapes” e atributos

Análise numérica x análise temática
Resultados - Mapas obtidos

Fuzzy k-médias


3 classes
m=2

k-médias

3 classes
Resultados - Mapas obtidos

K-médias
Resultados - Mapas obtidos

Fuzzy k-médias - diferentes valores de m
m = 1.1
m = 1.5
m=2
m=3
Conclusões







O Tefcm deve ser n-dimensional
A interface pode ser refinada
Dificuldades encontradas: ambiente, linguagem C++ e
paradigmas empregados (programação genérica e
orientação a objetos)
Métodos de classificação: k-médias x fuzzy k-médias
Muito sensível aos centros iniciais
Valor de m é experimental
Aprendizado
Trabalhos futuros


O que fazer com a matriz U?
Como otimizar os centros iniciais: AG, redes neurais,
etc...