Kuinka seurasimme ja analysoimme yli 200 000 ihmisen jalanjälkeä MIT: ssä

Ensimmäisenä keväänä minulla oli ilo ottaa 6.S08 (yhdistetyt sulautetut järjestelmät), joka opettaa EECS: n peruskäsitteitä, kuten leipälauta, salaus ja algoritminen suunnittelu.

Vaikka luokka oli uskomattoman aikaa vievä ja haastava, minun on sanottava, että se oli yksi palkitsevimmista luokista, jonka olen tähän mennessä käynyt. Olen ylpeä siitä, että olen työskennellyt uskomattomien ihmisten kanssa (huuda Avery Lampille, Daniel Gonzalezille ja Ethan Weberille loputtomista muistoista) ja rakensimme yhdessä lopullisen projektin, jota emme unohda.

Viimeisessä projektissamme tiimimme tiesi haluavansa olla seikkailunhaluisia. Kävellessään saadakseen jäätelöä yhden päivän ajan Avery ehdotti laitetta WiFi-anturipyyntöjen seuraamiseksi, samanlainen kuin jotkut ostoskeskukset tekevät. Alustavan tutkimuksen ja suostuttelun jälkeen ohjaajiamme kohtaan päätimme sitoutua ja aloimme tutkia ideaa.

Mitä ovat WiFi-anturipyynnöt?

Useimmat ihmiset pitävät puhelinta vastaanottimena; se muodostaa yhteyden matkapuhelin- / WiFi-verkkoihin ja on käytännöllistä vain käytettäessä, kun se on kytketty. Kuitenkin, kun puhelimet etsivät WiFi-verkkoja, ne lähettävät yleensä myös pieniä tietopaketteja, joita kutsutaan anturipyyntöiksi .

Nämä anturipyynnöt lähettävät katkelmia tiedoista, kuten yksilöllinen MAC-osoite (samanlainen kuin sormenjälki), RSSI-signaali (logaritminen signaalin voimakkuus) ja luettelo aikaisemmista havaituista SSID-tunnuksista. Koska kukin puhelin lähettää yhden MAC-osoitteen (lukuun ottamatta viimeaikaisia ​​yrityksiä anonymisoida), voimme helposti hyödyntää niitä jäljittämään kampuksella kävelleviä opiskelijoita.

Koettimen pyyntöjen kerääminen

Loppuhankkeen vaatimuksiin sisältyi lukukauden aikana käytettyjen standardien 6.S08 komponenttien käyttö: Teensy-mikrokontrolleri, ESP8266 ja GPS-moduuli. Ottaen kuitenkin huomioon ESP8266: n (120 mA) alhaisen virrankulutuksen ja vahvan suorittimen tarpeen puuttumisen, päätimme ohittaa Teensyn kokonaan. Tämä suunnittelupäätös vaati meitä oppimaan käyttämään FTDI-ohjelmoijia Arduinon toteutuksen vilkkumiseen ESP: eillemme, mutta se antoi meille mahdollisuuden jatkaa ympäristöä, joka tarjosi vahvan tuntemuksen ja laaja kirjastojen sisäänrakennetun AT- komento laiteohjelmisto.

Seuraavien päivien aikana meillä oli todiste konseptista, joka seurasi kampuksen ympäri tehtyjä koepyyntöjä; tämä riitti lieventämään professoreidemme epäilyksiä, ja se oli peliä.

POC: n kehittäminen

Nyt kun tiesimme tarpeeksi koepyynnöistä eteenpäin, tiimimme käytti muutaman päivän ajan infrastruktuurin kirjoittamisen, jonka avulla voimme kerätä nämä pyynnöt joukkona. Kirjoitin Flask + MySQL -taustan laitteiden infrastruktuurin ja tietojen hallitsemiseksi, Avery työskenteli iOS-sovelluksen kanssa helpottaakseen laitteiden käyttöönottoa, Daniel Gonzalez loi kauniin käyttöliittymän verkkosivustollemme ja Ethan loi analyysialustan, joka muutti saapuvien tietojen runsauden ymmärrettävää tietoa arvokkailla oivalluksilla.

Laitteistopuolella Daniel ja Ethan juotti ESP8266: n prototyyppilevyille joidenkin tehomoduulien kanssa. Käytimme uudelleen luokan meille antamia PowerBoost 1000C -laitteita näiden laitteiden saattamiseksi täysin kannettaviksi, mikä oli mukava sivuvaikutus, joka antoi meille mahdollisuuden suorittaa seuranta joissakin ahtaissa paikoissa.

Erityisesti joukkuedynamiikka oli aivan upeaa: nauroimme yhdessä, opimme yhdessä ja nautimme todella toistenne seurasta. Käyttöönotto kello 4 ei ollut niin paha, kun se tapahtui joidenkin parhaiden ystävien kanssa.

Käyttöönotto

Ottaen huomioon, että Ethan kirjoitti hienon koodin laitteiden automaattiseen yhdistämiseen lähimpään suojaamattomaan WiFi-hotspotiin käynnistyksen yhteydessä, ja Avery kirjoitti sovelluksen päivittämään sijainti + viimeksi siirretyt kentät (hyödyllinen tietämään, mitkä MAC-osoitteet liitetään kuhunkin sijaintiin), käyttöönotto oli yhtä helppoa kuin kytkeä laitteet läheiseen pistorasiaan ja varmistaa, että se pystyi pingistämään kotiin. Käyttöönotto oli varsin nautinnollista, jos luovuutesi kanssa.

Tietojen analysointi

Annettuamme projektin kestää viikon, keräsimme noin 3,5 miljoonaa koepyyntöä (!). Haluan myös huomata, että kaikki tiedot ovat nimettömiä; nämä tiedot eivät ole millään tavalla riittävän tarkkoja määrittelemään kartoitus MAC-osoitteista yksilöihin, mikä lieventää useimpia ohjaajiemme liittyviä yksityisyyden huolenaiheita.

Aloitimme soveltamalla Ethanin työtä kaikkiin paikkoihin, mikä aiheutti välitöntä jännitystä. Tietomme osoittivat selvästi jokaisen sijainnin takana ajoittaisen käyttäytymisen .

Lisäksi se osoitti selvästi joitakin suurempia suuntauksia koko kampuksella: suurten valtimoiden (aula 10, 26–100) liikenne oli huippua noin kello 17.00, kun taas kampuksen reunalla olevat rakennukset (kuten Stata, jolla on kahvila) saavuttivat huippuliikenteen keskipäivä. Tarpeetonta sanoa, kun infrastruktuuri on paikallaan, tiedoista tulee paljon jännittävämpiä.

Kun saimme selville, että näiden trendien tiedot olivat olemassa, aloimme kysyä itseltämme vielä mielenkiintoisempia kysymyksiä:

  • Mitä voisimme tehdä johtopäätöksen laitteiden merkki + jakelusta MIT: ssä?
  • Entä jos mallinnamme kampuksemme verkkokaaviona?
  • Onko olemassa yleisin kävely?
  • Mielenkiintoisempaa, voisimmeko ennustaa minne ihmiset menevät seuraavaksi sijaintihistoriansa perusteella?

Jatkoimme hyökätä näitä yksitellen.

Tietojoukon analysointi

MAC-osoitteet tarjoavat tosiasiallisesti lukuisia tietoja 6 tavuina; Voimme hyödyntää näitä tietoja selvittääksemme enemmän ihmisistä, jotka kävelevät ympärillämme. Esimerkiksi jokainen valmistaja ostaa toimittajan etuliitteen jokaiselle valmistamalleen laitteelle, ja voimme käyttää tätä selvittämään MIT: n ympärillä olevat suosituimmat laitteet.

Mutta on myös saalis - NSA on viime aikoina yrittänyt käyttää tätä tekniikkaa yksilöiden jäljittämiseen. Tämän seurauksena emme pysty määrittämään laitteiden jakautumista täysin, mutta voimme tutkia, kuinka laaja koepyynnön anonymisointi on.

On melko ironista, että mikä tahansa laite, joka anonymisoi koepyynnöt, todella ilmoittaa sinulle tekevän sen - nimettömissä laitteissa osoitteen paikallisesti osoitettu bitti (toiseksi vähiten merkittävä bitti) on asetettu arvoon 1. Siksi yksinkertaisen SQL-kyselyn suorittaminen antaa meille mahdollisuuden tietää, että melkein 25% laitteista tekee MAC-osoitteista nimettömiä (891 131/3570 048 koetettua pyyntöä).

Suorittaessamme toimittajan etuliitteiden luetteloa (MAC-osoitteen kolme ensimmäistä tavua), näemme, että kaksi ylintä kahdeksasta parhaasta osoitteesta ovat nimettömiä.

  • Paikallisesti osoitettu ”02: 18: 6a”, 162589 esiintymistä
  • Paikallisesti osoitettu ”da: a1: 19”, 145 707 esiintymää
  • 74: da: ea Texas Instrumentsilta, 116133 esiintymää
  • 68: c4: 4d Motorola Mobilitystä, 66 829 esiintymää
  • fc: f1: 36 Samsungilta, 66573 esiintymää
  • 64: bc: 0c LG: ltä, 63 200 esiintymää
  • ac: 37: 43 HTC: ltä, 60420 esiintymää
  • ac: bc: 32 Applelta, 55 643 esiintymää

Mielenkiintoista on, että vaikka Apple on ylivoimaisesti suurin anonyymipyynnön pelaaja, he näyttävät satunnaisesti lähettävän todellisen osoitteen aina silloin tällöin. Jos joku seuraa niin korkealla taajuudella kuin meidän (lähes joka sekunti), se on ongelmallista; tarkasimme iPhonen omistavien ystävien kanssa ja pystyimme seuraamaan heidän sijaintiaan pelottavalla tarkkuudella.

Tulevien sijaintien ennustaminen

Mallintamisen jälkeen opiskelijan kävelyt verkkokaaviona huomasimme, että voimme helposti laskea todennäköisyyden mennä toiseen solmuun, kun otetaan huomioon solmu, jossa he olivat aiemmin. Lisäksi huomasimme, että tämä kaavio voidaan helposti mallintaa Markov-ketjuksi. Annetaan ensimmäinen joukko pisteitä, mihin ne menisivät seuraavaksi?

Tämä aiheutti kuitenkin merkittävän haasteen: tietokannassamme ei ollut juurikaan ymmärrystä siitä, milloin kävely alkoi ja milloin kävely päättyi. Se oli vain muutama koordinaattien kaatopaikka sijaintien ja aikaleimojen kanssa . Jos tarkastelet kävelyt manuaalisesti, oli selvää, kun jotkut alkoivat ja toiset päättyivät, koska ajat olisivat melko kaukana toisistaan.

Tämä voidaan ymmärtää tarkastelemalla yllä olevaa kuvaa. Esimerkiksi tämä henkilö ei selvästikään kävellyt Statasta Whitaker-rakennukseen, koska ne ovat eri päivinä. Tietokannassamme ei kuitenkaan ole aavistustakaan tästä, ja koska myöhemmät yritykset käyttää näitä tietoja tuottavat virheellisiä tuloksia .

Mielenkiintoista on, että jos strukturoimme tämän uudelleen aikasarjatietojen ryhmittelyn ongelmaksi , siitä tulee hyvin kiehtova. Entä jos aikaleimoja olisi klusteroitu siten, että voimme tunnistaa opiskelijan tekemät erilaiset "kävelyt"? Ottaen huomioon viime aikoina tapahtuneen aikasarjatietojen klusteroinnin, ajattelin, että tämä olisi hauska projekti, josta aloitan kesän.

Jäsennys tietokanta kävelee

Minun oli ymmärrettävä paremmin aikaleimat, jotta voisin ymmärtää parhaiten, miten tiedot mahdollisesti ryhmitellään. Aloitin piirtämällä aikaleimat histogrammiin ymmärtämään paremmin tietojen jakautumista. Onneksi tämä yksinkertainen vaihe auttoi minua lyömään palkka-lika: käy ilmi, että anturipyyntöjen taajuus suhteessa ESP8266: een seuraa suunnilleen Gaussin jakaumaa, mikä antaa meille mahdollisuuden käyttää Gaussin seosmallia. Yksinkertaisemmin voisimme vain hyödyntää sitä, että aikaleimat noudattavat tätä jakaumaa yksittäisten klustereiden tuhoamiseksi.

Seuraava ongelma oli, että GMM: lle on kerrottava, kuinka monta klusteria on käytettävä , se ei tunnista sitä yksin. Tämä aiheutti vahvan ongelman, varsinkin kun otetaan huomioon, että jokaisen yksilön käyntien määrä oli hyvin vaihteleva. Onneksi pystyin hyödyntämään Bayesin tietokriteeriä, joka pisteyttää mallit kvantitatiivisesti niiden monimutkaisuuden suhteen. Jos optimoisin minimoimalla BIC: n mallikoon suhteen, voisin määrittää optimaalisen klustereiden määrän ilman ylimääräistä asennusta; tätä kutsutaan yleisesti kyynärpäätekniikaksi.

BIC toimi alussa kohtuullisen hyvin, mutta rankaisi liikaa ihmisiä, jotka kävivät monilla kävelyretkillä, laskemalla liian vähän mahdollisten klustereiden lukumäärää . Verroin tätä Silhouette Scoringiin, joka pisteyttää klusterin vertaamalla klusterin sisäistä etäisyyttä lähimpään klusteriin. Yllättäen tämä tarjosi paljon järkevämmän lähestymistavan aikasarjatietojen ryhmittelyyn ja vältteli monia BIC: n kohtaamia karhoja.

Suurensin DO-pisarani antamaan tämän käydä muutaman päivän, ja kehitin nopean Facebook-botin ilmoittamaan minulle valmistumisen jälkeen. Kun tämä olisi poissa, voisin palata töihin ennustamalla seuraavia vaiheita.

Markov-ketjun kehittäminen

Nyt, kun olemme ryhmitelleet valtavan määrän koetinkyselyjä erillisiin käynteihin, voimme kehittää Markov-ketjun. Tämä antoi meille mahdollisuuden ennustaa tapahtumien seuraava tila edellisten perusteella.

Käytin Python-kirjastoa Markovify generoimaan Markov-mallin, joka antoi edellisestä vaiheestamme korpus, joka lyhensi kehitysaikaa verrattain.

Olen sisällyttänyt mallin edellä luotuun Markov-ketjuun; tämä edustaa oikeastaan ​​kävelyä siitä, että opiskelija lähtee luennolta (26–100 on luentosali) ja menee hänen asuntolaansa! On todella jännittävää, että tietokone pystyi noutamaan tämän ja tuottamaan samanlaisen kävelyn. Jotkut sijainnit toistuvat, koska jokainen tallennettu sijainti edustaa todellakin havaintoa. Siksi, jos sijainti näkyy enemmän kuin muut, se tarkoittaa yksinkertaisesti sitä, että henkilö vietti enemmän aikaa siellä.

Vaikka tämä on alkeellista, mahdollisuudet ovat varsin jännittäviä . entä jos voisimme hyödyntää tätä tekniikkaa älykkäämpien kaupunkien luomiseksi, torjua ruuhkia ja tarjota parempia oivalluksia siitä, miten voimme pystyä lyhentämään keskimääräisiä kävelyaikoja? Tämän projektin datatieteen mahdollisuudet ovat rajattomat , ja olen uskomattoman innoissani niiden toteuttamisesta.

Johtopäätös

Tämä projekti oli yksi ensimmäisen vuoden mielenkiintoisimmista kohokohdista, ja olen erittäin iloinen siitä, että teimme sen! Haluan kiittää uskomattomia 6.S08-ikäisiäni, mentoriamme Joe Steinmeyeria ja koko 6.S08-henkilökuntaa, joka mahdollisti tämän.

Olen oppinut tämän projektin aikana paljon siitä, kuinka aikasarjatietoja klusteroidaan, infrastruktuuriin, jota tarvitaan anturipyyntöjen seuraamiseen kampuksella. Olen liittänyt lisää tuotteita alla tiimimme seikkailuihin.