Clustering

Os algoritmos de clustering são um exemplo de unsupervised learning, em que o conjunto de treino é constituído por observações de $D$ de variáveis, sem nenhum rótulo. O objetivo é agrupar as observações de acordo com a sua semelhança.

Os dois principais métodos de clustering geram centros do cluster, chamados centroids, que representam os pontos pertencentes a esse cluster. Dado que o número $K$ de clusters tende a ser muito mais pequeno do que o número de pontos, acabamos com uma representação comprimida do mesmo conjunto de dados.

K-Means Clustering

O conjunto de treino, $X = (x_1, x_2, ..., x_N)$, consiste em $N$ observações sem rótulos. O objetivo é agrupar estas observações em $K$ grupos distintos, chamados clusters. O modelo utiliza funções de distância, como a distância euclidiana representada abaixo, para agrupar as observações em clusters.

No final, obtemos $K$ conjuntos chamados clusters $(C_1, C_2, ..., C_K)$, em que onde o cluster $C_k$ agrupa todos os pontos mais próximos de $c_k$ do que todos os restantes centroids.

Obtemos também $K$ vetores chamados centroids $(c_1, c_2, ..., c_K)$, que correspondem ao valor médio dos pontos pertencentes ao cluster $C_k$.

Assim, podemos definir o erro da solução de clustering de forma intuitiva.

Derivando a expressão do erro, concluímos que os centroids que minimizam o erro são os pontos médios de cada um dos clusters.

Contudo, não podemos simplesmente calcular cada centroid. Primeiramente, temos de associar corretamente cada ponto a um cluster. Só aí o resultado anterior se torna válido. Para tal, é aplicado o algoritmo especificado na secção seguinte.

Algoritmo

É utilizado um processo iterativo, em que, inicializando os centroids com valores aleatórios, se associada cada ponto ao centroid mais próximo. De seguida, os novos centroids são calculados através da expressão anteriormente referida. O processo é repetido até se dar a convergência da solução.

Inicializar K centroids de forma aleatória;
do {
	Associar cada ponto x ao centroid mais próximo;
	Calcular os novos centroids;
}
until (|erro_novo - erro_velho| < threshold ou iterações máximas excedidas)

O clustering final vai depender da inicialização. O valor de $K$ foi assumido como sabido. Contudo, nem sempre sabemos qual o melhor valor de $K$. Assim, é usual realizar o algoritmo diversas vezes para diferentes valores de $K$, escolhendo o $K$ que produz o melhor resultado. Este método é bastante sensível a outliers e não é bom para descobrir clusters com formas não convexas, dado que apenas descobre clusters com simetria esférica.

EM Clustering

Este método descreve cada cluster como uma distribuição multi variada. Assim, cada observação tem uma probabilidade de pertencer a cada um dos clusters. Este é um método de soft clustering, em contraste como os métodos de hard clustering (como o método anterior), pois permite que cada observação pertence a mais do que um cluster. Este método permite também saber qual a forma do cluster.

Gaussian Mixture

Uma gaussian mixture é uma combinação de distribuição normais multivariada, em que cada uma destas tem um peso associado.

A partir desta expressão, e com recurso ao teorema de Bayes, chegamos à expressão do logaritmo da função de máxima verosimilhança.

Algoritmo

O algortimo consiste, então, em maximizar a função de log-verosimilhança, com respeito aos parâmetros dos vetores de médias, matrizes de covariância e mixing coefficientes. Este compreende 4 etapas.

Inicialização

Nesta etapa escolhe-se o número de clusters $K$ e inicializam-se os vetores de médias $\mu_k$ (geralmente com valores arbitrários), as matrizes de covariância $\Sigma_k$ (geralmente com o valor da matriz identidade) e os mixing coefficients $\pi_k$ (geralmente com o valor $\frac{1}{K}$, de modo a dar a mesma importância a cada cluster).

Expectation

Nesta etapa computa-se o valor de $P(c_k \mid x_i)$ para cada ponto $x_i$ e cada cluster $c_k$.

Pois $P(x_i)$ é invariante entre as componentes, podemos simplesmente calcular

e depois normalizar

Maximization

Cada observação $x_i$ contribui de modo a atualizar cada cluster $c_k$, através do parâmetro $\gamma_{ki}$.

Evaluate Maximum Likelihood

Nesta etapa avalia-se a função log verosimilhança e procura-se a convergência, repetindo o processo se necessário.

Avaliação

Existem várias métricas de validade que permitem avaliar uma solução de clustering. Os critérios externos necessitam de informação externa, como os rótulos das observações, enquanto que os critérios internos permitem avaliar a qualidade da solução sem precisar deste tipo de informação.

Purity

A purity é um medida externa que avalia quantos dos clusters contém apenas uma única classe ou rótulo. Considerando $C = {c_1, c_2, ..., c_k}$ como o conjunto de clusters e $L = {l_1, l_2, ..., l_g}$ como o conjunto de rótulos de cada uma das observações, definimos purity como indicado abaixo.

Esta medida vê-se enviasada para os casos em que $K = N$, pois cada cluster terá, obviamente, apenas uma obervação, pertencente a apenas uma classe.

Silhouette

Esta é uma medida interna que avalia a coesão (cada membro de um cluster deve estar tão próximo dos outros membros do mesmo cluster quanto possível) e a separação (os clusters devem estar distantes entre si). A medida é calculada para um objeto $x_i$ e tem em conta o valor $a$ que representa a distância média de $x_i$ aos pontos no mesmo cluster e o valor $b$ que representa o mínimo da distância média de $x_i$ aos pontos de um outro cluster.

Define-se a silhouette de um cluster como a média das silhouettes dos seus pontos e define-se a silhouette da solução de clustering como a média das silhouettes dos clusterings.