lookalike
本文主人公 英特 是一名传统的软件工程师，让我们与英特一起来研究如何实现自己的lookalike算法，并尝试着在新浪微博上应用这一算法。
当2012 年facebook 在广告领域开始应用定制化受众（Facebook CustomAudiences）功能后，受众发现这个概念真正得到大规模应用。什么是受众发现？如果你的企业已经积累了一定的客户，无论这些客户是否关注你或者是否和你在Facebook 上有互动，你都能通过Facebook 的广告系统触达到。受众发现实现了什么功能？在没有这个系统之前，广告投放一般情况都是用兴趣标签去区分用户，再去给这部分用户发送广告，受众发现让你不用选择这些标签，包括用户基本信息、兴趣等。你需要做的只是上传一批你目前已有的用户或者你感兴趣的一批用户，剩下的工作就等着受众功能帮你完成了。
像Facebook 这样通过一群已有的用户发现并扩展出其他用户的推荐算法就叫Lookalike，当然英特并不清楚Facebook 的算法细节，而各个公司实现Lookalike 的方式也各有不同。这里也包括腾讯在微信端的广告推荐上的应用、Google 在YouTube上推荐感兴趣视频等。下面让我们与英特一起结合前人的工作，实现自己的Lookalike算法，并尝试着在新浪微博上应用这一算法。
1 调研
首先要确定微博领域的数据，关于微博的数据可以采用下面这几个分类维度。
- 用户基础数据：用户的年龄、性别、公司、邮箱、地点、公司等。
- 关系图：根据人-人和人-微博的关注、评论、转发信息建立关系图。
内容数据：用户的微博内容，包含文字、图片、视频。
有了这些数据后，怎么做数据的整合分析？来看看现在应用最广的方式——协同过滤、或者叫关联推荐。协同过滤主要是利用某兴趣相投、拥有共同经验之群体的喜好来推荐用户可能感兴趣的信息，协同过滤的发展有以下三个阶段。
第一阶段：基于用户的喜好去做推荐。用户A 和用户B 相似，用户B 购买了物品a、b、c，用户A 只购买了物品a，那就将物品b、c 推荐给用户A。这就是基于用户的协同过滤，其重点是如何找到相似的用户。因为只有准确地找到相似的用户才能给出正确的推荐。而找到相似用户的方法，一般是根据用户的基本属性贴标签分类，再高级点可以用上用户的行为数据。
第二阶段：某些商品光从用户的属性标签找不到联系，而根据商品本身的内容联系倒是能发现很多有趣的推荐目标，它在某些场景中比基于相似用户的推荐原则更加有效。比如在购书或者电影类网站上，当你看一本书或电影时，推荐引擎会根据内容给你推荐相关的书籍或电影。
第三阶段：如果只把内容推荐单独应用在社交网络上，准确率会比较低，因为社交网络的关键特性还是社交关系。如何将社交关系与用户属性一起融入整个推荐系统就是关键。另外一个问题就是仅仅用兴趣标签过于粗犷，人与人的兴趣差异不光光是兴趣标签决定的，往往和时间、环境等其他的影响息息相关，如何将人在社交网络的所有特征尽可能提取出来并且计算呢？在神经网络和深度学习算法出现后，提取特征任务就变得可以依靠机器完成了，人们只要把相应的数据准备好就可以了，其他数据都可以提取成向量形式，而社交关系作为一种图结构如何表示为深度学习可以接受的向量形式，而且这种结构还能有效还原原结构中位置信息？这就需要一种可靠的向量化社交关系的表示方法。基于这一思路，在2016 年的论文中出现了一个算法node2vec，使社交关系也可以很好地适应神经网络。这意味着深度学习在推荐领域应用的关键技术点已被解决。
在实现算法前英特主要参考了以下三篇论文：
Audience Expansion for Online social Network Advertising ,2016
- node2vec: Scalable Feature Learning for Networks Aditya Grover ,2016
Deep Neural Networks for YouTube Recommendations ,2016
第一篇论文是linkedin 给出的，主要谈了针对在线社交网络广告平台如何根据已有的受众特征做受众群扩展。这涉及如何定位目标受众和原始受众的相似属性。论文给出了两种方法来扩展受众，一是与营销活动无关的受众扩展，二是与营销活动有关的受众扩展。
Linkedin 的lookalike 流程图
在流程图中，Linkedin 给出了如何利用营销活动数据、目标受众基础数据去预测目标用户行为进而发现新的用户。在今天的推荐系统或广告系统里越来越多地利用了多维度信息。如何将这些信息有效地加以利用，这篇论文给出了一条路径，而且在工程上这篇论文也论证得比较扎实，值得参考。
第二篇论文主要讲的是node2vec，这也是本文用到的主要算法之一。node2vec主要用于处理网络结构中的多分类和链路预测任务，具体来说是对网络中的节点和边的特征向量表示方法。
简单点来说就是将原有社交网络中的图结构，表达成特征向量矩阵，每一个node（可以是人或物品或内容等）表示成一个特征向量，用向量与向量之间的矩阵运算来得到相互的关系。
下面来看看node2vec 中的关键技术——随机游走算法，它定义了一种新的遍历网络中某个节点的邻域的方法，具体策略如下图所示。
随机游走策略
假设我们刚刚从节点t 走到节点v，当前处于节点v，现在要选择下一步该怎么走，方案如下：
其中dtx表示节点t 到节点x 之间的最短路径，dtx= 0表示会回到节点t 本身，dtx = 1表示节点t 和节点x 直接相连，但是在上一步却选择了节点v，dtx= 2表示节点t 不与x 直接相连，但节点v 与x 直接相连。其中p 和q 为模型中的参数，形成一个不均匀的概率分布，最终得到随机游走的路径。与传统的图结构搜索方法（如BFS和DFS）相比，这里提出的随机游走算法具有更高的效率，因为本质上相当于对当前节点的邻域节点的采样，同时保留了该节点在网络中的位置信息。
node2vec 由斯坦福大学提出，并有开源代码，这一部分大家不用自己动手实现了.
第三篇论文讲的是Google 如何做YouTube 视频推荐，论文是在英特做完结构设计和流程设计后看到的，其中模型架构的思想和英特的不谋而合，还解释了为什么要引入DNN：引入DNN 的好处在于大多数类型的连续特征和离散特征可以直接添加到模型当中。此外英特还参考了这篇论文对于隐含层（FC）单元个数的选择。下图是这篇论文提到的算法结构。
YouTube 推荐算法结构图
2 实现
（1）数据准备
① 获得用户的属性（User profile），如性别、年龄、学历、职业、地域、能力标签等；
② 根据项目内容和活动内容制定一套受众标签（Audience Label）；
③ 提取用户之间的关注关系，微博之间的转发关系；
④ 获取微博message 中的文本内容；
⑤ 获得微博message 中的图片内容。
（2）用户标签特征处理
① 根据步骤1 中用户属性信息和已有的部分受众标签系统。利用GBDT 算法（可以直接用xgboost）将没有标签的受众全部打上标签。这个分类问题中请注意处理连续值变量以及归一化。
② 将标签进行向量化处理，这个问题转化成对中文单词进行向量化，这里用word2vec 处理后得到用户标签的向量化信息Label2vec。这一步也可以使用word2vec在中文的大数据样本下进行预训练，再用该模型对标签加以提取，对特征的提取有一定的提高，大约在0.5%左右。
（3）文本特征处理
清洗整理步骤1 中提取到的所有微博message 文本内容，训练doc2vec 模型，得到单个文本的向量化表示，对所得的文本作聚类（KMeans，在30 万的微博用户的message 上测试，K 取128 对文本的区分度较强），最后提取每个cluster 的中心向量，并根据每个用户所占有的cluster 获得用户所发微博的文本信息的向量表示content2vec。
（4）图像特征
将步骤1 中提取到的所有的message 图片信息进行整理分类，使用预训练卷积网络模型（这里为了平衡效率选取VGG16 作为卷积网络）提取图像信息，对每个用户message 中的图片做向量化处理，形成Image2vec，如果有多张图片则将多张图片分别提取特征值再接一层Max Pooling 提取重要信息后输出。
（5）社交关系建立（node2vec 向量化）
将步骤1 数据准备中获得的用户之间的关系和微博之间的转发评论关系转化成图结构，并提取用户关系sub-graph，最后使用node2vec 算法得到每个用户的社交网络图向量化表示。下图为社交关系化后的部分图示。
用户的社交关系
将步骤2345 得到的向量做拼接，经过两层FC，得到表示每个用户的多特征向量集（User vector Set, UVS）。这里取的输出单元个数时可以根据性能和准确度做平衡，目前英特实现的是输出512 个单元，最后的特征输出表达了用户的社交关系、用户属性、发出的内容、感兴趣的内容等的混合特征向量，这些特征向量将作为下一步比对相似性的输入值。
分别计算种子用户和潜在目标用户的向量集，并比对相似性。英特使用的是余弦相似度计算相似性，将步骤6 得到的用户特征向量集作为输入x 和y，代入下面公式计算相似性。
注意：余弦相似度更多是从方向上区分差异，而对绝对的数值不敏感，因此没法衡量每个维度值的差异。这里要在每个维度上减去一个均值或者乘以一个系数，或者在之前做好归一化。
（6）受众扩展。
① 获取种子受众名单，以及目标受众的数量N；
② 检查种子用户是否存在于UVS 中，将存在的用户向量化；
③ 计算受众名单中用户和UVS 中用户的相似度，提取最相似的前N 个用户作为目标受众。
最后将以上步骤串联起来，形成流程图。
Lookalike 算法流程图
在以上步骤提取完特征后，英特使用一个两层的神经网络做最后的特征归并提取，算法结构示意图如下。
Lookalike 算法结构示意图
其中FC1 层也可以替换成Max Pooling，Max Pooling 层具有强解释性，也就是把用户特征群上提取的最重要的特征点作为下一层的输入，读者可以自行尝试，这里限于篇幅问题就不做展开了。
3 结果
英特根据Lookalike 思想完整实现了算法，并在实际产品中投入试用，针对某客户（乳品领域世界排名前三的品牌主）计算出结果（部分）如下。
可以观察到以上微博ID 的主题基本都是西点企业或西点培训企业，和品牌主售卖的乳品有很高的关联性：乳品是非常重要的西点原料，除终端用户外，西点相关企业就是乳品企业主需要寻找的最重要的受众之一。
4 总结探讨
英特在这个案例中学到了关于用深度学习做推荐的相关知识，在最终的总结会中，英特也列出了两点通过本项目学习到的经验。
（1）特征表达。
除了前文提到的特征外，英特也对其他重要特征表达做了处理和变换：根据业务需求，需要抽取出人的兴趣特征，如何表达一个人的兴趣？除了他自己生成的有关内容外，还有比较关键的一点是比如“我”看了一些微博，但并没有转发他们，大多数情况下都不会转发，但有些“我”转发了，有些“我”评论了；“我”转发了哪些？
评论了哪些？这次距上次的浏览该人的列表时间间隔多久？都代表“我”对微博的兴趣，而间接地反映出“我”的兴趣特征。这些数据看来非常重要，但又无法直接取得，怎么办？
下面来定义一个场景，试图描述出我们对看过的内容中哪些是感兴趣的，哪些是不感兴趣的：
a）用户A，以及用户A 关注的用户B；
b）用户A 的每天动作时间（比如转发、评论、收藏、点赞的时间点）。其中起始时间定义为苏醒时间A_wake(t)；
c）用户B 每天发帖（转发、评论）时间：B_action(t)；
d）简单假设一下A_wake(t)> B_action(t)，也就是B_action(t)的评论都能看到。这就能得到用户A 对应了哪些帖子；
e）同理，也可知用户A 在A_wake(t)时间内转发、评论了哪些帖子；
f）结合上次浏览间隔时间，可以描述用户A 对哪些微博感兴趣（postive），哪些不感兴趣（negative）；
（2）全连接层的激活单元比对提升。
英特在学习Google 那篇论文后，比对隐含层（也就是结构图中的FC 层）各种单元组合产生的结果。
YouTube 推荐模型隐含层单元选择对比
Google 选择的是最后一种组合，英特在初期选用了512 tanh→256 tanh 这种两层组合，后认为输入特征维度过大，512 个单元无法完整地表达特征，故又对比了1024→512 组合，发现效果确实有微小提升，大概提升了0.7%。另外模型的FC 层输入在［-1,1］区间，考虑到relu 函数的特点故没有使用它，而是使用elu 激活函数。测试效果比tanh 函数提升了0.3%～0.5%。
本文选自《深度学习算法实践》，点此链接可在博文视点官网查看此书。
相关阅读
本教程摘选自 https://blog.csdn.net/qq_28205153/article/details/55798628 的原理部分。 AES简介 高级加密标准(AES,Advance
退火算法解决旅行员问题（学习笔记）给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。退火算法
SPFA 算法详解( 强大图解，不会都难！)&&spfa优化——深度
https://blog.csdn.net/muxidreamtohit/article/details/7894298 适用范围：给定的图存在负权边，这时类似Dijkstra等算法便没有了
A*算法和dijkstra算法都是启发式搜索，dijkstra算法可以看成是广度优先搜索，而A*可以认为是深度优先搜索。 dijkstra就是保证当前节
RSA是目前最有影响力和最常用的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。 RSA算