给出了一类线性分类算法的数学描述,在求解分类问题的平分最近点法与最大间隔法的基础上。将线性分类问题转化为一类无约束不可微优化问题。设计了一种求解该问题的不可微优化算法,并证明了算法的收敛性。初步的数值例子表明该算法是有效的,且具有简单实用的特点。

第2卷第4 8期 20 0 8年 1 2月

西

安

科

技

大学学

报

Vo . 8 No 4 12 . De . 0o c2 8

J R A F X N UN V R I Y O C E E A D E HN L G 0U N L O IA I E ST F S I NC N T C O O Y

文章编号：17 9 1 (0 8 0 0 1 o 6 2— 35 20 )4— 86一 4

一

种求解分类问题的优化算法 王雪峰 (西安科技大学理学院，陕西西安 7 0 5 ) 10 4

摘

要：给出了一类线性分类算法的数学描述，求解分类问题的平分最近点法与最大间隔法的在

基础上。线性分类问题转化为一类无约束不可微优化问题。设计了一种求解该问题的不可微将

优化算法，并证明了算法的收敛性。初步的数值例子表明该算法是有效的，且具有简单实用的特 点。

关键词：线性分类；不可微优化；算法中图分类号：02 4 2 文献标识码： A

分类问题虽然不是新问题，但随着计算机的普及应用，特别是机器学习和数据挖掘的迅速发展赋予了它们新的意义。一般的分类问题都可利用优化算法来求解，文中把线性分类问题转化为一种不可微规划问题，给出了求解该问题的不可微优化算法，明了算法的收敛性，证并进行了数值实验，数值结果可行 有效。

1线性分类的数学描述 Magrn是在机器学习中使用最优化方法的先驱，他最早提出了最大间隔法的思想。后来， nai a是

V pi等人才在比 an k较严密的理论基础上，发展了一系列与核技术相联系的各种支持向量机 实例。

。文献

[] 7介绍了求解分类问题的平分最近点法和最大间隔法，中在此基础上给出了线性分类算法及其计算文 首先介绍几个基本概念，虑 n维空间上的分类问题，考它包含 n个指标和 Z个样本点。记这 Z样本个

点的集合为 T={,。,,,} XXY其中∈ ( Y)… ( Y)∈( ), X=R是输入指标变量， 或称输入，或称模式，分量其 称为特征，属性，或或输入指标； Y∈Y={, 1是输出指标， 1一}或称输出，=1…,这 z样本点组成的， Z .个集合称为训练集，这里的问题是，对任意给定的一个新的模式根据训练集，断它所对应的输出 Y是 1推 还是一1。

可以用数学

语言描述分类问题。 根据给定的训练集 T={,,,,}∈( ),中∈X:R, ( Y )… (2Y) XXY其 Y∈Y={,} i, 1一1,=1 …

,

寻找 X=R上的一个实值函数 g )以便用决策函数 )= g ( ( )推断任一模式相对应的 Y (, sn g x )

值。 若训练集可以用直线正确分开，这类问题称为线性可分问题，其确切定义为：对于训练集 T (。={, Y)…,,f} XY其中∈X=, 1, (l))∈( ),, Y∈y={,} 1…,若存在 t∈R,∈R和正数， l一1,, Z . o“b

使得对所有使 Y=的下标 i t ) b; 1有( +≥而对所有使 Y=一的下标 i∞ ) b一， o f 1,有( +≤占则称 训练集线性可分。同时也称相应的分类问题是线性可分的。

+收稿日期： 0 7—1 20 2—1 7

责任编辑：郭西山

基金项目：国家自然科学基金项目(0 7 0 3 63 4 6 )作者简介：王雪峰 (9 3男， 16一)陕西合阳人，副教授，主要从事数学的教学与研究