基于鄰居選取策略的人群定向算法

周 孟 朱福喜,2

1(武漢大學計算機學院 武漢 430072)2 (漢口學院計算機科學與技術學院 武漢 430212)

?

基于鄰居選取策略的人群定向算法

周 孟1朱福喜1,2

1(武漢大學計算機學院 武漢 430072)2(漢口學院計算機科學與技術學院 武漢 430212)

(angel19851229@163.com)

人群定向是廣告推薦系統中的一種重要技術，它是通過分析種子人群的行為數據，找出潛在的目標人群，而現有人群定向算法大多依賴于傳統的協同過濾推薦算法.由于傳統的協同過濾算法具有推薦精度低和抗攻擊能力較弱的問題，為了解決這些問題，提出了一種基于鄰居選取策略的人群定向算法.1)通過用戶行為相似，動態選擇出與種子人群具有相似行為的用戶；2)以用戶特征和用戶行為作為鄰居選取的依據，通過用戶相似度從行為相似人群中選擇出每個種子用戶的鄰居，并將所有的相似鄰居作為候選人群；3)通過基于鄰居選取策略的人群定向算法，從候選人群中擇出潛在的目標用戶，以完成人群定向.實驗結果表明:與現有方法相比，該方法不僅提高了人群定向的精度，而且也增強了系統的抗攻擊能力.

種子人群；行為相似人群；鄰居選取策略；用戶相似度；人群定向

目前隨著互聯網的發展，互聯網廣告的數據資源以驚人的速度增長，為了解決廣告主向目標用戶投放廣告的需求，人群定向技術應運而生.人群定向主要通過現有用戶的行為，找出未來潛在的目標人群，并選擇適當的廣告投放給這些目標人群.

人群定向的精度依賴于信息過濾的技術，而在現有的技術中，推薦系統已經成為解決互聯網信息過濾的主要有效工具，并且應用十分廣泛[1].在現有推薦技術中，基于協同過濾的推薦方法是主要常用的技術，其主要是通過協同過濾算法，找出行為相似的用戶，并對目標用戶進行商品推薦.但是，以往的協同過濾推薦算法，僅僅使用了用戶對商品的評分來選取相似度比較高的用戶作為推薦的對象,從而導致了系統的推薦精度很低.這是因為用戶對商品的評分數據比較稀疏，并且在推薦系統中沒有深入考慮到用戶的詳細信息，如性別、年齡、職業等.為了提高推薦算法的性能和用戶滿意度，很多學者提出了不同的推薦方法.如黃震華等人[2]將排序學習融入推薦系統中，并通過整合大量的用戶和物品的特征，構建用戶偏好需求模型，來提高推薦算法的性能和用戶滿意度；郭磊等人[3]提出了一種結合推薦對象間關聯關系進行推薦的算法，該算法不僅考慮了用戶間的社會關系，而且還考慮了推薦對象間的關聯關系；榮輝桂等人[4]提出了基于用戶相似度協同過濾推薦方法，該方法是通過用戶之間的不同社交關系來計算用戶間的相似度.雖然上述方法都提高了推薦系統的性能，但是這些推薦系統都沒有考慮到大量的用戶概貌攻擊問題.

1 相關工作

對于推薦系統的研究工作，國內外學者提出了許多的推薦算法.目前，傳統的主流推薦算法是基于內容過濾的推薦算法[5-6]和基于協同過濾的推薦算法[7-9].基于內容過濾的推薦算法主要不需要專門的領域知識，而且推薦的結果直觀、容易理解，但是該算法無法靈活結合用戶興趣等其他多方面的有用信息;基于協同過濾的推薦算法主要分為基于用戶的協同過濾算法和基于項目的協同過濾算法.基于用戶的協同過濾算法充分利用了相似用戶的信息，并為目標用戶產生推薦集合，但是在該算法中，涉及到用戶的信息量相當有限，并且數據相對稀疏，即用戶對項目的評分相對較少，于是造成了嚴重的數據冷啟動問題.在這種情況下，推薦的精確度將會受到嚴重影響，大大降低了推薦系統的性能;基于項目的協同過濾推薦算法則是鑒于用戶已評分的項目，預測相似項目的評分.雖然該方法減少了數據稀疏性和冷啟動問題對推薦系統的影響，但是用戶的興趣愛好是隨著時間變化的，該方法的推薦覆蓋率較低，并且用戶對推薦的滿意度也較低.

為解決數據稀疏和冷啟動問題，Chen等人[10]提出了2階段聚類的推薦算法，并將圖摘要方法和基于內容相似度的算法結合，實現了基于用戶興趣的推薦，減少了數據稀疏和冷啟動問題對推薦系統的影響.Wang等人[11]首先對用戶進行分類，并對不同的行為分配不同的權重;然后計算用戶間的相似度，并根據用戶間的相似行為，產生相應的用戶推薦集合.雖然該方法取得了一定的效果，但該方法需要用戶的大量行為數據，如果在用戶行為較少的情況下，不能產生良好的推薦效果.Koren[12]提出了基于矩陣分解的推薦算法，該算法解決了數據稀疏的問題，提高了系統推薦的質量;但該方法沒有考慮到用戶攻擊概貌對推薦性能的影響.

為解決攻擊概貌的問題，Mobasher等人[13]提出了基于PLSA模型的推薦算法，通過PLSA模型對用戶進行聚類，從而實現對用戶的推薦,與其他方法相比，該方法對攻擊概貌具有較強的抗攻擊能力，而且推薦的精確度較高；Mehta等人[14]提出了基于奇異值分解的推薦算法，該方法通過減弱攻擊概貌對推薦的影響來提高系統的抗攻擊能力，但該方法對小規模的概貌攻擊具有較好的效果，對于大規模的攻擊仍是顯得力不從心；Sandvig等人[15]提出了基于關聯規則的協同過濾算法，雖然該算法具有較強的穩定性，但是降低了推薦的精準度，并且系統推薦的覆蓋面也較小.

此外，還有學者在推薦系統中引入了用戶間的信任關系，以解決攻擊概貌問題.Jamali等人[16]提出了隨機游走模型，通過多次隨機游走算法，融合返回的多個評分，得到目標項目的預測評分，但是該模型容易受到數據稀疏的影響；Ma等人[17]提出了基于矩陣分解進行推薦的方法，通過對用戶或項目特征的學習，得到目標用戶的推薦,并且，他們還提出了融合社會信息的推薦方法[18]；Jia等人[19]提出了一種基于雙重鄰居選取策略的協同過濾算法，通過用戶的評分信息，計算目標用戶與興趣相似用戶的信任度，并以此為選取鄰居用戶的依據，利用雙重鄰居選取策略，已完成對目標用戶的推薦.雖然該方法具有較強的抗攻擊能力，但在用戶評分信息的稀疏性較大.

針對上述方法中存在的問題，在現有推薦技術的人群定向算法上，本文提出了一種基于鄰居選取策略的人群定向算法.首先通過用戶行為和用戶特征，動態選擇出與種子人群具有較高相似行為的候選人群;然后通過基于鄰居選取策略的人群定向算法，從候選人群中選擇出潛在的目標人群，以完成人群定向.本文的主要工作體現在3個方面：

1) 提出了一種興趣指紋生成算法，根據每個用戶的興趣愛好，生成該用戶的興趣指紋.

2) 提出了一種基于用戶行為和用戶特征的候選人群選擇算法，該算法首先以用戶行為為依據，動態選擇出種子人群的行為相似人群;然后以用戶行為和用戶特征為依據，從行為相似人群中選擇出每個種子用戶的鄰居，并將選擇出的所有鄰居作為候選人群.

3) 提出了一種基于鄰居選取策略的人群定向算法，通過該算法從候選人群中選擇出潛在的目標用戶，以完成人群定向.

2 用戶相似度

互聯網用戶可以通過用戶行為和用戶特征2個方面來描述.用戶行為是指用戶訪問的一系列的媒體(或網站)信息，可以通過該用戶訪問的網頁直接獲取;用戶特征是指描述用戶個人身份的屬性或信息，主要包括用戶的人口屬性和興趣愛好.其中，人口屬性包括性別、年齡、婚姻狀況、個人收入、學歷、職業和行業7個子屬性；興趣愛好可分為娛樂、財經金融、運動、數碼產品、旅游、汽車、文藝、時政、健康保健和軍事10個興趣愛好.為了選取種子用戶的鄰居，本文采用了用戶相似度的方法.因此，本節著重對用戶特征獲取和相似度2方面進行詳細介紹.

2.1 用戶特征

與用戶行為不同，用戶特征并不能直接獲取.然而可以通過用戶的訪問行為進行預測.由于用戶特征包含人口屬性和興趣愛好2個子特征，于是，本文采用了不同的方法來進行預測用戶的人口屬性和興趣愛好.

2.1.1 人口屬性預測

人口屬性是用戶內在屬性的描述.在系統中，能夠直接獲取用戶訪問了哪些網站等信息，但獲得用戶的人口屬性往往比較困難.于是，可以通過用戶訪問的網站去自動預測人口屬性.比如以性別為例：經常瀏覽汽車網、游戲網的用戶絕大部分是男性，經常訪問娛樂綜藝的用戶絕大多數用戶是女性.此時，性別屬性預測問題可以轉化為分類問題.本文以性別為例，詳細描述人口屬性預測的方法.

假設某個用戶訪問了n個不同的媒體，分別為M1，M2，…，Mn，C1表示為男性用戶，C2表示為女性用戶，C1(Mi)表示訪問了媒體Mi的男性用戶計數，C2(Mi)表示訪問了媒體Mi的女性用戶計數，則該用戶的性別分類概率為

(1)

同理，該方法也可擴展應用于獲得人口屬性的其他子屬性.

2.1.2 興趣愛好分類

與人口屬性類似，用戶的興趣愛好并不能直接獲取.但是，可以獲取到用戶瀏覽的所有頁面，而用戶經常瀏覽的頁面通常隱含了用戶的興趣，因此，通過對訪問的頁面進行分類，得到每個用戶的興趣偏好.

網頁的分類流程如圖1所示，主要包括訓練和分類2個階段：首先通過樣本訓練貝葉斯分類器，然后使用訓練的貝葉斯分類器對訪問的頁面進行興趣分類.

1) 訓練階段:①對樣本數據進行分詞、過濾無用詞等預處理操作，形成分詞后的訓練樣本；②通過訓練樣本訓練貝葉斯分類器.

2) 分類階段:①需要對抓取頁面的內容進行預處理操作；②通過貝葉斯分類器對該網頁進行興趣分類，并將網頁的興趣類別作為訪問了該網頁用戶的興趣愛好.

Fig. 1 Page classification圖1 網頁的分類流程

2.2 相似度

2.2.1 人口屬性的相似度

人口屬性主要包括7個子屬性，可以分為2類：1)數值型屬性，主要包括年齡和個人收入；2)名稱型的屬性，主要包括性別、婚姻狀況、學歷、職業和行業.由于屬性的類型不同，其屬性之間的距離計算也不同.對于數值型屬性的相似度計算如下：首先計算2個用戶在該屬性上的數值絕對差，并將該屬性的絕對差值的最小和最大劃分為區間[vmin,vmax]，然后將這個區間劃分為x個等距的子區間，即[vmin,v1]，[v1,v2]，…，[vx-1,vmax]，并且每個子區間依次給定數值型屬性的距離為1，2，…，x.此時，如果數值型屬性的絕對差值落在第i子區間內，那么在該屬性上的距離d=i(i≤x).

例1. 假設年齡的最小值和最大值區間為[vmin,vmax]，并將該區間劃分為3個子區間，即[vmin,v1]，[v1,v2]，[v2,vmax]，則用戶uA和uB在年齡上的差值為|l|=|uA-vB|，其中vA為用戶uA的年齡，vB為用戶uB的年齡，并且|l|∈[v1,v2]，則用戶uA和uB在年齡上的距離為2.

針對所有的數值屬性a1，a2，…，an，假設用戶uA和uB在所有數值屬性上的距離為

(2)

其中,dj表示2個用戶在屬性aj上的距離，若所有的dj都為0，則Dnumber的默認值為1.

對于名稱型屬性的距離計算，本文采用了方法：假設名稱型屬性的取值數目為N，則對所有取值按順序進行人工評級，即所有的評級為r1，r2，…，rN，若2個用戶在該屬性上的評級分別為ri和rj，則2個用戶在該屬性上的距離為|ri-rj|.

例2. 以學歷為例，學歷分為本科以下、本科、碩士和博士，其對應的人工評級為1，2，3，4，若2個用戶uA和uB的學歷分別為本科和博士，則2個用戶在“學歷”屬性上的距離為2.

針對所有的名稱型屬性b1，b2，…，bn，假設用戶uA和uB在所有名稱型屬性上的距離為

(3)

如果2個用戶的距離越小，則他們之間的相似度就越大.于是本文中采用了距離的調和均值的倒數作為2個用戶的人口屬性相似度，即:

(4)

2.2.2 興趣相似度

由于每個用戶是個獨立的個體，并且不同用戶的興趣愛好或許不同.因此，每個用戶都會擁有屬于自己的興趣指紋，如果2個用戶的興趣指紋越相似，那么這2個用戶的興趣相似度就越大.本文提出了一種興趣指紋算法來生成用戶的興趣指紋.

興趣指紋算法的主要思想是將每個用戶的多個興趣映射到1個K位的指紋中，該算法主要經過4個階段：

1) 對所有的興趣進行Hash，得到n個K位的Hash值.

2) 抽取用戶的所有興趣愛好，以及每個興趣的概率權重.

3) 計算用戶的第i(1≤i≤K)位的興趣數字指紋.首先設置該位的初始累加數為0，依次循環每個散列的第i位，如果該位為1，則累加數加上該興趣的權重；如果該位為0，則累加數減去該興趣的權重.最后，如果累加數為正，則第i的興趣數字指紋為1，否則為0.

4) 對K個數字指紋進行連接，生成用戶的興趣指紋.該算法的具體實現如下.

算法1. 興趣指紋生成算法.

輸入：用戶的興趣概率矩陣P=(pij)、P是m×n矩陣、用戶ux的興趣概率向量Px=(px1,px2,…,pxn)、n個興趣；

輸出: 用戶的興趣指紋F.

①H←?，F′←?；

② fori←1 tondo*本文中K的取值為所有興趣標簽的計數*

③ 對于興趣i，生成1個K位Hashhi；

④H←H∪hi；

⑤ end for

⑥ fori←1 toKdo

⑦sum←0；

⑧ forj←1 tondo

⑨q←hj的第i位；

⑩ ifq=1 do

興趣指紋反映了用戶的興趣愛好，因此，2個用戶之間的興趣相似度可以通過他們的興趣指紋來計算.假設用戶uA和uB的興趣指紋分別為FA=fA1fA2…fAK和FB=fB1fB2…fBK，則2個用戶的興趣相似度計算為

(5)

如果2個用戶興趣指紋相同，那么興趣相似度為1；如果興趣指紋完全不同，興趣相似度為0.

2.2.3 用戶特征相似度

用戶特征是用戶的內在屬性，并且用戶特征包含了人口屬性和興趣2個方面，因此用戶特征相似度包含人口屬性的相似度和興趣的相似度2部分.由于人口屬性和用戶興趣是從不同方面來描述用戶特征，屬于不同的維度空間，用戶之間的人口屬性相似度和興趣相似度不同，都會影響用戶特征的相似度.

例3. 假設有3個用戶uA,uB,uC，uA與uB的人口屬性相似度和興趣相似度分別為0.8和0.2，而uA與uC的人口屬性相似度和興趣相似度分別為0.6和0.4.若采用算術平均值的方法計算用戶特征相似度，則uA與uB的用戶特征相似度為0.5，uA與uC的用戶特征相似度為0.5，此時，uB和uC都與uA具有相同的用戶特征相似度；若采用調和均值的方法計算用戶特征相似度，則uA與uB的用戶特征相似度為0.32，uA與uC的用戶特征相似度為0.48，此時，uA與uC的用戶特征相似度高于uA與uB.

對于上述實例，若從人口屬性和用戶興趣2個角度去考慮，uA與uC的用戶特征相似度應高于uA與uB.基于此，本文沒有采用算術平均的方法來計算用戶特征相似度，而是采用了調和平均的方法來計算2個用戶的特征相似度，即:

(6)

其中，simP(uA,uB)是2個用戶的人口屬性相似度，simI(uA,uB)是2個用戶的興趣相似度.

2.2.4 用戶行為相似度

用戶行為相似度是從用戶訪問的媒體角度來衡量2個用戶之間的相似度，該相似度是從動態角度考慮2個用戶的相似程度，這是由于用戶行為是隨著時間不斷發生變化的，并且用戶訪問的媒體反映了用戶的行為軌跡，因此，在人群定向分析算法中，用戶訪問行為也是必須考慮的因素.于是，本文通過用戶訪問的不同媒體來計算2個用戶之間的行為相似度.

假設有m個用戶組成的集合U={u1,u2,…,um}和n個媒體組成的集合M={M1,M2,…,Mn}，則用戶-媒體訪問矩陣可以用m×n矩陣C來表示，Cij(1≤i≤m,1≤j≤n)表示用戶ui訪問媒體Mj的計數，并且用戶uA和用戶uB的共同訪問的媒體集合為T，則2個用戶的行為相似度為

(7)

2.2.5 用戶相似度

每個用戶不僅具有內在的用戶特征，而且還包含動態的用戶行為.于是在本文中，用戶相似度是從用戶特征和用戶行為2個角度來衡量用戶間的相似程度，由于用戶特征和用戶行為是用戶的2個不同的維度，并且算術平均數方法容易受到極端數值的影響，計算出的平均數的代表性較差(參見例3)，于是，采用了調和平均方法來計算用戶uA和用戶uB的相似度，即:

(8)

其中,simF(uA,uB)是2個用戶的特征相似度，simB(uA,uB)是2個用戶的行為相似度.

3 基于鄰居選取策略的人群定向算法

人群定向是通過種子人群的行為特征，找出潛在的目標人群.由于推薦系統的開放性，導致基于推薦算法的人群定向的抗攻擊能力差.為此，本文提出了一種基于鄰居選取策略的人群定向算法，該算法首先根據用戶行為找出種子人群的行為相似人群;然后以用戶行為和用戶特征為依據，找出每個種子用戶的鄰居，并將所有鄰居作為種子人群的候選人群;最后通過基于鄰居選取策略的人群定向算法，從候選人群中選擇出相似度較高的用戶作為潛在的目標人群.在人群定向算法中，為了選擇出種子人群的行為相似人群和候選人群，本文提出了一種基于用戶行為和用戶特征的候選人群選取算法.

3.1 基于用戶行為和用戶特征的候選人群選取算法

由于人群定向是找出與種子人群具有相同行為的目標人群，因此，該目標人群應是與種子人群具有較高行為相似度的用戶集合.然而僅僅通過用戶行為相似尋找候選人群，具有一定的片面性，這是因為人群定向系統容易受到用戶概貌攻擊的影響，當系統遇到大規模的用戶攻擊時，人群定向的精度明顯降低.本文提出了一種基于用戶行為和用戶特征的候選人群選取算法.該算法通過用戶行為，尋找出較高的行為相似人群,根據用戶特征和用戶行為為選擇鄰居的依據，從行為相似人群中，找出每個種子用戶的鄰居集合，并將所有的種子用戶的鄰居集合作為人群定向的候選人群.這樣從局部角度增強系統的抗攻擊能力，有助于提高人群定向的質量.

候選人群選取算法的目標主要是以用戶行為和用戶特征為依據，找出相似度較高的種子用戶的鄰居.該算法主要包括3個階段：1)選取種子人群的中心用戶.在該階段，為了減少每個用戶與種子人群的比較次數，本文從種子人群中選擇出中心用戶，并計算中心用戶的媒體向量.2)尋找種子人群的行為相似人群.計算每個用戶與中心用戶的行為相似度，并計算所有行為相似度的平均值作為行為相似度的閾值，選出行為相似度不低于閾值的那些用戶作為種子人群的行為相似人群.3)選取出種子人群的候選人群.計算行為相似人群中每個用戶與種子用戶的相似度，并根據相似度的大小，選擇出每個種子用戶的前k個鄰居，并將選擇出的所有鄰居集合作為種子人群的候選人群.

算法2. 基于用戶行為和用戶特征的候選人群選取算法.

輸出: 候選人群Pcand.

①Sbeh←?,uc←u,Mc←0,Pcand←?；*u為中心用戶，Mc為中心用戶u的訪問的媒體向量*

② fori←1 tondo

③num←0,sum←0；

④ forj←1 tordo

⑤ ifCji≠0 do

⑥sum←sum+Cji；

⑦num←num+1；

⑧ end if

⑩Mc(i)←sumnum；

3.2 基于鄰居選取策略的人群定向算法

由于候選人群Pcand中的用戶是針對每個種子用戶而選擇出的鄰居集合，但并不是每個用戶都與所有的種子用戶具有較高的相似性，因此，本文從種子人群的整體角度出發，提出了基于鄰居選取策略的人群定向算法(audience targeting based on neighbor choosing strategy, ATNCS)，該算法以用戶特征和用戶行為為選取依據，計算候選人群Pcand中的每個用戶與種子人群的相似度，動態選擇相似度較高的用戶作為潛在的目標人群.

人群定向算法的思想主要是從候選人群中選擇出潛在的目標人群，該算法主要包括3個階段：1)計算候選人群中的每個用戶與種子用戶的相似度，根據該用戶與所有種子用戶的相似度，計算相似度的平均值，并將其作為該用戶與種子人群的相似度;2)根據所有用戶與種子人群的相似度，計算種子人群的相似度閾值;3)從候選人群中選擇出用戶與種子人群相似度不低于閾值的用戶集合，并將這些用戶作為潛在的目標人群.

算法3. 基于鄰居選取策略的人群定向算法.

輸入: 種子用戶集合S、候選人群Pcand、種子用戶-媒體訪問矩陣、種子用戶-興趣概率矩陣、候選人群-媒體訪問矩陣、候選人群-興趣概率矩陣、種子用戶及候選人群的人口屬性；

輸出: 目標人群集合At.

①At←?,sum←0,Q←?；

② for eachui∈Pcanddo

③simi←0,sumSimi←0；

④ for eachuj∈Sdo

⑤ 計算sim(ui,uj)；

⑥sumSimi←sumSimi+sim(ui,uj)；

⑦ end for

⑧simi←sumSimi|S|；*simi為用戶ui與種子人群的相似度*

⑨sum←sum+simi；

⑩Q←Q∪{〈simi,ui〉}；

4 實驗驗證與分析

4.1 數據集

為了驗證算法的有效性，本文使用了1家互聯網廣告公司的在線廣告用戶作為實驗數據，該實驗數據包括4組數據:組1(G1)包含1 882 146個用戶、2 912個媒體和14 415 499個網頁；組2(G2)包含1 854 321個用戶、2 736個媒體和13 959 907個網頁；組3(G3)包含2 561 384個用戶、2 987個媒體和18 746 897個網頁；組4(G4)包含2 118 465個用戶、2 896個媒體和16 081 431個網頁.此外，除上述數據集之外，還包含人口屬性的分類樣本數據集和頁面興趣分類的樣本數據集.

在實驗時，我們隨機選擇10%的用戶作為種子人群，剩下90%的用戶作為測試數據.

4.2 對比算法

為了驗證人群定向算法的性能，本文選擇作為對比算法的2種算法：

1) 基于用戶協同過濾的人群定向(audience targeting based on user collaborative filtering, ATUCF)算法.該算法主要通過用戶訪問的媒體，找出相似用戶集合進行人群定向.

2) 不確定近鄰的協同過濾的人群定向(audience targeting based on uncertain neighbors’ collaborative filtering, ATUNCF)算法[20].基于用戶訪問的媒體，計算用戶之間的相似性，并自適應地選擇每個種子的近鄰對象作為潛在的目標人群.

4.3 人群定向的效果對比

為了驗證新方法在人群定向中的效果，本文在4.1節中4組數據集上，對ATNCS，ATUCF，ATUNCF進行了對比實驗.此外，還進行了僅采用用戶行為的人群定向算法(ATNCS-B)和僅采用用戶特征的人群定向算法(ATNCS-F)的實驗，具體實驗結果如表1所示.

從表1中可以看出，在ATUCF，ATUNCF，ATNCS方法中，ATUNCF方法在準確率Precision上比ATUCF方法平均提高了3%～5%，而ATNCS方法比ATUNCF方法平均提高了1%～3%；在召回率Recall上，ATUNCF方法比ATUCF方法平均提高了將近3%，而ATNCS方法比ATUNCF方法平均提高了1%～2%.顯然，ATUCF方法的推薦精度最低，其次是ATUNCF方法，ATNCS的推薦性能是最優的.這是因為在人群定向時，ATUCF方法僅僅考慮了用戶的訪問媒體信息，并且沒有考慮用戶特征信息，即在人群定向時，僅僅通過用戶之間是否存在共同的訪問媒體，如果共同訪問媒體的越多，2個用戶就越相似.而ATUNCF方法則不同，該方法在尋找種子用戶的鄰域時，不僅考慮用戶之間的相似性，而且還考慮了媒體之間的相似性，因此ATUNCF的方法的性能優于ATUCF方法.ATNCS方法與ATUNCF方法類似，也是通過尋找種子用戶鄰域來進行人群定向，但是在尋找用戶的鄰域時，ATUNCF方法只考慮了用戶訪問的媒體信息，并沒有考慮用戶特征信息，而ATNCS方法在鄰居選取策略中考慮了用戶行為和用戶特征為信息.即在尋找種子用戶的鄰居時，首先通過用戶之間的行為相似度動態選擇出種子人群的行為相似人群；然后通過用戶相似度選擇出種子人群的候選人群；最后通過用戶相似度的方法從候選人群中動態選擇出潛在的目標人群.并且在選擇候選人群和目標人群時，均使用了用戶相似度方法，該相似度方法不僅考慮行為相似度，而且還考慮了用戶特征相似度.因此ATNCS方法的性能優于ATUNCF方法.

Table 1 Comparison of Different Methods表1 不同方法的性能比較

此外，在ATNCS-B，ATNCS-F，ATNCS方法中，在準確率Precision上，ATNCS方法比ATNCS-B方法平均提高了5%～6%，比ATNCS-F方法平均提高了3%～5%；在召回率Recall上，ATNCS方法比ATNCS-B方法平均提高了3%～4%，比ATNCS-F方法平均提高了2%～3%.顯然，ATNCS方法人群定向的性能是最優的.這是因為ATNCS-B只考慮用戶行為信息，忽視了用戶的特征信息，即在選擇種子用戶的鄰居時只考慮了用戶行為相似度，并沒有考慮用戶特征相似度；ATNCS-F方法則與之相反，只考慮了用戶特征信息，并沒考慮用戶的行為信息，即在計算用戶的相似度時，只使用了用戶特征相似度，并沒有考慮用戶的行為相似度；而新方法在選擇種子用戶的鄰居時，用戶相似度方法中不僅使用了用戶的行為相似度，而且還考慮了用戶特征相似度.因此，這2種方法的人群定向效果低于新方法.從另一方面，也說明了用戶特征和用戶行為鄰居選取策略中具有重要的作用，不能被忽視.

4.4 抗攻擊能力比較

為了評價ATNCS方法的抗攻擊能力，在原有的4組數據集中，分別注入了不同規模的用戶概貌攻擊數據.實驗中注入的用戶攻擊規模有：2%，5%，7%，10%.并且還進行了ATUTC方法和ATUNCF方法進的實驗，3種不同方法在4組數據集中的平均結果分別如圖2所示：

Fig. 2 Comparison of anti-attack capability圖2 抗攻擊能力的比較

從圖2中可以看出，無論是在準確率Precision上，還是召回率Recall和F-measure上，隨著用戶攻擊規模的增大，人群定向的效果逐漸降低.從而可知，攻擊的用戶越多，人群定向的性能受到的影響就越大.除此之外，從圖2中還可以看出，ATUCF下降幅度較大，說明ATUCF方法受到的影響較明顯，這是由于ATUCF方法在人群定向中只考慮較少的用戶行為信息，并沒有考慮用戶特征信息，從而導致該方法具有較弱的抗攻擊能力.而ATUNCF方法和ATNCS方法下降幅度較小，ATUNCF方法和ATNCS方法受到的影響較小.這是因為ATUNCF方法不僅通過訪問的媒體來計算用戶之間的相似度，而且能夠通過相似度的動態閾值來自適應地選擇用戶的近鄰.而ATNCS方法具有較高的抗攻擊能力，主要有2個原因：1)在選擇種子用戶的鄰居時，使用了用戶相似度方法，該方法不僅考慮了用戶特征相似度，而且還考慮了行為相似度.2)ATNCS方法經歷了3個階段，即選取種子人群的行為相似人群、選取種子人群的候選人群和選取潛在目標人群，在每個階段中都會過濾一些用戶集合，進而會過濾掉一些攻擊用戶，這樣從局部角度增強了用戶的抗攻擊能力.因此，隨著攻擊規模的增大，ATNCS方法的效果仍優于ATUNCF方法.與其他2種方法相比，ATNCS方法具有較強的抗攻擊能力.

4.5 調和均值方法的影響

在人群定向算法中，計算用戶特征相似度和用戶相似度時都采用了調和均值的方法.而不同的均值計算方法都會影響最終的人群定向效果.為了驗證調和均值方法對人群定向的影響，本文在4組數據集上進行了簡單調和均值法(harmonic mean,HM)與算術平均法(arithmetic mean, AM)的對比實驗，具體的實驗結果如圖3所示:

Fig. 3 Comparison of different parameters圖3 不同參數的比較

從圖3中可以看出，無論是在準確率Precision上，還是召回率Recall和F-measure上，AM方法都沒有HM方法的人群定向的效果較好.在4組數據集中，2種方法在第2組數據集上的影響最大，HM方法的準確率Precision比AM方法高2.4%，在召回率Recall上，HM方法比AM方法高2.2%；而在第3組數據集上的影響最小，在準確率Precision上，HM方法比AM方法高0.9%，HM方法的召回率Recall比AM方法高1.1%.由此可知，不同的均值方法都會影響最終的人群定向效果.

4.6 參數的影響

在基于用戶行為和用戶特征的候選人群選取算法中設置了參數k，參數k的不同影響著人群定向的效果.為了驗證參數k的影響，本文在4組數據集上進行了不同參數k的實驗，具體實驗結果如圖4所示.

從圖4中可以發現，k的取值對人群定向的結果具有顯著影響.隨著k的取值的不同，無論哪組數據集，ATNCS方法的3個評價指標Precision，Recall，F-measure也都發生了顯著變化.當參數k從0開始增加時，3個評價指標的值會逐漸升高；當參數k=6時，3個評價指標達到了最大值，此時，人群定向的效果是最佳的；當參數k>6后，3個評價指標便會隨著k的增加而逐漸減小.由此可知，參數k的取值影響著人群定向的質量.于是在人群定向中，選擇合適的參數k是不容忽視的.

Fig. 4 Comparison of different parameters圖4 不同參數的比較

5 結論與進一步工作

本文以用戶行為和用戶特征為鄰居選取的重要依據，提出了基于鄰居選取策略的人群定向算法.首先從行為相似人群中找出種子的候選人群，并通過基于鄰居選取策略的人群定向算法找出潛在的目標人群.實驗結果表明：用戶行為和用戶特征不僅在人群定向中起了重要作用，而且在增強人群定向系統的抗攻擊能力方面也十分重要.

此外，該算法雖然取得了一定效果，但是忽略了系統中的時間屬性，如用戶訪問的媒體和用戶特征都是具有一定時間屬性的.在未來的工作，將進一步研究如何將時間屬性與用戶媒體、用戶特征結合在一起，以進一步改善人群定向的效果.

[1]Xu Hailing, Wu Xiao, Li Xiaodong, et al. Comparison study of internet recommendation system[J]. Journal of Software, 2009, 20(2): 350-362 (in Chinese)(許海玲, 吳瀟, 李曉東, 等. 互聯網推薦系統比較研究[J]. 軟件學報, 2009, 20(2): 350-362)

[2]Huang Zhenhua, Zhang Jiawen, Tian Chunqi, et al. Survey on learning-to-rank based recommendation algorithms[J]. Journal of Software, 2016, 27(3): 691-713 (in Chinese)(黃震華, 張佳雯, 田春岐, 等. 基于排序學習的推薦算法研究綜述[J]. 軟件學報, 2016, 27(3): 691-713)

[3]Guo Lei, Ma Jun, Chen Zhumin, et al. Incorporating item relations for social recommendation[J]. Chinese Journal of Computers, 2014, 37(1): 219-228 (in Chinese)(郭磊, 馬軍, 陳竹敏, 等. 一種結合推薦對象間關聯關系的社會化推薦算法[J]. 計算機學報, 2014, 37(1): 219-228)

[4]Rong Huigui, Huo Shengxu, Hu Chunhua, et al. User similarity-based collaborative filtering recommendation algorithm[J]. Journal of Communications, 2014, 35(2): 16-24 (in Chinese)(榮輝桂, 火生旭, 胡春華, 等. 基于用戶相似度的協同過濾推薦算法[J]. 通信學報, 2014, 35(2): 16-24)

[5]Popescul A, Ungar L H, Pennock D M, et al. Probabilistic models for unified collaborative and content-based recommen-dation in sparse-data environments[C]Proc of the 7th Conf on Uncertainty in Artificial Intelligence. New York: ACM, 2001: 437-444

[6]Arora G, Kumar A, Devre G S, et al. Movie recommendation system based on users’ similarity[J]. International Journal of Computer Science and Mobile Computing, 2014, 3(4): 765-770

[7]Ekstrand M D, Riedl J T, Konstan J A. Collaborative filtering recommender systems[J]. Foundations and Trends in Human-Computer Interaction, 2011, 4(2): 81-173

[8]Linden G, Smith B, York J. Amazon. com recommen-dations: Item-to-item collaborative filtering[J]. IEEE Internet Computing, 2003, 7(1): 76-80

[9]Cai Yi, Leung H, Li Qing, et al. Tyco: Towards typicality-based collaborative filtering recommendation[C]Proc of the 22nd IEEE Int Conf on Tools with Artificial Intelligence. Piscataway, NJ: IEEE, 2010: 97-104

[10]Chen Kehan, Han Panpan, Wu Jian. User cluster based social network recommendation[J]. Chinese Journal of Computers, 2013, 36(2): 349-359 (in Chinese)(陳克寒, 韓盼盼, 吳健. 基于用戶聚類的異構社交網絡推薦算法[J]. 計算機學報, 2013, 36(2): 349-359)

[11]Wang Tingting, Liu Hongyan, He Jun, et al. Predicting new user’s behavior in online dating systems[G]LNAI 7121: Proc of the 7th Int Conf on Advanced Data Mining and Applications. Berlin: Springer, 2011: 266-277

[12]Koren Y. Factorization meets the neighborhood: A multifaceted collaborative filtering model[C]Proc of the 14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2008: 426-434

[13]Mobasher B, Burke R, Sandvig J J. Model-based collaborative filtering as a defense against profile injection attacks[C]Proc of the 21st AAAI Conf on Artificial Intelligence(AAAI’06). Menlo Park, CA: AAAI Press, 2006: 1388-1393

[14]Mehta B, Hofmann T, Nejdl W. Robust collaborative filtering[C]Proc of the 1st ACM Int Conf on Recommender Systems. New York: ACM, 2007: 49-56

[15]Sandvig J J, Mobasher B, Burke R. Robustness of collaborative recommendation based on association rule mining[C]Proc of the 1st ACM Int Conf on Recommender Systems. New York: ACM, 2007: 105-112

[16]Jamali M, Ester M. TrustWalker: A random walk model for combining trust-based and item-based recommendation[C]

[17]Ma H, King I, Lyu M R. Learning to recommend with social trust ensemble[C]Proc of the 32nd ACM SIGIR Int Conf on Research and Development in Information Retrieval. New York: ACM, 2009: 203-210

[18]Ma H, Zhou T C, Lyu M R, et al. Improving recommender systems by incorporating social contextual information[J]. ACM Trans on Information Systems, 2011, 29(2): 219-230

[19]Jia Dongyan, Zhang Fuzhi. A collaborative filtering recommendation algorithm based on double neighbor choosing strategy[J]. Journal of Computer Research and Development, 2013, 50(5): 1076-1084 (in Chinese)(賈冬艷, 張付志. 基于雙重鄰居選取策略的協同過濾推薦算法[J]. 計算機研究與發展, 2013, 50(5): 1076-1084)

[20]Huang Chuangguang, Yin Jian, Wang Jing, et al. Uncertain neighbors’ collaborative filtering recommendation algorithm[J]. Chinese Journal of Computers, 2010, 33(8): 1369-1377 (in Chinese)(黃創光, 印鑒, 汪靜, 等. 不確定近鄰的協同過濾推薦算法[J]. 計算機學報, 2010, 33(8): 1369-1377)

Zhou Meng, born in 1986. PhD candidate. Student member of CCF. His main research interests include data mining and natural language processing.

Zhu Fuxi, born in 1957. Professor and PhD supervisor. His main research interests include artificial intelligence, knowledge mining and distributed computing.

An Audience Targeting Algorithm Based on Neighbor Choosing Strategy

Zhou Meng1and Zhu Fuxi1,2

1(SchoolofComputerScience,WuhanUniversity,Wuhan430072)2(SchoolofComputerScienceandTechnology,HankouUniversity,Wuhan430212)

Audience targeting which is designed to discover the prospective target users by analyzing the these seed users’ behavior is an important technology in the online advertising recommendation systems, and the existing audience targeting technologies mostly rely on collaborative filtering algorithms. However, the traditional collaborative filtering algorithms have the disadvantages of lower precision and weaker anti-attack capability. In order to solve the problems, an audience targeting algorithm based on neighbor choosing strategy is proposed. Firstly, the users which have the similar behavior with the seed audiences are chosen dynamically by means of the user behavior similarity. Then, on the basis of the users’ feature and behavior, the neighbors of each seed user are chosen from the behavior similar audiences by the user similarity, and all the neighbors are considered to be the candidate audiences. Finally, the prospective audiences are chosen from the candidate users by the audience targeting algorithm based on neighbor choosing strategy, so as to complete the task of audience targeting. Compared with the existing methods, the experimental results on real-world advertisement datasets show that the audience targeting algorithm not only improves the precision, but enhances the anti-attack capability as well.

seed audiences; behavior similar audiences; neighbor choosing strategy; user similarity; audience targeting

2016-05-20；

2016-11-04

國家自然科學基金項目(61272277) This work was supported by the National Natural Science Foundation of China (61272277).

朱福喜(fxzhu@whu.edu.cn)

TP391; TP18