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

8
大数据:互联网大规模数据挖掘与分布式处理
Mining of Massive Datasets
7
L聚类
Cluster ing
聚类的概念
聚类是对点集进行考察并按照某
种距离测度将它们聚成多个“簇
比格犬
的过程。聚类的目标是同一簇内
的点之间的距离较短,而不同簇
中点之间的距离较大。如图,不
吉娃娃狗
同种类的犬在某种程度上形成
肠狗
种簇。三种不同犬类的身高体重
身高
分布图,可以知道这些犬可以分
到三个簇中,每个簇恰好对应
种犬类
的操作
而聚类分析则是根据最大化簇内的
最大化簇内的相似性
相似性、最小化簇间的相似性的原
则将数据对象聚类或分组,所形成
的每个簇可以看作一个数据对象类
用显式或隐式的方法描述它们。
最小化簇间的相似性
聚类算法需要考虑的因素
能够适用于大数据量
(可伸缩性)
聚类结果可解易使用
021能处理不同类型数据
(距离定义)
具有处理噪声的能力
能够发现任意形状的簇
(结果特点)
能够处理高维数据
Web广告
Advert is ing on the Web
章节具体框架
Web
在线广告
广告匹配
题
相关问题
在线算法
问题
投标和搜索查搜索广告的历d问恩广告机会在线和离线算[匹配及完美匹
询的匹配
史
的定义
更复杂问题的 Adwords问题
配问题的赏心算法
Balance算法直接广告
心算法最大匹配贪心
算法
Balance算法
的配牌法争的个下单法关问题
的竞争率
般性的Adw0rds问题
Balance算法的最后论述
在线算法分类
离线算法将算法所需的所有数据准备好才产生答案的传统算法
只能保存有限的流数据,但是需要在某个流元素到达之后
在线算法就以输出的方式对查询进行应答,此时是在对末来的数据
无所知的情况下对当前元素进行决策的过程
般情况下会寻找搜索引擎收益和广告上显示次数同时的
牌条最大化,因为无法保证在线算法与离线算法一样有效
采用贪心策略,综合考虑关键词与广告的匹配程度、广告
3贪心算法商竞价、广告商剩余预算等因素,通过最大化当前输入元
素信息的某个函数得到当前的最优值。
4克争率
在某个小于1的常数c使得对于任意输入,一个具体的在
线算法的结果至少是最优离线算法结果的c倍。