论文部分内容阅读
数据挖掘是当今计算机应用技术和理论研究中最热门的领域之一。数据挖掘技术经过十多年的发展，已经逐渐建立起系统的挖掘理论和成熟的挖掘技术。形成了以关联规则挖掘、分类规则挖掘、聚类规则挖掘为主要形式的，以数据库技术、统计学、人工智能、可视化技术和信息技术为主要工具的多学科交叉的应用技术。从最初的商业应用逐渐扩展到医疗、金融、生物、电信、军事、体育等诸多领域。数据挖掘成为越来越多的科学家、研究人员、工程应用人员、商人、医生所关注的对象。
分类作为数据挖掘的一个重要分支，在过去的十多年中引起很多来自不伺领域的学者的注意，学者们提出了以信息论为基础的决策树算法、以概率论为基础的贝叶斯分类方法，以神经科学为基础的神经网络方法等等，这些算法基本上都是确定性算法。以自然进化为基础的遗传算法因为其智能性、并行性、不确定性等诸多特点成为其中一个特殊的分支。挖掘分类模式的方法有多种，如决策树方法、贝叶斯网络、遗传算法、基于关联的分类方法、粗糙集和k-最临近方法等等。
作为数据挖掘技术的核心算法之一，决策树是一种自顶向下、无回溯、不断搜索重要分裂变量的归纳学习算法，其基本目标是在特定的学习任务指导下从一组无次序、无规则的事例中构建简洁、直观的树型结构，核心技术是树的生长和剪枝。决策树不仅具备了数据挖掘技术充分发现隐藏在数据背后大量信息的基本特点，还具有许多其它传统的统计学方法和机器学习方法无法比拟的优点。
遗传算法是一种新兴的搜索寻优技术，它模拟达尔文的进化论，根据“优胜劣汰”的原则，借助选择、交叉、变异等操作逐步逼近最优解。具有隐并行机制和自适应性，因此它非常适合于多维，非线性和具有多峰值的问题。遗传算法具有全局优化性和易操作性。最初应用于非数值计算方面，直到近几年才转向全局优化问题，并取得了显著的成果，吸引了越来越多的研究者，逐渐成为人工智能领域的一个热点。
本文致力于数据挖掘的分类任务，其目标是对一个样例进行分类。采用决策树和遗传算法的混合方法来挖掘分类规则。这种混合方法的中心思想是将小的析取的概念引入到数据挖掘中。一个小的析取指的是满足少数样例的某个规则。尽管每个小的析取仅仅覆盖很少的样例，但是，所有小的析取的集合就能覆盖大多数样例。在混合方法中，采用了两种改进的遗传算法，专门设计用来发现一些规则，这些规则覆盖了属于小的析取的样例。相反，传统的决策树算法常用于产生那些覆盖属于大的析取的样例的规则。在文中，我们给出在三个公共数据集上评估混合方法的结果，并与其他数据挖掘方法的结果进行了对比。
本文的组织结构如下：在第一章首先介绍了数据挖掘概述，然后分别对论文的选题及其研究意义、选题的国内外研究现状、主要的研究内容进行了阐述。第二章简要介绍了几种常见的决策树算法，如基于信息论的1D3算法和C4.5算法，以及基于最小GINI指标的CART算法，并且指出各种算法的特点以及优缺点。第三章详细介绍了遗传算法的工作原理：遗传算法的基本术语、基本流程、编码、初始群体的生成、适应度函数的计算、遗传操作的设计以及终止规则等等，并指出了遗传算法的特点和优点。第四章通过分析决策树算法与遗传算法各自优点和缺点，将小的析取问题引入数据挖掘中，采用了一种基于决策树与遗传算法的混合方法。混合方法使用了两种改进的遗传算法挖掘小的析取规则，通过在公共数据集上的测试，说明了算法的效果。第五章总结了论文的主要工作。