Математика/ 2. Перспективы информационных систем

Василенко Ю.А., Исак Ю.Ю., Попович М.Т., Мельник Е.А., Головчак И.И.

Закарпатский государственный университет, Украина

Определение важности дискретных признаков (анализ подходов).

Как отмечено многими авторами работ по искусственному интеллекту, задача численной оценки и выбора информативных дискретных признаков некоторых объектов (материальных, ситуаций, явлений и др.) относится к наиболее важным в распознавании. В Украине и за рубежом предложены различные методы уменьшения числа признаков путем выбора некоторого подмножества из исходной (заданной) совокупности признаков. Однако здесь еще имеется много нерешенных проблем (как вычислительных, так и принципиальных). Например, в [3] указано, что при наличии трех бинарных признаков “наиболее информативный” из них может не входить в “информативную пару признаков”, ниже авторами показана несостоятельность оценки важности отдельных признаков и групп признаков в тестовых методах распознавания и др.

К решению указанной нами задачи известны самые разнообразные подходы. Так, в [5] эта задача решается на основе статистической теории распознавания (предложены приближенные формулы для численной оценки полезности признаков). В [7] для решения этой задачи используется построение специальной метрики, в которой расстояние между разделяемыми множествами объектов становится возможно большим. В [6] для определения важности дискретных признаков предлагается метод случайного поиска с адаптацией (СПА), а в [1] рассмотрен для этих целей способ, основанный на идее вычисления вероятности значений отдельного признака для каждого класса распознаваемых объектов.

Проблема нахождения хорошей численной характеристики для измерения эффективности данного множества свойств объектов с точки зрения их классификации рассматривалась Бахадуром (указано в [2]). “В качестве таких характеристик предлагались различные меры информативности, расстояния и разделимости, однако все они не имеют однозначной связи с ошибками классификации”, как отмечено Л.Каналом в [3].

В [2] обоснован и исследован метод численной оценки важности отдельных дискретных признаков (групп признаков), частично свободный от вышеуказанного недостатка. При этом оценка важности признаков объектов осуществляется непосредственно по характеру компонент разбиения , количество которых может быть произвольным.

Оценку важности дискретных признаков , , …, по отношению к распознающей функции наиболее естественно можно определить следующим образом. Пусть — некоторое множество наборов значений признаков , , …, , на каждом из которых известна функция . Предположим, что функция принимает значения О₀, О₁, …, О_k-1. Рассмотрим, например, признак . Допустим, что этот признак принимает значения .

Пусть — количество всех наборов в множестве М, в которых признак принимает значение ; — количество всех наборов из М, в которых признак принимает значение , а функция принимает значение ; через обозначим количество всех наборов множества М. Тогда важность признака p₁ по отношению к можно оценить следующей формулой:

, (1)

где .

Аналогично оценивается важность остальных признаков .

Формула (1) получается из следующих соображений. Величину можно интерпретировать как вероятность того, что функция принимает значение при условии, что значение признака равно . Величина представляет собой максимальную из этих вероятностей. Можно еще сказать, что величина представляет собой ту информацию, которую можно получить о значении функции , зная, что на наборе значение признака равно . Как вытекает из (1), величина , определяемая функцией (1), характеризует собой ту информацию, которую можно получить о функции , зная значение признака на наборе . Ясно, что признак , для которого эта информация является наибольшей, можно считать самым важным по отношению к функции .

Можно показать, что (1) является частным случаем функционала , введенного в [2]. При этом аналогом признака является обобщенный признак .

На практике вместо формулы (1) удобно применять следующую формулу:

(2)

Формула (1) представляет собой некоторый функционал, определенный на множестве . Далее (1) будем называть функционалом важности признака . Аналогично вычисляются функционалы важности признаков , , …, .

Правомерность приведенной нами оценки важности дискретных признаков можно убедительно доказать, опираясь на фундаментальные исследования широко известных английских ученых Кендалла и Стюарта (переведены с английского и опубликованы в СССР в 1973 г.). Так в [4] рассмотрены категории, или классы. Приведем для этих данных некоторые сведения, необходимые для дальнейшего изложения затронутой нами темы.

Пусть имеется генеральная совокупность, в которой классификация произведена на основании наличия или отсутствия некоторого признака . Простейшая задача о взаимозависимости признаков возникает тогда, когда имеется два признака и . Если обозначает отсутствие и - отсутствие , то количества попаданий в четыре возможные подгруппы могут быть в очевидных обозначениях представлены табл. 1.

Эту таблицу 2х2 (иногда называемую 4-х клеточной таблицей) часто удобно записывать в форме табл. 2.

Табл. 1 Табл. 2

		Не	Сумма
не
Сумма

Если между и не существует никакой связи, т.е. если обладание признаком не связано с обладанием признаком , то доля индивидов с признаком среди индивидов, обладающих признаком , должна быть равна доле индивидов с признаком среди индивидов, с обладающим признаком . Таким образом, по определению, признаки независимы в данной совокупности из наблюдений, если

(3)

Как показано в [4], вероятность правильного оценивания категории при заданной категории будет равна

(4)

Аналогично, вероятность правильного оценивания категории при заданной категории равна

(5)

Если категоризованные переменные и интерпретировать в терминах, использованных выше, т.е. под понимать , а под - , то величины , , , в (4) и (5) будут аналогами , , , при в (1). В этом случае будут представлять собой вероятность правильного оценивания значений при задании признака . Таким образом правомерность предложенной формулы (1) и состоятельность вышеуказанного обоснования не вызывает никаких сомнений.

Используя функционал важности признаков (ФВП) легко реализовать процедуру ранжирования по важности отдельных дискретных признаков , характеризующих объекты некоторой заданной обучающей выборки (ОВ). Расположив признаки в порядке убывания ФВП для при , получим некоторый ранжированный ряд признаков , , …, , где - самый важный признак относительно , а - наименее важный признак относительно - функции, задающей разбиение М на образы (классы).

В заключение, отметим некоторые существенные стороны оценки важности признаков (1).

1. , ( - число классов ОВ)

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

3. Численная величина ФВП некоторого признака совпадают с той долей объектов ОВ, которую можно правильно отнести в соответствующие классы на основе учета значений взятого признака, т. е. (1) имеет однозначную связь с ошибками классификации ОВ. Заметим, что свойства 1, 2, 3 непосредственно вытекают из (1).

На основе использования понятия функции принадлежности из теории нечетких множеств были разработаны критерии оценки важности признаков, являющиеся обобщением ФВП [2].

Оценка важности отдельных признаков (1) эффективно применяется в методе разветвленного выбора признаков (РВП) [2] для конструирования оптимальных (по памяти и быстродействию) граф-схем, распознающих наборы дискретных признаков.

Литература:

1. Адасовский Б.И. Метод вычисления информативности многомодальных признаков. – ДАН СССР, 1978, т. 239, № 2. – с. 286 – 289;

2. Василенко Ю.А. Математическое конструирование многоуровневых распознающих систем на основе метода разветвленного выбора признаков (теория, алгоритмы, реализация, применение), дисс… докт. техн. наук. Харьков, 1991, 230 с.;

3. Канал Л. Обзор систем для анализа структуры образов и разработки алгоритмов классификации в режиме диалога. Распознавание образов при помощи цифровых вычислительных машин (пер. с англ.). – М.: Мир, 1974. – с. 124 - 143.

4. Кендал М., Стьюарт А. Статистические выводы и связи (пер. с англ.). – М.: Наука, 1973. – 900 с.

5. Козловский Б.В., Хараузов К.Н. Критерий оценки полезности признаков в задаче распознавания образов. Известия АН СССР. Техническая кибернетика, 1969, № 3. – с. 31 - 36.

6. Лбов Г.С. Выбор эффективной системы зависимых признаков. Вычислительные системы, 1965, вып. 19. – с. 21 - 34.

7. Неймарк Ю.И. К вопросу о выборе признаков при распознавании образов. Известия АН СССР. Техническая кибернетика, 1970, № 1. – с. 41 - 46.