Hvordan vi spores og analyserede over 200.000 folks fodspor på MIT

Min førsteårs forår havde jeg fornøjelsen at tage 6.S08 (Interconnected Embedded Systems), der lærer grundlæggende EECS-begreber såsom breadboarding, kryptografi og algoritmisk design.

Mens klassen var utrolig tidskrævende og udfordrende, må jeg sige, at det var en af ​​de mest givende klasser, jeg har taget indtil videre. Jeg er stolt over at have arbejdet med nogle utrolige mennesker (råb til Avery Lamp, Daniel Gonzalez og Ethan Weber for de endeløse minder), og sammen byggede vi et sidste projekt, som vi ikke ville glemme.

Til vores afsluttende projekt vidste vores team, at vi ville være eventyrlystne. Mens Avery gik for at få is en dag, foreslog Avery en enhed til at overvåge anmodninger om WiFi-sonde, svarende til hvordan nogle indkøbscentre gør. Efter nogle indledende undersøgelser og overtalelse over for vores instruktører besluttede vi at begå og begyndte at undersøge ideen.

Hvad er anmodninger om WiFi-sonde?

De fleste mennesker betragter deres telefon som en modtager; den opretter forbindelse til mobil- / WiFi-netværk, og til alle praktiske anvendelser er den kun funktionel, når den er tilsluttet. Men når telefoner søger efter WiFi-netværk, sender de ofte også små pakker med information kaldet probeanmodninger .

Disse probeanmodninger sender uddrag af information, såsom en unik MAC-adresse (svarende til et fingeraftryk), RSSI-signal (logaritmisk signalstyrke) og en liste over tidligere opståede SSID'er. Da hver telefon sender en MAC-adresse (undtagen de seneste forsøg på anonymisering), kan vi nemt udnytte disse til at spore studerende, der går rundt på campus.

Indsamling af probeanmodninger

Krav til vores afsluttende projekt omfattede brug af de standard 6.S08-komponenter, vi brugte i løbet af semestret: en Teensy-mikrokontroller, en ESP8266 og et GPS-modul. I betragtning af det lave strømforbrug på ESP8266 (120 mA) og manglen på behov for en stærk CPU besluttede vi dog at omgå Teensy helt. Denne designbeslutning krævede, at vi lærte at bruge FTDI-programmører til at blinke en implementering af Arduino til vores ESP'er, men det gjorde det muligt for os at fortsætte med et miljø, der gav stærk fortrolighed og en bred vifte af biblioteker over den indbyggede AT- kommandofirmware.

Inden for de næste par dage havde vi et Proof of Concept, der spores probeanmodninger, der blev fremsat omkring campus; dette var nok til at mindske enhver tvivl fra vores professorer, og det var spillet videre.

Udvikling af en POC

Nu da vi vidste nok om sondeanmodninger til at fortsætte, brugte vores team de næste par dage på at skrive infrastrukturen, der gjorde det muligt for os at indsamle disse anmodninger en masse. Jeg skrev en Flask + MySQL-backend til at styre enhedsinfrastruktur + information, Avery arbejdede på en iOS-applikation for at lette implementeringen af ​​enheder, Daniel Gonzalez skabte en smuk frontend til vores hjemmeside, og Ethan oprettede en analyseplatform, der forvandlede den rigdom af indgående data til forståelige data med værdifuld indsigt.

På hardwaresiden lodde Daniel og Ethan vores ESP8266'er på prototype-kort sammen med nogle strømmoduler. Vi genanvendte PowerBoost 1000C'erne, der blev givet os af klassen, for at gøre disse enheder helt bærbare, hvilket havde den gode bivirkning af at tillade os at udføre sporing på nogle stramme steder.

Navnlig var holdets dynamik helt vidunderlig: vi lo sammen, lærte sammen og nød virkelig hinandens selskab. Implementeringer kl. 4 var ikke så dårlige, når det er sammen med nogle af dine bedste venner.

Implementering

I betragtning af at Ethan skrev en smidig kode for automatisk at forbinde enhederne til det nærmeste usikrede WiFi-hotspot ved opstart, og Avery skrev en app for at opdatere placeringen + sidst flyttede felter (nyttigt til at vide, hvilke MAC-adresser der skal tilknyttes hver placering), implementering var lige så let som at tilslutte enhederne til en stikkontakt i nærheden og sikre, at den var i stand til at pinge hjem. Implementering var ret behageligt, hvis du blev kreativ med det.

Analyse af dataene

Efter at have ladet projektet køre i en uge, indsamlede vi ca. 3,5 millioner probeanmodninger (!). Jeg vil også gerne bemærke, at dataene alle er anonymiserede. Disse data er på ingen måde finkornede nok til at bestemme en kortlægning fra MAC-adresser til enkeltpersoner, hvilket mindsker de fleste privatlivets bekymringer, som vores instruktører havde.

Vi begyndte med at anvende Ethans arbejde på alle steder, hvilket medførte øjeblikkelig spænding. Vores data viste tydeligt den periodiske opførsel bag hvert sted.

Desuden var det tydeligt tegn på nogle større tendenser i hele campus: store arterier (lobby 10, 26-100) opnåede spidsbelastning omkring kl. 17, mens bygninger i udkanten af ​​campus (såsom Stata, som har en café) opnåede spidsbelastning ved middag. Det er overflødigt at sige, at med infrastrukturen på plads bliver dataene meget mere spændende.

Når vi først fandt ud af, at dataene for disse tendenser eksisterede, begyndte vi at stille os nogle flere interessante spørgsmål:

  • Hvad kunne vi konkludere om fabrikat + distribution af enheder på MIT?
  • Hvad hvis vi modellerede vores campus som et netværksgraf?
  • Er der en mest almindelig gåtur?
  • Mere interessant kan vi forudsige, hvor folk vil gå videre i betragtning af deres placeringshistorik?

Vi fortsatte med at angribe disse en efter en.

Analyse af datasættet

MAC-adresser giver faktisk en overflod af information i 6 byte; vi kan udnytte disse oplysninger til at bestemme mere om de mennesker, der går omkring os. For eksempel køber hver producent et forhandlerpræfiks for hver enhed, de fremstiller, og vi kan bruge dette til at bestemme de mest populære enheder omkring MIT.

Men der er også en fangst - Nylige forsøg på at bruge denne teknologi til at spore enkeltpersoner fra NSA har ført mange producenter til anonymisering af probeanmodninger. Som et resultat vil vi ikke være i stand til fuldt ud at bestemme fordelingen af ​​enheder, men vi kan undersøge, hvordan udbredt sondeanmodning er anonymisering.

Det er ret ironisk, at enhver enhed, der anonymiserer sondeanmodninger, faktisk informerer dig om, at de gør det - i anonyme enheder er den lokalt adresserede bit (næstmest signifikante bit) af adressen indstillet til 1. Derfor kører en simpel SQL-forespørgsel os ved, at næsten 25% af enhederne anonymiserer MAC-adresser (891.131 / 3.570.048 sondeanmodninger indsamlet).

Når vi kører listen over leverandørpræfikser (de første tre bytes i en MAC-adresse), ser vi, at de to øverste ud af top otte adresser er anonymiserede.

  • Lokalt adresseret “02: 18: 6a”, 162.589 forekomster
  • Lokalt adresseret “da: a1: 19”, 145.707 forekomster
  • 74: da: ea fra Texas Instruments, 116.133 forekomster
  • 68: c4: 4d fra Motorola Mobility, 66.829 begivenheder
  • fc: f1: 36 fra Samsung, 66.573 forekomster
  • 64: bc: 0c fra LG, 63.200 forekomster
  • ac: 37: 43 fra HTC, 60.420 forekomster
  • ac: bc: 32 fra Apple, 55.643 forekomster

Interessant nok, mens Apple er langt den største spiller inden for sonde-anmodning om anonymisering, sender de tilsyneladende tilfældigt den rigtige adresse hver gang imellem. For nogen, der sporer med en så høj frekvens som vores (næsten hvert sekund), er dette problematisk; Vi tjekkede med iPhone-ejende venner og var i stand til at spore deres placering med en skræmmende nøjagtighed.

Forudsiger fremtidige placeringer

Efter modellering af studerendes gåture som et netværksgraf, indså vi, at vi let kunne beregne sandsynligheden for at gå til en anden node givet den node, de tidligere var på. Desuden indså vi, at denne graf let kan modelleres som en Markov-kæde. Givet et indledende sæt hjørner, hvor skulle de gå videre?

Dette udgjorde imidlertid en betydelig udfordring: vores database havde ringe forståelse for, hvornår en gåtur begyndte, og hvornår en gåtur sluttede. Det var lidt mere end et dump af koordinater med placeringer og tidsstempler . Hvis du undersøgte ture manuelt, var det klart, hvornår nogle begyndte, og andre sluttede, da tiderne ville være ret langt fra hinanden.

Dette kan forstås ved at undersøge billedet ovenfor. For eksempel gik denne person tydeligvis ikke fra Stata til Whitaker-bygningen, da de er på forskellige dage. Imidlertid har vores database ingen idé om dette, og da ethvert efterfølgende forsøg på at bruge disse data ville give mangelfulde resultater .

Interessant nok, hvis vi re-strukturerede dette som et problem med klyngning af tidsseriedata , bliver det meget spændende. Hvad hvis der var en måde at samle tidsstemplerne på, så vi kunne identificere de forskellige "gåture", som en studerende gik på? I betragtning af den nylige brummer omkring gruppering af tidsseriedata, regnede jeg med, at dette ville være et sjovt projekt at starte min sommer med.

Analyse af databasen i gåture

For bedst at forstå, hvordan man potentielt kunne klynge dataene, var jeg nødt til bedre at forstå tidsstemplerne. Jeg begyndte med at plotte tidsstemplerne på et histogram for bedre at forstå fordelingen af ​​dataene. Med glæde nok hjalp dette enkle trin mig med at ramme lønningsskidt: det viser sig, at frekvensen af ​​probeanmodninger med hensyn til afstanden fra en ESP8266 omtrent følger en Gaussisk fordeling, hvilket giver os mulighed for at bruge en Gaussisk blandingsmodel. Mere simpelt kunne vi bare udnytte det faktum, at tidsstemplerne ville følge denne fordeling for at udrydde de enkelte klynger.

Det efterfølgende problem var, at en GMM skal få at vide, hvor mange klynger der skal bruges , den identificerer den ikke alene. Dette præsenterede et stærkt problem, især når man overvejer, at antallet af gåture hver enkelt gik på var meget varierende. Med glæde var jeg i stand til at bruge Bayes Information Criterion, som kvantitativt scorer modeller med hensyn til deres kompleksitet. Hvis jeg optimerede til at minimere ved BIC med hensyn til modelstørrelse, kunne jeg bestemme et optimalt antal klynger uden overmontering; dette kaldes almindeligvis albue-teknikken.

BIC fungerede rimeligt godt i starten, men ville alt for straffe personer, der gik mange gåture ved at underberegne antallet af mulige klynger . Jeg sammenlignede dette med Silhouette Scoring, som scorer en klynge ved at sammenligne afstanden inden for klyngen med afstanden til den nærmeste klynge. Overraskende nok tilvejebragte dette en meget mere fornuftig tilgang til gruppering af tidsseriedata og undgik mange af de faldgruber, som BIC stødte på.

Jeg opskalerede min DO-dråbe for at lade denne køre i et par dage og udviklede en hurtig Facebook-bot, der underrettede mig efter afslutningen. Med dette ude af vejen kunne jeg komme tilbage til arbejdet med at forudsige de næste trin.

Udvikling af en Markov-kæde

Nu hvor vi har segmenteret en enorm streng af sondeanmodninger i separate gåture, kan vi udvikle en Markov Chain. Dette tillod os at forudsige den næste tilstand af begivenheder givet de foregående.

Jeg brugte Python-biblioteket Markovify til at generere en Markov-model givet et corpus fra vores tidligere trin, hvilket forkortede udviklingstiden sammenligneligt.

Jeg har medtaget en prøve Markov Chain genereret ovenfor; dette repræsenterer faktisk turen fra en studerende, der forlader forelæsning (26–100 er en forelæsningssal) og går til hans sovesal! Det er virkelig spændende, at en computer var i stand til at hente dette og generere en lignende gåtur. Nogle placeringer gentages, det er fordi hver registrerede placering faktisk repræsenterer en observation. Derfor, hvis en placering vises mere end andre, betyder det simpelthen, at personen tilbragte mere tid der.

Selvom dette er primitivt, er mulighederne ret spændende . hvad hvis vi kunne udnytte denne teknologi til at skabe smartere byer, arbejde mod overbelastning og give bedre indsigt i, hvordan vi muligvis kan reducere gennemsnitlige gåtider? Datavidenskabsmulighederne i dette projekt er uendelige , og jeg er utrolig begejstret for at forfølge dem.

Konklusion

Dette projekt var et af de mest spændende højdepunkter i mit førsteårsår, og jeg er utrolig glad for, at vi gjorde det! Jeg vil gerne takke mine utrolige 6.S08-jævnaldrende, vores mentor Joe Steinmeyer og alle de 6.S08-medarbejdere, der gjorde dette muligt.

Jeg har lært meget, mens jeg forfølger dette projekt, fra hvordan man klynger tidsseriedata til den nødvendige infrastruktur til sporing af sondeanmodninger omkring campus. Jeg har vedhæftet nogle flere varer nedenfor vores teams eventyr.