Model of Statistical Dependence of Sample Distributions Using Nearest Neighbor Graphs and the Kullback–Leibler Divergence
摘要
This paper presents the results of numerical modeling of the distribution of the nearest neighbor graphs (NNGs) of by the number of connected components and vertices by degrees for the case when the distances between objects are not symmetric. The objects are discrete probability distributions and the distances between them are calculated using the Kullback–Leibler divergence. Estimates of the probability that a set of probability distributions is formed by statistically dependent objects are numerically obtained. The numerical algorithm for constructing a benchmark of the probabilities of realizing a certain NNG structure is based on the fact that, up to isomorphism, this structure does not depend on the distribution of distances between objects. An algorithm for collecting the sample statistics of the NNGs for arbitrary random asymmetric matrices, whose elements are treated as distances, is described. An example of the analysis of big data distributions obtained as a result of the automatic processing of a corpus of more than 100 000 literary texts by 8500 authors in Russian is considered. The corpus is structured according to the authors in the form of n-grams of letter combinations. The example is interesting because the n-gram distributions make it possible to accurately identify the author of a single text, so that the reference author distributions can be considered as a basis. In the exact sense of linear algebra, the vectors of the author’s standards are linearly independent. At the same time, it turned out that these vectors are statistically dependent with a probability practically equal to 1, which allows additional structuring of the data array. The results obtained in the L1 histogram norm for the same distributions are also compared, and it is shown that the benchmark for asymmetric distances allows obtaining an answer at a higher level of confidence in this example.