论文部分内容阅读
k近邻是离群数据挖掘中的一种常用查询方法,但传统的k近邻查询方法难以适应海量高维数据集,在低维空间中表现良好的k近邻查询方法,在高维空间中均出现不同程度的恶化,尤其当数据量急剧增加时,其k近邻查询方法处理效率低,难以满足海量数据分析的实际需求。此外,大多数k近邻查询方法视所有属性同等重要,而在实际应用中,忽略属性之间的差异,将无法查询到有意义的近邻数据对象。本文针对海量高维数据集,对加权k近邻查询与离群数据挖掘算法展开深入研究。其主要研究成果如下:(1)给出了一种基于加权k近邻查询的离群数据挖掘算法WKNNOM。该算法利用信息熵度量数据集中所有属性的重要程度,并采用Z-order空间填充曲线将高维空间数据编码,映射成Z值,以此作为查询加权k近邻的依据;在兼顾每个对象与其加权k近邻个体差异基础上,利用加权k近邻,给出了一种离群数据挖掘算法;利用人工和UCI标准数据集,实验验证了该算法的可行性和准确性。(2)采用Hadoop并行计算平台,给出了一种加权k近邻的并行查询方法及离群数据并行挖掘算法WKNNOM-MR。该算法首先对输入数据随机抽样,并采用信息熵计算样本集中各个属性权值;其次在各计算节点上,利用属性权值和原始数据集生成Z-order空间填充曲线,并计算每个数据对象的Z值;再次采用LSH策略对k近邻候选集进行划分,将相近的Z值对象放置到同一计算节点,以此缓解计算节点间的数据倾斜问题并改善加权k近邻查询的准确性;然后根据每个对象与其加权k近邻之间的距离计算离群因子,给出了一种离群数据并行挖掘算法;最后在Hadoop集群上,采用人工合成、UCI标准数据集和天体光谱数据,实验验证了该算法的可扩展性和可伸缩性。