基于层次的聚类.ppt

网络信息收集 索引与信息检索 聚类 信息科学技术学院马永芳张旭东张涵 Agenda 网络爬虫是什么 怎样爬 预备知识整体框架核心算法算法改进 WebCrawler是 软件 系统 Awebcrawlerisonetypeofbot orsoftwareagent 搜集对象是什么 整个Web 部分Web 哪一部分 Web是不断更新的 哪些要re crawl Agenda 网络爬虫是什么 怎样爬 预备知识整体框架核心算法算法改进DistributedCrawling 怎样搜集 网页为节点网页中的HyperLink为有向边Crawl 图遍历 right 链接是哪些 RefertoHTML4 01Specification Agenda 网络爬虫是什么 怎样爬 预备知识整体框架核心算法算法改进DistributedCrawling 系统框图 CoreAlgorithmsI PROCEDURESPIDER1 G LetROOT anyURLfromGInitializeSTACKLetSTACK push ROOT STACK InitializeCOLLECTIONWhileSTACKisnotempty URLcurr pop STACK PAGE look up URLcurr STORE COLLECTION ForeveryURLiinPAGE push URLi STACK ReturnCOLLECTION Agenda 网络爬虫是什么 怎样爬 预备知识整体框架核心算法算法改进DistributedCrawling AMoreCompleteCorrectAlgorithm PROCEDURESPIDER4 G SEEDS InitializeCOLLECTIONInitializeVISITEDForeveryROOTinSEEDSInitializeSTACKLetSTACK push ROOT STACK WhileSTACKisnotempty DoURLcurr pop STACK UntilURLcurrisnotinCOLLECTIONinsert hash URLcurr VISITED PAGE look up URLcurr STORE COLLECTION ForeveryURLiinPAGE push URLi STACK ReturnCOLLECTION UntilURLcurrisnotinVISITED STACK用disk basedheap结构实现 还存在什么问题呢 SustainedgrowthinsizeanddynamicityoftheWebEfficiencyisamust1billionpages permonth 385pages secBottleneckinnetwork look up callDNSandtcpconnection transferoverheads improvenetworkbandwidthutilizationNoenoughmemorytoholdalldatastructureIsurlorpagesVISITED DiskI Oismuchsloweranddeteriorateperformance URL不唯一性 不同url指向的同一个网页IP地址和域名之间的多对多关系大规模网站用于负载平衡的技术 内容镜像 virtualhosting 和 Proxypass 不同的主机名映射到同一个IP地址 发布多个逻辑网站的需要 Apache支持 动态网页的参数Sessionid上一页 下一页 同义 地址 域名与IP对应存在4种情况 一对一 一对多 多对一 多对多 一对一不会造成重复搜集 后三种情况都有可能造成重复搜集 可能是虚拟主机 多个域名共一个IP 内容不同 162 105 129 12可能是DNS轮转 202 112 8 2 202 112 8 3可能是一个站点有多个域名对应和等价 对URL进行规格化 用一个标准的字符串表示协议 http 利用canonical主机名字查DNS会返回IP和一个canonical名字显式加上一个端口号 80也加上 规格化并清理好文档路径例如将 books papers sigmod1999 ps写成 papers sigmod1999 ps Robotexclusion 检查在服务器文档根目录中的文件 robots txt 包含一个路径前缀表 crawlers不应该跟进去抓文档 例如 AltaVistaSearchUser agent AltaVistaIntranetV2 0W3CWebreqDisallow Out Of Date excludesomeaccess controlledareasUser agent Disallow TeamDisallow ProjectDisallow Systems限制只是对crawlers 一般浏览无妨 servertraps 防止系统异常病态HTML文件例如 有的网页含有68kBnull字符误导Crawler的网站用CGI程序产生无限个网页用软目录创建的很深的路径 WebCrawlerneed 可扩展性ScalableParallel distributed快FastBottleneck Networkutilization友好性PoliteDoS DenyofServiceAttack robot txt健壮RobustTraps errors crashrecovery持续搜集ContinuousBatchorincremental DistributedCrawling 任务划分问题 M个节点同时执行搜集问题 如何有效的把N个网站的搜集任务分配到M个机器上去 目标 任务分配得均匀 Balance 23 Hashing 从一个值均匀分布的hash函数开始 h name avalue e g 32 bitinteger 把values映射到hashbuckets一般取模mod buckets 把items放到buckets冲突 需要chain解决冲突 0 1 2 3 0 4 8 12 buckets h x values overflowchain 还有很多很多问题 如 HighPerformanceWebCrawler 如果不采取措施 DNS地址解析会成为一个重要的瓶颈怎样提高DNS解析模块的性能 并发DNSclient缓存cachednsresults预取prefechclient消除已经访问过的URL优化方法URL用fingerprint 如MD5 来记录 减少内存开销利用访问的时空局部性 Cache海量数据的高效率查找表B treeBloomfilter避免在重复的网页上再提取链接 Agenda 索引技术 IndexTechniques引入概览倒排表建立布尔查询实现排序 ScoringandRanking向量空间余弦相似度 DocumentCollection site baidureport90 300pagesGooglereport43 000pages UserInformationNeed 在这个新闻网站内查找articlestalksaboutCultureofChinaandJapan anddoesn ttalkaboutstudentsabroad QUERY 中国日本文化 留学生 中国日本文化 留学生site Howtodoit 字符串匹配 如使用grep所有WebPages 找到包含 中国 文化 and 日本 的页面 再去除包含 留学生 的页面 Slow forlargecorpora NOT 留学生 isnon trivialOtheroperations e g find 中国 NEAR 日本 notfeasible DocumentRepresentation BagofwordsmodelDocument termincidencematrix 关联矩阵 IncidenceVector Transpose 把Document term矩阵转置得到term document关联矩阵每个term对应一个0 1向量 incidencevector Retrieval InformationNeed 在这个新闻网站内查找 articlestalksaboutCultureofChinaandJapan anddoesn ttalkaboutstudentsabroad Toanswerquery 读取term向量 中国 文化 日本 留学生 complemented bitwiseAND101110AND110010AND011011AND100011 000010 D5 Let sbuildasearchsystem 考虑系统规模 文档数 N 1milliondocuments 每篇文档约有1Kterms 平均6bytes term 6GBofdatainthedocuments 不相同的term数 M 500Kdistinctterms这个Matrix规模是 500Kx1M十分稀疏 不超过onebillion1 sWhat sabetterrepresentation Agenda 索引技术 IndexTechniques引入概览倒排表建立布尔查询实现排序 ScoringandRanking向量空间余弦相似度 Invertedindex 对每个termT 保存包含T的文档 编号 列表 Invertedindexconstruction Documentstobeindexed Friends Romans countrymen 输入 元组序列 IdidenactJuliusCaesarIwaskilledi theCapitol Brutuskilledme Doc1 SoletitbewithCaesar ThenobleBrutushathtoldyouCaesarwasambitious Doc2 Indexersteps Sortbyterms Coreindexingstep 合并一个文档中的多次出现 添加term的Frequency信息 结果split为一个Dictionary文件和一个Postings文件 Agenda 索引技术 IndexTechniques引入概览倒排表建立布尔查询实现排序 ScoringandRanking向量空间余弦相似度 BooleanQueryprocessing 查询 中国AND文化查找Dictionary 定位中国 读取对应的postings 查找Dictionary 定位文化 读取对应的postings Merge 合并 AND 两个postings Themerge Lists的合并算法 34 2 4 8 16 32 64 1 2 3 5 8 13 21 2 8 Ifthelistlengthsarexandy themergetakesO x y operations Crucial postingssortedbydocID Booleanqueries Exactmatch QueriesusingAND ORandNOTtogetherwithquerytermsPrimarycommercialretrievaltoolfor3decades Professionalsearchers e g Lawyers stilllikeBooleanqueries Youknowexactlywhatyou regetting BeyondBooleantermsearch 短语phrase Find BillGates not BillandGates 词的临近关系Proximity FindGatesNEARMicrosoft 文档中的区域限定 Finddocumentswith author Ullman AND textcontainsautomata Solution 记录term的fieldproperty记录term在docs中的positioninformation Agenda 索引技术 IndexTechniques引入概览倒排表建立布尔查询实现排序 ScoringandRanking问题描述向量空间余弦相似度 BeyondBooleanSearch 对大多数用户来说 LIMIT 3STATUTEACTION SFEDERAL 2TORT 3CLAIM大多数用户可能会输入北京空气or北京污染作为Query怎样解释和处理这样fulltextqueries 没有ANDORNOT等boolean连接符某些queryterm不一定要出现在结果文档中用户会期待结果按某种order返回 mostlikelytobeuseful的文档在结果的前面 Scoring density based 按query 给文档打分scoring 根据score排序Idea如果一个文档talksaboutatopicmore thenitisabettermatch if如果包含很多次queryterm的出现 文档是relevant 相关的 termweighting Termfrequencyvectors 考察termt在文档d 中出现的次数numberofoccurrences 记作tft d 对一个free textQueryqScore q d t qtft d ProblemofTFscoring 没有区分词序 Positionalinformationindex长文档具有优势 归一化 normalizingfordocumentlengthwft d tft d d 出现的重要程度其实与出现次数不成正比关系从0次到1次的出现 和100次出现到101次出现 意义大不相同 平滑不同的词 其重要程度其实不一样Considerquery日本的汉字丼 区分Discriminationofterms Discriminationofterms 怎样度量terms的common程度collectionfrequency cf 文档集合里term出现的总次数documentfrequency df 文档集合里出现过term的文档总数 tfxidftermweights tfxidf权值计算公式 termfrequency tf orwf somemeasureoftermdensityinadocinversedocumentfrequency idf 表达term的重要度 稀有度 原始值idft 1 dft同样 通常会作平滑为文档中每个词计算其tf idf权重 Documentsasvectors 每一个文档j能够被看作一个向量 每个term是一个维度 取值为tf idfSowehaveavectorspacetermsareaxesdocsliveinthisspace高维空间 即使作stemming mayhave20 000 dimensions Agenda 索引技术 IndexTechniques引入概览倒排表建立布尔查询实现排序 ScoringandRanking问题描述向量空间余弦相似度 Intuition Postulate 在vectorspace中 closetogether 的文档会talkaboutthesamethings 用例 Query by example FreeTextqueryasvector Cosinesimilarity 向量d1和d2的 closeness 可以用它们之间的夹角大小来度量具体的 可用cosineoftheanglex来计算向量相似度 向量按长度归一化Normalization Example Docs Austen sSenseandSensibility PrideandPrejudice Bronte sWutheringHeightscos SAS PAP 996x 993 087x 120 017x0 0 0 999cos SAS WH 996x 847 087x 466 017x 254 0 929 NotesonIndexStructure 怎样保存normalizedtf idf值 在每一个postingsentry吗 保存tf normalization Spaceblowupbecauseoffloats通常 tf以整数值保存 indexcompression文档长度 每doc只保存一个 idf放在字典里 每个词只有一个 Thusfar WecanbuildaInformationRetrievalSystemSupportBooleanquerySupportFree textquerySupportrankingresult 文本聚类 聚类分析的对象是一篇篇文档特征 文档中的词t每个文档d表示为一个向量 m是特征的个数 tfti是词ti在d中出现的次数相似度 两个文档对应向量的距离相似度矩阵 两两向量之间相似度构成的矩阵 硬聚类和软聚类 硬聚类 每个文档只能属于一类C1 C2 Ck DC Ci Cj 其中 1 i j k 1 软聚类 文档集合被划分为k个可能相交的文档子集 即每个文档可能属于多个类别 文本聚类的流程 提纲 概述文本聚类的流程主要聚类算法介绍聚类的质量评价文本聚类的应用 主要聚类算法介绍 基于划分的聚类基于层次的聚类其他聚类算法 基于划分的聚类 K 均值 K means 算法是一种基于质心的聚类技术 其基本原理是首先选择k个文档作为初始的聚类点 然后根据类中对象的平均值 将每个文档 重新 赋给最类似的类 并更新类的平均值 然后重复这一过程 直到类的划分不再发生变化 K 近邻算法每个对象和距离它最近的K 1个对象组成一个类是一种软聚类 允许类的重叠 k 平均 输入 类的数目k 包含n个文本的特征向量 输出 k个类 使平方误差准则最小 步骤 1 任意选择k个对象作为初始的类中心 2 repeat 3 根据类中对象的平均值 将每个对象 重新 赋给最类似的类 4 更新类的平均值 5 until不再发生变化 K 均值举例 将n个向量分到k个类别中去选择k个初始中心计算两项距离计算均值 K 均值算法 算法复杂度为O kln 其中l为迭代次数 n为文档个数 k为类别个数K 均值算法最后一定是可以收敛的该算法本质上是一种贪心算法 可以保证局部最优 但是很难保证全局最优 需要预先指定k值和初始划分 K meansconvergencetoalocalminimum FromWikipedia Determiningthenumberofclustersinadataset RuleofthumbTheElbowMethod 变种 K medoids medoid 离类r质心最近的文档向量 K means的改进 确定K对于不同的K都尝试聚类 取效果最好的确定初始种子排除明显是 噪声 的文档向量尝试多种初始向量的组合 取效果最好的通过其他方法 如层次聚类 确定初始文档向量 K 近邻算法 每个对象和距离它最近的K 1个对象组成一个类是一种软聚类 允许类的重叠 需要比较每两个对象之间