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

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

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

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

Очевидно, что, если мы решим использовать математические функции, то тогда зависимая переменная 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 , позволяющий строить нелинейные разделители.

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

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

Знаете ли Вы, что cогласно релятивистской мифологии "гравитационное линзирование - это физическое явление, связанное с отклонением лучей света в поле тяжести. Гравитационные линзы обясняют образование кратных изображений одного и того же астрономического объекта (квазаров, галактик), когда на луч зрения от источника к наблюдателю попадает другая галактика или скопление галактик (собственно линза). В некоторых изображениях происходит усиление яркости оригинального источника." (Релятивисты приводят примеры искажения изображений галактик в качестве подтверждения ОТО - воздействия гравитации на свет)
При этом они забывают, что поле действия эффекта ОТО - это малые углы вблизи поверхности звезд, где на самом деле этот эффект не наблюдается (затменные двойные). Разница в шкалах явлений реального искажения изображений галактик и мифического отклонения вблизи звезд - 10¹¹ раз. Приведу аналогию. Можно говорить о воздействии поверхностного натяжения на форму капель, но нельзя серьезно говорить о силе поверхностного натяжения, как о причине океанских приливов.
Эфирная физика находит ответ на наблюдаемое явление искажения изображений галактик. Это результат нагрева эфира вблизи галактик, изменения его плотности и, следовательно, изменения скорости света на галактических расстояниях вследствие преломления света в эфире различной плотности. Подтверждением термической природы искажения изображений галактик является прямая связь этого искажения с радиоизлучением пространства, то есть эфира в этом месте, смещение спектра CMB (космическое микроволновое излучение) в данном направлении в высокочастотную область. Подробнее читайте в FAQ по эфирной физике.

F(x) −	∑	λ_iG_i
	i

F(x) −	∑	λ_iG_i
	i

w =	∑	λ_iy_ix_i
	i

∑	λ_iy_i = 0
i