В деревьях решений для работы с непрерывными признаками нужно найти оптимальный порог разделения.
Порог — это число, которое делит данные на две части: значения ≤ порога идут влево, значения > порога — вправо.
Пример:
Значения: [1, 3, 5, 7, 9]
Метки: [0, 0, 1, 1, 1]
Если выбрать порог = 4:
- Левая часть (≤ 4): значения [1, 3], метки [0, 0]
- Правая часть (> 4): значения [5, 7, 9], метки [1, 1, 1]
Это хорошее разделение! Левая часть чистая, правая чистая.
Алгоритм поиска лучшего порога:
1. Отсортируй уникальные значения признака
2. Для каждой пары соседних уникальных значений:
- Порог = среднее этих двух значений
- Раздели данные по порогу
- Посчитай информационную выгоду
3. Верни порог с максимальной выгодой
Реализуйте алгоритм поиска лучшего порога.
Формат входных данных
- Первая строка: N — количество элементов
- Вторая строка: N вещественных чисел — значения признака
- Третья строка: N целых чисел (0 или 1) — метки классов
Формат выходных данных
- Первая строка: оптимальный порог (вещественное число, 4 знака после запятой)
- Вторая строка: информационная выгода (вещественное число, 4 знака после запятой)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 3 5 7 9
0 0 1 1 1
|
4.0000
0.9710
|