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

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

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

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

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

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

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

1 引言

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

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

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

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

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

2.1 問題和處理框架

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

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

2.2 特征提取

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

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

表1 特征列表

續(xù)表

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

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

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

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

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

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

3.1 采樣法概述

所謂采樣法(Sampling)，是一種處理數(shù)據(jù)的技術(shù)。其主要思路是對不平衡的訓(xùn)練集數(shù)據(jù)進行修改，構(gòu)造出一個不平衡度減小的相對平衡的數(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ù)，得到其的一個子集Emaj，并讓其與Smin一同訓(xùn)練分類器。Over Sampling方法則相反，通過增加Smin的用戶數(shù)，得到新集合Emin，然后讓其與Smaj一同訓(xùn)練分類器。

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

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

3.2 隨機采樣

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.7 采樣法總結(jié)

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

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

4 實驗設(shè)置

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

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

4.2 結(jié)果評價

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

圖1 困惑矩陣

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

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

圖2 ROC曲線示意

5 實驗結(jié)果及分析

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

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

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

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

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

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

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

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

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

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

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

6 總結(jié)

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

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

[2] 應(yīng)維云, 覃正, 趙宇, 等. SVM 方法及其在客戶流失預(yù)測中的應(yīng)用研究 [J]. 系統(tǒng)工程理論與實踐, 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] 錢蘇麗, 何建敏, 王純麟. 基于改進支持向量機的電信客戶流失預(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)域為數(shù)據(jù)挖掘和機器學(xué)習(xí)。E-mail:wuyuexin@gmail.com趙鑫(1985—),博士,主要研究領(lǐng)域為網(wǎng)絡(luò)數(shù)據(jù)挖掘和自然語言處理。E-mail:batmanfly@gmail.com過巖巍(1989—),碩士,主要研究領(lǐng)域為搜索引擎和網(wǎng)絡(luò)數(shù)據(jù)挖掘。E-mail:pkuguoyw@gmail.com

1003-0077(2016)04-0213-10

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

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

TP

A