## 5 Privacy Risk Assessment: Advancements within the PRUDEnce Framework
### Relationship between Entropy, Feature Frequency, and Re-Identification Risk
#### 5.1.1 Formal Proof  
Here, we present formal proof regarding the correlation between the entropy of features' frequency distribution and the risk of re-identification.  
**Claim:** trajectory features with low entropy in their frequency distribution are those with low frequency, and they are more at risk of re-identifying the data owner.  
Proof.: entropy is a measure of uncertainty or randomness in a probability distribution. Let \(x_{ui}\) represent the \(i\)-th feature of record \(x_{u}\) of dataset \(D_{n=1}^{N}\) where \(N\) is the total number of individuals. The Shannon Entropy [26] for feature \(x_{i}\) is given by  
\[E(x_{i})=-\sum_{u=0}^{N}p_{u}(x_{ui}=v)\log_{2}p_{u}(x_{ui}=v)\]  
where \(p_{u}(x_{ui}=v)\) is the probability that individual \(u\) has a feature value _vs._ for \(x_{i}\)  
The probability \(p_{u}(x_{ui}=v)\) can be calculated based on its frequency:  
\[FR(u,v)=|\{x_{j}|x_{j}i=vs.j=u\}|\]  
in individual \(u\)'s data divided by the individual data size \(N\):  
\[p_{u}(x_{ui}=v)=\frac{FR(u,v)}{N}\]  
Substituting \(p_{u}(x_{ui}=v)=\frac{FR(u,v)}{N}\) into the entropy formula, we obtain  
\[E(x_{i})=-\sum_{u=0}^{N}\frac{FR(u,v)}{N}\log_{2}\frac{FR(u,v)}{N}\]  
For a feature with low frequency, \(FR(u,v)\) is small for all \(u=0,\ldots,N\). Therefore, the probability \(p_{u}(x_{ui}=v)\) is also small. In the low-frequency scenario, where the feature value frequency is low, the probability \(p_{u}(x_{ui}=v)\) is also low, leading to a smaller contribution to the overall entropy. This is because \(p_{u}(x_{ui}=v)\log_{2}(p_{u}(x_{ui}=v))\) is close to zero when \(p_{u}(x_{ui}=v)\) is small. Hence, the entropy \(E(x_{i})\) is lower for low-frequency features.  
Conversely, in the high-frequency scenario, where the feature value frequency is high, the probability \(p_{u}(x_{ui}=v)\) is higher. This results in a larger contribution to the overallentropy, as \(p_{u}(x_{ui}=v)\log_{2}(p_{u}(x_{ui}=v))\) is higher when \(p_{u}(x_{ui}=v)\) is larger. Hence, the entropy \(E(x_{i})\) is higher for high-frequency features.  
**Base Case:** we consider the case where _vs_. appears only once in the dataset. This means that \(FR(u,v)=1\) for an individual \(u\) and \(0\) for all others. The entropy calculation becomes  
\[E(x_{i})=-\bigg{(}\frac{1}{N}\log_{2}\frac{1}{N}\bigg{)}=-\bigg{(}\frac{1}{N} \cdot(-\log_{2}N)\bigg{)}=\frac{\log_{2}N}{N}\]  
Since \(S(u)\) is a finite positive number, \(\frac{\log_{2}N}{N}\) is positive but small. Thus, \(E(x_{i})\) is low.  
**Inductive Step:** we assume that, for a feature value _vs_. appearing \(k\) times in the dataset, the entropy \(E(x_{i})\) is low. We must show that the entropy remains low if the feature \(x_{i}\) appears \(k+1\) times.  
If _vs_. appears \(k+1\) times, the probabilities \(p_{u}(x_{ui}=v)\) will still be small because \(FR(u,v)\) divided by \(N\) remains small. Thus, the term \(p_{u}(x_{ui}=v)\log_{2}(p_{u}(x_{ui}=v))\) for each \(u=0,\ldots,N\) will contribute a small value to the overall entropy.  
With these small contributions, we see that the entropy \(E(x_{i})\) will increase slightly but remain low because the additional term for the \(k+1\)-th occurrence is small.  
Therefore, by induction, features with low frequency have low entropy.  
**Conclusion:** features with low entropy in their frequency distribution, indicating low frequency, contribute less to the overall uncertainty. However, this also means that these features are more unique. The uniqueness of these features makes it easier to re-identify the data owners, as fewer individuals have these low-frequency features. This establishes a link between local entropy and uniqueness in the data. Therefore, we have shown that features with low entropy are indeed those with low frequency, and can pose a higher risk of re-identifying the data owner. For this reason, we use entropy and frequency to reduce the size of the background knowledge set when evaluating maximum risk and _empirical privacy risk_ across the entire dataset.