Universidade de São Paulo Instituto de Ciências ... jbatista/procimg/Aula3_  · Naive Bayes. 5 •Uma…

  • View
    212

  • Download
    0

Embed Size (px)

Transcript

  • 1

    Universidade de So PauloInstituto de Cincias Matemticas e de Computao

    Francisco A. Rodrigues

    Departamento de Matemtica Aplicada e Estatstica - SME

  • 2

    Conceitos bsicos

    Naive Bayes

    K-vizinhos mais prximos

    Redes Neurais

    Outros classificadores

    Combinao de classificadores

  • 3

    NaiveNaive BayesBayes

  • 4

    Se em uma dimenso para N pontos temos N dados,

    em l dimenses termos Nl dados.

    Assim, se l grande, a estimao de uma fdp

    multidimensional difcil de se obter.

    Logo, devemos fazer algumas concesses acerca da

    preciso que esperamos obter na estimao de uma

    fdp.

    Naive Bayes

  • 5

    Uma das suposies que podemos fazer que os

    atributos individuais so estatisticamente

    independentes. Assim:

    Para fazer essa estimao ser necessrio lN (l

    pontos para cada fdp 1D) ao invs de Nl pontos.

    Naive Bayes

  • 6

    O classificador Naive Bayes associa o vetor de

    atributos x classe:

    Apesar da limitao em assumir independncia dos

    atributos, o classificador Naive Bayes robusto e

    apresenta boa performance para muitos dados reais.

    Naive Bayes

  • 7

    Naive Bayes

    Naive Bayes no Weka:

    http://www.cs.waikato.ac.nz/ml/weka/

  • 8

    Naive Bayes

    Formato:

  • 9

    Naive Bayes

    Naive Bayes no Weka:

    @RELATION iris

    @ATTRIBUTE sepallength REAL@ATTRIBUTE sepalwidth REAL@ATTRIBUTE petallength REAL@ATTRIBUTE petalwidth REAL@ATTRIBUTE class {Iris-setosa,Iris-versicolor,Iris-virginica}

    @DATA5.1,3.5,1.4,0.2,Iris-setosa4.9,3.0,1.4,0.2,Iris-setosa4.7,3.2,1.3,0.2,Iris-setosa4.6,3.1,1.5,0.2,Iris-setosa5.0,3.6,1.4,0.2,Iris-setosa5.4,3.9,1.7,0.4,Iris-setosa...

  • 10

    Naive Bayes

  • 11

    kk--vizinhosvizinhos mais prmais pr ximosximos

    knnknn

  • 12

    k-vizinhos mais prximos (knn)

  • 13

    Os elementos das classes so pontos no Rn

    Em geral, os vizinhos so definidos por uma

    distncia, que pode ser a euclidiana

    ou outras mtricas, como Mahalanobis.

    k-vizinhos mais prximos (knn)

  • 14

    Algoritmo:

    Identifique os k-vizinhos mais prximos do vetor de

    atributos x que se quer classificar.

    Determine o nmero de vizinhos em cada classe.

    Classifique x com pertencente classe que resultou

    em um maior nmero de vizinhos.

    k-vizinhos mais prximos (knn)

  • 15

    k-vizinhos mais prximos (knn)

  • 16

    Propriedades:

    A verso mais simples do mtodo considera k=1, que

    conhecida como nearest neighbor rule (NN).

    Dado que o conjunto de treinamento seja relativamente

    grande, pode-se provar que:

    Ou seja, o erro cometido na classificao no mximo duas

    vezes maior do que o classificador bayesiano, que timo.

    k-vizinhos mais prximos (knn)

  • 17

    Propriedades:

    Para o caso de duas classes, pode-se mostrar que:

    Ou seja, quando k tende ao infinito, a performance do knn

    tende performance tima (igual performance do

    classificador bayesiano).

    k-vizinhos mais prximos (knn)

  • 18

    Regies de separao: Telhas de Voronoi

    k-vizinhos mais prximos (knn)

  • 19

    function z=k_nn_classifier(Z,v,k,X) [l,N1]=size(Z); [l,N]=size(X); c=max(v); % The number of classes % Computation of the (squared) Euclidean distance% of a point from each reference vectorfor i=1:N

    dist=sum((X(:,i)*ones(1,N1)-Z).^ 2); %Sorting the above distances in ascending order[sorted,nearest]=sort(dist); % Counting the class occurrences among the k-closest% reference vectors Z(:,i) refe=zeros(1,c); %Counting the reference vectors per classfor q=1:k

    class=v(nearest(q)); refe(class)=refe(class)+1;

    end[val,z(i)]=max(refe);

    end

    k-vizinhos mais prximos (knn)

  • 20

    function clas_error=compute_error(y,y_est) [q,N]=size(y); % N= no. of vectorsc=max(y); % Determining the number of classes clas_error=0; % Counting the misclassified vectorsfor i=1:N

    if(y(i)~ =y_est(i)) clas_error=clas_error+1;

    endend

    % Computing the classification error clas_error=clas_error/N;

    k-vizinhos mais prximos (knn)

    Clculo do erro na classificao:

  • 21

    Redes neurais artificiaisRedes neurais artificiais

  • 22

    Redes neurais artificiais

    Motivao

    O crebro humano possui em torno de 1011

    neurnios.

    O funcionamento desses neurnios constitui a base

    para o estudo das redes neurais.

  • 23

    Redes neurais artificiais

    Motivao

  • 24

    Redes neurais artificiais

    Motivao

  • 25

    Redes neurais artificiais

    Histrico

    Um histrico resumido sobre Redes Neurais Artificiais deve comear por trs das

    mais importantes publicaes iniciais, desenvolvidas por: McCulloch e Pitts (1943),

    Hebb (1949), e Rosemblatt (1958).

    Estas publicaes introduziram o primeiro modelo de redes neurais simulando

    mquinas, o modelo bsico de rede de auto-organizao, e o modelo Perceptron de

    aprendizado supervisionado, respectivamente.

    Alguns histricos sobre a rea costumam pular os anos 60 e 70 e apontar um

    renicio da rea com a publicao dos trabalhos de Hopfield (1982) relatando a

    utilizao de redes simtricas para otimizao e de Rumelhart, Hinton e Williams

    que introduziram o poderoso mtodo Backpropagation.

    Entretanto, para se ter um histrico completo, devem ser citados alguns

    pesquisadores que realizaram, nos anos 60 e 70, importantes trabalhos sobre

    modelos de redes neurais em viso, memria, controle e auto-organizao como:

    Amari, Anderson, Cooper, Cowan, Fukushima, Grossberg, Kohonen, von der

    Malsburg, Werbos e Widrow.

  • 26

    Aprendizado

    O que aprender?

    Incrementar o conhecimento

    adaptar-se melhor s novas situaes do ambiente

    ...

    Como se aprende?

    Observando

    Memorizando

    Generalizando

    Especializando

    .....

  • 27

    O que necessrio para o aprendizado?

    Aspecto externo (do ambiente)

    exemplos, experincias, ensino, ....

    Aspecto estrutural (do agente)

    sentidos

    crebro (baixo nvel)

    memria e processador de smbolos (alto nvel)

    Aspecto funcional (mecanismos de aprendizado)

    modelo simblico: representao de conhecimento, induo, deduo

    modelo conexionista: redes neurais

  • 28

    Redes neurais

    Tcnica de aprendizado que tem como modelo o crebro.

    Q_ _m n_ _ Ch_ r _ , n_ _ m _ m _ !

    Voc consegue identificar a frase?

    Pegar uma borracha sendo arremessada

    Apesar de no ser to rpido quanto um computador,

    nosso crebro consegue calcular a trajetria da borracha

    muito bem.

    O crebro humano formado por 100 bilhes de

    neurnios, cada um, ligado a outro ou a 100.000 outros!

  • 29

    Redes neurais artificiais

    Neurnio

    Dendritos: Tm por funo receber informaes ou impulsos nervosos,

    oriundos de axnios de outros neurnios e conduzi-los at o corpo celular.

    Corpo celular: os sinais recebidos so somados e de acordo com um

    limiar, estabelece se o neurnio deve ser ativado ou no. O limiar um

    valor ou taxa de valores que determinam a ativao do neurnio. Se o

    somatrio ultrapassar este valor o neurnio dispara

    Axnio: Os impulsos ou disparos so transmitidos a outros neurnios,

    passando atravs do axnio at os dendritos dos neurnios seguintes.

  • 30

    Redes neurais artificiais

    Neurnio

    Fisicamente no h contato entre os neurnios, porm entre

    a terminao axnica de um neurnio e o dendrito de outro, h

    um espao chamado de espao sinaptico.

    Atravs das sinapses os neurnios se unem funcionalmente,

    formando redes neurais.

    As sinapses funcionam como vlvulas, sendo capazes de

    controlar a transmisso de impulsos entre os neurnios.

    http://www.youtube.com/watch?v=HXx9qlJetSU

  • 31

    Redes neurais artificiais

    Neurnio

    As sinapses podem ser excitatrias ou inibitrias:

    Excitatria: ocorre quando a ativao do neurnio alta e a

    soma dos impulsos recebidos pelo neurnio supera o seu limiar,

    disparando ento uma substncia dita Neurotransmissora, no

    espao sinaptico.

    Esta substncia altera o potencial eltrico da membrana ps-

    sinaptica, preparando para o envio de impulsos eletricos;

    Inibitria: reduz a capacidade de recepo do outro neurnio.

  • 32

    Redes neurais artificiais

    Definio

  • 33

    Redes neurais artificiais

    Aquisio do conhecimento: Aprendizado

  • 34

    Redes neurais artificiais

    Devido similaridade com a estrutura do crebro, as

    redes neurais exibem caractersticas similares ao

    comportamento humano, tais como:

  • 35

    Redes neurais artificiais

    Devido similaridade com a estrutura do crebro, as

    redes neurais exibem caractersticas similares ao

    comportamento humano, tais como:

  • 36

    Redes neurais artificiais

    Devido similaridade com a estrutura do crebro, as

    redes neurais exibem caractersticas similares ao

    comportamento humano, tais como:

  • 37

    Redes neurais artificiais

    Devido similaridade com a estrutura do crebro, as

    redes neurais exibem caractersticas similares ao

    comportamento humano, tais como:

  • 38

    Redes neurais artificiais

    Devido similaridade com a estrutura do creb