Personalized Ranking Metric Embedding for Nest New POI Recommendation

介紹(Introduction):

本篇論文主要利用距離嵌入(Metric

Embedding)將每個(gè)POI映射到一個(gè)低維的歐拉空間當(dāng)中弧圆，有效地利用馬爾科夫鏈模型預(yù)測(cè)POI的變化，用兩個(gè)POI的歐拉距離衡量?jī)烧叩男蛄嘘P(guān)系至扰，并且進(jìn)一步提出了成對(duì)排序(pair-wise

ranking)的距離嵌入，可以對(duì)空間中潛在的POI進(jìn)行排序资锰，最后提出了個(gè)性化的距離嵌入排名(PRME)算法敢课，綜合考慮序列信息和個(gè)人喜好，因?yàn)槿藗兌純A向于拜訪距離他們位置比較近的POI绷杜，所以考慮空間因素直秆，將模型拓展為PRME-G模型。

論文原理：

論文使用了兩個(gè)數(shù)據(jù)集鞭盟，F(xiàn)ourSquare在新加坡內(nèi)的數(shù)據(jù)和Gowalla在加利福尼亞和內(nèi)華達(dá)的數(shù)據(jù)圾结，在使用前對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，將訪問少于10個(gè)POI的用戶刪除齿诉，以及將少于10個(gè)用戶訪問的POI刪去筝野。通過對(duì)數(shù)據(jù)的統(tǒng)計(jì)可以得到以下三個(gè)結(jié)論：

用戶有探索新POI的傾向

時(shí)間局部性，用戶訪問兩個(gè)POI的時(shí)間間隔不會(huì)很長(zhǎng)

空間局部性粤剧，用戶連續(xù)訪問的兩個(gè)POI的距離不會(huì)很遠(yuǎn)

當(dāng)在短時(shí)間內(nèi)發(fā)生兩個(gè)check-in時(shí)歇竟，可以相信存在馬爾科夫鏈的屬性，也就是下一個(gè)POI很大程度上受當(dāng)前POI的影響俊扳⊥窘基于這種短時(shí)間內(nèi)的馬爾科夫?qū)傩院腿藗兲剿餍翽OI的傾向猛遍，我們可以定義本論文涉及推薦問題：給定一個(gè)用戶u和他當(dāng)前所處的位置l馋记，從用戶u沒有訪問過的POI中選擇一個(gè)新的推薦給用戶u。如果只是推薦一個(gè)POI懊烤，那么推薦用戶u訪問最頻繁的POI就可能得到較高的正確率梯醒，但是我們要推薦新的POI，所以這種方法并不適用腌紧，它要使用更稀疏的歷史數(shù)據(jù)推測(cè)轉(zhuǎn)移概率茸习，所以下一個(gè)新POI的推薦要比下一個(gè)POI推薦更難。

我們首先介紹使用成對(duì)排名的距離嵌入算法來對(duì)位置變換進(jìn)行建模壁肋。距離嵌入模型適用于處理稀疏的數(shù)據(jù)和未觀測(cè)到的數(shù)據(jù)号胚。我們用高維空間的一個(gè)點(diǎn)表示現(xiàn)實(shí)世界的POI，用兩個(gè)POI在高維空間中的歐拉距離表示兩個(gè)POI轉(zhuǎn)換的概率浸遗，距離越小猫胁，概率越大，把所有的POI嵌入到高維隱空間跛锌，我們的模型可以推測(cè)位置轉(zhuǎn)換的概率弃秆，并且也可以用來給沒有觀測(cè)到的轉(zhuǎn)換賦予有意義的概率。在距離嵌入模型中，每個(gè)POI在K維空間中用一個(gè)K維向量表示位置菠赚，我們的任務(wù)脑豹，就是通過訪問序列來推測(cè)出表示POI的K維向量，轉(zhuǎn)換概率如下所示：

上述式子只能表示已經(jīng)觀測(cè)到的POI轉(zhuǎn)換關(guān)系衡查，因?yàn)楸挥^測(cè)到的數(shù)據(jù)非常稀疏瘩欺，為了讓學(xué)習(xí)到的向量關(guān)系符合POI轉(zhuǎn)換的概率關(guān)系，我們需要充分利用沒有觀測(cè)到的數(shù)據(jù)拌牲，我們假設(shè)觀測(cè)到的下一個(gè)POI和當(dāng)前的POI更有關(guān)系击碗，沒有觀測(cè)到POI影響更小，所以能夠觀測(cè)到的POI的排名應(yīng)該比沒有觀測(cè)到的POI排名高们拙，以此作為排名推測(cè)的依據(jù)稍途。

POI推薦的目標(biāo)就是提供對(duì)所有POI的排名，推薦排名最高的一項(xiàng)砚婆。我們可以進(jìn)一步簡(jiǎn)化上面的概率表示：

接下來介紹個(gè)性化排名距離嵌入算法械拍，下一個(gè)POI推薦不僅與當(dāng)前位置有關(guān)，而且與用戶的喜好有關(guān)装盯，我們引入一個(gè)新的高維空間坷虑，將用戶和POI嵌入到這個(gè)高維空間，用戶u和位置l在空間中的歐拉距離表示u對(duì)l的喜愛程度埂奈，距離越近迄损，喜愛程度越高，去的可能越大账磺，綜合考慮序列信息和個(gè)人喜好芹敌，用戶將l作為下一個(gè)訪問的POI的概率可以表示為：

根據(jù)之前提到的，馬爾科夫鏈屬性在兩次短時(shí)間訪問時(shí)才能凸顯垮抗，所以當(dāng)下一次訪問和當(dāng)前訪問時(shí)間差距比較大時(shí)氏捞，可以不考慮序列信息，只考慮用戶的喜好冒版，所以可以改善表示為：

最后將地理因素考慮進(jìn)模型液茎，我們用當(dāng)前POI的位置和下一次訪問的位置之間的距離計(jì)算地理因素系數(shù)w，位置越近越近辞嗡，w越小捆等，可能性越大，同樣续室，當(dāng)兩次時(shí)間差過大時(shí)栋烤，不考慮當(dāng)前POI對(duì)下一次訪問的影響，地理因子同樣不需要考慮猎贴，所以最終的概率表示為：

該模型的最優(yōu)化標(biāo)準(zhǔn)參考貝葉斯個(gè)性化推薦(BPR)的方法班缎，最大化后驗(yàn)概率來推測(cè)參數(shù)蝴光，使用logistic函數(shù)表示條件概率，對(duì)參數(shù)使用高斯前驗(yàn)达址，最后加正則化參數(shù)蔑祟，防止過擬合，損失函數(shù)為：

算法實(shí)現(xiàn)：

如果直接對(duì)上面的表達(dá)式利用梯度下降計(jì)算最值時(shí)的參數(shù)沉唠，計(jì)算量比較大疆虚，所以采用之前提到的排名原則，對(duì)用戶u满葛，當(dāng)前位置lc径簿，觀測(cè)到的下一訪問li，隨機(jī)選擇一個(gè)沒有觀測(cè)到過的位置lj嘀韧，用戶u在位置lc訪問觀測(cè)到的li的概率應(yīng)該大于沒有觀測(cè)到的lj的概率篇亭，所以我們最小化的目標(biāo)變?yōu)?/p>

當(dāng)z最小時(shí)，前一項(xiàng)最小锄贷，概率大译蒂，后一項(xiàng)最大，概率小谊却，符合預(yù)期柔昼，所以梯度下降算法用下列方式進(jìn)行參數(shù)更新：

在算法實(shí)現(xiàn)過程中，首先獲得數(shù)據(jù)元組炎辨，包括用戶捕透，當(dāng)前位置，下一觀測(cè)到的位置碴萧，隨機(jī)選擇一個(gè)沒有觀測(cè)到的位置乙嘀，然后用期望為0，方差為0.01的正態(tài)分布隨機(jī)初始化用戶和POI在高維空間中向量位置勿决，一個(gè)表示序列關(guān)系的空間乒躺，一個(gè)表示用戶喜好的空間招盲，然后用上面的參數(shù)更新方法更新參數(shù)低缩，直到收斂，即損失函數(shù)最小曹货，收斂后返回用戶和POI在兩個(gè)空間中的高維坐標(biāo)咆繁。

在測(cè)試時(shí)，如果要推測(cè)用戶u下一刻要訪問哪一個(gè)POI顶籽，需要對(duì)所有未觀測(cè)到的POI利用之前訓(xùn)練出的兩個(gè)空間中的坐標(biāo)計(jì)算出D玩般，按D值進(jìn)行排序，將D值最小的POI推薦給用戶礼饱。

需要的數(shù)據(jù)集可以從http://www.ntu.edu.sg/home/gaocong/data/poidata.zip下載坏为，代碼如下所示:

import os

import numpy as np

from math import radians, cos, sin, asin, sqrt, pow, log

def getUser():

? ? fr=open("user.txt",'r')

? ? user=[]

? ? for linein fr.readlines():

? ? ? ? user.append(line.strip())

? ? fr.close()

? ? return user

def getShop():

? ? fr=open("shop.txt",'r')

? ? shop=[]

? ? for linein fr.readlines():

? ? ? ? shop.append(line.strip())

? ? fr.close()

? ? return shop

def getTrainTuple(fileName):

? ? data=[]

? ? observedPOI={}

? ? exUser=' '

? ? exShop=' '

? ? exTime=' '

? ? fr=open(fileName)

? ? for linein fr.readlines():

? ? ? ? lineArr=line.strip().split('\t')

? ? ? ? user=lineArr[0]

? ? ? ? shop=lineArr[1]

? ? ? ? time=float(lineArr[4])*24+float(lineArr[3].split(':')[0])+float(lineArr[3].split(':')[1])/60.0

? ? ? ? if user==exUser:

? ? ? ? ? ? newTuple=[user,exShop,shop,exTime,time]

? ? ? ? ? ? data.append(newTuple)

? ? ? ? ? ? if usernot in observedPOI.keys():

? ? ? ? ? ? ? ? observedPOI[user]={}

? ? ? ? ? ? if exShopnot in observedPOI[user].keys():

? ? ? ? ? ? ? ? observedPOI[user][exShop]=[]

? ? ? ? ? ? observedPOI[user][exShop].append(shop)

? ? ? ? ? ? exShop=shop

exTime=time

else:

? ? ? ? ? ? exUser=user

exShop=shop

exTime=time

fr.close()

? ? return data,observedPOI

def getTestTuple(fileName):

? ? data=[]

? ? exUser=''

? ? exShop=''

? ? exTime=''

? ? fr=open(fileName)

? ? for linein fr.readlines():

? ? ? ? lineArr=line.strip().split('\t')

? ? ? ? user=lineArr[0]

? ? ? ? shop=lineArr[1]

? ? ? ? time=float(lineArr[4])*24+float(lineArr[3].split(':')[0])+float(lineArr[3].split(':')[1])/60.0

? ? ? ? if user==exUser:

? ? ? ? ? ? newTuple=[user,exShop,shop,exTime,time]

? ? ? ? ? ? data.append(newTuple)

? ? ? ? ? ? exShop=shop

exTime=time

else:

? ? ? ? ? ? exUser=user

exShop=shop

exTime=time

fr.close()

? ? return data

def initVec():

? ? userP={}

? ? shopP={}

? ? shopS={}

? ? user=getUser()

? ? shop=getShop()

? ? for itemin user:

? ? ? ? userP[item]=np.random.normal(0,0.01,60)

? ? for itemin shop:

? ? ? ? shopP[item]=np.random.normal(0,0.01,60)

? ? ? ? shopS[item]=np.random.normal(0,0.01,60)

? ? return userP,shopP,shopS

def loadFileWithDic(fileName):

? ? fr=open(fileName,'r')

? ? data={}

? ? i=0

? ? arr=[]

? ? key=''

? ? for linein fr.readlines():

? ? ? ? if i==0:

? ? ? ? ? ? key=line.strip().split('\t')[0]

? ? ? ? ? ? temp=line.strip().split('\t')[1][1:].split(' ')

? ? ? ? ? ? for itemin temp:

? ? ? ? ? ? ? ? if item!='':

? ? ? ? ? ? ? ? ? ? arr.append(float(item))

? ? ? ? ? ? i=1

? ? ? ? else:

? ? ? ? ? ? temp=line.strip().split(' ')

? ? ? ? ? ? for itemin temp:

? ? ? ? ? ? ? ? if item!='' and item!=']':

? ? ? ? ? ? ? ? ? ? if item[-1]==']':

? ? ? ? ? ? ? ? ? ? ? ? arr.append(float(item[:-1]))

? ? ? ? ? ? ? ? ? ? else:

? ? ? ? ? ? ? ? ? ? ? ? arr.append(float(item))

? ? ? ? ? ? if len(arr)==60:

? ? ? ? ? ? ? ? i=0

? ? ? ? ? ? ? ? data[key]=np.array(arr)

? ? ? ? ? ? ? ? arr=[]

? ? fr.close()

? ? return data

def getVisited(fileName):

? ? fr=open(fileName,'r')

? ? visited={}

? ? for linein fr.readlines():

? ? ? ? lineArr=line.strip().split('\t')

? ? ? ? user=lineArr[0]

? ? ? ? shop=lineArr[1]

? ? ? ? if usernot in visited.keys():

? ? ? ? ? ? visited[user]=[]

? ? ? ? if shopnot in visited[user]:

? ? ? ? ? ? visited[user].append(shop)

? ? fr.close()

? ? return visited

def sigmoid(x):

? ? return 1.0/(1.0+np.exp(float(-x)))

def Edis(a,b):

? ? sum=0.0

? ? for iin range(len(a)):

? ? ? ? sum=sum+(a[i]-b[i])*(a[i]-b[i])

? ? return sum

def train():

? ? userP,shopP,shopS=initVec()

? ? data,observedPOI=getTrainTuple('train.txt')

? ? shop=getShop()

? ? for iin range(500):

? ? ? ? print("The "+str(i+1)+" is done!")

? ? ? ? for itemin data:

? ? ? ? ? ? (user,exShop,Cshop,exTime,time)=item

shopJ=shop[int(np.random.uniform(len(shop)))]

? ? ? ? ? ? while shopJ==exShopor shopJin observedPOI[user][exShop]:

? ? ? ? ? ? ? ? shopJ=shop[int(np.random.uniform(len(shop)))]

? ? ? ? ? ? if time-exTime<6:

? ? ? ? ? ? ? ? z=0.2*(Edis(userP[user],shopP[shopJ])-Edis(userP[user],shopP[Cshop]))+0.8*(Edis(shopS[exShop],shopS[shopJ])-Edis(shopS[exShop],shopS[Cshop]))

? ? ? ? ? ? ? ? d=1-sigmoid(z)

? ? ? ? ? ? ? ? userP[user]=userP[user]+0.005*(d*0.4*(shopP[Cshop]-shopP[shopJ])-0.006*userP[user])

? ? ? ? ? ? ? ? shopP[Cshop]=shopP[Cshop]+0.005*(d*0.4*(userP[user]-shopP[Cshop])-0.006*shopP[Cshop])

? ? ? ? ? ? ? ? shopP[shopJ]=shopP[shopJ]+0.005*(d*0.4*(shopP[shopJ]-userP[user])-0.006*shopP[shopJ])

? ? ? ? ? ? ? ? shopS[exShop]=shopS[exShop]+0.005*(d*1.6*(shopS[Cshop]-shopS[shopJ])-0.006*shopS[exShop])

? ? ? ? ? ? ? ? shopS[Cshop]=shopS[Cshop]+0.005*(d*1.6*(shopS[exShop])-shopS[Cshop]-0.006*shopS[Cshop])

? ? ? ? ? ? ? ? shopS[shopJ]=shopS[shopJ]+0.005*(d*1.6*(shopS[shopJ]-shopS[exShop])-0.006*shopS[shopJ])

? ? ? ? ? ? else:

? ? ? ? ? ? ? ? z=Edis(userP[user],shopP[shopJ])-Edis(userP[user],shopP[Cshop])

? ? ? ? ? ? ? ? d=1-sigmoid(z)

? ? ? ? ? ? ? ? userP[user]=userP[user]+0.005*(d*2*(shopP[Cshop]-shopP[shopJ])-0.006*userP[user])

? ? ? ? ? ? ? ? shopP[Cshop]=shopP[Cshop]+0.005*(d*2*(userP[user]-shopP[Cshop])-0.006*shopP[Cshop])

? ? ? ? ? ? ? ? shopP[shopJ]=shopP[shopJ]+0.005*(d*2*(shopP[shopJ]-userP[user])-0.006*shopP[shopJ])

? ? fr=open('userP1000.txt','w')

? ? for keyin userP.keys():

? ? ? ? fr.write(str(key)+'\t'+str(userP[key])+'\n')

? ? fr.close()

? ? fr=open('shopP1000.txt','w')

? ? for keyin shopP.keys():

? ? ? ? fr.write(str(key)+'\t'+str(shopP[key])+'\n')

? ? fr.close()

? ? fr=open('shopS1000.txt','w')

? ? for keyin shopS.keys():

? ? ? ? fr.write(str(key)+'\t'+str(shopS[key])+'\n')

? ? fr.close()

? ? return userP,shopP,shopS

def test():

? ? userP,shopP,shopS=train()

? ? #userP=loadFileWithDic('userP.txt')

#shopS=loadFileWithDic('shopS.txt')

#shopP=loadFileWithDic('shopP.txt')

? ? data=getTestTuple("test.txt")

? ? visited=getVisited("train.txt")

? ? user=getUser()

? ? shop=getShop()

? ? allNum=0

? ? corNum=0

? ? count=0

? ? for itemin data:

? ? ? ? (Cuser,exShop,Cshop,exTime,time)=item

if Cusernot in useror exShopnot in shopor Cshopnot in shopor Cshopin visited[Cuser] or Cshop==exShop:

? ? ? ? ? ? continue

? ? ? ? allNum=allNum+1

? ? ? ? if exShopnot in visited[Cuser]:

? ? ? ? ? ? visited[Cuser].append(exShop)

? ? ? ? poss={}

? ? ? ? count=count+1

? ? ? ? for pShopin shop:

? ? ? ? ? ? if pShopin visited[Cuser] or pShop==exShop:

? ? ? ? ? ? ? ? continue

? ? ? ? ? ? if (time-exTime)<6:

? ? ? ? ? ? ? ? poss[pShop]=0.2*Edis(userP[Cuser],shopP[pShop])+0.8*Edis(shopS[exShop],shopS[pShop])

? ? ? ? ? ? else:

? ? ? ? ? ? ? ? poss[pShop]=Edis(userP[Cuser],shopP[pShop])

? ? ? ? ans=min(poss.items(), key=lambda x: x[1])[0]

? ? ? ? if ans==Cshop:

? ? ? ? ? ? corNum=corNum+1

? ? ? ? ? ? print(str(corNum)+" : "+str(count))

? ? print("The currect rate is "+str((100.0*float(corNum))/float(allNum))+"%.")

def haversine(lon1, lat1, lon2, lat2):

? ? lon1, lat1, lon2, lat2= map(radians, [lon1, lat1, lon2, lat2])

? ? dlon= lon2- lon1

dlat= lat2- lat1

a= sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2

? ? c= 2 * asin(sqrt(a))

? ? r= 6371

? ? return c* r

def getPosition():

? ? fileList=['New/FourSquare/train.txt','New/FourSquare/test.txt','New/FourSquare/tune.txt']

? ? position={}

? ? for fileNamein fileList:

? ? ? ? fr=open(fileName,'r')

? ? ? ? for linein fr.readlines():

? ? ? ? ? ? shop=line.strip().split('\t')[1]

? ? ? ? ? ? if shopnot in position.keys():

? ? ? ? ? ? ? ? lat=float(line.strip().split('\t')[2].split(',')[0])

? ? ? ? ? ? ? ? lon=float(line.strip().split('\t')[2].split(',')[1])

? ? ? ? ? ? ? ? position[shop]={'lat':lat,'lon':lon}

? ? ? ? fr.close()

? ? return position

def trainG():

? ? userP,shopP,shopS=initVec()

? ? data,observedPOI=getTrainTuple('train.txt')

? ? position=getPosition()

? ? shop=getShop()

? ? for iin range(500):

? ? ? ? print("The "+str(i+1)+" is done!")

? ? ? ? for itemin data:

? ? ? ? ? ? (user,exShop,Cshop,exTime,time)=item

shopJ=shop[int(np.random.uniform(len(shop)))]

? ? ? ? ? ? while shopJ==exShopor shopJin observedPOI[user][exShop]:

? ? ? ? ? ? ? ? shopJ=shop[int(np.random.uniform(len(shop)))]

? ? ? ? ? ? if time-exTime<6:

? ? ? ? ? ? ? ? d1=haversine(position[exShop]['lat'],position[exShop]['lon'],position[Cshop]['lat'],position[Cshop]['lon'])

? ? ? ? ? ? ? ? d2=haversine(position[exShop]['lat'],position[exShop]['lon'],position[shopJ]['lat'],position[shopJ]['lon'])

? ? ? ? ? ? ? ? w1=pow(1+d1,0.25)

? ? ? ? ? ? ? ? w2=pow(1+d2,0.25)

? ? ? ? ? ? ? ? z=0.2*(w2*Edis(userP[user],shopP[shopJ])-w1*Edis(userP[user],shopP[Cshop]))+0.8*(w2*Edis(shopS[exShop],shopS[shopJ])-w1*Edis(shopS[exShop],shopS[Cshop]))

? ? ? ? ? ? ? ? d=1-sigmoid(z)

? ? ? ? ? ? ? ? userP[user]=userP[user]+0.005*(d*0.4*(w1*shopP[Cshop]-w2*shopP[shopJ])-0.006*userP[user])

? ? ? ? ? ? ? ? shopP[Cshop]=shopP[Cshop]+0.005*(d*0.4*w1*(userP[user]-shopP[Cshop])-0.006*shopP[Cshop])

? ? ? ? ? ? ? ? shopP[shopJ]=shopP[shopJ]+0.005*(d*0.4*w2*(shopP[shopJ]-userP[user])-0.006*shopP[shopJ])

? ? ? ? ? ? ? ? shopS[exShop]=shopS[exShop]+0.005*(d*1.6*(w1*shopS[Cshop]-w2*shopS[shopJ])-0.006*shopS[exShop])

? ? ? ? ? ? ? ? shopS[Cshop]=shopS[Cshop]+0.005*(d*1.6*w1*(shopS[exShop])-shopS[Cshop]-0.006*shopS[Cshop])

? ? ? ? ? ? ? ? shopS[shopJ]=shopS[shopJ]+0.005*(d*1.6*w2*(shopS[shopJ]-shopS[exShop])-0.006*shopS[shopJ])

? ? ? ? ? ? else:

? ? ? ? ? ? ? ? z=Edis(userP[user],shopP[shopJ])-Edis(userP[user],shopP[Cshop])

? ? ? ? ? ? ? ? d=1-sigmoid(z)

? ? ? ? ? ? ? ? userP[user]=userP[user]+0.005*(d*2*(shopP[Cshop]-shopP[shopJ])-0.006*userP[user])

? ? ? ? ? ? ? ? shopP[Cshop]=shopP[Cshop]+0.005*(d*2*(userP[user]-shopP[Cshop])-0.006*shopP[Cshop])

? ? ? ? ? ? ? ? shopP[shopJ]=shopP[shopJ]+0.005*(d*2*(shopP[shopJ]-userP[user])-0.006*shopP[shopJ])

? ? fr=open('userP.txt','w')

? ? for keyin userP.keys():

? ? ? ? fr.write(str(key)+'\t'+str(userP[key])+'\n')

? ? fr.close()

? ? fr=open('shopP.txt','w')

? ? for keyin shopP.keys():

? ? ? ? fr.write(str(key)+'\t'+str(shopP[key])+'\n')

? ? fr.close()

? ? fr=open('shopS.txt','w')

? ? for keyin shopS.keys():

? ? ? ? fr.write(str(key)+'\t'+str(shopS[key])+'\n')

? ? fr.close()

? ? return userP,shopP,shopS

def testG():

? ? userP,shopP,shopS=trainG()

? ? #userP=loadFileWithDic('userP.txt')

#shopS=loadFileWithDic('shopS.txt')

#shopP=loadFileWithDic('shopP.txt')

? ? data=getTestTuple("test.txt")

? ? visited=getVisited("train.txt")

? ? user=getUser()

? ? shop=getShop()

? ? allNum=0

? ? corNum=0

? ? count=0

? ? for itemin data:

? ? ? ? (Cuser,exShop,Cshop,exTime,time)=item

if Cusernot in useror exShopnot in shopor Cshopnot in shopor Cshopin visited[Cuser] or Cshop==exShop:

? ? ? ? ? ? continue

? ? ? ? allNum=allNum+1

? ? ? ? if exShopnot in visited[Cuser]:

? ? ? ? ? ? visited[Cuser].append(exShop)

? ? ? ? poss={}

? ? ? ? count=count+1

? ? ? ? for pShopin shop:

? ? ? ? ? ? if pShopin visited[Cuser] or pShop==exShop:

? ? ? ? ? ? ? ? continue

? ? ? ? ? ? if (time-exTime)<6:

? ? ? ? ? ? ? ? d=haversine(position[exShop]['lat'],position[exShop]['lon'],position[pshop]['lat'],position[pshop]['lon'])

? ? ? ? ? ? ? ? w=pow(1+d1,0.25)

? ? ? ? ? ? ? ? poss[pShop]=w*(0.2*Edis(userP[Cuser],shopP[pShop])+0.8*Edis(shopS[exShop],shopS[pShop]))

? ? ? ? ? ? else:

? ? ? ? ? ? ? ? poss[pShop]=Edis(userP[Cuser],shopP[pShop])

? ? ? ? ans=min(poss.items(), key=lambda x: x[1])[0]

? ? ? ? if ans==Cshop:

? ? ? ? ? ? corNum=corNum+1

? ? ? ? ? ? print(str(corNum)+" : "+str(count))

? ? print("The currect rate is "+str((100.0*float(corNum))/float(allNum))+"%.")

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末究驴，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子匀伏，更是在濱河造成了極大的恐慌洒忧，老刑警劉巖，帶你破解...
    沈念sama閱讀 212,884評(píng)論 6贊 492
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件够颠，死亡現(xiàn)場(chǎng)離奇詭異熙侍，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)履磨，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,755評(píng)論 3贊 385
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門蛉抓，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人剃诅，你說我怎么就攤上這事巷送。” “怎么了矛辕？”我有些...
    開封第一講書人閱讀 158,369評(píng)論 0贊 348
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵惩系，是天一觀的道長(zhǎng)。 經(jīng)常有香客問我如筛，道長(zhǎng)堡牡，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 56,799評(píng)論 1贊 285
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任杨刨，我火速辦了婚禮晤柄，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘妖胀。我一直安慰自己芥颈，他們只是感情好，可當(dāng)我...
    茶點(diǎn)故事閱讀 65,910評(píng)論 6贊 386
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布赚抡。 她就那樣靜靜地躺著爬坑，像睡著了一般。 火紅的嫁衣襯著肌膚如雪涂臣。 梳的紋絲不亂的頭發(fā)上盾计，一...
    開封第一講書人閱讀 50,096評(píng)論 1贊 291
  • 城市分裂傳說
    那天，我揣著相機(jī)與錄音赁遗，去河邊找鬼署辉。 笑死，一個(gè)胖子當(dāng)著我的面吹牛岩四，可吹牛的內(nèi)容都是我干的哭尝。 我是一名探鬼主播，決...
    沈念sama閱讀 39,159評(píng)論 3贊 411
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼剖煌，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼材鹦！你這毒婦竟也來了逝淹？” 一聲冷哼從身側(cè)響起，我...
    開封第一講書人閱讀 37,917評(píng)論 0贊 268
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對(duì)情侶失蹤桶唐，失蹤者是張志新（化名）和其女友劉穎创橄，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體莽红，經(jīng)...
    沈念sama閱讀 44,360評(píng)論 1贊 303
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡妥畏，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,673評(píng)論 2贊 327
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了安吁。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片醉蚁。...
    茶點(diǎn)故事閱讀 38,814評(píng)論 1贊 341
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖鬼店，靈堂內(nèi)的尸體忽然破棺而出网棍，到底是詐尸還是另有隱情，我是刑警寧澤妇智，帶...
    沈念sama閱讀 34,509評(píng)論 4贊 334
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布滥玷，位于F島的核電站，受9級(jí)特大地震影響巍棱，放射性物質(zhì)發(fā)生泄漏惑畴。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 40,156評(píng)論 3贊 317
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一航徙、第九天 我趴在偏房一處隱蔽的房頂上張望如贷。 院中可真熱鬧，春花似錦到踏、人聲如沸杠袱。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,882評(píng)論 0贊 21
  • 一樁弒父案窝稿，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽楣富。三九已至，卻和暖如春伴榔，著一層夾襖步出監(jiān)牢的瞬間纹蝴，已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,123評(píng)論 1贊 267
  • 情欲美人皮
    我被黑心中介騙來泰國(guó)打工潮梯， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留骗灶，地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 46,641評(píng)論 2贊 362
  • 代替公主和親
    正文 我出身青樓秉馏，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親脱羡。 傳聞我的和親對(duì)象是個(gè)殘疾皇子萝究，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,728評(píng)論 2贊 351

推薦閱讀更多精彩內(nèi)容