一种基于格的隐私保护聚类数据挖掘方法

软件学报ＩＳＳＮ　１０００—９８２５，ＣＯＤＥＮ　ＲＵＸＵＥＷ　Ｊｏｕｒｎａｌ　ｏｆＳｏｆｔｗａｒｅ，２０１７，２８（９）：２２９３—２３０８［ｄｏｉ：１０．１３３２８／ｊ．ｃｎｋｉ．ｊｏｓ．００５１８３］　◎中国科学院软件研究所版权所有．　Ｅ－ｍａｉｌ：ｊＯＳ＠ｉｓｃａｓ．ａｃ．ｃｎ　ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃｎ　Ｔｅｌ：＋８６．１０—６２５６２５６３　一种基于格的隐私保护聚类数据挖掘方法　崔一辉１，２，宋伟１，２，王占兵　，一，史成良　，一，程芳权１，２　（软件工程国家重点实验室（武汉大学），湖北武汉（武汉大学计算机学院，湖北武汉４３００７２）　４３００７２）　通讯作者：宋伟，Ｅ－ｍａｉｌ：ｓｏｎｇｗｅｉ＠ｗｈｕ．ｅｄｕ．ｃａ　摘要：　由于云计算的诸多优势，用户倾向于将数据挖掘和数据分析等业务外包到专业的云服务提供商，然而随　之而来的是用户的隐私不能得到保证．目前，众多学者关注云环境下敏感数据存储的隐私保护问题，而隐私保护数据　分析的相关研究还比较少．但是如果仅仅为了保护数据隐私，而不对大数据进行挖掘分析，大数据也就失去了其潜在　的巨大价值．提出了一种云计算环境下基于格的隐私保护数据挖掘方法，利用格加密构建隐私数据的安全同态运算　方法，并且在此基础上实现了支持隐私保护的云端密文数据聚类分析数据挖掘服务．为保护用户数据隐私月户将数　据加密之后发布给云服务提供商，云服务提供商利用基于格的同态加密算法实现隐私保护的ｋ－ｍｅａｎｓ、隐私保护层　次聚类以及隐私保护ＤＢＳＣＡＮ数据挖掘服务，但云服务提供商并不能直接访问用户数据破坏用户隐私与现有的隐　私数据发布方法相比，隐私数据发布基于格的最接近向量困难问题（ｃｖＰ）和最短向量困难问题（ｓＶＰ）具有很高的安　全性．同时，有效保持了密文数据间距离的精确性＿一与现有研究相比，挖掘结果也具有更高的精确性和可用性．对方法　的安全性进行了理论分析，并设计实验对提出的隐私保护数据挖掘方法效率进行评估，实验结果表明，提出的基于格　的隐私保护数据挖掘算法与现有的方法相比具有更高的数据分析精确性和计算效率．　关键词：　数据挖掘；隐私保护；隐私保护的数据挖掘；基于格的加密　中图法分类号：ＴＰ３ｌ１　中文引用格式：崔一辉，宋伟，王占兵，史成良，程芳权．一种基于格的隐私保护聚类数据挖掘方法．软件学报，２０１７，２８（９）：　２２９３－２３０８．ｈｔｔｐ：／／ｗｗｗ．ｊｏｓｌｏｒｇ．ｅｎ／ｉ０００－９８２５／５１８３．ｈｔｍ　英文引用格式：ｃｕｉ　ＹｒＩ，Ｓｏｎｇ　Ｗ，Ｗａｎｇ　ｚＢ，ｓｈｉ　ｃ　Ｌ’Ｃｈｅｎｇ　ＦＱ，Ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｃｌｕｓｔｅｒ　ｍｉｎｉｎｇ　ｍｅｔｈｏｄ　ｂａｓｅｄ　ｏｎ　ｌａｔｔｉｃｅ．Ｒｕａｎ　Ｊｉａｎ　Ｘｕｅ　Ｂａｏ／Ｊｏｕｒｎａｌ　ｏｆＳｏｆｔｗａｒｅ，２０１７，２８（９）：２２９３，２３０８（ｉｎ　Ｃｈｉｎｅｓｅ）．ｈｔｔｐ：／／ｗｗｗ．ｊｏｓｉｏｒｇ．ｃｎ／１０００￣９８２５／５１８３．ｈｔｍ　Ｐｒｉｖａｃｙ　Ｐｒｅｓｅｒｖｉｎｇ　Ｃｌｕｓｔｅｒ　Ｍｉｎｉｎｇ　Ｍｅｔｈｏｄ　Ｂａｓｅｄ　ｏｎ　Ｌａｔｔｉｃｅ　ＣＵＩ　Ｙｉ．ＨＵＩ　，　，ＳＯＮＧ　Ｗｅｉ　，　，ＷＡＮＧ　Ｚｈａｎ．Ｂｉｎｇ　＇　，ＳＨＩ　Ｃｈｅｎｇ—Ｌｉａｎｇ　，　，ＣＨＥＮＧ　Ｆａｎｇ．Ｑｕａｎ。，　（Ｓｔａｔｅ　Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｓｏｆｔｗａｒｅ　Ｅｎｇｉｎｅｅｒｉｎｇ（Ｗｕｈａｎ　Ｕｎｉｖｅｒｓｉｔｙ），Ｗｕｈａｎ　４３００７２，Ｃｈｉｎａ）　（Ｃｏｍｐｕｔｅｒ　Ｓｃｈｏｏｌ，Ｗｕｈａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｗｕｈａｎ　４３００７２，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｄｕｅ　ｔｏ　ｔｈｅ　ｖａｒｉｏｕｓ　ａｄｖａｎｔａｇｅｓ　ｏｆ　ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ，ｕｓｅｒｓ　ｔｅｎｄ　ｔｏ　ｏｕｔｓｏｕｒｃｅ　ｄａｔａ　ｍｉｎｉｎｇ　ｔａｓｋ　ｔｏ　ｐｒｏｆｅｓｓｉｏｎａｌ　ｃｌｏｕｄ　ｓｅｒｖｉｃｅ　ｐｒｏｖｉｄｅｒｓ．Ｈｏｗｅｖｅｒ，ｕｓｅｒ’Ｓ　ｐｒｉｖａｃｙ　ｃａｎｎｏｔ　ｂｅ　ｇｕａｒａｎｔｅｅｄ．Ｃｕｒｒｅｎｔｌｙ，ｗｈｉｌｅ　ｍａｎｙ　ｓｃｈｏｌａｒｓ　ａｒｅ　ｃｏｎｃｅｒｎｅｄ　ａｂｏｕｔ　ｈｏｗ　ｔｏ　ｐｒｏｔｅｃｔ　ｓｅｎｓｉｔｉｖｅ　ｄａｔａ　ｆｒｏｍ　ｕｎａｕｔｈｏｒｉｚｅｄ　ａｃｃｅｓｓ，ｆｅｗ　ｓｃｈｏｌａｒｓ　ｅｎｇａｇｅ　ｒｅｓｅａｒｃｈ　ｏｎ　ｄａｔａ　ａｎａｌｙｓｉｓ．Ｂｕｔ　ｉｆ　ｐｏｔｅｎｔｉａｌ　ｋｎｏｗｌｅｄｇｅ　ｃａｎｎｏｔ　ｂｅ　ｍｉｎｅｄ，ｔｈｅ　ｖａｌｕｅ　ｏｆ　ｂｉｇ　ｄａｔａ　ｍａｙ　ｎｏｔ　ｂｅ　ｆｕｌｌｙ　ｕｔｉｌｉｚｅｄ．Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａ　ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ｍｉｎｉｎｇ（ＰＰＤＭ）ｍｅｔｈｏｄ　ｂａｓｅｄ　ｏｎ　ｌａｔｔｉｃｅ，ｗｈｉｃｈ　ｓｕｐｐｏｒｔ　・基金项目：国家自然科学基金（６１２３２００２，６１５７２３７８，６１２０２０３４）；ＣＣＦ中文信息技术开放课题（ＣＣＦ２０１４—０１一Ｏ２）；武汉市创新团　队项目（２Ｏ１４０７０５０４０２０２３７）；武汉大学自主科研项目（２０４２０１６ｇｆ００２０，２０１６．２０１７）　Ｆｏｕｎｄａｔｉｏｎ　ｉｔｅｍ：Ｎａｔｉｏｎａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｃｈｉｎａ（６１２３２００２，６ｌ５７２３７８，６１２０２０３４）；ＣＣＦ　Ｃｈｉｎｅｓｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｔｅｃｈｎｏｌｏｇｙ　ｏｐｅｎ　ｔｏｐｉｃ（ＣＣＦ２０１４－０１一Ｏ２）；Ｗｕｈａｎ　Ｉｎｎｏｖａｔｉｏｎ　Ｔｅａｍ　Ｐｒｏｊｅｃｔ（２Ｏｌ４Ｏ７Ｏ５Ｏ４Ｏ２Ｏ２３７）；Ｗｕｈａｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｉｎｄｅｐｅｎｄｅｎｔ　ｒｅｓｅａｒｃｈ　ｐｒｏｊｅｃｔ（２０４２０１６ｇｆ００２０，２０１６－２０１７）　收稿时间：２０１６－０７—１０；修改时间：２０１６－０９—０４；采用时间：２０１６－１１．１０；ｊｏｓ在线出版时间：２０１７－０２—２０　ＣＮＫＩ网络优先出版：２０１７－０２—２０　１４：０２：１９，ｈｔｔｐ：／／ｗｗｗ．ｃｎｋｉ．ｎｅｔ／ｋｃｍｓ／ｄｅｔａｉｌ／１１．２５６０．ＴＰ．２０１７０２２０．１４０２．Ｏ１１．ｈｔｍｌ　２２９４　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２８，Ｎｏ．９，Ｓｅｐｔｅｍｂｅｒ　２０１７　ｃｉｐｈｅｒｔｅｘｔ　ｉｎｔｅｒｍｅｄｉａｔｅ　ｐｏｉｎｔ　ａｎｄ　ｄｉｓｔａｎｃｅ　ｈｏｍｏｍｏｒｐｈｉｃ　ｃｏｍｐｕｔｉｎｇ．Ｍｅａｎｗｈｉｌｅ，ｉｔ　ｂｕｉｌｄｓ　ａ　ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｃｌｏｕｄ　ｃｉｐｈｅｒｔｅｘｔ　ｄａｔａ　ｃｌｕｓｔｅｒｉｎｇ　ｄａｔａ　ｍｉｎｉｎｇ　Ｍｅｔｈｏｄ．Ｕｓｅｒｓ　ｅｎｃｒｙｐｔ　ｐｒｉｖａｃｙ　ｄａｔａ　ｂｅｆｏｒｅ　ｏｕｔｓｏｕｒｃｅ　ｔｈｅ　ｄａｔａ　ｔｏ　ｃｌｏｕｄ　ｓｅｒｖｉｃｅ　ｐｒｏｖｉｄｅｒｓ，ｃｌｏｕｄ　ｓｅｒｖｉｃｅ　ｐｒｏｖｉｄｅｒｓ　ｕｓｅ　ｈｏｍｏｍｏｒｐｈｉｃ　ｅｎｃｒｙｐｔｉｏｎ　ｔｏ　ａｃｈｉｅｖｅ　ｐｒｉｖａｃｙ　ｐｒｏｔｅｃｔｉｏｎ　ｍｉｎｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ｉｎｃｌｕｄｉｎｇ　ｋ－ｍｅａｎｓ，ｈｉｅｒａｒｃｈｉｃａｌ　ｃｌｕｓｔｅｒｉｎｇ　ａｎｄ　ＤＢＳＣＡＮ．　Ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ｔｈｅ　ｅｘｉｓｔｉｎｇ　ＰＰＤＭ　ｍｅｔｈｏｄ，ｔｈｅ　ｐｒｅｓｅｎｔｅｄ　ｍｅｔｈｏｄ　ｗｉｔｈ　ｈｉｇｈ　ｓｅｃｕｒｉｔｙ　ｉｓ　ｂａｓｅｄ　ｏｎ　ｓｈｏ￣ｅｓｔ　ｖｅｃｔｏｒ　ｄｉｉｃｕｌｆｔｉｅｓ（ＳＶＰ）ａｎｄ　ｔｈｅ　ｃｌｏｓｅｓｔ　ｖｅｃｔｏｒ　ｐｒｏｂｌｅｍ（ＣＶＰ）．Ｍｅａｎｗｈｉｌｅ，ｉｔ　ｍａｉｎｔａｉｎｓ　ｔｈｅ　ａｃｃｕｒａｃｙ　ｏｆ　ｄｉｓｔａｎｃｅ　ｂｅｔｗｅｅｎ　ｔｗｏ　ｄａｔａ，ｐｒｏｖｉｄｉｎｇ　ｍｉｎｉｎｇ　ｒｅｓｕｌｔｓ　ｗｉｔｈ　ｈｉｇｈ　ａｃｃｕｒａｃｙ　ａｎｄ　ａｖａｉｌａｂｉｌｉｔｙ．Ｅｘｐｅｒｉｍｅｎｔｓ　ｒｅ　ａｄｅｓｉｇｎｅｄ　ｆｏｒ　ｔｈｅ　ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｃｌｕｓｔｅｒ　ｍｉｎｉｎｇ（ＰＰＣＭ）ｗｉｔｈ　ｃａｒｄｉａｃ　ａｒｒｈｙｔｈｍｉａ　ｄａｔａｓｅｔｓ　ｏｆ　ｍａｃｈｉｎｅ　ｌｅａｒｎｉｎｇ，ａｎｄ　ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｍｅｔｈｏｄ　ｂａｓｅｄ　ｏｎ　ｌａｔｔｉｃｅ　ｅｎｓｕｒｅ　ｎｏｔ　ｏｎｌｙ　ｓｅｃｕｒｉｔｙ　ｂｕｔ　ａｌｓｏ　ａｃｃｕｒａｃｙ　ａｎｄ　ｐｅｒｆｏｒｍａｎｃｅ．　Ｋｅｙ　ｗｏｒｄｓ：ｄａｔａ　ｍｉｎｉｎｇ；ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ；ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ｍｉｎｉｎｇ（ＰＰＤＭ）；ｌａｔｔｉｃｅ—ｂａｓｅｄ　ｃｒｙｐｔｏｇｒａｐｈｙ　随着云计算的发展和普及，用户越来越倾向于将数据存储到云上，租用云计算服务中心提供的丰富计算和　存储资源，能够为用户提供更加高效、专业的数据分析服务．然而，云服务提供商往往并不完全可信，用户在享用　云计算高效服务的同时，用户隐私数据也直接暴露给云服务中心，因此，数据隐私安全问题就成为用户使用云计　算不得不考虑的首要问题．为解决云计算外包服务模式下的用户数据安全问题，现有研究更多地致力于解决用　户隐私数据的存储安全，如密文可搜索机制、数据验证等．这些研究大多适用于查询、授权访问等简单应用场　景，而并不适用于数据聚类挖掘、关联分析等复杂应用场景．而数据需要隐藏发布的根本原因在于数据的潜在　价值，隐私数据发布后，数据的深层可用性对数据隐藏技术的发展和成熟至关重要【１】．　用户将数据挖掘分析任务外包到云上，不可避免地会涉及到敏感数据，如何操作、分析这些数据的同时保　护用户隐私，成为必须要解决的问题【２，３】．目前，众多学者主要致力于服务提供商可信前提下的数据分析和处理　研究，但这种假设在云计算的外包服务环境下并不成立，比如云服务提供商出于商业利益的驱使对用户隐私数　据的滥用、云服务管理员出于好奇窥视用户隐私信息、云服务提供商遭遇黑客攻击等，都会导致用户隐私泄露．　２０００年，Ａｇｒａｗａｌ首次提出了隐私保护数据挖掘（ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ｍｉｎｉｎｇ，简称ＰＰＤＭ）Ｉ￣概令Ｉ　．如图１　所示，隐私保护数据挖掘是指用户将数据外包给云服务提供商存储管理，由云服务提供商在确保用户隐私的前　提下进行数据挖掘服务，并将有价值的挖掘结果返回给用户．为保护数据隐私，ＰＰＤＭ中隐私数据本身和数据挖　掘结果对于任何非授权第三方都不可见．例如：医疗机构获得了大量第一手的医疗大数据，其需要对医疗大数据　进行聚类分析，进而得到潜在的疾病聚簇以及疾病治疗方案之间的相互关联性．显然，各个医疗机构数据挖掘的　能力相对有限，往往需要将原始医疗数据发布给专业的云服务提供商，并委托其按照需要对大数据进行挖掘和　分析，这时，病患的隐私成为不得不考虑的问题．保证用户数据的安全性和保障数据挖掘结果的准确性往往相互　矛盾，现有数据挖掘算法和研究往往没有考虑云环境下云服务提供商不可信的情况，因此，如何在保证用户隐私　的前提条件下提高挖掘结果的准　系　蓉　理　员　用户域　Ｆｉｇ．１　Ｄａｔａ　ｍｉｎｉｎｇ　ｐｒｏｂｌｅｍ　ｏｆ　ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　图１　隐私保护数据挖掘问题　没有任何一种隐私保护技术适用于所有应用场景【　．针对不同的应用场景，众多学者提出了很多高效的方　法【　］．目前，关联规则和决策树挖掘等隐私保护挖掘研究相对较多　９－１１ｌ，而聚类挖掘由于涉及计算量较大，支持　崔一辉等：一种基于格的隐私保护聚类数据挖掘方法　２２９５　隐私保护的聚类挖掘研究还相对较少．本文主要研究支持隐私保护的高精确性聚类挖掘问题，在保护用户数据　隐私的前提下，提供高精度的聚类挖掘服务．Ｚｈａｎｇ等人认为：现有研究在云端进行数据处理过程中，产生的中间　临时数据存在着安全隐患Ｉｌ引．本文提出的算法很好地解决了这个问题．针对现有研究安全性难以保障或者数据　挖掘精确性不足的问题，本文提出了一种基于格的保持距离加密算法，该加密算法本身具有计算中心点和计算　密文距离的同态性质，并在此基础上设计了云服务环境下隐私保护的聚类挖掘算法，使得云服务提供商在不解　密的前提下实现数据挖掘操作，这样可以在保护用户隐私的同时提升数据的可用性，在密文环境下，可以更加精　确地进行数据分析，从而获得更多有价值的信息．论文提出的隐私保护数据挖掘方法可以容易地扩展到其他数　据挖掘应用场景，文中基于提出的方法实现了ＰＰＫ．ｍｅａｎｓ（ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　Ｋ－ｍｅａｎｓ）、隐私保护层级聚类以及　ＰＰＤＢＳＣＡＮ（ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ＤＢＳＣＡＮ）方法，实现云端密文数据环境下的精确数据挖掘服务．　本文的主要贡献包含以下４方面的内容．　（１）在ＧＧＨ［　】公钥密码的基础上设计了一种基于格的保持距离加密算法，算法安全性基于格的最近　向量求解困难问题和最短向量困难问题，安全性得到有效保障．基于格的困难问题与大素数难分解等　问题相比性能较好，而且加密方式属于批处理加密方式，更加适合大数据的元组存储形式，每次加密　以行为单位而非将元组中的元素逐列进行处理，可以提高隐私数据的加密发布效率：　（２）在提出的保持距离加密算法基础上，设计了密文状态下的数据均值计算方法和密文数据之间的距离　计算方法．与现有的聚类方法相比，论文提出的加密算法保持密文隐私数据计算与明文计算保持同态　特性，使得隐私数据挖掘的精确性大大提升；　（３）　本文设计的隐私保护聚类挖掘框架可以容易地扩展实现多种聚类挖掘算法，如ｋ－ｍｅａｎｓ、层次挖掘以　及ＤＢＳＣＡＮ等．而现有的隐私保护挖掘算法大多数只能支持某一种特定挖掘算法，因此，本文提出的　方法具有更好的可扩展性，可以更好地支持复杂应用需求，从多个角度挖掘出潜在的聚类关系；　（４）　本文进一步构建了隐私保护的ｋｄ—ｔｒｅｅ结构，在保证数据隐私的前提下，高效地完成最近邻检索、ＫＮＮ　查询和范围查询，实现密文环境下高效的隐私保护ＤＢｓｃａｎ等聚类挖掘算法．　１相关工作　隐私保护的聚类挖掘从数据存储方式上可以分为云服务提供商存储和用户存储，从隐私模型的角度包括　差分隐私、基于平移变换、基于水印、基于匿名和基于加密等，在挖掘方法上面支持的挖掘算法也不尽相同，　数据类型主要包括字符型和数值型两种．随着云存储的快速发展，本文主要致力于解决数据存储在云服务提供　商场景的隐私保护数据挖掘问题研究．隐私保护数据挖掘研究现状见表１．　Ｔａｂｌｅ　１　Ｒｅｓｅａｒｃｈ　ｓｔａｔｕｓ　ｏｆ　ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ｍｉｎｉｎｇ　表１　隐私保护数据挖掘研究现状　典型算法　Ａｌｌａｒｄｔ　Ｘｕｎ　ｙｉｔ　Ｖｌａｃｈｏｓ｛８＿　ｋ－匿名　Ｏｌｉｖｅｉｒａ［　数据存储　云服务提供商　√　√　方式　用户　分布式　√　存储　集中式　、，　差分隐私　平移变换　、，　隐私模型　基于水印　、，　基于匿名　加密　、，　基于噪音　ｋ－ｍｅａｎｓ　挖掘方法　ＤＢＳＣＡＮ　√　、，　层次聚类　、，　、，　隐私保护的数据挖掘过程分为两个阶段：首先，用户需要对原始数据进行隐私保护的数据发布；然后，云服　务提供商需要在经过隐私保护处理的数据上进行数据挖掘．隐私保护的数据挖掘算法大致分为两类：一类是对　２２９６　Ｊｏｕｒｎａｌ　ｏｆＳｏｆｔｗａｒｅ软件学报Ｖｏ１．２８，Ｎｏ．９，Ｓｅｐｔｅｍｂｅｒ　２０１７　数据本身进行泛化扰动或者添加噪音进而保护数据隐私【１６－１８，１９］，该类方法的优点在于避免了复杂的处理过程，　方法性能相对较好：另一类通过对数据本身进行平移变换到另一个向量空间，以确保数据隐私【】　，此类方法的优　点是挖掘的精度往往比较高．　第１类主要使用泛化和添加噪音的方式进行隐私保护的数据挖掘．　匿名方案［２ｏ］和ｌ－多样化方案［２ｌＪ主要是通过数据的泛化来隐藏用户的隐私，其数据发布前后见表２、表３，　抵御了连接攻击，在一定程度上可以很好地解决数据发布中的数据隐私保护问题，当数据仅仅为了简单应用时，　这两种方案简单有效．但是进行聚类数据挖掘时，由于数据被泛化，挖掘分析的结果不是很精确．例如在原始数　据上进行数据挖掘，挖掘出的聚簇数目为３，但是由于数据的泛化，挖掘出的聚簇数目为２．文献［２２】提出了基于差　分隐私的聚类技术，有效地在保证用户隐私的条件下进行挖掘．Ｍｏｈａｎ认为：尽管差分隐私提出了一种理论上可　以在保护用户隐私数据记录前提条件下数据处理，但是其实际使用的输出结果存在精度丢失问题Ｌ２　．现实中，精　确挖掘的需求不容忽视，尤其是在医学生物以及银行商业金融领域．文献【１６】提出了一种通过增加噪音和构建　决策分类树来进行隐私保护聚类挖掘的方法，因为辅助信息决策分类树的存在，挖掘性能有较大提升，但是用户　的隐私也会有一定程度的泄露．文献［１８】提出的ＮｅＳＤＯ算法采用合成数据替换真实数据，发布合成数据进行数　据挖掘，数据发布的性能较好，挖掘精度由于合成数据的原因受到一定影响．且合成数据是邻域数据的均值，也　会泄露一定的数据隐私．文献［２４］提出的基于组内数据交换方法的挖掘方法，其优势主要体现在操作相对简单　性能最佳，但是挖掘精确性和安全性会受到一定影响．文献［１９］通过扰动原始数据从而达到隐私保护的目的，并　且在此技术上进行数据挖掘．　Ｔａｂｌｅ　２　Ｔｈｅ　ｒａｗ　ｄａｔａ　表２原始数据　垒壁　１２３７　３４２０　２５４３　４４６ｌ　２５４３　４４６１　７８　７９　６９　６８　６ｌ　６２　Ｗｅｉｇｈｔ　８０　７８　Ｈｅａｒｔｒａｔｅ　Ｄｉｓｅａｓｅ　６６　６７　６４　６３　７６　７９　６７　６６　６４　６３　心脏病　心脏病　心脏病　心脏病　心脏病　心脏病　第２类主要使用向量空问映射方法．　ＲＢＴ算法【ｌ　５ｌ是目前隐私保护的聚类挖掘精度最高的算法，该算法的隐私保护数据发布实质是将元组数据　进行平移旋转，平移旋转保证了数据的精度，但是其安全性相对较低，且明文和密文一一对应，会遭遇统计攻击．　文献［２５１结合算法ｋ－ｍｅａｎｓ设计了Ｐｋ．ｍｅａｎｓ方法进行聚类挖掘，另外，Ｐｋ．ｍｅａｎｓ支持的聚类算法比较单一，其实　现了一个隐私保护的ｋ．ｍｅａｎｓ算法．事实上，每一种聚类挖掘算法都有该算法适合的聚簇类型，单一的挖掘算法　Ｐｋ—ｍｅａｎｓ不能满足所有类型的聚类挖掘需求．全同态加密为动态数据隐私保护提供了一种理论支持，但其在解　决任意计算方面的实用性还存在很大的差距．因此，数据隐私保护的研究主要还是针对特定的计算类型，应用同　态加密方法研究代价可以被实际应用所接受的隐私保护机制【２】．　综上所述，现有的算法往往存在以下问题：第１类方法在性能上较好，挖掘精度存在一定问题；第２类方法在　精确性上优于第１类方法，但是安全性上存在一定问题．另外，部分算法只能针对一种挖掘算法进行挖掘，云计算　崔一辉等：一种基于格的隐私保护聚类数据挖掘方法　２２９７　环境下，亟需一种能够适应多种挖掘算法的隐私保护数据发布方式和数据挖掘方法，并且兼顾安全性、精确性　和挖掘性能．　２准备知识　本节介绍论文中使用的密码学工具和基本定义．论文中使用的符号见表４　Ｔａｂｌｅ　４　Ｎｏｔａｔｉｏｎｓ　表４符号定义　符号　ｂ　Ｊ　，　＾如　符号定义　用户公钥，用户公开自己的公钥给云服务提供商，后者利用　６进行隐私保护的同态计算　用户私钥，用户使用自己的私钥处理云服务提供商返回的聚类结果，得到明文结果　扩展高维向量积运算矩阵　云服务提供商求解距离的辅助向量　衡量优质基的阈值参数　密文状态下数据向量ｅ１和ｅ２之间的欧式距离　数据集中的第ｉ明文向量　密文元组（　，ｆ　）　隐私保护的ｋ－ｍｅａｎｓ算法中迭代结束条件阈值　为单位矩阵　向量ｍ经过混淆编码生成的向量　～　如　　。ｍ　ｅｆ　ａ　＾　ｃｏｄｅ　定义１．线性空间上有向量集合ｖｌ，ｖ２…．，ｖｎｃ＿Ｒ　，格（１ａｔｔｉｃｅｓ）就是这些向量的线性组合，格三的维数（月）等　于构成格的线性不相关向量的个数ｌ１　：　Ｌ＝｛ａｌＶｌｑ－ａ２ｖ２ｑ－…＋口＂ｖｎ　ａｉＥ乙ｖｉ￣Ｒｍ，１≤ｆ≤　｝．　～定义２．可以采用Ｈａｄａｍａｒｄ比率来衡量格中基向量的正交程度，对于格　的一组基向量｛ｖｌ，ｖ２…．，ｖ　），两两　正交程度较高，即Ｈａｄａｍａｒｄ（ｖ１，　２，．．．，ｖ　）值大于阈值甜，称｛　ｌ，ｖ２，．．．，　｝就是格　的一组优质基【ｌ３Ｊ．　定义３．当格三的一组基向量｛　１，　２…．，ｖ　｝两两正交程度较低，即Ｈａｄａｍａｒｄ｛ｖ１，　２，．．．，ｖ　｝值小于阈值甜，称　｛ｖｌ，　２…．，　｝就是格三的一组劣质基【”Ｊ．　根据格基的等价变换原理，由一个优质的基转化为一个劣质的基很容易，相反则很困难．本文利用格加密的　这一性质，由用户掌握格的优质基作为密钥，生成劣质基供云端对数据进行聚类挖掘计算，但是云端并不能直接　解密访问用户隐私数据，从而在隐私保护前提下实现聚类数据挖掘服务．　定义４（扩展的高维向量积）．向量积通常存在于三维向量，论文扩展三维向量积到向量积．对于任意ｎ　维向量　＝（　，０２，．．．，　），ｂ：（ｂｌ，ｂＥ，．．．，　），记　＠６为向量西，ｂ的扩展向量积，其中，　－ａ２　Ｏ　…　…　…　０　６１　ａ＠ｂ＝　０　－ａ３　日２　…　０　●－＿　●●●　●●●　●●●　６２　，　。＝　一…　ａｉ　１　…　０　●●●　●●●　●●●　●●●　●●●　●●●　一１　　…　－ａＩ　・・・　●●●　●●●　…由上述定义可知：当两个高维向量面，　方向相同时，其高维向量积西０　＝０．文中利用这一性质实现云端　加密隐私数据的同态精确计算．　定义５ｆ隐私保护ｋ－ｄ树１．每个节点都为ｋ维点的二叉树．所有非叶子节点可以视作用一个超平面把空间分　区成两个半空间（ｈａｌｆ－ｓｐａｃｅ）．节点左边的子树代表在超平面左边的点，节点右边的子树代表在超平面右边的点．　本文在混淆编码的基础上由数据拥有者构建的ｋ．ｄｔｒｅｅ在保证用户隐私的前提下提高数据挖掘的性能．　定义６．吉文斯旋转表示为如下形式的矩阵（乘积Ｇ（ｉｊ，　．Ｘ表示向量　在（　，７）平面中的逆时针旋转觚度．　这里的Ｃ＝ＣＯＳ（　和ｓ＝ｓｉｎ（￣现在第ｉ行和第ｋ行与第ｉ列和第ｋ列的交叉点上．Ｇ（ｉｊ，　中，非零元素的描述为　２２９８　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２８，Ｎｏ．９，Ｓｅｐｔｅｍｂｅｒ　２０１７　ｇｉｉ＝Ｃ莲　ｃ，ｇｑ　一ｓ　ｇｊ　１…０．．　．　０　：　●　０…Ｃ．－　．　０　：　●　Ｇ（ｉ，Ｊ，　）＝　０…Ｓ．．　．　０　：　●　●　０…０－．　．　１　３基于格的保持相对距离数据加密方法　本文提出的隐私保护聚类挖掘方法（ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｃｌｕｓｔｅｒ　ｍｉｎｉｎｇ，简称ＰＰＣＭ）系统架构如图２所示．用　户为保护数据隐私，利用加密算法对数据进行加密．为了支持云端的聚类挖掘分析，论文在ＧＧＨ的基础上设计　了一种基于格的保持相对距离加密算法，确保云端对密文进行距离运算与明文的距离保持同态特性，云服务提　供商按照用户的聚类挖掘请求对云端的加密隐私数据进行聚类分析，并返回密文分析结果，用户利用个人私钥　对分析结果进行解密．　０；　ｃ　０　密文同态计算　Ｉ——．——，　Ｊ　Ｌ．——　Ｊ　＼　…　一一一一一　一一一一一一］　一：ｌ２Ｕ９～　Ｉ一一一．　１．丝塑薯墨　堕ｌ　ｊ生成挖掘请求ｉ　ｔ……　用户私钥　《　、》　　—　保持距离的　加密算法　．－……一．１＿曼塑　一ｊ～一一　公开参数　Ｆｉｇ．２　ＰＰＣＭ　ａｒｃｈｉｔｅｃｔｕｒｅ　图２　ＰＰＣＭ系统架构　ＰＰＣＭ利用基于格的距离同态加密算法实现，基于格的距离同态加密算法由以下５部分组成：第３．１节介绍　ｓｅｔｕｐ过程、系统公开参数和用户密钥的生成方法，每个用户与云服务提供商使用同一公开参数：第３．２节介绍　向量的混淆编码（ｃｏｎｆｕｓｉｏｎ　ｃｏｄｉｎｇ），并在此基础上构建隐私保护　ｔｒｅｅ；第３．３节基于ＧＧＨ公钥密码设计　了基于格的保持距离的隐私保护数据处理算法（Ｅｎｃ），将数据外包存储在云服务提供商；第３．４节介绍用户获得　云端密文挖掘结果后的明文数据解密过程（Ｄｅｃ）；第３．５节和第３．６节介绍云服务提供商密文状态下的同态运算．　３．１用户密钥和公开参数生成（ｓｅｔｕｐ）　用户需要生成用户密钥　曲以及公开参数　．用户选择优质基　，『＝ｖ　，ｖ２…．，ｖ　以及随机整数矩阵　满　足ｄｅｔ（∽＝±１．由于使用随机算法求解满足ｄｅｔ（∽＝±１的矩阵时间开销很大，本文采用对单位矩阵进行初等变换　的方法生成转换矩阵　对单位矩阵进行交换行或者交换列的初等变换矩阵的行列式等于原行列式乘以一１．将　某一行或者某一列的倍数加到其他的行或者列，行列式不变．左乘　为对单位矩阵＾做随机的初等行变换，右乘　矩阵Ｂ对矩阵单位矩阵＾做随机的初等列变换．本算法涉及的初等变换不包括对于矩阵某一行（列）乘以ｋ．我们　得到一组劣质基　曲＝　ｗ１，ｗ２，…，Ｗ　．　６即为用户的公钥．用户将私钥　，　安全存储在本地，公钥　６提交　崔一辉等：一种基于格的隐私保护聚类数据挖掘方法　２２９９　给云服务提供商．安全性与矩阵中元素的取值范围有关，矩阵中元素取值范围越大算法越安全可靠，但是随着矩　阵中元素大小的增加，也会导致性能的下降．　算法１．密钥生成ｋｅｙＧｅｎｅｒａｔｅ（ｖ／，ｎ）．　输入：泯判断优质基的阈值，ｎ是密钥维度；　输出：　１：Ｗｈｉｌｅ（ｔｒｕｅ）｛　２：随机选取ｖｌ，ｖ２…．，ｖｎ；　３：ｉｆ（Ｈａｄａｍａｒｄ（ｖｌ，Ｖ２，　３）＞阈值　｛　４：Ｊ　尸　ｌ，Ｖ２　．，Ｖｎ－Ｉ，ｖ＂；　５：　ｂｒｅａｋ；　６：　７：Ｕ＝ＡＡＢ　ＩＩＡ为单位矩阵．　８：　曲＝　９：ｒｅｔｕｒｎＫｐ　和Ｋｐ“ｂ．　云服务提供商在聚类挖掘的过程中需要求解向量之间的距离，加密的密文包含随机数．如何在计算距离的　过程中抵消掉随机数的影响，获得一个相对准确的距离用于聚类挖掘，是数据处理过程中需要解决的重要问题．　三维空间中具有如图３所示性质：（ｒ１一ｒ２）（／ｌ，１２，，３）＝｛０，０，０｝，即，选定直线上的随机向量之差和直线的方向向量的向　量积为０．本文将三维空间的向量积性质扩展高维，利用本文定义的高维向量积在云服务商求解距离的过程中　抵消掉随机数，进而计算出密文向量之间的相对距离，此距离在混淆编码过程中进行了缩放．　１　０，５　Ｏ　．ｏ５　．＇　１　Ｆｉｇ．３　Ｔｈｒｅｅ　ｄｉｍｅｎｓｉｏｎａｌ　ｖｅｃｔｏｒ　ｓｐａｃｅ　图３三维向量空间情形　随机数生成公式如下所示（初始化过程中生成　＝｛‘，ｆ２，．．．，　高维随机向量生成公式：　｝为生成随机数所需向量，此向量作为公开　参数上传云服务提供商，云服务提供商借助其完成聚类挖掘所需各类同态运算）．　（　，　，…，ｒ９＝　一ｌ＝　一ｌ＋　ｌｔ　＝　＋　ｆ　其中，　，　，…，　一　，ｒ　ｔ≠０　２３００　Ｊｏｕｒｎａｌ　ｏｆＳｏｆｔｗａｒｅ软件学报Ｖｏ１．２８，Ｎｏ．９，Ｓｅｐｔｅｍｂｅｒ　２０１７　３．２混淆编码和隐私保护　一ｄ　ｔｒｅｅ生成　首先，我们对原数据进行混淆编码，混淆编码本质上是一个保距映射（保持相对距离），经过混淆的原始数据　实际上进行了变换和缩放，其目的是抵御背景知识攻击，经过混淆编码的向量数据相对位置不发生改变，真实距　离转换成为相对距离，因此不改变聚类特性．云服务提供商完成聚类挖掘，将挖掘结果返回给用户，用户首先解　密聚类结果，然后进行逆混淆编码得到聚类结果．数据发布的过程中，列名同样是需要隐藏的元素，以降低暴力　破解的攻击风险．但攻击者确定某一列是血压时，随机选择某一密钥进行解密，当其将数据解密后发现在正常的　血压范围里面，随机选择的密钥就有可能是解密密钥；但是如果无法确定选择的列的属性，就很难确定当前选择　密钥是否正确．本质上讲，混淆编码过程首先进行一系列的吉文斯旋转，然后进行缩放，进而进行向量的交换混　淆，最后进行平移变换．　ｇ将一单位矩阵的第Ｐ行的所有元素与第ｑ行互换，这一变换　（　ｆ），将第ｉ行的所有元　素乘以非零常数　．　混淆编码过程ｃｏｄｅ＝ｋｅｙ１ｍ＋ｋｅｙ２，其中，ｋｅｙｌ＝兀　兀　１＂　（后）兀Ｇ（　，　，　），尼　２＝［ｋｌ，也…．，ｋｎ　．　在混淆编码的数据上面构建的缸　ｔｒｅｅ，需要证明经过混淆编码向量向量仍旧保持了了其相对位置．显而易　见，缩放变换、元素交换以及平移变换不改变元素之间的相对位置，下面我们证明一系列的吉文斯变换不会改　变向量之问的相对位置．　性质１．经过一系列吉文斯变换，向量之间的距离不变．　证明：设向量　＝（Ｘ１，Ｘ２　．，　），　＝（Ｙｌ　Ｙ　．，　），将向量　，　分别执行一轮吉文斯变换，得到ｊ｝，，　，即：　『　＝Ｇ（ｉ，Ｊ，　）・　＝（　，…，ｔｃｏｓ０一　，ｓｉｎ　，…，Ｘｉ　ｓｉｎ０＋　，ｃｏｓ０，…，　）　Ｉ　＝Ｇ（ｉ，Ｊ，０）‘　＝（Ｙｌ，…，Ｙｉｃｏｓ０一　，ｓｉｎ０，…，Ｙｆ　ｓｉｎ０＋Ｙ，ｃｏｓ０，…，　）’　则转换过后二者终点的距离：　■———一　（　，　）＝　ＩＺ（ｘ；一　）　，Ｖ　≠Ｅ，Ｉ　／∑（《一　）　＋（　一　）　＋（　一　）　，Ｖ／　∑（≠ｊ，／　《一　）　＋［（　—Ｙｉ）ＣＯＳＯ一（　一Ｙ／）ｓｉｎＯ］　＋［（　—Ｙｉ）ｓｉｎ０＋（ｘｊ－ｙ，）ｃｏｓ０］　，Ｖ／　ｋ∑（￣ｉ，／　ｘｋ—Ｙｋ）　＋（ｔ－ｙ　）　＋（　－ｙｊ）　＝、　（　一　）　ｄｌ（ｘ，　）．　Ｖ　ｋ＝ｌ　综上证明：经过一轮吉文斯变换，向量之间的距离不会发生变换．同理可证：经过一系列吉文斯变换，向量的　距离不会发生变化．所以在混淆编码上面构建的　ｔｒｅｅ，在保证安全的同时保持了其索引特性．　口　３．３用户加密发布数据（Ｅｎｅ１　本文中，明文数据以向量的形式存储，对于明文高维向量ｍ，用户通过高维随机向量生成　ｒ的模应该小　于格中向量之问距离的一半．用户使用自己的公钥　曲加密ｍ，生成的密文二元组（　ｆ，ｔｉ）由两部分组成（第１部分　用于解密过程还原明文数据；第２部分ｔ　为　曲ｍ的哈希值，主要用于密文状态下的辅助同态计算过程）：　ｅｉ　（ｓｉ，ｔ３　（　ｂ・　ｆ＋ｒｆ，ｈａｓｈＭ（ｋｐ　ｂ・ｍｅ））　（１）　为哈希矩阵，矩阵的秩为ｌ，见公式（２）．Ｍｈ　＾Ｋｐｕｂ＂　）的哈希过程是单向的，对于该哈希等式的求解，满足条　件的解有无数多个．对于同一个数据集，　＾的取值应满足公式（３），云服务提供商才可以计算密文距离：　崔一辉等：一种基于格的隐私保护聚类数据挖掘方法　２３０１　ｈ２…　０　０　…　Ｍ　ｓｈ＝　。　０　０　（　ｃ　Ｚ）　０　０　０　Ｏ　０　ｒａｎｋ（［Ｍｈ　＾；　】）：＝”　３．４用户解密还原挖掘结果（Ｄｅｃ）　（３）　云服务提供商将挖掘结果返回给用户，此时，挖掘结果是密文状态的，防止了云服务提供商的非授权访问．　用户得到挖掘结果需要进行如下操作，最终获得明文挖掘结果：　ｖ＝ｒｏｕｎｄ（ＳｉＫｐ￣，）・Ｋ　Ｈｉ，　ｃｏｄｅ＝ｖ・　．　用Ｂａｂａｉ算法计算最近向量ｖ最接近　ｆ，再次计算ｖ・　逆混淆编码过程还原混淆编码数据为原始数据：　ｍ＝　，即得到明文编码ｃｏｄｅ．　（ｃｏｄｅ—ｋｅｙ２）．　３．５云服务提供商距离的密文计算　在隐私保护聚类挖掘的过程中，云服务提供商需要计算密文之间的距离．对于一对密文向量　１，ｔ　）及（　：，　），　密文的计算过程如下：　ＳＩ　“ｂ・ｍｌ＋ｒｌ，ｔｌ＝ｈａｓｈＭ（Ｋｐ“ｂ・ｍ１）　２＝　・ｍ２＋ｒ２，ｔ２＝ｈａｓｈ　等式（４）减等式（５），得：　１—　２＝＾　“ｂ・（ｍｌ—ｍ２）＋ｒｌ—ｒ２　ｔｌ－ｔ２　Ｍｈ　ｈ・（　ｂ・ｍ１）一Ｍｈ。　ｈ・（　ｂ・ｍ２）＝　ｈ・（　ｂ・（ｍｌ—ｍ２））　对公式（６）两边分别乘以　＝｛ｌＩ　１２，．．．，　），由定义４扩展的高维向量积的性质可得等式（８）：　‘（４）　（５）　（６）　（７）　（８）　ｍ２）　（　一　）＝　＠（　枷・（ｍ　一　））＝　・（　・（ｍ　～ｍ２））　与　曲对于云服务提供商已知，又由等式（８）结合等式（７）可以求出　而可以得到（　１一ｍ２），最终可以求出ｍｌ和　２的欧式距离．　（　１一　ｚ），　曲对于云端己知，进　×（　ｌ一　）对于云服务提供商已知，且云服务提供商掌握　，但是在等式（８）中，　生成的矩阵的值为０，所以　依靠密文二元组的第１部分无法求解出　（　１～ｍ２）．当直线取值满足等式（３）时，由等式（７）和等式（８）可以求解　出唯一的　一ｍ２），进而求解出唯一的　—　２），最终求得欧氏距离．　算法２．ｃｏｍｐｕｔｅＤｉｓｔａｎｃｅ．　Ｉｎｐｕｔ：密文元组ｅｌ，ｅ２；　Ｏｕｔｐｕｔ：；￣组之间的欧式距离　。　１：（Ｓ１－Ｓ２）　２：　×（　一　）　３：等式（７）和等式（８）可求解出　１一ｍ２）　４：左乘Ｋ　－１即可得到ｍｌ—ｍ２　５：如㈤　ｃｏｍｐｕｔｅＥｕｃｌｉｄｅａｎ（ｍｌ—ｍ２）　６：ｒｅｔｕｒｎ　ｄ　自．　；　３．６均值密文计算　对于明文ｍ１，ｍ２，．．．，ｍ　，加密处理后如下所示：　２３０２　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２８，Ｎｏ．９，Ｓｅｐｔｅｍｂｅｒ　２０１７　Ｋｐ曲　ｌ＋，ｉ，ｈａｓｈＭ（Ｋｐ曲　Ｊ　ｅｌ　（（　，％　）：｛　＝（Ｋｐ曲’ｍ２＋ｒ２，ｈａｓｈＭ（Ｋｐ曲　　ｐ曲’ｍ　＋　，ｈａｓｈＭ（　ｐ曲　Ｉｅｎ　（密文均值计算公式：　（ｎ＝｜　ｎ｜、　｛Ｌ∑　／　，∑ｆ　／卟　ｉ＝１　／　ｉ＝１／　Ｊ　性质２．密文状态下均值运算具有同态性质．　证明：明文的中心点为ｍｍ　＝（∑　ｍ　）　，由于（∑ｎ　ｒ￣）ｌｎ仍为直线上的点，所以中心点的计算具有同态性　质．密文状态下的计算结果与直接对均值进行隐私保护的数据发布处理，结果是一致的．　ｒ　Ｈ＝｜、　／　／　ｎ｜　ｆ　ｎｉ＝１　｜、　／　／　（　：＋．．．　）／　＝　曲ｌ＼∑ｍｉ／ｎ　１＋∑　＝　脚Ｉ∑ｍｉ　ｎ　＝Ｋｐ　ｍ　ｉ＝１　ｆ＝１／　厂　厂　ｉ＝１　／、、　／　／　ｆ　＝（ｆｌ＋ｆ２＋．．．＋ｆ　）／　＝ｈａｓｈＭＩ　Ｋ　Ｉ＼∑ｍｆ　ｎ　　ｌＩ＝ｈａｓｈＭ（Ｋ　・ｍ　ｆｄ）．　３．７性能分析和安全分析　口　与现有的方法相比，由于本文采用基于格的困难问题的批处理方式进行数据发布，与基于大素数难分解等　困难问题进行数据发布的方式相比性能较好．密文ｋ－ｍｅａｎ算法的时间复杂度是Ｏ（ｎｌｏｇ（ｎ）），密文层次聚类的时　间复杂度为Ｏ（ｎ　），密文ＤＢＳＣＡＮ时间复杂度Ｄ（月）．由于本文构建了隐私保护的ｋｄ—ｔｒｅｅ，密文挖掘过程中处理性　能有很大的提升．　最短向量问题（ｔｈｅ　ｓｈｏｒｔｅｓｔ　ｖｅｃｔｏｒ　ｐｒｏｂｌｅｍ，简称ｓｖＰ）是寻找一个格三中最短的非零向量．即，寻找一个ｖ∈　满足其欧几里德范数Ｉｌｖｌ［最小．最接近向量问题（ｔｈｅ　ｃｌｏｓｅｓｔｖｅｃｔｏｒｐｒｏｂｌｅｍ，简称ｃｖｅ）是对于一个非格三中的向量　Ｗ，在格中寻找一个向量ｖ，使得ｌｌｗ—ｖＩｌ最小．ＣＶＰ和ＳＶＰ都是ＮＰ完备问题，因此求解起来十分困难．因此，这两个　问题都是可以作为密钥的基础的．论文中对于明文ｍ，其密文Ｓ＝　ｕｂ＂ｍ　＋ｒｉ，其中，公钥　曲是一组劣质级，云　端掌握　和Ｋｐｕｂ，求解明文ｍ　必须计算出Ｋｐｕｂ＂ｍ　Ｋｐｕｂ＂ｍ　求解是一个最接近向量求解问题，这是一个ＣＶＰ问题，　可以被证明是ＮＰ问题．　其次，算法每次加密元组使用的　都是随机，因此，即使是同一明文，两次不同的加密结果也不一样，从而避　免了统计攻击．由于加密过程中随机数ｒ的存在，攻击者即使获得若干组明文密文对，也无法通过其对应关系获　取用户的隐私数据明文信息，或者依靠对应关系计算出用户私钥．因此，本算法可以抵御选择明文攻击（ｃｈｏｓｅｎ—　ｐｌａｉｎｔｅｘｔ　ａｔｔａｃｋ）．本文算法与ＲＢＴ［　】的平移旋转相比安全性更高，ＰＢＴ中，数据的安全性依赖于　明文与密文有　一一对应关系，当泄露一组明文密文对时，僦会泄露，所以ＰＢＴ中的隐私保护处理方法不能抵御选择明文攻击．　当敌手Ａ通过公钥无法计算得到算法私钥，该算法即具有不可攻破性．而本文方法对于敌手　掌握公开参　需要求解最短向量问题，该问题是ＮＰ问题，因此，本文的算法具有不可攻破性．密钥取值位数在　数　咖求解　生成密钥的时候可以调节，当密钥长度是１　０２４位，暴力破解需要２加　次枚举，安全性得到了一定的保证．　４基于ｋ－ｄ　ｔｒｅｅ的隐私保护聚类挖掘方法（ＰＰＣＭ）　４．１基于密文的　．ｄ　ｔｒｅｅ　隐私保护的聚类挖掘过程中，图４所示的ｋ－ｍｅａｎ需要求解出指定范围中的元素，图５所示的ｄｂｓｃａｎ需要求　解核心点．该问题可以转化为求解ＫＮＮ问题，即，ｋ最近邻是否在指定半径内．图６所示的层级聚类需要求解最近　邻问题，事实上就是ＫＮＮ问题的特殊情况．构建高效的高维密文索引，可以高效地进行范围查询和ＫＮＮ查询，　是个亟需解决的困难问题．本文在混淆编码的基础上构建了密文ｋ．ｄｔｒｅｅ，用于聚类挖掘中的性能优化．用户将数　据上传到云服务提供商之前，构建密文肛　ｔｒｅｅ（￣图７所示）．　崔一辉等：一种基于格的隐私保护聚类数据挖掘方法　２３０３　Ｆｉｇ．４　Ｒａｎｇｅ　ｑｕｅｒｙ　ｐｒｏｂｌｅｍ　ｏｆ　ｋ－ｍｅａｎｓ　Ｆｉｇ．５　ＫＮＮ　ｐｒｏｂｌｅｍ　ｏｆ　Ｄｂｓｃａｎ　图４　ｋ－ｍｅａｎｓ范围查询问题　图５　Ｄｂｓｃａｎ的ＫＮＮ问题　Ｆｉｇ．６　Ｎｅａｒｅｓｔ　ｎｅｉｇｈｂｏｒ　ｐｒｏｂｌｅｍ　ｏｆ　ｈｉｅｒａｒｃｈｉｃａｌ　ｃｌｕｓｔｅｒｉｎｇ　Ｆｉｇ．７　Ｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌ　ｃｉｐｈｅｒｔｅｘｔ　ｋ－ｄ　ｔｒｅｅ　ｅｘａｍｐｌｅ　图６层次聚类最近邻问题　图７二维密文缸　ｔｒｅｅ示例　树最邻近搜索的过程如下：从根节点开始，递归地往下移．往左还是往右的决定方法与插入元素的方法　一样（如果输入点在分区面的左边则进入左子节点，在右边则进入右子节点）．一旦移动到叶节点，将该节点当做　目前最佳点．解开递归，并对每个经过的节点运行下列步骤：如果目前所在点比目前最佳点更靠近输入点，则将　其变为目前最佳点．检查另一边子树有没有更近的点，如果有，则从该节点往下找．当根节点搜索完毕后，完成最　邻近搜索．　４．２隐私保护聚类挖掘　首先，用户生成自己的公私钥对　ｂ以及公开参数向量　＝｛‘，ｆ２，．．．，　｝；然后，对数据进行隐私保护　的数据处理，并将处理结果上传到云端，云端调用密文中心点计算算法和密文距离计算算法进行数据挖掘；最　终，将多种挖掘算法的结果返回给用户，避免使用单一算法挖掘难以发现潜在的挖掘聚簇的问题．用户端使用保　持距离的解密算法还原挖掘的最终明文结果．　用户预处理过程中，用户将元组使用第３．３节中的算法将隐私数据进行加密处理后，结果见表５．　Ｔａｂｌｅ　５　Ｐｏｓｔ．ｒｅｌｅａｓｅ　ｄａｔａ　表５发布数据　上传到云服务提供商，同时还需要上传的是加密过程中产生随机数向量的生成参数　．对于云端隐私保护　的数据挖掘结果，用户可以使用第３．４节的算法得到明文数据．当用户可以判断聚类类型时，用户可以直接指定　２３０４　Ｊｏｕｒｎａｌ　ｏｆＳｏｆｔｗａｒｅ软件学报Ｖｏ１．２８，Ｎｏ．９，Ｓｅｐｔｅｍｂｅｒ　２０１７　挖掘算法；否则，云端使用多种聚类挖掘算法进行处理，返回聚类结果给用户．　云端收到用户的聚类分析请求后，根据聚类请求选择合适的聚类算法进行处理．隐私保护的聚类处理核心　问题是密文数据点距离计算问题和均值密文计算问题．ＰＰＫ．ｍｅａｎｓ反复迭代计算密文均值和密文距离，直至簇　的均值不发生变化，即：两次迭代计算均值之间的距离小于某一阈值ａ，见算法４．求解过程中，试用　时间开销．基于层级的聚类需要求解距离最近的元组，该问题是ＫＮＮ问题的特例，使用　此时，利用隐私保护缸　ｔｒｅｅ时间复杂度为Ｏ（１ｏｇｎ）．　算法４．隐私保护的聚类算法ＰＰＫ—ｍｅａｎｓ．　输入：数据集Ｃ、簇的个数　和用户指定的阈值、迭代此处ｎｕｍ；　输出：聚簇Ｇ．　１：ｃｈｏｏｓｅ　０１，Ｃ２，…，ｅ　ａｓ　ｉｎｉｔｉａｌ　ｃｅｎｔｒｏｉｄ　ｔｒｅｅ进行优　化，以质心为中心、两个质心的连线距离的一般为半径，寻找此范围里面的向量，从而大幅度减少了距离计算的　ｔｒｅｅ减少了距离运算，　每个元组查找最近邻的时间复杂度由０（＂）降低为Ｏ（１ｏｇｎ）．ｄｂｓｃａｎ需要求解向量是否为核心点，然后连接核心点，　２：Ｄｏ｛　３：ｇｅｎｅｒａｔｅＳｅａｒｃｈＰａｔｈ（）；　４：ｒａｎｇｅＱｕｅｒｙ（）；　５：调用第３．５节距离的密文计算方法，将每个点指派到最近的中间点，形成　个簇．　６：调用第３．６节密文的中心点计算方法，重新计算每个簇的中间点　７：　ｆ＋十：　８：）ｗｈｉｌｅ（质心发生变化大于指定的阈值ａ　ｏｒ　ｉ＜ｎｕｍ）　基于格的保持距离的加密算法可以精确地计算出向量之间的相对距离以及中心点与各个向量值间的相对　距离．对于ｋ－ｍｅａｎｓ而言，本文的发布方法可以准确地求解均值和密文条件下数据之间的距离，因此可以保证挖　掘的正确性．对于层次聚类而言，本文算法求解的距离具有保持距离相对大小的特性，因此可以选择出当前相距　最小的两个元素．对于ＤＮＳＣＡＮ而言，本文的隐私保护数据发布方法可以准确地求解　Ｂ域中的核心点．　综上所述，数据经过基于格的保持距离数据处理方法处理，上传到云端可以进行聚类挖掘过程中涉及的所　有同态密文计算，因此可以保证挖掘的正确性．　５实验结果与分析　５．１实验环境　实验环境：Ｗｉｎｄｏｗ　７操作系统；ＣＰＵ　ｉｎｔｅｌ　Ｂ９５０　２．１０ＧＨｚ；４．００ＧＢ内存．编程环境：Ｍａｔｌａｂ７．０．１１编译器．　实验数据：本文的实验数据选用加州大学尔湾分校的机器学习数据库中的心脏心律失常数据集的真实数　据＿２　，针对真实数据集规模有限的问题，本文利用正态分布生成了模拟数据集，使用模拟数据集进行较大规模的　实验．参照ＲＢＴ方法【ｌ５１，论文选择数据集中的３列数据：年龄（ａｇｅ）、体重（ｗｅｉｇｈｔ）和心率（ｈｅａｒｔ　ｒａｔｅ）．实验中，随机　选择１０　０００，２０　０００，３０　０００和４０　０００条记录规模分别进行了实验分析．衡量优质基的阈值参数采用　：０．９，加密　过程批处理维度３．　论文研究了一种隐私保护的数据聚类挖掘方法，引入挖掘准确率用于度量隐私保护数据挖掘算法与明文　条件下数据挖掘算法的一致性，见公式（９）（隐私保护的聚类方法准确率与对应的普通明文条件下的数据挖掘结　果进行比较，准确率值越高，表明隐私保护的聚类数据分析方法分析结果越精确）：　ｒａｔｅａｃ￣　＝∑　ｌ　ｆ　ｌ　×　ｌ　　ｌ（９）　其中，Ｃ为数据集，Ｃ　为明文条件下得到的第ｉ个数据聚类，Ｓ　为与之对应的隐私保护数据挖掘聚类方法得到的第　ｉ个密文数据聚类．本文设计的准确率度量方法中，考虑了聚类大小权重因素（ＩＣ，Ｉ／ＩＣＩ）的影响．　本文设计实验，从两个方面对提出的隐私保护聚类数据挖掘方法进行评估，即，挖掘算法的性能和精确度．　崔一辉等：一种基于格的隐私保护聚类数据挖掘方法　２３０５　５．２实验结果分析　本文针对基于格的保持距离的加密算法进行了密钥生成、加密解密性能以及密文计算的时间开销的实验　测试，实验结果证明，本文提供的方法切实可行．与现有的方法相比，聚类挖掘的精度优于现有方法，用户发布数　据时在时间开销有所增加，但是在可接受范围内．实验分别针对基于格的保持距离的加密算法和聚类挖掘算法　进行了分析比较．　５．２．１　基于格的保持距离的加密算法性能分析　密钥生成性能实验结果如图８所示，用户生成密钥的时间开销主要是生成公钥的时间，私钥的生成时问忽　略不计．一次公钥私钥对生成时间约为８ｍｓ．对于初始化密钥过程中的转换矩阵计算取值，实验结果表明，进行３０　次初等变换即可．由图９可以看出，加密的时间要远远超过解密的时间．这是因为加密过程中符合条件的随机数　的生成占用了一定的时间．平均一次加密的时间为Ｏ．４ｍｓ．如实验数据所示，本文提出的算法与现有的方法相比　性能更好．主要是由于一次可以加密或解密一个元组中多列．由图１０可以看出：４０　０００次的密文距离计算只需要　６７ｓ，４０　０００次的中间点求解计算只需要６７ｓ，聚类挖掘所需要的云端的密文计算开销在可接收范围内．考虑到实　际应用中云计算服务器性能能强，实际应用中可以获得更好的隐私数据挖掘效率．　Ｆｉｇ．８　Ｋｅｙ　ｇｅｎｅｒａｔｉｏｎ　ｔｉｍｅ　ｏｖｅｒｈｅａｄ　Ｆｉｇ．９　Ｅｎｃｒｙｐｔｉｏｎ　ａｎｄ　ｄｅｃｒｙｐｔｉｏｎ　ｔｉｍｅ　ｏｖｅｒｈｅａｄ　图８密钥生成时间开销　图９加密解密时间开销　－Ｉ　臣　盈计算中箱譬船间１间点时间　ｌ　。雾　Ｆｉｇ．１　０　ＣＳＰ　ｃａｌｃｕｌａｔｉｏｎ　ｔｉｍｅ　ｏｖｅｒｈｅａｄ　图１０云端密文计算时间开销　５．２．２隐私保护的聚类挖掘方法性能与准确率分析　本文提出的聚类挖掘方法包括用户预处理部分时间开销、云服务提供商挖掘部分时间开销以及与现有方　２３０６　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２８，Ｎｏ．９，Ｓｅｐｔｅｍｂｅｒ　２０１７　法挖掘准确率的比较．　从图１１可以看出：与现有的方法相比，本文ＰＰＣＭ发布数据的时间较高，但是在可以接受的范围内．主要原　因是发布算法基于格的困难为题，提升了隐私保护数据的安全性而带来的时间开销．　从图１２可以看出：密文ｋ－ｍｅａｎ算法的时间复杂度是Ｏ（ｎｌｏｇ（ｎ）），密文层次聚类的时问复杂度为Ｏ（ｎ　），密文　ＤＢＳＣＡＮ时间复杂度０（ｎ）．实验结果表明：实际情况中，ｋ．ｍｅａｎ并非严格按照理论分析的时间复杂度产生时间　开销，由于数据集的差异以及初始中心点的选择不同，ＰＰｋ．ｍｅａｎ算法的时间开销会与理论分析有所差异．从结　果可以看到：隐私保护的层次挖掘算法性能最差，ＰＰＤＢｓｃａｎ性能最好．一方面，这与选取的数据及有关系；另一方　面，３种算法针对不同聚类类型的数据集各有优缺点，并无可比性彳艮多情况下，用户需要执行多种挖掘方法，以便　发现数据集中潜在的聚类．　　●４５００　４ｏｏ０　３５００　３ＯＯＯ　程露西叠髓飘僚护的婚ｆｌ＿婚似　琶　磁翻酶ｌ糕雠护舳艨挑懿　懿　整　酶稿性护纳ｏＩ煳　嫒２５ＯＯ　避２ＯＯＯ　，湖　＇００ｏ　５０ｏ　Ｏ　：　１００１３０　２００００　隧　震　＿　３ＯＯＯＯ　４Ｏｏｏ０　数攒规模　Ｆｉｇ．１　１　Ｕｓｅｒ　ｐｒｅｐｒｏｃｅｓｓｉｎｇ　ｔｉｍｅ　ｏｖｅｒｈｅａｄ　Ｆｉｇ．１　２　Ｐｒｉｖａｃｙ　ｐｒｏｔｅｃｔｉｏｎ　ｃｌｕｓｔｅｒｉｎｇ　ｍｉｎｉｎｇ　ｔｉｍｅ　ｏｖｅｒｈｅａｄ　图ｌ１　用户预处理时间开销　图１２　隐私保护的聚类挖掘时间开销　从图１３可以看出：本文提出的算法与目前准确率最高的ＲＢＴ算法的准确率相当，但是更加安全．在极端情　况下，由于ｋ取值的不同，ｋ匿名挖掘甚至于不能达到实验中的正确率．由于不同的挖掘算法侧重点不同，对于同　一数据返回的结果相差较大，本文的准确率针对３种方法分别进行比较，即：原始数据的ｋ－ｍｅａｎｓ结果与密文环　境下ＰＰｋ－ｍｅａｎｓ的结果进行比对，计算精确率．　’　ｅ　Ｉ．４　１．２　＾　ｔ　赫０．８　德　０　６　４　２　Ｏ　伯Ｏ∞　２∞ｏｏ　３（ＩＯＯＯ　４Ｏ０ｏＯ　徽＿擀规横　Ｆｉｇ．１　３　Ｐｒｉｖａｃｙ　ｐｒｏｔｅｃｔｉｏｎ　ｍｉｎｉｎｇ　ａｌｇｏｒｉｔｈｍ　ａｃｃｕｒａｃｙ　图１３　隐私保护挖掘算法准确率　与现有的方法相比，本文的方法在增强安全的同时，很好地保证了挖掘结果的精度和挖掘的效率．虽然牺牲　了一定效率，但保证了隐私数据的精度和安全性．对于用户而言，挖掘精度对于用户至关重要，挖掘结果的精度　崔一辉等：一种基于格的隐私保护聚类数据挖掘方法　ｐ　２３０７　出现偏差，很可能对于用户决策造成不可弥补的损失　６总结与展望　本文主要研究了云计算环境下支持隐私保护的隐私数据加密发布方法以及密文隐私数据的挖掘方法．首　先，本文提出了一种用于隐私数据发布的基于格的保持距离的加密算法，在该方法的基础上，设计了聚类挖掘过　程中需要的密文计算方法，可以对密文数据进行处理，处理的结果保持同态特性．云服务提供商在保障用户隐私　的条件下，有能力进行聚类挖掘，最终将挖掘结果返回给用户．隐私保护的聚类挖掘方法提供了３种聚类挖掘机　制，用户可以根据自己的数据特征，选择有效的聚类挖掘算法进行云端隐私数据挖掘操作．　ＲｅｆｅＦｅｎｃｅｓ：　［１】Ｎｉ　ｗｗ，Ｃｈｅｎ　Ｇ，Ｃｈｏｎｇ　ＺＨ，Ｗｕ　ＹＪ．Ｐｒｉｖａｃｙ—Ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ｐｕｂｌｉｃａｔｉｏｎ　ｆｏｒ　ｃｌｕｓｔｅｒｉｎｇ．Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ，２０１２，４９（５）：１０９５—１　１０４．（ｉｎ　Ｃｈｉｎｅｓｅ　ｗｉｔｈ　Ｅｎｇｌｉｓｈ　ａｂｓｔｒａｃｔ）　Ｄｉｎｇ　Ｙ，Ｗａｎｇ　ＨＭ，Ｓｈｉ　ＰＣ，Ｗｕ　ＱＢ，Ｄａｉ　ＨＤ，Ｆｕ　ＨＹ．Ｔｒｕｓｔｅｄ　Ｃｌｏｕｄ　Ｓｅｒｖｉｃｅ．Ｃｈｉｎｅｓｅ　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒｓ，２０１５，３８（１）：１３３—１４９　（ｉｎ　Ｃｈｉｎｅｓｅ　ｗｉｔｈ　Ｅｎｇｌｉｓｈ　ａｂｓｔｒａｃｔ）．【ｄｏｉ：１Ｏ．３７２４／ＳＰ．Ｊ．１０１６．２０１５．００１３３］　Ｗｕ　ＸＤ，Ｚｈｕ　ＸＱ，Ｗｕ　ＧＱ，Ｄｉｎｇ　Ｗ．Ｄａｔａ　ｍｉｎｉｎｇ　ｗｉｔｈ　ｂｉｇ　ｄａｔａ．ＩＥＥＥ　Ｔｒａｎｓ．ｏｎ　Ｋｎｏｗｌｅｄｇｅ　ａｎｄ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，２０１４，２６（１）：　９７—１０７．【ｄｏｉ：１０．１　１０９／ＴＫＤＥ．２０１３．１０９］　Ａｇｒａｗａｌ　Ｒ，Ｓｒｉｋａｎｔ　Ｒ．Ｐｒｉｖａｃｙ—Ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ｍｉｎｉｎｇ．ＡＣＭ　Ｓｉｇｍｏｄ　Ｒｅｃｏｒｄ，２０００，２９（２）：４３９－４５０．【ｄｏｉ：１Ｏ．１　１４５／３４２００９．３３５４３８］　Ｚｈｏｕ　ＳＧ，Ｌｉ　Ｆ，Ｔａｏ　ＹＦ，Ｘｉａｏ　ＸＫ．Ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖａｔｉｏｎ　ｉｎ　ｄａｔａ　ａｐｐｌｉｃａｔｉｏｎｓ：Ａ　ｓｕｒｖｅｙ．Ｃｈｉｎｅｓｅ　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒｓ，２００９，３２（５）：　８４７—８６１（ｉｎ　Ｃｈｉｎｅｓｅ　ｗｉｔｈ　Ｅｎｇｌｉｓｈ　ａｂｓｔｒａｃｔ）．［ｄｏｉ：１０．３７２４／ＳＰ．Ｊ．１０１６．２００９．００８４７】　Ｍｏｈａｍｍｅｄ　Ｎ，Ｃｈｅｎ　Ｒ，Ｆｕｎｇ　ＢＣＭ，Ｙｕ　ＰＳ．Ｄｉｆｆｅｒｅｎｔｉａｌｌｙ　ｐｒｉｖａｔｅ　ｄａｔａ　ｒｅｌｅａｓｅ　ｆｏｒ　ｄａｔａ　ｍｉｎｉｎｇ．Ｉｎ：Ｐｒｏｃ．ｏｆ　ｔｈｅ　１　７ｔｈ　ＡＣＭ　ＳＩＧＫＤＤ　Ｉｎｔ’１Ｃｏｎｆ．ｏｎＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙ　ａｎｄＤａｔａＭｉｎｉｎｇ．ＡＣＭ　Ｐｒｅｓｓ，２０１１．４９３－５０１．［ｄｏｉ：１０．１１４５／２０２０４０８．２０２０４８７】　Ａｌｌａｒｄ　Ｔ，Ｈ６ｂｒａｉｌ　Ｇ，Ｍａｓｓｅｇｌｉａ　Ｆ，Ｐａｃｉｔｔｉ　Ｅ．Ｃｈｉａｒｏｓｃｕｒｏ：Ｔｒａｎｓｐａｒｅｎｃｙ　ａｎｄ　ｐｒｉｖａｃｙ　ｆｏｒ　ｍａｓｓｉｖｅ　ｐｅｒｓｏｎａｌ　ｔｉｍｅ－ｓｅｒｉｅｓ　ｃｌｕｓｔｅｒｉｎｇ．Ｉｎ：　Ｐｒｏｃ．ｏｆ　ｔｈｅ　２０１５　ＡＣＭ　ＳＩＧＭＯＤ　Ｉｎｔ’１　Ｃｏｎｆ．ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ．ＡＣＭ　Ｐｒｅｓｓ，２０１５．７７９—７９４．［ｄｏｉ：１０．１１４５／２７２３３７２．　２７４９４５３］　　Ｍ，Ｓｃｈｎｅｉｄｅｒ　Ｊ，Ｖａｓｓｉｌｉａｄｉｓ　ＶＧ．Ｏｎ　ｄａｔａ　ｐｕｂｌｉｓｈｉｎｇ　ｗｉｔｈ　ｃｌｕｓｔｅｒｉｎｇ　ｐｒｅｓｅｒｖａｔｉｏｎ．ＡＣＭ　Ｔｒａｎｓ．ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　［８】　Ｖｌａｃｈｏｓｆｒｏｍ　Ｄａｔａ（ＴＫＤＤ），２０１５，９（３）：２３ｌ【ｄｏｉ：１０．１　１４５／２７００４０３］　【９】　Ｇｉａｎｎｏｔｔｉ　Ｆ，Ｌａｋｓｈｍａｎａｎ　ＬＶＳ，Ｍｏｎｒｅａｌｅ　Ａ，Ｐｅｄｒｅｓｃｈｉ　Ｄ，Ｗａｎｇ　Ｈ．Ｐｒｉｖａｃｙ－Ｐｒｅｓｅｒｖｉｎｇ　ｍｉｎｉｎｇ　ｏｆ　ａｓｓｏｃｉａｔｉｏｎ　ｕｌｒｅｓ　ｆｒｏｍ　ｏｕｔｓｏｕｒｃｅｄ　ｔｒａｎｓａｃｔｉｏｎ　ｄａｔａｂａｓｅｓ．Ｓｙｓｔｅｍｓ　Ｊｏｕｒｎａｌ，ＩＥＥＥ，２０１３，７（３）：３８５—３９５．［ｄｏｉ：１０．１　１０９／ＪＳＹＳＴ．２０１２．２２２１８５４】　－Ｊａｈｎｋｅ　ＪＨ．Ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｄｅｃｉｓｉｏｎ　ｔｒｅｅ　ｌｅａｒｎｉｎｇ　ｕｓｉｎｇ　ｕｎｒｅａｌｉｚｅｄ　ｄａｔａ　ｓｅｔｓ．ＩＥＥＥ　Ｔｒａｎｓ．ｏｎ　Ｋｎｏｗｌｅｄｇｅ　ａｎｄ　［１Ｏ】　Ｆｏｎｇ　ＰＫ，ＷｅｂｅｒＤａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，２０１２，２４（２）：３５３—３６４．【ｄｏｉ：１０．１　１０９／ＴＫＤＥ．２０１０．２２６］　Ｊｏｈｎｓｏｎ　Ａ，Ｓｈｍａｔｉｋｏｖ　Ｖ．Ｐｒｉｖａｃｙ—Ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ｅｘｐｌｏｒａｔｉｏｎ　ｉｎ　ｇｅｎｏｍｅ－ｗｉｄｅ　ａｓｓｏｃｉａｔｉｏｎ　ｓｔｕｄｉｅｓ．Ｉｎ：Ｐｒｏｃ．ｏｆ　ｔｈｅ　１９ｔｈ　ＡＣＭ　ＳＩＧＫＤＤ　Ｉｎｔ’１　Ｃｏｎｆ．ｏｎ　ｎｏｗｌｅｄｇｅ　ＫＤｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．ＡＣＭ　Ｐｒｅｓｓ，２０１３．１０７９－１０８７．【ｄｏｉ：１０．１　１４５／２４８７５７５．２４８７６８７］　ｕ　Ｃ，Ｎｅｐａｌ　Ｓ，Ｐａｎｄｅｙ　Ｓ，Ｃｈｅｎ　ＪＪ．Ａ　ｐｒｉｖａｃｙ　ｌｅａｋａｇｅ　ｕｐｐｅｒ　ｂｏｕｎｄ　ｃｏｎｓｔｒａｉｎｔ－ｂａｓｅｄ　ａｐｐｒｏａｃｈ　ｆｏｒ　ｃｏｓｔ－ｅｆｆｅｃｔｉｖｅ　ｐｒｉｖａｃｙ　［１２】　Ｚｈａｎｇ　ＸＹ，Ｌｉｐｒｅｓｅｒｖｉｎｇ　ｏｆ　ｉｎｔｅｒｍｅｄｉａｔｅ　ｄａｔａ　ｓｅｔｓ　ｉｎ　ｃｌｏｕｄ．ＩＥＥＥ　Ｔｒａｎｓ．ｏｎ　Ｐａｒａｌｌｅｌ　ａｎｄ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｓｙｓｔｅｍｓ，２０１３，２４（６）：１　１９２—１２０２．【ｄｏｉ：　１０．１　１０９／ＴＰＤＳ．２０１２．２３８］　ｙｐｔａｎａｌｙｓｉｓ　ｏｆ　ｔｈｅ　ｇｏｌｄｒｅｉｃｈ—ｇｏｌｄｗａｓｓｅｒ—ｈａｌｅｖｉ　ｃｒｙｐｔｏｓｙｓｔｅｍ　ｆｒｏｍ　ｃｒｙｐｔｏ’９７．Ｉｎ：Ｐｒｏｃ．ｏｆ　ｔｈｅ　Ａｎｎｕａｌ　Ｉｎｔ’１　Ｃｒｙｐｔｏｌｏｇｙ　［１３】　Ｎｇｕｙｅｎ　Ｐ．ＣｒＣｏｎｆ．Ｂｅｒｌｉｎ，Ｈｅｉｄｅｌｂｅｒｇ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，１９９９．２８８—３０４．［ｄｏｉ：１０．１００７／３・５４０－４８４０５—１１８】　　Ｘ，Ｚｈａｎｇ　Ｙ．Ｅｑｕａｌｌｙ　ｃｏｎｔｒｉｂｕｔｏｒｙ　ｐｒｉｖａｃｙ—ｐｒｅｓｅｒｖｉｎｇ　ｋ－ｍｅａｎｓ　ｃｌｕｓｔｅｒｉｎｇ　ｏｖｅｒ　ｖｅｒｔｉｃａｌｌｙ　ｐａｒｔｉｔｉｏｎｅｄ　ｄａｔａ．Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍｓ，　［１４】　Ｙｉ２０１３，３８（１）：９７－１０７－【ｄｏｉ：１０．１０１６／ｊ．ｉｓ．２０１２．０６．００１］　ｉｖｅｉｒａ　ＳＲＭ，Ｚａｉａｎｅ　ＯＲ．Ａｃｈｉｅｖｉｎｇ　ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖａｔｉｏｎ　ｗｈｅｎ　ｓｈａｒｉｎｇ　ｄａｔａ　ｆｏｒ　ｃｌｕｓｔｅｒｉｎｇ．Ｉｎ：Ｐｒｏｃ．ｏｆ　ｔｈｅ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｓｅｃｕｒｅ　［１５］　ＯｌＤａｔａ　Ｍａｎａｇｅｍｅｎｔ　ｉｎ　Ｃｏｎｊｕｎｃｔｉｏｎ　ｗｉｔｈ　ＶＬＤＢ．Ｂｅｒｌｉｎ，Ｈｅｉｄｅｌｂｅｒｇ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２００４．６７－８２．［ｄｏｉ：１Ｏ．１００７／９７８－３－５４０－　３００７３－１＿６］　【１６］　Ｉｓｌａｍ　ＭＺ，Ｂｒａｎｋｏｖｉｃ　Ｌ．Ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ｍｉｎｉｎｇ：Ａ　ｎｏｉｓｅ　ａｄｄｉｔｉｏｎ￣ａｍｅｗｏｒｋ　ｕｓｉｎｇ　ａ　ｎｏｖｅｌ　ｃｌｕｓｔｅｒｉｎｇ　ｔｅｃｈｎｉｑｕｅ　Ｋｎｏｗｌｅｄｇｅ－Ｂａｓｅｄ　Ｓｙｓｔｅｍｓ，２０１１，２４（８）：１２１４—１２２３．［ｄｏｉ：１０．１０１６／ｊ．ｋｎｏｓｙｓ．２０１１．０５．Ｏｌ１］　２３０８　Ｊｏｕｒｎａｌ　ｏｆＳｏｆｔｗａｒｅ软件学报Ｖｏ１．２８，Ｎｏ．９，Ｓｅｐｔｅｍｂｅｒ　２０１７　【１７】　Ｚｂｕ　Ｙ，Ｌｉｕ　Ｌ．Ｏｐｔｉｍａｌ　ｒａｎｄｏｍｉｚａｔｉｏｎ　ｆｏｒ　ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ｍｉｎｉｎｇ．Ｉｎ：Ｐｒｏｃ．ｏｆ　ｔｈｅ　ｌＯｔｈ　ＡＣＭ　ＳＩＧＫＤＤ　Ｉｎｔ’ｌ　Ｃｏｎｆ．ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．ＡＣＭ　Ｐｒｅｓｓ，２００４．７６１—７６６．［ｄｏｉ：１Ｏ．１　１４５／１０１４０５２．１０１４１５３］　　ＷＷ，Ｌｉｕ　ＴＴ，Ｚｈａｎｇ　Ｙ．Ａ　ｐｒｉｖａｃｙ－ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ｐｕｂｌｉｓｈｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｃｌｕｓｔｅｒｉｎｇ　ａｐｐｌｉｃａｔｉｏｎ．Ｊｏｕｒｎａｌ　ｏｆ　［１８］　Ｃｈｏｎｇ　ＺＨ，ＮｉＣｏｍｐｕｔｅｒ　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ，２０１Ｏ，４７（１２）：２０８３—２０８９（ｉｎ　Ｃｈｉｎｅｓｅ　ｗｉｔｈ　Ｅｎｇｌｉｓｈ　ａｂｓｔｒａｃｔ）．　　ＹＰ，Ｃｈｅｎ　ＭＨ，Ｌｉ　ＱＷ，Ｚｈａｎｇ　Ｗ．Ｅｎａｂｌｉｎｇ　ｍｕｌｔｉｌｅｖｅｌ　ｔｒｕｓｔ　ｉｎ　ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ｍｉｎｉｎｇ．ＩＥＥＥ　Ｔｒａｎｓ．ｏｎ　Ｋｎｏｗｌｅｄｇｅ　ａｎｄ　【１９］　ＬｉＤａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，２０１２，２４（９）：１５９８－１６１２．［ｄｏｉ：１０．１１０９／ＴＫＤＥ．２０１１．１２４］　■ｒｉｂａｓ　Ｇ，Ｔｏｒｒａ　Ｖ，Ｅｒｏｌａ　Ａ，Ｃａｓｔｅｌｌａ－Ｒｏｃａ　Ｊ．Ｕｓｅｒ　ｋ－ａｎｏｎｙｍｉｔｙ　ｆｏｒ　ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ｍｉｎｉｎｇ　ｏｆ　ｑｕｅｒｙ　ｌｏｇｓ．　［２Ｏ］　Ｎａｖａｒｒｏ　ＡｒＩｎｆｏｒｍａｔｉｏｎ　Ｐｒｏｃｅｓｓｉｎｇ＆Ｍａｎａｇｅｍｅｎｔ，２０１２，４８（３）：４７６—４８７．［ｄｏｉ：１０．１Ｏｌ６／ｊ．ｉｐｍ．２０１　１．０１．００４］　［２１］　Ｘｉａｏ　Ｘ，Ｙｉ　Ｋ，Ｔａｏ　Ｙ．Ｔｈｅ　ｈａｒｄｎｅｓｓ　ａｎｄ　ａｐｐｒｏｘｉｍａｔｉｏｎ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　１－ｄｉｖｅｒｓｉｔｙ．Ｉｎ：Ｐｒｏｃ．ｏｆ　ｔｈｅ　１　３ｔｈ　Ｉｎｔ’１　Ｃｏｎｆ．ｏｎ　Ｅｘｔｅｎｄｉｎｇ　Ｄａｔａｂａｓｅ　Ｔｅｃｈｎｏｌｏｇｙ．ＡＣＭ　Ｐｒｅｓｓ，２０１０．１３５—１４６．［ｄｏｉ：１０．１１４５／１７３９０４１．１７３９０６０］　ｉｒｍ　ｆｏｕｎｄａｔｉｏｎ　ｆｏｒ　ｐｒｉｖａｔｅ　ｄａｔａ　ａｎａｌｙｓｉｓ．Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　ｏｆ　ｔｈｅ　ＡＣＭ，２０１　１，５４（１）：８６—９５．【ｄｏｉ：１０．１　１４５／１８６６７３９．　［２２】　Ｄｗｏｒｋ　Ｃ．Ａ　ｆ１　８６６７５８］　［２３】　Ｍｏｈａｎ　Ｐ，Ｔｈａｋｕｒｔａ　Ａ，Ｓｈｉ　Ｅ，Ｓｏｎｇ　Ｄ，Ｃｕｌｌｅｒ　ＤＥ．ＧＵＰＴ：Ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ａｎａｌｙｓｉｓ　ｍａｄｅ　ｅａｓｙ．Ｉｎ：Ｐｒｏｃ．ｏｆ　ｔｈｅ　２０１２　ＡＣＭ　ＳＩＧＭＯＤ　Ｉｎｔ’１　Ｃｏｎｆ．ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆＤａｔａ．ＡＣＭ　Ｐｒｅｓｓ，２０１２．３４９－３６０．【ｄｏｉ：１０．１　１４５／２２１３８３６．２２１３８７６］　ｏｕｇｈ　ＤＭ．Ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ｏｂｆｕｓｃａｔｉｏｎ　ｆｏｒ　ｉｎｈｅｒｅｎｔｌｙ　ｃｌｕｓｔｅｒｅｄ　ｄａｔａ．Ｉｎｔ’１　Ｊｏｕｒｎａｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　ａｎｄ　［２４］　Ｐａｒａｍｅｓｗａｒａｎ　Ｒ，ＢｌＣｏｍｐｕｔｅｒ　Ｓｅｃｕｒｉｔｙ，２００８，２（１）：４—２６．【ｄｏｉ：１０．１５０４／ＩＪＩＣＳ．２００８．０１６８１９】　ｓｓｉｍ　Ｋ，Ｒａｓｋｈｏｄｎｉｋｏｖａ　Ｓ，Ｓｍｉｔｈ　Ａ．Ｓｍｏｏｔｈ　ｓｅｎｓｉｔｉｖｉｔｙ　ａｎｄ　ｓａｍｐｌｉｎｇ　ｉｎ　ｐｒｉｖａｔｅ　ｄａｔａ　ａｎａｌｙｓｉｓ．Ｉｎ：Ｐｒｏｃ．ｏｆ　ｔｈｅ　３９ｔｈ　Ａｎｎｕａｌ　ＡＣＭ　［２５］　ＮｉＳｙｍｐ．ｏｎ　Ｔｈｅｏｒｙ　ｏｆＣｏｍｐｕｔｉｎｇ．ＡＣＭ　Ｐｒｅｓｓ，２００７．７５—８４．【ｄｏｉ：１０．１　１４５／１２５０７９０．１２５０８０３】　　ｒｅｐｏｓｉｔｏｒｙ　ｏｆ　ｍａｃｈｉｎｅ　ｌｅａｒｎｉｎｇ　ｄａｔａｂａｓｅｓ．Ｉｒｖｉｎｅ：Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｃａｌｉｆｏｒｎｉａ，Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　ａｎｄ　［２６］　Ｂｌａｋｅ　ＣＬ，Ｍｅｒｚ　ＣＪ．ＵＣＩＣｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ．１９９８．ｈｔｔｐ：／／ｗｗｗ．ｉｃｓ．ｕｃｉ．ｅｄｕ／－ｍｌｅａｒｒｄＭＬＲｅｐｏｓｉｔｏｒｙ．ｈｔｍｌ　附中文参考文献：　［１］倪巍伟，陈耿，崇志宏，吴英杰．面向聚类的数据隐藏发布研究．计算机研究与发展，２０１２，４９（５）：１０９５－１１０４．　［２］丁滟，王怀民，史佩昌，吴庆波，戴华东，富弘毅．可信云服务．计算机学报，２０１５，３８（１）：１３３－１４９．【ｄｏｉ：１０．３７２４／ＳＰ．Ｊ．１０１６．２０１５．００１３３］　■［５］周水庚，李丰，陶宇飞，肖小奎．面向数据库应用的隐私保护研究综述．计算机学报，２００９，３２（５）：８４７－８６１．【ｄｏｉ：１０．３７２４／ＳＰ．Ｊ．１０１６　２００９．００８４７］　ｆ１８］崇志宏，倪巍伟，刘腾腾，张勇．一种面向聚类的隐私保护数据发布方法．计算机研究与发展，２０１０，４７（１２）：２０８３—２０８９．　崔一辉（１９８１一），男，陕西西安人，硕士，主　要研究领域为应用密码学，云安全，隐私　保护．　史成￣（１９９４－－），男，学士，主要研究领域为　应用密码学，云安全，隐私保护．　宋伟（１９７８一），男，博士，副教授，主要研究　领域为应用密码学，云安全，隐私保护．　程芳权（１９８５－），男，博士，主要研究领域为　应用密码学．云安全，隐私保护．　王占兵（１９９２－－），男，硕士，主要研究领域为　应用密码学，云安全，隐私保护．