基于游戲玩家流失預警的改進決策樹算法

林雪云

(福建師范大學福清分校， 福建 福清　350300)

?

基于游戲玩家流失預警的改進決策樹算法

林雪云

(福建師范大學福清分校， 福建 福清350300)

摘要：首先對樣本數(shù)據(jù)的影響因素進行l(wèi)ogistic回歸剔除絕大部分噪聲因素，再通過降維和共線性診斷進一步篩選出影響因素中對實際結(jié)果有重要影響的指標以及共線性的指標，剔除無用和重復的類別，對清洗后的數(shù)據(jù)進行分析。最后進行了實例驗證。

關(guān)鍵詞：決策樹; 流失預警; 降維; ID3算法; CART算法; logistic回歸

0引言

對網(wǎng)游企業(yè)而言，游戲玩家的流失情況至關(guān)重要，直接關(guān)系到企業(yè)的收益。傳統(tǒng)的數(shù)據(jù)挖掘算法已不再適應時代的需求，針對大數(shù)據(jù)量如果無法快速地獲得行業(yè)中的最新信息，對網(wǎng)游這一及時性和更新頻率極高的行業(yè)而言就是致命的。

研究決策樹在游戲玩家流失預警中的具體應用可以很好地解決這一問題，文中改進的決策樹模型可以用于大數(shù)據(jù)分析，在減少計算量，提高運行效率的同時，增加預測的精確性，方便運營做出更加貼合實際的決策。

1決策樹模型

1.1決策樹算法簡介

決策樹算法[1]是數(shù)據(jù)挖掘算法中的一種分類算法，且在各種分類算法中，決策樹能夠最為直觀看到分類的節(jié)點與方法，也更易于獲得決策，因此被廣泛用于數(shù)據(jù)挖掘中。

游戲玩家的流失預警將會用到ID3算法以及CART算法，兩種算法分別是基于信息增益和節(jié)點不純度的算法，文中通過對兩種算法的結(jié)合獲取最優(yōu)決策樹。

1.2ID3算法與CART算法簡介

1.2.1ID3(Iterative Dichotomizer 3)算法

ID3算法[2]是一種較為經(jīng)典的決策樹算法，算法的主要思想是從根節(jié)點出發(fā)，賦予最優(yōu)屬性，之后將該屬性的每個取值作為一個分支，以其分支為起點生成新的節(jié)點，對最優(yōu)屬性的選擇標準是借鑒于以信息熵為定義的信息增益來選擇每個節(jié)點的測試屬性，熵(Entropy)亦成為了任意樣本集純度的衡量標準。

該算法局限性在于只能針對離散值，且算法在運算時僅考慮一個信息增益方面，即使得越在上層的節(jié)點對目標屬性提供的信息越多，但并未考慮到由于屬性的確定所帶來的不純度方面的影響。且ID3算法所生成的節(jié)點的分類可能有很多無用分類，即很多分類是可以進行合并的。

1.2.2CART算法

決策樹算法實際上就是將樣本劃分成越來越小的子集，最為理想的狀態(tài)即生成的決策樹的所有葉子節(jié)點的標記都是一樣的。如果實現(xiàn)，則決策樹的分支過程應該已經(jīng)停止，因為其中已經(jīng)不包含隱藏的類別了，但是這只是一個理想化的狀態(tài)?，F(xiàn)實數(shù)據(jù)的處理中，由于較大噪聲樣本等情況的存在，劃分往往是很難一步就達到目標的，而分類過程需要不止一步才能達到目標，那么這個分類對的過程即一種遞歸樹的生長過程。CART則是當前僅有的一種通用的樹生長算法。

CART算法[3]主要包括3個部分：

1)節(jié)點屬性選擇原則。CART算法對節(jié)點選擇的原則可以從CART算法的目標出發(fā)來看，就是使得節(jié)點的不純度盡可能的降低，不純度(Impurity)是相對于純度的概念，對一個節(jié)點不純度的衡量往往比對其純度的衡量更為方便，也更加利于分類。

2)分支停止原則。對現(xiàn)實數(shù)據(jù)的處理，往往會由于一些誤差值或者極端值導致一類數(shù)據(jù)無法繼續(xù)細分，這就需要對數(shù)據(jù)分支在什么時候停止進行判定，如果都是分支到不純度達到最小，那么最后的結(jié)果可能是每個節(jié)點只對應一個樣本，設(shè)計最初的目的分類就無法得到體現(xiàn)，因為這樣的結(jié)果最多得到的就是一張巨大的“查找表”，而未實現(xiàn)對數(shù)據(jù)的分類。

一種分支停止原則為驗證和交叉驗證技術(shù)[4-6],即在驗證時選擇部分樣本進行驗證，而另一部分樣本作為測試驗證的樣本集，分支操作直至對于驗證集而言分類誤差最??；另一種分支停止原則即在分支過程中設(shè)置閥值，在分支誤差小于閥值時，停止分支操作。

3)剪枝。實際上是分支的逆過程，在決策樹充分“生長”的情況下對決策樹進行剪枝，即對所有相鄰的節(jié)點，如果剪去這一分支，使得不純度的增長很小，那么這一分支即可抹去。不足之處在于：當數(shù)據(jù)量過大時，為了剔除噪聲因素即剪枝在計算量上的代價過大，甚至于無法實現(xiàn)。

1.2.3改進算法

針對上述ID3算法和CART算法的不足之處，文中提出了一種新的決策樹算法，算法結(jié)合了ID3算法和CART算法，即通過ID3算法來初步生成決策樹，再通過CART算法對決策樹進行剪枝，從信息增益和不純度兩個方面同時考慮，而單純用CART對模型進行剪枝往往會由于數(shù)據(jù)量的過大或者影響因素過多造成計算量的代價過大，所以在進行決策樹模型之前，先通過logistic回歸挑選出對目標變量有顯著影響的因素，再通過降維和共線性診斷進一步剔除無用和重復統(tǒng)計的變量，大大縮減了CART模型的計算量。

2改進的決策數(shù)算法具體實現(xiàn)

在一款游戲的運營中，游戲玩家的流失預警是指對游戲玩家的流失能夠進行預判，使得網(wǎng)游企業(yè)能夠及時調(diào)整游戲的運營，減少由于運營上的過失等造成利益上的損失，實現(xiàn)游戲運營的利潤最大化。游戲玩家流失的影響因素中大致由以下4部分因素組成：

1)上線情況。反映上線情況的指標有上線時長、上線頻率。

2)充值情況。反映指標有充值頻率、充值間隔、首充間隔。

3)角色情況。反映指標主要有角色等級信息、社群以及參與活動信息。

4)游戲廣告宣傳的環(huán)境因素。主要指標為地推效果、廣告來源等。

下面對這4部分因素抽取一段時間數(shù)據(jù)(以14 d為流失標準和考察期間)進行分析。

2.1決策數(shù)算法數(shù)據(jù)源

選取一段時間段游戲玩家的上線、充值、角色情況以及之后的流失情況數(shù)據(jù),總數(shù)據(jù)量18 012條，初始指標41個，通過對玩家上線、充值和角色情況數(shù)據(jù)的分析得到?jīng)Q策樹，從而得到對玩家流失行為發(fā)生的預判模型，對玩家流失風險進行評估。

2.2改進決策數(shù)算法

2.2.1指標篩選

首先對游戲玩家流失數(shù)據(jù)源進行指標粗篩選，由于影響因素較多,所以必須先對模型進行降維，降維方法選擇主成分分析法中的因子分析，因子分析中使用最大方差法得到其旋轉(zhuǎn)解，即新的替代變量，代替原因素進行分析。得到的結(jié)果見表1。

表1　各成分解釋的方差

由表1中“方差的%”項可知各個成分所能夠解釋的方差，選取前5項即解釋方差>5%的成分進行分析。研究所解釋方差>5%的前5項成分的組成因素，選取其中影響較大的因素進行分析，從而獲得玩家流失的主要影響因素有18個。

通過在數(shù)據(jù)源中剔除這18個因素之外的數(shù)據(jù)進行共線性檢驗，得到相關(guān)的關(guān)聯(lián)矩陣表，接著通過多項logistic回歸獲取對游戲玩家流失造成影響的數(shù)據(jù)，使用似然比檢驗，置信區(qū)間設(shè)置為95%。剔除其中共線性的指標，避免重復分類造成分類標準的錯誤導致決策失準[7]。

在剔除方法上文中選擇的是先對游戲玩家流失數(shù)據(jù)源進行降維分析，降維方法通過系數(shù)相關(guān)矩陣來檢驗變量中的共線性，剔除其中的共線性指標。剔除標準為相關(guān)系數(shù)達到75%以上的系數(shù)即可認為存在共線性，即兩者之間有較強的相關(guān)性，在下面的分析中只要選其中解釋方差%更高的一項即可。

從選出的共線性指標的意義來看，共線性的剔除還是有效的，Level和Total_Battle_lev分別為等級和戰(zhàn)斗值，從游戲的角度,等級越高，則其戰(zhàn)斗值越高，Last_login和Last_Server_Date上次登錄時間和上次登錄服務器的時間(這兩個的區(qū)別在于一個是登錄賬號,一個是登錄游戲服務器，玩家一般是登錄賬號之后就登錄游戲服務器開始游戲，但由于之間可能存在的一段時間差,導致數(shù)據(jù)不完全匹配)。

對數(shù)據(jù)進行標準化，以避免由度量問題帶來的誤差，就可以開始對數(shù)據(jù)進行決策樹算法的分類。

2.2.2決策樹的初步生成

因為如果對所有的指標都進行描述則過于繁雜，所以下面算法的具體實現(xiàn)過程是抽取樣例數(shù)據(jù)且抽取關(guān)鍵性指標(即在之后的決策樹結(jié)果中出現(xiàn)的指標Online_Days_byserver、Total_Credit_byserver、Total_Battle_lev進行分析)。

下面對決策樹第一個分類指標的生成(取小樣本數(shù)據(jù)總共537條記錄)進行描述之后的分類指標的生成類似,見表2。

根據(jù)ID3算法得到第一步的決策樹，之后的分類指標及其層次也是按照這個過程獲得。

2.2.3決策樹的分支停止

對于決策樹的分支停止原則，采用熵不純度分至閥值為止。對于節(jié)點N而言，其上的熵不純度為

ImpN=-jPwjlog2P(wj)

式中:P(wj)----節(jié)點N處屬于類別wj的樣本數(shù)占總樣本數(shù)的比重。

2.2.4決策樹的剪枝

決策樹的剪枝過程與分枝停止過程的判斷恰恰相反，分枝停止過程是判斷熵不純度分值低于閥值時停止操作，而決策樹的剪枝則是在決策樹充分生長之后對決策樹中相鄰的節(jié)點進行是否剪枝的判斷，即對抹去一根枝條對熵不純度會不會造成巨大的影響，如果影響較小，那么完全可以剪去這段枝干。至此決策樹的構(gòu)建就已完成。

表2　小數(shù)據(jù)樣本前10條記錄表樣例(部分指標用于闡述算法)

從生成的決策樹中可以看出，玩家是否流失(is_running_off)主要影響因素為Online_Days_byserver(考察期間內(nèi)的登錄天數(shù))，Total_Credit_byserver(總充值)以及Total_Battle_lev(總戰(zhàn)斗力)，且影響能力遞減，Onlie_Days_byserver是玩家是否流失的先決的判定標準，這亦符合現(xiàn)實案例，因為玩家流失的最直觀表現(xiàn)即是不再上線或者由于對游戲的興趣缺乏，只是受既往習慣的影響，隔天等登錄一次游戲，之后就是充值金額以及戰(zhàn)力。充值金額對玩家是否流失的影響在于玩家若是喜愛某款游戲，必會經(jīng)常性或者大量充值游戲，以求在游戲中獲得成就感。最后戰(zhàn)力對玩家流失的影響則不是直觀可以看出，戰(zhàn)力越高的玩家越容易留在游戲中，若是新手并且影響過大則表明游戲機制可能有一定問題，因為這樣會導致新手玩家很難在游戲中存活，游戲很難獲取新玩家進入，那么游戲的盈利能力就會極差。

2.3改進的決策樹與傳統(tǒng)的決策樹算法效果對比

對3種算法在事例數(shù)增加時分類錯誤率的效果進行對比,見表3。

表3　3種算法在事例數(shù)增加時分類錯誤率的效果對比表

下面通過在節(jié)點數(shù)相同情況下3種算法的錯誤率的效果對比來驗證改進算法的有效性，如圖1所示。

從圖中可以看出，改進的決策樹算法相對于傳統(tǒng)的ID3算法以及CART算法而言具有更小的錯誤率，即可以獲得更加準確的決策方案。

圖1　隨著分類節(jié)點數(shù)增加3種算法效果對比圖

3結(jié)語

傳統(tǒng)的決策樹算法在運用到CART算法時，往往由于算法中大量的噪聲指標和數(shù)據(jù)的影響造成數(shù)據(jù)不準，而為了剔除這類指標變量，所付出的代價往往是巨大的計算量，所以,文中在運用決策樹算法的起始步驟中增加了對數(shù)據(jù)源的進一步清洗，主要通過降維和共線性診斷來剔除無用和重復指標[8]。

1)通過主成分分析中的因子分析進行降維，降維時用到的并不是降維后的變量，而是降維后能夠解釋方差百分比較高的因子中所用到的變量(指標)，從而得到對分析結(jié)果有顯著影響的指標。

2)通過logistic回歸以及共線性診斷剔除數(shù)據(jù)源中無用的噪聲指標以及存在共線性關(guān)系的指標，因為這類指標的存在往往會使得同一類的數(shù)據(jù)被強制分類了兩次，造成的不只是計算量上的增加，還有數(shù)據(jù)的多次無用分類，可能對運營決策造成重復分析的影響。而文中用到的方法能夠很好地規(guī)避這類影響。

決策樹算法在決策樹的生成過程中無法無視數(shù)據(jù)量綱，即決策樹的生成中原始數(shù)據(jù)的量綱仍能對文中提到的改進的決策樹算法造成影響，未來的研究方向即在決策樹算法中引入馬氏距離來避免數(shù)據(jù)量綱對決策樹結(jié)果造成的影響，同時也要考慮到由于在模型中對馬氏距離的引入所造成的對數(shù)據(jù)計算量上的代價。

參考文獻：

[1]李華,劉帥,李茂,等.數(shù)據(jù)挖掘理論及應用研究[J].斷塊油氣田,2010,23(1):88-89.

[2]Deng Chengyu, Zhang Jiantao, Liu Yongshan. Researchon dynamic load balancing strategy and corresponding model [J]. Computer Engineering and Applications,2011,47(8):131-134.

[3]陳輝林，夏道勛.基于CART決策樹數(shù)據(jù)挖掘算法的應用研究[J].煤炭技術(shù),2011,10:165-166.

[4]方敏，牛文科，張曉松.分類回歸樹多吸引子細胞自動機分類方法及過擬合研究[J].計算機研究與發(fā)展，2012，49(8):1747-1752.

[5]Maji P. fuzzy-rough supervised attribute clustering algorithm and classification of microarray data [J]. IEEE Trans on System, Man and Cybernetics, Part B,2010,41(2):1-12.

[6]馮少榮.決策樹算法的研究與改進[J].廈門大學學報：自然科學版,2007,46(4)：496-500.

[7]陳戈珩，胡明輝，吳天華.基于支持向量機和HMM的音頻信號分類算法[J].長春工業(yè)大學學報，2015,36(4):369-373.

[8]趙強利，蔣艷凰,盧宇彤.具有回憶和遺忘機制的數(shù)據(jù)流挖掘模型與算法[J].軟件學報，2015,26(10):2567-2578.

Improved decision tree algorithm based on game players erosion warning

LIN Xueyun

(Fuqing Branch, Fujian Normal University, Fuqing 350300， China)

Abstract：First the logistic regression is used to eliminate the noises from the important factors in sample data, and then the influential and collinear indexes in the factors are picked out with dimension reduction and collinear diagnosis to eliminate the useless and redundant data. The processed data are analyzed and verified with examples.

Key words：decision tree; loss of early warning; dimension reduction; ID3 algorithm; CART algorithm; logistic regression.

收稿日期：2016-01-10

基金項目：福建省教育廳B類項目(JB13197)

作者簡介：林雪云(1976-)，女，漢族，福建閩侯人，福建師范大學福清分校副教授，碩士，主要從事數(shù)據(jù)挖掘方向研究,E-mail:58452805@qq.com.

DOI:10.15923/j.cnki.cn22-1382/t.2016.2.16

中圖分類號：TP 311.1

文獻標志碼：A

文章編號：1674-1374(2016)02-0182-05