一种基于动机感知的用户识别实时算法①

张梦菲 邱 强 肖茁建 姚 晓 方金云

(*中国科学院计算技术研究所 北京 100190) (**中国科学院大学 北京 100190)

0 引 言

Web数据挖掘一直是学术界和工业界研究的热点之一。随着大数据技术的发展,面向电子商务的Web数据挖掘在智能推荐、广告投放等领域发挥着越来越重要的作用。截至2018年12月,我国网络购物用户规模达到6.10亿,电子商务已成为大数据的重要来源[1]。用户识别技术作为Web日志挖掘的基础, 是从大量无序的数据中分析出匿名用户的独立行为轨迹和特征,并最终识别出唯一的用户个体。其结果的准确性直接影响了后续数据挖掘和个性化服务的效果。因此,研究电商平台的用户识别具有重要的应用价值。

用户识别技术的研究主要集中在Web数据挖掘[2]、电子设备[3-5]、文本信息中匿名作者[6，7]以及共享账户[8]等领域。在Web挖掘领域中的用户识别方法主要有2种：(1)基于启发式规则的方法[9，10]；(2)根据用户行为模式的方法。基于启发式规则的识别算法利用IP、用户代理(userAgent)、cookie技术识别用户，userAgent是用户的操作系统及其版本信息和浏览器及其版本信息。Yen等人[10]在启发式规则中证明了cookie技术比IP+userAgent方法具有更高的识别用户准确率，然而由于用户隐私问题，很难获得cookie数据的完整数据项。肖慧等人[11]提出了重写URL的IASR(IP，agent, session and referrer)算法用户跟踪方法，在启发式规则中引入用户会话(session)来识别用户，该方法在服务器端支持session的情况下提高了准确率，但是实际情况中难以保证session的完整性和实效性。基于行为模式的用户识别算法根据用户兴趣和习惯的独特性[12]和稳定性[13]，并利用数据挖掘和机器学习算法对点击流数据分类和预测来识别用户。Yang[14]提出了一种用户画像识别用户的算法，通过对时间T之前已知用户会话行为建立用户画像来预测未知用户，该方法对小规模数据取得了不错的效果，但对于规模较大的网站该算法不具备可行性。Naini等人[12]将数据划分成匿名和已知用户数据，并用直方图展示用户2个星期内访问不同网站的习惯和行为信息，把问题转化为2个图的最小带权匹配问题，准确率达到90.0%，但该算法主要针对的是用户在多个网站的访问行为，实际用户在一个电商网站的访问行为要更复杂。

在电商平台中，用户识别面临着以下的问题：(1)“多用户问题”和“单用户问题”，同一个用户在不同的时间内通过在地址栏输入URL或从收藏夹中进入网页会被识别为多个用户，即“多用户问题”；多个用户共享一个IP甚至使用同种设备和浏览器可能会被识别为一个用户，即“单用户问题”。(2)效率问题，关键绩效指标(key performance indicater, KPI)指数在百万级别以上的情况下，对用户识别算法的效率提出了更高的要求。Web日志处理也越来越趋于实时化[15，16]。

针对以上问题，本文以义乌购小商品官网电商平台义乌购(www.yiwugo.com)的实际运营数据为研究对象，提出了基于Spark[17]的启发式和用户动机感知相结合的通用用户识别算法(Spark based user identification by Heuristic rules and user motivation perception，SHUMP)。SHUMP算法采用初次匹配、精确识别的二阶段模式来实时识别用户。在初次匹配阶段,利用用户IP、用户代理(userAgent)、cookie、用户会话(session)、引用(referer)等信息匹配用户。在精确识别阶段,提取每条点击流日志的URL特征,通过感知用户动机来精确识别用户身份。对于“多用户问题”和“单用户问题”，该算法在用户的session或者cookie缺失、用户设备相同、引用信息无法匹配的情况下，根据用户的行为动机来区分用户，将动机相似的识别为同一个用户，从而解决“多用户问题”；将动机不同的识别为多个用户，从而解决“单用户问题”；并对上述算法在Spark计算框架下进行了优化。

本文第1节介绍用户识别中的概念和问题定义。 第2、3节分别介绍了SHUMP算法中2个阶段的具体技术细节。第4节介绍为解决实时化用户识别算法效率设计的分布式计算方法。第5节对本文算法进行实验验证和分析。第6节总结并展望本文的用户识别算法。

1问题定义

定义1日志的用户访问记录集合I=，其中m为记录的个数，pi(1≤i≤m)是每个用户的一次页面访问记录。

定义2网站每个用户的一次页面访问记录表示为：pi=,pi的各个数据项记录了用户单次访问的行为信息,包括时间(time)、地点(IP和userAgent)、用户(userId)、来源(referer)、内容(URL)、会话ID(sessionId)、cookie、状态(status)等信息。

定义3电商平台中用户类型集合如图1所示，其中U1是已识别用户，对应定义2中userId数据项不为空的记录；U2是可追踪用户，对应定义2中cookie数据项不为空的记录，系统可以通过cookie数据项追踪用户；U3是未识别用户，对应定义2中userId和cookie数据项都为空的记录，网站只能获取这类用户的IP和userAgent信息。

定义4定义3中的U2、U3是本文的研究对象。用户识别是将定义2中userId数据项为空的记录与其他记录进行分析，判定哪些是同一个用户的行为记录，并为这些用户生成唯一的ID编码，即userId。

图1 用户类型集合

2 基于启发式规则的初次匹配算法

本文对电商平台的所有日志数据分别根据IP+userAgent、cookie和userId划分为三级桶，其中在二、三级桶数据划分时，第1个阶段按照启发式规则进行初步匹配，第2个阶段用URL动机感知的算法来精确识别用户。

基于启发式规则的初次匹配算法是以userId、cookie、session和网站拓扑结构信息为用户初次识别的4个维度值，并根据相关规则进行匹配。具体步骤见算法1。

算法1启发式规则的初次匹配算法输入:2个用户的行为特征feature1和feature2输出:feature1和feature2是否匹配 1.if(f==0){key1= l1.cookie,key2 = l2.cookie} else {key1= l1.userId,key2= l2.userId} 2.if(key1!= null&key1== key2){return true} 3. if(l1.session == l2.session){return true} 4.if(l1.referer == l2.url){return true} 5. if((l1.referer == l2.referer)&(l1.url == l2.url)){returntrue}

算法输入为定义1中的2条日志l1和l2标志位f,f代表要匹配的是cookie还是userId。如果非空的userId、cookie或者session相同,算法直接判定为同一个用户;否则,按照网站的拓扑结构,如果当前URL可以由上一条记录到达,则匹配。

3 基于动机感知的精确用户识别算法

3.1 动机感知模型

电商平台的用户动机主要反映在URL中,URL中包括了用户浏览、搜索、点赞、购物车等行为信息,通过感知用户的动机,将用户访问行为反馈到用户识别。本文通过对每条URL提取出类型(type)、网站版块(block)、访问的商铺ID(shopId)、访问的商品ID(productId)、搜索关键词(word)5个特征来构建用户的访问动机模型。具体步骤见算法2。

算法2动机获取算法输入:URL输出:该URL所反映的用户动机 1.对每条URL提取出特征type 2.如果type = 4, 提取block 3.如果type = 3,解析搜索词word 4.如果 type = 7,提取shopId和productId

算法2构建了每条点击流日志5个维度的用户动机模型，其中特征type代表用户的不同行为类型,如表1所示，以电商网站为例,当type=4时,表示用户在浏览网站的版块(block),如:论坛、采购、投诉等版块。shopId、productId、word 3个特征包含了用户感兴趣的商铺、商品和搜索求购信息。表2展示了3种不同类型访问记录的动机解析结果，其中空白部分表示对应的信息不存在，shopId和productId提供的用户动机信息还需根据3.2节内容来计算。

表1 典型的电商网站URL类型解析

表2 义乌购URL动机解析示例

3.2 相似度计算

用户访问动机是指在一定时间阈值T范围内的用户访问轨迹，本文取阈值T=30 min。用户动机中如果不包含shopId、productId、word 3个特征，则匹配URL的type和block;否则根据shopId、productId、word 3个特征对应的商铺主营范围、商品标题、搜索词来计算动机的相似度矩阵。

相似度矩阵是通过计算2个用户行为动机模型的相异数来确定用户动机的距离。文献[18]提出了利用相异数计算2个词的距离，相异数越小，说明距离越小，2个词越相似。算法提取了商品标题、商铺主营范围、搜索词等短文本的核心词集合，并把核心词映射到商品分类树的节点上，计算树的各个节点之间的距离,得到基础相异数；并利用式(1)，从基础分析、文本分析、维度分析和扩展分析4个角度修正相异数，其中tagi是核心词、id是核心词在分类词库中的词码，disij是基础分析得到的相异数，f1、f2、f3、f4分别是从词频分析、位置分析、附属维度和品牌维度得到的计算因子，表示该核心词在短文本中的重要程度,具体描述见算法3。

(1)

算法3相似度计算算法输入:2个用户行为的特征feature1和feature2输出: 2个行为是否匹配 1. 初始化阈值threshold 2. if (feature1和feature2的word、shopId、productId的任何一个特征同时存在){转至第4步} else {转至第3步} 3. if(feature1.match(feature2)){return true} else{return false} 4. T1=提取feature1的核心词集合 T2=提取feature2的核心词集合 5. 计算T1和T2的相异数value; 6. if(value> threshold){return false} else{return true}

表3～表5是商铺主营、商品标题、搜索词3种用户行为动机模型的提取核心词示例,其中商品标题的核心词用相异数修饰其在标题中的重要程度。表6是用户行为动机相似度矩阵计算结果，P1、P2、S1、S2、W1、W2代表表3～表5提取的核心词，S1指

表3 商铺核心词提取示例

表4 商品相异数示例

表5 搜索词核心词提取示例

表6 用户行为相似度矩阵计算结果

一条URL代表的用户行为是访问了一个商铺，该商铺的主营是S1。表中的值代表用户行为相异数，S1和P1的用户行为相异数是0。当type和block相等或用户行为相异数小于阈值threshold时,则判定两条URL为同一个用户。

4 二阶段识别算法的实时化

二阶段识别算法的复杂度为O(n2)，如何满足在线访问用户的实时识别直接关系到电商平台推荐系统的用户体验。本文在Spark分布式计算框架下对算法进行了优化,算法流程如图2所示。

步骤1数据清洗,Spark Streaming从Kafka中并行读取实时数据流,并调用filter 算子,将日志爬虫和异常信息过滤,得到真实用户访问的数据流normalDStream;

步骤2一级桶划分,将日志数据以IP+userAgent作为key值,对相同的key进行数据划分,产生一级桶数据b11，b12，…，b1n，数据集合为IADStream;

步骤3数据匹配，调用groupBykey算子和mapValues算子，在每个桶b1i中进行数据匹配,数据匹配包括初次匹配和URL动机相似度计算;

步骤4二、三级桶划分,对一级桶b1i进行桶划分的原则是:假设pi∈b1i并且pj∈b1j，则在b1i中总是存在记录pk(i≤k≤j),pi和pk相互匹配并且pk和pj相互匹配。通过判断第2节中算法1 (l1,l2,f)的f标志位，并按照cookie和userId划分成二、三级桶数据b2i，和b3i;

步骤5userId生成，为所有匿名用户生成userId，登录用户的userId保持不变。

SHUMP算法利用Spark将日志数据划分成大小均衡的DStream数据流，分配到指定多个节点的内存中，并利用转换算子对数据进行三级桶划分和用户识别，从而找到用户各自所属的类别。

图2 SHUMP算法并行计算流程

5 实验结果与分析

5.1 实验数据集与环境

本文采用义乌购(www.yiwugo.com)网站的nginx日志数据,该网站依托全球最大的小商品批发市场——义乌小商品城。网站每天产生百万级别的真实点击流日志记录，其数据格式如表8所示，每一条日志对应定义2中的pi。

本文从用户识别的准确性和效率2个方面进行了实验验证。在由7台服务器搭建的集群环境中，每台节点都配置jdk1.8、Hadoop-2.7.0、Zookeeper-3.4.8和Spark-2.2.0相关环境，采用主从方式进行实验。表7是实验所用服务器的硬件配置信息。

表7 服务器硬件配置信息

5.2 准确性验证

5.2.1 准确率验证

在准确率实验中,本文将日志按照天进行分割,对2017年10月1日至10月31日31天的日志进行预处理,抽取出登录用户的日志,并将日志中的userId数据项清除。式(2)是准确率计算公式,其中,originalNum为清除userId数据项之前的原始用户数量,SHUMPNum为经过SHUMP算法计算得到新的用户数量。算法准确率最高达99.97%,月平均值为97.89%(图3)。

accuracy=

(2)

表8 义乌购电商平台nginx日志格式

图3 1个月内SHUMP算法的准确率变化图

5.2.2 对比验证

文献[12]构建用户之间访问路线的二部图结构，然后计算二部图的最大匹配，但是实验数据将用户访问的URL加密，每个网站作为最小单位，计算匿名用户访问不同网站的统计信息，并且数据量小，极大简化了用户识别的问题，然而并不适用于内容繁多、页面链接复杂的的Web场景。文献[14]将用户识别问题转化监督问题，基于用户行为预先建立用户画像，然后按照session进行匹配得到分数，并分类到已知的用户中，在小数据集比如2个用户的识别上准确率最高达到99.30%，低于本文算法的准确率，然而该算法随着数据量增大，准确率下降，仅在100个用户的数据集上准确率就下降至87.36%。以上方法不仅存在大数据量的可扩展性问题，效率也没有得到验证。与监督学习不同的是，本文的方法并非将测试数据分类到正确的类别上，而是将一组用户同时找到它们各自所属的：“类别”，它们可能为同一个用户，也可能属于独特的一个用户，本文方法能找出并赋予它们独特的ID。在对比实验中，本节与复现的文献[11]进行实验对比，验证SHUMP算法的时间效率和用户数量，同时将与部署的百度统计结果进行对比，进一步验证算法的可靠性。

表9展示了原始记录数为500万条的日志经过IASR算法和SHUMP算法之后的数据，SHUMP算法处理速度明显高于IASR算法，识别的用户数量多于IASR算法，由于IASR算法仅仅考虑传统的启发式匹配规则，对于IP地址和设备相同的用户，如果用户禁用cookie等信息，或者从网页收藏夹直接进入网站造成引用信息无法获取，该算法无法区分不同的用户，无法解决“单用户问题”和“多用户问题”，而SHUMP算法则会根据用户的动机进行相似度匹配计算，可以识别出更多的真实用户，提高识别准确率。

表9 SHUMP与IASR算法效率和准确率对比

另外，本文在义乌购网站中部署百度统计对比识别出的网站用户个数，实验通过计算网站14天的用户识别数量与百度统计相同时间段内的用户数量对比如图4所示。可以看出指标的趋势基本一致，但本文数据比百度统计略高，这是因为百度统计依赖于浏览器设置cookie、JavaScript、图片等，如果浏览器禁用，则无法获取访问数据，本文直接分析实际的日志文件，不受浏览器的限制,数据更加完整。因此本文的用户识别算法是可靠的。

图4 百度统计与SHUMP算法识别出的用户数量对比图

5.3 效率验证

实验将一段时间的日志数据预处理之后得到正常数据，并分成20份，从50万条日志增大到1 000万条。实验分别用单线程、多线程、Spark框架实现二阶段用户识别算法，并按式(3)计算3个算法的处理时间。其中，Ti代表各个数据量的算法处理时间，Ti由统计10次处理时间求平均并4舍5入求整得到。

(3)

图5为3种二阶段用户识别算法效率随着数据量大小的变化趋势，其中，HUMP with single thread和HUMP with multi-thread为二阶段用户识别算法的单线程和多线程实现版本，统称为单机算法(HUMP)，SHUMP是二阶段用户识别算法在Spark上的优化。可以看出，多线程HUMP算法处理时间低于单线程HUMP算法，但二者皆在数据量达到900万条之后处理时间陡增，而SHUMP算法处理时间远远低于HUMP算法，集中在0～1 s，表10详细记录了其执行时间。在百万级别的数据情况下SHUMP算法耗时始终保持毫秒级，可以满足用户实时识别的场景。

6 结 论

本文采用启发式规则初次匹配和用户动机精确识别的二阶段识别用户算法。对于cookie相同或者session相同或者符合网站拓扑结构或者访问动机相同的用户,算法分配相同的ID。用户动机分析有效解决了相同IP地址的多个用户使用同种操作系统和浏览器访问网站会被认为是单用户的问题以及当一个用户多次直接进入网页被认为是多用户的问题。实验表明SHUMP算法具有较高的准确率和处理效率,比百度统计结果更可靠。SHUMP算法已经应用在义乌购电商平台。

图5 SHUMP算法与HUMP单线程和多线程算法随着数据大小变化执行时间变化图

表10 SHUMP算法随数据量大小变化处理时间分布

本文提出的SHUMP算法为用户行为分析和商品推荐奠定了基础,算法对电商网站的用户识别具有一定的通用性。但受电商业务影响,用户动机模型不尽相同,用户的个性化访问习惯也增加了用户识别的难度,这将是下一步研究的内容。