大数据

日志

Spark 大规模稀疏矩阵乘法

spark 可以通过 BlockMatrix 进行矩阵相乘，但其在大规模稀疏矩阵场景有非常严重的性能问题，本文通过基于 RDD 和 DataFrame 两种方式实现基于 spark 的大规模稀疏矩阵乘法运算。

一、矩阵乘法运算

1

二、通过 BlockMatrix 进行矩阵相乘

3 

from pyspark.mllib.linalg.distributed import *
from pyspark.sql import SparkSession

ss = SparkSession.builder.appName("test") \
    .config("spark.serializer", "org.apache.spark.serializer.KryoSerializer") \
    .getOrCreate()

sc = ss.sparkContext
sc.setLogLevel("WARN")

M_rdd = sc.parallelize([(0,0, 1), (0,1, 2), (0,2, 3), (1,0, 4), (1,1, 5), (1,2, 6)])
N_rdd = sc.parallelize([(0,0, 7), (0,1, 8), (1,0, 9), (1,1, 10), (2,0, 11), (2,1, 12)])
M = CoordinateMatrix(M_rdd).toBlockMatrix()
N = CoordinateMatrix(N_rdd).toBlockMatrix()
M.multiply(N).toCoordinateMatrix().entries.collect()

######## 输出 #############
# [MatrixEntry(0, 0, 58.0),
#  MatrixEntry(1, 0, 139.0),
#  MatrixEntry(0, 1, 64.0),
#  MatrixEntry(1, 1, 154.0)]

三、BlockMatrix 的性能问题

在 spark 的官方文档中关于 multiply 这个方法的描述如下

Left multiplies this BlockMatrix by other, another BlockMatrix. The colsPerBlock of this matrix must equal the rowsPerBlock of other. If other contains any SparseMatrix blocks, they will have to be converted to DenseMatrix blocks. The output BlockMatrix will only consist of DenseMatrix blocks. This may cause some performance issues until support for multiplying two sparse matrices is added.

也就是说，BlockMatrix 在进行矩阵乘法时会先把稀疏矩阵转换成稠密矩阵！！对于一个 10000 x 10000 的稀疏矩阵，实际存储的可能只有几万个非零元素，而转换成稠密矩阵后，你需要对所有 10000 x 10000 = 1亿 个元素提供存储空间！！而实际场景面对的稀疏矩阵的维度远远大于 10000，所以 BlockMatrix 无法适用于大规模稀疏矩阵运算。

四、矩阵乘法公式

CodeCogsEqn
图片 1
从矩阵乘法公式可知，矩阵相乘主要有以下环节：
1.左矩阵的列号(j)与右矩阵的行号(j)相同的元素进行两两相乘得到 MN_ik。
2.对所有具有相同下标(ik)的 MN_ik 进行相加，即得到 P_ik。

五、基于 RDD 实现矩阵乘法

阅读全文 →

日志

基于 CCO 的协同过滤推荐

基于 CCO(Correlated Cross-Occurrence) 的协同过滤本质上是一种 Item-Based CF 算法

基于 CCO 的协同过滤推荐

基于 CCO 的协同过滤推荐通过物品之间的共现情况来计算物品之间的关联度，它跟一般的协同过滤算法不同的地方在于一般的协同过滤只能针对单一行为，而CCO算法可以计算交叉行为下的协同关联。

例如：它不仅可以通过用户的浏览行为来告诉你 “浏览了内容A的人可能会浏览内容B” ,它还能结合用户的浏览行为和用户的广告点击行为来告诉你 “点击了广告A的人可能会浏览内容F”。

基于单一行为

假设有以下用户浏览行为日志：
用户行为log

整理后得到以下关系：
u1=> [ t1, t2, t3, t5 ]
u2=> [ t1, t3, t4, t5 ]
u3=> [ t2, t4 ]

构建 “用户关于浏览帖子” 的矩阵 V 以及对应的转置矩阵 V^T：
mtV

将 矩阵V^T 乘以 矩阵 V 即可得到浏览帖子的共现矩阵：
mtVV

对数似然比（Log Likelihood Ratio）即LLR。我们根据两个事件的共现关系计算LLR值，用于衡量两个事件的关联度：
LLR
阅读全文 →

日志

常用推荐算法比较

在推荐系统中常用的推荐算法一般可以分为两类，即 基于内容推荐 以及 协同过滤。另外，还有一类算法专门处理冷启动问题，例如：基于全局最优推荐。

基于内容推荐

基于内容推荐（Content-based Recommendations）非常好理解，简单来说就是根据用户偏好的内容给他推荐其他相似的内容。

cb

图：基于内容推荐

例如：从用户画像我们发现某个用户比较喜欢活跃在“音乐”、“体育”、“动漫”、“影视” 这些栏目，那么我们就会更倾向推荐这些栏目的内容给他，我们还发现他平时偏好的是关于 “NBA”、“美剧”、“邓紫棋” 等方面的内容，那么跟这些相关的内容就会有更高的推荐权重。

评价

基于内容推荐的结果一般具有很强的解释性，因为它推荐的就是强相关的内容，但这种强相关的特点也会导致一个很明显的缺陷，它缺乏惊喜度，因此它很难挖掘用户潜在的兴趣。要解决惊喜度的问题，可以采用另一类算法–协同过滤。

协同过滤

协同过滤（Collaborative Filtering）推荐本质上也是一个找相似的过程，但它认为的相似不是指物品在属性上的相似，而是指在用户行为的层面上这些物品是否有关联，协同过滤一般可以分为 基于用户的协同过滤（User-CF） 和 基于物品的协同过滤（Item-CF）。

用户物品偏好

图：用户物品偏好

基于用户的协同过滤

解释：因为 用户1 与 用户2 都喜欢物品A、B、C、D、E，所以认为 用户1 和 用户2 是兴趣相似的用户，现在发现 用户2 还喜欢 物品F 所以我们认为 用户1 很可能也对 物品F 感兴趣，所以向 用户1 推荐 物品F。

基于物品的协同过滤

解释：因为喜欢 物品A 的大多数都喜欢 物品C，所以可以认为 物品A 和 物品C 是相似的。用户4 喜欢 物品A 所以向 用户4 推荐 物品C。

评价

协同过滤集合了群体智慧，能满足推荐惊喜度，善于发掘用户潜在的兴趣。训练的用户历史行为数据越多，一般训练出来的模型效果也会越好。协同过滤推荐的解释性一般较弱，推荐结果不如基于内容推荐算法直观，当然这是算法特点导致的，不直观不等于不正确。
阅读全文 →

日志

个性化推荐系统的基本抽象

在大多数 UGC、PGC、OGC 平台中，“推荐”随处可见，本文主要介绍个性化推荐系统的抽象组成。

关于推荐

人工 VS 个性化

  • 早期的推荐功能大多以人工筛选为主。人工筛选可以确保内容的高质量，这是主要的优点之一，但人工筛选往往需要投入大量的人力成本。另外，由于不同用户的个人偏好差异巨大，高质量的内容往往不等于最合适的内容（例如：一篇介绍奢侈品牌化妆品的“高大上”内容对于一位平时只关心美食和户外运动的用户而言可能是毫无吸引力的）。

  • 为了提升用户体验，后来出现了“个性化内容推荐”的概念，通过引入个性化推荐系统，解决这类“千人千面”的问题。

推荐系统抽象

个性化推荐系统一般有三大环节：预处理 -> 召回 -> 排序 。
注：也可以认为是两层（召回 -> 排序）

预处理

第一个环节是预处理，预处理指的是对各种数据源的数据进行特征提取和特征构建，例如：内容特征提取，用户行为画像构建。

召回

第二个环节是召回，召回就是把预处理产生的特征作为输入参数，训练出推荐模型，然后使用推荐模型得出候选集合的过程。常用的召回方式有：基于内容推荐、基于协同过滤推荐等。

排序

第三个环节是排序，简单来说就是将候选集合根据一定的规则，例如：点击预估、匹配关联度、人为权重等进行调整，从而影响最后的推荐顺序。

推荐系统架构

最后简单画了一个基本的推荐系统架构原型
个性化推荐系统框架

图：个性化推荐系统架构 ©️hejunhao.me
转载请注明出处:

© http://hejunhao.me

日志

NLP 关键词提取算法之 TF-IDF

TF-IDF 是处理 NLP 问题时经常使用的经典算法，常用于对文本进行关键词的提取。

TF-IDF 介绍

计算公式

TF-IDF 的计算非常简单


TF-IDF = TF(\text{文章词频}) * IDF(\text{逆文档频率})

概念解释

TF: 指某个词在一段文本中出现的词频


TF = \dfrac{\text{某个词在文章中出现的次数}}{\text{文章总词数}}

IDF: 指某个词在所有文本（对应语境所在的训练语料，例如：科学领域、体育领域）中的区分度，它认为越少出现的词区分度越高，相应的 IDF 值也越高。


IDF = \log\dfrac{(\text{训练语料的总文档数+1})}{(\text{出现该词的文档数+1})}

分母 “+1” 是为了防止分母为零，同时相应地分子 “+1” 以防止 IDF 为负数。

算法总结

经验

从计算公式可知，TF-IDF 的准确性非常依赖 IDF 模型的质量。同一个词在不同领域对应的区分度（IDF）也不同甚至差别巨大，例如 “冠军” 在体育领域的语料中出现的次数远远大于在政治领域的语料中所出现的次数，这意味着在后者的语境下，“冠军” 这个词的区分度更高，IDF 值更大。要提升 TF-IDF 的算法效果一般需要根据业务场合单独训练特定领域的 IDF 模型。

评价

  • TF-IDF 计算复杂度低，适合对效率优先的场景。
  • 由于它只依赖关键词的统计特征进行排序，有时候效果并不理想，比如有时候文本的关键要素不一定是频繁出现的元素。
  • 另外它也缺乏对文本结构的考虑。
转载请注明出处:

© http://hejunhao.me

日志

Hadoop之YARN/MRv2

YARN又称为Mapreduce version 2（MRv2）是hadoop2.x的新架构，它将旧Hadoop Mapreduce框架中的JobTracker的资源管理和作业生命周期管理拆分成两个组件即ResourceManager(RM)和ApplicationMaster(AM)

一、为何需要MRv2？

mr1vsmr2

MRv1与MRv2对比

MRv1资源管理问题

  1. Hadoop1.0引入了“slot”的概念，每个slot代表了各个节点上的一份资源（CPU、内存等），MRv1把Map和Reduce的资源单独区分，即Map slot、Reduce slot，两个阶段的slot不能共享，这意味着资源的利用率大大降低
  2. 非MR应用不能分享资源，所以只能运行MR计算框架的应用
  3. 每个集群只有一个JobTracker,限制了集群的扩展，集群规模限制在4000个节点左右

MRv2资源管理方案

  1. 舍弃“slot”的概念，每个节点以“资源”（CPU、内存等）为单位分配给有需要的应用
  2. 支持运行MR应用和非MR应用
  3. JobTracker的大量功能被迁移到ApplicationMaster（AM），集群内可以存在多个AM（每个应用程序都拥有一个独立的AM），集群可以扩展到上万个节点

二、YARN架构

YARN_Architecture

YARN架构图(via Apache Hadoop)

资源管理器（ResourceManager，RM）

ResourceManager运行在主节点（Master）上，负责全局资源调度(分配/回收)，处理各个应用的资源请求，ResourceManager由调度器（Scheduler）和应用管理器（ApplicationsManager， AsM）组成

  • 调度器（Scheduler）
    调度器根据资源调度策略（例如Capacity Scheduler、Fair Scheduler），将包含适当资源（CPU、内存等）的资源容器（Container）分配给相应的节点，应用程序的各个任务均在容器内执行，且只能使用容器分配到的资源.调度器只负责资源调度，不关心应用的执行状态.
    阅读全文 →
日志

通过Sqoop向Hive导入ORC表

Sqoop在很长一段时间都只支持导入为textfile、avrofile、sequencefile等格式，如果需要将数据导入为ORC、parquet等格式的Hive Table往往需要分两个步骤完成（先导出临时表，再通过Hive转换）。而从Sqoop 1.4.4开始，Sqoop集成了HCatalog，我们可以轻易地实现多格式支持。

HCatalog配置

Sqoop需要依赖HCatalog的lib，所以需要配置环境变量$HCAT_HOME，一般从hive目录下即可找到hcatalog的相关路径

导入命令

sqoop import 
--connect jdbc:mysql://127.0.0.1:3306/test 
--username your_user_name --password your_passwd 
--table table_name --driver com.mysql.jdbc.Driver 
--create-hcatalog-table 
--hcatalog-table table_name 
--hcatalog-partition-keys month,day 
--hcatalog-partition-values 12,09 
--hcatalog-storage-stanza 'stored as orc tblproperties ("orc.compress"="SNAPPY")'

参数说明

阅读全文 →

日志

大数据的技术生态圈

本文来源知乎一个题为“如何用形象的比喻描述大数据的技术生态？”的精彩回答

大数据本身是个很宽泛的概念，Hadoop生态圈（或者泛生态圈）基本上都是为了处理超过单机尺度的数据处理而诞生的。你可以把它比作一个厨房所以需要的各种工具。锅碗瓢盆，各有各的用处，互相之间又有重合。你可以用汤锅直接当碗吃饭喝汤，你可以用小刀或者刨子去皮。但是每个工具有自己的特性，虽然奇怪的组合也能工作，但是未必是最佳选择。

大数据，首先你要能存的下大数据

传统的文件系统是单机的，不能横跨不同的机器。HDFS（Hadoop Distributed FileSystem）的设计本质上是为了大量的数据能横跨成百上千台机器，但是你看到的是一个文件系统而不是很多文件系统。比如你说我要获取/hdfs/tmp/file1的数据，你引用的是一个文件路径，但是实际的数据存放在很多不同的机器上。你作为用户，不需要知道这些，就好比在单机上你不关心文件分散在什么磁道什么扇区一样。HDFS为你管理这些数据。

存的下数据之后，你就开始考虑怎么处理数据

虽然HDFS可以为你整体管理不同机器上的数据，但是这些数据太大了。一台机器读取成T上P的数据（很大的数据哦，比如整个东京热有史以来所有高清电影的大小甚至更大），一台机器慢慢跑也许需要好几天甚至好几周。对于很多公司来说，单机处理是不可忍受的，比如微博要更新24小时热博，它必须在24小时之内跑完这些处理。那么我如果要用很多台机器处理，我就面临了如何分配工作，如果一台机器挂了如何重新启动相应的任务，机器之间如何互相通信交换数据以完成复杂的计算等等。这就是MapReduce / Tez / Spark的功能。MapReduce是第一代计算引擎，Tez和Spark是第二代。MapReduce的设计，采用了很简化的计算模型，只有Map和Reduce两个计算过程（中间用Shuffle串联），用这个模型，已经可以处理大数据领域很大一部分问题了。

那什么是Map什么是Reduce？

阅读全文 →