2019-04-04

一、实体识别

同名异义

异名同义

单位统一

ID-Mapping

谈到大数据，有一个非常基本但又关键的环节就是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%。

讲解ID-Mapping算法之前，先说几个重要概念：

MAC(Media Access Control)，MAC位址，为网卡的标识，唯一标识网络设备。

IMEI（International Mobile Equipment Identity），通常说的手机序列号、手机“串号”，在移动电话网络中识别每一部独立的手机等行动通讯装置；序列号共有15位数字，前6位（TAC）是型号核准号码，代表手机类型。接着2位（FAC）是最后装配号，代表产地。后6位（SNR）是串号，代表生产顺序号。最后1位（SP）一般为0，是检验码，备用。

IMSI（International Mobile SubscriberIdentification Number），储存在SIM卡中，区别移动用户的有效信息；其总长度不超过15位，同样使用0～9的数字。其中MCC是移动用户所属国家代号，占3位数字，中国的MCC规定为460；MNC是移动网号码，最多由两位数字组成，用于识别移动用户所归属的移动通信网;MSIN是移动用户识别码，用以识别某一移动通信网中的移动用户。

Android ID是系统随机生成的设备ID 为一串64位的编码（十六进制的字符串），通过它可以知道设备的寿命（在设备恢复出厂设置或刷机后，该值可能会改变）。

UDID （Unique Device Identifier），苹果IOS设备的唯一识别码，它由40个字符的字母和数字组成，为了保护用户隐私苹果已经禁止读取这个标识了。

UUID（Universally Unique IDentifier），是基于iOS设备上面某个单个的应用程序，只要用户没有完全删除应用程序，则这个 UUID 在用户使用该应用程序的时候一直保持不变。如果用户删除了这个应用程序，然后再重新安装，那么这个 UUID 已经发生了改变。缺点是用户删除了你开发的程序后，基本上无法获取关联之前的数据。

OpenUDID，不是苹果官方的，是一个替代 UDID 的第三发解决方案， 缺点是如果你完全删除全部带有OpenUDID SDK 包的App（比如恢复系统等），那么OpenUDID 会重新生成，而且和之前的值会不同。

IDFA （广告标示符），苹果禁用UDID后想出了折中办法，就是提供另外一套和硬件无关的标识符，用于给商家监测广告效果，这就是IDFA。用户可以在手机设置里改变这串字符，会导致商家没有办法长期跟踪用户行为。

telphone(手机号)。 手机号也可以唯一的标识用户。因为两个人的手机号在同一时间内不会一样。

上面给出的这几个信息都可以唯一标识一位用户，可以作为用户ID号。

假设有一位用户张三，在第一个手机上使用百度地图， 在ipad上观看百度爱奇艺视频，在第二个手机上使用手机百度app, 在pc电脑上使用百度搜索，如何将同一个用户在这些不同端的用户信息聚合起来呢？

ID-Mapping主要解决这个问题，用来关联ID信息。

算法思路

我们把用户在各个端的信息收集起来，假设输入两条日志的id信息为：

line1:  < mac1,mac2>  < imei1>  < tel1>

line2:    < mac1>        < imei2>  < tel1,tel2>

上下是两条用户行为日志，看到他们都有mac1，两条数据应该是同一个用户。

使用多轮map-reduce的聚合方法,map做数据分块，reduce做归并

第一轮，以mac1和 mac2为key字段来map和reduce

Map 输出：

mac1  line1  < mac1,mac2 >  < imei1>  < tel1>

mac2  line1  < mac1,mac2>  < imei1>  < tel1>

mac1  line2  < mac1>        < imei2>  < tel1,tel2>

Reduce 输出：

line1  < mac1,mac2>  < imei1,imei2>  < tel1,tel2>

line1  < mac1,mac2>  < imei1>      < tel1>

line2  < mac1,mac2>  < imei2,imei1>  < tel1,tel2>

第二轮, 以line1和 line2为key字段来map和reduce

Map 输出：

line1  < mac1,mac2>  < imei1,imei2>  < tel1,tel2>

line1  < mac1,mac2>  < imei1>        < tel1>

line2  < mac1,mac2>  < imei2,imei1>  < tel1,tel2>

Reduce 输出：

line1  < mac1,mac2>  < imei1,imei2>  < tel1,tel2>

line2  < mac1,mac2>  < imei1,imei2>  < tel1,tel2>

第三轮, 以< mac1,mac2>为key字段来map和reduce

Map输出：

< mac1,mac2>  < imei1,imei2>  < tel1,tel2>

< mac1,mac2>  < imei1,imei2>  < tel1,tel2>

Reduce输出：

< mac1, mac2>  < imei1,imei2>  < tel1,tel2>

依次指定< id >重复上述过程，直到无法归并

数据和索引设计

数据库表的设计，设置global-id作为主key，(类似身份证号的作用)，其他的字段都可以有多个（map< string,int>），这些用来表示一个用户的多个身份标识。

//数据表

global_id              string,

imei                    map<string,int>                           

mac                    map<string,int>                           

imsi                    map<string,int>                           

phone_number            map<string,int>                           

idfa                    map<string,int>                           

openudid                map<string,int>                           

uid                    map<string,int>                           

did                    map<string,int> 12345678910

例如这四条记录可以看到其实是一个用户，存储的时候就把它们存为一个用户，用global_id作为key。

由此得到 

global_id <=> imei,mac,imsi,phone_number,idfa,openudid,uid,did的相互映射关系。

//索引表

id              string                                     

global_id        string                                     

1234

线上查询的时候,假设获取了mac1类型ID, 根据mac的索引表获取global_id,然后根据global_id数据表获取用户imei、phone_number等其他ID信息。

ID过期问题

对于僵尸用户，或者长期不用的用户，保存数据没有意义，浪费资源而且数据长期不更新后可能数据不准确。

可以对每个ID加入活跃度参数，一方面代表用户的活跃程度，一方面可以对ID的存储做控制。

用户行为数据：代表了用户的活跃度，数据入表活跃度设置为0

ID Mapping历史数据：按周更新，代表上周用户的数据，迭代计算时，活跃度+1

全量用户信息数据：代表全量用户，数据引入时，设置活跃度参数为一个合理值。（eg: 60）

原文：https://blog.csdn.net/lili0710432/article/details/78970856

二、冗余性识别

冗余性产生原因

解决数据冗余性