论文部分内容阅读
随着信息获取、存储和传播技术的发展,从大规模数据集中快速获取有用的信息成了众多学科的研究热点。虽然已经有大量的工作致力于探索高效的查询和分析方法,但大部分研究都忽略了实体之间普遍存在的关联。正是这种关联的存在,使得实体间显式或隐式地形成一个巨大的关联网络。基于这种无处不在的关联,不同来源、彼此关联的各种类型数据汇聚到一起,能更为形象地表现综合知识,有利于从多侧面、多视点表达尽可能完整的语义,并挖掘和理解隐含在数据中的知识。关于实体本身内容的研究已经很深入,实体间关联的研究才刚刚起步,而这种相互关联的研究更具有价值;为了更好地捕获实体间的关系,用图模型的顶点表示某个实体及其相关的所有信息,边表示实体间的关联。基于图研究实体关系及其分析技术,能在当前数据检索和分析基础上,进一步加深对现实世界的理解。本文将图相关的理论和技术引入实体关系研究中,以高效的检索和分析为目标,针对实体关系关联分析中的关键技术问题展开研究,包括以下五个部分。(1)针对海量多源实体间关联表达的完整性问题,提出了一种基于实体关系的多视图关联模型,建立了关联模型快速构建算法,能更加全面地表达实体之间的关联关系与隐含知识人们从不同角度感知现实世界中的实体,产生了对实体不同视角的描述,如何更加全面完整地表达海量多源描述中实体间关联关系,是当前的研究热点。传统的关系模型和图模型由于建模着眼点的不同而无法直接表达和操作来自不同数据源的实体关系,因此,我们需要研究新的多源实体关系刻画机制。针对这一问题,论文首先提出了一种描述多源实体关系的多视图关联模型。该模型采用关联模式描述实体之间的关联约束,对各数据源中的实体进行特征和属性抽取,形成实体特征关联图,并将该数据源中所有实体的特征进行聚合,形成该数据源的关联视图,再将所有视图进行融合交联形成多视图关联模型,定义了一组操作算子对模型中的查询和分析操作进行表达。论文还提出了基于关联路径的关联模型构建算法,采用基于特征索引的分块构建技术,改善了模型构建效率,实现了无监督条件下的多视图融合,为无先验知识的关联分析应用提供了一种有效的模型实现方法。以多类型信息检索为例,进一步阐述了关联模型的构建过程以及基于模型的分析效用。理论推导和真实数据集上的实验表明,面向多源数据,论文所建立模型能更加全面地表达实体间的关联关系与隐含知识。(2)针对实体存在属性描述的实体分析问题,研究了一种融合属性描述和关联关系的遗传聚类分析算法,提高了聚类分析质量和效率实体存在丰富的属性描述,在关联图中综合属性信息和关联关系进行实体分析,对从全局分析数据的拓扑结构、实施功能分析具有重要价值。多数已有方法单纯考虑实体属性或关联,导致聚簇结构中实体联系松散或实体属性分布过于随机。针对实体存在属性描述的实体分析问题,论文研究了一种融合属性描述和关联关系的实体聚类分析方法。通过分析通信系统中信息传输机制,对实体聚类分析问题进行建模,将实体属性及关系表示为信息长度,构建描述代价模型。在证明该问题的NPC特性基础上,提出了遗传算法用于实体聚类分析;该算法通过融合属性和关系实现标签优先选择,从而扩展标签传播方法初始化种群,并结合邻居关联实体编码减小机制用于遗传染色体局部变异,减小搜索空间。理论分析表明,该方法无需事先设定聚类的数量,且算法的时间复杂度与属性关联图的规模和平均关联实体数量成正比;通过在多个真实数据集上进行实验,并与典型算法比较,验证了算法的合理性和有效性。(3)针对关联路径存在标签约束的关系分析问题,研究了一种基于划分编码的关系可达性分析方法,改善了大规模关联图上的关系分析效率实体间的关系通过属性或标签约束,判断两个实体之间是否存在给定属性或标签约束的关系,能够有效支持异构数据之间的关联关系推断,对从局部预测和分析不同类型关联关系具有重要的价值。已有研究方法多数没有考虑关系上存在约束的情形,或者在大规模关联图上的分析效率有待改进。针对这一问题,在不同类型约束下,论文提出一种基于递归二分划分的关系可达性计算方法。该算法基于层次划分思想和实体间独立集性质,在保持实体间可达性和约束标签前提下对大规模关联图进行递归划分,以减小需要编码的实体数量;并结合贪婪扩展思想和递归编码机制,为标签约束的可达性查询提供压缩的2-Hop编码。在编码基础上,基于压缩索引快速分析实体间存在约束的关系可达性。论文在理论上证明了该方法的正确性,通过真实和合成数据集上的实验,表明该算法在降低编码大小和构建代价的同时,能够保持较高的分析效率。(4)针对关系存在权重的实体关系分析问题,提出了基于截断过滤策略的模式匹配方法,提高了大规模关联图上的模式匹配分析效率基于现实应用构建的关联模型,实体间关联的紧密程度通常用关系的权重衡量。用户在给出查询模式时,只有考虑实体间关联的紧密程度,才能更准确地刻画满足用户意图的实体及其关系。多数已有的检索和分析方式单纯从实体间关联的视角出发,忽略了关联的紧密程度。针对实体之间关系存在权重描述的现实状况,论文提出了一种权重约束的模式匹配方法,基于用户需求构建实体关系模式,在大规模关联图中查找与之匹配的实体关系组合。该算法基于2-Hop编码覆盖思想,通过遍历裁剪求解实体间的权重约束可达性;基于实体的属性匹配和关系的结构约束,形成初始匹配结果;并通过模式图多距离连接截断和过滤不满足约束的实体,然后将所有实体和关系进行组合形成分析结果。论文在大规模真实数据集和模拟数据集上进行了实验,通过与典型模式匹配方法做比较,验证了算法的可行性和有效性。(5)设计实现了支持多源数据的实体关系关联查询与分析实验系统在综合论文研究成果基础上,设计实现了一个支持多源数据的实体关系关联分析实验系统;一方面,验证了本文所研究方法的有效性和实用性;另一方面,展示了实体关系关联分析的效用及基于此的潜在应用前景。在需求分析的基础上,设计了实验系统的整体框架和物理部署,对实验系统的关键功能模块尤其是查询分析引擎、集成展示框架等进行详细阐述,并在真实数据集上,验证了本文算法并展示了基于实体关系关联分析的应用实例。