基于聚类的数据敏感属性匿名保护算法*

为了防止数据敏感属性的泄露,需要对数据敏感属性进行匿名保护。针对l-多样性模型当前已提出的算法大多是建立在概念层次结构的基础上,该方法会导致不必要的信息损失。为此,将基于属性泛化层次距离KACA算法中的距离度量方法与聚类结合,提出了一种基于聚类的数据敏感属性匿名保护算法。该算法按照l-多样性模型的要求对数据集进行聚类。实验结果表明,该算法既能对数据中的敏感属性值进行匿名保护,又能降低信息的损失程度。     

最优聚类的k-匿名数据隐私保护机制

基于聚类的k-匿名机制是共享数据脱敏的主要方法,它能有效防范针对隐私信息的背景攻击和链接攻击。然而,现有方案都是通过寻找最优k-等价集来平衡隐私性与可用性.从全局看,k-等价集并不一定是满足k-匿名的最优等价集,隐私机制的可用性最优化问题仍然未得到解决.针对上述问题,提出一种基于最优聚类的k-匿名隐私保护机制.通过建立数据距离与信息损失间的函数关系,将k-匿名机制的最优化问题转化为数据集的最优聚类问题;然后利用贪婪算法和二分机制,寻找满足k-匿名约束条件的最优聚类,从而实现k-匿名模型的可用性最优化;最后给出了问题求解的理论证明和实验分析.实验结果表明该机制能最大程度减少聚类匿名的信息损失,并且在运行时间方面是可行有效的.     

抵制轨迹相似性攻击的轨迹（k，e） 匿名算法

针对轨迹匿名集中轨迹间的相似性过高导致的轨迹隐私泄露问题,提出抵制轨迹相似性攻击的轨迹(k,e)-匿名算法。该算法在预处理过程中,采用轨迹同步化处理方法减少信息损失;生成匿名集时,将轨迹斜率作为轨迹数据的敏感值,选择至少k条不同轨迹斜率的轨迹来满足轨迹k-匿名,并要求每个类中轨迹斜率差异值至少为e,以防止集合中轨迹的斜率相似性过高而导致隐私泄露。实验结果表明,该算法可以有效抵制轨迹相似性攻击,在减少信息损失的同时增强了轨迹数据可用性,更好地实现了轨迹隐私保护。     

MA-Datafly:一种支持多属性泛化的k-匿名方法

Datafly算法是数据发布环境下保护数据隐私的一种k-匿名方法,实现k-匿名时只对准标识符属性集中属性值种类最多的属性进行归纳。当准标识符属性集中只有一个属性的取值多样而其他属性取值具有同质性时,该算法可行。实际应用中数据的取值却往往不具有这种特点。针对这个问题,提出一种自底向上的支持多属性归纳k-匿名算法,并对该算法进行实验测试,结果表明该算法能有效降低原始数据的信息损失并能提高匿名化处理效率。     

一种基于子空间划分的最优k-匿名动态规划算法

目前大部分k-匿名算法未能有效兼顾算法效率和发布数据的可用性.从子空间划分的角度研究基于空间多维划分的最优k-匿名问题,发现所有可能的子空间数量远小于所有可能的划分数量,并从理论上分析基于子空间划分的最优k-匿名问题具有最优子结构性质,从而设计出基于子空间划分的隐私保护最优k-匿名动态规划算法k-ASPDP.实验对算法k-ASPDP发布数据的可用性及算法效率与同类算法进行比较分析.实验结果表明,算法k-ASPDP是有效可行的.     

隐私保护k-匿名算法研究

隐私保护已成为个人或组织机构关心的基本问题,k-匿名是目前数据发布环境下实现隐私保护的主要技术之一。鉴于多数k-匿名方法采用泛化和隐匿技术,严重依赖于预先定义的泛化层或属性域上的全序关系,产生很高的信息损失,降低了数据的可用性,提出了一种基于聚类技术的k-匿名算法。实验结果表明,该算法在保护隐私的同时,提高了发布数据的可用性。     

基于有损连接的个性化隐私保护

数据表的k-匿名化(k-anonymization)是数据发布环境下保护数据隐私的一种重要方法,在此基础上提出的(,)-匿名模型则是有效的个性化隐私保护方法,泛化/隐匿是实现匿名化的传统技术,然而该技术存在效率低,信息损失量大等缺陷。针对上述问题,引入有损连接的思想,提出了基于贪心策略的(,)-匿名聚类算法,该方法通过准标识符属性和敏感属性间的有损连接来保护隐私数据。实验结果表明,与泛化/隐匿方法相比,该方法在信息损失量和时间效率上具有明显的优势,可以获得更好的隐私信息保护。     

一种基于K-匿名聚类的可穿戴设备数据重发布方法

近年来,可穿戴设备被广泛地被应用于日常生活。用户量增加造成的可穿戴设备数据重发布是导致隐私泄漏的一个重要原因。为此,数据匿名化重发布方法受到了广泛关注。然而,现有的数据匿名化重发布方法存在两个方面的不足:一方面,现有的数据匿名化重发布算法可能会造成严重的信息损失或用户隐私数据的泄漏;另一方面,现有的数据匿名化重发布算法在兼顾保护用户隐私和减少信息损失的情况下会造成较高的发布成本。为了兼顾隐私安全和数据可用性,并且提高数据重发布算法的效率,结合可穿戴设备自身的特点,提出基于聚类的数据匿名化重发布算法,该算法直接对增量数据进行基于聚类匿名化操作,使数据匿名化重发布更为高效。此外,在数据量较大的应用场景中,基于聚类的数据匿名化重发布算法可以有效减少信息损失。实验结果表明,基于聚类的数据匿名化重发布算法能够在保证用户隐私安全的前提下减少信息的损失并且提高执行效率。     

基于个人隐私约束的k-匿名模型

传统的数据发布隐私保护研究假设数据发布者持有的电子化数据是原始的、未经过处理的数据.k-匿名模型提出之后,许多匿名化模型主要针对敏感属性提出了各种约束.然而,隐私保护中另一个重要原则是个人的隐私自治.实际应用场景中,个人有选择和决定隐私约束的权利.用户所提供的数据很可能是不完整的或预先经过处理的.围绕非敏感属性上的约束条件定义了一种新颖的匿名化模型:基于个人隐私约束的k-匿名;并设计了一种自上而下的启发式匿名化算法.实验表明,该算法能很好地处理基于个人隐私约束的k-匿名问题,并具有较少的信息损失.     

PPDM中面向k-匿名的MI Loss评估模型

隐私保护数据挖掘（PPDM）利用匿名化等方法使数据所有者在不泄露隐私信息的前提下,安全发布在数据挖掘中有效可用的数据集。k-匿名算法作为PPDM研究使用最广泛的算法之一,具有计算开销低、数据形变小、能抵御链接攻击等优点,但是在一些k-匿名算法研究中使用的数据可用性评估模型的权重设置不合理,导致算法选择的最优匿名数据集在后续的分类问题中分类准确率较低。提出一种使用互信息计算权重的互信息损失（MI Loss）评估模型。互信息反映变量间的关联关系,MI Loss评估模型根据准标识符和标签之间的互信息计算权重,并通过Loss公式得到各个准标识符的信息损失,将加权后的准标识符信息损失的和作为数据集的信息损失,以弥补评估模型的缺陷。实验结果证明,运用MI Loss评估模型指导k-匿名算法能够明显降低匿名数据集在后续分类中的可用性丢失,相较于Loss模型和Entropy Loss模型,该模型分类准确率提升了0.73%~3.00%。     

面向缺失数据的数据匿名方法

在数据发布过程中,为了防止隐私泄露,需要对数据的准标识符属性进行匿名化,以降低链接攻击风险,实现对数据所有者敏感属性的匿名保护.现有数据匿名方法都建立在数据无缺失的假设基础上,在数据存在缺失的情况下会直接丢弃相关的记录,造成了匿名化前后数据特性不一致.针对缺失数据匿名方法进行研究,基于k-匿名模型提出面向缺失数据的数据匿名方法KAIM(k-anonymity for incomplete mircrodata),在保留包含缺失记录的前提下,使在同一属性上缺失的记录尽量被分配到同一分组参与泛化.该方法将分组泛化前后的信息熵变化作为距离,基于改进的k-member 算法对数据进行聚类分组,最后通过基于泛化层次的局部泛化算法对组内数据进行泛化.实际数据集的大量实验结果表明,KAIM 造成信息缺损仅为现有算法的43.8%,可以最大程度地保障匿名化前后数据特性不变.     

An approximate microaggregation approach for microdata protection

Microdata protection is a hot topic in the field of Statistical Disclosure Control, which has gained special interest after the disclosure of 658,000 queries by the America Online (AOL) search engine in August 2006. Many algorithms, methods and properties have been proposed to deal with microdata disclosure. One of the emerging concepts in microdata protection is k-anonymity, introduced by Samarati and Sweeney. k-Anonymity provides a simple and efficient approach to protect private individual information and is gaining increasing popularity. k-Anonymity requires that every record in the microdata table released be indistinguishably related to no fewer than k respondents.In this paper, we apply the concept of entropy to propose a distance metric to evaluate the amount of mutual information among records in microdata, and propose a method of constructing dependency tree to find the key attributes, which we then use to process approximate microaggregation. Further, we adopt this new microaggregation technique to study k-anonymity problem, and an efficient algorithm is developed. Experimental results show that the proposed microaggregation technique is efficient and effective in the terms of running time and information loss.     

面向论坛FAQ文档的轻量级聚类算法

文档聚类分析是组织文档的一种有效方法,在信息处理中被广泛应用于未知话题的自动发现并取得不错的效果。本文提出了一个轻量级聚类算法。该算法利用减小原始文档的索引数,来处理大量小文档,并把它们分组到几千个簇,或者通过更改特定参数,将聚类簇的数量减小到几十个。理论分析和实际应用表明,该算法提高了对高维数据和大量小文档处理效率。     

Efficient multivariate data-oriented microaggregation

Microaggregation is a family of methods for statistical disclosure control (SDC) of microdata (records on individuals and/or companies), that is, for masking microdata so that they can be released while preserving the privacy of the underlying individuals. The principle of microaggregation is to aggregate original database records into small groups prior to publication. Each group should contain at least k records to prevent disclosure of individual information, where k is a constant value preset by the data protector. Recently, microaggregation has been shown to be useful to achieve k-anonymity, in addition to it being a good masking method. Optimal microaggregation (with minimum within-groups variability loss) can be computed in polynomial time for univariate data. Unfortunately, for multivariate data it is an NP-hard problem. Several heuristic approaches to microaggregation have been proposed in the literature. Heuristics yielding groups with fixed size k tends to be more efficient, whereas data-oriented heuristics yielding variable group size tends to result in lower information loss. This paper presents new data-oriented heuristics which improve on the trade-off between computational complexity and information loss and are thus usable for large datasets.     

PHD: an efficient data clustering scheme using partition space technique for knowledge discovery in large databases

Rapid technological advances imply that the amount of data stored in databases is rising very fast. However, data mining can discover helpful implicit information in large databases. How to detect the implicit and useful information with lower time cost, high correctness, high noise filtering rate and fit for large databases is of priority concern in data mining, specifying why considerable clustering schemes have been proposed in recent decades. This investigation presents a new data clustering approach called PHD, which is an enhanced version of KIDBSCAN. PHD is a hybrid density-based algorithm, which partitions the data set by K-means, and then clusters the resulting partitions with IDBSCAN. Finally, the closest pairs of clusters are merged until the natural number of clusters of data set is reached. Experimental results reveal that the proposed algorithm can perform the entire clustering, and efficiently reduce the run-time cost. They also indicate that the proposed new clustering algorithm conducts better than several existing well-known schemes such as the K-means, DBSCAN, IDBSCAN and KIDBSCAN algorithms. Consequently, the proposed PHD algorithm is efficient and effective for data clustering in large databases.     

优化初始聚类中心的K-means聚类算法

针对传统K-means算法对初始中心十分敏感,聚类结果不稳定问题,提出了一种改进K-means聚类算法。该算法首先计算样本间的距离,根据样本距离找出距离最近的两点形成集合,根据点与集合的计算公式找出其他所有离集合最近的点,直到集合内数据数目大于或等于[α]（[α]为样本集数据点数目与聚类的簇类数目的比值）,再把该集合从样本集中删除,重复以上步骤得到K（K为簇类数目）个集合,计算每个集合的均值作为初始中心,并根据K-means算法得到最终的聚类结果。在Wine、Hayes-Roth、Iris、Tae、Heart-stalog、Ionosphere、Haberman数据集中,改进算法比传统K-means、K-means++算法的聚类结果更稳定;在Wine、Iris、Tae数据集中,比最小方差优化初始聚类中心的K-means算法聚类准确率更高,且在7组数据集中改进算法得到的轮廓系数和F1值最大。对于密度差异较大数据集,聚类结果比传统K-means、K-means++算法更稳定,更准确,且比最小方差优化初始聚类中心的K-means算法更高效。     

An evolutionary approach to enhance data privacy

Dissemination of data with sensitive information about individuals has an implicit risk of unauthorized disclosure. Perturbative masking methods propose the distortion of the original data sets before publication, tackling a difficult tradeoff between data utility (low information loss) and protection against disclosure (low disclosure risk). In this paper, we describe how information loss and disclosure risk measures can be integrated within an evolutionary algorithm to seek new and enhanced masking protections for continuous microdata. The proposed technique constitutes a hybrid approach that combines state-of-the-art protection methods with an evolutionary algorithm optimization. We also provide experimental results using three data sets in order to illustrate and empirically evaluate the application of this technique.     

Bandwidth optimal all-reduce algorithms for clusters of workstations

We consider an efficient realization of the all-reduce operation with large data sizes in cluster environments, under the assumption that the reduce operator is associative and commutative. We derive a tight lower bound of the amount of data that must be communicated in order to complete this operation and propose a ring-based algorithm that only requires tree connectivity to achieve bandwidth optimality. Unlike the widely used butterfly-like all-reduce algorithm that incurs network contention in SMP/multi-core clusters, the proposed algorithm can achieve contention-free communication in almost all contemporary clusters, including SMP/multi-core clusters and Ethernet switched clusters with multiple switches. We demonstrate that the proposed algorithm is more efficient than other algorithms on clusters with different nodal architectures and networking technologies when the data size is sufficiently large.     

An algorithm for k-anonymous microaggregation and clustering inspired by the design of distortion-optimized quantizers

We present a multidisciplinary solution to the problems of anonymous microaggregation and clustering, illustrated with two applications, namely privacy protection in databases, and private retrieval of location-based information. Our solution is perturbative, is based on the same privacy criterion used in microdata k-anonymization, and provides anonymity through a substantial modification of the Lloyd algorithm, a celebrated quantization design algorithm, endowed with numerical optimization techniques.Our algorithm is particularly suited to the important problem of k-anonymous microaggregation of databases, with a small integer k representing the number of individual respondents indistinguishable from each other in the published database. Our algorithm also exhibits excellent performance in the problem of clustering or macroaggregation, where k may take on arbitrarily large values. We illustrate its applicability in this second, somewhat less common case, by means of an example of location-based services. Specifically, location-aware devices entrust a third party with accurate location information. This party then uses our algorithm to create distortion-optimized, size-constrained clusters, where k nearby devices share a common centroid location, which may be regarded as a distorted version of the original one. The centroid location is sent back to the devices, which use it when contacting untrusted location-based information providers, in lieu of the exact home location, to enforce k-anonymity.We compare the performance of our novel algorithm to the state-of-the-art microaggregation algorithm MDAV, on both synthetic and standardized real data, which encompass the cases of small and large values of k. The most promising aspect of our proposed algorithm is its capability to maintain the same k-anonymity constraint, while outperforming MDAV by a significant reduction in data distortion, in all the cases considered.     

一种分层聚类模型及其在电信行业的应用

提出一种分层聚类算法,该算法可识别任意形状、大小的类,在某电信企业的客户分析中取得了较好的结果。算法首先从不同的角度对电信客户进行聚类或分类,然后以这些类为基础,实行自底向上的层次聚类得到最终的聚类结果。算法执行效率高,适合大规模数据的聚类问题。