·132· 智能系统学报 第4卷 支持向量数据描述(SVDD)是由Tax和Duin于 %∈{+1，·1}}能够被超平面w·x)+b=0分 1999年提出的一种一类分类方法s1,其理论源于 类.优化超平面的求解问题为 SM目前，SVDD已在故障诊断、语音识别、图像识 别等领域得到应用6.与SM寻求最优超平面不 mn中)=方wW+C 同的是，VDD的出发点是寻求一个包容目标样本 sty[(w·x)+b]≥1-5， (1) 数据的最小容量超球体，将这种基于一类分类的分 5,≥0 类思想引入多类分类可望解决SM在处理无标签 这是一个二次规问题，根据KKT定理，最优解为 数据多类分类问题上存在的难题.为此，提出了一种 其拉格朗日函数的鞍点： 基于支持向量数据描述的无标签数据多类分类方 L(w,b.a) =wP+C5-a,6w+ 法，并将其用于区域物流中心城市分类评价.该方法 采用主成分分析作数据预处理，提取输入数据的统 B,5 2) 计特征值，得到主成分特征指标输入到SVDD分类 器进行多类聚类分类.实证分析也验证了该方法的 a 店 =C,a,-B=0 有效性和可行性 a,yw·x,+b)-1+5,1=0, (3 1主成分分析和支持向量机 a,B.5,≥0， 11主成分分析原理 B,5,=0 主成分分析(PCA)是一种统计维数压缩方 得 法1？给定一个数据集X w-ayx. X=(x,i=1,2,,mj=1,2,,p ∑ya,=0 4) 1)将原始数据进行标准化处理：=一 ~聊 var(xi) C=a,+B. 式中=arW士化 根据式4)重构式2，得到其对偶二次规划问题， maxo (a) 2计算相关矩阵：R=(6=5·S 2+ sta,≥0， (5) S,=十∑哪弹，避=公m聊 n-1与 ∑ya,=0 根据KKT定理，对于大多数的样本，a,=Q对 /n 应a,≠的样本为支持向量)由此可见，由支持向 3)令IR-入1=0，求解相关矩阵R的特征根 量决定的分类面和由全体样本集决定的分类面是等 入，且使得入，≥2≥…≥入，其对应的特征向量为 价的 u,得到主成分：y=u上 对于线性不可分问题，依据统计学习理论可知， 如果选用适当的核函数，将低维的输入空间数据通 4计算各主成分方差贡献率：9=入/公人：和 过核函数映射到高维特征空间，输入空间线性不可 累计方差贡献率：E=∑9 分问题在特征空间将转化为线性可分问题.满足 T Mercer2条件的对称函数都可以作为核函数， 当E≥0（通常取80%）时n的最小整数作为 引入核函数K(x,x)代替式(5)中向量的内积 m的值，即主成分的个数为m: (x,x,得 12支持向量机算法 对于两类问题，假定样本集{(x,y),x∈R, maxo(a) 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved. http://www.cnki.net支持向量数据描述 (SVDD)是由 Tax和 Duin于 1999年提出的一种一类分类方法 [ 5 ] ,其理论源于 SVM. 目前 , SVDD已在故障诊断、语音识别、图像识 别等领域得到应用 [ 629 ] . 与 SVM寻求最优超平面不 同的是 , SVDD的出发点是寻求一个包容目标样本 数据的最小容量超球体 ,将这种基于一类分类的分 类思想引入多类分类可望解决 SVM 在处理无标签 数据多类分类问题上存在的难题. 为此 ,提出了一种 基于支持向量数据描述的无标签数据多类分类方 法 ,并将其用于区域物流中心城市分类评价. 该方法 采用主成分分析作数据预处理 ,提取输入数据的统 计特征值 ,得到主成分特征指标输入到 SVDD分类 器进行多类聚类分类. 实证分析也验证了该方法的 有效性和可行性. 1 主成分分析和支持向量机 1. 1 主成分分析原理 主成分分析 ( PCA ) 是一种统计维数压缩方 法 [ 10 ] . 给定一个数据集 X: X = ( xij ) , i = 1, 2, …, n; j = 1, 2, …, p. 1) 将原始数据进行标准化处理: zij = xij - 珋xj var( xj ) . 式中:珋xj = ∑ n i =1 xij / n, var( xj ) = 1 n - 1∑ n i =1 ( xij - 珋xj ) 2 . 2)计算相关矩阵 : R = ( rij ) p×p , rij = Sij Sii ·Sjj , Sij = 1 n - 1∑ n k =1 (zk i - 珋zi ) (zk j - 珋zj ) ,珋zi = ∑ n k =1 zk i / n,珋zj = ∑ n k =1 zk j / n. 3) 令 | R - λ| = 0,求解相关矩阵 R的特征根 λj且使得λ1 ≥λ2 ≥ … ≥λp ,其对应的特征向量为 uj ,得到主成分 : yj = u∑ p j=1 xj . 4) 计算各主成分方差贡献率 : ej =λj /∑ p k =1 λk 和 累计方差贡献率 : E = ∑ m j=1 ej . 当 E≥θ(θ通常取 80% )时 n的最小整数作为 m 的值 ,即主成分的个数为 m. 1. 2 支持向量机算法 对于两类问题 ,假定样本集 { ( xi , yi ) , xi ∈R l , yi ∈{ + 1, - 1} } 能够被超平面 (w ·x) + b = 0分 类. 优化超平面的求解问题为 m in< (w ) = 1 2 (w·w ) + C∑ n i =1 ξi , s. t. yi [ (w·xi ) + b ] ≥ 1 - ξi , (1) ξi ≥ 0. 这是一个二次规划问题 ,根据 KKT定理 ,最优解为 其拉格朗日函数的鞍点 : L (w, b,α) = 1 2 ‖w‖ 2 + C∑ n i =1 ξi - ∑ n i =1 αi ( yi (w·xi + b) +ξi - 1) - ∑ n i =1 βiξi . (2) 即 5L 5ξi = C - αi - βi = 0. αi [ yi (w·xi + bi ) - 1 +ξi ] = 0, (3) αi ,βi ,ξi ≥ 0, βiξi = 0. 得 w = ∑ n i =1 αi yi xi , ∑ n i =1 yiαi = 0, (4) C =αi +βi . 根据式 (4)重构式 (2) ,得到其对偶二次规划问题 : maxQ (α) = - 1 2 ∑ n i =1 ∑ n j =1 αiαj yi yj ( xi , xj ) + ∑ n i =1 αi , s. t. αi ≥ 0, (5) ∑ n i =1 yiαi = 0. 根据 KKT定理 ,对于大多数的样本 ,αi = 0. 对 应αi ≠0的样本为支持向量 [ 1 ] . 由此可见 ,由支持向 量决定的分类面和由全体样本集决定的分类面是等 价的. 对于线性不可分问题 ,依据统计学习理论可知 , 如果选用适当的核函数 ,将低维的输入空间数据通 过核函数映射到高维特征空间 ,输入空间线性不可 分问题在特征空间将转化为线性可分问题. 满足 Mercer条件的对称函数都可以作为核函数. 引入核函数 K ( xi , xj )代替式 (5)中向量的内积 ( xi , xj ) ,得 maxQ (α) = - 1 2 ∑ n i =1 ∑ n j=1 · ·132· 智 能 系 统 学 报 第 4卷