基于PU與生成對抗網(wǎng)絡的POI定位算法

田繼偉 王勁松 石 凱

(天津理工大學計算機科學與工程學院 天津 300384) (天津市智能計算及軟件新技術(shù)重點實驗室(天津理工大學) 天津 300384) (計算機病毒防治技術(shù)國家工程實驗室(天津理工大學) 天津 300457)

隨著互聯(lián)網(wǎng)的蓬勃發(fā)展，個性化推薦技術(shù)已經(jīng)成為學術(shù)界的研究熱點之一.近年來，個性化推薦技術(shù)已經(jīng)成功應用于多個領(lǐng)域，尤其是在廣告推薦領(lǐng)域，它帶來了巨大的商業(yè)價值.但是，個性化推薦技術(shù)的數(shù)據(jù)來源于人們在網(wǎng)絡上產(chǎn)生的行為，這些網(wǎng)絡行為往往是低成本的，由這些低成本的行為推薦來的廣告雖然具有很大價值，但確有局限性.例如，經(jīng)常在網(wǎng)絡上瀏覽汽車的人雖然有很大可能性接受汽車類的廣告推薦，但是相比之下，那些去4S店的人有更大可能性購買汽車，從而給商家?guī)碚嬲睦麧?考慮到推薦技術(shù)的這種局限性，對興趣點(point of interest, POI)的定位和推薦技術(shù)就變得非常重要.另外，隨著智能移動設(shè)備的快速普及，人們對基于位置的社交網(wǎng)絡服務(location-based social networking service, LBSNS)的依賴性也越來越高.基于數(shù)據(jù)挖掘的POI定位和推薦技術(shù)已經(jīng)成為一個重要課題.高榕等人[1]將POI、社交關(guān)聯(lián)和評論信息融合起來，提出了一種GeoSoRev興趣點推薦模型.Chen等人[2]研究了LBSNS中的連續(xù)個性化POI推薦問題，將時間關(guān)系融合到POI推薦中.Gao等人[3]將內(nèi)容信息融合進了POI推薦系統(tǒng)中.Yin等人[4]考慮了用戶在不同區(qū)域往往有不同的興趣，研究了跨區(qū)域的POI推薦系統(tǒng).但是，文獻[1-4]的POI推薦系統(tǒng)都無法離開POI定位技術(shù)的建設(shè).

目前，國內(nèi)外許多研究已經(jīng)利用無線網(wǎng)絡來進行POI定位.其中，使用最多的方法是基于無線信號接收強度(received signal strength, RSS)的位置指紋技術(shù)[5-7]，該技術(shù)已經(jīng)廣泛應用于移動通信領(lǐng)域，且可以在任何具有WiFi發(fā)射設(shè)備的地方推廣應用.但是由于用戶隱私問題，有POI標記的數(shù)據(jù)難以收集.一般來說，采集來的數(shù)據(jù)可以分為2類：一類是占比很大的沒有標記POI的數(shù)據(jù)；另一類是占比很小的標記了POI的數(shù)據(jù)，即正樣本數(shù)據(jù).這就造成了正樣本數(shù)據(jù)不足的問題，極大地影響了POI定位的準確性.目前很少有研究致力于解決這一普遍存在的問題.Matos等人[8]提出了一種模擬定位的方式去進行POI的識別.然而，這種識別系統(tǒng)的誤差會隨著系統(tǒng)計算量的增大而增加.此外，Moghtadaiee等人[9]提出了一種短距離RSS誤差模型來提高POI定位效果，但累積誤差的問題仍然無法得到有效解決.

本文基于現(xiàn)有數(shù)據(jù)，提出了一種基于PU與生成對抗網(wǎng)絡(positive and unlabeled generative adversarial network, puGAN)的模型來進行POI的有效定位與識別.實驗表明，本文提出的puGAN模型比傳統(tǒng)的POI定位和分類模型具有更好的效果.本文工作的主要貢獻有2個方面：

1) 將PU(positive and unlabeled)學習[10-11]和生成對抗網(wǎng)絡(generative adversarial network, GAN)模型相結(jié)合，并應用到POI定位算法中，以此解決數(shù)據(jù)樣本不足的問題，從而提高POI定位的準確性；

2) 理論證明了puGAN模型的普遍適用性.

1 相關(guān)研究工作

到目前為止，大部分POI定位模型都有著數(shù)據(jù)采集不足的缺陷.有2種方式可以解決這個問題：一種方式是覆蓋所有的采集點采集充足的數(shù)據(jù)，但這種方式往往伴隨著巨大的人力、財力和時間成本，通常來說是不可接受的；另一種方式是基于少量正樣本和大量無標簽樣本，使用PU學習方法.下面簡單介紹PU學習算法.

1.1 PU學習算法

PU學習作為半監(jiān)督學習[12]的一個重要分支，逐漸成為了研究界的熱點問題.PU算法對無標簽樣本的使用情況，可以概括成2個方面：

1) 基礎(chǔ)模型的研究.通過單類模型(one-class, OC)對正樣本數(shù)據(jù)進行學習，但是這種方式通常會浪費較多的數(shù)據(jù)特征，從而導致模型欠擬合.或者使用SVM等二分類模型，它們雖然能夠利用到所有的數(shù)據(jù)特征，但無法避免無標簽樣本噪聲過大而可能導致的欠擬合問題.

2) 基于高可信樣本的挖掘.這種方法的核心是優(yōu)先找到高可信的正樣本或者負樣本，從而基于此樣本進行學習和分類.任亞峰等人[13]使用這種PU學習的方式，從大量無標簽樣本中識別出少量高可信的負樣本，進行了識別虛假評論的研究.

PU學習雖然能夠利用少量正樣本以及大量無標簽樣本進行學習，但是正樣本和無標簽樣本的樣本量相差巨大，影響了模型學習的準確性和快速性.本文在利用PU學習算法的同時引入了GAN模型，一方面生成偽正樣本彌補正樣本不足的缺陷，另一方面學習無標簽樣本的分布，提高分類模型的準確性.下面簡單介紹GAN模型.

1.2 GAN模型

2014年，Goodfellow等人[14]提出了GAN，并進行了一系列研究[15-16]，解決了如何使機器學習的訓練成果向著理想方向前進的問題.Odena[17]首次將GAN模型與半監(jiān)督學習相結(jié)合來提高生成器的質(zhì)量.

如圖1所示，GAN模型針對正樣本提出了生成器與判別器的概念.生成器通過不斷學習真實樣本數(shù)據(jù)的分布生成偽樣本，從而盡可能欺騙判別器.而判別器則通過學習真實樣本和偽樣本的差異，盡可能區(qū)分出數(shù)據(jù)來源.

Fig. 1 The illustration of GAN model圖1 GAN模型圖

生成器和判別器不斷博弈的過程就是數(shù)據(jù)不斷生成和分類的過程.實驗證明，GAN模型在訓練樣本不足的情況下，能夠有效學習出原有數(shù)據(jù)的分布特征.與此同時，模型的判別器也能夠準確地區(qū)分出樣本是來源于生成器還是來源于真實的訓練數(shù)據(jù)集.

另外，2017年，Arjovsky等人[18]提出了一種觀點，即GAN中利用JS散度會導致納什不均衡的問題，這會使模型訓練不穩(wěn)定.為了解決這個問題，他提出了WGAN模型，這種模型在提升穩(wěn)定性與準確性上有很好的表現(xiàn).本文提出的puGAN模型也使用了這一思想.

不同于傳統(tǒng)的GAN模型，本文不僅將GAN模型應用于POI定位中，而且在模型中分別對正樣本和無標簽樣本都引入了生成器和判別器.

2 基于PU與生成對抗網(wǎng)絡的模型

本文將第1節(jié)的PU學習與生成對抗網(wǎng)絡模型相結(jié)合，提出了基于PU與生成對抗網(wǎng)絡的模型.下面將詳細介紹puGAN模型的原理及理論分析.

2.1 puGAN模型

在本文中，Xp，Xu分別表示正樣本數(shù)據(jù)集和無標簽樣本數(shù)據(jù)集；pp(x)，pn(x)，pu(x)，p(x)分別表示正樣本、負樣本、無標簽樣本以及整個數(shù)據(jù)集合的分布；Gp，Gu分別表示puGAN模型中正樣本生成器和無標簽樣本生成器；Dp，Du分別表示正樣本判別器和無標簽樣本判別器；Dpu表示正樣本無標簽樣本判別器.本文假設(shè)數(shù)據(jù)分布遵循的規(guī)則為

p(x)=pp(x)+pn(x),

pu(x)=θppp(x)+θnpn(x),

其中θp，θn都是0～1之間的小數(shù)，并且滿足θp+θn=1.

基于上面的假設(shè)，本文設(shè)計了puGAN模型.如圖2所示，描述了puGAN模型的訓練過程.其中，判別器Du通過對真實的無標簽樣本與無標簽樣本生成器Gu生成的數(shù)據(jù)進行判別分類，從而調(diào)整學習得到無標簽樣本數(shù)據(jù)的分布特征.同理，判別器Dp通過對正樣本進行判別分類，訓練得到正樣本數(shù)據(jù)的分布特征.

Fig. 2 The illustration of puGAN model圖2 puGAN模型圖

最終，puGAN模型的目標函數(shù)為

(1)

其中，α，β，γ均為大于0的參數(shù).

判別器希望提高自己的辨別能力，能夠準確分辨出樣本是來源于真實樣本集還是來源于生成器生成.而生成器則不斷提升自己的“偽造”技術(shù)，希望能夠生成可以“以假亂真”的數(shù)據(jù).根據(jù)零和博弈的原則，將目標函數(shù)進行推導，可以得到

VGu,Du(G,D)=Ex～pu(x)lg(Du(x))+Ez～pzu(z)lg(1-Du(Gu(z))),

(2)

VGp,Dp(G,D)=Ex～pp(x)lg(Dp(x))+Ez～pzp(z)lg(1-Dp(Gp(z))),

(3)

VGp,Gu,Dpu(G,D)=Ex～pp(x)lg(Dpu(Gp(x)))+Ez～pu(z)lg(1-Dpu(Gu(z))).

(4)

在此訓練過程中，正樣本判別器Dp、無標簽樣本判別器Du、正樣本無標簽樣本判別器Dpu、正樣本生成器Gp和無標簽樣本生成器Gu均由深度神經(jīng)網(wǎng)絡訓練得到.整個模型的訓練過程如算法1所示.

算法1.puGAN模型訓練算法.

輸入：正樣本數(shù)據(jù)集和無標簽樣本數(shù)據(jù)集；

① FOR 訓練次數(shù)

② FOR 迭代次數(shù)

⑦ 計算無標簽樣本判別器的梯度值，并以此梯度進行梯度下降計算

⑧ 計算正樣本判別器的梯度值，并以此梯度進行梯度下降計算

⑩ END FOR

在此訓練過程中，噪聲普遍存在于正樣本和無標簽樣本數(shù)據(jù)中，因此，本文分別對正樣本和無標簽樣本引入了生成器與判別器，從而調(diào)整并學習得到2個樣本的分布特征.隨后，使用無標簽樣本生成器和正樣本生成器分別生成偽無標簽樣本和偽正樣本數(shù)據(jù)，并根據(jù)此數(shù)據(jù)進行分類學習，最終得到了POI定位的分類模型.

2.2 理論分析

(5)

(6)

(7)

證明. 對于任何一個給定的生成器，分類器Du，Dp，Dpu的估值函數(shù)方程為

(8)

(9)

(10)

通過合并最優(yōu)估值函數(shù)，可以得到結(jié)論：

(11)

證畢.

定理1.當且僅當pu=pgu，pp=pgp,且2pp=φupgu+φppgp時，目標函數(shù)可以達到全局最小值.

證明. 當滿足上述條件時，可以得到：

Ex～pu(x)[-lg 2]+Ex～pzu(x)[-lg 2]=-lg 4,

(12)

Ex～pp(x)[-lg 2]+Ex～pzp(x)[-lg 2]=-lg 4,

(13)

Ex～pzp(x)[-lg 2]+Ex～pzu(x)[-lg 2]=-lg 4.

(14)

將式(12)～(14)帶入式(11)，可以得到：

C(G)=α[-lg 4+JS(pp‖pgp)]+β[-lg 4+JS(pu‖pgu)]+γ[-lg 4+JS(pgp‖pgu)]，

(15)

其中，JS為分布之前的JS散度.

所以，當滿足條件pu=pgu，pp=pgp且2pp=φupgu+φppgp時，可以取得目標函數(shù)的全局最優(yōu)值.

證畢.

3 實例分析

3.1 數(shù)據(jù)集

本文使用的是脫敏后某高校校園無線網(wǎng)絡接入日志數(shù)據(jù)，日志提供了對設(shè)備信息加密后的唯一標識及掃描得到的WiFi信息列表.具體的WiFi數(shù)據(jù)格式為

〈id1,sig1|id2,sig2|…|idm,sigm〉，

其中,idi表示第i個發(fā)射WiFi信號設(shè)備的標識，sigi為第i個WiFi所對應的信號強度.

數(shù)據(jù)集共包含176 449條數(shù)據(jù)，覆蓋了210個WiFi接入點和150個POI.其中，正樣本15 888條，無標簽樣本160 561條.本文將有連接行為的數(shù)據(jù)標記為該WiFi接入點的正樣本數(shù)據(jù)，并與對應的POI進行關(guān)聯(lián)，將與其他POI關(guān)聯(lián)的正樣本數(shù)據(jù)作為該POI的負樣本數(shù)據(jù)，將無連接行為的數(shù)據(jù)作為無標簽數(shù)據(jù).通常來說，一個POI可能對應多個WiFi接入點，同時每個WiFi接入點對應著多條正樣本和無標簽樣本數(shù)據(jù).通過對數(shù)據(jù)集進行初步分析，可以知道正樣本大約只有總數(shù)據(jù)量的9%，而剩余的91%均為無標簽樣本.本文又對正樣本數(shù)據(jù)進行深入統(tǒng)計和分析，得到了它的統(tǒng)計規(guī)律如圖3所示:

Fig. 3 The statistics of positive samples圖3 正樣本數(shù)據(jù)統(tǒng)計圖

從圖3可以發(fā)現(xiàn)， 47%的WiFi接入點擁有的正樣本數(shù)在10條以下，而正樣本數(shù)量在300條以上的WiFi接入點僅僅占比9%.由此可見，過半的WiFi接入點的正樣本缺失情況嚴重.此情況在一個POI具有多個WiFi接入點的時候尤為明顯.

在實驗中，由于采集得到的負樣本在物理空間中通常偏于一側(cè)，為了避免訓練結(jié)果出現(xiàn)偏差，本文使用正樣本和負樣本作為評估集，使用正樣本和無標簽樣本作為訓練集.

在訓練過程中，由于數(shù)據(jù)本身特征維度相對較高，在樣本偏少的情況下，傳統(tǒng)的分類模型通常會因訓練不足而難以得到理想的樣本分布情況.為了證明puGAN模型的有效性，本文進行了2組對比實驗：第1組實驗對比了OC、SVM[19]、神經(jīng)網(wǎng)絡(neural network, NN)[20]以及puGAN這4種模型的效果；第2組實驗對比了GAN模型在不同使用條件下的效果.下面將分別闡述這2組實驗.

3.2 傳統(tǒng)模型與puGAN模型對比

實驗通過調(diào)整模型不同的超參數(shù)進行交叉驗證訓練，得到了不同準確率下對應的數(shù)據(jù)召回率.根據(jù)此準確率和召回率，使用ROC曲線來對模型效果進行比較與分析.如圖4所示是不同模型在實驗數(shù)據(jù)集上的表現(xiàn).

圖4中，橫軸表示模型的召回率，縱軸表示模型的準確率，ROC面積越大表示模型效果越好.

從圖4可以看出，單類模型的ROC面積為0.761，在準確率為80%時召回率不足60%，效果明顯低于其他的幾類模型.SVM與神經(jīng)網(wǎng)絡(NN)模型在ROC曲線的評估上效果相當，當準確率為80%時召回率均為77%左右.而puGAN模型在準確率為80%時召回率達到了85%左右，對應的ROC面積也明顯高于其他模型.

Fig. 4 Comparison of ROC curves among OC, SVM, NN and puGAN圖4 OC,SVM,NN和puGAN的ROC曲線對比圖

此外，我們還觀察了這4種模型的訓練誤差和測試誤差隨迭代次數(shù)增加的變化，這種變化反應模型的擬合情況，如圖5所示:

Fig. 5 Training error and Testing error among OC, SVM, NN and puGAN圖5 OC,SVM,NN和puGAN訓練誤差和測試誤差分析對比圖

由圖5可知，單類模型明顯存在著欠擬合的情況，經(jīng)過多輪的迭代，訓練誤差始終維持在26%左右，整體效果較差.SVM和神經(jīng)網(wǎng)絡的表現(xiàn)明顯優(yōu)于單類模型，訓練誤差維持在21%左右.但隨著迭代次數(shù)的增加，由于神經(jīng)網(wǎng)絡結(jié)構(gòu)復雜，它的測試誤差不斷上升，出現(xiàn)了過擬合的情況.puGAN模型在訓練初始階段，收斂速度會略慢于SVM以及神經(jīng)網(wǎng)絡，但在最終效果卻明顯優(yōu)于上述2類模型，且模型表現(xiàn)穩(wěn)定，訓練誤差和測試誤差均維持在15%左右.

綜上，由于單類模型在訓練過程中只利用了正樣本進行學習，而忽略了大量的無標簽樣本，所以整體實驗效果均不佳.SVM與神經(jīng)網(wǎng)絡均使用了正樣本和無標簽樣本進行二分類學習，SVM模型結(jié)構(gòu)較神經(jīng)網(wǎng)絡簡單，因此收斂速度較快，在準確率和召回率上二者差別不大.puGAN對正樣本和無標簽樣本進行學習，生成偽正樣本來彌補數(shù)據(jù)不足的問題，同時生成偽無標簽樣本來提高判別器對正樣本的識別能力.因此，從ROC曲線以及模型擬合情況來看，puGAN的效果明顯優(yōu)于傳統(tǒng)的機器學習模型.

3.3 3種GAN模型對比

第2組實驗中，我們對比分析了puGAN模型與另外2種未校正模型在準確率、召回率以及訓練誤差、測試誤差等指標上的表現(xiàn)情況.其中未校正的模型包括未對正樣本建模(本文稱GAN1)以及未對無標簽樣本建模(本文稱GAN2)這2種情況.

如圖6所示，puGAN模型的ROC面積略高于GAN1和GAN2這2種未校正的模型.在這3種模型中，GAN1模型面積最小，其值只有0.835.該模型由于未能夠?qū)φ龢颖具M行分布上的學習，使得訓練得到的模型在準確率以及召回率上的表現(xiàn)不佳，得到的分類面也偏于無標簽樣本數(shù)據(jù)一方.GAN2模型雖然也受到了訓練樣本不均勻的影響，但是在準確率和召回率上的表現(xiàn)卻略好于GAN1模型，原因是GAN2模型對正樣本進行了建模和重采樣，使其受到的正樣本數(shù)據(jù)不足的影響略低于GAN1模型.

此外，我們也同樣觀察了上述3種模型訓練誤差和測試誤差的變化，并對它們的擬合情況進行了分析.如圖7所示為3種模型的訓練誤差以及測試誤差隨著迭代次數(shù)增加的變化情況.從圖7中可以看出，GAN1模型在訓練初期存在過擬合的情況，但隨著迭代次數(shù)的增加，過擬合逐漸緩解，效果趨于穩(wěn)定.GAN2模型在訓練過程中整體效果較為穩(wěn)定，但是誤差較大，始終維持在20%以上.而puGAN模型最終訓練誤差和測試誤均在15%左右且效果穩(wěn)定.

Fig. 6 Comparison of ROC curves among GAN1, GAN2 and puGAN圖6 GAN1,GAN2和puGAN的ROC曲線圖

Fig. 7 Training error and Testing error among GAN1, GAN2 and puGAN圖7 GAN1,GAN2和puGAN訓練誤差和測試誤差分析對比圖

綜上所述，在GAN的3類模型中，puGAN模型在ROC面積以及穩(wěn)定性上表現(xiàn)更為突出.

4 結(jié) 論

本文討論了puGAN模型在POI定位中的應用.實驗表明，該模型通過對正樣本和無標簽樣本進行建模和生成，提升了POI定位的準確率和召回率，從而有效解決了數(shù)據(jù)樣本不足以及半監(jiān)督學習中噪聲過大的問題.

實驗還表明，該模型能夠避免復雜模型所帶來的過擬合問題，且具有更好的穩(wěn)定性.此研究為現(xiàn)有的POI定位系統(tǒng)提供了新的指導意義.

雖然puGAN模型在準確率、召回率和穩(wěn)定性上表現(xiàn)優(yōu)秀，但是卻存在迭代速度較慢的缺點.在大數(shù)據(jù)的背景下，提升模型訓練速度也早已成為了一個重要的課題.在今后的研究中，我們會改進訓練過程中最優(yōu)化的方法來提升模型訓練的效率.