МЕТОДИКА РАСПОЗНАВАНИЯ ДУБЛИКАТОВ И НЕКОТОРЫЕ ПРИЛОЖЕНИЯ
1. Пусть в евклидовом пространстве Rn задано конечное множество точек D и многозначное отображение V: Rn ? Rn, переводящее D в большее (конечное) множество V(D). Например, V может моделировать многократный процесс измерений случайной величины ? ? D, результаты которого неоднозначны вследствие случайных ошибок; V(D) можно рассматривать как множество значений, полученных в результате измерений. При этом каждое реальное значение x величины ? превращается в множество точек V(x), представляющих исходное значение х; каждую точку из V(х) можно рассматривать как приближенное значение для х. При изучении реальных процессов трудность заключается в правильном моделировании (с помощью V) реальных ошибок. Пусть теперь D неизвестно, и мы знаем только множество V(D) "результатов измерений". Как распознать среди точек V(D) те из них, которые отвечают одной точке из D? Точки, отвечающие одному и тому же реальному значению, назовем дубликатами. Пусть V таково, что V(x) ?V(y)= ?, если x? y.
2. Введем меру удаленности друг от друга точек из V(D), стремясь к тому, чтобы точки, принадлежащие одному и тому же V(x), были достаточно близки в смысле меры ?, а точки из разных V(x) и V(y), напротив, были далеки. Пусть a, b ? V(D). Фиксируем точку a и построим специальную окрестность Hr, точки a. Будем стремиться к тому, чтобы точка a была центром Hr, а точка b была на границе Hr или близко к границе. Простейший вариант такой: Hr' = {с ? Rn : |ai- сi | No |ai- bi |, 1 No i No n}, т.е. Hr' - параллелепипед с центром в a, имеющий точку b одной из своих вершин.
Для того чтобы эта конструкция стала пригодной для приложений, нужно дополнить ее, чтобы она моделировала механизм ошибок, влияющих на измерения. Ниже мы предъявим такую окрестность Hr (a, b), введем меру ? удаленности точек a и b друг от друга, положив в основу определения схему, изложенную в [1], а именно: ?(a,b) = vol Hr(a,b)/vol V(D), где vol V(D) - число точек в множестве V(D), а vol Hr(a,b) - число точек из V(D), попавших в Hr(a,b).
3. Опишем задачу, для решения которой вводится эта мера ?. Пусть обнаружен исторический текст, описывающий неизвестную нам династию правителей с указанием длительности их правлений. Является ли эта династия новой, ранее не встречавшейся, или это - одна из известных династий, но описанная в непривычных терминах (видоизмененные имена и т.д.)? Рассмотрим n последовательных разных правителей (р. династию) с истинными длительностями правлений (p1 , p2, ... pn ); часто одна и та же р. династия описывается в разных первоисточниках с разных точек зрения. Но существуют "инвариантные факты", описания которых мало зависят от автора текста, например, длительность правления: обычно нет особых причин, по которым автор значительно исказил бы это число. Тем не менее часто возникали трудности в вычислении длительностей правлений, приведшие к тому, что в разных документах для одного и того же правителя приводятся разные числа.
Итак, каждый автор, описывая р. династию, p = (p1 , p2, ... pn ), по-своему вычисляет длительности правлений и получает последовательность чисел a = (a1 , a2, ... an ), где ai - длительность правления правителя с номером i. Эту последовательность чисел (вектор a? Rn) назовем числовой династией (ч. династией). Другой автор, описывая эту же р. династию, получит, возможно, другой вектор b? Rn. Итак, одна и та же р. династия может изображаться разными ч. династиями.
Пусть D = {p = (p1 , p2, ... pn )} - достаточно большое множество р. династий длины n. Модель (гипотеза): если две ч. династии близки (в смысле меры ?), то они изображают одну и ту же р. династию, являются двумя вариантами ее описания (такие ч. династии назовем зависимыми); если же две ч. династии изображают две различные р. династии, то ч. династии значительно отличаются друг от друга (тогда назовем их независимыми). Перед проверкой модели дадим точное определение ?, отождествив множество всех ч. династий, описывающих р. династии из множества D ? Rn, с множеством V(D).
4. Укажем ошибки, чаще всего приводившие к разногласиям в определении длительностей правлений: а) перестановка (путаница) двух соседних правителей, б) замена двух правителей одним, длительность правления которого равна сумме длительностей их правлений, в) неточность в вычислении длительности правления: чем она больше, тем больше и ошибка в ее вычислении. Эти три основных типа ошибок можно описать при помощи подходящего отображения V: D ?Rn. Пусть p?D ; вектор c назовем виртуальной вариацией вектора p, c=v(p), если каждая координата ci вектора с совпадает либо с одной из следующих трех координат вектора p: p-i-1 , p-i, p-i+1, либо с числом p-i + p-i+1. Ясно, что каждый вектор c = v(p) можно рассматривать как ч. династию, получившуюся из р. династии в результате первых двух типов ошибок: а) и б).
Положим V(D) - объединение всех векторов c=v(p), где p?D. Осталось смоделировать ошибку типа в). Пусть на положительной полуоси t T 0 задана кусочно-гладкая функция ?(t) T 0 (у нас роль ?(t) будет играть плотность вероятностей случайной величины ?, см. ниже). Положим H(?(t)) = h(t), где H(s) - монотонно убывающая функция на полуоси s T 0, lim[s?+0] = +?, например, H(s) = 1/s. Если ? - дискретная случайная величина, то h(t) тем больше, чем с меньшей вероятностью ? принимает значение t. Пусть t - длительность правления, ?(t) - число правителей, правивших t лет. В [1], стр. 115, приведена вычисленная автором экспериментальная гистограмма частот. Если t - значение, принимаемое ? с большой вероятностью, то амплитуда ошибок h уменьшается (небольшие длительности правлений лучше поддавались вычислению, чем редкие - большие длительности).
Укажем функцию h(t) для плотности вероятностей случайной величины - длительности правления ([1], стр. 115). Разобьем отрезок (0, 100) целочисленной оси t на отрезки (10t, 10t + 9), 0 No t No 9. Тогда h(t) = 2 при t = 0,1; h(t) = 3 при t = 2; h(t) = 5 (t-1) при 3 No t No 9. Рассмотрим в Rn параллелепипед П(a, b)=П, ортогональные проекции ?i = ai ? (|ai - bi| + h(ai)) которого на координатные оси в Rn задаются отрезками со следующими концами:
? ai ? (|ai - bi | + 2), 0 No ai < 20,
?i =? ai ? (|ai - bi | + 3), 20 No ai < 30,
? ai ? (|ai - bi | + 5[ai/10] - 1 ), 30 No ai < 100;
здесь [y] - целая часть числа y. Итак, если 0 No ai < 20, то значения ai и bi рассматриваются с точностью до ?1 (т.е. такова ошибка, допускаемая при их измерении), если 20 No ai < 30, то допустимая ошибка равна ?3/2 и т.д.
Осталось смоделировать то, что факт принадлежности точки с ? V(D) к параллелепипеду П можно рассматривать лишь приближенно. Для этого нужно сделать границу П "более размытой", приближенной. Пусть r - фиксированное число. Рассмотрим вектор p?D, для которого по крайней мере r его координат pi попали в проекции ?i параллелепипеда П и некоторая виртуальная вариация которого c = v(p) целиком попала в П. Такие векторы p?D назовем r-близкими к П.
Окончательно определим окрестность Hr(a, b), взяв объединение П и всех виртуальных вариаций векторов p?D, r-близких к П. В качестве ?(a, b) возьмем отношение числа векторов множества V(D), попавших в окрестность Hr(a, b) (при этом не засчитываются виртуальные вариации самих векторов a и b, отличные от a и b) к числу векторов в V(D).
Это число ? имеет вероятностную интерпретацию. В самом деле, построим по множеству V(D) функцию ? плотности вероятностей. Разобьем Rn на стандартные кубы достаточно малого размера так, чтобы ни одна точка из V(D) не попала на границу какого-либо куба. Если x?Rn - внутренняя точка куба, то положим ?(x) = (число точек множества V(D) , попавших в куб)/(число точек V(D)); если x на границе куба, то ?(x) = 0. Ясно, что ?(a, b) является интегралом от функции ? по множеству Hr(a, b) при условии, что Hr (a,b) состоит из кубов нашего разбиения. Поскольку мы моделируем приближенные вычисления, то можно считать это условие выполненным. Число ?(a, b) можно рассматривать как вероятность того, что случайный вектор, распределенный в Rn с функцией плотности ?, попал в окрестность Hr с центром в a и "радиуса" |b - a| + h(a).
5. Для проверки модели п. 3 были использованы хронологические таблицы Ж. Блера [2] и Гинцеля [3], содержащие все сохранившиеся данные о реальных исторических династиях. Мною был составлен полный список всех династий длины n = 15 из истории Европы, Средиземноморья, Ближнего Востока, Египта от 4000 г. до н.э. до 1800 г. н.э. Эти данные были дополнены сведениями из 14 других хронологических таблиц. В получившемся списке D некоторые р. династии представлены несколькими ч. династиями. Укажем основные династии, вошедшие в список D: епископы и папы в Риме, сарацины, первосвященники в Иудее, грекобактрийцы, экзархи в Равенне, все династии Египта, Византии, Римской империи, Испании, России, Франции, Италии, Оттоманской империи, Шотландии, Лакедемона, Германии, Швеции, Дании, Израиля, Вавилона, Сирии, Сициона, Иудеи, Португалии, Парфии, Боспорского царства, Македонии, Польши, Англии. Число векторов в V(D)? R15 равно примерно 15*1011. Если для какой-то пары a, b ? V(D) число ?(a, b) мало, то наблюдаемая близость династий a и b - редкое событие, тем более, чем меньше ?. В качестве r бралось 1 + 2/3n = 11 правилу "двух третей".
Затем был проведен обширный вычислительный эксперимент по определению ?(a, b). Результаты полностью подтвердили модель п. 3: для зависимых ч. династий a, b число ? колеблется от 10-12 до 10-8, а если a и b независимы, то ? не меньше 10-3. Налицо резкое различие (на 5 порядков) между зависимыми и независимыми династиями. Это, очевидно, позволяет решить задачу распознавания ч. династии.
6. Эксперимент обнаружил несколько особых пар a, b (всего несколько десятков из 106 обработанных пар), считавшихся ранее независимыми, но для которых ?(a, b) таково, как и для зависимых пар.
Примеры. 1) Римская империя от 82 г. н.э. до 217 г.н.э. и Римская империя 270-526 гг. н.э., ? = 1,3 * 10-12. 2) Римско-Германская империя 962-1254 гг. н.э. и империя Габсбургов 1273-1619 гг. н.э., ? = 1,2 * 10-12. 3) Две Римские империи 270-553 гг. н.э. и 962-1254 гг. н.э. ? = 2,3 * 10-10. 4) Империя Карла Великого 681-887 гг. н.э. и Восточная Римская империя 333-527 гг. н.э. ? = 8,25 * 10-9.
- --
А.Т.Фоменко. Некоторые статистические закономерности распределения плотности информации в текстах со шкалой. Семиотика и информатика, в. 15. М., 1980, стр. 99.
- --
Ж.Блер. Хронологические таблицы (Brit. Roy. Soc.), м., т. 1-2, 1808.
- --
F.K.Ginzel. Handb. Der Mathematischen und Technischen Chronologie, b. I-III, Leipzig, 1906, 1914.
- --
А.Т. Фоменко. Проблемы механики управляемого движения. Иерархические системы, Межвузовский сб. научн. тр., 1980, стр. 161.
|