人工智能算法-习题思考题参考答案 胡矿

第1章习题参考答案1.（1）加法操作，（2）乘法操作，（3）比较操作，（4）乘法操作。2.共执行了16次元素比较操作。初始序列为{4,3,12,5,6,7,2,9}，采用插入排序将序列排序为升序序列，按照算法思想：（1）初始时默认{4}有序，3和4比较1次，3比4小插入到4前面，则有序序列变为{3,4}，进行1次比较；（2）插入12，12和4比较1次，12比4小，12插入到4后面，则有序序列变为{3,4,12}，进行1次比较；（3）插入5，5和12比较1次，5比12小；5和4比较1次，5比4大，5插入到4后面，则有序序列变为{3,4,5,12}，进行2次比较；（4）插入6，6和12比较1次，6比12小；6和5比较1次，6比5大，6插入到5后面，则有序序列变为{3,4,5,6,12}，进行2次比较；（5）插入7，7和12比较1次，7比12小；7和6比较1次，7比6大，7插入到6后面，则有序序列变为{3,4,5,6,7,12}，进行2次比较；（6）插入2，2比序列前面的所有元素都小，分别和每个元素比较1次，最后插入到3前面，则有序序列变为{2,3,4,5,6,7,12}，进行6次比较；（7）插入9，9和12比较1次，9比12小；9和7比较1次，9比7大，9插入到7后面，则有序序列变为{2,3,4,5,6,7,9,12}，进行2次比较。综上，共比较16次。3.54.（1）fn=O(g(n))，由于（2）fn=O(g(n))，由于（3）gn=O(f(n))，由于（4）gn=O(f(n))，由于5.证明：令Fn=Ofn，Gn=Ogn。根据O的定义，存在正常数c1和非负整数n1令c3=c1c2，n3=max{nF因此O证毕。6.（1）元素比较操作最少执行n-1次，当原列表为升序排列时达到该（2）元素比较操作最多执行n(n-1)2次，当原列表为降序排列时达到该（3）元素赋值操作最少执行0次，当原列表为升序排列时达到该最小值。（4）元素赋值操作最多执行3n(n-1)2次，当原列表为降序排列时达到该（5）O(n2)7.（1）使用蛮力法，遍历所有元素找出最大值，时间复杂度为O(n)。算法：BruteSearch//蛮力法输入：查找列表A输出：A中的最大值步骤：1.max←A[1]2.Fori=2TonDo3.IfAi>m4.max5.EndIf6.EndFor7.Returnmax（2）使用算法2.1中的递归合并排序算法对列表A进行非降序排序，排序后列表A的最后一个元素即为最大值，时间复杂度为Ω(n8.（1）为了方便表示，用M(n)表示乘法运算次数，那么M(n)需满足M采用迭代法可得到M==不难看出M=M（2）为了方便的表示，用S(n)表示加减运算次数，不包括n减少时所需的减法运算，那么S(n)需满足S采用迭代法可得到S==因此S=S9.（1）由原式可得TT则Tn-152是以3为公比的等比数列，首项为T1（2）由原式可得TTn-1TT上述式子累加可得Tn-T(1)=n(n-1)2

第2章习题参考答案1.每趟执行后列表中的元素如下表：ANEXAMPLEAENXAMPLEAENAXMPLEAAENXMPLEAAENXMPELAAENXELMPAAEELMNPX2.（1）例如（5,19,17,21,11,8,1），算法2.1和算法2.3都需比较11次。（2）例如（2,5,4,9,3,6,8,7,1,0），算法2.1需比较23次，算法2.3需比较19次。（3）例如（8,5,3,9,11,6,4,1,10,7,2），算法2.1需比较26次，算法2.3需比较28次。3.用递归的分治法同时返回列表A[l:r]的最大值和最小值。算法：MaxMin//分治法求最大最小值输入：A[l:r]输出：max,min//A中的最大值和最小值1.Ifr=lThen2.max←A[l];min←A[l]3.returnmax,min4.EndIf5.Ifr=2Then6.max←max⁡{Al,A7.returnmax,min8.EndIf9.mid←(l+r)/210.(max1,min1)←MaxMin(A[l:mid])//处理前半部分11.(max2,min2)←MaxMin(A[mid+1,r])//处理后半部分12.Ifmin2<min1Then13.min←min214.EndIf15.Ifmax2>max1Then16.max←max217.EndIf28.Returnmax,min（1）以元素比较为基本，算法的计算时间记为CnCn=2Cn下面求解C(n)的递推式：C=（2）蛮力法中元素比较次数为2(n-1)，分治法中元素比较次数为3n2-2，分治法4.利用快速排序原理，将一个数组分为三个部分：负元素、未知元素、正元素。A[1]…A[i-1]A[i]…A[j]A[j+1]…A[n]负元素未知元素正元素算法如下：算法：NegBeforePos//列表重排列输入：A[1:n]//待重排列的列表输出：A[1:n]//重排列后的列表步骤：1.i←1;j←n2.WhileijDo3.IfA[i]<0Then4.i←i+15.Else6.swap(A[i],A[j])7.j←j-18.EndIf9.EndWhile10.ReturnA算法需一个长度为n的数组用来存放所有元素，而每次迭代都会从左向右，缩减一位未知元素空间。因此，算法的时间复杂度为O(n)，空间复杂度为O(n)。5.（1）蛮力法：蛮力法求解最近对问题，分别计算每一对点之间的距离，然后找出距离最小的点对，为了避免对同点对计算两次距离，只考虑i<j的那些点对(复杂度分析：算法的基本操作是计算计算两个点间的欧几里得距离。注意到，在求欧几里得距离时，避免了求平方根操作，因此，算法的基本操作为求平方，其执行次数为：T（2）分治法：用分治法求解最近对问题，就是将集合S分成两个子集S1和S2，每个子集中分别有n2个点。然后在每个子集中递归的求其最近点对，在求出每个子集的最近点对后，关键在于如何实现分治法中的合并步骤。如果S中的最近点对都在S1中或都在S2中，则问题很容易解决。如果这2个点分别在S1和S2中，则对于S1中任一点p，S时间复杂性可由如下递推式表示：T合并子问题的解的时间fn=O1T

第3章习题参考答案1.基本思路：直接使用深度优先（DFS）算法以及广度优先算法即可得到给定图的一个连通分量。（1）使用DFS求连通分量算法：DFS//深度优先算法输入：G=<V,E>输出：G//图G的一个连通分量步骤：1.G←2.visit(v)//遍历初始顶点3.Initialize(S)//将栈S初始化为空4.Push(S,v)//初始顶点入栈5.WhileS非空Do6.x←Pop7.G←8.For每一个与x邻接的点wDo9.Ifw未被遍历过Then10.visit(w)11.Push(S,w)//将顶点入栈12.EndIf13.EndFor14.EndWhile15.ReturnG（2）使用BFS求连通分量算法：BFS//广度优先算法输入：G=<V,E>输出：G//图G的一个连通分量步骤：1.G←2.visit(v)//遍历初始顶点3.Initialize(Q)//初始化队列4.Enqueue(Q,v)//初始顶点入队5.WhileQ非空Do6.x←Dequeue(Q)7.G←8.For每一个与已x邻接的点wDo9.Ifw未被遍历过Then10.visit(w)11.Enqueue(Q,w)12.EndIf13.EndFor14.EndWhile15.ReturnG2.参考如下极端情况，其中一个顶点出度为n-1，其余顶点出度均为0，最多有(n-1)!种拓扑排序结果。3.第一步：遍历所有顶点，找出入度为0的顶点F并将该顶点入队，将与F连接的顶点E、B、C、G入度减1，同时让F出队，F即为拓扑排序的第1个元素。此时拓扑序列为｛F｝。第二步：遍历所有顶点，找出入度为0的顶点E并将该顶点入队，将与E连接的顶点A入度减1，同时让E出队，E即为拓扑排序的第2个元素。此时拓扑序列为｛F,E｝。第三步：遍历所有顶点，找出入度为0的顶点A并将该顶点入队，将与A连接的顶点B入度减1，同时让A出队，A即为拓扑排序的第3个元素。此时拓扑序列为｛F,E,A｝。第四步：遍历所有顶点，找出入度为0的顶点B并将该顶点入队，将与B连接的顶点C入度减1，同时让B出队，B即为拓扑排序的第4个元素。此时拓扑序列为｛F,E,A,B｝。第五步：遍历所有顶点，找出入度为0的顶点C并将其入队，将与C连接的顶点D入度减1，同时让C出队，C即为拓扑排序的第5个元素。此时拓扑序列为｛F,E,A,B,C｝。第六步：遍历所有顶点，找出入度为0的顶点D并将该顶点入队，将与D连接的顶点G入度减1，同时让D出队，D即为拓扑排序的第6个元素。此时拓扑序列为｛F,E,A,B,C,D｝。第七步：遍历顶点发现只剩下顶点G，则G为拓扑排序的最后一个元素。因此，该有向图的最终拓扑排序序列为｛F,E,A,B,C,D,G｝。

第4章习题参考答案1.（1）基于贪心法的哈夫曼树构造过程如下：①合并出现频率最小的字符B和D，并计算合并后的频率；②合并出现频率最小的字符E和C，并计算合并后的频率；③合并出现频率值最小的两个节点，并计算合并后的频率；④合并所有字符，完成哈夫曼树的构造。（2）ABACABAD的编码为0100011101000101。（3）100010111001010解码为BADEADA。注意：上述答案不唯一，根据构造的哈夫曼树结构不同而不同。2.每次先取剩余硬币中面值最大的硬币，如果不满足条件，再选择次面值最大的硬币。假设有4种硬币，面值分别为50元、10元、5元和1元。如需找零99元，首先选择一个面值不超过99元的最大硬币，即50元，由于9050=1，因而选择一个面值为50元的硬币，然后从99元中减去50元，剩下49元。再选择一个面值不超过49元的最大硬币，即10元，由于4910=4，因而选择4个面值为10元的硬币，然后从49元中减去40元，剩下9元。如此一直做下去，最终的硬币选择方案为1个50元的硬币、4个10元的硬币、1个5元的硬币和算法：Change//求解找零问题的贪心算法输入：找零金额n，非升序的硬币面值{d1,d2输出：每种面额硬币数量C[1:m]步骤：1.Fori=1TomD2.C[i]←03.EndFor4.Fori=1TomD5.C[6.n←nmod7.EndFor8.Ifn=09.ReturnC10.Else11.ReturnNoSolution//无解3.每次选择元素个数最少的两个列表进行合并排序，从而合并元素时元素比较总次数最少。该算法的步骤如下：（1）找到包含元素最少的两个列表，可采用堆排序算法根据列表中元素个数进行排序，时间复杂度为O(nlog（2）找到元素最少的两个列表后采用算法2.2进行合并，时间复杂度为O(nlog由于每次需通过堆排序查找包含元素最少的两个列表，共执行(n-1)次堆排序，因此该算法的时间复杂度为O(n

第5章习题参考答案1.动态规划的基本思想：问题的最优解如果可由子问题的最优解推导得到，则可先求解子问题的最优解，再构造原问题的最优解。动态规划要把之前步骤已计算出的结果记录下来，当需要求解原问题的时候，就可使用各子问题（规模更小）的解来构造当前解。动态规划是一个多阶段决策，不是一次性解出多个，而是将多个决策变成多次决策；各个子问题之间并不独立，大规模问题的解可由小规模问题的解进行递推得到（前后有联系）。使用动态规划算法求解问题的基本步骤：（1）分析最优解的性质，刻画其最优子结构特征。（2）递归地定义最优值。（3）根据状态转移顺序，以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，以填表的方式构造最优解。动态规划算法适用的条件或场景：（1）最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。（2）无后效性：某状态以后的过程不会影响以前的状态，只与当前状态有关。（3）重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用。2.共同点：二者都要求原问题具有最优子结构性质，都是将原问题分而治之，分解成若干个规模较小(小到很容易解决的程序)的子问题，找出子问题与原问题之间的关系（递推式）然后将子问题的解合并，形成原问题的解。不同点：分治法中，分解后得到的子问题相互独立，通常使用递归算法求解。动态规划法中，分解后的子问题相互间有联系（并不独立）、有重叠部分，需要记忆，通常使用迭代方式来求解。3.（1）各子问题的最优值如下表：物品容量0123456000000001000252525252002025254545301520354045604015203540556050152035405565第一行的值为0，因为物品标号为0（考虑前0个物品的最优值）的情况下（即没有物品）最大价值都是0。第一列的值为0，因为在当前背包容量为0的情况下最大价值都是0。当i=2、j=3时，由于j>w2，物品2可装入背包、也可不装入背包，此时考虑物品2是否装入背包，比较装入或不装物品2时的最大价值：物品2不装入背包时的价值为b(2,3)=25；物品2装入背包时的价值为b(2,3)=b(2-1,4-2)=20；取两者中的最大值max{25,20}=25，即此时背包最大价值为25。以此类推，继续迭代直至填满表格。（2）有1个最优子集。最优值为最大价值65，最优解为{0,0,1,0,1}。（3）一般来说，可以通过判断表中最后一列的最大值个数来判断（背包问题的最优值只会在最后一列中产生）。4.分析：无论怎样的组合，最后有i枚硬币的面额加起来等于总金额j。设最后一枚硬币为的面额为di，这枚硬币之外的前面硬币的面额加起来为j-di。我们不关心前面i-1枚硬币的组合，也不知道di和i。可以确定的是，前面的硬币组合成了n-di，且硬币的数量一定减少。因此，可用数组fi[j]来表示用i针对第i-1项，最后一枚硬币的面额为d1,d2,…,dm时，所需最少硬币数分别为因此，f[i][j]=min{f[i-1][j],  f[i][j-di]+1}（算法如下：算法：MinimumChange//最少硬币找钱输入：Coins[1:m],n//Coins代表硬币面额数组，n为需找钱金额输出：f[m][n]步骤：1.Fori=1TomDo2.f[i][0]←03.EndFor4.Fori=1TomDo5.Forj←1TonDo6.Ifj<Coins[1]Then7.f[1][j]←+∞8.Else9.f[1][j]←1+f[1][j-Coins[1]]10.EndIf11.Ifj<Coins[i]Then12.f[i][j]←f[i-1][j]13.Else14.f[i][j]←min(f[i−1][j],1+f[i][j-Coins[i]])15.EndIf16.EndFor17.EndFor18.Returnf[m][n]时间复杂度为O(mn)。5.分析：首先将问题分解，构建递推式。在国际机场i的飞机有两种可能的飞行方式：（1）直接从国际机场飞到中心机场，花费为s+d[i]（2）从中间的某一个国际机场转机，花费为s+(dj-di)2+C(j)（从j机场飞到中心机场的费用+因此算法思想为：对各个国际机场到中心机场的距离进行排序，C(i)为飞机只选择前i个国际机场、飞行距离为k时的最小花费，最小花费为C(i)=min{s+d[i]2,s+dj假如有编号为1、2、3、4的四个机场。类比Floyd算法，构建一个一维数组。数组中存放到当前点到中心机场的距离。使用一个循环来更新这个数组，循环的次数为n次。每次循环都比较直飞的距离与当前点经过第i个（1≤i≤n）机场中转的最小花费。经过n轮循环，确定最后的结果。算法如下：算法：MinimumFee//飞机飞行最小花费输入：s,d1//s为地面加油费用，di1≤i≤n为第i输出：C(n)//距离中心机场最远的国际机场飞到中心机场的最小花费步骤：1.Fori=1TonDo2.Forj=1TonDo3.C4.EndFor5.EndFor6.ReturnC(n)时间复杂度为O(n2第6章习题参考答案（1）算法思想：按顺序依次从集合中选取元素，将选取元素的值进行相加，如果相加结果大于给定的正整数d，则停止选取新元素，回溯到上一个所选择元素，将该元素和其后续选择的元素从已选元素集合中删除，再继续选取该元素的后续元素。重复上述过程，直到选择元素累加值等于给定正数d或已完成对解空间树的遍历，算法终止。如题中示例，在选取元素1、2、5、6后，发现元素累加值大于9，则回溯到元素5，将元素5及其后续选择的元素从已选元素集合中删除，然后选择元素5的后续元素6，此时元素累加值满足给定正整数d=9，从而得到问题的解。（2）解空间树如下：

第7章习题参考答案（1）算法思想：首先应用贪心法求得最优值得上界2+3+5+4=14，每一行的最小元素相加得到最优值的下界2+3+1+4=10，最优值必为10~14中的某个值。设当前已对人员1分配了任务，并且花费了成本，则限界函数可定义为。假设已经将任务2分配给人员1，任务3分配给人员2，则花费的成本是5，该部分解可能获得的最小成本是5+(1+4)=10。（2）解空间树如下图所示，包含13个节点。

第8章思考题参考答案1.C4.5是一种经典的决策树算法，基本思想是选择具有最大信息增益率的属性作为分裂属性，在构造树的过程中通过剪枝操作降低过拟合风险。给定样本集合D和具有V个离散取值的属性a，信息增益率计算公式如下：GainRatio(D,a)=其中，IVa=v=1VDv|D|*log2DvD，称为属性a的固有值，a的可能取值越多（V越大），IVa的值通常会越大。给定样本集合D和属性集合A={a1,a（1）创建根节点N。（2）若D中所有样本全属于同一类别C，则将N的类别标记为C。（3）若A为空集或D中所有样本在A上取值相同，则N为叶子节点，且N所属类别为D中样本数量最多的类别。（4）对A中每个属性计算信息增益率GainRatio(D,a)，并得到最优划分属性a*（5）根据a*中每个取值a*v，为N生成一个叶子节点，若该叶子节点对应样本子集Dv为空，将此节点标记为叶子节点，且类别为D中数量最多的类别；否则，以Dv为样本集、A\{（6）根据剪枝策略对生成决策树剪枝，输出以N为根节点的决策树。2.证明：设点x到超平面S上的投影为x1，则w由于x1x与S的法向量 w⋅x1x此外，基于欧几里得距离，向量的模为其L2范数 w⋅x1x通常，若范数无下标（如w），则||w||2 ||w||2=||又因为 w⋅x1x已知 w⋅x1+b=0 w⋅x1=-b将式（6）代入式（4）中得 w⋅x1x将式（7）代入式（1）中 -b-wTx=||则 r=wTx+3.SVM本身是一个二值分类器。SVM算法最初为二值分类问题而设计，当处理多类问题时，就需要构造合适的多类分类器。目前，构造SVM多类分类器的方法主要有直接法和间接法两类。（1）直接法。直接在目标函数上进行修改，将多个分类面的参数求解合并到一个优化问题中，通过求解该优化问题，“一次性”实现多类分类。这种方法看似简单，但计算复杂度高，实现困难，只适用于小样本分类问题。（2）间接法。通过组合多个二分类器实现多分类器的构造，常见的方法有one-against-one和one-against-all两种。one-against-one方法在每两个类之间都构造一个binarySVM；one-against-all方法训练时依次把某个类别的样本归为一类，剩余样本归为另一类。4.增量贝叶斯分类器通过学习带有类标签的实例来判断无标签实例的类别，逐步更新分类器的参数。针对新增样本的特点，增量学习主要分为两种，一种是样本集中所有实例都带有类标签，另一种是样本集中只有一部分实例带有类标签。设样本空间S由特征空间I和类别空间C组成，其中，S=s1,s2,…,sn}=I,C，I=A1,A2,…,Am，C=c1,c2,…,cl为了提升训练效率，以贝叶斯模型本身具有增量的学习特性为基础，分别给出增量地学习分类参数和增量地更新已有类别概率的具体实现：（1）增量学习分类参数假设选择xp',cp θr其中，δ=C+|D|，θr（2）增量更新已有类别概率通过分析学习参数的变化可知，xp',cp'加入到训练集后，只有与之相关的项的估计变化较大，而与之无关的项变化较小。为此，使用D∪ Pc其中，P(t|cq',θ)是在D下的估计，P(t|c5.类别不平衡，是指在分类任务中不同类别的训练样本数目差别很大，导致分类结果偏向于较多观测的类，进而影响分类效果。可使用欠采样法直接对训练集中多样本类进行“欠采样”，即去除一些多样本类的样本，使得正例、反例数目接近，然后再进行学习。或使用过采样法，增加一些少数类样本，使得正例、反例数目接近，然后再进行学习。6.根据个体学习器的生成方式，目前集成学习方法主要分为两大类，第一类是个体学习器之间存在强依赖关系，必须串行生成的序列化方法，代表性方法为“Boosting”；第二类是个体学习器间不存在强依赖关系，可同时生成的并行化方法，代表性方法为“Bagging”和“RandomForest”。（1）Boosting：基分类器以串行方式连接，各基分类器相互依赖。基本思想是将基分类器层层叠加，每一层在训练的时候，对前一层基分类器分错的样本给予更高的权重。测试时，为了降低分类的偏差，根据各层分类器的结果的加权得到最终结果。（2）Bagging：训练过程中各基分类器之间无强依赖，可通过并行训练对每个个体单独学习，学习内容可相同、也可不同。最终决策时，每个个体单独判断，再通过投票方式做出最后的集体决策，旨在降低分类的方差。（3）Bagging：训练过程中各基分类器之间无强依赖，是一个集体决策的过程，可通过并行训练对每个个体单独学习，学习内容可相同、也可不同。最终决策时，每个个体单独判断，再通过投票方式做出最后的集体决策，旨在降低分类的方差。

第9章思考题参考答案1.从外部指标和内部指标两个方面度量聚类结果好坏。（1）常用的外部指标包括①纯度：用聚类正确的样本数除以总的样本数。②兰德系数（RandIndex,RI）RI=其中，TP表示两个同类样本点在同一个簇中的情况数量；FP表示两个非同类样本点在同一个簇中的情况数量；TN表示两个非同类样本点分别在两个簇中的情况数量；FN表示两个同类样本点分别在两个簇中的情况数量。③F值（FβPrecision=Recall=F其中，β=1时，称为F1-score，此时精确率和召回率同样重要。某些情况下，如果认为精确率更重要些，则调整β的值小于1；如果认为召回率更重要些，则调整β的值大于1兰德系数和F值越大表示聚类效果越好。（2）常用的内部指标包括①误差平方和（SumofSquaredErrors,SSE）。SSE计算公式如下：SSE=其中，r代表簇的个数，ni代表第i个簇中的样本数，Xij为第i个簇中的第j个样本取值，Xi为第理论上，SSE的值越小越好。该指标的局限性是，只考虑簇内样本的相似度，未考虑不同簇之间的关系。②轮廓系数（S）。对于某个样本而言，将该样本与簇内其他样本点间的平均距离定义为簇的内聚度a，将该样本与最近簇中所有样本点间的平均距离定义为簇之间的分离度b，则该样本轮廓系数的计算公式如下： S=b-a对于全体样本的集合而言，所有样本的轮廓系数均值称为聚类结果的轮廓系数。该指标的取值范围是1~1，当簇间分离度b远大于内聚度a时，轮廓系数的值近似等于1。所以该指标的值接近1，聚类效果越佳。2.确定k值大小，核心指标是定义如下的误差平方和： SSE=i=1其中，Ci是第i个簇，p是Ci中的样本点，mi是Ci的质心（手肘法的基本思想是随着聚类数k的增大，样本划分会更精细，每个簇的聚合程度会逐渐提高，SSE会逐渐变小。当k小于真实聚类数时，由于k的增大会大幅增加每个簇的聚合程度，故SSE大幅下降；当k到达真实聚类数时，再增加k所得到的聚合程度，SSE的下降幅度会骤减，且随着k值的继续增大趋于平缓。SSE和k的关系图是一个手肘形状，肘部对应的k值就是数据的真实聚类数，这也是该方法被称为手肘法的原因。手肘法的主要步骤包括：（1）k-均值算法中每一步都可计算出SSE值，即每个聚类中的点到它们质心的距离的平方；（2）找出SSE曲线下降途中的拐点，当设定的簇数量不断逼近真实簇数量时，SSE呈现快速下降态势，而当设定簇数量超过真实簇数量时，SSE也会继续下降、下降会迅速趋于缓慢，找出SSE曲线下降途中的拐点，即可较好的确定k值。3.用于聚类算法的距离计算方法主要有如下几种：（1）闵可夫斯基距离样本xi=xi1 dij（2）马氏距离在标准化欧几里得距离中，即使消除了量纲的影响，若忽略特征之间的相关性，仍可能导致分类错误。给定一个样本集合X，X=x1,x2,…,x dij（3）余弦距离利用闵可夫斯基度量对高维数据进行聚类通常是无效的，因为样本间的距离随着维数的增加而增加。余弦距离测量两个矢量之间的夹角，而不是两个矢量之间的幅值差，适用于高维数据聚类时相似度测量，定义为： d=cos4.首先，将所有非数值型数据转换成编码，例如，针对表中的收入属性，可将low、medium、high分别转换为0、1、2。接着，在所有非数值型数据都已转换成编码后，将所有数据构成一个矩阵，矩阵的每一行作为一个特征向量，每一个特征向量代表训练数据集表中的一行数据。最后，通过执行以向量之间的欧式距离为度量的k-均值算法，而实现聚类。

第10章思考题参考答案1.使用二分类的异常检测，优点是简单、速度快，缺点是当样本不平衡时不能很好地衡量结果。2.聚类问题是将样本集合按照某种模式相似性度量和聚类算法，无监督地将相似的样本归为一类，属于无监分类（不需先验知识，无指导的分类），所以聚类问题更注重于分类。异常检测问题旨在检测数据中不符合预期行为的数据，其基本思想是通过数据挖掘方法找出显著不同于其他数据的异常点，所以异常检测问题更注重于找出异常点。聚类是为了发现强相关的簇，而异常值检测则是为了检测与其他对象不强相关的数据点。聚类算法的目标是将数据点划分到某一类中，异常值检测的目标是检测一些不属于任何簇的数据点。没有任何一种聚类算法适用于所有数据集，不同数据集需采用不同的聚类算法。当聚类算法选取不合适时，样本不能创建任何有意义的簇，那么该方法可能会失败。针对高维空间中的稀疏数据，任意两个样本间的距离可能会非常相似，聚类算法可能得不到有意义的簇。3.生成模型用于异常检测的基本思路是，学习生成网络的潜在特征空间，使潜在特征空间能很好地捕捉到给定数据背后的常态。将生成模型用于异常检测的核心思想是，在生成网络的潜在特征空间中，更能准确地产生正常实例，并且实际实例和生成实例之间的残差定义为异常分数。生成模型用于异常检测基本步骤为：（1）将样本数据输入到生成模型中进行训练，使生成模型能描述样本数据的概率分布。（2）将新实例输入到训练好的生成模型中并输出生成实例，计算新实例与生成实例之间的残差。若新实例服从样本数据的分布，则表明能较好地生成实例，且它们之间的残差很小；否则残差很大，当残差超过一定阈值时，判断该新实例为异常数据。

第11章思考题参考答案1.Apriori算法与AprioriTid算法都是利用低阶频繁项集生成高阶候选项集，进而生成所有频繁项集的重复过程。不同之处在于，Apriori算法每次迭代都通过扫描原始数据库计算候选项集的支持度，而AprioriTid算法通过生成k阶Tid表Ck，存储每个事务中的k维候选项集，以判断k维候选项集是否能成为k维频繁项目集，避免原始数据库的重复扫描AprioriTid算法引入的k阶Tid表记为Ck，形式化为<t.Tid,{C∈Ck|C⊆t}>，其中，Tid为事务t的标识，C为事务（1）扫描原始数据库，得到1阶Tid表和频繁1-项集，连接频繁1-项集得到候选2-项集，将候选2-项集中项的映射至1阶Tid表。（2）当k>2时，将(k－1)阶Tid表Ck－1视为数据库进行扫描。对任意k阶候选项集C，如果C的子集均包含于Ck-1的某条记录中，则将C（3）重复上述步骤，直到没有新的频繁项集生成为止。2.数据转换是有效挖掘数值型样本关联规则的代表性方法。简单且直接的方法是将数值型数据分割为几个相邻的区间，然后对数值型样本在各个区间进行映射，转换为离散型数据样本，进而采用Apriori算法来挖掘关联规则。此外，可采用模糊概念将数值型数据进行抽象、概括，例如，[90,100]的成绩概括为“优秀”，[80,90)的成绩概括为“良好”，等等。然后，通过设置隶属函数将每个数值映射至模糊集中，计算支持度、并产生模糊关联规则。

第12章思考题参考答案1.PersonalizedPageRank（PPR）算法的目标是，计算所有节点相对于用户u的相关度。从用户u对应的节点开始游走，每到一个节点都以1d的概率停止游走并从u重新开始，或以d的概率继续游走，从当前节点指向的节点中按照均匀分布随机选择一个节点往下游走。因此，引入用户偏好节点，可个性化地计算网络节点的相关性和重要性。经过多轮游走之后，每个顶点被访问到的概率也会收敛、趋于稳定，此时可基于该概率进行排名。PPR与传统PageRank不同的是，每次重新游走时，总是从u开始。另外，对每个节点的权重进行初始化时，假如对u进行推荐，PPR将u初始化为1，其他节点都初始化为0。引入用户偏好节点加强了用户的相关性特征，如在商品推荐中，引入用户偏好节点能吸引与购买用户相似的用户，因为他们购买了相同（或相似或相关）的产品。此外，引入用户偏好节点可发现相似/相关产品，因为它们是由相同（或相似或相关）用户购买的。2.基于Spark的PageRank算法，维护两个数据集，一个由（pageID,linkList）的元素组成，包含每个页面的相邻页面列表；另一个由（pageID,rank）元素组成，包含每个页面的当前排序值。算法步骤如下：（1）将每个页面的排序值初始化为1.0。（2）每次迭代对页面p的每个相邻页面（有直接链接的页面）发送一个值为rank(p)/numNeighbors(p)的贡献值，记为contributionsReceived，其中，numNeighbors(p)表示p邻居页面的排序值。（3）将每个页面的排序值设为0.15+0.85*contributionsReceived。算法第2步和第3步循环迭代。在该过程中，算法会逐渐收敛于每个页面的实际PageRank值。实际中，收敛通常需要大约10轮迭代。3.（1）HITS算法对于每个页面需计算Authority和Hub两个分值，PageRank只需计算一个分值。搜索引擎应用更重视HITS算法计算出的Authority权值，但在很多使用HITS算法的其他领域，Hub分值也有重要作用。（2）从两者的计算效率和处理对象集合大小来看，PageRank算法更适合部署在服务器端，而HITS算法更适合部署在客户端；（3）HITS算法因为与用户查询密切相关，因此必须在接收到用户查询后实时计算，计算效率较低；而PageRank算法广泛应用于离线计算，直接使用计算结果，计算效率较高；（4）HITS算法的计算对象数量较少，只需计算扩展集合内网页之间的链接关系；而PageRank算法是全局性算法，对所有互联网页面节点进行处理；（5）HITS算法存在主题泛化问题，因此更适合处理具体化的用户查询；而PageRank算法在处理宽泛的用户查询时更有优势；（6）从链接反作弊的角度来说，PageRank算法从机制上优于HITS算法，而HITS算法更易遭受链接作弊的影响；（7）HITS算法结构不稳定，当对“扩充网页集合”内链接关系做出很小改变，则对最终排名有很大影响；而PageRank算法相对HITS而言表现稳定。

第13章思考题参考答案1以知识图谱（KG）为代表的领域知识库，往往使用逻辑规则描述内部实体之间的语义信息，实现知识推理。通过将领域知识库中的逻辑规则表示为Horn子句（只含有一个正文字的析取式，形如p1∨p2∨…pn∨q），等价地转换为有向无环图（DAG）具体地，给定一个Horn子句h，若h蕴含p→q，则可在DAG中构建一条p指向q的有向边。基于这一思想，对于每一条Horn子句均可构建一个逻辑等价的DAG。然后，通过最大似然估计从数据中计算各节点的CPT，得到描述数据和逻辑规则中所蕴含知识的2基于BN近似推理思想，首先利用采样算法生成大量的样本数据。然后，针对CPT中的缺失值，采用期望最大（EM）算法进行修补。具体地，对于缺失的参数θ，EM算法从某个随机产生的初始值θ0出发，基于已有网络结构和参数估计样本中缺失数据的权重，可得到一组带权样本。在通过一系列完整的带权样本填充缺值数据后，利用最大似然估计更新缺失的参数θ。重复上述步骤直至θ收敛，进而通过补全的参数实现BN推理。此外，可引入分类挖掘思想，对每个变量学习分类器，将其变量取值进行分类，例如，将[20,23]和(23,25]视为不通的年龄段等。通过生成样本数据学习变量在不同类别下的CPT，即可在证据不包含于原CPT中时执行概率推理。基于深度学习模型也可解决证据不包含于CPT时的概率推理问题，即通过学习CPT的连续条件概率分布（CPD），解决概率推理任务中变量取值不在CPT中时无法执行概率推理的问题。例如，假设CPD服从高斯混合模型（GMM），即可将GMM的参数近似地作为需得到的CPD；然而，用于GMM参数学习的EM算法对初始值较敏感。以生成对抗网络（GAN）为代表的深度学习模型通过最小化生成分布和真实分布之间的差异来学习真实分布，因此，可使用GAN的生成器和判别器的迭代训练，取代传统的EM算法，从而学习得到GMM的参数，通过GMM参数来近似得到CPT的连续真实分布CPD。3为了学习贝叶斯网分类器，将C和X中每一个属性变量xj（j=1,2,...,n）分别视为BN中的节点，且通过属性变量构建的节点取值为1或0，通过C构建的节点取值为{c1,c2,…,cm}。节点集合{x1,x2,…,xn,C}作为无边的DAG初始结构，基于算法13.1学习得到贝叶斯网分类器的DAG结构，并通过最大似然估计从D中计算各节点的CPT。基于贝叶斯网的概率推理实现基于贝叶斯分类器的预测，即计算P(ci|x)=max{P(c1|x),P(c2|x),...,P(cm|x)}，为此，将输入的待分类数据x视作证据变量，节点C视作查询变量，通过贝叶斯网的概率推理算法，计算得到满足P(C=ci|x=1)=max{P(C=c1|x=1),P(C=c2|x=1),...,P(C=cm|x=1)}的C的取值，以之作为x的分类。

第14章思考题参考答案1.将图14.3中的神经网络扩展为l层全连接神经网络，给定训练样本(x,y)，x为输入向量，y为标签向量，设x经过该l层全连接神经网络得到的输出向量为ŷ，我们希望通过调整参数向量w和b，使网络输出向量ŷ与标签向量y尽可能接近，也就是网络输出与真实标签间的均方误差尽可能小，即min各层网络间的关系表示为a由链式法则可知，损失值E对第ii≤l∂E2.由式（14-10）yyi对向量z的第i个分量zi∂yi对向量z的第j个分量zj∂3.神经网络的泛化能力是指，学习到的模型对未知数据的预测能力，泛化能力是衡量神经网络性能优劣的一个重要指标。一般使用“欠拟合”、“正常拟合”和“过拟合”来衡量模型的泛化能力。其中，“欠拟合”是指模型在训练数据集上表现差，在测试数据上表现也差；“正常拟合”是指模型在训练数据集和测试数据集上均表现良好；“过拟合”是指模型在训练数据集上表现好，但在测试数据集上表现差。影响神经网络的泛化能力的主要有以下两类因素：（1）样本复杂性，是指训练某一固定结构神经网络所需的样本数量。训练样本数量过少，可能导致过拟合，模型表达能力不足。（2）神经网络的结构复杂性，是指模型的规模或容量。模型参数的数量较少，往往使模型的泛化能力不足而导致欠拟合；模型参数的数量过多，会出现模型对已知数据预测得很好，但对未知数据预测得很差的现象。根据样本数量和参数数量，优化神经网络训练过程的一般方法为：（1）尽可能获得较高质量的样本数据，即样本的分布能较好反映总体分布。（2）尽可能增加样本数量，以便模型能充分学习到样本的一般性质。（3）当拥有充分的训练样本时，可通过增加网络参数来提高模型的表达能力。（4）当训练样本不够时，可通过简化网络结构来提高模型的泛化能力。此外，还可通过正则化、dropout、提前停止等方法来提高模型的泛化能力。当神经网络的结构复杂性与样本复杂性协调时，模型就会有较好的泛化能力。

第15章思考题参考答案1.自编码器是一种非线性降维技术，采用带隐藏层的神经网络，将高维数据映射成低维空间中的嵌入向量，进而实现数据的降维，能较好地学习到数据之间的非线性关系。用于图像分类的自编码器主要包含两个部分：第一个部分为原始的自编码器结构，即通过编码器和解码器学习图像的特征；第二个部分为分类器，其输入为第一部分的输出。用于分类任务的支持向量机（SVM）主要包括两个部分：第一个部分为特征提取器，第二个部分为分类器，其中SVM充当分类器。SVM实现分类的基本思想是，通过某种事先选择的非线性映射函数（核函数），将输入特征通过非线性变换到高维的特征空间，在高维空间中构造最优分类超平面。尽管通过非线性变换将样本数据映射到高维甚至无穷维空问，然后在高维空间中构造最优分类超平面，但在求解最优化问题和计算分类平面时并不需要显式计算该非线性函数，甚至不需知道其具体形式。因此，SVM巧妙地解决了维数问题，其算法复杂度与样本维数无关；SVM克服了神经网络分类分类法的许多缺点，具备较高的泛化能力，某些情形下可替代多层感知机和神经网络等已有的学习算法。2.首先利用自编码器提取高维数据特征，再借助聚类算法实现分类。经过自编码器训练后，得到重构后的数据。处理自编码器输出的k-均值聚类算法和经典的k-均值聚类算法思路大致相同，可概括为以下几步：（1）初始化：确定初始聚类中心，随机挑选原始数据样本的k个点作为第1次聚类的聚类中心；（2）聚类：计算样本集中其他样本点到选定的k个聚类中心的欧几里得距离，并将样本点分别归到与其欧几里得距离最小的类别中，作为同一类；（3）重新计算聚类中心：分别计算各类内样本的平均值，作为每一类的新的聚类中心；（4）循环迭代：重复执行（2）和（3），直到循环次数达到最大值；（5）聚类结束：取最后1次循环的结果作为聚类结果，计算所有样本的聚类精度和各个类的聚类精度。3.自编码器是一种无监督学习模型。它基于反向传播算法与最优化方法（如梯度下降法），利用输入数据本身作为监督来指导神经网络学习一个映射关系，从而得到一个重构输出。在异常检测场景下（异常对于正常来说是少数），如果使用自编码器重构出来的输出与原始输入的差异超出一定阈值，则原始数据存在异常。通过将数据集划分为正常数据和异常数据，并利用正常数据来训练自编码器，以学习到正常数据的编码，然后根据学习到的编码，在一定程度内还原正常数据。因为该自编码器已学习到了正常数据的编码格式，所以当一个数据提供给该自编码器时，它会按照正常数据的编码格式去编码和解码，并得到一个还原误差。如果解码后的数据和输入数据的还原误差小于误差阈值，则表明输入的数据是正常的，否则是异常的。4.生成对抗网络异常检测模型框架由以下三部分组成：（1）GE(x)和GD(z)统称为生成网络，可看成是模型的第一部分。这一部分由编码器GE(x)和解码器GD(z)构成，对于输入数据x经过编码器GE(x)得到潜在向量z，z经过解码器GD(z)得到x的重构数据x'（2）模型的第二部分是判别器D，对于原始图像x判为真，重构图像x'（3）模型的第三部分是对重构图像x'再做编码的编码器E(x')，得到重构图像编码的潜在变量在训练阶段，整个模型均是通过正常数据进行训练，也就是编码器GE(x)、解码器GD(z)和重构编码器E(x')，都适用于正常数据。当模型在测试阶段接收到一个异常数据时，模型的编码器和解码器将不适用于异常样本，编码后的潜在变量z和重构编码器得到的潜在变量z'之间差距A(设定一个阈值φ，当A(x)>φ时，模型就认定输入的样本x5.变分自编码器能实现给定随机噪声z生成数据x：z→P(x)。若需给定条件c生成数据x，例如给定输入标签0~9，生成对应的手写体数据，传统的变分自编码器不能实现这种需求。此时，需在变分自编码器的基础上增加一个条件输入c，其对应的模型是条件变分自编码器，具体过程可参见文献“K.Sohn,X.Yan,H.Lee.LearningStructuredOutputRepresentationusingDeepConditionalGenerativeModels.Proc.NIPS2015,pp.3483–3491”。6.如果观察到隐变量服从的分布与先验分布差距较大时，可用参数β>1赋予KL散度项更高的权重，鼓励网络学习更广泛的分布，这种简单的操作衍生了一类新的模型解耦的变分自编码器（DisentangledVariationalAutoencoders）。变分自编码器的损失函数变化如下：J7.以多模态的文本和图像数据融合的生成对抗网络为例，介绍生成对抗网络实现文本、图像、结构化数据等多模态数据的融合方法。首先，用全连接层-隐藏层-全连接层的结构构造包含两个生成器、一个判别器的生成对抗网络，并将训练图像的属性特征矩阵A和文本矢量特征矩阵W分别输入到两个生成器中，完成对应伪图像的合成。通过冗余处理。将融合的特征作为判别器伪通道的输入，与训练图像的真实视觉特征进行对抗，最终获得两个具有高性能的生成器。测试阶段将测试图像的属性特征矩阵At和文本矢量特征矩阵W

第16章思考题参考答案1.将视频数据拆解为一帧一帧的图像数据，将每帧图像数据都输入到已训练好的YOLO模型进行检测，保存检测后的每一帧图像数据，并将检测后的图像数据合成视频数据作为输出结果。2.目标检测基于静态图像数据，在给定图像中对特定目标物体进行自动识别和定位，包括目标定位子任务和目标分类子任务。目标定位子任务负责确定输入图像中目标物体的位置和范围，输出物体的检测框来表示物体的位置信息；目标分类子任务负责判断输入图像中是否含有需检测的目标物体，并输出相应置信度分数来表示目标物体所属的类别。目标跟踪基于视频数据，在视频序列初始帧中通过矩形框指定所需跟踪目标物体的位置和尺寸，在后续视频帧中连续估计目标的状态，不断地移动和调整矩形框的位置和大小，使其能更好地框住目标物体。目标跟踪不需识别出目标物体所属的类别，可通过观察目标物体的位置、大小和形状的时空变化来跟踪物体。3.可通过如下两种方法对已训练好的目标检测模型进行压缩。（1）模型剪枝：通过删除已训练好的目标检测模型中的冗余参数来降低模型的复杂度，减少计算资源的占用。例如，模型中权值接近零的参数对检测结果影响较小，可将参数权值作为冗余度评价准则来确定需要删除哪些参数。随着删除参数的增加，模型的检测精度会逐渐降低，需在删除一定数量的参数后，通过微调训练来恢复模型的检测精度。（2）参数量化：目标检测模型