无监督学习与聚类.ppt

《无监督学习与聚类.ppt》由会员分享，可在线阅读，更多相关《无监督学习与聚类.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、无监督学习与聚类无监督学习与聚类现在学习的是第1页，共38页10.0 监督学习与无监督学习监督学习与无监督学习n监督学习与无监督学习的监督学习与无监督学习的最大区别最大区别在于训练样本在于训练样本是否有类别标号，无类别标号的称为无监督学习；是否有类别标号，无类别标号的称为无监督学习；n监督学习与无监督学习也被称为有教师学习与无监督学习与无监督学习也被称为有教师学习与无教师学习。教师学习。现在学习的是第2页，共38页10.1 混合密度及可辨识性混合密度及可辨识性n从理论上讲，无监督学习可以看作是一个从理论上讲，无监督学习可以看作是一个混合混合密度的估计密度的估计问题：问题：1.所有样本都来自于所

2、有样本都来自于c种类别，种类别，c已知；已知；2.每种类别的先验概率每种类别的先验概率 已知；已知；3.类条件概率的数学形式已知类条件概率的数学形式已知 ，但参数，但参数 未知；未知；4.样本类别未被标记。样本类别未被标记。现在学习的是第3页，共38页混合密度混合密度n样本可以看作是按如下方式产生的：先以概率样本可以看作是按如下方式产生的：先以概率 决定其所属类别决定其所属类别 ，然后根据概率密度，然后根据概率密度 生成一个具体的样本生成一个具体的样本x。n因此因此x样本的产生概率为：样本的产生概率为：现在学习的是第4页，共38页可辨识性可辨识性n不可辨识不可辨识：如果无论样本的数目有多少，都

3、不：如果无论样本的数目有多少，都不存在唯一的解存在唯一的解 ，则称密度，则称密度 是不可辨识是不可辨识的；的；n完全不可辨识完全不可辨识：如果参数：如果参数 的任何部分都无法的任何部分都无法求出，则称为完全不可辨识；求出，则称为完全不可辨识；n大多数的混合密度是可以辨识的，但也存在某大多数的混合密度是可以辨识的，但也存在某些混合密度是无法辨识的。些混合密度是无法辨识的。现在学习的是第5页，共38页完全不可辨识完全不可辨识n假设样本假设样本x的概率是由两个的概率是由两个0-1分布混合而成，两分布混合而成，两个分布的先验概率相等，参数分别为个分布的先验概率相等，参数分别为 则混则混合概率为：合概率

4、为：n即使可以统计出即使可以统计出 ，也也无法求解出参数无法求解出参数 。现在学习的是第6页，共38页部分不可辨识部分不可辨识n假设样本假设样本x的概率密度是两个均匀分布的混合：的概率密度是两个均匀分布的混合：n如果训练样本是如果训练样本是0-1之间的均匀分布：之间的均匀分布：n则对任意的则对任意的0t1为控制不同类别混合程度为控制不同类别混合程度的自由参数。的自由参数。现在学习的是第15页，共38页模糊模糊k-均值聚类算法均值聚类算法1.begin initialize n,c,b,m1,mc;2.do 计算计算n个样本对个样本对c个类别的隶属度：个类别的隶属度：3.重新计算各个聚类的均值重

5、新计算各个聚类的均值m1,mc;4.until m1,mc变化很小；变化很小；5.return m1,mc。现在学习的是第16页，共38页10.4 层次聚类层次聚类1.begin initialize c,cn,Dixi,i=1,n;2.do cc-13.求最接近的聚类，如求最接近的聚类，如Di和和Dj；4.合并合并Di和和Dj；5.until c=c;6.return c个聚类个聚类;7.end现在学习的是第17页，共38页层次聚类的树图层次聚类的树图相相似似度度标标尺尺现在学习的是第18页，共38页层次聚类的特点层次聚类的特点n层次聚类不用初始化聚类中心，因此聚类结果不受层次聚类不用初始化

6、聚类中心，因此聚类结果不受初初始聚类中心始聚类中心的影响；的影响；n需要定义类别之间的相似性度量；需要定义类别之间的相似性度量；n当样本数比较多时，算法的计算量比较大（算法第当样本数比较多时，算法的计算量比较大（算法第3步）。步）。n聚类结果同样是对平方误差准则函数的聚类结果同样是对平方误差准则函数的贪心优化贪心优化结果。结果。现在学习的是第19页，共38页聚类算法存在的问题（一）聚类算法存在的问题（一）n准则函数的选择准则函数的选择平方误差准则平方误差准则Je比较大比较大平方误差准则平方误差准则Je比较小比较小现在学习的是第20页，共38页聚类算法存在的问题（二）聚类算法存在的问题（二）n特

7、征量纲的影响（缩放坐标轴）特征量纲的影响（缩放坐标轴）现在学习的是第21页，共38页10.5 竞争学习竞争学习nHebb假设假设：如果一条突触两侧的神经元同时被激活，则该突：如果一条突触两侧的神经元同时被激活，则该突触的强度将会增大；触的强度将会增大；nHebb学习规则学习规则：第：第i个神经元与第个神经元与第j个神经元之间的连接个神经元之间的连接wij，第，第i个神经元向第个神经元向第j个神经元的输出为个神经元的输出为p，第，第j个神经元的输个神经元的输出为出为a，则：，则：其中其中为学习率。为学习率。现在学习的是第22页，共38页竞争网络竞争网络n样本的特征维数为样本的特征维数为d，输入层

8、神经，输入层神经元数元数d+1，输入样本须归一化到，输入样本须归一化到单位长度；单位长度；n输出层对应输出层对应c个类别；个类别；n输出层神经元之间有侧向抑制连输出层神经元之间有侧向抑制连接，对于每一个输入样本，只有接，对于每一个输入样本，只有一个竞争层神经元被激活一个竞争层神经元被激活(称为胜称为胜元，输出元，输出1)，其它神经元被抑制，其它神经元被抑制(输出输出0)。输入层输入层竞争层竞争层现在学习的是第23页，共38页竞争学习竞争学习1.begin initialize 学习率学习率,训练样训练样本数本数n,类别类别数数c,迭代次数迭代次数k，初始，初始权值权值w1,wc;2.归归一化所

9、有一化所有训练样训练样本和本和权值权值；3.do 随机随机选选取一个取一个x4.计计算算胜胜元：元：5.权值权值修正：修正：6.权值归权值归一化：一化：7.until 在在k次重复中次重复中w无无显显著改著改变变；8.return w1,wc现在学习的是第24页，共38页竞争学习过程竞争学习过程现在学习的是第25页，共38页10.6 自组织特征映射自组织特征映射n自组织特征映射自组织特征映射也称为也称为Kohonen网络网络(SOFM,Self-Organizing Feature Map)；nSOFM采用的仍然是采用的仍然是竞争学习规则竞争学习规则，与竞争网络不同，与竞争网络不同的是竞争网络

10、每次只对一个胜元的权值进行调整，而的是竞争网络每次只对一个胜元的权值进行调整，而SOFM则对以胜元为中心的一个则对以胜元为中心的一个邻域内的神经元邻域内的神经元均进均进行调整；行调整；n经过学习后的网络会具有经过学习后的网络会具有空间拓扑有序性空间拓扑有序性。现在学习的是第26页，共38页1维维SOFM网络拓扑结构网络拓扑结构窗函数窗函数输入层输入层竞争层竞争层现在学习的是第27页，共38页2维维SOFM网络拓扑结构网络拓扑结构窗函数窗函数y*输入层输入层竞争层竞争层现在学习的是第28页，共38页SOFM学习算法学习算法1.begin initialize 网络拓扑结构，权值，邻域网络拓扑结构

11、，权值，邻域(0)，迭代次数，迭代次数T，学习率，学习率(0)，t0；2.2.归一化所有训练样本和权值；归一化所有训练样本和权值；3.3.do 随机选择样本随机选择样本x；4.4.计算胜元计算胜元y*：5.5.调整权值：调整权值：6.6.权值归一化：权值归一化：7.7.tt+1；8.until t=T其中其中(t)逐渐缩小范围，逐渐缩小范围，(t)逐渐减小。逐渐减小。现在学习的是第29页，共38页10.6 谱聚类谱聚类n谱聚类谱聚类是一种新的聚类分析方法是一种新的聚类分析方法n谱聚类通过求取核矩阵的特征值和特征矢量实现聚类。谱聚类通过求取核矩阵的特征值和特征矢量实现聚类。n令：令：x1,xn

12、为样本集合，为样本集合，为输为输入空入空间间到特征到特征空空间间的映射，并且的映射，并且|(x)|=1，k为为相相应应的核函数。的核函数。n核矩核矩阵阵K=k(xi,xj)nn现在学习的是第30页，共38页两类谱聚类两类谱聚类1.计算核矩阵计算核矩阵K；2.计算对应最大特征值的特征矢量计算对应最大特征值的特征矢量y（n维）；维）；3.通过一个阈值通过一个阈值量化量化y，y中的元素大于中的元素大于的置的置为为1，小，小于于的置的置为为0；4.对应对应0的的样样本本为为一个一个类别类别，对应对应1的的样样本本为为另一个另一个类类别别。现在学习的是第31页，共38页例例10.1n将将19个样本分成个

13、样本分成2个聚类。个聚类。x1=(0,0)t,x2=(1,0)t,x3=(0,1)t,x4=(1,1)t,x5=(2,1)t,x6=(1,2)t,x7=(2,2)t,x8=(3,2)t,x9=(6,6)t,x10=(7,6)t,x11=(8,6)t,x12=(7,7)t,x13=(8,7)t,x14=(9,7)t,x15=(7,8)t,x16=(8,8)t,x17=(9,8)t,x18=(8,9)t,x19=(9,9)t现在学习的是第32页，共38页核矩阵：核矩阵：现在学习的是第33页，共38页n特征值特征值 最大特征值对应特征矢量最大特征值对应特征矢量现在学习的是第34页，共38页聚类结果聚

14、类结果现在学习的是第35页，共38页多类别谱聚类多类别谱聚类1.计算核矩阵计算核矩阵K；2.计算计算K的特征值和特征矢量；的特征值和特征矢量；3.观察特征值分布，确定聚类数观察特征值分布，确定聚类数m；4.利用对应前利用对应前m个特征值的特征矢量确定样本的类别个特征值的特征矢量确定样本的类别归属。归属。现在学习的是第36页，共38页例例10.2n多类别聚类多类别聚类 (0,0),(0,1),(1,0),(1,1),(0,10),(0,11),(1,10),(1,11),(10,0),(10,1),(11,0),(11,1),(10,10),(10,11),(11,10),(11,11)现在学习的是第37页，共38页 特征值：特征值：最大最大4个特征值对应的特征矢量：个特征值对应的特征矢量：现在学习的是第38页，共38页