賈小貝，方歡 (安徽理工大學(xué)數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001)

隨著網(wǎng)絡(luò)的迅速發(fā)展，囤積在互聯(lián)網(wǎng)上的數(shù)據(jù)也越來(lái)越多。面對(duì)如此海量的信息，如何快速提取所需要的信息是Web用戶所關(guān)心的問(wèn)題之一。與此同時(shí)，對(duì)Web站點(diǎn)的拓?fù)浣Y(jié)構(gòu)的設(shè)計(jì)以及功能也提出了更多的要求，比如如何改善網(wǎng)站的結(jié)構(gòu)以方便用戶迅速找出所需要的信息，如何為用戶提供個(gè)性化服務(wù)，如何發(fā)現(xiàn)潛在的訪問(wèn)群體，為不同的訪問(wèn)群體做出準(zhǔn)確的市場(chǎng)定位。因此，一種將傳統(tǒng)數(shù)據(jù)應(yīng)用于Web領(lǐng)域的技術(shù)——Web挖掘應(yīng)運(yùn)而生。由于Web信息普遍具有無(wú)結(jié)構(gòu)性、缺乏完整性約束和分布松散的特點(diǎn)，因此直接對(duì)Web信息進(jìn)行挖掘具有相當(dāng)?shù)碾y度。Web日志具有完美的結(jié)構(gòu)，其包含的信息反映了用戶瀏覽行為特點(diǎn)，為Web挖掘提供了良好的前提條件[1]。 對(duì)Web用戶聚類(lèi)基于Web日志進(jìn)行挖掘,該方法的主要步驟是首先對(duì)用戶日志進(jìn)行預(yù)處理，然后從中選取所需的用戶特征計(jì)算行為相似度，最后應(yīng)用聚類(lèi)算法得到聚類(lèi)結(jié)果。通過(guò)對(duì)用戶進(jìn)行聚類(lèi)最終達(dá)到用戶與網(wǎng)站間一對(duì)一(onetoone)的模式。

過(guò)程聚類(lèi)(clustering)是將數(shù)據(jù)對(duì)象劃分成若干組(class)或者類(lèi)(cluster)的過(guò)程[2],劃分后的結(jié)果使得組內(nèi)的數(shù)據(jù)相似度很高，不同組的數(shù)據(jù)相似度較低。與聚類(lèi)相關(guān)的算法很多，主要包括劃分聚類(lèi)算法、層次聚類(lèi)算法、網(wǎng)格聚類(lèi)算法、模型聚類(lèi)算法以及密度聚類(lèi)算法[3，4]。作為一種重要的數(shù)據(jù)挖掘技術(shù)，聚類(lèi)已經(jīng)在Web日志挖掘中得到廣泛的應(yīng)用。但是與傳統(tǒng)數(shù)據(jù)挖掘相對(duì)比，聚類(lèi)技術(shù)在Web日志挖掘中的應(yīng)用所需要探討的問(wèn)題還有很多。如在Web日志挖掘中，關(guān)于用戶訪問(wèn)路徑相似度的評(píng)價(jià)方法具有良好的實(shí)際應(yīng)用價(jià)值，但是到目前為止，有關(guān)用戶訪問(wèn)路徑的相似度計(jì)算大部分是基于集合之間的交集運(yùn)算，如夾角余弦方法、Jaccard相關(guān)系數(shù)計(jì)算法、名義變量、基于非歐氏距離的序列排列方法(SAM)、多維序列排列方法[5～8]。文獻(xiàn)[9]提出將雅克比系數(shù)和CM(Common road length divide Max road length)系數(shù)相結(jié)合來(lái)計(jì)算不同訪問(wèn)序列間的相似度。文獻(xiàn)[10]提出首先對(duì)頁(yè)面聚類(lèi)再進(jìn)行用戶相似度計(jì)算的方法。然而，這些研究都對(duì)行為序列的時(shí)間信息進(jìn)行了弱化。一般而言，用戶的Cookies記錄了用戶瀏覽路徑，其主要描述特定用戶在一段時(shí)間內(nèi)所依瀏覽的頁(yè)面以及各個(gè)瀏覽頁(yè)面駐留時(shí)間的一個(gè)集合。已有的傳統(tǒng)方法或者沒(méi)有把瀏覽的頁(yè)面作為一種序列考慮，或者在處理的過(guò)程當(dāng)中忽略掉了其中所包含的時(shí)間信息，這就使得計(jì)算出的結(jié)果不能真實(shí)地反映出用戶間的行為相似性程度。文獻(xiàn)[11]提出了一種Web的用戶聚類(lèi)方法，將用戶的瀏覽模式看做一個(gè)序列，與此同時(shí)也考慮了與瀏覽頁(yè)面相關(guān)的時(shí)間信息，但是該方法在計(jì)算頁(yè)面停留時(shí)間時(shí)，采用的是平均停留時(shí)間(即整條路徑總的停留時(shí)間除以瀏覽的頁(yè)面數(shù))。然而，用戶往往在感興趣的頁(yè)面停留的時(shí)間較長(zhǎng)，在不感興趣的頁(yè)面駐留時(shí)間較短，采用平均時(shí)間很難發(fā)現(xiàn)用戶的偏好，因此所得到的聚類(lèi)就不能真正反映用戶間的區(qū)別。

下面，筆者結(jié)合Web用戶瀏覽行為的主要特征，基于序列對(duì)齊[12]的核心思想,提出了一種新的相似度計(jì)算方法。這種方法不僅把瀏覽頁(yè)面作為一種序列，同時(shí)還考慮了頁(yè)面所包含的時(shí)間信息，通過(guò)引入相似度矩陣對(duì)用戶進(jìn)行行為聚類(lèi)的分析和研究。最后，通過(guò)一些程序采集到的Web用戶的日志進(jìn)行算法驗(yàn)證，并將其結(jié)果與傳統(tǒng)的SPSS聚類(lèi)結(jié)果進(jìn)行比較，驗(yàn)證了所提出方法的有效性。

1 相關(guān)概念

定義1[13](隸屬度) 項(xiàng)Ui與類(lèi)cj的連接強(qiáng)度J(Ui,cj)定義為：

式中，sim(Ui,Uk)表示項(xiàng)Ui與cj類(lèi)中的Uk項(xiàng)的相似度；m為cj中元素項(xiàng)的個(gè)數(shù)。

定義2[9](相似度矩陣) 相似度矩陣以對(duì)象-對(duì)象的結(jié)構(gòu)表示，存儲(chǔ)n個(gè)對(duì)象兩兩之間的相似性，表示為一個(gè)n×n維的矩陣A：

(1)

式中，A是一個(gè)對(duì)稱陣，AT=A；dij量化表示對(duì)象i,j之間的相似性。一般而言，dij是一個(gè)非負(fù)的數(shù)值，且dij的值越接近1，則意味著i,j之間越接近；當(dāng)dij的值越接近0，則表示i,j之間差異越大。

定義3(含時(shí)間因素的序列) 二元組N=(T;DI)是一個(gè)含時(shí)間的序列,其中T是一個(gè)活動(dòng)序列集合，DI是定義在活動(dòng)集T上的時(shí)間函數(shù)，即DI:T→R0，其中，R0≥0。

定義4(含時(shí)間因素的子序列) 二元組N=(T;DI) 是一個(gè)含時(shí)間的序列,其中T是一個(gè)活動(dòng)序列集合，如果T1?T，則N1=(T1;DI)是N的一個(gè)含時(shí)間因素的子序列。

定義5[14](不含時(shí)間的2個(gè)序列的相似度)P,Q是2個(gè)字符串序列，這2個(gè)字符串之間的相似度可表示為SSAM(P,Q):

(2)

式中，ωd為刪除操作的代價(jià)；ωi為插入操作的代價(jià)；η為重排操作的代價(jià)；ωd，ωi，η均是一個(gè)人為給定的一個(gè)正常數(shù)；D為刪除操的作的次數(shù)；I為插入操作的次數(shù)；R為重排操作的次數(shù)；|P|,|Q|分別表示每個(gè)字符串的長(zhǎng)度。

定義6(含時(shí)間因素的SAM距離)S1={(t1,T1),(t2,T2),…,(ti,Ti)}(1≤i≤n)和S2={(a1,I1),(a2,I2),…,(aj,Ij)}(1≤j≤n)為2個(gè)帶有時(shí)間戳(時(shí)間戳表示的是一個(gè)時(shí)間序列T={t1,t2,…,tn},其中序列中的每個(gè)元素描述了對(duì)應(yīng)活動(dòng)的持續(xù)時(shí)間)的序列集，其中ti∈T,aj∈A代表活動(dòng)集，Ti∈T′,Ij∈I代表時(shí)間集。則這2個(gè)序列集之間的距離記為dSAM(S1,S2)：

(3)

式中，|Ti-Tj|代表一次補(bǔ)償操作；|Ti-Tj|*|i-j|代表一次重排操作。

定義7(含時(shí)間因素的2個(gè)序列集間的相似度)S1={(t1,T1),(t2,T2),…,(ti,Ti)}(1≤i≤n)和S2={(a1,I1),(a2,I2),…,(aj,Ij)}(1≤j≤n)為2個(gè)帶有時(shí)間戳的序列集，其中ti∈T,aj∈A代表活動(dòng)集，Ti∈T′,Ij∈I代表時(shí)間集。這2個(gè)子序列集之間的相似度記為sim(S1,S2):

(4)

這2個(gè)含時(shí)間因素的序列間之間的相似度記為SIM(S1,S2)：

(5)

其中,w1+w2=1。

定義8(2個(gè)子類(lèi)之間的相似度) 對(duì)于2個(gè)子類(lèi)C1，C2，C1中包含的元素個(gè)數(shù)為|C1|,C2中包含的元素個(gè)數(shù)為|C2|，則這2個(gè)子類(lèi)C1，C2之間的相似度表示為SIM(C1,C2):

(6)

其中，α+β=1。

定理1[15](相似傳遞性) 如果P和Q相似，Q和R也相似，那么P和R在一定程度上也具有相似性。

2 基于活動(dòng)時(shí)間對(duì)齊的相似度評(píng)價(jià)算法

下面給出2個(gè)用戶間行為相似度評(píng)價(jià)算法——基于活動(dòng)時(shí)間對(duì)齊的相似度評(píng)價(jià)算法(Similarity Calculation Method Based On Activity Time Alignment,SCMBATA)。

輸入：2個(gè)用戶包含時(shí)間的活動(dòng)序列：

S1={(t1,T1),(t2,T2),…,(tn,Tn)}

S2={(a1,I1,(a2,I2),…,(an,In)}

輸出：用戶行為的相似度

SIM(u1,u2)

步驟：

Step1:i=1,j=1;

Step2: if (ti=aj)

(|ti-aj|) /進(jìn)行補(bǔ)償操作/

i++,j++;

else if (ti≠aj)

(|ti-aj|*|i-j|);/重排操作/

i++,j++；

Step3:i=n

/結(jié)束/

return SIM(u1,u2)。

3 基于Web訪問(wèn)日志的用戶聚類(lèi)算法

下面給出基于Web訪問(wèn)日志的用戶聚類(lèi)算法——基于相似度矩陣的聚類(lèi)評(píng)價(jià)算法(Clustering Based On Similarity Matrix Algorithm,CBOSMA)。

輸入：相似度矩陣，相似度閾值λ0

輸出：Web用戶聚類(lèi)結(jié)果集合

步驟：

Step1 輸個(gè)相似度矩陣，取除對(duì)角線外所有元素的平均值作為相似度閾值λ0：

Step2 用三元組∑=(i,j,sim(ui，uj))(其中的元素分別代表行號(hào)，列號(hào)，相似值；且(i≠j)表示出相似矩陣的前(n-1行)每一行的最大值；

Step3 根據(jù)相似度矩陣中當(dāng)?shù)脑剡m當(dāng)計(jì)算相似度閾值λ=γλ0(其中γ為調(diào)節(jié)系數(shù)，其中0≤γ≤1)，使分類(lèi)的精度較高；

Step4 將所得到三元組中的相似度值分別與相似度閾值比較，大于閾值的元素所在的行號(hào)和列號(hào)對(duì)應(yīng)的元素歸為一類(lèi)，小于閾值的所在行號(hào)的元素單獨(dú)歸為一類(lèi)。即如果sim(ui,uj)≥λ，那么class1={useri,userj}。如果sim(ui，uj)<λ，則class2={user2};

Step6 如果類(lèi)間有交集，則用定義1中的隸屬度判別該交集項(xiàng)所屬的類(lèi)；

Step7 由定義8計(jì)算類(lèi)間相似度，得到由類(lèi)間相似度構(gòu)成的相似度矩陣，繼續(xù)上面的步驟直到得到需要的分類(lèi)結(jié)果。

4 實(shí)證分析

圖1 程序截取的日志片段圖

通過(guò)對(duì)所選取的數(shù)據(jù)集(該數(shù)據(jù)集來(lái)源于data tang.com共享平臺(tái))中的1000個(gè)用戶的日志文件進(jìn)行清洗、過(guò)濾等預(yù)處理。接著，把從數(shù)據(jù)集中抽取的12個(gè)用戶(其中這12個(gè)用戶在數(shù)據(jù)集中的序號(hào)為87,89,91,170,177,450,656,665，741,773,776,898)的日志信息作為分析對(duì)象：首先計(jì)算用戶間的相似度，然后進(jìn)行聚類(lèi)。樣本數(shù)據(jù)包中的數(shù)據(jù)文件可分為2部分，其中behavior文件夾中是按日期歸檔的樣本行為日志，demographic.csv是樣本的人口屬性信息，二者可通過(guò)樣本ID關(guān)聯(lián)。圖1展示了一個(gè)典型的日志片段，表1表示了該日志片段中各符號(hào)代表的含義。

表1 日志片段中的符號(hào)含義

為了對(duì)所選取的用戶行為進(jìn)行更加精確地分析，截取每個(gè)日志的同一個(gè)時(shí)間段(比如開(kāi)機(jī)后1h)進(jìn)行分析。首先，從這些日志文本中提取所需要的路徑以及與路徑相關(guān)的時(shí)間信息(以一個(gè)進(jìn)程名的變更作為一個(gè)動(dòng)作的完成，2個(gè)動(dòng)作間隔作為在一個(gè)動(dòng)作上的駐留時(shí)間)；然后，根據(jù)筆者提出的相似性計(jì)算方法SCMBATA，計(jì)算得到這12個(gè)用戶相似性矩陣：

由相似性矩陣A，根據(jù)聚類(lèi)算法CBOMSA，將這12個(gè)用戶分類(lèi)，分類(lèi)結(jié)果如下：

C1={user1,user3,user4,user5,user8,user9,user12}

C2={user2,user6,user10,}

C3={user7,user11}

根據(jù)分類(lèi)，由式(6)可得類(lèi)間的相似度(在此規(guī)定權(quán)重因子以各類(lèi)中元素占總的元素的比重表示)：

SIM(C1,C2)=0.35 SIM(C1,C3)=0.30 SIM(C2,C3)=0.24

由計(jì)算出的類(lèi)間的相似度值可以看出類(lèi)與類(lèi)間的差異度比較明顯，這也表明了該聚類(lèi)方法的有效性。

Web用戶的行為特征主要由瀏覽路徑和各個(gè)頁(yè)面停留的時(shí)間所體現(xiàn)。每個(gè)用戶瀏覽頁(yè)面的順序以及停留時(shí)間與該用戶的行為習(xí)慣以及偏好有很大的關(guān)系。人們往往會(huì)優(yōu)先瀏覽自己所喜歡的頁(yè)面并且在這個(gè)頁(yè)面上駐留較長(zhǎng)的時(shí)間。而且，一個(gè)用戶的行為習(xí)慣在很大程度上與自己的文化背景，學(xué)歷以及生活環(huán)境密不可分。但是，在傳統(tǒng)的SPSS聚類(lèi)中,以這些變量作為因子進(jìn)行聚類(lèi)所得到的結(jié)果僅僅只能粗糙地反映出用戶間的差別。以學(xué)歷、收入、用戶居住類(lèi)型作為因子變量，表2展示了SPSS和筆者提出的聚類(lèi)方法得到的聚類(lèi)結(jié)果對(duì)比情況，加粗部分表示筆者提出的聚類(lèi)分組結(jié)果和SPSS分組結(jié)果重疊的部分。

表2 聚類(lèi)結(jié)果對(duì)比

根據(jù)表2的結(jié)果分析可以看出，以用戶的瀏覽路徑以及時(shí)間因素作為考慮要素所得到的聚類(lèi)結(jié)果和SPSS 得出的聚類(lèi)結(jié)果有很明顯的區(qū)別，這表明了時(shí)間因素對(duì)用戶進(jìn)行聚類(lèi)的重要影響。

5 結(jié)語(yǔ)

面對(duì)愈來(lái)愈多的用戶群以及日益龐大的數(shù)據(jù)庫(kù)信息，如何快速準(zhǔn)確地找到個(gè)人所需是每個(gè)人所關(guān)注的焦點(diǎn)。為了對(duì)每個(gè)用戶進(jìn)行有效的私人訂制，需要對(duì)這些用戶進(jìn)行歸類(lèi)，然后根據(jù)各個(gè)類(lèi)別的差異進(jìn)行站點(diǎn)拓?fù)浣Y(jié)構(gòu)改善以及網(wǎng)站推薦。筆者從用戶的瀏覽日志入手，同時(shí)考慮了用戶的行為以及各個(gè)行為過(guò)程的的駐留時(shí)間，將所提出的用戶相似度評(píng)價(jià)方法和聚類(lèi)算法得出的結(jié)果與傳統(tǒng)的SPSS聚類(lèi)結(jié)果進(jìn)行了對(duì)比,結(jié)果表明網(wǎng)頁(yè)駐留時(shí)間對(duì)于用戶相似度評(píng)價(jià)有重要意義。

[1]Romero C, Ventura S, Zafra A, et al.Applying Web usage mining for personalizing hyperlinks in Web-based adaptive educational systems[J].Computers & Education,2009, 53(3):828～840.

[2] Himmelspach L, Conrad S.Fuzzy Clustering of Incomplete Data Based on Cluster Dispersion[A].Computational Intelligence for Knowledge-Based Systems Design[C].2010:59～68.

[3] He H, Hai H, Wang R.FCA-Based Web User Profile Mining for Topics of Interest[A].IEEE International Conference on Integration Technology[C].2007:778～782.

[4] Leoni M D, Aalst W M, Dongen B F V.Data-and Resource-Aware Conformance Checking of Business Processes[C].Business Information Systems，2015:35～36.

[5] Bas P, Chassery J M, Macq B.Geometrically invariant watermarking using feature points[J].IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society, 2002, 11(9):1014～28.

[6] Algiriyage N, Jayasena S, Dias G.Web user profiling using hierarchical clustering with improved similarity measure[A].Moratuwa Engineering Research Conference[C].2015:295～300.

[7] Montani S, Leonardi G, Quaglini S, et al.A knowledge-intensive approach to process similarity calculation[J].Expert Systems with Applications, 2015, 42(9):4207～4215.

[8] Hay B, Wets G, Vanhoof K.Web Usage Mining by Means of Multidimensional Sequence Alignment Methods[J].Lecture Notes in Computer Science, 2003, 2703:50～65.

[9] Li Y, Zhu T, Li A, et al.Web behavior and personality: A review[A].Web Society[C].IEEE, 2011:81～87.

[10] Meghabghab G, Kandel A.Search Engines, Link Analysis and User’s Web Behavior[J].Studies in Computational Intelligence, 2010, 99(3)：10～26.

[11] Zhang Y, Xu G.On web communities mining and recommendation[J].Concurrency & Computation Practice & Experience, 2010, 21(5):561～582.

[12] Cárden G G, Tuomisto H, Lehtonen S.Newly discovered diversity in the tropical fern genus Metaxya based on morphology and molecular phylogenetic analyses[J].Kew Bulletin, 2016, 71(1):1～27.

[13] Schefels C.Computing User Importance in Web Communities by Mining Similarity Graphs[J].International Journal on Advances in Internet Technology, 2013, 6(1/2):79～89.

.[14] Joh C H, Arentze T A, Timmermans H J P.A position-sensitive sequence-alignment method illustrated for space- time activity-diary data[J].Environment and Planning A, 2001, 33(2):313～338.

[15] Li L, Xi Y.Research on Clustering Algorithm and Its Parallelization Strategy[A].International Conference on Computational and Information Sciences[C].2011:325～328.