基于智能手机用户行为习惯的App使用预测算法研究

王克强 王保群 张雨帅 王纪超

1(重庆邮电大学通信与信息工程学院 重庆 400065)2(重庆邮电大学移动通信技术重庆市重点实验室 重庆 400065)

0 引 言

随着智能手机进入人们的生活，涌现了各种各样的移动App以满足人们的生活需要。极光大数据在近日发布数据显示，国内高中低端机型的手机平均安装App数量分别为56个、52个和39个。然而调查研究表明，智能手机用户平均每天使用的应用程序数量大约为9个，大量安装的应用程序增加了用户查找APP的时间，占用了手机内存，造成手机卡顿等现象，严重影响了用户体验。

Trinh等[1]通过收集智能手机用户使用App数据，通过大数据分析得出手机用户使用App的行为是有一定规律的，例如用户在家或者工作中使用SMS最多，在休息时使用Media最多，在假期使用相机最多等行为，证明了用户使用App的行为可以通过研究用户使用App的行为习惯进行预测。因此，为了解决上述提出的问题，越来越多的人通过研究智能手机用户使用App的行为习惯，寻找用户与手机App使用之间的关系，以便预测用户将要使用的下一个App，从而可以将App提前预加载到手机中，减少手机App的冷启动时间，提升用户体验。

Huang等[2-4]根据用户浏览网页的行为习惯提出了基于贝叶斯模型和马尔可夫模型的Web网页预测模型。通过网页预测模型的启发，Ma等[5]提出了基于贝叶斯网络模型和线性回归模型的智能手机App使用预测算法，并且得到了较好的预测准确度；Song等[6]通过分析手机App后台运行情况，提出基于App共存模式的应用程序使用预测模型，实验分析该模型可使手机App的重启率降低10%；Shin等[7]分析设计了基于用户的朴素贝叶斯模型和基于App的朴素贝叶斯模型，得到可能使用App的Topk列表，并设计了最可能使用的App UI界面，从而大大减少了用户查找App的时间，得到了较好的用户满意度反馈；刘帅琪等[8]采用Apriori关联规则挖掘算法挖掘智能手机用户App使用记录中的序列模式，得到的预测模型能够为用户提供较为理想的App列表。但是以上研究仅仅是对智能手机用户使用App的记录来进行预测，并没有把单个用户对App的喜爱程度考虑在内，例如某些用户比较喜欢听音乐，那么该用户对音乐播放器的喜爱程度显然与其他手机APP的喜爱程度是不同的。

针对此问题，本文通过衡量智能手机用户使用App频次和使用App时长作为用户对App喜爱程度的度量，采用Weight-PrefixSpan序列模式挖掘算法挖掘用户使用App的行为习惯，结合贝叶斯网络整合用户App使用记录、使用App时间等特征，提出了一种新的预测下一个将要使用的App的方法，使得预测用户将要使用的App算法更加合理、准确。

本文的主要贡献为：

(1) 考虑智能手机用户对每个App的喜爱程度，设计实现了加入用户对APP喜爱程度的Weight-PrefixSpan序列模式挖掘算法，并将其与贝叶斯网络算法相结合，提出了一种新的预测用户下一个最可能使用的App的算法模型——WAPA算法。与传统Bayesian预测算法、Apriori预测算法相比，该算法有效地提高了预测准确度，且大大减少了算法模型的训练时间。

(2) 在不同用户数据集上的实验表明，本文提出的WAPA算法可以有效地挖掘用户使用App的行为习惯，提高预测准确率。

1 相关概念

1.1 PrefixSpan算法介绍

Han等[9]提出了一种挖掘序列模式的算法，其主要思想是检测成为prefix前缀的序列，将数据库在这个prefix上投影，挖掘其中的频繁项，然后扩充到prefix中，继续进行挖掘，直到挖掘出所有的频繁序列，PrefixSpan算法在时间和空间效率上比Apriori算法有较大提高。

设I={x1,x2,…,xn}是一个事件集合，其中xi代表集合中的事件。

定义1事件序列。设S={xi,xj,xk,…}是集合I的一个有序子集，其中i

定义2序列长度。序列中所有事件元素数目的总和。

定义3序列模式。若序列S在数据库中发生的次数不小于规定的阈值，则称S为序列模式。

PrefixSpan算法的步骤如下：

1)k=1；

2) 从数据库中发现长度为k的序列模式S1；

3) 以S1划分投影数据库，分别挖掘长度为k的序列模式为前缀prefix的长度为k+1的序列模式S=L，如果挖掘结果为空，则停止；

4)k=k+1，S=L，转步骤3)；

5) 记录所有挖掘到的序列模式。

1.2 贝叶斯网络

贝叶斯网络[10]，又称贝叶斯信念网络，是图论与概率论的结合。贝叶斯网络直观地表示为一个复杂的赋值因果关系图，完整的贝叶斯网络是一个二元组B=，其中：

(1)G=(V(G),E(G))，是一个有向无环图，V(G)是节点组合，节点表示所研究问题域中的变量；E(G)为弧集合，有向弧定性表示节点之间的概率依赖关系。

(2) 网络参数θ构成的条件概率表达了节点之间的因果依赖程度。

贝叶斯网络的数学基础是贝叶斯公式，基于先验概率，根据相关条件可推导后验概率。并且网络蕴含了条件独立性假设，如果给定根节点的先验概率分布和非根节点的条件概率分布，则可以通过推理得到包含所有节点的联合概率分布，如下式所示：

(1)

式中：Vi为网络节点；Pa(Vi)为节点Vi的父节点。

2 特征提取与分析

2.1 时间特征提取与分析

智能手机用户将要使用的下一个App与用户使用App的时间息息相关。我们将一天分为[0 ∶00-6 ∶00]、[6 ∶00-9 ∶00]、[9 ∶00-12 ∶00]、[12 ∶00-14 ∶00]、[14 ∶00-18 ∶00]、[18 ∶00-22 ∶00]、[22 ∶00-24 ∶00]7个时间段进行分析。

图1 各时间段APP使用情况表

分析用户在各个时间段对于App的使用情况得图1，可以看出SMS短信和Mobile mail邮件软件在9 ∶00-12 ∶00或14 ∶00-18 ∶00即工作时间使用次数较多，而YouTube视频播放软件在18 ∶00-22 ∶00即晚上休息时间使用次数较多，这说明了智能手机用户使用App的行为与每天的时间段有很大关系，所以我们选择时间段作为我们的一个特征。

2.2 App使用记录特征提取与分析

智能手机用户使用App的记录是预测下一个App算法的重要特征。手机用户使用App时大多有一定的规律，根据分析数据统计可得某用户一年内12 000条使用记录中，[SMS,Mobile mail]即使用完SMS后，下一个使用Mobile mail的频次多达600多次；[Facebook,youtube]的频次多达456次；类似使用记录在其他用户App使用记录中也很明显。故我们提取智能手机用户App使用记录作为我们的一个特征。

3 WAPA算法设计

3.1 问题分析

在预测用户将要使用的下一个App的过程中，传统的贝叶斯和其他App预测算法存在两个问题：

1) 传统App预测算法仅仅对App使用记录进行统计分析，并没有考虑用户使用App的习惯，没有挖掘出用户使用App过程中各App之间的规律。

2) 用户使用智能手机时大多数情况下仅仅喜欢使用其中几款App，传统App预测算法没有考虑到用户对各App的喜爱程度，而是认为所有App的重要程度相同，这显然是不合理的。

针对以上问题，本文对智能手机用户使用App的记录进行分析，通过衡量用户使用App的频次和使用App的时长，得到每个App的权重，用来表示智能手机用户对App的喜爱程度。采用Weight-PrefixSpan序列模式挖掘算法挖掘手机用户使用App的序列模式，并采用贝叶斯网络算法整合序列模式与使用时间段的关系，提出一种新的预测用户将要使用的下一个App的算法——WAPA算法。

3.2 Weighted-PrefixSpan序列模式挖掘算法

3.2.1相关定义

定义4App权重。给定一个App使用记录S={x1,x2,…,xn}，则App权重计算如下式所示：

w(xi)=αf(xi)+(1-α)t(xi)

(2)

式中:w(xi)为Appxi的权重，f(xi)为Appxi在使用记录s中的使用频次，t(xi)为Appxi在使用记录s中的使用时长，α为权重参数，用来权衡使用频次和使用时长两个特征。

定义5序列权值。给定一个App序列S={x1,x2,…,xn}和App权重集合w={w(x1),w(x2),…,w(xn)}，则App序列s的权值计算如下所示：

式中：n为序列中App的个数。

定义6App序列模式。给定一个最小App序列权值min_weight，如果某App序列s的序列权值权值不小于min_weight，即W(s)≥min_weight，则称该App序列s为App序列模式。

3.2.2Weight-PrefixSpan序列模式挖掘算法设计

本算法考虑智能手机用户对每个App的喜爱程度，通过衡量用户使用App的频次和使用App的时长，得到每个App的权重，序列模式挖掘过程中采用序列权值对算法生成的序列进行剪枝，从而得到我们所需的App加权序列模式。

Weighted-PrefixSpan序列模式挖掘算法流程如图2所示。

图2 Weighted-PrefixSpan序列模式挖掘算法流程图

3.3 WAPA算法

基于上述讨论，我们可以了解智能手机用户使用App的行为与该App的序列模式和使用时间段息息相关，本文采用贝叶斯网络算法将与下一个将要使用App具有因果依赖关系的App加权序列模式和App使用时间等特征进行整合，提出WAPA算法。如下式所示：

式中：P(A,S′,T)为序列模式S′,使用时间T，AppA的联合概率分布，序列模式S′由改进的Weight-PrefixSpan序列模式挖掘算法挖掘得来。由式(4)可得在使用时间段T内序列模式S′发生的情况下，下一时刻使用AppA的条件概率。

4 实 验

4.1 实验配置

实验软硬件配置如表1所示。

表1 实验配置

4.2 数据集的选择

本文采用美国国家科学基金会资助的livelab项目提供的数据集，该数据集包含了34名学生在一年内的手机使用情况，包含App使用记录、使用App的时间、地点、手机、充电状态、加速度状态、CPU利用率、Wifi连接情况等等。我们对数据集中的特征进行分析，综合每个特征的可利用性，最终简化特征数量，选择对于预测用户将要使用的下一个App最重要的2个特征：智能手机用户使用App的时间和App使用记录。从数据集中随机抽取70%作为训练集，其余30%作为测试集。

4.3 评价指标

指标1准确率(Accuracy)表示App预测过程中预测正确的次数占总预测次数的比值。计算公式如下：

一般情况下，模型的准确率越高，说明模型的效果越好。

指标2训练时间指在实验中，模型训练所用运行时间越短，占用资源越少，对用户影响越小，算法越好。

4.4 实验结果分析

(1) 候选App个数的确定 由图3可以看出当候选App个数为3～4个时，WAPA等各种算法的预测准确率较好。当继续增加候选App个数时，预加载App所占用资源会继续增加，但是总预测准确率增加较少。

图3 不同个数候选App下预测准确率

综上所述，我们预加载App时，只需要预加载准确率最高的3～4个App即可，此时可在保证准确率的情况下尽量少地占用手机资源。

(2) 权重参数α的确定 首先，初始化α=0.1,0≤α≤1，采用轮询方式获取使得准确率(Accuracy)最高的α，此时的α即为App使用频次和App使用时长最佳参数。实验结果如图4所示。

图4 不同权重参数α下的预测准确率

由图4可知，准确率(Accuracy)随权重参数α(即使用时间和使用频次的衡量变量)的改变而改变，当α=0.8左右时准确率最高，即此为衡量用户使用App时长和使用频次所占比重的最佳值。

(3) 序列长度的确定 序列模式挖掘过程中，我们会挖掘到序列长度为1的序列模式、长度为2的序列模式、长度为3的序列模式等等，分别计算在各序列长度下预测的准确率。实验结果如图5所示。

图5 序列长度与预测准确率

如图5所示在序列长度为3时，App预测的准确率最高，当序列长度为1时，相当于直接统计各App的使用频次。当序列长度过长时，前面的App使用对下一个App的使用影响较小，对于用户行为习惯不具有代表性，导致预测准确率降低。

(4) 不同算法训练时间比较 不同算法的准确率和训练时间如表2所示。

表2 各算法训练时间

由表2可知，WAPA算法因为加入了智能手机用户对App的喜爱程度，我们得到的下一个App就是用户喜爱程度较高的App，所以预测准确率较其他算法稍高。由于WAPA算法采用Weighted-Prefixspan算法挖掘序列模式过程中，采用剪枝过程大大减少了挖掘序列模式的运行时间，故算法的训练时间较其他算法有了很大改善。

5 结 语

本文针对智能手机用户使用App过程中的行为习惯，将用户对于App的喜爱程度考虑在内，提出了一种新的基于用户行为习惯的下一时刻将要使用App的预测算法。该方法首先采用序列模式挖掘技术挖掘用户使用App过程中的序列模式，然后使用贝叶斯网络将序列模式、使用时间等特征进行整合。实验表明，相比于其他算法模型，本文提出的WAPA算法能够有效地预测下一个App的使用，而且算法中的剪枝操作大大减少了模型的训练时间。下一步的研究将着重于算法的应用，同时考虑智能手机预加载App所占用的资源与用户体验提升之间的关系衡量。