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

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

Государственный университет информатики и искусственного интеллекта

Е.В. Волченко (lm@mail.promtele.com)

Донецк

Аннотация

выборка экспертный групповой объект

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

Введение

При построении обучающихся систем автоматического распознавания в качестве исходной информации традиционно [Журавлев, 1978] рассматривают обучающую выборку , содержащую значения признаков объектов , - количество признаков распознавания, и соответствующие этим объектам номера классов , - количество классов системы. Классификация объектов обучающей выборки в общем случае осуществляется экспертом и считается верной, поскольку проверить правильность классификации не представляется возможным [Лапко и др., 1999]. Размер обучающей выборки, точность измерения значений признаков составляющих её объектов и их классификация оказывают наибольшее влияние на качество решающих правил, формируемых в результате обучения, и, как следствие, на эффективность работы всей системы в целом, поэтому задача предобработки обучающих выборок является одной из центральных задач построения обучающихся систем распознавания [Загоруйко, 1999], [Pal et al., 2004].

Во многих случаях разработка систем распознавания затрудняется тем, что эксперт, определяющий классификацию объектов обучающей выборки, не обладает достаточным объемом знаний для принятия гарантированно безошибочных решений, т.е. классификация объектов обучающей выборки может содержать ошибки [Кувшинов и др., 2002]. В подобных случаях в [Дуда, 1976] предлагается выдвигать предположения относительно законов распределения значений признаков и классифицировать объекты обучающей выборки автоматически. Данный подход позволяет получать эффективные решения, однако существует широкий класс прикладных задач, для которых определение законов распределения признаков не представляется возможным. Другим подходом к решению данной проблемы является использование непараметрических методов [Лапко и др., 1999] и комитетных решающих правил [Кувшинов и др., 2002], использующих частично классифицированные обучающие выборки. Эти методы, на наш взгляд, эффективно решают рассматриваемую задачу только в том случае, если объекты обучающей выборки, классификация которых известна, классифицированы верно.

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

1. Для каждого объекта обучающей выборки по каждому классу системы выполняется расчет показателя, характеризующего степень уверенности экспертов в принадлежности объекта некоторому классу и отнесение объекта к классу с максимальным показателем;

2. Формирование взвешенной обучающей выборки, веса объектов которой являются показателями степени уверенности экспертов в правильности классификации.

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

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

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

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

2. Определение классификации объектов обучающей выборки

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

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

Расчет показателя уверенности классификации осуществляется следующим образом:

, (2.1)

где .

Определение классификации каждого из объектов обучающей выборки осуществляется путем выбора номера класса, соответствующего максимальному показателю уверенности классификации:

.

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

3. Построение взвешенной обучающей выборки

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

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

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

4. Построение решающих правил по взвешенной обучающей выборке

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

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

. (4.1)

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

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

,

где , - распознаваемый объект.

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

5. Экспериментальные исследования

Для оценки эффективности применения предложенного в данной работе подхода выполним ряд экспериментальных исследований, в которых для тестовых обучающих выборок, классификация объектов которых выполнялась группой экспертов, построим взвешенные обучающие выборки и оценим эффективность построенных по ним решающих правил. Анализ эффективности предложенного подхода проводиться на выборках размером 200-1000 объектов, значения признаков которых распределены по нормальному закону распределения. Результаты оценки являются средними по результатам 50 экспериментов. Количество одинаковых классификаций экспертами устанавливалось пропорционально удаленности объекта от межклассовой границы (наиболее удаленный объект был классифицирован всеми экспертами одинаково, лежащий на границе - с минимальным перевесом в сторону одного из классов).

При проведении экспериментов оценивалась частота неверной классификации объектов тестовой выборки (созданной по тем же генераторам, что и исходные выборки размером 200 объектов) решающим правилом, построенным по выборкам и соответственно. Оценка предложенного подхода выполнялась при различной степени пересечения классов (табл. 1) с постоянным размером выборки 600 объектов и различном размере выборок (табл. 2) при постоянной степени пересечения классов 20%.

Табл. 1.

Табл. 2.

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

Выводы

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

Список литературы

[Айзерман, 1970] Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. - М.: Наука, 1970.

[Волченко, 2009] Волченко Е.В. Метод построения взвешенных обучающих выборок в открытых системах распознавания // Доклады 14-й Всероссийской конференции «Математические методы распознавания образов (ММРО-14)», Суздаль, 2009. - М.: Макс-Пресс, 2009.

[Дуда, 1976] Дуда Р., Харт П. Распознавание образов и анализ сцен: Пер. с англ. - М.: Мир, 1976 .

[Журавлев, 1978] Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. - 1978. Т. 33.

[Загоруйко, 1999] Загоруйко Н.Г. Прикладные методы анализа знаний и данных. - Новосибирск: Издательство института математики, 1999.

[Кувшинов и др., 2002] Кувшинов Б.М., Шапошник И.И., Ширяев В.И. Использование комитетов в задачах распознавания образов с неточными экспертными оценками / // Теория и системы управления. - 2002. № 5.

[Лапко и др., 1999] Лапко А.В., Лапко В.А., Ченцов С.В. Непараметрические модели распознавания образов в условиях малых выборок // Автометрия. - 1999. № 6.

[Pal et al., 2004] Pal S.K., Mitra P. Pattern Recognition Algorithms for Data Mining: Scalability, Knowledge Discovery and Soft Granular Computing. -- Chapman and Hall/CRC, 2004.

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