人工智能论文.doc

目录1引言22有关的基本概念2（1）粗糙集的基本概念2（2）属性重要度33ID3算法3（1）信息熵和条件熵3（2）基于条件熵的属性选择44算法的改进45实例验证56总结97分工9一种基于属性重要度的ID3算法 摘要：决策树是数据挖掘中重要的分类算法，通常用来形成分类器。ID3算法是决策树中的核心算法。针对ID3算法倾向于取值较多的属性的缺点，引进属性重要度对ID3算法予以改进，并通过实验对改进前后的算法进行了比较。实验表明，改进后的算法是有效的！ 关键字：决策树 ID3算法 属性重要度1引言决策树分类方法是一种有效的数据挖掘方法（参考文献1）。在决策树的构造中，ID3算法是最有影响力的决策树生成算法，它是由Quinlan于1979年提出。ID3算法的基本思想是，以信息熵为度量，用于决策树节点的属性选择，每次优先选取信息量最多的属性或者说能使熵值变成最小的属性，以构造一棵熵值下降最快的决策树，到叶子节点处的熵值为0（引自人工智能-技术导论p196）。但是该方法有倾向于选择取值较多的属性的缺点。粗糙集理论是由波兰数学家Z Paw lak于1982年首先提出的一种研究不精通，不确定性知识的数学工具，目前主要用于分类（参考文献2,3,）。通过对粗糙集理论和ID3算法的研究，利用粗糙集中属性重要性知识，选择属性重要度大的属性作为节点进行分类，使生成决策树时取值较少的属性不会被淹没或者降低属性值较多且并不重要的属性，最终使决策树减少了对取值较多的属性的依赖性，从而尽可能地减少大数据掩盖小数据的现象发生，并通过实验对改进前后的算法进行了比较。实验表明，改进后的算法是有效的！2有关的基本概念（参考文献4,5,6,7）（1）粗糙集的基本概念 定义1 设U是一个论域，R是U上的一个等价关系。U/R表示U上由R导出的所有等价类。xR表示包含元素x的R的等价类，xU。定义2 一个近似空间（或知识库）就是一个关系系统K=U，P，其中U是论域，P是U上的一个等价关系簇。如果QP，Q中的等价关系的交集称为Q上的不分明关系，记作则IND（Q），即：xind(Q)=xp.可知，IND（Q）中的每一个等价类中的各元素对Q中的各属性来说有相同的值，其中等价类的求解可由P中等价关系的等价类相交而求得。 定义3 令XU，对每个概念X（样例集）和不分明关系B，包含于X中的最小可定义集和包含X的最大可定义集，都是根据B能够确定的，前者称为X的下近似集，后者称为x的上近似集。 下近似和上近似集的概念也可以通过集合来定义： B_(X)=x|xU xBXB_(X)=x|(xUxBX)（2）属性重要度 定义1 设有两个属性集C和D，则D对C的依赖度定义为K， K=（C,D）=， 定义2 设属性,C是条件属性集，D是决策属性集，则的属性重要度定义为：SGF=（，C,D）=（C,D）-（C-,D）.3ID3算法(参考文献10,11,30)（1）信息熵和条件熵 ID3算法将实例集视为一个离散的信息系统，用信息熵表示其信息量。实例集中的实例的结论视为随机事件，而将诸属性看做是加入的信息源。 设S是一个实例集，A为S中实例的一个属性。H(S)和H(S|A)分别称为实例集S的信息熵和条件熵，其计算公式如下： H(S)=- （1）其中，i(i=1,2,n)为S中各实例所有可能的结论；lb即log2. H（S|A）= （2）其中，k（k=1,2，m）为属性A的取值，为按属性对实例集S进行分类时k对应的那个子类所得诸子类中与属性值。（2）基于条件熵的属性选择 对于一个待分类的实例集S，先分别计算各可取属性Aj（j=1,2，L）的条件熵H(S|Aj)。然后取其中熵值最小的属性As作为当前节点。4算法的改进（参考文献22,23,24,25）传统的ID3算法选择属性A作为测试属性的原则：使式（2）的值最小。这种算法往往偏向于选择值较多的属性，然而取值较多的属性却并不总是最优的属性。即按照使熵值最小的原则，被ID3算法列为应选取的属性，对其进行测试不会提供太多的信息。所以，我们引入属性重要度。对于某些问题，属性具有不同的重要度，当我们在用ID3算法构造决策树时，可以首先利用表中的数据计算所有属性的属性重要度，如果不是，则它们在分类能力上就有差别。此次对ID3算法的改进就是基于属性重要度，对选择标准进行改进。通过对式（2）加权和增加属性重要度，加强了属性的标注，降低了非重要属性的标注，把“加权和”转换为与属性重要度相加的“新加权和”。这样，生成决策树时，取值少的属性不会被淹没，最终使决策树减少“大数据掩盖小数据”的现象的发生。利用属性重要度，将式（2）修改为 H(S|A)= （3）用改进后的算法构造决策树时，可以首先计算各个属性的属性重要度，若相同，则说明此实例集中的属性在分类能力上没有差别，则不需要用进行改进；若不同，则用改进的ID3算法来构造决策树。5实例验证注：通过计算书上P193某保险公司的汽车驾驶保险类别划分的部分实例，发现属性性别，年龄段，婚状的属性重要度均相同，我们便没有列出，但我们在此举了另外一个例子来验证我们的算法。下表所示的是影响天气舒适度的划分的实例的集合。属 性 穿衣指数 温 度 湿 度 风 力 天气舒适度1 较多 很高 很大 没有 不舒适（N）2 较多 很高 很大 很大 不舒适（N）3 较多 很高 很大 中等 不舒适（N）4 正常 很高 很大 没有 舒适（P）5 正常 很高 很大 中等 舒适（P）6 很多 适中 很大 没有 不舒适（N）7 很多 适中 很大 中等 不舒适（N）8 很多 很高 正常 没有 舒适（P）9 很多 很高 正常 很大 不舒适（N）10 较多 适中 很大 没有 不舒适（N）11 较多 适中 很大 中等 不舒适（N）12 很多 适中 正常 没有 不舒适（N）13 很多 适中 正常 中等 不舒适（N）14 较多 适中 正常 中等 舒适（P）15 较多 适中 正常 很大 舒适（P）16 正常 适中 很大 很大 舒适（P）17 正常 适中 很大 中等 舒适（P）18 正常 很高 正常 没有 舒适（P）19 很多 适中 很大 很大 不舒适（N）20 正常 很高 正常 中等 舒适（P）首先我们来计算属性重要度（这里我们用A表示穿衣指数，B表示温度，C表示湿度，D表示风力，Z表示决策属性舒适度）对于决策属性Z，当Z=P时，4,5,8,14,15,16,17,18,20，当Z=N时，1,2,3,6,7,9,10,11,12,13,19。对于条件属性A，当A=较多，A1=1,2,3,10,11,14,15；当A=正常,A2=4,5,16,17,18,20;当A=很多，A3=6,7,8,9,12,13,19。计算A的属性重要度为：SGF(A)=6/20=0.3.对于条件属性B，当B=很高，B1=1,2,3,4,5,8,9,18,20；当B=适中,B2=6,7,10,11,12,13,14,15,16,17,19。计算B的属性重要度为：SGF(B)=0/20=0.对于条件属性C，当C=很大，C1=1,2,3,4,5,6,7,10,11,16,17,19；当C=正常,C2=8,9,12,13,14,15,18,20。计算C的属性重要度为：SGF(C)=0/20=0.对于条件属性D，当D=没有，D1=1,4,6,8,10,12,18；当D=很大,D2=2,9,15,16,19;当D=中等，D3=3,5,7,11,13,14,17,20。计算D的属性重要度为：SGF(D)=0/20=0.可知，属性A,B,C,D的重要度是不同的，下面我们就用改进后的算法来构造决策树。按A划分，实例集S被划分为两个字类：S(A1)=(1,N),(2,N),(3,N),(10,N),(11,N),(14,P),(15,P)S(A2)=(4,P),(5,P),(16,P),(17,P),(18,P),(20,P)S(A3)=(6,N),(7,N),(8,P),(9,N),(12,N),(13,N),(19,N)从而，对子集S（A1）而言， P(P)=2/7,P(N)=5/7对子集S（A2）而言， P(P)=6/6,P(N)=0/6对子集S（A3）而言， P(P)=1/7,P(N)=6/7于是，由公式（1）有： H(S(A1)=-(P(P)lbP(P)+ P(N)lbP(N) =-(（2/7）lb(2/7)+（5/7）lb(5/7) =0.8631 H(S(A2)=-(P(P)lbP(P)+ P(N)lbP(N) =-(（6/6）lb(6/6)+（0/6）lb(0/6) =0 H(S(A3)=-(P(P)lbP(P)+ P(N)lbP(N) =-(（1/7）lb(1/7)+（6/7）lb(6/7) =0.5917又| S(A1)|/|S|=7/20, | S(A2)|/|S|=6/20, | S(A3)|/|S|=7/20利用属性重要度，根据式（3）则有，H(S|A)=(（7/20）+ SGF(A)H(S(A1)+ (（6/20）+SGF(A)H(S(A2)+(（7/20）+SGF(A)H(S(A3) =0.9456用同样的方法可求得：则有，H(S|B)=0.9661 ；H(S|C)=0.9328；H(S|D)=0.9880.比较可知H(S|C)H(S|A)H(S|B)H(S|D).则用改进后的ID3算法可得决策树如下：中等很高适中正常很高很多正常/很多很多/较多正常很大湿度穿衣指数P穿衣指数N湿度N风力NPN改进算法构造的决策树为了便于比较，再给出用ID3算法构造的决策树如下：PN很大没有很高适中很大正常很多较多P正常穿衣指数湿度温度PNN风力ID3算法构造的决策树比较两种算法构造的决策树我们可以看出，改进的ID3算法所生成的决策树降低了穿衣指数对天气舒适影响的重要性，离根节点的距离变远，而湿度，温度，风力在分类中的的重要度相应的提高了，这显然是与实际情况相符合的，因为在实际生活中，人们穿衣服的多少实际上是一种主观的行为，跟个人的习惯有关，比方说，老人，成人和小孩，正常人和病人在相同的环境下穿衣服肯定也是不一样的。因此，在ID3算法中加入属性重要度是有意义的！6总结首先，在充分看书之后，大家都对决策树比较感兴趣，所以决定论文方向与决策树相关。大家通关各种途径查阅资料之后，在第一次开会交流时，确定了对ID3算法进行改进这个主题。确立主题之后，我们各自思考改进方法，在第二次开会交流时，一致决定在ID3算法的条件熵计算式中加入属性重要度的概念，从而为我们的论文确立了明确的方向，之后，我们根据各自的分工将论文写好。通过这次论文，真的学到不少东西，不仅仅是对决策树，ID3算法有了更深刻的了解，而且也学会了自己提出问题，并且通过各种途径来解决它，很好的锻炼了个人思考的能力，充分了发挥了团队合作的优势！参考文献：1HAN JIAWEI，KAMBER M.数据挖掘：概念与技术M.北京：机械工业出版社，20012王国胤，姚一豫，于洪.粗糙集理论与应用研究描述.计算机学报.2009.07.153王钰.粗糙集理论及其应用研究.西安电子科技大学.2005.04.014马昕.粗糙集理论在数据挖掘领域中的应用.浙江大学.2003.09.015蒋朝哲.粗糙集理论在多属性决策中的应用研究.西南交通大学.2006.05.016冯为军.基于粗糙集理论的数据挖掘算法的研究.哈尔滨工程大学.2009.12.017瞿彬彬.基于粗糙集理论的决策信息系统知识获取研究.华中科技大学.2006.04.018 朱明.数据挖掘M.合肥：中国科学计算大学出版社，2002.67-719 张维明，数据仓库原理与应用M.北京：电子工业出版社，2002.182-199.10 洪家荣，丁明峰，李星原，等.一种新的决策树归纳学习算法J.计算机学报，1995,18（6）：470-474.11 杨明，张载鸿.决策树学习算法ID3的研究J.危机发展，2002，（5）：6-9.12 刘小虎，李生.决策树的优化算法J.软件学报，1998，9（10）：797-800.13 郭景峰，米浦波，刘国华.决策树算法的并行性研究J.计算机工程，2002，28，（8）：77-7814 QUINLAN J R.C.4.5:programs for Machine LearingM.San.Mateo CA: Morgan Kaufmann Publishers,1993.81-10615纪霞. 不完备信息系统中粗糙集理论的扩展研究与应用.安徽大学.2010.04.0116刘才辉.基于矩阵的粗糙集上，下近似求解算法.计算机应用研究.2011.0517袁修久，何华灿.优势关系下的相容约简和下近似约简.西北工业大学学报.2006.1018蔡莉，胡学钢.一种基于依赖度的决策表属性约简算法.安庆师范学院学报.2008.0219WANGX，XIE.An Extended Fuzzy-ID3 Based on the Mutual Informantion between Atributes.复旦学报.2004.1020韩忠华，刘春光，王长涛.基于属性依赖度分析的粗糙集数据挖掘方法应用.沈阳建筑大学学报.2009.0921王小魏，蒋玉明.决策树ID3算法的分析与改进.计算机工程与设计.201122李然，曾黄麟.基于依赖度的启发式约简算法.四川理工学院学报.2006.0423杨明，张载鸿.决策树学习算法ID3的研究.微机发展.2001.0524瞿俊海，张素芳，王熙照.ID3算法的理论基础.兰州大学学报.2007.12