1、Mining of Massive Datasets 大数据：互联网大规模数据挖掘与分布式处理聚类7PartClustering聚类 是对点集进行考察并按照某种距离测度将它们聚成多个 “簇 ”的过程。聚类的目标是同一簇内的点之间的距离较短，而不同簇中点之间的距离较大。如图，不同种类的犬在某种程度上形成一种簇。三种不同犬类的身高体重分布图，可以知道这些犬可以分到三个簇中，每个簇恰好对应一种犬类。身高吉 娃娃狗体重腊肠狗比格犬聚类的概念聚类的概念xyz0而聚类分析则是根据 最大化簇内的相似性 、 最小化簇间的相似性 的原则将数据对象聚类或分组，所形成的每个簇可以看作一个数据对象类，用显式或隐式的方
2、法描述它们。最大化簇内的相似性最小化簇间的相似性聚类的操作聚类的操作聚类算法基于划分的K-meansK-medoids基于层次的凝聚的分裂的基于密度的DBSCANOPTICS基于网格的STINGCLIQUE基于模型的StatisticsNeural Network聚类分析算法的分类聚类分析算法的分类010203040506能够适用于大数据量（可伸缩性）能够处理不同类型数据（距离定义）能够发现任意形状的簇（结果特点）能够处理高维数据具有处理噪声的能力聚类结果可解易使用聚类聚类 算法需要考虑算法需要考虑 的因素的因素Web 广告8PartAdvertising on the Web目前 ，许多 W
3、EB应用通过广告而维持 生计，从 在线广告中获益最多的是搜索应用 ，而搜索广告的有效性主要源于将搜索查询和广告进行匹配的一个称为Adwords模型。本章将主要关注广告匹配的优化算法。这里使用的算法属于一种特殊的类型，他们属于一种特殊的类型，它们属于贪心算法且从特定技术角度来说是在线算法，重点讨论在线 广告的相关问题、在线算法、 Adwords实现和问题 等。Web广告背景广告背景Web 广告Adwords实现投标和搜索查询的匹配更复杂问题的匹配问题文档和投标之间的匹配算法Adwords问题搜索广告的历史Adwords问题的定义Adwords问题的贪心算法 Balance算法Balance算法竞
4、争的一个下界多投标者的Balance算法一般性的Balance算法Adwords问题的最后论述在线广告相关问题广告机会直接广告展示广告的相关问题在线算法在线和离线算法贪心算法竞争率广告匹配问题匹配及完美匹配最大匹配贪心算法贪心匹配算法的竞争率章节具体章节具体 框架框架在线算法分类在线算法分类1 离线算法 将算法所需的所有数据准备好才产生答案的传统算法在线算法只能保存有限的流数据，但是需要在某个流元素到达之后就以输出的方式对查询进行应答，此时是在对未来的数据一无所知的情况下对当前元素进行决策的过程2 算法现象 一般情况下会寻找搜索引擎收益和广告上显示次数同时的最大化，因为无法保证在线算法与离线算法一样有效3 贪心算法采用贪心策略，综合考虑关键词与广告的匹配程度、广告商竞价、广告商剩余预算等因素，通过最大化当前输入元素信息的某个函数得到当前的最优值。4 竞争率 存在某个小于 1的常数 c,使得对于任意输入，一个具体的在线算法的结果至少是最优离线算法结果的 c倍。
