Полиномиальная регрессия

Это расширение линейной регрессии, которое позволяет моделировать более сложные зависимости между независимой переменной X и зависимой переменной Y. В отличие от линейной регрессии, где мы предполагаем линейную зависимость, полиномиальная регрессия использует полиномиальные функции для описания связи между переменными.

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

Логистическая регрессия

Это статистический метод, используемый для моделирования зависимости между одной или несколькими независимыми переменными и бинарной зависимой переменной (например, "да/нет", "1/0", "успех/неудача"). Этот метод особенно полезен в задачах классификации, где необходимо предсказать вероятность принадлежности объекта к одной из категорий.

Применение логистической регрессии:

- Классификация: Логистическая регрессия часто используется для классификации объектов на две категории. Например, предсказание, будет ли клиент купить продукт или нет, на основе его характеристик.

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

- Социальные науки: Применяется для анализа данных, где исследуется влияние различных факторов на бинарный результат (например, выборы, респонденты, ответившие "да" или "нет").

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

SVM (Support Vector Machine) — это алгоритм машинного обучения, используемый для задач классификации и регрессии. Он работает на основе нахождения гиперплоскости, которая наилучшим образом разделяет данные на различные классы.

Гиперплоскость — векторное пространство с n измерениями может быть разделено с помощью гиперплоскости, которая является подпространством размерности n−1. В двухмерном пространстве это линия, в трехмерном — плоскость, а в общем случае — гиперплоскость.

Задача SVM заключается в нахождении гиперплоскости, которая максимизирует расстояние (зазор) между ближайшими точками разных классов. Эти ближайшие точки называются опорными векторами.

SVM стремится максимизировать расстояние между классами, что помогает улучшить обобщающую способность модели. Чем больше зазор, тем меньше вероятность ошибки на тестовых данных.

SVM с линейным ядром

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

В SVM с линейным ядром задача состоит в том, чтобы найти гиперплоскость, которая наилучшим образом разделяет два класса данных с максимальным зазором (margin). Основная цель SVM — максимизировать расстояние между ближайшими точками двух классов (называемыми опорными векторами) и гиперплоскостью разделения.

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

Зазор (margin) - это расстояние между гиперплоскостью и ближайшими точками каждого класса. Задача SVM заключается в максимизации этого зазора.

Есть два типа зазора:
1. Классификация с жёстким зазором (hard margin), когда все обучающие образцы должны быть правильно классифицированы и находиться за пределами полосы разделения.
2. Классификация с мягким зазором (soft margin), когда вводится допущение, что некоторые обучающие образцы могут нарушать условие правильной классификации или попадать в полосу разделения

SVM с полиномиальным ядром

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

Влияние гиперпараметров
- Степень полинома d: Чем выше степень, тем более сложной становится граница между классами. При высоких значениях степень модели может стать излишне сложной и переобучиться.
- 𝛾: Этот параметр регулирует влияние отдельных признаков. Если γ слишком велико, модель может плохо обобщаться на новых данных.
- c0: Этот параметр смещает границу принятия решения, добавляя гибкость при нахождении разделяющей гиперплоскости.

Когда использовать полиномиальное ядро:
1. Данные содержат признаки, которые имеют полиномиальные зависимости.
2. Линейное ядро не может адекватно разделить классы.
3. Модель требует нелинейной границы, но с более низким уровнем сложности, чем при использовании RBF-ядра.

SVM с RBF ядром

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

Принцип работы RBF ядра:
RBF ядро трансформирует данные в высокоразмерное пространство признаков, где линейное разделение классов становится возможным. Вместо того чтобы пытаться разделить данные в исходном пространстве, оно создает нелинейные границы между классами в новом, высокоразмерном пространстве.

Когда использовать RBF ядро:
1. Линейные модели или полиномиальные ядра не дают хороших результатов, так как границы между классами слишком сложны.
2. Требуется максимальная гибкость в создании нелинейных границ между классами.
3. Данные имеют высокую сложность, и полиномиальные ядра не могут точно разделить классы.

Алгоритм k-ближайших соседей

k-Nearest Neighbors (k-NN) — это метод машинного обучения, основанный на принципе нахождения k ближайших точек данных (соседей) в пространстве признаков, которые наиболее близки к новой точке, и на их основе делается предсказание.

Алгоритм k-NN не строит модели и не использует обучение в привычном смысле. Вместо этого он просто сохраняет все тренировочные данные и использует их для предсказаний.

k — это количество ближайших соседей, на основе которых алгоритм делает предсказание для новой точки данных. Это ключевой гиперпараметр модели.

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

Найдя расстояние до всех точек в тренировочных данных, алгоритм выбирает 𝑘 ближайших соседей.

Метод случайного леса

Случайный лес (Random Forest) — это ансамблевый метод машинного обучения, который строит несколько деревьев решений и объединяет их предсказания для получения более точного результата.

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

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

Ридж-регрессия

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

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

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

Лассо-регрессия

Lasso Regression — это метод линейной регрессии, который включает регуляризацию для уменьшения сложности модели и предотвращения переобучения. Название "Лассо" происходит от "Least Absolute Shrinkage and Selection Operator", что подчеркивает две основные функции этого метода: сжатие коэффициентов и отбор признаков.

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

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

Задача о рюкзаке

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

Алгоритм:
1. Создаем двумерный массив размером
2. Заполняем первую строку массива нулями.
3. Для каждого предмета, начиная с первого и до n-го, проходим по всем возможным вместимостям рюкзака от 0 до W:
- Если текущий предмет можно положить в рюкзак, то выбираем максимальное значение между суммой стоимости текущего предмета и стоимостью предметов, которые можно положить в рюкзак с ограниченной вместимостью.
- Если текущий предмет нельзя положить в рюкзак, то значение остается таким же, как и в предыдущей ячейке массива.
4. Значение в последней ячейке массива будет являться оптимальной стоимостью предметов в рюкзаке.
5. Чтобы восстановить решение, начиная с последней ячейки, проверяем, было ли значение обновлено.

Сложность: O(nW), где n - число предметов, а W - вместимость рюкзака.

Код Хаффмана

Метод без потерь для сжатия данных, который использует переменную длину кодирования. Он был разработан Дэвидом Хаффманом в 1952 году.

Алгоритм:
1. Создаем таблицу частот символов в исходном наборе данных.
2. Создаем листы дерева для каждого символа на основе их частоты, присваивая символам коды длиной 1.
3. Повторяем следующие шаги до тех пор, пока не будет создано дерево:
а. Выбираем два узла с наименьшей частотой и создаем новый узел-родитель.
б. Присваиваем новому узлу суммарную частоту своих потомков.
в. Дополняем левому потомку кодом "0" и правому потомку кодом "1".
4. Повторяем шаг 3 до тех пор, пока все узлы не будут объединены в один корневой узел.

Алгоритм выполняет сортировку и слияние символов, что требует O(n log n) операций. Однако, само кодирование и декодирование имеют сложность O(n) (n - размер исходной строки).

Эластичная чистая регрессия

Elastic Net — метод линейной регрессии, который сочетает преимущества двух регуляризаций: Лассо (L1) и Риджа (L2). Он помогает справиться с задачей отбора признаков и предотвращает переобучение, особенно когда данные содержат много коррелирующих признаков.

Эластичная сеть использует комбинацию штрафов:
L1-регуляризация (Лассо): способствует разреженности признаков (некоторые коэффициенты становятся нулевыми).
L2-регуляризация (Ридж): снижает величину коэффициентов, предотвращая переобучение.

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

Градиентная повышающая регрессия

Gradient Boosting — это метод ансамблевого обучения, который объединяет несколько слабых моделей (обычно деревьев решений), чтобы получить мощную и точную модель. Идея заключается в том, чтобы каждое следующее дерево исправляло ошибки предыдущего.

Работа градиентного бустинга:
1) Инициализация: Создаем первое дерево, которое пытается предсказать целевое значение.
2) Оценка ошибки: Вычисляем разницу между фактическими значениями и предсказанными — это наши остатки.
3) Обучение следующего дерева: Строим следующее дерево на основе ошибок предыдущего, чтобы минимизировать остатки.
4) Комбинирование моделей: Итоговое предсказание — это сумма предсказаний всех деревьев с учетом их весов.

Каждое новое дерево учится на градиенте ошибки предыдущего, отсюда и название — градиентный бустинг.

Наивная байесовская классификация

Алгоритм машинного обучения, который основан на теореме Байеса. Он называется «наивным» потому, что предполагает независимость всех признаков друг от друга — даже если на практике это не всегда так. Несмотря на такое упрощение, алгоритм показывает отличные результаты в задачах классификации текста и фильтрации спама.

Основная идея — вычислить вероятность того, что объект принадлежит определенному классу, учитывая его признаки. Для этого используется формула Байеса.

Алгоритм наивного Байеса оценивает вероятность для каждого класса и выбирает тот, у которого вероятность выше.

Используется для фильтрация спама, анализа тональности или, например, классификации новостей.

Кластеризация k-средних — Группировка по схожести

Алгоритм k-средних (k-Means) — метод кластеризации без учителя, который делит набор данных на заранее заданное количество кластеров (k). Точки данных группируются вокруг центров кластеров на основе их схожести.

Цель алгоритма — минимизировать сумму квадратов расстояний от каждой точки до ближайшего центра кластера. Проще говоря, он старается сделать кластеры как можно более плотными и четко отделенными друг от друга.

Алгоритм выполняется в несколько шагов:
1) Инициализация центров кластеров: случайным образом выбираются k точек данных в качестве начальных центров.
2) Назначение точек: каждая точка данных привязывается к ближайшему центру на основе расстояния (обычно евклидового).
3) Обновление центров: вычисляются новые центры кластеров как среднее всех точек в каждом кластере.
4) Повтор: процесс назначения и обновления продолжается до тех пор, пока центры не перестанут меняться или не достигнется максимальное количество итераций.

DBSCAN — Кластеризация на основе плотности

Density-Based Spatial Clustering of Applications with Noise — алгоритм кластеризации, объединяющий точки данных в группы на основе их плотности. Если точки находятся близко друг к другу, они считаются частью одного кластера. Если точка сильно удалена от других, она считается выбросом (шумом).

Как работает DBSCAN
DBSCAN не опирается на сложные математические формулы — он использует два основных параметра:
Эпсилон (ε) — это радиус вокруг точки, в пределах которого алгоритм ищет ближайших соседей. Этот радиус называют "окрестностью".
Минимум точек (minPts) — минимальное количество точек в пределах радиуса ε, чтобы считать точку "основной".

Алгоритм выделяет три типа точек:
1) Основные точки — точки, вокруг которых находится не меньше minPts соседей в пределах радиуса ε. Они формируют "ядро" кластера.
2) Пограничные точки — точки, которые сами по себе не образуют кластер (меньше minPts соседей), но лежат в окрестности основной точки. Они как бы "пристегнуты" к кластеру.
3) Точки шума — точки, которые не принадлежат ни к одному кластеру и не попадают в окрестность основных точек. Это выбросы, которые игнорируются при построении кластеров.

Поиск самой длинной общей подпоследовательности (Longest Common Subsequence)

Используется для нахождения наибольшей общей подпоследовательности между двумя строками или последовательностями.

Алгоритм:

1. Создание таблицы. Создаем таблицу размером (n+1) на (m+1), где n и m - длины строк или последовательностей.

2. Итеративно проходимся по каждой ячейке таблицы слева направо и сверху вниз, сравнивая символы текущей позиции.
-Если символы совпадают, увеличиваем значение ячейки на 1 и переходим диагонально влево-вверх.
-Если символы не совпадают, выбираем максимальное значение из ячейки слева и сверху и записываем его в текущую ячейку.

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

Сложность: O(n*m)

Поиск Фибоначчи

Метод, основанный на сравнении, который использует числа Фибоначчи для поиска элемента в отсортированном массиве.

Последовательность Фибоначчи начинается с чисел 0 и 1, а каждое следующее число равно сумме двух предыдущих чисел. Вот первые несколько чисел последовательности: 0, 1, 1, 2, 3, 5, 8, 13 и т.д.

Сложность: O(log n)

Судоку

Алгоритм:
1. Создайте функцию, которая проверяет, действительна ли данная матрица судоку или нет. Сохраните Hashmap для строки, столбца и полей. Если какое-либо число имеет частоту больше 1 в hashMap, верните false, иначе верните true;
2. Создайте рекурсивную функцию, которая принимает сетку и текущий индекс строки и столбца.
3. Проверьте базовые случаи:
⁃ Если индекс находится в конце матрицы, т.е. i=N-1 и j=N, тогда проверьте, безопасна ли сетка или нет, если безопасно, распечатайте сетку и верните true, иначе верните false.
⁃ Другой базовый случай — когда значение столбца равно N, т. е. j = N, затем происходит переход к следующей строке, т. е. i++ и j = 0.
4. Если текущий индекс не присвоен, то заполняем элемент от 1 до 9 и повторяем для всех 9 случаев индекс следующего элемента, т.е. i, j+1. если рекурсивный вызов возвращает true, разорвите цикл и верните true.
5. Если присвоен текущий индекс, вызовите рекурсивную функцию с индексом следующего элемента, т. е. i, j+1.

Сложность: O(9^(n*n)

Проверка строки-палиндрома

Строка называется палиндромом, если обратная сторона строки совпадает с ней. Например, «abba» является палиндромом, потому что обратная сторона «abba» будет равна «abba».

Алгоритм:
1. Инициализируйте две переменные: l с начала и h с конца данной строки.
2. Теперь мы сравним символы с индексами l и h друг с другом.
3. Если символы не равны, строка не является палиндромом.
4. Если символы равны, мы увеличим l и уменьшим h.
5. Шаги 2,3 и 4 будут повторяться до тех пор, пока (l < h) или мы не обнаружим неравные символы.
6. Если мы достигнем условия ( l < h ), это означает, что все соответствующие символы равны и строка является палиндромом.

Сложность: O(n)