Машинное обучение #

Введение в машинное обучение и основные понятия статистики #

Представление данных #

Данные представляются в виде таблицы, в которой:

• строки - объекты
• столбцы - признаки

Ограничение табличного представления данных - все объекты должны иметь одинаковое количество признаков.

Типы признаков #

• Количественный (числовой) - область значения - вещественные числа, сам имеет числовую природу
• Порядковый - задаёт порядок, последовательность объектов
• Номинальный (категориальный) - не имеет числовой природы, как правило, число возможных значений конечно.
  • Бинарный - частный случай номинального признака, имеющий два значения

Характеристики признаков #

• максимальное и минимальное значения
• среднее арифметическое значение
• медиана - центральное значение в выборке, либо среднее от двух центральных значений, если количество элементов четное; значение медианы в том, что на нее не так сильно влияет попадание в выборку аномальных данных
• мода - наиболее часто встречающееся значение в выборке; в отличии от среднего и медианы имеет смысл и для номинальных признаков
• средне квадратичное отклонение (отклонение) - отражает отличие элементов выборки друг от друга, т.е. если все элементы одинаковы, отклонение - нулевое, в остальных случаях - положительное
  • всегда неотрицательное
  • равно нулю, если все значение признака равны друг другу
  • чем больше величина отклонения, тем сильнее разброс значений выборки относительно среднего значения \( S_p = \sqrt{\frac{1}{n-1}\sum{i=1}_n(p_i - \overline{p})^2} \)

Если медианное и среднее значения близки друг к другу, выборка называется симметричной. В таких выборках проще искать аномалии.

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

Где \(h_p\) - медиана

Коэффициент корреляции #

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

С геометрической точки зрения, КК - показатель того, как значения признаков ложатся на прямую.

Формула КК:

Свойства КК:

• принадлежит к отрезку [-1, 1]
• если равен нулю или близок к нему, то очевидной зависимости между признаками нет.
• КК > 0 - прямая зависимость между признаками
• КК < 0 - обратная зависимость
• чем ближе модуль КК к 1, тем зависимость (при 1, она линейная)

Восстановление пропущенных значений #

Виды повреждения данных:

• пустые (пропущенные) значения
• (заведомо) некорректные данные

Способы борьбы с пропусками данных:

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

Метрика. Восстановление пропущенных объектов по их близости друг к другу #

Метрика - обобщение понятия расстояния из геометрии и может быть вычислена для объектов произвольной природы.

Дано два набора данных:

Формулы вычисления метрики:

1. Евклидова метрика (геометрическая формула расстояния между точками):

2. Метрика Манхеттен

3. Max-метрика

Свойства метрики #

1. Расстояние от объекта до него же самого должно равняться нулю
2. Расстояние от одного объекта до другого должно равняться обратному расстоянию
3. Расстояние между двумя точками должно быть меньше чем сумма расстояний между этими точками и любой произвольной, не лежащей на прямой между ними (неравенство треугольника)

Формула восстановления данных с помощью метрики

Способы нормирования признаков #

Нормирование - приведение всех признаков к единому масштабу.

Признак: \(P = (p_1, p_2, ..., p_n)\) \(\overline{p}\) - среднее значение \(s\) - отклонение

1. Приведение всех признаков в интервал [0, 1]:

2. Выполнить преобразование, после которого среднее значение и отклонение признака будут равны 0 и 1:

3. Помимо приведенных формул, к значению признака можно предварительно применять различные функции, например логарифмирование.

Использование коэффициента корреляции для восстановления данных #

КК - выражает как сильно значение одного признака влияют на значения другого признака, т.е. меру близости признаков (т.е. столбцов таблицы). Метрика - выражает меру близости объектов (строк таблицы).

Формула восстановления пропущенного значения с помощью среднего значения и КК:

Пусть P(A) - значение признака P объекта A \(\overline{P}\) - среднее значение признака P Требуется определить P(A) по столбцам-признакам \(P_1, P_2, ..., P_m\)

Все вычисления проводятся без учета строки с пропущенным значением.

При использовании КК в работе с данными признаки можно не нормировать. КК также не изменится при изменении масштаба признаков и переводе в другие единицы измерения.

Применение метрик и КК в рекомендательных системах #

Алгоритмы восстановления данных можно использовать при проектировании рекомендательных систем.

Рекомендательная система:

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

С математической точки зрения это таблица, в которой:

• строки соответствуют пользователям
• столбцы - товарам
• на пересечении - оценка, которую пользователь поставил конкретному товару

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

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

Поиск выбросов и аномалий #

Задача поиска выбросов (outlier detection) заключается в нахождении всех аномальных объектов в заданном множестве.

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

1. Если данные будут использоваться при решении задачи предсказания, то удаление выбросов, как правило, повышает точность предсказания
2. Удаление выбросов позволяет получить нормальные (типичные, эталонные) объекты
3. Многие характеристики (например, среднее значение) очень чувствительны к наличию выбросов

Идеальных методов обнаружения выбросов не бывает потому, что…

• … не существует формального определения выброса
• … алгоритм, беспощадный к выбросам, будет удалять и часть “нормальных” объектов
• … алгоритм, гуманный к “нормальным” объектам, будет пропускать часть выбросов

Методы обнаружения выбросов #

1. Поиск аномальных объектов с помощью здравого смысла; например, если известен нормальный диапазон для значений признака.
2. Методы, основанные на анализе одного признака (каждый признака берётся отдельно и ищутся объекты с аномальными значениями этого признака).
3. Методы, основанные на одновременном анализе нескольких признаков.

Методы, анализирующие признаки по отдельности #

Дано: \(P = (p_1, p_2, ..., p_n) \)

Где,

Основная идея поиска аномалий - найти значения \(p_i\) , расположенные вдали от среднего значения или медианы.

Простейшие методы поиска:

1. Удалить все объекты, у которых величина \(|p_i - \overline{p}|\) слишком велика (этот метод не учитывает величину отклонения признака; для некоторых признаков большой показатель отклонения это норма)
2. Удалить все объекты, у которых величина \(\frac{|p_i - \overline{p}|}{S_p}\) слишком велика
3. Более продвинутый критерий Шовене
4. Определение выбросов без использования среднего и отклонения

Простое правило для определения выброса (второй метод) #

1. Пусть X - подозрительное значение
2. Исключим X из выборки и по оставшимся элементам вычислим среднее и отклонение
3. Если выборка симметричная, то X будет выбросом, если он не принадлежит интервалу \( (\overline{p} - 3S_p, \overline{p} + 3S_p) \)
4. Если выборка не симметричная, то X будет выбросом, если он не принадлежит интервалу \( (\overline{p} - 5S_p, \overline{p} + 5S_p) \)

Критерий Шовене (Chauvenet) #

Значение \(p_i\) является выбросом, если выполнено неравенство

Где \(erfc(x) = \frac{2}{\sqrt{\pi}}\int_x^\infty e^{-t^2}dt\) дополнение функции ошибок

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

Поиск выбросов без использования среднего и отклонения #

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

Квартили:

• 1-ая квартиль \(Q_{25}\) - это такое число, что ровно 25% выборки меньше его
• 2-ая квартиль \(Q_{50}\) - это такое число, что ровно 50% выборки меньше его (фактически это медиана)
• 3-ая квартиль \(Q_{75}\) - это такое число, что ровно 75% выборки меньше его

Таким образом, 50% выборки принадлежат интервалу \([Q_{25}, Q_{75}]\) , их можно считать “эталонными”. Соответственно, элементы, достаточно удаленные от этого интервала можно считать выбросами.

Если элемент не попадает в интервал: \( (Q_{25} - 1,5*(Q_{75} - Q_{25}), Q_{75} + 1,5*(Q_{75} - Q_{25})) \) то он является выбросом.

Методы, анализирующие несколько признаков #

• необходимы в случаях, когда аномальное значение сходно, к примеру, со средним между нормальными значениями
• аномалии могут характеризоваться не только экстремальными значениями одного признака, но и нестандартными комбинациями нескольких признаков (например, сами по себе вес в 100 кг и рост 150 см не являются аномалиями, но их сочетание у одного объекта - является)

1. Метрические методы

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

2. Геометрические методы

• объекты проецируются на n-мерное пространство (например, на плоскость, в случае, если объекты могут быть описаны двумя признаками)
• строится выпуклая оболочка - многоугольник (для двумерного пространства) или многогранник, который неким образом описывает точки
• аномалиями в данном случае будут точки, лежащие на оболочке

3. Поиск с помощью кластеризации

• при этом, объекты будут разделены на группы по некоторому признаку (или их сочетанию)
• при таком подходе выбросами считаются элементы малых (в том числе одноэлементных групп)

4. Поиск с помощью моделей предсказания

• некоторые вариации метода опорных векторов (SVM)
• вариация решающих деревьев (decision trees) под названием “изолирующий лес”
• с помощью произвольной модели предсказания некоторого признака P по другим признакам таблицы
  • в этом случае выбросом будет тот объект, для которого предсказанное и имеющееся значения разойдутся очень сильно

Кластеризация (clustering) #

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

Задачи кластеризации:

• вычисления степени сходства объектов
• упрощение дальнейшей обработки данных (обработка меньших групп данных)
• сокращение объема хранимых данных за счет оставления одного представителя (эталона) от каждого кластера (задача сжатия данных)
• поиск выбросов
• разбиение признаков на кластеры и оставление по одному признаку из каждого кластера (отбор признаков)

Типы алгоритмов:

1. разбивающие данные на заданное число кластеров (то есть число кластеров - входной параметр алгоритма)

• пример: алгоритм k-means
• недостатки:
  • человеческий фактор(проблемы с предсказанием верного количества конечных кластеров)

2. в которых число кластеров не определено заранее, а вычисляется самим алгоритмом

• пример: алгоритм FOREL
• недостатки:
  • алгоритм может выдать слишком много(мало) кластеров; в этом случае вся операция бесполезна

Если алгоритм кластеризации использует метрику на множестве объектов, то значения всех признаков необходимо предварительно нормировать!!1!

Кластеризация с помощью графов #

Данные представляются в виде графа, где:

• вершина - объект
• ребро - расстояние между объектами

Соответственно перед построением графа необходимо вычислить расстояния между каждой парой объектов

Описание алгоритма:

1. На вход алгоритма подается некоторое число R
2. Из графа удаляются все ребра, метрики которых > R
3. Оставшиеся после этого связными компоненты графа являются кластерами

Описание второго алгоритма

1. На вход подается желаемое число кластеров k
2. Строится остовное дерево (это подграф, содержащий все вершины исходного графа и не имеющий циклов) c минимальной суммарной длиной ребер; для этой задачи могут применяться:

• алгоритм Краскала
• алгоритм Прима

3. Удаляем из дерева k-1 самых длинных ребер
4. В один кластер попадают вершины из связанных компонент

Алгоритм FOREL (формальный элемент) #

Главное свойство алгоритма - количество кластеров не определено заранее Идея - найти точки сгущения объектов и объявить эти сгущения кластерами

Описание алгоритма:

• На вход подается число R
• Представление данных: объекты представляются точками в пространстве \(R^m\) , где m - количество признаков объекта

1. В произвольную точку пространства добавляем формальный объект F (отсюда и название)
2. Пусть K - все объекты, до которых расстояние от F меньше R
3. Находим центр тяжести объектов из множества K и переносим туда объект F. Переходим к шагу 2

• итерируемся по шагам 2-3 до тех пор, пока множество K не стабилизируется (то есть в него перестанут добавляться новые элементы и удаляться старые)

4. После стабилизации множество K объявляется новым кластером и объекты, попавшие в него удаляются из выборки
5. Возвращаемся на шаг 1, если выборка не пуста, иначе алгоритм завершается

Центр тяжести - точка, координаты которой совпадают со средним значением признака.

Алгоритмы k-means (k-средних) #

• Главное свойство: количество кластеров k определено заранее
• Идея реализации: одновременно происходит поиск всех центров кластеров

Описание алгоритма (одна из реализаций):

• Вход: число кластеров k
• Представление данных: объекты представляются точками в пространстве \(R^m\) , где m - количество признаков объекта

1. Генерируем k случайных точек - центры кластеров
2. Объект будет отнесен к тому кластеру, чей центр расположен ближе всех к этому объекту
3. В получившихся кластерах центр переносится в центр тяжести, возврат на шаг 2

• шаги 2-3 повторяются до тех пор, пока центры кластеров не стабилизируются

Недостатки алгоритма:

• результат зависит от выбора исходных центров кластеров, их оптимальный выбор неизвестен

Выбор оптимального числа кластеров #

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

Идея - будем перебирать значения k, пока “качество кластеризации” не стабилизируется.

• Пусть \(S_k\) - сумма расстояний от объектов до центров их кластеров (при условии, что объекты разбиты на k кластеров).
• Тогда величину \(|S_{k+1} - S_k|\) можно рассматривать как увеличение качества кластеризации при переходе от k кластеров к (k+1) кластеру.
• Таким образом, “качество кластеризации” стабилизируется для такого k, где величина \(|S_{k+1} - S_k|\) становится небольшой.

Кластеризация по столбцам #

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

Собственно сама кластеризация по столбцам выполняется в два шага:

• данные транспонируются
• применяется один из стандартных алгоритмов кластеризации

Назначение:

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

Задача предсказания, линейная регрессия #

Предсказание (prediction):

• есть множество объектов M с известными значениями признака Y (целевой признак)
• требуется найти Y для нового объекта \(A \notin M\)

Задачи предсказания:

1. Предсказание количественного признака Y называется задачей регрессии
2. Предсказание номинального (категориального) признака Y называется задачей классификации

План решения задачи регрессии #

Общий план решения:

• множество объектов разбить на 2 множества:
  • тренировочную выборку (Train)
  • тестовую или проверочную выборку (Test)
• модель предсказания будет строиться по объектам Train, а качество проверяться объектам Test

Показатели качества регрессии:

1. MAE (средняя абсолютная ошибка):

Где:

2. MAPE (средняя абсолютная ошибка в процентах):

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

Принцип работы модели (линейной) регрессии:

Узлы - это объекты тренировочной выборки

Предсказываться значения Y в новых точках можно с помощью:

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

Модель регрессии называется линейной, если значение предсказываемого признака Y вычисляется как сумма известных признаков \(X_1, X_2,... X_m\) , взятых с некоторыми коэффициентами

Задача заключается в нахождении оптимальных весов (коэффициентов) \(w_i\) .

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

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

Построение модели линейной регрессии #

Отклонение истинного от предсказанного значения равно \(|y' - y| = |w_1x + w_0 - y|\) . Эту величину нужно минимизировать для всех объектов тренировочной выборки.

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

В общем случае:

Когда нецелевых признаков больше одного, все происходит аналогично, только параметров \(w_i\) будет больше (и полученная зависимость \(y'=...\) будет уже определять не прямую, а гиперплоскость).

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

Проблемы модели линейной регрессии #

Получаемая при построении линейной регрессии система линейных уравнений может:

1. Не иметь решений
2. Иметь более одного решения

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

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

Проблемы системы с бесконечным количеством решений:

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

Советы по поиску хорошей модели регрессии:

1. Отбор признаков. Нужно удалять нецелевые признаки, которые линейно зависят от других или имеют высокую корреляцию с другими признаками
2. Коэффициент регрессии можно минимизировать (“регуляризация” и “лассо”)

Обобщение модели линейной регрессии:

1. Регуляризация (Ridge-regression)

Основная идея:

• нужно стремиться сделать коэффициент регрессии минимальным
• величины весов также должны быть минимальными (по модулю)

Способ минимизации:

Где C - заданная константа

2. Лассо

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