Hadoop大作业

网络大数据课程作业TOC\o"1-3"\h\u目录HYPERLINK\l_Toc72631实验环境部署PAGEREF_Toc72631HYPERLINK\l_Toc139411.1主机环境PAGEREF_Toc139411HYPERLINK\l_Toc210161.2虚拟机环境PAGEREF_Toc210161HYPERLINK\l_Toc182202方法介绍PAGEREF_Toc182201HYPERLINK\l_Toc160992.1文本聚类PAGEREF_Toc160991HYPERLINK\l_Toc15582.2主要的聚类方法PAGEREF_Toc15582HYPERLINK\l_Toc194322.3K-means算法PAGEREF_Toc194323HYPERLINK\l_Toc299202.4Hadoop实现PAGEREF_Toc299204HYPERLINK\l_Toc257592.5Spark实现PAGEREF_Toc257597HYPERLINK\l_Toc19503实验结果统计PAGEREF_Toc19508HYPERLINK\l_Toc290214对两个平台上实现方法的对比PAGEREF_Toc290218HYPERLINK\l_Toc326645收获与建议PAGEREF_Toc326649HYPERLINK\l_Toc26478附录PAGEREF_Toc2647810网络大数据课程作业1实验环境部署1.1主机环境处理器Intel(R)Core(TM)2DuoCPU2.80GHz内存8.00GB操作系统WIN7SP164bit1.2虚拟机环境VMware®Workstation10.0.2build-1744117处理器2Core内存4GB操作系统Ubuntu12.04LTSDesktop32bitHadoop与Spark环境在之前的 练习 飞向蓝天的恐龙练习非连续性文本练习把字句和被字句的转换练习呼风唤雨的世纪练习呼风唤雨的世纪课后练习 中已经搭好。2方法介绍2.1文本聚类文本聚类（Textclustering）主要是依据著名的聚类假设：同类的文档相似度较大，而不同类的文档相似度较小。作为一种无监督的机器学习方法，聚类由于不需要训练过程，以及不需要预先对文档手工标注类别，因此具有一定的灵活性和较高的自动化处理能力，已经成为对文本信息进行有效地组织、摘要和导航的重要手段。文本聚类可以用于生成一篇简明扼要的摘要文档；对搜索引擎返回的结果进行聚类，使用户迅速定位到所需要的信息；对用户感兴趣的文档（如用户浏览器cache中的网页）聚类，从而发现用户的兴趣模式并用于HYPERLINK"http://baike.baidu.com/view/506542.htm"\t"http://baike.baidu.com/_blank"信息过滤和信息主动推荐等服务；数字图 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 馆服务；HYPERLINK"http://baike.baidu.com/view/5182467.htm"\t"http://baike.baidu.com/_blank"文档集合的自动整理等等。2.2主要的聚类方法（1）基于划分的方法基于划分的聚类算法（PartitioningMethod）是文本聚类应用中最为普遍的算法。方法将数据集合分成若干个子集，它根据设定的划分数目k选出k个初始聚类中心，得到一个初始划分，然后采用迭代重定位技术，反复在k个簇之间重新计算每个簇的聚类中心，并重新分配每个簇中的对象，以改进划分的质量。使得到的划分满足“簇内相似度高，簇间相似度小”的聚类原则。典型的划分聚类方法有K-means算法和K-medoids算法，两者的区别在于簇代表点的计算方法不同。前者使用所有点的均值来代表簇，后者则采用类中某个数据对象来代表簇。为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，各类改进的划分算法逐渐增多。基于划分方法的优点是运行速度快，但该方法必须事先确定k的取值。算法容易局部收敛，且不同的初始聚类中心选取对聚类结果影响较大。为此，应用最广泛的k-means算法有很多变种，他们可能在初始k个聚类中心的选择、相似度的计算和计算聚类中心等策略上有所不同，最终实现聚类结果改进的目标。（2）基于层次的方法基于层次的聚类算法（HierarchicalMethod）又叫“分级聚类算法”或“树聚类”，它通过分解给定的数据对象集来创建一个层次。这种聚类方法有两种基本的技术途径：一是先把每个对象看作一个簇，然后逐步对簇进行合并，直到所有对象合为一个簇，或满足一定条件为止；二是把所有对象看成一类，根据一些规则不断选择一个簇进行分解，直到满足一些预定的条件，如类的数目达到了预定值，或两个最近簇的距离达到阈值等。前者称为自下而上的凝聚式聚类，后者称为自上而下的分裂式聚类。（3）基于密度的方法绝大多数划分算法都是基于对象之间的距离进行聚类，这类方法只能发现圆形或球状的簇，较难发现任意形状的簇。为此，提出了基于密度的聚类算法（Density-BasedClusteringMethod），其主要思想是：只要邻近区域的对象或数据点的数目超过某个阈值，就继续聚类。即对给定类中的每个数据点，在一个给定范围的区域中至少包含某个数目的点，这样就能很好的过滤掉“噪声”数据，发现任意形状的簇。其基本出发点是，寻找低密度区域分离的高密度区域。（4）基于网格的方法基于网格的算法（Grid-BasedClusteringMethod）把对象空间量化为有限数目的单元，形成了一个网络结构。所用的聚类操作都在整个网络结构即量化的空间上进行。这种方法的一个突出的优点就是处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中的每一维的单元数目有关。（5）基于模型的方法基于模型的算法（Model-BasedClusteringMethod）试图优化给定的数据和某些数学模型之间的适应性。这样的算法经常是基于这样的假设，数据是根据潜在的概率分布生成的。它通过为每个聚类假设一个模型来发现符合相应模型的数据对象。根据标准统计方法并综合考虑“噪声”或异常数据，该方法可以自动确定聚类个数，从而得到鲁棒性较好的聚类方法。基于模型的算法主要有两类，分别为统计学方法和神经网络方法。2.3K-means算法K-means算法接受数据集和参数k，经过若干次迭代，将输入的n个数据对象（以m维向量形式表示）划分为k个聚类，使得所获得的聚类满足：同一聚类中的数据对象的相似度较高（或距离最近）；不同聚类中的数据对象的相似度较低（或距离最远）。算法 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 ：适当选择k个初始中心；在第i次迭代中，对任意一个样本数据，求其到k个中心的距离，然后将该样本数据归到距离最短的中心所在的类；对于每个类，利用求均值等方法更新该类的中心值；对于所有的k个聚类中心，如果经过2、3的某次迭代法更新后，值保持不变，则迭代结束，否则继续迭代。2.4Hadoop实现本次作业的实验数据为大量的中文短文本，包含未分词和已分词两种模式，而对于大规模的中文网站聚类，其流程见下图：图1中文聚类分析根据这一完整的流程，我们先在hadoop下实现聚类，共有七个源文件：（1）WordFrequenceInDocument.java提取中文、分词、去停用词、统计词频 （2）WordCountsInDocuments.java统计每个网页的单词数目  （3）WordsInCorpusTFIDF.java统计单词在多少个网页出现，计算TFIDF，建立词表  （4）DocumentVetorBuid.java建立网页向量，随机选取K个网页作为中心点  （5）Kmeans.java判断网页属于哪一类，更新中心点，最后输出网页所属中心标号  （6）KmeansDriver.java控制Mapreduc的Job顺序，以及K-means迭代流程，设置参数  （7）DocTool.java根据网页向量以及所有中心点向量输出网页所属的中心编号在处理中文文本的过程中，三个主要的mapreduce过程如下：表1WordFrequenceInDocument表2WordCountsInDocuments表3WordsInCorpusTFIDF网页向量以及初始中心点的选取在Mapreduce中的过程为：表4DocumentVectorBuildDocTool简化了Kmeans过程中的代码，将计算网页向量与中心点向量之间的余弦距离，并根据最大的余弦距离判断网页属于哪一类的方法抽象出来，Kmeans的迭代过程中可以直接在调用，简化了Kmeans主类的代码复杂度。 Kmeans主类由两个Mapreduce组成，一个是在迭代过程中更新中心点，一个是生成最后的结果，这两个Mapreduce的Mapper和Reducer如下：表5Kmeans聚类2.5Spark实现Spark平台中的实现不需要分别编写Map方法和Reduce方法，而是按照串行程序的正常逻辑顺序来编写。具体实现过程如下：（1）输入的文件使用Hadoop实现中预处理之后的文件，即样本文本特征向量集合，可以直接进行KMeans聚类的处理；（2）随机生成k个（k=10）向量（维度和取值范围都与样本文本的特征向量一致）作为初始的k个中心；（3）使用map操作将每个样本文本特征向量与其所属的类别映射到一起（需要调用方法来计算每个样本文本特征向量到每个中心的距离，返回最近的中心ID）；（4）使用reduce操作按照映射到的中心ID来汇合，汇合的过程中，特征向量每个维度上数值都将累加，计数器也随之增长。然后再使用map操作，计算平均值，即可得到新的k个中心；（5）计算新的k个中心与旧的k个中心的距离和，若为0（或小于某一阈值）则停止迭代，输出聚类结果，程序结束，否则继续迭代，重复3、4、5。代码见附录。3实验结果统计经统计，一共12142条样本文本，聚类到k=10类，其中分类是0~9的分别为542、2172、1652、2698、30、2386、303、506、976、877条。Hadoop的结果：图2Hadoop结果Spark的结果：图3Spark结果4对两个平台上实现方法的对比（1）Hadoop的各项时间的统计信息如下（单位ms）：readingfilesandcreatingdicttime:73441generatingvectorstime:7133totaliteration:10firstitertime:832246averageitertime:540034totaltime:5204791（2）Spark的各项时间的统计信息如下（单位ms）：readingfilestime:321totaliteration:8firstitertime:30428averageitertime:15000totaltime:120132列表如下：单位：ms读文件时间迭代次数首次迭代时间平均迭代时间总时间Hadoop73441108322465400345204791Spark32183042815000120132表6Hadoop与Spark对比不难看出Spark平台的效率和速度都要比Hadoop平台高出很多。5收获与建议通过本学期“网络大数据管理理论和应用”的学习，我了解到关于大数据、分布式平台、语义计算等比较前沿的知识。比如在学习过程中，我了解到通过大数据分析处理用户行为模式，向用户推荐广告，然后通过销量的变化来判断广告推荐系统的好坏这样一种算法，对于这种算法我就比较感兴趣，所以通过课程的学习我拓展了自身的视野。通过老师和助教的指导，我们还搭建了hadoop和spark平台，进行了基本的mapreduce编程，为以后深入学习打下了基础。在学习过程中，我们还锻炼了做 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 的能力，分享了自学的心得。至于建议方面，我觉得做报告的环节，是否可以限定在相关领域的核心期刊或会议论文上，这样学术性会更好，更能锻炼大家的学习和报告能力。附录objectSparkKMeans{//String转VectordefparseVector(line:String):Vector={returnnewVector(line.split('').map(_.toDouble))}//计算最近中心点defclosestCenter(p:Vector,centers:Array[Vector]):Int={varbestIndex=0varbestDist=p.squaredDist(centers(0))//差平方之和for(i<-1untilcenters.length){valdist=p.squaredDist(centers(i))if(distrand.nextDouble)System.out.println("initialcentersdone...\n")System.out.println("kmeansiterationsstart...")varfirst:Long=0valto1=System.currentTimeMillis()variter:Int=1varover:Int=1for(i<-1toiterations){if(over==1){System.out.println("\titeration"+i+"start...")varti1=System.currentTimeMillis()//对每个点计算距离其最近的中心点valmappedPoints=points.map{p=>(closestCenter(p,centers),(p,1))}valnewCenters=mappedPoints.reduceByKey{case((sum1,count1),(sum2,count2))=>(sum1+sum2,count1+count2)//(向量相加,计数器相加)}.map{case(id,(sum,count))=>(id,sum/count)//根据前面的聚类，用平均值算法重新计算中心节点的位置}.collectvarcdist:Double=0//计算收敛距离并更新中心节点for((id,value)<-newCenters){cdist+=value.squaredDist(centers(id))centers(id)=value}System.out.println("\t\tdistance:"+cdist)varti2=System.currentTimeMillis()if(first==0)first=ti2-ti1System.out.println("\titeration"+i+"done...")if(cdist<0.3){mappedPoints.saveAsTextFile("output")iter=iover=0}}}valto2=System.currentTimeMillis()System.out.println("kmeansiterationsdone...")System.out.println("readingfilestime:"+(t2-t1))System.out.println("totaliteration:"+iter);System.out.println("firstitertime:"+first);System.out.println("averageitertime:"+(to2-to1)/iter);System.out.println("totaltime:"+(to2-to1));}}