知识的发现方法与应用

《知识的发现方法与应用》由会员分享，可在线阅读，更多相关《知识的发现方法与应用（17页珍藏版）》请在金锄头文库上搜索。

1、人工智能知识的发现方法及应用学院：经济与管理学院 班级：工业工程091601班姓名：王兴喜学号：200916020125 日期:2012年6月21日知识的发现方法及应用【摘要】知识的发现方法与应用越来越成为当今世界各个领域所要探求的重点领域，从某中 意义上来说，只是发现可以当做一个哲学问题来解释，因为有时似乎它很高深莫测，让 人摸不到头脑。所以从这点上来说，知识的发现方法及应用是一切知识领域之祖。我们 可以从这里面找到一切科学的踪迹。【关键词】知识 方法应用【正文】一、 知识发现的概念KDD （知识发现）是一个综合的过程，它包括数据录入、迭代求解、用户交互以及 许多定制要求和决策设计等，而Da

2、ta Mining只是KDD中的一个具体却是关键的步骤。 数据库中的知识发现术语是在1989年的第一届KDD专题讨论会上被首次采用，它强调 了知识是数据发现的最终产品。这一研究领域兴起于八十年代初，它是一个众多学科诸如人工智能、机器学习、模 式识别、统计学、数据库和知识库、数据可视化等相互交叉、融合所形成的一个新兴的 且具有广阔前景的领域。从数据库中发现出来的知识可以用在信息管理、过程控制、科 学研究、决策支持等许多方面。1998年第四届知识发现与数据挖掘国际会议上不仅进行了学术讨论，并且有30多 家软件公司展示了数据挖掘软件产品，在北美、欧洲等国得到较大应用。在我国，许多 单位也已开始此项技

3、术研究，但目前取得成功应用的例子还未见报道1 KDD （知识发现）概念及一般步骤在 KDD96 国际会议上，Fayyad, Piatetsky-Shapiro 和 Smyth 对 KDD 作了如下描述： 指从数据库中获取正确、新颖、有潜在应用价值和最终可理解的模式的非平凡过程。在 这个描述中，数据是一系列事实的集合，模式是指用语言L来表示的一个表达式E，它 可用来描述数据集的特性，E所描述的数据是集合F的一个子集FE。过程是在KDD中包 含的步骤，如数据的预处理、模式搜索、知识表示及知识评价等，非平凡是指它已经超 越了一般封闭形式的数量计算，而将包括对结构、模式和参数的搜索。数据准备数据挖掘结

4、果表达和解程F*F*2知识发现过程一般包括如下步骤：数据准备 包括3个子步骤：数据集成、数据选择、数据预处理。数据集成将多文 件或多数据库运行环境中的数据进行合并处理，解决语义模糊性、处理数据中的遗漏和 清洗脏数据等。数据选择的目的是辨别出需要分析的数据集合，缩小处理范围，提高数 据采掘的质量。预处理是为了克服目前数据采掘工具的局限性。数据挖掘iii要先决定如何产生假设，是让数据挖掘系统为用户产生假设，还是用户自己对于数 据库中可能包含的知识提出假设。前一种称为发现型的数据挖掘，后一种称为验证型的 数据挖掘。选择合适的工具。挖掘知识的操作。证实发现的知识。结果表达和解释 根据最终用户的决策目的

5、对提取的信息进行分析，把最有价值的 信息区分出来，并且通过决策支持工具提交给决策者，因此这一步骤任务不仅是把结果 表达出来，还要对信息进行过滤处理，如果不能令决策者满意，需要重复以上数据挖掘 过程。相关技术Data Mining （数据挖掘）主要任务有数据汇总、概念描述、分类、聚类、相关 性分析、偏差分析、建模等。具体技术包括：统计分析（statistical analysis）常见的统计方法有回归分析（多元回归、自回归等）、判别分析（贝叶斯分析、费 歇尔判别、非参数判别等）、聚类分析（系统聚类、动态聚类等）和探索性分析（主元 分析法、相关分析法等）。其处理过程可以分为三个阶段：搜集数据、分析

6、数据和进行 推理。决策树（decision tree）决策树是一棵树，树的根节点是整个数据集合空间，每个分节点是对一个单一变量 的测试，该测试将数据集合空间分割成两个或更多块。每个叶节点是属于单一类别的记 录。首先，通过训练集生成决策树，再通过测试集对决策树进行修剪。决策树的功能是 预言一个新的记录属于哪一类。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量 做决策树。通过递归分割的过程来构建决策树：1寻找初始分裂，整个训练集作为产生决策 树的集合，训练集每个记录必须是已经分好类的。决定哪个属性（Field）域作为目前 最好的分类指标。一般的做法是穷尽所有的属性域，对每

7、个属性域分裂的好坏做出量化， 计算出最好的一个分裂。量化的标准是计算每个分裂的多样性（diversity）指标GINI指标。2树增长到一棵完整的树，重复第一步，直至每个叶节点内的记录都属于同一 类。3数据的修剪，去掉一些可能是噪音或者异常的数据。其基本算法(贪心算法)为：自上而下分而治之的方法，开始时，所有的数据都在 根节点；属性都是种类字段(如果是连续的，将其离散化)；所有记录用所选属性递归 的进行分割；属性的选择是基于一个启发式规则或者一个统计的度量(如， information gain)。停止分割的条件：一个节点上的数据都是属于同一个类别；没 有属性可以再用于对数据进行分割。伪代码(B

8、uilding Tree)为： Procedure BuildTree(S)用数据集S初始化根节点R用根结点R初始化队列QWhile Q is not Empty do 取出队列Q中的第一个节点Nif N 不纯(Pure) for每一个属性A估计该节点在A上的信息增益选出最佳的属性，将N分裂为N1、N2属性选择的统计度量为：v信息增益Information gain (ID3/C4.5)，所有属性假设都是种类字段，经过修改之后可以适用于数值字段；v基尼指数 Gini index (IBM IntelligentMiner)，能够适用于种类和数值字段。关联规则(correlation rules

9、)规则反映了数据项中某些属性或数据集中某些数据项之间的统计相关性，其一般形 式为：X1A.AXn YC,S，表示由X1A.AXn可以预测Y，其中可信度为C， 支持度为S。设I=i1，少九是二进制文字的集合，其中的元素称为项(item)o记D 为交易(transaction)/的集合，这里交易T是项的集合，并且TII。对应每 一个交易有唯一的标识，如交易号，记作TID。设X是一个I中项的集合，如 果XT那么称交易T包含X。一个关联规则是形如X的蕴涵式，这里XII； Yil,并且XGY=F。规 则XPY在交易数据库D中的支持度(support)是交易集中包含X和Y的交 易数与所有交易数之比，记为s

10、upport(XAY)，即. support(XY)=|T:XEYIT，TiD|/|D|规则XPY在交易集中的可信度(confidence)是指包含X和Y的交易数与 包含X的交易数之比，记为confidence(XPY)，即.confidence(XY)=|T: XEYIT，TiD|/|T:Xfr，TiD|给定一个交易集D，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定 的最小支持度(minsupp)和最小可信度(minconf)的关联规则。基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔型关联规 则处理的值都是离散的、种类化的，它显示了这些变量之间的关系；而数值型关联

11、规则 可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分 割，或者宜接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。基 于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单层的关联规则 中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的；而在多层的关联规 则中，对数据的多层性已经进行了充分的考虑。基于规则中涉及到的数据的维数，关联 规则可以分为单维的和多维的。在单维的关联规则中，我们只涉及到数据的一个维，如 用户购买的物品；而在多维的关联规则中，要处理的数据将会涉及多个维。Agrawal等于1993年首先提出了挖掘顾客交易数据库中项

12、集间的关联规则问 题，其核心方法是基于频集理论的递推方法。以后诸多的研究人员对关联规则的挖掘问 题进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、并行 的思想等，以提高算法挖掘规则的效率；提出各种变体，如泛化的关联规则、周期关联 规则等，对关联规则的应用进行推广。Agrawal等在1993年设计了一个基本算法，提出了挖掘关联规则的一个重要 方法一这是一个基于两阶段频集思想的方法，将关联规则挖掘算法的设计可以分解为 两个子问题：1)找到所有支持度大于最小支持度的项集(Itemset)，这些项集称为频集(Frequent Itemset)。2)使用第1步找到的频集产生期望的规

13、则。这里的第2步相对简单一点。如给定了一个频集Y=I1I2.Ik,略2, I户，产 生只包含集合11，12, .，U中的项的所有规则（最多k条），其中每一条规则的右 部只有一项，（即形如YI I，”1/k）。一旦这些规则被生成，那么只有那些大 于用户给定的最小可信度的规则才被留下来。对于规则右部含两个以上项的规则，在其 以后的工作中进行了研究。为了生成所有频集，使用了递推的方法。其核心思想如下:L1 = large 1-itemsets;for (k=2; Lk_11F; k+)Ck=apriori-gen(Lk_1); 新的候选集for all transactions tlD Ct=sub

14、set(Ck,t); 事务t中包含的候选集 for( all candidates cl Ct ) c.count+;Lk=cl Ck |c.count3minsupAnswer=EkLk;首先产生频繁1-项集L1，然后是频繁2-项集L2，直到有某个r值使得L,为空， 这时算法停止。这里在第k次循环中，过程先产生候选k-项集的集合Ck，Ck中的每 一个项集是对两个只有一个项不同的属于Lk-1的频集做一个（k-2）-连接来产生的。Ck 中的项集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每 个元素需在交易数据库中进行验证来决定其是否加入Lk，这里的验证过程是算法性能 的一

15、个瓶颈。这个方法要求多次扫描可能很大的交易数据库，即如果频集最多包含10 个项，那么就需要扫描交易数据库10遍，这需要很大的I/O负载。Agrawal等引入了修剪技术（Pruning）来减小候选集Ck的大小，由此可以显 著地改进生成所有频集算法的性能。算法中引入的修剪策略基于这样一个性质：一个项 集是频集当且仅当它的所有子集都是频集。那么，如果 Ck中某个候选项集有一个(k-1)-子集不属于匕.1,则这个项集可以被修剪掉不再被考虑，这个修剪过程可以降 低计算所有的候选集的支持度的代价。基于Apriori的频集方法即使进行了优化，但是Apriori方法一些固有缺陷还是 无法克服：1)可能产生大量的候选集。当长度为1的频集有10000个的时候，长度 为2的候选集个数将会超过10M。还有就是如果要生成一个很长的规则的时候，要产 生的中间元素也是巨大量的。2)无法对稀有信息进行分析。由于频集使用了参数 minsup，所以就无法对小于minsup的事件进行分析；而如果将minsup设成一 个很低的值，那么算法的效率就成了一个很难处理的问题。以下两种方法，分别用于