?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

Previous Entry Share Flag Next Entry
Кусочек голограммы. Обработка логов.
nyaload
_winnie
Закон больших чисел - какое-то волшебство.

Взять две московские школы - в обоих будет 2% Александров и 2% Маш, плюс-минус несколько человек. Хотя школы разные! Что бы узнать сотношение мнений толпы людей - достаточно опросить случайную сотню из толпы. Причем сотни будут каждый раз разные, а пропорции мнений - одинаковые!

При обработке логов - не обязательно использовать мега-кластер что бы обработать логи. Достаточно взять случайную выборку в 1млн элементов, и все события которые происходят хотя бы раз на тысячу - там будут. Можно с точностью до долей процентов получить разбиение на типы событий. Если интересует бинарный признак, можно вообще только 100 записей выдернуть.

Случайная выборка - очень мощный инструмент в обработке данных. Можно взять кусочек голограммы, и в ней будет полное изображение, только более размытое. Что бы посчитать количество рук и ног - достаточно фотографии человека 20x15 пикселей, а не 1024x768. Точно так же можно взять кусочек логов в 1000, 1млн записей - и часто этого достаточно что бы посчитать нужную статистику. Причем на локальном компьютере, любым скриптом, в любой програме и операционной системе без лагов доступа к общему кластеру. При социологическом опросе страны с населением в сотню миллионов человеков - этот инструмент использутся постоянно, а иначе никак. А вот при обработке данных из логов - почему-то часто обрабатываются целиком все логи, вместо малой части.

Сражу скажу когда такой способ работает неправильно - когда ищем соотношение каких-то двух редких событий, настолько редких что при случайной выборке - будет деление нуля на ноль. Или если мы считаем то, что портится при случайной выборке (напр. доля уникальных записей).

Рассмотрим два типа логов:
1) события в логах не сгруппированы, одно событие - одна запись:

Выборку можно сделать так: awk 'rand() < 0.0001'

2) события сгруппированы по признаку, и посчитаны, напр.
Маш: 3 штуки
Александров: 2 штуки
Степанов: 1 штука
Зинаид: 1 штука
Алексеев: 1 штука

Из такого лога выборку можно сделать таким скриптом:
awk -F '\t' -f sample_by_field.awk

BEGIN{
#srand()
SAMPLE_FREQ = 1e-6; #какую часть логов оставить.
SAMPLE_FIELD=2; #номер поля со штуками
OFS="\t";
}

{
if ($SAMPLE_FIELD == "1") { #оптимизация под самый частый случай
if (rand() < SAMPLE_FREQ)
print $0;
} else {
N = $SAMPLE_FIELD + 0;
sum = 0;
for (i = 0; i < N; ++i) {
if (rand() < SAMPLE_FREQ)
sum += 1;
}
if (sum) {
$SAMPLE_FIELD = sum;
print $0;
}
}
}
_Winnie C++ Colorizer


Суммирование rand() вместо использования биноминального распределения может показаться неоптимизированным, но у меня на событие которое происходит миллион раз - так же есть и миллион уникальных событий, поэтому нет смысла оптимизировать.

Tags: , ,


  • 1
Назови это "метод Лас-Вегаса". ;)

Ну раз Лас-Вегас занят - бери Монте-Карло!

Мне кажется, ты не прав с аналогией. Аналогии вообще вредная штука, не знаю, когда они могут быть полезны.
Надо бы проверить на двух реальных школах, но мне кажется, что проценты в школах в Южном Бутово и в Матушкино-Савёлках будут разные. Хотя бы потому, что в Зеленограде живёт в разы меньше приезжих из республик Северного Кавказа и стран Средней Азии, а они редко называют своих дочерей Машами.

Да, школы неудачный пример, именно потому что район не является случайной выборкой...

Аналогии полезны для быстрого создания гипотез, изобретения новых методов.

Например, делаем аналогию между человеком и компьютером. Начинаем смотреть, есть ли какие-то полезные методы в медицине, которые можно применить в обслуживании компьютеров. Если вдруг надо обслуживать 100000 компьютеров, то как организованы большие поликлиники. Естественно, аналогии будут где-то расходится (сломаный компьютер иногда проще выкинуть, чем починить, но не человека), а где-то - быть похожими (если надо диагностировать болезнь/причину поломки).

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

Какой вид тренда по времени?

Вроде случайной выборке будет пофиг на тренд. Если делаем выборку rand() < 0.01, то всё равно - все события были в понедельник, или размазаны по всей неделе.

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

Очень к месту тут будет вспомнить про reservoir sampling.

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

  • 1