MO443/MC920 Introdução ao Processamento de Imagem Digital Clustering de pixels por Kmeans...

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

Universidade de Campinas (UNICAMP)

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ão-

supervisionada 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óides2. 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

Impacto da inicialização aleatória

FronteiraDiferente

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

• Manhattan (City Block)

n

iii yxd

1

n

iii yxd

1

2

x

y

x

y

Calculando Distâncias

• Minkowski – Parâmetro r• r = 2, distância Euclidiana• r = 1, City Block

rn

i

rii yxd

1

1

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

– Se a matriz C for uma matriz identidade, essa distância é igual a distância Euclidiana.

211 )()´( yxCyxd

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 composto de n exemplos, e que deve ser dividido em c sub-conjuntos disjuntos .

• Cada sub-conjunto representa um cluster.

nxxD ,...,1

cDD ,...,1

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

• A soma dos erros quadrados é definida

iDxi

i xn

m1

c

i Dxie

i

mxJ1

2

Soma dos Erros Quadrados

Adequado nesses casos- Separação natural

Não é muito adequado para dadosmais dispersos.Outliers podem afetar bastante os vetores médios m

Je = grande

Je = pequeno

Je = pequeno

Critérios de Dispersão• Vetor médio do cluster i

• Vetor médio total

• Dispersão do cluster i

• Within-cluster

• Between-cluster

iDxi

i xn

m1

D

xn

1m

iDx

tiii mxmxS ))((

c

iiw SS

1

c

i

tiiiB mmnS

1

)m)(m(

Critérios de Dispersão

• Relação Within-Between

Caso ideal

Baixo within (Sw)(boa compactação)

Alto between (Sb)Clusters distantesum do outro.

Critérios de Dispersão

Clusters dispersosAlto within

Baixo between (Sb)Baixa distância entreos clusters.

Caso não ideal

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 Z-Score

)min()max(

)min(

xx

xxn ii

)(

)(

xstd

xmeanxn ii

Tanh

1

)(

)(001tanh

2

1

xstd

xmeanxn ii

x

xn ii

Soma

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:

n

iii yxyxd

1

2),(

k-NN: Um Exemplo

1 2 3 4 5 6 7 8

1

2

3

4

A qual classe pertenceeste ponto?Azul ou vermelho?

não se pode afirmar

vermelho – 5,2 - 5,3

vermelho – 5,2 - 5,3 - 6,2

azul – 3,2 - 2,3 - 2,2 - 2,1k=7

k=5

k=1

k=3

Calcule para os seguintes valores de k:

A classificação pode mudar de acordocom 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