大数据分析方法与应用 课件 第4章 聚类算法

大数据分析方法与应用第4章聚类算法4.1聚类的原理目录CONTENTS4.2K-Means聚类4.3

K最近邻算法4.4

模糊C-均值算法第4章聚类算法4.1聚类的原理聚类的原理聚类（Clustering）是指根据“物以类聚”的原理，将本身没有类别的样本聚集成不同的组，这样的一组数据对象的集合叫作簇。聚类算法是数据挖掘和机器学习领域中常见的技术之一，具有广泛的应用。聚类是按照某个特定标准（如距离）把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。也即聚类后同一类的数据尽可能聚集到一起，不同类数据尽量分离。在分类（Classification）中，对于目标数据库中存在哪些类是知道的，要做的就是将每一条记录分别属于哪一类标记出来。4.1聚类的原理

聚类的原理聚类的一般过程01数据特征标准化和降维数据准备03通过对选择的特征进行转换形成新的突出特征特征提取02特征选择04基于某种距离函数进行相似度度量，获取簇聚类05分析聚类结果，如距离误差等聚类结果评估从最初的特征中选择最有效的特征，并将其存储在向量中4.2K-Means聚类

K-Means聚类4.2.1K-Means聚类算法的原理K-Means算法步骤为每个聚类确定一个初始聚类中心，这样就有k个初始聚类中心将样本集中的样本按照最小距离原则分配到最近邻聚类使用每个聚类中的样本均值作为新的聚类中心结束得到k个聚类重复步骤2和3直到聚类中心不再变化输入输出簇的数目k和包含n个对象的数据库k个簇，使平方误差准则最小4.2K-Means聚类

K-Means聚类4.2.1K-Means聚类算法的原理K-Means聚类算法使用误差平方和准则函数来评价聚类性能。给定数据集X，其中只包含描述属性，不包含类别属性。假设X包含k个聚类子集X1,X2,…,Xk；各个聚类子集中的样本数量分别为n1,n2,…,nk；各个聚类子集的均值代表点（也称聚类中心）分别为m1,m2,…,mk。误差平方和准则函数公式为：4.2K-Means聚类

K-Means聚类4.2.1K-Means聚类算法的原理数据对象集合S如下表所示，作为一个聚类分析的二维样本，要求的簇的数量k=2O12345x001.555y20002数据对象集合S1）选择O1(0,2)，O2(0,0)为初始的簇中心，即M1=O1=(0,2)，M2=O2=(0,0)4.2K-Means聚类

K-Means聚类4.2.1K-Means聚类算法的原理2）对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇a.

对于O3：

；

；

因为d(M1,O3)≥d(M2,O3)，故将O3分配给C2。b. 对于O4：

；

因为d(M1,O4)≥d(M2,O4)，故将O4分配给C2。c. 对于O5：

；

因为d(M1,O5)≤d(M2,O5)，故将O5分配给C1。综上，得到新簇C1={O1,O5}，中心为M1=O1=(0,2)；C2={O2,O3,O4}，中心为M2=O2=(0,0)。计算平方误差准则，单个方差为：E1=[(0-0)2+(2-2)2]+[(0-5)2+(2-2)2]=25；E2=[(0-0)2+(0-0)2]+[(0-1.5)2+(0-0)2]+[(0-5)2+(0-0)2]=27.25。总体平均方差是：E=E1+E2=25+27.25=52.254.2K-Means聚类

K-Means聚类4.2.1K-Means聚类算法的原理M1=((0+5)/2,(2+2)/2)=(2.5,2)；M2=((0+1.5+5)/3,(0+0+0+0)/3)=(2.17,0)重复2和3，得到O1分配给C1，O2分配给C2，O3分配给C2，O4分配给C2，O5分配给C1。综上，得到新簇C1={O1,O5}，中心为M1=(2.5,2)和C2={O2,O3,O4}，中心为M2=(2.17,0)。单个方差为：E1=[(0-2.5)2+(2-2)2]+[(2.5-5)2+(2-2)2]=12.5；E2=[(2.17-0)2+(0-0)2]+[(2.17-1.5)2+(0-0)2]+[(2.17-5)2+(0-0)2]=13.1667。总体平均方差是：E=E1+E2=12.5+13.1667=25.667。由上可以看出，第一次迭代后，总体平均方差值由52.25至25.667，显著减小。由于在两次迭代中，簇中心不变，所以停止迭代过程，算法停止。3）计算新簇的中心4.2

K-Means聚类

K-Means聚类4.2.1K-Means聚类算法的原理K-Means算法的主要优点是解决聚类问题的一种经典算法，简单、快速;对处理大数据集，该算法是相对可伸缩和高效率的;k值可以根据实际需求自行调节，以达到控制类簇内样本点数量的目的;当结果簇是密集的，而簇与簇之间区别明显时，它的效果较好.4.2

K-Means聚类K-Means聚类4.2.1K-Means聚类算法的原理K-Means算法的主要缺点在簇的平均值被定义的情况下才能使用，这对于处理符号属性的数据不适用;必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。经常发生得到次优划分的情况。解决方法是多次尝试不同的初始值;它对于“噪声”和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响.4.2

K-Means聚类

K-Means聚类4.2.2K-Means聚类算法在MATLAB中的实现MATLAB提供了专用函数K-Means用于聚类的质心，默认为欧几里得距离，如图所示

MATLAB专用函数K-Means4.2

K-Means聚类K-Means聚类4.2.2K-Means聚类算法在MATLAB中的实现假设给定的数据集X={xm|m=1,2,…,total}，X中的样本用d个描述属性A1,A2,…,Ad（维度）来表示。数据样本xi=(xi1,xi2,…,xid)，xj=(xj1,xj2,…,xjd)，其中xi1,xi2,…,xid和xj1,xj2,…,xjd分别是样本xi和xj对应d个描述属性A1,A2,…,Ad的具体取值。样本xi和xj之间的相似度通常用它们之间的距离d(xi,xj)来表示，距离越小，样本xi和xj越相似，差异度越小；距离越大，样本xi和xj越不相似，差异度越大。欧式距离公式如下：4.2

K-Means聚类

K-Means聚类4.2.2K-Means聚类算法在MATLAB中的实现依据下表中二维数据，通过MATLAB中K-Means算法，令K=3进行聚类。x23-121011540421211222y2010101231-1020212-110

K-Means算法代码示例数据4.2

K-Means聚类

K-Means聚类4.2.2K-Means聚类算法在MATLAB中的实现K-Means算法代码示例14.2

K-Means聚类K-Means聚类4.2.2K-Means聚类算法在MATLAB中的实现K-Means算法代码示例24.2

K-Means聚类

K-Means聚类4.2.2K-Means聚类算法在MATLAB中的实现聚类结果示意由右图可知，K-Means根据距离的远近将数据集中的样本点划分成了三个类簇，并分别用不同的颜色和标记（+，o，*）表示，质心点由“✖”表示。4.3K最近邻算法

K最近邻算法4.3.1K最近邻算法的原理KNN（k-NearestNeighbor），就是K最近邻算法，这是一种常用的监督学习方法。该方法的思路非常简单直观：如果一个样本在特征空间中的K个最相似（即特征空间中最邻近）的样本中的大多数属于某一个类别，则该样本也属于这个类别，即“物以类聚，人以群分”。K最近邻算法概述如图所示K最近邻算法概述图4.3K最近邻算法

K最近邻算法4.3.1K最近邻算法的原理K-Means算法与KNN算法的区别K-Means算法K-Means算法是无监督学习，没有样本的输出K-Means算法有很明显的训练过程，需要训练选择质心KNN算法是监督学习，有分类的输出KNN算法基本没有训练过程，其原理是根据测试集的结果选择距离训练集前k个最近的值KNN算法4.3K最近邻算法

K最近邻算法4.3.1K最近邻算法的原理KNN算法实现过程模型三要素距离度量k值分类决策规则首先，随机选择k个对象，所选择的每个对象都代表一个组的初始均值或初始的组中心值，对剩余的每个对象，根据其与各个组初始均值的距离，将他们分配各最近的（最相似）小组其次，重新计算每个小组新的均值最后，这个过程不断重复，直到所有的对象在K组分布中都找到离自己最近的组4.3K最近邻算法

K最近邻算法4.3.2K最近邻算法在MATLAB中的实现实例基于六条测井曲线，对岩性进行划分，训练集如图所示训练集由3300个深度的测井曲线以及对应的岩性分类组成。则每一个深度看作一个样本，测井曲线的数值作为属性、岩性作为分类结果。367个深度的测井曲线以及对应的岩性分类作为测试集，测试建立的模型性能。基于六条测井曲线数据构建一个KNN模型，用于岩性类型划分数据目的基于测井数据的岩性识别结果示意图4.3K最近邻算法

K最近邻算法4.3.2K最近邻算法在MATLAB中的实现1）数据导入4.3K最近邻算法

K最近邻算法4.3.2K最近邻算法在MATLAB中的实现2）建立使用训练数据集构造KDTree4.3K最近邻算法

K最近邻算法4.3.2K最近邻算法在MATLAB中的实现3）寻找测试集K个邻居使用KDTree结构体MDI，得到n,

n为样本数x邻居数的矩阵，每一行对应一个测试样本，这一行的所有元素代表最邻近的训练集样本点的索引。4.3K最近邻算法

K最近邻算法4.3.2K最近邻算法在MATLAB中的实现4）循环提取测试集样本对应邻居循环提取测试样本的邻居，并统计众数进行投票，得到最终分类结果。使用validate计算最终的准确率分类。其中mode用于计算最近邻点分类向量tempClass中的众数。4.3K最近邻算法

K最近邻算法4.3.2K最近邻算法在MATLAB中的实现5）对K进行优化调参将以上过程封装为函数myKNNCLass，将k作为参数进行调参，由于需要使用众数作为结果，因此邻居数应该选择为奇数。4.3K最近邻算法

K最近邻算法4.3.2K最近邻算法在MATLAB中的实现得到结果取近邻数K=1;此时的准确率为90.9836%取近邻数K=3;此时的准确率为87.9781%取近邻数K=5;此时的准确率为84.153%取近邻数K=7;此时的准确率为84.9727%取近邻数K=9;此时的准确率为82.2404%取近邻数K=11;此时的准确率为80.0546%取近邻数K=13;此时的准确率为79.235%取近邻数K=15;此时的准确率为77.8689%，则最后使用取近邻数1为最好。4.3K最近邻算法

K最近邻算法4.3.3鸢尾花分类案例分析Iris也称鸢尾花卉数据集，是一类多重变量分析的数据集鸢尾花有3个亚属，分别为山鸢尾（Iris-setosa）、变色鸢尾（Iris-versicolor）和维吉尼亚鸢尾（Iris-virginica）数据集包含150个数据样本，分为3类，每类50个数据，每个数据包含4个属性可通过花萼长度，花萼宽度，花瓣长度，花瓣宽度4个属性预测鸢尾花卉分别属于三个亚属中的哪一类列名说明数据类型SepalLength花萼长度FloatSepalWidth花萼宽度FloatPetalLength花瓣长度FloatPetalWidth花瓣宽度FloatClass类别变量。0表示山鸢尾，1表示变色鸢尾，2表示维吉尼亚鸢尾。Int鸢尾花数据集特征4.3K最近邻算法

K最近邻算法4.3.3鸢尾花分类案例分析不同特征描述下鸢尾花分布4.3K最近邻算法

K最近邻算法4.3.3鸢尾花分类案例分析K近邻学习的工作机制给定测试样本，基于某种距离度量找出训练集中与其最靠近的K个训练样本，然后基于这K个“邻居”的信息来进行预测。示例代码如图4.4模糊C-均值算法

模糊C-均值算法4.4.1模糊C-均值算法的原理传统的聚类分析是一种硬划分（CrispPartition），它把每个待辨识的对象严格地划分到某类中，具有“非此即彼”的性质。然而实际上大多数对象并没有严格的属性，它们在性质和类属方面存在着中介性，具有“亦此亦彼”的性质，因此适合进行软划分。Zadeh提出的模糊集理论为这种软划分提供了有力的分析工具，用模糊方法来处理聚类问题，称之为模糊聚类分析。模糊聚类得到了样本属于各个类别的不确定性程度，表达了样本类属的中介性，建立起了样本对于类别的不确定性的描述，能更客观地反映现实世界，从而成为聚类分析研究的主流。在基于目标函数的聚类算法中模糊C均值（FuzzyC-Means,FCM）类型算法的理论最为完善，应用最为广泛。4.4模糊C-均值算法

模糊C-均值算法4.4.1模糊C-均值算法的原理模糊C均值聚类的准则设xi(i=1,2,…,n)是n个样本组成的样本集合，c为预定的类别数目，μj(xi)是第i个样本对于第j类的隶属度函数。用隶属度函数定义的聚类损失函数可以写为：其中，b>1是一个可以控制聚类结果的模糊程度的常数。在不同的隶属度定义方法下最小化聚类损失函数，就得到不同的模糊聚类方法。其中最有代表性的是模糊C均值方法，它要求一个样本对于各个聚类的隶属度之和为1，即（i=1,2,…,n）4.4模糊C-均值算法

模糊C-均值算法4.4.1模糊C-均值算法的原理模糊C均值算法步骤设置目标函数的精度e，模糊指数b（b通常取2）和算法最大迭代次数初始化隶属度矩阵μij和聚类中心vi由公式更新模糊划分矩阵μij和聚类中心vi根据所得到的隶属度矩阵，取样本隶属度最大值所对应类作为样本聚类的结果，聚类结束若目标函数|J(t)-J(t+1)|<e则迭代结束，否则跳转执行步骤3123454.4模糊C-均值算法

模糊C-均值算法4.4.1模糊C-均值算法的原理模糊C均值算法优缺点FCM算法优越于传统硬C均值聚类算法在于隶属度可以连续取值于[0,1]区间，考虑到了样本属于各个类的“亦此亦彼”性，能够对类与类之间样本有重叠的数据集进行分类，具有良好的收敛性。而且FCM算法复杂度低，易于实现。优点如目标函数在迭代过程中容易陷入局部最小、函数收敛速度慢、对初始值、噪声比较敏感等问题。缺点4.4模糊C-均值算法

模糊C-均值算法4.4.2模糊C-均值算法在MATLAB中的实现数据集由400个二维平面上的点组成，这些点构成4个集合，但彼此之间没有明显的极限。数据集示例如图数据集分布4.4模糊C-均值算法

模糊C-均值算法4.4.2模糊C-均值算法在MATLAB中的实现模糊C均值代码4.4模糊C-均值算法

模糊C-均值算法4.4.2模糊C-均值算法在MATLAB中的实现数据集分布4.4模糊C-均值算法

模糊C-均值算法4.4.3用户需求聚类案例分析分析步骤基本思路用电特征提取模型的构建聚类个数确定4.4模糊C-均值算法

模糊C-均值算法4.4.3用户需求聚类案例分析分析步骤1）基本思路模糊C均值聚类分析的基本思路是通过不断优化目标函数来获得各样本点对于所有聚类中心的隶属度，进而确定样本点的类属，最终达到自动对样本数据聚类的目的。4.4模糊C-均值算法

模糊C-均值算法4.4.3用户需求聚类案例分析分析步骤2）模型的构建本文提出的用电需求分类预测模型。首先把数据按不同的行为特征分成n个类，其结果是一组n个具有不同输入输出的数据集。其次对每个数据集建立起相应的模型。最后对预测结果进行汇总。模型框架结构如下图所示。基于模糊C均值聚类的方法建立了居民中期用电需求分类预测模型。4.4模糊C-均值算法

模糊C-均值算法4.4.3用户需求聚类案例分析分析步骤2）模型的构建分类负荷预测模型框架4.4模糊C-均值算法

模糊C-均值算法4.4.3用户需求聚类案例分析分析步骤3）用电特征提取特征提取主要包括聚类属性选择与预测输入变量提取2个部分提取了各用户日均用电量、月电量达到第2档的比例、月电量达到第3档的比例与高温敏感性4组聚类属性所有预测模型的输入变量主要提取出过去7天的用电量与当天的气温共计8个输入属性分档月用电量电价/（元•kWh-1）第1档200kWh以下0.4983第2档201-400kWh0.5483第3档400kWh以上0.7983福建省居民生活用电价格表4.4模糊C-均值算法

模糊C-均值算法4.4.3用户需求聚类案例分析分析步骤4）聚类个数确定最佳聚类个数确定的流程图如图所示。4.4模糊C-均值算法

模糊C-均值算法4.4.3用户需求聚类案例分析分析步骤4）聚类个数确定为了客观地确定合适的聚类个数，本文主要通过计算每一个试探类别数的误差平方（SSE）和MeanIndexAdequacy（MIA）值，通过对比分析找出最优的聚类个数参数。SSE和MIA计算公式如下。4.