在線游戲用戶的流失預(yù)測：基于不平衡數(shù)據(jù)的采樣方法比較和分析

吳悅昕，趙 鑫，過巖巍，閆宏飛

(北京大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)系，北京 100871)

在線游戲用戶的流失預(yù)測：基于不平衡數(shù)據(jù)的采樣方法比較和分析

吳悅昕，趙 鑫，過巖巍，閆宏飛

(北京大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)系，北京 100871)

流失用戶預(yù)測問題在很多領(lǐng)域都是研究重點(diǎn)。目前主流的流失用戶預(yù)測方法是使用分類法，即把用戶是否會(huì)流失看作一個(gè)二分類問題來處理。該文提出了一個(gè)基于二分類問題解決的在線游戲流失用戶預(yù)測方法。此方法除了總結(jié)了一些對在線游戲而言比較重要的可以用于流失預(yù)測的特征之外，也考慮到流失用戶相對稀少的問題，在流失用戶預(yù)測問題中引入了不平衡數(shù)據(jù)分類的思想。該文主要在流失預(yù)測中結(jié)合使用了基于采樣法的不平衡數(shù)據(jù)處理策略，并對現(xiàn)有主要的幾種采樣算法進(jìn)行了對比實(shí)驗(yàn)和分析。

在線游戲；流失預(yù)測；不平衡數(shù)據(jù)；采樣法

1 引言

流失用戶預(yù)測問題是一個(gè)被廣泛關(guān)注的重要而困難的問題。在電信[1]、銀行[2]、電子商務(wù)[3]等領(lǐng)域，流失用戶預(yù)測都是一個(gè)重要的研究方向。文獻(xiàn)[1]表明，對于電信業(yè)來說，贏得一個(gè)新客戶所花費(fèi)的成本約為$300～600，這大約是保留一個(gè)老客戶所花費(fèi)成本的5～6倍。這對于在線游戲領(lǐng)域來說也是相似的。特別是目前主流的依靠對附加內(nèi)容收費(fèi)的在線游戲，尤其依賴于頻繁、大量向游戲付費(fèi)的高付費(fèi)玩家。高付費(fèi)玩家數(shù)占總玩家數(shù)的比例較小(在數(shù)萬的總游戲人數(shù)中只有4 000個(gè)左右)，因此吸引一個(gè)高付費(fèi)玩家進(jìn)入游戲的成本與保留一個(gè)老的高付費(fèi)玩家的成本之比相對于每個(gè)用戶都需要付費(fèi)的電信業(yè)來說會(huì)更加高昂。這里，本文主要研究在線游戲內(nèi)高付費(fèi)用戶的流失預(yù)測問題。相對于以前的研究，本文主要把重點(diǎn)放在了對數(shù)據(jù)的預(yù)處理上。因?yàn)榱魇ьA(yù)測問題的特點(diǎn)，流失的用戶往往是十分少量的，而正常的活躍用戶數(shù)量相對來說則過于龐大。這種數(shù)據(jù)的不平衡性大大影響了預(yù)測效果。本文通過預(yù)先對數(shù)據(jù)平衡化，使得預(yù)測結(jié)果的F值得到了15%以上的提升，效果十分明顯。這說明數(shù)據(jù)平衡化是提升流失預(yù)測結(jié)果的一個(gè)簡單、有效的手段。

根據(jù)其他行業(yè)內(nèi)的相關(guān)研究[1-2]，我們發(fā)現(xiàn)目前對此類問題主流的處理思路是將其看作二分類的問題，使用有監(jiān)督的機(jī)器學(xué)習(xí)的方法來解決。根據(jù)這個(gè)思路，我們首先需要在游戲原始記錄中總結(jié)出與用戶流失相關(guān)的一些特征，然后利用已知流失與否的用戶記錄來訓(xùn)練并測試分類器，最后測試效果較好的分類器即可用于用戶流失預(yù)警的任務(wù)。

實(shí)際應(yīng)用過程中，我們發(fā)現(xiàn)流失的用戶數(shù)量遠(yuǎn)遠(yuǎn)小于未流失的活躍用戶數(shù)量的。我們手頭的數(shù)據(jù)當(dāng)中流失用戶與沒有流失的活躍用戶數(shù)量之比約為1∶7，屬于不平衡數(shù)據(jù)。傳統(tǒng)的有監(jiān)督的分類模型和算法都必須在相對平衡的數(shù)據(jù)上才能有比較好的效果，而在不平衡度較高的時(shí)候，則會(huì)對多數(shù)類別產(chǎn)生嚴(yán)重的偏向，有時(shí)候甚至?xí)霈F(xiàn)學(xué)習(xí)到的分類器會(huì)把所有輸入的未標(biāo)記數(shù)據(jù)都標(biāo)記為多數(shù)類別的情況。不平衡數(shù)據(jù)問題在各個(gè)領(lǐng)域的流失用戶預(yù)測問題中基本上都是普遍存在的，但目前對流失用戶預(yù)測問題的研究方向主要是深入挖掘原始記錄，對各個(gè)記錄與用戶的流失傾向性的關(guān)聯(lián)進(jìn)行分析(如文獻(xiàn)[4]通過數(shù)據(jù)挖掘發(fā)現(xiàn)呼叫模式變化可以有效預(yù)測電信用戶流失)，以及使用復(fù)雜的分類模型，使之更適應(yīng)于流失預(yù)測的任務(wù)(如文獻(xiàn)[5]將混合過程神經(jīng)網(wǎng)絡(luò)方法應(yīng)用到了流失用戶預(yù)測任務(wù)中)，并沒有對不平衡數(shù)據(jù)進(jìn)行針對性的處理。文獻(xiàn)[6]考慮到了不平衡數(shù)據(jù)對預(yù)測的影響，但只采用了基于代價(jià)敏感學(xué)習(xí)的思路，通過改進(jìn)的支持向量機(jī)來建立模型，方法比較單一，缺乏通用性。

而我們則嘗試轉(zhuǎn)換思路，使用了采樣法對訓(xùn)練數(shù)據(jù)集進(jìn)行調(diào)整，實(shí)現(xiàn)不平衡數(shù)據(jù)的平衡化處理。這樣的處理方法通用性強(qiáng)，不需要過于深入挖掘特征和研究復(fù)雜模型，可以很容易地應(yīng)用到不同領(lǐng)域的流失用戶預(yù)測當(dāng)中。本文研究了目前主流的基于采樣的不平衡數(shù)據(jù)處理方法，將其結(jié)合到我們的流失用戶預(yù)測問題上進(jìn)行了實(shí)驗(yàn)，并對這些方法進(jìn)行了測試、分析和比較。在不進(jìn)行不平衡數(shù)據(jù)處理時(shí)，應(yīng)用支持向量機(jī)進(jìn)行分類實(shí)驗(yàn)只能達(dá)到32.8%的正類F值和0.600的正類ROC-AUC。在使用采樣法進(jìn)行處理之后，這兩者最高分別被提升到48.7%和0.737，提升十分顯著。

2 在線游戲流失用戶預(yù)測問題和方法簡介

2.1 問題和處理框架

我們的在線游戲流失用戶預(yù)測任務(wù)的問題在于根據(jù)所有高付費(fèi)用戶最近一段時(shí)間的原始游戲記錄來預(yù)測哪些用戶會(huì)在一段較短時(shí)間內(nèi)有較大可能性從游戲中流失。

因?yàn)槲覀円呀?jīng)擁有了所有高付費(fèi)用戶的完整游戲記錄以及他們的流失情況，因此我們可以使用有監(jiān)督的機(jī)器學(xué)習(xí)方法來尋找這些游戲記錄與用戶的流失傾向之間的內(nèi)在關(guān)系。我們使用二分類問題的框架來處理流失預(yù)測問題： 每個(gè)用戶有一個(gè)表示其是否流失的流失標(biāo)簽以及一系列狀態(tài)特征，對于有確定標(biāo)簽的用戶，我們使用其狀態(tài)特征來訓(xùn)練一個(gè)兩輸出的分類器用于預(yù)測無標(biāo)簽用戶的流失標(biāo)簽。由于我們已經(jīng)有了用戶的流失標(biāo)簽，因此我們的任務(wù)在于以下兩方面： 從龐雜的游戲記錄中總結(jié)出與用戶流失傾向相關(guān)的狀態(tài)特征，以及找到一個(gè)能夠盡可能提升預(yù)測結(jié)果的分類器訓(xùn)練方法。

2.2 特征提取

我們找到的與在線游戲流失用戶預(yù)測任務(wù)相關(guān)的論文只有文獻(xiàn)[7]，而此文獻(xiàn)使用基于社會(huì)影響的方法進(jìn)行分析，這與我們通過游戲行為分析的任務(wù)不符。由于沒有相關(guān)的工作可以參考，因此我們自行對游戲記錄進(jìn)行了一定的分析，提取了一些特征。我們希望提取的特征可以在計(jì)算上比較簡單，與我們手頭的游戲記錄能夠比較契合，并且能夠大致對用戶的活躍程度進(jìn)行描述。

我們最后使用的特征有四大類，共17小類，具體的每類特征選用見表1。對每個(gè)小類的特征來說，具體的特征以天為單位計(jì)算。以登錄時(shí)間為例，我們計(jì)算用戶每天的登錄時(shí)間，并將其作為一個(gè)特征，故每小類特征中的特征數(shù)等于我們考慮的游戲天數(shù)。對每個(gè)用戶來說，我們選取其最后一次登錄之前若干天的游戲情況作為其特征。例如，使用十天的游戲情況，則按之前的描述，就會(huì)產(chǎn)生170個(gè)特征。這些特征都會(huì)進(jìn)行歸一化處理。

表1 特征列表

續(xù)表

最后，為了實(shí)現(xiàn)預(yù)測，每個(gè)用戶最后若干天的游戲情況將不參與到特征計(jì)算中。例如，我們不考慮每個(gè)用戶最后四天的游戲情況，意味著我們意圖實(shí)現(xiàn)一個(gè)能夠至少提前四天預(yù)測用戶是否流失的分類器。

2.3 分類器訓(xùn)練與不平衡數(shù)據(jù)

確定需要使用的狀態(tài)特征之后，我們可以把每個(gè)用戶表示為一個(gè)二元組(x,y)， 其中x為我們選用的狀態(tài)特征組成的特征向量，y為類別標(biāo)簽(流失或活躍)。給定一組用戶數(shù)據(jù)集合{(x,y)}，我們可以利用其訓(xùn)練一個(gè)分類器。訓(xùn)練得到的分類器可以用于預(yù)測無標(biāo)簽數(shù)據(jù)的類別，實(shí)現(xiàn)流失預(yù)測。這里我們定義流失用戶為正類，活躍用戶為負(fù)類。

通常，流失用戶的數(shù)量大大低于活躍用戶的數(shù)量。對于傳統(tǒng)分類器來說，不平衡數(shù)據(jù)會(huì)對其性能產(chǎn)生顯著的影響[8]。傳統(tǒng)分類器在訓(xùn)練階段并不考慮數(shù)據(jù)中可能的不平衡性，在構(gòu)造一個(gè)對于訓(xùn)練數(shù)據(jù)集錯(cuò)誤率最小的模型的時(shí)候，就會(huì)產(chǎn)生對于多數(shù)類別的嚴(yán)重傾向。這是由于少數(shù)類的實(shí)例過于稀疏，使得分類器無法正確學(xué)習(xí)到其中的各個(gè)子概念[9-11]。對于多數(shù)類來說，由于擁有龐大的數(shù)據(jù)，這種沒能被規(guī)則充分描述的子概念很少出現(xiàn)；而對于少數(shù)類別來說，這種情況就比較嚴(yán)重，分類器很難判斷對于一些少數(shù)類實(shí)例，是應(yīng)該視其表達(dá)了一個(gè)子概念，還是將其視為噪音。因此，這樣學(xué)習(xí)到的模型無法對少數(shù)類有較好的分類效果。

鑒于傳統(tǒng)分類器在大部分問題上的有效性，我們還是在應(yīng)用傳統(tǒng)分類器的基礎(chǔ)上進(jìn)行不平衡數(shù)據(jù)的處理，目前的研究也主要基于這個(gè)方向。一些方法只對某種特定的分類器有用，如決策樹[12]和神經(jīng)網(wǎng)絡(luò)[13]，因此在應(yīng)用上有不少局限。本文主要著眼于能與大部分分類器配合的具有一般性的方法。處理不平衡數(shù)據(jù)的主要思路是使數(shù)據(jù)平衡化，而數(shù)據(jù)平衡化可以在訓(xùn)練前或訓(xùn)練時(shí)完成。采樣法[14-15]通過在訓(xùn)練前對數(shù)據(jù)平衡化來解決不平衡數(shù)據(jù)問題，而代價(jià)敏感學(xué)習(xí)[16]則采用的是在訓(xùn)練時(shí)對少數(shù)類進(jìn)行補(bǔ)償?shù)姆椒?。研究表明，代價(jià)敏感學(xué)習(xí)與以采樣法有很強(qiáng)的相關(guān)性[17-19]，因此本文主要基于采樣法來對用戶流失預(yù)測問題進(jìn)行處理。

3 使用不平衡數(shù)據(jù)進(jìn)行用戶流失預(yù)測

3.1 采樣法概述

所謂采樣法(Sampling)，是一種處理數(shù)據(jù)的技術(shù)。其主要思路是對不平衡的訓(xùn)練集數(shù)據(jù)進(jìn)行修改，構(gòu)造出一個(gè)不平衡度減小的相對平衡的數(shù)據(jù)集。采樣法主要分為兩種，Under Sampling與Over Sampling。本文定義所有用于訓(xùn)練的已經(jīng)有標(biāo)簽的用戶特征數(shù)據(jù)構(gòu)成集合S，Smaj為S中所有活躍用戶的集合，Smin為S中所有流失用戶的集合。顧名思義，Under Sampling方法減少Smaj中的用戶數(shù)，得到其的一個(gè)子集Emaj，并讓其與Smin一同訓(xùn)練分類器。Over Sampling方法則相反，通過增加Smin的用戶數(shù)，得到新集合Emin，然后讓其與Smaj一同訓(xùn)練分類器。

假定我們手頭的數(shù)據(jù)中有500個(gè)活躍用戶，50個(gè)流失用戶。直接使用這些數(shù)據(jù)訓(xùn)練分類器得不到很好的效果，于是我們事先對數(shù)據(jù)進(jìn)行采樣處理。如果我們選擇使用某種方法將活躍用戶數(shù)量減少，假設(shè)減少到100個(gè)，這就屬于Under Sampling方法；如果我們選擇某種手段將流失用戶數(shù)量增加，假定增加到300，這就屬于Over Sampling方法。

下面介紹幾種常用的采樣算法。

3.2 隨機(jī)采樣

隨機(jī)采樣分為隨機(jī)Under Sampling與隨機(jī)Over Sampling。隨機(jī)Under Sampling就是說從Smaj中隨機(jī)選出一個(gè)事先給定了大小的子集構(gòu)成集和Emaj來代替Smaj。而隨機(jī)Over Sampling則不斷隨機(jī)從Smin中選取用戶，然后將其副本放入Smin，直到其成為一個(gè)事先給定了大小的集合Emin，并用其替代原來的Smin。這兩種算法的優(yōu)點(diǎn)是簡單，容易理解和實(shí)現(xiàn)。

如果參照我們上面的例子，隨機(jī)Under Sampling算法會(huì)隨機(jī)從500個(gè)活躍用戶中選擇100個(gè)用于最終訓(xùn)練，而隨機(jī)Over Sampling算法會(huì)隨機(jī)創(chuàng)建流失用戶數(shù)據(jù)的副本直到數(shù)量達(dá)到300，然后進(jìn)行訓(xùn)練。

兩種隨機(jī)采樣方法看起來是等價(jià)的，因?yàn)樗麄兛梢园言瓟?shù)據(jù)集調(diào)整到一個(gè)相同的不平衡度。但實(shí)際上，兩者都有各自的問題，使得分類器學(xué)習(xí)到的模型產(chǎn)生偏誤[10，20-21]。隨機(jī)Under Sampling的問題比較明顯，就是可能會(huì)把Smaj中體現(xiàn)活躍用戶概念的較重要、信息量大的用戶移除，降低分類器的學(xué)習(xí)效果[22]。隨機(jī)Over Sampling的問題則比較隱蔽。其問題在于，隨機(jī)Over Sampling的過程相當(dāng)于產(chǎn)生Smin中用戶的簡單拷貝，因此在特征空間中某些點(diǎn)會(huì)堆積過多的用戶實(shí)例，使得分類器的訓(xùn)練產(chǎn)生過擬合的現(xiàn)象，即訓(xùn)練得到的模型過于復(fù)雜使得能夠比較精確地?cái)M合訓(xùn)練集中的用戶，但對新用戶的分類效果卻產(chǎn)生了下降[20]。

3.3 有導(dǎo)向的Under Sampling

隨機(jī)Under Sampling的問題是可能會(huì)移除比較重要的用戶，因此改進(jìn)的方法就是分析Smaj中的用戶特征，并移除其中相對不重要的那些用戶，達(dá)到Under Sampling的效果。這就形成了有導(dǎo)向的Under Sampling方法。

一種檢測用戶信息的方法是使用用戶特征的K近鄰信息(KNN Under Sampling)[23]。此方法認(rèn)為離Smin中用戶距離較遠(yuǎn)(即與流失用戶較不相似)的用戶所含信息較少，并選取那些離Smin中用戶距離較近的Smaj中用戶來構(gòu)成集合Emaj。一個(gè)效果相對較好的距離計(jì)算方法是計(jì)算Smaj中每個(gè)用戶與所有Smin中用戶距離值當(dāng)中K個(gè)最大值的平均值來作為其與Smin的距離。然后根據(jù)事先給定的數(shù)量選取距離較小的一部分用戶組成Emaj。以之前的例子來說，我們需要計(jì)算所有500個(gè)活躍用戶和與之距離最遠(yuǎn)的K個(gè)流失用戶的平均距離，然后選出此距離值最小的100個(gè)活躍用戶用于最終訓(xùn)練。

另一種移除信息量小的用戶的方法是利用所謂的濃縮近鄰法(Condensed Nearest Neighbor Rule，簡稱CNN)[23]。這個(gè)方法選取S的一個(gè)一致子集合E來代替S。所謂E是S的一致子集合指E是S的子集且利用E訓(xùn)練的1-近鄰分類器可以對S進(jìn)行完全正確的分類，即對S中每個(gè)用戶找到其在E中距離最近的用戶，兩者所屬類別相同。S的一致子集合E的構(gòu)造方法為，先取E等于Smin，然后在E中加入任取的一個(gè)Smaj中用戶。之后利用E對Smaj中每個(gè)用戶進(jìn)行1-近鄰分類，如果分類錯(cuò)誤就把該用戶加入E。這樣構(gòu)造的一致子集合并不一定是最小的，但實(shí)踐表明通過這個(gè)方法可以充分縮小原始數(shù)據(jù)集。CNN方法通常會(huì)和之后提到的數(shù)據(jù)清理算法結(jié)合使用。

3.4 人工數(shù)據(jù)構(gòu)造法

人工數(shù)據(jù)構(gòu)造法是一種Over Sampling方法。由于隨機(jī)Over Sampling方法容易產(chǎn)生過擬合的現(xiàn)象，為了減小過擬合，Over Sampling方法加入的數(shù)據(jù)最好不是已有數(shù)據(jù)的簡單拷貝。于是產(chǎn)生了人工數(shù)據(jù)構(gòu)造法，將基于原數(shù)據(jù)集中用戶構(gòu)造的人工數(shù)據(jù)加入以實(shí)現(xiàn)Over Sampling。

一個(gè)廣泛使用的人工數(shù)據(jù)構(gòu)造法是SMOTE(the synthetic minority oversampling technique)[25]，是一個(gè)基于K近鄰用戶來構(gòu)造人工數(shù)據(jù)的方法。SMOTE方法為Smin中每個(gè)用戶構(gòu)造若干新用戶。為Smin中用戶xi構(gòu)造新用戶時(shí)，先找到其在Smin中的K個(gè)最鄰近用戶，并在其中隨機(jī)選取一個(gè)用戶xj，則構(gòu)造的新用戶為xnew=xi+(xj-xi)*δ，其中δ是0到1之間的一個(gè)隨機(jī)數(shù)。實(shí)際上，構(gòu)造的新用戶就是xi與xj在特征空間中連線上的一點(diǎn)。以前文的例子來說，我們需要構(gòu)建250個(gè)人工流失用戶。構(gòu)造每個(gè)人工流失用戶時(shí)，我們首先隨機(jī)選取一個(gè)流失用戶作為樣本，然后再隨機(jī)從它的K近鄰中選取一個(gè)流失用戶作為參考，新生成的流失用戶是這兩個(gè)流失用戶連線上隨機(jī)選取的一點(diǎn)。

3.5 有導(dǎo)向的人工數(shù)據(jù)構(gòu)造法

SMOTE方法構(gòu)造人工數(shù)據(jù)時(shí)，Smin中的每個(gè)用戶的地位是相同的，根據(jù)每個(gè)用戶構(gòu)造的新用戶數(shù)量是相同的。但實(shí)際上，每個(gè)用戶的信息量不同，因此需要構(gòu)造的人工用戶的數(shù)量也往往不同。因此產(chǎn)生了根據(jù)用戶的K鄰近信息來計(jì)算需要生成的新用戶數(shù)量的方法。

BorderLine方法[26]只為Smin中“危險(xiǎn)”的用戶構(gòu)造人工用戶。所謂“危險(xiǎn)”的用戶指這樣的用戶，其在所有用戶集S中的K近鄰中，屬于Smaj的用戶數(shù)量大于等于K/2而小于K。這里K近鄰用戶都屬于Smaj時(shí)則被考慮為噪音而不為其構(gòu)造人工數(shù)據(jù)。BorderLine方法通過增加兩類邊界處的流失用戶數(shù)量來豐富流失用戶的邊界，使分類器偏向流失用戶。

ADASYN方法[27]則比較直觀。此方法計(jì)算Smin中所有用戶的K近鄰中屬于Smaj的用戶所占的比例，然后以此比例值為權(quán)值來分配每個(gè)用戶需要構(gòu)造的新用戶的數(shù)量。這樣，越“危險(xiǎn)”的用戶會(huì)被構(gòu)造越多的新用戶，分類器就會(huì)給予其更多的偏向。

3.6 數(shù)據(jù)清理方法

數(shù)據(jù)清理方法是一種清除類間重疊的采樣方法。常用的數(shù)據(jù)清理方法是基于Tomek Link的數(shù)據(jù)清理方法[28]。Tomek Link指一個(gè)用戶對，其中xi∈Smaj，xj∈Smin，并且不存在xk∈S，使得d(xi,xj)>d(xi,xk)或d(xi,xj)>d(xk,xj)，其中d(x,y)指用戶x與y特征向量之間的歐氏距離。容易知道，一個(gè)Tomek Link中的兩個(gè)用戶或是位于類邊界的兩側(cè)，或是至少有一個(gè)是噪音。使用Tomek Link進(jìn)行數(shù)據(jù)清理時(shí)，可以將其作為一種Under Sampling方法，去除每個(gè)Tomek Link中屬于Smaj的用戶。此時(shí)，通常將其和之前提到的CNN方法結(jié)合使用。One Side Selection方法[29]就是這樣的Under Sampling方法，此方法先通過Tomek Link對原數(shù)據(jù)集進(jìn)行一次Under Sampling，然后再使用CNN方法進(jìn)行一次Under Sampling。由于Tomek Link的計(jì)算比較耗時(shí)，因此也有人先采用CNN方法，然后再使用Tomek Link進(jìn)行Under Sampling(CNN+Tomek Link方法)[6]。也可以將Tomek Link作為對其他采樣算法進(jìn)行數(shù)據(jù)清理的方法，此時(shí)可以通過清除每個(gè)Tomek Link中的所有用戶來實(shí)現(xiàn)數(shù)據(jù)清理?；赟MOTE的方法常和此類數(shù)據(jù)清理方法結(jié)合使用[22]。

3.7 采樣法總結(jié)

表2對本文之前介紹的各個(gè)采樣方法進(jìn)行了簡單總結(jié)。

表2 基于采樣法的不平衡數(shù)據(jù)處理方法

4 實(shí)驗(yàn)設(shè)置

4.1 數(shù)據(jù)準(zhǔn)備

我們已經(jīng)有了原始的游戲記錄、用戶列表、用戶標(biāo)簽以及要抽取的特征列表。我們要做的是得到能夠用于輸入分類器的代表每個(gè)用戶的特征和標(biāo)簽的組合。因?yàn)樘卣魇且蕴鞛閱挝挥?jì)算的，因此我們需要先掃描記錄，把需要計(jì)算特征的用戶的游戲記錄按天分割開，然后為每個(gè)選定的用戶逐天計(jì)算各個(gè)特征。每個(gè)用戶的特征值需要進(jìn)行歸一化才能在分類中有較好效果。歸一化過程先計(jì)算所有高付費(fèi)用戶每個(gè)特征每天的平均值，然后計(jì)算用戶每個(gè)特征每天的值與對應(yīng)的平均值之比，將其作為最后使用的特征值。最后根據(jù)需要使用的特征以及天數(shù)，構(gòu)造可以用于分類訓(xùn)練和測試的特征文件。最后得到的數(shù)據(jù)集中一共有3 898個(gè)用戶實(shí)例，其中496個(gè)屬于正類(流失用戶)，3 402個(gè)屬于負(fù)類(活躍用戶)。

4.2 結(jié)果評價(jià)

本文使用支持向量機(jī)(使用RBF核函數(shù))作為基本分類器，并采用五折交叉驗(yàn)證的方式對結(jié)果進(jìn)行評價(jià)。通常在不平衡數(shù)據(jù)中，人們重點(diǎn)關(guān)注正類的分類效果，因此對正類的分類結(jié)果單獨(dú)計(jì)算得到的準(zhǔn)確率、召回率、F值、ROC曲線等將更適合于評價(jià)對不平衡數(shù)據(jù)的分類效果。下面對本文使用的評價(jià)指標(biāo)進(jìn)行詳細(xì)介紹。

圖1 困惑矩陣

對于二分類問題而言，每個(gè)用戶的分類結(jié)果可能有四種情況，如圖1的困惑矩陣所示。因此，對于正類來說，其準(zhǔn)確率的定義為TP/(TP+FP)，即分類器報(bào)告的正類用戶中真正正類用戶所占的比率；召回率的定義為TP/(TP+FN)，即分類器正確報(bào)告的正類用戶占所有正類用戶的比率。正類的F值就是正類的準(zhǔn)確率和召回率的調(diào)和平均數(shù)。負(fù)類的準(zhǔn)確率、召回率、F值也可以按類似方式定義。

ROC曲線[19，22]是分類結(jié)果中TP率和FP率的曲線。TP率的定義為TP/(TP+FN)，等于正類召回率；FP率的定義為FP/(FP+TN)，等于1-負(fù)類召回率。使用ROC曲線來作為分類器效果的評價(jià)標(biāo)準(zhǔn)時(shí)，多采用ROC曲線下方面積(簡寫為ROC-AUC)來作為數(shù)值化的標(biāo)準(zhǔn)。圖2中，孤線的結(jié)果優(yōu)于直線，ROC-AUC也更大。

圖2 ROC曲線示意

5 實(shí)驗(yàn)結(jié)果及分析

5.1 各種不平衡數(shù)據(jù)處理方法實(shí)驗(yàn)結(jié)果和分析對比

首先我們考察每種采樣方法在設(shè)置不同的采樣比率后可以達(dá)到的最好結(jié)果，評價(jià)標(biāo)準(zhǔn)分別為正類F值和ROC-AUC。此處我們設(shè)置使用所有特征，使用的特征天數(shù)為十天，提前天數(shù)為四天，使用五折交叉驗(yàn)證來檢驗(yàn)分類結(jié)果。每個(gè)結(jié)果都是三次重復(fù)實(shí)驗(yàn)的平均值。

由圖3可知，所有采樣算法在最好情況下兩個(gè)指標(biāo)都大大優(yōu)于不進(jìn)行采樣處理的情況。對于四種Under Sampling算法來說，兩個(gè)指標(biāo)在最好情況下都劣于所有的Over Sampling算法。Under Sampling算法中最好的是隨機(jī)Under Sampling算法，說明其他方法在保留信息量大的負(fù)類用戶方面效果都比較一般。Over Sampling算法相差都不大，其中最好的是ADASYN算法。另外在使用Tomek Link進(jìn)行處理后，各個(gè)Over Sampling算法的效果都產(chǎn)生了一定的下降。這主要是因?yàn)楸疚氖褂弥С窒蛄繖C(jī)作為基本分類器，而支持向量機(jī)使用支持向量作為分類依據(jù)，因此對擴(kuò)展類邊界和移除噪音有幫助的數(shù)據(jù)清理算法對于支持向量機(jī)來說很難產(chǎn)生正向的改進(jìn)。

然后我們來看采樣比率變動(dòng)對不同采樣算法的影響。采樣比率指應(yīng)用采樣法后被增加或減少的那類的實(shí)例數(shù)與采樣前之比。首先我們來看Under Sampling算法。圖4左邊是兩種可改變采樣比率的Under Sampling算法在不同比率下正類F值和ROC-AUC值的變化情況?？梢钥闯鰩缀踉谒斜嚷氏拢瑑蓚€(gè)指標(biāo)都是隨機(jī)Under Sampling算法較高。不過，對隨機(jī)Under Sampling算法來說，兩個(gè)指標(biāo)有較明顯的峰值，而KNN算法則相對平緩。然后考察采樣比率變化時(shí)正類準(zhǔn)確率與召回率的變化。圖4右邊表示，隨著采樣比率的升高，兩者都出現(xiàn)正類準(zhǔn)確率升高，而召回率下降的情況。這是因?yàn)椴蓸颖嚷侍嵘臅r(shí)候，數(shù)據(jù)集中屬于負(fù)類的用戶數(shù)量增加，此時(shí)分類器會(huì)縮小識別到的正類的概念空間，擴(kuò)大負(fù)類的概念空間。在采樣比率設(shè)置過低的時(shí)候，分類器學(xué)習(xí)到的正類的概念空間過大，因此會(huì)錯(cuò)誤地把很多多數(shù)負(fù)類用戶識別為正類，使得正類的準(zhǔn)確率偏低而召回率較高。在采樣比率提升時(shí)這種傾向就會(huì)逐漸降低，導(dǎo)致正類準(zhǔn)確率升高，而召回率下降。另外，正類召回率基本上都是KNN Under Sampling較高。這似乎違反了直觀，因?yàn)镵NN Under Sampling優(yōu)先保留與正類用戶接近的負(fù)類用戶，這樣應(yīng)該會(huì)減少識別到的正類概念空間，導(dǎo)致正類召回率降低。不過，事實(shí)上這些被優(yōu)先保留的用戶往往較多屬于噪音而較少處于類邊界上，而目前分類器對噪音都有一定的容忍度，因此識別到的正類概念空間在同等情況下會(huì)稍大。

圖3 各采樣法最佳效果對比

圖4 采樣比率變化對Under Sampling算法的影響

對于Over Sampling算法來說，采樣比率對準(zhǔn)確率和召回率也有類似的影響。隨著采樣比率的升高，Over Sampling算法出現(xiàn)正類準(zhǔn)確率下降，而召回率升高的情況。這也是由于分類器學(xué)習(xí)到的正類的概念空間的改變所導(dǎo)致的，這里不再進(jìn)行詳細(xì)的分析。

5.2 改變使用的特征對結(jié)果的影響

這里我們考察使用不同大類的特征時(shí)對結(jié)果的影響。之前的結(jié)果都是使用了所有四大類特征得到的，這里嘗試只使用其中的某個(gè)大類的特征來進(jìn)行分類實(shí)驗(yàn)。結(jié)果如圖5。由于實(shí)驗(yàn)結(jié)果當(dāng)中F值與ROC-AUC的變化趨勢基本相同，因此為了簡明起見本文僅展示了ROC-AUC的結(jié)果進(jìn)行對比。

圖5 單獨(dú)使用不同類特征時(shí)對預(yù)測結(jié)果的影響

可以發(fā)現(xiàn)，單獨(dú)使用在線情況進(jìn)行分類實(shí)驗(yàn)的時(shí)候，在多數(shù)采樣方法下結(jié)果是最好的，甚至優(yōu)于使用所有大類特征時(shí)的效果。這說明在線情況在我們的數(shù)據(jù)當(dāng)中是一個(gè)最有力的表現(xiàn)用戶的活躍情況的特征。對于其他大類的特征來說，貨幣花費(fèi)對于用戶流失的預(yù)測效果是四大類中最差的。這點(diǎn)比較出乎我們的意料，因?yàn)槲覀冾A(yù)期對于高付費(fèi)用戶來說，真實(shí)貨幣的花費(fèi)應(yīng)是其活躍度的一個(gè)直接反映。實(shí)際分析之后發(fā)現(xiàn)，高付費(fèi)用戶在流失之前既可能如我們之前預(yù)測的那樣減低貨幣花費(fèi)，也可能反而增加花費(fèi)。增加花費(fèi)的一個(gè)可能是用戶之前已經(jīng)在游戲內(nèi)充入一定量的真實(shí)貨幣，因此想在退出游戲之前將其消耗完；另一個(gè)可能是用戶在離開游戲之前會(huì)有一定的賭博心態(tài)，從而會(huì)先執(zhí)行一些充值抽獎(jiǎng)?lì)惖牟僮鳎绻泻玫墨@得則繼續(xù)一段時(shí)間的游戲，否則徹底退出游戲。這樣，貨幣花費(fèi)對與用戶活躍程度的預(yù)測能力就下降了。最后，我們發(fā)現(xiàn)在不進(jìn)行采樣處理時(shí)，單獨(dú)使用除在線情況之外的某一大類特征時(shí)最后結(jié)果都較差，ROC-AUC與0.5十分接近。而進(jìn)行采樣算法后，效果大大提升，有些甚至已經(jīng)比較接近使用所有大類特征時(shí)的效果。這表明在特征選取相對不完善時(shí)，不平衡數(shù)據(jù)會(huì)將這種不完善性放大，使得分類的結(jié)果急劇惡化。在使用采樣法弱化不平衡數(shù)據(jù)問題之后，我們發(fā)現(xiàn)其實(shí)特征的不完善程度并沒有太高，各個(gè)大類的特征都能夠在一定程度上反映用戶的活躍程度。也就是說，即使我們不能找到非常適合于流失預(yù)測的特征，在使用采樣法之后我們也能取得相對可以接受的預(yù)測效果。

6 總結(jié)

在流失預(yù)測的任務(wù)當(dāng)中，本文創(chuàng)新性地采用了基于采樣法的不平衡數(shù)據(jù)處理方法，并將其應(yīng)用在了一個(gè)新的領(lǐng)域——在線游戲領(lǐng)域中，取得了較好的效果。由于考慮了不平衡數(shù)據(jù)處理，因此即使在特征相對不完善時(shí)也能取得相對較好的預(yù)測效果。這樣的結(jié)果為流失用戶預(yù)測問題提供了一個(gè)新的思路，即在不過分深入地挖掘特征以及改進(jìn)模型的情況下，通過對數(shù)據(jù)集的針對性處理來提升預(yù)測結(jié)果。未來我們可以繼續(xù)嘗試其他的不平衡數(shù)據(jù)處理法，以及將目前的方法應(yīng)用到其他領(lǐng)域當(dāng)中，通過繼續(xù)研究來讓我們的方法更加完善。另外，本文的方法主要還是一個(gè)離線算法，而實(shí)際的流失預(yù)測問題通常須要在一個(gè)在線的環(huán)境中實(shí)現(xiàn)動(dòng)態(tài)地預(yù)測。為了將我們的方法應(yīng)用到在線的環(huán)境中去，我們將來還需要考慮很多方面的問題，例如，對模型進(jìn)行更新、重新訓(xùn)練的時(shí)機(jī)和如何加快訓(xùn)練、預(yù)測的速度等。這些也構(gòu)成了未來流失預(yù)測問題研究方向的重要一環(huán)。

[1] 夏國恩, 金煒東. 基于支持向量機(jī)的客戶流失預(yù)測模型 [J]. 系統(tǒng)工程理論與實(shí)踐, 2008, 28(1): 71-77.

[2] 應(yīng)維云, 覃正, 趙宇, 等. SVM 方法及其在客戶流失預(yù)測中的應(yīng)用研究 [J]. 系統(tǒng)工程理論與實(shí)踐, 2007, 27(7): 105-110.

[3] 朱幫助, 張秋菊. 電子商務(wù)客戶流失三階段預(yù)測模型[J]. 中國軟科學(xué), 2010，(06): 186-192.

[4] Wei C P, Chiu I. Turning telecommunications call details to churn prediction: a data mining approach[J]. Expert systems with applications, 2002, 23(2): 103-112.

[5] Song Guojie, Yang Dongqing, Wu Ling, et al. A mixed process neural network and its application to churn prediction in mobile communications[C]//Proceedings of Sixth IEEE International Conference, 2006: 798-802.

[6] 錢蘇麗, 何建敏, 王純麟. 基于改進(jìn)支持向量機(jī)的電信客戶流失預(yù)測模型[J]. 管理科學(xué), 2007, 20(1).

[7] Kawale J, Pal A, Srivastava J. Churn prediction in MMORPGs: A social influence based approach[C]//Proceedings of Computational Science and Engineering, 2009. CSE′09. International Conference on. IEEE, 2009, 4: 423-428.

[8] Chawla N V, Japkowicz N, Kotcz A. Editorial: special issue on learning from imbalanced data sets[J]. ACM SIGKDD Explorations Newsletter, 2004, 6(1): 1-6.

[9] Weiss G M. Mining with rarity: a unifying framework[J]. Sigkdd Explorations, 2004, 6(1): 7-19.

[10] Holte R C, Acker L E, Porter B W. Concept learning and the problem of small disjuncts[C]//Proceedings of the Eleventh International Joint Conference on Artificial Intelligence. 1989, 1.

[11] Quinlan J R. Induction of decision trees[J]. Machine learning, 1986, 1(1): 81-106.

[12] Maloof M A. Learning when data sets are imbalanced and when costs are unequal and unknown[C]//Proceedings of ICML-2003 workshop on learning from imbalanced data sets II. 2003.

[13] Hykin S. Neural networks: A comprehensive foundation[J]. Prentice Hall International, Inc, 1999.

[14] Laurikkala J. Improving identification of difficult small classes by balancing class distribution[J]. Artificial Intelligence in Medicine, 2001: 63-66.

[15] Estabrooks A, Jo T, Japkowicz N. A multiple resampling method for learning from imbalanced data sets[J]. Computational Intelligence, 2004, 20(1): 18-36.

[16] Elkan C. The foundations of cost-sensitive learning[C]//Proceedings of International Joint Conference on Artificial Intelligence. LAWRENCE ERLBAUM ASSOCIATES LTD, 2001, 17(1): 973-978.

[17] Zhou Zhihua, Liu Xuying. Training cost-sensitive neural networks with methods addressing the class imbalance problem[J]. Knowledge and Data Engineering, IEEE Transactions on, 2006, 18(1): 63-77.

[18] McCarthy K, Zabar B, Weiss G. Does cost-sensitive learning beat sampling for classifying rare classes?[C]//Proceedings of the 1 st international workshop on Utility-based data mining. 2005, 21(21): 69-77.

[19] Liu Xuying, Zhou Zhihua. The influence of class imbalance on cost-sensitive learning: An empirical study[C]//Proceedings of Sixth International Conference on. IEEE, 2006: 970-974.

[20] Mease D, Wyner A J, Buja A. Boosted classification trees and class probability/quantile estimation[J]. The Journal of Machine Learning Research, 2007, 8: 409-439.

[21] Drummond C, Holte R C. C4. 5, class imbalance, and cost sensitivity: Why under-sampling beats over-sampling[C]//Proceedings of Workshop on Learning from Imbalanced Datasets II. 2003.

[22] Batista G E, Prati R C, Monard M C. A study of the behavior of several methods for balancing machine learning training data[J]. ACM SIGKDD Explorations Newsletter, 2004, 6(1): 20-29.

[23] Mani I. knn approach to unbalanced data distributions: A case study involving information extraction[C]//Proceedings of Workshop on Learning from Imbalanced Datasets. 2003.

[24] Hart P E. The Condensed Nearest Neighbor Rule[J]. IEEE Transactions on Information Theory, 1968, 14: 515-516.

[25] Chawla N V, Bowyer K W, Hall L O, et al. SMOTE: synthetic minority over-sampling technique[J]. arXiv preprint arXiv:1106.1813, 2011.

[26] Han Hui, Wang Wenyuan, Mao Binghuan. Borderline-SMOTE: A new over-sampling method in imbalanced data sets learning[J]. Advances in Intelligent Computing, 2005: 878-887.

[27] He Haibo, Bai Yang, Garcia E A, et al. ADASYN: Adaptive synthetic sampling approach for imbalanced learning[C]//Proceedings of IEEE International Joint Conference on IEEE, 2008: 1322-1328.

[28] Tomek I. Two modifications of CNN[J]. IEEE Trans. Syst. Man Cybern., 1976, 6: 769-772.

[29] Kubat M, Matwin S. Addressing the curse of imbalanced training sets: one-sided selection[C]//Proceedings of Machine Learning-International Workshop Then Conference-. Morgan Kaufmann Publishers, Inc., 1997: 179-186.

User Churn Prediction for Online Game: Comparison and Analysis of Approaches Based on Sampling for Imbalanced Data

WU Yuexin, ZHAO Xin, GUO Yanwei, YAN Hongfei

(Department of Computer Science and Technology， Peking University, Beijing 100871, China)

The problem of user churn prediction is a research focus in many fields. Currently the main approach of the problem is based on classification, which predicts whether users will churn by a 2-class classification process. This paper addresses an approach for online game user churn prediction based on 2-class classification. We summarize some important features for the problem of online game user churn prediction. Furthermore, we noticed that churned users is relatively rare, and introduce the imbalanced learning methods into our work with a focus on the sampling methods. We conducted experiments on major sampling methods and analyzed the results.

online game; user churn prediction; imbalanced data; sampling

吳悅昕(1989—),碩士,主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘和機(jī)器學(xué)習(xí)。E-mail:wuyuexin@gmail.com趙鑫(1985—),博士,主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)數(shù)據(jù)挖掘和自然語言處理。E-mail:batmanfly@gmail.com過巖巍(1989—),碩士,主要研究領(lǐng)域?yàn)樗阉饕婧途W(wǎng)絡(luò)數(shù)據(jù)挖掘。E-mail:pkuguoyw@gmail.com

1003-0077(2016)04-0213-10

2014-09-10 定稿日期： 2015-03-15

973項(xiàng)目(2014CB340400);國家自然科學(xué)基金(61272340);江蘇未來網(wǎng)絡(luò)創(chuàng)新研究院項(xiàng)目(BY2013095-4-02)

TP

A