Методы построения математических функций. Методы и средства анализа данных

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

Корреляционный анализ

Корреляционный анализ - это анализ переменных на предмет того, существует ли между ними какая-либо достаточно сильная зависимость. Нам требуется установить, влияют ли независимые переменные на зависимую - или это случайный набор данных. Следует отметить, тем не менее, что иногда даже корреляция не определяет причинности, а только то, что они изменяются по сходному закону. В общем, больше нам и не надо.

Очевидно, что, если мы решим использовать математические функции, то тогда зависимая переменная y будет вычисляться через какую-то функцию F (мы будем называеть ее функцией регрессии) от атрибутов

X = < X 1,... X i,... X n >

. Однако очевидно также, что будет какая-то погрешность

θ

, (иначе все слишком хорошо, у нас просто прямая зависимость - впрочем, такое тоже возможно при

θ = 0

На интуитивном уровне можно сказать, что независимые переменные проецируются с некоторым разбросом (погрешностью) на плоскость Oy. (Рисунок). Тогда (опустив некоторые сложные математические выкладки) можно сказать, что:

Это означает, что полная вариация зависимой переменной складывается из вариации функции регрессии F(X) () и вариации остаточной случайной компоненты.

В корреляционном анализе нас интересует, насколько изменчивость зависимой переменной обуславливается изменчивостью независимых переменных (функции от них). То есть:

I - это индекс корреляции, $0 \le I \le 1$ , основной показатель корреляции переменных. В общем случае формулы для индекса корреляции нет, однако иногда его можно оценить.

Для двух переменных

В том случае, если рассматривается двумерная нормальная (х и у распределены нормально) система (x,y), то тогда:

где r - коэффициент корреляции, еще один из достаточно сильных показателей взаимосвязи переменных. Положительный - они прямо пропорциональны, отрицательный - обратно. Однако для любого отклонения от двумерности и нормальности он не является прямо определяющим корреляцию.

В том случае, если есть отклонение от нормальности, то тогда имеет смысл попробовать разбить y на интервалы (сгруппировать по оси объясняющей переменной) и посчитать среди них среднее:

$\overline{y_i}=\frac{\sum_{k=1}^{m_i} y_{i k}}{m_i}$ , где k - число интервалов группировки,

m i

- число точек в i-м интервале,

y i k

- k-ая точка в i-м интервале.

$s_{\overline{y}(x)}^2=\frac{1}{n}\sum_{i=1}^k m_i(\overline{y}_i - \overline{y})^2, \overline{y}=\frac{\sum_{i=1}^k m_i \overline{y}_i}{n}$

$\widehat{\rho}_{y,x}$ - корреляционное отношение, оно похоже по свойствам на корреляционный коэффициент, но несимметрично: $\widehat{\rho}_{y,x} \ne \widehat{\rho}_{x,y}$ и не говорит о характере связи.

В том случае, если сгруппировать невозможно, то следует сначала провести регрессионный анализ и выявить коэффициенты функции регрессии

w 0,... w p

, а затем считать

$I_{y,X}^2=1- \frac{\frac{1}{n-p-1} \sum_{i=1}^{n} (y_i - F(X_i,w_0...w_p))}{\frac{1}{n} \sum_{i=1}^n (y_i - \overline{y})}$

Для произвольного числа переменных

Для произdольного числа переменных

I y, x

индекс корреляции называется коэффициентом корреляции

R y, X

. Для линейного случая считается через попарные коэффициенты корреляции:

$R_{y,X}^2=1- \frac{det (r_{ij})_{ij..pp}}{M_{0}^0}$ , где $M_{0}^0$ - минор (определитель матрицы, получающейся из исходной матрицы

r i j

вычеркиванием первого (нулевого) столбца и строки)

Этот коэффициент всегда больше любого коэффициента попарной корреляции.

Для нелинейного все опять же следует попробовать свести к интервалам, которые линеаризуются, или рассматривать регрессию.

Регрессионный анализ

Регрессионный анализ — метод моделирования измеряемых данных и исследования их свойств. Данные состоят из пар значений зависимой переменной (переменной отклика) и независимой переменной (объясняющей переменной). Регрессионная модель есть функция независимой переменной и параметров с добавленной случайной переменной. Параметры модели настраиваются таким образом, что модель наилучшим образом приближает данные. Критерием качества приближения (целевой функцией) обычно является среднеквадратичная ошибка: сумма квадратов разности значений модели и зависимой переменной для всех значений независимой переменной в качестве аргумента.
При построении математической функции классификации или регрессии основная задача сводится к выбору наилучшей функции из всего множества функций. Может существовать множество функций, одинаково классифицирующих одну и ту же обучающую выборку.
В результате задачу построения функции классификации и регрессии можно формально описать как задачу выбора функции с минимальной степенью ошибки: $min R(f) = \frac{1}{m}\sum_{i=1}^mc(y_i,f(x_i))$
Где:

В случае бинарной классификации (принадлежности объекта к одному из двух классов) простейшая функция потерь принимает значение 1 в случае неправильного предсказания и 0 в противном случае.
Но здесь не учитывается ни тип ошибки, ни её величина.
Для оценки качества классификации целесообразно использовать разность f(x) - y. Разница между предсказанным и известным (по данным обучающей выборки) значением зависимой переменной.

Метод наименьших квадратов

В случае когда регрессионная функция линейна, множество всех возможных функций разбиения (F) можно представить в виде: $y = w_0 + w_{1}x_1 + w_{2}x_2 + ... + w_{n}x_n = w_0 + \sum w_{j}x_j$ ,
где

w 0, w 1,..., w n

- коэффициенты при независимых переменных.
Задача заключается в отыскании таких коэффициентов w, чтобы разница между предсказанным и известным значением зависимой переменной была минимальна. Также задачу можно сформулировать как минимизация суммы квадратов разностей рассчитанных и известных значений зависимой переменной.
$min R(f) = min \frac{1}{m} \sum_{i=1}^m(y_i - \sum_{j=1}^n w_{i}f_{i}(x_i))^2$

Нелинейные методы

Нелинейные модели лучше классифицируют объекты, однако их построение более сложно. Задача также сводится к минимизации выражения
$min R(f) = min \frac{1}{m} \sum_{i=1}^m(y_i - \sum_{j=1}^n w_{i}f_{i}(x_i))^2$ .
При этом множество F содержит нелинейные функции.
В простейшем случае построение таких функций сводится к построению линейных моделей. Для этого исходное пространство объектов преобразуется к новому. В новом пространстве строится линейная функция, которая в исходном пространстве является нелинейной. Для использования построенной функции выполняется обратное преобразование в исходное пространство. Если объекты их обучающей выборки отобразить графически (откладывая по одной оси значение одной из независимых переменных, а по другой оси значение зависимой переменной), то может получиться картина, когда объекты одного класса будут сгруппированы в центре, а объекты другого рассеяны вокруг этого центра. В этом случае применение линейных методов не поможет. Выходом из этой ситуации является перевод объектов в другое пространство. Можно возвести координату каждой точки в квадрат, тогда распределение может получиться таким, что станет возможным применение линейных методов.
Описанный подход имеет один существенный недостаток. Процесс преобразования достаточно сложен с точки зрения вычислений, причём вычислительная сложность растёт с увеличением числа данных. Если учесть, что преобразование выполняется два раза (прямое и обратное), то такая зависимость не является линейной. В связи с этим построение нелинейных моделей с таким подходом будет неэффективным. Альтернативой ему может служить метод Support Vector Machines (SVM), не выполняющий отдельных преобразований всех объектов, но учитывающий это в рассчётах.

Метод опорных векторов

Основная идея метода опорных векторов – перевод исходных векторов в пространство более высокой размерности и поиск максимальной разделяющей гиперплоскости в этом пространстве.

Каждый объект данных представлен, как вектор (точка в p-мерном пространстве (последовательность p чисел)). Рассмотрим случай бинарной классификации - когда каждая из этих точек принадлежит только одному их двух классов.

Нас интересует, можем ли мы разделить эти точки какой-либо прямой так, чтобы с одной стороны были точки одного класса, а с другой - другого. Такая прямая называется гиперплоскостью размерностью "p−1". Она описывается уравнением $\overrightarrow{w} \cdot \overrightarrow{x} - b=0,$ где $\overrightarrow{w} \cdot \overrightarrow{x}$ - скалярное произведение векторов.

Тогда для того, чтобы разделить точки прямой, надо, чтобы выполнялось:

$\overrightarrow{w} \cdot \overrightarrow{x_i} - b > 0$ ->

y i = 1

(принадлежит к одному классу)

$\overrightarrow{w} \cdot \overrightarrow{x_i} - b < 0$ ->

y i = - 1

(принадлежит к другому классу)

Для улучшения классификации попробуем найти такую разделяющую гиперплоскость, чтобы она максимально отстояла от точек каждого класса (фактически, разделим не прямой, а полосой).

$\overrightarrow{w} \cdot \overrightarrow{x_i} - b \ge 0 + \epsilon$ ->

y i = 1

(принадлежит к одному классу)

$\overrightarrow{w} \cdot \overrightarrow{x_i} - b \le 0 - \epsilon$ ->

y i = - 1

для некоторого

ε > 0

Домножим эти уравнения на константу так, чтобы для граничных точек - ближайших к гиперплоскости - выполнялось:

Это можно сделать, так как для оптимальной разделяющей гиперплоскости все граничные точки лежат на одинаковом от нее расстоянии. Разделим тогда неравенства на

ε

и выберем

ε = 1

. Тогда:

$\overrightarrow{w} \cdot \overrightarrow{x_i} - b \ge 1$ , если

y i = 1

$\overrightarrow{w} \cdot \overrightarrow{x_i} - b \le 1$ , если

y i = - 1

Ширина разделительной полосы тогда равна $\frac{2}{\| w \|}$ . Нам нужно, чтобы ширина полосы была как можно большей ( $\|w \|^2 \to min$ )(чтобы классификация была точнее) и при этом $y_i(\overrightarrow{w} \cdot \overrightarrow{x_i} - b) \ge 1$ (так как $y_i = \pm 1$ ). Это задача квадратичной оптимизации.

Это в том случае, если классы линейно разделимы (разделимы гиперплоскостью). В том случае, если есть точки, которые лежат по "неправильные" стороны гиперплоскости, то мы считаем эти точки ошибками. Но их надо учитывать:

$y_i(\overrightarrow{w} \cdot \overrightarrow{x_i} - b) \ge 1 - \xi_i$ ,

ξ i

- ошибка

x i

, если

ξ i = 0

- ошибки нет, если

0 < ξ i < 1

, то объект внутри разделительной полосы, но классифицируется правильно, если

ξ i > 1

- это ошибка.

Тогда нам надо минимизировать сумму $\|w \|^2 + C \sum_i \xi_i \to min$ , C - параметр, позволяющий регулировать, что нам важнее - отсутствие ошибок или выразительность результата (ширина разделительной полосы), мы его выбираем сами .

Как известно, чтобы найти минимум, надо исследовать производную. Однако у нас заданы еще и границы, в которых этот минимум искать! Это решается при помощи метода Лагранжа: Лагранж доказал (для уравнений в общем и неравенств в частности), что в той точке, где у функции F(x) условный (ограниченный условиями) минимум, в той же точке у функции

(для фиксированного набора

λ i, G i

- условия ограничений) тоже минимум, но уже безусловный, по всем x. При этом либо

λ i = 0

и соответственно ограничение

G i

не активно, либо $\lambda_i \ne 0$ , тогда неравенство

G i

превращается в уравнение.

Тогда можно нашу задачу ( минимизировать $\frac{1}{2}\|w \|^2 + C \sum_i \xi_i$ при условиях $\xi_i \ge 0$ , $y_i(\overrightarrow{w} \cdot \overrightarrow{x_i} - b) \ge 1 - \xi_i$ ) сформулировать при помощи метода лагранжа следующим образом:

Необходимо найти минимум по w, b и

ξ i

и максимум по

λ i

функции $\frac{1}{2} w \cdot w + C \sum_i \xi_i - \sum_i \lambda_i ( \xi_i + y_i (w \cdot x_i - b - 1)$ при условиях $\xi_i \ge 0 , \lambda_i \ge 0$ .

Возьмем производную лагранжианы по w, приравняем ее к нулю и из полученного выражения выразим w:

Следовательно, вектор w - линейная комбинация учебных векторов

x i

, причем только таких, для которых $\lambda_i \ne 0$ . Именно эти вектора называются опорными и дали название метода.

Подставим w в лагранжиану и получим новую (двойственную) задачу:

$\sum_i \lambda_i - \frac{1}{2} \sum_{i,j} \lambda_i \lambda_j y_i y_j (x_i \cdot x_j) \to max$ при

Это финальная задача, которую нам надо решить. Обратите внимание, что в итоге все свелось к скалярному произведению двух векторов -

x i

x j

. Это произведение называется Ядром.

Эта задача решается методом последовательных оптимизации (благодаря тому, что коэффициенты при

λ i λ j

положительны -> функция выпуклая -> локальный максимум яявляется глобальным):

Ядра

Это все хорошо, если набор хотя бы более-менее линеен (когда ошибка достаточно мала). В том случае, если набор не линеен, тогда ошибка велика. В 1992 году Бернхард Босер, Изабель Гуйон и Вапник предложили способ создания нелинейного классификатора, в основе которого лежит переход от скалярных произведений к произвольным ядрам, так называемый kernel trick , позволяющий строить нелинейные разделители.

Результирующий алгоритм крайне похож на алгоритм линейной классификации, с той лишь разницей, что каждое скалярное произведение в приведенных выше формулах заменяется нелинейной функцией ядра (скалярным произведением в пространстве с большей размерностью). В этом пространстве уже может существовать оптимальная разделяющая гиперплоскость. Так как размерность получаемого пространства может быть больше размерности исходного, то преобразование, сопоставляющее скалярные произведения, будет нелинейным, а значит функция, соответсвующая в исходном пространстве оптимальной разделяющей гиперплоскости будет также нелинейной.

Стоит отметить, что если исходное пространство имеет достаточно высокую размерность, то можно надеяться, что в нём выборка окажется линейно разделимой.

Знаете ли Вы, что такое "усталость света"?
Усталость света, анг. tired light - это явление потери энергии квантом электромагнитного излучения при прохождении космических расстояний, то же самое, что эффект красного смещения спектра далеких галактик, обнаруженный Эдвином Хабблом в 1926 г.
На самом деле кванты света, проходя миллиарды световых лет, отдают свою энергию эфиру, "пустому пространству", так как он является реальной физической средой - носителем электромагнитных колебаний с ненулевой вязкостью или трением, и, следовательно, колебания в этой среде должны затухать с расходом энергии на трение. Трение это чрезвычайно мало, а потому эффект "старения света" или "красное смещение Хаббла" обнаруживается лишь на межгалактических расстояниях.
Таким образом, свет далеких звезд не суммируется со светом ближних. Далекие звезды становятся красными, а совсем далекие уходят в радиодиапазон и перестают быть видимыми вообще. Это реально наблюдаемое явление астрономии глубокого космоса. Подробнее читайте в FAQ по эфирной физике.

F(x) −	∑	λ_iG_i
	i

F(x) −	∑	λ_iG_i
	i

w =	∑	λ_iy_ix_i
	i

∑	λ_iy_i = 0
i