Fuzzy Support Vector Machines Chun-Fu Lin and Sheng-De Wang
Abstract—A support vector machine(SVM)learns the decision surface from two distinct class of the input points.In many appli-cations,each input point may not be fully assigned to one of the two class.In this paper,we apply a fuzzy membership to each input point and reformulate the SVMs such that different input points can make different constributions to the learning of deci-sion surface.We call the propod method fuzzy SVMs(FSVMs). Index Terms—Classification,fuzzy membership,quadratic pro-gramming,support vector machines(SVMs).
I.I NTRODUCTION
T HE theory of support vector machines(SVMs)is a new classification technique and has drawn much attention on this topic in recent years[1]–[5].The theory of SVM is bad on the idea of structural risk minimization(SRM)[3].In many ap-plications,SVM has been shown to provide higher performance than traditional learning machines[1]and has been introduced as powerful tools for solving classification problems.
An SVM first maps the input points into a high-dimensional feature space and finds a parating hyperplane that maximizes the margin between two class in this space.Maximizing the margin is a q
uadratic programming(QP)problem and can be solved from its dual problem by introducing Lagrangian multi-pliers.Without any knowledge of the mapping,the SVM finds the optimal hyperplane by using the dot product functions in feature space that are called kernels.The solution of the optimal hyperplane can be written as a combination of a few input points that are called support vectors.
There are more and more applications using the SVM tech-niques.However,in many applications,some input points may not be exactly assigned to one of the two class.Some are more important to be fully assinged to one class so that SVM can perate the points more correctly.Some data points cor-rupted by nois are less meaningful and the machine should better to discard them.SVM lacks this kind of ability.
In this paper,we apply a fuzzy membership to each input point of SVM and reformulate SVM into fuzzy SVM(FSVM) such that different input points can make different constribu-tions to the learning of decision surface.The propod method enhances the SVM in reducing the effect of outliers and nois in data points.FSVM is suitable for applications in which data points have unmodeled characteristics.
The rest of this paper is organized as follows.A brief review of the theory of SVM will be described in Section II.The FSVM
Manuscript received January25,2001;revid August27,2001.
C.-F.Lin is with the Department of Electrical Engineering,National Taiwan University,Taiwan(e-mail:u.edu.tw).
S.-D.Wang is with the Department of Electrical Engineering,National Taiwan University,Taiwan(e-mail:u.edu.tw).
Publisher Item Identifier S1045-9227(02)01807-6.will be derived in Section III.Three experiments are prented in Section IV.Some concluding remarks are given in Section V.
II.SVMs
In this ction we briefly review the basis of the theory of SVM in classification problems[2]–[4].
Suppo we are given a
t
The optimal hyperplane problem is then regraded as the so-lution to the
problem
(6)
where can be regarded as a
regularization parameter.This is the only free parameter in the
SVM formulation.Tuning this parameter can make balance be-
tween margin maximization and classification violation.Detail
discussions can be found in[4],[6].
Searching the optimal hyperplane in(6)is a QP problem,
which can be solved by constructing a Lagrangian and trans-
formed into the
dual
(7)
where is the vector of nonnegative Lagrange
形容爱读书的成语multipliers associated with the constraints(5).
The Kuhn–Tucker theorem plays an important role in the
theory of SVM.According to this theorem,the
solution
(8)
in
(8)are tho for which the constraints(5)are satisfied with the
equality sign.The
point
and
is classified correctly and clearly
away the decision margin.
To construct the optimal
hyperplane,it follows
that
,the computation
of problem(7)and(11)is impossible.There is a good property
of SVM that it is not necessary to know
about
called kernel that can compute the dot
product of the data points in feature
space
(14)
and the decision function
is
(15)
III.FSVMs
In this ction,we make a detail description about the idea
and formulations of FSVMs.
A.Fuzzy Property of Input
SVM is a powerful tool for solving classification problems
[1],but there are still some limitataions of this theory.From the
training t(1)and formulations discusd above,each training
point belongs to either one class or the other.For each class,we
can easily check that all training points of this class are treated
中国铁道大学uniformly in the theory of SVM.
In many real-world applications,the effects of the training
points are different.It is often that some training points are more
important than others in the classificaiton problem.We would
左眼角有痣
require that the meaningful training points must be classified
correctly and would not care about some training points like
nois whether or not they are misclassified.
That is,each training point no more exactly belongs to one
of the two class.It may90%belong to one class and10%
be meaningless,and it may20%belong to one class and80%
be meaningless.In other words,there is a fuzzy
membership
can be regarded as the attitude of
meaningless.We extend the concept of SVM with fuzzy mem-
bership and make it an FSVM.
B.Reformulate SVM Suppo we are given a
t
,and sufficient
small denote the corresponding feature
space vector with a
mapping.
Since the fuzzy
membership is the attitude of the corre-
sponding
point
(17)
where
(19)
(22)
and the Kuhn–Tucker conditions are defined
as
(23)
is misclassi-
fied.An important difference between SVM and FSVM is that
the points with the same value of
in SVM controls the tradeoff be-
tween the maximization of margin and the amount of misclassi-
河道清淤施工方案fications.A
larger
makes SVM
ignore more training points and get wider margin.
In FSVM,we can
t
(25)
钱学森学院
where
,and make the first
point
.If we want to make fuzzy membership
be a linear function of the time,we can
lect
(26)
By applying the boundary conditions,we can
新生儿缺氧
get
Fig.1.The result of SVM learning for data with time property. By applying the boundary conditions,we can
get
(30)
where
(31)
such
that
1,it may belongs to this class with lower accuracy or really
belongs to another class.For this purpo,we can lect the
fuzzy membership as a function of respective class.
Suppo we are given a quence of training
做巧克力
points
if
Fig.2.The result of FSVM learning for data with time property.
Fig.3shows the result of the SVM and Fig.4shows the result of FSVM by
tting
is indicated as square.In Fig.3,the SVM finds the
optimal hyperplane with errors appearing in each class.In Fig.4,
we apply different fuzzy memberships to different class,the
ppt项目符号FSVM finds the optimal hyperplane with errors appearing only
in one class.We can easily check that the FSVM classify the
class of cross with high accuracy and the class of square with
low accuracy,while the SVM does not.
C.U Class Center to Reduce the Effects of Outliers
Many rearch results have shown that the SVM is very n-
sitive to nois and outliners[8],[9].The FSVM can also apply
to reduce to effects of outliers.We propo a model by tting
the fuzzy membership as a function of the distance between the
point and its class center.This tting of the membership could
not be the best way to solve the problem of outliers.We just pro-
po a way to solve this problem.It may be better to choo a dif-
ferent model of fuzzy membership function in different training
t.
Suppo we are given a quence of training
points
1
(37)
and the radius of
class
if
(39)
where
is indicated as square.In Fig.5,the
SVM finds the optimal hyperplane with the effect of outliers,
for example,a square at( 2.2).In
Fig.6,the distance of the above two outliers to its corresponding
mean is equal to the radius.Since the fuzzy membership is a
function of the mean and radius of each class,the two points
are regarded as less important in FSVM training such that there
is a big difference between the hyperplanes found by SVM and
FSVM.
