Abstract
Clustering and analyzing collected data can improve user experiences and quality of services in big data and IoT applications. However, directly releasing original data brings potential privacy concerns, which raises challenges and opportunities for privacy-preserving clustering. In this paper, we study the problem of non-interactive clustering in a distributed setting under the framework of local differential privacy (LDP). We first extend the Bit Vector, a novel anonymization mechanism, to be functionality-capable and privacy-preserving. Based on the modified encoding mechanism, we propose the kCluster algorithm for clustering in the anonymized space. We show the modified encoding mechanism can be easily implemented in existing clustering algorithms that only rely on distance information, such as DBSCAN. Theoretical analysis and experimental results validate the effectiveness of the proposed schemes.
1. Introduction
In the era of IoT and Big Data, clustering is essential for tasks like user profiling and pattern recognition. However, centralizing raw data from multiple users or organizations poses massive privacy risks. Current solutions typically fall into two categories: interactive methods, which require constant communication, and non-interactive methods, which often only support simple statistics like mean estimation. The challenge addressed in this research is how to perform complex clustering on distributed data without ever seeing the original values, while ensuring that an individual's specific data point remains mathematically protected.
2. System Architecture
The proposed framework operates in a distributed environment where multiple data sources (e.g., Alice, Bob) maintain their own datasets. Instead of sending raw data to a central server, each source applies a distance-aware encoding mechanism to anonymize their records locally. These anonymized records are then sent to an untrusted aggregator.
As shown in the architecture above, the aggregator receives a set of anonymized data, constructs a distance matrix, and performs clustering analysis without ever accessing the plaintext source data. This non-interactive approach significantly reduces communication overhead and enhances privacy.
3. The DPBV Mechanism and Distance Estimation
The core of this approach is the Differentially Private Bit Vector (DPBV). This mechanism maps numerical values into a bit string (Hamming space) that preserves Euclidean distances. To satisfy $(\epsilon, \delta)$-LDP, the authors add a randomized response layer that flips bits with a specific probability.
A significant technical hurdle in using Bit Vectors is the "local view" problem. Standard Bit Vectors only accurately estimate distances within a small range; as the actual Euclidean distance increases, the estimated distance eventually plateaus, losing accuracy for global relationships.
To resolve this, the authors developed a Distance Consistence Algorithm. This algorithm treats the distance matrix like a graph, using stable short-distance estimates to "triangulate" and refine larger, global distances that would otherwise be inaccurate due to LDP noise.
4. The kCluster Algorithm
Traditional clustering algorithms like k-means require calculating a "mean" or centroid, which is impossible in the DPBV anonymized Hamming space. To overcome this, the authors propose kCluster. Instead of relying on centroids, kCluster assigns points to clusters based on the average distance to all other points already in a cluster. This allows the aggregator to perform high-quality clustering using only the distance matrix derived from the anonymized bit vectors.
Additionally, the framework supports Vertical Partitioning. In scenarios where different features of the same data point are held by different parties (e.g., Alice holds age data while Bob holds income data), a specialized decomposition method allows for distance estimation with lower error rates than standard non-decomposed methods.
5. Experimental Results
The researchers evaluated their approach using synthetic geometric datasets (Blobs, Circles, Moons) and the real-world Digit dataset (1,797 hand-written digits). Key findings include:
- High Utility: On the Digit dataset, kCluster achieved a Normalized Mutual Information (NMI) of 74.65%, slightly outperforming standard k-means (74.32%) in certain configurations.
- Robust Privacy: Under LDP constraints (e.g., $\epsilon=2$), DP-kCluster maintained an NMI of ~73.57%, significantly outperforming alternative methods like Random Subspace Projection (RSP).
- Scalability: The decomposition method for vertically partitioned data successfully controlled error rates even as data dimensionality increased.
6. Conclusion
DPBV provides a tunable balance between privacy and utility, allowing researchers to adjust the $\epsilon$ parameter based on their requirements. While the mechanism is robust, future work will address potential collusion attacks and the computational overhead of estimating large distances. The team plans to extend this distance-aware encoding to other tasks, including mean estimation and privacy-preserving classification.
Summary updated