Hadoop大作业

1、网络大数据课程作业目录1 实验环境部署0.1.1 主机环境 0.1.2 虚拟机环境0.2 方法介绍0.2.1 文本聚类 0.2.2 主要的聚类方法 1.2.3 K-means 算法2.2.4 Hadoop 实现3.2.5 Spark 实现6.3 实验结果统计7.4 对两个平台上实现方法的对比7.5 收获与建议8.附录 9.网络大数据课程作业1 实验环境部署1.1 主机环境处理器Intel(R) Core(TM)2 DuoCPU 2.80GHz内存8.00GB操作系统WIN7SP1 64bit1.2 虚拟机环境VMware? Workstation 10.0.2 build-1744117处理器

2、2Core内存4GB操作系统Ubuntu12.04LTS Desktop 32bitHadoop与Spark环境在之前的练习中已经搭好。2 方法介绍2.1 文本聚类文本聚类(Text clustering)主要是依据著名的聚类假设：同类的文档相似度较大， 而不同类的文档相似度较小。 作为一种无监督的机器学习方法， 聚类由于不需要训练过程， 以及不需要预先对文档手工标注类别， 因此具有一定的灵活性和较高的自动化处理能力， 已经成为对文本信息进行有效地组织、 摘要和导航的重要手段。文本聚类可以用于生成一篇简明扼要的摘要文档； 对搜索引擎返回的结果进行聚类， 使用户迅速定位到所需要的信息； 对用户感

3、兴趣的文档 (如用户浏览器cache 中的网页)聚类，从而发现用户的兴趣模式并用于信息过滤和信息主动推荐等服务；数字图书馆服务；文档集合的自动整理等等。2.2 主要的聚类方法（ 1）基于划分的方法基于划分的聚类算法（ Partitioning Method ）是文本聚类应用中最为普遍的算法。 方法将数据集合分成若干个子集， 它根据设定的划分数目 k 选出 k 个初始聚类中心， 得到一个初始划分， 然后采用迭代重定位技术， 反复在 k 个簇之间重新计算每个簇的聚类中心， 并重新分配每个簇中的对象， 以改进划分的质量。 使得到的划分满足“簇内相似度高，簇间相似度小”的聚类原则。典型的划分聚类方法有

4、K-means算法和K-medoids算法，两者的区别在于簇代表点的计算方法不同。前者使用所有点的均值来代表簇， 后者则采用类中某个数据对象来代表簇。 为了对大规模的数据集进行聚类， 以及处理复杂形状的聚类， 各类改进的划分算法逐渐增多。基于划分方法的优点是运行速度快，但该方法必须事先确定k 的取值。算法容易局部收敛， 且不同的初始聚类中心选取对聚类结果影响较大。 为此， 应用最广泛的k-means算法有很多变种，他们可能在初始k个聚类中心的选择、相似度 的计算和计算聚类中心等策略上有所不同，最终实现聚类结果改进的目标。（ 2）基于层次的方法基于层次的聚类算法（Hierarchical Met

5、hod）又叫“分级聚类算法”或“树聚类” ， 它通过分解给定的数据对象集来创建一个层次。 这种聚类方法有两种基本的技术途径： 一是先把每个对象看作一个簇， 然后逐步对簇进行合并， 直到所有对象合为一个簇， 或满足一定条件为止； 二是把所有对象看成一类， 根据一些规则不断选择一个簇进行分解， 直到满足一些预定的条件， 如类的数目达到了预定值， 或两个最近簇的距离达到阈值等。 前者称为自下而上的凝聚式聚类， 后者称为自上而下的分裂式聚类。（ 3）基于密度的方法绝大多数划分算法都是基于对象之间的距离进行聚类， 这类方法只能发现圆形或球状的簇，较难发现任意形状的簇。为此，提出了基于密度的聚类算法（De

6、nsity-Based Clustering Metho。,其主要思想是：只要邻近区域的对象或数据点的数目超过某个阈值， 就继续聚类。 即对给定类中的每个数据点， 在一个给定范围的区域中至少包含某个数目的点，这样就能很好的过滤掉“噪声”数据，发现任意形状的簇。其基本出发点是，寻找低密度区域分离的高密度区域。（ 4）基于网格的方法基于网格的算法（ Grid-Based Clustering Method ）把对象空间量化为有限数目的单元， 形成了一个网络结构。 所用的聚类操作都在整个网络结构即量化的空间上进行。 这种方法的一个突出的优点就是处理速度很快， 其处理时间独立于数据对象的数目，只与量化

7、空间中的每一维的单元数目有关。（ 5）基于模型的方法基于模型的算法 （ Model-Based Clustering Method） 试图优化给定的数据和某些数学模型之间的适应性。 这样的算法经常是基于这样的假设， 数据是根据潜在的概率分布生成的。 它通过为每个聚类假设一个模型来发现符合相应模型的数据对象。根据标准统计方法并综合考虑“噪声”或异常数据，该方法可以自动确定聚类个数， 从而得到鲁棒性较好的聚类方法。 基于模型的算法主要有两类， 分别 为统计学方法和神经网络方法。2.3 K-means 算法K-means算法接受数据集和参数k,经过若干次迭代，将输入的n个数据对象（以 m 维向量形式

8、表示）划分为 k 个聚类，使得所获得的聚类满足：1、 同一聚类中的数据对象的相似度较高（或距离最近）；2、 不同聚类中的数据对象的相似度较低（或距离最远）。算法流程：1、 适当选择 k 个初始中心；2、 在第 i 次迭代中，对任意一个样本数据，求其到 k 个中心的距离，然后将该样本数据归到距离最短的中心所在的类；3、 对于每个类，利用求均值等方法更新该类的中心值；4、 对于所有的 k 个聚类中心， 如果经过 2、 3 的某次迭代法更新后， 值保持 不变，则迭代结束，否则继续迭代。开始结心2.4 Hadoop 实现(1) WordFrequencelnDocument.java提取中文、分词、去

9、停用词、统计词频(2) WordCountsInDocuments.java统计每个网页的单词数目本次作业的实验数据为大量的中文短文本，包含未分词和已分词两种模式,而对于大规模的中文网站聚类，其流程见下图:图1中文聚类分析根据这一完整的流程，我们先在 hadoop下实现聚类，共有七个源文件:判断网页向量属 于哪个中心建七网页向量统计单词在多少 个网页出现计算TF1DF达到迭代次数或、 中心点不改变一建立问我统计每个网页的 总词数提取中文、分 词、去除停用词判断网页向收寓 于哪个中心更新中心点随机生成K个中心统计单词在每个 网页出现的次数输出网页编号及 所属中心编号(3) WordsInCorp

10、usTFIDF.java统计单词在多少个网页出现，计算TFIDF,建立词表(4) DocumentVetorBuid.java建立网页向量，随机选取K个网页作为中心点(5) Kmeans.java判断网页属于哪一类，更新中心点，最后输出网页所属中心标号(6) KmeansDriver.java控制Mapreduc的Job顺序，以及K-means迭代流程，设置参数 DocTool.java根据网页向量以及所有中心点向量输出网页所属的中心编号在处理中文文本的过程中，三个主要的mapreduce过程如下:t'jQxJFreqjencE ln3oc jnentMapper输入key阿贝铜号va

11、lue网应全部内容提取中文、分词、去除停用词输出单词可触以端号value1Reducer输入key单词g网页编号values111 1将values H4所布1相加输出key单词©网页洞号value雎同在该网页中出现的次数表 1 WordFrequenceInDocumentWordCounrs1nCocumenr 三Mapperkey单词0 M贝编号value单河在该网引中出现的次数调换顺序疝中key网页箱号value通同工单词在该网页中山现的次数Reducer惭入key网页编号values单词1 =出现的次数1 统计每个网页有多少个单词输出key堆词网页编号value单词出现次数

12、/该网页的总词数表 2 WordCountsInDocumentsWordsInCorpusTFlDFMapper流、key事间可网中编号value单词出现次数/该网庾的总词数调换畸序输出key单词value网页堀号工由班次数/网页忌洞数Redijcer输入key制伺valuesR页编号二出闱次数/网页总词数虢计单词在参少个网页中出现.计，TFSF并记录下所有单词输出key单词&网页编号valueTFIDFcleanup在HDF3中写下词有表 3 WordsInCorpusTFIDF网页向量以及初始中心点的选取在Mapreduce中的过程为:EocumertVetorBuidMappe

13、r输入key单词日网页编号valueTFTDF调换顺序，记录所有网页编号输出key网贝编号value单年TF1DEcleanup将所有冏贝编号记淤局入HDFS中Reducersemp读取网页褊号.随机选K个作为中心点编号,读取词表输入网讨啕弓vaIves单词 1-TFIDF1使用网丧中全局工匕替换陋同一用换顺序.记录中心审编号的TFJLLF输出key网页编号value单词1编号；tf idf 1/Jcleanup将中心点聚类编号及对应的所白邛同tfidf值巧入HDFS表 4 DocumentVectorBuildDocTool简化了 Kmeans过程中的代码，将计算网页向量与中心点向量之间 的

14、余弦距离，并根据最大的余弦距离判断网页属于哪一类的方法抽象出来， Kmeans的迭代过程中可以直接在调用，简化了Kmeans主类的代码复杂度。Kmeans主类由两个Mapreduce组成，一个是在迭代过程中更新中心点，- 个是生成最后的结果，这两个 Mapreduce的 Mapper和Reducer如下：KmeansMappersetupA HDFS中读入中心点向量以及间表输入key网页编号value电词j细三；tfidf 1/调用Dor:Tool的 mjmNdfeatCCNum诋回M页所属中心编弓输出中心编号value单词1编号;tf idfl/Reducersetup从HDFS中读入词表输

15、入key中心编号values属十同一个中心所有网页TF工DF借助词表大小计算values中所有网页向量的均值作为新中心点向量输出hey中心编号value新的中心点向量表5 Kmeans聚类2.5 Spark 实现Spark平台中的实现不需要分别编写 Map方法和Reduce方法，而是按照用 行程序的正常逻辑顺序来编写。具体实现过程如下：(1) 输入的文件使用Hadoop实现中预处理之后的文件，即样本文本特征向 量集合，可以直接进行 KMeans聚类的处理；(2) 随机生成k个(k=10)向量(维度和取值范围都与样本文本的特征向 量一致)作为初始的k个中心；(3) 使用map操作将每个样本文本特

16、征向量与其所属的类别映射到一起(需要调用方法来计算每个样本文本特征向量到每个中心的距离，返回最近的中心 ID)；(4) 使用reduce操作按照映射到的中心ID来汇合，汇合的过程中，特征向 量每个维度上数值都将累加，计数器也随之增长。然后再使用 map操作，计算 平均值，即可得到新的k个中心；(5) 计算新的k个中心与旧的k个中心的距离和，若为0(或小于某一阈伯：)则停止迭代，输出聚类结果，程序结束，否则继续迭代，重复3、4、5。代码见附录。3实验结果统计经统计，一共12142条样本文本，聚类到k=10类，其中分类是09的分别 为 542、2172、1652、2698、30、2386、303、

17、506、976、877 条。Hadoop的结果：图2 Hadoop结果Spark的结果:图3 Spark结果4对两个平台上实现方法的对比(6) Hadoop的各项时间的统计信息如下(单位ms):reading files and creating diet time: 73441generating vectors time: 7133total iteration: 10first iter time: 832246average iter time: 540034total time: 5204791(7) Spark的各项时间的统计信息如下(单位ms):reading files tim

18、e: 321total iteration: 8first iter time: 30428average iter time: 15000total time: 120132列表如下：单位：ms读文件时间迭代次数首次迭代时间平均迭代时间总时间Hadoop73441108322465400345204791Spark32183042815000120132表6 Hadoop与Spark对比不难看出Spark平台的效率和速度都要比Hadoop平台高出很多。5收获与建议通过本学期“网络大数据管理理论和应用”的学习，我了解到关于大数据、 分布式平台、语义计算等比较前沿的知识。比如在学习过程中，我了解

19、到通过大 数据分析处理用户行为模式，向用户推荐广告，然后通过销量的变化来判断广告 推荐系统的好坏这样一种算法，对于这种算法我就比较感兴趣，所以通过课程的 学习我拓展了自身的视野。通过老师和助教的指导，我们还搭建了 hadoop和spark平台，进行了基本的 mapreduce编程，为以后深入学习打下了基础。在学习过程中，我们还锻炼了做 报告的能力，分享了自学的心得。至于建议方面，我觉得做报告的环节，是否可以限定在相关领域的核心期刊 或会议论文上，这样学术性会更好，更能锻炼大家的学习和报告能力。附录object SparkKMeans /String 转 Vectordef parseVecto

20、r(line: String): Vector = return new Vector(line.split( ' ').map( .toDouble)计算最近中心点def closestCenter(p: Vector, centers: ArrayVector): Int = var bestIndex = 0var bestDist = p.squaredDist(centers( 0) /差平方之和for (i <- 1 until centers.length) val dist = p.squaredDist(centers( i)if (dist <

21、bestDist) bestDist = distbestIndex = ireturn bestIndex/主方法def main(args: ArrayString) val sc = new SparkContext( "local" , "SparkKMeans")System.out.println( "reading files start.")val t1 = System.currentTimeMillis()val lines = sc.textFile( "/home/fabkxd/Documents/k

22、means_data/inputfile.txt" )val points = lines.map(parseVector(_).cache() /文本中每行代表一个样本，转换为 Vectorval t2 = System.currentTimeMillis()System.out.println( "reading files done. n")val dimensions = 5100 /节点的维度val k = 10 聚类个数System.out.println( "initial centers start.")/随机初始化k个中心节点

23、val rand = new Random(42)var centers = new ArrayVector( k)for (i <- 0 until k)centers(i) = Vector( dimensions, _ => rand.nextDouble)System.out.println( "initial centers done. n")System.out.println( "kmeans iterations start.")var first: Long = 0val to1 = System.currentTimeMi

24、llis()var iter: Int = 1var over: Int = 1for (i <- 1 to iterations) if (over = 1) System.out.println( "titeration " + i + " start.")var ti1 = System.currentTimeMillis()/对每个点计算距离其最近的中心点val mappedPoints = points .map p => (closestCenter(p, centers), (p, 1) val newCenters = mappedPoints.reduceByKey case (sum1, count1), (sum2, count2) => (sum1 + sum2, count1 + count2) /(向量相加，计数器相加).map case (id, (sum, count) => (id, sum / count) /根据前面的聚类，用平均值算法重新计算中心节点的位