您好,欢迎来到爱go旅游网。
搜索
您的当前位置:首页一种基于多目标优化的数据分类模型

一种基于多目标优化的数据分类模型

来源:爱go旅游网
总第296期 2014年第6期 计算机与数字工程 Computer&Digital Engineering Vo1.42 No.6 1023 一种基于多目标优化的数据分类模型 陈三风 。 王辉静 郭森 。 陆芸婷 。 518029) 深圳518029)(2.深圳市可视媒体处理与传输重点实验室深圳(1.深圳信息职业技术学院信息技术研究所摘要论文将从多目标优化的角度出发,结合LDA的第一个目标(最大化类间方差)和SVM的第二个目标(最小化 经验风险),构造一个新的最大类间方差和最小经验风险(MVE)数据分类模型。由于该模型是一个非凸规划模型,论文使 用凹凸规划(CCCP)来进行求解。为了验证论文提出的数据类模型,对人工和真实的数据挖掘实验室数据(UCI)数据集进 行分类实验测试。实验结果表明该数据分类模型有效性的。 关键词多目标规划;分类;数据挖掘 TP24 DOI:10.3969/j.issn1672—9722.2014.06.027 中图分类号A Data Classification Model Based on Multi—objective Optimization CHEN Sanfeng ’ WANG Huijing GUO Sen ’ LU Yunting ’ (1.Institute of Information Technology,Shenzhen Institute of Information Technology,Shenzhen 518029) (2.Shenzhen Key 1.aboratory of Visual Media Processing and Transmission,Shenzhen 518029) Abstract For multi—objective optimization,the LDA’S first goals(maximum inter-class variance)and the SVM second goal(minimum the empirical risk)are combined for configuring a new MVE data classification mode1.It is a non-convex pro— gramming model and CCCP programming is utilized.In order to verify the data classification model presented in this paper, some data classification experiments are carried based on artificia1 and real UCI datasets.The experimental results show that the data c1assi“cation modeliS effective. Key Words multi—objective planning,classification,data mining Class Number TP24 1 引言 随着计算机软硬件和存储设备等相关技术的 发展,人们将收集越来越多的数据。为了从这些海 量数据中获取深层次有用的知识,有关学者开展了 一构造出来的分类模型可能会由于过拟合训练样本 而导致预测精度低下;反之,如果目标函数太简单, 那么构造出来的分类模型很可能会在训练样本上 产生大的偏差。针对以上两方面问题,有的数据分 类模型采用优化单个目标函数的方法,如神经网络 一系列基于大规模数据的关联分析模型、聚类模型 般采用最小化平方损失函数,决策树一般采用最 和分类模型[1]等相关研究,其广泛用于人工智能、 模式识别、决策支持和商业智能等一系列工业生产 和社会生活中。构造大规模数据的分类模型需要 小化信息熵;另外一部分数据分类模型则采用同时 优化多个目标函数的方法,如线性判别分析 (LDA)[2]采用同时最大化类间方差和最小化类内 综合考虑多方面的因素,其中一个关键的问题就是 如何构造其目标函数。如果目标函数太复杂,那么 方差,支持向量机(SVM)[3]采用同时最大化分类 间隔和最小化经验风险。 收稿日期:2013年12月15日,修回日期:2014年1月25日 基金项目:国家自然科学基金(编号:61271420);广东省自然科学基金(编号:¥2012010008997,¥2011010006120, S2OllO1o0O6115);深圳市科技计划(编号:JC201105190821A,ZYA201007070116A)资助。 作者简介:陈三风,女,博士,副教授,研究方向:信号分析与处理、模式识别。王辉静,女,博士,副教授,研究方向:模 式识别与人工智能。郭森,男,博士,副教授,研究方向:图形图像处理。陆芸婷,女,博士,副教授,研究方向:计算机 网络。 陈三风等:一种基于多目标优化的数据分类模型 第42卷 (2) 由于客观世界非常复杂,如果仅优化单个目标 函数对数据进行分类的效果一般都不理想。同时, 根据统计学习理论的偏置一方差分解原理[4],大部 Minimize砌 Sww 将目标函数(1)和目标函数(2)结合起来,LDA 的最终目标函数如下: Maximize JF(叫)一 w ̄SBw (3) 分数据分类模型采用在偏置误差和方差之间的一 个折衷选择。根据该分解原理,本文拟构造一个新 的基于多目标优化的数据分类模型,即结合LDA 的第一个优化目标(最大化类间方差)和SVM的 第二个优化目标(最小化经验风险)来构造一个新 LDA易于求解,因此常被用于分类或特征约 减。但是,LDA模型不包含对于训练错误的惩罚 项。因此,当真实数据不满足LDA给出的正态分 的最大类间方差和最小经验风险(MVE)目标函 数,并基于该目标函数来构造数据分类模型。 2最大类间方差和最小经验风险 (MVE)数据分类模型的构造 考虑一个两类分类问题{G ,G2},其中G 类有 N 个样本X ==={ )Nj ,Gz类有N 个样本X 一 {z ) ,分类的目标则是找到最优的决策边界b (该边界由投影方向叫决定),使得G 中的样本x 和G 中的样本X 能够最大程度地分开。首先深 入分析LDA和SVM的特性,分别指出两种分类 算法的优劣,并基于此提出本文的分类模型。 2.1线性判别分析(LDA) 从数据分类的角度来分析第1步:LDA计算 两类样本均值向量m ===— 1∑N 1 、m。一 ∑N2 %,其中 和7n 之间的距离为S。=== ’Z ( 1一 2)( l— 2)。r。 第2步:LDA分别计算两类类内方差s 和 S ,分别为S 一∑ N一1 (.zli-m )( 一 ) 和S。 一∑Ni一2 (.z 一mz)(z 一m ) ,总的类内方差为 S 一S1+S2。 第3步:LDA将所有的方差投影到方向砌上, 即:Var 一∑N1 (wx 一一 ) 和Var。===∑ (wx2 一 2) 。根据矩阵运算可得,Varl= [∑ NI(xl ̄-m1)(乩一m1)  ̄w=wrs1训,Vat2一 硼 [∑N一 2 (X2i- )(z2i- 。) w=w S。硼。类 内方差在方向硼上的投影后,表示为 S 叫=叫 (S1+Sz)砌;类间方差则表示为 砌 SB 一(叫・m1~ ・m2)。 一训 、(m1一 2)( 1~ 2)rw一训 S6叫 最后,LDA的目标函数为最大化类间方差叫T S 训和最小化类内方差叫rS 叫,即: Maximize W SR叫 (1) 布假设时,LDA的性能将非常差。 2.2支持向量机(SVM) SVM已经被广泛用于进行数据分类,本部分 将从多目标规划的角度重新考虑SVM模型。根 据Vapnik的统计学理论[3],模型的真实风险R(J’) 将小于经验风险R (厂)和置信度区间c ̄(n/h)之 和,即: R(厂)≤R p( )+q ̄(n/h) (4) 其中 为训练样本数目,h为模型的复杂度(VC 维)。根据不等式(4),增加模型的复杂度(VC维) 将可以降低经验风险,但是会增大置信度区间。因 此,最优决策边界实际上是经验风险和置信度区间 的折衷。从多目标规划的角度出发,SVM表示如 下: Maximize ‘5) Minimize∑a (6) S.t.: Y (wx +6) 1一d a O (7) 其中a 为拉格朗日乘子,将以上两个目标函数整 合,可得到以下SVM模型: Minimize 1 ll硼I1 +c∑a (8) S.t.: Y (wz +6) 1一a a 0 (9) 式中c为惩罚因子。 2.3最大类间方差和最小经验风险(MVE) 根据以上分析,本文将结合LDA的第一个目 标(最大化类间方差)和SVM的第二个目标(最小 化经验风险),构造一个新的基于最大类问方差和 最小经验风险(MVE)数据分类模型。与SVM模 型相比,MVE模型使用类间方差来替代最大间隔, 从而达到结构风险最小化的目的。从多目标规划 的角度来分析,MVE表示如下: Maximize S R硼 (10) 2014年第6期 计算机与数字工程 1O25 Minimize∑ S.t.: (11) 则原始的MVE模型可以表示成如下的模型: Minimize-厂( )+Ux(z) 眦 一 Gb, ∈G1 +口 三三6, EGz ∞ 0 重写_厂(z)+Ux(z)如下 厂(z)+Ux(z)===g(z)--h(x) 其中g(z)一 1 l0 I lz II。+∑a + ( )和 (z.) 1 一其中 是投影方向,b是分类边界。将两个目标函 数使用参数C组合为一个日标函数,获得MVE模 型如下: 音p Jl l +c・W S 叫都是凸函数。MVE的 l算法1 CCCP求解MVE模型输入:初始迭代点 求解算法如下: Minimize∑口。一f・ SB训 (12) .t.: t ——d 三6,z EG1 WSC +∞≥6, ∈G2 0/i () (13) 式中0/i为拉格朗日乘子,C为惩罚因子。 为了对比以上几种模型,表1中列出了几个模 型的目标函数。对于那些选取的目标函数,在其对 应的表格单元上标记“√”。 表1 从多目标分类的角度考虑各个分类模型的目标函数 3 MVE模型的求解 从MVE模型的构造来看,MVE不是一个标 准的凸二次规划模型,因此很难直接求解。CCCP 规划是近几年来优化界内提出的用于求解非凸规 划的一个常用方法,其求解速度较快、精度较高。 CCCP的基本原理是将一个非凸规划分解成一个 凸规划和一个凹规划,然后对于凹规划部分,CCCP 使用一个线性近似来计算下一个迭代点。对此,本 文将使用CCCP规划l5]方法将MVE模型转化为 一系列的凸规划模型。由于算法的每一步都会使 得目标函数趋于收敛。因此,经过一系列的迭代, 算法终将收敛到一个局部最优点。为了便于描述, 在此引入一些符号,令z一(叫, ),-厂(z)一 a 一 c・wTs。W,可行域表示如下 f( ,a,6): ] x_1 wxi-ai ̄ b,xi E G1 E X, 令 c 。。, ER。 ,参数s>0 输出:局部最优点32 算法开始 Repeat XIk+l=minimize告IDl lz J】。+∑d 一(^ ( ), ) Until l l~ l1 e 算法结束 根据以上分析可知,在每一个迭代步中,只需 要计算一个凸二次规划模型,就可以借助现有的许 多软件进行求解。 4仿真实验 为了测试MVE模型的性能,本文使用两个人 工数据集和四个真实的UCI数据集[6q]对比 MVE、LDA和SVM的性能。在本文的实验中, I DA使用Matlab实现,SVM使用Libsvm实现, 而MVE使用Visual Fortran 6.5实现。在本文 中,只考虑线性分类的情况,因此对于SVM,只采 用线性核函数。 图1和图2为了本文使用的人工数据集的示 意图。每个数据集都是一个三维的两类分类问题, 总共有2000个样本,每类有1000个样本。在两个 数据集中,使用20 的样本进行训练,8O 的样本 进行测试。即:共使用400个训练样本和1600个 测试样本进行实验,所有的样本都服从高斯分布z ~N( , )。在两类样本中, 一E1,1,11, 一E2, 2,2],协方差矩阵为 一 z一0.3*J,其中,I是一 个3*3的单位矩阵。此外,本文将SVM和MVE 中的参数C都设置为1。表2和3为两个人工数据 集的实验结果,根据实验结果可知,相对于SVM 和I DA模型,MVE在人工数据集上的性能更加 稳定、准确。 为了进一步验证MVE的性能,本文对4个 UCI真实数据集:wbreastc,liver,bupa,pima进一 步进行实验对比,表4~表7为实验结果。从实验 结果可以看到,MVE模型在4个UCI数据集上性 1026 陈三风等:一种基于多目标优化的数据分类模型 第42卷 能都更好,而SVM和LDA各有两次超过对方。 此外,SVM在训练样本上常常表现更好,即SVM 对于训练样本的拟合能力很好,但是其泛化性一 般。因此,本文提出的MVE模型总体性能比较 好,是一个优秀的数据分类模型。 4 3 0"3 2 《 1 0 3 图1数据集1线性可分数据集 图2数据集2近似可分数据集 表2模拟数据集1的实验结果 表3模拟数据集2的实验结果 表4 wbreastc数据集的实验结果对比 表5 Liver数据集的实验结果对比 表6 bupa数据集的实验结果对比 表7 pima数据集的实验结果对比 5 结语 由于分类数据的复杂性,基于单目标优化的数 据分类模型很难获得一个最佳的决策边界,基于多 目标优化的模型l_9叫o]在很大程度上可以改善这种 缺点。本文从多目标规划的角度出发,分别分析了 线性判别模型(LDA)和支持向量机模型(SVM)的 构造特点。在此基础上,结合I.DA的第一个目标 (最大化类间方差)和SVM的第二个目标(最小化 经验风险),构造一个新的最大类间方差和最小经 验风险(MVE)数据分类模型。由于MVE模型是 一个非凸模型,本文使用CCCP规划来对其进行求 解。对人工实验数据和真实UCI数据集进行分别 实验验证。实验结果表明,MVE模型是一个非常 有效的数据分类模型。 在本文中,只研究了线性核函数下的各数据分 类模型的性能对比,拟在将来的工作中进一步研究 如何构造基于Mercy核函数的等非线性MVE数 据分类模型。 参考文献 r1]D.Olson,Y.Shi.Introduction to Business Data Min— ingEM].Englewood Clifs:McGraw-Hill/Irwin,2012. Es]Fisher,R.A.The Use of Multiple Measurements in Taxonomic Problems[J].Annals of Eugenics,1996,7: 179~188. I-3]Vapnik,V.N.The Nature of Statistical Learning Theory[M].2nd edition,New York:Springer,2000. [43 Domingos,P.A Unified BiawVariance Decomposition and its Applications[C]//Proc.of thseventeeth Intern tional Conference on Machine Learning,Stanford,CA. Morgan Kaufmann,2009:231—238. Es]Le Thi Hoai An,Pham Dinh Tao.Solving a class of lineariy constrained indefinite quadratic problem by D. 2014年第6期 计算机与数字工程 2301-23 J1. 1027 C.algorithms[J].Journal of Global Optimization, 2007,11:253—285. [9]Shi,Y,Y.Peng,W.xu,et a1.Data Mining via Mul— tiple Criteria Linear Programming:Applications in f 6 j D.Newman,S.Hettich,C.Blake,et a1.UCI Repos— itory of machine learning[J[1_2008. Credit Card Portfolio Management[J].International Journal of Information Technology and Decision Mak— ing,2005,2(1):131—151. [7]A.Oliva,八Torralba.Modeling the Shape of the Scene:A Holistic ReDreseI1tation of the Spatial Enve— lope[J].International Journal of Computer Vision, 2001,42(3):145—175. [1O]C.Siagian,L.Itti.Rapid Biologically-inspired scene classification using features shared with visual atten— E83 L.Renniger,J.Malik.When is scene identification just texture recognition[J].Vision Research,2004,44: ’;不 ’ 不. 不 . . 币. 币 ’ 币  ’tion[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29(2):300—312. 出乖 乖 矫 尔 坏 不 ;. . 1 不 币. 乔 (上接第1014页) 发展模型预测值和其实际值进行叠加如图3,两曲 线基本吻合,模型有效。 Herald,2008(10):23—28. [4]宋光辉,吴栩,詹素卿,等.行业指数相关关系的多重分 形时变性及实证分析[J].统计与信息论坛,2013(7): 5 结语 依据机床行业指数发展y的模型公式 Y一15.57667+().67860×al +0.98665×a2+1.49583×a3 32—36. SONG Guanghui,WU Xu,ZHAN Suqing,et a1.Em— pirical Analysis of Multifractal Correlation Industry In— dexs[J].Statistics&Information Forum,2013(7):32— 36. 得出,国民经济每增长一个单位,机床产业增长 E5]焦字军.SQL Server在城镇地籍数据库管理工作中的 应用口].测绘地理信息,2013(5):58—60. JIAO Zijun.Application of SQL Server in Urban Ca— 0.6786;基础设施建设每增加一个点,机床行业增 加产值0.98665;房地产产值每增加1,机床行业增 加1.49583。 dastral Database Management[J].Journal of Geomat— ics,2013(5):58—6O. 机床行业发展主要影响因数为经济总体发展 情况、基础设施建设和房地产这三个因数,我国经 济一直保持高速发展,十二丘规划期间基本保持在 7 以上,基础设施建设也在逐步完善当中,特别是 [6]朱世武.sas编程技术与金融数据处理[M].北京:清华 大学出版社,2003:120—60. ZHU Shiwu.Sas programming technology and financial 高速铁路、地铁、港口等还处于发展期,还有发展空 间。房地产经过高速发展后,房价涨幅过大,国家 在政策方面也有所限制,房地产产业增速已经明显 放慢。展望机床行业未来发展空间将随着三因数 增长而增长但增幅会有所放缓。 参考文献 data processing[M].Beijing:Tsinghua university press,2003:120—260. [7]高惠璇.Sas系统sas/ets软件使用手册[M].北京:中 国统计出版社,1998:121—355. GA()Huixuan.Sas/ets software user manual r M]. Beijing:China statistics press,1998:121—355. [8]周冰,王美清,甘佳.基于主成份分析的云制造服务 QoS评估方法研究EJ].制造业自动化,2013(7):28—33. ZHOU Bing,WANG Meiqing,GAN Jia.A method of cloud manufacturing service QoS evaluation based on [1]关桂齐,杨松山,刘国良.我国数控技术发展的分析与 研究[J].机械制造,2013(6):88—91. GUAN Guiqi,YANG Songshan,LIU Guoliang.The analysis and research of numerical control technology PCA[J].Manufacturing Automation,2013(7):28-33. [9]张鹤.多元线性回归分析方法的实例研究[D].郑州:中 原工学院,2012,5:4-18. ZHANG He.The case study of multivariate linear re— development in china[J].Machinery,2013(6):88—91. [2]张力,王燕梅.基于机床工业的产业增长源泉探析[J]. 经济经纬,2010(5):22—26. ZHANG Li,WANG Yanmei.A Probe into the Sources gression analysis method[D].Zhengzhou:Zhongyuan University of Technology,2012,5:4—18. of Industrial Growth Based on Machine Tool Industry [J].Economic survey,2010(5):22—26. [10]赖艺芬,梁飞豹.基于典型相关的线性回归模型[J]. 福州大学学报,2004(4):438—441. LAI Yifen,LIANG Feibao.Linear regression model [3]蒋治平.我国股市行业指数之间的冲击传导研究[J]. 证券市场导报,2008(10):23—28. JIANG Zhiping.The Conduction Study of Industry in— based on canonical correlation[J].Journal of Fuzhou University,2004(4):438—441. dics in Stock Market in China rJ].Securities Market 

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- igat.cn 版权所有

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务