Алгоритмы выбора линейных регрессионных моделей (практика)

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(→Реализованные алгоритмы)
(→Случайный поиск с адаптацией (СПА) [rsa])
Строка 58: Строка 58:
=== метод группового учета аргиментов (МГУА) [gmdh] ===
=== метод группового учета аргиментов (МГУА) [gmdh] ===
=== Случайный поиск с адаптацией (СПА) [rsa] ===
=== Случайный поиск с адаптацией (СПА) [rsa] ===
 +
Алгоритм случайного поиска с адаптацией похож на генетический, но лишен операции скрещивания, зато обладает более сложной операцией мутации — признаки из хороших наборов появляются с большей вероятностью, чем из плохих.
 +
'''Вход:'''
 +
* <tex>$F$</tex> — набор признаков
 +
* <tex>$X$</tex> — обучающая выборка
 +
* <tex>$Q$</tex> — критерий качества (степень ошибки)
 +
* <tex>$d$</tex> — количество шагов осле наождения оптимума
 +
* <tex>$j_{max}$</tex> — максимальное число признаков в наборе
 +
* <tex>$T$</tex> — количество итераций
 +
* <tex>$N$</tex> — количество генерируемых наборов на каждой итерации
 +
* <tex>$h$</tex> — скорость адаптации (шаг изменения вероятностей)
 +
 +
 +
# для всех признаков равные вероятности: <tex>$p_1=\ldots=p_m=1/m$</tex>
 +
# для всех сложностей наборов: <tex>$j=1\ldots,j_{max}$</tex>
 +
## для всех итераций: <tex>$t=1,\ldots,T$</tex>
 +
### генерация набора признаков согласно вероятностям: <tex>$F_t=\{F_{t1},\ldots,F_{tN}\}$</tex>, <tex>$|F_{t1}|=\ldots=|F_{tN}|=j$</tex>
 +
### лучший набор: <tex>$F_t^{min}=\arg\min_{F_{ti}\in F_t}Q(F_{ti})$</tex>
 +
### худший набор: <tex>$F_t^{max}=\arg\max_{F_{ti}\in F_t}Q(F_{ti})$</tex>
 +
### суммарное наказание: <tex>$\Delta P=0$</tex>
 +
### по всем плохим признакам: <tex>$f_i\in F_t^{max}$</tex>
 +
#### <tex>$\Delta p_i=\min\{p_i,h\}$</tex>
 +
#### <tex>$p_i=p_i-\Delta p_i$</tex>
 +
#### <tex>$\Delta P=\Delta P+\Delta p_i$</tex>
 +
### по всем хорошим признакам: <tex>$f_i\in F_t^{min}$</tex>
 +
#### <tex>$p_i=p_i+\Delta P/j$</tex>
 +
## лучший набор из просмотренных: <tex>$F_{j^*}=\arg\min_{k\le j}Q(F_k)$</tex>
 +
## если <tex>$j\ge j^*+d$</tex>, то вернуть <tex>$F_{j^*}$</tex>
=== Гребневая регрессия [ridgeregr] ===
=== Гребневая регрессия [ridgeregr] ===

Версия 04:26, 28 января 2010

Описание библиотеки алгоритмов выбора линейных регрессионных моделей

Вспомогательные функции

Содержание

Архитектура

Соглашения об интерфейсе функций

Для унификации способов применения методов выбора модели предусмотрен формат интерфейса функции.

На вход каждый метод принимает 3 параметра:

  • features — матрица признакового описания объектов, в которой строки соответствуют объектам, а столбцы - признакам;
  • target - столбец значений целевого признака;
  • Params - структура с параметрами алгоритма; она может обладать следующими полями:
    • Common - структура, содержащая общие параметры алгоритмов:
      • maxNFeatures - максимальное допустимое количество отобранных информативных признаков;
    • ИмяМетода - для каждого метода структура с его собственными параметрами; например, для метода полного перебора esearch параметры должны быть доступны как поля структуры Params.Esearch.

На вход методам может передаваться структура параметров, содержащая не все поля (поле Params.Common и поля, соответствующие конкретным методам), а также не все их поля (например, может быть не задано Params.Common.maxNFeatures). Если необходимые алгоритму параметры не заданы, должны быть использованы некоторые значения "по умолчанию".

На выходе каждый метод возвращает описание набора информативных признаков и их весов в виде структуры с полями:

  • isInformative - логический вектор-столбец, представляющий собой маску информативных признаков (выбранным информативным признакам соответствует true, остальным - false);
  • weight - столбец с весами каждого признака; для неинформативных признаков веса должны быть нулевыми.

Шаблон шапки файла метода 

function FeaturesRating = methodName(features, target, Params)
% Description.
%
% Arguments
% Input
%   features - matrix of features, where rows are objects, and colums are feature vectors
%   target   - target feature vector
%   Params   - structure with fields 
%     Common      - common params; structure with fields
%       maxNFeatures - maximum features number to select
%     MethodName  - structure with params for particular method
% Output
%   FeaturesRating - structure with rating for all features; has fields
%     isInformative - logical column of marks is particular feature informative (true) or not (false)
%     weight        - weight of particular feature
%
% Example
% TODO
%
% See also
% TODO
% 
% Revisions
% TODO

TODO Example

Реализованные алгоритмы

Полный перебор [esearch]

Лассо Тибширани [lasso]

Least Angle Regression (LARS) [lars]

Генетический алгоритм [genetic]

метод группового учета аргиментов (МГУА) [gmdh]

Случайный поиск с адаптацией (СПА) [rsa]

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

Вход:

  • $F$ — набор признаков
  • $X$ — обучающая выборка
  • $Q$ — критерий качества (степень ошибки)
  • $d$ — количество шагов осле наождения оптимума
  • $j_{max}$ — максимальное число признаков в наборе
  • $T$ — количество итераций
  • $N$ — количество генерируемых наборов на каждой итерации
  • $h$ — скорость адаптации (шаг изменения вероятностей)


  1. для всех признаков равные вероятности: $p_1=\ldots=p_m=1/m$
  2. для всех сложностей наборов: $j=1\ldots,j_{max}$
    1. для всех итераций: $t=1,\ldots,T$
      1. генерация набора признаков согласно вероятностям: $F_t=\{F_{t1},\ldots,F_{tN}\}$, $|F_{t1}|=\ldots=|F_{tN}|=j$
      2. лучший набор: $F_t^{min}=\arg\min_{F_{ti}\in F_t}Q(F_{ti})$
      3. худший набор: $F_t^{max}=\arg\max_{F_{ti}\in F_t}Q(F_{ti})$
      4. суммарное наказание: $\Delta P=0$
      5. по всем плохим признакам: $f_i\in F_t^{max}$
        1. $\Delta p_i=\min\{p_i,h\}$
        2. $p_i=p_i-\Delta p_i$
        3. $\Delta P=\Delta P+\Delta p_i$
      6. по всем хорошим признакам: $f_i\in F_t^{min}$
        1. $p_i=p_i+\Delta P/j$
    2. лучший набор из просмотренных: $F_{j^*}=\arg\min_{k\le j}Q(F_k)$
    3. если $j\ge j^*+d$, то вернуть $F_{j^*}$

Гребневая регрессия [ridgeregr]

Поиск самой длинной проекции вектора ответов на биссекторы векторов признаков [maxkselect]

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%B0_%D0%BB%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D1%8B%D1%85_%D1%80%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D1%85_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B5%D0%B9_%28%D0%BF%D1%80%D0%B0%D0%BA%D1%82%D0%B8%D0%BA%D0%B0%29»
Личные инструменты