Формально описанную выше процедуру можно записать следующей формулой:
D=F({0},{1,...,M}S1).
Множество повышенной надежности в этом случае можно записать в следующем виде:
S1nпн= S1 Х D=F({0},{1,...,M}) Х F({0},{1,...,M} F({0},{1,...,M})).
Очевидно, что последнюю формулу можно обобщить, исключив из первоначального множества признаков найденное ранее множество повышенной надежности и попытавшись найти минимальное множество среди оставшихся признаков. С другой стороны, существуют и множество таких задач, для которых не существует прямых дублей первого рода.
Косвенный дубль первого рода
Для нахождения косвенного дубля первого рода необходимо найти такое множество признаков D из множества M`` = M- M`, которое является минимальным и позволяющим вычислить дублируемые признаки множества M`. При этом в нашем случае необходимо выполнение условия, что существует сеть T({0},D) и S1|D=?. Другими словами, среди множества признаков, не включающего начальное минимальное множество, нужно найти такие признаки, по которым можно восстановит значения признаков начального минимального множества. Схематично процесс формирования косвенного дубля первого рода изображен на рис. 2.
Формально же описанную выше процедуру можно записать следующей формулой:
D=F(S1,{1,...,M}S1).
Множество повышенной надежности в этом случае можно записать в следующем виде:
S1кпн= S1 Х D=F({0},{1,...,M}) Х F({0},{1,...,M}){1,...,M} F({0},{1,...,M})).
Эта формула так же допускает обобщение. Однако следует заметить, что косвенные дубли первого рода встречаются еще реже, чем прямые дубли первого рода. Соотношение между косвенным и прямым дублем первого рода описываются следующей теоремой.
Теорема 1. Если множество D является косвенным дублем первого рода, то оно является и прямым дублем первого рода.
Доказательство. Построим нейронную сеть, состоящую из последовательно соединенных сетей T(S1,D) и T({0},S1), как показано на рис. 3. Очевидно, что на выходе первой сети будут получены те сигналы, которые, будучи поданы на вход второй сети, приведут к получению на выходе второй сети правильного ответа. Сеть, полученная в результате объединения двух сетей T(S1,D) и T({0},S1), является сетью T({0},D). Что и требовалось доказать.
Следствие. Если у множества S1 нет прямого дубля первого рода, то у нее нет и косвенного дубля первого рода
Доказательство. Пусть это не так. Тогда существует косвенный дубль первого рода. Но по теореме 1 он является и прямым дублем первого рода, что противоречит условию теоремы. Полученное противоречие доказывает следствие.
Рис. 1. Процесс формирования ПДПР и набора повышенной надежности
Прямой дубль второго рода
Перенумеруем входные признаки из множества S1={i1,...,ik}, k=|S1|. Множество признаков, являющееся прямым дублем второго рода для признака можно получить, найдя минимальное множество для получения ответа, если из исходного множества входных признаков исключен признак. Таким образом, прямые дубли второго рода получаются следующим образом: Dj=F({0},{1,...,M}{ij}).
Полный прямой дубль второго рода получается объединением всех дублей для отдельных признаков
Множество повышенной надежности для прямого дубля второго рода можно записать в следующем виде:
2nпн= F({0},{1,...,M}) U F({0},{1,...,M}{j}).
j?F({0},{1,...,M})
При формировании прямого дубля второго рода в зависимости от поставленной задачи можно ограничиться несколькими признаками. В этом случае множество повышенной надежности будет складываться из минимального набора признаков плюс прямые дубли второго рода для интересующих нас признаков. Если же прямой дубль второго рода требуется найти лишь для одного признака из минимального множества, то тогда набор повышенной надежности будет состоять из минимального множества и единственного прямого дубля второго рода.
Заметим, что при построении прямого дубля второго рода не требовалось отсутствия в нем всех элементов множества S1, как это было при построении прямого дубля первого рода. Такое снижение требований приводит к тому, что прямые дубли второго рода встречаются чаще, чем прямые дубли первого рода. Более того, прямой дубль первого рода, очевидно, является прямым дублем второго рода. Более точное соотношение между прямыми дублями первого и второго родов дает следующая теорема.
Теорема 2. Полный прямой дубль второго рода является прямым дублем первого рода тогда и только тогда, когда
F({0},{1,...,M}{j}) |F({0},{1,...,M})=?
j?F({0},{1,...,M}) (1)
Доказательство. Построим сеть, состоящую из параллельно работающих сетей, T({0},{1,...,M}{ij}), за которыми следует элемент, выдающий на выход среднее арифметическое своих входов. Такая сеть, очевидно, будет решать задачу, а в силу соотношения (1) она будет сетью T({0},{1,...,M}S1). Таким образом, если соотношение (1) верно, то прямой дубль второго рода является прямым дублем первого рода. Необходимость следует непосредственно из определения прямого дубля первого рода.
Рис. 2. Процесс формирования КДПР и набора повышенной надежности
Рис. 3. Сеть для получения ответа из косвенного дубля
Косвенный дубль второго рода
Косвенный дубль второго рода для признака является минимальным множеством входных признаков, для которых существует сеть T({i1},{1,...,M}{i1}). Другими словами -- это такое минимальное множество признаков, по которому можно восстановить значение признака из минимального множества. При этом этот признак перейдет из разряда «признаков» в разряд «результатов».
Таким образом, прямые дубли второго рода получаются следующим образом: Dj=F({ij},{1,...,M}{ij}).
Полный косвенный дубль второго рода строится как объединение косвенных дублей второго рода для всех признаков первоначального минимального множества (2), а множество повышенной надежности можно выразить формулой (3).
|S1|
D=U F({ij},{1,...,M}{ij}). (2)
j=1
nпн= F({0},{1,...,M}) U F({j},{1,...,M}{j}).
j?F({0},{1,...,M}) (3)
Соотношения между косвенными дублями второго рода и другими видами дублей первого и второго рода задаются теоремами 1, 2 и следующими двумя теоремами.
Теорема 3. Косвенный дубль второго рода всегда является прямым дублем второго рода.
Доказательство данной теоремы полностью аналогично доказательству теоремы 1.
Теорема 4. Полный косвенный дубль второго рода является косвенным дублем первого рода тогда, и только тогда, когда верно соотношение
({j},{1,...,M}{j})|F({0},{1,...,M})=?
j?F({0},{1,...,M})
Доказательство данной теоремы полностью аналогично доказательству теоремы 2.
Результат применения технологии
Рассмотрим полученные результаты применения технологии дублирования информации на примере решения задачи классификации объекта потребительского рынка (магазина) на предмет его принадлежности к определенному типу (Бутик, Гипермаркет, Дискаунтер, Магазин у дома, Супермаркет, Универсальный магазин, Универсам). В основу легла база данных, представляющая собой таблицу, и состоящая из 529 примеров, характеризующихся 118 признаками и результатом, в роли которого выступает определенный класс. На основе этих данных была поставлена задача соотнесения объектов выборки к определенному классу, сокращение числа входных сигналов, создание набора повышенной надежности к неумышленным искажениям информации и установление взаимозависимостей между признаками с помощью возможностей алгоритмов дублирования информации. В качестве инструмента технической реализации использованы нейросетевые технологии [3].
В результате работы с нейросетевым имитатором набор прототипов для данной выборки составил 50 признаков из 118, при этом сеть способна классифицировать объекты по заданным классам со 100% точностью. Реализуя последовательно алгоритмы построения дублей, были получены следующие наборы повышенной надежности и иерархические схемы признакового пространства:
S1пп -- состоит из 74 признаков (50 прототипов, 24 дублера);
S1кп -- отсутствует, так как нейронная сеть не смогла решить задачу одновременного вычисления всего набора прототипов;
S2пп -- включает в себя 97 признаков, количество которых совпадает с количеством полного прямого дубля второго рода;
S2кп -- в его состав вошло 100 признаков, что так же соответствует полному дублю.
Для проверки надежности полученных наборов были сформированы три выборки на базе исходного задачника. В первой выборке случайным образом внесены искажения информации в наиболее информативный признак в 53 объекта (10% от общего количества). Во второй выборке -- в тринадцати прототипах (10%) и том же объеме примеров (686 искажений). В третьей -- в 50% прототипах (1325 искажений).
Тестирование качества решения задачи классификации показало, что искажения информации не влияют на качество классификации по задачнику со всем набором признаков и с наборов повышенной надежности, основанном на косвенном дубле второго рода. Однако качество решений задачи на базе других наборов признаков ухудшается в зависимости от роста количества искажений. Наиболее зависимым от точности данных оказалось решение нейронной сети, основанное на минимальном наборе признаков.
В качестве решения задачи предложена выборка, качественный и количественный набор признаков в которой равен набору повышенной надежности на базе косвенного дубля второго рода. Решение задачи классификации по данной выборке является устойчивым.
На примере решения этой задачи показано, что одновременное использование набора прототипов и дублеров позволяет формировать набор признаков, обладающей устойчивостью к искажениям информации во входных данных. Эксперименты показали, что в этих условиях менее устойчивой является система, решающая задачу на выборке с минимальным набором признаков, а более устойчивой -- система, основанная на наборах повышенной надежности.
Анализ состава наборов признаков проиллюстрировал, что ряд из них не входит ни в минимальный набор, ни в набор дублеров. А анализ изменения ошибок вычисления позволил сделать вывод, что эти признаки являются зашумляющими, то есть решение задачи осуществляется менее качественно, если они присутствуют в выборке.
При решении задач по сокращению количества входной информации исследователь сталкивается с риском понижения качества решения и полезности их алгоритмов. В этом случае уменьшать погрешность вычислений можно и целесообразно за счет увеличения пространства признаков путем добавления дублирующей информации из набора исходных данных.
Алгоритмы поиска дублеров основаны на минимизации пространства признаков, а процессы формирования на их основе наборов повышенной надежности достаточно просты и имеют самостоятельное значение и не зависят от методов минимизации пространства признаков. Кроме этого, практическое применение данных алгоритмов показывает, что они могут войти в серию методов устанавливающих зависимости между признаками, объясняющих структуру пространства признаков и выявляющих иерархическую зависимость между характеристиками объектов исследования.
Однако предложенная технология дублирования не избавлена от недостатков. Некоторые из предложенных в ней алгоритмов построения дублей и наборов повышенной надежности являются достаточно трудоемкими и требуют от пользователя максимум внимания. Но данная проблема может быть частично устранена при соответствующей технической и аппаратной поддержке решения задачи.
Реализованные алгоритмы дублирования способны выступать в роли помощников в принятии решений. Они позволяют вырабатывать информацию нового содержания и создавать базу для дальнейшего анализа и обработки. С их помощью можно расставлять приоритеты среди признаков, формировать отдельно выборки, состоящие из первичной и вторичной информации, фильтровать данные и т.п.
Литература
1. Аксенов В.В. Использование экономико-математических методов в повышении качества оперативной экономической информации (на примере информационной системы Госснаба СССР): ил РГБ ОД 61:85-8/1162.
2. Бройдо В.Л. Достоверность экономической информации в АСУ. -- Л.: Изд-во ЛГУ, 1984. -- 199 с.
3. Горбань А.Н., Россиев Д.А. Нейронные сети на персональном компьютере. -- Новосибирск: Наука, 1996. -- 276 с.
4. Пивоваров А.Н. Опыт использования рациональных приемов и методов обеспечения достоверности обработки постоянной информации в АСУ. -- Л., 1978.
5. Пивоваров А.Н. Методы обеспечения достоверности информации в АСУ. -- М., Радио и Связь, 1982. -- 144 с.
6. Шульц Я. Ограничения влияния ошибок входных данных в АСУ. -- Podnikova organizace, 1976, V.30, #12, p 44-46. (ВЦП.№-А-47612).
7. Харкевич А.А. «Борьба с помехами». -- М.: Наука, 1992. -- С. 192-195.