slopeone算法

㈠ 协同过滤与分类

[TOC]

本文是《写给程序员的数据挖掘实践指南》的一周性笔记总结。主要涵盖了以下内容：

所谓推荐系统就是系统根据你的行为操作为你推荐你可能想要的其他物品。这在电商平台、音乐平台、资讯推送平台等多有见到。而协同过滤简单来说是利用某兴趣相投、拥有共同经验之群体的喜好来推荐用户感兴趣的信息，个人通过合作的机制给予信息相当程度的回应（如评分）并记录下来以达到过滤的目的进而帮助别人筛选信息。其推荐基础是用户评分。这里可以分为两种用户评分，即显式评分与隐式评分。显式评分即日常见到的为物品打分，如对喜好音乐评级等；隐式评分是通过对用户行为的持续性观察，进而发现用户偏好的一种方法，如新闻网页中的推送你经常阅读过的相关内容等。两种评分方法都有自己的问题。

总体来说，协同过滤其运作机制也可以分为两种：

基于用户的推荐是指通过用户的行为偏好，划分相似用户。在相似用户群体之间互相推送一方喜欢而另一方未有过的物品。核心在于相似用户群体的划分。这种推荐方法有自己的局限：

基于用户的过滤其核心是用户群体的划分，其实也就是分类。

这里的距离函数包括三种：曼哈顿距离和欧氏距离。这里以二维举例，更多维情况下类推即可。

两距离函数可以一般化为：

其中，当r=1时，函数为曼哈顿距离；当r=2时，函数为欧氏距离。

算法实现：

在算出距离函数后，通过比对目标用户与所有用户群体的偏好，找到最近邻的用户并给予推荐。

基于用户距离的推荐有一个明显的问题，就是用户评分体系的差异。比如评分极端的用户给喜欢的评最高分，给不喜欢的评最低分；而有些用户倾向于不出现极端评分。即所谓“分数贬值”( Grade Inflation )问题。这种问题的存在可能让基于距离的评分产生偏差。皮尔逊相关系数可以缓解这种问题。

原皮尔逊相关系数公式在实际运用的时候会出现多次迭代的问题，影响计算效率，这里给出了近似公式：

皮尔逊相关系数的用户判断依据不是单纯的用户距离，而是用户的评分一致性：取值在[-1, 1]之间，越接近1则表示两用户的评分一致性越好；反之则反。
python实现：

基于用户推荐的过程中，另一个存在的问题就是由于大部分人的喜爱物品集合的交集过少，存在大量计算值为0的feature的情况。即所谓 稀疏性 问题。一个较容易理解的例子是对书本内容的挖掘。余弦相似度会忽略这种0-0匹配。
余弦相似度：

python实现：

如此多的评估系数，如何进行抉择呢？根据数据特征：

另外值得考虑的一点是，目前为止的推荐都是基于单用户的。即对一个用户的推荐系统只是基于另一个用户。这会存在一些问题。比如虽然虽然两者相似度很高，但是另外一个人有一些怪癖，怪癖的推荐就是不合理的；又比如，在相似度极高的情况下，你不能确定统一账户下的操作是同一个人做出的或者说操作行为是为了用户自身。比如用户考虑购买某件商品作为礼物送给别人，这就是基于别人喜好的购买行为，这种推荐也是不合适的。
对这种问题的解决可以使用群体划分的方法。原理与单用户类似，但是用户的匹配是k个。在这k位最优匹配的用户之间，以相似度的大小为依据设定权重作为物品推荐的条件。此即协同过滤的k近邻。

正如前面提到的基于用户的推荐有复杂度、稀疏性的问题，而基于物品的过滤则可以缓解这些问题。所谓基于物品的过滤是指，我们事先找到最相似的物品，并结合用户对物品的评级结果来生成推荐。前提是要对物品进行相似度匹配，找到一种算法。

这里的调整是指为了减轻用户评分体系的不一致情况（抵消分数贬值），从每个评级结果中减去该用户所有物品的平均分的评级结果。

其中，U表示所有同时对i， j进行评级过的用户的集合。 表示用户u给物品i的评分减去用户u对所有物品的评分的平均值。

在得到所有物品的余弦相似度后，我们就可以通过该指数预测用户对某件物品的偏好程度。方法就是所有相似物品的相似度乘以得分的总和。

其中p（u, i）指的是用户u对物品i评分的预测值。N是用户u的所有评级物品中每个和i得分相似的物品。这里的相似指的是矩阵中存在N和i的一个相似度得分。 是i和N之间的相似度得分。 是u给N的评级结果。公式较好运行的条件是 取值在（-1， 1）之间，这里就要使用归一化概念。

另一种常用的基于物品过滤的算法就是 slope one 算法。它的大概原理是预测用户u对产品j的评分时，预先计算包含所有物品的两物品偏差表；根据u的已评价的所有物品评分与该物品和产品j的偏差（ ）之和并乘以所有对此两类物品有过评分的用户个数，一一加总，除以所有同时对产品i与u评价过的所有物品有过评分的用户的人数，得到得分。公式如下：

其中， ； 是利用加权s1算法给出的用户u对物品j的预测值。 指的是对所有除j之外u打过分的物品。

python实现：

在前面两节中，基于物品和基于用户的过滤其前提都是用户需要对已有的item进行评分。而实际上，如果一个新的item出现，由于缺乏别人的偏好，他永远不会被推荐。这就是推荐系统中所谓的—— 冷启动 问题。基于用户评价的系统就会出现这种问题。
冷启动 问题的解决方案之一就是 基于物品属性的过滤 来进行推荐：对物品自身的属性进行归纳总结，并以此进行物品推荐。基于物品属性的过滤存在一个问题同样是量纲的不统一。如果量纲不统一极端值将会对推荐系统造成大麻烦。解决方法也很简单：归一化。此章使用的是z-评分。
使用z得分也存在问题，就是极易受到离群值的影响。这里可以使用 改进的标准分数 来缓解这个问题：

什么时候可以进行归一化呢？

这里用曼哈顿距离举例基于物品属性的过滤：

在上一章最后一节对于用户是否喜欢某件item的判别中，实际上包含了分类器的思想：分类器就是利用对象属性判定对象属于哪个组或类别的程序。这里简单用另一个小项目来说明。

简单来说就是根据运动员的某些指标来判断这位运动员属于什么类别的运动员。

准确率有0.8。

㈡ 如何在linux下安装配置Apache Mahout

Mahout安装详细全过程
1、jdk安装 2
2、SSH无密码验证配置 2
3、 Hadoop配置 3
4、Hadop使用 6
5、Maven安装 7
6、安装mahout 7
7、hadoop集群来执行聚类算法 8
8、其他 8
————————————————————
1、jdk安装
1.1、到官网下载相关的JDK
下载地址：http://www.oracle.com/technetwork/java/javase/downloads/index.html

1.2、打开“终端”
输入：sh jdk-6u24-linux-i586.bin

1.3、设置JAVA_HOME环境系统变量
输入：
vi /etc/environment
在文件中添加：
export JAVA_HOME=/root/jdk1.6.0_24
export JRE_Home=/root/jdk1.6.0_24/jre
export CLASSPATH=$CLASSPATH:$JAVA_HOME/lib:$JAVA_HOME/jre/lib
同样，修改第二个文件。输入：
vi /etc/profile
在umask 022之前添加以下语句：
export JAVA_HOME=/root/jdk1.6.0_24
export JRE_Home=/root/jdk1.6.0_24/jre
export CLASSPATH=$CLASSPATH:$JAVA_HOME/lib:$JAVA_HOME/jre/lib
export PATH=$JAVA_HOME/bin:$JAVA_HOME/jre/bin:$PATH:$HOME/bin

1.4、注销用户，检测JDK版本。
输入：
java -version

2、集群环境介绍
集群包含三个节点：1 个 namenode，2 个 datanode，节点之间局域网连接，可以相互 ping 通。节点 IP 地址分布如下：
Namenode: [email protected]
Datanode1: slave1 @192.168.1.20
Datanode2: [email protected]
三台节点上均是CentOS系统，Hadoop在/root/hadoop/目录下。
在/etc/hosts上添加主机名和相应的IP地址：
192.168.1.10 master
192.168.1.20 slave1
192.168.1.21 slave2
3、SSH无密码验证配置
2.1 Hadoop 需要使用SSH 协议，namenode 将使用SSH 协议启动 namenode和datanode 进程，伪分布式模式数据节点和名称节点均是本身，必须配置 SSH localhost无密码验证。
用root用户登录，在家目录下执行如下命令：ssh-keygen -t rsa
[root@master ~]# ssh-keygen -t rsa
Generating public/private rsa key pair.
Enter file in which to save the key (/root/.ssh/id_rsa): & 按回车默认路径 &
Created directory '/root/.ssh'. &创建/root/.ssh目录&
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in /root/.ssh/id_rsa.
Your public key has been saved in /root/.ssh/id_rsa.pub.
The key fingerprint is:
c6:7e:57:59:0a:2d:85:49:23:cc:c4:58:ff:db:5b:38 root@master
通过以上命令将在/root/.ssh/ 目录下生成id_rsa私钥和id_rsa.pub公钥。进入/root/.ssh目录在namenode节点下做如下配置：
[root@master .ssh]# cat id_rsa.pub > authorized_keys
[root@master .ssh]# scp authorized_keys 192.168.1.20:/root/.ssh/
[root@master .ssh]# scp authorized_keys 192.168.1.21:/root/.ssh/
配置完毕，可通过ssh 本机IP 测试是否需要密码登录。

2.2 和namenode无密码登录所有Datanode原理一样，把Datanode的公钥复制到
Namenode的.ssh目录下。
[root@slave1 .ssh]# scp authorized_keys1 192.168.1.10:/root /.ssh
[root@ slave2.ssh]# scp authorized_keys2 192.168.1.10:/root /.ssh
将刚传过来的authorized_keys1、2加入到authorized_keys
[root@ master.ssh]# cat authorized_keys1 > authorized_keys
[root@ master.ssh]# cat authorized_keys2 > authorized_keys
这样也能在Datanode上关闭和启动Hadoop服务。
4、 Hadoop配置
下载 hadoop-0.20.2.tar.gz， 进行解压。
tar zxvf hadoop-0.20.2.tar.gz
修改/etc/profile，加入如下：
# set hadoop path
export HADOOP_HOME=/root/hadoop
export PATH=$HADOOP_HOME/bin:$PATH

4.1、进入hadoop/conf， 配置Hadoop配置文件
4.1.1 配置hadoop-env.sh文件
添加 # set java environment
export JAVA_HOME=/root/jdk1.6.0_24
编辑后保存退出。

4.1.2 配置core-site.xml
# vi core-site.xml
<?xml version="1.0"?>
<?xml-stylesheet type="text/xsl" href="configuration.xsl"?>
<!-- Put site-specific property overrides in this file. -->
<configuration>
<property>
<name>fs.default.name</name>
<value>hdfs://192.168.1.10:9000/</value>
</property>
<property>
<name>hadoop.tmp.dir</name>
<value>/root/hadoop/hadooptmp</value>
</property>
</configuration>

4.1.3 配置hdfs-site.xml
# vi hdfs-site.xml
<?xml version="1.0"?>
<?xml-stylesheet type="text/xsl" href="configuration.xsl"?>
<!-- Put site-specific property overrides in this file. -->
<configuration>
<property>
<name>dfs.name.dir</name>
<value>/root/hadoop/hdfs/name</value>
</property>
<property>
<name>dfs.data.dir</name>
<value>/root/hadoop/hdfs/data</value>
</property>
<property>
<name>dfs.replication</name>
<value>3</value>
</property>
</configuration>

4.1.4 配置mapred-site.xml
# vi mapred-site.xml
<?xml version="1.0"?>
<?xml-stylesheet type="text/xsl" href="configuration.xsl"?>
<!-- Put site-specific property overrides in this file. -->
<configuration>
<property>
<name>mapred.job.tracker</name>
<value>192.168.1.10:9001</value>
</property>
<property>
<name>mapred.local.dir</name>
<value>/root/hadoop/mapred/local</value>
</property>
<property>
<name>mapred.system.dir</name>
<value>/tmp/hadoop/mapred/system</value>
</property>
</configuration>

4.1.5 配置masters
# vi masters
192.168.1.10
4.1.6 配置slaves
# vi slaves
192.168.1.20
192.168.1.21

4.2、 Hadoop启动
4.2.1 进入 /root/hadoop/bin目录下，格式化namenode
# ./hadoop namenode –format

4.2.2 启动hadoop所有进程
在/root/hadoop/bin 目录下，执行start-all.sh命令
启动完成后，可用jps命令查看hadoop进程是否启动完全。正常情况下应该有如下进程：
10910 NameNode
11431 Jps
11176 SecondaryNameNode
11053 DataNode
11254 JobTracker
11378 TaskTracker

我在搭建过程中，在此环节出现的问题最多，经常出现启动进程不完整的情况，要不是datanode无法正常启动，就是namenode或是TaskTracker启动异常。解决的方式如下：
1）在Linux下关闭防火墙：使用service iptables stop命令；
2）再次对namenode进行格式化：在/root/hadoop/bin 目录下执行hadoop namenode -format命令
3）对服务器进行重启
4）查看datanode或是namenode对应的日志文件，日志文件保存在/root/hadoop/logs目录下。
5）再次在/bin目录下用start-all.sh命令启动所有进程，通过以上的几个方法应该能解决进程启动不完全的问题了。

4.2.3 查看集群状态
在 bin目录下执行：hadoop dfsadmin -report
# hadoop dfsadmin –report

4.3 在WEB页面下查看Hadoop工作情况
打开IE浏览器输入部署Hadoop服务器的IP：
http://localhost:50070
http://localhost:50030。

5、Hadop使用
一个测试例子wordcount：
计算输入文本中词语数量的程序。WordCount在Hadoop主目录下的java程序包hadoop-0.20.2-examples.jar 中，执行步骤如下：
在/root/hadoop/bin/目录下进行如下操作：
./hadoop fs -mkdir input(新建目录名称，可任意命名)
mkdir /root/a/
vi /root/a/a.txt
写入hello world hello
# hadoop fs -FromLocal /root/a/ input
在/root/hadoop/bin下执行：
# ./hadoop jar hadoop-0.20.2-examples.jar wordcount input output (提交作业，此处需注意input与output是一组任务，下次再执行wordcount程序，还要新建目录intput1与output1不能跟input与output重名)

6、Maven安装
6.1下载Maven
解压tar vxzf apache-maven-3.0.2-bin.tar.gz
mv apache-maven-3.0.2 /root/maven

6.2 vi ~/.bashrc
添加如下两行
export M3_HOME=/root/maven
export PATH=${M3_HOME}/bin:${PATH}

6.3 先logout，之后再login
查看maven版本，看是否安装成功
mvn -version

7、安装mahout
安装方法见：
https://cwiki.apache.org/confluence/display/MAHOUT/BuildingMahout

8、hadoop集群来执行聚类算法
8.1数据准备
cd /root/hadoop
wget http://archive.ics.uci.e/ml/databases/synthetic_control/synthetic_control.data

8.2 ./hadoop fs -mkdir testdata
./hadoop fs -put synthetic_control.data testdata
./hadoop fs -lsr testdata

bin/hadoop jar /root/mahout/mahout-examples-0.4-job.jar org.apache.mahout.clustering.syntheticcontrol.kmeans.Job

8.3查看一下结果吧
bin/mahout vectormp --seqFile /user/root/output/data/part-r-00000
这个直接把结果显示在控制台上。

9、hadoop集群来执行推荐算法
分布式
bin/hadoop jar /root/trunk/mahout-distribution-0.4/mahout-core-0.4-job.jar org.apache.mahout.cf.taste.hadoop.item.RecommenderJob -Dmapred.map.tasks=3 -Dmapred.rece.tasks=3 -Dmapred.input.dir=testdata/100wan.txt -Dmapred.output.dir=output2

伪分布式
bin/hadoop jar /root/trunk/mahout-distribution-0.4/mahout-core-0.4-job.jar org.apache.mahout.cf.taste.hadoop.pseudo.RecommenderJob --recommenderClassName org.apache.mahout.cf.taste.impl.recommender.slopeone.SlopeOneRecommender -Dmapred.input.dir=testdata/10wan.dat -Dmapred.output.dir=output_w10wan
10、其他
离开安全模式：hadoop dfsadmin -safemode leave

㈢ 网易云音乐的歌单推荐算法是怎样的

“商品推荐”系统的算法( Collaborative filtering )分两大类，第一类，以人为本，先找到与你相似的人，然后看看他们买了什么你没有买的东西。这类算法最经典的实现就是“多维空间中两个向量夹角的余弦公式”；第二类, 以物为本直接建立各商品之间的相似度关系矩阵。这类算法中最经典是'斜率=1' (Slope One)。amazon发明了暴力简化的第二类算法，‘买了这个商品的人，也买了xxx’。我们先来看看第一类，最大的问题如何判断并量化两人的相似性，思路是这样 -- 例子：有3首歌放在那里，《最炫民族风》，《晴天》，《Hero》。A君，收藏了《最炫民族风》，而遇到《晴天》，《Hero》则总是跳过；B君，经常单曲循环《最炫民族风》，《晴天》会播放完，《Hero》则拉黑了C君，拉黑了《最炫民族风》，而《晴天》《Hero》都收藏了。我们都看出来了，A,B二位品味接近，C和他们很不一样。那么问题来了，说A，B相似，到底有多相似，如何量化？我们把三首歌想象成三维空间的三个维度，《最炫民族风》是x轴，《晴天》是y轴，《Hero》是z轴，对每首歌的喜欢程度即该维度上的坐标，并且对喜欢程度做量化(比如： 单曲循环=5, 分享=4, 收藏=3, 主动播放=2 , 听完=1, 跳过=-1 , 拉黑=-5 )。那么每个人的总体口味就是一个向量，A君是 (3,-1,-1)，B君是(5,1,-5)，C君是(-5,3,3)。 (抱歉我不会画立体图)我们可以用向量夹角的余弦值来表示两个向量的相似程度， 0度角(表示两人完全一致)的余弦是1， 180%角(表示两人截然相反)的余弦是-1。根据余弦公式, 夹角余弦 = 向量点积/ (向量长度的叉积) = ( x1x2 + y1y2 + z1z2) / ( 跟号(x1平方+y1平方+z1平方 ) x 跟号(x2平方+y2平方+z2平方 ) )可见 A君B君夹角的余弦是0.81 ， A君C君夹角的余弦是 -0.97 ，公式诚不欺我也。以上是三维(三首歌)的情况，如法炮制N维N首歌的情况都是一样的。假设我们选取一百首种子歌曲，算出了各君之间的相似值，那么当我们发现A君还喜欢听的《小苹果》B君居然没听过，相信大家都知道该怎么和B君推荐了吧。