Py 机器基础及其实践 11

第6章聚类6.1聚类算法简介6.3基于层次的聚类6.2K-means聚类6.5高斯混合聚类6.6本章小结16.4谱聚类6.1聚类算法简介学习基础学习认知能力信息素养高聚类分析是一种无监督学习（UnsupervisedLearning）的算法，它是将数据对象按照相似性划分为多个子集的过程，每个子集称为一个“簇”（Cluster）。假设样本集合为，通过聚类把样本划分到不同的簇，使得相似特征的样本在同一个簇中，不相似特征的样本在不同簇中，最终形成k个不同簇，若各个簇互不相交，即对任意两个簇，则称为硬聚类，否则称为软聚类。同一个簇中的数据相似性高，不同簇中的数据相似性低。6.1聚类算法简介6.1.1聚类算法分类1.基于划分的方法基于划分的方法是基于距离作为判断依据，将数据对象划分为不重叠的簇，使每个数据对象属于且只属于一个簇。首先要确定这些样本点最后聚成几类，然后挑选几个样本点作为初始中心点，通过不断迭代，直到达到“类（簇）内的样本点都足够近，类（簇）间的样本点都足够远”的目标。基于划分的距离算法有K-means、K-medoids、kernelK-means等算法。6.1聚类算法简介6.1.1聚类算法分类2.基于层次的方法基于层次的聚类可分为两种：凝聚法和分裂法。凝聚法采用的是一种自底向上的方法，从最底层开始，每一次通过合并最相似的聚类来形成上一层次中的聚类，当全部数据都合并到一个簇或者达到某个终止条件时，算法结束。分裂法采用的是一种自顶向下的方法，从一个包含全部样本数据的簇开始，逐层分裂为若干个簇，每个簇继续不断往下分裂，直到每个簇中仅包含一个样本数据。6.1聚类算法简介6.1.1聚类算法分类3.基于密度的方法在基于密度的聚类方法中，簇被看成是由低密度区域分隔开来的高密度对象区域。基于密度的聚类方法定义了领域的范围，当临近区域的密度超过某个阈值，就继续聚类，即某区域内的对象个数超过一个给定范围，则将其添加到簇中。基于密度的聚类方法可以对不规则形状的数据样本点进行聚类，同时过滤噪声数据效果比较好。DBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise）就是典型的代表。6.1聚类算法简介6.1.1聚类算法分类4.基于网格的方法基于网络的聚类方法将数据空间划分为由若干有限的网格单元（cell）组成的网格结构，将数据对象集映射到网格单元中，所有聚类操作都在该结构上进行。该方法的处理与数据对象个数无关，只依赖于每个量化空间中每一维上的单元数，处理速度快，但算法效率的提高是以聚类结果的准确率为代价的，经常与基于密度的聚类算法结合使用。6.1聚类算法简介6.1.1聚类算法分类5.基于模型的方法基于模型的方法包括基于概率模型的方法和基于神经网络模型的方法。概率模型主要指概率生成模型，同一“类”的数据属于同一种概率分布，即假设数据是根据潜在的概率分布生成的。高斯混合模型（GaussianMixtureModels，GMM）就是最典型、常用基于概率模型的聚类方法。自组织映射（SelfOrganizedMaps，SOM）则是一种常见的基于神经网络模型的方法。6.1聚类算法简介6.1.2距离度量方法1.闵可夫斯基距离闵可夫斯基距离（MinkowskiDistance）将样本看作高维空间中的点进行距离度量。P和Q的闵可夫斯基距离定义为：6.1聚类算法简介6.1.2距离度量方法2.马氏距离与欧氏距离、曼哈顿距离一样，马氏距离（MahalanobisDistance）常被用于评定数据之间的相似度指标，它可以看作是欧氏距离的修正，修正了欧氏距离中各维度尺度不一致且相关的问题。单个数据点的马氏距离定义为：6.1聚类算法简介6.1.2距离度量方法3.汉明距离汉明距离（HammingDistance）需要将处理的样本数据转换为0和1表示的二进制串，样本中各分量的取值只能是0或1，例如字符串“1110”与“1001”之间的汉明距离为3。对于任意样本特征和，有，其汉明距离为：6.1聚类算法简介6.1.2距离度量方法4.夹角余弦夹角余弦（Cosine）度量将样本看成是高维空间中的向量进行度量，度量方法就是计算两个向量的余弦夹角。对于任意两个n维样本和，其夹角余弦为：6.2K-means聚类假设簇划分为(C1,C2,...,Ck)，则目标就是最小化平方误差：k均值聚类算法描述如下：输入：训练数据集D={x1,x2,…,xN}，聚类个数k。过程：（1）从D中随机选择k个样本作为初始的均值向量：。（2）重复执行以下过程，直至当前均值向量不再更新：①令，其中1≤i≤k。②对于i=1,2,…,N，选择每个样本与各均值向量mj(1≤j≤k)的距离：，根据离均值距离最小的确定其聚类标记：，将样本划入相应的聚类。③对于i=1,2,…,k，计算新的均值向量：，如果新的均值向量与之前的均值向量不相等，则更新，即，否则不更新。6.2K-means聚类西瓜数据集6.2K-means聚类1利用Parzen矩形窗估计概率密度、分类假设聚类个数为k=3，首先随机选取3个样本x3=(0.634,0.264)、x8=(0.437,0.211)、x9=(0.666,0.091)作为初始的均值向量，分别对应于3个聚类C1、C2、C3中的均值向量，初始时每个聚类中元素为空。考察样本x1=(0.697,0.460)，它与当前的均值向量、、距离分别为0.206、0.360、0.370，因此x1被划入聚类C1中，类似地，对x2,x3,…,x30所有样本都执行类似的过程，将每个样本进行了划分，故有：C1={x1,x2,x3,x4,x5,x14,x21,x22,x25,x26,x27,x29}C2={x6,x7,x8,x10,x11,x12,x15,x18,x19,x20,x23,x24,x28,x30}C3={x9,x13,x16,x17}26.2K-means聚类3（3）根据得到的C1、C2、C3更新均值向量：

6.2K-means聚类针对三文鱼和鲈鱼数据的聚类，使用K-means进行聚类。6.3基于层次的聚类──AGNES聚类6.3.1AGNES聚类算法思想AGNES采用自底而上合并聚类簇，每次找到距离最短的两个聚类簇，然后合并成一个大的聚类簇，以此类推，直到全部样本数据合并为一个聚类簇。整个聚类过程就形成了一个树形结构，如图所示。6.3基于层次的聚类──AGNES聚类AGNES聚类算法描述如下：输入：样本数据集D={x1,x2,…,xN}、聚类簇个数k、聚类簇度量函数get_dist。过程：（1）将每个对象看成是一个聚类簇，即对于任意的1≤j≤N，有。（2）根据聚类簇度量函数get_dist确定各个簇之间的距离。（3）设置当前簇个数q=N。（4）当q>k时，重复执行以下步骤：①找出距离最近的两个簇和，合并和：。②对编号为j+1,j+2,…,q的簇重新编号，依次为j,j+1,…,q-1。③对j=1,2,…,q-1，更新聚类簇之间的距离。④根据约束条件，确定新参数的上下界。6.4基于层次的聚类──AGNES聚类AGNES聚类算法在西瓜数据集上的运行结果6.4谱聚类6.4.1谱聚类基本算法思想谱聚类的核心思想源于图论，它将待聚类数据集中的每个样本视为图结构中的一个顶点，所有顶点通过边相互连接，边上的权重表示样本间的相似程度——相似性越高的样本，对应边的权重越大；相似性越低的样本，对应边的权值越小。对于无向图

G=(V,E)

，V表示顶点集合，E表示顶点之间的边的集合，若顶点vi与vj之间有边连接，则wij为两个顶点之间的权重。由于G是无向图，则wij=wji。有向图G如图6-7所示。在图G中，若vi和vj有边的存在，则wij>0；vi和vj不存在边，则wij=0。图6-3所示的有向图G的权值矩阵为W，如图6-8所示。1.相似矩阵图中顶点间的相似度衡量主要基于距离度量，空间中两点距离越近，相似度越高；距离越远，相似度越低，即相似度与距离呈反比关系。以下是3种常见的相似度的衡量方法。（1）近邻法。该方法采用欧式距离计算两个顶点的距离，若距离小于等于阈值，则设定为阈值ϵ，否则设置为0。（2）k近邻法。该方法利用kNN算法思想，取与顶点最近的k个顶点，该顶点与这k个顶点的权重都大于0，但相似矩阵不一定是对称的，这是因为一个点vi在另外一个点vj的k个近邻中，可能vj不在vi的k个近邻中。有两种可以保证所得的相似矩阵对称：（3）余弦相似度。2.度矩阵对于图中任意顶点

vi​，其度数

di​

定义为与该顶点相连的所有边的权重之和，即：

依据先前对顶点度数的定义，能够构建一个n×n的度矩阵D，其形式为D=diag(d1,d2,…,dn)，其中对角线上的元素依次对应各个顶点的度数。例如，对于图6-8所示的邻接矩阵W，把他的每一列相加，放在对角线上，就得到了度矩阵D。如图6-9所示。3.拉普拉斯矩阵基于已得到的相似矩阵

W

与度矩阵

D，通过

L=D−W

可得出拉普拉斯矩阵（Laplacianmatrix）

L，也称为基尔霍夫矩阵。根据图6-8和图6-9，可得L如图6-10所示。拉普拉斯矩阵具备以下特性：（1）对称性。因为相似矩阵

W

与度矩阵

D

均为对称矩阵，由此可得拉普拉斯矩阵

L

同样具有对称性质，即

Lij​=Lji​。（2）半正定。拉普拉斯矩阵中的n个实数特征值都大于或等于零。（3）二次型性质：对于任意向量

f

，根据拉普拉斯矩阵定义可得：6.4.2图的划分谱聚类算法的核心思路，是把聚类任务巧妙转化为图的划分任务。其理想的划分标准，是让切分后不同子图间的边权重总和达到最小，同时子图内部的边权重总和尽可能大。然而，想要精确找到符合这一优化条件的解，属于NP难问题，计算复杂度极高。聚类最终效果的优劣，与具体采用的划分准则紧密相关，像最小割集准则（Minimumcut）、比例割集准则（Ratiocut）、规范割集准则（Normalizedcut）等，都是实践中较为常用的划分准则。若要将无向图G分割为k个彼此独立、没有边相连的子图，可分别用A1、A2、...、Ak

表示每个子图的顶点集合。这些集合需满足两个条件：一是任意两个集合的交集为空（Ai∩Aj=Φ），二是所有集合的并集等于原图的顶点集（A1∪A2∪...∪Ak=V）。进一步地，对于原图顶点集V中任意两个不相交的子集A和B（A∩B=Φ），它们之间的权重进行如下定义：1）最小割集准则。该方法以降低子图间连接紧密程度为目标，核心在于最小化不同子图之间的边权重总和。为量化该优化目标，其构建了对应的代价函数，通过求解此函数的最小值，实现对图的划分，从而完成聚类任务。在该准则下，子图间边权重和越小，意味着各子图的独立性越强，以此达成聚类效果的优化。其代价函数如下：2）比例割集准则。为实现这一目标，比例割集准则构建了专门的目标函数，通过对该函数的优化求解，推动图划分朝着子图间连接稀疏、子图内节点丰富的方向进行，有效规避了因子图规模失衡导致的聚类缺陷。其代价函数为：3）规范割集准则。与比例割集准则思路相近，同样致力于优化图的划分效果。其代价函数为：6.4.3Ncut聚类在谱聚类算法的实际应用中，由于规范割集准则（Ncut）在平衡子图内聚性与子图间分离性方面的卓越表现，成为最常用的图划分准则。最小化Ncut目标函数获取聚类结果的具体方法。谱聚类算法流程：输入：样本集合D={x1,x2,…,xn}，维度p，聚类簇个数k输出：生成簇划分C={c1，c2，…，ck}（1）根据数据集D构造相似矩阵W。（2）根据相似矩阵W得到度矩阵。（3）计算拉普拉斯矩阵L=D-W。（4）对L进行标准化处理，提取

D−1/2LD−1/2

的前

k

个最小特征值及其对应的特征向量f。（5）对特征向量f进行标准化处理，得到n*p的特征矩阵

F，并对矩阵的每一行进行标准化，使每行对应一个

p维特征向量。（6）对F中的每一行作为n个样本输入到kmeans类进行聚类。对于非凸簇形数据，如环形分布，谱聚类优于k-means，如图6-5所示。此外，谱聚类还可通过相似性矩阵的稀疏化，可过滤噪声影响；支持融合文本、图像等多源数据构建联合相似性矩阵，提升聚类鲁棒性。defSpectral_Cluster(data,cluster_n,k):

#谱聚类

W=Get_W(data,k)

D=Get_D(W)

L=Get