Data Mining na Prática: Algoritmo K-Means

Olá pessoal, nesta coluna vamos continuar nosso estudo sobre algoritmos de Data Mining. Veremos como utilizar um algoritmo clássico de classificação (clustering) para segmentação de dados de acordo com categorias. Uma versão simples do algoritmo será implementada em uma stored procedure do SQL Server 2000, de maneira semelhante à a regressão linear implementada na coluna anterior.

O algoritmo

A ideia do algoritmo K-Means (também chamado de K-Médias) é fornecer uma classificação de informações de acordo com os próprios dados. Esta classificação, como será vista a seguir, é baseada em análise e comparações entre os valores numéricos dos dados. Desta maneira, o algoritmo automaticamente vai fornecer uma classificação automática sem a necessidade de nenhuma supervisão humana, ou seja, sem nenhuma pré-classificação existente. Por causa desta característica, o K-Means é considerado como um algoritmo de mineração de dados não supervisionado.

Para entender como o algoritmo funciona, vamos imaginar que temos uma tabela com linhas e colunas que contêm os dados a serem classificados. Nesta tabela, cada coluna é chamada de dimensão e cada linha contém informações para cada dimensão, que também são chamadas de ocorrências ou pontos. Geralmente, trabalha-se com dados contínuos neste algoritmo, mas nada impede que dados discretos sejam utilizados, deste que eles sejam mapeados para valores numéricos correspondentes.

Como foi dito, o algoritmo vai analisar todos os dados desta tabela e criar classificações. Isto é, o algoritmo vai indicar uma classe (cluster) e vai dizer quais linhas pertencem a esta classe. O usuário deve fornecer ao algoritmo a quantidade de classes que ele deseja. Este número de classes que deve ser passada para o algoritmo é chamado de k e é daí que vem a primeira letra do algoritmo: K-Means.

Para gerar as classes e classificar as ocorrências, o algoritmo faz uma comparação entre cada valor de cada linha por meio da distância. Geralmente utiliza-se a distância euclidiana para calcular o quão ‘longe’ uma ocorrência está da outra. A maneira de calcular esta distância vai depender da quantidade de atributos da tabela fornecida. Após o cálculo das distâncias o algoritmo calcula centroides para cada uma das classes. Conforme o algoritmo vai iterando, o valor de cada centroide é refinado pela média dos valores de cada atributo de cada ocorrência que pertence a este centroide. Com isso, o algoritmo gera k centroides e coloca as ocorrências da tabela de acordo com sua distância dos centroides.

Para simplificar a explicação de como o algoritmo funciona vou apresentar o algoritmo K-Means em cinco passos:

• PASSO 01: Fornecer valores para os centroides: Neste passo os k centroides devem receber valores iniciais. No início do algoritmo geralmente escolhe-se os k primeiros pontos da tabela. Também é importante colocar todos os pontos em um centroide qualquer para que o algoritmo possa iniciar seu processamento.
• PASSO 02: Gerar uma matriz de distância entre cada ponto e os centroides: Neste passo, a distância entre cada ponto e os centroides é calculada. A parte mais ‘pesada’ de cálculos ocorre neste passo pois se temos N pontos e k centroides teremos que calcular N x k distâncias neste passo.
• PASSO 03: Colocar cada ponto nas classes de acordo com a sua distância do centroide da classe: aqui, os pontos são classificados de acordo com sua distância dos centroides de cada classe. A classificação funciona assim: o centroide que está mais perto deste ponto vai ‘incorporá-lo’, ou seja, o ponto vai pertencer à classe representada pelo centroide que está mais perto do ponto. É importante dizer que o algoritmo termina se nenhum ponto ‘mudar’ de classe, ou seja, se nenhum ponto for ‘incorporado’ a uma classe diferente da que ele estava antes deste passo.
• PASSO 04: Calcular os novos centroides para cada classe: neste momento, os valores das coordenadas dos centroides são refinados. Para cada classe que possui mais de um ponto o novo valor dos centroides é calculado fazendo-se a média de cada atributo de todos os pontos que pertencem a esta classe.
• PASSO 05: Repetir até a convergência: o algoritmo volta para o PASSO 02 repetindo iterativamente o refinamento do cálculo das coordenadas dos centroides. Notem que desta maneira teremos uma classificação que coloca cada ponto em apenas uma classe. Desta maneira dizemos que este algoritmo faz uma classificação hard (hard clustering) uma vez que cada ponto só pode ser classificado em uma classe. Outros algoritmos trabalham com o conceito de classificação soft onde existe uma métrica que diz o quão ‘dentro’ de cada classe o ponto está.

Vamos ver agora um exemplo prático da utilização do algoritmo K-Means.

Exemplo de uso de algoritmo

Neste exemplo vamos considerar que uma determinada empresa vende produtos para clientes por meio de pedidos compostos por itens de pedidos. Para facilitar o entendimento do cenário e do modelo de dados vamos utilizar a base de dados de exemplo Northwind do SQL Server 2000. O diagrama de entidades com as tabelas que nos interessa é apresentado na Figura 1.

A tabela que contém os itens de pedidos se chama Order Details e possui uma chave primária composta nas colunas OrderID e ProductID. Existem duas chaves estrangeiras na tabela Order Details, sendo que a primeira chave estrangeira relaciona a coluna ProductID da tabela de produtos chamada Products com a coluna ProductID da tabela Order Details. A segunda chave estrangeira relaciona a coluna OrderId da tabela de pedidos chamada Orders com a coluna OrderId da tabela Order Details. O modelo ainda apresenta a tabela de clientes Customers relacionado à tabela de pedidos Orders por meio das colunas CustomerID presente em ambas as tabelas.

Com base neste modelo, o departamento de marketing da empresa deseja segmentar os clientes para poder oferecer descontos diferenciados e outros benefícios. A segmentação dos clientes deve dividir todos os clientes da base de dados em três categorias: Clientes Ouro, Clientes Prata e Clientes Bronze. O critério de classificação dos clientes deve levar em consideração apenas duas variáveis: o total de pedidos de cada cliente e a quantidade total gasta pelo cliente em todos os pedidos, sem considerar descontos. Obviamente os clientes que possuírem mais pedidos e o maior valor gasto serão classificados como Clientes Ouro.

Com base nestas informações, inicialmente vamos calcular o total de pedidos para cada cliente e a quantidade gasta pelo cliente em todos os pedidos por meio da consulta apresentada na Listagem 1. O resultado desta consulta foi armazenado em uma tabela chamada PERFIL.

Com os dados armazenados na tabela PERFIL um gráfico de pontos foi gerado no Excel com a Quantidade de Pedidos x o Total Gasto. A Figura 2 apresenta este gráfico gerado a partir dos dados da tabela PERFIL.

Para classificar os dados da tabela PERFIL de acordo com o que o departamento de marketing deseja podemos utilizar o algoritmo K-Means. Como especificado somente dois atributos, Quantidade de Pedidos e Total Gasto, serão utilizados para classificar os clientes. Na vida real o algoritmo K-Means pode trabalhar com qualquer quantidade de atributos para classificar os valores.

Analisando os dados da Figura 2 podemos ver claramente que três clientes serão classificados como Clientes Ouro, pois fica fácil de ver a distância entre estes clientes e os demais. Porém não fica fácil a classificação dos demais clientes em Clientes Prata e Clientes Bronze.

Para ajudar a classificar estes clientes vamos utilizar uma implementação do algoritmo K-Means que vai trabalhar com apenas dois atributos. Esta implementação foi colocada na stored procedure ST_KMEANS 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 mais de dois atributos para a classificação.

Para tornar mais modular o algoritmo, a implementação do cálculo da distância entre os pontos foi feita na função DIST(), que deve ser criada antes da stored procedure. A Listagem 2 apresenta a chamada da stored procedure ST_KMEANS para o exemplo da tabela PERFIL. O primeiro parâmetro que deve ser passado para a procedure é o nome da tabela, seguido pelos parâmetros dos atributos. O quarto parâmetro indica qual é a quantidade de classificações que o algoritmo deve utilizar (clusters). A Listagem 2 apresenta os 23 primeiros pontos classificados de acordo com o algoritmo K-Means, colocando-os os em ordem de acordo com a classe a que pertencem.

No resultado apresentado pela stored procedure a coluna X equivale ao valor da primeira coluna passada como parâmetro, que no nosso exemplo é QTD_PEDIDOS, e a coluna Y equivale ao valor da segunda coluna passada como parâmetro, que no nosso exemplo é QTD_GASTA.

A Stored Procedure ainda possui um quinto parâmetro. Se este parâmetro não for passado a stored procedure retorna os dados classificados como na Listagem 2. Se o quinto parâmetro for passado como 1, a stored procedure retorna as coordenadas dos centroides de cada classe. A Listagem 3 apresenta a chamada à stored procedure com o uso do quinto parâmetro e o seu resultado.

Notem que os pontos que definem os centroides de cada classe não existem no conjunto de pontos iniciais.

No nosso exemplo, o algoritmo classificou os dados em três classes: classe 1, 2 e 3. De acordo com a definição do tipo de cliente a classe 1 equivale ao Cliente Bronze, a classe 2 equivale a Cliente Prata e a classe 3 equivale ao Cliente Ouro. Colocando estes dados em um gráfico de pontos podemos visualizar mais facilmente a classificação dos clientes. Este gráfico é apresentado na Figura 3.

No gráfico da Figura 3 os clientes representados pela cor amarelo escuro (triângulo) são aos Clientes Ouro, os clientes de cor cinza (quadrado) são os Clientes Prata e os clientes de cor amarelo claro (losango) são os Clientes Bronze. Os três pontos em preto indicam os centroides calculados pelo algoritmo

Com a utilização do algoritmo pode-se classificar os clientes existentes de acordo com sua Quantidade de Pedidos e Total Gasto em todos os pedidos, da maneira que o departamento de marketing desejou. Para classificar de um novo cliente basta executar novamente a stored procedure e verificar qual é a sua classificação. Desta maneira, todos os clientes serão novamente analisados e re-classificados.

Como alternativa pode-se comparar os dados de um novo cliente aos dados dos centroides antes de incluir o cliente na tabela. Esta comparação é feita por meio da distância entre os valores do novo cliente e os valores dos centroides fornecidos pelo algoritmo quando este recebe o valor 1 para o quinto parâmetro.