数据挖掘中的

1、数据挖掘中的SVM,oneroadsmth 2003.12,1.Jiawei Han Data Minining Concept and Techniques,什么是数据挖掘,数据挖掘（Data Mining）就是从观测到的数据集（经常是很庞大的），抽取出潜在的、有价值的信息1 数据集：传统的数据库，数据仓库，Web 三大学科的交叉： 机器学习 统计学 数据库技术,数据挖掘的图示,Data Warehouse,Prepared data,Data,Patterns,Knowledge,Knowledge Base,数据挖掘的主要任务,分类 Classification 银行客户关系分类 预测

2、Prediction 股票趋势预测，GDP预测 关联规则 Association Rules 购物篮分析（60买面包的人会买黄油） 聚类 Clustering 金融欺诈行为检测,数据挖掘中的ML方法,人工神经网络 Neural Networks 决策树 Decision Trees 规则归纳 Rule Induction 最近邻方法 Nearest Neighbor Method 遗传算法 Genetic Algorithms 支持向量机 Support Vector Machines 粗糙集 Rough Set 贝叶斯信念网 Bayesian Belief Networks 模糊逻辑 Fuz

3、zy Logic,www.KD,SVM在DM中的使用情况,DM的门户网站KDnuggets在2003年的一项名为 “What data mining techniques you use regularly? ” 的调查结果中，把SVM称为 “the biggest gainer” 它占到了11的使用率,SVM在DM中的应用,Drug Design R.Burbidge,M.Trotter,B.Buxton and S.Holden(2001)Drug Design by Machine Learning:Support Vector Machines for Pharmaceutical D

4、ata Analysis Bioinformatics Paul Bertone(2001) Integrative Data Mining:The New Direction in Bioinformatics Travel Time Prediction Chun-Hsin Wu,Chia-Chen,Da-Chun,and Ming-Hua Chang (2003)Travel Time Prediction with Support Vector Regression. Intrusion Detection Srinivas Mukkamala, Guadalupe Janoski,

5、Andrew H. Sung. (2002) Intrusion Detection Using Support Vector Machines.,1.David Hand. Principles of Data Mining,数据挖掘的特点,最大的特点：海量数据集 美国零售商沃尔玛每天大约2千万笔的交易，一年的客户交易数据库容量超过11TB AT&T公司，1亿电话用户，每天3亿次的呼叫特征数据 美国宇航局NASA的地球观测系统每小时生成几个GB的原始数据 人类基因工程中超过3.3109个核苷酸的数据库 其它特点：较高维度，有噪声，属性值缺失,带来的问题,传统的统计方法没法应用 经典的ML方法

6、的使用会受制于计算机硬件 过度拟合（Overfitting）的频现 维度灾难（Curse of Dimensionality） 分布式存储带来的数据访问困难 分析时间太长，影响后期的实时决策效果,SVM在DM中的优势和不足,优势： 最大间隔的思想更好的泛化能力，有助于解决过度拟合 核函数解决非线性问题的同时避免维度灾难 二次优化存在唯一解，并且可以找到全局最优 稀疏性支持向量个数相对数据集小得多，易于存储 不足： 运算效率低 计算时占用资源过大,大规模数据下的SVM,SVM的核心在于求解一个QP问题 原始问题： 等价问题形式：,庞大的核函数矩阵Q,Q是一个LL的矩阵,且不稀疏 Q在寻优计算中要

7、经常调用 带来的问题 Q无法在内存中存储 实时计算Q，带来效率低下 Q太大，使得矩阵运算很耗时,分解算法（ Decomposition),思想： 将大型的二次规划问题（QP问题）分成若干个小的QP问题，也就是每次抽取一个小的工作集（Working Set）来做QP，从而解决内存不够的问题,Boser - A training algorithm for optimal margin classifiers - 1992,Chunking,Boser,Vapnik 1992 思想： 去掉非SV的（i0）样本，不影响解 缺陷： 当模型不稀疏的时候（SVs很多）的时候，Data Set会越来越大，以

8、至于无法计算,Osuna - Training support vector machines:an application to face detection - 1997,Chunking with Fixed-size Work Set,Osuna 1997 思想： 同Chunking，但是固定Data Set的大小 缺陷： 虽然解决了计算可行的问题，B的大小可能比真正的SV还小,Joachims - Making large-scale support vector machine learning pratiacal - 1999,Shrinking,Joachims 1998 思想

9、： 边界支持向量BSVs（aiC的SV）在迭代过程中ai不会变化，如果找到这些点，并把它们固定为C，可以减少QP的规模 缺陷： 当SVs数量过多，或者SVs中BSVs较少时效率不高,Platt - Fast training of support vector machines using sequential minimal optimiztion - 1999,SMO,Platt 1999 思想： Data Set的大小设定为2，可以得到QP的解析解（analytical solution），避免了复杂的数值求解 缺陷： 迭代次数多，非线性情况下的优势不明显,分解算法的问题,大数据集下的S

10、VM的特点：SVs很多 上述方法的问题： SVs多时，收敛的太慢 SVs太多时，测试速度比较慢，特别是使用非线性核函数时 想法：压缩SVs的数量,Y.-J.Lee and O.L.Mangasarian. - RSVM:Reduced support vector machines -2001,RSVM,Reduced SVM Y-J.Lee O.L.Mangasarian 2001 SIAM International Conference on Data Mining 2001,RSVM的基本思路,（1）式,（2）式,（3）式,抽取子集R,总训练集A中随机抽取一个子集R R的数目m占总数目

11、L的110 实质上压缩了SVs的数目，将SVs限制在R中,（4）式,削减Q！,大幅削减Q的维度,（5）式,（6）式,正方型核长方形核,Y.-J.Lee and O.L.Mangasarian. - SSVM:A smooth support vector machines - 1999,有约束无约束,采用SSVM（Smooth SVM） Y-J.Lee O.L.Mangasarian 1999 思想： 将约束不等式代人主式，将消去，同时采用一个平滑函数使得主式二次可导，再用Newton下降法，从而将有约束优化转化为无约束优化，,（7）式,Y.-J.Lee and O.L.Mangasarian

12、. - RSVM:Reduced support vector machines -2001,实验结果（训练时间）,RSVM，SMO，PCG Chunking 算法用于 UCI Adult dataset 的训练时间,Y.-J.Lee and O.L.Mangasarian. - RSVM:Reduced support vector machines -2001,实验结果（正确率）,数据集（数目，维数，R的大小） RSVM 传统SVM,疑惑,压缩了SVs的个数，甚至是限定在R集中 准确率和速度（训练速度，测试速度）的双重提升 两全其美？ 作者给出的解释： 压缩SVs的个数，避免的了大样本下的

13、过度拟合（overfitting）问题,不同的结果,Kuan-Ming Lin, Chih-Jen Lin 2003 A study on reduced support vector machines IEEE Transactions on Neural Networks, 2003.,鱼和熊掌不可兼得,用实验分析了RSVM的性能得到以下结论 不论在多大的数据集下RSVM和普通SVM相比正确率有所下降，但仅仅 （a little lower） 在大型数据集或者某些SVs很多的情况下，RSVM体现出很高的效率 ！,RSVM总结,思路： 随机选择的一个较小的子集R，将SVs限定在R中，来压缩SVs的数目，从而大大降低Q的规模，再转化为无约束优化问题，用Newton下法降来求解 评价： 以很小的正确率下降换取效率，是一种适