随着互联网的发展,网络上的数据呈指数级爆发增长,大数据时代来临。用户可以从大量数据中获取对自己有用的信息,或者通过对数据分析建立模型来帮助更好地决策,这给人们的生活带来极大便利。但是用户往往只有有限的存储空间和计算能力,无法做到对大数据集的存储和计算,这给用户从大数据中学习模型（机器学习）带来了挑战。公共云平台的出现给这一难题带来了转机,云平台凭借强大的存储能力和计算能力受到用户的广泛关注,用户可以将学习任务外包给云,即用户将数据存储到云上,并由云进行模型计算。但是由于云平台并不完全可信任,且用户隐私意识在不断提高,所以用户倾向于将数据加密后再上传到云平台进行存储,然后由云平台在密文数据集上进行机器学习如K均值聚类学习等。本文主要关注外包环境下隐私保护的K均值聚类方案,主要工作如下:（1）针对Rong等人的方案中使用乘法同态实现安全加法时存在的隐私泄露问题,本文提出了一个单密钥的外包K均值聚类的隐私保护方案（PPOKC）。提出的方案采用了本身具有加法同态性质的Paillier密码系统,避免了Rong等人方案中的隐私泄露问题。此外,提出的方案采用了Li等人基于局部敏感哈希函数的剪枝策略,从而可以节省聚类中关于某些数据记录的距离计算,提升聚类效率。（2）针对实际生活中用户倾向于使用自己的公钥加密数据的问题,本文提出了一个多密钥的外包K均值聚类的隐私保护方案（PPMOC）。该方案采用支持多密钥运算的BCP密码系统,支持用户用各自的公钥加密数据,且该方案与局部敏感哈希函数相结合,节省聚类中关于某些数据记录的距离计算。（3）针对提出的两个K均值聚类的隐私保护方案,本文进行了理论分析,并且使用Python语言和Crypto密码库进行了实验仿真,并与同等实验条件下实现的去剪枝策略方案和Rong等人的方案进行了对比,结果表明PPOKC方案与无剪枝的方案相比,可节省约0.52倍的时间,其中距离计算部分可节省约0.7倍的时间,而PPMOC方案可节省约0.31倍的时间,这说明提出方案的可行性和高效性。