基于Tsallis熵的近似差分隐私K-means算法.pdf

第 8 卷 第 4 期 信 息 安 全 学 报 Vol.8 No.4 2023 年 7 月 Journal of Cyber Security July 2023 通讯作者:李男,博士,副教授,Email:。本课题得到国家自然科学基金资助项目(No.62472447)资助。收稿日期:2022-01-01;修改日期:2022-03-08;定稿日期:2023-04-20 基于 Tsallis 熵的近似差分隐私 K-means 算法 杨舒丹杨舒丹1,2,李 男1,2,郑文娟3,杜启明1 1战略支援部队信息工程大学 网络空间安全学院 郑州 中国 450000 2数学工程与先进计算国家重点实验室 郑州 中国 450000 332142 部队 保定 中国 071000 摘要 利用 K-means 算法对用户信息进行聚类时,存在隐私泄露的风险。差分隐私保护技术可提供严格的隐私保护,但目前大多数满足差分隐私的 K-means 算法在处理多维数据时,存在随机选择质心和噪声添加不均衡的问题,因而导致聚类结果不理想。为此,本文提出一种基于 Tsallis 熵的近似差分隐私 K-means 算法。针对质心选择的随机性问题,提出 Tsallis 熵对属性赋权的策略来优化对象间的欧氏距离,然后对比各对象到唯一随机初始质心的赋权欧式距离来确定其余初始质心,使算法在减少随机选择初始质心的同时,提高模型准确率;在此基础上,针对噪声添加不均衡的问题,提出一种能够平衡信噪比的隐私预算分配策略,然后对迭代质心加入高斯扰动,使算法在不增加计算复杂度的情况下满足(,)差分隐私保护,同时提升扰动结果的准确性;最后在四个真实数据集上对算法进行有效性评价。实验结果表明,所提出的算法能够在保证用户隐私安全的同时实现高效用的聚类。关键词 近似差分隐私;高斯机制;Tsallis 熵;K-means 聚类;数据挖掘 中图法分类号 TP391 DOI 号 10.19363/J10-1380/tn.2023.07.08 An approximate differential privacy K-means algorithm based on Tsallis entropy YANG Shudan1,2,LI Nan1,2,ZHENG WenJuan3,DU Qiming1 1 Department of Cyberspace Security Academy,Strategic Support Force Information Engineering University,Zhengzhou 450000,China 2 State Key Laboratory of Mathematical Engineering and Advanced Computing,Zhengzhou 450000,China 3 Peoples Liberation Army 32142 Unit,Baoding 071000,China Abstract When using the K-means algorithm to cluster user information,there is a risk of privacy leakage.Differential privacy protection technology can provide strict privacy protection.However,most of the current K-means algorithms that meet differential privacy have problems of random selection of centroids and imbalanced noise addition when processing multi-dimensional data,which leads to unsatisfactory clustering results.To this end,this paper proposes an approximate differential privacy K-means algorithm based on Tsallis entropy.Aiming at the randomness problem of centroid selection,a strategy of attribute weighting by Tsallis entropy is proposed to optimize the Euclidean distance between objects,and then the weighted Euclidean distance between each object and the unique random initial centroid is compared to determine the remaining initial centroids.This allows the algorithm to reduce the random selection of the initial centroid while im-proving the accuracy of the model;on this basis,a privacy budget allocation strategy that can balance the signal-to-noise ratio is proposed for the problem of noise imbalance,and then add Gaussian perturbation to the iterative centroid,so that the algorithm satisfies(,)differential privacy protection without increasing the time complexity,and at the same time improves the accuracy of the perturbation results;finally,the effectiveness of the algorithm is evaluated on four real data sets.Experimental results show that the proposed algorithm can achieve efficient clustering while ensuring user privacy.Key words approximate differential privacy;Gaussian mechanism;Tsallis entropy;K-means clustering;data mining 1 引言 随着信息技术的快速发展,人类社会正处于万物互联的大数据时代,数据作为大数据时代的核心要素,已成为技术创新的基石、经济繁荣的催化剂1。为了充分释放数据的价值,以 K-means 聚类分析2为代表的数据挖掘3算法得到了广泛的应用。然而这些算法在发现知识的同时,也在无时无刻地114 Journal of Cyber Security 信息安全学报,2023 年 7 月,第 8 卷,第 4 期 收集着人们的个人信息,如果在应用中不注重保护个人信息,则攻击者很容易通过重构攻击4-6、成员推理攻击等手段获取这些信息,进而造成个人隐私的泄露。因此,在聚类过程中获得高质量数据分析的同时,应该不断加强对个人隐私的保护,只有这样才能促进大数据应用健康发展。差分隐私7定义了一个与背景知识无关的量化分析模型,并提供严格的数学证明,具有强大的隐私保障水平,已被广泛应用于数据挖掘领域8-11。已有文献提出满足差分隐私的 K-means 聚类算法:Blum等人12最早提出了基于差分隐私的K-means算法,并通过 SuLQ 平台13实现;Frank 等人14基于PINQ平台设计和实现了满足差分隐私的K-means聚类算法;Thanh 等人15通过直接关注数据点,提出估计误差的隐私感知 K-means 算法,以阻止对手推断未知数据点;Yu 等人16根据数据点的分布密度选择初始中心点,提出剔除离群值的差分隐私 K-means算法;胡等人17以 K-means+的结果作为输入值,通过交替的方式来确定初始质心,提出了基于Laplace 机制的 K-means 差分隐私算法;Dwork18等人提出了指数递减隐私预算分配策略的差分隐私K-means 算法。然而上述方法大多要求在传统的 K-means 算法的聚类过程添加 Laplace 噪声来实现差分隐私保护,存在以下两方面局限:(1)传统的 K-means 算法由于忽略了数据对象各属性对聚类结果发挥的不同聚类作用,同时随机选择初始质心,导致质心的质量良莠不齐,进而造成聚类效果不稳定的情况时常发生。(2)聚类数据集大多是多属性的数据样本,采用Laplace 机制处理多变量隐私问题时,会产生过多的噪声19,同时随着迭代次数的不断增加,质心趋于稳定,等量的噪声会增加隐私预算的开销以及引起质心较大的波动,进而影响聚类结果。为了解决上述问题,本文提出了一种基于Tsallis熵的 K-means 聚类近似差分隐私保护算法。针对问题 1,利用能度量系统有序化程度且能对不同的数据集均有较好的适应性的 Tsallis 熵20-22对样本属性赋权,并采用赋权欧氏距离作为相似性度量的依据,然后随机选取一个初始质心,计算其余数据样本到此质心的赋权欧氏距离以衡量其被选为初始质心的概率,最后采用轮盘法依次选出其余初始质心。针对问题 2,设计对迭代数越大的质心多分配隐私预算的策略,相对降低噪声量,提高信噪比。然后采用能更大程度地保留数据的可用性、更适合处理多维数据的高斯机制对迭代质心添加噪声,使算法满足(,)差分隐私保护。2 背景知识 2.1 Tsallis 熵 信息熵是对系统有序化的一种度量,但对于常见的幂律厚尾分布族23却不能通过信息熵来刻画24,而以1()nqiip x为例的依赖于概率幂的熵度量可以做到。因此,Tsallis 熵为代表的泛化熵被提出。定义定义 1.Tsallis 熵。Tsallis 熵通过一个可调节的参数 q 将其应用范围拓展到所谓的非拓展系统中25,具体定义形式如下:1()()ln()nqqiqiiSXp xp x (1)其中1ln()(1)/(1)qqxxq,1,0qx是logq 函数26,1,.,nXxx是一个随机变量()ip x是取值为ix的概率,Rq是一个可调节的参数,当1q 时,Tsallis熵()qSX退化为信息熵;当2q 时,Tsallis熵()qSX退化为基尼系数。2.2 近似差分隐私 2.2.1 近似差分隐私的理论基础近似差分隐私的理论基础 定义定义 2.差分隐私。设随机算法:nMXY。考虑任意两个只有一个条目不同的相邻数据集,nX XX,如果,对于所有相邻的,X X和所有的TY,满足:()()pr M XTe pr M XT (2)则M满足差分隐私(即满足纯差分隐私),其中其中M的选择是随机的,为隐私预算,与隐私保护水平呈负相关,当较小时,隐私保护能力较强,但此时噪声大,容易导致数据失真,反之亦然。在实际应用场景中,当对高维向量、矩阵等复杂数据进行处理时,为保证数据的可用性,往往要求噪声不会过大,因此Dwork等人提出了近似差分隐私27。定 义定 义3.(,)差 分 隐 私。设 随 机 算 法:nMXY。满足:()()pr M XTe pr M XT (3)则M是(,)差分隐私(即满足近似差分隐私),其中为松弛因子,且01。当越小时,隐私性损失量越微弱,当=0时,M的隐私保护能力退化为公式(2)。定义定义 4.敏感度。设:RnnfX。f的2敏感杨舒丹 等:基于 Tsallis 熵的近似差分隐私 K-means 算法 115 性是:22,max()()X Xf Xf X (4)其中,X X是相邻数据集。2.2.2 近似差分隐私的实现机制近似差分隐私的实现机制 高斯机制是实现近似差分隐私保护的主要方法,其通过向数据中添加符合高斯分布的随机变量达到隐私保护的目的。高斯分布2()N,的密度函数为:2221()()exp()22xp x (5)其中均值和方差分别为和2,该分布的可视化图像如图1所示:图 1 高斯分布 Figure 1 Gaussian distribution 定义定义 5.高斯机制。设:RnnfX。高斯机制定义为:1()()(,.,)kM Xf XYY (6)其中,iY是独立的2(0,)N高斯分布函数,而22222ln(1.25)/,可见,该噪声大小取决于查询函数的2敏感性、给定的隐私预算,以及松弛因子。在同样的隐私保护预算分配下,髙斯机制添加的噪声要小于拉普拉斯机制27,因此更大程度地保留了数据的可用性,适于处理多维数据。在算法实现中,松驰因子的大小也会大大影响模型的准确率。2.2.3 近似差分隐私的性质近似差分隐私的性质 性质性质 1.序列组合性。设1(,.,)kMMM是一个算法序列,其中iM是(,)ii 差分隐私,那么M满足11(,)kkiiii差分隐私。即:序列组合性允许对数据集进行多次查询操作,最终总的隐私预算为各个查询操作所消耗的隐私预算总和。3 基于 Tsallis 熵的 K-means 聚类差分隐私算法设计 本文建立了一个兼具隐私保护性和高可用性的差分隐私K-means聚类模型。图2是模型的概述,其中数据挖掘器不能直接访问原始数据库,但可以向差分隐私接口提交查询和相应的隐私预算,差分隐私接口将返回一个保持统计特征的不敏感数据。然后,数据挖掘者利用本文提出的基于Tsallis熵的K-means聚类近似差分隐私方案,根据查询结果构建差分隐私模型,并在不暴露原始数据集敏感信息的情况下发布该模型。图 2 满足差分隐私的数据挖掘框架概述 Figure 2 A system overview of differential privacy data mining 本文提出的基于Tsallis熵的K-means聚类近似差分隐私方案将围绕高质量的聚类结果和可靠的隐私保护两个方面展开。针对K-means算法随机选择初始质心,导致初始质心质量不稳定,影响聚类的准确率这一问题,本文设计了基于Tsallis熵对属性赋权的初始质心选择法对初始质心进行优化。在此基础上,针对在聚类过程中,攻击者恶意查询某个子类中用户信息这一隐私泄露现象,本文依据迭代质心的特点设计隐私预算划分策略,从信噪比的角度出发,解决迭代数越大的质心其信噪比相对越小的问题,然后向迭代质心添加高斯噪声,以满足(,)差分隐私,从而实现对用户敏感信息的保护。文中假定所有的数据源可信,但在进行数据挖掘过程中存在第三方攻击者的前提下,设计了基于Tsallis熵的K-means聚类差分隐私算法,目的是实现数据的可用且不可见,为了方便和形式化描述,将其命名为DPTK-means。DPTK-means算法的基本框架如图3所示:在图3中,当攻击者查询某个子类中用户信息时,反馈的查询结果不再是真实的用户聚类信息,而是经过特定的近似差分隐私机制操作后返回的随机扰动结果。本文采用高斯机制实现隐私保护,与不116 Journal of Cyber Security 信息安全学报,2023 年 7 月,第 8 卷,第 4 期 考虑隐私保护的情况相比,本文设计的K-means聚类模型是基于特定扰动的统计结果来构建。图 3 算法框架 Figure 3 The frame of algorithm 3.1 基于 Tsallis 熵的 K-means 算法 传统K-means算法选择初始质心具有随机性,容易导致算法陷入局部最优,难以获得稳定而精确的聚类结果。已有文献利用信息熵对聚类样本各属性赋权以提高聚类精度28,但并未考虑信息熵对不同数据集的适应性问题。Tsallis熵具有度量系统有序化程度,能适应不同类型数据等优点,本文将其用于计算各属性权重,通过对样本属性值进行适当缩放,以获得较优的聚类结果。因此设计基于Tsallis熵的改进K-means算法,重点考虑数据分布问题,为了方便和形式化描述,将其命名为TK-means。在具体实现过程中,围绕初始质心的选择这一问题进行展开:首先采用Tsallis熵法计算各属性的权重,再根据所设计初始质心算法得到优化后的k个初始质心,具体的算法框架如图3部分所示。3.1.1 确定属性权重确定属性权重 使用改进熵值法计算属性权重的目的是优化初始质心,从而提高聚类准确度。在统计学中,信息熵等指标的缺点在于没有一种指标总能在各种数据集上获得最好的效果,缺乏对数据集的适应性。本文采用Tsallis熵统一常用的度量指标,同时通过可调参数q来适应各种数据集,这种思想第一次在文献22中被提出,被用于决策树分类问题20-21。本文根据不同属性对聚类的作用不同,采用Tsallis熵法计算各属性的权重,以便为无序且不同规模的数据集聚类提供依据。采用Tsallis熵法确定属性权重后,本文将TK-means权值算法总结为如下:Step1:构造数据属性值矩阵。1111nmmnxxXxx (7)其中,n为样本总数,m为样本维数,ijx为第1,.,jm维属性所对应的第1,.,in个数据样本的属性值。Step2:计算样本的属性值比重。1/nijijijipxx (8)Step3:计算第j维属性的Tsallis熵。,11lnlnnqq jijqijiSppn (9)其中,q jS为衡量属性不纯度的指标,因此对于给定的j,q jS越小,样本的属性值之间的差值越大,该属性的聚类作用越大,属性越重要,反之成立。当属性值都相等时:,max1q jqSS,该属性的聚类效果为零。Step4:计算第j维属性的权值。,11(1)q jjmq jjSwS (10)Step5:计算赋权欧氏距离。21(,)()mwabjajbjjdxxwxx (11)该方法的优点是利用第j维属性的权值适当放大或缩小相应的属性值,使权值大的属性聚类作用更大,权值小的属性聚类作用更小,从而更能真实反映实际聚类时各属性发挥的作用。3.1.2 初始质心选择法初始质心选择法 为了避免K-means算法随机选择初始质心,导杨舒丹 等:基于 Tsallis 熵的近似差分隐私 K-means 算法 117 致每次聚类结果的差异较大。本文根据不同子类质心的相对距离与聚类效果成正比的原则,设计了新的初始质心选择策略,具体步骤如下:Step1:在数据集X中随机选择一个初始聚类质心()ic T29。Step2:计算数据集X中每个数据样本ix与当前已有的初始质心的最短赋权欧氏距离聚类中心最短距离:(,)wabdxx。Step3:计算数据样本ix被选为初始质心的概率:22(,()/(,()bjwaiwaixTpdxc Tdx c T,并利用轮盘法(各个个体被选中的概率与其适应度大小成正比)选出下一个质心。Step4:重复Step2,3直到选出k个初始质心。以上通过改善初始质心选择方式和利用Tsallis熵权值法的预选初始质心方式,目的是使得两两子类的质心的距离相对分散,类中的数据样本呈现相似的效果。因本文针对中心化差分隐私问题进行展开,即假定数据源可信,没有敌手从数据输入端对聚类结果进行干扰,隐私泄露只存在于数据挖掘过程中。因此算法的worst-case准确性将不会成为敌手攻击的缺口。此外,初始质心的选择只与数据域相关,与具体的数据无关,因此对聚类过程中的迭代质心添加高斯噪声进行隐私保护并不产生影响。3.2 满足近似差分隐私的 TK-means 算法 为保证聚类过程中,用户信息的隐私安全,引入差分隐私,通过添加噪声对结果进行扰动,使得攻击者在查询过程中无法区分从相邻数据集返回的结果。目前,构建满足差分隐私保护的K-means聚类模型需要解决以下两个关键性问题。(1)如何设计预算策略,以便于在将隐私保护水平进行量化表示的同时,减少预算的浪费。在聚类过程中,随着迭代次数不断增加质心趋于稳定,添加等量的噪声将引起质心较大的波动,会影响聚类结果。因此隐私预算设置和划分至关重要。本文从信噪比平衡的角度出发,依据迭代质心的特点设计隐私预算划分策略,即:当迭代次数增加时,为查询分配更大的隐私预算,以达到更小的扰动规模,可以在很大程度上保护数据集的真实信息。因此,本文在设计预算划分策略的重点就在于对迭代数越大的质心多分配隐私预算,以相对降低噪声量,提高信噪比。(2)如何实现对迭代质心的隐私保护,在实现用户数据不可见的同时,保证数据良好的可用性。通常数据隐私性和可用性呈现明显的负相关关系,而的差分隐私,往往需要付出更多的隐私代价。因此本文采用(,)差分隐私,通过对迭代质心添加高斯噪声,实现对个人隐私保护和整体统计趋势可用性之间的平衡。3.2.1 建立隐私适量预算分配规则建立隐私适量预算分配规则 如果将相同隐私预算产生的噪声加入到每次迭代生成的质心中,那么在不同的迭代中,扰动过程引起的信噪比明显会有相当大的不均衡性。因此,本文根据迭代次数H,为第一次迭代分配预算份额为1H,后续每次迭代的预算份额依次增大隐私预算的份额,相应为:11,.,112HH,以减少噪声的添加。在聚类过程中耗费的总隐私预算总份额为:111.112SHHH (12)其中,迭代次数为H。单位隐私预算为:0S (13)其中,为总隐私预算。第i次迭代所需的隐私预算为:0(1)iHi (14)3.2.2 迭代质心的隐私保护策略迭代质心的隐私保护策略 差分隐私保护的K-means聚类模型通过添加噪声对结果进行扰动,本文采用高斯机制实现对迭代质心的隐私保护。原因在于在同样的隐私保护预算分配下,髙斯机制对比拉普拉斯机制减少了噪声量。某类别数据样本的质心为:1()bibxTic TxT,其中iT表示iT中数据样本的个数。为了保护数据隐私,需对每个中心点加入一定量的噪声,加噪的方式是通过每一维度单独加噪的方式,得到加噪后的中心点,本文采用差分隐私添加噪声,所添加的噪声为一个随机常量,并未涉及乘除运算,因此并不会增加算法的时间复杂度,具体的证明过程参见3.3.1节。11(,.,)*()bibdxTiikxYYcTTY (15)其中d为样本维度。每一个iY服从独立同分布,根据高 斯 机 制 可 知,所 添 加 的 噪 声 满 足:222(0,2ln(1.25)iN,其中2为敏感度,其具体118 Journal of Cyber Security 信息安全学报,2023 年 7 月,第 8 卷,第 4 期 取值证明过程详见3.3.3节。因此本文所提出的DPTK-means算法设计流程是:首先根据所设计预选初始质心策略得到初始质心,然后对这些质心进行迭代优化,在迭代优化的过程中加入适应性的高斯噪声,得到最终的聚类结果。具体步骤如下所示:Step1:采用Tsallis熵法计算聚类数据样本各属性的权值。Step2:根据预选初始质心算法得到k个初始质心。Step3:对所有数据对象进行扫描,根据其与k个初始质心的欧氏距离将其分类到最近的聚类中。Step4:重新计算k个类的质心。Step5:根 据 迭 代 次 数 在 每 个 质 心 上 加 入222(0,2ln(1.25)/)iN的高斯噪声,其中i表示第i次迭代所需的隐私预算。Step6:重复执行Step3、4、5,直到完成算法要求的迭代次数时,循环终止。3.3 DPTK-means 算法有效性及安全性分析 3.3.1 算法复杂度分析算法复杂度分析 在DPTK-means算法设计中,有三个关键步骤,包括选择最优质心、隐私保护预算分配和噪声计算。已知样本总数为m,迭代次数为t。(1)在K-means聚类算法中,为了选择最优质心,需要根据样本到质心的距离进行最优簇划分,从理论上来说该划分过程的计算复杂度为为()O mkt,其中k为质心个数,一般情况下,k tm。(2)隐私预算分配的复杂度是(1)O,分配中只需要对数据样本做常数操作,而不涉及乘除运算。因此,隐私预算的分配并不会增加算法复杂度。(3)与非隐私保护的K-means算法相比,在计算迭代质心时,噪声估计步骤带来了额外的计算量。事实上,未添加噪声的迭代质心的计算也会产生大量的运算,而在这基础上增加简单的常数计算,并不会增加算法复杂度,这也正是差分隐私区别于其他传统加密技术的优势所在。因此,相对于非隐私保护的K-means聚类算法而言,DPTK-means算法的效率不会下降。综上分析,DPTK-means算法的计算复杂度与非隐私保护K-means聚类算法大致相同,即()O mkt,因此,本文提出的DPTK-means算法能保证与非隐私保护情况下相同量级的计算复杂度。3.3.2 算法安全性分析算法安全性分析 算法中的随机函数若能够提供满足高斯分布的噪声,则可以为查询结果提供近似差分隐私保护。本文提出的DPTK-means算法通过实现高斯机制,为聚类结果提供了近似差分隐私保护,即在聚类过程中添加适当的满足高斯分布的噪声到质心。安全性证明过程如下:对于每次迭代过程,每个数据点只会影响d个求和查询与一个计数查询,因此本文将一次迭代的输出看做1d维。由于对每个数据点做了,r r的范围限制,因此全局敏感度为221d r 。设单次迭代的查询函数为:ddfXXN,dX XX是待聚类数据中的一对相邻数据集,这两个数据集分别被划分到不同的簇:*1(),.,()kc Tc T和*1(),.,()kcTcT,其 中 存在*()()jjc TcT。设*()()jjf c Tf cTv。考虑噪声幅值x(0,N 2),则隐私损失随机变量6分布为:222222*22222lnln2jjjjxjjjx vpr M cTf cTxpr M cTf cTxx vvee (16)因此在一次迭代过程中,隐私损失随机变量的分布均值为222jv,方差为22jv。为了方便引入变量(0,1)ZN,则隐私损失随机变量为:22222Z,通过证明隐私损失随机变量的绝对值超过i的概率最多为i来证明(,)ii 差分隐私。因此,在一次迭代过程中超过i的概率重写为:222pr Z,将其上界定为:2pr Ztt (17)其中2 t,当pr Zt时,也符合标准高斯尾部 界 限 的,由 于22222ln(1.25)/i,因 此,ipr Zt,从而证明了每次迭代过程满足杨舒丹 等:基于 Tsallis 熵的近似差分隐私 K-means 算法 119 (,)ii 差分隐私。根据(,)ii 差分隐私的序列组合性可知,整个聚类过程满足11(,)kkiiii差分隐私。4 实验及分析 本节通过实验对提出的DPTK-means算法进行验证分析,实验采用Python进行编程实现,物理环境为:处理器Intel(R)Core(TM)i7-9700 CPU 3.00GHz;内存64.0 GB;操作系统Windows 10。4.1 实验数据集及评价指标 实验中采用UCI数据库30中的四个真实聚类数据集:3D-roadNetwork、Adult、Wine-quality、Statlog。以3D-roadNetwork数据集为例,包含434,874个实例,其形式为ID,经度,纬度,海拔。其余三个数据集的信息如表1所示。在以下数据集上的实验表明了本文所提出的算法在性能上的提升和在差分隐私约束下的有效性。表 1 数据集 Table 1 Datasets 数据集 样本数 维数(属性数)3D-roadNetwork 434874 4 Adult 48841 6 Wine-quality 4898 12 Statlog 946 18 在本文的实验中,使用以下两个指标来评估性能:标准化互信息(Normalized Mutual Information简称NMI)31和相对误差(Relative Error简称RE)15。NMI是评价性能的常用指标。NMI值越接近于1,意味着算法结果与标准结果之间的相似度越高,聚类质量越好。RE测量估计的质心相对于未实现隐私保护K-means的实际质心之间的误差。RE值越小,结果越相似,差分隐私聚类的可用性越高。具体来说,给定原始质心()ic T和扰动质心*()ic T所在簇,平均扰动计算为:*()()1()iiiic Tc Tc TkT (18)4.2 对比算法 为了评估本文所提出的DPTK-means算法的有效性,将其性能与最常用的几个K-means聚类算法进行比较:K-means:传统K-means聚类算法。DPK-means:在传统K-means聚类算法的基础上,为每次迭代均添加等量的拉普拉斯噪声。EDPK-means16:传统K-means聚类算法,在每次迭代中添加拉普拉斯噪声,并使用指数递减的隐私预算分配。4.3 实验结果与分析 4.3.1 TK-means 算法聚类性能分析算法聚类性能分析 实验实验1:各属性的Tsallis熵权值分布。本次实验的目的是分析各属性Tsallis熵权值对聚类作用的影响程度。计算数据集各属性对应的Tsallis熵权值如图4所示,为了简单方便,当固定q时,取2q。在图4中,横坐标分别代指四个数据集的属性集,以3D-roadNetwork数据集为例,其四个属性分别为:ID,经度,纬度,海拔。通过图(a)中各属性的Tsallis熵权值可知,属性2的权值为0.288,而属性4的权值为0.21,同比下降了7.8%。由此可以看出:在聚类的过程中,同一数据样本的不同属性的聚类作用存在显著差异,因此在进行聚类时应加以区分,这正是传统K-means算法聚类结果常常不理想的原因之一。实验实验2:TK-means算法的有效性分析。本次实验的目的是对比TK-means算法和K-means算法的聚类效果,本文采用NMI评价指标对TK-means算法和K-means算法的聚类质量进行评估,实验结果是取2q 时,在10次实验后统计聚类情况计算平均值得到。具体结果如图5所示:图5展示了,两种算法在不同数据集上的实验结果。在Adult数据集上聚类时,当5k聚类效果达到最佳,聚类评价指标NMI由0.821提高到0.893;在Statlog数据集上聚类时,当4k聚类效果达到最佳,聚类评价指标NMI由0.644提高到0.705;在Wine-quality数据集上聚类时,当2k聚类效果达到最佳,聚类评价指标NMI由0.82提高到0.9;在3D-roadNetwork数据集上观察k从1到12的聚类结果的变化情况,不难发现TK-means算法对比传统的K-means算法聚类准确率在整体趋势上均有所提升,当9k时K-means算法的聚类结果达到最优0.725NMI,但此时基于Tsallis熵改进的K-means算法的0.778NMI,同比提高了5.3%,具体的可视化分布如图6所示,其他三个数据集可视化效果类似。当12k时基于Tsallis熵改进的K-means算法的聚类结果达到最优0.8NMI,意味着算法结果与标准结果之间的相似度较高,这充分说明了文中TK-means算法的有效性。120 Journal of Cyber Security 信息安全学报,2023 年 7 月,第 8 卷,第 4 期 图 4 各属性 Tsallis 熵权值 Figure 4 Attribute Tsallis entropy weight 图 5 聚类结果 Figure 5 The clustering results 在图6中横纵坐标1,2x x表示数据对象分布范围,通过观察图6可知,在3D-roadNetwork数据集上,当9k时(图中红色圆点为质心k的数目),在K-means算法进行聚类的结果中(图6左),存在两个聚类质心有相距较近的问题,这是由于选择初始质心的随机性所导致。而在TK-means算法进行聚类的结果中(图6右),两两子类的质心的距离相对分散,类内中的数据样本呈现均匀分布的效果。杨舒丹 等:基于 Tsallis 熵的近似差分隐私 K-means 算法 121 图 6 聚类结果可视化分布 Figure 6 Visual distribution 实验实验3:TK-means算法对不同数据集的适应性分析。此次试验目的是为了全面评估Tsallis熵中参数q的影响,本实验中q在0.1,10.0的范围内以0.1的步长遍历整个区间。对于每个选定的q,本文通过在TK-means算法上的聚类效果,对其性能进行评估,此处以3D-roadNetwork数据集在9k时,不同值参数q对 Tsallis 熵分裂准则的影响的情况为例,其实,其他数据集也表现出类似的趋势。实验的迭代次数最大值为100,最终取10次实验的平均值,图7展示了具体的聚类结果。图 7 参数 q 的影响 Figure 7 The influence of parameter q 图7直观展示了TK-means算法在3D-road-Network数据集上选用不同参数q对聚类结果的影响。显然NMI对q的变化很敏感,例如:当1.8q时,3D-roadNetwork数据集的聚类质量最好,并不是当1q时,Tsallis熵()qSX退化为信息熵,也不是当2q时,Tsallis熵()qSX退化为基尼系数,从而体现Tsallis熵通过可调参数q以适应各种数据集。本文通过选择不同的q实现不同的目标。总之,实验结果表明参数q的确对聚类准确率有影响,这也反映了TK-means算法的适应性和灵活性。4.3.2 差分隐私约束下的有效性差分隐私约束下的有效性 对实验过程中选用的参数做简要介绍。首先,四个数据集聚类k值的选择,通过实验2可知四个数据集的最佳聚类k值,具体信息如图表2所示:表 2 最佳聚类数 Table 2 Optimal cluster number 数据集 k 3D-roadNetwork 12 Adult 5 Wine-quality 2 Statlog 4 其次针对不同的,由于噪声的随机性,因此在以上三个算法对每个执行10次,最终取评价指标的平均值。最后由于两个对比算法涉及松弛因子,因此本次实验中对于DPTK-means算法取0.01。实验实验4:隐私保护预算对聚类结果的影响。本次实验的目的是对比分析实现隐私保护后各个算法在数据集上的聚类结果的可用性和准确性。采用RE评价指标对DPTK-means算法和两个对比算法的质心偏离情况进行评估,采用NMI评价指标对三个算法的聚类质量进行评估。通过观察随着隐私预算的变化,RE值和NMI值的分布情况来判断噪声对算法聚类结果的影响程度,实验结果分别如图8、图9所示:由图8可以看出,在不同的数据集上,DPTK-means算法的聚类结果的RE值要低于两个对比算法,这意味着DPTK-means算法的聚类结果更优。通过文章第二节介绍差分隐私的定义可知,当隐私预算 122 Journal of Cyber Security 信息安全学报,2023 年 7 月,第 8 卷,第 4 期 图 8 质心的偏离情况 Figure 8 Deviation of the center of mass 图 9 满足差分隐私条件下的聚类准确性 Figure 9 Clustering accuracy under the condition of differential privacy 越小时,添加的噪声越多,从而隐私保护的程度越高。随着隐私预算的增加,DPTK-means的RE评价曲线得到了较明显的下降,说明在较少的隐私预算下DPTK-means可以获得更高的可用性。与四种不同的数据集相比发现,DPTK-means比两种对比算法更能适应高维数据。具体来说,在4维数据集杨舒丹 等:基于 Tsallis 熵的近似差分隐私 K-means 算法 123 3D-roadNetwork(图(a)和6维数据集Adult上(图(b),DPTK-means与EDPK-means具有相似的隐私保护性能。然而当隐私预算增