基于區(qū)塊鏈的多方隱私保護(hù)k-means聚類方案

趙 樂(lè)，張 恩*，秦磊勇，李功麗

（1.河南師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南 新鄉(xiāng) 453007；2.智慧商務(wù)與物聯(lián)網(wǎng)技術(shù)河南省工程實(shí)驗(yàn)室（河南師范大學(xué)），河南 新鄉(xiāng) 453007）

0 引言

機(jī)器學(xué)習(xí)［1-2］的快速發(fā)展為解決各種領(lǐng)域的諸多問(wèn)題取得了重大突破，例如神經(jīng)科學(xué)、疾病預(yù)測(cè)、計(jì)算機(jī)視覺(jué)、語(yǔ)言處理、健康與互聯(lián)網(wǎng)等方面。機(jī)器學(xué)習(xí)的發(fā)展離不開對(duì)大量數(shù)據(jù)的訓(xùn)練，k-means 聚類算法作為機(jī)器學(xué)習(xí)的一種重要算法，可以從大量未知數(shù)據(jù)中訓(xùn)練出具有潛在價(jià)值的知識(shí)，為問(wèn)題（如，物品傳輸優(yōu)化、文檔分類器、客戶分類等）的解決尋找出更好的方法。

多個(gè)參與方聯(lián)合進(jìn)行k-means 聚類訓(xùn)練時(shí)，較為簡(jiǎn)單的一種方法是各個(gè)用戶將數(shù)據(jù)上傳到中央服務(wù)器，再經(jīng)過(guò)不斷迭代獲得最優(yōu)聚類中心，然而將數(shù)據(jù)從多個(gè)用戶發(fā)送到中央服務(wù)器，不僅會(huì)導(dǎo)致大量的通信開銷，同時(shí)也會(huì)帶來(lái)數(shù)據(jù)的隱私及安全問(wèn)題。為避免隱私泄露，已經(jīng)有研究人員對(duì)k-means 聚類的隱私保護(hù)問(wèn)題進(jìn)行了研究，目前主要有兩種典型的隱私保護(hù)方法：一種是基于安全多方計(jì)算的隱私保護(hù)k-means 聚類方法［3-8］，為保護(hù)各個(gè)用戶隱私，安全多方計(jì)算［9-10］通常使用不經(jīng)意傳輸、混淆電路、同態(tài)加密等密碼學(xué)技術(shù)實(shí)現(xiàn)隱私保護(hù)，這種方式雖然不會(huì)泄露用戶在聚類過(guò)程中的隱私信息，但是參與方需要承擔(dān)較高的計(jì)算和通信成本，最終聚類結(jié)果也有受到推理攻擊的風(fēng)險(xiǎn)。另一種是基于差分隱私的隱私保護(hù)k-means 聚類方法［11-26］，差分隱私可有效地抵抗差分攻擊，但中心化差分隱私大都將一個(gè)可信第三方作為數(shù)據(jù)收集者，在對(duì)數(shù)據(jù)進(jìn)行收集之后進(jìn)行k-means 聚類，對(duì)迭代過(guò)程中產(chǎn)生的數(shù)據(jù)以及聚類結(jié)果添加噪聲來(lái)實(shí)現(xiàn)數(shù)據(jù)的隱私保護(hù)。而可信第三方在受到黑客攻擊會(huì)存在數(shù)據(jù)被惡意篡改的情況，并且實(shí)際生活中，這種可信第三方往往不容易找到，因此存在用戶誠(chéng)實(shí)提供數(shù)據(jù)而得到篡改聚類結(jié)果的問(wèn)題?；诒镜鼗罘蛛[私的隱私保護(hù)k-means 聚類，雖然各個(gè)用戶在本地對(duì)數(shù)據(jù)進(jìn)行隱私保護(hù)，不可信第三方只能對(duì)數(shù)據(jù)進(jìn)行分析，而不能收集其敏感信息；但是，存在不可信第三方為了節(jié)約開銷不進(jìn)行k-means 聚類，而直接返回錯(cuò)誤聚類結(jié)果的問(wèn)題，造成各個(gè)用戶提供數(shù)據(jù)而得到錯(cuò)誤聚類結(jié)果。

為解決上述問(wèn)題，本文提出了一種基于區(qū)塊鏈的多方隱私保護(hù)k-means 聚類方案（Multi-party Privacy Protectionk-means Clustering Scheme based on Blockchain，M-PPkCS/B），設(shè)計(jì)了一種新的聚類中心初始化方法，使區(qū)塊鏈與用戶交互完成初始聚類中心的選擇，用戶通過(guò)多次進(jìn)行數(shù)據(jù)上鏈和鏈上數(shù)據(jù)下載操作，保證每一個(gè)初始聚類中心生成過(guò)程的公開透明性，以及各個(gè)用戶獲取初始聚類中心的公平性，且去除了初始聚類中心選擇的隨機(jī)性，提高聚類迭代效率；結(jié)合區(qū)塊鏈及智能合約進(jìn)行聚類中心更新，實(shí)現(xiàn)多方在保護(hù)本地隱私數(shù)據(jù)的情況下，保證各方得到正確的聚類結(jié)果。

本文主要工作如下：

1）設(shè)計(jì)一種多方k-means 聚類中心初始化算法（Multipartyk-means Clustering Center Initialization Algorithm，M-kCCIA）。各個(gè)用戶先在本地進(jìn)行一輪Lloyd 算法產(chǎn)生k個(gè)聚類中心，在m個(gè)用戶中進(jìn)行k次隨機(jī)選擇，每次選出一個(gè)用戶生成初始聚類中心；第一次被選擇的用戶選擇k個(gè)聚類中相似度最高聚類對(duì)應(yīng)的聚類中心，用戶對(duì)其進(jìn)行隱私保護(hù)并上傳至區(qū)塊鏈；之后選擇的每個(gè)用戶從區(qū)塊鏈上下載已有聚類中心，并進(jìn)行校正，求其k個(gè)聚類中心和校正后聚類中心的歐幾里得平方距離和，選出最大值對(duì)應(yīng)的聚類中心作為初始化聚類中心，用戶同樣對(duì)其進(jìn)行隱私保護(hù)并上傳至區(qū)塊鏈。與隨機(jī)化初始聚類中心算法RS（Random Selection）算法［3］相比，此初始化方法可以去除聚類中心選擇的隨機(jī)性，有效提高算法的迭代效率。

2）利用區(qū)塊鏈公開透明、不可篡改的特性，將區(qū)塊鏈與本地化差分隱私技術(shù)結(jié)合，提出一種基于區(qū)塊鏈的隱私保護(hù)k-means 聚類算 法（Blockchain-based Privacy Protectionk-means Clustering Algorithm，Bc-PPkCA），并構(gòu)建聚類中心更新智能合約，各個(gè)用戶把隱私保護(hù)后的各類屬性值和與個(gè)數(shù)和上傳至區(qū)塊鏈后，區(qū)塊鏈才會(huì)根據(jù)智能合約進(jìn)行聚類中心更新，區(qū)塊鏈上的數(shù)據(jù)具有公開透明性，保證了每個(gè)用戶可以正確地獲得迭代過(guò)程以及最終的聚類中心，解決中心化差分隱私保護(hù)k-means 聚類方案中可信服務(wù)器遭受攻擊會(huì)返回篡改聚類結(jié)果，以及本地化差分隱私保護(hù)k-means 聚類方案不可信服務(wù)器為節(jié)約開銷返回錯(cuò)誤聚類結(jié)果的問(wèn)題。

3）在兩個(gè)數(shù)據(jù)集上對(duì)所提兩個(gè)算法進(jìn)行了實(shí)驗(yàn)。結(jié)果表明：本文提出的M-kCCIA 比傳統(tǒng)隨機(jī)選擇k個(gè)數(shù)據(jù)作為初始化聚類中心的迭代次數(shù)少，M-kCCIA 的平均迭代次數(shù)與隨機(jī)生成初始聚類中心的平均迭代次數(shù)相比，在兩個(gè)數(shù)據(jù)集上的平均迭代次數(shù)分別減少了5.68 次和2.75 次。其次Bc-PPkCA 在兩個(gè)數(shù)據(jù)集的準(zhǔn)確率分別能夠達(dá)到97.53%和96.19%。

1 相關(guān)工作

Dwork 等［13］于2006 年提出了差分隱私定義，用添加拉普拉斯噪聲的方法研究隱私保護(hù)統(tǒng)計(jì)數(shù)據(jù)庫(kù)問(wèn)題，該方法按照靈敏度進(jìn)行縮放。由于不同的問(wèn)題需要用不同的機(jī)制來(lái)進(jìn)行差分隱私保護(hù)，McSherry 等［14］研究了數(shù)字拍賣與屬性拍賣中收益最優(yōu)化問(wèn)題，將差分隱私與機(jī)制設(shè)計(jì)結(jié)合，引入一個(gè)新的差分隱私保護(hù)機(jī)制——指數(shù)機(jī)制，該機(jī)制可以用來(lái)處理輸出結(jié)果是非數(shù)值型的查詢。

Blum 等［18］設(shè)計(jì)了一個(gè)可用于交互式查詢的亞線性查詢（Sub-Linear Queries，SuLQ）數(shù)據(jù)庫(kù)模型，用戶可以發(fā)出查詢并獲得響應(yīng)，對(duì)獲得的響應(yīng)添加拉普拉斯噪聲，首先將差分隱私用于k-means 聚類隱私保護(hù)，將SuLQ 框架應(yīng)用于k-means 聚類算法，通過(guò)在聚類更新的每次迭代中添加噪聲達(dá)到隱私保護(hù)的目的。Nissim 等［19］提出了一種抽樣聚合框架，該框架在不需要顯式計(jì)算平滑靈敏度的情況下同樣可用。Dwork 等［20］的方案是在每次迭代中加入拉普拉斯噪聲，按照指數(shù)遞減的方式分配隱私預(yù)算，在事先不知道迭代次數(shù)的情況下考慮運(yùn)行k-means 聚類的可能性。Su 等［21］對(duì)具有差分隱私的Lloyd 算法（Lloyd algorithm with Differential Privacy，DPLloyd）進(jìn)行了改進(jìn)，并在非交互式方法下提出了一種基于擴(kuò)展統(tǒng)一網(wǎng)格方法的k-means 聚類方案（the EUGbasedk-Means clustering scheme，EUGkM），并將DPLloyd 的改進(jìn)方案同新的k-means 聚類算法有效結(jié)合實(shí)現(xiàn)隱私保護(hù)的k-means 聚類。Feldman 等［22］提出了一種既滿足差分隱私又具有近似誤差性質(zhì)的隱私保護(hù)k-means 聚類算法，其中算法的近似誤差與數(shù)據(jù)的維度呈亞線性關(guān)系。Lu 等［23］設(shè)計(jì)了一種新的迭代算法，該算法在迭代過(guò)程中控制質(zhì)心運(yùn)動(dòng)的方向，再在選定區(qū)域中加入差分隱私噪聲，來(lái)解決交互式差分隱私聚類算法存在不收斂的問(wèn)題。Ni 等［24］提出了基于聚類合并的差分隱私k-means 聚類算法（Differentially Private K-means Clustering algorithm based on Cluster Merging，DP-KCCM），該算法首先生成n×k個(gè)初始聚類中心，之后每次迭代加入自適應(yīng)噪聲，將最終得到的n×k個(gè)聚類中心合并成k個(gè)，提高了聚類效用。Zhang 等［25］提出了中心化差分隱私與安全多方計(jì)算結(jié)合的k-means 聚類算法，該算法利用雙云服務(wù)器為聚類的迭代過(guò)程中的份額添加噪聲，同時(shí)實(shí)現(xiàn)了聚類迭代過(guò)程中以及聚類結(jié)果的隱私保護(hù)。然而，以上中心化差分隱私保護(hù)k-means 聚類方案均存在可信服務(wù)器被篡改，并返回錯(cuò)誤聚類結(jié)果的問(wèn)題。

Xia 等［26］提出本地化差分隱私保護(hù)k-means 聚類機(jī)制，該機(jī)制中用戶先在本地?cái)_動(dòng)數(shù)據(jù)，再對(duì)數(shù)據(jù)進(jìn)行k-means 聚類，該機(jī)制可以采用不可信服務(wù)器進(jìn)行聚類中心更新，多個(gè)用戶合作獲得有質(zhì)量的聚類結(jié)果。而上述本地化差分隱私保護(hù)k-means 聚類方案存在不可信服務(wù)器為節(jié)約計(jì)算開銷而返回錯(cuò)誤聚類結(jié)果的問(wèn)題，聚類結(jié)果的正確性無(wú)法得到有效保證。此外，現(xiàn)有隱私保護(hù)k-means 聚類方案的聚類中心初始化大多為隨機(jī)選擇，聚類的迭代效率較低。針對(duì)此類問(wèn)題，本文提出一種基于區(qū)塊鏈的多方協(xié)作k-means 聚類隱私保護(hù)方案，方案設(shè)計(jì)了一種新的聚類中心初始化算法，使得多個(gè)用戶聯(lián)合選擇k個(gè)聚類中心，能夠有效減少聚類迭代次數(shù)；并且設(shè)計(jì)了一個(gè)基于區(qū)塊鏈的隱私保護(hù)k-means 聚類算法，使數(shù)據(jù)隱私不被泄露的同時(shí)在區(qū)塊鏈上完成聚類中心的更新，確保各個(gè)用戶得到正確的聚類結(jié)果。

2 基礎(chǔ)知識(shí)

2.1 k-means聚類

k-means 聚類［27］是一種基于距離的聚類算法，具有較高的計(jì)算效率，是聚類算法當(dāng)中最常用的一種算法。通過(guò)k-means 聚類可將數(shù)據(jù)劃分為k個(gè)聚類，相同聚類當(dāng)中的數(shù)據(jù)保持較高的相似度，而不同聚類的數(shù)據(jù)有著較小的相似度。基于歐幾里得距離的k-means 聚類算法包括以下三部分：

1）初始化k個(gè)聚類中心：c1，c2，…，ck。

2）計(jì)算數(shù)據(jù)集中每個(gè)數(shù)據(jù)與各個(gè)聚類中心之間的歐幾里得距離，比較出每個(gè)數(shù)據(jù)歐幾里得距離最近的聚類中心，將數(shù)據(jù)歸為最近聚類中心所屬聚類。

3）根據(jù)上次聚類結(jié)果，計(jì)算各個(gè)聚類數(shù)據(jù)的屬性值和以及個(gè)數(shù)和，用屬性值和與個(gè)數(shù)和的商來(lái)更新聚類中心，得到k個(gè)新的聚類中心。判斷是否達(dá)到終止條件，若達(dá)到終止條件，則返回新產(chǎn)生的聚類中心；若未達(dá)到終止條件，則繼續(xù)執(zhí)行2）～3）。

2.2 差分隱私

近年來(lái)，差分隱私［28］越來(lái)越多地被應(yīng)用在隱私保護(hù)數(shù)據(jù)發(fā)布與數(shù)據(jù)挖掘等領(lǐng)域。與其他許多隱私保護(hù)方法相比，其建立在嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)定義上，可以根據(jù)參數(shù)來(lái)對(duì)隱私保護(hù)的水平進(jìn)行衡量，保證即使兩個(gè)數(shù)據(jù)集僅相差一個(gè)元素，對(duì)這兩個(gè)數(shù)據(jù)集進(jìn)行相同查詢，得到的查詢結(jié)果幾乎完全相同。基本定義［28］如下：

定義1若對(duì)于隨機(jī)算法A，RA是算法A所有輸出結(jié)果構(gòu)成的集合，SA是RA的任意子集SA?RA，如果對(duì)于任意兩個(gè)相鄰數(shù)據(jù)集D0、D1，算法A滿足式（1）則算法A滿足ε-差分隱私。

其中：ε是隱私預(yù)算。

差分隱私具有兩種組合屬性，如下：

性質(zhì)1 序列組合性：m個(gè)算法A1，A2，…，Am的隱私預(yù)算分別為ε1，ε2，…，εm，當(dāng)這m個(gè)算法對(duì)同一數(shù)據(jù)集D進(jìn)行計(jì)算 時(shí)，這些算 法構(gòu)成 新的組 合算法A(A1(D)，A2(D)，…，Am(D))滿足差分隱私。

性質(zhì)2 并行組合性：n個(gè)算法A1，A2，…，An的隱私預(yù)算分別為ε1，ε2，…，εn，對(duì)于n個(gè)不同的數(shù)據(jù)集D1，D2，…，Dn，這些算法構(gòu)成新的組合算法A(A1(D1)，A2(D2)，…，An(Dn))滿足(maxεi)-差分隱私。

2.3 本地化差分隱私

本地化差分隱私［29］不同于中心化差分隱私，中心化差分隱私需要可信第三方來(lái)收集數(shù)據(jù)，之后再對(duì)收集到的數(shù)據(jù)進(jìn)行隱私保護(hù)處理；而本地化差分隱私針對(duì)的是不可信第三方數(shù)據(jù)收集者，用戶首先在本地通過(guò)隨機(jī)響應(yīng)機(jī)制［30］對(duì)數(shù)據(jù)進(jìn)行擾動(dòng)，將經(jīng)過(guò)擾動(dòng)后的數(shù)據(jù)發(fā)送給數(shù)據(jù)收集者，之后數(shù)據(jù)收集者對(duì)其進(jìn)行統(tǒng)計(jì)分析，在統(tǒng)計(jì)分析的過(guò)程中不會(huì)泄露用戶的隱私信息。其基本定義如下：

定義2給定m個(gè)用戶，每個(gè)用戶各自對(duì)應(yīng)一條記錄。若隱私算法F，對(duì)于任意兩條輸入記錄m0和m1(m0，m1∈DF)，得到相同輸出結(jié)果m*(m*∈RF)，滿足式（2）則稱算法F滿足ε-本地化差分隱私，DF、RF分別為算法F定義域和值域。

其中：ε是隱私預(yù)算。

2.4 隨機(jī)響應(yīng)機(jī)制

隨機(jī)響應(yīng)機(jī)制［30］是目前本地化差分隱私保護(hù)的主流機(jī)制。為更清楚地介紹其原理，下文以一個(gè)具體情景為例進(jìn)行介紹：為了調(diào)查n個(gè)用戶中患有抑郁癥的人數(shù)，向每個(gè)用戶發(fā)起一個(gè)隱私問(wèn)題“你是不是患有抑郁癥？”，每個(gè)用戶對(duì)這個(gè)問(wèn)題進(jìn)行回答；但在回答之前會(huì)通過(guò)擲硬幣的方式來(lái)決定是否誠(chéng)實(shí)回答，其中這枚硬幣是一枚非均勻硬幣。如果硬幣正面朝上，則用戶會(huì)回答真實(shí)的答案；如果硬幣反面朝上，用戶則會(huì)回答與真實(shí)答案相反的答案。假設(shè)硬幣朝上的概率為p，反面朝上的概率為1 -p，當(dāng)隱私預(yù)算ε與概率p的關(guān)系滿足以下等式時(shí)，其滿足ε-本地化差分隱私。

2.5 區(qū)塊鏈

區(qū)塊鏈［31］現(xiàn)在已經(jīng)應(yīng)用于金融、版權(quán)保護(hù)等領(lǐng)域，是一種分布式共享賬本和數(shù)據(jù)庫(kù)，具有去中心化、不可篡改、公開透明等特點(diǎn)，不需要額外的第三方可信機(jī)構(gòu)［31］。區(qū)塊鏈網(wǎng)絡(luò)上所有節(jié)點(diǎn)都擁有整個(gè)網(wǎng)絡(luò)的交易數(shù)據(jù)和記錄，節(jié)點(diǎn)間交易均是公開透明的，有效地防止了合謀篡改的風(fēng)險(xiǎn)。區(qū)塊鏈還具有鏈上儲(chǔ)存記錄不可更改的特點(diǎn)，有效地保證了鏈上數(shù)據(jù)的安全性。從區(qū)塊鏈架構(gòu)設(shè)計(jì)上，可以將區(qū)塊鏈簡(jiǎn)單地分成三層：協(xié)議層、擴(kuò)展層以及應(yīng)用層。其中協(xié)議層負(fù)責(zé)搭建交易通道、制定節(jié)點(diǎn)獎(jiǎng)勵(lì)、構(gòu)建網(wǎng)絡(luò)環(huán)境等一系列工作，擴(kuò)展層可以讓區(qū)塊鏈更加實(shí)用，智能合約便是擴(kuò)展層的應(yīng)用開發(fā)，應(yīng)用層包含區(qū)塊鏈的典型應(yīng)用與案例，區(qū)塊鏈的架構(gòu)如圖1 所示。

圖1 區(qū)塊鏈的架構(gòu)Fig.1 Architecture of blockchain

智能合約［32］是一種運(yùn)行在區(qū)塊鏈上模塊化、可重用的自動(dòng)執(zhí)行腳本，一經(jīng)部署就可自我執(zhí)行、自我驗(yàn)證的計(jì)算機(jī)協(xié)議，總是按照之前定好的規(guī)則執(zhí)行操作，近些年區(qū)塊鏈的發(fā)展為智能合約提供了可靠的執(zhí)行環(huán)境。以太坊是區(qū)塊鏈基礎(chǔ)開發(fā)的平臺(tái)，它可以提供圖靈完備的智能合約系統(tǒng)，用戶可以通過(guò)以太坊根據(jù)自己的需求編寫智能合約，基于以太坊的智能合約是圖靈完備的。

3 本文方案

本文提出了一種基于區(qū)塊鏈的多方隱私保護(hù)k-means 聚類方案（M-PPkCS/B），各個(gè)用戶首先通過(guò)M-kCCIA 生成初始聚類中心，然后通過(guò)智能合約在區(qū)塊鏈上完成多用戶隱私保護(hù)k-means 聚類中心更新。本文使用的相關(guān)符號(hào)及其含義如表1 所示。

表1 符號(hào)及其含義Tab.1 Symbols and their meanings

3.1 M-kCCIA

聚類中心的初始化方法對(duì)聚類迭代效率至關(guān)重要，一個(gè)好的聚類初始化算法會(huì)提高聚類迭代效率，所以在不同條件下進(jìn)行聚類選用不同的初始化聚類中心方法尤為重要。本節(jié)提出一種適用于區(qū)塊鏈環(huán)境下多方聯(lián)合的隱私保護(hù)聚類中心初始化算法，此算法在保護(hù)各個(gè)用戶隱私數(shù)據(jù)的同時(shí)，保證聚類中心的隱私，用戶將生成的初始聚類中心上傳至區(qū)塊鏈，以區(qū)塊鏈的公開透明性，有效地防止惡意敵手的篡改。除此之外，在聚類中心的選擇上，被選擇生成初始聚類中心的用戶通過(guò)下載區(qū)塊鏈上已有聚類中心，選取同一聚類相似度高、不同聚類相似度低的聚類中心，提高聚類迭代效率。

算法1 中，m個(gè)用戶首先在本地均進(jìn)行一次Lloydk-means 聚類，各個(gè)用戶均產(chǎn)生k個(gè)聚類中心。然后從m個(gè)用戶中選出一個(gè)用戶，從被選擇用戶的k個(gè)聚類中心中選取出第一個(gè)初始聚類中心，選取規(guī)則為同一聚類中的數(shù)據(jù)到其聚類中心的歐幾里得平方距離和最小的聚類對(duì)應(yīng)的聚類中心。對(duì)選取過(guò)的聚類中心做標(biāo)記，下次再選到相同用戶時(shí)，此聚類中心不再參與選取，之后用戶在本地對(duì)被選擇的聚類中心進(jìn)行擾動(dòng)，并上傳至區(qū)塊鏈。m個(gè)用戶再次選出一個(gè)用戶，從該用戶未被標(biāo)記的聚類中心中選取出第二個(gè)初始聚類中心，選取規(guī)則為本地的各個(gè)聚類中心中與區(qū)塊鏈上已有的聚類中心歐幾里得平方距離和最大值對(duì)應(yīng)的聚類中心。對(duì)于未選擇的k-2 個(gè)聚類中心均采用上述第二個(gè)選取規(guī)則進(jìn)行選擇，算法1 整體結(jié)構(gòu)如圖2 所示。

圖2 M-kCCIA整體結(jié)構(gòu)Fig.2 Overall structure of M-kCCIA

算法1 M-kCCIA。

M-kCCIA 中，為保護(hù)各個(gè)用戶的隱私數(shù)據(jù)，需要根據(jù)隨機(jī)響應(yīng)機(jī)制對(duì)各個(gè)用戶的隱私數(shù)據(jù)進(jìn)行隨機(jī)擾動(dòng)處理，處理方法是參考文獻(xiàn)［26］為M-kCCIA 設(shè)計(jì)的。各個(gè)隱私數(shù)據(jù)的處理方法Random1 如下：

則對(duì)應(yīng)的十進(jìn)制為：

3.2 Bc-PPkCA

為了實(shí)現(xiàn)各個(gè)用戶在提供了正確數(shù)據(jù)后，可以在保護(hù)本地隱私數(shù)據(jù)的同時(shí)得到正確聚類結(jié)果。本文設(shè)計(jì)一種基于區(qū)塊鏈的多方隱私保護(hù)k-means 聚類算法，在區(qū)塊鏈環(huán)境下多方聯(lián)合更新聚類中心，此算法在保護(hù)各個(gè)用戶隱私數(shù)據(jù)的情況下，利用本地化差分隱私保證了迭代過(guò)程中聚類中心的隱私，同時(shí)結(jié)合區(qū)塊鏈公開透明性以及智能合約誠(chéng)實(shí)執(zhí)行的特性，來(lái)保證聚類中心更新計(jì)算的正確性，以及每個(gè)用戶獲得新聚類中心的公平性，有效解決服務(wù)器與用戶合謀以及不可信服務(wù)器返回錯(cuò)誤聚類結(jié)果的問(wèn)題，整體結(jié)構(gòu)如圖3所示。

圖3 Bc-PPkCA整體結(jié)構(gòu)Fig.3 Overall structure of Bc-PPkCA

Bc-PPkCA 首先調(diào)用M-kCCIA 算法，生成初始化聚類中心，之后各個(gè)用戶從區(qū)塊鏈上下載初始聚類中心，再調(diào)用智能合約算法（算法2），讓各個(gè)用戶與區(qū)塊鏈聯(lián)合更新聚類中心，具體算法見算法3。

算法2 智能合約算法。

算法2 提前部署在以太坊上，各個(gè)用戶一旦上傳數(shù)據(jù)，算法2 便會(huì)按照定好的規(guī)則執(zhí)行操作，完成聚類中心更新，直至達(dá)到迭代終止條件。

算法3 Bc-PPkCA。

智能合約中對(duì)擾動(dòng)的屬性值和二進(jìn)制串，以及擾動(dòng)的個(gè)數(shù)和二進(jìn)制串進(jìn)行校正，用戶會(huì)將兩個(gè)二進(jìn)制串各個(gè)位對(duì)應(yīng)的擾動(dòng)概率發(fā)送給區(qū)塊鏈，智能合約會(huì)根據(jù)上傳的屬性值和個(gè)數(shù)來(lái)進(jìn)行校正，即用戶及區(qū)塊鏈均知道(0 ≤j≤l1-1)和fb，jb(0 ≤j≤l2-1)。

4 安全分析

本文提出的M-kCCIA 在滿足定理1 和定理2 時(shí)，是滿足ε1-本地化差分隱私的，證明過(guò)程分別見證明1、證明2。

根據(jù)性質(zhì)2 可知，本文提出Bc-PPkCA 在滿足定理1～定理4 時(shí)，是滿足max(ε1，εb，εa)-本地化差分隱私的。

基于區(qū)塊鏈的智能合約是由許多節(jié)點(diǎn)執(zhí)行的計(jì)算機(jī)程序，可以被跟蹤且不可改變，因此利用智能合約來(lái)約束每個(gè)用戶均上傳本地?cái)?shù)據(jù)后，才能開始進(jìn)行聚類中心的更新。區(qū)塊鏈技術(shù)不需要依賴額外的可信第三方機(jī)構(gòu)，其特點(diǎn)是防篡改并且公開透明，區(qū)塊鏈遵守少數(shù)服從多數(shù)的原則，只有當(dāng)網(wǎng)絡(luò)中至少51%的節(jié)點(diǎn)同意篡改數(shù)據(jù)，才可以對(duì)數(shù)據(jù)進(jìn)行篡改，但是付出的代價(jià)是巨大的。因此利用區(qū)塊鏈來(lái)進(jìn)行用戶聯(lián)合聚類中心的更新，保證了所有用戶一旦誠(chéng)實(shí)上傳數(shù)據(jù)，區(qū)塊鏈就會(huì)根據(jù)智能合約誠(chéng)實(shí)地執(zhí)行協(xié)議，直到達(dá)到終止條件，返回根據(jù)輸入計(jì)算的正確的聚類結(jié)果。

5 實(shí)驗(yàn)與結(jié)果分析

本章對(duì)本文提出的M-kCCIA 以及Bc-PPkCA 進(jìn)行了功能分析，將M-kCCIA 與文獻(xiàn)［6，25］的初始化聚類中心算法以及Bc-PPkCA 與文獻(xiàn)［4-5，8，24，26］這5 種隱私保護(hù)k-means 聚類算法分別進(jìn)行了功能比較。實(shí)驗(yàn)實(shí)現(xiàn)了基于區(qū)塊鏈的多方聯(lián)合隱私保護(hù)k-means 聚類系統(tǒng)。在聚類中心k取不同值的情況下，將本文提出的M-kCCIA 與隨機(jī)選擇初始化k-means 聚類算法進(jìn)行了迭代效率的比較。并將本文方案與明文聚類得到的結(jié)果進(jìn)行比較，從實(shí)驗(yàn)結(jié)果可以看出本文方案的準(zhǔn)確率與明文訓(xùn)練相差很小，具有較高實(shí)用性。

5.1 功能比較

本文所提出的M-kCCIA 與文獻(xiàn)［6，25］所提出的聚類中心初始化算法功能比較的結(jié)果如表2 所示。

表2 初始化算法的功能比較Tab.2 Function comparison of initialization algorithms

文獻(xiàn)［6］中是兩個(gè)用戶協(xié)作產(chǎn)生k個(gè)初始聚類中心，首先用戶1、用戶2 本地均進(jìn)行明文k-means 聚類，用戶1 將數(shù)據(jù)分為類，用戶2 將數(shù)據(jù)分為類，用戶1 將其個(gè)聚類中心秘密共享給用戶2，用戶2 將其個(gè)聚類中心秘密共享給用戶1。然而一旦兩個(gè)用戶之間秘密共享的份額在雙方不知情的情況下被敵手惡意篡改，則初始聚類中心的正確性無(wú)法得到保證，在后面的計(jì)算過(guò)程中，用戶無(wú)法正確更新聚類。

文獻(xiàn)［25］中是m個(gè)用戶協(xié)作產(chǎn)生k個(gè)初始聚類中心，當(dāng)m＜k時(shí)，每個(gè)用戶首先隨機(jī)選擇個(gè)數(shù)據(jù)點(diǎn)作為初始聚類中心，再隨機(jī)選擇k-×m個(gè)用戶，各自隨機(jī)選擇一個(gè)數(shù)據(jù)點(diǎn)作為初始聚類中心；當(dāng)m≥k時(shí)，隨機(jī)選擇k個(gè)用戶，每個(gè)用戶隨機(jī)選擇一個(gè)數(shù)據(jù)點(diǎn)作為初始聚類中心。初始聚類中心選擇之后，參與初始化的用戶Ui將產(chǎn)生的初始聚類中心{ai}(1 ≤i≤k)發(fā)送給云服務(wù)器1，將{ci-ai}(1 ≤i≤k)發(fā)送給云服務(wù)器2，兩個(gè)云服務(wù)器對(duì)拿到的數(shù)據(jù)添加Laplace 噪聲，并經(jīng)過(guò)混淆電路，得到k個(gè)加噪聲的初始聚類中心發(fā)送給各個(gè)用戶。然而上述算法必須保證兩個(gè)云服務(wù)器是可信的，一旦云服務(wù)器遭受攻擊，帶噪聲的初始聚類中心便會(huì)被篡改，之后聚類迭代產(chǎn)生的聚類結(jié)果也是毫無(wú)意義的。

M-kCCIA 優(yōu)化了初始聚類中心的選擇方法并與區(qū)塊鏈技術(shù)相結(jié)合，用戶聯(lián)合產(chǎn)生的每個(gè)初始聚類中心經(jīng)過(guò)本地化差分隱私保護(hù)之后，上傳至區(qū)塊鏈，利用區(qū)塊鏈公開透明的性質(zhì)，每個(gè)用戶均能從區(qū)塊鏈得到正確的初始聚類中心，MkCCIA 不僅能夠提高聚類的迭代效率，還能解決之前初始聚類中心算法中用戶傳送數(shù)據(jù)被敵手惡意篡改，以及第三方云服務(wù)器遭受攻擊而導(dǎo)致用戶無(wú)法獲取正確初始聚類中心的問(wèn)題。

此外將本文Bc-PPkCA 與文獻(xiàn)［4-5，8，24，26］中所提算法進(jìn)行功能比較，如表3 所示。文獻(xiàn)［4-5，8，24，26］中均是用戶與服務(wù)器結(jié)合來(lái)完成k-means 聚類中心的迭代更新過(guò)程。其中文獻(xiàn)［4］中是兩個(gè)用戶將加密的數(shù)據(jù)發(fā)送到服務(wù)器上，服務(wù)器來(lái)進(jìn)行聚類中心更新，此方案不能保證服務(wù)器在迭代更新過(guò)程中數(shù)據(jù)不被篡改，因此用戶得到聚類結(jié)果的正確性是無(wú)法保證的。文獻(xiàn)［5］中使用兩個(gè)服務(wù)器交互來(lái)完成對(duì)多個(gè)用戶數(shù)據(jù)的k-means 聚類，但是兩個(gè)服務(wù)器一旦合謀，便可得到用戶的聚類中心，此外服務(wù)器返回的結(jié)果一旦被惡意篡改，用戶便無(wú)法得到正確的聚類結(jié)果。文獻(xiàn)［8］中云服務(wù)器根據(jù)數(shù)據(jù)分析師發(fā)送的公鑰，來(lái)計(jì)算加密的屬性值和，之后將密文發(fā)送給數(shù)據(jù)分析師進(jìn)行解密，更新聚類中心，此方案雖然可以能夠保護(hù)聚類中心的隱私，但聚類中心的更新依賴于云服務(wù)器，一旦服務(wù)器遭受黑客攻擊，則聚類結(jié)果正確性無(wú)法保證。文獻(xiàn)［24］中將中心化差分隱私與聚合結(jié)合，提高數(shù)據(jù)可用性，但是中心化差分隱私需要可信第三方來(lái)收集數(shù)據(jù)，而這種可信第三方往往不容易被找到。文獻(xiàn)［26］中用本地化差分隱私來(lái)保護(hù)用戶的隱私數(shù)據(jù)，由于本地化差分隱私的性質(zhì)，此方案可以在不可信第三方上進(jìn)行聚類中心更新而不泄露用戶的隱私數(shù)據(jù)，但是在不可信第三方上進(jìn)行計(jì)算有太多的不確定性，計(jì)算結(jié)果的正確性更是無(wú)法保證。

表3 隱私保護(hù)k-means算法的功能比較Tab.3 Function comparison of privacy protection k-means algorithms

針對(duì)以上采用第三方服務(wù)器的方案均無(wú)法防止聚類結(jié)果被篡改，并且不可信第三方返回結(jié)果正確性無(wú)法保證的問(wèn)題，本文設(shè)計(jì)防篡改智能合約，保證用戶可以與區(qū)塊鏈結(jié)合來(lái)進(jìn)行聚類中心更新，解決之前服務(wù)器存在的篡改問(wèn)題，使區(qū)塊鏈按照用戶傳送的數(shù)據(jù)來(lái)正確進(jìn)行聚類中心計(jì)算，保證聚類結(jié)果的正確性并且保證用戶的隱私信息、迭代過(guò)程產(chǎn)生數(shù)據(jù)的隱私、聚類結(jié)果的隱私。

對(duì)于m個(gè)數(shù)據(jù)擁有者，第i個(gè)數(shù)據(jù)擁有者有ni個(gè)數(shù)據(jù)，每個(gè)數(shù)據(jù)都為d維，每個(gè)數(shù)據(jù)最終均轉(zhuǎn)換為l位的二進(jìn)制數(shù)據(jù)，文獻(xiàn)［26］中在更新聚類中心時(shí)的計(jì)算復(fù)雜度為O(l+mni)，而Bc-PPkCA 在更新聚類中心時(shí)的計(jì)算復(fù)雜度僅為O(l+m)。

此外本文對(duì)各個(gè)用戶分類結(jié)果的屬性值和以及個(gè)數(shù)和進(jìn)行本地化差分隱私保護(hù)，而文獻(xiàn)［26］中對(duì)每個(gè)特征均進(jìn)行擾動(dòng)，因此在相同隱私預(yù)算下，本文算法可用性會(huì)比文獻(xiàn)［26］算法高。

5.2 實(shí)驗(yàn)平臺(tái)與數(shù)據(jù)集

在配置如下的計(jì)算機(jī)上進(jìn)行了實(shí)驗(yàn)：操作系統(tǒng)是Windows 64 位，CPU 為AMD Ryzen 7 4800U 1.80 GHz，內(nèi)存為16.0 GB。利用Python 3.7 語(yǔ)言來(lái)實(shí)現(xiàn)用戶本地操作及本地化差分隱私保護(hù)，用Solidity 0.5.1 語(yǔ)言實(shí)現(xiàn)智能合約，并將其部署在以太坊。

為更好地測(cè)試方案的性能，本文在兩個(gè)樣本數(shù)差別較大的數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。其中：HTRU2 數(shù)據(jù)集描述了在高時(shí)間分辨率宇宙調(diào)查（南方）期間收集的脈沖星候選樣本；Abalone 數(shù)據(jù)集描述了鮑魚性別、長(zhǎng)度、高度等8 個(gè)屬性，預(yù)測(cè)鮑魚的年齡。兩個(gè)數(shù)據(jù)集的詳細(xì)情況如表4 所示，兩個(gè)數(shù)據(jù)集均可以從http：//archive.ics.uci.edu/ml/datasets 獲取。

表4 數(shù)據(jù)集介紹Tab.4 Introduction of datasets

5.3 結(jié)果分析

本節(jié)首先展示了在k取不同值的情況下，分別在HTRU2和Abalone 上運(yùn)行M-kCCIA 和隨機(jī)化初始聚類中心算法RS算法［3］的實(shí)驗(yàn)結(jié)果。由于初始聚類中心的選取每次結(jié)果不一定相同，迭代次數(shù)會(huì)隨著初始聚類中心的選取而發(fā)生改變，為更準(zhǔn)確地衡量?jī)煞N算法的迭代效率，在k取不同值時(shí)，分別對(duì)HTRU2 與Abalone 運(yùn)行兩種算法各10 次，得到兩個(gè)數(shù)據(jù)集分別在兩種算法下的迭代次數(shù)，統(tǒng)計(jì)在k值相同時(shí)，每個(gè)數(shù)據(jù)集在各個(gè)算法下的平均迭代次數(shù)，其比較結(jié)果如圖4所示。

圖4 初始化算法的迭代效率比較結(jié)果Fig.4 Comparison results of iterative efficiency of initialization algorithms

根據(jù)實(shí)驗(yàn)結(jié)果可知，k值在取3、4、5、6 時(shí)，HTRU2 和Abalone 運(yùn)行M-kCCIA 都比RS 算法所需迭代次數(shù)少。對(duì)于每個(gè)數(shù)據(jù)集，求其采用同一初始化方法、不同k值迭代次數(shù)的平均值?？傻玫紿TRU2 運(yùn)行M-kCCIA 的平均迭代次數(shù)，與RS 算法的平均迭代次數(shù)相比，減少了5.68 次；Abalone 運(yùn)行M-kCCIA 的平均迭代次數(shù)，與RS 算法的平均迭代次數(shù)相比，減少了2.75 次?？梢姅?shù)據(jù)集的大小不會(huì)對(duì)實(shí)驗(yàn)結(jié)果產(chǎn)生影響。

為衡量本文方案，對(duì)兩個(gè)數(shù)據(jù)集的聚類結(jié)果分別進(jìn)行準(zhǔn)確率分析。通過(guò)比較明文的聚類結(jié)果與M-PPkCS/B 的聚類結(jié)果，得到兩種結(jié)果中存在分類差異的數(shù)據(jù)點(diǎn)數(shù)量，從而判斷出本文方案聚類結(jié)果的準(zhǔn)確率。兩個(gè)數(shù)據(jù)集的明文聚類中心結(jié)果與M-PPkCS/B 的聚類中心結(jié)果比較如圖5 所示。

圖5 聚類中心比較結(jié)果Fig.5 Comparison results of cluster centers

為精確求出M-PPkCS/B 的準(zhǔn)確率，首先分別求出數(shù)據(jù)集運(yùn)行M-PPkCS/B 得到的聚類結(jié)果與明文聚類的結(jié)果，并為兩個(gè)結(jié)果中每個(gè)數(shù)據(jù)的聚類結(jié)果進(jìn)行標(biāo)記，將聚類結(jié)果為第b(1 ≤b≤k)類的數(shù)據(jù)標(biāo)簽記為b，統(tǒng)計(jì)出兩個(gè)聚類結(jié)果中數(shù)據(jù)相同而標(biāo)記不同的數(shù)據(jù)量，即存在聚類差異的數(shù)據(jù)量，進(jìn)而求出數(shù)據(jù)集運(yùn)行M-PPkCS/B 聚類結(jié)果的準(zhǔn)確率。

通過(guò)實(shí)驗(yàn)可以得到，HTRU2 的聚類結(jié)果準(zhǔn)確率能夠達(dá)到97.53%，其明文聚類結(jié)果和M-PPkCS/B 聚類結(jié)果分別如圖6～7 所示。Abalone 的聚類結(jié)果準(zhǔn)確率能夠達(dá)到96.19%，其明文聚類結(jié)果和M-PPkCS/B 聚類結(jié)果分別如圖8～9 所示。

圖6 HTRU2的明文聚類結(jié)果Fig.6 Plaintext clustering results of HTRU2

圖7 HTRU2的M-PPkCS/B聚類結(jié)果Fig.7 Clustering results of M-PPkCS/B of HTRU2

圖8 Abalone的明文聚類結(jié)果Fig.8 Plaintext clustering results of Abalone

通過(guò)上述實(shí)驗(yàn)可以看出，本文提出的基于區(qū)塊鏈的多方隱私保護(hù)k-means 聚類方案準(zhǔn)確率較高，數(shù)據(jù)可用性能夠得到有效保證。

圖9 Abalone的M-PPkCS/B聚類結(jié)果Fig.9 Clustering results of M-PPkCS/B of Abalone

6 結(jié)語(yǔ)

針對(duì)現(xiàn)存中心化差分隱私保護(hù)k-means 聚類方案中可信服務(wù)器會(huì)遭受攻擊返回篡改聚類結(jié)果，以及本地化差分隱私保護(hù)k-means 聚類方案中的服務(wù)器會(huì)為節(jié)約開銷返回錯(cuò)誤聚類結(jié)果這些問(wèn)題，設(shè)計(jì)了一種基于區(qū)塊鏈的多方隱私保護(hù)k-means 聚類方案（M-PPkCS/B）。首先，結(jié)合區(qū)塊鏈設(shè)計(jì)了一種多方k-means 聚類中心初始化算法（M-kCCIA），去除了初始化聚類中心選擇的隨機(jī)性，保證用戶聯(lián)合產(chǎn)生初始聚類中心產(chǎn)生的正確性，有效地提高了聚類迭代效率。其次，設(shè)計(jì)了一種基于區(qū)塊鏈的隱私保護(hù)k-means 聚類算法（Bc-PPkCA），利用區(qū)塊鏈公開透明且防篡改的特點(diǎn)，構(gòu)建了聚類中心更新算法的智能合約，實(shí)現(xiàn)了利用區(qū)塊鏈來(lái)正確更新多方聯(lián)合的聚類中心。M-PPkCS/B 利用本地化差分隱私對(duì)數(shù)據(jù)進(jìn)行隱私保護(hù)，用戶無(wú)需上傳自己的隱私數(shù)據(jù)，只需對(duì)要發(fā)送到區(qū)塊鏈的各類數(shù)據(jù)根據(jù)隨機(jī)響應(yīng)機(jī)制進(jìn)行擾動(dòng)，無(wú)需復(fù)雜的加密解密操作就可實(shí)現(xiàn)對(duì)初始聚類中心、迭代產(chǎn)生的數(shù)據(jù)以及聚類結(jié)果的隱私保護(hù)。下一步工作考慮加入獎(jiǎng)懲機(jī)制，更好地激勵(lì)用戶參與聚類，制定適合本文方案的激勵(lì)機(jī)制。