非监督学习法PPT课件.ppt
《非监督学习法PPT课件.ppt》由会员分享,可在线阅读,更多相关《非监督学习法PPT课件.ppt(49页珍藏版)》请在三一文库上搜索。
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中的样本到中的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 监督 学习 PPT 课件
