文档介绍：数据分类算法基本原理数据分类是数据挖掘中的一个重要题目。数据分类是指在已有分类的训练数据的基础上, 根据某种原理, 经过训练形成一个分类器; 然后使用分类器判断没有分类的数据的类别。注意,数据都是以向量形式出现的,如<, , , …>。支持向量机是一种基于分类边界的方法。其基本原理是(以二维数据为例) :如果训练数据分布在二维平面上的点, 它们按照其分类聚集在不同的区域。基于分类边界的分类算法的目标是, 通过训练, 找到这些分类之间的边界( 直线的――称为线性划分, 曲线的――称为非线性划分)。对于多维数据(如 N维) ,可以将它们视为 N 维空间中的点, 而分类边界就是 N 维空间中的面,称为超面(超面比 N 维空间少一维) 。线性分类器使用超平面类型的边界,非线性分类器使用超曲面。线性划分如下图: 可以根据新的数据相对于分类边界的位置来判断其分类。注意, 我们一般首先讨论二分类问题,然后再拓展到多分类问题。以下主要介绍二分类问题。 4、支持向量机分类的基本原理支持向量机是基于线性划分的。但是可以想象, 并非所有数据都可以线性划分。如二维空间中的两个类别的点可能需要一条曲线来划分它们的边界。支持向量机的原理是将低维空间中的点映射到高维空间中, 使它们成为线性可分的。再使用线性划分的原理来判断分类边界。在高维空间中, 它是一种线性划分, 而在原有的数据空间中, 它是一种非线性划分。但是讨论支持向量机的算法时, 并不是讨论如何定义低维到高维空间的映射算法( 该算法隐含在其“核函数”中) ,而是从最优化问题(寻找某个目标的最优解) 的角度来考虑的。 5、最优化问题我们解决一个问题时, 如果将该问题表示为一个函数 f(x) , 最优化问题就是求该函数的极小值。通过高等数学知识可以知道, 如果该函数连续可导, 就可以通过求导, 计算导数= 0 的点, 来求出其极值。但现实问题中, 如果 f(x) 不是连续可导的, 就不能用这种方法了。最优化问题就是讨论这种情况。求最优解的问题可以分为两种:(1 )无约束最优问题;(2 )有约束最优问题。无约束最优算法可以表达为: min ( ) x f x 。可以用数值计算方法中的牛顿法、最速梯度下降法等,通过多次循环,求得一次近似的最优解。有约束问题,一般表达为: min ( ) . . ( ) 0 {1, 2, , } nxi f x x E s t x i m ?????? ???? 6、线性可分的二分类问题线性可分的二分类问题是指: 原数据可以用一条直线( 如果数据只有二维) 或一个超平面划分开。用一个多维空间中的超平面将数据分隔为两个类有三种基本方法: (1) 平方最近点法:用两类点中最近的两点连线的平分线作为分类线(面) (2) 最大间隔法:求分类面,使分类边界的间隔最大。分类边界是值从分类面分别向两个类的点平移,直到遇到第一个数据点。两个类的分类边界的距离就是分类间隔。分类平面表示为: ( ) 0 w x b ? ??。注意, x 是多维向量。分类间隔的倒数为: 212 w 。所以该最优化问题表达为: 2,1 min , 2 . . (( ) ) 1) 1, 1, , w b i i w s t y w