Distance-based machine learning methods have limited applicability to categorical data, since they do not capture the complexity of the relationships among diferent values of a categorical attribute. Nonetheless, categorical attributes are common in many application scenarios, including clinical and health records, census and survey data. Although distance learning algorithms exist for categorical data, they may disclose private information about individual records if applied to a secret dataset. To address this problem, we introduce a diferentially private algorithm for learning distances between any pair of values of a categorical attribute according to the way they are co-distributed with the values of other categorical attributes forming the so-called context. We show empirically that our approach consumes little privacy budget while providing accurate distances.
Most machine learning and data analysis methods rely, directly or indirectly, on their ability
to compute distances or similarities between data objects. Although diferent definitions of
distance/similarity exist, they are relatively easy to compute, provided that data are given in
form of numeric vectors. Additionally, for most of the above-mentioned distance-based methods,
diferentially private counterparts of them have been proposed as well. Diferential privacy [
When data are described by categorical features/attributes, instead, distances can only account
for the match or mismatch of the values of an attribute between two data objects, leading to
poorer and less expressive proximity measures (e.g., the Jaccard similarity). And yet, intuitively,
a patient whose disease is “gastritis” should be closer to a patient afected by “ulcer” than to
one having “migraine”. An eficient solution consists in using some distance learning algorithm
to infer the distance between any pair of diferent values of the same categorical attribute from
data. Among all existing methods, DILCA [
In this paper, we address the problem of learning meaningful distances for categorical data in a diferentially private way. To this purpose, we first introduce a diferentially-private extension of DILCA adopting the exponential mechanisms. We show experimentally that it provides accurate distances even with relatively small values of privacy budget . Additionally, we show that our algorithm (which we call DP-DILCA) is efective in two distance-based learning scenarios, including clustering and k-NN classification.
In this section, we introduce the necessary background required to understand the theoretical foundations of our method and, contextually, we introduce its related scientific literature.
Diferential privacy [
Definition 1 ( -diferential privacy). Let ℳ : Ω →− ℛ be a randomized mechanism (i.e. a stochastic function with values in a generic set ℛ) and consider a real number > 0. We say that ℳ preserves -diferential privacy if for all pair of datasets , ′ difering for only one record
Diferential privacy satisfies two important properties: composition and post-processing [
Several mechanisms and techniques preserving diferential privacy have been proposed in
literature. Two of the most famous mechanisms are the Laplace and the Exponential mechanisms
[
∑︀∈( ) || where ( ) is the set of the attributes belonging to the context of , || is the number of values attribute can assume, and (|) is the conditional probability that takes value given that has value .
The conditional probabilities (|) are estimated from the data: the contingency table between attributes and is constructed and this contingency table can be interpreted as the empirical joint distribution of the two variables.
In this section, we introduce a method whose final goal is to inject some form of randomness
in DILCA in order to make the resulting distances among the values of the target attribute
diferentially private. There are two moments when DILCA algorithm accesses the original
(secret) dataset: the context and the contingency tables computation phases. If the context
selection is made preserving ℎ · -diferential privacy (where ℎ ∈ [
1 (2) + ( ) ;
︁) 1, . . . , } ∖ { }; 3 ( ) ← ∅ 4 for = 1 to do
; 1 ← 2 ℱ ← { 5 6 7 8 end privacy.
Algorithm 1: (, , ℎ · , )
context Input: The original dataset with records and attributes = {1, ...., }, the target attribute ∈ , the privacy budget ℎ, the number of attributes in the and the post-processing theorems guarantee that the overall algorithm preserves -diferential
The context selection procedure used by DILCA is an application of a filter method for
supervised feature selection. Indeed, some work has been done on diferentially private feature
selection. For instance, [
︁) Theorem 3.1 (Sensitivity of ′(, )). Given a dataset with records and two attributes
Algorithm 1 describes the diferentially private version of context selection. It requires the specification, as input parameter, of the desired number of attributes in the context of the target attribute. When setting the value of parameter , one must consider that lower values of are preferable, from a diferentially private point of view. In step 5 of Algorithm 1, the exponential mechanism is applied times, in order to extract the top attributes: each application of the exponential mechanism requires part of the overall privacy budget; thus, the smaller is, the higher the accuracy of the selected context. Algorithm 1 preserves ℎ-diferential privacy.
Once the context of target attribute has been selected, DILCA algorithm computes the contingency table (, ) between and , for each in context. Instead of the exact value (, ), we compute a distorted contingency table via the Laplace mechanism. This 1.0 0.8 e r0.6 o c -s0.4 F 0.2 mechanism needs the specification of two parameters, the sensitivity of the function , that can be proved to be 2, and the privacy budget. Since the total number of needed contingency tables is = |( )|, the privacy budget we spend for each contingency table is (1− ℎ) . In this way, the overall DP-DILCA algorithm preserves -diferential privacy.
In this section, we describe the experiments conducted to evaluate the performances of DPDILCA. For this evaluation, we use four real-world datasets: adult1, NLTCS2, IPUMS-BR and IPUMS-ME3.
In the first experiment, we run DP-DILCA on the real-world datasets in order to assess the quality of the context they select. For each dataset, we consider one attribute at a time as target attribute and we compute its diferentially private context for increasing levels of privacy budget . Then we compare the context selected by DP-DILCA with the context obtained with the corresponding non-private method. In all the experiments we set = 3. To evaluate the similarity between the private and non-private context for each target attribute, we use the F-score, i.e., the harmonic mean of precision and recall. For each , we repeat the experiments 30 times and we compute the mean value of all scores. Figure 1 shows the results of our comparison: for each we report the average value of the F-score over all the attributes of each dataset. In all the datasets, the results achieved by DP-DILCA increase with respect to .
In this section we repeat the same experiments on the real-world data presented in Section 4.1, but we focus on the final output of DP-DILCA: the distances between the values of the target attribute. As before, for each dataset we consider one attribute at a time as target and we compute the diferentially private distance matrix associated to its values, for increasing levels of privacy budget . Then we compare the distances obtained with DP-DILCA with those 1https://archive.ics.uci.edu/ 2http://lib.stat.cmu.edu/ 3https://international.ipums.org/ obtained with the corresponding non-private method. In this experiment we set = 3 and ℎ = 0.3. We quantify the linear correlation between the private distance matrix ′, with shape × , and its non-private counterpart through the sample Pearson’s correlation coeficient. The coeficient takes values between -1 (perfect negative correlation) and 1 (perfect positive correlation). If the two matrices are not correlated we will have ∼= 0.
For each , we repeat the experiments 30 times and we compute the mean value of the sample Pearson correlation coeficient. Figure 2 shows the results of our computations: for each we report the average value of the measure over all the attributes of each dataset. The results show that there is positive correlation between private and non-private distances and the Pearson’s coeficient increases as grows. Notice that the Pearson coeficient is always 1 when the target attribute has only two values. For this reason, for NLTCS (Figure 2(b)), which consists of binary attributes only, the Person’s correlation is always maximum.
In this section, we assess the efectiveness and utility of the distances computed by our
differentially private algorithms. To this purpose, we embed DP-DILCA into two distance-based
learning algorithms: the Ward’s hierarchical clustering algorithm and the kNN classifier. Both
the algorithms take as input the matrix of the pairwise distances between the data objects.
DP-DILCA’s output is the distance between values of a categorical attribute; if it is applied to
all attributes in , then the distance between any pair of objects , , both described by
can be computed as (, ) = √︀∑︀∈ [., .]2, where is the distance
matrix returned by DP-DILCA for attribute and . and . are the values of attribute
on objects and [
We run the experiment about clustering as follows: for each real-world dataset, we compute
the object distance matrix using the diferent private and non private metrics, then we run
Ward’s hierarchical clustering with these matrices as input. Since the hierarchical algorithm
returns a dendrogram which, at each level, contains a diferent number of clusters, we consider
the level corresponding to the number of clusters equal to the number of classes. We call the
overall clustering models and , depending on the distance metric
adopted. We evaluate the quality of the results through the adjusted rand index (ARI) computed
w.r.t. the actual classes [
As last experiment, we run the kNN classification algorithm, with = 5. We perform a 4-fold cross-validation: one fold is retained as test set, then the metrics , and are learned on the remaining 3 folds and the classification model is trained on the same set. We call the overall models and , depending on the distance learning algorithm used. For each dataset, we apply the four kNN models 30 times and compute the mean accuracy of the classification on the the test set. The process is repeated four times and the results are further averaged on the four test sets. In Figure 3(b) we report the mean accuracy of all the models for increasing levels of privacy budget . The results of are always very close to those of , even for very low levels of .
We have introduced a new family of diferentially private algorithms for the data-driven computation of meaningful and expressive distances between any two values of a categorical attribute. Our approach is built upon an efective context-based distance learning framework whose output, however, may reveal private information if applied to a secret dataset. For this reason, we have proposed a randomized algorithm, based on the Laplace and exponential mechanisms, that satisfies -diferential privacy and returns accurate distance measures even with relatively small privacy budget consumption. Additionally, the metric learnt by our approach can be used profitably in distance-based machine learning algorithms, such as hierarchical clustering and kNN classification. This work is supported by Fondazione CRT (grant number 2019-0450).