Mineração de dados - O pesadelo dos usuários

Esses dias estava tendo problemas com uma cliente fresca (pra variar): ao mudar o nome do produto, o permalink permanecia o mesmo e ela queria que fosse atualizado. Bem, se é permalink não é pra ser atualizado. Mas como cliente fresco é cliente fresco. Não tem como argumentar. Enfim.
Como solução, elaborei um algoritmo que gerasse o novo permalink e verificasse a similaridade com o antigo. Se fosse suficientemente diferente, a troca seria realizada para o novo.

Bem, aí é que entra a questão. Como calcular similaridade entre strings?

Essa questão é muito comum quando temos que comparar valores não numéricos. Como nomes, palavras, endereços, imagens, vídeos, etc. E é a questão primordial quando estamos lidando com mineração de dados.

Mineração de dados (ou data mining)

Esta área estuda a extração de informações a partir de grandes quantidades de dados. Ela é formada por um grande número de ferramentas e técnicas divididas em várias subáreas como agrupamentos, grafos, árvores de decisão, hipóteses, dendrogramas, regras, entre muitas outras.
Por exemplo, nós fazemos isso intuitivamente no nosso dia a dia ao lidar com pessoas. Montamos regras para lidar melhor com os outros a partir de padrões de comportamento que descobrimos (mesmo que inconscientemente) uns nos outros. Porém, é impossível para um ser humano analisar o comportamento de milhares ou milhões de pessoas uma a uma.
A mineração de dados surgiu junto com os grandes volumes de dados que temos hoje. Na internet praticamente qualquer pequeno website pode acumular ao longo do tempo grandes volumes de dados. E pode haver informações preciosas ali dentro. Porém, como é inviável analisá-las manualmente, é preciso encontrar formas automatizadas de cuidar disso. É aí que entra a mineração de dados.

Por de seu crescente uso, hoje fala-se muito de infração de privacidade na internet. (Se você não quer informações suas na internet não as coloque na internet.) A internet não é um ser mágico que fica com sondas te perseguindo e espionando só pra saber sobre coisas extremamente relevantes, como a que horas você foi ao banheiro...
Mas qual o interesse que as grandes empresas podem ter em saber tanto sobre os usuários? O interesse delas não está em saber sobre você diretamente. Elas querem esses dados para extrair padrões de consumo e comportamento. Assim podem direcionar melhor propagandas, vendas, promoções, ofertas, serviços, etc conforme o grupo de consumo em que conseguiram te classificar, por exemplo.

Os únicos problemas quanto a privacidade que podem ocorrer são quanto a você apresentar um comportamento completamente distinto do restante levado em conta. Ou melhor, sua privacidade vai ser violada se você for absolutamente distinto entre milhões/bilhões para que o sistema acabe gerando uma regra (grupo ou o que for a saída dele) exclusiva para você. Aí podemos dizer que sua privacidade está sendo violada por uma máquina que só está vendo dados a processar (é como reclamar que uma lâmpada está te observando).

A não ser que você seja um sheikh, rei, imperador, milionário, bilionário, etc empresa alguma vai querer saber sobre você como indivíduo. Talvez a seção de fofocas do jornal local, caso a cidade onde você mora seja bem pequena. Bem, se você for. É uma pessoa só. Não é necessário utilizar algoritmos avançados e desperdiçar poder computacional com isso. Praticamente qualquer um consegue fazer isso.

Para ilustrar um pouco o quanto a mineração de dados é utilizada, aqui vai uma pequena listas de websites/ferramentas que a utilizam:

• LastFM é uma rádio online. Porém, ela utiliza técnicas de inteligência artificial para montar o seu padrão de gosto musical. Além de usar tal informação para, através de mineração, direcionar propagandas, montar rádios direcionadas a grupos com gostos similares, etc. Pena que deixou de ser gratuita já faz um bom tempo. Era muito boa pra conhecer bandas novas de lugares desconhecidos.
• Google Analytics é um sistema que fornece armazena diversas informações sobre os usuários ao acessarem um website. Aqui no blog temos ele instalado e podemos ver várias informações que no futuro podemos usar para melhorar nosso conteúdo.
• Google é uma que dispensa comentários não é? Tudo nela de alguma forma é usado para direcionar as propagandas e produtos dela. Aliás, gostei desse sistema de refinamento de pesquisas deles baseado nas minhas pesquisas passadas. Sim, pode me fazer perder muito conteúdo relevante, mas ultimamente notei o oposto.
• Facebook é um dos monster supreme masters nessa área. Cada vez mais pede mais informações a seu respeito. Tudo nele tem alguma forma de mineração de dados por trás: as sugestões de amizades, de gostos, de páginas, de "curtirs", os tipos de informação que são enviadas no seu mural, os jogos que você joga, os aplicativos que usa, quanto tempo usa, de onde usa, etc.
• Telemarketing também usa mineração de dados. Por que você acha que entre tantas pessoas escolheram ligar logo para você? No telemarketing pobre e porco foi "sorte", mas no caso de grandes empresas é por você ter apresentado alguma característica apresentada por consumidores. Essa é uma das consequências mais irritantes do data mining, convenhamos.

Além de uma infinidade de lugares. Se você não sabia, bem, paciência. Mas é bom saber. Pois os jornais fazem estardalhaços para aquilo que vai dar audiência e a verdade não costuma dar muito audiência não. Fala-se muito do facebook, da google, violação de privacidade daqui e de lá. Mais em momento algum explicam como isso é feito. E nem que essa área surgiu na década de 90. Ou seja, já tem mais de 20 anos que a mineração de dados é usada e você nem sequer ouviu falar dela.

Bem, como exemplo de mineração de dados, vou colocar um caso de extração de regras de associação de compras em supermercados. Um dos usos mais antigos e clássicos de mineração de dados. Pois tenho alguns dados para mostrar pois fiz um trabalho sobre isso na faculdade (e acabo de encontrá-lo no meu computador).

Extração de regras de associação de carrinhos de compras

O trabalho (da faculdade) se tratava do seguinte: tínhamos uma base de dados de compras de um supermercado e deveríamos extrair regras de associação dali. Por exemplo, quem compra atum costuma comprar detergente também (não sei se isso é verdade). Para começar, tínhamos que tratar os dados do mercado, um arquivinho texto bem porco:

número de compras: 97875

maior compra tem 279 produtos

segunda maior compra tem 254 produtos

menor compra tem 1 produto (18899 compras)

13 ACHOCOVOMALTINE ACUCAR_CRISTALCUCAR ALL_BRAN_KELLOG_S AMACCOMFORT CAFE_CABOCLO FEIJAO_BROTO_LEGAL FOSFORO_GUARANY GOMA_POX IOGMOLICO LEITE_PARMALAT OLEO_MILHO_LIZA SCLIXO_SUPER_LIXO SHOUT_ELIMINA_ODORES
13 ALFACE_MIMOSA BARRA_DE_CEREAIS_UNIAO BISCNESTLE BISNAGUINHA_WICKBOLD CAFE_SERRA_DA_GRAMA CHOCNESTLE COCA_COLA MANTEIGA_VIGOR MINI_WAFER_NESTLE_PASSATEMPO NESTON_BARRA REQCATUPIRY REVISTA_PENSE_LEVE SUCO_MAGUARY
13 ALVBRILHANTE CAFE_CABOCLO CAFE_SERRA_DA_GRAMA CERA_POLWAX CHOCVISCONTI CIF FERMLACTEO_RICH FILTCHUVA_DE_PRATA_CERESER GFATERMTERMOLAR MOLHO_DE_ALHO_KITANO MOSTARDA_HEMMER PALMITO_ARUBA REVISTA_DIETA_JA
13 ACUCAR_DA_BARRA BISCNABISCO CIGARRO_FREE FILEZINHO_FRANGO_SADIA GOIABADA_PREDILECTA LEITE_PARMALAT OVINHO_DE_AMENDELMA_CHIPS OVOS_BRANCOS_KAMIMURA PAO_PANCO_LEITE QUEIJO_RALADO_TEIXEIRA_4_FORMAGGI SOBRECOXA_FRANGO_SADIA SOPA_KNORR SUCO_MAGUARY
13 ACHOCGAROTADA AZEITE_GALLO BATATA_RUFFLES CHAMPAGNE_ESPDE_PRATA COCA_COLA GOMET_S_DORI IOGDIETALAT IOGPARMALAT LEITE_NINHO LEITE_SAO_CARLOS RAID SALGCEBOLITOS VINHO_ST_GERMAIN
13 ALFACE_CRESPA ALFACE_MIMOSA_BIO_TERRA BISCNESTLE BISCTOSTINES CEREAL_NESTLE CLIGHT_CHA CREME_VEGBECEL FILE_PEITO_FRANGO_SADIA LEITE_SALUTE PAO_WICKBOLD_LIGHT QUEIJO_DANUBIO_MINAS SABJOHNSON_S TEMPLINGUANOTTO
13 ACUCAR_UNIAO BISCNABISCO BISCTOSTINES CERA_POLIFLOR CHOCNESTLE CONDSEDA FANTA LEITE_MOCA LYSOFORM MANDOLATE_CASEIRO_ITAL PAPEL_HIGPERSONAL SPO_ARIEL SHBIO
13 ACUCAR_UNIAO ARROZ_PRATO_FINO CLIGHT_CHA CLIGHT_DIET CROCK_PIZZA MANTEIGA_LECO NESTON_BARRA PAO_DE_QUEIJO_MINEIRO PAO_WICKBOLD_HAMBUGUER POP_CORN_YOKI QUEIJO_RALADO_TEIXEIRA_4_FORMAGGI TEMPLINGUANOTTO TORRADA_BAUDUCCO
...

Isso é só um trechinhozinho dos dados. Eram aproximadamente 98 mil compras, ou seja, 98 mil linhas de dados.

Bem, regras de associação simplesmente medem as chances de algo ocorrer dado que algo ocorreu. Ou seja, no caso, medem as chances de que um produto também vai ser comprado se um produto já foi. Por exemplo, uma regra bem famosa (nem sabemos se é verdade) é a de que homens que compram fraldas na sexta feira à noite também compram cerveja. Vale notar que são regras assimétricas, ou seja, quanto a essa regra ela é válida para os homens que vão para comprar fraldas, e não para os que vão para comprar cerveja: fralda implica em cerveja mas cerveja não implica em fralda.

Primeiro, tive que encontrar um algoritmo para fazer a comparação entre strings. Na época não achei muita coisa na net que me ajudasse. Não tive muito tempo pra pesquisar e nem pra ler todos os materiais que havia conseguido. Apenas encontrei uma referência na wikipédia que salvou minha pele ajudou bastante: Distância de Levenshtein.

Precisávamos elaborar um algoritmo que realizasse o clustering (vulgo agrupamento) de produtos iguais, mas de marcas diferentes. Por exemplo, leite da marca X e da marca Y eram tratados como produtos diferentes e queríamos que fossem tratados como um só. Para que pudéssemos analisar o produto em si, independente de marca.

Além de nos livrar de produtos muito comuns como Coca-cola que aparece em mais de 50% das compras. Depois de nos livrar dos produtos praga - eliminamos todos os que apareciam em mais de 20% das compras - começamos a gerar os grupos.
Como exemplo, um dos grupos obtidos, o grupo PAPEL:

PAPEL_HIGPERSONAL PAPEL_HIGNEVE PAPEL_ALUMROCHEDO PAPEL_HIGNICE PAPEL_HIGMIRAFIORI PAPEL_HIGCAMELIA PAPEL_HIGSUBLIME PAPEL_HIGPRIMAVERA PAPEL_ALUMROLITTO PAPEL_HIGFOFINHO PAPEL_HIGDUALETTE PAPEL_SULFITE_MAXCOTE_BCO_TILIBRA PAPEL_HIGGARDENIA PAPEL_MANTIGUITTO PAPEL_ALUMMASTER_PACK PAPEL_PBALA_FEST_LAR PAPEL_ALUMWYDA PAPEL_WYDA_MANTEIGA PAPEL_BALA_SEDA 

Para fazer as comparações entre strings, utilizamos a distância de Levenshtein, porém, fizemos algumas adaptações. Como acrescentar uma ponderação para favorecer o início dos termos. Já que notamos que na maioria dos produtos era ali onde estava a parte mais significativa dos nomes.
Para um produto entrar num grupo, era feita comparação entre o nome do produto e todos daquele grupo. Caso superasse um valor de similaridade mínima, seria inserido, caso não seria comparado com os próximos grupos até ser associado a um ou até ser criado um novo grupo para ele.

Com os grupos em mãos, pegamos a base de dados inicial e substituímos os nomes dos produtos pelo nome do grupo em que ele foi inserido descartando repetições. Aí, finalmente aplicamos o algoritmo apriori algumas dezenas de vezes e conseguimos algumas regras. Claro que, num trabalho elaborado em dois dias corridos de trabalho, não conseguimos descobrir nenhuma regra para revolucionar as vendas no mercado, mas encontramos algumas das quais não dá pra discordar. Veja:

#Significa: quem compra coco tambem compra leite (com 61,5% de chance)

LEITE <- COCO  (1.0, 61.5)
LEITE <- ACHOCTODDY  (1.1, 62.7)
LEITE <- ACHOCNESCAU  (2.7, 60.1)
PAPEL <- TOALHA LEITE  (1.1, 64.8)
LEITE <- FARTRIGO PAPEL  (1.1, 62.4)
LEITE <- FEIJAO PAPEL  (1.2, 61.3)
PAPEL <- SPO ACUCAR  (1.0, 64.7)
LEITE <- SPO ACUCAR  (1.0, 65.5)
LEITE <- SPO CAFE  (1.2, 60.7)
LEITE <- CREME SUCO  (1.0, 66.3)
LEITE <- CREME ACUCAR  (1.1, 69.9)
LEITE <- CREME CAFE  (1.1, 65.6)
LEITE <- CREME COCA  (1.3, 63.7)
LEITE <- CREME PAPEL  (1.4, 67.7)
LEITE <- CREME PAO  (1.9, 62.5)
LEITE <- SUCO ACUCAR  (1.1, 64.1)
LEITE <- SUCO CAFE  (1.2, 60.7)
LEITE <- ACUCAR PAO  (1.9, 60.1)

Conseguimos muitas outras, mas todas regras bobas. O que nos animou bastante, pois apesar de não serem resultados relevantes, foram resultados corretos.
Note os valores entre parenteses. O primeiro deles é do programa que usamos para extrair as regras, já o segundo diz com que frequencial percentual isso ocorre. Ou seja, quem compra LEITE, tem 61,5% de chances de comprar COCO. Quem compra PAPEL, 64,8% para comprar TOALHA e LEITE. E assim vai.



Com isso, podemos notar que a mineração de dados já deveria ser assunto pra conversa de "buteco" há muito tempo. Claro que ela não se restringe a só a técnica exibida aqui. Basicamente cria-se uma técnica diferente para cada problema diferente. Logo vou enviar um post sobre clustering (agrupamento de dados) que é uma das técnicas utilizadas no exemplo do mercado.


Espero que tenha gostado e que tenha sido de alguma utilidade. ;)


Fontes:
http://pt.wikipedia.org/wiki/Regras_de_associa%C3%A7%C3%A3o,
http://pt.wikipedia.org/wiki/Minera%C3%A7%C3%A3o_de_dados
e http://www.devmedia.com.br/data-mining-de-regras-de-associacao-parte-1/6533.