Ефективна оцінка медіани

    Отже, у Вас є якийсь потік даних. Великий такий потік. Або вже готовий набір. І хочеться визначити якісь його характеристики. Алгоритм визначення мінімального і максимального значення можуть придумати навіть не програмісти. Обчислення середнього вже трохи складніше, але теж не представляє ніяких труднощів — знай підраховуй собі суму да инкрементируется лічильник на кожне нове значення. Середньоквадратичне відхилення — все те ж саме, тільки числа інші. А як щодо медіани?
 
Для тих, хто забув, що це таке, нагадую — медіана (50-й перцентиль) вибірки даних — це таке значення, яке ділить цю вибірку навпіл — дані з однієї половини мають значення не менше медіани, а з другого — не більше. Цінність її полягає в тому, що її значення не залежить від величини випадкових сплесків, які можуть дуже сильно вплинути на середнє.
 
Строго кажучи, з визначення випливає, що для обчислення точного значення медіани нам потрібно зберігати всю вибірку, інакше немає ніяких гарантій, що ми нарахували саме те, що хотіли. Але для безперервних і великих потоків даних точне значення все одно не має великого сенсу — зараз воно одне, а через нових 100 відліків — вже інше. Тому ефективний метод оцінки медіани, який не вимагатиме багато пам'яті і ресурсів CPU, і буде давати точність порядку одного відсотка або краще — якраз те що потрібно.
 
Відразу попереджу — запропонований метод має низку обмежень. Зокрема, він дуже погано працює на відсортованих вибірках (але зате дуже добре працює на більш-менш рівномірно розподілених). Далі розглядається більш простий випадок невід'ємних значень, для загального випадку потрібні додаткові обчислення.
 
Ідея методу полягає в тому, щоб побудувати такий процес обчислення, який буде сходитися до дійсного значення медіани. Якщо ми вже обробили якоюсь обьем даних і маємо якусь оцінку медіани, то про надходження нового обьема (з майже такою ж медианой, що важливо) наша оцінка повинна бути покращена. Якщо більш точно — то оцінка повинна бути покращена з більшою ймовірністю, ніж погіршена.
 
Можна використовувати різного роду вікна обчислення медіани, наприклад, порахувати точну медіану останніх 100 значень, і усереднити з постійно уменьшающимся вагою з попередньою оцінкою. Такий метод буде добре працювати, але є набагато більш легкий і практично такий же точний. А саме — просто зрушувати поточну оцінку медіани до нового значенням на якусь невелику константну дельту. У разі, якщо попередня оцінка була не точною, то при обробці нового обсягу даних вона наблизиться до дійсного значення, тобто стане більш точною. А якщо оцінка вже й так точна, то на обробці нового обсягу даних на половині значень буде зрушення в одну сторону, а на іншій половині — в іншу, в результаті оцінка повернеться до точного значення.
 
Важливо, що дельта повинна мати однакове абсолютне значення для зрушень як у більшу, так і в меншу сторону, інакше ми отримаємо не 50-й перцентиль. Але тепер постає проблема підбору значення дельти — надто маленьке дасть повільну збіжність, а надто велике — отримаємо велику погрішність, особливо якщо дельта порівнянна з самим значенням медіани. Автоматичне обчислення дельти вже позбавляє її звання константи, але це й неважливо, якщо в результаті ми отримаємо кращий результат.
 
Має сенс робити дельту постійно зменшується, щоб поліпшити збіжність. Але чи не занадто швидко, інакше, за несприятливих умов оцінка ризикує ніколи не наздогнати дійсне значення медіани. Коефіцієнт 1/count підходить ідеально — він легко обчислюється, і ряд sum (1 / n) — розходиться, так що в кінці-кінців оцінка досягне дійсної медіани, якою б не поганий вона була спочатку.
 
Прив'язувати значення дельти до поточної оцінки медіани — ризиковано. У невдалих умовах занадто заниженою оцінкою буде складно рости. Найкраще обчислювати дельту виходячи з іншої цілком стійкою характеристики вибірки — середнього значення. З коефіцієнтом 1/count значення дельти буде постійно зменшуватися (за винятком нечисленних випадків, коли поточне середнє виросте занадто сильно в порівнянні з попереднім). Для даних, які можуть приймати не тільки невід'ємні значення, такий підхід вже не спрацює, але ми можемо легко вийти з положення, якщо вважати два середніх — позитивних і негативних значень, і використовувати суму їх абсолютних значень.
 
Підсумковий алгоритм оцінки медіани майже такий же простий, як і алгоритм обчислення середнього значення:
 
sum += value
count ++
delta = sum / count / count        // delta = average/count
if value < median {
  median -= delta
} else {
  median += delta
}

 
Похибка і швидкість збіжності, на мою думку, у нього відмінна — на вибірці в 100 значень похибка зазвичай близько 10-20%, на 1000 — вже близько 1-3%, і далі похибка зменшується ще більше.
 
Для бажаючих самостійно оцінити якість роботи алгоритму — невеликий скриптик на perl-е:
 
#!/usr/bin/perl -s

$N = shift || 100000;
for (1 .. $N) {
  push @a, (rand(1)*rand(1))**2;
}
@t = sort { $a <=> $b } @a;
$MEDIAN = $t[$N/2-1];

median_init();
for (@a) {
  median_update($_);
}

$diff = ($MEDIAN-$median)/$MEDIAN*100;
$avg = $sum/$count;

print "Real:\t\t$MEDIAN
Estimated:\t$median
Difference:\t$diff \%

Average: $avg
";

sub median_init() {
  $count = $sum = $median = 0;
}
sub median_update($) {
  $value = $_[0];
  $sum += $value;
  $count ++;
  $delta = $sum / $count / $count;
  if($median <= $value) {
    $median += $delta;
    $s2 = '+';
  } else {
    $median -= $delta;
    $s2 = '-';
  }
  if($debug) {
    $s = ($value > $MEDIAN) ? '+' : '-';
    printf "%s %.5f\t%d\t%.7f\t  %s  %e\n", $s, $value, $count, $median, $s2, $delta;
  }
}

    
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.