基于Ｗｅｂ日志的個性化搜索引擎模型的發現
2009-01-01 00:00:00鮑鈺
計算機應用研究 2009年5期
（華東師范大學 軟件學院 上海 200062）
摘 要：個性化搜索是指同樣的關鍵字對不同的人返回其感興趣的搜索結果。對于不同的用戶個體，同樣的關鍵字可能有不同含義，如關鍵字“apple”被愛好音樂的人士理解為Apple iPod，但也會被健康飲食的人士理解為apple fruit。每次用戶搜索關鍵字的過程，都會被記錄在網站服務器的后臺日志中。通過若干挖掘算法，將Web原始日志信息進行用戶識別，會話分組后，提取單一用戶多次會話中的搜索關鍵字關聯規則，為實現個性化搜索引擎提供參考。
關鍵詞：Web日志；個性化搜索；單用戶搜索關鍵字關聯規則發現算法
中圖分類號：TP311文獻標志碼：A
文章編號：1001-3695(2009)05-1806-04
Discover personalized search engine model by mining Web logs
BAO Yu
(Software Engineering Institute East China Normal University Shanghai 200062 China)
Abstract:The Web site visitors’ search keywords was recorded in the Web server log files. Analyzing and exploring associations in the search keywords of single Web user could provide the personal search results.This paper discovered the single user search keywords association rule by using algorithm SUSKARD.
Key words:Web logs; personal Web search;SUSKARD algorithm
1 數據預處理
原始Web日志雖然包含了大量訪問者的瀏覽信息，但有些日志是隨鑲嵌在網頁中的圖片和腳本產生的；網絡搜索引擎使用的Web蜘蛛、軟機器人或智能代理也會產生訪問日志。這些日志對分析用戶的訪問情況都是無用的，應該過濾掉。大多數情況，只有日志中HTML或ASP文件與用戶會話相關。一般不會顯示請求頁面上的圖形文件，它們是根據HTML的超文本引用標志自動下載的，這些日志與分析用戶的行為模式也沒有任何關系，所以通過檢查URL的后綴，將日志中文件的后綴名為GIF、JPEG、JPG、gif、jpeg、jpg和map的項刪除。除了刪除上面列出的無關項外，還應當刪除露宿者數據。所謂的露宿者是偶爾訪問站點且逗留時間極短的用戶，這些數據對挖掘過程沒有什么貢獻，所以在數據凈化階段也要刪除露宿者Web log中一般至少包括如下字段：每個訪問者的IP地址和域名；訪問的日期和時間；訪問的頁面名稱；訪問請求是否成功；下載文件的大小；引導訪問者來到本站點的URL；訪問者使用的瀏覽器和操作系統，等等。
當然對于不同的Web server，其Web log的格式也有所不同。例如Microsoft IIS 4.0（Microsoft’s Internet information server version 4）的W3C格式如下：
#Fields: date time cip csusername scomputername sip csmethod
csuristem csuriquery scstatus scbytes csbytes
timetaken cs(UserAgent) cs(Cookie) cs(Referer)
對于搜索類網站，具體一條日志記錄表示如下：
20071128 00:05:23 W3SVC87 www.website.com GET /ajax/search.aspx keyword=apple 80 220.171.120.51
Mozilla/4.0+(compatible;+MSIE+6.0;+Windows+NT+5.1;+SV1;+.NET+CLR+1.1.4322) 200 0 0
上面一條日志信息表示IP地址為220.171.120.51的用戶，在時間20071128 00:05:23對網站www.website.com提出了關鍵字為“apple”的搜索請求。
在原始網站服務器后臺日志中，所有用戶的訪問日志會零星摻插在一起，必須對日志按照用戶進行分組，這便是用戶識別。同一用戶對Web站點會有很多次的訪問，又需要在同一用戶的所有訪問日志上進行會話分組，并提取出一次會話中，用戶進行搜索的所有關鍵字集合 。經過會話識別后的一條條記錄，稱之為單用戶搜索關鍵字會話集（single user search keywords session dataset，SUSKSD）。
2 用戶識別方法比較
由于本地緩存、公司防火墻和代理服務器的存在，要識別出每一個用戶變得很復雜。依賴用戶的合作是最好的解決辦法，但是由于涉及到隱私，這種解決辦法往往難以進行。表1歸納了目前常用的為精確確定用戶及其行為所使用的方法及其優缺點。
根據IP和代理識別用戶是最簡單易行的，不過誤差也較大，因為存在多人共有一臺電腦的可能。嵌入SessionID技術一般在電子商務記錄用戶購物籃內物品時最常用，對每一次用戶訪問都嵌入一個SessionID，也就是把一段時間內同一用戶的請求都標記上相同的SessionID號。但是，嵌入SessionID只在動態網站上適用，而且是以時間間隔來判別當前SessionID是否有效，因此沒有考慮短時間內重復訪問的情況。注冊的方法只有在用戶登錄進站后才能跟蹤用戶訪問行為，方法準確性稍高一些，但是并不是所有的用戶都愿意注冊且每一次訪問時都愿意登錄，其可操作性不強。在客戶端寫入Cookie標志，可以跟蹤用戶的重復訪問情況，精確性較高，但是如果用戶不打開瀏覽器Cookie開關，就無法實施。利用代理軟件，精確性最高，可以得到用戶精確的訪問情況，但是可操作性差，用戶可能認為侵犯了個人隱私，拒絕使用代理軟件。本系統中采用根據IP地址識別用戶的方法。
表1 用戶識別方法比較
方法優點缺點
IP地址和代理不需要特殊附加技術，最容易實施不能保證用戶與IP和代理一一對應
嵌入SessionID容易實行，與IP無關未考慮短時間內用戶重復訪問的情況，僅動態網站下適用
注冊可以精確跟蹤一個用戶的訪問情況并非所有的用戶都愿意注冊，且每一次訪問時都愿意登錄
Cookie可以跟蹤重復訪問用戶如果禁用Cookie選項就無法收集信息
代理軟件可以得到精確訪問情況有時會遭到用戶的拒絕甚至投訴
3 單用戶搜索關鍵字會話集發現算法
在跨越時間區段較大的Web服務器日志中，用戶有可能多次訪問了該站點。會話識別的目的就是將用戶的訪問記錄分為單個的會話（session）。最簡單的方法是利用超時，如果兩個頁面間請求時間的差值超過一定的界限就認為用戶開始了一個新的會話。許多商業產品將缺省超時值確定為30 min，超時的界限可以根據站點的使用統計反饋結果進行調節，直到可以準確地識別會話。為方便起見，在本文中也使用30 min作為會話的超時界限。通過會話識別，可以將雜亂無章的Web日志信息歸結為一條條的單用戶搜索關鍵字會話記錄，并采用單用戶搜索關鍵字會話集發現算法（discover single user search keywords session dataset，DSUSKSD），產生如表2所示的單用戶搜索關鍵字會話集。
表2 單用戶搜索關鍵字會話集
IPIDSIDkey words
1000000110001K1、K2、K3
1000000110002K1
1000000110003K3、K4、K5
1000000110004K1、K2、K3
1000000110005K1、K2、K3、K5
表2中IPID=10000001 SID=10001的記錄，表示某IPID=10000001單個用戶在這次會話中，搜索了K1、K2和K3這三個關鍵字。
L:the set of input logs
L={L1，L2，L3，…，Li，…，L|L| } ，i≤|L|
|L|:the number of input logs
Li={IPi，TIMEi，METHODi，URLi，PROTi，CODEi，BYTESi}
S:the set of sessions
S={S1，S2，S3，…，Si，…，S|S|}，i≤|S|
|S|:the number of sessions
Si={IPi，KEYWORDSi}
KEYWORDSi={ KEYWORD1，KEYWORD2，…，KEYWORDm，…，KEYWORD|KWSi|}，m≤|KWSi|
|KWSi|:the number of KEYWORDSi in Session_i
//input: L |L|，Δt
//output:S，|S|
Function DSUSKSD (|L|，L，Δt)
for each Li of L
if Methodi is ‘GET’ AND Urli is ‘SEARCH WEBPAGE’
if S2k∈Open_Sessions_Set with IPk=IPi then
if((TimeiEND_TIME(Sk))<Δt)then
//Δt:會話超時界限設為30 min
Sk=(IPk，KEYWORDSk∪KEYWORDSi)
//屬同一會話，合并關鍵字
else
CLOSE_SESSION(Sk)
WRITE_SESSION(Sk)
Si={IPi，KEYWORDSi}
OPEN_SESSION(Si)
end if
else
Si={IPi，KEYWORDSi}
OPEN_SESSION(Si)
end if
end if
end for
for each Si of Open_Sessions_Set
CLOSE_SESSION(Si)
WRITE_SESSION(Si)
end for
end Function
函數END_TIME(Sk)返回會話Sk中最后一個搜索請求日志的記錄時間。
函數CLOSE_SESSION(Sk)從Open_Sessions_Set中移除Sk。
函數WRITE_SESSION(Sk)將Sk寫入單用戶搜索關鍵字會話集SUSKSD中。
函數OPEN_SESSION(Si)向Open_Sessions_Set中添加Sk。
4 單用戶搜索關鍵字關聯規則發現算法SUSKARD
關聯分析即發現關聯規則，這些規則展示了屬性—值頻繁地在給定數據集中一起出現的條件。例如：可通過對數據的分析得出啤酒→尿布的關聯規則，即買啤酒的人往往會買尿布。對于這種無序項目集，采用Apriori算法[1]可以生成所有頻集。
4.1 關聯規則理論原理
1）關聯規則 設I={i1，i2，…，im}是二進制文字的集合，其中的元素稱為項(item)。記D為交易(transaction)T的集合，這里交易T是項的集合，并且TI。對應每一個交易有惟一的標志，如交易號，記做TID。設X是一個I中項的集合，如果XT，那么稱交易T包含X。
一個關聯規則是形如XY的蘊涵式，這里XI，YI，并且X∩Y=。
2）支持度(support)和置信度(confidence) 規則XY在交易數據庫D中的支持度是交易集中包含X和Y的交易數與所有交易數之比，記為support(XY)，即
support(XY)=|{T:X∪YT，T∈D}|/|D|
規則XY在交易集中的置信度是指包含X和Y的交易數與包含X的交易數之比，記為confidence(XY)，即
confidence(XY)=|{T:X∪YT，T∈D}|/|{T:XT，T∈D}|
給定一個交易集D，挖掘關聯規則問題就是產生支持度和置信度分別大于用戶給定的最小支持度(minsup)和最小置信度(minconf)的關聯規則。
置信度表示規則的強度，支持度表示規則的頻度。最小支持度表示數據項集在統計意義上的最低重要性，最小置信度表示規則的最低可靠性。如果數據項集X的支持度X.sup≥minsup，則X是大數據項集(large itemset)。置信度和支持度大于相應閾值的規則稱為強關聯規則；反之，稱為弱關聯規則。關聯規則挖掘即找出數據庫的強規則。
4.2 單用戶搜索關鍵字關聯規則發現算法
可采用目前國際上眾多學者基于Apriori算法提出的一些改進或擴展方法，如DHP方法[2]、Partition法[3]、頻繁閉項集法[4]、FP2Growth算法[5]、閉包項集格[6]、TBAR算法[7]、動態剪枝[8]等，進行關聯規則的挖掘。本文結合Web日志中搜索關鍵字具體背景，提出一個基于搜索關鍵字的高效頻繁項集生成算法。引入路徑深度M和決策閾值S，單用戶在一次搜索過程中，一般最多提供三個搜索關鍵字，因此只需得到頻繁3項集L3就可以了，即M=3。
SUSKARD算法思想如下：
a）M=3。
b)初始化C1={（ITEMSETi，SUPi）/0<i c)set m=1 //m為當前路徑深度 d)選擇Cm中SUPi>S的元組（ITEMSETi，SUPi），構成Lm。 e)if m<M then goto f) else exit end if f)對于任意兩個不同的{ITEMSETx，SUPx}，{ITEMSETy，SUPy}∈Lm，將ITEMSETx和ITEMSETy取并集為ITEMSETz。對于節點個數為m+1的ITEMSETz，掃描其在SUSKSD的KEYWORDS字段中出現的次數SUPz，并將（ITEMSETz，SUPz）插入到Cm+1中。 g)m=m+1，goto d)。 獲得L1、L2、L3后，根據如下支持度和置信度計算公式，可以求得單用戶搜索關鍵字間的關聯程度： support(AB)=P(A∪B)=support_count(A∪B)/all_count confidence(AB)=P(B|A)= support_count(A∪B )/support_count(A) SUSKARD算法需要注意，Agrawal等人[9]引入了修剪技術（pruning）來減小Apriori算法候選集Ck的大小，即一個項集是頻集當且僅當它的所有子集都是頻集，這個性質在算法SUSKARD中同樣成立。 在表2的單用戶搜索關鍵字會話集SUSKSD上，執行SUSKARD算法的過程如表3~8所示（這 里M=3，S=2）。 5 實驗數據分析 根據表3~8的頻繁項集，關鍵字K1、K2間的關聯程度： support(K1K2)=support_count(K1∪K2)/all_count=3/5=60% confidence(K1K2)=support_count(K1∪K2)/support_count(K1)=3/4=75% 關鍵字K2、K1間的關聯程度： support(K2K1)=support_count(K2∪K1)/all_count=3/5=60% confidence(K2K1)=support_count(K2∪K1)/ support_count(K2)=3/3=100% 關鍵字K1、K3間的關聯程度： support(K1K3)=support_count(K1∪K3)/all_count=3/5=60% confidence(K1K3)=support_count(K1∪K3)/support_count(K1)=3/4=75% 關鍵字K3、K1間的關聯程度： support(K3K1)=support_count(K3∪K1)/all_count=3/5=60% confidence(K3K1)=support_count(K3∪K1)/support_count(K3)=3/4=75% 關鍵字K2、K3間的關聯程度： support(K2K3)=support_count(K2∪K3)/all_count=3/5=60% confidence(K2K3)=support_count(K2∪K3)/support_count(K2)=3/3=100% 關鍵字K3、K2間的關聯程度： support(K3K2)=support_count(K3∪K2)/all_count=3/5=60% confidence(K3K2)=support_count(K3∪K2)/support_count(K3)=3/4=75% 關鍵字K1、K2K3間的關聯程度： support(K1K2K3)=support_count(K1∪K2∪K3)/all_count=3/5=60% confidence(K1K2K3)=support_count(K1∪K2∪K3)/ support_count(K1)=3/4 =75% 關鍵字K2、K1K3間的關聯程度： support(K2K1K3)=support_count(K2∪K1∪K3)/all_count=3/5=60% confidence(K2K1K3)=support_count(K2∪K1∪K3)/support_count(K2)=3/3=100% 關鍵字K3、K1K2間的關聯程度： support(K3K1K2)=support_count(K3∪K1∪K2)/all_count=3/5=60% confidence(K3K1K2)=support_count(K3∪K1∪K2)/support_count(K3)=3/4=75% 本文假設最小支持度(minsup)為20%，最小置信度(minconf)為70%，因此以上規則均為強關聯規則。當分析出某單個用戶的搜索關鍵字關聯規則后，此用戶在日后提交關鍵字K1的搜索請求時，根據上文得到如下強關聯規則： K1K2 K1K3 K1K2K3 6 結束語 本文通過若干挖掘算法，將Web原始日志信息進行用戶識別，會話分組后，提取單一用戶多次會話中的搜索關鍵字關聯規則，并根據此規則實現了個性化搜索引擎模型。搜索引擎模型可以自動將用戶搜索的關鍵字擴充為與其有強關聯規則的組合關鍵字搜索。聯系到具體實例，就是當用戶再次搜索K1=apple時，搜索引擎返回的是同時含有（K1=apple，K2=ipod，K3=mp3）的搜索記錄，從而實現了單用戶的個性化搜索結果。 參考文獻： ［1］AGRAWAL R，IMIELINSKI T，SWAMI A.Mining association rules between sets of items in large database[C]//Proc of ACM SIGMOD International Conference on Management of Data.Washington DC:[s.n.]，1993:207216. [2]PARK J S，CHEN M S，YU P S.An effective hash based algorithm for mining association rules[C]//Proc of ACM SIGMOD International Conference on Management of Data.1995:175186. [3]SAVASERE A OMIECINSKI E NAVATHE S. An efficient algorithm for mining association rules in large database[C]//Proc of the 21th International Conference on Very Large Database.1995:432-443. [4]PASQUIER N，BASTIDE Y TAOUIL R，et al.Discovering frequent closed item sets for association rules[C]//Proc of the 5th International Conference on Database Theory.1999:398416. [5]HAN J PEI J YIN Y. Mining frequent patterns without candidate generation[C]//Proc ofACM SIGMOD Internal Conference on Management of Data.Dallas，Texas:ACM Press，2000:112. [6]PASQUOER N，BASTIDE Y，TAOUIL R.Efficient mining of association rules using closed item set lattices [J].Information System，1999，24(1):2546. [7]BERZAL F，CUBERO JC，MARIN N，et al.TBAR:an efficient method for association rule mining in relational databases[J].Data Knowledge Engineering，2001，37(1):4764. [8]皮德常，秦小麟，王寧生.基于動態剪枝的關聯規則挖掘算法[J].小型微型計算機系統，2004 25(10):18501852. [9]AGRAWAL R，SRIKANT R.Fast algorithms for mining association rules[C]//Proc of International Conference on Very Large Databases.1994:487-499.
