# Releasing Differentially Private Trajectories with Optimized Data Utility
## 4 Trajectory Synthesis
### Private Location Clustering  
Since the location inference attacks aim to infer individuals' actual (or precise) locations from obfuscated locations, a widely used remedy is to replace the actual locations with blurred locations such as grids [6] or clusters [22]. The location privacy protection algorithms based on grids split the geographical space where individuals move into uniform and rectangular cells. The locations inside a cell are represented by the cell itself. However, a careless setting of the cell size is likely to divide a place in nature into different cells, which could lose original location semantics. In contrast, recent works have demonstrated that the clustering has a more natural division on geographical space, so the neighboring locations that share the same semantics have a greater chance to gather together [22]. Therefore, despite defending against location inference attacks, another advantage of location clustering is the better preservation of the semantic utility of individual trajectories. We apply \(K\)-means as the fundamental clustering algorithm. It is easy to be extended for privacy protection, especially for differential privacy, because of its efficiency in computing and simplicity in parameter configuration. However, previous efforts showed that clustering on individual data without any privacy protection measures could lead to a compromise on privacy, e.g., the adversary could find out whether a given location is in a certain cluster [25]. Therefore, we need to propose a differentially private location clustering algorithm. Despite the clustering, a recent study [26] on private classification provides us with another inspiration. We leave it as our future work. The basic idea of location clustering is calculating the distance of pairwise (actual) locations and then gathering those locations having shorter distances iteratively. To ensure the clustering is differentially private, the random noise generated by the Laplace mechanism is injected into the objective function of \(K\)-means clustering. Finally, actual (or original) locations are blurred into clusters, then each actual trajectory is translated into a sequence of clusters, i.e., a cluster trajectory. The pseudocode of private location clustering is presented in Algorithm 2. ```
0: geographical space \(\mathcal{L}\), number of clusters \(K\), privacy budget \(\epsilon_{1}\), max number of iterations \(p\), sensitivity \(\Delta\). 0: a set of clusters \(\{C_{1},C_{2},\ldots,C_{K}\}\). 1: Initialize cluster centroids \(c_{1}\), \(c_{2}\),..., \(c_{K}\in\mathcal{L}\) randomly. 2:for\(r=1\) to \(p\)do
3: Initialize each cluster \(C_{k}\) with \(\mathcal{O}\), \(k=1,2,\ldots,K\). 4: // Assign the locations in \(\mathcal{L}\) to their closest cluster centroid. 5:for\(i=1\) to \(|\mathcal{L}|\)do
6:\(k^{*}:=\operatorname*{arg\,min}_{k=1,2,\ldots,K}\|l_{i}-c_{k}\|_{2}\), \(l_{i}\in\mathcal{L}\). 7: Add \(l_{i}\) into the cluster \(C_{k^{*}}\). 8: Let \(\gamma_{i,k^{*}}\longleftarrow 1\). 9:for\(k\in\{1,2,\ldots,K\}-\{k^{*}\}\)do
10: Let \(\gamma_{i,k}\longleftarrow 0\). 11:endfor
12:endfor
13: Calculate the objective function \(g=\sum_{i=1}^{|\mathcal{L}|}\sum_{k=1}^{K}\gamma_{i,k}\|l_{i}-c_{k}\|_{2}+Lap( \frac{p\Delta}{\epsilon_{1}})\). 14:if the objective function \(g\) converges, then
15: Break. 16:endif
17: // Update each cluster centroid with the mean of all locations in that cluster. 18:for\(k=1\) to \(K\)do
19: Let \(c_{k}\longleftarrow\frac{1}{|C_{k}|}\sum_{k\in C_{k}}l\). 20:endfor
21:endfor
22:return\(\{C_{1},C_{2},\ldots,C_{K}\}\). ```  
**Algorithm 2** Private location clustering. In line 1, we initialize \(K\) cluster centroids with the locations uniformly chosen from the geographical space \(\mathcal{L}\) at random, where \(\mathcal{L}\) is actually the set of locations occurring in the actual trajectory dataset \(D_{A}\). After that, we iteratively update the clusters until the convergence. The steps in a single iteration are elaborated as follows. In line 3, we initialize each cluster with an empty set.