Clustering is an unsupervised learning technique used to group a set of elements into nonoverlapping clusters based on some predefined dissimilarity function. In our context, we rely on clustering algorithms to extract points of interest in human mobility as an inference attack for quantifying the impact of the privacy breach. Thus, we focus on the input parameters selection for the clustering algorithm, which is not a trivial task due to the direct impact of these parameters in the result of the attack. Namely, if we use too relax parameters we will have too many point of interest but if we use a too restrictive set of parameters, we will find too few groups. Accordingly, to solve this problem, we propose a method to select the best parameters to extract the optimal number of POIs based on quality metrics.
The first step in inference attacks over mobility traces is the extraction of the point of interest (POI) from a trail of mobility traces. Indeed, this phase impacts directly the global accuracy of an inference attack that relies on POI extraction. For instance, if an adversary wants to discover Alice’s home and place of work the result of the extraction must be as accurate as possible, otherwise they can confuse or just not find important places. In addition, for a more sophisticated attack such as next place prediction, a mistake when extracting POIs can decrease significantly the global precision of the inference. Most of the extraction techniques use heuristics and clustering algorithms to extract POIs from location data. On one hand, heuristics rely on the dwell time, which is the lost of signal when user gets into a building. Another used heuristic is the residence time, which represents the time that a user spends at a particular place. On the other hand, clustering algorithms group nearby mobility traces into clusters.
In particular, in the context of POI extraction, it is important to find a suitable set of parameters, for a specific cluster algorithm, in order to obtain a good accuracy as result of the clustering. The main contribution of this paper is a methodology to find a “optimal” configuration of input parameters for a clustering algorithm based on quality indices. This optimal set of parameters allows us to have the appropriate number of POIs in order to perform another inference attack. This paper is organized as follows. First, we present some related works on parameters estimation techniques in Section 2. Afterwards, we describe the clustering algorithms used to perform the extraction of points of interests (POIs) as well as the metrics to measure the quality of formed clusters in sections 3 and 4, respectively. Then, we introduce the method to optimize the choice of the parameters in Section 5. Finally, Section 6 summarizes the results and presents the future directions of this paper. 2
Most of the previous works estimate the parameters
of the clustering algorithms for the point of interest
extraction by using empirical approaches or highly
computationally expensive methods. For instance,
we use for illustration purpose two classical
clustering approaches, K-means
To perform the POI extraction, we rely on the following clustering algorithms: 3.1
DJ-Cluster
DT-Cluster
Introduced in
The objective of the begin and end location finder
inference attack
Since we have introduced the different clustering algorithms to extract points of interest, we present in the next section the indices to measure the quality of the clusters. 4
One aspect of the extraction of POIs inference attacks is the quality of the obtained clusters, which impacts on the precision and recall of the attack. In the following subsection we describe some metrics to quantify how accurate or “how good“ is the outcome of the clustering task. Intuitively, a good clustering is one that identifies a group of clusters that are well separated one from each other, compact and representative. Table 1 summarizes the notation used in this section.
C ci nc mi d(x, y) |ci| m0 m00 |C|
An ensemble of clusters.
The ith cluster of C.
The number of clusters in C.
The medoid point of the ith cluster.
The Euclidean distance between x and y.
The number of points in a cluster ci.
The closest point to the medoid mi.
The second closest point to the medoid mi.
The total number of points in a set of C.
The intra-inter cluster ratio
DIC(ci) = d(xj , mi) (1) 1 |ci| 1 |ci|
X xj2 ci,xj6=mi Then, the average intra-cluster distance (DIC) is computed using Equation 2.
AV G DIC(C) = Afterwards, the mean distance among all medoids (DOC) in the cluster C is computed, using Equation 3.
1 |nC | ⇥ (|nC | 1) |C| X |C|
X
ci2 C cj2 C,i6=j
Inspired by the Ben-David and Ackerman
K
AM (ci) = d(mi, m0i0) d(mi, m0i) (5) Since the average of the k-additive point margins for all groups ci in a cluster C is computed, we take the ratio between the average k-additive Point Margin and the minimal inter-cluster distance (Equation 1) as shown in Equation 6.
1 Pnc AM (C) = minci2 C nc ci2 DCIKC(ci) AM (ci) (6) The additive margin method has a linear complexity in the number of clusters. This metric gives a high value for a well centered clusters. 4.3
The information loss ratio is a metric inspired by the
work of Sole and coauthors
nc |c| SSE(C) = X X d(xj , mi)
ci2 C xj2 ci Then, we estimate the accumulated distance of all points of a trail of mobility traces in the cluster C to a global centroid (GC) using the following equation Equation 8.
|C| SST (C) = X d(xi, GC)
xi2 C Finally, the ratio between aforementioned distances is computed using Equation 9, which results in the (7) (8) diam(ci) = maxx,y2 ci,x6=yd(x, y) (10)
DBI(C) = information loss ratio.
IL(C) =
SSE(C) SST (C) The computation of this ratio has a linear complexity. The lowest is the value of this ratio, the more representative the clusters are. 4.4
This quality index
Then, if the clustering C is compact (i.e, the diameters tend to be small) and well separated (distance between cluster medoids are large), the result of the index, given by the Equation 11, is expected to be large.
DIL(C) = minci2 C [mincj2 C,j=i+1 [ The greater is this index, the better the performance of the clustering algorithm is assumed to be. The main drawbacks of this index is the computational complexity and the sensitivity to noise in data. 4.5
The objective of the Davis-Bouldin index (DBI)
v
n
S(ci) = utu n1c xXj2ci d(xj , mi)2 Then, we compute the distance between two different clusters ci and cj , given by Equation 13. q M (ci, cj ) =
Afterwards, a similarity measure between two clusters ci and cj , called R-similarity, is estimated, based on Equation 14. (14) (16) R(ci, cj ) =
S(ci) + S(cj )
M (ci, cj ) After that, the most similar cluster cj to ci is the one maximizing the result of the function Rall(ci), which is given by Equation 15 for i 6= j.
Rall(ci) = maxcj2 C,i6=j R(ci, cj ) (15) Finally, the DBI is equal to the average of the similarity between clusters in the clustering set C (Equation 16). Ideally, the clusters ci 2 C should have the minimum possible similarity to each other. Accordingly, the lower is the DB index, the better is the clustering formed. These indices would be used to maximize the number of significant places a cluster algorithm could find. More precisely, in the next section we evaluate the cluster algorithm aforementioned as well as the method to extract the meaningful places using the quality indices. 5
In order to establish how to select the best set
of parameters for a given clustering algorithm, we
have computed the precision, recall and F-measure
of all users of LifeMap dataset
To compute the recall (c.f. Equation 17), we take as input a clustering set C, the ground truth represented by the vector Ppoi (which was defined manually by each user) as well as a radius to count all the clusters c 2 C that are within the radius of ppoi 2 Ppoi, which represents the ”good clusters”. Then, the ratio of the number of good clusters compared to the total number of found clusters is computed. This measure illustrates the ratio of extracted cluster that are POIs divided by the total number of extracted clusters.
Total nb of users Collection period (nb of days)
Average nb of traces/user
Total nb of traces Min #Traces for a user Max #Traces for a user
To compute the recall (c.f. Equation 18), we take as input a clustering set C, a vector of POIs Ppoi as well as a radius to count the discovered POIs ppoi 2 Ppoi within a radius of the clusters c 2 C, which represents the ”good POIs”. Then, the ratio between the number of good POIs and the total number of POIs is evaluated. This metric represents the percent of the extracted unique POIs. (18) (19) Recall =
good P OIs total number of P OIs
Finally, the F-measure is defined as the weighted average of the precision and recall as we can see in Equation 19.
F measure = 2 ⇥ precision ⇥ recall precision + recall We present the dataset used for our experiments in the next subsection.
In order to evaluate our approach, we use the
LifeMap dataset
Since we have described our dataset, we present the results of our experiments in the next subsection.
This section is composed of two parts, in the first part we compare the performance of the previously described clustering algorithms, with two baseline clustering algorithms namely k-means and DBSCAN. In the second part, a method to select the most suitable parameters for a clustering algorithm is presented.
Input parameters Tolerance rate (%) Tolerance rate (%) Minpts (points) Eps (Km.) Merge distance (Km.) Time shift (hour) K (num. clusters)
Possible values {0.75, 0.8, 0.85, 0.9} {0.75, 0.8, 0.85, 0.9} {3, 4, 5, 6, 7, 8, 9, 10, 20, 50} {0.01, 0.02, 0.05, 0.1, 0.2} {0.02, 0.04, 0.1, 0.2, 0.4} {1, 2, 3, 4, 5, 6} {5, 6, 7,8, 9}
In order to compare the aforementioned clustering algorithms, we have take into account the precision, recall, F-measure obtained, average execution time, number of input parameters and time complexity. To evaluate these algorithms, we used the LifeMap dataset with POIs annotation and a set of different parameters configurations for each algorithm, which are summarized in Table 3. After running these configurations, we obtained the results shown in Table 4 for the different input values.
It is possible to observe that the precision of DJCluster out performs better than the other clustering algorithms. In terms of recall DBSCAN and TD-Cluster perform the best but DJ-Cluster is just behind them. Moreover, DJ-Cluster has the best F-measure. Regarding the execution time, DTClustering the fastest one while DJ-Cluster is the slowest algorithm due to the preprocessing phase. Despite the high computational time of DJ-Cluster, this algorithm performs well in terms of F-measure.
In the following, we describe our method to
choose “optimal” parameters for obtaining a good
F-measure. We have used the aforementioned
algorithms with a different set of input parameters
configurations for users with POIs annotations in the
LifeMap dataset
Regarding the relation between the quality indices and the F-measure, we studied the relationship between these factors, in order to identify the indices that are highly correlated with the F-measure, as can be observed in Figure 1. We observe that the two best performing indices, except for k-means, are IL and DBI. The former shows a negative correlation with respect to the F-measure. While the latter, has a positive dependency to the F-measure. Our main objective is to be able to identify the relationship between quality and F-measure among the previous evaluated clustering algorithms. Accordingly, we discard the inter-intra cluster ratio (RII) and the adaptive margin (AM), which only perform well when using k-means and the DJ clustering algorithms. Finally, we observe that the Dunn index has a poor performance. Based on these observations, we were able to propose an algorithm to automatically choose the best configuration of input parameters. 5.4
Let us define a vector of parameters pi 2 P and P a set of vectors, such that P = {p1, p2, p3, . . . , pn}, a trail of mobility traces M of a user. From previous sections we have the clustering function C(pi) and the quality metrics Information Loss IL(C) and Davis-Bouldin index DBI(C). Thus, for each vector of parameters we have a tuple composed of the trail of mobility traces, the result of the clustering algorithm and the quality metrics (pi, M, Cpi , ILCpi , DBICpi ). When we compute the clustering algorithm and the quality metrics for each vector of parameter for a given user u. We define also a 0u matrix, which the matrix u sorted by IL ascending. Finally, the result matrix u is of the form: u = p1 p2 p3 . . . pn
M M M M
Cp1 Cp2 Cp3 Cpn
ILCp1 ILCp2 ILCp3 ILCpn
DBICp1 DBICp2 DBICp3 DBICpn 0.6 0.4 0.2 e ru0.0 s a e m _ F 0.6 0.4 0.2 0.0 k means
Resume
TD cluster
Heuristic
DBI IL IL_DBI MAX u1 u2 u3 u4 u5 u6 u7 u1 u2 u3 u4 u5 u6 u7 u1 u2 u3 u4 u5 u6 u7 User
Therefore, the parameter selection function S( u) could be defined as:
(pi, if maxpi (DBI) & minpi (IL) S( u) = p0i, if maxp0i (DBI) in 1st quartile (20)
In detail, the function S takes as input a matrix containing the parameters vector pi, a trail of mobility traces M , the computed clustering C(pi, M ) as well as the quality metrics, such as Information loss (IL(C)) and the Davis-Bouldin index (DBI(C)). Once all these values have been computed for each evaluated set of parameters, two cases are possible. In the first case, both IL and DBI agree on the same set of input parameters. In the second situation, both IL and DBI refer each one to a different set of parameters. In this case, the algorithm sorts the values by IL in the ascending order (i.e., from the smallest to the largest information loss value). Then, it chooses the set of parameters with the greatest DBI in the first quartile.
For the sake of evaluation, our methodology was tested using the LifeMap dataset to check if the chosen parameters are optimal. We have tested the method with the seven users of LifeMap that have annotated manually their POIs. Consequently, for every set of settings of each clustering algorithm, we have computed the F-measure because we have the ground truth as depicted in Figure 2. The ”MAX” bar represents the best F-measure for the given user and it is compare to the F-measures obtained when using the ”DBI”, ”IL” or ”IL DBI” as indicators to choose the best input parameters configuration. Finally, this method has a satisfactory performance extracting a good number of POIs for maximizing the F-measure achieving a difference of only 9% with respect to the F-measure computed from the data with the ground truth. 6
In the current paper, we have presented a method to extract the a optimal number of POIs. Consequently, based on the method described in tis paper, we are able to find an appropriate number of POIs relying only on the quality metrics of the extracted clusters and without the knowledge of the ground truth. Nonetheless, we are aware of the small size of dataset but the results encourage us to continue in this direction.
Therefore, in the future we plan to test our method in a larger dataset and in presence of noise like downsamplig or random distortion. Another idea is to evaluate the impact of this method in more complex attacks like prediction of future locations or deanonymization to verify if this step can affect the global result of a chain of inference attacks.