李睿峰等：基于空间近邻关系的非平衡数据重采样算法 863. KEY WORDS imbalanced data;neighbor relationship;resample;local density;classification 非平衡数据的分类问题已经成为当今许多数 免的会导致噪声点增加并损失数据原有信息，从 据密集型应用中一个关键的研究方向，例如信用 而降低分类精度，因此合理的过采样和欠采样 卡欺诈数据冈、网络入侵)、金融工程、生物医学 方法是重采样方法的核心.为了对数据集做有效 数据分析)和设备故障检测等.这类应用中的 的均衡化处理，本文提出了一种基于样本空间近 少数类样本通常蕴含重要的信息，是数据分析的 邻关系的重采样(Resampling based on neighbour 重要目标，其已成为数据挖掘研究的热点之一仞 Relationship,RBNR)方法.本方法首先根据数据集 例如在设备故障检测应用中，不平衡的测试数据 中少数类样本的空间近邻关系进行安全级别评估， 广泛存在，通常正常样本的数据量要远远大于故 根据安全级别有指导的进行SMOTE升采样；然后 障样本图由此导致使用传统的故障诊断方法训练 对多数类样本依据其空间近邻关系计算局部密度， 所得的结果分类器对正常样本产生很高的检测 从而对多数类样本密集区域进行降采样处理.采 率，对故障样本的检测和隔离效果却很差，而故障 用十折交叉验证的方式产生训练集和测试集，在 样本的检测率在故障诊断领域中更有意义，也更 对训练集进行重采样之后，以核超限学习机(Kernel 为重要 extreme learning machine,KELM)2作为分类器进 目前，机器学习和数据挖掘领域针对不平衡 行训练，并在测试集上进行了验证 数据集的处理思路例主要有两大类：改进算法0 以适应非平衡数据集，或者对数据集进行重构山 1基本算法与相关定义 以适应现有的分类算法.改进算法是指在算法层 1.1核超限学习机 面进行改进以适应非平衡学习问题，如代价敏感 学习、支持向量机(Support vector machine, 给定训练集D={(xy,其中x∈Rd表示 训练样本，d∈R表示x;的维数，n为样本总数； SVM)、集成学习)等.通过修改算法中的代价敏 y:=y,…ymJT为与x;对应的理想输出向量，其中 感信息以适应数据不平衡，但也面临着一些问题， m∈R表示y的维数.此时，ELM模型定义为 如修改算法后如何避免分类性能恶化，多类分类 问题的代价敏感信息确定困难等数据集重构 腰+c∑s 也称为重采样方法，它在不修改分类算法的情况 i=1 下修改训练数据集的大小，可容易地应用于任何 s.t.h(xB=y-5i,i=1,2,…,n (1) 分类算法.重采样方法利用少数类样本过采样和 其中，Il和2分别表示矩阵的F范数和向量的 多数类样本欠采样两种手段阿，人为调整实例数 2范数；h(x)=[h(x),…,hu(x]表示隐层神经元对 量来平衡数据集的分布.欠采样主要包括随机欠 输入样本x的映射向量；B=B1,…,T是模型输 抽样6、单边选择忉、近邻清理和基于欧氏距 出权重向量；L代表隐层神经元个数；=[， 离的随机欠抽样9等方法，过采样主要有随机插 2,…,mJT表示对应于x的训练误差；C是正则化 值、先验复制和合成少数类过采样技术P0-别 参数，并且C∈R+ Synthetic minority oversampling technique,SMOTE) 令Y=y1,…,ynJT,基于KKT优化条件求解式 等方法.由于单独采用欠采样方法可能导致样本 (1)的优化问题，可得输出权重： 信息丢失，单独采用过采样方法可能导致分类器 B=HT(C-I+HHT)Y (2) 出现增加时间开销、过拟合现象等问题，于是人们 较多采用混合采样的非均衡数据处理方法).包括 其中，隐层输出矩阵H=[h(x)T,…,h(xn)TT,I表示 谷琼等22提出的一种基于SMOTE-Clustering的混 单位矩阵 合采样算法；冯宏伟等m提出的基于“变异系数” 最终，对于输入z,ELM的输出为： 的边界混合采样方法(Boundary mixed sampling, (3) BMS);陶新民等2]提出的基于随机欠采样 =e=ahr+aHy (Random under--sampling,.RU)与SMOTE相结合的 应用Mercer条件定义核矩阵2=HHT,i,)= SVM算法等 h(x)h(x)T=k(x,x)表示中第i行第j列的元素 由于人为地增加样本或者减少样本都不可避 应用基于核函数的隐式映射代替传统的显式特征KEY WORDS    imbalanced data；neighbor relationship；resample；local density；classification 非平衡数据的分类问题已经成为当今许多数 据密集型应用中一个关键的研究方向[1] ，例如信用 卡欺诈数据[2]、网络入侵[3]、金融工程[4]、生物医学 数据分析[5] 和设备故障检测[6] 等. 这类应用中的 少数类样本通常蕴含重要的信息，是数据分析的 重要目标，其已成为数据挖掘研究的热点之一[7] . 例如在设备故障检测应用中，不平衡的测试数据 广泛存在，通常正常样本的数据量要远远大于故 障样本[8] . 由此导致使用传统的故障诊断方法训练 所得的结果分类器对正常样本产生很高的检测 率，对故障样本的检测和隔离效果却很差，而故障 样本的检测率在故障诊断领域中更有意义，也更 为重要. 目前，机器学习和数据挖掘领域针对不平衡 数据集的处理思路[9] 主要有两大类：改进算法[10] 以适应非平衡数据集，或者对数据集进行重构[1] 以适应现有的分类算法. 改进算法是指在算法层 面进行改进以适应非平衡学习问题，如代价敏感 学 习 [11]、 支 持 向 量 机 [12] （ Support vector machine， SVM）、集成学习[13] 等. 通过修改算法中的代价敏 感信息以适应数据不平衡，但也面临着一些问题， 如修改算法后如何避免分类性能恶化，多类分类 问题的代价敏感信息确定困难等[14] . 数据集重构 也称为重采样方法，它在不修改分类算法的情况 下修改训练数据集的大小，可容易地应用于任何 分类算法. 重采样方法利用少数类样本过采样和 多数类样本欠采样两种手段[15] ，人为调整实例数 量来平衡数据集的分布. 欠采样主要包括随机欠 抽样[16]、单边选择[17]、近邻清理[18] 和基于欧氏距 离的随机欠抽样[19] 等方法，过采样主要有随机插 值、先验复制[14] 和合成少数类过采样技术[20−21] （Synthetic minority oversampling technique，SMOTE） 等方法. 由于单独采用欠采样方法可能导致样本 信息丢失，单独采用过采样方法可能导致分类器 出现增加时间开销、过拟合现象等问题，于是人们 较多采用混合采样的非均衡数据处理方法[7] . 包括 谷琼等[22] 提出的一种基于 SMOTE-Clustering 的混 合采样算法；冯宏伟等[7] 提出的基于“变异系数” 的边界混合采样方法 （ Boundary mixed sampling， BMS） ； 陶 新 民 等 [23] 提 出 的 基 于 随 机 欠 采 样 （Random under-sampling，RU）与 SMOTE 相结合的 SVM 算法等. 由于人为地增加样本或者减少样本都不可避 免的会导致噪声点增加并损失数据原有信息，从 而降低分类精度，因此合理的过采样和欠采样 方法是重采样方法的核心. 为了对数据集做有效 的均衡化处理，本文提出了一种基于样本空间近 邻关系的重采样 （ Resampling based on neighbour Relationship，RBNR）方法. 本方法首先根据数据集 中少数类样本的空间近邻关系进行安全级别评估[24] ， 根据安全级别有指导的进行 SMOTE 升采样；然后 对多数类样本依据其空间近邻关系计算局部密度[7] ， 从而对多数类样本密集区域进行降采样处理. 采 用十折交叉验证的方式产生训练集和测试集，在 对训练集进行重采样之后，以核超限学习机（Kernel extreme learning machine，KELM） [25] 作为分类器进 行训练，并在测试集上进行了验证. 1    基本算法与相关定义 1.1    核超限学习机 DTr = {(xi , yi)} n i=1 xi ∈ R d d ∈ R xi n yi = [yi1,··· , yim] T xi m ∈ R yi 给定训练集 ，其中 表示 训练样本 ， 表 示 的维数 ， 为样本总数 ； 为与 对应的理想输出向量，其中 表示 的维数. 此时，ELM 模型定义为 min β,ξ 1 2 ∥β∥ 2 F +C 1 2 ∑n i=1 ∥ξi∥ 2 2 , s.t. h(xi)β = yi −ξi ,i = 1,2,··· ,n （1） || · ||F || · ||2 h(xi) = [h1(xi),··· ,hL(xi)] xi β = [β1,··· , βL] T ξi = [ξi1, ξi2,··· , ξim] T xi C C ∈ R + 其中， 和 分别表示矩阵的 F 范数和向量的 2 范数； 表示隐层神经元对 输入样本 的映射向量； 是模型输 出权重向量 ； L 代表隐层神经元个数 ； 表示对应于 的训练误差； 是正则化 参数，并且 . Y = [y1,··· , yn] 令 T ，基于 KKT 优化条件求解式 （1）的优化问题，可得输出权重： β = H T ( C −1 I+ HHT )−1 Y （2） H = [h(x1) T ,··· , h(xn) T ] T 其中，隐层输出矩阵 ，I 表示 单位矩阵. 最终，对于输入 z，ELM 的输出为： f(z) = h(z)β=h(z)H T ( I C + HH T )−1 Y （3） Ω = HHT δ(i, j) = h(xi)· h(xj) T = k(xi , xj) Ω 应用 Mercer 条件定义核矩阵 ， 表示 中第 i 行第 j 列的元素. 应用基于核函数的隐式映射代替传统的显式特征 李睿峰等： 基于空间近邻关系的非平衡数据重采样算法 · 863 ·