Como Cluster por vizinhos mais próximos em Análise Preditiva
Os vizinhos mais próximos é um simples algoritmo amplamente utilizado na análise preditiva para agrupar dados através da atribuição de um item para um cluster, determinando que os outros itens são mais semelhante a ele. Um uso típico do algoritmo vizinhos mais próximos segue estas etapas:
Derivar uma matriz de similaridade entre os itens no conjunto de dados.
Esta matriz, referido como o matriz de distância, manterá os valores de similaridade para cada item no conjunto de dados. (Estes valores são elaborados em detalhe no exemplo seguinte.)
Com a matriz no lugar, comparar cada item no conjunto de dados para todos os outros itens e calcular o valor de similaridade.
Usando a matriz de distância, examinar cada item para ver se a distância para os seus vizinhos é inferior a um valor que você definiu.
Este valor é o chamado limite.
O algoritmo coloca cada elemento em um cluster separado, analisa os itens, e decide quais itens são semelhantes, e adiciona itens semelhantes para o mesmo cluster.
O algoritmo pára quando todos os itens foram examinados.
Considere-se, um conjunto de dados de oito localizações geográficas onde as pessoas vivem. O objectivo consiste em dividir estes indivíduos em grupos com base nas suas localizações geográficas, tal como determinado pelo sistema de posicionamento global.
Este gráfico mostra um conjunto de dados simples de dados geográficos dos indivíduos. Suponha que todos os dados recolhidos sobre estes oito indivíduos foram coletados em um ponto específico no tempo.
| ID individual | GPS - Longitude Geográfica | GPS - Latitude Geográfica |
|---|---|---|
| 1 | 2 | 10 |
| 2 | 2 | 5 |
| 3 | 8 | 4 |
| 4 | 5 | 8 |
| 5 | 7 | 5 |
| 6 | 6 | 4 |
| 7 | 1 | 2 |
| 8 | 4 | 9 |
Tal como acontece com K-means, o primeiro pré-passo é calcular os valores de similaridade para cada par de indivíduos. Uma maneira para calcular a semelhança entre dois itens é para determinar a distância Euclidiana. O valor de similaridade entre dois pontos é calculado como mostrado anteriormente.
Semelhança entre Item A e Item B =
# 8730- (fum, 1 - fb, 1)2 + (fum, dois - fb, 2) 2+ # 133- + (fa - fb, n) 2
aqui fum, 1 é a primeira característica do item A, fum, dois é a segunda característica do item A, e os valores correspondentes rotulados b representam as características do item B. A variável n é o número de características. Neste exemplo, n é 2. Por exemplo, a semelhança entre o número 1 e número 2 é calculada como se segue:
Semelhança entre ponto 1 e Item 2 = # 8730- (2-2)2 +(10-5) 2 = 5
Com base desta medida de similaridade entre os itens, você pode usar o algoritmo do vizinho mais próximo para extrair os clusters do conjunto de dados de localizações geográficas.
O primeiro passo é colocar o indivíduo cujo ID é 1, longitude é 2, e latitude é 10 em C1 cluster. Em seguida, passar por todos os indivíduos restantes computação quão similar cada um é para o indivíduo em C1.
Se a semelhança entre Individual 1 e outro Individual x é inferior a 4,5, então Pessoa x irá juntar-se C1 caso contrário, você criar um novo cluster para acomodar Individual x.
A seguir mostra as semelhanças e as relações numéricas entre os indivíduos de 1 a 8. A semelhança entre esses elementos de dados é calculado como uma distância euclidiana.
Indivíduos com valores de similaridade mais próximo de 0 têm maior similaridade. Metade da matriz não é preenchida, porque a matriz é simétrico.
| # Individual 1 | Pessoa # 2 | Pessoa # 3 | Individual # 4 | Individual # 5 | # Indivíduo 6 | Individual # 7 | Individual # 8 | |
|---|---|---|---|---|---|---|---|---|
| # Individual 1 | 0 | 5 | 6 | 3.6 | 7,07 | 7,21 | 8,062 | 2.23 |
| Pessoa # 2 | 0 | 6,8 | 4,24 | 5 | 4.12 | 3.16 | 4,47 | |
| Pessoa # 3 | 0 | 5 | 1.41 | 1.41 | 7,28 | 6,40 | ||
| Individual # 4 | 0 | 3.31 | 4.12 | 7,21 | 1.41 | |||
| Individual # 5 | 0 | 1.41 | 6,70 | 5 | ||||
| # Indivíduo 6 | 0 | 5,38 | 5,38 | |||||
| Individual # 7 | 0 | 7,61 | ||||||
| Individual # 8 | 0 |
Você tem agora atribuído Individual 1 do primeiro cluster (C1). A semelhança entre o indivíduo e uma individual 2 é igual a 5, o qual é maior do que o valor limiar de 4,5. Um novo cluster é gerada - e Individuais 2 pertence a ele. Nesta fase, você tem dois cachos de um item cada: C1 = {1} individual e C2 = {Individual 2}.
Mover o foco para Individual 3, você acha que a semelhança entre Individual 3 e Individuais 2 1 é maior do que o valor limiar de 4,5. Assim que você atribui Individual 3 para um novo cluster que contém um item: C3 = {3} Individual.
Movendo-se para Individual 4, você calcular como semelhante Individual 4 é indivíduos 1, 2 e 3. O mais próximo (mais semelhante) para Individual 4 passa a ser individual 1. A semelhança entre 4 e 1 é de aproximadamente 3,6, que é inferior a o valor limiar de 4,5.
Individual 4 junta Individual 1 em C1 Cluster.
Em seguida está a examinar Individual 5 e calcular como ele é similar aos indivíduos 1, 2, 3 e 4. O item mais próximo da distância (mais semelhante) para individual 5 é individual 3. A semelhança é # 8730-2, que é menor do que o valor limite de 4,5. Assim Individual 5 junta C3.
Quando você examinar Individual 6 e calcular como ele é similar aos indivíduos 1, 2, 3, 4 e 5, você descobre que o indivíduo 3 é mais próxima (mais semelhante) para Individual 6. Assim Individual 6 junta C3.
Quando você examinar Individual 7 e calcular como ele é similar aos indivíduos 1, 2, 3, 4, 5 e 6, você achar que o (mais semelhante) o artigo mais próxima de 7 Individual é individual 2. Assim Individual 7 junta C2.
Quando você examinar Individual 8, e calcular sua semelhança com indivíduos 1, 2, 3, 4 e 5, você achar que o (mais semelhante) o artigo mais próximo Individual 8 é individual 4. Assim Individual 8 junta C1.
Os aglomerados construídos até agora, contendo itens mais semelhantes um ao outro, são
C1 = {Individual 1, Individual 4, Individual 8}
C2 = {Individual 2, 7 Individual}
C3 = {Individual 3, Individual 5, Individual 6}