北京大学：《模式识别》课程教学资源（课件讲稿）非监督学习方法.pdf_大学文库

13 8.1.2 单峰子集分离的迭代算法  假设数据集 S 有一个划分其中Γi 互不相交，且  估计各类的加权类条件概率密度函数：可用 Parzen 方法估计类条件概率密度 , 1 i c i S     N , N N S ; i i  i  i   ( | ) ( | ); i i i N f p N y y   1 1 ( | ) ( , ), . N i i i ii j i p K N  y yy y     14 8.1.2 单峰子集分离的迭代算法  考虑两个子集（类）的类条件概率密度函数加权估计值之间的“距离”   ( | ) ( | ) ( ) , 2  f y i  f y j p y dy 根据使两类的类条件概率密度函数加权估计值之间的“距离”最大进行类别划分 15 8.1.2 单峰子集分离的迭代算法  聚类准则：求子集划分能最大化  求解  考查某个样本 yk 从Γj 移入Γi,得到新的 2 1 1 1 [ ( | ) ( | )] ( ) ; 2 c c i j i j J ff p d         y y yy i j ~ , ~ ( | ) ( | ), ( | ) ( | ), 1 ( ) , ; i i i j j j k ffK f f N f f          y y y y y y   且一般 N 较大；只有当y很接近 yk时，△fi 才能不接近于0。 16 8.1.2 单峰子集分离的迭代算法  求解  考虑 J 的变化量   2 2 () 2 ( | ) ( | ) () , i i ji J cf p d c f f fp d             y y y y yy 第一项恒大于0 第二项取决于 f(y|Γi )-f(y|Γj )：差越大，△J 越大。注意：当 y 不是 yk的近邻时，△fi 的值接近于0。 17 8.1.2 单峰子集分离的迭代算法  求解  通过把 yk从Γj 移入Γi，使得 J 增大，故移入时应该选择使△J 尽可能大的Γi，即选择从而使得△J 最大；  如存在两个（或以上）子集的最大（相等），则可移入其中任意一类。 ( | ) max ( | ), k l l k i f y   f y  ( | ) k i f y  18 8.1.2 单峰子集分离的迭代算法  算法步骤 1. 对数据集 S 选定一个初始划分； 2. 对 S 中的每一个样本 y，逐一计算并把 y 重新分配到使得最大的子集中； 3. 如果有任何点进行了类别的转移，则重复上一步骤；直到不再有样本发生转移。 ( | ), k i f y  ( | ), k i f y 

8.2类别分离的间接方法 8.2.1C-均值算法（K-均值/means) 口三个要点：口问题假设：对样本集K={x}尚不知每个样本的 ■样本与样本/样本聚类间相似性的度量；类别，但可假设所有样本可分为c类，各类样本 ■准则函数：聚类质量的判别标准；在特征空间依类聚集，且近似球形分布； ■初始分类方法及迭代算法；口基本思路：用一代表点(prototype)来表示一个可盖化案英中图聚类，如类内均值m,来代表聚类K; 初始聚为口目标：口聚类准则：误差平方和J ■类内元素相似性高：家类合回y→聚类结束 ■类间元素相似性低。 J=会名mf 修改聚为 8.2.1C-均值算法(K-均值/means) 8.2.1C-均值算法（K-均值/means 口求解口C-均值算法步骤 ■假设已有一个初始划分，考查「k中的样本y,如 1.选择一个初始划分，并计算各类均值；把y移入「，J的改变量是 2.选择一个样本y,设y∈；如N,=l,则重选 w=或-m+- y;否则继续； 3. 分别计算如把y移动到其他各类中造成△；如果△J<0, 4.如果所有的△都大于0，则不移动y。否则移动y到产生最小△的类； →把y从「。移入「，会减小J。更新相关类的均值，以及J值：如连续迭代N次J值不变，则停止；否则转2。 8.2.1C-均值算法(K-均值/means) 8.2.1C-均值算法（K-均值/means) 初始代表，点的选择初始分类方法 1.经验选择； 1,最近距离法：离哪个代表点近就归入哪一类； 2.随机分成c类，选各类重心作为代表点； 2. 最近距离法归类，但每次都重新计算类代表 3.“密度法”选择代表点：点；口计算每个样本的一定球形邻域内的样本数作为” 密度”，选“密度”最大的样本点作为第一个代表 3. 直接划分初始分类：第一个样本自成一类，第点，在离它一定距离之外最大“密度”点作为第二二个样本若离它小于某距离阈值则归入此类，个代表点，，依此类推：否则建新类，… 4.用前c个样本点作为代表点； 4.将特征归一化，用样本各特征之和作为初始分 5.用c-1聚类求c个代表点：各类中心外加离它类依据。们最远的样本点，从1类开始

19 8.2 类别分离的间接方法  三个要点：  样本与样本/样本聚类间相似性的度量；  准则函数：聚类质量的判别标准；  初始分类方法及迭代算法；  目标：  类内元素相似性高；  类间元素相似性低。 20 8.2.1 C-均值算法（K-均值/means）  问题假设：对样本集 KN={xi } 尚不知每个样本的类别，但可假设所有样本可分为 c 类，各类样本在特征空间依类聚集，且近似球形分布；  基本思路：用一代表点 (prototype) 来表示一个聚类，如类内均值 mi 来代表聚类 Ki ；  聚类准则：误差平方和 J 2 1 . i c i i J      y y m 21  求解  假设已有一个初始划分，考查Γk中的样本 y，如把 y 移入Γj，J 的改变量是 8.2.1 C-均值算法（K-均值/means） 2 2 , 1 1 0 k j k j k j k j N N J N N J J             ym ym y 如果，把从移入会减小。 22  C-均值算法步骤 1. 选择一个初始划分，并计算各类均值； 2. 选择一个样本 y，设如则重选 y；否则继续； 3. 分别计算如把 y 移动到其他各类中造成 4. 如果所有的都大于0，则不移动 y。否则移动 y 到产生最小的类； 5. 更新相关类的均值，以及 J 值； 6. 如连续迭代 N 次 J 值不变，则停止；否则转2。 8.2.1 C-均值算法（K-均值/means） ; i y 1, Ni J; J J 23  初始代表点的选择 1. 经验选择； 2. 随机分成 c 类，选各类重心作为代表点； 3. “密度法”选择代表点：  计算每个样本的一定球形邻域内的样本数作为” 密度”，选“密度”最大的样本点作为第一个代表点，在离它一定距离之外最大“密度”点作为第二个代表点，…，依此类推； 4. 用前 c 个样本点作为代表点； 5. 用 c-1 聚类求 c 个代表点：各类中心外加离它们最远的样本点，从 1 类开始。 8.2.1 C-均值算法（K-均值/means） 24  初始分类方法 1. 最近距离法：离哪个代表点近就归入哪一类； 2. 最近距离法归类，但每次都重新计算类代表点； 3. 直接划分初始分类：第一个样本自成一类，第二个样本若离它小于某距离阈值则归入此类，否则建新类，…… 4. 将特征归一化，用样本各特征之和作为初始分类依据。 8.2.1 C-均值算法（K-均值/means）

25 8.2.1 C-均值算法（K-均值/means） 26  讨论  优点 时间复杂度 O(N)； 简单易实现； 适用于“球形”分布的数据；  用于非监督模式识别的问题 要求类别数已知； 是最小方差划分，并不一定能反映内在分布； 与初始划分有关，不保证全局最优。  存在不少变种：初始划分的方法；更新均值的时机；聚类数目的动态决定，等等。 8.2.1 C-均值算法（K-均值/means） 27 8.2.2 样本和核相似性度量的聚类算法  采用一个“核” Kj 代表一个类Γj ；  核 Kj 可以是一个函数，一个点集，某种适当的分类模型等等。  定义样本和各类的核之间的相似性度量  聚类准则函数，即最小化的目标函数 ( , ); K j  y ( , ). 1      c j y j j J y K 28  算法步骤，类似于 C-均值： 1. 选择初始划分，并计算初始核 Kj ，j=1,…,c； 2. 按照如下规则把各样本分类： 3. 更新核，并重复步骤 2-3 直至收敛。  C-均值算法 = 核是类均值，样本和核之间的相似性度量是欧式距离的特例。 8.2.2 样本和核相似性度量的聚类算法 f Δ( ) minΔ( ), then ; 1 i j i , ,c j i ,K  ,K   y y y  29  算法收敛的充分条件：准则函数 J 满足  ：修正之前的分类集合和对应的核集合；  ：修正之后的分类集合和对应的核集合； 8.2.2 样本和核相似性度量的聚类算法 ( , ) ( , ), ( , ) ( , ); J J J J   Γ K Γ K Γ K Γ K    如果那么 Γ,K Γ  ,K 30  正态核函数：适用于各类为正态分布  参数集从各类样本中估计；  相似性度量： 8.2.2 样本和核相似性度量的聚类算法 1 /2 1/2 1 1 ˆ ( , ) exp ( ) ( ) (2 ) | | ˆ 2 T j j jj j d j K V            y ym Σ y m Σ ， ) ˆ ( , Vj  m j Σj 1 1 1 ˆ ˆ ( , ) ( ) ( ) log| | . 2 2 T Kj jj j j      y ym Σ y m Σ

31  主轴核函数：适用于各类样本集中分布在各自的主轴方向上的子空间里的情况 8.2.2 样本和核相似性度量的聚类算法   前个最大特征值对应的特征向量系统；其中是第类样本协方差阵的 , , , ( , ) , 1 2 j j d T j j d j K V j U u u u y U y        ( ) ( ) ( , ) ( ) ( ) 是样本到主轴子空间的距离。 j T j j j T j T K j j j j y m U U y m y y m U U y m          32 8.2.3 近邻函数准则函数  近邻函数：不同样本间相似性的度量  如果 yi 是 yj 的第 I 个近邻，则 yi 对 yj 的近邻系数为 I;  如果 yj 是 yi 的第 K 个近邻，则 yj 对yi 的近邻系数为 K;  yi 和 yj 之间的近邻函数： I K 2, i j; ij     33 8.2.3 近邻函数准则函数  连接：如 yi和 yj被分到同一类，则称它们相互连接；  每个连接对应一个连接损失：两点之间的近邻函数αij ;  一个点和其自身的连接损失为αii=2N（N 是样本总数），以惩罚只有一个点的聚类；  不同类的点不存在连接，故连接损失αij=0;  总类内损失： 1 1 . N N within ij i j L      34 8.2.3 近邻函数准则函数  连接损失可使得密度相近的点容易聚成一类 1 6  2  5,  2 1 2 1; 损失：ik ij 35 8.2.3 近邻函数准则函数  第 i 类和第 j 类之间的最小近邻函数值定义为：  记第 i 类内最大连接损失为αimax ;  定义第 i 类和第 j 类之间的连接损失为βij ，其设计目标是：如果两类间的最小近邻值小于任何一方的类内的最大连接损失时，损失代价就是正的，从而应该考虑把这两类合并。   , min , k il j ij ij      y y 36 8.2.3 近邻函数准则函数  总类间损失：  总类内损失：  准则函数： ; between ij i j L     1 1 ; N N within ij i j L      . Lwithin Lbetween J  