Algoritmos de clustering - algoritmo de deslocamento médio

Introdução ao algoritmo de desvio médio

Conforme discutido anteriormente, é outro algoritmo de agrupamento poderoso usado no aprendizado não supervisionado. Ao contrário do agrupamento K-means, ele não faz suposições; portanto, é um algoritmo não paramétrico.

O algoritmo de deslocamento médio basicamente atribui os pontos de dados aos clusters de forma iterativa, deslocando os pontos em direção à densidade mais alta de pontos de dados, ou seja, o centroide do cluster.

A diferença entre o algoritmo K-Means e o Mean-Shift é que posteriormente não é necessário especificar o número de clusters com antecedência porque o número de clusters será determinado pelos dados de escrita do algoritmo.

Trabalho de algoritmo de desvio médio

Podemos entender o funcionamento do algoritmo de agrupamento Mean-Shift com a ajuda das seguintes etapas -

  • Step 1 - Primeiro, comece com os pontos de dados atribuídos a um cluster próprio.

  • Step 2 - Em seguida, este algoritmo calculará os centróides.

  • Step 3 - Nesta etapa, a localização de novos centróides será atualizada.

  • Step 4 - Agora, o processo será iterado e movido para a região de maior densidade.

  • Step 5 - Por fim, ele será interrompido assim que os centróides alcançarem a posição de onde ele não pode se mover mais.

Implementação em Python

É um exemplo simples para entender como funciona o algoritmo Mean-Shift. Neste exemplo, vamos primeiro gerar um conjunto de dados 2D contendo 4 blobs diferentes e depois aplicar o algoritmo Mean-Shift para ver o resultado.

%matplotlib inline
import numpy as np
from sklearn.cluster import MeanShift
import matplotlib.pyplot as plt
from matplotlib import style
style.use("ggplot")
from sklearn.datasets.samples_generator import make_blobs
centers = [[3,3,3],[4,5,5],[3,10,10]]
X, _ = make_blobs(n_samples = 700, centers = centers, cluster_std = 0.5)
plt.scatter(X[:,0],X[:,1])
plt.show()
ms = MeanShift()
ms.fit(X)
labels = ms.labels_
cluster_centers = ms.cluster_centers_
print(cluster_centers)
n_clusters_ = len(np.unique(labels))
print("Estimated clusters:", n_clusters_)
colors = 10*['r.','g.','b.','c.','k.','y.','m.']
for i in range(len(X)):
    plt.plot(X[i][0], X[i][1], colors[labels[i]], markersize = 3)
plt.scatter(cluster_centers[:,0],cluster_centers[:,1],
    marker=".",color='k', s=20, linewidths = 5, zorder=10)
plt.show()

Resultado

[[ 2.98462798 9.9733794 10.02629344]
[ 3.94758484 4.99122771 4.99349433]
[ 3.00788996 3.03851268 2.99183033]]
Estimated clusters: 3

Vantagens e desvantagens

Vantagens

A seguir estão algumas vantagens do algoritmo de agrupamento Mean-Shift -

  • Não é necessário fazer nenhuma suposição de modelo como em K-means ou mistura gaussiana.

  • Ele também pode modelar os clusters complexos que possuem forma não convexa.

  • Ele só precisa de um parâmetro chamado largura de banda, que determina automaticamente o número de clusters.

  • Não há problema de mínimos locais como no K-means.

  • Nenhum problema gerado por outliers.

Desvantagens

A seguir estão algumas desvantagens do algoritmo de agrupamento Mean-Shift -

O algoritmo de deslocamento médio não funciona bem no caso de dimensão alta, onde o número de clusters muda abruptamente.

  • Não temos nenhum controle direto sobre o número de clusters, mas em alguns aplicativos, precisamos de um número específico de clusters.

  • Ele não pode diferenciar entre modos significativos e sem sentido.