Метод совместного построения решающих правил и выбора словаря признаков по взвешенным обучающим выборкам

Аннотация

Волченко Е.В. – Метод совместного построения решающих правил и выбора словаря признаков по взвешенным обучающим выборкам. В работе предложен новый подход к решению задачи совместного построения решающих правил классификации и рабочего словаря признаков в обучающихся системах распознавания, основанный на использовании взвешенных обучающих выборок. Описаны метод w-GridDC формирования взвешенной обучающей выборки w-объектов, алгоритм w-MIEF построения рабочего словаря признаков на ее основе и модифицированный метод k-ближайших соседей для выполнения классификации объектов. Приведены результаты экспериментальных исследований, подтверждившие эффективность предложенного подхода.

Введение

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

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

При комплексном подходе к построению решающих правил классификации и формированию рабочего словаря признаков данную задачу, согласно [5], называют задачей комбинированного типа DX (построения решающего правила D в наиболее информативном пространстве признаков X). Ее сложность состоит в необходимости одновременного решения двух ключевых задач распознавания: построения эффективного решающего правила классификации, для которой в большинстве случаев увеличение количества признаков приводит к повышению эффективности классификации и минимизации словаря признаков для сокращения временных и емкостных затрат на выполнение классификации [6].

Наиболее известными алгоритмами решения задачи типа DX являются:

– алгоритмы CORAL и DW [1], основанные на переборе всех возможных словарей признаков и формировании на их основе решающих правил классификации;

– алгоритм FRiS-DX [6], основанный на выборе очередного варианта признакового пространства и построения в нем решающего правила на основе алгоритма FRiS-Stolp, выделяющего подмножества эталонных объектов, на основании которых выполняется классификация.

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

В данной работе на основе разработанных ранее алгоритмов [7,8] предлагается новый подход к решению задачи типа DX, который состоит в предварительном сокращении исходной выборки путем перехода к сокращенным взвешенным выборкам w-объектов и дальнейшем построении оптимального словаря признаков и решающего правила классификации на их основе.

Цель работы

Целью данной работы является разработка метода совместного построения решающих правил классификации и рабочего словаря признаков на основе взвешенных выборок w-объектов в обучающихся системах распознавания.

Постановка задачи

В качестве исходных данных дано некоторое множество объектов X={X₁,Х₂,...,Х_k}, представленное в виде объединения непересекающихся классов и называемое обучающей выборкой. Каждый объект X_i из X описывается системой признаков, т. е. X_i={X_i1,X_i2,...,X_in} и представляется точкой в линейном пространстве признаков, т. е. X_i∈Rⁿ. Для каждого объекта X_i известна его классификация y_i∈[1,l].

Решение задачи классификации некоторого объекта X_i^W={X_s1, X_s2,...,X_sn} предполагает выполнение двух этапов обработки исходной выборки Х для получения сокращенной по количеству объектов и их признаков взвешенной обучающей выборки и выполнение непосредственной классификации.

На первом этапе необходимо сформировать классифицированную взвешенную обучающую выборку w-объектов X^W={X₁^W,X₂^W,...,X_m^W}, y_i^W∈[1,l], где X^W={X_i1^W,X_i2^W,...,X_in^W,p_i}, p_i – вес i-го w-объекта.

На втором этапе необходимо по выборке w-объектов построить сокращенный рабочий словарь из k (k ≤ n) признаков при условии неухудшении эффективности классификации.

Построение выборки w-объектов по исходной обучающей выборке на основе алгоритма w-GridDC

Общим принципом построения сокращенных обучающих выборок w-объектов [8,9] является выделение областей компактного расположения объектов одного класса в пространстве признаков и замена этого множества объектов одним w-объектом, вес которого характеризует количественные или топологические особенности найденного множества. Приведем далее обобщенное описание метода w-GridDC построения выборки w-объектов.

Идеей метода GridDC [8] является наложение сетки на признаковое пространство для формирования множества клеток, определение объектов выборки, принадлежащих каждой из клеток, и их замена на w-объекты. Формирование объектов новой выборки выполняется только в случае принадлежности всех объектов клетки одному классу. Вес w-объектов определяется по количеству объектов исходной выборки, принадлежащих клетке.

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

Шаг 1. Формирование сетки. Рассчитывается шаг клетки s по формуле:

где [...] – оператор округления до ближайшего целого значения; mах{х_i} – максимальное значение i-го признака среди всех объектов выборки, min{x_i} – минимальное значение.

Выполняется разбиение признакового пространства Rⁿ по каждому из п признаков на интервалы длиной s (наложение прямоугольной сетки), результатом которого является множество клеток G. Далее для каждого объекта выборки X определяется клетка, которой этот объект принадлежит.

Показано [8], что Объект Х_i принадлежит некоторой клетке G_j тогда и только тогда, когда каждое из значений его признаков входит в интервал значений соответствующих признаков данной клетки.

В результате формирования сетки и обработки объектов исходной обучающей выборки будут сформированы непересекающиеся подмножества Х_Gj объектов, принадлежащих клетке G_j, j∈[1,|G|].

Шаг 2. Формирование значений признаков w-объектов. Возможны следующие варианты обработки содержимого клеток.

1. Если все объекты клетки принадлежат к одному классу, то значения признаков объекта новой выборки рассчитываются как координаты центра масс объектов этой клетки:

2. Если клетка не содержит ни одного объекта, то объект новой выборки не формируется.

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

Классификация w-объекта определяется по классификации объектов, по которым он сформирован.

Шаг 3. Определение веса w-объектов. Вес w-объекта равен количеству объектов исходной выборки, принадлежащих клетке, т. е. p_j=|Х_Gj|.

В результате выполнения алгоритма будет получена новая взвешенная обучающая выборка w-объектов Х^W.

Построение рабочего словаря признаков на основе взвешенных обучающих выборок w-объектов

Введение в описание объектов взвешенной обучающей выборки новой характеристики – веса – не позволяет эффективно использовать известные алгоритмы построения рабочего словаря признаков. Для решения задачи построения рабочего словаря признаков по взвешенным обучающим выборкам w-объектов в [7] предложен метод w-MIEF, описание которого приведем далее.

Основой метода w-MIEF является оценка индивидуальной информативности признаков по обобщенному критерию, включающему в себя отношение дискриминанта Фишера и коэффициент индивидуальной эффективности распознавания. Основной особенностью предлагаемого метода является использование в качестве исходных данных взвешенной выборки w-объектов.

Алгоритм w-MIEF состоит из следующих этапов:

1. Инициализация алгоритма (значений дискриминанта Фишера fisher_i = 0, i ∈ [1,n] и среднего значения fisherAvg = 0.

2. Вычисление отношения дискриминанта Фишера для всех признаков априорного словаря

где D_ji – дисперсия значений i-ого признака по j-ому классу, m_ji – среднее значение i-ого признака по j-ому классу.

3. Вычисление степени покрытия классов признаками априорного словаря

где S_i – количество уникальных найденных значений признака x_i, featValItems_ja – количество объектов класса j с заданным значением i-ого признака.

4. Вычисление взвешенной эффективности признаков

где featValWeight_j – суммарный вес объектов класса j с заданным значением i-ого признака, p_a – вес w-объекта.

5. Выбор наилучших признаков:

 1) с максимальной эффективностью по степени перекрытия классов

 2) с максимальной эффективностью по информативности:

6. Формирование рабочего словаря признаков по параметрам максимальной эффективности по степени перекрытия классов и информативности признаков по следующим правилам:

 1) эффективность текущего признака совпадает с эффективностью лучшего признака;

 2) эффективность признака больше 0 и данный признак улучшает распознавание хотя бы одного класса;

 3) эффективность признака больше 0 и распознавание хотя бы одного из классов лежит в пределах порога t, заданного пользователем.

Отметим, что наличие пользовательского порога t связно с тем, что возможны ситуации, когда признаки не улучшают распознавание хотя бы одного из классов, но, тем не менее, имеют схожий с лучшим уровень распознавания классов. Таким образом, если для рассматриваемого признака разница между лучшим и текущим уровнем распознавания любого из классов находится в пределах (0;t], то данный признак также помечается, как информативный.

В результате работы алгоритма w-MIEF будет сформирован рабочий словарь, содержащий k (k ≤ n) признаков.

Выполнение классификации на основе взвешенной выборки w-объктов

Для классификации объектов на основе взвешенных обучающих выбороко w-объктов будем использовать модифицированный алгоритм k-ближайших соседей [9], широко применяющийся при решении задач классификации в условиях неполных априорных данных. Выбор данного метода для классификации на основе взвешенной обучающей выборки основывается на результатах исследований [10], согласно которым он будет показывать высокую эффективность классификации при использовании сокращенной обучающей выборки.

Модификация алгоритма k-ближайших соседей в данном случае будет состоять в использовании метрики, позволяющей определять близость между объектами взвешенной обучающей выборки и классифицируемым объектом X_s [10]:

Для определения классификации X_s найдем k-ближайших к нему w-объктов каждого из классов и отнесем к тому классу, суммарное расстояние до w-объктов которого минимально.

Результаты экспериментальных исследований

Для оценки эффективности предложенного подхода был проведен ряд экспериментальных исследований. В качестве исходных данных были использованы выборки объектов двух классов размером 1000–5000 объектов при 20% пересечении областей классов в пространстве признаков, содержащих 10–100 признаков распознавания. Для генерации значений признаков использовался нормальный и равномерный законы распределения. Также для экспериментальных исследований были исользованы наборы данных репозитория UCI [11].

В качестве критерия оценки эффективности классификации использовалась частота неверных классификаций. Количество «ближайших соседей» было выбрано равным 10% размера обучающей выборки w-объктов.

При анализе результатов предложенного подхода к решению рассматриваемой задачи были получены следующие результаты:

1) размер взвешенных выборок w-объктов составил в среднем 2,3% размера исходных обучающих выборок;

2) количество признаков, включенных в рабочий словарь, составило 40%–55% исходного количесва признаков;

3) частота неверной классификации объектов тестовой выборки модифицированным методом k-ближайших соседей по выборке w-объктов с использованием рабочего словаря признаков уменьшилась в среднем на 3,7% по сравнению с частотой неверной классификации методом k-ближайших соседей по исходной выборке;

4) эффективность предложенного подхода увеличивалась с увеличением размера исходных обучающих выборок.

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

Выводы

В данной работе предложен новый подход к решению задачи типа DX построения эффективного решающего правила классификации с определением минимального словаря признаков, основаный на переходе к вхвешенным обучающим выборкам w-объктов. Описаны метод w-GriDC формирования взвешенной обучающей выборки w-объктов, алгоритм w-MIEF построения рабочего словаря признаковна ее основе и модифицированный медот k-ближайших соседей для выполнения классификации объектов. Анализ предложенного подхода показал сходимость составляющих его методов, их низкую времнную сложность, корректонсть обработки объетов исходной выборки. Отличительной особенностью данного подхода является использование сокращенной взвешенной обучающей выборки, что позволяет существенно сократить временные и емкосные затраты на построение словаря признаков и выполнение классификации объектов при сохранении начального уровня эффективности работы системы.

Список использованной литературы

1. Загоруйко Н.Г. Прикладные методы анализа данных и знаний / Н.Г. Загоруйко. – Новосибирск: ИМ СО РАН, 1999. – 270 с.
2. Pal R.S. Pattern recognition: from classical to modern approaches / K.S. Pal, A. Pal – Calcutta: World scientific, 2001. – 612 p.
3. Theodoridis S. Pattern Recognition / S. Theodoridis, K. Koutroumbas. – San Diego: Academic Press, 2008. – 823 p.
4. Загоруйко Н.Г. Проблема выбора в задачах анализа данных и управления / Н.Г. Загоруйко, Г.С. Лбов // Сиб. журн. индустр. матем. – № 3:1. – 2000. – С. 101–109.
5. Загоруйко Н.Г. Методы распознавания и их применение / Н.Г. Загоруйко. – М: Сов. радио, 1972. – 206 с.
6. Борисова И.А. Использование FRiS-функции для построения решающего правила и выбора признаков (задача комбинированного типа DX) / И.А. Борисова, В.В. Дюбанов, Н.Г. Загоруйко, О.А. Кутненко // Труды Всероссийской конференции «Знания–Онтология–Теория» (ЗОНТ–07), Новосибирск, 2007. – Том І. – С. 37–44.
7. Волченко Е.В. Метод w-MIEF построения рабочего словаря признаков на основе взвешенных обучающих выборок / Е.В. Волченко, В.С. Степанов // Вісник Національного технічного універсистету «Харківський політехнічний інститут». Збірник наукових праць. Тематичний випуск: Нові рішення в сучасних технологіях. – Харків: НТУ «ХПІ», 2012. – № 18. – C. 26–33.
8. Волченко Е.В. Сеточный подход к построению взвешенных обучающих выборок w-объектов в адаптивных системах распознавания / Е.В. Волченко // Вісник Національного технічного універсистету «Харківський політехнічний інститут». Збірник наукових праць. Тематичний випуск: Інформатика і моделювання. – Харків: НТУ «ХПІ», 2011. – № 36. – С. 12–22.
9. Волченко Е.В. Метод построения взвешенных обучающих выборок в открытых системах распознавания // Доклады 14-й Всероссийской конференции «Математические методы распознавания образов (ММРО-14)», Суздаль, 2009. – М.: Макс-Пресс, 2009. – С. 100–104.
10. Волченко Е.В. О способе опеределения близости объектов взвешенных обучающих выборок / Е.В. Волченко // Вісник Національного технічного універсистету «Харківський політехнічний інститут». Збірник наукових праць. Тематичний випуск: Інформатика і моделювання. – Харків: НТУ «ХПІ», 2012. – № 15. – C. 12–20.
11. Merz C.J. UCI Repository of machine learning datasets / C.J. Merz, P.M. Murphy // Infofmation and Computer Science University of California, Irvine, CA, 1998. – Режим доступа: http://www.ics.uci.edu/databases