[發(fā)明專利]基于聚類匿名的隱私保護(hù)表數(shù)據(jù)共享方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201910752801.6
• 申請(qǐng)日: 2019-08-15
• 公開（公告）號(hào): CN110555316B
• 公開（公告）日: 2023-04-18
• 發(fā)明（設(shè)計(jì)）人: 劉麗蘋;樸春慧
• 申請(qǐng)（專利權(quán)）人: 石家莊鐵道大學(xué)
• 主分類號(hào): G06F21/62
• 分類號(hào): G06F21/62
• 代理公司: 石家莊輕拓知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 13128
• 代理人: 侯迎新

1.一種基于聚類匿名的隱私保護(hù)表數(shù)據(jù)共享方法，其特征在于：應(yīng)用于共享靜態(tài)數(shù)據(jù)表，步驟為：

Step?1、聚類處理：基于k-medios聚類的表數(shù)據(jù)記錄劃分，依據(jù)數(shù)據(jù)表中記錄間的距離，使用k-medios聚類算法對(duì)共享靜態(tài)數(shù)據(jù)表中的記錄進(jìn)行聚類，得到若干個(gè)簇；

Step?2、匿名處理：對(duì)經(jīng)過Step?1處理得到的每個(gè)簇分別進(jìn)行處理，首先將簇中的數(shù)據(jù)依據(jù)信息損失量進(jìn)行分割，然后對(duì)得到的每個(gè)簇進(jìn)行調(diào)整，使得每個(gè)簇均滿足k-匿名條件、且不存在敏感屬性值完全相等的情況，最后對(duì)其進(jìn)行泛化處理，從而生成匿名數(shù)據(jù)表；

Step?3、差分隱私加噪處理：對(duì)表數(shù)據(jù)中的敏感屬性值進(jìn)行差分隱私處理；

Step?4、比較驗(yàn)證：最后通過示例分析及與經(jīng)典k-匿名算法MDAV進(jìn)行比較，進(jìn)行方法的可用性以及隱私性驗(yàn)證；

步驟Step?1中，表數(shù)據(jù)記錄劃分的核心思想為：利用聚類技術(shù)將共享靜態(tài)數(shù)據(jù)表中n條記錄劃分為多個(gè)簇，使得相似度高的記錄劃分到一組；同時(shí)為了能夠滿足接下來的k-匿名需求，在聚類結(jié)束后需對(duì)不滿足匿名要求的簇進(jìn)行調(diào)整，因此，結(jié)合k-medios聚類算法，表數(shù)據(jù)記錄劃分的具體流程如下：

Step?11：歸一化處理，對(duì)數(shù)據(jù)表中的非敏感有序分類型屬性進(jìn)行量化，也就是量化為數(shù)值1,2,3,···,n，然后將該有序分類型屬性看做數(shù)值型屬性進(jìn)行處理，進(jìn)而對(duì)數(shù)據(jù)表中的所有非敏感屬性中的數(shù)值型屬性數(shù)據(jù)進(jìn)行歸一化處理，歸一化公式如下：

式中，x_i’為一個(gè)數(shù)值型屬性的歸一化數(shù)值，x_i為一個(gè)數(shù)值型屬性的原始數(shù)值，x_min為該屬性的最小值，x_max為該屬性的最大值；

Step?12：根據(jù)表數(shù)據(jù)記錄間的非敏感屬性的距離大小，利用k-medios聚類算法對(duì)表數(shù)據(jù)進(jìn)行聚類處理，將表數(shù)據(jù)記錄劃分為k₁個(gè)簇；

Step?13：根據(jù)k-匿名參數(shù)k₂對(duì)不滿足匿名要求的簇進(jìn)行簇記錄調(diào)整，若所劃分的簇中的數(shù)據(jù)記錄數(shù)目均大于k₂，則不進(jìn)行調(diào)整；若存在所得簇C_i中的數(shù)據(jù)記錄數(shù)小于k₂，則將距離簇C_i的中心點(diǎn)最近的記錄添加到簇C_i中，同時(shí)保證該記錄所在簇中的數(shù)據(jù)記錄仍大于k₂；

Step?14：重復(fù)步驟Step?3，直到每個(gè)簇中的記錄均大于等于k₂；

Step?15：將數(shù)據(jù)按照所屬簇不同分割為不同的子數(shù)據(jù)表T1,T2,···,Tk₁，從而得到k₁張子數(shù)據(jù)表；

Step?12中，在使用k-medios聚類算法對(duì)記錄進(jìn)行劃分時(shí)，由于數(shù)據(jù)表含有分類型屬性、數(shù)值型屬性兩種類型的屬性，在計(jì)算記錄間距離時(shí)需要采用不同的數(shù)據(jù)距離計(jì)算方法，且在進(jìn)行k-medios聚類算法時(shí)需要考慮聚類結(jié)果最優(yōu)的問題，即最佳劃分簇?cái)?shù)k₁的選擇過程為：

Step?121、數(shù)據(jù)表記錄間距離計(jì)算公式：

在計(jì)算數(shù)據(jù)表記錄間的距離時(shí)，由于在數(shù)據(jù)表中存在多種屬性，因此需要將不同的屬性分開計(jì)算，數(shù)值屬性距離計(jì)算公式如公式2：

dist(x_i,x_j)＝|x_i-x_j|

(公式2)

分類型屬性計(jì)算公式如公式3：

(公式3)

假設(shè)數(shù)據(jù)表中有m個(gè)數(shù)值型屬性，n個(gè)分類型屬性，因此，數(shù)據(jù)表中任意兩條記錄X_i、X_j的距離計(jì)算公式如公式4：

(公式4)

式中x_ip和x_jp分別為記錄X_i和記錄X_j的第p個(gè)數(shù)值型屬性值，x_iq和x_jq分別為記錄X_i和記錄X_j的第q個(gè)分類型屬性值；

Step?122、數(shù)據(jù)記錄劃分簇?cái)?shù)k₁的確定：

k-medios聚類算法的使用是為了使相似記錄劃分到一組，為匿名化處理做準(zhǔn)備，盡量減少匿名化過程帶來的信息損失，因此在確定聚類的簇?cái)?shù)目時(shí)，主要考慮簇內(nèi)的相似度問題，因此通過組內(nèi)平方誤差和SSE來確定數(shù)據(jù)記錄劃分簇?cái)?shù)k₁；而隨著k₁的增加，每個(gè)簇內(nèi)的數(shù)據(jù)記錄將逐漸減少，簇內(nèi)記錄間的距離應(yīng)越來越小，因此，SSE的值應(yīng)隨著k₁的增大而減??；故在通過SSE進(jìn)行k₁值的確定時(shí)，關(guān)注其變化情況，當(dāng)SSE隨著k₁的增加減少的相對(duì)緩慢時(shí)，認(rèn)為進(jìn)一步增大k₁聚類效果變化不大，則該k₁值為最佳聚類數(shù)目；若將各個(gè)k₁的值與相應(yīng)的SSE值表示在折線圖中，則拐點(diǎn)處對(duì)應(yīng)的k₁值即為最佳聚類數(shù)目；

Step?2中，經(jīng)過表數(shù)據(jù)記錄劃分處理得到的k₁張子數(shù)據(jù)表，然后依次處理每張子數(shù)據(jù)表，其核心思想是：對(duì)子數(shù)據(jù)表內(nèi)數(shù)據(jù)記錄進(jìn)行劃分，使得生成的每個(gè)簇中的記錄數(shù)目在[k₂,2k₂-1]之間，同時(shí)保證每個(gè)簇中的敏感屬性取值不唯一，因此，表數(shù)據(jù)匿名處理算法實(shí)現(xiàn)的具體流程如下：

Step?21：判斷數(shù)據(jù)集合中數(shù)據(jù)記錄數(shù)目是否大于2k₂-1，若大于2k₂-1，則執(zhí)行步驟Step22；

Step?22：在該數(shù)據(jù)集合內(nèi)選取兩條記錄r₁和r₂作為兩個(gè)初始簇，使得當(dāng)r₁和r₂組成一個(gè)簇時(shí)，在該簇內(nèi)的所有記錄兩兩組合中信息損失量最大，并執(zhí)行步驟Step?23；

Step?23：分別計(jì)算數(shù)據(jù)集合內(nèi)每條記錄劃分到兩個(gè)簇后的信息損失變化情況，并將該記錄劃分為使得信息損失量較小的簇中，調(diào)整數(shù)據(jù)記錄，使得每個(gè)簇中的數(shù)據(jù)記錄最少為k₂，并將生成的簇作為新生成的兩個(gè)數(shù)據(jù)集合返回步驟Step?21；

Step?24：當(dāng)所有數(shù)據(jù)集合中的數(shù)據(jù)記錄數(shù)目均在[k₂,2k₂-1]之間，依次循環(huán)判斷每個(gè)數(shù)據(jù)集合內(nèi)是否存在敏感屬性取值唯一的情況，若存在則執(zhí)行步驟Step25；

Step?25：選取與該數(shù)據(jù)集合Q內(nèi)敏感屬性值不同的數(shù)據(jù)記錄，同時(shí)保證若刪除該數(shù)據(jù)記錄，其所在數(shù)據(jù)集合中的數(shù)據(jù)記錄數(shù)目仍大于等于k₂、且敏感屬性值不唯一；

Step?26：計(jì)算若所選數(shù)據(jù)記錄劃分到相應(yīng)數(shù)據(jù)集合Q后的信息損失變化量，并將使得信息損失量較小的數(shù)據(jù)記錄劃分到數(shù)據(jù)集合Q中；

Step?27：得到記錄數(shù)目在[k₂,2k₂-1]之間、且不存在集合內(nèi)部敏感屬性取值唯一的情況的各個(gè)數(shù)據(jù)集合，并將各個(gè)集合進(jìn)行泛化處理，得到匿名數(shù)據(jù)表。