Cluster espectral em python
O que é agrupamento?
O agrupamento é um problema de aprendizado de máquina não supervisionado, no qual é preciso dividir as observações "M" em clusters "k", com pontos no mesmo cluster sendo extremamente semelhantes e pontos em aglomerados diferentes sendo muito diferentes. Problemas como segmentação de clientes, sistemas de recomendação, detecção de anomalia, etc., são resolvidos de agrupamento. Você pode estar familiarizado com o algoritmo de agrupamento K-Means, no qual não temos rótulos e devemos colocar cada ponto de dados em seu cluster. O método de agrupamento espectral é usado para atingir o mesmo objetivo que o método de agrupamento K-Means, mas com uma abordagem baseada em gráfico. A imagem abaixo mostra os três clusters separados um do outro e têm pontos semelhantes juntos.
O que é agrupamento K-Means?
O cluster de K-Means envolve a identificação dos clusters K do conjunto de dados que são distintos um do outro. Somente variáveis independentes são usadas para criar clusters. K significa que o agrupamento é um algoritmo de aprendizado sem supervisão. Os pontos de dados no mesmo cluster são bastante semelhantes, enquanto os pontos de dados em aglomerados diferentes são muito distintos. Você começa com K Centros Random e atribui itens aos que estão mais próximos. O centro de cada coleção é então recalculado, resultando em novos centros K. Você continua fazendo isso até que o número de iterações atinja um limiar predeterminado ou o centro de aglomerados, mal se move. O método do cotovelo é comumente usado para determinar o valor de k.
Classificação vs. Clustering
Classificação é o resultado da aprendizagem supervisionada, o que significa que você deseja que o sistema gere um rótulo conhecido. Por exemplo, se você construiu um classificador de imagem, diria: "Este é um cachorro, este é um gato", com base em amostras de cães e gatos que você mostrou.
O agrupamento é a conseqüência do aprendizado sem supervisão, o que implica que você viu muitas amostras, mas não recebeu rótulos para eles. Por exemplo, podemos usar o cluster para segmentar os clientes do mesmo tipo dos clientes de diferentes tipos. Esta é uma declaração de problema amplamente usada que é resolvida usando clustering.
O que é o algoritmo de cluster espectral?
O agrupamento espectral é um algoritmo moderno de agrupamento baseado na teoria dos gráficos. Ele superou várias abordagens clássicas de agrupamento e ainda está evoluindo. Este algoritmo toma cada ponto de dados como um nó do gráfico e usa particionamento de gráficos para resolver o problema de agrupamento.
Trabalho de agrupamento espectral
Criando uma estrutura de dados do gráfico
Você pode visualizar qualquer conjunto de dados como uma nuvem de pontos, com m aponta n dimensões. Você pode fazer um gráfico desses pontos, com os nós sendo os pontos e as bordas (representadas por c) sendo ponderado por quão semelhantes os pontos são. Depois de termos nossos dados na forma de um gráfico, podemos gerar uma matriz de adjacência simplesmente inserindo o peso da borda entre os nós "i" e "j" em cada coluna da matriz. Isto é um m x m Matriz simétrica. C é o nome da matriz de adjacência.
Projetando os dados
Nesta etapa, os dados são projetados em um espaço inferior dimensional para tornar os pontos mais próximos um do outro no espaço dimensional inferior. A fórmula fornece o grau de cada nó:
A matriz de grau é então calculada usando a fórmula:
O Laplaciano do Gráfico pode ser calculado usando a fórmula L = D-W. Podemos calcular o espectro desta matriz, ou seus vetores próprios dispostos de mais significativos a menos importantes, agora que temos o Laplacian do gráfico. Tomar os autovetores de "K" menos significativos fornecem uma representação de cada nó no gráfico nas dimensões "K", que representa cada ponto no conjunto de dados. Os menores valores próprios estão relacionados aos autovetores menos significativos. Este é um tipo de redução de dimensionalidade que não é linear.
Agrupando os dados
Esta etapa implica principalmente agrupar os dados dimensionais reduzidos usando o agrupamento K-Means ou qualquer outra técnica de cluster clássica. O gráfico normalizado matriz Laplacian é atribuído a cada nó. Os dados são então agrupados usando qualquer método padrão.
Em um cenário ideal, você prevê que seus dados não estivessem totalmente conectados, com componentes conectados distintos para cada cluster. No entanto, na prática, este raramente é o caso: depende de várias coisas, incluindo os dados em si e como você cria seu gráfico de adjacência. Em termos de eficiência, os melhores clusters são separados, quanto mais cluster espectral se comporta previsivelmente: o gráfico terá mais de um componente conectado (idealmente K, o número de clusters no conjunto de dados), os primeiros k auto -valores serão zero e executando K-Means in the Space criado, tomando os primeiros k auto-vetores do gráfico Laplacian produzirá resultados bastante satisfatórios. Quanto mais próximos os aglomerados, mais distantes os valores próprios são de 0, e mais próximos os pontos no espaço próprio são de aglomerados distintos.
K-Means vs. Cluster espectral
Considere os dados fornecidos abaixo.
Mesmo quando o verdadeiro número de clusters k é conhecido pelo algoritmo, o K-Means falhará em agrupar os dados acima com sucesso. Isso ocorre porque o K-Means é um bom algoritmo de agrupamento de dados para encontrar grupos globulares como os abaixo:
onde todos os membros do cluster estão próximos um do outro (no sentido euclidiano). Abordagens de agrupamento de gráficos, como agrupamento espectral, por outro lado, não agrupam pontos de dados diretamente em seu espaço de dados nativo, mas, em vez disso, construa uma matriz de similaridade com o (i, j)º linha representando alguma distância de similaridade entre o iº e jº Pontos de dados no seu conjunto de dados.
De certa forma, o agrupamento espectral é mais geral (e poderoso) que o K-Means, pois o agrupamento espectral é aplicável sempre que K-means não estiver (basta usar uma distância euclidiana simples como medida de similaridade). No entanto, o oposto não é verdadeiro. Ao escolher uma dessas estratégias em detrimento da outra, há algumas preocupações práticas a serem lembradas. A matriz de dados de entrada é fatorada com K-means, enquanto a matriz Laplaciana é fatorada com agrupamento espectral (uma matriz derivada da matriz de similaridade).
Implementando agrupamento espectral usando Python
Importando as bibliotecas
de Sklearn.cluster importar espectralclusteringimportar numpy como np
Lendo os dados
X = np.Array ([[1, 1], [2, 1], [1, 0],
[4, 7], [3, 5], [3, 6]])
Observe que, neste exemplo, pegamos os dados com menos dimensões. Se você tiver dados dimensionais maiores, pode aplicar a análise de componentes principais (PCA) para reduzir as dimensões dos dados.
Inicializando nosso modelo
Model = SpectralClustering (n_clusters = 2,atribui_labels = 'discretize',
Random_state = 0).ajuste (x)
Obtenha rótulos de cada ponto de dados
Imprimir (modelo.Rótulos_)Saída
Array ([1, 1, 1, 0, 0, 0])Vantagens do agrupamento espectral
- O agrupamento espectral não assume a forma dos dados. Ele tem um bom desempenho em todos os tipos de distribuições de dados. Outros algoritmos clássicos, como K-means, assumem a forma de dados como esféricos.
- Funciona muito bem quando as relações são aproximadamente transitivas (como similaridade).
- Não precisamos de todo o conjunto de dados para cluster; Apenas uma matriz de similaridade/distância, ou talvez apenas a Laplaciana, será suficiente.
Desvantagens do agrupamento espectral
- Os autovetores de computação são o gargalo; Portanto, é caro para conjuntos de dados realmente grandes.
- Não funciona bem com conjuntos de dados barulhentos.
- O número de clusters (k) precisa ser decidido com antecedência.
Usar casos de agrupamento espectral
- Segmentação de imagem
- Segmentação do cliente
- Resolução da entidade
- Sequências de proteínas Cluster Spectral
Conclusão
Vimos como podemos usar o cluster espectral para agrupar nossos pontos de dados. Primeiro, projetamos os pontos de dados em uma estrutura de dados gráficos, reduzimos as dimensões dos dados e depois aplicamos a técnica tradicional de agrupamento nos dados reduzidos. Mais tarde, vimos com que facilidade esse algoritmo complexo poderia ser implementado em Python usando algumas linhas de código.