集奥聚合带你解密大数据ID-Mapping
来源：数据观 时间：2016-06-27 14:46:24 作者：集奥聚合
　　谈到大数据，有一个非常基本但又关键的环节就是ID-Mapping（Identifier -Mapping）。ID-Mapping通俗的说就是把几份不同来源的数据，通过各种技术手段识别为同一个对象或主体，例如同一台设备（直接），同一个用户（间接），同一家企业（间接）等等，可以形象地理解为用户画像的“拼图”过程。一个用户的行为信息、属性数据是分散在很多不同的数据来源的，因此从单个数据来看，都相当于“盲人摸象”，看到的只是这个用户一个片面的画像，而ID-Mapping能把碎片化的数据全部串联起来，消除数据孤岛，提供一个用户的完整信息视图，同时让某一个领域的数据在另一个领域绽放出巨大的价值。
　　ID-Mapping有非常多的用处，比如跨屏跟踪和跨设备跟踪，将一个用户的手机、PC、平板等设备的上的行为信息串联到一起。再比如这两年非常热的程序化交易，它的一个重要环节就是要把当前广告请求的用户和第一方DMP平台里的用户历史兴趣数据匹配起来。可以说，没有ID-Mapping，程序化交易就变成了盲目投放，它的实时竞价，精准投放的优势也就不存在了。
　　ID-Mapping既然有这么大的作用，那么应该如何做好ID-Mapping呢？这个环节不是一个简单的按照Key匹配的过程，集奥聚合作为领先的第三方大数据公司，研发了多项ID-Mapping 的独家技术，用新的匹配技术和算法模型来重塑了ID-Mapping过程。据粗略评估，集奥聚合ID-Mapping系统有能力把十几个数据源的 56亿ID（Identifier，即标识符）匹配到一起，准确率达到 95%以上，有效用户总量提升了30%，平均每个用户的标签量提升200%以上。值得注意的是，这里的Identifier是指标识符，而并非Identity（身份信息），集奥聚合可在完全脱敏，不（也无需）识别、指出用户姓甚名谁的身份信息的情况下合法地将标识符对应至某匿名用户。
　　简单来说，集奥聚合ID-Mapping体系有三个层面。
　　第一个层面是物理Mapping
　　这是最单纯基本的层面，也就是如何精准地记录和标识一个用户，例如利用硬件设备码生成一个统一的设备码，利用一些强账号来标识用户等等。这个层面上主要的技术难度在于ID的稳定性、唯一性和持久性。
　　第二个层面是基于用户行为做迭代滚动Mapping
　　由于原始数据存在噪音，同一个用户的多份数据、多种ID之间是“多对多”的关系。那么哪些ID是可信的呢？
　　我们设计了一个置信度传播的机器学习图模型来帮助确定哪些身份ID是可信的。

　　算法示意图如上，每个节点是一个UID或QQ号或GID等标识的潜在的“用户”
　　 一开始节点之间关系的概率是随机的
　　 其中总有两个ID的关系是强置信的prior
　　 迭代收敛后，哪些ID是归属于同一个用户的标识符被识别出来
　　大体来说，这个算法的过程是给每一个ID，以及两个ID，如IMEI和邮箱之间的pair关系都有一个预设的置信度。而所有的ID根据两两关联构成了一张图，那么每个ID的置信度根据这张网的结构传播给相关联的ID，同时也从其他ID那边接收置信度，而pair关系的置信度不变。当算法迭代收敛时，高置信度的ID就是可信的。同一个子图内的ID就标识了同一个用户。用类似的算法，我们也可以评价每个数据源的质量等。
　　第三个层面是基于用户兴趣做相似用户的合并
　　如果说层面二主要还在判断标识一个用户的ID是否正确，那么层面三致力于把行为相似的用户给合并起来。
　　例如，某一个用户的设备多次连接同一个Wi-Fi网关，但是每次链接都会随机更换ID，那么相当于这个用户的数据“分裂”在多个不同ID下。那么如何把这些ID合并成同一个用户呢？
　　除了上述做法之外，集奥聚合开发了相似用户合并技术。基于用户的上网时间偏好、网址访问偏好、点击行为偏好、浏览行为偏好、APP偏好和社交账号偏好等，为每个用户提取了上千个特征之后，进行相似用户的聚类。
　　聚类中选择类中心附近的用户，再加上一些辅助准则判定，就可以把用户合并起来。
　　经实际测试，可以把用户ID总量减少80%，同时保持用户合并的准确率在91%以上。使用的历史数据时间窗越长就越精准。仅此一项就能让用户的标签密度提升 500%。最早出现于安卓
深入浅出理解 Cookie Mapping
Posted on 2014 年 11 月 9 日 by Abbo
在RTB（实时竞价广告，Real-Time-Bidding）广告领域（当然实际上不仅仅是这个领域），有一个常见的词汇叫 Cookie Mapping（Cookie 匹配），一会又是DSP（需求方供应平台）与DSP的Cookie Mapping，一会又是DSP与Ad Exchange的Cookie Mapping，一会还有DMP（数据管理平台）与DSP的Cookie Mapping，已经完全把大家搞浑了。许多互联网广告从业者都不清楚到底什么是 Cookie Mapping，到底又是为什么要 Cookie Mapping。今天就以小小的笔记，分享大家疑问的解答。
用户唯一标识体系
在互联网中，我们有着许多标识唯一用户的技术手段，其中，最为常见的就是 Cookie 了（什么是Cookie请参看网站分析中的Cookie）。简单的多，Cookie具备几个特征：
• 唯一性，一个Cookie是唯一存在于一个域名下的；
• 归属权，一个Cookie必须属于某一个域名，且相互不能访问使用；
• 持久性，一个Cookie可以持久的存在于一个浏览器中。
正因为Cookie具备上述几个特征，也就衍生出Cookie在使用上的一些特点了，我们以DSP.COM（广告购买平台），ADX.COM（广告交易平台），DMP.COM（数据管理平台）为例，存在以下结论：
• DSP.COM，ADX.COM，DMP.COM都存在各自的用户标识体系（各自定义的唯一ID标识）；
• 用户Abbo在上述三个产品的ID分别是dsp-1，adx-a，dmp-①，且相互不能访问使用。
就这样，DSP.COM，ADX.COM，DMP.COM都可以唯一的标识出用户Abbo，但他们并不能互相读取标识信息。
共享用户特征
由于客户需求，广告主在DSP.COM，ADX.COM，DMP.COM均有业务存在：
• 广告主使用DSP.COM进行广告投放，并且用户Abbo点击了游戏广告；
• 用户Abbo主动使用了DMP.COM提供的浏览器购物比价插件服务；
• 用户Abbo点击过位于交易平台ADX.COM上的职业学习、求职类广告；
刚好，DSP.COM识别出了Abbo喜欢玩游戏特征，DMP.COM识别出了Abbo是男性用户，ADX.COM识别出了Abbo是个年轻人。此时问题来了，由于三方的数据并不共享，因此对于广告主而言，仅知道dsp-1喜欢玩游戏，adx-a是年轻人，dmp-①是男性用户。广告主并不能直接知道Abbo是个喜爱玩游戏的年轻男性。
最终目标，我们需要不同产品体系中的用户的特征，合并绑定到一个用户上来，这也就是本文主题的关键——Cookie Mapping。
常见 Mapping 方式
我们刚刚看到，不同厂商、产品对用户都使用了不同的标识体系，诸如dsp-a，adx-a，dmp-①此类。因此，我们在Cookie Mapping中的最为基础的信息表——ID映射关系，俗称Cookie Mapping表。它负责使dsp-1，adx-a，dmp-①关联起来。
要使同一个用户在不同体系中关联起来，只有一个做法，那就是当用户发生行为的时候，同时能够联通多家厂商、产品。也就是出现了以下最常见的几种Mapping方式生成ID映射关系表：
• 用户加载网页代码时候，同时加载DSP.COM，ADX.COM，DMP.COM的代码，互相调用Mapping接口传输ID信息；（客户端Mapping）
• 用户加载网页代码时候，由服务端转发携带ID的请求，由ADX.COM服务器告诉DSP.COM相关ID信息。（服务端Mapping）
这样一来，经过大量的Mapping匹配后，不同厂商、产品之间也就自然形成了一套对应ID映射关系表格了。
移动端的 Mapping
移动终端的发展趋势，Cookie的效果已经远不如PC端了——PC端的用户上网行为，往往发生在一两款Web浏览软件（浏览器）中，而移动端App较为分散，用户行为、特征体现在更多的应用程序（App）上。况且，移动终端的唯一性，存在着更多的ID体系标识唯一用户，诸如MAC地址、iOS IDFA、Android ID等等。这些ID往往是具备一定唯一性，并且能够在不同App中共享的标识信息。因此，移动终端有时候也不需要 Mapping，如果约定俗成的使用某一类ID也是可以进行唯一用户标识的。
斗胆小结
斗胆小结本文，观点并不一定全部正确，如有不足，还请点出：
• 唯一标识需求将长期存在；
• Cookie标识在PC端短期内（10年）不会消失；
• 多终端的发展，将出现更多标识体系；
• Mapping ID的需求将长期存在。
Open-ID是一个很好的想法，也是一个很好的应用，特别是第三方开源Open-ID产品，个人觉得还是值得一

一点做用户画像的人生经验（一）：ID强打通

1. 背景
   在构建精准用户画像时，面临着这样一个问题：日志采集不能成功地收集用户的所有ID，且每条业务线有各自定义的UID用来标识用户，从而造成了用户ID的零碎化。因此，为了做用户标签的整合，用户ID之间的强打通（亦称为ID-Mapping）成了迫切的需求。大概三年前，在知乎上有这样一个与之相类似的问题：如何用MR实现并查集以对海量数据pair做聚合；目前为止还无人解答。本文将提供一个可能的解决方案——如何用MR计算框架来实现大数据下的ID强打通。
   首先，简要地介绍下Android设备常见的ID：
   • IMEI（International Mobile Equipment Identity），即通常所说的手机序列号、手机“串号”，用于在移动电话网络中识别每一部独立的手机等行动通讯装置；序列号共有15位数字，前6位（TAC）是型号核准号码，代表手机类型。接着2位（FAC）是最后装配号，代表产地。后6位（SNR）是串号，代表生产顺序号。最后1位（SP）一般为0，是检验码，备用。
   • MAC(Media Access Control)一般代指MAC位址，为网卡的标识，用来定义网络设备的位置。
   • IMSI（International Mobile SubscriberIdentification Number），储存在SIM卡中，可用于区别移动用户的有效信息；其总长度不超过15位，同样使用0～9的数字。其中MCC是移动用户所属国家代号，占3位数字，中国的MCC规定为460；MNC是移动网号码，最多由两位数字组成，用于识别移动用户所归属的移动通信网;MSIN是移动用户识别码，用以识别某一移动通信网中的移动用户。
   • Android ID是系统随机生成的设备ID 为一串64位的编码（十六进制的字符串），通过它可以知道设备的寿命（在设备恢复出厂设置或刷机后，该值可能会改变）。
2. 设计
   从图论的角度出发，ID强打通更像是将小连通图合并成一个大连通图；比如，在日志中出现如下三条记录，分别表示三个ID集合（小连通图）：
   A B C

   C   D
       D   E
   

   通过将三个小连通图合并，便可得到一个大连通图——完整的ID集合列表A B C D E。淘宝明风介绍了如何用Spark GraphX通过outerJoinVertices等运算符来做大数据下的多图合并；针对ID强打通的场景，也可采用类似的思路：日志数据构建大的稀疏图，然后采用自join的方式做打通。但是，我并没有选用GraphX，理由如下：
   • GraphX只支持有向图，而不支持无向图，而ID之间的关联关系是一个无向连通图；
   • GraphX的join操作不完全可控，“不完全可控”是指在做图合并时我们需要做过滤山寨设备、一对多的ID等操作，而在GraphX封装好的join算子上实现过滤操作则成本过高。
   因而，基于MR计算模型（Spark框架）我设计新的ID打通算法；算法流程如下：打通的map阶段将ID集合id_set中每一个Id做key然后进行打散（id_set.map(id -> id_set))），Reduce阶段按key做id_set的合并。通过观察发现：仅需要两步MR便可完成上述打通的操作。以上面的例子做说明，第一步MR完成后，打通ID集合为：A B C D、 C D E，第二步MR完成后便得到完整的ID集合列表A B C D E。但是，在两步MR过程中，所有的key都会对应一个聚合结果，而其中一些聚合结果只是中间结果。故而引入了key_set用于保存聚合时的key值，加入了第三步MR，通过比较key_set与id_set来对中间聚合结果进行过滤。算法的伪代码如下：
   MR step1:
   Map:

   input: id_set
   process: flatMap id_set;
   output: id -> (id_set, 1)
   

   Rduce:

   process: reduceByKey
   output: id -> (id_set, empty key_set, int_value)
   

MR step2:
Map:
input: id -> (id_set, empty key_set, int_value)
process: flatMap id_set, if have id_aggregation, then add key to key_set
output: id -> (id_set, key_set, int_value)
Reduce:
process: reduceByKey
output: id -> (id_set, key_set, int_value)

MR step3:
Map:
input: id -> (id_set, empty key_set, int_value)
process: flatMap id_set, if have id_aggregation, then add key to key_set
output: id -> (id_set, key_set, int_value)
Reduce:
process: reduceByKey
output: id -> (id_set, key_set, int_value)

Filters:
process: if have id_aggregation, then add key to key_set
filter: if no id_aggregation or key_set == id_set
distinct

3. 实现
   针对上述ID强打通算法，Spark实现代码如下：
   case class DvcId(id: String, value: String)
   val log: RDD[mutable.Set[DvcId]]// MR1val rdd1: RDD[(DvcId, (mutable.Set[DvcId], mutable.Set[DvcId], Int))] = log
   .flatMap { set =>
   set.map(t => (t, (set, 1)))
   }.reduceByKey { (t1, t2) =>
   t1._1 ++= t2._1
   val added = t1._2 + t2._2
   (t1._1, added)
   }.map { t =>
   (t._1, (t._2._1, mutable.Set.empty[DvcId], t._2._2))
   }// MR2val rdd2: RDD[(DvcId, (mutable.Set[DvcId], mutable.Set[DvcId], Int))] = rdd1
   .flatMap(flatIdSet).reduceByKey(tuple3Add)// MR3val rdd3: RDD[(DvcId, (mutable.Set[DvcId], mutable.Set[DvcId], Int))] = rdd2
   .flatMap(flatIdSet).reduceByKey(tuple3Add)// filterval rdd4 = rdd3.filter { t =>
   t._2._2 += t._1
   t._2._3 == 1 || (t._2._1 – t._2.2).isEmpty
   }.map(._2._1).distinct()
   // flat id_setdef flatIdSet(row: (DvcId, (mutable.Set[DvcId], mutable.Set[DvcId], Int))) = {
   row._2._3 match {
   case 1 =>
   Array((row._1, (row._2._1, row._2._2, row._2._3)))
   case _ =>
   row._2._2 += row._1 // add key to keySet
   row._2._1.map(d => (d, (row._2._1, row._2._2, row._2._3))).toArray
   }
   }
   def tuple3Add(t1: (mutable.Set[DvcId], mutable.Set[DvcId], Int),

   t2: (mutable.Set[DvcId], mutable.Set[DvcId], Int)) = {
   

   t1._1 ++= t2._1
   t1._2 ++= t2._2
   val added = t1._3 + t2._3
   (t1._1, t1._2, added)
   }
   其中，引入常量1是为了标记该条记录是否发生了ID聚合的情况。
   ID强打通算法实现起来比较简单，但是在实际的应用时，日志数据往往是带噪声的：
   • 有山寨设备；
   • ID之间存在着一对多的情况，比如，各业务线的UID的靠谱程度不一，有的UID会对应到多个设备。
   另外，ID强打通后是HDFS的离线数据，为了提供线上服务、保证ID之间的一一对应关系，应选择何种分布式数据库、表应如何设计、如何做到数据更新时而不影响线上服务等等，则是另一个需要思考的问题。