Weka與Mahout

一 基於雲計算的海量資料採擷

2008年7 月，《Communications of the ACM》雜誌發表了關於雲計算的專輯，雲計算因其清晰的商業模式而受到廣泛關注，並得到工業和學術界的普遍認可。目前工業界推出的雲計算平臺有Amazon公司的EC2和S3，Google公司的Google Apps Engine, IBM公司的Blue Cloud，Microsoft公司的Windows Azure, Salesforce公司的Sales Force, VMware公司的vCloud，Apache軟體開源組織的Hadoop等。在國內，IBM與無錫市共建了雲計算中心，中石化集團成功應用IBM的雲計算方案建立起一個企業雲計算平臺。阿裡巴巴集團於2009年初在南京建立電子商務雲計算中心。

嚴格的講，雲計算是一種新穎的商業計算模型，它可以將計算任務分佈在大量互連的電腦上，使各種應用系統能夠根據需要獲取計算資源、存儲資源和其他服務資源。Google公司的雲平臺是最具代表性的雲計算技術之一，包括四個方面的主要技術：Google檔案系統GFS、平行計算模型MapReduce、結構化資料表BigTable和分散式的鎖管理Chubby。基於以上技術，雲計算可以為海量資料處理和分析提供一種高效的計算平臺。簡單來說，將海量資料分解為相同大小、分佈存儲，然後採用MapReduce模型進行並行化程式設計，這種技術使Google公司在搜尋引擎應用中得到了極大的成功。

然而MapReduce計算模型適合結構一致的海量資料，且要求計算簡單。對於大量的資料密集型應用（如資料採擷任務），往往涉及到資料降維、程式反覆運算、近似求解等等複雜的演算法，計算非常困難。因此，基於雲計算的海量資料採擷技術成為了工業界和學術界共同關心的熱點技術之一。

分散式運算是解決海量資料採擷任務，提高海量資料採擷效率的方法之一。目前，分散式資料採擷技術主要有基於主體（agent）的分散式資料採擷、基於網格的分散式資料採擷、基於雲的分散式資料採擷等。海量資料採擷另一個核心問題是資料採擷演算法的並行化。圖1給出基於雲計算的海量資料採擷服務的層次結構圖。

圖1  基於雲計算的海量資料採擷服務的層次結構圖

中國移動研究院從2007年3月份啟動“大雲”的研發工作。2008年，中國移動研究院已建設有256個節點、1024個CPU、256TB存儲的雲平臺。中國移動“大雲”平臺主要為資料採擷、系統評估、搜索等應用提供計算服務。在開源 Hadoop雲平臺上，中科院計算所研製了並行資料採擷工具平臺PDMiner。針對海量資料，雲計算分別從資料採擷模式和方法等方面進行相關的研究。與此同時，中科院深圳先進研究院還研製了一個分散式資料採擷系統AlphaMiner。

    本文首先討論了海量資料採擷的研究熱點；其次基於開放的Hadoop平臺，討論並行資料採擷演算法工具箱和資料採擷雲的設計。

二 技術熱點

    雲 計算是一種資源利用模式，它能以簡便的途徑和以按需的方式通過網路訪問可配置的計算資源，快速部署資源。在這種模式中，應用、資料和資源以服務的方式通過 網路提供給使用者使用。大量的計算資源組成資源池，用於動態創建高度虛擬化的資源以供用戶使用。但對於海量資料分析任務，雲平臺缺乏針對海量資料採擷和分析 演算法的並行化實現。因此面向海量資料採擷的新型雲計算模式，主要包括海量資料預處理、適合於雲計算的海量資料採擷平行算法、新型海量資料採擷方法和雲計算 資料採擷工具箱等技術。

    （1）海量數據預處理。為了適合並行處理，雲平臺應可以提供海量資料的概念分層組織以及海量資料的並行載入；並實現高維度約減和資料稀疏化技術，提高資料管理和挖掘的效率。

    （2）適合於雲計算的海量資料採擷平行算法。海量資料採擷的關鍵問題是資料採擷演算法的並行化。而雲計算採用MapReduce 等 新型計算模型，這意味著現有的資料採擷演算法和並行化策略不能直接應用於雲計算平臺下進行海量資料採擷，需要進行一定的改造。因此需要深入研究資料採擷演算法 的並行化策略，繼而實現高效的雲計算並行海量資料採擷演算法。並行海量資料採擷演算法包括並行關聯規則演算法、並行分類演算法和並行聚類演算法，用於分類或預測模 型、資料總結、資料聚類、關聯規則、序列模式、依賴關係或依賴模型、異常和趨勢發現等。在此基礎上，針對海量資料採擷演算法的特點對已有的雲計算模型進行優 化和擴充，使其更適用于海量資料採擷。

    （3）新型海量資料採擷方法。新 型海量資料採擷方法包含面向同構資料、異構資料和跨域資料的不同的資料採擷新方法。在同構海量資料採擷系統中，各個節點存儲的資料都具有相同的屬性空間。 雲平臺採用集成學習的方式來生成最終的全域預測模型。並在同構節點的元學習基礎上，實現資料採擷增量學習方法，已滿足即時要求；在異構海量資料採擷系統 中，雲平臺根據資料模態，將資料節點分類，並提供異構資料相關性度量和集成機制。除此之外，由於資料採擷應用的特殊性，雲平臺能提供對海量資料移轉挖掘方 法的支撐，以便擴充雲計算環境下資料採擷應用的適用範圍，更好地滿足資料採擷終端使用者的需求。

    （4）並行資料採擷工具箱。海量資料採擷應用系統開發前，都會對採用的演算法進行性能的評估。目前已有的Weka工具箱採用的是單機演算法，不能應用在基於雲計算的海量資料採擷應用中。Apache組織近年來組織了Mahout開源專案，設計用於雲平臺的資料採擷演算法。但Mahout專案目前還缺少資料準備、資料展示和使用者交互，還不完全適合海量資料採擷平行算法的性能評估。因此，雲平臺應可以提供一個基於MapReduce計算模型的並行資料採擷工具箱，用於海量資料採擷平行算法的性能評估。

    在網格計算研究中，國際研究者研發了多個基於網格的複雜資料分析任務的服務系統，如Data Mining Grid、Grid Miner等 等。在這些系統中，實現了複雜資料分析任務的工作流定義、資源調度和管理的透明化、具體演算法的註冊和服務化等。以上部分技術可以直接遷移到雲計算平臺上， 但由於雲計算模式和資料採擷服務的特殊性，仍需在按需服務、多工調度和分配等技術上進行進一步的突破。具體技術內容包括：

    （1）按需服務的自治計算模式。 將海量資料採擷任務的服務化，設計並實現並行資料採擷軟體自配置、自優化、自修復和自保護的方法，以及自我調整使用者需求的資料採擷服務的自動發現和組合演算法。

    （2）多工的動態分配機制。海量資料採擷應用往往是資料密集，且具有突發性的特點；除此之外，不同的資料採擷應用對演算法精度、性能要求也不一致。因此，基於雲計算的海量資料採擷必須優化負載調節的策略與任務遷移策略等。

    （3）資料採擷服務的動態按需遷移。雲 平臺提供支援海量資料採擷任務的服務重定位方法，即當一個伺服器上運行中的服務按需遷移到另一個伺服器上去時，能同時有效地為後繼工作流任務提供可用的資 源空間，並滿足整合伺服器資源的需要。在資源管理和配置中，針對海量資料的大規模和異構等特點，運用虛擬化技術進行存儲管理，並設計一種新型的動態遷移架 構。

    （4）複雜資料採擷任務服務平臺。 在Hadoop等雲平臺上，設計支援複雜資料採擷任務服務化的中介軟體系統。支援複雜資料分析任務的流定義、複雜資料分析任務的動態配置、平行算法的註冊、雲平臺資源的調度和管理的透明化，最終實現複雜資料分析任務的按需服務。

Weka是由新西蘭Waikato大學研發的資料處理和知識發現套裝軟體。其可以實現資料預處理、聚類、分類、回歸、特徵選擇、視覺化等各種資料採擷的任務。Weka被廣泛用於各種資料採擷任務中演算法的評估。但其中資料採擷演算法的實現是基於單機實現的。與Weka不同的是，Apache組織基於Hadoop平臺的，採用MapReduce計算模型，實現大量機器學習演算法的並行化，並將其封裝在Mahout項目。但由於Mahout並不提供一種圖形介面交互，使用者需要大量手工配置資料和參數，同時目前實現的並行資料採擷演算法也不完全。

表1  Weka與Mahout主要異同

	資料來源	資料格式	資料存儲	演算法	使用者介面
Weka	支持文字檔：包括本地的資料檔案以及網路資料檔案； 支援資料庫檔：通過JDBC連接。	標準格式是Arff,行表示實例，列表示各個屬性。另外還支持CSV，C45以及BSI。	資料檔案載入存儲於記憶體之中	在單機上實現分類、聚類、關聯規則等資料採擷演算法	包括發現模式的表示，資料採擷原語的操作，介面功能主要包括4個部分：Simple CLI、Explorer、Experimenter Knowledge Flow
Mahout	僅支持文字檔	每個演算法自己根據演算法的情況自己設定的檔案格式	存儲於Hdfs上	基於MapReduce計算模型，實現….	命令列交互

mahout:

1.可大規模分散式運算

2.目標物件是程式開發人員

3.與hadoop和lucene有很好的介面

4.是圍繞著可擴展的演算法和介面特殊設計的

5.命令列和API

6.Apache  license

weka:

1.記憶體消耗厲害

2.目標物件是資料採擷分析人員

3.有大量的演算法集

4.GUI

5.GPL

正反例極不平衡的資料集的採樣

此類不均衡問題是“分類型資料採擷”（我就直接按照目標變數來定義概念了哈）實際專案中很常見的一類問題，畢竟生活中像UCI上那種正負類樣本點數據基本差不-多的情況是很少見的，至少在我所做過的兩個項目中，所遇到的資料情況都是應該屬於類極不均衡問題（正負類樣本點的比例大致在1:100左右，在這裡我將少類樣本-定義為正類點，多類樣本定義為負類點。由於項目原因，就不介紹具體背景了，反正無非就是在客戶中發現有具有潛在風險的客戶之類的）。
    在有些演算法中（主要是基於資訊熵或GINI係數進行分類的演算法），這種類極不均衡問題會帶來演算法失效的結果，例如：在使用DT演算法進行分類的時候，類不均衡問題-會使得樹無法繼續生長，當然，通過調整閾值或設定樹的最小層數也可以強制使得樹繼續生長，但對於大量的資料而言，這種做法多少有些拍腦袋的嫌疑。
    在有些演算法中（主要是基於樣本點距分劃面距離的演算法），類不均衡問題會導致分劃面的位置過於偏向於正類點的位置，例如：SVM方法中，以線性SVM為例，如果對-於正負類樣本點採用同樣的懲罰係數的話，可能最終結果是分化面基本上把幾乎所有的正類點和負類點都劃在分劃面的一側，使得最終的結果都為負類點。
    在這些演算法中，對於不均衡類問題都無法得到很好的解決。其實從一種比較通俗的角度來想，資料採擷無非就是定義一個“規則”，這個規則或者是一堆的IF…ELSE-，或者就直接是一個簡單或複雜的函數式，或是兩者的結合。資料採擷的訓練過程就是尋找一個在全域或局部最優的“規則”來刻畫某種想要的“模式（PATTERN）-”（在本案例中就是刻畫潛在的風險客戶的特徵）。當類不均衡問題出現的時候，模型在訓練過程中，最終找到的那種刻畫方式往往會傾向於最顯著的那種“規則”，當負-類點的的數量多到一定程度的時候，便把正類點的那種“模式”給淹沒掉了。所以我們必須採用抽樣的方式來使得正類點的“模式”再顯現出來，所以，一種解決方式便是-通過分層抽樣，來使得正負類樣本點的數量比例維持在一個可接受的範圍內，（聽過一種說法是維持在1:10左右，但不知道這個比例也是拍腦袋得來的還是怎麼證明得-到的）。

    我的做法是這樣的——如果正例（有欺詐）與反例（無欺詐）的原始比例是1：1000——因為決策樹既能分辨正例又能分辨反例，如果反例的某些個分支既大又精確，那就把反例的那些個分支統統砍掉，砍完了（即把欺詐概率極小的人排掉）再用剩下的數據（此時再無抽騙的風險了）做一個決策樹

[轉]統計學習那些事

SVM的基本原理普遍表述為，SVM通過非線性變換把原空間映射到高維空間，然後在這個高維空間構造線性分類器，因為在高維空間資料點更容易分開。 甚至有部分學者認為SVM可以克服維數災難(curse of dimensionality)。如果這樣理解SVM的基本原理，我覺得還沒有看到問題的本質。因為這個看法不能解釋下面的事實：SVM在高維空間裡構建 分類器後，為什麼這個分類器不會對原空間的資料集Overfitting呢？要理解SVM的成功，我覺得可以考慮以下幾個方面：第一，SVM求解最優分類 器的時候，使用了L2-norm regularization，這個是控制Overfitting的關鍵。第二，SVM不需要顯式地構建非線性映射，而是通過Kernel trick完成，這樣大大提高運算效率。第三，SVM的優化問題屬於一個二次規劃（Quadratic programming），優化專家們為SVM這個特殊的優化問題設計了很多巧妙的解法，比如SMO（Sequential minimal optimization）解法。第四，Vapnika的統計學習理論為SVM提供了很好的理論背景（這點不能用來解釋為什麼SVM這麼popular， 因為由理論匯出的bound太loose）。於是SVM成功了，火得一塌糊塗！
再說Boosted Trees。它基本的想法是通過對弱分類器的組合來構造一個強分類器。所謂“弱”就是比隨機猜要好一點點；“強”就是強啦。這個想法可以追溯到由Leslie Valiant教 授（2010年圖靈獎得主）在80年代提出的probably approximately correct learning (PAC learning) 理論。不過很長一段時間都沒有一個切實可行的辦法來實現這個理想。細節決定成敗，再好的理論也需要有效的演算法來執行。終於功夫不負有 心人， Schapire在1996年提出一個有效的演算法真正實現了這個夙願，它的名字叫AdaBoost。AdaBoost把多個不同的決策樹用一種非隨機的方 式組合起來，表現出驚人的性能！第一，把決策樹的準確率大大提高，可以與SVM媲美。第二，速度快，且基本不用調參數。第三，幾乎不 Overfitting。我估計當時Breiman和Friedman肯定高興壞了，因為眼看著他們提出的CART正在被SVM比下去的時 候，AdaBoost讓決策樹起死回生！Breiman情不自禁地在他的論文裡讚揚AdaBoost是最好的現貨方法（off-the-shelf，即 “拿下了就可以用”的意思）。其實在90年代末的時候，大家對AdaBoost為什麼有如此神奇的性能迷惑不解。1999年，Friedman的一篇技術 報告“Additive logistic regression: a statistical view of boosting”解釋了大部分的疑惑（沒有解釋AdaBoost為什麼不容易Overfitting，這個問題好像至今還沒有定論），即搞清楚了 AdaBoost在優化什麼指標以及如何優化的。基於此，Friedman提出了他的GBM（Gradient Boosting Machine，也叫MART或者TreeNet）。幾乎在同時，Breiman另闢蹊徑，結合他的Bagging (Bootstrap aggregating) 提出了Random Forest （今天微軟的Kinect裡面就採用了Random Forest，相關論文Real-time Human Pose Recognition in Parts from Single Depth Images是CVPR2011的best paper）。
有一個關於Gradient Boosting細節不得不提。Friedman在做實驗的時候發現，把一棵新生成的決策樹，記為f_m，加到當前模型之前，在這棵決策樹前乘以一個小的 數，即v×f_m（比如v=0.01），再加入到當前模型中，往往大大提高模型的準確度。他把這個叫做“Shrinkage”。接下 來，Hastie，Tibshirani和Friedman進一步發現（我發現大師們都是親自動手寫程式做實驗的），如果把具有Shrinkage的 Gradient Boosting應用到線性回歸中時，得到的Solution Path與Lasso的Solution Path驚人地相似(如圖所示)！他們把這一結果寫在了ESL的第一版裡，並推測這二者存在著某種緊密的聯繫，但精確的數學關係他們當時也不清楚。 Tibshirani說他們還請教了斯坦福的優化大師（我估計是Stephen Boyd），但還是沒有找到答案。



後來Tibshirani找到自己的恩師Efron。Tibshirani在“The Science of Bradley Efron”這本書的序言裡寫道，“He sat down and pretty much single-handedly solved the problem. Along the way, he developed a new algorithm, ‘least angle regression,’ which is interesting in its own right, and sheds great statistical insight on the Lasso.”我就不逐字逐句翻譯了，大意是：Efron獨自擺平了這個問題，與此同時發明了“Least angle regression (LAR)”。Efron結論是Lasso和Boosting的確有很緊密的數學聯繫，它們都可以通過修改LAR得到。更令人驚歎的是LAR具有非常明確 的幾何意義。於是，Tibshirani在序言中還有一句，“In this work, Brad shows his great mathematical power–not the twentieth century, abstract kind of math, but the old-fashioned kind: geometric insight and analysis.”讀Prof Efron的文章，可以感受到古典幾何學與現代統計學的結合之美（推薦大家讀讀Efron教授2010年的一本新書Large-Scale Inference，希望以後有機會再寫寫這方面的體會）！總之，Efron的這篇文章是現代統計學的里程碑，它結束了一個時代，開啟了另一個時代。
這裡，想補充說明一下Lasso的身世，它的全稱是The Least Absolute Shrinkage and Selection Operator，讀音不是[‘læso]而是[læ’su:]，有中文翻譯為“套索”，個人覺得這個翻譯不好，太遠離它本來的含義，不如就用 Lasso。Tibshrani自己說他的Lasso是受到Breiman的Non-Negative Garrote（NNG）的啟發。 Lasso把NNG的兩步合併為一步，即L1-norm regularization。Lasso的巨大優勢在於它所構造的模型是Sparse的，因為它會自動地選擇很少一部分變數構造模型。現在，Lasso 已經家喻戶曉了，但是Lasso出生後的頭兩年卻很少有人問津。後來Tibshirani自己回憶時說，可能是由下面幾個原因造成的：1. 速度問題：當時電腦求解Lasso的速度太慢；2. 理解問題：大家對Lasso模型的性質理解不夠（直到Efron的LAR出來後大家才搞明白）；3. 需求問題：當時還沒有遇到太多高維資料分析的問題，對Sparsity的需求似乎不足。Lasso的遭遇似乎在闡釋我們已經熟知的一些道理： 1.千里馬常有，而伯樂不常有（沒有Efron的LAR，Lasso可能很難有這麼大的影響力）。2.時勢造英雄（高維資料分析的問題越來越多，比如 Bioinformatics領域）。3.金子總是會閃光的。
LAR把Lasso （L1-norm regularization）和Boosting真正的聯繫起來，如同打通了任督二脈（數學細節可以參考本人的一個小結[1]， 當然最好還是親自拜讀Efron的原著）。LAR結束了一個晦澀的時代：在LAR之前，有關Sparsity的模型幾乎都是一個黑箱，它們的數學性質（更 不要談古典的幾何性質了）幾乎都是缺失。LAR開啟了一個光明的時代：有關Sparsity的好文章如雨後春筍般地湧現，比如Candes和Tao的 Dantzig Selector。伯克利大學的Bin Yu教授稱“Lasso, Boosting and Dantzig are three cousins”。近年來興起的Compressed sensing（Candes & Tao, Donoho）也與LAR一脈相承，只是更加強調L1-norm regularization其他方面的數學性質，比如Exact Recovery。我覺得這是一個問題的多個方面，Lasso關注的是構建模型的準確性，Compressed sensing關注的是變數選擇的準確性。由此引起的關於Sparsity的研究，猶如黃河氾濫，一發不可收拾。比如Low-rank 逼近是把L1-norm從向量到矩陣的自然推廣（現在流行的“使用者推薦系統”用到的Collaborative filtering的數學原理源於此）。有興趣的童鞋可以參考我個人的小結[2]。
還必須提到的是演算法問題。我個人覺得，一個好的模型，如果沒有一個快速準確的演算法作為支撐的話，它最後可能什麼也不是。看看Lasso頭幾年的冷遇 就知道了。LAR的成功除了它漂亮的幾何性質之外，還有它的快速演算法。LAR的演算法複雜度相當於最小二乘法的複雜度，這幾乎已經把Lasso問題的求解推 向極致。這一記錄在2007年被Friedman的Coordinate Descent（CD）刷新，至今沒人打破。Hastie教授趣稱這個為“FFT（Friedman + Fortran + Tricks）”。因為CD對Generalized Lasso問題並不能一網打盡，許多凸優化解法應運而生，如Gradient Projection， Proximal methods，ADMM (Alternating Direction Method of Multipliers)， (Split) Bregman methods，Nesterov’s method (一階梯度法中最優的收斂速度，Candes 的很多套裝軟體都根據這個方法設計) 等等。哪個方法更好呢？這個就像問“誰的武功天下第一”一樣。我只能回答“王重陽以後再也沒有天下第一了，東邪西毒南帝北丐，他們各有各的所長，有的功夫 是這個人擅長一些，而另外幾門功夫又是另一個人更擅長一些”。有關L1的演算法可能還會大量湧現，正如優化大師Stephen Boyd所說（2010年9月28日）：“God knows the last thing we need is another algorithm for the Lasso.”
最後我想以討論“模糊系統”和“統計學習”來結尾。這個話題非常具有爭議，我就冒天下之大不諱吧，談一談我這幾年的學習體會。記得十年前，立新老師 曾經寫過一篇文章《模糊系統：挑戰與機遇並存——十年研究之感悟》，發表在2001年《自動化學報》上。我2005年看到的時候，敬仰之情，猶如滔滔江 水。立新老師曾經有這麼一句話：“If a method works well in practice, there must be some theoretical reasons for its success.”2005年的時候，我開始問自己什麼使模糊系統的成功？立新老師認為有如下幾個原因：1.模糊系統的通用逼近性能（Universal Approximator）；2.模糊系統快速的構造演算法，比如他自己的WM方法，Roger Jang的ANFIS等等；3.結果的可解釋性；4.利用各種不同形式的資訊。
下面我談談自己的看法，第一，通用逼近性能當然是一個好的性質，它表明模糊系統是很flexible的，但flexible的結構太多了，比如神經 網路。問題往往不在flexible，而在太flexible導致overfitting。就如同SVM一樣，沒有L2-norm regularization，實踐中的性能就會變得很差。第二，快速演算法，這是好的方法必備的，SVM，Boosting，Random Forest的演算法都很快，而且可以直接用到高維，這一點上，我沒有看到模糊系統的優勢。第三，可解釋性：模糊系統對低維資料（比如2-4維）的確具有好 的解釋性（因為IF-THEN規則的前提和結論都很簡潔），但這個時候其它工具也可以做得到，比如Gradient Boosting和Random Forests（很多例子可以在ESL這本書裡看到）。第四，充分的利用各種資訊。立新老師指的是IF-THEN規則可以比較自由靈活的加入先驗知識，並 在他的書裡面詳細給出實例。遺憾的是，這些例子都在處理低維空間的問題。如何用IF-THEN規則解構高維空間呢？我個人看不到它們特殊的優勢。然而，在 統計學習裡，利用不同的先驗知識處理高維空間的例子比比皆是，比如Sparsity，group-structure，smoothness等等。現在舉 一個Gradient Boosting  machine（GBM，也叫MART）的例子來說明我的觀點。根據Lasso和Boosting的關係，可以知道GBM已經用到了Sparsity的性 質（L1-norm regularization）。GBM有兩個參數可以反映我們的先驗知識。第一個參數是深度（depth），控制每棵決策樹的深度 。如果深度為1，即樹樁結構（Stump），表明GBM將採用加法模型（Generalized Additive model），即不考慮變數之間的互動式作用（Interaction）；如果深度大於1，則考慮互動式作用。因為互動式作用在非線性建模中比較重要，如 異或（XOR）問題，沒有考慮互動式作用將失敗得很慘，所以這個參數設置反映了對非線性建模的先驗。第二個參數是Shrinkage的大小。假設深度選取 是合理的，在雜訊比較小的時候，沒有Shrinkage會比較好；雜訊比較大的時候，有Shrinkage會好一些。實踐中，使用GBM對高維資料分析， 試錯法（Trial and error）很容易使用，因為就這兩個參數（通常depth=3～4；實際資料的雜訊往往比較大，推薦設置Shrinkage=0.01）。模型構建好之 後，GBM會告訴你哪些變數是重要的，變數之間的互動式作用如何等等，這樣模型的結果也是比較容易理解。Random Forests也有相似的功能。好了，最後借Hastie教授的一幅圖來總結一下，無疑，GBM（MART）是他們的最愛，也是我的最愛。

[轉]決策樹模型組合之隨機森林與GBDT

SVM的基本原理普遍表述為，SVM通過非線性變換把原空間映射到高維空間，然後在這個高維空間構造線性分類器，因為在高維空間資料點更容易分開。 甚至有部分學者認為SVM可以克服維數災難(curse of dimensionality)。如果這樣理解SVM的基本原理，我覺得還沒有看到問題的本質。因為這個看法不能解釋下面的事實：SVM在高維空間裡構建 分類器後，為什麼這個分類器不會對原空間的資料集Overfitting呢？要理解SVM的成功，我覺得可以考慮以下幾個方面：第一，SVM求解最優分類 器的時候，使用了L2-norm regularization，這個是控制Overfitting的關鍵。第二，SVM不需要顯式地構建非線性映射，而是通過Kernel trick完成，這樣大大提高運算效率。第三，SVM的優化問題屬於一個二次規劃（Quadratic programming），優化專家們為SVM這個特殊的優化問題設計了很多巧妙的解法，比如SMO（Sequential minimal optimization）解法。第四，Vapnika的統計學習理論為SVM提供了很好的理論背景（這點不能用來解釋為什麼SVM這麼popular， 因為由理論匯出的bound太loose）。於是SVM成功了，火得一塌糊塗！
再說Boosted Trees。它基本的想法是通過對弱分類器的組合來構造一個強分類器。所謂“弱”就是比隨機猜要好一點點；“強”就是強啦。這個想法可以追溯到由Leslie Valiant教 授（2010年圖靈獎得主）在80年代提出的probably approximately correct learning (PAC learning) 理論。不過很長一段時間都沒有一個切實可行的辦法來實現這個理想。細節決定成敗，再好的理論也需要有效的演算法來執行。終於功夫不負有 心人， Schapire在1996年提出一個有效的演算法真正實現了這個夙願，它的名字叫AdaBoost。AdaBoost把多個不同的決策樹用一種非隨機的方 式組合起來，表現出驚人的性能！第一，把決策樹的準確率大大提高，可以與SVM媲美。第二，速度快，且基本不用調參數。第三，幾乎不 Overfitting。我估計當時Breiman和Friedman肯定高興壞了，因為眼看著他們提出的CART正在被SVM比下去的時 候，AdaBoost讓決策樹起死回生！Breiman情不自禁地在他的論文裡讚揚AdaBoost是最好的現貨方法（off-the-shelf，即 “拿下了就可以用”的意思）。其實在90年代末的時候，大家對AdaBoost為什麼有如此神奇的性能迷惑不解。1999年，Friedman的一篇技術 報告“Additive logistic regression: a statistical view of boosting”解釋了大部分的疑惑（沒有解釋AdaBoost為什麼不容易Overfitting，這個問題好像至今還沒有定論），即搞清楚了 AdaBoost在優化什麼指標以及如何優化的。基於此，Friedman提出了他的GBM（Gradient Boosting Machine，也叫MART或者TreeNet）。幾乎在同時，Breiman另闢蹊徑，結合他的Bagging (Bootstrap aggregating) 提出了Random Forest （今天微軟的Kinect裡面就採用了Random Forest，相關論文Real-time Human Pose Recognition in Parts from Single Depth Images是CVPR2011的best paper）。
有一個關於Gradient Boosting細節不得不提。Friedman在做實驗的時候發現，把一棵新生成的決策樹，記為f_m，加到當前模型之前，在這棵決策樹前乘以一個小的 數，即v×f_m（比如v=0.01），再加入到當前模型中，往往大大提高模型的準確度。他把這個叫做“Shrinkage”。接下 來，Hastie，Tibshirani和Friedman進一步發現（我發現大師們都是親自動手寫程式做實驗的），如果把具有Shrinkage的 Gradient Boosting應用到線性回歸中時，得到的Solution Path與Lasso的Solution Path驚人地相似(如圖所示)！他們把這一結果寫在了ESL的第一版裡，並推測這二者存在著某種緊密的聯繫，但精確的數學關係他們當時也不清楚。 Tibshirani說他們還請教了斯坦福的優化大師（我估計是Stephen Boyd），但還是沒有找到答案。



後來Tibshirani找到自己的恩師Efron。Tibshirani在“The Science of Bradley Efron”這本書的序言裡寫道，“He sat down and pretty much single-handedly solved the problem. Along the way, he developed a new algorithm, ‘least angle regression,’ which is interesting in its own right, and sheds great statistical insight on the Lasso.”我就不逐字逐句翻譯了，大意是：Efron獨自擺平了這個問題，與此同時發明了“Least angle regression (LAR)”。Efron結論是Lasso和Boosting的確有很緊密的數學聯繫，它們都可以通過修改LAR得到。更令人驚歎的是LAR具有非常明確 的幾何意義。於是，Tibshirani在序言中還有一句，“In this work, Brad shows his great mathematical power–not the twentieth century, abstract kind of math, but the old-fashioned kind: geometric insight and analysis.”讀Prof Efron的文章，可以感受到古典幾何學與現代統計學的結合之美（推薦大家讀讀Efron教授2010年的一本新書Large-Scale Inference，希望以後有機會再寫寫這方面的體會）！總之，Efron的這篇文章是現代統計學的里程碑，它結束了一個時代，開啟了另一個時代。
這裡，想補充說明一下Lasso的身世，它的全稱是The Least Absolute Shrinkage and Selection Operator，讀音不是[‘læso]而是[læ’su:]，有中文翻譯為“套索”，個人覺得這個翻譯不好，太遠離它本來的含義，不如就用 Lasso。Tibshrani自己說他的Lasso是受到Breiman的Non-Negative Garrote（NNG）的啟發。 Lasso把NNG的兩步合併為一步，即L1-norm regularization。Lasso的巨大優勢在於它所構造的模型是Sparse的，因為它會自動地選擇很少一部分變數構造模型。現在，Lasso 已經家喻戶曉了，但是Lasso出生後的頭兩年卻很少有人問津。後來Tibshirani自己回憶時說，可能是由下面幾個原因造成的：1. 速度問題：當時電腦求解Lasso的速度太慢；2. 理解問題：大家對Lasso模型的性質理解不夠（直到Efron的LAR出來後大家才搞明白）；3. 需求問題：當時還沒有遇到太多高維資料分析的問題，對Sparsity的需求似乎不足。Lasso的遭遇似乎在闡釋我們已經熟知的一些道理： 1.千里馬常有，而伯樂不常有（沒有Efron的LAR，Lasso可能很難有這麼大的影響力）。2.時勢造英雄（高維資料分析的問題越來越多，比如 Bioinformatics領域）。3.金子總是會閃光的。
LAR把Lasso （L1-norm regularization）和Boosting真正的聯繫起來，如同打通了任督二脈（數學細節可以參考本人的一個小結[1]， 當然最好還是親自拜讀Efron的原著）。LAR結束了一個晦澀的時代：在LAR之前，有關Sparsity的模型幾乎都是一個黑箱，它們的數學性質（更 不要談古典的幾何性質了）幾乎都是缺失。LAR開啟了一個光明的時代：有關Sparsity的好文章如雨後春筍般地湧現，比如Candes和Tao的 Dantzig Selector。伯克利大學的Bin Yu教授稱“Lasso, Boosting and Dantzig are three cousins”。近年來興起的Compressed sensing（Candes & Tao, Donoho）也與LAR一脈相承，只是更加強調L1-norm regularization其他方面的數學性質，比如Exact Recovery。我覺得這是一個問題的多個方面，Lasso關注的是構建模型的準確性，Compressed sensing關注的是變數選擇的準確性。由此引起的關於Sparsity的研究，猶如黃河氾濫，一發不可收拾。比如Low-rank 逼近是把L1-norm從向量到矩陣的自然推廣（現在流行的“使用者推薦系統”用到的Collaborative filtering的數學原理源於此）。有興趣的童鞋可以參考我個人的小結[2]。
還必須提到的是演算法問題。我個人覺得，一個好的模型，如果沒有一個快速準確的演算法作為支撐的話，它最後可能什麼也不是。看看Lasso頭幾年的冷遇 就知道了。LAR的成功除了它漂亮的幾何性質之外，還有它的快速演算法。LAR的演算法複雜度相當於最小二乘法的複雜度，這幾乎已經把Lasso問題的求解推 向極致。這一記錄在2007年被Friedman的Coordinate Descent（CD）刷新，至今沒人打破。Hastie教授趣稱這個為“FFT（Friedman + Fortran + Tricks）”。因為CD對Generalized Lasso問題並不能一網打盡，許多凸優化解法應運而生，如Gradient Projection， Proximal methods，ADMM (Alternating Direction Method of Multipliers)， (Split) Bregman methods，Nesterov’s method (一階梯度法中最優的收斂速度，Candes 的很多套裝軟體都根據這個方法設計) 等等。哪個方法更好呢？這個就像問“誰的武功天下第一”一樣。我只能回答“王重陽以後再也沒有天下第一了，東邪西毒南帝北丐，他們各有各的所長，有的功夫 是這個人擅長一些，而另外幾門功夫又是另一個人更擅長一些”。有關L1的演算法可能還會大量湧現，正如優化大師Stephen Boyd所說（2010年9月28日）：“God knows the last thing we need is another algorithm for the Lasso.”
最後我想以討論“模糊系統”和“統計學習”來結尾。這個話題非常具有爭議，我就冒天下之大不諱吧，談一談我這幾年的學習體會。記得十年前，立新老師 曾經寫過一篇文章《模糊系統：挑戰與機遇並存——十年研究之感悟》，發表在2001年《自動化學報》上。我2005年看到的時候，敬仰之情，猶如滔滔江 水。立新老師曾經有這麼一句話：“If a method works well in practice, there must be some theoretical reasons for its success.”2005年的時候，我開始問自己什麼使模糊系統的成功？立新老師認為有如下幾個原因：1.模糊系統的通用逼近性能（Universal Approximator）；2.模糊系統快速的構造演算法，比如他自己的WM方法，Roger Jang的ANFIS等等；3.結果的可解釋性；4.利用各種不同形式的資訊。
下面我談談自己的看法，第一，通用逼近性能當然是一個好的性質，它表明模糊系統是很flexible的，但flexible的結構太多了，比如神經 網路。問題往往不在flexible，而在太flexible導致overfitting。就如同SVM一樣，沒有L2-norm regularization，實踐中的性能就會變得很差。第二，快速演算法，這是好的方法必備的，SVM，Boosting，Random Forest的演算法都很快，而且可以直接用到高維，這一點上，我沒有看到模糊系統的優勢。第三，可解釋性：模糊系統對低維資料（比如2-4維）的確具有好 的解釋性（因為IF-THEN規則的前提和結論都很簡潔），但這個時候其它工具也可以做得到，比如Gradient Boosting和Random Forests（很多例子可以在ESL這本書裡看到）。第四，充分的利用各種資訊。立新老師指的是IF-THEN規則可以比較自由靈活的加入先驗知識，並 在他的書裡面詳細給出實例。遺憾的是，這些例子都在處理低維空間的問題。如何用IF-THEN規則解構高維空間呢？我個人看不到它們特殊的優勢。然而，在 統計學習裡，利用不同的先驗知識處理高維空間的例子比比皆是，比如Sparsity，group-structure，smoothness等等。現在舉 一個Gradient Boosting  machine（GBM，也叫MART）的例子來說明我的觀點。根據Lasso和Boosting的關係，可以知道GBM已經用到了Sparsity的性 質（L1-norm regularization）。GBM有兩個參數可以反映我們的先驗知識。第一個參數是深度（depth），控制每棵決策樹的深度 。如果深度為1，即樹樁結構（Stump），表明GBM將採用加法模型（Generalized Additive model），即不考慮變數之間的互動式作用（Interaction）；如果深度大於1，則考慮互動式作用。因為互動式作用在非線性建模中比較重要，如 異或（XOR）問題，沒有考慮互動式作用將失敗得很慘，所以這個參數設置反映了對非線性建模的先驗。第二個參數是Shrinkage的大小。假設深度選取 是合理的，在雜訊比較小的時候，沒有Shrinkage會比較好；雜訊比較大的時候，有Shrinkage會好一些。實踐中，使用GBM對高維資料分析， 試錯法（Trial and error）很容易使用，因為就這兩個參數（通常depth=3～4；實際資料的雜訊往往比較大，推薦設置Shrinkage=0.01）。模型構建好之 後，GBM會告訴你哪些變數是重要的，變數之間的互動式作用如何等等，這樣模型的結果也是比較容易理解。Random Forests也有相似的功能。好了，最後借Hastie教授的一幅圖來總結一下，無疑，GBM（MART）是他們的最愛，也是我的最愛。

[轉]邏輯回歸與決策樹在分類上的一些區別

行銷預測模型的目標變數很多為一種狀態或類型，如客戶“買”還是“不買”、客戶選擇上網方式為 “寬頻”還是“撥號”、行銷戰通道是郵件、電話、還是網路。我們把這類問題統稱為 “分類”。決策樹和邏輯回歸都是解決“分類”問題的高手。用不同的演算法解答同樣的問題，自然引出了兩者孰優孰劣的討論，但迄今為止，仍然沒有一個明確的結 論。出現這種情況是意料之中的，因為兩者的具體表現取決於資料狀況和挖掘人員的水準。從演算法本身看，決策樹和回歸各有優勢，因此最好的應用不是兩者擇一， 而是相互取捨，利用一方的長處彌補另一方的不足。

在進一步討論之前，讓我們來看一下邏輯回歸和決策樹的主要差別。

有 些分歧是表面的，例如決策樹可以對付缺失值，而邏輯回歸需要挖掘人員預先對缺失資料進行處理。但實際上決策樹同樣要對缺失值做出某種假設和處理。例如 CART在遇到一個變數中有缺失情況時，是用次級變數進行替換切分。這種做法在邏輯回歸中也可以辦到，但需要單獨的程式設計。而在決策樹中，這一步已經嵌入軟 件的演算法引擎。

從 實質上看，決策樹和邏輯回歸的分歧是：1．邏輯回歸對資料整體結構的分析優於決策樹，而決策樹對局部結構的分析優於邏輯回歸。2．邏輯回歸擅長分析線性關 系，而決策樹對線性關係的把握較差。雖然對付非線性關係是決策樹的強項，但是很多非線性關係完全可以用線性關係作為近似，而且效果很好。線性關係在實踐中 有很多優點：簡潔，易理解，可以在一定程度上防止對資料的過度擬合。3．邏輯回歸對極值比較敏感，容易受極端值的影響，而決策樹在這方面表現較好。

兩 者的差別主要來自演算法邏輯。決策樹由於採用分割的方法，所以能夠深入資料細部，但同時失去了對全域的把握。一個分層一旦形成，它和別的層面或節點的關係就 被切斷了，以後的挖掘只能在局部中進行。同時由於切分，樣本數量不斷萎縮，所以無法支援對多變數的同時檢驗。而邏輯回歸，始終著眼整個資料的擬合，所以對 全域把握較好。但無法兼顧局部資料，或者說缺乏探查局部結構的內在機制。

除 外，邏輯回歸和決策樹還有一些應用上的區別。決策樹的結果和邏輯回歸相比略顯粗糙。邏輯回歸原則上可以提供資料中每個觀察點的概率，而決策樹只能把挖掘對 象分為有限的概率組群。比如決策樹確定17個節點，全部人口就只能有17個概率，在應用上受到一定限制。就操作來說，決策樹比較容易上手，需要的資料預處 理較少，而邏輯回歸則要求一定的訓練和技巧。

對 於兩者間互補或增強，主要思路是利用決策樹對局部資料結構優越的把握能力增加邏輯回歸的效力。在具體做法上有幾種，一種是從決策樹分析中找出資料局部結 構，作為在邏輯回歸中構建依變數（interaction)的依據。另一種是在需要對預測因數進行離散化處理時，利用決策樹分析決定最佳切分點。還有一種 是把決策樹分類的最終結果作為預測變數，和其他協變數一起代入回歸模型，又稱為“嫁接式模型”。從理論上講，嫁接模型綜合了決策樹和邏輯回歸的優點。最終 節點包含了資料中重要的局部結構，而協變數可以拾補被決策樹遺漏的資料整體結構。

嫁 接模型是一個很巧妙的設計，但是在實踐中並沒有得到普遍的認同。由於決策樹已經對資料進行了最大限度的擬合，所以留給協變數的餘地很小。換句話說，把決策 樹的最終節點作為預測因數，就可能找不出還有獨立作用的協變數。而沒有協變數，邏輯回歸實際只是決策樹的重複。再有，由於節點是多個屬性的綜合，不易解 釋。每個節點到底代表什麼不明確，由此限制了這種方法的推廣。