Как статистиката ви помага да се справите по-добре, SavePearlHarbor
Още едно копие на пристанището
Как статистиката помага за подобряване на Yandex.Traffic
Принципът на работа на Yandex.Traffic е доста прост. Не е необходима отделна лекция, за да се опише. Приложенията Yandex.Maps и Yandex.Navigator използват GPS, за да определят местоположението на устройството, на което работят, и да изпращат тази информация на сървъра. А той от своя страна въз основа на тези данни създава картина на задръстванията.
Но как точно става това? Сега това е напълно нетривиален процес, който изисква използването на специални алгоритми и отчитане на статистиката. Как да различим бавно напредващ шофьор от пешеходец или велосипедист? Как можете да сте сигурни, че предадената информация е правилна? И най-важното, как да направим данните за трафика възможно най-точни?
Първият проблем, с който трябва да се сблъскате, когато картографирате трафика, е, че GPS технологията далеч не е идеална и не винаги точно определя местоположението. Проследявайки движението на един обект, можете да получите доста странни данни: мигновени движения на доста големи разстояния, пресичане на пътя и др. В резултат на това можем да получим следната картина:
Алгоритъмът трябва да реши какво е било. За да прецизира данните, алгоритъмът ще се опита да намери най-вероятния маршрут, разрешен от правилата. След това трябва да определим какъв вид обект е пред нас? Всъщност в задръстване автомобилите могат да се движат със скоростта на пешеходец и точността на GPS не ни позволява да кажем със сигурност дали даден обект се движи по пътното платно или покрай пътя. Тук могат да се вземат предвид няколко фактора: първо, ако броят на обектите, движещи се с ниска скорост, е достатъчно голям, тогава можем да приемем, че по този път наистина има задръстване и се движат автомобилибавно. Можем също да вземем предвид историята на скоростта на движение на обекта през последните няколко часа. Например, ако даден обект не е развил скорост над 10-15 километра в час през последните четири часа, тогава най-вероятно е пешеходец.
И така, ние определихме скоростта на автомобилите в определена посока за определен период, обработихме ги със специални алгоритми, осреднихме ги и накрая получихме приблизителната обща скорост на потока. Всичко това се случва в реално време и в поток, състоящ се от стотици хиляди машини.
Както казахме по-горе, алгоритмите се занимават с определяне на вида на обекта, скоростта на неговото движение и осредняване на скоростта на потока. Но как да оцените качеството на тяхната работа, за да разберете в каква посока трябва да се движите, за да ги подобрите?
Първият проблем се решава чрез пускане на тестови автомобили в града. Подобно на обикновените потребители, те изпращат данни за своите движения, но в същото време ние знаем точно какви са били реалните условия. След това, въз основа на показателите, можете да сравните реалната карта на задръстванията в определен район с тази, изчислена от алгоритмите, и да определите колко добре системата върши работата си.
Сравнявайки реалната ситуация с резултатите от няколко алгоритъма наведнъж, можем да преценим кой е по-добър. Да кажем, че тестваме нов алгоритъм и го сравняваме със стария. Изпълняваме го на 67 сегмента и получаваме следните резултати:
В 54 случая новият алгоритъм работи по-добре от стария, а в 13 случая - по-зле. По отношение на процента верни отговори и грешки, новият алгоритъм е очевидно по-добър. Сега си представете, че добавяме друг алгоритъм към сравнението. Но той беше каран на по-малък брой сегменти - на шест.
Процентът на попаденията и грешките е дори по-добър от първия. Но струва ли си да се доверитепроверка на толкова малък брой сегменти? За да отговорим ясно на този въпрос, нека се обърнем към статистиката.
Статистика
Първо, нека се занимаваме със случайни стойности. Да кажем, че хвърляме монета три пъти. Главите се приемат за нула, а опашките за единица. Общо можем да получим осем комбинации. Ако преброим сумите на изпуснатите стойности за всяка от комбинациите, ще видим, че екстремните стойности отпадат най-малко и когато се приближаваме до центъра, вероятността се увеличава.
Сега разгледайте пример, в който хвърляме монета N пъти. Ще вземем броя на обектите като k, а броя на комбинациите като C.
Средна и наблюдавана средна стойност
Сега нека поставим друга задача. Нека си представим, че имаме монета и искаме да разберем дали е четна, т.е. дали пада от всяка страна с еднаква вероятност. Ще проверим тази хипотеза, като хвърлим монета. Ако монетата е четна, тогава колкото повече пъти хвърляме монетата, толкова по-близо до средната трябва да бъде най-големият брой резултати. В същото време при малък брой хвърляния вероятността да се направи неправилно заключение е много по-висока.
Защо изобщо говорим за случайност? В края на краищата грешките в алгоритмите за изграждане на карта на задръствания най-често възникват по някакви обективни причини. Но не всички от тези причини са ни известни. Ако знаехме всички причини, бихме могли да създадем идеален алгоритъм и никога повече да не го подобряваме. Но докато това се случи, сме принудени да приемаме някои грешки в алгоритъма като случайни променливи. Затова проверяваме колко по-добре алгоритъмът е започнал да работи, използвайки приблизително същия апарат като хипотезата с плоска монета. Само в този случай като основна хипотеза приемаме, че алгоритъмът изобщо не се е променил. И след това приС помощта на прекарването на данните през алгоритъма ние определяме дали има изкривявания в една или друга посока. И точно както в случая с монета, важно е да има възможно най-много такива пускания, в противен случай вероятността да направите грешка ще бъде твърде висока.
Ако се върнем към нашия пример с два алгоритъма, тогава можем да кажем с увереност, че първият нов алгоритъм е по-добър от стария. Но вторият буди повече съмнения, въпреки факта, че процентът на верни отговори и грешки е по-добър. Може би наистина работи по-добре, но трябва да се направят повече тестове, за да се уверите в това.