Pattern Recognition & artificial IntelligenceLecture 5: 聚类算法(一)主要内容聚类的定义聚类算法分类典型聚类算法讲解聚类的定义聚类的定义典型的非监督式机器学习数据类别不被事先标识通过学习模型推断出数据的一些内在结构，进而进行聚类。聚类算法分类聚类算法分类划分方法：首先得到初始的K个划分的集合。如K-平均、K-中心点、CLARANS以及对它们的改进。层次方法：创建给定数据对象集合的一个层次性的分解。根据层次分解的过程可以分为凝聚(自底向上)或分裂(自顶向下)。基于密度的方法：根据密度的概念来聚类对象，如DBSCAN、DENCLUE、OPTICS。聚类算法分类基于网格的方法：首先将对象空间量化为有限数目的单元，形成网格结构，然后在网格结构上进行聚类，如STING、CLIQUE、WaveCluster。基于模型的方法：为每个簇假设一个模型，发现数据对模型的最好匹配，如COBWEB、CLASSIT，GCM, AutoClass, SOM。基于降维的方法：如Spectral clustering，Ncut等聚类算法分类类别算法分裂/划分方法K-MEANS(K-平均)、K-MEDOIDS算法(K-中心点)、CLARANS算法(基于选择的方法)层次法BIRCH算法(平衡迭代规约和聚类)、CURE算法(代表聚类)、CHAMELEON算法(动态模型)基于密度的方法DBSCAN算法(基于高密度连接区域)、OPTICS算法(对象排序识别)、DENCURE算法(密度分布函数)基于网格的方法STING算法(统计信息网格)、CLIQUE算法(聚类高维空间)、WAVE-CLUSTER算法(小波变换)基于模型的方法统计学方法、神经网络方法基于降维的方法Spectral clustering，Ncut典型聚类算法讲解 -----基于划分的聚类算法划分聚类法 – K-meansQ1：k是什么？A1：k是聚类算法当中类的个数。 Q2：means是什么？A2：means是均值算法。Summary：k-means是采用均值算法把数据分成K个类的算法！划分聚类法 – K-means算法概述k-means算法，亦称k-均值或k-平均，是一种基于质心的启发式聚类算法。基本思想：通过迭代把数据集划分为不同的类别(或称簇)，使得评价聚类性能的准则函数达到最优，使得每个聚类类内紧凑，类间独立。对于连续型属性具有较好的聚类效果，不适合处理离散型属性。划分聚类法 – K-means准则函数 平方误差和准则函数 即SSE(sum of the squared error) SSE是数据库中所有对象的平方误差总和，其中 为数据对象； 为簇 的平均值。 这个准则函数使得生成的簇尽可能的紧凑和独立。1. 随机抽取k个点作为初始聚类的中心，由各中心代表各聚类2.计算所有点到这k个中心的距离，并将点归到离其最近的聚类3. 调整聚类中心，即将聚类的中心移动到聚类的几何中心(即平均值)划分聚类法 – K-means算法流程4.重复第2、3步直到聚类的中心不再移动，此时算法收敛划分聚类法 – K-meansSimple Example选择初始中心点各点划分进最近聚类调整聚类中心迭代计算中心点收敛！划分聚类法 – K-means算法实现的具体流程划分聚类法 – K-means算法特点：影响主要因素一般采用欧氏距离、曼哈顿距离或者名考斯距离的一种，作为样本间的相似性度量输入数据及k值的选择初始中心点距离度量影响聚类效果！Factors划分聚类法– K-means不足：k-means算法只有在簇的平均值被定义的情况下才能使用。k-means算法的不足之处在于它要多次扫描数据库。k-means算法只能找出球形的类，而不能发现任意形状的类。初始质心的选择对聚类结果有较大的影响。k-means算法对于噪声和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。划分聚类法 – K-means应用实例问题描述： 如图所示，一只遥望大海的小狗。此图为100×100像素的JPG图片，每个像素可以表示为三维向量(分别对应红绿蓝三基色)。 要求使用k-means算法，将图片分割为合适的背景区域(三个)和前景区域(小狗)。划分聚类法 – K-meansMatlab程序实现function [M, j, e] = kmeans(X, K, Max_Its)[N,D]=size(X);I=randperm(N);M=X(I(1:K),:);Mo = M;for n=1:Max_Its for k=1:K Dist(:,k) = sum((X - repmat(M(k,:),N,1)).^2,2)'; end [i, j]=min(Dist, [], 2); f