本發(fā)明涉及基于向量同態(tài)加密的隱私保護K?NN分類方法，包括：A.接收查詢向量組和標(biāo)準(zhǔn)向量組；B.通過查詢向量組生成矩陣G，標(biāo)準(zhǔn)向量組使用密鑰S通過向量同態(tài)加密生成密文組和新密鑰GS；C.對新密鑰GS進行密鑰轉(zhuǎn)換為轉(zhuǎn)換密鑰S'，得到此時的轉(zhuǎn)換矩陣M和轉(zhuǎn)換密文組；D.使用轉(zhuǎn)換密鑰S'對轉(zhuǎn)換密文組解密，得到解密向量組；E.根據(jù)K個最小值的解密向量的分量為對應(yīng)的各查詢向量附上分類標(biāo)簽。本發(fā)明能夠良好的對用戶隱私數(shù)據(jù)保護，并且在隱私數(shù)據(jù)受到保護的情況下，通過K?NN算法對用戶的查詢向量進行高效、準(zhǔn)確的分類，提高了對向量類型判斷的效率，擴大了向量類型判斷的應(yīng)用范圍。

技術(shù)領(lǐng)域

本發(fā)明涉及K-NN算法在隱私保護下的向量分類方法，具體的講是基于向量同態(tài)加密的隱私保護K-NN分類方法。

背景技術(shù)

K臨近算法(K-NN)廣泛應(yīng)用于模式識別中，在數(shù)據(jù)分類中也有良好的表現(xiàn)。在大數(shù)據(jù)時代，復(fù)雜的計算往往外包給第三方云。然而在這個過程中，外包的數(shù)據(jù)可能包含敏用戶的一些敏感的數(shù)據(jù)，直接將用戶的信息外包給第三方云很可能導(dǎo)致用戶的一些隱私信息泄露出去，給用戶造成損失。一種直接的解決方式就是將數(shù)據(jù)加密之后再上傳到云端，但是這也給K-NN算法的效率帶來一些新的挑戰(zhàn)。同態(tài)加密技術(shù)可以在密文下進行操作，而解密之后的結(jié)果是正確的。于是可以將數(shù)據(jù)通過同態(tài)加密技術(shù)加密之后再在密文下運行K-NN方法。傳統(tǒng)的加密方案主要針對整數(shù)進行加密，對于向量的整體操作效率不高，出于效率方面的考慮可以使用向量的同態(tài)加密技術(shù)來加密數(shù)據(jù)，這樣可以大大提高運行效率。

K-NN方法是以特征向量x為中心的一個鄰域里，固定落入鄰域中的樣本個數(shù)K(n)。通常采用如下方式實現(xiàn)：在一個合適的距離尺度下(常用的歐氏(Euclidean)距離)，逐漸地增大包圍x點的區(qū)域的體積，直到有K(n)個樣本點落入該區(qū)域中。在這過程中需要進行概率密度估計，其密度估計形式為：其中，n為樣本個數(shù)，V(n)為該區(qū)域的體積。如果x點周圍的樣本點個數(shù)較少，那么相應(yīng)的區(qū)域就會變得很大，即V(n)的值很大，的值變得很小。相反，如果x點周圍的樣本點個數(shù)較多，那么相應(yīng)的區(qū)域就會變得較小，即V(n)的值較小，的值變得很大。并且K(n)也會隨n的增加而增加。由于K近鄰法則進行概率估計密度時，存在兩個缺點，一是估計密度的積分必須擴散到無窮大，二是計算上存在沉重的負(fù)擔(dān)。因此，一些研究學(xué)者直接用K-NN算法進行分類，分類的原則是：在一定的距離尺度下，考慮待識別樣本x周圍的K(n)個最近鄰樣本，并將x歸入到K(n)個最近鄰中某一類樣本最多的那個類別中去。算法步驟：

(1)對一個待分類的數(shù)據(jù)對象y，計算它與訓(xùn)練集R中的每個數(shù)據(jù)對象的距離；

(2)找出待分?jǐn)?shù)據(jù)對象y與訓(xùn)練集R中的數(shù)據(jù)對象距離最近的k個；

(3)依次統(tǒng)計出這k個數(shù)據(jù)對象的所屬類別，找出包含最多個數(shù)的類；

(4)將待分?jǐn)?shù)據(jù)y劃分到此類中；

(5)重復(fù)以上步驟，直到所有待分?jǐn)?shù)據(jù)分類結(jié)束；

K-NN算法不僅可以用于分類，還可以用于回歸。通過找出一個樣本的K個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。

發(fā)明內(nèi)容

本發(fā)明提供的基于向量同態(tài)加密的隱私保護K-NN分類方法，可在對用戶隱私數(shù)據(jù)保護的情況下，通過K-NN算法對用戶的查詢向量進行高效、準(zhǔn)確的分類。

本發(fā)明基于向量同態(tài)加密的隱私保護K-NN分類方法，步驟包括：

A.接收查詢向量組(x₁，x₂，…x_n)和標(biāo)準(zhǔn)向量組(p₁，p₂，…p_m)，其中標(biāo)準(zhǔn)向量組(p₁，p₂，…p_m)對應(yīng)有標(biāo)準(zhǔn)分類標(biāo)簽(t₁，t₂，…t_m)；