论文部分内容阅读
随着科学技术的飞速发展,传感器网络、无线射频识别、隐私保护等技术得到了广泛的研究与应用,随之而来也产生了大量的不确定数据。以前人们总是试图使用处理确定数据的方法来处理不确定数据,但是往往得不到正确的结果,因此探索适合于处理不确定数据的挖掘算法显得尤为迫切。本文首先概述了不确定数据产生的原因及其表现形式,并且简要介绍了不确定性方法,在此基础之上提出了不确定数据的模型,总结了几种常用的不确定性算法。由于不确定数据比确定数据要复杂得多,在处理方法上有其特殊性,目前的一些算法,在使用范围和效率上都存在着很大的局限性。本文按照数据的结构化类型分类,将数据分为结构化数据、半结构化数据和非结构化数据,在处理这三类不同的结构类型数据上有着各自不同的方法,并选取了结构化数据和半结构化数据作为本文的研究重点展开研究。本文的主要研究内容如下:(1)关系型数据是一种典型的结构化数据。在我们的工作和生活中应用非常普遍。这种数据表现直观,相对于其他类型的数据,处理起来较为简单。现实世界中普遍存在着不确定关系型数据,而传统的挖掘算法无法适用于此类数据的问题,并且用户希望高效地挖掘出符合要求的信息,目前已有基于约束的不确定数据频繁项挖掘的经典算法-U-FPS算法,但U-FPS算法需要构建频繁模式树,当数据量较大时,会占用大量内存,并且需要大量使用递归调用导致挖掘效率降低。针对该算法的不足,提出了适用于基于约束的不确定数据的新算法—UC-Eclat挖掘算法,该算法不需要构建频繁模式树,而采用了数据库垂直模式求交集的方式来计算支持度的方法,提高了挖掘效率。并通过实验证明了UC-Eclat算法在效率上更优。(2)图型数据是一种半结构化数据。由于图更加适合于用来描绘复杂的数据以及数据之间的关系,所以,越来越多的科技领域试图用图结构来描绘结构复杂的数据对象。目前已有经典频繁子图挖掘算法—DFS算法,但该算法搜索空间过大,从而导致算法执行效率过低。本文针对该算法的不足,提出了子图模式搜索空间裁剪策略,有效地缩减了算法的搜索空间,接下来又提出了一种数据库划分的思想,在此基础上产生了EDFS算法,该算法进一步对搜索空间进行裁剪,相对于最初的深度优先搜索算法,在效率上有了大幅度的提高。最后通过实验证明改进后的算法更优。