聚类分析（13）课件

,第十章 非监督模式识别,模 式 识 别,Pattern Recognition,,第十章 非监督学习方法,10.1 引言,3,2,10.2 单峰子集的分离方法,10.3 聚类方法,1,10.1 引言,有监督学习（supervised learning)：用已知类别的样本训练分类器，以求对训练集的数据达到某种最优，并能推广到对新数据的分类 非监督学习（unsupervised learning) ：样本数据类别未知，需要根据样本间的相似性对样本集进行分类(聚类，clustering) 非监督学习方法大致分为两大类： 基于概率密度函数估计的方法 基于样本间相似性度量的方法,方案对比,10.2 单峰子集的分离方法,思想：把特征空间分为若干个区域，在每个区域上混合概率密度函数是单峰的，每个单峰区域对应一个类 一维空间中的单峰分离: 对样本集 KN=xi 应用直方图方法估计概率密度函数，找到概率密度函数的峰以及峰之间的谷底，以谷底为阈值对数据进行分割,一维空间中的单峰子集分离,概率密度分析,多维空间投影方法,多维空间y中直接划分成单峰区域比较困难，把它投影到一维空间x中简化问题。 确定合适的投影方向u： 使投影x=uTy的方差最大，方差越大，类之间分离的程度也可能越大 样本协方差矩阵的最大特征值对应的特征向量满足这样的要求 存在问题：这样投影有时并不能产生多峰的边缘密度函数,概率密度分析,投影方法举例,基于样本间相似性度量的方法： 按样本间的相似性（在特征空间的距离远近）进行分类。 把距离近的样本聚为一类，距离远的归为另一类。,10.3 聚类方法,两种聚类方法 迭代的动态聚类方法 非迭代的层次聚类方法,10.3 聚类方法,聚类分析应用于图像分割,10.3 聚类方法,聚类分析应用于图像分割,10.3 聚类方法,聚类分析应用于入侵检测模型,10.3 聚类方法,聚类分析应用于,故障检测 蛋白质编码识别 车辆轨迹检测 各种区域划分,10.3.1 迭代的动态聚类方法,动态聚类方法的任务：,将数据集划分成一定数量的子集，因此要划分多少个 子集往往要预先确定，这个子集数目能够体现数据集 比较合理的划分。,需要解决的问题,如何确定划分的子集数目 如果划分数目已定，又如何找到最佳划分？于是需要 对不同划分作出评价，并找到优化的划分结果。这是 一个动态的迭代过程。,10.3.1 迭代的动态聚类方法,三个要点：,选定某种距离度量作为样本间的相似性度量； 确定样本合理的初始分类，包括代表点的选择，初始 分类的方法选择等； 确定某种评价聚类结果的准则函数，以调整初始分类 直到达到该准则函数的极值。,要点1准则函数,准则函数：聚类质量的判别标准，常用的最小误差平方和准则 反映了用c个聚类中心代表c个样本子集所带来的总的误差平方和。即各类样本与其所属样本均值间误差平方之总和。,目标: 类内元素相似性高，类间元素相似性低,要点2样本集的初始划分,凭经验选代表点，根据问题的性质、数据分布，从 直观上看来较合理的代表点C; 将全部样本随机分成C类，计算每类重心，把这些 重心作为每类的代表点; 按密度大小选代表点：以每个样本作为球心，以d 为半径做球形;落在球内的样本数称为该点的密度， 并按密度大小排序。 用前C个样本点作为代表点。,选一批代表点后，代表点就是聚类中心，计算其它样本到聚类中心的距离，把所有样本归于最近的聚类中心点，形成初始分类，再重新计算各聚类中心，称为成批处理法。 选一批代表点后,依次计算其它样本的归类，当计算完第一个样本时，把它归于最近的一类，形成新的分类。再计算新的聚类中心，再计算第二个样本到新的聚类中心的距离，对第二个样本归类。即每个样本的归类都改变一次聚类中心。此法称为逐个处理法。,要点2样本集的初始划分,直接用样本进行初始分类，先规定距离d,把第一个样品作为第一类的聚类中心，考察第二个样本，若第二个样本距第一个聚类中心距离小于d，就把第二个样本归于第一类，否则第二个样本就成为第二类的聚类中心，再考虑其它样本，根据样本到聚类中心距离大于还是小于d，决定分裂还是合并。,要点2样本集的初始划分,迭代计算,迭代过程在原理上与梯度下降法是一样的，即使 准则函数数值下降为准则。 初始划分只能作为一个迭代过程的初始条件，需要 按照准则函数极值化的方向对初始划分进行修改，在使用上面提到的误差平方和准则时，可以按以下方法进行.,相似性分析,C-均值算法（k-Means, k-均值),对样本集 KN =xi尚不知每个样本的类别，但可假设所有样本可分为C类，各类样本在特征空间依类聚集，且近似球形分布 用一代表点来表示一个聚类，如类内均值 mi 来代表聚类 Ci 聚类准则：误差平方和 J,相似性分析,C-均值算法的训练,初始化：选择c个代表点p1, p2, ,pc 建立c个空聚类列表： K1, K2, ,Kc 按照最小距离法则逐个对样本x进行分类： 计算J及用各聚类列表计算聚类均值，并用来作为各聚类新的代表点（更新代表点） 若J 不变或代表点未发生变化，则停止。否则转2。,相似性分析,C-均值算法的其他考虑,按照与C个代表点的最小距离法对新样本y进行分类，即： 初始划分的方法 更新均值的时机：逐个样本修正法与成批样本修正法 聚类数目的动态决定,相似性分析,例：成批处理法(ISODATA算法） 已知有20个样本，每个样本有2个特征，数据分布如下图,第一步：令C=2，选初始聚类中心为,例：成批处理法,第三步：根据新分成的两类建立新的聚类中心,第四步： 转第二步 第二步：重新计算 到z1(2) , z2(2) 的距离，把它们归为最近聚类中心，重新分为两类，,第三步，更新聚类中心,第四步， 第二步， 第三步，更新聚类中心,层次聚类：先把每个样本作为一类，然后根据它们间的相似性和相邻性聚合。 相似性、相邻性一般用距离表示 1. 最短距离： 两类中相距最近的两样品间的距离 2、最长距离：两类中相距最远的两样本间的距离,10.3.2 层次聚类方法,最短距离举例：,最长距离举例：,3、中间距离：最短距离和最长距离都有片面性，因此有时用中间距离。设1类和23 类间的最短距离为d12，最长距离为d13，23 类的长度为d23，则中间距离为：,4、均值距离：,10.3.2 层次聚类方法,划分序列：N个样本自底向上逐步合并一类： 每个样本自成一类（划分水平1） K水平划分的进行：计算已有的c=N-K+2个类的类间距离矩阵D(K-1)=dij(K-1)，其最小元素记作d(K-1)，相应的两个类合并成一类； 重复第2步，直至形成包含所有样本的类（划分水平N） 划分处于K水平时，类数c = N-K+1，类间距离矩阵D(K)=dij(K)，其最小元素记作d(K) 如果D(K) 阈值dT，则说明此水平上的聚类是适宜的,10.3.2 层次聚类方法,层次聚类树表示方法,y1,y2,y3,y4,y5,y6,1-水平 -,2-水平 -,3-水平 -,4-水平 -,5-水平 -,6-水平 -,分级 聚类,例：如下图所示 1、设全部样本分为6类 2、作距离矩阵D(0),3、求最小元素： 4、把G1, G3合并G7=(1,3) G4, G6合并G8=(4,6) 5、作距离矩阵D(1),6、若合并的类数没有达到要求，转3。否则停止。 3、求最小元素： 4、G8, G5, G2合并, G9=（2,5,4,6）,设有6个五维模式样本如下，按最小距离准则进行聚类分析： x1: 0, 3, 1, 2, 0 x2: 1, 3, 0, 1, 0 x3: 3, 3, 0, 0, 1 x4: 1, 1, 0, 2, 0 x5: 3, 2, 1, 2, 1 x6: 4, 1, 1, 1, 0,10.5 聚类中的问题,非监督模式识别问题存在更大的不确定性: 可利用信息少 相似性度量一般对数据尺度(scale)较敏感 影响聚类结果的因素：样本的分布，样本数量，聚类准则，相似性度量，预分类数等 针对不同数据，不同目标选择不同的聚类算法 动态聚类算法计算效率高，实际应用多,作业,画出ISODATA算法的流程框图 试用ISODATA算法对如下模式分布进行聚类分析： x1(0, 0), x2(3,8), x3(2,2), x4(1,1), x5(5,3), x6(4,8), x7(6,3), x8(5,4