大数据：互联网大规模数据挖掘

1、Mining of Massive Datasets,大数据：互联网大规模数据挖掘与分布式处理,聚类,7,Part,Clustering,聚类是对点集进行考察并按照某种距离测度将它们聚成多个“簇”的过程。聚类的目标是同一簇内的点之间的距离较短，而不同簇中点之间的距离较大。如图，不同种类的犬在某种程度上形成一种簇。三种不同犬类的身高体重分布图，可以知道这些犬可以分到三个簇中，每个簇恰好对应一种犬类。,而聚类分析则是根据最大化簇内的相似性、最小化簇间的相似性的原则将数据对象聚类或分组，所形成的每个簇可以看作一个数据对象类，用显式或隐式的方法描述它们。,最大化簇内的相似性,最小化簇间的相似性,01,

2、02,03,04,05,06,能够适用于大数据量 （可伸缩性）,能够处理不同类型数据 （距离定义）,能够发现任意形状的簇 （结果特点）,能够处理高维数据,具有处理噪声的能力,聚类结果可解易使用,Web广告,8,Part,Advertising on the Web,目前，许多WEB应用通过广告而维持生计，从在线广告中获益最多的是搜索应用，而搜索广告的有效性主要源于将搜索查询和广告进行匹配的一个称为Adwords模型。 本章将主要关注广告匹配的优化算法。这里使用的算法属于一种特殊的类型，他们属于一种特殊的类型，它们属于贪心算法且从特定技术角度来说是在线算法，重点讨论在线广告的相关问题、在线算法、

3、Adwords实现和问题等。,二部图,最大匹配,完美匹配,最大匹配的贪心算法,贪心匹配算法的竞争率为1/2,01,02,03,04,05,推荐系统,9,Part,Recommendation Systems,举例1，在淘宝上多次浏览某类商品时，淘宝网站会出现该类产品的推荐，诸如：您可能感兴趣。 举例2，某些门户网站会基于您的浏览足迹，推荐您感兴趣的新闻内容。 没错，这就是推荐系统的巨大魅力，大数据环境之下，Web应用可以对涉及用户喜好进行预测，而这种系统称为推荐系统。,不知道大家有没有这样的经验，反正我是经常碰到。,这类系统通过计算用户或/和项之间的相似度来推荐项。与某用户相似的用户所喜欢的项

4、会推荐给该用户。,这类系统主要考察的是推荐项的性质。用户计算机用户以往的浏览历史来预测用户将来的行为，也就是基于内容的推荐。,推荐系统,基于内容的系统,协同过滤系统,基于内容的推荐（Content-based Recommendation）是信息过滤技术的延续与发展，它是建立在项目的内容信息上作出推荐的，而不需要依据用户对项目的评价意见，更多地需要用机器学习的方法从关于内容的特征描述的事例中得到用户的兴趣资料。在基于内容的推荐系统中，项目或对象是通过相关的特征的属性来定义，系统基于用户评价对象的特征，学习用户的兴趣，考察用户资料与待预测项目的相匹配程度。用户的资料模型取决于所用学习方法，常用的

5、有决策树、神经网络和基于向量的表示方法等。基于内容的用户资料是需要有用户的历史数据，用户资料模型可能随着用户的偏好改变而发生变化。,不需要其它用户的数据，没有冷开始问题和稀疏,能为具有特殊兴趣爱好的用户进行推荐,能推荐新的或不是很流行的项目，没有新项目问题,通过流出推荐项目内容特征，解释推荐那些项目的原因,已有比较好的技术，如关于分类学习的技术已趋成熟,优点,缺点是要求内容能容易抽取成有意义的特征，要求特征内容有良好的结构性，并且用户的口味必须能够用内容特征形式来表达，不能显式地得到其它用户的判断情况。,分析 数据,输出 结果,过滤 数据,数据 收集,利用分类聚类技术分析出这些日志数据之间的关

6、联性，以及这些日志数据和用户之间的关联性，这也是最重要的一步。,Web日志中有很多无用的信息，我们要把这些无用的信息排除掉，而且要区分出用户和日志数据之间的联系。,即搜集用户的行为资料，其中也包括很多方法，根据我找到的资料与以往的经验来看，web日志可以作为我们的切入点，即我们的数据来源。,基于用户的协同过滤推荐的基本原理是，根据所有用户对物品或者信息的偏好，发现与当前用户口味和偏好相似的“邻居”用户群，在一般的应用中是采用计算“K- 邻居”的算法；然后，基于这 K 个邻居的历史偏好信息，为当前用户进行推荐。,上图示意出基于用户的协同过滤推荐机制的基本原理，假设用户 A 喜欢物品 A，物品 C，用户 B 喜欢物品 B，用户 C 喜欢物品 A ，物品 C 和物品 D；从这些用户