论文部分内容阅读
随着互联网的极大普及和计算机技术、信息管理技术、信息系统的迅猛发展,各行业的数据量激增,在此背景下诞生的KDD(Knowledge Discovery in Databases,知识发现)和DM(Data Mining,数据挖掘)给人们提供了一种新的认识数据和理解数据的智能手段。数据挖掘就是从大量的、不完整的、有噪声的、随机的数据中,提取隐含在其中的、人们事先不知道的、具有潜在价值的信息和知识的过程。序列模式挖掘是数据挖掘研究领域中一个重要的研究课题,其主要研究目的是从大型时序数据库中发现事件之间存在的隐藏的、有趣的序列关系。本文针对序列模式挖掘中的频繁序列挖掘和闭序列挖掘展开研究。为实现序列模式的高效挖掘,本文以传统序列模式挖掘算法为基础,结合序列模式自身的特点,建立了ML-List (Minimal Location List,最小位置表)结构,并基于这种结构提出了一种频繁序列挖掘新算法FSM_BML(Frequent Sequence Mining based on Minimal Location,基于最小位置的频繁序列挖掘)和一种闭序列挖掘新算法FCSM_BASC(Frequent Closed Sequence Mining based on Adjacent Sequence Check,基于相邻序列检测的闭序列挖掘)。本文的研究重点在于减少扫描原始序列数据库中记录的次数,另外,还提出了一种能够加速支持度计算的方法和一种只需在相邻序列间进行的闭合检测方法,主要贡献如下。首先,本文利用相同记录号克服了传统频繁序列挖掘算法中反复扫描原始序列数据库中全部记录或投影数据库中全部投影的弊端。其次,本文提出了一种利用序列的最小位置快速确定搜索的起始位置的方法,加强了搜索序列的针对性,避免了传统频繁序列挖掘算法中全部从序列的最开始进行搜索,从而提高了频繁序列挖掘的效率。再次,本文提出了一种只需在相邻序列间进行子模式检测的闭合检测方法,大大减少了检测范围,且只保留候选闭序列一次,在很大程度上提高了闭序列挖掘的效率。最后,本文提出了一种半避免冗余剪枝方法,可以提前确定部分的非闭序列,并减少了部分支持度的计算,除此之外,本文提出了另一种避免冗余剪枝方法,可以提前确定部分的闭序列,并将那些一定不能扩展成频繁(x+1)-序列的频繁x-序列剪枝,减少了搜索空间。两种剪枝方法提高了闭序列挖掘的效率。实验结果验证了本文所提出的算法的正确性和高效性。