Story Transcript
OFICINA ESPAÑOLA DE PATENTES Y MARCAS
19
ESPAÑA
Número de publicación:
21
Número de solicitud: 201230075
51
Int. CI.:
H04W 4/02
Fecha de presentación:
71
20.01.2012 43
(2009.01)
SOLICITUD DE PATENTE
12
22
2 427 690
11
TELEFONICA, S.A. (100.0%) GRAN VIA, N.28 28013 MADRID ES
Fecha de publicación de la solicitud: 31.10.2013
Solicitantes:
72
Inventor/es: LARA, Rubén; MARTÍNEZ, Rocío; RODRÍGUEZ, Miguel Ángel; MARTÍN, Alberto y ARMENTA, Ana
74
Agente/Representante: ARIZTI ACHA, Monica
54
Título: MÉTODO PARA LA DETECCIÓN Y ETIQUETADO AUTOMÁTICO DE PUNTOS DE INTERÉS DE USUARIO
ES 2 427 690 A2
57 Resumen: Método para la detección y etiquetado automático de puntos de interés de usuario. El método comprende adquirir información de señales intercambiadas entre dispositivos móviles de un usuario y una pluralidad de estaciones de transceptor base, o BTS, analizar dicha información adquirida para determinar, durante un periodo de tiempo, las ubicaciones de dicho dispositivo móvil del usuario y deducir a través de un modelo estadístico los puntos de interés, identificando y etiquetando al menos parte de dichas ubicaciones determinadas por dicho dispositivo móvil del usuario como puntos de interés.
A2
ES 2 427 690 A2 DESCRIPCIÓN
MÉTODO PARA LA DETECCIÓN Y ETIQUETADO AUTOMÁTICO DE PUNTOS DE INTERÉS DE USUARIO
Campo de la técnica
5
La presente invención se refiere, en general, a un método para detectar y etiquetar automáticamente uno o más puntos de interés (PoI) de un usuario de servicios telefónicos móviles, basándose dicho método exclusivamente en información de uso telefónico geolocalizada y sin interacción del cliente. Basándose en los eventos de uso geolocalizados generados en la red de operador de telecomunicaciones y
10
usando métodos estadísticos, la invención permite la identificación, a partir de todas las ubicaciones visitadas por el usuario, de las ubicaciones más relevantes para él: sus PoI. Además, la invención asigna automáticamente etiquetas a los PoI detectados, aportando así un significado a tales ubicaciones.
15
Antecedentes de la invención El estudio de patrones de movilidad humana ha recibido una atención creciente en los últimos años, especialmente debido al aumento en la disponibilidad de datos de ubicación procedentes tanto de sistemas de posicionamiento global (GPS) como del uso del teléfono móvil, que deja registros geolocalizados en las redes del operador.
20
Entender cómo y cuando tienen lugar movimientos humanos por poblaciones, ciudades o países es de interés en muchas áreas, tales como gestión de tráfico, diseño de redes de transporte o control de propagación de enfermedades. Sin embargo, no sólo es de interés una vista global de flujos de población, sino también los patrones de movilidad individual de un usuario, en varios campos. El conocimiento
25
de qué ubicaciones visita un usuario periódicamente, durante qué periodo, con qué frecuencia, qué días de la semana y en qué momentos del día, etc. pueden aprovecharse para proporcionar servicios contextuales, publicidad relevante, ofertas controladas para afrontar las necesidades de movilidad particulares del usuario, planificación de itinerarios. En general, conocer las ubicaciones relevantes para un
30
usuario puede permitir
la personalización
de interacciones
de servicios
y
comunicaciones comerciales y mejorar su relevancia. Con el fin de estimar PoI es necesario suponer que los movimientos humanos siguen algún patrón y, por tanto, la ubicación de un usuario es en cierta medida previsible. En este sentido, varios autores han trabajado recientemente en la
35
previsibilidad de patrones de movilidad humana intentando hallar los límites de tal
2
ES 2 427 690 A2
previsibilidad. Basándose en el estudio de la trayectoria de 100.000 usuarios de teléfono móvil anónimos cuya posición fue objeto de seguimiento durante un periodo de seis meses, se halló en [1] que las trayectorias humanas muestran un alto grado de regularidad espacial y temporal, estando cada individuo caracterizado por una
5
distancia de desplazamiento característica independiente del tiempo y una probabilidad significativa de volver a algunas pocas ubicaciones altamente frecuentadas. La referencia [2] intenta contestar a la pregunta de “¿Hasta qué punto es previsible el comportamiento humano?” estudiando los patrones de movilidad de
10
usuarios de teléfono móvil anónimos. Los autores midieron la entropía de la trayectoria de cada individuo, y hallaron un 93% de previsibilidad potencial en la movilidad de usuario por toda la base de usuario. También hallaron una falta considerable de variabilidad en la previsibilidad, en gran parte independiente de la distancia que los usuarios cubren de manera regular.
15
Los modelos de predicción de ubicación desarrollados en los últimos años tienen en cuenta comportamientos individuales y colectivos. Como por ejemplo en [3] , en el que un modelo se basa en la trayectoria pasada de la persona y las características geográficas de la zona en la que se mueve la colectividad, tanto en términos de ocupación del suelo, puntos de interés y distancia de los viajes.
20
El método de predicción puede afrontarse de diferentes formas, [4] por ejemplo, presenta una predicción de ubicación y permanencia usando estimación de densidad de núcleo (KDE, Kernel Density Estimation) basándose en información de comunicación, proximidad, ubicación y actividad de los sujetos. El comportamiento de comunicación colectivo también se ha usado para
25
detectar la aparición de eventos anómalos como en [5] donde se estudia cómo pueden describirse anomalías espacio-temporales usando herramientas de la teoría de percolación convencional. Los patrones de movilidad humana también se han deducido a partir de registros de GPS [6] donde se propone un método de agrupamiento para extraer los
30
principales puntos de interés, denominados geolocalizaciones, a partir de datos de GPS. Partiendo de geolocalizaciones proponen una definición de comunidad, la geocomunidad, que capta la relación entre una descripción espacial de movimientos humanos y el contexto social en el que viven los usuarios. Un análisis estadístico de las principales características de los trayectos humanos proporciona las distribuciones
35
adecuadas de las distancias cubiertas por personas dentro de una geolocalización y
3
ES 2 427 690 A2
entre geolocalizaciones y tiempo de descanso. También analizan factores que influyen en las personas cuando eligen ubicaciones sucesivas en su movimiento. La referencia [7] da a conocer un estudio de la movilidad en un mapa de consciencia de actividad que describe la actividad más probable asociada con una
5
zona de espacio específica. Esto les permite captar el patrón de actividad diaria individual y analizar las correlaciones entre el perfil de la zona de trabajo de diferentes personas. Para este fin entienden la ubicación de trabajo de cada usuario como la parada más frecuente durante las horas del día. Basándose en un gran volumen de datos de teléfono móvil de casi un millón de registros de los usuarios en la zona
10
metropolitana central de Boston, hallaron una fuerte correlación en los patrones de actividad diaria dentro del grupo de personas que comparten un perfil de zona de trabajo común. Además, dentro del propio grupo, la similitud en los patrones de actividad disminuye a medida que sus lugares de trabajo se separan. Algunos autores [8] se centran en modelos de movilidad centrada humana, es
15
decir, cómo las redes sociales y los patrones de movilidad coinciden entre sí, intentando extender la movilidad de la red social a los movimientos geográficos, que denominan “redes oportunistas”. Así, la comunidad científica está trabajando e investigando sobre la movilidad humana como tema, y varios enfoques proporcionan un mejor conocimiento de
20
diferentes aspectos de la movilidad humana, pero desde la perspectiva de su aprovechamiento para la personalización, y lo que más nos importa es conocer cuándo y con qué fin los usuarios visitan frecuentemente determinadas ubicaciones, es decir, cuáles son los puntos de interés de los usuarios. Diferentes invenciones se basan en el tema de los PoI para diferentes fines:
25
El documento US2010121803 “Predictive ephemeral Points of Interest”, a los usuarios de una aplicación inalámbrica se les proporciona la capacidad de registrar ubicaciones y recuperar mapas de ubicaciones pasadas y predecir ubicaciones futuras de interés específico. Dentro de esta invención, para predecir una ubicación, se recopilan datos acerca de ubicaciones notificadas previas, y se usa un análisis
30
estadístico para presentar una guía visual que halle los PoI en un momento particular en el futuro. El documento WO2011076988 “Methods and apparatus for grouping points of interest according to area names”, se proporciona un enfoque para la búsqueda y el agrupamiento en masa de puntos de interés basándose en información de mensajes
35
de difusión de célula. Se produce, al menos en parte, la recepción de un mensaje
4
ES 2 427 690 A2
desde un terminal móvil. El mensaje especifica información de punto de interés y un nombre de zona asociado correspondiente a una de una pluralidad de células de una red de comunicación. El mensaje se analiza sintácticamente para determinar la información de punto de interés y el nombre de zona asociado.
5
El documento WO2011072882, un método para evaluar un atributo de un punto de interés comprende asociar una región con el punto de interés y evaluar el atributo según una comparación de los datos de posición de una pluralidad de usuarios con datos de posición que definen la región asociada. El documento US2011166957 “Biasing of search result clustering to ensure
10
more effective point of interest targeting”: pueden proporcionarse resultados de servicio de directorio en respuesta a una petición de un producto o proveedor de servicios deseado basándose en una o más ubicaciones seleccionadas por el usuario. El usuario puede buscar un producto o proveedor de servicios deseado que esté próximo a una ubicación desde la que el usuario puede comenzar el desplazamiento al
15
punto de interés, denominada ubicación de origen, y satisface un objetivo beneficioso para el usuario (por ejemplo, una preferencia de desplazamiento direccional). El documento US2010023259 “Discovering points of interest from users map annotations”. Un método que facilita la generación de un punto de interés en relación con un mapa. Un componente de interfaz puede recopilar una parte de datos de
20
anotación de dos o más usuarios, en el que la parte de datos de anotación está asociada con un mapa digital e incluye al menos una ubicación de mapa y una descripción específica del usuario de la ubicación de mapa. Un agregador de anotaciones puede evaluar datos de anotación correspondientes a la ubicación de mapa en el mapa digital. El agregador de anotaciones puede crear un punto de interés
25
para la ubicación de mapa basándose en la evaluación y rellena el mapa digital con al menos una ubicación identificada extraída de dos o más usuarios. El documento US2003191578 “Method and System for providing reminders about points of interests while travelling”. Un sistema de navegación incluye una característica que permite que un usuario especifique un tipo de punto de interés y
30
reciba entonces un recordatorio cuando el usuario está en la proximidad de una ubicación del punto de interés del tipo especificado mientras se desplaza en una región geográfica. El documento US2009097710 “Methods and system for communication and displaying points-of-interest”. Un método para visualizar ubicaciones de coordenadas
5
ES 2 427 690 A2
de puntos de interés en imágenes en perspectiva y para transferir información basada en coordenadas. El documento US2008076451 “Point of Interest Spatial Rating Search Method and System”. Un sistema y método para buscar y recuperar la información de
5
ubicación asociada con uno o más puntos de interés, por lo que los criterios de búsqueda pueden depender de la ubicación de un punto de interés con respecto a la posición en tiempo real del usuario, y cualquier preferencia o restricción de búsqueda seleccionada por el usuario, tal como información de valoración acerca del punto de interés.
10
El documento US7890254 “Point of Interest Display System”. Un sistema de visualización de puntos de interés incluye una base de datos actualizable que se comunica con un microprocesador que recibe datos desde un receptor GPS que proporciona al sistema la ubicación actual del vehículo y una dirección de información de desplazamiento.
15
El documento US2004236504 “Vehicle Navigation Point of Interest”. La presente invención proporciona un sistema de navegación para ayudar a localizar puntos de interés durante la navegación del vehículo. El sistema incluye un procesador habilitado por software para recibir y almacenar una selección de usuario de puntos de visita preferidos y un tiempo seleccionado por el usuario y determinar e indicar un
20
subconjunto de los puntos de visita preferidos que se localizan dentro de una ubicación predeterminada con respecto a la posición del vehículo en el tiempo seleccionado por el usuario o con respecto a un destino seleccionado. El documento US2011125359 “Navigation Apparatus, Server Apparatus and Method of Providing Point of Interest Data”. Un aparato de navegación incluye una
25
interfaz de comunicaciones para comunicar datos a través de una red de comunicaciones y un recurso de procesamiento acoplado a la interfaz y que se dispone para recibir una petición de información de puntos de interés, y para comunicar a través de la interfaz de comunicaciones un mensaje que constituye una petición de datos de puntos de interés para la recepción por un servidor remoto.
30
El documento WO2011072745 “Dynamic Point of Interest Suggestion”. Un sistema, método y dispositivo para recomendar un POI a través de un dispositivo de navegación que incluye recibir una recomendación de un POI desde un tercero en un servidor y determinar información relacionada con el POI. La información determinada se correlaciona con datos relacionados con dispositivos de navegación asociados con
35
el servidor. Los dispositivos de navegación se seleccionan para recibir el POI
6
ES 2 427 690 A2
recomendado por un tercero basándose en resultados de la correlación de la información determinada con los datos relacionados con los dispositivos de navegación y el POI recomendado se reenvía desde el servidor a un dispositivo de navegación objetivo basándose en resultados de la correlación de la información
5
determinada con los datos relacionados con los dispositivos de navegación. El documento EP1939797 “Method and apparatus for automatically determining a
semantic
classification
of
context
data”.
Un
método
para
determinar
automáticamente una clasificación semántica para datos de contexto obtenidos por un dispositivo móvil, comprendiendo dicho método muestrear mediante dicho dispositivo
10
móvil uno o más flujos de datos de contexto a lo largo del tiempo; aplicar un algoritmo de agrupamiento para identificar uno o más agrupamientos en los datos de contexto muestreados; ejecutar un motor lógico para determinar automáticamente un nombre de concepto a partir de un conjunto de nombres de concepto predefinidos como una clasificación semántica de dichos uno o más agrupamientos; asignar dicho nombre de
15
concepto a dichos uno o más agrupamientos o sugerir dicha asignación al usuario. Problemas con las soluciones existentes Como se observa, puntos de interés es una expresión a la que hacen referencia varios trabajos existentes. La mayoría de ellos usan datos de GPS, y la
20
información acerca de los PoI se recopila a partir de usuarios particulares, se propone y visualiza, o se calculan rutas entre PoI dados. Pero en todos los trabajos en los que se mencionan PoI que deben calcularse, las ubicaciones relevantes deben darse o bien por el usuario o bien por un sistema de navegación. Por
25
ejemplo,
las
invenciones
US2009097710
y
US7890254
trabajan
respectivamente en un método y un sistema para visualizar el punto de interés. El documento US2010121803 recopila datos acerca de ubicaciones notificadas previamente y usa el análisis estadístico para presentar una guía visual para hallar los PoI en un momento particular en el futuro, los documentos US2004236504 y WO2011072745 trabajan en una sugerencia de puntos de interés dinámica para
30
dispositivos de navegación, y el documento US2011125359 consiste en un sistema remoto de petición de datos de puntos de interés. Basándose en la evaluación de datos anotados por el usuario el documento US2010023259 crea puntos de interés para ubicaciones de mapa, y según el documento US2008076451 la ubicación de usuario proporciona un método de
35
búsqueda de puntos de interés mientras que el documento US2003191578 genera un
7
ES 2 427 690 A2
recordatorio cuando el usuario está en la proximidad del punto de interés. El documento WO2011072882 también trabaja con la información de ubicación de un punto de interés y comparándolo con una región asociada evalúa un atributo del propio punto de interés.
5
Por el documento US2011166957 se aplican técnicas de clasificación para agrupar y así garantizar la selección puntos de interés más eficaz entre las ubicaciones seleccionadas por el usuario, por el documento WO2011076988 se agrupan los puntos de interés según nombres de zonas, y también por el documento EP1939797 que proporciona un método para determinar automáticamente una
10
clasificación semántica para datos de contexto obtenidos por un dispositivo móvil. Varias referencias como [2][3][4][5] también trabajan con registros de detalle de llamada (CDR) o datos de GPS [6] y construyen modelos predictivos, pero éstos son experimentos habitualmente aislados llevados a cabo para una población específica y no comprenden una detección y etiquetado completamente automático de las
15
ubicaciones más relevantes para un usuario. También se han encontrado muchas invenciones que están de alguna manera relacionadas con los PoI. Algunas de ellas recopilan información directamente de los usuarios, otras registran las ubicaciones previamente visitadas (a través de GPS), y muchas se centran en sistemas de visualización de POI para navegación GPS.
20 Sumario de la invención Es necesario ofrecer una alternativa al estado de la técnica que cubra las lagunas encontradas en la misma, particularmente relacionadas con la falta de propuestas que realmente presenten un método eficaz para detectar y etiquetar
25
automáticamente y de una manera no intrusiva los PoI de servicios móviles de usuario. Para ello, la presente invención proporciona un método para detectar y etiquetar PoI, basándose dicho método exclusivamente en información de uso telefónico geolocalizada y sin interacción del cliente. El método de la invención comprende:
30
a) adquirir información de señales intercambiadas entre dispositivos móviles de usuario y una pluralidad de estaciones base, o BTS; b) analizar dicha información adquirida para determinar, durante un periodo de tiempo, las ubicaciones de dicho dispositivo móvil del usuario basándose en las ubicaciones de las BTS con las que se ha producido el intercambio de
35
dichas señales; y
8
ES 2 427 690 A2
c) detectar y etiquetar al menos parte de las ubicaciones determinadas por dicho dispositivo móvil del usuario como puntos de interés al menos basándose en el número de veces que dicho dispositivo móvil del usuario ha estado en dichas ubicaciones determinadas durante dicho periodo de
5
tiempo, en el que dichas etapas b) y c) comprenden aplicar dicho análisis e identificación a través de un modelo estadístico. Este modelo estadístico según una realización comprende un algoritmo de agrupamiento por partición alrededor de medoides, o PAM, basándose en una
10
distancia de Pearson. El algoritmo de agrupamiento mencionado devuelve veinte representaciones diferentes de agrupamientos. Las representaciones de agrupamientos se representan por su curva medoide y se etiquetan considerando hábitos sociales y características culturales de la región
15
en estudio. Otras características del método de la invención se describen según las reivindicaciones adjuntas 2 a 10, y en una sección posterior en relación con la descripción detallada de varias realizaciones. El método de la invención comprende además limitar la adquisición de información desde el dispositivo móvil del usuario por
20
un umbral superior y uno inferior. Dicho método, comprende filtrar cada una de dichas BTS para cada uno de dicho dispositivo móvil del usuario cuando la comunicación entre los mismos es inferior a un umbral. Asimismo, la adquisición de información de la etapa a) anterior, comprende además para cada par usuario-BTS relevante, un vector que contiene dichas ubicaciones para cada hora de los días de la semana. El modelo
25
estadístico empleado comprende además un algoritmo de agrupamiento por partición alrededor de medoides, o PAM, basándose en una distancia de Pearson, de manera que dicho algoritmo de agrupamiento devuelve veinte representaciones diferentes de agrupamientos. Las representaciones de agrupamientos se representan mediante su curva centroide y se etiquetan considerando hábitos sociales y características
30
culturales de la región en estudio. Para identificar puntos de interés teniendo en cuenta los hábitos y dichas características culturales de la región se usa un primer conjunto de 20 etiquetas, y a partir de dicho primer conjunto de 20 etiquetas se usa un segundo conjunto de 5 etiquetas para identificar dichos puntos de interés basándose en aplicaciones prácticas. La adquisición de información de la etapa a) incluye el número
9
ES 2 427 690 A2
de dicho dispositivo móvil del usuario, la fecha y hora, y la BTS asociada a dichas señales intercambiadas. Breve descripción de los dibujos
5
Las anteriores y otras ventajas y características se entenderán de manera más completa a partir de la siguiente descripción detallada de realizaciones, con referencia a los dibujos adjuntos, que deben considerarse de una manera ilustrativa y no limitativa, en los que: La figura 1 muestra el esquema actual usado para la localización de los puntos
10
de interés. La figura 2 muestra el esquema actual usado para la localización de los puntos de interés basándose en información geolocalizada. La figura 3 muestra los diferentes procesos que van a realizarse para estimar el modelo estadístico.
15
La figura 4 muestra un ejemplo de casos de uso y aplicaciones que pueden realizarse conociendo puntos de interés de los usuarios, según una realización de la presente invención. La figura 5 muestra una posible inclusión de la invención en terceros para la correcta personalización de sus campañas de marketing o actividades comerciales,
20
según una realización de la presente invención. La figura 6 muestra un ejemplo de un vector de uso de varias BTS, según una realización de la presente invención. La figura 7 muestra un ejemplo de un conjunto de agrupamientos, representado cada uno por su curva medoide, según una realización de la presente invención.
25 Descripción detallada de varias realizaciones La invención trabaja sobre eventos geolocalizados obtenidos a partir de la red del operador de una manera no intrusiva durante un periodo de tiempo dado, captando cualquier registro geolocalizado que deja el uso de teléfonos móviles en la red, a partir
30
de la señalización (eventos de entrada en/salida de sesiones de datos, inicio y terminación de llamadas de voz, envío de SMS, etc.). Esta información adquirida, es decir, eventos geolocalizados, deben contener al menos la siguiente información: - El número asociado al evento - La fecha y hora para el evento
35
- La BTS asociada al evento
10
ES 2 427 690 A2
Cuando se habla acerca de llamadas de voz, los CDR contienen (para cada cliente del operador): - El número que realiza la llamada - El número que recibe la llamada
5
- Fecha y hora de la llamada - Duración de la llamada - La BTS en la que comienza la llamada - LA BTS en la que finaliza la llamada La invención consiste en una serie de procesos que basándose en información
10
geolocalizada llevan a los puntos de interés de los clientes que generaron esa información geolocalizada. 1. Recopilación de información de ubicación Procesando una determinada cantidad de registros de señalización (por
15
ejemplo, CDR) se obtienen eventos (en el caso de CDR, llamadas) relacionados con cada cliente durante el periodo de tiempo cubierto, y como se dispone del evento fecha, hora y BTS, también se obtiene el número de eventos para cada BTS que el cliente ha estado usando durante los días del periodo.
20 Un identificador de BTS se enlaza a un punto geográfico, de manera más precisa a la zona geográfica cubierta por la estación base. Así, tener la cuenta de eventos para cada BTS significa que se tiene la cuenta de eventos para cada ubicación que visitó el cliente (cada ubicación en la que el cliente realizó o recibió una
25
llamada en el caso de CDR).
2. Filtros de comunicación de clientes
30
Este método usa métodos estadísticos para construir los modelos de movilidad que entre otras cuestiones extraen la comunicación más característica por patrones BTS por la base del cliente. Con el fin de permitir modelos estadísticos fiables y extensibles, se eliminan por filtrado los casos en los que el comportamiento de comunicación parece demasiado extremo para su modelado, esto es, los clientes que
11
ES 2 427 690 A2
hablan mucho o muy poco (en general, por cada ubicación que visitan), o eventos que no pueden modelarse ya que no responden a un patrón de uso de BTS común. Esto es sólo considerando los casos en los que la comunicación global (número de eventos en general) está limitada por un umbral superior y uno inferior:
5 3. Filtro de uso de BTS Para cada cliente también se elimina por filtrado cada BTS que no alcanza un umbral de comunicación representativo TR. Este umbral puede expresarse como una
10
cantidad absoluta de eventos geolocalizados, como un porcentaje de los eventos geolocalizados de cliente, o como una combinación de ambos. Para el caso de un umbral dado por un porcentaje:
15
4. BTS relevante Los pares cliente-BTS que permanecen tras las dos fases de filtrado son lo que se denomina las “BTS relevantes”. Para cada cliente se tiene un conjunto de BTS que representan las ubicaciones en las que el cliente comunica (o registra cualquier tipo de eventos) al menos los necesarios para modelarse.
20
Cliente1 {BTS11,BTS21,....BTSn1} Cliente2 {BTS12,BTS22,....BTSn2} ..... Clientem {BTS1m,BTS2m,....BTSnm} Modelos de análisis de movilidad
25
Con el fin de explicar mejor los modelos de análisis de movilidad se realiza un acercamiento de los componentes del diagrama de bloques presentado anteriormente. Las casillas numeradas se explican en los siguientes párrafos. 5. Vectores de uso cliente-BTS
30
Para cada par “cliente-BTS relevante”, se construye un vector que contiene el número de posiciones registradas (llamadas o en general, cualquier tipo de eventos geolocalizados Nge) de cada uno de los clientes en cada una de las BTS para cada hora de los días de la semana. Pero como no cada día de la semana tiene el mismo
12
ES 2 427 690 A2
significado en cuanto a patrones de actividad diaria, se agrupa lunes, martes, miércoles y jueves mientras que viernes, sábado y domingo permanecen separados. {Cliente1,BTS11}{Ngemt00,...,Ngemt23,
Ngefr00,...,Ngefr23,
Ngest00,...,Ngest23,
Ngefr00,...,Ngefr23,
Ngest00,...,Ngest23,
Ngefr00,...,Ngefr23,
Ngest00,...,Ngest23,
Ngesn00,...,Ngesn23}
5
{Cliente1,BTS21}{Ngemt00,...,Ngemt23, Ngesn00,...,Ngesn23} ..... {Cliente1,BTSn1}{Ngemt00,...,Ngemt23, Ngesn00,...,Ngesn23}
10
Así, para cada cliente se obtienen varias curvas, tantas como BTS relevantes que recopilan el patrón de comunicación de ese cliente sobre sus BTS representativas por los cuatro diferentes tipos de días. Es lo que se denomina vectores de uso de BTS. La figura 6 muestra varios ejemplos de vector de uso de BTS. Hacen referencia al cliente X, y contienen la cuenta agregada de llamadas que el cliente X realiza o
15
recibe a través de las bts1, bts2 y bts3 respectivamente a intervalos de 24 horas de lunes a jueves (mt00-mt23), los viernes (fr00-fr23), sábados (st00-st23) y domingos (sn00-sn23). 6. Normalizaciones Se realiza una primera normalización dividiendo cada valor por el número de
20
días del correspondiente tipo presente en el periodo de tiempo en consideración. Esta normalización permite comparar las 4 partes diferentes de las curvas entre sí: {Cliente1,BTS1}’ = {Cliente1,BTS1}/{Nmt,Nfr,Nst,Nsn} donde Nmt es el número de lunes, martes, miércoles y jueves durante el periodo de
25
tiempo considerado; Nfr es el número de viernes durante el periodo de tiempo considerado; Nst es el número de sábados durante el periodo de tiempo considerado; Nsn es el número de domingos durante el periodo de tiempo considerado. {Cliente1,BTS1}’ = {Ngemt00/Nmt ,...,Ngemt23/Nmt,
30
Ngefr00/Nfr,...,Ngefr23/Nfr, Ngest00/Nst,...,Ngest23/Nst, Ngesn00/Nsn,...,Ngesn23/Nsn } {Cliente1,BTS1}’ = {N’gemt0,...,N’gemt23, N’gefr00,...,N’gefr23,
35
N’gest00,...,N’gest23,
13
ES 2 427 690 A2
N’gesn00,...,N’gesn23} Tras esta primera normalización, es necesario realizar una segunda. Con el fin de hacer posible la comparación entre diferentes curvas de uso de BTS con niveles de comunicación media muy diferentes, y para poder centrarse en la propia forma de la
5
curva (y no sólo en los niveles de amplitud), las curvas también se normalizan dividiéndolas por la suma de valores para cada punto y danto así una suma resultante igual a 1:
={Cliente1,BTS1}’/
{Cliente1,BTS1}’’={Cliente1,BTS1}’/
{Cliente1,BTS1}’’ = {N’gemt00/N’t,...,N’gemt23/N’t, N’gefr00/N’t,...,N’gefr23/N’t,
10
N’gest00/N’t,...,N’gest23/N’t, N’gesn00/N’t,...,N’gesn23/N’t} Donde
15
7. Muestra Entonces se extrae una muestra representativa de los vectores de uso de BTS
20
normalizados para alimentar un método de clasificación no supervisado para identificar las principales clases de patrones de uso de BTS. 8. Agrupamiento Existen varias posibles implementaciones para el método de clasificación; una
25
opción es usar un algoritmo de agrupamiento como por ejemplo, un método de partición alrededor de medoides (PAM) basándose en una distancia de Pearson. Agrupamiento PAM El agrupamiento por partición alrededor de medoides (PAM) puede
30
considerarse una versión más robusta del enfoque de k-medios clásico. Se describe
14
ES 2 427 690 A2
en el capítulo 2 del libro “Finding Groups in Data: An Introduction to Cluster Analysis”, Kaufman & Rousseeuw, 1990. Tiene algunas características deseables: •
Puede trabajar directamente sobre un conjunto de datos, pero también acepta una matriz de disimilitud de esos datos como
5
entrada. •
Es más robusta que k-medios ya que minimiza una suma de disimilitudes en lugar de una suma de distancias euclidianas cuadradas.
10
El algoritmo PAM se basa en la búsqueda de k objetos representativos (medoides) entre las observaciones del conjunto de datos. Estas observaciones deben representar la estructura de los datos. Tras hallar un conjunto de k medoides, se construyen k agrupamientos asignando cada observación a su objeto representativo más próximo, basándose en una distancia dada. En el caso de nuestra invención se
15
usa una distancia de Pearson. Un medoide puede definirse como el objeto de un agrupamiento cuya disimilitud promedio con respecto a todos los objetos en el agrupamiento es mínima. Por defecto, no se especifica el conjunto inicial de medoides. El algoritmo en primer lugar busca un buen conjunto inicial de medoides (fase de construcción).
20
Después halla un mínimo local para la función objetivo (fase de cambio). Distancia de Pearson Si tenemos muestras de dos variables X e Y, es muy común calcular el coeficiente de correlación de Pearson de muestra para revelar si existe una relación
25
lineal entre las dos variables:
Este coeficiente siempre está entre -1 y 1. Es 1 si existe una relación lineal positiva perfecta entre las dos variables, y es -1 si existe una relación lineal negativa perfecta.
30
Una expresión equivalente da el coeficiente de correlación como la media de los productos de las puntuaciones estándar:
15
ES 2 427 690 A2
donde sx y sy son la desviación estándar de muestra de X e Y. La correlación de Pearson puede tomarse como una medida de similitud entre los datos por pares (Xi, Yi). Así también se puede obtener una correlación basada en la distancia como una expresión de la disimilitud entre ese vector de datos:
5 El mayor valor de esta distancia será 2 cuando los vectores puedan considerarse “opuestos”, y los valores más bajos serán 0 cuando los vectores puedan considerarse como que tienen la misma forma o perfil (si se representan en secuencia).
10
La invención usa un método de agrupamiento PAM basándose en una distancia de Pearson para agrupar las diferentes curvas {Cliente, BTSi} en varias clases siguiendo una estrategia no supervisada. El resultado del método de agrupamiento es un conjunto de clases de vectores de uso de BTS, estando representada cada una de las clases por su medoide. Las
15
clases resultantes deben ser lo más diferentes entre ellas como sea posible pero los vectores pertenecientes a la misma clase deben ser lo más similares posible. Las similitudes se consideran según la distancia dada, en este caso la de Pearson. 9. Agrupamientos, medoides y centroides
20
El proceso de agrupamiento intenta cubrir tanta variabilidad como sea posible en el sentido de detectar muchos grupos diferentes para los patrones de comunicación de BTS relevante. Esto es por lo que inicialmente se trabaja con un número relativamente alto de agrupamientos. Por ejemplo, en una de las implementaciones, el algoritmo de agrupamiento
25
debe devolver 20 clases diferentes. La figura 7 muestra un conjunto de agrupamientos, representado cada uno por su curva medoide. 10. Etiquetado de medoide
30
Una vez que se obtienen el medoide y centroide para cada clase se asigna una etiqueta diferente a los mismos teniendo en cuenta los hábitos sociales y características culturales de la región en estudio. En este caso el algoritmo daría 20 etiquetas diferentes para etiquetas de “nivel 0” (el conjunto más amplio de etiquetas). Considerando los patrones de los representantes de clases se agrupan más adelante
35
en 5 etiquetas de “nivel 1”.
16
ES 2 427 690 A2
El siguiente cuadro de texto muestra un conjunto de ejemplo de etiquetas de nivel 0 creadas para los agrupamientos de uso de BTS:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
5
trabajo (tarde comercial) ocio de vida nocturna ocio de sábado por la noche ocio de domingo por la noche ocio de viernes por la noche trabajo (oficina, por la mañana) trabajo (comercial) trabajo lunes-jueves (hora de almuerzo) ocio de domingo por la noche compra por la tarde días de trabajo casa compra sábado por la mañana ocio por la noche de días de trabajo trabajo (tarde) ocio de domingo por la tarde ocio de sábado por la tarde (compra) ocio de viernes por la tarde compra por la tarde compra de viernes por la tarde (almuerzo viernes, salir de casa) ocio de viernes por la noche
Y como se mencionó anteriormente, se crea un conjunto de “nivel 1” de etiquetas pensando en aplicaciones prácticas que no necesitarían tal detalle: 1 2 3 4 5
trabajo de oficina trabajo comercial casa/ocio por la noche noche/ocio por la noche ocio por la tarde/compra
11. Medidas de dispersión entre clases
10
La distancia de Pearson para el representante de agrupamiento (medoide) se analiza para cada agrupamiento, para obtener el promedio y la desviación estándar de la distancia al centro de agrupamiento para cada elemento clasificado. Tales valores se usan más adelante para decidir acerca de la precisión de clasificación de POI, para observar si asignar o no una etiqueta de punto de interés.
15 12. Resultados del modelo •
La distancia
17
ES 2 427 690 A2
o
Una función que implementa la distancia, necesita aplicarse cada vez que necesitamos asignar automáticamente una etiqueta POI a una nueva instancia (vector de comunicación normalizado)
•
5
Conjunto medoide: o
•
•
10
Representantes de agrupamientos: 96 vectores de posición
Conjunto umbral o
Distancia promedio dentro de cada agrupamiento
o
Distancia de desviación estándar
Conjunto de etiqueta (etiquetas POI) o
Conjuntos de etiquetas de nivel 0
o
Conjuntos de etiquetas de nivel 1
o
Tabla de correspondencia
13. Uso del modelo
15
Para cualquier vector de cliente-uso de BTS (presente en la muestra o no) asignamos la etiqueta de “nivel 0” del centroide más próximo en cuanto a la misma distancia que se ha usado en el proceso de agrupamiento (en este caso la distancia de Pearson). La etiqueta de “nivel 1” equivalente también se asigna basándose en el
20
conocimiento de la etiqueta de “nivel 0” y en la tabla de correspondencia. Para algunos casos, la instancia (vector cliente-uso de BTS que se etiqueta automáticamente) y el centroide son muy similares y las etiquetas de “nivel 0” son una buena elección. Pero esto no siempre ocurre, y las etiquetas de nivel 1 representan un etiquetado más general, con un margen de error inferior.
25
Una posibilidad de la asignación de las etiquetas es usar el valor de la distancia promedio y la desviación estándar de distancia para obtener un umbral para decidir cuál de las etiquetas debe usarse. Por ejemplo, si Distancia({Cliente,BTSi},Centroide) > Avg(distancia) + stdDev(distancia)
30
entonces el vector está alejado del centro de agrupamiento, así no es lo suficientemente fiable y puede ser que no se quiera proporcionar esa etiqueta. Para ese caso podemos por ejemplo devolver un código que implique que el agrupamiento y la etiqueta obtenidos no son lo suficientemente fiables. Para los casos en los que
18
ES 2 427 690 A2
Avg(distancia)
<
Distancia({Cliente,BTSi},Centroide)
<
Avg(distancia)
+
stdDev(distancia) Puede decirse que el vector no está ni demasiado lejos ni demasiado cerca del centro de agrupamiento. En este caso podemos considerar que el agrupamiento
5
asignado no es lo suficientemente fiable para devolver la etiqueta de nivel 0 y en su lugar puede considerarse sólo la etiqueta de nivel 1. Y para el resto de los casos en los que Distancia({Cliente,BTSi},Centroide) < Media(distancia) El vector está lo suficientemente cerca del centroide de agrupamiento y la
10
etiqueta de nivel 0 parece ser una solución aceptable para el proceso de etiquetado de puntos de interés automático. Esta invención permite que un cliente tenga varios POI con la misma etiqueta. En algunos casos, podemos modificar una de las etiquetas produciendo nuevas etiquetas de nivel 1 especializadas. Por ejemplo, un cliente puede tener más de una
15
ubicación etiquetada como “casa”. Teniendo en cuenta otra información como la zona habitual de actividad del cliente durante días de la semana y fines de semana, y calculada durante el periodo de tiempo dado, uno de esos POI puede etiquetarse como “2da residencia”. En estos casos el conjunto de etiquetas de nivel 1 iniciales se expande por la adición de nuevas etiquetas especializadas.
20 14. Punto de interés Finalmente, como un resultado de nuestra invención obtenemos para cada cliente: -
25
Un conjunto de BTS que son de especial interés para el cliente, cada una etiquetada automáticamente. Las etiquetas explican el significado particular de las ubicaciones para el cliente particular.
Ejemplo de varias realizaciones El conocimiento de los puntos de interés de nuestros clientes permite una
30
amplia variedad de casos de uso y aplicaciones. Conocer los lugares en los que viven, trabajan y que prefieren nuestros clientes para sus actividades de ocio en las diferentes horas de la semana permite al operador desarrollar aplicaciones y servicios específicos que aprovechan tal información segmentada por ubicación.
19
ES 2 427 690 A2
Esa información también puede proporcionarse a instituciones que podrían encontrarla útil para cualquier planificación de servicios públicos tales como diseño de redes de transporte público, control de propagación de enfermedades, u otras iniciativas públicas basándose en el conocimiento de los puntos de interés de los
5
ciudadanos. Y terceros (compañías) también pueden interesarse en el uso de los puntos de interés para la correcta personalización de sus campañas de marketing o actividades comerciales. Imagine una gran compañía textil que vende diferentes tipos de ropa para los
10
diferentes segmentos, donde los segmentos pueden definirse por la edad y nivel socioeconómico (SEL) cruzado. Esa compañía luego se interesa en realidad en conocer qué ubicaciones son de interés para los adolescentes para decidir dónde ubicar tiendas que vendan ropa para ese segmento. De manera similar, esa compañía también está muy interesada en conocer qué lugares se visitan a través de las rutas
15
diarias de personas en la treintena con una probabilidad superior de poder de adquisición. El poder de adquisición puede correlacionarse con el ARPU (ingresos promedio por usuario). Así, la información generada automáticamente por la invención puede venderse a terceras partes o combinarse con otros modelos predictivos en el operador para
20
soportar (como en este caso de uso) el proceso de diseño de redes de compra (basándose en la mezcla usada de las ubicaciones de interés de nuestros clientes y los segmentos más tradicionales como edad, SEL o ARPU). Ventajas de la invención
25
Esta invención toma información de entrada que ya está disponible en la actividad habitual de un operador de telecomunicaciones, así no tienen que desarrollarse procesos especiales con el fin de obtenerla. Esta invención permite una obtención completamente automática de los puntos de interés de los clientes, tanto de manera individual como en un modo global y
30
agregado. Esta invención es un método no intrusivo, así no se perjudica o molesta a los usuarios en su actividad durante la comunicación. Esta
invención
puede
extenderse
fácilmente
para
incorporar
características y también puede extenderse o aplicarse a cualquier región.
20
nuevas
ES 2 427 690 A2
Esta invención permite el desarrollo de servicios nuevos y disruptivos que tienen en cuenta el conocimiento de las ubicaciones en las que entra un usuario y lo que significan para ellos.
21
ES 2 427 690 A2
SIGLAS
5
POI
Point de Interest; punto de interés
BTS
Base Transceiver Station; estación de transceptor base
CDR
Call Detail Record; registro de detalle de llamada
GPS
Global Positioning System; sistema de posicionamiento global
SMS
Short Message Service; servicio de mensajes cortos
22
ES 2 427 690 A2
BIBLIOGRAFÍA [1]
González, Hidalgo, Barabási (2008) Understanding individual mobility patterns. Nature, 453, 779-782
[2]
Song, C., Qu, Z., Blumm, N. y Barabási, A-L. (2010). Limits of Predictability in Human Mobility. Science, 327, 1018–1021.
5 [3]
Calabrese, Di Lorenzo, Ratti (2010) Human Mobility Prediction based on Individual and Collective Geographical Preferences. ITSC
[4]
Firouzi, Liu. Sadrpour (2009) Mobility Pattern Prediction Using Cell-phone Data logs. EECS Final Project Report.
10
[5]
Candia, González, Wang, Schoenharl, Madey, Brabási (2008) Uncovering Individual and Collective Human Dynamics from Mobile Phone Records. Journal of Physics A: Mathematical and Theoretical 41
[6]
Zignani, Gaito (2010) Extracting Human Mobility Patterns From GPS-based Traces. 978-1-4244-9229-9/10/$26.00 ©2010 IEEE
15
[7]
Phithakkitnukoon, Horanont, Di Lorenzo, Shibasaki, Ratti (2010) Activity Aware Map: Identifying Human Daily Activity Pattern Using Mobile Phone Data. LNCS 6219, págs. 14–25
[8]
Boldrini, Conti, Passarella (2009) The Sociable Traveller: Human Travelling Patterns in Social-Based Mobility. MobiWac’09, October 26–27, 2009, Tenerife,
20
islas canarias, España.
23
ES 2 427 690 A2
REIVINDICACIONES 1.
Método para la detección y etiquetado automático de puntos de interés de usuario, que comprende: a) adquirir información de señales intercambiadas entre dispositivos
5
informáticos móviles de usuario y una pluralidad de estaciones de transceptor base, o BTS; b) analizar dicha información adquirida para determinar, durante un periodo de tiempo, las ubicaciones de dicho dispositivo móvil del usuario basándose en las ubicaciones de las BTS con las que se ha
10
producido el intercambio de dichas señales; e c) detectar y etiquetar al menos parte de las ubicaciones determinadas por dicho dispositivo móvil del usuario como puntos de interés al menos basándose en el número de veces que dicho dispositivo móvil del usuario haya estado en dichas ubicaciones determinadas durante dicho
15
periodo de tiempo, en el que dichas etapas b) y c) comprenden aplicar dicho análisis e identificación a través de un modelo estadístico. 2.
Método según la reivindicación 1, que comprende además limitar dicha adquisición de información desde el dispositivo móvil del usuario por un umbral
20
superior y uno inferior. 3.
Método según la reivindicación 1, que comprende además filtrar cada una de dichas BTS para cada uno de dicho dispositivo móvil del usuario cuando la comunicación entre los mismos es inferior a un umbral.
4.
25
Método según la reivindicación 1 a 3, en el que dicha adquisición de información de la etapa a) comprende además para cada par usuario-BTS relevante, un vector que contiene dichas ubicaciones para cada hora de los días de la semana.
5.
Método según la reivindicación 1, en el que dicho modelo estadístico comprende además un algoritmo de agrupamiento por partición alrededor de
30
medoides, o PAM, basándose en una distancia de Pearson. 6.
Método según la reivindicación 5, en el que dicho algoritmo de agrupamiento devuelve veinte representaciones diferentes de agrupamientos.
7.
Método según la reivindicación 6, en el que dichas representaciones de agrupamientos se representan mediante su curva centroide y se etiquetan
24
ES 2 427 690 A2
considerando hábitos sociales y características culturales de la región en estudio. 8.
Método según la reivindicación 7, en el que se usa un primer conjunto de 20 etiquetas para identificar puntos de interés teniendo en cuenta dichos hábitos y
5
dichas características culturales de la región. 9.
Método según la reivindicación 8, en el que a partir de dicho primer conjunto de 20 etiquetas se usa un segundo conjunto de 5 etiquetas para identificar dichos puntos de interés basándose en aplicaciones prácticas.
10.
10
Método según la reivindicación 1, en el que dicha adquisición de información de dicha etapa a) incluye el número de dicho dispositivo móvil del usuario, la fecha y hora, y la BTS asociada a dichas señales intercambiadas.
25
ES 2 427 690 A2
Clientes
Operador de telecomunicaciones
Red de comunicaciones
Eventos geolocalizados
Modelado estadístico
Puntos de interés de los clientes
Figura 1
26
ES 2 427 690 A2
Eventos geolocalizados
1 – Información de ubicación
2 – Filtro de comunicación de clientes
3 – Filtro de uso de BTS
4 – BTS relevantes
Modelos de análisis de movilidad 14 –Puntos de interés
Figura 2
27
ES 2 427 690 A2
4 – BTs relevante
5 – Vectores de uso cliente-BTS 13- Uso del modelo
6 - Normalizaciones
Entrenamiento del modelo 12 – Resultados del 7 - Muestra modelo 8 - Agrupamiento- PAM 9 – Agrupamientos medoides y centroides
Distancia Conj. de medoides
10 – Etiquetado de medoides Dos niveles
Umbral Conj. de etiquetas
11 – Medidas de dispersion entre clases
14- Puntos de interés
Figura 3
28
ES 2 427 690 A2
Puntos de interés Base del cliente
Lugar casa del cliente Lugar trabajo del cliente Zonas de ocio semana cliente
Ocio tiempo almuerzo cliente Zonas ocio noche cliente …
Campañas de marketing basadas en ubicación
Servicios contextuales
Figura 4
29
Planificación urbana
ES 2 427 690 A2
Operador
Modelos predictivos
Modelos de movilidad
POI: Ubicaciones y etiquetas
Fuente explícita
Edad SEL ARPU
Segmentación céntrica ubicación-interés
Planificación de redes de tiendas
Figura 5
30
ES 2 427 690 A2
31
ES 2 427 690 A2
32
ES 2 427 690 A2
33
ES 2 427 690 A2
34
ES 2 427 690 A2
35
ES 2 427 690 A2
36
ES 2 427 690 A2
37
ES 2 427 690 A2
38
ES 2 427 690 A2
39
ES 2 427 690 A2
40
ES 2 427 690 A2
41
ES 2 427 690 A2
42
ES 2 427 690 A2
43