基于ELM集成和半監督聚類的SNS隱私保護

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

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

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

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

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

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

傳統的聚類算法對初始值敏感，即不同的初始值會導致不同的聚類結果，有時候會使聚類陷入局部最優，而不是全局最優.針對上述問題，本文提出一種基于Bagging的ELM（extreme learning machine）集成與基于Seeds集半監督聚類相結合的隱私保護算法.該算法首先利用ELM－Bagging對無標記數據進行標記，并加入Seeds集以擴大監督信息規模，然后采用基于Seeds集的半監督聚類算法進行K－匿名，以達到隱私保護的目的.

1 K－匿名數據隱私保護概念

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

定義1 （K－匿名）：給定數據表T（A1，A2，…，An），QI是T的準標識符，T［QI］為T在QI上的投影（記錄可以重復），當且僅當在T［QI］上出現的每組值至少要在T［QI］上出現K次，則T滿足K－匿名.

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

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

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

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

1）連續型數據距離定義

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

在滿足K－匿名模型的同時，LL越小，說明類內同質性越強，相對的信息損失量也就越小.

2）分類型數據距離定義

對于分類型數據距離定義相對比較簡單，如果Xi＝Yi，d（Xi，Yi）＝0，否則d（Xi，Yi）＝1.

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

2 半監督聚類

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

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

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

從目標函數可以看出，初始類中心的選取對聚類結果會有很大的影響.如果隨機選取初始類中心，往往會導致準則函數陷入局部最優，而不是全局最優.

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

3 基于Bagging的ELM集成算法

實際聚類應用中帶標記數據非常少，而基于Seeds集的半監督聚類算法受Seeds集規模和質量的影響明顯.本文使用ELM算法，利用少量帶標記數據訓練分類器，對無標記數據進行標記，使標記訓練集增大，同時采用Bagging算法集成ELM分類器，從而提高標記的準確性和泛化能力.

3.1 ELM

ELM算法是由Huang于2004年提出，是一種單隱層前饋網絡學習算法［16］.ELM在訓練前隨機設置隱含層到輸入層的連接權值和偏置值，對輸出層權重產生唯一最優解，其本質是不需要調整隱藏層，試圖達到最小訓練誤差以及最小輸出權重.該算法具有較好的泛化性能，其學習速度相當快.

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

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

H為第j列表示第j個節點層對應的輸出，其中的一個解就是H′T.

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

1）隨機產生隱藏節點的參數aj，bj，i＝1，2，…，L；2）計算隱藏層輸出矩陣H；3）計算輸出權重β＝H′T.

3.2 集成分類器設計

考慮到單個弱分類器準確率不高，可以將分類器集成使用，提高準確率.集成學習是一種分類器組合方法，使得組合后的分類器能夠表現出比單個分類器更好的性能.分類器集成的泛化誤差等于集成中個體網絡的平均泛化誤差和平均差異度之差，因此，要增強分類器的泛化能力，一方面應提高單個ELM的泛化能力，另一方面應增大訓練集之間的差異.

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

本文提出基于Bagging的ELM集成算法，對無標記數據進行標記.算法描述如下：

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

3.3 基于ELM－Bagging的半監督聚類匿名算法

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

輸入：數據集X，匿名要求K，帶標記的Seeds集S，基分類器個數T，以及ELM隱層節點P1，P2，…，PT的個數.

輸出：數據集X的K－匿名.

Step1 ELM－Bagging訓練過程對Seeds集的擴充

a）對S進行Bootstrap采樣，得到T個訓練集S1，S2，…，ST；

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

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

Step2 初始化聚類中心

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

Step3 重新分配數據點

X中每個數據點x都重新分配到距離最近的聚類中，要求每個聚類當中的個數K＜N＜K＋1.

Step4 重新計算聚類中心

Step5 如果所有聚類中心都不變化，則算法結束，否則轉入Step3

4 實驗

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

實驗的硬件環境為Pentium（R）dual－core3.2GHz CPU操作系統為Microsoft Windows XP，所有程序均用matlab7.1實現.

表1 500個數據Tab.1 500data

表2 1 000個數據Tab.2 1 000data

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

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

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

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

5 結束語

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

［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，FEDER 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集的半監督核聚類［J］.計算機工程與應用，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] 李昆侖，曹錚，劉明，等.半監督聚類的若干新發展［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.