Data Mining na Prática: Algoritmo K-Means

A idéia 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 centróides para cada uma das classes. Conforme o algoritmo vai iterando, o valor de cada centróide é refinado pela média dos valores de cada atributo de cada ocorrência que pertence a este centróide. Com isso, o algoritmo gera k centróides e coloca as ocorrências da tabela de acordo com sua distância dos centróides.

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 centróides.

Neste passo os k centróides 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 centróide qualquer para que o algoritmo possa iniciar seu processamento.

PASSO 02: Gerar uma matriz de distância entre cada ponto e os centróides.

Neste passo, a distância entre cada ponto e os centróides é calculada. A parte mais ‘pesada’ de cálculos ocorre neste passo pois se temos N pontos e k centróides 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 centróide da classe.

Aqui, os pontos são classificados de acordo com sua distância dos centróides de cada classe. A classificação funciona assim: o centróide que está mais perto deste ponto vai ‘incorporá-lo’, ou seja, o ponto vai pertencer à classe representada pelo centróide 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 centróides para cada classe.

Neste momento, os valores das coordenadas dos centróides são refinados. Para cada classe que possui mais de um ponto o novo valor dos centróides é 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 centróides.

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á.

O leitor que deseja obter mais informações sobre o algoritmo K-Means pode dar uma olhada no link abaixo e até fazer o download de outras implementações do algoritmo:

http://www.kdkeys.net/forums/3538/ShowPost.aspx

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 01.

Figura 01. Diagrama com as principais tabelas da base de dados NorthWind.

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 tabelas 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 01. O resultado desta consulta foi armazenado em uma tabela chamada PERFIL.

Listagem 01. Obtendo o perfil de cada cliente.

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 02 apresenta este gráfico gerado a partir dos dados da tabela PERFIL.

Figura 02. Gráfico de pontos mostrando a Quantidade de Pedidos x Total Gasto por cliente.

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 02 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 02 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 02 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.

Listagem 02. Chamada à stored procedure ST_KMEANS

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 02. Se o quinto parâmetro for passado como 1, a stored procedure retorna as coordenadas dos centróides de cada classe. A Listagem 03 apresenta a chamada à stored procedure com o uso do quinto parâmetro e o seu resultado.

Listagem 03. Execução da stored procedure ST_KMEANS com cinco parâmetros.

Notem que os pontos que definem os centróides 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 esta dados em um gráfico de pontos podemos visualizar mais facilmente a classificação dos clientes. Este gráfico é apresentado na Figura 03.

Figura 03. Classificação dos clientes de acordo com o algoritmo KMeans.

No gráfico da Figura 03 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 centróides 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 centróides 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 centróides fornecidos pelo algoritmo quando este recebe o valor 1 para o quinto parâmetro.