K-近邻研究应用.doc

研究基于分类的K-近邻算法设计方案 第一章 绪论 模式识别又常称作模式分类，从处理问题的性质和解决问题的方法等角度，模式识别分为有监督的分类（Supervised Classification）和无监督的分类(Unsupervised Classification)两种。二者的主要差别在于，各实验样本所属的类别是否预先已知。一般说来，有监督的分类往往需要提供大量已知类别的样本，但在实际问题中，这是存在一定困难的，因此研究无监督的分类就变得十分有必要了。 模式还可分成抽象的和具体的两种形式。前者如意识、思想、议论等,属于概念识别研究的范畴,是人工智能的另一研究分支。我们所指的模式识别主要是对语音波形、地震波、心电图、脑电图、图片、照片、文字、符号、生物传感器等对象的具体模式进行辨识和分类。 模式识别研究主要集中在两方面,一是研究生物体(包括人)是如何感知对象的，属于认识科学的范畴,二是在给定的任务下,如何用计算机实现模式识别的理论和方法。前者是生理学家、心理学家、生物学家和神经生理学家的研究内容,后者通过数学家、信息学专家和计算机科学工作者近几十年来的努力,已经取得了系统的研究成果。 模式识别或者通俗一点讲自动分类的基本方法有两大类，一类是将特征空间划分成决策域，这就要确定判别函数或确定分界面方程。而另一种方法则称为模板匹配[1]，即将待分类样本与标准模板进行比较，看跟哪个模板匹配度更好些，从而确定待测试样本的分类。近邻法则在原理上属于模板匹配。 分类的方法包括统计的方法、近邻法、神经网络分类法、无监督聚类法和新出现的基于统计学习理论的支持向量机法，K-近邻分类法是近邻分类法的扩展。 它将训练样本集中的每个样本都作为模板，用测试样本与每个模板做比较，看与哪个模板最相似(即为近邻)就按最近似的模板的类别作为自己的类别。譬如A类有10个训练样本，因此有10个模板，B类有8个训练样本，就有8个模板。任何一个待测试样本在分类时与这18个模板都算一算相似度如最相似的那个近邻是B类中的一个，就确定待测试样本为B类，否则为A类。因此原理上说近邻法是最简单的。数据挖掘是八十年代，投资AI研究项目失败后，AI转入实际应用时提出的。它是一个新兴的，面向商业应用的AI研究。在模板数量很大时其错误率指标还是相当不错的。就是说近邻法有必要近十几年来人们利用信息技术生产和搜集数据的能力大幅度提高无数个数据库被用于商业管理、政府办公、科学研究和工程开发等这一势头仍将持续发展下去。于是一个新的挑战被提了出来:在这被称之为信息爆炸的时代信息过量几乎成为人人需要面对的问题。如何才能不被信息的汪洋大海所淹没从中及时发现有用的知识提高信息利用率呢?要想使数据真正成为一个公司的资源只有充分利用它为公司自身的业务决策和战略发展服务才行否则大量的数据可能成为包袱甚至成为垃圾。因此面对人们被数据淹没人们却饥饿于知识的挑战数据挖掘和知识发现(DMKD)技术应运而生并得以蓬勃发展越来越显示出其强大的生命力。K-近邻法的研究主要在分为两部分： 一.对其算法的的改进研究 辽宁工程技术大学的张宇[3]提出了一种出了一种利用随机属性子集组合k-近邻分类器的算法通过随机的属性子集组合多个k 近邻分类器, 利用简单的投票, 对多个k-近邻分类器的输出进行组合, 这样可有效地改进k-近邻分类器的精度。 广东石油化工学院计算机与电子信息学院的周靖，刘晋胜[4]采用特征相关性差异优化距离的改进k近邻算法。可以有效地解决 近邻算法训练样本规模及分类精度间的矛盾，提出了一种采用特征相关性差异优化距离的改进算法(FCDKNN)。 该算法将特征熵值与其分布概率的乘积作为特征相关性的概念， 在此基础上定义围绕特征相关性差异的样本距离测度，明确特征在类别上的重要性及相关性，在小样本情况下提取针对分类的大量有效信息，以增强算法的全局优化能力。对比仿真实验结果表明， 该算法在保持效率的情况下分类精度得到了极大地提高。 中国地质大学计算机科学系的陆微微, 刘晶[6]提出了一种一种提高 K- 近邻算法效率的新算法。此方法是基 于凹凸轮廓结构特 征估计轮廓的宽度与高度比值, 进而快速、正确地对粘连字符进行切分,使把部分原本发生在分类阶段的计算移到训练阶段来完成。该算法可以使knn算法的效率提高80%。此外该方法还可用于 KNN 的所有变体 中, 具有 良好的推广能力 。 二.对K-近邻法的具体应用。 安徽大学计算机科学与技术学院的刘锋，白凡[5]应用了一种改进的K近邻算法进行网页分类。其针对传统K近邻算法对于噪声词敏感的缺点，结合网页文章构成的特殊性，对文档的特征向量表示模型进行了改进，从而也改进了K近邻算法中特证词的权值以及文档相似度的计算公式，实验结果表明改进后的K近邻算法提高了分类的精度。但此算法增加了网