Ⅰ LightGBM（lgb）介紹
GBDT (Gradient Boosting Decision Tree) 是機器學習中一個長盛不衰的模型，其主要思想是利用弱分類器（決策樹）迭代訓練以得到最優模型，該模型具有訓練效果好、不易過擬合等優點。GBDT不僅在工業界應用廣泛，通常被用於多分類、點擊率預測、搜索排序等任務；在各種數據挖掘競賽中也是致命武器，據統計Kaggle上的比賽有一半以上的冠軍方案都是基於GBDT。而LightGBM（Light Gradient Boosting Machine）是一個實現GBDT演算法的框架，支持高效率的並行訓練，並且具有更快的訓練速度、更低的內存消耗、更好的准確率、支持分布式可以快速處理海量數據等優點。
1.1 LightGBM提出的動機
常用的機器學習演算法，例如神經網路等演算法，都可以以mini-batch的方式訓練，訓練數據的大小不會受到內存限制。而GBDT在每一次迭代的時候，都需要遍歷整個訓練數據多次。如果把整個訓練數據裝進內存則會限制訓練數據的大小；如果不裝進內存，反復地讀寫訓練數據又會消耗非常大的時間。尤其面對工業級海量的數據，普通的GBDT演算法是不能滿足其需求的。
LightGBM提出的主要原因就是為了解決GBDT在海量數據遇到的問題，讓GBDT可以更好更快地用於工業實踐。
1.2 XGBoost的缺點及LightGBM的優化
（1）XGBoost的缺點
在LightGBM提出之前，最有名的GBDT工具就是XGBoost了，它是基於預排序方法的決策樹演算法。這種構建決策樹的演算法基本思想是：
這樣的預排序演算法的優點是能精確地找到分割點。但是缺點也很明顯：
首先，空間消耗大。這樣的演算法需要保存數據的特徵值，還保存了特徵排序的結果（例如，為了後續快速的計算分割點，保存了排序後的索引），這就需要消耗訓練數據兩倍的內存。
其次，時間上也有較大的開銷，在遍歷每一個分割點的時候，都需要進行分裂增益的計算，消耗的代價大。
最後，對cache優化不友好。在預排序後，特徵對梯度的訪問是一種隨機訪問，並且不同的特徵訪問的順序不一樣，無法對cache進行優化。同時，在每一層長樹的時候，需要隨機訪問一個行索引到葉子索引的數組，並且不同特徵訪問的順序也不一樣，也會造成較大的cache miss。
（2）LightGBM的優化
為了避免上述XGBoost的缺陷，並且能夠在不損害准確率的條件下加快GBDT模型的訓練速度，lightGBM在傳統的GBDT演算法上進行了如下優化：
下面我們就詳細介紹以上提到的lightGBM優化演算法。
2.1 基於Histogram的決策樹演算法
（1）直方圖演算法
Histogram algorithm應該翻譯為直方圖演算法，直方圖演算法的基本思想是：先把連續的浮點特徵值離散化成 個整數，同時構造一個寬度為 的直方圖。在遍歷數據的時候，根據離散化後的值作為索引在直方圖中累積統計量，當遍歷一次數據後，直方圖累積了需要的統計量，然後根據直方圖的離散值，遍歷尋找最優的分割點。
直方圖演算法簡單理解為：首先確定對於每一個特徵需要多少個箱子（bin）並為每一個箱子分配一個整數；然後將浮點數的范圍均分成若干區間，區間個數與箱子個數相等，將屬於該箱子的樣本數據更新為箱子的值；最後用直方圖（#bins）表示。看起來很高大上，其實就是直方圖統計，將大規模的數據放在了直方圖中。
我們知道特徵離散化具有很多優點，如存儲方便、運算更快、魯棒性強、模型更加穩定等。對於直方圖演算法來說最直接的有以下兩個優點：
當然，Histogram演算法並不是完美的。由於特徵被離散化後，找到的並不是很精確的分割點，所以會對結果產生影響。但在不同的數據集上的結果表明，離散化的分割點對最終的精度影響並不是很大，甚至有時候會更好一點。原因是決策樹本來就是弱模型，分割點是不是精確並不是太重要；較粗的分割點也有正則化的效果，可以有效地防止過擬合；即使單棵樹的訓練誤差比精確分割的演算法稍大，但在梯度提升（Gradient Boosting）的框架下沒有太大的影響。
（2）直方圖做差加速
LightGBM另一個優化是Histogram（直方圖）做差加速。一個葉子的直方圖可以由它的父親節點的直方圖與它兄弟的直方圖做差得到，在速度上可以提升一倍。通常構造直方圖時，需要遍歷該葉子上的所有數據，但直方圖做差僅需遍歷直方圖的k個桶。在實際構建樹的過程中，LightGBM還可以先計算直方圖小的葉子節點，然後利用直方圖做差來獲得直方圖大的葉子節點，這樣就可以用非常微小的代價得到它兄弟葉子的直方圖。
注意：XGBoost 在進行預排序時只考慮非零值進行加速，而 LightGBM 也採用類似策略：只用非零特徵構建直方圖。
2.2 帶深度限制的 Leaf-wise 演算法
在Histogram演算法之上，LightGBM進行進一步的優化。首先它拋棄了大多數GBDT工具使用的按層生長 (level-wise) 的決策樹生長策略，而使用了帶有深度限制的按葉子生長 (leaf-wise) 演算法。
XGBoost 採用 Level-wise 的增長策略，該策略遍歷一次數據可以同時分裂同一層的葉子，容易進行多線程優化，也好控制模型復雜度，不容易過擬合。但實際上Level-wise是一種低效的演算法，因為它不加區分的對待同一層的葉子，實際上很多葉子的分裂增益較低，沒必要進行搜索和分裂，因此帶來了很多沒必要的計算開銷。
LightGBM採用Leaf-wise的增長策略，該策略每次從當前所有葉子中，找到分裂增益最大的一個葉子，然後分裂，如此循環。因此同Level-wise相比，Leaf-wise的優點是：在分裂次數相同的情況下，Leaf-wise可以降低更多的誤差，得到更好的精度；Leaf-wise的缺點是：可能會長出比較深的決策樹，產生過擬合。因此LightGBM會在Leaf-wise之上增加了一個最大深度的限制，在保證高效率的同時防止過擬合。
Gradient-based One-Side Sampling 應該被翻譯為單邊梯度采樣（GOSS）。GOSS演算法從減少樣本的角度出發，排除大部分小梯度的樣本，僅用剩下的樣本計算信息增益，它是一種在減少數據量和保證精度上平衡的演算法。
AdaBoost中，樣本權重是數據重要性的指標。然而在GBDT中沒有原始樣本權重，不能應用權重采樣。幸運的是，我們觀察到GBDT中每個數據都有不同的梯度值，對采樣十分有用。即梯度小的樣本，訓練誤差也比較小，說明數據已經被模型學習得很好了，直接想法就是丟掉這部分梯度小的數據。然而這樣做會改變數據的分布，將會影響訓練模型的精確度，為了避免此問題，提出了GOSS演算法。
GOSS是一個樣本的采樣演算法，目的是丟棄一些對計算信息增益沒有幫助的樣本留下有幫助的。根 據計算信息增益的定義，梯度大的樣本對信息增益有更大的影響。因此，GOSS在進行數據采樣的 時候只保留了梯度較大的數據，但是如果直接將所有梯度較小的數據都丟棄掉勢必會影響數據的總 體分布。所以，GOSS首先將要進行分裂的特徵的所有取值按照絕對值大小降序排序（XGBoost一 樣也進行了排序，但是LightGBM不用保存排序後的結果），選取絕對值最大的 個數 據。然後在剩下的較小梯度數據中隨機選擇 個數據。接著將這 個數據乘 以一個常數 這樣演算法就會更關注訓練不足的樣本, 而不會過多改變原數據集的分布。最 後使用這 個數據來計算信息增益。下圖是GOSS的具體演算法。
2.4 互斥特徵捆綁演算法
高維度的數據往往是稀疏的，這種稀疏性啟發我們設計一種無損的方法來減少特徵的維度。通常被 抹綁的特徵都是互斥的（即特徵不會同時為非零值，像one-hot），這樣兩個特徵描綁起來才不會 丟失信息。如果兩個特徵並不是完全互斥 (部分情況下兩個特徵都是非零值)，可以用一個指標對 特徵不互斥程度進行像量，稱之為沖突比率，當這個值較小時，我們可以選擇把不完全互斥的兩個 特徵肺綁，而不影響最後的精度。
互斥特徵肺綁演算法 (Exclusive Feature Bundling, EFB) 指出如 果將一些特徵進行融合綁定，則可以降低特徵數量。這樣在構建直方圖時的時間復雜度從O(#data* # feature)變為 O(#data* # bundle), 這里 bundle 指特徵融合綁 定後特徵包的個數, 且 #bundle 遠小於 # feature 。
我們將論文《Lightgbm: A highly efficient gradient boosting decision tree》中沒有提到的優化方案，而在其相關論文《A communication-efficient parallel algorithm for decision tree》中提到的優化方案，放到本節作為LightGBM的工程優化來向大家介紹。
3.1 直接支持類別特徵
實際上大多數機器學習工具都無法直接支持類別特徵，一般需要把類別特徵，通過 one-hot 編碼，轉化到多維的0/1特徵，降低了空間和時間的效率。但我們知道對於決策樹來說並不推薦使用 one-hot 編碼，尤其當類別特徵中類別個數很多的情況下，會存在以下問題：
1,會產生樣本切分不平衡問題，導致切分增益非常小（即浪費了這個特徵）。使用 one-hot編碼，意味著在每一個決策節點上只能使用one vs rest（例如是不是狗，是不是貓等）的切分方式。
例如，動物類別切分後，會產生是否狗，是否貓等一系列特徵，這一系列特徵上只有少量樣本為 1，大量樣本為 0，這時候切分樣本會產生不平衡，這意味著切分增益也會很小。較小的那個切分樣本集，它占總樣本的比例太小，無論增益多大，乘以該比例之後幾乎可以忽略；較大的那個拆分樣本集，它幾乎就是原始的樣本集，增益幾乎為零。比較直觀的理解就是不平衡的切分和不切分沒有區別。
2,會影響決策樹的學習。因為就算可以對這個類別特徵進行切分，獨熱編碼也會把數據切分到很多零散的小空間上，如下圖左邊所示。而決策樹學習時利用的是統計信息，在這些數據量小的空間上，統計信息不準確，學習效果會變差。但如果使用下圖右邊的切分方法，數據會被切分到兩個比較大的空間，進一步的學習也會更好。下圖右邊葉子節點的含義是X=A或者X=C放到左孩子，其餘放到右孩子。
演算法流程如下圖所示，在枚舉分割點之前，先把直方圖按照每個類別對應的label均值進行排序; 然後按照排序的結果依次枚舉最優分割點。從下圖可以看到, 為類別的均值。當然，這個方法很容易過擬合，所以LightGBM裡面還增加了很多對於這個方法的約束和正則化。
在Expo數據集上的實驗結果表明，相比0/1展開的方法，使用LightGBM支持的類別特徵可以使訓練速度加速8倍，並且精度一致。更重要的是，LightGBM是第一個直接支持類別特徵的GBDT工具。
3.2 支持高效並行
（1）特徵並行
特徵並行的主要思想是不同機器在不同的特徵集合上分別尋找最優的分割點，然後在機器間同步最優的分割點。XGBoost使用的就是這種特徵並行方法。這種特徵並行方法有個很大的缺點：就是對數據進行垂直劃分，每台機器所含數據不同，然後使用不同機器找到不同特徵的最優分裂點，劃分結果需要通過通信告知每台機器，增加了額外的復雜度。
LightGBM 則不進行數據垂直劃分，而是在每台機器上保存全部訓練數據，在得到最佳劃分方案後可在本地執行劃分而減少了不必要的通信。具體過程如下圖所示。
（2）數據並行
傳統的數據並行策略主要為水平劃分數據，讓不同的機器先在本地構造直方圖，然後進行全局的合 並，最後在合並的直方圖上面尋找最優分割點。這種數據劃分有一個很大的缺點：通訊開銷過大。 如果使用點對點通信，一台機器的通訊開銷大約為 O(#machine* # feature*#bin) 如果使用集成的通信，則通訊開銷為
LightGBM在數據並行中使用分散規約 (Rece scatter) 把直方圖合並的任務分攤到不同的機器，降低通信和計算，並利用直方圖做差，進一步減少了一半的通信量。具體過程如下圖所示。
(3）投票並行
基於投票的數據並行則進一步優化數據並行中的通信代價，使通信代價變成常數級別。在數據量很大的時候，使用投票並行的方式只合並部分特徵的直方圖從而達到降低通信量的目的，可以得到非常好的加速效果。具體過程如下圖所示。
大致步驟為兩步：
XGBoost對cache優化不友好，如下圖所示。在預排序後，特徵對梯度的訪問是一種隨機訪問，並且不同的特徵訪問的順序不一樣，無法對cache進行優化。同時，在每一層長樹的時候，需要隨機訪問一個行索引到葉子索引的數組，並且不同特徵訪問的順序也不一樣，也會造成較大的cache miss。為了解決緩存命中率低的問題，XGBoost 提出了緩存訪問演算法進行改進。
而 LightGBM 所使用直方圖演算法對 Cache 天生友好：
4.1 優點
這部分主要總結下 LightGBM 相對於 XGBoost 的優點，從內存和速度兩方面進行介紹。
（1）速度更快
（2）內存更小
4.2 缺點
訓練配置 ：
6307410個樣本做訓練集
訓練出的LightGBM模型文件及其含義解析：
第1棵樹
樹的結構
第二棵樹，含義參考第一棵樹
特徵重要性
重要性值是統計特徵在所有樹中作為中間節點（分裂節點）的分裂特徵且分裂增益為正的次數，可以理解成是對分裂作用越大的特徵越重要
參考自：
Microstrong
魚達爾
Ⅱ 優化演算法筆記（八）人工蜂群演算法
（以下描述，均不是學術用語，僅供大家快樂的閱讀）
工蜂群演算法（Artificial Bee Colony Algorithm，ABC）是一種模仿蜜蜂采蜜機理而產生的群智能優化演算法。其原理相對復雜，但實現較為簡單，在許多領域中都有研究和應用。
人工蜂群演算法中，每一個蜜源的位置代表了待求問題的一個可行解。蜂群分為采蜜蜂、觀察蜂和偵查蜂。采蜜蜂與蜜源對應，一個采蜜蜂對應一個蜜源。觀察蜂則會根據采蜜蜂分享的蜜源相關信息選擇跟隨哪個采蜜蜂去相應的蜜源，同時該觀察蜂將轉變為偵查蜂。偵查蜂則自由的搜索新的蜜源。每一個蜜源都有開採的限制次數，當一個蜜源被采蜜多次而達到開采限制次數時，在該蜜源采蜜的采蜜蜂將轉變為偵查蜂。每個偵查蜂將隨機尋找一個新蜜源進行開采，並轉變成為采蜜蜂。
下面是我的實現方式（我的答案）：
1． 三種蜜蜂之間可以相互轉化。
采蜜蜂->觀察蜂：有觀察蜂在采蜜過程中發現了比當前采蜜蜂更好的蜜源，則采蜜蜂放棄當前蜜源轉而變成觀察蜂跟隨優質蜜源，同時該觀察蜂轉變為采蜜蜂。
采蜜蜂->觀察蜂：當該采蜜蜂所發現的蜜源被開采完後，它會轉變為觀察蜂去跟隨其他采蜜蜂。
采蜜蜂->偵查蜂：當所有的采蜜蜂發現的蜜源都被開采完後，采蜜蜂將會變為偵查蜂，觀察蜂也會變成偵查蜂，因為大家都無蜜可采。
偵查蜂->采蜜蜂、觀察蜂：偵查蜂隨機搜索蜜源，選擇較好的數個蜜源位置的蜜蜂為采蜜蜂，其他蜜蜂為觀察蜂。
2.蜜源的數量上限
蜜源的數量上限等於采蜜蜂的數量上限。初始化時所有蜜蜂都是偵查蜂，在這些偵查蜂所搜索到的蜜源中選出數個較優的蜜源，發現這些蜜源的偵查蜂變為采蜜蜂，其他蜜蜂變為觀察蜂。直到所有的蜜源都被開采完之前，蜜源的數量不會增加，因為這個過程中沒有產生偵查蜂。所有的蜜源都被開采完後，所有的蜜蜂再次全部轉化為偵查蜂，新的一輪蜜源搜索開始。也可以在一個蜜源開采完時馬上產生一個新的蜜源補充，保證在整個開采過程中蜜源數量恆定不變。
蜜源的開采實際上就是觀察蜂跟隨采蜜蜂飛向蜜源的過程。得到的下一代的位置公式如下：
表示第i只觀察蜂在第t代時隨機選擇第r只採蜜蜂飛行一段距離，其中R為（-1，1）的隨機數。
一隻觀察蜂在一次迭代過程中只能選擇一隻采蜜蜂跟隨，它需要從眾多的采蜜蜂中選擇一隻來進行跟隨。觀察蜂選擇的策略很簡單，隨機跟隨一隻采蜜蜂，該采蜜蜂發現的蜜源越優，則選擇它的概率越大。
是不是很像輪盤賭，對，這就是輪盤賭，同時我們也可以稍作修改，比如將勤勞的小蜜蜂改為懶惰的小蜜蜂，小蜜蜂會根據蜜源的優劣和距離以及開采程度等因素綜合來選擇跟隨哪只採蜜蜂（雖然影響不大，但聊勝於無）。
忘記了輪盤賭的小夥伴可以看一下 優化演算法筆記（六）遺傳演算法 。
下面是我的人工蜂群演算法流程圖
又到了實驗環節，參數實驗較多，全部給出將會佔用太多篇幅，僅將結果進行匯總展示。
實驗1：參數如下
上圖分別為采蜜蜂上限為10%總數和50%總數的情況，可以看出當采蜜蜂上限為10%總群數時，種群收斂的速度較快，但是到最後有一個點死活不動，這是因為該點作為一個蜜源，但由於適應度值太差，使用輪盤賭被選擇到的概率太小從而沒有得到更佳的蜜源位置，而因未開采完，采蜜蜂又不能放棄該蜜源。
看了看采蜜蜂上限為50%總群數時的圖，發現也有幾個點不動的狀態，可以看出，這時不動的點的數量明顯多於上限為10%總數的圖，原因很簡單，采蜜蜂太多，「先富」的人太多，而「後富」的人較少，沒有帶動「後富者」的「先富者」也得不到發展。
看看結果
嗯，感覺結果並沒有什麼差別，可能由於問題較簡單，迭代次數較少，無法體現出采蜜蜂數對於結果的影響，也可能由於蜜源的搜索次數為60較大，總群一共只能對最多20*50/60=16個蜜源進行搜索。我們將最大迭代次數調大至200代再看看結果
當最大迭代次數為200時，人工蜂群演算法的結果如上圖，我們可以明顯的看出，隨著采蜜蜂上限的上升，演算法結果的精度在不斷的下降，這也印證了之前的結果，由於蜜源搜索次數較大（即搜索深度較深）采蜜蜂數量越多（搜索廣度越多），結果的精度越低。不過影響也不算太大，下面我們再來看看蜜源最大開采次數對結果的影響。
實驗2：參數如下
上圖分別是蜜源開采限度為1,20和4000的實驗。
當蜜源開采上限為1時，即一個蜜源只能被開采一次，即此時的人工蜂群演算法只有偵查蜂隨機搜索的過程，沒有觀察蜂跟隨采蜜蜂的過程，可以看出圖中的蜜蜂一直在不斷的隨機出現在新位置不會向某個點收斂。
當蜜源開采上限為20時，我們可以看到此時種群中的蜜蜂都會向一個點飛行。在一段時間內，有數個點一動不動，這些點可能就是采蜜蜂發現的位置不怎麼好的蜜源，但是在幾次迭代之後，它們仍會被觀察蜂開采，從而更新位置，蜜源開采上限越高，它們停頓的代數也會越長。在所有蜜蜂都收斂於一個點之後，我們可以看到仍會不斷的出現其他的隨機點，這些點是偵查蜂進行隨機搜索產生的新的蜜源位置，這些是人工蜂群演算法跳出局部最優能力的體現。
當蜜源開采上限為4000時，即不會出現偵查蜂的搜索過程，觀察蜂只會開采初始化時出現的蜜源而不會采蜜蜂不會有新的蜜源產生，可以看出在蜂群收斂後沒有出現新的蜜源位置。
看看最終結果，我們發現，當蜜源開采上線大於1時的結果提升，但是好像開采上限為5時結果明顯好於開采次數上限為其他的結果，而且隨著開采次數不斷上升，結果在不斷的變差。為什麼會出現這樣的結果呢？原因可能還是因為問題較為簡單，在5次開採的限度內，觀察蜂已經能找到更好的蜜源進行開采，當問題較為復雜時，我們無法知曉開采發現新蜜源的難度，蜜源開采上限應該取一個相對較大的值。當蜜源開采限度為4000時,即一個蜜源不可能被開采完(開采次數為20(種群數)*200(迭代次數)),搜索的深度有了但是其結果反而不如開采限度為幾次幾十次來的好,而且這樣不會有偵查蜂隨機搜索的過程,失去了跳出局部最優的能力。
我們應該如何選擇蜜源的最大開采次數限制呢？其實，沒有最佳的開采次數限制，當適應度函數較為簡單時，開采次數較小時能得到比較好的結果，但是適應度函數較復雜時，經過試驗，得出的結果遠差於開采次數較大時。當然，前面就說過，適應度函數是一個黑盒模型，我們無法判斷問題的難易。那麼我們應該選擇一個適中的值，個人的選擇是種群數的0.5倍到總群數的2倍作為蜜源的最大開采次數，這樣可以保證極端情況下，1-2個迭代周期內小蜜蜂們能將一個蜜源開采完。
人工蜂群演算法算是一個困擾我比較長時間的演算法，幾年時間里，我根據文獻實現的人工蜂群演算法都有數十種，只能說人工蜂群演算法的描述太過模糊，或者說太過抽象，研究者怎麼實現都說的通。但是通過實現多次之後發現雖然實現細節大不相同，但效果相差不多，所以我們可以認為人工蜂群演算法的穩定性比較強，只要實現其主要思想即可，細節對於結果的影響不太大。
對於人工蜂群演算法影響最大的因素還是蜜源的開采次數限制，開采次數限制越大，對同一蜜源的開發力度越大，但是分配給其他蜜源的搜索力度會相對減少，也會降低蜂群演算法的跳出局部最優能力。可以動態修改蜜源的開采次數限制來實現對演算法的改進，不過效果不顯著。
其次對於人工蜂群演算法影響是三類蜜蜂的搜索行為，我們可以重新設計蜂群的搜索方式來對演算法進行改進，比如采蜜蜂在開采蜜源時是隨機飛向其他蜜源，而觀察蜂向所選的蜜源靠近。這樣改進有一定效果但是在高維問題上效果仍不明顯。
以下指標純屬個人yy,僅供參考
目錄
上一篇 優化演算法筆記（七）差分進化演算法
下一篇 優化演算法筆記（九）杜鵑搜索演算法
優化演算法matlab實現（八）人工蜂群演算法matlab實現
Ⅲ 關於lightgbm處理category特徵的理解
之前一直使用的集成回歸樹模型都是RF，Xgboost，GBDT這三個，其中RF是bagging思想，Xgboost和GBDT是boosting思想。但是在嘗試了微軟開源的Lightgbm之後，感覺再也回不去了。這款橫空出世的輕量級tree boost模型，在不損失精度的情況下，大大提升了計算效率。同時也做出了一些改進。在這里先聊一聊它對『category』』這種類別型數據的處理的支持。
如果你對演算法有一定的了解，你會知道是無法直接處理類別型數據的，即離散特徵。我們需要對類別型數據做一個one-hot，將類別型數據稀疏化。例如用鞋子品牌這一特徵維度對鞋子進行分類：耐克鞋，阿迪鞋，李寧鞋。你不能將他們編碼成（0,1,2），因為這樣你就已經不公平的定義了三者之間的距離，阿迪和耐克的距離是1，而李寧和耐克的距離是2，我們不能這樣貿然定義，不能做一個莽夫。眾生平等，所以我們要一視同仁，採取one-encode編碼將三者轉換為（1,0,0），（0,1,0），（0,0,1）。讓距離的計算變得更加合理。
而Lightgbm可以直接支持category特徵的處理，在用pandas結構使用LGB時可以指定哪一列是類別型數據，省去one-hot的步驟。如果類別過多，如商品ID，在one-hot處理後數據會變得過於稀疏，大大增加了訓練集的大小，浪費計算資源。而LGB則會採用一種直方圖式的方法去處理，max bin的默認值是256，對於category類型的feature，則是每一種取值放入一個bin，且當取值的個數大於max bin數時，會忽略那些很少出現的category值。在求split時，對於category類型的feature，算的是"按是否屬於某個category值劃分"的gain，它的實際效果就是類似one-hot的編碼方法。
在最近的一個項目中，我第一直覺認為商品ID應該是和商品銷量高度相關的特徵，對商品ID進行one-hot後，在輸出的feature importance中該特徵得分非常高，也符合我的直覺。但是最終結果卻變差了。針對這一問題，我個人的理解是，在過於稀疏化後，相當於變相減少了數據量，在學習能力很強的模型下，很容易導致過擬合的現象，若不能獲取更多的數據，可以考慮放棄該列特徵或者將商品ID按照其他的方法進行重新分成各大類，降低稀疏化程度，也可以獲得不錯的效果。
Ⅳ 演算法太多挑花眼
演算法太多挑花眼？教你如何選擇正確的機器學習演算法
機器學習演算法雖多，卻沒有什麼普適的解決方案。決策樹、隨機森林、樸素貝葉斯、深度網路等等等等，是不是有時候覺得挑花了眼呢？福利來啦~本文將教你慧眼識精，快速挑選出滿意的演算法！
機器學習既是一門科學，也是一種藝術。縱觀各類機器學習演算法，並沒有一種普適的解決方案或方法。事實上，有幾個因素會影響你對機器學習演算法的選擇。
有些問題是非常特別的，需要用一種特定的解決方法。例如，如果你對推薦系統有所了解，你會發現它是一類很常用的機器學習演算法，用來解決一類非常特殊的問題。而其它的一些問題則非常開放，可能需要一種試錯方法（例如：強化學習）。監督學習、分類、回歸等問題都是非常開放的，可以被用於異常檢測或建立更加廣泛的預測模型。
此外，我們在選擇機器學習演算法時所做出的一些決定與演算法的優化或技術層面關系並不大，而更多地與業務決策相關。下面，讓我們一起來看看有哪些因素能幫你縮小機器學習演算法的選擇范圍。
數據科學過程
在你開始研究不同的機器學習演算法前，你需要對自己擁有的數據、面對的問題及相關約束有清晰的了解。
理解你的數據
當我們決定使用哪種演算法時，我們所擁有的數據的類型和形態起著關鍵性的作用。有些演算法可以利用較小的樣本集合工作，而另一些演算法則需要海量的樣本。特定的演算法對特定類型的數據起作用。例如，樸素貝葉斯演算法對處理待分類的輸入特別有效，但是對於缺失值則一點都不敏感。
因此，你需要做到：
了解你的數據
1. 查看總結統計和數據可視化的結
百分比可以幫助你識別大多數數據的范圍
平均數和中位數可以描述集中趨勢
相關系數可以指出強的關聯性
2. 數據可視化
箱形圖可以識別出異常值
密度圖和直方圖可以顯示出數據的散布情況
散點圖可以描述二元關
數據清洗
1. 處理缺失值。缺失的數據對於某些模型的影響比對其它模型更大。即使是對於那些被用於處理缺失數據的模型來說，它們也可能對缺失數據很敏感（某些變數的缺失數據可能導致預測性能變差）
2. 選擇處理異常值的方法
異常值在多維數據中十分常見。
有些模型對異常值的敏感性比其它模型要低。通常而言，樹模型對於異常值的存在不太敏感。然而回歸模型、或者任何試圖使用方程的模型都會受到異常值的嚴重影響。
異常值可能是糟糕的數據收集造成的，也可能是合理的極值。
3. 數據需要被聚合嗎？
數據增強
1. 特徵工程是從原始數據中產生能夠被用於建模的數據的過程，可以起到以下幾種作用：
使模型更容易被解釋（如數據分箱（binning））
捕獲更復雜的關系（如神經網路）
減少數據冗餘並降低數據維度（如主成分分析（PCA））
重新縮放變數（如標准化或歸一化）
2. 不同的模型可能有不同的特徵工程的要求。有的模型有內置的特徵工程。
對問題進行分類
下一步是對問題進行分類。這是一個需要分兩步實現的過程。
1. 根據輸入分類：
如果你擁有的是帶標簽的數據，那麼這就是一個監督學習問題。
如果你擁有的是未標注過的數據，並且希望從中找到有用的結構，那麼這就是一個無監督學習問題。
如果你想要通過與環境的交互來優化一個目標函數，那麼這就是一個強化學習問題。
2. 根據輸出分類：
如果模型的輸出是一個（連續的）數字，那麼這就是一個回歸問題。
如果模型的輸出是一個類別，那麼這就是一個分類問題。
如果模型的輸出是一組用輸入數據劃分出的簇，那麼這就是一個聚類問題。
你想發現一個異常點嗎？此時你面對的就是一個異常檢測問題。
理解你要滿足的約束條
你需要考慮你能夠存儲數據的容量有多大？這取決於系統的存儲容量，你可能無法存儲若干 GB 大小的分類、回歸模型或者若干 GB 的用於聚類分析的數據。例如，在嵌入式系統中，你就會面臨這種情況。
對預測過程的速度是否有要求？在實時應用中，很顯然，盡快得出預測結果是十分重要的。例如，在自動駕駛問題中，應用必須盡可能快地對道路標志進行分類，以免發生交通事故。
對學習過程的速度是否有要求？在某些情況下，快速訓練模型是十分必要的：有時，你需要使用不同的數據集快速地實時更新你的模型。
尋找可用的演算法
當對自己的任務環境有了一個清晰的認識後，你就可以使用你所掌握的工具確定適用於待解決的問題並切實可行的演算法。一些影響你選擇模型的因素如下：
模型是否滿足業務目標
模型需要多少數據預處理工作
模型有多准確
模型的可解釋性如何
模型運行的速度有多快：構造模型需要多久？模型做出預測需要多長時間？
模型的可伸縮性如何
模型的復雜度是一個影響演算法選擇的重要標准。一般來說，一個更復雜的模型具備下列特徵：
它依賴於更多的特徵進行學習和預測（例如，使用十個而不是兩個特徵來預測目標）
它依賴於更復雜的特徵工程（例如，使用多項式特徵、交互特徵或主成分）
它有更大的計算開銷（例如，需要一個由 100 棵決策樹組成的隨機森林，而不是一棵單獨的決策樹）
除此之外，同樣的機器學習演算法可以基於參數的個數和某些超參數的選擇而變得更加復雜。例如：
回歸模型可以擁有更多的特徵，或者多項式項和交互項。
決策樹可以擁有更大或更小的深度。
將相同的演算法變得更加復雜增加了發生過擬合的幾率。
常用的機器學習演算法
線性回歸
這可能是機器學習中最簡單的演算法。例如，當你想要計算一些連續值，而不是將輸出分類時，可以使用回歸演算法。因此，當你需要預測一個正在運行的過程未來的值時，你可以使用回歸演算法。然而，當特徵冗餘，即如果存在多重共線性（multicollinearity）時，線性回歸就不太穩定。
在下列情況下可以考慮使用線性回歸：
從一個地方移動到另一個地方所需的時間
預測下個月某種產品的銷售情況
血液中的酒精含量對協調能力的影響
預測每個月禮品卡的銷售情況，並改善年收入的估算
Logistic 回歸
Logistic 回歸執行二進制分類，因此輸出二值標簽。它將特徵的線性組合作為輸入，並且對其應用非線性函數（sigmoid），因此它是一個非常小的神經網路的實例。
logistic回歸提供了許多方法對你的模型進行正則化處理，因此正如在樸素貝葉斯演算法中那樣，你不必擔心你的特徵是否相關。該模型還有一個很好的概率化的解釋。不像在決策樹或者支持向量機中那樣，你可以很容易地更新你的模型以獲取新的數據。如果你想要使用一個概率化的框架，或者你希望在未來能夠快速地將更多的訓練數據融合到你的模型中，你可以使用 logistic 回歸演算法。logistic 回歸還可以幫助你理解預測結果背後起作用的因素，它不完全是一個黑盒方法。
在下列情況下可以考慮使用 logistic 回歸演算法：
預測客戶流失
信用評分和欺詐檢測
評價市場營銷活動的效果
決策樹
決策樹很少被單獨使用，但是不同的決策樹可以組合成非常高效的演算法，例如隨機森林或梯度提升樹演算法。
決策樹很容易處理特徵交互，並且決策樹是一種非參數模型，所以你不必擔心異常值或者數據是否是線性可分的。決策樹演算法的一個缺點是，它們不支持在線學習，因此當你要使用新的樣本時，你不得不重新構建決策樹。決策樹的另一個缺點是，它很容易發生過擬合，而這就是像隨機森林（或提升樹）這樣的集成學習方法能夠派上用場的地方。決策樹也需要大量的內存空間（擁有的特徵越多，你的決策樹可能會越深、越大）
決策樹能夠很好地幫助你在諸多行動路徑中做出選擇：
做出投資決策
預測客戶流失
找出可能拖欠銀行貸款的人
在「建造」和「購買」兩種選擇間進行抉擇
銷售主管的資質審核
K-均值
有時，你完全沒有數據的標簽信息，並且你的目的是根據對象的特徵來為其打上標簽。這種問題被稱為聚類任務。聚類演算法可以在這種情況下被使用：例如，當你有一大群用戶，你希望根據他們共有的一些屬性將其劃分到一些特定的組中。
如果在你的問題聲明中有這樣的問題：例如，找出一群個體的組織形式，或將某些東西分組，或找出特定的組。這時，你就應該使用聚類演算法。
該方法最大的缺點是，K-均值演算法需要提前知道你的數據會有多少簇，因此這可能需要進行大量的試驗去「猜測」我們最終定義的簇的最佳個數——K。
主成分分析（PCA）
主成分分析能夠對數據進行降維。有時，你擁有各種各樣的特徵，這些特徵之間的相關性可能很高，而模型如果使用如此大量的數據可能會產生過擬合現象。這時，你可以使用主成分分析（PCA）技術。
主成分分析（PCA）能夠起作用的關鍵因素是：除了低維的樣本表徵，它還提供了各種變數的一種同步的低維表徵。同步的樣本和變數的表徵提供了一種能夠可視化地找到能夠表示一組樣本的特徵的變數的方法。
支持向量機
支持向量機（SVM）是一種在模式識別和分類問題中被廣泛應用的監督機器學習技術——當你的數據恰好有兩類時。
支持向量機准確率高，對於防止過擬合很好的理論保障。當你使用一個合適的核函數時，即使你的數據在基（低維）特徵空間中是線性不可分的，他們也可以很好地工作。支持向量機在文本分類問題中非常流行，在該問題中，輸入是一個維度非常高的空間是很正常的。然而，SVM 是一種內存密集型演算法，它很難被解釋，並且對其進行調優十分困難。
在下列現實世界的應用中，你可以使用支持向量機：
發現患有糖尿病等常見疾病的人
手寫字元識別
文本分類——將文章按照話題分類
股票市場價格預測
樸素貝葉斯
這是一種基於貝葉斯定理的分類技術，它很容易構建，非常適用於大規模數據集。除了結構簡單，據說樸素貝葉斯的表現甚至比一些復雜得多的分類方法更好。當 CPU 和內存資源有限時，樸素貝葉斯演算法也是一個很好的選項。
樸素貝葉斯非常簡單，你僅僅是在做大量的計數工作。如果樸素貝葉斯的條件獨立假設確實成立，樸素貝葉斯分類器的收斂速度會比 logistic 回歸這樣的判別模型更快，因此需要的訓練數據更少。即使樸素貝葉斯的假設不成立，樸素貝葉斯分類器往往也能很好地完成任務。如果你想使用一種快速的、簡單的、性能也不錯的模型，樸素貝葉斯是一個很好的選擇。這種演算法最大的缺點就是它不能學習到特徵之間的相互作用。
在下列真實世界的應用中，你可以使用樸素貝葉斯：
情感分析和文本分類
類似於 Netflix、Amazon 這樣的推薦系統
識別垃圾郵件
人臉識別
隨機森林
隨機森林是一種決策樹的集成方法。它能夠同時解決具有大規模數據集的回歸問題和分類問題，還有助於從數以千計的輸入變數中找出最重要的變數。隨機森林具有很強的可伸縮性，它適用於任何維數的數據，並且通常具有相當不錯的性能。此外，還有一些遺傳演算法，它們可以在具有最少的關於數據本身的知識的情況下，很好地擴展到任何維度和任何數據上，其中最簡單的實現就是微生物遺傳演算法。然而，隨機森林學習的速度可能會很慢（取決於參數設置），並且這種方法不能迭代地改進生成模型。
在下列現實世界的應用中，你可以使用隨機森林：
預測高危患者
預測零件在生產中的故障
預測拖欠貸款的人
神經網路
神經網路中包含著神經元之間連接的權重。這些權重是平衡的，逐次對數據點進行學習。當所有的權重都被訓練好後，如果需要對新給定的數據點進行回歸，神經網路可以被用於預測分類結果或一個具體數值。利用神經網路，可以對特別復雜的模型進行訓練，並且將其作為一種黑盒方法加以利用，而在訓練模型之前，我們無需進行不可預測的復雜特徵工程。通過與「深度方法」相結合，甚至可以採用更加不可預測的模型去實現新任務。例如，最近人們已經通過深度神經網路大大提升了物體識別任務的結果。深度學習還被應用於特徵提取這樣的非監督學習任務，也可以在人為干預更少的情況下，從原始圖像或語音中提取特徵。
另一方面，神經網路很難被解釋清楚，其參數設置也復雜地讓人難以置信。此外，神經網路演算法也都是資源密集型和內存密集型的。
SCIKIT 參考手冊
Scikit learning 為大家提供了一個非常深入的、解釋地很清楚的流程圖，它能夠幫助你選擇正確的演算法。我認為此圖十分方便。
結論
一般來說，你可以根據上面介紹的要點來篩選出一些演算法，但是要想在一開始就知道哪種方法最好是很難的。你最好多迭代幾次選擇演算法的過程。將你的數據輸入給那些你確定的潛在優秀機器學習演算法，通過並行或串列的方式運行這些演算法，最終評估演算法性能，從而選擇出最佳的演算法。
在最後，我想告訴你：為現實生活中的問題找到正確的解決方案，通常不僅僅是一個應用數學方法的問題。這要求我們對業務需求、規則和制度、相關利益者的關注點有所了解，並且具備大量的專業知識。在解決一個機器學習問題的同時，能夠結合並平衡這些問題是至關重要的，那些能做到這一點的人可以創造最大的價值。