Kva er retorikk?

No aprendizado supervisionado, podem-se destacar diversos paradigmas de aprendi- zado, que determinam a abordagem utilizada por um algoritmo deAMdurante o processo de indu¸c˜ao de um classificador. Esta se¸c˜ao apresenta brevemente trˆes paradigmas muito utilizados: simb´olico, estat´ıstico e baseado em exemplos. Algoritmos de classifica¸c˜ao ba- seados nesses paradigmas foram utilizados nos experimentos desta pesquisa.

Para ilustrar o funcionamento de alguns algoritmos de classifica¸c˜ao apresentados nesta se¸c˜ao, ser´a utilizado como exemplo um conjunto de dados formado por animais vertebrados e suas caracter´ısticas. Dependendo de suas caracter´ısticas, cada vertebrado ´e classificado

em uma das cinco categorias: “Mam´ıfero”, “R´eptil”, “Peixe”, “Anf´ıbio” ou “P´assaro”. A Tabela 2.1 apresenta esse conjunto de dados.

Tabela 2.1: Conjunto de Dados de Vertebrados (Tan et al., 2005)

Animal Temperatura Corporal Cobertura da pele Ov´ıparo Criatura Aqu´atica Criatura A´erea Possui

PernasHiberna Classe Humano Quente Cabelos N˜ao N˜ao N˜ao Sim N˜ao Mam´ıfero Cobra Fria Escamas Sim N˜ao N˜ao N˜ao Sim R´eptil Salm˜ao Fria Escamas Sim Sim N˜ao N˜ao N˜ao Peixe Baleia Quente Cabelos N˜ao Sim N˜ao N˜ao N˜ao Mam´ıfero Sapo Fria N˜ao possui Sim Semi N˜ao Sim Sim Anf´ıbio Morcego Quente Cabelo N˜ao N˜ao Sim Sim Sim Mam´ıfero Pomba Quente Penas Sim N˜ao Sim Sim N˜ao P´assaro Gato Quente Pelos N˜ao N˜ao N˜ao Sim N˜ao Mam´ıfero Tartaruga Fria Escamas Sim Semi N˜ao Sim N˜ao R´eptil Pinguim Quente Penas Sim Semi N˜ao Sim N˜ao P´assaro Porco Espinho Quente Espinhos N˜ao N˜ao N˜ao Sim Sim Mam´ıfero Enguia Fria Escamas Sim Sim N˜ao N˜ao N˜ao Peixe Salamandra Fria N˜ao possui Sim Semi N˜ao Sim Sim Anf´ıbio

Paradigma Simb´olico

O paradigma simb´olico fundamenta-se na constru¸c˜ao de representa¸c˜oes simb´olicas para a generaliza¸c˜ao do conhecimento. Em classifica¸c˜ao, essas representa¸c˜oes s˜ao formadas por meio de relacionamentos l´ogicos entre os atributos de entrada do conjunto de dados e as classes envolvidas no problema. As representa¸c˜oes simb´olicas geradas geralmente podem ser interpretadas em linguagem natural, de maneira similar `a representa¸c˜ao do conhecimento utilizada por seres humanos, na forma de alguma express˜ao l´ogica, ´arvores de decis˜ao, regras ou rede semˆantica (Monard e Baranauskas, 2003).

Sistemas baseados nesse paradigma s˜ao muito ´uteis quando o classificador gerado pre- cisa ser interpretado por especialistas da ´area do problema ao qual o classificador est´a sendo aplicado. Duas t´ecnicas muito utilizadas em aprendizado simb´olico s˜ao t´ecnicas para indu¸c˜ao de AD e t´ecnicas para extra¸c˜ao de regras de decis˜ao, das quais pode-se destacar os algoritmos C4.5 e Ripper, respectivamente, brevemente apresentados a seguir.

´

Arvores de Decis˜ao

Uma maneira natural e intuitiva de se classificar um padr˜ao ´e por meio de uma sequˆen- cia de decis˜oes, em que a pr´oxima decis˜ao depende da decis˜ao atual (Larranaga et al.,

2006). Essa sequˆencia de decis˜oes pode ser representada por uma estrutura de dados do tipo ´arvore, a qual ´e definida recursivamente como: um n´o folha que corresponde a uma classe ou um n´o interno, de decis˜ao, que cont´em uma decis˜ao sobre algum atributo. Para cada resultado da decis˜ao, existe uma aresta para uma sub´arvore. Essa t´ecnica de clas- sifica¸c˜ao est´a entre as mais populares e tem sido aplicada em tarefas como, por exemplo, diagn´ostico m´edico (Mitchell, 1997).

2.1 Conceitos Fundamentais de Classifica¸c˜ao 11 Na Figura2.3´e apresentado um exemplo de ´arvore de decis˜ao para a classifica¸c˜ao dos vertebrados da Tabela2.1. A partir das caracter´ısticas de cada animal, a ´arvore de decis˜ao realiza inferˆencias para classific´a-lo. Supondo que uma nova esp´ecie X de um animal seja descoberta e deva ser classificada como “Mam´ıfero” ou “N˜ao Mam´ıfero”, as caracter´ısticas da tabela podem ser utilizadas para essa classifica¸c˜ao. Atrav´es das caracter´ısticas da tabela, se um animal tem a temperatura do corpo fria, ele definitivamente n˜ao ´e um mam´ıfero. Se a temperatura de seu corpo ´e quente, ele pode ser um p´assaro ou um mam´ıfero. Assim, ´e necess´ario verificar se ele ´e um ov´ıparo. Aqueles animais que n˜ao s˜ao ov´ıparos s˜ao mam´ıferos, enquanto os outros animais n˜ao s˜ao mam´ıferos.

Figura 2.3: AD para a Classifica¸c˜ao de Vertebrados (Tan et al., 2005)

A classifica¸c˜ao de dados em uma AD se inicia na raiz em dire¸c˜ao a um n´o-folha, que define a classe. Nesse processo, ao testar um atributo em um determinado n´o, move-se para baixo na ´arvore por meio do ramo relacionado ao valor do atributo presente no exemplo de teste. O processo ´e repetido para a sub´arvore enraizada no novo n´o. O algoritmo C4.5 (Quinlan,1993) ´e um exemplo de algoritmo de indu¸c˜ao deADmuito utilizado em AM.

As ADs foram escolhidas como uma das t´ecnicas de classifica¸c˜ao utilizadas neste tra- balho devido, principalmente, a sua alta interpretabilidade e facilidade de entendimento. Regras de Decis˜ao

Um classificador baseado em regras classifica exemplos utilizando uma cole¸c˜ao de re- gras da forma “Se . . . Ent˜ao . . . ”, extra´ıdas do conjunto de exemplos de treinamento (Tan et al., 2005). As regras s˜ao extra´ıdas utilizando algoritmos de cobertura sequencial de

exemplos, que seguem um estrat´egia gulosa para a obten¸c˜ao das regras. Um conjunto de regras, inicialmente vazio, ´e incrementado `a medida que as regras s˜ao selecionadas e, a cada itera¸c˜ao, uma classe ´e analisada, sendo considerada positiva e todas as outras como negativas. A melhor regra ´e selecionada para compor o conjunto de regras, baseado em uma medida de avalia¸c˜ao. ´E desej´avel que uma regra cubra a maioria dos exemplos posi- tivos e nenhum (ou poucos) exemplo(s) negativo(s). A seguir, ´e apresentado um conjunto de regras extra´ıdo do conjunto de dados de vertebrados da Tabela 2.1.

• R1 : SE (Criatura Aqu´atica = Sim) E (Temperatura Corporal = Fria) ENT˜AO

(Classe = Peixe)

• R2 : SE (Cobertura da Pele = Cabelos) E (Criatura Aqu´atica = N˜ao) ENT˜AO

(Classe = Mam´ıfero)

• R3 : SE (Cobertura da Pele = Escamas) E (Criatura Aqu´atica = N˜ao) ENT ˜AO

(Classe = R´eptil)

• R4 : SE (Ov´ıparo = Sim) E (Criatura A´erea = SIM) ENT˜AO (Classe = P´assaro)

• R5 : SE (CoberturaPele = N˜ao possui) ENT ˜AO (Classe = Anf´ıbio)

Um exemplo de teste ´e classificado de acordo com a regra na qual suas caracter´ısticas se enquadram. Por exemplo, dado um novo animal com as caracter´ısticas apresentadas na tabela 2.2, suas caracter´ısticas se enquadram na regra R1, e portanto sua classifica¸c˜ao

ser´a “Peixe”.

Tabela 2.2: Conjunto de Dados de Vertebrados (Tan et al., 2005)

Animal Temperatura Corporal Cobertura da pele Ov´ıparo Criatura Aqu´atica Criatura A´erea Possui Pernas Hiberna Tubar˜ao Fria Escamas N˜ao Sim N˜ao N˜ao N˜ao

O algoritmo Ripper (Cohen,1995) ´e um dos algoritmos mais utilizados para a extra¸c˜ao de regras. Ele ordena, de maneira crescente, as classes envolvidas no problema de acordo com sua frequˆencia no conjunto de treinamento, e ´e adequado para a constru¸c˜ao de mo- delos em conjuntos de dados desbalanceados. Al´em disso, ele trabalha bem com dados com ru´ıdo, devido ao seu mecanismo de valida¸c˜ao, que previne o super-ajuste do modelo ao conjunto de treinamento. Devido a essas caracter´ısticas, esse algoritmo foi escolhido como um dos algoritmos utilizados nesta pesquisa.

Paradigma Estat´ıstico

A id´eia geral de t´ecnicas que se baseiam nesse paradigma ´e explorar as dependˆencias funcionais de um conjunto de dados por meio de modelos estat´ısticos, e assim encontrar um classificador que separe corretamente os dados em suas classes.

2.1 Conceitos Fundamentais de Classifica¸c˜ao 13 V´arias dessas t´ecnicas assumem alguma forma de modelo, e ent˜ao encontram valores apropriados para os parˆametros do modelo a partir dos dados de treinamento. Um classi- ficador linear, por exemplo, assume que as classes podem ser expressas como combina¸c˜ao linear dos valores dos atributos, e ent˜ao procura uma combina¸c˜ao linear particular que fornece a melhor aproxima¸c˜ao sobre o conjunto de dados (Monard e Baranauskas, 2003). Inicialmente, assume-se que os dados s˜ao gerados de forma independente e identica- mente distribu´ıda, de acordo com o modelo de distribui¸c˜ao de probabilidade assumido para o problema. Duas t´ecnicas muito utilizadas baseadas nesse paradigma s˜ao SVMs e Redes Bayesianas.

M´aquinas de Vetores de Suporte

As SVMs, baseadas na teoria de aprendizado estat´ıstico, utilizam fun¸c˜oes de kernel para mapear os vetores de caracter´ısticas dos exemplos para um espa¸co de dimens˜ao mais elevada, geralmente muito maior que o espa¸co original (Cristianini e Shawe-Taylor,2000). Com um mapeamento apropriado para uma dimens˜ao suficientemente grande, ´e poss´ıvel separar dados de duas classes por meio de um hiperplano.

Para problemas com mais de duas classes, s˜ao utilizadas duas estrat´egias. A primeira ´e conhecida como um-contra-todos, na qual o problema ´e decomposto em K problemas bin´arios, sendo K o n´umero de classes. Um classificador bin´ario ´e ent˜ao associado a cada classe e especializado em separar sua classe associada de todas as outras classes. Na segunda estrat´egia, chamada um-contra-um, s˜ao utilizados K(K − 1)/2 classificadores bin´arios, e cada classificador ´e utilizado para fazer a distin¸c˜ao entre um par de classes.

O objetivo no treinamento dasSVMs ´e encontrar um hiperplano que separa os dados de diferentes classes com a maior margem poss´ıvel. ´E esperado que quanto maior for essa margem, maior ´e a capacidade de generaliza¸c˜ao do classificador. A margem de separa¸c˜ao entre as classes ´e um conceito fundamental no projeto de SVMs e est´a associada ao erro permitido na classifica¸c˜ao. Os exemplos que se encontram dentro da margem de separa¸c˜ao ou sobre ela s˜ao chamados de vetores de suporte e definem a superf´ıcie de separa¸c˜ao. A Figura 2.4 ilustra o mapeamento dos dados do problema de classifica¸c˜ao de vertebrados, considerando duas caracter´ısticas, para um espa¸co de maior dimens˜ao. O conjunto de dados bidimensional representado na Figura2.4.a ´e mapeado para um espa¸co tridimensional representado na Figura 2.4.b. Nesse espa¸co, ´e determinado o hiperplano de separa¸c˜ao entre as classes.

A Figura 2.5 ilustra um hiperplano de separa¸c˜ao para o problema de classifica¸c˜ao dos vertebrados nas classes “Mam´ıfero” e “N˜ao Mam´ıfero”.

A escolha dasSVMs como uma das t´ecnicas de classifica¸c˜ao utilizadas nesta pesquisa foi motivada pela sua boa capacidade de generaliza¸c˜ao, mesmo para problemas com muitos atributos.

Figura 2.4: Exemplos de Problema de Separa¸c˜ao de Dados usando SVMs

Figura 2.5: Exemplo de Hiperplano de Separa¸c˜ao das SVMs Redes Bayesianas

As Redes Bayesianas est˜ao fundamentadas na manipula¸c˜ao de probabilidades expl´ıci- tas para hip´oteses. O c´alculo das probabilidades ´e feito com base no teorema de Bayes (Bayes, 1763). Segundo esse teorema, um problema de classifica¸c˜ao pode ser formalizado de maneira estat´ıstica. Sendo T um conjunto de atributos e y uma classe, se y tem uma rela¸c˜ao n˜ao determin´ıstica com os atributos, T e y podem ser tratatos como vari´aveis aleat´orias e ter sua rela¸c˜ao probabil´ıstica capturada por P (y|T ). Essa probabilidade con- dicional ´e conhecida como probabilidade a posteriori de y, em oposi¸c˜ao `a sua probabilidade a priori, P (y) (Tan et al., 2005).

Durante a fase de treinamento, as probabilidades a posteriori P (y|T ) de todas as combina¸c˜oes de T e y s˜ao obtidas, baseado nas informa¸c˜oes dos exemplos de treinamento. Atrav´es dessas probabilidades, um exemplo de teste T′ _{pode ser classificado encontrando-}

2.1 Conceitos Fundamentais de Classifica¸c˜ao 15 se a classe y′ _{que maximiza a probabilidade a posteriori P (y}′_{, |T}′_).

A abordagem de Redes Bayesianas utiliza uma representa¸c˜ao gr´afica que descreve os relacionamentos entre as vari´aveis do conjunto de dados (atributos e classes). Essa representa¸c˜ao ´e constitu´ıda de um Grafo Ac´ıclico Direcionado (DAG) (Directed Acyclic Graph) e de uma tabela de probabilidades para cada n´o do DAG. Os n´os representam vari´aveis e os arcos representam rela¸c˜oes de dependˆencia entre pares de vari´aveis.

A Figura 2.6 ilustra um exemplo de utiliza¸c˜ao de uma Rede Bayesiana para modelar um problema de pacientes com doen¸cas card´ıacas e azia. Cada vari´avel do diagrama possui apenas dois valores. Os n´os pais do n´o que corresponde `a vari´avel doen¸cas card´ıacas (DC) representam fatores de risco que podem influenciar na doen¸ca, como pr´atica de exerc´ıcios (PE) e dieta saud´avel (DS). Os n´os filhos do n´o (DC) correspondem aos sintomas da doen¸ca, como dor no peito (DP) e press˜ao sangu´ınea alta (PA). Os n´os associados aos fatores de risco contˆem as probabilidades a priori, enquanto os n´os (DC), azia (A) e seus sintomas contˆem as probabilidades a posteriori.

Figura 2.6: Exemplo de Rede Bayesiana para Detectar Doen¸cas Card´ıacas e Azia (adap- tado de Tan et al.(2005))

Atrav´es do exemplo da Figura 2.6 pode-se, por exemplo, obter a probabilidade a posteriori de uma pessoa n˜ao ter uma doen¸ca card´ıaca dado que ela n˜ao pratica exerc´ıcios,

por´em tem uma dieta saud´avel. Essa probabilidade condicional ´e dada pela Equa¸c˜ao2.1. P (DC = N ˜ao|P E = N ˜ao, DS = Sim) = 1 − P (DC = Sim|P E = N ˜ao, DS = Sim)

= 1 − 0, 55

= 0, 45 (2.1)

Em uma Rede Bayesiana, uma vari´avel A ´e dita condicionalmente dependente de B quando o n´o que a representa tem como n´o pai o n´o que representa a vari´avel B. A vari´avel DP, por exemplo, ´e condicionalmente dependente das vari´aveis DC e A. Uma vez gerada a topologia da Rede Bayesiana, a classe predita ´e dada pelo r´otulo mais prov´avel, baseado no valor dos atributos de entrada do exemplo apresentado.

A t´ecnica de Rede Bayesiana foi escolhida como uma das t´ecnicas de classifica¸c˜ao desta pesquisa devido ao fato de capturar o conhecimento a priori do conjunto de dados utilizando um modelo gr´afico, fornecendo probabilidades que denotam o grau de certeza da classifica¸c˜ao. Al´em disso, a t´ecnica ´e robusta ao super-ajustamento (Tan et al., 2005). Paradigma Baseado em Exemplos

Esse paradigma tem como pressuposto que se dois exemplos s˜ao similares, ent˜ao eles pertencem `a mesma classe. Desta forma, quando um novo exemplo ´e similar a um exemplo conhecido, a classe deste ´e atribu´ıda ao novo exemplo. Ao contr´ario de outros paradigmas, que durante a fase de treinamento geram um modelo de classifica¸c˜ao expl´ıcito e depois descartam os exemplos de treinamento, algoritmos desse paradigma precisam manter os exemplos de treinamento na mem´oria para classificar novos exemplos, por isso s˜ao cha- mados de pregui¸cosos (lazy) (Monard e Baranauskas,2003). Uma t´ecnica muito utilizada ´e a t´ecnica dos K-vizinhos mais pr´oximosKNN, brevemente apresentada a seguir. K-Vizinhos mais pr´oximos

O algoritmo KNN relaciona cada um dos exemplos de treinamento a um ponto em um espa¸co n-dimensional, sendo n o n´umero de atributos de entrada que descrevem o conjunto de dados (Fix e Hodges,1951). Para classificar um novo exemplo, a similaridade com outros exemplos j´a conhecidos ´e calculada por meio do c´alculo da distˆancia de tais exemplos ao novo exemplo. Essa distˆancia geralmente ´e calculada pela medida da distˆancia Euclidiana entre os exemplos, considerando os valores de seus atributos de entrada. O n´umero de exemplos a serem comparados com um novo exemplo ´e dado pelo parˆametro K do algoritmo.

A Figura2.7ilustra exemplos de classifica¸c˜ao utilizando o algoritmoKNNpara valores de K iguais a 1, 2 e 3. Um novo exemplo X ´e classificado baseado nas classes de seus K vizinhos mais pr´oximos.

Ao contr´ario de algoritmos como ADs e baseados em regras, que buscam um modelo global para ajustar todo o espa¸co de busca, o algoritmoKNN faz suas predi¸c˜oes baseado

2.1 Conceitos Fundamentais de Classifica¸c˜ao 17

Figura 2.7: Exemplo de Classifica¸c˜ao Utilizando a t´ecnica KNN para K igual a 1, 2 e 3 (adaptado de Tan et al.(2005))

em informa¸c˜oes locais. Devido a essa caracter´ıstica, o algoritmo KNN ´e mais suscet´ıvel a ru´ıdo nos dados. Apesar disso, esse algoritmo produz fronteiras de decis˜ao mais ar- bitr´arias, fornecendo um modelo mais flex´ıvel que algoritmos como ADs e baseados em regras. A variabilidade das fronteiras de decis˜ao do algoritmo KNN tamb´em ´e maior, j´a que elas dependem da composi¸c˜ao dos exemplos de treinamento (Tan et al.,2005). Devido a essas caracter´ısticas, o algoritmo KNN foi um dos escolhidos para compor o conjunto de algoritmos de classifica¸c˜ao utilizados nesta pesquisa.