《武汉工程大学学报》 2014年08期
75-78
出版日期：2014-08-31
ISSN:1674-2869
CN:42-1779/TQ
同好推荐算法的实践
0引言当前，书目推荐已经成为图书馆书目检索系统中必不可少的栏目.甚至不止是图书馆，网络上各种各样的读书网址中都会有着书目推荐的专栏，书目推荐专栏已成为各网站争夺读者和点击率的关键所在.因为大众无论是否承认都有着一定的从众心理，这也是同好推荐备受欢迎的原因之一.现在国内外大部分公司都有着各自的推荐算法，例如：Amazon、 Netflix、lastfm、Pandora、Google，对于卓越亚马逊而言，其书目推荐技术使用的是Amazon的同好推荐技术;而Amazon被称为推荐之王，其销量的百分之三十依靠的不是别的，就是它所使用的同好推荐技术带来的，从中可以看出同好推荐算法革新的重要性［1］.通过对手机社区用户图书下载行为进行分析，然后产生相应的图书推荐，从而让用户方便的找到自己喜欢看的书.1同好推荐算法及问题分析所谓同好推荐算法就是通过对用户以往行为的统计分析，利用一些数学算法预测分析出用户在未来一段时间可能的行为策略［2］.当前比较流行的同好推荐算法主要分为两大方式：启发式和基于模型的方式.启发式的方法即对用户行为先进行主观预测再通过实际检验一步步接近用户最真实的状态.而基于模型的方式则是从以往数据出发，通过对用户以往的一些行为数据的统计分析，在本文的书目同好推荐中就是对用户以往阅读书籍的分析［3］，但书目同好推荐不仅仅局限于对单一用户或单一书籍的统计分析，而是把过去所有用户和所有书籍作为统计对象，于是不可避免的庞大数据源就出现了，而且这些数据相互交织，增加了对这些数据分析的难度.怎样高效稳定的得到所需要的结果就成了重中之重.2数据库查询计算的传统算法产生书的推荐（喜欢这本书的人还喜欢什么书）步骤：1）获取还有哪些人看过这本书； 2）获取这些人还看过哪些书；3）计算每本书对应的用户数；4）按每本书对应的用户数倒序输出.产生用户的同好推荐： 获取这个用户看过哪些书； 获取看过这些书的所有用户；获取这些用户都还看过哪些书；计算每本书对应的用户数；按每本书对应的用户数倒序输出.2.1传统算法问题分析传统算法优点：算法容易理解；在支持子查询的数据库容易实现.传统算法缺点：只能在支持子查询的数据库实现，如mssql可以，mysql就不行；每计算一次书的推荐（或用户的推荐），都涉及嵌套查询，而统计数据通常都是很大（这样才准确），导致了计算速度很慢；每次查询结果不能复用.2.2基于矩阵模型的创新算法伴随着大数据时代的到来［4］，传统的查询算法已经远远无法满足当今世界的需求，传统的查询算法中往往伴随着子查询等等，在数据量较大的数据库中往往造成运行速度缓慢等严重问题，改变以往的子查询算法就成为重中之重.2.2.1算法描述例如A、B、C三个用户下载过编号为101的图书，同时A用户又下载过编号为105、109的书，B用户又下载过编号为103、109的书， C用户又下载过编号为102、105、106、109的图书.那么，对A、C两用户而言，101和105这两本书的同好度为2.这里解释下同好度：两书之间的同好度就是同时读过这两本书的用户数［5］.针对编号为101的图书进行矩阵统计，矩阵图的横向和纵向都是书籍编号，按从小到大排列.横向和纵向的交叉点就是表示下载横向编号的书同时下载了纵向编号的书的用户数，即两书之间的同好度.因为同好度是相互的，所以只用了矩阵的上三角来存储.某本书的同好推荐只需要将这些数值倒序排列就可以了.第8期林雪云：同好推荐算法的实践武汉工程大学学报第36卷2.2.2程序实现1）这边考虑用一个字典表来保存两书之间的同好度，字典的键值是【两书籍中的小编号+“$”+两书籍中的大编号】,键值就是两书之间的同好度，如果用二维数组来表示矩阵有两个缺点：其一浪费存储空间，因为上面说明过矩阵的下半部分是没有数据的，其二不方便查找数据，要建立书籍ID和矩阵索引之间的关系才能定位相应的数据.2）要产生一个书籍的推荐可以开始一个循环，开始值为所有书籍的最小编号，结束值为最大编号.3）在循环体产生键值：【两书籍中的小编号+“$”+两书籍中的大编号】.4）记录相关度.5）倒序输出相关度，从而产生推荐.2.2.3算法优点相比在数据库中计算，可以清楚的看到，只要计算一次两书之间的相关度就可以在后面的计算重复使用，可以大大提高计算速度.通过按图书编号从小到大来计算每本图书和其他图书之间的同好度，实验就可以只计算编号比当前编号大的图书的同好度，提高计算速度.2.2.4算法拓展应用用户的同好推荐的实现基于图书同好推荐，本文上述算法已经可以获取每本书的相应的同好推荐，可以算出用户看过的所有书的同好推荐，产生并集，然后按同好度倒序输出\[6\].具体做法如下：(1)假设实验要产生20本书作为某个用户的推荐.(2)假设用户看过10本书.(3)程序产生这10本书相应的同好推荐，每本书对应2本（要排除用户已经看过的书和其他书产生的推荐的书）.(4)对这20本书按同好度倒序输出.另外，还可以用于商品（如食品、服装、电影等）的同好推荐，甚至于计算两物品之间的关联度［7］，用于分析事件发生的影响因素分析.例如:a事件的发生可能由于b或者c事件的发生，实验即可将a,b,c看做3本图书，把a事件发生且b事件发生记为1，从而得到a,b,c三者之间的同好度（即关联度），比较关联度大小，即可知道a事件的主要影响因素\［8\］.3实验评价3.1评价标准评价标准1：数据量时间（平均一条数据所花费的时间）比：P1=(t1-t2)n/t2n=(t1-t2)t1（1）式（1）中n为数据量.P1越大表明传统算法相对于创新算法而言耗时更多.评价标准2：耗时稳定性比：P2=Σ12i=1(t1i-t1)2n-1-Σ12i=1(t2i-t2)2n-1（2）P2越大表明传统算法相对于创新算法而言更加不稳定\［9\］.其中tij中j =1对应传统算法，j =2对应创新算法，i =1...12对应月份分为1...12.3.2实验环境实验使用手机社区用户近一年的下载数据，经过数据清洗、转换后，有效数据集1.2亿行.实验机器：操作系统Win 7，处理器为英特尔酷睿i52500，主频是3.3GHZ，内存为8Gb.3.3实验过程将实验数据按1～12个月的顺序递增，依次测试：1个月，2个月，……，12个月不同数据量下新旧算法的推荐效率，实验输入数据如表1所示.表1实验数据Table 1Experimental data月份〖2〗123456789数据量×1070.140.240.340.440.540.640.740.840.94改进算法的离线计算，计算的结果在后续的推荐中可以重复利用.随机抽取150个用户，计算推荐的平均时间，具体如图1所示，新旧算法耗时表如表2所示，新旧算法P1指标如表3所示，月数与P1的关系如图2所示.图1新旧算法实验分析Fig.1Experimental analysis of the new and old algorithm注：t1t2表2传统算法和创新算法耗时Table 2Timeconsuming of traditional algorithms and innovative algorithms 月份〖2〗123456789101112t11244275188141 2581 7352 1762 8103 0193 6174 1264 492t2125121117113109108105104103101100100n1 2312 1383 0433 9494 8625 7756 6737 5718 4719 39410 30111 208表3传统算法和创新算法P1指标Tabel 3P1 indicators of traditional algorithms and innovative algorithms月份〖2〗123456789101112P102.53.46.210.515.119.72628.334.840.343.9 图2月数与P1的关系Fig.2Relationship of months and P1注：P1由表3可知，当数据量增大时，传统算法的耗时相对于创新算法是线性增长，随着数据量的继续增加，传统算法的耗时将远大于创新算法.由公式（2）可得传统算法与创新算法稳定性对比表，即表4所示.表4传统算法和创新算法稳定性对比Table 4Stability compared to traditional algorithms and innovative algorithms〖2〗平均值方差传统算法2 0932 289 426.5创新算法108.871.2创新算法的耗时平均值仅为传统算法的1/20，说明创新算法的耗时远小于传统算法.同时，创新算法的方差为传统算法的1/32135，说明创新算法的稳定性远远优于传统算法.即创新算法相对于传统算法而言更能长久保持低耗时.3.4实验结果从上述实验结果可以看出：①基于矩阵的创新算法效率明显比传统算法高.②随着数据量的不断增大，传统算法线性下降，而基于矩阵的创新算法，由于可以重复利用计算结果，效率基本一致.③随着数据量的不断增大，创新算法的稳定性远远优于传统算法.4结语根据大数据量下同好度推荐存在的问题，针对传统推荐算法在运算速度及稳定性不足等问题提出了基于矩阵模型的创新算法，该算法改进了传统数据库查询的推荐算法，以提高运行效率.面对的大数据，基于矩阵的创新算法，可以采用离线计算的形式，提前计算物品与物品之间的同好度表.通过实验表明，改进的算法对比传统的推荐算法具有明显的效率优势，不仅在耗时上，更在于改进算法的稳定性上.基于矩阵模型的推荐算法不足在于在第一步新建同好度表时的耗时偏大，对这部分内容的改进也是本法未来的改进方向.致谢 感谢福建省自然科学基金委员会和福建师范大学福清分校科研基金的资助！