第4卷第2期 智能系统学报 Vol 4 Ng 2 2009年4月 CAA I Transactions on Intelligent System s Apr 2009 基于支持向量数据描述的无标签数据多类分类 朱帮助'，林健2 (1五邑大学系统科学与技术研究所，广东江门529020,2北京航空航天大学经济管理学院，北京100083) 摘要：为解决支持向量机(SM)在处理无标签数据多类分类上的难题，提出了一种基于支持向量数据描述 (DD)的无标签数据多类分类算法.该方法只需要建立一个分类模型就可以实现多类聚类分类.首先采用主成分 分析作数据预处理，提取输入数据的统计特征值，得到主成分特征指标输入到SDD分类器进行多类聚类分类.以珠 三角地区物流中心城市分类评价为研究对象，实证结果表明，采用主成分分析降低了数据维度，有效浓缩了评估信 息，DD分类器很好地区分了各中心城市，实现了多类分类的目的. 关键词：多类分类；无标签数据；支持向量数据描述；主成分分析 中图分类号：TP18文献标识码：A文章编号：1673-4785(2009)02-013106 Multi-class classification a lgor ithm for unlabeled da ta using SVDD ZHU Bang-zhu,L N Jian' (1.Institute of System Science and Technobgy,Wuyi University,Jiangen 529020,China;2 School of Econom ics and Manage- ment,Beijing University of Aeronautics and A stronautics,Beijing 100083,China) A bstract:Support vectormachines SVM)may encounter problem s in dealing with multi-class classification of un- labeled data So we suggested a new multi-class classification algorithm based on support vector data description (SVDD)in this paper Compared with othermulti-class classification algorithms,the proposed algorithm only nee- ded one classifier to complete the multi-class clustering classification W ith thismethod,principal component anal- ysis (PCA)was used to preprocess original data o extract statistically characteristic values inputting these values into an SVDD classifier comp leted multi-class clustering classification Taking nine cities in the Pearl River delta area as an example,an evaluation wasmade of the devebpmental levels of the logistics of these cities The test re- sults showed that data dimensions were reduced by using principal component analysis,and the evaluated infoma- tion was effectively concentrated by adopting feature extraction with PCA.Moreover,the SVDD classifier could dis- tinguish the central cities very well,so it can be used as an effective app roach for multi-class classification of unla- beled data Keywords:multi-class classification,unlabeled data;support vector data description;princ p le component analysis 多类分类问题是目前模式识别领域中的一个热一法、决策树法、Weson法等2].但这些方法通常 点与难点课题.基于统计学习理论的支持向量机 需要构造多个两类分类器，算法计算复杂度较高；此 (SM)从新的角度有效地解决了两类分类问题.在外，这些方法无一例外都是有监督学习方法，需要为 此基础上，一些学者开展了多类分类问题研究，提出每个样本附上类别标签.但在实际应用（如区域物 了一些具体的实现方法，代表性的有一对多法、一对 流中心城市分类评价)中广泛存在着大量的无标签 收稿日期：200807-12 数据，上述要求常常很难得以满足)，因此在一定 基金项目：国家自然科学基金资助项目(70471074) 程度上降低了这些方法的实用价值」 通信作者：朱帮助.E1mai让wp办z@126com 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 4卷第 2期 智 能 系 统 学 报 Vol. 4 №. 2 2009年 4月 CAA I Transactions on Intelligent System s Ap r. 2009 基于支持向量数据描述的无标签数据多类分类 朱帮助 1 , 林 健 2 (1. 五邑大学 系统科学与技术研究所 ,广东 江门 529020; 2. 北京航空航天大学 经济管理学院 ,北京 100083) 摘 要 :为解决支持向量机 ( SVM )在处理无标签数据多类分类上的难题 ,提出了一种基于支持向量数据描述 ( SVDD)的无标签数据多类分类算法. 该方法只需要建立一个分类模型就可以实现多类聚类分类. 首先采用主成分 分析作数据预处理 ,提取输入数据的统计特征值 ,得到主成分特征指标输入到 SVDD分类器进行多类聚类分类. 以珠 三角地区物流中心城市分类评价为研究对象 ,实证结果表明 ,采用主成分分析降低了数据维度 ,有效浓缩了评估信 息 , SVDD分类器很好地区分了各中心城市 ,实现了多类分类的目的. 关键词 :多类分类 ;无标签数据 ;支持向量数据描述 ;主成分分析 中图分类号 : TP18 文献标识码 : A 文章编号 : 167324785 (2009) 0220131206 M ulti2class classification algor ithm for unlabeled data using SVDD ZHU Bang2zhu 1 , L IN Jian 2 (1. Institute of System Science and Technology, W uyi University, Jiangmen 529020, China; 2. School of Economics and Manage2 ment, Beijing University of Aeronautics and A stronautics, Beijing 100083, China) Abstract:Support vectormachines (SVM) may encounter p roblem s in dealing with multi2class classification of un2 labeled data. So we suggested a new multi2class classification algorithm based on support vector data descrip tion (SVDD) in this paper. Compared with othermulti2class classification algorithm s, the p roposed algorithm only nee2 ded one classifier to comp lete the multi2class clustering classification. W ith thismethod, p rincipal component anal2 ysis (PCA) was used to p rep rocess original data to extract statistically characteristic values; inputting these values into an SVDD classifier comp leted multi2class clustering classification. Taking nine cities in the Pearl River delta area as an examp le, an evaluation wasmade of the developmental levels of the logistics of these cities. The test re2 sults showed that data dimensions were reduced by using p rincipal component analysis, and the evaluated informa2 tion was effectively concentrated by adop ting feature extraction with PCA. Moreover, the SVDD classifier could dis2 tinguish the central cities very well, so it can be used as an effective app roach formulti2class classification of unla2 beled data. Keywords:multi2class classification; unlabeled data; support vector data descrip tion; p rincip le component analysis 收稿日期 : 2008207212. 基金项目 :国家自然科学基金资助项目 (70471074). 通信作者 :朱帮助. E2mail: wpzbz@126. com. 多类分类问题是目前模式识别领域中的一个热 点与难点课题. 基于统计学习理论 [ 1 ]的支持向量机 (SVM)从新的角度有效地解决了两类分类问题. 在 此基础上 ,一些学者开展了多类分类问题研究 ,提出 了一些具体的实现方法 ,代表性的有一对多法、一对 一法、决策树法、W eston法等 [ 223 ] . 但这些方法通常 需要构造多个两类分类器 ,算法计算复杂度较高 ;此 外 ,这些方法无一例外都是有监督学习方法 ,需要为 每个样本附上类别标签. 但在实际应用 (如区域物 流中心城市分类评价 )中广泛存在着大量的无标签 数据 ,上述要求常常很难得以满足 [ 4 ] ,因此在一定 程度上降低了这些方法的实用价值
·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卷
第2期 朱帮助，等：基于支持向量数据描述的无标签数据多类分类 ·133· 根据统计学习理论，只要核函数满足Mercer条 a,ayyK(x,)+】 件，它就对应某一变换空间中(x)中的内积)因 sta,≥0. 6) 此，在最优分类面中采用适当的内积核函数就可以 2a,=0 实现从低维向高维空间的映射，从而实现某一低维 空间的非线性问题向高维特征空间的线性问题转 决策函数为 换，而计算复杂度并没有增加.于是，式(12)问题转 f()=(+b1 7) 换为求最优解： 任选一支持向量x,计算出b: max∑a,K(x,x)- ∑a,a,K(x,x,(13) lk(+b1-1 (8 st∑a,=l, 2支持向量数据描述多类分类 0≤a,≤C 求解优化问题(13)可以得到a,的值，通常大部 21原理 分a,将为0，不为0的a,所对应的样本称为支持向 假定一个包含个目标样本的无标签数据x, 量支持向量体现在超球体的边界上.因此，超球 i=L,,x∈R支持向量数据描述(SVDD)的 体的半径由支持向量到球心的距离决定.即对应于 基本思想是寻求一个最小容积的超球体，使所有的 0R2,z在边界外 (16) 2,=1 22算例分析 a=∑a,x, (11) 利用SVDD对无标签数据进行多类聚类分类， 通过选择合适的核函数以及与之对应的参数，可以 C-a,-Y,=0 根据式11)重构式9)，得到其对偶二次规划问题： 获得比较理想的分类边界 考虑如图1所示的两维样本分布，采用SVDD ma2,xx)·F2a,9 进行一类分类所得结果如图1(a),通过调整高斯径 向基核函数中参数σ值的大小，来比较所取得的多 s t P,=1.0≤a,≤C (12) 类分类效果，如图1(b)~(d)所示 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved. http://www.cnki.net
αiαj yi yjK ( xi , xj ) + ∑ n i =1 αi , s. t. αi ≥ 0, (6) ∑ n i =1 yiαi = 0. 决策函数为 f ( x) = sgn[ ∑ n i =1 αi yi K ( xi , x) + b ]. (7) 任选一支持向量 xi ,计算出 b: yi [ ∑ b i =1 αi yi K ( xi , x) + b ] = 1. (8) 2 支持向量数据描述多类分类 2. 1 原 理 假定一个包含 l个目标样本的无标签数据 { xi , i = 1, …, l}, xi ∈R d . 支持向量数据描述 (SVDD )的 基本思想是寻求一个最小容积的超球体 ,使所有的 (或绝大多数的 )目标样本都包含在该球体内. 即设 法找一个以 a为中心 ,以 R 为半径的能够包含所有 样本点的最小超球体. m in F (R, a,ξi ) = R 2 + C∑ l i =1 ξi , s. t. ( xi - a ) T ( xi - a ) ≤ R 2 +ξi , (9) ξi ≥ 0. 这也是一个二次优化问题,可以构造出拉格朗日函数: m in F (R, a,ξi ) = R 2 + C∑ l i =1 ξi - ∑ l i =1 αi { R 2 +ξi - ( xi - a ) T ( xi - a ) } - ∑ l i =1 γiζi , s. t. αi ≥ 0, (10) γi ≥ 0. 求解得 ∑ l i =1 αi = 1, a = ∑ l i =1 αi xi , (11) C - αi - γi = 0. 根据式 (11)重构式 (9) ,得到其对偶二次规划问题 : max∑ l i =1 αi ( xi ·xi ) - ∑ l i =1 ∑ l j =1 αiαj ( xi ·xj ) , s. t. ∑ l i =1 αi = 1, 0 ≤αi ≤ C. (12) 根据统计学习理论 ,只要核函数满足 Mercer条 件 ,它就对应某一变换空间 R 2 , z在边界外. (16) 2. 2 算例分析 利用 SVDD对无标签数据进行多类聚类分类 , 通过选择合适的核函数以及与之对应的参数 ,可以 获得比较理想的分类边界. 考虑如图 1所示的两维样本分布 ,采用 SVDD 进行一类分类所得结果如图 1 ( a) ,通过调整高斯径 向基核函数中参数 σ值的大小 ,来比较所取得的多 类分类效果 ,如图 1 ( b) ～( d)所示. 第 2期 朱帮助 ,等 :基于支持向量数据描述的无标签数据多类分类 ·133·
·134 智能系统学报 第4卷 1.0 由此可见，随着σ的减小，正常域范围不断缩 0.8 小，支持对象数目则不断增加.当·小到一定的时 候，分类区域被分成若干个互不相通、相互孤立的子 0.6 区域，每个子区域代表一类.随着σ的进一步减少 0.4 最终会形成每一个样本点对应一个子区域，即每一 个样本点都是支持向量， 0.2 3实证分析 0.200.20.40.60.81.01.2 为说明基于支持向量数据描述的无标签数据多 类分类方法的有效性和可行性，以珠三角地区9个 (a)o=1 物流中心城市分类评价作为研究对象开展实证研 1.0 究.20世纪90年代中期以来，随着现代物流理念在 0.8 我国的普及，我国部分省市已开始制定相应的物流 规划，尤其是物流中心的规划与建设.物流中心城市 0.6 的确定是当前物流规划中的首要工作，其实质上是 0.4 一个分类评价问题山依据综合性、客观性、可得 0.2 性、可比性等原则，在对有关文献综合分析和征询有 关专家意见的基础上，从4个方面选取指标建立城 8.200.20.40.60.81.01.2 市物流发展水平综合评价指标体系，这些指标从不 同角度反映了城市物流的发展特征：1)社会经济发 (b)0=03 展类：综合反映了城市物流发展的社会经济基础，包 1.0 括GDP(,万元、人均GDP(,元八、GDP增 长率(，%：2)生产消费流通类：分别从生产、消 0.8 费等角度反映了城市物流服务的需求状况和需求规 0.6 模，包括社会消费品零售总额(x,万元)、工业总产 值(x,万元)、批发零售贸易业总额(x,万元；3) 0.4 人力资源类：反映了物流发展的人力资源状况，包括 0.2 物流从业人员比例，等于交通运输、仓储和邮政业人 员数总从业人员数(x,%:4)交通运输类：反映 8.200.20.4060.81.01.2 X 了城市物流发展的物质基础，包括运输量(，万 吨)、港口吞吐量(。，万吨)、运输网密度(x,千公 (c以0=01 里万平方公里人.各指标数据均来自《广东省统计 1.0 年鉴(2005)》 0.8 采用Matlab70编程进行主成分分析，得特征 值、贡献率和累积贡献率，如表1由于第一、二2个 0.6 。 主成分的特征值大于1，且累积贡献率达到 0.4 8409%,因此可以取前2个主成分，作为特征提取 的目的指标，如表2 0.2 表1特征值、贡献率和累积贡献率 9200,2040608101.2 Table 1 Egenvalue,con tribution and accumultive contri X bution (d)0=002 主成分 特征值贡献率/%累积贡献率% 图1参数·对分类效果的影响 1 618 6184 61.84 Fig 1 Multi-class classification outcomes of differento 2 223 2225 8409 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved. http://www.cnki.net
( a)σ = 1 ( b)σ = 0. 3 ( c)σ = 0. 1 ( d)σ = 0. 02 图 1 参数 σ对分类效果的影响 Fig. 1 Multi2class classification outcomes of differentσ 由此可见 ,随着 σ的减小 ,正常域范围不断缩 小 ,支持对象数目则不断增加. 当 σ小到一定的时 候 ,分类区域被分成若干个互不相通、相互孤立的子 区域 ,每个子区域代表一类. 随着 σ的进一步减少 , 最终会形成每一个样本点对应一个子区域 ,即每一 个样本点都是支持向量. 3 实证分析 为说明基于支持向量数据描述的无标签数据多 类分类方法的有效性和可行性 ,以珠三角地区 9个 物流中心城市分类评价作为研究对象开展实证研 究. 20世纪 90年代中期以来 ,随着现代物流理念在 我国的普及 ,我国部分省市已开始制定相应的物流 规划 ,尤其是物流中心的规划与建设. 物流中心城市 的确定是当前物流规划中的首要工作 ,其实质上是 一个分类评价问题 [ 11 ] . 依据综合性、客观性、可得 性、可比性等原则 ,在对有关文献综合分析和征询有 关专家意见的基础上 ,从 4个方面选取指标建立城 市物流发展水平综合评价指标体系 ,这些指标从不 同角度反映了城市物流的发展特征 : 1)社会经济发 展类 :综合反映了城市物流发展的社会经济基础 ,包 括 GDP( x1 ,万元 ) 、人均 GDP ( x2 ,元 /人 )、GDP增 长率 ( x3 , % ) ; 2)生产消费流通类 :分别从生产、消 费等角度反映了城市物流服务的需求状况和需求规 模 ,包括社会消费品零售总额 ( x4 ,万元 ) 、工业总产 值 ( x5 ,万元 ) 、批发零售贸易业总额 ( x6 ,万元 ) ; 3) 人力资源类 :反映了物流发展的人力资源状况 ,包括 物流从业人员比例 ,等于交通运输、仓储和邮政业人 员数 /总从业人员数 ( x7 , % ) ; 4)交通运输类 :反映 了城市物流发展的物质基础 , 包括运输量 ( x8 , 万 吨 ) 、港口吞吐量 ( x9 ,万吨 ) 、运输网密度 ( x10 ,千公 里 /万平方公里 ). 各指标数据均来自《广东省统计 年鉴 (2005) 》. 采用 Matlab 7. 0编程进行主成分分析 ,得特征 值、贡献率和累积贡献率 ,如表 1. 由于第一、二 2个 主成 分 的 特 征 值 大 于 1, 且 累 积 贡 献 率 达 到 84. 09% ,因此可以取前 2个主成分 ,作为特征提取 的目的指标 ,如表 2. 表 1 特征值、贡献率和累积贡献率 Table 1 Eigenva lue, con tr ibution and accum ula tive con tr i2 bution 主成分 特征值 贡献率 /% 累积贡献率 /% 1 6. 18 61. 84 61. 84 2 2. 23 22. 25 84. 09 ·134· 智 能 系 统 学 报 第 4卷
第2期 朱帮助，等：基于支持向量数据描述的无标签数据多类分类 ·135· 表2第一、二主成分 合水平较高；第3层次是第3类城市，包括江门和肇 Table 2 The fisrt and second princ iple com ponen ts 庆，这2个城市位于珠三角西部，经济实力不强，物 序号 h 乃 流人才短缺，交通基础设施较落后，尚未真正形成交 -066 .101 通运输网络，造成物流发展综合水平偏低.该分类评 2 221 .051 价结果基本符合目前珠三角地区物流发展的实际情 况，也得到了有关政府和物流专家的认可. 1.05 010 0.04 1.33 4结论 5 -056 099 本文结合一类分类方法的最新成果，提出了基 6 -047 .027 于支持向量数据描述的无标签数据多类分类算法， > -0.27 1.10 并将该方法应用于珠三角物流中心城市分类评价 8 -077 .011 中，分类边界明确，分类结果合理，从而验证了该方 9 -058 .1.62 法的有效性与可行性 与已有的多类分类算法相比，本文提出的基于 将前2个主成分值作为SVDD分类器的输入向 量进行多类分类.分类器核函数采用高斯径向基核 主成分分析的支持向量数据描述无标签数据多类分 类方法具有如下几点优势： 函数.调节核函数的参数σ等于05，即 K(x.x)exp(-l x -x2/0 )采用主成分分析作数据预处理，提取主成分 SVDD的分类结果为3类： 特征指标作为SVDD分类器的输入，大大降低了数 据维度，有效浓缩了评估信息，实现了多类分类的可 X=2,3:X2=f4,5.6,7,8:X3=1,9. 视化； SVDD的分类效果如图2所示.从图2可以发现，基 于SVDD的无标签数据多类分类方法可以获得较为 2)将一类分类分类思想引入多类分类中，有效 地解决了传统SM在处理无标签数据多类分类问 理想的分类边界 题上存在的困难，较大程度上简化了多类分类过程 1.5 中的计算复杂度，提高了模型的实用价值； 1.0 3)多类分类问题十分普遍，虽然本文是以珠三 角地区物流中心城市分类评价为应用对象验证了所 0 提出方法的有效性；但该方法具有较强的通用性，稍 -0.5 加变化就可以用于解决其他领域的多类分类问题： 当然，在实际应用中，如何合理确定核函数的参数大 -1.5 小，将是未来进一步研究的问题之一 -1.0-0.500.51.01.52.0 第一主成分 参考文献： 图2分类效果 [1 ]VAPN IK V.Statistical leaming theory [M ]New York:Wi- Fig 2 Classification outcome ey,1998:5964 为了对比，本文还采用Kmeans法进行了3类 [2]PLATT J C,CR ISTAN NIN,SHAW E T J.Large margin 分类，分类结果与SVDD分类结果一致，从而验证了 DAGs for multiclass classification [C]//Advances in Neural 本文所提出方法的有效性与可行性 Inmation Processing Systems 12 Cambridge,Mass MIT 依据SVDD分类结果，珠三角9个中心城市的 Press 547-553. 物流发展水平大致可分为3个层次：第1层次是第 [3 ]W ESION J,WATKNS C Multi-class support vector ma- chines[R ]CSD-TR-98-04.London:Royal Holloway Uni- 1类城市，包括广州和深圳，由于在经济实力、消费 versity.1998 能力、人力资源、物流运输能力等方面均很雄厚，导 [4 ]ZHOU Z H,LIM.Tri-training exp biting unlabeled data 致物流发展综合水平很高，遥遥领先于其他城市：第 using three classifiers[J].EEE Transactions on Knowledge 2层次是第2类城市，包括佛山、中山、珠海、东莞和 and Data Engineering.2005,17(11):1529-1541. 惠州，这些城市在经济增长、工业总产值及交通运输 [5]TAX D M J,DUN R PW.Support vector domain descrip- 网络密度上具有一定的相对优势，致使物流发展综 tion[J Patter Recognition Letters,1999,20 (11/13): 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
表 2 第一、二主成分 Table 2 The fisrt and second pr inc iple com ponen ts 序号 y1 y2 1 - 0. 66 - 1. 01 2 2. 21 - 0. 51 3 1. 05 0. 10 4 0. 04 1. 33 5 - 0. 56 0. 99 6 - 0. 47 - 0. 27 7 - 0. 27 1. 10 8 - 0. 77 - 0. 11 9 - 0. 58 - 1. 62 将前 2个主成分值作为 SVDD分类器的输入向 量进行多类分类. 分类器核函数采用高斯径向基核 函数. 调节核函数的参数 σ等于 0. 5,即 K ( xi , xj ) = exp ( - ‖xi - x‖ 2 /0. 5 2 ). SVDD的分类结果为 3类 : X1 = { 2, 3}; X2 = { 4, 5, 6, 7, 8}; X3 = { 1, 9}. SVDD的分类效果如图 2所示. 从图 2可以发现 ,基 于 SVDD的无标签数据多类分类方法可以获得较为 理想的分类边界. 图 2 分类效果 Fig. 2 Classification outcome 为了对比 ,本文还采用 K2means法进行了 3类 分类 ,分类结果与 SVDD分类结果一致 ,从而验证了 本文所提出方法的有效性与可行性. 依据 SVDD分类结果 ,珠三角 9个中心城市的 物流发展水平大致可分为 3个层次 :第 1层次是第 1类城市 ,包括广州和深圳 ,由于在经济实力、消费 能力、人力资源、物流运输能力等方面均很雄厚 ,导 致物流发展综合水平很高 ,遥遥领先于其他城市 ;第 2层次是第 2类城市 ,包括佛山、中山、珠海、东莞和 惠州 ,这些城市在经济增长、工业总产值及交通运输 网络密度上具有一定的相对优势 ,致使物流发展综 合水平较高 ;第 3层次是第 3类城市 ,包括江门和肇 庆 ,这 2个城市位于珠三角西部 ,经济实力不强 ,物 流人才短缺 ,交通基础设施较落后 ,尚未真正形成交 通运输网络 ,造成物流发展综合水平偏低. 该分类评 价结果基本符合目前珠三角地区物流发展的实际情 况 ,也得到了有关政府和物流专家的认可. 4 结 论 本文结合一类分类方法的最新成果 ,提出了基 于支持向量数据描述的无标签数据多类分类算法 , 并将该方法应用于珠三角物流中心城市分类评价 中 ,分类边界明确 ,分类结果合理 ,从而验证了该方 法的有效性与可行性. 与已有的多类分类算法相比 ,本文提出的基于 主成分分析的支持向量数据描述无标签数据多类分 类方法具有如下几点优势 : 1)采用主成分分析作数据预处理 ,提取主成分 特征指标作为 SVDD分类器的输入 ,大大降低了数 据维度 ,有效浓缩了评估信息 ,实现了多类分类的可 视化 ; 2)将一类分类分类思想引入多类分类中 ,有效 地解决了传统 SVM 在处理无标签数据多类分类问 题上存在的困难 ,较大程度上简化了多类分类过程 中的计算复杂度 ,提高了模型的实用价值 ; 3)多类分类问题十分普遍 ,虽然本文是以珠三 角地区物流中心城市分类评价为应用对象验证了所 提出方法的有效性 ;但该方法具有较强的通用性 ,稍 加变化就可以用于解决其他领域的多类分类问题. 当然 ,在实际应用中 ,如何合理确定核函数的参数大 小 ,将是未来进一步研究的问题之一. 参考文献 : [ 1 ]VAPN IK V. Statistical learning theory[M ]. New York:W i2 ley, 1998: 59264. [ 2 ] PLATT J C, CR ISTIAN IN IN, SHAW E T J. Large margin DAGs for multiclass classification[C ] / /Advances in Neural Information Processing Systems 12. Cambridge, Mass: M IT Press: 5472553. [ 3 ]W ESTON J, WATKINS C. Multi2class support vector ma2 chines[R ]. CSD2TR298204. London: Royal Holloway Uni2 versity, 1998. [ 4 ] ZHOU Z H , L IM. Tri2training: exp loiting unlabeled data using three classifiers[J ]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17 (11) : 152921541. [ 5 ] TAX D M J, DU IN R PW. Support vector domain descrip2 tion[J ]. Pattern Recognition Letters, 1999, 20 ( 11 /13) : 第 2期 朱帮助 ,等 :基于支持向量数据描述的无标签数据多类分类 ·135·
·136· 智能系统学报 第4卷 1191-1199 市分类评价中的应用[J]中国公路学报，2004,17(4)： [6]TAX D,DU N R Outlier detection using classifier instabil- 119-122 ity[J]Advances in Pattem Recognition,Lecture notes in ZHAO Chuang,LU Kai,LI Diansheng Application of Computer Science,1998,1451:593-01 OFM neural netork or classification and evaluation of b- [7]J ANG Shengyi SONG Xiaoyu,WANG Hui,et al A clus- gistics center city[J]China Joumal ofHighway and Trans- tering-based method for unsupervised intrusion detections p0t2004,17(4):119-122 [J ]Pattem Recognition Letters,2006,27(7):802-810. 作者简介： [8 ]BANERJEE A.A support vecpor method for anomaly detec- 朱帮助，男，1979年生，讲师，博士， tion in hyperspectral magery[J]EEE Trans on Geosci- 主要研究方向为复杂系统分析与建模、 ence and Remote Sensing,2006,44(8):2282-2290. 智能信息处理，发表学术论文近20篇 [9赵学风，段晨东，刘义艳，等.一种基于支持向量数据描 其中多篇被SCLEL ISTP收录. 述的损伤诊断方法[J]系统仿真学报，2008,20(6)： 1570-1573 ZHAO Xuefeng,DUAN Chendong.L U Yiyan,et al Struc- ture damage diagnosis method based on SVDD technique 林健，男，1958年生，教授，博士 [J Joumal of System Smulation,2008,20(6):1570- 生导师，博士，主要研究方向为复杂系 1573 统建模与仿真、信息管理与信息系统」 [10]KM K L JUNG K,KM H J.Face recognition using ker 主持多项因家自然科学基金项目和省 nel principal component analysis[J].IEEE Signal Proces- 部级科研项目，发表学术论文150余 sion Letters,.2002,9(2):40-42 篇，其中多篇被SC1 EL ISTP收录， [11赵闯，刘凯，李电生.SOM神经网络在物流中心城 2009中国智能自动化会议 Chnese Itelligent Automa tion Conference 2009中国智能自动化会议(2009CAC)将于2009年9月27~29日在江苏南京举行.会议由中国自动化学会 智能自动化专业委员会和江苏省自动化学会主办，东南大学承办.本次征文的内容包含以下29大类：人工神经网 络、模糊系统、进化计算、计算智能及软计算、智能控制、先进控制方法和技术、机器人技术与系统、多智能体 系统、人工认知系统生物信息学、离散事件系统与混合系统、无线传感器网络、智能信息处理、混沌、分形与小 波、智能管理与决策、智能建模与仿真、智能故障诊断、数据挖掘与知识发现、智能技术在通信与网络中的应用 、智能人机交互技术、虚拟现实及多媒体技术、计算机视觉模式识别与图像处理、智能测量及多传感器信息融 合、智能自动化装置、智能交通系统、人工生命系统及其应用、智能设计与制造、其它等。 2009年4月30日前通过htp:/1 cms amnss ac cn提交论文；2009年6月15日前发出会议论文录用结果的通 知：录用的论文将在《仲国科学F:信息科学专刊($C源)、控制理论与应用》专刊(E源)、《陈南大学学报增 刊(E源)、南京理工大学学报增刊(EI源)、中南大学学报增刊(E源)或有出版号的论文集上发表.会议网 址为：htp:/w.iacaa org/ciac/h_CN/index hml联系人：清华大学计算机系钱宗华，电话：010-62788939， E-mail gianzh tsinghua edu cn 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
119121199. [ 6 ] TAX D, DU IN R. Outlier detection using classifier instabil2 ity[J ]. Advances in Pattern Recognition, Lecture notes in Computer Science, 1998, 1451: 5932601. [ 7 ]J IANG Shengyi, SONG Xiaoyu, WANG Hui, et al. A clus2 tering2based method for unsupervised intrusion detections [J ]. Pattern Recognition Letters, 2006, 27 ( 7) : 8022810. [ 8 ]BANERJEE A. A support vector method for anomaly detec2 tion in hyperspectral imagery [ J ]. IEEE Trans on Geosci2 ence and Remote Sensing, 2006, 44 (8) : 228222290. [ 9 ]赵学风 ,段晨东 ,刘义艳 ,等. 一种基于支持向量数据描 述的损伤诊断方法 [ J ]. 系统仿真学报 , 2008, 20 ( 6) : 157021573. ZHAO Xuefeng, DUAN Chendong, L IU Yiyan, et al. Struc2 ture damage diagnosis method based on SVDD technique [J ]. Journal of System Simulation, 2008, 20 ( 6 ) : 15702 1573. [ 10 ]KIM K I, JUNG K, KIM H J. Face recognition using ker2 nel p rincipal component analysis[J ]. IEEE Signal Proces2 sion Letters, 2002, 9 (2) : 40242. [ 11 ]赵 闯 ,刘 凯 ,李电生. SOFM神经网络在物流中心城 市分类评价中的应用 [J ]. 中国公路学报 , 2004, 17 (4) : 1192122. ZHAO Chuang, L IU Kai, L I D iansheng. App lication of SOFM neural network for classification and evaluation of lo2 gistics center city[J ]. China Journal of H ighway and Trans2 port, 2004, 17 (4) : 1192122. 作者简介 : 朱帮助 ,男 , 1979年生 ,讲师 ,博士 , 主要研究方向为复杂系统分析与建模、 智能信息处理 ,发表学术论文近 20篇 , 其中多篇被 SCI、EI、ISTP收录. 林 健 ,男 , 1958年生 ,教授 ,博士 生导师 ,博士 ,主要研究方向为复杂系 统建模与仿真、信息管理与信息系统 , 主持多项国家自然科学基金项目和省 部级科研项目 ,发表学术论文 150 余 篇 ,其中多篇被 SCI、EI、ISTP收录. 2009中国智能自动化会议 Chinese Intelligent Automation Conference 2009中国智能自动化会议 (2009 CIAC) 将于 2009年 9月 27～29日在江苏南京举行. 会议由中国自动化学会 智能自动化专业委员会和江苏省自动化学会主办 ,东南大学承办. 本次征文的内容包含以下 29大类 :人工神经网 络 、模糊系统 、进化计算 、计算智能及软计算 、智能控制 、先进控制方法和技术 、机器人技术与系统 、多智能体 系统 、人工认知系统 、生物信息学 、离散事件系统与混合系统 、无线传感器网络 、智能信息处理 、混沌、分形与小 波 、智能管理与决策 、智能建模与仿真 、智能故障诊断 、数据挖掘与知识发现 、智能技术在通信与网络中的应用 、智能人机交互技术 、虚拟现实及多媒体技术 、计算机视觉、模式识别与图像处理 、智能测量及多传感器信息融 合 、智能自动化装置 、智能交通系统 、人工生命系统及其应用 、智能设计与制造 、其它等. 2009年 4月 30日前通过 http: / / cms. amss. ac. cn /提交论文 ; 2009年 6月 15日前发出会议论文录用结果的通 知 ;录用的论文将在《中国科学 F:信息科学 》专刊 ( SCI源 )、《控制理论与应用 》专刊 ( EI源 )、《东南大学学报 》增 刊 ( EI源 )、《南京理工大学学报 》增刊 ( EI源 )、《中南大学学报 》增刊 ( EI源 )或有出版号的论文集上发表. 会议网 址为 : http: / /www. iacaa. org/ ciac / zh_CN / index. html. 联系人 :清华大学计算机系钱宗华 ,电话 : 010 - 62788939, E2mail: qianzh@ tsinghua. edu. cn. ·136· 智 能 系 统 学 报 第 4卷
