带通配符和间隔约束的近似频繁模式挖掘研究

代理获取

页面导航

目录
摘要
著录项
相似文献
相关主题

摘要

近年来,随着生物信息计算、网络入侵检测、文本检索等领域的发展,如何从序列数据中快速地提取用户感兴趣的、有意义的模式成为了一项关键的研究课题。对于已有的模式定义,最具挑战性的问题是发现带通配符和间隔约束的模式。
　　在进行模式匹配和挖掘的过程中,允许模式在目标序列中的出现带有编辑误差能够使得问题更加满足实际应用需要,在生物信息学等领域有着实际的应用价值。本文针对带通配符和间隔约束的近似频繁模式挖掘展开研究。用户可以指定模式字符间通配符的间隔约束范围、以及允许出现的编辑误差。对该问题的研究,完善了模式匹配与挖掘问题的研究,而且在许多实际领域具备应用价值。
　　本文的研究工作主要包括以下方面:
　　(1)文本中字符分布特征和模式特征是传统模式匹配和挖掘问题的重要参数,有助于揭示问题求解复杂性。因此,以此为研究对象,本文建立了数学模型E(Ω)=n*D*π(P),其中Ω为模式精确出现数目,n为文本长度,D为模式中各通配符间隔 gapi的乘积,π(P)为基于字符分布的模式出现概率。在人工随机数据和DNA真实数据上的实验表明,模型的预测误差率分别为1.8％~3.2%和4.7%~7.8%。本文同时揭示了在不同字符分布中,模式模长和通配符跨度对匹配数Ω的影响。因此,本文提出的统计模型可用于估计真实大文本中的模式出现数目,为模式挖掘问题中支持度的分析提供参考。
　　(2)针对带通配符和间隔约束的近似模式匹配挖掘问题,本文提出了MARP(Mining Approximate Repeating Patterns with wildcards and gap lengths)算法。算法的核心工作包括两个组成部分:一,使用模式支持率度量模式出现的频繁程度,为此,本文给出了满足间隔约束的近似补偿序列的计算公式。基于此,本文给出了类Apriori性质,该性质可以对候选模式集进行有效的确定性剪枝,降低了候选模式集的规模并能够及时终止算法,从而提高了挖掘的效率;二,本文给了模式的近似出现的计算方法,该方法基于改进的动态规划编辑矩阵,在计算编辑距离时,能够同时考虑插入、删除和替换三种操作,能够有效的计算模式的近似出现数目,使得挖掘算法能够有效计算模式的支持度。实验部分分析了各种因素对算法性能的影响,并将算法应用于真实蛋白质序列模式挖掘中。与已有算法相比,MARP算法能够更加灵活的挖掘模式。

著录项

作者
项泰宁;
展开▼
作者单位

合肥工业大学;

展开▼
授予单位合肥工业大学;
学科计算机应用技术
授予学位硕士
导师姓名吴信东;
年度 2014
页码
总页数
原文格式 PDF
正文语种中文
中图分类 TP311.13;
关键词
通配符; 间隔约束; 近似模式挖掘;

相似文献

中文文献
外文文献
专利

1. 一种有效的带通配符约束的频繁序列模式挖掘算法 [J] . 毛洪 ,田卫东 . 微计算机信息 . 2010,第033期
2. 近似到达时间约束下的语义轨迹频繁模式挖掘 [J] . 吴瑕 ,唐祖锴 ,祝园园 . 软件学报 . 2018,第010期
3. 基于DSCFCI_tree的带项目约束的数据流频繁闭合模式挖掘算法 [J] . 胡为成 ,王本年 ,程转流 . 中国科学技术大学学报 . 2009,第011期
4. 带间隔约束的Top-k对比序列模式挖掘 [J] . 杨皓 ,段磊 ,胡斌 . 软件学报 . 2015,第011期
5. 带约束的一维装箱问题近似算法的研究 [J] . 董一鸿 ,赵杰煜 . 计算机工程与应用 . 2003,第018期
6. 基于约束的交互式频繁模式挖掘算法 [C] . 任家东 ,孙亚非 ,郭盛 . 第二十四届中国数据库学术会议 . 2007
7. 满足One-off条件及间隔约束的频繁模式挖掘研究 [A] . 黄咏明 . 2010

带通配符和间隔约束的近似频繁模式挖掘研究

目录

摘要

著录项

相似文献

相关主题

期刊订阅