人工智能(研究生)2013年试题_标准答案..doc

课程编号：21-081200-108-07 北京理工大学 2013 - 2014学年第一学期 研究生《人工智能》期末试题 班级 学号 姓名 成绩 1. 学习（30分+5分） 下图给出了两类数据，分别如图中和所示。另外，图中两条黑色粗实线分别代表横、纵坐标轴，其交点为原点。 第1题图 现要求对上述数据进行分类。 [10分] 如果采用Decision Tree实现分类，请说明该Decision Tree的非叶节点、叶节点和边分别是什么，并计算以下两个值：(a) 该数据集的Entropy; (b) 当根节点选择根据x的值是否大于0来进行决策时，所对应的Information Gain。 解：1）非叶节点为x与y，叶节点为类别，边为x与y的取值区间； 2）两类样本分别为6个和9个，因此： 3） [10分] 如果采用Na?ve Bayesian Classifier实现分类，并将x，y的取值分别离散化为“大于0”和“小于等于0”两种情况，请给出需要学习的数值及其结果，进而判断当时的分类结果 解：已知样本a = {a1,a2}，其中a1为属性x的值,a2为属性y的值。 类别集合C={黑框，白球} 若给出某一测试用例m，则需计算P(黑框|m)与P(白球|m)，并据此来进行判别，但若要计算这两个概率值，则需要计算各个类条件概率，下面为具体的学习过程。 Step1. 根据给出的训练集，统计各类别以及各类别下各个特征属性的条件概率估计： Step2. 由于各个属性间是独立的，则根据贝叶斯定理有如下推导： 则可推导出样本的类别。 对于样本m = {x0, y=0} 判别其类别的过程如下： 因此，当x0, y=0 则将其判别为白球类别。 [10分] 如果采用Neural Network实现分类，请画出能对上述数据进行分类的网络结构（不含权值），并说明如何根据上述数据学习得到该网络中的权值。 解：采用多层感知器。该神经网络的输入神经元个数为2，分别表示x与y的值，输出神经元个数为1，1表示类别为黑框，0表示白球。隐含层神经元个数为4。则其结构如下： 可利用BP学习算法来进行学习（最小二乘法、权值计算使用梯度下降等）。 （附加题）[5分] 能否使用Clustering技术解决上述分类问题？如能，应怎样解决？ 解：可以采用聚类技术求解。用k-means算法将以上数据聚成两类，获得相应聚类中心。分类时，根据数据到聚类中心的距离来进行判定。 可以用聚类算法。但由于数据是凹型数据，因此，直接用k-means算法无法得到满意，因此，可考试将此数据集映射到高维空间，使其变成凸型数据之后再对其使用类似于k-means的算法进行聚类。另外一种方法则是采用可以处理凹型数据的聚类算法，譬如PCCA（Perron Cluster Cluster Analysis）方法。 2. 搜索（30分+5分） 给定函数：。要求计算该函数的最小值，其中的取值范围为。 [10分] 如果采用Gradient Descent方法求解，请描述其中一次迭代过程。 解：梯度下降法的基本思想为：假设我们要求函数的最小值，首先需要选取一个初始点，然后下一点的产生是沿着梯度直线方向，这里是沿着梯度的反方向（因为是求最小值）。梯度下降法的迭代公式为： , 其中，表示的是梯度的反方向，表示的是在梯度方向上的搜索步长。梯度可以通过对函数求导取得，步长的确定比较麻烦，太大容易发散，太小收敛速度太慢。因此步长的选择需要沉思熟虑。另外，算法迭代的停止条件是梯度向量的幅值接近0即可。 根据以上思想，对以下函数进行最小值求解。 ，其中以及 由于此问题是存在约束条件下的最小值问题，在此条件下无法直接利用梯度下降法对其进行优化，需要将其进行转化，转化无约束条件下进行求解。因此有两种方法解决，一是采用拉格朗日定理对其转化，另一种是加入一个惩罚项，对超出约束条件的点进行惩罚。这里可采用加入惩罚项来解决。 因此，将上述函数转化为以下函数表示： 其中为处罚项。若x1与x2均在此约束范围内惩罚项的值为0，对函数值没有影响。下面是具体的一次迭代过程： 首先，设置初始值为x1 = 0, x2 = 0. 其次，计算梯度向量，对x1与x2求偏导： 然后，计算下一点的值： 由于此值均在约束条件下，所以 此次迭代结束。 [10分] 设计一个求解该问题的Evolutionary Algorithm。 解：/*初始化遗传算法参数*/ const int maxGeneration; //进化代数，即迭代次数 cons