基于規(guī)則的推薦算法分析和實(shí)現(xiàn)

段繼光 李建俊 仇賓

（河北師范大學(xué)附屬民族學(xué)院 河北省石家莊市 050091）

隨著互聯(lián)網(wǎng)技術(shù)突飛猛進(jìn)的發(fā)展和智能終端的廣泛普及，信息數(shù)據(jù)爆炸式增長(zhǎng)。面對(duì)海量的信息數(shù)據(jù)，用戶無法有效從中獲取自己真正需要的信息，產(chǎn)生了所謂的信息超載（information overload）問題[1]。

推薦系統(tǒng)是一種可用來解決信息超載問題的技術(shù)方法。與搜索引擎一樣，推薦系統(tǒng)也是一種幫助用戶查找有用信息的工具。但是推薦系統(tǒng)和搜索引擎又有所不同，搜索引擎實(shí)現(xiàn)了用戶有明確目的時(shí)的主動(dòng)查找需求，而推薦系統(tǒng)可以在用戶沒有明確目的的時(shí)候幫助他們發(fā)現(xiàn)感興趣的新內(nèi)容[2]。

推薦系統(tǒng)可以應(yīng)用到許多互聯(lián)網(wǎng)應(yīng)用中，比如基于位置信息的在線購物系統(tǒng)中，由于系統(tǒng)中的商品很多，有效地推薦用戶可能感興趣的、并位于特定位置范圍內(nèi)的商品，是實(shí)用且有價(jià)值的系統(tǒng)功能。推薦功能可幫助用戶高效地查找其感興趣的商品，提升系統(tǒng)的使用體驗(yàn)和用戶黏性，使系統(tǒng)產(chǎn)生更好的效益。

1 推薦系統(tǒng)

推薦系統(tǒng)通過分析用戶行為記錄，對(duì)用戶興趣進(jìn)行建模，然后主動(dòng)給用戶推薦可以滿足其興趣和需求的信息。推薦系統(tǒng)由用戶建模、推薦對(duì)象建模、推薦算法三個(gè)功能模塊組成。

推薦系統(tǒng)的三個(gè)功能模塊中，核心部分是推薦算法。當(dāng)前，推薦算法主要分為：基于關(guān)聯(lián)規(guī)則的推薦(Association Rule-based Recommendation)、基于內(nèi)容的推薦（Contentbased Recommendation）、協(xié)同過濾推薦（Collaborative Filtering Recommendation）、基于效用推薦（Utility-based Recommendation）、基于知識(shí)推薦（Knowledge-based Recommendation）、組合推薦等（Hybrid Recommendation）[3]。

2 基于關(guān)聯(lián)規(guī)則的推薦算法

基于關(guān)聯(lián)規(guī)則的推薦算法，是依據(jù)特定關(guān)聯(lián)規(guī)則（數(shù)據(jù)之間隱含的關(guān)聯(lián)性），在系統(tǒng)中查找符合關(guān)聯(lián)規(guī)則的項(xiàng)目，并通過特定指標(biāo)（置信度）對(duì)找到的結(jié)果項(xiàng)目進(jìn)行排序，生成推薦結(jié)果推送給用戶。

基于關(guān)聯(lián)規(guī)則的推薦算法的主要操作過程：

（1）利用關(guān)聯(lián)規(guī)則挖掘算法，在系統(tǒng)中查找關(guān)聯(lián)規(guī)則，這些關(guān)聯(lián)規(guī)則需要滿足支持度和置信度閾值要求，我們將找到的關(guān)聯(lián)規(guī)則集合記為R。關(guān)聯(lián)規(guī)則挖掘算法主要有如下幾種：FP-tree、DHP、Apriori、Apriori Tid 等算法。

（2）在集合R 中，使用迭代遍歷查找被用戶支持的關(guān)聯(lián)規(guī)則，我們將其記為R1。所謂被用戶支持的關(guān)聯(lián)規(guī)則，指的是在規(guī)則前邊的項(xiàng)目集，是用戶曾訪問（這里的訪問是指瀏覽、添加購物車、下單購買等操作）過的項(xiàng)目集。

（3）查找那些用戶沒有訪問過，但是被關(guān)聯(lián)規(guī)則R1 預(yù)測(cè)到的項(xiàng)目，這些項(xiàng)目組成的集合記為P。

（4）對(duì)集合P 中的項(xiàng)目，根據(jù)它們?cè)陉P(guān)聯(lián)規(guī)則R1 中置信度值的大小，將這些項(xiàng)目排序，排名靠前的項(xiàng)目作為算法執(zhí)行結(jié)果。需要特別說明的是，如果出現(xiàn)某個(gè)項(xiàng)目被若干個(gè)規(guī)則同時(shí)預(yù)測(cè)到，就從中選取具有最大置信度的規(guī)則為依據(jù)，進(jìn)行排序，生成推薦結(jié)果。

圖1：Apriori 算法偽碼

圖2：Apriori 算法Java 模擬程序代碼

2.1 關(guān)聯(lián)規(guī)則

我們將數(shù)據(jù)之間的隱含關(guān)聯(lián)性關(guān)系稱為關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則的定義如下：

設(shè)數(shù)據(jù)項(xiàng)（Item）的集合為I ={i1,i2,is,...,im},事務(wù)(Transaction)的集合為T = {t1,t2,t3,…,tm}，而且事務(wù)集合T 中的任一個(gè)事務(wù)ti，均為數(shù)據(jù)項(xiàng)集合I 的一個(gè)子集。

關(guān)聯(lián)規(guī)則可以用（1）式形式化表示：

在（1）式中，集合A 和B 為數(shù)據(jù)項(xiàng)集合I 的非空子集，稱為項(xiàng)目集（Item Set），其中集合A 是規(guī)則前件，集合B 是規(guī)則后件，分別簡(jiǎn)稱為前件和后件。

我們通過某個(gè)消費(fèi)者在線商城購物為例分析：假設(shè)用戶將牛奶、咖啡、糖三種商品加入購物車并下單購買，那么集合{牛奶，咖啡，糖}就構(gòu)成了一個(gè)事務(wù)，在線商城系統(tǒng)中的所有商品組成的集合就是數(shù)據(jù)項(xiàng)集。而“牛奶→咖啡，糖”就是一個(gè)關(guān)聯(lián)規(guī)則，規(guī)則的前件集合A 為{牛奶}，后件集合B 為{咖啡，糖}，為簡(jiǎn)便書寫，可以將關(guān)聯(lián)規(guī)則中事務(wù)的花括號(hào)略去不寫。

圖3：Apriori 算法模擬程序運(yùn)行結(jié)果

2.2 支持度和置信度

我們?cè)鯓訉?duì)關(guān)聯(lián)規(guī)則進(jìn)行評(píng)價(jià)和衡量呢？通常使用下列兩個(gè)重要指標(biāo)：支持度（Support）和置信度（Confidence）。

2.2.1 支持度

針對(duì)關(guān)聯(lián)規(guī)則 A → B，其支持度是指在事務(wù)集合T 中數(shù)據(jù)項(xiàng)A和B 同時(shí)出現(xiàn)的概率，形式化定義如（2）式所示：

若支持度值越大，表示規(guī)則左右兩個(gè)事務(wù)同時(shí)發(fā)生的幾率大；相反，支持度值越小，表示規(guī)則左右兩個(gè)事務(wù)同時(shí)發(fā)生的幾率小。若支持度的值很小，表示此關(guān)聯(lián)規(guī)則基本不成立。

2.2.2 置信度

針對(duì)關(guān)聯(lián)規(guī)則 A → B，其置信度是指在事務(wù)集合T 中，如果A出現(xiàn)，B 也同時(shí)出現(xiàn)的概率，形式化定義如（3）所示：

如果置信度值越大，此關(guān)聯(lián)規(guī)則就越可能成立；反之，表明此關(guān)聯(lián)規(guī)則成立的可能性就越小。也就是說，置信度的值與關(guān)聯(lián)規(guī)則成立的可能性大小成正比。

假定系統(tǒng)最小支持度是30%，最小置信度是70%，我們可從中找到下面的關(guān)聯(lián)規(guī)則：

r=咖啡→牛奶,

通過分析，可知關(guān)聯(lián)規(guī)則r 的支持度為：Support(r)=3/6=50% ,大于最小支持度閾值30%；置信度為：Confidence(r)=3/4=75%，比最小置信度閾值70%大，故可得r 是成立的。

3 Apriori算法

通過前文分析，已知確定一條關(guān)聯(lián)規(guī)則的途徑。但是我們需要找到系統(tǒng)中全部的關(guān)聯(lián)規(guī)則，怎樣實(shí)現(xiàn)這個(gè)目標(biāo)？對(duì)此，我們通過利用Apriori 算法加以實(shí)現(xiàn)。Apriori 算法主要包括兩個(gè)步驟：

（1）通過迭代遍歷，查找到事務(wù)數(shù)據(jù)庫中的全部頻繁項(xiàng)集，即支持度比系統(tǒng)設(shè)定的支持度閾值大于或等于的項(xiàng)目集；

（2）利用第一步操作中得到的頻繁項(xiàng)集，構(gòu)造得到符合系統(tǒng)最小置信度閾值要求的關(guān)聯(lián)規(guī)則。

Apriori 算法的偽碼如圖1所示。

Apriori 算法中的兩個(gè)主要操作步驟通常被稱作連接和剪枝，其具體操作過程如下：

3.1 連接

此操作是指為了找到頻繁k 項(xiàng)集。具體步驟是：根據(jù)系統(tǒng)設(shè)定的最小支持度閾值，首先在1 項(xiàng)候選集C1中，將所有小于最小支持度閾值的項(xiàng)集刪除掉，就得到1 項(xiàng)頻繁項(xiàng)集L1。然后將L1自身連接，生成的集合為兩項(xiàng)候選集C2，同理，刪除掉C2中小于最小支持度的項(xiàng)集，就得到兩項(xiàng)頻繁項(xiàng)集L2。以此類推，可以通過將Lk-1和L1鏈接，生成候選集Ck，然后刪除Ck中低于最小支持度閾值的元素，得到頻繁k 項(xiàng)集Lk。這一步操作中，主要操作是頻繁項(xiàng)集的連接，因此簡(jiǎn)稱為連接。

3.2 剪枝

因?yàn)楹蜻x集Ck是頻繁集Lk的超集，所以不能確定候選集Ck中的哪些元素是頻繁的，哪些不是頻繁的。對(duì)此，掃描候選集Ck中的元素，將元素的支持度和支持度閾值比較，來判斷元素是否為頻繁的。為了降低復(fù)雜度，我們可以對(duì)候選集Ck進(jìn)行剪枝壓縮處理。通過Apriori 性質(zhì)可知：頻繁項(xiàng)集的任一非空子集都是頻繁的。所以在掃描過程中，若發(fā)現(xiàn)候選頻繁項(xiàng)集的某個(gè)非空子集不是頻繁的，就可以確定該候選頻繁項(xiàng)集肯定就不是頻繁的，進(jìn)而從Ck中刪除掉這個(gè)頻繁項(xiàng)集，實(shí)現(xiàn)對(duì)候選集Ck的壓縮，提高了處理效率。

通過連接和剪枝兩個(gè)操作，就可以得到系統(tǒng)中所有的頻繁項(xiàng)集。對(duì)每一個(gè)頻繁項(xiàng)集l 的非空子集s，若滿足下式：

可得到關(guān)聯(lián)規(guī)則：s →(l-s)。

4 基于Apriori算法推薦功能模擬實(shí)現(xiàn)

通過前面對(duì)Apriori 算法的分析，編寫了該算法的Java 模擬程序，程序部分代碼如圖2所示。

運(yùn)行結(jié)果如圖3所示。

在圖3 中，程序運(yùn)行結(jié)果中包含2；-＞1；:0.75 的信息，置信度為0.75，大于0.7 的置信度閾值，表明關(guān)聯(lián)規(guī)則“咖啡→牛奶”是有效的，即若用戶的歷史行為中包含咖啡商品的話，就向其推薦牛奶商品，這和本文前面的分析是一致的。

5 結(jié)論

本文簡(jiǎn)要討論了推薦系統(tǒng)，和基于規(guī)則的推薦算法Apriori 算法，并模擬實(shí)現(xiàn)該算法。但如果要在實(shí)際環(huán)境中使用，還存在下列兩個(gè)問題：

（1）如何在實(shí)際在線購物系統(tǒng)中添加本文中討論的推薦系統(tǒng)功能？對(duì)此，我們可以將推薦系統(tǒng)功能實(shí)現(xiàn)為在線購物系統(tǒng)的一個(gè)后臺(tái)模塊，通過用戶在系統(tǒng)中瀏覽記錄、歷史訂單等行為記錄進(jìn)行建模，利用算法挖掘關(guān)聯(lián)規(guī)則。當(dāng)用戶在訪問購物系統(tǒng)時(shí)，讀取用戶的歷史行為涉及到的商品數(shù)據(jù)，再去檢索關(guān)聯(lián)規(guī)則中是否包含以當(dāng)前商品為某條關(guān)聯(lián)規(guī)則前件的記錄，若包含，則把關(guān)聯(lián)規(guī)則后件對(duì)應(yīng)的商品推薦給用戶。

（2）推薦功能模塊性能問題？通過前面對(duì)Apriori 算法執(zhí)行過程分析，可知Apriori 算法的復(fù)雜度比較高，面對(duì)大數(shù)據(jù)環(huán)境下的關(guān)聯(lián)規(guī)則挖掘，實(shí)現(xiàn)高效的性能，也是需要進(jìn)一步思考解決的問題。