林雪云

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

?

基于游戲玩家流失預(yù)警的改進(jìn)決策樹算法

林雪云

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

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

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

0引言

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

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

1決策樹模型

1.1決策樹算法簡(jiǎn)介

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

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

1.2ID3算法與CART算法簡(jiǎn)介

1.2.1ID3(Iterative Dichotomizer 3)算法

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

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

1.2.2CART算法

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

CART算法[3]主要包括3個(gè)部分：

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

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

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

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

1.2.3改進(jìn)算法

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

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

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

1)上線情況。反映上線情況的指標(biāo)有上線時(shí)長(zhǎng)、上線頻率。

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

3)角色情況。反映指標(biāo)主要有角色等級(jí)信息、社群以及參與活動(dòng)信息。

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

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

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

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

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

2.2.1指標(biāo)篩選

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

表1　各成分解釋的方差

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

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

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

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

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

2.2.2決策樹的初步生成

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

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

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

2.2.3決策樹的分支停止

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

ImpN=-jPwjlog2P(wj)

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

2.2.4決策樹的剪枝

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

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

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

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

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

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

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

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

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

3結(jié)語

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

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

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

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

參考文獻(xiàn)：

[1]李華,劉帥,李茂,等.數(shù)據(jù)挖掘理論及應(yīng)用研究[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ù)挖掘算法的應(yīng)用研究[J].煤炭技術(shù),2011,10:165-166.

[4]方敏，牛文科，張曉松.分類回歸樹多吸引子細(xì)胞自動(dòng)機(jī)分類方法及過擬合研究[J].計(jì)算機(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ìn)[J].廈門大學(xué)學(xué)報(bào)：自然科學(xué)版,2007,46(4)：496-500.

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

[8]趙強(qiáng)利，蔣艷凰,盧宇彤.具有回憶和遺忘機(jī)制的數(shù)據(jù)流挖掘模型與算法[J].軟件學(xué)報(bào)，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

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

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

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

中圖分類號(hào)：TP 311.1

文獻(xiàn)標(biāo)志碼：A

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