В этой статье объясняется, как выполнить стратифицированное разделение сгруппированного набора данных на обучающие и проверочные наборы.
Одним из наиболее частых шагов в конвейере машинного обучения является разделение данных на наборы для обучения и проверки. Это один из необходимых навыков, которым должны овладеть все практикующие, прежде чем решать любую проблему. Процесс разделения требует случайного перемешивания данных с последующим разделением с использованием заранее установленного порога. В вариантах классификации вы можете использовать стратификацию, чтобы гарантировать одинаковое распределение классов в обоих наборах. При обработке данных временных рядов вы можете пропустить перемешивание и сохранить самые ранние наблюдения в обучающем наборе. Вы также можете сгруппировать данные, и вы, вероятно, захотите объединить группы в любом наборе данных. Наконец, возможно, вам повезет встретить сочетание вышеперечисленного и у вас не будет подходящего решения для этого, как это случилось со мной.
В этой статье представлено решение, которое я разработал для обработки стратифицированного разделения сгруппированных данных, при котором группы должны храниться вместе в любом наборе данных.
Фон
Недавно я работал над проектом профилактического обслуживания нескольких тысяч промышленных устройств. Эти устройства передают данные телеметрии через беспроводное соединение в серверную систему, где они хранятся и обрабатываются. Все устройства проходят регулярный график профилактического обслуживания, которого недостаточно, чтобы избежать случайных неожиданных поломок. Из-за разрушительного характера этих поломок производитель устройств решил создать набор моделей профилактического обслуживания, чтобы попытаться предсказать вероятность несвоевременного отказа устройства до следующего периода обслуживания.
Моей команде было поручено работать над конкретным компонентом устройства и разработать модель профилактического обслуживания для оценки вероятности отказа в будущем. Мы выбрали классификационную модель и прошли весь процесс настройки конвейера. Когда мы подошли к этапу разделения набора данных, мы решили не разделять данные устройства между обучающими и проверочными наборами. Данные каждого устройства будут либо на первом, либо на втором, и никогда не будут разделены между ними. Мы также решили провести стратифицированное разбиение, чтобы в обоих наборах была одинаковая доля положительных наблюдений.
На данный момент мы поняли, что не существует документированного способа решения этой проблемы. Пакет Scikit-Learn реализует решения для разделения сгруппированных наборов данных или для выполнения стратифицированного разделения, но не для того и другого одновременно. Немного подумав, это имеет смысл, поскольку это задача оптимизации с несколькими целями. Вы должны разделить данные по границам группы, обеспечивая требуемую пропорцию разделения, сохраняя при этом общее расслоение.
Излишне говорить, что эта часть конвейера была ручной, с использованием генератора случайных чисел и нескольких проб. Нет, я не горжусь этим, отсюда и эта статья.
Постановка задачи
Учитывая помеченный и сгруппированный набор данных, мы хотим разделить его на наборы для обучения и проверки, сохраняя при этом распределение меток как можно ближе к обоим и групповой целостности. После разделения данных на два набора данных группы должны сохранять свою целостность, назначать их любому набору, а не разделять между ними. Кроме того, процесс разделения должен строго соблюдать установленную пропорцию разделения и стратификацию меток.
Ожидаемый результат для этой проблемы - для входного набора данных список групп, назначенных каждому набору данных, гарантирующий, что как разделение на обучение / проверка, так и стратификация как можно ближе к указанным значениям.
Исследование решений
Я начал с того, что обратился за помощью к классическим пакетам оптимизации, таким как OR-Tools от Google. К сожалению, я не нашел там решения. Реализованные оптимизационные решения казались мне близкими к тому, что мне было нужно, но сигары все равно не было. Я искал решение, которое можно было бы использовать из конвейера Python, поэтому некоторые хорошо известные оптимизаторы на основе Java казались недоступными. Почему бы не свернуть свою?
Несколько лет назад я участвовал в разработке оптимизатора маршрута транспортных средств, что позволило мне много узнать о дискретных алгоритмах оптимизации. Я обобщил свои знания в статье ниже.
Изучив все эти идеи, я решил разработать решение этой проблемы для оптимизации на основе Python. Я представляю код для проверки концепции, которая впоследствии может привести к созданию независимого пакета Python. Начнем с обзора модели проблемы.
Модель проблемы
Чтобы решить эту проблему, нам не нужно обрабатывать весь набор данных, только его количество. Нам нужно только определить количество различных групп и количество классов в каждой группе. Чтобы мотивировать обсуждение проблемной модели, давайте посмотрим на игрушечный пример, в котором мы хотим наложить разделение 70/30.
На изображении выше показаны модель и решение элементарной проблемы. Каждая строка таблицы содержит описание группы с размером в первом столбце, количеством образцов первого класса во втором, а третья указывает на включение проверочного набора (предлагаемое решение). Вы можете увидеть итоги столбца внизу вместе с рассчитанной долей образцов первого класса (20,70%).
Итак, как работает предлагаемое решение? Чтобы проверить соответствие разделению 70/30, нам нужно добавить все значения первого столбца, отмеченные (значение 1) в третьем, как принадлежащие набору проверки. Частичная сумма (10960) составляет 29,74% от общей суммы, что довольно близко к требуемым 30%. Для проверки расслоения проделываем то же самое, но во втором столбце. Сумма (2328) составляет 21,24% от предыдущего подсчета, что означает, что мы довольно близко подошли к требуемым 20,70%.
Стоит отметить, что и проблема, и представление решения довольно просты. Мы можем представить решение как логический массив, который очень компактен.
Итак, как я пришел к решению?
Модель оптимизации
Как было показано ранее, мы хотим найти решение данной проблемы, которое подходит как к цели разделения, так и к цели стратификации. Обратите внимание, что стратификация будет иметь несколько целей, если у вас более двух классов.
Процесс оптимизации начинается с генерации начального приближенного решения с использованием случайной перестановки групп.
Первоначальное решение
Первоначальное решение - это наш первый подход к проблеме, шаг вперед в процессе поиска. Чтобы ускорить процесс оптимизации, мы займемся соотношением «обучение / проверка» только и начнем со случайного перемешивания. Как видите, в приведенной ниже функции используется случайная перестановка размеров групп для выбора аппроксимации требуемой пропорции без учета слоев. Процедура останавливается, когда набор для проверки превышает требуемую емкость.
Теперь, когда у нас есть решение, мы можем попробовать его улучшить. Мы сделаем это, внеся небольшие изменения в решение, по сути перевернув биты в массиве решений. Но как мы узнаем, что мы улучшаем решение? Как мы измеряем улучшения? Введите функцию стоимости.
Функция стоимости
Функция стоимости измеряет расстояние от существующего решения до теоретического оптимума. Мы знаем этот оптимум из постановки задачи и хотим сгенерировать массив решений, который наилучшим образом соответствует пропорциям разделения и слоев. Приведенная ниже функция вычисляет стоимость, связанную с данным массивом решений, и JIT-компилируется с Numba для повышения производительности.
В процессе оптимизации все решения оцениваются с использованием указанной выше функции стоимости, при этом более низкие затраты соответствуют лучшим решениям. Как видите, функция стоимости учитывает разницу между пропорцией разделения запрошенного набора данных и пропорцией из оцененного решения. Затем он делает то же самое с разницей между слоями проблемы и пропорциями слоев решения.
Теперь, когда у нас есть функция стоимости, как с ее помощью генерировать решения для оценки? Мы начинаем с разработки начального решения, а затем повторяем его.
Процесс поиска
Процесс поиска итеративно генерирует новые решения на основе предыдущего и оценивает их. В этом конкретном случае мы создаем решение, переворачивая бит вектора решения, тем самым перемещая группу в набор проверки или из него. Мы должны быть осторожны, чтобы не создавать ранее сгенерированные решения, иначе мы отправим процесс поиска оптимизации в бесконечный цикл.
Чтобы избежать циклов, делаем то же, что и Ариадна в своем лабиринте; мы отмечаем проторенный путь. Вместо создания потока мы используем набор Python для хранения посещенных состояний нашего пространства поиска. Но сохранение всего массива состояний для каждого шага не будет ни эффективным, ни быстрым с точки зрения памяти. Чтобы ускорить тесты включения набора, мы должны сначала преобразовать массив состояний в более компактное представление - строку. Python довольно эффективно обрабатывает строковые хэши, и мы также получаем выгоду от сжатия представления состояния. Функция ниже показывает, как преобразовать массив состояний в строку ASCII. Обратите внимание, что процедура использует только шесть бит на символ и JIT-компилируется с использованием Numba.
Действующее решение
Мы всегда держим под рукой лучшее на данный момент решение, действующее решение, и используем его в качестве последнего, когда процесс оптимизации завершается. Когда в процессе генерируется лучшее решение с меньшими затратами, он заменяет действующего оператора лучшим. Таким образом, у оптимизатора всегда есть готовый ответ, независимо от выбранных критериев завершения.
В процессе оптимизации генерируются новые решения путем изменения одного бита ранее сгенерированного решения с использованием определенного критерия. Здесь мы рассмотрим два разных подхода к этому процессу. Первый подход использует эвристику для генерации нового решения и очень похож на методы, используемые в алгоритмах информированного поиска. Второй подход использует градиент функции стоимости для определения следующего наилучшего решения и по духу аналогичен градиентному спуску.
Эвристический подход
Основной цикл оптимизатора на основе эвристики начинается с создания списка возможных производных состояний путем переворота всех битов родительского решения. Затем он отфильтровывает уже посещенные состояния, используя набор, в котором хранятся массивы двоичных состояний в строковой кодировке (например, список запретов без владения). Как видно из приведенной ниже функции, создание новых решений - это просто итерация по битовому массиву, переворачивание каждого из них и фильтрация уже изученных решений.
Затем процедура оценивает каждое из вновь созданных состояний с помощью функции стоимости и соответствующим образом сортирует их. Пришло время процессу выбрать следующего кандидата для расширения, и именно здесь он использует эвристику. Проще говоря, лучший кандидат - это тот, у кого самые низкие затраты. Такой подход заставляет процесс оптимизации искать лучшее решение, более близкое по стоимости к предыдущему. В задачах дискретной оптимизации обычно находят близкие друг к другу локальные минимумы, поэтому такой подход имеет смысл. В специальной литературе это называется «интенсификация».
Важно отметить, что мы не обязательно улучшаем существующее решение, выбирая самое дешевое решение. Мы просто выбираем самое дешевое решение из сгенерированного списка, но оно может иметь более высокую стоимость, чем наше лучшее на данный момент. Поступая так, мы участвуем в так называемом «подъеме на холмы». В качестве аналогии вы можете представить себе лыжника, поднимающегося на небольшой холм в надежде найти более крутой склон, чтобы спуститься на противоположной поверхности.
Однако, применяя эту стратегию, мы рискуем застрять в местной высокогорной долине. Процедура оптимизации отслеживает, как часто она идет в гору, и после заранее определенного количества неудачных попыток снизить затраты традиционного оператора она начинает действовать иначе. Возвращаясь к аналогии с лыжницей, представьте, что ей скучно искать хороший спуск, и она вызывает свой частный вертолет, чтобы отвезти ее на соседний и более многообещающий пик. Если повезет, она может найти более захватывающий трек.
Эта стратегия называется «диверсификацией»: вместо использования наименьших затрат процедура поиска будет выбирать наибольшую, когда обнаруживает впадину. Эта стратегия позволяет процессу оптимизации искать различные пути вплоть до неуловимого глобального минимума.
Ниже представлена функция, решающая задачу оптимизации с помощью эвристического поиска.
Как видите, на каждой итерации функция генерирует список возможных решений и использует только одно в качестве следующего хода. Для задач с большим количеством групп этот подход станет слишком медленным для практического использования.
Градиентный подход
Мы можем попытаться выбрать лучшее расширение, следуя градиенту функции стоимости в качестве альтернативы предыдущему подходу. Глядя на функцию стоимости, мы можем быстро получить ее градиент. В приведенном ниже коде вычисляется градиент функции стоимости как вектор. Обратите внимание, что вектор градиента просто содержит разницу в счетах по каждому измерению стоимости.
Теперь мы можем использовать этот вектор для поиска наилучшей модификации решения. Помните, что мы просто перемещаем группы между наборами поездов и проверок, поэтому мы хотим использовать градиент стоимости, чтобы определить, какое перемещение больше всего повлияет на значение затрат. Обратите внимание, что первый компонент вектора затрат (строка 14 выше) является положительным, когда количество проверочных наборов ниже ожидаемого значения. Чтобы снизить стоимость, мы должны добавить еще одну группу в набор для проверки. То же верно и для пластовых компонентов. Если процесс оптимизации получает вектор градиента стоимости с положительными элементами, он должен выбрать одну группу из обучающего набора и переместить ее в набор проверки. С другой стороны, если все компоненты градиента стоимости имеют отрицательные значения, мы должны удалить группу из проверочного набора и вернуть ее в обучающий набор. Решение для всех других промежуточных случаев будет зависеть от подобия векторов, как поясняется ниже.
Как должна процедура оптимизации выбирать лучшую группу для передачи между наборами данных? Здесь мы должны использовать подобие векторов, чтобы сопоставить вектор градиента стоимости с каждым вектором из матрицы задачи, и выбранной метрикой было косинусное подобие.
Сходство косинуса происходит из определения внутреннего произведения между двумя векторами и является максимальным, когда оба вектора указывают в одном направлении, и минимальным, когда противоположны. В приведенном ниже коде реализуется вычисление косинусного сходства с адаптацией к нашей задаче, меняя знак векторов группы проверки.
Изменяя знак векторов проверки (строка 11 выше), алгоритм гарантирует, что они будут ближе к градиенту стоимости, который указывает в обратном направлении движения от набора обучающих данных.
Теперь мы можем использовать косинусное подобие для генерации следующего хода. В приведенном ниже коде содержится функция, которая производит следующее лучшее решение на основе критерия косинусного сходства.
Функция генерации решения вычисляет вектор оценок подобия косинуса, вычисленных между каждым из векторов группы из матрицы задачи и вычисленным вектором градиента стоимости. Следующее лучшее решение соответствует переворачиванию бита вектора проблемы с наивысшим баллом. Обратите внимание, что для диверсификации мы используем самый низкий балл.
Код
Весь код для этой статьи доступен в сопутствующем репозитории GitHub. Он находится в одном файле Python, который вы можете запустить из командной строки или из своей любимой IDE. Существует набор автономных функций и два класса, каждый из которых реализует один из описанных выше подходов к оптимизации. Оба решателя непрерывно повторяют цикл, пока не достигнут критерий остановки. В настоящее время они используют в качестве критерия остановки минимальное значение стоимости или максимальное количество итераций без улучшения.
Поиск Решатель
Метод решателя этого класса расширяет текущее решение до всех допустимых состояний. Затем он ранжирует их в соответствии со стоимостью и выбирает самую низкую для следующего расширения. Этот решатель может очень медленно прийти к решению, так как процесс расширения может занять много времени, чтобы выполнить многочисленные проблемы групп. Мы можем обойти этот недостаток, искусственно ограничив количество расширений и добавив немного стохастичности (здесь не делается).
Градиентный решатель
Решатель градиента использует градиент стоимости каждого решения, чтобы выбрать следующий лучший ход. Вместо того, чтобы расширять все допустимые решения, этот решатель переходит «прямо к делу», выбирая лучшее решение для разработки. Как объяснялось ранее, этот решатель использует косинусное сходство, чтобы найти наилучшее соответствие между вектором градиента стоимости и векторами группы. Такой дизайн значительно ускоряет работу этого решателя, благодаря чему он превосходит поисковый решатель почти в каждом случае проблемы.
Полученные результаты
Чтобы сравнить производительность обоих методов, я провел серию экспериментов, варьируя количество групп и измеряя время выполнения. Для каждого размера группы я выполнил код для обоих методов десять раз и взял среднее значение за секунды. Помимо количества групп, я сохранил все остальные параметры постоянными.
На следующей диаграмме показано, как работают оба метода оптимизации во времени в зависимости от количества групп в определении проблемы. Как видите, эвристический оптимизатор работает суперлинейно, а градиент выглядит линейным.
Обратите внимание, что эти результаты должны лишь дать вам представление о производительности обоих методов, поскольку качество оптимизации (измеренное как окончательная стоимость) сильно различается. Лучшее сравнение производительности, вероятно, повлечет за собой ограничение, заключающееся в том, что оба метода сообщают результаты в узком интервале. Тем не менее, я всегда предпочитаю использовать метод градиента эвристике.
Заключение
В этой статье мы рассмотрели проблему разделения сгруппированного набора данных машинного обучения на обучение и проверку при соблюдении как требуемой пропорции разделения, так и присущего стратификации меток. Мы рассмотрели возможные решения из стандартных библиотек Python, и, когда ни одно из них не было очевидным, мы решили применить свои собственные. Мы сформулировали эту проблему как дискретный процесс оптимизации и разработали два возможных решения для нее. Первое решение основывается на информированном поиске с использованием эвристики, а второе использует градиент функции стоимости для минимизации стоимости решения. Подход на основе градиента показывает гораздо лучшую производительность выполнения, чем эвристический.
Будущая работа
Как я уже говорил ранее, работа, которую вы видите здесь, все еще является проверкой концепции. Я показал, как решить стратифицированное разбиение сгруппированного набора данных, используя подход дискретной оптимизации. Следующим шагом будет преобразование этого кода в полноценный пакет Python с улучшенной производительностью с помощью компиляции Cython.
Другим возможным расширением этой идеи было бы включение стратифицированного K-Fold расщепления.
Ресурсы
Жоау Паулу Фигейра работает специалистом по анализу данных в tb.lx by Daimler Trucks and Buses в Лиссабоне, Португалия.
