機器學習-變數離散之MDLP-20180217

02-26

連續變數的離散化在數據挖掘中是很常見的問題，而通常需要離散化的場景主要是兩類：一種是演算法不適合處理連續變數，如邏輯回歸；另一種是演算法適合處理連續變數，但由於缺失值的存在，演算法沒有處理缺失值的能力，如sklearn中的隨機森林，需要對變數進一步處理，其中一種方法就是將缺失值當做一類別，同時對未缺失的部分進行離散，最後one-hot處理。

即使有時演算法可以處理連續變數，也沒有缺失值，我們也會對變數進行離散，離散的一個顯著好處就是增加模型的穩健性，但同時也會降低模型的擬合能力，比如隨機森林，如果你提前對連續變數進行離散，離散的切點一般是只考慮單個變數的分布進行切分的，沒有考慮到其他變數的影響，這樣就導致在決策樹中，你提前定的切點並不一定是模型中最優的切點。

今天介紹的是一種與決策樹理論類似的離散方法，被稱為MDLP，全稱是「最短描述長度原則」，所以與決策樹一樣，是基於資訊理論的知識演化而來的監督離散方法。

MDLP的基本思想是，離散後輸入變數對輸出變數的解釋能力變強，則這種離散是有用的，否則是沒有意義的。它是利用信息增益最大化的方法尋找連續變數的最優切點，當切點確定後，將連續變數一分為二，分為兩部分數據集，在這兩部分數據集中用同樣的方法循環切分，直到信息增益的值小於停止標準為止。

假設樣本集合 $D$ 中第 $k$ 類樣本所佔的比例為 $p_k$ ，則信息熵的計算公式如下：

$Ent(D) = -sum_{k=1}^{left| y ight|}{p_klog_2p_k}$

相應的，將數據集一分為二，則信息增益的計算為：

$Gain(D) = Ent(D)-frac{left| D_1 ight|}{left| D ight|}Ent(D_1)-frac{left| D_2 ight|}{left| D ight|}Ent(D_2)$

假設樣本子集中 $D_1$ 的類別數量為 $left| y_1 ight|$ ， $D_2$ 的類別數量為 $left| y_2 ight|$ ，則停止準則為：

$StopC = frac{log_2(left| D ight|-1)}{left| D ight|}+frac{Delta}{left| D ight|}$

其中： $Delta = log_2(3^{(left| y ight|-2)}-[Ent(D)-left| y_1 ight|Ent(D_1)-left| y_2 ight|Ent(D_2)]$

現在這種離散方法在sklearn中並沒有收錄，不過我看到Orange這個包有這種離散方法，只是Orange的輸入數據格式有點變態，我寫了一部分在這裡：https://github.com/Shuilongyin/-py-/blob/master/discretize.py

另外也有人自己寫了這種方法，不過是基於py2，源碼找不到了，我copy了一份，並基於py3改寫了一部分，計算速度比較慢：https://github.com/Shuilongyin/-py-/blob/master/MDLP.py