在大数据时代,用户的隐私保护是一个关键问题。作为数据挖掘的经典算法,原始k-means算法常用于对明文数据进行聚类分析,没有考虑到隐私保护的问题。已有工作研究支持隐私保护的k-means算法,但是一般有计算成本高(例如加密算法),精度损失大(例如数据扰动方法),通讯成本高(例如安全多方计算)等缺点。负数据库作为一种新型的数据表示方法,存储的是原始数据库补集中的信息,其难以逆转的特性可以用于保护原始数据的隐私。负数据库支持距离度量,可以被应用到k-means聚类分析中保护隐私。负数据库上现有的隐私保护k-means算法只能支持基于海明距离的相似度计算,但是现实中很多数据的相似度计算都是基于欧式距离的,这大大限制了该方法的适用范围。并且该方法将实数转化为二进制编码,编码的长度取决于数据库中不同实数值的数目,这使得该方法仅适用于结构简单、属性值少的数据,实用性较差。针对上述情况,本文利用欧氏距离二进制数编码方式中编码位数只与属性值大小相关的特点,提出了面向负数据库的欧氏距离计算公式。在此基础之上,提出了一种新的基于负数据库的隐私保护k-means聚类算法,并改进了负数据库的生成算法以进一步提高聚类的精度。具体工作如下:1)提出了面向负数据库的欧氏距离估算方法。根据负数据库的特点,通过贝叶斯定理进行概率计算后,可以在已知一个负数据库和一个实时串的前提下,估算出负数据库所隐藏的串和实时串之间欧氏距离。通过模拟数据进行误差实验,验证了面向负数据库的欧氏距离估算方法的准确性。2)提出了一种基于负数据库的隐私保护的-means聚类算法。主要思想是用K-hidden算法对聚类数据生成负数据库进行保护,并给出了欧氏距离在负数据库上的度量方法进行聚类过程中的计算。通过实验证明了我们所提出的隐私保护-means聚类算法可以在保护隐私的同时达到接近原始-means算法的聚类效果。3)提出了一种负数据库生成算法(称为QK-hidden算法),并构建了一种细粒度的隐私保护k-means方法,提升了聚类精度。在K-hidden负数据生成算法的基础上,QK-hidden算法引入了一组参数对每一个属性位的取反概率进行细粒度控制,从而可以控制每一个属性位的估算准确度和隐私度。根据QK-hidden算法的特点,提出了面向QK-NDB的欧氏距离估算方法。将该方法应用到隐私保护的-means算法中,通过实验验证了QK-hidden算法可以提高原有隐私保护的-means算法的聚类精度。