采用數(shù)據(jù)挖掘的自動化推薦技術(shù)的研究

陳慶章, 湯仲喆，王 凱，姚 敏，裴玉潔

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 浙江 杭州 310023)

1 緒論

隨著網(wǎng)絡(luò)中信息量的迅速增長，信息種類也日趨繁多，用戶通過互聯(lián)網(wǎng)要獲得自己感興趣的資料需要花費(fèi)越來越多的時(shí)間。由此催生了信息推薦系統(tǒng)。信息推薦系統(tǒng)的基本作用是依據(jù)用戶曾經(jīng)的訪問記錄，分析用戶的喜好，然后當(dāng)用戶登錄網(wǎng)上應(yīng)用系統(tǒng)時(shí)，推薦適合用戶喜好的資料給用戶，供用戶選擇。從而節(jié)省用戶檢索信息的時(shí)間。

鑒于推薦系統(tǒng)(Recommender System)[1-2]能滿足用戶個(gè)性化的需求，節(jié)省用戶搜尋信息的時(shí)間，同時(shí)可以幫用戶及時(shí)獲得最新與自己喜好相關(guān)的信息，它已被廣泛的應(yīng)用于電子商務(wù)網(wǎng)站[3-7]中。

1.1 網(wǎng)上推薦系統(tǒng)研究現(xiàn)狀

網(wǎng)上推薦系統(tǒng)的主要推薦技術(shù)可分為： 非個(gè)性化的推薦技術(shù)(Non-Personalized Recommendation)、基于屬性的推薦技術(shù)(Attribute-based Recommendation)、物品關(guān)聯(lián)式推薦技術(shù) (Item-to-Item Correlation)和人物關(guān)聯(lián)式推薦技術(shù)(People-to-People Correlation)。推薦技術(shù)的主要推薦方式分為基于內(nèi)容的過濾方式(Content-Based Filtering)和合作過濾方式(Collaborative Filtering)?；趦?nèi)容的過濾是利用信息與用戶興趣喜好的相似性來過濾信息。其優(yōu)點(diǎn)是簡單、有效，但是只能推薦用戶以前看過或類似的信息，不能發(fā)掘新的用戶感興趣的信息。合作過濾方式是基于其他用戶的選擇將信息推薦給用戶，其優(yōu)點(diǎn)是能為讀者發(fā)現(xiàn)新的感興趣的信息，但也存在著許多問題，如早期評估者問題，稀疏問題和新近的項(xiàng)目的推薦問題等。已經(jīng)有很多學(xué)者對推薦系統(tǒng)進(jìn)行了研究，國內(nèi)的推薦系統(tǒng)做的比較成功的網(wǎng)站有豆瓣、當(dāng)當(dāng)網(wǎng)、淘寶網(wǎng)和京東商城等。國外的典型研究成果有： 1998年Sarwar B.等人研究的GroupLens系統(tǒng)[6]；1997年L. Terveen等人提出的PHOAKS系統(tǒng)[8]。

本論文研究的推薦系統(tǒng)采用個(gè)性化的推薦機(jī)制。首先應(yīng)用人工神經(jīng)網(wǎng)絡(luò)技術(shù)產(chǎn)生用戶群組，再利用數(shù)據(jù)挖掘技術(shù)從現(xiàn)成的網(wǎng)絡(luò)交易數(shù)據(jù)庫的交易數(shù)據(jù)中，挖掘出用戶與項(xiàng)目之間以及項(xiàng)目與項(xiàng)目之間的關(guān)聯(lián)法則，由此得出信息推薦規(guī)則，然后根據(jù)用戶的輸入信息，判斷用戶類型，最后返回推薦結(jié)果。其中，用戶聚類采用人工神經(jīng)網(wǎng)絡(luò)技術(shù)的ART(Adaptive Resonance Theory)算法實(shí)現(xiàn)，國外學(xué)者對ART聚類算法的應(yīng)用研究情況有： Massey, L.[9]提出運(yùn)用ART聚類算法進(jìn)行文檔分類。2009年Bhupesh Gour和Sudhir Sharma等人[10]提出了將ART聚類算法運(yùn)用到指紋識別系統(tǒng)。國內(nèi)學(xué)者對ART聚類算法的應(yīng)用研究情況有： 西安電子科技大學(xué)白琳[11]提出了基于ART聚類的入侵檢測算法來解決網(wǎng)絡(luò)安全問題。中國醫(yī)科大學(xué)白英龍[12]和李春濤提出一種基于ART聚類算法的患者個(gè)性特征聚類模型。

1.2 現(xiàn)有ART算法的不足

目前被廣泛用來進(jìn)行用戶聚類的ART算法主要存在著以下兩方面的不足。

1. 屬性向量“同或”狀態(tài)的考慮問題

i=1,…,p

(1)

這種常規(guī)的相似度的計(jì)算，只考慮了“1”的作用，并未考慮外權(quán)向量中“0”的作用。但在實(shí)際運(yùn)用中，0和1分別表示兩種狀態(tài)，在判斷中都是有用的信息，是同等重要的。因此，這種方法有明顯的不足之處。為解決這種不足，文中設(shè)計(jì)了一種新的相似度計(jì)算方法，同時(shí)考慮了“0”和“1”的狀態(tài),看Wt[i][j*]和x[i]對應(yīng)位置上相同狀態(tài)的個(gè)數(shù),即Wt[i][j*]與x[i] “同或”值的個(gè)數(shù)。這種方法能夠很準(zhǔn)確地考慮兩個(gè)向量中“同或”的狀態(tài),而不存在孰輕孰重的問題。

2. 輸入屬性的權(quán)重問題

在ART算法中應(yīng)用的輸入模式是多個(gè)屬性的集合。并且這些屬性均被轉(zhuǎn)換成二進(jìn)制數(shù)據(jù)進(jìn)行處理。每個(gè)屬性所占的位數(shù)都有可能影響到聚類的結(jié)果。因此，當(dāng)一個(gè)屬性的輸入向量所占的位數(shù)值越大時(shí)，這個(gè)屬性對聚類的結(jié)果影響便越大。從廣義的角度來看，每個(gè)屬性的重要性可能是不同的。為了處理在聚類過程中屬性重要性的問題，ART算法也將進(jìn)行相應(yīng)的改進(jìn)來調(diào)整輸入屬性的權(quán)重，以便得到更為合理和靈活的輸出結(jié)果。

2 推薦機(jī)制總體框架

圖1 在線自動化推薦機(jī)制的框架

關(guān)于在線自動推薦機(jī)制的框架如圖1所示。這一框架結(jié)構(gòu)依賴于運(yùn)用ART神經(jīng)網(wǎng)絡(luò)技術(shù)預(yù)處理用戶的個(gè)人資料，通過分析用戶的個(gè)性化屬性信息，分類所有在線用戶，得出用戶的類型信息，應(yīng)用數(shù)據(jù)挖掘技術(shù)處理歷史交易數(shù)據(jù)和用戶類型，找出用戶與選擇的項(xiàng)目之間以及項(xiàng)目與項(xiàng)目之間的關(guān)聯(lián)規(guī)則，并將其存入知識數(shù)據(jù)庫。當(dāng)一個(gè)用戶在線發(fā)起一個(gè)服務(wù)請求時(shí)，系統(tǒng)會通過識別用戶的類型信息找出適合該類型用戶的相關(guān)規(guī)則，挖掘出用戶的興趣度信息，并將個(gè)性化的推薦信息展現(xiàn)給用戶。該自動推薦機(jī)制的處理流程由兩個(gè)階段組成，即預(yù)處理階段和在線階段。

2.1 預(yù)處理階段的設(shè)計(jì)

預(yù)處理階段是分析用戶信息，包括用戶的屬性和歷史交易數(shù)據(jù)。由于從數(shù)據(jù)庫提取的資料可能存有格式不相容的問題，因此必須做適當(dāng)?shù)奶幚?。圖2描述了預(yù)處理階段的操作流程，處理步驟為： 步驟1選擇相關(guān)用戶數(shù)據(jù)，包括用戶屬性和歷史交易數(shù)據(jù)信息；步驟2設(shè)計(jì)ART分類網(wǎng)絡(luò)；步驟3輸入實(shí)驗(yàn)值，得出分類結(jié)果；步驟4應(yīng)用Apriori算法進(jìn)行數(shù)據(jù)挖掘，整合ART分類結(jié)果和歷史交易數(shù)據(jù)，計(jì)算出用戶類型和項(xiàng)目之間，以及項(xiàng)目與項(xiàng)目之間的關(guān)系；步驟5創(chuàng)建關(guān)聯(lián)規(guī)則知識庫： 將數(shù)據(jù)挖掘的結(jié)果以規(guī)則的形式儲存于知識庫中。

圖2 自動化推薦系統(tǒng)的預(yù)處理流程

2.2 在線階段的設(shè)計(jì)

根據(jù)預(yù)處理過程，推薦的知識被儲存在知識庫中。只要用戶在線輸入所需的項(xiàng)目，ARS就會自動處理(圖3)。處理流程如下： (1)ART根據(jù)用戶的屬性將用戶進(jìn)行歸類；(2)系統(tǒng)根據(jù)用戶的類型和所需的項(xiàng)目讀取知識庫；(3)結(jié)合關(guān)聯(lián)規(guī)則，提取用于推薦的相關(guān)項(xiàng)目。

圖3 自動化推薦系統(tǒng)的在線處理流程

ARS通過網(wǎng)絡(luò)界面將項(xiàng)目推薦給用戶。其中被推薦項(xiàng)目的數(shù)量由它們與關(guān)聯(lián)規(guī)則的匹配情況決定。

2.3 應(yīng)用ART網(wǎng)絡(luò)進(jìn)行聚類的設(shè)計(jì)

ART技術(shù)將用戶劃分為合適的聚類[13]。ART網(wǎng)絡(luò)的結(jié)構(gòu)有三個(gè)主要部件： 輸入層、輸出層和網(wǎng)絡(luò)連接層。

(2)

(3)

(4)

Step 8執(zhí)行警戒測試。(設(shè)r為警戒值，且r∈{0,1})如果Vj*小于預(yù)設(shè)值r，那么這個(gè)樣品與輸出類是不太相關(guān)的，接著進(jìn)行下一個(gè)輸出點(diǎn)的比較，轉(zhuǎn)入步驟9。否則進(jìn)入步驟10。Step 9測試是否存在另一個(gè)相似的輸出集。(設(shè)Icount表示為已被使用的輸出集個(gè)數(shù)，初始值為0.)如果Icount < Nout,計(jì)算出輸入向量與剩余輸出集的下一個(gè)最大匹配度net[j]，令I(lǐng)count = Icount+1，net[j*]=0, 轉(zhuǎn)入步驟6. 否則，如果不存在其他的輸出集用于測試，那么： (1)生成新的類，令Nout = Nout+1, 并創(chuàng)建新的連接權(quán)重。

(2) 設(shè)置輸出值。如果j=j*, 那么Y[j]=1,(Y[j]表示輸出向量，1≤i≤P)否則Y[j]=0；(3) 轉(zhuǎn)入步驟4(輸入一個(gè)新的向量X)；Step 10如果Vj* >r,即境界測試通過,那么(1) 調(diào)整權(quán)重值

(2) 設(shè)置輸出值: 如果j=j*, 那么Y[j]=1, 否則Y[j]=0；Step 11如果沒有新的聚類生成且正好完成一個(gè)循環(huán)，則輸出聚類結(jié)果。否則轉(zhuǎn)入步驟4輸入新向量X。

2.4 改進(jìn)后的ART算法(MART)

(7)

Mt[i]為輸入屬性的權(quán)重，即第i個(gè)節(jié)點(diǎn)重要性，其中Mt[i]∈R+。

新算法MART(Modified ART)的執(zhí)行步驟與原算法類似，只是需要首先設(shè)置每一個(gè)節(jié)點(diǎn)(屬性)的重要性，即Mt[i]。根據(jù)相似的用戶屬性，利用MART算法形成用戶分組。這個(gè)結(jié)果可用于下一個(gè)挖掘過程中。

2.5 生成強(qiáng)關(guān)聯(lián)規(guī)則

首先由Apriori算法得出頻繁項(xiàng)集，再根據(jù)獲得頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則。其中可能產(chǎn)生的法則是X?Y，依此我們可以計(jì)算當(dāng)X發(fā)生時(shí)，也發(fā)生Y的信任度，若是到達(dá)設(shè)定的最低信任度(Minimum Confidence Level)，則此強(qiáng)關(guān)聯(lián)規(guī)則就成立。而信任度的計(jì)算方法是：confidence(X?Y)=P(Y|X)=support(X∪Y)/support(X)，其中X∩Y=φ具體過程為： 設(shè)每一個(gè)頻繁項(xiàng)集由li表示，X是這個(gè)頻繁項(xiàng)集的子集，其中(li-X)∩X=φ是指交易記錄中包含項(xiàng)目X的次數(shù)，support(li)是指交易記錄中包含li的次數(shù)，那么X?(li-X)的信任度為support(li)/support(X)，若它的值大于或等于設(shè)定的最低信任度，則為強(qiáng)關(guān)聯(lián)規(guī)則。以此類推，直到生成所有的強(qiáng)關(guān)聯(lián)規(guī)則，即用戶類型和項(xiàng)目之間以及項(xiàng)目與項(xiàng)目之間的推薦規(guī)則，并將它們存入知識庫，用于之后系統(tǒng)的在線推薦階段。

3 在線自動化推薦機(jī)制在圖書推薦中的應(yīng)用

3.1 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)虛擬了30個(gè)學(xué)生和49本圖書，它們都是隨機(jī)生成的，用于模擬圖書館的用戶借閱記錄。在試驗(yàn)中，我們選取了信息管理專業(yè)和計(jì)算機(jī)應(yīng)用技術(shù)專業(yè)，作為該機(jī)制的研究對象。隨機(jī)生成了120條歷史借閱總記錄，其中信息管理專業(yè)有63條記錄，計(jì)算機(jī)應(yīng)用技術(shù)專業(yè)有57條記錄。該實(shí)例應(yīng)用一共分為圖書推薦預(yù)處理階段和在線圖書推薦階段兩部分。

3.2 圖書推薦預(yù)處理階段

(1) 設(shè)計(jì)ART網(wǎng)絡(luò)的輸入模式

為了應(yīng)用本研究機(jī)制，我們需要先設(shè)計(jì)代表學(xué)生借閱習(xí)慣的輸入向量。學(xué)生屬性的二進(jìn)制表示形式，即ART網(wǎng)絡(luò)的輸入模式定義如表1所示。

表1 ART網(wǎng)絡(luò)的輸入模式定義

定義好學(xué)生屬性值之后，下一步就是將學(xué)生屬性轉(zhuǎn)換成二進(jìn)制。輸入模式(二進(jìn)制向量)經(jīng)過MART網(wǎng)絡(luò)進(jìn)行聚類處理，擁有相似圖書借閱習(xí)慣的學(xué)生將會被自動劃分到相同的聚類。這里我們將MART網(wǎng)絡(luò)的警戒值分別設(shè)為0.1到0.9，各屬性節(jié)點(diǎn)的權(quán)重值設(shè)為Mt[i]=[1,3,1,1,1,1]，即“專業(yè)”在各個(gè)屬性中占有更重要的地位，實(shí)驗(yàn)結(jié)果如表2 所示。

表2 不同警戒值下的實(shí)驗(yàn)結(jié)果

(2) 挖掘出關(guān)聯(lián)規(guī)則并放入知識庫中

通過MART網(wǎng)絡(luò)得到聚類結(jié)果之后，將用戶的類型信息和圖書借閱記錄一起輸入到知識庫中。Apriori算法通過調(diào)整支持度和信任度, 挖掘出學(xué)生用戶類型和圖書之間，以及圖書與圖書之間的關(guān)聯(lián)規(guī)則, 生成強(qiáng)關(guān)聯(lián)規(guī)則并將其存入知識庫，圖4給出了在最小支持度設(shè)為2，最小信任度設(shè)為0.5下的生成的關(guān)聯(lián)規(guī)則。

3.2 在線圖書推薦階段

在ART網(wǎng)絡(luò)生成學(xué)生聚類以及知識庫信息建立之后，ARS的在線階段就可以實(shí)現(xiàn)了。當(dāng)一個(gè)學(xué)生使用在線ARS查找圖書的時(shí)候，ARS將根據(jù)學(xué)生的屬性或其輸入的關(guān)鍵字判斷用戶類型，參考知識庫中用戶類型與圖書之間以及圖書與圖書之間的關(guān)聯(lián)規(guī)則，將與該類型用戶相關(guān)聯(lián)的圖書推薦給該用戶。

結(jié)合本實(shí)例應(yīng)用中的例子，如圖5所示，當(dāng)一個(gè)學(xué)生在查詢圖書名含有“Tcp”的圖書時(shí)，將會看到自動化推薦系統(tǒng)除了將含有“Tcp”的圖書顯示出來以外，還推薦了其他兩本圖書“解析極限編程”以及“D make me think”。

4 結(jié)論

本研究結(jié)合人工神經(jīng)網(wǎng)絡(luò)技術(shù)和數(shù)據(jù)挖掘技術(shù)，展示了一個(gè)個(gè)性化的自動化推薦機(jī)制。針對屬性向量“同或”狀態(tài)的考慮問題和屬性的權(quán)重問題，對經(jīng)典的ART算法進(jìn)行優(yōu)化，得到MART算法。并創(chuàng)建了一個(gè)以用戶為導(dǎo)向的圖書推薦系統(tǒng)，該系統(tǒng)首先運(yùn)用MART算法產(chǎn)生用戶聚類，由此得出每個(gè)用戶的類型，再使用Apriori算法挖掘出用戶類型與圖書之間，以及圖書與圖書之間的強(qiáng)關(guān)聯(lián)規(guī)則，即圖書推薦規(guī)則，最后根據(jù)在線用戶輸入信息或用戶類型信息，將適當(dāng)?shù)南嚓P(guān)項(xiàng)目或信息推薦給用戶。該圖書推薦機(jī)制所具有的優(yōu)勢有： (1) 社群特征。運(yùn)用ART 網(wǎng)絡(luò)聚類用戶社群，進(jìn)而推薦適合每個(gè)社群的不同的圖書信息； (2) 關(guān)聯(lián)特征。利用數(shù)據(jù)挖掘中的Apriori 算法可發(fā)掘出用戶社群與圖書之間，以及圖書與圖書之間的強(qiáng)關(guān)聯(lián)規(guī)則； (3) 用戶分群效率高。當(dāng)ART 網(wǎng)路聚類完畢后，在線系統(tǒng)能夠?qū)⑦m當(dāng)?shù)男畔⑼扑]給用戶，因此非常適合網(wǎng)絡(luò)的動態(tài)變化和快速反應(yīng)的環(huán)境。

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

圖5 推薦結(jié)果界面

[1] Sarwar, B., Karypis, G., Konstan, J. et al. Analysis of Recommendation Algorithms for E-commerce [C]//ACM Conference on Electronic Commerce, 2000: 158-167.

[2] Yu, P. S.. Data Mining and Personalization Technologies [C]//Proceedings of the 6th International Conference on Database Systems for Advanced Applications, 1999: 6-13.

[3] AltaVista. http://www.altavista.digital.com, 2002[DB/OL].

[4] Amazon. http://www.amazon.com, 2002[DB/OL].

[5] Hill, W.C., Stead, L., Rosenstein, M., et al. Recommending and evaluating choices in a virtual community of use[C]//Proceedings of CHI’95, 1995: 194-201.

[6] Konstan, J., Miller, B., Maltz, D., et al. Group-Lens Applying Collaborative Filtering to Usenet News[C]//Proceedings of Communications of ACM, 1997, 40 (3): 77-87.

[7] Shardanand, U., Maes, P.. Social Information Filtering: Algorithms for Automating ‘Word of Mouth’ [C]//Proceedings of the Computer-Human Interaction Conference (CHI’95), 1995.

[8] Editmax. http://www.editmax.net/n1229c15.aspx, 2009[DB/OL].

[9] Louis Massey. On the quality of ART1 text clustering [J]. Neural Networks, 2003: 771-778.

[10] Bhupesh Gour, T. K. Bandopadhyaya, Sudhir Sharma. High Quality Cluster Generation of Feature Points of Fingerprint Using Neutral Network [J]. EuroJournals Publishing, 2009: 13-18.

[11] 白琳. 基于神經(jīng)計(jì)算和進(jìn)化網(wǎng)絡(luò)的入侵檢測[D]. 西安電子科技大學(xué),2005.

[12] 白英龍,李春濤. 一種患者個(gè)性特征聚類模型的設(shè)計(jì)[J]. 中國全科醫(yī)學(xué),2007,10(23):2022-2023.

[13] 鄭麗英.基于trie的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法[N].蘭州理工大學(xué)學(xué)報(bào)，2004，30(5)： 90-92.