Hogyan követtük nyomon és elemeztük több mint 200 000 ember lépteit az MIT-nél

Első tavaszomon örömmel vettem a 6.S08-at (összekapcsolt beágyazott rendszerek), amely olyan alapvető EECS-fogalmakat tanít, mint a kenyérsütés, a rejtjelezés és az algoritmikus tervezés.

Bár az osztály hihetetlenül időigényes és kihívásokkal teli volt, azt kell mondanom, hogy ez volt az egyik leghálásabb osztály, amelyet eddig vettem. Büszke vagyok arra, hogy hihetetlen emberekkel dolgoztam együtt (Kiáltás Avery Lampnak, Daniel Gonzaleznek és Ethan Webernek a végtelen emlékekért), és közösen felépítettünk egy végső projektet, amelyet nem felejtünk el.

A végső projektünkre csapatunk tudta, hogy kalandosak akarunk lenni. Séta közben, hogy egy nap fagylaltot kapjon, Avery javasolt egy eszközt a WiFi szondakérelmek figyelemmel kísérésére, hasonlóan ahhoz, ahogyan egyes bevásárlóközpontok teszik. Néhány kezdeti kutatás és az oktatóinkkal való meggyőzés után úgy döntöttünk, hogy elkötelezzük magunkat, és elkezdtük kutatni az ötletet.

Mik azok a WiFi szondakérések?

A legtöbb ember vevőnek tartja a telefonját; csatlakozik celluláris / WiFi hálózatokhoz, és minden gyakorlati felhasználásra csak akkor működik, ha csatlakozik. Amikor azonban a telefonok WiFi hálózatokat keresnek, általában kis információcsomagokat is küldenek, az úgynevezett szondakérelmeket .

Ezek a szondakérelmek olyan információrészleteket küldenek, mint például egyedi MAC-cím (hasonló az ujjlenyomathoz), RSSI-jel (logaritmikus jelerősség) és a felmerült korábbi SSID-k listája. Mivel minden telefon egy MAC-címet fog küldeni (leszámítva a közelmúltbeli anonimizálási kísérleteket), ezeket könnyedén felhasználhatjuk az egyetemen sétáló diákok nyomon követésére.

Szondakérelmek gyűjtése

Végső projektünk követelményei magukban foglalták a félév során használt standard 6.S08 komponensek használatát: egy Teensy mikrovezérlőt, egy ESP8266-ot és egy GPS-modult. Tekintettel azonban az ESP8266 alacsony energiafogyasztására (120 mA) és az erős CPU szükségességének hiányára, úgy döntöttünk, hogy a Teensy-t teljesen megkerüljük. Ehhez a tervezési döntéshez meg kellett tanulnunk az FTDI programozók használatát az Arduino megvalósításának villantására az ESP-k számára, de ez lehetővé tette számunkra, hogy olyan környezetben folytassuk, amely erős ismeretséget és széles könyvtárat biztosított a beépített AT- parancs firmware.

A következő napokban rendelkezésünkre állt a Proof of Concept, amely nyomon követte az egyetem környékén tett szondakérelmeket; ez elég volt a professzoraink kétségeinek enyhítésére, és ez játék volt.

POC kidolgozása

Most, hogy már elég tudtunk a folytatásról, a csapatunk a következő napokat azzal az infrastruktúrával írta, amely lehetővé teszi számunkra, hogy tömegesen gyűjtsük ezeket a kéréseket. Írtam egy Flask + MySQL háttérprogramot az eszközinfrastruktúra + információk kezelésére, Avery egy iOS alkalmazáson dolgozott az eszközök telepítésének megkönnyítése érdekében, Daniel Gonzalez létrehozott egy gyönyörű felületet a weboldalunkon, Ethan pedig egy elemző platformot, amely a bejövő adatok gazdagságát átalakította érthető adatok értékes felismerésekkel.

Hardver oldalon Daniel és Ethan forrasztották az ESP8266-at prototípus táblákra, néhány tápegységgel együtt. Újra felhasználtuk az osztály által kapott PowerBoost 1000C-ket, hogy ezeket az eszközöket teljesen hordozhatóvá tegyük, aminek az volt a szép mellékhatása, hogy lehetővé tette számunkra a nyomkövetést néhány szűk helyen.

Különösen a csapat dinamikája volt csodálatos: együtt nevettünk, együtt tanultunk és igazán élveztük egymás társaságát. A hajnali 4 órakor történő telepítések nem voltak olyan rosszak, amikor a legjobb barátaiddal tartanak.

Telepítés

Tekintettel arra, hogy Ethan írt néhány remek kódot az eszközök automatikus csatlakoztatásához a legközelebbi nem biztonságos WiFi hotspothoz indításkor, az Avery pedig írt egy alkalmazást a hely + legutóbb áthelyezett mezők frissítésére (hasznos annak ismeretében, hogy mely MAC-címeket kell társítani az egyes helyekhez), telepítés olyan egyszerű volt, mint csatlakoztatni az eszközöket egy közeli konnektorhoz, és biztosítani, hogy képes legyen pingelni haza. A telepítés nagyon élvezetes volt, ha kreatív voltál vele.

Az adatok elemzése

Miután egy hétig hagytuk futni a projektet, körülbelül 3,5 millió próbakérelmet gyűjtöttünk össze (!). Azt is szeretném megjegyezni, hogy az adatok mind névtelenek; Ezek az adatok semmiképpen sem elég finomak ahhoz, hogy meghatározzák a MAC-címekről az egyénekre történő leképezést, enyhítve oktatóink adatvédelmi aggályait.

Először Ethan munkáját alkalmaztuk az összes helyszínen, ami azonnali izgalmat váltott ki. Adataink egyértelműen megmutatták az egyes helyek mögötti időszakos viselkedést .

Ez egyértelműen jelezte az egyetemen tapasztalható nagyobb tendenciákat: a fő artériák (10. előcsarnok, 26–100) csúcsforgalmat értek el 17 óra körül, míg az egyetem szélén lévő épületek (például a kávézóval rendelkező Stata) csúcsforgalmat értek el a dél. Mondanom sem kell, hogy a meglévő infrastruktúra mellett az adatok sokkal izgalmasabbá válnak.

Miután rájöttünk, hogy léteznek adatok ezekre a trendekre, elkezdtünk még néhány érdekes kérdést feltenni magunknak:

  • Mire következtethetnénk az eszközök gyártmánya + terjesztése kapcsán az MIT-nél?
  • Mi lenne, ha campusunkat hálózati grafikonként modelleznénk?
  • Van egy leggyakoribb séta?
  • Érdekesebb módon meg tudnánk jósolni, hogy az emberek hová mennek tovább a helyelőzmények alapján?

Egyenként támadtuk ezeket.

Az adatkészlet elemzése

A MAC-címek valóban rengeteg információt nyújtanak 6 bájtban; felhasználhatjuk ezeket az információkat, hogy többet tudjunk meg a körülöttünk járó emberekről. Például minden gyártó megvásárol egy gyártói előtagot minden gyártott eszközhöz, és ennek segítségével meghatározhatjuk az MIT körüli legnépszerűbb eszközöket.

De van még egy fogás is - az NSA nemrégiben megpróbálta felhasználni ezt a technológiát az egyének nyomon követésére, és sok gyártót arra késztetett, hogy névtelenítsék a szondakérelmeket. Ennek eredményeként nem tudjuk teljesen meghatározni az eszközök eloszlását, de megvizsgálhatjuk, hogy mennyire elterjedt a szondakérelmek névtelenítése.

Nagyon ironikus, hogy minden olyan eszköz, amely anonimizálja a szondakérelmeket, valóban tájékoztatja Önt, hogy ezt megteszik - anonimizált eszközöknél a cím helyileg címzett bitje (a második legkevésbé jelentős bit) 1-re van állítva. Ezért egy egyszerű SQL lekérdezés futtatása lehetővé teszi számunkra, hogy tudja, hogy az eszközök közel 25% -a anonimizálja a MAC-címeket (891 131/3 570 048 próbakérelem összegyűjtve).

A szállító előtagok listájának futtatásával (egy MAC-cím első három bájtja) azt látjuk, hogy a nyolc első cím közül a kettő névtelen.

  • Helyileg címzett „02: 18: 6a”, 162 589 előfordulás
  • Helyileg címzett „da: a1: 19”, 145 707 előfordulás
  • 74: da: ea Texas Instruments-től, 116 133 előfordulás
  • 68: c4: 4d a Motorola Mobility-től, 66.829 előfordulás
  • fc: f1: 36 a Samsung-tól, 66 573 előfordulás
  • 64: bc: 0c az LG-től, 63 200 előfordulás
  • ac: 37: 43 HTC-ből, 60 420 előfordulás
  • ac: bc: 32 az Apple-től, 55 643 előfordulás

Elég érdekes, hogy bár az Apple messze a legnagyobb szereplő a névtelenítés iránti kérelemben, látszólag véletlenszerűen küldik el a valós címet. Valaki számára olyan magas frekvencián követ, mint a miénk (szinte minden másodpercben), ez problémás; megnéztük az iPhone tulajdonos barátaival, és ijesztő pontossággal tudtuk követni a helyüket.

Jövőbeli helyek előrejelzése

Miután modelleztük a diákok sétáit hálózati grafikonként, rájöttünk, hogy könnyen kiszámíthatjuk annak valószínűségét, hogy egy másik csomópontra megyünk, figyelembe véve azt a csomópontot, ahol korábban tartózkodtak. Továbbá rájöttünk, hogy ez a grafikon könnyen modellezhető Markov láncként. A csúcsok kezdeti halmaza alapján hova mennének tovább?

Ez azonban jelentős kihívást jelentett: adatbázisunk kevéssé értette, hogy mikor kezdődött a séta, és mikor ért véget a séta. Alig volt több, mint egy koordináták kiírása helyekkel és időbélyegekkel . Ha manuálisan megvizsgálta a sétákat, akkor egyértelmű volt, hogy egyesek mikor kezdődtek, mások pedig véget értek, mivel az idők meglehetősen távol esnek egymástól.

Ez a fenti kép vizsgálatával érthető meg. Például ez az egyén nyilvánvalóan nem sétált Statától a Whitaker épületig, mivel ezek különböző napokon vannak. Adatbázisunknak azonban fogalma sincs erről, és mivel az adatok felhasználásának későbbi kísérlete hibás eredményeket hozna .

Elég érdekes, ha ezt az idősoros adatok klaszterezésének problémaként strukturáljuk , akkor nagyon érdekes lesz. Mi lenne, ha lenne mód az időbélyegek csoportosítására, így azonosíthatnánk a diák „különféle sétáit”? Figyelembe véve az idősoros adatok klaszterezésének közelmúltbeli buzgóságát, arra gondoltam, hogy ez egy szórakoztató projekt, amellyel a nyaramat kezdhetem.

Az adatbázis séta elemzése

Ahhoz, hogy a lehető legjobban megértsem az adatok lehetséges klaszterezését, jobban meg kellett értenem az időbélyegeket. Úgy kezdtem, hogy az időbélyegeket hisztogramra rajzoltam, hogy jobban megértsem az adatok eloszlását. Örülök, hogy ez az egyszerű lépés segített a fizetési szennyeződések eltalálásában: kiderült, hogy a szondakérések gyakorisága az ESP8266-tól való távolságra vonatkoztatva nagyjából egy Gauss-féle eloszlást követ, lehetővé téve számunkra a Gauss-féle keverékmodell használatát. Egyszerűbben csak azt a tényt tudnánk kihasználni, hogy az időbélyegek ezt az eloszlást követik az egyes klaszterek kibontásához.

A későbbi probléma az volt, hogy egy GMM-nek meg kell mondani, hogy hány klasztert használjon , önmagában nem fogja azonosítani. Ez komoly problémát vetett fel, különösen ha figyelembe vesszük, hogy az egyes egyének megtett sétáinak száma nagyon változó volt. Örömmel tudtam felhasználni a Bayes információs kritériumot, amely kvantitatív módon pontozza a modelleket összetettségük szempontjából. Ha optimalizálnám a BIC minimalizálását a modell méretéhez képest, akkor a fürtök optimális számát meghatározhatnám túlteljesítés nélkül; ezt általában könyöktechnikának nevezik .

A BIC az elején meglehetősen jól működött, de a lehetséges fürtök számának alulszámításával túlságosan megbüntetné azokat a személyeket, akik sok sétát tettek . Összehasonlítottam ezt a Silhouette Scoring-szel, amely a klasztert úgy értékeli, hogy összehasonlítja a klaszteren belüli távolságot a legközelebbi klaszterrel való távolsággal. Meglepő módon ez sokkal ésszerűbb megközelítést biztosított az idősoros adatok klaszterezéséhez, és elkerülte a BIC által tapasztalt sok buktatót.

Felnagyítottam a DO cseppemet, hogy ez néhány napig működhessen, és kifejlesztettem egy gyors Facebook botot, amely értesít a befejezésről. Ezzel az útból visszatérhetek a következő lépések előrejelzéséhez.

Markov-lánc fejlesztése

Most, hogy a vizsgálati kérelmek hatalmas sorozatát külön sétákra bontottuk, kidolgozhatunk egy Markov-láncot. Ez lehetővé tette számunkra az események következő állapotának megjóslását az előzőekhez képest.

A Markovify Python könyvtár segítségével generáltam egy Markov modellt, amely az előző lépésünkből kapott korpuszt adott, ami összehasonlíthatóan lerövidítette a fejlesztési időt.

Mellékeltem egy fent létrehozott Markov-lánc mintát; ez tulajdonképpen azt jelenti, hogy egy diák elhagyja az előadást (26–100 előadóterem) és a kollégiumába megy! Nagyon izgalmas, hogy egy számítógép képes volt felvenni ezt és hasonló sétát generálni. Bizonyos helyek megismétlődnek, mert minden rögzített hely valóban megfigyelést jelent. Ezért, ha egy helyszín több jelenik meg, mint mások, ez egyszerűen azt jelenti, hogy az egyén több időt töltött ott.

Bár ez primitív, a lehetőségek meglehetősen izgalmasak . mi lenne, ha felhasználhatnánk ezt a technológiát intelligensebb városok létrehozására, a torlódások elleni fellépésre és jobb betekintésre szolgálna arra, hogy miként tudnánk lerövidíteni az átlagos sétaidőt? A projekt adattudományának lehetőségei végtelenek , és hihetetlenül izgatott vagyok, hogy folytathatom ezeket.

Következtetés

Ez a projekt az első év egyik legizgalmasabb fénypontja volt, és hihetetlenül örülök, hogy sikerült! Szeretnék köszönetet mondani hihetetlen 6.S08-as társaimnak, mentorunknak, Joe Steinmeyernek és a 6.S08-nak mindazoknak, akik ezt lehetővé tették.

Sokat tanultam a projekt megvalósítása során, az idősoros adatok klaszterezésétől kezdve a szondakérelmek nyomon követéséhez szükséges infrastruktúráig az egyetemen. Csatoltam még néhány árut a csapatunk kalandjaihoz.