6. О выборе информативного множества признаков
В главе 3 «Базовые гипотезы» Николай Григорьевич затрагивает одну из важнейших и интереснейших тем (которую он развивает в отдельной главе (6)) - проблему выбора множества информативных признаков.
В условиях, когда законы распределения неизвестны и трудно оценить представительность выборки, не может быть указаний на число признаков, чтобы гарантированно подтверждалась гипотеза компактности.
Представительность выборки и информативность признаков – понятия условные. Обучающая выборка представительна, если при заданном наборе признаков и заданном типе решающих правил удается построить правило, распознающее объекты с заданной точностью. Система признаков информативна, если при заданной выборке и заданном типе решающих правил удается сделать то же самое. Оценка информативности того или иного признака производится по количеству ошибок распознавания.
Возможны и другие способы оценки информативности. Из гипотезы компактности следует, что для хорошего распознавания образов желательно, чтобы расстояния между «своими» точками в cреднем были меньше расстояний между чужими и расстояния до чужих дочек были больше расстояний до чужих. Если гиперсферы, каждая из которых включает точки только одного образа, пересекаются, то желательно, чтобы их диаметры различались как можно больше.
Компактность (плотность) образа Wi, представленного в обучающей выборке I точками 1,2,..,t..,k,..I можно характеризовть средней длиной ребер полного графа:
Wi=
То же мы можем сказать и образе Wj, представленного J точками.
Разнесенность образов в пространстве можно охарактеризовать через среднее расстояние между всеми парами точек из разных образов:
W(i,j)=Σr(t,s), 1 ≤ t ≤ I, 1 ≤ s ≤J.
Тогда, информативность пространства признаков тем больше, чем больше величина
D=
Этот критерий информативности будет хорошо работать для независимых признаков. В противном случае нам нужно будет перебрабрать и проверить на информативность Cкомбинаций для выбора n признаков из g. Регулярно встречаются случаи необходимости перебора 1015. Очевидно, в таких случаях речь о нахождении оптимального решения не идет и разрабатываются различные эвристические алгоритмы.
6.1. Методы последовательного сокращения и добавления признаков DEL и ADD
Допустим, требуется выбрать 25 признаков из 50. Оценим ошибку распознавания α0 при использовании всех 50 признаков. Затем, последовательно будем исключать признаки по одному, каждый раз определяя ошибку распознавания в 49 мерном пространстве. Получим ряд ошибок (α11,α12,...,αki,α50), из которого выберем наименьшую αki и уберем из рассмотрения i-ый признак.
Эту процедуру будем повторять до тех пор, пока не останется 25 признаков.
Количество проверяемых множеств признаков:
L=
и в нашем случае оно равно 900, что на 12 порядков меньше объема полного перебора.
Если предшествующий метода - это метод «сверху вниз», то метод последовательного добавления - ADD - метод «снизу вверх». Начинаем с одномерных признаковых подпространств. Распознаем контрольную последовательность каждым из признаков по отдельности, выбираем признак, дающий минимальную ошибку, к нему последовательно добавляем каждый из (g-1), выбираем нилучший и т.д.
6.2. Метод случайного поиска с адаптацией (алгоритм СПА)
Единичный отрезок разбивается на g участков одинаковой длины (1/g). Каждому участку сопоставляется свой признак: первому - первый, второму - второй и т.д. Запускается датчик случайных чисел с равномерным распределением в диапазоне 0..1. После n шагов работы выбирается n признаков. По числу ошибок оценивается качество распознавания. Такая процедура проделывается r раз. В итоге получаем список оценок L=(α1,...,αr). Теперь можно упорядочить список L по возрастанию α т.е. по убыванию качества распознавания, и ввести систему поощрений и наказаний. Участки, соответствующие признакам, дающим лучший результат, увеличиваются, «худшие» - уменьшаются, но так, чтобы суммарная длина по-прежнему была равна 1.
Испытываем r новых признаковых подсистем, но теперь вероятность попадания на «лучшие» участки выше, чем на плохие.
Продолжаем процесс адаптации таким образом, что длина участков признаков, регулярно попадающих в самые информативные подсистемы, увеличивается на величину h<(1/g), а для самых неинформативных длины их участков уменьшаются.
После некоторого количества циклов поиска и адаптации, процесс стабилизируется.
Алгоритм СПА был протестирован для систем, в которых возможен полный перебор сочетаний признаков. Результаты: на одних и тех же примерах алгоритм СПА дает лучшие результаты, чем DEL и ADD.
7. Меры близости между предикатами
В результате исследований в области экспертных систем Н.Г Загоруйко и В.М. Бушуев ввели метрику в пространстве знаний.
Знания, используемые в экспертных системах, часто представлены в виде продукций типа
(X1,X2,..,Xn)(X1&X2&..,&Xn)A
При этом значения переменных могут задаваться по-разному:
X1=7,X2=(2..6),X10>0
и.т.п. При этом величина отличия значений предикатов роли не играет, нам же требуется оперировать такими понятиями, как степень похожести (близости), аналогичности, т.е. понятиями, которыми оперирует человек, рассуждая по аналогии. Таким образом, для расширения логических возможностей экспертных систем нужно научиться измерять степень похожести знаний, т.е. ввести метрику в пространстве знаний для измерения расстояний между знаниями. Это сделано следующим образом.
Можно считать, что каждый предикат отражает знание эксперта о распределении возможных значений данной характеристики. Например, утверждение X5=(a|b|c) равносильно утверждению, что X5 с равной вероятностью 1/3 может принимать одно из трех значений, утверждение X4=(2,3,4,5) равносильно утверждению о том, что предикат X4 с вероятностью 0.25 принимает одно из 4 значений в диапазоне целых чисел 2..5.
В таком случае, расстояние между одноименными предикатами можно определять через расстояние между двумя распределениями вероятности.
Предложенная мера для измерения этого расстояния R=f(r,h,w) учитывает расстояние r ото всех элементов одного распределения до всех элементов другого, энтропийную меру h, по смыслу близкую к дисперсии распределений, и степень пересечения распределений w, характеризующую величину согласия («консенсуса»).Ниже приведены формулы для расчета аргументов функции.
7.1. Расстояния
Если функции плотности вероятности f1(x),f2(x) отражают мнения двух экспертов о значении предиката X на участке xmin..xmax, тогда различия двух распределений измеряются величиной:
r=
В дискретном случае разделим ось X, отображающую мнение экспертов о распределении значений предиката, на m частей (квантилей) так, чтобы в каждой части была заключена плотность вероятности, равная 1/m. Тогда:
r=()/(xmax-xmin)
Здесь x1i,x2i - правые границы i-х квантилей 1-го и 2-го экспертов.
7.2. «Консенсус»
«Консенсус» вычисляется следующим образом. Интервал разбивается на T равных участков и определяется вероятности P1t,P2t попадания оценок экспертов в t-тую градацию. Тогда:
w=
7.3. Энтропийная мера или категоричность суждений
Расстояния между суждениями зависят и от категоричности h их оценок. При одинаковых r и w мера R считается тем большей, чем больше распределения, отражающие мнения двух экспертов, отличаются от равномерного распределения по всему диапазону значений xmin..xmax. Величина h находится следующим образом:
h=(h1+h2)
h1=
h2=
Теперь общая мера расстояния между предикатами, отражающая знания двух экспертов о характеристике X принимается равной rwh. Проверка данной меры экспертным путем показала, что в экспериментах по упорядочиванию распределений использование приведенной меры сохраняет порядок, установленный экспертами.
7.4. Расстояние между знаниями
Зная расстояние между одноименными предикатами, можно построить меру расстояния и между двумя знаниями, выраженными в виде множества предикатов.
Даже если эксперты оперируют не полностью совпадающими наборами характеристик, можно положить, что распределение значений отсутствующих характеристик принимается равномерным в известном диапазоне. В таком случае, расстояние между двумя знаниями, представленными продукциями, состоящими из n предикатов, по аналогии с n мерным евклидовым пространством, находим по формуле:
R=
Метрика в пространстве знаний позволяет формулировать и решать на материале базы знаний те же задачи, которые обычно решаются на материале базы данных аналогичными методами.
Литература
1. Загоруйко Н.Г. Прикладные методы анализа данных и знаний. - Новосибирск: ин-т Математики, 1999.
2. Философский энциклопедический словарь. – М.: Советская энциклопедия. 1983
3. Чурсин Н.Н. Популярная информатика. К.: «Техника», 1982. Электронная версия:
© «НиТ. Раритетные издания», 1998
4. Математическая энциклопедия, т. 1. М: Советская энциклопедия, 1977.
5. Моисеев Н. Человек и ноосфера. - М.:Молодая гвардия, 1990.
6. Столяров Ю.Н. Онтологический и метонимический смыслы понятия информация
http://www.gpntb.ru/win/inter-events/crimea2001/tom/sec4/Doc3.HTML
7. Леонов В.П. Применение статистики в статьях и диссертациях по медицине и биологии. часть III. Проблемы взаимодействия "автор - редакция - читатель". \\ Международный журнал медицинской практики, 1999, вып 12, стр.7-13.
8. Михайлов А.И., Черный А.И., Гиляревский Р.С. Научные коммуникации и информатика. М.: Наука, 1976
9. Налимов В.В., Мульченко З.М. Наукометрия. Изучение развития науки как информационного процесса. М.: Наука, 1969. - 192с.
10. Налимов В.В., Мульченко З.М. К вопросу о логико-лингвистическом анализе языка науки./ В кн.: Проблемы структурной лингвистики. М.: Наука, 1972. - 554с.
|
