An Estimation Algorithmfor Number of Clusters Based on Tabu.ppt

1、1,An Estimation Algorithm for Number of Clusters Based on Tabu Search,2,主要内容,提出Tabu-Clustering Tabu 具体Tabu-Clustering 实验结果,3,Tabu-Clustering算法,与已提出的各算法不同，该算法可以同时处理不同对象的分布模型。 紧凑球形分布 非紧凑球形分布 同时具备以上两种特征,4,算法的三个阶段,最小生成树聚类 聚类簇重组 禁忌搜索优化分阶段逐步进行优化，最终估算出合适的聚类簇数目,5,Tabu,Tabu算法的基本思想,6,Tabu,Tabu算法的基本要素,7,Tabu-C

2、lustering,阶段一 最小生成树聚类以4个对象为例 说明聚类过程，以 欧式距离作为相似 度的计算标准。,8,虚线表示当前对象集合，di表示当前对象集合与其第i个最相邻对象间距离。定义距离集合的平均值其中，n为对象个数，w为加权因子，用来调整对象间的相似度。,9,Tabu-Clustering,阶段二 聚类簇重组 两个距离定义 定义1：每个聚类簇中根据最小生成树方法生成的对象间距离的最大值所组成的距离集合，称为聚类簇内距离D1。 定义2：聚类簇间距离构成的距离矩阵，称为聚类簇间距离D2。,10,当考虑聚类簇内距离时，令图中4个对象构成聚类簇 ，则聚类簇内距离表示为 其中， 。,11,当考虑

3、聚类簇间距离，令图中4个对象分别代表不同的聚类簇，则聚类间距离表示为 其中， ，当p=q时， =0。,12,孤立对象Ok根据其与各聚类簇间的相似度进行合并，添加到簇 中，聚类簇 的对象分布和两聚类簇间的拓扑关系发生变化，聚类簇 的簇内部聚类明显较两聚类簇间距离大，即由于 ，表明两聚类簇存在 共性区，共性区的对象同属于 和 ，因此两聚类应重组建立新簇。,13,定义合并矩阵其中，a为合并因子。反复进行合并过程直至所有满足合并条件的聚类簇合并结束，合并矩阵的所有元素为0时停止，输出新的聚类簇集合,14,Tabu-Clustering,阶段三 禁忌搜索优化 经过第一二阶段得到的待优化解即已获得的聚类簇

4、集合，以字符串表示，解的长度即聚类簇的数目，解向量元素即聚类簇编号。 邻域构建 目标函数计算 禁忌搜索优化实现,15,邻域构建 邻域球用于提高算法的全局搜索能力 概率门限用于提高算法对局部区域的搜索效率,16,目标函数计算 聚类簇集合创建 目标函数F(S)计算其中 ， 为第m个聚类簇内对象的最大距离D1。， ， 表示聚类簇 中两聚类簇间最小距离D2。当F(S)最大时可获得最优解，此时的聚类簇数目即最佳聚类簇数目。,17,禁忌搜索的优化实现步骤1：初始化。产生初始解S0，令Sc= S0，Fc=F(S0), Fc表示其目标函数值， Sc表示当前解。设算法迭代次数M=100和当前迭代次数i=1。步骤

5、2：构建邻域。产生相邻解 ，j=1，N，N=150，并计算函数值F( ), 将函数值以升序排列 ，对应排序后相邻解表示为 。,18,步骤3：禁忌和期望准则运算。如果 不被禁止，或禁止但满足期望标准条件，即 ，则，转向步骤4，否则其中， 表示已排序个体集合中不在禁忌表中的当前最大函数值，转4，如果所有相邻解都被禁止，则转2。 步骤4：更新禁忌表。将解Sc加入禁忌表，设禁忌表计数器t=t+1，如果tT，将禁忌表中最初禁止解释放，T=30,如果 ，则 。 步骤5：终止条件判断。如果 ,则i=i+1，转2，否则输出最优解 。,19,实验Experiment,20,W为加权因子,21,a为合并因子,22

6、,23,综上所述， Tabu-Clustering算法分阶段优化计算结果，最终得到正确的聚类簇数目估算结果。此算法对紧凑型球形和非紧凑型球形分布的对象集合均具有较好的适应能力，能估算正确的聚类数目。,24,Example,由7种不同的绝缘材料构成一种绝缘体，如何排列才能使绝缘效果最好。 编码方式。1-27 任意两个材料交换位置就得到一个邻域解， =21 禁忌长度取3,禁忌元素为两种材料数对 绝缘效果为最终的目标函数，越大越好 期望标准。如果当前解的某次移动得到的解优于历史最优解，则不论该解是否在禁忌表中，都接受为下次迭代的最优解，迭代次数为5,25,初始状态： 随机给定初始解：2-5-7-3-

7、4-6-1 目标函数值为10，历史最优值也为10，禁忌表为空,当前解x： 2-5-7-3-4-6-1,历史最优值c(x*)=10,当前值c(x)=10,26,第1步： 当前邻域中目标函数值改善最大的移动是(4，5)，交换4、5，可增加目标值6。,27,第2步：,当前解x： 2-4-7-3-5-6-1,历史最优值c(x*)=16,当前值c(x)=16,28,第3步：,当前解x： 2-4-7-1-5-6-3,历史最优值c(x*)=18,当前值c(x)=18,29,第4步：,当前解x： 4-2-7-1-5-6-3,历史最优值c(x*)=18,当前值c(x)=14,30,第5步：(最大迭代次数5),当前解x： 5-2-7-1-4-6-3,历史最优值c(x*)=20,当前值c(x)=20,31,Tabu,Tabu算法流程图,