1、第五章第五章 聚类分析聚类分析主讲人：第五章第五章 聚类分析聚类分析 (Clustering Analysis)5.1 5.1 聚类分析的概念聚类分析的概念5.2 5.2 模式相似性测度模式相似性测度5.3 5.3 类的定义与类间距离类的定义与类间距离5.4 5.4 聚类的算法聚类的算法5.1 5.1 聚类分析的概念聚类分析的概念一、聚类分析的基本思想一、聚类分析的基本思想 相似的归为一类。相似的归为一类。模式相似性的度量和聚类算法。模式相似性的度量和聚类算法。无监督分类无监督分类（Unsupervised）。二、特征量的类型二、特征量的类型 物理量物理量-(-(重量、长度、速度重量、长度、速
2、度)次序量次序量-(-(等级、技能、学识等级、技能、学识)名义量名义量-(-(性别、状态、种类性别、状态、种类)第五章第五章 聚类分析聚类分析三、方法的有效性三、方法的有效性 取决于分类算法和特征取决于分类算法和特征点分布情况的匹配。点分布情况的匹配。5.1 聚类分析的概念2w2W1w1W2x1xb分类无效时的情况分类无效时的情况1.1.特征选取不当使分类无效。特征选取不当使分类无效。三、方法的有效性三、方法的有效性 取决于分类算法和特征取决于分类算法和特征点分布情况的匹配。点分布情况的匹配。5.1 聚类分析的概念分类无效时的情况分类无效时的情况2.2.特征选取不足可能使不同特征选取不足可能使
3、不同类别的模式判为一类。类别的模式判为一类。2w2W1w1W2x1x3w3W三、方法的有效性三、方法的有效性 取决于分类算法和特征取决于分类算法和特征点分布情况的匹配。点分布情况的匹配。5.1 聚类分析的概念分类无效时的情况分类无效时的情况3.3.特征选取过多可能无益反特征选取过多可能无益反而有害而有害,增加分析负担并使增加分析负担并使分析效果变差。分析效果变差。2w2W1w1W2x1xb三、方法的有效性三、方法的有效性 取决于分类算法和特征取决于分类算法和特征点分布情况的匹配。点分布情况的匹配。5.1 聚类分析的概念分类无效时的情况分类无效时的情况4.4.量纲选取不当。量纲选取不当。三、方法
4、的有效性三、方法的有效性 取决于分类算法和特征取决于分类算法和特征点分布情况的匹配。点分布情况的匹配。5.1 聚类分析的概念分类无效时的情况分类无效时的情况4.4.量纲选取不当。量纲选取不当。下列是一些动物的名称：下列是一些动物的名称：羊羊 （sheepsheep）狗狗 （dogdog）蓝鲨（蓝鲨（blue sharkblue shark）蜥蜴蜥蜴 （lizardlizard）毒蛇（毒蛇（viperviper）猫猫 （catcat）麻雀（麻雀（sparrowsparrow）海鸥海鸥 （seagullseagull）金鱼（金鱼（gold fishgold fish）绯鲵鲣（绯鲵鲣（red-mul
5、letred-mullet）蛙蛙 （frogfrog）要对这些动物进行分类，则不同的特征有不同的分法：要对这些动物进行分类，则不同的特征有不同的分法：特征选取不同对聚类结果的影响特征选取不同对聚类结果的影响特征选取不同对聚类结果的影响特征选取不同对聚类结果的影响羊羊,狗狗,猫猫蓝鲨蓝鲨蜥蜴蜥蜴,毒蛇毒蛇,麻雀麻雀,海鸥海鸥,金鱼金鱼,绯鲵鲣绯鲵鲣,青蛙青蛙(a)按繁衍后代的方式分按繁衍后代的方式分哺乳动物哺乳动物非哺乳动物非哺乳动物金鱼金鱼绯鲵鲣绯鲵鲣蓝鲨蓝鲨羊羊,狗狗,猫猫蜥蜴蜥蜴,毒蛇毒蛇麻雀麻雀,海鸥海鸥 青蛙青蛙(b)按肺是否存在分按肺是否存在分无肺无肺有肺有肺特征选取不同对聚类结果的
6、影响特征选取不同对聚类结果的影响青蛙青蛙羊羊,狗狗,猫猫 蜥蜴蜥蜴,毒蛇毒蛇麻雀麻雀,海鸥海鸥 金鱼金鱼绯鲵鲣绯鲵鲣 蓝鲨蓝鲨(c)按生活环境分按生活环境分陆地陆地水里水里两栖两栖特征选取不同对聚类结果的影响特征选取不同对聚类结果的影响蓝鲨蓝鲨金鱼金鱼绯鲵鲣绯鲵鲣蜥蜴蜥蜴,毒蛇毒蛇麻雀麻雀,海鸥海鸥 青蛙青蛙羊羊,狗狗,猫猫(d)按繁衍后代方式和肺是否存在分按繁衍后代方式和肺是否存在分非哺乳且有肺非哺乳且有肺哺乳且无肺哺乳且无肺哺乳且有肺哺乳且有肺非哺乳且无肺非哺乳且无肺特征选取不同对聚类结果的影响特征选取不同对聚类结果的影响距离测度不同距离测度不同,聚类结果也不同聚类结果也不同数据的粗聚类是
7、两类数据的粗聚类是两类,细聚类为细聚类为4类类综上可见综上可见:选择什么特征？选择什么特征？选择多少个特征？选择多少个特征？选择什么样的量纲？选择什么样的量纲？选择什么样的距离测度？选择什么样的距离测度？这些对分类结果都会产生极大影响。这些对分类结果都会产生极大影响。聚类过程遵循的基本步骤 一、特征选择(feature selection)尽可能多地包含任务关心的信息二、近邻测度(proximity measure)定量测定两特征如何“相似”或“不相似”三、聚类准则（clustering criterion）以蕴涵在数据集中类的类型为基础四、聚类算法（clustering algorithm）
8、按近邻测度和聚类准则揭示数据集的聚类结构五、结果验证（validation of the results）常用逼近检验验证聚类结果的正确性六、结果判定（interpretation of the results）由专家用其他方法判定结果的正确性聚类应用的四个基本方向一、减少数据 许多时候，当数据量N很大时，会使数据处理变得很费力。因此可使用聚类分析的方法将数据分成几组可判断的聚类m（mN）来处理，每一个类可当作独立实体来对待。从这个角度看，数据被压缩了。二、假说生成 在这种情况下，为了推导出数据性质的一些假说，对数据集进行聚类分析。因此，这里使用聚类作为建立假说的方法，然后用其他数据集验证这些
9、假说。聚类应用的四个基本方向聚类应用的四个基本方向三、假说检验 用聚类分析来验证指定假说的有效性。例如：考虑这样的假说例如：考虑这样的假说“大公司在海外投资大公司在海外投资”。要验证这个假说是否正确，就要对大公司和有要验证这个假说是否正确，就要对大公司和有代表性的公司按规模、海外活跃度、成功完成代表性的公司按规模、海外活跃度、成功完成项目的能力等进行聚类分析。从而来支持这个项目的能力等进行聚类分析。从而来支持这个假说。假说。四、基于分组的预测 对现有数据进行聚类分析，形成模式的特征，并用特征表示聚类，接下来，对于一个未知模式，就可以用前面的聚类来确定是哪一类？聚类应用的四个基本方向例如：考虑被
10、同种疾病感染的病人数据集。例如：考虑被同种疾病感染的病人数据集。先按聚类分析进行分类，然后对新的病人确定他先按聚类分析进行分类，然后对新的病人确定他适合的聚类，从而判断他病情。适合的聚类，从而判断他病情。5.2 5.2 模式相似性测度模式相似性测度 用于描述各模式之间特征的相似程度用于描述各模式之间特征的相似程度 距距 离离 测测 度度 相相 似似 测测 度度 匹匹 配配 测测 度度一、距离测度一、距离测度(差值测度差值测度)测度基础：两个矢量矢端的距离测度基础：两个矢量矢端的距离测度数值：两矢量各相应分量之差的函数。测度数值：两矢量各相应分量之差的函数。时，等号成立；时，等号成立；0),(y
11、xd，当且仅当，当且仅当xy),(),(xydyxd),(),(),(yzdzxdyxd常用的距离测度有：常用的距离测度有：1.1.欧氏欧氏(Euclidean)(Euclidean)距离距离 4.明氏(Minkowski)距离 2.绝对值距离绝对值距离(街坊距离街坊距离)3.切氏(Chebyshev)距离5.2 模式相似性测度5.马氏(Mahalanobis)距离注意！马氏距离对一切非奇异线性变换都是不变的，这说明它不受特征量纲选择的影响，并且是平移不变的。上面的V V的含义是这个矢量集的协方差阵的统计量，故马氏距离加入了对特征的相关性的考虑。5.2 模式相似性测度5.2 模式相似性测度二、
12、相似测度测度基础：以两矢量的方向是否相近作为考虑的基础,矢量长度并不重要。设1.角度相似系数(夹角余弦)5.2 模式相似性测度2.相关系数它实际上是数据中心化后的矢量夹角余弦。21)()()()()(),(yyyyxxxxyyxxyxr5.2 模式相似性测度3.指数相似系数 niiiiyxnyxe122)(43exp1),(式中式中 为相应分量的协方差，为相应分量的协方差，为矢量维数。为矢量维数。2in53 类的定义与类间距离1 1 类的定义类的定义定义定义1 1 设集合设集合S S中任意元素中任意元素x xi i与与y yj j间的距离间的距离d dijij有有 d dijij h h其中其
13、中h h为给定的阀值，称为给定的阀值，称S S对于阀值对于阀值h h组成一类。组成一类。类的定义有很多种，类的划分具有人为规定性，这反类的定义有很多种，类的划分具有人为规定性，这反映在定义的选取及参数的选择上。一个分类结果的优劣最映在定义的选取及参数的选择上。一个分类结果的优劣最后只能根据实际来评价。后只能根据实际来评价。53 类的定义与类间距离2 2 类间距离测度方法类间距离测度方法 最近距离法最近距离法 最远距离法最远距离法 中间距离法中间距离法 重心距离法重心距离法 平均距离法平均距离法 离差平方和法离差平方和法53 类的定义与类间距离2 2 类间距离测度方法类间距离测度方法 最近距离法
14、最近距离法 最远距离法最远距离法 中间距离法中间距离法 重心距离法重心距离法 平均距离法平均距离法 离差平方和法离差平方和法式中式中 表示表示 和和 之间的距离。之间的距离。ijjikldD,minijdkixwljxw53 类的定义与类间距离2 2 类间距离测度方法类间距离测度方法 最近距离法最近距离法 最远距离法最远距离法 中间距离法中间距离法 重心距离法重心距离法 平均距离法平均距离法 离差平方和法离差平方和法式中式中 表示表示 和和 之间的距离。之间的距离。ijdkixwljxwijjikldD,max53 类的定义与类间距离2 2 类间距离测度方法类间距离测度方法 最近距离法最近距离
15、法 最远距离法最远距离法 中间距离法中间距离法 重心距离法重心距离法 平均距离法平均距离法 离差平方和法离差平方和法pw wqw wkw wpqkpqDkqDklDkpDlw wpqkqkpklDDDD2222412121qplwww53 类的定义与类间距离2 2 类间距离测度方法类间距离测度方法 最近距离法最近距离法 最远距离法最远距离法 中间距离法中间距离法 重心距离法重心距离法 平均距离法平均距离法 离差平方和法离差平方和法22222)(pqqpqpkqqpqkpqppklDnnnnDnnnDnnnDnp,nq分别为类分别为类w wp和和w wq的的样本个数样本个数lpqwww53 类的
16、定义与类间距离2 2 类间距离测度方法类间距离测度方法 最近距离法最近距离法 最远距离法最远距离法 中间距离法中间距离法 重心距离法重心距离法 平均距离法平均距离法 离差平方和法离差平方和法wwqjpixxijqppqdnnD22153 类的定义与类间距离2 2 类间距离测度方法类间距离测度方法 最近距离法最近距离法 最远距离法最远距离法 中间距离法中间距离法 重心距离法重心距离法 平均距离法平均距离法 离差平方和法离差平方和法wtixtititxxxxs)()(qplwwwqplpqsssD2)()(2qpqpqpqppqxxxxnnnnDpxqx分别为对应类的重心分别为对应类的重心类内离差
17、平方和类内离差平方和 2222pqlkkkqlkqkkplkpkklDnnnDnnnnDnnnnD递推公式为递推公式为:222222kqkppqkqqkppklDDDDDD 最近距离法最近距离法 1/2 1/2 0 -1/2 最远距离法最远距离法 1/2 1/2 0 1/2 中间距离法中间距离法 1/2 1/2 -1/4 0 重心距离法重心距离法 0 平均距离法平均距离法 0 0 可变平均法可变平均法 0 可变法可变法 0 离差平方和法离差平方和法 0pqqppnnnqpqnnnqpqppnnnqpqnnnqppnnn)1(qpqnnn)1(112121lkpknnnnlkqknnnnlkkn
18、nn53 类的定义与类间距离3 3 聚类的准则函数聚类的准则函数判别分类结果好坏的一般标准：判别分类结果好坏的一般标准：类内距离小，类间距离大。类内距离小，类间距离大。某些算法需要一个能对分类过程或分类结果某些算法需要一个能对分类过程或分类结果的优劣进行评估的准则函数。如果聚类准则函数的优劣进行评估的准则函数。如果聚类准则函数选择得好，聚类质量就会高。聚类准则往往是和选择得好，聚类质量就会高。聚类准则往往是和类的定义有关的，是类的定义的某种体现。类的定义有关的，是类的定义的某种体现。聚类的准则函数聚类的准则函数一、类内距离准则一、类内距离准则 设有待分类的模式集设有待分类的模式集 在某种相似性
19、测在某种相似性测度基础上被划分为度基础上被划分为 类，类，类内距离准则函数类内距离准则函数 定义为定义为:(表示表示 类的模式均类的模式均值矢量。值矢量。)Nxxx,21cjjinicjx,2,1;,2,1)(；WJcjnijjiWjmxJ112)(53 类的定义与类间距离jmjw53 类的定义与类间距离加权类内距离准则加权类内距离准则 :WWJ21jcjjWWdNnJ(2-3-22)2)()(2)()()1(2jjijjkxxjkjijjjxxnndww(2-3-23)式中，2)()(jkjixx表示jw类内任两个模式距离2)1(jjnn 个组合数，所以2jd表示类内Nnj表示jw类先验概率
20、的估计频率。平方和，共有两模式间的均方距离。N为待分类模式总数，53 类的定义与类间距离加权类间距离准则加权类间距离准则:对于两类问题，类间距离有时取)()(21212mmmmJB(2-3-26)2BJ和WBJ的关系是221BWBJNnNnJ(2-3-27)max)()(1cjjjjWBmmmmNnJ(2-3-25)53 类的定义与类间距离 的类内离差阵定义为的类内离差阵定义为 (2-3-28)(2-3-28)jw),2,1()(1)(1)()(cjmxmxnSjjijnijijjWj53 类的定义与类间距离mjjwjnijijjxnm1)(1),2,1(cj式中式中 为类为类 的模式均值矢量的模式均值矢量 (2-3-29)(2-3-29)
