机器学习 习题答案汇 胡晓 第1-11章

[在此处键入]第1章习题第1题垃圾分类：可回收物、有害垃圾、厨余垃圾和其他垃圾。重量属性、湿度属性、颜色属性、形状属性、名称属性等。第2题模型性能评估主要是对模型性能优良进行评价，测度模型是否达到任务要求，不同任务通常设计不同评估函数；损失函数也叫代价函数，定义为整个训练集上所有样本误差的平均；目标函数定义为优化函数，等于代价函数+正则化项。第3题监督学习，每个数据都有对应标签。简单说，通过数据+标签训练模型。非监督学习，数据没有对应标签。简单说，通过数据，获得某种潜在函数。强化学习通过在智能体与环境的交互过程中智能体学习策略以达成回报最大化或实现特定目标。第4题自适应学习率、小批量梯度下降、动量第5题奥卡姆剃刀准则：如无必要，勿增实体。（Entitiesshouldnotbemultipliedunnecessarily）罗生门现象(LeoBreiman)：处理问题时，往往各执一词，从而形成有利于自己的处理方式。机器学习中的罗生门现象与岭回归有关，没有唯一解。“没有免费的午餐”定理(NoFreeLunchTheorem，NFL)：在优化算法中任何一个模型函数都不能解决所有问题。如果在一些训练样本上表现好，那么在另一些训练样本上表现不好。第6题0.5166．程序，略。第1题高斯分布对离群点非常敏感，拥挤现象影响明显。参考教材图2.13，采用学生t分布计算相似度。实现同一簇类点(距离较近)聚合更紧密，不同簇类间点更加疏远。第2题xXXXXXT第3题EEE第4题模仿例2.4，详细过程略。第1题略。第2题提示：输入图像，计算直方图，然后估计概率分布曲线。第3题稀少事件指在有限次试验中很少甚至不出现事件。以至于，稀少事件概率为零，实际上并不等于零。为避免这种不准确的概率计算出现，可以采用“m-估计法”。例如0-1事件概率计算PNπ0和π1为专家直觉概率，即凭先验知识，出现0和1的概率应该为π0第1题模仿例题4.1，详细过程略。第2题设包含N个样本的样本集D=x1,y1,x2,y2,…,xN,PPP第3题ball-tree是对kd-tree的改进，在数据维度较大时，kd-tree性能急剧下降，而ball-tree在高维数据情况下具有更好的性能。kd-tree采用二叉树思想，最近邻使用欧式距离（超球体），分割子空间为超方体。显然，分割的超方体与搜索的超球体相交可能性大，而相交空间需要检查；ball-tree，采用两边之和与第三边大小进行判断，分割子空间也是超球体，所以分割区与搜索区相交部分减少。第1题略。第2题优化问题存在约束条件，min拉格朗日函数定义为，F优化问题存在不等式约束条件，min如果满足KKT条件：∂Fx,ββkλmλmgm其拉格朗日函数定义为，F第3题∇第4题∂J∂J第5题∂第1题设∑的特征向量和特征值分别是v和λ，即∑v=1v=ϕ将2代入3得，λϕ所以有，λN第2题设I∈RKKK第3题K第4题K第5题核函数均为正定函数:∀n∈N,i=1第1题略。第2题略。第3题定理：Hoeffding不等式设Z1,ZP第4题Booting是实现集成学习的一种机制；而AdaBoost（AdaptiveBoosting）是实现Boosting机制的一种方式。第5题CART与ID3和C4.5相同点：特征选择、树的⽣成和剪枝三个不揍。ID3和C4.5⽤于分类，CART既可⽤于分类，也可以实现回归。第8章聚类 28.1聚类基本理论 28.1.1聚类的性质 28.1.2相似性测度 38.1.3类簇中心 48.1.4聚类算法评价指标 68.2K均值聚类 118.3层次聚类 138.3.1凝聚筑巢 138.3.2平衡迭代削减层次聚类 158.4密度聚类 188.4.1DBSCAN 188.4.2高斯混合聚类 208.5小结与拓展 21实验八聚类实验 21习题 24第8章聚类聚类是无监督学习算法，其目的是把相似样本归为一类，不相似样本归为另一类。例如将动物聚类，可以根据“腿属性”聚类成无足动物、两腿动物和四腿动物。聚类算法大体可分为均值区域划分聚类、层次聚类、密度聚类和谱聚类算法。层次聚类算法可追溯到1963年，最著名的k均值聚类算法则于1967年被提出，1995年提出的MeanShift算法于1995年用于聚类，谱聚类算法诞生于2000年左右。聚类概念聚类概念相似度测度：欧式距离，曼哈顿距离，闵可夫斯基距离，值差异测量类簇中心：K均值中心、基于密度的中心评价指标：纯度，聚类熵，同质性，兰德指数，轮廓系数算法K均值聚类：k层次聚类：凝聚筑巢，平衡迭代削减层密度聚类：DBSCAN，高斯混合聚类8.1聚类基本理论8.1.1聚类的性质对样本数据集X=x1,x2非空性：X图8.图8.1聚类示意X1X2X3X412全覆盖：k=1K聚类簇Xk中样本在某个属性或某些属性指导下彼此“相似”而物以类聚。异簇之间样本“不相似”而敬而远之。实际上，聚类结果未必全满足上述三个条件。如图8.1所示，如果把图中黑色点当作噪声样本，显然上述三个条件全满足。如果不是噪声点，1号黑色样本点可能同时被划归为X2和8.1.2相似性测度1.相似度测度的性质在聚类算法，样本间相似度通常需要采用两个样本之间的“距离测度(DistanceMetric,DM)”进行衡量。设两个向量x=(x1,x2非负性，距离不能是负数：DMx同一性，具有相同属性向量的两个样本的距离等于零：DMx无向性或对称性，x到y与y到x的距离相等：DMx直递性，三角不等式：DMx2.常见距离测度1)欧氏距离(Euclidean)DM2)曼哈顿距离(Manhattan)DM3)闵可夫斯基距离(Minkowski)DM式中，p=1时，闵氏距离即为曼哈顿距离；图8.2闵可夫斯基图8.2闵可夫斯基距离图形xxlll-11-11(0,0)图8.2显示了二维空间中样本点xi,1,xi,2取不同值时，与原点3.不同量纲间距离测度计算上述距离时，隐含一个假设：各属性分量的量纲(单位)相同。然而如果属性分量的单位不相同，则各分量的分布(期望，方差等特性)可能不同。举个例子：二维样本(身高,体重)，其中身高范围是150~190厘米，体重范围是50~60公斤。现有三个样本：张三(180,50)，李四(190,50)，王五(180,60)。那么张三与李四之间的闵氏距离等于张三与王五之间的闵氏距离，但是身高的10厘米并不一定等价于体重的10公斤。针对量纲不同的属性，通常采用两种方式进行标准化：1)采用每个属性值的标准差进行归一DM式中，sn表示第n2)标准化属性尺度是把所有属性取值缩放到相同区间0,1x=3.值差异度量(ValueDifferenceMetric,VDM)无序属性采用值差异度量(VDM)。在K个类簇中，设ma,x是属性a上取值为x的样本数，ma,x,k表示在第k类样本簇中属性a上取值为x的样本数，则属性a上取值为x1和xVDM设样本的d属性向量中有dc个有序属性，d-dc个无序属性，则样本x,yDM当不同属性重要性不同时，可乘权重系数wi≥0，8.1.3类簇中心类簇中心，又称为簇质心，定义为簇内样本分布中心，如图8.1中每簇的中心点。然而，不同聚类算法定义各有差别，简单分为两种：1.K均值聚类簇中心设聚类结果为X1,X2,…,XK，第k类的样本数量为Nk，则μ通过式8.7计算类簇中心符合最优理论。2.基于密度的类簇中心AlexRodriguez和AlessandroLaio在Science期刊文章中提出：类簇中心周围都是密度比其低的点，同时这些点距离该簇中心的距离相比于其他聚类中心最近。设样本集X=x1,x2对于样本xn，首先计算其局部密度ρn和距离(1)样本xn的局部密度局部密度定义为以xn为中心、ϵ为半径的邻域Nϵ(xn)内样本点的数量(不包括1)硬截断ρ式中，I把邻域半径ϵ称为截断距离。2)高斯平滑截断ρ计算局部密度的目的为了依据密度大小寻找类簇中心，为此希望样本点的局部密度尽可能不相等。显然，高斯平滑截断具有两个优点：(1)具有相同局部密度的概率小；(2)邻域Nϵ(2)距离d当获得X=xnn=1N的密度集ρnn=1N后，则xn的距离dd式中，IdXn=m|ρm>ρn然而，当ρn=maxm∈IdXρd式中，IdX=1,2,⋯,N为样本集图8.3展示了一个决策类簇中心的例子，图中样本点为二维属性向量。图8.3(a)为28个样本点分布。直观上，容易发现点1和点10可作为类簇中心。dρ图8.3(dρ图8.3(a)二维样本空间分布和(b)决策图(ρn(a)(b)尽管ρ9和ρ10相差不大，但是d9和d10却有很大差别：点9属于点1的类簇(把点1作为大腿抱着)，在其附近还有几个更高的局部密度的点，因此d9较小；此外，点26、27和28是孤立的，尽管有相对较高的距离值，但是它们的局部密度值很低。这些点称为异常点，可当作噪声点，也可作为单个点构成的簇。综上所述，只有同时具有较高局部密度和距离的点才是非孤立点的类簇中心。8.1.4聚类算法评价指标如图8.4所示，假设两种聚类算法A1和A2，对X=xC=K=为了表述方便，假设算法A1的聚类结果是期望结果，称每个聚类为一个类；聚类算法A2的结果则需要进行评价，称每个聚类为一个簇。聚类算法A1聚类算法A1聚类算法A2CCCCKKKKK图8.4聚类算法评价指标620324114105791112138171615211819

6324157109111213814171615202118191.纯度(Purity)将每个簇内频数最高的样本类别作为正确的类簇，则每簇纯度定义为，Purity参考算法A1的聚类结果，图8.4聚类算法A2每个簇的纯度分别为：Purity整个聚类的纯度定义为，Purity算法A2聚类后整体纯度为，Purity2.聚类熵针对每一个聚类簇KkEn式中,S表示聚类算法A1的类别数，pks是簇Xk中样本属于类Cs的概率。当Xk图8.4聚类算法A2聚类结果每个簇的熵为，EntropyEntropy3.同质性(Homogeneity)同质性也叫均一性，一个类簇中仅有一个类别的样本，均一性最高。相当于精确率，即被聚类的类簇中正确分类的样本数占该类簇中的样本数的比例,Accuracy假设K5为噪声簇，图8.4聚类算法A21有时，同质性度量还用条件熵定义为h值，h=1-式中，H(KHH(C)=-式中，K表示聚类算法A2的簇数。n总是实例数，ns和nk分别表示类Cs和簇Kk的实例数，ns,kH(C)=-H4.完整性(Completeness)同类别的样本被归类到同一聚类簇中，则满足完整性。相当于召回率，即每个聚类中正确分类的样本数占该类别样本的数量，Recall假设K5为噪声簇，图8.4聚类算法A2结果前41有时，完整性度量也用条件熵定义为h值，c=1-同质性和完整性都是基于两类别划分间的条件熵：已知某一类别划分后，计算另一类别划分的不确定性程度，不确定性越小，两个类别划分越接近，h值或c值就越大。V-Measure，是同质性和完整性的调和平均值(harmonicmean)，定义为v=5.兰德指数和调整兰德指数考虑X=xnn=1N中任意两个互异样本xn和SS：xn和xm在A1和ASSSD：xn和xm在A1属于同类，但在A2属于不同簇,SD=DS：xn和xm在A1属于不同类簇，但在ADS=DD：xn和xm在A1和ADD=用a、b、c和d接下来，结合图8.4给出计算过程：a其中，C23+b、c和SS+DS：同一簇中任取两个样本点来自同类和非同类，a+c=SS+SDa+a+可得a=21,b=27,c=18,d=144进一步制定混淆矩阵(PairConfusionMatrix),同簇非同簇同簇非同簇同类a=b=a+b同类212748非同类c=d=c+d非同类18144162a+cb+d39171基于a、b、(1)兰德指数(RandIndex,RI)RI=(2)JaccardCoefficientJ(3)FewlkesandMallowsindexFM=上述三个系数的范围是0,1，值越大，划分越好。然而，即便随机划分，RI值也未必接近于0。于是1985年Hubert和Arabie提出调整兰德指数：假设聚类算法A1和A2CC⋯CsumsCCCCsumsKnn⋯naK51006Knn⋯naK14005Knn⋯naK00202⋮⋮⋮⋱⋮⋮K00235Knn⋯naK11013sumsbb⋯bsums7644(4)调整兰德指数(AdjustedRandIndex,ARI)ARI=采用调整兰德指数是为了消除随机标签对于兰德指数评估结果的影响。计算ARI的另一种方法是根据列联表(contingencytable)，表中，nks表示同时落入Kk和Cs为此，基于列联表的调整兰德指数计算公式，ARI调整兰德指数范围是-1,1，负数代表聚类结果不好，越接近于1越好。对任意数量的聚类中心和样本数，随机聚类的ARI都非常接近于0。图8.4示列的ARI的计算过程如下：a=a+c=a+ARI上述四个指数越大表明：A1和A26.轮廓系数(SilhouetteCoefficient,SC)xn的SCSC式中，a(xn)：为样本xn到同一簇内其它样本的平均距离，体现了样本xn的簇内不相似度bXk(xn)：样本xn到簇Kk内样本的平均距离，反映样本xnb(xn)=SC(xn)接近1，则说明样本xn聚类合理；SC(xn)所有样本的SC的均值称为聚类结果的轮廓系数。8.2K均值聚类K均值聚类算法(K-means)的基本思路：依据距离相似度将样本集聚类成K个簇，致使簇内样本距离尽可能小，簇间距离尽可能大。1.K均值聚类的基本步骤算法8.1是K均值聚类的伪代码。首先，通常依据对样本集的先验知识选择一个合适的K值。然后，对簇中心初始化处理。随后进入迭代过程，直至收敛。K均值算法通常选择如下几种方式之一作为迭代收敛条件：算法8.1K均值聚类输入：样本集X∈Rd×N,X=过程：1、生成K个中心点μ2、重复下述过程直至收敛依据argmin1≤k≤KMD(xn,重新计算中心点μk修正中心点μk如果收敛,跳出循环至3，否则重复迭代3、终止。输出：聚类结果K聚类中心不再有变化，或者变化很小，即max式中，ε为预设的一个非常小值。各样本到对应簇中心距离之和SumSu类内距离总和SOD不再发生变化。每轮迭代需要计算全部样本点到所有质心的距离，计算量大耗时。ElkanK-Means利用“两边之和大于等于第三边”和“两边之差小于第三边”两个性质减少不必要的距离计算。已知MD(μi,μj)，如果2MD2.K-means++算法在K均值聚类算法中，K个初始中心点对最后的聚类结果和运行时间有很大影响。如果完全随机选择，可能导致算法收敛较慢。K-means++算法对中心点选择进行了优化，优化步骤如下：1)从样本集中随机选择一个点作为第一个聚类中心μ1；2)计算所有样本xn与已选择的聚类中心的距离3)选择一个距离较大样本作为新的聚类中心；4)重复(2)和(3)直到选择出K个聚类质心。3.小批量K均值聚类当样本数量非常大时，如10万以上，传统K-Means算法的计算量非常大，因为每轮迭代都要计算全部样本点到所有质心的距离。即便采用ElkanK-Means，计算量仍然很大。后来有人提出小批量K均值(MiniBatchK-Means)：1)从样本集中随机抽取小批量样本分配给最近的质心；2)更新质心；3)重复1)和2)，直至达到收敛条件。相对于传统K均值算法，小批量K均值得收敛速度提高了，但聚类精确度有所降低。尽管K均值算法普遍使用，但是始终存在K值选择和初始聚类中心点选择问题。为了避免这些问题，可以选择另一种比较实用的聚类算法——层次聚类算法。8.3层次聚类层次聚类(hierarchicalclustering)是基于簇间的相似度的树形聚类算法。一般有两种划分策略：自底向上的凝聚策略和自顶向下的分拆策略。1)凝聚策略。初始时将每个样本点当做一个类簇，然后依据相似度准则合并相似度最大的类簇，直到达到终止条件。2)分拆策略。初始时将所有的样本归为一个类簇，然后依据某种相似度准则找出簇中最不相似的两个样本xi和xx1x2x3x4x5xxxxxx1.000.000.750.500.25相似度图8.5基于凝聚策略的层次聚类示意图凝聚筑巢(AgglomerativeNesting,AGNES)是一种自底向上的层次聚类算法。1.基本步骤1)每个样本作为一个初始聚类簇；2)根据相似度准则将两个最相似簇合并成一个聚类簇；3)重复2)直到满足终止条件。如图8.5所示，由颜色和形状属性构成样本的特征向量。在初始层，每个样本之间存在一定差异，一个样本一个叶节点，共6个簇。由于样本x2和x3在“形状”属性上完全相同，“颜色”属性上也相似，它们的相似度最高，所以把样本x2和x3聚成同一簇。由此，经过第一轮聚类后，得到5个簇：x1、x2,x3、x4、x5和x6；接下来，在这5个簇中合并两个相似度最高的簇x1和x2,x在此聚类算法中，需要考虑两个核心因素：簇间相似度和终止条件。2.簇间相似度依据相似度的不同定义，层次聚类算法主要有单链式、全链式、均链接和非链接四种。(1)单链式(single-linkage)簇类间距离定义为分处两簇的样本间的最小距离，DXiXj图8.6单链式和全链式相似度计算XiXjXiXj(a)(b)(c)如图8.6红色双箭头表示两簇XX图8.6单链式和全链式相似度计算XXXX(a)(b)(c)(2)完全链接聚类(complete-linkage)簇类间距离定义为分处两簇的样本间的最大距离，D如8.6所示蓝色双箭头表示两簇Xi和X(3)均链接聚类(average-linkage)簇间距离定义为分处两簇样本间距离的平均值,D(4)非链接(ward-linkage)目标是每个类簇的方差最小。3.终止条件除了设置固定簇数量终止外，还可以设置距离上限：如果在某一轮迭代中，所有簇间距离都超过该阈值，则停止聚类。在采用这种停止准则时，隐含了一种假设：簇内样本在特征空间上距离很近，而异簇内样本间距离较大。算法8.2AGNES算法输入：样本集X∈Rd×N,X=过程：1、将每个样本作为一个初始簇，即N个初始簇，X2、重复下述计算任意两个簇间相似度，DM合并两个相似度度最大的两个簇，获得新的聚类X1如果满足终止条件,跳出循环至输出；否则重复迭代输出：聚类结果X8.3.2平衡迭代削减层次聚类平衡迭代削减层次聚类(BalancedIterativeReducingandClusteringUsingHierarchies,BIRCH)单次扫描样本集构建聚类特征树(ClusteringFeatureTree,CFT)，随后进行优化(可选)即可完成聚类。运行速度快，适合数据量大、类别数较多的情况。1.聚类特征设用样本集X=x1,x2,⋯,xNCF012345678910107684351029CF1=5,012345678910107684351029CF1CF25个样本：2,6,6个样本：6,5,CF1图8.7聚类特征CF和可加性示列LS=SS是CF中所有样本的特征值平方和,SS显然，聚类特征CF有可加性。图8.7加以说明。对于两个不相交的簇Xi和Xj，已知，CFi=Mi,LSi,(1)簇质心μ(2)簇半径簇中样本到质心的平均距离，R=(3)簇直径簇中两两样本之间距离的平均值，D=一个CF拥有的样本集构成一个簇。CF存储的是簇中所有样本属性的统计和，当给某个簇添加新样本时，这新样本的属性值并入到了CF中，不再需要存储到内存。因此，BIRCH聚类在很大程度上对样本集进行了压缩。2.聚类特征树生成和决策树类似，聚类特征树仍然分为：根节点、中间结点(枝节点)、叶节点。在构造树结构之前，需要提前定义三个重要参数：(1)枝平衡因子β每个内部节点不得多于β个分支，即树中每个节点最多包含β个子节点，CFi,1≤i≤β，CF(2)叶平衡因子λ叶子节点允许包含的最大CF数；(3)空间阈值γ叶节点每个CF的超球体的最大半径，所有类簇的半径不得大于γ。下面简单介绍聚类特征树的生成过程：设样本集X=x1,x2,⋯,xN，β=2，λ=3,γ=τ。如图8.8所示依次按(a)、(CF1x1sc1CF1

γsc2x2x1图8.8聚类特征树的生成过程(a)(b)(c)(CFxscCF

γscxx图8.8聚类特征树的生成过程(a)(b)(c)(d)(e)xscscxxCF

CF

scscscCF

CF

scscCF

CF

CF

CF

图8.8(b)，读入样本x2，判断x2与x1是否同处一个半径γ的超球体。如果是，则把x2也放入sc1，图8.8(c)，读入样本x3时，判断x3是否与sc1处于同一超球体。如果是，则并入CF1。这里假设不是，则需要在根节点新增一个CF2和sc2来容纳图8.8(d)，读入样本x4时，设x4与x3在同一个超球体，将x4并入CF2图8.8(e)，继续读入一系列能被sc1和sc2吸收样本后，读入了一个不能被sc1和sc2吸收的xi。由于β=2，所以，不能在根节点开设新CF3，只能向下分裂。设xi与根节点中的CF2最近，所以在CF2下生成两个分支：CF3和CF4。之前CF2的子簇归入CF3，x4落入CF4图8.9聚类特征树的生成过程——分支(a)(c)scscscscLNscLNCF

CF

RNCF

CF

CF

CF

CF

(b)scscscLNscLNCF

CF

RNCF

CF

CF

CF

scscCF

CF

scscscLNscLNCF

CF

RNCF

CF

CF

CF

scscCF

CF

CF

CF

CF

LNNN继续读入样本能被sc1、sc2或sc3吸收，按上述规则一路走来波澜不惊。之后形成了如图8.9(a)所示的小树CFT，树的高度为2，此树包含一个根节点RN和两个叶节点(LN1和LN2)。请读者注意：这里把下标重新进行了排列，实际样本所属关系与图8.8一致。RN包含2个CF(CF1,CF2)。叶节点LN1拥有2个CF(CF3,图8.9(b)，在读入一个xj，xj距叶节点LN2最近。我们希望xj能被CF5,CF6或CF7接纳。但是，xj不位于这三个子簇下三个超球体之内，按图8.8(c)步骤，需要在LN在LN2所有CF包括新增的CF8，找到两个距离最大的CF作为两个新叶子节点(LN2和LN3)的种子，然后将CF5细心的读者会发现：出现了新问题——根节点出现了3个分支，不符合题设β=2的要求。怎么办？方法与分裂叶节点一样。从而获得如图8.9(c)的树，此时树的高度为3。此树包括1个根节点、2个中间节点(非叶节点：NLN1和NLN2)、3个叶节点(LN1、LN2和LNCF此后，读入样本后，从上到下依次从根节点和中间节点寻找最近分支，最后在叶节点寻找最近的CF。直至扫描完所有样本，建立一棵聚类特征数CFT当扫描完所有样本，在内存建立一棵CFT后，可以考虑进行如下优化：(1).去除一些异常CF，异常CF包含样本点很少，可以将其合并到最近的超球体；(2).利用其它聚类算法所有CF元组进行聚类，以便消除由于样本读入顺序导致的不合理的树结构，以及一些由于节点中CF个数限制导致的树结构分裂；至此，之前介绍的K-Means和BIRCH聚类算法一般只适用于凸样本集。而密度聚类算法既可以适用于凸样本集，也可以适用于非凸样本集。8.4密度聚类密度聚类(Density-BasedSpatialClustering)是一种基于密度的聚类算法。8.4.1DBSCANDBSCAN(density-basedspatialclusteringofapplicationswithnoise)是密度聚类的一个具有代表性算法，通过样本间的可连接性来定义相似性。1.基本概念给定样本集X=x1,称Nϵz=xn∈X|DMz,xn≤ϵ为z的半径ϵ称邻域Nϵz中样本数量ρz=N图8.10中，ρz=6，ρx1=4；如ρz>Xc为XXϵx1x2x3x4x5x6z图8.10核心点、边界点、噪声点和密度直接可达若b∈Xnc⋂Nϵxxxxxxz图8.10核心点、边界点、噪声点和密度直接可达一个边界点可能同时落入多个核心点的Nϵ在X中既不是核心点又不是边界点的点为噪声点，如图8.10中蓝色样本点。由噪声点构成的集合记为X从图8.10所示可知：核心点对应稠密区域内部的点，边界点对应稠密区域边缘的点，而噪音点对应稀疏区域中的点。设xi,xj∈X，如果xi∈Xc,xj∈Nϵxi设有一系列样本x1,x2,…,xk∈i=1,2,…,k-1，则称xk是从x1密度可达的。仔细观察图8.10发现，尽管不可达x6，但是x1密度可达设xi,xj,xk∈X，若xj和xk上述概念归结为：1个概念(密度)、2个参数(邻域半径和密度阈值)、3种类型点(核心点、边界点和噪声点)和4类关系(密度直达、密度可达、密度相连，非密度相连)。若非空集合Xk⊂X，如果它满足：对于xi,xj∈X，(1)最大性：若xi∈(2)连接性：若xi,x则称Xk是X的一个2.密度聚类过程图8.11描绘了密度聚类的基本过程。图中黑色填充点表示未被访问的样本，红色边框点表示已经被访问过，紫色填充点表示为噪声点或临时定位噪声点，蓝色填充点表示已经决策为某簇的样本，绿色填充点表示已经决策为另外一簇的样本。1)从X中随机选择一个未被访问的样本点。如果该点不是核心点(如图8.11中xm)，将该点暂时标注为噪声点，并另外选择一个没有被访问过的样本点；如果该点是核心点(如图8.5中xn)，xmxnxnxxxxxxxxxxxxxxx(a)(b)(c)(d)(e)(f)xxxx(g)(h)(i)图8.11密度聚类的基本过程xxxx(j)算法8.3GMM聚类输入：数据集X∈Rd过程：1、初始化高斯混合模型参数w2、重复#参数估计在当前模型参数下，计算X中所有样本后验概率，p依次估计新的μk#估计后面参数时可以采用之前估计参数。如果达到最大循环次数或LLX3、X#开始聚类4、forn=1,2,…,N计算p将xn聚类到pendfor#结束聚类输出：聚类结果X2)对Xk中所有尚未被处理的样本(如图8.11中xi)。如是核心点，则将Nϵxi中所有样本并入Xk3)重复步骤2)，直至Xk不再有未被处理的样本4)设置k=k+1，重复步骤1)~3)，直到8.4.2高斯混合聚类与K均值聚类相似，高斯混合模型(Gaussianmixturemodel,GMM)聚类将样本聚类到子簇Xk,k=1,2,…,K。K均值基于距离聚类对圆形分布的样本聚类效果好，而在3.4-3.5我们已经介绍了学习高斯混合模型的算法。一旦获得高斯混合模型，对X=x1,x2,⋯,xN，即可按算法8.38.5小结与拓展聚类是一种经典无监督学习方法，通过对无标记训练样本的学习，发掘和揭示数据集本身潜在的结构与规律，即不依赖于训练数据集的类标记信息。聚类算法与表征学习结合以便有效挖掘出实例间的复杂关系。近年来，随着人工神经网络的发展，深度聚类(DeepClustering)也成为了聚类算法中的研究方向。利用神经网络强大的学习能力实现优化表征学习和聚类。实验八聚类实验1．实验目的1.1了解Scikit-learn提供的聚类算法相关函数；1.2掌握采用python对聚类算法(k-mean和高斯混合模型)编程能力。2．实验环境平台：Windows/Linux；编程语言：python3.实验内容3.1常见聚类算法性能比较实验；3.2手写数字聚类实验。4.实验步骤4.1聚类算法性能比较实验首先，用make_blobs生成4个类中心的高斯分布数据：[-1,-1],[-1,1],[1.5,-0.5],[1.5,0.5]。代码8.1环形数据生成代码importscipy.ioassiodefThreeCircles():

path=u'cluster_data/ThreeCircles.mat'

ThreeCircles=sio.loadmat(path)['ThreeCircles']

ThreeCircles=ThreeCircles[0::代码8.1环形数据生成代码importscipy.ioassiodefThreeCircles():

path=u'cluster_data/ThreeCircles.mat'

ThreeCircles=sio.loadmat(path)['ThreeCircles']

ThreeCircles=ThreeCircles[0::3,:]#每隔3行取一个数据

data=ThreeCircles

data=np.array([data[:,1],data[:,2],data[:,0]]).T#list与array互换

returndataX,y=make_blobs(n_samples=1000,n_features=2,centers=[[-1,-1],[-1,1],[1.5,-0.5],[1.5,0.5]], cluster_std=[[0.45,0.2],[0.25,0.5],0.25,0.3],random_state=10)然后，分别用如下聚类算法进行聚类，KMeans(n_clusters=n_classes,random_state=random_state).fit_predict(X)GaussianMixture(n_components=n_classes,covariance_type="spherical",max_iter=50,random_state=random_state).fit_predict(X)AgglomerativeClustering(linkage="average",n_clusters=n_classes).fit_predict(X)Birch(n_clusters=n_classes,branching_factor=5,threshold=0.5).fit_predict(X)DBSCAN(eps=0.4,min_samples=9).fit_predict(X)在图8.12第一列中，为上述5种聚类算法对这4类高斯分布数据的聚类结果。AGNES和DBSCAN把分布有重叠的样本聚类成了一类。最后，通过上述算法(BIRCH除外)对三个圆形分布数据进行聚类比较，如图8.12的第二列。AGNES和DBSCAN能把圆环分布数据准确聚类，而kmeans和GMM却不具备此聚类能力。本实验代码相对简单，读者可以应用以往实验自行编写。这里附上环形数据生成代码。图8.12几种算法聚类结果比较图8.12几种算法聚类结果比较linkage=’average’linkage=’single’4.2手写数字聚类算法性能分析首先，用PCA将64维数据降维成2维，手写数字数据相关代码见实验五。reduced_data=PCA(n_components=2).fit_transform(data)然后，用k-means++对降维后的数据进行聚类，class

sklearn.cluster.KMeans(n_clusters=8,

*,

init='k-means++',

n_init=10,

max_iter=300,

tol=0.0001,

verbose=0,

random_state=None,

copy_x=True,

algorithm='lloyd')init{‘k-means