10-非监督学习方法

第十章非监督学习方法„10.1引言„10.2单峰子集的分离方法„10.3类别分离的间接方法„10.4分级聚类方法„10.5其他聚类方法简介„10.6聚类中的问题10.1引言10.1引言„有监督：样本数据类别已知，训练分类器以求对新数据进行分类„非监督：样本数据类别未知，首先要求对样本集进行分类(聚类)„非监督学习方法大致分为两大类：„基于概率密度函数估计的方法„基于样本间相似性度量的方法10.1引言HierarchicalClustering分层聚类HierarchicalClustering分层聚类PartitionalClustering分块聚类PartitionalClustering分块聚类K-SeriesK-SeriesPCA/SVDbasedmethodsPCA/SVDbasedmethodsPDFbasedmethodsPDFbasedmethodsGraphTheorybasedmethodsGraphTheorybasedmethodsTop-downDivisionTop-downDivisionBottom-upAgglomerativeBottom-upAgglomerativeOthermethodsOthermethods10.2单峰子集的分离方法10.2单峰子集的分离方法„思想：把特征空间分为若干个区域，在每个区域上混合概率密度函数是单峰的，每个单峰区域对应一个类„如下图简单示例，x=0和y=0这两个超平面可以把(x,y)平面分成四个单峰区域10.2单峰子集的分离方法10.2单峰子集的分离方法„投影方法„多维空间中直接划分成单峰区域比较困难，而一维空间中则比较简单。„寻找一个坐标系统，在该系统下，数据的混合概率密度函数可以用边缘概率密度表示。„如果某边缘概率密度函数呈现多峰形式，则在此坐标轴上（一维）作分割。10.2单峰子集的分离方法„投影方法（续）„一维空间中的单峰分离}|{SyyuSuSTiii∈=轴上的投影为在样本集对Si应用直方图方法估计概率密度函数找到概率密度函数的峰，以及峰之间的谷底在谷底处做垂直于ui的超平面对数据分割10.2单峰子集的分离方法10.2单峰子集的分离方法„投影方法（续）„确定合适的坐标系统ui„启发式的方法：使投影{uiTy}的方差昀大，方差越大，类之间分离的程度也可能越大„满足这样要求的ui是样本协方差矩阵的昀大特征值对应的特征向量„存在问题：这样选择的ui有时并不能产生多峰的边缘密度函数10.2单峰子集的分离方法„投影方法（续）„算法步骤1.计算样本协方差阵的昀大特征值对应的特征向量ui，把样本数据投影到ui上2.用直方图法求边缘概率密度函数3.找到边缘概率密度函数的各个谷点，在这些谷点上作垂直于ui的超平面把数据划分成几个子集4.如果没有谷点，则用下一个昀大的特征值代替5.对所得到的各个子集进行同样的过程，直至每个子集都是单峰为止10.2单峰子集的分离方法„单峰子集分离的迭代算法„考虑数据S有一个划分)|()|(||,||,1iiiiiiiiiciypNNyfSNNNSΓ=Γ===ΓΓΓ=∑=为加权的类条件概率密度互不相交，且其中U10.2单峰子集的分离方法„单峰子集分离的迭代算法（续）„两个子集（类）之间的“距离”[][]昀大目标：使∫∑∑∫==Γ−Γ=Γ−ΓdyypyfyfJdyypyfyfcicjjiji)()|()|()()|()|(112210.2单峰子集的分离方法„单峰子集分离的迭代算法（续）„考虑把yk从Γi中移到Γj中造成J的改变是估计核其中()),,(1)()]|()|([2)(]2[2KyyKNffdyypfyfyfcdyypfcJkjiijii=∆−=∆∆Γ−Γ+∆=∆∫∫10.2单峰子集的分离方法„单峰子集分离的迭代算法（续）„第一项恒大于0„第二项主要取决于差越大，∆J越大„yk应该从Γj中移到使昀大的Γi中)|(iyfΓ)|()|(jiyfyfΓ−Γ10.2单峰子集的分离方法„单峰子集分离的迭代算法（续）„算法步骤1.对S选定一个初始划分2.对S中每一个点y，计算，并把y重新分配到使昀大的类中。3.如果有任何点进行了类别的转移，那么重复上一步骤。)|(iyfΓ)|(iyfΓ10.3类别分离的间接方法10.3类别分离的间接方法„两个要点„样本间相似性的度量„准则函数：聚类质量的判别标准„目标„类内元素相似性高„类间元素相似性低10.3类别分离的间接方法„C-均值算法（K-Means,K-均值)„昀小误差平方和准则，mi是类内均值„假设已经有了初始划分，把Γk中的一个元素y移到Γj中时，J的改变量∑∑=Γ∈−=ciyiimyJ12||||22||||1||||1jjjkkkmyNNmyNNJ−++−−−=∆10.3类别分离的间接方法„C-均值算法（续）„算法步骤1.选择一个初始划分，并计算各类均值2.选择一个样本y，设位于Γk中。分别计算把y移到其他各类中造成的∆J3.若所有∆J都大于0，则不移动y。否则移动y到产生昀小∆J的类4.更新相关类的均值，以及J值。5.若连续迭代N次J不变，则停止。否则转2。10.3类别分离的间接方法„C-均值算法（续）„初始划分的确定„初始代表点（核）的确定„剩余点的分配„C-均值算法存在不少变种„初始划分的方法„更新均值的时机„聚类数目的动态决定„等等10.3类别分离的间接方法„C-均值算法（续）„时间复杂度为O(N)„简单易实现„适用于“球形”分布的数据„一般对初始划分敏感10.3类别分离的间接方法„基于样本和核相似性度量的聚类算法„采用一个“核”来代表一个类„核Kj可以是一个函数，一个点集，等等„样本和核之间相似性的度量„准则函数，昀小化的目标),(jKy∆∑∑=Γ∈∆=cjyjjKyJ1),(10.3类别分离的间接方法„样本和核相似性度量的聚类算法（续）„算法步骤类似于C-均值1.选择初始划分并计算初始核2.重新分配各个样本3.修正核，并重复2-3直至收敛„C-均值算法=以类均值为核，欧氏距离作为样本和核之间的相似性度量),(min),(kkjjKyKyy∆=∆Γ∈如果10.3类别分离的间接方法„样本和核相似性度量的聚类算法（续）„算法收敛的充分条件：准则函数J满足„修正之前的分类和对应的核„修正之后的分类和对应的核)~,()~,~(),,()~,(ΚΓ≤ΚΓΚΓ≤ΚΓJJJJ那么如果K,ΓK~,~Γ10.3类别分离的间接方法„样本和核相似性度量的聚类算法（续）„正态核函数，适用于各类为正态分布|ˆ|log21)(ˆ)(21),)ˆ,()}(ˆ)(21exp{|ˆ|)2(1),(112/12/jijTijjjjijTijdjjmymyKymVmymyVyKΣ+−Σ−=∆Σ=−Σ−−Σ=−−（相似性度量从各类样本中估计参数集π10.3类别分离的间接方法„样本和核相似性度量的聚类算法（续）„主轴核函数，适用于各类样本集中在各自的主轴方向上的子空间里的情况距离是样本到主轴子空间的征向量系统个昀大特征值对应的特前类样本协方差阵的是第)]()[()]()[(),(),...,,(),(21jTjjjTjTjjjjjdjTjjmyUUmymyUUmyKydjuuuUyUVyKj−−−⋅−−−=∆==10.3类别分离的间接方法„样本和核相似性度量的聚类算法（续）„可以拟合各种形状的分布„需要预先知道数据的分布形状10.3类别分离的间接方法„近邻函数准则算法„近邻函数：样本间相似性的度量如果yi是yj的第I个近邻，yj是yi的第K个近邻„近邻函数使得密度相近的点容易聚成一类jiKIaij≠−+=,210.3类别分离的间接方法„近邻函数准则算法（续）„纯粹按照欧氏距离，则黄色点归为第一类„按照近邻函数值，黄色点归为第二类。这是比较合理的第一类第二类10.3类别分离的间接方法„近邻函数准则算法（续）„同一类中的点之间存在“连接”。连接损失就定义为两点之间的近邻函数αij。„一个点和其自身的连接损失定义为αii=2N，以惩罚只有一个点的聚类„不同类的点不存在连接，连接损失为αij=0„总类内损失∑∑===NiNjijwithinL11α10.3类别分离的间接方法„近邻函数准则算法（续）„第i类和第j类之间的昀小近邻函数值定义为„第i类内昀大连接损失记为αimax„第i类与第j类之间的连接损失定义为βij,)(min,klyyijjlikαγΓ∈Γ∈=10.3类别分离的间接方法„近邻函数准则算法（续）„βij的设计目标是：如果两类间的昀小近邻值大于任何一方的类内的昀大连接损失时，损失代价就是正的，从而应该考虑把这两类合并≤≤++≤+≤+−+−−=maxmaxmaxmaxmaxmaxmaxmaxmaxmaxmaxmaxmaxmax,,,,,,,)],()[(jijiijjiijjijiijjijjijiijiijjijiijjijiijijififififαγαγααγαγαγαγαγαγαγαγαγαγαγβ10.3类别分离的间接方法„近邻函数准则算法（续）„总类间损失„准则函数∑≠=jiijbetweenLβbetweenwithinLLJ+=10.3类别分离的间接方法„近邻函数准则算法（续）„算法步骤1.计算距离矩阵2.用距离矩阵计算近邻矩阵Mij，Mij表示yj是yi的第几个近邻3.计算近邻函数矩阵Lij=Mij+Mji-2I,Lii=2N4.在L中，每个点与其昀近邻连接，形成初始的划分5.对每两个类计算γij和αimax，αjmax，只要γij小于αimax、αjmax中的任何一个，就合并两类（建立连接）。重复至没有新的连接发生为止),(jiijyy∆=∆10.4分级聚类方法10.4分级聚类方法„树状结构的聚类y1,y2,y3,y4,y5y1,y2,y3y4,y5y1,y2y1y2y3y4y510.4分级聚类方法„自顶向下逐步分割„自底向上逐步合并„标准：损失函数。每一个分割或者合并，都要使损失昀小10.4分级聚类方法„自底向上逐步合并算法1.每个样本都各自形成一类2.从已有的类中，挑出两个合并成一类。被合并的两类是使损失函数昀小的两个类3.重复2直至形成包含所有样本的类。„损失函数：定义把两个类合并的损失10.4分级聚类方法„不同方法的损失函数Complete-LinkAverage-LinkSingle-LinkCostFunctionMethod),(min,jiSxSxxxdjjii∈∈∑∑∈∈iijjSxSxjijixxdss),(1),(max,jiSxSxxxdjjii∈∈10.5其他聚类方法简介10.5其他聚类方法简介„MixtureModels„假设数据是从k个未知分布E1,E2,...,Ek生成的。Ei的概率密度表示为„用表示yr是由Ei生成的概率，则算法的目的是昀大化似然函数„一般这种似然函数无法直接求昀大值。„用EM算法(Expectation-Maximum)解决这类问题)|(θypiirτ∏∑===nrkiriirypL11)|(),(θττθ10.5其他聚类方法简介„基于图论的聚类方法„每个数据构成图上一点。„根据数据之间的相似性，指定一个阈值可以建立图上的边„应用图论中的一些理论对该图进行划分„例：昀小生成树算法，找到图的昀小生成树，然后把树上昀长的边去掉形成两个类。在两个子图中再去掉昀长边，…，依次进行下去10.5其他聚类方法简介„基于图论的聚类方法（续）„例：高度连通子图算法„边割集：一个图G的边割集(edgecutset)定义为边的集合：从G中去掉该集合中的所有边之后，得到的图不连通。包含昀少边的边割集称为G的昀小边割集（称做MinCut）。„边连通度：图G的边连通度用k(G)表示，定义为昀小边割集的大小。如果k(G)=s，则G称为s-边连通图。10.5其他聚类方法简介„基于图论的聚类方法（续）„定义一个具有n个顶点的图G是“高度连通”的，如果k(G)n/2„算法步骤：1.去除图中度数很低的点。2.找到图的昀小边割集（有成熟算法），由此分