基于局部离群因子的模糊支持向量机算法

Fuzzy support vector machine algorithm based on local outliers factor

摘要

模糊支持向量机是一种结合了支持向量机和模糊理论的分类算法。现有的模糊支持向量机算法可以在一定程度上克服噪声数据的影响，但存在成本敏感性，导致对数据的先验分布估计不准确。提出一种新的模糊支持向量机算法，该算法在设计样本的模糊隶属度函数时，利用采样点及其邻域密度的相似性构建的离群因子来更好地获取数据的分布信息。利用UCI数据集对优化后的模型进行验证，证明了其良好的性能。

Abstract

Fuzzy support vector machine is a classification algorithm that combines support vector machine and fuzzy theory.The existing fuzzy support vector machine algorithms can overcome the impact of noise data to some extent，but they have cost sensitivity，leading to inaccurate estimation of the prior distribution of data.A new fuzzy support vector machine algorithm was proposed.When designing the fuzzy membership function of samples，this algorithm better captures the distribution information of data by using the outlier factor constructed by the similarity of sampling points and their neighborhood density.The optimized model is validated using UCI datasets，which proves its good performance.

Graphical abstract

关键词

模糊支持向量机 / 邻域密度 / 离群因子 / 隶属度函数 / 不平衡数据

Key words

fuzzy support vector machine / neighborhood density / outlier factor / membership function / imbalanced dataset

支持向量机（support vector machine，SVM）是一种基于统计学的VC（Vapnik Chervonenkis）维理论和结构风险最小化原理的机器学习方法，能较好地解决小样本、非线性、局部极小等实际问题，在模式识别和分类问题上具有良好的泛化性能。然而SVM对于噪声和异常值较为敏感，在产生分类决策面时易受其影响。Lin等^［1］将模糊数学的概念引入到SVM中，提出了模糊支持向量机（fuzzy support vector machine，FSVM）算法，通过对每个样本赋予一个模糊隶属值，使得不同的样本在构造分类决策面时的贡献不同。FSVM是一种代价敏感算法，可以在一定程度上克服噪声数据的影响，但是该算法不能有效地处理不平衡数据上的分类问题，该算法的隶属度计算仅依赖于原始数据空间中的中心点和初始超平面，可以很好地识别规则的单密集区域数据。然而，由于过度依赖中心点的计算，该算法在面对不规则或多个数据密集型区域时性能较差，一些改进的FSVM算法被相继提出。Fu等^［2］提出了一种新的基于相对密度的直觉模糊支持向量机（relative density-based intuition- istic FSVM，RIFSVM）算法。利用相对密度来获取样本的先验信息，并通过引入直觉模糊评分函数进一步提高了模型对噪声或离群点的强识别能力，降低了类不平衡的影响。Kumar等^［3］提出了一种基于类内密度信息的模糊支持向量机（FSVM with within-class density information，FSVM-WD）算法，使用k近邻距离的概念来估计类内相对密度，样本的隶属度被定义为k近邻距离的倒数，具有较高的鲁棒性和容错性。Liu等^［4］提出了一种基于支持向量数据描述（support vector data description，SVDD）的模糊支持向量机算法（SVDD-based FSVM，FSVM-SVDD），噪声和异常点是由一个体积最小且包含最多样本的超球体来识别的，比SVM和FSVM具有更强的鲁棒性。Fan等^［5］提出了一种基于样本类确定性的模糊隶属度评价方法（entropy-based FSVM，EFSVM），利用熵来评价训练样本的类确定性，然后根据训练样本的类确定性来分配它们的模糊隶属度。与传统的 SVM 和 FSVM 相比，EFSVM 在不平衡数据集上能得到更灵活的决策面。Zhang等^［6］将信息熵与归一化的类中心距离相结合，得到模糊隶属函数，其中信息熵是基于k近邻（k-nearest neighbors，KNN）算法计算的。罗富财等^［7］将数据局部密度和数据特征距离引入模糊聚类，并将聚类得到的模糊隶属度作为模糊因子应用于模糊支持向量机，降低了人为选取模糊因子的主观性，将噪声点和孤立点对分类造成的影响降至最低。该方法使用KNN算法根据样本点之间的距离确定样本的局部密度。

上述算法采用KNN算法选择近邻点时，通常使用欧氏距离或曼哈顿距离等标准来度量样本点之间的距离，从而确定样本之间的紧密度。在样本分布均匀且类别界限清晰的情况下。这种方法在分类和回归问题中表现尤为出色。然而，KNN算法在处理密度分散不均的数据时可能会遇到一些困难。当数据中存在不同密度的类簇时，使用统一的距离度量标准可能无法准确反映样本之间的真实紧密度。此外，KNN算法对噪声和异常值也比较敏感，因为它们可能会改变样本点之间的距离分布。对此，本文结合了文献［8—13］的异常数据识别方法，在设计模糊隶属函数时利用采样点及其邻域密度的相似性构建的离群因子（local outlier factor，LOF）获取数据的分布特征。相比之下，LOF算法关注的是每个样本点相对于其近邻点的局部密度偏差。因此，即使在不同密度的类簇中，LOF算法也能有效地识别出异常值和离群点。

1 模糊支持向量机

在处理噪声和异常值时，SVM对每个样本同等对待，每个样本的误分类成本是相同的，使得决策表面有很大的偏差^［9］。FSVM在其目标函数中考虑了每个样本对一个类的模糊归属，通过引入模糊隶属度来区分不同样本的重要性。假设一个二分类数据集D=\{(x_{\mathrm{1}},y_{\mathrm{1}}),(x_{\mathrm{2}},y_{\mathrm{2}}),\cdots ,(x_n,y_n)\}，引入模糊隶属度，数据集被扩展为D=\{(x_{\mathrm{1}},y_{\mathrm{1}},s_{\mathrm{1}}),(x_{\mathrm{2}},y_{\mathrm{2}},s_{\mathrm{2}}),\cdots ,(x_n,y_n,s_n)\}，s_i为第i个样本的模糊隶属度；x_i\in {\mathbf{R}}^n；y_i \in\left\{-\mathrm{1,1}\right\}。与SVM不同，FSVM首先将输入空间中的样本点映射到高维特征空间中，然后通过求解二次规划问题得到分类超平面。其目标函数可以表示为

\underset{\omega ,b}{\mathrm{m}\mathrm{i}\mathrm{n}}\frac{\mathrm{1}}{\mathrm{2}}{‖\omega ‖}^{\mathrm{2}}+C{\displaystyle \sum _{i=\mathrm{1}}^n}{s}_i{\xi }_i（1）

式中：C>\mathrm{0}是惩罚参数；{\xi }_i为第i个样本点的松弛变量；n为样本数；s_i为样本点x_i的模糊隶属值。

约束条件为

y_i(\omega \cdot \mathit{\phi }(x_i)+b)\ge \mathrm{1}-{\xi }_i,{\xi }_i\ge \mathrm{0},i=\mathrm{1,2},\cdots ,n（2）

式中：y_i为第i个样本的标签；\mathit{\phi }(x_i)为将输入空间中的数据映射到特征空间中的向量；b为偏差。

为求解式（1），通过拉格朗日函数求其对偶规划为

\mathrm{m}\mathrm{a}\mathrm{x}\omega (\alpha )={\displaystyle \sum _{i=\mathrm{1}}^n}{\alpha }_i-\frac{\mathrm{1}}{\mathrm{2}}{\displaystyle \sum _{i=\mathrm{1}}^n}{\displaystyle \sum _{j=\mathrm{1}}^n}{\alpha }_i{\alpha }_j{y}_i{y}_{j}k(x_i,x_j)（3）

约束条件为

{\displaystyle \sum _{i=\mathrm{1}}^n}{\alpha }_i{y}_i=\mathrm{0,0}\le {\alpha }_i\le C{s}_i,i=\mathrm{1,2},\cdots ,n（4）

在对偶问题中，变量{\alpha }_i的上界约束随着模糊因子s_i变化。所以模糊隶属度s_i成为决定FSVM性能好坏的关键。

2 基于类中心的模糊隶属函数的局限性

本文在一个人工数据集上分析了基于类中心距离的模糊隶属度计算方法的局限性。图1a是一个外部密集、内部稀疏的二维人工数据集。按照Lin等^［1］的方法，外围样本将会被赋予较小的模糊隶属值，结果如图1b所示。显然，基于样本到类中心距离的方法无法准确描述数据的分布特征，密集区域的样本很可能被分配一个相对较小的权重。对于实际情况而言，同一类别的距离类中心距离相同的两个样本，一个在高密度区域，一个在相对稀疏的区域，显然前者更重要。

现有的改进模糊支持向量机算法虽然考虑到样本周围的紧密度（文献［2—7］），但通常是根据样本点之间的距离确定的，这在处理密度分散不均的数据时，可能无法准确反映样本之间的真实紧密程度。此外，噪声和异常值的存在可能会改变样本点之间的距离分布。为了更好地解决这些问题，本文将样本的离群因子作为设计模糊隶属函数的依据。

3 局部离群因子的定义

3.1 实例的k距离邻域

假设x_i\in D，对于\forall k\in Z，点x_i的k距离记为k-distance（x_i ），它表示点x_i到第k个近邻点的距离，但不包括点x_i。对于x_j\in D，x_j与x_i的距离记为d(x_i,x_j)。给定点x_i的k距离，则点x_i的k距离邻域包括与点x_i的距离不超过k距离的所有点，定义为k-\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{e}(x_i)，简记为N_k(x_i)，计算如下。

（5）

式中：点x_j称为点x_i的k最近邻^［14-16］。

3.2 局部可达密度

点x_i的局部可达密度被定义为

\mathrm{l}\mathrm{r}{\mathrm{d}}_k(x_i)=\left(\frac{\left|N_k(x_i)\right|}{\sum _{x_j\in N_k(x_i)}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{c}\mathrm{h}-\mathrm{d}\mathrm{i}\mathrm{s}{\mathrm{t}}_k(x_i,x_j)}\right)（6）

式中： \mathrm{r}\mathrm{e}\mathrm{a}\mathrm{c}\mathrm{h}-\mathrm{d}\mathrm{i}\mathrm{s}{\mathrm{t}}_k(x_i,x_j)=\mathrm{m}\mathrm{a}\mathrm{x}\left\{\right.k-distance（x_j ）d(x_i,x_j)\}为x_i、 x_j两点间的可达距离，偏离程度较大的点的可达距离之和一般大于偏离程度较小的点的可达距离之和，那么局部可达密度要小于偏离程度较小的点的局部可达密度。\mathrm{l}\mathrm{r}{\mathrm{d}}_k(x_i)值说明了点所处的局部空间区域的密度情况^［14-16］。

3.3 局部离群因子

点x_i的LOF定义为

\mathrm{L}\mathrm{O}{\mathrm{F}}_k(x_i)=\frac{\sum _{x_j\in N_k(x_i)}\frac{\mathrm{l}\mathrm{r}{\mathrm{d}}_k(x_j)}{\mathrm{l}\mathrm{r}{\mathrm{d}}_k(x_i)}}{\left|N_k(x_i)\right|}（7）

式（7）表示相邻实例N_k(x_i)的局部可达密度与实例x_i的局部可达密度之比的平均值。如果这个比率更接近于1，那么它表示在x_i的邻域内的实例密度相似，且x_i可能与该邻域属于同一聚类。如果比值小于1，表示x_i密度大于其邻域点密度，x_i密度大；如果该比值大于1，表示x_i的密度小于其邻近实例的密度，则x_i更有可能是一个离群值。不难看出，若点x_i的偏离程度较大，则它的局部可达密度\mathrm{l}\mathrm{r}{\mathrm{d}}_k(x_i)较小，而它的N_k(x_i)内的点由于处在同一个群组中，那么它们的局部可达密度\mathrm{l}\mathrm{r}{\mathrm{d}}_k(x_i)相对较小，则\mathrm{l}\mathrm{r}{\mathrm{d}}_k(x_j)/\mathrm{l}\mathrm{r}{\mathrm{d}}_k(x_i)的值较大，最终点x_i的LOF值就越大，它离周围的实例就越远^［14-16］。

3.4 基于离群因子的模糊隶属函数设计

基于样本的离群因子，本文的模糊隶属函数定义为

s_i^{+}=\mathrm{1},i=\mathrm{1,2},\cdots ,p（8）

s_i^{-}=\frac{\mathrm{1}}{\mathrm{1}+\mathrm{e}\mathrm{x}\mathrm{p}(\mathrm{L}\mathrm{O}{\mathrm{F}}_i^{-})},i=p+\mathrm{1},p+\mathrm{2},\cdots ,n（9）

式中：\mathrm{L}\mathrm{O}{\mathrm{F}}_i^{-}为第i个负类样本的局部离群因子。

为了探究式（9）的合理性，使用式（9）计算并标记出与图1b相同的30个实例的模糊隶属值，结果如图2所示。在图2中，很明显，外围实例和内部实例的模糊隶属值并不像图1b所示的相隔甚远。相反，它遵循实例的分布特征，将较小的模糊值分配给分布在稀疏区域的样本点，将较大的模糊值分配给分布在密集区域的样本点。从图2可以看出，边缘上的实例没有被误判为噪声，并给出了合理的模糊值。从图2可以看出，对于这种非正态分布的数据集，本文的模糊隶属值计算方法是比较合理的。

4 数据验证

为了进一步分析和评估本文算法对分类任务的贡献是否仅限于特定数据集，将研究范围扩大。本文采用UCI数据库中的多个二分类数据集进行初步测试，UCI数据集及其相关属性，如表1所示。Libsvm-weight-3.20软件包用来训练FSVM模型，为每个样本分配不同的权值。所有数值实验均在\mathrm{2.50}\mathrm{G}\mathrm{H}\mathrm{z}/\mathrm{8.0}\mathrm{G}\mathrm{B}的计算机上利用Matlab2023b软件实现。

为了有效地评估模型的分类性能，采取以下评估指标：AUC、G-mean和F1值。这些评估指标都是基于一个混淆矩阵，如表2所示。

Precision=\frac{TP}{TP+FP}（10）

Recacall=\frac{TP}{TP+FN}（11）

G-\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{n}=\sqrt[]{\mathrm{P}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}·\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{l}}（12）

F\mathrm{1}=\frac{\mathrm{2}·\mathrm{P}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}·\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{l}}{\mathrm{P}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}+\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{l}}（13）

实验中所有SVM和FSVM算法均采用RBF核函数，使用网格搜索法对惩罚因子C和核参数\gamma进行选择，C的选择范围是[{\mathrm{2}}^{\mathrm{0}},{\mathrm{2}}^{\mathrm{15}}]，\gamma的选择范围是[{\mathrm{2}}^{-\mathrm{15}},{\mathrm{2}}^{\mathrm{0}}]。在计算LOF值时，本文根据数据集的大小指定了参数k的取值范围： k=\sqrt[]{N}，N为样本数。本文算法与5种模糊支持向量机算法的比较结果如表3—9所示。

由表3—9的最终结果可以看出，本文算法分类性能提升显著，在AUC、G-mean值和F1值评估指标下均取得了较好的结果。从表3可以看出，FSVM算法的表现比较弱，这是因为数据分布有可能不是标准的球形分布，也可能是异常值的影响。无论是哪一种情况，很显然，这样基于样本到类中心距离来设计的模糊隶属函数会出现问题，样本与类别之间的归属信息无法得到准确的表述。本文算法考虑了样本的局部离群因子（实例x_i的局部可达密度与相邻实例N_k(x_i)的局部可达密度之比的平均值）。如果LOF值小于1，则表示x_i的密度大于其邻域点的密度，并且x_i是致密的；如果LOF值大于1，表明x_i的密度小于其相邻实例的密度，则x_i越有可能是离群值。这一过程可以更好地获取数据的分布信息并对模糊隶属函数作出适当的修正，减小了仅使用样本与类中心距离作为模糊隶属函数时对数据集几何形状的依赖，数据集是非球形分布时的分类精度也获得了提升，同时也降低了异常值或噪声点对分类超平面的影响。此外，根据表3—9中的F1值，本文算法在7个数据集中表现出绝对的优势，F1值越高，对少数类的分类准确率就越高，这说明其他7种算法在少数类分类中的性能并不高，这可能是因为这些算法得到的分离超平面仍然向少数类倾斜，导致少数类的分类准确率较低。从最终结果来看，本文算法分类性能不仅优于标准的FSVM算法，而且优于现有的一些改进FSVM算法。基于离群因子的模糊隶属函数设计思路使得每个样本对最终的决策超平面有着相对合理的影响，有效降低了异常数据对最优分类超平面的影响，提高了模型的分类性能。

5 结论

本文算法在设计样本的模糊隶属函数时，利用采样点及其邻域密度的相似性构建的离群因子来获取数据的分布特征。由于LOF算法关注的是局部密度偏差，因此它对异常值和离群点更加敏感。这意味着即使在一个复杂的数据集中，LOF算法也能准确地识别出那些与周围样本点密度差异较大的点。此外，LOF算法不需要假设数据分布是均匀的或具有特定的形状。因此，它可以应用于各种类型的数据集，包括那些具有不同密度类簇的数据集。因此，在处理密度分散不均或存在异常值的数据集时，本文算法更具优越性。

参考文献

[1] Lin C F， Wang S D.Fuzzy support vector machines［J］.IEEE Transactions on Neural Networks，2002，13（2）：464-471.

[2] Fu C， Zhou S S， Zhang D，et al.Relative density-based intuitionistic fuzzy SVM for class imbalance learning［J］.Entropy，2022，25（1）：34.

[3] Kumar A， Singh S K， Saxena S，et al.CoMHisP：a novel feature extractor for histopathological image classification based on fuzzy SVM with within-class relative density［J］.IEEE Transactions on Fuzzy Systems，2021，29（1）：103-117.

[4] Liu W， Ci L L， Liu L P.A new method of fuzzy support vector machine algorithm for intrusion detection［J］.Applied Sciences，2020，10（3）：1065.

[5] Fan Q， Wang Z， Li D D，et al.Entropy-based fuzzy support vector machine for imbalanced datasets［J］.Knowledge-Based Systems，2017，115（3）：87-99.

[6] Zhang X Y， Guo Y L， Li F L，et al.Geometric mean maximum FSVMI model and its application in carotid artery stenosis risk prediction［J］.Chinese Journal of Electronics，2021，30（5）：824-832.

[7] 罗富财，吴飞，陈倩，等.基于机器学习的无线传感器网络入侵检测算法［J］.哈尔滨工程大学学报，2020，41（3）：433-440.

[8] 徐志博，刘永生，户盼茹.结合离群因子和K-means++聚类改进的点云去噪算法［J］.信息技术与信息化，2023，15（3）：21-24.

[9] Wang K F， An J， Yu Z B，et al.Kernel local outlier factor-based fuzzy support vector machine for imbalanced classification［J］.Concurrency and Computation：Practice and Experience，2021，33（13）：62-77.

[10] 凌莉，程张玉，邹承明.融合孤立森林和局部离群因子的离群点检测方法［J］.计算机应用与软件，2022，39（12）：278-283.

[11] She C Y， Zeng S H， Wang Q，et al.Adaptive fuzzy C-means clustering integrated with local outlier factor［J］.Intelligent Data Analysis，2022，26（6）：1507-1521.

[12] 杨娜，付颖煜，李天昊.基于局部离群因子的数据异常识别方法及其在古建结构监测中的应用［J］.建筑结构学报，2022，43（10）：68-75.

[13] Kim M， Jung S， Kim B，et al.Fault detection method via k-nearest neighbor normalization and weight local outlier factor for circulating fluidized bed boiler with multimode process［J］.Energies，2022，15（17）：6146.

[14] Breunig M M， Kriegel H P， Ng R T，et al.LOF：identifying density-based local outliers［C］//Proceedings of the 2000 ACM SIGMOD international conference on Management of data.Dallas：ACM，2000：93-104.

[15] 张付志，魏莎. 基于局部密度的用户概貌攻击检测算法［J］.小型微型计算机系统，2013，34（4）：850-855.

[16] 周玉，朱文豪，孙红玉.一种基于目标函数的局部离群点检测方法［J］.东北大学学报（自然科学版），2022，43（10）：1405-1412.

基金资助

国家重点研发计划子项(2019YFC1903901-01)