李春生,刘小刚,焦海涛,张可佳

(东北石油大学计算机与信息技术学院，黑龙江 大庆 163318)

0 引 言

随着网络信息时代的到来，应用APP已经涉及人们生活的各个领域，如何快速准确地获得人们所需要的APP资源成为APP搜索系统的研究热点。每天互联网上涌现出大量不同类型的APP信息资源，这些APP信息资源中存在多种同类产品。因此，如何对这些多种同类APP产品进行合理排序，需要定量地对APP间的相似度进行计算。智能PC设备已经成为人们生活中不可或缺的一部分[1]，伴随而来的是各种PC应用软件的应运而生。应用软件作为智能PC的最小功能单元，已经涉及人们生活的各个领域。在面对如此各式各样的APP时，用户如何快速准确地选择适合自己的APP成为一大难题。搜索引擎的出现极大地解决了信息量过载问题，大大提高了信息的搜索效率。

目前搜索引擎[2]在第三方推荐系统中被广泛应用，极大地提高了用户搜索匹配APP的速率。搜索按照搜机索制的不同，分为目录型、关键词型和混合型搜索引擎[3]。近年来，推荐系统在各个领域都被广泛使用，并取得了一定成就[4]。在众多的推荐系统中，主流的推荐系统算法大致分为2类：一类是基于用户行为数据的协同过滤算法，另一类是基于内容数据的过滤算法。前者适用于用户和项目较多，数据比较丰富的情况，具有较高的准确率，它是根据具有类似观点用户的行为对目标用户进行推荐[5]。后者仅仅需要得到2类信息：描述项目的特征和用户曾经的爱好，并且这种推荐方式完全是按照信息的具体内容与用户爱好间的相关性达到向用户推荐的目的，因此较适合文本信息推荐[6]。面对如此众多的移动APP，推荐系统逐步被应用在APP市场[7]。

如今国内官方尚未公布APP的排名算法，但也易了解到影响APP排名的因素大致有：应用名称、副标题、关键词、应用描述、应用评论、下载量、活跃度等。例如：百度手机助手是“官方认证”的副标题起到关键作用，它的名字中含有当前最热门的关键词“百度”，从而影响到该APP的排名。小米应用商店其实也是可以添加副标题的，这里把小米应用商店看成是关键词和首发。目前国内各种推荐系统都采用各自的APP排序算法，但是对于2种相似度极高的APP，并没有提出一种解决该类问题的办法。如何定义2个APP之间的相似程度成为相似APP推荐的关键[8]。因此，本文在原有PageRank算法基础上，提出一种扩大同类APP相似度的改进算法，并对计算所得TPR值最大的APP标出“权威”字样，方便用户区分众多同类APP。个性化的APP推荐系统最终研究目的是满足用户的个性化需求[9]。

1 PageRank算法

1.1 算法思想

PageRank算法又名页面排序算法，是Google的2名创始人Larry Page和Sergey Brin[10]于20世纪末提出的一种测评网页等级/重要性的算法，同时该算法也作为Google用来判定网站好坏的唯一标志，又是作为全球Web页面的排序算法[11]。PageRank算法里面的Page不是指网页，而是指Larry Page本人，目的是为了纪念Larry Page对该算法的贡献。该算法在当时Google搜索引擎查询结果的排序上起了至关重要的作用，同时该技术也为Google早期的核心技术之一。PageRank算法的核心思想概括为：通过PR值的高低描述一个网页的重要性，PR值越高，被其他网页链接得越多，网页越重要。PageRank算法认为被多个重要页面引用的网页，依旧是重要的网页[11]。

本文涉及的数学概念有：

1)强连通图：在简单有向图G中的任意一对节点间，至少存在一个节点是可达的，则称这个图是单连通的。如果在图G中任意2节点间均可达，则称这个图是强连通图[12-13]。

2)矩阵的转置：将矩阵的行列互换得到的新矩阵称为原矩阵的转置矩阵。

3)正向相似：通过搜索引擎搜索APP1时会将与其相似的APP2也一同搜到，对于APP1来说，APP1正向相似于APP2。

4)反向相似：通过搜索引擎搜索APP1时会将与其相似的APP2也一同搜到，对于APP2而言，APP2反向相似于APP1。

1.2 计算过程

PageRank算法最初是通过网页之间的超链接关系来确定网页的等级排名，本文使用它来代表同类APP间的相似度。PR值越高，该APP越权威，越容易从同类APP中区分。PR值是由某段时间内APP的下载量和卸载量决定的。传统的PageRank算法的数学表达式：

(1)

在式(1)中，N为同类APP总数；d为0～1之间的经验常数，d值越高，表示用户卸载当前APP随机下载其它同类APP的概率就越大；PR(x)为APP的PR值；Tn表示x的第n个同类APP；PR(Tn)表示APP Tn的PR值；1-d表示用户继续使用当前APP的概率；C(Tn)为与Tn正向相似的APP数量。

下面通过示例对PageRank算法的计算过程进行描述。图1是多个同类APP间具有的相似关系模型图，顶点代表应用软件APP节点，有向边代表APP间具有正向相似关系。

图1 APP间绑定关系

首先定义：应用APP ui正向相似vi时，即当搜索引擎搜索应用APP ui时，同时也会搜索到应用APP vi。图1对应的邻接矩阵中当APP ui正向相似于APP vi时，A[i,j]=1，否则A[i,j]=0，则该邻接矩阵的公式如下：

(2)

公式(2)中E表示应用APP vi与APP vj的正向相似关系。图1的邻接矩阵如下：

(3)

接着定义APP相似概率矩阵：将矩阵(3)中每一行除以该行非零数字之和，即能得到图1的APP相似概率矩阵如式(4)所示。该矩阵记录了每个顶点(APP)与其他顶点(APP)相似的概率，即其中i行j列的值表示用户从APP i相似于APP j的概率。

(4)

将矩阵D转置得到图1的转移概率矩阵P如式(5)所示，明显矩阵P是矩阵A的行归一化矩阵，目的是为了在计算迭代时每个节点的概率之和为1。

(5)

再定义PageRank概率向量u，其中ui表示搜索引擎搜索当前APP却搜到vi的概率，那么当前APP的PageRank值计算公式如下：

ut+1=utp

(6)

在公式(6)中，ut表示在t时刻APP的搜索概率分布，即在t时刻准确搜到该APP的概率，ut+1表示在t+1时刻准确搜索到该APP的概率分布。这就是本文所说的PageRank算法的计算公式[14]。

2 算法缺陷分析

由于PageRank算法是线下计算每个APP的PR值，当用户通过搜索引擎查询关键字匹配获得的APP集合，再按照搜索结果的前后顺序依次推荐给用户，因此具有极快的响应速度，该特点在Google的网页排序中也得到了证明。

但由于传统的PageRank算法过多地依赖外部网页对自身的链接数量，因此将该算法应用到APP搜索引擎中会暴露出自身的一些缺陷。目前在市场上存在许多同类的APP，对于官方网站则会显示“官网”的字样，而对于多种同类APP，当用户使用APP搜索引擎通过某关键字搜索某款APP时，搜索结果会显示所有同类APP。关于文本相似度计算的研究有许多，如李茹等[15]研究了基于框架语义分析的汉语句子相似度计算；张玉娟等[16]对《知网》的句子相似度计算进行了研究；斯坦福大学Taher Haveliwalat等[17]提出了关于主题敏感性的PageRank算法。本文在原有PageRank算法基础上，提出一种扩大同类APP相似度的改进算法，最后对计算所得最大TPR值的APP标出“权威”字样，并且在搜索引擎显示区域只显示PR值达到某个值的APP，并非所有APP。这样能够扩大同类APP在搜索引擎中相似度的差距，并能帮助用户快速地在APP搜索引擎的搜索结果中选中合适的APP产品。

3 算法改进

3.1 基本思路

通过式(1)计算所得APP的PR值并不能完全代表APP的相似度，当然也不能快速地帮助用户查找到最合适的APP。为了解决这个问题，本文认为在通过APP的下载量来计算该APP的PR值时，应该综合考虑其他因素。比如用户安装APP的保存时间，用户在安装了某个APP后在PC端保存的时间越长，表明该APP越受到用户的欢迎，APP的评分也应越高，在搜索系统中的排名也应越靠前。在PageRank算法中引入APP保存时间因子，使用户保存时间越短的APP逐渐悬沉下去，保存时间长的APP能快速浮上来。但是由于目前无法获取第三方推荐系统中用户APP的下载时间和卸载时间，所以也就无法计算用户APP的实际使用时间。为此本文采用在第三方推荐系统搜索引擎关键字的搜索周期来表示用户使用APP的时间。本文假设用户从卸载某款APP到通过推荐系统再次搜索并安装该APP的时间比用户实际使用该APP时间长。当用户通过推荐的关键字匹配方法搜索所需的APP产品时所搜索到的APP数量比实际该类APP产品的数量少。并假设二者对计算APP的TPR值带来的误差相互抵消。

APP的保存时间因子Wt表示如下：

Wt=m/T

(7)

其中，Wt为APP的保持时间因子，T为一个APP再次被搜索引擎搜索到的周期，m为常数，它的大小受式(1)中d的影响，它是一个实验数据，APP的保存时间因子Wt反比于搜索引擎的搜索周期T。

3.2 算法改进

在本次改进的Time-PageRank算法中，将加入保存时间因子，公式(1)修正为：

(8)

本次改进的Time-PageRank算法描述：通过搜索引擎搜索APP，获得APP模型图的邻接矩阵A和搜索引擎访问周期T。可以自由调整访问周期T的值，用于表示APP保存时间长短。最终通过计算得出每个APP的TPR值。

改进算法的步骤：

1)按照多种类型APP的相似关系获取APP模型子图。

2)获得每个搜索引擎的搜索周期T。

3)通过式(7)计算保存时间因子Wt。

4)通过式(8)计算每个APP的TPR值。

5)连续迭代，直到收敛。

首先计算每个APP的TPR值，最后通过PRn+1=APRn不断迭代TPR值，当满足下面关系时迭代结束，即TPR值收敛(A为邻接矩阵，ε为任意大于0的数)：

|PRn+1-PRn|<ε

6)通过步骤5中连续迭代，待TPR值收敛后输出迭代次数和TPR值排名。

4 结果验证

图1(见1.2节)是用于仿真的APP模型子图，为了便于分析，假设该图能够完全描述现在同类APP间的相似关系。

如图2所示，系列1为保存时间因子Wt=(1,1,1,1,1,1)，模拟传统的PageRank算法；系列2为保存时间因子Wt=(1,1,1,0.1,1,1)改进的Time-PageRank算法。

图2 传统PageRank算法与改进的Time-PageRank算法实验结果对比图

由于系列2的保存时间因子Wt在APP 4处为0.1，图中明显看出在APP编号4处系列2的TPR值明显低于系列1处的PR值。认为在加入保存时间因子的PageRank算法中APP的独立性增加，即该APP的相似度降低，扩大了该APP与其他同类APP的相似度差距。该APP在与其他同类APP能同时被搜到的概率降低，符合之前改进算法的设想。

如图3所示，系列1中m=1，系列2中m=0.15，系列3中m=0.015(m为公式(7)中的常数)，系列4中m=0.15/N(N为同类APP总数)。由图看出m的取值对PR值的整体排名顺序无影响，但影响计算过程中迭代收敛的快慢。

5 结束语

本文将原有PageRank算法应用在APP搜索系统中，并提出一种扩大同类APP相似度的Time-PageRank算法，最后对计算所得最大TPR值的APP标出“权威”字样，并且在搜索引擎显示区域只显示TPR值达到某个值的APP产品。极大地方便了用户在众多同类APP中找到适合的APP。

本文设计改进算法能在一定范围内降低APP的TPR值(即相似度)，从而达到提高APP搜索独立性，扩大与其他同类APP的相似度，最终达到提高搜索引擎的搜索效率，降低搜索错误率的目的。本文通过在传统的PageRank算法中加入时间保存因子，实现了对原有PR值的降低，达到了预期的实验效果。

本次改进算法的不足之处在于认为用户卸载APP和下次搜索该APP的时间差与采用关键字匹配APP计算TPR值带来的误差相互抵消，二者对于实际计算TPR值带来的误差是否相等有待于进一步研究；多种类型APP中是否所有APP都满足文中提出的相似关系模型有待于进一步研究。