Шаговая регрессия (пример)
Материал из MachineLearning.
(→Исходный код) |
|||
(28 промежуточных версий не показаны.) | |||
Строка 1: | Строка 1: | ||
{{TOCright}} | {{TOCright}} | ||
- | [[ | + | Решение практических задач восстановления [[регрессионный анализ|регрессионной]] зависимости требует рассмотрения большого числа порождаемых признаков. Процедура построения регрессионных моделей состоит из двух шагов. На первом шаге, на основе свободных переменных- результатов измерений, порождается набор признаков. На втором шаге производится выбор признаков. При выборе признаков выполняется настройка параметров модели, оценивается её качество. Модель с настроенными параметрами, доставляющая минимум заданному функционалу качества, называется моделью оптимальной структуры. |
- | + | ||
- | + | ||
- | + | Среди методов отбора признаков широкое распространение получил шаговый метод, впервые предложенный в 1960 году Эфроимсоном. На каждом шаге признаки проверяются на возможность добавления признаков в модель или удаления из модели, основываясь на F-статистике. Также могут быть использованы другие способы определения значимости признака, например, [[критерий Акаике| критерий Акаике]], [[Байесовский информационный критерий| Байесовский критерий]], критерий Маллоуза. | |
- | [[Метод наименьших углов(пример)|Метод наименьших углов]] (англ. least angle regression, LARS) - | + | В данной статье рассматриваются два метода отбора признаков: метод наименьших углов и шаговая регрессия. Эти методы похожи. Различие заключается в том, что алгоритм LARS, вместо последовательного добавления и удаления свободных переменных, на каждом шаге изменяет их веса. |
+ | |||
+ | [[Метод наименьших углов (пример)|Метод наименьших углов]] (англ. least angle regression, LARS) - | ||
алгоритм отбора признаков в задачах линейной [[регрессия|регрессии]]. При большом количестве свободных переменных возникает проблема [[ридж-регрессия|неустойчивого оценивания]] весов модели. | алгоритм отбора признаков в задачах линейной [[регрессия|регрессии]]. При большом количестве свободных переменных возникает проблема [[ридж-регрессия|неустойчивого оценивания]] весов модели. | ||
LARS предлагает метод выбора такого набора свободных переменных, который имел бы наиболее значимую статистическую связь с | LARS предлагает метод выбора такого набора свободных переменных, который имел бы наиболее значимую статистическую связь с | ||
зависимой переменной. Также LARS предлагает метод оценки весов. | зависимой переменной. Также LARS предлагает метод оценки весов. | ||
- | == | + | == Постановка задачи == |
- | Цель | + | Цель шаговой регрессии состоит в отборе из большого количества предикатов небольшой подгруппы переменных, которые вносят наибольший вклад в вариацию зависимой переменной. |
- | Пусть нам задана регрессионная модель | + | Пусть нам задана [[регрессионная модель| регрессионная модель]] |
- | ::<tex> y= f(\beta, x) +\mathbf{\varepsilon}</tex> | + | ::<tex> y= f(\beta, x) +\mathbf{\varepsilon}</tex>, |
- | Алгоритм заключается в последовательном добавлении и удалении признаков согласно определённому критерию. Обычно используется [[Критерий Фишера|F- критерий]], который имеет вид | + | где <tex> x </tex>- свободная переменная, <tex> y </tex>- зависимая переменная, <tex> \beta </tex>- набор параметров, <tex> \varepsilon</tex>- случайная аддитивная величина. |
+ | |||
+ | Алгоритм заключается в последовательном добавлении и удалении признаков, согласно определённому критерию. Обычно используется [[Критерий Фишера|<tex> F </tex> -критерий]], который имеет вид | ||
::<tex>F={\frac{S_1-S_2}{S_2}}{\frac{m-p_2}{p_1-p_2}</tex> | ::<tex>F={\frac{S_1-S_2}{S_2}}{\frac{m-p_2}{p_1-p_2}</tex> | ||
- | где индекс 2 соответствует второй регрессионной модели , индекс 1 соответствует первой регрессионной модели, которая является модификацией второй модели; <tex> p_1, p_2 </tex>- соответствующие числа параметров модели; <tex>S</tex>- сумма квадратов невязок, задающий критерий качества модели | + | где индекс 2 соответствует второй регрессионной модели , индекс 1 соответствует первой регрессионной модели, которая является модификацией второй модели; <tex> p_1, p_2 </tex>- соответствующие числа параметров модели; <tex>S</tex>- сумма квадратов невязок, задающий критерий качества модели: |
- | ::<tex>S=\sum_{i} {(y^i-f(\beta, x^i))^2</tex> | + | ::<tex>S=\sum_{i} {(y^i-f(\beta, x^i))^2</tex> |
- | + | Требуется найти набор признаков, удовлетворяющий <tex>F</tex>-критерию. | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | Требуется найти набор признаков | + | |
== Описание алгоритма == | == Описание алгоритма == | ||
- | + | Шаговая регрессия включает два основных шага: шаг Add (последовательное добавление признаков) и шаг Del (последовательное удаление признаков). | |
- | + | Обозначим текущий набор признаков <tex> A </tex>. Начальным набором является пустой набор <tex> A= \emptyset</tex>. К текущему набору <tex> A </tex> присоединяется по одному признаку, который дoставляет максимум <tex>F</tex>-критерию или | |
- | + | ::<tex> j^*= arg \max_{j\in J}F_{add}= arg \max_{j\in J}{\frac{S(A)-S(A\cup x^j)}{S(A\cup x^j)}} </tex> | |
- | ::<tex> j^*= arg \min_{j\in J} | + | Добавляется несколько признаков, пока значение критерия на шаге не станет меньше заданного <tex> F_1 </tex>. Затем признаки удаляются по одному так, чтобы значение <tex>F</tex>-критерия было минимально: |
+ | |||
+ | ::<tex> j^*= arg \min_{j\in J}F_{del}= arg \min_{j\in J}{\frac{S(A/x^j)-S(A)}{S(A)}} </tex> | ||
Признаки удаляются , пока значение F-критерия на шаге не станет больше заданного критического значения <tex> F_2 </tex>. | Признаки удаляются , пока значение F-критерия на шаге не станет больше заданного критического значения <tex> F_2 </tex>. | ||
- | Критические значения <tex> F_1 </tex> и <tex> F_2 </tex> для каждого шага определяются по таблице Фишера c заданным уровнем значимости <tex> \alpha </tex> со степенями свободы <tex> p_1 - p_2 </tex> и <tex> m - p_2 </tex>. | + | Критические значения <tex> F_1 </tex> и <tex> F_2 </tex> для каждого шага определяются по таблице Фишера c заданным [[Уровень значимости|уровнем значимости]] <tex> \alpha </tex> со степенями свободы <tex> p_1 - p_2 </tex> и <tex> m - p_2 </tex>. |
== Остановка алгоритма == | == Остановка алгоритма == | ||
Строка 59: | Строка 56: | ||
Критерий штрафует модели с большим количеством признаков. Минимизация критерия позволяет найти множество, состоящее из значимых признаков. | Критерий штрафует модели с большим количеством признаков. Минимизация критерия позволяет найти множество, состоящее из значимых признаков. | ||
== Вычислительный эксперимент == | == Вычислительный эксперимент == | ||
- | Показана работа | + | Показана работа алгоритмов в серии задач, основанных как на реальных, так и на модельных данных. |
- | === Пример | + | === Пример на модельных данных === |
- | Рассмотрим пример на модельных данных. Сравним два алгоритма: Метод наименьших углов и Шаговую регрессию. Назначена линейная модель, выборка состоит из 20 объектов и 10 признаков. По оси абсцисс показаны номера признаков, по оси ординат- параметры, полученные при использовании Метода наименьших углов. Красным цветом обозначены признаки, выбранные при помощи Шаговой регрессии. Мы видим, что Шаговой регрессией были выбраны | + | Рассмотрим пример на модельных данных. Сравним два алгоритма: Метод наименьших углов и Шаговую регрессию. Назначена линейная модель, выборка состоит из 20 объектов и 10 признаков. По оси абсцисс показаны номера признаков, по оси ординат- параметры, полученные при использовании Метода наименьших углов. Красным цветом обозначены признаки, выбранные при помощи Шаговой регрессии. Мы видим, что Шаговой регрессией были выбраны 6 признаков, которым алгоритмом Lars были присвоены наибольшие значения параметров <tex> \beta </tex>. |
- | [[Изображение: | + | [[Изображение:sample7.png|800px]] |
- | === Пример | + | === Пример на реальных данных === |
Рассмотрим пример на реальных данных : данные по кредитованию одним из немецких банков . | Рассмотрим пример на реальных данных : данные по кредитованию одним из немецких банков . | ||
- | Проведем проверку алгоритма на задаче из репозитория UCI: [http://archive.ics.uci.edu/ml/datasets/Statlog+%28German+Credit+Data%29 Statlog (German Credit Data) Data Set ]. Объектами являются анкеты людей, желавших получить кредит в банке. Изначально анкеты содержали 20 пунктов, таких как состояние | + | Проведем проверку алгоритма на задаче из репозитория UCI: [http://archive.ics.uci.edu/ml/datasets/Statlog+%28German+Credit+Data%29 Statlog (German Credit Data) Data Set]. Объектами являются анкеты людей, желавших получить кредит в банке. Изначально анкеты содержали 20 пунктов, таких как состояние банковского счета заемщика, информация о его кредитной истории, цель займа, величина займа, возраст заемщика, время с момента трудоустройства на текущее место работы и другие. Но так как некоторые из них не были числовыми, а многие алгоритмы (в том числе рассматриваемый в данной статье) работают только с числовыми признаками, то из 20 разнородных признаков было составлено 24 числовых. В выборке представлено 256 объектов. |
- | == | + | ==== Нахождение модели оптимальной структуры ==== |
- | На графике показана зависимость критерия Маллоуза от количества признаков. | + | На графике показана зависимость критерия Маллоуза от количества признаков в модели. Из графика мы находим, что минимум критерия Маллоуза достигается при количестве признаков, равном 13. Это и есть модель оптимальной структуры. |
[[Изображение:German1.png#filelinks|800px]] | [[Изображение:German1.png#filelinks|800px]] | ||
+ | |||
+ | |||
+ | ==== Сравнение работы двух алгоритмов ==== | ||
+ | |||
+ | Аналогично примеру 1, сравним два алгоритма.На графике показана зависимость параметров модели, полученные с помощью Lars, от номера признака. Красным цветом обозначены признаки, выбранные при помощи Шаговой регрессии. В отличие от первого примера на модельных данных, Шаговой регрессией были выбраны несколько признаков, которым Lars присвоил параметры, близкие к нулю. Одним из недостатков метода Шаговой регрессии является то, что важная переменная может быть никогда не включена в модель, а второстепенные признаки будут включены. | ||
+ | [[Изображение:German7.png|800px]] | ||
+ | |||
+ | |||
+ | ==== Зависимость критериев от шага алгоритмов ==== | ||
+ | |||
+ | Сравним для двух моделей значения критерия Маллоуза, [[критерий Акаике| критерия Акаике]] и критерия SSE(сумма квадратов регрессионных остатков). Сплошной линией показаны критерии для Шаговой регрессии, пунктирной- для Метода наименьших углов. | ||
+ | |||
+ | [[Изображение:German6.png|800px]] | ||
+ | |||
+ | ==== Сравнение критерия Маллоуза для обучающей и тестовой выборки (Stepwise regression) ==== | ||
+ | |||
+ | В качестве обучающей выборки были выбраны 200 объектов, в качестве тестовой- остальные 56. | ||
+ | |||
+ | [[Изображение:German3.png|800px]] | ||
+ | |||
+ | ==== Сравнение критерия Маллоуза для обучающей и тестовой выборки (Lars)==== | ||
+ | |||
+ | [[Изображение:German2.png|800px]] | ||
+ | |||
+ | == Исходный код == | ||
+ | Скачать листинги алгоритмов можно здесь [https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/Group774/Dzhamtyrova2010FeatureSelection] | ||
+ | |||
+ | == Смотри также == | ||
+ | * [[Регрессионный анализ|Pегрессионный анализ]] | ||
+ | * [[Регрессионная модель|Регрессионная модель]] | ||
+ | * [[Метод наименьших углов (пример)|Метод наименьших углов]] | ||
+ | * [[Шаговая регрессия| Шаговая регрессия]] | ||
+ | * [[Критерий Фишера]] | ||
+ | == Литература == | ||
+ | * Крымова Е.А., Стрижов В.В. Алгоритмы выбора признаков линейных регрессионных моделей из конечного и счетного множеств. | ||
+ | |||
+ | {{ЗаданиеВыполнено|Раиса Джамтырова|В.В.Стрижов|28 мая 2010|Raisa|Strijov}} | ||
+ | [[Категория:Практика и вычислительные эксперименты]] | ||
+ | [[Категория:Регрессионный анализ]] |
Текущая версия
|
Решение практических задач восстановления регрессионной зависимости требует рассмотрения большого числа порождаемых признаков. Процедура построения регрессионных моделей состоит из двух шагов. На первом шаге, на основе свободных переменных- результатов измерений, порождается набор признаков. На втором шаге производится выбор признаков. При выборе признаков выполняется настройка параметров модели, оценивается её качество. Модель с настроенными параметрами, доставляющая минимум заданному функционалу качества, называется моделью оптимальной структуры.
Среди методов отбора признаков широкое распространение получил шаговый метод, впервые предложенный в 1960 году Эфроимсоном. На каждом шаге признаки проверяются на возможность добавления признаков в модель или удаления из модели, основываясь на F-статистике. Также могут быть использованы другие способы определения значимости признака, например, критерий Акаике, Байесовский критерий, критерий Маллоуза.
В данной статье рассматриваются два метода отбора признаков: метод наименьших углов и шаговая регрессия. Эти методы похожи. Различие заключается в том, что алгоритм LARS, вместо последовательного добавления и удаления свободных переменных, на каждом шаге изменяет их веса.
Метод наименьших углов (англ. least angle regression, LARS) - алгоритм отбора признаков в задачах линейной регрессии. При большом количестве свободных переменных возникает проблема неустойчивого оценивания весов модели. LARS предлагает метод выбора такого набора свободных переменных, который имел бы наиболее значимую статистическую связь с зависимой переменной. Также LARS предлагает метод оценки весов.
Постановка задачи
Цель шаговой регрессии состоит в отборе из большого количества предикатов небольшой подгруппы переменных, которые вносят наибольший вклад в вариацию зависимой переменной.
Пусть нам задана регрессионная модель
- ,
где - свободная переменная, - зависимая переменная, - набор параметров, - случайная аддитивная величина.
Алгоритм заключается в последовательном добавлении и удалении признаков, согласно определённому критерию. Обычно используется -критерий, который имеет вид
где индекс 2 соответствует второй регрессионной модели , индекс 1 соответствует первой регрессионной модели, которая является модификацией второй модели; - соответствующие числа параметров модели; - сумма квадратов невязок, задающий критерий качества модели:
Требуется найти набор признаков, удовлетворяющий -критерию.
Описание алгоритма
Шаговая регрессия включает два основных шага: шаг Add (последовательное добавление признаков) и шаг Del (последовательное удаление признаков).
Обозначим текущий набор признаков . Начальным набором является пустой набор . К текущему набору присоединяется по одному признаку, который дoставляет максимум -критерию или
Добавляется несколько признаков, пока значение критерия на шаге не станет меньше заданного . Затем признаки удаляются по одному так, чтобы значение -критерия было минимально:
Признаки удаляются , пока значение F-критерия на шаге не станет больше заданного критического значения .
Критические значения и для каждого шага определяются по таблице Фишера c заданным уровнем значимости со степенями свободы и .
Остановка алгоритма
Останов алгоритма производится при достижении заданного минимума критерием Маллоуза :
- ,
где - среднеквадратичная ошибка, вычисленная для модели, настроенной методом наименьших квадратов на всем множестве признаков, - сложность модели.
Критерий штрафует модели с большим количеством признаков. Минимизация критерия позволяет найти множество, состоящее из значимых признаков.
Вычислительный эксперимент
Показана работа алгоритмов в серии задач, основанных как на реальных, так и на модельных данных.
Пример на модельных данных
Рассмотрим пример на модельных данных. Сравним два алгоритма: Метод наименьших углов и Шаговую регрессию. Назначена линейная модель, выборка состоит из 20 объектов и 10 признаков. По оси абсцисс показаны номера признаков, по оси ординат- параметры, полученные при использовании Метода наименьших углов. Красным цветом обозначены признаки, выбранные при помощи Шаговой регрессии. Мы видим, что Шаговой регрессией были выбраны 6 признаков, которым алгоритмом Lars были присвоены наибольшие значения параметров .
Пример на реальных данных
Рассмотрим пример на реальных данных : данные по кредитованию одним из немецких банков . Проведем проверку алгоритма на задаче из репозитория UCI: Statlog (German Credit Data) Data Set. Объектами являются анкеты людей, желавших получить кредит в банке. Изначально анкеты содержали 20 пунктов, таких как состояние банковского счета заемщика, информация о его кредитной истории, цель займа, величина займа, возраст заемщика, время с момента трудоустройства на текущее место работы и другие. Но так как некоторые из них не были числовыми, а многие алгоритмы (в том числе рассматриваемый в данной статье) работают только с числовыми признаками, то из 20 разнородных признаков было составлено 24 числовых. В выборке представлено 256 объектов.
Нахождение модели оптимальной структуры
На графике показана зависимость критерия Маллоуза от количества признаков в модели. Из графика мы находим, что минимум критерия Маллоуза достигается при количестве признаков, равном 13. Это и есть модель оптимальной структуры.
Сравнение работы двух алгоритмов
Аналогично примеру 1, сравним два алгоритма.На графике показана зависимость параметров модели, полученные с помощью Lars, от номера признака. Красным цветом обозначены признаки, выбранные при помощи Шаговой регрессии. В отличие от первого примера на модельных данных, Шаговой регрессией были выбраны несколько признаков, которым Lars присвоил параметры, близкие к нулю. Одним из недостатков метода Шаговой регрессии является то, что важная переменная может быть никогда не включена в модель, а второстепенные признаки будут включены.
Зависимость критериев от шага алгоритмов
Сравним для двух моделей значения критерия Маллоуза, критерия Акаике и критерия SSE(сумма квадратов регрессионных остатков). Сплошной линией показаны критерии для Шаговой регрессии, пунктирной- для Метода наименьших углов.
Сравнение критерия Маллоуза для обучающей и тестовой выборки (Stepwise regression)
В качестве обучающей выборки были выбраны 200 объектов, в качестве тестовой- остальные 56.
Сравнение критерия Маллоуза для обучающей и тестовой выборки (Lars)
Исходный код
Скачать листинги алгоритмов можно здесь [1]
Смотри также
Литература
- Крымова Е.А., Стрижов В.В. Алгоритмы выбора признаков линейных регрессионных моделей из конечного и счетного множеств.
Данная статья была создана в рамках учебного задания.
См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |