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

Mining of Massive Datasets Mining of Massive Datasets 大数据：互联网大规模数据挖掘与分布式处理大数据：互联网大规模数据挖掘与分布式处理聚类聚类7PartClustering聚类是对点集进行考察并按照某种距离测度将它们聚成多个“簇”的过程。聚类的目标是同一簇内的点之间的距离较短，而不同簇中点之间的距离较大。如图，不同种类的犬在某种程度上形成一种簇。三种不同犬类的身高体重分布图，可以知道这些犬可以分到三个簇中，每个簇恰好对应一种犬类。身高吉娃娃狗体重腊肠狗比格犬xyz 0而聚类分析则是根据最大化簇内的相似性、最小化簇间的相似性的原则将数据对象聚类或分组，所形成的每个簇可以看作一个数据对象类，用显式或隐式的方法描述它们。最大化簇内的相似性最小化簇间的相似性聚类算法基于划分的基于划分的K-meansK-medoids基于层次的基于层次的凝聚的凝聚的分裂的分裂的基于密度的基于密度的DBSCANOPTICS基于网格的基于网格的STINGCLIQUE基于模型的基于模型的StatisticsNeural Network010102020303040405050606能够适用于大数据量能够适用于大数据量（可伸缩性）（可伸缩性）能够处理不同类型数据能够处理不同类型数据（距离定义）（距离定义）能够发现任意形状的簇能够发现任意形状的簇（结果特点）（结果特点）能够处理高维数据能够处理高维数据具有处理噪声的能力具有处理噪声的能力聚类结果可解易使用聚类结果可解易使用WebWeb广告广告8PartAdvertising on the Web 目前，许多WEB应用通过广告而维持生计，从在线广告中获益最多的是搜索应用，而搜索广告的有效性主要源于将搜索查询和广告进行匹配的一个称为Adwords模型。 本章将主要关注广告匹配的优化算法。这里使用的算法属于一种特殊的类型，他们属于一种特殊的类型，它们属于贪心算法且从特定技术角度来说是在线算法，重点讨论在线广告的相关问题、在线算法、Adwords实现和问题等。Web广告广告Adwords实实现现投标和搜索查投标和搜索查询的匹配询的匹配更复杂问题的更复杂问题的匹配问题匹配问题文档和投标之文档和投标之间的匹配算法间的匹配算法Adwords问问题题搜索广告的历搜索广告的历史史Adwords问题问题的定义的定义Adwords问题问题的贪心算法的贪心算法Balance算法算法Balance算法算法竞争的一个下竞争的一个下界界多投标者的多投标者的Balance算法算法一般性的一般性的Balance算法算法Adwords问题问题的最后论述的最后论述在线广告在线广告相关问题相关问题广告机会广告机会直接广告直接广告展示广告的相展示广告的相关问题关问题在线算法在线算法在线和离线算在线和离线算法法贪心算法贪心算法竞争率竞争率广告匹配广告匹配问题问题匹配及完美匹匹配及完美匹配配最大匹配贪心最大匹配贪心算法算法贪心匹配算法贪心匹配算法的竞争率的竞争率1离线算法离线算法 将算法所需的所有数据准备好才产生答案的传统算法将算法所需的所有数据准备好才产生答案的传统算法在线算法在线算法只能保存有限的流数据，但是需要在某个流元素到达之后只能保存有限的流数据，但是需要在某个流元素到达之后就以输出的方式对查询进行应答，此时是在对未来的数据就以输出的方式对查询进行应答，此时是在对未来的数据一无所知的情况下对当前元素进行决策的过程一无所知的情况下对当前元素进行决策的过程2算法现象算法现象一般情况下会寻找搜索引擎收益和广告上显示次数同时的一般情况下会寻找搜索引擎收益和广告上显示次数同时的最大化，因为无法保证在线算法与离线算法一样有效最大化，因为无法保证在线算法与离线算法一样有效3贪心算法贪心算法采用贪心策略，综合考虑关键词与广告的匹配程度、广告采用贪心策略，综合考虑关键词与广告的匹配程度、广告商竞价、广告商剩余预算等因素，通过最大化当前输入元商竞价、广告商剩余预算等因素，通过最大化当前输入元素信息的某个函数得到当前的最优值。素信息的某个函数得到当前的最优值。4竞争率竞争率存在某个小于存在某个小于1的常数的常数c,使得对于任意输入，一个具体的在使得对于任意输入，一个具体的在线算法的结果至少是最优离线算法结果的线算法的结果至少是最优离线算法结果的c倍。倍。1 1二部图二部图设设G=(G=(V,EV,E）是一个无向图，如果顶点）是一个无向图，如果顶点V V可分割为两个互不相交的子集可分割为两个互不相交的子集( (A,BA,B），并且），并且图中的每条边（图中的每条边（i i，j j）所关联的两个顶点）所关联的两个顶点i i和和j j分别属于这两个不同的顶点集，则称分别属于这两个不同的顶点集，则称图图G G为一个二分图。为一个二分图。2 2最大匹配最大匹配一个二分图一个二分图G G，在，在G G的一个子图的一个子图M M中，中，M M的边集中的任意两条边都不依附于同一个顶点，的边集中的任意两条边都不依附于同一个顶点，选择这样的边数最大的子集称为图的最大匹配问题。选择这样的边数最大的子集称为图的最大匹配问题。3 3完美匹配完美匹配在一个匹配中，所有的节点都不会同时是两条或者多条边对的端点且所有的节点都在一个匹配中，所有的节点都不会同时是两条或者多条边对的端点且所有的节点都出现，则匹配是完美的。出现，则匹配是完美的。4 4最大匹配的贪最大匹配的贪心算法心算法按照任意次序来考虑边，当考虑边（按照任意次序来考虑边，当考虑边（x,yx,y）时，如果）时，如果x x和和y y都不是已有匹配中边的端都不是已有匹配中边的端点则加入，否则跳过。贪心算法产生的匹配不一定是最大匹配，很可能结果会不尽点则加入，否则跳过。贪心算法产生的匹配不一定是最大匹配，很可能结果会不尽人意。人意。5 5贪心匹配算法贪心匹配算法的竞争率为的竞争率为1/21/2。因为算法的竞争率是算法所有可能的输入下所得到最小值和最优结果的比值，因此因为算法的竞争率是算法所有可能的输入下所得到最小值和最优结果的比值，因此1/21/2是竞争率的上界。又设是竞争率的上界。又设MoMo是最大匹配、是最大匹配、MgMg是贪心算法匹配，是贪心算法匹配，L L为在为在MoMo中匹配但在中匹配但在MgMg中不匹配的左节点结合，中不匹配的左节点结合，R R为为L L中所有节点连接的边右节点的集合。由于中所有节点连接的边右节点的集合。由于| |M0M0|=|=|M0M0|+|L| ,|L|=|R|+|L| ,|L|=|R|，|R|=|Mg| |R|=|Mg| ，可以推导得到，可以推导得到| |M0M0|=|=2|Mg2|Mg| |，竞争率至，竞争率至少为少为1/21/2。因此竞争率为。因此竞争率为1/21/2。二部图最大匹配完美匹配最大匹配的贪心算法贪心匹配算法的竞争率为1/20102030405推荐系统推荐系统9PartRecommendation Systems举例1，在淘宝上多次浏览某类商品时，淘宝网站会出现该类产品的推荐，诸如：您可能感兴趣。举例2，某些门户网站会基于您的浏览足迹，推荐您感兴趣的新闻内容。没错，这就是推荐系统的巨大魅力，大数据环境之下，Web应用可以对涉及用户喜好进行预测，而这种系统称为推荐系统。不知道大家有没有这样的经验，反正我是经常碰到。这类系统通过计算用户或/和项之间的相似度来推荐项。与某用户相似的用户所喜欢的项会推荐给该用户。这类系统主要考察的是推荐项的性质。用户计算机用户以往的浏览历史来预测用户将来的行为，也就是基于内容的推荐。推荐系统推荐系统基于内容的系统 协同过滤系统基于内容的推荐（Content-based Recommendation）是信息过滤技术的延续与发展，它是建立在项目的内容信息上作出推荐的，而不需要依据用户对项目的评价意见，更多地需要用机器学习的方法从关于内容的特征描述的事例中得到用户的兴趣资料。在基于内容的推荐系统中，项目或对象是通过相关的特征的属性来定义，系统基于用户评价对象的特征，学习用户的兴趣，考察用户资料与待预测项目的相匹配程度。用户的资料模型取决于所用学习方法，常用的有决策树、神经网络和基于向量的表示方法等。基于内容的用户资料是需要有用户的历史数据，用户资料模型可能随着用户的偏好改变而发生变化。不不需要其它用户的数据，没有冷开始问题和稀疏需要其它用户的数据，没有冷开始问题和稀疏能为具有特殊兴趣爱好的用户进行推荐能为具有特殊兴趣爱好的用户进行推荐能推荐新的或不是很流行的项目，没有新项目问题能推荐新的或不是很流行的项目，没有新项目问题通过流出推荐项目内容特征，解释推荐那些项目的原因通过流出推荐项目内容特征，解释推荐那些项目的原因已有比较好的技术，如关于分类学习的技术已趋成熟已有比较好的技术，如关于分类学习的技术已趋成熟优点优点缺点缺点是是要求内容能容易抽取成有意义要求内容能容易抽取成有意义的特征，的特征，要求特征内容有要求特征内容有良好的结构性良好的结构性，并且用户并且用户的的口味必须能够用内容特征形式来表达，不能口味必须能够用内容特征形式来表达，不能显式地得到其它用户的判断情况显式地得到其它用户的判断情况。分析分析数据数据输出输出结果结果过滤过滤数据数据数据数据收集收集利用分类聚类技术分析出这些日志数据之间的关联性，以及这利用分类聚类技术分析出这些日志数据之间的关联性，以及这些日志数据和用户之间的关联性，这也是最重要的一步。些日志数据和用户之间的关联性，这也是最重要的一步。Web日志中有很多无用的信息，我们要把这些无用的日志中有很多无用的信息，我们要把这些无用的信息排除掉，而且要区分出用户和日志数据之间的联信息排除掉，而且要区分出用户和日志数据之间的联系。系。即搜集用户的行为资料，其中也包括很多方法，根据我找到即搜集用户的行为资料，其中也包括很多方法，根据我找到的资料与以往的经验来看，的资料与以往的经验来看，web日志可以作为我们的切入点，日志可以作为我们的切入点，即我们的数据来源。即我们的数据来源。基于基于用户的协同过滤推荐的基本原理是，根据所有用户对物品或用户的协同过滤推荐的基本原理是，根据所有用户对物品或者信息的偏好，发现与当前用户口味和偏好相似的者信息的偏好，发现与当前用户口味和偏好相似的“邻居邻居”用户用户群，在一般的应用中是采用计算群，在一般的应用中是采用计算“K- 邻居邻居”的算法；然后，基的算法；然后，基于这于这 K 个邻居的历史偏好信息，为当前用户进行推荐个邻居的历史偏好信息，为当前用户进行推荐。上图示意出基于用户的协同过滤推荐机制的上图示意出基于用户的协同过滤推荐机制的基本原理，假设用户基本原理，假设用户 A 喜欢物品喜欢物品 A，物品，物品 C，用户用户 B 喜欢物品喜欢物品 B，用户，用户 C 喜欢物品喜欢物品 A ，物品物品 C 和物品和物品 D；从这些用户的历史喜好信；从这些用户的历史喜好信息中，我们可以发现用户息中，我们可以发现用户 A 和用户和用户 C 的口的口味和偏好是比较类似的，同时用户味和偏好是比较类似的，同时用户 C 还喜欢还喜欢物品物品 D，那么我们可以推断用户，那么我们可以推断用户 A 可能也喜可能也喜欢物品欢物品 D，因此可以将物品，因此可以将物品 D 推荐给用户推荐给用户 A。