基于用户的协同过滤算法

Scroll Down

基于用户的协同过滤系统

协同过滤算法的两个步骤

  1. 找到和目标用户兴趣相似的用户集合
  2. 找到这个集合中,用户喜欢的,且目标用户没有听说过的物品推荐给目标用户

如何计算用户之间的相似度/如何找到兴趣相似的用户

  1. 对任何两两用户进行余弦相似度的计算
    对于用户的每一个进行过行为(浏览或观看)转化为一个向量成为 aList
    对于另外一个用户进行过的行为我们转化为 bList
item用户A用户B
item111
item210
item300
item411
item501
item611
item711
item800
item901

对于任意一个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);
    }
}
  1. 先对用户进行筛选,再进行相似度的计算
    因为很多用户其实没有对同样的物品产生行为,我们不能把时间浪费在计算这种无谓的相似度上面。我们因此要首先计算彼此之间有对同一个物品产生了行为的用户,就是有可能相似的用户
    为此我们可以先建立物品到用户的倒排表

倒排表:对于每一个物品都保存对该物品产生过行为的用户

a

用户-物品倒排表

建立稀疏矩阵C
如果用户u和v同时属于倒排表第k个物品的对应的用户列表,就在矩阵中加入C[u][v] += 1
最终就能得到用户之间有交集的C
然后建立用户间相似矩阵W,这是一个密矩阵

总结一下以上过程就是
  1. 建立倒排表
  2. 建立稀疏矩阵C
  3. 建立相似矩阵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是物品数量