Differentially private nearest neighbor classification

Gürsoy, Mehmet Emre and İnan, Ali and Nergiz, Mehmet Ercan and Saygın, Yücel (2017) Differentially private nearest neighbor classification. Data Mining and Knowledge Discovery (SI), 31 (5). pp. 1544-1575. ISSN 1384-5810 (Print) 1573-756X (Online)

[thumbnail of Differentially_Private_K_NN.pdf] PDF
Restricted to Registered users only

Download (1MB) | Request a copy


Instance-based learning, and the k-nearest neighbors algorithm (k-NN) in particular, provide simple yet effective classification algorithms for data mining. Classifiers are often executed on sensitive information such as medical or personal data. Differential privacy has recently emerged as the accepted standard for privacy protection in sensitive data. However, straightforward applications of differential privacy to k-NN classification yield rather inaccurate results. Motivated by this, we develop algorithms to increase the accuracy of private instance-based classification. We first describe the radius neighbors classifier (r-N) and show that its accuracy under differential privacy can be greatly improved by a non-trivial sensitivity analysis. Then, for k-NN classification, we build algorithms that convert k-NN classifiers to r-N classifiers. We experimentally evaluate the accuracy of both classifiers using various datasets. Experiments show that our proposed classifiers significantly outperform baseline private classifiers (i.e., straightforward applications of differential privacy) and executing the classifiers on a dataset published using differential privacy. In addition, the accuracy of our proposed k-NN classifiers are at least comparable to, and in many cases better than, the other differentially private machine learning techniques.
Item Type: Article
Additional Information: Wos Document Type: Article; Proceedings Paper / Conference: ECML PKDD Conference / Location: Skopje, MACEDONIA / Date: SEP 18-22, 2017
Uncontrolled Keywords: Data mining; Differential privacy; k-Nearest neighbors
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Yücel Saygın
Date Deposited: 15 Aug 2018 10:12
Last Modified: 26 Apr 2022 09:58
URI: https://research.sabanciuniv.edu/id/eprint/35798

Actions (login required)

View Item
View Item