《大数据处理与智能决策 》课件_6-聚类算法概论.ppt

1、什么是聚类？什么是聚类？“物以类聚物以类聚”，将数据分组成为多个类。在同一个类，将数据分组成为多个类。在同一个类内对象之间具有较高的度，不同类之间的对象差别较大。内对象之间具有较高的度，不同类之间的对象差别较大。例：一个照片中有30位学生，每个学生10张不同照片，将这300张照片打乱，聚类就是在不告诉机器任何学生的信息，仅凭对300张照片的学习，然后把它分成10类；聚类的应用场景聚类的应用场景经常光顾商店的客人，谁买什么东西，买多少？l 按会员卡记录的光临次数、光临时间、性别、年龄、职业、购物种类、金额等变量分类l 这样商店可以.l 识别顾客购买模式（如喜欢一大早来买酸奶和鲜肉，习惯周末时一次

2、性大采购）l 刻画不同的客户群的特征（用变量来刻画，就像刻画猫和狗的特征一样，即用户画像）聚类的应用场景聚类的应用场景原因：原因：l 为什么我们要这样分类？l 因为每一个类别里面的人消费方式、消费习惯都不一样，需要针对不同的人群，制定不同的关系管理方式，以提高客户对公司商业活动的相应率。l 如：淘宝、京东等均会根据用户画像为用户推荐用户可能感兴趣的商品；甚至所谓的大数据杀熟理论也是基于此。聚类的应用场景聚类的应用场景目的：目的：挖掘有价值的客户，并制定相应的促销策略：如，对经常购买酸奶的客户 对累计消费达到12个月的老客户针对潜在客户派发广告，比在大街上乱发传单命中率更高，成本更低！针对不同消

3、费层级或消费偏好的客户推送相应的产品及服务！聚类的应用领域聚类的应用领域经济领域：帮助市场分析人员从客户数据库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。谁喜欢打国际长途，在什么时间，打到那里？对住宅区进行聚类，确定自动提款机ATM的安放位置 股票市场板块分析，找出最具活力的板块龙头股 企业信用等级分类 生物学领域 推导植物和动物的分类；对基因分类，获得对种群的认识数据挖掘领域 作为其他数学算法的预处理步骤，获得数据分布状况，集中对特定的类做进一步的研究聚类的研究领域聚类的研究领域数据挖掘 聚类可伸缩性、各种各种复杂形状类的识别，高维聚类等统计学 主要集中在基于距离的聚类分析，

4、发现球状类机器学习 无监督学习（聚类不依赖预先定义的类，不等同于分类）空间数据技术生物学市场营销学聚类的应用场景聚类的应用场景以上分析，如果没有大量的数据去支持，聚类分析就什么都挖不出来。大量的数据不等于大量的垃圾，我们需要针对客户市场细分所需要的资料。如需要知道白金持卡人和金卡持卡人的流动率，各自平均消费水平有多少，等；聚类分析可以辅助企业进行客户细分，但是数据分析的客户细分并不等同于商业领域的细分，看不懂结果，也可能造成企业管理层无法对结果善加利用。聚类分析的原理聚类分析的原理聚类分析中“类”的特征：聚类所说的类不是事先给定的，而是根据数据的相似性相似性和距离距离来划分 聚类的数目和结构都

5、没有事先假定聚类方法的目的是寻找数据中：潜在的自然分组结构a structure of“natural”grouping 感兴趣的关系relationship聚类分析的原理聚类分析的原理什么是自然分组结构Natural grouping?我们看看以下的例子：有16张牌如何将他们分为 一组一组的牌呢？AKQJ聚类分析的原理聚类分析的原理分成四组每组里花色相同组与组之间花色相异AKQJ花色相同的牌为一副花色相同的牌为一副Individual suits聚类分析的原理聚类分析的原理分成四组符号相同的牌为一组AKQJ符号相同的的牌符号相同的的牌Like face cards聚类分析的原理聚类分析的原理

6、分成两组颜色相同的牌为一组AKQJ颜色相同的配对颜色相同的配对Black and red suits聚类分析的原理聚类分析的原理分成两组大小程度相近的牌分到一组AKQJ大配对和小配对大配对和小配对Major and minor suits聚类分析的原理聚类分析的原理这个例子告诉我们，分组的意义在于我们怎么定 义 并 度 量“相 似 性”Similar因此衍生出一系列度量相似性的算法AKQJ大配对和小配对大配对和小配对Major and minor suits聚类分析的原理聚类分析的原理 相似性度量相似性度量，即综合评定两个事物之间相近程度的一种度量。两个事物越接近，它们的相似性度量也就越大，而

7、两个事物越疏远，它们的相似性度量也就越小。聚类分析按照样本点之间的亲疏远近程度进行分类。为了使类分得合理，必须描述样本之间的亲疏远近程度。刻画聚类样本点之间的亲疏远近程度主要有以下两类函数：（1）距离函数：距离函数：可以把每个样本点看作高维空间中的一个点，进而使用某种距离来表示样本点之间的相似性，距离较近的样本点性质较相似，距离较远的样本点则差异较大。（2）相似系数函数：相似系数函数：两个样本点愈相似，则相似系数值愈接近1；样本点愈不相似，则相似系数值愈 接近0。这样就可以使用相似系数值来刻画样本点性质的相似性。聚类分析的原理聚类分析的原理距离函数距离函数 有n个特征值则组成n维向量 ，称为该

8、样本的特征向量。它相当于特征空间中的一个点，以特征空间中，点间的距离函数作为模式相似性的测量，以“距离”作为模式分类的依据，距离越小，越“相似”。T21,.,nxxxX注意：注意：聚类分析是否有效，与模式特征向量的分布形式有很大关系。选取的特征向量是否合适非常关键。例：酱油与可乐。聚类分析的原理聚类分析的原理17复习：已知向量 ，则：321yyyY232313322212312121321321TyyyyyyyyyyyyyyyyyyyyyYY 相似性度量相似性度量-距离距离2232221321321TYYYyyyyyyyyy聚类分析的原理聚类分析的原理常见的距离函数：常见的距离函数：l 欧氏距

9、离（欧氏距离（Euclidean）l 马氏距离马氏距离(Maharanobis)l曼哈顿距离（曼哈顿距离（Manhattan Distance）l 明氏距离明氏距离(Minkowaki)l 汉明汉明(Hamming)距离距离l 切比雪夫距离切比雪夫距离(Chebyshev)191）欧式距离（欧式距离（Euclidean distance，欧几里德）欧几里德）简称距离简称距离 设X1、X2为两个n维模式样本，T112111,.,nxxxXT222212,.,nxxxX2121),(XXXXD)()(21T21XXXX22122111)()(nnxxxx注意：注意：各特征向量对应的维上应当是相同的

10、物理量；注意物理量的单位。距离越小，越相似。欧氏距离定义为：某些维上物理量采用的单位发生变化，会导致对同样的点集出现不同聚类结果的现象。（2.3，5.6）（3.0，4.1）（4.5，8.8）（3.4，4.4）1：2，3，42：3，43：4（2.3，5.6，4，4.1）（3.0，4.1，5，5.1）（4.5，8.8，6，6.1）（3.4，4.4，7，7.1）1：2，3，42：3，43：422对n维向量：,nxx1Xnmm1M2）马氏距离马氏距离(Maharanobis)平方表达式：式中，X：模式向量；M：均值向量；C：该类模式总体的协方差矩阵。)()(1T2MXCMXD 22112211Tnnn

11、nmxmxmxmxmxmxEEMXMXC(M_Mean)(C_covariance)经过简单的推导就可以得到两个n维向量a(x11,x12,x1n)与 b(x21,x22,x2n)间的标准化欧氏距离的公式：23nnnnnnnnmxmxEmxmxEmxmxEmxmxEmxmxEmxmxEmxmxE112222112211221111112212222121212211nnnkkjkn 表示的概念是各分量上模式样本到均值的距离，也就是在各维上模式的分散情况。越大，离均值越远。2jk优点：排除了模式样本之间的相关影响。当C=I 时，马氏距离为欧氏距离。3）曼哈顿距离（曼哈顿距离（Manhattan

12、Distance）公式：公式：二维平面两点a(x1,y1)与b(x2,y2)间的曼哈顿距离：d（1，2）=|x1-x2|+|y1-y2|定义：定义：通俗来讲，想象你在曼哈顿要从一个十字路口开车到另外一个十字路口实际驾驶距离就是这个“曼哈顿距离”，此即曼哈顿距离名称的来源，同时，曼哈顿距离也称为城市街区距离(City Block distance)。251x2xiXjX当m=2时，明氏距离为欧氏距离。n维模式样本向量Xi、Xj间的明氏距离表示为：式中，xik、xjk分别表示Xi和Xj的第k个分量。mnkmjkikjimxxD11),(XX22111),(jijijixxxxDXX街坊欧氏4）明氏

13、距离明氏距离(Minkowaki)当m=1时：nkjkikjixxD11),(XX即为曼哈顿距离(“City block”distance)。当k=2时：图示5）汉明）汉明(Hamming)距离距离 在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如：1011101 与 1001001 之间的汉明距离是 2。2143896 与 2233796 之间的汉明距离是 3。toned 与 roses 之间的汉明距离是 3。jknkikjihxxnD121),(XX设Xi、Xj 为n维二值（1或1）模式

14、样本向量，则两个模式向量的各分量取值均不同：Dh(Xi,Xj)=n；全相同：Dh(Xi,Xj)=0式中，xik、xjk分别表示Xi和Xj的第k个分量。汉明距离：6）切比雪夫距离）切比雪夫距离(Chebyshev Distance)国际象棋中，国王可以直行、横行、斜行，所以国王走一步可以移动到相邻8个方格中的任意一个。国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步？这个距离就叫切比雪夫距离。n维空间点a(x11,x12,x1n)与b(x21,x22,x2n)的切比雪夫距离：相似系数函数相似系数函数-1）余弦）余弦(Cosine)相似度相似度 有没有搞错，又不是学几何，怎么扯到夹角余

15、弦了？各位看官稍安勿躁。几何中夹角余弦可用来衡量两个向量方向的差异，机器学习中借用这一概念来衡量样本向量之间的差异。(1)在二维空间中向量A(x1,y1)与向量B(x2,y2)的夹角余弦公式：(2)两个n维样本点a(x11,x12,x1n)和b(x21,x22,x2n)的夹角余弦类似的，对于两个n维样本点a(x11,x12,x1n)和b(x21,x22,x2n)，可以使用类似于夹角余弦的概念来衡量它们间的相似程度。即：夹角余弦取值范围为-1,1。夹角余弦越大表示两个向量的夹角越小，夹角余弦越小表示两向量的夹角越大。当两个向量的方向重合时夹角余弦取最大值1，当两个向量的方向完全相反夹角余弦取最小

16、值-1。292）Tanimoto测度测度用于0，1二值特征的情况，jijjiijijiSXXXXXXXXXXTTTT),(数中占有的特征数目的总和中共有的特征数目jijiXXXX,相似性测度函数的共同点都涉及到把两个相比较的向量Xi，Xj的分量值组合起来，但怎样组合并无普遍有效的方法，对具体的模式分类，需视情况作适当选择。30数据标准化数据标准化【对于尺度无关的解释】如果向量中第一维元素的数量级是100，第二维的数量级是10，比如v1=(100,10),v2=(500,40)，则计算欧式距离 可见欧式距离会给与第一维度100权重，这会压制第二维度的影响力。标准化欧氏距离是针对简单欧氏距离的缺点

17、而作的一种改进方案。标准欧氏距离的思路：既然数据各维分量的分布不一样，好吧！那我先将各个分量都“标准化”到均值、方差相等吧。均值和方差标准化到多少呢？先复习点统计学知识吧，假设样本集X的均值(mean)为m，标准差(standarddeviation)为s，那么X的“标准化变量”表示为：而且标准化变量的数学期望为0，方差为1。31数据标准化数据标准化因此样本集的标准化过程(standardization)用公式描述就是：标准化后的值标准化后的值=(标准化前的值标准化前的值 分量的均值分量的均值)/分量的标准差分量的标准差经过简单的推导就可以得到两个n维向量a(x11,x12,x1n)与b(x2

18、1,x22,x2n)间的标准化欧氏距离的公式：如果将方差的倒数看成是一个权重，这个公式可以看成是一种加权欧氏距离。32数据标准化数据标准化 以上方法称为z-score法，是基于原始数据的均值（mean）和标准差（standard deviation）进行数据的标准化。将A的原始值x使用z-score标准化到x。z-score标准化方法适用于属性A的最大值和最小值未知的情况，或有超出取值范围的离群数据的情况。除此之外，还有min-max法，如下：33数据标准化数据标准化比例法，如下：（2.3，5.6，4，4.1）34聚类准则：聚类准则：根据相似性测度确定的，衡量模式之间是否相似的标 准。即把不同

19、模式聚为一类还是归为不同类的准则。确定聚类准则的两种方式：1）阈值准则：根据规定的距离阈值进行分类的准则。2）函数准则：利用聚类准则函数进行分类的准则。聚类准则函数：在聚类分析中，表示模式类间相似或差异性的函数。它应是模式样本集X 和模式类别 的函数。可使聚类分析转化为寻找准则函数极值的最优化问题。一种常用的指标是误差平方之和。cSj,2,1j,聚类准则聚类准则35聚类准则函数：cjjSXjJ12MX式中：c为聚类类别的数目，jSXjjNXM1jS为属于集的样本的均值向量，jNjS为 中样本数目。J代表了分属于c个聚类类别的全部模式样本与其相应类别模式均值之间的误差平方和。适用范围：适用于各类样本密集且数目相差不多，而不同类间的样本又明显分开的情况。36例1：类内误差平方和很小，类间距离很远。可得到最好的结果。类长轴两端距离中心很远，J值较大，结果不易令人满意。137错误分类例2：另一种情况 有时可能把样本数目多的一类分拆为二，造成错误聚类。原因：这样分开，J值会更小。正确分类 谢谢！