圖挖掘與深度學(xué)習(xí)算法
近年來由于大數(shù)據(jù)的興起，和一些優(yōu)化算法上的突破，深度學(xué)習(xí)迅速崛起，影響了很多機(jī)器學(xué)習(xí)的領(lǐng)域，比如圖像識(shí)別，語音識(shí)別，自然語言處理（NLP）等等。受自然語言處理中的詞嵌入（Word embedding）模型的啟發(fā)，一類被稱為網(wǎng)絡(luò)嵌入（Network embedding）的社交網(wǎng)路模型越來越受到學(xué)術(shù)和工業(yè)界的重視。
圖挖掘算法
Page ranking, label propagation, connected component, triangle count
Page ranking
PageRank算法是一種鏈接分析算法，由Google提出并用于標(biāo)識(shí)網(wǎng)頁重要性。PageRank算法基于兩個(gè)假設(shè)：
1）入鏈數(shù)量假設(shè)：如果一個(gè)網(wǎng)頁的入鏈數(shù)量越多，則其重要程度越高。
2）入鏈質(zhì)量假設(shè)：高質(zhì)量的網(wǎng)頁為其鏈接的頁面帶去更多權(quán)重。
以上兩個(gè)假設(shè)分別對(duì)應(yīng)小白規(guī)則一和規(guī)則二?；谶@兩條假設(shè)，PageRank算法為每個(gè)頁面設(shè)置初始權(quán)重值，根據(jù)網(wǎng)頁間的鏈接關(guān)系，在多輪迭代中更新每個(gè)網(wǎng)頁的權(quán)重，直至各頁面的權(quán)重值穩(wěn)定。不考慮作弊的情況，我們通常將最終權(quán)重值越高的節(jié)點(diǎn)視為越可靠網(wǎng)頁。
Label propagation
標(biāo)簽傳播算法（label propagation）的核心思想非常簡(jiǎn)單：相似的數(shù)據(jù)應(yīng)該具有相同的label。LP算法包括兩大步驟：1）構(gòu)造相似矩陣；2）勇敢的傳播吧。
Label Propagation算法是一種基于標(biāo)簽傳播的局部社區(qū)劃分算法。對(duì)于網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)，在初始階段，Label Propagation算法對(duì)每一個(gè)節(jié)點(diǎn)一個(gè)唯一的標(biāo)簽，在每一個(gè)迭代的過程中，每一個(gè)節(jié)點(diǎn)根據(jù)與其相連的節(jié)點(diǎn)所屬的標(biāo)簽改變自己的標(biāo)簽，更改的原則是選擇與其相連的節(jié)點(diǎn)中所屬標(biāo)簽最多的社區(qū)標(biāo)簽為自己的社區(qū)標(biāo)簽，這便是標(biāo)簽傳播的含義。隨著社區(qū)標(biāo)簽的不斷傳播，最終緊密連接的節(jié)點(diǎn)將有共同的標(biāo)簽。
Label Propagation算法最大的優(yōu)點(diǎn)是其算法過程比較簡(jiǎn)單，想比較于優(yōu)化模塊度的過程，算法速度非?？?。Label Propagation算法利用網(wǎng)絡(luò)的結(jié)構(gòu)指導(dǎo)標(biāo)簽的傳播過程，在這個(gè)過程中無需優(yōu)化任何函數(shù)。在算法開始前我們不必要知道社區(qū)的個(gè)數(shù)，隨著算法的迭代，在最終的過程中，算法將自己決定社區(qū)的個(gè)數(shù)。
連通分支
連通分支（Connected Component）是指：在一個(gè)圖中，某個(gè)子圖的任意兩點(diǎn)有邊連接，并且該子圖去剩下的任何點(diǎn)都沒有邊相連。
Triangle count 三角形計(jì)數(shù)
Triangle Count在社交網(wǎng)絡(luò)分析中是非常有用的。這個(gè)三角形是一個(gè)三結(jié)點(diǎn)的小圖，其中結(jié)點(diǎn)兩兩相連。假如，在Facebook上，你認(rèn)識(shí)兩個(gè)校友，而這兩個(gè)校友彼此有相互認(rèn)識(shí)，那么你們?nèi)齻€(gè)就組成了一個(gè)三角形。像這樣的，社交網(wǎng)絡(luò)擁有越多的三角形，其聯(lián)系也就業(yè)緊密。
Triangle Count的算法思想如下：
? 計(jì)算每個(gè)結(jié)點(diǎn)的鄰結(jié)點(diǎn)，
? 統(tǒng)計(jì)對(duì)每條邊計(jì)算交集，并找出交集中id大于前兩個(gè)結(jié)點(diǎn)id的結(jié)點(diǎn)，
? 對(duì)每個(gè)結(jié)點(diǎn)統(tǒng)計(jì)Triangle總數(shù)，注意只統(tǒng)計(jì)符合計(jì)算方向的Triangle Count。
深度學(xué)習(xí)Deep Learning
簡(jiǎn)單來說，深度學(xué)習(xí)模型是大而深的人工神經(jīng)網(wǎng)絡(luò)。 神經(jīng)網(wǎng)絡(luò)（“NN”）可以很好地呈現(xiàn)在有向無環(huán)圖中：輸入層接收信號(hào)向量; 一個(gè)或多個(gè)隱藏層處理前一層的輸出。
因?yàn)楝F(xiàn)在有了大量數(shù)據(jù)和巨大計(jì)算能力， 深度學(xué)習(xí)模型越來越受到人們的關(guān)注。大而深的神經(jīng)網(wǎng)絡(luò)在每層中有更多的層+更多的節(jié)點(diǎn)，這導(dǎo)致要調(diào)整的指數(shù)級(jí)更多的參數(shù)。 沒有足夠的數(shù)據(jù)，我們無法有效地學(xué)習(xí)參數(shù)。 如果沒有強(qiáng)大的計(jì)算機(jī)，學(xué)習(xí)將會(huì)過于緩慢和不足。
下面是幾種主要的深度學(xué)習(xí)模型
1.Convolutional Neural Network 卷積神經(jīng)網(wǎng)絡(luò)
卷積神經(jīng)網(wǎng)絡(luò)是“CNN”的縮寫，是一種前饋人工神經(jīng)網(wǎng)絡(luò)，其神經(jīng)元之間的連接模式受到視覺皮層系統(tǒng)組織的啟發(fā)。初級(jí)視覺皮層（V1）從視網(wǎng)膜的原始視覺輸入中進(jìn)行邊緣檢測(cè)。次級(jí)視覺皮層（V2），也稱為前皮質(zhì)，接收來自V1的邊緣特征，并提取簡(jiǎn)單的視覺特性，例如方向，空間頻率和顏色。 可視區(qū)域V4處理更復(fù)雜的對(duì)象屬性。所有處理過的視覺特征都流入最終邏輯單元，即顳下回（IT），用于對(duì)象識(shí)別。
卷積是一個(gè)數(shù)學(xué)術(shù)語，這里指的是兩個(gè)矩陣之間的操作。 卷積層具有固定的小矩陣，也稱為內(nèi)核或?yàn)V波器。
卷積和合并（或上圖中的“子采樣”）層的作用類似于V1，V2和V4視覺皮層單元，響應(yīng)特征提取。 對(duì)象識(shí)別推理發(fā)生在后來的全連接層中，這些層采用了提取的特征。
遞歸神經(jīng)網(wǎng)絡(luò) Recurrent Neural Network
序列模型通常被設(shè)計(jì)為將輸入序列轉(zhuǎn)換為輸出序列。 遞歸神經(jīng)網(wǎng)絡(luò)，簡(jiǎn)稱“RNN”，適用于此目的，并在手寫識(shí)別，語音識(shí)別和機(jī)器翻譯等問題上有了巨大的改進(jìn)。
自動(dòng)編碼 Autoencode
自動(dòng)編碼器用于無監(jiān)督學(xué)習(xí), 它旨在學(xué)習(xí)用低維數(shù)據(jù)表示高維數(shù)據(jù)集。
自動(dòng)編碼器模型試圖學(xué)習(xí)近似函數(shù)f（x）≈x 重現(xiàn)輸入數(shù)據(jù)。但是，它受到中間瓶頸層的限制，節(jié)點(diǎn)數(shù)量非常少。 由于容量有限，模型被迫形成非常有效的數(shù)據(jù)編碼，這實(shí)際上是我們學(xué)到的低維代碼。
強(qiáng)化（深度）學(xué)習(xí)Reinforcement (Deep) Learning
RL是機(jī)器學(xué)習(xí)的子領(lǐng)域，它允許機(jī)器和軟件代理自動(dòng)確定給定上下文中的最佳行為，目標(biāo)是最大化由給定度量測(cè)量的長(zhǎng)期性能。深度增強(qiáng)學(xué)習(xí)Deep Reinforcement Learning是將深度學(xué)習(xí)與增強(qiáng)學(xué)習(xí)結(jié)合起來從而實(shí)現(xiàn)從Perception感知到Action動(dòng)作的端對(duì)端學(xué)習(xí)的一種全新的算法。簡(jiǎn)單的說，就是和人類一樣，輸入感知信息比如視覺，然后通過深度神經(jīng)網(wǎng)絡(luò)，直接輸出動(dòng)作，中間沒有hand-crafted工作。深度增強(qiáng)學(xué)習(xí)具備使機(jī)器人實(shí)現(xiàn)完全自主的學(xué)習(xí)一種甚至多種技能的潛力。
上面這張圖（來自David Silver）可以很清楚的看到整個(gè)交互過程。事實(shí)上，這就是人與環(huán)境交互的一種模型化表示。在每個(gè)時(shí)間點(diǎn)time-step Agent都會(huì)從可以選擇的動(dòng)作集合A中選擇一個(gè)執(zhí)行.這個(gè)動(dòng)作集合可以是連續(xù)的比如機(jī)器人的控制也可以是離散的比如游戲中的幾個(gè)按鍵。動(dòng)作集合的數(shù)量將直接影響整個(gè)任務(wù)的求解難度，因此DeepMind才從玩最簡(jiǎn)單的游戲做起。
那么知道了整個(gè)過程，任務(wù)的目標(biāo)就出來了，那就是要能獲取盡可能多的reward。沒有目標(biāo)，控制也就無從談起，因此，獲取reward就是一個(gè)量化的標(biāo)準(zhǔn)，reward越多，就表示執(zhí)行得越好。每個(gè)時(shí)間片，Agent都是根據(jù)當(dāng)前的觀察來確定下一步的動(dòng)作。每次的觀察就作為Agent的所處的狀態(tài)state，因此，狀態(tài)State和動(dòng)作Action存在映射關(guān)系，也就是一個(gè)state可以對(duì)應(yīng)一個(gè)action，或者對(duì)應(yīng)不同動(dòng)作的概率（常常用概率來表示，概率最高的就是最值得執(zhí)行的動(dòng)作）。那么state到action的過程就稱之為一個(gè)策略Policy。
生成性對(duì)抗網(wǎng)絡(luò)Generative Adversarial Network
生成對(duì)抗網(wǎng)絡(luò)（GAN）是由兩個(gè)網(wǎng)絡(luò)組成的深度神經(jīng)網(wǎng)絡(luò)體系結(jié)構(gòu)，將一個(gè)網(wǎng)絡(luò)與另一個(gè)網(wǎng)絡(luò)相互對(duì)立（因此稱為“對(duì)抗性”）。
GAN的潛力巨大，因?yàn)樗麄兛梢詫W(xué)習(xí)模仿任何數(shù)據(jù)分布。 也就是說，GAN可以被教導(dǎo)在任何領(lǐng)域創(chuàng)造類似于我們自己的世界：圖像，音樂，演講，散文。 從某種意義上說，他們是機(jī)器人藝術(shù)家，他們的作品令人印象深刻 - 甚至令人痛苦。要理解GAN，你應(yīng)該知道生成算法是如何工作的，為此，將它們與判別算法進(jìn)行對(duì)比是有益的。 判別算法試圖對(duì)輸入數(shù)據(jù)進(jìn)行分類; 也就是說，給定數(shù)據(jù)實(shí)例的功能，它們會(huì)預(yù)測(cè)數(shù)據(jù)所屬的標(biāo)簽或類別。
例如，給定電子郵件中的所有單詞，判別算法可以預(yù)測(cè)該郵件是垃圾郵件還是非垃圾郵件。 垃圾郵件是標(biāo)簽之一，從電子郵件收集的單詞包是構(gòu)成輸入數(shù)據(jù)的功能。 當(dāng)以數(shù)學(xué)方式表達(dá)此問題時(shí)，標(biāo)簽稱為y，并且要素稱為x。 公式p（y | x）用于表示“y給定x的概率”，在這種情況下，它將轉(zhuǎn)換為“基于郵件的內(nèi)容，這份電子郵件是垃圾郵件的概率”。
因此，判別算法將特征映射到標(biāo)簽。 他們只關(guān)心這種相關(guān)性。 考慮生成算法的一種方法是他們做相反的事情。 他們嘗試預(yù)測(cè)給定某個(gè)標(biāo)簽的特征，而不是預(yù)測(cè)給定某些特征的標(biāo)簽。
生成算法試圖回答的問題是：假設(shè)這封電子郵件是垃圾郵件，這些功能的可能性有多大？ 雖然判別模型關(guān)心y和x之間的關(guān)系，但是生成模型關(guān)心“你如何得到x。”它們?cè)试S你捕獲p（x | y），x給出y的概率，或給出類的特征的概率。 （也就是說，生成算法也可以用作分類器。恰好它們可以做的不僅僅是對(duì)輸入數(shù)據(jù)進(jìn)行分類。）
另一種思考方式是將判別與生成區(qū)分開來，如下所示：
判別模型學(xué)習(xí)了類之間的界限
生成模型模擬各個(gè)類的分布
一個(gè)神經(jīng)網(wǎng)絡(luò)，稱為生成器，生成新的數(shù)據(jù)實(shí)例，而另一個(gè)神經(jīng)網(wǎng)絡(luò)，鑒別器，評(píng)估它們的真實(shí)性; 即，鑒別器決定它所評(píng)論的每個(gè)數(shù)據(jù)實(shí)例是否屬于實(shí)際訓(xùn)練數(shù)據(jù)集。
以下是GAN采取的步驟：
生成器接收隨機(jī)數(shù)并返回圖像。
將生成的圖像與從實(shí)際數(shù)據(jù)集中獲取的圖像流一起饋送到鑒別器中。
鑒別器接收真實(shí)和假圖像并返回概率，0到1之間的數(shù)字，1表示真實(shí)性的預(yù)測(cè)，0表示假。
所以你有一個(gè)雙反饋循環(huán)：
鑒別器處于反饋循環(huán)中，具有圖像的基本事實(shí)，我們知道這一點(diǎn)。
發(fā)生器與鑒別器一起處于反饋回路中。
你可以將GAN看作是貓與老鼠游戲中偽造者和警察的組合，其中偽造者正在學(xué)習(xí)傳遞虛假筆記，并且警察正在學(xué)習(xí)如何檢測(cè)它們。兩者都是動(dòng)態(tài)的;也就是警察也在訓(xùn)練中（也許中央銀行正在標(biāo)記掉掉的賬單），并且每一方都在不斷升級(jí)中學(xué)習(xí)對(duì)方的方法。
鑒別器網(wǎng)絡(luò)是標(biāo)準(zhǔn)卷積網(wǎng)絡(luò)，可以對(duì)饋送給它的圖像進(jìn)行分類，二項(xiàng)分類器將圖像標(biāo)記為真實(shí)或偽造。在某種意義上，生成器是反卷積網(wǎng)絡(luò)：當(dāng)標(biāo)準(zhǔn)卷積分類器采用圖像并對(duì)其進(jìn)行下采樣以產(chǎn)生概率時(shí)，生成器采用隨機(jī)噪聲矢量并將其上采樣到圖像。第一個(gè)通過下采樣技術(shù)（如maxpooling）丟棄數(shù)據(jù)，第二個(gè)生成新數(shù)據(jù)。
兩個(gè)網(wǎng)都試圖在零和游戲中優(yōu)化不同的和相反的目標(biāo)函數(shù)或損失函數(shù)。這實(shí)際上是一個(gè)演員評(píng)論模型。當(dāng)鑒別器改變其行為時(shí)，發(fā)生器也是如此，反之亦然。他們的損失相互沖突。
Deep learning 用途
1. 分類 classification
所有分類任務(wù)都取決于標(biāo)記的數(shù)據(jù)集; 也就是說，人類必須將他們的知識(shí)傳遞給數(shù)據(jù)集，以便神經(jīng)元學(xué)習(xí)標(biāo)簽和數(shù)據(jù)之間的相關(guān)性。 這被稱為監(jiān)督學(xué)習(xí)。
檢測(cè)面部，識(shí)別圖像中的人物，識(shí)別面部表情（生氣，快樂）
識(shí)別圖像中的物體（停車標(biāo)志，行人，車道標(biāo)記......）
識(shí)別視頻中的手勢(shì)
檢測(cè)語音，識(shí)別發(fā)言者，將語音轉(zhuǎn)錄為文本，識(shí)別語音中的情感
將文本分類為垃圾郵件（在電子郵件中）或欺詐性（在保險(xiǎn)索賠中）; 識(shí)別文本中的情緒（客戶反饋）
人類可以生成的任何標(biāo)簽，您關(guān)心的任何結(jié)果以及與數(shù)據(jù)相關(guān)的任何結(jié)果都可用于訓(xùn)練神經(jīng)網(wǎng)絡(luò)。
2. 聚類 Clustering
聚類或分組是對(duì)相似性的檢測(cè)。 深度學(xué)習(xí)不需要標(biāo)簽來檢測(cè)相似性。 沒有標(biāo)簽的學(xué)習(xí)被稱為無監(jiān)督學(xué)習(xí)。 未標(biāo)記的數(shù)據(jù)是世界上大多數(shù)數(shù)據(jù)。 機(jī)器學(xué)習(xí)的一個(gè)定律是：算法可以訓(xùn)練的數(shù)據(jù)越多，它就越準(zhǔn)確。 因此，無監(jiān)督學(xué)習(xí)有可能產(chǎn)生高度準(zhǔn)確的模型。
搜索：比較文檔，圖像或聲音以表示類似的項(xiàng)目。
異常檢測(cè)：檢測(cè)相似性的另一面是檢測(cè)異?；虍惓Ｐ袨?。 在許多情況下，異常行為與您想要檢測(cè)和預(yù)防的事物高度相關(guān)，例如欺詐。
3. 預(yù)測(cè)分析：回歸 Predictive Analytics: Regressions
通過分類，深度學(xué)習(xí)能夠在例如圖像中的像素和人的名稱之間建立相關(guān)性。 你可以稱之為靜態(tài)預(yù)測(cè)。 出于同樣的原因，暴露于足夠的正確數(shù)據(jù)，深度學(xué)習(xí)能夠建立當(dāng)前事件和未來事件之間的相關(guān)性。 它可以在過去和未來之間進(jìn)行回歸。 從某種意義上說，未來的事件就像標(biāo)簽一樣。 深度學(xué)習(xí)并不一定關(guān)心時(shí)間，或者事情尚未發(fā)生。 給定時(shí)間序列，深度學(xué)習(xí)可以讀取一串?dāng)?shù)字并預(yù)測(cè)下一個(gè)最可能發(fā)生的數(shù)字。
硬件故障（數(shù)據(jù)中心，制造，運(yùn)輸）
健康故障（中風(fēng)，基于重要統(tǒng)計(jì)數(shù)據(jù)的心臟病發(fā)作和來自可穿戴設(shè)備的數(shù)據(jù)）
客戶流失（根據(jù)Web活動(dòng)和元數(shù)據(jù)預(yù)測(cè)客戶離開的可能性）
員工流動(dòng)（同上，但員工）
我們?cè)侥茴A(yù)測(cè)，我們就越能預(yù)防。 通過神經(jīng)網(wǎng)絡(luò)，我們正在走向一個(gè)意外減少的世界。 不是零意外，只是略微減少。 我們也正在走向一個(gè)智能代理的世界，它將神經(jīng)網(wǎng)絡(luò)與強(qiáng)化學(xué)習(xí)等其他算法相結(jié)合，以實(shí)現(xiàn)目標(biāo)。
工具
Tensorflow
TensorFlow可能是最著名的深度學(xué)習(xí)框架; 它由Google開發(fā)和維護(hù)。 它是用C ++ / Python編寫的，提供Python，Java，Go和JavaScript API。目前，TensorFlow聚集了最大的深度學(xué)習(xí)社區(qū)，因此有很多視頻，在線課程，教程等等。 它支持在多個(gè)GPU上運(yùn)行模型，甚至可以在計(jì)算集群中的多臺(tái)機(jī)器上分割單個(gè)計(jì)算圖。
PyTorch
PyTorch是由Facebook的人工智能研究小組發(fā)布的，基于Torch（之前的Facebook Lua框架）。 它是動(dòng)態(tài)圖的主要代表。PyTorch是pythonic，非常適合開發(fā)人員。 PyTorch中的內(nèi)存使用對(duì)任何神經(jīng)網(wǎng)絡(luò)都非常有效。 它也被稱為比TensorFlow快一點(diǎn)。
Gradient Boosting Decision Tree（GBDT） 梯度下降樹
決策樹是一種基本的分類與回歸方法。決策樹模型具有分類速度快，模型容易可視化的解釋，但是同時(shí)是也有容易發(fā)生過擬合，雖然有剪枝，但也是差強(qiáng)人意。
提升方法（boosting）在分類問題中，它通過改變訓(xùn)練樣本的權(quán)重（增加分錯(cuò)樣本的權(quán)重，減小分隊(duì)樣本的的權(quán)重），學(xué)習(xí)多個(gè)分類器，并將這些分類器線性組合，提高分類器性能。boosting數(shù)學(xué)表示為：
其中w是權(quán)重，?是弱分類器的集合，可以看出最終就是基函數(shù)的線性組合。于是決策樹與boosting結(jié)合產(chǎn)生許多算法，主要有提升樹、GBDT等。
1.1 Gradient boosting
Gradient Boosting是一種Boosting的方法，它主要的思想是，每一次建立模型是在之前建立模型損失函數(shù)的梯度下降方向。損失函數(shù)是評(píng)價(jià)模型性能（一般為擬合程度+正則項(xiàng)），認(rèn)為損失函數(shù)越小，性能越好。而讓損失函數(shù)持續(xù)下降，就能使得模型不斷改性提升性能，其最好的方法就是使損失函數(shù)沿著梯度方向下降（講道理梯度方向上下降最快）。Gradient Boost是一個(gè)框架，里面可以套入很多不同的算法
1.2 提升樹-boosting tree
以決策樹為基函數(shù)的提升方法稱為提升樹，其決策樹可以是分類樹OR回歸樹。提升樹模型可以表
示為決策樹的加法模型。
2. Gradient boosting decision tree (GBDT) 梯度下降樹
梯度提升決策樹GBDT(Gradient Boosting Decision Tree)最早由Friedman文章“Greedy Function Approximation: A Gradient Boosting Machine”提出這個(gè)概念。GBDT中的樹用的是CART回歸樹（不是分類樹），GBDT用來做?回歸預(yù)測(cè)，調(diào)整后也可以用于分類。由于GBDT中的CART樹，在模型訓(xùn)練的時(shí)候，需要逐個(gè)訓(xùn)練樣本進(jìn)行計(jì)算，模型的訓(xùn)練時(shí)間相當(dāng)之長(zhǎng)。因此，這個(gè)也決定了GBDT不適合實(shí)時(shí)的線上訓(xùn)練，更加適用于離散的場(chǎng)景。
GBDT的思想使其具有天然優(yōu)勢(shì)可以發(fā)現(xiàn)多種有區(qū)分性的特征以及特征組合。Facebook(Practical Lessons From Predicting Clicks on Ads at Facebook)使用其來自動(dòng)發(fā)現(xiàn)有效的特征、特征組合，來作為LR模型中的特征，以提高 CTR預(yù)估（Click-Through Rate Prediction）的準(zhǔn)確性。GBDT在萬能的淘寶搜索及預(yù)測(cè)業(yè)務(wù)上也發(fā)揮了重要作用。
GBDT 雖然是個(gè)強(qiáng)力的模型，但卻有著一個(gè)致命的缺陷，不能用類似 mini batch 的方式來訓(xùn)練，需要對(duì)數(shù)據(jù)進(jìn)行無數(shù)次的遍歷。如果想要速度，就需要把數(shù)據(jù)都預(yù)加載在內(nèi)存中，但這樣數(shù)據(jù)就會(huì)受限于內(nèi)存的大小；如果想要訓(xùn)練更多的數(shù)據(jù)，就要使用外存版本的決策樹算法。雖然外存算法也有較多優(yōu)化，SSD 也在普及，但在頻繁的 IO 下，速度還是比較慢的。
工作過程實(shí)例
以年齡預(yù)測(cè)為例，A,B,C,D四個(gè)人，他們的年齡分別是14,16,24,26。其中A、B分別是高一和高三學(xué)生；C,D分別是應(yīng)屆畢業(yè)生和工作兩年的員工。如果是用一棵傳統(tǒng)的回歸決策樹來訓(xùn)練，會(huì)得到如下圖1所示結(jié)果
現(xiàn)在我們使用GBDT來做這件事，由于數(shù)據(jù)太少，我們限定葉子節(jié)點(diǎn)做多有兩個(gè)，即每棵樹都只有一個(gè)分枝，并且限定只學(xué)兩棵樹。我們會(huì)得到如下圖2所示結(jié)果：
在第一棵樹分枝和圖1一樣，由于A,B年齡較為相近，C,D年齡較為相近，他們被分為兩撥，每撥用平均年齡作為預(yù)測(cè)值。此時(shí)計(jì)算殘差（殘差的意思就是： A的預(yù)測(cè)值 + A的殘差 = A的實(shí)際值），所以A的殘差就是16-15=1（注意，A的預(yù)測(cè)值是指前面所有樹累加的和，這里前面只有一棵樹所以直接是15，如果還有樹則需要都累加起來作為A的預(yù)測(cè)值）。進(jìn)而得到A,B,C,D的殘差分別為-1,1，-1,1。然后我們拿殘差替代A,B,C,D的原值，到第二棵樹去學(xué)習(xí)，如果我們的預(yù)測(cè)值和它們的殘差相等，則只需把第二棵樹的結(jié)論累加到第一棵樹上就能得到真實(shí)年齡了。這里的數(shù)據(jù)顯然是我可以做的，第二棵樹只有兩個(gè)值1和-1，直接分成兩個(gè)節(jié)點(diǎn)。此時(shí)所有人的殘差都是0，即每個(gè)人都得到了真實(shí)的預(yù)測(cè)值。
換句話說，現(xiàn)在A,B,C,D的預(yù)測(cè)值都和真實(shí)年齡一致了。：
A: 14歲高一學(xué)生，購(gòu)物較少，經(jīng)常問學(xué)長(zhǎng)問題；預(yù)測(cè)年齡A = 15 – 1 = 14
B: 16歲高三學(xué)生；購(gòu)物較少，經(jīng)常被學(xué)弟問問題；預(yù)測(cè)年齡B = 15 + 1 = 16
C: 24歲應(yīng)屆畢業(yè)生；購(gòu)物較多，經(jīng)常問師兄問題；預(yù)測(cè)年齡C = 25 – 1 = 24
D: 26歲工作兩年員工；購(gòu)物較多，經(jīng)常被師弟問問題；預(yù)測(cè)年齡D = 25 + 1 = 26
LightGBM
LightGBM采用Histogram算法，其思想是將連續(xù)的浮點(diǎn)特征離散成k個(gè)離散值，并構(gòu)造寬度為k的Histogram。然后遍歷訓(xùn)練數(shù)據(jù)，統(tǒng)計(jì)每個(gè)離散值在直方圖中的累計(jì)統(tǒng)計(jì)量。在進(jìn)行特征選擇時(shí)，只需要根據(jù)直方圖的離散值，遍歷尋找最優(yōu)的分割點(diǎn)。
LightGBM增加了針對(duì)于類別特征的決策規(guī)則，這在決策樹上也很好實(shí)現(xiàn)。主要的思想是，在對(duì)類別特征計(jì)算分割增益的時(shí)候，不是按照數(shù)值特征那樣由一個(gè)閾值進(jìn)行切分，而是直接把其中一個(gè)類別當(dāng)成一類，其他的類別當(dāng)成另一類。這實(shí)際上與0/1展開的效果是一樣的。
為了能讓 GBDT 高效地用上更多的數(shù)據(jù)，我們把思路轉(zhuǎn)向了分布式 GBDT， 然后就有了 LightGBM。設(shè)計(jì)的思路主要是兩點(diǎn)，1. 單個(gè)機(jī)器在不犧牲速度的情況下，盡可能多地用上更多的數(shù)據(jù)；2.多機(jī)并行的時(shí)候，通信的代價(jià)盡可能地低，并且在計(jì)算上可以做到線性加速。
基于這兩個(gè)需求，LightGBM 選擇了基于 histogram 的決策樹算法。相比于另一個(gè)主流的算法 pre-sorted（如 xgboost 中的 exact 算法），histogram 在內(nèi)存消耗和計(jì)算代價(jià)上都有不少優(yōu)勢(shì)。
Pre-sorted 算法需要的內(nèi)存約是訓(xùn)練數(shù)據(jù)的兩倍(2 * #data * #features
* 4Bytes)，它需要用32位浮點(diǎn)來保存 feature value，并且對(duì)每一列特征，都需要一個(gè)額外的排好序的索引，這也需要32位的存儲(chǔ)空間。對(duì)于 histogram 算法，則只需要(#data
* #features * 1Bytes)的內(nèi)存消耗，僅為 pre-sorted算法的1/8。因?yàn)?span style="color: rgb(0, 0, 0); font-size: 18px; font-family: "Helvetica Neue", serif;"> histogram 算法僅需要存儲(chǔ) feature
bin value (離散化后的數(shù)值)，不需要原始的 feature value，也不用排序，而 bin
value 用 uint8_t (256bins) 的類型一般也就足夠了。
在計(jì)算上的優(yōu)勢(shì)則主要體現(xiàn)在“數(shù)據(jù)分割”。決策樹算法有兩個(gè)主要操作組成，一個(gè)是“尋找分割點(diǎn)”，另一個(gè)是“數(shù)據(jù)分割”。從算法時(shí)間復(fù)雜度來看，Histogram 算法和 pre-sorted 算法在“尋找分割點(diǎn)”的代價(jià)是一樣的，都是O(#feature*#data)。而在“數(shù)據(jù)分割”時(shí)，pre-sorted 算法需要O(#feature*#data)，而 histogram 算法是O(#data)。因?yàn)?/span> pre-sorted 算法的每一列特征的順序都不一樣，分割的時(shí)候需要對(duì)每個(gè)特征單獨(dú)進(jìn)行一次分割。Histogram算法不需要排序，所有特征共享同一個(gè)索引表，分割的時(shí)候僅需對(duì)這個(gè)索引表操作一次就可以。（更新: 這一點(diǎn)不完全正確，pre-sorted 與 level-wise 結(jié)合的時(shí)候，其實(shí)可以共用一個(gè)索引表(row_idx_to_tree_node_idx)。然后在尋找分割點(diǎn)的時(shí)候，同時(shí)操作同一層的節(jié)點(diǎn)，省去分割的步驟。但這樣做的問題是會(huì)有非常多隨機(jī)訪問，有很大的chche miss，速度依然很慢。）。
最后，在數(shù)據(jù)并行的時(shí)候，用 histgoram 可以大幅降低通信代價(jià)。用 pre-sorted 算法的話，通信代價(jià)是非常大的（幾乎是沒辦法用的）。所以 xgoobst 在并行的時(shí)候也使用 histogram 進(jìn)行通信。
當(dāng)然， histogram 算法也有缺點(diǎn)，它不能找到很精確的分割點(diǎn)，訓(xùn)練誤差沒有 pre-sorted 好。但從實(shí)驗(yàn)結(jié)果來看， histogram 算法在測(cè)試集的誤差和 pre-sorted 算法差異并不是很大，甚至有時(shí)候效果更好。實(shí)際上可能決策樹對(duì)于分割點(diǎn)的精確程度并不太敏感，而且較“粗”的分割點(diǎn)也自帶正則化的效果。
在 histogram 算法之上， LightGBM 進(jìn)行進(jìn)一步的優(yōu)化。首先它拋棄了大多數(shù) GBDT 工具使用的按層生長(zhǎng)
(level-wise) 的決策樹生長(zhǎng)策略，而使用了帶有深度限制的按葉子生長(zhǎng) (leaf-wise) 算法。 level-wise 過一次數(shù)據(jù)可以同時(shí)分裂同一層的葉子，容易進(jìn)行多線程優(yōu)化，不容易過擬合。但實(shí)際上level-wise是一種低效的算法，因?yàn)樗患訁^(qū)分的對(duì)待同一層的葉子，帶來了很多沒必要的開銷。因?yàn)閷?shí)際上很多葉子的分裂增益較低，沒必要進(jìn)行搜索和分裂。leaf-wise則是一種更為高效的策略，每次從當(dāng)前所有葉子中，找到分裂增益最大(一般也是數(shù)據(jù)量最大)的一個(gè)葉子，然后分裂，如此循環(huán)。因此同 level-wise 相比，在分裂次數(shù)相同的情況下，leaf-wise 可以降低更多的誤差，得到更好的精度。leaf-wise 的缺點(diǎn)是可能會(huì)長(zhǎng)出比較深的決策樹，產(chǎn)生過擬合。因此 LightGBM 在leaf-wise 之上增加了一個(gè)最大深度的限制，在保證高效率的同時(shí)防止過擬合。
另一個(gè)比較巧妙的優(yōu)化是 histogram 做差加速。一個(gè)容易觀察到的現(xiàn)象：一個(gè)葉子的直方圖可以由它的父親節(jié)點(diǎn)的直方圖與它兄弟的直方圖做差得到。通常構(gòu)造直方圖，需要遍歷該葉子上的所有數(shù)據(jù)，但直方圖做差僅需遍歷直方圖的 k 個(gè)桶。利用這個(gè)方法，LightGBM 可以在構(gòu)造一個(gè)葉子的直方圖后，可以用非常微小的代價(jià)得到它兄弟葉子的直方圖，在速度上可以提升一倍。
隨機(jī)森林算法
隨機(jī)森林屬于集成學(xué)習(xí)（Ensemble Learning）中的bagging算法。在集成學(xué)習(xí)中，主要分為bagging算法和boosting算法。我們先看看這兩種方法的特點(diǎn)和區(qū)別。
bagging的算法過程如下：
? 從原始樣本集中使用Bootstraping方法隨機(jī)抽取n個(gè)訓(xùn)練樣本，共進(jìn)行k輪抽取，得到k個(gè)訓(xùn)練集。（k個(gè)訓(xùn)練集之間相互獨(dú)立，元素可以有重復(fù)）
? 對(duì)于k個(gè)訓(xùn)練集，我們訓(xùn)練k個(gè)模型（這k個(gè)模型可以根據(jù)具體問題而定，比如決策樹，knn等）
對(duì)于分類問題：由投票表決產(chǎn)生分類結(jié)果；對(duì)于回歸問題：由k個(gè)模型預(yù)測(cè)結(jié)果的均值作為最后預(yù)測(cè)結(jié)果
boosting的算法過程如下：
? 對(duì)于訓(xùn)練集中的每個(gè)樣本建立權(quán)值wi，表示對(duì)每個(gè)樣本的關(guān)注度。當(dāng)某個(gè)樣本被誤分類的概率很高時(shí)，需要加大對(duì)該樣本的權(quán)值。
進(jìn)行迭代的過程中，每一步迭代都是一個(gè)弱分類器。我們需要用某種策略將其組合，作為最終模型。（例如AdaBoost給每個(gè)弱分類器一個(gè)權(quán)值，將其線性組合最為最終分類器。誤差越小的弱分類器，權(quán)值越大）
Bagging，Boosting的主要區(qū)別
? 樣本選擇上：Bagging采用的是Bootstrap隨機(jī)有放回抽樣；而Boosting每一輪的訓(xùn)練集是不變的，改變的只是每一個(gè)樣本的權(quán)重。
? 樣本權(quán)重：Bagging使用的是均勻取樣，每個(gè)樣本權(quán)重相等；Boosting根據(jù)錯(cuò)誤率調(diào)整樣本權(quán)重，錯(cuò)誤率越大的樣本權(quán)重越大。
? 預(yù)測(cè)函數(shù)：Bagging所有的預(yù)測(cè)函數(shù)的權(quán)重相等；Boosting中誤差越小的預(yù)測(cè)函數(shù)其權(quán)重越大。
? 并行計(jì)算：Bagging各個(gè)預(yù)測(cè)函數(shù)可以并行生成；Boosting各個(gè)預(yù)測(cè)函數(shù)必須按順序迭代生成。
下面是將決策樹與這些算法框架進(jìn)行結(jié)合所得到的新的算法：
1）Bagging + 決策樹 = 隨機(jī)森林
2）AdaBoost + 決策樹 = 提升樹
3）Gradient Boosting + 決策樹 = GBDT
決策樹
常用的決策樹算法有ID3，C4.5，CART三種。3種算法的模型構(gòu)建思想都十分類似，只是采用了不同的指標(biāo)。決策樹模型的構(gòu)建過程大致如下：
ID3，C4.5決策樹的生成
輸入：訓(xùn)練集D，特征集A，閾值eps 輸出：決策樹T
? 若D中所有樣本屬于同一類Ck，則T為單節(jié)點(diǎn)樹，將類Ck作為該結(jié)點(diǎn)的類標(biāo)記，返回T
? 若A為空集，即沒有特征作為劃分依據(jù)，則T為單節(jié)點(diǎn)樹，并將D中實(shí)例數(shù)最大的類Ck作為該結(jié)點(diǎn)的類標(biāo)記，返回T
? 否則，計(jì)算A中各特征對(duì)D的信息增益(ID3)/信息增益比(C4.5)，選擇信息增益最大的特征Ag
? 若Ag的信息增益（比）小于閾值eps，則置T為單節(jié)點(diǎn)樹，并將D中實(shí)例數(shù)最大的類Ck作為該結(jié)點(diǎn)的類標(biāo)記，返回T
? 否則，依照特征Ag將D劃分為若干非空子集Di，將Di中實(shí)例數(shù)最大的類作為標(biāo)記，構(gòu)建子節(jié)點(diǎn)，由結(jié)點(diǎn)及其子節(jié)點(diǎn)構(gòu)成樹T，返回T
? 對(duì)第i個(gè)子節(jié)點(diǎn)，以Di為訓(xùn)練集，以A-{Ag}為特征集，遞歸地調(diào)用1~5，得到子樹Ti，返回TiCART決策樹的生成
?
這里只簡(jiǎn)單介紹下CART與ID3和C4.5的區(qū)別。
? CART樹是二叉樹，而ID3和C4.5可以是多叉樹
? CART在生成子樹時(shí)，是選擇一個(gè)特征一個(gè)取值作為切分點(diǎn)，生成兩個(gè)子樹
? 選擇特征和切分點(diǎn)的依據(jù)是基尼指數(shù)，選擇基尼指數(shù)最小的特征及切分點(diǎn)生成子樹
隨機(jī)森林是一種重要的基于Bagging的集成學(xué)習(xí)方法，可以用來做分類、回歸等問題。
隨機(jī)森林有許多優(yōu)點(diǎn)：
? 具有極高的準(zhǔn)確率
? 隨機(jī)性的引入，使得隨機(jī)森林不容易過擬合
? 隨機(jī)性的引入，使得隨機(jī)森林有很好的抗噪聲能力
? 能處理很高維度的數(shù)據(jù)，并且不用做特征選擇
? 既能處理離散型數(shù)據(jù)，也能處理連續(xù)型數(shù)據(jù)，數(shù)據(jù)集無需規(guī)范化
? 訓(xùn)練速度快，可以得到變量重要性排序
? 容易實(shí)現(xiàn)并行化
?
隨機(jī)森林的缺點(diǎn)：
? 當(dāng)隨機(jī)森林中的決策樹個(gè)數(shù)很多時(shí)，訓(xùn)練時(shí)需要的空間和時(shí)間會(huì)較大
? 隨機(jī)森林模型還有許多不好解釋的地方，有點(diǎn)算個(gè)黑盒模型
與上面介紹的Bagging過程相似，隨機(jī)森林的構(gòu)建過程大致如下：
? 從原始訓(xùn)練集中使用Bootstraping方法隨機(jī)有放回采樣選出m個(gè)樣本，共進(jìn)行n_tree次采樣，生成n_tree個(gè)訓(xùn)練集
? 對(duì)于n_tree個(gè)訓(xùn)練集，我們分別訓(xùn)練n_tree個(gè)決策樹模型
? 對(duì)于單個(gè)決策樹模型，假設(shè)訓(xùn)練樣本特征的個(gè)數(shù)為n，那么每次分裂時(shí)根據(jù)信息增益/信息增益比/基尼指數(shù)選擇最好的特征進(jìn)行分裂
? 每棵樹都一直這樣分裂下去，直到該節(jié)點(diǎn)的所有訓(xùn)練樣例都屬于同一類。在決策樹的分裂過程中不需要剪枝
? 將生成的多棵決策樹組成隨機(jī)森林。對(duì)于分類問題，按多棵樹分類器投票決定最終分類結(jié)果；對(duì)于回歸問題，由多棵樹預(yù)測(cè)值的均值決定最終預(yù)測(cè)結(jié)果
AdaBoost
Adaboost 是 bosting 的方法之一。bosting就是把若干個(gè)分類效果并不好的分類器綜合起來考慮，會(huì)得到一個(gè)效果比較好的分類器。
AdaBoost的一般流程如下所示：
（1）收集數(shù)據(jù)
（2）準(zhǔn)備數(shù)據(jù)：依賴于所用的基分類器的類型，這里的是單層決策樹，即樹樁，該類型決策樹可以處理任何類型的數(shù)據(jù)。
（3）分析數(shù)據(jù)
（4）訓(xùn)練算法：利用提供的數(shù)據(jù)集訓(xùn)練分類器
（5）測(cè)試算法：利用提供的測(cè)試數(shù)據(jù)集計(jì)算分類的錯(cuò)誤率
（6）使用算法：算法的相關(guān)推廣，滿足實(shí)際的需要
接下來，具體闡述adaBoost分類算法1 訓(xùn)練算法：基于錯(cuò)誤提升分類器的性能
上面所述的基分類器，或者說弱分類器，意味著分類器的性能不會(huì)太好，可能要比隨機(jī)猜測(cè)要好一些，一般而言，在二類分類情況下，弱分類器的分類錯(cuò)誤率達(dá)到甚至超過50%，顯然也只是比隨機(jī)猜測(cè)略好。但是，強(qiáng)分類器的分類錯(cuò)誤率相對(duì)而言就要小很多，adaBoost算法就是易于這些弱分類器的組合最終來完成分類預(yù)測(cè)的。
adaBoost的運(yùn)行過程：訓(xùn)練數(shù)據(jù)的每一個(gè)樣本，并賦予其一個(gè)權(quán)重，這些權(quán)值構(gòu)成權(quán)重向量D，維度等于數(shù)據(jù)集樣本個(gè)數(shù)。開始時(shí)，這些權(quán)重都是相等的，首先在訓(xùn)練數(shù)據(jù)集上訓(xùn)練出一個(gè)弱分類器并計(jì)算該分類器的錯(cuò)誤率，然后在同一數(shù)據(jù)集上再次訓(xùn)練弱分類器，但是在第二次訓(xùn)練時(shí)，將會(huì)根據(jù)分類器的錯(cuò)誤率，對(duì)數(shù)據(jù)集中樣本的各個(gè)權(quán)重進(jìn)行調(diào)整，分類正確的樣本的權(quán)重降低，而分類錯(cuò)的樣本權(quán)重則上升，但這些權(quán)重的總和保持不變?yōu)?span style="color: rgb(0, 0, 0); font-size: 18px; font-family: "Helvetica Neue", serif;">1.
并且，最終的分類器會(huì)基于這些訓(xùn)練的弱分類器的分類錯(cuò)誤率，分配不同的決定系數(shù)alpha，錯(cuò)誤率低的分類器獲得更高的決定系數(shù)，從而在對(duì)數(shù)據(jù)進(jìn)行預(yù)測(cè)時(shí)起關(guān)鍵作用。alpha的計(jì)算根據(jù)錯(cuò)誤率得來：
alpha=0.5*ln(1-ε/max(ε,1e-16))
其中，ε=為正確分類的樣本數(shù)目/樣本總數(shù)，max(ε,1e-16)是為了防止錯(cuò)誤率為而造成分母為0的情況發(fā)生
計(jì)算出alpha之后，就可以對(duì)權(quán)重向量進(jìn)行更新了，使得分類錯(cuò)誤的樣本獲得更高的權(quán)重，而分類正確的樣本獲得更低的權(quán)重。D的計(jì)算公式如下：
如果某個(gè)樣本被正確分類，那么權(quán)重更新為：
D(m+1,i)=D(m,i)*exp(-alpha)/sum(D)
如果某個(gè)樣本被錯(cuò)誤分類，那么權(quán)重更新為：
D(m+1,i)=D(m,i)*exp(alpha)/sum(D)
其中，m為迭代的次數(shù)，即訓(xùn)練的第m個(gè)分類器，i為權(quán)重向量的第i個(gè)分量，i<=數(shù)據(jù)集樣本數(shù)量
當(dāng)我們更新完各個(gè)樣本的權(quán)重之后，就可以進(jìn)行下一次的迭代訓(xùn)練。adaBoost算法會(huì)不斷重復(fù)訓(xùn)練和調(diào)整權(quán)重，直至達(dá)到迭代次數(shù)，或者訓(xùn)練錯(cuò)誤率為0。
基于單層決策樹構(gòu)建弱分類器
單層決策樹是一種簡(jiǎn)單的決策樹，也稱為決策樹樁。單層決策樹可以看做是由一個(gè)根節(jié)點(diǎn)直接連接兩個(gè)葉結(jié)點(diǎn)的簡(jiǎn)單決策樹，比如x>v或x<v，就可以看做是一個(gè)簡(jiǎn)單決策樹。
