基于众包平台针对可达性查询的不确定图清洗研究

发布时间：2020-07-16 07:09

【摘要】：图数据库在大数据时代扮演着重要且核心的角色,其中不确定图有着广泛的应用,如合著者关系网、生物分子网络、社交网络等。本文研究的对象是仅边具有存在概率的不确定图,研究的目标是提高不确定图上可达性查询的可靠性。然而,目前关于不确定图清洗的研究仅针对限定距离的可达性查询,且假设众包平台对不确定图的清洗结果是完全正确的。因此,首先研究基于精确众包平台、针对同时限定距离与标签的可达性查询的不确定图清洗;基于此,考虑众包噪声对清洗结果的影响,进行基于非精确众包平台针对可达性查询的不确定清洗的研究。为此,归纳了有关不确定图清洗的研究方法、基础概念与可达率计算方法,提出了进行不确定图清洗的初步理论。其次,对于无众包噪声的情况,设计了基于精确众包的不确定图清洗框架;提出了可以准确快速地计算概率可达性的算法;为减小对最优待清洗边的搜索范围,设计了改进的路径搜索算法以提取有效边;依次设计了不确定图的单边清洗与多边清洗算法,并通过实验验证了清洗算法的选边准确性与高效性。然后,对于基于非精确众包的不确定图清洗,建立了融入众包噪声到清洗结果的不确定图清洗模型;从数值层面考察了众包噪声对清洗结果的影响,发现如果众包精确度保持在50%以上,依然可以通过清洗目标边来提升查询结果质量。接着,归纳出查询结果质量增益函数(?Q),以考察不同边被清洗后对可达性查询结果可靠性的提升程度;通过分析非精确众包答案对查询结果质量增益的影响,提出并证明:边相关因子P_e~*可以替代查询结果质量增益?Q,作为对不同目标边清洗效果的考察标准,为设计清洗算法奠定了理论基础。之后,基于P_e~*分别设计了基于非精确众包的单边清洗与多边清洗算法;提出了缩小目标边搜索范围的优化技术以提高选边效率,设计了避免大量可达率计算的二次剪枝算法。通过实验证明了提出的清洗算法可以高效准确地选取目标边。最后,通过两个案例分析,简述本文的图清洗研究对其他图查询的应用价值。
【学位授予单位】：华东师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP311.13
【图文】：

关系网,图数,不可靠

华东师范大学硕士学位论文不确定数据然而，由于数据源不可靠、信息丢失及模式不一致等原因，这些知识图谱的质量不甚理想[6]。通常，在一些主流的图数据库中有 69%至 99%的实体数据缺乏完整的属性信息[7]。例如：作者重名可能导致从一些学术网站(DBLP、Google Scholar 等)提取的作者合著关系网不可靠；截至 2016 年，Wikidat仅仅包含全图 2%的人的父亲信息[6]。从某种角度说，在这些不完整的图数据库中，一些实体所缺失的数据是不确定的，即有可能存在也可能不存在或者存在的数量不确定。MarylandStanfordAjim Premji

不确定,可达性,交互网络,限定条件

图 1-2 三种类型的不确定图0.8JiawWei Wang0.3Wei Wang0.90.70.2MusicFashionPoliticsLady GagaA. 边的存在不确定 B. 顶点不确定C. 边的属性不确定

不确定,构成元素

边属性)都可能是不确定的，而一个不确定图至少有一种不确定的构成元素。图1-2 展示了分别包含这三种不确定构成元素的不确定图[5]。其中，顶点不确定的情况一般是实体解析领域的研究对象。本文研究的不确定图仅边的存在性是不确定的，即图中的每条边都有一定的存在概率。这种不确定图是许多应用的基础模型。例如：在机器生成的知识图谱中，由于数据是利用自然语言处理技术从网页文档中提取的，不同实体之间的关系是不确定的；在蛋白质交互网络中，不同蛋BillGatesSergey BrinMarylandStanfordJane StanfordSteveWoznaikJerry YangAjim PremjiWiproYahoo!Googlefoundednationality

【相似文献】