《大数据处理与智能决策》教学课件-聚类算法基础理论

《《大数据处理与智能决策》教学课件-聚类算法基础理论》由会员分享，可在线阅读，更多相关《《大数据处理与智能决策》教学课件-聚类算法基础理论（51页珍藏版）》请在金锄头文库上搜索。

1、聚类算法基础理论大数据处理与智能决策教研室智能技术与工程学院重庆科技学院主要内容：主要内容：一一、有监督学习和无监督学习、有监督学习和无监督学习二、基于距离阈值的聚类算法二、基于距离阈值的聚类算法三、层次聚类法三、层次聚类法四、动态聚类法四、动态聚类法3二、基于距离阈值的聚类算法二、基于距离阈值的聚类算法1） 问题：问题：有N个待分类的模式 ，要求按距离阈值T分类到以 为聚类中心的模式类中。2） 算法描述算法描述 任取样本Xi 作为第一个聚类中心的初始值，如令Z1 = X1 。 计算样本X2 到Z1 的欧氏距离 ， 若 ，定义一新的聚类中心Z2 = X2 ； 否则 X2 以Z1为中心的聚类。(

2、T_threshold )1 近邻聚类法近邻聚类法4依此类推，直到将所有的N个样本都进行分类。 假设已有聚类中心Z1、Z2，计算 和 ，若 且 ，则建立第三个聚类中心Z3 = X3； 否则X3离Z1和Z2中最近者（最近邻的聚类中心）。3） 算法特点算法特点B）优点：计算简单。（一种虽粗糙但快速的方法）A）局限性：很大程度上依赖于第一个聚类中心的位置选择、待 分类模式样本的排列次序、距离阈值T的大小以及样本分布 的几何性质等。5 用先验知识指导阈值T 和起始点Z1的选择，可获得合理的聚类结果。否则只能选择不同的初值重复试探，并对聚类结果进行验算，根据一定的评价标准，得出合理的聚类结果。 对对结结

3、果果验验算算，类类内内各各样样本点间距离方差之和太大本点间距离方差之和太大减小减小T，修改中心，修改中心Z。4）算法讨论）算法讨论图5 选取不同阈值和聚类中心时得到的不同聚类结果62 最大最小距离算法（小中取大距离算法最大最小距离算法（小中取大距离算法 ） 1） 问题问题已知N个待分类的模式 ， 分类到聚类中心 对应的类别中 。2） 算法描述算法描述 选任意一模式样本做为第一聚类中心Z1。 选择离Z1距离最远的样本作为第二聚类中心Z2。 逐个计算各模式样本与已确定的所有聚类中心之间的距离，并选出其中的最小距离。例当聚类中心数k=2时，计算min( Di1 , Di2 )，i=1，N（N个最小距

4、离） 7 将样本 按最近距离划分到相应聚类中心对应的类别中。 重复步骤，直到没有新的聚类中心出现为止。 在所有最小距离中选出最大距离，如该最大值达到 的一定分数比值一定分数比值( 阈值阈值T ) 以上以上，则相应的样本点取为新的聚类中心，返回；否则，寻找聚类中心的工作结束。（：用试探法取为一固定分数，如1/2。）则Z3存在。为使聚类中心更有代表性，可取各类的样本均值作为聚类中心。例k =2时思路总结：思路总结： 先找中心后分类；关键：怎样开新类，聚类中心如何定。先找中心后分类；关键：怎样开新类，聚类中心如何定。8例3 对图示模式样本用最大最小距离算法进行聚类分析。 选选Z1=X1距距Z1最远，

5、选为最远，选为Z2。计算。计算T。对应最小距离对应最小距离中的最大值，中的最大值，且且T，选作，选作Z3。结果：Z1=X1；Z2=X6； Z3=X7 。 用全体模式对三个聚类中心计算最小距离中的最大值，无T 情况，停止寻找中心。 聚类10个最小距离中，X7对应的距离T,9三三 层次聚类法层次聚类法（Hierarchical Clustering Method） （系统聚类法、分级聚类法）（系统聚类法、分级聚类法）思路：每个样本先自成一类， 然后按距离准则逐步合并，减少类数。1 算法描述算法描述 N个初始模式样本自成一类，即建立N 类：计算各类之间（即各样本间）的距离，得一NN维距离矩阵D(0)

6、。“0”表示初始状态。(G_Group)10假设已求得距离矩阵D(n)（n为逐次聚类合并的次数），找出D(n)中的最小元素，将其对应的两类合并为一类。由此建立新的分类：。计算合并后新类别之间的距离，得D(n+1)。跳至第2步，重复计算及合并。 结束条件：结束条件：取距离阈值T，当D(n)的最小分量超过给定值 T 时，算法停 止。所得即为聚类结果。或不设阈值T，一直到将全部样本聚成一类为止，输出聚类的分 级树。112 问题讨论：类间距离计算准则问题讨论：类间距离计算准则HK最短距离法最短距离法 如H、K是两个聚类，则两类间的最短距离定义为：H类中的某个样本XH和K类中的某个样本XK之间 的欧氏距

7、离。DHK：H类中所有样本与K类中所有样本之间的最小距离。12如果K类由I和J两类合并而成，则得到递推公式：HKIJ最长距离法最长距离法 若K类由I、J两类合并而成，则有：13中间距离法中间距离法 介于最长与最短的距离之间。如果K类由I类和J类合并而成，则H和K类之间的距离为重心法重心法 将每类中包含的样本数考虑进去。若I类中有nI个样本，J类中有nJ个样本，则类与类之间的距离递推式为 14 定义类间距离的方法不同，分类结果会不太一致。实际问定义类间距离的方法不同，分类结果会不太一致。实际问题中常用几种不同的方法，比较分类结果，从而选择一个比较题中常用几种不同的方法，比较分类结果，从而选择一个

8、比较切合实际的分类。切合实际的分类。类平均距离法类平均距离法：H类任一样本Xi和K类任一样本Xj之间的欧氏距离平方。若K类由I类和J类合并产生，则递推式为15例：给出6个五维模式样本如下，按最短距离准则进行系统聚类分类。计算各类间欧氏距离：解：（1）将每一样本看作单独一类，得：， ， ， ；16D(0)000000（2）将最小距离 对应的类 和 合并为1类，得 新的分类。计算聚类后的距离矩阵D(1)：由D(0) 递推出D(1) 。得距离矩阵D(0)：17D(0)000000 D(1) 0 0 0 0 0（3）将D(1)中最小值 对应的类合为一类， 得D(2)。 D(2) 0 0 0 018（4

9、）将D(2)中最小值 对应的类合为一类，得D(3)。 D(2) 0 0 0 0 D(3) 0 0 0若给定的阈值为 ，D(3)中的最小元素 ，聚类结束。若无阈值，继续分下去，最终全部样本归为一类。可给出聚类过程的树状表示图。19 层次聚类法的树状表示 类间距离类间距离阈值增大，阈值增大，分类变粗。分类变粗。20五、五、 动态聚类法动态聚类法两种常用算法：* K-均值算法* 迭代自组织的数据分析算法(ISODATA, iterative self-organizing data analysis techniques algorithm) 判断判断合理性合理性选初始选初始 中心中心聚类聚类合理合

10、理不合理不合理输出输出修改修改图9 动态聚类法的基本思路21K-均值算法的聚类准则：聚类中心Zj的选择应使准则函数J极小， 即使Jj的值极小。1 K-均值算法均值算法 基于使聚类准则函数最小化，准则函数：聚类集中每一样本点到该类中心的距离平方和。 对于第j个聚类集，准则函数定义为Sj：第j个聚类集（域），聚类中心为Zj ；Nj：第j个聚类集Sj中所包含的样本个数。对所有K个模式类有221） 算法描述算法描述括号内序号：迭代运算的次序号。（1）任选K个初始聚类中心：Z1(1)， Z2(1)， ZK(1) 算法主要流程：1. 随机地选择k个对象，每个对象初始地代表了一个簇的中心；2. 对剩余的每个

11、对象，根据其与各簇中心的距离，将它赋给最近的簇；3. 重新计算每个簇的平均值，更新为新的簇中心；4. 不断重复2、3，直到准则函数收敛。23（2）按最小距离原则将其余样本分配到K个聚类中心中的某一 个，即：若 ，则注意：注意：k迭代运算次序号；K聚类中心的个数 。 Nj：第j类的样本数。（3）计算各个聚类中心的新向量值：（4）如果 ，则回到（2），将模式 样本逐个重新分类，重复迭代计算。这里：分别计算K个聚类中的样本均值向量，故称K-均值算法。，算法收敛，计算完毕。如果24聚类过程中，聚类中心位置或个数发生变化。“动态”聚类法2） 算法讨论算法讨论 结果受到所选聚类中心的个数和其初始位置，以及

12、模式样本的几何性质及读入次序等的影响。实际应用中需要试探不同的K值和选择不同的聚类中心起始值。25例：已知20个模式样本如下，试用K-均值算法分类。 解： 取K=2，并选： 计算距离，聚类： ：26： ： ，可得到： 计算新的聚类中心： 判断：，故返回第步。27 从新的聚类中心得： ： 有： 计算聚类中心： 28 返回第步，以Z1(3)， Z2(3)为中心进行聚类。 以新的聚类中心分类，求得的分类结果与前一次迭代结果相 同： 计算新聚类中心向量值，聚类中心与前一次结果相同，即： ，故算法收敛，得聚类中心为结果图示：29图10 K-均值算法聚类结果X1X4X3X5X8X9X7X10X2X6x1x

13、213579135790X11X12X13X14X15X16X17X18X19X2030 上述K-均值算法，其类型数目假定已知为K个。当K未知时，可以令K逐渐增加， 此时J j 会单调减少。最初减小速度快，但当K 增加到一定数值时，减小速度会减慢，直到K =总样本数N 时，Jj = 0。JjK关系曲线如下图：3）聚类准则函数）聚类准则函数Jj与与K的关系曲线的关系曲线JjA135724608109K 曲线的拐点 A 对应着接近最优的K值（J 值减小量、计算量以及分类效果的权衡）。 并非所有的情况都容易找到关系曲线的拐点。迭代自组织的数据分析算法可以确定模式类的个数K 。312 迭代自组织的数据

14、分析算法迭代自组织的数据分析算法(iterative self-organizing data analysis techniques algorithm,ISODATA)算法特点 加入了试探性步骤，组成人机交互的结构； 可以通过类的自动合并与分裂得到较合理的类别数。 相似：聚类中心的位置均通过样本均值的迭代运算决定。相异： K-均值算法的聚类中心个数不变； ISODATA的聚类中心个数变化。 与K-均值算法比较：1）算法简介）算法简介32基本思路： （1）选择初始值包括若干聚类中心及一些指标。可在迭代运 算过程中人为修改，据此将N个模式样本分配到各个聚类中 心去。（3）聚类后的处理：计算各类

15、中的距离函数等指标，按照给定的 要求，将前次获得的聚类集进行分裂或合并处理，以获得新 的聚类中心，即调整聚类中心的个数。（4）判断结果是否符合要求： 符合，结束； 否则，回到（2）。 （2）按最近邻规则进行分类。33算法共分十四步： 第一 六步：预选参数，进行初始分类。 为合并和分裂准备必要的数据。 第七步：决定下一步是进行合并还是进行分裂。 第八 十步：分裂算法。 第十一 十三步：合并算法。 第十四步：决定算法是否结束。 2）算法描述）算法描述设有N个模式样本X1，X2，XN 。预选参数，进行初始分类。第一步：预选NC个聚类中心 ， NC也是聚类过程 中实际的聚类中心个数。预选指标： 34K

16、：希望的聚类中心的数目。N：每个聚类中应具有的最少样本数。若样本少于N ，则该 类不能作为一个独立的聚类，应删去。S ：一个聚类域中样本距离分布的标准差阈值。标准差向量的 每一分量反映样本在特征空间的相应维上，与聚类中心的 位置偏差（分散程度）。要求每一聚类内，其所有分量中 的最大分量应小于S，否则该类将被分裂为两类。C ：两聚类中心之间的最小距离。若两类中心之间距离小于 C，则合并为一类。L：在一次迭代中允许合并的聚类中心的最大对数。 I：允许迭代的次数。35第二步：把N个样本按最近邻规则分配到NC个聚类中。若 则 第三步：若Sj中的样本数NjN ，则取消该类，并且NC减去1。 第四步：修正各聚类中心值。第五步：计算Sj类的类内平均距离 。 第六步：计算总体平均距离 ，即全部样本到各自聚类中心距 离的平均距离。N：每类应具有的 最少样本数。363) 如果迭代的次数是偶数，或NC2K，即聚类中心数目大于或 等于希望数的两倍，则跳到第十一步(合并)。否则进入第八步 (分裂)。第七步：判决是进行分裂还是进行合并，决定迭代步骤等。判断分裂还是合并。1) 如迭代已达I次(最后一次)，置C=0