Informações:

Publicações do PESC

Título
Autômatos Celulares Generalizados Como Modelos de Influência para Agrupamentos de Dados e Interações Sociais
Linha de pesquisa
Inteligência Artificial
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
25/6/2008
Resumo

Os sistemas complexos estão compostos por muitos elementos de caraterísticas semelhantes com interações mútuas tipicamente não-lineares. Em alguns desses sistemas, a origem da não-linearidade pode ser modelada considerando que cada elemento possui uma propriedade, que chamaremos influência, cujo valor é co-determinante da intensidade das interações de um elemento com os restantes, e que por sua vez, o histórico de interações modifica o valor da influência. Os autômatos celulares são uma das ferramentas conceituais mais empregadas na modelagem de sistemas complexos. No presente trabalho desenvolvemos dois autômatos celulares generalizados (ACG), um deles determinístico e o outro estocástico, para aplicar o conceito de influência ao problema de detecção de agrupamentos de dados e à dinâmica das relações sociais. O ACG determinístico é o embasamento de um novo algoritmo para detecção de agrupamentos em grandes bancos de dados. O conceito de vizinhança, inerente aos ACGs, é a única medida de distância empregada; por este motivo, os dados não requerem nenhum pré-processamento. A localidade do processamento da informação dos ACGs confere ao algoritmo uma aptidão intrínseca para sua paralelização. A escalabilidade do algoritmo com respeito à quantidade de dados a considerar deriva-se do fato que as próprias células que compõem o ACG representam subconjuntos. A capacidade de auto-organização dos ACG permite que os agrupamentos emerjam sem a necessidade de parâmetros. São apresentados resultados da aplicação do algoritmo a bancos de dados sintéticos e naturais. Finalmente, o ACG estocástico aplicado à dinâmica das relações sociais resulta num modelo que reproduz as tendências observadas em bancos de dados criminalísticos.

Abstract

Complex systems are large sets of elements with similar characteristics interacting in a non-linear way with each other. In some of these systems, the source of non-linearity can be modeled considering that each element has a property, which we call influence, whose value is co-determinant of the intensity of the interactions of an element with the others, and that in turn, the history of interactions alters the value of the influence. Cellular automata are common tools employed for modeling complex systems. In this work we develop two generalized cellular automata (GCA), one of them deterministic and the other, stochastic, to apply the concept of influence to the problem of data clustering, and to the dynamics of social relations. The deterministic GCA is the core of a new clustering algorithm for large databases. The concept of neighborhood, as part of the cellular automaton definition, is the only measure of distance employed and for this reason, the data do not require any pre-processing. Since GCAs perform local processing of information, the algorithm is naturally suited to be parallelized. The scalability of the algorithm with respect to the amount of data to be processed is assured since the cells that make up the GCA themselves represent subsets of data. Self-organization, a property found in many GCAs, is responsible for the emergence of clusters without need of tuning parameters. Several tests, performed both on synthetic and natural databases serve to illustrate the performance of the algorithm. Finally, the stochastic GCA applied to the dynamics of social relations results in a model that reproduces the observed trends in databases of criminal activities.

Arquivo
Topo