基于粗糙集的数据挖掘方法的研究

VIP免费

3.0 牛悦 2024-11-19 4 4 1.03MB 58 页 15积分

侵权投诉

基于粗糙集的数据挖掘方法的研究

Abstract

The data mining method based on Rough Sets is discussed in this paper ,which

includes getting attribute reduct by Genetic algorithm, rule extraction , comparison with

Id3 algorithm , and applications about Rough Sets method.

In attribute reduct by Genetic algorithm , design a fitness function based on reliable

degree of Rough Sets. Experiment which use data through UCI proves the algorithm

validity , How to set the parameter of algorithm is discussed.

In rule extraction , IADT algorithm is designed , which can get a minimal reduct or

relative minimal reduct and improve efficiency of rules.

By comparing with ID3 algorithm , the advantage of Routh Sets method can be

seen and it supports this valid method in Data mining’s applications from theory.

In applications, rule is extracted in data sets Zoo.In designing the analytic CRM,

some model are built by Rough Sets method.

Key words :Rough Sets , Genetic algorithm , Rule extraction , ID3, analytic

CRM

基于粗糙集的数据挖掘方法的研究

摘要

本文对基于粗糙集的数据挖掘方法进行了一定的研究，主要讨论了遗传算法

求粗糙集的属性约简、粗糙集的规则提取、与决策树 ID3 算法的比较以及粗糙集方

法在实际中的应用等问题。

遗传算法求属性约简中，基于依赖度设计了适应值函数，对算法的有效性进

行了实验证明，并讨论了参数的设置。

规则提取中设计了 IADT 算法，避开了 NP 难题，可以找到最简或相对最简

规则，大大提高了规则的效率。

通过和 ID3 的比较，进一步明确了粗糙集算法的优点，对数据挖掘实际应用

采用有效的算法给予了理论支持。

在应用中，采用粗糙集算法提取了 Zoo 数据的规则。在分析型 CRM 的设计中

采用粗糙集算法设计了几个具体的模型。

关键词：粗糙集遗传算法规则提取 ID3 算法分析型 CRM

目录
目   录
第一章 绪论..........................................................1
1．1  知识发现和数据挖掘..........................................................................................................1
1．2  粗糙集和数据挖掘..............................................................................................................1
1．3  论文研究的内容..................................................................................................................1
第二章  粗糙集理论基本概念和算法.....................................1
2．1  粗糙集的基本概念..............................................................................................................1
2．2  粗糙集属性约简算法分析..................................................................................................1
2．3　在数据挖掘中的流程........................................................................................................1
第三章  遗传算法求最佳约简...........................................1
3．1  遗传算法简单介绍..............................................................................................................1
3．2  基于依赖度的遗传算法......................................................................................................1
3．3  算法的深入讨论..................................................................................................................1
第四章  规则提取.....................................................1
4．1  问题的提出和传统的提取方法..........................................................................................1
4．2  基于属性重要性的决策树算法..........................................................................................1
4．3  不相容表的算法处理..........................................................................................................1
第五章  粗糙集理论和 ID3 算法的比较...................................1
5．1  ID3 算法和粗糙集理论的规则提取.................................................................................1
5．2  粗糙集和信息熵..................................................................................................................1
5．3  两种方法的比较..................................................................................................................1
第六章  基于粗糙集的数据挖掘方法的应用...............................1
6．1  提取 ZOO 中的规则............................................................................................................1
6．2  基于粗糙集的分析型 CRM 模型........................................................................................1
总结语...............................................................1
参考文献.............................................................1
附录.................................................................1
3

基于粗糙集的数据挖掘方法的研究

第一章绪论

1．1 知识发现和数据挖掘

近几十年来，随着数据库技术的成熟和数据应用的普及，特别是进入九十年

代，伴随着因特网（Internet）的出现和发展，展现在人们面前的已不是局限于本

部门，本单位和本行业的庞大数据库，而是浩瀚无垠的信息海洋，数据洪水正向

人们滚滚涌来。当数据量极度增长时，如果没有有效的方法，由计算机及信息技

术来提取有用信息和知识，人们也会感到面对信息海洋像大海捞针一样束手无策

据估计，一个大型企业数据库中数据，只有百分之七得到很好应用。这样，相对

于“数据过剩”和“信息爆炸”，人们又感到“信息贫乏”（Information poor）

和"数据关在牢笼中”(data in jail),奈斯伯特(John Naisbett)惊呼“We are drowning

in information，but starving for knowledge”（人类正被数据淹没，却饥渴于知识）。

面临浩渺无际的数据，人们呼唤从数据汪洋中来一个去粗存精、去伪存真的技术。

从数据库中发现知识(KDD)及其核心技术——数据采掘(DM)便应运而生了。

一份最近的 Gartner 报告中列举了在今后 3～5年内对工业将产生重要影响

的五项关键技术，其中 KDD 和人工智能排名第一。同时，这份报告将并行计算机

体系结构研究和 KDD 列入今后 5年内公司应该投资的10 个新技术领域

1.1.1 发展历史

1989 年8月，在美国底特律的第11 届国际人工智能联合会议的专题讨论会

上召开了第一届的KDD 的Workshop，1991、1993、1994 年又接着举行KDD 专题

讨论会。从 1995 年开始，每年都举办一次KDD 国际会议。从 1997 年开始，KDD

也拥有自己的专门杂志《Knowledge Discovery and Data Mining》。1995 年以来，国

外在知识发现和数据挖掘方面的论文非常多，已形成了热门研究方向。

1.1.2 知识发现

知识发现（KDD）是从数据中发现有用知识的整个过程；数据挖掘（DM）

是KDD 过程中的一个特定步骤，它用专门算法从数据中抽取模式

（patterns）。1996 年，Fayyad、Piatetsky Shapiror 和Smyth 将KDD[1]过程定义为：

Knowledge discovery in databases is the nontrivial process of identifying

valid，novel，ptentially useful，and ultimately understandable patterns in data..

从数据中鉴别出有效模式的非平凡过程，该模式是新的、潜在有用的和最终

可理解的。

KDD 过程是多个步骤相互连接、反复进行人机交互的过程。具体包括：

① 学习某个应用领域：包括应用中的预先知识和目标。

② 建立目标数据集：选择一个数据集或在多数据集的子集上聚焦。

③ 数据预处理：去除噪声或无关数据，去除空白数据域，考虑时间顺序和数

据变化等。

第一章绪论

④ 数据转换：找到数据的特征表示，用维变换或转换方法减少有效变量的数

目或找到数据的不变式。

⑤ 选定数据挖掘功能：决定数据挖掘的目的。

⑥ 选定数据挖掘算法：用 KDD 过程中的准则，选择某个特定数据挖掘算法

（如汇总、分类、回归、聚类、偏差分析等）用于搜索数据中的模式。

⑦ 数据挖掘：搜索或产生一个特定的感兴趣的模式或一个特定的数据集。

⑧ 解释：解释某个发现的模式，去掉多余的不切题意的模式，转换某个有用

的模式，以使用户明白。

⑨ 发现知识：把这些知识结合到运行系统中，获得这些知识的作用或证明这

些知识。用预先、可信的知识检查和解决知识中可能的矛盾。

1．1．3 数据挖掘

所谓数据挖掘，就是从数据库中抽取隐含的、以前未知的、具有潜在应用价值

的信息的过程。数据挖掘是 KDD 最核心的部分。数据挖掘与传统统计分析工具不

同的是数据挖掘使用的是基于发现的方法，运用模式匹配和其它算法决定数据之

间的重要联系。而传统的统计学分析方法是建立在一定的假设之上的，假设的存

在在一定程度上限制了它的应用范围。另外，当数据量大时，数据挖掘相对统计

学的优势就会比较突出了，比如在计算速度和发现问题上。但是，数据挖掘并没

有完全排斥统计学，还是把统计学当中许多方法应用到数据挖掘当中，比如聚类

回归、时间序列等等。数据挖掘是一个集统计学、人工智能、模式识别、计算机科学

机器学习等多种学科为一体的产物，不仅是数据库系统和机器学习研究的重要课

题，还是孕育了巨大的商业前景的重要领域。

数据挖掘算法的好坏将直接影响到所发现知识的好坏。目前大多数的研究都

集中在数据挖掘算法和应用上。需要说明的是，有的学者认为，数据挖掘和知识

发现含义相同，表示成KDD/DM。它是一个反复的过程，通常包含多个相互联系

的步骤：明确问题，选择数据，数据预处理、模型建立，选择算法，发现知识，

知识评价与反馈，知识的应用等一系列过程。实际上，人们往往不严格区分数据

挖掘和数据库中的知识发现，把两者混淆使用。一般在科研领域中称为 KDD，而

在工程领域则称为数据挖掘。本论文采用数据挖掘的概念，挖掘步骤图 1.1 所示：

图 1.1

基于粗糙集的数据挖掘方法的研究

1．1．4 数据挖掘的目标和相应算法[8,910]

数据挖掘采用基于发现的方法对海量的数据进行知识发现或采掘，目的是发

现隐含在数据中人们不知道的知识，从而科学地辅助人的决策。数据挖掘重点解

决的问题是发现隐含在数据中的知识，从而指导人们的行为和思维，提供决策支

持。数据挖掘的目标和相应算法下面给予简单介绍。

● 依赖关系

计算依赖关系的典型算法有关联规则。关联规则最初开始应用于购物篮分析，

在商场或超市对商品进行相关分析，比如关联规则可以挖掘出象“买啤酒的中年

男子，有 80%的可能买尿布”这样出人意料而又现实的规则。

设I={i1，i2，...，im}是一组物品集(一个商场的物品可能有上万种)，D是

一组事务集(称之为事务数据库)。D中的每个事务T是一组物品，显然满足 T

I。称事务T支持物品集X，如果 X T。关联规则是如下形式的一种蕴含:X Y，

其中 XI，YI，且 X∩Y=I。

　　(1)称物品集X具有大小为s的支持度，如果 D中有 s%的事务支持物品集X;

　　(2)称关联规则 X Y 在事务数据库 D中具有大小为s的支持度，如果物品集

X∪Y 的支持度为s;

　　(3)称规则 X Y 在事务数据库 D中具有大小为c的可信度，如果 D中支持物

品集X的事务中有 c%的事务同时也支持物品集Y。

关联规则一般的算法采用 Aprio算法，除此外还有Fp Tree、DIC算法等。扩

展开来，还有多维关联规则，可以从不同概念层上提取关联规则。另外，关联规

则发现的思路还可以用于序列模式发现。除了具有上述关联规律，还有时间上或

序列上的规律。

● 分类

分类在数据挖掘中是一项非常重要的任务，分类的目的是学会一个分类函数

或分类模型(也常常称作分类器)，该模型能把数据库中的数据项映射到给定类别

中的某一个。分类和回归都可用于预测。预测的目的是从利用历史数据纪录中自动

推导出对给定数据的推广描述，从而能对未来数据进行预测。和回归方法不同的

是，分类的输出是离散的类别值，而回归的输出则是连续数值。

要构造分类器，需要有一个训练样本数据集作为输入。训练集由一组数据库

记录或元组构成，每个元组是一个由有关字段(又称属性或特征)值组成的特征向

量，此外，训练样本还有一个类别标记。一个具体样本的形式可为:

(v1，v2，...，vn;c);其中 vi表示字段值，c表示类别。

分类器的构造方法有统计方法、机器学习方法、神经网络方法、统计学习方法

等等。

统计方法包括贝叶斯法和非参数法(近邻学习或基于事例的学习)，对应的知

识表示则为判别函数和原型事例。机器学习方法包括决策树法和规则归纳法，前

者对应的表示为决策树或判别树，后者则一般为产生式规则。决策树经典的算法

有ID3 和其改进算法 C4.5，除此之外，还有CART 和ChAID 算法。

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

目录基于粗糙集的数据挖掘方法的研究AbstractThedataminingmethodbasedonRoughSetsisdiscussedinthispaper,whichincludesgettingattributereductbyGeneticalgorithm,ruleextraction,comparisonwithId3algorithm,andapplicationsaboutRoughSetsmethod.InattributereductbyGeneticalgorithm,designafitnessfunctionbasedonreliabledegreeofRoug...

展开>> 收起<<

基于粗糙集的数据挖掘方法的研究.doc

共58页,预览6页

还剩页未读，继续阅读

基于粗糙集的数据挖掘方法的研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: