K-Means distribuído sobre dados binários comprimidos

E quem disse que o K-Means estava morto hein?

Distributed K-means over Compressed Binary Data

Abstract—We consider a network of binary-valued sensors with a fusion center. The fusion center has to perform K-means clustering on the binary data transmitted by the sensors. In order to reduce the amount of data transmitted within the network, the sensors compress their data with a source coding scheme based on LDPC codes. We propose to apply the K-means algorithm directly over the compressed data without reconstructing the original sensors measurements, in order to avoid potentially complex decoding operations. We provide approximated expressions of the error probabilities of the K-means steps in the compressed domain. From these expressions, we show that applying the Kmeans algorithm in the compressed domain enables to recover the clusters of the original domain. Monte Carlo simulations illustrate the accuracy of the obtained approximated error probabilities, and show that the coding rate needed to perform K-means clustering in the compressed domain is lower than the rate needed to reconstruct all the measurements.

Conclusion: In this paper, we considered a network of sensors which transmit their compressed binary measurements to a fusion center. We proposed to apply the K-means algorithm directly over the compressed data, without reconstructing the sensor measurements. From a theoretical analysis and Monte Carlo simulations, we showed the efficiency of applying K-means in the compressed domain. We also showed that the rate needed to perform K-means on the compressed vectors is lower than the rate needed to reconstruct all the measurements.

Anúncios
K-Means distribuído sobre dados binários comprimidos

Mineração de Dados na Prática

Uma das boas surpresas ao abrir a edição Nr 98 da SQL Magazine foi encontrar um ótimo artigo sobre Mineração de Dados, em especial a explicação muito didática do funcionamento do K-Means (K-Médias).

O artigo é assinado por Marcio Marcenes Netto e Tauller Augusto de Araujo Matos e mostra o desenvolvimento do algoritmo de acordo com as suas interações e como o mesmo forma os Clusters.

Vale a pena a leitura, se você é estudante de Banco de Dados e procura saber um pouco mais sobre esse algoritmo.

Mineração de Dados na Prática

Top 10 Algoritmos em Mineração de Dados

Esse artigo de 2007 apresenta os 10 algoritmos de Mineração de Dados mais utilizados dentro dos mais diversos tipos de domínios. O processo de determinação desses algoritmos deram-se através de uma pesquisa da ACM KDD no qual diversos pesquisadores deram seus respectivos pareceres. Os algoritmos apresentados nessa pesquisa estão descritos de maneira bem sucinta e objetiva e vale a pena a leitura.

Ten Algorithms in Data Mining

 

Top 10 Algoritmos em Mineração de Dados