How we personalized POIs

At 2GIS we want to facilitate the user’s search routine and therefore strive to anticipate user requests. Under the cut, we will tell you about how we came up with an algorithm for personalizing interesting places and what came of it.

POI (point of interest) – a small round icon on the map. Indicates a place or company that may be of interest to the user.

Here they are – POI 2GIS. Each category has its own icon

POIs – city objects popular with the majority in different headings. And I also want to take into account the interests of each user separately. Therefore, we decided to add personalized POIs to the map, which will be responsible for this.

Well-chosen POIs also shorten the chain of search steps on the map. Usually the user searches for something like this: opened the application → entered a search query → viewed the results → opened the object card.

With personalized POIs, the user can navigate the map and find information without a search query: open the application → see the desired POI on the map → open the object card.

Map without personalized POIs and with them – interesting restaurants, coffee shops and clinics for the user

Data

It is logical to take as potential objects for POI those in which the user has already shown interest. And among them, look for those to which he will return with the greatest probability. At the same time, it is desirable that the objects interest the user as long as possible – so that he gets used to looking for them on the map.

But how can this data be classified? You can mark up a selection of objects, enrich it with a variety of features and apply boosting or neural networks. But you can go the other way – and come up with a rule of thumb.

Rule of thumb

There are pros and cons to a rule of thumb. Yes, this will give a weaker classification quality. But the main advantage is that we can quickly and easily check the demand for POIs. Data preparation, training of such a model and its implementation will take much less time than, for example, boosting. And if the feature turns out to be successful for both the user and the company, we can always switch to more complex and costly models.

For empirical models, a good domain context is important. Investigating user behavior in the product, we found out that the probability of repeated user access to the product (retention rate) has an exponential distribution.

This property is present not only in the retention rate of the product, but also in many other phenomena associated with repeated access – for example, repeated access to an object, as in our case. This knowledge helped us develop algorithms for determining the user’s “home” city, short-term and long-term user interests.

First algorithm

The first step was to form a sample of the form

$$

$$ – n-dimensional vector of features of the i-th object, and as the object of classification we consider all objects that the user was interested in for a certain time before the calculation date. In our case, it is two months.

$$ – the class of the i-th object – the response, which takes on a value equal to 1 if the user visited the company in the control period of time, and 0 if he did not visit.

Since we are interested in objects that will be of interest to the user for a long time, we chose a month as a control period two weeks after the calculation date. This lag of two weeks is needed in order not to capture among the successful objects of instant / short-term interest – those that the user is looking for right on the date of calculation or near it, but not the fact that he will return to them. Objects with y = 1 are considered successful – that is, those to which the user returned during the control period.

The rule $$, which associates the set of attributes of an object X with its class Y, looks like this:

$$ equals 1 if on day i the user was interested in the object, otherwise 0. Day number equals 1 on the first day of the training sample and k on the last.

$$ – a parameter that is responsible for the rate of change in the significance of the day of interaction with the object as it moves away from the calculation date.

$$ – threshold value.

The idea is that the farther away the day when the user was interested in an object, the less weight this day will have when evaluating this object. Function parameters $$ and $$ are matched by maximizing the target variable:

$$

where F is an F-measure with an appropriate ratio of the desired accuracy and completeness of the model. In this problem, the main emphasis is on the accuracy of the algorithm, so we took the parameter $$…

$$

Results 1.0

The algorithm was tested for more than 450 million objects. Among them, the share of objects with a response equal to 1 is approximately 5%. The completeness of the algorithm is 0.153, the accuracy is 0.401, and the F-measure $$ – 0.303.

The quality of such an algorithm may seem unacceptably low. The fact is that the number of objects for classification includes objects that we cannot attribute to long-term interests based on these metrics – users were too little interested in them to draw any conclusions.

Only 3% of objects were of interest to the user for more than two days during the training period. This is not surprising: it includes objects from spheres with low retention. There are many of them, they can be very large – for example, pharmacies, bars, or just objects that are not of interest to the user.

Among objects with a response equal to 1, this percentage is higher – 22%. This is also small, but it is explained by the large period between site visits.

If we exclude such objects, then with the same model parameters, the completeness increases from 0.153 to 0.684 with the same accuracy in 0.401, and the F-measure, with emphasis on precision, becomes 0.437 – classical, of course, higher.

However, with this kind of model, there are still two problems. At first, users have different activity levels: someone uses the application once a day, and someone – once a month. Therefore, the use of a common threshold value and some parameters of the weighting function can underestimate the quality of the classification.

Secondly, sites may have different frequency of visit depending on their field of activity. For example, a user regularly goes to a hypermarket for groceries once a week, goes to a hairdresser’s once a month, and in case of a cold, he can visit the clinic as often as the doctor tells him to. So we can miss objects with long visit intervals.

Second algorithm

To address these issues, we added a feature to the function showing the maximum period of user interest, and slightly differently took into account the intensity of site visits and its relevance. We divided users into three groups according to the frequency of visiting the product. For each of them, we selected their own parameters of this model:

$$– number of the last day of user interaction with the object (equal to 1 on the first day of the training sample and k on the last).

$$– the number of days of user interaction with the object in the period under review.

$$– the number of days between the first and the last day of user interaction with the object in the period under consideration.

$$ – the parameters of the function, which are selected by maximizing the target variable (in our case, it is the F-measure) in a similar way for the first model.

Results 2.0

The parameters were evaluated and the following results were obtained for user clusters.