《基于粒子群优化的快速KNN分类算法.ppt》由会员分享，可在线阅读，更多相关《基于粒子群优化的快速KNN分类算法.ppt（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、基于粒子群优化的基于粒子群优化的快速快速KNN分类算法分类算法张景祥 济南大学计算机工程学院 计算机专业英语教程科技英语,专业英语,IT英语特点：词汇、术语、专用语 北京石油化工学院北京石油化工学院张国英张国英 沙芸沙芸 江慧娜江慧娜 主要内容n1 论文背景与意义论文背景与意义n2 近邻分类文本分类算法近邻分类文本分类算法 n3 粒子群优化算法粒子群优化算法 n4 基于粒子群算法的基于粒子群算法的K近邻分类算法近邻分类算法 n5 实验结果实验结果1 论文背景与意义论文背景与意义n基于机器学习的文本分类过程，与智能优基于机器学习的文本分类过程，与智能优化技术结合，对于庞大的文档集合分类，化技术结
2、合，对于庞大的文档集合分类，利于提高分类的速度和精度。利于提高分类的速度和精度。n智能优化应该作为文本分类的重要一环。智能优化应该作为文本分类的重要一环。2 近邻分类文本分类算法近邻分类文本分类算法 n 计算测试文本X的特征项权重，文档特征向量w=w1,w2,wM;n 对训练集中的任一文本Xj，生成文档向量wj=wj,1,wj,2,wj,M；n 计算训练文本集样本与测试文本的相似度，选出与测试文本最相似的 k个文本；n 在新文本的 k个近邻中，依次计算每类的权重n n n 比较类的权重，将文本分到权重最大的类CI中。3 粒子群优化算法粒子群优化算法PSOn粒子群优化算法是群体智能优化方法n使用
3、并行和结构化策略，随机但有指导性地加强高维空间的搜索能力。n所搜索的目标空间点有最小的适应度函数值n具有全局搜索和快速收敛的特点 nPSO种群中任一粒子i的移动速度 nPSO种群中任一粒子i的位置3 粒子群优化算法粒子群优化算法4 基于基于PSO的的K近邻分类算法近邻分类算法n文档分类的训练样本集规模很大nKNN方法穷尽搜索整个样本空间的代价很大n粒子群算法群体的随机搜索能力，群体利用与其k个随机样本距离最近的粒子信息指导种群粒子的移动，在很小的搜索空间内快速获得k个近邻样本。n输入：文档集合文档总数N，近邻个数k，粒子群种群个数Q，误差阈值。n(1)生成测试文档的文档特征向量w；n(2)用随
4、机函数在区间1,N内为Q个粒子各选择出k个整数（对应文档集合的文档序号）作为每个粒子的初始k个近邻位置，粒子群的初始速度为0；n(3)计算w的k个最优近邻有序集合作为粒子群的全局最优位置，各粒子的位置先作为其局部最优位置。n(4)置n=n+1，计算每个粒子的移动速度(即其k个近邻的序号偏移量)n n(5)从种群移动历史中选择w的k个最优近邻有序集合作为全局指导，nIf ，则 ；从粒子j的移动历史中 选择其k个最优近邻有序集合作为局部指导。(6)根据计算有序集合 和 与测试文档X的相似度 和 ，如果 算法停止，输出集合 作为测试文档X的k个近邻。5 实验结果实验结果nKNN算法的参数包括k近邻的
5、选择，本文分别对k25和k35进行了实验,特征维数分别为50和100。表1特征向量维数为100时的结果算法 k=35 k=25 误分率 时间(s)误分率 时间(s)KNN 75 157 75 140 PSOKNN 75 48 75 43 算法 k=35 k=25 误分率 时间(s)误分率 时间(s)KNN 70.2 107 70.2 101 PSOKNN 70.2 31 70.2 29表2特征向量维数为50时的结果n当特征向量的维数是100时，相对算法KNN的分类时间而言，本文算法PSOKNN平均减少了69%的分类时间；n当特征向量的维数为50时，PSOKNN算法比KNN的分类时间平均减少72%。PSOKNN算法在保持分类性能不变的情况下，可以大大减少分类时间