Point of Interest (POI) visit is critical information for many location-based services, such as POI recommendation and advertising push. However, most POI visit information is obtained from user's check-in data on social networks, which inevitably contains false visits and misses parts of real visits. Some work has been done to attempt mining POI visits from users' GPS trajectories, but they could not cover indoor POIs. In this paper, we proposed a Wi-Fi fingerprint-based POI visit identification system, WiVisit, in order to get accurate POI visit info, including indoor POIs. Different from traditional Wi-Fi fingerprintbased localization system, WiVisit can generate Wi-Fi fingerprints automatically with Wi-Fi and POI binding info for different POIs without any human effort. Therefore, WiVisit system could be easily and widely deployed in the real world. Moreover, a multi-model fusion based POI visit identification method was used in WiVisit to handle multiple POI types. Finally, extensive real POI visits were collected and used to assess the performance of WiVisit system. WiVisit achieved a 90% recall rate and 83% accuracy from the visited POIs, which already outperformed the state-of-the-art.
The term "Point of Interest" (POI) refers to a geographical location that someone may find interesting, useful, or visit frequently. The POI visit information of a user is very important for a lot of location-based services (LBS), such as push advertisements, next POI recommendation [1,2,3]. However, most POI visit information is obtained from users' check-in data on locationbased social networks, such as Yelp, Foursquare, and Facebook Places. Due to that POI visit information is pushed by a user manually, there are many missing and fake POI visits. Moreover, if the user pushed the visit information when they left the POI, the best time to push ads will be missed. Therefore, we wanted to build an accurate localization system which can identify real POI visits when users arrive at the POI.
Some researchers also tried to use GPS trajectory information to identify POI visit [4,5,6]. However, many POIs are indoor POIs. For these POIs, the GPS signal will be blocked, and the GPS trajectory information will be missing as well. For that reason, utilizing GPS trajectories for indoor POI visit identification is impracticable. In recent years, Wi-Fi devices have been broadly used, and Wi-Fi fingerprint-based localization techniques have been also widely applied in both outdoor and indoor environment. Based on pre-built Wi-Fi fingerprints for each POI, a localization system [7,8,9,10,11] can be used to identify if the user is at a POI and which POI they are visiting. However, in order to achieve this goal, there are several challenges. First, the amount of POI is colossal, and one POI may change frequently due to renovation or relocation. Thus, POI fingerprints are very difficult to collect and update manually. Second, different types of POI have diverse Wi-Fi environments; therefore, the features of fingerprints for distinct POIs will vary considerably.
In order to solve these challenges, we implemented an auto-generated Wi-Fi fingerprint-based POI visit identification system (WiVisit). Figure 1 shows the framework of WiVisit system. First, we proposed an automatic POI fingerprints collection method. The basic idea is, if the scanned Wi-Fi list in the localization query contains a POI's Wi-Fi and the RSSI is strong enough, the user is most likely to be visiting that POI. That is, they are very close to the Wi-Fi device based on the path loss model [12] at the POI. In order to obtain POI's Wi-Fi information, we designed a POI-Wi-Fi binding module based on the similarity between names of the POI and Wi-Fi. Applying the POI-Wi-Fi binding information, many in-POI localization queries will be collected automatically, of which the scanned Wi-Fi list contains a POI's Wi-Fi and the RSSI is strong enough. Then, the POI's fingerprints could be built from these queries. Secondly, based on the POIs' type information, we divided all POIs into different groups, and trained different POI visit identification models for each of them. At last, we proposed a multi-model fusion mechanism to combine these models in one. The following are our main contributions in this paper:
β’ We proposed a POI-Wi-Fi binding module, which could discover Wi-Fi devices that are placed in the POIs. Based on the POI-Wi-Fi binding information, the WiVisit system could automatically collect and update POI fingerprints without any human effort.
β’ We designed a multi-model fusion based POI visit identification method which can be used for different types of POI. β’ We also conducted extensive experiments to test the performance and effectiveness of WiVisit system in the real world.
The following sections are organized as follows: Section 2 introduces the related work and Section 3 gives a formal definition of POI visit identification. Section 4 is a detail description about how to generate POI fingerprints automatically. Section 5 introduces the POI visit identification model. Section 6 is the experiments and evaluations about WiVisit, and Section 7 is the conclusion.
Many POIs are placed in an indoor environment, such as stores, shopping malls, restaurants, and bars. Determining whether a user is visiting a POI, rather than just passing through it, can be treated as an indoor localization problem.
Over the years, many indoor localization technologies have been developed including cameras [13][14], sound [15,16], radio frequency [7,17,18,19], etc. Camera-based technologies [13,14] can achieve a high accuracy, but the privacy concern of them is a big issue for real-life deployment. Sound-based solutions [15,16] are vulnerable to environmental noises and the coverage is quite small. In addition, dedicated infrastructure is needed for UWBbased [19,20,21] and Bluetooth-based [17] solutions. Since Wi-Fi access points are deployed ubiquitously, we focused on Wi-Fi based indoor localization methods in our work.
Wi-Fi-based indoor localization has drawn a lot of attention from researchers in the last decade. RADAR [7] is a pioneering system employing Wi-Fi RSSI information as the fingerprint for localization. After which, many RSSI-based indoor fingerprint localization methods have been developed to reduce the offline training load or to improve the accuracy [8,9,10,11,22]. However, these methods still required some human efforts on fingerprint collection and updating, which is impossible for a large number of POIs. In the past few years, some fine-grained CSIbased indoor localization methods have been proposed [23,24,25,26,27,28]. However, only a few commercial Wi-Fi chips could provide the CSI information to users. Hence, CSI-based indoor localization methods cannot be adopted widely in the real world.
Compared with these methods, WiVisit can automatically generate and update POIs' Wi-Fi fingerprints from localization queries without any human effort. Meanwhile, WiVisit system adopts RSSI information as the fingerprints, which are available on almost all existing Wi-Fi chips. Therefore, the WiVisit system can be deployed in the real world rapidly and widely.
GPS system is widely used for outdoor localization. Consequently, in recent years, some researchers tried to mine POI visit events from users' GPS trajectory data [4,5,6]. They first extracted stay-points from a GPS trajectory as first, then they detected semantic locations from these stay-points and assigned a POI visit information for each location. However, due to privacy concerns, users would not open GPS localization service all the time. For this reason, getting a complete GPS trajectory of a user for POI visit mining is very difficult in the real world. Additionally, in an indoor POI, users may not be able to receive a GPS signal, so they cannot get the GPS location information which is required for POI visit mining.
In comparison with these methods, WiVisit system does not require users' trajectories. Whenever the user needs position information, the WiVisit system can identify the POI visit based on the user's localization query. Moreover, as Wi-Fi devices are ubiquitous in the world, almost all POIs have deployed their own Wi-Fi devices that WiVisit system can use for POI visit identification.
Localization query: A localization query is a user scanned Wi-Fi list that contains Wi-Fi MAC address (π) and RSSI value (π):
where πΎ represents the number of scanned Wi-Fi. POI fingerprint: A POI fingerprint (πΉ π π π ) records Wi-Fi information in a period of localization queries of the POI (π π ):
where π is the number of Wi-Fis, π ππ is the median RSSI of the Wi-Fi π ππ in the POI (π π ) localization queries, used to build fingerprints and π ππ is the rate of occurrence:
The POI visit identification's task is to determine if a localization query is from a POI and which POI it is from, based on the scanned Wi-Fi list in the query and POIs' Wi-Fi fingerprints:
π is the probability threshold used to determine whether the query is in a POI.
Most of Wi-Fi fingerprint based indoor localization systems [7,8,9,10,11,22] collect fingerprints information by human efforts. However, it is not feasible to create a mass pool of POI Wi-Fi fingerprints manually. Therefore, we proposed an effective Wi-Fi binding method, which is the key point to build Wi-Fi fingerprints of POIs automatically. Wi-Fi is ubiquitous and most of POIs have their own Wi-Fis. We noticed that most POIs have an SSID (Service Set Identifier, the WiFi name that users can see) similar to their POI name. For instance, in China, McDonald's-related Wi-Fi SSIDs are mcd-chinanet or mcdonald's. Because of this, we proposed a POI-Wi-Fi binding method, shown in Figure 2. First, for each POI name, we used a natural language processing (NLP) interpreter [29,30] to get its' Chinese name (CN ), Chinese pinyin (PY ), Chinese pinyin abbreviation (PYABB), English name (EN ) and English abbreviation(ENABB), shown in equation 5. Then, a text similarity between each pair of POI and Wi-Fi was computed as following:
where π(π πππ , π πππ ) is defined as the text hamming distance. Similarity score is the maximum value among different Wi-Fi POI names.
In addition to Wi-Fi SSID and POI name's similarity, we also integrated the coordinate distance to the Wi-Fi POI matching score. It is given as:
where πΎ is a normalize factor between similarity and distance, π·(π, π) is the distance between Wi-Fi and POI, and π· π‘β is the distance threshold value to select candidate POI Wi-Fi pair sets for binding process 1 . Finally, we assigned each Wi-Fi to the POI which has the maximum score greater than πΊ π‘β among all candidate POIs. It is formulated as follows:
where πΊ π‘β is the score threshold for choosing the real matched POI-Wi-Fi-pair.
Applying the POI-Wi-Fi binding information, POI fingerprints can be collected automatically.
Based on the path loss model [12], the further away the user is from the Wi-Fi device, the lower the power of received Wi-Fi signal is. Thus, if a user visits a POI, the scanned POI Wi-Fi's RSSI will be higher than the user outside of the POI. For a localization query, if a scanned Wi-Fi in the query is a POI-Wi-Fi and the RSSI value is high enough2 , the localization query is likely to have taken place in the POI, and was used to build the POI fingerprint information. This way, based on a period of localization queries, the fingerprint information of POIs can be generated.
For WiVisit system, the POI fingerprint records all Wi-Fi that were scanned in the history localization queries at that POI. For each Wi-Fi, it contains two statistics information, median RSSI value and the rate of occurrence, which are defined in Section 3.
To train the POI visit identification model, first, we need extract a set of in-POI and out-POI queries as train samples. Similar to fingerprint generation, for WiVisit system, the in-POI queries are those that contain a POI WiFi and the RSSI value is high enough and without additional GPS info. In addition, for the WiVisit system, to make sure that the out-POI queries take place not only truly outside the POIs, but also not far from them, the out-POI queries are extracted based on three criteria: (1) they contain GPS info and their GPS location accuracy [33], [34] is no larger than 30 meters; (2) their distance from POI positions is less than 100 meters; (3) they contain one binding Wi-Fi in their scanned Wi-Fi lists at least. Due to that the Wi-Fi signal can penetrate walls, a Wi-Fi can be scanned in multiple neighboring POIs, meaning a WiFi can appear in different POI fingerprints. Consequently, each query can generate multiple feature vectors for different POIs, whose fingerprint contains at least one Wi-Fi that is in the scanned Wi-Fi list of the query, which makes a query sample potentially correspond to multiple training samples for our identification model. For this reason, we label each sample as follows:
1. If query recalls a different POI from its raw-extracted POI, the corresponding feature vector is treated as a negative sample to the recalled POIs. 2. If a query recalls the same POI as its raw-extracted POI, the original label is used.
Recently, almost all POIs deploy their own Wi-Fi routers to provide Wi-Fi services for their employees and visitors. Therefore, when a user visits a POI, the POI's Wi-Fi devices will appear on the scanned Wi-Fi list of the user. However, the range of that a Wi-Fi can be scanned is limited. If a user does not visit a POI, the user is likely to fail to scan the POI's Wi-Fi. There is a strong correlation between scanned Wi-Fi and POI visit, which is crucial for POI visit identification. Thus, given a Wi-Fi query and a POI π, π (π|ππ’πππ¦) is the probability of the query occurring in POI. We extracted several features from four dimensions to reflect π (π|ππ’πππ¦).
1. π (π|π π ) is defined as the probability of Wi-Fi π scanned when users visit a POI π π . First, we assume that each Wi-Fi scanned in a query is independent from one another. Based on the bayes formula, the posterior probability π (π π |ππ’πππ¦) is proportional to the likelihood function πΏ(ππ’πππ¦|π π ).
where πΎ is the number of scanned Wi-Fi. π (π π |π π ) can be approximate as the rate of occurrence π ππ . Thus, the first posterior probability feature is:
However, not all of the Wi-Fi are independence with each other. Thus, we also chose some statistics features about π (π π |π π ), which do not require independence between the Wi-Fi:
2. Due to that Wi-Fi signals can penetrate walls, a POI's Wi-Fi can sometimes still be scanned even when the user is outside. However, in those cases, the user is usually further away from the POI's Wi-Fi device than in the POI, which makes the signal strength of the POI's Wi-Fi weaker. Moreover, due to the obstruction of walls, the received signal strength will also be weaker when the user is outside. For these reasons, the RSSI of POI's Wi-Fi is also very important for POI visit identification. Therefore, we calculated RSSI weighted posterior probability based on the following likelihood function:
where π½ π = [(π π + π πππ₯ )/π ππππ ] πΌ . Similar to Equation 9-11, we can get RSSI weighted posterior probability features:
With different πΌ, we can get different likelihood functions, which will generate different posterior probability features based on Equation 13. Then, we can get a set of RSSI weighted posterior probability features. 3. In recent years, Wi-Fi is used not only to connect to the Internet, but also to communicate between smart home devices. In an indoor environment, for example, in addition to routers, there are many smart devices with Wi-Fi chips that can be scanned, such as smart TV, intelligent speakers, smart air-conditioners. Therefore, when a user is in a POI, the scanned RSSI of smart devices could also be very strong. Then, the proportion of strong Wi-Fi in the scanned Wi-Fi list will be very high. However, if the user is outside the POI, due to the obstruction of walls and their increasing distance from the smart devices and routers, the proportion of strong Wi-Fi in the scanned Wi-Fi list will decrease. Based on this intuition, we also extracted posterior probability features between POI and Wi-Fi that is filtered by the absolute RSSI value. For these features, the likelihood function can be represented as follow:
where π π is the absolute RSSI threshold. For different absolute RSSI thresholds, based on Equation 14, the RSSI filtered posterior probability feature can be represented as:
With different π π , we can get a set of absolute RSSI filtered features. 4. For commercial Wi-Fi devices, the RSSI measurements of Wi-Fi signal will be influenced by antennas, quality of Wi-Fi chips, the position of holding the phone, etc. Thus, even in the same location, different phones scanning the same Wi-Fi will have different RSSI values. Sometimes, features generated by the absolute RSSI value will introduce such bias. Therefore, we extracted some posterior probability features between the POI and Wi-Fi that is filtered by relative RSSI information to remove this bias. First, we extracted marginal features for the query::
where π π‘ππ(π₯) is the set of the highest π₯ Wi-Fi based on RSSI value in the scanned Wi-Fi list of the query. Meanwhile, we extracted the edge distribution probability features for the POI:
where πΏ π‘ππ(π ) means the highest π Wi-Fi based on median RSSI value in the fingerprint of the POI. And finally, we extracted the joint probability features:
Based on Equation 16-18, with different π₯ and π , we can also get a set of relative RSSI filtered features.
As described in section 5.2, based on different values of hyper-parameters, we used a 784dimensions feature vector to represent each train sample. Meanwhile, the lightGBM [32] classification model was used to build the POI visit identification model. For the lightGBM model, we had chosen the gradient Boosting Decision tree (GBDT) as the boosting tree and binary log-loss as the loss function. The number of leaves for each tree was set as 127. Meanwhile, to avoid over-fitting, the feature fraction was set as 0.6 and the bagging fraction was set as 0.7.
All other parameters of lightGBM model were used as their default values.
To deal with hybrid POI types, we trained 61 sub-models by dividing query samples into 61 parts based on their POI info, and then combined their predicted results to get the final result by voting. If the number of sub-models, which gives visit prediction, is larger than 30 (i.e. half of 61), the final prediction is visit and the highest score POI is the visited POI. Figure 3 shows the full POI visit identification model training workflow.
Moreover, in order to improve the robustness and generalization of WiVisit, we brought in several optimization methods:
1. POI queries balance: Different POIs will have different popularity. A popular POI will have more localization queries than an unpopular POI. The unbalanced query numbers of different POIs will affect the generalization of the model. Therefore, during the sample extraction phase, the maximum number of query samples in each POI is limited. 2. Training samples balance: For most of POIs, the number of negative samples is much larger than positive samples. In order to get more effective parameter estimation, we adopted random under-sampling on negative samples for each POI. Finally, for each POI, the number of negative samples is no more than 1.2 times of positive samples.
Finally, we can use the trained model to predict POI visit information. In detail, for a user localization query with scanned Wi-Fi list, the related POIs' fingerprints are extracted from the fingerprint database, whose fingerprint contains at least one Wi-Fi in the scanned Wi-Fi list of the query. For each POI, the feature vector is computed, and visit prediction of sub-models is added to obtained the final visiting score. If there is at least one POI predicted as visited finally, we selected the POI with the highest visiting score as the visiting result.
In order to evaluate WiVisit system, we extracted the top 6 hot types ('Entertainment', 'Life services', 'Restaurant', 'Shopping', 'Fitness', 'Hotel') of POIs in Beijing from Tencent Map [31], which contained 210 sub-types and had more than 90,000 POIs in total. We then applied our POI Wi-Fi binding module, introduced in Section 4, to these POIs, to get POI Wi-Fi information. We extracted these Wi-Fis which occurred at least once in last two weeks of all Tencent localization queries as the candidate Wi-Fi set to binding POI. The size of candidate Wi-Fi set is about several billions. Due to the large number of Wi-Fi existing, for a given POI, all similar Wi-Fi to the given POI cannot be computed within a reasonable time. Therefore, given a POI, we only extracted the set of Wi-Fi whose distances from the POI is less than 200 meters (π· π‘β ) which is large enough compared with common indoor Wi-Fi coverage area. The threshold π· π‘β is used for filtering a small candidate binding Wi-Fi set to each POI. The normalization factor πΎ was set as 0.005, which means that the score of one POI-Wi-Fi pair will be equal to 0 if their similarity is 1 but their distance is larger than π· π‘β = 200. To assess the accuracy of POI-Wi-Fi binding module, we manually labeled 20,000 POI-Wi-Fi pairs as the benchmark data set. The accuracy of different binding score thresholds was calculated and shown in Figure 4. Finally, POI-Wi-Fi pairs with binding scores larger than 0.8 and accuracy larger than 98% were used to generate POI fingerprints.
After POI-Wi-Fi binding, we obtained 42278 POIs which had binding Wi-Fi. For these POIs, we extracted raw user queries from 20210301 to 20210304 to build the fingerprint database. To train the POI identification model, we collected localization queries from 20210305 to 20210306 as the training set of WiVisit. To evaluate the identification performance, we collected localization queries from another two days (20210307, 20210308) as the test set to compare different methods. Moreover, we also manually collected real POI visited queries to evaluate the performance of WiVisit in the real world. For each POI, the visited queries are collected from two collectors with two different types of mobile phones and staying five minutes at least. The POI identification model consists of 61 sub-models. These sub-models were trained parallelly in cluster mode, whose training time is no more than half an hour. Online prediction is triggered on a server when one query is received. Based on our test, the average time of predicting is less than 30ms per query. The detailed information of these sample sets is shown in Table 1.
The rule for labeled visiting samples, that is, if at least one scanned Wi-Fi in the query is a binding Wi-Fi and the RSSI value is higher than -50db without any GPS info, then the query is visit sample and the corresponding POI is the visited POI. For evaluation, we only compare BASE0 with other methods in manual set. 2. BASE1: One intuitive assumption is that one localization query having more overlapped Wi-Fi with a POI fingerprint is more likely to occur in this POI. Based on this assumption, we computed ratios of Wi-Fi overlapping between a localization query and POIs' fingerprints.
Where π π is the ratio of Wi-Fi overlapping between the query and POI π. If the maximum overlapping ratio is larger than the given threshold, this query is labeled as a visit query and the POI corresponding to the maximum ratio is the visited POI. In order to choose the best threshold, we plotted the overlapping ratios between query and its associated POI for each training sample shown in Figure 5 3 . As shown in the figure, the best threshold is 0.84. 3. BASE2: In addition to the ratio of Wi-Fi overlapping, we included the RSSI strength and the rate of occurrence of each Wi-Fi to define a visiting score as follows:
where π π£ (π π |ππ’πππ¦) is defined as the score of a user in POI π π with the scanned query, and π€ π is the weight of Wi-Fi π π in query with π π . Based on the path loss model [12], the weight function is π€ π π = 10 (π π βπ 0 )/π π‘β , where π π is the signal strength of Wi-Fi π π , π 0 is the maximum of RSSIs of the given query, and π π‘β is a measure of divergence of all RSSIs. In our evaluation, π π‘β was fixed as 50. π ππ is the co-occur probability of π π and π π , which was defined in Section 3. For this method, the best threshold is 0.12, with the highest F score in the Train Set. 4. WiVisit-1: The same classification model as WiVisit with only one lightGBM model. 5. WiVisit: Our fusion POI-visiting model for different POI types.
For POI visit identification, the objective is to not only determine if a localization query occurs in a POI, but also to identify which POI it is from. Thus, we used four dimensions metrics (precision, recall, F score, accuracy) to evaluate the performance. The following are definitions about these metrics:
First, we compared these methods on the Test Set, which was collected by the same rules as the Training Set, but in different time period. Table 2 shows the evaluation result. BASE1 can accurately determine whether the user is visiting (92.3% Precision), but its predicted POI is not the real visited (39.3% Accuracy). That is, POIs with the maximum of overlapping Wi-Fis were not always the visited POIs. BASE2 had a higher recall rate and accuracy, which means the RSSI and rate of co-occurrence is more useful to find the right visited POI. However, the lower precision means it's not enough to decide whether a localization query is occurring in a POI. Compared with these two baseline methods, WiVisit-1 achieved much better performance in both POI visit judgment and final visited POI identification. Moreover, compared with WiVisit-1, since the fusion model is more robust in various POIs, WiVisit could obtained about 10% improvements in both precision and accuracy.
We further compared these methods in different POI types, since the different types of POI had various Wi-Fi environments. As shown in Figure 6, for the 6 types of POIs, we used the F scores to show the performance on POI visit judgment and accuracies to show the performance on final visited POI identification. For POI visit judgment, as shown in the figure, BASE1 and WiVisit-1 yielded a similar performance while WiVisit-1 yielded a more robust result in different types of POIs. BASE2 gave in the worst F score with a much better accuracy for visited POI identification. Obviously, BASE1 and BASE2 were both affected by POI types, especially for "Hotel". WiVisit-1 and WiVisit achieved much robust performance in terms of F score and accuracy. Moreover, WiVisit obtained much better performance in all types of POIs compared with other methods.
We further compared the above methods on the Manual Set, shown in Table III. Since Manual Set only contained visit samples, we only used recall and accuracy to assess the performance. BASE0 achieved 100% accuracy, meaning the rule for visit query extraction was very effective.
Meanwhile, strict rules have caused a lower recall rate 32.4% for BASE0. BASE1 obtained a remarkable improvement in recall rate. However, it did not achieve a reasonable accuracy. BASE2 had a much better balance performance in both recall and accuracy. The accuracy is much lower than the recall which means that both BASE1 and BASE2 still cannot distinguish the true visited POI among POI dense area. WiVisit1 and WiVisit still had the best performance than other methods. While WiVisit had a similar recall rate with BASE2, it achieved a significant accuracy improvement from 73.3% to 83.6%.
In this paper, we proposed an auto-generated Wi-Fi fingerprint-based POI visiting identification system, WiVisit, which collects accurate user' POI visit information, including indoor POIs. It is crucial for various LBS. Meanwhile, compared with traditional Wi-Fi fingerprint-based localization methods, WiVisit does not require any human effort in fingerprint collection and updating. Therefore, WiVisit can be deployed in the real world widely and easily. Moreover, WiVisit system adopts a multi-model fusion based method for POI visit identification, which can deal with different types of POI in the real world. Based on our extensive experiments, the recall rate of WiVisit is around 90% and the accuracy is 83%, which already outperforms state-of-the-art. However, there are still many POIs cannot be bound with Wi-Fis, due to their irregular Wi-Fi SSID or no Wi-Fi device is deployed in them. In the future, crowd-sourcing methods can be used to collect more POIs' Wi-Fi information, which will make WiVisit system versatile for more POIs in the real world.