Cluster com economia de espaço

A maioria dos algoritmos de agrupamento que eu vi começou com a criação de distâncias cada um entre todos os pontos, o que se torna problemático em conjuntos de dados maiores. Existe alguém que não faz isso? Ou faz isso em algum tipo de abordagem parcial / aproximada / escalonada?

Qual algoritmo / implementação de cluster ocupa menos que O (n ^ 2) espaço?

Existe uma lista de algoritmos e seus requisitos de tempo e espaço em algum lugar?

K-Means e Mean-Shift usam os descritores de amostra bruta (não é necessário pré-calcular uma matriz de afinidade).

Caso contrário, para cluster espectral ou cluster de iteração de energia, é possível usar uma representação de matriz esparsa (por exemplo, Linhas Esparas Comprimidas) da matriz de afinidade k-vizinhos mais próximos (para alguma métrica de distância ou afinidade). Se k for pequeno (digamos 5 ou 10). Você obterá uma representação com muito espaço eficiente (2 * n_samples * k * 8 bytes para valores de ponto flutuante de precisão dupla).

Alguns algoritmos de cluster podem usar estruturas de índice espacial. Isso permite, por exemplo, que o DBSCAN e o OPTICS sejam executados no tempo (desde que o índice permita consultas ).$O(n\log n)$$O(\log n)$

Obviamente, um algoritmo executado nessa complexidade não cria uma matriz de distância .$O(n^2)$

Para alguns algoritmos, como cluster hierárquico com ligação única e ligação completa, existem algoritmos otimizados disponíveis (SLINK, CLINK). É que a maioria das pessoas usa o que pode obter e o que é fácil de implementar. E o cluster hierárquico é fácil de implementar de forma ingênua, usando iterações em uma matriz de distância (resultando em um algoritmo ...).$n$$n^2$$O(n^3)$

Não estou ciente de uma lista completa comparando algoritmos de cluster. Provavelmente, existem mais de 100 algoritmos de clustering. Existem pelo menos uma dúzia de variantes k-means, por exemplo. Além disso, há complexidade em tempo de execução e complexidade de memória; há casos médios e piores. Existem grandes diferenças de implementação (por exemplo, link único mencionado acima; implementações de DBSCAN que não usam um índice e, portanto, estão em e, embora não precisem armazenar a matriz de distância , eles ainda precisam calcular todas as distâncias aos pares). Além disso, existem muitos parâmetros. Para k-significa,$O(n^2)$$n\times n$$k$é crítico. Para praticamente qualquer algoritmo, a função de distância faz uma enorme diferença (muitas implementações permitem apenas a distância euclidiana ...). E quando você chega a funções dispendiosas de distância (além de coisas triviais como a Euclidiana), o número de cálculos de distância pode rapidamente ser a parte principal. Então você precisaria diferenciar entre o número de operações no total e o número de cálculos de distância necessários. Portanto, um algoritmo que está em operações , mas apenas cálculos de distância pode facilmente superar um algoritmo que é em ambos, quando as funções de distância são realmente caras (por exemplo, a distância a função em si é ).$O(n^2)$$O(n)$$O(n \log n)$$O(n)$

Boa pergunta. Um método simplificado para dizer 3 vizinhos mais próximos é amostrar vizinhos Nsample de cada ponto de dados, mantendo o mais próximo 3. Embora seja trivial, executar isso para alguns valores de Nsample dará uma idéia da relação sinal / ruído, ruído próximo / de fundo , facilmente plotados para seus dados. Um truque adicional é verificar os vizinhos dos vizinhos, para ver se algum deles está mais próximo do que os vizinhos diretos. Além disso, se os dados de entrada já estiverem bem embaralhados, faça a amostra em blocos, caso contrário, o cache será interrompido.

(Adicionado): veja fastcluster em R e acredito no SciPy v0.11.
Para texto, consulte google-all-pairs-similarity-search .

Repita: "Uma medida de dissimilaridade apropriada é muito mais importante para obter sucesso com o clustering do que a escolha do algoritmo de clustering" - escolhendo o método de clustering .