K-means聚类

K-MeansclusteringPatternRecognition聚类Clustering2/33聚类簇（Cluster）:一个数据对象的集合•聚类–把一个给定的数据对象集合分成不同的簇，并使簇与簇之间的差距尽可能大，簇内数据的差异尽可能小；•聚类是一种无监督分类法:没有预先指定的类别•典型的应用–作为一个独立的分析工具，用于了解数据的分布；–作为其它算法的一个数据预处理步骤；与分类的区别分类(CategorizationorClassification)就是按照某种标准给对象贴标签(label)，再根据标签来区分归类。简单地说，聚类是指事先没有“标签”而通过某种成团分析找出事物之间存在聚集性原因的过程。区别是，分类是事先定义好类别，类别数不变。3/33发现客户的特征•客户分割（segmentation）是一种发现用户特性的方法。•将一个基于数据的客户信息分组：从而给你一个客户信息的概况，这可以直接转化为增加客户的经营策略。4/33聚类问题的数学描述•给定数据集合V，根据数据对象间的相似程度将数据集合分成组，并满足：则该过程称为聚类。Ci称为簇。1{|1,2,...,}jiijkiiCjkCVCCCV5/33基本概念•Clustercenter•Clustersize•Clusterdensity•Clusterdescriptions•一个好的聚类方法要能产生高质量的聚类结果—簇，这些簇要具备以下两个特点：–高的簇内相似性–低的簇间相似性6/33聚类需求•可伸缩性•能够处理不同类型的属性•能发现任意形状的簇•在决定输入参数的时候，尽量不需要特定的领域知识；•能够处理噪声和异常•对输入数据对象的顺序不敏感•能处理高维数据•能产生一个好的、能满足用户指定约束的聚类结果•结果是可解释的、可理解的和可用的7/33计算对象之间的相异度•通常使用距离来衡量两个对象之间的相异度。•常用的距离度量方法有:明可夫斯基距离（Minkowskidistance）:其中s=(xs1,xs2,…,xsq)和t=(xt1,xt2,…,xtq)是两个q维的数据对象,p是一个正整数。当p=1时,d称为曼哈坦距离（Manhattandistance）pqjptjxsjxstd1||||...|22||11|tqxsqxtxsxtxsxstd8/33SimilarityandDissimilarity•当q=2时,d就成为欧几里德距离:–距离函数有如下特性：•d(s,t)0•d(k,k)=0•d(s,t)=d(t,s)•d(s,t)d(s,k)+d(k,t)•可以根据每个变量的重要性赋予一个权重)2||...2|22|2|11(|tqxsqxtxsxtxsxstd9/33聚类算法•K-meansalgorithms•Hierarchicalclusteringmethods•Kohonenneuralnetwork(self-organizingmap)•其他10/33k-means算法算法概述算法实现性能分析改进算法应用实例11/33算法概述——概念描述Summary：k-means是采用均值算法把数据分成K个类的算法！Q1：k是什么？A1：k是聚类算法当中类的个数。Q2：means是什么？A2：means是均值算法。12/33k-means算法，亦称k-均值或k-平均，是一种基于质心的启发式聚类算法。最早想法由HugoSteinhaus于1957年提出,名称的出现则是在1967年；该算法最常见的形式是采用被称为劳埃德算法（LloydAlgorithm）的迭代式改进探索法。StuartLloyd于1957年在Bell实验室给出了标准算法；StuartLloyd于1982年正式发表在IEEETransactionsonInformationTheory基本思想：通过迭代把数据集划分为不同的类别（或称簇），使得评价聚类性能的准则函数达到最优，使得每个聚类类内紧凑，类间独立。对于连续型属性具有较好的聚类效果，不适合处理离散型属性。算法概述——概念描述13/33•平方误差和准则函数即SSE（SumoftheSquaredError）SSE是数据库中所有对象的平方误差总和，其中：p为数据对象；mi为簇Ci的平均值。这个准则函数使得生成的簇尽可能的紧凑和独立。算法概述——准则函数kiCpiimpSSE1214/33算法概述——基本流程1.随机抽取k个点作为初始聚类的中心，由各中心代表各聚类2.计算所有点到这k个中心的距离，并将点归到离其最近的聚类3.调整聚类中心，即将聚类的中心移动到聚类的几何中心（即平均值）4.重复第2、3步直到聚类的中心不再移动，此时算法收敛15/33算法概述——简单算例迭代计算中心点收敛！选择初始中心点各点划分进最近聚类调整聚类中心16/33算法概述——主要因素（1）初始中心点输入数据及k值的选择距离度量Factors影响聚类效果！一般采用曼哈顿距离、欧氏距离或者明可夫斯基距离的一种，作为样本间的相似性度量17/331.凭检验直观选择k2.按密度大小选代表点确定k3.使距离度量方法值最小的k4.最大最小距离法确定(阈值比例系数θ，0θ1)1.随机选点的方法2.凭借经验选取有代表性的点3.基于取样的方法确定4.基于密度的选择方法算法概述——主要因素（2）初始中心点选择k的值这样的依赖性导致聚类结果的不稳定，且容易陷入局部最优18/33V19/33算法实现——伪代码•初始化：随机选择K个聚类均值mj，j=1,...,K;•循环，直到K个均值都不再变化为止；•Cj=,j=1,...K•fori=1ton•endfor•更新K个聚类的均值：•输出：聚类{C1,...,CK}}{,minarg1ikkjikjxCCmxkjCxjjKjxnm,...,1,120/33应用实例——图像分割21/33应用实例——图像分割22/33优缺点性能分析主要优点1.思想简单易行2.时间杂度接近线性3.对大数据集，具有高效性和可伸缩性主要缺点1.依赖于初始均值的选择2.须事先给定聚类数k值3.对噪声和孤立数据敏感23/33K-均值算法局限24/33算法改进——k-modes算法k-means算法是在数据挖掘领域中普遍应用的聚类算法，它只能处理数值型数据，而不能处理分类属性型数据。k-modes算法是在数据挖掘中对分类属性型数据的采用的聚类算法。k-modes算法是对k-means算法的扩展。例如表示人的属性有：姓名、性别、年龄、家庭住址等属性。k-modes算法就能够处理分类属性型数据。k-modes算法采用差异度来代替k-means算法中的距离。k-modes算法中差异度越小，则表示距离越小。一个样本和一个聚类中心的差异度就是它们各个属性不相同的个数，不相同则记为一，最后计算一的总和。这个和就是某个样本到某个聚类中心的差异度。该样本属于差异度最小的聚类中心。25/33算法改进—k-modes算法(续)K-modes算法：实现对离散数据的快速聚类，同时保留了k-means算法的效率。针对分类属性的度量和更新质心的问题改进如下：1.度量记录之间的相关性的计算公式是比较两记录之间，属性相同为0，不同为1，并把所有相加，值越大越不相关。2.更新modes，使用一个簇的每个属性出现频率最大的属性值作为簇的属性值。26/33算法改进——k-prototype算法K-prototype算法：可对数值和分类属性混合数据进行聚类，定义了一个对数值与离散属性都计算的相异性度量标准。结合了k-means和k-modes算法，针对混合属性，解决两个核心问题如下：1.度量具有混合属性的方法是，数值属性采用k-means方法得到为P1，分类属性采用k-modes方法得到P2，那么度量值为P1+aP2。其中，a是权重，若认为分类属性重要则增加a，否则减少a，当a=0时即只有数值属性。2.更新簇的中心的方法，也是结合k-means和k-modes的更新方法。27/33算法改进——k-中心点算法K-中心点算法为解决k-means算法对于孤立点敏感的问题，采用簇中的中心点而非平均值作为参照点。仍然基于最小化所有对象与其参照点之间的相异度之和的原则来执行聚类。28/33算法改进——二分k-means算法二分k-means算法：为了克服k-means算法收敛于局部的问题。首先将所有的点作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续划分，选择哪个簇进行划分取决于对其划分是否可以最大程度降低SSE值。伪代码如下：•将所有的点看成一个簇•Repeat从簇表中取出一个簇（对选定的簇进行多次二分实验）fori=1to实验次数do试用基本K均值（k=2），二分选定的簇endfor从实验中选取总SSE最小的两个簇添加到簇表中•Until簇表中包含K个簇29/33层次聚类•层次聚类（hierarchicalclustering）方法把数据组织成若干簇，并形成一个相应的树状图进行聚类。•假设有N个待聚类的样本，对于层次聚类来说，基本步骤就是：1、（初始化）把每个样本归为一类，计算每两个类之间的距离，也就是样本与样本之间的相似度；2、寻找各个类之间最近的两个类，把他们归为一类（这样类的总数就少了一个）；3、重新计算新生成的这个类与各个旧类之间的相似度；4、重复2和3直到所有样本点都归为一类，结束。30/33层次聚类31/33•基于密度的聚类•基于网格的聚类•基于模型的聚类•模糊聚类等选择哪种聚类方法，需要考虑实际的应用需求、簇的类型与特征、数据的特性、数据质量、数据集的规模（样本个数、样本属性个数）等因素。其它聚类方法32/33THEENDThankyou.