基于用户的协同过滤系统

协同过滤算法的两个步骤

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

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

1. 对任何两两用户进行余弦相似度的计算
   对于用户的每一个进行过行为（浏览或观看）转化为一个向量成为 aList
   对于另外一个用户进行过的行为我们转化为 bList

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

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

用户-物品倒排表

建立稀疏矩阵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是物品数量