数学建模聚类分析.ppt

《数学建模聚类分析.ppt》由会员分享，可在线阅读，更多相关《数学建模聚类分析.ppt（52页珍藏版）》请在优知文库上搜索。

1、聚聚 类类 分分 析析 一、聚类分析（一、聚类分析（Cluster Analysis）简介）简介 聚类分析是直接比较各事物之间的性质，将性质聚类分析是直接比较各事物之间的性质，将性质相相近近的归为一类，将性质的归为一类，将性质差别较大差别较大的归入不同的类的分析的归入不同的类的分析技术。技术。 数理统计中的数值分类有两种问题：数理统计中的数值分类有两种问题： ：已知分类情况，将未知个体归入正确类别：已知分类情况，将未知个体归入正确类别 ：分类情况未知，对数据结构进行分类：分类情况未知，对数据结构进行分类基本思想基本思想 聚类分析的基本思想聚类分析的基本思想: : 对所研究的样品或指标对所研究的

2、样品或指标( (变量变量) )之间存在着程度不同的相似性之间存在着程度不同的相似性( (或亲疏关系或亲疏关系) )。（1 1）根据一批样品的多个指标）根据一批样品的多个指标, , 具体找出一些能够具体找出一些能够度量样品或指标之间的相似程度的度量样品或指标之间的相似程度的统计量统计量。（2 2）以这些统计量为分类的依据）以这些统计量为分类的依据, , 把一些相似程度把一些相似程度较大较大的样品的样品( (或指标或指标) )聚合为一类。聚合为一类。 把另一些彼此之间相似程度把另一些彼此之间相似程度较大较大的样品的样品( (或指标或指标) )聚合为另一类。聚合为另一类。 基本思想基本思想 按相似程

3、度的大小按相似程度的大小把关系把关系密切密切的样品聚合到一个的样品聚合到一个小小的分类单位的分类单位, , 关系关系疏远疏远的样品聚合到一个的样品聚合到一个大大的分类单位的分类单位, , 直到把所有的样品直到把所有的样品( (或指标或指标) )都聚合完毕。都聚合完毕。 把不同的类型一一划分出来把不同的类型一一划分出来, , 形成一个由小到大形成一个由小到大的分类系统。再把整个分类系统画成一张分群图的分类系统。再把整个分类系统画成一张分群图( (又又称称谱系谱系图图), ), 用它把所有样品用它把所有样品( (或指标或指标) )间的亲疏关系间的亲疏关系表示出来。表示出来。 要做聚类分析，首先得按

4、照我们聚类的目的，从要做聚类分析，首先得按照我们聚类的目的，从对象中对象中提取提取出能表现这个目的的出能表现这个目的的特征指标特征指标；然后根据；然后根据亲疏程度进行分类。亲疏程度进行分类。聚类分析根据分类对象的不同可分为聚类分析根据分类对象的不同可分为Q型和型和R型两大类型两大类Q型是对样本进行分类处理，其作用在于型是对样本进行分类处理，其作用在于:1. 具有共同特点的样本聚在一起具有共同特点的样本聚在一起2. 所得结果比传统的定性分类方法更细致、全面、所得结果比传统的定性分类方法更细致、全面、合理合理二、聚类对象二、聚类对象R型是对变量进行分类处理，其作用在于：型是对变量进行分类处理，其作

5、用在于：1. 可以了解变量间及变量组合间的亲疏关系可以了解变量间及变量组合间的亲疏关系2. 可以根据变量的聚类结果及它们之间的关系，可以根据变量的聚类结果及它们之间的关系，选择主要变量进行回归分析或选择主要变量进行回归分析或Q型聚类分析型聚类分析 2 相似性度量相似性度量 进行进行“相关性相关性”或或“相似性相似性”度量。在相似性度量。在相似性度量中常常包含有许多主观上的考虑，但是最重要度量中常常包含有许多主观上的考虑，但是最重要的是考虑指标性质或观测的尺度。的是考虑指标性质或观测的尺度。 当样品进行聚类时，当样品进行聚类时，“靠近靠近”往往是往往是距离距离。同时对指标进行聚类时，根据同时对指

6、标进行聚类时，根据相关系相关系数或某种数或某种关联性度量来关联性度量来聚类。聚类。Q型型样品间的样品间的“相似性相似性”度量度量距离距离 设每个样品有 p 个指标, 观察值记为nixxxxTpiiii, 2 , 1,),(21(1)每个样品 可看成是 p 维空间的一个点。于是, 可用各点之间的距离来衡量各样品点之间的接近程度。 样品 和 之间的距离 , 一般应满足如下条件: () , 且 时当且仅当 ; () ; () ; 有时所用的距离不满足(), 但在广义的角度上仍称为距离。常用的距离有如下几种:ixixjx),(jixxd0),(jixxd0),(jixxdjixx ),(),(ijji

7、xxdxxd),(),(),(jkkijixxdxxdxxdpkjkikijxxd12112)(pkjkikijxxd 3、明考斯基距离、明考斯基距离(Minkowski)1、绝对距离（、绝对距离（Block距离）距离）2、欧氏距离、欧氏距离(Euclidean distance)qpkqjkikijxxd11)(4、切比雪夫距离、切比雪夫距离(Chebychev)jkikpkijxxd1max)(6.马氏距离马氏距离5.数据的标准化数据的标准化,ijjijjxxxS jjxSj其中 和是第 个指标的均值和样本标准差以上距离与各变量的量纲有关，为了消除量纲的以上距离与各变量的量纲有关，为了消除

8、量纲的影响，可对数据标准化。影响，可对数据标准化。21( )( )( )( )()()()ijijijdMxxSxx 例例1 欧洲各国的语言有许多相似之处，有的十分欧洲各国的语言有许多相似之处，有的十分相似。为了研究这些语言的历史关系，也许通过比较相似。为了研究这些语言的历史关系，也许通过比较他们数字的表达式比较恰当。表列举出英语，挪威语，他们数字的表达式比较恰当。表列举出英语，挪威语，丹麦语，荷兰语，德语，法语，西班牙语，意大利语，丹麦语，荷兰语，德语，法语，西班牙语，意大利语，波兰语，匈牙利语和芬兰语的波兰语，匈牙利语和芬兰语的1,2,10的拼法，希望的拼法，希望计算这计算这11种语言之间

9、的语言的距离种语言之间的语言的距离.11种欧洲语言的数词选择适用的距离选择适用的距离 在聚类分析中通常要结合实际问题来选择在聚类分析中通常要结合实际问题来选择适用适用的的距离距离, , 有时应根据实际问题定义新的距离有时应根据实际问题定义新的距离, , 显然，本例无法直接用上述公式来计算距离。但显然，本例无法直接用上述公式来计算距离。但可以发现可以发现前三种文字前三种文字( (英、挪、丹英、挪、丹) )很相似很相似, , 特别是每个单词的第特别是每个单词的第一一个字母。可以用个字母。可以用1010个数词个数词中中第一个第一个字母字母不同不同的的个数个数来定义两种语言之间的距离。来定义两种语言之

10、间的距离。例如：英语和挪威语中只有例如：英语和挪威语中只有1 1和和8 8的第一个字母不同的第一个字母不同, , 则它们之间的距离为则它们之间的距离为2 2。E N Da Du G Fr Sp I P H Fi E 0 N 2 0Da 2 1 0Du 7 5 6 0G 6 4 5 5 0Fr 6 6 6 9 7 0Sp 6 6 5 9 7 2 0I 6 6 5 9 7 1 1 0P 7 7 6 10 8 5 3 4 0H 9 8 8 8 9 10 10 10 10 0Fi 9 9 9 9 9 9 9 9 9 8 02112121nkkjnkkinkkjkiijxxxxCnknkjkjikink

11、jkjikiijxxxxxxxxr11221)()()(1、夹角余弦、夹角余弦2、相关系数、相关系数R型聚类统计量型聚类统计量 对两个指标之间的相似程度用对两个指标之间的相似程度用相似系数相似系数来刻划，来刻划，相似系数相似系数绝对对值越接近于绝对对值越接近于1，表示指标间的关系，表示指标间的关系越密切，绝对值越接近于越密切，绝对值越接近于0，表示指标间的关系越，表示指标间的关系越疏远疏远. 三三 系统聚类分析系统聚类分析1. 1. 系统聚类分析的基本思想是：系统聚类分析的基本思想是： 距离相近的样品（或变量）先聚成类，距离距离相近的样品（或变量）先聚成类，距离相远的相远的后后聚成类，过程一直

12、下去，每个样品（或聚成类，过程一直下去，每个样品（或变量）总能聚到合适的类中。变量）总能聚到合适的类中。 系统聚类分析过程是：系统聚类分析过程是： 假设总共有假设总共有n个样品（或变量），第一步将每个样品（或变量），第一步将每个样品（或变量）独自聚成一类，共有个样品（或变量）独自聚成一类，共有n类；类； 第二步根据所确定的样品（或变量）第二步根据所确定的样品（或变量）“距离距离”公式，公式， 将距离较近的两个样品（或变量）聚合为一类，其将距离较近的两个样品（或变量）聚合为一类，其他样品（或变量）仍各自聚为一类，共有他样品（或变量）仍各自聚为一类，共有n1类；类； 第三步将第三步将“距离距离”最

13、近的两个类进一步聚成一类，共最近的两个类进一步聚成一类，共聚成聚成n2类；类；以上步骤一直进行下去，以上步骤一直进行下去，最后最后将所有的样品或变量）聚成一类。将所有的样品或变量）聚成一类。 将整个分类系统地画成一张谱系图，所以有时将整个分类系统地画成一张谱系图，所以有时系统聚类分析系统聚类分析也叫也叫谱系聚类分析谱系聚类分析。2.2. 类间距离类间距离 首先定义类与类之间地距离，又类间的距离定义首先定义类与类之间地距离，又类间的距离定义 不同产生不同的系统聚类分析。常见的类间的距离不同产生不同的系统聚类分析。常见的类间的距离有有法。它们的归类步骤基本是一致的。法。它们的归类步骤基本是一致的。

14、8种之多，与之相应的系统聚类分析也有种之多，与之相应的系统聚类分析也有8种之多、种之多、分别为最短距离法、最长距离法、中间距离法、重心分别为最短距离法、最长距离法、中间距离法、重心法、类平均法、可变类平均法、可变法和离差平方和法、类平均法、可变类平均法、可变法和离差平方和 用 i , j 表示样品 。用 表示 与 之间的距离, 用 与 表示两个类, 所包含的样品数分别为 与 之间的距离用 表示。下面给出四种最常用的类与类之间距离的定义。jixx ,ixijdjxqGpGpGqGpnqn),(qpGGD1 、最短距离（、最短距离（Nearest Neighbor)x21x12x22x1113dq

15、pijqppqGjGidGGDD,min),(即定义 与 之间的距离为 与 中最近的两个样品的距离。 类与类之间的最短距离有如下的递推公式。设 由 与 合并而成, 则 与其它类 的最短距离为pGqGpGqGpGrGqGrG),(qpkGkkqijkpijkrijkrGjGidGjGidGjGidGGD,min,minmin,min),(),(),(minkqkpGGDGGD 1 1、根据样品的特征，规定样品之间的距离根据样品的特征，规定样品之间的距离 ，共，共有有 个。将所有列表，记为个。将所有列表，记为D（0 0）表，该表是一张）表，该表是一张对称表。所有的样本点各自为一类。对称表。所有的样

16、本点各自为一类。 2、选择选择D D（0 0）表中最小的非零数，不妨假设）表中最小的非零数，不妨假设 ，于是将于是将 和和 合并为一类，记为合并为一类，记为 。pqdpGqGqprGGG，2nCijd开始各样本自成一类开始各样本自成一类最短距离法进行聚类分析的步骤如下：最短距离法进行聚类分析的步骤如下： 3、利用递推公式计算新类与其它类之间的、利用递推公式计算新类与其它类之间的距离。分别距离。分别删除删除D（0）表的第）表的第p，q行和第行和第p，q列，并新增一行和一列添上的结果，列，并新增一行和一列添上的结果，产生产生D（1）表。）表。 4、在、在D（1）表再选择）表再选择最小最小的非零数，其的非零数，其对应的两类有构成新类，再利用递推公式对应的两类有构成新类，再利用递推公式计算新类与其它类之间的距离。分别删除计算新类与其它类之间的距离。分别删除D（1）表的相应的行和列，并新增一行和一）表的相应的行和列，并新增一行和一列添上的新类和旧类之间的距离。结果，列添上的新类和旧类之间的距离。结果，产生产生D（2）表。类推直至所有的样本点归）表。类推直至所有的样本点归为一类为止。为一类为止。最