基于屬性規(guī)則與關聯(lián)規(guī)則的推薦模型設計

余鵬程，李 燁

(上海理工大學 光電信息與計算機工程學院，上海 200093)

基于屬性規(guī)則與關聯(lián)規(guī)則的推薦模型設計

余鵬程，李 燁

(上海理工大學 光電信息與計算機工程學院，上海 200093)

針對如何更好地描述商品屬性與用戶偏好之間關系的問題，提出了屬性規(guī)則概念；并針對推薦系統(tǒng)的冷啟動問題，將屬性規(guī)則與關聯(lián)規(guī)則相結合，設計了一種新的推薦模型；為解決在關聯(lián)規(guī)則生成過程中，Apriori算法需要多次掃描數(shù)據(jù)庫的問題，采用矩陣運算的方法，一次掃描數(shù)據(jù)庫，生成頻繁項集，同時利用頻繁項集支持度計數(shù)生成屬性規(guī)則；最后，匹配兩種規(guī)則產(chǎn)生最終Top-N推薦列表。

屬性規(guī)則；關聯(lián)規(guī)則；推薦系統(tǒng)；Apriori算法

“+互聯(lián)網(wǎng)”時代的到來，使得“信息過載”問題越來越明顯，而作為解決“信息過載”問題并挖掘用戶潛在需求的有效方法，推薦系統(tǒng)正吸引越來越多的關注[1]。搜索引擎作為解決“信息過載”問題的傳統(tǒng)解決方案是指自動從因特網(wǎng)搜集信息，經(jīng)過一定整理后，提供給用戶進行查詢的系統(tǒng)。然而，在滿足用戶的隱性偏好方面，搜索引擎卻無能為力[2]。推薦系統(tǒng)是根據(jù)用戶的潛在需求、興趣等，將用戶感興趣的信息、產(chǎn)品推薦給用戶。隨著移動互聯(lián)網(wǎng)的興起，推薦系統(tǒng)的優(yōu)勢將會更加明顯。

目前，運用較為成功的推薦技術是基于協(xié)同過濾的推薦，其是根據(jù)用戶興趣和特點尋找與用戶需求相似的信息推薦給用戶,或者尋找與用戶有相似興趣和特點的目標用戶群進行推薦。協(xié)同過濾的關鍵是相似性計算，其核心是對推薦對象進行最近鄰查詢[3-4]。然而對于新用戶，協(xié)同過濾推薦算法無法根據(jù)新用戶的少量信息產(chǎn)生有效推薦，即冷啟動問題[5-6]，并隨著用戶數(shù)量的上升，算法耗時也在增加，使得推薦效果在一定情況下變差。為了從新用戶的少量信息中準確挖掘用戶偏好，本文提出屬性規(guī)則的概念，并且設計一種基于關聯(lián)規(guī)則與屬性規(guī)則相結合的推薦模型來解決冷啟動問題。采用經(jīng)典算法Apriori[7]來挖掘關聯(lián)規(guī)則，為了避免Apriori算法多次掃描數(shù)據(jù)庫的問題，采用矩陣計算的方式產(chǎn)生頻繁項集[8]，同時利用各項的支持度計數(shù)產(chǎn)生屬性規(guī)則。最后根據(jù)當前獲取的用戶信息，分別匹配關聯(lián)規(guī)則與屬性規(guī)則，綜合兩種規(guī)則產(chǎn)生的推薦結果來生成最終的Top-N推薦列表。

1 基本概念

設I={i1,i2,…,in}是數(shù)據(jù)庫D中所有項的集合，T={t1,t2,…,tm}是所有交易的集合，每個ti稱為T的子集，且每個事物ti包含的項均是I的子集[9]。

定義 數(shù)據(jù)庫D中包含特定項集的事務個數(shù)稱支持度計數(shù)，支持度計數(shù)除以事務總數(shù)即為該項集的支持度。設|·|表示集合中元素的個數(shù)，符號m代表事務總數(shù)。則對于某一項集X的支持度計數(shù)

(1)

定義 若項集X包含k個項，并且支持度c(X)大于支持度閾值α，則稱項集X為頻繁k項集。

定義 對于某一規(guī)則X?Y，其中X,Y∈T，且X∩Y=?，其支持度與置信度為

supp(X?Y)=δ(X∪Y)

(2)

(3)

若其滿足supp(r)≥a,conf(r)≥β條件，則該規(guī)則即為X?Y的關聯(lián)規(guī)則，用Rules_s表示為

Rules_s={r:X?Y|supp(r)≥α,

conf(r)≥β,X,Y?T,X∩Y=?}

(4)

其中，α和β分別為給定的支持度閾值與置信度閾值。

2 推薦模型設計

本文設計的推薦系統(tǒng)模型如圖1所示，主要包括4個模塊：數(shù)據(jù)預處理模塊、推薦算法模塊、用戶信息采集模塊、推薦結果綜合處理模塊，以下介紹4個的模塊功能。

圖1 推薦模型

2.1 數(shù)據(jù)預處理模塊

首先，本文設計的推薦模型采用用戶的歷史購物數(shù)據(jù)，之所以采用歷史購物數(shù)據(jù)，一是避免對用戶產(chǎn)生侵襲性；二是客觀反映用戶偏好。原始交易記錄包含諸多冗余成分，并不能直接作為系統(tǒng)的輸入，需進行預處理。例如，天貓電器商城2015年11月份的交易數(shù)據(jù)中，每一種商品包含21條屬性。因此要對其進行降維，特征提取，刪除冗余信息，并保留關鍵屬性，如商品的種類、外觀、顏色等[10]。

2.2 推薦算法模塊

推薦算法模塊是本模型的核心部分，合適的推薦算法對推薦模型的優(yōu)劣具有決定作用，本文采用基于矩陣的Apriori算法來生成頻繁項集，并最終通過頻繁項集生成關聯(lián)規(guī)則與屬性規(guī)則。

2.2.1 關聯(lián)規(guī)則算法

Apriori是關聯(lián)規(guī)則挖掘中的經(jīng)典算法之一，其原理簡單，效果明顯，應用廣泛。其的核心思想是對數(shù)據(jù)庫進行多次掃描，利用已知的 頻繁項集，聯(lián)合一定的約束策略生成 頻繁項集，然后由最終的k頻繁項集生成關聯(lián)規(guī)則[11-12]。

Apriori算法主要分為兩個階段：候選項集的產(chǎn)生與剪枝、頻繁項集的形成。其的核心也是圍繞著如何高效生成候選項集進行的,而在生成候選項集的過程中，最重要的工作就是連接和剪枝。算法采用合并兩個(k-1)頻繁項集來產(chǎn)生候選k頻繁項集的策略，這種方法雖保證了候選項集產(chǎn)生的完全性，但需要通過額外的算法來保證該候選項集的所有子集均是頻繁的[13]。

從其原理可看出在生成頻繁項集的過程中，Apriori算法需要多次掃描數(shù)據(jù)庫，且會產(chǎn)生大量的候選項集，當數(shù)據(jù)庫包含大量交易數(shù)據(jù)時，該方法效率極低，難以滿足推薦系統(tǒng)對實時性的要求。而本文設計的推薦模型采用矩陣計算的方式通過一次掃描數(shù)據(jù)庫，就能生成頻繁項集。

基于矩陣的Apriori算法描述如下：

輸入 交易數(shù)據(jù)庫D、最小支持度α和最小置信度β。

輸出 關聯(lián)規(guī)則Rules_s。

(1)掃描交易數(shù)據(jù)庫D，構建交易矩陣Dm×n，其中矩陣每一行代表一次交易記錄，每一列代表一種商品項。當?shù)趇次交易包含商品j時，di×j=1，否則di×j=0；可得矩陣

(5)

(2)由頻繁1項集產(chǎn)生候選2項集C2，對矩陣Dm×n的每一行求和，刪除值<2的行(值<2不可能產(chǎn)生頻繁2項集)。C2每一個元素IiIj的支持度為

(6)

其中，∧表示與運算。刪除支持度<α的候選項，得到頻繁2項集

L2={c∈Ck|Supp(IiIj)≥α}

(7)

(3)當k≥3時，根據(jù)頻繁(k-1)項集Lk-1生成候選k項集Ck。首先刪除矩陣Dm×n中行元素之和

(8)

刪除支持度<α的候選項，得到k頻繁項集Lk={c∈Ck|Supp(IiIj…It)≥α}；

(4)由頻繁k項集Lk生成候選k+1項集Ck+1,如果Ck+1不等于空，執(zhí)行步驟(3)，否則執(zhí)行步驟(5)；

(5)遍歷頻繁項集，生成關聯(lián)規(guī)則庫Rules_s。

2.2.2 屬性規(guī)則算法

定義 設集合A={a1,a2,…，an}是數(shù)據(jù)庫中項的屬性集合，在交易數(shù)據(jù)庫D中，具有屬性a的項按照支持度計數(shù)進行降序排列，取前N項為：IN={i1,i2,…,iN}，則屬性a的規(guī)則 即為Rules_a

Rules_a={r:a?IN|Supp(i)≥α,a∈A,i∈IN}

(9)

其中，α為給定的支持度閾值。

在屬性規(guī)則生成之前，首先需要根據(jù)商品的種類選擇合適的屬性，建立屬性集合，然后遍歷數(shù)據(jù)庫，計算出每一種屬性對應的商品項的數(shù)量，最后保留前N項即可。遍歷數(shù)據(jù)庫與生成屬性規(guī)則可同時進行。

屬性規(guī)則生成算法描述如下：

輸入 頻繁1項集L1，商品屬性集合A,推薦商品數(shù)N。

輸出 屬性規(guī)則庫Rules_a。

1.按照支持度對L1進行降序排列

2.for a∈A

3.fori∈L1

4.ifi具有a屬性

5.IN←i

6.n++；

7.if n==N

8.rule_a←a?IN

9.Rules_a←rule_a

10.n=0;

11.break;

12.returnRules_a；

2.3 用戶信息采集模塊

用戶信息采集模塊的功能是收集用戶信息與目標商品屬性。當用戶瀏覽商品時，如果是舊用戶，則先獲取用戶的注冊信息，根據(jù)其歷史購物記錄，隱性初步獲取其偏好。然后獲取用戶所瀏覽商品的信息，如商品種類、商品的尺寸、商品的外觀描述等，從而顯性獲取目標商品的屬性[9]。然后將采集的信息傳遞給推薦算法模塊，推薦算法模塊根據(jù)用戶瀏覽的商品信息分別進行關聯(lián)規(guī)則與屬性規(guī)則匹配，從而生成推薦商品列表。

2.4 推薦結果綜合處理模塊

在獲取用戶信息之后，將提取的商品信息與關聯(lián)規(guī)則和屬性規(guī)則匹配，生成推薦結果，完成商品的Top-N推薦。

首先，根據(jù)目標商品信息，匹配關聯(lián)規(guī)則，生成關聯(lián)規(guī)則推薦列表；然后按照支持度計數(shù)排序，若是舊用戶，需去除用戶購買過的商品，取前N項作為關聯(lián)規(guī)則推薦的最終結果，并記為Result_s；另外，根據(jù)提取商品的不同屬性，分別匹配屬性規(guī)則，取前N項作為屬性規(guī)則推薦的最終結果，并記為Result_a。

則最終推薦給用戶的商品為

Result=(1-weight)Result_s+weight×Result_a

(10)

其中，weight為屬性規(guī)則推薦結果所占權重[14-15]。

3 模型推薦實例

表1為事務數(shù)據(jù)庫 包含的交易數(shù)據(jù)，表2表示每一個項的屬性信息，設支持度閾值為0.2，置信度為0.5，N=2，weight=0.5。

表1 事務數(shù)據(jù)庫

表2 商品屬性

產(chǎn)生推薦列表的過程如下：

(1)根據(jù)支持度閾值以及設定的置信度，得到頻繁1-項集{I1:6;I2:7,I3:5,I4:4,I5:3,I6:2}；關聯(lián)規(guī)則：{I1?I2I4,I2?I1I4,I1I2?I4,I4?I1I2}；屬性規(guī)則：{A0?I1I4,A1?I2I3,B0?I2I3,B1?I1I4I5}；

(2)設用戶當前輸入為I1，獲取I1的兩種屬性值A0、B1，再分別匹配關聯(lián)規(guī)則與屬性規(guī)則，通過匹配關聯(lián)規(guī)則產(chǎn)生推薦列表：I2、I4；匹配屬性規(guī)則產(chǎn)生推薦列表：I1、I4、I5。由于weight=0.5，即屬性規(guī)則推薦結果占最終推薦結果的1/2。為避免新商品的冷啟動問題，在關聯(lián)規(guī)則與屬性規(guī)則中分別隨機選取一件商品，組成最終的推薦列表，如{I1I5}。

若用戶輸入的商品項匹配不到關聯(lián)規(guī)則，如I6，則可匹配屬性規(guī)則，產(chǎn)生推薦列表{I2I3}。

4 結束語

本文設計的推薦模型，在采集用戶信息時，采用顯性與隱性相結合的方式，既客觀獲取用戶的偏好，又動態(tài)實時獲取最新數(shù)據(jù)，使數(shù)據(jù)更能反映出用戶的興趣[16]；本文首次提出屬性規(guī)則概念來描述商品屬性與用戶偏好的關系，根據(jù)歷史購物數(shù)據(jù)，生成屬性規(guī)則，采用關聯(lián)規(guī)則經(jīng)典算法Apriori，利用矩陣計算頻繁項集，只掃描數(shù)據(jù)庫一次，產(chǎn)生關聯(lián)規(guī)則；采用屬性規(guī)則與關聯(lián)規(guī)則相結合的方式來產(chǎn)生推薦列表，并根據(jù)用戶對象不同，利用不同的權重系數(shù)來調(diào)整推薦結果，使整個推薦系統(tǒng)更加有效可行。

[1] 王國霞,劉賀平.個性化推薦系統(tǒng)綜述[J].計算機工程與應用,2012,48(7):66-76.

[2] 許海玲,吳瀟,李曉東,等.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J].軟件學報,2009,20(2):350-362.

[3] 馬宏偉,張光衛(wèi),李鵬.協(xié)同過濾推薦算法綜述[J].小型微型計算機系統(tǒng),2009,30(7):1282-1288.

[4] 文俊浩,舒珊.一種改進相似性度量的協(xié)同過濾推薦算法[J]. 計算機科學,2014,41(5):68-71.

[5] 孫冬婷,何濤,張福海.推薦系統(tǒng)中的冷啟動問題研究綜述[J].計算機與現(xiàn)代化,2012(5):59-63.

[6] 于洪,李俊華.一種解決新項目冷啟動問題的推薦算法[J]. 軟件學報,2015,26(6):1395-1408.

[7] Agrawl R,Srikant R.Fast algorithms for mining assoeiation rules[C].Santiago,Chile:Proe of the 20th International Conference on Very Large Data Bases,1994.

[8] 李超,余昭平.基于矩陣的Apriori算法改進[J].計算機工程,2006,32(23):68-69.

[9] Pang-Ning Tan,Michael Steinbach,Vipin Kumar.數(shù)據(jù)挖掘?qū)д揫M].2版.范明,范宏建,譯.北京:人民郵電出版社,2011.

[10] 菅志剛,金旭.數(shù)據(jù)挖掘中數(shù)據(jù)預處理的研究與實現(xiàn)[J].計算機應用研究,2004,21(7):117-118,157.

[11] 羅昌銀.一種基于動態(tài)排序的最大頻繁項集挖掘算法[D].重慶:重慶大學,2010.

[12] 李杰,徐勇,王云峰,等.面向個性化推薦的強關聯(lián)規(guī)則挖掘[J].系統(tǒng)工程理論與實踐,2009,29(8):144-152.

[13] 楊澤民.數(shù)據(jù)挖掘中關聯(lián)規(guī)則算法的研究[J].軟件,2013(11):71-72,92.

[14] 陳君,唐雁.基于Web社會網(wǎng)絡的個性化Web信息推薦模型[J].計算機科學,2006,33(4):185-187,193.

[15] 李忠俊,周啟海,帥青紅.一種基于內(nèi)容和協(xié)同過濾同構化整合的推薦系統(tǒng)模型[J]. 計算機科學,2009,36(12):142-145.

[16] 楊引霞,謝康林,朱揚勇,等.電子商務網(wǎng)站推薦系統(tǒng)中關聯(lián)規(guī)則推薦模型的實現(xiàn)[J]. 計算機工程,2004,30(19):57-59.

Design of Recommendation Model Based on Attribute Rule and Association Rule

YU Pengcheng，LI Ye

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology,Shanghai 200093, China)

Currently, as an effective method to mining potential demand of the users，recommendation system is applied more and more widely. However, in order to solve the problem how to describe the relationship between the attribute of commodity and users’ preferences, this paper proposes the concept of attribute rules in first time. For the cold start problem of recommendation system, we design a new recommendation model by combining attribute rules and association rules; we use Apriori algorithm and matrix operation to mining association rules and avoid the problem of scanning database repeatedly in the process of generating frequent item sets. At the same time, using the support of frequent item set to generate attribute rules; Finally, match two kinds of rules and generate the final Top-N recommendaion list.

attribute rules; association rules; recommended system; Apriori algorithm

2016- 04- 20

滬江基金資助項目(C14002)

余鵬程(1989-)，男，碩士研究生。研究方向：數(shù)據(jù)挖掘和機器學習。李燁(1974-)，男，高級工程師。研究方向：工業(yè)控制與監(jiān)測等。

10.16180/j.cnki.issn1007-7820.2017.03.008

TP301.6

A

1007-7820(2017)03-026-04