K-Means Clustering with Local Distance Privacy

We utilize the one-dimensional distance property to describe the high-dimensional data space. Then all the data points in the domain can be described as the distance relationship to the user’s true data record as shown in Fig. 1 .

10.26599/BDMA.2022.9020050.F001 Fig. 1Noisy distance sampling.

Our purpose is to get a data record whose distance to the user’s real data record cannot be distinguished from the distances between all other data records to the real data record. We say the perturbation method achieves distance privacy if the adversary cannot know how far the perturbed data record to the user’s real data record by observing the report. We propose two methods to achieve distance privacy: the BLM and CIM.

Bounded Laplace method. BLM is similar to the traditional Laplace mechanism, but it is bounded and performed on the distance property instead of the attribute value. Specifically, given the privacy budget $ϵ$ and the user’s real data record $r$ , the probability density function of generating data record $r^{\prime }$ with distance $d(r,r^{\prime })$ is shown as follows:

(2) $$F^{\text{blm}}=\frac{ϵ}{\mathrm{\ell }(1-{\text{e}}^{-ϵ})}\cdot {\text{e}}^{-\frac{ϵ}{\mathrm{\ell }}d(r,r^{\prime })}$$

Since any possible data record $r^{\prime }$ has the distance $d(r,r^{\prime })⩽\mathrm{\ell }$ , the normalization factor ${\displaystyle \frac{ϵ}{\mathrm{\ell }(1-{\text{e}}^{-ϵ})}}$ ensures the noisy distance be sampled in the range $[0,\mathrm{\ell }]$ . And the whole sampling process satisfies the local differential privacy definition.

Theorem 3 The proposed BLM satisfies $ϵ$ -local differential privacy.

Proof

(3) $${\displaystyle \frac{\mathrm{Pr}[d^{*}(r,r^{*})/d(r,r^{*})]}{\mathrm{Pr}[d^{*}(r^{\prime },r^{*})/d(r^{\prime },r^{*})}}={\text{e}}^{-\frac{ϵ}{\mathrm{\ell }}\cdot (d(r^{\prime },r^{*})-d(r,r^{*}))}⩽$$ $${\text{e}}^{\frac{ϵ}{\mathrm{\ell }}\cdot d(r,r^{\prime })}⩽{\text{e}}^{ϵ}$$

where $d^{*}(r,r^{*})=d^{*}(r^{\prime },r^{*})$ . Therefore, the proposed method provides a local differential privacy guarantee.

■

Cluster indistinguishable method. Instead of treating all the data records as the same, CIM incorporates the distance metric for privacy evaluation, which is named $d_{\chi }$ -privacy^{[ 12 ]}. Specifically, it provides stronger privacy for data records with distances closer to the user’s real data record and weaker privacy for records that are far away from the user’s real data record. Following is the sampling distribution.

(4) $$F^{\text{cim}}=\frac{ϵ}{1-{\text{e}}^{-ϵ}}\cdot {\text{e}}^{-ϵ\cdot d(r,r^{\prime })}$$

Theorem 4 The proposed CIM satisfies local $d_{\chi }$ -privacy.

Proof

(5) $${\displaystyle \frac{\mathrm{Pr}[d^{*}(r,r^{*})/d(r,r^{*})]}{\mathrm{Pr}[d^{*}(r^{\prime },r^{*})/d(r^{\prime },r^{*})}}={\text{e}}^{-ϵ\cdot (d(r^{\prime },r^{*})-d(r-r^{*}))}⩽$$ $$\mathrm{\hspace{1em}}{\text{e}}^{ϵ\cdot d(r,r^{\prime })}$$

where $d^{*}(r,r^{*})=d^{*}(r^{\prime },r^{*})$ .

■

To recover the feature value of perturbed data record $r^{\prime }$ , we model the data record generation process as an optimal process. Specifically, we force the generated synthetic data record to follow the restriction that the distance to the user’s real record equals $\hat{d}$ .

$$\text{loss}=\sqrt{{\displaystyle \underset{i=1}{\overset{d}{\sum }}}{(v_i-{\hat{v}}_i)}^2}-\hat{d}.$$

Specifically, we define the distance between the perturbed data record and the real data record as a loss function, and then keep updating a synthetic data record until satisfying the stop condition. The details can be found in Algorithm 3.

We initialize a data record randomly (Line 1), and utilize the distance between the synthetic data record and the real data record as the loss function (error) (Line 3). We define $E$ as the distance difference (Line 4). We continuously update the synthetic data record until $E$ reaches the threshold (Lines 5–12).

Remark We would like to remark here that the proposed method ensures distance privacy that the attacker has no idea how close the observed data record is to the user’s real data record. That is, the distances instead of the data records are indistinguishable. Since the synthetic data record is generated totally random and only restricted to the distance property, some of the generated data value may be outside of the data domain. Then, the attacker can infer that this value is not the true value. But even so, the attacker cannot infer its real value.