基于用户的协同过滤系统
协同过滤算法的两个步骤
- 找到和目标用户兴趣相似的用户集合
- 找到这个集合中,用户喜欢的,且目标用户没有听说过的物品推荐给目标用户
如何计算用户之间的相似度/如何找到兴趣相似的用户
- 对任何两两用户进行余弦相似度的计算
对于用户的每一个进行过行为(浏览或观看)转化为一个向量成为 aList
对于另外一个用户进行过的行为我们转化为 bList
item | 用户A | 用户B |
---|---|---|
item1 | 1 | 1 |
item2 | 1 | 0 |
item3 | 0 | 0 |
item4 | 1 | 1 |
item5 | 0 | 1 |
item6 | 1 | 1 |
item7 | 1 | 1 |
item8 | 0 | 0 |
item9 | 0 | 1 |
对于任意一个item,0表示没有进行行为,1表示进行过行为
// 利用DistanceContext接口来实现距离的计算
DistanceContext distanceContext = new DistanceContext(new Cosine(aList,bList));
public class Cosine implements DistanceStrategy {
/**
* 夹角余弦
* @param aList
* @param bList
* @return
*/
@Override
public double getDistance(ArrayList<Double> aList, ArrayList<Double> bList) {
double m_ab = 0 ; //XY的乘积和
double m_a = 0; //X的平方和
double m_b = 0; //Y的平方和
for (int i=0;i<aList.size();i++)
{
m_ab+=aList.get(i)*bList.get(i);
m_a+=Math.pow(aList.get(i),2);
m_b+=Math.pow(bList.get(i),2);
}
return (m_ab)/(Math.sqrt(m_a)*Math.sqrt(m_b));
}
}
Jaccard公式同样也可以计算
public class JaccardDistance implements DistanceStrategy {
/**
* 杰卡德距离
* 不同的维度的个数占“非全零维度”的比例
* @param aList
* @param bList
* @return
*/
@Override
public double getDistance(ArrayList<Double> aList, ArrayList<Double> bList) {
int count=0; //不同维度的数量
int count1=0; //全零维度的数量
for (int i=0;i<aList.size();i++)
{
if (!aList.get(i).equals(bList.get(i)))
count++;
if (aList.get(i)==0&&bList.get(i)==0)
count1++;
}
return count/(aList.size()-(double)count1);
}
}
- 先对用户进行筛选,再进行相似度的计算
因为很多用户其实没有对同样的物品产生行为,我们不能把时间浪费在计算这种无谓的相似度上面。我们因此要首先计算彼此之间有对同一个物品产生了行为的用户,就是有可能相似的用户
为此我们可以先建立物品到用户的倒排表
倒排表:对于每一个物品都保存对该物品产生过行为的用户
用户-物品倒排表
建立稀疏矩阵C
如果用户u和v同时属于倒排表第k个物品的对应的用户列表,就在矩阵中加入C[u][v] += 1
最终就能得到用户之间有交集的C
然后建立用户间相似矩阵W,这是一个密矩阵
总结一下以上过程就是
- 建立倒排表
- 建立稀疏矩阵C
- 建立相似矩阵W
计算相似度矩阵
for (int i=0;i<userItemList.size();i++)
for (int j = 0; j < userItemList.get(i).size(); j++)
//判断倒排表中有没有,且用户对物品进行过行为
if (!(inverted.get(j).contains(i)) && (userItemList.get(i).get(j)) != 0) {
inverted.get(j).add(i);
for (Integer integer : inverted.get(j)) {
if (integer == i) //如果是其本身就不计算
continue;
Integer Uindex = integer;
if (!intersection.get(Uindex).contains(i) && (similarityMatrix.get(Uindex).get(i).similarity == 0)) { //如果交集中没有i且i不是那个用户
intersection.get(Uindex).add(i);
double distance = distanceContext.getDistance(userItemList.get(Uindex), userItemList.get(i)); //计算相似度
similarityMatrix.get(i).set(Uindex, new Entry(Uindex, distance));
similarityMatrix.get(Uindex).set(i, new Entry(i, distance));
}
}
}
上述代码中,userItemList 为用户对item的评分,此处有过行为为1,没有则为0
inverted是倒排表
intersection为交集
对于用户相似度计算的改进
这里引入一个例子,用户u买过《新华字典》,用户v也买过《新华字典》,事实上,人人基本上都买过《新华字典》,这对于我们的相似度计算是一个无用的信息,我们需要对这一部分数据进行惩罚
因此我们在原有余弦相似度的基础上再乘上
1/(log(1+abs(N(i))))
进行推荐
现在我们有了用户相似度矩阵w,假如我们要算的是用户 u 对物品 i 的兴趣,我们可以使用如下的公式:
在上述公式中,p是用户 u 对物品 i 的兴趣,v 代表的是对物品 i 有过行为的人,且是和用户 u 最接近的几个人,所以我们用一个并集来表示他们,w 表示用户 u 和 v 的相似度,r表示用户 v 对 物品 i 的兴趣,这里如果 v 对 i 有行为就代表 v 对 i 有兴趣,因此 r 为 1 。
for (int i=0;i<itemNum;i++)
{
if (userItemList.get(userIndex).get(i)!=0) //如果本身就看过就跳过
continue;
double interest=0;
for (int j=0;j<k;j++)
{
Entry entry = array.get(j);
interest+= entry.similarity * userItemList.get(entry.user_index).get(i); //计算兴趣
}
list.put(i,interest);
}
上述代码中,list为用户没看过的且感兴趣的评估
entry是用户相似度,里面包含了similarity和user_index
interest是用户的感兴趣程度
itemNum是物品数量