基于ISODATA的用户访问路径聚类算法

基于ISODATA的用户访问路径聚类算法 2006年第23卷第8期微电子学与计算机 1 引言 WWW技术日渐成熟,在信息及服务共享、电子商务等方面得到广泛应用,使得人类的交互信息不可避免地日趋海量化。对于Web服务器日志而言, 某些 Web热点的日志数据正以每天数十兆字节的速度增长。这些数据记录了用户与服务器之间的在线交互信息。对于Web服务器的拥有者来说,从这些数据中分析和发现用户的浏览模式、兴趣爱好等知识,进而改进自身所提供的服务,有十分重要的意义。用户访问模式的数据挖掘,研究如何从用户与 Web服务器的交互...

2006年第23卷第8期微电子学与计算机 1 引言 WWW技术日渐成熟,在信息及服务共享、电子商务等方面得到广泛应用,使得人类的交互信息不可避免地日趋海量化。对于Web服务器日志而言, 某些 Web热点的日志数据正以每天数十兆字节的速度增长。这些数据记录了用户与服务器之间的在线交互信息。对于Web服务器的拥有者来说,从这些数据中分析和发现用户的浏览模式、兴趣爱好等知识,进而改进自身所提供的服务,有十分重要的意义。用户访问模式的数据挖掘,研究如何从用户与 Web服务器的交互数据中发现隐含的规律性。文献 [4]提出在 Web站点中根据路径进行聚类的方法, 在他们的方法中相似度的定义是采用两个访问向量的角度的cos值的办法。访问向量的元素是用户是否访问该页面,采用的聚类方法是 K-means方法。文献[3]提出了K-paths路径聚类方法,考虑到了用户访问事务中页面被访问的先后次序,而这种先后次序体现了用户的访问兴趣。本文定义了新的相似度和聚类中心,采用模糊 ISODATA聚类用户的访问路径,挖掘出了相似用户访问兴趣的聚类,从而调整站点结构。 2 基本概念 Web站点的设计一般遵循一种分类结构,即一个页面的子页面的组织是根据子页面的类别来安排的。从另一个方面来说,这种结构也反映了用户的兴趣。设一个页面中有k个链接,一个用户面对该页面中的这些链接进行访问,如果他首先访问第 l个,那么代表了他对该链接所达的页面的兴趣要大于其它链接所达的页面。用户对Web站点的访问存在某种有序关系,这种有序关系反映的是用户的一种访问兴趣,也就是说群体用户的访问兴趣和他们的访问序列有很强的相关性,先访问的节点具有较大的访问兴趣,因此需要一种聚类方法把这种有序关系挖掘出来[5]。所以进行聚类挖掘的目的,就是从用户的访问日志中得到具有相似用户访问兴趣的聚类,即路径聚类。聚类之前首先要在 Web站点的日志中识别用户访问事务。设L为用户访问日志,其中的一个项 l∈L包括用户的IP地址l.ip,用户的标识符l.uid, 存取页的 URL地址 l.url,以及存取访问的时间 l. time。进行挖掘前,首先进行数据清洗:通过检查 URL的后缀,可以删除那些不相关的项,如gif,jpeg, 收稿日期:2005-08-30 基金项目:国家“863”计划项目(2003AA209021) 基于ISODATA的用户访问路径聚类算法刘晓东刘国荣王颖李辉 (西安交通大学计算机系,陕西西安 710049) 摘要:文章提出了一种基于ISODATA的用户访问路径聚类算法,根据用户的访问兴趣定义了相似性测量手段和聚类中心。在对 Web站点的访问日志进行事务识别后,根据群体用户对 Web站点的访问顺序进行聚类,则每一个聚类集反映出该聚类集中的全体用户具有相似的访问兴趣。关键词:ISODATA,聚类,用户访问模式中图法分类号:TP31 文献标识码:A 文章编号:1000-7180(2006)08-091-03 UserAccessClusteringAlgorithmBasedonISODATA LIUXiao-dong,LIUGuo-rong,WANGYing,LIHui (Dept.ofComputerScienceandEngineering,Xi+anJiaotongUniversity,Xi+an710049China) Abstract:Inthispaper,amethodtoresolveuseraccessclusteringwithISODATAisprovided.Accordingtothere- quirementoftheclustering,thenewmethodisusedtomeasuresimilarityandtogetthecenterofacluster.Afterpro- cessingtheLogintheWebsiteandidentifyingeachuseraccesstransaction,theaccesspathsofalltheuserscanbe clustered.Theneachclustercanthenrepresentthesimilaraccessinterestoftheusersinthecluster. Keywords:ISODATA,Cluster,Useraccesspattern 91 微电子学与计算机 2006年第23卷第8期 jpg,cgi,只保留html文件。数据清洗完之后,就要对 Log进行处理以寻找每一个事务。经过事务识别后, 得到用户访问事务集。每一个用户访问事务相当于用户对站点的一条访问路径,用户的访问事务集就是全体用户在一个时间段内对站点的访问路径集。找到用户访问事务集之后,就可以在其上按路径进行分割聚类。为了描述问题的方便,现给出以下有关概念, 其中设站点有n个页面: (1)兴趣度:用户对一个页面m的兴趣度。 interest(m)=n-j 其中j为用户对该页面的访问顺序。 (2)相似度:两个用户s,t访问路径的相似度。 similar(s,t)=interest(m) 其中 m是指用户 s,t访问路径中第一个不同的页面。 (3)聚类中心:一个聚类c中访问次数最多的页面的集合。 center(c)={m1,m2,⋯mk} 其中m1,m2,⋯..mk为站点的页面,k为用户访问的最长路径。 3 算法描述设共有 n个用户的访问路径, 样本集为{X1, X2,...,Xn},初始的聚类数为k,初始的聚类中心为第一个用户的访问页面C1,C2,...Ck。 (1)规定下列控制参数: K———期望得到的聚类数; N———一个聚类中的最小样本数; S——— 标准偏差参数; C———合并参数; L———每次迭代允许合并的最大聚类对数; I———允许迭代的次数。其中 K,N,I,L,Web管理员可以根据自己的意愿选定,而对于标准偏差参数S和合并参数C,可以这样来确定: S:设定一个类中的访问路径数为 30个,则当 2/3的访问路径在某一访问层上与该聚类的聚类中心不同,计算出这时该聚类该层的标准偏差。 C:合并参数C通过同两两聚类中心的相似度相比来决定两个聚类是否应该合并,可以认为如果两个聚类中心2/3的访问页面都相同,则这两个聚类应该合并。那么,C就是当两个聚类的聚类中心2/ 3的访问页面都相同时,这两个聚类的聚类中心的相似度。 (2)根据下列关系将每个样本X1分到聚类中心为ci的聚类Ci块中: |Xl-Ci|=min 1!l!n |Xl-Ci| (3)若有任何一个Ci满足Ni 公式求标准差 "i= ("i1,"i2,⋯,"in)T; "im= 1 NiX1∈C1 %similar(X1m,Cim)& 式中Xlm是第l个样本的第 m个分量,Xlm应该在Ci中,Cim是第i个聚类的第 m个分量,"im是第 i 个聚类的第m个分量标准差,n为样本维数。 (9)若对任何一个 "im>S,i=1,2,...k,并且δi>δ且 Ni>2(N+1),或 k!K/2,则把 Ci分裂为两个聚类块, 中心对应为C+l和C-i,把原来的Ci取消,且令k=k+1; C+l和C-i的计算公式如下: ① 给定一个k值,使0!k!1; ② 令yi=k*"i; ③ 令C+l=Ci+yi,C-i=Ci+yi; (10)对于所有的聚类中心,计算两两的相似度: δij=similar(Ci,Cj),i=1,2,...,k-1;j=1,2,...k; (11)比较δij和C,把小于C的按大小升序排列; δi1j1<δi2j2<...<δiLjL 其中L是步骤l给出的每次迭代允许的最大聚类对数; (12)从最小的δi,j开始,对于每个δi1j1合并两类 Ci1和Cj1,新的聚类中心为: C1= 1 Ni1+Nj1 Ni1×Ci1+Nj1×Cj1( ) 92 2006年第23卷第8期微电子学与计算机把类数减少1,k=k-1。由于每次迭代,一个聚类中心最多只能被合并一次,所以实际合并的对数总是小于或等于1的。 (13)若是最后一次迭代,则程序终止,否则改变参数,转步骤(1),迭代次数加1。该算法流程如图1所示。 4 实验结果分析按照上述方法对交通大学的Web服务器(www. xjtu.edu.cn)上的日志数据进行预处理后,识别出 2079个用户访问路径,最长的事务访问页面数为 8,平均事务访问长度为 6.67,即用户平均访问 6.67 个页面。随机抽取 12,69,145,251个事务作为初始的聚类中心,算法的执行情况如表1所示。该实验结果说明 K,I的选值对结果有直接影响,K最终的值和初始值不会偏差很大,中心的平均长度和初始值有很大的关系。该算法有较高的效率。 5 结束语本文提出的基于 ISODATA的用户访问路径聚类算法,聚类结果为大多用户感兴趣的访问路径, 根据此结果,WEB管理人员可以调整站点的结构。参考文献 [1] 苏新宁,杨建林,邓三鸿,周军.数据挖掘理论与技术.北京:科学技术文献出版社,2003 [2][加]JiaweiHan,MichelineKamber,范明、孟小峰译.数据挖掘概念与技术.北京:机械工业出版社,2003 [3] 王实,高文,李锦涛,谢辉.路径聚类:在 Web站点中的知识发现.计算机研究与发展,2001(4) [4]MobasherB,CooleyRetal.CreatingadaptiveWebsitesthrough usagebasedclusteringofURLs.In:Procofthe1999IEEE KnowledgeandDataEngineeringExchangeWorkshop (KDEX’99).NewYork:IEEEPress,1999:32～37 [5] 王颖,张丽霞,刘晓东,王伟峰.关联规则挖掘技术在 Web 预取中的应用.微电子学与计算机,2005,22(4) [6] 刘晓东,曹云飞,胡昭,王伟峰.基于动态组件的组合组件. 微电子学与计算机,2005,22(4) 刘晓东男,(1954-),副教授。研究方向为人工智能与虚拟现实技术的研究与应用。刘国荣男,(1957-),副教授。研究方向为人工智能与数理逻辑的研究与应用。王颖女,(1982-),硕士研究生。研究方向为人工智能和虚拟现实技术应用。李辉男,(1971-),硕士研究生。研究方向为虚拟现实技术应用。表1 算法执行情况 K最终值 I迭代次数 K最终值中心的平均长度 12 4 10 23.45 69 5 65 18.77 145 5 141 19.65 251 4 229 22.54 93

                    本文档为【基于ISODATA的用户访问路径聚类算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

基于ISODATA的用户访问路径聚类算法

你可能还喜欢