商务智能ppt第五章 聚类分析

第五章聚类分析【学习目标】

理解聚类的基本概念掌握距离计算的不同方式掌握聚类的不同方法5.1聚类的基本概念“物以类聚，人以群分”，在自然科学和社会科学中，存在着大量的分类问题。例如，市场营销中的市场细分和客户细分问题。大型购物网站收集到客户人口特征、消费行为和喜好方面的数据，并希望对这些客户进行特征分析。可以从客户分类入手，根据客户的年龄、职业、收入、消费金额、消费频率、喜好等方面进行单变量或多变量的客户分组。这种分组是极为常见的客户细分方式，但存在的不足是客户群划分带有明显得主观色彩，需要有丰富的行业经验才能得到比较合理或理想的客户细分，否则得到的分组可能无法充分反映和展现客户的特点，主要表现在，同一客户细分段中的客户在某些特征方面并不相似，而不同客户细分段中的客户在某些特征方面却又很相似。因此，这种客户细分并没有真正起到划分客户群的作用。为解决该问题，希望从数据自身出发，充分利用数据进行客户的客观分组，使诸多特征有相似性的客户被分在同一组，而不相似的客户被区分到另一些组中。聚类分析则是这样一种方法聚类分析又称群分析，它是研究（样品或指标）分类问题的一种多元统计分析方法。聚类分析起源于分类学，但是聚类不等于分类。聚类与分类的不同在于，聚类所要求划分的类是未知的。聚类分析内容非常丰富，有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。聚类分析能够将一批样本或（变量）数据依据其诸多特征，按照性质上的亲疏程度在没有先验知识的情况下进行自动分类，产生多个分类结果。类内部的个体在特征上具有相似性，不同类间个体特征的差异性较大理解聚类分析的关键是理解两个要点：“没有先验知识”和“亲疏程度”。为此，可以先看一个例子编号购物环境服务质量A超市7368B超市6664C超市8482D超市9188E超市9490“亲疏程度”的衡量与计算在聚类分析中，衡量个体之间的“亲属程度”是极为重要的，它将直接影响最终的聚类结果。衡量“亲疏程度”一般有两个角度：第一，个体间的相似程度；第二，个体间的差异程度。衡量个体间的相似程度通常可以采用简单相关系数或等级相关系数等；个体间的差异程度通常通过某种距离来测度，以下着重讨论个体间的差异程度。为定义个体间的距离，应先将每个样本数据看成k维空间上的一个点。例如，可将表5-1中五个超市样本看成k等于2的二维空间上的五个点，也就是看成由购物环境和服务质量两个变量构成的二维平面上的五个点，并于此定义某种距离，计算五个点彼此间的“亲疏程度”。通常，点与点之间距离越小，意味着它们越“亲密”，越有可能聚成一类。点与点之间距离越大，意味着它们越“疏远”，越有可能分别属于不同的类。编号购物环境服务质量A超市7368B超市6664C超市8482D超市9188E超市94905.2.1定距型变量个体间距离计算

如果涉及到的k个变量都是定距型变量，那么个体间距离的定义通常有以下几种方式：1.欧氏距离(EuclideanDistance)欧氏距离（也称欧几里得度量（Euclideanmetric））是一个通常采用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。在二维和三维空间中的欧氏距离就是两点之间的实际距离。2.曼哈顿距离(ManhattanDistance)

想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源，曼哈顿距离也称为城市街区距离(CityBlockdistance)。曼哈顿距离(ManhattanDistance)

需要注意的地方：非负性：d(i,j)≥0距离是一个非负的数值；同一性：d(i,i)=0对象到自身的距离为0；对称性：d(i,j)=d(j,i)距离是一个对称函数；3.切比雪夫距离(ChebyshevDistance)

国际象棋玩过么？国王走一步能够移动到相邻的8个方格中的任意一个。那么国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步？自己走走试试。你会发现最少步数总是max(|x2-x1|,|y2-y1|)步。有一种类似的一种距离度量方法叫切比雪夫距离。在数学中，切比雪夫距离是向量空间中的一种度量，两个点之间的距离定义是其各坐标数值差绝对值的最大值。举个例子：二维样本(身高,体重)，其中身高范围是150~190，体重范围是50~60，有三个样本：a(180,50)，b(190,50)，c(180,60)。那么计算a与b之间，a与c之间的曼哈顿距离、欧氏距离或切比雪夫距离标准欧氏距离的定义*

标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案。标准欧氏距离的思路：针对数据各维分量的分布不一致情况将各个分量“标准化”到均值、方差相等。假设样本集X的均值(mean)为m，标准差(standarddeviation)为s，那么X的“标准化变量”（标准化变量的数学期望为0，方差为1）表示为：标准化后的值=(标准化前的值－分量的均值)/分量的标准差。夹角余弦(Cosine)*夹角余弦取值范围为[-1,1]。夹角余弦越大表示两个向量的夹角越小，夹角余弦越小表示两向量的夹角越大。当两个向量的方向重合时夹角余弦取最大值1，当两个向量的方向完全相反夹角余弦取最小值-1。5.2.2计数变量个体间距离的计算方式

卡方（Chi-Square）距离文化程度企业高中及以上初中小学及以下合计甲44（46）36（42）140（132）220乙60（58）60（54）160（168）280合计104963005005.2.3二值变量个体间距离计算该表是根据原始数据转换而来的两个体取值的交叉列联表。表中，a+b+c+d等于变量的总个数，a为两个体取值都为1的变量个数，b为个体x取值为0,而个体y取值为1的变量个数，c为个体x取值为1而个体y取值为0的变量个数，d为两个体取值都是0的变量个数。显然，a+d的比重描述了两个体之间的相似程度，而b+c的比重反映了两个体之间的差异程度。1.简单匹配系数

个体x10个体y1ab0cd姓名性别发烧咳嗽检查1检查2检查3检查4JackMYNPNNNMaryFYNPNPNJimMYPNNNN2.雅科比系数(Jaccardcoefficient)

一个二元属性是对称的，如果它的两种状态具有同等价值并且携带相同的权重；即关于哪个结果应该用0或1编码并无偏好（例如，属性gender的两种状态男和女）。一个二元属性是非对称的，如果其状态的结果不是同等重要的。为方便计，我们将用1对最重要的结果（通常是稀有的）编码（例如，HIV阳性），而另一个用0编码（例如，HIV阴性）。给定两个不对称的二元变量，两个都取值1的情况（正匹配）被认为比两个都取值0的情况（负匹配）更有意义。基于这样变量的相似度被称为非恒定的相似度。对非恒定的相似度，最著名的评价系数是Jaccard系数，在它的计算中，负匹配的数目被认为是不重要的，因此被忽略。换句话说，就是把d去掉。姓名性别发烧咳嗽检查1检查2检查3检查4JackMYNPNNNMaryFYNPNPNJimMYPNNNN首先给Y和P值赋值为1，N赋值为05.2.4其他个体间距离计算

1.汉明距离(Hammingdistance)，汉明距离表示两个（相同长度）字对应位不同的数量。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。1011101与1001001之间的汉明距离是2。2143896与2233796之间的汉明距离是3。信息熵(InformationEntropy)

信息熵并不属于一种相似性度量。信息熵是衡量分布的混乱程度或分散程度的一种度量。分布越分散(或者说分布越平均)，信息熵就越大。分布越有序（或者说分布越集中），信息熵就越小。n：样本集X的分类数；pi：X中第i类元素出现的概率；信息熵越大表明样本集S分类越分散，信息熵越小则表明样本集X分类越集中。当S中n个分类出现的概率一样大时（都是1/n），信息熵取最大值log2(n)。当X只有一个分类时，信息熵取最小值0。5.3聚类的方法

5.3.1K-Means聚类算法K均值聚类算法（K-MeansClusteringAlgorithm）是一种迭代求解的聚类分析算法，其步骤是随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心2．K-Means(K均值)聚类算法及步骤

（1）首先确定一个k值，即我们希望将数据集经过聚类得到k个集合。（2）从数据集中随机选择k个数据点作为质心。（3）对数据集中每一个点，计算其与每一个质心的距离（如欧式距离），离哪个质心近，就划分到那个质心所属的集合。（4）把所有数据归好集合后，一共有k个集合。然后重新计算每个集合的质心。（5）如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值（表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛），我们可以认为聚类已经达到期望的结果，算法终止。（6）如果新质心和原质心距离变化很大，需要迭代3~5步骤

XYP100P212P331P488P5910P6107第一次循环

P1P2P33.162.24P411.39.22P513.511.3P612.210.3（1）首先令K等于2，随机选择两个点：P1和P2；（2）通过勾股定理计算剩余点分别到这两个点的距离，（3）第一次分组后结果：表其余点到P1、P2的距离组A：P1组B：P2、P3、P4、P5、P6（4）分别计算A组和B组的质心：A组质心还是P1=（0，0）B组新的质心坐标为：P2’=（（1+3+8+9+10）/5，（2+1+8+10+7）/5）=（6.2，5.6）第二次循环

P1P2’P22.246.3246P33.165.6036P411.33P513.55.2154P612.24.0497（5）再次计算每个点到质心的距离,如表5-7所示：表5-7其余点到质心的距离（6）第二次分组结果：组A：P1、P2、P3组B：P4、P5、P6（7）再次计算质心：P1’=（1.33，1）P2”=（9，8.33）

P1’P2”P11.412P20.610P31.49.5P4471.1P5701.7P6561.7（8）再次计算每个点到质心的距离，如表5-8所示：表5-8其余点到新质心的距离（9）第三次分组结果：组A：P1、P2、P3组B：P4、P5、P6可以发现，第三次分组结果和第二次分组结果一致，说明已经收敛，聚类结束。k-means有个缺点？

怎么确定K呢？将K从2~N进行遍历，

然后？

K-means算法最优k值的选取方法

K-Medians聚类算法K-Means算法存在一个问题，就是当数据中出现了某些数据偏离整体数据很远时，会给算数平均值带来不利影响。比如，某公司有五个人的年薪是5万元，但是有另外一个人的年薪高达100万，那么年薪中间值会是5万（能代表公司的年薪情况），而平均值达到了20万（完全不能代表公司薪资情况）！这种问题当然也会在K-Means算法中发生。一个解决办法就是使用K-Medians算法代替K-Means算法，二者算法相似，只是用中值代替平均值有十个点：1.（3,8）；2.（3,6）；3.（3,4）；4.（4,5）；5.（4,7）；6.（5,1）；7.（5,5）；8.（7,3）；9.（7，5）；10.（8,5）。将这10个点划分为两个类。首先，选取两个初始的中心点为3号，和6号。然后，用曼哈顿距离公式为他们进行划分

C#1(3,4)C#2(5,1)

1.（3,8）4912.（3,6）2714.（4,5）2515.（4,7）4717.（5,5）3418.（7,3）5429.（7,5）56110.（8,5）671图5-5第一次聚类后结果对第一类点集重新排列：（3,8）；（3,6）；（3,4）；（4,5）；（4,7）；（5,5）；（7,5）；（8,5）。对横坐标排序之后的中位数是4，对纵坐标排序之后的中位数是5，这个时候第一类的中心点就变成了（4,5）第二类的点集是（5,1）和（7,3），中心点就是（6,2）

C#1(4,5)C#2(6,2)

1.（3,8）4912.（3,6）2713.（3,4）2514.（4,5）0515.（4,7）2716.（5,1）5227.（5,5）1418.（7,3）5229.（7,5）34110.（8,5）451

C#1(3,4)C#2(5,1)

1.（3,8）4912.（3,6）2714.（4,5）2515.（4,7）4717.（5,5