基于用戶軌跡數(shù)據(jù)的用戶興趣區(qū)域推薦(云南大學(xué)信息學(xué)院，云南 昆明 650504)
2019-12-06 06:25:15龍玉絨王麗珍陳紅梅
軟件工程 2019年11期
龍玉絨 王麗珍 陳紅梅
摘? 要：推薦系統(tǒng)是通過分析已知信息和用戶偏好，在用戶選擇物品或服務(wù)時(shí)，向用戶提供幫助和建議的系統(tǒng)。但是目前大部分推薦系統(tǒng)都是基于用戶評(píng)價(jià)或評(píng)分信息向用戶推薦購(gòu)物、電影等電子商務(wù)服務(wù)，基于用戶軌跡數(shù)據(jù)進(jìn)行用戶興趣區(qū)域推薦的研究十分罕見。用戶的軌跡數(shù)據(jù)蘊(yùn)含了用戶的偏好，不同的軌跡反映不同的用戶特性。所以提出一種從用戶軌跡數(shù)據(jù)中挖掘最大頻繁項(xiàng)集，并將最大頻繁項(xiàng)集用于計(jì)算用戶相似性和偏好的推薦方法。該推薦方法還綜合考慮了相似用戶訪問次數(shù)、置信度和用戶住宅信息等可能會(huì)影響推薦質(zhì)量的因素。將提出的方法和基于協(xié)同過濾的推薦方法、基于關(guān)聯(lián)規(guī)則的推薦方法進(jìn)行比較，結(jié)果顯示本文提出方法的效果較好。
關(guān)鍵詞：軌跡數(shù)據(jù)挖掘;區(qū)域推薦;相似用戶;頻繁項(xiàng)集
中圖分類號(hào)：TP391? ? ?文獻(xiàn)標(biāo)識(shí)碼：A
User Interest Region Recommendation Based on User Trajectory Data
LONG Yurong，WANG Lizhen，CHEN Hongmei
（School of Information Science and Engineering，Yunnan University，Kunming 650504，China）
Abstract：A recommendation system is a system which provides help and advice to users by analyzing the existing information and users' preferences when users choose goods or services.However，most recommendation systems recommend shopping，movies and other e-commerce services to users based on user evaluation or scoring information.It is very rare to conduct research on user interest region recommendation based on user trajectory data.User's trajectory data contains users different preference，reflecting different user characteristics.Therefore，it is? necessary to make recommendations based on user trajectory data.This paper presents an interest region recommendation method，which calculates user similarity and preference by mining maximum frequent itemsets from user trajectory data.We take into account three factors，including numbers of similar user visits，confidence and user residence information.In the paper，the proposed method is compared with the recommendation algorithm based on collaborative filtering and the recommendation algorithm based on association rules，and the results show that the proposed method is effective.
Keywords：trajectory data mining;region recommendation;similar users;frequent itemset
1? ?引言（Introduction）
近年來，基于位置的社交網(wǎng)絡(luò)[1]十分流行，用戶可以將他們的活動(dòng)軌跡數(shù)據(jù)或者訪問的地點(diǎn)在網(wǎng)絡(luò)上進(jìn)行共享，這些數(shù)據(jù)都帶有位置信息。推薦系統(tǒng)[2-4]可以運(yùn)用于此類數(shù)據(jù)。Berjani B[5]、Hu L[6]和Liu Y[7]等人均是利用社交數(shù)據(jù)進(jìn)行位置推薦。但是，現(xiàn)有的位置推薦方法大體有如下不足：
（1）數(shù)據(jù)多為用戶簽到數(shù)據(jù)，蘊(yùn)含信息單一，不能準(zhǔn)確評(píng)估用戶偏好。
（2）向用戶推薦的是一個(gè)興趣點(diǎn)而不是一個(gè)興趣區(qū)域。
（3）對(duì)用戶進(jìn)行相似性評(píng)估時(shí)，需要用戶的評(píng)分信息。
針對(duì)上述問題，本文提出了一種從用戶軌跡數(shù)據(jù)中挖掘最大頻繁項(xiàng)集，并基于最大頻繁項(xiàng)集計(jì)算用戶相似性和偏好用于興趣區(qū)域推薦的方法。
本文主要貢獻(xiàn)包括：
（1）不需要用戶的評(píng)分信息，從用戶軌跡數(shù)據(jù)轉(zhuǎn)化得到的事務(wù)數(shù)據(jù)中挖掘最大頻繁項(xiàng)集，基于最大頻繁項(xiàng)集定義用戶相似性。
（2）提出一種不產(chǎn)生候選模式，只需要掃描兩次數(shù)據(jù)庫的頻繁項(xiàng)集挖掘方法。
（3）提出一種考慮了相似用戶訪問次數(shù)、置信度和住宅信息三種因素的用戶興趣區(qū)域推薦方法，該方法能更準(zhǔn)確地進(jìn)行用戶興趣區(qū)域推薦。
2? ?定義（Definition）
基于用戶軌跡數(shù)據(jù)進(jìn)行用戶興趣區(qū)域推薦的算法中，主要的挑戰(zhàn)是相似用戶的度量及用戶興趣區(qū)域推薦。本節(jié)首先對(duì)停留區(qū)域和停留區(qū)域間的鄰近關(guān)系進(jìn)行定義，用于將軌跡數(shù)據(jù)轉(zhuǎn)化為事務(wù)數(shù)據(jù)。其次給出相似用戶的定義及推薦得分的定義，最后給出本文的問題定義。
設(shè)I={i1，i2，i3，..，in}是項(xiàng)的集合，則稱為項(xiàng)集，K=|X|，X稱為K項(xiàng)集。事務(wù)是事務(wù)數(shù)據(jù)庫中的一條記錄，代表發(fā)生的一次事件。數(shù)據(jù)庫D={T1，T2，T3，...，Tm}是事務(wù)的集合，稱為事務(wù)數(shù)據(jù)庫。支持度計(jì)數(shù)是指包含特定項(xiàng)集的事務(wù)個(gè)數(shù)。頻繁項(xiàng)集是指在事務(wù)數(shù)據(jù)D中出現(xiàn)的頻率大于支持度計(jì)數(shù)閾值的項(xiàng)集。如果頻繁項(xiàng)集L的所有超集都是非頻繁的，那么頻繁項(xiàng)集L為最大頻繁項(xiàng)集。
例1：如表1所示，S001是項(xiàng)，{S001，S003}是一個(gè)項(xiàng)集，TID：T001是一個(gè)事務(wù)。D={T001，T002，T003}是事務(wù)數(shù)據(jù)庫。{S001，S003}的支持度計(jì)數(shù)為：1，因?yàn)橹挥幸粭l事務(wù)包含{S001，S003}。
定義1（數(shù)據(jù)點(diǎn)描述）
定義2（軌跡數(shù)據(jù)）軌跡數(shù)據(jù)是由許多數(shù)據(jù)點(diǎn)按時(shí)間順序組成的一個(gè)數(shù)據(jù)點(diǎn)序列。
定義3（停留區(qū)域）停留區(qū)域是指用戶軌跡數(shù)據(jù)中移動(dòng)速度低于平均速度或某個(gè)用戶給定的速度閾值的區(qū)域。
例2：如圖1所示，圖中給出用戶A的一條軌跡數(shù)據(jù)P={p1，p2，p3，p4，p5，p6，p7}。如果用戶A在點(diǎn)p3、p4、p5、p6區(qū)域內(nèi)的移動(dòng)速度小于一個(gè)給定的速度閾值，例如30米/分鐘，那么區(qū)域A1：{p3，p4，p5，p6}是用戶A的一個(gè)停留區(qū)域。
本文定義停留區(qū)域是為了對(duì)用戶的軌跡數(shù)據(jù)進(jìn)行預(yù)處理，將軌跡數(shù)據(jù)中對(duì)推薦沒有價(jià)值的數(shù)據(jù)忽略。由于我們擬推薦的是用戶可能訪問的興趣區(qū)域，所以我們只關(guān)注用戶長(zhǎng)時(shí)間停留或移動(dòng)速度較慢的區(qū)域，即停留區(qū)域。假設(shè)用戶A在區(qū)域B1內(nèi)的速度為600米/分鐘。我們只認(rèn)為用戶A經(jīng)過了區(qū)域B1，并不認(rèn)為A訪問了區(qū)域B1。
定義4（鄰近關(guān)系）假設(shè)有兩個(gè)停留區(qū)域A1和B2，如果兩個(gè)停留區(qū)域的最小外包矩形有重疊時(shí)，我們稱停留區(qū)域A1和B2具有鄰近關(guān)系。
圖1 停留區(qū)域
Fig.1 Stay region
圖2 鄰近關(guān)系
Fig.2 Proximity relationship
本文定義停留區(qū)域間的鄰近關(guān)系是為了確定用戶興趣區(qū)域的位置相關(guān)性，并確定訪問過相關(guān)區(qū)域的用戶。已知停留區(qū)域集：SR={A1，A2，B1，B2，C3}。通過計(jì)算確定A1、B2、C3具有鄰近關(guān)系，可以確定訪問了鄰近區(qū)域的用戶A、B、C具有一定的訪問相似性。
例3：如圖2所示，根據(jù)定義4，A1、B2和C3是相互鄰近的停留區(qū)域，對(duì)于這樣的相互鄰近的停留區(qū)域，我們可以確定一個(gè)用戶興趣區(qū)域S，用戶興趣區(qū)域S為A1、B2和C3三者最小外包矩形并集的最小外包矩形，圖2中虛線的矩形就是用戶興趣區(qū)域S。并且確定用戶A、B、C訪問過該區(qū)域。我們將其轉(zhuǎn)化為一條事務(wù)：TID為S，項(xiàng)集為{A，B，C}。表示興趣區(qū)域S被用戶A、B、C訪問過。
根據(jù)上述的定義，我們可以將用戶的軌跡數(shù)據(jù)轉(zhuǎn)化為兩類事務(wù)數(shù)據(jù)集，一類事務(wù)數(shù)據(jù)TID為用戶興趣區(qū)域，項(xiàng)集為用戶，如表2所示為一個(gè)可能的“興趣區(qū)域—用戶”事務(wù)數(shù)據(jù)集，其中TID為用戶興趣區(qū)域的編號(hào)，項(xiàng)集為訪問過該區(qū)域的用戶。例如第一條事務(wù)表示用戶{A，B，C，F(xiàn)，H}訪問過用戶興趣區(qū)域S001。第二類事務(wù)數(shù)據(jù)TID為用戶，項(xiàng)集為用戶訪問過的興趣區(qū)域，如表3所示為一個(gè)可能的“用戶—興趣區(qū)域”事務(wù)數(shù)據(jù)集。例如第一條數(shù)據(jù)表示用戶A訪問過興趣區(qū)域S001、S003、S005。
我們從第一類事務(wù)數(shù)據(jù)集中挖掘最大頻繁項(xiàng)集，其中項(xiàng)為用戶，包含在最大頻繁項(xiàng)集中的用戶都是頻繁訪問過相同的興趣區(qū)域的用戶，在一定程度上這些用戶的興趣區(qū)域是相似的，于是認(rèn)為用戶偏好也是相似的。所以不需要用戶評(píng)分?jǐn)?shù)據(jù)，我們可以定義相似用戶。
定義5（相似用戶）假設(shè)L為一個(gè)最大的頻繁項(xiàng)集，我們稱屬于L的用戶為相似用戶，其相似性為1，表示為：
其中ui、uj分別表示兩個(gè)用戶。
我們知道，關(guān)聯(lián)規(guī)則X1X2表示項(xiàng)集之間的關(guān)聯(lián)關(guān)系。規(guī)則置信度是指項(xiàng)集X1出現(xiàn)的情況下項(xiàng)集X2出現(xiàn)的概率。我們將其運(yùn)用到推薦得分的定義中。
定義6（推薦得分）給定一個(gè)待推薦的用戶興趣區(qū)域S，Score（s）表示待推薦用戶興趣區(qū)域S的推薦得分，Score（s）的計(jì)算如下：
其中，為相關(guān)規(guī)則置信度，vt為該用戶興趣區(qū)域被相似用戶訪問的次數(shù)，d表示用戶住宅區(qū)與該用戶興趣區(qū)域的距離。
為何要如此定義推薦得分？
從二類事務(wù)數(shù)據(jù)中可挖掘出項(xiàng)為用戶興趣區(qū)域的頻繁項(xiàng)集?？紤]規(guī)則置信度是為了推薦頻繁項(xiàng)集中的用戶興趣區(qū)域。規(guī)則置信度表示該用戶在訪問過其他頻繁項(xiàng)集的情況下訪問待推薦用戶興趣區(qū)域的概率，規(guī)則置信度越高，用戶訪問該用戶興趣區(qū)域的概率越大。假設(shè)用戶興趣區(qū)域{S1，S2，S3}是頻繁項(xiàng)集，用戶A訪問過用戶興趣區(qū)域S1和S2，將用戶興趣區(qū)域S3推薦給A時(shí)，需要考慮規(guī)則{S1，S2}{S3}的置信度?？紤]相似用戶的訪問次數(shù)是為了將相似用戶偶然訪問的用戶興趣區(qū)域排除，并且用戶興趣區(qū)域被相似用戶訪問的次數(shù)越多，說明該用戶興趣區(qū)域?qū)@類用戶的吸引力越大。考慮用戶住宅區(qū)和推薦用戶興趣區(qū)域之間的距離是因?yàn)橥扑]時(shí)離用戶住宅區(qū)距離較近的用戶興趣區(qū)域更有可能被該用戶訪問。
問題定義（基于用戶軌跡數(shù)據(jù)的用戶興趣區(qū)域推薦）給定用戶軌跡數(shù)據(jù)集{PA，PB，PC，...，Pk}，支持度計(jì)數(shù)閾值。向用戶推薦top-n個(gè)最有可能訪問的用戶興趣區(qū)域。
3? ?算法（Algorithm）
在這一部分，將介紹我們提出的兩個(gè)算法：基本算法basic_algorithm和改進(jìn)算法improved_algorithm。basic_algorithm算法挖掘頻繁項(xiàng)集時(shí)運(yùn)用的是類apriori方法。由于基本算法在計(jì)算停留區(qū)域間鄰近關(guān)系時(shí)，算法時(shí)間復(fù)雜度較高，挖掘頻繁項(xiàng)集時(shí)需要多次掃描數(shù)據(jù)庫、產(chǎn)生大量的候選，所以提出改進(jìn)算法：improved_algorithm。改進(jìn)算法將網(wǎng)格劃分運(yùn)用到鄰近關(guān)系的計(jì)算中減少不必要的計(jì)算，減少時(shí)間的耗費(fèi)。同時(shí)，改進(jìn)算法在挖掘頻繁項(xiàng)集時(shí)提出一種不需要多次掃描數(shù)據(jù)庫、不產(chǎn)生候選模式的挖掘方法。
3.1? ?基本算法：basic_algorithm
首先介紹基本算法basic-algorithm，基本算法中挖掘頻繁項(xiàng)集運(yùn)用的是類apriori[8]方法。
算法1：basic-algorithm
輸入：用戶的軌跡數(shù)據(jù);top-n的n值;頻繁項(xiàng)集支持度計(jì)數(shù)閾值sup。
輸出：推薦給用戶的top-n個(gè)用戶興趣區(qū)域。
變量：SRS：用戶停留區(qū)域集;D：事務(wù)集;PIS：“興趣區(qū)域—用戶”事務(wù)數(shù)據(jù)（項(xiàng)為用戶）的最大頻繁項(xiàng)集;RPIS：“用戶—興趣區(qū)域”事務(wù)數(shù)據(jù)（項(xiàng)為興趣區(qū)域）的頻繁項(xiàng)集;Fk：k階頻繁項(xiàng)集;Ck：k階頻繁項(xiàng)集候選;SUS：相似用戶集;Result：推薦結(jié)果;RL（i）：用戶i的推薦列表。
步驟：
步驟1是從用戶的軌跡數(shù)據(jù)中產(chǎn)生停留區(qū)域。步驟2是運(yùn)用用戶和其停留區(qū)域等信息將軌跡數(shù)據(jù)轉(zhuǎn)化為事務(wù)數(shù)據(jù)集。步驟3是運(yùn)用類apriori方法產(chǎn)生項(xiàng)為用戶的最大頻繁項(xiàng)集，其中3.1是賦初始值，3.2是產(chǎn)生一階的頻繁項(xiàng)集，步驟3.5是通過連接k-1的頻繁項(xiàng)集產(chǎn)生k階頻繁項(xiàng)集的候選模式，步驟3.6是統(tǒng)計(jì)k階候選模式的支持度計(jì)數(shù)，步驟3.7是判斷候選模式的支持度計(jì)數(shù)是否滿足閾值產(chǎn)生k階的頻繁項(xiàng)集，步驟3.8是停止條件，當(dāng)k階頻繁項(xiàng)集為空時(shí)循環(huán)停止。步驟4是產(chǎn)生項(xiàng)為用戶興趣區(qū)域的頻繁項(xiàng)集。步驟5是產(chǎn)生相似用戶集。步驟6是產(chǎn)生top-n個(gè)推薦用戶興趣區(qū)域，其中6.1是產(chǎn)生候選推薦集、計(jì)算每一個(gè)候選推薦用戶興趣區(qū)域的得分并按得分進(jìn)行降序排序，步驟6.2返回top-n個(gè)推薦用戶興趣區(qū)域。
3.2? ?改進(jìn)算法：improved_algorithm
由于基本算法耗時(shí)長(zhǎng)，查找停留區(qū)域間的鄰近關(guān)系的時(shí)間復(fù)雜度為。挖掘頻繁項(xiàng)集時(shí)需要多次掃描數(shù)據(jù)庫。為了改進(jìn)這些問題我們提出了改進(jìn)算法。
根據(jù)鄰近關(guān)系的定義，如果兩個(gè)停留區(qū)域的最小外包矩形重疊，兩個(gè)停留區(qū)域之間具有鄰近關(guān)系。為了識(shí)別所有的鄰近關(guān)系，我們需要計(jì)算所有停留區(qū)域之間的關(guān)系，所以當(dāng)停留區(qū)域的數(shù)量巨大時(shí)，這是一步非常耗時(shí)的操作。為了減少不必要的計(jì)算，在改進(jìn)算法中我們采用網(wǎng)格劃分來快速搜索鄰近關(guān)系。接下來，我們將介紹網(wǎng)格劃分。
網(wǎng)格劃分：首先，找到所有停留區(qū)域最小外包矩形中最大的長(zhǎng)度和寬度，分別表示為L(zhǎng)w和Lh。對(duì)于一個(gè)最小外包矩形，長(zhǎng)度是指它在X軸方向上的長(zhǎng)度，寬度是指它在Y軸方向上的長(zhǎng)度。接下來，找出最小外包矩形最小的X、Y坐標(biāo)和最大的X、Y坐標(biāo)，分別表示為minX、minY、maX和maxY。所有停留區(qū)域的最小外包矩形的X坐標(biāo)位于區(qū)間[minX，maxX]，Y坐標(biāo)位于區(qū)間[minY，maxY]。將空間[（minX，minY），（maxX，maxY）]劃分為許多網(wǎng)格。網(wǎng)格的長(zhǎng)度是Lw，寬度是Lh。圖3給出了網(wǎng)格劃分示例。
如何將停留區(qū)域的最小外包矩形映射到網(wǎng)格中？
因?yàn)橥Ａ魠^(qū)域的最小外包矩形是一個(gè)區(qū)域而不是一個(gè)點(diǎn)，它可能位于多個(gè)網(wǎng)格中。所以我們將最小外包矩形的中心點(diǎn)映射到網(wǎng)格中，中心點(diǎn)所在的網(wǎng)格也就是該停留區(qū)域所在的位置。首先，我們定義一個(gè)二維數(shù)組：grid來存儲(chǔ)位于網(wǎng)格中的停留區(qū)域。其次，我們計(jì)算停留區(qū)域所在的網(wǎng)格。最后將其存儲(chǔ)在數(shù)組中。
圖3 網(wǎng)格劃分
Fig.3 Grid partition
例4：在空間中maxX=9、maxY=13、minX=1、minY=1、Lw=2、Lh=3，{（3，3），（3，6），（5，6），（5，3）}這四個(gè)點(diǎn)是停留區(qū)域o最小外包矩形的坐標(biāo)。我們可以計(jì)算出最小外包矩形的中心點(diǎn)（4，4.5），中心點(diǎn)所在的網(wǎng)格就是停留區(qū)域o所在的網(wǎng)格。因此，我們可以計(jì)算o所在網(wǎng)格的行數(shù)和列數(shù)。行號(hào)為：=1，列號(hào)為：=1。因此，grid[1，1]是o所在的網(wǎng)格。
搜索區(qū)域：一個(gè)網(wǎng)格的搜索區(qū)域是它自己和周圍的8個(gè)網(wǎng)格。
例5：如圖3所示，對(duì)于停留區(qū)域最小外包矩形o所在的網(wǎng)格，陰影網(wǎng)格為搜索區(qū)域。假設(shè)位于o附近的停留區(qū)域的外包矩形都是最大的。如果它們的中心點(diǎn)位于陰影網(wǎng)格中，它們可能與o有鄰近關(guān)系。如果中心點(diǎn)沒有位于陰影部分則它們不可能與o有鄰近關(guān)系。因?yàn)榫W(wǎng)格的長(zhǎng)度是停留區(qū)域最小外包矩形的最大長(zhǎng)度，網(wǎng)格的寬度是停留區(qū)域最小外包矩形的最大寬度，即使最小外包矩形是最大，停留區(qū)域最小外包矩形也不會(huì)在X軸方向或Y軸方向跨三個(gè)網(wǎng)格。所以，我們不需要搜索其他區(qū)域。
另外，由于基本算法在挖掘頻繁項(xiàng)集時(shí)需要多次掃描數(shù)據(jù)庫，這個(gè)操作十分耗時(shí)，并且會(huì)產(chǎn)生大量的候選集。在改進(jìn)算法中我們提出一種新方法來挖掘頻繁項(xiàng)集。我們以字典序來存放項(xiàng)集和其支持度計(jì)數(shù)，當(dāng)我們遍歷數(shù)據(jù)庫時(shí)對(duì)結(jié)果集進(jìn)行更新。這種方法只需要掃描兩次數(shù)據(jù)庫，并且不產(chǎn)生候選。為了方便描述，我們將產(chǎn)生頻繁項(xiàng)集這部分算法稱為DIC_Item。例6詳細(xì)地闡述了DIC_Item算法挖掘頻繁項(xiàng)集的過程。
例6：以從表2的事務(wù)數(shù)據(jù)中挖掘頻繁項(xiàng)集為例說明DIC_Item算法。第一次進(jìn)行遍歷數(shù)據(jù)庫，將數(shù)據(jù)庫中支持度計(jì)數(shù)小于閾值的項(xiàng)去掉，如表4所示，我們進(jìn)行遍歷后可以得到項(xiàng)和其支持度計(jì)數(shù)：{A：2，B：2，C：2，D：2，E：1，F(xiàn)：1，G：1，H：2}，假設(shè)我們的閾值為2。我們將支持度計(jì)數(shù)小于2的項(xiàng)去掉，對(duì)項(xiàng)集進(jìn)行映射，得到如表4所示的結(jié)果。
接下來，我們?cè)俅伪闅v數(shù)據(jù)庫對(duì)結(jié)果集內(nèi)容進(jìn)行添加和更新，我們掃描S001的映射集得到項(xiàng)集{AB，AC，AH，BC，BH，CH，ABC，ACH，BCH，ABCH}，對(duì)結(jié)果集中沒有的項(xiàng)集進(jìn)行添加，已存在的項(xiàng)集更新其Value值，得到如表5所示的結(jié)果。掃描S002的映射集得到項(xiàng)集{AB，AD，BC，ABD}，對(duì)于結(jié)果集中沒有的{AD，ABD}項(xiàng)集添加對(duì)應(yīng)的Key和Value。對(duì)于已有的{AB，BC}更新其Value值，得到如表6所示的結(jié)果。掃描完所有的事務(wù)后得到如表7所示的結(jié)果。掃描完所有的事務(wù)后對(duì)結(jié)果集進(jìn)行遍歷，去掉結(jié)果集中Value值小于閾值的項(xiàng)集，最后得到的頻繁項(xiàng)集是：{AB，BC，BH，CH，BCH}。
根據(jù)上述方法：網(wǎng)格劃分、DIC_Item，我們的改進(jìn)算法：improved_algorithm過程如下：
算法2：improved_algorithm
輸入：用戶的軌跡數(shù)據(jù);top-n的n值;頻繁項(xiàng)集支持度計(jì)數(shù)閾值sup。
輸出：推薦給用戶的top-n個(gè)用戶興趣區(qū)域
變量：SRS：用戶停留區(qū)域集;D：事務(wù)集;PIS：“興趣區(qū)域-用戶”事務(wù)數(shù)據(jù)（項(xiàng)為用戶）的最大頻繁項(xiàng)集;RPIS：“用戶-興趣區(qū)域”事務(wù)數(shù)據(jù)（項(xiàng)為興趣區(qū)域）的頻繁項(xiàng)集;F1：1階頻繁項(xiàng)集;G：網(wǎng)格集合;GS：當(dāng)前網(wǎng)格中停留區(qū)域集合;GI：位于搜索區(qū)域的停留區(qū)域集合;SR，SI：停留區(qū)域;S：區(qū)域集合;DIC：結(jié)果集;SUS：相似用戶集;Result：推薦結(jié)果。
步驟：
步驟1是從用戶的軌跡數(shù)據(jù)中產(chǎn)生停留區(qū)域。步驟2是運(yùn)用用戶和其停留區(qū)域等信息將軌跡數(shù)據(jù)轉(zhuǎn)化為事務(wù)數(shù)據(jù)集，其中2.1是將停留區(qū)域映射到網(wǎng)格中，2.2—2.8是遍歷網(wǎng)格找尋鄰近關(guān)系，利用鄰近關(guān)系找尋屬于同一個(gè)用戶興趣區(qū)域的停留區(qū)域并將其轉(zhuǎn)化為事務(wù)。步驟3是利用DIC_Item算法產(chǎn)生項(xiàng)為用戶的最大頻繁項(xiàng)集，其中3.1是第一次掃描事務(wù)并得到事務(wù)的映射集，3.2是第二遍掃描事務(wù)，同時(shí)更新結(jié)果集，3.3是判斷結(jié)果集中Value值大于支持度計(jì)數(shù)閾值的部分。步驟4是產(chǎn)生項(xiàng)為用戶興趣區(qū)域的頻繁項(xiàng)集。步驟5是產(chǎn)生相似用戶集。步驟6是產(chǎn)生top-n個(gè)推薦用戶興趣區(qū)域，其中6.1是產(chǎn)生候選推薦集、計(jì)算每一個(gè)候選用戶興趣區(qū)域的得分并按得分進(jìn)行降序排序，步驟6.2返回top-n個(gè)用戶興趣區(qū)域。
4? ?實(shí)驗(yàn)（Experiment）
第一，比較基本算法和改進(jìn)算法在不同支持度計(jì)數(shù)閾值和不同事務(wù)數(shù)量條件下執(zhí)行的時(shí)間效率。第二，比較三種算法的推薦質(zhì)量：improved_algorithm算法、基于關(guān)聯(lián)規(guī)則推薦[9]和基于協(xié)同過濾推薦算法[10]。第三，通過實(shí)驗(yàn)分析推薦top-n個(gè)用戶興趣區(qū)域給用戶中n值對(duì)準(zhǔn)確率的影響。所有算法均采用C#進(jìn)行編寫，并且在Core i3 1.8GHz和4GB內(nèi)存的計(jì)算機(jī)上運(yùn)行。
實(shí)驗(yàn)中采用的數(shù)據(jù)有兩種：一種是真實(shí)的GPS軌跡數(shù)據(jù)，它記錄了182個(gè)用戶從2007到2012年的軌跡數(shù)據(jù)。另外一種是模擬數(shù)據(jù)，模擬數(shù)據(jù)是隨機(jī)產(chǎn)生的，用戶興趣區(qū)域和訪問過該興趣區(qū)域的用戶都是隨機(jī)產(chǎn)生。
4.1? ?時(shí)間性能的比較
對(duì)basic_algorithm算法和improved_algorithm算法進(jìn)行時(shí)間性能的比較。實(shí)驗(yàn)研究了事務(wù)數(shù)量和支持度計(jì)數(shù)閾值兩個(gè)參數(shù)對(duì)算法執(zhí)行時(shí)間的影響
4.1.1? ?事務(wù)數(shù)量對(duì)算法執(zhí)行時(shí)間的影響
首先，我們來評(píng)估事務(wù)數(shù)量對(duì)算法執(zhí)行時(shí)間的影響。在這組實(shí)驗(yàn)中，我們采用模擬數(shù)據(jù)，事務(wù)的數(shù)目從5000增加到20000。如圖4所示，隨著事務(wù)數(shù)目的增多，算法的執(zhí)行時(shí)間也增大。因?yàn)殡S著事務(wù)數(shù)目的增多，項(xiàng)集的數(shù)目也增多，所以相似用戶的數(shù)量和待推薦用戶興趣區(qū)域都會(huì)增多，計(jì)算推薦得分的次數(shù)也會(huì)增多。因此，算法執(zhí)行時(shí)間增大。然而，改進(jìn)算法在計(jì)算頻繁項(xiàng)集時(shí)不需要多次掃描數(shù)據(jù)庫，不采用連接產(chǎn)生候選項(xiàng)集，所以改進(jìn)算法的執(zhí)行時(shí)間比基本算法的執(zhí)行時(shí)間少。從圖4可知改進(jìn)算法improved_algorithm的執(zhí)行時(shí)間沒有basic_algorithm增長(zhǎng)迅速，這說明了改進(jìn)算法improved_algorithm的效果。
4.1.2? ?支持度閾值對(duì)算法執(zhí)行時(shí)間的影響
接下來我們分析支持度計(jì)數(shù)閾值對(duì)算法的影響，支持度計(jì)數(shù)閾值從8減少到2。如圖5所示，隨著支持度計(jì)數(shù)閾值的下降，算法的執(zhí)行時(shí)間增加。這是因?yàn)橹С侄扔?jì)數(shù)閾值變小后滿足閾值的項(xiàng)集會(huì)增多，從而產(chǎn)生更多的頻繁項(xiàng)集。由于本文衡量相似用戶是根據(jù)最大頻繁項(xiàng)集來進(jìn)行衡量，所以最大頻繁項(xiàng)集增多相似用戶也會(huì)增多，向用戶進(jìn)行推薦時(shí)需要計(jì)算更多相似用戶興趣區(qū)域的推薦得分。因此閾值下降，算法的執(zhí)行時(shí)間增多。從圖5可以看出基本算法執(zhí)行時(shí)間比改進(jìn)算法執(zhí)行時(shí)間增加得更快。因?yàn)榛舅惴〞?huì)產(chǎn)生更多的候選模式及大量的連接操作。然而，改進(jìn)算法不需要產(chǎn)生候選模式，并且它產(chǎn)生模式不需要連接操作。所以改進(jìn)算法的時(shí)間增加的比較緩慢。
圖4 事務(wù)數(shù)目對(duì)算法執(zhí)行時(shí)間影響
Fig.4 The impact of the number of transactions
圖5 閾值對(duì)算法執(zhí)行時(shí)間影響
Fig.5 The impact of thresholds
4.2? ?準(zhǔn)確率、召回率和F值的對(duì)比
接下來，我們對(duì)比改進(jìn)算法、基于協(xié)同過濾推薦算法和基于關(guān)聯(lián)規(guī)則推薦算法三者的推薦質(zhì)量。這部分實(shí)驗(yàn)在真實(shí)數(shù)據(jù)上進(jìn)行。我們用時(shí)間來對(duì)真實(shí)數(shù)據(jù)進(jìn)行分類，分為2007年的數(shù)據(jù)、2008年的數(shù)據(jù)、2009年的數(shù)據(jù)、2010年的數(shù)據(jù)。2007年數(shù)據(jù)有10508條、2008年數(shù)據(jù)有19795條、2009年數(shù)據(jù)有51170條、2010年數(shù)據(jù)有10015條。推薦質(zhì)量的對(duì)比算法在這四個(gè)數(shù)據(jù)集上進(jìn)行。
推薦質(zhì)量我們用準(zhǔn)確率、召回率和F值來衡量。在本文中，我們將準(zhǔn)確率定義為：推薦給用戶的用戶興趣區(qū)域集與用戶訪問興趣區(qū)域集的交集與用戶訪問興趣區(qū)域集之比。我們將用戶訪問過的興趣區(qū)域隨機(jī)的抹掉一部分，查看推薦給用戶的用戶興趣區(qū)域列表中包含多少抹掉的用戶興趣區(qū)域。
定義7（準(zhǔn)確率）表達(dá)如下：
定義8（召回率）表達(dá)如下：
在準(zhǔn)確率和召回率的定義中，m為用戶數(shù)目，|E（i）|為用戶i訪問用戶興趣區(qū)域被抹掉集合的長(zhǎng)度，R（i）為推薦給用戶i的用戶興趣區(qū)域集合，為用戶i被抹掉的用戶興趣區(qū)域集合與推薦用戶興趣區(qū)域集合的交集的長(zhǎng)度。
定義9（F值）表達(dá)如下：
其中，P為準(zhǔn)確率，C為召回率。
在本組實(shí)驗(yàn)中對(duì)三種算法的準(zhǔn)確率、召回率和F值進(jìn)行對(duì)比，參數(shù)設(shè)置如表8所示。如圖6所示，對(duì)比三者可知本文提出的算法準(zhǔn)確率優(yōu)于其他兩種算法。當(dāng)數(shù)據(jù)量變化時(shí)，準(zhǔn)確率會(huì)受一定的影響，但是從圖6中可以看出我們提出的算法波動(dòng)較小，較為穩(wěn)定。從圖7和圖8可以看出，我們提出算法的召回率和F值均優(yōu)于對(duì)比算法。
4.3 top-n中n值對(duì)準(zhǔn)確率的影響
我們將研究推薦top-n個(gè)用戶興趣區(qū)域給用戶的n值對(duì)推薦準(zhǔn)確率的影響。如圖9所示，隨著n值的增加三個(gè)推薦算法的準(zhǔn)確率也增加，但是improved_algorithm算法優(yōu)于其他兩個(gè)算法。從圖7中可以看出我們提出的improved_algorithm算法在n=10時(shí)，算法的準(zhǔn)確率較高，隨著n值的不斷增加，準(zhǔn)確率緩慢的增加。這說明我們定義的用戶興趣區(qū)域推薦得分具有一定的合理性。用戶訪問可能性更高的用戶興趣區(qū)域，推薦得分更高，用戶興趣區(qū)域排名更靠前。所以當(dāng)n值增大時(shí)，準(zhǔn)確率不會(huì)急劇上升，因?yàn)橛脩艨赡茉L問的用戶興趣區(qū)域大部分包含在了top-10中，只會(huì)有少量出現(xiàn)在top-10后的推薦列表中。
圖8 F值的對(duì)比
Fig.8 Comparison of F
圖9 top-n中n值對(duì)準(zhǔn)確率的影響
Fig.9 The impact of n on precision
5? ?結(jié)論（Conclusion）
由于許多推薦算法進(jìn)行推薦時(shí)需要用戶的評(píng)分信息。這樣會(huì)因?yàn)槿鄙傩畔⒂绊懲扑]質(zhì)量。本文提出了一種不需要用戶評(píng)分?jǐn)?shù)據(jù)的推薦算法。論文定義了停留區(qū)域，通過停留區(qū)域間的鄰近關(guān)系將用戶的軌跡數(shù)據(jù)轉(zhuǎn)化為事務(wù)數(shù)據(jù)，并基于挖掘到的最大頻繁項(xiàng)集來定義用戶的相似性。最后定義了推薦得分。在模擬數(shù)據(jù)和真實(shí)數(shù)據(jù)上進(jìn)行了廣泛的實(shí)驗(yàn)證明了提出方法的有效性，同時(shí)，將我們提出算法和基于協(xié)同過濾推薦算法、基于關(guān)聯(lián)規(guī)則推薦算法進(jìn)行了對(duì)比，結(jié)果顯示本文提出算法具有更好的推薦效果。在接下來的工作中，我們將在本文基礎(chǔ)上擴(kuò)展，將其運(yùn)用于選址。
參考文獻(xiàn)（References）
[1] Bao J，Zheng Y，Wilkie D，et al.Recommendations in location-based social networks：a survey[J].GeoInformatica，2015，19（3）：525-565.
[2] Xin M，Zhang Y，Li S，et al.A Location-Context Awareness Mobile Services Collaborative Recommendation Algorithm Based on User Behavior Prediction[J].International Journal of Web Services Research （IJWSR），2017，14（2）：45-66.
[3] Wu T，Mao J，XIE Q，et al.Top-κ hotspots recommendation algorithm based on real-time traffic[J].Journal of East China Normal University （Natural Science），2017（5）：195-209.
[4] Schafer J B，Konstan J，Riedl J.Recommender systems in e-commerce[C].Proceedings of the 1st ACM conference on Electronic commerce.ACM，1999：158-166.
[5] Berjani B，Strufe T.A recommendation system for spots in location-based online social networks[C].Proceedings of the 4th workshop on social network systems.ACM，2011：4.
[6] Hu L，Chen J，Shen S，et al.Recommendation Algorithm Research Based on Clustering on Users' Trajectories[C].Proceedings of the 29th CCF National Database Conference，2012：250-256.
[7] Liu Y，Pham T A N，Cong G，et al.An experimental evaluation of point-of-interest recommendation in location-based social networks[J].Proceedings of the VLDB Endowment，2017，10（10）： 1010-1021.
[8] Agrawal R，Srikant R.Fast algorithms for mining association rules[M].Readings in database systems（3rd ed.）.Morgan Kaufmann Publishers Inc.，1996.
[9] Kardan A A，Ebrahimi M.A novel approach to hybrid recommendation systems based on association rules mining for content recommendation in asynchronous discussion groups[J].Information Sciences，2013（219）：93-110.
[10] Yi C，Leung H F，Li Q，et al.Typicality-Based Collaborative Filtering Recommendation[J].IEEE Transactions on Knowledge & Data Engineering，2014，26（3）：766-779.
作者簡(jiǎn)介：
龍玉絨（1994-），女，碩士生.研究領(lǐng)域：數(shù)據(jù)挖掘.
王麗珍（1962-），女，博士，教授.研究領(lǐng)域：數(shù)據(jù)挖掘，計(jì)算機(jī)算法.本文通訊作者.
陳紅梅（1976-），女，博士，副教授.研究領(lǐng)域：數(shù)據(jù)挖掘，人工智能.
