INBC : an incremental algorithm for dataflow segmentation based on a probabilistic approach

Abstract

This technical report presents a new algorithm for unsupervised segmentation of data flows based on an incrementai probabilistic approach. The algorithm called INBC (for Incrementai Naive Bayes Clustering) assumes that the observed variables are statistically independent, following an approach known as Naive Bayes. INBC creates and continually adjusts a probabilistic model consistent to all sequentially presented data. In the domain of mobile robotics, INBC detects regularities in the sensor readings identifying trajectory segments corresponding to higher order concepts like "wall at right" or curve at left". INBC adopts a mixture model of distribution components that can be expanded to accommodate new information from an input data point, or reduced if spurious components are identified along the leaming process. On the other hand, each data point assimilated by the model contributes to the sequential update of the model parameters based on the maximization of the likelihood of the data. The parameters are updated through the accumulation of relevant information extracted from each data point. The accumulators are limited to a maximum value controlled by a discount factor, making possible the incrementalleaming ofunbounded data streams. The approximation used by INBC to update the model parameters makes it suitable to model non-stationary but slowly variable environments. INBC was tested with simulated data representing typical environments encountered in the considered application domains.

Este relatório apresenta um novo algoritmo para a segmentação não-supervisionada de fluxos de dados baseado numa abordagem probabilística incrementai. O algoritmo, chamado de INBC (Incrementai Na"ive Bayes Clustering), assume que as variáveis observadas são estatisticamente independentes, seguindo uma abordagem conhecida como Na"ive Bayes. INBC cria e ajusta continuamente um modelo probabilístico consistente com todos os dados apresentados seqüencialmente. No domínio da robótica móvel, o algoritmo INBC detecta regularidades nos sinais sensoriais de entrada identificando segmentos de trajetórias correspondentes a conceitos de ordem mais alta como "parede à direita" ou "curva à esquerda". O algoritmo adota um modelo de mistura de distribuições componentes que pode ser expandido para acomodar nova informação fornecida por um dado de entrada, ou reduzido, se forem identificadas componentes espúrias ao longo do processo de aprendizado. Por outro lado, cada dado assimilado pelo modelo contribui para a atualização dos seus parâmetros, baseada na maximização da verossimilhança de todos os dados apresentados. O ajuste dos parâmetros do modelo é baseado na acumulação de informações relevantes extraídas de cada dado observado. Os valores dos acumuladores são limitados a um máximo regulado por um fator de desconto, tomando possível o aprendizado incrementai de seqüências de dados ilimitadas. A aproximação adotada na atualização do modelo faz com que o INBC seja apropriado para a modelagem de ambientes não-estacionários, mas com parâmetros que variam lentamente com o tempo. Para mostrar a utilidade da abordagem adotada, são apresentados vários experimentos com dados simulados.