～随手记～

随手随记

～tech notes～

技术笔记开篇.

～hadoop mapreduce by streaming with python～

以经典的推荐算法中的协同过滤算法为例,看一下如何在hadoop的mapreduce机制上实现.

～算法细分～

user-based和item-based

其user-item-rating数据具有共同的特点:量大/稀疏;

步骤相同:

1.构造user-item-rating矩阵;

2.计算相似度;

3.找top n,计算矩阵中未知的rating;

其中核心问题是计算user或者item的最近邻或者相似度;

相似度算法包括:pearson, cosin, ...

～hadoop streaming～

hadoop streaming实现的目标是:可以让任何语言编写的mapreduce程序都能在hadoop上运行;前提是这些map reduce程序遵循标准输入输出(stdin/stdout).

这简直是python党的福音,python有丰富的数据处理包,numpy/pandas/...,加之其动态脚本的特性,可以灵活的修改,免除类似java各种依赖编译之苦...

～item-based 余弦相似度算法～

以item-based算法为例,做一个余弦相似度的mapreduce的python实现;

为何选cosin呢?因为这个实现起来简单,也好理解:D

～余弦相似度～

余弦相似度用来判断两个向量的相似程度,原理是计算两个向量夹角的余弦值,其值越接近于1,夹角越小,两向量越相似;

公式是:两个向量的点乘积/两向量模的乘积;

由于向量的夹角和其长度无关,可以先对向量进行规范化,或者单位化,即转化为一个模为1的单位向量,然后再计算两个单位向量夹角余弦,此时分母为1,只计算两单位向量点乘积即可;

～item-based 相似度计算步骤～

hadoop streaming使用的关键是用stdio形式来处理数据,所以要以这种模式来设计算法;算法要做的是:定义好各个mr阶段的map和reduce的输入/输出的格式和处理过程;

item-based 相似度mapreduce计算步骤:

0.构造user,item.score矩阵;

1.规范化

将矩阵排列为i-u-s形式,按照每一列item,进行规范化(normalization),让每一个item对应的向量都成为单位向量(模为1);

处理成单位向量,之后只要计算两个item的点乘积即可;

2.item之间在每一个user下,得分的两两乘积

将上述结果排列为u-i-s形式,针对每个user,进行其对应的所有items之间两两的乘积运算,输出:item_a-item_b-score_a*score*b;

注意这里要计算出item_a-item_b-score_a*score_b 和 item_b-item_a-score_a*score_b;在后续第三步中,按照一个item_a_item_b排序分组,再组内将这些乘积相加,就算得item_a与item_b的点乘积;

3.计算item间两两点乘积

将上述结果按照item_a_item_b,score_a*score_b的形式排序分组处理,将分组内的所有数值相加,即得item_a和item_b的点乘积;

～本机测试～

既然hadoop streaming要求其map reduce程序的实现支持stdio,那么可以用这个特性来进行本地的测试,利用管道命令即可;

比如测试step1,可以使用命令:

cat testdata/ratings_small.csv | python cfmr_itembased_step1_normalization_m.py |sort -k 1 |python cfmr_itembased_step1_normalization_r.py 

注意管道中的sort一步,这是必需的,这模拟了hadoop mapreduce机制中,在map过程中的排序过程,需要用这个命令来保证map的输出是基于key排序的;