栗維勛，馬 斌，王 琛，何紀成，高明慧，徐 劍

1(國網(wǎng)河北省電力有限公司，石家莊 050000)

2(南瑞集團有限公司(國網(wǎng)電力科學(xué)研究院)，南京 210061)

3(北京科東電力控制系統(tǒng)有限責(zé)任公司，北京 100192)

4(東北大學(xué) 軟件學(xué)院，沈陽 110169)

E-mail：1193328465@qq.com

1 引 言

聚類作為典型的數(shù)據(jù)分析與挖掘技術(shù)，在眾多領(lǐng)域發(fā)揮著重要作用[1-3].聚類屬于機器學(xué)習(xí)中的無監(jiān)督學(xué)習(xí)，目的是把數(shù)據(jù)點劃分成若干類，同一個類中的數(shù)據(jù)點有很大的相似性，而不同類的數(shù)據(jù)點有很大的相異性.聚類可以在大量數(shù)據(jù)中獲取有用的知識，找出數(shù)據(jù)之間的潛在關(guān)系，是智能推薦、信息檢索、圖像模式識別、網(wǎng)絡(luò)實時監(jiān)控和預(yù)警等領(lǐng)域中的常用技術(shù)手段[4-6].

隨著云計算、物聯(lián)網(wǎng)以及5G技術(shù)的飛速發(fā)展，催生大數(shù)據(jù)時代快速到來.但是，在實際應(yīng)用場景中，部分數(shù)據(jù)擁有者由于資源受限，需要將數(shù)據(jù)進行外包.因此，外包聚類服務(wù)也隨之產(chǎn)生，成為聚類方法發(fā)展的新趨勢[7-9].數(shù)據(jù)外包后，如何保障其隱私性是一個具有挑戰(zhàn)性的問題.外包的數(shù)據(jù)常常包括金融、生物醫(yī)學(xué)等個人敏感信息，一旦發(fā)生數(shù)據(jù)泄露問題，對個人或社會將產(chǎn)生嚴重的負面影響[10].針對上述問題，目前，通常的做法是對外包的數(shù)據(jù)進行加密處理.然而，傳統(tǒng)的聚類方法僅能對明文數(shù)據(jù)進行聚類，不支持密文數(shù)據(jù)的聚類.因此，研究密文數(shù)據(jù)上的聚類方法就變的重要而迫切.

在密文數(shù)據(jù)上實現(xiàn)聚類是當前隱私保護機器學(xué)習(xí)研究的熱點問題之一[11-13].目前，眾多學(xué)者采用同態(tài)加密來支持密文數(shù)據(jù)上的運算[13，14-17].Cheon等人[13]實現(xiàn)了密文上的均值漂移算法，將非多項式內(nèi)核替換為多項式內(nèi)核，以便可以在同態(tài)加密下高效的計算，降低了傳統(tǒng)均值漂移算法的超線性復(fù)雜度，在速度和準確性方面有了提升.Almutairi等人[14]利用同態(tài)加密技術(shù)設(shè)計了一種可更新距離矩陣，利用矩陣計算的性質(zhì)來對密文進行計算.Hyeong等人[15]提出了支持比較操作的安全協(xié)議，首先使用Paillier密碼系統(tǒng)對明文數(shù)據(jù)進行加密，然后將明文運算操作替換成密文安全協(xié)議.雖然使用Paillier算法可以保證語義安全性，但是計算消耗較高.Chen等人[16]設(shè)計了一種基于Paillier加密的智能電表數(shù)據(jù)聚合方案，保護用戶的隱私信息.該方案引入可信的第三方密鑰生成中心，為用戶生成合法的密鑰，用戶密鑰保存在服務(wù)器中用于驗證用戶的合法身份.Angela等人[17]則解決了密文運算中的除法問題，同態(tài)加密中不允許兩個密文數(shù)據(jù)直接相除，但可以用一個密文數(shù)據(jù)除以常數(shù)，這個常數(shù)代表數(shù)據(jù)總和，即使暴露也不會泄露關(guān)鍵信息.Xing等人[18]提出了一種基于同態(tài)加密的K-means聚類方案，該方案既不會泄露個人信息，也不會泄漏社區(qū)的特征數(shù)據(jù).在該方案中，聚類的每次迭代調(diào)用的隱私保護算法，可在不泄漏每個參與者標簽的情況下計算簇類中心.參與者無法獲知同一簇類中的其他參與者信息.通過安全性分析，即使存在共謀參與者，也不會泄露其余參與者的私人信息.Almutairi等人[19]考慮到現(xiàn)有方法都需要所有數(shù)據(jù)擁有者參與，參與的數(shù)據(jù)量過于龐大，客戶端計算能力不足，因此引入可信第三方，將計算外包給第三方，節(jié)約計算成本，同時保證相互之間的隱私性.

綜上所述，在密文聚類方面，學(xué)者們已經(jīng)提出了較多的研究方案.但是，仍存在如下問題：

1)多數(shù)密文上的聚類方案都是利用同態(tài)加密算法結(jié)合K-means算法實現(xiàn)，基于密度聚類的算法較少.而K-means算法存在需要預(yù)先輸入聚類簇數(shù)以及對初始聚類中心過于依賴等缺點，無法滿足某些場景的實際應(yīng)用需求，因此還需在密文上實現(xiàn)其他聚類算法.

2)已有方案很多采用同態(tài)加密算法，該算法僅能支持加法或者乘法運算，而全同態(tài)加密可同時支持密文下的加法和乘法運算，構(gòu)建的通信協(xié)議也更加簡單.

因此，本文利用全同態(tài)加密技術(shù)研究面向密文數(shù)據(jù)的密度聚類模型，并將密度聚類的典型代表OPTICS算法作為研究切入點.首先，設(shè)計了面向密文數(shù)據(jù)的OPTICS聚類模型(OPTICS-CMED)，對OPTICS-CMED的實體構(gòu)成和形式化定義進行了描述；設(shè)計了對應(yīng)于基本操作的通信協(xié)議，包括：距離計算協(xié)議和排序協(xié)議.基于上述通信協(xié)議，構(gòu)建OPTICS-CMED的聚類過程.對OPTICS-CMED的正確性、安全性進行了分析，結(jié)果表明該模型可以同時保證正確性和安全性.最后，利用標準實驗數(shù)據(jù)進行性能測試，結(jié)果表明該模型可以在保證聚類準確性的前提下實現(xiàn)密文數(shù)據(jù)聚類.

2 OPTICS概述

OPTICS是一種無需用戶提供特定密度閾值的密度聚類算法，是DBSCAN(Density-Based Spatial Clustering of Applications with Noise)的改進算法，其不明顯的產(chǎn)生類簇，而是通過對結(jié)果隊列中的樣本點進行排序，來表達數(shù)據(jù)的基于密度的聚類結(jié)構(gòu)[20].由于OPTICS算法輸出的是一個排好順序的樣本點隊列，稱為結(jié)果隊列，相較于DBSCAN，OPTICS算法對輸入的參數(shù)不敏感.

OPTICS算法的核心思想：對于簇Ci中任意對象p，在其ε鄰域Nε(p)中，至少存在MinPts-1個其他對象，其中ε代表歐氏距離半徑，MinPts表示使得對象p作為核心對象在它的ε鄰域中至少應(yīng)含有的對象數(shù)量.

OPTICS算法中，存在核心距離core-distance(cd)和可達距離reachability-distance(rd)兩個概念.

定義1.對象p的核心距離cdε，MinPts(p).設(shè)半徑參數(shù)為ε′，使得p的ε′鄰域剛好包含MinPts個對象，若p不是關(guān)于ε′和MinPts的核心對象，則p的核心距離沒有定義，如式(1)所示：

(1)

定義2.對象p到對象q的可達距離rdε，MinPts(p，q).是使p從q密度可達的最小半徑值，其中q必須是核心對象，并且p必須在q的領(lǐng)域內(nèi)，如式(2)所示：

rdε，MinPts(p，q)=

(2)

OPTICS聚類算法，最終將根據(jù)識別結(jié)果輸出數(shù)據(jù)集的簇排序，該排序給出了對數(shù)據(jù)結(jié)構(gòu)化和聚類的一般觀察.

3 模型構(gòu)建

3.1 模型描述

OPTICS-CMED包括兩方實體，即客戶(Client，C)和服務(wù)器(Server，S)，如圖1所示.

圖1 面向密文數(shù)據(jù)的OPTICS聚類模型Fig.1 OPTICS clustering model over encrypted data

在OPTICS-CMED模型中，聚類過程由S與C通過安全通信協(xié)議交互完成.C將加密的樣本數(shù)據(jù)集發(fā)送給S，S進行聚類，并生成種子隊列和結(jié)果隊列，其中結(jié)果隊列包含著表示聚類結(jié)構(gòu)的簇排序?qū)ο罅斜?，從結(jié)果隊列中可以得到聚類結(jié)果.整個過程在密文下進行，在計算樣本點與中心點的距離時不會泄露隱私，通過隱藏類簇中心來防止攻擊者推斷出用戶所屬的類簇分組.在圖1中虛線區(qū)域表示需要保護隱私的數(shù)據(jù)及模型，其中聚類模型僅能被S獲知，而明文聚類結(jié)果僅能被C獲知.

定義3是對OPTICS-CMED的描述.

定義3.密文數(shù)據(jù)的OPTICS聚類模型(OPTICS-CMED)可以由如下元組表示{C，S，Distance，getOrder}.

1)Distance(E(x)，E(y))：安全距離計算協(xié)議，將FHE加密的數(shù)據(jù)E(x)，E(y)作為參數(shù)輸入，得到加密向量的乘法平方結(jié)果，即歐幾里德距離結(jié)果，保存到數(shù)組中；

2)getOrder(E(rd0)，…，E(rdm-1))：排序協(xié)議，將FHE加密的可達距離數(shù)組rd作為參數(shù)輸入，完成密文下可達距離的排序.

3.2 通信協(xié)議

OPTICS-CMED的通信協(xié)議包括安全距離計算協(xié)議和排序協(xié)議.安全距離計算協(xié)議用于實現(xiàn)兩個加密的向量的歐氏距離計算；排序協(xié)議用于實現(xiàn)對多個加密數(shù)據(jù)進行從小到大排序.

3.2.1 安全距離計算協(xié)議

安全距離計算協(xié)議是利用FHE的加法同態(tài)和乘法同態(tài)性質(zhì)，計算由FHE加密的兩個向量的歐氏距離的平方，返回一個FHE加密的運算結(jié)果.在安全距離計算協(xié)議中，S的輸入是兩個加密的向量數(shù)據(jù)和用于加密的密鑰，距離計算僅由S即可完成.S獲得FHE加密的向量點乘結(jié)果用于后續(xù)計算核心距離和可達距離，同時保證數(shù)據(jù)的隱私.

協(xié)議1是安全距離計算協(xié)議的描述.

協(xié)議1.安全距離計算協(xié)議distance(E(x)，E(y))

S：E(x)=(E(x1)，…，E(xd))，E(y)=(E(y1)，…，E(yd))，pk；

S：E(s)

1.S：Ef(s)←Ef(0)

2.S：for1≤i≤d：

3.S：E(zi)←(E(xi)⊙E(yi))×(E(xi)⊙E(yi))

4.S：E(s)←E(s)⊕E(zi)

5.S：returnE(s)

3.2.2 排序協(xié)議

圖2 排序過程Fig.2 Process diagram of ordering

在排序過程中，找到數(shù)組中最小值，將它與數(shù)組的第1個元素交換位置；再在剩下的元素中找到最小值，與數(shù)組的第2個元素交換位置.循環(huán)下去，直到完成對整個數(shù)組的排序.而獲取最小值的方法：利用兩個元素的比較協(xié)議，對數(shù)組中的元素進行兩兩比較，找到數(shù)值較小的一方賦值給下標小的一方，放入另一個數(shù)組中；同時使下標較大的一方數(shù)值為0，直到所有比較完成.再對另一個數(shù)組中的元素進行兩兩比較，重復(fù)上述過程，最后得到一個最小值.

協(xié)議2是對排序協(xié)議的具體描述.

協(xié)議2.排序協(xié)議getOrder(E(rd[0])，…，E(rd[m-1]))

輸入S：E(rd[0])，…，E(rd[m-1])，公鑰pk；

輸入C：私鑰sk；

輸出S：有序數(shù)組E(Qorder[k])

1.S：for0≤k≤m

2.S：for0≤i≤m：

3.S：E(rd′[i])←E(rd[i])

4.S：num←m

6.S：for1≤j≤?num/2」

7.C，S：flag=Compare(E(rd′[2i(j-1)])，E(rd′[2i(j-1)+2i-1]))

9.S：E(rd1)←E(rd′[2i(j-1)])⊕E(r1)

10.S：E(rd2)←E(rd′[2i(j-1)+2i-1])⊕E(r2)

11.S： sendE(rd1)E(rd2)toC

12.C：if(flag==1)

13.C：E(rdmin)←E(rd1)

14.C：else：

15.C：E(rdmin)←E(rd2)

16.C： sendE(rdmin) andE(flag)toS

17.S：E(rd′[2i(j-1)])←E(rdmin)⊕(E(flag)⊙E(1))?r2⊙E(flag)?r1

18.S：E(rd′[2i(j-1)+2i-1])←E(0)

19.S：num←「num/2?

20.S：E(rdmin)←E(rd′[0])

21.S：E(Qorder[k])←E(rdmin)

3.3 聚類過程

在OPTICS-CMED模型的聚類過程中，S將半徑ε和最小點數(shù)MinPts兩個參數(shù)作為輸入，計算每個元素的核心距離(cd)和可達距離(rd)，完成后續(xù)聚類過程.

OPTICS-CMED的聚類過程如下：

Step 1.C對數(shù)據(jù)進行處理，將浮點數(shù)轉(zhuǎn)化成整型，對數(shù)據(jù)進行加密，發(fā)送待聚類數(shù)據(jù)集x、半徑ε和最小點數(shù)MinPts給S，并向S提交聚類服務(wù)請求；

Step 2.S收到C的聚類服務(wù)請求后，開始進行聚類，創(chuàng)建兩個隊列，種子隊列Qorder和結(jié)果隊列Qreachdist；

Step 3.如果x中的數(shù)據(jù)全部處理完，則算法結(jié)束；否則，從x中選擇一個未被處理的核心對象，找出它的所有直接密度可達點，如果該點不存在于Qreachdist中，則將其存入Qorder中，并調(diào)用getOrder協(xié)議，與C共同完成可達距離rd排序；

Step 4.如果Qorder為空，則執(zhí)行Step 3；否則，從Qorder中取出第一個樣本點：

Step 4.1.判斷該點是否為核心對象，如果不是，則跳至Step 4；否則將該點存入Qreachdist；

Step 4.2.若該點是核心對象，找到它的所有直接密度可達點，存入Qorder，并調(diào)用getOrder協(xié)議，將Qorder的點按照rd重新排序.如果該點已經(jīng)在Qorder中且新的rd較小，則更新該點的rd；

Step 4.3.若Qorder中不存在直接密度可達樣本點，插入Qorder中，調(diào)用getOrder協(xié)議，將Qorder的點按照rd重新排序；

Step 5.輸出Qreachdist中的有序樣本點，發(fā)送給C；

Step 6.C進行解密得到明文聚類結(jié)果.

4 正確性與安全性分析

4.1 正確性分析

首先對安全距離計算協(xié)議和排序協(xié)議進行分析，并進而證明OPTICS-CMED的正確性.

1)安全距離計算協(xié)議

綜上所述，本文的安全距離計算協(xié)議是正確的.

2)排序協(xié)議

排序協(xié)議中主要采用了選擇排序的思想，在未排序序列中找到最小值放在序列起始位置；在剩余的數(shù)據(jù)中繼續(xù)排序找出最小值，將其放在已排序序列的隊尾；重復(fù)上述過程直到處理完所有數(shù)據(jù).

在求最小值協(xié)議中，通過調(diào)用加密數(shù)據(jù)的比較協(xié)議Compare()實現(xiàn)兩個密文數(shù)據(jù)的比較，由C得到比較結(jié)果flag.然后，S將兩個增加隨機值的待比較的數(shù)據(jù)d1，d2發(fā)送給C，其中d1=dl+r1，d2=dr+r2，r1，r2，是隨機數(shù)，dl表示左值，dr表示右值.

當flag=1時，dmin←d1；

當flag=0時，dmin←d2.

保證dmin記錄的是最小值.C將dmin和flag一同發(fā)送給S，S根據(jù)dmin=dmin+(flag-1)×r2-flag×r1去除干擾值得到真實的最小值dmin.

當flag=1時，dmin=d1=dleft+r1，則：

dmin=dleft+r1+(1-1)×r2-1×r1=dleft；

當flag=0時，dmin=d1=dright+r2，則：

dmin=dright+r2+(0-1)×r2-0×r1=dright.

因此，S可以成功去除干擾值獲得明文最小值dmin，并用下標較小的數(shù)組存儲最小值，同時將下標較大數(shù)組置0，最后d0存儲m個元素中的最小值.

綜上所述，本文的排序協(xié)議是正確的.

3)OPTICS-CMED

在OPTICS-CMED中，首先調(diào)用比較協(xié)議判斷當前加密的樣本數(shù)據(jù)點是否是核心對象，再利用一個輔助數(shù)組vi來判斷該數(shù)據(jù)點是否被訪問過.由于在密文下無法得知vi的值，需要C的幫助，為防止數(shù)據(jù)泄露，S對其增加干擾值后發(fā)送給C進行解密，最后S再去除干擾值得到真正的vi值.若vi=0表示當前數(shù)據(jù)點未被訪問過，vi=1表示當前數(shù)據(jù)點已經(jīng)被訪問過.再調(diào)用排序協(xié)議對可達距離進行排序，保證最后可以得到有序的數(shù)組E(Qreachdist[d]).由于安全距離計算協(xié)議和排序協(xié)議都是正確的，得到包含聚類結(jié)果的E(Qreachdist[d])邏輯上也是正確的.

綜述所述，OPTICS-CMED也是正確的.

4.2 安全性分析

本節(jié)在半誠實模型下對通信協(xié)議和OPTICS-CMED的安全性進行分析，C和S都是半誠實的參與方，它們誠實地遵循協(xié)議的執(zhí)行，允許從協(xié)議執(zhí)行過程中獲取的數(shù)據(jù)進行推斷.其輸入數(shù)據(jù)是隱私數(shù)據(jù)，僅能被個人獲知.

1)安全距離計算協(xié)議

在安全距離計算協(xié)議中，S的視圖為VS=(E(yi)，E(xi)，E(zi)，E(s)).由于FHE是語義安全的，S無法從E(xi)，E(yi)，E(zi)和E(s)中提取出明文xi，yi，zi，s，保證了數(shù)據(jù)xi，yi，zi，s的隱私；此協(xié)議僅由S執(zhí)行，C無法獲得隱私信息.

因此，本文設(shè)計的安全距離計算協(xié)議在半誠實模型下是安全的.

2)排序協(xié)議

在排序協(xié)議中，S的視圖為VS=(E(rd[m])，pk，r1，r2，E(rdmin)，E(Qorder[k]))，其中r1，r2是隨機數(shù).C和S首先調(diào)用加密數(shù)據(jù)的比較協(xié)議對S的加密數(shù)據(jù)E(rd[m])進行比較，C獲得明文的比較結(jié)果flag，由于加密數(shù)據(jù)的比較協(xié)議的安全性，保證了C和S比較過程中數(shù)據(jù)的隱私.接著，S將增加隨機干擾的密文數(shù)據(jù)E(rd1)和E(rd2)發(fā)送給C，C根據(jù)比較結(jié)果flag，將密文E(rd1)和E(rd2)賦值為E(rdmin)，再返回給S.由于FHE加密算法是語義安全的，C即使對密文數(shù)據(jù)E(rdmin)與EP(rd[m])解密也無法獲取明文rdmin和rd[m].由于比較結(jié)果僅被C獲知，C將更新后的密文發(fā)送給S，因此S無法通過密文E(rdmin)，E(rd[m])，獲知左值和右值哪個是最小值，保證了待比較數(shù)據(jù)在S方的隱私.C的視圖為VC=(skP，flag，E(rd1)，E(rd2))，由于E(rd1)，E(rd2)是增加隨機干擾值的密文數(shù)據(jù)，即使C可以使用私鑰解密也很難從明文rd1和rd2中提取出真實值，從而保證了待比較數(shù)據(jù)在C方的隱私.雖然C能夠獲知比較結(jié)果，但其無法獲知待比較數(shù)據(jù)的真實值，無法進行推斷.因此，本文的排序協(xié)議在半誠實模型下是安全的.

綜上所述，本文所設(shè)計的通信協(xié)議在半誠實模型下都是安全的.

3)OPTICS-CMED

在OPTICS-CMED中，首先，調(diào)用比較協(xié)議用于判定該加密數(shù)據(jù)點是否為核心對象.比較協(xié)議在半誠實模型下是安全的，S將增加噪聲干擾的最高位發(fā)送給C，保證其解密后無法得到最高位的明文，從而不知道數(shù)據(jù)的大小.S不擁有FHE私鑰，無法解密，因此比較過程是安全的.

通過調(diào)用安全距離計算協(xié)議計算兩個加密數(shù)據(jù)點的歐氏距離的平方，即核心距離.安全距離計算協(xié)議在半誠實模型下是安全的，整個過程僅在S方進行，未向C方發(fā)送任何數(shù)據(jù)，保證了S方加密數(shù)據(jù)的安全性.S方不擁有私鑰，無法解密待計算的數(shù)據(jù)，又因為FHE的加法與乘法同態(tài)性，保證計算過程的安全性，因此安全距離計算時是安全的.

最后，先調(diào)用更新數(shù)組函數(shù)將未訪問的數(shù)據(jù)點放入種子數(shù)組中，再調(diào)用排序協(xié)議獲取有序數(shù)組，由于S對數(shù)組下標填加干擾值，即使C擁有解密的私鑰也無法獲知真正的下標順序.協(xié)議2在半誠實模型下是安全的，得到的數(shù)據(jù)也是安全的，C無法得知密文的最小值，無法獲取待比較數(shù)據(jù)的大小關(guān)系，保證了數(shù)組元素的大小關(guān)系不會泄露給C.

綜上所述，基于安全距離計算協(xié)議與排序協(xié)議進行構(gòu)造的OPTICS-CMED在半誠實模型下也是安全的.

5 實驗分析

本文的實驗環(huán)境如表1所示.加密方案中的密鑰長度為1024位，安全參數(shù)λ=100.由于FHE方案僅能對整數(shù)進行操作，本節(jié)使用IEEE 754雙精度浮點數(shù)代表實數(shù)，精度為52位，然后通過乘以大的實數(shù)來進行變換.

表1 實驗環(huán)境Table 1 Test environment

實驗采用4種FCPS標準數(shù)據(jù)集(1)http：//uni-marburg.de/fb12/datenbionik/data?language svnc=1/，分別為：Hepta、Lsun、Tetra、Wingnut公共數(shù)據(jù)集.OPTICS聚類的性能主要由參數(shù)ε與MinPts決定，為了獲得最優(yōu)的聚類效果，對參數(shù)ε與MinPts的不同取值情況下的OPTICS聚類性能進行測試，采用輪廓系數(shù)來評價聚類效果.利用4種數(shù)據(jù)集，對OPTICS-CMED與明文下的OPTICS進行對比，參數(shù)與輪廓系數(shù)關(guān)系如圖3-圖6所示.參數(shù)ε越小，明文OPTICS聚類算法與OPTICS-CMED的輪廓系數(shù)均越來越大，說明聚類效果得到提升.

由圖3和圖4對比可知，MinPts值越大，輪廓系數(shù)越小，表示其聚類性能有所下降.當參數(shù)ε小到超過數(shù)據(jù)閾值時，將無法完成聚類.

圖3 參數(shù)與輪廓系數(shù)關(guān)系(Hepta數(shù)據(jù)集)Fig.3 Relationship between parameters and silhouette coefficient(Hepta dataset)

圖4 參數(shù)與輪廓系數(shù)關(guān)系(Lsun數(shù)據(jù)集)Fig.4 Relationship between parameters and silhouette coefficient(Lsun dataset)

從圖4～圖6中數(shù)據(jù)分析可知，OPTICS-CMED聚類輪廓系數(shù)比明文OPTICS算法低1.3%～8.1%，且輪廓系數(shù)均超過0.6，在可接受范圍內(nèi)，因此OPTICS-CMED可以在密文下完成聚類，且聚類效果可以得到有效保障.

圖5 參數(shù)與輪廓系數(shù)關(guān)系(Tetra數(shù)據(jù)集)Fig.5 Relationship between parameters and silhouette coefficient(Tetra dataset)

圖6 參數(shù)與輪廓系數(shù)關(guān)系(Wingnut數(shù)據(jù)集)Fig.6 Relationship between parameters and silhouette coefficient(Wingnut dataset)

采用F1-score對本方案進行實驗分析.在聚類中，精確率(Precision)和召回率(Recall)是相互矛盾的，F(xiàn)1-score會同時考慮精確率和召回率，重新計算新的分數(shù)，如式(3)所示，當F1-score較高時則能說明實驗方法有效.

(3)

表2給出了參數(shù)ε與MinPts的不同取值情況下的OPTICS-CMED與明文OPTICS對比結(jié)果.

表2 OPTICS-CMED與明文OPTICS的F1-score對比結(jié)果Table 2 F1-score comparison of OPTICS-CMED and plaintext clustering

表2中1與2、5與6對照數(shù)據(jù)可知，當MinPts相同時，參數(shù)ε越小，F(xiàn)1-score越來越大，整體性能得到提升；但當參數(shù)ε達到最低閾值時，將無法聚類.由2與4、6與7組對比數(shù)據(jù)可知，MinPts值越大，F(xiàn)1-score也越來越大.

綜合分析輪廓系數(shù)與F1-score可知，當OPTICS參數(shù)ε=0.01且MinPts=10時，聚類效果最優(yōu).

在參數(shù)為ε=0.01且MinPts=10情況下，利用Lsun數(shù)據(jù)集(n表示數(shù)據(jù)總數(shù)，取n=50、100、200、300、400)分別進行實驗.

表3給出了當n變化時明文聚類與OPTICS-CMED模型客戶端和服務(wù)器運行時間的對比.數(shù)據(jù)表明，其運行時間隨n線性增長，服務(wù)器承擔了主要的開銷，減輕了客戶端的負擔.

表3 明文聚類與OPTICS-CMED的時間開銷對比Table 3 Time cost comparison of plaintext clutering and OPTICS-CMED

6 結(jié)束語

針對面向密文數(shù)據(jù)的OPTICS聚類研究成果較少的問題，利用全同態(tài)加密構(gòu)建了面向密文數(shù)據(jù)的OPTICS聚類模型(OPTICS-CMED).首先，對OPTICS-CMED的實體構(gòu)成進行介紹，給出了形式化定義，詳細描述了模型的通信協(xié)議及其在聚類過程中的調(diào)用方式，從正確性、安全性兩方面進行理論分析，通過實驗對模型進行性能測試，結(jié)果表明本文設(shè)計的OPTICS-CMED能夠在密文下完成聚類運算，同時可以保證在密文下的聚類效果，具有一定的實際應(yīng)用價值.