Ch9 数据挖掘基础算法.pdf

鸣谢：本课程得到Google公司(北京） 中国大学合作部精品课程计划资助 9.1 数据挖掘并行算法研究的重要性 9.2 基于MapReduce的K-Means聚类算法 9.3 基于MapReduce的分类算法 9.4 基于MapReduce的频繁项集挖掘算法  数据挖掘是通过对大规模观测数据集的分析，寻找隐藏在这 些数据集中的有用信息和事实的过程。  数据挖掘的特征之一：海量数据 Small data does not require data mining, large data causes problems —— 摘自黎铭的《数据挖掘》课件  研究发现大数据隐含着更为准确的事实  因此海量数据挖掘是并行计算中值得研究的一个领域 研究发现大数据隐含着更为准确的事实 2001年微软研究院的 Banko and Brill*等研究发 现数据越大，机器学习 的精度越高；当数据不 断增长时，不同算法的 分类精度趋向于相同！ * M. Banko and E. Brili (2001). Scaling to very very large corpora for natural language disambiguation. ACL 2001 研究发现大数据隐含着更为准确的事实 2007年Google公司 Brants等基于MapReduce 研究了一个2万亿单词 训练数据集的语言模 型，发现大数据集上 的简单算法能比小数 据集上的复杂算法产 生更好的结果 * T. Brants, A. C. Popat, et al. Large Language Models in Machine Translation. In EMNLP-CoNLL 2007 - Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning 9.1 数据挖掘并行算法研究的重要性 9.2 基于MapReduce的K-Means聚类算法 9.3 基于MapReduce的分类算法 9.4 基于MapReduce的频繁项集挖掘算法 9.2 基于MapReduce的K-Means聚类算法 1. K-Means聚类算法介绍 2. 基于MapReduce的K-Means并行算法设计 3. 实验结果与小结 4. 聚类算法应用实例  定义 ：将给定的多个对象分成若干组，组内的各个对象是相似 的，组间的对象是不相似的。进行划分的过程就是聚类过程， 划分后的组称为簇(cluster) 。  几种聚类方法： 基于划分的方法； 基于层次的方法； 基于密度的方法；  ... ... 数据点的数值类型  数据点的类型可分为： 欧氏（Euclidean） 非欧  这二者在数据的表示以及处理上有较大的不同： 怎样来表示cluster ？ 怎样来计算相似度 Cluster的表示  欧氏空间： 取各个数据点的平均值（centroid）  非欧空间 取某个处于最中间的点 取若干个最具代表性的点（clustroid） ... ... 相似度(距离)的计算  欧氏空间：可以有较为简单的方法  非欧氏空间：通常不能直接进行简单的数字计算 Jaccard 距离: 1 - |S ∩ T| / | S ∪T| Cosine距离：两个向量的夹角大小 Edit 距离：适合于string类型的数据 基于划分(Partitioning)的聚类方法  给定N个对象，构造K个分组，每个分组就代表一个聚类。  K个分组满足以下条件： 每个分组至少包含一个对象； 每个对象属于且仅属于一个分组；  K-Means算法是最常见和典型的基于划分的聚类方法 K-Means算法 输入：待聚类的N个数据点，期望生成的聚类的个数K 输出：K个聚类 算法描述: 选出K个点作为初始的cluster center Loop: 对输入中的每一个点p ： ｛