Нахождение порогов с оптимальным балансом классов27.02.2024 14:30

Решим такую алгоритмическую задачу: дано множество точек (x_i,y_i) на плоскости, имеющих метки 0 или 1. Требуется выделить область $\{x\geq a \,\&\, y \geq b\}$ , в которой отношение числа 1 к числу 0 максимально, при условии, что число нулей в этой области не меньше заданного числа.

Упорядочим все точки по убыванию y_i . Будем поддерживать структуру данных, которая ответит на вопрос: сколько всего чисел, добавленных в структуру, не меньше заданного числа? Тогда, если добавлять в эту структуру координаты x_i всех точек, а также поддерживать упорядоченное множество значений x-координат точек с меткой 1, то алгоритм будет следующим. Для каждой просмотренной точки с меткой 1 найти количество точек с x-координатами, превосходящими координату текущей точки. Количество всех просмотренных точек с меткой 1, попавших в эту область, находится как индекс текущей точки в упорядоченном множестве.

Для реализации упорядоченного множества с функциями добавления элемента и поиска количества элементов, не меньших заданного (нахождение индекса) применяется сбалансированное дерево двоичного поиска, а точнее, дерево порядковых статистик. В Python упомянутая структура данных реализована в контейнере SortedList из библиотеки sortedcontainers. Сложность алгоритма составила $O(m^2\log^2n)$ , где — число всех точек, — число единиц.

С реализацией можно ознакомиться здесь.

В дальнейшем планируется применить реализованную процедуру для разработки объяснимых методов машинного обучения. А именно, в роли выступит значение одного из признаков, в роли — значение решающей функции в пороговой области (области «спорных точек»). Выделяемой области придается следующий смысл: число — порог дихотомизации признака, — вес при бинаризованном признаке.