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君推薦了吧。