Содержание к диссертации
Введение
Глава 1. Существующие подходы к повышению обобщающей способности алгоритмов эмпирического прогнозирования
1.1 Введение 18
1.2. Методы, основанные на повышении аппроксимирующей способности на обучающей информации 19
1.3. Методы, основанные на подборе модели, оптимальной по уровню сложности 21
1.4.Робастные процедуры 25
1.5. Методы регуляризации 27
1.6. Коллективные методы
1.6.1 Методы коллективной коррекции для групп алгоритмов 28
1.6.2 Методы голосования по множествам закономерностей 30
Глава 2. Методы повышения точности эмпирического прогнозирования, основанные на минимизации обобщённой ошибки
2.1. Функционал обобщённой ошибки в задачах прогнозирования скалярных величин и его составные элементы 37
2.2. Способы снижения составляющей нестабильности 41
2.3. Коллективные методы прогнозирования непрерывных величин, использующие взвешенное голосование
2.3.1. Введение 50
2.3.2. Метод взвешенных средних, минимизирующий компоненту нестабильности 51
2.3.3. Метод взвешенных парных регрессий 52
2.4. Использование Монте-Карло экспериментов для оценки эффективности коллективных методов
2.4.1 Сценарии экспериментов 53
2.4.2 Результаты экспериментов для метода среднеарифметических 55
2.4.3 Результаты экспериментов для метода взвешенных парных регрессий 57
2.5 Методы оценивание составляющей нестабильности 62
2.6 Обобщенная ошибка и методы её снижения в задачах с нескалярными прогнозируемыми величинами.
2.6 .1. Случай векторной прогнозируемой величины конечной размерности 64
2.6.2. Случай прогнозирования функциональных зависимостей 68
Глава 3. Процедуры эмпирического прогнозирования, основанные на взвешенном голосовании по системам базовых множеств в пространстве прогностических переменных .
3.1 Процедура статистически взвешенного голосования
3.1.1 Введение 74
3.1.1 Максимизации функционала правдоподобия специального вида 74
3.1.2. Использование процедуры статистически взвешенного голосования для прогнозирования скалярных непрерывных переменных 79
3.1.3 Использование процедуры взвешенного голосования для оценки кривых вероятности отказов 80
3.2 Процедура взвешенного голосования, основанная на интервальных оценках функционала локальных потерь
3.2.1 Введение 83
3.2.2. Неравенства для распределений функций Е,и(х) 85
3.2.3 Метод оценивания весовых коэффициентов, основанный на оптимизации функционала La[ Глава 4. Методы распознавания, основанные на голосовании по системам подобластей признакового пространства 4.1. Метод Статистически Взвешенных Синдромов 4.1.1 Введение 95 4.1.1. Методы построения синдромов 96 4.1.2. Выбор модели разбиений оптимального уровня сложности 98 4.1.3. Процедура вычисления оценок за классы в методе СВС 99 4.1.4. Отбор признаков 100 4.1.5. Решающее правило 102 4.2. Метод двумерных линейных разделителей 102 4.3. Алгоритм мультимодельного голосования с пропорциональной коррекцией 104 4.4. Исследование эффективности предложенных алгоритмов 4.4.1. Задачи 107 4.4.2. Результаты экспериментов 110 Глава 5. Методы повышения стабильности процедур обучения, основанные на идентификации выпадающих наблюдений 5.1. Введение 114 5.2. Монте-Карло исследования влияния выпадающих объектов на точность множественной линейной регрессии . 5.2.1 Используемые процедуры поиска выпадающих объектов 114 5.2.2. Сценарии экспериментов 117 5.2.3. Результаты экспериментов 118 5.3. Влияние выпадающих объектов на точность распознавания 125 Глава 6. Метод оценки статистической достоверности результатов эмпирического прогнозирования, основанный на перестановочном тесте 6.1 Ведение 130 6.2. Перестановочный тест 131 6.3. Примеры использования перестановочного теста 6.3.1. Прогноз результатов BCG терапии рака мочевого пузыря 135 6.3.2. Прогноз биологических свойств химических соединений по их молекулярной структуре 139 6.4 Точный расчёт распределения статистики перестановочного теста (опримизируемого функционала качества разбиений) при исследований зависимости бинарной величины от непрерывной прогностической переменной 6.4.1.Введение 142 6.4.2 Свойства оптимизируемого функционала качества 143 6.4.3 Алгоритм расчета распределения оптимальных значений функционала качества на множестве всевозможных перестановок 146 6.4.4.Численные эксперименты 153 Глава 7. Метод анализа данных, основанный на достоверных оптимальных разбиениях пространств прогностических переменных 7.1 Введение 157 7.2. Метод оптимальных разбиений 161 7.3. Оценки эффективности методов анализа данных, основанных на оптимальных разбиениях 7.3.1 Введение 170 7.3.2. Сценарий генерации выборок 170 7.3.3. Методика оценивания эффективности алгоритмов поиска закономерностей 173 7.3.4. Результаты тестирования метода ПЗ 175 7.3.5. Метод максимальной значимости и результаты его тестирования 177 7.3.6.Метод условных значимостей 179 7.3.7. Исследование зависимости эффективности поиска закономерностей от объёма обучающей информации 182 7.3.8. Заключение 185 Глава 8. Использование методов распознавания в медицинских исследованиях 8.1. Введение 188 8.2. Программные средства. 8.2.1. Введение 190 8.2.2. Программная система «РАЗБИЕНИЯ» 191 8.3. Примеры решённых задач 8.3.1 Прогнозирование исходов психогенных расстройств 195 8.3.2 Прогноз результатов лечения остеогенной саркомы 8.3.2.1 Постановка задачи 199 8.3.2.2. Прогнозирование гистологического ответа в ходе предоперационной химиотерапии 201 8.3.2.3. Прогнозирование отдалённых результатов лечения 203 8.3.3 Прогноз динамики депрессивных синдромов в остром периоде сотрясения головного мозга 204 Список литературы Введение к работе Актуальность темы. Методы прогнозирования, в основе которых лежат анализ внутренней структуры и эмпирической информации, получили значительное распространение в различных областях прикладных исследований. Методы такого рода далее будут называться методами эмпирического прогнозирования. Особенно интенсивно эмпирическое прогнозирование используется в слабоформализованных областях, где моделирование, основанное на априори известных и описывающих суть изучаемых явлений физических законах, невозможно или малоэффективно. К таким областям могут быть отнесены медицинские и биометрические исследования, различные задачи, возникающие в бизнесе, экономике, социологии, геологии, экологии, технике, сельском хозяйстве. В зависимости от типа прогнозируемой величины могут быть выделены три группы наиболее широко используемых методов эмпирического прогнозирования. К первой группе отнесем разнообразные методы регрессионного анализа, которые предназначены в основном для прогнозирования непрерывных скалярных величин по известным векторам прогностических (независимых) переменных. Ко второй группе, которая в настоящее время, по-видимому, лидирует по числу приложений, отнесем методы распознавания образов. Методы распознавания предназначены для отнесения объектов к конечному числу априори фиксированных классов по известным описаниям, которые обычно представляют собой вектора значений переменных (признаков). Можно выделить также третью группу методов, предназначенных для оценки по вектору прогностических переменных вероятности безотказной работы объектов в течение произвольного интервала времени, прошедшего с начала функционирования. Фактически векторам прогностических переменных ставятся в соответствие монотонно невозрастающие функции, заданные на некотором интервале временной оси. В основе всех вышеупомянутых методов лежит процедура обучения, заключающаяся в настройке параметров прогнозирующего алгоритма по имеющемуся в распоряжении исследователей массиву эмпирических данных, который мы далее будем называть обучающей выборкой. Естественно, что одной из центральных проблем, связанных с правомерностью использования эмпирического прогнозирования, является сохранение точности прогноза на новых аналогичных по типу и условиям получения объектах, но не содержащихся в обучающей выборке. Данное свойство прогнозирующих алгоритмов принято называть обобщающей или экстраполирующей способностью. Может быть выделен ряд основных направлений исследований, связанных с разработкой методов улучшения обобщающей способности. В их число входит разработка методов повышения точности прогноза или распознавания на известной обучающей информации. Повышение точности может быть достигнуто путём использования высокопараметризованных моделей с широкими возможностями аппроксимации. В качестве примера могут быть приведены алгоритмы распознавания из модели вычисления оценок[5,23, 25] , модели с потенциальными функциями[3], модели опорных векторов[84], многослойного перцептрона[4,68], методы, основанные на аппроксимации сплайнами. Одним из путей повышения аппроксимационных возможностей параметризованных моделей является использование их алгебраических замыканий относительно операций над матрицами оценок [24]. Однако при ограниченном объёме обучающей информации и высокой размерности данных чрезмерное увеличение аппроксимационных возможностей используемых методов приводит к потере устойчивости получаемых решений и к реальному снижению прогнозирующей способности на новой информации, которая не использовалась при обучении[12, 11]. Достаточно распространённым подходом к повышению точности распознавания является использование коллективных решений. При этом такие решения могут строиться как по набору заранее обученных алгоритмов из разных моделей, так и по наборам элементов (закономерностей), которые строятся в рамках одной модели. Существуют также целый ряд методов принятия коллективных решений наборами заранее обученных алгоритмов. Наряду с простейшими голосованием по большинству и классификацией по максимальным величинам суммарных оценок к их числу могут быть отнесены различные методы логической [30] и алгебраической коррекции. В качестве примеров моделей распознавания, основанных на голосовании по наборам закономерностей, могут быть названы тестовый алгоритм, алгоритмы типа Кора и Лорег[6,75,110], метод комитетов[42]. Вместе с тем описанные в литературе методы голосования носят в основном эвристический характер и не включают в себя статистически обоснованных процедур взвешивания различных элементов. Повышения точности эмпирического прогнозирования может быть достигнуто путём уменьшения или исключения влияния на обучение объектов, которые по разным причинам значительно отклоняются от закономерностей, связанных с задачей прогнозирования. К настоящему времени предложено большое число устойчивых к выпадающим объектам методов для прогнозирования непрерывных переменных [72,70,7]. В меньшей степени задача рассматривалась также в теории распознавания [70]. Однако слабо изученным остаётся количественное влияние выпадающих объектов на точность эмпирического прогнозирования с учётом степени их отклонения от основных закономерностей и распределения в пространстве прогностических переменных. С задачей собственно эмпирического прогнозирования связана не менее важная задача оценки влияния на прогнозируемую величину отдельных прогностических переменных или групп переменных. Широкий спектр методов для решения данной задачи был разработан в рамках теории математической статистики. К их числу следует отнести одномерные и многомерные статистические тесты, методы корреляционного, регрессионного, дисперсионного и ковариационного анализов. Однако методы корреляционного и линейного регрессионного анализа требуют предположений о линейном характере зависимостей, дисперсионный анализ применим только в случае категориальных или порядковых прогностических переменных с ограниченным числом возможных значений. Основные цели работы. Наиболее значимой целью работы является новых методов распознавания и других методов эмпирического прогнозирования, обладающих высокой обобщающей способностью. Данная цель включает в себя также тестирование разработанных методов на достаточно представительных наборах практических или искусственно сгенерированных задач и выявление условий их наиболее эффективного функционирования. Целью исследования также является разработка универсальных методов, позволяющих оценивать влияние на прогнозируемую величину отдельных прогностических переменных или групп переменных. Научная новизна исследования. Рассматривался подход к повышению обобщающей способности методов эмпирического прогнозирования, основанный на минимизации обобщённой ошибки прогнозирования, представляющей собой усреднение ошибки не только по пространству всевозможных объектов, для которых осуществляется прогноз, но и по пространству всевозможных обучающих выборок. Обобщённая ошибка может быть представлена в виде суммы трёх составляющих: неустранимой шумовой составляющей, составляющей смещения и составляющей нестабильности. Составляющая смещения представляет собой среднеквадратичное отклонение математического ожидания прогнозирующей функции по пространству обучающих выборок (ПОВ) от условных математических ожиданий в точках пространства прогностических переменных. Составляющая нестабильности представляет собой усредненное по среднеквадратичное отклонение прогнозирующих функций от их, усредненных по ПОВ значений. Неустраняемая шумовая составляющая представляет собой среднеквадратичное отклонение прогнозируемой величины от условных математических ожиданий в точках пространства прогностических переменных. Повышение обобщающей способности методов эмпирического прогнозирования может достигаться путём снижения составляющих смещения и нестабильности. В качестве средств снижения составляющих смещения и нестабильности рассматривались коллективные методы. На первом шаге рассматривалась задача прогнозирования скалярных переменных. Было показано, что использование в качестве прогнозируемых значений среднеарифметических значений по наборам прогностических алгоритмов приводит к коллективному методу, для которого составляющие смещения, нестабильности и, как результат, вся обобщённая ошибка не превышают средние значения этих параметров по наборам. При этом может достигаться значительное снижение составляющей смещения, зависящее от величины взаимных различий алгоритмов коллектива. Откуда может быть сделан вывод об эффективности наборов относительно слабо коррелирующих друг с другом алгоритмов с низкими значениями составляющей нестабильности. В частности могут быть использованы наборы алгоритмов, осуществляющих прогноз по подмножествам переменных с размерностью существенно меньшей размерности исходной задачи. Данный вывод был убедительно подтверждён для коллективов алгоритмов множественной линейной регрессии с помощью Монте-Карло экспериментов. Было показано, что аналоги результатов, касающихся поведения составляющих обобщённой ошибки для метода среднеарифметических значений, справедливы также для задач прогнозирования векторных величин и функциональных зависимостей. Была разработана процедура построения прогнозирующих функций путём взвешенного голосования по системам подобластей в многомерном признаковом пространстве (базовых множеств). Весовые коэффициенты при голосовании вычисляются путём максимизации функционала правдоподобия специального вида. Данную процедуру построения прогнозирующих функций далее будет называться методом прогнозирования статистически взвешенным голосованием (ПСВГ). Недостатком метода ПСВГ является независимое включение в используемый функционал правдоподобия сомножителей, соответствующих отдельным базовым множествам. При этом не предполагается учёт меры их взаимного пересечения, что в реальности может привести к существенному завышению вклада множеств, в значительной степени дублирующих друг друга. В связи с этим была предложена процедура построения оптимальных коллективных решений, основанная на минимизации оценок локального функционала потерь и принимающая во внимание степень коррелированности вошедших в коллектив элементов. Метод ПСВГ был использован при построении ряда алгоритмов распознавания. В первую очередь здесь следует упомянуть разработанный автором совместно с группой сотрудников Института биохимической физики им. Н.М.Эмануэля РАН метод «Статистически взвешенные синдромы» [35,97], в котором в качестве базовых множеств выступают двумерные и одномерные частичные логические закономерности. При этом граничные точки, формирующие логические закономерности ищутся с помощью метода оптимальных разбиений интервалов допустимых значений отдельных признаков. Отбор закономерностей производится по величине функционала, характеризующего степень разделения классов, при возможном использовании также функционала, характеризующего стабильность границ. Метод СВС был достаточно успешно использован при решении целого ряда практических задач [29,31,35,36,92]. Вместе с тем в нём используются только одномерные модели оптимальных разбиений, а в голосовании участвуют только закономерности, выделенные с помощью границ, параллельных координтным осям. Для преодоления этих ограничений были предложены метод двумерных линейных разделителей (ДЛР) [86] и метод мультимодельного голосования с пропорциональной коррекцией (МГПК), [66] использующие для вычисления оценок за классы процедуру ПСВГ. В методе ДЛР базовые множества формируются путём дихотомических разбиений двумерных областей допустимых значений пар признаков. При этом разбиения производятся с помощью прямых с произвольной ориентацией относительно координатных осей, а элементы разбиения включаются в систему базовых множеств при превышении порогового значения функционала, характеризующего степень разделения классов. В методе МГПК совместно используются базовые множества, полученные с помощью а) одномерных разбиений; б) двумерных разбиений с границами, параллельными координатным осям; в) двумерных разбиений, производимых с помощью прямых с произвольной ориентацией относительно координатных осей. Также как и в методах ДЛР и МГПК в систему базовых множеств включаются элементы разбиений, для которых величина функционала, характеризующего степень разбиения, превышает пороговые значения. Для снижения эффекта перенастройки величины пороговых значений варьируются в зависимости от сложности используемой модели разбиений. В работе произведён сравнительный анализ трёх методов. Исследования показали, что метод МГПК в среднем обеспечивает высокую точность на широком круге задач. В диссертации также представлен ряд исследования по оценке влияния выпадающих объектов на экстраполирующую способность множественной линейной регрессии и линейного дискриминанта Фишера. Исследования проводились на искусственно сгенерированных выборках данных с различным характером отклонения распределения выпадающих объектов от распределения. В ходе исследований были предложены новые процедуры выявления выпадающих объектов и проведена оценка их эффективности. В диссертации также исследуется задача оценки статистической достоверности зависимости прогнозируемой величины от группы прогностических переменных, выявленной с помощью методов эмпирического прогнозирования. В качестве средства оценки достоверности рассматривается перестановочный тест, не требующий предположений о характере шумовой составляющей и ограничений на размер выборок. Предложен новый метод исследования влияния отдельных прогностических переменных, а также пар переменных на прогнозируемую величину. Метод основан на построении оптимальных разбиений областей допустимых значений прогностических переменных в рамках моделей различного уровня сложности. Для верификации выявленных таким образом закономерностей используется перестановочный тест и его модификации. Эксперименты, проведённые на искусственно сгенерированных выборках, продемонстрировали возможности метода по выявлению закономерностей, предусмотренных сценарием генерации данных, а также низкую вероятность включения в выходной набор ложных и частично ложных закономерностей. Важным преимуществом разработанного метода построения оптимальных статистически достоверных разбиений является возможность использования его в задачах со смешанным типом скалярных прогностических переменных, включая непрерывные, порядковые и категориальные переменные. Метод допускает также и самую разнообразную природу прогнозируемых величин. В качестве прогнозируемых переменных, наряду со скалярными переменными, могут выступать также и векторные величины, а также кривые выживаемости. 1) Совокупность теоретических и экспериментальных результатов, устанавливающих взаимосвязь составляющих смещения и нестабильности для метода среднеарифметических значений по коллективу прогностических алгоритмов со средними значениями данных составляющих по алгоритмам коллектива. Взаимосвязь установлена для задач прогнозирования как скалярных, так и векторных величин, а также функциональных зависимостей. Процедура построения прогнозирующих функций путём взвешенного голосования по системам подобластей в многомерном признаковом пространстве (базовым множествам), в которой весовые коэффициенты при голосовании вычисляются путём максимизации функционала правдоподобия специального вида. Процедура построения оптимальных коллективных решений, основанная на минимизации оценок локального функционала потерь и принимающая во внимание степень коррелированности вошедших в коллектив элементов. Методы распознавания, основанные на взвешенном голосовании по системам подобластей признакового пространства. Методы выявления в данных объектов, выпадающих из основных закономерностей, основанные на использовании искажений регрессионных функций или разделяющих поверхностей. Совокупность результатов, обосновывающих использование перестановочных тестов в качестве средства оценки достоверности результатов эмпирического прогнозирования. Метод анализа данных, основанный на построении оптимальных разбиений пространства прогностических переменных в рамках заранее фиксированных моделей различного уровня сложности и использующий для верификации перестановочные тесты. Результаты применения разработанных методов распознавания данных для решения задач медицинской диагностики и прогнозирования. Методы исследований. В работе использованы методы математической теории распознавания образов, а также методы математической статистики. Практическая значимость. Разработанные метод поиска закономерностей с помощью оптимальных статистически достоверных разбиений (см. Гл. 7), метод распознавания "Статистически взвешенные синдромы" (см. Гл. 4), а также методика верификации, основанная на перестановочном тесте были реализованы в рамках программной системы РАЗБИЕНИЯ. Метод "Статистически взвешенные синдромы" вошёл в состав программной системы "РАСПОЗНАВАНИЕ". Разработанные методы успешно использовались для решения прикладных задач в сотрудничестве с Институтом Биохимической Физики им. Н.М.Эммануэля РАН, Научно-исследовательским институтом неврологии РАМН, Российским онкологическим научным им Н.Н.Блохина РАМН, 1586 Окружного военного клинического госпиталя МВО РФ, Институтом органической химии РАН, Эдинбургским университетом (Великобритания) и др. При этом метод оптимальных разбиений, описанный в Главе 7, использовался для детального изучения влияния потенциальных прогностических показателей на зависимую величину с целью выявления оптимального набора. Метод «Статистически Взвешенные Синдромы», описанный в Главе 4, использовался для решения собственно диагностических или прогностических задач. Для статистической верификации полученных решений использовалась представленная в Главе 6 методика, основанная на перестановочном тесте. Результаты большинства исследований опубликованы в научной периодике или представлены на конференциях соответствующей тематики. Апробация работы. Основные результаты работы докладывались и обсуждались на Всероссийских конференциях "Математические методы распознавания образов" (6-ая Москва, 1993 г., 7-ая Москва, 1995 г., 8-ая Москва, 1997г., 9-ая Москва, 1999 г., 10-ая Москва, 2001 г., 11-ая Москва, 12-ая Москва, 2003 г.); на международной конференции "Математические методы интеллектуализации обработки информации" (Алушта, 1996 г.), "Распознавание образов и обработка информации" (Минск, 2003 г.); COMPSTAT 2000 (Утрехт, Нидерланды, 2000); 2 Conference «Computer Science and Information Technologies - CSIT-99» ( Ереван, Армения, 1999 г.); на международных конференциях «Распознавание образов и анализ изображений: новые информационные технологии» (РОАИ-3-98, Нижний Новгород, 1996, РОАИ-5-2000, Самара, 2000г.; РОАИ-6-2002 Великий Новгород, 2002г.; РОАИ-7-2004, Санкт-Петербург, 2004); на 18-ом международном семинаре по статистическому моделированию (Лёвен, Бельгия, 2003), International conference on systems and signals in intelligent technologies (Минск, 1998 г.), на 14-ом международном семинаре по статистическому моделированию ( Грац, Австрия, 1999г.); Международная научно-практической конференция «KDS-2001»(Санкт Петербург, 2001); Fourth International Conference «Pattern Recognition and Information Processing-PRIP'97» (Минск, 1997 г.); на 6-ом открытом германо-российском семинаре "Pattern Recognition and Image Understanding" (Новосибирск, 2003), на 14-ой международной конференции по распознаванию образов (Брисбен, Australia, 1998) В методах эмпирического прогнозирования значения прогнозируемой переменной Г по вектору прогностических переменных Xv ... ,Хр, производится с помощью алгоритма, построенного по массивам данных, аккумулирующим опыт предшествующего наблюдения за переменными. Согласно терминологии распознавания образов, выборку данных, используемую для построения прогнозирующего алгоритма, будем называть обучающей. Далее предполагается, что прогностические переменные представляют собой скалярные величины, принимающие значения из некоторого множества точек вещественной оси. В качестве прогнозируемой переменной Y могут выступать величины различной природы. В практических приложениях часто возникают задачи прогнозирования скалярных непрерывных переменных, которая обычно решается с помощью разнообразных методов регрессионного анализа. В качестве обучающей выборки при этом используется набор S0={(yl,xl),...,(ym,xm)}, где у. -значения переменной Y, a xl5...,xm- соответствующие значения векторов переменных Хх, ... ,Хр. Задаче распознавания принадлежности объектов, описываемых векторами признаков, классам KV...,KL, очевидно, соответствует задача прогнозирования векторов бинарных переменных размерности L. При этом /- ая компонента вектора Y дяя объекта s принимает значение 1, если seKnn значение 0 в противном случае. Задаче прогнозирования вероятности отказа объекта к моменту времени t с начала функционирования соответствует задача прогнозирования монотонно невозрастающих функций, принимающих значения из отрезка [0,1] и заданных на некотором отрезке вещественной оси. В качестве обучающей выборки в задачах прогнозирования вероятностей отказов используется набор вида So = (s, =(al,tl,xl),...,sm= (am,tm,xm)}, где t, - момент последнего наблюдения за объектом -si eS0, а бинарный индикатор а. указывает, существовал ли объект st в момент времени tj, или в момент ti была зафиксирована его "гибель". В настоящее время существуют различные подходы к решению задачи прогнозирования вероятности отказов, наиболее известным из которых является использование модели Кокса[81]. 1.2 Методы, основанные на повышении аппроксимирующей способности на обучающей информации. Среди используемых подходов к увеличению экстраполирующей способности эмпирического прогнозирования в первую очередь следует упомянуть повышение точности аппроксимации зависимости прогнозируемой величины от прогностических переменных на самой обучающей выборке. Одним из способов повышения точности является выбор наиболее подходящей модели - вида используемой для аппроксимации параметризованной функциональной зависимости. Такой подход является эффективным в случаях, когда вид зависимости может быть предположен заранее с достаточной долей уверенности. Однако в большинстве случаев его использование затруднено из-за высокой трудоёмкости, связанной с перебором возможных вариантов. Другим подходом является использование моделей общего вида, содержащих богатые семейства функциональных зависимостей. В качестве примеров в частности могут быть приведены известные классы моделей распознающих алгоритмов: модели вычисления оценок [5, 23, 25], модели типа потенциальных функций [3], ядерные методы, нейросетевые модели типа многослойного перцептрона [4, 68]. Обучение в случаях моделей общего вида, как правило, требует использования специализированных процедур оптимизации, максимизирующих точность аппроксимации на обучающей выборке. Так при обучении нейросетевых алгоритмов типа многослойного перцептрона обычно используется метод обратного распространения ошибки. При обучении алгоритмов типа вычисления оценок используются методы поиска максимальных подсистем систем линейных неравенств [53, 32]. Ещё одним способом улучшения точности эмпирического прогнозирования путем повышения качества аппроксимации на обучающей информации является построение нового оптимального прогностического алгоритма по множеству обученных заранее алгоритмов с использованием набора корректирующих операций. В работах [24, 26] предложен широко известный метод построения по множеству априори существующих алгоритмов распознавания {А} нового алгоритма, превосходящего по точности каждый из алгоритмов из {А}. Было показано [26], что произвольный алгоритм А для распознавания принадлежности объектов классам К,,...,К, представим как последовательное выполнение оператора В и распознаваемому объекту s действительный вектор размерности L, по которому далее решающее правило С вычисляет собственно информационный вектор, описывающий принадлежность S классам К,,...,Кт. Пусть {В} - множество операторов, соответствующих алгоритмам из {А}. Метод конструирования новых алгоритмов основан на использовании операций алгебраической коррекции, заданных на множестве числовых матриц, генерируемых операторами из множества {В}. В [26.] анализируются условия, при которых возможно построение методами алгебраической коррекции алгоритмов, правильно распознающих решающего правила С. При этом оператор В вычисляет по произвольному объекты произвольной выборки S ,...,Sq. При построении коллективных методов прогнозирования важную роль могут играть как вопросы формирования исходного коллектива прогностических методов {П .-.Л }, так и вопрос организации собственно процедуры принятия коллективного решения. Наиболее последовательным подходом к формированию {П1,...,П1} является включение в набор алгоритмов с низкими значениями обобщённой ошибки, с возможно большим разбросом D(x), а также с возможно меньшими значениями коэффициентов KjXx) в каждой точке пространства прогностических переменных. Однако одновременное достижение всех этих условий является на практике трудноосуществимым. Одним из путей является поиск эффективного метода прогнозирования с дальнейшей генерацией на его основе множества прогностических алгоритмов с использованием технологий бэггинга или бустинга [77, 89, 96]. Возможность значительного снижения компоненты смещения при одновременном снижении компоненты нестабильности позволяет сделать предположение об эффективности подхода, в котором в набор {Пр...,!! } включаются стабильные слабо коррелирующие друг с другом алгоритмы. Такой подход может быть реализован путём построения набора прогностических алгоритмов по системе подмножеств прогностических признаков небольшой размерности. При этом высокая стабильность алгоритмов достигается благодаря низкой размерности соответствующих подмножеств прогностических переменных. Взаимная корреляция алгоритмов определяется взаимной корреляцией подмножеств переменных. Эффективность методов, основанных на принятии коллективных решений по системам алгоритмов низкой размерности, подтверждается результатами экспериментов, представленными в настоящей главе в параграфах 2.4.2, 2.4.3.. Может быть предложен целый ряд подходов к организации процедур принятия коллективных решений. В параграфах 2.3.2 , 2.3.3 представлены методы взвешенных средних для коллективов линейных регрессий. В главе 3 рассмотрены методы построения коллективных решений по системам подобластей пространства прогностических переменных (базовых множеств). В главе 4 представлены методы распознавания, основанные на принятии коллективных решений по системам базовых множеств низкой размерности. Конечно использование метода среднеарифметических, предполагающих равноправное вхождение различных эмпирических моделей в окончательную модель не является единственно возможным способом построения коллективного решения. Простейшими обобщениями метода среднеарифметических являются метод взвешенных средних [116]. Метод взвешенных средних, в котором коллективное решение строится по множеству методов її = {П1,...,ПІ} будем далее обозначать nw(n). Сопоставим методам Ul,...,UL неотрицательные вещественные числа cx,...,cL, удовлетворяющие условию с(. =1. Коллективную взвешенную 1=1 прогнозирующую функцию ЛДхДп, с) в методе Uw(fl) будем задавать суммой прогнозирующих функций методов П1,...,ПІ, умноженных на L соответствующие коэффициенты cv...,cL. То есть hw(x,S,fl,c) = Y,cMx S)- В 1-І качестве оптимальных могут быть использованы значения коэффициентов с,,...,сх, минимизирующие компоненту нестабильности. Компонента нестабильности может для метода быть представлена в виде lijitt M nn.x) V(nj,x)}?l(d4)=±YjfjCicjyij, rij м м L 1=1 j=i где = Ky(x)Jv(Jl.,x) Jv(n .,х)Р,0Ц). Следовательно, задача минимизации компоненты нестабильности сводится к задаче билинейного программирования j L L 72ЕЕс/с/(/- тіп L /=i;=l /=i Существенными недостатками подхода к увеличению точности прогноза, основанного на минимизации компоненты нестабильности как функции весовых коэффициентов c ,...,cL, является трудность получения достаточно точных оценок коэффициентов /... Кроме того, его использование полностью игнорирует происходящие одновременно изменения компоненты смещения, которая также может вносить существенный вклад в величину ошибки. Альтернативным путем построения эффективных коллективных решений являются эвристические и полуэвристические подходы, примером использования которых является метод взвешенных парных регрессий. При построении коллективных методов прогнозирования важную роль могут играть как вопросы формирования исходного коллектива прогностических методов {П .-.Л }, так и вопрос организации собственно процедуры принятия коллективного решения. Наиболее последовательным подходом к формированию {П1,...,П1} является включение в набор алгоритмов с низкими значениями обобщённой ошибки, с возможно большим разбросом D(x), а также с возможно меньшими значениями коэффициентов KjXx) в каждой точке пространства прогностических переменных. Целью использования процедуры взвешенного голосования [59,113] является построение детерминированной функции прогностических переменных, максимально коррелирующей с прогнозируемой функцией Y. Пусть случайная функция Y стохастически зависит от прогностических переменных Х,,...,Хп. При этом в нашем распоряжении имеется эмпирическая выборка данных (обучающая выборка) SQ = {Cv1,x1), ...,(ут,хт)}, где {ух, ...,ут}- значения реализаций функции Y, a {Xj,...,xw}- соответствующие им вектора значений прогностических переменных. Предположим, что задана конечная система подобластей базовых множеств QQ с В", где В" - система борелевских множеств пространства R". Через (X обозначим минимальная алгебра, содержащая Q0, а через Q множество элементов QL которые не могут быть представлены в виде объединения других элементов QQ . Предположим, что некоторая точка х принадлежит элементу q множества Qx. В качестве прогнозируемого значения функции Y в точке х естественно \YP(daJ) ВД использовать условное математическое ожидание: М(Г q) = Определение. Функция м(х) определяется таким образом, что %u(x) = M(Y\q), где gэлемент Qj , содержащий точку х. Легко показать, что yfQeQ0M(4u\Q) = M(Y\Q) ZJYP(da ) М(У?)Р( 7) Через Vi обозначим среднее значение прогнозируемой функции Y на объектах обучающей выборки с векторами значений прогностических переменных, принадлежащих базовому множеству Q.. То есть г т /\ У і9 где тГ число объектов обучающей выборки с векторами прогностических переменных принадлежащих базовому множеству Q{. Предположим, что точка х принадлежит базовым множествам Q ,...,Qp из системы Q0. Мы будем аппроксимировать плотность распределения f?(V.) величины V, и распределения fi(%u) функции fM(x) внутри базового множества Q., используя нормальный закон: (4)= [4 м(Уй,.)]- еХр{-%ет!} i = l,...,p Для обоснования аппроксимации //( -) с помощью нормального закона может быть использована центральная предельная теорема. В случае если базовые множества задаются априори независимо от обучающей выборки, сумма 2_. У,- может интерпретироваться как сумма mi независимых одинаково распределенных случайных величин имеющих математическое ожидание М(У?) и дисперсию D(Y\Qi). При т;— оо плотность распределения Vi стремится к / (Vf). Для обоснования аппроксимации распределения функции и(х) внутри базового множества Q. с помощью нормального закона может быть использован принцип максимума энтропии. Функцию "правдоподобия" L определим как произведение плотностей вероятностей fy(Vj) и ff( u). Неизвестные условные математические ожидания M(Y\q),M(Y\Q]),...,M(Y\Qp) будем рассматривать как неизвестные параметры zQ,...,zp соответственно. Тогда функцию правдоподобия L можно записать в виде Uz . z flNfiz NjiV ) Точка максимума функционала L(ZQ,...,ZP) совпадает с точкой минимума функционала L(Z0—V- 2D(rQ) 2Д ф] В качестве оценок условных математических ожиданий M(Y\q),M(Y\Ql),...,M(Y\Qp) будем рассматривать значения параметров zQ,...,zp, доставляющие минимум функционалу L ( 0,...,zp). Одной из причин высокой нестабильности эмпирического моделирования может явиться наличие в обучающих выборках относительно небольшой доли объектов, значительно отклоняющихся от основной закономерности, существующей в данных. В случае если выпадающие наблюдения случайным образом разбросаны в пространстве прогностических переменных, они могут вызывать также случайные отклонения оптимальных прогнозирующих функций, повышая при этом компоненту нестабильности. Соответственно, уменьшение вклада выпадающих наблюдений в оптимизируемые функционалы или полное исключение их из обучающих выборок может привести к снижению компоненты нестабильности и к соответствующему увеличению точности прогноза Исследования, представленные в настоящем разделе, преследовали две цели. Первой целью являлась количественная оценка влияния выпадающих объектов в составе обучающей выборки на точность прогноза при различных типах их распределения в данных. Второй целью являлось разработка и тестирование новой процедуры идентификации выпадающих объектов. Разработка данной процедуры связана со стремлением повысить точность идентификации в задачах более высокой размерности при ограниченном объёме обучающих данных. Были использованы две процедуры поиска выпадающих объектов, которые далее будут называться процедурами R и RI. В обеих этих процедурах на каждом шаге по текущей обучающей выборке S ={sl = (yvx]),...,sm ={ут ,\щ)} строится соответствующая оптимальная регрессионная поверхность h(x,S(). В процедуре R для идентификации объекта s-eS как выпадающего из общей закономерности используется величина невязки R(s .,S ) = [у -h(x -,S )] , то время как в процедуре RI для идентификации s. наряду с R(si,St) используется также величина 3 J искажения линейной регрессионной функции D{s-,Sl), связанная с s-. Величина D(s .,S{) вычисляется по множеству точек {х[,...,хп}пространства прогностических переменных, случайным образом выбранных из окрестностей точек {xlv..,xw}, соответствующих объектам S . Пусть хг- = (х .,...,хг ). Для вычисления компоненты х\: ищется [д/mj ближайших соседей компоненты х- вектора х,, по которым вычисляются соответствующие выборочные среднее М и дисперсия D. Величина Г. выбирается из нормального распределения N(M,D). Множество точек {хГ,...,х„} используется вместо {x«,...,xm} для того, чтобы избежать занижения величин D(s :,Sl0) вследствие эффекта "сверхнастройки". Величина искажения вычисляется по формуле На первом шаге процедуры R в исходной выборке S0 ищется объект s\utc максимальным значением величины невязки R{s[0Ut,S0) и формируется новая текущая выборка S[ = S0\s\ut. На А:-ом шаге процедуры в выборке iff, ищется объект SgUf с максимальным значением R{s )Ut,StkA). Процедура прекращается в случае выполнения неравенства к ктах = [03т]. В результате формируется выборка потенциальных выпадающих объектов SL = {smt,- smt } Размером ктах. На первом шаге процедуры RI в исходной выборке S0 ищется объект s\ut с максимальным значением произведения R{sl0Ut,S0)D{s])Ut,S0) и формируется новая текущая выборка S[ =S0\s\ut. Аналогично с процедурой R на к -ом шаге процедуры RI ищется объект s\ut с максимальным Л с/ \т\(сЛ с/ значением произведения R{s0Ut,Slk_ D{sK0Ut,Stk_ . Также как и процедура R процедура RI прекращается в случае выполнения неравенства k krw.= [0.3/я]. Для каждой из текущих выборок «у дополнительно т. вычисляется функционал стабильности 0( ) = V )(.$, ). Среди к=\ выборок SL...,Sl ищем выборку S[ с минимальным значением функционала Ф. В результате формируется выборка потенциальных выпадающих объектов S%ut = {slut,...,%/} размером ks. На втором этапе в случае обеих процедур вычисляется средняя величина квадрата невязки на S\S$ut для регрессионной функции h(x,S\Sgut) : A( L)=i Z [yj-hiXjJXSPj]2 ,memp=\S\SPut\ ТИ Далее те объекты из Sgut, для которых R(s .,S\Sgut) 3.0 A(S\SPut)—— mfs P исключаются из множества потенциальных выпадающих объектов. В результате на выходе второго этапа формируется окончательная выборка выпадающих объектов Sf.Методы, основанные на повышении аппроксимирующей способности на обучающей информации
Коллективные методы прогнозирования непрерывных величин, использующие взвешенное голосование
Максимизации функционала правдоподобия специального вида
Монте-Карло исследования влияния выпадающих объектов на точность множественной линейной регрессии
Похожие диссертации на Методы эмпирического прогнозирования, основанные на устойчивых разбиениях и коллективных решениях
