Os conjuntos de dados de aprendizado de máquina podem ter milhões de exemplos, mas nem todos os algoritmos de agrupamento são escalonados de maneira eficiente. Muitos algoritmos de agrupamento calculam a similaridade entre todos os pares de exemplos, o que significa que o tempo de execução aumenta conforme o quadrado do número de exemplos \(n\), indicado como \(O(n^2)\) na notação de complexidade.Os algoritmos \(O(n^2)\) não são práticos para conjuntos de dados com milhões de exemplos.
O algoritmo k-means tem uma complexidade de \(O(n)\), o que significa que o algoritmo é dimensionado linearmente com \(n\). Este algoritmo será o foco deste curso.
Tipos de agrupamento
Para conferir uma lista completa de diferentes abordagens de agrupamento, consulte A Comprehensive Survey of Clustering Algorithms (Xu, D., 2005). & Tian, Y. Ann. Data. Sci. (2015) 2: 165. Cada abordagem é mais adequada para uma distribuição de dados específica. Este curso discute brevemente quatro abordagens comuns.
Agrupamento baseado em centroide
O centroide de um cluster é a média aritmética de todos os pontos no cluster. O clustering com base no centroide organiza os dados em clusters não hierárquicos. Os algoritmos de agrupamento baseados em centroide são eficientes, mas sensíveis a condições iniciais e valores discrepantes. Entre eles, o k-means é o mais usado. Ela exige que os usuários definam o número de centroides, k, e funciona bem com clusters de tamanho aproximadamente igual.
Clustering baseado em densidade
O agrupamento com base na densidade conecta áreas contíguas de alta densidade de exemplos em clusters. Isso permite a descoberta de qualquer número de clusters de qualquer forma. Os valores discrepantes não são atribuídos a clusters. Esses algoritmos têm dificuldade com clusters de densidades diferentes e dados com dimensões altas.
Agrupamento baseado em distribuição
Essa abordagem de agrupamento pressupõe que os dados sejam compostos de distribuições probabilísticas, como distribuições gaussianas. Na Figura 3, o algoritmo baseado em distribuição agrupa os dados em três distribuições gaussianas. À medida que a distância do centro da distribuição aumenta, a probabilidade de um ponto pertencer à distribuição diminui. As faixas mostram essa diminuição na probabilidade. Quando você não se sentir confortável em assumir uma distribuição subjacente específica dos dados, use um algoritmo diferente.
Clustering hierárquico
O clustering hierárquico cria uma árvore de clusters. O agrupamento hierárquico é adequado para dados hierárquicos, como taxonomias. Confira um exemplo em Comparison of 61 Sequenced Escherichia coli Genomes de Oksana Lukjancenko, Trudy Wassenaar e Dave Ussery. É possível escolher qualquer número de clusters cortando a árvore no nível certo.
