View
164
Download
4
Category
Preview:
DESCRIPTION
Datamining algorithm for classification
Citation preview
K-means
K-means no Data Mining
❏Classificação❏Regressão❏Descoberta de Regras de Associação❏Descoberta de Padrões Sequenciais❏Agrupamento (clustering)❏Detecção de Anomalias
Definição de Agrupamento
Dado um conjunto de pontos, cada tendo um conjunto de atributos, e uma métrica de similaridade entre eles, achar agrupamentos tal que:●Pontos similares entre si formam um agrupamento.●Pontos menos similares entre si são de diferentes
agrupamentos.
Agrupamento pode ser ambíguo
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.
●Baseada em análise e comparações entre os valores numéricos dos dados.
Métricas de Similaridade
●Distância Euclidiana (para atributos contínuos)
●Outras métricas específicas para cada problema.
Distância EuclidianaÉ a distância entre dois pontos, que pode ser provada pela aplicação repetida do teorema de Pitágoras.
Classes
O usuário deve fornecer quantidade de classes que ele deseja.
K-means
Agrupamento por K-means
●Cada grupo é associado a um centróide. (Ponto Central)
●Cada ponto é atribuído a um grupo com o centróide mais próximo.
Centroids Algorithm
Iteração dos centróides
K-means na prática
O departamento de marketing de uma 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.
Classificação
Dois atributos:●Quantidade de Pedidos●Total Gasto
●3 grupos = 3 centróides
● (Obs: Na vida real o algoritmo K-Means pode trabalhar com qualquer quantidade de atributos para classificar os valores.)
Como otimizar o K-means?
Passos do Algoritmo
Passo 1: Fornecer valores para os centróides.Passo 2: Gerar Matriz de Distância entre cada ponto e os centróides.Passo 3: Associar cada ponto para o centróide mais perto.Passo 4: Calcular os novos centróidesPasso 5: Repetir até que nenhum ponto seja associado para um centróide diferente.
Passos do Algoritmo
Passo 1: Fornecer valores para os centróides.Passo 2: Gerar Matriz de Distância entre cada ponto e os centróides.Passo 3: Associar cada ponto para o centróide mais perto.Passo 4: Calcular os novos centróidesPasso 5: Repetir até que nenhum ponto seja associado para um centróide diferente.
Passos do Algoritmo
Passo 1: Fornecer valores para os centróides.Passo 2: Gerar Matriz de Distância entre cada ponto e os centróides.Passo 3: Associar cada ponto para o centróide mais perto.Passo 4: Calcular os novos centróidesPasso 5: Repetir até que nenhum ponto seja associado para um centróide diferente.
Passos do Algoritmo
Passo 1: Fornecer valores para os centróides.Passo 2: Gerar Matriz de Distância entre cada ponto e os centróides.Passo 3: Associar cada ponto para o centróide mais perto.Passo 4: Calcular os novos centróidesPasso 5: Repetir até que nenhum ponto seja associado para um centróide diferente.
Passos do Algoritmo
Passo 1: Fornecer valores para os centróides.Passo 2: Gerar Matriz de Distância entre cada ponto e os centróides.Passo 3: Associar cada ponto para o centróide mais perto.Passo 4: Calcular os novos centróidesPasso 5: Repetir até que nenhum ponto seja associado para um centróide diferente.
Geração da Matriz de Distância
Se temos N pontos e k centróides teremos que calcular N x k distâncias neste passo.Ex: 20.000 registros no BD
5 grupos/centróides 100.000 cálculos por iteração
Passos do Algoritmo
Passo 1: Fornecer valores para os centróides.Passo 2: Gerar Matriz de Distância entre cada ponto e os centróides.Passo 3: Associar cada ponto para o centróide mais perto.Passo 4: Calcular os novos centróidesPasso 5: Repetir até que nenhum ponto seja associado para um centróide diferente.
Passos do Algoritmo
Passo 1: Fornecer valores para os centróides.Passo 2: Gerar Matriz de Distância entre cada ponto e os centróides.Passo 3: Associar cada ponto para o centróide mais perto.Passo 4: Calcular os novos centróidesPasso 5: Repetir até que nenhum ponto seja associado para um centróide diferente.
Associação dos pontos
Os pontos são classificados de acordo com sua distância dos centróides de cada classe.
O centróide que está mais perto deste ponto vai ‘incorporá-lo’.
Cada ponto precisa realizar uma verificação.
Passos do Algoritmo
Passo 1: Fornecer valores para os centróides.Passo 2: Gerar Matriz de Distância entre cada ponto e os centróides.Passo 3: Associar cada ponto para o centróide mais perto.Passo 4: Calcular os novos centróidesPasso 5: Repetir até que nenhum ponto seja associado para um centróide diferente.
Passos do Algoritmo
Passo 1: Fornecer valores para os centróides.Passo 2: Gerar Matriz de Distância entre cada ponto e os centróides.Passo 3: Associar cada ponto para o centróide mais perto.Passo 4: Calcular os novos centróidesPasso 5: Repetir até que nenhum ponto seja associado para um centróide diferente.
Passos do Algoritmo
Passo 1: Fornecer valores para os centróides.Passo 2: Gerar Matriz de Distância entre cada ponto e os centróides.Passo 3: Associar cada ponto para o centróide mais perto.Passo 4: Calcular os novos centróidesPasso 5: Repetir até que nenhum ponto seja associado para um centróide diferente.
Passos do Algoritmo
Passo 1: Fornecer valores para os centróides.Passo 2: Gerar Matriz de Distância entre cada ponto e os centróides.Passo 3: Associar cada ponto para o centróide mais perto.Passo 4: Calcular os novos centróidesPasso 5: Repetir até que nenhum ponto seja associado para um centróide diferente.
Passos do Algoritmo
Passo 1: Fornecer valores para os centróides.Passo 2: Gerar Matriz de Distância entre cada ponto e os centróides.Passo 3: Associar cada ponto para o centróide mais perto.Passo 4: Calcular os novos centróidesPasso 5: Repetir até que nenhum ponto seja associado para um centróide diferente.
É necessário utilizar informações das iterações anteriores. (dependência de dados)
K-means- Áreas de Maior ProcessamentoPasso 1: Fornecer valores para os centróides.Passo 2: Gerar Matriz de Distância entre cada ponto e os centróides.Passo 3: Associar cada ponto para o centróide mais perto.Passo 4: Calcular os novos centróidesPasso 5: Repetir até que nenhum ponto seja associado para um centróide diferente.
K-means usando MapReduce
Fonte:http://www.iterativemapreduce.org/samples.html
K-means MPI e OpenMP
http://users.eecs.northwestern.edu/~wkliao/Kmeans/
http://www.cse.buffalo.edu/faculty/miller/Courses/CSE633/Chandramohan-Fall-2012-CSE633.pdf
K-means com MPI
Consider N data points each of it is vector and P processors.
(1) Assign N/P data points to each processor.(2) Node 0 randomly choose K points and assigns them as cluster means and broadcast.
K-means com MPI
(3) In each processor for each data point find membership using the cluster mean.
(4) Recalculate local means for each cluster in each processor.
K-means com MPI
(5) Globally broadcast all local means for each processor find the global mean.(6) Go to step (3) and repeat until the number of iterations > 10000 or number of points where membership has changed is less than 0.1 %.
K-means com OpenMP
Consider N data points each of it vector and P threads.(1) Node 0 randomly choose K points as assign them ascluster means.(2) In each thread for each data point find membership using the cluster mean.
K-means com OpenMP
(3) Recalculate local means for each cluster in eachthread.(4) Globally broadcast all local means for eachprocessor and find the global mean.
K-means com OpenMP
(5) Find the global mean in each thread
(6) Go to step (2) and repeat until the number of iterations >10000 or number of points where membership has is less than 0.1 %.
MPI Results
MPI vs. OpenMP
Recommended