كيف قمنا بتتبع وتحليل خطى أكثر من 200000 شخص في معهد ماساتشوستس للتكنولوجيا

في ربيعي الأول ، كان من دواعي سروري أن آخذ 6.S08 (الأنظمة المضمنة المترابطة) ، والتي تعلم مفاهيم EECS الأساسية مثل اللوح ، والتشفير ، والتصميم الحسابي.

بينما كان الفصل مستهلكًا للوقت بشكل لا يصدق ويشكل تحديًا ، يجب أن أقول إنه كان أحد أكثر الفصول مكافأة التي درستها حتى الآن. أنا فخور بالعمل مع بعض الأشخاص الرائعين (صرخوا إلى Avery Lamp و Daniel Gonzalez و Ethan Weber من أجل الذكريات التي لا تنتهي) ، وقمنا معًا ببناء مشروع نهائي لن ننساه.

بالنسبة لمشروعنا النهائي ، علم فريقنا أننا نريد أن نكون مغامرين. أثناء المشي للحصول على الآيس كريم يومًا ما ، اقترح Avery جهازًا لمراقبة طلبات فحص WiFi ، على غرار ما تفعله بعض مراكز التسوق. بعد بعض البحث الأولي والإقناع تجاه معلمينا ، قررنا الالتزام بالفكرة وبدأنا البحث عنها.

ما هي طلبات مسبار WiFi؟

يعتبر معظم الناس هواتفهم بمثابة جهاز استقبال ؛ يتصل بالشبكات الخلوية / WiFi ، ولجميع الاستخدامات العملية ، لا يعمل إلا عند الاتصال. ومع ذلك ، عندما تبحث الهواتف عن شبكات WiFi ، فإنها ترسل عادةً حزمًا صغيرة من المعلومات تسمى طلبات التحقيق .

ترسل طلبات الفحص هذه مقتطفات من المعلومات مثل عنوان MAC الفريد (مشابه لبصمة الإصبع) وإشارة RSSI (قوة الإشارة اللوغاريتمية) وقائمة بمعرفات SSID السابقة التي تمت مواجهتها. نظرًا لأن كل هاتف سيرسل عنوان MAC واحدًا (باستثناء المحاولات الأخيرة لإخفاء الهوية) ، يمكننا بسهولة الاستفادة منها لتتبع الطلاب الذين يتجولون في الحرم الجامعي.

جمع طلبات التحقيق

تضمنت متطلبات مشروعنا النهائي استخدام مكونات 6.S08 القياسية التي استخدمناها خلال الفصل الدراسي: متحكم صغير صغير ، و ESP8266 ، ووحدة GPS. ومع ذلك ، نظرًا لاستهلاك الطاقة المنخفض لـ ESP8266 (120 مللي أمبير) ، وعدم الحاجة إلى وحدة معالجة مركزية قوية ، قررنا تجاوز Teensy تمامًا. يتطلب قرار التصميم هذا أن نتعلم كيفية استخدام مبرمجي FTDI من أجل تشغيل تطبيق Arduino لمزودات الطاقة الكهروستاتيكية لدينا ، ولكنه مكّننا من الاستمرار في بيئة توفر إلمامًا قويًا واتساعًا في المكتبات على AT- المدمج. قيادة البرامج الثابتة.

في غضون الأيام القليلة التالية ، كان لدينا دليل على المفهوم يتتبع طلبات التحقيق التي تم إجراؤها حول الحرم الجامعي ؛ كان هذا كافياً لتخفيف أي شكوك من أساتذتنا ، واستمرت اللعبة.

تطوير POC

الآن بعد أن عرفنا ما يكفي عن طلبات التحقيق للمضي قدمًا ، أمضى فريقنا الأيام القليلة التالية في كتابة البنية التحتية التي ستسمح لنا بجمع هذه الطلبات بشكل جماعي. لقد كتبت خلفية Flask + MySQL لإدارة البنية التحتية للجهاز + المعلومات ، وعملت Avery على تطبيق iOS لتسهيل نشر الأجهزة ، وأنشأ Daniel Gonzalez واجهة جميلة لموقعنا على الإنترنت ، وأنشأ Ethan منصة تحليلات حولت ثروة البيانات الواردة إلى بيانات واضحة مع رؤى قيمة.

على جانب الأجهزة ، قام Daniel و Ethan بلحام ESP8266s الخاصة بنا على لوحات النموذج الأولي ، إلى جانب بعض وحدات الطاقة. لقد أعدنا استخدام PowerBoost 1000Cs التي قدمها لنا الفصل لجعل هذه الأجهزة محمولة بالكامل ، الأمر الذي كان له تأثير جانبي لطيف وهو السماح لنا بإجراء التتبع في بعض المواقع الضيقة .

والجدير بالذكر أن ديناميكية الفريق كانت رائعة للغاية: ضحكنا معًا وتعلمنا معًا واستمتعنا بصحبة بعضنا البعض حقًا. لم تكن عمليات النشر في الساعة 4 صباحًا سيئة للغاية عندما تكون مع بعض أفضل أصدقائك.

النشر

بالنظر إلى أن إيثان كتب بعض الرموز الأنيقة لتوصيل الأجهزة تلقائيًا بأقرب نقطة اتصال WiFi غير آمنة عند التمهيد ، وكتب Avery تطبيقًا لتحديث الموقع + آخر الحقول المنقولة (مفيدة لمعرفة عناوين MAC التي يجب ربطها بكل موقع) ، نشر كان سهلاً مثل توصيل الأجهزة بمنفذ قريب والتأكد من أنه قادر على اختبار الاتصال بالمنزل. كان النشر ممتعًا للغاية إذا كنت مبدعًا فيه.

تحليل البيانات

بعد السماح بتشغيل المشروع لمدة أسبوع ، قمنا بجمع حوالي 3.5 مليون طلب اختبار (!). أود أيضًا أن أشير إلى أن جميع البيانات مجهولة المصدر ؛ لا تعتبر هذه البيانات دقيقة بما يكفي بأي حال من الأحوال لتحديد تعيين من عناوين MAC إلى الأفراد ، مما يخفف من معظم مخاوف الخصوصية التي يواجهها مدرسونا.

بدأنا بتطبيق عمل إيثان على جميع المواقع ، مما تسبب في إثارة فورية. أظهرت بياناتنا بوضوح السلوك الدوري وراء كل موقع.

علاوة على ذلك ، فقد كان مؤشرًا واضحًا على بعض الاتجاهات الأكبر في جميع أنحاء الحرم الجامعي: حققت الشرايين الرئيسية (اللوبي 10 ، 26-100) ذروة حركة المرور حوالي الساعة 5 مساءً ، في حين حققت المباني الواقعة على حافة الحرم الجامعي (مثل Stata ، الذي يحتوي على مقهى) ذروة حركة المرور في وقت الظهيرة. وغني عن القول ، مع وجود البنية التحتية في مكانها الصحيح ، تصبح البيانات أكثر إثارة.

بمجرد أن اكتشفنا أن البيانات الخاصة بهذه الاتجاهات موجودة ، بدأنا في طرح بعض الأسئلة الأكثر إثارة للاهتمام على أنفسنا:

  • ماذا يمكن أن نستنتج بشأن صنع + توزيع الأجهزة في معهد ماساتشوستس للتكنولوجيا؟
  • ماذا لو قمنا بتصميم الحرم الجامعي لدينا على هيئة رسم بياني للشبكة؟
  • هل هناك نزهة شائعة؟
  • والأكثر إثارة للاهتمام ، هل يمكننا توقع المكان الذي سيذهب إليه الأشخاص بعد ذلك في ضوء سجل مواقعهم؟

شرعنا في مهاجمة هؤلاء واحدًا تلو الآخر.

تحليل مجموعة البيانات

توفر عناوين MAC في الواقع عددًا كبيرًا من المعلومات في 6 بايت ؛ يمكننا الاستفادة من هذه المعلومات لتحديد المزيد حول الأشخاص الذين يتجولون حولنا. على سبيل المثال ، يشتري كل مصنع بادئة بائع لكل جهاز يقوم بتصنيعه ، ويمكننا استخدام هذا لتحديد أكثر الأجهزة شيوعًا حول معهد ماساتشوستس للتكنولوجيا.

ولكن هناك أيضًا مشكلة - المحاولات الأخيرة لاستخدام هذه التكنولوجيا لتتبع الأفراد من قبل وكالة الأمن القومي أدت بالعديد من الشركات المصنعة إلى إخفاء هوية طلبات التحقيق. نتيجة لذلك ، لن نتمكن من تحديد توزيع الأجهزة بشكل كامل ، ولكن يمكننا التحقيق في مدى انتشار طلب التحقق من إخفاء الهوية.

من المثير للسخرية أن يخبرك أي جهاز يخفي هويته طلبات التحقيق فعلاً أنهم يفعلون ذلك - في الأجهزة المجهولة الهوية ، يتم تعيين البت الموجه محليًا (بت ثاني أقل أهمية) من العنوان على 1. لذلك ، يتيح لنا تشغيل استعلام SQL بسيط اعلم أن ما يقرب من 25٪ من الأجهزة تخفي هوية عناوين MAC (تم جمع 891،131 / 3570،048 طلب فحص).

عند تشغيل قائمة بادئات البائعين (أول ثلاثة بايت من عنوان MAC) ، نرى أن أهم اثنين من العناوين الثمانية الأولى مجهول الهوية.

  • تمت معالجتها محليًا "02: 18: 6 أ" ، 162589 تكرارًا
  • تمت معالجتها محليًا "da: a1: 19" ، 145707 تكرارات
  • 74: da: ea from Texas Instruments ، 116133 مرة
  • 68: c4: 4d من Motorola Mobility ، 66829 مرة
  • fc: f1: 36 من Samsung ، 66573 مرة
  • 64: قبل الميلاد: 0 ج من إل جي ، 63200 مرة
  • ac: 37:43 من HTC ، 60420 مرة
  • ac: قبل الميلاد: 32 من Apple ، 55643 مرة

ومن المثير للاهتمام ، أنه في حين أن شركة Apple هي إلى حد بعيد أكبر لاعب في التحقيق يطلب إخفاء الهوية ، يبدو أنهم يرسلون بشكل عشوائي العنوان الحقيقي بين الحين والآخر. بالنسبة لشخص ما يتعقب بتردد مرتفع مثلنا (كل ثانية تقريبًا) ، فإن هذا يمثل مشكلة ؛ لقد تحققنا مع الأصدقاء الذين يمتلكون iPhone وتمكنا من تتبع مواقعهم بدقة مخيفة.

توقع المواقع المستقبلية

بعد نمذجة مسارات الطلاب كرسم بياني للشبكة ، أدركنا أنه يمكننا بسهولة حساب احتمال الانتقال إلى عقدة أخرى بالنظر إلى العقدة التي كانوا عليها سابقًا. علاوة على ذلك ، أدركنا أن هذا الرسم البياني يمكن تصميمه بسهولة على أنه سلسلة ماركوف. بالنظر إلى مجموعة أولية من الرؤوس ، إلى أين ستتجه بعد ذلك؟

ومع ذلك ، فقد شكل هذا تحديًا كبيرًا: لم يكن لدى قاعدة البيانات الخاصة بنا فهم يذكر لوقت بدء المشي ومتى انتهى. كان أكثر بقليل من مجرد تفريغ للإحداثيات مع المواقع والطوابع الزمنية . إذا قمت بفحص الممرات يدويًا ، فقد كان من الواضح متى بدأ بعضها وانتهى البعض الآخر ، حيث ستكون الأوقات بعيدة عن بعضها البعض.

يمكن فهم ذلك من خلال فحص الصورة أعلاه. على سبيل المثال ، من الواضح أن هذا الشخص لم يمشي من ستاتا إلى مبنى ويتاكر ، لأنهما في أيام مختلفة. ومع ذلك ، فإن قاعدة بياناتنا ليس لديها فكرة عن ذلك ، ولأن أي محاولات لاحقة لاستخدام هذه البيانات ستؤدي إلى نتائج معيبة .

ومن المثير للاهتمام ، أننا إذا أعدنا هيكلة هذا باعتباره مشكلة تجميع بيانات السلاسل الزمنية ، فإنه يصبح مثيرًا للاهتمام للغاية. ماذا لو كانت هناك طريقة لتجميع الطوابع الزمنية ، بحيث يمكننا تحديد "مسارات المشي" المختلفة التي قام بها الطالب؟ بالنظر إلى الضجة الأخيرة حول تجميع بيانات السلاسل الزمنية ، فقد اعتقدت أن هذا سيكون مشروعًا ممتعًا لبدء الصيف.

تحليل قاعدة البيانات في مسارات

من أجل فهم أفضل كيفية تجميع البيانات بشكل محتمل ، كنت بحاجة إلى فهم الطوابع الزمنية بشكل أفضل. لقد بدأت برسم الطوابع الزمنية على الرسم البياني لفهم توزيع البيانات بشكل أفضل. بكل سرور ، ساعدتني هذه الخطوة البسيطة في الوصول إلى الأوساخ المدفوعة: اتضح أن تكرار طلبات التحقيق فيما يتعلق بالمسافة من ESP8266 يتبع تقريبًا توزيع Gaussian ، مما يسمح لنا باستخدام نموذج Gaussian Mixture. بشكل أكثر بساطة ، يمكننا فقط الاستفادة من حقيقة أن الطوابع الزمنية ستتبع هذا التوزيع لانتزاع المجموعات الفردية.

كانت المشكلة اللاحقة هي أن GMM بحاجة إلى أن يتم إخبارها بعدد المجموعات المراد استخدامها ، ولن تحددها بمفردها. قدم هذا مشكلة قوية ، لا سيما عند الأخذ في الاعتبار أن عدد مناحي كل فرد كان متغيرًا بدرجة كبيرة. بكل سرور ، تمكنت من استخدام معيار Bayes للمعلومات ، والذي يسجل النماذج كميًا فيما يتعلق بتعقيدها. إذا قمت بالتحسين للتقليل بواسطة BIC فيما يتعلق بحجم النموذج ، فيمكنني تحديد العدد الأمثل من المجموعات دون التجهيز الزائد ؛ يشار إلى هذا عادة باسم تقنية الكوع.

عمل مركز معلومات البنك بشكل جيد في البداية ، لكنه كان يفرط في معاقبة الأفراد الذين ذهبوا في نزهات عديدة من خلال عدم تقدير عدد المجموعات المحتملة . لقد قارنت هذا مع Silhouette Scoring ، والذي يسجل مجموعة من خلال مقارنة المسافة داخل المجموعة مع المسافة إلى أقرب مجموعة. والمثير للدهشة أن هذا قدم نهجًا أكثر منطقية لتجميع بيانات السلاسل الزمنية ، وتجنب العديد من المزالق التي واجهتها BIC.

لقد قمت بتوسيع نطاق تطبيق Droplet الخاص بي للسماح بتشغيل هذا الأمر لبضعة أيام ، وقمت بتطوير روبوت سريع على Facebook لإخطاري عند الانتهاء. مع هذا بعيدًا ، يمكنني العودة إلى العمل متنبئًا بالخطوات التالية.

تطوير سلسلة ماركوف

الآن بعد أن قمنا بتقسيم سلسلة هائلة من طلبات الفحص إلى مسارات منفصلة ، يمكننا تطوير سلسلة ماركوف. سمح لنا هذا بالتنبؤ بالحالة التالية للأحداث بالنظر إلى الأحداث السابقة.

لقد استخدمت مكتبة Python Markovify لإنشاء نموذج ماركوف بمجموعة من خطوتنا السابقة ، والتي اختصرت وقت التطوير بشكل مماثل.

لقد قمت بتضمين عينة Markov Chain التي تم إنشاؤها أعلاه ؛ هذا في الواقع يمثل المشي من مغادرة الطالب للمحاضرة (26-100 قاعة محاضرات) والذهاب إلى سكنه! من المثير حقًا أن يتمكن الكمبيوتر من التقاط هذا وإنشاء مسيرة مماثلة. تتكرر بعض المواقع ، وذلك لأن كل موقع مسجل يمثل بالفعل ملاحظة. لذلك ، إذا ظهر موقع أكثر من غيره ، فهذا يعني ببساطة أن الفرد قضى وقتًا أطول هناك.

في حين أن هذا أمر بدائي ، فإن الاحتمالات مثيرة للغاية . ماذا لو تمكنا من الاستفادة من هذه التكنولوجيا لإنشاء مدن أكثر ذكاءً ، والعمل ضد الازدحام ، وتقديم رؤى أفضل حول كيف يمكننا تقليل أوقات المشي المتوسطة؟ إمكانيات علم البيانات في هذا المشروع لا حصر لها ، وأنا متحمس للغاية لمتابعتها.

استنتاج

كان هذا المشروع من أكثر الأشياء إثارة في سنتي الأولى ، وأنا سعيد للغاية لأننا فعلناه! أود أن أشكر زملائي المذهلين 6.S08 ، ومرشدنا جو شتاينماير ، وجميع موظفي 6.S08 الذين جعلوا هذا ممكنًا.

لقد تعلمت الكثير أثناء متابعة هذا المشروع ، من كيفية تجميع بيانات السلاسل الزمنية ، إلى البنية التحتية المطلوبة لتتبع طلبات التحقيق حول الحرم الجامعي. لقد أرفقت بعض السلع أدناه بمغامرات فريقنا.