基于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.