web文本挖掘PPT课件

2020/6/11,.,1,第九章WEB挖掘,2020/6/11,.,2,WEB挖掘,万维网是目前一个巨大的、分布广泛的全球性信息服务中心，它涉及新闻、广告、消费信息、金融管理、教育、政府、电子商务和许多其它信息服务。WEB还包了丰富和动态的超链接信息，以及WEB页面的访问和使用信息，这为数据挖掘提供了丰富的资源。WEB对有效的资源和知识发现还是具有极大的挑战性。,2020/6/11,.,3,TheWebHasManyOtherRichStructures,2020/6/11,.,4,WEB对有效的资源和知识发现具有挑战性,对有效的数据仓库和数据挖掘而言，WEB似乎太庞大了。WEB的数据量目前以百兆兆字节计算，而且仍然在迅速地增长。许多机构和社团都把各自大量的可访问信息置于网上。这使得几乎不可能去构造一个数据仓库来复制、存储或集成WEB上的所有数据。,2020/6/11,.,5,WEB对有效的资源和知识发现具有挑战性,WEB页面的复杂性远比任何传统的文本文档复杂得多Web页面缺乏同一的结构，它包含了远比任何一组书籍或其它文本文档多得多的风格和内容。Web可以看作一个巨大的数字图书馆；然而，这一图书馆中的大量文档并不根据任何有关排列次序加以组织。他没有分类索引，更没有按标题、作者、封面页等索引。对在这样的图书馆中搜索希望得到的信息是极具挑战性的。,2020/6/11,.,6,WEB对有效的资源和知识发现具有挑战性,Web是一个动态性极强的信息源。Web不仅以极快的速度增长，而且其信息还在不断地发生着更新。新闻、股票市场、公司广告和web服务中心都在不断更新着各自的页面。链接信息和访问记录也在频繁地更新之中。Web面对的是一个广泛的行行色色的用户群体。目前因特网上连接有约五千万台工作站，其用户群仍在不断地扩展中。各个用户可以有不同的背景、兴趣和使用目的。大部分用户并不了解信息网络结构，不清楚搜索的高昂代价，极容易在“黑暗”的网络中迷失方向，也极容易在“跳跃式”访问中翻乱不已和在等待一段信息中失去耐心。,2020/6/11,.,7,WEB对有效的资源和知识发现具有挑战性,Web上的信息只有很小的一部分是相关的或有用的。据说99%的web信息对99%的用户是无用的。虽然这看起来不是很明显，但一个人只是关心web上的很小很小一部分信息确是事实，web所包含的其余信息对用户来说是不感兴趣的，而且会淹没所希望得到的搜索结果。,2020/6/11,.,8,FindingInformationOntheWeb,两种获得web信息的方法:Browsing:Fromastartingpoint,navigatethroughhyperlinkstofinddesireddocuments.Yahooscategoryhierarchyfacilitatesbrowsing.Searching:Submitaquerytoasearchenginetofinddesireddocuments.Manywell-knownsearchenginesontheWeb:Google,MSN,Yahoo,AltaVista,Fast,Lycos,etc.SearchingisthesecondmostpopularactivitiesontheWebbehindemail.,2020/6/11,.,9,浏览和查找方式的比较,Categoryhierarchyisbuiltmostlymanuallywhilesearchenginedatabasescanbecreatedautomatically.Searchenginescanindexmuchmoredocumentsthanacategoryhierarchy.Browsingismoreaccurateandmorefocused(lessjunkwillbeencountered)thansearching.,2020/6/11,.,10,WEB挖掘,尽管传统的搜索引擎和新一代的搜索引擎Google等在一定程度上满足了人们信息检索的需要，但搜索引擎的查全率、查准率都不尽如人意。于是，人们想到了数据挖掘技术，将传统的数据挖掘同web结合起来进行web挖掘，从web文档和web活动中抽取用户感性趣的潜在的有用模式和隐藏信息，弥补了搜索引擎的不足。,2020/6/11,.,11,WEB挖掘及相关概念,Web挖掘时针对网络信息资源进行的，其中涉及一些同传统的数据挖掘不同的知识和概念。比如IP地址、网页的HIML语言、WEB页面的URL地址和WEB服务器的日志记录等。,2020/6/11,.,12,WEB挖掘及相关概念,WEB挖掘中用到的术语和概念www组织在1999年制定了一套规范的web范围相关术语。IP地址/域名。URL统一资源定位器超级链接hyperlink超文本标记语言htmlXml可扩展标记语言代理服务器proxyserverWeb服务日志搜索引擎网络蜘蛛,2020/6/11,.,13,搜索引擎为什么查询很重要？,信息就在你的指尖Fundamentalrs(q,di)betherankingscoreofdiwithrespecttoq;link(j,i)=1ifdjpointstodi,=0otherwise.rs(q,di)=sim(q,di)+link(j,i)sim(q,dj)=0.2isaconstantparameter.,2020/6/11,.,55,链接分析-PAGERANK,PageRankcitationranking(Page,Brin,etal.ThePageRankCitationRanking:BringOrdertotheWeb.Technicalreport,StanfordU.98).WebcanbeviewedasahugedirectedgraphG(V,E),whereVisthesetofwebpages(vertices)andEisthesetofhyperlinks(directededges).Eachpagemayhaveanumberofoutgoingedges(forwardlinks)andanumberofincominglinks(backlinks).Eachbacklinkofapagerepresentsacitationtothepage.PageRankisameasureofglobalwebpageimportancebasedonthebacklinksofwebpages.,2020/6/11,.,56,链接分析-PAGERANK,PageRankisbasedonthefollowingbasicideas:Ifapageislinkedtobymanypages,thenthepageislikelytobeimportant.Ifapageislinkedtobyimportantpages,thenthepageislikelytobeimportanteventhoughtherearenttoomanypageslinkingtoit.Theimportanceofapageisdividedevenlyandpropagatedtothepagespointedtobyit.,10,5,5,2020/6/11,.,57,链接分析-PAGERANK,PageRankDefinitionLetubeawebpage,Fubethesetofpagesupointsto,Bubethesetofpagesthatpointtou,Nu=|Fu|bethenumberofpagesinFu.Therank(importance)ofapageucanbedefinedby:R(u)=(R(v)/Nv)vBu,2020/6/11,.,58,链接分析-PAGERANK,PageRankisdefinedrecursivelyandcanbecomputediteratively.Initiateallpagerankstobe1/N,NisthenumberofverticesintheWebgraph.Ini-thiteration,therankofapageiscomputedusingtheranksofitsparentpagesin(i-1)thiteration.Repeatuntilallranksconverge.LetRi(u)betherankofpageuinithiterationandR0(u)betheinitialrankofu.Ri(u)=(Ri-1(v)/Nv)vBu,2020/6/11,.,59,链接分析-PAGERANK,rI1=0*ri-11+1/2*ri-12+0*ri-13+0*ri-14rI2=0*ri-11+1/2*ri-12+0*ri-13+0*ri-14,001,RI=,ri1ri2ri3ri4,ri-11ri-12ri-13ri-14,=,2020/6/11,.,60,链接分析-PAGERANK,MatrixrepresentationLetMbeanNNmatrixandmuvbetheentryattheu-throwandv-thcolumn.muv=1/Nvifpagevhasalinktopageumuv=0ifthereisnolinkfromvtouLetRibetheN1rankvectorfori-thiterationandR0betheinitialrankvector.ThenRi=MRi-1,2020/6/11,.,61,链接分析-PAGERANK,Example:ConsiderthefollowingpartialWebgraph:Ri=M=Ri+1=,A,B,C,D,001,ABCD,ABCD,ri1ri2ri3ri4,ri-11ri-12ri-13ri-14,2020/6/11,.,62,链接分析-PAGERANK,Iftheranksconverge,i.e.,thereisarankvectorRsuchthatR=MR,RistheeigenvectorofmatrixMwitheigenvaluebeing1.ConvergenceisguaranteedonlyifMisaperiodic(theWebgraphisnotabigcycle).ThisispracticallyguaranteedforWeb.Misirreducible(theWebgraphisstronglyconnected).Thisisusuallynottrue.,2020/6/11,.,63,链接分析-PAGERANK,Ranksink:Apageoragroupofpagesisaranksinkiftheycanreceiverankpropagationfromitsparentsbutcannotpropagateranktootherpages.Ranksinkcausesthelossoftotalranks.Example:,A,B,C,D,(C,D)isaranksink,2020/6/11,.,64,链接分析-PAGERANK,Asolutiontothenon-irreducibilityandranksinkproblem.Conceptuallyaddalinkfromeachpagevtoeverypage(includeself).Ifvhasnoforwardlinksoriginally,makeallentriesinthecorrespondingcolumninMbe1/N.Ifvhasforwardlinksoriginally,replace1/Nvinthecorrespondingcolumnbyc1/Nvandthenadd(1-c)1/Ntoallentries,0c0=0,otherwisewhere0w1.Bothsim(q,d)andR(d)needtobenormalizedtobetween0,1.,2020/6/11,.,70,链接分析-PAGERANK,PageRank算法实质上是一种通过离线对整个互联网结构图进行幂迭代的方法.PageRank所计算出的价值度的值实际上就是互联网结构图经过修改后的相邻矩阵的特征值.对这些值的计算有非常有效的方法(事实上,仅需要若干次的迭代计算即可以得到),因此能够很好地应用到整个互联网规模的实践中.这种方法的另一个主要优点是所有的处理过程都是离线进行的,因此不会为在线的查询过程付出额外的代价.,2020/6/11,.,71,链接分析-PAGERANK,但是,PageRank算法也同样存在一个显著的问题,即价值度的计算是不是针对查询的.对于某个特定主题的查询,在返回结果中一些与主题无关的“强壮”网页将会排在较前的位置.比如,PageRank会把网页网页排在,2020/6/11,.,72,链接分析-PAGERANK,PageRankdefinestheglobalimportanceofwebpagesbuttheimportanceisdomain/topicindependent.Weoftenneedtofindimportant/authoritativepageswhicharerelevanttoagivenquery.Whatareimportantwebbrowserpages?Whichpagesareimportantgamepages?Kleinberg(Kleinberg98)proposedtouseauthorityandhubscorestomeasuretheimportanceofawebpagewithrespecttoagivenquery.,2020/6/11,.,73,链接分析-HITS,Thebasicidea:Apageisagoodauthoritativepagewithrespecttoagivenqueryifitisreferenced(i.e.,pointedto)bymany(goodhub)pagesthatarerelatedtothequery.Apageisagoodhubpagewithrespecttoagivenqueryifitpointstomanygoodauthoritativepageswithrespecttothequery.Goodauthoritativepages(authorities)andgoodhubpages(hubs)reinforceeachother.,2020/6/11,.,74,链接分析-HITS,Authoritiesandhubsrelatedtothesamequerytendtoformabipartitesubgraphofthewebgraph.Awebpagecanbeagoodauthorityandagoodhub.,hubs,authorities,2020/6/11,.,75,链接分析-HITS,Mainstepsofthealgorithmforfindinggoodauthoritiesandhubsrelatedtoaqueryq.Submitqtoaregularsimilarity-basedsearchengine.LetSbethesetoftopnpagesreturnedbythesearchengine.(Siscalledtherootsetandnisofteninthelowhundreds).,2020/6/11,.,76,链接分析-HITS,Mainstepsofthealgorithmforfindinggoodauthoritiesandhubsrelatedtoaqueryq.ExpandSintoalargesetT(baseset):AddpagesthatarepointedtobyanypageinS.AddpagesthatpointtoanypageinS.Ifapagehastoomanyparentpages,onlythefirstkparentpageswillbeusedforsomek.,2020/6/11,.,77,链接分析-HITS,3.FindthesubgraphSGofthewebgraphthatisinducedbyT.,S,T,2020/6/11,.,78,链接分析-HITS,ComputetheauthorityscoreandhubscoreofeachwebpageinTbasedonthesubgraphSG(V,E).Givenapagep,leta(p)betheauthorityscoreofph(p)bethehubscoreofp(p,q)beadirectededgeinEfromptoq.Twobasicoperations:OperationI:Updateeacha(p)asthesumofallthehubscoresofwebpagesthatpointtop.OperationO:Updateeachh(p)asthesumofalltheauthorityscoresofwebpagespointedtobyp.,2020/6/11,.,79,链接分析-HITS,OperationI:foreachpagep:a(p)=h(q)q:(q,p)EOperationO:foreachpagep:h(p)=a(q)q:(p,q)E,q1,q2,q3,p,q3,q2,q1,p,2020/6/11,.,80,链接分析-HITS,MatrixrepresentationofoperationsIandO.LetAbetheadjacencymatrixofSG:entry(p,q)is1ifphasalinktoq,elsetheentryis0.LetATbethetransposeofA.Lethibethevectorofhubscoresafteriiterations.Letaibethevectorofauthorityscoresafteriiterations.OperationI:ai=AThi-1OperationO:hi=Aai,2020/6/11,.,81,链接分析-HITS,AftereachiterationofapplyingOperationsIandO,normalizeallauthorityandhubscores.Repeatuntilthescoresforeachpageconverge(theconvergenceisguaranteed).5.Sortpagesindescendingauthorityscores.6.Displaythetopauthoritypages.,2020/6/11,.,82,链接分析-HITS,Algorithm(summary)submitqtoasearchenginetoobtaintherootsetS;expandSintothebasesetT;obtaintheinducedsubgraphSG(V,E)usingT;initializea(p)=h(p)=1forallpinV;foreachpinVuntilthescoresconvergeapplyOperationI;applyOperationO;normalizea(p)andh(p);returnpageswithtopauthorityscores;,2020/6/11,.,83,链接分析-HITS,Example:Initializeallscoresto1.1stIteration:Ioperation:a(q1)=1,a(q2)=a(q3)=0,a(p1)=3,a(p2)=2Ooperation:h(q1)=5,h(q2)=3,h(q3)=5,h(p1)=1,h(p2)=0Normalization:a(q1)=0.267,a(q2)=a(q3)=0,a(p1)=0.802,a(p2)=0.535,h(q1)=0.645,h(q2)=0.387,h(q3)=0.645,h(p1)=0.129,h(p2)=0,q1,q2,q3,p1,p2,2020/6/11,.,84,链接分析-HITS,After2Iterations:a(q1)=0.061,a(q2)=a(q3)=0,a(p1)=0.791,a(p2)=0.609,h(q1)=0.656,h(q2)=0.371,h(q3)=0.656,h(p1)=0.029,h(p2)=0After5Iterations:a(q1)=a(q2)=a(q3)=0,a(p1)=0.788,a(p2)=0.615h(q1)=0.657,h(q2)=0.369,h(q3)=0.657,h(p1)=h(p2)=0,q1,q2,q3,p1,p2,2020/6/11,.,85,链接分析-HITS,Shouldalllinksbeequallytreated?Twoconsiderations:Somelinksmaybemoremeaningful/importantthanotherlinks.Websitecreatorsmaytrickthesystemtomaketheirpagesmoreauthoritativebyaddingdummypagespointingtotheircoverpages(spamming).Domainname:thefirstleveloftheURLofapage.Example:domainnamefor“/meng/meng.html”is“”.,2020/6/11,.,86,链接分析-HITS,Transverselink:linksbetweenpageswithdifferentdomainnames.I