Метрики "важности" признаков (Importances)

Метрика важности (по английски importances, общепринятого русского термина не знаю, перевожу в лоб, звучит глупо, кто знает -- исправьте) признаков -- это величина показывающая как отдельно взятый признак влияет на распределение целевой переменной. Они используются для:

• отбора признаков
• взвешивания признаков (для метрических методов и линейных методов с регуляризацией)
• for adapting feature sampling probability in random forest, extra random trees. (я вроде понимаю про что это, но не могу перевести, кто могет, дерзайте).

Везде далее метрики рассматриваются как функция от двух переменных: признака ($f$ -- столбец матрицы объект-признак) и целевой переменной ($y$ -- столбец ответов для каждого объекта), таким образом $I(f) = \rho(f, y)$, где $\rho$ зависит от конкретного метода подсчета метрики.

Корреляция

$\rho (f,y)={\frac {(\sum _{i=1}^{N}f_{i}-{\overline {f}})(y_{i}-{\overline {y}})}{(\sum _{i=1}^{N}f_{i}-{\overline {f}})^{2}(\sum _{i=1}^{N}y_{i}-{\overline {y}})^{2}}}$, обычная корреляция, ничего нового. Следует учитывать что корреляция -- линейная и не работает на сложных, нелинейных зависимостях (простой пример: $\rho(sin(x), cos(x)) = 0$, только если выше приведена дискретная корреляция, для реальной выборки, про строгое равенство нулю можно говорить только при вычислении корреляции на математической модели где $x$ принимает все значения на $[0, 2\pi)$).

Условная энтропия и расстояние Кульбака-Лейблера

Напоминаем что энтропия случайной величины $y$ есть $H(y) = -\mathbb{E} ~ln(p(y)) = -\sum _{y} p(y)ln(p(y))$.

Аналогично вводится понятие условной энтропии т.е. энтропии величины y при условии что известен f:

$H(y|f) = -\mathbb{E}_f\left\lbrace\mathbb{E}[ ln(p(y|f)) |f]\right\rbrace = -\sum _{f} p(f) \sum _y p(y|f) ln(p(y|f))$.

Для распределений двух величин P(x) и Q(x) определяется расстояние Кульбака-Лейблера:

$KL(P||Q) = \sum _x P(x) ln \left( \frac{P(x)}{Q(x)} \right)$,

более подробно про него в отдельной статье (ссылки нет но когда нибудь будет).

Через условную энтропию и расстояние Кульбака-Лейблера определяется понятие взаимной информации.

Взаимная информация

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

$MI(x, y) = \sum_{x, y} p(x, y) ln(\frac{p(x, y)}{p(x)p(y)}) = KL(p(x, y)||p(x)p(y)) = H(y) - H(y|x)$.

Если расстояние Кульбака-Лейблера показывает насколько близки друг к другу два распределения, то взаимная информация это расстояние от $p(x, y)$ до $p(x)p(y)$, как известно чем ближе одно распределение к другому, тем более независимы случайные величины $x$ и $y$(в частности если распределения совпадают, то величины независимы). При $\rho(f, y) = MI(f, y) = H(y) - H(y|f) = const(f) - H(y|f)$. Интуиция в том что лучший признак минимизирует условную энтропию (т.е. он дает больше информации о значении случайной величины $y$). В принципе это почти то же самое что и $\rho(f, y) = -H(y|f)$.

Relief критерий

Рассмотрим объекты в метрическом пространстве (как правило с евклидовой метрикой). Для каждого объекта выборки $x_n$ находим $K$ ближайших соседей совпадающего класса (обозначим $x_{s(n, i)}, i=\overline{1,K}$) и K ближайших соседей другого класса (обозначим $x_{d(n, i)}, i=\overline{1,K}$). После чего для каждого признака считаем важность как $I(f_i) = \frac{1}{N} \sum _{n=1}^N \sum_{k = 1} ^K \frac{|x_n^i - x_{d(n, k)}^i|}{|x_n^i - x_{s(n, k)}^i|}$. $K$ -- является параметром метода и подбирается по ситуации.