论文部分内容阅读
本文研究基于图结构的数据挖掘问题,即将特定数据组织成图形式的数据结构,然后辅之算法操作,获取有用知识。当前主流的数据挖掘算法所处理的大多是向量型数据,而在物联网以及社会网络等研究领域如果仅采用向量型数据进行表达,则会产生数据的“属性沉没”问题,即不能够有效的表达向量内数据间属性关系,因为这些数据来源于现实世界,具有天然结构性。图结构可以有效避免“属性沉没”,使得数据间属性相关性充分表达,获取比向量更为丰富的额外信息。如何将这些数据组织成图结构,并对这些图数据进行有效操作,成为了数据挖掘领域新的研究热点。频繁子图的查询和图分类是图数据挖掘的核心,也是其它图数据研究的基础。本文通过对已有子图查询和图分类算法的讨论,改进了图的编码表示方法,使得普通无向图的子图查询可扩展至对有向图的操作;提出将抽样策略融入图分类领域,提升了分类模型形成的效率;最后实现了图挖掘在生物信息领域的应用。本文所做的主要工作如下:1、提出的新算法DFSS对gSpan算法做了适用性改进,算法所采用的图编码技术与传统的FSG,FFSM,AGM等算法对图结构的编码均不同,针对有向图数据特点,提出了层级度和连结度概念,可使算法适用范围有效地扩展至对有向图的学习;目前为止,一系列频繁子图的挖掘大都是基于无向图上的知识发现,对直接作用于有向图的挖掘尚且很少。并且所设计算法较先前基于Apriori思想的FSG,AGM等一系列频繁图挖掘算法,在时间复杂度方面有了一定程度的改进,使得挖掘效率得以提升了(m4/n2)倍;实验结果表明在不损失挖掘完整度的前提下,效率是FFSM算法的70—80倍。2、传统的图分类算法由于支持度阈值选择过低导致频繁子模式规模过大进而造成效率过低,阈值选择过高导致重要模式丢失而造成分类精度下降,如FSG和CEP方法;针对这些问题,提出将抽样学习策略引入图分类领域,同时提出了点的平均度概念,在保持分类准确率前提下通过顶点平均度的计算抽样选取代表性子模式,结合CEP所给出的频繁闭显露模型,设计出一种新的图特征(分类规则)提取方法,解决了CEP算法由于支持度阈值设置过低而导致的无法计算现象,大大提升了分类效率;并通过实验证明本文算法优于现有的一些主流算法。3、提出了一种基于频繁子树挖掘策略的DNA重复序列识别方法,绕开了传统序列比对方式,将序列按照后缀树结构方式进行组织,再对后缀树形式做了约减改进,使其更加适合子树挖掘操作,最后利用频繁子树挖掘的方法对其进行学习,算法可以直接识别出满足设定阈值的重复序列,避免了由短重复体拼接所造成的时间浪费,设计的“二次识别技术”使得算法对模糊重复体也有着很好的识别效果,提高了识别的完整程度,利用实验证明:算法在识别效率方面较高,尤其当识别较长重复体时,优势体现的更为明显,同时在识别的完整程度方面也不相上下。