李昆侖，王哲，張娟，武倩，宋嵩

（河北大學(xué)電子信息工程學(xué)院，河北保定 071002）

社會化網(wǎng)絡(luò)服務(wù)（social network service，SNS）是近年來興起的一類網(wǎng)絡(luò)應(yīng)用，作為一種新興的互聯(lián)網(wǎng)應(yīng)用模式，正受到越來越多的關(guān)注.在美國，SNS網(wǎng)站Facebook超越谷歌成為美國最大的網(wǎng)站.Hitwise發(fā)布的統(tǒng)計數(shù)據(jù)顯示，7.07%的美國網(wǎng)絡(luò)用戶訪問該網(wǎng)站.截至2011年，中國SNS網(wǎng)站的用戶數(shù)量已達(dá)2.35億，與此同時，SNS網(wǎng)站中的各種問題也逐漸顯現(xiàn)出來，特別是用戶個人信息安全問題，已成為所有SNS網(wǎng)站發(fā)展所面臨的共同挑戰(zhàn).2011年12月，CSDN、人人網(wǎng)、世紀(jì)佳緣等眾多SNS網(wǎng)站遭遇黑客攻擊，導(dǎo)致4 300萬用戶隱私被泄露，帶來很大的安全隱患.

為了保護(hù)個人隱私信息，需要在發(fā)布前對其進(jìn)行處理.采用K－匿名（K－anonymization）模型可以達(dá)到防止隱私泄露的目的.K－匿名模型［1］是1998年Samarati和Sweeney提出的，它要求發(fā)布的數(shù)據(jù)中，至少存在K條記錄在準(zhǔn)標(biāo)識符上不可區(qū)分，使攻擊者不能判別出隱私信息所屬的具體個體，從而保護(hù)了個人隱私.K－匿名需要對隱私數(shù)據(jù)在準(zhǔn)標(biāo)識符上的屬性值作數(shù)據(jù)概化處理，以消除鏈接攻擊，概化處理增加了屬性值的不確定性，不可避免地會造成一定的信息損失，降低了數(shù)據(jù)的可用性.當(dāng)前K－匿名模型的研究主要集中在保護(hù)個人隱私信息的同時，提高數(shù)據(jù)的可用性.

Aggarwal等［2－3］的研究表明，最優(yōu)數(shù)據(jù)匿名問題（即在實現(xiàn)對敏感屬性匿名保護(hù)的同時，使得信息損失最小化）是NP難題.圍繞如何降低匿名保護(hù)時的信息損失，已出現(xiàn)了多種啟發(fā)式數(shù)據(jù)匿名算法.啟發(fā)式算法的優(yōu)點在于它們是通用的，即可以應(yīng)用在許多匿名規(guī)則上.Iyengar［4］采用基于遺傳算法的不完全隨機(jī)搜索方法，解決了K－匿名中的組合爆炸問題.根據(jù)頻繁項集挖掘算法的思想，LeFevre［5］提出Icognito算法來計算匿名數(shù)據(jù).Bayardo［6］提出基于冪集空間搜索的算法，來解決K－匿名的隱私保護(hù)問題.

以上研究工作大多集中在通過泛化、隱匿實現(xiàn)K－匿名，然而，該技術(shù)存在效率低、K－匿名化后數(shù)據(jù)的可用性差等問題.近年來，一些學(xué)者將聚類算法應(yīng)用到隱私信息的K－匿名化［7－8］，彌補(bǔ)了泛化、隱匿技術(shù)的不足.Hansen等［9］證明了單變量數(shù)據(jù)的最優(yōu)聚類算法可在多項式時間內(nèi)實現(xiàn).Sonlanas［10］提出了基于遺傳算法的多變量聚類算法和可變大小的多變量V－MDAV算法.

傳統(tǒng)的聚類算法對初始值敏感，即不同的初始值會導(dǎo)致不同的聚類結(jié)果，有時候會使聚類陷入局部最優(yōu)，而不是全局最優(yōu).針對上述問題，本文提出一種基于Bagging的ELM（extreme learning machine）集成與基于Seeds集半監(jiān)督聚類相結(jié)合的隱私保護(hù)算法.該算法首先利用ELM－Bagging對無標(biāo)記數(shù)據(jù)進(jìn)行標(biāo)記，并加入Seeds集以擴(kuò)大監(jiān)督信息規(guī)模，然后采用基于Seeds集的半監(jiān)督聚類算法進(jìn)行K－匿名，以達(dá)到隱私保護(hù)的目的.

1 K－匿名數(shù)據(jù)隱私保護(hù)概念

K－匿名是一種保護(hù)隱私數(shù)據(jù)的有效方法，它通過對數(shù)據(jù)進(jìn)行泛化、抑制、聚類等操作，使得每條數(shù)據(jù)包含在一個容量大于等于K的組中，且不能夠唯一鑒別每條數(shù)據(jù)所有者的身份，從而達(dá)到保護(hù)隱私的目的.泛化、隱匿是實現(xiàn)數(shù)據(jù)K－匿名化的傳統(tǒng)技術(shù)，但它在處理數(shù)值型數(shù)據(jù)時存在效率低、信息損失量大等缺陷.為此，聚類算法被應(yīng)用到數(shù)據(jù)的K－匿名上.為了便于K－匿名聚類算法，引入如下幾個定義［11］：

定義1 （K－匿名）：給定數(shù)據(jù)表T（A1，A2，…，An），QI是T的準(zhǔn)標(biāo)識符，T［QI］為T在QI上的投影（記錄可以重復(fù)），當(dāng)且僅當(dāng)在T［QI］上出現(xiàn)的每組值至少要在T［QI］上出現(xiàn)K次，則T滿足K－匿名.

定義2 （匿名表聚類）：給定數(shù)據(jù)表T（A1，A2，…，An），QI是T的準(zhǔn)標(biāo)識符，基于QI的一個K劃分將T劃分為G個類，設(shè)Ci為第i類的類質(zhì)心，對于所有i（i＝1，…，G），用Ci取代第i類中所有元素的操作稱為聚類.

實現(xiàn)匿名化的聚類算法分為3個步驟：1）刪除顯示標(biāo)識符，數(shù)據(jù)被初步匿名化；2）將數(shù)據(jù)表T的QI屬性值標(biāo)準(zhǔn)化，再基于QI進(jìn)行K劃分（K＝2）；3）將標(biāo)準(zhǔn)化的值恢復(fù)為原數(shù)值，對K劃分的數(shù)據(jù)表進(jìn)行聚類操作（用平均值作為類質(zhì)心），得到2個等價類.

數(shù)據(jù)隱私匿名問題可以看作是具有特定約束的聚類問題，即必須滿足匿名模型的約束要求［12］.傳統(tǒng)聚類方法并不適合直接用于解決數(shù)據(jù)匿名問題［7］.傳統(tǒng)的聚類過程要求指定具體的類數(shù)目，然而，K－匿名聚類問題并不限制類的數(shù)目，而是要求每個類至少包含K條記錄.在滿足匿名模型要求的情況下，使得類內(nèi)對象盡可能地相似，而類間對象盡可能地不相似.

數(shù)據(jù)屬性按照類型可分為2類：連續(xù)型數(shù)據(jù)（如郵編，收入等）和分類型數(shù)據(jù)（如顏色，職稱，名次等）.不同類型的數(shù)據(jù)，數(shù)據(jù)間相似性度量方式及類中心定義是不相同的.

1）連續(xù)型數(shù)據(jù)距離定義

其中Xi，Yi表示X，Y第i維的屬性.

在滿足K－匿名模型的同時，LL越小，說明類內(nèi)同質(zhì)性越強(qiáng)，相對的信息損失量也就越小.

2）分類型數(shù)據(jù)距離定義

對于分類型數(shù)據(jù)距離定義相對比較簡單，如果Xi＝Y(jié)i，d（Xi，Yi）＝0，否則d（Xi，Yi）＝1.

實施K－匿名模型隱私保護(hù)主要是考慮以下2個方面：1）如何保證數(shù)據(jù)應(yīng)用過程中不泄露隱私；2）如何更有利于數(shù)據(jù)的應(yīng)用，降低信息損失量.當(dāng)前，隱私保護(hù)領(lǐng)域的研究主要集中于如何設(shè)計隱私保護(hù)方法更好地達(dá)到這2方面的平衡.

2 半監(jiān)督聚類

在數(shù)據(jù)匿名問題中，存在大量的無標(biāo)記數(shù)據(jù)，而有標(biāo)記的數(shù)據(jù)相對較少.這就導(dǎo)致有限的訓(xùn)練數(shù)據(jù)不足以提供足夠的數(shù)據(jù)分布信息，使得聚類后的數(shù)據(jù)不能得到滿意的匿名結(jié)果.因此，本文提出采用半監(jiān)督聚類方法解決K－匿名問題.

半監(jiān)督聚類算法可分為3類：1）基于約束的方法.該方法使用監(jiān)督信息約束聚類的搜索過程，通過使用已經(jīng)給定的標(biāo)記數(shù)據(jù)集或者其他約束條件來進(jìn)行聚類，得到更多的啟發(fā)式信息，減少搜索的盲目性，其直接目標(biāo)是取得更好的聚類效果.2）基于相似性度量的方法.該方法首先利用標(biāo)記數(shù)據(jù)找到滿足標(biāo)記或約束的距離測度函數(shù)，再通過利用基于各種距離的聚類方法進(jìn)行聚類的過程，它的主要目的是對符合某些給定條件的距離函數(shù)進(jìn)行聚類.3）基于約束和相似性度量的融合方法［13－14］.

現(xiàn)有半監(jiān)督聚類算法很多是在傳統(tǒng)聚類算法基礎(chǔ)上引入監(jiān)督信息發(fā)展而來.K－means算法也稱K－均值算法［15］，是目前最為常用的聚類算法之一，它主要以K為參數(shù)，把n個對象分為K個類，使類內(nèi)具有較高相似度，類間具有較低的相似度.其目標(biāo)函數(shù)如下：

從目標(biāo)函數(shù)可以看出，初始類中心的選取對聚類結(jié)果會有很大的影響.如果隨機(jī)選取初始類中心，往往會導(dǎo)致準(zhǔn)則函數(shù)陷入局部最優(yōu)，而不是全局最優(yōu).

Basu等提出的Generative模型結(jié)合EM理論支持的Seeded－K－means和Constrained－K－means算法是基于約束的半監(jiān)督聚類方法［15］，這2種算法是基于種子（Seeds）集的，它們使用少量帶標(biāo)記數(shù)據(jù)形成Seeds集以改善K－means聚類的初始化效果，進(jìn)而提高整個數(shù)據(jù)集的聚類效果.

3 基于Bagging的ELM集成算法

實際聚類應(yīng)用中帶標(biāo)記數(shù)據(jù)非常少，而基于Seeds集的半監(jiān)督聚類算法受Seeds集規(guī)模和質(zhì)量的影響明顯.本文使用ELM算法，利用少量帶標(biāo)記數(shù)據(jù)訓(xùn)練分類器，對無標(biāo)記數(shù)據(jù)進(jìn)行標(biāo)記，使標(biāo)記訓(xùn)練集增大，同時采用Bagging算法集成ELM分類器，從而提高標(biāo)記的準(zhǔn)確性和泛化能力.

3.1 ELM

ELM算法是由Huang于2004年提出，是一種單隱層前饋網(wǎng)絡(luò)學(xué)習(xí)算法［16］.ELM在訓(xùn)練前隨機(jī)設(shè)置隱含層到輸入層的連接權(quán)值和偏置值，對輸出層權(quán)重產(chǎn)生唯一最優(yōu)解，其本質(zhì)是不需要調(diào)整隱藏層，試圖達(dá)到最小訓(xùn)練誤差以及最小輸出權(quán)重.該算法具有較好的泛化性能，其學(xué)習(xí)速度相當(dāng)快.

對于N個不同的訓(xùn)練樣本Z＝（Xi，ti）i＝1，2，…，N.具有L個隱層節(jié)點，激活函數(shù)為g（x）的ELM，任意指定aj和bj，可以零誤差逼近任意的N個樣本，如式（5）.

其中aj是輸入權(quán)值，bj是隱層節(jié)點的閾值，xi為輸入向量，oi為輸出向量，β是輸出權(quán)值，或公式（5）可以簡化表示為

H為第j列表示第j個節(jié)點層對應(yīng)的輸出，其中的一個解就是H′T.

ELM算法的步驟可歸納如下：

1）隨機(jī)產(chǎn)生隱藏節(jié)點的參數(shù)aj，bj，i＝1，2，…，L；2）計算隱藏層輸出矩陣H；3）計算輸出權(quán)重β＝H′T.

3.2 集成分類器設(shè)計

考慮到單個弱分類器準(zhǔn)確率不高，可以將分類器集成使用，提高準(zhǔn)確率.集成學(xué)習(xí)是一種分類器組合方法，使得組合后的分類器能夠表現(xiàn)出比單個分類器更好的性能.分類器集成的泛化誤差等于集成中個體網(wǎng)絡(luò)的平均泛化誤差和平均差異度之差，因此，要增強(qiáng)分類器的泛化能力，一方面應(yīng)提高單個ELM的泛化能力，另一方面應(yīng)增大訓(xùn)練集之間的差異.

現(xiàn)有的集成方法通過擾動訓(xùn)練數(shù)據(jù)來獲得差異度較大的個體網(wǎng)絡(luò).例如Boosting算法中各網(wǎng)絡(luò)的訓(xùn)練集決定于之前產(chǎn)生的網(wǎng)絡(luò)的表現(xiàn)，被已有網(wǎng)絡(luò)錯誤判斷的示例將以較大的概率出現(xiàn)在新網(wǎng)絡(luò)的訓(xùn)練集中.Bagging算法的基礎(chǔ)是可重復(fù)取樣從原始訓(xùn)練集中隨機(jī)抽取的若干示例來訓(xùn)練網(wǎng)絡(luò).通過重復(fù)選取訓(xùn)練集增加了集成的差異度，從而提高了泛化能力.

本文提出基于Bagging的ELM集成算法，對無標(biāo)記數(shù)據(jù)進(jìn)行標(biāo)記.算法描述如下：

1）每次從訓(xùn)練樣本中隨機(jī)抽取1／2樣本（有放回樣本），用取出的樣本訓(xùn)練ELM分類器，得到一個ELM分類器h1；2）用相同的方法形成多個ELM分類器，訓(xùn)練之后可得到一個預(yù)測函數(shù)序列h1，h2，…，ht；3）對未知樣本分類時，每個分類器ht都得到一個分類結(jié)果，T個分類器投票，得票最高的分類結(jié)果即為未知樣本的分類結(jié)果.

3.3 基于ELM－Bagging的半監(jiān)督聚類匿名算法

本文提出了一種基于Bagging的ELM集成與基于Seeds集半監(jiān)督聚類相結(jié)合的隱私保護(hù)算法.該算法首先利用基于Bagging的ELM集成分類方法對無標(biāo)記數(shù)據(jù)進(jìn)行標(biāo)記，并加入Seeds集以擴(kuò)大監(jiān)督信息規(guī)模，其次用標(biāo)記信息Seeds集初始化聚類中心，并做K－均值聚類，最后，用類中心代替類中所有數(shù)據(jù)，完成匿名隱私保護(hù).為了盡可能的增大訓(xùn)練集之間的差異，算法用Bootstrap進(jìn)行采樣.算法描述如下.

輸入：數(shù)據(jù)集X，匿名要求K，帶標(biāo)記的Seeds集S，基分類器個數(shù)T，以及ELM隱層節(jié)點P1，P2，…，PT的個數(shù).

輸出：數(shù)據(jù)集X的K－匿名.

Step1 ELM－Bagging訓(xùn)練過程對Seeds集的擴(kuò)充

a）對S進(jìn)行Bootstrap采樣，得到T個訓(xùn)練集S1，S2，…，ST；

b）用S1，S2，…，ST分別訓(xùn)練ELM，得到ELM分類器H1，H2，…，HT；

c）對未知樣本X分類時，每個分類器Hi都得出一個分類結(jié)果，T個分類器投票，得票最高的分類結(jié)果即為未知樣本X的類標(biāo)記，并將X加入到Seeds中.

Step2 初始化聚類中心

a）將擴(kuò)充的Seeds集S中數(shù)據(jù)點按標(biāo)記劃分為M個聚類，如果某一類沒有標(biāo)記數(shù)據(jù)，從X中將任意數(shù)據(jù)放入，其中M＝X／K取整數(shù)；

Step3 重新分配數(shù)據(jù)點

X中每個數(shù)據(jù)點x都重新分配到距離最近的聚類中，要求每個聚類當(dāng)中的個數(shù)K＜N＜K＋1.

Step4 重新計算聚類中心

Step5 如果所有聚類中心都不變化，則算法結(jié)束，否則轉(zhuǎn)入Step3

4 實驗

實驗所使用的數(shù)據(jù)集為UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的Adult數(shù)據(jù)，該數(shù)據(jù)集包括部分美國人口普查數(shù)據(jù)，Adult數(shù)據(jù)集是隱私保護(hù)的基準(zhǔn)測試集.將含有缺失值的記錄刪除，數(shù)據(jù)集共有45 222個元組.為了驗證算法的有效性，隨機(jī)選取2組數(shù)據(jù)進(jìn)行相同測試.2組數(shù)據(jù)的個數(shù)分別為500，1 000個數(shù)據(jù)，將其中age，fnlwgt，education－num 3個屬性作為準(zhǔn)標(biāo)識符，將salary作為敏感屬性，考慮到不同準(zhǔn)標(biāo)識符對匿名效果影響不同，在這里，將所有數(shù)據(jù)進(jìn)行歸一化處理如下：

實驗的硬件環(huán)境為Pentium（R）dual－core3.2GHz CPU操作系統(tǒng)為Microsoft Windows XP，所有程序均用matlab7.1實現(xiàn).

表1 500個數(shù)據(jù)Tab.1 500data

表2 1 000個數(shù)據(jù)Tab.2 1 000data

實驗中，設(shè)置初始標(biāo)記率為10%，然后通過ELM－Bagging算法將Seeds集數(shù)量依次增加至20%，30%，40%，50%，做基于Seeds集的半監(jiān)督聚類并計算信息損失量.

一個集成分類器的泛化能力是由每個分類器的輸出空間的差異程度決定的，分類器之間的差異度是再訓(xùn)練階段的目標(biāo).ELM在輸出相對準(zhǔn)確的前提下，通過調(diào)整ELM參數(shù)的不同保證了分類器輸出空間的不同.從統(tǒng)計機(jī)器學(xué)習(xí)的角度來看，當(dāng)基分類器個數(shù)越多時，集成分類器的輸出結(jié)果更接近期望值，但是，當(dāng)基分類器個數(shù)增加時，分類器的計算時間和復(fù)雜度都會增加.在實驗中訓(xùn)練7個基分類器，通過調(diào)整隱層節(jié)點個數(shù)，保證每個分類器的準(zhǔn)確率在80%以上，否則會產(chǎn)生過多的噪聲，影響聚類效果.

算法Step1是通過ELM－Bagging算法對Seeds擴(kuò)大，由于ELM是一種速度極快的分類器，所以Step1中時間代價可以忽略不計.Step2，Step3進(jìn)行半監(jiān)督K－均值聚類的代價主要集中在重新分配數(shù)據(jù)點和重新計算聚類中心的迭代次數(shù)上.假設(shè)數(shù)據(jù)集規(guī)模為n，維數(shù)為d，迭代次數(shù)為m，所以，算法最壞情況下的時間復(fù)雜度為O（mknd）.

從表中可以看出，當(dāng)標(biāo)記率相同的時候，隨著匿名數(shù)的增加，信息損失量隨之逐漸增加.這是因為K－匿名本身就是NP難題，要想獲得更好的隱私保護(hù)效果，就要以增大信息損失量為代價.當(dāng)K值相同的時候，隨著Seeds集規(guī)模的增加，信息損失量在減少，這是因為ELM集成分類器可以使得Seeds集規(guī)模持續(xù)增大的同時質(zhì)量有所提高，進(jìn)而可以有效地利用監(jiān)督信息指導(dǎo)聚類過程，最終達(dá)到改善聚類性能的效果.

5 結(jié)束語

SNS是近年來新興的一類網(wǎng)絡(luò)應(yīng)用，針對這類網(wǎng)絡(luò)應(yīng)用的隱私安全問題，本文采用K－匿名模型進(jìn)行隱私保護(hù)，提出一種基于Bagging的ELM集成與基于Seeds集的半監(jiān)督聚類相結(jié)合的匿名算法.在社會服務(wù)化網(wǎng)絡(luò)中，存在大量無標(biāo)記數(shù)據(jù)和少量已標(biāo)記數(shù)據(jù)，該方法能夠通過ELM－Bagging算法訓(xùn)練未標(biāo)記數(shù)據(jù)，增大標(biāo)記數(shù)據(jù)的規(guī)模，充分利用有限的監(jiān)督信息指導(dǎo)完成聚類匿名任務(wù).實驗表明，該方法能夠有效地保護(hù)個人隱私安全，并且隨著標(biāo)記信息的不斷擴(kuò)大，信息損失量在減少.同時，因為ELM集成分類器速度較快，所以該方法與一般的半監(jiān)督聚類算法相比，并沒有增加算法的時間復(fù)雜性.

［1] SAMARATI P，SWEENEY L.Generalizing data to provide anonymity when disclosing information［Z］.Proc of the 17th ACM SIGMOD SIGACT SIGART Symposium，New York，ACM，1998.

［2] AGGARWAL G，F(xiàn)EDER T，KENTHAPADI K，et al.Achieving anonymity via clustering［Z］.Proc of the 25th ACM SIGMOD－SIGACT－SIGART Symp，New York，ACM，2006.

［3] MEYERSON A，WILLIAMS R.On the complexity of optimal k－anonymity［Z］.Proc of the 23rd ACMSIGACT－SIGMOD－SIGART Symp，New York，ACM，2004.

［4] IYENGAR V.Transforming data to satisfy privacy constraints［Z］.Proc of the 8th ACM SIGKDD Int'l Conference，New York：ACM，2002.

［5] LEFEVRE K，DEWITT D，RAMAKRISHNAN R.Incognito：Efficient full－domain k－anonymity［Z］.Proc of the 24th ACM SIGMOD Int'l Conference，New York：ACM，2005.

［6] BAYARDO R，AGRAWAL R.Data privacy through optimal K－anonymization［Z］.Proc of the 21st Int'l Confereence，Los Alamitos，2005.

［7] HE Wei，LIU Xing.A cluster－based protocol to enforce integrity and preserve privacy in data aggregation［Z］.Proceedings of the 29th IEEE International Conference on Distributed Computing Systems Workshops，Montreal，2009.

［8] LIN Jing，WEN Tong.Density－based microaggregation for statistical disclosure control［J］.ACM Trans Algorithms，2010，6（3）：1－19.

［9] LEFEVRE K，DEWITT D，RAMAKRISHNAN R.Mondrian multidimensional k－anonymity［Z］.Proc of the 22nd Int'l Conference，Los Alamitos，2006.

［10] SOLANAS A，MARTINEZ BALLESTE A，DOMINGO FERRER J，et al.A 2d－tree－based blocking method for microaggreagting very large data sets［Z］.Proc of the First International Conference on Availability，Reliability and Security，Sydney，2006.

［11] DOMING－FERRER J，TORRA V.Ordinal，continuous and heteroge－neous k－anonymitythrough microaggreagtion［J］.Journal of Data Mining and Knowledge Discovery，2005，11（2）：195－202.

［12] CHENG Jing，LIU Jia.K－isomorphism：Privacy preserving network publication against structural attacks［Z］.Proceedings of the ACM SIGMOD International Conference on Management of Data，New York，2010.

［13] 李昆侖，張超，劉明，等.基于SEED集的半監(jiān)督核聚類［J］.計算機(jī)工程與應(yīng)用，2010，45（20）：154－157.LI Kunlun，ZHANG Chao，LIU Ming，et al.Semi－supervised kernel clustering algorithm based on seed set［J］.Computer Engineering and Applications，2010，45（20）：154－157.

［14] 李昆侖，曹錚，劉明，等.半監(jiān)督聚類的若干新發(fā)展［J］.模式識別與人工智能，2010，22（5）：735－742.LI Kunlun，CAO Zheng，LIU Ming，et al.Some developments on semi－supervised clustering［J］.Pattern Recognition and Artificial Intelligence，2010，22（5）：735－742.

［15] MACQUEEN J.Some methods for classification and analysis of multivariate observations［Z］.Proc of the 5th Berkeley Symp，Berkeley，1967.

［16] HUANG Guangbin.Extreme learning machine：A new learning scheme of feedforward neural networks［J］.Neurocomputing，2006，70（8）：489－501.