非监督学习法PPT课件.ppt

1、第五章 非监督学习法5.3 聚类方法聚类方法聚类方法不通过对概率密度函数作出估计而直接按样本间的相似不通过对概率密度函数作出估计而直接按样本间的相似性，或彼此间在特征空间中的距离长短进行分类，以使性，或彼此间在特征空间中的距离长短进行分类，以使某种聚类准则达到极值为最佳。某种聚类准则达到极值为最佳。两种对数据集进行聚类的方法：两种对数据集进行聚类的方法：(1)迭代的动态聚类算法迭代的动态聚类算法(2)非迭代的分级聚类算非迭代的分级聚类算法法7/11/20251中国矿业大学 计算机科学与技术学院第五章 非监督学习法例：使用聚类方法实现道路识别例：使用聚类方法实现道路识别7/11/20252中国矿

2、业大学 计算机科学与技术学院第五章 非监督学习法5.3.1 动态聚类方法动态聚类方法的任务动态聚类方法的任务将数据集划分成一定数量的子集，子集数目在理想情将数据集划分成一定数量的子集，子集数目在理想情况下能体现数据集比较合理的划分。况下能体现数据集比较合理的划分。要解决的问题要解决的问题(1)怎样才能知道该数据集应该划分的子集数目怎样才能知道该数据集应该划分的子集数目(2)如果划分数目已定，则又如何找到最佳划分。如果划分数目已定，则又如何找到最佳划分。由于优化过程是从不甚合理的划分到由于优化过程是从不甚合理的划分到“最佳最佳”划分，是一个划分，是一个动态的迭代过程，故这种方法称为动态聚类方法。

3、动态的迭代过程，故这种方法称为动态聚类方法。7/11/20253中国矿业大学 计算机科学与技术学院第五章 非监督学习法动态聚类方法基本要点动态聚类方法基本要点动态聚类示意图动态聚类示意图7/11/20254中国矿业大学 计算机科学与技术学院第五章 非监督学习法动态聚类算法的要点动态聚类算法的要点(1)选定某种距离度量作为样本间的相似性度量。选定某种距离度量作为样本间的相似性度量。(2)确定样本合理的初始分类，包括代表点的选择，确定样本合理的初始分类，包括代表点的选择，初始分类的方法选择等。初始分类的方法选择等。(3)确定某种评价聚类结果质量的准则函数，用以确定某种评价聚类结果质量的准则函数，用

4、以调整初始分类直至达到该准则函数的极值。调整初始分类直至达到该准则函数的极值。7/11/20255中国矿业大学 计算机科学与技术学院第五章 非监督学习法C-均值算法均值算法1、准则函数、准则函数误差平方和准则误差平方和准则准则函数是以计算各类均值准则函数是以计算各类均值，与计算各类样本到其所属类，与计算各类样本到其所属类均值点误差平方和为准则均值点误差平方和为准则。各类均值：各类均值：(5.3-1)误差平方和准则可表示为：误差平方和准则可表示为：(5.3-2)最佳的聚类是使误差平方和准则为最小的分类。这种类型的聚最佳的聚类是使误差平方和准则为最小的分类。这种类型的聚类通常称为最小方差划分。类通

5、常称为最小方差划分。7/11/20256中国矿业大学 计算机科学与技术学院第五章 非监督学习法C-均值算法均值算法2、样本集初始划分、样本集初始划分初始划分的一般作法是先选择一些代表点作为聚类的核心，初始划分的一般作法是先选择一些代表点作为聚类的核心，然后把其余的样本按某种方法分到各类中去。然后把其余的样本按某种方法分到各类中去。代表点的选择方法：代表点的选择方法：(2)将全部数据随机地分为将全部数据随机地分为C类，计算各类重心，将这些重类，计算各类重心，将这些重心作为每类的代表点。心作为每类的代表点。(1)凭经验选择代表点。凭经验选择代表点。根据问题的性质，用经验的办法确定类别数，从数据中找

6、出根据问题的性质，用经验的办法确定类别数，从数据中找出从直观上看来是比较合适的代表点。从直观上看来是比较合适的代表点。7/11/20257中国矿业大学 计算机科学与技术学院第五章 非监督学习法(3)“密度密度”法选择代表点。法选择代表点。(4)从从(c-1)聚类划分问题的解中产生聚类划分问题的解中产生C聚类划分问题的代表点。聚类划分问题的代表点。选选“密度密度”为最大的样本点作为第一个代表点，然后人为规为最大的样本点作为第一个代表点，然后人为规定距该代表点定距该代表点 距离外的区域内找次高距离外的区域内找次高“密度密度”的样本点作的样本点作为第二个代表点，依次选择其它代表点，使用这种方法的目为

7、第二个代表点，依次选择其它代表点，使用这种方法的目的是避免代表点过分集中在一起。的是避免代表点过分集中在一起。对样本集首先看作一个聚类，计算其总均值，然后找与该均对样本集首先看作一个聚类，计算其总均值，然后找与该均值相距最远的点，由该点及原均值点构成两聚类的代表点。值相距最远的点，由该点及原均值点构成两聚类的代表点。依同样方法，对已有依同样方法，对已有(c-1)个聚类代表点个聚类代表点(由由(c-1)个类均值个类均值点组成点组成)找一样本点，使该样本点距所有这些均值点的最小找一样本点，使该样本点距所有这些均值点的最小距离为最大，这样就得到了第距离为最大，这样就得到了第c个代表点。个代表点。7/

8、11/20258中国矿业大学 计算机科学与技术学院第五章 非监督学习法确定初始划分的方法确定初始划分的方法(1)对选定的代表点按距离最近的原则将样本划属各代表点代对选定的代表点按距离最近的原则将样本划属各代表点代表的类别。表的类别。(2)在选择样本的点集后，将样本按顺序划归距离最近的代表在选择样本的点集后，将样本按顺序划归距离最近的代表点所属类，并立即修改代表点参数，用样本归入后的重心代点所属类，并立即修改代表点参数，用样本归入后的重心代替原代表点，因此代表点在初始划分过程中作了修改。替原代表点，因此代表点在初始划分过程中作了修改。7/11/20259中国矿业大学 计算机科学与技术学院第五章

9、非监督学习法(3)既选择了代表点又同时确定了初始划分的方法。既选择了代表点又同时确定了初始划分的方法。然后选然后选1 1=y1，计算样本计算样本y2与与y1的距离的距离D(y1,y2)，如其小于如其小于d，则归入则归入1 1，否则建立新的类别否则建立新的类别2 2。首先规定一阈值首先规定一阈值d。当轮到样本当轮到样本ye时，已有了时，已有了K类即，类即，1 1,2 2,k，而每类而每类第一个入类样本分别为第一个入类样本分别为y1 11 1,y2 21 1,yk1 1，则计算则计算D(yi1 1,ye),i=1,2,k,若若D(yi1 1,ye)d 则建立新类。否则将则建立新类。否则将ye归归入

10、与入与y1 11 1,y2 21 1,yk1 1距离最近的类别中。距离最近的类别中。7/11/202510中国矿业大学 计算机科学与技术学院第五章 非监督学习法(4)先将数据标准化，用先将数据标准化，用yij表示标准化后第表示标准化后第i数据的数据的第第j个分量，令个分量，令 如果欲将样本划分为如果欲将样本划分为c类，则对每个类，则对每个i计算计算如所得结果非整数，则找到其最近整数如所得结果非整数，则找到其最近整数K，将第将第i数据归入数据归入第第K类。类。7/11/202511中国矿业大学 计算机科学与技术学院第五章 非监督学习法3、迭代计算、迭代计算 均值算法的迭代计算过程在原理上与梯度下

11、降法是一样的，均值算法的迭代计算过程在原理上与梯度下降法是一样的，即以使准则函数值下降为准则。即以使准则函数值下降为准则。但是由于但是由于c-均值算法的准则函数值由数据划分的调整所决定，均值算法的准则函数值由数据划分的调整所决定，因此只能通过逐个数据从某个子集转移到另一子集计算准则因此只能通过逐个数据从某个子集转移到另一子集计算准则函数值是否降低为准则。函数值是否降低为准则。C-均值算法均值算法按准则函数极值化的方向对初始划分进行修改。按准则函数极值化的方向对初始划分进行修改。如果原属如果原属k中的一个样本中的一个样本y从从k移入移入j时，它会对误差平方时，它会对误差平方和产生影响，和产生影响

12、k类在抽出样本类在抽出样本y后用后用 表示，其相应均值为表示，其相应均值为(5.3-3)7/11/202512中国矿业大学 计算机科学与技术学院第五章 非监督学习法而样本而样本y新加盟的新加盟的 集合，其均值为：集合，其均值为：(5.3-4)由于由于y的移动只影响到的移动只影响到k与与j这两类的参数改动，因此，计算这两类的参数改动，因此，计算Jc值的变动只要计算相应两类误差平方和的变动即可，此时值的变动只要计算相应两类误差平方和的变动即可，此时(5.3-5)(5.3-6)如果如果(5.3-7)则将样本则将样本y从从k移入移入j 移入就会使误差平方总和移入就会使误差平方总和Jc减小，它减小，它

13、表明样本变动是合乎准则要求的。表明样本变动是合乎准则要求的。7/11/202513中国矿业大学 计算机科学与技术学院第五章 非监督学习法4、C均值算法步骤均值算法步骤 C-均值算法均值算法(1)选择某种方法把选择某种方法把N个样本分成个样本分成C个聚类的初始划分，计算每个聚类的初始划分，计算每个聚类的均值个聚类的均值m1 1,m2 2,mc和和Jc。(2)选择一个备选样本选择一个备选样本y，设其在设其在i中。中。(3)若若N Ni=1，则转则转(2)，否则继续。，否则继续。(4)计算计算(5.3-8)7/11/202514中国矿业大学 计算机科学与技术学院第五章 非监督学习法(5)对于所有的对

14、于所有的j，若，若eiej，则将则将y从从j 移到移到i中。中。(6)重新计算重新计算mi i和和mj j的值，并修改的值，并修改Jc。(7)若连续迭代若连续迭代N次次(即所有样本都运算过即所有样本都运算过)Jc不变，则停止，不变，则停止，否则转到否则转到(2)。7/11/202515中国矿业大学 计算机科学与技术学院第五章 非监督学习法Jc值随值随c变化的曲线，变化的曲线，7/11/202516中国矿业大学 计算机科学与技术学院第五章 非监督学习法ISODATA算法算法ISODATA算法的功能与算法的功能与C均值算法的不同点均值算法的不同点(1)考虑了类别的合并与分裂，因而有了自我调整类别数

15、的能力。考虑了类别的合并与分裂，因而有了自我调整类别数的能力。合并主要发生在某一类内样本个数太少的情况，或两类聚类合并主要发生在某一类内样本个数太少的情况，或两类聚类中心之间距离太小的情况。为此设有最小类内样本数限制中心之间距离太小的情况。为此设有最小类内样本数限制，以及类间中心距离参数。以及类间中心距离参数。分裂则主要发生在某一类别的某分量出现类内方差过大的现分裂则主要发生在某一类别的某分量出现类内方差过大的现象，因而宜分裂成两个类别，以维持合理的类内方差。给出象，因而宜分裂成两个类别，以维持合理的类内方差。给出一个对类内分量方差的限制参数一个对类内分量方差的限制参数，用以决定是否需要将某一

16、用以决定是否需要将某一类分裂成两类。类分裂成两类。7/11/202517中国矿业大学 计算机科学与技术学院第五章 非监督学习法(2)由于算法有自我调整的能力，因而需设置若干控制参数。由于算法有自我调整的能力，因而需设置若干控制参数。如聚类数期望值如聚类数期望值K、每次迭代允许合并的最大聚类对数每次迭代允许合并的最大聚类对数L、及及允许迭代次数允许迭代次数I等。等。7/11/202518中国矿业大学 计算机科学与技术学院第五章 非监督学习法ISODATA算法算法ISODATA算法的步骤算法的步骤(1)确定控制参数及设置代表点确定控制参数及设置代表点需确定的控制参数为：需确定的控制参数为：K：聚

17、类期望数；聚类期望数；N：一个聚类中的最少样本数；一个聚类中的最少样本数；S：标准偏差控制参数，用于控制分裂；标准偏差控制参数，用于控制分裂；C：类间距离控制参数，用于控制合并；类间距离控制参数，用于控制合并；L：每次迭代允许合并的最大聚类对数；每次迭代允许合并的最大聚类对数；I：允许迭代的次数。允许迭代的次数。设初始聚类数为设初始聚类数为c及聚类中心及聚类中心mi,i=1,2,c。7/11/202519中国矿业大学 计算机科学与技术学院第五章 非监督学习法(2)分类：对所有样本，按给定的分类：对所有样本，按给定的c个聚类中心，以最小距离进个聚类中心，以最小距离进行分类，即行分类，即(3)撤消

18、类内样本数过小类别：撤消类内样本数过小类别：若有任何一个类若有任何一个类j,其样本数，其样本数，NjS，并且有条件并且有条件(a)或或(b)。(a)且且(b)ck/2则把则把j分裂成两个聚类，其中心相应为分裂成两个聚类，其中心相应为mj+与与mj-，把原来的把原来的mj取消，且令取消，且令c=c+1，由于由于mj+与与mj-值值设置不当将会导致影设置不当将会导致影响到其它类别，因此响到其它类别，因此mj+与与mj-可可按以下步骤计算：按以下步骤计算：(a)给定一给定一k值，值，0k1；(b)令令rj=kjmax(c)mj+=mj+rj；mj-=mj-rj 其中其中k值应使值应使j中的样本到中的

19、样本到mj+与与mj-的的距离不同，但又应距离不同，但又应使使j中的样本仍然在分裂后的新样本类中。中的样本仍然在分裂后的新样本类中。7/11/202522中国矿业大学 计算机科学与技术学院第五章 非监督学习法(11)计算类间聚类中心距离：计算类间聚类中心距离：(12)列出类间距离过近者：列出类间距离过近者：比较比较Dij与与C并将小于并将小于C的的Dij按按上升次序排列上升次序排列该队列最大个数是控制合并对数的参数该队列最大个数是控制合并对数的参数L7/11/202523中国矿业大学 计算机科学与技术学院第五章 非监督学习法(13)执行合并：执行合并：从类间距离最大的两类开始执行合并过程，此时

20、需将从类间距离最大的两类开始执行合并过程，此时需将mil与与mjl合并，得合并，得且且c=c-1，从第二个从第二个Dj2j2开始，则要检查其涉及的开始，则要检查其涉及的mil与与mjl是否已在前面合并过程中被合并，如两者并未被合并，则是否已在前面合并过程中被合并，如两者并未被合并，则执行合并过程。执行合并过程。(14)结束步骤：结束步骤：如是最后一次迭代则终止，否则可根据需要转步骤如是最后一次迭代则终止，否则可根据需要转步骤1或步或步骤骤2，转步骤，转步骤1是为了更改控制数。迭代计数要加是为了更改控制数。迭代计数要加1。7/11/202524中国矿业大学 计算机科学与技术学院第五章 非监督学习

21、法ISODATA算法与算法与C均值算法的主要不同在于自我控制与调均值算法的主要不同在于自我控制与调整的能力不同。它们的另一个不同点是，整的能力不同。它们的另一个不同点是，C均值算法的类均值算法的类均值参数在每个样本归入时随即修改，因而称为逐个样本修均值参数在每个样本归入时随即修改，因而称为逐个样本修正法，而正法，而ISODATA算法的均值向量或聚类中心参数是在每一算法的均值向量或聚类中心参数是在每一次迭代分类后修正的，因而称为成批样本修正法。次迭代分类后修正的，因而称为成批样本修正法。7/11/202525中国矿业大学 计算机科学与技术学院第五章 非监督学习法样本非球体分布的动态聚类算法样本非

22、球体分布的动态聚类算法 7/11/202526中国矿业大学 计算机科学与技术学院第五章 非监督学习法样本非球体分布的动态聚类算法样本非球体分布的动态聚类算法 1、基于样本和核的相似性度量的动态聚类算法、基于样本和核的相似性度量的动态聚类算法样本在特征空间的分布具有方向性，或说非各向同性，因此样本在特征空间的分布具有方向性，或说非各向同性，因此各聚类就不再能以一个代表点来表示了，而必须用一种分类各聚类就不再能以一个代表点来表示了，而必须用一种分类模型表示。模型表示。其中其中vj是一个定义是一个定义Kj的参数集，而的参数集，而Kj可以用一个函数、一个点可以用一个函数、一个点集或一分类模型表示。此外

23、还需确定一个样本与各类的核之集或一分类模型表示。此外还需确定一个样本与各类的核之间的度量间的度量(y,Kj)，以此判断样本应当属于哪一类。以此判断样本应当属于哪一类。7/11/202527中国矿业大学 计算机科学与技术学院第五章 非监督学习法正态核函数正态核函数:根据正态分布的贝叶斯决策规则，可定义相似性度量为：根据正态分布的贝叶斯决策规则，可定义相似性度量为：采用类似于采用类似于C均值算法的方法定义准则函数为：均值算法的方法定义准则函数为：7/11/202528中国矿业大学 计算机科学与技术学院第五章 非监督学习法算法步骤：算法步骤：(1)选择初始划分，即将样本集划分为选择初始划分，即将样本

24、集划分为C类，并确定每类的初类，并确定每类的初始核始核Kj,j1,2,c(2)按照下列关系按照下列关系将样本分到相应的聚类中去。将样本分到相应的聚类中去。(3)重新修正核重新修正核Kj,j1,2,c，若核保持不变，则算法终若核保持不变，则算法终止，否则转步骤止，否则转步骤2。7/11/202529中国矿业大学 计算机科学与技术学院第五章 非监督学习法算法的收敛性算法的收敛性如果如果则有则有那么算法将会收敛。那么算法将会收敛。7/11/202530中国矿业大学 计算机科学与技术学院第五章 非监督学习法C均值算法实际上是基于核均值算法实际上是基于核Kj的动态聚类算法的特例的动态聚类算法的特例修正后

25、的核集：修正后的核集：7/11/202531中国矿业大学 计算机科学与技术学院第五章 非监督学习法样本非球体分布的动态聚类算法样本非球体分布的动态聚类算法 2、近邻函数准则算法、近邻函数准则算法 几种不同形状的数据构造的例子几种不同形状的数据构造的例子特点：类内样本具有明显的近邻关系，因而可以利用这种特点：类内样本具有明显的近邻关系，因而可以利用这种关系，定义近邻函数，以执行动态聚类算法。关系，定义近邻函数，以执行动态聚类算法。7/11/202532中国矿业大学 计算机科学与技术学院第五章 非监督学习法(1)近邻关系描述近邻关系描述样本集中任何一对样本间的近邻关系可以用彼此是对方的样本集中任何

26、一对样本间的近邻关系可以用彼此是对方的第几个近邻的方式来描述。第几个近邻的方式来描述。例如：例如：yi是是yj的第的第I个近邻，而个近邻，而yj是是yi的第的第K个近邻，则这一对样本个近邻，则这一对样本之间的近邻函数值可定义为之间的近邻函数值可定义为(I+K-2)。近邻函数值为：近邻函数值为：aij=I+K-27/11/202533中国矿业大学 计算机科学与技术学院第五章 非监督学习法(2)“连接连接”损失损失用近邻关系进行聚类，可以看作是一种连接过程，即将用近邻关系进行聚类，可以看作是一种连接过程，即将具有适当近邻关系的样本连接成同一类，而避免在近邻具有适当近邻关系的样本连接成同一类，而避免

27、在近邻关系较差的样本之间进行连接。关系较差的样本之间进行连接。为了实现按近邻关系建立样本间的连接关系，可定义一为了实现按近邻关系建立样本间的连接关系，可定义一个个“连接连接”损失，以近邻函数值作连接损失值。采用这损失，以近邻函数值作连接损失值。采用这种定义，可以使连接趋向于发生在距离接近的样本之间。种定义，可以使连接趋向于发生在距离接近的样本之间。为了防止样本自身实行连接，可将为了防止样本自身实行连接，可将aij定义为定义为2N或更大，或更大，其中其中N是样本集的样本数，这种定义是考虑到样本集内是样本集的样本数，这种定义是考虑到样本集内任何一对非自身的样本间的最大连接损失为任何一对非自身的样本

28、间的最大连接损失为(2N-4)即即7/11/202534中国矿业大学 计算机科学与技术学院第五章 非监督学习法样本之间的样本之间的“连接连接”与与“连接连接”损失损失7/11/202535中国矿业大学 计算机科学与技术学院第五章 非监督学习法(3)类内损失与类间损失类内损失与类间损失 类内损失：是所有连接关系损失总和类内损失：是所有连接关系损失总和 两类间的最小近邻函数值两类间的最小近邻函数值rij 是是1 1与与2 2间各对样本近邻函数值间各对样本近邻函数值的最小值，而的最小值，而1 1对所有对所有c-1类的最小近邻值类的最小近邻值rij定义为：定义为：7/11/202536中国矿业大学 计

29、算机科学与技术学院第五章 非监督学习法类内最大连接损失类内最大连接损失aimax：即：即i中各点间连接的最大连接损失中各点间连接的最大连接损失值。值。设设i与与k之间具有最小的近邻函数值即之间具有最小的近邻函数值即ri=rik，则类间的损失则类间的损失显然与显然与ri,aimax及及akmax这这三者的关系有关，为此定义三者的关系有关，为此定义1 1对其对其它各类的类间损失为：它各类的类间损失为：7/11/202537中国矿业大学 计算机科学与技术学院第五章 非监督学习法总的类间损失定义为总的类间损失定义为:准则函数定义为准则函数定义为:7/11/202538中国矿业大学 计算机科学与技术学院

30、第五章 非监督学习法(4)近邻函数准则算法近邻函数准则算法步骤步骤1：计算距离矩阵：计算距离矩阵D步骤步骤2：利用矩阵：利用矩阵D，确定近邻矩阵确定近邻矩阵M，其元素其元素Mij为样本为样本yi与与yj的的近邻函数值。一般近邻函数值。一般M为正定矩阵。为正定矩阵。M中元素都为整数。中元素都为整数。步骤步骤3：形成近邻函数矩阵：形成近邻函数矩阵L，其元素为：其元素为：而而L矩阵对角元素矩阵对角元素Lij=2N(或更大或更大)。7/11/202539中国矿业大学 计算机科学与技术学院第五章 非监督学习法步骤步骤4：通过对矩阵：通过对矩阵L进行搜索，将每个点与和它有最小近邻函进行搜索，将每个点与和它

31、有最小近邻函数值的点连接起来，从而形成初始聚类。数值的点连接起来，从而形成初始聚类。步骤步骤5：对于在步骤：对于在步骤4中所形成的每个类中所形成的每个类i计算计算ri，并与并与aimax及及akmax进行比较。若进行比较。若ri小于或等于小于或等于aimax及及akmax中的任何一中的任何一个，则合并类个，则合并类i和类和类k，即在这两类中建立即在这两类中建立“连接连接”。重。重复步骤复步骤5，直到无这样的，直到无这样的“连接连接”发生为止，程序至此终发生为止，程序至此终止。止。7/11/202540中国矿业大学 计算机科学与技术学院第五章 非监督学习法分级聚类方法分级聚类方法分级聚类方法的目

32、的并不把分级聚类方法的目的并不把N个样本分成某一个预定的个样本分成某一个预定的类别数类别数C，而是把样本集按不同的相似程度要求分成不而是把样本集按不同的相似程度要求分成不同类别的聚类，它可以用一树形结构表示。同类别的聚类，它可以用一树形结构表示。最极端的情况是每个样本各自为一类，最极端的情况是每个样本各自为一类，N个样本共有个样本共有N类，没有任何聚类，另一极端则是将所有样本归一类。类，没有任何聚类，另一极端则是将所有样本归一类。在这两个极端之间的是类别数从在这两个极端之间的是类别数从N逐渐减少，每类的数逐渐减少，每类的数量相应增加，而类内样本的相似程度要求也随之下降。量相应增加，而类内样本的

33、相似程度要求也随之下降。这种聚类就是分级聚类，这种聚类就是分级聚类，7/11/202541中国矿业大学 计算机科学与技术学院第五章 非监督学习法分级聚类方法示意图分级聚类方法示意图7/11/202542中国矿业大学 计算机科学与技术学院第五章 非监督学习法聚类的相似性度量方法聚类的相似性度量方法(1)最近距离最近距离:(2)最远距离最远距离:(3)均值距离均值距离:7/11/202543中国矿业大学 计算机科学与技术学院第五章 非监督学习法分级聚类算法分级聚类算法初始时设置初始时设置j=yj，jI,I=j|j=1,2,N，j表示各个聚表示各个聚类集合，类集合，N是样本数，初始时每个样本自成一类

34、是样本数，初始时每个样本自成一类。步骤步骤2：把：把i并入并入k，并去掉并去掉i。步骤步骤3：把：把i从指标集从指标集I中除掉，若中除掉，若I的基数仅等于的基数仅等于2时，则终时，则终止计算，否则转向步骤止计算，否则转向步骤1。步骤步骤1：在集合：在集合j|jI中找到一对满足条件中找到一对满足条件的聚类集合的聚类集合i与与k。其中其中(i,k)是该两聚类的相似性度量。是该两聚类的相似性度量。7/11/202544中国矿业大学 计算机科学与技术学院第五章 非监督学习法不同的相似性度量对聚类结果的影响不同的相似性度量对聚类结果的影响三种数据分布的例子三种数据分布的例子采用最近距离的距聚类结果采用

35、最近距离的距聚类结果7/11/202545中国矿业大学 计算机科学与技术学院第五章 非监督学习法采用最远距离的距聚类结果采用最远距离的距聚类结果7/11/202546中国矿业大学 计算机科学与技术学院第五章 非监督学习法5.4 非监督学习方法中的一些问题点集的数据构造、被分析的点集中样本点的数量、所采用的点集的数据构造、被分析的点集中样本点的数量、所采用的距离度量和相似性度量、所用的聚类准则，以及最终的聚类距离度量和相似性度量、所用的聚类准则，以及最终的聚类数都会影响到分类的结果。数都会影响到分类的结果。样本各分量之间的尺度比例的确定也是十分重要的问题。样本各分量之间的尺度比例的确定也是十分重

36、要的问题。7/11/202547中国矿业大学 计算机科学与技术学院第五章 非监督学习法非监督学习中的尺度问题举例非监督学习中的尺度问题举例7/11/202548中国矿业大学 计算机科学与技术学院第五章 非监督学习法本章小结本章小结本章学习了非监督学习方法的内容，主要讲了聚类，即数据本章学习了非监督学习方法的内容，主要讲了聚类，即数据按它内在规律划分。实际上我们可以从广义上定义非监督学按它内在规律划分。实际上我们可以从广义上定义非监督学习方法，即本章开始讲的，对数据集进行分析，寻找其内在习方法，即本章开始讲的，对数据集进行分析，寻找其内在的规律性，聚类只是其中一个方面。的规律性，聚类只是其中一个方面。至于非监督学习方法与有监督学习方法主要在分类这一点上至于非监督学习方法与有监督学习方法主要在分类这一点上值得比较，两者都是讲对数据进行分类，但后者有训练样本，值得比较，两者都是讲对数据进行分类，但后者有训练样本，训练样本有标号，因而属识别，而前者只是按其自然分布状训练样本有标号，因而属识别，而前者只是按其自然分布状态进行划分而已。态进行划分而已。本章学习了动态聚类与分级聚类两种方法，要着重体会两者本章学习了动态聚类与分级聚类两种方法，要着重体会两者的区别与不同的用途。的区别与不同的用途。7/11/202549中国矿业大学 计算机科学与技术学院