Ch6-MapReduce算法设计revised.pptx

Ch 6 MapReduce算法设计 南京大学计算机科学与技术系主讲人 黄宜华 杨晓亮2011年春季学期 MapReduce海量数据并行处理 鸣谢 本课程得到Google公司 北京 中国大学合作部精品课程计划资助 Ch 6 MapReduce算法设计 1 MapReduce可解决哪些算法问题 2 回顾 MapReduce流水线3 MapReduce排序算法4 MapReduce单词同现分析算法5 MapReduce文档倒排索引算法6 实验2 莎士比亚文集WordCount实验实验3 莎士比亚文集倒排索引实验7 专利文献数据分析 自MapReduce发明后 Google大量用于各种海量数据处理 目前Google内部有7千以上的程序基于MapReduce实现 MapReduce可广泛应用于搜索引擎 文档倒排索引 网页链接图分析与页面排序等 Web日志分析 文档分析处理 机器学习 机器翻译等各种大规模数据并行计算应用领域各类大规模数据并行处理算法 1 MapReduce可解决哪些算法问题 CitefromGoogle 基本算法各种全局数据相关性小 能适当划分数据的计算任务 如 分布式排序分布式GREP 文本匹配查找 关系代数操作如 选择 投影 求交集 并集 连接 成组 聚合 矩阵向量相乘 矩阵相乘词频统计 wordcount 词频重要性分析 TF IDF 单词同现关系分析典型的应用如从生物医学文献中自动挖掘基因交互作用关系文档倒排索引 1 MapReduce可解决哪些算法问题 MapReduce可解决哪些算法问题 复杂算法或应用Web搜索引擎网页爬取 倒排索引 网页排序 搜索算法Web访问日志分析分析和挖掘用户在Web上的访问 购物行为特征 以定制个性化用户界面或投放用户感兴趣的产品广告数据 文本统计分析如科技文献引用关系分析和统计 专利文献引用分析和统计图算法并行化宽度优先搜索 最短路径问题 可克服Dijkstra串行算法的不足 最小生成树 子树搜索 比对Web链接图分析算法PageRank 垃圾邮件连接分析聚类 clustring 文档聚类 图聚类 其它数据集聚类 MapReduce可解决哪些算法问题 复杂算法或应用相似性比较分析算法字符序列 文档 图 数据集相似性比较分析基于统计的文本处理最大期望 EM 统计模型 隐马可夫模型 HMM 机器学习监督学习 无监督学习 分类算法 决策树 SVM 数据挖掘统计机器翻译生物信息处理DNA序列分析比对算法Blast 双序列比对 多序列比对生物网络功能模块 Motif 查找和比对广告推送与推荐系统 MapReduce算法应用专著1 MiningofMassiveDatasets2010 AnandRajaraman Kosmix Inc JeffreyD Ullman StanfordUniv 主要介绍基于MapReduce的大规模数据挖掘相关的技术和算法 尤其是Web或者从Web导出的数据 MapReduce可解决哪些算法问题 Ch3 Similaritysearch includingthekeytechniquesofminhashingandlocalitysensitivehashing Ch4 Data streamprocessingandspecializedalgorithmsfordealingwithdatathatarrivessofastitmustbeprocessedimmediatelyorlost Ch5 Thetechnologyofsearchengines includingGoogle sPageRank link spamdetection andthehubs and authoritiesapproach alinkanalysisalgorithm Hyperlink InducedTopicSearch HITS Ch6 Frequent itemsetmining includingassociationrules market baskets theA PrioriAlgorithmanditsimprovements aclassicalgorithmforlearningassociationrules Ch7 Algorithmsforclusteringverylarge high dimensionaldatasets Ch8 TwokeyproblemsforWebapplications managingadvertisingandrecommendationsystems MapReduce应用算法专著2 Data IntensiveTextProcessingwithMapReduceJimmyLinandChrisDyer 2010 UniversityofMaryland CollegePark主要介绍基于MapReduce的大规模文档数据处理技术和算法 MapReduce可解决哪些算法问题 Ch4 InvertedIndexingforTextRetrievalCh5 GraphAlgorithmsParallelBreadth FirstSearchPageRankCh6 EMAlgorithmsforTextProcessingEM HMMCaseStudy WordAlignmentforStatisticalMachineTranslation MapReduce应用案例1 纽约时报历史文章处理In2007 converting11millionimagedocumentsfromtheNewYorkTimesarchivebetween1851and1922forfreeaccess扫描存储的图像文件TIFF转换为PDF后 上网提供联机的PDF下载访问DerekGottfrid asoftwareprogrammerattheTimes thoughtthiswasaperfectopportunitytousetheAmazonWebServices AWS andHadoop StoringandservingthefinalsetofPDFsfromAmazon sSimpleStorageService S3 wasalreadydeemedamorecost effectiveapproachthanscalingupthestorageback endofthewebsite WhynotprocessthePDFsintheAWScloudaswell Derekcopiedthe4TBofTIFFimagesintoS3 He startedwritingcodetopullallthepartsthatmakeupanarticleoutofS3 generateaPDFfromthemandstorethePDFbackinS3 ThiswaseasyenoughusingtheJetS3t OpenSourceJavatoolkitforS3 iTextPDFLibraryandinstallingtheJavaAdvancedImageExtension AftertweakinghiscodetoworkwithintheHadoopframework DerekdeployedittoHadooprunningon100nodesinAmazon sElasticComputeCloud EC2 Thejobranfor24hoursandgeneratedanother1 5TBofdatatobestoredinS3 At10centsperinstanceperhour thewholejobendedupcostingonly 240 100instancesx24hoursx 0 10 incomputation MapReduce可解决哪些算法问题 Citefrom HadoopinAction ChuckLam 2010 ManningPublications MapReduce应用案例2 中国移动通信数据挖掘ChinaMobilelookstodatawarehousingandminingofthisdatatoextractinsightsforimprovingmarketingoperations networkoptimization andserviceoptimization SometypicalapplicationsincludeAnalyzinguserbehaviorPredictingcustomerchurnAnalyzingserviceassociationAnalyzingnetworkqualityofservice QOS AnalyzingsignalingdataFiltering原来使用由著名供应商提供的专用的商业数据挖掘系统 但该系统的单服务器构架严重限制了大数据量挖掘处理 一个分支机构使用了8核 32GB内存 一个磁盘阵列的Unix服务器 但仅能处理1 4百万个用户的行为数据 或者仅仅本分支机构10 的用户数据 而且处理时间很长 MapReduce可解决哪些算法问题 MapReduce应用案例2 中国移动通信数据挖掘然后他们决定基于Hadoop重新做一个数据挖掘系统Datanode TaskTracker 单路4核Xeon2 5GHzCPU 8GBRAM 4x250GBSATAdisksNamenode JobTracker 双路2核AMDOpteron2 6GHzCPU 16GBRAM 4x146GBSAS MapReduce可解决哪些算法问题 价格比较 10倍数据时的速度比较 MapReduce应用案例3 StambleUpon最佳网站推荐Usingacombinationofhumanopinionsandmachinelearningtoimmediatelydeliverrelevantcontent StumbleUponpresentsonlywebsitesthathavebeensuggestedbyotherlike mindedStumblers EachtimeyouclicktheStumblebutton youarepresentedwithahigh qualitywebsitebasedonthecollectiveopinionsofotherlike mindedwebsurfers StumbleUponusesratingsof like and dislike toformcollaborativeopinionsonwebsitequality Hadoopexcelsinthistraditionallystrongareafordistributedprocessing log and clickcollectioncombinedwithanalysis StumbleUponharnessesthisnaturalaptitudeofHadoopforavarietyofanalysistasks includingApachelogfilecollectionanduser sessionanalysis StumbleUponusesScribetocollectdatadirectlyintoHDFSwhereit sreviewedandprocessedbyanumberofsystems AcombinationofCascadingandplainMapReducebasedanalysisjobsextractdatafromthelogsforvanillastatistics suchasclickcounts MapReduce可解决哪些算法问题 清华大学MapReduce课程学生自选设计项目2007年设计项目项目1 对Netflix数据进行处理 实现相应的矩阵算法SVD 使得从这个数据集中获得比较好的电影推荐结果 项目2 通过对学校中各种不同角色的模拟以及他们之间的相互关系 可以用来模拟传染病在一个人群中的传播模式 项目3 通过网络上的数据采集以及最后对采集到的数据进行后期处理 建立索引 对于用户采购IT产品 例如数码相机进行推荐 是一个垂直搜索的雏形 项目4 NBody系统的模拟 即通过模拟多个小球或者数量众多节点的相互作用模型 用以研究行星的变化 气体的变化 布朗运动等 项目5 统计气象预报 通过对某一个地区几十年的气象数据进行统计 用来对未来的数据进行预报 主要实现一个分布式的神经网络算法 项目6 心电图数据处理 现有的心电图数据处理还停留在小规模的状态 大规模的心电图数据被大量浪费 本项目试图对大量的数据进行并行处理 从而能够利用长时间的心电图数据 项目7 网络音乐的模式分类 由于网络上各种音乐数据非常的多 本项目则基于内容对音乐进行聚类和搜索 MapReduce可解决哪些算法问题 清华大学MapReduce课程学生自选设计项目2008年设计项目项目1 笔记本电脑信息的整合与搜索 从互联网上各大网站等信息来源获取各类笔记本产品的详细信息 对数据进行分类和索引 根据用户的查询需求提供产品推荐 为用户在购买笔记本时提供有针对性的推荐和查询服务 项目2 水木精华区的全文搜索 为水木精华区建立全文搜索引擎 以网络爬虫为开始 将数据保存到分布式文件系统中并建立索引 最后建立搜索引擎 项目3 网络新闻分类 从互联网上下载各类新闻 并通过机器学习算法建立新闻分类 主要实现一个基于朴素贝叶斯方法的分类器以及网页下载与索引程序 项目4 跨论坛热门信息检索 网络上有多个论坛的内容 本项目是为了在多个论坛的热点新闻之间建立联系 在构造搜索引擎的过程中 将论坛热门信息因素加入到检索排序中 项目5 煎饼大亨 本项目主题是实现一款模拟经营类游戏 使用hadoop大规模数据处理技术 对店铺 顾客进行模拟 并针对店铺信息等提供可供玩家设置的交互性 从而实现最简单的模拟经营效果 项目6 图片搜索引擎 实现了一个基本的图片搜索引擎的功能 根据关键字来查找互联网相关图片 返回图片缩略图 并给出文件名 文件大小 图片所在网页等信息 MapReduce可解决哪些算法问题 清华大学MapReduce课程学生自选设计项目NBody模拟 布朗运动 2007年 MapReduce可解决哪些算法问题 清华大学MapReduce课程学生自选设计项目Epidemic 传染病模拟 学校生活模拟 2007年 MapReduce可解决哪些算法问题 清华大学MapReduce课程学生自选设计项目新闻分类搜索引擎 2008年 MapReduce可解决哪些算法问题 清华大学MapReduce课程学生自选设计项目手机评论搜索 2007年 MapReduce可解决哪些算法问题 2 回顾 MapReduce流水线 MapReducePipelinemap K1 V1 K2 V2 shuffleandsortreduce K2 V2 K3 V3 denotesalist Anyalgorithmthatyouwishtodevelopmustbeexpressedintermsofsuchrigidly definedcomponents FiguretakenfromJimmyLin smanuscript April2010 Phasesthatwecancontrol MapperInitialize setup map Itiscalledonceforeachkey valuepairintheinputsplit Thedefaultistheidentityfunction Close cleanup ShuffleshufflephaseneedsthePartitionertoroutetheoutputofmappertoreducerPartitionercontrolsthepartitioningofthekeysoftheintermediatemap outputs Thekeyisusedtoderivethepartition typicallybyahashfunction Thetotalnumberofpartitionsisthesameasthenumberofreducetasksforthejob HashPartitioneristhedefaultPartitioner hadoopv0 21 0 回顾 MapReduce流水线 SortwecancontrolshowthekeysaresortedbeforetheyarepassedtotheReducerbyusingacustomizedcomparatorReducerInitialize setup reduce Itiscalledonceforeachkey Thedefaultimplementationisanidentityfunction Close cleanup 回顾 MapReduce流水线 Phasesthatwecancontrol 回顾 MapReduce流水线 Hadoop常用的key value对的数据类型 这些数据类型都实现了WritableComparable接口 以便进行网络传输和文件存储 以及进行大小比较 回顾 MapReduce流水线 Hadoop编程API文档 Hadoop基本类库API http hadoop apache org common docs r0 21 0 api index htmlHadoopHDFS类库API http hadoop apache org hdfs docs r0 21 0 api index htmlHadoopMapReduce类库API http hadoop apache org mapreduce docs r0 21 0 api index html DataSize10MB 10GB 1000GB SortAlgorithminMapReducemap k1 k1 Identityfunctionshuffleandsort 1 total orderpartitioning 2 localsortingreduce k1 k1 IdentityfunctionAcustomizedtotal orderPartitionerrecallthatshufflephaseneedsaPartitionertopartitionthekeyspaceInputFormat OutputFormatthatdependsonyourdataformat 3 MapReduce排序算法 Isthereanyproblemhere MapReduce排序算法 Partitioner 两个问题 1 如何避免在某些Reducer上聚集过多的数据而拖慢了整个程序 2 当有大量的key要分配到多个partition 也就是Reducer 时 如何高效地找到每个Key所属的partition对Partitioner的要求划分均匀查找快速ThankGod thereexistsaclass TotalOrderPartitionerinhadooplibs whichwasoriginallyusedinTeraSort MapReduce排序算法 TeraSort InMay2008 runningona910 nodecluster Hadoopsortedthe10billionrecords 1TBinsize in209seconds 3 48minutes towintheannualgeneralpurposeterabytesortbenchmark Theclusterstatisticswere 910nodes4dualcoreXeons 2 0ghzperanode4SATAdisksperanode8GRAMperanode1gigabitEthernetoneachnodeRedHatEnterpriseLinuxServerRelease5 1 kernel2 6 18 SunJavaJDK1 6 0 05 b13InMay2009 itwasannouncedthatateamatYahoo usedHadooptosortoneterabytein62seconds MapReduce排序算法 TotalOrderPartitionerforTeraSort TotalOrderPartitioner一个提供全序划分的Partitioner从Hadoopv0 19 0开始正式发布在库类中为满足两个要求所采用的策略通过采样获取数据的分布构建高效的划分模型 MapReduce排序算法 TotalOrderPartitioner 获取数据分布作均匀划分Key的分布未知预读一小部分数据采样 sample 对采样数据排序后均分 假设有N个reducer 则取得N 1个分割点usesasortedlistofN 1sampledkeysthatdefinethekeyrangeforeachreduce Inparticular allkeyssuchthatsample i 1 key sample i aresenttoreducei Thisguaranteesthattheoutputofreduceiarealllessthantheoutputofreducei 1 Example设reduce数目为3 采到9条记录 1 22 55 60 62 66 68 70 90取两个分割点60 68 划分区间为 60 60 68 68 MapReduce排序算法 TotalOrderPartitioner 高效的划分模型若Key的数据类型是BinaryComparable的 即两个对象的可以直接按字节比较大小 如Text 则以key构造TrieTree 否则以二分查找来确定key的所属区间TrieTree 一种高效的适于查找的数据结构Thepartitionerbuildsatwoleveltriethatquicklyindexesintothelistofsamplekeysbasedonthefirsttwobytesofthekey ref hadoopdocs 两级的trie可以最多对应大约256 256个reducer 通常是足够的 Figure AnexampleofTrieTakenFromwiki MapReduce排序算法 wordco occurrencematrix语料库的单词同现矩阵是一个二维N N矩阵N是语料库的词汇量 即 不同单词的数目 矩阵元素M i j 代表单词W i 与单词W j 在一定范围内同现的次数 一个语句中 一个段落中 一篇文档中 或文本串中一个宽度为M个单词的窗口中 这些都依具体问题而定 Buildingwordco occurrencematricesfromlargecorporaacommontaskintextprocessing andprovidesthestartingpointtomanyotheralgorithms 4 构建单词同现矩阵算法 AWordCo occurrenceMatrixExample Figure Exampleofperson to wordco occurrencematrix Figuretakenfrom YutakaMatsuo POLYPHONET AnAdvancedSocialNetworkExtractionSystemfromtheWeb 2006 构建单词同现矩阵算法 Buildingthewordsco occurrencematrix如果内存足够大 把整个矩阵放在内存中 矩阵元素的计算会非常简单实际上 web scale的文档的词汇量可能有数十万 甚至数亿同现矩阵的空间开销为简单地在单机上的实现 内存与磁盘之间的换页会使任务的执行十分缓慢 构建单词同现矩阵算法 M R Algorithm pairs approach pseudo code 1 classMapper2 methodMap docida docd 3 foralltermw docddo4 foralltermu Neighbors w do5 Emitcountforeachco occurrenceEmit pair w u count1 1 classReducer2 methodReduce pairp counts c1 c2 3 s 04 forallcountc2counts c1 c2 do5 s s c Sumco occurrencecounts6 Emit pairp counts Algo from JimmyLin smanuscript April2010 构建单词同现矩阵算法 Asimple pairs approachexample语料wearenotwhatwewanttobebutatleastwearenotwhatweusedtobe同现定义Neighbors w wordsthatco occurwithwwithina2 wordwindow 构建单词同现矩阵算法 Asimple Pairs approachexample cont aftermap 1 1 1 1 1 1 1 1 1 1 1 1 1 1 构建单词同现矩阵算法 Asimple Pairs approachexample cont aftershuffleandsort 1 1 1 1 1 1 1 1 1 1 1 1 1 1 构建单词同现矩阵算法 Asimple Pairs approachexample cont afterreduce 2 2 2 1 1 2 1 1 1 1 构建单词同现矩阵算法 Asimple Pairs approachexample cont figure theco occurrencematrix 构建单词同现矩阵算法 算法的扩展同现定义Neighbors w 为其他形式时该怎么实现根据同现关系的不同 可能需要实现和定制不同的FileInputFormat和RecordReader 如同现关系为一个英文句子 则需要实现以一个英文句子为单位的FileInputFormat和RecordReader如同现关系为一个段落 则需要实现以一个段落为单位的FileInputFormat和RecordReader同现关系可扩展为从大量观察数据中进行任意离散关联事件的分析和数据挖掘类似应用问题零售商通过分析大量的交易记录 识别出关联的商品购买行为 如 啤酒和纸尿裤 的故事 从生物医学文献中自动挖掘基因交互作用关系 构建单词同现矩阵算法 文档倒排算法简介InvertedIndex 倒排索引 是目前几乎所有支持全文检索的搜索引擎都要依赖的一个数据结构 基于索引结构 给出一个词 term 能取得含有这个term的文档列表 thelistofdocuments WebSearch中的问题主要分为三部分 crawling gatheringwebcontent indexing constructionoftheinvertedindex retrieval rankingdocumentsgivenaquery crawling和indexing都是离线的 retrieval是在线 实时的 5 文档倒排索引算法 简单的文档倒排算法 文档倒排索引算法 基于以上索引的搜索结果 fish doc1 doc2red doc2 doc3redfish doc2 doc1 onefishtwofish doc2 redfishbluefish doc3 oneredbird 倒排索引 one doc1 doc3fish doc1 doc2two doc1red doc2 doc3blue doc2bird doc3 简单的文档倒排算法 文档倒排索引算法 importjava io IOException importjava util StringTokenizer importorg apache hadoop io Text importorg apache hadoop mapreduce Mapper publicclassInvertedIndexMapperextendsMapper Overrideprotectedvoidmap Textkey Textvalue Contextcontext throwsIOException InterruptedException defaultRecordReader LineRecordReader key lineoffset value linestring FileSplitfileSplit FileSplit context getInputSplit StringfileName fileSplit getPath getName Textword newText TextfileName lineOffset newText fileName key toString StringTokenizeritr newStringTokenizer value toString for itr hasMoreTokens word set itr nextToken context write word fileName lineOffset 改进 map输出的key除了文件名 还给出了该词所在行的偏移值 格式 filename offset 简单的文档倒排算法 文档倒排索引算法 importjava io IOException importjava util Collections importjava util Iterator importorg apache hadoop io Text importorg apache hadoop mapreduce Reducer publicclassInvertedIndexReducerextendsReducer Overrideprotectedvoidreduce Textkey Iterablevalues Contextcontext throwsIOException InterruptedException Iteratorit values iterator StringBuilderall newStringBuilder if it hasNext all append it next toString for it hasNext all append all append it next toString context write key newText all toString 最终输出键值对示例 fish doc1 0 doc1 8 doc2 0 doc2 8 简单的文档倒排算法 文档倒排索引算法 publicclassInvertedIndexer publicstaticvoidmain String args try job newJob conf invertindex job setJarByClass InvertedIndexer class job setInputFormatClass TextInputFormat class job setMapperClass InvertedIndexMapper class job setReducerClass InvertedIndexReducer class job setOutputKeyClass Text class job setOutputValueClass Text class FileInputFormat addInputPath job newPath args 1 FileOutputFormat setOutputPath job newPath args 2 System exit job waitForCompletion true 0 1 catch Exceptione e printStackTrace 带词频等属性的文档倒排算法 文档倒排索引算法 如果考虑单词在每个文档中出现的词频 位置 对应Web文档的URL等诸多属性 则前述简单的倒排算法就不足以有效工作 我们把这些词频 位置等诸多属性称为有效负载 Payload 以下的算法内容引自JimmyLin Data IntensiveTextProcessingwithMapReduce 2010 CollegePark 以及其课件 带词频等属性的文档倒排算法基本的倒排索引结构一个倒排索引由大量的postingslist构成一个postingslist由多个posting构成 按docid排序 一个postingslist与一个term关联一个posting包含一个documentid和一个payloadpayload上载有term在document中出现情况相关的信息 e g termfrequency positions termproperties 同时还有对应Web文档到其URL的映射doc id URL 文档倒排索引算法 带词频属性的文档倒排算法Map和Reduce实现伪代码1 classMapper2 procedureMap docidn docd 3 H newAssociativeArray4 foralltermt docddo5 H t H t 16 foralltermt Hdo7 Emit termt posting 1 classReducer2 procedureReduce termt postings 3 P newList4 forallposting postings do5 Append P 6 Sort P 7 Emit termt postingsP 文档倒排索引算法 备注 本算法取自JimmyLin smanuscrip April2010 没有作改动 但对其中词频的计算 H t 持保留看法 还需要讨论一下 带词频属性的文档倒排算法 Asimpleexampleposting docid tf 文档倒排索引算法 带词频属性的文档倒排算法ScalabilitybottleneckThealgorithmassumesthatthereissufficientmemorytoholdallpostingsassociatedwiththesameterm Thereducerfirstbuffersallpostingsandthenperformsanin memorysortAscollectionsgrowlarger reducerswillrunoutofmemorySolutionlettheMapReduceruntimetodothesortingEmittheintermediatekey valuepairslikethis tuple tff designtrick value to keyconversion 文档倒排索引算法 Arevisedexample 文档倒排索引算法 InvertedIndexing Arevisedexample cont 文档倒排索引算法 可扩展的带词频属性的文档倒排算法Mapper1 classMapper2 methodMap docidn docd 3 H newAssociativeArray4 foralltermt docddo5 H t H t 16 foralltermt Hdo7 Emit tuple tfH t 文档倒排索引算法 可扩展的带词频属性的文档倒排算法AcustomizedpartitionerWhy Toensurethatalltupleswiththesametermareshuffledtothesamereducer noticethatthenewkeyisatuple How ClassNewPartitionerextendsHashPartitioner org apache hadoop mapreduce lib partition HashPartitioner overridethemethodgetPartition Kkey Vvalue intnumReduceTasks term key toString split 0 termsuper getPartition term value numReduceTasks SetthecustomizedpartitionerinjobconfigurationJob setPartitionerClass NewPartitioner 文档倒排索引算法 可扩展的带词频等属性的文档倒排算法 cont Reducer1 classReducer2 methodSetup 初始化3 tprev 4 P newPostingsList5 methodReduce tuple tf f 6 ift tprev tprev then7 Emit tprev P 8 P Reset 9 P Add 10 tprev t11 methodClose12 Emit t P 文档倒排索引算法 用于输出最后一次未得到输出的 可扩展的带词频等属性的文档倒排算法 cont Extensions单词形态还原 e g books book removingstopwords commonwordssuchas the a of etc 文档倒排索引算法 Afewdesigntricks DesignPatterns LocalaggregationusecombinerComplexstructures suchas pairs and stripes value to keyconversion MapReduce算法设计总结 6 实验2 莎士比亚文集WordCount 实验内容与要求1 在Eclipse环境下编写WordCount程序 统计所有除Stop Word 如a an of in on the this that 外所有出现次数k次以上的单词计数 最后的结果按照词频从高到低排序输出2 在集群上运行程序 对莎士比亚文集文档数据进行处理3 可自行建立一个Stop Word列表文件 其中包含部分停词即可 不需要列出全部停词 参数k作为输入参数动态指定 如k 10 4 实验结果提交 要求书写一个实验报告 其中包括 实验设计说明 包括主要设计思路 算法设计 程序和各个类的设计说明程序运行和实验结果说明和分析性能 扩展性等方面存在的不足和可能的改进之处源程序 执行程序 停词列表文件运行结果文件实验报告文件命名规则 MPLab2 学号 姓名 doc实验报告提交至 FTP 210 28 132 80 用户名 hadoop口令 hadoop实验完成时间 4月22日前完成并提交报告 6 实验3 莎士比亚文集倒排索引算法 实验内容与要求1 编写所介绍的带词频属性的文档倒排索引程序 在单机上用小数据集调试通过2 在集群上运行程序 对莎士比亚文集文档数据进行倒排索引处理 结果输出到指定文件3 实验结果提交 要求书写一个实验报告 其中包括 实验设计说明 包括主要设计思路 算法设计 程序和各个类的设计说明程序运行和实验结果说明和分析性能 扩展性等方面存在的不足和可能的改进之处源程序 执行程序运行结果文件实验报告文件命名规则 MPLab2 学号 姓名 doc实验报告提交至 FTP 210 28 132 80 用户名 hadoop口令 hadoop实验完成时间 4月29日前完成并提交报告 数据源 美国专利文献数据AvailablefromtheNationalBureauofEconomicResearchathttp www nber org patents Thedatasetswereoriginallycompiledforthepaper TheNBERPatentCitationDataFile Lessons InsightsandMethodologicalTools Twodatasets Citationdataset cite75 99 txt Patentdescriptiondataset apat63 99 txt 7 专利文献数据分析 本例引自ChuckLam HadoopinAction 2010 ManningPublications 数据源 美国专利文献数据Citationdataset cite75 99 txt CITING CITED 3858241 9562033858241 13242343858241 33984063858241 35573843858241 36348893858242 15157013858242 33192613858242 36687053858242 3707004 专利文献数据分析 3858241引用了956203 1324234 3398406 3557384 3634889 数据源 美国专利文献数据Patentdescriptiondataset apat63 99 txt PATENT GYEAR GDATE APPYEAR COUNTRY POSTATE ASSIGNEE ASSCODE CLAIMS NCLASS CAT SUBCAT CMADE CRECEIVE RATIOCIT GENERAL ORIGINAL FWDAPLAG BCKGTLAG SELFCTUB SELFCTLB SECDUPBD SECDLWBD 3070801 1963 1096 BE 1 269 6 69 1 0 3070802 1963 1096 US TX 1 2 6 63 0 3070803 1963 1096 US IL 1 2 6 63 9 0 3704 3070804 1963 1096 US OH 1 2 6 63 3 0 6667 3070805 1963 1096 US CA 1 2 6 63 1 0 专利文献数据分析 专利文献数据分析 Apartialviewofthepatentcitationdatasetasagraph Eachpatentisshownasavertex node andeachcitationisadirectededge arrow 数据源 美国专利文献数据Patentdescriptiondataset apat63 99 txt 专利文献数据分析 数据源 美国专利文献数据Patentdescriptiondataset apat63 99 txt 专利文献数据分析 专利被引列表 Citationdataset倒排 M