徐宏， 陳焰*， 支艷利， 張金鵬

(1.昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院, 昆明 650504;2. 云南財(cái)經(jīng)大學(xué) 信息管理中心， 昆明 650221)

0 引言

隨著互聯(lián)網(wǎng)的普及發(fā)展以及電子商務(wù)網(wǎng)站的興起，利用網(wǎng)絡(luò)進(jìn)行在線信息的搜索已經(jīng)成為旅游者在旅游前獲取信息的主要渠道，但是嚴(yán)重的信息過載使得旅游者常常淹沒于大量的信息搜索和產(chǎn)品選擇當(dāng)中。旅游個(gè)性化推薦系統(tǒng)正是解決這一問題的有效方法，其不僅能為旅游者搜索到符合其需求和偏好的旅游信息，做出旅游決策，也能減少旅游企業(yè)的成本，幫助企業(yè)盈利[1]。但是旅游推薦系統(tǒng)具有相對(duì)于其他推薦項(xiàng)目的特殊性。從四個(gè)方面分析，第一，用戶的旅游數(shù)據(jù)信息更復(fù)雜；第二，用戶在網(wǎng)站進(jìn)行搜索時(shí)，很難準(zhǔn)確表達(dá)自己的需求；第三，開發(fā)者很難獲取用戶的旅游偏好信息[2]；第四，用戶的旅游數(shù)據(jù)更稀疏。Ricci,et[3]也指出，相對(duì)于書、電影等低復(fù)雜度的推薦系統(tǒng)，保險(xiǎn)、金融、旅游等是最為復(fù)雜的推薦項(xiàng)目。從四大著名的外文數(shù)據(jù)庫(kù)ProQuest、ScienceDirect、Ingenta、Springer中進(jìn)行相關(guān)搜索發(fā)現(xiàn)，由于旅游推薦系統(tǒng)的特殊性與重要性，旅游個(gè)性化推薦正在成為學(xué)術(shù)界和產(chǎn)業(yè)界研究的熱點(diǎn)。

本文通過對(duì)國(guó)內(nèi)外推薦系統(tǒng)在旅游領(lǐng)域的應(yīng)用文獻(xiàn)整理，總結(jié)了旅游推薦系統(tǒng)相對(duì)應(yīng)其他推薦產(chǎn)品的特殊性；分析了傳統(tǒng)旅游推薦系統(tǒng)的一般框架；并針對(duì)傳統(tǒng)推薦方法在面對(duì)這些特殊性時(shí)存在的缺陷，提出了一種基MC-Apriori算法的旅游個(gè)性化推薦模型，該方法通過MC-Apriori算法對(duì)用戶搜索和閱覽的歷史關(guān)鍵詞進(jìn)行頻繁集挖掘并向用戶推薦符合其興趣傾向的旅游信息，通過利用收集的康輝旅行社的語(yǔ)料數(shù)據(jù)測(cè)試，證明了本文的推薦方法比傳統(tǒng)推薦系統(tǒng)更具有使用價(jià)值，并且在此基礎(chǔ)上，論證了MC-Apriori算法不僅減少了每次掃描全部數(shù)據(jù)所需要的開銷，而且提高了效率。

1 傳統(tǒng)旅游推薦系統(tǒng)

旅游推薦的內(nèi)容包括游、娛、購(gòu)、食、住、行六方面的旅游產(chǎn)品。若向用戶推薦準(zhǔn)確、多樣和個(gè)性化的旅游產(chǎn)品，需要通過四方面的數(shù)據(jù)信息：用戶需求、用戶偏好、約束條件及旅游資源庫(kù)。用戶需求是用戶對(duì)當(dāng)前旅游產(chǎn)品的要求，屬主觀條件，如：用戶對(duì)住宿條件等要求。用戶偏好可以通過分析該用戶的歷史旅游數(shù)據(jù)，如用戶對(duì)旅游產(chǎn)品的評(píng)論內(nèi)容[4]。約束條件值是指影響用戶決策的一些外部客觀條件，如用戶的性別或收入[5]。旅游資源庫(kù)是旅游領(lǐng)域中的包含屬性值[6]的旅游產(chǎn)品，它是分析、產(chǎn)生推薦系統(tǒng)的重要數(shù)據(jù)之一，如推薦景點(diǎn)可采集景點(diǎn)名稱和類別、門票、評(píng)分等信息。

在推薦時(shí)，有時(shí)還要考慮多個(gè)產(chǎn)品之間復(fù)雜的時(shí)空關(guān)系[7]，因此相比其他產(chǎn)品，旅游數(shù)據(jù)更復(fù)雜，用戶更難準(zhǔn)確表述自己的需求。而對(duì)于開發(fā)者來(lái)說，很難獲取用戶旅游偏好信息。而受時(shí)間和消費(fèi)支出等約束條件，用戶一年之內(nèi)實(shí)際旅游過的景點(diǎn)屈指可數(shù)，用戶之間共同旅游的景點(diǎn)更是很少，所以旅游數(shù)據(jù)更稀疏。而如何挖掘用戶的隱藏信息變得更重要。

通過對(duì)當(dāng)前推薦系統(tǒng)在旅游領(lǐng)域的應(yīng)用文獻(xiàn)分析，總結(jié)出了旅游推薦系統(tǒng)的一個(gè)通用框架。其主要包含4個(gè)步驟：旅游產(chǎn)品建模、用戶建模、推薦計(jì)算，產(chǎn)品展示。通常的推薦方法有基于內(nèi)容的推薦[8]，基于協(xié)同過濾的推薦[9]，基于知識(shí)的推薦[10]和基于社會(huì)媒體的推薦[11]，并且時(shí)間復(fù)雜性大于O(m2×n)。如Majid等[12]根據(jù)構(gòu)建的景點(diǎn)庫(kù)，建立了用戶知識(shí)偏好矩陣，通過基于協(xié)同過濾的方法實(shí)現(xiàn)了個(gè)性化推薦。而推薦算法的使用存在一些弊端，基于內(nèi)容的方法推薦的信息范圍過于狹窄；對(duì)于協(xié)同過濾方法，如用戶評(píng)分?jǐn)?shù)據(jù)少，產(chǎn)生數(shù)據(jù)稀疏性問題；而基于知識(shí)的推薦需要挖掘難以獲取的領(lǐng)域知識(shí)和推理技術(shù)；基于社會(huì)媒體的技術(shù)是將用戶的社會(huì)關(guān)系和其他社會(huì)媒體數(shù)據(jù)運(yùn)用到旅游推薦當(dāng)中，但是獲取社會(huì)信任關(guān)系還是當(dāng)前社會(huì)推薦需要解決的問題。相對(duì)于其他三種方法，基于協(xié)同推薦的方法使用更普遍，本文將此方法和改進(jìn)的算法進(jìn)行對(duì)比。

根據(jù)上述分析，本文提出一種新的面向旅游用戶的個(gè)性化搜索推薦模型。因?yàn)橛脩粜枨蟆a(chǎn)品偏好，以及約束條件可以在用戶閱覽的旅游信息中反映，所以通過TextRank方法對(duì)用戶搜索和閱覽的歷史關(guān)鍵詞進(jìn)行頻繁集挖掘，生成用戶傾向性詞典；然后根據(jù)用戶當(dāng)前搜索關(guān)鍵詞，利用MC-Apriori算法關(guān)聯(lián)挖掘用戶傾向性詞典，從而向用戶推薦滿足其當(dāng)前興趣傾向的旅游信息。該模型在保障推薦結(jié)果準(zhǔn)確、多樣和個(gè)性的基礎(chǔ)上，還解決了旅游個(gè)性化推薦面臨的特殊問題，提高了效率。

2 相關(guān)知識(shí)

2.1 TextRank算法抽取文本關(guān)鍵詞

TextRank[13]是比較常用的文本關(guān)鍵詞抽取方法，該方法實(shí)質(zhì)是一種基于圖的排序算法。同一文本中大多數(shù)詞語(yǔ)都是為表達(dá)同一主題，詞語(yǔ)與詞語(yǔ)之間也存在一定的語(yǔ)義關(guān)系，將詞語(yǔ)看做圖中的頂點(diǎn)，頂點(diǎn)之間通過有向邊反映它們之間的關(guān)系?；趫D的排序算法的基本理論，在具有語(yǔ)義關(guān)系的詞語(yǔ)之間建立連線構(gòu)建TextRank模型，根據(jù)詞語(yǔ)之間的相互“投票”遞歸計(jì)算詞語(yǔ)的值，而每個(gè)詞語(yǔ)值的大小取決于其詞語(yǔ)投票分?jǐn)?shù)和投票詞自身的值大小，值較大的詞語(yǔ)視為重要詞語(yǔ)。其中不和任何詞語(yǔ)有連線的詞語(yǔ)為孤立點(diǎn)。本文通過TextRank方法對(duì)用戶搜索內(nèi)容和閱覽文本信息進(jìn)行關(guān)鍵詞挖掘。遞歸計(jì)算公式如式(1)。

其中，d為阻尼系數(shù)，代表從圖中某一特定點(diǎn)指向其他任意點(diǎn)的概率，WS(Vi)為頂點(diǎn)Vj即詞j的得分，Link(Vi)為與點(diǎn)Vi有連線的點(diǎn)的集合。

2.2 利用word2vec查找語(yǔ)義相似詞語(yǔ)

Word2vec[14]是Google于2013年開源的一款將詞語(yǔ)表征為實(shí)數(shù)值向量的高效工具，其利用深度學(xué)習(xí)(Deep Learning)的思想，通過訓(xùn)練，把文本內(nèi)容的處理簡(jiǎn)化為K維向量空間中的向量運(yùn)算，而向量空間上的相似度可以用來(lái)表示文本語(yǔ)義上的相似度。Word2vec已經(jīng)被廣泛的應(yīng)用于很多NLP(Nature Language Processing)相關(guān)的工作中，如情感分析、詞性分析和聚類等。

鑒于此，本文采用word2vec將用戶傾向性詞典中的每個(gè)關(guān)鍵詞生成一個(gè)200維的向量，然后通過向量與向量之間的余弦距離來(lái)計(jì)算詞語(yǔ)之間的相似度，計(jì)算公式如式(2)。

(2)

其中，公式2中ei是語(yǔ)料句子中第i個(gè)詞，fj是目標(biāo)句子中第j個(gè)詞，第i個(gè)詞和第j個(gè)詞之間的相似度用Sim(ei,fj)表示，分子表示ei與fj的200維向量的乘積，當(dāng)cos相似度大于0.6時(shí)，表示兩個(gè)詞相似。

word2vec查找語(yǔ)義相似詞語(yǔ)的具體操作如下：

(1)配置word2vec工具；

(2)挖掘康輝旅行社的文本語(yǔ)料；

(3)使用NLPIR2013工具(http://ictclas.nlpir.org/)?對(duì)每個(gè)語(yǔ)料進(jìn)行分詞；

(4)將分好的語(yǔ)料進(jìn)行訓(xùn)練。

(5)得到模型文件。文件中存儲(chǔ)著文檔中的詞語(yǔ)和其對(duì)應(yīng)的向量。

(6)利用公式2計(jì)算，比較詞語(yǔ)的相似性，若cos大于0.6時(shí)，表示兩個(gè)詞相似，否則不相似。

2.3 Apriori算法及矩陣聚類改進(jìn)算法

2.3.1 Apriori算法

Apriori算法[15]是一種挖掘布爾型關(guān)聯(lián)規(guī)則頻繁集項(xiàng)的算法，在數(shù)據(jù)挖掘中具有里程碑的作用。它的結(jié)構(gòu)簡(jiǎn)單，沒有復(fù)雜的推導(dǎo)，易于理解。項(xiàng)集(Itemset)簡(jiǎn)單地說就是項(xiàng)的集合，包含k個(gè)項(xiàng)的集合稱為k-項(xiàng)集，譬如3-項(xiàng)集{l1，l2，l3}。一個(gè)項(xiàng)集的支持度(Support Count)為該項(xiàng)集出現(xiàn)頻度，即整個(gè)數(shù)據(jù)集中包含該項(xiàng)集的記錄個(gè)數(shù)。若某項(xiàng)集出現(xiàn)的頻度大于一定的頻度閾值則成為頻繁項(xiàng)集。頻繁k-項(xiàng)集集合計(jì)作Lk，其頻度記support_count(Lk)。通過逐層搜索迭代的方法來(lái)完成頻繁項(xiàng)集的挖掘工作。即利用k-項(xiàng)集探察(k+1)-項(xiàng)集,來(lái)窮盡數(shù)據(jù)集中所有頻繁項(xiàng)集,直到不能再找到任何頻繁k-項(xiàng)集。最后在所有的頻繁集中找出強(qiáng)規(guī)則，即產(chǎn)生用戶感興趣的關(guān)聯(lián)規(guī)則。

但隨著挖掘數(shù)據(jù)庫(kù)的不斷增大，應(yīng)用Apriori算法時(shí)每次迭代產(chǎn)生候選項(xiàng)目集以及統(tǒng)計(jì)其支持度非常耗時(shí)。為了提高效率，Apriori算法的一系列改進(jìn)算法主要在以下方面進(jìn)行優(yōu)化：1)減少掃描數(shù)據(jù)庫(kù)的次數(shù)；2)減少生成候選項(xiàng)目及的數(shù)目。

Apriori算法的流程圖，如圖1所示。

圖1 Apriori算法流程圖

2.3.2 MC-Apriori 算法

針對(duì)旅游數(shù)據(jù)稀疏、復(fù)雜且龐大的特點(diǎn)，以及Apriori算法的不足，提出了一種MC-Apriori算法，該算法以減少掃描數(shù)據(jù)庫(kù)的次數(shù)和數(shù)據(jù)庫(kù)規(guī)模為目的，只需掃描數(shù)據(jù)庫(kù)一次，生成聚類矩陣來(lái)代替原來(lái)的事務(wù)數(shù)據(jù)庫(kù)，在生成頻繁項(xiàng)集時(shí)，也只需對(duì)部分聚類矩陣進(jìn)行相應(yīng)運(yùn)算，因而可以大大提高算法的運(yùn)算效率，最后在生成的所有頻繁項(xiàng)集中去挖掘包含用戶當(dāng)前搜索關(guān)鍵詞的最大項(xiàng)集。

定義1：每個(gè)項(xiàng)Ij的向量定義為：

定義2：2-項(xiàng)集{IiIj}的向量定義為：

定義3：k-項(xiàng)集{I1I2…Ik}的支持度計(jì)數(shù)為：

定義4 項(xiàng)集I的矩陣D：

項(xiàng)集I轉(zhuǎn)換為D’的表示如下：

為提高Apriori算法在旅游推薦系統(tǒng)中的效率，將相似的事務(wù)在數(shù)據(jù)庫(kù)中進(jìn)行標(biāo)記(本文中稱“相似記錄個(gè)數(shù)”記為(α1,α2,…,p)-1，p為矩陣的行數(shù)，根據(jù)該事務(wù)在D中對(duì)于的某行加上出現(xiàn)的“相似記錄個(gè)數(shù)”。從而獲得數(shù)據(jù)的矩陣D″：

將D″中的值與D矩陣進(jìn)行比較，若D中的項(xiàng)為0，則將D″相同位置也標(biāo)記為0，否則，不改變。最后獲得D矩陣。

算法過程如下：

②通過Lk-1與自己自然連接產(chǎn)生候選k-項(xiàng)集的集合Ck。當(dāng)k=2時(shí)，對(duì)于候選項(xiàng)集合C2，直接根據(jù)定義2算出個(gè)各項(xiàng)集的支持度計(jì)數(shù)，然后轉(zhuǎn)③。

③分別取候選k-項(xiàng)集Ck中的每個(gè)項(xiàng)集與L2中的元素進(jìn)行比較，如果不在L2中，則該候選項(xiàng)集是非頻繁的，將其從Ck中刪除從而達(dá)到初步剪枝。因?yàn)楹蜻xk-項(xiàng)集Ck的集合中每個(gè)項(xiàng)集的長(zhǎng)度為k，所以不必考慮小于k的聚類矩陣。先在聚類矩陣MC(k)中利用列向量間的*運(yùn)算求出Ck中每個(gè)候選項(xiàng)集對(duì)應(yīng)的列向量，再通過列元素求和來(lái)計(jì)算器支持度計(jì)數(shù)。如果大于等于min_sup，則將該候選k-項(xiàng)集放到頻繁k-項(xiàng)集Lk中，否則繼續(xù)在聚類矩陣MC(k+1)中統(tǒng)計(jì)此項(xiàng)集的支持度計(jì)數(shù)，并將其累加到前次的計(jì)數(shù)中，直到大于或等于min_sup，或者到達(dá)了最后聚類矩陣MC(n)而終止。

④循環(huán)②③步，直到候選集Ck為空而停止。得到所有的頻繁項(xiàng)集。

⑤若最大頻繁集中的項(xiàng)數(shù)個(gè)數(shù)小于當(dāng)前搜索關(guān)鍵詞KEY的個(gè)數(shù)，則向用戶推薦以“KEY為關(guān)鍵詞的文本”；否則遍歷所有頻集，找出以KEY為真子集且頻度最大的項(xiàng)集，向用戶推薦以該頻繁集為關(guān)鍵詞的旅游信息，否則，若遍歷結(jié)果為空時(shí)，則向用戶推薦以“KEY為關(guān)鍵詞的文本”。

根據(jù)以上思想，基于MC-Apriori算法推薦的偽代碼描述如下：

輸入：用戶當(dāng)前搜索關(guān)鍵詞集KEY={k1，k2，…，kq}(q為關(guān)鍵詞的個(gè)數(shù))；用戶傾向性詞典I；最小支持度閾值min_sup。

輸出： L： 推薦給用戶的關(guān)鍵詞集GEN_KEY。

方法：

1)D=Cluster_Matrix_Create(I,min_sup)；

//Cluster_Matrix_Create(k)此為生成聚類矩陣算法。

2)for(k=2;Lk-1≠;k++){

Ck=Candidate_Itemset_Gen(Lk-1);

Lk=Large_Itemset_Gen(Ck);}

3)if q≥p(p為最大頻繁集項(xiàng)數(shù)) then GEN_KEY=“以KEY為關(guān)鍵詞的文本”。

4)temp_L=max_key_frequent(Lk);//遍歷所有頻繁集Lk。q

End

改進(jìn)的Apriori算法結(jié)構(gòu)圖如圖2所示。

圖2 改進(jìn)的Apriori算法結(jié)構(gòu)圖

目前，基于Apriori的改進(jìn)算法層出不窮，此算法不僅可以滿足對(duì)用戶傾向性詞典的挖掘，而且可以很友好的處理龐大，稀疏復(fù)雜的旅游領(lǐng)域數(shù)據(jù)，本算法的時(shí)間復(fù)雜度為O(n)～O(n2)。

3 基于MC-Apriori算法的旅游個(gè)性化推薦模型

在旅游網(wǎng)站中的搜索時(shí)，用戶輸入的關(guān)鍵詞往往會(huì)比較集中，且和當(dāng)前主題相關(guān)；考慮用戶的個(gè)性習(xí)慣，輸入的關(guān)鍵詞分布應(yīng)該不會(huì)太廣泛。針對(duì)用戶特定的行為習(xí)慣，利用MC-Apriori可以比較容易準(zhǔn)確地搜索出用戶傾向性詞典中達(dá)到一定頻度閾值的關(guān)鍵詞頻繁集。

本文引入了用戶的閱覽文本內(nèi)容，在用戶模糊交互且旅游數(shù)據(jù)龐大、復(fù)雜、稀疏的情況下，用戶閱覽文本內(nèi)容可以反映出用戶當(dāng)前的興趣傾向，并且確保推薦內(nèi)容的準(zhǔn)確、多樣；且每個(gè)用戶會(huì)產(chǎn)生個(gè)自的用戶傾向性詞典，則保證了推薦信息的個(gè)性化。同時(shí)利用MC-Apriori算法，不僅可以減少工作量，而且提高了運(yùn)算效率?；贛C-Apriori算法的旅游個(gè)性化推薦模型,如圖3所示。

圖3 基于MC-Apriori算法的旅游個(gè)性化推薦模型

如圖3所示，首先借助TextRank算法對(duì)用戶的搜索關(guān)鍵詞進(jìn)行挖掘并按時(shí)間排序，存儲(chǔ)在用戶個(gè)性化詞典中；同理利用TextRank算法挖掘用戶搜索后瀏覽文本內(nèi)容的前1/8個(gè)旅游領(lǐng)域的關(guān)鍵詞；將此內(nèi)容關(guān)鍵詞集和用戶個(gè)性化詞典進(jìn)行合并且按時(shí)間排序，通過word2vec工具比較每?jī)尚杏涗?，將語(yǔ)義相似且ID小的記錄刪除并標(biāo)記，存儲(chǔ)在容量固定的用戶傾向性詞典中；最后通過MC-Apriori算法對(duì)用戶傾向性詞典進(jìn)行挖掘，得到推薦信息。

3.1 用戶傾向性詞典模塊設(shè)計(jì)

本文提出的旅游推薦模型，關(guān)鍵是對(duì)用戶的傾向性詞典進(jìn)行挖掘分析并記錄。如圖4所示，模型中為每用戶建立一個(gè)用戶個(gè)性化詞典、內(nèi)容關(guān)鍵詞集和用戶傾向性詞典數(shù)據(jù)模塊，各模塊中的記錄按照用戶的搜索時(shí)間升序排列，ID越大表示用戶搜索的時(shí)間越靠近當(dāng)前，并且定義用戶傾向性詞典的容量為用戶個(gè)性化詞典和內(nèi)容關(guān)鍵詞集容量的和，固定的容量不僅可以使記錄都是用戶近期感興趣的信息，而且也節(jié)約了存儲(chǔ)空間，提高了MC-Apriori運(yùn)算效率。當(dāng)用戶進(jìn)行搜索查看時(shí)，將挖掘的關(guān)鍵詞記錄到對(duì)應(yīng)的表中，隨著記錄不斷增加，當(dāng)記錄達(dá)到一定的容量，按照LRU(最近最久未使用)算法存儲(chǔ)記錄。此外，通過word2vec工具對(duì)比用戶傾向性詞典中每?jī)尚杏涗?，將語(yǔ)義相似且ID小的記錄刪除并在“相似記錄個(gè)數(shù)”中加1。

圖4 用戶存儲(chǔ)模塊結(jié)構(gòu)

3.2 評(píng)測(cè)指標(biāo)

推薦系統(tǒng)效果評(píng)估是一個(gè)困難的問題，常見的評(píng)估指標(biāo)可以分為準(zhǔn)確度、多樣性、新穎性和覆蓋率四大類。針對(duì)旅游領(lǐng)域的特殊性和復(fù)雜性，根據(jù)傳統(tǒng)的推薦系統(tǒng)性能評(píng)測(cè)指標(biāo)，本文采用以下指標(biāo)對(duì)算法性能評(píng)估。

1)綜合評(píng)價(jià)指標(biāo)(F-Measure)

2)效率

4 實(shí)驗(yàn)舉例

將本算法在對(duì)收集的康輝旅行社的語(yǔ)料數(shù)據(jù)上測(cè)試。對(duì)于某一個(gè)用戶，當(dāng)前用戶傾向性詞典表，如表1所示。

表1 用戶傾向性詞典表

如表1所示，該用戶到目前為止搜索和閱覽文本總數(shù)為13次，設(shè)置用戶傾向性詞典的容量為120條記錄，其中I1到I10分別代表昆明、景點(diǎn)、黑龍?zhí)丁⒚坊?、門票、道館、泉眼、公園、保險(xiǎn)、團(tuán)購(gòu)這10個(gè)關(guān)鍵詞，當(dāng)前與ID=5的記錄{I1，l3，I4，I7，I8}語(yǔ)義相似的個(gè)數(shù)為1，與ID的記錄{I1，l3，I4，I8}語(yǔ)義相似的個(gè)數(shù)為3，用戶當(dāng)前搜索關(guān)鍵詞(ID=9)為{I1，I4}。

當(dāng)前用戶在搜索框中輸入關(guān)鍵詞{昆明，梅花}時(shí)，首先將搜索關(guān)鍵詞經(jīng)過word2vec更新用戶傾向性詞典表，然后采用MC-Apriori算法進(jìn)行頻繁項(xiàng)集的挖掘，令min_sup為2。過程如下：

1)掃描事務(wù)數(shù)據(jù)庫(kù)一次,獲得項(xiàng)集I的矩陣D。生成聚類矩陣CM(k)，k為2,3,4,5,10,16。

CM(5)=(1011010100)

CM(10)=(2022002200)

CM(16)=(4044000400)

同法可計(jì)算出：I3,I4,I5,I6,I7,I8,I9,I10與2相比的大小，所以生成頻繁1-項(xiàng)集L1={I1,I3,I4,I5,I8}，由此可直接排除I2,I6,I7,I9,I10。

2)L1=與自己自然連接產(chǎn)生候選2-項(xiàng)集的集合

C2={I1I3,I1I4,I1I5,I1I8,I3I4,I3I5,I3I8,I4I5,I4I8,I5I8}。在CM(2)中，因?yàn)?/p>

3)L2與自己自然連接產(chǎn)生候選3-項(xiàng)集的集合C3={I1I3I4,I1I3I5,I1I3I8,I1I4I5,I1I4I8,I1I5I8,I3I4I5,I3I4I8,I3I5I8},由于{I4I5,I5I8}是非頻繁2-項(xiàng)集，所以{I1I4I5,I1I5I8,I3I4I5,I3I5I8}從C3中刪除，因此只需考{I1I3I4,I1I3I5,I1I3I8,I1I4I8,I3I4I8}的支持度計(jì)數(shù)。由于k=3>2,所以只需從聚類矩陣MC(3)考慮，

1+0+1=2≥2

同理，可以計(jì)算其他候選集的支持度，得到的頻繁3-項(xiàng)集L3={I1I3I4,I1I3I5,I1I3I8,I1I4I8,I3I4I8}。

4)L3與自己自然連接產(chǎn)生候選4-項(xiàng)集的集合C4={I1I3I4I5,I1I3I4I8,I1I3I5I8},由于{I4I5,I5I8}是非頻繁2-項(xiàng)集，所以將{I1I3I4I5,I1I3I5I8},從C4中刪除，實(shí)現(xiàn)剪枝，同3),計(jì)算出{I1I3I4I8}的支持度,得L4={I1I3I4I8}，算法終止，找出了所有的頻繁項(xiàng)集。

5) 因?yàn)樽畲箜?xiàng)集的項(xiàng)數(shù)為4≥2(2為當(dāng)前搜索關(guān)鍵詞的個(gè)數(shù))，則在所有頻繁項(xiàng)集中找出以{昆明，梅花}為真子集的項(xiàng)數(shù)最大的頻繁集，即{昆明、黑龍?zhí)?、梅花、公園}。

6)向用戶推薦以該頻繁集為關(guān)鍵詞的旅游信息。

MC-Apriori算法、Apriori算法以及協(xié)同過濾算法在收集的康輝旅行社的語(yǔ)料數(shù)據(jù)中多次試驗(yàn)所花費(fèi)時(shí)間的平均值如表2所示。

表2 不同方法在多次試驗(yàn)下的所需時(shí)間評(píng)均值 /毫秒

MC-Apriori算法以及協(xié)同過濾算法隨著語(yǔ)料的遞增F值大小變化，如圖5所示。

圖5 二種算法隨著語(yǔ)料的遞增F值大小變化

從表2中可以觀察得到，測(cè)試中MC-Apriori算法所需的平均時(shí)間小于Apriori算法與基于協(xié)同過濾的算法。圖5中，隨著語(yǔ)料的增加，F(xiàn)值增大，且MC-Apriori的F值大于于協(xié)同過濾的算法。當(dāng)語(yǔ)料增加到一定程度上，F(xiàn)值趨于穩(wěn)定。

MC-Apriori算法在第一次對(duì)數(shù)據(jù)庫(kù)掃描的同時(shí)根據(jù)事務(wù)中項(xiàng)的和生成不同的聚類矩陣，只需對(duì)部分聚類矩陣計(jì)算就可以產(chǎn)生頻繁項(xiàng)集，減少了每次掃描全部數(shù)據(jù)庫(kù)所需要的開銷，提高了算法的效率。因?yàn)槁糜螖?shù)據(jù)復(fù)雜，基于協(xié)同過濾算法的推薦模型中很難準(zhǔn)確描述這些數(shù)據(jù)，而用戶的閱覽信息可以很好的反映用戶的旅游需求和對(duì)旅游產(chǎn)品的偏好，以及約束條件，所以本文提出的模型提高了準(zhǔn)確率。且MC-Apriori算法時(shí)間復(fù)雜度為O(n)～O(n2)，基于協(xié)同過濾算法為O(m2*n)，Apriori算法為O(m*n2)，所以效率也提高了。通過對(duì)收集的康輝旅行社的語(yǔ)料數(shù)據(jù)測(cè)試，F(xiàn)值提升了5%。

5 總結(jié)

本文針對(duì)個(gè)性化推薦在旅游領(lǐng)域面臨的特殊問題，提出了一種通過矩陣聚類的Apriori改進(jìn)的方法，該算法只需對(duì)數(shù)據(jù)庫(kù)掃描一次并生成一系列不同的聚類矩陣，而只需要對(duì)部分聚類矩陣計(jì)算就可以產(chǎn)生頻繁項(xiàng)集。引入用戶的閱覽內(nèi)容，不僅反映用戶當(dāng)前的興趣傾向，且保證推薦內(nèi)容的準(zhǔn)確、多樣及個(gè)性，同時(shí)利用改進(jìn)Apriori算法提高了搜索效率，減少了工作量。通過對(duì)收集的康輝旅行社的語(yǔ)料數(shù)據(jù)大量測(cè)試，論證了本文提出的旅游推薦模型相比較傳統(tǒng)的推薦模型具有一定的應(yīng)用價(jià)值。為了更好的推薦結(jié)果，推薦算法有待進(jìn)一步研究。

[1] 喬向杰,張凌云.近十年國(guó)外旅游推薦系統(tǒng)的應(yīng)用研究[J].旅游學(xué)刊.2014(08).

[2] JANNACH D,ZANKER M, FUCHS M.Constraint-based recommendation in tourism:a multi-perspective case study[J]. Journal of Information Technology and Tourism, 2009, 11(2):139- 155.

[3] Ricci F, Rokach L, Shapira B.Introduction to recommender systems handbook[A].//:Recommender Systems Handbook[M]. New York: Springer, 2011：1-35.

[4] 張晗,潘正運(yùn),張燕玲.旅游服務(wù)智能推薦系統(tǒng)的研究與設(shè)計(jì)[J].微計(jì)算機(jī)信息, 2006,22(5-3):170-171.

[5] FENZA G, FISCHETTI E, FURNO D, et al. A hybrid context aware system for tourist guidance based on collaborative filtering[A].FENZA G.The IEEE International Conference on Fuzzy Systems[C].New Jersey: IEEE Press, 2004：259-262.

[6] 文益民,史一帆,蔡國(guó)永,繆裕青,龍剛.個(gè)性化旅游推薦研究綜述[A].2015中國(guó)旅游科學(xué)年會(huì)論文集[C]. 2015.

[7] GE Y, LIU Q, XIONG H, et al. Cost-aware travel tour recommendation[A].GE Y.ACM SIGKDD Conference[C]. New York: ACM Press, 2011:983-991.

[8] RICCI F. Travel recommender systems[J].IEEE Intelligent systems, 2002：55-57.

[9] JIANG K, WANG P, YU N H. ContextRank:personalized tourism recommendation by exploiting context information of geotagged web photos[A]. The 6th International Conference on Image and Graphics[C]. New Jersey: IEEE Press, 2011: 931-937.

[10] 王顯飛,陳梅,李小天.基于約束的旅游推薦系統(tǒng)的研究與設(shè)計(jì)[J]. 計(jì)算機(jī)技術(shù)與發(fā)展,2012:141-145.

[11] BUSTOS F, LOPEZ J, JULIAN V, et al. STRS: Social network based recommender system for tourism Enhanced with trust[A]. BUSTOS F. Distributed Computing and Artificial Intelligence[C]. Berlin: Springer, 2008: 71-79.

[12] MAJID A, CHEN L, CHEN G, et al.A context-aware personalized travel recommendation system based on geotagged socialmedia datamining[J].International Journal of Geographical Information Science. 2012,27(4): 662-684.

[13] 楊潔,季鐸,蔡?hào)|風(fēng),代翠.基于TextRank的多文檔關(guān)鍵詞抽取技術(shù)[A]. 第四屆全國(guó)信息檢索與內(nèi)容安全學(xué)術(shù)會(huì)議論文集(上)[C]. 2008.

[14] 羅杰.王慶林.李原基于word2vec與語(yǔ)義相似度的領(lǐng)域詞語(yǔ)聚類[C]. 2014.

[15] TANG J, HU X, LIU H. Social recommendation:a review[J]. Social Network Analysis and Mining, 2013,3(4): 1113-1133.