1、數(shù)據(jù)挖掘中的SVM,oneroadsmth 2003.12,1.Jiawei Han Data Minining Concept and Techniques,什么是數(shù)據(jù)挖掘,數(shù)據(jù)挖掘（Data Mining）就是從觀測到的數(shù)據(jù)集（經(jīng)常是很龐大的），抽取出潛在的、有價值的信息1 數(shù)據(jù)集：傳統(tǒng)的數(shù)據(jù)庫，數(shù)據(jù)倉庫，Web 三大學科的交叉： 機器學習 統(tǒng)計學 數(shù)據(jù)庫技術,數(shù)據(jù)挖掘的圖示,Data Warehouse,Prepared data,Data,Patterns,Knowledge,Knowledge Base,數(shù)據(jù)挖掘的主要任務,分類 Classification 銀行客戶關系分類 預測

2、Prediction 股票趨勢預測，GDP預測 關聯(lián)規(guī)則 Association Rules 購物籃分析（60買面包的人會買黃油） 聚類 Clustering 金融欺詐行為檢測,數(shù)據(jù)挖掘中的ML方法,人工神經(jīng)網(wǎng)絡 Neural Networks 決策樹 Decision Trees 規(guī)則歸納 Rule Induction 最近鄰方法 Nearest Neighbor Method 遺傳算法 Genetic Algorithms 支持向量機 Support Vector Machines 粗糙集 Rough Set 貝葉斯信念網(wǎng) Bayesian Belief Networks 模糊邏輯 Fuz

3、zy Logic,www.KD,SVM在DM中的使用情況,DM的門戶網(wǎng)站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,數(shù)據(jù)挖掘的特點,最大的特點：海量數(shù)據(jù)集 美國零售商沃爾瑪每天大約2千萬筆的交易，一年的客戶交易數(shù)據(jù)庫容量超過11TB AT&T公司，1億電話用戶，每天3億次的呼叫特征數(shù)據(jù) 美國宇航局NASA的地球觀測系統(tǒng)每小時生成幾個GB的原始數(shù)據(jù) 人類基因工程中超過3.3109個核苷酸的數(shù)據(jù)庫 其它特點：較高維度，有噪聲，屬性值缺失,帶來的問題,傳統(tǒng)的統(tǒng)計方法沒法應用 經(jīng)典的ML方法

6、的使用會受制于計算機硬件 過度擬合（Overfitting）的頻現(xiàn) 維度災難（Curse of Dimensionality） 分布式存儲帶來的數(shù)據(jù)訪問困難 分析時間太長，影響后期的實時決策效果,SVM在DM中的優(yōu)勢和不足,優(yōu)勢： 最大間隔的思想更好的泛化能力，有助于解決過度擬合 核函數(shù)解決非線性問題的同時避免維度災難 二次優(yōu)化存在唯一解，并且可以找到全局最優(yōu) 稀疏性支持向量個數(shù)相對數(shù)據(jù)集小得多，易于存儲 不足： 運算效率低 計算時占用資源過大,大規(guī)模數(shù)據(jù)下的SVM,SVM的核心在于求解一個QP問題 原始問題： 等價問題形式：,龐大的核函數(shù)矩陣Q,Q是一個LL的矩陣,且不稀疏 Q在尋優(yōu)計算中要

7、經(jīng)常調用 帶來的問題 Q無法在內存中存儲 實時計算Q，帶來效率低下 Q太大，使得矩陣運算很耗時,分解算法（ Decomposition),思想： 將大型的二次規(guī)劃問題（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的規(guī)模 缺陷： 當SVs數(shù)量過多，或者SVs中BSVs較少時效率不高,Platt - Fast training of support vector machines using sequential minimal optimiztion - 1999,SMO,Platt 1999 思想： Data Set的大小設定為2，可以得到QP的解析解（analytical solution），避免了復雜的數(shù)值求解 缺陷： 迭代次數(shù)多，非線性情況下的優(yōu)勢不明顯,分解算法的問題,大數(shù)據(jù)集下的S

10、VM的特點：SVs很多 上述方法的問題： SVs多時，收斂的太慢 SVs太多時，測試速度比較慢，特別是使用非線性核函數(shù)時 想法：壓縮SVs的數(shù)量,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的數(shù)目m占總數(shù)目

11、L的110 實質上壓縮了SVs的數(shù)目，將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 思想： 將約束不等式代人主式，將消去，同時采用一個平滑函數(shù)使得主式二次可導，再用Newton下降法，從而將有約束優(yōu)化轉化為無約束優(yōu)化，,（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,實驗結果（正確率）,數(shù)據(jù)集（數(shù)目，維數(shù)，R的大?。?RSVM 傳統(tǒng)SVM,疑惑,壓縮了SVs的個數(shù)，甚至是限定在R集中 準確率和速度（訓練速度，測試速度）的雙重提升 兩全其美？ 作者給出的解釋： 壓縮SVs的個數(shù)，避免的了大樣本下的

13、過度擬合（overfitting）問題,不同的結果,Kuan-Ming Lin, Chih-Jen Lin 2003 A study on reduced support vector machines IEEE Transactions on Neural Networks, 2003.,魚和熊掌不可兼得,用實驗分析了RSVM的性能得到以下結論 不論在多大的數(shù)據(jù)集下RSVM和普通SVM相比正確率有所下降，但僅僅 （a little lower） 在大型數(shù)據(jù)集或者某些SVs很多的情況下，RSVM體現(xiàn)出很高的效率 ！,RSVM總結,思路： 隨機選擇的一個較小的子集R，將SVs限定在R中，來壓縮SVs的數(shù)目，從而大大降低Q的規(guī)模，再轉化為無約束優(yōu)化問題，用Newton下法降來求解 評價： 以很小的正確率下降換取效率，是一種適