Implementation of php+mysql collaborative filtering algorithm

To implement the collaborative filtering recommendation algorithm, we must first understand the core idea and process of the algorithm. The core idea of ​​this algorithm can be summarized as follows: If a and b like the same series of items (let’s call b a neighbor for now), then a is likely to like other items that b likes. The implementation process of the algorithm can be simply summarized as follows: 1. Determine which neighbors a has. 2. Use the neighbors to predict what kind of items a may like. 3. Recommend the items a may like to a.

The core formula of the algorithm is as follows:

1. Cosine similarity (finding neighbors):

2. Prediction formula (Predict what kind of items a might like):

From these two formulas alone, we can see that just calculating according to these two formulas requires It involves a lot of looping and judgment, and it also involves sorting issues, which involves the selection and use of sorting algorithms. Here I choose quick sort, copy a section of quick sort from the Internet, and use it directly. In short, it is very troublesome to implement, not to mention efficiency in the case of big data.

First create a table:

DROP TABLE IF EXISTS `tb_xttj`;
CREATE TABLE `tb_xttj` (
  `name` varchar(255) NOT NULL,
  `a` int(255) default NULL,
  `b` int(255) default NULL,
  `c` int(255) default NULL,
  `d` int(255) default NULL,
  `e` int(255) default NULL,
  `f` int(255) default NULL,
  `g` int(255) default NULL,
  `h` int(255) default NULL,
  PRIMARY KEY  (`name`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1;

INSERT INTO `tb_xttj` VALUES ('John', '4', '4', '5', '4', '3', '2', '1', null);
INSERT INTO `tb_xttj` VALUES ('Mary', '3', '4', '4', '2', '5', '4', '3', null);
INSERT INTO `tb_xttj` VALUES ('Lucy', '2', '3', null, '3', null, '3', '4', '5');
INSERT INTO `tb_xttj` VALUES ('Tom', '3', '4', '5', null, '1', '3', '5', '4');
INSERT INTO `tb_xttj` VALUES ('Bill', '3', '2', '1', '5', '3', '2', '1', '1');
INSERT INTO `tb_xttj` VALUES ('Leo', '3', '4', '5', '2', '4', null, null, null);

I will only recommend Leo in the last row to see which one of f, g, and h can be recommended to him.

Using php+mysql, the flow chart is as follows:

The code to connect to the database and store it as a two-dimensional array is as follows:

header("Content-Type:text/html;charset=utf-8");

mysql_connect("localhost","root","admin");
mysql_select_db("geodatabase");
mysql_query("set names 'utf8'");	

$sql = "SELECT * FROM tb_xttj";
$result = mysql_query($sql);

$array = array();
while($row=mysql_fetch_array($result))
{
	$array[]=$row;//$array[][]是一个二维数组
}

Question 1: This step can be regarded as a whole table query. This kind of query is taboo. It is okay for this small demonstration system, but for big data The system is inefficient. As for how to improve it, we still need to learn more.

The Cos value code for Leo and others is as follows:

/*
 * 以下示例只求Leo的推荐,如此给变量命名我也是醉了;初次理解算法，先不考虑效率和逻辑的问题，主要把过程做出来
 */

$cos = array();
$cos[0] = 0;
$fm1 = 0;
//开始计算cos
//计算分母1，分母1是第一个公式里面 “*”号左边的内容，分母二是右边的内容
for($i=1;$i<9;$i++){
	if($array[5][$i] != null){//$array[5]代表Leo
		$fm1 += $array[5][$i] * $array[5][$i];
	}
}

$fm1 = sqrt($fm1);

for($i=0;$i<5;$i++){
	$fz = 0;
	$fm2 = 0;
	echo "Cos(".$array[5][0].",".$array[$i][0].")=";
	
	for($j=1;$j<9;$j++){
	    //计算分子
		if($array[5][$j] != null && $array[$i][$j] != null){
			$fz += $array[5][$j] * $array[$i][$j];
		}
		//计算分母2
		if($array[$i][$j] != null){
			$fm2 += $array[$i][$j] * $array[$i][$j];
		}			
	}
	$fm2 = sqrt($fm2);
	$cos[$i] = $fz/$fm1/$fm2;
	echo $cos[$i]."<br/>";
}

The result obtained in this step is Jiang Zi:

Sort the obtained Cos values ​​and use the quick sort code as follows (copied from Baidu):

//对计算结果进行排序,凑合用快排吧先
function quicksort($str){
	if(count($str)<=1) return $str;//如果个数不大于一，直接返回
	$key=$str[0];//取一个值，稍后用来比较；
	$left_arr=array();
	$right_arr=array();
	
	for($i=1;$i<count($str);$i++){//比$key大的放在右边，小的放在左边；
		if($str[$i]>=$key)
		$left_arr[]=$str[$i];
		else
		$right_arr[]=$str[$i];
	}
	$left_arr=quicksort($left_arr);//进行递归；
	$right_arr=quicksort($right_arr);
	return array_merge($left_arr,array($key),$right_arr);//将左中右的值合并成一个数组；
}

$neighbour = array();//$neighbour只是对cos值进行排序并存储
$neighbour = quicksort($cos);

The $neighbour array here only stores the order from largest to The small sorted CoS value is not associated with people. This problem still needs to be solved.

Select the 3 people with the highest CoS values ​​as Leo’s neighbors:

//$neighbour_set 存储最近邻的人和cos值
$neighbour_set = array();
for($i=0;$i<3;$i++){
	for($j=0;$j<5;$j++){
		if($neighbour[$i] == $cos[$j]){
			$neighbour_set[$i][0] = $j;
			$neighbour_set[$i][1] = $cos[$j];
			$neighbour_set[$i][2] = $array[$j][6];//邻居对f的评分
			$neighbour_set[$i][3] = $array[$j][7];//邻居对g的评分
			$neighbour_set[$i][4] = $array[$j][8];//邻居对h的评分
		}
	}
}
print_r($neighbour_set);
echo "<p><br/>";

The result of this step is Jiang Zi:

This is a two-dimensional array. The subscripts on the first level of the array are 0, 1, and 2, representing 3 people. The second-level subscript 0 represents the order of the neighbors in the data table, for example, Jhon is the 0th person in the table; the subscript 1 represents the Cos value of Leo and the neighbor; the subscript 2, 3, and 4 represent the neighbor pair f and g respectively. , h rating.

Start making predictions, and the Predict calculation code is as follows:

I calculate Leo's prediction values ​​for f, g, and h respectively. There is a problem here, that is, how to deal with it if some neighbors have empty scores for f, g, h. For example, the ratings of h by Jhon and Mary are empty. Instinctively I thought of using if to judge, and if it is empty, skip this set of calculations, but whether this is reasonable remains to be considered. The following code does not write this if judgment.

//计算Leo对f的评分
$p_arr = array();
$pfz_f = 0;
$pfm_f = 0;
for($i=0;$i<3;$i++){
	$pfz_f += $neighbour_set[$i][1] * $neighbour_set[$i][2];
	$pfm_f += $neighbour_set[$i][1];
}
$p_arr[0][0] = 6;
$p_arr[0][1] = $pfz_f/sqrt($pfm_f);
if($p_arr[0][1]>3){
	echo "推荐f";
}

//计算Leo对g的评分
$pfz_g = 0;
$pfm_g = 0;
for($i=0;$i<3;$i++){
	$pfz_g += $neighbour_set[$i][1] * $neighbour_set[$i][3];
	$pfm_g += $neighbour_set[$i][1];
	$p_arr[1][0] = 7;
	$p_arr[1][1] = $pfz_g/sqrt($pfm_g);
}
if($p_arr[0][1]>3){
	echo "推荐g";
}

//计算Leo对h的评分
$pfz_h = 0;
$pfm_h = 0;
for($i=0;$i<3;$i++){
	$pfz_h += $neighbour_set[$i][1] * $neighbour_set[$i][4];
	$pfm_h += $neighbour_set[$i][1];
	$p_arr[2][0] = 8;
	$p_arr[2][1] = $pfz_h/sqrt($pfm_h);
}
print_r($p_arr);
if($p_arr[0][1]>3){
	echo "推荐h";
}

$p_arr is the recommended array for Leo, its content is similar to the following;

Array ( [0] => Array ( [0] => 6 [1] => 4.2314002228795 ) [1] => Array ( [0] => 7 [1] => 2.6511380196197 ) [2] => Array ( [0] => 8 [1] => 0.45287424581774 ) )

f is the 6th column, the Predict value is 4.23, g is the seventh column, the Predict value is 2.65...

After calculating the Predict values ​​of f, g, h, there are two processing methods: one is to recommend items with a Predict value greater than 3 to Leo, and the other is to sort the Predict values ​​from large to small, and sort the Predict values ​​with the largest values. The first 2 items recommended to Leo. This code was not written.

As can be seen from the above example, the implementation of the recommendation algorithm is very troublesome, requiring looping, judgment, merging arrays, etc. If not handled properly, it will become a burden on the system. There are still the following problems in actual processing:

1. In the above example, we only recommend Leo, and we already know that Leo has not evaluated items f, g, h. If put into an actual system, for each user who needs to make a recommendation, it is necessary to find out which items he has not rated, which is another part of the overhead.

2. The entire table query should not be performed. Some standard values ​​can be set in the actual system. For example: We find the Cos value between Leo and other people in the table. If the value is greater than 0.80, it means that they can be neighbors. In this way, when I find 10 neighbors, I stop calculating the Cos value to avoid querying the entire table. This method can also be used appropriately for recommended items. For example, I only recommend 10 items, and stop calculating the Predict value after recommending them.

3. As the system is used, the items will also change. Today it is fgh, and tomorrow it may be xyz. When the items change, the data table needs to be dynamically changed.

4. Content-based recommendations can be appropriately introduced to improve the recommendation algorithm.

5. Recommended accuracy issues. Setting different standard values ​​will affect the accuracy.

Summary: I think the essential problem is that the efficiency of the algorithm is not high. Continue to study and see if there is a better collaborative filtering recommendation algorithm.

The above is the detailed content of Implementation of php+mysql collaborative filtering algorithm. For more information, please follow other related articles on the PHP Chinese website!