Clustering“Uma técnica de Data Mining para

agrupamentos de dados segundo seu grau de semelhança.”

- Wikipedia

Fernando Machado fm@fmachado.com http://twitter.com/fmachado

Agenda

• Por que este tema?• Data Mining

– Exemplos de casos reais– Processo de descoberta de conhecimento

(KDD)• Clustering

– Algoritmo K-means

Por que Clustering?

• Primeiros contatos– 1999 a 2002

• Extração de notícias da web– Versões até 2002

• Supervisão humana permanente• Manutenção constante• Alta taxa de erros• Falhas na arquitetura

Por que Clustering?

• Extração de notícias da web– Versão 2009 - ...

• Supervisão humana mínima– Exceto no início onde houve treinamento

• Manutenção mínima– Infraestrutura

• Taxa de erros < 5%– Inteligência Artificial básica

• Escalável e alto desempenho– Horizontal e vertical

– Seach-engine alta performance

www.guianews.com.brem 02/dez/2000

www.guianews.com.brem 19/mar/2010

Afinal, o que ée para que serve

Clustering?

Afinal, o que ée para que serve

ClusteringData Mining?

Data Mining

É o processo de descoberta

automática de informações úteis

em grandes depósitos de dados.

Data Mining

Grandes depósitosde dados?

Quão grande sãoesses depósitos?

Data Mining

Yahoo! Groups40 TB de dados para indexar

Data Mining

Possui aproximadamente 19 PB de dados transferidos através de sua rede a cada dia

1 petabyte = 1.024 terabytes19 petabytes = 19.456 terabytes

Data Mining

• Em maio de 2009, o Brasil chegou à 157.501.813 acessos no Serviço Móvel Pessoal (...).

• A Vivo ainda lidera o mercado com 29,38% de participação (...).

• Como a Vivo faz para identificar tendências ou o comportamento de seus ~45.675.525 clientes?

Data Mining

• Atua sobre grandes bancos de dados;

• Visa descobrir padrões úteis e recentes;

• Envolve estatística ealgoritmos sofisticados;

Data Mining – Padrões?

• Esta é uma compra fraudulenta?

• Que tipo de produto devo oferecer para este cliente?

• Como as mudanças nas sequências do DNA de um indivíduo afetam o risco do desenvolvimento de novas doenças?

Data Mining

• Data mining é uma parte integral da descoberta de conhecimento em banco de dados (KDD);

• KDD Knowledge Discovery in Database– Processo geral de conversão de dados brutos

em informações úteis.

Afinal, o que ée para que serve

Clustering?

Clustering

• Uma técnica de Data Mining para agrupamentos de dados segundo seu grau de semelhança.

• Você consegue identificar visualmente agrupamentos?

Clustering

Clustering

Clustering

Clustering

Clustering

• Em Data Mining, uma das atividades obrigatórias é o pré-processamento.

• Verificação dos dados:– Ignorar registros errados?

• É possível alguém ter filhos aos 10 anos de idade?• É possível que ela esteja trabalhando nesta

empresa? – Que valores adotar quando um atributo não

estiver preenchido?

Clustering

Visualmente é fácil?Vamos ver usando matemática...