大数据挖掘背景及工具
– 目标是创建一些可伸缩的数据挖掘算法,供开发人 员在 Apache 在许可下免费使用。 – Mahout 包含许多实现,包括集群、分类、CF 和进 化程序。 – 此外,通过使用 Apache Hadoop 库,Mahout 可以有 效地扩展到云中。
背景知识
• Mahout的意思是大象的饲养者及驱赶者。
• 图示为文章用词中的幂律关系
– 也称为长尾效应
多处数据都满足幂律
• • • • 1) Web图当中节点的度 2) 商品的销量 3) Web网站的大小 4) Zipf定律
大数据挖掘工具Mahout
• Mahout 是 Apache Software Foundation (ASF) 开发的一个开源项目
2) 相似项
• 有时数据看上去像一系列集合,这时的目 标是,寻找那些共同元素比例较高的集合 对。
– 由于顾客大都对许多不同的商品感兴趣,寻 找兴趣相似的那部分顾客,并根据这些关联 对数据进行表示的做法会更有用。 – 为向顾客推荐感兴趣的商品,Amazon先寻找 与他相似的顾客群,并把其中大部分人购买 过的商品也推荐给他,该过程称为协同过滤
– Mahout 这个名称来源于Hadoop徽标上的大象 – Mahout利用Hadoop来实现可伸缩性和容错性。
Mahout 的历史
• Mahout 项目是由 Apache Lucene(开源搜索)社区 中,对数据挖掘感兴趣的一些成员发起的
– 希望建立一个可靠、文档翔实、可伸缩的项目,在 其中实现一些常见的,用于集群和分类的数据挖掘 算法。 – 此后在发展中,又并入了更多广泛的数据挖掘方法
分类
• 分类技术用于决定一个事物,是不是属于一 种类型、类目,或者该事物是不是含有某些 属性。
– 分类有助于判断一个新进入事物,是否匹配先前 发现的模式, 也常用于分类行为或者模式。 – 分类也可用来检测可疑的网络活动或欺诈。也可 根据用户发的信息,判定表示失望或者满意
应用实例
• Yahoo! :Mail决定接收的信息是不是垃圾邮件 ,基于先前邮件和用户的垃圾邮件报告,以及 邮件的特性。一些信息被分类为垃圾邮件
– MapReduce 的随机决策实现,它提供了分类、 关联规则、用于识别文档主题的 Latent Dirichlet Allocation – 以及许多使用 HBase ,和其他辅助存储选项的 类别选项。
Mahout与Hadoop家族 其他主要成员关系
Mahout的基础
• Mahout提供了分布式的挖掘环境,具体讲: 1 基于AFS Hadoop集群 2 采用DFS分布式文件系统 3 利用MapReduce 计算模型 4 实现了一批开源的挖掘方法
使用 Mahout 创建数据集群
• 具体的步骤包括:
– 1.准备输入。如果创建文本集群,需要 将文本转换成数值表示。 – 2.使用 Mahout 中可用的 Hadoop 就绪的 驱动程序运行所选集群算法。 – 3.计算结果。 – 4.如果有必要,执行迭代。
Mahout的发展
• Apache Mahout 为集群、分类和 CF(协同过滤) 提供了许多重要的功能,但它还存在很大的 发展空间。
数据挖掘是数据模型的发现过程
• 数据挖掘(data mining)是数据"模型"的发 现过程,而"模型"却可以有多种含义。 • 下面介绍在建模方面最重要的几个方向
擅长的典型场景
• 数据挖掘擅长的,是当人们对数据中的 寻找目标,几乎一无所知。
– 比如,并不清楚到底是影片的什么因素, 导致某些观众喜欢或者厌恶该影片。 – 因此,在Netflix竞赛要求设计一个算法, 来预测观众对影片的评分时,基于已有评 分样本的数据挖掘算法获得了巨大成功。
建模的计算方法
• 数据建模有很多不同的方法。 • 数据可以通过,其生成所可能遵从的, 统计过程构建来建模。
数据建模两种做法
• 数据建模方法,可描述为下列两种做法 之一:
– 1)对数据进行简洁的近似汇总描述; – 2)从数据中抽取出最突出的特征,代替数 据,并忽略剩余内容
数据汇总
• 一种数据汇总形式是PageRank,谷歌成功 的关键算法
应用实例
• 是最出名的使用推荐系统商务网站。 基于交易和网页活性,Amazon推荐给用户可能感 兴趣的书籍和其他item。 • Netflix类似于推荐用户感兴趣的DVDs,并且为研 究者提供百万大奖去提升推荐质量。 • 约会网站像Líbímseti将一部分用户推荐给其他用 户。 • 社交网络网站像Facebook,用推荐技术的变形来 为用户识别最可能建立联系的朋友
• 数据挖掘是一类深层次的数据分析方法。
– 数据挖掘可以描述为:按既定决策目标,对大 量的数据进行探索和分析,揭示隐藏的、未知 的或验证已知的规律性,并进一步将其模型化 的先进有效的方法。
数据、信息与知识
客观世界
收集 数据
分析
信息
再 分 析
知识
指导
经典挖掘模型CRISP-DM
商业理解 结果部署 数据 建立模型 模型评估 数据理解
– 1) 频繁项集(frequent itemset) – 2) 相似项(similar item)
1) 频繁项集
• 该模型适用于多个项集组成的数据,其 原始应用发生在真实的购物篮场景下:
– 在超市结账的时候,某些物品会被顾客同 时购买,例如热狗和芥末,这些物品组成 了项集 – 寻找那些在很多购物篮中,同时出现的项 集(频繁项集),这就是要找的,用以刻 画数据的特征。
使用 Mahout 实现集群算法
• Mahout 支持一些集群算法实现(都是使用 MapReduce 编写的),它们都有一组各自的目标和 标准 • 以聚类为例,其提供了:
• Canopy:一种快速集群算法,通常用于为其他集群算 法创建初始种子。 • K-Means(以及 模糊 K-Means):根据项目与之前迭代 的质心(或中心)之间的距离将项目添加到 k 集群中。 • Mean-Shift:无需任何关于集群数量的 推理知识的算法 ,它可以生成任意形状的集群。 • Dirichlet:借助基于多种概率模型的集群,它不需要提 前执行特定的集群视图。
1
Part 1大数据挖掘及其背景 应用于大数据处理
• 杨文川
2
1) 大数据挖掘 2) 数据模型的发现 3) 大数据挖掘知识点 4) Mahout及其应用
量化一切、利用所有的数据
大数据挖掘的基础 在数字化时代,获取数据正变得比以往 任何时候都简单而不受限制
文字、方位、社交关系等都变成了数据
发现数据间的隐含信息
大数据挖掘
大数据挖掘的核心动力来源于人类了 解和分析世界的渴望。
之前信息技术变革的重点在"T"(技术)上,而不 是在"I"(信息)上。
现代信息系统让大数据成为了可能, 人们更多的关注信息"I"本身。
传统的数据挖掘
• 数据挖掘(Data Mining),又称知识发现 (KDD)
– 是一个从大量数据中提取、挖掘出未知的、有 价值的模式或规律等知识的复杂过程。
大数据挖掘知识点
• 对数据挖掘研究有益的一些知识
– (1)用于度量词语重要性的TF.IDF指标 – (2)哈希函数及其使用 – (3)二级存储器(磁盘)及其对算法运行时间 的影响; – (4)自然对数的底e及包含它的一系列恒等式 – (5)幂定律(power law)
TF.IDF
• 假定文档集中有N篇文档,fij为词项i在 文档j中出现的频率(即次数),词项i在文 档j中的词项频率TFij定义为 fij TFij = max k f kj • 假定词项i在文档集的ni篇文档中出现, N 那么词项i的IDF定义 IDFi = log 2 ni • 具有最高TF.IDF得分的那些词项,通常 都是刻画文档主题的最佳词项
聚类
• 聚类技术尝试将大量拥有相同相似度的 事物,聚集到不同的类中。
– 聚类有助于在海量的、很难弄懂的事物集合中, 发现结构,甚至层次。 – 可以使用聚类,根据网站日志发现用户的经常使 用模式
应用实例
• Google News可根据具备逻辑性的故事,使用新 闻文章的Topic聚集新闻,而不是文章的列表。 – 搜索引擎(像Clusty)基于相同的方法,聚集搜 索结果。 • 使用聚类技术,基于消费者属性,收入、位置 、购买习惯,可将不用用户分到不用的类中
Mahout 核心挖掘算法
• Mahout孵化了相当多的技术和算法, 很多都是在开发和实验阶段。 • 有3个核心主题:
– 协同过滤/推荐系统、聚类和分类。
推荐系统
• 推荐系统是目前使用的系统中最普及的
– 相关的服务或网页,包括基于历史行为推荐书、 电影、文档。 – 尝试推论出用户偏好,并标记出用户不知晓的、 感兴趣的item
• Picasa (/)和其他的照片 管理应用可以判断一张照片中是否含有人脸。 • 光学字符识别软件:通过将小区域作为独立字 符来分类,将扫描文本的若干小区域归类到独 立的字符上
42
谢 谢
数据准备
数据挖掘三阶段
数据准备 数据挖掘 结果评价 结果表达和解释 数据挖掘 数据转换 预处理 数据选择 数据集成 目标数据 数据 数据源 预处理后 转换数据 数据 模式 知识
常用的数据挖掘方法
关联规则 聚类分析 分类技术 时序模式 偏差检测 预测估计 …….
传统的数据挖掘软件
• 专用挖掘工具、通用挖掘工具
正态分布
• 假定现有的数据是一系列数字。
– 统计学家可能会判定这些数字,来自一个 高斯分布(即正态分布),并利用公式来计算 该分布最有可能的参数值。 – 该高斯分布的均值和标准差,能够完整地 刻画整个分布,因而成为上述数据的一个 模型
幂律分布