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

有效

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

1.一種新型基于地理位置 的多重興趣點(diǎn)搜索方法，其特征在于，該方法依次含有以下步驟：

步驟(1.):根據(jù)興趣點(diǎn)的分布，構(gòu)建可視網(wǎng)，一個可視網(wǎng)N＝(E,Ω)這樣進(jìn)行表示，其中Ω表示區(qū)域內(nèi)所有興趣點(diǎn)構(gòu)成的集合，E表示可視線的集合，其中可視線是每個興趣點(diǎn)和其可視點(diǎn)的連線，對于任意一個興趣點(diǎn)P_i其可視點(diǎn)為P_i朝向掃描線移動方向的反方向能直接看到，即不被任何其他興趣點(diǎn)或可視線阻隔的點(diǎn)；

可視網(wǎng)的構(gòu)建可分為下面幾個過程：

步驟(1.1.):聲明并定義各個變量，首先定義興趣點(diǎn)，即某一區(qū)域內(nèi)指定類別的地點(diǎn)，每個興趣點(diǎn)有其橫縱坐標(biāo)和綜合評分(0-5)屬性，設(shè)區(qū)域內(nèi)共有n個興趣點(diǎn){P₁,P₂,...,P_n-1,P_n}；V表示已掃描過的點(diǎn)集合；Conv(V)表示V的凸包，而C^P(V)則表示Conv(V)∩V；C^E(V)表示Conv(V)上的線段，表示可視線的集合；

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

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

步驟(1.3.1.):當(dāng)掃描線掃描到興趣點(diǎn)P_i時，找到其可視點(diǎn)集合

步驟(1.3.2.):根據(jù)上一步得到的可視點(diǎn)，與P_i相連可更新可是線段集合E，即

步驟(1.3.3.):將P_i加入V中，即V←V∪{P_i}；

步驟(1.3.4.):更新C^P(V)和C^E(V)；

步驟(2.)：在構(gòu)建可視網(wǎng)后，再次使用掃描線從右向左掃描，當(dāng)掃描到興趣點(diǎn)P_i時，要回溯其L層臨近點(diǎn)來構(gòu)成新的點(diǎn)團(tuán)，在步驟2.2給出了L層臨近點(diǎn)的定義，在這里采用一種遞歸的思想，該方法的最終目的是尋找最優(yōu)的一些點(diǎn)團(tuán)，其中每個點(diǎn)團(tuán)包含N個不同類型的興趣點(diǎn)，稱之為N-異構(gòu)點(diǎn)團(tuán)，為了尋找N-異構(gòu)點(diǎn)團(tuán)，可以從(N-1)—異構(gòu)點(diǎn)團(tuán)來組合得到，從而可以把問題歸結(jié)到1—異構(gòu)點(diǎn)團(tuán)的尋找，通過這樣一種降低問題復(fù)雜度的方法來解決問題，具體步驟如下：

步驟(2.1.):初始化，從最基本的1—異構(gòu)點(diǎn)團(tuán)入手，通過掃描得到G₁，其含有所有1—異構(gòu)點(diǎn)團(tuán)；

步驟(2.2.):給出遞歸的一般過程，從G_j-1得到G_j，定義L_i，P_i的L-層臨近點(diǎn)是那些在P_i前已經(jīng)被掃描過的，同時是從P_i出發(fā)最多可以通過L條可視線可以到達(dá)的點(diǎn)，為了從G_j-1得到G_j，點(diǎn)團(tuán)集合S_i,j-1需要得到，其每個元素包含j-1個異構(gòu)的興趣點(diǎn)，且都是來自P_i的L-層臨近點(diǎn)；然后檢查S_i,j-1中的每個(j-1)—異構(gòu)點(diǎn)團(tuán)是否包含和P_i相同類型的點(diǎn)，如果不存在，P_i和該點(diǎn)團(tuán)組合構(gòu)成一個j—異構(gòu)點(diǎn)團(tuán)并加入到G_j，這樣一直掃描到最后一個點(diǎn)，重復(fù)該過程，從而得到G_j；

步驟(2.3.):通過步驟2.1和步驟2.2構(gòu)造的遞歸方法，可以得到G_N-1，即(N-1)-異構(gòu)點(diǎn)團(tuán)集合，作為第3個步驟的輸入；

步驟(3.):經(jīng)過前面的過程，得到了可視網(wǎng)E，G_N-1和P_i的L-層臨近點(diǎn)L_i，這些變量將作為這一步的輸入，來得到最終的算法結(jié)果即最優(yōu)的K個N-異構(gòu)點(diǎn)團(tuán)，既然要選最優(yōu)的，必然要有一個標(biāo)準(zhǔn)對不同的點(diǎn)團(tuán)進(jìn)行比較評價；

對于一個點(diǎn)團(tuán)，其包含了N個異構(gòu)的點(diǎn)，考慮到每個點(diǎn)的位置和綜合評分，以及這些點(diǎn)的拓?fù)浣Y(jié)構(gòu)，制定出下面的準(zhǔn)則給一個點(diǎn)團(tuán)評分

Π表示一個N-異構(gòu)點(diǎn)團(tuán)，R(Π)表示這個點(diǎn)團(tuán)的評分，一個點(diǎn)團(tuán)的評分由3部分構(gòu)成，α,β,γ分別代表著3部分的權(quán)重，第一部分反映的是每個興趣點(diǎn)的評分的影響，e_j是P_j的評分，根據(jù)不同的類型不同的興趣點(diǎn)可以有各自的評分體系；第二部分反映的是點(diǎn)團(tuán)中個點(diǎn)的離散程度，其中是點(diǎn)團(tuán)的直徑，決定Π中兩個興趣點(diǎn)之間的轉(zhuǎn)移距離，一個點(diǎn)團(tuán)越集中，則興趣點(diǎn)之間的轉(zhuǎn)移時間消耗越少；第三部分d(Π,c)反映了點(diǎn)團(tuán)和當(dāng)前用戶位置c的距離，距離越近，用戶越能更快的到達(dá)目的地；

在步驟3中仍然采用掃描線的方法，掃描線從右至左進(jìn)行掃描，對于從第n-N+1的每一個點(diǎn)p_i，采取以下的幾個步驟：

步驟(3.1.):任意C_m∈G_N-1，如果則S_i,N-1←S_i,N-1∪C_m，得到S_i,N-1；

步驟(3.2.):任意C_m∈S_i,N-1，如果P_i與C_m中所有興趣點(diǎn)的類型都不相同，則P_i和C_m可以組合構(gòu)成一個N-異構(gòu)點(diǎn)團(tuán)，將這個新得到的{P_i,C_m}加入B中，B存儲當(dāng)前入選最優(yōu)的前K個組合，如果此時B中不夠K個，則直接插入后按照點(diǎn)團(tuán)評分升序排序，如果已經(jīng)達(dá)到K個點(diǎn)團(tuán)，則跟B中評分最低點(diǎn)團(tuán)s比較，如果高于s，則刪去s將當(dāng)前得到的點(diǎn)團(tuán)插入后再升序排序，這樣一直掃描到最左面的點(diǎn)p₁，從而得到最終的集合B，其中保存了最優(yōu)的K個異構(gòu)點(diǎn)團(tuán)組合。