[發(fā)明專利]基于地理位置的興趣點(diǎn)團(tuán)推薦方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201610113281.0
• 申請(qǐng)日: 2016-03-01
• 公開(kāi)（公告）號(hào): CN105653736B
• 公開(kāi)（公告）日: 2019-11-15
• 發(fā)明（設(shè)計(jì)）人: 王勝靈;孟祥恒
• 申請(qǐng)（專利權(quán)）人: 北京師范大學(xué)
• 主分類號(hào): G06F16/29
• 分類號(hào): G06F16/29;G01C21/34
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

本發(fā)明屬于基于地理位置的服務(wù)推薦領(lǐng)域，其特征在于可以按照用戶需求通過(guò)一次請(qǐng)求返回多個(gè)類型點(diǎn)，形成組合推薦。依次含有以下步驟：第一步：先用一條掃描線從右至左進(jìn)行掃描，在掃描過(guò)程中通過(guò)找到每個(gè)點(diǎn)的可視點(diǎn)并連線，從而構(gòu)成整個(gè)網(wǎng)絡(luò)的可視網(wǎng)。第二步：利用遞歸的思想，從最簡(jiǎn)單的單點(diǎn)結(jié)構(gòu)構(gòu)造2?異構(gòu)點(diǎn)團(tuán)，這樣依次可以得到(N?1)?異構(gòu)點(diǎn)團(tuán)。為了減少不必要的匹配，提出L層臨近點(diǎn)的概念，即在進(jìn)行匹配的時(shí)候只考慮與當(dāng)前點(diǎn)臨近的一些點(diǎn)團(tuán)。在這一步得到G_N?1，其包含(N?1)?異構(gòu)點(diǎn)團(tuán)。第三步：有了前面的鋪墊，在這一步中形成備選的N?異構(gòu)點(diǎn)團(tuán)，通過(guò)比較排序，始終只保留前K個(gè)最優(yōu)的組合，得到最終的集合B，包含最優(yōu)的K個(gè)組合，返回給用戶。

技術(shù)領(lǐng)域

基于地理位置的興趣點(diǎn)推薦服務(wù)領(lǐng)域。

背景技術(shù)

基于位置的服務(wù)(LBSs)在我們的生活中正變?yōu)樵絹?lái)越重要的一部分，所有現(xiàn)存的LBS提供商都支持臨近興趣點(diǎn)的查找。在這種典型的LBS中，用戶提交當(dāng)前位置和感興趣的興趣點(diǎn)給服務(wù)器，服務(wù)器返回給用戶一些臨近的滿足用戶要求的興趣點(diǎn)，供用戶參考選擇。但是在實(shí)際生活中人們通常不只訪問(wèn)一個(gè)興趣點(diǎn)，而是連續(xù)的去多個(gè)不同的地方，比如一個(gè)人在吃完晚飯后會(huì)想去看電影，在這種情形下，用戶希望得到一個(gè)點(diǎn)對(duì)(餐館和電影院的組合)，要求這兩個(gè)點(diǎn)分別都有著較高的評(píng)價(jià)，同時(shí)在地理位置上是臨近的，方便從一個(gè)地方轉(zhuǎn)移到另一個(gè)地方。

為了滿足這樣的用戶應(yīng)用需求，我們提出一種名為“多合一”的LBS查詢方法，它對(duì)原有的LBS服務(wù)進(jìn)行擴(kuò)展，支持異構(gòu)的興趣點(diǎn)(Point of Interest，POI)請(qǐng)求。在“N-in-One”中，一個(gè)用戶允許查詢N類位置相關(guān)的同時(shí)類型各異的興趣點(diǎn)，而且僅僅通過(guò)一次請(qǐng)求。服務(wù)器進(jìn)行運(yùn)算后，返回給用戶一個(gè)點(diǎn)團(tuán)集合。提供“N-in-One”服務(wù)具有挑戰(zhàn)，“N-in-One”服務(wù)不等同于N次單一類型的服務(wù)，因?yàn)橐紤]N個(gè)點(diǎn)的位置相關(guān)性和由此帶來(lái)的時(shí)間和空間復(fù)雜度問(wèn)題。為了克服這些挑戰(zhàn)，我們利用計(jì)算幾何學(xué)的技術(shù)提出一種新的方法，從而較好地實(shí)現(xiàn)了上述目的。而如何快速準(zhǔn)確地計(jì)算出最優(yōu)的K個(gè)N-異構(gòu)點(diǎn)團(tuán)是本發(fā)明所研究的重點(diǎn)。

發(fā)明內(nèi)容

本發(fā)明的目的在于提供了一種快速準(zhǔn)確查詢當(dāng)前位置附近最優(yōu)的一些異構(gòu)點(diǎn)團(tuán)的方法，從而實(shí)現(xiàn)組合查詢的目的。

本發(fā)明的特征在于，它依次含有以下步驟：

步驟(1.)：根據(jù)興趣點(diǎn)的分布，構(gòu)建可視網(wǎng)。一個(gè)可視網(wǎng)定義為N＝(E，Ω)，其中Ω表示區(qū)域內(nèi)所有興趣點(diǎn)構(gòu)成的集合，E表示可視線的集合，其中可視線是每個(gè)興趣點(diǎn)和其可視點(diǎn)的連線。對(duì)于任意一個(gè)興趣點(diǎn)Pi其可視點(diǎn)為Pi朝向掃描線移動(dòng)方向的反方向能直接看到，即不被任何其他興趣點(diǎn)或可視線阻隔的點(diǎn)。例如在圖1中，P5的可視點(diǎn)是P6和P7，而由于P8、P9、P10被線段擋住所以不是P5的可視點(diǎn)。可視網(wǎng)的構(gòu)建可分為下面幾個(gè)過(guò)程：

步驟(1.1.)：聲明并定義各個(gè)變量。首先定義興趣點(diǎn)，即某一區(qū)域內(nèi)指定類別的地點(diǎn)，如飯店、電影院、ATM機(jī)、咖啡廳等，每個(gè)興趣點(diǎn)有其橫縱坐標(biāo)和綜合評(píng)分(0-5)屬性，設(shè)區(qū)域內(nèi)共有n個(gè)興趣點(diǎn){P₁，P₂…，P_n-1，P_n}；V表示已掃描過(guò)的點(diǎn)集合；Conv(V)表示V的凸包，而C^P(V)則表示Conv(V)∩V；C^E(V)表示Conv(V)上的線段，表示可視線的集合。

步驟(1.2.)：掃描線l從右向左掃描，掃描最右面的三個(gè)點(diǎn)，初始化各變量。把這三個(gè)點(diǎn)保存在V中，即V←{P_n，P_n-1，P_n-2}，其他變量C^P(V)＝{P_n，P_n-1，P_n-2}，E←E∪C^E(V)。

步驟(1.3.)：完成初始化后，對(duì)于i＝n-2，n-3，…，1，0，重復(fù)以下步驟：