简化的粒子群优化快速KNN分类算法
- 格式：pdf
- 大小：257.16 KB
- 文档页数：3
Ｃｏｍｐｕｔｅｒ Ｅｎ￣ｎｅｅｎｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 ２００８，４４（３２） ５７ 简化的粒子群优化快速ＫＮＮ分类算法 李欢１，焦建民ｚ ＬＩ Ｈｕａｎ ，ＪＩＡ０ Ｊｉａｎ—ｍｉｎ
１．宁波大红鹰职业技术学院软件学院，浙江宁波３１５１７５ ２．南京航空航天大学民航学院，南京２１００１６ １．Ｓｃｈｏｏｌ ｏｆ Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｎｉｎｇｂｏ Ｄａｈｏｎｇｙｉｎｇ Ｖｏｃａｔｉｏｎａｌ Ｔｅｃｈｎｏｌｏｇｙ Ｃｏｌｌｅｇｅ，Ｎｉｎｇｂｏ，Ｚｈｅｊｉａｎｇ ３１５１７５，Ｃｈｉｎａ ２．Ｃｉｖｉｌ Ａｖｉａｔｉｏｎ Ｃｏｌｌｅｇｅ。Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ａｅｒｏｎａｕｔｉｃｓ＆Ａｓｔｒｏｎａｕｔｉｃｓ，Ｎａｎｊｉｎｇ ２１００１６，Ｃｈｉｎａ Ｅ－ｍａｉｌ：ｊｉａｏａｏ１９９６＠１６３．ｃｏｎｌ
ＬＩ Ｈｕａｎ，ＪＩＡＯ Ｊｉａｎ—ｍｉｎ．Ｉｍｐｒｏｖｅｄ ｓｉｍｐｌｉｆｉｅｄ ＰＳＯ ＫＮＮ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｌｇｏｒｉｔｈｍ．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， ２００８．４４（３２）：５７—５９．
Ａｂｓｔｒａｃｔ：Ａｎ ｅｆｆｉｃｉｅｎｔ ａｌｇｏｒｉｔｈｍ ＳＰＳＯＫＮＮ ｉｓ ｐｒｏｐｏｓｅｄ ｔｏ ｒｅｄｕｃｅ ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ＫＮＮ ｔｅｘｔ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｌｇｏ— ｒｉｔｈｍ，ｉｔ ｉｓ ｂａｓｅｄ ｏｎ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ｗｈｉｃｈ ｓｅａｒｃｈｅｓ ｒａｎｄｏｍｌｙ ｗｉｔｈｉｎ ｔｒａｉｎｉｎｇ ｄｏｃｕｍｅｎｔ ｓｅｔ．Ｄｕｒｉｎｇ ｔｈｅ ｐｒｏｃｅｄｕｒｅ ｆｏｒ ｓｅａｒｃｈｉｎｇ ｋ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒｓ ｏｆ ｔｅｓｔｅｄ ｓａｍｐｌｅ，ｔｈｏｓｅ ｄｏｃｕｍｅｎｔ ｖｅｃｔｏｒｓ ｔｈａｔ ａｒｅ ｉｍｐｏｓｓｉｂｌｅ ｔｏ ｂｅ ｔｈｅ ｋ ｃｌｏｓｅｓｔ ｖｅｃｔｏｒｓ ａｒｅ ｋｉｃｋｅｄ ｏｕｔ ｑｕｉｃｋｌｙ．Ａｎｄ ｒｅｍｏｖｉｎｇ ＰＳＯ ｅｖｏｌｕｔｉｏｎａｒｙ ｐｒｏｃｅｓｓ ｏｆ ｐａｒｔｉｃｌｅ ｖｅｌｏｃｉｔｙ ｉｍｐａｃｔ，ｔｈｕｓ ｗｅ ｃａｎ ｍｏｒｅ ｒａｐｉｄｌｙ ｆｉｎｄ ｔｈｅ ｋ ｃｌｏｓｅｓｔ ｖｅｃ— ｔｏｒｓ ｏｆ ｔｅｓｔ ｓａｍｐｌｅｓ．Ｂｙ ｖｅｒｉｆｙｉｎｇ ｔｈｅ ｖａｌｉｄｉｔｙ ｏｆ ａｌｇｏｒｉｔｈｍ，ｆｉｎｄｉｎｇ ｔｈｅ ｓａｍｅ ｋ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒｓ，ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｃｃｕｒａｃｙ ｏｆ ＳＰ— ＳＯＫＮＮ ａｌｇｏｒｉｔｈｍ ｉｓ ｈｉｇｈｅｒ ｔｈａｎ ＫＮＮ ａｌｇｏｒｉｔｈｍ． Ｋｅｙ ｗｏｒｄｓ：Ｋ Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒ（ＫＮＮ）ｃｌａｓｓｉｆｉｅｒ；Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ（ＰＳＯ）；ｓｉｍｉｌａｒｉｔｙ
摘要：提出了一种有效的ｋ近邻分类文本分类算法，即ＳＰＳＯＫＮＮ算法，该算法利用粒子群优化方法的随机搜索能力在训练集中 随机搜索．在搜索ｋ近邻的过程中，粒子群跳跃式移动，掠过大量不可能成为ｋ近邻的文档向量，并且去除了粒子群进化过程中粒 子速度的影响，从而可以更快速地找到测试样本的ｋ个近邻．通过验证算法的有效性表明，在查找ｋ近邻相同时，ＳＰＯＳＫＮＮ算法的 分类精度高于基本ＫＮＮ算法。 关键词：Ｋ近邻分类器；粒子群优化算法；相似度 、 ＤＯＩ：１０．３７７８￣．ｉｓｓｎ．１００２—８３３１．２００８．３２．０１７ 文章编号：１００２—８３３１（２００８）３２—００５７—０３ 文献标识码：Ａ 中图分类号：ＴＰ１８
１引言 随着文本信息量的快速增长，文本分类已成为信息检索、 知识挖掘和管理等领域的关键技术。文本分类的精确程度取决 于特征提取的科学性和分类算法的科学性。现有的文本分类方 法主要有支持向量机（ＳＶＭ）、Ｋ近邻（ＫＮＮ）、决策树、线性最小 二乘法估计（ＬＬＳＰ）和贝叶斯分类算法（Ｂａｙｅｓ）ｔ－］等，相关研究证 明，ＫＮＮ算法是ＶＳＭ（向量空间模型）下最好的分类算法之— 】。 ＫＮＮ方法基于类比学习，是一种非参数的分类技术，在基 于统计的模式识别中非常有效，对于未知和非正态分布可以取 得较高的分类准确率，具有鲁棒性、概念清晰等诸多优点。其基 本原理为：计算未知类别文本向量与样本集中每个文本向量的 夹角余弦值，以此判断文本相似度，在样本集中找出 个最相 似的文本向量，分类结果为 个相似样本中相似样本最多的 一类。 但在文本分类中，ＫＮＮ方法的缺陷也突出地暴露出来，主 要有：首先ＫＮＮ算法是懒散的分类算法，对于分类所需的计算 都推迟到分类时才进行，在其分类器中存储有大量的样本向
基金项日：浙江省教育厅２００６年度高校科研计Ｊ￣ｌＪ（Ｎｏ．２００６０３４７）。 作者简介：李欢（１９７０一），女，硕士，副教授，研究方向：软计算理论及其应用。 收稿日期：２００７—１２—１７ 修回日期：２００８—０３—２０
量，在未知类别样本需要分类时，再计算所有存储样本和未知 类别样本的距离，对于高维文本向量或样本集规模较大的情况 其时间和空间复杂度较高（时间代价为ｏ（ｎ＊ｍ），ｎ为ＶＳＭ空间 特征维数，ｍ为样本集大小）；其次ＫＮＮ方法是建立在ＶＳＭ模 型上的，其样本距离的测度使用欧式距离，各维权值相同，也就 是认定各维对于分类的贡献是相同的，显然这是不符合实际情 况的，同等的权重使得特征向量之间距离或者夹角余弦的计算 不够准确，进而影响分类精度；最后，对于文本的高维向量，对 于分类起主要作用的维数远远低于文本本身的维数，相当多维 对于文本分类意义不大甚至是噪声数据。 对于上述缺点，文献【２］提出运用ＢＰ前向神经网络来计算 各维权值。此方法虽然利用了神经网络的分类和泛化能力，但 存在以下缺点： （１）ＢＰ神经网络学习算法容易陷入局部最小点，且在高维 文本及其高数据量的情况下，学习算法计算开销很大，学习速 度缓慢，另外，只适合于较为平稳的环境下，因其新知识记忆会 使老知识的记 丧失； Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 （２）在其测算属性权值的方法中，需要逐个删除输入节点， 每次删除均可能需要重新训练ＢＰ神经网络，对于高维或者大 量的样本，计算量过大。 本文针对以上ＫＮＮ方法的不足，提出—种改进ＫＮＮ方法， 以提高其分类速度。 ２ ＫＮＮ文本分类算法 ２．１ ＫＮＮ的概念 ＫＮＮ（Ｋ—Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒ），代表ｋ个最近邻分类法，通过 Ｋ个最与之相近的历史记录的组合来辨别新的记录。ＫＮＮ是 一个众所周知的统计方法，在过去的４Ｏ年里在模式识别中集 中地被研究。ＫＮＮ在早期的研究策略中已被应用于文本分类， 是基准Ｒｅｕｔｅｒｓ主体的高操作性的方法之一。其他方法，如 ＬＬＳＦ、决策树和神经网络等。 ２．２ ＫＮＮ算法 该算法的基本思路是：在给定新文本后，考虑在训练文本 集中与该新文本距离最近（最相似）的 篇文本，根据这 篇 文本所属的类别判定新文本所属的类别，具体的算法步骤如下： （１）根据特征项集合重新描述训练文本向量＿３１。‘ （２）在新文本到达后，根据特征词分词新文本，确定新文本 的向量表示。 （３）在训练文本集中选出与新文本最相似的 个文本，计 算公式为： ｓｉｍ（ｄ ， ）＝ 埘 ∑ 其中，Ｋ值的确定目前还没有很好的方法，一般采用先定一个 初始值，然后根据实验测试的结果调整 值。 （４）在新文本的 个邻居中，依次计算每类的权重，计算 公式为： ｐ（ｘ， ）＝∑ ｉｍ（ｘ， ） （ ， ） （２） 其中， 为新文本的特征向量，ｓｉｍ（ｘ，ｄｉ）为相似度计算公式，与 上一步骤的计算公式相同，而ｙ（ｄ ，ｃｊ）为类别属性函数，即如 果 属于类Ｃｊ，那么函数值为１，否则为０。 （５）比较类的权重，将文本分到权重最大的那个类别中。 ３粒子群优化算法 对ｋ近邻方法完成分类最重要的就是要找到ｋ个近邻，穷 尽搜索整个训练集，即计算测试样本与所有训练样本间的距 离。洲练样本数较多或者表示样本的特征向量维数较高时，计 算复杂性就越高。Ｈｕａｎｇ和ｗｅｎ 黾出了一种基于小波域部分 距离搜索的ｋ近邻搜索算法，本文基于粒子群算法的智能随机 搜索能力加快ＫＮＮ寻找ｋ个近邻的速度。ＰＳＯ初始化为一群 随机粒子（随机解）【５ｊ，然后粒子们就追随当前的最优粒子在解 空间中搜索，即通过迭代找到最优解。在每一次迭代中，粒子通 过跟踪２个最优解来更新自己。—个就是粒子本身所找到的最 优解，即个体极值ｐｂｅｓｔ；另一个是整个种群目前找到的最优 解，即全局最优解 ｅｓｔ。设搜索空问为Ｄ维，总粒子数为ｎ，第 ｉ个粒子位置表示为向量 ＝（ …， ）；第ｉ个粒子的历 史最优位置为Ｐｉ＝（ｐ Ｐ …，Ｐ ），其中 为所有 （ ＝１，…， ｎ）中的最优；第ｉ个粒子的位置变化率为向量Ｖ ：（ …， Ｕ／Ｄ ｏ每个粒子的位置按式（１）和式（２）进行变化：
ｎ＋ｌ ｎ＋ｃ１：一一ｎＸｒ ｘＬｐｚ Ｘｌｄ）Ｘｒ ２ｔｐ￣ ） （３） ｌｄ＝ ＋ｃ１ ｌ — Ｊ＋ｃ２ Ｌｊ
？， （４） ＝ ＋ 斗 其中：ｎ是循环次数，ｒ．和ｒ２是均匀分布在（０，１）区间的随机数， Ｃ１和ｃ，是学习因子，一般取值为Ｏ．５，粒子在搜索空间内不断跟 踪局部优化和全局优化值进行搜索，直到达到规定的迭代次数 或满足误差阈值。 ＰＯＳ算法的流程如下： 步骤１初始化所有微粒．在允许范围内随机设置微粒的初 始位置和速度，并将各微粒的ｐｂｅｓｔ设为初始位置，取ｇｂｅｓｔ为 ｐｂｅｓｔ中的最优值。 步骤２评价每个微粒的适应值。 步骤３对每个微粒，将其适应值与历史最优位置ｐｂｅｓｔ进 行比较，如果优于ｐｂｅｓｔ，则将其作为当前最优位置ｐｂｅｓｔ。 步骤４对每个微粒，将当前最优位置ｐｂｅｓｔ与群体历史最 优位置ｇｂｅｓｔ进行比较，如果优于ｇｂｅｓｔ，则将其作为群体最优 位置ｇｂｅｓｔ。 步骤５根据微粒群速度和位置更新方程来调整微粒的速
度和位置。 步骤６检查终止条件（通常为达到最大迭代次数或者足 够好的适应值）或者最优解停滞不再变化．若上述条件满足，终 止迭代；否则返回第２步。 在文献［６］中证明，ＰＯＳ中粒子速度不是必需的，从ＢＰＳＯ 模型角度来看，粒子位置 ，代表当前问题的解，优化的最终结
果是使 无限逼近最优解 ，因此，只需要考虑 的直接变 化。粒子速度 ．代表粒子移动的快慢程度，粒子移动速度的大 小并不代表粒子能够有效趋近最优解位置，反而可能造成粒子 偏离正确的进化方向，出现粒子“发散”现象，从而有可能造成 后期收敛缓慢、收敛精度低等缺点。因此，在本文应用简化的粒 子群Ｋ近邻分类算法，去除粒子速度的影响，以增加搜索的精 确度。
