使用挖掘介绍及趋势.pptx

2024/4/15 周一Web Usage Mining1提纲提纲1.简介1.1 WUM的定义和应用1.2 WUM基本的过程1.3 原型系统和商用系统2.趋势2024/4/15 周一Web Usage Mining2Web Mining 的分类12：1.Content Mining2.Structure Mining3.Usage MiningWeb Mining 分类分类2024/4/15 周一Web Usage Mining31.1.1 定义定义(Jaideep Srivastava1)“the process of applying data mining techniques to the discovery of usage patterns from Web data”2024/4/15 周一Web Usage Mining41.1.2功能功能System Improvement1).Site Improvement2).Web Caching and Network Transmission(E.Cohen5)2024/4/15 周一Web Usage Mining51.1.2功能功能1).Site Improvement根据实际用户的浏览情况，调整网站的网页的连接结构和内容，更好的服务用户A=B=C=DA=D极端：Adaptive web sites(Mike Perkowitz78)2024/4/15 周一Web Usage Mining61.1.2功能功能2).Caching&Network Transmission(E.Cohen5)例如：从proxy 的访问信息中可以分析用户的访问模式，从而可以预测用户的Page访问，提高Web Caching的性能A=B=CA=B=DA=BCached:C、D2024/4/15 周一Web Usage Mining71.1.2功能功能*与传统的销售途径不同的是与传统的销售途径不同的是：网上零售系统可捕捉到大量的采购过程的细节，提供了更加深入分析的可能2024/4/15 周一Web Usage Mining81.1.2功能功能Personalization定义：定义：根据发现的用户喜好，动态地为用户定制观看的内容或提供浏览建议。直接实现形式直接实现形式：Recommender系统(10J.Ben Schafer)。作用：作用：1)方便用户查询和浏览2)增强广告的作用3)促进网上销售4)提高用户忠诚度2024/4/15 周一Web Usage Mining91.2 基本的过程基本的过程*1).Data Gathering2).Preprocessing3).Pattern discovery4).Patterns analysis2024/4/15 周一Web Usage Mining101.2 基本的过程基本的过程Site Files,Raw Usage Data,User ProfileSite Content&Structure,Server/Session/Episode DataUsage Statistics,User Clusters,Association Rules,Sequential PatternsKnowledge1).Data Gathering2).Preprocessing4).Patterns analysis3).Pattern discovery2024/4/15 周一Web Usage Mining111.2.1 Data Gathering可以利用的Web Data包括:1).Content:页面的实际内容2).Structure:包括intra-structure和 inter-structure3).Usage:例如：Click Stream4).User Profile:例如：registration data 和 customer profiles5.Business Data？2024/4/15 周一Web Usage Mining121.2.1 Data Gathering数据来源数据来源:1)Server Level Collection2)Client Level Collection3)Proxy Level Collection2024/4/15 周一Web Usage Mining131.2.1 Data GatheringServer Level Collection:1)Web Log File2)Packet Sniffing 技术 缺点是扩展性差（加密通道和用户跟踪）3)Web Page Content&structure4)Application Server2024/4/15 周一Web Usage Mining141.2.1 Data GatheringClient Level Collection:优点是可以比较全面和准确收集到用户数据Applet&Script 缺点:不支持代理，功能会被用户关闭。Modified browser 优点是全面和准确收集到用户数据，缺点是需要吸引或强制用户使用2024/4/15 周一Web Usage Mining151.2.1 Data GatheringProxy Level Collection:这种数据收集方式适合有大量静态页面的网站2024/4/15 周一Web Usage Mining161.2.2 Preprocessing1).Content&Structure2).Usage Data2024/4/15 周一Web Usage Mining171.2.2 PreprocessingContent&Structure:解决两个问题第一、page的独特性的表示方法？第二、page 的内容和结构的量化形式（quantifiable form）2024/4/15 周一Web Usage Mining181.2.2 Preprocessingstructure举例：ABC Site MapEindex1AB1CFNavigationMixedMediaPage Type2024/4/15 周一Web Usage Mining191.2.2 PreprocessingABC Site Map的结构可表示为：M=F1=index,(frame,1,left|frame,A,main)F2=1,(get,A,main),(get,C,main)F3=A,(get,B,top)F4=C,(get,E,top),(get,F,top)F5=BF6=EF7=F2024/4/15 周一Web Usage Mining201.2.2 PreprocessingIndex=1-A=1-C=EIndex=1-A=BMap的结构表示了用户可能的click访问的路径2024/4/15 周一Web Usage Mining211.2.2 PreprocessingContent Classification:1)Usage Type2)Content Features*具体种类的划分跟应用的环境相关2024/4/15 周一Web Usage Mining221.2.2 PreprocessingUsage Type 1)Head Page 例如：Index2)Media Page 例如：B,E,F3)Navigation Page 例如：1,C4)Mixed Page 例如：A2024/4/15 周一Web Usage Mining231.2.2 PreprocessingContent Features(22 Soumen Chakrabarti):1。可以使用vector space model来表示page的内容：把page的示成一个在此高维空间中的一个向量page出现的term作为向量的维,维对应的值是通过某种方式计算出来的权重(例如：TFIDF),它反映了term在此page区别其他page的时候的重要程度。2。Clustering&Classification2024/4/15 周一Web Usage Mining241.2.2 PreprocessingUsage Data:数据的抽象41.User2.Page View(Click)用户在某个时刻看到的浏览器中的内容3.Click Stream 一组连续的page view 请求4.User Session(transaction)用户的阶段性的click stream,可以跨多个服务器5.Server Session 用户的,在一个服务器上的阶段性的click stream6.Episode 用户session中的一段有意义的click stream2024/4/15 周一Web Usage Mining251.2.2 PreprocessingUsage Data:数据的抽象4Raw DataPage ViewClick StreamUser SessionServer SessionEpisodes2024/4/15 周一Web Usage Mining261.2.2 PreprocessingUsage Preprocessing的流程1.数据清理2.识别User/Session 3.识别Page View4.识别Episode2024/4/15 周一Web Usage Mining271.Data cleaning:*把log条目分割成对应的数据项目*剔除图片或其它非page类的log条目*剔除spider/agent的访问条目*规格化URI*提取POST数据项1.2.2 Preprocessing2024/4/15 周一Web Usage Mining281.2.2 Preprocessing清理后的Sample LogIP AddressTime/DateMethod/URIReferrerAgent202.120.224.4 15:30:01/2-Jan-01 GET Index.htmhttp:/ok.edu/link.htmMozilla/4.0(IE5.0W98)202.120.224.4 15:30:01/2-Jan-01 GET 1.htmhttp:/ex.edu/index.htm Mozilla/4.0(IE5.0W98)202.120.224.4 15:30:01/2-Jan-01 GET A.htmhttp:/ex.edu/index.htm Mozilla/4.0(IE5.0W98)202.120.224.4 15:37:09/2-Jan-01 GET E.htmhttp:/ex.edu/C.htmMozilla/4.0(IE5.0W98)202.120.224.4 15:33:04/2-Jan-01 GET Index.htmhttp:/ok.edu/res.phpMozilla/4.0(IE4.0NT)202.120.224.4 15:33:04/2-Jan-01 GET 1.htmhttp:/ex.edu/index.htm Mozilla/4.0(IE4.0NT)202.120.224.4 15:33:04/2-Jan-01 GET A.htmhttp:/ex.edu/index.htm Mozilla/4.0(IE4.0NT)202.120.224.4 15:35:11/2-Jan-01 GET B.htmhttp:/ex.edu/A.htmMozilla/4.0(IE4.0NT)202.120.224.4 15:35:11/2-Jan-01 GET C.htmhttp:/ok.edu/A.htmMozilla/4.0(IE5.0W98)2024/4/15 周一Web Usage Mining292.User and Session identification:1.2.2 Preprocessing1.IP Address&Agent2.Embedded Session ID3.Registration(User Profile)4.Cookie5.Software Agent(Applet&Scrtipt)6.Modified Browser2024/4/15 周一Web Usage Mining30在只有IP/Agent的情况下，我们假设User 和 Session 是等同*的:1.2.2 Preprocessing15:33:04/2-Jan-01 GET Index.htmhttp:/ok.edu/res.php15:33:04/2-Jan-01 GET 1.htmhttp:/ex.edu/index.htm15:33:04/2-Jan-01 GET A.htmhttp:/ex.edu/index.htm15:35:11/2-Jan-01 GET B.htmhttp:/ex.edu/A.htm15:30:01/2-Jan-01 GET Index.htmhttp:/ok.edu/link.htm15:30:01/2-Jan-01 GET 1.htmhttp:/ex.edu/index.htm15:30:01/2-Jan-01 GET A.htmhttp:/ex.edu/index.htm15:37:09/2-Jan-01 GET E.htmhttp:/ex.edu/C.htm15:35:11/2-Jan-01 GET C.htmhttp:/ok.edu/A.htmMozilla/4.0(IE5.0W98)202.120.224.4User1:202.120.224.4Mozilla/4.0(IE4.0NT)User2:2024/4/15 周一Web Usage Mining313.Page View Identification:1.2.2 Preprocessing1-Ahttp:/ok.edu/res.phpBA.htm1-Ahttp:/ok.edu/link.htmEC.htm1-CA.htmMozilla/4.0(IE5.0W98)202.120.224.4User1:202.120.224.4Mozilla/4.0(IE4.0NT)User2:2024/4/15 周一Web Usage Mining32Path Completion解决由于Cache带来的问题路径不全的问题1.2.2 Preprocessingtime1-A1-C1-E1-C1-FSession_1Session_22024/4/15 周一Web Usage Mining334.Episode Identification:1.2.2 Preprocessing定义:meaningful subset of user/server sessionAuxiliary-Media Episodes:timeA A MMAA A MAEpisode1Episode2Episode32024/4/15 周一Web Usage Mining34Auxiliary-Media Episodes:1.2.2 Preprocessing可以使用的方法包括：1）Page type 2）Reference length3）Maximal Forward Reference2024/4/15 周一Web Usage Mining351).Page type Episode:根据page view的类型来确定1.2.2 PreprocessingtimeA A MMAA A MAEpisode1Episode2Episode3Session X缺点是，必须要求每个page view有固定的用途。2024/4/15 周一Web Usage Mining362).Reference Length Episode:page view的类型是根据用户在此处停留的时间来确定。停留时间相对长的，就认为是Media Page,停留时间短的则是一个Auxiliary Page1.2.2 Preprocessing2024/4/15 周一Web Usage Mining372).Maximal Forward Reference Episode23,chen它的假设是：一个episode是访问某个Media page的一个最大深度的page view 引用路径，即从用户session的第一个page view开始，一直向前访问，直到有一个backward page view 出现1.2.2 PreprocessingIndex 1-A 1-C E 1-C BTimeEpisode1Episode22024/4/15 周一Web Usage Mining381.2.3 Pattern Discovery其中有：1)Statistical Analysis2)Frequent Itemsets and Association Rules3)Clustering&Classification4)Sequential Patterns5)Dependency Modeling2024/4/15 周一Web Usage Mining391.2.3 Pattern Discovery1)Statistical Analysis主要用于改进系统的Performance,design等包括：1)most frequently accessed pages2)average view time of a page 3)average length of a path through a site2024/4/15 周一Web Usage Mining401.2.3 Pattern Discovery2)Frequent Item-sets and Association Rules可以寻找出经常频繁访问的page组，可用于修改Web Site的设计或提前缓冲页面，改进系统的性能。2024/4/15 周一Web Usage Mining411.2.3 Pattern Discovery3)Clustering&Classification包括两方面的应用：*user 用于Market segmentation(市场分割)和个人内容定制*page(content)后者主要用于IR和Surf Assistance2024/4/15 周一Web Usage Mining421.2.3 Pattern Discovery5)Sequential Patterns可用于用户的 visit pattern.包括：1.trend analysis2.change point detection3.similarity Analysis.2024/4/15 周一Web Usage Mining431.2.3 Pattern Discovery6)Dependency Modeling不仅提供了理论化分析用户行为的框架，同时也可以用来，提高网上产品销量，提高用户的访问提供方便可以使用的方法有：1）Markov Model 2）Bayesian Brief Network2024/4/15 周一Web Usage Mining441.2.4 Pattern Analysis目的是根据实际应用，通过用户的选择和观察，把发现的rules,patterns和statistics转换为知识Knowledge。1）Information filtering(例如：SQL),2）Visualization3)OLAP4)Knowledge Query2024/4/15 周一Web Usage Mining451.3 原型系统和商用系统原型系统和商用系统2024/4/15 周一Web Usage Mining46IBM:SpeedTracer 17从日志文件中重建user traversal path,然后识别出user session;在此基础上，利用数据挖掘算法发现 most common traversal path 和 frequently visited page group;系统提供三种统计类型的报告：1)user-based 例如：频繁访问本站的前N名的用户地址2)path-based 例如：被频繁访问的前N名的路径3)group-based 例如：被频繁访问的前N名的page group2024/4/15 周一Web Usage Mining47WebLogMiner 14,151)经过清理的log数据以DataCube的形式存储在Database中2)提供OLAP3)提供包括序列模式和关联规则在内的多种数据挖掘的方法Simon Fraser University 2024/4/15 周一Web Usage Mining48Web Utilization Miner1)完整的log preparation,querying 和 visualization2)主要提供sequence pattern的发现3)提供MINT查询语言3)提供树结构的sequence pattern显示方式http:/wum.wiwi.hu-berlin.de/德国柏林Humboldt大学商学院2024/4/15 周一Web Usage Mining492.Trends2024/4/15 周一Web Usage Mining50PAKDD 20011.Server Log提供的可用信息太少2.动态页面的大量使用使得分析log更为困难3.Session的分析一直是个难点194.其他一些数据没有记录：例如：Search keywords5.Crawlers的过滤6.巨大的数据量及其自动转换7.Market Level insightRon Kohavi:Mining E-Commerce Data:The Good,the Bad,and the Ugly.*WUM在在 E-Commerce 领域内的应用还刚起步领域内的应用还刚起步 2024/4/15 周一Web Usage Mining51WEBKDD2000主题：Web Mining for E-Commerce-Challenges and Opportunities2024/4/15 周一Web Usage Mining5216 提出了Recommender系统的在E-Commerce领域内的发展机遇和挑战：1）结合多种用户数据的结合多种用户数据的,建立建立subtle recommender 系统系统*Demographic Information 例如：register data*Purchase Data*Explict Rating 例如：用户对产品的评价*Ownership Data2)Recommender 系统和市场分析决策结合系统和市场分析决策结合(*)3）用户数据的共享用户数据的共享4)道德问题道德问题5）扩展性扩展性*Recommender/Personalization系统可能的切入点可能的切入点2024/4/15 周一Web Usage Mining53WUM技术与现有的E-Commerce系统集成可能的切入点可能的切入点2024/4/15 周一Web Usage Mining54改造和构造新的算法，把原有旧的数据源（例如Web Log）和新的数据(Business Data)结合起来，用以发现新的Usage Pattern可能的切入点可能的切入点2024/4/15 周一Web Usage Mining55在文2021中把把用户的Tranversal Pattern和purchasing Pattern结合起来考虑，并构建了一个算法用以挖掘用户的large transaction pattern(使用规则来表示).可能的切入点可能的切入点2024/4/15 周一Web Usage Mining56可能的切入点可能的切入点:提供完整的应用功能提供完整的应用功能1.数据收集，清理和转换2.数据存储3.数据挖掘4.个人定制5.市场分析和决策2024/4/15 周一Web Usage M可能的切入点可能的切入点:提供完整的应用功能提供完整的应用功能2024/4/15 周一Web Usage Mining58Conclusion1Jaideep Srivastava,Robert Cooley,Mukund Deshpande,Pang-Ning Tan,Web Usage Mining:Discovery and Applications of Usage Patterns from Web Data(2000).SIGKDD Explorations,Vol.1,Issue 2,2000.11Robert Cooley,Bamshad Mobasher,and Jaideep Srivastava,Data Preparation for Mining World Wide Web Browsing Patterns(1999),Knowledge and Information Systems V1(1).2024/4/15 周一Web Usage Mining591Jaideep Srivastava,Robert Cooley,Mukund Deshpande,Pang-Ning Tan,Web Usage Mining:Discovery and Applications of Usage Patterns from Web Data(2000).SIGKDD Explorations,Vol.1,Issue 2,2000.2Robert Cooley,Bamshad Mobasher,and Jaideep Srivastava,Web Mining:Information and Pattern Discovery on the World Wide Web(A Survey Paper)(1997),in Proceedings of the 9th IEEE International Conference on Tools with Artificial Intelligence(ICTAI97),November 1997.3WWW.W3C.ORG,W3C Working Draft WD-logfile-960323 4WWW.W3C.ORG,Web Characterization Terminology&Definitions Sheet,W3C Working Draft 24-May-19995E.Cohen,B.Krishnamurthy,and J.Rexford.Improving end-to-end performance of the web using server volumes and proxy filters.In Proc.ACM SIGCOMM,pages 241-253,1998.6T.Fawcett and F.Provost.Activity monitoring:Noticing interesting changes in behavior.In Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,pages 53-62,San Diego,CA,1999.ACM.7Mike Perkowitz,Oren Etzioni:Towards adaptive Web sites:Conceptual framework and case study.Artificial Intelligence 118(1-2):245-275(2000)8Mike Perkowitz,Oren Etzioni:Adaptive Web Sites:an AI Challenge.IJCAI(1)1997:16-239 Alex Buchner and Maurice D Mulvenna.Discovering internet marketing intelligence through online analytical web usage mining.SIGMOD Record,27(4):54-61,1998.10J.Ben Schafer,Joseph A.Konstan,John Riedi,Recommender systems in e-commerce,Proceedings of the First ACM Conference on Electronic Commerce(EC-99),November 3-5,1999,Denver,CO,USA.ACM,1999 158-16611Robert Cooley,Bamshad Mobasher,and Jaideep Srivastava,Data Preparation for Mining World Wide Web Browsing Patterns(1999),Knowledge and Information Systems V1(1).2024/4/15 周一Web Usage Mining6012J.Han,O.R.Za?ane,and Y.Fu,Resource and Knowledge Discovery in Global Information Systems:A Scalable Multiple Layered Database Approach,Proc.of a Forum on Research and Technology Advances in Digital Libraries(ADL95),McLean,Virginia,May 1995.13O.Zaiane and J.Han,WebML:Querying the World-Wide Web for Resources and Knowledge,Proc.(CIKM98)Intl Workshop on Web Information and Data Management(WIDM98),Bethesda,Maryland,Nov.1998,pp.9-12.14J.Pei,J.Han,B.Mortazavi-Asl,and H.Zhu Mining Access Patterns Efficiently from Web Logs,Proc.2000 Pacific-Asia Conf.on Knowledge Discovery and Data Mining(PAKDD00),Kyoto,Japan,April 2000.15O.R.Zaiane,M.Xin,J.Han,Discovering Web Access Patterns and Trends by Applying OLAP and Data Mining Technology on Web Logs,Proc.Advances in Digital Libraries Conf.(ADL98),Santa Barbara,CA,April 1998,pp.19-29.16J.Ben Schafer,Joseph A.Konstan,John Riedi,Recommender systems in e-commerce,Proceedings of the First ACM Conference on Electronic Commerce(EC-99),November 3-5,1999,Denver,CO,USA.ACM,1999 158-16617Kun-lung Wu,Philip S Yu,and Allen Ballman.Speedtracer:A web usage mining and analysis tool.IBM Systems Journal,37(1),1998.18 Bamshad Mobasher,R.Cooley,J.Srivastava,Automatic Personalization Based On Web Usage Mining,Communication of ACM,August,2000(Volume 43,Issue 819 Measuring the Accuracy of Sessionizers for Web Usage Analysis(with B.Berent,M.Spiliopoulou,and J.Wiltshire),in Proceedings of the Web Mining Workshop at the First SIAM International Conference on Data Mining,April 2001,Chicago20C.-H Yun and M.-S.Chen,Mining Web Transaction Patterns in an Electronic Commerce Environment,Proc.of the 4th Pacific-Asia Conf.on Knowledge Discovery and Data Mining,pp.216-219,April 18-20,200021C.-H.Yun and M.-S.Chen,Using Pattern-Join and Purchase-Combination for Mining Web Transaction Patterns in an Electronic Commerce Environment,Proc.of the 24th annual Internl Computer Software and Application Conference(COMPSAC-2000),pp.99-104,October 25-27,2000.22Soumen Chakrabarti,Data mining for hypertext:A tutorial survey.ACM SIGKDD Explorations,1(2),pages 1-11,200023M.-S.Chen,J.S.Park and P.S.Yu,Efficient Data Mining for Path Traversal Patterns in Distributed Systems,Proc.of the 16th IEEE Internl Conf.on Distributed Computing Systems,May 27-30,1996,pp.385-392.24 Suhail Ansari,Ron Kohavi,Llew Mason,and Zijian Zheng,Integrating E-Commerce and Data Mining:Architecture and Challenges,WebKDD2000