论文部分内容阅读
近年来，网络技术不断发展，数据规模成几何增长，通过数据挖掘技术对原始数据提取分析，获得了有价值的知识。然而数据的隐私问题引起了挖掘应用者的高度重视，尤其是在分布式环境下。数据扰动技术是简单高效的隐私保护方法，为了达到隐藏保密信息的效果，多使用噪声对原始数据进行扰动，但其适用于集中式环境中。DBSCAN对簇集使用基于密度的定义，因此它受数据对象中的噪声点影响较小，并且对簇集的形状和大小没有特殊要求。该特性使得DBSCAN算法在隐私保护技术下能够发现更多的簇。然而DBSCAN算法并不是完美无缺的，其算法自身仍存在计算复杂度高、对高维和变密度簇的处理能力差等缺陷，当数据集趋向于海量、稀疏分布时，这种缺陷表现的更为明显。 针对上述问题，本文使用小波变换作为隐私保护方法，其对原始数据扰动的同时降低数据的维度，并使用相应的安全协议保证分布式环境下的交互安全。重新定义临近性度量和核心密度可达链，对基于密度的聚类算法进行改进。进一步降低簇邻接数据对聚类准确度的影响，与基于小波的隐私保护技术形成一个整体，为分布式环境下的数据提供良好的处理环境。本文的主要工作如下: 1)针对DBSCAN算法计算复杂度高、对高维和变密度簇的处理能力差的问题，提出改进的K-DBSCAN算法。使用K近邻来反映数据对象之间的相似性关系，减少对高维和变密度数据的聚类误差。而构建K最近邻时间复杂度较高，为了提高算法的效率，使用kd树的方法有效找出K最近邻，降低计算复杂度。定义核心密度可达链替代密度可达链，用一个仅包含核心点的核心密度可达链来进行扩展聚类，以此提高聚类的准确性; 2)针对现有分布式隐私保护算法无法满足效率与隐私之间较好折衷的问题，提出基于安全多方计算与小波数据扰动相结合的分布式隐私保护聚类算法。各数据方使用小波变换实现数据压缩和信息隐藏，并用属性列的随机重排来防止数据重构可能产生的信息泄露。该算法仅使用压缩重排后的数据参与分布聚类计算，因此计算量和通信量小，算法效率高，而多重保护措施有效保护了隐私数据。因小波变换具有高保真性，所以聚类的准确性受其扰动变换的影响较小。理论分析和实验结果表明，所提算法安全高效，在处理高维数据时全局F测量值和执行效率优于同类算法，解决了效率与隐私之间的折衷问题; 3)该方法在现实生活中具有应用价值，因此设计并实现了基于小波变换的K-DBSCAN隐私保护聚类算法的原型系统。使用数据对系统进行测试，测试的数据分析表明系统运行良好，达到预期效果。