协同过滤算法示例

什么是协同过滤算法？

协同过滤是利用集体智慧的一个典型方法。
要理解什么是协同过滤 (Collaborative Filtering, 简称 CF)，首先想一个简单的问题，如果你现在想看个电影，但你不知道具体看哪部，你会怎么做？
大部分的人会问问周围的朋友，看看最近有什么好看的电影推荐，而我们一般更倾向于从口味比较类似的朋友那里得到推荐。
这就是协同过滤的核心思想。

协同过滤一般是在海量的用户中发掘出一小部分和你品位比较类似的，在协同过滤中，这些用户成为邻居，然后根据他们喜欢的其他东西组织成一个排序的目录作为推荐给你。

举个栗子

package com.lzhpo.cf1.test1;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.Set;

/**
 * 基于用户的协同过滤推荐算法实现
 * <p>
 * A a b d
 * B a c
 * C b e
 * D c d e
 * </p>
 *
 * UserCF的核心思想即为根据用户数据模拟向量相似度，我们根据这个相似度，来找出指定用户的相似用户，然后将相似用户买过的而指定用户没有买的东西推荐给指定用户，<br/>
 * 推荐度的计算也是结合了相似用户与指定用户的相似度累加。注意这里我们默认是用户的隐反馈行为，所以每一个物品的影响因子默认为1。
 *
 * @author lzhpo
 */
public class UserCF {

    public static void main(String[] args) {
        /*
         * 输入用户-->物品条目  一个用户对应多个物品
         * 用户ID    物品ID集合
         *   A        a b d
         *   B        a c
         *   C        b e
         *   D        c d e
         */
        Scanner scanner = new Scanner(System.in);
        System.out.println("Input the total users number:");
        //输入用户总量
        int n = scanner.nextInt();
        //建立用户稀疏矩阵，用于用户相似度计算【相似度矩阵】
        int[][] sparseMatrix = new int[n][n];
        //存储每一个用户对应的不同物品总数  eg: A 3
        Map<String, Integer> userItemLength = new HashMap<>();
        //建立物品到用户的倒排表 eg: a A B
        Map<String, Set<String>> itemUserCollection = new HashMap<>();
        //辅助存储物品集合
        Set<String> items = new HashSet<>();
        //辅助存储每一个用户的用户ID映射
        Map<String, Integer> userId = new HashMap<>();
        //辅助存储每一个ID对应的用户映射
        Map<Integer, String> idUser = new HashMap<>();
        System.out.println("Input user--items maping infermation:<eg:A a b d>");
        scanner.nextLine();
        //依次处理N个用户 输入数据  以空格间隔
        for (int i = 0; i < n; i++) {
            String[] userItem = scanner.nextLine().split(" ");
            int length = userItem.length;
            //eg: A 3
            userItemLength.put(userItem[0], length - 1);
            //用户ID与稀疏矩阵建立对应关系
            userId.put(userItem[0], i);
            idUser.put(i, userItem[0]);
            //建立物品--用户倒排表
            for (int j = 1; j < length; j++) {
                //如果已经包含对应的物品--用户映射，直接添加对应的用户
                if (items.contains(userItem[j])) {
                    itemUserCollection.get(userItem[j]).add(userItem[0]);
                } else {//否则创建对应物品--用户集合映射
                    items.add(userItem[j]);
                    //创建物品--用户倒排关系
                    itemUserCollection.put(userItem[j], new HashSet<String>());
                    itemUserCollection.get(userItem[j]).add(userItem[0]);
                }
            }
        }
        System.out.println(itemUserCollection.toString());
        //计算相似度矩阵【稀疏】
        Set<Entry<String, Set<String>>> entrySet = itemUserCollection.entrySet();
        for (Entry<String, Set<String>> stringSetEntry : entrySet) {
            Set<String> commonUsers = stringSetEntry.getValue();
            for (String userU : commonUsers) {
                for (String userV : commonUsers) {
                    if (userU.equals(userV)) {
                        continue;
                    }
                    //计算用户u与用户v都有正反馈的物品总数
                    sparseMatrix[userId.get(userU)][userId.get(userV)] += 1;
                }
            }
        }
        System.out.println(userItemLength.toString());
        System.out.println("Input the user for recommendation:<eg:A>");
        String recommendUser = scanner.nextLine();
        System.out.println(userId.get(recommendUser));
        //计算用户之间的相似度【余弦相似性】
        int recommendUserId = userId.get(recommendUser);
        for (int j = 0; j < sparseMatrix.length; j++) {
            if (j != recommendUserId) {
                System.out.println(idUser.get(recommendUserId) + "--" + idUser.get(j) + "相似度:" + sparseMatrix[recommendUserId][j] / Math.sqrt(userItemLength.get(idUser.get(recommendUserId)) * userItemLength.get(idUser.get(j))));
            }
        }

        //计算指定用户recommendUser的物品推荐度
        //遍历每一件物品
        for (String item : items) {
            //得到购买当前物品的所有用户集合
            Set<String> users = itemUserCollection.get(item);
            //如果被推荐用户没有购买当前物品，则进行推荐度计算
            if (!users.contains(recommendUser)) {
                double itemRecommendDegree = 0.0;
                for (String user : users) {
                    //推荐度计算
                    itemRecommendDegree += sparseMatrix[userId.get(recommendUser)][userId.get(user)] / Math.sqrt(userItemLength.get(recommendUser) * userItemLength.get(user));
                }
                System.out.println("The item " + item + " for " + recommendUser + "'s recommended degree:" + itemRecommendDegree);
            }
        }
        scanner.close();
    }

}

测试用户--物品映射数据：
左边第一个大写的是用户，右边的是物品。

A a b d
B a c
C b e
D c d e

推荐结果：

请输入用户个数:
4
请输入用户--物品映射数据:<eg:A a b d>
A a b d
B a c
C b e
D c d e
{a=[A, B], b=[A, C], c=[B, D], d=[A, D], e=[C, D]}
{A=3, B=2, C=2, D=3}
请输入给哪个用户推荐物品:<eg:A>
A
0
A--B相似度:0.4082482904638631
A--C相似度:0.4082482904638631
A--D相似度:0.3333333333333333
The item c for A's recommended degree:0.7415816237971964
The item e for A's recommended degree:0.7415816237971964