Universidade de Campinas (UNICAMP)
MO443/MC920
Introdução ao
Processamento de Imagem Digital
Clustering de pixels por Kmeans
Classificação de pixels por Knn
Alexandre Xavier Falcão & David Menotti
Objetivos
• Introduzir diferentes tipos de aprendizagem
– Não Supervisionada (Kmeans)
– Supervisionada (Knn)
• não paramétricos.
• Relacionar as técnicas com pixels
Aprendizagem Não-Supervisionada
• O que pode ser feito quando se tem um
conjunto de exemplos mas não se conhece as
categorias envolvidas?
Como ‘‘classificar’’ esses pontos?
Por que estudar esse tipo de problema?
Aprendizagem Não-Supervisionada
• Primeiramente, coletar e rotular bases de
dados pode ser extremamente caro.
– Gravar voz é barato, mas rotular todo o material
gravado é caro.
– Rotular TODA uma grande base de imagens é
muito caro, mas... alguns elementos de cada
classe não
• Segundo, muitas vezes não se tem
conhecimento das classes envolvidas.
– Trabalho exploratório nos dados
(ex. Data Mining.)
Aprendizagem Não-Supervisionada
• Pré-classificação:
– Suponha que as categorias envolvidas são
conhecidas, mas a base não está rotulada.
– Pode-se utilizar a aprendizagem nãosupervisionada para fazer uma pré-classificação, e
então treinar um classificador de maneira
supervisionada (tópico de pesquisa)
Clustering
• É a organização dos objetos similares (em
algum aspecto) em grupos.
Quatro grupos (clusters)
Cluster
• Uma coleção de objetos que são similares
entre si, e diferentes dos objetos pertencentes
a outros clusters.
• Isso requer uma medida de similaridade.
• No exemplo anterior, a similaridade utilizada
foi a distância.
– Distance-based Clustering
k-Means Clustering
• É a técnica mais simples de aprendizagem não
supervisionada.
• Consiste em fixar k centróides (de maneira aleatória),
um para cada grupo (clusters).
• Associar cada indivíduo ao seu centróide mais
próximo.
• Recalcular os centróides com base nos indivíduos
classificados.
Algoritmo k-Means
1. Determinar os centróides
2. Atribuir a cada objeto do grupo o centróide
mais próximo.
3. Após atribuir um centróide a cada objeto,
recalcular os centróides.
4. Repetir os passos 2 e 3 até que os centróides
não sejam modificados.
k-Means – Um Exemplo
Objetos em um plano 2D
k-Means – Um Exemplo
Passo 1:Centróides inseridos aleatoriamente
k-Means – Um Exemplo
Passo 2: Atribuir a cada objeto o centróide mais próximo
k-Means – Um Exemplo
Passo 3: Recalcular os centróides
k-Means – Um Exemplo
Impacto da inicialização aleatória.
k-Means – Um Exemplo
Fronteira
Diferente
Impacto da inicialização aleatória
k-Means – Inicialização
• Importância da inicialização.
• Quando se têm noção dos centróides, pode-se
melhorar a convergência do algoritmo.
• Execução do algoritmo várias vezes, permite
reduzir impacto da inicialização aleatória.
k-Means – Um Exemplo
4 Centróides
Calculando Distâncias
• Distância Euclidiana
d
n
 x  y 
i 1
y
2
i
i
x
• Manhattan (City Block)
y
n
d   xi  yi
i 1
x
Calculando Distâncias
• Minkowski
– Parâmetro r
• r = 2, distância Euclidiana
• r = 1, City Block

r
d    xi  yi  
 i 1

n
1
r
Calculando Distâncias
• Mahalanobis
– Leva em consideração as variações estatísticas dos
pontos. Por exemplo se x e y são dois pontos da
mesma distribuição, com matriz de covariância C,
a distância é dada pela equação
d  ( x  y)´C
1
( x  y)

1
2
– Se a matriz C for uma matriz identidade, essa
distância é igual a distância Euclidiana.
Critérios de Otimização
• Até agora discutimos somente como medir a
similaridade.
• Um outros aspecto importante em clustering é o
critério a ser otimizado.
• Considere um conjunto D  x1 ,..., xn  composto de
n exemplos, e que deve ser dividido em c subconjuntos disjuntos D1 ,...,Dc .
• Cada sub-conjunto representa um cluster.
Critérios de Otimização
• O problema consiste em encontrar os clusters
que minimizam/maximizam um dado critério.
• Alguns critérios de otimização:
– Soma dos Erros Quadrados.
– Critérios de Dispersão
Soma dos Erros Quadrados
• É o mais simples e usado critério de
otimização em clustering.
• Seja ni o número de exemplos no cluster Di e
seja mi a média desse exemplos
1
mi 
ni
x
xDi
• A soma dos erros quadrados é definida
c
J e    x  mi
i 1 xDi
2
Soma dos Erros Quadrados
Je = pequeno
Je = grande
Je = pequeno
Adequado nesses casos
- Separação natural
Não é muito adequado para dados
mais dispersos.
Outliers podem afetar bastante os
vetores médios m
Critérios de Dispersão
• Vetor médio do cluster i
1
mi 
ni
x
xDi
• Vetor médio total
1
m  x
n D
• Dispersão do cluster i
Si 
• Within-cluster
• Between-cluster
t
(
x

m
)(
x

m
)

i
i
xDi
c
S w   Si
i 1
c
S B   ni (mi  m)(mi  m)t
i 1
Critérios de Dispersão
• Relação Within-Between
Caso ideal
Alto between (Sb)
Clusters distantes
um do outro.
Baixo within (Sw)
(boa compactação)
Critérios de Dispersão
Caso não ideal
Baixo between (Sb)
Baixa distância entre
os clusters.
Clusters dispersos
Alto within
Critérios de Dispersão
• Podemos entender melhor os critérios de dispersão
analisando o seguinte exemplo:
Diferentes clusters para c=2 usando
diferentes critérios de otimização
Erro Quadrado
Sw
Relação Sw/Sb
Normalização
• Evitar que uma característica se sobressaia a
outras.
– V1 = {200, 0.5, 0.002}
– V2 = {220, 0.9, 0.050}
• Se calcularmos a distância Euclidiana, veremos
que a primeira característica dominará o
resultado.
32
Normalização
• Diferentes técnicas de normalização
Min-Max
ni 
xi  min(x)
max(x)  min(x)
Tanh

xi  m ean( x)  
1
  1
ni   tanh 001
2
std ( x)  

Z-Score
ni 
xi  m ean( x)
std ( x)
Soma
ni 
xi
x
33
Normalização
• Considere as seguintes características
– Qual delas discrimina os pontos verdes x azuis?
Aprendizagem Supervisionada
• Alguém (um professor) fornece a identificação
(rótulos) de cada objeto da base de dados.
– Métodos Paramétricos: Assumem que a
distribuição dos dados é conhecida
(distribuição normal por exemplo)
– Métodos Não-Paramétricos: Não consideram essa
hipótese.
Aprendizagem Supervisionada
• Em muitos casos não se tem conhecimento da
distribuição dos dados.
• Consequentemente, utilizar um método
paramétrico pode não ser adequado.
Distribuição Normal
Aprendizagem Supervisionada
• Um algoritmo não-paramétrico para
aprendizagem supervisionada é o k-NN (k
Nearest Neighbor).
• Consiste em atribuir a um exemplo de teste x
a classe do seu vizinho mais próximo.
k-NN
• Significado de k:
– Classificar x atribuindo a ele o rótulo representado
mais frequentemente dentre as k amostras mais
próximas.
– Contagem de votos.
• Uma medida de proximidade bastante
utilizada é a distância Euclidiana:
d ( x, y ) 
n
 x  y 
i 1
2
i
i
k-NN: Um Exemplo
A qual classe pertence
este ponto?
Azul ou vermelho?
Calcule para os seguintes
valores de k:
k=1 não se pode afirmar
k=3 vermelho – 5,2 - 5,3
k=5 vermelho – 5,2 - 5,3 - 6,2
4
k=7 azul – 3,2 - 2,3 - 2,2 - 2,1
3
2
1
1
2
3 4 5 6 7 8
A classificação pode mudar de acordo
com a escolha de k.
kNN: Funciona bem?
• Certamente o kNN é uma regra simples e intuitiva.
• Considerando que temos um número ilimitado de
exemplos
– O melhor que podemos obter é o erro Bayesiano (E*)
– Para n tendendo ao infinito, pode-se demonstrar que o
erro do kNN é menor que 2E*
• Ou seja, se tivermos bastante exemplos, o kNN vai
funcionar bem.
kNN: Distribuições Multi-Modais
• Um caso complexo de
classificação no qual o
kNN tem sucesso.
kNN: Como escolher k
• Não é um problema trivial.
– k deve ser grande para minimizar o erro.
• k muito pequeno leva a fronteiras ruidosas.
– k deve ser pequeno para que somente exemplos
próximos sejam incluídos.
• Encontrar o balanço não é uma coisa trivial.
– Base de validação
kNN: Como escolher k
• Para k = 1,...,7 o ponto x é corretamente classificado
(vermelho.)
• Para k > 7, a classificação passa para a classe azul
(erro)
kNN: Complexidade
• O algoritmo básico do kNN armazena todos os
exemplos. Suponha que tenhamos n exemplos
– O(n) é a complexidade para encontrar o vizinho
mais próximo.
– O(nk) complexidade para encontrar k exemplos
mais próximos
• Considerando que precisamos de um n grande
para o kNN funcionar bem, a complexidade
torna-se problema.
kNN: Reduzindo complexidade
• Se uma célula dentro do diagrama de Voronoi possui os
mesmos vizinhos, ela pode ser removida.
Mantemos a mesma fronteira e diminuímos a quantidade de exemplos
kNN: Reduzindo complexidade
• kNN protótipos
– Consiste em construir protótipos para representar
a base
– Diminui a complexidade, mas não garante as
mesmas fronteiras