贾小贝,方欢 (安徽理工大学数学与大数据学院,安徽 淮南 232001)
随着网络的迅速发展,囤积在互联网上的数据也越来越多。面对如此海量的信息,如何快速提取所需要的信息是Web用户所关心的问题之一。与此同时,对Web站点的拓扑结构的设计以及功能也提出了更多的要求,比如如何改善网站的结构以方便用户迅速找出所需要的信息,如何为用户提供个性化服务,如何发现潜在的访问群体,为不同的访问群体做出准确的市场定位。因此,一种将传统数据应用于Web领域的技术——Web挖掘应运而生。由于Web信息普遍具有无结构性、缺乏完整性约束和分布松散的特点,因此直接对Web信息进行挖掘具有相当的难度。Web日志具有完美的结构,其包含的信息反映了用户浏览行为特点,为Web挖掘提供了良好的前提条件[1]。 对Web用户聚类基于Web日志进行挖掘,该方法的主要步骤是首先对用户日志进行预处理,然后从中选取所需的用户特征计算行为相似度,最后应用聚类算法得到聚类结果。通过对用户进行聚类最终达到用户与网站间一对一(onetoone)的模式。
过程聚类(clustering)是将数据对象划分成若干组(class)或者类(cluster)的过程[2],划分后的结果使得组内的数据相似度很高,不同组的数据相似度较低。与聚类相关的算法很多,主要包括划分聚类算法、层次聚类算法、网格聚类算法、模型聚类算法以及密度聚类算法[3,4]。作为一种重要的数据挖掘技术,聚类已经在Web日志挖掘中得到广泛的应用。但是与传统数据挖掘相对比,聚类技术在Web日志挖掘中的应用所需要探讨的问题还有很多。如在Web日志挖掘中,关于用户访问路径相似度的评价方法具有良好的实际应用价值,但是到目前为止,有关用户访问路径的相似度计算大部分是基于集合之间的交集运算,如夹角余弦方法、Jaccard相关系数计算法、名义变量、基于非欧氏距离的序列排列方法(SAM)、多维序列排列方法[5~8]。文献[9]提出将雅克比系数和CM(Common road length divide Max road length)系数相结合来计算不同访问序列间的相似度。文献[10]提出首先对页面聚类再进行用户相似度计算的方法。然而,这些研究都对行为序列的时间信息进行了弱化。一般而言,用户的Cookies记录了用户浏览路径,其主要描述特定用户在一段时间内所依浏览的页面以及各个浏览页面驻留时间的一个集合。已有的传统方法或者没有把浏览的页面作为一种序列考虑,或者在处理的过程当中忽略掉了其中所包含的时间信息,这就使得计算出的结果不能真实地反映出用户间的行为相似性程度。文献[11]提出了一种Web的用户聚类方法,将用户的浏览模式看做一个序列,与此同时也考虑了与浏览页面相关的时间信息,但是该方法在计算页面停留时间时,采用的是平均停留时间(即整条路径总的停留时间除以浏览的页面数)。然而,用户往往在感兴趣的页面停留的时间较长,在不感兴趣的页面驻留时间较短,采用平均时间很难发现用户的偏好,因此所得到的聚类就不能真正反映用户间的区别。
下面,笔者结合Web用户浏览行为的主要特征,基于序列对齐[12]的核心思想,提出了一种新的相似度计算方法。这种方法不仅把浏览页面作为一种序列,同时还考虑了页面所包含的时间信息,通过引入相似度矩阵对用户进行行为聚类的分析和研究。最后,通过一些程序采集到的Web用户的日志进行算法验证,并将其结果与传统的SPSS聚类结果进行比较,验证了所提出方法的有效性。
定义1[13](隶属度) 项Ui与类cj的连接强度J(Ui,cj)定义为:
式中,sim(Ui,Uk)表示项Ui与cj类中的Uk项的相似度;m为cj中元素项的个数。
定义2[9](相似度矩阵) 相似度矩阵以对象-对象的结构表示,存储n个对象两两之间的相似性,表示为一个n×n维的矩阵A:
(1)
式中,A是一个对称阵,AT=A;dij量化表示对象i,j之间的相似性。一般而言,dij是一个非负的数值,且dij的值越接近1,则意味着i,j之间越接近;当dij的值越接近0,则表示i,j之间差异越大。
定义3(含时间因素的序列) 二元组N=(T;DI)是一个含时间的序列,其中T是一个活动序列集合,DI是定义在活动集T上的时间函数,即DI:T→R0,其中,R0≥0。
定义4(含时间因素的子序列) 二元组N=(T;DI) 是一个含时间的序列,其中T是一个活动序列集合,如果T1⊆T,则N1=(T1;DI)是N的一个含时间因素的子序列。
定义5[14](不含时间的2个序列的相似度)P,Q是2个字符串序列,这2个字符串之间的相似度可表示为SSAM(P,Q):
(2)
式中,ωd为删除操作的代价;ωi为插入操作的代价;η为重排操作的代价;ωd,ωi,η均是一个人为给定的一个正常数;D为删除操的作的次数;I为插入操作的次数;R为重排操作的次数;|P|,|Q|分别表示每个字符串的长度。
定义6(含时间因素的SAM距离)S1={(t1,T1),(t2,T2),…,(ti,Ti)}(1≤i≤n)和S2={(a1,I1),(a2,I2),…,(aj,Ij)}(1≤j≤n)为2个带有时间戳(时间戳表示的是一个时间序列T={t1,t2,…,tn},其中序列中的每个元素描述了对应活动的持续时间)的序列集,其中ti∈T,aj∈A代表活动集,Ti∈T′,Ij∈I代表时间集。则这2个序列集之间的距离记为dSAM(S1,S2):
(3)
式中,|Ti-Tj|代表一次补偿操作;|Ti-Tj|*|i-j|代表一次重排操作。
定义7(含时间因素的2个序列集间的相似度)S1={(t1,T1),(t2,T2),…,(ti,Ti)}(1≤i≤n)和S2={(a1,I1),(a2,I2),…,(aj,Ij)}(1≤j≤n)为2个带有时间戳的序列集,其中ti∈T,aj∈A代表活动集,Ti∈T′,Ij∈I代表时间集。这2个子序列集之间的相似度记为sim(S1,S2):
(4)
这2个含时间因素的序列间之间的相似度记为SIM(S1,S2):
(5)
其中,w1+w2=1。
定义8(2个子类之间的相似度) 对于2个子类C1,C2,C1中包含的元素个数为|C1|,C2中包含的元素个数为|C2|,则这2个子类C1,C2之间的相似度表示为SIM(C1,C2):
(6)
其中,α+β=1。
定理1[15](相似传递性) 如果P和Q相似,Q和R也相似,那么P和R在一定程度上也具有相似性。
下面给出2个用户间行为相似度评价算法——基于活动时间对齐的相似度评价算法(Similarity Calculation Method Based On Activity Time Alignment,SCMBATA)。
输入:2个用户包含时间的活动序列:
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|) /进行补偿操作/
i++,j++;
else if (ti≠aj)
(|ti-aj|*|i-j|);/重排操作/
i++,j++;
Step3:i=n
/结束/
return SIM(u1,u2)。
下面给出基于Web访问日志的用户聚类算法——基于相似度矩阵的聚类评价算法(Clustering Based On Similarity Matrix Algorithm,CBOSMA)。
输入:相似度矩阵,相似度阈值λ0
输出:Web用户聚类结果集合
步骤:
Step1 输个相似度矩阵,取除对角线外所有元素的平均值作为相似度阈值λ0:
Step2 用三元组∑=(i,j,sim(ui,uj))(其中的元素分别代表行号,列号,相似值;且(i≠j)表示出相似矩阵的前(n-1行)每一行的最大值;
Step3 根据相似度矩阵中当的元素适当计算相似度阈值λ=γλ0(其中γ为调节系数,其中0≤γ≤1),使分类的精度较高;
Step4 将所得到三元组中的相似度值分别与相似度阈值比较,大于阈值的元素所在的行号和列号对应的元素归为一类,小于阈值的所在行号的元素单独归为一类。即如果sim(ui,uj)≥λ,那么class1={useri,userj}。如果sim(ui,uj)<λ,则class2={user2};
Step6 如果类间有交集,则用定义1中的隶属度判别该交集项所属的类;
Step7 由定义8计算类间相似度,得到由类间相似度构成的相似度矩阵,继续上面的步骤直到得到需要的分类结果。
图1 程序截取的日志片段图
通过对所选取的数据集(该数据集来源于data tang.com共享平台)中的1000个用户的日志文件进行清洗、过滤等预处理。接着,把从数据集中抽取的12个用户(其中这12个用户在数据集中的序号为87,89,91,170,177,450,656,665,741,773,776,898)的日志信息作为分析对象:首先计算用户间的相似度,然后进行聚类。样本数据包中的数据文件可分为2部分,其中behavior文件夹中是按日期归档的样本行为日志,demographic.csv是样本的人口属性信息,二者可通过样本ID关联。图1展示了一个典型的日志片段,表1表示了该日志片段中各符号代表的含义。
表1 日志片段中的符号含义
为了对所选取的用户行为进行更加精确地分析,截取每个日志的同一个时间段(比如开机后1h)进行分析。首先,从这些日志文本中提取所需要的路径以及与路径相关的时间信息(以一个进程名的变更作为一个动作的完成,2个动作间隔作为在一个动作上的驻留时间);然后,根据笔者提出的相似性计算方法SCMBATA,计算得到这12个用户相似性矩阵:
由相似性矩阵A,根据聚类算法CBOMSA,将这12个用户分类,分类结果如下:
C1={user1,user3,user4,user5,user8,user9,user12}
C2={user2,user6,user10,}
C3={user7,user11}
根据分类,由式(6)可得类间的相似度(在此规定权重因子以各类中元素占总的元素的比重表示):
SIM(C1,C2)=0.35 SIM(C1,C3)=0.30 SIM(C2,C3)=0.24
由计算出的类间的相似度值可以看出类与类间的差异度比较明显,这也表明了该聚类方法的有效性。
Web用户的行为特征主要由浏览路径和各个页面停留的时间所体现。每个用户浏览页面的顺序以及停留时间与该用户的行为习惯以及偏好有很大的关系。人们往往会优先浏览自己所喜欢的页面并且在这个页面上驻留较长的时间。而且,一个用户的行为习惯在很大程度上与自己的文化背景,学历以及生活环境密不可分。但是,在传统的SPSS聚类中,以这些变量作为因子进行聚类所得到的结果仅仅只能粗糙地反映出用户间的差别。以学历、收入、用户居住类型作为因子变量,表2展示了SPSS和笔者提出的聚类方法得到的聚类结果对比情况,加粗部分表示笔者提出的聚类分组结果和SPSS分组结果重叠的部分。
表2 聚类结果对比
根据表2的结果分析可以看出,以用户的浏览路径以及时间因素作为考虑要素所得到的聚类结果和SPSS 得出的聚类结果有很明显的区别,这表明了时间因素对用户进行聚类的重要影响。
面对愈来愈多的用户群以及日益庞大的数据库信息,如何快速准确地找到个人所需是每个人所关注的焦点。为了对每个用户进行有效的私人订制,需要对这些用户进行归类,然后根据各个类别的差异进行站点拓扑结构改善以及网站推荐。笔者从用户的浏览日志入手,同时考虑了用户的行为以及各个行为过程的的驻留时间,将所提出的用户相似度评价方法和聚类算法得出的结果与传统的SPSS聚类结果进行了对比,结果表明网页驻留时间对于用户相似度评价有重要意义。
[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.