论文部分内容阅读
随着当代计算机技术和信息技术的不断发展和应用,各种领域都通过越来越多的手段产生大量的数据。但由于数据收集方式造成的误差,和数据本身的不确定性等原因,使得采集到的数据往往都是不确定的,这就是不确定数据。它是一种不同于传统类型的新型数据,数据中的不确定性采用概率或置信度表达。不确定数据上的最近邻查询是从目标数据集中查找距离查询对象较近的对象,在诸如决策制定、模式识别、数据挖掘等应用中具有重要的应用。而相互最近邻查询作为一种特殊的最近邻查询,近些年引起了越来越多研究者的关注。 近些年来国内外对不确定数据上的各种最近邻查询及其相关问题进行了深入而广泛的研究,而不确定数据上的相互最近邻查询相对较复杂,目前关于它的研究尚少。传统的算法也无法应用于不确定数据上的相互最近邻查询,因此本文对不确定数据上的相互最近邻查询进行了研究,并提出了在三种不同应用场景下的相互最近邻查询算法。本文的主要工作如下: 首先,根据候选对象之间的空间关系和不确定性,设计了一组用于对候选对象集合进行裁剪的裁剪规则,分别是最小最大距离裁剪规则,几何覆盖裁剪规则,半空间裁剪规则以及概率裁剪规则,其中前三种裁剪规则都属于几何裁剪。 其次,运用上述的裁剪规则,分别给出了三种不同应用场景下的相互最近邻查询算法:(1)当查询数据集和目标数据集分别为不确定数据集和点数据集,查询对象是一个不确定数据对象时,在目标数据集中查找前Top k个以较大概率成为查询对象的相互最近邻的点对象;(2)当查询数据集和目标数据集分别为点数据集和不确定数据集,查询对象是一个点对象时,在目标数据集中查找以大于给定阈值的概率成为查询对象的相互k近邻的不确定数据对象;(3)当查询数据集和目标数据集为同一个不确定数据集,查询对象是一个不确定对象时,在数据集中查找以大于阈值的概率成为查询对象的相互最近邻的不确定数据对象。 最后,实验结果表明,上述的算法具有较好的收敛性和稳定性,能更好地应用于不确定数据上的相互最近邻查询。