代分号学号 密1020121208题(中、英文)作者姓指导教师姓名、学科门创新性声明秉承学校严谨的学风和优良的科学道德,本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。
尽我所知,除了文中特别加以标注和致谢中所罗列的内容以外,论文中不包含其他人已经发表或撰写过的研究成果;也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。
与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。
申请学位论文与资料若有不实之处,本人承担一切的法律责任。
本人签名:日期关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定,即:研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。
学校有权保留送交论文的复印件,允许查阅和借阅论文;学校可以公布论文的全部或部分内容,可以允许采用影印、缩印或其它复制手段保存论文。
同时本人保证,毕业后结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。
(保密的论文在解密后遵循此规定)本人签名:导师签名:日期:日期:摘要数据挖掘是当今计算机科学中快速发展的一个研究方向,它涉及到多个领域的知识。
数据挖掘能从大量的数据中发现一些人们事先未知的、潜在的、有趣的知识,因此广泛被应用于商业分析、机器学习、网络个性化服务等领域。
数据挖掘有很多研究方向,关联规则和序列模式是其中重要的两类,其中关联规则的研究重点在于频繁项集的发现,而序列模式则强调数据的序列特性。
本文基于粒计算的相关原理和模型,对关联规则和序列模式的挖掘算法进行了研究。
本文的主要工作概括如下:1. 概述了数据挖掘和粒计算的基本原理,说明了数据挖掘的主要研究方向和粒计算的几个重要的计算模型,对关联规则、序列模式和粗糙集的基础理论知识进行了介绍,对常见的关联规则挖掘算法和序列模式挖掘算法进行了简单的汇总和分析。
2. 详细分析了关联规则挖掘算法Apriori算法的原理。
针对Apriori算法存在的产生较多候选频繁项的问题,给出基于粒化原理的改进算法Apriori-GRC算法,并通过仿真实验表明其有效性。
3. 给出一种基于重要度的粗糙集信息系统属性约简算法Sig-Reducts算法。
讨论了序列的粗糙集模型,在Sig-Reducts算法的基础上,给出了一种基于决策表的序列规则挖掘算法Sequence-Mining算法,分析了算法的时间复杂度并通过仿真实验进行了验证。
关键词:数据挖掘粒计算关联规则序列模式AbstractData mining is a research direction that develop quickly, it involves different knowledge of many aspects. Data mining is able to discover some unknown, potential, and interesting information from large amounts of data, so it is widely used in in the correlation analysis, classification, network personalized services and so on. Data mining has many research directions, and frequent pattern mining and sequence pattern mining are two important types. Frequent pattern mining focuses on items that frequently appear, while sequential pattern mining emphasizes the temporal characteristics of items.This paper focuses on frequent pattern mining and sequential pattern mining based on the the principles and models of the granular computing. Some results are obtained and summarized as follow:1.The Theoretical basis of frequent pattern, sequential pattern and granular computing is briefly illuminated. The common algorithm of data mining and the principles of granular computing are introduced.2. A classical algorithm of frequent pattern mining –Apriori Algorithm is discussed in detail. Aiming at some existed questions in Apriori Algorithm such as, produceding candadata itemset need to match pattern, this chapter proposes one kind of frequent pattern mining algorithm based on granular computing, and its effectiveness is proved by the simulation.3. A information system attributes reducts algorithm based on the importance of attributes is proposed which is named Sig-Reducts. Introduce the granulated model of the sequence set. Based on the Sig-Reducts algorithm, this chapter proposes the Sequence-Mining algorithm which produces the sequential rule, and proves its effectiveness.Keyword:Granular Computing Data Mining Frequent Pattern Mining Sequential Pattern Mining目录第一章绪论 (1)1.1研究背景 (1)1.2研究现状 (2)1.2.1 数据挖掘研究现状 (2)1.2.2 粒计算研究现状 (3)1.3 本文主要研究工作和内容安排 (4)第二章相关研究分析 (7)2.1 数据挖掘 (7)2.1.1 数据挖掘的概念以及对象 (7)2.1.2 数据挖掘的步骤 (7)2.1.3 数据挖掘的功能 (8)2.2 关联规则挖掘和序列模式挖掘 (9)2.2.1 关联规则和序列模式的概念 (9)2.2.2 相关定义 (10)2.2.3 主要挖掘算法 (11)2.3粒计算理论 (12)2.3.1 粒计算的思想 (12)2.3.2 几个重要的概念 (12)2.3.3 粒计算研究的基本问题 (13)2.3.4 现有的粒计算模型 (14)2.3.5 各模型之间的关系 (15)2.4 粗糙集理论基础知识 (16)2.4.1 下近似集和上近似集 (16)2.4.2 信息系统和决策表 (18)2.4.3 约简与核 (19)2.5本章小结 (19)第三章基于粒化原理的关联规则挖掘算法 (21)3.1 挖掘关联规则的Apriori算法 (21)3.1.1 Apriori性质和Apriori算法的步骤 (21)3.1.2 Apriori算法描述 (22)3.1.3 存在的问题 (24)3.2一种基于粒化原理的关联规则挖掘算法—Apriori-GRC算法 (25)3.2.1 Apriori算法中的粒化原理分析 (25)3.2.2 Apriori-GRC算法描述 (25)3.2.3 算法示例 (27)3.3 仿真结果及分析 (28)3.4 本章小结 (30)第四章基于决策表的序列模式挖掘算法 (31)4.1 一种基于重要度的信息系统属性约简算法—Sig-Reducts算法 (31)4.1.1 属性的信息量和重要度 (31)4.1.2 Sig-Reducts算法描述 (32)4.2 序列的粗糙集模型 (35)4.2.1 序列和子序列 (35)4.2.2 序列信息系统和序列决策表 (36)4.3一种基于决策表的序列模式挖掘算法—Sequence-Mining算法 (37)4.3.1 算法思想 (37)4.3.2 算法描述 (38)4.4算法效率分析和仿真实验 (41)4.4.1 Sig-Reducts算法的时间复杂度分析 (41)4.4.2 Sequence-Mining算法的时间复杂度分析 (41)4.4.3 Sig-Reducts算法的仿真实验 (42)4.5本章小结 (43)结束语 (45)致谢 (47)参考文献 (49)攻读硕士期间完成的论文和参与的科研工作 (53)第一章绪论 1第一章绪论本章阐述了数据挖掘技术的应用需求背景,简单介绍了粒计算的原理,并指出基于粒计算的数据挖掘技术具有重要的理论和实际意义。
根据目前数据挖掘技术和粒计算的主要研究方向,本章给出其简单的总结。
最后本章总结了作者在攻读硕士学位期间的研究工作,并给出了全文的内容安排。
1.1 研究背景随着计算机技术、互联网和通信技术的飞速发展,我们已经进入了海量数据时代,如何有效地解决数据爆炸已经成了信息化进程中非常重要的课题。
从信息处理的角度来讲,我们希望计算机可以帮助我们对现有的各种数据进行深入的整理、归类和分析,并最终为我们的决策提供有效的数据支撑,从而使我们在做决策时更加客观和科学。
因此这就需要有能够对海量数据进行有效处理的工具。
传统的数据分析方法,例如各种统计分析技术等,只能够获取这些数据的表层现象,很难进行更深入的分析,不便于发觉数据在逻辑层面的规律和规则,而往往这些规律和规则对我们做出决策时具有非常重要的作用。
因此,针对拥有海量数据却难以发现其中蕴含的有效信息这一矛盾,我们急需一中能够从海量数据中发现潜在知识的工具,数据挖掘技术正是在这样的背景下出现的。