聚类(K-means)

ResearchCenteronFictitiousEconomy&DataScience,ChineseAcademyOfSciences中国科学院虚拟经济与数据科学研究中心数据挖掘与商务智能田英杰研究员2聚类Clustering3聚类簇（Cluster）:一个数据对象的集合•聚类–把一个给定的数据对象集合分成不同的簇，并使簇与簇之间的差距尽可能大，簇内数据的差异尽可能小；•聚类是一种无监督分类法:没有预先指定的类别•典型的应用–作为一个独立的分析工具，用于了解数据的分布；–作为其它算法的一个数据预处理步骤；与分类的区别4发现客户的特征•客户分割（segmentation）是一种发现用户特性的方法。•将一个基于数据的客户信息分组：从而给你一个客户信息的概况，这可以直接转化为增加客户的经营策略。新浪微博兴趣圈自动挖掘（）5聚类问题的数学描述•给定数据集合V，根据数据对象间的相似程度将数据集合分成组，并满足：则该过程称为聚类。Ci称为簇。1{|1,2,...,}jiijkiiCjkCVCCCV6基本概念•Clustercenter•Clustersize•Clusterdensity•Clusterdescriptions•一个好的聚类方法要能产生高质量的聚类结果—簇，这些簇要具备以下两个特点：–高的簇内相似性–低的簇间相似性7聚类需求•可伸缩性•能够处理不同类型的属性•能发现任意形状的簇•在决定输入参数的时候，尽量不需要特定的领域知识；•能够处理噪声和异常•对输入数据对象的顺序不敏感•能处理高维数据•能产生一个好的、能满足用户指定约束的聚类结果•结果是可解释的、可理解的和可用的8计算对象之间的相异度•通常使用距离来衡量两个对象之间的相异度。•常用的距离度量方法有:明考斯基距离（Minkowskidistance）:其中i=(xi1,xi2,…,xip)和j=(xj1,xj2,…,xjp)是两个p维的数据对象,q是一个正整数。当q=1时,d称为曼哈坦距离（Manhattandistance）qqppqqjxixjxixjxixjid)||...|||(|),(2211||...||||),(2211ppjxixjxixjxixjid9SimilarityandDissimilarity•当q=2时,d就成为欧几里德距离:–距离函数有如下特性：•d(i,j)0•d(i,i)=0•d(i,j)=d(j,i)•d(i,j)d(i,k)+d(k,j)•可以根据每个变量的重要性赋予一个权重)||...|||(|),(2222211ppjxixjxixjxixjid10聚类算法•K-meansalgorithms•Kohonenneuralnetwork(self-organizingmap)•Hierarchicalclusteringmethods•其他k-means算法算法概述算法实现性能分析改进算法应用实例算法概述——概念描述Summary：k-means是采用均值算法把数据分成K个类的算法！Q1：k是什么？A1：k是聚类算法当中类的个数。Q2：means是什么？A2：means是均值算法。k-means算法，亦称k-均值或k-平均，是一种基于质心的启发式聚类算法。发明于1956年，该算法最常见的形式是采用被称为劳埃德算法（LloydAlgorithm）的迭代式改进探索法。基本思想：通过迭代把数据集划分为不同的类别（或称簇），使得评价聚类性能的准则函数达到最优，使得每个聚类类内紧凑，类间独立。对于连续型属性具有较好的聚类效果，不适合处理离散型属性。算法概述——概念描述平方误差和准则函数即SSE（sumofthesquarederror）SSE是数据库中所有对象的平方误差总和，其中为数据对象；为簇的平均值。这个准则函数使得生成的簇尽可能的紧凑和独立。算法概述——准则函数pimiC算法概述——基本流程1.随机抽取k个点作为初始聚类的中心，由各中心代表各聚类2.计算所有点到这k个中心的距离，并将点归到离其最近的聚类3.调整聚类中心，即将聚类的中心移动到聚类的几何中心（即平均值）4.重复第2、3步直到聚类的中心不再移动，此时算法收敛算法概述——简单算例迭代计算中心点收敛！选择初始中心点各点划分进最近聚类调整聚类中心算法概述——主要因素（1）初始中心点输入数据及k值的选择距离度量Factors影响聚类效果！一般采用欧氏距离、曼哈顿距离或者名考斯距离的一种，作为样本间的相似性度量1.凭检验直观选择k2.按密度大小选代表点确定k3.使距离度量方法值最小的k4.最大最小距离法确定1.随机选点的方法2.凭借经验选取有代表性的点3.基于取样的方法确定4.基于密度的选择方法算法概述——主要因素（2）初始中心点选择k的值这样的依赖性导致聚类结果的不稳定，且容易陷入局部最优算法实现——具体流程1{x}Nnn12,,,kccc2(i)argminijjlabelxc:(s),1,2,,jsjslabelcXNjkfunction[M,j,e]=kmeans(X,K,Max_Its)[N,D]=size(X);I=randperm(N);M=X(I(1:K),:);Mo=M;forn=1:Max_Itsfork=1:KDist(:,k)=sum(X-repmat(M(K:),N,1)).^2,2)’;end[I,j]=min(Dist,[],2);fork=1:Kifsize(find(j==k))0M(k,:)=mean(X(find(j==k),:))endend算法实现——Matlab程序Z=zeros(N,K);form=1:NZ(m,j(m))=1;ende=sum(sum(Z.*Dist)./N);fprintf(‘%dError=%f\n’,n,e);Mo=M;end算法实现——Matlab程序应用实例——图像分割问题描述：如图所示，一只遥望大海的小狗。此图为100×100像素的JPG图片，每个像素可以表示为三维向量（分别对应红绿蓝三基色）。要求使用k-means算法，将图片分割为合适的背景区域（三个）和前景区域（小狗）。应用实例——图像分割（续）注：最大迭代次数为20次，需运行多次才有可能得到较好的结果。分割后的效果优缺点性能分析主要优点1.思想简单易行2.时间杂度接近线性3.对大数据集，具有高效性和可伸缩性主要缺点1.依赖于初始均值的选择2.须事先给定聚类数k值3.对噪声和孤立数据敏感25K-均值算法局限算法改进——k-modes算法K-modes算法：实现对离散数据的快速聚类，同时保留了k-means算法的效率。针对分类属性的度量和更新质心的问题改进如下：1.度量记录之间的相关性的计算公式是比较两记录之间，属性相同为0，不同为1，并把所有相加，值越大越不相关。2.更新modes，使用一个簇的每个属性出现频率最大的属性值作为簇的属性值。算法改进——k-prototype算法K-prototype算法：可对数值和分类属性混合数据进行聚类，定义了一个对数值与离散属性都计算的相异性度量标准。结合了k-means和k-modes算法，针对混合属性，解决两个核心问题如下：1.度量具有混合属性的方法是，数值属性采用k-means方法得到为，分类属性采用k-modes方法得到，那么度量值为其中，是权重，若认为分类属性重要则增加，否则减少，当时即只有数值属性。2.更新簇的中心的方法，也是结合k-means和k-modes的更新方法。1P2P12aPPaaaa=0算法改进——k-中心点算法K-中心点算法为解决k-means算法对于孤立点敏感的问题，采用簇中的中心点而非平均值作为参照点。仍然基于最小化所有对象与其参照点之间的相异度之和的原则来执行聚类。算法改进——二分k-means算法二分k-means算法：为了克服k-means算法收敛于局部的问题。首先将所有的点作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续划分，选择哪个簇进行划分取决于对其划分是否可以最大程度降低SSE值。伪代码如下：将所有的点看成一个簇Repeat从簇表中取出一个簇（对选定的簇进行多次二分实验）fori=1to实验次数do试用基本K均值（k=2），二分选定的簇endfor从实验中选取总SSE最小的两个簇添加到簇表中Until簇表中包含K个簇30层次聚类层次聚类（hierarchicalclustering）方法把数据组织成若干簇，并形成一个相应的树状图进行聚类。假设有N个待聚类的样本，对于层次聚类来说，基本步骤就是：•1、（初始化）把每个样本归为一类，计算每两个类之间的距离，也就是样本与样本之间的相似度；•2、寻找各个类之间最近的两个类，把他们归为一类（这样类的总数就少了一个）；•3、重新计算新生成的这个类与各个旧类之间的相似度；•4、重复2和3直到所有样本点都归为一类，结束层次聚类•基于密度的聚类•基于网格的聚类•基于模型的聚类•模糊聚类等选择哪种聚类方法，需要考虑实际的应用需求、簇的类型与特征、数据的特性、数据质量、数据集的规模（样本个数、样本属性个数）等因素。其它聚类方法33基于密度的聚类•基于密度的聚类方法与k-means算法使用簇的中心不同，它使用密度的概念。这种聚类方法根据样本点周围的密度不断增长聚类，这就克服了基于距离的算法只能发现凸形分布数据聚类的缺点。•基于密度的聚类方法首先计算一个区域中的点的密度，如果大于某个阈值就把它添加到相近的聚类中去，主要算法包括DBSCAN算法和OPTICS算法（DBSCAN的扩展算法）等。34基于密度的聚类