Сравнительный анализ методов выбора информативных признаков

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Сравнительный анализ методов выбора информативных признаков

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

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

Критерии информативности и пригодности

В данной статье в качестве оценки информативности и пригодности во всех способах выбора подсистемы признаков используются критерии, в основе которых лежит функция конкурентного сходства , где r_i - минимальное расстояние от распознаваемого объекта до эталона i-го образа [3].

Для оценки информативности используется критерий . Здесь , где F_si - сумма значений FRiS - функции для всех M_oi объектов обучающей выборки i - го образа, K_i - количество столпов в i - ом образе, i = 1, 2.

Для оценки пригодности используется функция , где F_so, F_sk - среднее значение FRiS - функции на обучении и на контроле соответственно.

Алгоритм AdDel

Алгоритм AdDel предназначен для сокращения перебора вариантов признаковых подпространств из большого исходного пространства признаков. Он состоит из последовательно сменяющих друг друга процедур добавления наиболее информативных элементов и исключения наименее информативных [1]. В данной статье этот алгоритм участвует в качестве первого способа сокращения перебора.

Краткое описание алгоритма

1. Свою работу алгоритм начинает с одномерных пространств. В выбранных признаковых подпространствах алгоритм FRiS-Stolp проводит обучение, т.е. находит эталоны (столпы). Вычисляются значения критерия . Величина Krit служит оценкой информативности системы. Выбирается то признаковое пространство, которому соответствует максимальное значение Krit.

2. Затем к уже выбранному признаковому пространству добавляются признаки аналогично пункту 1 до тех пор, пока не будет получено признаковое пространство размерности n₁ < N.

3. После того как мы добавили n₁ признак, исключим из системы n₂ (n₂<n₁) признаков. Признак исключается из системы, если значение Krit в признаковом пространстве без этого признака дает наибольшее значение по сравнению с остальными.

4. Особенность алгоритма AdDel состоит в том, что в процессе увеличения размерности n выбираемых подпространств качество Krit обучения растет, затем рост прекращается и начинается его уменьшение. Точка перегиба функции Krit = f(n) указывает на наиболее предпочтительный вариант решения задачи. Поэтому описанный выше процесс продолжается до тех пор, пока не будет выбрана наиболее информативная система признаков. Используем n выбранных в этой точке признаков. Они обеспечивают максимальное качество обучения.

Метод главных компонент

МГК также используется для сокращения признакового пространства.

Пусть имеется матрица переменных X размерностью (MЧN), где M - число объектов (строк), а N - это число переменных (столбцов), количество которых, как правило, велико и может быть больше количества объектов (N>M). В методе главных компонент используются новые, формальные переменные t_a (a=1,… Q), являющиеся линейной комбинацией исходных переменных x_j (j=1,…, N)

информативный подмножество алгоритм

С помощью этих новых переменных матрица X разлагается в произведение двух матриц T и P.

Матрица T называется матрицей счетов (scores). Ее размерность (MЧQ).

Матрица P называется матрицей нагрузок (loadings). Ее размерность (QЧN). Нагрузки - это ортогональные нормированные вектора, т.е. .

Матрица E называется матрицей остатков. Её размерность (MЧN).

Схема разложения по главным компонентам

Новые переменные t_a называются главными компонентами (Principal Components), поэтому и сам метод называется методом главных компонент или Principal Component Analysis - PCA. Число столбцов - t_a в матрице T, и p_a в матрице P - равно Q, которое называется числом главных компонент. Эта величина заведомо меньше числа переменных N и числа объектов M.

Второй способ заключается в использовании МГК, в котором в качестве информативного признакового подпространства выбираются первые m главных компонент.

Комбинированный способ

Этот способ состоит из комбинации выше указанных способов, алгоритма AdDel и МГК - третий способ. Сначала их первичных признаков с помощью МГК формируются вторичные признаки - главные компоненты. А затем алгритм AdDel выбирает из них подмножество наиболее информативных компонент.

Результаты эксперимента

В работе использовались реальные данные: рентгеновские спектры микрочастиц разных типов материалов. Решалась задача распознавания двух образов.

Было задано признаковое пространство X размерности N = 982, количество объектов на обучении и контроле M_o = M_k = 200 (по 100 объектов в каждый образ).

Для всех способов было проведено по 10 экспериментов. Каждый эксперимент отличался случайным делением выборки на обучающую и контрольную.

По результатам экспериментов были сформированы диаграммы (для каждого способа результаты были усреднены по количеству экспериментов), в которых отображаются значения различных параметров в зависимости от способа выбора информативного признакового подпространства (см. рис 1 -5).

Рис. 1. Среднее значение FRiS - функции на контрольной выборке

Рис. 2. Среднее значение FRiS-функции на обучающей выборке

Рис. 3. Результаты распознавания контрольных объектов

Рис. 4. Количество потребовавшихся столпов

Рис. 5. Оценка случайности выбранных признаков

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

Литература

информативный подмножество алгоритм

[1] Н.Г. Загоруйко: Прикладные методы анализа данных и знаний.: Изд. ИМ СО РАН, Новосибирск, 1999, 270 с.

[2] Айвазян С.А., Мхитарян В.С.: Теория вероятностей и прикладная статистика т. 1: М.: ЮНИТИ-ДАНА, 2001, 656 с.

[3] Борисова И., Дюбанов В., Загоруйко Н., Кутненко О.: Использование FRiS-функции для построения решающего правила и выбора признаков (задача DX).: Труды конференции ЗОНТ -07

Размещено на Allbest.ru