论文部分内容阅读
复杂的网络中,如生物网络、社交网络,经常存在着数据的不确定性。这些不确定性存在的原因有很多,如原始数据不准确、获取技术方式不精确、使用粗粒度的数据集合、满足特殊应用、隐私保护等,这些不精确的图数据构成了不确定图模型。在不确定图问题中,一个基本的问题就是不确定图的K近邻查询问题。在现在的研究中,关于不确定图的K近邻查询主要集中在基于可能世界模型获取节点之间的概率,进而得出K个近邻节点集合上。但是这种基于可能世界的不确定图模型的查询时间复杂度已被证明是个#P问题。为了解决该问题,近年来很多学者在研究很多方法,其中在时间和准确率上有显著效果的是抽样算法。在Chernoff Hoeffding定理的引导下,抽样算法可以平衡时间和准确率两个变量的关系。虽然抽样算法可在多项式时间内给出结果,但当使用它在线查询或者进行频繁查询时,其依然表现出较长的时间等待问题。基于目前的研究现状,本文基于学习式搜索思想,采用BP神经网络学习模型,提出基于BP网的不确定图K近邻查询算法。主要的研究包括:首先给出单源点的BP-K近邻查询算法(基于BP网的不确定图的K近邻),包括BP-K近邻查询算法处理不确定图节点间概率计算的机器学习思想与训练数据集形式。在单源点的BP-K近邻查询算法的基础上,使用Cantor数方法描述了不确定图中的节点对的表示方法,使用抽样算法得出训练集,把单源点的BP-K近邻查询算法扩到多源点的BP-K近邻查询算法,在整个不确定图中进行BP网的拟合。本文提出了几点尝试:(1)在理论和实验上验证传统的不确定图K近邻查询算法耗时较长,难以处理实际问题中的图结构数据。(2)验证抽样算法在Chernoff Hoeffding定理指导下的准确率及该算法在计算部分节点间概率时时间的高效性,并证明该算法在线查询时会出现明显的时间等待问题。(3)从真实的数据集中抽取部分数据集进行BP网的拟合训练,训练网络的拟合能力和泛化能力,找到合适的BP学习模型进行预测,可以基本拟合该不确定图样本数据。(4)验证BP-K近邻算法解决实际问题的可行性。实验证明BP-K近邻查询算法的查全率较高,并给出传统算法、抽样算法和BP-K近邻算法计算不确定图K近邻查询时的时间对比。