Привет всем! Каждую зиму в русских (да и не только) городах появляется зловредный гололед. Множество людей подскальзывается и травмирует различные части тела. Скажете, эта проблема должна решаться коммунальщиками — да, так и есть, но они часто не доглядывают за состоянием тротуаров и дворовых тропинок, а может быть и просто не знают, куда смотреть. Чтобы хоть как-то улучшить ситуацию, в решение проблемы все больше должны включаться современные технологии. Возможное улучшение — это приложение, в котором люди могут определить для себя наиболее безопасный маршрут из точки A в точку B, глядя на карту заледенелости. Итак, сегодня поговорим о создании системы оценки степени заледенелости улиц, основанной на статистике падений людей. Под катом машинное обучение, облака и мобильные приложения.

Где еще может быть полезно?

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

Еще одним полезным применением окажется получение тренером информации о падениях своих спортсменов на длинных трассах: лыжников, бегунов и пр. Все три галлюцинации полезных по мнению автора случая показаны на картинке выше для более полного осознания проблем. Автор же представляет разбор реализации системы для городского случая и называет ее Sleet Monitor. Система будет реализована в связке мобильного Android приложения и облачной составляющей. Сразу скажу, что весь код находится в репозитории на GitHub

В чем сложность?

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

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

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

Сбор данных

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

Данные представляют собой строки следующего формата: time_offset: x_value y_value z_value ... time_offset: x_value y_value z_value is_fall. Показания акселерометра нормированы по максимально возможному для конкретного типа акселерометра значению. Кол-во кортежей (time_offset, x_value, y_value, z_value) в строке зависит от частоты предоставления данных операционной системой. Здесь стоит заметить, что вся выборка была собрана на смартфоне LG Nexus 5, который выдает стабильно данные раз в 5 мсек при не заблокированном экране. Таким образом, за 1.5 секунды мы имеем 300 кортежей данных с пометкой времени.

Все данные приходилось собирать путем самостоятельных падений при помощи своего друга Кручинина Дмитрия. Таким образом, собранный датасет основан на выборке падений двух людей. Все собранные данные (грязные и очищенные) находятся в директории ml/data в репозитории.

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

Архитектура

Поскольку система основана на статистических данных со множества пользователей, ей необходима поддержка с воздуха центральная система, обрабатывающая данные. Она представляет из себя несколько машин и сервисов, развернутых в облаке Microsoft Azure, которые делятся на три типа в соответствии с их задачами:

1. Получение данных со смартфона
2. Детектирование падений
3. REST API получения карты заледенелости улиц

Все машины находятся в одной сети и «общаются» через базу данных Apache Cassandra. Эта NoSQL DBMS была выбрана благодаря ее главному свойству — она эффективно работает с большим потоком данных, приходящих в реальном времени со множества устройств. Сразу здесь стоит упомянуть дизайн базы данных. В базе имеется две таблицы со следующими схемами:

• sensor_data(user_id: varchar, x: float, y: float, z: float, lat: double, lon: double, timestamp: bigint, fall_status: int). Здесь хранятся все кортежи данных, приходящих с Android устройств. Почему храним все? Считается, что эти данные могут пригодиться в будущем, например, для обучения какого-либо алгоритма без учителя. Физическое хранение строк в этой таблице расположено по убыванию значения timestamp, чтобы можно было эффективно работать с более свежими кортежами данных.
  
  
• update_info(user_id: varchar, is_updated: boolean). Эта таблица нужна только для того, чтобы приложению-детектору определить, от каких пользователей пришли новые данные. Добавлена, чтобы не искать в большой таблице sensor_data свежие записи по каждому пользователю, а сразу знать, у кого есть обновления.

На картинке изображена полная архитектура системы, а за ней следует более детальное описание каждой составляющей.

Получение данных со смартфона

Для отправки и получения данных со смартфона был использован Azure Event Hub, специально предназначенный для большого потока коротких сообщений. На серверной стороне имеется машина с запущенным Java приложением, которое читает данные из очереди Event Hub`а и записывает их в базу данных Cassandra.

Данные представлены в формате JSON. Каждое сообщение от клиента содержит показания акселерометра, временные метки и GPS-координаты для всех измерений, полученных в промежутке 1 минуты.

Детектор падений

Для обработки потока данных от пользователей в облаке запущена машина с Python приложением. Почему именно Python? Просто потому что исследования с машинным обучением проводились на Python с использованием библиотеки scikit-learn, а переписывать приложение с использованием других технологий только для того чтобы запустить его на сервере на данном этапе было лишним.

Детектор падений работает по принципу скользящего окна (англ. — sliding window). Окно скользит по интерполированным данным (да, каждый кусок свежих данных, взятых из базы, интерполируется по причине проблемы, описанной вначале) и запускает классификатор для определения факта падения. Решение классификатора 1 (падение) или -1 (не падение) записывается обратно в базу данных для первого извлеченного кортежа в исследованном куске данных. Естественно, вся эта процедура выполняется независимо для каждого пользователя, который определяется по user_id в таблице.

Классификатор

Отдельно стоит поговорить про классификатор. Он основан на классическом (без использования нейронных сетей) алгоритме машинного обучения. Качество классификации оценивается по метрике F1-score. В поле исследования попало следующее:

1. Алгоритм машинного обучения и его параметры. Кандидатами на звание лучшего классификатора падений были выставлены Random Forest Classifier, Support Vector Classification/Regression и Linear Regression. После проведения нескольких запусков было выявлено, что Random Forest Classifier с кол-вом деревьев 10 и остальными параметрами по умолчанию (которые установил scikit-learn) показывает наилучшие результаты.
   
   
2. Датасет. Здесь варьировались тестовая и тренировочная выборки по соотношению <кол-во позитивов>:<кол-во негативов> и менялся набор самих негативов. Финальная тренировочная выборка негативов включает примеры простых движений смартфона в воздухе, хождений по комнате, подбрасываний, а также примеры, на которых классификатор давал ложные срабатывания в боевых условиях (т.е. когда весь цикл системы был реализован, а автор намеренно делал хождения по комнате и прыжки без падений). Итого датасет составлял 84 позитивных примера и 400 негативных. Из них 80% случайных примеров отводилось на обучение, остальные 20% — на тестирование.
   
   
3. Набор осей акселерометра. Исследования показали, что набор осей {x, z} дает наилучшие результаты в классификации, что также положительно влияет на сокращение интернет-трафика пользователя. Но здесь стоит оговориться. Дело в том, что данные падений собирались автором при постоянном положении смартфона в кармане верхней его частью вниз. Именно это направление соответствует направлению y на LG Nexus 5. Алгоритм переобучался на данных по оси y, и, несмотря на то, что он показывал неплохие результаты на тестовой выборке, в боевых условиях он давал очень много ложных срабатываний при простом повороте смартфона «вниз головой». Эту проблему можно решить путем создания более репрезентативной выборки. Но на данный момент результат с учетом только двух осей очень даже неплохой.
   
   
4. Параметры интерполяции. Как было сказано ранее, ввиду большого зоопарка устройств на Android приходится работать с разреженными данными. Здесь помогает линейная интерполяция. И раз уж мы беремся за интерполяцию, неплохо было бы попробовать уменьшить разрешение данных для сокращения интернет-трафика со стороны пользователя и для уменьшения серверной нагрузки на детектирование падений. Напомню, базовый датасет содержит полутора-секундные фреймы данных, разбитые на 300 кортежей (x, y, z, timestamp) (один кортеж в 5 мсек). При уменьшении разрешения до одного кортежа в 50 мсек наблюдается все еще приемлемое качество классификации, но объем данных сокращается в 10 раз!

Итоговое максимальное по нескольким тренировочным эпохам значение F1-score при всех указанных наилучших параметрах и с учетом намеренного разрежения данных в 10 раз оказывается на уровне ~90%. Без разрежения — ~95%.

REST API и отображение точек на карту

Для получения обновлений всеми пользователями приложения Sleet Monitor о степени заледенелости улиц был написан простенький REST API на Java с использованием библиотеки spark-java. Приложение обращается все к той же базе данных Cassandra и достает свежие координаты тех точек, для которых значение fall_status = 1 (в этом месте было обнаружено падение). По-хорошему, здесь можно провести некоторую очистку данных вроде проверки на совпадение координат нескольких точек. На данный момент без дополнительной обработки координаты добавляются в R-Tree для быстрого поиска по прямоугольной области, которая приходит в запросе от клиента.

Чтобы отобразить точки на карте моим товарищем Бондарем Богданом был реализован принцип heat map, позаимствованный из примера Google для Android. Суть принципа заключается в том, что при изменении масштаба карты в сторону увеличения области обзора отрисованные точки схлопываются так, что там, где чем больше плотность точек в окрестности, тем крупнее выглядит пятно на карте.

На рисунке ниже показан пример отрисованных точек падений. Это настоящие падения, «нападанные» автором на снегу специально для демонстрации работы системы. В красных областях автор намеренно падал несколько раз, чтобы показать, что классификатор падений работает неплохо, и при записи не было ниодного ложного срабатывания, при том что запись производилась непрерывно с одинаковой скоростью обхода улиц.

Заключение

Итак, небольшое улучшение в городской жизни людей сделать возможно. Система отслеживания падений людей реализована. Естественно, здесь можно и нужно сделать много оптимизаций, чтобы снизить как серверную нагрузку, так и нагрузку на интернет-трафик пользователя — натренировать модель сразу на более разреженных данных, тем самым сократив вычислительные затраты на детектор падений; увеличить шаг бегущего окна в детекторе; для сокращения трафика передавать данные с Android устройства в бинарном виде, а не как сейчас в JSON; и др.

Улучшения всегда можно делать, многие из них тривиальные, и при этом могут принести значительное снижение затрат как на серверную часть, так и по трафику пользователя. Цель разработки была в том, чтобы получить опыт запуска полного конвейера, включающего мобильное приложение и высоконагруженную серверную часть, обрабатывающую огромный поток данных в реальном времени. Но чтобы запустить эту систему в реальных условиях, нужно значительно расширить парк машин в облаке и распространить мобильное приложение с достижением высокой концентрации пользователей хотя бы в одном городе. А с монетизацией пока ничего не ясно.

Предвидя эту проблему на этапе зарождения идеи, сразу было решено делать проект открытым. Напомню, весь код находится в репозитории на GitHub. Цель написания дебютной для автора статьи на Хабрахабр заключалась не только в том чтобы рассказать о полученном опыте построения подобных систем, но и в том, чтобы получить какую-то обратную связь от сообщества. Поэтому комментарии очень приветствуются, равно как и предложения по дальнейшему развитию системы. Спасибо за внимание.