Algoritmos de agrupamento: do início ao estado da arte

Não é um mau momento para ser um Cientista de Dados. Pessoas sérias podem encontrar interesse em você se você direcionar a conversa para “Big Data”, e o resto da multidão da festa ficará intrigada quando você mencionar “Inteligência Artificial” e “Aprendizado de Máquina”. Até o Google acha que você não é ruim e que está ficando ainda melhor. Existem muitos algoritmos 'inteligentes' que ajudam os cientistas de dados a fazer sua magia. Tudo pode parecer complicado, mas se entendermos e organizarmos um pouco os algoritmos, nem é tão difícil encontrar e aplicar o que precisamos.

Cursos sobre mineração de dados ou aprendizado de máquina geralmente começam com clustering, porque são simples e úteis. É uma parte importante de uma área um pouco mais ampla de Aprendizado Não Supervisionado, onde os dados que queremos descrever não são rotulados. Na maioria dos casos, é onde o usuário não nos fornece muitas informações sobre qual é a saída esperada. O algoritmo tem apenas os dados e deve fazer o melhor que puder. No nosso caso, ele deve realizar clustering – separando os dados em grupos (clusters) que contêm pontos de dados semelhantes, enquanto a dissimilaridade entre os grupos é a maior possível. Os pontos de dados podem representar qualquer coisa, como nossos clientes. O clustering pode ser útil se, por exemplo, quisermos agrupar usuários semelhantes e, em seguida, executar diferentes campanhas de marketing em cada cluster.

Agrupamento K-Means

Após a necessária introdução, os cursos de Data Mining continuam sempre com K-Means; um algoritmo de agrupamento completo, eficaz e amplamente utilizado. Antes de realmente executá-lo, temos que definir uma função de distância entre os pontos de dados (por exemplo, distância euclidiana se quisermos agrupar pontos no espaço), e temos que definir o número de agrupamentos que queremos (k).

O algoritmo começa selecionando k pontos como centroides iniciais ('centros' de clusters). Podemos apenas selecionar quaisquer k pontos aleatórios, ou podemos usar alguma outra abordagem, mas escolher pontos aleatórios é um bom começo. Então, repetimos iterativamente duas etapas:

1. Etapa de atribuição: cada um dos m pontos de nosso conjunto de dados é atribuído a um cluster que é representado pelo mais próximo dos k centróides. Para cada ponto, calculamos as distâncias para cada centróide e simplesmente escolhemos o menos distante.

2. Etapa de atualização: para cada cluster, um novo centroide é calculado como a média de todos os pontos do cluster. Da etapa anterior, temos um conjunto de pontos que são atribuídos a um cluster. Agora, para cada um desses conjuntos, calculamos uma média que declara um novo centroide do cluster.

Após cada iteração, os centróides estão se movendo lentamente e a distância total de cada ponto ao seu centróide atribuído fica cada vez menor. As duas etapas são alternadas até a convergência, ou seja, até que não haja mais mudanças na atribuição do cluster. Após várias iterações, o mesmo conjunto de pontos será atribuído a cada centróide, levando, portanto, aos mesmos centróides novamente. O K-Means é garantido para convergir para um ótimo local. No entanto, isso não precisa necessariamente ser a melhor solução geral (ótimo global).

O resultado final do agrupamento pode depender da seleção dos centróides iniciais, portanto, muita atenção foi dada a esse problema. Uma solução simples é apenas executar o K-Means algumas vezes com atribuições iniciais aleatórias. Podemos então selecionar o melhor resultado tomando aquele com a soma mínima das distâncias de cada ponto ao seu cluster – o valor do erro que estamos tentando minimizar em primeiro lugar.

Outras abordagens para selecionar pontos iniciais podem depender da seleção de pontos distantes. Isso pode levar a melhores resultados, mas podemos ter um problema com outliers, aqueles raros pontos isolados que estão apenas “fora” que podem ser apenas alguns erros. Como estão longe de qualquer cluster significativo, cada um desses pontos pode acabar sendo seu próprio 'cluster'. Um bom equilíbrio é a variante K-Means++ [Arthur e Vassilvitskii, 2007], cuja inicialização ainda escolherá pontos aleatórios, mas com probabilidade proporcional à distância quadrada dos centróides previamente atribuídos. Pontos mais distantes terão maior probabilidade de serem selecionados como centroides iniciais. Consequentemente, se houver um grupo de pontos, a probabilidade de que um ponto do grupo seja selecionado também aumenta à medida que suas probabilidades se somam, resolvendo o problema de discrepâncias que mencionamos.

K-Means++ também é a inicialização padrão para a implementação Scikit-learn K-Means do Python. Se você estiver usando Python, esta pode ser sua biblioteca de escolha. Para Java, a biblioteca Weka pode ser um bom começo:

Java (Weka)

 // Load some data Instances data = DataSource.read("data.arff"); // Create the model SimpleKMeans kMeans = new SimpleKMeans(); // We want three clusters kMeans.setNumClusters(3); // Run K-Means kMeans.buildClusterer(data); // Print the centroids Instances centroids = kMeans.getClusterCentroids(); for (Instance centroid: centroids) { System.out.println(centroid); } // Print cluster membership for each instance for (Instance point: data) { System.out.println(point + " is in cluster " + kMeans.clusterInstance(point)); }

Python (aprender Scikit)

 > >> from sklearn import cluster, datasets > >> iris = datasets.loadiris() > >> Xiris = iris.data > >> yiris = iris.target > >> kmeans = cluster.KMeans(nclusters=3) > >> kmeans.fit(Xiris) KMeans(copy_x=True, init='k-means++', ... > >> print(kmeans.labels[::10]) [1 1 1 1 1 0 0 0 0 0 2 2 2 2 2] > >> print(yiris[::10]) [0 0 0 0 0 1 1 1 1 1 2 2 2 2 2]

No exemplo Python acima, usamos um conjunto de dados de exemplo padrão 'Iris', que contém dimensões de pétalas e sépalas de flores para três espécies diferentes de íris. Nós os agrupamos em três clusters e comparamos os clusters obtidos com as espécies reais (alvo), para ver que eles combinam perfeitamente.

Nesse caso, sabíamos que havia três clusters (espécies) diferentes e o K-Means reconheceu corretamente quais combinam. Mas, como escolhemos um bom número de clusters k em geral? Esse tipo de pergunta é bastante comum em Machine Learning. Se solicitarmos mais clusters, eles serão menores e, portanto, o erro total (total de distâncias dos pontos aos clusters atribuídos) será menor. Então, é uma boa ideia apenas definir um k maior? Podemos terminar com k = m, ou seja, cada ponto sendo seu próprio centroide, com cada cluster tendo apenas um ponto. Sim, o erro total é 0, mas não obtivemos uma descrição mais simples de nossos dados, nem é geral o suficiente para cobrir alguns novos pontos que possam aparecer. Isso é chamado de overfitting, e não queremos isso.

Uma maneira de lidar com esse problema é incluir alguma penalidade para um número maior de clusters. Então, agora estamos tentando minimizar não apenas o erro, mas erro + penalidade . O erro apenas convergirá para zero à medida que aumentarmos o número de clusters, mas a penalidade aumentará. Em alguns pontos, o ganho de adicionar outro cluster será menor que a penalidade introduzida e teremos o resultado ideal. Uma solução que utiliza o Bayesian Information Criterion (BIC) para este fim é chamada de X-Means [Pelleg e Moore, 2000].

Outra coisa que temos que definir corretamente é a função de distância. Às vezes, essa é uma tarefa simples, lógica, dada a natureza dos dados. Para pontos no espaço, a distância euclidiana é uma solução óbvia, mas pode ser complicada para características de diferentes 'unidades', para variáveis ​​discretas, etc. Isso pode exigir muito conhecimento de domínio. Ou podemos ligar para o Machine Learning para obter ajuda. Podemos realmente tentar aprender a função de distância. Se tivermos um conjunto de pontos de treinamento que sabemos como devem ser agrupados (ou seja, pontos rotulados com seus clusters), podemos usar técnicas de aprendizado supervisionado para encontrar uma boa função e aplicá-la ao nosso conjunto de destino que ainda não está agrupado .

O método usado no K-Means, com suas duas etapas alternadas, assemelha-se a um método de Expectativa-Maximização (EM). Na verdade, pode ser considerado uma versão muito simples do EM. No entanto, não deve ser confundido com o algoritmo de agrupamento EM mais elaborado, embora compartilhe alguns dos mesmos princípios.

Agrupamento EM

Assim, com o agrupamento K-Means, cada ponto é atribuído a apenas um único cluster, e um cluster é descrito apenas por seu centroide. Isso não é muito flexível, pois podemos ter problemas com clusters que se sobrepõem ou que não são de forma circular. Com o EM Clustering, podemos agora dar um passo adiante e descrever cada cluster por seu centroide (média), covariância (para que possamos ter clusters elípticos) e peso (o tamanho do cluster). A probabilidade de que um ponto pertença a um cluster é agora dada por uma distribuição de probabilidade gaussiana multivariada (multivariada - dependendo de múltiplas variáveis). Isso também significa que podemos calcular a probabilidade de um ponto estar sob um 'sino' gaussiano, ou seja, a probabilidade de um ponto pertencer a um cluster.

Iniciamos agora o procedimento EM calculando, para cada ponto, as probabilidades dele pertencer a cada um dos clusters atuais (que, novamente, podem ser criados aleatoriamente no início). Este é o passo E. Se um cluster é realmente um bom candidato para um ponto, ele terá uma probabilidade próxima de um. No entanto, dois ou mais clusters podem ser candidatos aceitáveis, de modo que o ponto tem uma distribuição de probabilidades sobre os clusters. Essa propriedade do algoritmo, de pontos não pertencentes restritos a um cluster, é chamada de “soft clustering”.

A etapa M agora recalcula os parâmetros de cada cluster, usando as atribuições de pontos ao conjunto anterior de clusters. Para calcular a nova média, covariância e peso de um cluster, cada dado de ponto é ponderado pela sua probabilidade de pertencer ao cluster, conforme calculado na etapa anterior.

Alternar essas duas etapas aumentará a probabilidade logarítmica total até convergir. Novamente, o máximo pode ser local, então podemos executar o algoritmo várias vezes para obter clusters melhores.

Se agora queremos determinar um único cluster para cada ponto, podemos simplesmente escolher o mais provável. Tendo um modelo de probabilidade, também podemos usá-lo para gerar dados semelhantes, ou seja, amostrar mais pontos semelhantes aos dados que observamos.

Propagação de afinidade

O Affinity Propagation (AP) foi publicado por Frey e Dueck em 2007 e está se tornando cada vez mais popular devido à sua simplicidade, aplicabilidade geral e desempenho. Está mudando seu status do estado da arte para o padrão de fato.

As principais desvantagens do K-Means e algoritmos semelhantes são ter que selecionar o número de clusters e escolher o conjunto inicial de pontos. A Propagação de Afinidade, em vez disso, toma como entrada medidas de similaridade entre pares de pontos de dados e simultaneamente considera todos os pontos de dados como exemplos potenciais. As mensagens de valor real são trocadas entre os pontos de dados até que um conjunto de exemplares de alta qualidade e os clusters correspondentes emerjam gradualmente.

Como entrada, o algoritmo exige que forneçamos dois conjuntos de dados:

1. Semelhanças entre pontos de dados, representando o quão adequado um ponto é para ser o exemplar de outro. Se não houver semelhança entre dois pontos, pois eles não podem pertencer ao mesmo cluster, essa semelhança pode ser omitida ou definida como -Infinity dependendo da implementação.

2. Preferências, representando a adequação de cada ponto de dados para ser um exemplar. Podemos ter algumas informações a priori de quais pontos poderiam ser favorecidos para essa função, e assim podemos representá-la por meio de preferências.

Tanto as semelhanças quanto as preferências são frequentemente representadas por meio de uma única matriz, onde os valores na diagonal principal representam as preferências. A representação matricial é boa para conjuntos de dados densos. Onde as conexões entre os pontos são esparsas, é mais prático não armazenar toda a matriz nxn na memória, mas manter uma lista de semelhanças com os pontos conectados. Nos bastidores, 'trocar mensagens entre pontos' é a mesma coisa que manipular matrizes, e é apenas uma questão de perspectiva e implementação.

O algoritmo então passa por várias iterações, até convergir. Cada iteração tem duas etapas de passagem de mensagens:

1. Cálculo de responsabilidades: A responsabilidade r(i, k) reflete a evidência acumulada de como o ponto k é adequado para servir como exemplo para o ponto i, levando em consideração outros exemplos potenciais para o ponto i. A responsabilidade é enviada do ponto de dados i para o ponto de exemplo candidato k.

2. Calculando disponibilidades: A disponibilidade a(i, k) reflete a evidência acumulada de quão apropriado seria para o ponto i escolher o ponto k como seu exemplar, levando em consideração o suporte de outros pontos de que o ponto k deveria ser um exemplar. A disponibilidade é enviada do ponto de exemplar candidato k para o ponto i.

Para calcular as responsabilidades, o algoritmo usa semelhanças e disponibilidades originais calculadas na iteração anterior (inicialmente, todas as disponibilidades são definidas como zero). As responsabilidades são definidas para a similaridade de entrada entre o ponto i e o ponto k como seu exemplar, menos o maior da soma de similaridade e disponibilidade entre o ponto i e outros exemplares candidatos. A lógica por trás do cálculo de quão adequado é um ponto para um exemplar é que ele é mais favorecido se a preferência inicial a priori for maior, mas a responsabilidade fica menor quando há um ponto semelhante que se considera um bom candidato, então há um ' competição' entre os dois até que um seja decidido em alguma iteração.

O cálculo de disponibilidades, então, usa responsabilidades calculadas como evidência de que cada candidato seria um bom exemplo. A disponibilidade a(i, k) é definida como a auto-responsabilidade r(k, k) mais a soma das responsabilidades positivas que o candidato exemplar k recebe de outros pontos.

Finalmente, podemos ter diferentes critérios de parada para encerrar o procedimento, como quando as mudanças nos valores caem abaixo de algum limite ou o número máximo de iterações é atingido. Em qualquer ponto através do procedimento de Propagação de Afinidade, a soma das matrizes Responsabilidade (r) e Disponibilidade (a) nos dá a informação de agrupamento que precisamos: para o ponto i, o k com máximo r(i, k) + a(i, k) representa o ponto eu sou exemplar. Ou, se precisarmos apenas do conjunto de exemplares, podemos escanear a diagonal principal. Se r(i, i) + a(i, i) > 0, o ponto i é um exemplar.

Vimos que com K-Means e algoritmos semelhantes, decidir o número de clusters pode ser complicado. Com o AP, não precisamos especificá-lo explicitamente, mas ele ainda pode precisar de alguns ajustes se obtivermos mais ou menos clusters do que podemos achar ideal. Felizmente, apenas ajustando as preferências podemos diminuir ou aumentar o número de clusters. Definir preferências para um valor mais alto levará a mais clusters, pois cada ponto é 'mais certo' de sua adequação para ser um exemplar e, portanto, é mais difícil 'superar' e incluí-lo sob a 'dominação' de algum outro ponto. Por outro lado, definir preferências mais baixas resultará em menos clusters; como se estivessem dizendo “não, não, por favor, você é um exemplo melhor, eu vou entrar no seu cluster”. Como regra geral, podemos definir todas as preferências para a similaridade mediana para um número médio a grande de clusters, ou para a similaridade mais baixa para um número moderado de clusters. No entanto, algumas execuções com preferências de ajuste podem ser necessárias para obter o resultado que atenda exatamente às nossas necessidades.

A Propagação de Afinidade Hierárquica também merece destaque, como uma variante do algoritmo que lida com a complexidade quadrática dividindo o conjunto de dados em alguns subconjuntos, agrupando-os separadamente e realizando o segundo nível de agrupamento.

No fim…

Há toda uma gama de algoritmos de agrupamento, cada um com seus prós e contras em relação ao tipo de dados que eles usam, complexidade de tempo, pontos fracos e assim por diante. Para mencionar mais algoritmos, por exemplo, há Hierarchical Agglomerative Clustering (ou Linkage Clustering), bom para quando não temos necessariamente clusters circulares (ou hiperesféricos) e não sabemos o número de clusters com antecedência. Começa com cada ponto sendo um cluster separado e funciona juntando dois clusters mais próximos em cada etapa até que tudo esteja em um grande cluster.

Com Hierarchical Agglomerative Clustering, podemos facilmente decidir o número de clusters depois cortando o dendrograma (diagrama de árvore) horizontalmente onde acharmos adequado. Também é repetível (sempre dá a mesma resposta para o mesmo conjunto de dados), mas também é de maior complexidade (quadrático).

Então, DBSCAN (Density-Based Spatial Clustering of Applications with Noise) também é um algoritmo que vale a pena mencionar. Agrupa pontos que estão próximos uns dos outros, expandindo os aglomerados em qualquer direção onde existam pontos próximos, lidando assim com diferentes formas de aglomerados.

Esses algoritmos merecem um artigo próprio, e podemos explorá-los em um post separado mais tarde.

É preciso experiência com algumas tentativas e erros para saber quando usar um algoritmo ou outro. Felizmente, temos uma variedade de implementações em diferentes linguagens de programação, portanto, testá-las requer apenas um pouco de vontade de jogar.