基于层次的聚类.ppt

《基于层次的聚类.ppt》由会员分享，可在线阅读，更多相关《基于层次的聚类.ppt（94页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、网络信息收集、索引与信息检索、聚类网络信息收集、索引与信息检索、聚类信息科学技术学院马永芳张旭东张涵Agendan网络爬虫是什么？n怎样爬？n预备知识n整体框架n核心算法n算法改进Web Crawler是。是。n软件，系统n“Awebcrawlerisonetypeofbot,orsoftwareagent.“n搜集对象是什么？n整个Web?n部分Web？哪一部分？nWeb是不断更新的，哪些要re-crawl？Agendan网络爬虫是什么？n怎样爬？n预备知识n整体框架n核心算法n算法改进nDistributedCrawling怎样搜集怎样搜集?网页为节点网页中的HyperLink为有向边Cr

2、awl=图遍历,right?链接是哪些？链接是哪些？Refer to HTML 4.01 SpecificationAgendan网络爬虫是什么？n怎样爬？n预备知识n整体框架n核心算法n算法改进nDistributedCrawling系统框图系统框图Core Algorithms IPROCEDURE SPIDER1(G)Let ROOT:=any URL from GInitialize STACK Let STACK:=push(ROOT,STACK)Initialize COLLECTION While STACK is not empty,URLcurr:=pop(STACK)PAG

3、E:=look-up(URLcurr)STORE(,COLLECTION)For every URLi in PAGE,push(URLi,STACK)Return COLLECTIONAgendan网络爬虫是什么？n怎样爬？n预备知识n整体框架n核心算法n算法改进nDistributedCrawlingA More Complete Correct AlgorithmPROCEDURE SPIDER4(G,SEEDS)Initialize COLLECTION Initialize VISITED For every ROOT in SEEDSInitialize STACK Let STA

4、CK:=push(ROOT,STACK)While STACK is not empty,Do URLcurr:=pop(STACK)Until URLcurr is not in COLLECTION insert-hash(URLcurr,VISITED)PAGE:=look-up(URLcurr)STORE(,COLLECTION)For every URLi in PAGE,push(URLi,STACK)Return COLLECTIONUntil URLcurr is not in VISITED STACK用disk-basedheap结构实现还存在什么问题呢？还存在什么问题呢？

5、nSustainedgrowthinsizeanddynamicityoftheWebnEfficiencyisamustn1billionpages/permonth385pages/secnBottleneckinnetwork,look-up()callnDNSandtcpconnection/transferoverheadsimprovenetworkbandwidthutilizationnNoenoughmemorytoholdalldatastructurenIsurlorpagesVISITED?nDiskI/Oismuchsloweranddeteriorateperfor

6、manceURL不唯一性不唯一性不同url指向的同一个网页nIP地址和域名之间的多对多关系大规模网站用于负载平衡的技术：内容镜像“virtual hosting”和“Proxy pass”：不同的主机名映射到同一个IP地址，发布多个逻辑网站的需要（Apache支持）动态网页的参数Session id上一页/下一页“同义同义”地址地址n域名与IP对应存在4种情况：n一对一，一对多，多对一，多对多。一对一不会造成重复搜集，n后三种情况都有可能造成重复搜集。n可能是虚拟主机，多个域名共一个IP,内容不同,-162.105.129.12n可能是DNS轮转-202.112.8.2，-202.112.8.

7、3n可能是一个站点有多个域名对应和等价对对URLURL进行规格化进行规格化n用一个标准的字符串表示协议(http)n利用canonical主机名字n查DNS会返回IP和一个canonical名字n显式加上一个端口号（80也加上）n规格化并清理好文档路径n例如将/books/./papers/sigmod1999.ps写成/papers/sigmod1999.psRobot exclusionRobot exclusion检查 n在服务器文档根目录中的文件，robots.txt,包含一个路径前缀表，crawlers不应该跟进去抓文档，例如#AltaVista SearchUser-agent:A

8、ltaVista Intranet V2.0 W3C WebreqDisallow:/Out-Of-Date#exclude some access-controlled areasUser-agent:*Disallow:/TeamDisallow:/ProjectDisallow:/Systems限制只是对crawlers，一般浏览无妨server trapsn防止系统异常n病态HTML文件n例如，有的网页含有68 kB null字符n误导Crawler的网站n用CGI程序产生无限个网页n用软目录创建的很深的路径 Crawler needn可扩展性ScalablenParallel,dis

9、tributedn快FastnBottleneck?Networkutilizationn友好性PolitenDoS（DenyofServiceAttack）,robot.txtn健壮RobustnTraps,errors,crashrecoveryn持续搜集ContinuousnBatchorincrementalDistributed Crawling任务划分问题任务划分问题nM个节点同时执行搜集n问题：如何有效的把N个网站的搜集任务分配到M个机器上去？n目标：任务分配得均匀（Balance）谁负责http:/ chain还有很多很多问题还有很多很多问题n如：HighPerformance

10、WebCrawler！n如果不采取措施，DNS地址解析会成为一个重要的瓶颈n怎样提高DNS解析模块的性能？n并发DNSclientn缓存cachednsresultsn预取prefechclientn消除已经访问过的URLn优化方法nURL用fingerprint(如MD5)来记录，减少内存开销n利用访问的时空局部性-Cachen海量数据的高效率查找表nB-treenBloom filtern避免在重复的网页上再提取链接Agendan索引技术：IndexTechniquesn引入概览n倒排表建立n布尔查询实现n排序：ScoringandRankingn向量空间余弦相似度Document Col

11、lectionsite:()baidureport90,300pagesGooglereport43,000pagesUser Information Needn在这个新闻网站内查找narticlestalksaboutCultureofChinaandJapan,anddoesnttalkaboutstudents abroad.nQUERY：n“中国日本文化留学生”中国日本文化-留学生site:http:/ to do it?n字符串匹配，如使用grep所有WebPages，找到包含“中国中国”,“文化文化”and“日本日本”的页面,再去除包含“留学生留学生”的页面?nSlow(forla

12、rgecorpora)nNOT“留学生留学生”isnon-trivialnOtheroperations(e.g.,find“中国中国”NEAR“日本日本”)notfeasibleDocument RepresentationnBag of wordsmodelnDocument-termincidencematrix（关联矩阵）中国文化日本留学生教育北京D1110011D2011100D3101100D4100110D5111001D60010011 if page contains word,0 otherwiseIncidence VectorD1D2D3D4D5D6中国101110文化

13、110010日本011011留学生011100教育100100北京100011nTranspose：把Document-term矩阵转置n得到term-document关联矩阵n每个term对应一个0/1向量,incidencevectorRetrievalnInformationNeed:n在这个新闻网站内查找:articlestalksaboutCultureofChinaandJapan,anddoesnttalkaboutstudents abroad.nToanswerquery:n读取term向量“中国中国”,“文化文化”,“日本日本”,“留学生留学生”(complemented)

14、nbitwiseANDn101110AND110010AND011011AND100011=000010D5Lets build a search system!n考虑系统规模：n文档数：N=1milliondocuments,每篇文档约有1Kterms.n平均6bytes/term=6GBofdatainthedocuments.n不相同的term数：M=500Kdistincttermsn这个Matrix规模是？n500Kx1Mn十分稀疏：不超过onebillion1snWhatsabetterrepresentation?Agendan索引技术：IndexTechniquesn引入概览n

15、倒排表建立n布尔查询实现n排序：ScoringandRankingn向量空间余弦相似度Inverted indexn对每个termT:保存包含T的文档(编号)列表中国中国文化文化留学生留学生248163264128235813213413161DictionaryPostingsSorted by docID(more later on why).Inverted index constructionTokenizerToken stream.FriendsRomansCountrymenLinguistic modulesModified tokens.friendromancountrym

16、anIndexerInverted index.friendromancountryman24213161Documents tobe indexed.Friends,Romans,countrymen.n输入：元组序列.I did enact JuliusCaesar I was killed i the Capitol;Brutus killed me.Doc 1So let it be withCaesar.The nobleBrutus hath told youCaesar was ambitiousDoc 2Indexer stepsnSortbyterms.Core indexi

17、ng stepn合并一个文档中的多次出现，添加term的Frequency信息.n结果split为一个Dictionary文件和一个Postings文件.Agendan索引技术：IndexTechniquesn引入概览n倒排表建立n布尔查询实现n排序：ScoringandRankingn向量空间余弦相似度Boolean Query processingn查询:中国中国AND文化文化n查找Dictionary，定位中国中国;n读取对应的postings.n查找Dictionary，定位文化文化;n读取对应的postings.n“Merge”合并(AND)两个postings:1283424816

18、3264123581321中国中国文化文化34128248163264123581321The mergenLists的合并算法34248163264123581321中国中国文化文化28If the list lengths are x and y,the merge takes O(x+y)operations.Crucial:postings sorted by docID.Boolean queries:Exact matchnQueriesusingAND,ORandNOTtogetherwithquerytermsnPrimarycommercialretrievaltoolfor

19、3decades.nProfessionalsearchers(e.g.,Lawyers)stilllikeBooleanqueries:nYouknowexactlywhatyouregetting.Beyond Boolean term searchn短语phrase：nFind“BillGates”,not“BillandGates”n词的临近关系Proximity:nFindGatesNEAR Microsoft.n文档中的区域限定:nFinddocumentswith(author=Ullman)AND(textcontainsautomata).nSolution：n记录term的

20、fieldpropertyn记录term在docs中的positioninformation.Agendan索引技术：IndexTechniquesn引入概览n倒排表建立n布尔查询实现n排序：ScoringandRankingn问题描述n向量空间余弦相似度Beyond Boolean Searchn对大多数用户来说.nLIMIT!/3 STATUTE ACTION/S FEDERAL/2 TORT/3 CLAIMn大多数用户可能会输入北京北京 空气空气or北京污染作为Queryn怎样解释和处理这样full textqueries?n没有ANDORNOT等boolean连接符n某些queryte

21、rm不一定要出现在结果文档中n用户会期待结果按某种order返回，mostlikelytobeuseful的文档在结果的前面Scoring:density-basedn按query，给文档打分scoring，根据score排序nIdean如果一个文档talksaboutatopicmore,thenitisabettermatchnif如果包含很多次queryterm的出现，文档是relevant(相关的)ntermweighting.Term frequency vectorsn考察termt在文档d,中出现的次数numberofoccurrences，记作tft,dD1D2D3D4D5D6

22、中国11071340文化220060日本052019留学生012600教育300200北京17000118对一个free-textQueryqScore(q,d)=tq tft,dProblem of TF scoringn没有区分词序nPositionalinformationindexn长文档具有优势n归一化：normalizingfordocumentlengthnwft,d=tft,d/|d|n出现的重要程度其实与出现次数不成正比关系n从0次到1次的出现，和100次出现到101次出现，意义大不相同n平滑n不同的词，其重要程度其实不一样nConsiderquery日本日本 的的 汉字汉字

23、 丼丼n区分DiscriminationoftermsDiscrimination of termsn怎样度量terms的common程度 ncollectionfrequency(cf)：文档集合里term出现的总次数ndocumentfrequency(df)：文档集合里出现过term的文档总数Wordcfdftry104228760insurance104403997tf x idf term weightsntfxidf权值计算公式:ntermfrequency(tf)norwf,somemeasureoftermdensityinadocninversedocumentfrequen

24、cy(idf)n表达term的重要度(稀有度)n原始值idft=1/dftn同样，通常会作平滑n为文档中每个词计算其tf.idf权重：Documents as vectorsn每一个文档j能够被看作一个向量，每个term是一个维度，取值为tf.idfnSowehaveavectorspacentermsareaxesndocsliveinthisspacen高维空间：即使作stemming,mayhave20,000+dimensionsD1D2D3D4D5D6中国4.10.03.75.93.10.0文化4.54.50011.60日本03.52.902.13.9留学生03.15.112.800

25、教育2.9002.200北京7.10004.43.8Agendan索引技术：IndexTechniquesn引入概览n倒排表建立n布尔查询实现n排序：ScoringandRankingn问题描述n向量空间余弦相似度IntuitionPostulate:在vectorspace中“closetogether”的文档会talkaboutthesamethings.t1d2d1d3d4d5t3t2用例：Query-by-example，FreeTextqueryasvectorCosine similarityn向量d1和d2的“closeness”可以用它们之间的夹角大小来度量n具体的，可用cos

26、ineoftheanglex来计算向量相似度.n向量按长度归一化Normalizationt 1d 2d 1t 3t 2ExamplenDocs:AustensSense and Sensibility,Pride and Prejudice;BrontesWuthering Heightsncos(SAS,PAP)=.996x.993+.087x.120+.017x0.0=0.999ncos(SAS,WH)=.996x.847+.087x.466+.017x.254=0.929Notes on Index Structuren怎样保存normalizedtf-idf值？n在每一个postin

27、gsentry吗?n保存tf/normalization?nSpaceblowupbecauseoffloatsn通常：ntf以整数值保存indexcompressionn文档长度，每doc只保存一个;idf放在字典里，每个词只有一个Thus farnWecanbuildaInformationRetrievalSystemnSupportBooleanquerynSupportFree-textquerynSupportrankingresult文本聚类文本聚类n聚类分析的对象是一篇篇文档n特征：文档中的词tn每个文档d表示为一个向量n，m是特征的个数，tfti是词ti在d中出现的次数n相似

28、度：两个文档对应向量的距离n相似度矩阵：两两向量之间相似度构成的矩阵硬聚类和软聚类硬聚类和软聚类n硬聚类：每个文档只能属于一类nC1C2Ck=DC，CiCj=，其中，1ijk(1)n软聚类：文档集合被划分为k个可能相交的文档子集，即每个文档可能属于多个类别。文本聚类的流程文本聚类的流程提纲提纲n概述n文本聚类的流程n主要聚类算法介绍n聚类的质量评价n文本聚类的应用主要聚类算法介绍主要聚类算法介绍n基于划分的聚类n基于层次的聚类n其他聚类算法基于划分的聚类基于划分的聚类nK-均值（K-means）算法n是一种基于质心的聚类技术，其基本原理是首先选择k个文档作为初始的聚类点，然后根据类中对象的平均

29、值，将每个文档(重新)赋给最类似的类，并更新类的平均值，然后重复这一过程，直到类的划分不再发生变化。nK-近邻算法n每个对象和距离它最近的K-1个对象组成一个类n是一种软聚类（允许类的重叠）k-平均平均n输入:类的数目k，包含n个文本的特征向量。n输出:k个类，使平方误差准则最小。n步骤:n1)任意选择k个对象作为初始的类中心;n2)repeat;n3)根据类中对象的平均值，将每个对象(重新)赋给最类似的类;n4)更新类的平均值;n5)until不再发生变化。K-均值举例均值举例n将n个向量分到k个类别中去n选择k个初始中心n计算两项距离n计算均值K-均值算法均值算法n算法复杂度为O(kln)

30、，其中l为迭代次数，n为文档个数，k为类别个数nK-均值算法最后一定是可以收敛的n该算法本质上是一种贪心算法。n可以保证局部最优，但是很难保证全局最优。n需要预先指定k值和初始划分K-means convergence to a local minimum From WikipediaDetermining the number of clusters in a data setnRuleofthumbnTheElbowMethod变种：变种：K-medoidsmedoid：离类r质心最近的文档向量K-means 的改进的改进n确定Kn对于不同的K都尝试聚类，取效果最好的n确定初始种子n排除明

31、显是“噪声”的文档向量n尝试多种初始向量的组合，取效果最好的n通过其他方法（如层次聚类）确定初始文档向量K-近邻算法近邻算法n每个对象和距离它最近的K-1个对象组成一个类n是一种软聚类（允许类的重叠）n需要比较每两个对象之间的距离，时间代价为O(N2)基于层次的聚类基于层次的聚类n定义：对给定的数据进行层次的分解：n分类：n凝聚的（agglomerative）方法（自底向上）（案例介绍）思想：一开始将每个对象作为单独的一组，然后根据同类相近，异类相异的原则，合并对象，直到所有的组合并成一个，或达到一个终止条件为止。n分裂的（divisive）方法（自顶向下）思想：一开始将所有的对象置于一类，在

32、迭代的每一步中，一个类不断地分为更小的类，直到每个对象在单独的一个类中，或达到一个终止条件。基于层次的聚类基于层次的聚类n特点：n类的个数不需事先定好n需确定类间距离函数n运算量要大，适用于处理小样本数据n时间代价O(N2)广泛采用的类间距离：广泛采用的类间距离：n最小距离法（singlelinkagemethod）n极小异常值在实际中不多出现，避免极大值的影响广泛采用的类间距离：广泛采用的类间距离：n最大距离法（completelinkagemethod）n可能被极大值扭曲，删除这些值之后再聚类广泛采用的类间距离：广泛采用的类间距离：n类平均距离法（averagelinkagemethod）

33、类间所有样本点的平均距离n该法利用了所有样本的信息，被认为是较好的系统聚类法广泛采用的类间距离：广泛采用的类间距离：n重心法（centroidhierarchicalmethod）n类的重心之间的距离n对异常值不敏感，结果更稳定基于层次的聚类基于层次的聚类n优点：能够生成层次化的嵌套类，准确度高n缺点：速度慢，不适合大文本集的聚类提纲提纲n概述n文本聚类的流程n主要聚类算法介绍n聚类的质量评价n文本聚类的应用聚类的质量评价聚类的质量评价n指标：纯度（Purity）和F值（F-measure）n标准答案：一般是人工分好类的文档集合纯度纯度F值值F值值问题问题n如果没有可靠的人工分类的结果该如何评价分类效果的好坏？邀请话题邀请话题n特征之间的相关性问题（SVD）n样本之间的推荐关系的利用。（Hits算法）作业作业n设计合理的数据结构，实现给予上次作业的词义距离计算。要求，输入一个词，给出跟这个目标词最相近的20个词。n对比参考：googleword2vector项目n开一个大作业选题：对现代汉语的动词进行自动聚类研究并给出合理的语言学解释。2人组。对题目不清楚的可以上机的时候找老胡聊一下。