本发明涉及密态数据融合、数据外包计算与云存储等数据安全领域，尤其涉及一种新型的多用户外包k-means聚类方法。
背景技术：
1、在当前信息时代，云计算作为一种先进的计算模式，吸引了众多组织的使用。其吸引力源于其具有成本效益、灵活性和可扩展性的特点。通过云服务，组织可以避免昂贵的硬件设备和数据中心的资本支出，根据需求灵活利用计算和存储资源。通过这种方式，数据所有者可以减少本地计算资源，并获得高质量的服务。然而，随着云计算的普及，也带来了一定的安全挑战，如保护数据机密性和用户隐私。为了保护来自云以及未经授权用户的外包数据的机密性，一个传统的方式是用户在上传所持有的数据时对数据进行加密。通过这种方式，数据所有者可以有效地保护数据隐私。然而，在多用户协同训练一个聚类模型的环境中，每个用户的私人数据都不希望透露给其他不受信任的第三方。因此，传统的多用户外包k-means聚类方案引入了安全的同态加密适合于需要在密文下进行计算的场景。
2、传统的多用户外包k-means聚类方案通过计算每一个新的加密聚类中心，通过遍历每个距离得到最小距离的方式存在以下不足：1、新的加密聚类中心的每次计算需要将每个数据属性总和除以对于聚类总数，这可能会出现分数情况，不利于同态运算。2、随着聚类中心k的逐渐增加，在计算最小距离时需要串行的遍历比较每个值，这会导致运行时间的开销极大。由于上述的两个关键问题没有良好的解决，以至于传统的多用户外包k-means聚类效率低下，导致外包k-means聚类技术并不支持基于大部分加密系统的迭代。
3、于是，需要研究一种高效且通用的多用户外包k-means聚类方案，既能够高效率地对完成数据聚类的任务，还能够保证可以将里面使用的加密系统替换为更高效的加密系统。同时，能够保证聚类中心的激增，不会影响聚类中计算最小加密距离的效率。这两个方面是多用户外包k-means聚类的重点，对用户数据的安全融合有着重要意义。
技术实现思路
1、为了达到上述目的，本发明提供了一种新型的多用户外包k-means聚类方法。所述方法应用的系统包括第一云服务器、第二云服务器，以及多个用户端，用户端与第一云服务器、第二云服务器通信连接，第一云服务器和第二云服务器通信连接，第一云服务器和第二云服务器分别生成同态加密公钥和私钥对(pkcs1,skcs1)、(pkcs2,skcs2)，用户端能够生成公钥和私钥对(pkdoi,skdoi)，其中i∈[m]，m为用户端数量；所述方法包括如下步骤：
2、步骤一：各个用户端向第一云服务器发送加密数据集和加密噪声值,所有用户端发送的加密数据集成加密数据库d；
3、步骤二：第一云服务器解密后再加密噪声，并从所有加密数据集集成的加密数据库d中随机挑选k个的数据作为初始的聚类中心；每个聚类中心的数据数量初始化为1个并使用第二云服务器的加密公钥加密；所述k为预定数值；
4、步骤三：执行安全平方欧式距离协议，计算加密数据集中每条数据记录与每个聚类中心的平方欧氏距离，形成加密的距离矩阵d i s；
5、步骤四：执行安全加密距离比较协议，得到最小平方欧氏距离值的位置；
6、步骤五：执行安全最小距离下标矩阵协议，得到安全最小距离下标矩阵k；k矩阵为预先定义的矩阵，其行数和列数与d i s相同，各元素初始化赋值为0；
7、步骤六：执行安全加密新聚类大小协议，得到新的加密聚类大小向量；
8、步骤七：执行安全加密新聚类中心协议，得到新得出新的聚类中心；
9、步骤八：执行安全终止条件协议，确定是进行下一轮聚类的迭代还是结束迭代；
10、步骤九：执行安全聚类中心解密协议，计算出未缩放的最终聚类中心。
11、进一步的，执行安全平方欧式距离协议包括如下步骤：
12、第一步：第一云服务器使用同态运算去除加密数据库d的噪声；
13、第二步：对于i∈[n]，j∈[k],t∈[z],第一云服务器计算如下公式[[pdt]]＝([[dit]]*[[|cj|]]-[[λjt]])2
14、[[disij]]＝sum([[pdt]])
15、pdt为数据向量里的某个值与聚类中心向量的某个值的距离，dit表示加密数据库d中第i条数据的第t个向量值，|cj|为第j个聚类中心包含的数据数量，λjt表示第j个聚类中心的第t个向量值；disij为距离矩阵dis的元素，表示第i条数据第j个聚类中心各个分量之间距离值之和，disij为距离矩阵第i行第j列的元素。此处i∈[n]，n为总数据条数,z为向量的分量数量。
16、进一步的，执行安全加密距离比较协议包括如下步骤：
17、第一步：第一云服务器输入[[a]]、[[b]]、[[aind]]、[[bind]]、[[|ca|]]、[[|cb|]]并选择一个随机值r使用第二云服务器的公钥加密使用如下公式计算：
18、[[a']]＝[[a]]*[[|cb|2]]*[[r]]
19、[[b']]＝[[b]]*[[|ca|2]]*[[r]]
20、计算结果发送至第二云服务器；
21、其中，a、b表示加密数据库d中某行数据与任意两个聚类中心的距离值，aind表示a在d i s矩阵中的位置、bind表示b在d i s矩阵中的位置、|ca|表示表示距离值a所对应的聚类中心包含的数据数量；|cb|表示距离值b所对应的聚类中心包含的数据数量；
22、第二步：第二云服务器解密[[a']]、[[b']]，并判断a-b是否大于0,若大于0则令临时向量h＝0，否则h＝1，并使用pkcs2加密发给第一云服务器；
23、第三步:第一云服务器计算最小元组(min,minind,cmin)内的各个值，计算公式如下：
24、[[min]]＝[[a]]*[[h]]+[[b]]*([[1]]-[[h]])
25、[[minind]]＝[[aind]]*[[h]]+[[bind]]*([[1]]-[[h]])
26、[[cmin]]＝[[|ca|]]*[[h]]+[[|cb|]]*([[1]]-[[h]])
27、min表示a、b中最小值，minind为aind、bind位值中最小值，cmin表示|ca|、|cb|中最小值。
28、进一步的，安全最小距离下标矩阵协议的执行步骤为：
29、第一步：第一云服务器输入[[d i s]]、[[|c|]]，并利用行随机功能函数π1(*)随机化[[d i s]]的行，列随机功能函数π2(*)随机化[[d i s]]和[[|c|]]的列；
30、|c|为具有k个元素的一维数组，其内各元素表示每个聚类中心包含的数据数量，各元素初始化为1；
31、第二步：若聚类中心总数k为奇数则将第i行要比较的平方欧氏距离值分成s＝(k+1)/2对，否则分成s＝k/2对，并由第一云服务器和第二云服务器共同对各对进行迭代比较直到k＝1为止，比较过程执行安全加密距离比较协议；每次比较得到的值参与下次迭代；
32、第三步：第一云服务器将最后比较出来的[[minind]]发送给第二云服务器；
33、第四步：第二云服务器解密[[minind]]，并将k矩阵的对应位置的元素值标记为1。
34、进一步的，执行安全加密新聚类大小协议的步骤为：
35、第一步：第二云服务器对于j∈[k],i∈[n],设sj为矩阵k的第j列值的和，遍历矩阵k各列，各列值的和作为向量s对应列的元素，使用pkcs2加密向量s发送给第一云服务器；
36、第二步：第一云服务器进行逆随机排列还原矩阵s为原来的排列模式；
37、[[|c'|]]＝π2-1([[s]])
38、第三步：第一云服务器输出新的加密聚类大小向量|c'|。
39、进一步的，安全加密新聚类中心协议执行步骤为：
40、第一步：第一云服务器输入[[d]]、[[|c'|]],对于i∈[n]，t∈[z]并计算如下公式
41、[[d]]＝π1([[d]])
42、[[d]]＝π2([[d]])
43、[[dit]]＝[[dit]]+[[p]]
44、p为噪声，是使用第二云服务器的公钥加密的随机值；
45、第一云服务器发送随机化后的[[d]]给第二云服务器；
46、第二步：第二云服务器解密[[d]]，并对于j∈[k],t∈[z],根据矩阵k将属于第j个聚类中心的数据记录中的属性值都相加得到λ'j，然后使用第二云服务器的加密公钥pkcs2加密新的聚类中心λ'发送给第一云服务器；
47、第三步：第一云服务器对λ'进行逆随机化计算，并去除噪声p，计算公式
48、[[λ']]＝π2-1([[λ']])
49、[[λ'jt]]＝[[λ'jt]]-[[p]]*[[|c'j|]]。
50、进一步的，安全终止条件协议的执行步骤为：
51、第一步：第一云服务器按顺序计算如下公式
52、[[t]]＝sum([[λ'jt]]-[[λjt]])
53、[[t]]＝[[t]]*[[p]]
54、第一云服务器发送[[t]]给第二云服务器；
55、第二步：第二云服务器解密[[t]]，并进行判断；t≠0则表示新聚类中心和旧聚类中心存在不同属性值，则赋值[[λjt]]＝[[λ'jt]]使得新聚类中心覆盖掉旧聚类中心并且赋值[[|c|]]＝[[|c'|]]使得新的聚类中心数据总数覆盖旧的聚类中心数据总数，不执行步骤九，而是进入下一轮聚类的迭代(从步骤三开始执行)，t＝0则结束聚类的迭代。
56、进一步的，安全聚类中心解密协议的执行步骤为：
57、第一步：第一云服务器输入[[λ']]、[[|c'|]]并生成噪声δ、τ用pkcs2加密，计算如下公式
58、[[λ'jt]]＝[[λ'jt]]+[[δ]]
59、[[|c'j|]]＝[[|c'j|]]+[[τ]]
60、第一云服务器发送[[λ']]、[[|c'|]]给第二云服务器，对于i∈[m],使用pkdoi加密δ、τ并发送给对应公钥的用户端；
61、第二步：第二云服务器解密[[λ']]、[[|c'|]]，用pkdoi加密λ'、|c'|发送密文给对应公钥的用户；
62、第三步：pkdoi对应公钥的用户解密[[λ']]、[[|c'|]]、[[δ]]、[[τ]]并计算如下公式λ'jt＝λ'jt-δ
63、|c'j|＝|c'j|+τ
64、最终聚类中心μ计算为如下公式：
65、
66、μ'jt表示第j个聚类中心的第t个分量。
67、进一步的，步骤一中，各个用户端向第一云服务器发送加密数据集和加密噪声值具体方法为：i∈[m],用户端doi首先对明文数据集di添加噪声r i,之后将添加噪声后的数据集di'用第二云服务器的pkcs2进行加密，噪声值r i使用第一云服务器的pkcs1加密,并将加密数据集di”和加密噪声值r i'发送值第一云服务器。
68、进一步的，步骤二中，第一云服务器将加密噪声值r i'进行解密再使用第二云服务器的pkcs2对其进行加密。
69、本发明的有益效果为：
70、1.提出了一种改进的云端多用户外包k-means聚类方案，可以减少云服务器通信开销和聚类的迭代时间。
71、2.为了基于pa i l l i er的部分同态加密方案，设计了安全平方欧氏距离协议、加密距离比较协议、最小值下标矩阵协议、新加密聚类大小协议、新加密聚类中心协议、安全终止条件协议和安全聚类中心解ss密协议，实现多用户协同聚类模型并保护隐私。
72、3.基于一组协议，设计了一个通用多用户隐私保护外包k-均值聚类方案(gmppoc)，为了保护多用户的隐私。在该发明中，数据拥有者无需一直保持在线即可以顺利获得聚类结果。4.云服务器双方之间的通信，相较于其他方案数量大幅减少，降低了通信之间的成本。
73、5.提出了使用分而治之得出最小距离矩阵的计算方法，该方法相较于其他需要遍历比较的方案大幅度减少聚类时间；
1.一种多用户外包k-means聚类方法，所述方法应用的系统包括第一云服务器、第二云服务器，以及多个用户端，用户端与第一云服务器、第二云服务器通信连接，第一云服务器和第二云服务器通信连接，第一云服务器和第二云服务器分别生成同态加密公钥和私钥对(pkcs1,skcs1)、(pkcs2,skcs2)，用户端能够生成公钥和私钥对(pkdoi,skdoi)，其中i∈[m]，m为用户端数量；其特征在于，所述方法包括如下步骤：
2.如权利要求1所述的多用户外包k-means聚类方法，其特征在于，执行安全平方欧式距离协议包括如下步骤：
3.如权利要求2所述的多用户外包k-means聚类方法，其特征在于，执行安全加密距离比较协议包括如下步骤：
4.如权利要求3所述的多用户外包k-means聚类方法，其特征在于，安全最小距离下标矩阵协议的执行步骤为：
5.如权利要求4所述的多用户外包k-means聚类方法，其特征在于，执行安全加密新聚类大小协议的步骤为：
6.如权利要求5所述的多用户外包k-means聚类方法，其特征在于，安全加密新聚类中心协议执行步骤为：
7.如权利要求6所述的多用户外包k-means聚类方法，其特征在于，安全终止条件协议的执行步骤为：
8.如权利要求7所述的多用户外包k-means聚类方法，其特征在于，安全聚类中心解密协议的执行步骤为：
9.如权利要求1所述的多用户外包k-means聚类装置，其特征在于，步骤一中，各个用户端向第一云服务器发送加密数据集和加密噪声值具体方法为：用户端doi首先对明文数据集di添加噪声ri,之后将添加噪声后的数据集di'用第二云服务器的pkcs2进行加密，噪声值ri使用第一云服务器的pkcs1加密,并将加密数据集di”和加密噪声值ri'发送值第一云服务器。
10.如权利要求9所述的多用户外包k-means聚类系统，其特征在于，步骤二中，第一云服务器将加密噪声值ri'进行解密再使用第二云服务器的pkcs2对其进行加密。
