廖旺宇

(四川旅游學(xué)院 ，四川 成都 610100)

基于增量關(guān)聯(lián)規(guī)則游記挖掘的景點推薦應(yīng)用研究※

廖旺宇

(四川旅游學(xué)院 ，四川 成都 610100)

文章提出了一種基于旅游文記挖掘的改進增量關(guān)聯(lián)規(guī)則景點推薦算法。該算法緊密關(guān)注旅行者偏好，基于分類有效降低了算法空間復(fù)雜度，使得挖掘結(jié)果聚焦度更高；能夠高效處理旅游文記數(shù)量增長的狀況，避免了反復(fù)掃描整個數(shù)據(jù)集，僅需掃描增量數(shù)據(jù)集并結(jié)合已有挖掘結(jié)果便可開展高效運算分析，完成相關(guān)景點推薦應(yīng)用。通過使用網(wǎng)絡(luò)獲取旅游文記作為實例對算法進行驗證，表明改進算法在候選項集獲取個數(shù)方面減少明顯，推薦結(jié)果清晰明了，有較明顯的優(yōu)勢。

關(guān)聯(lián)規(guī)則；增量更新；旅游文記挖掘；景點推薦

旅游逐漸成為休閑娛樂活動中不可或缺的組成部分。同時，互聯(lián)網(wǎng)技術(shù)和自媒體平臺的迅速發(fā)展一方面為旅行者分享旅行經(jīng)歷、提供出行建議帶來了巨大的便利；另一方面為計劃出行者進行景點和線路甄選提供了極具代表性和可靠性的[1]重要參考依據(jù)。然而旅行者很難高效、準確地從龐雜多樣、質(zhì)量參差不齊的旅游文記中獲取滿足其偏好和要求的出行參考信息。設(shè)計一種高效算法幫助旅行者處理、分析繁雜的旅游文記，使其在獲得了某些旅游景點并安排到自己的旅游行程單之后，可以通過系統(tǒng)智能地推薦符合其喜好的相關(guān)聯(lián)的旅游目的地或者景點，以擴展其旅游景點的選擇范圍或豐富其行程安排[2]成為亟待解決的需求。

由R·Agraeal等人首先提出的關(guān)聯(lián)規(guī)則算法[3]可以解決上述問題。但是經(jīng)典的關(guān)聯(lián)規(guī)則算法，如Apriori算法等，所處理的數(shù)據(jù)集都相對固定，無法高效應(yīng)對互聯(lián)網(wǎng)中旅游文記數(shù)量快速增長的情況。在旅游文記集合增長之后只能完全重新執(zhí)行高花費的整個頻繁項目集的發(fā)現(xiàn)過程[4]，進而重新獲取關(guān)聯(lián)規(guī)則挖掘，嚴重降低了運行效率。并且，在傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘過程中，為了最大限度地獲取更多的規(guī)則，需要對所有頻繁項目集的非空子集進行計算。而事實上，旅行者只關(guān)注與其偏好相吻合的、關(guān)聯(lián)性強的景點集合。傳統(tǒng)挖掘方式獲得的規(guī)則中包含了眾多用戶不關(guān)注的規(guī)則，這樣既不方便用戶瀏覽挖掘結(jié)果，又浪費了計算機的資源，降低了效率。

基于上述考慮，本文利用在原有高效更新關(guān)聯(lián)規(guī)則算法[5]和增量關(guān)聯(lián)規(guī)則更新算法[6]基礎(chǔ)上所提出的改進增量關(guān)聯(lián)規(guī)則算法，高效地從大容量旅游文記中獲取用戶關(guān)注度高的關(guān)聯(lián)景點集合。依據(jù)該關(guān)聯(lián)景點集合便可精確地推薦、選擇滿足旅行者偏好的景點。同時，當(dāng)旅游文記集合增長時，無須完全重新掃描整個游記文本集合，只需對增量游記進行掃描處理便可更新相關(guān)聯(lián)的景點集合，為智能、高效的景點推薦提供了極大的便利。

1 基于增量關(guān)聯(lián)規(guī)則旅游文記挖掘的旅游景點推薦的算法設(shè)計

1.1算法基礎(chǔ)

基本思想：設(shè)初始數(shù)據(jù)集為DB，在掃描DB一次之后，記錄所有非空項目集及其支持度計數(shù)并用于生成初始數(shù)據(jù)集的頻繁項目集。在實驗數(shù)據(jù)集動態(tài)增長之后，設(shè)增長部分的數(shù)據(jù)集為db。此時只需對db進行一次掃描，記錄所有非空項目集及其支持度計數(shù)，并利用該結(jié)果與DB中已知的挖掘結(jié)果進行合并分析處理，便可生成擴充之后的新數(shù)據(jù)集DB+db的頻繁項目集進而獲取強規(guī)則。該方法避免了重復(fù)掃描整個DB+db數(shù)據(jù)集，減少數(shù)據(jù)庫I/O次數(shù)的同時，降低了算法運行的空間需求，提升了挖掘結(jié)果的聚焦度。

設(shè)DB中的事務(wù)總數(shù)為|DB|，db中的事務(wù)總數(shù)為|db|。若用戶設(shè)定的最小支持度閾值為minsup，則數(shù)據(jù)集DB、db及DB+db中頻繁項所需滿足的最小支持度計數(shù)分別為cDB=minsup*|DB|、cdb=minsup*|DB|和cDB+db=minsup*|DB|。且，顯然cDB+db=cDB+cdb。

設(shè)數(shù)據(jù)集DB、db、DB+db中候選項的實際支持度計數(shù)分別為sDB、sdb、sDB+db，且顯然sDB+db=sDB+sdb。

為便于討論，設(shè)fx=sx-cx(x=DB，db，DB+db)，顯然有：若f≥0，則該候選項集為數(shù)據(jù)集中的頻繁項集；若f<0，則該候選項集為數(shù)據(jù)集中的非頻繁項集，且fDB+db=fDB+fdb。

性質(zhì)1，若某一候選項集在DB中為頻繁項集，且在db中為頻繁項集，則該候選項在DB+db中為頻繁項集。

證明：若某一候選項集在DB和db中為頻繁項集，則fDB≥0，fdb≥0，顯然有fDB+db=fDB+fdb≥0。所以，該候選項集在DB+db中為頻繁項集。

性質(zhì)2，若某一候選項集在DB中為非頻繁項集，且在db中也為非頻繁項集，則該候選項集在DB+db中為非頻繁項集。

證明：若某一候選項集在DB和db中為非頻繁項集，則fDB<0，fdb<0，顯然有fDB+db=fDB+fdb<0。所以，該候選項集在DB+db中為非頻繁項集。

性質(zhì)3，若一個候選項在DB和db中分別為頻繁項集、非頻繁項集或非頻繁項集、頻繁項集，則該候選項集在DB+db中是否為頻繁項集不確定。

證明：若某一候選項集在DB中頻繁，在db中不頻繁，則fDB≥0，fdb<0，顯然無法確定fDB+db=fDB+fdb的值為正值還是負值。

若某一候選項集在DB中不頻繁，在db中頻繁，則fDB<0，fdb≥0，顯然無法確定fDB+db=fDB+fdb的值為正值還是負值。

所以，以上兩種情況無法確定該候選項是否為DB+db中的頻繁候選項。

當(dāng)出現(xiàn)性質(zhì)3中情況時，只能將該候選項集在DB+db中的實際支持度計數(shù)sDB+db與(|DB| + |db|)*minsup比較進行判斷。而sDB+db=sDB+sdb，顯然可以通過已知的sDB和sdb容易地得到。

因此，根據(jù)性質(zhì)1、性質(zhì)2、性質(zhì)3，候選項集是否為頻繁項集的判斷方式可以歸納為表1：

表1 增量更新候選項頻繁狀況判定表

1.2算法描述

增量關(guān)聯(lián)規(guī)則游記挖掘算法分為兩個階段：首先，高效統(tǒng)計出DB或db中每一非空項集的支持度計數(shù)；然后，利用上一階段的結(jié)果和已知的挖掘結(jié)果更新具有用戶指定的最小支持度閾值的頻繁項集。

對于每一個項集都有一個count域來存儲其實際支持度計數(shù)，算法描述如下。

算法1：統(tǒng)計各項集的實際支持度計數(shù)

輸入：事務(wù)數(shù)據(jù)集DB或db，項集I={i1，i2，……，in}。

輸出：所有實際支持度計數(shù)大于零的項集CDB或Cdb，及CDB或Cdb中每一項目所對應(yīng)的實際支持度計數(shù)。

算法描述：

(1)初始化CDB或Cdb，將其置為空值。

(2)設(shè)置算法關(guān)注的目的地項目。不妨設(shè)算法只關(guān)注與目的地ix相關(guān)的景點。

(3)對事物數(shù)據(jù)集DB或db中的每一事務(wù)中的所有包含ix的項集c進行計數(shù)：

若該項集c已經(jīng)包含于CDB或Cdb中，則將其對應(yīng)的count值增加1；

否則將該項集c加入CDB或Cdb中，并將其計數(shù)count記為1。

(4)對事物數(shù)據(jù)集DB或db中的每一事務(wù)中的所有與ix相關(guān)，但不包含ix的項集c進行計數(shù)：令c=c-ix，則：

若該項集c已經(jīng)包含于CDB或Cdb中，則將其對應(yīng)的count值增加1；

否則將該項集c加入CDB或Cdb中，并將其計數(shù)count記為1。

由算法1顯然可以產(chǎn)生所有與游客密切關(guān)注的目的地ix相關(guān)的、項目集合的實際支持度計數(shù)非零的項集。

若對數(shù)據(jù)集DB使用該算法，可以完成對初始數(shù)據(jù)集中與用戶關(guān)注景點相關(guān)的、實際支持度計數(shù)非零的候選項目集合CDB。隨后依據(jù)CDB便捷地得到頻繁項集FDB，并檢驗其各子項是否滿足最小置信度閾值，進而得到初始數(shù)據(jù)中用戶關(guān)注度高的關(guān)聯(lián)景點集合。

當(dāng)游記動態(tài)增長時，首先將新增數(shù)據(jù)集db作為輸入執(zhí)行算法1，即可獲得db的所有與用戶關(guān)注景點相關(guān)的、項集的支持度計數(shù)非零的候選項目集合Cdb。此時，執(zhí)行算法2將容易地獲取到DB+db的頻繁項集FDB+db，進而得到更新后的用戶關(guān)注度高的相關(guān)景點集合。

算法2：

輸入：最小支持度閾值minsup，候選項集CDB、Cdb，原數(shù)據(jù)集DB的頻繁項集FDB。

輸出：DB+db中具有最小支持度閾值minsup的所有頻繁項集的集合FDB+db。

算法描述：

(1)初始化CDB+db，將其值置為CDB+db=CDB+Cdb。

(2)求db的頻繁項集：首先將Fdb置為空值，若Cdb中某一項目cdb的實際支持度計數(shù)大于等于|db|*minsup，則將cdb加入Fdb中。

(3)依據(jù)表1中的方法判斷項集在DB+db中是否頻繁：

①對于CDB+db中的所有項目fDB+db，若在DB中頻繁：

若在db中不頻繁:計算fDB+db.count=fDB.count+fdb.count。

如果fDB+db.count≥(|DB| + |db|)*minsup，則將fDB+db加入FDB+db；否則，將其從頻繁項集中刪除。

若在db中頻繁：將fDB+db加入FDB+db，并置其支持度計數(shù)為fDB.count+fdb.count。

②對于CDB+db中的所有項目fDB+db，若在DB中不頻繁：

若在db中頻繁：計算fDB+db.count=fDB.count+fdb.count。

如果fDB+db.count≥(|DB| + |db|)*minsup，則將fDB+db加入FDB+db；否則，將其從頻繁項集中刪除。

若在db中不頻繁，則將其從頻繁項集中刪除。

(4)將CDB+db置為CDB：

在獲取頻繁項集FDB+db，并檢驗其中子項是否滿足最小置信度閾值，進而得到更新后的數(shù)據(jù)集中用戶關(guān)注度高的關(guān)聯(lián)景點集合。

2 實驗與結(jié)果分析

2.1基于旅游文記挖掘的旅游景點推薦應(yīng)用實例

本文以四川省成都市為例，從螞蜂窩網(wǎng)站上以“成都”作為檢索詞獲取了427篇旅行游記，并隨機將其中321篇游記作為初始實驗數(shù)據(jù)集DB，106篇作為增量實驗數(shù)據(jù)集db。隨后分別提取了DB和db中每一篇游記中的地理名詞。在糾正了錯誤語義的地理名詞之后，對獲取到的共208個地理名詞進行了數(shù)據(jù)預(yù)處理，將所有地理名詞替換為對應(yīng)的地理名詞ID號，形成了由游記ID和地理名詞ID集合構(gòu)成的實驗數(shù)據(jù)表，部分數(shù)據(jù)表快照如圖1所示。

圖1 游記地理名詞集合部分數(shù)據(jù)快照

其中，TID為標(biāo)識符，TRANS為各游記中經(jīng)過預(yù)處理的地理名詞集合。DB中單個元組包含的ID個數(shù)最小值為1個，最大值為31個；db中單個元組包含的ID個數(shù)最小值為1個，最大值為16個。本文隨機選取以關(guān)注武侯祠對應(yīng)的項目“I5”為例開展應(yīng)用實例實驗。

首先執(zhí)行算法1，產(chǎn)生DB中所有支持度計數(shù)非零的候選項集合及其支持度計數(shù)CDB，得：

CDB={(I1,56),(I2,195),(I3,66),…,(I1I2,47),(I1I3,12),…,(I1I2I3,10),(I1I2I4,22),…,…,(I1I2I3I4I5I6I9I10I11I12I17I27I28I31I32I33I42I44I45I50I110I118I125I127I135I147I150I151I152I161I162,1)}

其中，(x,y)∈CDB，則x表示DB中的地理名詞項目集，y表示其對應(yīng)的支持度計數(shù)。不妨設(shè)用戶給定的最小支持度閾值為minsup=20%，則CDB需滿嘴的最小支持度計數(shù)為minsup*|DB|=321*20%≈64。

在CDB中進行篩選，即可產(chǎn)生具有用戶指定的最小支持度閾值的頻繁項集FDB，得：

FDB={(I2,195),(I3,66),(I4,92),(I5,126),(I6,189),(I9,118),(I14,73),(I2I4,70),(I2I5,95),(I2I6,144),(I2I9,88),(I4I6,72),(I5I6,110),(I5I9,67),(I6I9,87),(I2I5I6,88),(I2I6I9,71)}

若僅為針對初始數(shù)據(jù)集求頻繁項集FDB，則至此執(zhí)行完畢。并可由所得FDB進一步容易地根據(jù)公式(1)[7-8]求取。

Confidence(X→Y)=Support(X∪Y)/Support(X)(1)

各候選項集的置信度值如表2所示。

進而根據(jù)用戶設(shè)置的最小支持度閾值、最小置信度閾值得到與旅行者關(guān)注的武侯祠相關(guān)的、可推薦游覽的景點的集合。

表2 DB中各規(guī)則的支持度和置信度

若游記數(shù)量增長之后需要更新強關(guān)聯(lián)規(guī)則，則先對增量集合db執(zhí)行算法1，產(chǎn)生db中所有支持度計數(shù)非零的候選項集合及其支持度計數(shù)Cdb，得：

Cdb={(I1,16),(I2,71),(I3,36),…,(I1I2,10),(I1I3,7),…,(I1I2I3,5),(I1I2I4,2),…,…,(I2I5I6I9I13I14I17I18I34I62I66I78I84I85I134I175,1)}

若用戶設(shè)定的最小支持度閾值仍為minsup=20%，則cdb需滿足的最小支持度計數(shù)為minsup*|DB|=106*20%≈21。在Cdb中進行篩選，即可產(chǎn)生具有用戶指定的最小支持度閾值的頻繁項集Fdb，得：

Fdb={(I2,71),(I3,36),(I4,24),(I5,45),(I6,72),(I9,45),(I14,23),(I2I3,31),(I2I5,34),(I2I6,57),(I2I9,35),(I3I6,27),(I5I6,36),(I5I9,23),(I6I9,32),(I2I3I6,24),(I2I5I6,28),(I2I6I9,28)}

隨后，根據(jù)算法2，設(shè)置CDB+db=CDB+Cdb，并對CDB+db中所有子集依據(jù)表1中的判斷方式進行判斷。

例如，在候選項集CDB+db中：

(1)子集I2，在DB和db中均為頻繁項集，因此I2屬于FDB+db。

(2)子集I1，在DB和db中均為非頻繁項集，因此I1不屬于FDB+db。

(3)子集I2I4，在DB中為頻繁項集，在db中為非頻繁項集，需要從全局判斷其是否屬于FDB+db。此時，候選子集需要滿足的最小支持度計數(shù)為(|DB|+|db|)*minsup=(321+106)*20%，約為85。而子集I2I4在DB+db中的支持度計數(shù)為70+17=87，因此I2I4屬于FDB+db。

(4)子集I2I3，在DB中為非頻繁項集，在db中為頻繁項集，需要從全局判斷其是否屬于FDB+db。此時，候選子集需要滿足的最小支持度計數(shù)為(|DB|+|db|)*minsup=(321+106)*20%，約為85。而子集I2I4在DB+db中的支持度計數(shù)為50+31=81，因此I2I3不屬于FDB+db。

對CDB+db中所有子集均使用上述方法進行判斷后，最終可得到所需的更新之后的游記集合DB+db中的頻繁地名項集FDB+db：

FDB+db={(I2,266),(I3,102),(I4,116),(I5,171),(I6,261),(I9,119),(I14,87),(I2I4,104),(I2I5,152),(I2I6,147),(I2I9,89),(I5I6,113),(I6I9,88),(I2I5I6,116),(I2I6I9,99)}

根據(jù)FDB+db可以簡易地根據(jù)公式(1)計算出納入新增游記地名記錄之后的新數(shù)據(jù)集中各候選項集的置信度值如表3所示。

表3 DB+db中各規(guī)則的支持度和置信度

進而向旅行者推薦滿足最小支持度閾值和最小置信度閾值的與其關(guān)注的武侯祠緊密關(guān)聯(lián)的景點的集合。假設(shè)，用戶設(shè)置置信度為65%，則關(guān)聯(lián)規(guī)則I5→I2和I5→I6成為強規(guī)則。參照地名數(shù)據(jù)預(yù)處理記錄，可以還原為規(guī)則游覽武侯祠的游客還游覽了寬窄巷子和錦里。據(jù)此，可將寬窄巷子和錦里兩景點推薦給游客備選。

2.2應(yīng)用實例分析及與原算法的比較

應(yīng)用實例隨機選取以關(guān)注數(shù)據(jù)預(yù)處理后對應(yīng)于武侯祠的地名候選項集“I5”為例，對算法的運行過程進行了說明。算法在獲取游記地名候選項集的過程中只掃描了兩次數(shù)據(jù)庫，并可以在游記數(shù)量增長后只掃描增加部分的數(shù)據(jù)集db。既有效避免了多次掃描數(shù)據(jù)庫而引起多次I/O操作，又可以在處理增量數(shù)據(jù)時有效利用已有掃描結(jié)果，避免反復(fù)掃描龐大的數(shù)據(jù)集。同時，針對旅行者只關(guān)注其偏好的游覽項目的特點，設(shè)置了面向分類的關(guān)注項集，大幅度減小了候選項集中的項目個數(shù)，有效減小算法運行所需占用的空間的同時，增強了挖掘結(jié)果的聚焦度。

實驗結(jié)果表明，不論是對初始數(shù)據(jù)集DB還是增量數(shù)據(jù)集db進行處理，本文算法所求取的候選集C中的項目個數(shù)都有明顯下降。其中，對初始數(shù)據(jù)集DB進行處理時，本文算法共獲取的支持度計數(shù)不為零的候選項集總數(shù)為1 216 576 105個，相較于原算法獲取總數(shù)的2 250 572 195個大幅下降了45.94%；對增量數(shù)據(jù)集db進行處理時，本文算法共獲取的支持度計數(shù)不為零的候選項集總數(shù)為89 665個，相較于原算法獲取總數(shù)的151 134個大幅下降了40.67%。DB、db中各支持度計數(shù)非零的候選項集個數(shù)比較詳細情況見圖2所示。

(1)CDB子集數(shù)目比較

(2)Cdb子集數(shù)目比較圖2 候選項集子集個數(shù)比較

3 總結(jié)

旅游電子商務(wù)的快速發(fā)展使得越來越多的旅行者借助網(wǎng)絡(luò)獲取出行信息、預(yù)訂產(chǎn)品[9]，針對游客希望依據(jù)自己偏好的景點由系統(tǒng)自動向其推薦相關(guān)聯(lián)的旅游景點，以擴展、優(yōu)化和豐富其旅行選擇范圍的需求，本文利用改進的高效增量關(guān)聯(lián)規(guī)則算法予以實現(xiàn)，并有效降低了原有算法的空間復(fù)雜度，提高了挖掘結(jié)果的聚焦度。同時，伴隨著互聯(lián)網(wǎng)技術(shù)和自媒體的迅速發(fā)展，發(fā)表旅游評論和游記、分享旅行經(jīng)歷也愈發(fā)便捷，因而大量的旅游文記正在不斷生成。本文的算法可以高效應(yīng)對旅游文記數(shù)量增長的情況，從大量已有游記或新增游記中挖掘出一系列景點集合推薦給用戶，具有一定的應(yīng)用價值和針對性。

[1]曹新向. 充分利用網(wǎng)絡(luò),為旅游研究和決策提供服務(wù)[J]. 旅游學(xué)刊,2007,22(5):11-12.

[2]胡喬楠. 基于旅游文記的旅游景點推薦及行程路線規(guī)劃系統(tǒng)[D]. 杭州:浙江大學(xué),2015.

[3]Agrawal R， et al. Mining association rules between sets of items in large databases[C]∥ Proceedings of ACM SIGMOD Conference on Management of Data. Washington DC, 1993: 207-216.

[4]楊君銳. 關(guān)聯(lián)規(guī)則增量式快速更新方法的研究[J]. 微電子學(xué)與計算機,2004,21(9):120-124.

[5]周海巖. 適合于高效更新的關(guān)聯(lián)規(guī)則挖掘算法[J]. 小型微型計算機系統(tǒng),2004,25(4):634-637.

[6]馮玉才,馮建琳. 關(guān)聯(lián)規(guī)則的增量式更新算法[J]. 軟件學(xué)報,1998,9(4): 301-306.

[7]Jiawei Han, MichelineKamber .數(shù)據(jù)挖掘概念與技術(shù)(第2版)[M]. 范明,孟小峰,譯. 北京: 機械工業(yè)出版社,2007:147-148.

[8]黃德才. 數(shù)據(jù)倉庫與數(shù)據(jù)挖掘教程[M]. 北京:清華大學(xué)出版社,2016:228-230.

[9]閆海艷. 在線旅游用戶數(shù)據(jù)研究及其關(guān)聯(lián)應(yīng)用[D]. 上海:華東師范大學(xué),2015.

ApplicationResearchonIncrementalAssociationRulesforTravelogueMining-basedTouristAttractionsRecommending

LIAOWangyu

(Sichuan Tourism University, Chengdu 610100, Sichuan, China)

As the travelers would like the system to automatically recommend relevant scenery spots to optimize their travel plan based on their preferences and selections, an improved incremental updating algorithm of association rules based on tourist attraction recommendation is proposed. The algorithm focuses on the traveler’s preferences and its classification effectively reduces the space complexity of the algorithm, making the mining result more concentrated. It can efficiently handle the growth of travel documents, avoiding scanning the entire data set and only scanning the incremental data set and combining the results with the existing mining results. Through the experimental verification, the improved algorithm can significantly reduce the number of candidates, and the results are clear and have obvious advantages.

association rules; incremental updating; travelogue mining; tourist attractions recommending

F590.7

A

2095-7211(2017)06-0089-05

本文為四川省教育廳自然科學(xué)項目 “數(shù)據(jù)挖掘在餐飲旅游業(yè)客戶關(guān)系管理中的應(yīng)用研究”的階段性研究成果，項目編號：13ZB0148。

廖旺宇(1984—)，男，四川成都人，四川旅游學(xué)院講師，主要從事數(shù)據(jù)挖掘研究。