Как проследихме и анализирахме стъпките на над 200 000 души в MIT

Първокурсникът ми имах удоволствието да взема 6.S08 (взаимосвързани вградени системи), който преподава основни концепции на EECS като борд, криптография и алгоритмичен дизайн.

Докато класът беше изключително отнемащ време и предизвикателство, трябва да кажа, че това беше един от най-полезните класове, които съм взел досега. Горд съм, че работих с някои невероятни хора (Извикайте на Ейвъри Ламп, Даниел Гонзалес и Итън Уебър за безкрайните спомени) и заедно изградихме финален проект, който нямаше да забравим.

За окончателния ни проект екипът ни знаеше, че искаме да сме авантюристи. Докато се разхождаше един ден за сладолед, Ейвъри предложи устройство за наблюдение на заявките за WiFi сонда, подобно на това, което правят някои молове. След първоначално проучване и убеждаване към нашите инструктори, решихме да се ангажираме и започнахме да проучваме идеята.

Какво представляват заявките за WiFi сонда?

Повечето хора смятат телефона си за приемник; той се свързва с клетъчни / WiFi мрежи и за всички практически цели е функционален само когато е свързан. Когато обаче телефоните търсят WiFi мрежи, те често изпращат и малки пакети информация, наречени заявки за сонда .

Тези заявки за сонди изпращат откъси от информация като уникален MAC адрес (подобен на пръстов отпечатък), RSSI сигнал (логаритмична сила на сигнала) и списък с предходни SSID, които се срещат. Тъй като всеки телефон ще изпрати един MAC адрес (с изключение на скорошни опити за анонимизиране), ние можем лесно да ги използваме, за да проследяваме учениците, които се разхождат из кампуса.

Събиране на заявки за сонда

Изискванията за нашия окончателен проект включват използването на стандартните компоненти 6.S08, които използвахме през семестъра: микроконтролер Teensy, ESP8266 и GPS модул. Въпреки това, предвид ниската консумация на енергия на ESP8266 (120 mA) и липсата на нужда от силен процесор, решихме да заобиколим Teensy изобщо. Това дизайнерско решение изискваше от нас да се научим как да използваме програмисти на FTDI, за да включим внедряването на Arduino за нашите ESP, но ни даде възможност да продължим със среда, която осигурява силна познаваемост и широчина на библиотеките над вградения AT- команден фърмуер.

През следващите няколко дни имахме доказателство за концепция, което проследяваше заявките за сонди, направени около кампуса; това беше достатъчно, за да смекчи всякакви съмнения от нашите професори и беше игра.

Разработване на POC

Сега, след като знаехме достатъчно за заявките за сонди, за да продължим, нашият екип прекара следващите няколко дни в написването на инфраструктурата, която ще ни позволи масово да събираме тези заявки. Написах Flask + MySQL бекенд за управление на инфраструктурата на устройствата + информация, Ейвъри работеше върху приложение за iOS, за да улесни разполагането на устройства, Даниел Гонзалес създаде красив интерфейс на нашия уебсайт, а Итън създаде платформа за анализ, която трансформира богатството от входящи данни в разбираеми данни с ценна информация.

От хардуерна страна Даниел и Итън спояват нашите ESP8266 на прототипни платки, заедно с някои захранващи модули. Използвахме повторно PowerBoost 1000Cs, дадени ни от класа, за да направим тези устройства изцяло преносими, което имаше хубавия страничен ефект, като ни позволи да извършваме проследяване на някои тесни места.

Забележително е, че динамиката на екипа беше абсолютно прекрасна: смеехме се заедно, учехме заедно и истински се наслаждавахме на компанията на другия. Разполаганията в 4 часа сутринта не бяха толкова лоши, когато е с някои от най-добрите ви приятели.

Разполагане

Като се има предвид, че Итън написа чудесен код за автоматично свързване на устройствата към най-близката незащитена точка за достъп WiFi при зареждане, а Ейвъри написа приложение за актуализиране на местоположението + последно преместени полета (полезно за знанието кои MAC адреси да се свържат с всяко местоположение), внедряване беше толкова лесно, колкото включването на устройствата до близкия контакт и осигуряването на възможност за пинг вкъщи. Внедряването беше доста приятно, ако проявите креативност с него.

Анализиране на данните

След като оставихме проекта да работи за една седмица, събрахме около 3,5 милиона заявки за сонда (!). Бих искал също да отбележа, че всички данни са анонимизирани; по никакъв начин тези данни не са достатъчно фини, за да се определи картографиране от MAC адреси на физически лица, смекчаващи повечето опасения относно поверителността, които нашите инструктори са имали.

Започнахме с прилагането на работата на Итън на всички места, което предизвика незабавно вълнение. Нашите данни ясно показват периодичното поведение зад всяко място.

Освен това, това беше ясно показателно за някои по-големи тенденции в целия кампус: основните артерии (фоайе 10, 26–100) постигнаха пиков трафик около 17:00, докато сградите на ръба на кампуса (като Stata, който има кафене) постигнаха пиков трафик на по обяд. Излишно е да казвам, че с изградената инфраструктура данните стават много по-вълнуващи.

След като разбрахме, че данните за тези тенденции съществуват, започнахме да си задаваме още интересни въпроси:

  • Какво бихме могли да заключим относно марката + разпространение на устройства в MIT?
  • Ами ако моделирахме кампуса си като мрежова графика?
  • Има ли най-честата разходка?
  • По-интересното е, че бихме могли да предскажем къде ще отидат хората след тяхната история на местоположението?

Продължихме да атакуваме тези един по един.

Анализиране на набора от данни

MAC адресите всъщност предоставят множество информация в 6 байта; можем да използваме тази информация, за да определим повече за хората, които ни обикалят. Например всеки производител купува префикс на доставчик за всяко устройство, което произвежда, и ние можем да го използваме, за да определим най-популярните устройства около MIT.

Но има и уловка - неотдавнашните опити да се използва тази технология за проследяване на лица от NSA доведоха много производители към анонимизиране на заявките за сонда. В резултат на това няма да можем да определим напълно разпределението на устройствата, но можем да проучим колко широко разпространено е анонимизирането на заявка за сонда.

Доста иронично е, че всяко устройство, което анонимизира заявките на сонда, всъщност ви информира, че го правят - в анонимизирани устройства локално адресираният бит (вторият най-малко значителен бит) на адреса е зададен на 1. Следователно, стартирането на проста SQL заявка ни позволява знаем, че почти 25% от устройствата анонимизират MAC адресите (събрани 891 131 / 3,570 048 сонда заявки).

Изпълнявайки списъка с префиксите на доставчика (първите три байта на MAC адрес), виждаме, че първите два от осемте адреса са анонимизирани.

  • Локално адресирано „02: 18: 6a“, 162 589 повторения
  • Локално адресирано „da: a1: 19“, 145 707 повторения
  • 74: da: ea от Texas Instruments, 116 133 случая
  • 68: c4: 4d от Motorola Mobility, 66 829 повторения
  • fc: f1: 36 от Samsung, 66 573 повторения
  • 64: bc: 0c от LG, 63 200 повторения
  • ac: 37: 43 от HTC, 60 420 случая
  • ac: bc: 32 от Apple, 55 643 повторения

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

Предсказване на бъдещи местоположения

След като моделирахме разходките на учениците като мрежова графика, разбрахме, че можем лесно да изчислим вероятността да отидем до друг възел, като се има предвид възела, в който са били преди. Освен това разбрахме, че тази графика може лесно да бъде моделирана като верига на Марков. При първоначален набор от върхове, къде биха отишли ​​те след това?

Това обаче представляваше значително предизвикателство: нашата база данни имаше малко разбиране кога започва разходката и кога разходката приключва. Това беше малко повече от сваляне на координати с местоположения и времеви клейма . Ако разглеждате разходките ръчно, беше ясно кога някои започват, а други свършват, тъй като времената ще бъдат доста далеч един от друг.

Това може да се разбере чрез разглеждане на изображението по-горе. Например този човек очевидно не е ходил от Stata до сградата на Whitaker, тъй като те са в различни дни. Нашата база данни обаче няма представа за това и тъй като всички последващи опити за използване на тези данни биха довели до грешни резултати .

Интересното е, че ако преструктурираме това като проблем на клъстерирането на данни от времеви редове , става много интригуващо. Ами ако има начин да се групират времевите марки, така че да можем да идентифицираме различните „разходки“, на които е ходил студент? Имайки предвид неотдавнашния шум около групирането на данни от времеви редове, реших, че това ще бъде забавен проект, с който да започна моето лято.

Анализиране на базата данни в разходки

За да разбера най-добре как да групирам данните, трябваше да разбера по-добре времевите марки. Започнах с начертаване на клеймото за време върху хистограма, за да разбера по-добре разпределението на данните. Достатъчно радостно, тази проста стъпка ми помогна да стигна до мръсотия: оказва се, че честотата на заявките за сонда по отношение на разстоянието от ESP8266 грубо следва гауссово разпределение, което ни позволява да използваме модел на гаусова смес. По-просто казано, бихме могли просто да използваме факта, че времевите марки ще следват това разпределение, за да изтласкат отделните клъстери.

Последващият проблем беше, че на GMM трябва да се каже колко клъстера да използва , той няма да го идентифицира сам. Това представлява сериозен проблем, особено когато се има предвид, че броят на разходките, които е извършил всеки индивид, е силно променлив. С удоволствие успях да използвам информационния критерий на Bayes, който количествено оценява модели по отношение на тяхната сложност. Ако оптимизирах да минимизирам от BIC по отношение на размера на модела, бих могъл да определя оптимален брой клъстери, без да прекалявам; това обикновено се нарича техника на лакътя.

BIC работеше сравнително добре в началото, но би наказвал прекалено много хора, които са ходили на много разходки, като подчислява броя на възможните клъстери . Сравних това със Silhouette Scoring, който оценява клъстер, като сравнява разстоянието между клъстерите и разстоянието до най-близкия клъстер. Достатъчно изненадващо, това осигури много по-разумен подход за групиране на данни от времеви редове и избегна много от клопките, които BIC срещна.

Мащабирах капката си DO, за да оставя това да работи за няколко дни, и разработих бърз Facebook бот, който да ме уведоми при завършване. Като се махна това, бих могъл да се върна към работата, като прогнозирам следващите стъпки.

Разработване на верига на Марков

Сега, когато сме сегментирали огромна поредица от заявки за сонда в отделни разходки, може да развием верига на Марков. Това ни позволи да предскажем следващото състояние на събитията предвид предходните.

Използвах библиотеката на Python Markovify, за да генерирам модел на Марков, получил корпус от предишната ни стъпка, който съкрати сравнително времето за разработка.

Включих примерна верига на Марков, генерирана по-горе; това всъщност представлява разходката от напускащ лекция студент (26–100 е лекционна зала) и отивайки до общежитието му! Наистина е вълнуващо, че компютърът успя да се възползва от това и да генерира подобна разходка. Някои местоположения се повтарят, тъй като всяко записано местоположение всъщност представлява наблюдение. Следователно, ако дадено място се появява повече от други, това просто означава, че индивидът е прекарал повече време там.

Въпреки че това е примитивно, възможностите са доста вълнуващи . какво, ако можем да използваме тази технология, за да създадем по-интелигентни градове, да работим срещу задръстванията и да осигурим по-добра представа за това как можем да успеем да намалим средното време за ходене? Възможностите за наука за данни в този проект са безкрайни и аз съм изключително развълнуван да ги преследвам.

Заключение

Този проект беше един от най-вълнуващите акценти в първата ми година и аз се радвам невероятно, че го направихме! Бих искал да благодаря на моите невероятни връстници от 6.S08, на наставника ни Джо Щайнмайер и на целия персонал от 6.S08, който направи това възможно.

Научих много, докато използвах този проект, от това как да клъстерирам данни от времеви редове, до инфраструктурата, необходима за проследяване на заявките за сонди в кампуса. Прикачих още някои стоки по-долу от приключенията на нашия екип.