2.3. Периодический закон Менделеева [65]

Согласно философии Data Mining обнаружение закономерностей одной из своих целей имеет отображение данных из исходного пространства описания  в некоторое другое пространство , более удобное для восприятия человеком.

Пространство описывающих характеристик  может быть произвольным — любой размерности, с любым числом объектов наблюдения. Пространство же восприятия должно отвечать некоторым условиям, вытекающим из ограниченных возможностей человеческой системы восприятия информации. Одно из таких ограничений связано с размерностью пространства : она не должна быть большой, так как объектами в многомерном пространстве человек оперирует с большим трудом. При большом количестве объектов восприятие облегчается, если эти объекты отобразить в малоразмерное пространство , в котором объекты оказываются упорядоченными по их свойствам. При этом можно обнаружить наиболее легко воспринимаемые человеком линейные зависимости свойств  от свойств . Если глобальной линейной зависимости во всем диапазоне значений  добиться не удается, то можно попытаться воспользоваться суперпозицией локальных линейных зависимостей.

Сформулируем принцип локальной линейной гладкости : «Свойства  в -окрестностях точки  пространства  меняются по линейному закону, так что свойства объекта в точке  равны среднему значению свойств его левого и правого соседей: ». Пользуясь этим принципом, можно для некоторого множества  сконструировать пространство восприятия . Покажем это на простом числовом примере.

Пусть множество  состоит из семи объектов, свойство  которых указано в табл. 11. Построим одномерное пространстве восприятия  с целочисленными значениями координаты . Поместим в точку  любой объект, например . Подберем к нему ближайшего левого соседа по свойству . Это, очевидно, будет объект . Из приведенного выше соотношения можно найти ожидаемые (прогнозные) свойства правого соседа: . Этим соседом оказывается объект . Разместим найденные три объекта рядом друг с другом по оси  (см. рис. 37).

Таблица 11. Объекты множества  в пространстве описания

Теперь можно предсказать соседей для крайних из этих элементов: левого для  и правого для . Соседом  должен быть объект со свойством . Объекта с точно таким значением  нет. Ближайшим к нему оказывается объект . Условимся считать, что разница 8 — 7,9 = 0,1 меньше допустимого порога нарушения гладкости (например, 0,3), и поставим объект  справа от объекта .

Прогнозное значение свойства  у левого соседа объекта  равно 4. Ближайшее к нему значение  у объекта  равно 3,2. Отклонение в 0,8 превышает заданный порог, и мы приходим к заключению, что ближайший левый сосед для объекта  в таблице отсутствует. Предположим, что в природе такой объект с  существует и он случайно не попал в таблицу. Поставим его условно слева от  (пунктир на рис. 37) и продолжим процедуру. Соседом слева от условного элемента является объект , его левым соседом будет , а его левым соседом . Все объекты табл. 11 нашли на оси  свое место. Теперь легко видеть, что если объект  поместить в точку , то между свойствами  и  существует простая закономерность: .

Рис. 37

Если объекты множества  обладают числом свойств, большим чем одно, то прогноз и подбор соседей нужно делать по всем этим свойствам. В случае двумерного пространства восприятия  соседями объекта  являются четыре объекта: сосед слева , справа , сверху  и снизу . Связь их свойств определяется соотношением

Процедура двумерного линейного упорядочения аналогична той, что описана выше для одномерного случая: выбор начального элемента  и ближайших к нему двух соседей слева и сверху. Затем прогноз свойств двух соседей — справа и снизу, подбор объектов, свойства которых отличаются от прогнозных не более чем на заданную величину, установка этих объектов на свои места и прогноз новых соседей. На каждом шаге устанавливается только один объект, самый близкий к прогнозу, и после этого прогнозы всех соседей повторяются.

На этом принципе построен алгоритм ПАМИР [65], предназначенный для решения задач многомерного упорядочения. С помощью программы ПАМИР был проведен ряд экспериментов по двумерному упорядочению объектов  различной физической природы. В табл. 12 и 13 показаны множества объектов с целочисленными значениями одного свойства  и наилучший их порядок на двумерной плоскости . Наилучшим считается такой вариант, при котором сумма локальных отклонений от линейной зависимости минимальна. Если истинные значения свойств объекта  равны , а его прогнозные свойства оказались равными , то отклонения от линейной зависимости для всех  объектов имеют значения

Пусть нам дано множество , описанное характеристикой : 4, 8, 3, 12, 9, 7, 6, 7, 10, 2, 8, 7, 11, 4, 9, 6, 7, 7, 5, 10, 6, 11, 8, 5, 4, 5, 9, 7, 3, 6, 9, 6, 10, 8, 9. Применение алгоритма ПАМИР позволило отобразить это множество в двумерное пространство восприятия , представленное в табл. 12.

Таблица 12. Двумерное упорядочение множества объектов

В табл. 13 представлен результат аналогичной обработки множества объектов , описанных свойством : 18, 30, 2, 8, 15, 12, 2, 4, 24, 10, 6, 16, 6, 9, 24, 15, 6, 20, 4, 18, 5, 12, 25, 4, 36, 12, 1, 10, 3, 3, 5, 12, 8, 30.

Таблица 13. Двумерное упорядочение множества объектов

Закономерность, легко наблюдаемая в табл. 12, выражается формулой , а в табл. 13  формулой .

Напрашивается вывод, что исходный набор объектов «не полон», отсутствующие объекты должны были бы занять места пустых клеточек в таблицах. Свойства этих «зкообъектов» легко прогнозируются по приведенным выше интерполяционным формулам.

Возможности алгоритма ПАМИР были испытаны в экспериментах по переоткрытию периодического закона Менделеева.

Множество  было представлено химическими элементами первых семи рядов — с 1-го (водород) по 54-й (ксенон). Пространство описания включало в себя лишь три свойства элементов:  — атомный вес,  — валентность по кислороду и  — валентность по водороду. В качестве пространства восприятия была использована плоскость с дискретными значениями переменных   и . Для каждого элемента определялось восемь соседей, как показано на рис. 38. Программа может анализировать гладкость по двум, четырем или восьми направлениям.

Рис. 38

В табл. 14 представлен результат работы программы ПАМИР. В качестве начального был выбран элемент с атомным весом 15 (фосфор). Рамкой показана граница таблицы в стандартном современном представлении [130]. Отклонения от стандартного вида имеют место для элементов длинного ряда VI группы VIII (элементы 44, 45 и 46).

Таблица 14. Двумерное упорядочение химических элементов

В табл. 15 показан результат упорядочения множества элементов таблицы с 1-го по 54-й за исключением крайних элементов длинных рядов (27, 28, 45, 46), а также элементов 12, 22, 35 и 39, которые были не известны во времена Менделеева. Программа, начав с элемента 17, расставила все элементы на те места, которые они занимают в таблице Менделеева, оставив пустые клетки в местах, соответствующих пропущенным элементам. Свойства пропущенных элементов легко можно найти по интерполяционным формулам, как это и делал Д. И. Менделеев.

Таблица 15. Результат упорядочения неполного множества элементов

Как видно из этих примеров, если столбцам в табл. 14 и 15 сопоставить номера групп, а строкам — номера рядов, то результат программы ПАМИР почти совпадает с результатом, полученным Д. И. Менделеевым. Однако следует отметить существенные различия в пространствах , использованных Менделеевым и программой ПАМИР. Д. И. Менделеев, кроме атомного веса и валентностей, использовал большое число других химических и физических свойств элементов: виды соединений с хлором, растворимость сернистых соединений, температуру плавления, цвет, запах летучих соединений и многое другое [97,122]. Все эти глубокие знания облегчали ему поиск «соседей» при упорядочивании элементов. Следует отметить, что задача группировки ряда элементов решалась еще и предшественниками Менделеева. Так, было известно, что в одну группу следует относить элементы с современными номерами: 7-15-33-51; 8-16-34-52; 9-17-53; 20-38-56 и т. д. Подсказка такого рода могла бы существенно облегчить работу программы ПАМИР.

С другой стороны, машина использовала современные данные об атомных весах. До Менделеева атомные веса были известны неточно, ему приходилось исправлять их путем предсказания на основании всей таблицы. Ошибки в значениях атомных весов могут существенно исказить упорядочение, если использовать такое бедное описание свойств , которое использовала программа.

Результаты данной работы можно сформулировать так: принцип локальной гладкости является эффективным средством отображения пространства описания  в пространство восприятия . Свойствами локальной гладкости обладают пространства восприятия, построенные для многих известных законов природы — законов Ома, Ньютона, Менделя, Менделеева и др. Этот принцип должен найти свое заметное место в ряду концептов, используемых в алгоритмах обнаружения закономерностей или DM.

Если пространство описания  наблюдаемых объектов множества  достаточно информативно, чтобы можно было построить пространство восприятия  со свойством локальной гладкости, то сам процесс построения пространства  с помощью ЭВМ принципиальных затруднений не вызывает. Это тем более справедливо для таких удачно найденных пространств , для которых пространство  удовлетворяет свойству глобальной линейной гладкости.