第1章习题参考答案.docx

第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. 5log(n+100)<log2n<Vn<0.001n4+2n3+1<3n<(n-2)!<2n24. (1)/(n)=O(n),由于Hm鬻=Iim二0。ng(n)n2. )=O(g(),由于Iim=Iim"+"%”=0。ng(n)nn3. )g(n)=O(n),由于Iim华=Iim匕等=8。D7'''n80(n)nn4. )g(i)=O(n),由于Iim=Iim=8。°U'n8(n)nlogn+15. 证明：令F(ZI)=O(/(几)，G(Zl)=O(以九)。根据。的定义，存在正常数Cl和非负整数%,使得对所有的n叫,有尸(7i)cJ(n);同理，存在正常数Q和非负整数九2,使得对所有的nn2,有G(n)vgOO。令C3=qc2,H3=maxn1,n2,h(ri)=f(n)g(i),则对所有的几n3,有F(n)G(n)=()(n)c1f(n)c2g(n)=c3h(n)因此。(/(几)。(。(几)=O(M九)=。(/'(咖)证毕。6. (1)元素比较操作最少执行n-l次，当原列表为升序排列时达到该最小值。(2)元素比较操作最多执行电3次，当原列表为降序排列时达到该最大值。(3)元素赋值操作最少执行。次，当原列表为升序排列时达到该最小值。(4)元素赋值操作最多执行若2次，当原列表为降序排列时达到该最大值。(5)OoI2),(n)o7. (1)使用蛮力法，遍历所有元素找出最大值，时间复杂度为05)。算法：BrUteSearCh蛮力法输入：查找列表41：T输出：力中的最大值步骤：1. max<-Al2. Fori=2TonDo3. IfAi>mThen4. max<-Ai5. EndIf6. EndFor7. ReIUmmax(2)使用算法2.1中的递归合并排序算法对列表4进行非降序排序，排序后列表A的最后一个元素即为最大值，时间复杂度为O(Mogn)°8. (1)为了方便表示，用M(Ti)表示乘法运算次数，那么M(Tl)需满足M(n)= 10,M(n-1)+1,当n>1时当n=1时采用迭代法可得到M(n)=M(n-1)+1=M(n-2)+1+1=M(n-2)+2=M(n-3)+l+l=M(n-3)+3不难看出M(n)=M(ni)+i=M(n(n1)+n1=M(I)+n-l=n1(2)为了方便的表示，用Sm)表示加减运算次数，不包括"减少时所需的减法运算，那么S5)需满足、(S(n-1)+2,当n>l时SQI)=(0,当n=1时采用迭代法可得到S(n)=S(n-1)+2=S(n-2)+2+2=S(n-2)+4=S(n-3)+2+4=S(n-3)+6因此S(ri)=S(ni)+2i=S(n(n-1)+2(n1)=S(I)÷2(n-1)=2n-29. (1)由原式可得T(n)-y=3(r(n-1)-y)T(n)-竽=3则T(n)-号是以3为公比的等比数列，首项为丁一蔡=也即()一孩=汐-1,则Ts)=T3时】+协(2)由原式可得T(TI)-T(Tl-I)=n1T(n-1)-T(n-2)=(n-1)-1=n-2T(n-2)-T(n-3)=(n-2)-1=n-3T(2)-T(I)=2-1=1上述式子累加可得T(n)-T(I)=与2即Tm)=3尸2+3。第2章习题参考答案1 .每趟执行后列表中的元素如下表：ANEXAMPLEAENXAMPLEAENAXMPLEAAENXMPLEAAENXMPELAAENXELMPAAEEI.MNPX2 .(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:r的最大值和最小值。算法：MaxMin/分治法求最大最小值输入：A:r输出：心X,min/A中的最大值和最小值1. Ifr=Then2. wav<-Al;min<-A3. returnmax,min4. EndIf5. If=2Then6. wr<-ma×Al,Ar;min<r-mini4Z,i4r7. returnmax,min8. EndIf9. mid-9+r)210. (max,加1)-MaXMin(A/:mid)/处理前半部分11. (nax2,加2)-MaXMin(Amid+1,r)处理后半部分12. Ifnin2<minIThen13.14. EndIf15. Ifmax2>tnaxThen16. nax-nax217. EndIf28. Returnmax,min(1)以元素比较为基本，算法的计算时间记为CS),递推式如下:C(n)=2CQ)÷2(n>2),C(2)=1,C(I)=O下面求解C()的递推式：Col)=C(2k)=2C(y)+2=2C(2fc1)+2=22C(2fc2)+2+2=2"TC(2)+2fc1+2k-2+2=2k-1C(2)+2k-2=y-2(2)蛮力法中元素比较次数为2(-1),分治法中元素比较次数为冷-2,分治法效率更高。4.利用快速排序原理，将一个数组分为三个部分：负元素、未知元素、正元素。A-ijA+1n负元素未知元素正元素算法如下：算法：NegBeforePos列表重排列输入：A1:用待重排列的列表输出：A口：川重排列后的列表步骤：1. Z<-ljJ<-22. WhileijDo3. IfA<0Then4. z<-+l5. Else6. SWaP(Ai,AUD7j-jT8. EndIf9. EndWhile10. ReturnA算法需一个长度为的数组用来存放所有元素，而每次迭代都会从左向右，缩减一位未知元素空间。因此，算法的时间复杂度为0(”)，空间复杂度为0()。5.(1)蛮力法：蛮力法求解最近对问题，分别计算每一对点之间的距离，然后找出距离最小的点对，为了避免对同点对计算两次距离，只考虑i<的那些点对(Pi出)。复杂度分析：算法的基本操作是计算计算两个点间的欧几里得距离。注意到，在求欧几里得距离时，避免了求平方根操作，因此，算法的基本操作为求平方，其执行次数为：n-lnn-1TT(Tl)=WW2=2W(九-，)=九(九-1)=O(M)i=j=i+i=(2)分治法：用分治法求解最近对问题，就是将集合S分成两个子集Sl和S2,每个子集中分别有方个点。然后在每个子集中递归的求其最近点对，在求出每个子集的最近点对后，关键在于如何实现分治法中的合并步骤。如果S中的最近点对都在Sl中或都在52中，则问题很容易解决。如果这2个点分别在Sl和S2中，则对于SI中任一点P，”中最多只有5个点与它构成最接近点对的候选者，仍需进一步计算才能得到最终结果。时间复杂性可由如下递推式表示：T(n)=2g)+)合并子问题的解的时间f5)=0(l),因此，算法的时间笈杂度为：T(i)=O(nlogn)第3章习题参考答案1.基本思路：直接使用深度优先(DFS)算法以及广度优先算法即可得到给定图的一个连通分量。(1)使用DFS求连通分量算法*DFS/深度优先算法输入：G=<ViE>输出：g图G的一个连通分量步骤：1. g-02. visit®遍历初始顶点3. Initialize(S)将栈S初始化为空4. PUSh(S/)/初始顶点入栈5. WhileS非空Do6. X-Pop(5,)7. g-gu%8. For每一个与X邻接的点卬Do9. Ifw未被遍历过Then10. ViSit(W)11. PUSh(S,卬)将顶点入栈12. EndIf13. EndFor14. EndWhile15. RetUrng(2)使用BFS求连通分量算法:BFS/广度优先算法输入：G=<VfE>输出：g图G的一个连通分量步骤:1. g-02. ViSitW)遍历初始顶点3. InitiaIiZe(Q)初始化队列4. EnqUeUe(Q,u)初始顶点入队5. WhileQ非空Do6. xDequeUe(Q)7. g-g=%8. For每一个与己X邻接的点卬Do9. Ifw未被遍历过Then10. ViSit(W)11. Enqueue(,W)12. EndIf13. EndFor14. EndWhile15. RetUrng2 .参考如下极端情况，其中一个顶点出度为-1,其余顶点出度均为0,最多有(-1)!种拓扑排序结果。3 .第一步：遍历所有顶点，找出入度为0的顶点F并将该顶点入队，将与F连接的顶点E、B、C、G入度减1,同时让F出队，F即为拓扑排序的第1个元素。此时拓扑序列为F0第二步：遍历所有顶点，找出入度为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,B0第五步：遍历所有顶点，找出入度为O的顶点C并将其入队，将与C连接的顶点D入度减1,同时让C出队，C即为拓扑排序的第5个元素。此时拓扑序列为F,E,A,B,C。第六步：遍历所有顶点，找出入度为O的顶点D并将该顶点入队，将与D连接的顶点G入度减1,同时让D出队，D即为拓扑排序的第6个元素。此时拓扑序列为F,E,A,B,C,Do第七步：遍历顶点发现只剩下顶点G,则G为拓扑排序的最后一个元素。因此，该有向图的最终拓扑排序序列为F,E,A,B,C,D,Go第4章习题参考答案(1) (1)基于贪心法的哈夫曼树构造过程如下:合并出现频率最小的字符B和D,并计算合并后的频率;合并出现频率最小的字符E和C并计算合并后的频率;合并出现频率值最小的两个节点，并计算合并后的频率;(2) ABACABAD的编码为OlO1。(3) 010解码为BADEADA。注意：上述答案不唯一，根据构造的哈夫曼树结构不同而不同。2.每次先取剩余硬币中面值最大的硬币，如果不满足条件，再选择次面值最大的硬币。假设有4种硬币，面值分别为50元、10元、5元和1元。如需找零99元，首先选择一个面值不超过99元的最大硬币，即50元，由于慨M=1,因而选择一个面值为50元的硬币，然后从99元中减去50元，剩下49元。再选择一个面值不超过49元的最大硬币，即10元,由于葛=4,因而选择4个面值为10元的硬币，然后从49元中减去40元，剩下9元。如此一直做下去，最终的硬币选择方案为1个50元的硬币、4个10元的硬币、1个5元的硬币和4个1元的硬币。算法：C算nge/求解找零问题的贪心算法输入：找零金额n,非升序的硬币面值山，d2,.,dm）输出：每种面额硬币数量。1:力步骤：1. Fori=1TomDo2. Ci-0初始化每种面额硬币找钱数3. EndFor4. Fori=1TomDo5. CE-用6. nnmoddi取余7. EndFor8. Ifn=0Then9. ReturnC10. Else11. RetUmNOSoliltion/无解3.每次选择元素个数最少的两个列表进行合并排序，从而合并元素时元素比较总次数最少。该算法的步骤如下：（1）找到包含元素最少的两个列表,可采用堆排序算法根据列表中元素个数进行排序，时间复杂度为0（nIogn）。（2）找到元素最少的两个列表后采用算法2.2进行合并，时间复杂度为OSlogTi）。由于每次需通过堆排序查找包含元素最少的两个列表，共执行（n-l）次堆排序，因此该算法的时间复杂度为。（九2Iogn）。第5章习题参考答案1 .动态规划的基本思想：问题的最优解如果可由子问题的最优解推导得到，则可先求解子问题的最优解，再构造原问题的最优解。动态规划要把之前步骤已计算出的结果记录下来，当需要求解原问题的时候，就可使用各子问题（规模更小）的解来构造当前解。动态规划是一个多阶段决策，不是一次性解出多个，而是将多个决策变成多次决策；各个子问题之间并不独立，大规模问题的解可由小规模问题的解进行递推得到（前后有联系）。使用动态规划算法求解问题的基本步骤：（1）分析最优解的性质，刻画其最优子结构特征。（2）递归地定义最优值。（3）根据状态转移顺序，以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，以填表的方式构造最优解。动态规划算法适用的条件或场景：<1）最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。（2）无后效性：某状态以后的过程不会影响以前的状态，只与当前状态有关。（3）重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用。2 .共同点：二者都要求原问题具有最优子结构性质，都是将原问题分而治之，分解成若干个规模较小（小到很容易解决的程序）的子问题，找出子问题与原问题之间的关系（递推式）然后将子问题的解合并，形成原问题的解。不同点：分治法中，分解后得到的子问题相互独立，通常使用递归算法求解。动态规划法中，分解后的子问题相互间有联系（并不独立）、有重叠部分，需要记忆，通常使用迭代方式来求解。3 .（1）各子问题的最优值如下表：物品容量0123456000000001000252525252002025254545301520354045604015203540556050152035405565第一行的值为0,因为物品标号为0（考虑前。个物品的最优值）的情况下（即没有物品）最大价值都是0。第一列的值为0,因为在当前背包容量为。的情况下最大价值都是0。当i=2、户3时，由于广优，物品2可装入背包、也可不装入背包，此时考虑物品2是否装入背包,比较装入或不装物品2时的最大价值:物品2不装入背包时的价值为仇2,3）=25；物品2装入背包时的价值为仇2,3）二仇2-1,4-2）=20;取两者中的最大值max25,20）=25,即此时背包最大价值为25。以此类推，继续迭代直至填满表格。（2）有1个最优子集。最优值为最大价值65,最优解为0,0,1,0,1。（3） 一般来说，可以通过判断表中最后一列的最大值个数来判断（背包问题的最优值只会在最后一列中产生）。4.分析：无论怎样的组合，最后有i枚硬币的面额加起来等于总金额八设最后一枚硬币为的面额为山，这枚硬币之外的前面硬币的面额加起来为/-山。我们不关心前面i-l枚硬币的组合，也不知道山和心可以确定的是，前面的硬币组合成了九-4,且硬币的数量一定减少。因此，可用数组fi来表示用i种不同的硬币去找钱j时所需的最少硬币数。可将问题进行分解：针对第一1项，最后一枚硬币的面额为由处,dm时，所需最少硬币数分别为川田-必+1,fi）-+1/i/-dm+Io因此，/i=mini-l/,fij-di+l）Climtljn）,其中-1/表示不使用第i枚硬币找零时，对金额）进行找钱所需的最少硬币数。算法如下：算法：MinimIInlehange最少硬币找钱输入：Coins1:汨,nHCoins代表硬币面额数组，n为需找钱金额输出：力加1川步骤：LForZ=ITowDo2. W0-03. EndFor4. For/=1TomDo5. For7«-1TonDo6. Ifj<Coins1Then7. 川皿一+88. Else9. 川T+川-C。加10. EndIf11. Ifj<CoinsiThen12. 如I13. Else14. 4WI-min（I/,+fiij-Coinsi）15. EndIf16. EndFor17. EndFor18. Return/m«时间复杂度为5.分析：首先将问题分解，构建递推式。在国际机场i的飞机有两种可能的飞行方式：(1)直接从国际机场飞到中心机场，花费为S+di2;(2)从中间的某一个国际机场转机，花费为s+(c-矶i)2+C()(从j机场飞到中心机场的费用+从i飞到)机场的费用)。因此算法思想为：对各个国际机场到中心机场的距离进行排序，C(i)为飞机只选择前/个国际机场、飞行距离为及时的最小花费，最小花费为。)=!+?2+-di)2+C()(iyn),依次计算列表中的数值C(I),C(2),C()。假如有编号为1、2、3、4的四个机场。类比Floyd算法，构建一个一维数组。数组中存放到当前点到中心机场的距离。使用一个循环来更新这个数组，循环的次数为次。每次循环都比较直飞的距离与当前点经过第/个(li")机场中转的最小花费。经过轮循环，确定最后的结果。算法如下：算法：MinimUmFee飞机飞行最小花费S,d,dz,，dyHs为地面加油费用，4(ii九)为第i个国际机场到中心机场的距离输出：C()距离中心机场最远的国际机场飞到中心机场的最小花费步骤：1. Forz=ITorzDo2. Fory=ITo/?Do3. C(i)-mins+di2,s+(ddi)2+C()4. EndFor5. EndFor6. ReturnC(n)时间复杂度为0(层)。第6章习题参考答案(1)算法思想：按顺序依次从集合中选取元素，将选取元素的值进行相加，如果相加结果大于给定的正整数4则停止选取新元素，回溯到上一个所选择元素，将该元素和其后续选择的元素从已选元素集合中删除，再继续选取该元素的后续元素。重复上述过程，直到选择元素累加值等于给定正数”或已完成对解空间树的遍历，算法终止。如题中示例，在选取元素1、2、5、6后，发现元素累加值大于9,则PI溯到元素5,将元素5及其后续选择的元素从已选元素集合中删除，然后选择元素5的后续元素6,此时元素累加值满足给定正整数启9,从而得到问题的解。元素累加和128106H第7章习题参考答案（1）算法思想：首先应用贪心法求得最优值得上界2+3+5+4=14,每一行的最小元素相加得到最优值的下界2+3+1+4=10,最优值必为1014中的某个值。设当前已对人员1分配了任务，并且花费了成本u,则限界函数可定义为/=u+f第R行的最小值。Jt=r+I假设已经将任务2分配给人员1,任务3分配给人员2,则花费的成本是5,该部分解可能获得的最小成本是5+（l+4）=10o（2）解空间树如下图所示，包含13个节点。人员*一任务4/=2+6+1+4=131.C4.5是一种经典的决策树算法，基本思想是选择具有最大信息增益率的属性作为分裂属性，在构造树的过程中通过剪枝操作降低过拟合风险。给定样本集合。和具有V个离散取值的属性小信息增益率计算公式如下：Gain(D,d)GainRatio(D,a')=川其中，/V()=Z备*log2得，称为属性。的固有值，a的可能取值越多(V越大)，/V()的值通常会越大。表示在第V个分支节点，包含的。中所有取值为小的样本集合。Ga讥(D,)表示用属性。对。进行划分获得的信息增益。给定样本集合。和属性集合4=a1,a2,.tak),C4.5算法步骤如下：(1)创建根节点N。(2)若。中所有样本全属于同一类别G则将N的类别标记为(3)若力为空集或。中所有样本在4上取值相同，则N为叶子节点，且N所属类别为。中样本数量最多的类别。(4)对力中每个属性计算信息增益率GaiziR砒io(D,),并得到最优划分属性(5)根据中每个取值式，为N生成一个叶子节点，若该叶子节点对应样本子集Zr为空，将此节点标记为叶子节点，且类别为。中数量最多的类别；否则，以DU为样本集、aq.为属性集，重复步骤(1)至(5),继续分裂。(6)根据剪枝策略对生成决策树剪枝，输出以N为根节点的决策树。2 .证明：设点X到超平面S上的投影为Xi,则wX+b=0°由于XIX与S的法向量W平行，则wx1x=wx1x=wr(1)此外，基于欧几里得距离，向量的模为其Lz范数，即wx1x=wx1x=wr=wr(2)通常，若范数无下标(w),贝"w2的默认G范数为lw2=IIwII又因为WX1X=W(x1-X)=WtX1-WtX(4)已知wx1+h=0(5)Wxl=b(6)将式(6)代入式(4)中得(7)wx1x=-b-W1X将式(7)代入式(1)中(8)(9)-b-wx=wr_IWTX+引一IIWll3 .SVM本身是个二值分类器。SVM算法最初为二值分类问题而设计，当处理多类问题时，就需要构造合适的多类分类器。目前，构造SVM多类分类器的方法主要有直接法和间接法两类。(1)直接法。直接在目标函数上进行修改，将多个分类面的参数求解合并到一个优化问题中，通过求解该优化问题，“一次性”实现多类分类。这种方法看似简单，但计算复杂度高，实现困难，只适用于小样本分类问题。(2)间接法。通过组合多个二分类器实现多分类器的构造，常见的方法有one-against-one和One-against-all两种。one-against-one方法在每两个类之间都构造一个binarySVM；one-against-all方法训练时依次把某个类别的样本归为一类，剩余样本归为另一类。4 .增量贝叶斯分类器通过学习带有类标签的实例来判断无标签实例的类别，逐步更新分类器的参数。针对新增样本的特点，增量学习主要分为两种，一种是样本集中所有实例都带有类标签，另一种是样本集中只有一部分实例带有类标签。设样本空间S由特征空间/和类别空间C组成，其中，S=svs2sn=(I,C),I=(A1,A2,.fAmfC=c,C2,q,ICl为分类个数，IAil为该属性的取值个数，Aik为属性Ai的第攵个取值。给定训练样本D=Xi,X2,xJ新增实体集T=xx2,XmJo针对所有实例都带有类标签的增量学习，基于共扼分布重新估计分类器的参数：针对只有一部分实例带有类标签的增量学习，需要采用现有的分类器为对每个实例分配类别标签，同时利用其中含有的信息来修正当前的分类器。为了提升训练效率，以贝叶斯模型本身具有增量的学习特性为基础，分别给出增量地学习分类参数和增量地更新已有类别概率的具体实现：(1)增量学习分类参数假设选择(XlG)(X；,=(4p,Gp,.,4Jnp>)加入到训练集D中，此时，根据Dirichlet先验分布特性，重新估计参数,1P(Cr8')=最片若CrCp/)=提分+&，若Cr=G其中，=C+D,分为分类器的原有参数，%=P(Cr8)=笔*。C÷12(2)增量更新已有类别概率通过分析学习参数的变化可知，(x"弓)加入到训练集后，只有与之相关的项的估计变化较大，而与之无关的项变化较小。为此，使用Du(x'cj)估计xZT-xj的类条件概率时，忽略与无关的项的影响，求解方法如下:p(4Me)P©网Eb<xir P"q0)te×j<×,qpc其中，pgCle)是在。下的估计，«匕,夕)是在。1)3,弓)下的估计，且计算只在与候选元素相同的项之间进行。5 .类别不平衡，是指在分类任务中不同类别的训练样本数目差别很大，导致分类结果偏向于较多观测的类，进而影响分类效果。可使用欠采样法直接对训练集中多样本类进行“欠采样”，即去除一些多样本类的样本，使得正例、反例数目接近，然后再进行学习。或使用过采样法，增加一些少数类样本，使得正例、反例数目接近，然后再进行学习。6 .根据个体学习器的生成方式，目前集成学习方法主要分为两大类，第一类是个体学习器之间存在强依赖关系，必须串行生成的序列化方法，代表性方法为“Boosting"；第二类是个体学习器间不存在强依赖关系，可同时生成的并行化方法，代表性方法为“Bagging”和"RandomForest”。(I)Boosting:基分类器以串行方式连接，各基分类器相互依赖。基本思想是将基分类器层层叠加,每一层在训练的时候,对前一层基分类器分错的样本给予更高的权重。测试时，为了降低分类的偏差，根据各层分类器的结果的加权得到最终结果。(2) Bagging：训练过程中各基分类器之间无强依赖，可通过并行训练对每个个体单独学习，学习内容可相同、也可不同。最终决策时，每个个体单独判断，再通过投票方式做出最后的集体决策，旨在降低分类的方差。(3) Bagging：训练过程中各基分类器之间无强依赖，是一个集体决策的过程，可通过并行训练对每个个体单独学习，学习内容可相同、也可不同。最终决策时，每个个体单独判断，再通过投票方式做出最后的集体决策，旨在降低分类的方差。1.从外部指标和内部指标两个方面度量聚类结果好坏。(1)常用的外部指标包括纯度：用聚类正确的样本数除以总的样本数。兰德系数(RandIndex,RI)TP+TNRl=TP+FP+FN+TN其中，TP表示两个同类样本点在同一个簇中的情况数量；尸尸表示两个非同类样本点在同一个簇中的情况数量；刀V表示两个非同类样本点分别在两个簇中的情况数量；/W表示两个同类样本点分别在两个簇中的情况数量。尸值()TPPrecision=TP+FPTPRecall=TP+FNPrecisionRecallFBQ+'2Precision+Recall其中，0=1时，称为FI-ScOre,此时精确率和召回率同样重要。某些情况下，如果认为精确率更重要些，则调整/?的值小于1;如果认为召回率更重要些，则调整0的值大于1。兰德系数和F值越大表示聚类效果越好。(2)常用的内部指标包括误差平方和(SUmOfSqUaledErrors,SSE)。SSE计算公式如下：r/SSE=ZX沏-冗P1=1j=l其中，代表簇的个数，%代表第i个簇中的样本数，Xij为第i个簇中的第/个样本取值，X1为第i个样本平均值。理论上，SSE的值越小越好。该指标的局限性是，只考虑簇内样本的相似度，未考虑不同簇之间的关系。轮廓系数(S)0对于某个样本而言，将该样本与簇内其他样本点间的平均距离定义为簇的内聚度小将该样本与最近簇中所有样本点间的平均距离定义为簇之间的分离度，则该样本轮廓系数的计算公式如下：S_b-amax(,b)对于全体样本的集合而言，所有样本的轮廓系数均值称为聚类结果的轮廓系数。该指标的取值范围是-11,当簇间分离度力远大于内聚度。时，轮廓系数的值近似等于1。所以该指标的值接近1,聚类效果越佳。2 .确定女值大小，核心指标是定义如下的误差平方和:SSE=Jl1pcilp-miI2其中，G是第i个簇，是G中的样本点，叫是G的质心（Ci中所有样本的均值），SSE是所有样本的聚类误差，代表了聚类效果的好坏。手肘法的基本思想是随着聚类数&的增大，样本划分会更精细，每个簇的聚合程度会逐渐提高，SSE会逐渐变小。当a小于真实聚类数时，由于女的增大会大幅增加每个簇的聚合程度，故SSE大幅下降；当女到达真实聚类数时，再增加攵所得到的聚合程度，SSE的下降幅度会骤减，且随着攵值的继续增大趋于平缓。SSE和2的关系图是一个手肘形状，肘部对应的k值就是数据的真实聚类数，这也是该方法被称为手肘法的原因。手肘法的主要步骤包括：（l）h均值算法中每一步都可计算出SSE值，即每个聚类中的点到它们质心的距离的平方；（2）找出SSE曲线下降途中的拐点，当设定的簇数量不断逼近真实簇数量时，SSE呈现快速下降态势，而当设定簇数量超过真实簇数量时，SSE也会继续下降、下降会迅速趋于缓慢，找出SSE曲线下降途中的拐点，即可较好的确定攵值。3 .用于聚类算法的距离计算方法主要有如下几种：（1）闵可夫斯基距离样本Xi=（XmXi2，Xim）和Xj=（Xj,Xj2，X加）之间的闵可夫斯基距离的定义为：dij=（-x比-X及IP）P（P1）（2）马氏距离在标准化欧几里得距离中，即使消除了量纲的影响，若忽略特征之间的相关性，仍可能导致分类错误。给定一个样本集合X,X=（XI,X2,Xi,X；,Xn）的协方差矩阵记为S,样本Xj和X/间的马氏距离定义为：1dij=（xi-xy）S-1（xi-xy）2（3）余弦距离利用闵可夫斯基度量对高维数据进行聚类通常是无效的，因为样本间的距离随着维数的增加而增加。余弦距离测量两个矢量之间的夹角，而不是两个矢量之间的幅值差，适用于高维数据聚类时相似度测量，定义为：d=CosNV）=瑞瑞4 .首先，将所有非数值型数据转换成编码，例如，针对表中的收入属性，可将low、medium、high分别转换为0、1、2。接着，在所有非数值型数据都已转换成编码后，将所有数据构成一个矩阵，矩阵的每一行作为一个特征向量，每一个特征向量代表训练数据集表中的一行数据。最后，通过执行以向量之间的欧式距离为度量的上均值算法，而实现聚类。1 .使用二分类的异常检测，优点是简单、速度快，缺点是当样本不平衡时不能很好地衡量结果。2 .聚类问题是将样本集合按照某种模式相似性度量和聚类算法，无监督地将相似的样本归为一类，属于无监分类(不需先验知识，无指导的分类)，所以聚类问题更注重于分类。异常检测问题旨在检测数据中不符合预期行为的数据，其基本思想是通过数据挖掘方法找出显著不同于其他数据的异常点，所以异常检测问题更注重于找出异常点。聚类是为了发现强相关的簇,而异常值检测则是为了检测与其他对象不强相关的数据点。聚类算法的目标是将数据点划分到某一类中，异常值检测的目标是检测一些不属于任何簇的数据点。没有任何一种聚类算法适用于所有数据集，不同数据集需采用不同的聚类算法。当聚类算法选取不合适时，样本不能创建任何有意义的簇，那么该方法可能会失败。针对高维空间中的稀疏数据，任意两个样本间的距离可能会非常相似，聚类算法可能得不到有意义的簇。3 .生成模型用于异常检测的基本思路是，学习生成网络的潜在特征空间，使潜在特征空间能很好地捕捉到给定数据背后的常态。将生成模型用于异常检测的核心思想是，在生成网络的潜在特征空间中，更能准确地产生正常实例，并且实际实例和生成实例之间的残差定义为异常分数。生成模型用于异常检测基本步骤为：(1)将样本数据输入到生成模型中进行训练,使生成模型能描述样本数据的概率分布。(2)将新实例输入到训练好的生成模型中并输出生成实例，计算新实例与生成实例之间的残差。若新实例服从样本数据的分布，则表明能较好地生成实例，且它们之间的残差很小；否则残差很大，当残差超过一定阈值时，判断该新实例为异常数据。1 .Apriori算法与AprioriTid算法都是利用低阶频繁项集生成高阶候选项集，进而生成所有频繁项集的重复过程。不同之处在于，Apriori算法每次迭代都通过扫描原始数据库计算候选项集的支持度，而APriOriTid算法通过生成k阶Tid表金，存储每个事务中的2维候选项集，以判断k维候选项集是否能成为4维频繁项目集，避免原始数据库的重复扫描。APriOriTid算法引入的女阶Tid表记为金，形式化为Vt.Tid,CGJCG£>,其中，Tid