Содержание к диссертации
Введение
Глава 1. Модели восстановления зависимостей 13
1.1 Разбиение области значений целевого признака 14
1.2 Байесовский корректор 15
1.2.1 Общая схема построения модели 15
1.2.2 Вычисление оценок вероятностей 18
1.2.3 Сглаживание оценок вероятностей 22
1.2.4 Корректность модели 28
1.2.5 Свойства модели при снижении числа интервалов разбиения 29
1.3 Линейный корректор 31
1.3.1 Общая схема построения модели 31
1.3.2 Корректность модели 32
1.3.3 Вычисление вектора весов 32
1.3.4 Свойства модели при снижении числа интервалов разбиения 33
Глава 2. Устойчивость моделей 36
2.1 Изменение описаний объектов 36
2.2 Изменение значений целевого признака 37
2.3 Изменение описаний и значений целевого признака объектов 37
Глава 3. Практическое сравнение моделей 40
3.1 Модельные задачи 40
3.2 Реальные задачи 41
3.3 Результаты 43
Заключение 44
Литература 45
- Общая схема построения модели
- Свойства модели при снижении числа интервалов разбиения
- Изменение значений целевого признака
- Реальные задачи
Введение к работе
Диссертационная работа посвящена проблеме восстановления зависимостей по выборкам прецедентов. Предлагаются модели «байесовский корректор» и «линейный корректор» для решения данной задачи, основанные на решении набора специальных задач распознавания, построенных на исходной обучающей выборке, и последующей коррекции в пространстве значений целевого признака. Исследуются свойства корректности и устойчивости рассматриваемых моделей.
Актуальность темы. В настоящее время существуют различные параметрические и непараметрические подходы к восстановлению зависимостей по выборкам прецедентов: линейная, полиномиальная и обобщенная линейная модели, метод опорных векторов, логистическая регрессия, нейросетевые алгоритмы, ядерное сглаживание, регрессионные деревья, случайный лес, регрессия на основе классификации. Следует отметить существенные ограничения существующих подходов при решении реальных задач. Параметрические подходы требуют априорного знания аналитического вида функций. Наличие разнотипных признаков требует привлечения дополнительных средств описания объектов в единой шкале. Непараметрические подходы используют, как правило, методы частотной оценки в некоторой окрестности, при этом возникают проблемы выбора окрестности и функций расстояния, учета фактора различной важности признаков и т.п.
В то же время, случай дискретной величины (стандартная задача распознавания) в настоящее время достаточно хорошо изучен. Более 20 лет тому назад Ю.И.Журавлевым было отмечено, что задача распознавания может рассматриваться как задача интерполяции специальных функций, когда независимые переменные (значения признаков) могут быть фактически произвольны, а зависимая величина принимает конечное число значений. В настоящее время существуют различные модели и конкретные алгоритмы для решения задач распознавания, для которых исследованы свойства корректности и устойчивости (алгебраический подход, логические корректоры и др.).
Актуальной задачей является разработка методов восстановления зависимостей по выборкам прецедентов, основанных на решении набора специ-
альных задач распознавания и последующей коррекции в пространстве значений целевого признака. При этом основные трудности, связанные со сравнением объектов в признаковом пространстве (разнотипность и различная информативность признаков, согласование метрик для отдельных признаков, и др.), переносятся на уровень решения задач распознавания.
Целью диссертационной работы является разработка и исследование методов решения задачи восстановления зависимостей по выборкам прецедентов, основанных на решении набора специальных задач распознавания, построенных на исходной обучающей выборке, и последующей коррекции в пространстве значений целевого признака.
Основные положения, выносимые на защиту.
-
Общий подход к формированию задач распознавания и вычисления значения зависимой величины как коллективного решения.
-
Модели восстановления зависимостей «байесовский корректор» и «линейный корректор».
-
Доказательства свойств корректности и устойчивости моделей восстановления зависимостей «байесовский корректор» и «линейный корректор».
-
Результаты практической апробации моделей восстановления зависимостей на реальных прикладных задачах.
Научная новизна. Автором разработаны методы решения задачи восстановления зависимостей по выборкам прецедентов, основанных на решении набора специальных задач распознавания, построенных на исходной обучающей выборке, и последующей коррекции в пространстве значений целевого признака. Доказаны теоретические утверждения о свойствах корректности и устойчивости предложенных моделей восстановления зависимостей.
Теоретическая значимость. В работе предложен новый подход к решению задач восстановления зависимостей по выборкам прецедентов, приводятся доказательства свойств корректности и устойчивости предложенных методов.
Практическая значимость. Разработанные методы восстановления зависимостей по выборкам прецедентов применимы к реальным прикладным задачам, что подтверждается практической апробацией.
Достоверность результатов подтверждена строгими математическими доказательствами теоретических утверждений.
Апробация работы. Основные результаты работы докладывались на следующих научных конференциях:
14-я всероссийская конференция «Математические методы распознавания образов» (Суздаль, 2009 год);
2-я международная конференция «Классификация, прогнозирование, анализ данных» CFDM-2010 (Варна, Болгария, 2010 год);
10-я международная конференция «Распознавание образов и анализ изображений: новые информационные технологии - РОАИ-10-2010» (Санкт-Петербург, 2010 год).
Публикации. Материалы диссертации опубликованы в 4 научных статьях [?,?,?,?], из них 2 работы [?, ?] — в журналах, включенных в Перечень ведущих рецензируемых научных журиалов и изданий.
Структура и объем диссертации. Работа состоит из оглавления, введения, трех глав, заключения и списка литературы. Содержание работы изложено на 47 страницах. Список литературы включает 49 наименований. Текст работы иллюстрируется 1 таблицей.
Общая схема построения модели
Регрессионные деревья Метод восстановления зависимости описан в [23,30,31]. Листовым вершинам дерева приписываются значения зависимой величины, внутренним вершинам — признак описания объекта и его пороговое значение. Для восстановления зависимой величины нужно спуститься из корня дерева в листовую вершину, причем для определения поддерева, через которое проходит путь, производится сравнение значения признака, приписанного текущей вершине, и значения признака объекта, для которого производится восстановление зависимой величины. Процесс построения дерева является «жадным» алгоритмом, на каждом шаге выбирается признак и помещается в текущую вершину, для которой далее строятся поддеревья. Для выбора признака используется один из критериев: ID3, основанный на учете прироста информации; С4.5, основанный на учете нормализованного прироста информации; DB-CART, использующий оценки распределения описаний объектов и зависимой величины. Случайный лес Метод восстановления зависимости заключается в использовании комитета решающих деревьев [24,37]. Структура каждого дерева аналогична структуре регрессионных деревьев. Деревья строятся по следующей процедуре: генерируется случайная подвыборка обучающей выборки с повторе ниями; для каждой внутренней вершины выбирается признак из подмножества признаков мощности d d, выбор осуществляется на основе критерия Гини; дерево строится до полного исчерпания подвыборки и не подвергается процедуре прунинга.
Для восстановления зависимой величины осуществляется спуск по каждому дереву комитета до листовых вершин, оценкой зависимой величины является взвешенная сумма значений, приписанных листовым вершинам. Число деревьев комитета выбирается таким образом, чтобы минимизировать ошибку на выборке, состоящей из объектов, которые не содержатся хотя бы в одной подвыборке, на основе которой построено одно из деревьев.
Метод группового учета аргумента Метод заключается в порождении и выборе моделей восстановления зависимости оптимальной сложности [11,18,38]. Под сложностью модели в МГУА понимается число параметров. Для порождения используется базовая модель, подмножество элементов которой должно входить в искомую модель. Для выбора моделей используются внешние критерии, специальные функционалы качества моделей, вычисленные на тестовой выборке. Индуктивный алгоритм построения модели оптимальной структуры состоит из следующих основных шагов: выбор или задание класса базисных функций и преобразования дан ных, например, используется полином Колмогорова-Габора у = WQ + настраиваются параметры моделей, используется внутренний критерий — критерий, вычисляемый с использованием обучающей выборки, например, минимизации нормы разности вектора известных значений зависимой величины и вектора восстановленных значений; для выбора моделей вычисляется качество порожденных моделей, при этом используется контрольная выборка и назначенный внешний критерий; например, в качестве внешнего критерия могут быть использованы критерий регулярности, критерий минимального смещения, критерий абсолютного иммунитета к шуму. Если значение внешнего критерия не достигает своего минимума при увеличении сложности модели, то процесс построения прерывается.
Для порождения и выбора моделей может быть использован генетический алгоритм [17]. Регрессия на основе классификации (regression via classification) Данный подход заключается в сведении задачи восстановления зависимости к задаче классификации [35, 45-47]. Процесс обучения заключается в дискретизации области значений зависимой величины, постановке специальной задачи классификации: объекты, значения зависимой величины у І которых принадлежат интервалу Aj разбиения, относятся классу Kj, и обучении классификатора. Процесс восстановления зависимой величины заключается в классификации объекта и преобразовании метки класса в значение зависимой величины, например, в качестве оценки берется центр интервала. Известны коллективные методы восстановления регрессии на основе классификации [32], в которых генерируется N независимых разбиений на п интервалов, ставится N задач классификации с п классами. В качестве восстановленного значения зависимой величины берется среднее по результирующим значениям элементов коллектива. Для разбиения области значений зависимой величины используются методы: интервалы равной ширины, интервалы равной частоты [29], критерий контраста монотетичности [40], векторная квантизация [36].
Существуют и другие близкие по сути подходы и алгоритмы. Следует отметить существенные ограничения регрессионных подходов. Параметрические подходы требуют априорного знания аналитического вида функций. Наличие разнотипных признаков требует привлечения дополнительных средств описания объектов в единой шкале. Непараметрические подходы используют как правило методы частотной оценки в некоторой окрестности объекта, при этом возникают проблемы выбора окрестности и функций расстояния, учета фактора различной важности признаков и т.п. Существенным недостатком метода регрессии на основе классификации является компромисс между числом интервалов разбиения и размером классов в задаче классификации: при повышении дискретизации снижается количество объектов в классах и уменьшается обобщающая способность модели; при снижении дискретизации обобщающая способность увеличивается, но уменьшается точность модели восстановления зависимости. В регрессионном анализе важно правильно выделить причинно-следственные связи между различными факторами и заложить эти соотношения в модель. Построение функций множественной нелинейной регрессии с помощью аналитических методов математической статистики в большинстве случаев невозможно.
В то же время, случай дискретной величины у = {1,... , L} (стандартная задача распознавания) в настоящее время достаточно хорошо изучен. Более 20 лет тому назад Ю.И.Журавлевым было отмечено, что задача распознавания может рассматриваться как задача экстраполяции специальных функций, когда независимые переменные (значения признаков) могут быть фактически произвольны, а зависимая величина принимает конечное число значений. В настоящее время существуют различные модели и конкретные алгоритмы для решения задач распознавания [1, 5, 7, 9,10,13, 20, 25].
Свойства модели при снижении числа интервалов разбиения
Случай 5. Степень первого полинома равна Adr, степень второго полинома равна Adr —Поскольку степень первого полинома превосходит степень второго на а 2 , то Эй 0 : Уи А(и)В\(и) А\(и)В(и). Случай 6 аналогичен случаю 5, т.к. правые части выражений совпадают. Для доказательства случаев 7, 8, 9, 10 достаточно перенумеровать интервалы (первый интервал становится последним, второй — предпоследним и т.д.) и воспользоваться уже рассмотренными случаями.
Корректность модели
Определение 7 Модель восстановления зависимостей называется квазикорректной, если для обучающей выборки {(2/«,#«)}i выполнено уі Є Ak = у{ є Ak, і = 1,... ,т. Определение 8 Модель восстановления зависимостей называется корректной, если для обучающей выборки {(2/«,#«)}i выполнено уі = уі,і = l,...,m. Определение 9 Моделью А\ называется байесовский корректор над логическими классификаторами с оценками вероятностей 1.12 при использовании «ответа по среднему». Определение 10 Моделью А2 называется байесовский корректор над логическими классификаторами с частотными оценками вероятностей при использовании «ответа по максимуму».
Определение 11 Моделью А2 называется байесовский корректор над логическими классификаторами со сглаженным/и частотными оценками вероятностей (ширина окна сглаживания d) при использовании «ответа по максимуму». Теорема 1 Модели Ai, А2 и А2 при непротиворечивой обучающей информации являются квазикорректными. Модель Ai обладает свойством ( ), используется «ответ по среднему», следовательно, Ai(fi) = J2t=i ct P(А ЖІ) = ck Є АЛ. Модель А2 обладает свойством), используется «ответ по максимуму», следовательно, А2(ХІ) = с& Є Д&. Модель А2 обладает свойством ( ) (P(Д&ЖІ) P(А ж ),/: т &)) ис_ пользуется «ответ по максимуму», следовательно, А2(х = с& Є Д&. Рассмотрим, для каких разбиений А области значений целевого признака модели восстановления зависимостей обладают свойством корректности. Обозначим т — число различных значений целевого признака в обучающей выборке, т! = {І/І}І- Множество с =1 совпадает с множеством {і/ }Е і тогда и только тогда, когда т! = п. Теорема 2 Модели Ai, А2 и А2 при непротиворечивой обучающей информации и разбиении А : т! = п области значений целевого признака являются корректными. Модель Ai обладает свойством ( ), используется «ответ по среднему», следовательно, Ai(fi) = YA=\ t P(Д Ж») = Ск = Уг Модель А2 обладает свойством ( ) (P(А ж ) 0 Ф t = к), используется «ответ по максимуму», следовательно, А2(ХІ) = Ck = у%. Модель А2 обладает свойством ( ) (P(Д&ЖІ) P(At\xi),t Ф к), используется «ответ по максимуму», следовательно, А2(х = с& = у{.
Свойства модели при снижении числа интервалов разбиения
Для обучения корректной модели восстановления зависимостей с разбиением области значений целевого признака на т интервалов необходимо обучить т — 1 классификаторов, т.е. число классификаторов сравнимо с количеством объектов обучающей выборки. Рассмотрим свойства байесовского корректора для разбиения А : А = п}п т!. В предыдущем разделе было показано, что байесовский корректор обладает свойством квазикорректности для любого разбиения.
Погрешность модели восстановления зависимостей У ]уі — с&. , УІ Є Д&., і = 1,... ,m. Заметим, что данное выражение совпадает с погрешностью разбиения Q(A), т.е. для построения модели с заданной погрешностью 5 необходимо построить разбиение с погрешностью 5. Приведем алгоритм построения байесовского корректора с погрешностью 5 на обучающей выборки: 2: for к = 1,..., [logm] do 3: строим разбиение на п& интервалов; 4: Qk = (7(1, П&) — суммарная ошибка; end for Итоговое значение n = n ogmy Утверждение 4 Алгоритмическая сложность построения разбиения для байесовского корректора, дающего суммарную ошибку Q(А) 6, равна 0(m3logm). Нетрудно заметить, что алгоритмическая сложность построения разбиения на п интервалов равна 0(т ). Сложность вычисления качества разбиения Q(A) есть О(т). Для выбора п необходимо сделать [logm] шагов. Т.о. общая сложность есть О(m3logm). 1.3. Линейный корректор 1.3.1. Общая схема построения модели Пусть задано разбиение области целевого признака А = {Д&}-=1 на п интервалов. Обозначим и] = —(fpt)—(jj-}i = 1, Составим вектор ответов и(х) = (1,щ(х),... ,UN(X)), щ{х) = uj, если классификатор А{ отнес объект х в класс Щ. Определение 12 Линейным корректором называется функция = (u(x),w), w — вектор весов, w Є Mw+1. m Вектор весов есть решение оптимизационной задачи 2(yi — f(x i)) =1 min. w Алгоритм восстановления зависимостей 1. формирование разбиений вещественной оси на интервалы Д&, к = 1,... ,п; 2. задание разбиений, формирование обучающих выборок задач распознавания Z{, і = 1,... , JV, выбор классификаторов их обучение; 3. вычисление вектора весов w. Алгоритм вычисления значения зависимой величины 1. классификация алгоритмами А\,... , А объекта х; 2. вычисление вектора ответов у(х); 3. вычисление значения у(х). 1.3.2. Корректность модели Далее рассматривается задача с числом классов L = 2. Зададим N = п — 1 задач классификации: для задачи Z{ вектор меток имеет вид (і), і = 1,. .. , N. Составим матрицу U Є Mmxn5 в которой г-я строка есть вектор ответов й{хі),і = l,...,m, и вектору Є Rm,y = {yi,... ,ут). Пара U, у обладает свойством: yi = yj Ф В матрице U совпадают строки і и j, т.е. гап/с [/ = гап/с [/"г/, вектор весов w есть решение системы линейных алгебраических уравнений Uw = у. При этом f(x{) = у І И справедлива Теорема 3 Линейный корректор является корректной моделью.
Изменение значений целевого признака
Рассмотрим задачу. Решение имеет вид w = (F F) F у, оценки значений целевого признака объектов обучающей выборки у = Fw = F(FTF) lFTy. Из вышеизложенных рассуждений вытекает
Утверждение 5 Оценки у значений целевого признака объектов обуча Е У г ющей выборки имеют вид = Заметим, что для объекта обучающей выборки Х{ : у І Є Ак выполнено уг = ск. Итак, Теорема 4 Линейный корректор для разбиения А : А = п}п т является квазикорректной моделью.
Заметим, что данное выражение совпадает с погрешностью разбиения Q(A), т.е. для построения модели с заданной погрешностью 5 необходимо построить разбиение с погрешностью 5. Для построения требуемого разбиения можно воспользоваться алгоритмом 1.2.5. Алгоритмическая сложность построения такого разбиения равна 0(m3 log ш). Глава 2. Устойчивость моделей
В данной главе рассматривается свойство устойчивости моделей «байесовский корректор» и «линейный корректор». Устойчивость является аналогом регулярности по Журавлеву [9] для распознающих алгоритмов. В главе 1 было показано, что байесовский и линейный корректор с корректными классификаторами для объекта вычисляет оценку значения Е Уз целевого признака А(х{) = у І = щ 3. д ,,,, у І Є А . Введем обозначение Далее под моделью А будем понимать байесовский или линейный корректор с корректными классификаторами.
Рассмотрим задачу с изменением описаний объектов Z m = {(xi ,у{)}7=1. Разбиение области значений целевого признака А задачи Z m для модели совпадает с разбиением А, т.к. значения целевого признака у одинаковы для задач Zm и Z m. При этом оценки значений целевого признака для задач Z m и Z m совпадают, у = у .
Рассмотрим пространство задач с метрикой Введем метрику на пространстве алгоритмов pA(A(Zm), A(Z m)) = \\у — у \\. Обозначим my{Z) — число различных значений целевого признака задачи Z. Обозначим A (Z) — модель для задачи Z с разбиением А : А = my{Z). Напомним, что модель A (Zm) корректна, у = у. Также корректна модель A (Z m), у = if.
Рассмотрим задачу с изменением значений целевого признака объектов Z m = {(Жг,?/9}1- Рассмотрим пространство задач с метрикой pY(Zm,Z m) = \\у — у \\. ( -окрестность задачи Zm есть Z{Zm) = Теорема 6 Модель А устойчива относительно изменений значений целевого признака. Действительно, pA(A(Zm),A(Z m)) = \\у-у \\ = \\у І/\\ = pY(Zm,Z m) 5.
Изменение описаний и значений целевого признака объектов Рассмотрим задачу с изменением описаний и значений целевого признака объектов Z m = {(ХІ ,2/ )}i- Рассмотрим пространство задач с мет
Теорема 7 Модель А устойчива относительно изменения описаний и значений целевого признака объектов. В определении устойчивости при заданном є возь мем 5 = wye. Рассмотрим модель А с разбиением А : А my(Z). Такая модель не обладает свойством корректности. Покажем, что свойством устойчивости она также не обладает. Рассмотрим задачи Zm и Zm, различающиеся только по значению це У, левого признака одного объекта, у Практическое сравнение моделей
В данной главе производится практическое сравнение моделей «байесовский корректор», «линейный корректор» и известных моделей восстановления зависимостей (линейная регрессия и ядерное сглаживание) по прецедентам на модельных и реальных прикладных задачах.
В качестве классификаторов в моделях «байесовский корректор» и «линейный корректор» использовался алгоритм голосования по системам логических закономерностей классов. Сравнение проводилось по следующим задачам: Была проведена серия из 10 экспериментов. В каждом эксперименте были взяты 10 различных двумерных нормальных распределений (мат. ожидания и дисперсии взяты из равномерного распределения), для каждого распределения была сгенерирована выборка из 12 точек, ему подчиненных.
Реальные задачи
Объединением этих данных было создано множество объектов: {{rSl\ a 2))}._, ,х 1\х 2 Є Ш. Была рассмотрена целевая зависимость у, совпадающая с точностью до знака с плотностью распределения для каждой выборки. Для первых 5 выборок значением являлась плотность, для остальных 5 — плотность со знаком минус. Данные были зашумлены 47 признаками, подчиненных равномерному распределению. Вклад в целевую зависимость они не вносили. Т.о. были получены описания 120 объектов, состоящих из 49 признаков и целевого признака. Данные были разбиты на непересекающиеся обучающую и контрольную выборки: 90 и 30 объектов соответственно. Задачи с порядковыми признаками
Была проведена серия из 10 экспериментов. В каждом эксперименте была сгенерирована выборка из 200 объектов: dim Xj = 3, хг- , хг- — реализации случайной величины = 0,... , 10 с вероятностями соответствен (3)
Задача заключается в определении частоты кризов артериальной гипер-тензии по медицинским показателям состояния пациента и принимаемым лекарственным препаратам [12] (описание объекта — бинарные и количественные признаки): возраст; рост; вес; длительность заболевания; наличие ишемической болезни сердца; наличие сахарного диабета; наличие пиелонефрита; наличие сердечной недостаточности; значения систолического и диастолического давления; уровни сахара и холестерина в крови; принимает ли ингибиторы АПФ, диуретики, а - и (3 -адреноблокаторы, дезагреган-ты, антагонисты кальция, антагонисты рецепторов ангиотензина II, гиполи-пидемические средства, агонисты имидазолиновых рецепторов. Множество объектов разбито на непересекающиеся обучающую (263 объекта) и контрольную (66 объектов) выборки. Особенностью данной задачи является наличие сложной функциональной зависимости между описанием объекта и значением целевого признака. Стоимость домов
Задача заключается в определении стоимости недвижимости в пригородах Бостона (задача из репозитория UCI [33]). Описание объекта состоит из бинарных и количественных признаков: уровень преступности на душу населения в районе; доля жилой земли среди земельных объектов площадью более 25000 кв. футов в районе; доля земель, не доступных для розничной торговли в районе; индекс «Charles River»; концентрация NO2 в районе; количество комнат в доме; доля домов, построенных до 1940 г. в районе; взвешенное расстояние до 5 деловых центров Бостона; уровень доступности радиальных шоссе; сумма налогов с 10 тыс. долларов США; соотношение количества учеников к количеству учителей в районе; доля негров в районе; доля населения, имеющих низкий статус. Множество объектов разбито на непересекающиеся обучающую (253 объекта) и контрольную (253 объекта) выборки.
Прочность бетона
Задача заключается в определении прочности бетона на основе данных о массовых долях компонент и возрасте бетона (задача из репозитория UCI [48]). Описание объекта состоит из количественных признаков: массовые доли цемента, шлакопортландцемента, летучей золы, воды, суперпластификатора, крупного и мелкого заполнителя, возраст бетона. Множество объектов разбито на непересекающиеся обучающую (772 объекта) и контрольную (257 объектов) выборки. Особенностью данной задачи является наличие сложной нелинейной зависимости между описанием объекта и значением целевого признака. 3.3. Результаты Прочность бетона 0.01551 0.01127 0.02117 0.01745 Стоит отметить, что модели «байесовский корректор» и «линейный корректор» дали меньшую среднеквадратичную ошибку на всех рассмотренных задачах.
Основные результаты работы заключаются в следующем: 1. Разработан общий подход к формированию задач распознавания и вычисления значения зависимой величины как коллективного решения. 2. Разработаны модели восстановления зависимостей «байесовский корректор» и «линейный корректор», предложены аналитические методы оценки параметров моделей. 3. Доказаны свойства корректности, квазикорректности и устойчивости моделей восстановления зависимостей «байесовский корректор» и «линейный корректор». 4. Подтверждена применимость разработанных моделей восстановления зависимостей для решения реальных прикладных задачах результатами практической апробации.
