Как стать автором
Обновить

[кейс Locomizer] Какие знания можно на самом деле извлечь из анонимизированного датасета с координатами пользователей

Время на прочтение 20 мин
Количество просмотров 8.5K
Всего голосов 34: ↑32 и ↓2 +30
Комментарии 35

Комментарии 35

Прелестно, прелестно! ))) Прям вспомнил свой предыдущий проект.

Операции разрабатываются следующим образом: data scientist пишет матмодель в виде white paper, затем она программируются и отлаживаются на эталонных наборах данных на Python, и в конце собирается обработка на Spark (мы пишем на Java, но можно и на Scala), которую я оптимизирую. (Ага, примерно как в известном меме про рисование совы, впрочем, подробнее будет во второй части моего повествования.

Ну кстати да. У нас зачастую такое же происходит. Писать удобнее при помощи Юпитера, а вот в продакшн — отнють.
Допустим, любитель макдака, если только он по какой-то причине не привязан к конкретному ресторану, будет посещать в основном именно макдаки, но обходить стороной заведения бургер кинг. Соответственно, при положительном скоре в категории «рестораны быстрого питания» у него будет больший положительный скор по категории «McDonalds», который перевешивает меньший отрицательный скор по категории «Burger King».


Хм. Мне кажется, это преувеличение. Не отношу себя к любителям макдака, хотя иногда и посещаю. Но чтобы одновременно «обходить стороной заведения бургер кинг» — это чепуха. Ну то есть, как пример — годится, но на практике нужно такое рассматривать в каждом отдельном случае.
Да, тут как пример, но в жизни будет так: пользователь пойдет в ТЦ в котором есть макдак, а не в тот где есть бургер кинг. Не сказать, что он будет Burger King обходить стороной, но точно будет держаться ближе к McDonalds.
Ну это тоже сильное упрощение :) Скажем, у меня относительно рядом с домом есть три ТЦ, один маленький, и два огромных. Даже в маленьком есть и MD, и BK. Ну то есть, как эвристика это не хуже любой другой, и также как у любой другой тут будет куча случаев, когда она не работает.

И да, в больших ТЦ как правило фудкорт, и для меня оба этих заведения как правило в пределах 50 метров друг от друга, так что определить их по координатам вообще скорее всего не получится (в здании-то).

Но как пример эвристики — вполне сгодится. Скажем, мы пытались решить похожую задачу определения координат POI, имея на руках чек из него. Т.е. вы знаете, что вот в такое время человек что-то купил в заведении под названием «АБВГД», и название вам дает скажем Visa. Но вы не знаете, где оно находится. В данном тексте описано, что задача решается путем сбора информации о POI живьем, а мы пытались это определить по соседним точкам «траектории». И все решения, которые тут приходят в голову — чистая эвристика примерно такого же типа, с такими же допущениями.

Ну, я точно могу сказать, что аудитории macdonalds и бургеркинга практически не пересекаются. Примерно так же, как и зачастую люди пьют либо Кока-Колу, либо Пепси. Почему так? Ну, по совокупности факторов. Это примерно как обсуждать будет ли топ-менеджер заходить перекусывать в непонятную шаурмячную

Судя по мне — пересекаются. Если надо ребенка быстро накормить — идем, куда ближе от места прогулки.

P.S. Мы по музеям ходим, так что районы города совсем разные.
Ради интереса, как-нибудь выйдите во двор своей многоэтажки, и посмотрите, сколько спутников видит ваш смарт. (Скорее всего, вам потребуется рутованный андроид и/или какой-нибудь платный GPS-трекер.)

Эээээ. С десяток, причем SNR выше 30. Иногда два десятка. GPS-трекер бесплатный, андроид нерутованный — вся эта информация доступа бог знает с какого древнего уровня SDK из Location API вместе с азимутом и углом возвышения спутника надо горизонтом.
Телефоны среднего ценового диапазона.
У меня из здания — почти строго 2/20 (или 0/20). Собственно, один пример ничего не доказывает вообще (кроме того, что рутованный андроид скорее всего не нужен, да).
Из здания — да. Но в процитированной фразе речь шла про двор.
Вот прямо сейчас из квартиры — 4. С хреновым SNR 13-20, и длительным фиксом, да.
И «в один пример» входят некоторое число устройств на платформе Snapdragon, которые ведут себя схожим образом на протяжении последних 6 лет — Motorola Milestone 2, Highscreen Boost IIse, Xiaomi RedMi 4 Prime, Lenovo Phab 2 Pro, Яндекс.Телефон.
А если поопрашивать в чатиках — то это подтвердится для большинства девайсов от $200. Я это знаю точно, т.к. на протяжении последних лет играю в location-based игры, и там качество позиционирования очень сильно роляет.

В общем, вышепроцитированная фраза про спутники — заблуждение.
У меня двор-колодец, закрытый с трёх сторон. Видно в лучшем случае 1–3 спутника, пока из него не выйдешь.
Питер-стайл? ) тогда да
Ижевск — маленький Питер :)
Раз уж Вы отсылаете читателей к той статье из NYT, то у меня и вопрос про ту же тему: Какой объем статистики по девайсу нужен, чтобы идентифицировать уникального пользователя с надежностью 95%? Понятно, что на больших группах все работает; вопрос: как оно работает на малых группах и насколько малы эти группы?
Более частные вопросы:

1) Насколько уникальный профиль создает история перемещений девайса? Типа, вот этот парень ездит всегда из Коньково в Лужники, по пятницам вьет на Савеловской, а по субботам в Железнодорожный на весь день. Сколько таких парней найдется в одной многоэтажке — 1, 10, 50?

2) Можно ли понять, что вот тот же самый парень (малая группа), которую идентифицировали в вопросе #1, теперь ездит в аэропорт Шереметьево раз в неделю и покидает горд на два дня? Вряд ли таких пользователей в одной многоэтажке будет много, что дает возможность говорить о слежении за девайсом (но не об идентификации пользователя, пока).

3) Можно ли понять по совпадающим трэкам, что владелец данного девайса на iOS является также владельцем вот того девайса на Android? В смысле, пользователь носит два телефона на работу.

Давайте для простоты допустим, что: девайс есть смартфон совершеннолетнего жителя дефолт-сити, который работает 5/2 также в Москве, история доступна за год от одного провайдера.

Спасибо!
Я думаю, вы и сами знаете ответ :) Все в принципе можно, но все с определенными ограничениями. Скажем, я ношу на работу телефон и планшет, но планшет лежит на столе, а телефон в кармане. Сможем ли мы по треку, где этаж известен очень приблизительно, это понять? Ну то есть, это допущения из той же оперы, что и «воруют, кукурузу», описанные прямо тут.
Я предполагаю ответ и мне было бы интересно его проверить. Ваша компания вложилась в работу с большими массивами данных, но мне интересно Ваше мнение (поскольку Вы явно ближе к данным нужного типа, чем я), каковы были бы возможности технологии, если бы вы потратили сравнимые ресурсы на R&D в области персонального отслеживания девайсов.
Я не имею отношения к данному посту, поэтому отвечать могу только за свои опыты, которые к тому же закончились полтора года назад.

Мы какой-то результат получали даже на треках, которые вообще не от сотового провайдера, а от карточных транзакций. Т.е. человек что-то купил в такое-то время (с координатами), потом что-то еще в другом месте (без координат), и так далее. Этих данных вполне достаточно, чтобы вполне достоверно определить место работы и проживания с точностью до микрорайона. Мы свою задачу проверяли на себе, т.е. на одном номере карты. Вполне работает. Более того, задача предполагает построение маршрутов, что требует немало ресурсов, поэтому в каком-то смысле лучше решается на малых группах.

Ну то есть, если вы как-то группу заранее выделите — то по ней много чего можно сказать, и эти алгоритмы не слишком сложные. А вот найти в большом множестве треков два совпадающих — это просто вычислительно очень сложно может оказаться.
А, я не понял, что Вы не автор, прошу прощения.
Ну, тогда было бы круто услышать мнение начальника транспортного цеха :)
Ну да. Я просто решал очень похожие задачи немного с другой стороны, и в другом проекте.
1. Очень уникальный. Локация собирается покуда приложенька с картографическим и/или рекламным SDK, её собирающем, выполняется. Если она висит в фоне — то сильно реже. Закрыли или выгрузили приложеньку из фона — всё, трек оборвался. Спустились в метро — SDK послал вас непонятно куда.

2. Вопрос в общем-то теряет смысл, если не делать оооочень широких и непроверяемых допущений.

3. На них должны быть открыты одинаковые приложеньки одновременно (либо такие, которые юзают одинаковый SDK), чтобы паттерны сбора совпали, и попали они в выгрузку одного поставщика. Звучит весьма маловероятно. Если телефонов два, то используются они обычно для разных целей, и приложения на них стоят разные.

Но если накопить объём за год, и составить несколько сотен эвристик, заточенных на частные кейсы, кто-нибудь да найдётся. Но это работа на целый исследовательский институт, как вы понимаете.
1) Понятно, спасибо.

2) Не очень понятно, почему «теряет смысл», а не «нет, понять нельзя без допущений»?

3) А почему так? Там эвристики настолько сильно лажают, что паттерны не совпадут?

Вот это самый неясный момент в статье: почему собрать статистику по 100 человек за 30 дней можно и она будет содержать предсказательную силу, а по 10 людям за 300 дней нельзя…
Чем больше допущений, тем больше false positives. Эвристика по определению штука неточная, она всегда работает в рамках некоей гипотезы.

Но подтвердить или опровергнуть гипотезу, на которой основывается эвристика, без внешнего независимого контекста никак нельзя, потому что в эвристической модели она выступает в роли аксиомы. Принимается на веру, если так можно сказать в математическом смысле.

Вот смотрите. Берём какой-нибудь микрорайон, из которого ведут две дороги и электричка. Все жители этого микрорайона будут пользоваться только этими двумя дорогами и электричкой, потому что других путей вовне нет. И треки у них всех до ближайшей развязки или ТПУ с пересадками на 95% будут совпадать. Эвристика, основанная на таком совпадении, сматчит вам весь микрорайон, и чем больше времени вы будете брать, тем сильнее будет совпадение, потому что за год шанс уехать в командировку через аэропорт больше людей, чем за месяц, и скорее всего все они выберут один и тот же наиболее короткий маршрут.

Так же и визит к бабушке в пригород: накопленная на большом сроке статистика переведёт количество в качество, и одиночный визитёр растворится в нём, только усилив ожидаемый сигнал.

В любой эвристике такая закавыка: она имеет тенденцию начинать видеть закономерности там, где их нет, если данных много. И наоборот.

Очень важно вовремя остановиться, и научиться ограничивать датасет.
Вспоминается история про то, как Strava тепловой картой популярных маршрутов выдала расположение секретных военных баз.
А как связаны утечка данных с фитнес-трекеров и официально собираемая геолокация на смартфонах?

Данные с трекеров купить вообще нельзя, их никто не продаёт. У Стравы дыра была, отдавали данные кому попало без проверок.
Спасибо за текст, интересно.

Не очень понятно — с какой частотой обычный телефон Android пишет координаты юзера? Если человек смотрит в Google Maps, это понятно — тут GPS постоянно запущен, а в других случаях как? Если телефон просто в кармане лежит? Геолокация достаточно затратное для смартфона занятие, и обычно его стараются минимизировать или отключить. Нельзя просто так взять и писать лог GPS постоянно — телефон сядет за полдня, да и Android оповестит юзера раньше, что какая-то программа имеет фоновый доступ к геолокации.

Далее, как эти поставщики выкачивают данные, юзеры какое-то их приложение ставят? Android обычно предупреждает, что такая-то программа в фоне работает, непонятно как это можно незаметно сделать.

Более реально получать MAC-адреса девайсов в публичных WiFi-сетях, если конечно владелец сети отдает такую информацию, но если у юзера свой интернет на телефоне, то публичными WiFi он может и не пользоваться.

В общем, мутно тут как-то.
Не нужно ничего устанавливать специально.
Скорее всего, всё что нужно у вас уже установлено.
Разработчики мобильных приложений уже встроили модули мониторинга.
Вот такой, например — www.tutela.com

Да и сами операторы не прочь купить геоданные у поставщиков — tenders.mts.ru/TenderDescription.aspx?tender_id=4521774

Что важно — мы никогда не берёмся за задачи определения или нахождения конкретного человека, потому что ни одна из наших матмоделей не работает на малых выборках.

У вас просто алгоритмы под другое заточены. А вообще, если в датасете действительно есть timestamp, уникальный id девайса и координаты, то зная например из выпусков новостей, что некий политик сегодня был в Кремле, вчера на встрече ветеранов, а позавчера в театре, сопоставить нужный id с пересечением геолокаций в нужное время — тут даже machine learning и мат.моделей не надо, хватит обычных операций с множествами и простых фильтров.
У вас просто алгоритмы под другое заточены.

И я это несколько раз повторяю в статье открытым текстом, да.

Если вы берёте контекст извне, и заранее знаете, кого искать, задача упрощается, это должно быть очевидно.
Да, очевидно конечно, но в таком случае непонятно что в статье NY Times вы собираетесь опровергать. То что вы не ищете конкретных людей, не значит что этим не занимается кто-то другой.
А в каком месте я кого-то опровергаю? Нет же, я просто рассказываю о том, какие реальные задачи решаются по коммерческим датасетам, и какие знания из них можно извлечь без внешнего контекста.

И откуда мне знать вообще, что там пытается сделать с теми же данными кто-то другой? ¯\_(ツ)_/¯

Иногда навигацией занимаюсь. Могу сообщить о закольцованных треках по кругу. Наблюдал такую катину на смартфоне Samsung J 3. Приложение спотривный трекер Strava. Закольцованные виртуальные треки не настоящие возникали в случаях когда я забывал выключить на телефоне gps при этом прибор находился в многоэтажке на высоте. Примерно в метре от окна. При нечетком сигнале gps, периодически пропадающем, прибор рисует виртуальные круги. Это не чёткий сигнал приёмника. Ошибочная выборка. Сообщающая что прибор находится или в подвале или на этаже недалеко от окна.

Ради интереса, как-нибудь выйдите во двор своей многоэтажки, и посмотрите, сколько спутников видит ваш смарт. (Скорее всего, вам потребуется рутованный андроид и/или какой-нибудь платный GPS-трекер.)

Не потребуется.
play.google.com/store/apps/details?id=com.binarytoys.ulysse
На новых девайсах конкретно эта приложенька уже не работает (сколько уж лет не обновлялась). Вообще, в Play Store подобного вагон и маленькая тележка, но бесплатные поделки в основном либо такие же заброшенные, либо просто мусорные с кучей странных разрешений в манифесте.
Не обязательно данные могут быть из приложения, установленного на UE.

Операторы могут собирают трейсы, например, с eNodeB.
В этих трейсах нет координат, но есть много другой информации.
Трейсы экспортируются в GEO приложение, которое по трейсам определяет координаты и что-то ещё.
И вот уже эти данные идут к покупателю.
А вот классификатор по типам движения, работающий по принципу скользящего окна и машины состояний (методом проб и ошибок мы потратили на его разработку в сумме почти полгода), изощрён настолько, что называть его «фильтром» уже некорректно.

Вот про это будет особенно интересно почитать.
Про GNSS (GPS) довольно много неточностей.

Assisted GPS (AGPS) — это технология доставки альманахов и эфемерид через интернет. Альманахи и эфемериды — это данные для расчета координат спутника. Альманахи неточные, но могут служить месяц и более, транслируются с любого спутника. Эфемериды точные, могут служить 4 часа (для GPS), но транслируются только с того спутника, для которого предназначены.

В итоге давно не работавший приемник ловит какой-то спутник, берет с него альманахи, на основе данных альманахов определяет доплеровское смещение частоты, ловит остальные спутники, с них — эфемериды, а уж потом ищет решение. Если приемник переместили более чем на 300 км — картинка ещё интересней.

А засада тут вот в чем. Для приема эфемерид обычно используется когерентный прием. А для когерентного приёма нужен уровень сигнал-шум от 30 dB и выше. То есть всякие спутники с S/N 25 при этом игнорируются — с них не принять эфемериды без ошибок, а значит — их не удается пустить в решение.

Поэтому AGPS — это прежде всего средство ускорения старта (можно стартовать за 1 секунду вместо 35 для обычного способа). А во-вторую очередь — возможность использования некогерентного приема с S/N от 25.

Или отражать под непредсказуемым углом, сдвигать фазу, и так далее.
Гм, чем вам мешает сдвиг фазы? Сдвиг фазы на 180 градусов — это разница в 9.5 сантиметров. Она сильно ниже шума кода (он в районе ± трех метров для дешевых приемников). И вообще, где вы видели, чтобы стена дома сдвигала фазу? Ну или «отражала под непредсказуемым углом»? 10 лет вожусь с GNSS, но пока что никаких эффектов фазированной решетки от реальных домов не видел.

для нормальной точности нужно иметь 4 спутника в прямой видимости одновременно, лучше больше.
Для решения без высоты достаточно 3х спутников одной системы. Для решения с высотой — четырёх одной системы, и 3+N для N систем. Это будет весьма неточное решение. Для хоть какой-то точности — ну хотя 5+N, то есть 3 GPS+3 ГЛОНАСС. Ну а хорошее решение — 8+N и лучше. Обычно видим 18+ спутников (GPS+ГЛОНАСС), использует 10-12 лучших.

Ради интереса, как-нибудь выйдите во двор своей многоэтажки, и посмотрите, сколько спутников видит ваш смарт.
Вопрос не в том, сколько он видит, а в том, сколько спутников с большим S/N. Мы, скажем, стараемся в высокоточку брать с S/N от 35. Обычный приемник берет от 30, а мобильник может и от 25.

В-третьих, среднестатистический пользователь постоянно двигается, он не ждёт на месте по нескольку минут, пока его абонентский мобильный терминал поймает нужное количество спутников, он идёт или едет, поворачивает, и видимость постоянно меняется.
И это скорее улучшает решение. Ну или дает возможность улучшить. Спутники, принимаемые отраженным сигналом — будут регулярно пропадать. Спутники в прямой видимости — будут висеть дольше. Так что появляется возможность фильтровать и дать больший вес в корреляционной матрице долго висящим спутникам.

сделаны на гораздо более подходящей элементной базе, с хорошими усилителями и большими антеннами
По секрету — в большой антенне больше всего воздуха. Там маленький кристалл керамики + подстилающая (экран) для предотвращения приема отраженного сигнала снизу. Любая маленькая антенна на крыше автомобиля будет принимать отлично. Скорее уж в мобильниках экономят на ПАВ-фильтре для ухода от внеполосной помехи. Элементная база в мобильниках продвинутая, что-то вроде 22нм vs 90нм в обычных приемниках. Думаю что основная экономия (после ПАВ-фильтра) — в качестве и числе разрядов АЦП на стыке аналоговой и цифровой части.

P.S. Если в датасете есть количество спутников, принятых в решение — сделайте фильтр по нему. Скорее всего будет приличная корреляция с точностью решения.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории