- 1 -
中国科技论文在线
推荐算法FM中基于特征块结构的算法设计
朱伯程，张闯**
作者简介：朱伯程（1989-），男，硕士研究生。主要研究方向：数据挖掘、推荐系统
通信联系人：张闯（1975 ），男，副教授，主要研究方向：用户检索行为建模、机器学习等
（北京邮电大学模式识别实验室,北京 100876）
5 摘要：在一般推荐算法的预测模型中都会涉及特征项矩阵，而许多诸如线性回归、支持向量
机等机器学习方法都依此进行运算。一些特征之间含有很强的关联，往往一起伴随出现，这
会使特征项矩阵非常巨大从而导致算法非常耗时甚至不可计算。为此，本文在推荐算法 FM
的特征块结构基础上引入索引映射方法，通过用简单的索引值代替重复出现的特征块，同时
快速设计出映射函数，达到“压缩”特征项矩阵的目的，从而加速算法运算过程，提高算法10
效率。本文最后通过在百度电影推荐大赛真实数据集上的实验，可以证明该方法能够在不减
弱算法有效性的前提下提高算法设计的效率。
关键词：推荐系统；索引映射法；FM；特征块；机器学习
中图分类号：TP311
15
Design Index Model Based Block structure in Factorization
Machines
ZHU Bocheng, ZHANG Chuang
(School of Information & Communication Engineering,Beijing University of Posts &
Telecommunications,Beijin 100876) 20
Abstract: The most common predict model in recommend system is to use design
machine learnning methods such as linear regression, support vector rely on this representation.
However,when some feature has strong relational patterns, especially relations with high
cardinality, the design matrix can get very large which can make learning and prediction slow or
even work solve this issue by introducing Index mapping method based on Block 25
Structure in Factorization Machine,which use a simple index take the place of repeating patterns in
the design matrix, to achieve "compression" desigin matrix purposes. Empirically,it is shown on
baidu movie datasets that index mapping method can improve design efficiency without
weakening the Factorization Machine algorithm.
Key words: recommend system;index mapping method;Factorization Machines;Block 30
Structure;machine learning
0 引言
推荐系统是预测分析领域的一种具体应用，无论商业还是学术研究中推荐算法都有着广
泛的应用前景。 35
主流的推荐算法思想基本是选择出合适的特征项变量组成特征项向量（feature vector），
然后使用机器学习方法进行训练获得模型，最后使用这些模型去预测。这些算法的时间复杂
度依赖于特征项向量的大小，其中最好的训练模型方法的复杂度是线性时间复杂度。在大数
据时代的今天，特征项向量组成的特征项矩阵（design matrix）非常巨大。因此由特征项向
量组成特征项矩阵就将更加庞大，即使用线性复杂度的算法其运行时间也是不可忍受的，甚40
至还因内存问题导致程序崩溃。
推荐算法 FM 中的特征块结构[1]（Block Structure）机制，能够“压缩”特征项矩阵，降
低算法运行复杂度，从而提高算法的效率。然而计算特征块结构和映射函数有多种多样的方
- 2 -
中国科技论文在线
式，本文为此引入索引映射方法，旨在充分降低不同特征项之间的相关性，同时快速求解出
特征项矩阵和映射函数。同时，所引入的索引映射方法还能简化推荐系统的设计过程，为其45
他基于特征选择的算法提供新的思路。
本文第 1 节介绍推荐算法 FM 和特征块结构机制，第 2 节阐述索引映射方法并介绍在索
引映射方法下推荐算法的具体设计步骤，第 3 节介绍数据集的获取、分析统计以及在索引映
射方法下推荐算法的效果，通过多组对照试验，分析不同的特征项选择对推荐结果的影响；
第 4 节是对本文工作的总结和展望。 50
1 FM 算法和特征块结构
到目前为止关于推荐算法的研究很多，比如基于用户/物品的协同过滤算法，利用机器
学习的潜语义模型、矩阵分解模型，还有基于图的推荐模型等等。基于矩阵分解模型的推荐
算法，比如 SVD++[2]、LFM、SVDFeature 等等在推荐比赛中发挥了重要的作用。
由 Steffen Rendle 提出的 FM[3]（Factorization Machines）也属于这类推荐模型，该模型55
借助随机梯度下降法（SGD）和蒙特卡罗算法（MCMC）训练模型，在这些推荐比赛（比
如 KDD Cup 2012[4]）中都取得优异的成绩。
FM 算法
FM 算法的本质是通过机器学习的方法训练线性回归[5]模型，回归模型的数据基础是特
征项向量。d-维的 FM 模型定义为： 60
1 1
0 ,
1 1 1 1 11
l
j j
l l
kl ln d n n
l
i i i i f
i l i i i fj j
y x w w x x v
其中的 y(x)就是目标函数，在这个例子中就是电影评分项；x 是特征项向量，在这个例子中
是各属性列形成的值；式中 l-阶的交互作用由 PARAFAC 模型[6]依据参数：
0,
ll n k
lV R k N
分解得来的。特别地，当 d = 2 时，上述的模型表达式退化为： 65
0
1 1 1
,
n n n
i i i j i j
i i j i
y x w w x v v x x
其中需要训练获得的参数有：
0 , ,
n n kw R w R V R
这个 2 维 FM 模型包含了所有单个因子和任意两个因子之间的相互作用的影响。
特征块结构 70
为减少特征项向量中的重复，可以在 FM 模型中引入特征块结构（Block Structure）。
其定义如下：
令 1 2, ,....B B ，若中的每一个 ,i iB BiB X 都包含一个特征项矩阵
B Bi i
iB n pX R
和一个从原特征项矩阵 X 到特征项矩阵的映射函数 : 1,..., 1,..,iB Bn n ，且原特征项
矩阵中的每一行都可以表示为： 75
1 1 1 2 2 21 1 1 1 2 2 2 2,1 ,2 , ,1 ,2 ,, ,... , , ,..., ,...B B B B B B B BB B B B B Bi i i i p i i i px x x x x x x
那么就称集合是原特征项矩阵的一个特征块结构结构表示法，集合里面的每个特征项矩
- 3 -
中国科技论文在线
阵 iB 都被称为子特征块。
从原特征项矩阵 X 中找出特征块的过程，其实就是在完整的特征项矩阵 X 抽取出其中
重复的模块的过程，此过程中形成若干个子特征项矩阵（ 1 2,B BX X ...），同时用子特征矩阵80
中的相应行号（ iB ）来代替原特征项矩阵中的内容。
使用特征块结构表示法能够有效地“压缩”特征项矩阵，同时还能提高运算效率[1]，其
算法复杂度就成为：
Z i
i
B
Z
B
N n N X
之所以使用块结构表示法能提高运算速率，是因为大数据集中这些子特征项矩阵的大小85
总和会远远小于原特征项矩阵，因此在降低空间复杂度的同时也降低了时间复杂度。这跟数
据压缩的思想一致。
2 索引映射方法
FM 算法的特征块结构的构造方法多种多样，相应映射函数也就随之不同。为更快获取
特征块和映射函数，本文提出索引映射方法，依据数据库建模中所用到的规范化过程来构建90
特征块。该方法步骤如下：
1）对训练数据集进行数据库规范建模，设计出 N 张属性表和 1 张评分表，这张评分表
中存储的都是属性表的外键。
2）N 张属性表对应 N 个子特征块结构，每个块结构都可以由这张表唯一确定。假设属
性表 iB 的有
iBn 行 iBp 列，让主键取值从小到大排序后存入的数组，记该排序数组 iBI 。则95
由该表可直接获得子特征块矩阵
B Bi i
iB n pX R ：
,: ,:i iB Bi kX k B I
3）映射函数通过结合评分表 S 的外键和 N 张属性表的索引获得。相应的映射函数
. :, ,i iB B ik I indexOf S k index B k
其中 indexOf 是根据数值查找在数组中的位置操作，即映射函数可以直接根据评分表中的外100
键索引值在对应属性表的位置获得，位置标号从 0 开始。由于 iBI 是排序数组，能够非常迅
速地通过二分查找法（ 2logO n ）获得位置。从而有：
1 1 2 2,1 , ,2 ,..., ,1 , ,2 ,....ix index B index B index B index B
通过上述的三个步骤所获得的子特征块 ,i iB BiB X 符合子特征块结构的定义。因子特征
块的构造、映射函数函数的计算都依据属性表的索引值，故而将该方法称为索引映射方法。 105
3 实验分析
在实验环节，本文选用百度电影推荐系统算法大赛中的数据集1。首先对数据集进行分
析、统计，继而按照索引映射的方法构建出特征结构块，最后使用 FM 算法预测结果并分析。
1
- 4 -
中国科技论文在线
数据集描述
该数据集统计出的结果见表 1，从这些统计项发现，假如用户看过的电影都评过分，那110
么也只有占理论评分的 9565684/(149553*10716) = %；而实际的评分占历史观看记录
的比例为 1262741/9565684 = % ，可见大部分的用户都没有观影后评分的习惯，且可以
大致看出该数据集中的评分记录非常稀疏。
表 1 训练数据集统计表
统计项 数量
用户数 149553
电影数 10716
标签数量 1129
总观看次数 9565684
用户评分数 1262741
好友关系数量 143670 115
构建特征块结构和映射函数
按照索引映射方法，根据数据按规范化方式构造出表。最后会获得两张属性表，User 表
（见图 1）和 Movie 表（见图 2），这两张表符合数据库设计的第三范式；还有一张评分表
（Score 表，见图 3），符合数据库的第二范式。在数据形成表的过程中，按照前面介绍的
索引映射方法能快速构造出特征结构块。 120
User
userid friend history
103 104，106 1004，1005，1006，1008
104 105 1001，1008，1009
105 103，106 1001，1002，1009
… … …
图 1 User 表的示意图，表中的数据为示例用，并非真实数据
Movie
movieid tag
1001 11，12
1002 11，,13
1003 14，15
1004 13，16
… …
图 2 Movie 表的示意图，表中的数据为示例用，并非真实数据
125
- 5 -
中国科技论文在线
Score
userid movieid score
103 1001 4
103 1002 5
103 1003 4
104 1002 4
105 1003 3
106 1004 4
… … …
图 3 Score 表的示意图，表中的数据为示例用，并非真实数据
为了测试算法的有效性，我们将数据集中随机抽选 10%作为测试集，剩下的 90%作为训
练集，用于算法的模型训练。本实验基于 AMD Athlon™ II Dual-Core M340 ，
内存的环境，模型训练借助 libFM2工具包[7]实现。 130
4 实验结构分析
本文选用均方根误差 RMSE （Root-mean-square deviation）作为评价指标：
2
1
ˆ
n
ui ui
i
r r
RSME
n
实验中使用三组特征项集合，每一组分别使用普通的 FM 算法和使用特征块结构的 FM 算法
（FM-BS）进行模型训练，因此总共有六种情况。实验中无论是 FM 算法还是 FM-BS 算法135
都使用 MCMC[8]方法（实际过程中，还可以使用 ALS[9]方法进行训练），取 k=4（即潜在关
系维度/模型复杂度）。实验的结果（参见表 2）中 RMSE 一列表明，FM 模型和 FM-BS 模
型的评价结果是等价的，而且都随着特征项的增多 RMSE 逐渐减小，不过相应的运算时间
也相应增加；而从复杂度 Nz、libFM 迭代一次所花费的时间可以看出，FM-BS 模型的时间
复杂度和空间复杂度明显优于 FM 模型。 140
表 2 用数据集训练 FM 模型时参数 k=4，皆使用 MCMC 方法
特征项 表示法 复杂度Nz
libfm迭代一次
时间(sec)
RMSE
X 26,305,881 273
B 2,794,044 21
X 41,659,667 483
B 3,795,899 37
X 713,258,318
本机内存不够
不能运算
-
B 13,361,583 128
user,movie,tags
user,movie,tags
,friends
user,movie,tags,
friends,history
从图 4 中可以看到，在含有 history 特征项的第三组数据中，特征块结构的运用对空间/
时间复杂度优化的效果最明显。这是因为占有原特征项矩阵主要比例的 history 特征项压缩
比约为 71，与图 4 中的 : 比列相接近。这也表明通过特征块结构，特征块抽取145
原始矩阵的重复项能力越强，那么优化效果就越明显。
2
- 6 -
中国科技论文在线
图 4 实验中三种组合中，FM 模型和 FM-BS 模型的复杂度对比图。
从实验分析可以看到，使用索引映射方法获取的特征块矩阵和映射函数是符合 FM 模型
中特征块结构的定义的，能够直接用于 FM-BS 模型中；而基于数据库规范的索引映射方法，150
能够最大程度的抽取原始矩阵的重复项，因此能够在保证 FM-BS 模型的有效性的前提下简
化设计流程，提高设计效率。
5 结论
本文所提出的索引映射方法能利用数据库规范化标准简化特征块结构的构造过程，同时
可以快速地计算出用于 FM 算法的特征块矩阵和映射函数，从而在不减弱算法有效性的前提155
下提高算法设计的效率。
在接下来的工作中，考虑到索引映射方法是用于构造基于特征块结构，因此希望未来能
将索引映射方法应用到其他当前主流的基于特征提取的推荐算法中，比如 SVD++、
SVDFeature。通过适当地修改推荐算法，使之在数据库的基础上获取分布式并行运算的能力，
进一步提高算法的高效性和可实施性。 160
[参考文献]
[1] Steffen Factorization Machines to Relational Data[A].In Proceedings of the 39th international
conference on Very Large Data Bases[C], Trento, Italy.
[2] Y. Koren. Factorization meets the neighborhood: a multifaceted collaborative filtering model[A]. In KDD
'08:Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data 165
mining[C],pages 426-434, New York, NY, USA, 2008. ACM.
[3] S. Rendle. Factorization machines[A]. In Proceedings of the 2010 IEEE International Conference on Data
Mining[C], ICDM '10, pages 995-1000, Washington, DC,USA, 2010. IEEE Computer Society.
[4] Y. Niu, Y. Wang, G. Sun, A. Yue, B. Dalessandro,C. Perlich, and B. Hamner. The tencent dataset and
KDD-Cup'12[A]. In KDD-Cup Workshop[C], 2012. 170
[5] H.-F. Yu, C.-J. Hsieh, K.-W. Chang, and C.-J. linear classification when data cannot fit in
memory[A]. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data
mining[C], KDD '10, pages 833-842, New York, NY,USA, 2010. ACM.
[6] R. A. Harshman, "Foundations of the parafac procedure: models and conditions for an 'exploratory' multimodal
factor analysis"[J].UCLA Working Papers in Phonetics, pp. 1-84, 1970. 175
[7] S. Rendle. Factorization machines with libFM[J]. ACM Trans. Intell. Syst. Technol., 3(3):57:1-57:22, May
2012.
[8] R. Salakhutdinov and A. Mnih. Bayesian probabilistic matrix factorization using Markov chain Monte
Carlo[A].In Proceedings of the 25th international conference on Machine learning[C], ICML '08, pages 880-887,
New York, NY, USA, 2008. ACM. 180
[9] I. Pil a´szy, D. Zibriczky, and D. Tikk. Fast als-based matrix factorization for explicit and implicit feedback
datasets[A]. In RecSys ’10: Proceedings of the fourth ACM conference on Recommender systems[C], pages 71–78,
New York, NY, USA, 2010. ACM.
