Модель статистической зависимости выборочных распределений с использованием графов ближайших соседей и расстояния Кульбака-Лейблера

А. А. Кислицын

Институт прикладной математики им. М.В. Келдыша РАН

Аннотация: Представлены результаты численного моделирования распределения графов ближайших соседей по числу компонент связности и вершин по степеням для случая, когда расстояния между объектами не симметричны. Объектами являются дискретные распределения вероятностей, расстояния между которыми вычисляются в квазинорме Кульбака-Лейблера. Численно получены оценки вероятности того, что совокупность вероятностных распределений образована статистически зависимыми объектами. Численный алгоритм построения бенчмарка вероятностей реализации определенной структуры графа ближайших соседей основан на том, что с точностью до изоморфизма эта структура не зависит от распределения расстояний между объектами. Описывается алгоритм сбора выборочных статистик графов ближайших соседей для произвольных случайных несимметричных матриц, элементы которых трактуются как расстояния. Рассмотрен пример анализа распределений больших данных, полученных в результате автоматической обработки корпуса из более чем 100 тыс. литературных текстов 8.5 тыс. авторов на русском языке. Корпус структурирован по авторам в виде $n$-грамм буквосочетаний. Пример интересен тем, что распределения $n$-грамм позволяют достаточно точно идентифицировать автора отдельного текста, так что эталонные авторские распределения можно рассматривать как базис. В точном смысле линейной алгебры векторы авторских эталонов линейно независимы. В то же время оказалось, что эти векторы статистически зависимы с вероятностью, практически равной 1. Это позволяет провести дополнительное структурирование массива данных. Также проведено сравнение с результатами, получаемыми в гистограммной норме L1 для тех же распределений, и показано, что бенчмарк для несимметричных расстояний позволяет в данном примере получить ответ на большем уровне доверия.

Ключевые слова: граф ближайших соседей, распределение степеней вершин, кластеризация, расстояние Кульбака-Лейблера, критерий зависимости данных, идентификация автора текста.

Поступила в редакцию: 09.09.2024
Исправленный вариант: 09.09.2024
Принята в печать: 14.10.2024

DOI: 10.20948/mm-2025-02-14