A Tarefa de Classificaçao em˜ Text Mining · Eduardo Bezerra; Ronaldo Goldschmidt / Revista de Sistemas de Informacao da FSMA n. 5 (2010) pp. 42-62 estão associadas ao tipo

Revista de Sistemas de Informacao da FSMA n. 5 (2010) pp. 42-62 http://www.fsma.edu.br/si/sistemas.html

A Tarefa de Classificação em Text MiningEduardo Bezerra e Ronaldo Goldschmidt

Resumo—A tarefa de classificação consiste em criar ummapeamento de cada objeto de uma coleção (dataset) em umconjunto de categorias (ou classes). Esse mapeamento é tambémchamado de modelo de classificação ou classificador. No contextode dados textuais os objetos usados na formação do classificadorpodem ser documentos da coleção, ou mesmo frases ou palavrasque ocorrem naqueles documentos. Este tutorial fornece umaintrodução à tarefa de classificação de documentos, um dos prob-lemas mais conhecidos em Text Mining. São apresentados algunsalgoritmos populares na literatura para criação de modelos declassificação. Além disso, também são algumas descritas técnicascujo objetivo é permitir avaliar a qualidade de um modelo declassificação.

Index Terms—text mining, classificação, aprendizado indutivo.

I. INTRODUÇÃO

OS constantes avanços na área da Tecnologia daInformação têm viabilizado o armazenamento degrandes volumes dados. Tecnologias como a Internet, SistemasGerenciadores de Banco de Dados, leitores de códigos de bar-ras, dispositivos de memória secundária de maior capacidadede armazenamento e de menor custo e Sistemas de Informaçãoem geral são alguns exemplos de recursos que têm viabilizadoa proliferação e o crescimento de inúmeras bases de dados denatureza comercial, administrativa, governamental e cientı́fica.Segundo estimativas, o mundo produz atualmente de um a doisexabytes de informação por ano, o que equivale a cerca de 250megabytes ou 250 livros por ser humano.

A humanidade vive um cenário de grande sobrecarga deinformação no qual mecanismos de busca de informação pelaweb tais como GoogleTM, AltavistaTM, YahooTM, entre outros,ao invés de reduzir o problema, acabam por amplificá-lo, umavez que tornam novos documentos rapidamente disponı́veis.Por exemplo, a Google possui 4,2 bilhões de documentos emseus ı́ndices e realiza diariamente cerca de 150 milhões deconsultas, o que equivale a aproximadamente 2000 consultaspor segundo. Uma parcela significativa da informação exis-tente em formato digital é relativa a dados textuais. Estima-seque cerca de 80% dos dados existentes em empresas estejanesse formato, abrangendo documentos em intranets, páginasda Web, mensagens de e-mail, biblioteca digitais, newsgroups,blogs, dentre outros.

A busca por informação a partir de grandes quantidadesde documentos é inviável sem o auxı́lio de ferramentas com-putacionais apropriadas. Portanto, torna-se imprescindı́vel odesenvolvimento de ferramentas que auxiliem o ser humano,

Eduardo Bezerra é professor do CEFET-RJ (Centro Federal de EducaçãoTecnológica Celso Suckow da Fonseca).

Ronaldo Goldschmidt é professor do IST-FAETEC (Instituto Superior deTecnologia em Ciências da Computação do Rio de Janeiro - Fundação deApoio à Escola Técnica).

de forma automática e inteligente, na análise e na realizaçãode tarefas como extração de padrões, tendências, associaçõesa partir de coleções de dados textuais.

Para atender a essas novas demandas, surgiu uma nova áreade estudo denominada Mineração de Textos (Text Mining),que vem atraindo interesse junto às comunidades cientı́ficae industrial. Text Mining procura abstrair padrões, relaçõese regras (conhecimentos) a partir de dados textuais. Dadostextuais podem se apresentar em linguagem natural (inglês,português), ou em formato semi-estruturado (por exemplo,documentos em XML, documentos de email, etc.).

A. Complicadores no processamento de dados textuais

Há diversos complicadores na análise de dados textuais,entre eles:

• A falta de estrutura dos textos a serem analisados. Difer-entes estilos de escrita podem ter sido utilizados.

• A ambigüidade existente na estrutura e no significadodos textos. A natureza ambı́gua da linguagem naturalé um grande desafio. Confusões semânticas tais comosinonı́mia e polissemia tornam ainda mais difı́cil a tarefade compreensão da linguagem natural. A sinonı́mia com-preende as muitas formas de representar o mesmo con-ceito. Por exemplo: os termos automóvel e carro referem-se ao mesmo conceito. A polissemia, por outro lado,envolve termos iguais com significados diferentes emdiferentes contextos. Exemplo: A palavra manga possuisignificados diferentes nos contextos de fruticultura e devestuário.

B. Tipos de processamento de dados textuais

Há três tipos de processamento voltado à Análise deConteúdo, com nı́veis de sofisticação sucessivos:

• Processamento Léxico e Sintático - Envolve o reconhec-imento de tokens (termos), a normalização de termos e aconstrução da linguagem.

• Processamento Semântico - Envolve a extração do sig-nificado inerente aos textos. Requer a extração de enti-dades nomeadas tais como nomes de pessoas, nomes deorganizações, locais, etc...

• Processamento de Caracterı́sticas Extra-Semânticas -Mais complexo, envolve a identificação de sentimentosnos textos analisados. Por exemplo: sarcasmo, melanco-lia, alegria, etc.

II. TAREFAS DE Text Mining

A seguir encontram-se relacionadas e resumidas algumasdas principais principais tarefas de Text Mining. Estas tarefas

42

Eduardo Bezerra; Ronaldo Goldschmidt / Revista de Sistemas de Informacao da FSMA n. 5 (2010) pp. 42-62

estão associadas ao tipo de conhecimento a ser abstraı́do apartir dos dados analisados.

Descoberta de Associações: Abrange a busca por termosque freqüentemente ocorram de forma simultânea em doc-umentos textuais. Termos simultâneos e freqüentes podemauxiliar na remoção de ambigüidades e na caracterização decontextos. Um exemplo clássico e didático da aplicação destatarefa é na área de atendimento ao cliente: após o lançamentode um novo produto no mercado, diversos clientes utilizaramo site da empresa para relatar seu nı́vel de satisfação com talproduto. Palavras freqüentes e simultâneas podem auxiliar naidentificação de pontos fortes e fracos do produto, levando anovas ações de marketing ou até mesmo de reformulação daprodução. Algoritmos tais como o Apriori, GSP, DHP, entreoutros, são exemplos de ferramentas que implementam a tarefade descoberta de associações [1].

Agrupamento: Utilizada para separar os documentos deuma base de textos em subconjuntos ou clusters, de talforma que os documentos de um cluster compartilhem depropriedades comuns que os distingam de documentos em out-ros clusters. O objetivo nesta tarefa é maximizar similaridadeintracluster e minimizar similaridade intercluster. Diferenteda tarefa de classificação, que tem rótulos pré-definidos, aclusterização precisa automaticamente identificar os gruposde documentos aos quais o usuário deverá atribuir rótulos( [2]). Por exemplo: uma escola pode realizar um processode clusterização de sua base de documentos de forma obtergrupos de documentos que compartilhem o mesmo perfil deconteúdo. Na implementação desta tarefa podem ser utilizadosalgoritmos tais como: K-Means, K-Modes, K-Prototypes, K-Medoids, Kohonen, dentre outros.

Sumarização: Esta tarefa, muito comum em KDT, consisteem procurar identificar e indicar caracterı́sticas comuns entreconjuntos de textos [3]. Como exemplo considere um bancode textos como o mencionado no exemplo da tarefa ante-rior. Após a clusterização, uma prática usual é utilizar umalgoritmo de sumarização de textos que permita descrever deforma resumida o conteúdo dos documentos em cada cluster.Tal informação poderia ser utilizada pela equipe da escolapara organizar a chegada de novos textos. Lógica Indutiva,Algoritmos Genéticos, Otimização por Nuvem de Partı́culassão alguns exemplos de tecnologias que podem ser aplicadasna implementação da tarefa de sumarização.

Detecção de Desvios: Esta tarefa consiste em procuraridentificar documentos do banco de textos cujas caracterı́sticassejam divergentes de um conjunto de documentos textuais [3].Tais documentos são denominados “outliers”. A Estatı́sticafornece recursos para a implementação desta tarefa.

Classificação: Consiste em descobrir uma função quemapeie um conjunto de textos em um conjunto de rótuloscategóricos pré-definidos, denominados classes. Uma vez de-scoberta, a função pode ser aplicada a novos textos de formaa prever a classe em que tais textos se enquadram. Comoexemplo da tarefa de classificação, considere uma empresaque deseja separar notı́cias em função do segmento ao qualpertençam (esportes, polı́tica, religião, etc...). Uma aplicaçãoda tarefa de classificação consiste em descobrir uma funçãoque mapeie corretamente os textos, a partir de seu conteúdo,

em uma destas classes. Tal função, uma vez descoberta, podeser utilizada para prever a alocação de novos textos recebidospela empresa. Esta função pode ser incorporada a um sistemade apoio à decisão que auxilie na filtragem e catalogação dedocumentos textuais recebidos. Um outro exemplo se refereà classificação de e-mails em spam e não spam. De formaanáloga ao exemplo anterior, um mecanismo de classificaçãoautomática de e-mails pode auxiliar na filtragem de e-mailsindesejados. Redes Neurais, Algoritmos Genéticos, LógicaIndutiva são exemplos de tecnologias que podem ser aplicadasna tarefa de classificação ( [4]).

III. REPRESENTAÇÃO DE DOCUMENTOS

Há diversas técnicas de pré-processamento que permitem adeterminação de uma lista de termos T , isto é, do conjunto deunidades que compõem o vocabulário da coleção. Por outrolado, o processamento computacional em algoritmos de TextMining requer muitas vezes a representação dos documentosem um formato adequado. Portanto, uma atividade que deverealizada durante o pré-processamento de uma coleção é aescolha da forma de utilizar os termos do vocabulário pararepresentar os documentos da coleção. Em outras palavras,devemos decidir que representação deve ser utilizada paraestruturar essa coleção de documentos. Para resolver esteproblema, são usadas diversas técnicas para adicionar umadimensão numérica aos documentos. O objetivo desta seção éjustamente apresentar uma visão geral dessas técnicas.

A. O modelo de espaço Vetorial

Entre os principais modelos de representação de docu-mentos textuais, podemos citar o modelo probabilı́stico [5],os modelos booleanos clássico e estendido [6] e o modelode espaço vetorial (vector-space model, term vector model,VSM) [7].

O modelo probabilı́stico, como o próprio nome deixa trans-parecer, interpreta cada documento como um evento em umespaço amostral. O modelo booleano é baseado na Teoria dosConjuntos e interpreta cada documento como um conjunto determos. Por fim, o modelo de espaço vetorial interpreta cadadocumento utilizando conceitos e técnicas da Álgebra Lineare da Geometria Espacial. O VSM é a forma de representação emodelagem de documentos mais frequentemente utilizada noprocessamento de dados textuais. Nesse modelo, documentossão interpretados como objetos geométricos, mais especifica-mente como vetores em um espaço m-dimensional. Por contade o VSM ser o mais utilizado na prática, o restante dessaseção descreve este modelo em maiores detalhes.

Em 1975, Gerard Salton propôs um modelo matemático pararepresentar documentos, o VSM [7]. Curiosamente, Saltonoriginalmente propôs o VSM para uso em um sistema derecuperação de informações (SRI), o SMART [8]. Em um SRIque utiliza essa representação, as próprias consultas que osistema recebe, e que representam necessidades de informaçãode seus usuários, são também representadas como vetores.Desta forma, consultas e documentos podem ser manipuladosindistintamente e de forma integrada. De fato, a elegânciae simplicidade do VSM residem no fato de que, dado um

43


conjunto de documentos D e uma consulta q, para avaliara relevância de cada documento em D relativamente a q,podemos usar técnicas simples da Álgebra Linear.

Embora a utilização original do VSM tenha sido em sistemade recuperação de informações, conforme novas técnicas deanálise de dados textuais foram sendo propostas, tambémnesses casos, percebeu-se a utilidade e a adequabilidade doVSM como modelo de representação de uma coleção dedocumentos. De fato, conforme descrevemos em capı́tulosseguintes deste livro, diversas técnicas de MDT se baseiamnesse modelo de representação para documentos.

1) Matriz termo-documento: No VSM, cada documento dacoleção é representado como uma lista ordenada de valoresnuméricos, isto é, como um vetor. A cada componente dessalista, está associado um, e apenas um, termo do vocabulário.Definimos a dimensionalidade de uma coleção de docu-mentos como a cardinalidade do conjunto de termos T dovocabulário, que denotamos por m. No VSM, essa é mesmadimensionalidade do espaço vetorial em que os documentos(interpretados como vetores) são representados. Mais formal-mente, O VSM representa cada documento da coleção comoum vetor cuja forma é dada pela Equação 1.

~dj = (w1j , w2j , w3j , . . . , wmj) (1)

Cada componente do vetor ~dj é um valor numérico definidosobre um dos eixos (coordenadas) no espaço vetorial e cor-responde a um termo da coleção. Esse valor numérico estáassociado ou à importância do termo correspondente para odocumento, ou ao fato de o termo ocorrer (valor numérico 1)ou não (valor numérico 0) neste documento. (A Seção III-B,na página 45, apresenta detalhes sobre vários dos possı́veisprocedimentos de cálculo desses valores numéricos.)

Visto que cada documento da coleção é um vetor, podemosrepresentar o corpus como um todo através de uma matriz quedenotamos porM. As colunas dessa matriz são os vetores cor-respondentes aos documentos. Essa matriz é conhecida comomatriz termo-documento (term-document matrix). Se n é aquantidade de documentos do corpus e m é a dimensionalidadeda coleção, então M é de ordem m× n. Nessa matriz, cadacoluna corresponde a um documento do corpus, e cada linhaestá associada a um dos termos em T . A Figura 1 apresentaa forma esquemática de uma matriz termo-documento.

M =

w11 w12 · · · w1nw21 w22 · · · w2n

......

. . ....

wm1 wm2 · · · wmn

Figura 1. Forma esquemática de uma matriz termo-documento.

Note que a quantidade de zeros na matriz termo-documentonormalmente é grande. Em casos práticos, é comum aprodução de matrizes de termos por documentos esparsas, quechegam a conter mais de 90% de zeros. A propósito, essetambém é um aspecto relevante durante a implementação doVSM, onde é adequado utilizar estruturas de dados apropri-adas, que armazenem apenas os valores diferentes de zero da

matriz, resultando em uma significativa economia de memórianecessária para armazenamento.

2) Listas invertidas: Uma estrutura de dados normalmenteutilizada nessa implementação é a lista invertida. Para descr-ever a estrutura de uma lista invertida, considere, como exem-plo, que tenhamos uma matriz termo-documento conforme aaprensentada na Figura 2. A lista invertida correspondente àmatriz acima é apresentada na Figura 3. Nesse exemplo, queé apenas ilustrativo, a coleção é composta de 6 documentose o vocabulário tem tamanho 5 e corresponde ao conjuntode termos {t1, t2, t3, t4, t5}. Note entretanto, que em casospráticos, são comuuns coleções com dezenas ou centenas demilhares de documentos. É também comum encontrar coleçõescom vocabulários que contenham milhares ou dezenas demilhares de termos como componentes.

1 0 0 0 0 10 0 1 0 1 10 1 0 1 0 00 1 1 0 0 00 1 0 0 0 0

Figura 2. Exemplo de matriz termo-documento.

t1

��

// d1 // d6

t2

��

// d3 // d5 // d6

t3

��

// d2 // d4

t4

��

// d2 // d3

t5 // d1

Figura 3. Lista invertida correspondente à matriz da Figura 2.

3) Bolsa de palavras: A princı́pio, a simplicidade do VSMpode parecer uma desvantagem, visto que ele desconsideraqualquer aspecto acerca da estrutura lingüı́stica do texto. Emparticular, as dependências entres os termos do vocabuláriosão ignoradas no VSM.

Por exemplo, considere dois documentos em uma coleção,cada um composto por uma das duas frases a seguir: “Asmáquinas no aprendizado dos alunos” e “Os alunos de Apren-dizado de Máquinas”. Esses dois documentos seriam consid-erados equivalentes no VSM, visto que ele não considera aordem de ocorrência das palavras nos documentos da coleção,e considerando que as palavras “As”, “no”, “dos”, “Os” e “de”seriam eliminadas durante o pré-processamento.

De fato, ambos os documentos do exemplo apresentado noparágrafo anterior seriam representados pelos termos “alunos”,

44


“aprendizado” e “máquinas” do vocabulário (considerandoque não foi aplicada a normalização morfológica), sem nen-huma alusão à ordem na qual esses termos ocorrem emcada documento. Por esse motivo, outro nome pelo qual arepresentação VSM é conhecida é a denominada Bag-Of-Words (BoW), nome que remete ao fato de cada documento serrepresentado como uma bolsa de palavras, na qual a ordem deocorrência de cada palavra no documento não é considerada.

Paradoxalmente, essa caracterı́stica de desconsiderar a or-dem de ocorrência das palavras em cada documento não prej-udica a eficiência desse modelo de representação em diversastarefas relevantes da MDT.

B. Cálculo de pesos para os termosOs valores numéricos wij , i = 1..|T | correspondentes aos

elementos da matriz termo-documento M são chamados depesos. Existem diversos procedimentos alternativos para ocálculo dos pesos de uma bolsa de palavras. Entretanto, deuma forma geral, esses procedimentos tomam como pontode partida a frequência de ocorrência de cada termo, emcada documento e/ou na coleção como um todo. Esta Seçãodescreve os principais procedimentos existentes para cálculode pesos. Entretanto, é importante notar que existem diversasvariantes propostas na literatura para o cálculo dos pesos dostermos, além das que apresentamos aqui. Veja as notas bibli-ográficas deste Capı́tulo para obter referências para trabalhosque descrevem procedimentos alternativos de cálculo.

1) Medida 0/1: O procedimento de cálculo mais simples éaquele em que os pesos são binários, ou seja, cada componentewij de M é tal que wij ∈ {0, 1}. Neste procedimento, wijrecebe o valor 1 quando o documento dj contém pelo menosuma ocorrência do termo ti, e recebe o valor 0 em casocontrário. Note que este procedimento de cálculo produz umamatriz termo-documento na qual todas as entradas são binárias(com valores 0 ou 1). Podemos então resumir o procedimentode cálculo de pesos binários através da Equação 2.

wij ={

1 se dj contém ti0 se dj não contém ti

(2)

A representação VSM na qual são utilizados pesos obtidos apartir do conjunto {0,1} com o uso da Equação 2 é chamadade modelo de espaço vetorial binário (binary vector spacemodel).

Uma desvantagem desse procedimento de cálculo dos pesosé que ele não leva em consideração a intuição de que termosque aparecem mais vezes (até um certo limite; veja a discussãosobre a medida TF/IDF na página 45) são mais importantespara representar um documento do que aqueles que aparecemmenos vezes. De fato, note que este procedimento atribui ovalor 1 a um determinado componente, se os termo correspon-dente aconceu ao menos uma vez no documento em questão,independentemente da quantidade de vezes que o termo ocorre.

Os procedimentos de cálculo descritos nas próximas seçõesadotam a estratégia diferente de atribuir um valor entre 0 e 1 aum componente, em função da sua quantidade de ocorrências.Assim, saı́mos de um procedimento de atribuição de pesosbinários para descrever procedimentos que atribuem pesos nafaixa de valores do intervalo [0, 1].

2) Medida TF: Neste procedimento para cálculo de pesos,cada peso wij é dado pela função tf(t, d), que possui doisargumentos, conforme a descrição a seguir:

1) o argumento t representa um dos termos do vocabulário,2) o argumento d representa um dos documentos do corpus.A função tf(t, d) (de term frequency) é definida como

segue: dado um termo ti e um documento dj , essa funçãoretorna a quantidade de vezes que ti ocorre em dj . Este pro-cedimento de cálculo pode ser resumido através da Equação3.

wij = tf(ti, dj) (3)

3) Medida TF/IDF: O terceiro procedimento de cálculode pesos é conhecido na literatura por medida TF/IDF (termfrequency/inverse document frequency). Como motivação paraesse procedimento de cálculo de pesos, considere os conceitosde precisão e abrangência, conhecidos na área de Recuperaçãode Informações. Se um termo tal como, por exemplo, “com-putador” ocorre com razoável frequência em alguns documen-tos de uma coleção, isso muito provavelmente indica que estesdocumentos discorrem sobre computadores. A associação dotermo “computador” àqueles documentos irá então ajudar arecuperá-los em resposta a consultas apropriadas. Todavia, esteprocedimento não é adequado quando se quer obter não sóalta taxa de abrangência, mas também uma boa precisão nosdocumentos recuperados. O fato é que alta precisão implicana habilidade de distinguir documentos individuais na coleçãode outros irrelevantes à consulta em questão. Portanto, umtermo cuja frequência seja alta é relevante somente se suafrequência de ocorrência não for igualmente alta em todos osdocumentos da coleção. Por exemplo, o termo “computador”pode não ser um termo relevante em uma coleção na qualtodos os documentos versassem sobre computadores, e naqual virtualmente todos esses documentos contivessem aqueletermo.

Uma melhor forma de calcular a relevância de um termo édar maior importância (i.e., maior peso) a termos que ocorremmais raramente na coleção. Isso porque esses termos estãocertamente aptos a distinguir os poucos documentos nos quaiseles ocorrem daqueles em que eles não ocorrem. O fato queresume toda esta discussão é que bons termos, são aquelesque ocorrem frequentemente em documentos individuais, masraramente no restante dos documentos da coleção. Em outraspalavras, se dois termos quaisquer ta e tb ocorrem comigual frequência em um documento, e ta ocorrem em menosdocumentos do que tb, então o peso atribuı́do ta deve ser maiordo que o associado a tb.

A expressão matemática que reflete a intuição associadaà medida TF/IDF descrita nos parágrafos anteriores usa asfunções tf(t, d) (definida na Seção anterior) e idf(t). Estaúltima é o recı́proco da frequência documental (documentfrequency) de um termo, denotada por df(t) e definida comoo número de documentos em uma coleção D nos quais otermo t ocorre ao menos uma vez. A função idf(t) é dadapelo logaritmo do recı́proco da frequência documental (isto é,1/df(t)) vezes a quantidade de documentos em D (denotadapor |D|). Veja a Equação 4.

45


idf(t) = log(|D|

df(t)

)(4)

Sendo assim, a medida TF/IDF considera dois fatores nocálculo de wij . O primeiro fator é a frequência de um termot com relação a um documento d, conforme definido pelafunção tf(t, d). O segundo fator é a função idf(t). A ex-pressão matemática da medida TF/IDF expressa a importânciarepresentativa de um termo em relação a um documento, e édada pela Equação 5.

wij = tf(ti, dj)×idf(ti, dj) = tf(ti, dj)×log(|D|

df(ti)

)(5)

Na Equação 5, |D| corresponde à quantidade de documentosna coleção, tf(ti, dj) é a quantidade de vezes que o termoti ocorre no documento di, e df(ti) é a quantidade dedocumentos da coleção que possuem ao menos uma ocorrênciade tj .

A ideia subjacente à medida TF/IDF é a de que termos queocorrem em uma coleção não têm igual força discriminatóriapara a caracterização dos documentos. De fato, note que a me-dida TF/IDF aumenta em função da quantidade de ocorrênciasdo termo no documento. Isso traduz o conceito intuitivo deque, quanto mais um termo ocorre em um documento, maioré o indı́cio de que este termo seja representativo do mesmo.Além disso, a expressão acima também reflete outro conceitointuitivo, a saber, o fato de que quanto mais um termo ocorrena coleção como um todo, menor é o poder representativodeste termo com relação a um documento especı́fico dessacoleção. De fato, considerando a situação extrema em que umtermo ocorre em todos os documentos da coleção, o segundofator da Equação 5 se torna igual a zero, o que faz com quewij também seja igual a zero.

Outra forma de interpretar a medida TF/IDF é atravésdos escopos de informação que ela utiliza para determinarqual o peso de um termo ti relativamente a um documentodj . Em primeiro lugar, essa medida utiliza informação lo-cal da quantidade de ocorrências de ti em dj (através dafunção tf(ti, dj)). Em segundo lugar, essa medida tambémusa informação global, pois considera a quantidade de vezesque ti ocorre na coleção de documentos como um todo (atravésda função df(ti)).

4) Normalização dos Vetores: Outro aspecto importante aconsiderar no cálculo de pesos é que documentos grandes (ouseja, documentos que contêm muitos termos) são representa-dos no VSM como vetores que possuem muitas coordenadasdiferentes de zero. Isso faz com que o comprimento (módulo)desses vetores seja um valor grande, quando comparado aosdos demais documentos, o que pode resultar em distorçõesno cálculo de medidas de similaridades (veja o Apêndice Aentre os documentos, e por fim influenciar nos resultados dosalgoritmos de MDT aplicados.

De fato, já foi demonstrado experimentalmente que anormalização dos vetores ajuda a reduzir a tendência quefavorece documentos que têm maior comprimento [9]. Por essarazão, uma prática normalmente utilizada é alterar os vetoresrepresentantes dos documentos de tal forma que todos tenham

comprimento unitário. Isso equivale a um procedimento denormalização dos pesos, pois cada um dos componentes wijde um vetor é dividido pelo tamanho (ou módulo) desse vetor.A Figura 4 ilustra graficamente o problema com documentosde módulo relativamente grande.

Figura 4. Vetores de módulo muito grande têm predominância sobre outrosde módulo menor.

Para normalizar os vetores dos documentos, basta dividir(cada coordenada de) cada vetor ~d pela sua própria norma,conforme mostra a Equação 6. Nessa Equação, ||~d|| é a normaeuclideana do vetor ~d. A aplicação dessa transformação a todosos vetores faz com que todos eles passem a ter comprimentounitário.

~dnormalizado =~d

||~d||(6)

Durante o pré-processamento de um corpus, a normalizaçãode vetores é normalmente aplicada em conjunto com algumdos procedimentos de cálculo de pesos descritos anterior-mente. De fato, a combinação da medida TF/IDF com vetoresnormalizados é a mais comumente utilizada na prática. Nessecaso, cada peso wij é calculado pela Equação 7.

wij =tf(ti, dj)× idf(ti, dj)√∑|T |

k=1 [tf(ti, dj)× idf(tk, dj)]2

(7)

C. Redução da dimensionalidade da coleção

A grande dimensionalidade do espaço no qual documentosse encontram se deve ao fato do modelo de espaço vetorialconsiderar cada documento como um vetor em um espaço m-dimensional, onde m corresponde à quantidade de termos queocorrem na coleção. É comum encontrar coleções de documen-tos contendo dezenas de milhares de termos, o que leva a umarepresentação de vetores em um espaço de dimensionalidademuito grande.

Vetores representativos de documentos também têm a car-acterı́stica intrı́nseca de serem esparsos (apresentarem muitascoordenadas com valor igual a zero). Isso se deve ao fato deque apenas uma pequena quantidade de termos da coleçãocomo um todo ocorre em um determinado documento. Osdemais termos da coleção que não ocorrem nesse documentotêm no vetor correspondente o valor de coordenada igual azero.

Ocorre que, mesmo após a remoção das palavras de poucopoder discriminatório e da conflação de palavras às suas raı́zesmorfológicas, a quantidade de termos que permanecem podeainda ser muito grande para que a coleção seja tratável com-putacionalmente. Isso torna necessário e adequado eliminar o

46


máximo possı́vel de termos, de tal forma que os algoritmos demineração que forem aplicados trabalhem sobre documentosrepresentados em um espaço de dimensionalidade a menorpossı́vel. Por conta disso, outra atividade que é realizadadurante o pré-processamento de documentos corresponde àaplicação de técnicas para redução de dimensionalidade.

Técnicas para redução de dimensionalidade se baseiamna suposição de que cada documento é representado comoum conjunto de termos, onde cada termo de um documentoestá associado a um peso (valor numérico) que indica aimportância daquela caracterı́stica para o documento. Técnicaspara redução de dimensionalidade podem ser divididas em doistipos: seleção de termos e extração de termos. Independentedo tipo de técnica utilizada (a extração ou seleção de termos), aredução de dimensionalidade normalmente resulta no aumentoda eficiência do processamento da coleção e na diminuiçãodo risco de o algoritmo de mineração aplicado se ajustardemasiadamente aos documentos utilizados para geração domodelo de aprendizado. As duas próximas Seções resumem asduas famı́lias de técnicas para redução de dimensionalidade.

1) Seleção de termos: A seleção de termos tem o objetivode selecionar os termos mais representativos da coleção e que,por conta disso, devem ser utilizados como caracterı́sticas dosdocumentos durante a execução do algoritmo de agrupamento.Através da aplicação de alguma técnica de seleção sobre oconjunto original de termos To, obtém-se o conjunto de termosTf , de tal forma que |To| � |Tf | e |To| ⊃ |Tf |.

Uma técnica de seleção de termos bastaste utilizada naprática é definir dois valores inteiros positivos, δinf e δsup,e eliminar todos os termos cuja frequência (considerando acoleção de documentos como um todo) seja menor que δinfe maior que δsup. Esses valores são chamados de pontos decorte.

2) Extração de termos: A extração de termos tem o obje-tivo de obter um conjunto Tf a partir de To, o conjunto originalde termos da coleção. No entanto, diferentemente da seleçãode termos, o conjunto de termos obtido a partir de uma técnicade extração de termos não é um subconjunto do conjunto determos que existem naturalmente na coleção. Duas técnicasconhecidas de extração de termos são a Indexação SemânticaLatente (LSI, Latent Semantic Indexing) e o agrupamento determos. A estratégia geral dessas técnicas é formar termos apartir da combinação (linear ou não) dos termos originais dacoleção.

A técnica LSI leva em conta o fato de existirem de-pendências entre os termos componentes de um documento.Essa dependência se manifesta na forma de dados redundantes.No contexto do VSM (Seção III-A), cada termo que permaneceno vocabulário representa uma dimensão no espaço vetorialonde os documentos da coleção são representados. Entre-tanto, em virtude do fenômeno de sinonı́mia (veja a SeçãoI-A)), podem permanecer no vocabulário diversas palavrasque possuem o mesmo significado. Quando a representaçãoVSM é utilizada, o resultado é que mais dimensões sãocriadas no espaço de termos do que o mı́nimo necessário pararepresentar os documentos adequadamente. Nesse contexto,seria útil que houvesse alguma forma de detectar quais termossão sinônimos e substituı́-los por um único termo. Com a

aplicação da técnica LSI, algumas palavras (termos) comsignificado similar são mapeadas (projetadas) em uma mesmadimensão. Com efeito, diversas dimensões (correspondentesàs palavras com significado similar) são substituı́das por umaúnica dimensão, que representa este significado. Essa técnicasimula o comportamento humano de julgar a similaridadeconsiderando o significado entre os termos.

A técnica de agrupamento de termos consiste em formargrupos de termos, de acordo com a similaridade entres estesúltimos: termos similares são posicionados em um mesmogrupo; termo com baixa similaridade são alocados em gruposdistintos. Para o cálculo da similaridade entre um par determos, as métricas de similaridade apresentadas no ApêndiceA podem ser usadas. Uma vez formados os grupos, o con-junto de termos Ti que constituem um grupo qualquer sãosubstituı́dos no vocabulário por outro conjunto de termos Tique representem esse grupo, de tal forma que |Ti| < |Tf |. Oresultado desse procedimento é a diminuição do tamanho dovocabulário usado na representação da coleção. Em [10], Lin-den descreve diversos algoritmos de agrupamento aplicáveisa documentos (i.e., colunas da matriz termo-documento). Étambém perfeitamente possı́vel a aplicação desses algoritmospara agrupar termos de uma coleção (linhas da matriz termo-documento).

IV. VISÃO GERAL DA TAREFA DE CLASSIFICAÇÃO

A tarefa de classificação tem como objetivo produzir ummodelo que permita mapear um conjunto de objetos (doc-umentos, imagens, registros em uma tabela, etc.) em umconjunto de categorias. No caso especı́fico de Text Mining,no entanto, os objetos utilizados na construção do modelo declassificação são documentos textuais e a tarefa recebe o nomede Classificação de Documentos.

A. Abordagens para construção de classificadores

Na década de 1980, a forma usual de construção de classifi-cadores era a manual, com o uso da abordagem da engenhariado conhecimento. Atualmente, a abordagem utilizada é ado aprendizado indutivo. A seguir, apresentamos essas duasabordagens em mais detalhes.

1) Abordagem da Engenharia do Conhecimento: Nessaconstrução, um conjuntos de regras era definido por sereshumanos. Naquela época, era comum o uso de técnicas daEngenharia do Conhecimento (Knowledge Engineering) paradefinição manual de regras de classificação, que eram poste-riomente inseridas em sistemas especialistas. Essas regras declassificação eram definidas por especialistas do domı́nio.

Como exemplo da abordagem baseada em engenharia doconhecimento para geração de classificadores, considere aseguinte frase: “No Brasil, há hoje 600 unidades do carroem mãos de colecionadores. O modelo T desse automóvel foimontado no paı́s entre 1919 e 1926 com peças que vinhamdos EUA.”. Ao ler esta frase, um especialista de domı́nio podeextrair as seguintes regras para compor o classificador:

• Regra 1: (modelo or carro) and automo* → Setor Auto-mobilı́stico

47


• Regra 2: (avi* or aero*) and passage* → Setor deAviação

• Regra 3 . . .

A Regra 1 representa o conhecimento daquele especialistade domı́nio de que um documento que contenha uma ou maisocorrências das palavras modelo ou carro e simultaneamentealguma ocorrência de alguma palavra que comece por automodeve ser classificado como pertencente à categoria “SetorAutomobilı́stico”. Já na Regra 2 está implı́cito o conhecimentode que uma ou mais ocorrências de palavras de prefixos avi ouaero, e que também contenham palavras cujo prefixo é passageindicam um documento que deve ser classificado como “Setorde Aviação”.

Há duas principais desvantagens na abordagem baseadaem Engenharia de Conhecimento para construção de classi-ficadores:

1) Em primeiro lugar, a montagem manual das regras declassificação pelos especialistas do domı́nio consometempo e é bastante trabalhosa. Por exemplo, a cadanovo documento que deve ser adicionado à coleçãoMEDLINE (http://www.ncbi.nlm.nih.gov/PubMed) de-vem ser adicionados descritores provenientes da hierar-quia de conceitos MeSH (que atualmente possui 20.000descritores!). Esse processo manual demanda 2 milhõesde dólares/ano [11].

2) Outro aspecto negativo da abordagem baseada em re-gras é que diferentes especialistas de domı́nio podemgerar regras inconsistentes entre si (i.e., que predizemdiferentes classes para um mesmo documento). De fato,este problema da inconsistência tende a se agravarconforme aumenta o tamanho do conjunto de regras declassificação geradas.

As desvantagens descritas acima serviram de motivaçãopara a substituição da Engenharia do Conhecimento por outraabordagem ao longo dos anos. O detalhamento dessa outraabordagem para geração de classificadores, a baseada emaprendizado indutivo, é feito na próxima Seção.

2) Abordagem baseada em aprendizado indutivo: At-ualmente, a construção automática de classificadores é aabordagem dominante, na qual técnicas de Aprendizado deMáquina (Machine Learning) são utilizadas. Nesta abordagem,chamada de aprendizado indutivo, um conjunto de documentosde exemplo é apresentado para um algoritmo de classificação.Esse algoritmo deve então produzir uma representação ouregras de decisão para classificar futuros documentos.

Em um algoritmo cujo objetivo é a geração de um modelode classificação de documentos, a entrada fornecida é umconjunto de documentos D, onde cada um deles está associadoa uma ou mais classes pré-definidas de um conjunto finitoC = {c1, c2, . . . , cm}. Mais formalmente, a entrada é apresen-tada ao algoritmo de classificação na forma de um conjuntode pares objetos 〈di, Ci〉 onde di é o i-ésimo documento noconjunto D, e Ci é um subconjunto (possivelmente vazio) deC que corresponde às classes associadas a di.

Os documentos em D e suas classes correspondentes sãousados pelo algoritmo de classificação na construção de ummodelo de classificação. Uma vez construı́do, esse modelo

pode ser usado para, dado um novo documento d, realizarsua classificação, isto é, identificar qual o conjunto de classesmais adequado para associar a d. Nesse sentido, uma possı́velinterpretação da fase de geração do modelo de classificaçãoé a de que há um supervisor externo que, para cada docu-mento di em D, ensina ao algoritmo qual é a classificaçãocorreta de di. Por esse motivo, a classificação é então umatarefa que se encaixa na categoria de técnicas de aprendizadosupervisionado (supervised learning). Sendo assim, podemosdizer que métodos de classificação possuem uma fase inicial,denominada fase de treinamento. Nessa fase, o algoritmo declassificação é apresentado a exemplos (documentos) correta-mente classificados.

Há duas vantagens principais da abordagem baseada emaprendizado indutivo sobre a baseada em engenharia do con-hecimento. Em primeiro lugar, a primeira abordagem permitecriar classificadores mais precisos. Além disso, ela é tambémmenos cara e menos demorada. Entretanto, uma desvantagemda abordagem baseada em aprendizado indutivo é que suaaplicação pressupóe a existência de uma coleção de treina-mento rotulada, ou seja, de um conjunto de documentos, paracada um dos quais são conhecidas as classes correspondentes.

B. Variantes do problemaEm função das propriedades do conjunto de classes C

utilizado, há diversas variantes do problema de classificação.Esta Seção apresenta uma taxonomia que pode ser aplicadapara caracterizar determinado problema de classificação.

Em primeiro lugar, com relação à cardinalidade do conjuntoC, um problema de classificação pode ser binário ou n-ário.No primeiro caso, existem apenas duas classes no problemade classificação (i.e., |C| = 2). No segundo caso, existem nclasses em C, n > 2. Por vezes, pode ser conveniente doponto de vista prático tratar um problema de classificação n-ária como n problemas de classificação binária. Neste caso,cada tarefa de classificação binária resultante procura resolvero problema de gerar um modelo de classificação que permiteclassificar um documento novo como pertencente ou não auma classe, para todas as n classes.

Outra forma de categorizar problemas de classificação écom respeito aos eventuais relacionamentos entre os elementosde C. No primeiro caso, considera-se que não há relaçõesentre as classes, que essas relações são desconhecidas, ou quesão irrelevantes. No caso da existência de relações entre oselementos de C, o cenário mais comum é aquele em queesses elementos formam uma hierarquia de conceitos, unsmais especı́ficos, outros mais genéricos. Neste último caso,dizemos que estamos diante de um problema de classificaçãohierárquica. Como exemplo, citamos a hierarquia de conceitosdenominada MeSH. Cada conceito dessa hierarquia é usadopara rotular documentos da coleção PUBMED, composta deartigos da área médica. Em particular, os conceitos “Cheek”,“Chin” e “Eye” são casos particulares do conceito “Face”nessa hierarquia. Em problemas de classificação desta na-tureza, se um documento é associado a determinada classec, esse mesmo documento é indiretamente associado aosconceitos (classes) mais genéricos da hierarquia alcançaveisa partir de c.

48


Uma terceira forma de categorização de problemas declassificação diz respeito à quantidade de classes que estãoassociadas a cada documento em D. Nos problemas declassificação de única classe (single-class classification), cadadocumento em D está associado a apenas uma classe. Já nosproblemas de classificação multi-classes (multi-class classifi-cation), cada documento está associado a zero ou mais classes.

A seguir, resumimos a taxonomia das diferentes formaspelas quais um problema de classificação pode ser apresen-tado. Essa taxonomia é relativamente padronizada na literaturaacerca da tarefa de classificação. A lista abaixo apresentatambém os nomes originais utilizados na literatura estrangeira.

• Com relação à quantidade de elementos em C: binária(binary) versus n-ária (multi-way).

• Com relação à existencia de relações hierárquicas entre oselementos de C: não hierárquica (flat) versus hierárquica(hierarchical).

• Com relação à quantidade de classes associadas a cadadocumento em D: única classe (single-category) versusmulti-classes (multi-category)

As diversas variantes do problema de classificação descritasacima podem ser mescladas. Como exemplos, considere duascoleções de documentos que devem ser usadas para geração demodelos de classificação. A primeira coleção corresponde a di-versas mensagens de correio eletrônico, onde cada documentoestá associado a um e apenas um elemento do conjunto declasses C = {spam, não-spam}. Esse é portanto um problemade classificação binária de única classe. Outro exemplo é umacoleção de documentos em uma agência de notı́cias, onde cadaum deles está associado a uma ou mais classes no conjuntoC = {esportes, polı́tica, internacional}. Esse é portanto umproblema de classificação ternária multi-classes.

C. Passos da tarefa

A tarefa de classificação pode ser dividida em diversospassos. A seguir, resumimos os passos tı́picos que devem serrealizados para aplicação da tarefa de classificação sobre umacoleção de documentos. Vários desses passos são descritos emmaiores detalhes nas seções restantes deste Capı́tulo.

1) Definir o conjunto de classes e os potenciais relaciona-mentos entre elas. Esse passo envolve definir o conjuntoC de classes. Envolve também definir eventuais rela-cionamentos entre elementos desse conjunto, conformemencionado na Seção IV-B. Esse passo é dependente dodomı́nio da aplicação.

2) Rotular os textos (documentos). Este passo correspondea associar a cada documento em D um subconjunto deC. Normalmente, este passo é normalmente realizadopor especialistas (anotadores) com relação à coleção dedocumentos D. Se for feito manualmente, esse passo éde difı́cil realização, consome tempo, além de haver opotencial de inconsistência entre as decisões dos anota-dores. Entretanto, é também possı́vel que os documentosem D sejam previamente agrupados, para facilitar aatribuição de classes. Em [12], o leitor pode encontrauma descrição detalhada da tarefa de agrupamento dedocumentos.

3) Selecionar/Extrair caracterı́sticas a ser utilizadas pararepresentar os documentos da coleção. Esse passo cor-responde a aplicar técnicas de redução de dimensional-idade, conforme definido na Seção III-C. Na verdade,existem técnicas de redução de dimensionalidade es-pecı́ficas para a tarefa de classificação. Veja [13] paradetalhes.

4) Selecionar um método de classificação para treinar oclassificador. O objetivo da fase de treinamento na tarefade classificação produzir um modelo de classificaçãoatravés da observação de exemplos. Esse modelo declassificação, posteriormente, deve permitir classificarcorretamente documentos que não foram usados comoexemplos. Na Seção V, descrevemos diversos algorit-mos que podem ser usados para produzir modelos declassificação.

5) Avaliar o classificador. O objetivo de um algoritmode classificação é portanto inferir um modelo declassificação que permita associar documentos a zeroou mais das classes do conjunto C. Um aspecto im-portante a notar é que esse modelo de classificaçãoidealmente deve mapear de forma correta documentosnão contidos em D. Desta forma, para um documentonovo d, o classificador deve predizer (com um certograu de certeza) a classificação correta para d. Nessecontexto, é importante averiguar a qualidade do mod-elo de classificação gerado por um algoritmo, com oobjetivo de ter uma noção do quão efetivo será estemodelo quando for apresentado a documentos que nãoforam vistos durante a fase de treinamento. Usualmente,o modelo de classificação resultante da aplicação doalgoritmo deve ser validado com o uso de um con-junto de documentos que não foi utilizado na fase deaprendizado (treinamento). O objetivo de validar essemodelo é averiguar sua capacidade preditiva sobre doc-umentos não utilizados durante sua geração. Na SeçãoVI, descrevemos diferentes abordagens para avaliar aqualidade de um classificador.

6) Usar o classificador para para classificar novos docu-mentos. Um vez construı́do, o classificador ou mod-elo de classificação pode ser usado para predizer aclasse de novos documentos. Inclusive, esse modelo declassificação pode ser incorporado em um sistema deescopo mais amplo. Por exemplo, é comum em sistemasde correio eletrônico a existência de uma funcionalidadepara filtrar os chamados spams, mensagens de correioeletrônico que normalmente correspondem a conteúdode propaganda indesejável.

V. ALGORITMOS DE CLASSIFICAÇÃO

Um algoritmo de classificação toma como entrada ummapeamento da forma f : D → C. Essa função é ap-resentada explicitamente como um conjunto de documentosD e suas respectivas classes retiradas de um conjunto C. Apartir desse conjunto, o algoritmo então constrói um modelopreditivo (também chamado de modelo de classificação ouclassificador). De forma geral, um classificador é construı́do

49


através de um procedimento de treinamento no qual f éusada para inferir o modelo de classificação. Por esse motivo,denominamos f de conjunto de treinamento.

Uma vez construı́do, um modelo de classificação podeser usado na predição da classes (ou das classes) de novosdocumentos. A literatura sobre a tarefa de classificação ébastante rica em termos de algoritmos para geração dessesmodelos. Nas próximas seções, descrevemos três deles: Roc-chio, k-NN, Classificador Bayesiano. Por simplicidade, nessadescrição, consideramos que cada documento em D estáassociado a apenas uma classe. Consideramos também queo conjunto de classes é formado por m elementos, isto é,C = {c1, c2, . . . , cm}. Além disso, usamos a notação c(dj)para denotar um valor inteiro positivo correspondente à classe(i.e., o elemento de C) associada ao documento dj . Sendoassim, 1 ≤ c(dj) ≤ m. Outra notação utilizada é usar ~d paradenotar a representação vetorial (no sentido do modelo deespaço vetorial; veja a Seção III-A) do documento d ∈ D.

A. Algoritmo Rocchio

Esse algoritmo interpreta cada documento do conjunto detreinamento como um vetor no espaço n-dimensional. Maisespecificamente, a entrada para este algoritmo é uma matrizde termos por documentos, cuja construção é descrita naSeção III-A1. Dada essa matriz, o algoritmo Rocchio constróivetores representativos de cada uma das m classes definidasno conjunto de treinamento.

O vetor representativo dos documentos associados à classeci é da forma ~pk = (pk1, pk2, . . . , pkn), 1 ≤ k ≤ m. Cada ~pké chamado de vetor protótipo (prototype vector), e é definidocomo a média dos vetores correspondentes aos documentos daclasse ck. Sendo assim, o modelo de classificação produzidopor esse algoritmo corresponde a m vetores protótipos. OAlgoritmo 1 apresenta o procedimento de treinamento cor-respondente ao algoritmo Rocchio.

1: Entrada: conjunto de treinamento.2: Saida: {pk}, o conjunto de protótipos, 1 ≤ k ≤ |C|.3: m← |C|4: for k = 1 to m do5: ~pk ← (0, 0, . . . , 0)6: end for7: for all dj ∈ D do8: for k = 1 to m do9: if c(dj) = k then

10: ~pk ← ~pk + ~dj11: end if12: end for13: end for

Algoritmo 1: Rocchio - Fase de Treinamento

Uma vez criado um modelo de classificação através doAlgoritmo 1, podemos utilizá-lo para classificar um novodocumento d. A determinação da classe de um documentod é feita similaridade entre sua representação vetorial e osvetores protótipos. Mais especificamente, a similaridade entre~d e cada protótipo ~pk é calculada, e o protótipo mais similar

é determinado. Finalmente, a classe desse protótipo maissimilar é usada para classificar o documento d. O Algoritmo2 apresenta o algoritmo de classificação utilizado pelo métodoRocchio.

1: Entrada: d, documento a ser classificado.2: Saı́da: c, a classe inferida para d.3: m← |C|4: smax ← −∞5: for k = 1 to m do6: s← Similaridade(~d, ~pi)7: if s > smax then8: smax ← s9: c← ck

10: end if11: end for12: Retorne c

Algoritmo 2: Rocchio - Fase de Classificação

No Algoritmo 2, a linha 6 faz uso de uma função desimilaridade denominada Similaridade. Essa função tomadois vetores de mesma dimensionalidade e retorna um valornumérico que indica quanto esses vetores são similares. Noteque o conceito de similaridade usado aqui é o mesmo definidono Apêndice A, no qual apresentamos diferentes expressõespara cálculo de similaridades entre objetos.

B. Método k-NN: k vizinhos mais próximos

O algoritmo k-NN (k Nearest Neighbors) possui esse nomeporque ele determina a classe de um documento d com basenas classes dos documentos do conjunto de treinamento quesão vizinhos a d. O conceito de vizinhança entre documentos,fundamental para o funcionamento do k-NN, é definido atravésde uma função de similaridade, assim como no algoritmoRocchio.

Para classificar um documento d, esse método produz umaordem total sobre os documentos de D. Essa ordem totalpermite enumerar os documentos em D de acordo com asimilaridade de cada um em relação a d. A seguir, dado umnúmero inteiro k ≥ 1 fornecido como entrada, o algoritmopode determinar quais são os k documentos em D maissimilares a d. Por fim, as classes desses k vizinhos maissimilares são usadas para predizer a classe de d.

Para esclarecer a idéia básica do método k-NN, considere oexemplo descrito a seguir. A Figura 5 apresenta 16 pontoslocalizados em um espaço bidimensional. Neste exemplo,considere que esses pontos correspondem aos documentos doconjunto de treinamento. (Em uma situação real, entretanto, adimensionalidade do espaço seria 3 ou 4 ordens de grandezamaior, assim como também seria maior a quantidade dedocumentos envolvidos.) Note que, nessa figura, os pontos ouestão em branco ou em preto, o que indica as classes existentesno conjunto de treinamento.

Agora, considere a Figura 6, que apresenta o mesmo con-junto de treinamento da Figura 5 e, adicionalmente, um novoponto cuja classe desejamos determinar. Considerando que ovalor fornecido para k seja igual a 3, o k-NN toma esse novo

50


e ee e e ee e

uu u

u uu

u uFigura 5. Conjunto de treinamento fictı́cio de 16 elementos.

ponto e o utiliza como centro de uma circunferência que, porconta da distribuição dos objetos no espaço bidimensional,delimita 3 elementos do conjunto de treinamento. Neste ex-emplo, esses elementos são os vizinhos do ponto a classificar.A seguir, o k-NN contabiliza as quantidades das diferentesclasses dos pontos internos à circunferência para determinara classe do novo ponto. No exemplo, o k-NN classificaria onovo ponto como preto, visto que esta é a classe majoritáriadentre os vizinhos.

&%'$e e

e e e ee eu

u uu u

u

u ure

Figura 6. Na versão mais simples do k-NN, a classe do novo pontoé determinada pela classe majoritária dos pontos internos à circunferênciadefinida pelo valor de k = 3.

O exemplo apresentado acima ilustra o funcionamento davariante mais simples do k-NN, na qual os vizinhos sãoconsiderados independentemente de sua proximidade (similar-idade) maior ou menor em relação a d. Note, entretanto, que háoutras versões do k-NN que usam os vizinhos de d de formadiferente. Outra versão do k-NN é a que leva em consideraçãonão só os vizinhos em si, mas também o quanto eles estãopróximo de d. Para isso, a influência de cada vizinho sobrea classe prevista para d é ponderada pelas similaridades eles.A motivação para essa variante do k-NN é que, quanto maissimilar o vizinho, mais influência ele deve ter na determinaçãoda classe de d. A descrição e os algoritmos que seguem sãorelativos a essa segunda versão do k-NN.

Agora vamos formalizar o método k-NN na forma deum algoritmo que determine a classe de um documentonovo d. Em primeiro lugar, vamos definir a k-vizinhança (k-k-

vizinhançaneighborhood) de d como os k vizinhos mais próximos de d.Sendo assim, o Algoritmo 3 permite determinar a k-vizinhançade um documento d fornecido como entrada. Note mais umavez o uso da função Similaridade, que já tinha sido usada noAlgoritmo 2.

1: Entrada: D, conjunto de documentos; d, documento a serclassificado.

2: Saı́da: K, a k-vizinhança de d.3: for all dj ∈ D do4: sj ← Similaridade(dj , d)5: end for6: DSort ← lista de documentos em D ordenada por valores

decrescentes de sj7: K ← conjunto dos primeiros k documentos em DSort8: Retorne K.

Algoritmo 3: k-NN - Definição da k-vizinhança de d

Uma vez determinado K, o conjunto correspondente à k-vizinhança de um documento d, a classe desse documentopode ser determinada. Com esse objetivo, para cada ci ∈ C,devemos produzir estimativas de probabilidades condicionaisPr(ci|d), isto é, dado um documento d a ser classificado, oquão provável é de esse documento pertencer à classe ci.

Vamos então descrever como determinar essas estimativasde probabilidades utilizando a conjunto K. Primeiramente noteque a cardinalidade de K é k, por definição. Considere tambémque q(ci) é um número inteiro não-negativo que correspondeà quantidade de documentos de D que são da classe ci e queestão em K. Para calcular a estimativa para Pr(ci|d), bastaentão utilizar a Equação 8, definida a seguir.

Pr(ci|d) ≈q(ci)

k(8)

O passo final do método k-NN é utilizar as estimativas deprobabilidades obtidas com a aplicação da Equação 8 parainferir a classe do documento d. Isso é feito pela escolha daclasse c cuja estimativa de probabilidade é a maior dentretodas. Essa é a chamada classe majoritária (majority class) eé determinada pela expressão dada pela Equação 9.

c = arg maxci∈C

Pr(ci|d) (9)

Para entender a Equação 9, devemos primeiramente com-preender o operador arg max. De forma geral, esse operador operador

arg maxtoma um conjunto A qualquer e aplica uma função f : A→ Ba cada elemento desse conjunto, onde B ⊆


1: Entrada: d, documento a ser classificado; D, documentosdo conjunto de treinamento.

2: Saı́da: c, a classe inferida para d.3: K ← k-vizinhança de d, de acordo com o Algoritmo 3.4: for all ci ∈ C do5: q(ci) ← quantidade de documentos em K que per-

tencem à classe ci.6: Pr(ci|d)← q(ci)k (Equação 8)7: end for8: c← arg maxci∈C Pr(ci|d) (Equação 9)9: Retorne c

Algoritmo 4: k-NN - Fase de Classificação

Um aspecto importante acerca do k-NN é que não háuma fase de treinamento explı́cita, na qual um modelo declassificação é gerado, conforme vimos no método Rocchio(Seção V-A). No Rocchio, os documentos em D são usadosna fase de treinamento para a determinação dos prótotipos decada classe e não são necessários na fase de classificação. Jáno método k-NN, todos os documentos de D são mantidospara realizar a classificação de um documento novo. Outraforma de interpretar essa caracterı́stica é pensar que o modelode classificação no k-NN corresponde a todo o conjunto D.Isto é, a fase de treinamento do k-NN consiste apenas emarmazenar as representações vetoriais dos documentos em D.Por esse motivo é que se diz que o k-NN é um método deaprendizado tardio (lazy learning).aprendizado

tardio1) Valor do parâmetro k: Um parâmetro que deve ser

definido no método k-NN é justamente o valor de k, que deter-mina a quantidade de vizinhos a considerar na determinaçãoda classe de um documentos. Usar k = 1 é uma estratégiasujeita a erros. Isso porque o único vizinho escolhido tem opotencial de ser um exemplo atı́pico, o que pode acontecer emcaso em que há erros no conjunto de documentos usado notreinamento.

Uma estratégia mais robusta é utilizar um valor de k >1 exemplos mais similares e retornar a classe mais prováveldestes k exemplos. Nesse caso, tipicamente o valor escolhidoem problemas de classificação binária (veja a Seção IV-B) éı́mpar (para evitar empates durante a determinação da classemajoritária). Valores comumente utilizados na prática são k =3 ou k = 5.

C. Algoritmo C4.5

O C4.5 é um dos algoritmos mais tradicionais na tarefa declassificação. Esse método C4.5 procura abstrair uma árvorede decisão (decision tree) a partir de uma abordagem recursivaárvore de

decisão de particionamento da coleção D. Utiliza, para tanto, conceitose medidas da Teoria da Informação.

A fim de descrever o funcionamento do algoritmo C4.5,consideremos sua aplicação em um conjunto de documentosD representados de acordo com o modelo de espaço vetorial,e que o conjunto C = {c1, c2, . . . , cm} contém elementos quesão usados como classes dos documentos.

Uma árvore de decisão é um modelo de conhecimento (maisespecificamente, um modelo de classificação) em que cadanó não folha da árvore representa uma decisão sobre um

atributo que determina como os dados estão particionadospelos seus nós filhos. Inicialmente, a raiz da árvore representatoda a coleção D, com exemplos misturados das várias classes.Um predicado, denominado ponto de separação, é escolhidocomo sendo a condição que melhor separa ou discrimina asclasses. Tal predicado envolve exatamente um dos atributosdo problema e particiona o conjunto D em dois ou maissubconjuntos, que são associados cada um a um nó filho.Cada novo nó abrange, portanto, uma partição de D que, porsua vez, é recursivamente separada, até que o conjunto dedocumentos associado a cada nó folha consista inteiramenteou predominantemente de elementos de uma mesma classe.

Para ilustrar o funcionamento do algoritmo c4.5, considerea Tabela I, que apresenta uma coleção fictı́cia de documentosrepresentada em um espaço vetorial booleano. Observe queeste problema de classificação possui três classes: Polı́tica,Moda e Economia.

Partido Legenda PIB Real Classe1 1 0 0 Polı́tica1 0 0 1 Polı́tica0 0 0 1 Moda0 0 1 1 Economia0 0 1 1 Polı́tica

Tabela IEXEMPLO FICTÍCIO DE UMA COLEÇÃO DE DOCUMENTOS REPRESENTADA

EM UM ESPAÇO VETORIAL BOOLEANO.

A Figura 7 apresenta um esquema gráfico de uma árvorede decisão associada à coleção fictı́cia de documentos rep-resentada pela Tabela I. Nessa figura, observe os predicadosque indicam os critérios de separação dos dados em todosos nós não folha. Associado a cada nó folha encontra-se umsubconjunto do corpus cujos documentos satisfazem a todosos predicados pertencentes ao caminho que parte do nó raizaté o nó folha correspondente. Os documentos associadosa cada nó folha devem pertencer em maioria a uma únicaclasse de documentos. Quanto menor a diversidade de classesde documentos associados a um nó folha, maior a purezado referido nó. Existem medidas voltadas especificamente àaferição do grau de pureza/impureza de cada nó em árvoresde decisão como, por exemplo, o ı́ndice gini.

Figura 7. Exemplo de árvore de decisão em um corpus fictı́cio sobre notı́cias.

Na fase de construção da Árvore de Decisão, uma árvoreé gerada pelo particionamento recursivo dos dados de treina-mento. O conjunto de treinamento é separado em duas ou mais

52


partições usando restrições sobre os conjuntos de valores decada atributo. O processo é repetido recursivamente até quetodos ou a maioria dos exemplos em cada partição pertençama uma classe. A árvore gerada abrange todo o conjunto detreinamento e é construı́da em profundidade.

Há duas operações principais durante o processo deconstrução da árvore:(a) a avaliação dos pontos de separação de cada nó interno

da árvore e a identificação de qual o melhor ponto deseparação.

(b) a criação das partições usando o melhor ponto deseparação identificado para os casos pertencentes a cadanó

Uma vez determinado o melhor ponto de separação de cadanó, as partições podem ser criadas pela simples aplicação docritério de separação identificado.

Para avaliação dos pontos de separação de cada nó internoda árvore, as seguintes medidas devem ser calculadas:

• Ganho de informação considerando a partição da coleçãode documentos associada ao nó em análise. Observa-seque, para o nó raiz, a coleção de documentos correspondea D. Para este cálculo utiliza-se a fórmula abaixo querepresenta a entropia (ou complexidade) do conjunto dedocumentos considerando o atributo de classificação:

info(S) = −k∑

j=1

freq(Cj , S)|S|

log2freq(Cj , S)|S|

bits

(10)Onde:

– S representa a partição da base de dados;– freq(Cj , S) representa o número de vezes que a

classe Cj acontece em S;– |S| denota o número de casos do conjunto S;– k indica o número de classes distintas.

• Ganho de informação de cada atributo considerando apartição da base de dados associada ao nó em análise.Observa-se que, para o nó raiz, todos os atributos, comexceção do atributo de classificação, devem ser analisa-dos. Para este cálculo utilizam-se as fórmulas abaixosobre cada atributo:

infoX(T ) =n∑

i=1

|Ti||T |

info(Ti) bits (11)

Onde:– T representa a quantidade de ocorrências na partição

em análise;– Ti representa a quantidade de ocorrências de uma

classe contidas no conjunto T ;– n é o número de valores distintos do atributo X .

O cálculo do ganho de informação é expresso por:

gain(X) = info(S)− infoX(T ) (12)

Deve então ser selecionado para construção do nó da árvore,o atributo com maior ganho de informação obtido sobre apartição em análise.

Partido Legenda PIB Real Classe do Documento5 1 0 2 Polı́tica4 0 1 0 Polı́tica0 0 1 3 Moda1 1 3 7 Economia6 2 0 2 Polı́tica

Tabela IIEXEMPLO FICTÍCIO DE UMA BASE DE NOTÍCIAS REPRESENTADA EM UM

ESPAÇO VETORIAL CLÁSSICO.

É importante ressaltar que o processo de avaliação depontos de separação depende do domı́nio de cada atributo, quepode ser numérico ou categórico. No caso de classificação dedocumentos textuais representados em um espaço de vetores,todos os atributos são numéricos, uma vez que indicam afreqüência com que cada termo ocorre no documento. Noscasos em que os documentos são representados por vetoresbinários, os atributos podem ser considerados categóricos paraefeito de separação, uma vez que os valores possı́veis são ascategorias termo presente e termo ausente, conforme ilustradopela Tabela I.

O processo de avaliação dos pontos de separação de atrib-utos numéricos baseia-se em testes dicotômicos da formaA ≤ v, onde A é um atributo e v é um número real. Esteprocesso requer a ordenação dos exemplos de treinamentobaseado nos valores do atributo em análise. Por exemplo, se-jam v1, v2, ..., vn, valores ordenados de um atributo numéricoA. Como qualquer valor entre vi e vi+1 divide o conjuntonos mesmos dois subconjuntos, apenas (n− 1) possibilidadesde separação precisam ser analisadas. Tipicamente, o pontomédio entre vi e vi+1 é escolhido como ponto de separação.Pode ser observado, portanto, que o custo de avaliação dasseparações para um atributo numérico é dominado pelo custode ordenação dos valores.

O processo de avaliação dos pontos de separação deatributos categóricos baseia-se em testes sobre cada atributoindividualmente.

Em ambos os casos (atributos categóricos ou numéricos),os testes consistem em calcular o ganho de informaçãoassociado ao atributo correspondente. Este cálculo no casode atributos categóricos foi ilustrado acima. Consideremosagora um exemplo de cálculo de ganho de informação paraum atributo numérico. Suponhamos uma base de documentossimilar àquela da tabela I, representada na Tabela II. Estabase foi adaptada para atributos numéricos. Conforme jámencionado, nesta representação de espaço vetorial, cada valorindica o número de vezes que o termo correspondente ocorreno documento em questão.

Consideremos o cálculo do ganho de informação para oatributo referente ao termo Partido. Como este atributo énumérico, é necessário a avaliação dos pontos de separação afim de selecionar aquele que melhor particiona o conjunto dedocumentos. Para tanto, os valores são ordenados e os pontosmédios calculados, conforme mostra a tabela III. Esta mesmatabela mostra a condição associada a cada ponto médio,assim como o resultado do cálculo do ganho de informaçãoem cada situação. Assim, o melhor ponto de separação do

53


Pares Ponto Médio Predicado Ganho de Inf.0 e 1 0.5 Partido ≤ 0.5 0.7219281 e 4 2.5 Partido ≤ 2.5 0.9709514 e 5 4.5 Partido ≤ 4.5 0.4199735 e 6 5.5 Partido ≤ 5.5 0.170951

Tabela IIIPONTOS MÉDIOS DOS VALORES DO ATRIBUTO Partido E OS RESPECTIVOS

GANHOS DE INFORMAÇÃO.

atributo Partido, ou seja, o predicado que leva ao melhorganho de informação para o atributo Partido é Partido ≤ 2.5.Obviamente, um raciocı́nio análogo deve ser aplicado aosdemais atributos a fim de escolher qual deverá ser o atributoe a condição de separação a ser imposta na criação da árvorede decisão. A árvore de decisão parcialmente representada nafigura 8 ilustra o processo de construção da estrutura casoo maior ganho de informação estivesse associado ao atributoPartido.

Figura 8. Exemplo Parcial de Árvore de Decisão em um Corpus Fictı́ciosobre Notı́cias

A seguir encontra-se uma versão simplificada do AlgoritmoC4.5 para a fase de construção de árvores de decisão. Ela érecursiva, realizada em profundidade, e considera que cada nóda árvore gerada possui três informações:

• O nome do atributo associado• A sub-base correspondente• Uma lista de filhos

Cada nó da lista de filhos associada a um nó da árvore possui,por sua vez, duas informações:

• A raiz da sub-árvore associada• Um predicado envolvendo o atributo em questão e que

especifica a condição de seleção dos registros, defindo asub-base associada a sub-árvore

Convém ressaltar que o nó raiz da árvore recebe, no inı́ciodo processamento, a base de dados completa como subárvore.A versão do C4.5 descrita a seguir encontra-se subdividida emdois procedimentos (Algoritmo 5 e Algoritmo 6) e mostra oprocessamento a partir do nó raiz da árvore.

1: Entrada: D, o conjunto de treinamento.2: Saida: Árvore de decisão A.3: Raiz ← CriaNohArvore(D)4: ProcessaNohArvore(Raiz)5: ExibeArvore(Raiz)

Algoritmo 5: C4.5 - Fase de construção da árvore de decisão- Procedimento Principal

Quando a base de dados possui atributos ainda não processa-dos, a função BaseImpura() do passo 2 do Algoritmo 6 retornaverdadeiro ou falso dependendo do valor apurado a partir dealgum ı́ndice que calcule o grau de impureza da base. Quandoa base de dados não tem mais atributos diferentes do atributoobjetivo a serem processados, a função retorna falso. Nestecaso, conforme pode ser observado no passo 21, o algoritmoconsidera como classe o valor prevalente na referida base.

O procedimento do passo 5 do mesmo algoritmo executa ocálculo do ganho de informação apropriado em função do tipodo atributo (categórico ou numérico). Ainda com relação aoAlgoritmo 6, no passo 11, o procedimento particiona a base dedados em função dos predicados formados a partir dos valoresdo atributo com maior ganho de informação. Os elementos dalista de bases particionadas no passo 11 possuem, além dassub-bases, os predicados que levaram ao particionamento.

Conforme mostra o passo 21 do Algoritmo 6, caso abase de dados seja considerada suficientemente pura, ou nãotenha mais atributos a serem processados, o nó corrente éconsiderado um nó folha e o valor prevalente do atributoobjetivo nessa base é obtido e indicado para ser o rótulo daclasse correspondente.

1: Entrada: Nó raiz da subárvore Raiz.2: if BaseImpura(Raiz.SubBase) then3: MaiorGanho ← −∞4: for all Atb ∈ Raiz.SubBase do5: Gain ← CalcularGanhoInfo(Raiz.SubBase,Atb)6: if Gain > MaiorGanho then7: MaiorGanho ← Gain8: MelhorAtb ← Atb9: end if

10: end for11: Raiz.Atributo ← MelhorAtb12: lBases← ParticionarBase(MelhorAtb, Raiz.SubBase)13: for all B ∈ lBases do14: Filho ← CriaNohLista()15: Filho.Predicado ← MontaPredicado(MelhorAtb, B)16: Filho.SubArvore = CriaNohArvore(B)17: Inclui(Raiz.lFilhos, Filho)18: ProcessaNohArvore(Filho.SubArvore)19: end for20: else21: Raiz.Atributo ← ObterValorAtbObj(Raiz.SubBase)22: end if

Algoritmo 6: C4.5 - Fase de Construção da Árvore de Decisão- ProcessaNohArvore()

O processamento da árvore de decisão sobre um novodocumento a ser classificado consiste em percorrer a árvore,partindo do nó raiz em direção a um nó folha que estabeleçaa qual classe tal documento pertence. O caminho entre onó raiz e o nó folha é estabelecido na medida em que ospredicados associados aos nós não folha vão sendo satisfeitospelos atributos do documento a ser classificado.

Cabe ressaltar ainda a possibilidade de conversão de umaárvore de decisão para um conjunto de regras de classificação.Uma regra de classificação é uma regra de produção em que o

54


consequente estabelece uma classe a qual um novo documentodeverá pertencer, caso os atributos deste documento satisfaçamaos predicados estabelecidos no antecedente da regra.

D. Classificador Ingênuo de Bayes

O Classificador Ingênuo de Bayes (Naı̈ve Bayes Classifier),CIB, é um método de classificação baseado na Teoria dasProbabilidades. Mais especificamente, o Teorema de BayesTeorema

de Bayes (Bayes Theorem) desempenha um papel crı́tico nesse método.Dado um novo documento d a ser classificado, o CIB associaa d a classe mais provável dentre todas as classes possı́veis.Para realizar essa associação, o CIB segue um procedimentocomposto dos dois passos abaixo:

1) Gera uma estimativa da distribuição de probabilidadesposteriores para cada classe.

2) Associa a d a classe mais provável, com base nessadistribuição de probabilidades.

Vamos agora formalizar o procedimento realizado pelométodo CIB. Seja o conjunto de categorias C ={c1, c2, . . . , cm}. Seja d o documento a ser classificado. Paraclassificar d, o CIB calcula e avalia Pr(ci|d), para cada classeci ∈ C. O valor de Pr(ci|d) corresponde à probabilidade deo documento d pertencer à classe ci. Dessa forma, temos que∑

ci∈C Pr(ci|d) = 1, por definição. Se utilizarmos a definiçãode probabilidade concicional, obtemos uma expressão para ovalor Pr(ci|d), dada pela Equação 13.

Pr(ci|d) =Pr(ci, d)Pr(d)

(13)

Podemos utilizar o Teorema de Bayes para transformar aexpressão da Equação 13. (Deixamos como exercı́cio para oleitor a realização do algebrismo envolvido.) Quando fazemosisso, obtemos a expressão apresentada na Equação 14.

Pr(ci|d) =Pr(ci)× Pr(d|ci)

Pr(d)(14)

No CIB, a Equação 14 é calculada para cada classe ci, i =1 . . .m. Após esse cálculo, o método pode determinar a classemais provável para d. A classe mais provável de d, cmap, édada por:

cmap = arg maxci∈C

Pr(ci|d)

= arg maxci∈C

Pr(ci)× Pr(d|ci)Pr(d)

= arg maxci∈C

Pr(ci)× Pr(d|ci) (15)

Há duas transformações relevantes na Equação 15. Aprimeira é a eliminação do denominador Pr(d). Essatransformação simplifica os cálculos necessários e somenteé possı́vel porque Pr(d) é um valor constante e portanto oresultado retornado pelo operador arg max depende apenasde Pr(ci) × Pr(d|ci). A segunda transformação realizada naEquação 15 utiliza o Teorema de Bayes, conforme a Equação14.

De toda a discussão feita até aqui sobre o CIB, podemosconcluir que esse método precisa determinar estimativas para

as distribuições de probabilidades Pr(ci) e Pr(d|ci), a partirdos documentos do conjunto de treinamento. Portanto, vamosagora descrever de que forma essas estimativas podem serobtidas.

Primeiramente, vamos descrever o procedimento paraobtenção da estimativa para Pr(ci), denominada probabili-dade anterior (prior probability). É importante entender o probabilidade

anteriorsignificado do valor Pr(ci) para uma certa classe ci. Esse valoré a probabilidade de a classe de um documento escolhido aoacaso ser da classe ci. Sendo assim, se ni documentos em Dsão da classe ci, então podemos obter uma estimativa P̂r(ci)para Pr(ci) através da Equação 16.

Pr(ci) ≈ P̂r(ci) =ni|D|

(16)

O motivo pelo qual Pr(ci) é denominada probabilidade an-terior está relacionado ao fato de que, se não soubermos maisnada além da distribuição de probabilidade Pr(ci), i = 1 . . .m,podemos usar esses valores para determinar a classe maisprovável para d.

Agora vamos descrever a forma de produzir uma estimativapara a probabilidade Pr(d|ci), i = 1 . . .m. O significado destaprobabilidade é o seguinte: dentre todos os documentos daclasse ci, P (d|ci) corresponde à probabilidade de selecionarao acaso um documento com as mesmas caracterı́sticas ded, o documento que desejamos classificar. Nesse contexto,o método CIB interpreta um documento d a ser classificadocomo uma conjunção de |T | eventos binários, onde T é oconjunto de termos que compõe o léxico extraı́do de D. Ok-ésimo evento binário corresponde à ocorrência ou não dotermo tk no documento d. Dessa forma, podemos considerar dcomo um evento composto do |T | eventos binários, conformea Equação 17.

d = t1 ∧ t2 ∧ . . . ∧ t|T | (17)

De acordo com a Teoria das Probabilidades, e usandoa interpretação de d como um evento conjunto conformea Equação 17, podemos escrever a Equação 18 para obterPr(d|ci).

Pr(d|ci) = Pr(ci)×Pr(t1|ci)×Pr(t2|t1 ∧ ci)×Pr(t3|t1 ∧ t2 ∧ ci)×× . . .×Pr(t|T ||t1 ∧ t2 ∧ . . . ∧ t|T |−1 ∧ ci) (18)

De acordo com a Equação 18, Pr(d|ci) pode ser calculadopelo produtório de |T |+1 fatores. Portanto, para calcular umaestimativa para Pr(d|ci), devemos produzir estimativas paratodos os |T |+ 1 fatores envolvidos. Esse aspecto é um com-plicador, se considerarmos o custo computacional necessáriopara o cálculo desses fatores. Além disso, a quantidade dedocumento no conjunto de treinamento deve ser suficientepara que estimativas confiáveis possam ser produzidas. Nesseponto, o método CIB faz uma suposição sobre a dependência

55


existente entre os eventos e(t1), e(t2), e(t3), . . . , e(t1). Essasuposição facilita o cálculo da estimativa para Pr(d|ci), con-forme descrevemos a seguir.

A suposição que o CIB utiliza é considerar que os termos deum documento são condicionalmente independentes, dada aclasse ci. Isso quer dizer que, de acordo com essa suposição,o fato de um documento d conter um determinado termo t nãodiz nada acerca da probabilidade de d conter também outrotermo t

′. Dessa forma, a Equação pode ser significativamente

simplificada, o que resulta na Equação 19.

Pr(d|ci) = Pr(t1 ∧ t2 ∧ . . .∧ t|T ||ci) = Pr(ci)×|T |∏j=1

Pr(tj |ci)

(19)Note que a Equação 19 ainda contém |T |+1 fatores, assim

como na Equação 18. Entretanto, note também que a primeiraé uma simplificação da segunda, visto que, do terceiro aoúltimo fator da Equação 18, os termos foram removidos docondicionante. Essa simplificação facilita substancialmente oscálculos das estimativas de probabilidades, conforme descreve-mos a seguir.

Uma vez adotada a suposição de independência condicionalentre os termos, podemos descrever o procedimento paraobter estimativas para os fatores correspondentes às proba-bilidades condicionais da forma P (tj |ci). Suponha que há qiocorrências de termos nos documentos de D pertencentes àclasse ci. Considere ainda que qij corresponde à quantidadede ocorrências do termo tj entre as ni ocorrências anteriores.Então a estimativa p̂(tj |ci) pode ser obtida pela Equação 20.

Pr(tj |ci) ≈ P̂r(tj |ci) =qijqi

(20)

De posse da Equação 20, podemos definir uma expressãopara obter uma estimativa para Pr(d|ci), que denotamos porP̂r(d|ci). Essa expressão é apresentada na Equação 21.

Pr(d|ci) ≈ P̂r(d|ci) = P̂r(ci)×|T |∏j=1

P̂r(tj |ci) (21)

A suposição de independência condicional entre os termosde um documento certamente não condiz com a realidade. Porexemplo, em uma coleção de documentos, se sabemos que umdos documentos contém a palavra Hong, isso aumenta nossaexpectativa de encontrar a palavra Kong. Entretanto, apesar dea suposição adotada pelo CIB não refletir o que acontece emcoleções de documentos reais, experimentos mostram que essemétodo é efetivo na prática. Em [14], há uma explicação paraos bons resultados práticos obtidos com o método CIB.

1) Suavização de Laplace (Laplace Smoothing): Sabemosaté aqui que o cálculo das estimativas para as probabilidadesno método CIB é baseado em contagens de frequências sobrea coleção de treinamento D. Por exemplo, para obter aestimativa para as probabilidades anteriores p̂(ci), precisamosdeterminar com que frequência encontramos documentos emD que pertecem à classe ci. Esse valor pode ser diretamenteobtido pela Equação 16.

Entretanto, no cálculo das estimativas para as probabilidadescondicionais, há um complicador adicional: frequências iguaisa zero fazem com que a estimativa da probabilidade condi-cional seja igual a zero. Para ententer isso, perceba que bastaque um dos fatores da Equação 21 seja igual a zero para quetodo o produtório seja também igual a zero. Em particular, afreqüência qijqi é igual a zero quando o termo tj não ocorrenos documentos rotulados com classe ci (porque, neste caso,qij = 0 na Equação 20). Para prevenir a ocorrências defrequencias iguais a zero, devemos suavizar as estimativas.

De forma geral, o procedimento de suavizar uma estimativade probabilidade e significa adicionar a ela um pequeno valorpositivo δ, de tal forma que a nova estimativa é e + δ. Oresultado disso é que estimativas de probabilidade que sãoiguais a zero se tornam maiores que zero.

Uma das técnicas usadas para suavizar estimativas de prob-abilidades é a Suavização de Laplace (Laplace Smoothing). Suavização

deLaplaceQuando aplicada à Equação 20, essa técnica permite reescrevê-

la, conforme apresentado na Equação 22

P̂r(tj |ci) =qij + 1qi + |T |

(22)

Essa técnica pressupõe a observação de |ak| exemplosvirtuais, onde |ak| é a aridade (i.e., a quantidade de valorespossı́veis) do atributo previsor ak.

2) Transformação de produtório em somatório: Além daSuavização de Laplace, outro artifı́cio de implementação é nor-malmente utilizado no CIB. Considere novamente a Equação21. Repare que essa equação apresenta um produtório sobre osfatores P̂r(tj |ci). Do ponto de vista computacional, esse pro-dutório representa um complicador para o cálculo envolvido naEquação 21. Isso porque os valores P̂r(tj |ci) são normalmentemuito próximos de 0, o que faz com que o seu produtório sejaainda mais próximo de zero. Considerando que computadorespossuem uma capacidade finita para representação de númerosreais, isso pode levar a erros de aproximação do cálculodesejado.

Para contornar esse problema, utilizamos uma propriedadedo operador arg max e da função logarı́tmica f(x) = log(x),conforme descrito a seguir.

Primeiramente, note que a função log(x) é monotonica-mente crescente, o que significa que, se x1 ≥ x2, entãolog(x1) ≥ log(x2). Sendo assim, se aplicarmos a funçãologarı́tmica a cada elemento da lista passada como argumentopara o operador arg max, o resultado produzido por esseoperador permanece o mesmo. Ou seja:

arg maxci∈C

f(ci) = arg maxci∈C

log [f(ci))] (23)

Note também que podemos usar uma propriedade da funçãologarı́tmica segundo a qual o logaritmo de um produtório éigual ao somatório dos logaritmos. Como resultado, transfor-mamos o produtório da expressão original de cmap em umsomatório. Isso é vantajoso do ponto de vista computacional,visto que somas são menos sujeitas a erros de aproximaçãonumérica do que produtos. Esse desenvolvimento é apresen-tado na Equação 24.

56



P̂r(ci)×∏j

P̂r(tj |ci)

= arg max

ci∈Clog

P̂r(ci)×∏j

P̂r(tj |ci)

= arg max

ci∈C

log P̂r(ci) + log ∏j

P̂r(tj |ci)

= arg max

ci∈C

log P̂r(ci) + ∑j

log P̂r(tj |ci)

(24)

Pelo que foi descrito até aqui, podemos concluir que,de posse das estimativas P̂r(ci) e P̂r(tj |ci), a classe maisprovável de um documento d pode ser determinada pelaEquação 25.


log P̂r(ci) + ∑j

log P̂r(tj |ci)

(25)3) Algoritmos: Estamos agora em condições de apresentar

os algoritmos envolvidos no método CIB. O Algoritmo 7apresenta o procedimento de treinamento do CIB. Observeque as linhas 6 e 11 correspondem a aplicações das Equações16 e 20, respectivamente.

1: Entrada: Conjunto de treinamento D.2: Saı́da: Estimativas para Pr(ci) e Pr(tj |ci), i = 1 . . . |C|,

j = 1 . . . |T |.3: for all ci ∈ C do4: Di ← documentos em D pertencentes à classe ci5: ni ← |Di|6: P̂r(ci)← ni/|D|7: Ti ← união de todos os termos em Di8: qi ← quantidade de ocorrências de termos em Di9: for all tj ∈ Ti do

10: qij ← quantidade de ocorrências de tj em Di11: P̂r(tj |ci)← (qij + 1)/(qi + |T |)12: end for13: end for

Algoritmo 7: CIB - Treinamento

Para classificar um documento com o uso do CIB, aplicamoso Algoritmo 8.

1: Entrada: d, o documento a ser classificado.2: Td ← conjunto de termos do léxico que ocorrem em d.3: Retorne cmap, tal que

cmap = arg maxci∈C[log P̂r(ci) +

∑tj∈Td log P̂r(tj |ci)

]Algoritmo 8: CIB - Classificação

Documento Conteúdod1 Human machine interface for PARC com-

puter applicationsd2 A survey of user opinion of computer sys-

tem response timed3 The EPS user interface management systemd4 System and human system engineering test-

ing of EPSd5 Relation of user perceived response time to

error measurementd6 The generation of random, binary, ordered

treesd7 The int

Documents

A Tarefa de Classificaçao em˜ Text Mining · Eduardo Bezerra; Ronaldo Goldschmidt / Revista de Sistemas de Informacao da FSMA n. 5 (2010) pp. 42-62 estão associadas ao tipo