论文部分内容阅读
随着信息技术的发展,越来越多的领域开始使用“图”来表示和存储数据对象之间的关系。这种类型的数据被称作“图数据”。近年来,在现实应用中积累了大量的图数据,其中蕴含了大量有用的知识。“图挖掘”能够从图数据中发现数据对象之间关系的存在模式、结构特征与形成规律等知识,因而具有重要研究意义。 在现实世界中,由于数据获取技术的局限、数据不精确性和数据不完整性等原因,数据非确定性在图数据中普遍存在。这种带有非确定性的图数据被称作“非确定图数据”,例如生物信息学中的蛋白质交互网络、无线传感器网络的拓扑结构等。以蛋白质交互网络为例,由于高通量生物实验技术的可靠性不高,因此实验获得的每个蛋白质交互(即网络中的边)未必真实存在,而是具有一定的非确定性,反映该蛋白质交互实际存在的可能性。 由于在非确定图数据中蕴含着大量有用的知识,因此挖掘非确定图数据(简称非确定图挖掘)具有非常重要的意义。然而,现有的方法无法解决非确定图挖掘问题。一方面,传统的图挖掘算法无法解决非确定图挖掘问题,这是因为:第一、传统图数据模型无法描述图数据的非确定性;第二、传统图挖掘问题的定义在非确定图数据上并不适用;第三、非确定图数据使得挖掘间题的固有计算复杂性大大增加,原有的图挖掘算法无法解决这样困难的问题。另一方面,非确定数据挖掘的研究主要关注于非确定关系数据和非确定XML数据,现有的算法无法处理结构复杂的图数据。目前尚无对非确定图数据的模型、存储、查询、分析与挖掘的系统性研究。 本文运用算法学和数据挖掘的相关理论、方法与技术,以最小化时间和空间复杂性、最大化挖掘结果质量为目标,研究非确定图挖掘,包括非确定图数据模型、期望语义下的频繁子图模式挖掘算法、概率语义下的频繁子图模式挖掘算法和top-k极大团挖掘算法。主要研究成果如下: (1)本文提出了一种非确定图数据模型,其中包括非确定图和非确定图数据库的形式化定义,并对模型的语义进行了严格阐述。另外,本文还对该模型进行了简单的扩展,得到了带标记的非确定图数据模型。这些模型是非确定图挖掘算法研究的基础。 (2)本文在期望语义下研究了非确定图数据库上的频繁子图模式挖掘,提出了子图模式的期望支持度来评价子图模式的重要性,并在此基础上形式化定义了期望语义下的频繁子图模式挖掘问题。本文严格地证明了该问题是一个NP-难问题,且计算子图模式的期望支持度是一个#P-难问题。为了降低计算复杂性,本文的方法试图计算一个£一近似频繁子图模式集合,该集合包含全部频繁子图模式和少量非频繁子图模式,但这些非频繁子图模式的期望支持度低于期望支持度闽值minSUp的比例不得超过E。本文提出的近似挖掘算法实际计算一个(6)一近似频繁子图模式集合,任何频繁子图模式均以较高的概率属于该集合,任意期望支持度低于f1-e)minsup的非频繁子图模式均以较低的概率包含于该集合。真实数据上的实验结果表明该近似挖掘算法非常高效,而且挖掘结果的近似质量也非常高。 (3)本文在概率语义下研究了非确定图数据库上的频繁子图模式挖掘,提出了子图模式的妒一频繁概率来评价子图模式的重要性,并在此基础上形式化定义了概率语义下的频繁子图模式挖掘问题。本文严格证明了该问题是一个NP一难问题,且计算子图模式的妒一频繁概率是一个#P一难问题。为了降低计算复杂性,本文的方法试图计算一个£一近似频繁子图模式集合,该集合色含全部频繁子图模式和少量非频繁子图模式,但这些非频繁子图模式的妒一频繁概率不得比(,-频繁概率阈值丁低超过E。本文提出的近似挖掘算法实际计算一个(6)一近似频繁子图模式集合,保证任意频繁子图模式属于该集合的概率不低于《1-6)/2)8,其中s是该子图模式的边数,并且任意妒一频繁概率小于丁-£的非频繁子图模式属于该集合的概率不高于6/2。本文还在理论上给出了算法参数6的设置方法来保证挖掘结果的近似质量。真实数据上的实验结果表明该近似挖掘算法非常高效,而且挖掘结果的近似质量也非常高。 (4)本章研究了非确定图上的top-k极大团挖掘问题,提出了极大团概率来评价顶点子集成为极大团的可能性,形式化地证明了该问题是一个NP-难问题。本章提出了一种在多项式时间内计算顶点子集的极大团概率的算法,并在此基础上提出了一种基于分支限界搜索的挖掘算法。该算法采用了多项高效的裁剪技术、新型的搜索策略与预处理技术。真实数据上的实验结果表明本章提出的算法具有很高的效率,并且将该算法用于蛋白质复合体的预测能大大提高预测的精度。