基于变精度粗糙集的KNN分类改进算法_余鹰

格式：pdf
大小：375.78 KB
文档页数：7

下载文档原格式

基于邻域粗糙集与鱼群智能的基因选择方法

基于邻域粗糙集与鱼群智能的基因选择方法陈玉明;朱清新;曾志强;孙金华;唐朝辉【摘要】Facing the gene expression data with high dimension, small samples and uncertainty, a gene selection method based on neighborhood rough sets and fish swarm intelligence is proposed by fusing a fuzzy tolerance granulation technology and a fish swarm intelligence algorithm with global optimization ability. Firstly, the neighborhood rough sets are used to granulate the gene data and form some neighborhood particles. Secondly, the neighborhood classification accuracy is presented as an uncertainty evaluation function that aims to judge these neighborhood particles and distinguish key genes. Furthermore, a gene selection algorithm based on artificial fish swarm intelligence is designed. Finally, some gene selection experiments are carried out on two tumor gene data sets. The classification experiments of a small number of selected key genes are conducted by using SVM classifier. The experimental results show that the genes selected by our proposed method have a low redundancy and a better classification performance.%针对高维、小样本及不确定性的基因表达数据,融合模糊可容忍性的邻域粒化技术与具有全局寻优能力的鱼群智能算法,提出基于邻域粗糙集与鱼群智能的基因选择方法.首先,采用邻域粗糙集对基因数据进行邻域粒化,形成邻域粒子;其次,提出基于邻域分类精度的不确定性评价函数,用以评价邻域粒子的不确定性,分辨关键性基因;进一步融合鱼群智能方法,设计一种基因选择算法,选取分类性强的少量关键基因;最后,在两个癌症基因数据集中进行基因选择,采用SVM分类器对获取的关键基因组进行分类实验.实验结果表明,采用该方法获取的基因组具有较低的冗余度及较好的分类性能.【期刊名称】《电子科技大学学报》【年(卷),期】2018(047)001【总页数】6页(P99-104)【关键词】鱼群算法;基因选择;粒计算;邻域粗糙集;粗糙集【作者】陈玉明;朱清新;曾志强;孙金华;唐朝辉【作者单位】厦门理工学院计算机与信息工程学院福建厦门 361024;电子科技大学计算机科学与工程学院成都 611731;电子科技大学计算机科学与工程学院成都611731;厦门理工学院计算机与信息工程学院福建厦门 361024;厦门理工学院计算机与信息工程学院福建厦门 361024;厦门理工学院计算机与信息工程学院福建厦门 361024;电子科技大学计算机科学与工程学院成都 611731【正文语种】中文【中图分类】TP181微阵列技术的快速发展积累了大量的基因表达数据。

基于粗糙集与改进KNN算法的文本分类方法的研究

ｆｒｔｘｓｗｔｏｉｎｉｎｌｅｔｒ．Ｈｏｅｅ．ｗｅｔｅｌｉｒｅｎｍｂｒｏｉｈｄｍｅｓｏａｘｓｈｒｄｔｎｌｏｔｉｌｗｄｍｅｓｏａｃｏｓｅｈｖｗｖｒｈｎｉｄａｓｗｔｌｇｕｅｓｆｈｇ — ｉｎｉｎｌｅｔ．ｔｅｔａｉｏａｈａｔｉＫＮＮａｇｒｔｍ，ｄｅｔｈｅｄｔｒｃｓｏｓｄｒｂｅｔｅｔａｎｎａｌｓｅｕｔｉｎｒａｅｉｌｒｔａｃｌｔｎａｄｒｄｃｄｌｏｈｉｕｔｅｎｅＯｐｏｅｓｃｎｉｅａｌｈｒｉｉｇｓｍｐｅ，ｒｓｌｎｉｃｅｓｄｓｍｉｉｙｃｕａｉｎｅｕｅｏａｌｏ
问题，文首先利用粗糙集对高维文本信息进行属性约简，除冗余属性，本删而后用改进的基于簇的ＫＮ算法进行文本分Ｎ类。通过仿真实验，明该方法能够提高文本的分类精度和；率。证位确
ｃａｓｃｔｎｅｉｉｎｙｏｓｌｅｅｓｉｇｐｏｌｍｓｈｓｐｐｒｕｅｈｏｇｅｔｏＯｒｄｃｅａｔｂｔｓｏｅｉｏａｌｌｓｉａｉｆｃｅｃ．Ｔｏｖｎｕｎｒｂｅ，ｔｉａｅｓｓｔｅｒｕｈｓｔｉｆｏｍｅｈｄｔｅｕｅｔｔｕｅｆｄｃｓｎｔｂｅｈｉｒｉａｄｒｍｏｅｒｄｎａｔａｔｂｔｓｎｈｎｔｅｉｒｖｄｃｕｔｒｂｓｄＫＮＮａｇｒｈｉｓｄｔｌｓｉｅｔ．Ｓｍｔａｉｎｒｓｌｎｅｖｅｕｄｎｔｕｅ．ａｄｔｅｈｍｐｏｅｌｓ — ａｅｉｒｅｌｏｉｍＳｕｅｃａｓｙｔｘｓｉｄｔｅｕｔｔＯｆｏｓｓｏｈｔｔｅｍｅｈｄＣｍｐｏｅｔｅｐｅｉｉｎａｄａｃｒｃａｅｏｘｃａｓｆａｉｎｈｗｔａｈｔｏａｉｒｖｈｒｃｓｏｎｃｕａｙｒｔｆｔｔｌｓｉｃｔ．ｎｅｉｏＫｅｒｓｒｕｈｓｔｍｐｏｅｙｗｏｄ：ｏｇｅ；ｉｒｖｄＫＮＮａｇｒｈ；ｔｘｌｓｉｃｔｎｍｅｈｄｌｏｉｍｅｔｃａｓｆａｉｔｏｔｉｏ

一种改进的KNN文本分类算法

性最小二乘方估计（ＬＦ和贝叶斯算法（Ｂ等。ＫＬＳ）Ｎ）ＮＮ分类方
法具有简单、有效、非参数的特点，向量空间模型中最好的分是
在分类阶段所执行的操作与训练阶段类似，先对待分类的
文本进行预处理、特征选择和特征项权重计算，然后将得到的
信息安全与技术・０１７・５．２１．２０
ＴｃｎｌｇｎｔｄｅｈｏｏｙａｄＳｕｙ・技术探讨
足之处．出了一种改进的Ｋ提ＮＮ文本分类算法一类内均值ＫＮ算法。Ｎ通过实验表明，于传统的ＫＮ算法，算法提高了文相对Ｎ该本分类系统的稳定性和分类性能，有一定的应用价值。具
【关键词】文本分类；分类流程；ＮＫ值ＫＮ；
其中的高维特征向量对分类效果有诸多不利影响，因此需要通
过特征选择来降低特征向量的维数。用的特征选择方法有基常
于文档频率的特征提取法、信息增益法、统计量和互信息法等。然后计算特征项的频度，得出所有特征项的权重（特征项的权重表明了其区分文本类别能力的强弱）。最后用文本向量集来训练选定的分类器，得到分类模型。
【ｂｔｃＴｉｐｐｒｅｃｂｓｅｔａｓｃｔｎｒｅｓｎｌｅｃｎｌｉｈｈａｅｎＫＮａｏｉｍＯｅｒｉｃｌｎｔｔＡｓａｔ】ｈｅｄｓｒｅｘｃｓｉａｏｏｓｄｅｔｔｈｏｇｓｉｓｄＮｇｒ．ｖｒｅｎｅｎｖｕａｄｅｒｓａｉｔｆｉｐｃａｒａｄｅｏｅｗｃｂｌｉｏｌｔｈ－ｌｏＫａｅｘａ

KNN算法的改进方法

KNN算法的改进方法K近邻算法是机器学习中常用的一种分类算法。

KNN算法具有简单易懂、易于实现、无需训练等优点，但在处理大量数据时，算法的计算量会变得非常大，同时又会存在维度灾难和样本不平衡等问题。

为了解决这些问题，研究人员提出了许多改进的KNN 算法。

改进方法一：KD-Tree算法K近邻算法基于距离度量来进行分类，传统的KNN算法需要计算每个测试样本与所有已知样本之间的距离，随着样本数量的增加，计算的时间复杂度会呈指数级增长，这样就会导致算法无法简单高效地应用于大规模数据的处理中。

针对这种问题，研究人员提出了KD-Tree算法。

KD-Tree是一种树形数据结构，可以有效地减少样本到测试样本的距离计算量，从而提升算法的分类效率。

具体来说，KD-Tree 算法通过递归的方式将已知样本空间划分成多个区域，每个区域的划分方式采用平行于坐标轴的超平面。

当一个测试样本要被分类时，算法首先确定它在KD-Tree上所处的叶子节点，然后只需要计算测试样本与该叶子节点内的已知样本之间的距离，从而大大减少了计算量。

改进方法二：基于核函数的KNN算法传统的KNN算法只考虑了样本之间的欧几里得距离或曼哈顿距离等常见距离度量，忽略了样本之间的非线性关系。

因此，该算法在处理非线性分类问题时可能会出现一定的局限性。

针对这一问题，研究人员提出了基于核函数的KNN算法。

核函数是一种数学技巧，用于将非线性映射变成线性映射。

基于核函数的KNN算法通过对样本进行非线性映射，将样本从低维空间映射到高维空间，从而使得在高维空间中欧式距离近的样本在低维空间中也保持足够的相似性。

同时，算法还采用加权投票的方式以获得更好的分类结果。

改进方法三：SMOTE算法传统的KNN算法针对样本不平衡问题，在数据预处理阶段通常会采用欠采样或过采样等方法来平衡样本。

欠采样方法常常会丢失重要的信息，而过采样方法则可能会引入噪声或重复样本数据。

为了解决这一问题，研究人员提出了SMOTE算法。

一种基于粗糙集的改进KNN文本分类算法_苟和平

4927
Ck ） = δ（ d j ，
{
1， dj ∈ Ck 0， dj Ck 。定义 3
RX = ｛ x ∈ U | ［ x］ R ∩ X ≠ ｝。它们分别为 X 的 R 下近似集和 R 上近似集。 R），给定一个知识库 K = （ U，对于每个子集 X U 和一个等价关系 R ∈ ind（ K ），全集 U 可以划分为 3 个不相交的区域，即正域（ pos R ）、负域（ neg R ）和边界（ bnd R ）。 pos R = RX ； neg R = U － RX ； bnd R = RX － RX 。其中，正域（ pos R ）表示那些根据知识 R 判断肯定属于 X 的 U 中元素组成的集合；负域（ neg R ）是那些根据知识 R 判断肯定不属于 X 的 U 中元素组成的集合；边界（ bnd R ）是那些根据知识 R 既不能判断 X 的 U 中元素肯定属于 X 又不能判断肯定属于 U组成的集合。
表2
查准率 KNN RS-KNN 0. 688 9 0. 836 4 0. 606 1 0. 695 7 0. 862 1 0. 857 1 0. 685 7 0. 573 5 0. 608 7 0. 882 4
（ 6 ）比较各类的权重，将待分类文本 t i 归入权重最大的类别。 KNN 作为一种有监督机器学习的非参数方法，分类器在文本分类方面简单高效。但该算法的主要缺点是在分类时需要计算待分类文本 d i 与所有训练文本之间的距离，时间复杂度与训练文本数量、维数成正比，与大量的训练文本进行相似度的计算，计算开销大。因此，在大样本集或者是高维样本集下，分类效率会降低

粗糙集理论对于特征选择算法的改进与优化

粗糙集理论对于特征选择算法的改进与优化特征选择是数据挖掘和机器学习中的一个重要任务，它的目标是从原始数据集中选择出最具有代表性和区分性的特征，以便用于构建高效的分类器或回归模型。

在特征选择过程中，我们常常面临着特征维度高、样本数量有限、特征之间存在冗余等问题。

为了解决这些问题，粗糙集理论被引入到特征选择算法中，并取得了一定的改进和优化效果。

粗糙集理论是由Pawlak于1982年提出的一种数学工具，它主要用于处理不确定性和不完备性的问题。

在特征选择中，粗糙集理论通过将数据集划分为等价类来处理特征之间的关系，从而实现特征选择的目标。

具体而言，粗糙集理论通过计算下近似和上近似来评估特征的重要性，从而确定哪些特征对于分类或回归任务是最关键的。

与传统的特征选择算法相比，粗糙集理论在以下几个方面进行了改进和优化。

首先，粗糙集理论考虑了特征之间的依赖关系。

在传统的特征选择算法中，通常假设特征之间是相互独立的，但实际上特征之间可能存在一定的依赖关系。

粗糙集理论通过将数据集划分为等价类，可以更好地捕捉到特征之间的依赖关系，从而提高了特征选择的准确性和鲁棒性。

其次，粗糙集理论考虑了特征之间的冗余性。

在特征选择中，冗余特征往往会对分类或回归任务造成干扰，降低模型的性能。

传统的特征选择算法往往只考虑特征的个体重要性，而忽略了特征之间的冗余性。

粗糙集理论通过计算下近似和上近似，可以更好地评估特征的重要性和冗余性，从而实现对特征的精确选择。

此外，粗糙集理论还考虑了样本分布的不均衡性。

在实际的数据集中，不同类别的样本数量往往存在不均衡的情况。

传统的特征选择算法往往无法有效地处理样本分布不均衡的问题，导致选择出的特征具有较大的偏向性。

粗糙集理论通过计算下近似和上近似，可以更好地处理样本分布不均衡的情况，从而提高了特征选择的公平性和稳定性。

综上所述，粗糙集理论在特征选择算法中的应用，对于改进和优化特征选择过程具有重要意义。

通过考虑特征之间的依赖关系、冗余性和样本分布的不均衡性，粗糙集理论可以更准确地评估特征的重要性，从而选择出最具有代表性和区分性的特征。

一种基于密度的改进KNN文本分类算法

５８２，ｈｎ）１１９Ｃｉａ
Ａｂｔａｔｓｒｃ：ＴｈｅＫＮＮｇｒｔｍｓａｗｉｅｙｕｅｎａｔｆｃａｉｔｌｇｎｅｆｅｄｌａｏｉｈｉｄｌｓｄｉｒｉｉｎｅｌｅｃｌ．Ａｓａｔｘａｅｏｉａｉｎｉｌｉｉｅｔｃｔｇｒｚｔｏ
ＫＮ（ＮＫ近邻）算法容易实现，一般情况下能取得较高的分类准确率，在基于ＶＳ（Ｍ向量空间模型）的分类算法中，分类效果较好．但ＫＮ分类算法也存在不足之处，若训练样本的分布不均匀，则会造成Ｎ
ＭＡ０ｉｎＬＩＪｎｒｉｇ，Ｊａ，Ｕｉ — ｎＣＡｏｎｕＹｏｇ
（Ｃｍｐｔ￣１ｏｕｅ．ｒＣｌｇｄＪｌｎｅｓｙＸａｎｕｉｎ６０１Ｃｉａ２ＨａｄＴｃｎｌｉｏＳｏｅｅｉＵｉｒｔ，ｉｌｍｅｖｉｍｅＦｊ３１２，ｈ；．ｕｗｅｈｏｇａｎｏ￣Ｃ．￣
ｉｒｖｄＫＮＮａｇｒｔｍｒｐｓｄｔｒｖｅｔｘｔｇｒｚｔｎａｃｒｃｙａｊｓｉｇｔａｎｎａｌｍｐｏｅｌｏｈｉｐｏｏｅｉｏｅｔｔｅｏａｉｃｕａｙｂｄｕｔｉｉｇｓｍｐｅｉｓｏｍｐｈｅｃａｉｏｎｒ
ＫＮＮｘｌｓｉｃｔｏ．ｉｔｔａｓｆａｉｎｎｅｃｉ
ＫｅｒｓＫＮＮ；ｅｔｔｇｒｚｔｎ；ａｌｄｃｉｎｙｗｏｄ：ＴｘｅｏａｉＣａｉｏＳｍｐｅＲｅｕｔｏ

文本分类中一种基于密度的KNN改进方法

文本分类中一种基于密度的KNN改进方法
刘海峰;汪泽焱;姚泽清;刘守生
【期刊名称】《情报学报》
【年(卷),期】2009(028)006
【摘要】特征降维与分类算法的性能是文本自动分类的两个主要问题.KNN算法以其简单、有效、非参数特点常用于文本分类,但是训练文本分布的不均匀对KNN 的分类效果产生负面影响,而在实际应用中训练文本分布不均是常见现象.本文针对这种分类环境,首先提出了一种改进的tf-idf赋权方法用于特征降维,在此基础上进一步提出了一种基于密度的改进KNN方法用于文本分类, 使处于样本点分布较密集区域的样本点之间的距离增大.随后的文本分类试验表明,本文提出的方法基于密度的KNN方法具有较好的文本分类效果.
【总页数】5页(P834-838)
【作者】刘海峰;汪泽焱;姚泽清;刘守生
【作者单位】解放军理工大学理学院,南京,210007;解放军理工大学理学院,南京,210007;解放军理工大学理学院,南京,210007;解放军理工大学理学院,南
京,210007
【正文语种】中文
【中图分类】G35
【相关文献】
1.一种基于apiori算法改进的knn文本分类方法 [J], 骆凡;彭艳兵
2.一种基于Canopy和粗糙集的CRS-KNN文本分类算法 [J], 姚彬修;倪建成;于苹苹;曹博;李淋淋
3.基于密度的kNN文本分类器训练样本裁剪方法 [J], 李荣陆;胡运发
4.一种基于改进ML-KNN的微博文本分类方法 [J], 杜亚璞
5.一种基于密度的改进KNN文本分类算法 [J], 茅剑;刘晋明;曹勇
因版权原因，仅展示原文概要，查看原文内容请购买。

基于变精度粗糙集模型的Web文档分类方法

基于变精度粗糙集模型的Web文档分类方法
王效岳;白如江
【期刊名称】《现代图书情报技术》
【年(卷),期】2005(000)012
【摘要】针对变精度粗糙集模型进行研究,提出了利用变精度粗糙集模型进行Web文档的算法.通过引入阈值β,使得用户可以通过调整β的值,实现对Web文档的不同级别的分类.试验结果表明,该算法在大大降低关键词向量维数的基础上,在保证分类准确度的前提下,有效的增加了分类的灵活性.
【总页数】4页(P51-54)
【作者】王效岳;白如江
【作者单位】山东理工大学图书馆,淄博,255049;山东理工大学图书馆,淄
博,255049
【正文语种】中文
【中图分类】TP391
【相关文献】
1.基于模糊相关的Web文档分类方法 [J], 雷景生
2.基于向量空间模型的多主题Web文本分类方法 [J], 周炎涛;唐剑波;吴正国
3.基于Web挖掘和文档对象模型树的XML网页分类方法 [J], 马勇;郑翔;鲜敏;黎远松
4.一种基于容错粗糙集的Web文档分类方法 [J], 胡和平;易高翔
5.基于概率模型Web服务描述分类方法 [J], 黄聃
因版权原因，仅展示原文概要，查看原文内容请购买。

一种基于粗糙集的改进KNN文本分类算法

一种基于粗糙集的改进KNN文本分类算法苟和平;景永霞;冯百明;李勇【期刊名称】《科学技术与工程》【年(卷),期】2012(012)020【摘要】KNN algorithm is efficient text categorization algorithm in recall and precision, but the computational overhead of text similarity is higher when the number of texts is larger. Aiming at the problem of the KNN, an improved algorithm named RS-KNN based on rough set theory is proposed. According to the upper approximation space and lower approximation space of sample subsets, the algorithm can classify the part of texts driectly. Results of the experiment indicate the RS-KNN reduce computational overhead of text classification.%K最近邻算法(KNN)被认为是向量空间模型下最好的分类算法之一.在准确率和召回率方面比较出众,但随着样本数量的增加其相似度计算开销很大.提出一种改进算法RS-KNN,主要是利用粗糙集的相关理论,计算训练样本集中各样本子类的上近似空间和下近似空间,根据待分类文本出现在不同的近似空间.以缩减与待分类样本计算相似度的训练样本个数.实验表明此算法能够有效地降低分类计算开销.【总页数】4页(P4926-4929)【作者】苟和平;景永霞;冯百明;李勇【作者单位】琼台师范高等专科学校信息技术系,海口571100;琼台师范高等专科学校信息技术系,海口571100;西北师范大学数学与信息科学学院,兰州730070;西北师范大学数学与信息科学学院,兰州730070【正文语种】中文【中图分类】TP391.75【相关文献】1.基于粗糙集的快速KNN文本分类算法 [J], 孙荣宗;苗夺谦;卫志华;李文2.一种基于Canopy和粗糙集的CRS-KNN文本分类算法 [J], 姚彬修;倪建成;于苹苹;曹博;李淋淋3.一种改进的KNN中文文本分类算法 [J], 杜琳娜;闫光辉;杨霞霞;刘利松4.一种改进的KNN文本分类算法 [J], 刘辉;应培培5.一种基于密度的改进KNN文本分类算法 [J], 茅剑;刘晋明;曹勇因版权原因，仅展示原文概要，查看原文内容请购买。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

中图法分类号
An Improved KNN Algorithm Based on Variable Precision Rough Sets
2 YU Ying1，，MIAO DuoQian1 ，LIU CaiHui1 ，WANG Lei1 1
（ Department of Computer Science and Technology，Tongji University，Shanghai 201804 ）
（ 2）
sim（ d i ， d）是 d 与第 i 个最近邻对象 d i 之间的其中，相似度， 1， di ∈ Cj 3）将待分类样本 d 归属于权重最大的那个类别． 2． 2 变精度粗糙集的基本概念经典粗糙集理论是 Pawlak 于 1982 年提出的一处理不精确、不完整信息与知识的种能够定量分析、［Fra bibliotek ］{
0， di Cj
数学工具
．但在数据集存在噪声等干扰的情况
下，经典粗糙集理论会由于对数据的过拟合而使其对新对象的预测能力降低．而现实中处理的数据大存在噪声是在所难免的．为增强粗糙集的多不精确， Ziarko 抗干扰能力，
［7 ］
于 1993 年利用相对错误分类
率提出一种变精度粗糙集模型，该模型通过引入一个精度 β，将集合的上、下近似推广到任意精度水平 0， 0． 5）． β ∈［设 X 和 Y 表示有限论域 U 的非空子集，如果对于每个 e ∈ X 有 e ∈ Y，则称 Y 包含 X ，记作 Y X ，令 c（ X ， Y） =
618
模式识别与人工智能
25 卷
1
引
言
2
2． 1
相关基本概念
KNN 算法基本概念 KNN 分类算法是非参数化方法，算法具体步骤
分类是数据挖掘领域一种基本的学习方法，常、 SVM 、、 KNN 、用的分类方法有决策树神经网络贝叶斯等． KNN 最近邻算法以其实现的简单性及较高的
［1－2 ］分类准确性在许多领域得到广泛应用． KNN 是基于实例的学习方法，当给定一个训练
第 25 卷第 4 期 2012 年 4 月
模式识别与人工智能 PR ＆ AI
Vol． 25 No． 4 Aug 2012
* 基于变精度粗糙集的 KNN 分类改进算法
余
鹰
1， 2
苗夺谦
1
刘财辉
1
王
磊
1
1
（同济大学计算机科学与技术系
2
上海 201804 ）
（江西农业大学软件学院
南昌 330045 ）
2
（ School of Software，Jiangxi Agricultural University，Nanchang 330045 ）
ABSTRACT
K Nearest Neighbor （ KNN） is a simple，stable and effective supervised classification algorithm in machine learning and is used in many practical applications． Its complexity increases with the number of instances，and thus it is not practicable for largescale or high dimensional data． In this paper，an improved KNN algorithm based on variable parameter rough set model （ RSKNN ） is proposed． By introducing the concept of upper and lower approximations in variable precision rough set model，the instances of each class are classified into core and boundary areas，and the distribution of the training set is obtained． For a new instance，RSKNN firstly computes the area it belongs to． Then，according to the area information，the algorithm determines the category directly or searches knearest neighbors among the related areas instead of all areas． In this way，the computing cost is reduced and the robustness is enhanced． The experimental results for selected UCI datasets show that the proposed method is more effective than the traditional KNN with high classification accuracy． Key Words K Nearest Neighbor （ KNN ）， Variable Precision Rough Set， Upper and Lower Approximation
摘
要
传统 KNN 算法具有简单、稳定和高效的特点，在实际领域得到广泛应用．但算法的时间复杂度与样本规
模成正比，大规模或高维数据会降低 KNN 分类效率．文中通过引入变精度粗糙集模型，提出一种改进的 KNN 分类算法．算法运用变精度粗糙集上下近似概念，将各类训练样本划分为核心和边界区域，分类过程计算新样本与各类的近似程度，获取新样本的归属区域，减小分类代价，增强算法的鲁棒性．实验表明，与传统 KNN 算法相比，文中算法保持较高的分类精度并有效提高分类效率，具有一定的理论与实际价值．关键词 K 最近邻（ KNN），变精度粗糙集，上下近似 TP 391 ； TP 181
［8 － 9 ］
提出基于密度对
Cj ） = δ（ d i ，
样本进行裁剪的方法，降低 KNN 的计算量．张孝飞通过文本聚类的方法将样本中的若干相似文档合并成一个中心文档，并用这些中心文档代替原 6］始样本建立分类模型，减少相似计算量．文献［通过选择一个样本作为基准点，然后将所有其它样本按照距基准样本的距离进行排序并建立索引表．分类时根据索引表和有序队列查找 K 个最近邻，减小查找范围，从而提高 KNN 的分类速度．这些算法主要是通过一定的策略来直接减少需要比较的样本数量，或通过降低特征维数，减少计算量，从而达到提高分类效率的目的．这些方法在样本裁剪过多或特征维数过低时，会引起分类准确率严重下降．此外，确定裁剪哪些样本和特征也是一个非常困难的问题．已有的 KNN 改进算法在提高分类效率时忽略训练样本空间的分布特征，若能知道每个类的分布区域，只需少量计算就可判断一个待分类对象的归属．现实中因为训练样本有限，类的分布区域是模糊的，而变精度粗糙集
n
它只进行简单地存储或稍加处理，仅当看到待集时，以便根据与训练集中对象分类对象时才进行泛化，的相似性对该对象进行分类． KNN 算法虽然简单、有效，但是通常速度很慢．因为寻找训练集中 K 个最近邻对象的方法是．计算训练集中每个训练实例到待分类对象的距离，然后选择距离最近的 K 个．因此，处理一个待分类对象要搜寻整个训练集，且这个过程与训练集的大小成线性关系．对于训练集规模较大或维数较高的情况，寻找 K 个最近邻对象的计算量庞大，直接影响分类的速度．针对这个问题，有必要在使用 KNN 算法前对数据进行一些处理．例 3］为提高分类效率，如文献［提出一种基于特征词缩减的 KNN 改进算法．李荣陆等等
* 国家自然科学基金资助项目（ No． 60970061 ， 61075056 ， 61103067 ）收稿日期： 2011－06－24 ；修回日期： 2011－12－19 1979 年生， mail： yuyingjx@ 163． com．苗夺谦，作者简介余鹰，女，博士研究生，主要研究方向为粗糙集理论、数据挖掘． E1964 年生， 1979 年生，男，教授，博士生导师，主要研究方向为粗糙集理论、智能信息处理等．刘财辉，男，博士研究生，主要研 1976 年生，究方向为粗糙集、机器学习．王磊，男，博士研究生，主要研究方向为智能信息处理、数据挖掘．
如下． 1 ）搜索训练集 S，找出最接近待分类对象 d 的 k 个训练样本．这 k 个训练样本是待分类对象的 k 个 “最近邻” ．“最近邻” 用距离度量，如欧氏距离．两个 x12 ， …， x1n ）和 X2 = （ x21 ， x22 ， …， x2n ）对象 X1 = （ x11 ，的欧式距离：
是处理模糊和不确定性的数
{
card（ X ∩ Y）， if card（ X ）＞ 0 card（ X ） 0， if card（ X ） = 0 1 －
学工具，可用于分布区域的刻画．因此，本文基于变精度粗糙集模型提出一个 KNN 改进算法．实验表明，改进后的算法能在基本不改变传统 KNN 算法分类精度的条件下提高分类效率．
card（ X ）表示集合的势， Y）为集合 X 其中，称 c（ X ，关于集合 Y 的相对错误分类率．令 0 ≤ β ＜ 0 ． 5 ，多数包含关系： Y X c（ X ， Y） ≤ β ，