Допматериалы по работе с пропусками

Дополнительные материалы

Тест Литтла для выявления MCAR

Для того чтобы количественно определить полностью случайным ли образом сформированы пропущенные значения (MCAR), существует тест Литтла (Little’s test). Этот критерий был предложен⧉ в 1988 году Родериком Литтлом в качестве единого критерия оценки случайности пропущенных значений в многомерных количественных (!) данных.

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

Так как функция для проведения этого теста есть только на языке R, создадим новый ноутбук на R в Google Colab.

Откроем ноутбук с кодом на R

Датасет airquality

Вначале попрактикуемся на встроенном в R датасете airquality.

Посмотрим на первые строки датафрейма с помощью функции head().

датафрейм airquality в R

Оценим размерность.

Посмотрим на общие статистические показатели с помощью функции summary().

функция summary() на R

Теперь установим и импортируем библиотеку naniar⧉, которая и содержит необходимый нам тест Литтла.

Посмотрим на абсолютное количество и процент пропусков в каждом из столбцов.

абсолютное количество и процент пропусков в каждом из столбцов

Перейдем к статистическому тесту.

тест Литтла с помощью функции mcar_test()

Вероятность (p-value) очень мала, ниже порогового значения, например, в пять или даже один процент, и мы можем отвергнуть нулевую гипотезу о полностью случайных пропусках.

Кроме этого, функция mcar_test() сообщает о четырех выявленных в пропущенных данных паттернах.

Вернемся к датасету, с которым работали до сих пор.

Датасет «Титаник»

Подгрузите файл train.csv в сессионное хранилище ноутбука на R.

Импортируем его с помощью функции read.csv().

датасет "Титаник" на R

Обратите внимание, в параметр na.strings мы передали вектор с возможными вариантами записи пропущенных значений. Без этого параметра часть пропусков не была бы учтена.

Посмотрим на количество и процент пропусков в каждом столбце.

пропуски с помощью функции miss_var_summary()

Проведем тест Литтла.

тест Литтла на датасете "Титаник"

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

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

Временная сложность алгоритма

Откроем ноутбук с кодом на Питоне

Сравнение алгоритмов

Важность сравнения эффективности алгоритмов очевидна. Менее очевидным является способ их сравнения.

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

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

Линейный и бинарный поиск

Вернёмся к рассмотрению алгоритмов линейного и бинарного поиска. Вначале приведем соответствующие функции.

Эти алгоритмы аналогичны рассмотренным ранее, за исключением того, что в данном случае мы также будем считать количество операций. Под операцией в контексте поиска мы будем понимать сравнение искомого числа с очередным элементом массива.

Пусть даны два отсортированных массива из восьми и шестнадцати чисел.

Найдем в этих массивах индекс чисел 28 и 42 соответственно. Алгоритм линейного поиска ожидаемо справится за восемь и шестнадцать операций.

Заметим, что это худший случай из возможных (worst case scenario), искомые числа оказались на самом неудачном месте.

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

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

Количество операций (k) линейного поиска растет пропорционально количеству данных (n), т.е. $k = n$, это линейная зависимость, в бинарном же поиске зависимость логарифмическая $k = \log(n)$.

Сравним рост количества операций по мере роста объема данных.

Выведем результат на графике.

зависимость количества операций поиска от длины массива

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

Логарифмическая зависимость бинарного поиска

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

$$ \frac{n}{2}, \frac{n}{4}, \frac{n}{8}, \frac{n}{16}, \text{т.е.} \frac{n}{2^{k}} $$

В нашем случае,

$$ \frac{16}{2^k} $$

Выполнять такое деление мы будем до тех пор, пока количество чисел не будет равно одному (т.е. мы найдем нужное число).

$$ \frac{n}{2^k} = 1, 2^k = n $$

Тогда k (количество операций) будет равно

$$ k = \log_2 (n) $$

В нашем случае,

$$ 4 = \log_2 (16) $$

Нотация «О» большого

Такая оценка называется временной сложностью (time complexity) алгоритма и обычно выражается в O-символике или нотации «О» большого (big-O notation). Для приведенных выше алгоритмов запись будет выглядеть так:

  • линейный поиск: $O(n)$
  • бинарный поиск: $O(\log(n))$

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

  • для алгоритма линейного поиска в лучшем случае (если искомое значение стоит на первом месте) его сложность составит O(1), то есть потребуется одна операция
  • при бинарном поиске, если искомое число находится, что наиболее удачно, в середине отсортированного массива, его сложность также составит O(1)

Основание логарифма обычно не приводится поскольку

$$ \log_a b = \frac{\log_c b}{\log_c a} $$

Асимптотическое время

Нотация «О» большого отражает так называемое асимптотическое время работы алгоритма.

Асимптотический анализ (asymptotic analysis) изучает поведение функции при стремлении аргумента к определенному значению. В нашем случае мы смотрим на количество операций (поведение функции) при значительном увеличении объема данных (аргумент).

Скорость изменения функции ещё называют порядком изменения, от англ. order или нем. Ordnung, отсюда буква «O» в нотации.

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

Существует также константное время (когда сложность алгоритма не зависит от объема данных, $O(1)$, квадратичное время $O(n^2)$ или, например, факториальное $O(n!)$. В последнем случае, количество операций растет наиболее стремительно.

Про константы

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

Мы взяли массивы из 8-ми и 16-ти чисел и по формуле, должны были уложиться в $ \log_2(8) = 3 $ и $ \log_2(16) = 4 $ операции. Фактически же мы затратили четыре и пять соответственно.

Другими словами сложность алгоритма бинарного поиска в худшем случае составляет $ O(\log(n) + 1) $, однако так как нас интересует порядок (примерное понимание) роста функции при росте аргумента, а не точное значение, константы принято опускать.

Аналогично $O (2\log(n)) $ сводится к $ O (\log(n)) $.

Временная сложность в ML

Как применять вычислительную сложность алгоритма на практике? Рассмотрим два примера.

Поиск ближайших соседей по k-мерному дереву существенно быстрее, чем простой перебор всех векторов сравнения и расчет расстояния.

  • Во втором случае (brute force) временная сложность равна $O(n, m)$, где $n$ — количество векторов запроса, а $m$ — количество векторов сравнения.
  • В первом (kdtree) — $O(n\log(m))$, правда без учета операций для создания k-мерного дерева.

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

Например, из документации⧉ мы знаем, что сложность алгоритма IterativeImputer составляет

$$O(knp^3\min(n,p))$$

где $k$ — максимальное число итераций, $n$ — количество наблюдений, а $p$ — количество признаков. Таким образом, очевидно, что для снижения количества необходимых операций, в первую очередь нужно работать с признаками.

Еще одно сравнение методов заполнения пропусков

Способ сравнения

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

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

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

Создание данных с пропусками

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

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

Обратите внимание на один нюанс. Функция random.sample(), что удобно, выбирает элемент без возвращения, то есть один раз выбрав наблюдение с индексом «один», второй раз она это наблюдение не выберет.

Мы могли бы использовать функции np.random.randint() или random.choice(), однако в этом случае из-за повторов процент пропусков был бы чуть ниже желаемого, например не 20, а 18.

Применим объявленную функцию к датафрейму и создадим 20 процентов пропусков в первом столбце.

Проверим результат.

Перейдем к заполнению пропусков.

Заполнение пропусков

Заполнение константой

Заполнение медианой

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

Заполнение линейной регрессией

Напишем функцию для заполнения пропусков линейной регрессией.

Заполним пропуски.

Заполнение с помощью MICE

Заполнение с помощью KNNImputer

В данном случае используем только один из методов k-ближайших соседей, а именно класс KNNImputer библиотеки sklearn.

Заполнение с помощью Datawig

Сформируем и скачаем на диск .csv файл с пропусками для работы в другом ноутбуке.

Перейдем в ноутбук с библиотекой Datawig⧉. Подгрузим только что сформированный файл.

Подготовим данные.

Обучим модель.

Сделаем прогноз.

заполнение пропусков с помощью Datawig

Теперь, прежде чем «склеивать» train и test, нам нужно переименовать столбец mean radius_imputed и перенести его на первое место. Сделать это можно, соединив два метода библиотеки Pandas, метод .insert() и метод .pop().

применение методов .insert() и .pop() библиотеки Pandas

Соединим части датасета и обновим индекс.

Сформируем файл для переноса в основной ноутбук.

Также вы можете скачать уже готовый файл.

Вернемся обратно в основной ноутбук. Подгрузим и импортируем файл datawig_xnan.csv.

Остается оценить качество созданных моделей.

Оценка результата

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

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

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

Обратите внимание, результат линейной регрессии совпал с результатом алгоритма MICE (как в случае с датасетом «Титаник», так и в текущем сравнении методов). Это логично, MICE, как и линейная регрессия использовали один и тот же алгоритм (класс LinearRegression) и одни и те же признаки без пропусков (и MICE не пришлось заполнять их средним значением).

Сериализация и десериализация данных

Ранее мы обратили внимание на то, что библиотека Datawig создала файлы модели, в частности, в форматах JSON и Pickle. Зачем это нужно?

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

Процесс преобразования объекта (в частности, модели) в формат, пригодный для хранения и передачи данных, называется сериализацией (serialization). Процесс восстановления из этого формата называется соответственно десериализацией (deserialization).

сериализация и десериализация данных

Вначале рассмотрим в целом процесс серилизации в JSON и Pickle, а затем перейдем к работе с моделями.

Формат JSON

Формат JSON расшифровывается как JavaScript Object Notation, но, несмотря на наличие слова JavaScript в своем названии, не зависит от языка программирования. Кроме того, он позволяет сериализовать данные в человекочитаемый формат.

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

По сети мы получили объект типа bytes, то есть последовательность байтов, и десериализовали его с помощью метода .loads() в формат питоновского словаря.

Убедиться в человекочитаемости этого формата можно просто перейдя по ссылке в браузере: https://random-data-api.com/api/v2/banks⧉.

Вложенный словарь и список словарей

JSON-объект можно создать из вложенных питоновских словарей или списка словарей.

Методы .dumps() и .loads()

Вначале применим метод .dumps() для создания строкового JSON-объекта.

Обратите внимание, что хотя объект похож на питоновский словарь, тем не менее это строка. Восстановим словарь с помощью метода .loads().

Методы .dump() и .load()

Метод .dump() создает последовательность байтов и используется для записи JSON-объекта в файл. Этот метод принимает два основных параметра: источник данных и файл, в который следует записать JSON-объект. Передадим ему этот файл с помощью конструкции with open().

Восстановим список словарей из файла.

Посмотрим на результат.

Обратите внимание, результат десериализации — это новый объект.

JSON и Pandas

Библиотека Pandas позволяет сохранить датафрейм в файл формата JSON, а также импортировать такой файл и соответственно восстановить датафрейм.

создание датафрейма из JSON-файла
Скриншот демонстрирует только часть датафрейма

Pickle

Если JSON-объект можно создать на Питоне, а восстановить на Java, то объект Pickle сериализуется и десериализуется только с помощью Питона. За это отвечает одноименная библиотека.

Методы .dumps() и .loads()

Методы .dumps() и .loads() преобразуют объект в байты и восстанавливают исходный тип данных соответственно.

Методы .dump() и .load()

Методы .dump() и .load() сериализуют объект в файл и соответственно десериализуют объект из файла.

При создании файла в формате pickle можно использовать расширения .p, .pkl или .pickle.

Собственные объекты

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

Начнем с функций.

То же самое можно сделать с классом.

Обратите внимание, что после десериализации мы смогли восстановить не только общую структуру класса, но и те данные (атрибут color), которые поместили в создаваемый объект.

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

Сохраняемость модели ML

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

В машинном обучении говорят, что процесс сериализации и десериализации выполняется ради обеспечения сохраняемости модели (model persistance).

При этом, при использовании модуля Pickle, на этапах сериализации и десериализации важно работать с одинаковыми версиями Питона и используемых библиотек (например, sklearn). В противном случае результат может быть непредсказуемым. Это заставило некоторых специалистов предложить⧉ серилизацию модели ML с помощью JSON.

Рассмотрим сериализацию модели на практике. Вначале обучим модель логистической регрессии.

Оценим результат.

результат классификации с помощью исходной модели

Теперь выполним сериализацию и десериализацию модели.

Передадим десериализованной модели те же данные и убедимся, что она выдаст результат идентичный изначальной модели.

результат классификации с помощью десериализованной модели

Подведем итог

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