АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. B) Числа
  2. IV. Алгоритм действий командира (начальника) при увольнении военнослужащего в связи с невыполнением им условий контракта
  3. N-декомпозируемые отношения. Пример декомпозиции. Зависимость проекции/соединения.
  4. SCSI-1 В ОБЩИХ ЧЕРТАХ
  5. V. Регламент переговоров по поездной радиосвязи
  6. А потом он обратился к ним с увещанием в связи с тем, что они смеялись, когда кто-нибудь испускал ветры, и сказал: «Почему некоторые из вас смеются над тем, что делают и сами?»
  7. Алгоритм, использующий разложение числа на простые множители
  8. Алфавит Maple-языка и его синтаксис. Основные объекты (определение, ввод, действия с ними). Числа. Обыкновенные дроби.
  9. Анализ взаимосвязи спроса и предложения
  10. Анализ взаимосвязи уровня социального интеллекта и самооценки в подростковом возрасте
  11. Анализ и связи понятия Паразит
  12. Анализ относительных показателей (коэффициентов) - расчет отношений между отдельными позициями отчета или позициями разных форм отчетности, определение взаимосвязи показателей.

Изучим характер зависимости между величиной связи 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.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | 101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 | 126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)