Nesse tutorial vamos falar sobre um outro tipo de aprendizagem, a apredizagem não-supervisionada. Nesse tipo de aprendizagem vamos identificar informações relevantes dentro de um conjunto de dados, mas sem a presença de um componente externo para guiar o aprendizado. Lembre que no aprendizado supervisionado, o aprendizado era guiado por um "gabarito" que permitia avaliar se aquela predição era correta ou não. No aprendizado não-supervisionado, isso não acontece.
Essas técnicas são utilizadas quando o objetivo é encontrar padrões que auxiliem o entendimento dos dados. A partir de um conjunto de dados, o algoritmo de aprendizagem aprende a representar estes daddos a partir de algum critério de qualidade.
Existem 3 tarefas dentro do aprendizado supervisionado: (1) sumarização, (2) associação e (3) agrupamento. A primeira tem como objetivo encontrar uma descrição mais simples do conjunto de dados. A segunda tem por objetivo encontrar padrões frequentes de associações entre os atributos do dataset. E por fim, a terceira (foco deste tutorial) tem como função indetificar grupos nos dados a partir de alguma medida de similaridade entre os objetos.
Agrupamento (ou clusterização) tem como objetivo encontrar grupos (cluster) nos dados em que os objetos de cada grupo compartilham alguma característica ou propriedade relevante para o domínio do problema que está sendo estudado.
Fonte: Livro Inteligência Artificial - Uma abordagem de aprendizagem de máquina
Considerando um espaço de dimensão d, um cluster pode ser visto como uma coleção de objetos próximos ou que satisfazem alguma relação dentro deste espaço. Essa definição básica é bem intuitiva, mas formalizar este conceito não é uma tarefa tão simples, dada a grande diversidade de pesquisas e métodos relacionados a agrupamentos. Na verdade, isso depende muito do conjunto de dados e do objetivo da análise. No entanto, existem algumas definições de cluster como, por exemplo, um cluster bem separado é um cluster em que qualquer ponto desse conjunto esta mais próximo de todos os pontos do cluster em questão do que qualquer ponto em outro cluster. Podemos considerar também, um cluster baseado em centro, onde um ponto do cluster em questão está mais próximo ao centro do cluster do que ao centro de qualquer outro cluster. Um centro pode ser um centróide que é obtido a partir da média aritmética dos pontos do cluster.
Cada possível definição de cluster resulta em um critério de agrupamento que permite selecionar uma estrutura (ou modelo) para representar os clusters que melhor se ajuste a um determinado conjunto de dados. Cada algoritmo de agrupamento é baseado em um critério de agrupamento e usa uma medida de proximodade e um método de busca para encontrar uma estrutura ótima ou subótima que descreva os dados, de acordo com o critério de agrupamento adotado.
O critério de agrupamento também é outro fator que varia bastante. Estes critérios podem ser agrupados em três grandes categorias: (1) Compactação, (2) encadeamento ou ligação e (3) separação espacial. O critério de agrupamento é o principal aspecto que deve ser considerado em um algoritmo de agrupamento. Além disso, ele esta ligado a maioria das técnicas para avaliação dos resultados de um algoritmo deste tipo.
O algoritmo k-means trabalha com o critério de compactação. Esse tipo de critério priorizam clusters que possuem uma variação intracluster pequena. Normalmente, este tipo de algoritmo temdem a ser mais efetivos na descoberta de clusters esféricos e/ou bem sparados, mas podem não ter resultados tão expressivos para estruturas mais complexas.
Escolher um algoritmo para a tarefa de agrupamento não é simples e depende de uma profunda análise e interpretação dos resultados obtidos. A aplicação do algoritmo é apenas uma etapa dentro de todo processo de avaliação de um processo de agrupamento. Podemos dividir esse processo em várias etapas:
Existem vários algoritmos de clusterização. Podemos agrupá-los de acordo com o método usado para definir os clusters. Podemos dividi-los em algoritmos hierárquicos, particionais, baseados em grid e baseados em densidade. Existe um variedade muito grande de algoritmos que fogem o escopo desse tutorial. Para demonstrar o funcionamento de um desses algoritmos, vamos nos focar em um agoritmo particional conhecido como k-means.
O k-means (em geral, os algoritmos classificados como particionais) otimizam o critério de agrupamento utilizando uma abordagem iterativa. O primeiro passo consiste na criação de uma partição inicial. Em seguida, objetos são movidos entre os clusters com o objetivo de melhorar o valor do critério de agrupamento. Apesar de serem computacionalmente eficientes, esses algoritmos podem cair no chamado ótimo local.
O critério de agrupamento utilizado por esse tipo de algoritmo é o erro quadrático. Em outras palavras, o objetivo dessa técnica é obter uma partição que minimiza o erro quadrático dado um número fixo de clusters. Minimizar o erro quadrático, ou a variação dentro do cluster, implica em maximizar a variação entre os clusters. O erro quadrátrico para um agrupamento contendo $k$ clusters é dado por:
$E = \sum_{j=1}^k{\sum_{x_i \in C_j}{d(x_i,\bar{x}^{(j)})^2}}$
O objetivo desse tipo de agrupamento é encontrar uma partição contendo k clusters que minimiza esse valor de E, para um valor fixo de k. Isso é um problema NP-Hard, logo as abordagens apresentadas são aproximadas. Normalmente, os algoritmos utilizam uma abordagem gulosa que pode levar a um ótimo local.
O algoritmo a seguir mostra o funcionamento do k-means:
O k-means é sensível a escolha inicial dos centróidoes e da sua forma de atualização. Dependendo da escolha dos centróides, o algoritmo pode convergir para um ótimo local.
O pacote que possui os métodos de clusterização é o scikit.cluster. Existem diversos algoritmos com diversos propósitos dentro do pacote. A tabela a seguir resume bem esse conjunto de técnicas.
Fonte: http://scikit-learn.org/stable/modules/clustering.html#k-means
| Method name | Parameters | Scalability | Usecase | Geometry (metric used) |
|---|---|---|---|---|
| K-Means | number of clusters | Very large n_samples, medium n_clusters with
MiniBatch code |
General-purpose, even cluster size, flat geometry, not too many clusters | Distances between points |
| Affinity propagation | damping, sample preference | Not scalable with n_samples | Many clusters, uneven cluster size, non-flat geometry | Graph distance (e.g. nearest-neighbor graph) |
| Mean-shift | bandwidth | Not scalable with n_samples |
Many clusters, uneven cluster size, non-flat geometry | Distances between points |
| Spectral clustering | number of clusters | Medium n_samples, small n_clusters |
Few clusters, even cluster size, non-flat geometry | Graph distance (e.g. nearest-neighbor graph) |
| Ward hierarchical clustering | number of clusters | Large n_samples and n_clusters |
Many clusters, possibly connectivity constraints | Distances between points |
| Agglomerative clustering | number of clusters, linkage type, distance | Large n_samples and n_clusters |
Many clusters, possibly connectivity constraints, non Euclidean distances | Any pairwise distance |
| DBSCAN | neighborhood size | Very large n_samples, medium n_clusters |
Non-flat geometry, uneven cluster sizes | Distances between nearest points |
| Gaussian mixtures | many | Not scalable | Flat geometry, good for density estimation | Mahalanobis distances to centers |
| Birch | branching factor, threshold, optional global clusterer. | Large n_clusters and n_samples |
Large dataset, outlier removal, data reduction. | Euclidean distance between points |
Vamos trabalhar com o K-Means e o DBSCAN. Como exemplo, vamos aplicar os algoritmos a uma base de dados criada aleatoriamente. Detalhes do DBSCAN podem ser encontrados no artigo original do método ou neste link.
In [4]:
# Imports necessários
import numpy as np
from sklearn.cluster import KMeans
from sklearn.cluster import DBSCAN
from sklearn.datasets.samples_generator import make_blobs
from sklearn.preprocessing import StandardScaler
from sklearn import metrics
import matplotlib.pyplot as plt
In [5]:
# Criando a base de dados
centers = [[1, 1], [-1, -1], [1, -1]]
X, labels_true = make_blobs(n_samples=750, centers=centers, cluster_std=0.4,
random_state=0)
X = StandardScaler().fit_transform(X)
In [6]:
# Plotando a base de dados
colors = ["c.", "y.","r.","g.","b.","k."]
for i in range(len(X)):
plt.plot(X[i][0], X[i][1], colors[0], markersize = 10)
plt.show()
No K-Means precisamos informar o número de clusters em que os dados serão aplicados. Percebe-se que para utilizar o K-Means é necessário ter um conhecimento prévio do domínio para que se possa escolher um valor de k adequado.
In [14]:
kmeans = KMeans(n_clusters=4)
kmeans.fit(X)
centroids = kmeans.cluster_centers_
labels_kmeans = kmeans.labels_
for i in range(len(X)):
plt.plot(X[i][0], X[i][1], colors[labels_kmeans[i]], markersize = 10)
plt.scatter(centroids[:, 0],centroids[:, 1], marker = "*", s=150, linewidths = 2, zorder = 10)
plt.show()
Já o DBSCAN é um método onde não é necessário informar o número de clusters. O algoritmo encontra esse valor baseado nos parâmetros passados. No nosso exemplo, vamos passar dois parâmetros:
A variação destes parâmetros influenciam bastante no resultado de classificação.
In [8]:
dbscan = DBSCAN(eps=0.26, min_samples=10)
dbscan.fit(X)
labels_dbscan = dbscan.labels_
for i in range(len(X)):
plt.plot(X[i][0], X[i][1], colors[labels_dbscan[i]], markersize = 10)
plt.show()
Vamos avaliar a clusterização utilizando a métrica Silhouette Coefficient como descrita na documentação do Scikit-Learn.
If the ground truth labels are not known, evaluation must be performed using the model itself. The Silhouette Coefficient (sklearn.metrics.silhouette_score) is an example of such an evaluation, where a higher Silhouette Coefficient score relates to a model with better defined clusters. The Silhouette Coefficient is defined for each sample and is composed of two scores:
The Silhouette Coefficient s for a single sample is then given as:
$s = \frac{b - a}{max(a, b)}$
The Silhouette Coefficient for a set of samples is given as the mean of the Silhouette Coefficient for each sample.
Advantages
Drawbacks
In [15]:
print("Silhouette Coefficient for K-MEANS: %0.3f" % metrics.silhouette_score(X, labels_kmeans))
print("Silhouette Coefficient for DBSCAN: %0.3f" % metrics.silhouette_score(X, labels_dbscan))