摘要
为解决支持向量机(SVM)在分类时通常含有大量的冗余样本，从而导致面对较大规模数据集时SVM计算复杂度受到限制的问题，提出一种局部密度最小不确定性的SVM样本选择算法。该方法对决策面影响较大的边界数据进行有效选择，通过提取可能含有支持向量的训练样本，降低计算开销，进而提高SVM性能。首先，计算训练样本的K互近邻个数与高斯核密度估计。其次，将K互近邻个数与高斯核密度估计进行加和得到每个样本点的K局部密度并获取密度矩阵。然后，利用局部密度不确定性平衡优化方法，将密度矩阵进行三值映射后使不确定性改变量达到最小时得到最优阈值，并划分密度矩阵为中心数据与边界数据。最后，提取边界数据并作为SVM的训练样本建立分类模型。结果表明：利用该方法在UCI数据集上与其他6种常用样本选择方法进行实验对比，以准确率、保存率作为性能指标，文中提出的算法可以迅速划分中心数据与边界数据并删除大量冗余的训练样本，有效降低SVM的训练负担的同时提高了分类性能。
关键词
Abstract
To address the issue that support vector machines (SVM) frequently encompass a considerable number of redundant samples during classification, which restricts the computational complexity of SVM when confronted with large-scale datasets, a SVM sample selection algorithm based on local density minimum uncertainty is put forward. This approach efficiently identifies influential boundary data points that significantly affect the decision boundary, subsequently reducing computational costs by isolating potential support vectors from the training set, thereby bolstering SVM’s overall effectiveness. Firstly, the number of K nearest neighbors and Gaussian kernel density estimation of the training samples are computed; Secondly, the sum of the number of K nearest neighbors and Gaussian kernel density estimation is derived for each sample point to acquire the K local density and obtain the density matrix; Subsequently, employing the local density uncertainty balancing optimization method, the density matrix undergoes a triple-mapping process to minimize uncertainty changes, yielding the optimal threshold. This threshold then partitions the density matrix into center data and boundary data. Finally, the boundary data are extracted and utilized as training samples for the SVM, enabling the establishment of an effective classification model. To experimentally evaluate the efficacy of our method, we compared it with six commonly utilized sample selection techniques on UCI datasets, employing accuracy and preservation rate as key performance metrics. The findings indicate that the method introduced in this paper significantly reduces the number of redundant training samples, thereby effectively alleviating the training burden on SVM and enhancing its classification performance.
支持向量机（support vector machines，SVM）由Cortes等[1]于1995年提出，是一种基于VC维理论（Vapnik-Chervonenkis dimension）和结构风险最小化（structural risk minimization，SRM）原理的监督学习方法。SVM凭借坚实的统计学习理论在分类问题上具有许多优点，譬如SVM根据结构风险最小化原则同时考虑了经验风险和结构风险，这样避免了因样本量较少时经验风险最小化导致过拟合，提升了泛化性能[1-2]； SVM解决了凸二次规划（quadratic programming，QP）问题，使其不会陷入局部最小值而是转为找到全局最小值[3]；此外SVM通过最大化两类数据集间的距离得出稀疏解，从而以较低的复杂度提高了其泛化性[4]。由于具有上述优势，SVM被广泛应用于面部识别[5-6]、疾病诊断[7-8]、文本识别[9-10]、故障诊断[11-12]等领域。目前SVM在处理上述实际问题时，往往需要使用核技巧[13-14]将训练数据映射至高维空间，使数据点在高维空间变得线性可分。虽然核技巧提高了支持向量机的分类精度，但映射数据时需要大量的计算量，训练时间也会随之增加，在解决较大规模的数据集时，SVM分类器的效率会随着训练样本的增加而严重下降[15]。
值得注意的是，仅有一部分被称为支持向量（support vector，SV）的训练样本会影响SVM超平面的构建，因此可以去除掉与SV不相关的训练样本，保留与SV关系较为密切的训练样本，这样既不影响决策超平面的构建，也在一定程度上减少了训练数据。综上所述，减少冗余的非SV数据样本后再进行训练是提高SVM面对较大规模数据时提高训练效率的办法[16]。
近年来，研究者从基于聚类、几何分析等方面对训练数据进行样本选择，以降低SVM的计算开销。基于聚类的样本选择方法是一种被普遍应用的无监督机器学习方法，它将训练样本分为几个簇，每个簇的样本点相比其他簇的样本点更为相似，将聚类后的训练数据进行样本选择，以减少训练时间[15]。如Barros de Almeida等[17]提出的SVM-KM算法，该算法采用K均值聚类将训练样本聚成多个簇，其中包含单类标签的簇和多类标签的簇，然后仅保留单类标签簇的质心以及多类标签的所有数据点，将保留的点对SVM进行训练。该方法减少了训练样本的同时也降低了计算复杂度，但容易受训练数据集中特征的影响，并且对高维、稀疏的数据集进行分类时性能会下降。Shen等[18]提出一种K均值聚类后引入Fisher判别比的方法来缩减训练样本，该方法采用在簇中寻找边界样本来减少冗余数据的思想，经过两阶段来完成训练样本的筛选。1）使用K均值聚类，根据聚类后训练样本的类别标签将簇进一步划分为更小的簇，然后通过使用簇的质心作为训练数据来获得近似超平面，并采用最大最小距离聚类（max-min cluster distance，MMCD）算法去除远离近似超平面的冗余簇；2）通过快速迭代（fast incremental false discovery rate，FIFDR）算法删除每个剩余簇中的数据点，最后将保留点反馈入SVM进行分类。该方法相较原始训练数据训练准确率有所下降，但去除了较多冗余点，显著减少了训练时间。此外模糊聚类也被经常应用于样本选择，周玉等[19]提出了一种基于模糊C均值聚类（Fuzzy C-means clustering，FCM）诱导出阴影集（shadowed sets）获取核心数据与边界数据的方法，将获取后的边界数据放入分类器训练。结果表明，与传统分类器相比，改进后的分类器不仅节约了训练时间，而且网络的泛化能力和分类识别准确度得到了有效提高。苏小红等[20]利用阴影集对模糊集的分析能力，提出一种基于阴影集的模糊支持向量机样本选择方法，将模糊集划分为3个子集后在可信任和不确定子集中进行样本选择，并且采用子空间样本选择和边界向量提取的方法选样。结果表明，该方法在保持SVM泛化能力的前提下有效降低了选样率和训练时间。张代俐等[21]通过模糊隶属度函数计算每个样本的隶属度，利用隶属度评估每个样本的重要程度，基于3种不同的模糊隶属度函数，分别提出了基于类中心距离、核目标对齐和中心核对齐模糊隶属度函数的SVM样本约简算法，相比传统SVM在几个分类指标都有提升。上述基于聚类的样本选择算法对聚类性能均有一定要求，当聚类效果在数据集上表现不理想时，会影响后续样本选择的数据点进而导致分类性能下降。
相比基于聚类的样本选择算法，基于几何分析的方法较为简单直观，该方法从训练数据的几何形状如凸包（convex hull）或几何距离进行分析，判断处于数据边界的样本点位于超平面附近并将这部分数据点保留作为训练样本。Chau等[22]提出的凸凹壳SVM（compressed convex hull SVM，CCHSVM）算法，即网格处理后，利用凸包寻找极值点，然后使用 Jarvis March方法来确定不可分点的凹（非凸）壳，最后将凸凹包的顶点应用于SVM训练。结果表明CCHSVM具有良好的分类精度，同时训练速度明显快于传统 SVM 分类器。Xu等[23]提出一种基于凸包向量和样本距离的SVM主动学习算法，通过样本距离和凸包向量可以主动选择对当前SVM分类器最有价值的样本，该算法比随机采样所需的标记样本明显减少，降低了学习中的样本标记成本。Zhang等[24]借鉴KNN分类算法的思想，利用样本的几何特性，提出了一种简单的SV预提取方法。只要K选择合适，就可以提取出重要SV的边界样本，从而减少训练样本，大大加快训练过程。李福祥等[25]提出了一种利用边界点训练支持向量机的新方法。首先计算每两个样本之间的欧氏距离，找出每个样本点的同类近邻集和异类近邻集，根据该样本点到两个集合的距离，判断其是否可能成为边界点。其次根据每个样本近邻集中同类样本数目的多少来删减样本集，该方法在具有较好分类精度的同时有效减少了训练样本的数量。但基于几何分析的样本选择方法也存在不足之处，即选取的数据点大多在簇与簇相邻边界，而在非相邻边界上的一部分点也会被选取作为SV构造决策面，且凸包在选取该类点时数量较少，会导致采用高斯核函数时构造的决策面不能很好的区分不同类别数据点，因此在训练样本保存率较低的情况下分类性能不佳。
针对SVM在进行分类任务时，训练数据集通常存在大量的冗余数据，这些冗余样本点对决策边界的构造并没有贡献且严重增加了分类器的训练负担的问题，以及根据现有基于聚类、几何分析方法存在的优点与不足，本文提出一种局部密度最小不确定性的SVM样本选择算法来搜索并提取出边界数据，首先，计算每个训练样本的K互近邻数量与高斯核密度，接着将K 互近邻数量与高斯核密度进行加和获得K局部密度并得出密度矩阵，然后使用局部密度不确定性平衡优化方法得到最优阈值对密度矩阵进行划分，将阈值以上的数据定义为中心数据即在簇中心周围的样本点进行删除，阈值以下的数据定义为边界数据，对其保留放入SVM训练。在人工数据集和UCI数据集上的实验结果表明，该方法有效地保留了簇与簇相邻与非相邻的边界数据，应用于高斯核或径向基函数核（radial basis function，RBF）SVM上能构建较好的决策面，并且在保存率较低的情况下还能够获得比不删除训练数据时更高的准确率，提高了SVM的分类性能。
1 支持向量机原理简述
给定含有m个数据点的二分类样本集D={（x1，y1），（x2，y2），···，（xm，ym）}，yi∈{-1，+1}，其中 x∈Rn，SVM分类器最基本的思想就是基于训练集D在样本空间中找到一个最优的分类超平面。对于线性可分的SVM，即构造一个线性方程为wTx+b=0的超平面，该超平面能最大化两类间的安全边界[26]，其中w为权重向量，b为偏置。最优超平面可以通过以下凸二次规划问题来解决：
(1)
式中:ξi为松弛变量用于惩罚错误分类，C为正则化参数用于控制训练和边界误差之间的权衡。通常上述凸二次规划问题可以通过如下拉格朗日乘子法进行求解，该问题的拉格朗日函数可以写为
(2)
式中α=（α1，α2，···，α3）。此时求L（w，b，α，ξ，μ）的极大值，即式（1）的极小值，令L（w，b，α，ξ，μ）对w，b，ξi偏导为零后将L（w，b，α，ξ，μ）中的w，b消去转化为wTx+b极值的对偶问题。通常情况下，原始样本空间可能不存在一个能正确划分两类样本的超平面，对于这样的问题，需要将样本从原始空间映射得到一个更高维的特征空间中，使样本在这个特征空间线性可分，此时对于非线性SVM来说构造的超平面对应模型表示为
(3)
式中：φ（x）为将x映射后的特征向量，w、b为模型参数，同时映射到特征空间之后的极值对偶问题的目标函数为
(4)
此时求解φ（xi）Tφ（xj）非常困难，因此需要引入一个核函数K（xi，xj）=φ（xi）Tφ（xj）来避免高维特征空间的内积计算，这样只需要通过函数K（·，·）就可以得出计算结果。引入核技巧后的非线性SVM最优分类超平面的决策函数可以表示为
(5)
高斯核也被称为径向基函数核（RBF）泛化性能较好，是目前使用最为广泛的核函数，本文的实验内容均在高斯（或RBF）核SVM上进行。通过式（1）~（5）显示出SVM的一个重要性质：训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量αi有关[27]。因此在训练前，尽可能将与支持向量相关的训练样本筛选出来后，再放入SVM分类器训练，这样可以减少训练数据量，在保证与未选择样本前的准确率相近的情况下，提高SVM的训练速度和分类效率。
2 局部密度的SVM样本选择算法
SVM在实际分类任务中，支持向量SV是训练过程用于确定分类超平面的关键点，直接影响到分类决策边界的位置和方向。通常来说，类中心附近的密集样本点不包含SV，而类外围的稀疏样本点更可能具有SV[18]。由于支持向量往往位于不同类别的边界附近，这些边界区域的局部密度较低，因此局部密度低的点更有可能成为支持向量，通过计算每个点的局部密度并选择低密度点可以更有效地找到潜在的支持向量，从而提高SVM的训练效率和分类精度。为了有效提取样本中低密度的边界数据，提出一种局部密度最小不确定性的方法进行样本选择，由K互近邻个数及其高斯核密度加和得到的K局部密度，生成密度矩阵后采用不确定性平衡优化方法确定阈值划分密度矩阵，将密集数据视为中心数据删除，不确定数据与稀疏数据视为边界数据选择并应用于SVM训练进行分类。
2.1 K互近邻及其高斯核密度估计
K局部密度由K互近邻及其高斯核密度估计组成，因此需要先引入有关K近邻（K-nearest neighbors，KNN）的相关概念。假设数据集D={x1，x2，···，xn}，对于任意数据点x来说，K近邻个数表示为
(6)
式中：d（x，xi）为点y和xi之间的欧氏距离，d（x，x（k））为点x到其第K近邻的欧氏距离。由K近邻个数可以得出K互近邻个数的定义，对于集合D中的两个任意两个数据点xi，y，如果xi是y的K近邻，同时y也是xi的K近邻，那么该两点就是K互近邻（K-mutual nearest neighbors，KMNN），KMNN的个数可以用集合表示为
(7)
式中KKNN（x）为点x的K个最近邻点。因为KKMNN（x）有效反映了样本点在同一簇中的紧密联系程度，所以在聚类中可以识别密集的簇，同时KKMNN（x）能够直观地将数据中的稀疏区域和密集区域等密度分布信息展现出来。因此，采用KKMNN（x）的思想在SVM样本选择中有助于将含有少量SV存在的高密度样本点进行删除，这类点往往对分类超平面的构造作用较小。
此外，核密度估计（kernel density estimation，KDE）是一种非参数技术，用于估计样本数据上概率密度函数，它是数据分析的重要工具[28]。本文将利用核密度估计来分析SVM训练样本中样本分布的疏密情况，其中核函数选择高斯核，高斯核具有理想的数学特性[29]，并且采用高斯核计算局部核密度可以保留数据点本身的分布特点。在数据点邻域有相同的KKMNN（x）时能够突出局部核密度最高的数据点[30]。这进一步提高了对密集样本点的检索，帮助本文将其认为是对构造SVM决策超平面不重要的点从而进行删除。高斯核函数以及高斯核密度估计（Gaussian kernel density estimation，GKDE）的数学表达式如下：
(8)
(9)
式中：||x||为x的范数，d为数据样本的维度，d（x，xi）为点x与第K个最近邻点xi的欧氏距离。最后将KMNN与GKDE进行相加得到新的K局部密度ρk（x）为
(10)
2.2 局部密度不确定性平衡优化方法
局部密度不确定性平衡方法参考了阴影集的思想。阴影集由模糊集诱导而来，目的是解决模糊集中使用具有精确数值的隶属度来描述模糊逻辑的缺陷问题，用于观察和解释不确定现象。在一个模糊集中，找到一个阈值α，将大于1-α部分的隶属度升高至1，并将小于α的隶属度降低至0，保持整体不确定性平衡便可以将传统隶属度函数转变为具有三值逻辑的阴影集[19]。其中求解最优阈值α是构造阴影集的关键，Pedrycz等[31]提出一种基于模糊平衡的优化方法，使隶属度的增减量达到整体平衡（即不确定性平衡），如在离散情况下使下式中V应达到最小值，此时的阈值视为最优阈值αopt。其中A（x）为在论域X中的模糊集诱导出的阴影集，映射关系为A:X→{0，1，[0，1]}。
(11)
(12)
在聚类分析中，局部密度可以用来描述一个点在某个区域内的密集程度，若样本点局部密度越高，则说明该样本点更有可能属于某一类，通过式（10）可以得出每个点的K局部密度ρk，将数据集D={x1，x2，···，xn}所有点的ρk输出后得出密度矩阵有ρk（x）=[ρk（x1），ρk（x2），···，ρk（xn）]，本文将密度矩阵归一化至[0，1]后类比于模糊集中的隶属度，进行构造阴影集的三值映射即φ: ，其中ρk为密度矩阵的集合，φ为密度矩阵的三值映射关系。为了确定三值划分的最优阈值，提出局部密度不确定性平衡优化方法如下式来选择阈值对密度矩阵进行划分:
(13)
定义1 （密集数据） 对于（x，ρk（x）），ρk（x）为样本点x的K局部密度，若φ（x，ρk（x））=1，即ρk（x）＞1-α，则称样本点x为密集数据。
定义2（稀疏数据） 对于（x，ρk（x）），ρk（x）为样本点x的K局部密度，若φ（x，ρk（x））=0，即ρk（x）＜α，则称样本点x为稀疏数据。
定义3（不确定数据） 对于（x，ρk（x）），ρk（x）为样本点x的K局部密度，若φ（x，ρk（x））=（0，1），即α≤ρk（x）≤1-α，则称样本点x为不确定数据。
上述定义和公式解释为，当求出最优阈值α后，大于1-α的部分定义为x完全处于某类的密集核心区，即映射φ将局部密度升至1的部分；处于[α，1-α]的部分定义为x不确定是否完全属于某类的区域，即映射φ处于[0，1]局部密度不变的部分；而小于α的部分定义为稀疏边界区，即映射φ将局部密度降至0的部分。式（13）表示的是经过映射φ后，尽可能使局部密度的改变量达到整体不确定平衡，即使映射在[0，1]的不确定性改变量V（α）达到最小时，取得最优阈值αopt。本文将密集数据视为对决策面影响较小的中心数据进行删除，将不确定数据以及稀疏数据视为边界数据予以保留。
2.3 算法步骤
局部密度最小不确定性的SVM样本选择算法步骤描述如下：
输入：算法参数K、T，训练集。
输出：边界数据训练后的SVM分类器模型。
Step1 将数据划分为训练集与测试集。
Step2 通过式（7）、（9）计算训练样本的KKMNN（x）与KGKDE（x）并做归一化处理。
Step3 根据式（10）对KKMNN（x）和KGKDE（x）加和并进行归一化后得到每个样本点ρk以及密度矩阵ρk（x）。
Step4 对ρk（x）进行不确定性平衡优化，根据式（12）、（13）得出最优阈值αopt。
Step5 由定义1~定义3将ρk（x）划分为3种数据后保留小于1-Tαopt的边界数据，其余样本点删除，其中控制参数T用来控制所选样本的数量。
Step6 将边界数据应用于SVM训练后得出分类模型在测试集上验证模型性能。
算法对边界数据进行样本选择的过程如图1所示，生成每类数据量100的二维随机数据，其中x，y轴表示人工数据集的两项特征做 [0，1]归一化处理。图1（a）为原始数据；图1（b）为计算出每个样本点K局部密度后归一化的密度矩阵ρk（x），即每个样本点{x1，x2，···，x200}对应的K局部密度ρk；图1（c）为求出最优阈值的过程，即式（13）中V（α）为最小值0时对应的αopt；图1（e）将ρk（x）中低于1-Tαopt视为边界数据予以保留，高于1-Tαopt视为中心数据进行删除；图1（f）为保留的边界数据放入高斯核函数SVM训练后得出的决策线。
图1算法可视化过程
Fig.1Visualization process of the algorithm
可以看出，使用本文提出的方法选出边界数据应用于高斯核SVM训练后的模型，与不做任何筛选样本的全部数据训练后得出的SVM模型（见图2）相似。原因是本方法提取簇边界数据包含了足够多对高斯核决策线有重要影响的SV，仅用了约原数据量1/4的训练样本即可生成与全数据训练相似的决策线。
图2全部数据训练的SVM模型
Fig.2SVM model trained on the full dataset
2.4 计算复杂度分析
对于n个训练样本，局部密度最小不确定性的SVM样本选择算法计算复杂度分析为：算法中计算每个训练样本欧氏距离的时间复杂度为O（n2）；计算训练样本KKMNN（x）、KGKDE（x）、计算ρk（x）以及局部密度不确定性平衡优化的时间复杂度均为O（n），因此本文样本选择算法的时间复杂度近似为O（n2）。相较于传统SVM的时间复杂度为O（n3），本文提出的算法降低了时间复杂度，提高了训练效率。
3 实验与分析
为了验证局部密度最小不确定性的SVM样本选择算法的可靠性，本文介绍提出算法与4种样本选择算法即KNN[24]、SS[19]、DR[18]、BPLSH[32]以及两种常用对比方法即不进行样本选择（ALL）与同等样本量进行随机选择[23]（Rand）的LIBSVM，各方法详见表1，在12个UCI数据集[33]（见表2）对比，测试本文方法与其他算法在UCI数据集的分类性能，以及介绍本文算法不同的K、T参数在UCI数据集对性能的影响。为了直观展示提出算法与其他对比方法提取的边界数据的区别，在构造的Normal数据集上进行实验，展示各个样本选择算法保存对决策面有关键影响样本的能力，在选择样本后的对原始数据进行测试后的实验结果见图3、表3。其中性能指标设置为准确率（accuracy rate，AR）、保存率（preservation rate，PR）可以分别表示为：
(14)
(15)
式中：A为准确率，P为保存率，NTE为测试集中的样本数目，NCTE为SVM正确分类测试集的个数，NTR为训练集的样本个数，NSTR为经过样本选择算法后的训练样本数[32]。实验环境为：Windows11操作系统，Intel（R）Core（TM）i7-12650H 2.30 GHz，16 GB内存，采用MATLAB R2022b编写。
表1对比方法介绍
Tab.1Introduction to comparison methods
表2UCI数据集
Tab.2UCI datasets
图3人工数据集上各样本选择算法得出的SVM模型
Fig.3SVM models obtained by various sample selection algorithms on the artificial dataset
表3人工数据集实验结果
Tab.3Experimental results on the artificial dataset
3.1 参数对算法性能的影响
本文介绍局部密度最小不确定性的SVM样本选择算法中参数K、T在UCI数据集中对准确率、保存率的影响。图4展示了提出算法对全数据进行样本选择后与未进行样本选择（ALL）在十折交叉验证的准确率对比，图5为参数对保存率的影响变化。其中LIBSVM为RBF核函数，HTRU2数据集参数c=100，其余数据集c=10，参数g为默认。K选取范围与训练样本数量有关，在Cancer等9个数据集上，K取2~50，Credit Card、HTRU2、Magic 3个数据集上K取训练样本数量10%左右的20个值，本文在UCI数据集中取T=0.25，T=1.00，T=1.15这3个值进行测试。
由图4、5可以看出，参数T对训练样本的保存率的影响较为关键，T=1.00时保存率大都处于50%以下，参数T增大保存率下降，反之保存率上升。并且在确定T后，K的增大对样本保存率的影响会逐渐变小。经实验得出T取较小时，准确率随K的变化较为稳定，在规模较小的数据集如Haberman，Bupa上，T=0.25的准确率变化明显比其他值更稳定。此外，K的变化对准确率也有很大影响，K不宜过大也不宜过小。其中有以下原因，在保存率一定的情况下，当样本量较小时K增大会使簇间相邻边界数据的局部密度上升，此类样本点可能被划分为中心数据删除，导致其中包含的支持向量减少进而构建的决策模型分类性能不佳；同理，面对样本量较大的数据集时K过小也会使簇间相邻边界数据的选取率下降。如在Haberman上， K过大会导致准确率出现大幅度下降；在Credit Card等3个大型数据集上，K过小准确率也处于整体较低水平，因此要尽量避免上述现象的发生。总的来说，无论在全数据进行十折交叉训练测试或者UCI数据集分为2∶1训练测试的情况下，准确率达到峰值时对应的K与训练样本量密切相关，根据经验判断最优K通常处于训练样本量的15%以内。
图4UCI数据集上不同参数对准确率的影响
Fig.4Impact of different parameters on accuracy rate on UCI datasets
图5UCI数据集上不同参数对保存率的影响
Fig.5Impact of different parameters on preservation rate on UCI datasets
3.2 UCI数据集
本文在12个UCI数据集上与6种方法（见表1）进行对比实验，以准确率（accuracy rate，AR）、保存率（preservation rate，PR）作为性能指标。实验过程将数据集分为2/3训练集与1/3测试集，每个数据集的各个算法运行10次后取均值进行对比测试。为减轻参数对结果的影响，在一定保存率的范围内，每次测试采用循环选取性能表现最好的参数作为结果进行记录见表4。此外，为进一步测试算法泛化性能，对全部数据样本选择后再进行十折交叉验证并循环10次取平均值，准确率与保存率平均值见表5。上述实验为避免不同特征维度之间的量纲可能会出现差异影响分类性能，实验中所有数据集的各项特征都进行了归一化处理，并对缺失值使用平均值代替。
表4UCI数据集实验结果
Tab.4Experimental results on UCI datasets
表5UCI数据集交叉验证结果
Tab.5Cross validation experiment results on UCI datasets
表5（续）
从表4、5可以看出，本文提出的样本选择算法在训练数据保存率较低的同时仍然有着高于未进行样本选择的准确率，而其他样本选择算法在多种数据集上删除大部分训练数据会无可避免地使准确率下降。在交叉验证的实验中，提出算法的准确率在多个数据集中都有较好的表现，表明局部密度最小不确定性方法保留的边界数据相比其他算法有着更高的泛化性能，应用于SVM训练后准确率得到了提高，其中有以下原因，阴影集方法对边界数据进行筛选时易受聚类准确率影响，在聚类准确率较低时，必须扩大边界数据的数量才能够有较高准确率。KNN方法筛选后的边界数据往往在簇与簇相邻的边界，而高斯核（或RBF核）SVM的支持向量在相邻边界与非相邻边界上都可能存在，这可能会出现过拟合而无法形成良好的决策面导致准确率下降。DR方法能保证较低的保存率，Fisher比有效的删除了每个聚类簇的核心数据，但处于K均值聚类后边界簇的核心数据也可能包含SV的训练样本，删除这类样本会导致准确率下降。BPLSH法保留了边界数据的同时也对核心数据进行保留，这在一定程度上提高了准确率并防止了过拟合现象，但也因此增加了许多非SV的冗余样本。而本文提出局部密度最小不确定性的SVM样本选择算法不受聚类的影响，能搜索并保留簇周围稀疏的边界样本点，其中的相邻边界数据是距离决策边界点较近的点，非相邻边界数据含有的部分SV防止出现过拟合现象，本文方法尽可能地将大部分对构建分类决策面有帮助的边界样本点保存下来，同时删除了大量处于类中心周围的冗余样本，提高了SVM的分类性能。
4 结论
1）通过将K互近邻个数与高斯核密度估计进行加和定义了一种K局部密度，该局部密度能很好地突出簇中的高密度区域，在三值映射后，利用不确定性平衡优化方法可以将数据高效划分为边界数据与中心数据。
2）对边界数据进行样本选择并应用于SVM训练后，以准确率和保存率作为性能指标，在UCI数据集上的实验表现优秀，大幅减少了冗余训练样本，在有效降低训练负担情况下提高了分类准确率。
3）相较于其他SVM样本选择方法，局部密度最小不确定性方法在对相邻边界数据选择的同时还保留了足够多的非相邻边界数据，这样在面对多种形状的簇时仍然可以保持边界特征，可以建立分类性能较好的SVM模型。
4）尽管局部密度最小不确定性方法容易取得高准确率的K、T，但分类性能达到最优时的算法参数仍然较难确定，因此未来的研究将结合不同数据集的分布特性，分析如何自适应求出最优参数的方法，进一步减少因主观因素导致算法性能下降的影响。
