袁 藝, 陳海光

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

?

web日志挖掘中會(huì)話識(shí)別方法

袁 藝, 陳海光

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

通過(guò)對(duì)傳統(tǒng)web會(huì)話識(shí)別方法分析和比較,改進(jìn)了目前最常用的基于時(shí)間閾值會(huì)話識(shí)別方法,提出了一種基于動(dòng)態(tài)閾值會(huì)話識(shí)別方法,該算法采用動(dòng)態(tài)計(jì)算會(huì)話中請(qǐng)求記錄間的平均時(shí)間間隔和動(dòng)態(tài)計(jì)算會(huì)話中頁(yè)面的平均大小相結(jié)合的方法,根據(jù)用戶和網(wǎng)頁(yè)的特點(diǎn)動(dòng)態(tài)調(diào)整閾值,相對(duì)于傳統(tǒng)單一的先驗(yàn)閾值,該方法可以根據(jù)不同的用戶訪問(wèn)不同的頁(yè)面生成動(dòng)態(tài)的閾值,充分運(yùn)用用戶和網(wǎng)頁(yè)信息.經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證,該方法可以識(shí)別出更多的用戶會(huì)話,且識(shí)別會(huì)話的準(zhǔn)確率和查全率也比傳統(tǒng)算法更高.

web挖掘; 會(huì)話識(shí)別; 時(shí)間閾值; 數(shù)據(jù)預(yù)處理

0 引 言

隨著Internet 的不斷發(fā)展,越來(lái)越多的組織、企業(yè)、機(jī)構(gòu)通過(guò)網(wǎng)絡(luò)與用戶交流或交易.為了留住已有用戶,爭(zhēng)取潛在客戶,必須使自己的網(wǎng)站更加實(shí)用,更加有吸引力.為了實(shí)現(xiàn)這個(gè)目標(biāo),一般有兩種方法,第一種是通過(guò)要求用戶對(duì)瀏覽過(guò)的頁(yè)面,提交瀏覽體驗(yàn),得到用戶的喜好、興趣.第二種是通過(guò)對(duì)用戶的訪問(wèn)日志進(jìn)行分析,從而獲取用戶的瀏覽習(xí)慣,提高和改進(jìn)網(wǎng)站.

web日志分析,通過(guò)分析用戶訪問(wèn)網(wǎng)站的日志來(lái)得到用戶的訪問(wèn)模型,從而獲取用戶的個(gè)人興趣和訪問(wèn)習(xí)慣,調(diào)整網(wǎng)站內(nèi)容,優(yōu)化網(wǎng)站結(jié)構(gòu),發(fā)展個(gè)性服務(wù),發(fā)掘潛在用戶.在web日志挖掘中web日志預(yù)處理的會(huì)話標(biāo)識(shí)最重要和最耗時(shí).會(huì)話識(shí)別的目的是將用戶的多次請(qǐng)求劃分成一個(gè)個(gè)獨(dú)立的會(huì)話,每個(gè)會(huì)話代表一次訪問(wèn)過(guò)程,只有用戶的這些原始會(huì)話被識(shí)別后,才能應(yīng)用web數(shù)據(jù)的挖掘算法挖掘用戶模式,從而優(yōu)化網(wǎng)站,發(fā)展個(gè)性服務(wù),挖掘潛在用戶.

1 web日志挖掘數(shù)據(jù)預(yù)處理

web日志挖掘預(yù)處理階段主要有以下幾個(gè)步驟組成:數(shù)據(jù)清洗、用戶識(shí)別、會(huì)話識(shí)別.

1.1 清洗數(shù)據(jù)

web日志數(shù)據(jù)本身的特點(diǎn)不能直接用于日志挖掘,因此,數(shù)據(jù)清洗的目的就是把日志數(shù)據(jù)格式化,刪除不相干數(shù)據(jù),合并能合并的數(shù)據(jù)域,生成新的格式,使其適合挖掘算法.

首先要對(duì)web數(shù)據(jù)清洗,刪除不相關(guān)的數(shù)據(jù):

1) 去掉爬蟲(chóng)軟件和搜索代理等網(wǎng)絡(luò)機(jī)器人訪問(wèn)請(qǐng)求;

2) 刪除無(wú)效頁(yè)面;

3) 刪除以head為請(qǐng)求方式的web日志;

4) 刪除框架、CSS文件、腳本等非用戶請(qǐng)求的邏輯單位;

5) 對(duì)圖片、視頻進(jìn)行處理,計(jì)算網(wǎng)頁(yè)大小.

1.2 用戶識(shí)別

如果一個(gè)網(wǎng)站必須用戶登錄以后才可以瀏覽網(wǎng)頁(yè),用戶識(shí)別將變得非常簡(jiǎn)單,只要根據(jù)用戶名就可以很好識(shí)別用戶,但是現(xiàn)在絕大多數(shù)網(wǎng)站都允許訪問(wèn)者匿名瀏覽網(wǎng)頁(yè),在這種情況下,用戶識(shí)別就很具有挑戰(zhàn)性.如果網(wǎng)站使用的是通用日志格式(common log format)來(lái)記錄用戶請(qǐng)求記錄,那么就只能使用IP地址來(lái)區(qū)分用戶,因?yàn)閏ommon log format沒(méi)有記錄關(guān)于操作系統(tǒng)和瀏覽器等信息.當(dāng)然也可以使用cookies來(lái)識(shí)別用戶,當(dāng)客戶端用戶啟用cookies時(shí),第一次請(qǐng)求訪問(wèn)某個(gè)網(wǎng)站,該網(wǎng)站服務(wù)器在返回所請(qǐng)求內(nèi)容的同時(shí)會(huì)返回相應(yīng)的cookie,當(dāng)下一次該用戶請(qǐng)求訪問(wèn)同一個(gè)網(wǎng)站其他頁(yè)面時(shí),如果cookie沒(méi)有過(guò)期,那么用戶瀏覽器會(huì)把cookie和請(qǐng)求一起發(fā)給服務(wù)器,從而服務(wù)器可以識(shí)別用戶.但是因?yàn)閏ookies存在一些問(wèn)題,一般不被用于用戶識(shí)別,首先客戶端可能會(huì)禁止cookies使用,或者手動(dòng)清除掉存儲(chǔ)在自己機(jī)器上的cookies,其次cookies使用可能會(huì)侵犯用戶的隱私.

下面是最常使用的用戶識(shí)別方法:

1) 不同的IP地址代表不同的用戶;

2) 相同的IP地址,但用戶代理(Agent)數(shù)據(jù)域中的操作系統(tǒng)或?yàn)g覽器不同,則可以認(rèn)為是不同用戶;

3) 如果IP地址、操作系統(tǒng)和瀏覽器都相同,則判斷每一個(gè)請(qǐng)求的頁(yè)面與訪問(wèn)過(guò)的頁(yè)面之間是否有鏈接,如果一個(gè)請(qǐng)求訪問(wèn)的頁(yè)面與之前訪問(wèn)的所有頁(yè)面都沒(méi)有直接的鏈接,則假設(shè)是不同用戶.

然而,以上的規(guī)則并不能保證準(zhǔn)確識(shí)別出每一個(gè)用戶,因?yàn)橛袝r(shí)無(wú)法從web日志中獲取瀏覽器和操作系統(tǒng)信息,即像Common Log Format這樣的日志并不包含Agent相關(guān)信息,即使使用的是擴(kuò)展日志,同一個(gè)用戶也可以同時(shí)使用不同操作系統(tǒng)或?yàn)g覽器訪問(wèn)web服務(wù)器,將被認(rèn)為是不同用戶.具有相同IP地址的多個(gè)用戶使用相同操作系統(tǒng)和相同瀏覽器,并且看過(guò)的頁(yè)面集合也一樣會(huì)被認(rèn)為是同一個(gè)用戶.所以要非常準(zhǔn)確識(shí)別出每個(gè)用戶是很困難的,用戶識(shí)別結(jié)果直接影響整個(gè)預(yù)處理結(jié)果.

1.3 會(huì)話識(shí)別

可以把用戶在一次訪問(wèn)某網(wǎng)站期間從進(jìn)入該網(wǎng)站到離開(kāi)該網(wǎng)站所進(jìn)行的一系列活動(dòng)稱為一個(gè)會(huì)話.在跨度時(shí)間較大的web服務(wù)器中,用戶可能多次訪問(wèn)了該網(wǎng)站,會(huì)話識(shí)別的目的是將同一個(gè)用戶的多次請(qǐng)求劃分成一個(gè)個(gè)獨(dú)立的會(huì)話,每個(gè)會(huì)話代表一次訪問(wèn)過(guò)程.

web會(huì)話識(shí)別方法有很多,如基于時(shí)間閾值方法、最大向前序列方法、參引長(zhǎng)度方法、Fuzzy c-means聚類算法等,根據(jù)文獻(xiàn)[1]基于時(shí)間閾值識(shí)別會(huì)話是最常用的.文獻(xiàn)[2]中基于會(huì)話持續(xù)時(shí)間的方法,被許多商業(yè)產(chǎn)品用30 min作為默認(rèn)閾值來(lái)使用.文獻(xiàn)[3]等文獻(xiàn)又提出了從10 min到2 h不等的更多閾值.文獻(xiàn)[4]通過(guò)動(dòng)態(tài)計(jì)算頁(yè)面停留時(shí)間來(lái)調(diào)整會(huì)話閾值.文獻(xiàn)[5]提出了時(shí)間閾值與共享模式相結(jié)合來(lái)識(shí)別會(huì)話,首先使用基于時(shí)間閾值方法來(lái)識(shí)別會(huì)話,然后對(duì)識(shí)別后的會(huì)話采用共享模式進(jìn)行二次過(guò)濾識(shí)別.文獻(xiàn)[6]認(rèn)為會(huì)話閾值與參引長(zhǎng)度有關(guān),通過(guò)計(jì)算參引長(zhǎng)度來(lái)確定會(huì)話時(shí)間閾值.

基于時(shí)間閾值的會(huì)話識(shí)別方法,主要研究集中在如何確定會(huì)話閾值.對(duì)于固定閾值方法,閾值一旦確定就不會(huì)改變,顯然沒(méi)有考慮具體用戶和網(wǎng)站對(duì)會(huì)話的影響.最合理的時(shí)間閾值的選取顯然要依賴具體的用戶和網(wǎng)站.

2 改進(jìn)的基于動(dòng)態(tài)閾值會(huì)話識(shí)別方法

2.1 基本思想

每個(gè)用戶存在個(gè)體差異,如用戶計(jì)算機(jī)性能、網(wǎng)絡(luò)位置、網(wǎng)絡(luò)連接速度、閱讀速度、上網(wǎng)習(xí)慣,以及使用計(jì)算機(jī)的熟練程度等一系列因素.不同的用戶會(huì)話時(shí)間通常也是不相同的.例如,相同頁(yè)面不同用戶的瀏覽速度和興趣也不一定相同.但是,對(duì)于同一個(gè)用戶,其所屬的網(wǎng)絡(luò)環(huán)境、個(gè)人興趣、瀏覽速度等因素相對(duì)不同用戶來(lái)說(shuō),是比較穩(wěn)定的.所以除去用戶個(gè)體差異對(duì)會(huì)話閾值的影響,會(huì)話閾值還受網(wǎng)站的結(jié)構(gòu)、頁(yè)面的信息量影響.即同一個(gè)用戶瀏覽信息量大的頁(yè)面所需要的時(shí)間也應(yīng)更多.所以充分考慮了用戶和頁(yè)面信息量對(duì)會(huì)話閾值的影響,提出動(dòng)態(tài)頁(yè)面平均停留時(shí)間和頁(yè)面信息量相結(jié)合的算法.與以往固定的閾值及文獻(xiàn)[4]只考慮頁(yè)面間停留時(shí)間的動(dòng)態(tài)閾值方法(AST)相比,可以更好地根據(jù)用戶和網(wǎng)頁(yè)來(lái)識(shí)別會(huì)話,實(shí)驗(yàn)證明可以識(shí)別出更多的會(huì)話.

根據(jù)上面的思想,提出動(dòng)態(tài)調(diào)整閾值方法,當(dāng)有新請(qǐng)求被加入會(huì)話時(shí),頁(yè)面間停留時(shí)間相對(duì)較大時(shí)才會(huì)重新計(jì)算動(dòng)態(tài)閾值.動(dòng)態(tài)頁(yè)面停留時(shí)間計(jì)算公式如下:dynamicAverageStayTime=a(dynamicAverageStayTime+a(較大時(shí)間間隔)/2,其中a為平滑系數(shù),動(dòng)態(tài)閾值計(jì)算公式如下:

其中b為平滑系數(shù),currentPagesize為當(dāng)前請(qǐng)求頁(yè)面大小,averagePagesize為用戶會(huì)話平均頁(yè)面大小.

2.2 算法描述

因?yàn)樵谇捌谇逑慈罩緮?shù)據(jù)的同時(shí)已經(jīng)把日志數(shù)據(jù)按照用戶進(jìn)行了排序,且相同用戶默認(rèn)按照訪問(wèn)時(shí)間遞增排序,所以在會(huì)話識(shí)別算法(DPAST)中,前一個(gè)請(qǐng)求記錄的用戶名如果與后一個(gè)請(qǐng)求記錄的用戶名不同,則認(rèn)為前一個(gè)請(qǐng)求記錄是屬于前一個(gè)會(huì)話且該會(huì)話結(jié)束,后一個(gè)請(qǐng)求記錄是屬于新的一個(gè)會(huì)話.對(duì)于相同用戶名的兩條連續(xù)請(qǐng)求記錄,如果時(shí)間間隔小于動(dòng)態(tài)閾值,表明他們屬于同一個(gè)會(huì)話,重新計(jì)算會(huì)話平均頁(yè)面大小(averagePagesize),如果同一個(gè)會(huì)話內(nèi)前后兩個(gè)請(qǐng)求記錄的時(shí)間間隔相對(duì)較大則重新計(jì)算動(dòng)態(tài)平均頁(yè)面停留時(shí)間(dynamicAverageStayTime)和動(dòng)態(tài)時(shí)間閾值(dynamicThreshold).該算話時(shí)間復(fù)雜度為O(n),其中n為web日志訪問(wèn)記錄長(zhǎng)度.流程圖如圖1所示.

DPAST偽代碼如圖2所示.

圖2 DPAST偽代碼

3 實(shí)驗(yàn)測(cè)試與分析

本節(jié)將給出優(yōu)化后會(huì)話識(shí)別算法的實(shí)驗(yàn)結(jié)果,并與最常用的基于會(huì)話持續(xù)時(shí)間的算法(固定閾值為30 min)、基于頁(yè)面停留時(shí)間的算法(固定閾值為10 min)和只考慮頁(yè)面停留時(shí)間的動(dòng)態(tài)調(diào)整閾值的算法(AST)進(jìn)行分析比較.實(shí)驗(yàn)數(shù)據(jù)來(lái)源于美國(guó)航空航天局航天中心的Web服務(wù)器日志,該數(shù)據(jù)集是開(kāi)源的,任何人都可以用于研究和學(xué)習(xí),數(shù)據(jù)的真實(shí)可靠性已經(jīng)被許多研究人員認(rèn)可.該日志記錄了1995年7月整整一個(gè)月的訪問(wèn)請(qǐng)求.由于數(shù)據(jù)量巨大,人工識(shí)別會(huì)話非常耗時(shí),所以只選取一天數(shù)據(jù)進(jìn)行分析,根據(jù)對(duì)整個(gè)7月日志的分析,12日前后訪問(wèn)請(qǐng)求數(shù)量波動(dòng)不大,所以本實(shí)驗(yàn)只選取1995年7月12日這一天數(shù)據(jù)來(lái)測(cè)試本算法.經(jīng)統(tǒng)計(jì)該天一共有92 536條訪問(wèn)請(qǐng)求,經(jīng)過(guò)數(shù)據(jù)清洗后的日志數(shù)量為22 681(裁剪了大量不相干數(shù)據(jù)),對(duì)于清洗排序后的數(shù)據(jù)進(jìn)行人工會(huì)話識(shí)別,7月12日這一天內(nèi)產(chǎn)生的真實(shí)會(huì)話有6 270個(gè).

分別用上面三種算法進(jìn)行會(huì)話識(shí)別結(jié)果如表1所示,表1中A代表真實(shí)會(huì)話個(gè)數(shù)(A=6 270),T表示發(fā)現(xiàn)會(huì)話個(gè)數(shù),R表示發(fā)現(xiàn)的真實(shí)會(huì)話個(gè)數(shù).DPAST算法中initSessionTime為16 min,largerintervalTime為10 min,平滑系數(shù)a,b都為1.

從表1可以看出,作者提出的動(dòng)態(tài)閾值算法(DPAST)無(wú)論是從精確度還是查全度來(lái)講,都優(yōu)于基于固定先驗(yàn)閾值和只考慮頁(yè)面停留時(shí)間的動(dòng)態(tài)調(diào)整閾值的會(huì)話識(shí)別算法.

4 結(jié)束語(yǔ)

通過(guò)對(duì)最常用的固定先驗(yàn)閾值算法進(jìn)行改進(jìn),使會(huì)話閾值能夠根據(jù)用戶和網(wǎng)頁(yè)動(dòng)態(tài)調(diào)整,實(shí)驗(yàn)證明能更好地識(shí)別會(huì)話.

表1 三種會(huì)話識(shí)別算法識(shí)別結(jié)果

對(duì)于頁(yè)面對(duì)會(huì)話閾值的影響,現(xiàn)在該算法還只考慮了頁(yè)面的大小,今后會(huì)找一些信息量更多的日志,對(duì)頁(yè)面進(jìn)行量化,綜合考慮網(wǎng)站結(jié)構(gòu)、網(wǎng)頁(yè)性質(zhì)(內(nèi)容頁(yè)面還是輔助頁(yè)面)、網(wǎng)頁(yè)大小、超鏈接能因素對(duì)頁(yè)面進(jìn)行量化,得出每個(gè)頁(yè)面的量化值,將量化值帶入該算法進(jìn)行會(huì)話識(shí)別.

[1] Pabarskaite Z,Raudys A.A process of knowledge discovery from web log data:Systematization and critical review [J].Journal of Intelligent Information Systems,2007,28(1):79-104.

[2] 蔡浩,賈宇波,黃成偉,等.Web日志挖掘中的會(huì)話識(shí)別算法 [J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(6):1321-1323.

Cai H,Jia Y B,Huang C W,et al.In Web log mining session identification algorithm [J].Computer Engineering and Design,2009,30(6):1321-1323.

[3] Liu H,Ke?elj V.Combined mining of Web server logs and web contents for classifying user navigation patterns and predicting users′ future requests [J].Data & Knowledge Engineering,2007,61(2):304-330.

[4] Spiliopoulou M,Mobasher B,Berendt B,et al.A Framework for the Evaluation of Session Reconstruction Heuristics in Web-Usage Analysis [J].Informs Journal on Computing,2003,15(2):171-190.

[5] Montgomery A L,Faloutsos C.IdentifyingWeb Browsing Trends and Patterns [J].Computer,2001,34(7):94-95.

[6] Guerbas A,Addam O,Zaarour O,et al.Effective web log mining and online navigational pattern prediction [J].Knowledge-Based Systems,2013,49:50-62.

[7] Kapusta J,Munk M,Svec P,et al.Determining the Time Window Threshold to Identify User Sessions of Stakeholders of a Commercial Bank Portal [J].Procedia Computer Science,2014,29:1779-1790.

[8] 陳子軍,王鑫昱,李偉.一種Web日志會(huì)話識(shí)別的優(yōu)化方法 [J].計(jì)算機(jī)工程,2007,33(1):95-97.

Chen Z J,Wang X Y,Li W.The optimization of a Web log session identification method [J].Computer Engineering,2007,33(1):95-95.

[9] 方元康,胡學(xué)鋼,夏啟壽.Web日志預(yù)處理中優(yōu)化的會(huì)話識(shí)別方法 [J].計(jì)算機(jī)工程,2009,35(7):49-51.

Fang Y K,Hu X G,Xia Q S.Web log pretreatment session identification method of optimization in [J].Computer Engineering,2009,35(7):49-51.

[10] 周愛(ài)武,程博,李孫長(zhǎng),等.Web日志挖掘中的會(huì)話識(shí)別方法 [J].計(jì)算機(jī)工程與設(shè)計(jì),2010,31(5):936-938.

Zhou A W,Chen B,Li S C,et al.In Web log mining session identification method [J].Computer Engineering and Design,2010,31(5):936-938.

(責(zé)任編輯：包震宇,馮珍珍)

Method of session identification in web log mining

YUAN Yi, CHEN Haiguang

(College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai 200234,China)

In this paper,by analyzing and comparing of the traditional web method of session identification,with the improvement on the most commonly used method of session identification based on time threshold,this paper proposed a session identification method based on dynamic threshold,in which the algorithm uses the average time interval between request records in conversation of dynamic calculation,and in combination of the average size of dynamic calculation session pages dynamically adjusts the threshold according to the characteristics of users and Webpage.Compared with the traditional single a priori threshold,this method can generate dynamic threshold according to different user access to different pages and make full use of user information and Webpage.After experimental verification,this method can identify more user sessions.The accuracy of session identification and the recall rate are higher than the traditional algorithm.

web mining; session identification; threshold; data preprocessing

2015-08-24

陳海光,中國(guó)上海市徐匯區(qū)桂林路100號(hào),上海師范大學(xué)信息與機(jī)電工程學(xué)院,郵編:200234,E-mail:19276368@qq.com

TP 393

A

1000-5137(2016)05-0593-06

10.3969/J.ISSN.1000-5137.2016.05.013