一、算法简介

1.1 基本特性

矩阵分解将一个矩阵分解为两个或者多个低维矩阵的，这两个低维矩阵能够代表原矩阵特性并且预测原矩阵中未知的特性——在推荐系统矩阵中的描述就是：通过评估低维矩阵乘积来拟合评分矩阵。

图 1.

如图1所示，一个有m个用户与n个项目的稀疏的矩阵$R_{m\times n}$，第i行表示第i个用户对于每个项目的评分，第j列表示某个项目不同用户给予的评分状况。图中的问号部分表示这部分没有具体的评分。

现在假设将此矩阵分解为两个或者多个矩阵的乘积，这里假设有两个低维矩阵$P_{m\times k}$与$Q_{k\times n}$，存在$R_{m\times n}=P_{m\times k}{Q}_{k\times n}$
为了方便，我们将矩阵R中的那些未评分项目默认写为0。

1.2 奇异值分解（Singular Value Decomposition，SVD）

SVD算法在降维、数据压缩、推荐系统中都有广泛的应用。
但是！今天使用的SVD是一种基于机器学习的“ 伪 ”SVD，因为SVD本身是要求将原矩阵分解为可取的两个矩阵，但是这里的SVD我们是做近似分解(所以上图我用的约等于)，然后通过拟合让分解得到的矩阵的部分元素不断接近原矩阵的有效元素，最终使得原矩阵的无效元素(0元素)也能被拟合预测出来。这种SVD最早被Simon Funk在博客中发布，因此又叫做Funk-SVD。

二、算法思路

1. 确定k值之后，针对用户-项目矩阵$R_{n\times m}$生成矩阵$P_{n\times k}$与$Q_{k\times m}$，其中生成内容为随机数。
2. 计算矩阵$R_{n\times m}$中的实际取值$r_{uv}$同$P_{n\times k}{Q}_{k\times m}$中得到的预测值$r^{uv}$的差值
3. 通过第二步取得的差值，调整$P$矩阵的n个向量$p_u$与$Q$矩阵的$m$个向量$q_v$，得到全新的矩阵$P$与$Q$
4. 重复2、3两步，直到最终MAE或者RSME收敛于一个预定义可靠的范围内。或者单纯循环若干次即可（我们选择后者）

三、代码实现

package machinelearning.recommendersystem;

/**

* @author Ling Lin E-mail:linling0.0@foxmail.com

* @version 创建时间：2022年5月27日 下午2:58:45

*/
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Random;

public class MatrixFactorization {
	/**
	 * Used to generate random numbers.
	 */
	Random rand = new Random();

	/**
	 * Number of users.
	 */
	int numUsers;

	/**
	 * Number of items.
	 */
	int numItems;

	/**
	 * Number of ratings.
	 */
	int numRatings;

	/**
	 * Training data.
	 */
	Triple[] dataset;

	/**
	 * A parameter for controlling learning regular.
	 */
	double alpha;

	/**
	 * A parameter for controlling the learning speed.
	 */
	double lambda;

	/**
	 * The low rank of the small matrices.
	 */
	int rank;

	/**
	 * The user matrix U.
	 */
	double[][] userSubspace;

	/**
	 * The item matrix V.
	 */
	double[][] itemSubspace;

	/**
	 * The lower bound of the rating value.
	 */
	double ratingLowerBound;

	/**
	 * The upper bound of the rating value.
	 */
	double ratingUpperBound;

	/**
	 ************************ 
	 * The first constructor.
	 * 
	 * @param paraFilename
	 *            The data filename.
	 * @param paraNumUsers
	 *            The number of users.
	 * @param paraNumItems
	 *            The number of items.
	 * @param paraNumRatings
	 *            The number of ratings.
	 ************************ 
	 */
	public MatrixFactorization(String paraFilename, int paraNumUsers, int paraNumItems, int paraNumRatings,
			double paraRatingLowerBound, double paraRatingUpperBound) {
		numUsers = paraNumUsers;
		numItems = paraNumItems;
		numRatings = paraNumRatings;
		ratingLowerBound = paraRatingLowerBound;
		ratingUpperBound = paraRatingUpperBound;

		try {
			readData(paraFilename, paraNumUsers, paraNumItems, paraNumRatings);
			// adjustUsingMeanRating();
		} catch (Exception ee) {
			System.out.println("File " + paraFilename + " cannot be read! " + ee);
			System.exit(0);
		} // Of try
	}// Of the first constructor

	/**
	 ************************ 
	 * Set parameters.
	 * 
	 * @param paraRank
	 *            The given rank.
	 * @throws IOException
	 ************************ 
	 */
	public void setParameters(int paraRank, double paraAlpha, double paraLambda) {
		rank = paraRank;
		alpha = paraAlpha;
		lambda = paraLambda;
	}// Of setParameters

	/**
	 ************************ 
	 * Read the data from the file.
	 * 
	 * @param paraFilename
	 *            The given file.
	 * @throws IOException
	 ************************ 
	 */
	public void readData(String paraFilename, int paraNumUsers, int paraNumItems, int paraNumRatings)
			throws IOException {
		File tempFile = new File(paraFilename);
		if (!tempFile.exists()) {
			System.out.println("File " + paraFilename + " does not exists.");
			System.exit(0);
		} // Of if
		BufferedReader tempBufferReader = new BufferedReader(new FileReader(tempFile));

		// Allocate space.
		dataset = new Triple[paraNumRatings];
		String tempString;
		String[] tempStringArray;
		for (int i = 0; i < paraNumRatings; i++) {
			tempString = tempBufferReader.readLine();
			tempStringArray = tempString.split(",");
			dataset[i] = new Triple(Integer.parseInt(tempStringArray[0]), Integer.parseInt(tempStringArray[1]),
					Double.parseDouble(tempStringArray[2]));
		} // Of for i

		tempBufferReader.close();
	}// Of readData

	/**
	 ************************ 
	 * Initialize subspaces. Each value is in [0, 1].
	 ************************ 
	 */
	void initializeSubspaces() {
		userSubspace = new double[numUsers][rank];

		for (int i = 0; i < numUsers; i++) {
			for (int j = 0; j < rank; j++) {
				userSubspace[i][j] = rand.nextDouble();
			} // Of for j
		} // Of for i

		itemSubspace = new double[numItems][rank];
		for (int i = 0; i < numItems; i++) {
			for (int j = 0; j < rank; j++) {
				itemSubspace[i][j] = rand.nextDouble();
			} // Of for j
		} // Of for i
	}// Of initializeSubspaces

	/**
	 ************************ 
	 * Predict the rating of the user to the item
	 * 
	 * @param paraUser
	 *            The user index.
	 ************************ 
	 */
	public double predict(int paraUser, int paraItem) {
		double resultValue = 0;
		for (int i = 0; i < rank; i++) {
			// The row vector of an user and the column vector of an item
			resultValue += userSubspace[paraUser][i] * itemSubspace[paraItem][i];
		} // Of for i
		return resultValue;
	}// Of predict

	/**
	 ************************ 
	 * Train.
	 * 
	 * @param paraRounds
	 *            The number of rounds.
	 ************************ 
	 */
	public void train(int paraRounds) {
		initializeSubspaces();

		for (int i = 0; i < paraRounds; i++) {
			updateNoRegular();
			if (i % 50 == 0) {
				// Show the process
				System.out.println("Round " + i);
				System.out.println("MAE: " + mae());
			} // Of if
		} // Of for i
	}// Of train

	/**
	 ************************ 
	 * Update sub-spaces using the training data.
	 ************************ 
	 */
	public void updateNoRegular() {
		for (int i = 0; i < numRatings; i++) {
			int tempUserId = dataset[i].user;
			int tempItemId = dataset[i].item;
			double tempRate = dataset[i].rating;

			double tempResidual = tempRate - predict(tempUserId, tempItemId); // Residual

			// Update user subspace
			double tempValue = 0;
			for (int j = 0; j < rank; j++) {
				tempValue = 2 * tempResidual * itemSubspace[tempItemId][j];
				userSubspace[tempUserId][j] += alpha * tempValue;
			} // Of for j

			// Update item subspace
			for (int j = 0; j < rank; j++) {
				tempValue = 2 * tempResidual * userSubspace[tempUserId][j];

				itemSubspace[tempItemId][j] += alpha * tempValue;
			} // Of for j
		} // Of for i
	}// Of updateNoRegular

	/**
	 ************************ 
	 * Compute the RSME.
	 * 
	 * @return RSME of the current factorization.
	 ************************ 
	 */
	public double rsme() {
		double resultRsme = 0;
		int tempTestCount = 0;

		for (int i = 0; i < numRatings; i++) {
			int tempUserIndex = dataset[i].user;
			int tempItemIndex = dataset[i].item;
			double tempRate = dataset[i].rating;

			double tempPrediction = predict(tempUserIndex, tempItemIndex);// +
																			// DataInfo.mean_rating;

			if (tempPrediction < ratingLowerBound) {
				tempPrediction = ratingLowerBound;
			} else if (tempPrediction > ratingUpperBound) {
				tempPrediction = ratingUpperBound;
			} // Of if

			double tempError = tempRate - tempPrediction;
			resultRsme += tempError * tempError;
			tempTestCount++;
		} // Of for i

		return Math.sqrt(resultRsme / tempTestCount);
	}// Of rsme

	/**
	 ************************ 
	 * Compute the MAE.
	 * 
	 * @return MAE of the current factorization.
	 ************************ 
	 */
	public double mae() {
		double resultMae = 0;
		int tempTestCount = 0;

		for (int i = 0; i < numRatings; i++) {
			int tempUserIndex = dataset[i].user;
			int tempItemIndex = dataset[i].item;
			double tempRate = dataset[i].rating;

			double tempPrediction = predict(tempUserIndex, tempItemIndex);

			if (tempPrediction < ratingLowerBound) {
				tempPrediction = ratingLowerBound;
			} // Of if
			if (tempPrediction > ratingUpperBound) {
				tempPrediction = ratingUpperBound;
			} // Of if

			double tempError = tempRate - tempPrediction;

			resultMae += Math.abs(tempError);
			// System.out.println("resultMae: " + resultMae);
			tempTestCount++;
		} // Of for i

		return (resultMae / tempTestCount);
	}// Of mae

	/**
	 ************************ 
	 * Compute the MAE.
	 * 
	 * @return MAE of the current factorization.
	 ************************ 
	 */
	public static void testTrainingTesting(String paraFilename, int paraNumUsers, int paraNumItems, int paraNumRatings,
			double paraRatingLowerBound, double paraRatingUpperBound, int paraRounds) {
		try {
			// Step 1. read the training and testing data
			MatrixFactorization tempMF = new MatrixFactorization(paraFilename, paraNumUsers, paraNumItems,
					paraNumRatings, paraRatingLowerBound, paraRatingUpperBound);

			tempMF.setParameters(5, 0.0001, 0.005);

			// Step 3. update and predict
			System.out.println("Begin Training ! ! !");
			tempMF.train(paraRounds);

			double tempMAE = tempMF.mae();
			double tempRSME = tempMF.rsme();
			System.out.println("Finally, MAE = " + tempMAE + ", RSME = " + tempRSME);
		} catch (Exception e) {
			e.printStackTrace();
		} // Of try
	}// Of testTrainingTesting

	/**
	 ************************ 
	 * @param args
	 ************************ 
	 */
	public static void main(String args[]) {
		testTrainingTesting("D:/00/data/movielens-943u1682m.txt", 943, 1682, 10000, 1, 5, 2000);
	}// Of main

	public class Triple {
		public int user;
		public int item;
		public double rating;

		/**
		 *********************
		 * The constructor.
		 *********************
		 */
		public Triple() {
			user = -1;
			item = -1;
			rating = -1;
		}// Of the first constructor

		/**
		 *********************
		 * The constructor.
		 *********************
		 */
		public Triple(int paraUser, int paraItem, double paraRating) {
			user = paraUser;
			item = paraItem;
			rating = paraRating;
		}// Of the first constructor

		/**
		 *********************
		 * Show me.
		 *********************
		 */
		@Override
		public String toString() {
			return "" + user + ", " + item + ", " + rating;
		}// Of toString
	}// Of class Triple

}// Of class MatrixFactorization