符合本地端差分隱私的最近鄰居分類法

Abstract

分類是機器學習(machine learning)中的一個核心問題，而K-最近鄰居分類法(k-nearest neighbors algorithm)因其簡單性而成為分類演算法的絕佳嘗試。但是，將K-最近鄰居分類法應用於敏感資料時，必須考量隱私問題。研究人員開發了本地端差分隱私 (local differential privacy) 框架，這是敏感資料分析的實質標準，以提供一種嚴格的方式來保護用戶的隱私。該框架通過在將資料發送到資料伺服器之前於本地擾亂客戶端的數據來保護用戶的隱私。而在K-最近鄰居分類問題中使用本地端差分隱私的概念，我們可以為用戶提供可靠的隱私保證，同時伺服器端仍然能從的敏感資料中收集有用的統計資訊。 盡我們所知，之前沒有關於本地端差分隱私下的K-最近鄰居分類法的相關研究。因此，在本論文中，我們提出了LDPKNN，一種符合本地端差分隱私的K-最近鄰居分類演算法。我們將K-最近鄰居分類問題重新表述為頻率估計(frequency estimation) 任務，並應用一致性(consistency)的後處理技術來實現在本地端差分隱私下分類。各種評估指標和資料集的實驗結果表明，我們提出的方法優於直觀的解決方案，並在隱私與效用性取得良好的平衡。