一條SQL搞定信息增益的計算

周東諭，2011年加入騰訊，現任職於騰訊互娛運營部數據中心，主要從事遊戲相關的數據分析和挖掘工作。

信息增益原理介紹

介紹信息增益之前，首先需要介紹一下熵的概念，這是一個物理學概念，表示「一個系統的混亂程度」。系統的不確定性越高，熵就越大。假設集合中的變數X={x1,x2…xn}，它對應在集合的概率分別是P={p1,p2…pn}。那麼這個集合的熵表示為：

舉一個的例子：對遊戲活躍用戶進行分層，分為高活躍、中活躍、低活躍，遊戲A按照這個方式劃分，用戶比例分別為20%，30%，50%。遊戲B按照這種方式劃分，用戶比例分別為5%，5%，90%。那麼遊戲A對於這種劃分方式的熵為：

同理遊戲B對於這種劃分方式的熵為：

遊戲A的熵比遊戲B的熵大，所以遊戲A的不確定性比遊戲B高。用簡單通俗的話來講，遊戲B要不就在上升期，要不就在衰退期，它的未來已經很確定了，所以熵低。而遊戲A的未來有更多的不確定性，它的熵更高。

介紹完熵的概念，我們繼續看信息增益。為了便於理解，我們還是以一個實際的例子來說明信息增益的概念。假設有下表樣本

第一列為QQ，第二列為性別，第三列為活躍度，最後一列用戶是否流失。我們要解決一個問題：性別和活躍度兩個特徵，哪個對用戶流失影響更大？我們通過計算信息熵可以解決這個問題。

按照分組統計，我們可以得到如下信息：

其中Positive為正樣本（已流失），Negative為負樣本（未流失），下面的數值為不同劃分下對應的人數。那麼可得到三個熵：

整體熵：

性別熵：

性別信息增益：

同理計算活躍度熵：

活躍度信息增益：

活躍度的信息增益比性別的信息增益大，也就是說，活躍度對用戶流失的影響比性別大。在做特徵選擇或者數據分析的時候，我們應該重點考察活躍度這個指標。

使用Hive SQL實現信息熵的計算

從表2中我們不難發現，在計算信息熵和信息增益之前，需要對各維度做匯總計數，計算各公式中出現的分母。Hive SQL中，cube能幫助我們很快的做匯總計算，話不多說直接上代碼：

SELECTt1.feature_name,SUM((ea_all/es)*EA) as gain,SUM(NVL(-(ea_all/ES)*log2(ea_all/es),0)) as info,--計算信息增益率的分母SUM((ea_all/es)*EA)/SUM(NVL(-(ea_all/es)*log2(ea_all/es),0)) as gain_rate--信息增益率計算FROM( SELECT feature_name, feature_value, ea_all, --Key Step2 對於整體熵，要記得更換符號,NVL的出現是防止計算log2(0)得NULL case when feature_value=-100 then -(NVL((ea_positive/ea_all)*log2(ea_positive/ea_all),0)+NVL((ea_negative/ea_all)*log2(ea_negative/ea_all),0)) else (NVL((ea_positive/ea_all)*log2(ea_positive/ea_all),0)+NVL((ea_negative/ea_all)*log2(ea_negative/ea_all),0)) end as EA FROM ( SELECT feature_name, feature_value, SUM(case when is_lost=-100 then user_cnt else 0 end) as ea_all, SUM(case when is_lost=1 then user_cnt else 0 end) as ea_positive, SUM(case when is_lost=0 then user_cnt else 0 end) as ea_negative FROM ( SELECT feature_name, --Key Step1 對feature值和label值做匯總統計，1、用於熵計算的分母，2、計算整體熵情況 case when grouping(feature_value)=1 then -100 else feature_value end as feature_value, case when grouping(is_lost)=1 then -100 else is_lost end as is_lost, COUNT(1) as user_cnt FROM ( SELECT feature_name,feature_value,is_lost FROM gain_caculate )GROUP BY feature_name,cube(feature_value,is_lost) )GROUP BY feature_name,feature_value ))t1 join ( --Key Step3信息增益計算時，需要給出樣本總量作為分母 SELECT feature_name,COUNT(1) as es FROM gain_caculate GROUP BY feature_name)t2 on t1.feature_name=t2.feature_nameGROUP BY t1.feature_name

數據表結構如下：

關鍵步驟說明：

KeyStep1：各特徵的熵計算

KeyStep2：各feature下的信息增熵

信息增益計算結果：

結束語：

以上為信息熵計算過程的SQL版本，其關鍵點在於使用cube實現了feature和label所需要的匯總計算。需要的同學只需要按照規定的表結構填入數據，修改SQL代碼即可計算信息增益。文中如有不足的地方，還請各位指正。

參考文檔

[1] 演算法雜貨鋪——分類演算法之決策樹(Decision tree)

演算法雜貨鋪--分類演算法之決策樹(Decision tree)

[2] c4.5為什麼使用信息增益比來選擇特徵？

c4.5為什麼使用信息增益比來選擇特徵？ - 知乎

相關閱讀

一條SQL搞定卡方檢驗計算

此文已由作者授權騰訊雲技術社區發布，轉載請註明文章出處