[paper阅读] 在线广告中使用主题模型进行用户聚类(二)

方法论

在线广告的挑战

正如上面的部分解释的, 假设用户比较稳定并且已知用户的集群id的情况下, pLSA非常适用于推荐新物品. **然而, 在在线广告中, 我们试图为所有网络中的所有用户提供广告推荐. 而由于网络用户的id是基于用户设备中的cookie, 用户的id比较多变. **如果这些cookie被删除了, 那么他的集群id不再有效, 因为用户的id不再存在. 也注意: 这个原因可能会造成每天都会有许多用户进入或离开生态系统. 我们需要的是这样一个系统: 可以查看用户事件的历史然后在提供广告服务的时间给用户分配集群id(例如, 运行时).

在线广告领域中的另一个问题是: 我们不会试图给用户推荐新的物品, 至少不在本篇论文的讨论范围内. 我们试图去在给定用户确定集群的前提下, 获得一个用户的行为/点击概率. 例如: 如果一个用户由于他/她的行为将其贴上某个集群的标签, 我们希望得到它的集群id, 而不是用户将会进行什么操作(例如, 给定他过去的行为的泛化). 因此, 我们希望得到一个模型, 只会基于用户过的操作历史(而不是用户的id, 因为它太过多变), 然后给定群组(集群)的id(覆盖所用的新用户以及我们所知道的操作历史), 从而能够帮助我们计算群组的行为概率. 这也是我们方法与pLSA的最大不同: 给定行为历史, 用户独立于集群id.

pLSA的不同之处

作者们使用的聚类方法与pLSA的最大不同之处在于模型. 遵循在线广告中的规律, pLSA假设了给定用户id的情况下, beacons的独立性, 只要我们知道了集群id, 就可以假设在给定beacon id的情况下, 用户的id与集群的id是相互独立的. 这个模型中的独立性假设帮助作者们基于用户的beacon历史在运行时间内确定一个新用户或者已知用户的集群id. 在运行时间内获得用户的集群之后, 一个在线的广告系统将[给定一个特定网站上特定广告, 计算特定用户点击或者操作的概率] 变成了 [该用户所属的集群i在这个网站上点击这个广告的概率是多少?]

可以通过图2了解下这两种模型的不同之处.


(a) pLSA的盘子表示法


(b) 本文提出方法的盘子表示法

2: pLSA和本文提出方法的不同之处. 请注意: pLSA假设给定集群id之后用户和beacons是相互独立的, 而作者们这假设给定用户历史事件的beacon id之后, 用户和集群是相互独立的.

从上图中, 我们不难发现, 用户表示可以直接从模型中删除, 因此pLSA的关系就变得非常弱(由于作者在前面部分提到的在线广告的本质, 这种线上是合理的). 此外, 模型非常通用, 可以运用于不同的领域, 但是, 由于稳定变化的用户群, 这个模型在在线广告领域非常必要和有效.

自然地, 本文中提出的公式也会与传统的/用于训练模型概率的EM算法有所不同. 其中非常明显的一个例子: 正如上面提到的, PLSA的求期望部分是计算p(c_i|d_j, w_k), 给定文档j和单词w之后集群i的条件概率, 而在在线广告领域, 可以看成是给定用户j(u_j)和beacon k(b_k)后集群i的条件概率. 但是基于模型的独立性假设, p(c_i| u_j, b_k)=p(c_i|b_k). 我们将会在接下来的部分介绍EM算法的细节以及如何在运行时确定用户的集群.

模型的训练以及运行时确定用户的集群

想要在运行时确定用户的集群, 模型需要能够获取到用户的beacon历史. 一个用户的beacon历史为用户在前x天之间进行的一系列beacon(事件)(在本文中, 作者将这个值设置为60天). 例如, 对于用户i, 如果他之前有过n行为/beacon, 那么h(u_i)={b_{i,1}, b_{i,2},…, b_{i,n}}. 并不是所有的nbeacon都是唯一的, 因此, 可以得到一个概率分布: p(b_j|u_i)=\frac{n(b_j, u_i)}{n(u_i)}, 其中n(b_j, u_i)为用户i看见beaconj的次数, 而n(u_i)为用户i看过的总beacon数. 因此, 在运行时, 我们可以使用下面的公式对每个集群i进行计算:

p(c_i|u_j)=\sum_{b_k}p(c_i, b_k|u_j)=\sum_{b_k}p(c_i|b_k)p(b_k|u_j)

从而得到用户j最可能属于的集群. 由于在运行时用户的beacon概率是已知的, 所有我们需要存储的就是从beacon到集群的映射(也就是所有beacon集群对: p(c_i|b_k). 请注意: 这样的存储内存需求远小于存储每个用户的集群id(大概5亿用户,和600个集群, 基于作者们之前的经验, 使用不同数目的集群, 大约有13000beacon, 并不是每个beacon在所有集群上都有大于0的概率). 在用户的beacon历史修改或者有新用户的时候(那些可能过期的beacon或者那些模型训练时不存在的用户), 模型还是非常健壮的.

EM算法试图最大化:

{\prod_{\forall u_j}\prod_{\forall c_i}}_{p(c_i|u_j)>0} p(c_i|u_j)
={\prod_{\forall u_j}\prod_{\forall c_i}}_{p(c_i|u_j)>0} \sum_{b_k}p(c_i|b_k)p(b_k|u_j)

基于上面的集群确定流程, 得到下面的推导:

  • 求期望部分: 对于训练数据中的每个用户, 计算用户属于集群i的概率:
    p(c_i|u_j)=\sum_{b_k}p(c_i|b_k)p(b_k|u_j)
    可以进一步写成:
    p(c_i|u_j)=\sum_{b_k}\frac{p(c_i)p(b_k|c_i)}{p(b_k)}p(b_k|u_j)

其中, p(b_k)beacon k的概率, 计算方法如下: p(b_k)=\frac{\sum_{u_n}{n(u_n, b_k)}}{\sum_{u_n}{\sum_{b_m}n(u_n. b_m)}}, 其中n(u_n, b_k)为训练数据中用户n看到beacon k的次数.

  • 最大化部分: 在最大化部分, 我们计算p(c_i)p(b_k|c_i)的值:
    p(c_i)=\sum_{u_j}{p(u_j)p(c_i|u_j)}
    其中, p(c_i|u_j)为上一步的输出. 此外, 用户u_i的边缘概率为: p(u_i)=\frac{n(u_i)}{\sum_{\forall u_j}{n(u_j)}}, 其中n_i为用户u_i有过操作的beacon数.

p(b_k|c_i)=\sum_{u_j}p(b_k|u_j)p(u_j|c_i)
=\sum_{u_j}p(b_k|u_j)\frac{p(c_i|u_j)p(u_j)}{p(c_i)}

其中, p(c_i|u_j)为求期望时的输出值, 而p(c_i)为最大化步骤的一部分.

上面的公式意味着: 在求期望的部分, 我们将用户分配给集群(基于beacon-集群的对应关系, 由于最开始的时候我们没有这个值, 因此会进行随机的初始化), 然后, 在最大化部分, 我们计算beacon到集群的映射参数, 以及用户属于某个集群的概率. 这样一直交替运行直到达到收敛为止(也就是说: 集群概率以及映射关系的参数不再频繁变化). 具体细节在算法1部分. 算法中的一个细节是: 硬聚类和软聚类的区别: 在硬聚类中, 我们将用户分配给最有可能的集群c_i, 将p(c_i|u)=1(与运行时确定集群相似), 而软聚类而将用户分配给多个可能的集群, 其中\sum_{c_i} {p(c_i|u)}=1.

EM流程的最后, 我们会输出每个beacon-集群对的p(c_i|b_k), 以便用于实时确定用户的集群.

算法1 EM算法用于学习用户聚类的参数

学习集群参数 (用户集U, 物品集合B, 集群数目): 
for 每一个用户 uj ∈ U:
    将用户 uj 分配给任意集群 ci,  其中i ∈ [1,numClusters] 
    p(ci|uj) = 1 
end for 
for 每个集群 ci: 
    p_old(ci) = null 
    计算 p_new(ci) 
    for 每个物品 bk:
        p_old(bk|ci) = null 
        计算 p_new(bk|ci) 
    end for
end for 
while {对任何 ci, p_old(ci) 和 p_new(ci) 差异性很大} 或者 {对任何ci 和bk, p_old(bk|ci) 和 p_new(bk|ci) 的差异性很大}:
    for 每个用户 uj:
        if 软聚类:
            对于所有ci, 计算 p(ci|uj)
        else:
            选择对uj而言, p(ci|uj)概率最大的集群ci, 设置 p(ci|uj) = 1 
        end if 
    end for 
    for 每个集群 ci:
        p_old(ci) = p_new(ci)
        计算 p_new(ci) 
        for 每个 bk:
            p_old(bk|ci) = p_new(bk|ci) 
            计算 p_new(bk|ci)
        end for
    end for 
    end while 
for 每个集群 ci:
    for 每个 beacon bk:
        计算并返回 p(ci|bk)
    end for
end for

实现细节

本文中作者利用了Apache Pig来实现聚类算法. Pig是在Hadoop框架之上的高级别语言, 因此, 由于并行化使得聚类任务完成得更快. 正如上面部分提到的, 聚类任务从确定用户信息集合中每行的聚类id开始(例如, 单个用户的数据), 包含p(u_j)以及所有用户预见过的beacons的集合, 以及它们的条件概率(p(b_k|u_j)). 用户数据时预先计算好的, 以压缩整个训练数据, 并且减少一次EM步骤的计算时间. 确定集群信息步骤的pig脚本如图3(a)所示. 在图中, userWeightp(u_j)m 用户是p(b_k|u_j)袋, CLUSTERID是用户定义好的函数, 输入是p(c_i)p(b_k|c_i)以及用户(p(b_k|u_j)袋), 输出是p(c_i|u_j)袋(例如, clusterIdsWeights). 这个结构意味着我们可以通过平滑用户包或者clusterIdsWeights来计算EM的参数.

另一个问题是归一化概率的计算, 最开始, 我们针对每个概率都有一个权重, 但是需要对相同集群的值进行归一化. 例如, 假设在下面的示例中, 我们开始有一个变量clusterBeaconWight有一个(c_i, b_k)对的值\alpha p(b_k|c_i)(其中, \alpha是未知的). 首先, 需要基于集群id进行分组, 然后将p(b_k|c_i)加起来作为归一化因素. 之后, 使用这个叠加的和将组分散, 然后除以归一化的值以找到精确的概率. 示例代码段如图3(b)所示, 其中PARALLEL后面的数为reducer的数目, 而关键词FLATTEN用于分开相同集合p(b_k|c_i)集合的包.

使用Pig的力量, 以及Hadoop框架都在不同的机器上设置了许多用户的集群id, 并且同时计算不同集群参数的和. 注意: 本文中提出的用于模型训练的算法是可并行的, 例如, 基于我们希望计算的当前信息(要么通过用户id, beacon id或者集群id), 每个训练的时间节点, 我们都可以将数据集完整地进行分割. 这就意味着模型是并行可扩展的.


3: 用户集群实现中的Apache Pig示例代码, 可以帮助理解并行计算的步骤

打赏

mickey

记录生活,写给几十年后的自己。

发表评论

电子邮件地址不会被公开。 必填项已用*标注