Πώς παρακολουθήσαμε και αναλύσαμε πάνω από 200.000 βήματα ανθρώπων στο MIT

Η πρώτη μου άνοιξη, είχα την ευχαρίστηση να πάρω το 6.S08 (Interconnected Embedded Systems), το οποίο διδάσκει βασικές έννοιες EECS όπως breadboarding, κρυπτογραφία και αλγοριθμικό σχεδιασμό.

Ενώ το μάθημα ήταν απίστευτα χρονοβόρο και προκλητικό, πρέπει να πω ότι ήταν ένα από τα πιο ικανοποιητικά μαθήματα που έχω λάβει μέχρι στιγμής. Είμαι περήφανος που συνεργάστηκα με μερικούς απίστευτους ανθρώπους (Shout out to Avery Lamp, Daniel Gonzalez και Ethan Weber για τις ατελείωτες αναμνήσεις) και μαζί, χτίσαμε ένα τελικό έργο που δεν θα ξεχνούσαμε.

Για το τελικό μας έργο, η ομάδα μας ήξερε ότι θέλαμε να είμαστε τολμηροί. Καθώς περπατούσε για να πάρει παγωτό μια μέρα, η Avery πρότεινε μια συσκευή για την παρακολούθηση αιτημάτων διερεύνησης WiFi, παρόμοια με το πώς κάνουν ορισμένα εμπορικά κέντρα. Μετά από κάποια αρχική έρευνα και πειθώ προς τους εκπαιδευτές μας, αποφασίσαμε να δεσμευτούμε και ξεκινήσαμε να ερευνούμε την ιδέα.

Τι είναι τα αιτήματα διερεύνησης WiFi;

Οι περισσότεροι άνθρωποι θεωρούν το τηλέφωνό τους ως δέκτη. Συνδέεται με δίκτυα κινητής τηλεφωνίας / WiFi, και για όλες τις πρακτικές χρήσεις, λειτουργούν μόνο όταν συνδέονται. Ωστόσο, όταν τα τηλέφωνα αναζητούν δίκτυα WiFi, συνήθως στέλνουν επίσης μικρά πακέτα πληροφοριών που ονομάζονται αιτήματα διερεύνησης .

Αυτά τα αιτήματα διερεύνησης αποστέλλουν αποσπάσματα πληροφοριών, όπως μια μοναδική διεύθυνση MAC (παρόμοια με ένα δακτυλικό αποτύπωμα), το σήμα RSSI (ισχύς λογαριθμικού σήματος) και μια λίστα με προηγούμενα SSID που συναντήθηκαν. Καθώς κάθε τηλέφωνο θα στέλνει μία διεύθυνση MAC (εξαιρουμένων των πρόσφατων προσπαθειών ανωνυμοποίησης), μπορούμε εύκολα να τις αξιοποιήσουμε για να παρακολουθούμε μαθητές που περπατούν γύρω από την πανεπιστημιούπολη.

Συλλογή αιτημάτων διερεύνησης

Οι απαιτήσεις για το τελικό μας έργο περιλάμβαναν τη χρήση των τυπικών στοιχείων 6.S08 που χρησιμοποιήσαμε κατά τη διάρκεια του εξαμήνου: έναν μικροελεγκτή Teensy, ένα ESP8266 και μια μονάδα GPS. Ωστόσο, δεδομένης της χαμηλής κατανάλωσης ισχύος του ESP8266 (120 mA) και της έλλειψης ανάγκης για ισχυρή CPU, αποφασίσαμε να παρακάμψουμε εντελώς το Teensy. Αυτή η απόφαση σχεδιασμού απαιτούσε από εμάς να μάθουμε πώς να χρησιμοποιούμε τους προγραμματιστές FTDI προκειμένου να αναβοσβήσουμε μια εφαρμογή του Arduino για τα ESP μας, αλλά μας επέτρεψε να συνεχίσουμε με ένα περιβάλλον που παρείχε μεγάλη εξοικείωση και ένα εύρος βιβλιοθηκών πάνω από το ενσωματωμένο AT- υλικολογισμικό εντολών.

Μέσα στις επόμενες μέρες, είχαμε μια απόδειξη της έννοιας που παρακολούθησε αιτήματα διερεύνησης που υποβλήθηκαν γύρω από την πανεπιστημιούπολη. αυτό ήταν αρκετό για να μετριάσει τυχόν αμφιβολίες από τους καθηγητές μας και συνεχίστηκε.

Ανάπτυξη POC

Τώρα που γνωρίζαμε αρκετά για να συνεχίσουμε τα αιτήματα διερεύνησης, η ομάδα μας πέρασε τις επόμενες μέρες γράφοντας την υποδομή που θα μας επέτρεπε να συλλέγουμε αυτά τα αιτήματα μαζικά. Έγραψα ένα backend Flask + MySQL για τη διαχείριση της υποδομής συσκευών + πληροφοριών, ο Avery εργάστηκε σε μια εφαρμογή iOS για να διευκολύνει την ανάπτυξη συσκευών, ο Daniel Gonzalez δημιούργησε ένα όμορφο frontend στον ιστότοπό μας και ο Ethan δημιούργησε μια πλατφόρμα αναλυτικών στοιχείων που μετέτρεψε τον πλούτο των εισερχόμενων δεδομένων σε κατανοητά δεδομένα με πολύτιμες πληροφορίες.

Από πλευράς υλικού, ο Daniel και ο Ethan συγκολλήθηκαν τα ESP8266s μας σε πρωτότυπες πλακέτες, μαζί με μερικές μονάδες ισχύος. Ξαναχρησιμοποιήσαμε τα PowerBoost 1000Cs που μας έδωσε η τάξη για να κάνουμε αυτές τις συσκευές εντελώς φορητές, γεγονός που είχε την ωραία παρενέργεια που μας επέτρεπε να εκτελέσουμε παρακολούθηση σε ορισμένες στενές τοποθεσίες.

Συγκεκριμένα, η δυναμική της ομάδας ήταν απολύτως υπέροχη: γελάσαμε μαζί, μάθαμε μαζί και απολαύσαμε πραγματικά τη συντροφιά του άλλου. Η ανάπτυξη στις 4 π.μ. δεν ήταν τόσο άσχημα όταν ήταν με μερικούς από τους καλύτερους φίλους σας.

Ανάπτυξη

Δεδομένου ότι ο Ethan έγραψε κάποιον καλό κώδικα για αυτόματη σύνδεση των συσκευών στο πλησιέστερο μη ασφαλές hotspot WiFi κατά την εκκίνηση και ο Avery έγραψε μια εφαρμογή για να ενημερώσει τα πεδία τοποθεσίας + τελευταίας μετακίνησης (χρήσιμο για να γνωρίζει ποιες διευθύνσεις MAC θα συσχετιστούν με κάθε τοποθεσία), ανάπτυξη ήταν τόσο εύκολο όσο η σύνδεση των συσκευών σε ένα κοντινό κατάστημα και η διασφάλιση ότι ήταν σε θέση να κάνει ping στο σπίτι. Η ανάπτυξη ήταν αρκετά ευχάριστη αν γίνονταν δημιουργικοί.

Ανάλυση των δεδομένων

Αφού αφήσαμε το έργο να τρέξει για μια εβδομάδα, συλλέξαμε περίπου 3,5 εκατομμύρια αιτήματα διερεύνησης (!). Θα ήθελα επίσης να σημειώσω ότι όλα τα δεδομένα είναι ανώνυμα. Σε καμία περίπτωση αυτά τα δεδομένα δεν είναι αρκετά ακριβή για να προσδιορίσουν τη χαρτογράφηση από διευθύνσεις MAC σε άτομα, μετριάζοντας τις περισσότερες ανησυχίες περί απορρήτου που είχαν οι εκπαιδευτές μας.

Ξεκινήσαμε εφαρμόζοντας το έργο του Ethan σε όλες τις τοποθεσίες, οι οποίες προκάλεσαν άμεσο ενθουσιασμό. Τα δεδομένα μας έδειξαν σαφώς την περιοδική συμπεριφορά πίσω από κάθε τοποθεσία.

Επιπλέον, ήταν σαφώς ενδεικτικό ορισμένων μεγαλύτερων τάσεων σε όλη την πανεπιστημιούπολη: οι μεγάλες αρτηρίες (Λόμπι 10, 26–100) πέτυχαν μέγιστη κυκλοφορία γύρω στις 5 μ.μ., ενώ τα κτίρια στην άκρη της πανεπιστημιούπολης (όπως η Στάτα, η οποία διαθέτει καφετέρια) πέτυχαν μέγιστη κυκλοφορία σε μεσημέρι. Περιττό να πούμε, με την υποδομή που υπάρχει, τα δεδομένα γίνονται πολύ πιο συναρπαστικά.

Μόλις καταλάβαμε ότι υπήρχαν δεδομένα για αυτές τις τάσεις, αρχίσαμε να αναρωτιόμαστε μερικές πιο ενδιαφέρουσες ερωτήσεις:

  • Τι θα μπορούσαμε να συμπεράνουμε σχετικά με τη διανομή συσκευών + στο MIT;
  • Τι γίνεται αν διαμορφώσουμε την πανεπιστημιούπολη μας ως γράφημα δικτύου;
  • Υπάρχει πιο συνηθισμένος περίπατος;
  • Το πιο ενδιαφέρον, θα μπορούσαμε να προβλέψουμε πού θα πάνε οι άνθρωποι, δεδομένου του ιστορικού τοποθεσίας τους;

Προχωρήσαμε σε επίθεση με ένα προς ένα.

Ανάλυση του συνόλου δεδομένων

Οι διευθύνσεις MAC παρέχουν πραγματικά πληθώρα πληροφοριών σε 6 byte. μπορούμε να αξιοποιήσουμε αυτές τις πληροφορίες για να προσδιορίσουμε περισσότερα σχετικά με τους ανθρώπους που περπατούν γύρω μας. Για παράδειγμα, κάθε κατασκευαστής αγοράζει ένα πρόθεμα προμηθευτή για κάθε συσκευή που κατασκευάζει και μπορούμε να το χρησιμοποιήσουμε για να προσδιορίσουμε τις πιο δημοφιλείς συσκευές γύρω από το MIT.

Ωστόσο, υπάρχει επίσης μια απλή - οι πρόσφατες προσπάθειες χρήσης αυτής της τεχνολογίας για την παρακολούθηση ατόμων από την NSA οδήγησαν πολλούς κατασκευαστές σε ανώνυμα αιτήματα διερεύνησης. Ως αποτέλεσμα, δεν θα μπορέσουμε να προσδιορίσουμε πλήρως την κατανομή των συσκευών, αλλά μπορούμε να διερευνήσουμε πόσο διαδεδομένη είναι η ανωνυμοποίηση αιτημάτων διερεύνησης.

Είναι πολύ ειρωνικό το γεγονός ότι οποιαδήποτε συσκευή που ανωνυμοποιεί αιτήματα διερεύνησης, σας ενημερώνει πραγματικά ότι το κάνει - σε ανώνυμες συσκευές, το bit τοπικής διεύθυνσης (δεύτερο λιγότερο σημαντικό bit) της διεύθυνσης ορίζεται σε 1. Επομένως, η εκτέλεση ενός απλού ερωτήματος SQL μας επιτρέπει γνωρίζετε ότι σχεδόν το 25% των συσκευών ανωνυμοποιούν διευθύνσεις MAC (συλλέχθηκαν 891.131 / 3.570.048 αιτήματα διερεύνησης).

Εκτελώντας τη λίστα προθεμάτων προμηθευτή (τα πρώτα τρία byte μιας διεύθυνσης 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 και καταφέραμε να παρακολουθήσουμε την τοποθεσία τους με τρομακτική ακρίβεια.

Πρόβλεψη μελλοντικών τοποθεσιών

Αφού μοντελοποιήσαμε τις διαδρομές των μαθητών ως γράφημα δικτύου, συνειδητοποιήσαμε ότι θα μπορούσαμε εύκολα να υπολογίσουμε την πιθανότητα μετάβασης σε έναν άλλο κόμβο δεδομένου του κόμβου στον οποίο βρίσκονταν προηγουμένως. Επιπλέον, συνειδητοποιήσαμε ότι αυτό το γράφημα μπορεί εύκολα να μοντελοποιηθεί ως αλυσίδα Markov. Λαμβάνοντας υπόψη ένα αρχικό σύνολο κορυφών, πού θα πήγαιναν στη συνέχεια;

Ωστόσο, αυτό αποτέλεσε μια σημαντική πρόκληση: η βάση δεδομένων μας δεν γνώριζε πότε ξεκίνησε μια βόλτα και πότε τελείωσε μια βόλτα. Ήταν κάτι περισσότερο από μια απόρριψη συντεταγμένων με τοποθεσίες και χρονικές σημάνσεις . Αν εξετάζατε τις βόλτες με μη αυτόματο τρόπο, ήταν ξεκάθαρο πότε ξεκίνησαν και άλλα τελείωσαν, καθώς οι καιροί θα ήταν πολύ μακριά μεταξύ τους.

Αυτό μπορεί να γίνει κατανοητό εξετάζοντας την παραπάνω εικόνα. Για παράδειγμα, αυτό το άτομο σαφώς δεν περπατούσε από τη Στάτα στο κτίριο Whitaker, καθώς αυτά είναι διαφορετικές ημέρες. Ωστόσο, η βάση δεδομένων μας δεν έχει ιδέα για αυτό, και καθώς τυχόν επακόλουθες προσπάθειες χρήσης αυτών των δεδομένων θα παράγουν ελαττωματικά αποτελέσματα .

Είναι αρκετά ενδιαφέρον, αν το αναδιαρθρώσουμε ως πρόβλημα συγκέντρωσης δεδομένων χρονοσειρών , γίνεται πολύ ενδιαφέρον. Τι θα συνέβαινε αν υπήρχε ένας τρόπος για να συγκεντρωθούν οι χρονικές σημάνσεις, έτσι ώστε να μπορούμε να εντοπίσουμε τις διάφορες «βόλτες» που έκανε ένας μαθητής; Λαμβάνοντας υπόψη την πρόσφατη φήμη σχετικά με τη συγκέντρωση δεδομένων χρονοσειρών, σκέφτηκα ότι θα ήταν ένα διασκεδαστικό έργο για να ξεκινήσω το καλοκαίρι μου.

Ανάλυση της βάσης δεδομένων σε περιπάτους

Για να καταλάβω καλύτερα πώς να συσσωματώσω δυνητικά τα δεδομένα, έπρεπε να κατανοήσω καλύτερα τις χρονικές σημάνσεις. Ξεκίνησα σχεδιάζοντας τις χρονικές σημάνσεις σε ένα ιστόγραμμα για να κατανοήσω καλύτερα την κατανομή των δεδομένων. Ευτυχώς, αυτό το απλό βήμα με βοήθησε να χτυπήσω το βρωμιά: αποδεικνύεται ότι η συχνότητα των αιτημάτων ανίχνευσης σε σχέση με την απόσταση από ένα ESP8266 ακολουθεί περίπου μια κατανομή Gauss, επιτρέποντάς μας να χρησιμοποιήσουμε ένα Gaussian Mixture Model. Πιο απλά, θα μπορούσαμε απλώς να αξιοποιήσουμε το γεγονός ότι οι χρονικές σημάνσεις θα ακολουθούσαν αυτήν την κατανομή για την εξάλειψη των μεμονωμένων ομάδων.

Το επόμενο πρόβλημα ήταν ότι ένα GMM πρέπει να πει πόσα συμπλέγματα θα χρησιμοποιήσει , δεν θα το αναγνωρίσει από μόνο του. Αυτό παρουσίασε ένα ισχυρό ζήτημα, ειδικά όταν θεωρούμε ότι ο αριθμός των περιπάτων που έκανε κάθε άτομο ήταν πολύ μεταβλητός. Ευτυχώς, μπόρεσα να χρησιμοποιήσω το Bayes Information Criterion, το οποίο βαθμολογεί ποσοτικά μοντέλα σε σχέση με την πολυπλοκότητά τους. Εάν βελτιστοποιήσω την ελαχιστοποίηση κατά BIC σε σχέση με το μέγεθος του μοντέλου, θα μπορούσα να καθορίσω έναν βέλτιστο αριθμό συστάδων χωρίς υπερβολική τοποθέτηση. Αυτό συνήθως αναφέρεται ως η τεχνική του αγκώνα.

Το BIC λειτούργησε αρκετά καλά στην αρχή, αλλά θα τιμωρούσε υπερβολικά άτομα που πήγαν σε πολλές βόλτες υπολογίζοντας τον αριθμό των πιθανών ομάδων . Το συγκρίνω με το Silhouette Scoring, το οποίο βαθμολογεί ένα σύμπλεγμα συγκρίνοντας την απόσταση εντός του συμπλέγματος με την απόσταση στο πλησιέστερο σύμπλεγμα. Απροσδόκητα, αυτό παρείχε μια πολύ πιο λογική προσέγγιση για τη συγκέντρωση δεδομένων χρονοσειρών και απέφυγε πολλές από τις παγίδες που αντιμετώπισε η BIC.

Κλίμακα το σταγονίδιο DO για να το αφήσω να τρέξει για λίγες μέρες και ανέπτυξα ένα γρήγορο bot Facebook για να με ειδοποιήσει μετά την ολοκλήρωσή του. Χωρίς αυτό, θα μπορούσα να επιστρέψω στη δουλειά, προβλέποντας τα επόμενα βήματα.

Αναπτύσσοντας μια αλυσίδα Markov

Τώρα που έχουμε χωρίσει μια τεράστια σειρά αιτημάτων διερεύνησης σε ξεχωριστές διαδρομές, ενδέχεται να αναπτύξουμε μια αλυσίδα Markov. Αυτό μας επέτρεψε να προβλέψουμε την επόμενη κατάσταση των συμβάντων με τα προηγούμενα.

Χρησιμοποίησα τη βιβλιοθήκη Python Markovify για να δημιουργήσω ένα μοντέλο Markov, δεδομένου ενός σώματος από το προηγούμενο βήμα μας, το οποίο μείωσε τον χρόνο ανάπτυξης συγκρίσιμα.

Έχω συμπεριλάβει ένα δείγμα Markov Chain που δημιουργήθηκε παραπάνω. Αυτό στην πραγματικότητα αντιπροσωπεύει τη βόλτα από έναν μαθητή που φεύγει από τη διάλεξη (26–100 είναι μια αίθουσα διαλέξεων) και πηγαίνει στον κοιτώνα του! Είναι πραγματικά συναρπαστικό που ένας υπολογιστής μπόρεσε να το χρησιμοποιήσει και να δημιουργήσει μια παρόμοια βόλτα. Ορισμένες τοποθεσίες επαναλαμβάνονται, αυτό συμβαίνει επειδή κάθε καταγεγραμμένη τοποθεσία αντιπροσωπεύει πραγματικά μια παρατήρηση. Επομένως, εάν μια τοποθεσία εμφανίζεται περισσότερο από άλλες, αυτό σημαίνει απλώς ότι το άτομο πέρασε περισσότερο χρόνο εκεί.

Αν και αυτό είναι πρωτόγονο, οι δυνατότητες είναι αρκετά συναρπαστικές . τι γίνεται αν θα μπορούσαμε να αξιοποιήσουμε αυτήν την τεχνολογία για να δημιουργήσουμε εξυπνότερες πόλεις, να καταπολεμήσουμε τη συμφόρηση και να παρέχουμε καλύτερες πληροφορίες σχετικά με το πώς μπορούμε να μειώσουμε τους μέσους χρόνους περπατήματος; Οι δυνατότητες της επιστήμης δεδομένων σε αυτό το έργο είναι ατελείωτες και είμαι απίστευτα ενθουσιασμένος που τις επιδιώκω.

συμπέρασμα

Αυτό το έργο ήταν ένα από τα πιο συναρπαστικά στιγμιότυπα της πρωτοχρονιάς μου και είμαι εξαιρετικά χαρούμενος που το κάναμε! Θα ήθελα να ευχαριστήσω τους απίστευτους συναδέλφους μου 6.S08, τον μέντορά μας Joe Steinmeyer και όλο το προσωπικό του 6.S08 που το έκανε αυτό δυνατό.

Έχω μάθει πολλά κατά την επιδίωξη αυτού του έργου, από τον τρόπο συγκέντρωσης δεδομένων χρονοσειρών, έως την υποδομή που απαιτείται για την παρακολούθηση αιτημάτων διερεύνησης στην πανεπιστημιούπολη. Έχω επισυνάψει μερικά ακόμη προϊόντα από τις περιπέτειες της ομάδας μας.