《进化算法自适应分类.ppt》由会员分享，可在线阅读，更多相关《进化算法自适应分类.ppt（24页珍藏版）》请在三一文库上搜索。
1、进化算法自适应分类,报告人：刘丛,第一部分,K-means基本概念,第二部分,用进化算法解决k-means,第三部分,分类的有效性函数,第四部分,可变长进化算法的编码方式,第五部分,实验和总结,K-means基本概念(1),K-means算法： （1）适当选择k个类的初始中心； （2）在第k次迭代中，对任意一个样本，求其到k个中心的距离，将该样本归到距离最短的中心所在的类； （3）利用均值等方法更新该类的中心值； （4）对于所有的k个聚类中心，如果利用（2）-（3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。,K-means基本概念(2),K-means的优点： 能处理大型数据集，结
2、果类相当紧凑，并且类和类之间明显分离 K-means的缺点： （1）该算法必须事先给定类数和初始中点，类数和中点的初始值设定往往会对聚类的算法影响较大。 （2）通常会在获得一个局部最优值时停止 （3）并且只适合对数值型数据聚类 （4）只适用于聚类结果为凸形的数据集，K-means方法不适合发现非凸面形状的类簇，或者大小差别很大的类。 （5）对“噪音”和孤立点数据敏感，少量的该类数据对质点的计算会产生极大的影响。,用进化算法解决k-means（1）,进化算法是以达尔文的进化论思想为基础，通过模拟生物进化过程与机制的求解问题的自组织、自适应的人工智能技术。 进化算法步骤： （1）初始化种群 （2）
3、（a）选择（b）交叉（c）变异 （3）计算适应度函数及代数，如果满足适应度函数或满足最大代数则终止，否则转向（2）,用进化算法解决k-means（2）,进化算法特点： （1）遗传算法从问题解的串集开始搜索，而不是从单个解开始，避免了陷入局部最优。 （2）同时处理群体中的多个个体，即对搜索空间中的多个解进行评估. （3）对搜索空间没有任何特殊要求（如连通性、凸性等），只利用适应性信息，不需要导数等其它辅助信息，适应范围更广。 （4）遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传
4、算法有很高的容错能力 （5）具有自组织、自适应和自学习性 我们可以用遗传算法的第（1）个特点，解决k-means算法中对初始值要求太高的缺陷。,用进化算法解决k-means（3）,进化算法的分类方法 编码： 进化算法处理分类问题主要有三种编码方式 （a）二进制编码 1000101000 （b）整数编码 1111223333 （c）实际编码 1.5,1.5,5.0,5.5,10.5,1.5 适应度函数：,分类的有效性函数（1）,指标越大表示聚类效果越好，但是随着数据点个数的增加，计算量增加过快，对噪声比较敏感。,分子表示类内的紧凑度，值越小，说明类内相似性越大越紧凑，分母表示类间的分离度，值越大
5、，说明不相似性越大，本指标，值越小，分类的结果越好。 可以反映数据集的结构特征，缺点是，类数越大，指标趋向于0，失去了判定能力。也不能处理重叠数据集合,分类的有效性函数（2）,该模型只使用隶属度参数，缺少直接的形状关系，当类别很少的时候，得出的结果很好,分类的有效性函数（3）,分类的有效性函数（4）,分类的有效性函数（5）,分类的有效性函数（6）,我们的有效性函数：,Comp(k)表示聚类的紧密度，k值越大，结果越小， Sep（k）表示类间距的分离度。 该模型可以运用进化算法进行最优解搜寻 搜寻空间为kkmin,kmax, kmax=sqrt（n）,可变长进化算法的编码方式(1),传统的变长编码方式： （1）树结构编码 （2）mga变长编码 （3）基于相似度的可变长编码 （4）agent编码,可变长进化算法的编码方式(3),编码方式,li0.5,中心有效； li0.5,中心无效；,可变长进化算法的编码方式(3),适应度函数,实验和总结（1）,实验和总结（2）,实验与总结（3）,实验与总结（4）,实验和总结（5）,实验和总结（6）,结果分析 （1）我们使用欧氏距离作为距离公式，所以对数据集的几何形状具有很大的敏感性 （2）由于该模型需要考虑类间距，所以我们设置的案例类别数至少是两类,谢谢大家,