Determinar diferentes clusters de dados 1d do banco de dados

24

Eu tenho uma tabela de banco de dados de transferências de dados entre nós diferentes. Este é um enorme banco de dados (com quase 40 milhões de transferências). Um dos atributos é o número de transferências de bytes (nbytes) que variam de 0 bytes a 2 tera bytes. Gostaria de agrupar os nbytes de modo que, dado k clusters, algumas transferências x1 pertençam ao cluster k1, x2 transfters ao k2 etc.

Pela terminologia que usei, você deve ter adivinhado o que eu estava fazendo: K-significa. Esses são dados 1d, já que nbytes é o único recurso que me interessa. Quando eu estava procurando por métodos diferentes para isso, vi o EM ser mencionado algumas vezes, juntamente com uma abordagem sem agrupamento. Gostaria de saber suas opiniões sobre como abordar esse problema (especificamente se agrupar ou não agrupar).

Obrigado!

clustering k-means Shaun
fonte
O que são "transferências x1", "transferências x2" etc.? O "tipo de transferência" é uma segunda variável?
Peter Flom - Restabelece Monica
transferências x1 é apenas uma maneira de dizer que essas 500 transferências tinham tamanho de transferência em torno de algum valor (essa seria a média para esse cluster em k-médias).
Shaun
5
Eu não sou especialista em clustering, mas com tantos dados e apenas uma dimensão, gostaria de saber se você poderia fazer alguns gráficos de densidade do kernel usando larguras de banda diferentes e ver quantos modos / picos você encontra e se o resultado parece ser Seria útil para você.
gung - Restabelece Monica
11
Você perguntou se deseja agrupar ou não. Qual seria seu objetivo de agrupar? Você usaria os clusters para algum outro propósito ou é de interesse teórico?
Peter Flom - Restabelece Monica
Alguns dos outros atributos da tabela são nome de usuário, datas de início e término. Minha esperança é que, agrupando as transferências com base no tamanho da transferência, eu possa me referir a outros atributos de uma transferência específica para ver quem está transferindo quanto em que mês do ano. O que faremos com essa observação, ainda não sei. Mas é para onde eu vou.
Shaun

Respostas:

43

Em dados unidimensionais, não use análise de cluster.

A análise de cluster é geralmente uma técnica multivariada. Ou deixe-me dizer o contrário: para dados unidimensionais - que são completamente ordenados - existem técnicas muito melhores. Usar k-means e técnicas semelhantes aqui é um desperdício total, a menos que você faça um esforço suficiente para realmente otimizá-las para o caso 1-d.

Apenas para dar um exemplo: para k-significa, é comum usar k objetos aleatórios como sementes iniciais. Para dados unidimensionais, é bastante fácil fazer melhor usando apenas os quantis apropriados (1 / 2k, 3 / 2k, 5 / 2k etc.), depois de classificar os dados uma vez e otimizar a partir deste ponto de partida. No entanto, os dados 2D não podem ser classificados completamente. E em uma grade, provavelmente haverá células vazias.

Eu também não chamaria isso de cluster. Eu chamaria isso de intervalo . O que você realmente deseja fazer é otimizar as bordas do intervalo. Se você fizer k-means, ele testará para cada objeto se deve ser movido para outro cluster. Isso não faz sentido em 1D: apenas os objetos nas bordas do intervalo precisam ser verificados. Obviamente, isso é muito mais rápido, pois existem apenas ~ 2k objetos lá. Se eles ainda não preferem outros intervalos, objetos mais centrais também não.

Você pode pesquisar técnicas como a otimização do Jenks Natural Breaks , por exemplo.

Ou você pode fazer uma estimativa da densidade do kernel e procurar mínimos locais da densidade para dividir lá. O bom é que você não precisa especificar k para isso!

PS, por favor, use a função de pesquisa. Aqui estão algumas perguntas sobre o cluster de dados 1-d que você perdeu:

Anony-Mousse
fonte
Quantiles não necessariamente concordam com clusters. Uma distribuição 1d pode ter 3 clusters naturais, onde dois contêm 10% dos dados cada e o último contém 80% dos dados. Portanto, acho que é possível agrupar aqui, embora eu concorde que faz sentido otimizar a execução escolhendo sementes de maneira inteligente etc. ou usando outras idéias.
Bitwise
Os quantis são provavelmente bons pontos de partida para otimização , era a isso que eu estava me referindo. E apenas para dar um exemplo do que você pode fazer em 1D que não funciona tão bem em mais de 2 dimensões.
Anony-Mousse
Concordo que valeria a pena tentar usar quantis como sementes, mas ainda tentaria algumas inicializações aleatórias (para exemplos como o que eu dei). De qualquer forma, o melhor método seria apenas olhar para o gráfico de histograma / densidade e escolher manualmente as sementes e, em seguida, otimizá-las com o agrupamento. Isso convergirá muito rapidamente para uma boa solução.
Bitwise
3
Jenks é k-médias em 1D.
whuber
11
@whuber, mesmo que seja matematicamente, espero que ele tenha sido inteligente o suficiente para explorar que os dados podem ser ordenados . Se você usar a abordagem Lloyd para fazer k-means em dados 1-d, você é estúpido, porque está fazendo muitos cálculos que pode ignorar. E para a maioria das pessoas, k-means é Lloyd. E algumas pessoas se preocupam em evitar recomputações desnecessárias.
Anony-Mousse # 02/02
1

Sua pergunta é se você deve agrupar ou qual método você deve usar para agrupar?

Se você deve agrupar em cluster, isso depende se você deseja particionar automaticamente seus dados (por exemplo, se você deseja repetir esse particionamento várias vezes). Se você estiver fazendo isso apenas uma vez, basta olhar para o histograma da distribuição de seus valores e particioná-lo a olho, conforme proposto nos comentários. Eu recomendaria analisar os dados a olho nu, pois isso poderia ajudá-lo a determinar quantos clusters você deseja e também se o cluster "funcionou".

Em relação ao tipo de cluster, o k-means deve ser bom se houver clusters "reais" nos dados. Se você não encontrar clusters no histograma, não faz muito sentido agrupá-lo de qualquer maneira, já que qualquer particionamento do seu intervalo de dados fornecerá clusters válidos (ou, no caso de iniciação aleatória de kmeans, você terá clusters diferentes cada corrida).

Bit a bit
fonte