Os conjuntos de dados de machine learning podem ter milhões de mas nem todos os algoritmos de clustering são escalonados com eficiência. Muitos clustering algoritmos computam a semelhança entre todos os pares de exemplos, o que significa que o tempo de execução aumenta como o quadrado do número de exemplos \(n\), indicado como \(O(n^2)\) em notação de complexidade. \(O(n^2)\) os algoritmos não são prático 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 é escalonado linearmente com \(n\). Esse algoritmo será o foco deste curso.
Tipos de clustering
Para uma lista completa das diferentes abordagens de clustering, consulte Uma pesquisa abrangente de algoritmos de clustering Xu, D. & Tian, Y. Ana. Dados. Ciências (2015) 2: 165. Cada abordagem é mais adequada para de uma distribuição de dados específica. Este curso discute brevemente quatro abordagens.
Clustering baseado em centroide
O centroide de um cluster é o média aritmética de todos os pontos na aglomerado. O clustering baseado em Centroid (em inglês) organiza os dados em categorias não hierárquicas clusters. Algoritmos de clustering baseados em centroide são eficientes, mas sensíveis a condições iniciais e outliers. Dessas, k-means é o é amplamente utilizado. 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 clustering baseado em densidade conecta áreas contíguas de alta densidade de exemplo a clusters. Isso permite a descoberta de qualquer número de agrupamentos de qualquer forma. Os outliers não são atribuídos a clusters. Esses algoritmos têm dificuldade clusters de diferentes densidades e dados com dimensões altas.
Clustering baseado em distribuição
Essa abordagem de clustering pressupõe que os dados sejam compostos de distribuições de dados, como Distribuições gaussianas. Em Figura 3, o algoritmo baseado em distribuição agrupa os dados em três grupos gaussianos distribuições de dados. À medida que a distância do centro da distribuição aumenta, a probabilidade de um ponto pertencer à distribuição diminui. O show das bandas que diminuem a probabilidade. Quando não estiver confortável presumindo que um determinado dos dados, você deve usar um algoritmo diferente.
Clustering hierárquico
O clustering hierárquico cria uma árvore de clusters. Clustering hierárquico, sem surpresas, é adequado para dados hierárquicos, como taxonomias. Consulte Comparação de 61 genomas de Escherichia coli sequenciados de Oksana Lukjancenko, Trudy Wassenaar e Dave Ussery, por exemplo. Qualquer número de clusters pode ser escolhido cortando a árvore no nível certo.
