數(shù)據(jù)挖掘中的SVM課件

1、數(shù)據(jù)挖掘中的SVMoneroadsmth2003.12什么是數(shù)據(jù)挖掘數(shù)據(jù)挖掘（Data Mining）就是從觀測(cè)到的數(shù)據(jù)集（經(jīng)常是很龐大的），抽取出潛在的、有價(jià)值的信息1數(shù)據(jù)集：傳統(tǒng)的數(shù)據(jù)庫(kù)，數(shù)據(jù)倉(cāng)庫(kù)，Web三大學(xué)科的交叉：機(jī)器學(xué)習(xí)統(tǒng)計(jì)學(xué)數(shù)據(jù)庫(kù)技術(shù)1.Jiawei Han Data Minining Concept and Techniques數(shù)據(jù)挖掘的圖示Data WarehousePrepareddataDataPatternsKnowledgeKnowledgeBase數(shù)據(jù)挖掘的主要任務(wù) 分類 Classification銀行客戶關(guān)系分類 預(yù)測(cè) Prediction股票趨勢(shì)預(yù)測(cè)，GDP預(yù)

2、測(cè) 關(guān)聯(lián)規(guī)則 Association Rules購(gòu)物籃分析（60買面包的人會(huì)買黃油） 聚類 Clustering金融欺詐行為檢測(cè)數(shù)據(jù)挖掘中的ML方法人工神經(jīng)網(wǎng)絡(luò) Neural Networks決策樹 Decision Trees 規(guī)則歸納 Rule Induction 最近鄰方法 Nearest Neighbor Method 遺傳算法 Genetic Algorithms 支持向量機(jī) Support Vector Machines粗糙集 Rough Set貝葉斯信念網(wǎng) Bayesian Belief Networks模糊邏輯 Fuzzy LogicSVM在DM中的使用情況DM的門戶網(wǎng)站KDn

3、uggets在2003年的一項(xiàng)名為 “What data mining techniques you use regularly? ” 的調(diào)查結(jié)果中，把SVM稱為 “the biggest gainer” 它占到了11的使用率www.KDSVM在DM中的應(yīng)用Drug Design R.Burbidge,M.Trotter,B.Buxton and S.Holden(2001)Drug Design by Machine Learning:Support Vector Machines for Pharmaceutical Data AnalysisBioinformaticsPaul Bert

4、one(2001) Integrative Data Mining:The New Direction in BioinformaticsTravel Time Prediction Chun-Hsin Wu,Chia-Chen,Da-Chun,and Ming-Hua Chang (2003)Travel Time Prediction with Support Vector Regression.Intrusion DetectionSrinivas Mukkamala, Guadalupe Janoski, Andrew H. Sung. (2002) Intrusion Detecti

5、on Using Support Vector Machines. 數(shù)據(jù)挖掘的特點(diǎn)最大的特點(diǎn)：海量數(shù)據(jù)集美國(guó)零售商沃爾瑪每天大約2千萬筆的交易，一年的客戶交易數(shù)據(jù)庫(kù)容量超過11TBAT&T公司，1億電話用戶，每天3億次的呼叫特征數(shù)據(jù)美國(guó)宇航局NASA的地球觀測(cè)系統(tǒng)每小時(shí)生成幾個(gè)GB的原始數(shù)據(jù)人類基因工程中超過3.3109個(gè)核苷酸的數(shù)據(jù)庫(kù)其它特點(diǎn)：較高維度，有噪聲，屬性值缺失1.David Hand. Principles of Data Mining帶來的問題傳統(tǒng)的統(tǒng)計(jì)方法沒法應(yīng)用 經(jīng)典的ML方法的使用會(huì)受制于計(jì)算機(jī)硬件過度擬合（Overfitting）的頻現(xiàn)維度災(zāi)難（Curse of Dim

6、ensionality）分布式存儲(chǔ)帶來的數(shù)據(jù)訪問困難分析時(shí)間太長(zhǎng)，影響后期的實(shí)時(shí)決策效果SVM在DM中的優(yōu)勢(shì)和不足優(yōu)勢(shì)：最大間隔的思想更好的泛化能力，有助于解決過度擬合核函數(shù)解決非線性問題的同時(shí)避免維度災(zāi)難二次優(yōu)化存在唯一解，并且可以找到全局最優(yōu)稀疏性支持向量個(gè)數(shù)相對(duì)數(shù)據(jù)集小得多，易于存儲(chǔ)不足：運(yùn)算效率低計(jì)算時(shí)占用資源過大大規(guī)模數(shù)據(jù)下的SVMSVM的核心在于求解一個(gè)QP問題原始問題：等價(jià)問題形式：龐大的核函數(shù)矩陣QQ是一個(gè)LL的矩陣,且不稀疏Q在尋優(yōu)計(jì)算中要經(jīng)常調(diào)用帶來的問題Q無法在內(nèi)存中存儲(chǔ)實(shí)時(shí)計(jì)算Q，帶來效率低下Q太大，使得矩陣運(yùn)算很耗時(shí)分解算法（ Decomposition)思想： 將大

7、型的二次規(guī)劃問題（QP問題）分成若干個(gè)小的QP問題，也就是每次抽取一個(gè)小的工作集（Working Set）來做QP，從而解決內(nèi)存不夠的問題Chunking Boser,Vapnik 1992思想：去掉非SV的（i0）樣本，不影響解缺陷：當(dāng)模型不稀疏的時(shí)候（SVs很多）的時(shí)候，Data Set會(huì)越來越大，以至于無法計(jì)算Boser - A training algorithm for optimal margin classifiers - 1992Chunking with Fixed-size Work SetOsuna 1997思想：同Chunking，但是固定Data Set的大小缺陷：雖

8、然解決了計(jì)算可行的問題，B的大小可能比真正的SV還小Osuna - Training support vector machines:an application to face detection - 1997ShrinkingJoachims 1998思想：邊界支持向量BSVs（aiC的SV）在迭代過程中ai不會(huì)變化，如果找到這些點(diǎn)，并把它們固定為C，可以減少Q(mào)P的規(guī)模缺陷：當(dāng)SVs數(shù)量過多，或者SVs中BSVs較少時(shí)效率不高Joachims - Making large-scale support vector machine learning pratiacal - 1999SMOPl

9、att 1999思想：Data Set的大小設(shè)定為2，可以得到QP的解析解（analytical solution），避免了復(fù)雜的數(shù)值求解缺陷：迭代次數(shù)多，非線性情況下的優(yōu)勢(shì)不明顯Platt - Fast training of support vector machines using sequential minimal optimiztion - 1999分解算法的問題大數(shù)據(jù)集下的SVM的特點(diǎn)：SVs很多上述方法的問題：SVs多時(shí)，收斂的太慢SVs太多時(shí)，測(cè)試速度比較慢，特別是使用非線性核函數(shù)時(shí)想法：壓縮SVs的數(shù)量RSVMReduced SVMY-J.Lee O.L.Mangasari

10、an 2001SIAM International Conference on Data Mining 2001Y.-J.Lee and O.L.Mangasarian. - RSVM:Reduced support vector machines -2001RSVM的基本思路（1）式（2）式（3）式抽取子集R總訓(xùn)練集A中隨機(jī)抽取一個(gè)子集RR的數(shù)目m占總數(shù)目L的110實(shí)質(zhì)上壓縮了SVs的數(shù)目，將SVs限制在R中（4）式削減Q！大幅削減Q的維度（5）式（6）式正方型核長(zhǎng)方形核有約束無約束采用SSVM（Smooth SVM）Y-J.Lee O.L.Mangasarian 1999思想：將約束不等式

11、代人主式，將消去，同時(shí)采用一個(gè)平滑函數(shù)使得主式二次可導(dǎo)，再用Newton下降法，從而將有約束優(yōu)化轉(zhuǎn)化為無約束優(yōu)化，（7）式Y(jié).-J.Lee and O.L.Mangasarian. - SSVM:A smooth support vector machines - 1999實(shí)驗(yàn)結(jié)果（訓(xùn)練時(shí)間）RSVM，SMO，PCG Chunking 算法用于 UCI Adult dataset 的訓(xùn)練時(shí)間Y.-J.Lee and O.L.Mangasarian. - RSVM:Reduced support vector machines -2001實(shí)驗(yàn)結(jié)果（正確率） 數(shù)據(jù)集（數(shù)目，維數(shù)，R的大?。?RSV

12、M 傳統(tǒng)SVMY.-J.Lee and O.L.Mangasarian. - RSVM:Reduced support vector machines -2001疑惑壓縮了SVs的個(gè)數(shù)，甚至是限定在R集中準(zhǔn)確率和速度（訓(xùn)練速度，測(cè)試速度）的雙重提升兩全其美？作者給出的解釋：壓縮SVs的個(gè)數(shù)，避免的了大樣本下的過度擬合（overfitting）問題不同的結(jié)果Kuan-Ming Lin, Chih-Jen Lin 2003A study on reduced support vector machinesIEEE Transactions on Neural Networks, 2003.魚和熊掌不可兼得用實(shí)驗(yàn)分析了RSVM的性能得到以下結(jié)論不論在多大的數(shù)據(jù)集下RSVM和普通SVM相比正確率有所下降，但僅僅 （a little lower）在大型數(shù)據(jù)集或者某些SVs很多的情況下，RSVM體現(xiàn)出很高的效率 ！RSVM總結(jié)思路： 隨機(jī)選擇的一個(gè)較小的子集R，將SVs限定在R中，來壓縮SVs的數(shù)目，從而大大降低Q的規(guī)模，再轉(zhuǎn)化為無約束優(yōu)化問題，用Newton下法降來求解評(píng)價(jià)： 以很小的正確率下降換取效率，是一