Линейная регрессия — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 36 промежуточных версий 9 участников)
Строка 5: Строка 5:
 
==== Дано ====
 
==== Дано ====
  
* <tex> f_1(x), \dots ,f_n(x) </tex> - числовые признаки
+
* <tex> f_1(x), \dots ,f_n(x) </tex> числовые признаки;
* модель многомерной линейной регрессии:
+
* модель многомерной линейной регрессии: <br> <tex> f(x,\alpha) = \sum\limits_{j=1}^n \alpha_j f_j(x) </tex>, <br> где <tex> a \in R^n </tex>;
<center> <tex> f(x,\alpha) = \sum\limits_{j=1}^n \alpha_j f_j(x) </tex>, </center>
+
* обучающая выборка: множество из пар <tex>(x_i, y_i)_{i=1 \dots n}</tex>;
где <tex> a \in R^n </tex>
+
* <tex> x_i </tex> объекты из множества <tex> X = R^n </tex>;
* обучающая выборка: множество из пар <tex>(x_i, y_i)_{i=1 \dots n}</tex>
+
* <tex> y_i </tex> объекты из множества <tex> X = R </tex>.
* <tex> x_i </tex> - объекты из множества <tex> X = R^n </tex>
+
 
* <tex> y_i </tex> - объекты из множества <tex> X = R </tex>
+
==== Матричные обозначения ====
 +
 
 +
Перейдем к матричным обозначениям:
 +
 
 +
<tex>
 +
\underset{l \times n}{F} =
 +
\begin{pmatrix}
 +
  f_1(x_1) & \dots & f_n(x_1) \\
 +
  \dots & \dots & \dots \\
 +
  f_1(x_l) & \dots & f_n(x_l)
 +
\end{pmatrix}
 +
,
 +
 
 +
\underset{l \times 1}{y} =
 +
\begin{pmatrix}
 +
  y_1 \\
 +
  \dots \\
 +
  y_l
 +
\end{pmatrix},
 +
 
 +
\underset{n \times 1}{\alpha} =
 +
\begin{pmatrix}
 +
  \alpha_1 \\
 +
  \dots \\
 +
  \alpha_n
 +
\end{pmatrix}
 +
 
 +
</tex>,
 +
 
 +
где
 +
* <tex> F </tex> — матрица объектов-признаков, где строки соответствуют объектам а столбцы — признакам;
 +
* <tex> y </tex> — вектор ответов, или целевой вектор;
 +
* <tex> \alpha </tex> — вектор коэффициентов.
 +
 
 +
==== Постановка задачи ====
 +
 
 +
В этих трех векторно-матричных обозначениях очень удобно расписать постановку задачи наименьших квадратов:
 +
 
 +
<tex> Q(\alpha, X^l) = \sum\limits_{i=1}^n (f(x_i, \alpha) - y_i)^2 = || F\alpha - y ||^2 \rightarrow \underset{\alpha}{min} </tex>.
 +
 
 +
Необходимо найти вектор <tex> \alpha </tex> при известной матрице <tex> F </tex> и известном вектор-столбце <tex> y </tex>.
 +
 
 +
== Решение ==
 +
 
 +
=== Нормальная система уравнений ===
 +
 
 +
Запишем необходимые условия минимума в матричном виде:
 +
 
 +
<tex> \frac{\partial Q }{\partial \alpha } (\alpha) = 2F^T (F\alpha - y) = 0 </tex>.
 +
 
 +
Отсюда следует нормальная система задачи МНК:
 +
 
 +
<tex> F^T F \alpha = F^T y </tex>,
 +
 
 +
где <tex> F^T F — n \times n </tex> матрица.
 +
 
 +
Мы получили систему уравнений, откуда можем выразить искомый вектор <tex> \alpha </tex>.
 +
 
 +
==== Решение системы ====
 +
<tex> \alpha^* = (F^T F)^{-1} F^T y = F^+ y </tex>, <br> где <tex> F^+ </tex> — псевдо-обратная матрица.
 +
 
 +
Значение функционала: <tex> Q(\alpha^*) = ||P_F y - y||^2 </tex>, <br> где <tex> P_F = F F^+ = F (F^T F)^{-1} F^T </tex> — ''проекционная матрица''.
 +
 
 +
==== Проблемы ====
 +
 
 +
В случае мультиколлинеарности (столбцы матрицы <tex> F </tex> линейно-зависимы) нам не удастся найти обратную матрицу к <tex> F^T F </tex> (она будет вырождена).
 +
 
 +
Если же столбцы матрицы <tex> F </tex> почти линейно-зависимы, то у нас возникнет масса вычислительных проблем с обращением этой матрицы.
 +
 
 +
=== Решение МНК через сингулярное разложение ===
 +
 
 +
Воспользуемся понятием [[ Сингулярное разложение | сингулярного разложения ]], которое позволяет произвольную прямоугольную матрицу представить в виде произведения трех матриц:
 +
 
 +
<tex> F = V D U^T </tex>.
 +
 
 +
Найдем псевдо-обратную матрицу: <br> <tex> F^+ = (U D V^T V D U^T)^{-1} U D V^T = U D^{-1} V^T = \sum\limits_{j=1}^n \frac{ 1 }{ \sqrt{ \lambda_j } } u_j v_j^T </tex>.
 +
 
 +
Теперь, зная псевдо-обратную матрицу, найдем решение задачи наименьших квадратов: <br> <tex> \alpha^* = F^+ y = U D^{-1} V^T y = \sum\limits_{j=1}^n \frac{ 1 }{ \sqrt{ \lambda_j } } u_j (v_j^T y) </tex>.
 +
 
 +
Найдем вектор, которым наша линейная модель аппроксимирует целевой вектор <tex> y </tex>: <br> <tex> F \alpha^* = P_F y = (V D U^T) U D^{-1} V^T y = V V^T y = \sum\limits_{j=1}^n v_j (v_j^T y) </tex>.
 +
 
 +
Квадрат нормы вектора коэффициентов: <br> <tex> || \alpha^* ||^2 = ||D^{-1} V^T y||^2 = \sum\limits_{j=1}^n \frac{ 1 }{ \lambda_j } (v_j^T y)^2 </tex>.
 +
 
 +
В 3-х из 4-х формул сингулярные числа оказались в знаменателе. Если имеются сингулярные числа приближающиеся к 0, то мы получаем проблему мультиколлинеарности. Близкие к 0 собственные значения или сингулярные числа — показатель того, что среди признаков есть почти линейно-зависимый.
 +
 
 +
== Проблема мультиколлинеарности и переобучения ==
 +
 
 +
Если имеются сингулярные числа близкие к 0, то:
 +
 
 +
* матрица <tex> \sum = F^T F </tex> плохо обусловлена;
 +
* решение становится неустойчивым и неинтерпретируемым, слишком большие коэффициенты <tex> || \alpha_j || </tex> разных знаков;
 +
* возникает переобучение: <br> на обучении <tex> Q( \alpha^*, X^l ) = ||F \alpha^* - y||^2 </tex> мало; <br> на контроле <tex> Q( \alpha^*, X^k ) = ||F' \alpha^* - y'||^2 </tex> велико.
 +
 
 +
Стратегии устранения мультиколлинеарности и переобучения:
 +
 
 +
* отбор признаков, то есть выкидываем те признаки, которые могут оказаться линейно-зависимыми: <br> <tex> f_1, \dots, f_n \rightarrow f_{j_1} \dots, f_{j_m}, m \leq n </tex>;
 +
* регуляризация (накладываем дополнительные ограничения на вектор коэффициентов): <br> <tex> || \alpha || \rightarrow min </tex>;
 +
* преобразование признаков, чтобы в новом признаковом пространстве признаков оказалось меньше, но они хорошо восстанавливали бы исходные: <br> <tex> f_1, \dots, f_n \rightarrow g_1 \dots, g_m, m \ll n </tex>.
 +
 
 +
==Примеры кода==
 +
=== Пример кода для Scikit-learn ===
 +
 
 +
'''import''' matplotlib.pyplot '''as''' plt
 +
'''from''' sklearn '''import''' datasets, linear_model
 +
 +
<font color = green># generate dataset</font>
 +
X, y = datasets.make_regression(n_samples=1_000, n_features=1, noise=8, shuffle=True)
 +
 +
<font color = green># test and train data sizes</font>
 +
train_size = 700
 +
test_size = 300
 +
 +
<font color = green># split the data into training/testing sets</font>
 +
X_train = X[:-train_size]
 +
X_test = X[-test_size:]
 +
 +
<font color = green># split the targets into training/testing sets</font>
 +
y_train = y[:-train_size]
 +
y_test = y[-test_size:]
 +
 +
<font color = green># create linear regression object</font>
 +
regr = linear_model.LinearRegression()
 +
 +
<font color = green># train the model using the training sets</font>
 +
regr.fit(X_train, y_train)
 +
 +
<font color = green># make predictions using the testing set</font>
 +
y_pred = regr.predict(X_test)
 +
 +
<font color = green># plot outputs</font>
 +
plt.scatter(X_test, y_test, color='red', s=5)
 +
plt.plot(X_test, y_pred, color='blue', linewidth=2)
 +
 
 +
plt.xticks(())
 +
plt.yticks(())
 +
 +
plt.show()
 +
 
 +
Возможный результат исполнения программы:
 +
 
 +
[[Файл: Linear_regression_example.png]]
 +
 
 +
===Пример на языке Java===
 +
Пример линейной регресии с применением <code>weka.classifiers.functions.LinearRegression</code><ref>[http://weka.sourceforge.net/doc.dev/weka/classifiers/functions/LinearRegression.html/ Weka, Linear Regression]</ref>
 +
 
 +
<code>Maven</code> зависимомсть:
 +
  <dependency>
 +
    <groupId>nz.ac.waikato.cms.weka</groupId>
 +
    <artifactId>weka-stable</artifactId>
 +
    <version>3.8.0</version>
 +
  </dependency>
 +
 
 +
  '''import''' weka.classifiers.functions.LinearRegression;
 +
  '''import''' weka.core.Instance;
 +
  '''import''' weka.core.Instances;
 +
 
 +
  <font color="green">//Load Data set</font>
 +
  '''var''' data = new Instances(new BufferedReader(new FileReader("dataset/house.arff")));
 +
  data.setClassIndex(data.numAttributes() - 1);
 +
  <font color="green">//Build model</font>
 +
  '''var''' model = new LinearRegression();
 +
  '''try''' { model.buildClassifier(data); }
 +
  '''catch''' (Exception e) { e.printStackTrace(); }
 +
  <font color="green">//output model</font>
 +
  System.out.printf("model parameters: %s%n", model);
 +
  <font color="green">// Now Predicting the cost</font>
 +
  '''var''' myHouse = data.lastInstance();
 +
  '''var''' price  = model.classifyInstance(myHouse);
 +
  System.out.printf("predicted price = %s%n", price)
 +
 
 +
===Пример на языке R===
 +
{{Main|Примеры кода на R}}
 +
 
 +
<font color="gray"># reading data</font>
 +
data <- read.csv(<font color="green">"input.csv"</font>, <font color="#660099">sep</font> = <font color="green">','</font>, <font color="#660099">header</font> = FALSE)
 +
 +
<font color="gray"># evaluating linear regression model</font>
 +
model <- lm(data$<strong><font color="#660E7A">x</font></strong> ~ data$<strong><font color="#660E7A">y</font></strong>)
 +
 +
<font color="gray"># getting summary</font>
 +
print(summary(model))
 +
 +
<font color="gray"># visualizing data</font>
 +
plot(data$<strong><font color="#660E7A">y</font></strong>, data$<strong><font color="#660E7A">x</font></strong>)
 +
lines(data$<strong><font color="#660E7A">y</font></strong>, predict(fit), <font color="#660099">col</font> = <font color="green">'red'</font>)
 +
 
 +
==Применение==
 +
 
 +
Перечислим несколько примеров реального применения линейной регрессии:
 +
 
 +
* для предсказания скидки на продукты на основе поведения покупателей в прошлом;
 +
* экономисты использую линейную регрессия для предсказания экономического роста страны или региона;
 +
* застройщики при помощи данного метода могут предсказать, сколько домов он продаст в ближайшие месяцы и по какой цене;
 +
* цены на нефть могут быть предсказаны с использованием линейной регрессии.
 +
 
 +
==См. также==
 +
 
 +
* [[Общие понятия]]
 +
* [[Вариации регрессии]]
 +
* [[Логистическая регрессия]]
 +
* [[Обзор библиотек для машинного обучения на Python]]
 +
* [[Переобучение]]
 +
 
 +
==Источники информации==
 +
* [http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%B0%D1%8F_%D0%BB%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F machinelearning.ru {{---}} Многомерная линейная регрессия]
 +
* [http://www.machinelearning.ru/wiki/index.php?title=%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29 machinelearning.ru {{---}} Линейная регрессия (пример)]
 +
* [https://www.coursera.org/learn/vvedenie-mashinnoe-obuchenie/home/info Coursera {{---}} "Введение в машинное обучение", Неделя 4, ]
 +
* [http://www.ccas.ru/voron/download/Regression.pdf Лекции по алгоритмам восстановления регрессии К. В. Воронцов]
 +
* [https://scikit-learn.org/stable/auto_examples/linear_model/plot_ols.html#sphx-glr-auto-examples-linear-model-plot-ols-py Scikit-Learn {{---}} Linear Regression Example]
 +
* [https://www.quora.com/What-are-some-real-world-applications-of-simple-linear-regression What are some real-world applications of "simple" linear regression?]
 +
 
 +
[[Категория: Машинное обучение]]
 +
[[Категория: Регрессия]]

Текущая версия на 19:24, 4 сентября 2022

Линейная регрессия (англ. linear regression) — метод восстановления зависимости одной (объясняемой, зависимой) переменной [math] y [/math] от другой или нескольких других переменных (факторов, регрессоров, независимых переменных) [math] x [/math] с линейной функцией зависимости. Данный метод позволяет предсказывать значения зависимой переменной [math] y [/math] по значениям независимой переменной [math] x [/math].

Задача

Дано

  • [math] f_1(x), \dots ,f_n(x) [/math] — числовые признаки;
  • модель многомерной линейной регрессии:
    [math] f(x,\alpha) = \sum\limits_{j=1}^n \alpha_j f_j(x) [/math],
    где [math] a \in R^n [/math];
  • обучающая выборка: множество из пар [math](x_i, y_i)_{i=1 \dots n}[/math];
  • [math] x_i [/math] — объекты из множества [math] X = R^n [/math];
  • [math] y_i [/math] — объекты из множества [math] X = R [/math].

Матричные обозначения

Перейдем к матричным обозначениям:

[math] \underset{l \times n}{F} = \begin{pmatrix} f_1(x_1) & \dots & f_n(x_1) \\ \dots & \dots & \dots \\ f_1(x_l) & \dots & f_n(x_l) \end{pmatrix} , \underset{l \times 1}{y} = \begin{pmatrix} y_1 \\ \dots \\ y_l \end{pmatrix}, \underset{n \times 1}{\alpha} = \begin{pmatrix} \alpha_1 \\ \dots \\ \alpha_n \end{pmatrix} [/math],

где

  • [math] F [/math] — матрица объектов-признаков, где строки соответствуют объектам а столбцы — признакам;
  • [math] y [/math] — вектор ответов, или целевой вектор;
  • [math] \alpha [/math] — вектор коэффициентов.

Постановка задачи

В этих трех векторно-матричных обозначениях очень удобно расписать постановку задачи наименьших квадратов:

[math] Q(\alpha, X^l) = \sum\limits_{i=1}^n (f(x_i, \alpha) - y_i)^2 = || F\alpha - y ||^2 \rightarrow \underset{\alpha}{min} [/math].

Необходимо найти вектор [math] \alpha [/math] при известной матрице [math] F [/math] и известном вектор-столбце [math] y [/math].

Решение

Нормальная система уравнений

Запишем необходимые условия минимума в матричном виде:

[math] \frac{\partial Q }{\partial \alpha } (\alpha) = 2F^T (F\alpha - y) = 0 [/math].

Отсюда следует нормальная система задачи МНК:

[math] F^T F \alpha = F^T y [/math],

где [math] F^T F — n \times n [/math] матрица.

Мы получили систему уравнений, откуда можем выразить искомый вектор [math] \alpha [/math].

Решение системы

[math] \alpha^* = (F^T F)^{-1} F^T y = F^+ y [/math],
где [math] F^+ [/math] — псевдо-обратная матрица.

Значение функционала: [math] Q(\alpha^*) = ||P_F y - y||^2 [/math],
где [math] P_F = F F^+ = F (F^T F)^{-1} F^T [/math]проекционная матрица.

Проблемы

В случае мультиколлинеарности (столбцы матрицы [math] F [/math] линейно-зависимы) нам не удастся найти обратную матрицу к [math] F^T F [/math] (она будет вырождена).

Если же столбцы матрицы [math] F [/math] почти линейно-зависимы, то у нас возникнет масса вычислительных проблем с обращением этой матрицы.

Решение МНК через сингулярное разложение

Воспользуемся понятием сингулярного разложения , которое позволяет произвольную прямоугольную матрицу представить в виде произведения трех матриц:

[math] F = V D U^T [/math].

Найдем псевдо-обратную матрицу:
[math] F^+ = (U D V^T V D U^T)^{-1} U D V^T = U D^{-1} V^T = \sum\limits_{j=1}^n \frac{ 1 }{ \sqrt{ \lambda_j } } u_j v_j^T [/math].

Теперь, зная псевдо-обратную матрицу, найдем решение задачи наименьших квадратов:
[math] \alpha^* = F^+ y = U D^{-1} V^T y = \sum\limits_{j=1}^n \frac{ 1 }{ \sqrt{ \lambda_j } } u_j (v_j^T y) [/math].

Найдем вектор, которым наша линейная модель аппроксимирует целевой вектор [math] y [/math]:
[math] F \alpha^* = P_F y = (V D U^T) U D^{-1} V^T y = V V^T y = \sum\limits_{j=1}^n v_j (v_j^T y) [/math].

Квадрат нормы вектора коэффициентов:
[math] || \alpha^* ||^2 = ||D^{-1} V^T y||^2 = \sum\limits_{j=1}^n \frac{ 1 }{ \lambda_j } (v_j^T y)^2 [/math].

В 3-х из 4-х формул сингулярные числа оказались в знаменателе. Если имеются сингулярные числа приближающиеся к 0, то мы получаем проблему мультиколлинеарности. Близкие к 0 собственные значения или сингулярные числа — показатель того, что среди признаков есть почти линейно-зависимый.

Проблема мультиколлинеарности и переобучения

Если имеются сингулярные числа близкие к 0, то:

  • матрица [math] \sum = F^T F [/math] плохо обусловлена;
  • решение становится неустойчивым и неинтерпретируемым, слишком большие коэффициенты [math] || \alpha_j || [/math] разных знаков;
  • возникает переобучение:
    на обучении [math] Q( \alpha^*, X^l ) = ||F \alpha^* - y||^2 [/math] мало;
    на контроле [math] Q( \alpha^*, X^k ) = ||F' \alpha^* - y'||^2 [/math] велико.

Стратегии устранения мультиколлинеарности и переобучения:

  • отбор признаков, то есть выкидываем те признаки, которые могут оказаться линейно-зависимыми:
    [math] f_1, \dots, f_n \rightarrow f_{j_1} \dots, f_{j_m}, m \leq n [/math];
  • регуляризация (накладываем дополнительные ограничения на вектор коэффициентов):
    [math] || \alpha || \rightarrow min [/math];
  • преобразование признаков, чтобы в новом признаковом пространстве признаков оказалось меньше, но они хорошо восстанавливали бы исходные:
    [math] f_1, \dots, f_n \rightarrow g_1 \dots, g_m, m \ll n [/math].

Примеры кода

Пример кода для Scikit-learn

import matplotlib.pyplot as plt
from sklearn import datasets, linear_model

# generate dataset
X, y = datasets.make_regression(n_samples=1_000, n_features=1, noise=8, shuffle=True)

# test and train data sizes
train_size = 700
test_size = 300

# split the data into training/testing sets
X_train = X[:-train_size]
X_test = X[-test_size:]

# split the targets into training/testing sets
y_train = y[:-train_size]
y_test = y[-test_size:]

# create linear regression object
regr = linear_model.LinearRegression()

# train the model using the training sets
regr.fit(X_train, y_train)

# make predictions using the testing set
y_pred = regr.predict(X_test)

# plot outputs
plt.scatter(X_test, y_test, color='red', s=5)
plt.plot(X_test, y_pred, color='blue', linewidth=2)
 
plt.xticks(())
plt.yticks(())

plt.show()

Возможный результат исполнения программы:

Linear regression example.png

Пример на языке Java

Пример линейной регресии с применением weka.classifiers.functions.LinearRegression[1]

Maven зависимомсть:

 <dependency>
   <groupId>nz.ac.waikato.cms.weka</groupId>
   <artifactId>weka-stable</artifactId>
   <version>3.8.0</version>
 </dependency>
 import weka.classifiers.functions.LinearRegression;
 import weka.core.Instance;
 import weka.core.Instances;
 //Load Data set
 var data = new Instances(new BufferedReader(new FileReader("dataset/house.arff")));
 data.setClassIndex(data.numAttributes() - 1);
 //Build model
 var model = new LinearRegression();
 try { model.buildClassifier(data); }
 catch (Exception e) { e.printStackTrace(); }
 //output model
 System.out.printf("model parameters: %s%n", model);
 // Now Predicting the cost
 var myHouse = data.lastInstance();
 var price  = model.classifyInstance(myHouse);
 System.out.printf("predicted price = %s%n", price)

Пример на языке R

Основная статья: Примеры кода на R
# reading data
data <- read.csv("input.csv", sep = ',', header = FALSE)

# evaluating linear regression model
model <- lm(data$x ~ data$y)

# getting summary
print(summary(model))

# visualizing data
plot(data$y, data$x)
lines(data$y, predict(fit), col = 'red')

Применение

Перечислим несколько примеров реального применения линейной регрессии:

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

См. также

Источники информации

  • Weka, Linear Regression
  • Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Линейная_регрессия&oldid=85091»