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

利用K-means算法对用户信息进行聚类时,存在隐私泄露的风险。差分隐私保护技术可提供严格的隐私保护,但目前大多数满足差分隐私的K-means算法在处理多维数据时,存在随机选择质心和噪声添加不均衡的问题,因而导致聚类结果不理想。为此,本文提出一种基于Tsallis熵的近似差分隐私K-means算法。针对质心选择的随机性问题,提出Tsallis熵对属性赋权的策略来优化对象间的欧氏距离,然后对比各对象到唯一随机初始质心的赋权欧式距离来确定其余初始质心,使算法在减少随机选择初始质心的同时,提高模型准确率;在此基础上,针对噪声添加不均衡的问题,提出一种能够平衡信噪比的隐私预算分配策略,然后对迭代质心加入高斯扰动,使算法在不增加计算复杂度的情况下满足(ε,δ)-差分隐私保护,同时提升扰动结果的准确性;最后在四个真实数据集上对算法进行有效性评价。实验结果表明,所提出的算法能够在保证用户隐私安全的同时实现高效用的聚类。

基于差分隐私的K-means算法优化研究综述

差分隐私K-means算法(Differential Privacy K-means Algorithm,DP K-means)作为一种基于差分隐私技术的隐私保护数据挖掘(Privacy Preserving Data Mining,PPDM)模型,因简单高效且可保障数据的隐私而备受研究者的关注。文中首先阐述了差分隐私K-means算法的原理、隐私攻击模型,以分析算法的不足。然后从数据预处理、隐私预算分配、聚簇划分等3个角度讨论分析DP K-means算法改进研究的优缺点,并对研究中的相关数据集和通用评价指标进行了总结。最后指出DP K-means算法改进研究中亟待解决的挑战性问题,并展望了DP K-means算法的未来发展趋势。

一种基于改进差分进化的K-Means聚类算法研究

为改进传统K-Means聚类算法中因随机选取初始聚类中心而导致聚类结果不稳定且效率低的缺点,提出一种基于改进差分进化的K-Means聚类算法(AGDE-KM)。首先,设计自适应操作算子来提升算法前期的全局搜索能力和后期的收敛速度;其次,设计多变异策略并引入权重系数,在算法的不同进化阶段发挥不同变异策略的优势,平衡算法的全局和局部搜索能力,加快算法的收敛速度;最后,提出一种基于当前种群最佳个体的高斯扰动交叉操作,为个体提供更优进化方向的同时保持种群在“维”上的多样性,避免算法陷入局部最优。将算法停止执行时输出的最优解作为初始聚类中心替代传统K-Means随机选取的聚类中心。将提出算法在UCI公共数据库中的Vowel、Iris、Glass数据集和合成数据集Jcdx上进行对比实验,误差平方和(SSE)相对于传统K-Means分别减小5.65%、19.59%、13.31%、6.1%,聚类时间分别减少83.03%、81.33%、77.47%、92.63%。实验结果表明,提出的改进算法具有更快的收敛速度和更好的寻优能力,显著提升了聚类的效果、效率和稳定性。

应用BWP指标的差分隐私保护k-means算法

差分隐私是一种基于噪声扰动的隐私保护技术,针对差分隐私保护下噪声导致的聚类中心点偏移较大的问题,提出了一种基于BWP(between-within proportion)指标的差分隐私k-means算法。算法将聚类有效性评价指标BWP引入到隐私预算分配过程中,对传统隐私预算分配进行加权处理,在一次迭代中为不同密度分布的簇分配不同的隐私预算,从而添加不同的随机噪声。理论分析表明新算法满足ε-差分隐私保护。基于四个标准数据集对新算法进行了实验,实验结果表明,在聚类结果的可用性以及算法的稳定性上新算法具有优势。

基于拉普拉斯机制的差分隐私保护k-means++聚类算法研究

k-means++聚类算法是为了解决k-means聚类算法的准确度受其初始中心点选取的影响较大的问题而提出的,在聚类过程中,需要对相关的隐私数据提供保护。差分隐私模型定义了一种具有最大背景知识假设的攻击模型,并且能对隐私保护强度进行量化分析。文章提出一种基于拉普拉斯机制的差分隐私保护k-means++聚类算法(DPk-means++聚类算法),在初始化选取中心点和迭代求均值中心点的过程中,分别根据拉普拉斯机制添加噪声,解决了k-means++聚类算法随机选取初始化中心点隐私泄露的问题和迭代求簇心隐私泄露问题。通过实验分别对隐私预算动态变化对比及聚类准确性结果进行分析,DPk-means++聚类算法能够在隐私预算参数范围内且保证聚类准确性的前提下,实现对数据隐私提供不同级别的保护。

基于距离与误差平方和的差分隐私K-means聚类算法

K-means算法具有简单、快速、易于实现等优点,被广泛应用于数据挖掘领域,但在聚类过程中容易造成隐私泄露。差分隐私对隐私保护做了严格定义,且能够对隐私保护量化分析。为解决差分隐私保护中K-means聚类算法在初始中心点选择上具有盲目性而造成聚类可用性低的问题,文章提出一种BDPK-means聚类算法,该算法利用距离与簇内误差平方和的方法选取合理的初始中心点进行聚类。理论分析证明,该算法满足ε-差分隐私。实验证明,相同条件下与现有DPK-means算法相比,BDPK-means算法可提高聚类的可用性。

Spark框架下支持差分隐私保护的K-means++聚类方法

针对差分隐私聚类算法在处理海量数据时其隐私性和可用性之间的矛盾,提出了一种分布式环境下支持差分隐私的K-means++聚类算法.该算法通过内存计算引擎Spark,创建弹性分布式数据集,利用转换算子及行动算子操作数据进行运算,并在选取初始化中心点及迭代更新中心点的过程中,通过综合利用指数机制和拉普拉斯机制,以解决初始聚类中心敏感及隐私泄露问题,同时减少计算过程中对数据实施的扰动.根据差分隐私的特性,从理论角度对整个算法进行证明,以满足ε-差分隐私保护.实验结果证明了该方法在确保聚类结果可用性的前提下,具备出色的隐私保护能力和高效的运行效率.

基于k-means的不同维度隐私数据差分聚类方法仿真

不同维度隐私数据聚类时,若不能及时在聚类过程保护数据隐私,容易出现数据隐私泄露问题。为有效提升数据聚类时的隐私安全,提出一种基于k-means的不同维度隐私数据差分聚类方法。对数据杂乱噪声实施去除,利用CS重构算法重构出损伤数据原始信号,实现数据的损伤修复;针对k-means聚类算法聚类中心选取时数据易泄露问题,利用差分算法k-means聚类算法实施优化处理,结合拉普拉斯机制在初始聚类中心中加入有规律的人工规整噪声,有效提升数据的安全保护效果,实现数据的有效聚类。实验结果表明,使用上述方法开展隐私数据聚类时,聚类效果好、性能高。

一种改进的面向差分隐私保护的k-means聚类算法

笔者介绍了差分隐私保护的研究背景、差分隐私保护的基本原理和方法,分析了k-means算法的隐私泄露问题。针对传统面向差分隐私保护k-means算法存在簇中心选取随机性导致聚类可用性较低的问题,提出一种指数加噪机制与密度估计相结合的方法,选取初始聚类中心,从而保证初始中心挑选的合理性,保障样本数据的隐私性。实验结果表明,提出的新方法可以显著提高聚类结果的可用性。

一种差分隐私K-means聚类算法的隐私预算分配方案

差分隐私K-means聚类算法因其能很好地兼顾数据可用性和数据隐私安全,而得到了广泛地关注和研究。目前,在许多对差分隐私K-means聚类算法的研究中,都从K-means聚类算法的初始中心点的选择上做改进来提高数据的可用性,而很少关注隐私预算的分配问题对聚类结果带来的影响。传统的隐私预算分配方法可能在K-means算法后期的迭代更新质心的过程中引入大量的噪声而造成数据聚类效果差的问题。为了解决这个问题,提出一种结合三分法和等差数列的隐私预算分配方案。该方法在差分隐私K-means聚类算法中,保证每次迭代更新质心的过程中引入的噪声不会引起质心变形,且前期使用三分法分配较大的预算,而在后期使用等差递减的方式,分配隐私预算使隐私预算能在设定的迭代次数中用尽。实验证明,该方法在相同条件下能提高差分隐私K-means聚类算法的可用性。

一种改进的基于差分隐私的k-means聚类算法

聚类分析是数据挖掘和机器学习的一个重要分支,应用范围广,但在聚类分析过程中大量敏感信息的泄露对用户构成威胁。因此,在聚类分析过程中实现隐私保护至关重要。传统基于差分隐私(DP)的k-means聚类算法由于存在盲目选择初始中心点、对异常点敏感度较高等问题,导致在保护数据隐私时,出现聚类可用性较低的情况。针对该问题提出一种改进的基于差分隐私保护的(IDP)k-means聚类算法以提高聚类可用性,并进行理论分析和对比实验。理论分析表明,该算法满足ε-差分隐私;仿真实验结果表明,在同一隐私预算下,k-means算法改进后在聚类可用性上优于其它差分隐私k-means聚类算法,在同一数据集与同一隐私参数下,改进k-means算法在数据可用性方面比传统算法提高了将近5个百分点。

基于改进的k-means差分隐私保护方法在位置隐私保护中的应用

针对k-means差分隐私聚类结果的可用性较差的问题,依据LBS的数据采集特点对k-means算法进行了改进.仿真实验证明:在LBS隐私保护方面,提出的改进k-means聚类方法在聚类结果的匿名性方面相对普通差分隐私k-means聚类方法有一定程度的提高.

基于相对熵和K-means的形状相似差分隐私轨迹保护机制

为解决绝大多数研究未充分考虑位置对隐私预算的敏感程度以及轨迹形状带来的影响,使发布的轨迹可用性较差的问题,提出了基于相对熵和K-means的形状相似差分隐私轨迹保护机制。首先,根据地理空间的拓扑关系,利用相对熵计算真实位置对隐私预算的敏感程度,设计了位置敏感的隐私级别实时计算算法,并与差分隐私预算结合建立了一个新的隐私模型。其次,通过K-means算法对发布位置进行聚类,得到与真实位置方向最相似的发布位置集合,并引入Fréchet距离衡量发布轨迹与真实轨迹的相似性,提升发布轨迹的可用性。通过对真实数据集的实验表明,所提轨迹保护机制与其他方法相比在轨迹可用性方面有明显的优势。

PINQ下K-means的差分隐私保护研究

差分隐私保护是Dwork提出的基于数据失真技术的一种新的隐私保护模型,由于其克服了传统隐私保护需要背景知识假设和无法定量分析隐私保护水平的缺点,近年来迅速成为隐私保护领域研究热点。PINQ是最早实现差分隐私保护的交互型原型系统。介绍了差分隐私保护相关理论基础,分析了PINQ框架的实现机制。以PINQ中差分隐私保护下K-means聚类实现为例,研究了差分隐私在聚类中的应用。仿真实验表明,在不同的隐私预算下,实现的隐私保护级别也不同。

改进萤火虫群算法协同差分隐私的干扰轨迹发布

针对历史轨迹加噪发布干扰轨迹时数据集的冗余问题和轨迹形状相似带来的隐私泄露风险,提出轨迹数据先约简后泛化再进行差分隐私加噪的基于改进萤火虫群优化求解的干扰轨迹发布保护机制(IGSO-SDTP)。首先,基于位置显著点约简历史轨迹数据集;其次,结合k⁃匿名和差分隐私对简化后的轨迹数据集分别进行泛化和加噪;最后,设计了兼顾距离误差和轨迹相似性的加权距离,并以加权距离为评价指标,基于改进萤火虫群优化(IGSO)算法求解加权距离小的干扰轨迹。在多个数据集上的实验结果表明,与RD(Differential privacy for Raw trajectory data)、SDTP(Trajectory Protection of Simplification and Differential privacy)、LIC(Linear Index Clustering algorithm)、DPKTS(Differential Privacy based on K-means Trajectory shape Similarity)相比,IGSO-SDTP方法得到的加权距离分别降低了21.94%、9.15%、14.25%、10.55%,说明所提方法发布的干扰轨迹可用性和稳定性更好。

基于不可信服务器的差分隐私混合推荐算法

大多数现有的隐私保护推荐算法是针对显式反馈行为数据的单一推荐算法,且仅适用于可信服务器场景。针对以上不足,提出了一个新的隐私保护推荐系统框架。框架利用用户隐式反馈行为数据,在客户端考虑数值敏感度和数据分布不同,使用LCF-VDP(local collaborative filtering-value differential privacy)机制扰动原始数据并上传到服务器;服务器混合两种算法的相似度,最终选择topk混合相似度发送给每个用户设备,在每个用户设备中进行预测评分计算并推荐。仿真结果表明,提出的方法可以根据不同的需求来选择合适的参数,以达到最佳推荐效果,且LCF-VDP在各种隐私预算下比传统的扰动机制效用更好。

基于差分进化的加权k-means算法研究

针对处理大样本数据时聚类算法的局限性,以及k-means算法受初始聚类中心和异常数据的限制,聚类结果不稳定的问题,本文提出了基于差分进化的加权k-means算法,优先选择初始聚类中心,采用差分进化算法,根据样本对聚类分析影响程度不同,设计加权欧氏距离,来减少异常点带来的不利影响,从而获得稳定的聚类结果。实验结果表明,该算法选择的初始聚类中心更接近最终聚类中心,提高了算法的计算效率。

横向联邦学习中差分隐私聚类算法

聚类分析能够挖掘出数据间隐藏的内在联系并对数据进行多指标划分,从而促进个性化和精细化运营。然而,数据孤岛造成的数据碎片化和孤立化严重影响了聚类分析的应用效果。为了解决数据孤岛问题的同时保护相关数据隐私,提出本地均分扰动联邦K-means算法(ELFedKmeans)。针对横向联邦学习模式,设计了一种基于网格的初始簇心选择方法和一种隐私预算分配方案。在ELFedKmeans算法中,各站点联合协商随机种子,以较小的通信代价生成相同的随机噪声,保护了本地数据的隐私。通过理论分析证明了该算法满足差分隐私保护,并将该算法与本地差分隐私K-means(LDPKmeans)算法和混合型隐私保护K-means(HPKmeans)算法在不同的数据集上进行了对比实验分析。实验结果表明,随着隐私预算不断增大,三个算法的F-measure值均逐渐升高;误差平方和(SSE)均逐渐减小。从整体上看,ELFedKmeans算法的F-measure值比LDPKmeans算法和HPKmeans算法分别高了1.7945%~57.0663%和21.2452%~132.0488%;ELFedKmeans算法的Log(SSE)值比LDPKmeans算法和HPKmeans算法分别减少了1.2042%~12.8946%和5.6175%~27.5752%。在相同的隐私预算下,ELFedKmeans算法在聚类质量和可用性指标上优于对比算法。

面向Stacking算法的差分隐私保护研究

为解决同质集成学习算法对噪声更敏感,难以兼顾较好的预测性能和有效的隐私保护这一问题,提出一种基于差分隐私的DPStacking算法,将异质Stacking算法与差分隐私技术相结合,以优化算法的隐私保护和预测性能。但是,由于Stacking算法的低层和高层模型都可以由不同的学习器构成,若对某个具体学习器设计隐私预算分配方案来提供差分隐私保护,该方案往往无法适用于由任意基学习器和元学习构成的Stacking算法。基于此,设计了一种基于元学习器的隐私预算分配方案,此方案根据皮尔逊相关系数及差分隐私并行组合的特性为元学习器输入的不同构成体分配不同的隐私预算。通过理论与实验验证,DPStacking算法符合ε-差分隐私保护,与基于差分隐私的随机森林算法(DiffRFs)、Adaboost算法(DP-AdaBoost)、XGBoost算法(DPXGB)相比,能有效保护数据隐私的同时拥有更好的预测性能,并较好地解决了单一同质集成学习算法对噪声更加敏感的问题。

一类自适应梯度裁剪的差分隐私随机梯度下降算法

梯度裁剪是一种防止梯度爆炸的有效方法,但梯度裁剪参数的选取通常对训练模型的性能有较大的影响。为此,本文针对标准的差分隐私随机梯度下降算法进行改进。首先,提出一种自适应的梯度裁剪方法,即在传统裁剪方法基础上利用分位数和指数平均策略对梯度裁剪参数进行自适应动态调整,进而提出一类自适应梯度裁剪的差分隐私随机梯度下降算法。其次,在非凸目标函数的情况下对提出的自适应算法给出收敛性分析和隐私性分析。最后,在MNIST、Fasion-MNIST和IMDB数据集上进行数值仿真。其结果表明,与传统梯度裁剪算法相比,本文提出的自适应梯度裁剪算法显著提高了模型精度。