用python做算法_一文读懂FM算法优势,并用python实现!(附代码)-阿里云开发者社区..._weixin_39972777的博客-程序员ITS203

技术标签: 用python做算法  

介绍

我仍然记得第一次遇到点击率预测问题时的情形,在那之前,我一直在学习数据科学,对自己取得的进展很满意,在机器学习黑客马拉松活动中也开始建立了自信,并决定好好迎接不同的挑战。

为了做得更好,我购买了一台内存16GB,i7处理器的机器,但是当我看到数据集的时候却感到非常不安,解压缩之后的数据大概有50GB - 我不知道基于这样的数据集要怎样进行点击率预测。幸运地是,Factorization Machines(FM)算法拯救了我。

任何从事点击率预测问题或者推荐系统相关工作的人都会遇到类似的情况。由于数据量巨大,利用有限的计算资源对这些数据集进行预测是很有挑战性的。

然而在大多数情况下,由于很多特征对预测并不重要,所以这些数据集是稀疏的(每个训练样本只有几个变量是非零的)。在数据稀疏的场景下,因子分解有助于从原始数据中提取到重要的潜式或隐式的特征。

因子分解有助于使用低维稠密矩阵来表示目标和预测变量之间的近似关系。在本文中我将讨论算法Factorization Machines(FM) 和Field-Aware Factorization Machines(FFM),然后在回归/分类问题中讨论因子分解的优势,并通过python编程实现。

目录

1. 因式分解的直观介绍

2. FM算法如何优于多项式和线性模型

3. FFM算法介绍

4. 在python中使用xLearn库进行算法实现

因式分解的直观介绍

为了直观地理解矩阵分解,我们来看一个例子:假设有一个用户-电影评分(1-5)矩阵,矩阵中的每一个值表示用户给电影的评分(1-5)。

26be75979d975f9600423072c1524e977da0de09.png

从上述表格中我们可以看出,一些评分是缺失的,我们想设计一种方法来预测这些缺失的评分。直观上来讲,利用矩阵分解来解决这个问题的关键是应该有一些潜在的特征决定用户如何评价一部电影。举例来说 - 用户A和B都是演员阿尔·帕西诺的粉丝,那么他们就会对阿尔·帕西诺的电影评分较高。在上述例子中,对特定演员的偏好是一个隐藏的特性,因为我们没有明确地将其包含在评分矩阵中。

假设我们要计算K个隐藏或潜在的特征,我们的任务是找出矩阵P (U x K)和Q (D x K) (U – 用户, D – 电影),使得 P x QT  近似等于评分矩阵R。

498815979dab286a643775c14e7c49b04f228e0e.png

P矩阵的每一行表示用户与不同特征的相关性,Q矩阵的每一行表示该特征与电影同样的相关性。为了得到用户ui对电影dj的评分,我们可以计算对应于ui和dj两个向量的点积。

21869f4ca494b39ac3fe982ffb7af31ba664c443.png

接下来要做的就是求出矩阵P和矩阵Q。我们使用梯度下降算法来计算,目标函数是使用户的实际评分与通过矩阵P和Q估计的评分之间的平方误差最小,这里的平方误差由以下方程求出。

305b49bfb671130aad106d5970881b00b8c516c5.png

现在我们要给pik和qkj定义一个更新规则,梯度下降法中的更新规则是由最小化误差值的梯度来定义的。

63bd5da03d5b4e2d626694d82537a1de774b47c3.png

获得梯度值后,接下来可以定义pik和qkj的更新规则。

0d37e7582cdc567508faeb0c9f7894e2c9341152.png

这里α是控制更新步长的学习速率,使用上述更新规则,我们可以迭代地执行操作,直到误差收敛到最小,同时使用下面的公式计算总的误差,以此来确定什么情况下应该停止迭代。

1b3ccae6688e7b9953060782f9c5ffa00eb73298.png

上述解决方案很简单并且经常会导致过拟合,即现有的评分都被准确预测到,但是不能很好地推广到未知的数据上。为了解决这个问题,我们可以引入一个正则化参数 β,它将分别控制矩阵P和Q中向量“用户-特征”和“电影-特征”,并给出一个更好的评分的近似值。

如果对利用python实现上述功能和相关细节感兴趣,请参考这个链接http://www.quuxlabs.com/wp-content/uploads/2010/09/mf.py_.txt。一旦我们用上述方法计算出了矩阵P和Q,得到的近似评分矩阵如下:

199b76ad49d7beb301dc5a456f96d4c3f52dec4a.png

现在,我们既能够重新生成现有评分,也能对未知的评分进行一个合理的近似。

FM算法如何优于多项式和线性模型

首先考虑一组点击率预测数据的训练示例。以下数据来自相关体育新闻网站(发布商)和体育用品公司(广告商)。

190b00485070d01ac860b6d29ed4ffeb9eede5b8.png

当我们讨论FM或者FFM的时候,数据集中的每一列(比如上述表格中的出版商、广告商等)将被称为一个字段,每一个值( ESPN、Nike 等)都被称为一个特征。

线性或逻辑回归模型在很多问题上表现很好,但缺点是这种模型只能学习所有变量或者特征各自的影响,无法学习变量之间的相互作用。

70cd18c3d3f5f44f69302e7878cb4a523cf1602e.png

在上述等式中,w0、wESPN等代表参数,xESPN、xNike等代表数据集中的各个特征,通过最小化上述函数的对数损失,得到逻辑回归模型。捕获特征之间相互作用的一种方法是使用多项式函数,将每个特征对的乘积作为单独的参数来学习,并且把每一个乘积作为一个独立的变量。

76b505c9055651830f6773eb541c0b1cfae3cf9c.png

这也可以称为 Poly2模型,因为每一项都只考虑了两个特征之间的相互影响。

问题在于,即使面对一个中等大小的数据集,也需要一个庞大的模型,这对存储模型所需要的内存空间和训练模型所花费的时间都有很大的影响;

其次,对于一个稀疏数据集,这种技术不能很好地学习所有的权重或参数,因为没有有足够的训练样本使每一个特征对的权重是可靠的。

救星FM

FM算法解决了成对特征交互的问题。它使我们能够根据每一对特征组合中的可靠信息(隐藏特征)来训练模型,同时在时间和空间复杂度上更有效地实现上述目标。具体来讲,它将成对交互特征作为低维向量的点积(长度为K)进行建模,以下包含了一个二阶因子分解的方程。

1c2e3acc9102263f04afa962b9bc34a251971503.png

FM(K=3)项中每个参数的表示方法如下:

3eb92ded0573b89778571c8afd35a281c21ad805.png

上述等式中,我们分别计算了与2个特征对应的2个长度为3的潜因子的点积。

从建模的角度来看,这是非常强大的,因为每一个特征最后都会转换到一个相似特征被互相嵌套的空间,简而言之,点积基本上表示了潜在特征的相似程度,特征越相近,点积越大。

5c976bffc3e1365ed8d574c66dc8f873a88e02eb.png

对于余弦函数,当 θ是0时,得到最大值1;当 θ是180度,得到-1,所以当 θ接近于0时,相似性最大。

FM算法的另一个巨大优势是能够在线性时间复杂度下使用简单的数学方法计算模型中成对特征的相互作用。如果你想进一步了解具体的实现步骤,请参考链接中关于FM算法的原始研究论文。

https://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf

示例:FM算法性能优于 POLY2算法的演示

考虑以下一组虚构的点击率数据:

af2797035014750f9ffa4f72ba43ca3bd871a838.png

这个数据集由作为发布者的体育网站和体育用品广告商构成。广告是以弹出的方式来显示的,用户可以选择点击广告或者关闭广告。

特征对(ESPN,Adidas)只有一个负的训练数据,那么在Poly2算法中,这个特征对可能会学到一个负的权重值wESPN,Adidas;而在FM算法中,由于特征对(ESPN,Adidas)是由wESPN·wAdidas决定的,而其中的wESPN和wAdidas分别是从其他特征对中学到的(比如(ESPN,Nike),(NBC,Adidas)等),所以预测可能更加精确。

另一个例子是特征对(NBC,Gucci)没有任何训练数据,对于Poly2算法,这个特征对的预测值为0;但是在FM算法中,因为wNBC和wGucci可以从其他特征对中学到,所以仍然有可能得到有意义的预测值。

FFM算法介绍

57b831a65db7fa2f26af464243e922fec1a37b10.png

为了理解FFM算法,我们需要认识field的概念。field通常是指包含一个特定特征的更广泛的类别。在上述训练示例中,field分别指发布者(P)、广告商(A)和性别(G)。

在FM算法中,每一个特征只有一个隐向量v,来学习其他特征带来的潜在影响。以ESPN为例,wESPN被用来学习特征Nike(wESPN·wNike)和Male(wESPN.wMale)之间的潜在作用。

但是,由于ESPN和Male属于不同的field,所以对特征对(ESPN,Nike)和(ESPN,Male)的起作用的潜在作用可能不同。FM算法无法捕捉这个差异,因为它不区分field的概念,在这两种情况中,它会使用相同参数的点积来计算。

在FFM算法中,每个特征有若干个隐向量。例如,当考虑特征ESPN和Nike之间的交互作用时,用符号wESPN,A来表示ESPN的隐藏特征,其中A(广告商)表示特征Nike的field。类似的,关于性别的field的一个重要的参数wESPN,G也会被学习到。

8071061884cb5664252d5e1e4cc8699e3859f758.png

事实证明,FFM算法对获得由 Criteo、Avazu、Outbrain举办的点击率(CTR)比赛第一名是至关重要的,同时也帮助赢得了2015年RecSys挑战赛的三等奖。关于点击率数据集可以从Kaggle获得。

在python中使用xLearn库进行算法实现

一些在python中实现FM & FFM的最流行的库如下所示:

67da5673df4da16e81bdcec5f6785300b592b79f.png

为了在数据集上使用FM算法,需要将数据转换为libSVM格式。以下为训练和测试的数据文件格式:

:: …

3b01e42c374dfb178e0f5d5c46e71d244898fd67.png

在增加了field的概念之后,每个特征被唯一编码并被赋值,上述图中,特征ESPN用1表示,特征Nike用2表示,以此类推。每一行包含一个等效的训练示例并以“\ n”或换行符结尾。

对于分类(二进制/多类),是一个指示类标签的整数。

对于回归,是任何实数的目标值。

测试文件中的标签仅用于计算准确度或误差,未知的情况下可以用任何数值填写第一列。

同样,对于FFM算法,需要将数据转换为libffm格式。在这里,我们也需要对field进行编码,因为该算法需要field的信息来学习。格式如下:

:::: …

db510639dac16f07439889d9460619b556c45598.png

有关数值特征的重要说明

数值特征需要被离散化(通过将特定数值特征的整个范围分成较小的范围并且分别对每个范围进行标记编码而转换为分类特征),然后如上所示转换为libffm格式。

另一种可能性是添加一个与特征值相同的虚拟field值,它将是该特定行的数值特征(例如,具有值45.3的特征可以被变换为1:1:45.3)。 但是虚拟field值可能不包含任何信息,因为它们仅仅是这些数值特征的复制品。

xLearn

最近推出的xLearn库提供了一个在各种数据集上实现FM和FFM模型的快速解决方案。 它比libfm和libffm库快得多,为模型测试和调优提供了更好的功能。

e35f4048f33db8bb3e81e603385c1dadafeb6320.png

在这里,我们将用一个例子来说明FFM算法,数据来自Criteo点击率预测挑战赛中CTR数据集的一个微小(1%)抽样。 你可以从这里[Office1] 下载这个数据集。

但首先我们需要将其转换为xLearn所需的libffm格式以拟合模型。 以下函数将标准数据帧格式的数据集转换为libffm格式。

df = Dataframe to be converted to ffm format

Type = Train/Test/Val

Numerics = list of all numeric fields

Categories = list of all categorical fields

Features = list of all features except the Label and Id

12d9bf891abe681a2793eb572c1790ee3e921275.png

xLearn可以直接处理csv以及libsvm格式的数据来实现FM算法,但对FFM算法而言,我们必须将数据转换为libffm格式。

一旦我们有了libffm格式的数据集,就可以使用xLearn库来训练模型。

类似于任何其他机器学习算法,数据集被分成一个训练集和一个验证集。xLearn使用验证/测试对数损失来自动执行提前停止的操作,并且我们还可以在随机梯度下降的迭代中为验证集设置其他的监控指标。

下面的python脚本可以用于在ffm格式的数据集上使用xLearn来训练和调整FFM模型的超参数。

aba257bcbfe3316f8f877a7b15585049d90e3f45.png

该库还允许我们使用cv()函数进行交叉验证:

ae60e5853136500a8ef62706487d913c2c5f33f4.png

可以使用以下代码片段对测试集进行预测:

19d2d11463592b7fe03e7b6d91da91e55ef3faec.png

结语

在这篇文章中,我们已经演示了对一般分类/回归问题的因式分解的用法。如果您在执行这个算法的过程中遇到任何问题请及时告知我们。有关xLearn详细文档将在这个链接中给出,并会得到定期更新和支持。

原文发布时间为:2018-01-17

本文作者:ANKIT CHOUDHARY

本文来自云栖社区合作伙伴“数据派THU”,了解相关信息可以关注“数据派THU”微信公众号

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_39972777/article/details/110347421

智能推荐

手机用户的GSP轨迹数据分析_适当喝点的博客-程序员ITS203_gbsmot 轨迹

       目前,手机已经成为我们生活的必需品。服务商可以很容易通过手机采集到我们日常生活的GPS轨迹数据,图1为用户GPS轨迹数据示例,其采集数据的时间间隔为5秒。直接观察这些数据,我们只能发现用户经过某些地点,却不能确定用户是否在这些地点停留过。 图1用户GPS轨迹数据示例        那么,如何通过分...

PyTorch:基于FastAI的猫狗识别_yanqs_whu的博客-程序员ITS203

背景上次自己用PyTorch对AlexNet进行猫狗识别取得了不错效果。后续我又继续使用Resnet50进行猫狗分类,但是却没有取得较好的效果,想来还是自己炼丹的技巧太差了。因此,后续决定使用FastAI进行训练(FastAI封装了很多炼丹技巧),最后效果还不错,Kaggle的分数为0.05779,已经可以挤进前100了;相比上次,效果还是很不错的。代码(基本抄的参考链接)https:/...

citrixreceiver云桌面系统_基于Citrix的云桌面方案_weixin_39711441的博客-程序员ITS203

基于Citrix的云桌面方案①刘夏1,孙鹏1,霍旭轮1,陈明锐2【摘要】由于传统IT网络架构不相同,移动办公日渐增多,远程的管理和维护也更加困难,提出一种基于Citrix的云桌面解决方案,该方案对用户终端设备统一管理维护,使桌面系统和应用安全可靠,降低了桌面系统的运行与维护成本,满足企业对桌面的集中管理;同时,云桌面给用户提供了个性化的桌面,随时随地多样的访问方式,提升了桌面系统的服务水平和业务连...

沃尔什函数 与 沃尔什-哈达玛变换_路人甲ing..的博客-程序员ITS203_哈达玛变换

图像处理中有许多变换常常选用方波信号或者它的变形。沃尔什函数是一组矩形波,其取值为1和-1,非常便于计算机运算。沃尔什函数有三种排列或编号方式,以哈达玛排列最便于快速计算。采用哈达玛排列的沃尔什函数进行的变换称为沃尔什-哈达玛变换,简称WHT或直称哈达玛变换。沃尔什函数沃尔什函数有三种不同的函数定义,但都可由拉德梅克函数构成。1、按沃尔什排列的沃尔什函数...

Fire! -_-lyslyslys的博客-程序员ITS203

Joe works in a maze. Unfortunately, portions of the maze have caught on fire, and the owner of the maze neglected to create a fire escape plan. Help Joe escape the maze. Given Joe’s location in the ma...

IEEE 754 的标准对浮点数的处理_Car12的博客-程序员ITS203_ieee754增大位数提高浮点范围

参考文章:https://blog.csdn.net/weixin_42066185/article/details/88559936作者在工作中现在就面临这个浮点数通过modbus协议向上位机传输的问题的存在,遇到的是,我们应该怎么样合适的处理这个float 4个bytes 的数据,下面总结一下 个人的调研的结果:通过网上的调研结果有下面的两种的解决的方案:方案一:通过将你所得到的带小数的放大一定的倍数,都变成整数进行处理,例如:3.24 --放大100 变成 324 ,然后...

随便推点

MNIST手写数字数据集读取方法_Long仁的博客-程序员ITS203_mnist数据集怎么读

MNIST是一个非常有名的手写体数字识别数据集,在很多资料中,这个数据集都会被用作深度学习的入门样例。 数据集下载网址:http://yann.lecun.com/exdb/mnist/ 数据集简介: 1、共有4数据集,下载之后并将其解压保存在磁盘中(最好放在你代码执行目录下,方便后期使用。)如新建一个文件夹D:*****\MNIST_data存放数据。 train-images-idx3...

CSDN代码块显示颜色_qq_44388958的博客-程序员ITS203

很多刚开始玩CSDN的程序猿肯定都会有这样一个问题,为什么看别人的博客中的代码都是有颜色的,而自己的代码块却是没有颜色的比如这样是没有颜色的<body><input type="button" value="点击" id="btn"><input type="button" value="干掉第一个按钮的事件" id="btn2"></bod...

Android 动画实战_阎楠的博客-程序员ITS203

前言通过之前的《Android 动画总结》,对常用的Android动画有了一个整体认识。但是,之前的内容都是概念性的,所列的demo也没有实际意义。这里就通过两个实例了解一下如何在 实际开发中运用Android 动画来实现一些良好的用户体验。

操作系统06-临界区_zhc_24的博客-程序员ITS203

交错输出的 没有绝对情况的 如果同时访问共享的数据可能会破坏数据。 对这样的事情加上防范! 并发的程序访问共享的数据一定要注意。 对一些问题敏感的洞察生产消费者问题: 生产者往缓冲区放东西 消费者从缓冲区拿东西 ++ – 切换的可能 count++ 在汇编指令拆分为: register1 = count register1 = register1 + 1 count = r

360数科2020年4季度财报:全年收入上涨47.1%,继续领跑全行业_LeiSheCaiJing的博客-程序员ITS203

3月16日,360数科(Nasdaq:QFIN)发布2020年第4季度及全年未经审计的财务报告。360数科凭借稳健的业绩增长和卓越的风控表现,继续领跑市场。2020财年,360数科实现收入135.64亿元,较2019年92.2亿元增长47.1%;非美国会计准则(Non-GAAP)下净利润为37.97亿元,较2019年27.52亿元增长38%。稳健增长,再创轻资本战略里程碑财报显示,360数科4季度促成交易总额690.45亿元,同比增长29%;在2020年全年促成交易2467.58亿元,较2019年19

用grunt构建seajs项目_kyfxbl的博客-程序员ITS203

step by step介绍了使用纯grunt构建seajs项目的步骤

推荐文章

热门文章

相关标签