第八章-聚类分析

《数据挖掘》主讲：王名扬信息与计算机工程学院2引言—要挖掘知识的类型概念描述：特征化和比较；关联规则；分类/预测；聚类分析；其他的数据挖掘任务。俗语说：“物以类聚，人以群分”。如，要想把中国的县分成若干类，就有很多种划分方法：可考虑降水、土地、日照、湿度等各方面；可考虑收入、教育水准、医疗条件、基础设施等指标；既可以用某一项来分类，也可以同时考虑多项指标来分类。再如：同学间的交往（家庭情况、性格、学习成绩、业余爱好等）引言聚类与分类的区别聚类：是对组的数目或者组的结构不用做任何假设的一种发现项目（或者变量）的自然分组方法（定义）；必须先建立一个定量的尺度，借以量度对象之间的联系；无（教师）监督的学习方法；观察式学习。分类：依赖于事先确定的数据类别，以及标有数据类别的学习训练样本集合。组的数目已知，目标是将一个新的对象分派给这些组之一；有（教师）监督的学习方法；示例式学习。第7章聚类分析第7章7.1什么是聚类分析？7.2距离和相似系数7.3类的定义和类间距离7.4基于划分的聚类方法7.5基于层次的聚类方法7.6基于密度的聚类方法7学习目的掌握各种距离的计算方法。掌握聚类的常用方法。7.1什么是聚类分析聚类(Clustering)：根据“物以类聚”的道理，对样品和指标进行分类的一种多元统计分析方法；聚类分析中“类”的特征：聚类所说的类不是事先给定的，而是根据数据的相似性和距离来划分；聚类的数目和结构都没有事先假定。9聚类准则对聚类结果的影响羊,狗,猫,鲨鱼蜥蜴,蛇,麻雀，海鸥,金鱼,青蛙(a)繁衍后代的方式金鱼,鲨鱼羊,狗,猫,蜥蜴,蛇,麻雀，海鸥,青蛙(b)肺的存在金鱼,鲨鱼羊,狗,猫,蜥蜴,蛇,麻雀，海鸥,青蛙(c)生存环境金鱼蜥蜴,蛇,麻雀，海鸥,青蛙(d)繁衍后代的方式和是否存在肺鲨鱼羊,狗,猫,距离测度对聚类结果的影响数据的粗聚类是两类,细聚类为4类聚类分析无处不在挖掘有价值的客户，并制定相应的促销策略：如，对经常购买酸奶的客户；对累计消费达到12个月的老客户。针对潜在客户派发广告，比在大街上乱发传单命中率更高，成本更低。聚类分析无处不在谁是银行卡的黄金客户？：利用储蓄额、刷卡消费金额、诚信度等变量对客户分类，找出“黄金客户”！；这样银行可以：制定更吸引客户的服务，留住客户，如：一定额度和期限的免息透资服务；百盛的贵宾打折卡；在生日的时候送蛋糕等。聚类分析无处不在经济领域：帮助市场分析人员从客户数据库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征；谁喜欢打国际长途，在什么时间，打到哪里？对住宅区进行聚类，确定自动提款机ATM的安放位置；股票市场板块分析，找出最具活力的板块龙头股；企业信用等级分类；。。。。。。聚类分析无处不在生物学领域：推导植物和动物的分类；对基因分类，获得对种群的认识；。。。。。。数据挖掘领域：作为其他数学算法的预处理步骤，获得数据分布状况，集中对特定的类做进一步研究。聚类分析聚类分析的目的是寻找数据中：潜在的自然分组结构(structureofnaturalgrouping)。感兴趣的关系relationship聚类分析什么是自然分组结构？看一下的例子：现有16张扑克牌，问如何将它们进行分组？聚类分析按照花色是否相同：分成四组；组与组之间花色相异。聚类分析按照符号是否相同：分成四组；符号相同的牌为一组。聚类分析按照颜色是否相同：分成两组；颜色相同的牌为一组。聚类分析该例子告诉我们：分组的意义在于我们怎样定义并度量“相似性”？因此衍生出一系列度量相似性的方法。聚类分析的原则：同一个组内的数据对象具有较高的相似度；而不同组中的数据对象是不相似的。7.2距离和相似系数相似性（Similar）的度量（统计学角度）：1）Q型聚类：对样本进行聚类（行聚类）常用的距离有：只适用于度量数值型变量（间隔尺度变量）•明可夫斯基距离（包括欧氏距离、切比雪夫距离、曼哈顿距离）；•马氏距离；•其他距离。2）R型聚类：对变量进行聚类（列聚类）；用变量之间的相似系数来度量距离。7.2距离和相似系数一、Q型聚类（对样本聚类）距离：测度样本之间的亲疏程度；将每一个样本看作p维空间的一个点，并用某种度量测量点与点之间的距离，距离较近的归为一类，距离较远的点应属于不同的类。距离的意义样本资料矩阵样本资料矩阵设：定义距离的准则定义第i个和第j个样本间的距离要求满足如下四个条件（距离可以自己定义，只要满足距离的条件）：(1)即距离是一个非负的数值(2)自身的距离为0(3)即距离函数具有对称性(4)即距离函数满足三角不等式0ijdjidij,0jiijddkjikijddd距离矩阵样品间距离矩阵：变量的类型变量按测量尺度的不同可以分为以下三类：**间隔(Interval)尺度变量（数值型变量）用连续的数量来度量，如长度、重量、速度、温度等有序(ordinal)尺度变量（序数型变量）有次序关系，不可加，但可比，如一等、二等、三等奖学金名义(Norminal)尺度变量（名义型变量）类别变量，不可加也不可比，如性别中的男与女，职业的分类。1、间隔尺度变量（数值型变量）kplkjlilijxxd11)||(明氏距离（1）明可夫斯基距离ixjxijd令表示样品与的距离npnnppxxxxxxxxx212222111211设原始数据为ppbnanpbapbaxxxxxxbad/12211),(第七章：kplkjlilijxxd11)||(pljlilijxxd12)(明氏距离当k＝2时，即为欧氏距离：当k＝∞时，即为切比雪夫距离：jlilplijxxd1maxpljlilijxxd1特别地，当k＝1时，即为曼哈顿（绝对值）距离：123452018104471055325.236.328.911.5171x2x3x3124224)(lllxxd222)5.113.36()510()418(欧氏距离切比雪夫距离lllxxd423124max8.245.113.3624d计算明可夫斯基距离的缺点：当各变量的测量值相差悬殊时，常发生“大数吃小数”的现象，为消除这种现象带来的影响，通常先将每个变量进行标准化。年龄收入家庭人口数甲3030001乙4032003222)31()32003000()4030(d35示例：另外，明氏距离的数值与指标的量纲有关。如，二维样本（身高、体重），有三个样本：a(180,50);b(190,50);c(180,60)则a与b之间的明氏距离（欧氏距离、切比雪夫距离）等于a与c之间的距离但问题是，身高的10cm真的等价于体重的10kg吗？因此，明氏距离无法消除量纲的影响，在衡量这类样本的相似度时容易出现问题。36示例：另外，即使是同一个变量，选用的度量单位的不同，也将直接影响聚类分析的结果：如：将高度的度量单位由“米”变为“英尺”，或将重量的单位由“千克”变为“英镑”，可能会产生非常不同的聚类结构。一般，度量单位越小，变量可能的值域越大，对聚类结果的影响也越大。因此，为避免对度量单位选择的依赖，数据应当标准化。37度量值的标准化一种方法是将初始测量值转换为无单位变量。给定一个属性变量f，可用如下公式对其进行标准化：（1）计算标准差标准差描述的是变量的各个取值到均值的距离之平均，反映的是数值分布的离散度。标准差越大，数值越分散；反之，标准差越小，数值越集中。.)...211njjjxx(xnjx（2）计算标准化测量（z-score）：nijijjxxnS12)(11，而jjijijSxxx*),,3,2,1;,,3,2,1(pjni经过标准化变换处理后，每个变量的平均值为0，方差为1，且也不再具有量纲，这便于不同变量之间的比较。接下来就可以用前面所描述的任意一组距离度量方法进行计算相异度。度量值的标准化39特例：比例数值变量比例数值变量（比例标度型变量）：一个比例数值变量指在非线性的标度上取正的度量值的变量，如指数比例：40在计算比例数值变量所描述对象间的距离时，有两种处理方法：1）将比例数值变量看作区间标度变量，采用相同的方法处理，但不佳，因为比例尺度是非线性的；2）采用对数变换，对比例数值变量进行处理，然后将yif当做区间标度变量来处理。特例：比例数值变量2、有序(ordinal)尺度变量42有序尺度变量有序尺度变量（顺序变量）：一个离散的顺序变量类似于符号变量，但不同的是顺序变量的M个状态是以有意义的顺序进行排列的。如专业等级是一个顺序变量，是按照助教、讲师、副教授和教授的顺序排列的。一个连续的顺序变量，值的相对位置要比它的实际数值有意义的多，如某个比赛的相对排名（金牌、银牌和铜牌）可能比实际得分更重要。43有序尺度变量有序尺度变量的处理与间隔尺度变量非常类似，假设f是用于描述n个对象的一组顺序变量之一，关于f的距离计算如下：接下来就可以用间隔尺度变量中所描述的任意一组距离度量方法进行计算相异度。3、名义尺度变量（符号变量）45名义尺度变量名义尺度变量（符号变量）：二元变量：只有两个状态：0或者1。其中0代表变量所表示的状态不存在；1则代表相应的状态存在。如：电路的开和关，天气的有雨和无雨，人口性别的男和女，医疗诊断中的“十”和“一”，市场交易中的买和卖等都是此类变量名义变量：是二元变量的推广，可具有多于两个的状态值如颜色变量（红、橙、黄、绿、蓝等）。461）二元变量的相异度计算差异矩阵法：如果假设所有的二元变量有相同的权重，则可以得到一个两行两列（2*2）的条件表。47二元变量的相异度计算其中：q表示在对象i和对象j中均取1的二值变量个数；r表示在对象i取1但对象j中取0的二值变量个数；s表示在对象i中取0而在对象j中取1的二值变量个数；t则表示在对象i和对象j中均取0的二值变量个数。二值变量的总数为p，则：p=q+r+s+t。48恒定的相似度如果一个二值变量取0或1所表示的内容同等价值，且有相同的权重，则该二元变量是对称的。如，属性“性别”，有两个值“女性”和“男性”，两个取值都没有优先权。基于对称二元变量的相似度，称为恒定的相似度。对恒定相似度而言，评价对象i和j间相异度的最著名的方式是简单匹配系数：q表示在对象i和对象j中均取1的二值变量个数；r表示在对象i取1但对象j中取0的二值变量个数；s表示在对象i中取0而在对象j中取1的二值变量个数；t则表示在对象i和对象j中均取0的二值变量个数。49如果一个二值变量的两个取值的重要性不同等重要，则该二元变量就是不对称的。如一个疾病disease的测试结果positive或negative，显然这两个测试结果的重要性是不一样的：通常将比较重要的输出结果，编码为1；而将另一结果编码为0.基于这样的二元变量的相似度被称为非恒定的相似度.非恒定的相似度50对非恒定相似度，最常见的描述对象i和对象j间差异度的参数是Jaccard相关系数：在计算过程中，负匹配的数目t被认为是不重要的，因此被忽略。其中，q表示在对象i和对象j中均取1的二值变量个数；r表示在对象i取1但对象j中取0的二值变量个数；s表示在对象i中取0而在对象j中取1的二值变量个数；t则表示在对象i和对象j中均取0的二值变量个数。非恒定的相似度51例：样本Xi和样本Xj都是具有8个二元类型的变量：Xi={0,0,1,1,0,1,0,1}Xj={0,1,1,0,0,1,0,0}则，q=2;r=2;s=1;t=3简单匹配系数：d(i,j)=(r+s)/(q+r+s+t)=3/8Jaccard系数：d(i,j)=(r+s)/(q+r+s)=3/5示例522）名义尺度变量名义尺度变量（符号变量）：名义尺度变量是二元变量的推广，可具有多于两个的状态