摘要: 采用离线式计算推荐给每位用户的电影,采用Item-based算法并做了适当修改,
主要分两部分:

  1. 计算电影的相似度:利用调整的余弦相似度计算方法;
  2. 相似度加权求和:使用用户已打分的电影的分数进行加权求和,权值为用户未打分的各电影与打分的各电影的相似度,然后对所有相似度的和求平均。

系统详细设计

离线计算推荐电影模块

系统所用算法

本系统采用协同过滤(Collaborative Filtering)推荐算法。协同过滤推荐算法分为预测过程和推荐过程,其包括Item-based算法和User-based算法,但经查阅相关资料发现User-based算法存在两个问题:

  1. 数据的稀疏性:一个大型的电影推荐系统会有大量的电影信息,用户已打分的电影可能只占总量的很少一部分,不同用户之间电影打分的重叠性较低,导致算法无法找到一个兴趣用户;
  2. 算法的扩展性:最近邻算法的计算量会随着用户和电影信息数量的增加而增加,不适合信息量大的情况。所以本系统采用了Item-based协同过滤算法,并对其做了适当修改。

计算过程

计算过程分两步:

  1. 计算电影相似度:利用调整的余弦相似度计算方法,公式如下图:
    余弦相似度算法
  2. 电影相似度加权求和:使用用户已打分电影的分数进行加权求和,权值为用户未打分的各电影与打分的各电影的相似度,然后求平均,公式如下图:
    加权求和
    以上部分均采用了多线程技术计算,值得注意的是相似度计算存在很大的冗余,必须去除冗余计算,不然计算量很大,这需要在数据库中建立一个sim表来记录已经计算的的sim(i,j),当下次需要计算sim(i,j)或sim(j,i)可直接从数据库读取而无需重复计算。并且我认为如果R(u,N)值如果比较低,说明用户不喜欢此电影,这条相似度信息可以忽略,这需要设置一个打分阀值。

计算模块流程图:

由于计算量较大,计算模块采用了多线程技术,来提升系统运行效率,如下图为计算模块主线程和子线程的流程图,如图a,图b:
图a

图b

关键代码分析

计算模块采用多线程技术,主线程通过创建子线程来实现大量数据的计算,其中线程状态的监测很有必要,如下面为主线程实现代码:

 1sql="SELECT uid FROM user group by uid";
 2		uidItems=uiddb.executeQuery(sql);	
 3		for(int i=0;i<threadNum;i++){
 4			thCom[i]=new Thread(new thComp(uidItems,i));	
 5			thCom[i].start();
 6		}//for i
 7		boolean thFinished=false;
 8		while(!thFinished){
 9			try{
10				Thread.sleep(sleepTime);
11			}catch(Exception e){//try
12				e.printStackTrace();
13			}//catch();
14			thFinished=true;
15			for(int i=0;i<threadNum;i++){
16				if(thCom[i].isAlive()){
17					//System.out.println(thCom[i].getName()+":"+thCom[i].getState());
18					thFinished=false;
19					break;
20				}//if
21			}//for i
22		}//while(!thFinished)

由于子线程是从主线程创建的ResultSet中读取数据,这就需要子线程互斥的访问临界资源ResultSet,如下面代码所示:

 1public synchronized int getUserID(ResultSet uidItems){
 2		int uid=0;//0 shows that no usrid needs to process
 3		try{
 4			if(uidItems.next()){
 5				uid=uidItems.getInt("uid");
 6			}//if
 7		}catch(Exception e){
 8			e.printStackTrace();
 9		}//catch
10		return uid;
11	}//getUserID()

在为用户A计算要推荐的电影,计算电影i与电影j的相似度sim(i,j)时,可能在为用户B计算要推荐的电影已经计算过,如果再计算一次,会造成计算的冗余,降低了计算效率,使系统性能下降,这需要将将计算的sim(i,j)保存下来,然后需要计算sim(i,j)先判断是否已经计算过sim(i,j)或sim(j,i),如果计算过直接读取,否则计算,本系统中是将sim(i,j)的计算值保存到数据库的sim表中,主要实现代码如下:

 1String sql="SELECT sim FROM sim WHERE midi='"+midi+"' and midj='"+midj+"' or midi='"+midj+"' and midj='"+midi+"'";	
 2		uidItems=uiddb.executeQuery(sql);
 3		//select and fllaowing insert may have problems
 4		try{
 5			if(uidItems.next()){
 6				return uidItems.getDouble("sim");
 7			}//if(uidItems.next())
 8		}catch(Exception e){
 9			e.printStackTrace();
10		}//catch()
11	public synchronized void insertSim(String sql){
12		//here may have some problems
13		recSimdb.executeUpdate(sql);
14	}//insertSim

浏览推荐电影模块

浏览用户推荐电影流程图

浏览电影流程图

关键代码分析   

该模块主要是按推荐指数降序排序显示推荐给每个用户的电影,来满足用户的娱乐需求,提高用户的满意率,此功能主要代码如下所示:

 1public synchronized int getUserID(ResultSet uidItems){
 2		int uid=0;//0 shows that no usrid needs to process
 3		try{
 4			if(uidItems.next()){
 5				uid=uidItems.getInt("uid");
 6			}//if
 7		}catch(Exception e){
 8			e.printStackTrace();
 9		}//catch
10		return uid;
11	}//getUserID()

数据库设计模块

由于电影和用户信息数据量比较大,本系统将数据文件中的数据导入到mysql数据库中,同时增加了一些额外数据表来满足系统的要求,比如保存用户平均打分的avgrating表和降低计算电影相似性冗余的sim表。在经常查询的字段添加了索引,以提高查询速度,在group by字段也添加了索引。下面简单介绍下数据库中各个表结构如下几张图所示:

 1CREATE TABLE IF NOT EXISTS `item` (
 2  `id` int(11) NOT NULL AUTO_INCREMENT,
 3  `mid` int(11) NOT NULL,
 4  `title` varchar(255) DEFAULT NULL,
 5  `releasedate` varchar(50) DEFAULT NULL,
 6  `videoreleasedate` varchar(50) DEFAULT NULL,
 7  `imdburl` varchar(255) DEFAULT NULL,
 8  `unknown` int(11) DEFAULT '0',
 9  `action` int(11) DEFAULT '0',
10  `adventure` int(11) DEFAULT '0',
11  `animation` int(11) DEFAULT '0',
12  `children` int(11) DEFAULT '0',
13  `comedy` int(11) DEFAULT '0',
14  `crime` int(11) DEFAULT '0',
15  `documentary` int(11) DEFAULT '0',
16  `drama` int(11) DEFAULT '0',
17  `fantasy` int(11) DEFAULT '0',
18  `filmnoir` int(11) DEFAULT '0',
19  `horror` int(11) DEFAULT '0',
20  `musical` int(11) DEFAULT '0',
21  `mystery` int(11) DEFAULT '0',
22  `romance` int(11) DEFAULT '0',
23  `scifi` int(11) DEFAULT '0',
24  `thriller` int(11) DEFAULT '0',
25  `war` int(11) DEFAULT '0',
26  `western` int(11) DEFAULT '0',
27  PRIMARY KEY (`id`),
28  UNIQUE KEY `item_mid` (`mid`)
29) ENGINE=InnoDB  DEFAULT CHARSET=gbk AUTO_INCREMENT=11775 ;
1CREATE TABLE IF NOT EXISTS `avgrating` (
2  `usrid` int(11) NOT NULL,
3  `avgRating` double DEFAULT NULL,
4  UNIQUE KEY `avgrating_usrid` (`usrid`),
5  UNIQUE KEY `avgRating_usridAvgRating` (`usrid`,`avgRating`)
6) ENGINE=InnoDB DEFAULT CHARSET=gbk;
1CREATE TABLE IF NOT EXISTS `genre` (
2  `id` int(11) NOT NULL AUTO_INCREMENT,
3  `genre` varchar(50) NOT NULL,
4  `mid` int(11) DEFAULT NULL,
5  PRIMARY KEY (`id`)
6) ENGINE=InnoDB  DEFAULT CHARSET=gbk AUTO_INCREMENT=151 ;
1CREATE TABLE IF NOT EXISTS `info` (
2  `id` int(11) NOT NULL AUTO_INCREMENT,
3  `users_num` int(11) DEFAULT NULL,
4  `items_num` int(11) DEFAULT NULL,
5  `ratings_num` int(11) DEFAULT NULL,
6  PRIMARY KEY (`id`)
7) ENGINE=InnoDB DEFAULT CHARSET=gbk AUTO_INCREMENT=1 ;
1CREATE TABLE IF NOT EXISTS `rating` (
2  `id` int(11) NOT NULL AUTO_INCREMENT,
3  `usrid` int(11) DEFAULT NULL,
4  `itemid` int(11) DEFAULT NULL,
5  `rating` int(11) DEFAULT NULL,
6  `timestamp` int(11) DEFAULT NULL,
7  PRIMARY KEY (`id`),
8  UNIQUE KEY `rating_uidiid` (`usrid`,`itemid`)
9) ENGINE=InnoDB  DEFAULT CHARSET=gbk AUTO_INCREMENT=500001 ;

协同过滤Item-based算法

(1)相似度计算
Item-based算法首选计算物品之间的相似度,计算相似度的方法有以下几种:

  1. 基于余弦(Cosine-based)的相似度计算,通过计算两个向量之间的夹角余弦值来计算物品之间的相似性,公式如下:
    Cosine-based
    其中分子为两个向量的内积,即两个向量相同位置的数字相乘。
  2. 基于关联(Correlation-based)的相似度计算,计算两个向量之间的Pearson-r关联度,公式如下:
    Correlation-based
    其中表示用户u对物品i的打分,表示第i个物品打分的平均值。
  3. 调整的余弦(Adjusted Cosine)相似度计算,由于基于余弦的相似度计算没有考虑不同用户的打分情况,可能有的用户偏向于给高分,而有的用户偏向于给低分,该方法通过减去用户打分的平均值消除不同用户打分习惯的影响,公式如下:
    Adjusted Cosine
    其中表示用户u打分的平均值。

(2)预测值计算
根据之前算好的物品之间的相似度,接下来对用户未打分的物品进行预测,有两种预测方法:

  1. 加权求和
    用过对用户u已打分的物品的分数进行加权求和,权值为各个物品与物品i的相似度,然后对所有物品相似度的和求平均,计算得到用户u对物品i打分,公式如下:
    加权求和

其中为物品i与物品N的相似度,为用户u对物品N的打分。
2. 回归
和上面加权求和的方法类似,但回归的方法不直接使用相似物品N的打分值,因为用余弦法或Pearson关联法计算相似度时存在一个误区,即两个打分向量可能相距比较远(欧氏距离),但有可能有很高的相似度。因为不同用户的打分习惯不同,有的偏向打高分,有的偏向打低分。如果两个用户都喜欢一样的物品,因为打分习惯不同,他们的欧式距离可能比较远,但他们应该有较高的相似度。在这种情况下用户原始的相似物品的打分值进行计算会造成糟糕的预测结果。通过用线性回归的方式重新估算一个新的值,运用上面同样的方法进行预测。重新计算的方法如下:
回归

算法实现(java):

  1import java.sql.ResultSet;
  2import movierec.DB;
  3import movierec.FUN;
  4import movierec.SYS;
  5public class ItemBasedSim {
  6	/**
  7	 * @param args
  8	 */
  9	public int threadNum=5;
 10	public int sleepTime=3000;//ms
 11	public double thresholdRating=2.5;
 12	public int recNum=50;//the num of movies to recommend,which need to be computed
 13	public int RuNNum=20;//
 14	public Thread thCom[];
 15	DB recSimdb=null;
 16	//public static void main(String[] args) {
 17		// TODO Auto-generated method stub
 18		//System.out.println("test");
 19		/*
 20		long startTime = System.currentTimeMillis();
 21		System.out.println(fun.getDateTime()+" starts...");
 22		itemBasedSim ibs=new itemBasedSim (5);
 23		//ibs.sim(3,6);
 24		//System.out.println("sim:"+ibs.sim(5,9));
 25		ibs.compRecDeg();
 26		//ibs.compRecDegUI(1,1);
 27		long finishTime = System.currentTimeMillis();
 28		System.out.println(fun.getDateTime()+" finishs,spent:"+(finishTime-startTime)+"ms");
 29		*/
 30		//System.out.println("spent:"+(finishTime-startTime)+"ms");
 31		/*startTime = System.currentTimeMillis();
 32		ibs.compRecDegUI(2,1);
 33		finishTime = System.currentTimeMillis();
 34		System.out.println("spent:"+(finishTime-startTime)+"ms");*/
 35	//}//main()
 36	public ItemBasedSim(int thNum){
 37		threadNum=thNum;
 38		thCom=new Thread[threadNum];
 39	}//itemBasedSim()
 40	public void compRecDeg(){
 41		//SELECT avg(rating) FROM rating,item WHERE mid=itemid and war=1 group by usrid
 42		DB uiddb=new DB();	
 43		recSimdb=new DB();
 44		ResultSet uidItems=null;	
 45		String sql="delete FROM avgrating";
 46		uiddb.executeUpdate(sql);
 47		sql="insert into avgrating SELECT usrid,avg(rating) avgRating FROM rating group by usrid";
 48		uiddb.executeUpdate(sql);
 49		//sql="delete FROM sim";
 50		//uiddb.executeUpdate(sql);
 51		sql="delete FROM recom";
 52		uiddb.executeUpdate(sql);
 53		sql="SELECT uid FROM user group by uid";
 54		uidItems=uiddb.executeQuery(sql);	
 55		for(int i=0;i<threadNum;i++){
 56			thCom[i]=new Thread(new thComp(uidItems,i));	
 57			thCom[i].start();
 58		}//for i
 59		boolean thFinished=false;
 60		while(!thFinished){
 61			try{
 62				Thread.sleep(sleepTime);
 63			}catch(Exception e){//try
 64				e.printStackTrace();
 65			}//catch();
 66			thFinished=true;
 67			for(int i=0;i<threadNum;i++){
 68				if(thCom[i].isAlive()){
 69					//System.out.println(thCom[i].getName()+":"+thCom[i].getState());
 70					thFinished=false;
 71					break;
 72				}//if
 73			}//for i
 74		}//while(!thFinished)
 75		recSimdb.close_state();
 76		recSimdb.close_connect();
 77		uiddb.close_result();
 78		uiddb.close_state();
 79		uiddb.close_connect();
 80	}//compRecDeg()
 81	public double compRecDegUI(int uid,int iid,int thID,DB mrdb,DB mydb,DB uiddb){
 82		//db mrdb=new db();
 83		String mrsql="SELECT itemid,rating FROM rating WHERE usrid='"+uid+"'";
 84		mrsql+=" and rating>='"+this.thresholdRating+"' limit 0,"+this.RuNNum;
 85		//need to 
 86		ResultSet mrItems=null;
 87		double simUI=0;
 88		double fz=0;
 89		double fm=0;
 90		double pui=0;
 91		//System.out.println("uid="+uid+"  , itemid= "+iid+" , threadID="+thID);
 92		mrItems=mrdb.executeQuery(mrsql);
 93		try{
 94			while(mrItems.next()){				
 95				simUI=sim(iid,mrItems.getInt("itemid"),thID,mydb,uiddb);
 96				fz+=simUI*mrItems.getInt("rating");
 97				fm+=Math.abs(simUI);
 98				//System.out.println(uid+","+iid+"----------2");
 99			}//while(uidItems.next())
100			if(fm!=0)
101				pui=fz/fm;
102			else
103				pui=0;
104			//System.out.println("----------3");
105		}catch(Exception e){
106			e.printStackTrace();
107		}//catch()
108		return pui;
109	}//comRecDegUI()
110	public double sim(int midi,int midj,int thID,DB mydb,DB uiddb){
111		//db mydb=new db();
112		//db uiddb=new db();
113		ResultSet mItems=null;
114		ResultSet uidItems=null;
115		String sql="SELECT sim FROM sim WHERE midi='"+midi+"' and midj='"+midj+"' or midi='"+midj+"' and midj='"+midi+"'";	
116		uidItems=uiddb.executeQuery(sql);
117		//select and fllaowing insert may have problems
118		try{
119			if(uidItems.next()){
120				return uidItems.getDouble("sim");
121			}//if(uidItems.next())
122		}catch(Exception e){
123			e.printStackTrace();
124		}//catch()
125		///String sqlUid="SELECT usrid FROM rating GROUP BY usrid ";
126		String sqlUid="SELECT usrid,avgRating FROM avgrating ";
127		//maybe there are users who has not commented any movie
128		uidItems=uiddb.executeQuery(sqlUid);	
129		int uid=0;
130		double ru=0;
131		double rui=0;
132		double ruj=0;
133		double mid1=0;//(rui-ru)(ruj-ru)
134		double mid2=0;//pow((rui-ru),2);
135		double mid3=0;//pow((ruj-ru),2);
136		try{	
137			while(uidItems.next()){	
138				ru=0;
139				rui=0;
140				ruj=0;
141				uid=uidItems.getInt("usrid");
142				ru=uidItems.getDouble("avgRating");		
143				sql="SELECT rating FROM rating WHERE usrid='"+uid+"' AND itemid ='"+midi+"'";
144				mItems= mydb.executeQuery(sql);
145				if(mItems.next()){
146					rui=mItems.getDouble("rating");
147				}//if(mitems.next())			
148				sql="SELECT rating FROM rating WHERE usrid='"+uid+"' AND itemid ='"+midj+"'";
149				mItems= mydb.executeQuery(sql);	
150				if(mItems.next()){
151					ruj=mItems.getDouble("rating");
152				}//if(mitems.next())
153				//System.out.println("RU="+ru);
154				//System.out.println("RUI="+rui);
155				//System.out.println("RUJ="+ruj);
156				mid1+=(rui-ru)*(ruj-ru);
157				mid2+=Math.pow(rui-ru, 2);
158				mid3+=Math.pow(ruj-ru,2);
159			}//while(uidItems.next())
160			mid2=Math.sqrt(mid2)+Math.sqrt(mid3);
161			if(mid2!=0){
162				mid3=mid1/mid2;
163			}else
164				mid3=0;
165		}catch(Exception e){
166			e.printStackTrace();
167		}//catch
168		sql="INSERT INTO sim (midi, midj, sim,timestamp) VALUES ('"+midi+"','"+midj+"','"+mid3+"','";
169		sql+=System.currentTimeMillis()+thID+Math.random()+"')";
170		//mydb.executeUpdate(sql);
171		//insert may have problems ,because some select no sim at the same time
172		//but have unique index
173		try{
174			insertSim(sql);
175		}catch(Exception e){
176			//
177		}//catch
178		return mid3;		
179	}//sim()
180	public synchronized int getUserID(ResultSet uidItems){
181		int uid=0;//0 shows that no usrid needs to process
182		try{
183			if(uidItems.next()){
184				uid=uidItems.getInt("uid");
185			}//if
186		}catch(Exception e){
187			e.printStackTrace();
188		}//catch
189		return uid;
190	}//getUserID()
191	public synchronized void insertRecom(String sql){
192		recSimdb.executeUpdate(sql);
193	}//insertRecom
194	public synchronized void insertSim(String sql){
195		//here may have some problems
196		recSimdb.executeUpdate(sql);
197	}//insertSim
198	
199	class thComp implements Runnable{	
200		ResultSet uidItems=null;	
201		int thID=0;	
202		int gNum[]=new int[SYS.genre.length];
203		int gNumS=0;
204		public void run(){
205			int uid=0;
206			int mid=0;
207			String isql="";
208			String rsql="";
209			//String orderCol[]={"id","usrid","itemid","rating","timestamp"};
210			double recDeg=0;
211			DB middb=new DB();
212			DB mrdb=new DB();
213			DB mydb=new DB();
214			DB uiddb=new DB();
215			ResultSet midItems=null;
216			int midNum=0;
217			int i=0;
218			int hasRecIid[] = new int[SYS.recNum*2+5];
219			int hRNum=0;
220			while(0!=(uid=getUserID(uidItems))){
221				//here should compute the user's intersting to decide the num of each 
222				//kind to recommend
223			    hRNum=0;
224				gNumS=0;
225				for(i=0;i<SYS.genre.length;i++){		
226					gNum[i]=0;
227					isql="SELECT avg(rating) avgR FROM rating,item WHERE mid=itemid and "+SYS.genre[i]+"=1 and usrid='"+uid+"'";
228					midItems=middb.executeQuery(isql);
229					try{
230						if(midItems.next())
231						gNum[i]=(int) midItems.getDouble("avgR");
232					}catch(Exception e){
233						e.printStackTrace();
234					}//catch
235					gNumS+=gNum[i];
236				}//for i
237				if(gNumS>0){				
238					for(i=0;i<SYS.genre.length;i++){
239						midNum=(int) (gNum[i]/(gNumS*1.0)*SYS.recNum*2);
240						if(midNum>=1){
241							isql="SELECT itemid FROM rating,item WHERE mid=itemid and "+SYS.genre[i]+"=1 and usrid='"+uid+"' and rating>='"+thresholdRating;
242							isql+="' group by itemid order by rating desc limit 0,"+midNum;
243							//System.out.println(isql);
244							//各类间可能会有重复的item							
245							midItems=middb.executeQuery(isql);
246							try{
247								while(midItems.next()){
248									//System.out.println("----");
249									recDeg=0;
250									mid=midItems.getInt("itemid");
251									if(hasRec(hasRecIid,hRNum,mid))
252										continue;
253									hasRecIid[hRNum++]=mid;
254									//System.out.println(thID+":("+hRNum+"):"+uid+","+mid);
255									recDeg=compRecDegUI(uid,mid,thID,mrdb,mydb,uiddb);//very cost time
256									rsql="INSERT INTO recom (id, uid, mid, recdeg) VALUES (NULL,'"+uid+"','"+mid+"','"+recDeg+"')";
257									//System.out.println(rsql);
258									insertRecom(rsql);
259								}//while(iidItems.next())
260							}catch(Exception e){
261								e.printStackTrace();
262							}//catch()
263						}//if(midNum>=1)
264					}//for
265				}else{
266					isql="SELECT itemid FROM rating  where usrid!='"+uid+"' and rating>="+thresholdRating+" group by itemid order by rating desc";
267					isql+=" limit 0,"+SYS.recNum*2;
268					midItems=middb.executeQuery(isql);
269					try{
270						while(midItems.next()){
271							recDeg=0;
272							mid=midItems.getInt("itemid");
273							recDeg=compRecDegUI(uid,mid,thID,mrdb,mydb,uiddb);
274							rsql="INSERT INTO recom (id, uid, mid, recdeg) VALUES (NULL,'"+uid+"','"+mid+"','"+recDeg+"')";
275							//System.out.println(rsql);
276							insertRecom(rsql);
277						}//while(iidItems.next())
278					}catch(Exception e){
279						e.printStackTrace();
280					}//catch()
281				}//else
282			}//while(0!=(uid=getUserID(uidItems)))
283			middb.close_result();
284			middb.close_state();
285			middb.close_connect();
286			uiddb.close_result();
287			uiddb.close_state();
288			uiddb.close_connect();
289			mrdb.close_result();
290			mrdb.close_state();
291			mrdb.close_connect();
292		}//run()
293		public thComp(ResultSet uidItems,int thID){
294			this.uidItems=uidItems;
295			this.thID=thID;
296		}//thComp
297		public boolean hasRec(int hasRecIid[],int hRNum,int iid){
298			boolean flag=false;
299			for(int i=0;i<hRNum;i++)
300				if(hasRecIid[i]==iid){
301					flag=true;
302					break;
303				}//if(hasRecIid[i]==iid)
304			return flag;
305		}
306	}//class cdatatodb
307}

全部代码可在博主的github上查看:https://github.com/panjf2000/mvrecmd


微信公众号

潘建锋

关于版权和转载

本文由 潘建锋 创作,采用 署名 4.0 国际 (CC BY 4.0) 国际许可协议进行授权。
本站文章除注明转载/出处外,均为本站原创或翻译,转载时请务必署名,否则,本人将保留一切追究责任的权利。
署名 4.0 国际 (CC BY 4.0)

转载规范

标题:协同过滤Item-based算法实现电影推荐系统
作者:潘建锋
原文:HTTPS://strikefreedom.top/item-based-movie-recommendation

关于留言和评论

如果您对本文《协同过滤Item-based算法实现电影推荐系统》的内容有任何疑问、补充或纠错,欢迎在下面的评论系统中留言,与作者一起交流进步,谢谢!(~ ̄▽ ̄)~