Зависимость связи l_0 от числа общих имен в определяющих окрестностях

Изучим характер зависимости между величиной связи L_0 двух определяющих окрестностей Д_r и Д_s и количеством общих имен в этих окрестностях (с учетом кратности вхождения имен в Д_r и Д_s).

Определение.

Числом общих имен двух определяющих окрестностей Д_r(k) и Д_s(k) в списке Х (с учетом кратностей) назовем число:

r+k s+k

O(Д_r, Д_s) = д(a_i, a_j),

i=r-k j=s-k

где д(a_i, a_j)=1 если a_i=a_j (то есть имена a_i и a_j одинаковы) и равно нулю иначе.

Другими словами, O(Д_r, Д_s) – это число пар из декартового произведения Д_r x Д_s, таких, что в паре стоят одинаковые имена.

В рассмотренных нами случаях реальных хронологических списков, описывающих древнюю и средневековую историю Европы, обнаружилось весьма примечательное обстоятельство:

Значения L_0(Д_R, Д_S) И O(Д_R, Д_S) связаны между собой таким образом, что при увеличении O(Д_R, Д_S) увеличивается (в статистическом смысле) и L_0(Д_R, Д_S).

Этот вывод был получен на основе сравнения гистограмм частот значений L0(Д_r, Д_s) при условии, что значение O(Д_r, Д_s) фиксировано.)

Может показаться, что значение связи L0(Дr, Д_s) увеличивается при увеличении O(Д_r, Д_s) непосредственно за счет общих имен в Д_r и Д_s (механизмы, приводящие к такому увеличению даже в правильных списках действительно существуют, но они очень слабы). Однако это не так. Чтобы показать это, введем еще две меры связи определяющих окрестностей Д_r и Д_s в хронологическом списке Х.

Пусть дана пара определяющих окрестностей Д_r и Д_s в списке Х. Определим соответствующие разреженные определяющие окрестности следующим образом:

Д'_r = множество различных имен из Д_r;

Д'_s = множество различных имен из Д_s;

Д»_r, s = множество имен из Д'_r, не совпадающих ни с какими именами из Д_s;

Таким образом, окрестности Д_r, Д'_s и Д»_r, s разрежены таким образом, что в них не осталось различных имен. Кроме того, окрестность Д_r, s не содержит имен, общих с Д_s или с Д'_s.

Определение.

Положим c

L1(Дr, Д_s) – ____________________Д l(a, b),

|Д'_r|x|Д'_s| aД_r, bД'_s c

L (Д_r, Д_s) – ____________________Д l(a, b).

|Д»_r, s|x|Д'_s| aД»_r, s, bД'_s

Здесь через |ч| обозначена длина (разреженной) определяющей окрестности, то есть число имен в ней.

Легко проверить, что определенная таким образом величина связи L_2 не зависит от порядка определяющих окрестностей:

L2(Дr, Д_s) – L_2(Д_s, Д_r).

Величина связи L2(Дr, Д_s) уже не связана напрямую с общими именами в Д_r и Д_s – эти имена в ее определении вообще не участвуют. Оказалось однако, что для реальных списков, относящихся к древней и средневековой истории Европы, зависимость связи L_2(Д_r, Д_s) от O(Д_r, Д_s) остается прежней (такой же, как и описанная выше зависимость L_0(Д_r, Д_s) от O(Д_r, Д_s)). То же верно и для связи L_1(Д_r, Д_s).

Итак, в примерах, относящихся к древней и средневековой истории Европы (о них – ниже) было обнаружено, что в основе двух внешне не связанных друг с другом величин L2(Дr, Д_s) и O(Д_r, Д_s) лежит некий общий фактор (общая причина), приводящий к их статистической зависимости.

Таким фактором может являться наличие дубликатовв хронологических списках имен. В самом деле, как было показано выше, дублирующие друг друга определяющие окрестности в хронологическом списке имеют (в среднем) повышенное значение связи L_0. То же верно и для связей L_1, L_2.

Но с другой стороны, и значение O(Д_r, Д_s) для них должно быть в среднем выше, чем для пар независимых определяющих окрестностей, так как дубликаты иногда (не далеко не всегда!) используют одни и те же имена (точнее: использут одинаковые имена чаще, чем недубликаты, что и приводит к повышению значения O(Д_r, Д_s)). Таким образом, присутствие в списке Х дубликатов приводит к прямой зависимости (в статистическом смысле) величины L_2(Д_r, Д_s) от O(Д_r, Д_s). Эту зависимость мы и обнаруживаем в упомянутых примерах.

Замечание.

Может показаться, что для различения дубликатов в хронологических списках можно было бы использовать значения O(Д_r, Д_s) с тем же успехом, что и L_0(Д_r, Д_s). Отметим, что подсчет O(Д_r, Д_s) вычислительных сложностей не представляет какова бы ни была длина списка (т. к. сложность его вычисления вообще не зависит от длины списка).

Между тем, вычисление связей L_0, L_1 или L_2 для реальных списков, которые содержат сотни и тысячи имен, требует многочасовых вычислений на современных ЭВМ (сложность их вычисления пропорциональна квадрату длины списка).

Однако, использование O(Д_r, Д_s) в качестве меры связи отрезков списка, дает слишком «зашумленную» картину и не позволяет, в реальных примерах, надежно определить дубликаты в нем. Дело в следующем. Если O(Д_r, Д_s) велико, то, как правило, велико и значение L_0, L_1 или L_2.

Но обратное верно далеко не всегда. При больших значениях связи L_0, L_1 или L_2 соответствующее значение O(Д_r, Д_s) часто оказывается небольшим. Это означает, что дубликаты в значительной доле случаев используют различные имена для обозначения одних и тех же деятелей (иначе они были бы все видны «на глаз»). Использование же связей типа L_0 позволяет «выжать» из хронологического списка ту информацию о его структуре, которая на глаз не видна и определить дубликаты даже в том случае если все имена, используемые в них, попарно различны.

Для всех рассмотренных нами хронологических списков использование связей L_0, L_1 и L_2 приводило к одному и тому же виду ответа (обнаруживались одни и те же системы дубликатов). Поэтому мы будем иногда говорить просто о связи L, подразумевая под этим одну из связей L_0, L_1 или L_2.

5. Различение зависимых и независимых пар определяющих окрестностей
в хронологических списках имен

Перейдем к описанию способа определения порогов в множестве значений связи L(_r, _s), разделяющих зависимые и независимые пары определяющих окрестностей _r, _s. Приводимые ниже рассуждения имеют качественный характер. Они оправдываются aposteriori, так как позволяют получить более четкую картину структуры списка.

Важно, что наиболее существенные черты этой картины оказываются (во всех рассмотренных нами реальных примерах) нечуствительными не только к выбору параметров модели k и p (а также к приведенным выше изменениям в определении самой связи, что уже отмечалось), но и к колебаниям указанных порогов.

Пусть дан хронологический список имен Х. Зафиксируем для него параметры модели (k, p) и построим набор гистограмм частот появления значений связи L_0(_r, _s) (L_1 или L_2), при условии, что значение O(_r, _s) постоянно (для каждой из гистограмм оно свое). В рассмотренных нами реальных списках все эти гистограммы имели вид приблизительно как на рис. 28.

В качестве значения порога, отделяющего связь L_0 (L_1, L_2) для независимых пар определяющих окрестностей (_R, _S) от связи для зависимых пар (_R, _S) возьмем наименьшее значение, при котором соответствующая гистограмма падает до нуля (это значение для каждой пары (_R, _S), вообще говоря, свое, т. к. оно зависит от величины O(_R, _S)).

Связь, превосходящую такой порог, будем называть существенной связью, а связь, не превосходящую его – несущественной связью.

Определение.

Матрицей связей M(k, p, L_i, Х), 0, хронологического списка имен Х называется построенная по этому списку квадратная верхнетреугольная матрица размера (n-k)(n-k), в ячейке (r, s) которой стоит значение M_r, s.