精华内容
下载资源
问答
  • FM算法python实现

    千次阅读 2018-07-03 14:14:53
    在计算广告中,CTR预估(click-through rate)是非常...1、FM 算法模型: 2、FM交叉项求解过程 代码简单实现: 添加依赖项: from __future__ import division from math import exp import pandas as pd f...

    在计算广告中,CTR预估(click-through rate)是非常重要的一个环节,对于特征组合来说,FM(因子分解机)是其中较为经典且被广泛使用的模型。
    1、FM原理
    =>重点内容解决稀疏数据下的特征组合问题

    1. 可用于高度稀疏数据场景
    2. 具有线性的计算复杂度

         对于categorical(类别)类型特征,需要经过One-Hot Encoding转换成数值型特征。CTR/CVR预测时,用户的性别、职业、教育水平、品类偏好,商品的品类等,经过One-Hot编码转换后都会导致样本数据的稀疏性。特别是商品品类这种类型的特征,如商品的末级品类约有550个,采用One-Hot编码生成550个数值特征,但每个样本的这550个特征,有且仅有一个是有效的(非零)。由此可见,经过One-Hot编码之后,大部分样本数据特征是比较稀疏的(即特定样本的特征向量很多维度为0),同时导致特征空间大。(对于每一个特征,如果它有m个可能值,那么经过独热编码后,就变成了m个二元特征(取值0或1)。并且,这些特征互斥,每次只有一个激活。因此,数据会变成稀疏的.) sklearn中preprocessing.OneHotEncoder实现该编码方法。
         通过观察大量的样本数据可以发现,某些特征经过关联之后,与label之间的相关性就会提高。例如,“USA”与“Thanksgiving”、“China”与“Chinese New Year”这样的关联特征,对用户的点击有着正向的影响。换句话说,来自“China”的用户很可能会在“Chinese New Year”有大量的浏览、购买行为,而在“Thanksgiving”却不会有特别的消费行为。这种关联特征与label的正向相关性在实际问题中是普遍存在的,如“化妆品”类商品与“女”性,“球类运动配件”的商品与“男”性,“电影票”的商品与“电影”品类偏好等。因此,引入两个特征的组合是非常有意义的。(我的理解:个性化特征)

    一般的线性模型为
    这里写图片描述
    从上面的式子很容易看出,一般的线性模型压根没有考虑特征间的关联(组合)。为了表述特征间的相关性,我们采用多项式模型。在多项式模型中,特征xi与xj的组合用xixj表示。为了简单起见,我们讨论二阶多项式模型。具体的模型表达式如下:
    这里写图片描述 (1)
    上式中,n表示样本的特征数量,xi表示第i个特征。
    与线性模型相比,FM(Factorization Machine)的模型就多了后面特征组合的部分。
    从公式(1)可以看出,组合特征的参数一共有 n(n−1)/2 个,任意两个参数都是独立的。然而,在数据稀疏性普遍存在的实际应用场景中,二次项参数的训练是很困难的。其原因是,每个参数 wij 的训练需要大量 xi 和xj都非零的样本;由于样本数据本来就比较稀疏,满足“xi 和 xj 都非零”的样本将会非常少。训练样本的不足,很容易导致参数 wij 不准确,最终将严重影响模型的性能。
    类似地,所有二次项参数W i,j可以组成一个对称阵W,那么这个矩阵就可以分解为 W=VVT,V的第i行便是第i维特征的隐向量,则FM的模型方程为
    这里写图片描述

    2、FM交叉项求解过程
    这里写图片描述
    对表达式进行化简,可以把时间复杂度降低到O(kn)
    第一步是一个矩阵(矩阵中所有元素求和)减去对角线部分,然后除以2。多项式部分的计算复杂度是O(kn).即FM可以在线性时间对新样本作出预测

    3、实现步骤
    这里写图片描述

    代码简单实现:

    添加依赖项:

    from __future__ import division
    from math import exp
    import pandas as pd
    from numpy import *
    from random import normalvariate
    from datetime import datetime
    from sklearn import preprocessing

    读取数据:

    def load_train_data(data):
        global min_max_scaler
        data = pd.read_csv(data)
        labelMat = data.ix[:,-1]* 2 - 1
        X_train = np.array(data.ix[:, :-1])
        min_max_scaler = preprocessing.MinMaxScaler()
        X_train_minmax = min_max_scaler.fit_transform(X_train)
        return X_train_minmax,labelMat
    
    def laod_test_data(data):
    
        data = pd.read_csv(data)
        labelMat = data.ix[:, -1] * 2 - 1
        X_test = np.array(data.ix[:, :-1])
        X_tset_minmax = min_max_scaler.transform(X_test)
        return X_tset_minmax, labelMat

    定义sigmod函数:

    
    def sigmoid(inx):
        return 1. / (1. + exp(-max(min(inx, 10), -10)))

    模型训练:

    def FM_function(dataMatrix, classLabels, k, iter):
        m, n = shape(dataMatrix)
        alpha = 0.01
        w = zeros((n, 1))
        w_0 = 0.
        v = normalvariate(0, 0.2) * ones((n, k))
        for it in xrange(iter):
            print it
            for x in xrange(m):
                inter_1 = dataMatrix[x] * v
                inter_2 = multiply(dataMatrix[x], dataMatrix[x]) * multiply(v, v)
                interaction = sum(multiply(inter_1, inter_1) - inter_2) / 2.
                p = w_0 + dataMatrix[x] * w + interaction  #
                loss = sigmoid(classLabels[x] * p[0, 0]) - 1
                w_0 = w_0 - alpha * loss * classLabels[x]
                for i in xrange(n):
                    if dataMatrix[x, i] != 0:
                        w[i, 0] = w[i, 0] - alpha * loss * classLabels[x] * dataMatrix[x, i]
                        for j in xrange(k):
                            v[i, j] = v[i, j] - alpha * loss * classLabels[x] * (
                            dataMatrix[x, i] * inter_1[0, j] - v[i, j] * dataMatrix[x, i] * dataMatrix[x, i])
    
        return w_0, w, v

    精确度计算及其评估Assessment:

    def Assessment(dataMatrix, classLabels, w_0, w, v):
        m, n = shape(dataMatrix)
        allItem = 0
        error = 0
        result = []
        for x in xrange(m):
            allItem += 1
            inter_1 = dataMatrix[x] * v
            inter_2 = multiply(dataMatrix[x], dataMatrix[x]) * multiply(v, v)
            interaction = sum(multiply(inter_1, inter_1) - inter_2) / 2.
            p = w_0 + dataMatrix[x] * w + interaction
            pre = sigmoid(p[0, 0])
            result.append(pre)
            if pre < 0.5 and classLabels[x] == 1.0:
                error += 1
            elif pre >= 0.5 and classLabels[x] == -1.0:
                error += 1
            else:
                continue
        print result
        return float(error) / allItem

    main函数:

    if __name__ == '__main__':
        #-------读取数据----------
        trainData = 'train.txt'
        testData = 'test.txt'
        #------模型训练----
        dataTrain, labelTrain = load_train_data(trainData)
        dataTest, labelTest = laod_test_data(testData)
        w_0, w, v = FM_function(mat(dataTrain), labelTrain, 15, 100)

    参考资料:
    1. https://blog.csdn.net/jediael_lu/article/details/77772565#1fm
    2. https://www.jianshu.com/p/55be900e18db
    3. http://baijiahao.baidu.com/s?id=1589879343345420975&wfr=spider&for=pc
    4. https://blog.csdn.net/g11d111/article/details/77430095

    展开全文
  • tensorflow实现FM算法

    千次阅读 2019-04-19 19:51:53
    FM算法 Tensorflow实现 本节通过实现FM 算法熟悉tensorflow的使用 FM 算法原理 FM (factor machine)算法是有监督的机器学习算法,可以用来分类和回归,一般用来做CTR预估。FM算法的亮点是提出了一种特征组合的方式...

    FM算法 Tensorflow实现


    本节通过实现FM 算法熟悉tensorflow的使用

    FM 算法原理

    FM (factor machine)算法是有监督的机器学习算法,可以用来分类和回归,一般用来做CTR预估。FM算法的亮点是提出了一种特征组合的方式。
    y=w0+i=1nwixi+i&lt;jwi,jxixj y=w_{0}+\sum_{i=1}^{n}{w_{i}*x_{i}}+\sum_{i&lt;j}{w_{i,j}*x_{i}*x_{j}}

    W=VVT W=V*V^T

    VT=(V1T,V2T,&ThinSpace;,VnT) V^T=(V_{1}^{T},V_{2}^{T},\cdots,V_{n}^T)

    如上面公式所示,FM 算法在逻辑回归的基础上加入了特征交叉项。如过给每个交叉项单独指定一个权重,参数的个数是n的二次方,容易过拟合。为了减少参数的个数,每个特征对应一个维度为K隐因子向量,特征交叉项的系数是两个交叉特征的隐因子的点乘。采用矩阵表示,最后一项写成
    i&lt;jwi,jxixj=12(i,j&lt;Vi,Vj&gt;xixjixiVi2) \sum_{i&lt;j}{w_{i,j}*x_{i}*x_{j}}=\frac{1}{2}(\sum_{i,j}&lt;V_{i},V_{j}&gt;*x_{i}*x_{j}-\sum_{i}||x_{i}*V_{i}||^2)

    =12{XVVTXT(XX)(VV).sum(axis=1)} =\frac{1}{2}\{X*V*V^T*X^T-(X\cdot{X})*(V\cdot{V}).sum(axis=1)\}

    以X表示某个m 个样本构成的数据集m*n 矩阵,样本有n个特征,Y的预测值可以按下面公式表示
    YP=b+Xw+12{[(XV)2(XX)(VV)].sum(axis=1)} Y^P=b+X*\vec{w}+\frac{1}{2}\{[(X*V)^2-(X\cdot{X})*(V\cdot{V})].sum(axis=1)\}

    Tensorflow 实现

    本小节基于tensorflow 实现FM算法,代码如下:

    import tensorflow as tf
    import numpy as np
    from sklearn.model_selection import train_test_split
    from sklearn.datasets import load_svmlight_file
    
    learning_rate = 0.1
    training_epoches = 500
    batch_size =100
    display_step = 1
    
    X_total,Y_total=load_svmlight_file("libsvmfinal_8_2")
    shape=X_total.shape
    
    Y_total=Y_total.reshape(-1, 1)
    X_train, X_test, y_train, y_test = train_test_split(X_total, Y_total, test_size = 0.1, random_state = 42)
    
    n_samples = X_train.shape[0]
    n_features =shape[1]
    k=2
    
    #placeholder
    x = tf.sparse_placeholder(tf.float64)
    y = tf.placeholder(tf.float64, [None, 1])
    
    #parametor to train
    V = tf.Variable(tf.zeros([n_features, k],dtype=tf.float64),dtype=tf.float64,name="vk")
    b = tf.Variable(tf.zeros([1],dtype=tf.float64),dtype=tf.float64,name="b")
    w = tf.Variable(tf.random_normal((n_features,1),dtype=tf.float64),dtype=tf.float64,name="w")
    #model logic
    vx=tf.sparse_tensor_dense_matmul(x,V)
    vx_sq=tf.multiply(vx,vx)
    xx=tf.square(x)
    vsq_xsq=tf.sparse_tensor_dense_matmul(xx,V*V)
    biterm=vx_sq-vsq_xsq
    preds=tf.nn.sigmoid(tf.sparse_tensor_dense_matmul(x,w)+0.5*tf.reduce_sum(biterm,reduction_indices=1)+b)
    cost=tf.reduce_mean(-y*tf.log(tf.clip_by_value(preds,1e-10,1.0))-(1-y)*tf.log(tf.clip_by_value(1-preds,1e-10,1.0)))
    optimizer = tf.train.AdamOptimizer(learning_rate).minimize(cost)
    threshold=tf.constant(0.5,dtype=tf.float64)
    plabel=tf.cast(threshold<y,tf.float64)
    accuracy=tf.metrics.accuracy(y,plabel)
    #auc=tf.metrics.auc(y,preds)
    #accuracy=tf.reduce_mean(tf.cast(tf.equal(plabel,y),tf.float32))
    init = tf.global_variables_initializer()
    saver=tf.train.Saver()
    
    with tf.Session() as sess:
        #sess.run(init)
        sess.run(tf.initialize_local_variables())
        saver.restore(sess,"my_model3.ckpt198")
        for epoch in range(training_epoches):
            avg_cost = 0
            total_batch = int(n_samples / batch_size)
            batch=0
            for i in range(total_batch):
                xcsr=X_train[i*batch_size:(i+1)*batch_size]
                coo=xcsr.tocoo() 
                indices=np.mat([coo.row,coo.col]).transpose()           
                _, c = sess.run([optimizer, cost], 
                                feed_dict={x:tf.SparseTensorValue(indices,coo.data,coo.shape) 
                                         ,y: y_train[i * batch_size : (i+1) * batch_size]})
                avg_cost += c / total_batch
                batch +=1
                if batch%2000 ==1999:
                    print "epoch",epoch,"batch",batch
            print "b", b.eval()
            if epoch%100 ==99:
                save_path=saver.save(sess,"./my_model3.ckpt"+str(epoch))
            if (epoch+1) % display_step == 0:
    
                print("Epoch:", "%04d" % (epoch+1), "cost=", avg_cost)          
                xcsr=X_test
                coo=xcsr.tocoo() 
                indices=np.mat([coo.row,coo.col]).transpose()
                act=sess.run([accuracy],feed_dict={x:tf.SparseTensorValue(indices,coo.data,coo.shape),y: y_test})
                print "accuracy" ,act
                
        print("Optimization Finished!")
            
                
                
    

    tensorflow 程序脚本分为两步。第一步,使用tensorflow 定义的算子定义好模型,输入用placeholder 标识,变量使用variable定义。第二步,打开一个session,把输入放到placeholder 标识的dict 里,指定要执行的操作或要获取的输出,然后执行。在正式执行之前,要先初始化变量。

    在第一步和第二步之间我们没看到的是,tensorflow 维护了一张默认的tfgraph。第一步定义的算子被编码在这张图里,第二步的run 执行的是这张图中的逻辑。tensorflow 可以看作一门编程语言。第一步是编译器前端,把运算逻辑解析成中间表达形式(实际上,tfgraph 非常像抽象语法树);第二步第一次运行计算图之前会对做一些中间代码优化,比如公共子表达式消除,图枝剪,常量折叠等,然后tensorflow 运行时对计算图解释执行。

    展开全文
  • 1. 什么是FMFM即Factor Machine,因子分解机。2. 为什么需要FM?1、特征组合是许多机器学习建模过程中遇到的问题,如果对特征直接建模,很有可能会忽略掉特征与特征之间的关联信息,因此,可以通过构建新的交叉...

    1. 什么是FM?

    FM即Factor Machine,因子分解机。

    2. 为什么需要FM?

    1、特征组合是许多机器学习建模过程中遇到的问题,如果对特征直接建模,很有可能会忽略掉特征与特征之间的关联信息,因此,可以通过构建新的交叉特征这一特征组合方式提高模型的效果。

    2、高维的稀疏矩阵是实际工程中常见的问题,并直接会导致计算量过大,特征权值更新缓慢。试想一个10000*100的表,每一列都有8种元素,经过one-hot独热编码之后,会产生一个10000*800的表。因此表中每行元素只有100个值为1,700个值为0。

    而FM的优势就在于对这两方面问题的处理。首先是特征组合,通过对两两特征组合,引入交叉项特征,提高模型得分;其次是高维灾难,通过引入隐向量(对参数矩阵进行矩阵分解),完成对特征的参数估计。

    3. FM用在哪?

    我们已经知道了FM可以解决特征组合以及高维稀疏矩阵问题,而实际业务场景中,电商、豆瓣等推荐系统的场景是使用最广的领域,打个比方,小王只在豆瓣上浏览过20部电影,而豆瓣上面有20000部电影,如果构建一个基于小王的电影矩阵,毫无疑问,里面将有199980个元素全为0。而类似于这样的问题就可以通过FM来解决。

    4. FM长什么样?

    在展示FM算法前,我们先回顾一下最常见的线性表达式:

    07b75b9a30450fcf0cb4d627d464f554.png

    其中w0为初始权值,或者理解为偏置项,wi为每个特征xi对应的权值。可以看到,这种线性表达式只描述了每个特征与输出的关系。

    FM的表达式如下,可观察到,只是在线性表达式后面加入了新的交叉项特征及对应的权值。

    b9a6da5eabf8b787319a88da2a0633ae.png

    5. FM交叉项的展开

    5.1 寻找交叉项

    FM表达式的求解核心在于对交叉项的求解。下面是很多人用来求解交叉项的展开式,对于第一次接触FM算法的人来说可能会有疑惑,不知道公式怎么展开的,接下来笔者会手动推导一遍。

    241a1304c7c3dbf8c3b7d66820354a79.png

    设有3个变量(特征)x1 x2 x3,每一个特征的隐变量分别为v1=(1 2 3)、v2=(4 5 6)、v3=(1 2 1),即:

    80fd3b17a737b5405f9137b781a7d29d.png

    设交叉项所组成的权矩阵W为对称矩阵,之所以设为对称矩阵是因为对称矩阵有可以用向量乘以向量转置替代的性质。

    那么W=VVT,即

    6cc59dea5703cc14260d9854b0b2ff6c.png

    所以:

    b355464b1a46e800a562fd0608f9bd25.png

    实际上,我们应该考虑的交叉项应该是排除自身组合的项,即对于x1x1、x2x2、x3x3不认为是交叉项,那么真正的交叉项为x1x2、x1x3、x2x1、x2x3、x3x1、x3x2。

    去重后,交叉项即x1x2、x1x3、x2x3。这也是公式中1/2出现的原因。

    5.2 交叉项权值转换

    对交叉项有了基本了解后,下面将进行公式的分解,还是以n=3为例,

    019e9bf601e74f820c3e04ea9bb9be26.png

    所以:

    b68a265f7f87328cd7e97722e1a4d3e2.png

    wij可记作

    535944aff8077b722c3fd49bd1876929.png

    c75ce62f6e56cd88281eae3f7095214d.png,这取决于vi是1*3 还是3*1 向量。

    5.3 交叉项展开式

    上面的例子是对3个特征做的交叉项推导,因此对具有n个特征,FM的交叉项公式就可推广为:

    8c0d1cb2bcf46f768e9ead3c25654940.png

    我们还可以进一步分解:

    fbeeec82a44a9bb43957aafae9af5050.png

    所以FM算法的交叉项最终可展开为:

    3126a71203ec4cf694c15c972fbbbae3.png

    5.4隐向量v就是embedding vector?

    假设训练数据集dataMatrix的shape为(20000,9),取其中一行数据作为一条样本i,那么样本i 的shape为(1,9),同时假设隐向量vi的shape为(9,8)(注:8为自定义值,代表embedding vector的长度)

    所以5.3小节中的交叉项可以表示为:

    sum((inter_1)^2 - (inter_2)^2)/2

    其中:

    inter_1 =i*v shape为(1,8)

    inter_2 =np.multiply(i)*np.multiply(v) shape为(1,8)

    可以看到,样本i 经过交叉项中的计算后,得到向量shape为(1,8)的inter_1和inter_2。

    由于维度变低,所以此计算过程可以近似认为在交叉项中对样本i 进行了embedding vector转换。

    故,我们需要对之前的理解进行修正:

    我们口中的隐向量vi实际上是一个向量组,其形状为(输入特征One-hot后的长度,自定义长度);

    隐向量vi代表的并不是embedding vector,而是在对输入进行embedding vector的向量组,也可理解为是一个权矩阵;

    由输入i*vi得到的向量才是真正的embedding vector。

    具体可以结合第7节点的代码实现进行理解。

    6. 权值求解

    利用梯度下降法,通过求损失函数对特征(输入项)的导数计算出梯度,从而更新权值。设m为样本个数,θ为权值。

    如果是回归问题,损失函数一般是均方误差(MSE):

    81105ad144d3d4840cf0d00462b8c1b9.png

    所以回归问题的损失函数对权值的梯度(导数)为:

    25d7e3c0b90f76b5cc74a138c1ea42a6.png

    如果是二分类问题,损失函数一般是logit loss:

    d796a7c09dae9b03c51fdb26aa0039fd.png

    其中,

    80783b0d8d615e8833ca7f6b25e29bc6.gif表示的是阶跃函数Sigmoid。

    861491be576f9c344b8c408965dfe3f7.png

    所以分类问题的损失函数对权值的梯度(导数)为:

    abddc6b9744561d557e2eb1031836ac8.png

    ad2a09ad08715c5faf88c4f23dfced0b.png

    相应的,对于常数项、一次项、交叉项的导数分别为:

    deda05385a44da3564ed1ff61c154de0.png

    7. FM算法的Python实现

    FM算法的Python实现流程图如下:

    b1b68e4a976473078c2ea4dcfa8bcb29.png

    我们需要注意以下四点:

    1. 初始化参数,包括对偏置项权值w0、一次项权值w以及交叉项辅助向量的初始化;

    2. 定义FM算法;

    3. 损失函数梯度的定义;

    4. 利用梯度下降更新参数。

    下面的代码片段是以上四点的描述,其中的loss并不是二分类的损失loss,而是分类loss的梯度中的一部分:

    loss = self.sigmoid(classLabels[x] * p[0, 0]) -1

    实际上,二分类的损失loss的梯度可以表示为:

    gradient = (self.sigmoid(classLabels[x] * p[0, 0]) -1)*classLabels[x]*p_derivative

    其中 p_derivative 代表常数项、一次项、交叉项的导数(详见本文第6小节)。

    FM算法代码片段

    # 初始化参数

    w = zeros((n, 1)) # 其中n是特征的个数

    w_0 = 0.

    v = normalvariate(0, 0.2) * ones((n, k))

    for it in range(self.iter): # 迭代次数

    # 对每一个样本,优化

    for x in range(m):

    # 这边注意一个数学知识:对应点积的地方通常会有sum,对应位置积的地方通常都没有,详细参见矩阵运算规则,本处计算逻辑在:http://blog.csdn.net/google19890102/article/details/45532745

    # xi·vi,xi与vi的矩阵点积

    inter_1 = dataMatrix[x] * v

    # xi与xi的对应位置乘积 与 xi^2与vi^2对应位置的乘积 的点积

    inter_2 = multiply(dataMatrix[x], dataMatrix[x]) * multiply(v, v) # multiply对应元素相乘

    # 完成交叉项,xi*vi*xi*vi - xi^2*vi^2

    interaction = sum(multiply(inter_1, inter_1) - inter_2) / 2.

    # 计算预测的输出

    p = w_0 + dataMatrix[x] * w + interaction

    print('classLabels[x]:',classLabels[x])

    print('预测的输出p:', p)

    # 计算sigmoid(y*pred_y)-1准确的说不是loss,原作者这边理解的有问题,只是作为更新w的中间参数,这边算出来的是越大越好,而下面却用了梯度下降而不是梯度上升的算法在

    loss = self.sigmoid(classLabels[x] * p[0, 0]) - 1

    if loss >= -1:

    loss_res = '正方向 '

    else:

    loss_res = '反方向'

    # 更新参数

    w_0 = w_0 - self.alpha * loss * classLabels[x]

    for i in range(n):

    if dataMatrix[x, i] != 0:

    w[i, 0] = w[i, 0] - self.alpha * loss * classLabels[x] * dataMatrix[x, i]

    for j in range(k):

    v[i, j] = v[i, j] - self.alpha * loss * classLabels[x] * (

    dataMatrix[x, i] * inter_1[0, j] - v[i, j] * dataMatrix[x, i] * dataMatrix[x, i])

    FM算法完整实现

    # -*- coding: utf-8 -*-

    from __future__ import division

    from math import exp

    from numpy import *

    from random import normalvariate # 正态分布

    from sklearn import preprocessing

    import numpy as np

    '''

    data : 数据的路径

    feature_potenital : 潜在分解维度数

    alpha : 学习速率

    iter : 迭代次数

    _w,_w_0,_v : 拆分子矩阵的weight

    with_col : 是否带有columns_name

    first_col : 首列有价值的feature的index

    '''

    class fm(object):

    def __init__(self):

    self.data = None

    self.feature_potential = None

    self.alpha = None

    self.iter = None

    self._w = None

    self._w_0 = None

    self.v = None

    self.with_col = None

    self.first_col = None

    def min_max(self, data):

    self.data = data

    min_max_scaler = preprocessing.MinMaxScaler()

    return min_max_scaler.fit_transform(self.data)

    def loadDataSet(self, data, with_col=True, first_col=2):

    # 我就是闲的蛋疼,明明pd.read_table()可以直接度,非要搞这样的,显得代码很长,小数据下完全可以直接读嘛,唉~

    self.first_col = first_col

    dataMat = []

    labelMat = []

    fr = open(data)

    self.with_col = with_col

    if self.with_col:

    N = 0

    for line in fr.readlines():

    # N=1时干掉列表名

    if N > 0:

    currLine = line.strip().split()

    lineArr = []

    featureNum = len(currLine)

    for i in range(self.first_col, featureNum):

    lineArr.append(float(currLine[i]))

    dataMat.append(lineArr)

    labelMat.append(float(currLine[1]) * 2 - 1)

    N = N + 1

    else:

    for line in fr.readlines():

    currLine = line.strip().split()

    lineArr = []

    featureNum = len(currLine)

    for i in range(2, featureNum):

    lineArr.append(float(currLine[i]))

    dataMat.append(lineArr)

    labelMat.append(float(currLine[1]) * 2 - 1)

    return mat(self.min_max(dataMat)), labelMat

    def sigmoid(self, inx):

    # return 1.0/(1+exp(min(max(-inx,-10),10)))

    return 1.0 / (1 + exp(-inx))

    # 得到对应的特征weight的矩阵

    def fit(self, data, feature_potential=8, alpha=0.01, iter=100):

    # alpha是学习速率

    self.alpha = alpha

    self.feature_potential = feature_potential

    self.iter = iter

    # dataMatrix用的是mat, classLabels是列表

    dataMatrix, classLabels = self.loadDataSet(data)

    print('dataMatrix:',dataMatrix.shape)

    print('classLabels:',classLabels)

    k = self.feature_potential

    m, n = shape(dataMatrix)

    # 初始化参数

    w = zeros((n, 1)) # 其中n是特征的个数

    w_0 = 0.

    v = normalvariate(0, 0.2) * ones((n, k))

    for it in range(self.iter): # 迭代次数

    # 对每一个样本,优化

    for x in range(m):

    # 这边注意一个数学知识:对应点积的地方通常会有sum,对应位置积的地方通常都没有,详细参见矩阵运算规则,本处计算逻辑在:http://blog.csdn.net/google19890102/article/details/45532745

    # xi·vi,xi与vi的矩阵点积

    inter_1 = dataMatrix[x] * v

    # xi与xi的对应位置乘积 与 xi^2与vi^2对应位置的乘积 的点积

    inter_2 = multiply(dataMatrix[x], dataMatrix[x]) * multiply(v, v) # multiply对应元素相乘

    # 完成交叉项,xi*vi*xi*vi - xi^2*vi^2

    interaction = sum(multiply(inter_1, inter_1) - inter_2) / 2.

    # 计算预测的输出

    p = w_0 + dataMatrix[x] * w + interaction

    print('classLabels[x]:',classLabels[x])

    print('预测的输出p:', p)

    # 计算sigmoid(y*pred_y)-1

    loss = self.sigmoid(classLabels[x] * p[0, 0]) - 1

    if loss >= -1:

    loss_res = '正方向 '

    else:

    loss_res = '反方向'

    # 更新参数

    w_0 = w_0 - self.alpha * loss * classLabels[x]

    for i in range(n):

    if dataMatrix[x, i] != 0:

    w[i, 0] = w[i, 0] - self.alpha * loss * classLabels[x] * dataMatrix[x, i]

    for j in range(k):

    v[i, j] = v[i, j] - self.alpha * loss * classLabels[x] * (

    dataMatrix[x, i] * inter_1[0, j] - v[i, j] * dataMatrix[x, i] * dataMatrix[x, i])

    print('the no %s times, the loss arrach %s' % (it, loss_res))

    self._w_0, self._w, self._v = w_0, w, v

    def predict(self, X):

    if (self._w_0 == None) or (self._w == None).any() or (self._v == None).any():

    raise NotFittedError("Estimator not fitted, call `fit` first")

    # 类型检查

    if isinstance(X, np.ndarray):

    pass

    else:

    try:

    X = np.array(X)

    except:

    raise TypeError("numpy.ndarray required for X")

    w_0 = self._w_0

    w = self._w

    v = self._v

    m, n = shape(X)

    result = []

    for x in range(m):

    inter_1 = mat(X[x]) * v

    inter_2 = mat(multiply(X[x], X[x])) * multiply(v, v) # multiply对应元素相乘

    # 完成交叉项

    interaction = sum(multiply(inter_1, inter_1) - inter_2) / 2.

    p = w_0 + X[x] * w + interaction # 计算预测的输出

    pre = self.sigmoid(p[0, 0])

    result.append(pre)

    return result

    def getAccuracy(self, data):

    dataMatrix, classLabels = self.loadDataSet(data)

    w_0 = self._w_0

    w = self._w

    v = self._v

    m, n = shape(dataMatrix)

    allItem = 0

    error = 0

    result = []

    for x in range(m):

    allItem += 1

    inter_1 = dataMatrix[x] * v

    inter_2 = multiply(dataMatrix[x], dataMatrix[x]) * multiply(v, v) # multiply对应元素相乘

    # 完成交叉项

    interaction = sum(multiply(inter_1, inter_1) - inter_2) / 2.

    p = w_0 + dataMatrix[x] * w + interaction # 计算预测的输出

    pre = self.sigmoid(p[0, 0])

    result.append(pre)

    if pre < 0.5 and classLabels[x] == 1.0:

    error += 1

    elif pre >= 0.5 and classLabels[x] == -1.0:

    error += 1

    else:

    continue

    # print(result)

    value = 1 - float(error) / allItem

    return value

    class NotFittedError(Exception):

    """

    Exception class to raise if estimator is used before fitting

    """

    pass

    if __name__ == '__main__':

    fm()

    以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。

    展开全文
  • Python实现FM算法解析

    2020-09-19 06:45:00
    主要介绍了Python实现FM算法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
  • 1. 什么是FMFM即Factor Machine,因子分解机。2. 为什么需要FM?1、特征组合是许多机器学习建模过程中遇到的问题,如果对特征直接建模,很有可能会忽略掉特征与特征之间的关联信息,因此,可以通过构建新的交叉...

    1. 什么是FM?

    FM即Factor Machine,因子分解机。

    2. 为什么需要FM?

    1、特征组合是许多机器学习建模过程中遇到的问题,如果对特征直接建模,很有可能会忽略掉特征与特征之间的关联信息,因此,可以通过构建新的交叉特征这一特征组合方式提高模型的效果。

    2、高维的稀疏矩阵是实际工程中常见的问题,并直接会导致计算量过大,特征权值更新缓慢。试想一个10000*100的表,每一列都有8种元素,经过one-hot独热编码之后,会产生一个10000*800的表。因此表中每行元素只有100个值为1,700个值为0。

    而FM的优势就在于对这两方面问题的处理。首先是特征组合,通过对两两特征组合,引入交叉项特征,提高模型得分;其次是高维灾难,通过引入隐向量(对参数矩阵进行矩阵分解),完成对特征的参数估计。

    3. FM用在哪?

    我们已经知道了FM可以解决特征组合以及高维稀疏矩阵问题,而实际业务场景中,电商、豆瓣等推荐系统的场景是使用最广的领域,打个比方,小王只在豆瓣上浏览过20部电影,而豆瓣上面有20000部电影,如果构建一个基于小王的电影矩阵,毫无疑问,里面将有199980个元素全为0。而类似于这样的问题就可以通过FM来解决。

    4. FM长什么样?

    在展示FM算法前,我们先回顾一下最常见的线性表达式:

    afec0e3326f709024471a64469fd8490.png

    其中w0 为初始权值,或者理解为偏置项,wi为每个特征xi 对应的权值。可以看到,这种线性表达式只描述了每个特征与输出的关系。

    FM的表达式如下,可观察到,只是在线性表达式后面加入了新的交叉项特征及对应的权值。

    c6bdafa5f2ad532b64db4b7402b1b7ea.png

    5. FM交叉项的展开

    5.1 寻找交叉项

    FM表达式的求解核心在于对交叉项的求解。下面是很多人用来求解交叉项的展开式,对于第一次接触FM算法的人来说可能会有疑惑,不知道公式怎么展开的,接下来笔者会手动推导一遍。

    1f7332785e7581d8cb9475981e306230.png

    设有3个变量(特征)x1 x2 x3,每一个特征的隐变量分别为v1=(1 2 3)、v2=(4 5 6)、v3=(1 2 1),即:

    b33eed08835f1ee7e222b6bd84d319ec.png

    设交叉项所组成的权矩阵W为对称矩阵,之所以设为对称矩阵是因为对称矩阵有可以用向量乘以向量转置替代的性质。

    那么W=VVT,即

    b9f2908915d27a789a7313ef2735bc87.png

    所以:

    82d5800ae31e4b539606703298f4aa26.png

    实际上,我们应该考虑的交叉项应该是排除自身组合的项,即对于x1x1、x2x2、x3x3不认为是交叉项,那么真正的交叉项为x1x2、x1x3、x2x1、x2x3、x3x1、x3x2。

    去重后,交叉项即x1x2、x1x3、x2x3。这也是公式中1/2出现的原因。

    5.2 交叉项权值转换

    对交叉项有了基本了解后,下面将进行公式的分解,还是以n=3为例,

    4f0d5344310b162648977dd1e58bbe58.png

    所以:

    8a0ac45ad12d04c4f71e51fdf36292bc.png

    wij可记作

    e7e0d0c0291cdc733fadd1104b33dbd0.png

    c2b6df9936408152f9e3c97827d67e82.png,这取决于vi是1*3 还是3*1 向量。

    5.3 交叉项展开式

    上面的例子是对3个特征做的交叉项推导,因此对具有n个特征,FM的交叉项公式就可推广为:

    fc5a0d48deb9eaad0b0d0d22a1e09ec2.png

    我们还可以进一步分解:

    2c3faf385206c98480c63af48e8fb13c.png

    所以FM算法的交叉项最终可展开为:

    e170a16223213e75581a256b15664656.png

    5.4 隐向量v就是embedding vector?

    假设训练数据集dataMatrix的shape为(20000,9),取其中一行数据作为一条样本i,那么样本i 的shape为(1,9),同时假设隐向量vi的shape为(9,8)(注:8为自定义值,代表embedding vector的长度)

    所以5.3小节中的交叉项可以表示为:

    sum((inter_1)^2 - (inter_2)^2)/2

    其中:

    inter_1 = i*v  shape为(1,8)

    inter_2 = np.multiply(i)*np.multiply(v)  shape为(1,8)

    可以看到,样本i 经过交叉项中的计算后,得到向量shape为(1,8)的inter_1和 inter_2。

    由于维度变低,所以此计算过程可以近似认为在交叉项中对样本i 进行了embedding vector转换。

    故,我们需要对之前的理解进行修正:

    我们口中的隐向量vi实际上是一个向量组,其形状为(输入特征One-hot后的长度,自定义长度);

    隐向量vi代表的并不是embedding vector,而是在对输入进行embedding vector的向量组,也可理解为是一个权矩阵;

    由输入i*vi得到的向量才是真正的embedding vector。

    具体可以结合第7节点的代码实现进行理解。

    6. 权值求解

    利用梯度下降法,通过求损失函数对特征(输入项)的导数计算出梯度,从而更新权值。设m为样本个数,θ为权值。

    如果是回归问题,损失函数一般是均方误差(MSE):

    1de54bd2ff37c2502ced4494ef5e5a59.png

    所以回归问题的损失函数对权值的梯度(导数)为:

    eb5876b7305cf6e550d64c972c30d8f0.png

    如果是二分类问题,损失函数一般是logit loss:

    a9fe779b368db77446f9dadea7a3a304.png

    其中,

    80783b0d8d615e8833ca7f6b25e29bc6.gif表示的是阶跃函数Sigmoid。

    ddcd58793e9aa43abcbf6d357168cfbe.png

    所以分类问题的损失函数对权值的梯度(导数)为:

    98ccf32be954bb6f8cf48ba7c42aaadd.png

    5d253255ecd75972c76c2cff8abbce53.png

    相应的,对于常数项、一次项、交叉项的导数分别为:

    3fea010d41cfafe9c86afbdae643eecb.png

    7. FM算法的Python实现

    FM算法的Python实现流程图如下:

    6183f8c65560fe32879591e79bee53e6.png

    我们需要注意以下四点:

    1. 初始化参数,包括对偏置项权值w0、一次项权值w以及交叉项辅助向量的初始化;

    2. 定义FM算法;

    3. 损失函数梯度的定义;

    4. 利用梯度下降更新参数。

    下面的代码片段是以上四点的描述,其中的loss并不是二分类的损失loss,而是分类loss的梯度中的一部分:

    loss = self.sigmoid(classLabels[x] * p[0, 0]) -1

    实际上,二分类的损失loss的梯度可以表示为:

    gradient = (self.sigmoid(classLabels[x] * p[0, 0]) -1)*classLabels[x]*p_derivative

    其中 p_derivative 代表常数项、一次项、交叉项的导数(详见本文第6小节)。

    FM算法代码片段

    1 #初始化参数

    2 w = zeros((n, 1)) #其中n是特征的个数

    3 w_0 =0.4 v = normalvariate(0, 0.2) *ones((n, k))5 for it in range(self.iter): #迭代次数

    6 #对每一个样本,优化

    7 for x inrange(m):8 #这边注意一个数学知识:对应点积的地方通常会有sum,对应位置积的地方通常都没有,详细参见矩阵运算规则,本处计算逻辑在:http://blog.csdn.net/google19890102/article/details/45532745

    9 #xi·vi,xi与vi的矩阵点积

    10 inter_1 = dataMatrix[x] *v11 #xi与xi的对应位置乘积 与 xi^2与vi^2对应位置的乘积 的点积

    12 inter_2 = multiply(dataMatrix[x], dataMatrix[x]) * multiply(v, v) #multiply对应元素相乘

    13 #完成交叉项,xi*vi*xi*vi - xi^2*vi^2

    14 interaction = sum(multiply(inter_1, inter_1) - inter_2) / 2.15 #计算预测的输出

    16 p = w_0 + dataMatrix[x] * w +interaction17 print('classLabels[x]:',classLabels[x])18 print('预测的输出p:', p)19 #计算sigmoid(y*pred_y)-1准确的说不是loss,原作者这边理解的有问题,只是作为更新w的中间参数,这边算出来的是越大越好,而下面却用了梯度下降而不是梯度上升的算法在

    20 loss = self.sigmoid(classLabels[x] * p[0, 0]) - 1

    21 if loss >= -1:22 loss_res = '正方向'

    23 else:24 loss_res = '反方向'

    25 #更新参数

    26 w_0 = w_0 - self.alpha * loss *classLabels[x]27 for i inrange(n):28 if dataMatrix[x, i] !=0:29 w[i, 0] = w[i, 0] - self.alpha * loss * classLabels[x] *dataMatrix[x, i]30 for j inrange(k):31 v[i, j] = v[i, j] - self.alpha * loss * classLabels[x] *(32 dataMatrix[x, i] * inter_1[0, j] - v[i, j] * dataMatrix[x, i] * dataMatrix[x, i])

    FM算法完整实现

    1 #-*- coding: utf-8 -*-

    2

    3 from __future__ importdivision4 from math importexp5 from numpy import *

    6 from random import normalvariate #正态分布

    7 from sklearn importpreprocessing8 importnumpy as np9

    10 '''

    11 data : 数据的路径12 feature_potenital : 潜在分解维度数13 alpha : 学习速率14 iter : 迭代次数15 _w,_w_0,_v : 拆分子矩阵的weight16 with_col : 是否带有columns_name17 first_col : 首列有价值的feature的index18 '''

    19

    20

    21 classfm(object):22 def __init__(self):23 self.data =None24 self.feature_potential =None25 self.alpha =None26 self.iter =None27 self._w =None28 self._w_0 =None29 self.v =None30 self.with_col =None31 self.first_col =None32

    33 defmin_max(self, data):34 self.data =data35 min_max_scaler =preprocessing.MinMaxScaler()36 returnmin_max_scaler.fit_transform(self.data)37

    38 def loadDataSet(self, data, with_col=True, first_col=2):39 #我就是闲的蛋疼,明明pd.read_table()可以直接度,非要搞这样的,显得代码很长,小数据下完全可以直接读嘛,唉~

    40 self.first_col =first_col41 dataMat =[]42 labelMat =[]43 fr =open(data)44 self.with_col =with_col45 ifself.with_col:46 N =047 for line infr.readlines():48 #N=1时干掉列表名

    49 if N >0:50 currLine =line.strip().split()51 lineArr =[]52 featureNum =len(currLine)53 for i inrange(self.first_col, featureNum):54 lineArr.append(float(currLine[i]))55 dataMat.append(lineArr)56 labelMat.append(float(currLine[1]) * 2 - 1)57 N = N + 1

    58 else:59 for line infr.readlines():60 currLine =line.strip().split()61 lineArr =[]62 featureNum =len(currLine)63 for i in range(2, featureNum):64 lineArr.append(float(currLine[i]))65 dataMat.append(lineArr)66 labelMat.append(float(currLine[1]) * 2 - 1)67 returnmat(self.min_max(dataMat)), labelMat68

    69 defsigmoid(self, inx):70 #return 1.0/(1+exp(min(max(-inx,-10),10)))

    71 return 1.0 / (1 + exp(-inx))72

    73 #得到对应的特征weight的矩阵

    74 def fit(self, data, feature_potential=8, alpha=0.01, iter=100):75 #alpha是学习速率

    76 self.alpha =alpha77 self.feature_potential =feature_potential78 self.iter =iter79 #dataMatrix用的是mat, classLabels是列表

    80 dataMatrix, classLabels =self.loadDataSet(data)81 print('dataMatrix:',dataMatrix.shape)82 print('classLabels:',classLabels)83 k =self.feature_potential84 m, n =shape(dataMatrix)85 #初始化参数

    86 w = zeros((n, 1)) #其中n是特征的个数

    87 w_0 =0.88 v = normalvariate(0, 0.2) *ones((n, k))89 for it in range(self.iter): #迭代次数

    90 #对每一个样本,优化

    91 for x inrange(m):92 #这边注意一个数学知识:对应点积的地方通常会有sum,对应位置积的地方通常都没有,详细参见矩阵运算规则,本处计算逻辑在:http://blog.csdn.net/google19890102/article/details/45532745

    93 #xi·vi,xi与vi的矩阵点积

    94 inter_1 = dataMatrix[x] *v95 #xi与xi的对应位置乘积 与 xi^2与vi^2对应位置的乘积 的点积

    96 inter_2 = multiply(dataMatrix[x], dataMatrix[x]) * multiply(v, v) #multiply对应元素相乘

    97 #完成交叉项,xi*vi*xi*vi - xi^2*vi^2

    98 interaction = sum(multiply(inter_1, inter_1) - inter_2) / 2.99 #计算预测的输出

    100 p = w_0 + dataMatrix[x] * w +interaction101 print('classLabels[x]:',classLabels[x])102 print('预测的输出p:', p)103 #计算sigmoid(y*pred_y)-1

    104 loss = self.sigmoid(classLabels[x] * p[0, 0]) - 1

    105 if loss >= -1:106 loss_res = '正方向'

    107 else:108 loss_res = '反方向'

    109 #更新参数

    110 w_0 = w_0 - self.alpha * loss *classLabels[x]111 for i inrange(n):112 if dataMatrix[x, i] !=0:113 w[i, 0] = w[i, 0] - self.alpha * loss * classLabels[x] *dataMatrix[x, i]114 for j inrange(k):115 v[i, j] = v[i, j] - self.alpha * loss * classLabels[x] *(116 dataMatrix[x, i] * inter_1[0, j] - v[i, j] * dataMatrix[x, i] *dataMatrix[x, i])117 print('the no %s times, the loss arrach %s' %(it, loss_res))118 self._w_0, self._w, self._v =w_0, w, v119

    120 defpredict(self, X):121 if (self._w_0 == None) or (self._w == None).any() or (self._v ==None).any():122 raise NotFittedError("Estimator not fitted, call `fit` first")123 #类型检查

    124 ifisinstance(X, np.ndarray):125 pass

    126 else:127 try:128 X =np.array(X)129 except:130 raise TypeError("numpy.ndarray required for X")131 w_0 =self._w_0132 w =self._w133 v =self._v134 m, n =shape(X)135 result =[]136 for x inrange(m):137 inter_1 = mat(X[x]) *v138 inter_2 = mat(multiply(X[x], X[x])) * multiply(v, v) #multiply对应元素相乘

    139 #完成交叉项

    140 interaction = sum(multiply(inter_1, inter_1) - inter_2) / 2.141 p = w_0 + X[x] * w + interaction #计算预测的输出

    142 pre =self.sigmoid(p[0, 0])143 result.append(pre)144 returnresult145

    146 defgetAccuracy(self, data):147 dataMatrix, classLabels =self.loadDataSet(data)148 w_0 =self._w_0149 w =self._w150 v =self._v151 m, n =shape(dataMatrix)152 allItem =0153 error =0154 result =[]155 for x inrange(m):156 allItem += 1

    157 inter_1 = dataMatrix[x] *v158 inter_2 = multiply(dataMatrix[x], dataMatrix[x]) * multiply(v, v) #multiply对应元素相乘

    159 #完成交叉项

    160 interaction = sum(multiply(inter_1, inter_1) - inter_2) / 2.161 p = w_0 + dataMatrix[x] * w + interaction #计算预测的输出

    162 pre =self.sigmoid(p[0, 0])163 result.append(pre)164 if pre < 0.5 and classLabels[x] == 1.0:165 error += 1

    166 elif pre >= 0.5 and classLabels[x] == -1.0:167 error += 1

    168 else:169 continue

    170 #print(result)

    171 value = 1 - float(error) /allItem172 returnvalue173

    174

    175 classNotFittedError(Exception):176 """

    177 Exception class to raise if estimator is used before fitting178 """

    179 pass

    180

    181

    182 if __name__ == '__main__':183 fm()

    9588360.html=9588360.html

    展开全文
  • python实现FM算法

    2020-12-25 17:49:53
    x2,x3,那么就会有3中特征相乘的组合x1*x2,x1*x3,x2*x3,如果变量的维度比较少,我们是可以先计算这些特征组合在进行求相关的参数,但是如果遇到维度特别大的时候而且特征又是比较稀疏的时候可以考虑用FM算法 ...
  • Python实实现现FM算算法法解解析析 这篇文章主要介绍了Python实现FM算法解析文中通过示例代码介绍的非常详细对大家的学习或者工作具有一 定的 考学习价值需要的朋友们下面随着小编来一起学习学习吧 1. 什什么么是是...
  • FM算法

    2018-10-15 20:42:00
    FM算法(一):算法理论 FM算法(二):工程实现 Python实现FM (附代码与数据) FM算法梯度推导 转载于:https://www.cnblogs.com/zyber/p/9794527.html
  • NLP自然语言处理系列-推荐系统-FM与DeepFM算法实战 DNN实现 系列文章 NLP自然语言处理系列-推荐系统-FM与DeepFM算法实战 二阶权重参数设计 ...FM与DeepFM算法实战 一阶权重参数设计 ...
  • FM算法解析及Python实现 转载于:https://www.cnblogs.com/zyber/p/9794665.html
  • 1. DeepFM算法的提出 由于DeepFM算法有效的结合了因子分解机与神经网络在特征学习中的优点:同时提取到低阶组合特征与高阶组合特征,所以越来越被广泛使用。 在DeepFM中,FM算法负责对一阶特征以及由一阶特征两两...
  • 算法原理部分可以查看博客主线1.1FM算法原理详解 本文就直接上代码了,相关说明都在代码注释里。 # coding:UTF-8 from __future__ import division from math import exp from numpy import * from random import ...
  • 计算图领域建模3.DeepFM实现3.1SimpleInputLayer层3.2 BiInnerSumCross层3.3 SumPooling层3.4 Embedding层3.5 SimpleLossLayer层1.计算图模型系统的逻辑模型决定了容纳变化的多少。大学数据结构中大概介绍过结构体、...
  • DeepFM算法原理及实现

    千次阅读 2019-09-17 17:59:52
    因为DeepFM模型基本是在 Wide&deep 的基础上进行改进而来,所有DeepFM主要解决的问题是: 1、Wide&deep 模型需要手动做特征交叉,而DeepFM因为有FM层进行一阶和二阶特征自动组合,所以不需要手动特征工程 2...
  • 扒一扒 FM 算法实现

    2020-04-12 20:20:56
    模型是在 和 的基础上发展而来的,与相比的主要区别...本质上,算法引入隐向量的做法,与矩阵分解用隐向量表示用户和物品的做法异曲同工。是将矩阵分解隐向量的思想进行了进一步的扩展,从单纯的 user embedding、it...

空空如也

空空如也

1 2 3 4 5 ... 16
收藏数 302
精华内容 120
关键字:

fm算法实现