Achieving differential privacy for $k$-nearest neighbors based outlier detection by data partitioning
When applying outlier detection in settings where data is sensitive, mechanisms which guarantee the privacy of the underlying data are needed. The $k$-nearest neighbors ($k$-NN) algorithm is a simple and one of the most effective methods for outlier detection. So far, there have been no attempts made to develop a differentially private ($\epsilon$-DP) approach for $k$-NN based outlier detection. Existing approaches often relax the notion of $\epsilon$-DP and employ other methods than $k$-NN. We propose a method for $k$-NN based outlier detection by separating the procedure into a fitting step on reference inlier data and then apply the outlier classifier to new data. We achieve $\epsilon$-DP for both the fitting algorithm and the outlier classifier with respect to the reference data by partitioning the dataset into a uniform grid, which yields low global sensitivity. Our approach yields nearly optimal performance on real-world data with varying dimensions when compared to the non-private versions of $k$-NN.
Code (0)
등록된 구현이 없습니다.
Tasks
Outlier DetectionSimilar Papers 제목 키워드 기반
ReuseKNN: Neighborhood Reuse for Differentially-Private KNN-Based Recommendations
User-based KNN recommender systems (UserKNN) utilize the rating data of a target user's k nearest neighbors in the recommendation process. This, however, increases the privacy risk of the neighbors since their rating dat…
Recommendation SystemsA Local Density-Based Approach for Local Outlier Detection
This paper presents a simple but effective density-based outlier detection approach with the local kernel density estimation (KDE). A Relative Density-based Outlier Score (RDOS) is introduced to measure the local outlier…
Density EstimationObjectOutlier DetectionGenerating Synthetic Data with Locally Estimated Distributions for Disclosure Control
Sensitive datasets are often underutilized in research and industry due to privacy concerns, limiting the potential of valuable data-driven insights. Synthetic data generation presents a promising solution to address thi…
ClusteringHyperparameter OptimizationImputationModel Optimization+1Neighborhood Averaging for Improving Outlier Detectors
We hypothesize that similar objects should have similar outlier scores. To our knowledge, all existing outlier detectors calculate the outlier score for each object independently regardless of the outlier scores of the o…
On a Utilitarian Approach to Privacy Preserving Text Generation
Differentially-private mechanisms for text generation typically add carefully calibrated noise to input words and use the nearest neighbor to the noised input as the output word. When the noise is small in magnitude, the…
Privacy Preservingtext-classificationText ClassificationText Generation