建议先看CREDO:Efficient and Privacy-preserving Multi-level Medical Pre-Diagnosis Based on ML-KNN读书笔记（一）https://blog.csdn.net/qq_42145187/article/details/106999076

Zhu D, Zhu H, Liu X, et al. CREDO: Efficient and privacy-preserving multi-level medical pre-diagnosis based on ML-kNN[J]. Information Sciences, 2020: 244-262.

读书笔记（一）大体上介绍了CREDO的系统结构，读书笔记（二）则是详细地揭示了系统的五个阶段以及与隐私保护的分类相关工作等，作者水平有限，有不足之处欢迎交流指正。

一、系统初始化

(1) SP生成一系列的系统参数，为MU注册提供服务

(2) 计算先验概率和后验概率矩阵

(3) k-means聚类

二、生成查询向量

(4) MU使用SPDE加密自己的查询向量

注意算法SPDE是参考文献[46]提出的，本文是直接拿过来使用的。

三、疾病类型导航

(5) 基于PPDS算法，MU找到与自己最相符的group,并将该结果返回给SP

具体过程分两步走：

SP核对查询信息的有效性和以及MU的ＩＤ，核对后，解密并存储该用户信息

关于此处验证信息的有效性，左右两边都可以进行验证，移一下指数即可得到正确答案，这里不再详述了

MU接收到签名Sig2后，也是先对该签名做检查，核对信息的有效性

解密计算后得到Spearman距离集，选择距离最小的一个聚类中心，即可得到对应的簇。（注意，如果只选择一个最小值，预诊断的准确性会下降，但是如果我们选择多个较少的值，效率就会下降。所以选择高准确性还是高效率由MU决定。）MU创建sig3并发送给SP。

Gm的大小由系数𝛼𝛽1 来决定的，前提条件是需要满足下列两个式子

四、生成隐私保护的疾病预诊断

根据图5可以发现，如何得到特定的类以及类中实例的一个过程，先是在所有数据上进行k-means聚类，然后计算聚类后的聚类中心，根据聚类中心到查询向量V之间的spearman距离，选择距离较小的聚类中心，然后选取属于这些聚类中心的实例。

PC矩阵就是根据得到的实例生成的一个矩阵，每一行代表一个实例，每一列代表一类疾病

之后SP端会将矩阵PC发送给MU，之后就是再次hi行算法二，其中的计算过程可以参考第三步疾病类型导航阶段，计算的流程是一样的。

五、查询结果分析

重复第三步中的计算，根据Gs计算出来的大小排序，MU删除矩阵Ｐｃ中无用的实例，得到一个新的矩阵Pck,矩阵中剩下的每一行都对应MU的k近邻实例的一个类别向量，计算Pck中每一行的和，{sum1,sum2,,,,,sumf}，结合在第一阶段生成的矩阵PA 和PB

可以用l标签在整个训练集上出现的次数除以标签总次数来求出先验概率

注：分子代表的就是所有向量中，其k近邻有j个l标签，且其自身也有l标签的向量的个数。（看PCｋ矩阵中的列）

       分母即为这个向量有l标签，其k近邻有0∼m个有标签的情况的向量个数总和。

最后计算

如果b=1的计算出来的wxj值大于b=0时，则认为该病患可能得患有疾病 j，反之。。。。。。

安全性分析

下面的安全性分析都是基于诚实且好奇的模型。中间具体的安全性分析，就不再详细阐述了，如果对这部分感兴趣可以去看看原文。

结论：CREDO能够在保护MU的查询向量和SP的预诊断模型的前提下，提供可验证的多层次医疗预诊断服务。

性能分析

实验环境：

为了度量CREDO在实际环境中的集成性能，我们在智能手机上使用Java编程语言实现CREDO

(2.35GHz四核处理器，6gb内存，Android 8.0.0)和一台计算机(2.20GHz双核处理器，4gb内存，windows 10)。具体来说,一个应用程序CREDO.apk，安装在智能手机中模拟MU, SP的模拟器部署在计算机中，当MU输入医疗数据时，智能手机会向计算机发送加密的查询向量，通过802.11g WLAN得到响应。

采用的数据集Mulan(一个多标签的java库)

准确性：

选定的医学数据集被分为两个分区，一个训练集有333个实例，有645个实例的测试集。每个实例包含1449个属性和45个类别标签，所有1494个维度的值来自set{0,1}，其中1表示该实例包含相应的属性或标签，以及0表示此实例不包含相应的属性或标签。

为了使预诊断结果更加准确，基于5个参数[Hamming Loss, One-error, Coverage,Ranking Loss, Average Precision]

通过实验得到当k=14时，性能是最好的。

表2是在明文域上得出的，当我们在密文上再次执行时，平均精度为0.837 ±0.0273（为了不丢失精度，没有进行k-means聚类操作）

计算复杂度

图6(b)与图6(a)在相同条件下给出了四种方案的通信开销比较。由图可知，随着医疗实例数量的增加，SkNN和SMLDC的通信开销显著增加，远远高于CREDO和EPDK。但在类似的通信开销情况下，CREDO可以实现多标签分类。

通信开销

CREDO可以在通信开销方面实现高效率。

相关工作

将介绍一些安全的kNN查询解决方案、多标签分类的应用和隐私保护医学预诊断的相关工作。保证kNN查询安全的解决方案。安全kNN问题被建模为服务提供者查找用户生成的查询向量x的前k个近邻。安全kNN问题是实现安全的基础ML-kNN查询。

Wong等人[40]开发了一种新的不对称的保留标量积的加密(ASPE)方案，该方案保留两个向量之间的标量积，可用于在加密数据上找到k个最近邻。在在外包给服务器之前，使用了稍微不同的加密方案来加密数据和查询。作为替代方案，Hu等[18]提出了一种基于隐私同态的整体高效解决方案，包括安全遍历方案和加密方案。然而[18,40]中的两种方法都被证明是弱到无法抵抗甚至已知的明文攻击(KPA)。然后Yao et al.[42]和Choi et al.[6]设计了新的基于secure Voronoi diagram (SVD)的安全kNN方法，而不是寻找精确的最近邻居。为了准确地解决安全的kNN问题，Elmehdwi等人[12]利用Paillier密码系统的加性同态特性构造了隐私保护原语，基于原语进行kNN查询处理了加密数据库，用户可以安全的接收k个最近的记录。参考文献[35]进一步扩展了这项工作，其中他们提出了新的解决方案，如安全最小值(SMIN)、安全频率(SF)等并给出了形式安全分析。然而大多数的同态加密方案都需要大量的资源消耗计算。为了避免使用在线服务的大量的密码原语，Wang et al.[38]设计了一种基于保持顺序加密(OPE)和R树的安全kNN方案。然而，OPE提供的密文保留了明文的数字排序，这使得它对推理攻击的抵抗能力较弱。通过使用基于投影函数的方法来编码给定位置的邻居区域， Lei等人[23]提出了一种安全高效的查询处理方案来解决安全的kNN查询问题。在参考文献[23]中，他们提出的方案可以实现较强的安全性和次线性查询处理，但只能返回近似结果，只支持二维查询。

多标签分类的应用。注意到许多真实世界的健康数据可能包含多个标签，越来越多的研究关注引入多标签分类方法。

Li等人[25]提出了一种基于多标签问题变换联合分类的健康与疾病风险预测的多类分类问题变换方法(MLPTJC)。此后，重点研究了高性能多标签分类方法，Li等人在参考文献[15]提出了两种标签选择方法，适用于5G通信领域的医疗推荐。为了提高多标签医学文本分类的准确率，Glinka等[14]将特征选择技术的应用作为前一步，在医学文本报告上进行了大量的实验来展示其优势。Fang等[13]基于电子病历中症状的组成和分布，提出了另一种特征选择方法，选择患者特征的最佳子集，降低假阴性率。结合先进的深度学习技术，Maxwell等[30]开发了一种新的多标签分类方法，用于预测慢性病。为了以便从电子健康记录中预测诊断结果(EHR)， Zhang等人[45]基于EHR数据提出了一种用于多标签分类的卷积残差模型，并利用卷积神经网络将明文编码为固定长度的句子嵌入向量。随后，在整片乳腺组织病理学图像中，Mercan等人[31]基于四种不同的多实例多标签学习算法预测了诊断类别。为了有效地利用不断积累的健康数据，Huang等[20]提出了一个临床决策支持框架，通过基于ML-kNN的改进算法，可以集成来自不同来源的异构健康数据。以上均为明文上的医学多标签分类方案，操作过程不加密，这些方案很容易泄漏医疗用户或训练集的医疗数据，这些数据可能与敏感信息一起泄露。

保护隐私医学确诊之前。为了实现在线医学预诊断，医疗用户首先需要提交自己敏感的索引向量。考虑到医疗使用者的隐私问题，最近提出了许多方案。基于完全同态加密，Bos等[3]提出了一种工作实现，借助云对加密的健康信息提供隐私保护预诊断服务。在他们的设置中，医疗用户的数据也可以通过使用来基于格的同态密码系统来实现数据隐私，但是他们的方案中都有这样一个缺点：诊断模型的保密性被忽略了。这意味着任何人都可以获得服务提供商的私有财产，因此Bos等人的方案的安全性设置很弱。为了解决这个问题，Bos等[4]基于Paillier构建了三个主要的分类协议保护从医疗用户和服务提供商收集的数据的安全。随后，为了提高分类效率，Wu等[41]设计了一种新的高效且保护隐私的不经意传输协议。Jia等[21]利用不经意传输传输协议和多元多项式的无关评估，实现了一种不需要耗费时间的同态加密，实现了一种保护隐私的SVM分类器。

此外，Zhu等[47]利用轻量级多方随机掩蔽和多项式聚合两种技术，设计了基于非线性核支持向量机的医学初级诊断框架。最近,Wang et al.[39]提出了一种高效的用于外包计算的隐私保护传感器数据监测和在线诊断系统，可以在不使用代理再加密的情况下高效实现移动医疗保健监测网络的大部分特性。Zhang等人[43]提出了一种疾病预测系统称为PPDP, PPDP利用随机矩阵构建新的医疗数据加密、疾病学习和疾病预测算法。Guo等人[16]利用logistic回归实现了保护隐私的预诊断，可在医学检查中广泛应用。

现有的隐私保护医学预诊断方案都是在单标签数据集上实验的，而我们提出的方案将考虑多标签实例。

不同于上述所有作品，CREDO基于k-means聚类和ML-kNN分类，适用于多标签医学实例，通过引入另一种交互聚类，实现更高效的预诊断服务。此外，CREDO针对隐私问题，对MU和SP的敏感信息进行保护。CREDO可以很容易地在智能手机和电脑上实现，因为它的效率高，计算开销低。

总结

在本文中提出了一种高效且保护隐私的基于ML-kNN的疾病预诊断方案，命名为CREDO。使用CREDO，可以保护医疗用户健康信息的隐私和诊断前模型数据的机密性，且计算开销低。对于已注册的MU的查询请求，MU与SP将进行两次交互，第一次交互用于预诊断，第二次交互用于最终结果。两者都直接在SP加密查询向量上操作而不获取原始数据，导航和预诊断的结果也只能由MU解密并且诊断前诊断结果的准确性也是取决于MU的选择。因此，MU可以获得在线高效的预诊断服务。详细的安全分析表明了该算法的安全强度和隐私保护能力，并进行了大量的实验验证了该算法的有效性和准确性。