开放科学（资源服务）标志码（OSID）：

0 概述

分类任务^[1]是利用已知类别的样本通过建立模型预测新样本的类别^[2]。分类是数据挖掘中最重要的任务之一，应用十分广泛。目前，常用的分类算法主要有决策树^[3]、贝叶斯分类器^[4]、人工神经网络^[5]、支持向量机^[6]、k近邻（k-Nearest Neighbor，KNN）算法^[7]等。这些已有的分类算法及其改进算法被广泛地应用于各个领域，如统计学^[8]、医学^[9]、模式识别^[10]、决策理论^[11]等。KNN算法的基本思想^[12]是通过已知类别的训练样本寻找待测样本的$ k $个近邻，将$ k $个近邻中出现频率最高的类别作为待测样本的类别。由于KNN算法具有理论简单、易于操作等优点，被认为是数据挖掘中最简单的方法之一^[13]。但是，KNN算法也存在不足：第1个问题是它没有考虑样本的分布，当样本分布不均匀或样本中存在噪声样本时，分类精度会明显下降；第2个问题是所有训练样本具有同等重要性，判断待分类样本的类别时没有考虑$ k $个近邻的区别；第3个问题是使用单一的多数投票原则进行分类决策。以上3个问题都会影响分类的准确率及效率。

针对KNN算法存在的问题，很多研究者提出了不同的改进算法。文献[14]提出了k近质心近邻（k-Nearest Centroid Neighbor，KNCN）算法，该算法的设计思想是近邻点要尽可能地离待分类样本近，而且近邻点要均匀地分布在待分类样本周围，通过这些近邻点所属类别判断待测样本的类别。文献[15]提出了一种基于局部权重的k近质心近邻算法LMKNCN，该算法的设计思想是为$ k $个近质心近邻赋予不同的权重，再通过决策函数对每个测试样本进行分类。文献[16]将模糊理论与KNN相结合，提出了模糊k近邻（Fuzzy k-Nearest Neighbor，FKNN）算法，该算法的基本思想是为训练样本分配隶属度，根据$ k $个近邻样本的隶属度和距离的权重，通过最大隶属度原则确定待分类样本的类别。文献[17]提出了自适应$ k $值的FKNN算法，该算法的设计思想是通过改进的粒子群算法自适应优化$ k $值和模糊强度参数$ m $，从而提高算法性能。文献[18]将KNCN算法和FKNN算法相结合，提出了模糊k近质心近邻（Fuzzy KNCN，FKNCN）算法，该算法的设计思想是使用近质心近邻的概念来确定最近邻，并使用模糊理论为每个类分配隶属度，同时解决了样本分布和权重问题。文献[19]提出了基于Bonferroni均值的FKNCN算法，该算法的设计思想是运用均值算子和近质心近邻概念，计算最近的局部Bonferroni均值向量确定待分类样本的类别标签，该算法对异常值具有很好的鲁棒性。

然而，上述FKNCN算法及其改进算法在计算训练样本的隶属度时没有考虑训练样本中存在的噪声点或离群点，这在小样本数据集中会大幅降低分类精度。同时，算法忽略了训练样本特征的差异性，没有进行特征选择，影响了分类性能。针对这2个问题，本文对FKNCN算法进行改进，提出基于隶属度的模糊加权k近质心近邻算法MRFKNCN。设计新的隶属度函数计算训练样本的隶属度，区分训练样本中存在的噪声或离群样本与有效样本。在此基础上，通过基于冗余分析的Relief-F算法计算每个特征的权重，删去较小权重所对应的特征和冗余特征，选出重要特征后根据加权欧氏距离选取$ k $个有代表性的近质心近邻，并确定待测样本的类标号。

1 预备知识 1.1 符号说明

本文算法所使用的符号说明见表 1。

1.2 FKNCN算法

假定在p维特征空间中，训练样本集$ T=\{{x}_{j}\in {\mathbb{R}}^{p}{\}}_{j=1}^{n} $有$ M $个类标签$ {c}_{1}, {c}_{2}, \cdots , {c}_{M} $，给定一个待测样本点$ y $，FKNCN算法步骤如下：

步骤1   利用式（1）计算待测样本y与所有训练样本间的欧氏距离，进行升序排列，选择最短距离所对应的训练样本作为第1个近质心近邻点$ {x}_{1}^{\mathrm{N}\mathrm{C}\mathrm{N}} $：

$ d(y, {x}_{j})=\sqrt{(y-{x}_{j}{)}^{\mathrm{T}}(y-{x}_{j})} $

(1)

步骤2   当$ r=\mathrm{2, 3}, \cdots , k $时，利用式（2）计算$ {T}_{i} $（$ {T}_{i} $表示除去被选为近质心近邻的训练样本之外所有剩余的训练样本）中的训练样本与之前所选的$ r-1 $个近质心近邻的质心：

$ {x}_{rj}^{\mathrm{c}}=\frac{({x}_{1}^{\mathrm{N}\mathrm{C}\mathrm{N}}+{x}_{2}^{\mathrm{N}\mathrm{C}\mathrm{N}}+\cdots +{x}_{r-1}^{\mathrm{N}\mathrm{C}\mathrm{N}})+{x}_{j}}{r} $

(2)

步骤3   利用式（3）计算训练样本的质心与待测样本间的最短距离，选取所对应的训练样本作为第r个近质心近邻：

$ d(y, {x}_{rj}^{\mathrm{c}})=\mathrm{m}\mathrm{i}\mathrm{n}\sqrt{(y-{x}_{rj}^{\mathrm{c}}{)}^{\mathrm{T}}(y-{x}_{rj}^{\mathrm{c}})} $

(3)

步骤4   记$ k $个近质心近邻的集合为$ {X}^{\mathrm{N}\mathrm{C}\mathrm{N}}=\{{x}_{r}^{\mathrm{N}\mathrm{C}\mathrm{N}}\in {\mathbb{R}}^{p}{\}}_{r=1}^{k} $，利用式（4）计算待测样本$ y $属于第$ i $类的模糊隶属度：

$ {u}_{i}^{\mathrm{N}\mathrm{C}\mathrm{N}}\left(y\right)=\frac{\sum\limits_{r=1}^{k}{u}_{ir}(1/d(y, {x}_{r}^{\mathrm{N}\mathrm{C}\mathrm{N}}{)}^{2/(m-1)})}{\sum\limits_{r=1}^{k}(1/d(y, {x}_{r}^{\mathrm{N}\mathrm{C}\mathrm{N}}{)}^{2/(m-1)})} $

(4)

其中：$ i={c}_{1}, {c}_{2}, \cdots , {c}_{M} $，$ d(y, {x}_{r}^{\mathrm{N}\mathrm{C}\mathrm{N}}) $为待测样本和近质心近邻的欧氏距离；$ m $为模糊强度参数，代表每个近质心近邻与待测样本的权重；$ {u}_{ir} $为训练样本的隶属度。有以下2种计算方式定义$ {u}_{ir} $^[18]：一种是硬性分类，隶属度定义如式（5）所示；另一种是使用模糊隶属度，找到每个近质心近邻训练样本的k个近邻$ \left({x}_{rk}^{\mathrm{N}\mathrm{C}\mathrm{N}}\right) $，则$ {x}_{rk}^{\mathrm{N}\mathrm{C}\mathrm{N}} $属于第$ i $类的隶属度定义如式（6）所示。其中：$ {n}_{r} $表示第$ r $个近质心近邻训练样本的$ k $个近邻属于第$ i $类的近邻个数；$ c\left({x}_{rk}^{\mathrm{N}\mathrm{C}\mathrm{N}}\right) $表示近质心近邻训练样本的$ k $个近邻所属的类别。

$ {u}_{ir}\left({x}_{r}^{\mathrm{N}\mathrm{C}\mathrm{N}}\right)=\left\{\begin{array}{l}1, {x}_{r}^{\mathrm{N}\mathrm{C}\mathrm{N}}\in i\\ 0, {x}_{r}^{\mathrm{N}\mathrm{C}\mathrm{N}}\notin i\end{array}\right. $

(5)

$ {u}_{ir}\left({x}_{rk}^{\mathrm{N}\mathrm{C}\mathrm{N}}\right)=\left\{\begin{array}{l}0.51+0.49({n}_{r}/k), c\left({x}_{rk}^{\mathrm{N}\mathrm{C}\mathrm{N}}\right)=i\\ 0.49({n}_{r}/k), c\left({x}_{rk}^{\mathrm{N}\mathrm{C}\mathrm{N}}\right)\ne i\end{array}\right. $

(6)

利用式（5）和式（6）均可计算训练样本的隶属度。一般而言，优先选择式（6）计算其隶属度^[18]，原因在于该计算方式引入了模糊理论，将训练样本的隶属度模糊化，通过训练样本的$ k $个近邻确定其隶属度，能够确保训练样本在自己的类中被赋予较高的权重，而在其他类中被赋予较低的权重。

步骤5   通过最大的模糊隶属度值判断待测样本y的所属类别，如式（7）所示：

$ y=\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}\left({u}_{i}^{\mathrm{N}\mathrm{C}\mathrm{N}}\right(y\left)\right) $

(7)

步骤6   对于一个新的待测样本点，重复步骤1~步骤5。

1.3 特征的相关性度量

定义1   皮尔逊相关系数^[20]

设$ p $维空间中的2个样本点$ e=({e}_{1}, {e}_{2}, \cdots , {e}_{p}) $，$ f=({f}_{1}, {f}_{2}, \cdots , {f}_{p}) $，两者之间的皮尔逊相关系数的计算公式如式（8）所示：

$ {r}_{ef}=\frac{\sum\limits_{i=1}^{p}({e}_{i}-\overline{e})({f}_{i}-\overline{f})}{\sqrt{\sum\limits_{i=1}^{p}({e}_{i}-\overline{e})}\sqrt{\sum\limits_{i=1}^{p}({f}_{i}-\overline{f})}} $

(8)

其中：$ \overline{e}=\frac{1}{p}\sum\limits_{i=1}^{p}{e}_{i} $，$ \overline{f}=\frac{1}{p}\sum\limits_{i=1}^{p}{f}_{i} $，分别表示样本$ e $、$ f $所有特征的均值。

$ {r}_{ef} $表示特征之间的线性相关性，其取值范围是$ \left[-\mathrm{1, 1}\right] $，即$ 0\le \left|{r}_{ef}\right|\le 1 $，相关系数的绝对值越大，相关性越强，相关系数的绝对值越接近于0，相关度越弱。

2 MRFKNCN算法

隶属度函数的设计是FKNCN算法的关键，但FKNCN算法在计算训练样本的隶属度时，并没有考虑噪声点或离群点对分类的影响，同时该算法在计算待测样本与训练样本间的欧氏距离时，把所有训练样本的各维特征等同对待，没有区分它们的重要程度，这些都会影响分类的性能。为此，本文提出基于隶属度的模糊加权k近质心近邻算法MRFKNCN。通过密度聚类思想为训练样本设计新的隶属度函数、利用基于冗余分析的Relief-F算法计算特征的权重、确定待测样本的类别这3个部分克服噪声点、离群点的影响，同时解决相同特征权重的问题，提高分类的效率和准确率。

2.1 隶属度函数构造

样本集中经常会出现噪声点或离群点，而FKNCN算法在计算训练样本的隶属度时，没有区分这些样本与有效样本，导致所有训练样本的隶属度相同，这会在很大程度上影响分类的准确率。本文采用密度聚类的思想构造最小包围球。首先计算最小包围球的类中心和半径；然后根据训练样本在最小包围球的位置确定其隶属度；最后根据隶属度的大小判断训练样本是离群或噪声样本还是有效样本。计算最小包围球类中心和半径的具体步骤如下：

步骤1   计算训练样本$ {x}_{j} $与训练样本集中其他样本的欧氏距离，找到$ {x}_{j} $的第$ r $个近邻$ ({x}_{jr}, r=\mathrm{1, 2}, \cdots , k) $。

步骤2   根据样本$ {x}_{j} $的$ k $个近邻构造$ n\times k $的密度矩阵$ \mathit{D}=\left(d\right({x}_{j}, {x}_{jr}{\left)\right)}_{n\times k} $。

步骤3   利用式（9）计算所有样本的密度$ \rho \left({x}_{j}\right) $：

$ \rho \left({x}_{j}\right)=\frac{{z}_{j}}{\sum\limits_{j=1}^{n}{z}_{j}} $

(9)

其中：$ {z}_{j}=\sum\limits_{r=1}^{k}\frac{1}{d({x}_{j}, {x}_{jr})} $，为样本$ {x}_{j} $与其$ k $个近邻距离的倒数和。将密度从大到小排列，得到密度点集$ G $。

步骤4   选择最大密度样本点$ {x}_{\mathrm{m}\mathrm{a}\mathrm{x}} $，并找出离该点最近的样本点$ {x}_{n\_\mathrm{m}\mathrm{a}\mathrm{x}} $，通过这2个点确定最小包围球的类中心$ O\left(T\right) $：

$ O\left(T\right)=0.7{x}_{\mathrm{m}\mathrm{a}\mathrm{x}}+0.3{x}_{n\_\mathrm{m}\mathrm{a}\mathrm{x}} $

(10)

步骤5   利用式（10）计算最小包围球的半径：

$ R\left(T\right)=\lambda \frac{a\left(T\right)}{{n}^{\delta }} $

(11)

其中：$ \lambda $为自定义的惩罚因子；$ \delta $为半径调整系数；$ a\left(T\right) $为类中心到所有样本点距离的平均值。

计算出样本集中最小包围球的类中心和半径后，利用式（12）确定训练样本的隶属度：

$ u\left({x}_{{}_{j}}\right)=\left\{\begin{array}{l}0.7\times \left(\frac{1-d\left({x}_{j}\right)/R\left(T\right)}{1+d\left({x}_{j}\right)/R\left(T\right)}\right)+0.3, d\left({x}_{j}\right)\le R\left(T\right)\\ 0.3\times \left(\frac{1}{1+\left(d\right({x}_{j})-R(T\left)\right)}\right), d\left({x}_{j}\right) > R\left(T\right)\end{array}\right. $

(12)

其中：$ d\left({x}_{j}\right) $为训练样本$ {x}_{j} $与最小包围球类中心$ O\left(T\right) $的欧氏距离。从式（12）可以看出，训练样本离最小包围球的类中心越远，该训练样本的隶属度就越小。如果训练样本位于最小包围球之内，其隶属度都大于0.3；反之，位于最小包围球之外的训练样本，其隶属度都小于等于0.3。位于最小包围球之外的样本一般都为离群或噪声样本。本文构造最小包围球方法简单有效，原因在于其只需计算最小包围球的类中心和半径，再通过式（12）为离群或噪声样本赋予较小的隶属度，即可快速区分出离群或噪声样本与有效样本。

2.2 基于冗余分析的Relief-F算法

本节提出基于冗余分析的Relief-F特征选择算法计算每个特征的权重。首先将FKNCN算法中的欧氏距离改为特征加权的欧氏距离；然后通过加权欧氏距离确定待测样本的近质心近邻；最后通过近质心近邻的隶属度和距离加权确定待测样本的类隶属度。

2.2.1 特征权重的计算

在分类过程中，并不是所有的特征都与分类强相关，也会存在一些不相关特征及冗余特征。如果在分类时不处理这些特征，会出现计算成本高、分类性能低等问题。为了得到最优特征子集，特征选择是必不可少的。Relief-F算法^[21]是最成功的特征选择方法之一，算法的具体步骤如下：

1）对所有特征归一化处理：

$ {x}_{j, l}^{\mathrm{\text{'}}}=\frac{{x}_{j, l}-{\mu }_{l}}{{s}_{l}} $

(13)

其中：$ {x}_{j, l}^{\mathrm{\text{'}}} $为样本$ {x}_{j} $通过归一化处理后在第$ l $个特征上的值；$ {\mu }_{l} $、$ {s}_{l} $分别为所有样本在第$ l $个特征上的均值、标准差；$ {x}_{j, l} $为样本$ {x}_{j} $在第$ l $个特征上的值。

2）从训练集中随机选择样本点$ {x}_{j} $，找出$ {x}_{j} $同类的$ k $个最近邻样本集和不同类的$ k $个样本集。

3）通过式（14）计算每个特征的特征权重^[22]：

$ \begin{array}{l}w\left(l\right)\mathrm{ }=w\left(l\right)\mathrm{ }-\sum\limits_{r=1}^{k}{\rm{diff}}({A}_{l}, {x}_{j}, {H}_{r})/\alpha k+\\ \;\;\;\;\sum\limits_{c\ne \mathrm{c}\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{s}\left({x}_{i}\right)}\left[\frac{p\left(c\right)}{1-p\left(\mathrm{c}\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{s}\right({x}_{j}\left)\right)}\sum\limits_{r=1}^{k}{\rm{diff}}({A}_{l}, {x}_{j}, {M}_{r}(c\left)\right)\right]/\alpha k\end{array} $

(14)

其中：$ \mathrm{d}\mathrm{i}\mathrm{f}\mathrm{f}({A}_{l}, {x}_{j}, {H}_{r}) $表示样本$ {x}_{j} $与$ {H}_{r} $在第$ l $个特征上的距离；$ \mathrm{d}\mathrm{i}\mathrm{f}\mathrm{f}({A}_{l}, {x}_{j}, {M}_{r}(c\left)\right) $表示样本$ {x}_{j} $与$ {M}_{r}\left(c\right) $在第$ l $个特征上的距离；$ p\left(c\right) $表示属于类别$ c $的样本出现的概率。

虽然Relief-F算法在处理多分类问题时效率高并且能够很好地剔除不相关特征，但不能过滤冗余特征。为此，本文在Relief-F算法的基础上提出基于冗余分析的Relief-F特征选择算法计算所有特征的权重，算法描述如下：

算法1   基于冗余分析的Relief-F算法

输入  训练集$ T $，样本抽样次数$ \alpha $，最近邻样本个数$ k $

输出  每个特征的特征权重$ w $

步骤1   所有特征归一化处理。

步骤2   将所有特征权重置0。

步骤3   在$ T $中随机选择样本点$ {x}_{j} $。

步骤4   找到与$ {x}_{j} $同类的$ k $个最近邻样本集$ {H}_{r} $。

步骤5   每个类$ c\ne \mathrm{c}\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{s}\left({x}_{j}\right) $，找到与$ {x}_{j} $不同类的k个最近邻样本集$ {M}_{r}\left(c\right) $。

步骤6   更新每个特征的特征权重。

步骤7   根据特征权重阈值，选择分类权重最大的特征集合。

步骤8   冗余分析。利用皮尔森相关系数计算特征之间的相关性。

以上步骤是在一次抽样下计算每个特征的特征权重，经过$ \alpha $次抽样后，将特征权重更新$ \alpha $次，并设置一个特征权重阈值$ \mathit{\Gamma} $，将每个特征权重与总特征权重的比值累积，选择累积特征权重比大于阈值$ \mathit{\Gamma} $的特征作为新特征，并删掉剩余的不相关特征，然后分析新特征之间的相关性，在特征相关性较大的情况下保留权重较高的特征，消除权重较低的特征，目的是消除冗余特征的干扰。通过基于冗余分析的Relief-F算法计算特征权重，同时减少特征的数量、降低维数，从而完成特征选择。

2.2.2 加权欧氏距离的计算

利用式（15）计算待测样本$ y $与训练样本$ {x}_{j} $的加权欧氏距离，从而确定待测样本的$ k $个近质心近邻：

$ d(y, {x}_{j})=\sqrt{\sum\limits_{l=1}^{p}w\left(l\right)({y}_{l}-{x}_{jl}{)}^{\mathrm{T}}({y}_{l}-{x}_{jl})} $

(15)

其中：$ w\left(l\right) $为训练样本第$ l $个特征的特征权重，且$ w\left(l\right) > 0 $，$ \sum\limits_{l=1}^{p}w\left(l\right)=1 $。

2.2.3 待分类样本类别的确定

计算出每个特征的特征权重后，利用式（16）计算待测样本y属于每个类别的隶属度值：

$ {u}_{i}^{\mathrm{N}\mathrm{C}\mathrm{N}}\left(y\right)=\frac{\sum\limits_{r=1}^{k}{u}_{i}\left({x}_{r}^{\mathrm{N}\mathrm{C}\mathrm{N}}\right)(1/d({y}_{l}, {x}_{rl}^{\mathrm{N}\mathrm{C}\mathrm{N}}{)}^{2/(m-1)})}{\sum\limits_{r=1}^{k}(1/d({y}_{l}, {x}_{rl}^{\mathrm{N}\mathrm{C}\mathrm{N}}{)}^{2/(m-1)})} $

(16)

其中：$ d({y}_{l}, {x}_{rl}^{\mathrm{N}\mathrm{C}\mathrm{N}}) $表示待测样本$ y $和第$ r $个近质心近邻的加权欧氏距离；$ {u}_{i}\left({x}_{r}^{\mathrm{N}\mathrm{C}\mathrm{N}}\right) $表示待测样本的第$ r $个近质心近邻属于第$ i $类的隶属度。若$ {x}_{r}^{\mathrm{N}\mathrm{C}\mathrm{N}} $属于类别$ i $，则利用式（12）计算$ {u}_{i}\left({x}_{r}^{\mathrm{N}\mathrm{C}\mathrm{N}}\right) $；若不属于类别$ i $，则$ {u}_{i}\left({x}_{r}^{\mathrm{N}\mathrm{C}\mathrm{N}}\right) $的值为0。

得到待测样本$ y $属于每个类别的隶属度后，通过最大隶属度原则确定待测样本$ y $的类别。

2.3 算法描述

MRFKNCN算法的设计思想为：首先计算训练样本的隶属度；然后计算所有特征的权重，并找出$ k $个近质心近邻；最后计算待测样本的模糊隶属度，通过最大隶属度原则确定待测样本的类别。具体步骤如算法2所示，算法流程如图 1所示。

算法2   MRFKNCN算法

输入  近质心近邻个数$ k $，待测样本点$ y $，训练样本集$ T $，模糊强度参数$ m $

输出  待测试样本$ y $的类别

步骤1   利用式（9）计算训练样本的密度。

步骤2   利用式（10）和式（11）计算最小包围球的类中心和半径。

步骤3   利用式（12）计算训练样本隶属度。

步骤4   通过基于冗余分析的Relief-F算法计算所有特征的权重。

步骤5   利用式（15）计算待测样本与训练样本之间的加权欧氏距离，找出$ k $个近质心近邻集合。

步骤6   利用式（16）计算待测样本的模糊隶属度。

步骤7   根据最大隶属度原则确定待分类样本的类别。

2.4 算法复杂度分析

假设$ n $表示数据集的规模，$ p $表示特征维数，$ k $表示近邻个数，$ M $表示类别个数。基于隶属度的模糊k近质心近邻算法的时间复杂度主要来源于以下5个部分：1）通过密度聚类思想计算训练样本的隶属度，时间复杂度为$ O\left(np\right) $；2）计算每个特征的特征权重，时间复杂度为$ O\left(np\mu \right) $；3）计算训练样本的质心，时间复杂度为$ O\left(nk\right) $；4）待测样本到各个类的加权距离，时间复杂度为$ O\left(np\right) $；5）通过最大隶属度原则确定待测样本的类别，时间复杂度为$ O\left(M\right) $。因此，MRFKNCN算法总的时间复杂度为$ O(2np+nk) $。

3 仿真实验与分析 3.1 数据集

为验证本文MRFKNCN算法的有效性，选用UCI和KEEL中的11个标准数据集和4个含噪数据集进行仿真实验，所有实验都在Matlab2014b的环境下完成。表 2、表 3列出了实验中所用数据集的相关信息。

3.2 算法参数设置

为了更好地测试各算法的分类效果，对本文算法所使用的相关参数进行调优。

参考文献[23]，取$ \lambda =2 $，$ \delta =0.14 $计算最小包围球的半径。计算完特征权重后，需要设置一个阈值$ \mathit{\Gamma} \in \left(\mathrm{0, 1}\right) $^[22]。对本文的数据集进行多次试验可知，当$ \mathit{\Gamma} =0.8 $时，选出的新特征最具有代表性，模糊强度参数$ m=2 $，当模糊隶属度值与距离平方成反比时，在分类过程中会得到最优结果^[18]。

3.3 实验结果与分析

本节设计了4个实验来验证MRFKNCN算法的有效性，将分类的准确率作为评价标准，比较本文算法与其他算法的性能。准确率的计算方法如下：

$ A=\frac{{N}_{\mathrm{c}}}{{N}_{\mathrm{t}}}\times 100\mathrm{\%} $

(17)

其中：$ {N}_{\mathrm{c}} $为正确分类的样本个数；$ {N}_{\mathrm{t}} $为实际分类的样本个数。

对于样本总数较小的数据集，通过10次5折交叉验证进行实验；对于样本总数大的数据集，通过10次10折交叉验证进行实验，最后将所有实验得到的准确率平均值作为测试结果。实验1~实验3均采用交叉验证法确定最优k值。

3.3.1 MRFKNCN算法总体性能分析

实验1   为验证本文所提的新的隶属度函数在噪声点或离群点影响下的有效性，将MRFKNCN算法与利用式（5）计算隶属度的FKNCN算法（命名为FKNCN1）及利用式（6）计算隶属度的FKNCN算法（命名为FKNCN2）进行比较，运用表 3含噪数据集。实验结果如表 4所示。

表 4结果表明，当训练集中含有噪声点或离群点时，MRFKNCN算法的平均准确率明显高于FKNCN1算法和FKNCN2算法，在Iris、Vehicle、Wine、Letter这4个含噪数据集上，MRFKNCN算法的平均准确率比FKNCN1算法分别提高4.48、3.16、3.64、2.86个百分点，比FKNCN2算法分别提高3.26、3.92、2.69、2.33个百分点，这表明本文所设计的新隶属度函数可以很好地识别出训练样本集中的噪声点或离群点，尤其是在Iris小数据集中，MRFKNCN算法获得了较高的准确率。

实验2   为验证基于冗余分析的Relief-F算法计算特征权重方法的有效性，将MRFKNCN算法与未加权欧氏距离的MRFKNCN算法（命名为MRFKNCN_N）、确定统一特征权重的MRFKNCN算法（命名为MRFKNCN_U）进行对比，运用表 3中Arrhythmia、Segment、Zoo、Balance、Thyroid这5个数据集，3种算法的平均准确率结果如图 2所示。

图 2结果表明，5个数据集中MRFKNCN的分类准确率都明显优于MRFKNCN_N算法和MRFKNCN_U算法，说明不同的特征有不同的贡献率。因此，为了保证算法的准确率，应分别确定每个样本特征的权重，区分其差异，从而提高分类的性能。

实验3   在最优$ k $值下比较MRFKNCN、KNN^[13]、KNCN^[14]、LWKNCN^[15]、FKNN^[16]、FKNCN^[18]和BMFKNCN^[19]算法的分类平均准确率，所得结果如表 5所示，其中加粗数字为最优值。

表 5结果表明，虽然在Thyroid数据集中，BMFKNCN算法取得了较高的准确率，但是MRFKNCN算法的准确率仍高于其他5种对比算法。MRFKNCN算法在其余10个数据集中的准确率都高于其他6种对比算法的准确率，尤其是在Movement、Arrhythmia、Multivariate这3个高维数据集上的准确率大幅提升，说明MRFKNCN算法不仅可以去除噪声样本对分类性能的影响，还可以选出有代表性的特征提高分类的准确率。同时，MRFKNCN算法在11个数据集中获得了最高的平均准确率。

3.3.2 MRFKNCN算法在不同k值下的性能分析

实验4   为了验证MRFKNCN算法在不同k值下的分类性能，将MRFKNCN算法与6个对比算法在k=1~15时进行比较。运用表 3的Hayes-roth、Ecoli、Glass、Sends、Cleveland这5个数据集。图 3~图 7给出了7种算法的分类准确率对比折线图。

4 结束语

针对FKNCN算法未区别样本特征的不足，本文提出基于隶属度的模糊加权k近质心近邻算法MRFKNCN。利用密度聚类思想设计新的隶属度函数计算训练样本的隶属度，通过基于冗余分析的Relief-F算法计算每个特征的权重，删去不相关特征和冗余特征，选出重要的特征，并利用加权欧氏距离选取$ k $个近质心近邻，最终根据最大隶属度原则对待测样本进行分类。该算法有效解决了训练样本中存在噪声样本或离群样本的问题，而且还为每个特征赋予不同的权重，更符合分类的实际情况。实验结果表明，MRFKNCN算法在分类性能上明显优于其他对比算法。由于FKNCN算法对参数$ k $和模糊强度因子$ m $敏感也会影响分类性能，因此下一步将研究如何自适应地优化FKNCN算法的参数$ k $和模糊强度因子$ m $，进一步提高算法准确率。