趙 樂，張 恩*，秦磊勇，李功麗

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

0 引言

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

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

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

本文主要工作如下：

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

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

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

1 相關(guān)工作

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

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

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

2 基礎(chǔ)知識

2.1 k-means聚類

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

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

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

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

2.2 差分隱私

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

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

其中：ε是隱私預算。

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

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

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

2.3 本地化差分隱私

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

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

其中：ε是隱私預算。

2.4 隨機響應機制

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

2.5 區(qū)塊鏈

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

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

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

3 本文方案

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

表1 符號及其含義Tab.1 Symbols and their meanings

3.1 M-kCCIA

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

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

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

算法1 M-kCCIA。

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

則對應的十進制為：

3.2 Bc-PPkCA

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

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

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

算法2 智能合約算法。

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

算法3 Bc-PPkCA。

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

4 安全分析

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

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

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

5 實驗與結(jié)果分析

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

5.1 功能比較

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

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

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

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

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

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

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

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

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

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

5.2 實驗平臺與數(shù)據(jù)集

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

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

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

5.3 結(jié)果分析

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

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

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

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

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

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

通過實驗可以得到，HTRU2 的聚類結(jié)果準確率能夠達到97.53%，其明文聚類結(jié)果和M-PPkCS/B 聚類結(jié)果分別如圖6～7 所示。Abalone 的聚類結(jié)果準確率能夠達到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

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

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

6 結(jié)語

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