# An Effective Grouping Method for Privacy-Preserving Bike Sharing Data Publishing
## 3 Methodology
### Grouping Methods  
In this section, we develop solutions from the problem definitions and design anonymization algorithms. The anonymization algorithm consists of the following steps: attribute grouping, tuple grouping with random permutation, and column generalization.  
In attributes grouping, the related attributes are grouped in a fashion such that each attribute belongs to one subset, i.e., start location and end location form a subset. Each grouped subset forms a column. Particularly in a bike sharing table \(T\), there will be \(c\) columns \(C_{1},C_{2},...,C_{c}\) satisfying \(\bigcup_{i=1}C_{i}=A\) and for any \(1\leq i_{1}\
eq i_{2}\leq c\), \(C_{i_{1}}\cap C_{i_{2}}=\emptyset\).  
We group the related attributes by measuring the correlation between them. For the bike sharing data publishing, we consider most of the attributes to be categorical. The correlation between attributes are calculated by the mean square contingency coefficient [19; 56]. Given two attributes \(A_{1}\) and with value domains \(\{v_{11},v_{12},...,v_{1d_{1}}\}\) and \(\{v_{21},v_{22},...,v_{2d_{2}}\}\), respectively, and domain sizes \(d_{1}\) and \(d_{2}\), the mean square contingency coefficient between attributes \(A_{1}\) and \(A_{2}\) is calculated as follows:  
\[\phi^{2}(A_{1},A_{2})=\frac{1}{min\{d_{1},d_{2}\}-1}\sum_{i=1}^{d_{1}}\sum_{j=1 }^{d_{2}}\frac{(n_{ij}-n_{i}.n_{j})^{2}}{n_{i}.n_{j}}\]  
where \(n_{i}\). and \(n_{\cdot j}\) are the fractions of occurrence of \(v_{1i}\) and \(v_{2j}\) in the data, respectively. \(n_{ij}\) is the fraction of cooccurrence of \(v_{1i}\) and \(v_{2j}\) in the data. Therefore, \(n_{i}\). and \(n_{\cdot j}\) are the marginal totals of \(n_{ij}:n_{i}\). \(=\sum_{j=1}^{d_{2}}n_{ij}\) and \(n_{\cdot j}=\sum_{i=1}^{d_{1}}n_{ij}\). It can be shown that \(0\leq\phi^{2}(A_{1},A_{2})\leq 1\).  
After estimating the correlation between attributes, we use the widely-known _k-medoid_ clustering algorithm PAM (Partition Around Medoids) [57] to partition attributes into columns. In the algorithm, each attribute constitutes a point in the cluster space. The difference between two attributes is determined as \(d(A_{1},A_{2})=1-\phi^{2}(A_{1},A_{2})\), which lies between 0 and 1. In the space, two correlated attributes will have a smaller dissimilarity between the corresponding data points.  
We group attributes so that highly correlated attributes are placed in the same column. This approach is useful for privacy and data utility [19]. Regarding data utility, grouping highly correlated attributes protects the relationships among those attributes. In terms of data privacy, associating correlated attributes reduces the identification risks. Because relationships between uncorrelated attribute values are less common and hence more identifiable, it is desirable to break the associations between uncorrelated attributes to preserve privacy.  
The tuple grouping consists of different subsets of Table \(T\), such that each tuple relates to a specific subset based on their trip duration. Every subset of tuples denotes a bucket \(B\)[19]. Let \(T\) be a bike sharing table that contains \(b\) buckets \(B_{i}(1\leq i\leq b)\). Every bucket \(B\) contains \(n\) tuples \(t_{j}(1\leq j\leq n)\). The Mondrian [58] algorithm is used, and it follows a top-down approach without generalization for separating tuples to create a bucket. For each bucket, the values in every Column are randomly permuted to break the cross-column correlations. Hence, it will break the linkage between the \(QI\) values and sensitive values and reduce the adversary's confidence in linking with the \(POI\).  
In the bike sharing datasets, the Gender column holds an essential factor to breach personal privacy. Therefore, we use generalization methodology [29] to generalize the Gender column to preserve user privacy in the published bike sharing dataset.