Авторы: Цзявэй Ван, Сет Ли, Хёнсу Чэ, Фэй Хэ

Github: https://github.com/sethlee0111/MobilityHMM

Введение

Понимание и знание того, как использовать человеческую мобильность, могут быть очень полезны для различных приложений в наши дни. Например, зная, как люди перемещаются по городу, градостроители и застройщики могут проектировать город более эффективно. Однако использовать мобильность людей непросто, поскольку люди ведут разнообразный образ жизни. Кроме того, с каждым днем ​​города становятся все сложнее и крупнее. Следовательно, нам нужны более совершенный метод и модель для анализа и представления модели мобильности человека.

Одним из методов будет использование приложений для социальных сетей с геотегами. В настоящее время у каждого есть мобильный телефон, который они всегда носят с собой. Кроме того, приложения для социальных сетей, такие как Facebook, Instagram и Twitter, теперь предоставляют услугу регистрации, когда пользователи показывают другим пользователям и отслеживают, куда они пошли.

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

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

DataSet

Мы использовали набор данных регистрации NYC от FourSquare. Всего насчитывается 227428 наборов данных регистрации, а диапазон дат - с апреля 2012 года по февраль 2013 года. Всего 1083 пользователя, совершивших не менее 100 проверок на человека. Кроме того, существует 250 категорий объектов с 38333 идентификаторами объектов для каждого объекта.

Пример адатасета показан ниже:

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

Траектория - это полезная функция, извлекаемая из записей регистрации пользователей, которая включает шаблон активности пользователя. Траектория определяется как последовательность действий пользователя, которые связаны в течение определенного промежутка времени. Для этого временного интервала мы использовали 3 часа и предварительно обработали данные, вычислив временной интервал между двумя действиями пользователя и определив траектории.

Набор данных доступен здесь.

Мобильность HMM

Большинство существующих моделей мобильности используют скрытые марковские модели для представления мобильности человека. Скрытые марковские модели - это просто марковские модели со скрытыми состояниями, которые лучше абстрагируют ненаблюдаемые состояния пользователя. Один из них построен на основе скрытой марковской модели, в которой вероятность излучения генерируется из двумерного гауссовского распределения и предсказывается следующее местоположение пользователя. Однако мы хотели использовать все три функции; местоположение, время и категория. Это привело нас к разработке и реализации скрытой марковской модели, которая имеет разные вероятности излучения для каждой особенности, наблюдаемой в каждом состоянии. В нашей модели состояние генерирует три характеристики: местоположение (долгота и широта), время (в секундах) и категория. Для создания этих характеристик используется распределение Гаусса для местоположения и времени, а для категорий - полиномиальное распределение. Мы реализовали эту модель с нуля, ссылаясь на существующие реализации HMM в библиотеке hmmlearn.

Простая модель

Как показано на рисунке выше, у нашей простой модели два уровня: один - это глобальная модель, а другой - персональная.

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

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

Подводить итоги:

Глобализированная модель:

  • Может показать только базовый образ жизни всех людей
  • Не показывает личность людей, слишком много обобщений

Персонализированная модель:

  • Могу только показать неповторимый образ жизни каждого человека
  • Требуется много данных о траектории для индивидуальной настройки каждого пользователя

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

Локализованная модель

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

С эвристической точки зрения необходимо пересмотреть степень детализации нашей модели. Группировка пользователей и прогнозирование на основе шаблона группы становится отличным вариантом. Группировка не только помогает с детализацией нашей окончательной модели, но также помогает справиться с проблемой разреженности данных. Пользователи не будут записывать свои действия каждый день, обычно они регистрируются в очень непредсказуемое время. А из-за того, что их данные немногочисленны, нам сложно спрогнозировать их активность.

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

Мы изобрели этот алгоритм, основанный на жадном и рандомизированном алгоритме. Он получил название рандомизированный алгоритм на основе Жаккара.

Коэффициент подобия Жаккара используется как способ определения сходства между двумя разными наборами. Мы случайным образом выбираем одну группу и вычисляем все сходства Жаккара с другими группами. И затем мы объединяем выбранную группу с максимальной группой сходства Jaccard по категориям их пользователей, которые они отметили. Мы продолжаем делать это до тех пор, пока необходимое количество групп не достигнет требований нашей модели.

К счастью, наша модель локализации работает. Как видно из рисунка выше, мы извлекаем трех пользователей из наборов результатов нашего алгоритма группирования, и, по-видимому, у них есть общие проверки активности на месте проведения.

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

Таким образом, нам потребуется более совершенная технология или алгоритм группировки для решения проблемы.

Модель перегруппировки

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

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

Результат и оценка

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

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

Количество групп:

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

Количество состояний:

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

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

Дальнейшая работа

Для будущей работы мы планируем протестировать больше моделей, которые лучше представляют шаблоны мобильности. Есть несколько существующих работ, которые продвигают скрытую марковскую модель на шаг вперед, рассматривая не только предыдущее состояние, но и предыдущие. Кроме того, мы хотели бы протестировать наши данные на других наборах данных, которые имеют аналогичные характеристики, что означает, что они разрежены, но могут быть сгруппированы в соответствии с их шаблонами.

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

Заключение

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

Ссылка

[1] Динци Ян, Дацин Чжан, Винсент Чжэн и Чжиюн Ю.

Моделирование предпочтений пользователей путем использования пространственно-временных характеристик пользователей в фунтах на дюйм.

Транзакции IEEE по системам, человеку и кибернетике: системы, 45 (1): 129–142, 2014.

[2] Чао Чжан, Кейанг Чжан, Цюань Юань, Люмин Чжан, Тим Ханратти и Цзявэй Хан.

Gmove: моделирование мобильности на уровне группы с использованием социальных сетей с геотегами.

В материалах 22-й Международной конференции ACM SIGKDD по открытию знаний и интеллектуальному анализу данных, страницы 1305–1314. ACM, 2016.

[3] Уэсли Мэтью, Рубен Рапозо и Бруно Мартинс.

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

В материалах конференции ACM 2012 г. по повсеместным вычислениям, страницы 911–918. ACM, 2012.

[4] Будхадитья Деб и Притхвиш Басу.

Обнаружение скрытой семантической структуры следов мобильности человека.

В Европейской конференции по беспроводным сенсорным сетям, страницы 84–103. Спрингер, 2015.

[5] Грэм В. Тейлор, Джеффри Э. Хинтон и Сэм Т. Роуис.

Две модели с распределенным состоянием для создания многомерных временных рядов.

Журнал исследований в области машинного обучения, 12 (март): 1025–1068, 2011 г.

[6] Кристиан Барретт, Ричард Хьюги и Кевин Карплюс.

Оценка скрытых марковских моделей

Биоинформатика, 13 (2): 191–199, 1997.