《 人工智能引论》课件 第6、7章 基于经验的启发式搜索、机器学习绪论

第六章基于经验的启发式搜索6.1启发式搜索的基本思想6.2状态空间的启发式搜索6.3与或图的启发式搜索6.4博弈树的搜索6.1启发式搜索的基本思想前面讨论的搜索方法都是按事先规定的、根据结点的深度制定的路线进行搜索，搜索过程机械，具有较大的盲目性,生成的无用结点较多，搜索空间较大，因而效率不高。除了结点的深度信息之外，如果能够利用结点暗含的与问题相关的一些特征信息来预测目标结点的存在方向，并沿着该方向搜索，则有希望缩小搜索范围，提高搜索效率。利用结点的特征信息来引导搜索过程的一类方法称为启发式搜索。任何一种启发式搜索算法在生成一个结点的全部子结点之前，都将使用算法设计者提供的评价函数判断这个“生成”过程是否值得进行。评价函数通常为每个结点计算一个整数值，称为该结点的评价函数值。通常，评价函数值小的结点被认为是值得进行“生成”过程。按照惯例，将“生成结点n的全部子结点”称为“扩展结点n”。启发式搜索（最好优先搜索）确定路径6.1.1启发信息与评价函数用来评估结点重要性的函数称为评价函数。评价函数f（n）对从初始结点S0出发经过、结点n到达目标结点Sg的路径代价进行估计。其一般形式为g（n）表示从初始结点S0到结点n的已获知的最小代价；h（n）表示从n到目标结点Sg的最优路径代价的估计值，它体现了问题的启发式信息。所以，h（n）被称为启发式函数。f（n）由g（n）和h（n）两部分组成，启发式搜索算法可以使用f（n）的不同组合，进而表现出不同的特性。例如，有的算法使用f（n）=g（n），有的算法使用f（n）=h（n），有的算法使用f（n）=g（n）+h（n）6.1.2启发式搜索策略启发式搜索策略的目标是，通过优先考察最有希望出现在较短解路径上的节点，来显著提高搜索的有效性。启发式搜索是利用启发性信息进行指导的搜索。启发性信息就是有利于尽快找到问题之解的信息，按其用途可分为如下3种：（1）用于扩展节点的选择。即决定应先扩展哪一个节点，以免盲目地扩展。（2）用于生成节点的选择。即在扩展一个节点的过程中，用于决定将生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。（3）用于删除节点的选择。即决定应该从搜索树中抛弃或修剪哪些节点，以免造成进一步的时空浪费。需要指出的是，不存在适合所有问题的万能启发性信息，即不同的问题有不同的启发性信息。本章只讨论利用上述第一种启发性信息的状态空间的搜索方式，即决定哪个是下一步要扩展的节点。6.2状态空间的启发式搜索状态空间的启发式搜索指在状态空间中，利用启发式信息来指导搜索过程的一类算法。其目标是通过评估每个状态到目标状态的估计成本，从而优先探索那些看起来更有希望的路径，以提高搜索效率和找到最优解。启发式搜索结合了传统的状态空间搜索和启发式方法，通过减少需要探索的状态数量来加快问题求解过程。下面分别介绍以启发式函数f（n）=h（n）作为指导节点扩展的搜索算法，即最好优先搜索算法（全局最优法）；以代价函数f（n）=g（n）指导节点扩展的搜索算法，即分支限界法；以评价函数f（n）=g（n）+h（n）作为指导节点扩展的搜索算法的最佳图搜索法A*6.2.1最好优先搜索算法为了处理环，最好优先搜索算法用OPEN表和CLOSED表记录状态空间中那些被访问过的所有状态。这两个表中的结点及它们关联的边构成了状态空间的一个子图，称为搜索图。OPEN表存储一些结点，其中每个结点n的启发式函数值已经计算出来，但是n还没有被“扩展”。CLOSED表存储一些结点，其中每个结点已经被扩展。该类算法每次选代从OPEN表中取出一个较优的结点n进行扩展，将n的每个子结点根据情况放入OPEN表。算法循环直到发现目标结点或者OPEN表为空。算法中的每个节点带有一个父指针，该指针用于合成解路径。6.2.1最好优先搜索算法ProcedureBest-FirstSearchBegin建立只含初始结点S0的搜索图G，计算f（S0）；将S0放入OPEN表；将CLOSED表初始化为空。WhileOPEN表不空DoBegin从OPEN表中取出f（n）值最小的结点n，将从OPEN表中删除并放入CLOSED表。If

n是目标结点Then根据n的父指针指出从S0到n的路径，算法停止。ElseBegin扩展结点nIf

结点n有子结点ThenBegin（1）生成n的子结点集合{mi}把mi作为n的子结点加入到G中，并计算f（mi）。（2）Ifmi未曾在OPEN和CLOSED表中出现，Then将它们配上刚计算过的f值，将mi的父指针指向n，并把它们放入OPEN表。（3）Ifmi已经在OPEN表中，Then该结点一定有多个父结点。在这种情况下比较mi相对于n的f值和mi相对于其原父指针指向的结点的值，若前者不小于后者，则不做任何更改；否则将mi的f值更改为mi相对于n的f值，mi的父指针更改为n。最好优先搜索算法流程：6.2.1最好优先搜索算法（4）Ifmi已经在CLOSED表中，Then该结点同样也有多个父结点。在这种情况下，比较mi相对于n的f值和mi相对于其原父指针指向的结点的值如果前者不小于后者，则不作任何更改；否则将mi从CLOSED表移到OPEN表，置mi的父指针指向n。

（5）按f值从小到大的次序，对OPEN表中的结点进行重新排序。EndEndEndEnd最好优先搜索算法流程（接上表）：上述搜索算法生成一个明确的图G（称为搜索图）和一个G的子集T（称为搜索树），图G中的每一个结点也在树T上。搜索树是由结点的父指针来确定的。G中的每一个结点（除了初始结点S0）都有一个指向G中一个父辈结点的指针。该父辈结点就是那个结点在T中的唯一父辈结点。算法中（3）、（4）步保证对每一个扩展的新结点，其父指针的指向是已经产生的路径中代价最小的。6.2.1最好优先搜索算法贪婪最好优先算法：最好优先搜索算法是一个通用的算法框架。如果将该框架中的

f（n）实例化为h（n），则得到一个具体的算法，称为贪婪最好优先搜索（GreedyBest-FirstSearch，GBFS）算法。GBFS算法在判断是否优先扩展一个结点n时仅以n的启发值为依据。n的启发值越小，表明了从n到目标结点的代价越小，因而GBFS算法沿着n所在的分枝搜索就越可能发现目标结点。6.2.1最好优先搜索算法以八数码问题为例，令启发函数h（x）为节点x的棋局与目标棋局相比数码位置不同的个数，则搜索树如下图所示，图中节点旁边的数字为该节点启发函数的值6.2.2分支限界法分支限界法在文献中通常称为统一代价搜索（Uniform-CostSearch）。按照递增的代价--更精确地说，按照非递减代价制订路径。路径的估计代价很简单：f（n）=g（n），不采用剩余距离的启发式搜索；或等价地说，估计h（n）处处都为0。这种方法与广度优先搜索的相似性显而易见，即首先访问最靠近起始节点的节点。但是，使用分支限界法，代价值可以假设为任何正实数值。这两个搜索之间的主要区别是，最好优先搜索努力找到通往目标的某一路径，然而分支限界法努力找到一条最优路径。使用分支限界法时，一旦找到了一条通往目标的路径，这条路径很可能是最优的。为了确保这条找到的路径确实是最优的，分支限界法继续生成部分路径，直到每条路径的代价大于或等于所找到的路径的代价6.2.2分支限界法//BranchandBoundSearch.

BranchBound（Root_Node，goal）{CreateQueueQInsertRoot_NodeintoQWhile（QIsNotEmpty）{G=RemovefromIf

（G=goal）ReturnthepathfromRoot_NodetoG；elseInsertchildrenofGintotheQSortQbypathlength}//andwhileReturnfailure}分支限界法流程：6.2.2分支限界法没有启发式估计值的搜索树分支限界法（a）从根节点A开始。生成从根开始的路径（b）因为B具有最小代价，所以被扩展（c）在3个选择中，C具有最小代价，因此被扩展（d）节点H代价最低，因此被扩展（e）发现了到G2的路径，但为查看是否有路径到目标的距离更小，需扩展到其他分支（f）F和N的节点都具有15的代价：最右边的节点首先扩展（g）分支限界法其余部分6.2.2分支限界法遵循分支限界法，寻求一条到达目标的最佳路径的（a）~（f）和（g）。我们观察到，节点按照递增的路径长度扩展。搜索在（f）和（g）中继续，直到任何部分的路径的代价大于或等于到达目标的最短路径21。如（g）所示，请观察分支限界的其余部分。分支限界算法接下来的4个步骤如下。步骤1：到节点N的路径不能被延长。步骤2：下一条最短路径，A→B-E被延长了；当前，它的代价超过了21。步骤3：到节点M和N的路径不能被延长。步骤4：最小部分路径，具有的代价≤21被延长了。当前，代价是29，超过了开始到目标最短路径。在（g）中，分支限界法发现到达目标的最短路径是A到C到H到G2，代价为21。6.2.2分支限界法下图是五个城市交通路线图，A城市是出发地，E城市是目的地，两城市之间的交通费用（代价）如图中数字所示。试求从A到E最小费用的旅行路线。画出其如（b）所示的代价树。在代价树中，首先对A进行扩展，得到C1和B1，由于C1的代价小于B1的代价，所以把C1送入CLOSED表进行考察。对C1扩展得到D1，由于B1的代价小于D1，所以把B1送入CLOSED表进行考察。扩展B1得到D2和E1在OPEN表中的D1，D2和E1三个节点中，它们的代价g（D1）<g（D2）<g（E1），所以把D1送入CLOSED表进行考察。扩展D1得到E2和B2在OPEN表中g（E2）=g（D2）<g（B2）<g（E1），所以考察E2。E2是目标状态节点。所以采用分支限界法得到路径为ACBE，这是一条最小费用路径。6.2.3最佳图搜索算法A*如果最好优先搜索算法中的f（n）被实例化为f（n）=g（n）+h（n），则称之为A算法。进一步细化，如果启发函数h满足对于任一结点n，h（n）的值都不大于n到目标结点的最优代价，则称此类A算法为A*算法。A*算法在一些条件下能够保证找到最优解即A*算法具有最优性。下面首先以八数码为例介绍A算法的运行过程，然后介绍对A*算法最优性的分析。6.2.3最佳图搜索算法A*在A算法运行的初始时刻，OPEN表中只有初始结点，因此我们扩展它，得到右图中的第二层结点，将这些结点全部放入OPEN表。6.2.3最佳图搜索算法A*在第二次迭代过程中，A算法选择OPEN表中具有最小f值为1+3=4的结点扩展，得到第三层的3个结点，并将它们放入OPEN表。在第三次迭代中，A算法选择OPEN表中f值为2+3=5的结点进行扩展。在第四次迭代中，A算法选择OPEN表中f值为2+3=5的另一个结点进行扩展。在第五次迭代中，A算法选择OPEN表中f值为3+2=5的结点进行扩展。在第六次迭代中，A算法选择OPEN表中f值为4+1-5的结点进行扩展。在第七次迭代中，A算法选择OPEN表中f值为5＋0=5的结点进行扩展。通过此例可以发现，A算法相对于宽度优先搜索和深度优先搜索都具有优势。6.2.3最佳图搜索算法A*但是，由于对启发函数h没有任何限制，A算法不能保证找到最优解。经研究发现，A算法在如下3个条件成立时能够保证得到最优解：（1）启发函数h对任一结点n都满足h（n）不大于n到目标的最优代价。（2）搜索空间中的每个结点具有有限个后继。（3）搜索空间中每个有向边的代价均为正值。为了表明此类A算法的重要性，将此类A算法称为A*算法，称上述3个条件为A算法的运行条件。6.2.3最佳图搜索算法A*对h的限制可以更为正式地表述如下：令h*是能计算出任意结点到目标的最优代价的函数，称之为“完美启发函数”。如果

n：h（n）≤h*（n），则称h为可采纳的启发函数（admissibleheuristicfunction），或者称h是可采纳的，或者简称为可纳的。此外，也引入函数g*，它能计算从开始结点到任意结点的最优代价。定义估价函数：f*（n）=g*（n）+h*（n）。这样f*（n）就是从起始结点出发经过结点到达目标结点的最佳路径的总代价。把评价函数f（n）和f*（n）相比较，g（n）是对g*（n）的估价。h（n）是对h*（n）的估价。在这两个估价中，尽管g（n）容易计算，但它不一定就是从起始结点S。到结点n的真正的最短路径的代价，很可能从初始结点S到结点n的真正最短路径还没有找到，所以一般都有g（n）>g*（n）。但应注意，A*算法的步骤（3）和（4）保证了如果发现n的更好的g（n）值，则以此值作为n的最新的g（n），并相应地修改n的父指针，步骤（4）还在n已被扩展的情况下将n移回OPEN表，使得会被再次扩展。6.2.3最佳图搜索算法A*现在给出一些关于算法性质的定义，为了叙述方便，将一个算法记作M。完备性：如果存在解，则M一定能找到该解并停止，则称M是完备的。可纳性：如果存在解，则M一定能够找到最优的解，则称M是可纳的。优越性（DoMINance）：一个算法M1称为优越于另一个算法M2，指的是如果一个结点由M1扩展，则它也会被M2扩展，即M1扩展的结点集是M2扩展的结点集的子集。最优性：在一组算法中一个算法M称为最优的，如果M比其他算法都优越。A*算法的完备性和可纳性。为了证明该定理，我们首先介绍引理6.16.2.3最佳图搜索算法A*引理6.1在A*算法停止之前的每次结点扩展前，在OPEN表上总是存在具有如下性质的结点n*：（a）n*位于一条解路径上。（b）A*算法已得出从初始结点S0到n*的最优路径。（c）f（n*）≤f*（S0）。证明：为证明此引理在A*算法的每次结点扩展前都成立，只需证明：（1）本引理在A*算法初始执行时成立；（2）若本引理在一个结点被扩展之前成立，则在该结点被扩展之后本引理同样成立。按照此思路，将采用归纳法进行证明。6.2.3最佳图搜索算法A*归纳基础：在A*算法在第1次结点扩展前（即，S0被选择进行扩展之前），S0在OPEN表中，S0位于一条最优解路径上（因为所有的解路径都以为S0起点），并且A*已得知从S0到S0的最优路径。此外，根据f的定义，因此，在第1次结点扩展前，S0就是满足引理结论的n*。归纳步骤：假设引理在第m次（m≥0）结点扩展后成立，证明本引理在第m+1次结点扩展后仍成立。假定A*算法在扩展m个结点后，OPEN表中存在一个结点n*，A*算法已知从S0到n*的最优路径。那么，若n*在第m+1次扩展中未被选择，则它在第m+1次扩展后是满足引理要求的结点n*，在此情况下引理得证。6.2.3最佳图搜索算法A*另一方面，若n*在第m+1次扩展时被选择，则n*的每一个未在OPEN表和CLOSED表中出现的子结点都将被放入OPEN表，而且，这些新的子结点中必然存在一个结点（记为np）位于最优解路径上（因为经过n*的最优解路径必然在经过n*后再经过n*的某个子结点，所以np必然存在）。np也满足性质（b），即A*已得出从S0到np的最优路径，该路径记为P1：由到达n*的最优路径再连接上n*到np的有向边而组成。如果从S0到达np的最优路径不同于P1，则P1不构成最优解路径，从而与n*在最优解路径上的假设相矛盾。因此，np满足性质（a）和（b）。下面还需证明性质（c）在所有归纳步骤中成立，即证明性质（c）在A*停止前的0~m次扩展时都成立。6.2.3最佳图搜索算法A*对于任一结点n*（n*在最优解路径上；且A*算法已得出从S0到n*的最优路径，即g（n*）=g*（n*）），它满足如下不等式：因此，性质（c）成立。至此，引理得证。6.2.3最佳图搜索算法A*定理6.1若A*算法的运行条件成立，并且搜索空间中存在从初始结点S0到目标结点的代价有穷的路径，则A*算法保证停止并得出S0到目标结点的最优代价路径。证明：在引理6.1的基础上，证明本定理。首先证明如果搜索空间存在目标结点，则A*必然停止，然后证明A*在停止时已找到最优解路径。首先证明A*必然停止：假设它不停止，则它将不断扩展OPEN表中的结点。我们已假定搜索空间的分枝因子（每个结点的平均子结点数目）为一个有穷值，且每条有向边的权值为正数。所以，随着OPEN表上的结点在搜索树中的深度增加，它们的g值将无限增长。这种增长必然导致A*在未来的一次结点扩展时OPEN表中所有结点的g值都大于f（S0），此情况与引理6.1矛盾。因此A*算法必然停止。6.2.3最佳图搜索算法A*其次证明A*算法停止时已找到一条最优的解路径。A*只有在OPEN表为空或者当前扩展的结点为目标结点时才停止。前一个停止条件在不存在目标结点的搜索空间上发生。而本定理要求搜索空间存在目标结点。因此A*必然在扩展一个目标结点时停止。那么，现在只需说明该目标结点是否是最优的。假设A*算法在停止时扩展的目标结点不是最优的，并记此结点为ng2，而最优目标结点为ng1。易知，在此情况下，f*（ng2）>f*（S0），f*（ng1）=f*（S0）。此假设与引理6.1矛盾。因为引理6.1说明：在A*选择ng2之前，OPEN表上必然存在一个结点n*满足f*（n*）≤f*（S0）。由于f*（n*）≤f*（S0），所以A*在考察ng2和n*时必然选择n*而不是ng2，这与假设选择了ng2相矛盾。至此，定理6.1得证。6.3与或图的启发式搜索启发式搜索可以应用的第二个问题是AND-OR图（与或图）的反向推理问题。AND-OR图的反向推理过程可以表示一个问题归约过程。问题规约的基本思想是：在问题求解过程中，将一个大的问题变换成若干个子问题，再将这些子问题分解成更小的子问题，这样继续分解，直到所有的子问题都能被直接求解为止。问题规划方法之所以可行，是因为根据全部子问题的解就能构造出原问题的解。一般地，待求解的问题称为初始问题，能直接求解的问题称为本原问题。问题归约是不同于状态空间法的另一种问题描述和求解的方法。6.3.1问题归约表示以一个自动推理的例子介绍基于问题归约思想求解问题的过程。例6.1给定如下一组命题公式，给出证明命题r成立的证明序列。解：该问题的解是这样一个证明序列：p，t，p⋀t→q，p→m，s→q，q→r。那么，如何得到这个解?可以采用正向的思考，也可以采用反向的思考。正向思考过程通常如下：根据p和p→m可以得出m成立，根据p，t和p⋀t→q得出q成立，根据q成立和q→r得出r成立。基于此过程，构造出证明序列。反向思考过程通常如下：若要证明r成立，就必须利用能推导出r的蕴涵式q→r；进而要证明q成立，可以利用蕴涵式s→q或者p⋀t→q；如果利用蕴涵式s→q，则要证明s成立，但给出的公式集合中不含s，而且也不含后件为s的蕴涵式，所以此条路径不通；如果利用p⋀t→q证明q成立，则要求p和t都成立，由于p和t都在给定的公式集中存在，所以无须继续证明。至此，能够构造出证明序列。6.3.1问题归约表示在此例中，反向思考的过程就是问题归约的思想。例如，将“证明r成立”的问题通过蕴涵式q→r转化为“证明q成立”的问题；将“证明q成立”的问题通过p⋀t→q转化为“证明p成立”与“证明t成立”两个问题；“证明p成立”的问题由于p在命题集合中存在而能被立即解决；同理，“证明t成立”的问题也能被立即解决。正向思考和反向思考在效率上存在差别，但取决于具体的问题，没有绝对的优劣之分。例如，对于给定{p，p→q，p→r，p→s}，要证明s成立，则应用反向思考的效率高；对于给定{p，t→s，r→s，p→s}，要证明s成立，则应用正向思考的效率高。6.3.1问题归约表示基于问题归约思想求解问题的基本概念和方法。从问题归约的角度，一个问题表示为三元组：（S0，O，P），其中：S0是初始问题，即要求解的问题：P是本原问题集，其中的每一个问题是不用证明的，自然成立的，如公理、已知事实等，或已证明过的问题；O是操作算子集，它是一组变换规则，通过一个操作算子把一个问题化成若干个子问题。这样，基于问题归约的求解方法就是由初始问题出发，运用操作算子生成一些子问题，对子问题再运用操作算子生成子问题的子问题，如此进行到产生的问题均为本原问题为止，则初始问题得解。6.3.2与或图及解图将例6.1的问题被表示为右图，其中，方块结点表示问题，结点之间的有向边表示源结点对应的问题可分解为目标结点对应的问题。在该图中，最特殊的结点是q，另一个最特殊的是从q指向p和的有向边。q指向p和的两条有向边被一个圆弧连接，用于表示q被分解（归约）为q与t：只有当p和t对应的问题都被解决时，q才能被解决。将右图抽象为一种称为超图的结构，用二元组（N，H）表示：N为结点的有穷集合；H为超边的集合；一个超边表示为<s，D>，其中s∈N，称s为该超边的源结点，D⊆N，称D为该超边的目的结点集。超边也称为“k连接符”，其中k=|D|。问题归约的图形化表示（N1，H1），N1={r，q，p，t，m}，H={<r，{q}>，<q，{p，t}>，<q，{m}>}超图表示6.3.2与或图及解图从问题归约的角度看，一个问题可以用超图表示其中所有的问题以及问题的分解方法。此外，为了表示本原问题集合、初始问题，需要再增加两个元组。我们称此类图为与或图（AND-OR图），它的四元组表示为（N，n0，H，T），其中：N是结点集合，其中每个结点对应一个唯一的问题。n∈N，对应于初始问题。H是超边的集合，其中每个超边<s，D>表示结点s对应的问题的一个可行的分解方法；若|D|=1，则该超边称为“或弧”，同时称D中结点为s的“或子结点”（OR-node），也称它为s的“或后继”（OR-descendents）；若|D|>1，则该超边称为“与弧”，同时称D中结点为s的“与子结点”（AND-node），也称它们为s的“与后继”（AND-descendents）。T是N的子集，其中每个结点对应的问题都为本原问题，T中的结点也称为叶结点6.3.2与或图及解图与或图（N，n0，H，T）的每个以n0为根结点的子图可以表示一种对原始问题逐步分解的过程。下图（a）和图（b）分别是问题归约表示图中的两个不同的子图，其中图（a）所表示的分解过程能够解决原始问题，称这样的图为与或图的解图，而图（b）所表示的分解过程不能解决原始问题。如果能设计一种算法，它能从一个与或图中找出性质如图（a）的解图，则该算法就找到了解决原始问题的一个分解过程。与或图的子图6.3.2与或图及解图可解结点（SolvedNodes）和不可解结点（UnsolvableNodes）的概念假定AND-OR图的子图中每个结点至多有一个k连接符，其中的一个可解结点递归地定义如下：（1）叶结点是可解结点。（2）一个结点是可解的，当且仅当以它为源结点的某一条k连接符可解。（3）一个k连接符可解，当且仅当该连接符的每个目的结点都可解。将不是叶结点的结点简称为非叶结点，并递归定义不可解结点如下：（1）无后继的非叶结点是不可解的。（2）一个结点是不可解的，当且仅当以它为源结点的所有k连接符都不可解。（3）一个k连接符是不可解的，当且仅当该连接符存在一个不可解的目的结点。能导致初始结点可解的那些可解结点及相关的超边组成的子图称为该AND-OR图的解图。6.3.2与或图及解图一个归约问题的AND-OR图可能有多个解图，那么，其中哪个解图更优?为了评价解图的优劣，根据归约问题为每个本原问题赋予相应的权重，为每个操作算子赋予相应的权重，由这些权重来表示相应的费用。父结点的费用定义为相应的操作算子的费用与子节点费用之和。一个解图的费用定义为该图中初始结点的费用。计算一个归约问题的最优解的问题对应于计算该问题的AND-OR图的一个费用最小的解图的问题。称具有最小费用的解图为最优解图。假设任一结点n到目标集Sg的费用估计为h（n）。结点n的费用按下面的方法计算（1）如果n∈Sg，则h（n）=0，否则h（n）为以n为源结点的k连接符的费用的最小值。（2）一个k连接符<n，{n1，n2，…，nm}>的费用为h（n）=m+h（n1）+h（n2）+h（nm）。6.3.3AO*算法为了在AND-OR图中找到最优解图，需要一个类似于A*的算法，Nilsson因而提出了AO*算法，它和A*算法是不同的，主要有以下两个区别。区别1：AO*算法能考虑“与弧”的费用，而A*算法不能。与或图6.3.3AO*算法为了保证搜索到一个最优解图，在搜索AND-OR图时，每步需做3件事：（1）遍历图，从初始结点开始，沿当前最优路径，记录在此路径上未扩展的结点集。（2）从这些未扩展的结点中选择一个进行扩展。将其后继结点加入图中，计算每后继结点的f值（只需计算h，不计算g）。（3）改变最新扩展结点的f估值，以反映由其后继结点提供的新信息。将这种改变往上回传至整个图。在往后回传时，每到一个结点就判断其后继路径中哪一条最有希望并将它标记为目前最优路径的一部分。这样可能引起目前最短路径的变动。这种图的往上回传以修正费用估计的工作在A*算法中是不必要的，因为A*只需考察未扩展结点。但现在必须考察已扩展结点以便挑选目前的最优路径。6.3.3AO*算法第一步：A是唯一结点，因此它在目前最优路径的末端。第二步：扩展A后得结点B、C和D，因为B和C的费用为9，得出A的费用为6，所以把到D的路径标记为出自A的最有希望的路径（被标记的路径在图中用箭头指出）第三步：沿着最优希望的路径扩展D，得到E和F的与弧，得出D的费用估计为10，故将D的f值修改为10。往上退一层发现，A到与结点集{B，C}的耗费为9，所以，从A到{B，C}是当前最有希望的路径，因此，对<A，{B，C}>进行标记。6.3.3AO*算法第四步：扩展结点B，得结点G、H，且它们的费用分别为5、7。往上传其f值后，B的f值改为6（因为G的弧最佳）。往上一层继续回传，A到结点集{B，C}的费用更新为12，即（6+4+2）。因此，D的路径再次成为更好的路径，所以取消<A，{B，C}>的标记，再次标记<A，{D}>。A的费用为：f（A）=MIN{12，4+4+2+1）=116.3.3AO*算法区别2：如果有些路径通往的结点是其他路径上的“与”结点扩展出来的结点，那么不能像“或”结点那样只考虑从结点到结点的个别路径，有时候路径长一些可能会更好。下图中结点已按生成它们的顺序给了序号。现假定下一步要扩展结点10，其后继结点之一为结点5，扩展后的结果如图（b）所示。到结点5的新路径比通过3到5的先前路径长。但因为若要经由结点3而通向结点5，还必须解决结点4，而结点4是不可解结点，所以经由结点10而通向结点5的路径更好。长路径和短路径6.3.3AO*算法AO*算法的主要思想：在A*算法中用了两张表：OPEN表和CLOSED表。AO*算法只用一个结构G，它表达了至今已明显生成的部分搜索图。图中每一结点向下指向其直接后继结点，向上指向其直接前趋结点。同图中每一结点有关的还有h值它估计了从该结点至一组可解结点那条路径的费用。AO*算法还使用一个称为FUTILITY的值。若一解的估计费用大于FUTILITY的解，则放弃搜索该路径FUTILITY相当于一个阈值，它的选择应使得大于费用FUTILITY的任一解即使存在也因为代价大而无法使用。6.3.3AO*算法ProcedureAO*Begin设G仅由代表初始问题的结点n0构成，计算h（n0）。Repeat（1）沿着从n开始的带标记的k连接符，如果存在，挑选在此路径上但未扩展的一个结点进行扩展，记该结点为n。（2）生成n的后继结点。If

n没有后继结点，Then令h（n）=FUTILITY，标记n为不可解结点；ElseBegin记n的后继结点集为Suc。For每个不是结点n祖先的后继结点s∈Suc，DoBegin①把s加到图G中。②若s是一个叶结点，则标记s为SOLVED，并令h（s）=0。③若s是非叶结点，则计算它的h值。EndEndAO*算法流程：6.3.3AO*算法（3）将最新发现的信息向上回传。具体做法为：设C为一结点集，C包括已经做了SLOVED标记或者h值已经发生了改变的结点。将初始化为{n}。（4）Repeat①从C中挑选一个结点，该结点在G中的子孙均不在C中出现（即，保证对于每一正在处理的结点，是在处理其任一祖先之前来处理该结点）称此结点为c并令C=C-{c}。②计算以c为源结点的每条k连接符的费用，其费用等于其目的结点的h值之和加上该连接符自身的费用。从刚刚计算过的始于c的所有k连接符的费用中选出极小费用作为c的新h值。③把在②中计算出来的带极小费用的k连接符标记为始于c的最佳路径④If

c的带标记的连接符是SOLVED，Then

把c标记为SOLVED。⑤If

c已标记为SOLVED，或c的费用刚才已经改变，Then应把其新状态往回传。因此，把c的所有祖先结点加到C中。Unti1

C为空；Unti1n0标为SOLVED（求解成功），或n0的h值大于FUTILITY（无解）。EndAO*算法流程（接上表）：6.3.3AO*算法下图为AO*算法示例：开始时，在算法的步骤（3）处可知：C={A}，在步骤（4）的①步可知：c=A。由于有A到{B，C}的k连接符，根据该连接符知c的费用为：2+h（B）+h（C）=9；另外有A到{D}的k连接符，根据该连接符知c的费用为：1+h（D）=6，所以A的较好费用为6，将<A，{D}>作上标记。这样，在下一次循环的步骤（1）处，可得n=D，扩展D后得：Suc={E，F}，执行之后的步骤得到D的新费用为10，向上回传，由于连接符<A，{D}>的新费用大于连接符<A，{B，C}>的费用，所以A的费用更新为连接符<A，{B，C}>的费用（即9），此外，撤销对<A，{D}>的标记，同时对<A，{B，C}>做标记。6.4博弈树的搜索博弈一向被认为是富有挑战性的智力活动，如下棋、打牌、作战和游戏等。二人博弈、二人零和、全信息、非偶然博弈，博弈双方的利益是完全对立的（1）对垒的双方MAX和MIN轮流采取行动，博的结果只能有3种情况：MAX胜、MIN败；MAX败，MIN胜；和局。如果记“胜利”为+1分，“失败”为-1分，“平局”为0分，则双方在博弈结束时的总分总是为“零”，称此类博弈为“零和”。（2）“全信息”是指对垒过程中，任何一方都了解当前的格局和过去的历史。（3）“非偶然”是指任何一方都根据当前的实际情况采取行动，选择对自己最有利而对对方最不利的对策，不存在“碰运气”如掷骰子）的偶然因素。具有以上特点的博弈游戏有一字棋、象棋和围棋等。围棋的博弈树6.4.1博弈树假设有7枚钱币，任一选手只能将已分好的一堆钱币分成两堆个数不等的钱币，两位选手轮流进行，直到每一堆都只有一个或两个钱币，不能再分为止，哪个选手遇到不能再分的情况，则为输（取胜的策略用双线箭头表示）。分钱币的博弈无论MIN开始时怎么走法，MAX总可以获胜6.4.1博弈树如果站在某一方（如MAX方，即MAX要取胜），把上述博弈过程用图表示出来，则得到的是一棵“与”关系和“或”关系组成的树。当这颗树描述的是博弈过程的时候，我们称其称为博弈树，它有如下特点：（1）博弈的初始格局是初始结点。（2）在博弈树中，“或”结点和“与”结点是逐层交替出现的。自己一方扩展的结点之间是“或”关系，对方扩展的结点之间是“与”关系。双方轮流地扩展结点。（3）所有自己一方获胜的终局都是本原问题，相应的结点是可解结点；所有使对方获胜的终局都认为是不可解结点。6.4.2极小-极大搜索过程在博弈问题中，每一个格局可供选择的行动方案都有很多，因此会生成十分庞大的博弈树，如果试图通过直到终局的与或树搜索而得到最好的一步棋是不可能的最常使用的分析方法是极大极小分析法。其基本思想或算法如下：（1）设博弈的双方中一方为MAX，另一方为MIN。设计算法为其中的一方（例如MAX）寻找一个最优行动方案。（2）为了找到当前的最优行动方案，需要对各个可能的方案所产生的后果进行比较具体地说，就是要考虑每一方案实施后对方可能采取的所有行动，并计算可能的得分。（3）为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端结点的得分。此时估算出来的得分称为静态估值。6.4.2极小-极大搜索过程在博弈问题中，每一个格局可供选择的行动方案都有很多，因此会生成十分庞大的博弈树，如果试图通过直到终局的与或树搜索而得到最好的一步棋是不可能的最常使用的分析方法是极大极小分析法。其基本思想或算法如下：（4）当末端结点的估值计算出来后，再推算出父结点的得分，推算的方法是：对“或结点，选其子结点中一个最大的得分作为父结点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”结点，选其子结点中一个最小的得分作为父结点的得分，这是为了立足于最坏的情况。这样计算出的父结点的得分称为倒推值。（5）如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。6.4.2极小-极大搜索过程//MinMaxSearch.

functionminimax(node,depth)//指定当前节点和搜索深度//如果能得到确定的结果或者深度为零，使用评估函数返回局面得分ifnodeisaterminalnodeordepth=0returntheheuristicvalueofnode//如果轮到对手走棋，是极小节点，选择一个得分最小的走法iftheadversaryistoplayatnodeletα:=+∞foreachchildofnode

α:=min(α,minimax(child,depth-1))//如果轮到我们走棋，是极大节点，选择一个得分最大的走法else{wearetoplayatnode}letα:=-∞foreachchildofnode

α:=max(α,minimax(child,depth-1))returnα;极小-极大搜索算法流程：6.4.2极小-极大搜索过程试图利用完整的博弈树来进行极大极小分析是困难的，因此只生成一定深度的博弈树，然后进行极大极小分析，找出当前最好的行动方案。在此之后，再在已选定的分枝上扩展一定深度，再选最好的行动方案。如此进行下去，直到取得胜败的结果为止。4层的博弈树，用□表示MAX，用○表示MIN，结点上的数字表示它对应的评价函数的值。在MIN处用圆弧连接，用0表示其子结点取估值最小的格局。6.4.2极小-极大搜索过程（1）若格局p对任何一方都不是获胜的，则e（p）=（所有空格都放上MAX的棋子之后三子成一线的总数）-（所有空格都放上MIN的棋子后三子成一线的总数）一字棋博弈的极大极小过程6.4.2极小-极大搜索过程（2）若p是MAX获胜，则e（p）=+∞（3）若p是MIN获胜，则e（p）=-∞因此，若p为就有e（p）=6-4=2，其中×表示MAX方，○表示MIN方。在生成后继结点时，可以利用棋盘的对称性，省略了从对称上看是相同的格局。MAX走了箭头指向的一步，例如MIN将棋子走在×的上方，得到下面MAX就从这个格局出发选择一步，直到某方取胜为止。6.4.3

-

搜索过程

-

过程就是把生成后继和倒推值估计结合起来，及时剪掉一些无用分枝，以此来提高算法的效率。当某个MIN结点的值不大于它的前辈的MAX结点（不一定是父结点）的

值时，则MIN结点就可以停止向下搜索。当某个结点的

值大于等于它的前辈MIN结点的

值时，则该MAX结点就可以停止向下搜索。一字棋博弈的

-

过程A处的倒推值等于-1，将此下界叫做MAX结点的

值，即

≥-1B处的倒推值小于等于-1，此为MIN结点

值的上界，即B处

≤-16.4.3

-

搜索过程

-

过程首先使搜索树的某一部分达到最大深度，这时计算出某些MAX结点的

值，或者是某些MIN结点的

值。随着搜索的继续，不断修改个别结点的

或

值。对任一结点，当其某一后继结点的最终值给定时，就可以确定该结点的

或

值。当该结点的其他后继结点的最终值给定时，就可以对该结点的

或

值进行修正。

、

值修改有如下规律：（1）MAX结点的

值永不下降；（2）MIN结点的

值永不增加。因此可以利用上述规律进行剪枝，一般可以停止对某个结点搜索6.4.3

-

搜索过程剪枝的规则表述如下：（1）若任何MIN结点的

值小于或等于任何它的前辈MAX结点的α值，则可停止该MIN结点之下的搜索，这个MIN结点的最终倒推值即为它已得到的值。该值与真正的极大极小值的搜索结果的倒推值可能不相同，但是对开始结点而言，倒推值是相同的，使用它选择的走步也是相同的。（2）若任何MAX结点的

值大于或等于它的MIN先辈结点的

值，则可以停止该MAX结点之下的搜索，这个MAX结点处的倒推值即为它已得到的α值。当满足规则（1）而减少了搜索时，我们说进行了

剪枝；而当满足规则（2）而减少了搜索时，我们说进行了

剪枝。保存

和

值，并且一旦可能就进行剪枝的整个过程通常称为α-

过程，当初始结点的全体后继结点的最终倒推值全部给出时，上述过程便结束。6.4.3

-

搜索过程

-

过程示例结点A、B、C、D处都进行了剪枝，剪枝处用两横杠标出。凡剪去的部分，搜索时是不生成的。

-

剪枝6.4.3

-

搜索过程

第七章绪论7.1概述7.2归纳学习7.3分析学习7.4无监督学习7.5强化学习7.1机器学习概述

机器学习是人工智能的核心研究课题之一，通过解决机器的知识拥有量从而使机器具有智能的根本途径。任何人工智能系统特别是专家系统，在它拥有功能较强的自动化知识获取能力之前，都不会成为名副其实的强有力的智能系统。传统的手工式知识获取方法耗资耗时，已成为建造专家系统和其他知识系统的“瓶颈”问题。

机器学习已成为知识获取技术发展的主要方向。机器学习的应用领域极为广泛，涉及自然语言处理、计算机视觉、医疗诊断、金融预测等多个关键领域。7.1.1机器学习的定义什么是机器学习？从字面上来理解:机器学习是研究如何使用机器来模拟人类学习活动的一门学科。从人工智能的角度：机器学习是一门研究使用计算机获取新知识和技能，并能够识别现有知识的科学。7.1.2机器学习的基本结构机器学习系统:环境:系统外部信息的源泉，涵盖了系统的工作对象及其所处的外界条件。学习单元:处理环境所提供的信息，其作用类似于各种学习算法。知识库:专为存储学习环节所得知识的场所。执行单元:致力于解决系统所面临的现实问题，它运用知识库中的知识来解决各种问题，如问题求解、自然语言理解和定理证明等。7.1.3机器学习的基本策略每个机器学习系统的学习单元都可以包含一种或者多种学习策略，用来解决特定领域的特定问题。不存在一种普适的、可以解决任何问题的学习算法。根据学习方法：演绎学习、归纳学习、分析学习(含类比学习、解释学习)有无指导来分：有监督学习（或有导师学习）、无监督学习（或无导师学习）和强化学习（或增强学习）以上几种分类方法是相互联系和相互渗透的！7.2归纳学习归纳推理：是从特殊到一般的推理，它是一种“从事实建立理论的过程”，从主观上讲是一种主观地不充分置信的推理。归纳学习：是应用归纳推理进行学习的一种方法。根据归纳学习有无教师指导，可把它分为示例学习和观察发现学习。前者属于监督学习，后者属于无监督学习。7.2.1归纳学习的模式和规则1.归纳学习的一般模式给定：①观察陈述（事实）F，用于表达特定对象、状态和过程等的相关知识；②假定的初始归纳断言（可能为空）；③背景知识，用于定义有关观察陈述、候选归纳断言以及任何相关问题领域知识、假设和约束，其中包括能够刻画所求归纳断言的性质的优先准则。求：归纳断言（假设）H，能重言蕴涵或弱蕴涵观察陈述，并满足背景知识。7.2.1归纳学习的模式和规则这里，从H推导到F是演绎推理，因此是保真的；而从F推导出H是归纳推理，因此不是保真的，而是保假的，归纳学习系统的模型如图所示。实验规划过程通过对实例空间的搜索完成实例选择，并将这些选中的活跃实例提交给解释过程。解释过程对实例加以适当转换，把活跃实例变换为规则空间中的特定概念，以引导规则空间的搜索。7.2.1归纳学习的模式和规则2.归纳学习的规则

在归纳推理过程中，需要引用一些归纳规则。这些规则分为选择性概括规则和构造性概括规则两类。令D1和D2，分别为归纳前后的知识描述，则归纳是D1

D2。选择性概括：如果D2中所有描述基本单元（如谓词子句的谓词）都是D1中的，只是对D1中基本单元有所取舍，或改变连接关系。构造性概括：如果D2中有新的描述基本单元（如反映D1各单元间的某种关系的新单元）。这两种概括规则的主要区别在于，构造性概括能够构造新的描述符或属性。7.2.2归纳学习方法1.示例学习

示例学习（LearningfromExamples）：又称实例学习，是一种通过环境中的多个与某一概念相关的示例，经归纳推理得出一般性概念的学习方法。

在这种学习方式中，外部环境（教师）提供一组示例，包括正例和反例，它们都是一种特殊的知识，每个示例表达了仅适用于该例子的知识。

示例学习的目标是从这些特殊知识中归纳出适用于更广泛范围的一般性知识，以覆盖所有的正例并排除所有反例。7.2.2归纳学习方法通过示例学习，可以从病例中归纳产生如下的诊断规则：血沉=正常

(听诊=干鸣音

水泡音)→诊断=肺炎血沉=快→诊断=肺结核7.2.2归纳学习方法2.观察发现学习

观察发现学习（LearningfromObservationandDiscovery）：又称为描述性概括，其目标是确定一个定律或理论的一般性描述，刻画观察集，指定某类对象的性质。观察发现学习可分为概念聚类与机器发现两种。概念聚类：对事例进行聚类，形成概念描述。机器发现：发现规律，产生定律或规则。7.2.3ID3决策树归纳算法

决策树学习是离散函数的一种树形表示，表达能力强，可以表示任意的离散函数，是一种重要的归纳学习方法。决策树中有决策节点和状态节点两种节点，即决策节点和状态节点。昆兰在1979年提出的ID3算法是一种典型的决策树算法，是通用的规则归纳算法。决策节点：由决策节点可引出若干树枝，每个树枝代表一个决策方案，每个方案树枝连接到一个新的节点，它既可以是一个新的决策节点，也可以是一个状态节点；对于分类问题而言，决策节点表示待分类的对象属性，每一个树枝表示它的一个可能取值状态节点：状态节点对应着叶节点，每个状态节点表示一个具体的最终状态；对于分类问题而言，状态节点表示分类结果。7.2.3ID3决策树归纳算法ID3（Examples，Target_attribute，Attributes），其中Examples即训练样例集，Target_attribute是这棵树要预测的目标属性，Attributes是除目标属性外供学习的决策树要测试的属性列表。1）创建树的Root（根）结点。2）如果Examples都为正，那么返回label=+的单结点树Root。3）如果Examples都为反，那么返回label=-的单结点树Root。4）如果Examples为空，那么返回单结点树Root，label=Examples中最普遍的Target_attribute值。5）否则：①A←Attributes中分类Examples能力最好的属性，一般认为具有最高信息增益(informationgain)的属性是最好的属性。②Root的决策属性←A。③对于A的每个可能值vi：a．在Root下加一个新的分支对应测试A=vi。b．令Examples（vi）为Examples中满足A属性值为vi的子集。c．如果Examples（vi）为空：在这个新分支下加一个叶结点，结点的label=Examples中最普遍的Target_attribute值；否则在这个新分支下加一个子树ID3(Examples(vi)，Target_attribute，Attributes-{A})。6）结束。7）返回Root。7.2.3ID3决策树归纳算法思考：如何选择具有最高信息增益即分类能力最好的属性?昆兰建议选取获得信息量最大的属性作为扩展属性，这一启发式规则又称最小熵原理。因为获得信息量最大，即信息增益Gain最大，等价于使其不确定性最小，即使得熵最小，即条件熵H(S|Ai)为最小。因此也可以以条件熵H(S|Ai)为最小作为选择属性的重要标准。H(S|Ai)越小，说明Ai引人的信息越多，系统熵下降得越快。7.3分析学习归纳学习方法需要通过在大量训练样例中寻找经验化的规律来形成一般假设。然而，若训练数据不足时它会失败，无法达到一定的泛化精度。分析学习则使用先验知识扩大训练样例提供的信息，推导一般假设，降低了对数据量的要求。本节将探讨分析学习中的类比学习与基于解释的学习。7.3.1类比推理和类比学习1.类比推理类比推理是从个别事例到个别事例的推理方法。它是根据认识的新情况（目标）和已知情况（源）在某些方面的相似性，推断出其他相关方面的推理形式。其一般模式为：

已知：S1，T1 （源S1和目标T2）（源和目标相似）（源S1和源S2相关）S2 （已知源S2）

7.3.1类比推理和类比学习2.类比学习类比学习的一般原理基于类比推理的学习过程分为两步，首先归纳找出源域和目标域的公共性质，然后演绎地推理出从源域到目标域映射，得出目标域的新性质。不难看出，类比学习过程既有归纳过程，又有演绎过程，所以类比学习是演绎学习和归纳学习的组合，是由一个系统已有某领域中类似的知识，来推测另一个领域里相关知识的过程。7.3.1类比推理和类比学习2.类比学习类比学习的表示假设对象的知识是框架集来表示的，则类比学习可描述为把一个称为源框架的槽值传递给另一个称为目标框架的槽中，传递过程分为两步。1）利用源框架产生若干候选槽，并将这些槽值送到目标框架中去。2）利用目标框架中现有的信息来筛选上一步提取出来的相似性。7.3.1类比推理和类比学习2.类比学习例

考虑比尔与消防车之间的相似关系，关于比尔和消防车的框架为：比尔是一个（ISA）人

性别男

活动级

音量

进取心中等消防车是一个（ISA）车辆

颜色红

活动级快

音量极高

燃料效率中等

梯高异或（长、短）7.3.1类比推理和类比学习2.类比学习基于启发式规则求解，得到比尔的框架为：比尔是一个（ISA）人

性别男

活动级快

音量极高

进取心中等可以看出类比学习过程也依赖于知识表示和推理技术，在类比学习过程中合理地使用这些技术，能够形成一种合理的、有效的学习方法。7.3.2基于解释的学习基于解释的学习力图反映人工智能领域里基于知识的研究和发展趋势，将机器学习从归纳学习方法向分析学习方法的方向发展。

基于解释的学习的一般框架解释学习一般包括下列3个步骤：1）利用基于解释的方法对训练实例进行分析与解释，以说明它是目标概念的实例。2）对实例的结构进行概括性解释,建立该训练实例的一个解释结构以满足所学概念的定义；解释结构的各个叶结点应符合可操作性准则,且使这种解释比最初的例子适用于更大的一类例子。3）从解释结构中识别出训练实例的特性,并从中得到更大一类例子的概括性描述，获取一般控制知识。7.3.2基于解释的学习

基于解释的学习过程基于解释的学习过程可分为如下两个步骤：1）分析阶段：根据领域知识生成一棵证明树，解释为什么该实例是目标概念的一个实例。2）基于解释的概括阶段：通过将实例证明树中的常量用变量进行替换，形成一棵基于解释的抽象树（简称EBG树），得到目标概念的一个充分条件。7.3.2基于解释的学习例

下面以学习概念cup（杯子）为例说明EBG的学习过程。1）目标概念：cup2）高级描述：cup（z）3）领域知识：stable(x)

liftable(x)

drinkfrom(x)

cup(x)has(x,y)

concavity(y)

upward-pointing(y)

drinkfrom(x)bottom(x,y)

flat(y)

stable(x)light-weight(x)

graspable(x)

liftable(x)small(x)

madefrom(plastic)

light-weight(x)has(x,y)

handle(y)

graspable(x)（中文解释：stable稳定的；liftable便于拿起；drinkfrom可用来喝饮料；concavity凹空；light-weight轻质；graspable可握住；upward-pointing向上指示；bottom底；flat平坦的；plastic塑胶。）4）训练例子：Small(obj),madetrom(obj,plastic),has(obj,part1),handle(part2),has(obj,part2),concavity(part2),upward-pointing(part),bottom(obj,b),flat(b)。5）可操作性准则：目标概念必须以系统可识别的物理特征描述。7.3.2基于解释的学习利用以上规则和事实，以cup(obj)为目标作逆向推理，可以构造如图（a）所示的解释结构，其叶结点满足可操作性准则。对解释进行概括，变常量为变量，便得到概括后的解释结构。将此结构中的所有叶结点作合取，就得到目标概念所应满足的一般性的充分条件，以产生式规则形式表示为图（b）（a）解释结构（b）形成规则7.4无监督学习

无监督学习（UnsupervisedLearning）：是指在学习之前没有（不知道）关于输入数据的标准输出，对学习结果的判定由学习模型自身设定的条件决定。无监督学习的学习过程一般是一个自组织的过程，学习模型不需要先验知识。无监督学习可用于解决聚类问题，其典型方法有K均值聚类、主成分分析算法等。7.4.1聚类算法

在聚类算法中，训练样本的标记信息是未知的，将样本集分为若干互不相交的子集，即样本簇。聚类算法的目标：同一簇：样本尽可能彼此相似，即具有较高的类内相似度(Intra-clusterSimilarity)。不同簇：样本尽可能不同，即簇间的相似度低。K-均值算法是聚类方法的一种，期目标是使得聚类簇内的平方误差最小化。7.4.1聚类算法K-均值算法特性：对参数的选择比较敏感，不同的初始位置或者类别数量的选择往往会导致完全不同的结果。

（a）K=2：颜色

（b）K=2：形状

（c）K=2：大小

（a）K=4：颜色、形状

（b）K=4：形状、尺寸

（c）K=4：尺寸、颜色7.4.2主成分分析

主成分分析（PrincipleComponentsAnalysis，PCA）：是一种特征降维的方法，即通过分析找到数据特征的主要成分，使用这些主要成分来代替原始数据。主成分分析要求：降维后的结果要保持原始数据的原有结构。7.4.2主成分分析主成分分析的目的是求取一个d×l的映射矩阵W。给定一个样本集X，可将X从d维空间如下映射到l维空间：(xi)1×d(W)d×l。将所有降维后的数据用Y表示，有Y=XW，其中Y∈Rd×l是降维后的结果，X∈Rn×d是原始数据，W∈Rd×l是映射矩阵。

降维后n个l维样本数据Y的方差为:式中，tr表示矩阵的迹（Trace），即一个方阵主对角线（从左上方到右下方的对角线）上各个元素的总和。降维前n个d维样本数据X的协方差矩阵记为：7.4.2主成分分析主成分析的优化求解目标函数为：该优化求解目标需要满足如下约束条件：这是带约束的最优化问题求解，可通过拉格朗日乘子法转化为无约束的最优化问题，即：式中，λi（1≤i≤l）为拉格朗日乘子，wi为矩阵W第i列。对上述拉格朗日函数中的变量wi求偏导并令导数为零，有Σwi=λiwi上式表明：每一个wi，均是n个d维样本数据X的协方差矩阵Σ的特征向量，λi是这个特征向量所对应的特征值。为了使方差最大，可以求出协方差矩阵Σ的特征向量和特征根，然后取前l个最大特征根所对应的特征向量组成映射矩阵W即可。7.4.2主成分分析主成分分析算法伪代码：注意:每个特征向量wi与原始数据xi的维数是一样的，均为d。7.5强化学习

强化学习是智能体（Agent）在不断与其所处环境交互中进行学习的一种方法。学习信号以奖励形式出现，根据在终止状态所获得的奖惩来改进行动策略，智能体在与环境交互中取得最大化收益。

在这种方法中，智能体通过“尝试与试错”和“探索与利用”等机制在所处状态采取行动，不断与环境交互，直至进入终止状态。这种学习方式既不是从已有数据出发，也不是依赖于已有知识的学习方式。7.5.1强化学习的基本概念学习过程中要使用的若干概念。智能体（Agent）：智能体是强化学习算法的主体，它能够根据经验