Ji ZHANG's Blog

If I rest, I rust.

数据挖掘指南[8]聚类

原文:http://guidetodatamining.com/chapter-8/

前几章我们学习了如何构建分类系统,使用的是已经标记好类别的数据集进行训练:

训练完成后我们就可以用来预测了:这个人看起来像是篮球运动员,那个人可能是练体操的;这个人三年内不会患有糖尿病。

可以看到,分类器在训练阶段就已经知道各个类别的名称了。那如果我们不知道呢?如何构建一个能够自动对数据进行分组的系统?比如有1000人,每人有20个特征,我想把这些人分为若干个组。

这个过程叫做聚类:通过物品特征来计算距离,并自动分类到不同的群集或组中。有两种聚类算法比较常用:

k-means聚类算法

我们会事先告诉这个算法要将数据分成几个组,比如“请把这1000个人分成5个组”,“将这些网页分成15个组”。这种方法就叫k-means,我们会在后面的章节讨论。

层次聚类法

对于层次聚类法,我们不需要预先指定分类的数量,这个算方法会将每条数据都当作是一个分类,每次迭代的时候合并距离最近的两个分类,直到剩下一个分类为止。因此聚类的结果是:顶层有一个大分类,这个分类下有两个子分类,每个子分类下又有两个子分类,依此类推,层次聚类也因此得命。

在合并的时候我们会计算两个分类之间的距离,可以采用不同的方法。如下图中的A、B、C三个分类,我们应该将哪两个分类合并起来呢?

前往GitHub阅读全文

深入理解Reduce-side Join

在《MapReduce Design Patterns》一书中,作者给出了Reduce-side Join的实现方法,大致步骤如下:

  1. 使用MultipleInputs指定不同的来源表和相应的Mapper类;
  2. Mapper输出的Key为Join的字段内容,Value为打了来源表标签的记录;
  3. Reducer在接收到同一个Key的记录后,执行以下两步:
    1. 遍历Values,根据标签将来源表的记录分别放到两个List中;
    2. 遍历两个List,输出Join结果。

具体实现可以参考这段代码。但是这种实现方法有一个问题:如果同一个Key的记录数过多,存放在List中就会占用很多内存,严重的会造成内存溢出(Out of Memory, OOM)。这种方法在一对一的情况下没有问题,而一对多、多对多的情况就会有隐患。那么,Hive在做Reduce-side Join时是如何避免OOM的呢?两个关键点:

  1. Reducer在遍历Values时,会将前面的表缓存在内存中,对于最后一张表则边扫描边输出;
  2. 如果前面几张表内存中放不下,就写入磁盘。

数据挖掘指南[7]朴素贝叶斯和文本数据

原文:http://guidetodatamining.com/chapter-7/

非结构化文本的分类算法

在前几个章节中,我们学习了如何使用人们对物品的评价(五星、顶和踩)来进行推荐;还使用了他们的隐式评价——买过什么,点击过什么;我们利用特征来进行分类,如身高、体重、对法案的投票等。这些数据有一个共性——能用表格来展现:

因此这类数据我们称为“结构化数据”——数据集中的每条数据(上表中的一行)由多个特征进行描述(上表中的列)。而非结构化的数据指的是诸如电子邮件文本、推特信息、博客、新闻等。这些数据至少第一眼看起来是无法用一张表格来展现的。

举个例子,我们想从推特信息中获取用户对各种电影的评价:

可以看到,Andy Gavin喜欢看地心引力,因为他的消息中有“不寒而栗”、“演的太棒了”之类的文本。而Debra Murphy则不太喜欢这部电影,因为她说“还是省下看这部电影的钱吧”。如果有人说“我太想看这部电影了,都兴奋坏了!”,我们可以看出她是喜欢这部电影的,即使信息中有“坏”这个字。

我在逛超市时看到一种叫Chobani的酸奶,名字挺有趣的,但真的好吃吗?于是我掏出iPhone,谷歌了一把,看到一篇名为“女人不能只吃面包”的博客:

无糖酸奶品评

你喝过Chobani酸奶吗?如果没有,就赶紧拿起钥匙出门去买吧!虽然它是脱脂原味的,但喝起来和酸奶的口感很像,致使我每次喝都有负罪感,因为这分明就是在喝全脂酸奶啊!原味的感觉很酸很够味,你也可以尝试一下蜂蜜口味的。我承认,虽然我在减肥期间不该吃蜂蜜的,但如果我有一天心情很糟想吃甜食,我就会在原味酸奶里舀一勺蜂蜜,太值得了!至于那些水果味的,应该都有糖分在里面,但其实酸奶本身就已经很美味了,水果只是点缀。如果你家附近没有Chobani,也可以试试Fage,同样好吃。

虽然需要花上一美元不到,而且还会增加20卡路里,但还是很值得的,毕竟我已经一下午没吃东西了!

来源:http://womandoesnotliveonbreadalone.blogspot.com/2009/03/sugar-free-yogurt-reviews.html

这是一篇正面评价吗?从第二句就可以看出,作者非常鼓励我去买。她还用了“够味”、“美味”等词汇,这些都是正面的评价。所以,让我先去吃会儿……

前往GitHub阅读全文

使用git Rebase让历史变得清晰

当多人协作开发一个分支时,历史记录通常如下方左图所示,比较凌乱。如果希望能像右图那样呈线性提交,就需要学习git rebase的用法。

“Merge branch”提交的产生

我们的工作流程是:修改代码→提交到本地仓库→拉取远程改动→推送。正是在git pull这一步产生的Merge branch提交。事实上,git pull等效于get fetch origin和get merge origin/master这两条命令,前者是拉取远程仓库到本地临时库,后者是将临时库中的改动合并到本地分支中。

要避免Merge branch提交也有一个“土法”:先pull、再commit、最后push。不过万一commit和push之间远程又发生了改动,还需要再pull一次,就又会产生Merge branch提交。

使用git pull —rebase

修改代码→commit→git pull —rebase→git push。也就是将get merge origin/master替换成了git rebase origin/master,它的过程是先将HEAD指向origin/master,然后逐一应用本地的修改,这样就不会产生Merge branch提交了。具体过程见下文扩展阅读。

数据挖掘指南[6]概率和朴素贝叶斯

原文:http://guidetodatamining.com/chapter-6

朴素贝叶斯

还是让我们回到运动员的例子。如果我问你Brittney Griner的运动项目是什么,她有6尺8寸高,207磅重,你会说“篮球”;我再问你对此分类的准确度有多少信心,你会回答“非常有信心”。

我再问你Heather Zurich,6尺1寸高,重176磅,你可能就不能确定地说她是打篮球的了,至少不会像之前判定Brittney那样肯定。因为从Heather的身高体重来看她也有可能是跑马拉松的。

最后,我再问你Yumiko Hara的运动项目,她5尺4寸高,95磅重,你也许会说她是跳体操的,但也不太敢肯定,因为有些马拉松运动员也是类似的身高体重。

使用近邻算法时,我们很难对分类结果的置信度进行量化。但如果使用的是基于概率的分类算法——贝叶斯算法——那就可以给出分类结果的可能性了:这名运动员有80%的几率是篮球运动员;这位病人有40%的几率患有糖尿病;拉斯克鲁塞斯24小时内有雨的概率是10%。

近邻算法又称为被动学习算法。这种算法只是将训练集的数据保存起来,在收到测试数据时才会进行计算。如果我们有10万首音乐,那每进行一次分类,都需要遍历这10万条记录才行。

贝叶斯算法则是一种主动学习算法。它会根据训练集构建起一个模型,并用这个模型来对新的记录进行分类,因此速度会快很多。

所以说,贝叶斯算法的两个优点即:能够给出分类结果的置信度;以及它是一种主动学习算法。

前往GitHub阅读全文

Spark快速入门

Apache Spark是新兴的一种快速通用的大规模数据处理引擎。它的优势有三个方面:

  • 通用计算引擎 能够运行MapReduce、数据挖掘、图运算、流式计算、SQL等多种框架;
  • 基于内存 数据可缓存在内存中,特别适用于需要迭代多次运算的场景;
  • 与Hadoop集成 能够直接读写HDFS中的数据,并能运行在YARN之上。

Spark是用Scala语言编写的,所提供的API也很好地利用了这门语言的特性。它也可以使用Java和Python编写应用。本文将用Scala进行讲解。

安装Spark和SBT

  • 官网上下载编译好的压缩包,解压到一个文件夹中。下载时需注意对应的Hadoop版本,如要读写CDH4 HDFS中的数据,则应下载Pre-built for CDH4这个版本。
  • 为了方便起见,可以将spark/bin添加到$PATH环境变量中:
1
2
export SPARK_HOME=/path/to/spark
export PATH=$PATH:$SPARK_HOME/bin
  • 在练习例子时,我们还会用到SBT这个工具,它是用来编译打包Scala项目的。Linux下的安装过程比较简单:
    • 下载sbt-launch.jar到$HOME/bin目录;
    • 新建$HOME/bin/sbt文件,权限设置为755,内容如下:
1
2
SBT_OPTS="-Xms512M -Xmx1536M -Xss1M -XX:+CMSClassUnloadingEnabled -XX:MaxPermSize=256M"
java $SBT_OPTS -jar `dirname $0`/sbt-launch.jar "$@"

数据挖掘指南[5]进一步探索分类

原文:http://guidetodatamining.com/chapter-5

效果评估算法和kNN

让我们回到上一章中运动项目的例子。

在那个例子中,我们编写了一个分类器程序,通过运动员的身高和体重来判断她参与的运动项目——体操、田径、篮球等。

上图中的Marissa Coleman,身高6尺1寸,重160磅,我们的分类器可以正确的进行预测:

1
2
3
>>> cl = Classifier('athletesTrainingSet.txt')
>>> cl.classify([73, 160])
'Basketball'

对于身高4尺9寸,90磅重的人:

1
2
>>> cl.classify([59, 90])
'Gymnastics'

当我们构建完一个分类器后,应该问以下问题:

  • 分类器的准确度如何?
  • 结果理想吗?
  • 如何与其它分类器做比较?

前往GitHub阅读全文

离线环境下构建sbt项目

在公司网络中使用sbtMaven等项目构建工具时,我们通常会搭建一个公用的Nexus镜像服务,原因有以下几个:

  • 避免重复下载依赖,节省公司带宽;
  • 国内网络环境不理想,下载速度慢;
  • IDC服务器没有外网访问权限;
  • 用于发布内部模块。

sbt的依赖管理基于Ivy,虽然它能直接使用Maven中央仓库中的Jar包,在配置时还是有一些注意事项的。

数据挖掘指南[4]分类

原文:http://guidetodatamining.com/chapter-4

在上几章中我们使用用户对物品的评价来进行推荐,这一章我们将使用物品本身的特征来进行推荐。这也是潘多拉音乐站所使用的方法。

内容:

  • 潘多拉推荐系统简介
  • 特征值选择的重要性
  • 示例:音乐特征值和邻域算法
  • 数据标准化
  • 修正的标准分数
  • Python代码:音乐,特征,以及简单的邻域算法实现
  • 一个和体育相关的示例
  • 特征值抽取方式一览

根据物品特征进行分类

前几章我们讨论了如何使用协同过滤来进行推荐,由于使用的是用户产生的各种数据,因此又称为社会化过滤算法。比如你购买了Phoenix专辑,我们网站上其他购买过这张专辑的用户还会去购买Vampire的专辑,因此会把它推荐给你;我在Netflix上观看了Doctor Who,网站会向我推荐Quantum Leap,用的是同样的原理。我们同时也讨论了协同过滤会遇到的种种问题,包括数据的稀疏性和算法的可扩展性。此外,协同过滤算法倾向于推荐那些已经很流行的物品。试想一个极端的例子:一个新乐队发布了专辑,这张专辑还没有被任何用户评价或购买过,那它将永远不会出现在推荐列表中。

这类推荐系统会让流行的物品更为流行,冷门的物品更无人问津。

— Daniel Fleder & Kartik Hosanagar 2009 《推荐系统对商品分类的影响》

这一章我们来看另一种推荐方法。以潘多拉音乐站举例,在这个站点上你可以设立各种音乐频道,只需为这个频道添加一个歌手,潘多拉就会播放和这个歌手风格相类似的歌曲。比如我添加了Phoenix乐队,潘多拉便会播放El Ten Eleven的歌曲。它并没有使用协同过滤,而是通过计算得到这两个歌手的音乐风格是相似的。其实在播放界面上可以看到推荐理由:

“根据你目前告知的信息,我们播放的这首歌曲有着相似的旋律,使用了声响和电音的组合,即兴的吉他伴奏。”在我的Hiromi音乐站上,潘多拉会播放E.S.T.的歌曲,因为“它有着古典爵士乐风,一段高水准的钢琴独奏,轻盈的打击乐,以及有趣的歌曲结构。”

潘多拉网站的推荐系统是基于一个名为音乐基因的项目。他们雇佣了专业的音乐家对歌曲进行分类(提取它们的“基因”)。这些音乐家会接受超过150小时的训练,之后便可用20到30分钟的时间来分析一首歌曲。这些乐曲特征是很专业的:

这些专家要甄别400多种特征,平均每个月会有15000首新歌曲,因此这是一项非常消耗人力的工程。

注意:潘多拉的音乐基因项目是商业机密,我不曾了解它的任何信息。下文讲述的是如何构造一个类似的系统。

前往GitHub阅读全文

MySQL异常UTF-8字符的处理

ETL流程中,我们会将Hive中的数据导入MySQL——先用Hive命令行将数据保存为文本文件,然后用MySQL的LOAD DATA语句进行加载。最近有一张表在加载到MySQL时会报以下错误:

1
Incorrect string value: '\xF0\x9D\x8C\x86' for column ...

经查,这个字段中保存的是用户聊天记录,因此会有一些表情符号。这些符号在UTF-8编码下需要使用4个字节来记录,而MySQL中的utf8编码只支持3个字节,因此无法导入。

根据UTF-8的编码规范,3个字节支持的Unicode字符范围是U+0000–U+FFFF,因此可以在Hive中对数据做一下清洗:

1
SELECT REGEXP_REPLACE(content, '[^\\u0000-\\uFFFF]', '') FROM ...

这样就能排除那些需要使用3个以上字节来记录的字符了,从而成功导入MySQL。

以下是一些详细说明和参考资料。