Inteligência Artificial - Data Mining

Seres Humanos e Padroes Conceito Intuitivo Formalizando Na Pratica Distancias Classificadores Elementares Contatos

Introducao ao Reconhecimento de Padroes(Aprendizagem de Maquina / Data Mining)

Exemplos em Python

Prof. Ronaldo F. Ramos, Dr

1 de junho de 2014


Introducao ao Reconhecimento de Padroes (Aprendizagem de Maquina / Data Mining)


Roteiro

1 Seres Humanos e Padroes

2 Conceito Intuitivo

3 Formalizando

4 Na Pratica

5 Distancias

6 Classificadores Elementares

7 Contatos




Seres Humanos e Padroes

Os sentidos humanos enviam informacoes ao cerebro quereconhece alguns aspectos da realidade.

Sons

Imagens

Sensacao Tatil

Odores

Permitem tambem a identificacao de padroes logico-matematicos(o que exige um pouco mais do cerebro ;-) ).




Conceito de Reconhecimento de Padroes

Reconhecer um padrao equivale a classificar um objeto fısico oulogico como pertencente ou nao a uma predeterminada categoria.




Conceito Intuitivo

Dadas as categorias abaixo:

(a) Laranjas (b) Macas

A qual delas pertencem os objetos abaixo?




Conceito Intuitivo - Novo Grupo

(c) Laranjas (d) Macas (e) Tangerinas

A qual delas pertence o objeto abaixo?




Similaridade

Seu cerebro fez uma analise de

similaridade.

Pode-se fazer esta mesma analise no

computador?O que precisaremos para tal?




Uma definicao quase formal de RP

Um problema de RP e composto de ...




Um Conjunto de K Classes




Um Conjunto de objetos Ni por Classes Ki




Um Conjunto de atributos nj por objeto Ni




Mecanismo de Memoria e Aprendizagem




Regra de Decisao para Calcular Novos Objetos




Criterios de Avaliacao do Classificador




Que atributos descrevem bem uma tangerina?

Formato

Esferico ou Oval? Esferico

Fruta Cıtrica

Sim/Nao Sim

Cor

Laranja????Alaranjado

Rugosidade da Casca

Lisa ou Rugosa?Rugosa

Cheiro

Ativo/Fraco? Ativo





Formato


Fruta Cıtrica

Sim/Nao Sim

Cor


Rugosidade da Casca


Cheiro

Ativo/Fraco? Ativo





Formato


Fruta Cıtrica

Sim/Nao Sim

Cor


Rugosidade da Casca


Cheiro

Ativo/Fraco? Ativo





Formato


Fruta Cıtrica

Sim/Nao Sim

Cor


Rugosidade da Casca


Cheiro

Ativo/Fraco? Ativo





Formato


Fruta Cıtrica

Sim/Nao Sim

Cor


Rugosidade da Casca


Cheiro

Ativo/Fraco? AtivoProf. Ronaldo F. Ramos, Dr



Sobre os Atributos

Os atributos sao igualmente importantes?

E facil definir os atributos de um objeto?




Sobre os Atributos

Nem sempre.

Nem sempre.




Transformacao de Atributos

Atributos devem ser expressos na forma de numeros.Desta forma o conjunto de atributos da tangerina [Formato, FrutaCıtrica, Cor, Rugosidade da Casca, Cheiro] devem ser expressoscomo um vetor de atributos tais como:X = [0, 1, 2, 1, 1] 1

1A forma de numeralizar pode fazer muita diferenca no uso do modeloProf. Ronaldo F. Ramos, Dr



Adotando as seguintes convencoes:

Atributo Valores Textuais Numericos

Formato Esferico,Oval,Alongado 0,1,2

Fruta Cıtrica Nao,Sim 0,1

Cor Amarelo,Vermelho,Alaranjado,Verde 0,1,2,3

Rugosidade lisa,rugosa 0,1

Cheiro Nao,Sim 0,1




Terıamos as seguintes representacoes para as frutas

Objeto Laranja (X) [0, 1, 2, 1, 0]

Objeto Maca (Y) [0, 0, 1, 0, 0]

Objeto Tangerina (Z)[0, 1, 2, 1, 1]

O Objeto tangerina (Z) se assemelha mais alaranja(X) ou a Maca(Y)?




Conceito de Distancia

Uma forma de medir a similaridade entre dois padroes ecalcular a distancia entre eles.

Distancia city-block, quarteirao ou manhattan.Dq(X,Y) = |X1 − Y1|+ |X2 − Y2|+ ... + |Xn − Yn|Distancia Euclidiana.De(X,Y) =

√(X1 − Y1)2 + (X2 − Y2)2 + ... + (Xn − Yn)2




Comparacao entre Euclidiana e Quarteirao

ZZZZZZ

ZZZZZZ

C B

A

53

4

Dq(A,B) = 3 + 4 = 7De(A,B) =

√32 + 42 = 5




Agora e so fazer as contas




Classificadores Elementares

Agora voce sabe que uma tangerina e mais parecida com umalaranja do que com uma maca..;-).




Classificadores Elementares

Agora vamos estudar as flores....




Morfologia das Flores




Iris (Flor-de-lis)

Valei-me Deus e o fim do nosso amor .....

Iris Setosa Iris Virgınica Iris Versicolor

Estudo feito por Sir Ronald Fischer em 1936(Analise Discriminante).




Base de Dados de Iris I

Na WIKIPEDIA e em outros lugares encontraremos a base dedados de Fischer.SL=Comprimento da Sepala SW=Largura da SepalaPL=Comprimento da Petala PW = Largura da Petala

SL SW PL PW Species5.1 3.5 1.4 0.2 setosa4.9 3.0 1.4 0.2 setosa4.7 3.2 1.3 0.2 setosa4.6 3.1 1.5 0.2 setosa5.0 3.6 1.4 0.2 setosa5.4 3.9 1.7 0.4 setosa4.6 3.4 1.4 0.3 setosa5.0 3.4 1.5 0.2 setosa




Base de Dados de Iris II

4.4 2.9 1.4 0.2 setosa4.9 3.1 1.5 0.1 setosa5.4 3.7 1.5 0.2 setosa4.8 3.4 1.6 0.2 setosa4.8 3.0 1.4 0.1 setosa4.3 3.0 1.1 0.1 setosa5.8 4.0 1.2 0.2 setosa5.7 4.4 1.5 0.4 setosa5.4 3.9 1.3 0.4 setosa5.1 3.5 1.4 0.3 setosa5.7 3.8 1.7 0.3 setosa5.1 3.8 1.5 0.3 setosa5.4 3.4 1.7 0.2 setosa




Base de Dados de Iris III





Base de Dados de Iris IV





Base de Dados de Iris V

4.6 3.2 1.4 0.2 setosa5.3 3.7 1.5 0.2 setosa5.0 3.3 1.4 0.2 setosa7.0 3.2 4.7 1.4 versicolor6.4 3.2 4.5 1.5 versicolor6.9 3.1 4.9 1.5 versicolor5.5 2.3 4.0 1.3 versicolor6.5 2.8 4.6 1.5 versicolor5.7 2.8 4.5 1.3 versicolor6.3 3.3 4.7 1.6 versicolor4.9 2.4 3.3 1.0 versicolor6.6 2.9 4.6 1.3 versicolor5.2 2.7 3.9 1.4 versicolor




Base de Dados de Iris VI

5.0 2.0 3.5 1.0 versicolor5.9 3.0 4.2 1.5 versicolor6.0 2.2 4.0 1.0 versicolor6.1 2.9 4.7 1.4 versicolor5.6 2.9 3.6 1.3 versicolor6.7 3.1 4.4 1.4 versicolor5.6 3.0 4.5 1.5 versicolor5.8 2.7 4.1 1.0 versicolor6.2 2.2 4.5 1.5 versicolor5.6 2.5 3.9 1.1 versicolor5.9 3.2 4.8 1.8 versicolor6.1 2.8 4.0 1.3 versicolor6.3 2.5 4.9 1.5 versicolor




Base de Dados de Iris VII





Base de Dados de Iris VIII





Base de Dados de Iris IX

5.7 2.8 4.1 1.3 versicolor6.3 3.3 6.0 2.5 virginica5.8 2.7 5.1 1.9 virginica7.1 3.0 5.9 2.1 virginica6.3 2.9 5.6 1.8 virginica6.5 3.0 5.8 2.2 virginica7.6 3.0 6.6 2.1 virginica4.9 2.5 4.5 1.7 virginica7.3 2.9 6.3 1.8 virginica6.7 2.5 5.8 1.8 virginica7.2 3.6 6.1 2.5 virginica6.5 3.2 5.1 2.0 virginica6.4 2.7 5.3 1.9 virginica




Base de Dados de Iris X

6.8 3.0 5.5 2.1 virginica5.7 2.5 5.0 2.0 virginica5.8 2.8 5.1 2.4 virginica6.4 3.2 5.3 2.3 virginica6.5 3.0 5.5 1.8 virginica7.7 3.8 6.7 2.2 virginica7.7 2.6 6.9 2.3 virginica6.0 2.2 5.0 1.5 virginica6.9 3.2 5.7 2.3 virginica5.6 2.8 4.9 2.0 virginica7.7 2.8 6.7 2.0 virginica6.3 2.7 4.9 1.8 virginica6.7 3.3 5.7 2.1 virginica




Base de Dados de Iris XI

7.2 3.2 6.0 1.8 virginica6.2 2.8 4.8 1.8 virginica6.1 3.0 4.9 1.8 virginica6.4 2.8 5.6 2.1 virginica7.2 3.0 5.8 1.6 virginica7.4 2.8 6.1 1.9 virginica7.9 3.8 6.4 2.0 virginica6.4 2.8 5.6 2.2 virginica6.3 2.8 5.1 1.5 virginica6.1 2.6 5.6 1.4 virginica7.7 3.0 6.1 2.3 virginica6.3 3.4 5.6 2.4 virginica6.4 3.1 5.5 1.8 virginica




Base de Dados de Iris XII

6.0 3.0 4.8 1.8 virginica6.9 3.1 5.4 2.1 virginica6.7 3.1 5.6 2.4 virginica6.9 3.1 5.1 2.3 virginica5.8 2.7 5.1 1.9 virginica6.8 3.2 5.9 2.3 virginica6.7 3.3 5.7 2.5 virginica6.7 3.0 5.2 2.3 virginica6.3 2.5 5.0 1.9 virginica6.5 3.0 5.2 2.0 virginica6.2 3.4 5.4 2.3 virginica5.9 3.0 5.1 1.8 virginica




Algoritmo do Vizinho Mais Proximo - Neareast Neighbor

1 Seja Xnew um vetor cuja classe e desconhecida.

2 Procurar na tabela o vetor armazenado mais proximo deXnew.

3 Chamar de Xnear o vetor mais proximo de Xnew

4 Atribuir a Xnew a mesma classe de Xnear

5 Se a classificacao for correta incluir Xnew na tabela.

Mao a obra, ou melhor ao codigo ...




Qual o problema com o Vizinho Mais Proximo?




Uma Solucao

KNN - K Vizinhos Mais Proximos(K=Numero Impar Inteiro)O Padrao e classificado de acordo com a maioria dos vizinhos.




Algoritmo dos K Vizinhos Mais Proximos - K NeareastNeighbors

1 Armazenar os exemplos em uma tabela.

2 seja Xnew um vetor de classe desconhecida.

3 Encontrar na tabela os K vetores mais proximos de Xnew

4 Seja Ck a classe a que pertence a maioria dos vetores.

5 Atribuir Classe(Xnew) = Ck

6 Se a classificacao for correta incluir Xnew na tabela.

Bom, vamos ao codigo ...




Vantagens e Desvantagens do KNN

Vantagens

Simplicidade de Implementacao.

Ideal para tabelas pequenas ou medias.

Nao requer treinamento.

Desvantagens

Alto custo computacional para tabelas grandes.

A constante K e obtida por tentativa e erro.




Distancia Mınima ao Centroide

Cada classe passa a ter um unico vetor que a representachamado de centroide.

Apos o ”treinamento”nao sera necessario armazenar osexemplos. Apenas os centroides permanecem na memoria.

O centroide e o vetor medio, ou seja, a media dos exemplosda classe.

O centroide e o representante de sua classe.




Distancia Mınima ao Centroide




Atualizando o Centroide

Como foi visto o centroide representa a classe, portanto,descoberto um novo indivıduo da classe, o centroide deve/pode seratualizado.Mj(nj + 1) = (1− a)Mj(nj) + a(Xnew)Onde:a = 1/(nj + 1) e o fator de aprendizagemnj e o total de exemplos utilizados antes da chegada do XnewMj(nj) e o centroide antes da chegada do XnewMj(nj + 1) e o novo centroide com Xnew incorporado.




Avaliando Classificadores - Matriz de Confusao

Corretamente Classificadas = 5 + 3 + 11 = 19Erroneamente Classificadas = 2 + 3 + 0 + 0 + 2 + 1 = 8Total de Instancias = 27Taxa de Acerto = 19/27 (70,4 % )Taxa de Erro = 8/27 (29,6 % )




Matriz de Confusao por Classe - Tabela de Confusao -Binario

TP = True Positives. Verdadeiros Positivos. Classificados corretamente como gatos.FP = False Positives. Falsos Positivos. Classificados como gatos que sao outra coisaFN = False Negatives. Falsos Negativos. Classificados como outra coisa, mas sao realmente gatos.TN = True Negatives. Classificados como outra coisa e realmente nao sao gatos.




Metricas

True Positive Rate (Recall) (TPR). TPR = TP / (TP + FN)

True Negative Rate (Specificity) SPC = TN / (FP + TN)

Positive Predictive Value (Precision) PPV = TP / (TP + FP)

Negative Predictive Value (NPV) NPV = TN / (TN + FN)

False Positive Rate (fall-out) FPR = FP /( FP + TN)

False Discovery Rate (FDR) FDR = FP /(FP + TP) = 1 -PPV

False Negative Rate (Miss Rate) FNR = FN / ( FN + TP)

etc etc etc




Metricas Curva ROC - Receiver Operating Characteritics

Area Sob a curva. Acima de 0.9 (excelente). Entre 0.8 e 0.9(bom). Entre 0.7 e 0.8 (medio). Entre 0.6 e 0.7 (fraco).Abaixo de0.6 (ineficaz).




Continua ...

Isso e so o comeco ....




Contatos

Prof. Ronaldo F. RamosDoutor em Systemes Informatiques (Informatica)- Universidade de Evry - Franca.Pos Doutorado - UFC - DETIMestre em Engenharia de Producao/Inteligencia Aplicada - Universidade Federal deSanta CatarinaEngenheiro Mecanico - Universidade Federal do Ceara30 Anos de experiencia em Projetos de Engenharia e Sistemas [email protected]

Prof. Guilherme de Alencar BarretoDoutor em Engenharia Eletrica - Universidade de Sao Paulo - USP - Sao Carlos /Universidade de Bielefeld, UB, AlemanhaMestre em Engenharia Eletrica - Universidade de Sao Paulo - USP - Sao CarlosEngenheiro de Teleinformatica - Universidade Federal do CearaBolsista CNPQ Nıvel 2http://lattes.cnpq.br/8902002461422112



Education

Inteligência Artificial - Data Mining