《模式识别1非监督学习方法聚类分析边肇祺第二版》由会员分享，可在线阅读，更多相关《模式识别1非监督学习方法聚类分析边肇祺第二版（55页珍藏版）》请在金锄头文库上搜索。
1、第一章第一章非监督学习方法：聚非监督学习方法：聚类分析类分析根本概念根本概念相似性测度与聚类准那么相似性测度与聚类准那么基于试探的聚类搜索算法基于试探的聚类搜索算法系统聚类系统聚类分解聚类分解聚类动态聚类动态聚类1.1根本概念根本概念v分类与聚类的区别分类与聚类的区别v分类：用类别的样本训练集来设计分类分类：用类别的样本训练集来设计分类器监督学习器监督学习v聚类集群：用事先不知样本的类别，聚类集群：用事先不知样本的类别，而利用样本的先验知识来构造分类器而利用样本的先验知识来构造分类器无监督学习无监督学习v举例：小孩区分桔子和苹果举例：小孩区分桔子和苹果v相似性与距离聚类相似性与距离聚类v相似性
2、：相似性：模式之间具有一定的相似性，这既表现在实物的显著特征上，也表现在经过抽象以后特征空间内的特征向量的分布状态上。v聚类分析定义：聚类分析定义：对一批没有标出类别的模式样本集，按照样本之间的相似程度分类，相似的归为一类，不相似的归为另一类，这种分类称为聚类分析，也称为无监督分类。v分分类依据：依据：一个样本的特征向量相当于特征空间中的一点，整个模式样本集合的特征向量可以看成特征空间的一些点，点之间的距离函数可以作为模式相似性的度量，并以此作为模式的分类依据。v聚类分析是按不同对象之间的差异，根据距距离函数的规律离函数的规律进行模式分类的。v距离函数的定义v特征向量的特性 v聚类分析的有效性
3、：聚类分析方法是否有效，聚类分析的有效性：聚类分析方法是否有效，与模式特征向量的分布形式有很大关系。与模式特征向量的分布形式有很大关系。v假设向量点的分布是一群一群的，同一群样假设向量点的分布是一群一群的，同一群样本密集距离很近，不同群样本距离很远，本密集距离很近，不同群样本距离很远，那么很容易聚类；那么很容易聚类；v假设样本集的向量分布聚成一团，不同群的假设样本集的向量分布聚成一团，不同群的样本混在一起，那么很难分类；样本混在一起，那么很难分类；v对具体对象做聚类分析的关键是选取适宜的对具体对象做聚类分析的关键是选取适宜的特征。特征选取得好，向量分布容易区分，特征。特征选取得好，向量分布容易
4、区分，选取得不好，向量分布很难分开。选取得不好，向量分布很难分开。v特征空间维数特征空间维数v特征信息的冗余性：在对象分析和特征特征信息的冗余性：在对象分析和特征提取中，往往会提取一些多余的特征，提取中，往往会提取一些多余的特征，以期增加对象识别的信息量。以期增加对象识别的信息量。v高维特征空间分析的复杂性：特征空间高维特征空间分析的复杂性：特征空间维数越高，聚类分析的复杂性就越高维数越高，聚类分析的复杂性就越高v高维特征空间降维高维特征空间降维v降维方法：降维方法：v相关分析：特征向量的相关矩阵相关分析：特征向量的相关矩阵R，分析，分析相关性相关性v主成分分析：以正交变换为理论根底主成分分析
5、：以正交变换为理论根底v独立成分分析：以独立性为根底独立成分分析：以独立性为根底v特征的表示特征的表示v数值表示：对于实际问题，为了便于计算数值表示：对于实际问题，为了便于计算机分析和计算，特征必须进行量化。对不机分析和计算，特征必须进行量化。对不同的分析对象，量化方法是不一样的。同的分析对象，量化方法是不一样的。v连续量的量化：用连续量来度量的特征，连续量的量化：用连续量来度量的特征，只需取其量化值，如长度、重量等。只需取其量化值，如长度、重量等。v分级量的量化：度量分析对象等级的量，分级量的量化：度量分析对象等级的量，用有序的离散数字进行量化，比方学生成用有序的离散数字进行量化，比方学生成
6、绩的优，良，中，差可用绩的优，良，中，差可用1，2，3，4等量等量化表示。化表示。v定性量的量化：定性指标，没有数量关系，定性量的量化：定性指标，没有数量关系，也没有次序要求。比方，性别特征：男和也没有次序要求。比方，性别特征：男和女，可用女，可用0和和1来进行表示。来进行表示。v两类模式分类的实例两类模式分类的实例v区分一摊黑白围棋子区分一摊黑白围棋子v选颜色作为特征进行分类，用选颜色作为特征进行分类，用“1代表代表白，白，“0代表黑，那么很容易分类；代表黑，那么很容易分类；v选大小作为特征进行分类，那么白子和选大小作为特征进行分类，那么白子和黑子的特征相同，不能分类。黑子的特征相同，不能分
7、类。1.2相似性相似性测度和聚度和聚类准那么准那么一、相似性的测度一、相似性的测度欧欧氏氏距距离离: : 表表征征两两个个模模式式样样本本在在特特征征空空间间中的中的EuclidEuclid距离，距离，模式模式X X和和Z Z间的距离愈小，那么愈相似间的距离愈小，那么愈相似注意：注意：X X和和Z Z的量纲必须一致的量纲必须一致 消消除除量量纲纲不不一一致致对对聚聚类类的的影影响响：特特征征数数据据的的正正那那么么化化也也称称标标准准化化、归归一一化化，使特征变量与量纲无关。使特征变量与量纲无关。v马氏氏距距离离：表表征征模模式式向向量量X X与与其其均均值向向量量m m之之间的距离平方，的距
8、离平方，C C是模式是模式总体的体的协方差矩方差矩阵，v引引入入协方方差差矩矩阵，排排除除了了样本本之之间的的相相关关性性。 欧欧式式距距离离中中，如如果果特特征征向向量量中中某某一一分分量量的的值非非常常大大，那那么么就就会会掩掩盖盖值小小的的项所所起起到到的的作作用用，这是是欧欧式式距距离离的的缺缺乏乏；当当采采用用马氏氏距距离离，就就可可以以屏屏蔽蔽这一一点点。因因为相相关关性性强强的的一一个个分分量量，对应于于协方方差差矩矩阵C C中中对角角线上上的的那那一一项的的值就就会大一些。再将会大一些。再将这一一项取倒数，减小取倒数，减小该影响。影响。v当当协方方差差为对角角矩矩阵时，各各特特
9、征征分分量量相相互互独独立立；当当协方方差差为单位位矩矩阵时，马氏氏距距离离和和欧欧氏氏距距离离相同。相同。其中 分别是样本向量的第k个分量；当m2时，明氏距离就是欧氏距离；当m1时，就是街坊city block)距离： v一般化的明氏距离一般化的明氏距离v角度相似性函数角度相似性函数：表征了模式向量x x和z z之间夹角的余弦，反映了几何上的相似性，v当坐标系旋转或者尺度变换，夹角余弦测度均保持不变对位移和线性变换不成立v如果x和z的分量用二值来表示，0表示不具有某种特征，1表示具有某种特征，那么夹角余弦测度表示x和z具有共有特征数目的相似性测度。二、聚类准那么确实定二、聚类准那么确实定v试
10、探法探法v凭凭直直观和和经验，针对实际问题选择相相似似性性测度度并并确确定定此此相相似似性性测度度的的阈值，然然后后选择一一定定的的训练样本本来来检验测度度和和阈值的的可可靠靠程程度度，最最后后按按最最近近邻规那那么么指定某些模式指定某些模式样本属于某一个聚本属于某一个聚类类别。v举例例：对于于欧欧氏氏距距离离，它它反反映映了了样本本间的的近近邻性性，但但将将一一个个样本本分分到到不不同同类别时，还必必须规定定一一距距离离测度度的的阈值准准那那么作么作为聚聚类的判的判别准那么准那么v聚聚类准那么函数法准那么函数法v聚聚类就是将就是将样本本进行行组合分合分类以使以使类别可可分性分性为最大，因此聚
11、最大，因此聚类准那么准那么应是反映是反映类别间相似性或可分性的函数；同相似性或可分性的函数；同时，类别又由一个个又由一个个样本本组成，因此成，因此类别的可分性与的可分性与样本本间的差异性直接相关。基于此，聚的差异性直接相关。基于此，聚类准准那么函数那么函数J，应是模式是模式样本集本集x和模式和模式类别Sj,j=1,2,c的函数，即的函数，即vJ J代表了分属于代表了分属于c c个聚类类别的全部模式样本个聚类类别的全部模式样本与其对应类别模式均值之间的误差平方和；与其对应类别模式均值之间的误差平方和；v对于不同的聚类形式，对于不同的聚类形式， J J值是不同的，聚类值是不同的，聚类的目的是：使的
12、目的是：使J J值到达极小；值到达极小；v由此可见：聚类分析转化为寻找准那么函数由此可见：聚类分析转化为寻找准那么函数极值的最优化问题；极值的最优化问题；v此种聚类方法通常称为最小方差划分，适用此种聚类方法通常称为最小方差划分，适用于各类样本密集且数目相差不多，而不同类于各类样本密集且数目相差不多，而不同类间的样本又明显分开的情况图例解释间的样本又明显分开的情况图例解释把握类内距离与类间距离的问题；把握类内距离与类间距离的问题；v聚类准那么函数有许多其他形式。聚类准那么函数有许多其他形式。1.3基于试探的聚类搜索算法基于试探的聚类搜索算法一、按最邻近规那么的简单试探法一、按最邻近规那么的简单试
13、探法 给给N N个待分类的模式样本个待分类的模式样本 ，要求按距离阈值，要求按距离阈值T T分类到聚类中心分类到聚类中心算法过程：算法过程：Step 1Step 1：取任意的样本：取任意的样本xixi作为一聚类中的初作为一聚类中的初始值，如令始值，如令z1=x1z1=x1，计算，计算假设假设D21D21T T，确定一新的聚类中心，确定一新的聚类中心z2=x2z2=x2否那么否那么x2x2以以z1z1为中心的聚类；为中心的聚类；vStep 2：假设已有聚类中心z1和z2，计算v 假设D31T和D32T ，那么确定一新的聚类中心z3=x3；vStep i： v讨论讨论v这种方法的优点：计算简单，假
14、设模式样本的集这种方法的优点：计算简单，假设模式样本的集合分布的先验知识，那么可获得较好的聚类结果。合分布的先验知识，那么可获得较好的聚类结果。v在实际中，对于高维模式样本很难获得准确的先在实际中，对于高维模式样本很难获得准确的先验知识，因此只能选用不同的阈值和起始点来试验知识，因此只能选用不同的阈值和起始点来试探，并对结果进行验证。探，并对结果进行验证。v这种方法在很大程度上依赖于以下因素：这种方法在很大程度上依赖于以下因素：v第一个聚类中心的位置初始化问题第一个聚类中心的位置初始化问题v待分类模式样本排列次序聚类样本的选择问题待分类模式样本排列次序聚类样本的选择问题v距离阈值距离阈值T的大
15、小判决准那么问题的大小判决准那么问题v样本分布的几何性质样本的固有特性问题样本分布的几何性质样本的固有特性问题二、最大最小距离算法二、最大最小距离算法根本思想：根据实际问题选择距离函数，根本思想：根据实际问题选择距离函数，以试探类间距离为最大作为预选出聚类中以试探类间距离为最大作为预选出聚类中心的条件。核心就是：最大类间距离，最心的条件。核心就是：最大类间距离，最小类内距离。小类内距离。算法过程描述：先按照距离最大最小的方算法过程描述：先按照距离最大最小的方法预选出聚类中心，在按照按最邻近规那法预选出聚类中心，在按照按最邻近规那么将模式分类到聚类中心。对于么将模式分类到聚类中心。对于N N个待
16、分类个待分类的模式样本的模式样本 ，要求按最大最小距离法分类到聚类中心，要求按最大最小距离法分类到聚类中心 。Step 1Step 1：选任意一模式样本：选任意一模式样本xixi作为第一聚作为第一聚类中心类中心z1z1vStep2：选离：选离z1最远距离的样本最远距离的样本xj作为第二聚作为第二聚类中心类中心z2vStep3：逐个计算各模式样本：逐个计算各模式样本v与与之间之间的距离，并选出其中的最小距离。的距离，并选出其中的最小距离。vStep4：在所有模式样本的最小值中选出最大：在所有模式样本的最小值中选出最大距离，假设该最大值到达距离，假设该最大值到达的一定分数比值的一定分数比值以上，那
17、么将相应的样本取为第三聚类中心。以上，那么将相应的样本取为第三聚类中心。vStepi：v算法性能分析：算法复杂度增加，在选聚类算法性能分析：算法复杂度增加，在选聚类中心过程中消耗较大的资源。中心过程中消耗较大的资源。1.4系统聚类系统聚类v系统聚类：先把每个样本作为一类，然后根据它们系统聚类：先把每个样本作为一类，然后根据它们间的相似性或相邻性聚合，类别由多到少，直到获间的相似性或相邻性聚合，类别由多到少，直到获得适宜的分类要求为止；相似性、相邻性用距离表得适宜的分类要求为止；相似性、相邻性用距离表示。聚合的关键就是每次迭代中形成的聚类之间以示。聚合的关键就是每次迭代中形成的聚类之间以及它们和
18、样本之间距离的计算，不同的距离函数会及它们和样本之间距离的计算，不同的距离函数会得到不同结果。得到不同结果。v两类间距离计算准那么：两类间距离计算准那么：(注意理解注意理解v1.最短距离：两类中相距最近的两样本间的距离最短距离：两类中相距最近的两样本间的距离v 2. 最长距离 ：两类中相距最远的两个样本间的距离。v 3. 中间距离：最短距离和最长距离都有片面性，因此有时用中间距离。设1类和23类间的最短距离为d12，最长距离为d13， 23类的长度为d23，那么中间距离为：v上式推广为一般情况：v4. 重心距离：均值间的距离v5. 类平均距离：两类中各个元素两两之间的距离平方相加后取平均值 v
19、6. 离差平方和：v设N个样本原分q类，那么定义第i类的离差平方和为：v离差平方和增量：设样本已分成p,q两类，假设把p,q合为r类，那么定义离差平方增量：v算法过程描述：算法过程描述：Step1：初始距离矩阵的计算：初始距离矩阵的计算D(0)v说明：说明：1距离矩阵元素的值是类与类之间的距距离矩阵元素的值是类与类之间的距离，距离的定义有多种。离，距离的定义有多种。2距离矩阵，是对称矩距离矩阵，是对称矩阵。对角上线的元值表示同类之间的距离，即为阵。对角上线的元值表示同类之间的距离，即为0。vStep2：对于第：对于第n次迭代的距离矩阵次迭代的距离矩阵D(n)进行聚合进行聚合 说明：距离矩阵中选
20、择距离最小的，如果有相同的可以任选其中一个，要忽略对角线上的元素；也可以把相同的全部聚合。Step3：根据第n次聚合结果，计算合并后的新类别之间的距离矩阵D(n+1) 说明：合并类的距离计算应该符合距离的运算规那么。假设距离反映的是两类的重心距离，那么合并后，应该仍然反映的重心的距离。Step4：收敛性判决距离阈值D的设定 说明：算法的收敛条件判断准那么确实定。例例1：如以下图所示简单的一维情况：如以下图所示简单的一维情况1、设全部样本分为、设全部样本分为6类，类，2、计算距离矩阵、计算距离矩阵D(0)1234561029031160449166405254364066425811903、求最
21、小元素：4、把1, 3合并7=(1,3)4, 6合并8=(4,6)5、作距离矩阵D(1)，按最小距离准那么7285702908491605254406、假设合并的类数没有到达要求，转3。否那么停止。3、求最小元素：4、8, 5, 2合并, 9=2,5,4,61.5分解聚类分解聚类v分解聚类：把全部样本作为一类，然后根据相似性、相邻性分解。v目标函数为：两类均值方差 N：总样本数， ：1类样本数 ：2类样本数，分解聚类框图分解聚类框图初始分类调整分类方案最终结果目标函数达到最优？例例2：21个样本，每个样本取二个特征，原始个样本，每个样本取二个特征，原始资料矩阵如下表：资料矩阵如下表：样本号 1
22、2345678910x10022445667x2655343121011 12 13 14 15 16 17 18 19 20 21-4-2-3-3-5100-1-1-3322021-1-2 -1-3-5目标函数解：第一次分类时计算所有样本，分别划到 时的E值，找出最大E值对应的样本。 1、开始时， 2、分别计算当 划入 时的E值把 划入时有 然后再计算把 划入 时对应的E值，找出一个最大的E值。 一直计算下去 把 划为 的E值最大。 再继续进行第二，第三次迭代计算出 E(2) , E(3) , 次数 E值 第10次迭代 划入 时，E最大。于是分成以下两类：每次分类后要重新计算 的值。可用以下
23、递推公式：1.6动态聚类动态聚类兼顾系统聚类兼顾系统聚类和分解聚类和分解聚类一、动态聚类方法概要一、动态聚类方法概要先选定某种距离作为样本间的相似性先选定某种距离作为样本间的相似性度量度量;确定评价聚类结果的准那么函数确定评价聚类结果的准那么函数;给出某种初始分类，用迭代法找出使给出某种初始分类，用迭代法找出使准那么函数取极值的最好的聚类结果。准那么函数取极值的最好的聚类结果。选代表点初始分类分类合理否最终分类修改分类YN动态聚类框图动态聚类框图二、代表点种子点的选取方法：代二、代表点种子点的选取方法：代表点就是初始分类的聚类中心数表点就是初始分类的聚类中心数K凭经验选代表点，根据问题的性质、
24、凭经验选代表点，根据问题的性质、数据分布，从直观上看来较合理的代表数据分布，从直观上看来较合理的代表点点K;将全部样本随机分成将全部样本随机分成K类，计算每类，计算每类重心，把这些重心作为每类的代表点类重心，把这些重心作为每类的代表点;用前用前K个样本点作为代表点。个样本点作为代表点。 按密度大小选代表点： 以每个样本作为球心，以d为半径做球形；落在球内的样本数称为该点的密度，并按密度大小排序。首先选密度最大的作为第一个代表点，即第一个聚类中心。再考虑第二大密度点，假设第二大密度点距第一代表点的距离大于d1人为规定的正数那么把第二大密度点作为第二代表点，否那么不能作为代表点，这样按密度大小考察
25、下去，所选代表点间的距离都大于d1。d1太小，代表点太多，d1太大，代表点太小，一般选d12d。对代表点内的密度一般要求大于T。T0为规定的一个正数。三、初始分类和调整三、初始分类和调整选一批代表点后，代表点就是聚类中心选一批代表点后，代表点就是聚类中心，计算其它样本到聚类中心的距离，把所有，计算其它样本到聚类中心的距离，把所有样本归于最近的聚类中心点，形成初始分类，样本归于最近的聚类中心点，形成初始分类，再重新计算各聚类中心，称为成批处理法。再重新计算各聚类中心，称为成批处理法。选一批代表点后，依次计算其它样本的选一批代表点后，依次计算其它样本的归类，当计算完第一个样本时，把它归于最归类，当
26、计算完第一个样本时，把它归于最近的一类，形成新的分类。再计算新的聚类近的一类，形成新的分类。再计算新的聚类中心，再计算第二个样本到新的聚类中心的中心，再计算第二个样本到新的聚类中心的距离，对第二个样本归类。即每个样本的归距离，对第二个样本归类。即每个样本的归类都改变一次聚类中心。此法称为逐个处理类都改变一次聚类中心。此法称为逐个处理法。法。直接用样本进行初始分类，先规定距离直接用样本进行初始分类，先规定距离d，把第一个样品作为第一类的聚类中心，把第一个样品作为第一类的聚类中心，考察第二个样本，假设第二个样本距第一个考察第二个样本，假设第二个样本距第一个聚类中心距离小于聚类中心距离小于d，就把第
27、二个样本归于，就把第二个样本归于第一类，否那么第二个样本就成为第二类的第一类，否那么第二个样本就成为第二类的聚类中心，再考虑其它样本，根据样本到聚聚类中心，再考虑其它样本，根据样本到聚类中心距离大于还是小于类中心距离大于还是小于d，决定分裂还是，决定分裂还是合并。合并。最正确初始分类：如下图，随着初始分类K的增大，准那么函数下降很快，经过拐点A后，下降速度减慢。拐点A就是最正确初始分类。四、四、K-均值算法：成批处理法均值算法：成批处理法例：有例：有20个样本，每个样本有个样本，每个样本有2个特征，数据分布个特征，数据分布如以下图如以下图第一步：令K=2，选初始聚类中心为样本序号x1x2x3x
28、4x5x6x7x8x9x10特征x10101212367特征x20011122266x11x12x13x14x15x16x17x18x19x2086789789896777788899因为因为所以所以，同理，同理同样，把其他所有样本同样，把其他所有样本与两个聚类中心的距与两个聚类中心的距离计算出来，可判断得离计算出来，可判断得因此，可分类两大类因此，可分类两大类第三步：根据新分成的两类建立新的聚类中心第四步：转第二步。第二步：重新计算 到Z1(2) , Z2(2) 的距离，把它们归为最近聚类中心，重新分为两类，第三步，更新聚类中心第四步，第二步，第三步，更新聚类中心v说明：说明： (1)K是指
29、需要分成K类，均值是指每类的中心,就是该类所有样本的平均值，不一定就有某个样本在这个位置上。 (2)算法的收敛性判别：前后两次迭代的结果，也就是每迭代分类后，分类都是一样的，此时停止。 (3)K值和初始聚类中心对分类的结果影响很大。通常需要其它的算法来确定这两个的选取。v讨论讨论vK-均值算法的结果受如下选择的影响：均值算法的结果受如下选择的影响：v所选聚类的数目所选聚类的数目v聚类中心的初始分布聚类中心的初始分布v模式样本的几何性质模式样本的几何性质v读入次序读入次序v在实际应用中，需要试探不同的在实际应用中，需要试探不同的K值和选值和选择不同的聚类中心的起始值。择不同的聚类中心的起始值。v如果模式样本可以形成假设干个相距较如果模式样本可以形成假设干个相距较远的孤立的区域分布，一般都能得到较远的孤立的区域分布，一般都能得到较好的收敛效果。好的收敛效果。vK-均值算法比较适合于分类数目的情况。均值算法比较适合于分类数目的情况。作业作业1. 给定5个6维模式样本如下，试按最小距离准那么进行系统聚类分析。2.十个样本，每个样本2个特征，数据如下：用K-均值算法分成3类采用成批法和逐个法。样本序号1 2 3 4 5 6 7 8 9 10x10 1 2 4 5 5 6 1 1 1 x20 1 1 3 3 4 5 4 5 6
