k-均值问题的理论与算法综述

k-均值问题是理论计算机科学和组合优化领域的经典问题之一.相应的Lloyd算法是数据挖掘的十大经典算法之一,在各种领域被广泛研究和应用,特别是在图像处理和特征工程方面.随着数据多样性和数据量的爆炸性增长,在实际应用中遇到的k-均值聚类问题更加复杂多样,产生了各种亟需解决的具有挑战性的研究课题. k-均值问题在理论上是NP-难的.本文介绍经典k-均值问题及其变形的基于局部搜索、线性规划舍入、原始对偶、对偶拟合和Lagrange松弛等技术的有效算法.首先介绍经典k-均值问题的近似算法、加倍度量空间中的有效多项式时间近似方案及满足稳定性实例的多项式可解性,然后介绍k-均值问题的若干重要变形,包括k-中位、球面k-均值、鲁棒k-均值、带约束的k-均值和隐私保护k-均值等问题,最后列出k-均值领域中的若干公开问题.     

面向隐私保护的个性化搜索结果排序方法研究

针对个性化搜索中用户隐私保护的需求,提出一种面向隐私保护的个性化搜索结果排序方法.方法基于向量空间模型,引入安全点积计算方法来计算搜索相似度,旨在实现用户隐私保护的同时提高个性化搜索服务质量.首先分析了目前常用的搜索排序相似度计算方法存在的不足,然后分别介绍了向量空间模型和安全点积计算,最后详细介绍了面向隐私保护的个性化搜索结果排序方法,并对其性能进行了分析.     

基于模糊形式背景的变精度模糊信息粒

在模糊形式背景下研究变精度的模糊信息粒,给出精度为δ的必要模糊信息粒,充分模糊信息粒以及充分必要模糊信息粒的定义.在此基础上,进一步给出对任意给定的模糊信息粒转化为精度为δ的必要模糊信息粒,充分模糊信息粒及充分必要模糊信息粒的方法.     

分布式计算下基于差分隐私保护的参数估计

在大数据分析中,由于数据量巨大,储存于不同的机器中,常用的统计分析方法不能直接适用.因此需要对数据进行分布式计算.无论是分而治之还是多中心数据都需要对数据或计算中间结果进行传输.传输中不仅需要对数据进行隐私保护,也需要保证传输的高效性,同时传输次数过多不仅影响计算的效率,对数据的隐私保护也更有挑战.受此启发,本文在差分隐私模型下,提出了用于高效通讯的分布式参数估计算法中的隐私保护方案,并且严格证明了该方案既能有效保护数据安全,又不影响参数估计的有效性.最后,本文就线性模型下基于差分隐私保护算法的参数估计进行了模拟和实例验证.     

模糊数学在环境污染责任保险费率厘定中的运用

环境污染责任保险因开展经验及历史数据不足致费率难以合理厘定,引入模糊信息粒及综合评价理论,相对传统方法,更能实现费率厘定的公平合理,保障各方利益.本文以化学原料及化学制品制造业为研究对象,首先运用模糊信息粒理论处理历史数据,克服数据模糊不确定性,得出第三者赔偿额的模糊信息粒X;其次运用传统精算定价方法得出行业基准费率的...     

半群的(∈,∈ ∨q(λ,μ))-模糊k-理想(英文)

本文研究了半群中的广义模糊k-理想和(∈,∈∨q(λ,μ))-模糊k-理想.利用模糊集的截集及模糊集的性质,获得了(∈,∈∨q(λ,μ))-模糊k-理想的等价刻画,广义模糊特征化及广义模糊k-理想直积的基本性质.最后还给出了半群S是左k-诺特的充要条件是对于S的任意广义模糊左k-理想A,Im(A)是[λ,μ]上的良序子集.这些结果有重要的理论价值.     

一种云计算的隐私类型阈值模型和隐私保护方法

云计算作为一种新的计算模式,可为用户提供低成本的动态计算资源和存储资源,能充分提高资源的使用效率.但是数据隐私安全问题已成为云计算应用普及的最大挑战.为了更好管理用户的隐私数据,在基于(n+1,t+1)阈值的基础上,提出了一种基于隐私类型的(n+1,t+1)阈值隐私保护模型,结合可信的第三方服务器隔离存储模型,用户可在授权后依据数据隐私类型采用基于角色的访问控制进行相应的访问操作.安全分析表明,基于隐私类型的保护机制在方便用户按类型访问云中的数据资源同时,可以充分地实现用户数据的分类隐私保护.     

广义直觉模糊信息粒度

直觉模糊信息粒度是度量直觉模糊粒结构不确定性的一种重要方法。本文针对直觉模糊信息粒度在度量直觉模糊粒结构上存在的不足进行分析。首先,介绍直觉模糊粒结构距离。其次,改进了基于偏序关系提出的直觉模糊信息粒度的公理化定义,从直觉模糊粒结构距离观点出发,以最细的直觉模糊粒结构为参照物,计算每个直觉模糊粒结构与最细的直觉模糊粒结构之间的距离,距离的值越大,这个直觉模糊粒结构的信息粒度越大。最后,通过例子验证结论的合理性。     

基于形式概念的对象粒的属性逻辑公式描述

基于形式概念在属性集上建立逻辑语言系统,证明基于形式概念的基本对象粒描述定理,讨论合取原子属性逻辑公式所描述对象粒的性质,提出一个求解描述对象粒的属性逻辑公式的算法。     

基于安全多方的公平秘密共享方案

基于隐私保护的安全多方计算,提出一种新的公平秘密共享方案.方案利用隐私保护的安全多方计算,使参与者能够在不公开自己隐私秘密份额的情况下进行秘密恢复,从而确保了在所有参与者都诚实时,能恢复出真实秘密;当存在欺骗者时,都不能恢复出真实秘密,从而实现秘密恢复的公平性.与以往方案相比,该方案通过对私有秘密信息进行加密计算提高了安全性,同时在秘密恢复阶段,通过对秘密份额的安全多方计算,使其具有隐私保护功能.     

Some Basics on Privacy Techniques,Anonymization and their Big Data Challenges

With the progress in the information and communication fields, new opportunities and technologies for statistical analysis, knowledge discovery, data mining, and many other research areas have emerged, together with new challenges for privacy and data protection. Nowadays several personal records are kept in computerized databases. Personal data is collected and kept in census databases, medical databases, employee databases, among others. There has always been an asymmetry between the benefits of computerized databases and the rights of individual data subjects. Some data protection principles can be derived from the legal framework. In this survey, we present some basic cryptographic and non-cryptographic techniques that may be used for enhancing privacy, we focus mainly on anonymization in databases and networks, discuss some differences and interactions among the well-known models of k-anonymity and differential privacy and finally present some challenges to privacy that come from big data analytics.     

Community structure-based trilateral stackelberg game model for privacy protection

Location-based services are widely used in mobile applications, which not only bring convenience, but also cause serious privacy concerns. Based on the characteristics of social network, this work proposes a cooperative protection architecture to model the relationship among users, communities and location-based service. Furthermore, in order to construct K anonymity set, a novel community structure-based trilateral Stackelberg game model is developed for K-anonymity protection. In addition, an optimization method based on the proposed model is designed by the backward induction process. Finally, the security and the performance under different situations such as the anonymity parameter K and the community structure parameter overlapping weights are analyzed. The analysis results indicate that the proposed model and the optimization method are effective for privacy protection and can achieve high secure in location-based services.     

A key-lock-pair oriented access control scheme for the growth of users and files

A new access control scheme for the growth of users and files in file protection systems is proposed. Our scheme associates each user with a user key and each file with a file key. For each key, there are some corresponding locks, that can be extracted from a nonsingular matrix. Through simple operations on keys and locks, privacy decisions of the protection system can easily be revealed. Furthermore, by employing our method, whenever a new user or file is joined, the corresponding key values and lock values will be determined immediately without changing any previously defined keys and locks.     

基于二叉树的簇内分层密钥管理方案

通过对基于分簇的数据融合隐私保护算法CPDA的分析,提出了一种基于簇内分层随机密钥管理方案.它使用二叉树的逻辑结构,对簇内节点进行重新组织后,传输各自的切片数据,再通过建立密钥树的逻辑层次结构.对整个组密钥进行管理最终实现了在数据融合的同时,保护数据安全通过实验分析,相比于分簇隐私数据融合协议CPDA在具有更好的隐私保护性的同时,更低的数据通信量以及良好的可扩展性.     

Privacy-preserving data splitting: a combinatorial approach

Privacy-preserving data splitting is a technique that aims to protect data privacy by storing different fragments of data in different locations. In this work we give a new combinatorial formulation to the data splitting problem. We see the data splitting problem as a purely combinatorial problem, in which we have to split data attributes into different fragments in a way that satisfies certain combinatorial properties derived from processing and privacy constraints. Using this formulation, we develop new combinatorial and algebraic techniques to obtain solutions to the data splitting problem. We present an algebraic method which builds an optimal data splitting solution by using Gröbner bases. Since this method is not efficient in general, we also develop a greedy algorithm for finding solutions that are not necessarily minimally sized.

     

k-均值问题的差分隐私算法综述

$k$-均值问题是机器学习和组合优化领域十分重要的问题。它是经典的NP-难问题, 被广泛的应用于数据挖掘、企业生产决策、图像处理、生物医疗科技等领域。随着时代的发展, 人们越来越注重于个人的隐私保护:在决策通常由人工智能算法做出的情况下, 如何保证尽可能多地从数据中挖掘更多信息,同时不泄露个人隐私。近十年来不断有专家学者研究探索带隐私保护的$k$-均值问题, 得到了许多具有理论指导意义和实际应用价值的结果, 本文主要介绍关于$k$-均值问题的差分隐私算法供读者参考。     

SOM-based recommendations with privacy on multi-party vertically distributed data

Data collected for providing recommendations can be partitioned among different parties. Offering distributed data-based predictions is popular due to mutual advantages. It is almost impossible to present trustworthy referrals with decent accuracy from split data only. Meaningful outcomes can be drawn from adequate data. Those companies with distributed data might want to collaborate to produce accurate and dependable recommendations to their customers. However, they hesitate to work together or refuse to collaborate because of privacy, financial concerns, and legal issues. If privacy-preserving measures are provided, such data holders might decide to collaborate for better predictions. In this study, we investigate how to provide predictions based on vertically distributed data (VDD) among multiple parties without deeply jeopardizing their confidentiality. Users are first grouped into various clusters off-line using self-organizing map clustering while protecting the online vendors’ privacy. With privacy concerns, recommendations are produced based on partitioned data using a nearest neighbour prediction algorithm. We analyse our privacy-preserving scheme in terms of confidentiality and supplementary costs. Our analysis shows that our method offers recommendations without greatly exposing data holders’ privacy and causes negligible superfluous costs because of privacy concerns. To evaluate the scheme in terms of accuracy, we perform real-data-based experiments. Our experiment results demonstrate that the scheme is still able to provide truthful predictions.     

薛定谔方程的整体几何光学近似

整体几何光学方法是一种新的求解高频线性波动方程初值问题的渐进近似理论.该理论最初是对WKB初值数据问题提出来的.在本文中,我们将采用不同的方法,对这一方法予以重新推导,使得该理论同样适用于初值为扩展WKB函数的情形.特别地,我们将建立的理论用于薛定谔方程传播子的半经典近似上来.结果表明,整体几何光学方法提供的波场近似恰好是Kay提出的半相空间公式的一个实例.作为副产品,我们指出Van Vleck近似中起到关键作用的Maslov指标可以通过一个简单的代数关系式来确定.     

一种双扰动数量特征随机化问答策略

本文给出一种双扰动随机化回答模型.理论上扰动变量的引入会降低随机化调查的效率,本文使用两个设计参数设计了一种合理的双扰动变量随机化问答技术,在不降低装置对个体保护度的情况下,得出的结论表明,使用两个扰动变量可以提高调查装置的效率.通过数值模拟验证了本文模型的效率优于Bar-Lev,Bobovitch和Boukai 2004年单扰动回答模型的效率.