Wie wir die Schritte von über 200.000 Menschen am MIT verfolgt und analysiert haben

Als Neuling hatte ich das Vergnügen, 6.S08 (Interconnected Embedded Systems) zu nehmen, in dem grundlegende EECS-Konzepte wie Breadboarding, Kryptographie und algorithmisches Design vermittelt werden.

Während der Unterricht unglaublich zeitaufwändig und herausfordernd war, muss ich sagen, dass er einer der lohnendsten Kurse war, die ich bisher besucht habe. Ich bin stolz darauf, mit einigen unglaublichen Menschen zusammengearbeitet zu haben (Dank an Avery Lamp, Daniel Gonzalez und Ethan Weber für die endlosen Erinnerungen), und zusammen haben wir ein letztes Projekt gebaut, das wir nicht vergessen würden.

Für unser letztes Projekt wusste unser Team, dass wir abenteuerlustig sein wollten. Als Avery eines Tages zu Fuß ging, um Eis zu holen, schlug er ein Gerät zur Überwachung von WiFi-Sondenanforderungen vor, ähnlich wie in einigen Einkaufszentren. Nach anfänglichen Recherchen und Überzeugungsarbeit gegenüber unseren Ausbildern beschlossen wir, uns zu engagieren und begannen, die Idee zu recherchieren.

Was sind WiFi-Sondenanforderungen?

Die meisten Menschen betrachten ihr Telefon als Empfänger. Es stellt eine Verbindung zu Mobilfunk- / WiFi-Netzwerken her und ist für alle praktischen Zwecke nur funktionsfähig, wenn eine Verbindung besteht. Wenn Telefone jedoch nach WiFi-Netzwerken suchen, senden sie üblicherweise auch kleine Informationspakete aus, die als Prüfanforderungen bezeichnet werden .

Diese Prüfanforderungen senden Informationsschnipsel wie eine eindeutige MAC-Adresse (ähnlich einem Fingerabdruck), ein RSSI-Signal (logarithmische Signalstärke) und eine Liste früherer SSIDs. Da jedes Telefon eine MAC-Adresse sendet (mit Ausnahme der jüngsten Anonymisierungsversuche), können wir diese problemlos nutzen, um Studenten zu verfolgen, die auf dem Campus herumlaufen.

Sammeln von Sondenanforderungen

Zu den Anforderungen für unser Abschlussprojekt gehörte die Verwendung der Standardkomponenten 6.S08, die wir während des Semesters verwendet haben: ein Teensy-Mikrocontroller, ein ESP8266 und ein GPS-Modul. Angesichts des geringen Stromverbrauchs des ESP8266 (120 mA) und des Fehlens einer starken CPU haben wir uns jedoch entschlossen, den Teensy insgesamt zu umgehen. Diese Entwurfsentscheidung erforderte, dass wir lernen mussten, wie man FTDI-Programmierer verwendet, um eine Implementierung von Arduino für unsere ESPs zu flashen, aber es ermöglichte uns, mit einer Umgebung fortzufahren, die eine starke Vertrautheit und eine Breite von Bibliotheken über das integrierte AT- bot. Befehl Firmware.

Innerhalb der nächsten Tage hatten wir einen Proof of Concept, der die Sondenanfragen rund um den Campus verfolgte. Dies war genug, um die Zweifel unserer Professoren zu zerstreuen, und es ging weiter.

Entwicklung eines POC

Nachdem wir genug über Testanfragen wussten, um fortzufahren, schrieb unser Team die nächsten Tage die Infrastruktur, die es uns ermöglichen würde, diese Anfragen massenhaft zu sammeln. Ich habe ein Flask + MySQL-Backend geschrieben, um Geräteinfrastruktur + Informationen zu verwalten, Avery hat an einer iOS-Anwendung gearbeitet, um die Bereitstellung von Geräten zu vereinfachen, Daniel Gonzalez hat ein schönes Frontend für unsere Website erstellt und Ethan hat eine Analyseplattform erstellt, die die Fülle eingehender Daten in verwandelt verständliche Daten mit wertvollen Erkenntnissen.

Auf der Hardwareseite haben Daniel und Ethan unsere ESP8266 zusammen mit einigen Leistungsmodulen auf Prototypenplatinen gelötet. Wir haben die PowerBoost 1000Cs, die uns von der Klasse zur Verfügung gestellt wurden, wiederverwendet, um diese Geräte vollständig tragbar zu machen, was den netten Nebeneffekt hatte, dass wir an einigen engen Orten Tracking durchführen konnten .

Insbesondere die Teamdynamik war absolut wunderbar: Wir haben zusammen gelacht, zusammen gelernt und die Gesellschaft des anderen wirklich genossen. Bereitstellungen um 4 Uhr morgens waren nicht so schlecht, wenn es mit einigen Ihrer besten Freunde ist.

Bereitstellen

Angesichts der Tatsache, dass Ethan einen raffinierten Code geschrieben hat, um die Geräte beim Booten automatisch mit dem nächsten ungesicherten WLAN-Hotspot zu verbinden, und Avery eine App geschrieben hat, um den Standort und die zuletzt verschobenen Felder zu aktualisieren (nützlich, um zu wissen, welche MAC-Adressen jedem Standort zugeordnet werden sollen), Bereitstellung Es war so einfach, die Geräte an eine nahe gelegene Steckdose anzuschließen und sicherzustellen, dass sie nach Hause pingen konnten. Die Bereitstellung hat sehr viel Spaß gemacht, wenn Sie damit kreativ wurden.

Analysieren der Daten

Nachdem wir das Projekt eine Woche lang laufen ließen, haben wir ungefähr 3,5 Millionen Testanfragen (!) Gesammelt . Ich möchte auch darauf hinweisen, dass die Daten alle anonymisiert sind. Diese Daten sind in keiner Weise fein genug, um eine Zuordnung von MAC-Adressen zu Personen zu bestimmen, wodurch die meisten Datenschutzbedenken unserer Ausbilder gemindert werden.

Wir begannen damit, Ethans Arbeit auf alle Standorte anzuwenden, was sofortige Aufregung verursachte. Unsere Daten zeigten deutlich das periodische Verhalten hinter jedem Standort.

Darüber hinaus war dies ein deutlicher Hinweis auf einige größere Trends auf dem gesamten Campus: Die Hauptverkehrsadern (Lobby 10, 26–100) erreichten gegen 17:00 Uhr einen Spitzenverkehr, während Gebäude am Rande des Campus (wie Stata mit einem Café) einen Spitzenverkehr erreichten Mittag. Mit der vorhandenen Infrastruktur werden die Daten natürlich viel aufregender.

Als wir herausfanden, dass die Daten für diese Trends vorhanden waren, stellten wir uns einige interessantere Fragen:

  • Was können wir über die make + Distribution von Geräten am MIT schließen?
  • Was wäre, wenn wir unseren Campus als Netzwerkdiagramm modellieren würden?
  • Gibt es einen häufigsten Spaziergang?
  • Könnten wir interessanterweise vorhersagen, wohin die Menschen angesichts ihrer Standortgeschichte als nächstes gehen werden?

Wir griffen diese einzeln an.

Analysieren des Datensatzes

MAC-Adressen bieten tatsächlich eine Fülle von Informationen in 6 Bytes. Wir können diese Informationen nutzen, um mehr über die Menschen zu erfahren, die um uns herumgehen. Beispielsweise kauft jeder Hersteller für jedes von ihm hergestellte Gerät ein Herstellerpräfix, mit dem wir die beliebtesten Geräte rund um das MIT ermitteln können.

Aber es gibt auch einen Haken: Die jüngsten Versuche der NSA, diese Technologie zur Verfolgung von Personen zu verwenden, haben viele Hersteller dazu veranlasst, Sondenanfragen zu anonymisieren. Infolgedessen können wir die Verteilung der Geräte nicht vollständig bestimmen, aber wir können untersuchen, wie weit verbreitet die Anonymisierung von Prüfanfragen ist.

Es ist ziemlich ironisch, dass jedes Gerät, das Prüfanforderungen anonymisiert, Sie tatsächlich darüber informiert - bei anonymisierten Geräten wird das lokal adressierte Bit (zweitniedrigstes Bit) der Adresse auf 1 gesetzt. Daher können wir eine einfache SQL-Abfrage ausführen wissen, dass fast 25% der Geräte MAC-Adressen anonymisieren (891.131 / 3.570.048 gesammelte Prüfanfragen).

Wenn wir die Liste der Herstellerpräfixe (die ersten drei Bytes einer MAC-Adresse) ausführen, sehen wir, dass die ersten zwei der acht besten Adressen anonymisiert sind.

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

Interessanterweise ist Apple zwar bei weitem der größte Anbieter bei der Anonymisierung von Prüfanfragen, sendet jedoch gelegentlich gelegentlich die tatsächliche Adresse. Für jemanden, der mit einer Frequenz verfolgt, die so hoch ist wie unsere (fast jede Sekunde), ist dies problematisch. Wir haben mit Freunden, die ein iPhone besitzen, gesprochen und konnten ihren Standort mit erschreckender Genauigkeit verfolgen.

Vorhersage zukünftiger Standorte

Nachdem wir die Spaziergänge der Schüler als Netzwerkdiagramm modelliert hatten, stellten wir fest, dass wir die Wahrscheinlichkeit, zu einem anderen Knoten zu gehen, anhand des Knotens, an dem sie sich zuvor befanden, leicht berechnen konnten. Darüber hinaus haben wir festgestellt, dass dieses Diagramm leicht als Markov-Kette modelliert werden kann. Wohin würden sie bei einer anfänglichen Menge von Eckpunkten als nächstes gehen?

Dies war jedoch eine große Herausforderung: Unsere Datenbank hatte wenig Verständnis dafür, wann ein Spaziergang begann und wann ein Spaziergang endete. Es war kaum mehr als ein Dump von Koordinaten mit Orten und Zeitstempeln . Wenn Sie die Spaziergänge manuell untersuchten, war klar, wann einige begannen und andere endeten, da die Zeiten ziemlich weit voneinander entfernt waren.

Dies kann durch Untersuchen des obigen Bildes verstanden werden. Zum Beispiel ist diese Person eindeutig nicht von Stata zum Whitaker-Gebäude gelaufen, da sich diese an verschiedenen Tagen befinden. Unsere Datenbank hat jedoch keine Ahnung davon, und da alle nachfolgenden Versuche, diese Daten zu verwenden, zu fehlerhaften Ergebnissen führen würden .

Interessanterweise wird es sehr faszinierend , wenn wir dies als Problem der Clusterbildung von Zeitreihendaten neu strukturieren . Was wäre, wenn es eine Möglichkeit gäbe, die Zeitstempel so zu gruppieren, dass wir die verschiedenen „Spaziergänge“ identifizieren könnten, die ein Schüler unternommen hat? Angesichts der jüngsten Begeisterung für das Clustering von Zeitreihendaten dachte ich, dass dies ein unterhaltsames Projekt sein würde, mit dem ich meinen Sommer beginnen könnte.

Analysieren der Datenbank in Spaziergänge

Um zu verstehen, wie die Daten möglicherweise gruppiert werden können, musste ich die Zeitstempel besser verstehen. Ich begann damit, die Zeitstempel auf ein Histogramm zu zeichnen, um die Verteilung der Daten besser zu verstehen. Glücklicherweise hat mir dieser einfache Schritt dabei geholfen, Pay Dirt zu treffen: Es stellt sich heraus, dass die Häufigkeit von Sondenanforderungen in Bezug auf die Entfernung von einem ESP8266 in etwa einer Gaußschen Verteilung folgt, sodass wir ein Gaußsches Mischungsmodell verwenden können. Einfacher könnten wir die Tatsache nutzen, dass die Zeitstempel dieser Verteilung folgen würden, um die einzelnen Cluster auszuwringen.

Das nachfolgende Problem bestand darin, dass einem GMM mitgeteilt werden muss, wie viele Cluster verwendet werden sollen , und dass er es nicht selbst identifiziert. Dies stellte ein starkes Problem dar, insbesondere wenn man bedenkt, dass die Anzahl der Spaziergänge, die jeder Einzelne unternahm, sehr unterschiedlich war. Glücklicherweise konnte ich das Bayes-Informationskriterium verwenden, mit dem Modelle hinsichtlich ihrer Komplexität quantitativ bewertet werden. Wenn ich die Minimierung durch BIC in Bezug auf die Modellgröße optimieren würde, könnte ich eine optimale Anzahl von Clustern ohne Überanpassung bestimmen. Dies wird allgemein als Ellbogentechnik bezeichnet.

Der BIC funktionierte anfangs recht gut, würde jedoch Personen, die viele Spaziergänge unternommen haben, übermäßig bestrafen, indem er die Anzahl möglicher Cluster unterberechnete . Ich habe dies mit Silhouette Scoring verglichen, bei dem ein Cluster bewertet wird, indem die Entfernung innerhalb des Clusters mit der Entfernung zum nächsten Cluster verglichen wird. Überraschenderweise bot dies einen viel vernünftigeren Ansatz für das Clustering von Zeitreihendaten und vermied viele der Fallstricke, auf die BIC stieß.

Ich habe mein DO-Tröpfchen vergrößert, damit es einige Tage laufen kann, und einen schnellen Facebook-Bot entwickelt, der mich nach Abschluss benachrichtigt. Damit könnte ich mich wieder an die Arbeit machen und die nächsten Schritte vorhersagen.

Entwicklung einer Markov-Kette

Nachdem wir eine enorme Anzahl von Prüfanforderungen in separate Schritte unterteilt haben, können wir eine Markov-Kette entwickeln. Dies ermöglichte es uns, den nächsten Stand der Ereignisse unter Berücksichtigung der vorherigen vorherzusagen.

Ich habe die Python-Bibliothek Markovify verwendet, um ein Markov-Modell mit einem Korpus aus unserem vorherigen Schritt zu generieren, wodurch die Entwicklungszeit vergleichbar verkürzt wurde.

Ich habe ein Beispiel für eine Markov-Kette beigefügt, das oben generiert wurde. Dies ist tatsächlich der Weg von einem Studenten, der die Vorlesung verlässt (26–100 ist ein Hörsaal) und in seinen Schlafsaal geht! Es ist wirklich aufregend, dass ein Computer dies aufgreifen und einen ähnlichen Spaziergang erzeugen konnte. Einige Orte werden wiederholt, da jeder aufgezeichnete Ort tatsächlich eine Beobachtung darstellt. Wenn ein Ort mehr als andere erscheint, bedeutet dies einfach, dass die Person mehr Zeit dort verbracht hat.

Während dies primitiv ist, sind die Möglichkeiten ziemlich aufregend . Was wäre, wenn wir diese Technologie nutzen könnten, um intelligentere Städte zu schaffen, Staus entgegenzuwirken und bessere Einblicke zu erhalten, wie wir möglicherweise die mittleren Gehzeiten reduzieren können? Die datenwissenschaftlichen Möglichkeiten in diesem Projekt sind endlos und ich bin unglaublich aufgeregt, sie zu verfolgen.

Fazit

Dieses Projekt war einer der aufregendsten Höhepunkte meines ersten Studienjahres und ich bin unglaublich froh, dass wir es geschafft haben! Ich möchte meinen unglaublichen 6.S08-Kollegen, unserem Mentor Joe Steinmeyer und allen 6.S08-Mitarbeitern danken, die dies ermöglicht haben.

Ich habe bei der Durchführung dieses Projekts viel gelernt, angefangen beim Clustering von Zeitreihendaten bis hin zur Infrastruktur, die für die Verfolgung von Sondenanforderungen auf dem Campus erforderlich ist. Ich habe unten einige weitere Artikel über die Abenteuer unseres Teams angehängt.