ГЕОЛОКАЦИЯ СУБЪЕКТОВ НА ОСНОВЕ ПРОИЗВОДНОЙ СОЦИАЛЬНОЙ СЕТИ Российский патент 2019 года по МПК H04W4/02 H04W4/18 H04W64/00 G01C21/00 

ПЕРЕКРЕСТНАЯ ССЫЛКА НА РОДСТВЕННЫЕ ЗАЯВКИ

[0001] По данной заявке испрашивается приоритет на основании предварительной заявки на патент США № 62/373664, поданной 11 августа 2016 г., которая включена в данный документ путём ссылки.

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

[0002] Варианты осуществления настоящего изобретения относятся в общем к анализу данных о местоположении пользователя и в частности к геолокации субъектов на основе производной социальной сети.

УРОВЕНЬ ТЕХНИКИ

[0003] Несмотря на способность мобильных телефонов записывать географическое местоположение пользователя (широту, долготу) в некоторые моменты времени, по-прежнему сложно точно указать место, в котором находился субъект. Причина в том, что у точек местоположения часто отсутствует плотность и точность.

[0004] Мобильные телефоны часто записывают местоположение экономно вследствие ограничений по батарее (частые точки местоположения израсходуют батарею телефона). Когда они записываются, точки не всегда являются точными и часто содержат значительную величину неопределенности (например, радиус 100 метров). Эта неопределенность усугубляется в густонаселенных городских районах, где в радиусе неопределенности может быть много мест. Поэтому трудно узнать, в каком месте фактически находится пользователь.

РАСКРЫТИЕ ИЗОБРЕТЕНИЯ

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

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

[0007] Эти и другие возможности раскрытого объекта изобретения станут понятнее после рассмотрения нижеследующих чертежей, подробного описания и формулы изобретения. Нужно понимать, что применяемые в этом документе формулировки и терминология предназначены для описания и не должны рассматриваться как ограничивающие.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

[0008] Различные задачи, признаки и преимущества раскрытого объекта изобретения можно полнее оценить на основании нижеследующего подробного описания раскрытого объекта изобретения при рассмотрении применительно к следующим чертежам, на которых одинаковые ссылочные позиции идентифицируют одинаковые элементы.

[0009] Фиг. 1 - схема системы, показывающая сетевую систему в соответствии с некоторыми вариантами осуществления настоящего изобретения.

[0010] Фиг. 2 - схема, показывающая социальный граф в соответствии с некоторыми вариантами осуществления настоящего изобретения.

[0011] Фиг. 3 - схема, показывающая информацию GPS, ассоциированную с посещением пользователя, в соответствии с некоторыми вариантами осуществления настоящего изобретения.

[0012] Фиг. 4 - схема, показывающая сбор информации о местоположении, ассоциированной с посещением пользователя, в соответствии с некоторыми вариантами осуществления настоящего изобретения.

[0013] Фиг. 5 - схема, показывающая сбор информации о месте, ассоциированной с посещением пользователя, в соответствии с некоторыми вариантами осуществления настоящего изобретения.

[0014] Фиг. 6 - блок-схема, показывающая назначение информации о месте для пользователя в соответствии с некоторыми вариантами осуществления настоящего изобретения.

[0015] Фиг. 7 - схема, показывающая пример назначения информации о месте в соответствии с некоторыми вариантами осуществления настоящего изобретения.

ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ

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

[0017] В некоторых вариантах осуществления описанные в этом методики документе привлекают социальную сеть пользователя и другие источники данных, чтобы сделать надежные выводы о точном местоположении пользователя на основании информации GPS, ассоциированной с пользователем (например, сформированной его телефоном). В некоторых вариантах осуществления количество времени, которое пользователь находится в конкретном местоположении (также называемое «посещением» в данном документе), относительно количества времени, которое социальная связь находится в том же местоположении, также дает информацию о месте, ассоциированную с пользователем.

[0018] В некоторых вариантах осуществления описанные в данном документе системы и способы принимают информацию о двух пользователях A и B и информацию об их нахождении (широта и долгота, горизонтальная точность, время прибытия и ухода). Описанные в этом документе системы и способы определяют, что A располагался в месте V (например, ресторан «Марио») (потому что пользователь сообщил системе и/или вследствие веского алгоритмического доказательства), и могут отметить B в том же месте, привлекая информацию о социальной связи между A и B и другую контекстную информацию (например, временная и географическая близость соответствующих посещений пользователей, собственные предпочтения и привычки пользователей).

[0019] Для сбора информации о пользователе и создания производной социальной сети могут использоваться различные методики, например, как описано на фиг. 1 и 2 ниже. Более того, системы и способы сбора информации о пользователе, чтобы создавать и изменять производную социальную сеть, подробнее описаны в заявке на патент США № 15/298353, озаглавленной "System and Method for Detecting Interaction and Influence in Networks", поданной 20 октября 2016 г., содержимое которой включено в данный документ путём ссылки.

[0020] Фиг. 1 - схема системы, показывающая сетевую систему 100 в соответствии с некоторыми вариантами осуществления настоящего изобретения. Фиг. 1 показывает устройство 102 пользователя, сеть 104, сервер 106 и базу 108 данных.

[0021] Устройство 102 пользователя может ассоциироваться с пользователем, участвующим в системах и способах отслеживания местоположения, описанных в этом документе, и может собирать информацию от пользователей, участвующих в сетевой системе. В некоторых вариантах осуществления устройство 102 пользователя может включать в себя любое компьютеризированное устройство, допускающее запись и передачу информации о близости некоторого пользователя к другому пользователю или к некоторому местоположению. В некоторых вариантах осуществления компьютеризированное устройство может включать в себя смартфон, планшет, компьютер, переносной компьютер, автомобиль или «умные» часы, на которые можно установить мобильное приложение, которое облегчает сбор данных.

[0022] В некоторых вариантах осуществления устройство 102 пользователя может включать в себя смонтированные в транспортном средстве агенты сбора данных, например автомобильные бортовые диагностические модули, телеметрические и телематические модули, транспондеры, бортовые модули GPS и другие системы, которые собирают релевантные данные.

[0023] В некоторых вариантах осуществления устройство 102 пользователя может включать в себя потребительские носимые устройства или фитнес-мониторы, например Jawbone Up, Fitbit Charge либо устройства Apple Watch.

[0024] В некоторых вариантах осуществления данные могут передаваться непосредственно с устройства 302 пользователя в сеть 304 (например, в случае мобильного приложения) либо могут собираться посредством промежуточного этапа. Например, в случае транспортной телеметрической системы может использоваться промежуточный модуль для сбора информации с бортового устройства и ее передачи по линии радиосвязи на смартфон, где ее можно передать потом в сеть 304.

[0025] В некоторых вариантах осуществления мобильное приложение можно установить на вычислительное устройство (смартфон) пользователя и позволить пользователю участвовать в различных механизмах сбора данных. Например, пользователь может разрешить описанной в этом документе системе собирать посредством мобильного приложения контакты пользователя, друзей в Facebook, друзей в Instagram, координаты во времени и платежи, проведенные с использованием вычислительного устройства (смартфона), шаблоны звонков и сообщений.

[0026] В некоторых вариантах осуществления устройство 102 пользователя может принимать вид приложения или прикладной программы, которой снабжаются различные сетевые устройства. Например, встроенное в DVR приложение может передавать данные в отношении зрительских привычек и предпочтений, тогда как программное обеспечение, встроенное в навигационную систему автомобиля, может передавать данные в отношении положения и манеры вождения.

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

[0028] Сеть 104 дает возможность коммуникации между устройствами 102 пользователей. Сеть 104 может быть сетью общего пользования, например Интернетом, при этом каждое из устройства 102 пользователя и сервера 104 подключено через шлюз с использованием таких протоколов связи, как Wi-Fi, Ethernet и беспроводной 4G. В качестве альтернативы сеть 104 может быть закрытой сетью, например локальной сетью (LAN) с различными компонентами системы анализа взаимосвязей, не доступными в открытом Интернете. В некоторых вариантах осуществления коммуникация по сети 304 может быть зашифрованной, либо могут использоваться дополнительные протоколы безопасности, например туннелирование по виртуальной частной сети (VPN) или безопасной оболочке (SSH).

[0029] Сервер 106 может включать в себя один или несколько служебных компьютеров, реализующих базу 108 данных для хранения собранных данных о пользователе. В некоторых вариантах осуществления конкретная конфигурация сервера 106 может зависеть от некоторого количества факторов, например типа базы данных, ожидаемого размера базы данных и предполагаемых пользователем характеристик. В некоторых вариантах осуществления система масштабируется, и можно добавлять дополнительную обрабатывающую способность, когда увеличивается спрос.

[0030] Фиг. 2 - схема, показывающая социальный граф 200 в соответствии с некоторыми вариантами осуществления настоящего изобретения. Социальный граф 200 включает в себя узлы 202, 204, 206, параметры 212, 214, 216 узлов и связи 220, 222, 224.

[0031] Как описано выше, социальный граф 200 является одним из способов представления объектов и взаимосвязи между объектами. К описанным в этом документе системам и способам в равной степени применимы другие способы визуализации объектов и взаимосвязи с объектами (например, матрица).

[0032] Узлы 202, 204, 206 представляют собой объекты и ассоциируются с набором параметров 212, 214, 216. Как описано выше, параметры 212, 214, 216 можно назначать узлам 202, 204, 206 соответственно на основании информации, принятой от узлов 110 сбора данных. Объекты могут включать в себя людей, организации и устройства. Параметры 212, 214, 216 могут включать в себя информацию, идентифицирующую сущность и описывающую по меньшей мере одну из взаимосвязи с местоположением, деятельностью или транзакцией, ассоциированную с сущностью. Например, если сущностью является человек, то параметры могут включать в себя идентификационный номер, день рождения, пол, работодателя, оценку кредитоспособности, местоположение (и точность местоположения), зарплату, последние транзакции и последнюю деятельность. В качестве другого примера, если сущностью является компания, то узел может включать в себя такие свойства, как ID компании, ID поставщика, название компании, год основания, адрес, отрасль промышленности, рейтинг в промышленности, оценка кредитоспособности, информация о местоположении, представленная в виде широты и долготы компании, и индикатор достоверности для точности координат местоположения. Информация о местоположении компании может быть полезна для определения перемещения и взаимодействия субъектов. В некоторых вариантах осуществления информация о параметрах может ассоциироваться с временем, в которое наблюдается, принимается или обрабатывается информация о параметрах.

[0033] При использовании в данном документе транзакции могут относиться к покупкам (например, одежда, продовольствие, поездка, товар), а деятельность может относиться к событиям (например, спортивные события, занятия, вечеринки).

[0034] Узел (например, узел 202) может соединяться с другими узлами (например, узлом 204 и узлом 206) посредством связей 220, 222, 224. Связи могут представлять прочность взаимосвязей между объектами либо прочности между параметрами, ассоциированными с объектами. Прочность взаимосвязи между объектами может меняться в зависимости от характера участвующих объектов и имеющегося доказательства. В некоторых вариантах осуществления, и как подробнее описано ниже, меньшие оценки считаются лучшими, и они аналогичны расстоянию. Значение прочности взаимосвязи может называться расстоянием между узлами и измеряться в единицах, в этом документе называемых аксонами.

[0035] В вариантах осуществления предусмторены подграфы, представляющие собой эффективную досягаемость объекта. Эти подграфы - известные как эго-сети [личные сети] -являются ограниченными расстоянием подграфами для некоторого объекта. В вариантах осуществления эго-сети являются основной единицей для всей дальнейшей обработки, как только создан социальный граф. Эго-сеть может формироваться с использованием следующих рекомендаций:

[0036] Можно задать максимальное расстояние обхода, которое ограничивает подграф путями, которые меньше максимального расстояния обхода, измеренного в аксонах. В некоторых вариантах осуществления максимальное расстояние обхода можно установить в 100000 аксонов, но можно использовать и другие настройки в зависимости от применения.

[0037] К расстоянию для каждого перехода на пути могут применяться штрафы за переходы путем умножения расстояния на штраф. Например, если у первого перехода между узлами штраф 5, и расстояние первого перехода составляло 100 аксонов, то практически получили бы пересчитанное расстояние в 500 аксонов.

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

[0039] В зависимости от того, является ли исходным узлом эго-сети субъект или сущность, могут вводиться дополнительные ограничения на формирование эго-сети, например ограничения на характеристики сети, которые учитываются во время обхода.

[0040] В некоторых вариантах осуществления можно создавать разные социальные графы на основании нужного фактора унифицированности между объектами. В этом случае релевантные эго-сети могут отличаться друг от друга. Например, при определении влияний объекта на узел 202 связь 220 с узлом 204 может быть сильнее, если запрос относится к объекту, который обладает наибольшей корреляцией с узлом 202 в плане релевантных предложений ресторанов в Городе A, тогда как связь 224 с узлом 206 может быть сильнее, если запрос относится к объекту, который обладает наибольшей корреляцией с узлом 202 в плане релевантного розничного торговца для повседневной одежды.

[0041] В некоторых вариантах осуществления, и как подробнее описано ниже, для вычисления подобия между каждой парой пользователей может использоваться информация, ассоциированная с таблицей посещений пользователями различных местоположений (и, возможно, мест). Если два пользователя обнаружены достаточно похожими, то они могут стать сущностью в общем графе связей. Для каждой связи есть два узла (например, 202 и 204), представляющие каждого из двух пользователей, и вес (или оценка) (например, 220), которая является вещественным числом между 0 и 1, указывающим прочность связи между двумя узлами.

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

[0043] Может определяться фактор унифицированности для объекта на основании измененного параметра для этого объекта. Например, когда объект едет в новое местоположение, можно создать социальный граф на основании факторов, которые релевантны поездке в новое место (например, гостиница, прокатный автомобиль, рестораны). В качестве другого примера измененный параметр может включать в себя конкретную покупку или замеченный шаблон покупок. В некоторых вариантах осуществления измененные параметры могут определять осведомленность объекта о некой области. Социальный граф может выглядеть иначе в родном городе объекта, чем в месте, которое этот объект никогда не посещал раньше. Например, у гостиницы может быть иное значение релевантности в родном городе объекта, нежели в новом месте, которое посещает объект (место с меньшей осведомленностью). В некоторых вариантах осуществления измененная информация о параметрах включает в себя местоположение и время, ассоциированные с измененным параметром.

[0044] В некоторых вариантах осуществления оценочная прочность взаимосвязи может меняться в зависимости от характера участвующих объектов и доступной информации. Например, взаимосвязь между двумя субъектами может оцениваться с использованием, среди прочих, таких метрик, как длина той взаимосвязи, является ли взаимосвязь личной или профессиональной, как часто два субъекта находятся в одном местоположении, и как часто субъекты посещают похожие местоположения. Аналогичным образом взаимосвязь между субъектом и конкретной торговой маркой может, среди прочих, включать в себя то, сколько субъект покупал эту торговую марку, как часто субъект покупает конкурирующие торговые марки, и как часто одно изделие покупается одновременно с другим изделием. Хотя в зависимости от типа может быть наложение между характеристиками взаимосвязи, также могут быть и отличия.

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

[0046] Индивидуальные взаимосвязи можно представить с использованием взвешенных взаимосвязей, которые оценивают взаимосвязи на основании характеристик взаимосвязей. В вариантах осуществления характеристики включают в себя длительность, давность, взаимодействие, доверие/многообразие, управление и гармонию. Дополнительные подробности, описывающие вычисление весов для связей между двумя пользователями, можно найти в заявке на патент США № 15/298353, озаглавленной "System and Method for Detecting Interaction and Influence in Networks", поданной 20 октября 2016 г., содержимое которой включено в данный документ путём ссылки.

[0047] Фиг. 3 - схема, показывающая информацию GPS, ассоциированную с посещением пользователя, в соответствии с некоторыми вариантами осуществления настоящего изобретения. Фиг. 3 показывает центроид 300 и радиус 301 центроида.

[0048] В некоторых вариантах осуществления «посещение» является парой GPS (широта, долгота) с временем начала и окончания (например, «28.11.2016 10:30:00+00:00»), сформированной конкретным устройством пользователя (например, мобильным телефоном). Посещение можно представить в пространстве с помощью окружности: центроид 300 находится там, где посещение записывается устройством, а радиус 301 изображает горизонтальную точность той записи, которая оценивается устройством. Как правило, чем больше радиус, тем меньше достоверность положения пользователя.

[0049] Фиг. 4 - схема, показывающая сбор информации о местоположении, ассоциированной с посещением пользователя, в соответствии с некоторыми вариантами осуществления настоящего изобретения. Фиг. 4 показывает объект 402 посещения, базу 404 данных, таблицу 406 пользовательских данных, ID 410 посещения и ID 412 устройства.

[0050] Объект 402 посещения загружается с устройства 102 пользователя на сервер 106. Объект 402 посещения включает в себя информацию о местоположении для пользователя, включая центроид, точность, время начала и окончания. Формат объекта посещения может быть любым форматом, согласованным устройством 102 пользователя и сервером 106, например форматом JSON, как проиллюстрировано ниже:

{

"deviceId": AAAABBBB,

"lat": 40,706134,

"lon": -74,013672,

"hAccuracy": 100,

"startTime": "28.11.2016 10:30:00+00:00",

"endTime": "28.11.2016 12:32:00+00:00"

}

[0051] Сервер 106 может сохранить информацию об объекте 402 посещения в базе 108 данных для дальнейшего анализа. Информацию в базе 108 данных можно упорядочить в таблицу 404 данных посещений, которая назначает каждому объекту ID 410 посещения и ID 412 устройства в таблице 404. Может использоваться любая структура данных, которая хранит ассоциацию между ID и объектом, например, целочисленная таблица, которая показана ниже:

ID посещения ID устройства 111 AAAABBBB 222 CCCCDDDD … ….

[0052] Как подробнее описано ниже в тексте, сопровождающем фиг. 5, ID 410 посещения может использоваться для соотнесения места с пользователем.

[0053] Фиг. 5 - схема, показывающая сбор информации о месте, ассоциированной с посещением пользователя, в соответствии с некоторыми вариантами осуществления настоящего изобретения. Фиг. 5 показывает данные 502 о месте и ID 504 места, сохраненные в таблице 501 данных.

[0054] Данные 502 о месте соответствуют информации о месте, ассоциированной с местоположением пользователя. В некотором варианте осуществления данные 502 о месте получаются посредством «отметки». «Отметка» при использовании в данном документе относится к действию, которое добровольно выполняется пользователем устройства 102, подтверждающим, что посещение следует привязать к месту (например, ресторан «Марио»). Места могут передаваться приложению, работающему на устройстве 102 пользователя, из таблицы мест. Также могут использоваться другие процедуры подтверждения мест, которые отображают посещение в место (например, транзакция по кредитной карте, веское алгоритмическое доказательство из других программных приложений). Информацию о месте можно привязать к ID 504 места, например, как показано ниже:

ID места Название 2222 Bar X 3333 Restaurant Y … ….

[0055] Данные 502 о месте, которые подтверждены, можно загрузить в виде объекта, отображающего ID 410 посещения в ID 504 места. ID 504 места может соответствовать уникальному ID, назначенному некоторому месту. Объект данных 502 о месте может иметь любой формат, согласованный устройством 102 пользователя и сервером 106, например форматом JSON, как проиллюстрировано ниже:

{

"visitId": 111

"venueId": 2222

}

[0056] ID 504 места можно сохранить в базе данных так, чтобы коррелировать ID 111 посещения с ID 504 места. Например, может использоваться целочисленная таблица, как показано ниже:

ID посещения ID устройства ID места 111 AAAABBBB 2222 222 CCCCDDDD …. … …. ….

[0057] Фиг. 6 - блок-схема алгоритма, показывающая назначение информации о месте для пользователя в соответствии с некоторыми вариантами осуществления настоящего изобретения.

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

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

[0060] Также, как описано выше, сервер принимает информацию, связанную с конкретным местом, в котором находится второй пользователь. Место может быть местоположением (пара широта, долгота), дополненным семантическими метаданными: например, категория (ресторан, гостиница, стадион и т. п.), название, время работы и т. п. В некоторых вариантах осуществления информация об «отметке» также ассоциирована с уровнем достоверности касательно надежности совпадения между нахождением и местом, о котором идет речь. Факторы, которые вносят вклад в надежность, включают в себя подтверждение пользователем места (например, ручная отметка пользователем в отношении этого места), стороннюю проверку места (например, покупки, сделанные пользователем в некотором месте) и другое алгоритмическое доказательство.

[0061] Обращаясь к этапу 606, оценка взаимосвязи между первым пользователем и вторым пользователем определяется на основании величины наложения между радиусом первого пользователя и радиусом второго пользователя и социальной метрики, указывающей прочность социальной взаимосвязи между первым и вторым пользователем. Отметим, что нижеследующее является лишь примером такого алгоритма, который может принимать различные виды (например, пороговое решение, деревья вероятностных решений и т. п.):

метрика временного наложения * метрика пространственного наложения * метрика социальной связи > пороговая величина → пользователю 2 будет назначена информация о месте пользователя 1

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

[0063] Обращаясь к этапу 608, информация о месте для первого пользователя создается на основании информации о месте, ассоциированной со вторым пользователем, когда степень корреляции мест превышает пороговую величину. Например, предположим следующий сценарий:

ПОЛЬЗОВАТЕЛЬ 1, посещение центрировано в <40,708793, -74,011013>, с 09:10 до 09:45

ПОЛЬЗОВАТЕЛЬ 2, посещение центрировано в <40,708616, -74,011145>, с 09:12 до 09:48

ПОЛЬЗОВАТЕЛЬ 1 подтверждает посещение в "Starbucks", расположенном по адресу Бродвей, 115 (10006, Нью-Йорк).

[0064] Для двух пользователей может вычисляться значение признаков в алгоритме принятия решений, который может выполнить сопоставление мест для ПОЛЬЗОВАТЕЛЯ 2, если выполняются условия, например:

Метрика временного наложения: 33/38=0,86 (наложение по времени, которое измерено как расстояние Жаккара между набором минут в двух интервалах)

Метрика пространственного наложения: 1-0,044=0,956 (расстояние между двумя посещениями (от точки к точке) равно 0,022 км, масштабировано до теоретического максимума в 0,5 км)

Метрика социальной связи: 0,75 (свойство, считанное из социального графа, при условии, что они близкие друзья)

[0065] Каждый из отмеченных выше признаков может вычисляться разными путями (например: в пространственном наложении могла бы явно использоваться горизонтальная точность). Кроме того, алгоритм, принимающий окончательное решение, может отличаться в разных вариантах осуществления: например, можно умножить три признака и эвристически задать пороговую величину на основании знаний в предметной области (аналогично проиллюстрированной выше взаимосвязи ЕСЛИ-ТО); или, в качестве другого примера, можно оценить распределение этих оценок и выбрать пороговую величину в виде значения, образующего n-ый процентиль (то есть значения, образующего n% оценок, как не достаточно веского для совпадения мест). В конечном счете при достаточном количестве обучающих данных может использоваться алгоритм машинного обучения, подходящий для задачи принятия решений (например, логистическая регрессия, дерево решений), для нахождения оптимального способа принять окончательное решение по совпадению мест на основании пространственно-временных признаков и социальной связи.

[0066] Фиг. 7 - схема, показывающая пример назначения информации о месте в соответствии с некоторыми вариантами осуществления настоящего изобретения. Фиг. 7 показывает карту 700 пространственного наложения, центроид 701 пользователя A, центроид 702 пользователя B, объект 703 посещения пользователя A и объект 704 посещения пользователя B.

[0067] Пользователь A, согласно фиг. 7, является пользователем с уже подтвержденным местом, тогда как пользователь B является пользователем, которому назначается место на основании описанных в этом документе систем и способов. Как показано на карте 700 пространственного наложения, центроид 701 пользователя A и центроид 702 пользователя B очень близки, и горизонтальные (радиальные) компоненты каждого центроида накладываются. Даже если центроид 701 пользователя A и центроид 702 пользователя B точно не совпадают (например, немного смещены сигналы GPS (посещения), сформированные их устройствами), то есть вероятность, что два пользователя находятся в одном и том же месте.

[0068] Объект 703 посещения пользователя A и объект 704 посещения пользователя B включают в себя информацию о местоположении. Информация о местоположении включает в себя ID устройства, широту, долготу, hAccuracy (горизонтальная точность по широте/долготе, в отличие от вертикальной точности по высоте), время начала и время окончания. Как показано на фиг. 7, перекрывается время, в которое пользователь A и пользователь B обнаружены в местоположениях, показанных на карте 700 пространственного наложения (например, время начала и время окончания для пользователя A составляет 10:30 и 12:32, тогда как время начала и время окончания для пользователя B составляет 10:21 и 12:43). То есть посещение пользователя B начинается лишь за несколько минут до и заканчивается лишь через несколько минут после посещения пользователя A. Как правило, чем больше совпадают времена посещения пользователей, тем более вероятно, что они встречаются.

[0069] Объект 703 посещения пользователя A дополнительно включает в себя информацию об ID места, тогда как объект 704 посещения пользователя B не включает в себя информацию об ID места. Как описано выше, информация об ID места может назначаться, когда уровень достоверности касательно надежности информации о месте превышает пороговую величину. Факторы, которые вносят вклад в надежность информации о месте, включают в себя подтверждение пользователем места (например, ручная отметка пользователем в отношении этого места) и стороннюю проверку места (например, покупки, сделанные пользователем в некотором месте). В этом примере объект 703 посещения пользователя A содержит информацию о месте, потому что система определила, что у пользователя A была надежная информация о месте.

[0070] Пользователю B можно назначить информацию о месте пользователя A на основании силы корреляции между их информацией о местоположении и их информацией о социальной связи. Как описано, описанные в данном документе системы и способы могут учитывать прочность социальных связей между A и B, как описано выше на фиг. 2 и в заявке на патент США № 15/298353, озаглавленной "System and Method for Detecting Interaction and Influence in Networks", поданной 20 октября 2016 г., содержимое которой включено в данный документ путём ссылки. Если пользователь A и пользователь B являются близкими социальными связями (например, с оценкой 0,96), и наложение информации о местоположении значительное (превышает пороговую величину достоверности), то ID места пользователя A может либо назначаться, либо предполагаться для пользователя B.

[0071] В качестве другого примера предположим группу пользователей, которые идут ресторан все вместе. Их мобильные точки местоположения смещены, производя впечатление, что они, скорее всего, находятся в другом месте через дорогу; Кроме того, есть несколько возможных мест в радиусах неопределенности тех точек местоположения. Однако один пользователь раскрывает свое местоположение (например, оплачивая счет кредитной картой или привязывая фотографию к месту), подтверждая, таким образом, свое присутствие в том конкретном ресторане. Описанная в этом документе система может определить, что первый пользователь расположен географически близко к другим субъектам, с которыми у него прочные социальные связи, и может экстраполировать, что другие субъекты находятся в том же местоположении.

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

[0073] Процессы и логические потоки, описанные в данном описании изобретения, включая этапы способа в описанном в этом документе объекте изобретения, могут выполняться одним или несколькими программируемыми процессорами, исполняющими одну или несколько компьютерных программ для выполнения функций объекта изобретения, описанного в этом документе, путем воздействия на входные данные и формирования выхода. Процессы и логические потоки также могут выполняться с помощью специализированных логических схем, и устройство описанного в этом документе объекта изобретения можно реализовать с помощью специализированных логических схем, например FPGA (программируемая пользователем вентильная матрица) или ASIC (специализированная интегральная схема).

[0074] Процессоры, подходящие для исполнения компьютерной программы, в качестве примера включают в себя как универсальные, так и специализированные микропроцессоры и любой один или несколько процессоров в любом виде цифрового компьютера. Как правило, процессор будет принимать команды и данные из постоянного запоминающего устройства или оперативного запоминающего устройства, либо из обоих. Неотъемлемыми элементами компьютера являются процессор для исполнения команд и одно или несколько запоминающих устройств для хранения команд и данных. Как правило, компьютер также будет включать в себя или функционально соединяться для приема данных или передачи данных, либо того и другого, одно или несколько запоминающих устройств большой емкости для хранения данных, например магнитные, магнитооптические диски или оптические диски. Носители информации, подходящие для воплощения команд и данных компьютерных программ, включают в себя все виды энергонезависимого запоминающего устройства, включая, в качестве примера, полупроводниковые запоминающие устройства (например EPROM, EEPROM и устройства на флэш-памяти); магнитные диски (например, внутренние жесткие диски или съемные диски); магнитооптические диски; и оптические диски (например, диски CD и DVD). Процессор и запоминающее устройство могут дополняться специализированными логическими схемами или включаться в них.

[0075] Чтобы предусмотреть взаимодействие с пользователем, описанный в этом документе объект изобретения можно реализовать на компьютере с устройством отображения, например монитором CRT (электронно-лучевая трубка) или LCD (жидкокристаллический дисплей), для отображения информации пользователю и клавиатурой и указательным устройством, например мышью или шаровым манипулятором, с помощью которого пользователь может обеспечить компьютеру входные данные. Другие виды устройств с тем же успехом могут использоваться для обеспечения взаимодействия с пользователем. Например, обеспечиваемая пользователю обратная связь может быть любым видом сенсорной обратной связи (например, визуальная обратная связь, слуховая обратная связь или осязательная обратная связь), и выходные данные от пользователя могут приниматься в любом виде, включая звуковой, речевой или осязательный ввод.

[0076] Описанный в этом документе объект изобретения можно реализовать в вычислительной системе, которая включает в себя внутренний компонент (например, сервер данных), промежуточный компонент (например, сервер приложений) или внешний компонент (например, клиентский компьютер с графическим интерфейсом пользователя или веб-обозревателем, посредством которых пользователь может взаимодействовать с реализацией описанного в этом документе объекта изобретения), или любое сочетание таких внутренних, промежуточных и внешних компонентов. Компоненты системы могут быть взаимосвязаны с помощью любой формы или носителя цифровой передачи данных, например, с помощью сети связи. Примеры сетей связи включают в себя локальную сеть ("LAN") и глобальную сеть ("WAN"), например Интернет.

[0077] Нужно понимать, что раскрытый объект изобретения не ограничивается применением к особенностям конструкции и компоновкам компонентов, излагаемым в нижеследующем описании или проиллюстрированным на чертежах. Раскрытый объект изобретения допускает другие варианты осуществления и применение на практике и осуществление различными способами. Также нужно понимать, что применяемые в этом документе формулировки и терминология предназначены для описания и не должны рассматриваться как ограничивающие.

[0078] По существу, специалистам в данной области техники будет понятно, что концепция, на которой основано данное изобретение, можно без труда использовать в качестве основы для разработки других структур, способов и систем для осуществления нескольких целей раскрытого объекта изобретения. Поэтому важно, чтобы формула изобретения рассматривалась как включающая в себя такие эквивалентные конструкции в той мере, в какой они не отклоняются от сущности и объема раскрытого объекта изобретения.

[0079] Хотя раскрытый объект изобретения описан и проиллюстрирован в вышеприведённых примерных вариантах осуществления, подразумевается, что настоящее раскрытие изобретения проведено только в качестве примера, и что могут быть внесены многочисленные изменения в подробности реализации раскрытого объекта изобретения без отклонения от сущности и объема раскрытого объекта изобретения, которые ограничены только нижеследующей формулой изобретения.

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

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

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

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

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

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

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

3. Компьютеризированный способ по п. 1, в котором:

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

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

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

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

6. Компьютеризированный способ по п. 1, в котором социальная метрика дополнительно определяется по меньшей мере одним из:

длины взаимосвязи между первым пользователем и вторым пользователем; и

взаимосвязь является личной либо профессиональной.

7. Компьютеризированный способ по п. 1, в котором пороговое значение основано по меньшей мере на одном из:

принятого порогового значения;

распределения оценок взаимосвязи, ассоциированных с множеством пользователей; и

применения алгоритма машинного обучения к множеству информации о местоположении пользователя и информации о месте пользователя.

8. Вычислительная система для определения местоположения пользователя на основании местоположений других пользователей, при этом вычислительная система содержит:

процессор; и

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

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

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

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

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

9. Вычислительная система по п. 8, в которой первый центроид ассоциирован с первой широтой и долготой, первый радиус ассоциирован с точностью местоположения первого центроида, второй центроид ассоциирован со второй широтой и долготой, и второй радиус ассоциирован с точностью местоположения второго центроида.

10. Вычислительная система по п. 8, в которой:

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

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

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

12. Вычислительная система по п. 8, в которой степень корреляции мест дополнительно основана на уровне достоверности, назначенном информации о месте второго пользователя.

13. Вычислительная система по п. 8, в которой социальная метрика дополнительно определяется по меньшей мере одним из:

длины взаимосвязи между первым пользователем и вторым пользователем; и

взаимосвязь является личной либо профессиональной.

14. Вычислительная система по п. 8, в которой пороговое значение основано по меньшей мере на одном из:

принятого порогового значения;

распределения оценок взаимосвязи, ассоциированных с множеством пользователей; и

применения алгоритма машинного обучения к множеству информации о местоположении пользователя и информации о месте пользователя.

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

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

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

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

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

16. Постоянный машиночитаемый носитель по п. 15, в котором первый центроид ассоциирован с первой широтой и долготой, первый радиус ассоциирован с точностью местоположения первого центроида, второй центроид ассоциирован со второй широтой и долготой, и второй радиус ассоциирован с точностью местоположения второго центроида.

17. Постоянный машиночитаемый носитель по п. 15, в котором:

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

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

18. Постоянный машиночитаемый носитель по п. 17, в котором степень корреляции мест основана на величине наложения между длительностью первого пользователя и длительностью второго пользователя.

19. Постоянный машиночитаемый носитель по п. 15, в котором степень корреляции мест дополнительно основана на уровне достоверности, назначенном информации о месте второго пользователя.

20. Постоянный машиночитаемый носитель по п. 15, в котором социальная метрика дополнительно определяется по меньшей мере одним из:

длины взаимосвязи между первым пользователем и вторым пользователем; и

взаимосвязь является личной либо профессиональной.