非监督学习法5.3-5.4.ppt

2019/6/8,中国矿业大学 计算机科学与技术学院,(49)1,5.3 聚类方法,聚类方法,不通过对概率密度函数作出估计而直接按样本间的相似性，或彼此间在特征空间中的距离长短进行分类，以使某种聚类准则达到极值为最佳。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)2,例：使用聚类方法实现道路识别,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)3,5.3.1 动态聚类方法,动态聚类方法的任务,将数据集划分成一定数量的子集，子集数目在理想情况下能体现数据集比较合理的划分。,要解决的问题,(1) 怎样才能知道该数据集应该划分的子集数目,(2) 如果划分数目已定，则又如何找到最佳划分。,由于优化过程是从不甚合理的划分到“最佳”划分，是一个动态的迭代过程，故这种方法称为动态聚类方法。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)4,动态聚类方法基本要点,动态聚类示意图,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)5,动态聚类算法的要点,(1) 选定某种距离度量作为样本间的相似性度量。,(2) 确定样本合理的初始分类，包括代表点的选择，初始分类的方法选择等。,(3) 确定某种评价聚类结果质量的准则函数，用以调整初始分类直至达到该准则函数的极值。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)6,C-均值算法,1、准则函数误差平方和准则,准则函数是以计算各类均值 ，与计算各类样本到其所属类均值点误差平方和为准则。,各类均值：,(5.3-1),误差平方和准则可表示为：,(5.3-2),最佳的聚类是使误差平方和准则为最小的分类。这种类型的聚类通常称为最小方差划分。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)7,C-均值算法,2、样本集初始划分,初始划分的一般作法是先选择一些代表点作为聚类的核心，然后把其余的样本按某种方法分到各类中去。,代表点的选择方法：,(2) 将全部数据随机地分为C类，计算各类重心，将这些重心作为每类的代表点。,(1) 凭经验选择代表点。,根据问题的性质，用经验的办法确定类别数，从数据中找出从直观上看来是比较合适的代表点。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)8,(3) “密度”法选择代表点。,(4) 从(c-1)聚类划分问题的解中产生C聚类划分问题的代表点。,选“密度”为最大的样本点作为第一个代表点，然后人为规定距该代表点 距离外的区域内找次高“密度”的样本点作为第二个代表点，依次选择其它代表点，使用这种方法的目的是避免代表点过分集中在一起。,对样本集首先看作一个聚类，计算其总均值，然后找与该均值相距最远的点，由该点及原均值点构成两聚类的代表点。依同样方法，对已有(c-1)个聚类代表点(由(c-1)个类均值点组成)找一样本点，使该样本点距所有这些均值点的最小距离为最大，这样就得到了第c个代表点。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)9,确定初始划分的方法,(1) 对选定的代表点按距离最近的原则将样本划属各代表点代表的类别。,(2) 在选择样本的点集后，将样本按顺序划归距离最近的代表点所属类，并立即修改代表点参数，用样本归入后的重心代替原代表点，因此代表点在初始划分过程中作了修改。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)10,(3) 既选择了代表点又同时确定了初始划分的方法。,然后选1=y1，计算样本y2与y1的距离D(y1, y2)，如其小于d，则归入1 ，否则建立新的类别2。,首先规定一阈值d。,当轮到样本ye时，已有了K类即，1,2, ,k，而每类第一个入类样本分别为y11, y21, , yk1 ，则计算D(yi1, ye), i=1,2,k, 若D(yi1, ye) d 则建立新类。否则将ye归入与y11, y21, , yk1距离最近的类别中。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)11,(4) 先将数据标准化，用yij表示标准化后第i数据的第j个分量，令,如果欲将样本划分为c类，则对每个i计算,如所得结果非整数，则找到其最近整数K，将第i数据归入第K类。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)12,3、迭代计算,均值算法的迭代计算过程在原理上与梯度下降法是一样的，即以使准则函数值下降为准则。,但是由于c-均值算法的准则函数值由数据划分的调整所决定，因此只能通过逐个数据从某个子集转移到另一子集计算准则函数值是否降低为准则。,C-均值算法,按准则函数极值化的方向对初始划分进行修改。,如果原属k中的一个样本y从k移入j时，它会对误差平方和产生影响，k类在抽出样本y后用 表示，其相应均值为,(5.3-3),2019/6/8,中国矿业大学 计算机科学与技术学院,(49)13,而样本y新加盟的 集合，其均值为：,(5.3-4),由于y的移动只影响到k与j这两类的参数改动，因此，计算Jc值的变动只要计算相应两类误差平方和的变动即可，此时,(5.3-5),(5.3-6),如果,(5.3-7),则将样本y从k移入j 移入就会使误差平方总和Jc减小，它表明样本变动是合乎准则要求的。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)14,4、C均值算法步骤,C-均值算法,(1) 选择某种方法把N个样本分成C个聚类的初始划分，计算每个聚类的均值m1, m2, , mc和Jc 。,(2) 选择一个备选样本y，设其在i中。,(3) 若Ni =1 ，则转(2)，否则继续。,(4) 计算,(5.3-8),2019/6/8,中国矿业大学 计算机科学与技术学院,(49)15,(5) 对于所有的j，若eiej，则将y从j 移到i中。,(6) 重新计算mi和mj的值，并修改Jc 。,(7) 若连续迭代N次(即所有样本都运算过) Jc不变，则停止，否则转到(2)。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)16,Jc值随c变化的曲线，,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)17,ISODATA算法,ISODATA算法的功能与C均值算法的不同点,(1) 考虑了类别的合并与分裂，因而有了自我调整类别数的能力。,合并主要发生在某一类内样本个数太少的情况，或两类聚类中心之间距离太小的情况。为此设有最小类内样本数限制 ，以及类间中心距离参数。,分裂则主要发生在某一类别的某分量出现类内方差过大的现象，因而宜分裂成两个类别，以维持合理的类内方差。给出一个对类内分量方差的限制参数 ，用以决定是否需要将某一类分裂成两类。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)18,(2) 由于算法有自我调整的能力，因而需设置若干控制参数。,如聚类数期望值K、每次迭代允许合并的最大聚类对数L、及允许迭代次数I等。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)19,ISODATA算法,ISODATA算法的步骤,(1) 确定控制参数及设置代表点,需确定的控制参数为：,K：聚类期望数；,N ：一个聚类中的最少样本数；,S：标准偏差控制参数，用于控制分裂；,C：类间距离控制参数，用于控制合并；,L：每次迭代允许合并的最大聚类对数；,I：允许迭代的次数。,设初始聚类数为c及聚类中心mi, i=1,2,c 。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)20,分类：对所有样本，按给定的c个聚类中心，以最小距离进行分类，即,(3) 撤消类内样本数过小类别：,若有任何一个类j,其样本数，NjN 则舍去j ，令c=c-1。,(4) 更新均值向量：按现有样本分类结果，调整均值参数,(5) 计算类内平均距离：每类各样本离开均值的平均距离,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)21,(6) 计算整个样本集偏离均值的平均距离：,如果cK/2，则转向(8)，执行分裂步骤；,如果c2K，则转向(11)，执行合并步骤；,(8) 求各类内各分量标准偏差：,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)22,(9) 求每类具有最大标准偏差的分量：,(10) 分裂计算步骤：,则把j分裂成两个聚类，其中心相应为mj+与mj-，把原来的mj取消，且令c=c+1，由于mj+与mj-值设置不当将会导致影响到其它类别，因此mj+与mj-可按以下步骤计算：,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)23,(11) 计算类间聚类中心距离：,(12) 列出类间距离过近者：,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)24,(13) 执行合并：,从类间距离最大的两类开始执行合并过程，此时需将mil与mjl合并，得,且c=c-1，从第二个Dj2j2开始，则要检查其涉及的mil与mjl是否已在前面合并过程中被合并，如两者并未被合并，则执行合并过程。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)25,ISODATA算法与C均值算法的主要不同在于自我控制与调整的能力不同。它们的另一个不同点是，C均值算法的类均值参数在每个样本归入时随即修改，因而称为逐个样本修正法，而ISODATA算法的均值向量或聚类中心参数是在每一次迭代分类后修正的，因而称为成批样本修正法。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)26,样本非球体分布的动态聚类算法,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)27,样本非球体分布的动态聚类算法,1、基于样本和核的相似性度量的动态聚类算法,样本在特征空间的分布具有方向性，或说非各向同性，因此各聚类就不再能以一个代表点来表示了，而必须用一种分类模型表示。,其中vj是一个定义Kj的参数集，而Kj可以用一个函数、一个点集或一分类模型表示。此外还需确定一个样本与各类的核之间的度量(y, Kj)，以此判断样本应当属于哪一类。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)28,正态核函数:,根据正态分布的贝叶斯决策规则，可定义相似性度量为：,采用类似于C均值算法的方法定义准则函数为：,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)29,算法步骤：,(1) 选择初始划分，即将样本集划分为C类，并确定每类的初始核Kj, j1,2,c,(3) 重新修正核Kj, j1,2,c ，若核保持不变，则算法终止，否则转步骤2。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)30,算法的收敛性,如果,则有,那么算法将会收敛。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)31,C均值算法实际上是基于核Kj的动态聚类算法的特例,修正后的核集：,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)32,样本非球体分布的动态聚类算法,2、近邻函数准则算法,几种不同形状的数据构造的例子,特点：类内样本具有明显的近邻关系，因而可以利用这种关系，定义近邻函数，以执行动态聚类算法。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)33,(1) 近邻关系描述,样本集中任何一对样本间的近邻关系可以用彼此是对方的第几个近邻的方式来描述。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)34,(2) “连接”损失,用近邻关系进行聚类，可以看作是一种连接过程，即将具有适当近邻关系的样本连接成同一类，而避免在近邻关系较差的样本之间进行连接。,为了实现按近邻关系建立样本间的连接关系，可定义一个“连接”损失，以近邻函数值作连接损失值。采用这种定义，可以使连接趋向于发生在距离接近的样本之间。,为了防止样本自身实行连接，可将aij定义为2N或更大，其中N是样本集的样本数，这种定义是考虑到样本集内任何一对非自身的样本间的最大连接损失为(2N-4)即,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)35,样本之间的“连接”与“连接”损失,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)36,(3) 类内损失与类间损失,类内损失：是所有连接关系损失总和,两类间的最小近邻函数值rij 是1与2间各对样本近邻函数值的最小值，而1对所有c-1类的最小近邻值rij定义为：,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)37,类内最大连接损失aimax ：即i中各点间连接的最大连接损失值。,设i与k之间具有最小的近邻函数值即ri=rik，则类间的损失显然与ri, aimax及akmax这三者的关系有关，为此定义1对其它各类的类间损失为：,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)38,总的类间损失定义为:,准则函数定义为:,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)39,(4) 近邻函数准则算法,步骤1：计算距离矩阵D,步骤2：利用矩阵D，确定近邻矩阵M，其元素Mij为样本yi与yj的近邻函数值。一般M为正定矩阵。M中元素都为整数。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)40,步骤4：通过对矩阵L进行搜索，将每个点与和它有最小近邻函数值的点连接起来，从而形成初始聚类。,步骤5：对于在步骤4中所形成的每个类i计算ri，并与aimax及akmax进行比较。若ri小于或等于aimax及akmax中的任何一个，则合并类i和类k，即在这两类中建立“连接”。重复步骤5，直到无这样的“连接”发生为止，程序至此终止。,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)41,分级聚类方法,分级聚类方法的目的并不把N个样本分成某一个预定的类别数C，而是把样本集按不同的相似程度要求分成不同类别的聚类，它可以用一树形结构表示。,最极端的情况是每个样本各自为一类，N个样本共有N类，没有任何聚类，另一极端则是将所有样本归一类。在这两个极端之间的是类别数从N逐渐减少，每类的数量相应增加，而类内样本的相似程度要求也随之下降。这种聚类就是分级聚类，,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)42,分级聚类方法示意图,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)43,聚类的相似性度量方法,最近距离:,(2) 最远距离:,(3) 均值距离:,2019/6/8,中国矿业大学 计算机科学与技术学院,(49)44,分级聚类算法,初始时设置j = yj ，jI,I