Интересно, откуда появилась задача в такой формулировке. Я, наверное, повторю предыдущих авторов, но
- формула либо накапливает серьезную ошибку, либо восстанавливает в промежуточных вычислениях всю сумму;
- если поддерживать сумму чисел F_1, сумму квадратов F_2 и общее количество, то среднее квадратичное вычисляется по формуле F_2 / n - F_1^2 / n^2;
- откуда берутся ограничения? Даже если чисел 2^64, их размер 64 бита, можно обойтись длинкой на 256 бит. Кажется, это самая большая интрига в вопросе.
Так можно сказать, но тогда при чем тут машинное обучение. Любая программа, которая что-то получает на вход и выдает на выход, должна понять что-то про вход.
Можно еще попробовать воспользоваться максимальным отклонением сигнала. Т.е. если мы условно знаем, что шум дает прирост амплитуды не более 200 и точно знаем, что пульс опускается до нуля. То использовать в качестве порого не относительные, а абсолютные значение: 0 и 200.
У вас же две стадии обработки данных. Сначала все данные, включая категории, превращаются в числа. Потом вы думаете, что делать с пропущенными данными.
Кстати, по поводу среднего стоит помнить такую проблему. Вот у вас есть, например, граждане, которые родились в 87, 90, 93 году примерно в равных пропорциях. Пусть треть граждан не указала свой год рождения. Если пользоваться средним, мы вбросим треть граждан, которые родились в 90-году. Это, скажем, создает некоторую системную ошибку. Это не значит, что такой подход надо немедленно выкинуть, но просто стоит знать, если итоговые результаты не устроят.
Первый map принимает на вход пары С -> P и эмитит две пары: C -> (P, +1), P -> (C, -1). Второе число -- это расстояние со знаком. В сторону корня положительное.
Reduce собирает для каждой вершины её окрестность. Работать будет за O(n log n), но что поделаешь.
Дальше каждый map принимает на вход окрестность. Она может иметь вид несколько детей -> родитель -> несколько предков. Оставляем самого далекого предка (G, d_g). Выкидываем родителя. Для каждого ребенка (C, -d_c) эмитим пары С -> (G, d_g + d_c) и G -> (C, -(d_g + d_c)).
Reduce снова собирает окрестность.
Через log n операций мы останавливаемся и выкидываем все пары, которых расстояние больше чем n.
Может я путаю, но это должно по количеству операций занимать O(n log^2 n).
Вопрос же в том, как само расстояние определять.