非监督学习方法之聚类分析.pptx

《非监督学习方法之聚类分析.pptx》由会员分享，可在线阅读，更多相关《非监督学习方法之聚类分析.pptx（54页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第一章第一章 非监督学习方法：聚非监督学习方法：聚类分析类分析 基本概念基本概念 相似性测度与聚类准则相似性测度与聚类准则 基于试探的聚类搜索算法基于试探的聚类搜索算法 系统聚类系统聚类 分解聚类分解聚类 动态聚类动态聚类1.1 基本概念基本概念v分类与聚类的区别分类与聚类的区别v分类：用已知类别的样本训练集来设计分类器（监督学习）v聚类（集群）：用事先不知样本的类别，而利用样本的先验知识来构造分类器（无监督学习）v相似性与距离聚类相似性与距离聚类v相似性：相似性：模式之间具有一定的相似性，这既表现在实物的显著特征上，也表现在经过抽象以后特征空间内的特征向量的分布状态上。v聚类分析定义：聚类分

2、析定义：对一批没有标出类别的模式样本集，按照样本之间的相似程度分类，相似的归为一类，不相似的归为另一类，这种分类称为聚类分析，也称为无监督分类。v分类依据：分类依据：一个样本的特征向量相当于特征空间中的一点，整个模式样本集合的特征向量可以看成特征空间的一些点，点之间的距离函数可以作为模式相似性的度量，并以此作为模式的分类依据。v聚类分析是按不同对象之间的差异，根据距距离函数的规律离函数的规律进行模式分类的。v距离函数的定义v特征向量的特性v聚类分析的有效性：聚类分析的有效性：聚类分析方法是否有效，与模式特征向量的分布形式有很大关系。v若向量点的分布是一群一群的，同一群样本密集（距离很近），不同

3、群样本距离很远，则很容易聚类；v若样本集的向量分布聚成一团，不同群的样本混在一起，则很难分类；v对具体对象做聚类分析的关键是选取合适的特征。特征选取得好，向量分布容易区分，选取得不好，向量分布很难分开。v特征空间维数特征空间维数v特征信息的冗余性特征信息的冗余性：在对象分析和特征提取中，往往会提取一些多余的特征，以期增加对象识别的信息量。v高维特征空间分析的复杂性：高维特征空间分析的复杂性：特征空间维数越高，聚类分析的复杂性就越高v高维特征空间降维v降维方法：v相关分析：特征向量的相关矩阵R，分析相关性v主成分分析：以正交变换为理论基础v独立成分分析：以独立性为基础v特征的表示特征的表示v数值

4、表示：数值表示：对于实际问题，为了便于计算机分析和计算，特征必须进行量化。对不同的分析对象，量化方法是不一样的。v连续量的量化：用连续量来度量的特征，只需取其量化值，如长度、重量等。v分级量的量化：度量分析对象等级的量，用有序的离散数字进行量化，比如学生成绩的优，良，中，差可用1，2，3，4等量化表示。v定性量的量化：定性指标，没有数量关系，也没有次序要求。比如，性别特征：男和女，可用0和1来进行表示。v两类模式分类的实例两类模式分类的实例 区分一摊黑白围棋子v选颜色颜色作为特征进行分类，用“1”代表白，“0”代表黑，则很容易分类；v选大小大小作为特征进行分类，则白子和黑子的特征相同，不能分类

5、。1.2 相似性测度和聚类准则相似性测度和聚类准则 一、相似性的测度一、相似性的测度v欧氏距离欧氏距离: : 表征两个模式样本在特征空间中的Euclid距离，v模式X和Z间的距离愈小，则愈相似v注意注意：X和Z的量纲必须一致 v消除量纲不一致对聚类的影响：特征数据的正则化（也称标准化、归一化），使特征变量与量纲无关。zxDv马氏距离：马氏距离：表征模式向量X与其均值向量m之间的距离平方，C是模式总体的协方差矩阵，v引入协方差矩阵，排除了样本之间的相关性。 欧式距离中，如果特征向量中某一分量的值非常大，那么就会掩盖值小的项所起到的作用，这是欧式距离的不足；当采用马氏距离，就可以屏蔽这一点。因为相

6、关性强的一个分量，对应于协方差矩阵C中对角线上的那一项的值就会大一些。再将这一项取倒数，减小该影响。v当协方差为对角矩阵时，各特征分量相互独立；当协方差为单位矩阵时，马氏距离和欧氏距离相同。21tDxmCxm1(,)()mmmijikjkkDxxx x其中 分别是样本向量的第k个分量；当m2时，明氏距离就是欧氏距离；当m1时，就是街坊（city block)距离： jkikxx ,ijx x为 模 式 样 本 向 量1(,)ijikjkkDxxx xv一般化的明氏距离一般化的明氏距离v角度相似性函数角度相似性函数：表征了模式向量x x和z z之间夹角的余弦，反映了几何上的相似性，v当坐标系旋转

7、或者尺度变换，夹角余弦测度均保持不变（对位移和线性变换不成立）v如果x x和z z的分量用二值来表示，0表示不具有某种特征，1表示具有某种特征，则夹角余弦测度表示x x和z z具有共有特征数目的相似性测度。( , )tSx zx zxz二、聚类准则的确定二、聚类准则的确定v 试探法试探法凭直观和经验，针对实际问题选择相似性测度并确定此相似性测度的阈值，然后选择一定的训练样本来检验测度和阈值的可靠程度，最后按最近邻规则指定某些模式样本属于某一个聚类类别。v举例：举例：对于欧氏距离，它反映了样本间的近邻性，但将一个样本分到不同类别时，还必须规定一距离测度的阈值准则作为聚类的判别准则v 聚类准则函数

8、法聚类准则函数法 聚类就是将样本进行组合分类以使类别可分性为最大，因此聚类准则应是反映类别间相似性（或可分性）的函数；同时，类别又由一个个样本组成，因此类别的可分性与样本间的差异性直接相关。基于此，聚类准则函数J J，应是模式样本集x和模式类别Sj, j=1,2,c的函数，即 ccjsjjJ, 12xmxvJ J代表了分属于c个聚类类别的全部模式样本与其对应类别模式均值之间的误差平方和；v对于不同的聚类形式， J J值是不同的，聚类的目的是：使J J值达到极小；v由此可见：聚类分析转化为寻找准则函数极值的最优化问题；v此种聚类方法通常称为最小方差划分，适用于各类样本密集且数目相差不多，而不同类

9、各类样本密集且数目相差不多，而不同类间的样本又明显分开的情况（图例解释）间的样本又明显分开的情况（图例解释）把握类内距离与类间距离的问题把握类内距离与类间距离的问题；v聚类准则函数有许多其他形式。聚类准则函数有许多其他形式。1.3 基于试探的聚类搜索算法基于试探的聚类搜索算法一、按一、按最邻近规则的简单试探法最邻近规则的简单试探法 给N个待分类的模式样本 ，要求按距离阈值T分类到聚类中心v算法过程：算法过程：vStep 1：取任意的样本x xi i作为一聚类中的初始值，如令z z1 1=x=x1 1，计算若D21T，确定一新的聚类中心z z2 2=x=x2 2否则x x2 2以z z1 1为中

10、心的聚类；Nxxx,2112,z z 1221zx DvStep 2：假如已有聚类中心z z1 1和z z2 2，计算 若D31T和D32T ，则确定一新的聚类中心z z3 3=x=x3 3；vStep i： 3131D xz3232D xzv讨论讨论v这种方法的优点：计算简单，若模式样本的集合分布的先验知识已知，则可获得较好的聚类结果。v在实际中，对于高维模式样本很难获得准确的先验知识，因此只能选用不同的阈值和起始点来试探，并对结果进行验证。v这种方法在很大程度上依赖于以下因素：v第一个聚类中心的位置（初始化问题初始化问题）v待分类模式样本排列次序（聚类样本的选择问题聚类样本的选择问题）v距

11、离阈值T的大小（判决准则问题判决准则问题）v样本分布的几何性质（样本的固有特性问题样本的固有特性问题）v最大最小距离算法最大最小距离算法v基本思想基本思想：根据实际问题选择距离函数，以试探类间距离为最大作为预选出聚类中心的条件。核心核心就是：就是最大类间距离，最小类内距离。v算法过程描述：先按照距离最大最小的方法预选出聚类中心，在按照按最邻近规则将模式分类到聚类中心（详细过程参考蔡元龙版模式识别.22）。 v算法性能分析：算法复杂度增加，在选聚类中心过程中消耗较大的资源。 1.4 系统聚类系统聚类v系统聚类：系统聚类：先把每个样本作为一类，然后根据它们间的相似性或相邻性聚合，类别由多到少，直到

12、获得合适的分类要求为止；相似性、相邻性用距离表示。聚合的关键就是每次迭代中形成的聚类之间以及它们和样本之间距离的计算，不同的距离函数会得到不同结果。v两类间距离计算准则两类间距离计算准则：v1. 最短距离：两类中相距最近的两样本间的距离ijxxpqdDqjpi minv 2. 最长距离 ：两类中相距最远的两个样本间的距离。v 3. 中间距离：最短距离和最长距离都有片面性，因此有时用中间距离。设1类和23类间的最短距离为d12，最长距离为d13， 23类的长度为d23，则中间距离为：v上式推广为一般情况：ijxxpqdDqjpi max2231321220412121dddd12312d0d23

13、d13d04121212231321220为参数，其中ddddv4. 重心距离：均值间的距离v5. 类平均距离：两类中各个元素两两之间的距离平方相加后取平均值 qjpipqxxijqpdNND221之间的距离类点与类点为样本数样本数其中jidNNqpijqqpp:,:v6. 离差平方和： 设N个样本原分q类，则定义第i类的离差平方和为： 离差平方和增量：设样本已分成p,q两类，若把p,q合为r类，则定义离差平方增量： 1() (),.iNqTiiiijijjiijiSxxxxxxNi其中 为样本 的均值为第 类的样本数。增量愈小，合并愈合理类的离差平方和为类的离差平方和类于分别为其中rrqpq

14、pqprpqSSSSSSD,)(2v算法过程描述：算法过程描述：Step1：初始距离矩阵的计算D(0)说明：（1）距离矩阵元素的值是类与类之间的距离，距离的定义有多种。（2）距离矩阵，是对称矩阵。对角上线的元值表示同类之间的距离，即为0。Step2：对于第n次迭代的距离矩阵D(n)进行聚合 说明：距离矩阵中选择距离最小的，如果有相同的可以任选其中一个，要忽略对角线上的元素。vStep3：根据第n次聚合结果，计算合并后的新类别之间的距离矩阵D(n+1) 说明：合并类的距离计算应该符合距离的运算规则。如，距离反映的是两类的重心距离，那么合并后，应该仍然反映的重心的距离。vStep4：收敛性判决（距

15、离阈值D的设定） 说明：算法的收敛条件判断准则的确定。例例1：如下图所示（简单的一维情况） 1、设全部样本分为6类，2、计算距离矩阵D(0)3G1G2G5G4G6Gx1234561029031160449166405254364066425811903、求最小元素：4、把1, 3合并7=(1,3)4, 6合并8=(4,6)5、作距离矩阵D(1)，按最小距离准则16431 dd7285702908491605254406、若合并的类数没有达到要求，转3。否则停止。3、求最小元素：4、8, 5, 2合并, 9=（2,5,4,6）45852 dd树状图152346789101.5 分解聚类分解聚类v

16、分解聚类：把全部样本作为一类，然后根据相似性、相邻性分解。v目标函数两类均值方差 )()(212121xxxxTNNNEN：总样本数， ：1类样本数 ：2类样本数，两类均值:,21xx1N2N分解聚类框图分解聚类框图初始分类调整分类方案最终结果目标函数达到最优先？NY例例2：已知21个样本，每个样本取二个特征，原始资料矩阵如下表：样本号 12345678910 x10022445667x2655343121011 12 13 14 15 16 17 18 19 20 21-4-2-3-3-5100-1-1-3322021-1-2 -1-3-5目标函数0)()(212121xxxxNNNET)3

17、33. 1714. 0()0(1x)00()0(2x0,21)0(2)0(1NN解：第一次分类时计算所有样本，分别划到 时的E值，找出最大E值对应的样本。 1、开始时，G2),.,(2121)0(1xxxG空G)0(2 2、分别计算当 划入G2 时的E值把 划入G2时有2121,.,xxx1x40.23)610.1(75.021120)60(),10.175.0()121()60()333.1714.0()333.1714.0(122)1(2)0(11)0(1)0(1)1(1ENxxxxx 然后再计算把 划入 时对应的E值，找出一个最大的E值。 一直计算下去 把 划为 的E值最大。 2132,

18、.,xxxG2G2x21),.,(2021)1(1xxxG)(21)1(2xG),65.19.0(1x1,20),53()1(2)1(12NNxE(1)=56.6再继续进行第二，第三次迭代计算出 E(2) , E(3) , 次数 E值 1 56.6 2 79.16 3 90.90 4 102.61 5 120.11 6 137.15 7 154.10 8 176.15 9 195.26 10 213.07 11 212.01G2G1x21x20 x18x14x15x19x11x13x12x17x16 第10次迭代 划入 时，E最大。于是分成以下两类：G2x17),.,(1610211xxxxG

19、 ),(212019181715,141312112xxxxxxxxxxG 每次分类后要重新计算 的值。可用以下递推公式：21, xx(1)()()()1111(1)()()()2222() /(1)() /(1)kkkkikkkkixxxxNxxxxN( )( )12(1)(1)( )121( )2( )( )12,kkkkkikkkxxkxxxGGNN是第 步对分时两类均值是下一次对分时把 从划到时的两类均值为二类样本数10 x2x3x4x15x11x12x13x14x16x17x18x19x7x8x9x20 x21x6x1x5x6543211234561X2X4321566543211.

20、6 动态聚类动态聚类兼顾系统聚兼顾系统聚类和分解聚类类和分解聚类一、动态聚类的方法概要一、动态聚类的方法概要 先选定某种距离作为样本间的相似性的度量; 确定评价聚类结果的准则函数; 给出某种初始分类，用迭代法找出使准则函数取极值的最好的聚类结果。选代表点初始分类分类合理否最终分类修改分类YN动态聚类框图动态聚类框图 二、代表点（种子点）的选取方法：二、代表点（种子点）的选取方法：代表点就是初始分类的聚类中心数k 凭经验选代表点，根据问题的性质、数据分布，从直观上看来较合理的代表点k; 将全部样本随机分成k类，计算每类重心，把这些重心作为每类的代表点; 用前k个样本点作为代表点。 按密度大小选代

21、表点： 以每个样本作为球心，以d为半径做球形；落在球内的样本数称为该点的密度，并按密度大小排序。首先选密度最大的作为第一个代表点，即第一个聚类中心。再考虑第二大密度点，若第二大密度点距第一代表点的距离大于d1（人为规定的正数）则把第二大密度点作为第二代表点，否则不能作为代表点，这样按密度大小考察下去，所选代表点间的距离都大于d1。d1太小，代表点太多，d1太大，代表点太小，一般选d12d。对代表点内的密度一般要求大于T。T0为规定的一个正数。三、初始分类和调整三、初始分类和调整 选一批代表点后，代表点就是聚类中心，计算其它样本到聚类中心的距离，把所有样本归于最近的聚类中心点，形成初始分类，再重

22、新计算各聚类中心，称为成批处理法。 选一批代表点后,依次计算其它样本的归类，当计算完第一个样本时，把它归于最近的一类，形成新的分类。再计算新的聚类中心，再计算第二个样本到新的聚类中心的距离，对第二个样本归类。即每个样本的归类都改变一次聚类中心。此法称为逐个处理法。 直接用样本进行初始分类，先规定距离d,把第一个样品作为第一类的聚类中心，考察第二个样本，若第二个样本距第一个聚类中心距离小于d，就把第二个样本归于第一类，否则第二个样本就成为第二类的聚类中心，再考虑其它样本，根据样本到聚类中心距离大于还是小于d，决定分裂还是合并。 最佳初始分类：如图所示，随着初始分类k的增大，准则函数下降很快，经过

23、拐点A后，下降速度减慢。拐点A就是最佳初始分类。准则函数JK最佳初始分类A拐点03217654下降快下降慢四、四、K-均值算法：成批处理法均值算法：成批处理法例：例：已知有20个样本，每个样本有2个特征，数据分布如下图第一步：令K=2，选初始聚类中心为TTxZxZ)0,1()1(;)0,0()1(2211样本序号x1x2x3x4x5x6x7x8x9x10特征x10101212367特征x20011122266x11x12x13x14x15x16x17x18x19x20867897898967777888991543126654321X101099887702X1x2x3x4x5x6x7x8x9

24、x10 x11x12x13x14x15x16x17x18x19x20 x10001)1 ()1 ()1 ()1 (10100)1 (00000)1 (121121112111）（所以因为）（）（第二步：ZxZxZxZxZxZx18,2),.,()1 (),()1 ()1 (.)1 (, 1)1 (2)1 ()1 (,2)1 (1)1 ()1 (,)1 ()1 (0)01()01()1 (2120542131122065206524241413231322221222NNxxxxGxxGZxxxxxxZxZxZxZxZxZxZxZxZxZx二、一、因此分为两类：都属于、离计算出来，判断与第二个聚

25、类中心的距、同样把所有同理所以因为第三步：根据新分成的两类建立新的聚类中心TGxxxXNZ)5 . 0 , 0()10(21)10()00(21)(211)2(31)1(111TGxxxxxXNZ)33.5,67.5().(1811)2(20542)1(222第四步：转第二步。第二步：重新计算 到z1(2) , z2(2) 的距离，把它们归为最近聚类中心，重新分为两类，)(2 , 1),1 ()2(新旧聚类中心不等JZZJJ2021,.,xxx第三步，更新聚类中心TGxxxxxXNZ)13. 1 ,25. 1 ().(811) 3(8321)2(111TGxxxxXNZ)33. 7 ,67.

26、7().(1211) 3(20109)2(2228),.,()2(18211NxxxG12),.,()2(2201092NxxxG第四步，第二步，第三步，更新聚类中心转第二步因, 2 , 1),2() 3(jZZjj1220121220112829102012,.,(3),(3),.,(4)( ,.,)(4)(,.,),8,12x xxZZx xxGx xxGx xxNN重新计算到的距离，分别把归于最近的那个聚类中心，重新分为二类计算结束。TTZZZZ)33. 7 ,67. 7() 3() 4()13. 1 ,25. 1 () 3() 4(2211v说明：说明： (1)K是指需要分成K类，均值

27、是指每类的中心,就是该类所有样本的平均值，不一定就有某个样本在这个位置上。 (2)算法的收敛性判别：前后两次迭代的结果，也就是每迭代分类后，分类都是一样的，此时停止。 (3)K值和初始聚类中心对分类的结果影响很大。通常需要其它的算法来确定这两个的选取。v讨论讨论v K-均值算法的结果受如下选择的影响：v所选聚类的数目v聚类中心的初始分布v模式样本的几何性质v读入次序v在实际应用中，需要试探不同的K值和选择不同的聚类中心的起始值。v如果模式样本可以形成若干个相距较远的孤立的区域分布，一般都能得到较好的收敛效果。vK-均值算法比较适合于分类数目已知的情况。作业作业1. 给定5个6维模式样本（如下），试按最小距离准则进行系统聚类分析。2.已知十个样本，每个样本2个特征，数据如下：用K-均值算法分成3类。样本序号1 2 3 4 5 6 7 8 9 10 x10 1 2 4 5 5 6 1 1 1 x20 1 1 3 3 4 5 4 5 60,1 ,0,1 ,0,0:1 ,2,2,0,1 ,2:1 ,1 ,0,0,0,1:1 ,2,1 ,3,3,3:4,3,1 ,3,1 ,0:54321xxxxx