数据挖掘中的SVM

数据挖掘中的[e-mail]《DataMininingConceptandTechniques》什么是数据挖掘数据挖掘（DataMining）就是从观测到的数据集（经常是很庞大的），抽取出潜在的、有价值的信息1数据集：传统的数据库，数据仓库，Web三大学科的交叉：机器学习统计学数据库技术数据挖掘的图示DataWarehousePrepareddataDataPatternsKnowledgeKnowledgeBase数据挖掘的主要任务分类Classification银行客户关系分类预测Prediction股票趋势预测，GDP预测关联规则AssociationRules购物篮分析（60％买面包的人会买黄油）聚类Clustering金融欺诈行为检测数据挖掘中的ML方法人工神经网络NeuralNetworks决策树DecisionTrees规则归纳RuleInduction最近邻方法NearestNeighborMethod遗传算法GeneticAlgorithms支持向量机SupportVectorMachines粗糙集RoughSet贝叶斯信念网BayesianBeliefNetworks模糊逻辑FuzzyLogic中的使用情况DM的门户网站KDnuggets在2003年的一项名为“Whatdataminingtechniquesyouuseregularly?”的调查结果中，把SVM称为“thebiggestgainer”它占到了11％的使用率SVM在DM中的应用DrugDesignR.Burbidge,M.Trotter,B.BuxtonandS.Holden(2001)DrugDesignbyMachineLearning:SupportVectorMachinesforPharmaceuticalDataAnalysisBioinformaticsPaulBertone(2001)IntegrativeDataMining:TheNewDirectioninBioinformatics•TravelTimePredictionChun-HsinWu,Chia-Chen,Da-Chun,andMing-HuaChang(2003)TravelTimePredictionwithSupportVectorRegression.•IntrusionDetectionSrinivasMukkamala,GuadalupeJanoski,AndrewH.Sung.(2002)IntrusionDetectionUsingSupportVectorMachines.1.DavidHand.《PrinciplesofDataMining》数据挖掘的特点最大的特点：海量数据集美国零售商沃尔玛每天大约2千万笔的交易，一年的客户交易数据库容量超过11TBAT&T公司，1亿电话用户，每天3亿次的呼叫特征数据美国宇航局NASA的地球观测系统每小时生成几个GB的原始数据人类基因工程中超过3.3×109个核苷酸的数据库其它特点：较高维度，有噪声，属性值缺失带来的问题传统的统计方法没法应用经典的ML方法的使用会受制于计算机硬件过度拟合（Overfitting）的频现维度灾难（CurseofDimensionality）分布式存储带来的数据访问困难分析时间太长，影响后期的实时决策效果SVM在DM中的优势和不足优势：最大间隔的思想－更好的泛化能力，有助于解决过度拟合核函数－解决非线性问题的同时避免维度灾难二次优化－存在唯一解，并且可以找到全局最优稀疏性－支持向量个数相对数据集小得多，易于存储不足：运算效率低计算时占用资源过大大规模数据下的SVMSVM的核心在于求解一个QP问题原始问题：等价问题形式：11111minimize,2subjectto0:0llliijijijiijliiiiWyyKxxyi11,,12liiiiLwbwwxwby庞大的核函数矩阵QQ是一个L×L的矩阵,且不稀疏Q在寻优计算中要经常调用带来的问题Q无法在内存中存储实时计算Q，带来效率低下Q太大，使得矩阵运算很耗时,ijijijQyyKxx其中1minimize12subjectto00TTTQWy分解算法（Decomposition)思想：将大型的二次规划问题（QP问题）分成若干个小的QP问题，也就是每次抽取一个小的工作集（WorkingSet）来做QP，从而解决内存不够的问题Boser-Atrainingalgorithmforoptimalmarginclassifiers-1992ChunkingBoser,Vapnik1992思想：•去掉非SV的（αi＝0）样本，不影响解缺陷：•当模型不稀疏的时候（SVs很多）的时候，DataSet会越来越大，以至于无法计算Osuna-Trainingsupportvectormachines:anapplicationtofacedetection-1997ChunkingwithFixed-sizeWorkSetOsuna1997思想：同Chunking，但是固定DataSet的大小缺陷：虽然解决了计算可行的问题，B的大小可能比真正的SV还小Joachims-Makinglarge-scalesupportvectormachinelearningpratiacal-1999ShrinkingJoachims1998思想：边界支持向量BSVs（ai＝C的SV）在迭代过程中ai不会变化，如果找到这些点，并把它们固定为C，可以减少QP的规模缺陷：当SVs数量过多，或者SVs中BSVs较少时效率不高Platt-Fasttrainingofsupportvectormachinesusingsequentialminimaloptimiztion-1999SMOPlatt1999思想：DataSet的大小设定为2，可以得到QP的解析解（analyticalsolution），避免了复杂的数值求解缺陷：迭代次数多，非线性情况下的优势不明显分解算法的问题大数据集下的SVM的特点：SVs很多上述方法的问题：SVs多时，收敛的太慢SVs太多时，测试速度比较慢，特别是使用非线性核函数时想法：压缩SVs的数量Y.-J.LeeandO.L.Mangasarian.-RSVM:Reducedsupportvectormachines-2001RSVMReducedSVMY-J.LeeO.L.Mangasarian2001SIAMInternationalConferenceonDataMining2001RSVM的基本思路211min2subjectto1lTiiTiiiwwCywxb1liiiiwyx211min2subjecttolTiiQCQbye（1）式（2）式（3）式抽取子集R总训练集A中随机抽取一个子集RR的数目m占总数目L的1％－10％实质上压缩了SVs的数目，将SVs限制在R中1liiiiwyxiRiiiwyx（4）式削减Q！大幅削减Q的维度,21:1min2subjecttolRTRiRRRRiCbyeQQ,:RRKRQmRDm,=:KAQlADl:,=,:RKARQDlm1%10%ml（5）式（6）式正方型核－》长方形核,=AQDKA:,,=RQDKAR1%10%mllllmY.-J.LeeandO.L.Mangasarian.-SSVM:Asmoothsupportvectormachines-1999有约束－》无约束采用SSVM（SmoothSVM）Y-J.LeeO.L.Mangasarian1999思想：•将约束不等式代人主式，将ξ消去，同时采用一个平滑函数使得主式二次可导，再用Newton下降法，从而将有约束优化转化为无约束优化，2:,11min2lTRRRRiiPeQ（7）式Y.-J.LeeandO.L.Mangasarian.-RSVM:Reducedsupportvectormachines-2001实验结果（训练时间）RSVM，SMO，PCGChunking算法用于UCIAdultdataset的训练时间Y.-J.LeeandO.L.Mangasarian.-RSVM:Reducedsupportvectormachines-2001实验结果（正确率）数据集（数目，维数，R的大小）RSVM传统SVM疑惑压缩了SVs的个数，甚至是限定在R集中准确率和速度（训练速度，测试速度）的双重提升两全其美？作者给出的解释：•压缩SVs的个数，避免的了大样本下的过度拟合（overfitting）问题不同的结果Kuan-MingLin,Chih-JenLin2003AstudyonreducedsupportvectormachinesIEEETransactionsonNeuralNetworks,2003.鱼和熊掌不可兼得用实验分析了RSVM的性能得到以下结论不论在多大的数据集下RSVM和普通SVM相比正确率有所下降，但仅仅（alittlelower）在大型数据集或者某些SVs很多的情况下，RSVM体现出很高的效率！RSVM总结思路：随机选择的一个较小的子集R，将SVs限定在R中，来压缩SVs的数目，从而大大降低Q的规模，再转化为无约束优化问题，用Newton下法降来求解评价：以很小的正确率下降换取效率，是一种适用于数据挖掘的好方法Y.-J.LeeandO.L.Mangasarian.-RSVM:Reducedsupportvectormachines-2001问题1和直接用R来训练有什么不一样？A＝1000，R＝50，直接用R训练的测试结果A＝1000，R＝50，用RSVM训练的测试结果问题2R集的选择是Random就可以么？R集选择的策略对R集的选择敏感Lee中采取的策略类似于Random