Detecção de outliers é uma tarefa fundamental para descoberta de conhecimento em mineração de dados. Cujo objetivo é identificar as amostras de dados que desviam acentuadamente dos padrões apresentados num conjunto de dados. Neste trabalho, apresentamos uma nova técnica de detecção de outliers baseada em caminhada determinística do turista. Especificamente um caminhante é iniciado para cada exemplar de dado, variando-se o tamanho da memória, assim, um exemplar recebe uma alta pontuação de outlier ao participar em poucos atratores, enquanto que receberá uma baixa pontuação no caso de participar numa grande quantidade de atratores. Os resultados experimentais em cenários artificiais e reais evidenciaram um bom desempenho do método proposto. Em comparação com os métodos clássicos, o método proposto apresenta as seguintes características salientes: 1) Identifica os outliers através da determinação de estruturas no espaço de dados ao invés de considerar apenas características físicas, como distância, similaridade e densidade. 2) É capaz de detectar outliers internos, situados em regiões entre dois ou mais agrupamentos. 3) Com a variação do valor de memória, os caminhantes conseguem extrair tanto características locais, quanto globais do conjunto de dados. 4) O método proposto é determinístico, não exigindo diversas execuções (em contraste às técnicas estocásticas). Além disso, neste trabalho caracterizamos, pela primeira vez, que as dinâmicas exibidas pela caminhada do turista podem gerar atratores complexos, com diversos cruzamentos. Sendo que estes podem revelar estruturas ainda mais detalhadas e consequentemente melhorar a detecção dos outliers. / Outlier detection is a fundamental task for knowledge discovery in data mining. It aims to detect data items that deviate from the general pattern of a given data set. In this work, we present a new outlier detection technique using tourist walks. Specifically, starting from each data sample and varying the memory size, a data sample gets a higher outlier score if it participates in few tourist walk attractors, while it gets a low score if it participates in a large number of attractors. Experimental results on artificial and real data sets show good performance of the proposed method. In comparison to classical methods, the proposed one shows the following salient features: 1) It finds out outliers by identifying the structure of the input data set instead of considering only physical features, such as distance, similarity or density. 2) It can detect not only external outliers as classical methods do, but also internal outliers staying among various normal data groups. 3) By varying the memory size, the tourist walks can characterize both local and global structures of the data set. 4) The proposed method is a deterministic technique. Therefore, only one run is sufficient, in contrast to stochastic techniques, which require many runs. Moreover, in this work, we find, for the first time, that tourist walks can generate complex attractors in various crossing shapes. Such complex attractors reveal data structures in more details. Consequently, it can improve the outlier detection.

Detecção de outliers é uma tarefa fundamental para descoberta de conhecimento em mineração de dados. Cujo objetivo é identificar as amostras de dados que desviam acentuadamente dos padrões apresentados num conjunto de dados. Neste trabalho, apresentamos uma nova técnica de detecção de outliers baseada em caminhada determinística do turista. Especificamente um caminhante é iniciado para cada exemplar de dado, variando-se o tamanho da memória, assim, um exemplar recebe uma alta pontuação de outlier ao participar em poucos atratores, enquanto que receberá uma baixa pontuação no caso de participar numa grande quantidade de atratores. Os resultados experimentais em cenários artificiais e reais evidenciaram um bom desempenho do método proposto. Em comparação com os métodos clássicos, o método proposto apresenta as seguintes características salientes: 1) Identifica os outliers através da determinação de estruturas no espaço de dados ao invés de considerar apenas características físicas, como distância, similaridade e densidade. 2) É capaz de detectar outliers internos, situados em regiões entre dois ou mais agrupamentos. 3) Com a variação do valor de memória, os caminhantes conseguem extrair tanto características locais, quanto globais do conjunto de dados. 4) O método proposto é determinístico, não exigindo diversas execuções (em contraste às técnicas estocásticas). Além disso, neste trabalho caracterizamos, pela primeira vez, que as dinâmicas exibidas pela caminhada do turista podem gerar atratores complexos, com diversos cruzamentos. Sendo que estes podem revelar estruturas ainda mais detalhadas e consequentemente melhorar a detecção dos outliers. / Outlier detection is a fundamental task for knowledge discovery in data mining. It aims to detect data items that deviate from the general pattern of a given data set. In this work, we present a new outlier detection technique using tourist walks. Specifically, starting from each data sample and varying the memory size, a data sample gets a higher outlier score if it participates in few tourist walk attractors, while it gets a low score if it participates in a large number of attractors. Experimental results on artificial and real data sets show good performance of the proposed method. In comparison to classical methods, the proposed one shows the following salient features: 1) It finds out outliers by identifying the structure of the input data set instead of considering only physical features, such as distance, similarity or density. 2) It can detect not only external outliers as classical methods do, but also internal outliers staying among various normal data groups. 3) By varying the memory size, the tourist walks can characterize both local and global structures of the data set. 4) The proposed method is a deterministic technique. Therefore, only one run is sufficient, in contrast to stochastic techniques, which require many runs. Moreover, in this work, we find, for the first time, that tourist walks can generate complex attractors in various crossing shapes. Such complex attractors reveal data structures in more details. Consequently, it can improve the outlier detection.

Considere um meio desordenado constituído por $N$ pontos cujas coordenadas são geradas aleatoriamente de maneira uniforme e independente nas arestas unitárias de um hipercubo $d$-dimensional. As probabilidades de vizinhança entre os pares de pontos deste meio são expressas através da fórmula de Cox. Um caminhante parte de um dado ponto deste meio desordenado e se movimenta obedecendo à regra determinista de ir para o ponto mais próximo que não tenha sido visitado nos últimos $\\mu$ passos. Este processo foi denominado de caminhada determinista do turista. Cada trajetória gerada por esta dinâmica possui uma parte inicial não-periódica de $t$ passos (transiente) e uma parte final periódica de $p$ passos (atrator). Neste trabalho, obtemos analiticamente algumas distribuições estatísticas para a caminhada determinista do turista com memória $\\mu$ arbitrária em sistemas unidimensionais e com memória $\\mu=2$ no modelo Random Link (que corresponde ao limite $d ightarrow 1$). Estes resultados nos permitiram compreender o papel da memória no comportamento exploratório do turista e explicar a equivalência não-trivial entre o modelo Random Link e o modelo Random Map (que é um caso limite das redes de Kauffman). Enfatizamos que o número de pontos explorados pelo turista é a grandeza fundamental nos problemas considerados. As distribuições analíticas obtidas foram validadas através de experimentos numéricos. Também obtivemos uma dedução alternativa para a fórmula de Cox, apresentando os resultados finais em termos de distribuições estatísticas elementares. / Consider a medium characterized by $N$ points whose coordinates are randomly and independently generated by a uniform distribution along the unitary edges of a $d$-dimensional hypercube. The neighborhood probabilities between any pair of points in this medium are given by the Cox formula. A walker leaves from each point of this disordered medium and moves according to the deterministic rule to go the nearest point which has not been visited in the preceding $\\mu$ steps. This process has been called the deterministic tourist walk. Each trajectory generated by this dynamics has an initial non-periodic part of $t$ steps (transient) and a final periodic part of $p$ steps (attractor). In this work, we obtain analytically some statistical distributions for the deterministic tourist walk with arbitrary memory $\\mu$ in one-dimensional systems and with memory $\\mu=2$ in the random link model (which corresponds to $d ightarrow 1$ limit). These results enable us to understand the main role played by the memory on the tourist\'s exploratory behavior and explain the non-trivial equivalence between the random link model and the random map model (which is a limiting case of the Kauffman model). We stress that the number of explored points is the fundamental quantity in the considered problems. The obtained distributions have been validated by numerical experiments. We also obtain an alternative derivation for the Cox formula, writing the final results in terms of known statistical distributions.

Podemos considerar a caminhada determinista do turista como um processo do tipo dinâmico, que ocorre sobre uma rede composta por N pontos. Os pontos são gerados de maneira aleatória, no espaço euclidiano d dimensional. Um caminhante, partindo de um ponto qualquer do meio desordenado, se movimenta seguindo uma regra determinista de ir para o ponto mais próximo que não tenha sido visitado nos últimos ?= µ - 1 passos. Cada uma das trajetórias geradas através dessa dinâmica possui uma parte inicial não periódica de t passos, denominada transiente, e uma parte final, periódica, de p passos, denominada atrator. Devido ao custo computacional de memória, só é possível simular sistemas com N ? O(103) e µ << N. Neste estudo uma nova implementação na estrutura de armazenamento de dados, no modelo numérico do turista, nos permitiu obter algumas distribuições estatísticas para a caminhada, com valores de memória µ ? O(N). Com estes resultados verificamos a eficiência da estrutura proposta e avançamos no conhecimento acerca do comportamento do turista em caminhadas com memória da ordem de N. Também neste trabalho, obtivemos resultados numéricos interessantes, que serviram para explicar a formação de atratores com determinados períodos na caminhada determinista do turista unidimensional, bem como a não formação de atratores com períodos 2µ+1, 2µ+2 e 2µ+3.não são constituídos. Também neste trabalho, uma nova implementação na estrutura de armazenamento de dados, no modelo numérico do turista, nos permitiu obter algumas distribuições estatísticas para a caminhada, com valores de memória ? muito acima do que se tinha alcançado anteriormente. Com estes resultados verificamos a eficiência da estrutura proposta, e avançamos o conhecimento a cerca do comportamento do turista em sistema da ordem de N. / We may consider the deterministic tourist walk as a dynamic process performed over a landscape of N points. These points are randomly spread on a d dimensional euclidean space. A walker leaves from any point of that landscape and moves according to the deterministic rule of going to the nearest point that has not been visited in the last ?= µ - 1 steps. Each trajectory generated by this dynamics has an initial non-periodic part of t steps, called transient, and a final periodic one of p steps, called attractor. Due to computational costs of memory usage, it is possible to simulate only small sistems, with N ? O(103) and µ << N. In this work, we propose a new implementation of the structure for data storage. The numerical model of the tourist walk, allowed us to obtain some statistical distributions for the walk with a memory value µ ? O(N). Moreover, in this study we obtain interesting and useful numerical results to explain the presence of some specific attractors in deterministic walk in one-dimensional space and the absence of attractors with periods 2µ+1, 2µ+2 and 2µ+3. are not made. In this work, we propose a new implementation of the structure for storing data, the numerical model of the tourist, has allowed us to obtain some statistical distributions for the walk with a memory value ? over and above what had been achieved previously. With these results, we verifed the efficiency of the HL structure proposed, and advance knowledge about the behavior of the tourist walk in the order of N.

Podemos considerar a caminhada determinista do turista como um processo do tipo dinâmico, que ocorre sobre uma rede composta por N pontos. Os pontos são gerados de maneira aleatória, no espaço euclidiano d dimensional. Um caminhante, partindo de um ponto qualquer do meio desordenado, se movimenta seguindo uma regra determinista de ir para o ponto mais próximo que não tenha sido visitado nos últimos ?= µ - 1 passos. Cada uma das trajetórias geradas através dessa dinâmica possui uma parte inicial não periódica de t passos, denominada transiente, e uma parte final, periódica, de p passos, denominada atrator. Devido ao custo computacional de memória, só é possível simular sistemas com N ? O(103) e µ << N. Neste estudo uma nova implementação na estrutura de armazenamento de dados, no modelo numérico do turista, nos permitiu obter algumas distribuições estatísticas para a caminhada, com valores de memória µ ? O(N). Com estes resultados verificamos a eficiência da estrutura proposta e avançamos no conhecimento acerca do comportamento do turista em caminhadas com memória da ordem de N. Também neste trabalho, obtivemos resultados numéricos interessantes, que serviram para explicar a formação de atratores com determinados períodos na caminhada determinista do turista unidimensional, bem como a não formação de atratores com períodos 2µ+1, 2µ+2 e 2µ+3.não são constituídos. Também neste trabalho, uma nova implementação na estrutura de armazenamento de dados, no modelo numérico do turista, nos permitiu obter algumas distribuições estatísticas para a caminhada, com valores de memória ? muito acima do que se tinha alcançado anteriormente. Com estes resultados verificamos a eficiência da estrutura proposta, e avançamos o conhecimento a cerca do comportamento do turista em sistema da ordem de N. / We may consider the deterministic tourist walk as a dynamic process performed over a landscape of N points. These points are randomly spread on a d dimensional euclidean space. A walker leaves from any point of that landscape and moves according to the deterministic rule of going to the nearest point that has not been visited in the last ?= µ - 1 steps. Each trajectory generated by this dynamics has an initial non-periodic part of t steps, called transient, and a final periodic one of p steps, called attractor. Due to computational costs of memory usage, it is possible to simulate only small sistems, with N ? O(103) and µ << N. In this work, we propose a new implementation of the structure for data storage. The numerical model of the tourist walk, allowed us to obtain some statistical distributions for the walk with a memory value µ ? O(N). Moreover, in this study we obtain interesting and useful numerical results to explain the presence of some specific attractors in deterministic walk in one-dimensional space and the absence of attractors with periods 2µ+1, 2µ+2 and 2µ+3. are not made. In this work, we propose a new implementation of the structure for storing data, the numerical model of the tourist, has allowed us to obtain some statistical distributions for the walk with a memory value ? over and above what had been achieved previously. With these results, we verifed the efficiency of the HL structure proposed, and advance knowledge about the behavior of the tourist walk in the order of N.

Considere um meio desordenado constituído por $N$ pontos cujas coordenadas são geradas aleatoriamente de maneira uniforme e independente nas arestas unitárias de um hipercubo $d$-dimensional. As probabilidades de vizinhança entre os pares de pontos deste meio são expressas através da fórmula de Cox. Um caminhante parte de um dado ponto deste meio desordenado e se movimenta obedecendo à regra determinista de ir para o ponto mais próximo que não tenha sido visitado nos últimos $\\mu$ passos. Este processo foi denominado de caminhada determinista do turista. Cada trajetória gerada por esta dinâmica possui uma parte inicial não-periódica de $t$ passos (transiente) e uma parte final periódica de $p$ passos (atrator). Neste trabalho, obtemos analiticamente algumas distribuições estatísticas para a caminhada determinista do turista com memória $\\mu$ arbitrária em sistemas unidimensionais e com memória $\\mu=2$ no modelo Random Link (que corresponde ao limite $d ightarrow 1$). Estes resultados nos permitiram compreender o papel da memória no comportamento exploratório do turista e explicar a equivalência não-trivial entre o modelo Random Link e o modelo Random Map (que é um caso limite das redes de Kauffman). Enfatizamos que o número de pontos explorados pelo turista é a grandeza fundamental nos problemas considerados. As distribuições analíticas obtidas foram validadas através de experimentos numéricos. Também obtivemos uma dedução alternativa para a fórmula de Cox, apresentando os resultados finais em termos de distribuições estatísticas elementares. / Consider a medium characterized by $N$ points whose coordinates are randomly and independently generated by a uniform distribution along the unitary edges of a $d$-dimensional hypercube. The neighborhood probabilities between any pair of points in this medium are given by the Cox formula. A walker leaves from each point of this disordered medium and moves according to the deterministic rule to go the nearest point which has not been visited in the preceding $\\mu$ steps. This process has been called the deterministic tourist walk. Each trajectory generated by this dynamics has an initial non-periodic part of $t$ steps (transient) and a final periodic part of $p$ steps (attractor). In this work, we obtain analytically some statistical distributions for the deterministic tourist walk with arbitrary memory $\\mu$ in one-dimensional systems and with memory $\\mu=2$ in the random link model (which corresponds to $d ightarrow 1$ limit). These results enable us to understand the main role played by the memory on the tourist\'s exploratory behavior and explain the non-trivial equivalence between the random link model and the random map model (which is a limiting case of the Kauffman model). We stress that the number of explored points is the fundamental quantity in the considered problems. The obtained distributions have been validated by numerical experiments. We also obtain an alternative derivation for the Cox formula, writing the final results in terms of known statistical distributions.