支持隐私保护的<i>k</i>近邻分类器

分类器是数据挖掘中对样本进行分类的方法的统称.其设计目标是在通过学习后, 能够将数据分到已知类别.分类器不仅应用在搜索引擎以及各种检索程序中, 而且也大量应用在数据分析与预测领域.kNN分类器是一种重要的分类器, 广泛应用于生物信息学、股票预测、网页分类、鸢尾花类别预测等领域. 分类器在广泛应用的同时, 也产生了严重的用户隐私泄露问题[1, 2], 一旦泄露, 会给数据拥有者带来危害.比如, 不法分子盗取患者癌症信息, 利用患者迫切希望治愈的心理, 向患者销售高价药品, 骗取钱财; 在利用kNN进行股票预测时, 如果股民的个股信息在分类过程中被泄露, 就会给股票市场带来混乱.分类器处理的数据量大、种类多, 与之相关的用户数据隐私保护形势也非常严峻.目前, 针对数据分类过程中的隐私保护研究主要集中在密文数据运算方面, 但是该类技术也存在如下问题:(1)一些分类器对密文数据的运算复杂, 运算效率较低; (2)加密技术针对的是特定的分类器, 缺乏普适性. kNN分类器是监督学习中“懒惰学习”(lazy learning)的典型代表, 监督学习过程由两个阶段构成. (1)   样本训练阶段:在此阶段, 首先获取在准备工作阶段处理好的训练数据; 然后根据分类器类型选择分类算法, 对训练数据进行训练得到模型W, 以此作为分类阶段的一项输入. (2)   应用阶段(分类阶段):分类器C通过模型W对测试向量X进行分类预测, 得到最终的分类结果C(W, X). 在样本训练和分类阶段, 都可能发生用户隐私信息的泄露:在样本训练阶段, 数据拥有者不希望自己拥有的数据信息被泄露出去, 甚至对训练者也要进行保密, 这就需要对训练数据进行加密处理; 在分类阶段, 训练者会将得到的模型W作为分类器的构成部分, 并将分类器发布出去提供服务, 但不希望成果被第三方获取, 这就需要对分类模型和测试向量进行加密.总而言之, 分类器要保证数据的隐私性必须从两方面入手:(1)训练数据集和模型W的隐私保护; (2)测试向量X和分类结果C(W, X)的隐私保护. 目前已有一些关于分类器隐私保护的研究成果, 但大多数方案都是针对训练阶段数据的隐私保护, 很少有针对分类模型和分类过程的保护.因此, 设计基于加密数据的基本操作加密协议并以模块化顺序组合的方法构造安全的分类器, 使其从训练阶段到分类过程都能保证安全性, 同时保证待测数据能够获得一个准确的类别, 是当前机器学习隐私保护的重要研究方向之一.1 相关工作 分类器的构造和实施过程就决定其在隐私保护方面存在隐患, 例如, 在训练样本上执行分类器算法, 生成分类模型, 很容易造成样本数据的泄露; 在测试样本上执行分类模型, 生成预测结果时, 客户端会很容易得到分类模型, 而服务器端也可以轻易获取到输入的测试数据.因此, 分类器在样本训练和分类阶段的数据隐私问题已成为分类器隐私保护中最为重要的研究内容之一. (1) 样本训练阶段 为了保证在样本训练阶段原始数据的隐私性, 应将原始数据隐藏起来, 在此阶段, 不同的分类器会选择不同的算法来训练原始数据, 比如贝叶斯算法、支持向量算法、决策树算法等.这些算法包含了点积运算、加法运算、比较运算.为了保证隐藏后的数据仍然能够进行上述运算, 本阶段使用的隐私保护技术应满足3个方面的要求:(1)不改变原始数据的整体分布趋势; (2)不能从隐藏后的数据中直接推算出原始数据值; (3)确保经过变换后的数据不会降低分类器的分类效果.目前, 研究人员采用的技术主要分两类:数据干扰和数据加密.文献[3]提出一种基于非线性维数降低(即非度量多维缩放)来干扰原始数据的隐私保护框架, 使用k-Nearest Neighbor分类算法对分类任务中的新型隐私保护数据挖掘(privacy-preserving data mining, 简称PPDM)方法进行了测试, 在隐藏隐私数据的同时, 保证了数据的有效性; 文献[4]提出了数据扰动技术并利用该技术构建了决策树分类器, 之后, 相继提出了不同的扰动方法[5, 6].但是, 扰动技术不能保证密文数据的语义安全, 且数据添加了统计噪声易造成分类器的分类精度下降.文献[7]提出了两方参与的决策树分类器, 其假定数据分布在两方; 文献[8-10]利用安全多方计算(secure multi-party computation, 简称SMC)技术构造了安全的分类器; 文献[11]设计了一种基于主成分分析(primary component analysis, 简称PCA)的协同学习隐私保护方法, 其利用PCA实现了在协同学习过程中对压缩数据的隐私保护; 文献[12]设计了一种加法同态代理聚合方案实现了云端患者的历史数据的隐私保护, 引入了隐私保护的top-k疾病名称检索协议保证了朴素贝叶斯分类器的安全性; 文献[13]提出了一种分布式系统的隐私保护数据分类和相似性评估方案, 该方案在分类和相似度评估过程中不泄露任何关于新到达数据和训练模型的信息, 其最终的分类结果除外; 文献[14]提出了将线性分类器和IPE(inner product encryption)相结合的方法来对加密数据进行分类, 其隐私保护分类方案允许用户的数据被加密, 但服务器能够获知最终的加密结果; 文献[15]设计了实用的安全模型, 通过研究在安全的两方计算框架中的一些多元统计分析方法, 生成了一些构造块, 解决了安全的两方多元线性回归问题和安全的两方多变量问题; 文献[16]基于安全多方协议与同态加密方案训练几种简单的分类器, 例如线性分类器, 该分类器是支持加密数据分类的, 但是其构造的模型安全性较低, 导致客户端不仅能够得知最终的分类结果, 而且可能会获取分类模型的信息, 造成分类模型信息的泄露.综上所述, 在样本训练阶段不仅要隐藏原始数据, 还要将分类规则进行隐藏, 即保护服务器参与分类数据的隐私性, 防止通过模型或分类过程推导出个人信息. (2) 分类阶段 在分类阶段, 支持用户数据隐私性保护的研究成果较少.在文献[17]中, 第三方运行医疗预测函数对全同态加密(fully homomorphic encryption, 简称FHE)的患者数据进行运算, 得到预测结果.该算法仅隐藏了来自云端的输入数据, 在分类阶段, 任何一方都可以获取到分类模型, 容易泄露患者隐私给第三方或各参与方.文献[18, 19]构造了线性分支程序的安全评估, 用此实现了心电图(electrocardiogram, 简称ECG)信号的安全分类.这项技术是基于finely-tuned garbled电路的, 虽然保证了分类过程的安全性, 但分支程序的运行速度较慢.文献[20]利用神经网络[21]构造了安全的分类器, 这是感知器分类器的泛化, 使神经网络分类器能够支持对密文数据的分类. 综上所述, 在分类样本训练阶段的隐私保护研究成果较多, 在分类过程中的隐私保护研究成果则不多见, 容易造成用户隐私信息的泄露.为此, 本文首先对kNN分类器的操作进行分析, 提取出从样本训练阶段到分类过程中所包含的基本操作, 包括加法、乘法、点积、比较; 针对上述基本操作, 设计了相应的安全协议, 然后以模块化顺序组合的方式将其组合生成PP-kNN分类器, 从而保证了样本训练阶段和分类过程的数据隐私性.本文所设计的PP-kNN分类器的基本操作的隐私保护协议是基于差分隐私的, 给加密数据加入噪声, 防止在交互式环境中信息的泄露.在设计基本操作的安全协议时, 选择了两种同态加密方案对数据进行加密, 以增加隐私保护的强度.同时, 所设计的基本协议在半诚实模型下是安全的, 模块化顺序组合方法在该模型下也是安全的, 因此通过顺序组合构造的PP-kNN分类器也是安全的. 本文第1节对kNN分类器和本文使用的加密方法进行描述.第2节给出基本操作安全协议的设计.第3节详细说明支持隐私保护的kNN分类器的构造过程.第4节从计算代价、存储代价等方面对基本操作安全协议及PP-kNN分类器进行性能评估.最后, 对全文进行总结.2 预备知识 2.1 kNN分类器 在kNN分类过程中, 待分类对象的类别可以通过在它附近的训练数据的类别来确定, 所以采取的策略就是找到离待分类对象最近的k个邻居进行分析.kNN分类器的工作流程如下. Step 1.确定k值(最近邻居的个数).一般为奇数, 通常是采用交叉检验来确定(经验规则:k一般低于训练样本数的平方根). Step 2.确定距离度量公式.以文本分类为例, 采用夹角余弦, 得出待分类数据点和所有已知分类数据点的夹角余弦值.按夹角余弦值从大到小排列, 获取距离最近的k个样本(夹角余弦值越大, 角度就越小, 距离也就越近). ●  夹角余弦: $\cos \theta = \frac{{AB}}{{|A