{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Семинар 4. Линейная алгебра." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "В чем преимущество numpy?" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import numpy as np" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Как измерить время выполнения?\n", " - пакет time в python\n", " - %timeit (IPython magic function for timing)" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": true }, "outputs": [], "source": [ "A_quick_arr = np.random.normal(size = (100000,))\n", "B_quick_arr = np.random.normal(size = (100000,))\n", "\n", "A_slow_list, B_slow_list = list(A_quick_arr), list(B_quick_arr)" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "10 loops, best of 3: 41.5 ms per loop\n" ] } ], "source": [ "def my_sum(a, b):\n", " ans = 0\n", " for i in range(100000): \n", " ans += a[i] * b[i]\n", " return ans\n", "\n", "%timeit my_sum(A_quick_arr, B_quick_arr)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "10 loops, best of 3: 25.3 ms per loop\n" ] } ], "source": [ "%timeit sum([A_slow_list[i] * B_slow_list[i] for i in range(100000)])" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "10000 loops, best of 3: 150 µs per loop\n" ] } ], "source": [ "%timeit np.sum(A_quick_arr * B_quick_arr)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Что было в прошлый раз (и будет сегодня)? Линейная алгебра!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![](https://imgs.xkcd.com/comics/forgot_algebra.png)\n", "\n", "### Вектора и матрицы. \n", "\n", "#### Вектора\n", "$x = (x^1, ..., x^d)$ — вектор\n", "\n", "Векторное пространство $V$ — это множество:\n", " - состоящее из векторов \n", " - с определенными операциями сложения и умножения на число \n", " - замкнуто относительно этих операций\n", " - и выполнены 8 аксиом (см. лекцию)\n", " \n", "Например: евклидово пространство (вектор — набор вещественных чисел)\n", "\n", "Какое отношение имеет к анализу данных? Описывает объект!\n", "\n", "Например: задача кредитного скоринга. \n", "Объект — человек. \n", "Признаки:\n", " - пол (1 — мужской, 0 - женский)\n", " - зарплата \n", " - семейный статус (1 — женат, 0 - холост)\n", " - возраст\n", " - ...\n", "\n", "Получаем вектор:\n", "\n", "$x = (1, 100500, 1, 41, ...)$\n", "\n", "А как описать много объектов?\n", "\n", "#### Матрицы\n", "\n", "Хотим знать информацию про многих людей (матрица объекты-признаки):\n", "\n", "$ X = \\begin{pmatrix}\n", "1& 100500& 1& 41& ... \\\\ \n", "0& 0& 0& 18& ... \\\\\n", "...& ...& ...& ...& ... \\\\\n", "\\end{pmatrix}$\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Линейная независимость\n", "\n", "Один из векторов можно выразить через другие с помощью линейной комбинаций.\n", "\n", "Размерность векторного пространства — максимальное количество линейно независимых векторов в нем.\n", "\n", "Как понять что вектора линейно независимы? — Например, вычислить ранг (максимальное число линейно независимых строк/столбцов).\n", "\n", "**Как искать ранг?** [зайдем на википедию]\n", "\n", "1. Метод элементарных преобразований. Ранг матрицы равен числу ненулевых строк в матрице после приведения её к ступенчатой форме при помощи элементарных преобразований над строками матрицы. \n", "2. Метод окаймляющих миноров. Пусть в матрице A найден ненулевой минор k-го порядка M. Рассмотрим все миноры (k+1)-го порядка, включающие в себя (окаймляющие) минор M; если все они равны нулю, то ранг матрицы равен k. В противном случае среди окаймляющих миноров найдется ненулевой, и вся процедура повторяется.\n", "\n", "Выберем первый пункт.\n", "\n", "Как привести матрицу к ступенчатому виду?\n", "\n", "Элементарными преобразованиями матрицы называются следующие ее преобразования:\n", "\n", "1. Перестановка двух столбцов (строк) матрицы.\n", "2. Умножение всех элементов одного столбца (строки) матрицы на одно и то же число, отличное от нуля.\n", "3. Прибавление к элементам одного столбца (строки) соответствующих элементов другого столбца (строки), умноженных на одно и то же число.\n", "\n", "Алгоритм решения:\n", "1. В первом столбце выбрать элемент, отличный от нуля (ведущий элемент). Строку с ведущим элементом (ведущая строка), если она не первая, переставить на место первой строки (преобразование 1 типа). Если в первом столбце нет ведущего (все элементы равны нулю), то исключаем этот столбец, и продолжаем поиск ведущего элемента в оставшейся части матрицы. 2. Преобразования заканчиваются, если исключены все столбцы или в оставшейся части матрицы все элементы нулевые.\n", "Разделить все элементы ведущей строки на ведущий элемент (преобразование 2 типа). Если ведущая строка последняя, то на этом преобразования следует закончить.\n", "3. К каждой строке, расположенной ниже ведущей, прибавить ведущую строку, умноженную соответственно на такое число, чтобы элементы, стоящие под ведущим оказались равными нулю (преобразование 3 типа).\n", "4. Исключив из рассмотрения строку и столбец, на пересечении которых стоит ведущий элемент, перейти к пункту 1, в котором все описанные действия применяются к оставшейся части матрицы.\n", "\n", "Задание: найти ранг матрицы A\n", "\n", "$A = \\begin{pmatrix}\n", "3 & 1& -1 & -2 & 8 \\\\ \n", "7 & 1 & -2 & -1 & 12 \\\\\n", "11 & 1 & -3 & 0 & 16 \\\\\n", "2 & 2 & -1 & -5 & 12\n", "\\end{pmatrix}$\n", "\n", "[будет на проверочной =)]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Системы линейных уравнений\n", "\n", "Вектор-строка: $w = (w_1, ..., w_d) \\in \\mathbb{R}^{1 \\times d}$\n", "\n", "Вектор-столбец: $w = \\begin{pmatrix}\n", "w_1 \\\\ \n", "... \\\\\n", "w_d\n", "\\end{pmatrix} \\in \\mathbb{R}^{d \\times 1}$\n", "\n", "$Xw = y$ (линейная модель)\n", "\n", "Количество решений:\n", " - бесконечно\n", " - одно\n", " - ни одного\n", " \n", "Как понять?\n", " - если ранги X и X|y совпадают, то 1\n", " - если ранг X|y больше ранга X, то нисколько (система несовместа) \n", " - если rg(X) < d — то бесконечно.\n", "\n", "Как решать? Метод Гаусса.\n", "\n", "Два прохода:\n", "\n", "1. **Прямой.** На первом этапе осуществляется так называемый прямой ход, когда путём элементарных преобразований над строками систему приводят к ступенчатой или треугольной форме, либо устанавливают, что система несовместна. А именно, среди элементов первого столбца матрицы выбирают ненулевой, перемещают его на крайнее верхнее положение перестановкой строк и вычитают получившуюся после перестановки первую строку из остальных строк, домножив её на величину, равную отношению первого элемента каждой из этих строк к первому элементу первой строки, обнуляя тем самым столбец под ним. После того, как указанные преобразования были совершены, первую строку и первый столбец мысленно вычёркивают и продолжают пока не останется матрица нулевого размера. Если на какой-то из итераций среди элементов первого столбца не нашёлся ненулевой, то переходят к следующему столбцу и проделывают аналогичную операцию. \n", "2. **Обратный.** На втором этапе осуществляется так называемый обратный ход, суть которого заключается в том, чтобы выразить все получившиеся базисные переменные через небазисные и построить фундаментальную систему решений, либо, если все переменные являются базисными, то выразить в численном виде единственное решение системы линейных уравнений. Эта процедура начинается с последнего уравнения, из которого выражают соответствующую базисную переменную (а она там всего одна) и подставляют в предыдущие уравнения, и так далее, поднимаясь по «ступенькам» наверх. Каждой строчке соответствует ровно одна базисная переменная, поэтому на каждом шаге, кроме последнего (самого верхнего), ситуация в точности повторяет случай последней строки." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### На практике" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": false }, "outputs": [], "source": [ "import pandas as pd" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Загрузим данные для задачи кредитного скоринга:" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "
\n", " | Status of existing checking account | \n", "Duration in month | \n", "Credit history | \n", "Purpose | \n", "Credit amount | \n", "Savings account/bonds | \n", "Present employment since | \n", "Installment rate in percentage of disposable income | \n", "Personal status and sex | \n", "Other debtors / guarantors | \n", "... | \n", "Property | \n", "Age in years | \n", "Other installment plans | \n", "Housing | \n", "Number of existing credits at this bank | \n", "Job | \n", "Number of people being liable to provide maintenance for | \n", "Telephone | \n", "foreign worker | \n", "Credit | \n", "
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | \n", "A11 | \n", "6 | \n", "A34 | \n", "A43 | \n", "1169 | \n", "A65 | \n", "A75 | \n", "4 | \n", "A93 | \n", "A101 | \n", "... | \n", "A121 | \n", "67 | \n", "A143 | \n", "A152 | \n", "2 | \n", "A173 | \n", "1 | \n", "A192 | \n", "A201 | \n", "1 | \n", "
1 | \n", "A12 | \n", "48 | \n", "A32 | \n", "A43 | \n", "5951 | \n", "A61 | \n", "A73 | \n", "2 | \n", "A92 | \n", "A101 | \n", "... | \n", "A121 | \n", "22 | \n", "A143 | \n", "A152 | \n", "1 | \n", "A173 | \n", "1 | \n", "A191 | \n", "A201 | \n", "2 | \n", "
2 | \n", "A14 | \n", "12 | \n", "A34 | \n", "A46 | \n", "2096 | \n", "A61 | \n", "A74 | \n", "2 | \n", "A93 | \n", "A101 | \n", "... | \n", "A121 | \n", "49 | \n", "A143 | \n", "A152 | \n", "1 | \n", "A172 | \n", "2 | \n", "A191 | \n", "A201 | \n", "1 | \n", "
3 | \n", "A11 | \n", "42 | \n", "A32 | \n", "A42 | \n", "7882 | \n", "A61 | \n", "A74 | \n", "2 | \n", "A93 | \n", "A103 | \n", "... | \n", "A122 | \n", "45 | \n", "A143 | \n", "A153 | \n", "1 | \n", "A173 | \n", "2 | \n", "A191 | \n", "A201 | \n", "1 | \n", "
4 | \n", "A11 | \n", "24 | \n", "A33 | \n", "A40 | \n", "4870 | \n", "A61 | \n", "A73 | \n", "3 | \n", "A93 | \n", "A101 | \n", "... | \n", "A124 | \n", "53 | \n", "A143 | \n", "A153 | \n", "2 | \n", "A173 | \n", "2 | \n", "A191 | \n", "A201 | \n", "2 | \n", "
5 rows × 21 columns
\n", "\n", " | Status of existing checking account | \n", "Duration in month | \n", "Credit history | \n", "Purpose | \n", "Credit amount | \n", "Savings account/bonds | \n", "Present employment since | \n", "Installment rate in percentage of disposable income | \n", "Personal status and sex | \n", "Other debtors / guarantors | \n", "... | \n", "Property | \n", "Age in years | \n", "Other installment plans | \n", "Housing | \n", "Number of existing credits at this bank | \n", "Job | \n", "Number of people being liable to provide maintenance for | \n", "Telephone | \n", "foreign worker | \n", "Credit | \n", "
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | \n", "0 | \n", "6 | \n", "4 | \n", "4 | \n", "1169 | \n", "4 | \n", "4 | \n", "4 | \n", "2 | \n", "0 | \n", "... | \n", "0 | \n", "67 | \n", "2 | \n", "1 | \n", "2 | \n", "2 | \n", "1 | \n", "1 | \n", "0 | \n", "1 | \n", "
1 | \n", "1 | \n", "48 | \n", "2 | \n", "4 | \n", "5951 | \n", "0 | \n", "2 | \n", "2 | \n", "1 | \n", "0 | \n", "... | \n", "0 | \n", "22 | \n", "2 | \n", "1 | \n", "1 | \n", "2 | \n", "1 | \n", "0 | \n", "0 | \n", "2 | \n", "
2 | \n", "3 | \n", "12 | \n", "4 | \n", "7 | \n", "2096 | \n", "0 | \n", "3 | \n", "2 | \n", "2 | \n", "0 | \n", "... | \n", "0 | \n", "49 | \n", "2 | \n", "1 | \n", "1 | \n", "1 | \n", "2 | \n", "0 | \n", "0 | \n", "1 | \n", "
3 | \n", "0 | \n", "42 | \n", "2 | \n", "3 | \n", "7882 | \n", "0 | \n", "3 | \n", "2 | \n", "2 | \n", "2 | \n", "... | \n", "1 | \n", "45 | \n", "2 | \n", "2 | \n", "1 | \n", "2 | \n", "2 | \n", "0 | \n", "0 | \n", "1 | \n", "
4 | \n", "0 | \n", "24 | \n", "3 | \n", "0 | \n", "4870 | \n", "0 | \n", "2 | \n", "3 | \n", "2 | \n", "0 | \n", "... | \n", "3 | \n", "53 | \n", "2 | \n", "2 | \n", "2 | \n", "2 | \n", "2 | \n", "0 | \n", "0 | \n", "2 | \n", "
5 rows × 21 columns
\n", "