推荐星级:
- 1
- 2
- 3
- 4
- 5
基于马氏抽样的SVM非平衡数据分类算法的泛化性能研究
资料介绍
本文将样本为独立同分布的情形减弱为一致遍历马氏链的情形去研究了非平衡数据分类算法的泛化性能,提出了基于马氏抽样的SVM非平衡数据分类算法、基于马氏抽样的EDSVM非平衡数据分类算法和基于马氏抽样的SVM-WKNN非平衡数据分类算法.并用UCI数据库中的10个实际不平衡数据集进行数值实验,实验结果表明基于马氏抽样的上述三种算法的错分率均比基于随机抽样的对应算法的错分率要低,且上述三种算法中,基于马氏抽样的SVM-WKNN非平衡数据分类算法的泛化性能最好.
部分文件列表
文件名 | 大小 |
基于马氏抽样的SVM非平衡数据分类算法的泛化性能研究.pdf | 3M |
部分页面预览
(完整内容请下载后查看)11
Vol. 46 No. 11
Nov. 2018
第
期
电
子
学
报
2018
11
ACTA ELECTRONICA SINICA
年
月
SVM
基于马氏抽样的
非平衡
数据分类算法的泛化性能研究
,
徐 婕 贺美美
(
,
湖北大学计算机与信息工程学院 湖北武汉
430062)
:
摘
要
本文将样本为独立同分布的情形减弱为一致遍历马氏链的情形去研究了非平衡数据分类算法的泛化
SVM EDSVM
非平衡数据分类算法和基于马氏抽
,
、
性能 提出了基于马氏抽样的
非平衡数据分类算法 基于马氏抽样的
SVM-WKNN
. UCI
非平衡数据分类算法 并用
10 ,
数据库中的 个实际不平衡数据集进行数值实验 实验结果表明基
样的
, ,
于马氏抽样的上述三种算法的错分率均比基于随机抽样的对应算法的错分率要低 且上述三种算法中 基于马氏抽样
SVM-WKNN
.
的
非平衡数据分类算法的泛化性能最好
:
;
; k ;
关键词
中图分类号
URL: http: / /www. ejournal. org. cn
马氏抽样 支持向量机
近邻算法 非平衡数据
:
TP181
:
A
: 0372-2112 ( 2018) 11-2660-11
DOI: 10. 3969 /j. issn. 0372-2112. 2018. 11. 013
文献标识码
文章编号
电子学报
Research on the Generalization Performance of SVM Imbalanced Data
Classification Algorithm Based on Markov Sampling
XU Jie,HE Mei-mei
( School of Computer Science and Information Engineering,Hubei University,Wuhan,Hubei,430062,China)
Abstract: This paper changes the assumption that samples are independent and identically distributed to that samples
are uniformly ergodic Markov chains,which make it convenient for us to study the generalization performance of the imbal-
anced data classification algorithm,and SVM imbalanced data classification algorithm based on Markov sampling,EDSVM
imbalanced data classification algorithm based on Markov sampling and SVM-WKNN imbalanced data classification algo-
rithm based on Markov sampling are proposed. The numerical experiments of ten actual imbalanced datasets in the UCI data-
base show that the misclassification rate of the above algorithm based on Markov sampling is lower than that of the corre-
sponding algorithm based on random sampling,and the above three algorithms,SVM-WKNN imbalanced data classification
algorithm based on Markov sampling has the best generalization performance.
Key words: Markov sampling; support vector machine; k-nearest neighbor; imbalanced data
,
种方法是从数据层面的角度出发 主要 方法为 重抽
1
引言
[9]
, ,
其基本思想是既然样本是不平衡的 那么可以通
样
,
不管是在学术界还是工业界 对于不平衡数据的
, ;
过某种抽样策略 让样本相对均衡一些 第二种方法是
[1]
.
研究已经吸引 了 越 来 越 多 学 者 的 关 注
不 平 衡 数
,
从算法的角度出发 考虑不同错分类情况下的代价差
[2]
[10]
,
指的是数据集中样本类别是不均衡的 对于标准
据
, ,
从而对算法进行优化 使算法在对不平衡数据分
异
[11]
, ,
的二分类问题来说 样本数量多的类称为多数类 样本
.
类时也能有较好的效果 近年来
,Japkowicz
等人 证明
. ,
数量少的类称为少数类 在实际应用中 不平衡数据出
、
了在后向传播神经网络 决策树
C4. 5、SVM
几类算法
[3]
[4]
[12]
,
现在许多领域 如医疗诊断
、
、
信用卡欺
文本分类
,SVM
.
对非平衡数据的影响较为不敏感 李蓉等人
中
[5]
[6]
[7]
、
、 .
机械故障诊断 等 目前
,
诈检测
网络攻击识别
KSVM , k SVM
算法 通过结合 近邻算法和
提出了一种
[8]
:
,
各自的优点 在分类阶段计算待测样本与两类支持向
解决非平衡数据分类问题常用的方法有两种
第一
: 2017-09-04;
: 2018-02-05; :
责任编辑 蓝红杰
收稿日期
修回日期
:
基金项目 国家自然科学基金
( No. 61370002,No. 61403132,No. 61772011)
2661
11
: SVM
婕 基于马氏抽样的 非平衡数据分类算法的泛化性能研究
第
期
徐
N
*
*
, , SVM
量代表点的距离 如果距离大于给定阈值 则用 来
y ( x ·x ) ,
其中
i
a .
是拉格朗日系数 若样本线
i
∑
α
i = 1
i
i
j
,
分类 否则以每类支持向量代表点作为训练样本的
k
近
, ,
性不可分 可以使用核函数 将输入空间映射到高维特
[13]
.
邻算法来分类 王超学等人 提出了一种改进型算
,
征空间 从而使得原本线性不可分的样本可以在高维
—EDSVM( Euclidean Distance NN & Support Vector
法
1
2
,
特征空间可分 此时所求目标函数为
: min
w
‖ ‖
+ C
2
Machine) ,
该算 法 对 距 离 分 类 超 平 面 较 远 的 点 使 用
N
,
ξ 使得
i
y ( w·x + b) 1 -
i
,
ξ ξ
i
0,i = 1,2,…N,
∑
SVM
,
进行分类 对于距离分类超平面较近的点则以全
i = 1
i
i
,C
其中 ξ 为松弛变量 为惩罚因子
i
.
k ,
部的支持向量作为训练样本的 近邻算法进行分类 提
SVM
通过
训练模型获得的支持向量决定了最终的
.
高了样本分类的正确率
以上算法都是建立在样本是独立同分布的假设
, ,“ ”
分类超平面 这不但可以抓住关键样本 剔除 大量冗
,
余样本 而且表明了
SVM
“ ” .
具有较好 的 鲁棒 性 但
,
下 然而样本是独立同分布的假设无论是在理论上还
SVM
对位于两个类别的边界区域或重叠区域的样本点
,
是在实际应用中都是非常强的 并且很多机器学习应
,
进行分类时 会存在一定的分类错误 即
, SVM
算法的分
,
用中产生的数据并不服从独立同分布 于是将独立同
.
类错误一般都发生在最优分类超平面附近
2. 2 k
近邻算法
,
分布的情形减弱为非独立的情形 如一致遍历马氏链
[14]
, .
等 已有一些学者做了相关研究 如
: Xu
等人 证明了
k
( k-Nearest Neighbor, KNN)
简称 是一种
近邻算法
SVM
基于马氏抽样的
SVM
算法的泛化性能比基于随机抽样
[15]
, .
基于距离的算法 它没有明显的前期训练过程 具体过
. Zou
的
算法的泛化性能要好
等人 提出了基于
[16]
: ,
程为 每来一个未知的样本点 就在此样本点附近找
k
. Smale
马氏抽样的正则化回归算法
等人 将马氏抽样
, ,
个与之最近的点进行投票 统计投票结果 某类数量最
.
运用到了在线学习中 本文考虑到样本是独立同分布
, .
多 就把这个测试样本判定为该类
,
的假设在很多现实问题中不能满足 且随机抽样的效
[13]
KNN
,
,
,
率比较低 所以引入了新的马氏抽样方法来研究基于
属于懒惰学习方法
因为要扫描全部训练样本并计算距离所以计算量会较
KNN ,
方法主要靠周围有限的邻近样本 而不是
若测试样本比较大时
SVM
一致遍历马氏链样本的
非平衡数据分类算法的泛
.
,
化性能 给出了三种基于马氏抽样的非平衡数据分类
大 由于
靠判别类域的方法来确定所属类别 因此对于类域的
,KNN
方法较其他
,
, :
算法 分别是 基于马氏抽样的
SVM
非平衡数据类算
非平衡数据分类算法和基
、
法 基于马氏抽样的
EDSVM
交叉或重叠较多的待分样本集来说
.
SVM-WKNN
,
非平衡数据分类算法 三种
方法更为适合
于马氏抽样的
,
2. 3 EDSVM
算法都是先通过马氏抽样获取算法所需的训练样本
算法
[13]
.
再选用不同的算法对数据进行分类 基于基准库数据
EDSVM ( Euclidean Distance NN & Support Vector
,
集实验结果表明 上述基于马氏抽样分类算法的泛化
Machine) SVM KNN
是一种改进的 和
组合的不平衡数
SVM
,
性能总是优于基于随机抽样分类算法的泛化性能 并
, :
据分类算法 主要思想是 当待测样本与
最优分类
,
且将上述三种算法进行泛化性能的对比后发现 基于
, SVM
超平面的距离大于一定值时 用
;
进行分类 当待测
SVM-WKNN
SVM
,
最优分类超平面的距离小于一定值时 以
马氏抽样的
非平衡数据分类算法的泛化性
样本离
.
,
所有的支持向量作为测试样本的近邻样本 用
KNN
能最好
进
.
行分类
2
相关概念介绍
EDSVM
算法利用了支持向量能够代表训练样本集
EDSVM
2. 1
支持向量机
, .
的含义 提高了分类器的分类精度 但
没有考
[17]
( Support Vector Machine,
简称
SVM)
支持向量机
KNN
,KNN
对非平衡数据带来的影响
虑到用
对每个样
,
是一种应用广泛的分类算法 通过使结构风险最小化
, ,
本都赋予了相同的权重 当样本分布不均衡时 可能会
,
,
来提高泛化能力 实现经验风险和置信范围的最小化
其基本模型定义为特征空间上间隔最大的线性分类
Z = { z = ( x ,y ) ,z =
,
导致测试数据被分到样本容量较大的那一类 造成错
.
误分类的情况
2. 4
.
器 给定特征空间上的训练集
1
1
1
2
马尔可夫链
经典的机器学习建立在独立同分布的假设下 然
而实际应用中很多模型产生的样本是自然涌现的而非
n
( x ,y ) ,…z = ( x ,y ) } ,
其中
N
x
R ,y
{ + 1,-
∈
∈
,
2
2
N
N
i
i
1} ,i = 1,2,…N.
: f( x) = sign
相应的分类决策函数为
( wx + b) ,
其中
:
,
独立同分布 而马尔可夫链更符合机器学习中数据的
- 1, f( x) < 0
, ,
分布情况 本文的马尔可夫链为一致遍历马氏链 下面
sign( f( x) ) =
.
{
+ 1, f( x)
0
.
是一致遍历马氏链的概念
( Z,S)
N
*
: w =
y x ,b = y -
α
i = 1 i
构造拉格朗日函数可以求得
∑
,
是一个可测空间 马尔可夫链包括一个随
记
i
i
i
全部评论(0)