基于多示例多標記學習的手機游戲道具推薦*

唐　俊，周志華＋1.南京大學計算機軟件新技術國家重點實驗室，南京2100232.軟件新技術與產業化協同創新中心，南京210023

* The National Natural Science Foundation of China under Grant No. 61333014（國家自然科學基金）.

Received 2015-05，Accepted 2015-08.

CNKI網絡優先出版：2015-08-13，http://www.cnki.net/kcms/detail/11.5602.TP.20150813.1552.004.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10（01）-0103-09

?

基于多示例多標記學習的手機游戲道具推薦*

唐俊1，2，周志華1，2＋
1.南京大學計算機軟件新技術國家重點實驗室，南京210023
2.軟件新技術與產業化協同創新中心，南京210023

* The National Natural Science Foundation of China under Grant No. 61333014（國家自然科學基金）.

Received 2015-05，Accepted 2015-08.

CNKI網絡優先出版：2015-08-13，http://www.cnki.net/kcms/detail/11.5602.TP.20150813.1552.004.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10（01）-0103-09

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel:＋86-10-89056056

摘要：手機游戲提供商通過在游戲中銷售虛擬道具來獲得收益。將游戲玩家日志數據中每個事件描述為一個示例，玩家對多種游戲道具的購買狀態表示為多個標記，從而將游戲道具推薦問題抽象為多示例多標記學習問題。在此基礎上，將快速多示例多標記學習算法用于手機網絡游戲道具推薦，并利用半監督學習提升推薦性能。離線數據集以及實際在線手機網絡游戲實驗結果表明，基于多示例多標記學習的游戲道具推薦技術帶來了游戲營收的顯著增長。

關鍵詞：機器學習；多示例多標記學習（MIML）；半監督學習；推薦

1　引言

網絡游戲是隨著電子計算機和互聯網的發展與普及而進入人們日常生活中的一項廉價娛樂活動。網絡游戲玩家通過輸入輸出設備在計算機模擬出的虛擬世界中與虛擬世界環境及其他玩家進行互動來獲得休閑娛樂體驗。玩家在游戲中不但能夠通過被動接受滿足畫面、音樂、劇情等方面的感官需求，還能夠主動參與互動，在虛擬世界中獲得多種平時難以獲得的體驗。游戲總是以其獨特的表現形式豐富著人們的內心世界，故也被認為是第九項藝術[1]。游戲的藝術性豐富了玩家的內心世界，而游戲的商業性則為游戲開發者帶來收益。網絡游戲的收費模式主要有兩種：點卡收費和道具收費。點卡收費是傳統的收費方式，按照玩家登錄游戲的時長計費，時間越長費用越高。而道具收費是指玩家免費在游戲中進行基本娛樂活動，只有在需要增值服務道具時才進行付費。道具收費模式由于其“免費游戲，增值收費”的特點受到廣大玩家的歡迎，因此也被絕大多數網絡游戲所采用。隨著手機等移動計算設備的普及，手機網絡游戲也流行起來。由于移動互聯網隨時隨地的特性，人們接觸網絡游戲的門檻大大降低，使得手機網絡游戲玩家群體呈業余化趨勢。業余玩家們不再投入大量時間成為游戲專家，因此需要更好地引導他們去體驗網絡游戲世界。手機網絡游戲玩家群體的“業余化”特性是將推薦系統應用到游戲道具銷售上的主要原因。

推薦系統是對于搜索引擎的補充。在這個信息過載時代，當信息消費者們無法用準確的關鍵字來描述自己的需求時，推薦系統可以自動為他們提供想要的信息。推薦系統如今已經廣泛地應用在很多互聯網產品中，如購物網站淘寶、亞馬遜，社交網站Facebook，在線視頻網站Netflix、YouTube、Hulu等。應用在這些互聯網產品中的推薦系統大多采用了基于用戶行為數據的協同過濾推薦算法。算法利用user-item矩陣中隱含的用戶關聯、物品關聯以及用戶物品關聯這3類信息來進行推薦[2-3]。推薦系統的目標一般有兩種：一種是給出用戶對于物品的具體評分；另一種則只需對某個用戶給出一個包含n個物品的推薦列表，即Top-n推薦。對于第一種推薦目標，評價準則一般采用均方根誤差（root mean square error，RMSE），而對于Top-n推薦，評價準則主要采用準確率（precision）和召回率（recall）。這兩種目標顯然是不一致的，往往在Top-n推薦中采用一些簡單的算法就能獲得更好的效果，而無需采用要求給出具體評分的推薦算法[4]?；谖锲坊蛘呋谟脩舻膮f同過濾算法是簡單而有效的推薦算法[5-6]。而隱語義模型（latent factor model，LFM）類算法在利用user-item矩陣信息時，自然地假設存在“隱語義（latent factor）”，將user-item矩陣分解為user-latent矩陣和item-latent矩陣[7-8]。這樣一來，用戶和物品都可以與某個隱語義概念建立聯系，認知心理學中的“典型性”概念可以為該假設提供一些理論依據[9]。當矩陣數據并不稀疏時，LFM的效果是非常好的。當矩陣數據比較稀疏時，將相似度矩陣分解為多個低秩矩陣的積往往可以獲得很好的Top-n推薦效果[10-11]。

用戶行為數據一般以日志形式存在，由一系列事件組成，每條事件記錄一個用戶行為。在利用用戶行為數據進行物品推薦時，事件又可被分為顯性事件與隱性事件。顯性事件記錄了用戶的具體購買行為，直接反映用戶對物品的喜好；而所有非顯性事件都被歸為隱性事件。

手機網絡游戲中的玩家行為數據與一般互聯網產品的用戶行為數據相比，有以下3個特點：（1）玩家行為數據中包含大量事件上下文。普通互聯網產品的事件一般僅包括用戶ID、用戶行為ID和時間戳等內容。網絡游戲的事件不僅包含上述內容，還包括事件發生環境、前置事件、后續事件等事件上下文信息。（2）玩家行為數據中包含豐富的隱性事件。玩家在游戲虛擬世界中會留下大量與道具購買非直接相關的隱性事件記錄。（3）玩家行為數據中游戲道具數量有限。一款互聯網產品中物品數量成千上萬，而一款網絡游戲中的虛擬道具數量一般為幾十或幾百。

由于傳統的協同過濾算法主要利用user-item矩陣進行推薦，將其應用在手機網絡游戲道具推薦系統中會遇到以下兩個問題：（1）user-item矩陣中沒有事件上下文。一般為了能在推薦系統中利用事件上下文信息，只能通過人工添加相關的固定規則給推薦系統施加影響[5]。（2）user-item矩陣中不包含隱性事件信息。玩家只能通過顯性事件信息來描述，而大量隱性事件信息無法得到利用。

多示例多標記學習（multi-instance multi-label learning，MIML）[12]是近年來提出的一種新型機器學習框架。在該框架中，一個對象用多個示例描述，對象可以同時擁有多個類別標記，如圖1所示[13]。該框架對處理具有多義性的數據對象尤為適用，例如在圖像標注任務中，圖像的不同區域可以表示為不同的示例（即一個特征向量），一幅圖像可以同時劃歸多個類別；在文本分類任務中，不同的章節、段落可以表示為不同的示例，一個文檔可以同時屬于多個類別。MIML已被成功應用于圖像文本分類[13-14]、基因圖像標注[15]、視頻標注[16]、生態保護[17]等任務中。本文將游戲玩家日志數據中每個事件作為一個示例，玩家對于游戲道具的購買狀態作為標記，從而用多示例多標記學習框架來描述手機網絡游戲道具推薦問題。在此基礎上，本文通過快速多示例多標記學習算法進行道具推薦，并加入半監督學習以獲得更好的推薦性能。該算法不僅在離線數據集上進行實驗，還在實際手機網絡游戲中進行在線實驗。兩部分實驗結果都表明基于多示例多標記學習的游戲道具推薦技術給游戲營收帶來了顯著增長。

Fig.1 Multi-instance multi-label learning圖1　多示例多標記學習

本文組織結構如下：第2章介紹手機游戲道具推薦任務，并將其抽象為MIML問題；第3章提出co-MIMLfast算法；第4章給出基準數據上的實驗結果；第5章給出手機在線游戲實驗結果；第6章是結束語。

2　任務描述

圖2展示了游戲日志數據的產生過程。當ID為111的玩家在沙漠地圖坐標為（12，14）的地點進行了一次攻擊動作時，一條記錄該事件的數據便被存入游戲日志中。

Fig.2 Generation of game log data圖2　游戲日志數據的產生

顯然該事件是一個隱性事件。該隱性事件僅僅描述了玩家進行的一次攻擊動作，但它仍然可能隱藏了玩家對于某件游戲道具的偏好信息。例如，該游戲中有一件名為“諸葛神弩”的武器道具，只要購買了該道具，玩家就可以極大提高自己角色的戰斗力，從而輕松擊敗很多強大敵人。當某玩家在游戲中對某個敵人進行了一次攻擊動作，卻只對敵人造成少量傷害時，該玩家就很有可能對“諸葛神弩”這件武器道具產生興趣。從圖3中可以看到，當“攻擊”和“造成傷害”兩個隱性事件連續發生時，由于造成傷害的值僅為5，于是這位ID為111的玩家就有可能為了提升自己攻擊造成的傷害程度，想要購買“諸葛神弩”這件道具。當然，在實際玩家行為數據中包含了更多更復雜的隱性事件與游戲道具之間的關聯。

游戲提供商只能從游戲日志數據中直接觀察到某位玩家在某段時間內經歷的事件，以及他購買的游戲道具信息，卻難以觀察到事件與道具購買狀態之間的直接關聯信息（當然一些顯而易見的簡單關聯信息可以通過觀察獲得），即難以獲知是哪些事件導致了玩家對某道具的購買。事件與道具購買狀態之間的關聯信息顯然是構建道具推薦系統的基礎。將每個事件作為一個示例，每個道具的購買狀態作為一個類別標記，就可以用機器學習的方法來構建推薦系統。若用傳統的單示例機器學習算法進行推薦，必須給每一個示例（事件）指定一個標記（道具購買狀態）作為訓練樣本。這樣獲得的訓練樣本顯然具有極大噪音，因為該標記（道具購買狀態）很可能并非由該示例（事件）“觸發”。然而，這個情景用MIML來描述卻非常自然。用游戲日志數據中玩家經歷的事件信息來構建“多示例”，而游戲日志數據中玩家的道具購買情況來構建“多標記”，則多示例多標記模型描述了一位經歷了多個事件的玩家的所有道具購買狀態。這樣一來，盡管沒有事件與道具購買狀態之間的直接關聯信息，也可以利用事件信息來給玩家進行道具推薦。

Fig.3 Relationship between latent events and props圖3　隱性事件與道具的關聯

3　解決方案

在手機網絡游戲運營過程中，每位玩家每天都會產生大量日志數據。為了充分利用這些日志數據獲得更好的推薦性能，用于游戲道具推薦的MIML算法需要能夠進行快速處理。另一方面，手機網絡游戲玩家群體中存在大量免費玩家，他們的行為數據顯然沒有標記。將這些數據的標記都當作負標記處理，就默認了這些玩家對于所有游戲道具都不感興趣，很有可能給推薦模型的訓練帶來負面影響。而將這些數據的標記當作未標記處理，則有可能獲得更好的效果。因此用于游戲道具推薦的MIML算法需要能夠有效利用未標記樣本。

為了滿足快速計算和有效利用未標記樣本的需求，給出co-MIMLfast算法。

算法1 co-MIMLfast算法

輸入：標記數據L，未標記數據U，迭代輪數r。

訓練：

3. for i＝1:r

9. end for

測試：對于測試樣本Xtest，它的標記是（Xtest）與（Xtest）的交集

算法1是MIMLfast算法[18]與協同訓練（co-training）[19]的結合，兩個基模型分別由MIMLfast算法學習獲得，并在每一輪協同訓練過程中交換各自的預測樣本進行學習。MIMLfast算法滿足計算速度快的要求，能夠用于大規模數據，是目前最快速的MIML算法。而且MIMLfast的優化目標是最小化排序錯誤（ranking error），與Top-n推薦問題的目標非常貼近。協同訓練是一種基于異議的半監督學習算法[20-21]。與產生式模型、S3VM（semi-supervised support vector machine）、圖模型等幾類半監督學習算法相比，它是一種“元學習算法”，可以與任何基學習模型進行結合，只需外加一個交互標記樣本的過程即可進行半監督學習。本文已經確定使用MIMLfast算法進行MIML模型的訓練，因此利用協同訓練進行改造最為直接。

協同訓練一開始應用于多視圖的數據，后來被證明只要兩個基分類器不同（掌握不同知識），就可以以未標記樣本為載體來互相學習傳遞知識，并學習未標記的樣本[19，22]。算法1中利用Bootstrap方法訓練掌握不同知識的基分類器。另外，算子MIMLfast（?）指利用MIMLfast算法在訓練集上訓練MIML模型。下面簡單介紹MIMLfast算法的訓練過程。

MIMLfast算法為了在優化過程中利用不同標記之間的聯系，先通過一個矩陣W0將原來的特征向量x映射到另一個空間里。這個空間對于各個標記是共享的，因而這個樣本在標記l上的分類模型為：

由于W0和wl是通過交替優化進行的，不同標記之間的聯系信息就可以通過W0保存下來。為了應對MIML模型通常面臨復雜語義的情形，MIMLfast為每個標記l設計了子概念類。以標記“蘋果”為例，擁有這個標記的對象既有可能是一個水果，也有可能是一部手機，那么描述這兩種對象的特征向量可能就差別很大。子概念類的設計能夠讓示例與標記更好地擬合。令每個標記的子概念類數目為K，則有：

其中，wl，k對應了標記l的第k個子概念類的模型。在擁有了示例層面的模型后，需要建立以包為輸入的模型。MIMLfast中采用取最大值的方法定義包在標記l上的模型為：

有了對于包X在標記l上的模型，則定義這個模型的優化目標排序錯誤ε如下：

只要最小化ranking error，就能獲得一個好的多示例多標記推薦模型。對于這個非凸優化問題的求解，MIMLfast還采用了一些特別的優化技巧，詳情請參見文獻[18]。

4　基準測試

基準測試在常用的MIML數據集上進行，包括Letter Carroll[17]、Letter Frost[17]、MSRC V2[23]、Reuters[14]、Bird Song[17]和Scene[13]，它們的基本信息見表1。

Table 1　Popular MIML data sets表1　常用的MIML數據集

該實驗主要用于驗證co-MIMLfast算法的有效性。對于每個數據集，每次隨機選取其中9/10的數據作為訓練數據，其余1/10的數據作為測試數據，協同訓練的迭代輪數r＝5。最終的實驗結果是重復隨機選取30次后的平均結果。實驗中標記數據與未標記數據的比例為2∶1。實驗結果采用MIML中常用的5個評價準則，分別是Hamming Loss、One-Error、Coverage、Ranking Loss和Average Precision，其定義請參見文獻[24]。需要說明的是，為了實驗結果更加直觀，對表中的覆蓋率進行了歸一化處理。除了基本的MIMLfast算法，MIMLfast with self-training算法也被用來進行對比。Self-training作為一種最簡單的半監督學習算法，是一個很好的對比參照。

從表2中可以看出，co-MIMLfast的實驗結果在6個常用MIML數據集上相比MIMLfast的結果都有大幅提升（加粗數據表示，根據顯著水平為0.05的成對雙側t檢驗，相對于MIMLfast的性能提升具有顯著性），顯示出半監督學習的有效性。當然，兩個分類器的集成也給實驗效果的提升帶來了不少幫助。另外，One-Error和Ranking Loss是需要重點關注的評價指標。因為在Top-n推薦問題中，Ranking Loss直接反映了模型的好壞，而One-Error恰好是Top-1推薦的錯誤率。在這兩個評價指標上，co-MIMLfast顯著地提高了模型性能。

Table 2 Benchmark test results表2　基準測試結果

5　手機網絡游戲實驗

真實游戲數據實驗首先在3個手機網絡游戲的離線數據集上，對比co-MIMLfast算法與各種常用協同過濾算法的推薦效果。數據集的基本信息見表3。

Table 3 Online game data sets表3　網絡游戲數據集

與基準測試部分一樣，對于每個數據集，每次隨機選取其中9/10的標記數據作為訓練數據，其余1/10的標記數據作為測試數據，協同訓練的迭代輪數r＝5。標記數據占整個數據集的2/3，剩下的未標記數據只在co-MIMLfast算法中才會利用到。最終的實驗結果是重復隨機選取30次后的平均結果。這里使用的評價準則很簡單，就是與網絡游戲道具推薦系統產品收益直接相關聯的Top-n推薦準確率。推薦算法方面，常用的隨機推薦（Random）、最熱門推薦（Most-popular）、基于用戶的協同過濾（User-CF）、基于物品的協同過濾（Item-CF）和隱語義模型（LFM）都被用來與co-MIMLfast進行對比。其中，LFM是目前在非稀疏數據集上表現最好的推薦算法，而User-CF 與Item-CF也因為其簡單有效的特性被應用在很多互聯網產品中。關于這些算法的詳情，請參見文獻[2]。需要特別指出的是，無論是各種協同過濾算法還是co-MIMLfast算法，在實現時有非常多的具體細節可以修改或添加，這些固定規則的改動有可能大大影響算法在某些具體數據集上的表現。本文只考慮它們的基本算法。從表4中可以看出，co-MIMLfast算法在3個手機網絡游戲數據集合上都表現出了比較明顯的優勢。這得益于它利用了更多的數據來訓練模型：更多的事件上下文信息、更多的隱性事件信息以及更多的未標記信息。更多的事件上下文和隱性事件信息可以讓用戶相似度矩陣的構建更為精準，而未標記信息則使得對于用戶分布的估計更為準確。

Table 4 Precision of Top-n recommendation on game data sets表4　離線游戲數據集上Top-n推薦準確率

Table 5 Time cost of model training表5　模型訓練時間

表5給出了幾種算法的模型訓練時間對比。從表中可以看出快速多示例多標記學習算法在學習效率上的優勢。

最后，選取在離線數據實驗中表現較好的LFM 和co-MIMLfast兩種算法進行線上A/B測試。A/B測試是指將用戶隨機分為數量相等的兩組，分別使用兩種產品，通過比較兩種產品的轉化率來獲悉哪個產品更好。該測試在蘇州某公司開發運營的手機網絡游戲“xx三國”的道具推薦系統中進行，于2014年12月1日上線，測試周期為一個月。該游戲道具推薦系統是簡單的Top-1推薦。A/B測試中，根據玩家ID的奇偶性將玩家分為兩組。一組玩家通過LFM模型進行推薦，另一組則通過co-MIMLfast模型進行推薦。表6展示了10月至12月連續3個月該游戲的運營統計數據。其中，“付費確認框彈出”指玩家在游戲道具商店中選擇想要購買的道具后彈出的“請確認將從您的手機話費中支付xx元購買xx游戲道具”確認提示框，而“付費成功”指玩家在上述提示框中點擊了確定按鈕。可以看到，10月至11月游戲的用戶增長率與收入增長率分別是15.98%與16.02%，兩者基本一致。而11月至12月游戲的用戶增長率與收入增長率分別是16.70%與23.28%，收入增長率出現了較大的提升。因此，計算每用戶平均收入可知，道具推薦系統給這款游戲帶來了5.7%的營收增長。

Table 6 Statistics of the“xx Three Kingdoms”表6　“xx三國”運營數據統計

Table 7 Results of A/B test表7　A/B測試結果

表7給出了A/B測試的結果，其中轉化率等于付費成功次數除以付費確認框彈出次數。co-MIMLfast 在A/B測試中勝出，與線下離線實驗的實驗結果一致，表現出在網絡游戲道具推薦上的優勢。

6　結束語

手機網絡游戲中的玩家行為數據具有上下文信息豐富，隱性事件信息豐富等特點。本文的主要貢獻是將多示例多標記學習（MIML）框架用于描述手機網絡游戲道具推薦問題，并在實際游戲上線運營中測試了MIML在手機游戲道具推薦中的性能。本文設計的算法雖然并不復雜，但在離線測試和實際上線運營中都取得了很好的效果，顯示出MIML這一新型機器學習框架的巨大潛力。未來工作中將嘗試把MIML技術應用到更多手機網絡游戲的道具推薦中，并利用MIML的關鍵示例檢測機制[25]來發現觸發道具購買的具體事件，從而設計出更好的運營策略。

References:

[1] Liu Jin. Video game is the ninth art[EB/OL].（2012-08-27）[2015-03-13]. http://www.cflac.org.cn/ys/xwy/201208/t20120827_ 146180.html.

[2] Ricci F，Rokach L，Shapira B，et al. Recommender systems handbook[M]. New York: Springer-Verlag，2011.

[3] Breese J S，Heckerman D，Kadie C. Empirical analysis of predictive algorithms for collaborative filtering[C]//Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence，Madison，USA，1998. San Francisco，USA: Morgan Kaufmann Publishers Inc，1998: 43-52.

[4] Cremonesi P，Koren Y，Turrin R. Performance of recommender algorithms on top-n recommendation tasks[C]// Proceedings of the 4th ACM Conference on Recommender Systems，Barcelona，Spain，2010. New York，USA: ACM，2010: 39-46.

[5] Herlocker J L，Konstan J，Borchers A，et al. An algorithmic framework for performing collaborative filtering[C]//Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval，Berkeley，USA，1999. New York，USA:ACM，1999: 230-237.

[6] Sarwar B，Karypis G，Konstan J，et al. Item-based collaborative filtering recommendation algorithms[C]//Proceedings of the 10th International World Wide Web Conference，Hong Kong，China，2001. New York，USA:ACM，2001: 285-295.

[7] Chen C，Zheng L，Thomo A，et al. Comparing the staples in latent factor models for recommender systems[C]//Proceedings of the 29th Annual ACM Symposium on Applied Computing，Gyeongju，Korea，2014. New York，USA:ACM，2014: 91-96.

[8] Hofmann T. Latent semantic models for collaborative filtering[J]. ACM Transactions on Information Systems，2004，22（1）: 89-115.

[9] Cai Yi，Leung H，Li Qing，et al. Typicality-based collaborative filtering recommendation[J]. IEEE Transactions on Knowledge and Data Engineering，2014，26（3）: 766-779.

[10] Kabbur S，Ning X，Karypis G. FISM: factored item similarity models for top-n recommender systems[C]//Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，Chicago，USA，2013. New York，USA:ACM，2013: 659-667.

[11] Zheng Xiaodong，Ding Hao，Mamitsuka H，et al. Collaborative matrix factorization with multiple similarities for predicting drug-target interactions[C]//Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，Chicago，USA，2013. New York，USA:ACM，2013: 1025-1033.

[12] Zhou Zhihua，Zhang Minling，Huang Shengjun，et al. Multiinstance multi-label learning[J]. Artificial Intelligence，2012，176（1）: 2291-2320.

[13] Zhou Zhihua，Zhang Minling. Multi-instance multi-label learning with application to scene classification[C]//Advances in Neural Information Processing Systems 19: Proceedings of the 20th Annual Conference on Neural Information Processing Systems，Vancouver，Canada，Dec 4-7，2006. Cambridge，USA: MIT Press，2006: 1609-1616.

[14] Sebastiani F. Machine learning in automated text categorization[J].ACM Computing Surveys，2002，34（1）: 1-47.

[15] Li Yingxin，Ji Shuiwang，Kumar S，et al. Drosophila gene expression pattern annotation through multi-instance multilabel learning[J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics，2011，9（1）: 98-112.

[16] Xu Xinshun，Jiang Yuan，Xue Xiangyang，et al. Semi-supervised multi-instance multi-label learning for video annotation task[C]// Proceedings of the 20th ACM International Conference on Multimedia，Nara，Japan，2012. New York，USA:ACM，2012: 737-740.

[17] Briggs F，Fern X，Raich R. Rank-loss support instance machines for MIML instance annotation[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，Beijing，China，2012. New York，USA:ACM，2012: 534-542.

[18] Huang Shengjun，Zhou Zhihua. Fast multi-instance multi-label learning[C]//Proceedings of the 28th AAAI Conference on Artificial Intelligence，Quebec City，Canada，2014. Menlo Park，USA:AAAI，2014: 1868-1874.

[19] Wang Wei，Zhou Zhihua. Analyzing co-training style algorithms[C]//LNCS 4701: Proceedings of the 18th European Conference on Machine Learning，Warsaw，Poland，Sep 17-21，2007. Berlin，Heidelberg: Springer，2007: 454-465.

[20] Zhu Xiaojin. Semi-supervised learning literature survey，TR 1530[R]. Computer Sciences，University of Wisconsin-Madison，2006.

[21] Pise N N，Kulkarni P. A survey of semi-supervised learning methods[C]//Proceedings of the 4th International Conference on Computational Intelligence and Security，Suzhou，China，Dec 13-17，2008. Piscataway，USA: IEEE，2008: 30-34.

[22] Zhou Zhihua，Li Ming. Semi-supervised learning by disagreement[J]. Knowledge and Information Systems，2010，24（3）: 415-439.

[23] Winn J，Criminisi A，Minka T. Object categorization by learned universal visual dictionary[C]//Proceedings of the 10th IEEE International Conference on Computer Vision，Beijing，China，2005.Piscataway，USA:IEEE，2005:1800-1807.

[24] Schapire R E，Singer Y. BoosTexter: a boosting-based system for text categorization[J]. Machine Learning，2000，39（2/3）: 135-168.

[25] Li Yufeng，Hu Juhua，Jiang Yuan，et al. Towards discovering what patterns trigger what labels[C]//Proceedings of the 26th AAAI Conference on Artificial Intelligence，Toronto，Canada，2012. Menlo Park，USA:AAAI，2012: 1012-1018.

附中文參考文獻：

[1]劉瑾.電子游戲的第九藝術之說[EB/OL].（2012-08-27）[2015-03-13]. http://www.cflac.org.cn/ys/xwy/201208/t20120827_ 146180.html.

TANG Jun was born in 1990. He is an M.S. candidate at Nanjing University. His research interests include machine learning，data mining and phone game，etc.

唐?。?990—），男，南京大學碩士研究生，主要研究領域為機器學習，數據挖掘，手機游戲等。

ZHOU Zhihua was born in 1973. He is a professor and Ph.D. supervisor at Nanjing University，ACM distinguished scientist，IEEE fellow and CCF fellow. His research interests include artificial intelligence，machine learning and data mining，etc.

周志華（1973—），男，南京大學教授、博士生導師，ACM杰出科學家，IEEE會士，CCF會士，主要研究領域為人工智能，機器學習，數據挖掘等。

Mobile Phone Game Props Recommendation Based on Multi-Instance Multi-Label Learning*

TANG Jun1，2，ZHOU Zhihua1，2＋

1. National Key Laboratory for Novel Software Technology，Nanjing University，Nanjing 210023，China

2. Collaborative Innovation Center of Novel Software Technology and Industrialization，Nanjing 210023，China

Abstract:Mobile phone game providers gain profits by selling virtual props in games. This paper describes an event in game log data of players as an instance and represents the states of players’prop purchases by labels，so that the game props recommendation is modeled as multi-instance multi-label learning（MIML）problem. On the basis of this abstraction，an MIMLfast algorithm is used to recommend mobile phone game props and a semi-supervised learning part is integrated to improve the performance of recommendation. The results of experiments conducted on offline data sets and a real mobile phone game show that the MIML-based game props recommendation brings a remarkable increase of game profits.

Key words:machine learning; multi-instance multi-label learning（MIML）; semi-supervised learning; recommendation

文獻標志碼：A

中圖分類號：TP301

Corresponding author:＋ E-mail: zhouzh@lamda.nju.edu.cn
TANG Jun，ZHOU Zhihua. Mobile phone game props recommendation based on multi-instance multi-label learning. Journal of Frontiers of Computer Science and Technology，2016，10（1）：103-111.

doi:10.3778/j.issn.1673-9418.1505055