论文部分内容阅读
随着信息技术日新月异的的发展变化,在越来越多的领域中,研究者开始使用图这种数据结构来表示和存储数据对象之间的关系。这些数据被称为图数据。图数据中包含了大量的我们希望获得的知识和信息。如何从图数据中挖掘数据对象间的结构特征、形成规律及存在模式等知识,具有重要学术价值和实际意义。在许多领域的实际引用中,由于数据获取技术的客观局限、数据的不精确性等原因,获得的数据天然的带有不确定性。这种带有不确定性的图数据,称之为不确定图数据,例如生物信息学中的蛋白质相互作用网络,无线传感器网络的节点间的拓扑结构等等。在图挖掘技术中,频繁子图模式挖掘是非常重要且被广泛研究应用的一类。图数据中挖掘频繁子图模式可以获得很多有价值的信息,在诸如蛋白质相互作用网络研究,无线传感器网络研究等领域中得到了广泛的重视和研究。而如何在图数据库中进行频繁子图模式挖掘,得到了越来越多的关注。图数据库中挖掘频繁子图模式的难点之处在于,不仅存在着海量的可能子图模式需要检验,而且还需要做极大数量的子图同构性测试来判别图中是否蕴含一个给定的模式。而若处理的图数据带有不确定性,则第二个难点更为突出。本文综合运用数据挖掘的相关理论、概率论的基本知识和算法学,以最小化不确定图数据库中挖掘频繁子图模式算法运行的时间开销和空间开销为目的,研究期望语义下的不确定图数据库中频繁子图模式挖掘算法。主要的研究成果提供一个在不确定图数据库中能够有效挖掘频繁子图模式的算法MUSIC(Mining Uncertain Subgraph Patterns With Index of Connectivity andEdge),该算法运用建立在不确定图数据库上的UG索引(Uncertain Graph)来减少为了挖掘频繁子图模式所需要的比较次数。MUSIC算法根据apriori性质可以有效地枚举可能的子图模式,而建立在不确定图数据库上的UG索引则可被用来减少为了计算每个候选模式的期望支持度所进行的比较次数。本文还提供额外的基于待检验蕴含图调度和剪枝的优化策略,这样可以有效的提高算法的性能。通过在基于三个真实数据集及人工数据集上的不确定图数据库上的一系列实验,通过与代表该领域最新水平MUSE算法的性能指标进行对比,显示了本算法可以有效的降低在不确定图数据库中挖掘频繁子图模式所需的时间和空间开销。