Análise de Agrupamentos Com Base na Teoria da Informação: Uma Abordagem Representativa

Currently, one of the biggest challenges for the field of data mining is to perform cluster analysis on complex data. Several techniques have been proposed but, in general, they can only achieve good results within specific areas providing no consensus of what would be the best way to group this kind of data. In general, these techniques fail due to non-realistic assumptions about the true probability distribution of the data. Based on this, this thesis proposes a new measure based on Cross Information Potential that uses representative points of the dataset and statistics extracted directly from data to measure the interaction between groups. The proposed approach allows us to use all advantages of this information-theoretic descriptor and solves the limitations imposed on it by its own nature. From this, two cost functions and three algorithms have been proposed to perform cluster analysis. As the use of Information Theory captures the relationship between different patterns, regardless of assumptions about the nature of this relationship, the proposed approach was able to achieve a better performance than the main algorithms in literature. These results apply to the context of synthetic data designed to test the algorithms in specific situations and to real data extracted from problems of different fields

Não-extensividade em percolação por ligações de longo - alcance

A linear chain do not present phase transition at any finite temperature in a one dimensional system considering only first neighbors interaction. An example is the Ising ferromagnet in which his critical temperature lies at zero degree. Analogously, in percolation like disordered geometrical systems, the critical point is given by the critical probability equals to one. However, this situation can be drastically changed if we consider long-range bonds, replacing the probability distribution by a function like . In this kind of distribution the limit α → ∞ corresponds to the usual first neighbor bond case. In the other hand α = 0 corresponds to the well know "molecular field" situation. In this thesis we studied the behavior of Pc as a function of a to the bond percolation specially in d = 1. Our goal was to check a conjecture proposed by Tsallis in the context of his Generalized Statistics (a generalization to the Boltzmann-Gibbs statistics). By this conjecture, the scaling laws that depend with the size of the system N, vary in fact with the quantitie

Segmentação Fuzzy de Texturas e Vídeos

The segmentation of an image aims to subdivide it into constituent regions or objects that have some relevant semantic content. This subdivision can also be applied to videos. However, in these cases, the objects appear in various frames that compose the videos. The task of segmenting an image becomes more complex when they are composed of objects that are defined by textural features, where the color information alone is not a good descriptor of the image. Fuzzy Segmentation is a region-growing segmentation algorithm that uses affinity functions in order to assign to each element in an image a grade of membership for each object (between 0 and 1). This work presents a modification of the Fuzzy Segmentation algorithm, for the purpose of improving the temporal and spatial complexity. The algorithm was adapted to segmenting color videos, treating them as 3D volume. In order to perform segmentation in videos, conventional color model or a hybrid model obtained by a method for choosing the best channels were used. The Fuzzy Segmentation algorithm was also applied to texture segmentation by using adaptive affinity functions defined for each object texture. Two types of affinity functions were used, one defined using the normal (or Gaussian) probability distribution and the other using the Skew Divergence. This latter, a Kullback-Leibler Divergence variation, is a measure of the difference between two probability distributions. Finally, the algorithm was tested in somes videos and also in texture mosaic images composed by images of the Brodatz album

Dinâmica e estrutura de redes complexas no modelo de afinidade

In this work we elaborate and discuss a Complex Network model which presents connectivity scale free probability distribution (power-law degree distribution). In order to do that, we modify the rule of the preferential attachment of the Bianconi-Barabasi model, including a factor which represents the similarity of the sites. The term that corresponds to this similarity is called the affinity, and is obtained by the modulus of the difference between the fitness (or quality) of the sites. This variation in the preferential attachment generates very interesting results, by instance the time evolution of the connectivity, which follows a power-law distribution ki / ( t t0 )fi, where fi indicates the rate to the site gain connections. Certainly this depends on the affinity with other sites. Besides, we will show by numerical simulations results for the average path length and for the clustering coefficient

Universaidade em sistemas da mecâniaestatística de não equilíbrio com estados absorventes e percolação geográfica

Complex systems have stimulated much interest in the scientific community in the last twenty years. Examples this area are the Domany-Kinzel cellular automaton and Contact Process that are studied in the first chapter this tesis. We determine the critical behavior of these systems using the spontaneous-search method and short-time dynamics (STD). Ours results confirm that the DKCA e CP belong to universality class of Directed Percolation. In the second chapter, we study the particle difusion in two models of stochastic sandpiles. We characterize the difusion through diffusion constant D, definite through in the relation h(x)2i = 2Dt. The results of our simulations, using finite size scalling and STD, show that the diffusion constant can be used to study critical properties. Both models belong to universality class of Conserved Directed Percolation. We also study that the mean-square particle displacement in time, and characterize its dependence on the initial configuration and particle density. In the third chapter, we introduce a computacional model, called Geographic Percolation, to study watersheds, fractals with aplications in various areas of science. In this model, sites of a network are assigned values between 0 and 1 following a given probability distribution, we order this values, keeping always its localization, and search pk site that percolate network. Once we find this site, we remove it from the network, and search for the next that has the network to percole newly. We repeat these steps until the complete occupation of the network. We study the model in 2 and 3 dimension, and compare the bidimensional case with networks form at start real data (Alps e Himalayas)

Estudo da transição de fase da percolação através da entropia da informação

Various physical systems have dynamics that can be modeled by percolation processes. Percolation is used to study issues ranging from fluid diffusion through disordered media to fragmentation of a computer network caused by hacker attacks. A common feature of all of these systems is the presence of two non-coexistent regimes associated to certain properties of the system. For example: the disordered media can allow or not allow the flow of the fluid depending on its porosity. The change from one regime to another characterizes the percolation phase transition. The standard way of analyzing this transition uses the order parameter, a variable related to some characteristic of the system that exhibits zero value in one of the regimes and a nonzero value in the other. The proposal introduced in this thesis is that this phase transition can be investigated without the explicit use of the order parameter, but rather through the Shannon entropy. This entropy is a measure of the uncertainty degree in the information content of a probability distribution. The proposal is evaluated in the context of cluster formation in random graphs, and we apply the method to both classical percolation (Erd¨os- R´enyi) and explosive percolation. It is based in the computation of the entropy contained in the cluster size probability distribution and the results show that the transition critical point relates to the derivatives of the entropy. Furthermore, the difference between the smooth and abrupt aspects of the classical and explosive percolation transitions, respectively, is reinforced by the observation that the entropy has a maximum value in the classical transition critical point, while that correspondence does not occurs during the explosive percolation.

Estudo da transição de fase da percolação através da entropia da informação

Various physical systems have dynamics that can be modeled by percolation processes. Percolation is used to study issues ranging from fluid diffusion through disordered media to fragmentation of a computer network caused by hacker attacks. A common feature of all of these systems is the presence of two non-coexistent regimes associated to certain properties of the system. For example: the disordered media can allow or not allow the flow of the fluid depending on its porosity. The change from one regime to another characterizes the percolation phase transition. The standard way of analyzing this transition uses the order parameter, a variable related to some characteristic of the system that exhibits zero value in one of the regimes and a nonzero value in the other. The proposal introduced in this thesis is that this phase transition can be investigated without the explicit use of the order parameter, but rather through the Shannon entropy. This entropy is a measure of the uncertainty degree in the information content of a probability distribution. The proposal is evaluated in the context of cluster formation in random graphs, and we apply the method to both classical percolation (Erd¨os- R´enyi) and explosive percolation. It is based in the computation of the entropy contained in the cluster size probability distribution and the results show that the transition critical point relates to the derivatives of the entropy. Furthermore, the difference between the smooth and abrupt aspects of the classical and explosive percolation transitions, respectively, is reinforced by the observation that the entropy has a maximum value in the classical transition critical point, while that correspondence does not occurs during the explosive percolation.