关 键 词：

机器 学习 课件 ppt

资源描述：

机器学习课件 6.0M PPT版,机器,学习,课件,ppt

内容简介：

as the depth of water(D) in the tank increases,the rate of flow of water into the tank(Q) should decrease.,1. The function of function(chain)ruleLet u=f(x,y), z=g(u,v),2. The total influence ruleLet u=f(x,y),1. Inverse application of the function of function rule:,2. Inverse application of the total differential rule,Var1,Var2,v,u,Op4,Op2,Op5,Op3,two nodes are linked to each other.,can-reach(X3,X2),,教材：机器学习Tom M. Mitchell(卡内基梅隆大学) 著 曾华军等译，机械工业出版社 归纳学习算法，理论，应用洪家荣著，科学技术出版社,,第二章 示例学习示例学习的问题描述（见表2.1,表2.2）二. 决策树学习（ID3算法）学习效果的衡量标准（示例学习的优化问题）ID3算法： 输入：例子集（正例、反例）； 输出：决策树从树的根结点开始，每次都用“最好的属性”划分结点，直到所有结点只含一类例子为止。3. 信息增益结点nodei 例子集C, p个正例 n个反例 结点nodei的“信息熵”,头发=淡黄红色眼睛=蓝色 +头发=黑色 眼睛=褐色 ,表2.1,表2.2,outlook,sunny,overcast,rain,humidity,p,windy,high,normal,N,P,true,false,N,P,114,1-,2-,8-,9+,11+,3+,7+,12+,13+,4+,5+,6-,10+,14-,1-,2-,8-,9+,11+,6-,14-,4+,5+,10+,根结点:P=9,n=4A是例子的一个属性，有V个值a1, av, 用A扩展nodei结点把C分成V个子集C1, Cv, Ci对应ai (i=1,2, V)。 Ci含有pi个正例，ni个反例。 “期望信息熵”为属性outlook,有三个值，sunny,overcast,rain,用outlook扩展根结点得到三个子集C1,C2,C3。C1=1-,2-,8-,9+,11+,C2=3+,7+,12+,13+, C3=4+,5+,6-,10+,14-P1=2, n1=3 I(2,3)=0.971P2=4, n2=0 I(4,0)=0P3=3, n3=2 I(3,2)=0.971,则“信息增益”Gain(A)=I(p,n)-E(A)Gain(outlook)=0.940-E(outlook)=0.246bits3. 举例4. 决策树学习的常见问题1）不相关属性(irrelevant attributes)属性A把例子集分成v个子集C1,Cv，Ci含有Pi个正例、ni个反例。2) 不合适属性（Inadequate attributes)两类例子具有相同属性值。没有任何属性可进一步扩展决策树。哪类例子多，叶结点标为哪类。3）未知属性 决策树方法: 把未知属性作为“类”，原来的类作为“属性” “最通常值”办法, Bayesian 方法 按比例将未知属性例子分配到各子集中：属性A有值A1,Av, A值等于Ai的例子数pi和ni，未知属性值例子数分别为pu和nu, 在生成决策树时Ai的例子数Pi+puratio,temperature,outlook,outlook,windy,p,p,windy,windy,p,humidity,N,humidity,N,p,p,N,windy,p,outlook,p,cool,mild,hot,sunny,over,rain,true,false,true,false,sunny,over,rain,true,false,high,normal,high,norm,true,false,sunny,over,rain,三. 聚集算法1. 基本概念：定义1 （例子）. 设E=D1D2 Dn 是n维有穷向量空间，其中 Dj是有穷离散符号集。E中的元素e=(V1,V2, ,Vn)简记为叫做例子。其中VjDj。例如：对表2.1D1=高，矮；D2=淡黄，红，黑；D3=兰，褐E=D1 D2 D3例子 e=(矮，淡黄，兰）定义2。选择子是形为xj=Aj的关系语句，其中xj为第j个属性，Aj Dj; 公式（或项）是选择子的合取式，即 xj=Aj,其中 J 1, ,n; 规则是公式的析取式，即 ，其中Li为公式。,一个例子e=满足选择子xj=Aj当且仅当Vj是Aj的元素，即Vj Aj; e满足一个公式当且仅当它满足该公式的每一个选择子；e满足一条规则当且仅当e满足该规则的至少一个公式。 例子满足选择子（公式、规则）也称做选择子（公式、规则）覆盖该例子。例如： 例子e= 满足选择子头发=淡黄红色和 眼睛=蓝色 ；满足公式头发=淡黄红色 眼睛=蓝色 。,第二章 示例学习示例学习的问题描述（见表2.1,表2.2）二. 决策树学习（ID3算法）学习效果的衡量标准（示例学习的优化问题）ID3算法： 输入：例子集（正例、反例）； 输出：决策树从树的根结点开始，每次都用“最好的属性”划分结点，直到所有结点只含一类例子为止。3. 信息增益结点nodei 例子集C, p个正例 n个反例 结点nodei的“信息熵”,头发=淡黄红色眼睛=蓝色 +头发=黑色 眼睛=褐色 ,表2.1,表2.2,根结点:P=9,n=4A是例子的一个属性，有V个值a1, av, 用A扩展nodei结点把C分成V个子集C1, Cv, Ci对应ai (i=1,2, V)。 Ci含有pi个正例，ni个反例。 “期望信息熵”为属性outlook,有三个值，sunny,overcast,rain,用outlook扩展根结点得到三个子集C1,C2,C3。C1=1-,2-,8-,9+,11+,C2=3+,7+,12+,13+, C3=4+,5+,6-,10+,14-P1=2, n1=3 I(2,3)=0.971P2=4, n2=0 I(4,0)=0P3=3, n3=2 I(3,2)=0.971,outlook,sunny,overcast,rain,humidity,p,windy,high,normal,N,P,true,false,N,P,114,1-,2-,8-,9+,11+,3+,7+,12+,13+,4+,5+,6-,10+,14-,1-,2-,8-,9+,11+,6-,14-,4+,5+,10+,则“信息增益”Gain(A)=I(p,n)-E(A)Gain(outlook)=0.940-E(outlook)=0.246bits3. 决策树学习的常见问题1）不合适属性（Inadequate attributes)两类例子具有相同属性值。没有任何属性可进一步扩展决策树。 哪类例子多，叶结点标为哪类。3）未知属性 “最通常值”办法 按比例将未知属性例子分配到各子集中：属性A有值A1,Av, A值等于Ai的例子数pi和ni，未知属性值例子数分别为pu和nu, 在生成决策树时Ai的例子数Pi+puratio,temperature,outlook,outlook,windy,p,p,windy,windy,p,humidity,N,humidity,N,p,p,N,windy,p,outlook,p,cool,mild,hot,sunny,over,rain,true,false,true,false,sunny,over,rain,true,false,high,normal,high,norm,true,false,sunny,over,rain,三. 聚集算法1. 基本概念：定义1 （例子）. 设E=D1D2 Dn 是n维有穷向量空间，其中 Dj是有穷离散符号集。E中的元素e=(V1,V2, ,Vn)简记为叫做例子。其中VjDj。例如：对表2.1D1=高，矮；D2=淡黄，红，黑；D3=兰，褐E=D1 D2 D3例子 e=(矮，淡黄，兰）定义2。选择子是形为xj=Aj的关系语句，其中xj为第j个属性，Aj Dj; 公式（或项）是选择子的合取式，即 xj=Aj,其中 J 1, ,n; 规则是公式的析取式，即 ，其中Li为公式。,一个例子e=满足选择子xj=Aj当且仅当Vj是Aj的元素，即Vj Aj; e满足一个公式当且仅当它满足该公式的每一个选择子；e满足一条规则当且仅当e满足该规则的至少一个公式。 例子满足选择子（公式、规则）也称做选择子（公式、规则）覆盖该例子。例如： 例子e= 满足选择子头发=淡黄红色和 眼睛=蓝色 ；满足公式头发=淡黄红色 眼睛=蓝色 。,第三章 学习的计算理论示例学习的优化问题最优覆盖问题(MCV)生成具有最少数目公式的覆盖；最简公式问题(MCOMP)生成具有最少数目选择子及属性值的公式，或极大复合；最优示例学习问题(OPL)生成只由最简公式组成的最优覆盖。二. 最优覆盖问题是NP难题定理3.1：已知两个问题P1和P2,如果P1是NP难题。并且P1可在多项式时间内归纳到P2,则P2也是NP难题，并称P1可（多项式）归纳到P2,如果P2反过来也能归纳到P1,则称P1和P2是等价的。定理3.2：最优集合覆盖问题(SETCV)是从一个有穷集合的有穷覆盖中，找到一个具有最小基数的子覆盖。即设T是一个m个点的集合，F是T的子集族。 F=S1, ,Sp, 其中Si T。SETCV是找到F的具有最少数目的子族F,使得F是T的一个覆盖：F F, 并且 |F|=最小；其中符号| |表示基数。定理3.3 最优覆盖问题(MCV)是NP难题。设 T=1, ,7 , F=S1, ,S6 S1=1,4,5,7, S2=3,4, S3=2,5,7,S4=1,2,6, S5=1,3,7, S6=3,5,6,定理3.4 最简公式问题是NP难题。定理3.5 最优示例学习问题是NP难题。SETCV MCV, Li,归纳,P0,Li MCOMP P0+三. 最小属性子集问题定理3.6 最小属性子集问题(MAS)是NP难题。,归纳到,Pi,算法GMASA ,i1;建立正例集 PE在反例集NE背景下的联合扩张矩阵EM(PE|NE); 这里联合扩张矩阵是将所有正例的扩张矩阵罗在一起。,(3) 在EM(PE|NE)找到一列，记为第j列，它含有最少数目的死元素“*”,AA xj.(4) 如果EM(PE|NE) 删去所有在第j列含有非死元素的行；(5) 如果EM(PE|NE)= ,则终止，并返回A;否则iI+1.并转向(3);参考文献：归纳学习算法，理论，应用。 洪加荣著 P.46-52, P.57-58.,1. 将h初始化为H中最特殊假设 2. 对每个正例x 对h的每个属性约束a 如果x满足a 那么不做任何处理 否则将h中a替换为x满足的另一个更一般约束3. 输出假设hh hhh,表 FIND-S算法,候选消除算法：将G集合初始化为H中极大一般假设将S集合初始化为H中极大特殊假设对每个训练例d,进行以下操作： 如果是一正例 从G中移去所有与d不一致的假设 对S中每个与d不一致的假设s 从s中移去s 把s的所有的极小泛化式h加入到S中，其中h满足 h与d一致，而且G的某个成员比h更一般 从S中移去所有这样的假设：它比S中另一假设更一般如果是一个反例 从S中移去所有与d不一致的假设 对G中每个与d不一致的假设g 从G中移去g 把g的所有的极小特殊化式h加入到G中，其中h满足 h与d一致，而且S的某个成员比h更特殊 从G中移去所有这样的假设：它比G中另一假设更特殊, ,S0:,S1:,S2:,G0,G1,G2:, ,S2,S3:,G3:,G2:, , ,S3:,S4:,G4:,G3:,表 目标概念EnjoySport的正例和反例,第三章 概念学习和一般到特殊序2.1 简介定义：概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。2.2 概念学习任务,概念学习任务能被描述为：实例的集合、实例集合上的目标函数、候选假设的集合以及训练例的集合。归纳学习假设：任一假设如果在足够大的训练样例集中很好地逼近目标函数，它也能在未见实例中很好地逼近目标函数。2.3 作为搜索的概念学习EnjoySport的实例空间： 322 2 2 2=96假设空间：5 4 4444=51201+4 33 3 3 3=973假设的一般到特殊序定义：令hj和hk为在X上定义的布尔函数。称hj more_general_than_or_equal_to hk（记作 hjg hk），当且仅当,已知： 实例集X:可能的日子由下面的属性描述： Sky（可能取值为Sunny,Cloudy和Rain) AirTemp(可取值为Warm和Cold) Humidity(可取值为Normal和High) Wind(可取值为Strong和Weak) Water(可取值为Warm和Cool) Forecast(可取值为Same和Change) 假设集H: 每个假设描述为6个属性Sky,AirTemp,Humidity,Wind,Water和Forecast的值约束的合取。约束可以为“？”（表示接受任意值），“ ” （表示拒绝所有值），或一特定值,目标概念c: EnjoySport: X0,1 训练样例集D:目标函数的正例和反例（见表2-1)求解： H中的一假设h,使对于X中任意x, h(x)=c(x),实例集 X,假设集 H,h1,h2,h3,特殊,一般,列表后消除算法变型空间VersionSpace包含H中所有假设的列表对每个训练例 从变型空间中移出所有h(x) c(x)的假设h3. 输出VersionSpace中的假设列表,表 列表后消除算法, ,S:,G:, ,,LIFTABLE, DRINKABLE-FROM,Fred is the father of Mary and is a millionaire. John approached Mary. She was wearing blue jeans. Johnpointed a gun at her and told her he wanted her to get into his car. He drove her to his hotel and lockedher in his room. John called Fred and told him John was holding Mary captive. John told Fred if Fredgave him $250,000 at Trenos then John would release Mary. Fred gave him the money and John releasedMary.,参考文献：（第1次课第13次课）Machine Learning:An Artificial Intelligence Approach, Michalski , (TP11/M149)P83-134(Chapter 4 A Theory and Methogology of Inductive Learning)P307-363 (Chapter 10 Rediscovering Chemistry with the BACON System; Chapter 11 Learning From Observation: Conceptual Clustering)2.归纳学习算法，理论，应用，洪家荣著，科学出版社。（TP18/H46）P1-43 第一章：有导师学习算法P43-58 第二章：学习理论（4，5）本章前半部分，不包括PAC学习P81-103 第三章：无导师学习算法3.机器学习：实现人工智能的途径，Michalski, 科学出版社。(TP18/M33)第四章：归纳学习的理论和方法学，P49-81,第十章：BACON系统重新发现化学定律；第十一章：从观察中学习：概念聚类 P190-2264. J.R, QUINLAN, Induction of Decision Trees, Machine Learning 1: 81-106, 19865.Jiarong Hong, AE1: An Extension Matrix Approximate Method for the General Covering Problem, International Journal of Computer and Information Sciences, Vol.14,No.6,1985.6.,Choose initial “seed” events from E,Determine a star for each seed against the other seed events,By appropriately modifying and selecting complexes from stars,construct a disjoint cover of E that optimizes the criterion LEF,Is the terminationCriterion satisfied?,END,a,Given: E-a set of data events k-the number of clusters LEF-the clustering quality criterion,Y,N,Is the clusteringquality improving?,Choose k new seeds whichAre central events,Choose k new seeds which are “border” events,a,Y,N,e1,e2,X1 X2,012,X4X3,0 1 2,d,f,a,b,c,K=2 ; LEF-sparseness, Complexity; Termination criterion:base=2,probe=2Iteration 1Step 1: Select seed: e1,e2Step 2:Produce Stars: RG(e1|e2,m) RG(e2|e1,m) m=5RG(e1|e2,m)=x2=ax3=01,X4=1 2RG(e2|e1,m)=x2=b c,x4=0 2,Generalize:RG(e1|e2,m)=x2=ax31,X4=12RG(e2|e1,m)=x2=f,x4=02Step 3:Evaluation and Modification(disjoint) Sparseness ComplexityComplex 1: x2=ax31 15 2 Complex 2: x2=f 47 1 62 3(b) Complex 1: x4=12 Complex 2: X2=f (c) Complex 1: x2=ax31 Complex 2: X4=02,(d) Complex 1: x4=12 Complex 2: x4=02Step 4:The termination criterion is testedStep 5:select new seedse1,e4,e6 e2,e3,e5,e7,e8,e9,e10Central events: e4,e8Iteration 2Step 2:Produce satrs RG(e4|e8,m ), RG(e8|e4,m)RG(e4|e8,m)=x2=ax31,x11x3 1,x3=0RG(e8|e4,m)=x1=2,x2=f,x31,sparseness ComplexityComplex 1: x11x31 31 2Complex 2: x1=2 22 1 53 3Step 4: Termination criterion is tested (the last of the base iterations)Step 5:e1,e2,e3,e4,e5 e6,e7,e8,e9,e10New seeds: e1,e8Iteration 3The iteration produces the same clustering as iteration1Step 4: Termination criterion is tested (the first of the two probeStp 5: not better than the previous one, border events are selected,New seeds e2,e6Iteration 4Produces a new clustering: Sparseness ComplexityComplex 1: x31 49 1Complex 2: x3=0 22 1 71 2结果：x11x3 1x1=2,e1,e2,X1 X2,012,X4X3,0 1 2,知识发现S1 S S2 S F1=Cover(S1,S-S1) F2=Cover(S2,S-S2) 如果 S2 S1 S 则 F2 F1,知识发现算法1）例子分类。由两种方法对例子集合分类：层次分类。将已知例子集s依次分为一个树状的层次结构，S,s1,.Sn,S11,S1k,Sk1,Skk,。其中Sij是Si的子集。平行分类。令k=2,3,r,分别对同一个例子集S分类成k各子集，形成r个族，S, , 。2)描述抽象。产生每个子集在整个例子集S中的描述。即对层次分类，产生 , , 。其中Fi=Cover (Si,S-Si),Fij=Cover(Sij,S-Sij)。对平行分类。产生 , 。其中,i=1,2,l, 及 l=2,r。,3)规则形成。先在第1)步产生的集合中寻找子集关系，然后在第2)步产生相应的描述间构造决策规则。,S=110,S1=14,S2=58,S3=9,10,S11=1,2,S12=3,4,S21=5,6,S22=7,8,S31=0,S32=10,奶=有毛发=有,食物=肉羽毛=无脚=有爪,脚=蹄,羽毛=有,会飞=是脚=有爪,脚=无 食物=蜜,1）脚=蹄 奶=有 毛发=有，因S12 S12) 食物=肉羽毛=无脚=有爪 奶=有 毛发=有，因S11 S1。3）会飞=是脚=有爪 羽毛=有，因S22 S2,机器发现：BACON系统基本定律：增加定律：如果变元x的值随着变元Y的值增加而增加，则定义比值X/Y并检验该比值是否为常数。(2) 减少定律如果变元x的值随着变元Y的值减少而增加，则定义乘积XY并检验该乘积是否为常数。(3) 常数定律如果x的值对于很大一个数量接近于常数，则假定x总具有这个值,PV/T=8.32,参考文献：Learning from observation: conceptual clustering, in: Michalski(eds.), Machine Learning: Artificial Intelligence Approach, Vol.1, 2. 归纳学习算法，理论，应用. 洪家荣 科学出版社 P96-102.,Choose initial “seed” events from E,Determine a star for each seed against the other seed events,By appropriately modifying and selecting complexes from stars,construct a disjoint cover of E that optimizes the criterion LEF,Is the terminationCriterion satisfied?,END,a,Given: E-a set of data events k-the number of clusters LEF-the clustering quality criterion,Y,N,Is the clusteringquality improving?,Choose k new seeds whichAre central events,Choose k new seeds which are “border” events,a,Y,N,e1,e2,X1 X2,012,X4X3,0 1 2,d,f,a,b,c,K=2 ; LEF-sparseness, Complexity; Termination criterion:base=2,probe=2Iteration 1Step 1: Select seed: e1,e2Step 2:Produce Stars: RG(e1|e2,m) RG(e2|e1,m) m=5RG(e1|e2,m)=x2=ax3=01,X4=1 2RG(e2|e1,m)=x2=b c,x4=0 2,Generalize:RG(e1|e2,m)=x2=ax31,X4=12RG(e2|e1,m)=x2=f,x4=02Step 3:Evaluation and Modification(disjoint) Sparseness ComplexityComplex 1: x2=ax31 15 2 Complex 2: x2=f 47 1 62 3(b) Complex 1: x4=12 Complex 2: X2=f (c) Complex 1: x2=ax31 Complex 2: X4=02,(d) Complex 1: x4=12 Complex 2: x4=02Step 4:The termination criterion is testedStep 5:select new seedse1,e4,e6 e2,e3,e5,e7,e8,e9,e10Central events: e4,e8Iteration 2Step 2:Produce satrs RG(e4|e8,m ), RG(e8|e4,m)RG(e4|e8,m)=x2=ax31,x11x3 1,x3=0RG(e8|e4,m)=x1=2,x2=f,x31,sparseness ComplexityComplex 1: x11x31 31 2Complex 2: x1=2 22 1 53 3Step 4: Termination criterion is tested (the last of the base iterations)Step 5:e1,e2,e3,e4,e5 e6,e7,e8,e9,e10New seeds: e1,e8Iteration 3The iteration produces the same clustering as iteration1Step 4: Termination criterion is tested (the first of the two probeStp 5: not better than the previous one, border events are selected,New seeds e2,e6Iteration 4Produces a new clustering: Sparseness ComplexityComplex 1: x31 49 1Complex 2: x3=0 22 1 71 2结果：x11x3 1x1=2,e1,e2,X1 X2,012,X4X3,0 1 2,知识发现S1 S S2 S F1=Cover(S1,S-S1) F2=Cover(S2,S-S2) 如果 S2 S1 S 则 F2 F1,知识发现算法1）例子分类。由两种方法对例子集合分类：层次分类。将已知例子集s依次分为一个树状的层次结构，S,s1,.Sn,S11,S1k,Sk1,Skk,。其中Sij是Si的子集。平行分类。令k=2,3,r,分别对同一个例子集S分类成k各子集，形成r个族，S, , 。2)描述抽象。产生每个子集在整个例子集S中的描述。即对层次分类，产生 , , 。其中Fi=Cover (Si,S-Si),Fij=Cover(Sij,S-Sij)。对平行分类。产生 , 。其中,i=1,2,l, 及 l=2,r。,3)规则形成。先在第1)步产生的集合中寻找子集关系，然后在第2)步产生相应的描述间构造决策规则。,1）脚=蹄 奶=有 毛发=有，因S12 S12) 食物=肉羽毛=无脚=有爪 奶=有 毛发=有，因S11 S1。3）会飞=是脚=有爪 羽毛=有，因S22 S2,机器发现：BACON系统基本定律：增加定律：如果变元x的值随着变元Y的值增加而增加，则定义比值X/Y并检验该比值是否为常数。(2) 减少定律如果变元x的值随着变元Y的值减少而增加，则定义乘积XY并检验该乘积是否为常数。(3) 常数定律如果x的值对于很大一个数量接近于常数，则假定x总具有这个值,第三章 规则学习算法1. 基本概念：定义1 （例子）. 设E=D1D2 Dn 是n维有穷向量空间，其中 Dj是有穷离散符号集。E中的元素e=(V1,V2, ,Vn)简记为叫做例子。其中VjDj。例如：对表2.1D1=高，矮；D2=淡黄，红，黑；D3=兰，褐E=D1 D2 D3例子 e=(矮，淡黄，兰）定义2。选择子是形为xj=Aj的关系语句，其中xj为第j个属性，Aj Dj; 公式（或项）是选择子的合取式，即 xj=Aj,其中 J 1, ,n; 规则是公式的析取式，即 ，其中Li为公式。,一个例子e=满足选择子xj=Aj当且仅当Vj是Aj的元素，即Vj Aj; e满足一个公式当且仅当它满足该公式的每一个选择子；e满足一条规则当且仅当e满足该规则的至少一个公式。 例子满足选择子（公式、规则）也称做选择子（公式、规则）覆盖该例子。例如： 例子e= 满足选择子头发=淡黄红色和 眼睛=蓝色 ；满足公式头发=淡黄红色 眼睛=蓝色 。定义3：普化(generalize) :减少规则的约束，使其覆盖更多的训练例子叫普化。,定义4：特化(specialize) : 增加规则的约束，使其覆盖训练例子较少叫特化。定义5：一致：只覆盖正例不覆盖反例的规则被称为是一致的。定义6：完备：覆盖所有正例的规则被称为是完备的。,2. GS算法：GS算法输入： 例子集；输出： 规则；原则： （a) 从所有属性中选出覆盖正例最多的属性； (b) 在覆盖正例数相同的情况下，优先选择只覆盖正例不覆盖反例的属性值；设PE,NE是正例，反例的集合。 PE,NE是临时正，反例集。CPX表示公式，F表示规则（概念描述）。Ftrue;PE PE, NE NE, CPXtrue;按上述(a) (b)两规则选出一个属性值V 0 , 设V 0 为第j0个属性的取值，建立选择子Xj0=V0并加入公式中，CPXCPX Xj0=V0如果Xj0=V0覆盖NE中的反例，转(5); 否则 FFCPX, 转(6);,(5) 重新构造PE和NE, PE含有原来PE中被Xj0=V0覆盖的例子，NE含有原来NE中被Xj0=V0覆盖的例子，转（3）；(6) PEPEPE,如果PE= ,停止，否则转(2);GS算法举例：例子集见表2.3学习结果：ESR=normalAusculation=bublelikeX-ray=spotESR=normal3.AQ算法：普化(generalize) :特化(specialize) : 一致完备,肺炎,表2.3 肺炎与肺结核两组病历,AQ算法：输入：例子集、参数#SOL、#CONS、Star的容量m、优化标准；输出：规则；1）Pos和NEG分别代表某概念的正例和反例的事件集合 从Pos中随机地选择一事件 生成事件e相对于反例集NEG的一个约束Star(reduced star),G(e|NEG,m) , 其中元素不多于m个。 在得到的star中，根据设定的优化标准LEF找出一个最优的描述D。 若描述D完全覆盖集合Pos,则转 否则，减少Pos的元素使其只包含不被D覆盖的事件。从步骤开始重复整个过程。 生成所有描述D的析取，它是一个完备且一致的概念描述。,2) Star生成: Induce方法事件e的各个选择符被放入PS(partial star)中,将ps中的元素按照各种标准排序.在ps中保留最优的m个选择符.对ps中的选择符进行完备性和一致性检查,从ps中取出完备一致的描述放入SOLUTION表中,若SOLUTION表的大小大于参数#SO