В этом посте описывается KneeFinder, инструмент, который можно использовать для поиска точки колена/локтя.

Если вы попали сюда, возможно, вы пытаетесь настроить какой-то параметр алгоритма.

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

Лучшее определение (из Satopää, Albrecht, Irwin, and Raghavan, 2011, p.1) определяет точку колена как точку, где

«относительные затраты на увеличение [или уменьшение, NdC] некоторого настраиваемого параметра больше не стоят соответствующего выигрыша в производительности»

Хотя причина, по которой используется метод колена/локтя, ясна, методологии, используемые для его развертывания, меняются в зависимости от областей и алгоритмов. Что у них общего, так это заключительная часть: имея параметр VS результата графика, найдите оптимальное значение для этого параметра.

В этом посте объясняется, как найти его простым способом с помощью простого и надежного инструмента.

Пример

Скажем, у нас есть следующие данные:

Что обычно делают в такой ситуации, так это берут в качестве оптимального параметра p= 2 или p=3, следуя их смыслу. Проблема в том, что смысл одного может отличаться от смысла другого, и оба они не могут быть автоматизированы.

KneeFinder

Здесь мы предлагаем эмпирическое определение точки колена:

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

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

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

Разработаем наше определение графически:

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

Вот оно: оптимальное значение для вашего параметра равно двум.

Вы можете найти KneeFinder по этой ссылке. Обратите внимание, что он все еще находится на стадии тестирования, поэтому, если вы найдете проблему, пожалуйста, заполните ее на GitHub.

Внутри алгоритма

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

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

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

Спасибо за чтение!