/Banco de dados

voltar
/Banco de dados

Data Mining na Prática: Classificação Bayesiana

PorMauro Pichiliani em

Olá pessoal. Nesta coluna vamos continuar nosso estudo sobre algoritmos de Data Mining.

Nesta semana veremos um algoritmo de classificação
supervisionada chamado Classificação Bayesiana.
Da mesma maneira que nos artigos anteriores, uma versão
simples do algoritmo será implementada em uma stored procedure
que pode ser executada no SQL Server 2000 e 2005.

Antes de começar a falar sobre o algoritmo, gostaria de dizer que vou procurar prestigiar o evento iMasters Intercon 2006 (http://www.imasters.com.br/intercon/2006/) que será realizado dia 28 de outubro em São Paulo. Quem estiver por lá e quiser dar uma palavrinha comigo é só me procurar no espaço reservado para os colunistas.

O algoritmo

O algoritmo de Classificação Bayesiana recebe este nome por ser baseado no teorema de probabilidade de Bayes. Também é conhecido por classificador de Naïve Bayes (sim, com um trema na letra i) ou somente algoritmo de Bayes.

O algoritmo tem como objetivo calcular a probabilidade que uma amostra desconhecida pertença a cada uma das classes possíveis, ou seja, predizer a classe mais provável. Este tipo de predição é chamada de classificação estatística, pois é completamente baseada em probabilidades.

Esta classificação também é chamada simples ou ingênua (também é possível encontrar o adjetivo idiota), pois ela considera que o efeito do valor de um atribuído sobre uma determinada classes é independente dos valores dos outros atributos, o que simplifica os cálculos envolvidos. Por falar em atributos, é bom deixar claro que a Classificação Bayesiana obtém melhores resultados quanto os valores dos atributos são discretos ao invés de contínuos. Talvez isso fique mais claro no exemplo que será visto logo mais.

Outra característica deste algoritmo é que ele requer um conjunto de dados prévio que já esteja classificado, ou seja, um conjunto que linha que já estejam separadas em classes (ou clusters). Baseado neste conjunto de dados prévio, que também é chamado de conjunto de treinamento, o algoritmo recebe como entrada uma nova amostra desconhecida, ou seja, que não possui classificação, e retorna como saída a classe mais provável para esta amostra de acordo com cálculos probabilísticos. Diferente do algoritmo K-Means visto na coluna anterior, a Classificação Bayesiana não necessita de uma métrica para comparar a ‘distância’ entre as instâncias e nem classifica a amostra desconhecida automaticamente, pois é necessário um conjunto de dados já classificados. Devido à esta necessidade considera-se o algoritmo de Classificação Bayesiana como um algoritmo de mineração de dados supervisionado.

Sem entrar em detalhes muito técnicos de como o algoritmo funciona, basta pensar que os quatro passos abaixo devem ser seguidos:

Passo 01: Cálculos das probabilidades das classes.

Neste passo, cada classe do conjunto de treinamento possui sua probabilidade calculada. Na maioria das vezes, trabalhamos com apenas duas classes como, por exemplo, uma classe que indica se um determinado consumidor compra ou não um produto baseado em características demográficas do consumidor. O cálculo é feito dividindo-se o número de instâncias de determinada classe pelo número total de instâncias do conjunto de treinamento.

Passo 02: Cálculo das probabilidades da amostra desconhecida.

Agora, cada valor de cada atributo da amostra desconhecida possui sua probabilidade calculada para cada possível classe. Este passo é onde o processamento mais ‘pesado’ do algoritmo ocorre, pois, dependendo do número de atributos, classes e instâncias do conjunto de treinamento, é possível que muitos cálculos sejam necessários para se obter as probabilidades.

É importante notar que este cálculo depende inteiramente dos valores dos atributos da amostra desconhecida, ou seja, da amostra que se deseja prever a classes. Supondo que existam k classes no conjunto de testes e m atributos conjunto de testes será necessário calcular k x m probabilidades.

Passo 03: Calcular a probabilidades da amostra desconhecida.

Neste passo, as probabilidades calculadas para os valores da amostra desconhecida de uma mesma classe são multiplicadas. Em seguida, o valor obtido é multiplicado pela probabilidade da classe calculada no Passo 01.

Com as probabilidades de cada classe calculadas, verifica-se qual é a classe que possui maior probabilidade para a amostra desconhecida. Com isso, o algoritmo termina retornando a classe que possui maior probabilidade de conter a amostra desconhecida.

Mais informações sobre a classificação Bayesiana podem ser obtidas nos links abaixo:

http://en.wikipedia.org/wiki/Na%C3%AFve_Bayes
http://www.devmedia.com.br/articles/viewcomp.asp?comp=2637

Vamos ver agora um exemplo prático da utilização do algoritmo de Classificação Bayesiana com os cálculos de probabilidades.

Exemplo de uso de algoritmo

Neste exemplo, vamos considerar que uma empresa financeira deseja prever se um cliente será inadimplente ou não. Para isso, a financeira deve levar em consideração a sua base histórica de clientes e alguns atributos. Para facilitar o entendimento do cenário e do modelo de dados vamos utilizar um conjunto de treinamento com quinze linhas e com quatro atributos. A figura 01 mostra o conjunto de treinamento que será utilizado neste exemplo, armazenado na tabela TB_FINANCEIRA.


Figura 01. Dados históricos de uma empresa financeira.

As colunas apresentadas na tabela da Figura 01 são descritas a seguir:

CODIGO_CLIENTE: Esta coluna possui um identificador inteiro seqüencial. Para o algoritmo esta coluna é opcional, mas ela ajuda a organizar as linhas de histórico da tabela.

SEXO: Esta coluna identifica o sexo do cliente. Pode assumir apenas os valores MASCULINO e FEMININO.

ESTADOCIVIL: Esta coluna traz informações sobre o estado civil do cliente. Pode assumir apenas os valores CASADO e SOLTEIRO.

ESCOLARIDADE: Esta coluna traz informações sobre a escolaridade do cliente. Pode assumir apenas quatro valores diferentes: ENSINO MÉDIO INCOMPLETO, ENSINO MÉDIO COMPLETO, SUPERIOR INCOMPLETO e SUPERIOR COMPLETO.

RENDIMENTOS: Esta coluna traz informações sobre a faixa salarial do cliente. Pode assumir apenas os valores UM SALÁRIO MÍNIMO, DOIS SALÁRIOS MINIMOS e ACIMA DE TRÊS SALÁRIOS MÍNIMOS.

INADIMPLENTE: Esta é a coluna que apresenta a classificação das amostras. Neste exemplo a classificação indica se o cliente é devedor, isto é INADIMPLENTE=SIM, ou se o cliente não é devedor, isto é INADIMPLENTE=NAO. Para facilitar a visualização, os clientes do conjunto de treinamento que são inadimplentes foram marcados em vermelho e os clientes que não são inadimplentes foram marcados em azul.

Vamos agora executar a Classificação Bayesiana para a amostra desconhecia. Com base nos dados históricos apresentados na tabela da Figura 01 deseja-se classificar por meio da Classificação Bayesiana a amostra desconhecida apresentada na apresentada na Figura 02.

Passo 01: Cálculos das probabilidades das classes.

Existem apenas duas classes, uma que indica que o cliente é devedor (INADIMPLENTE=SIM) e outra que indica que o cliente não é devedor (INADIMPLENTE=NÃO). Calculando as probabilidades das classes tempos:

Probabilidade INADIMPLENTE=SIM: 4/15= 0,2667
Probabilidade INADIMPLENTE=NÃO: 11/15= 0,7334

Passo 02: Cálculo das probabilidades da amostra desconhecida.

Para o primeiro atributo da amostra desconhecida SEXO=MASCULINO, vamos calcular a probabilidade de INADIMPLENTE=SIM:

Probabilidade de SEXO=MASCULINO e INADIMPLENTE=SIM: 2/4 = 0,5

E para o caso onde o cliente é masculino e não é devedor tempos:

Probabilidade de SEXO=MASCULINO e INADIMPLENTE=NAO: 4/11 = 0,3636

Para os demais valores dos atributos da amostra desconhecida, temos:

Probabilidade de ESTADOCIVIL=SOLTEIRO e INADIMPLENTE=SIM: 1/4 = 0,25
Probabilidade de ESTADOCIVIL=SOLTEIRO e INADIMPLENTE=NÃO: 6/11 = 0,5455

Probabilidade de ESCOLARIDADE= ENSINO MÉDIO INCOMPLETO e INADIMPLENTE=SIM: 1/4 = 0,25
Probabilidade de ESCOLARIDADE = ENSINO MÉDIO INCOMPLETO e INADIMPLENTE=NÃO: 4/11 = 0,3636

Probabilidade de RENDIMENTOS= UM SALÁRIO MÍNIMO e INADIMPLENTE=SIM: 1/4 = 0,25
Probabilidade de RENDIMENTOS = UM SALÁRIO MÍNIMO e INADIMPLENTE=NÃO: 4/11 = 0,3636

Passo 03: Calcular a probabilidades da amostra desconhecida.

Multiplicando as probabilidades da amostra desconhecida para o caso de INADIMPLENTE=SIM pela probabilidade de inadimplência calculada no PASSO 1 temos:

0,5 x 0,25 x 0,25 x 0,25 x 0,2667 = 0,0021

Multiplicando as probabilidades da amostra desconhecida para o caso de INADIMPLENTE=NÃO pela probabilidade de não inadimplência calculada no Passo 01, temos:

0,3636 x 0,5455 x 0,3636 x 0,3636 x 0,7334 = 0,0192

Como 0,0192 > 0,0021, o algoritmo classifica a amostra desconhecida como INADIMPLENTE=NÃO, ou seja, este novo cliente tem uma probabilidade maior de não se tornar devedor do que de se tornar inadimplente, de acordo com os dados históricos e a Classificação Bayesiana.

Para ajudar a classificar estes clientes, vamos utilizar uma implementação do algoritmo de Classificação Bayesiana que vai trabalhar com apenas vários atributos que possuem valores textuais. Esta implementação foi colocada na stored procedure ST_CLASSIFICA_B baseada em instruções SQL do dialeto T-SQL, linguagem padrão do SQL Server. Com algumas poucas mudanças, a stored procedure pode ser implementada em outros bancos de dados e também poderá receber outros tipos de atributos. Internamente, esta stored procedure utiliza a função de separação de dados chamada iter_charlist_to_table(), descrita no artigo “Empacotando e Desempacotando Dados” disponível aqui no iMasters no endereço abaixo:

http://www.imasters.com.br/artigo/4043/sql_server/empacotando_e_desempacotando_dados/

O primeiro parâmetro que deve ser passado para a procedure é o nome da tabela. O segundo parâmetro deve indicar a lista de colunas utilizadas na classificação, todas separadas por vírgula e dentro de uma string. O terceiro parâmetro indica a coluna que contém as classificações. O quarto parâmetro deve receber a lista de valores da amostra desconhecida separada por vírgula e na ordem dos atributos passados no segundo parâmetro. A Listagem 01 apresenta a chamada da stored procedure ST_CLASSIFICA_B de acordo com o exemplo da empresa financeira descrito acima.


Listagem 01. Execução da stored procedure ST_CLASSIFICA_B.

A Stored Procedure ainda possui um quinto parâmetro. Se este parâmetro for passado como 0, a stored procedure retorna as probabilidades de cada classe. Se o quinto parâmetro for passado como 1, a stored procedure retorna apenas a classificação da amostra desconhecida. A Listagem 02 apresenta a chamada à stored procedure com o uso do quinto parâmetro e o seu resultado.


Listagem 02. Execução da stored procedure ST_CLASSIFICA_B retornando a classificação.

Contudo, deve-se considerar alguns detalhes antes do uso da Classificação Bayesiana. É necessário que o conjunto de treinamento esteja correto e consistente, pois uma linha que apresente algum valor errado pode comprometer todo o resultado. Outra desvantagem do algoritmo é que, quando não existe uma instância com valor de um atributo, a probabilidade torna-se zero, o que impossibilita a classificação correta de certas amostras.

Para fazer o download do script contendo a stored procedure ST_CLASSIFICA, as demais funções e os dados de exemplo é só clicar aqui.

Um grande abraço e até a próxima coluna.

Deixe um comentário! 8

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Comentando como Anônimo

  1. Rapaz, gostei muito do artigo… se nas minhas aulas de probabilidade essa matéria fosse explicada de forma tão esclarecedora teria me dado muito bem.

    Obrigado pela contribuição, ajudou muuuito!!!

  2. Adorei seu artigo.
    Vai me ajudar muito no meu projeto de graduação, na qual irei utilizar esse método e o KNN para diagnóstico de doenças. :)

leia mais