一种基于聚类的移动应用下载量预测方法

摘要

本发明提供一种基于聚类的移动应用下载量预测方法，包括：1)从后台数据中收集所有已知的app的历史数据，2)源数据处理，3)模式聚类，下载量预测。本发明创新性地进行app下载量预测，在app领域需求明显，并且具有良好拓展性，在其他电商领域具有十分广泛的应用前景，并且，本发明在考虑app下载曲线特性的基础上修改K-means算法，并优化求解效率。整个聚类过程可以在线下完成，而下载量的预测值计算在线上完成，优化了用户体验。

说明书

技术领域

本发明属于移动互联网应用领域。主要利用了余弦相似度与K中心聚类方 法，实现了一种针对移动应用(app)下载量的预测机制。

背景技术

随着移动互联网大潮的到来，近年来移动应用(app)蓬勃发展，以谷歌市 场为例(Google Play)目前其app数目已超过100万，而累计下载量则超过500 亿。不论android还是ios的app应用市场，其网页或者应用端的展示页面都十 分有限制，而大部分的app得不到有效的展示。工业界将传统电商中的推荐机制 逐渐引入到app领域，以此作为用户发现感兴趣优质app的一种途径，同时也是 一部分欠热门优质app曝光的有效途径。但目前没有一种对潜在的优质app的发 掘方法。

发明内容

本发明所要解决的技术问题是提供一种基于聚类的移动应用下载量预测方 法，能够根据app的已知下载量对其后一段时间的总下载量进行预测。

本发明解决技术问题所采用的技术方案是：一种基于聚类的移动应用下载量 预测方法，包括以下步骤：

1)从后台数据中收集所有已知的app的历史数据。

2)源数据处理，对步骤1)中的数据进行处理，生成长度为L的离散时间 序列x以表示每一个app的下载曲线，至此所有app的下载曲线组成一个离散时 间序列训练数据集；

3)模式聚类，将步骤2)中生成的离散时间序列数据集进行聚类，得到k 个下载模式；

4)下载量预测，给定一个app在m天内的下载曲线，与k个下载模式进行 匹配，计算之后(L-m)天的总下载量，得到预测结果。

在采用上述技术方案的同时，本发明还可以采用或者组合采用以下进一步的 技术方案：

所述步骤2)具体包括以下步骤：

(1)给定下载阈值thr；thr为人为指定的参数，默认thr＝0.1.在thr确定的 基础上可以计算得到整个训练数据集的L₁和L₂，一般调节thr使得L₁+L₂不小于 原序列长度的2/3。

(2)为离散时间序列数据集中的每一条离散时间序列x，计算相应的L₁(x) 和L₂(x)，其中L₁(x)表示从L_p开始往左数日下载量第一次下降到thr*v_p所用的天 数，相应的，L₂(x)用表示从L_p开始往右数日下载量第一次下降到thr*v_p所用的 天数；L_p为序列中指定的一天，v_p为下载量的峰值。

(3)计算所有训练数据集中L₁(x)和L₂(x)的平均值L₁和L₂。加：截取每条 离散序列峰值所在日前L₁天和后L₂天的下载数据，左边截取天数不足L₁时，用右 侧数据填充。相应的，用左侧数据填补右侧数据的不足。以确保所有序列的长度 均为L(L＝L₁+L₂)。至此，源数据被处理为长度均为L的离散时间序列。

所述步骤3)具体包括以下步骤：

(1)设定训练数据集中模式聚类的个数k；k为人工指定的参数，默认k＝6， 其具体值根据聚类效果进行调整。

(2)从训练数据集中随机指定k条曲线为k个聚类的中心，计算每个非中 心离散时间序列x到k个中心的曲线距离d(x,c)；

d(x,c)表示x与某一个聚类中心的距离，c专门指代聚类中心(center)，根 据d(x,c)将该离散序列划分到离它最近的聚类中心所在的类。

(3)更新聚类中心k，每次聚类中心更新的目标变为最小化F；

在给定的类划分下，聚类更新的目标为最小化类中每一条离散时间序列到类 中心的距离平方的和。

$F=\underset{k=1}{\overset{K}{\Sigma }}\underset{x_i\in C_k}{\Sigma }d{(x_i,{\mu }_k)}^2---\left(1\right)$

其中μ_k，C_k分别为第k个类的中心以及归属于第k类的曲线。

根据公式(1)可以导出每次第k类更新的值：

${\mu }_k^{*}=\underset{\mu }{\arg \min }\underset{x_i\in C_k}{\Sigma }d{(x_i,\mu )}^2---\left(2\right)$

其中为更新之后第k类中心的值。

$\left(4\right)\alpha =\frac{x_i^T\mu }{{\left|\right|\mathrm{xi}\left|\right|}^2}$

α是另一根离散序列纵坐标的缩放系数。

${\mu }_k^{*}=\underset{\mu }{\arg \min }\frac{1}{{\left|\right|\mu \left|\right|}^2}\underset{x_i\in C_k}{\Sigma }{\left|\right|(\frac{x_i{x}_i^T}{{\left|\right|\mathrm{xi}\left|\right|}^2}-I)\mu \left|\right|}^2---\left(3\right)$

进一步由公式3可以先后导出公式4：

${\mu }_k^{*}=\underset{\mu }{\arg \min }\frac{1}{{\left|\right|\mu \left|\right|}^2}{\mu }^T\underset{x_i\in C_k}{\Sigma }(I-\frac{x_i{x}_i^T}{{\left|\right|\mathrm{xi}\left|\right|}^2})\mu ---\left(4\right)$

令$M=\underset{x_i\in C_k}{\Sigma }(I-\frac{x_i{x}_i^T}{{\left|\right|x_i\left|\right|}^2}),$可以得到最终的计算方式：

${\mu }_k^{*}=\underset{\mu }{\arg \min }\frac{{\mu }^T\mathrm{M\mu }}{{\left|\right|\mu \left|\right|}^2}$

因此，就是矩阵M最小特征值对应的特征向量。

其中，T表示对矩阵进行转置，C_k表示当前划分中归属于第k类的曲线集合。 x_i表示离散序列x中的第i项，M的值只于x_i相关，没有特定的物理意义，I是 一个常数，对应x中的第i项，u表示各类中心形成的矩阵。

用求特征向量的方式进行聚类中心的更新使得算法的实现更加简单，同时也 有效的降低了求解的复杂度。

所述步骤4)具体包括以下步骤：

(1)给定一个app，其前m天的下载曲线是长度为m的离散时间序列test， 计算test和每个中心(聚类中心本身就是一条长度为L的离散序列)前m天构 成的离散序列的余弦相似度，选择最相似的类中心c；

(2)该其后的L-m天的下载量总和pred预测如下：

$\mathrm{pred}=\frac{{\Sigma }_{j=1}^m{\mathrm{test}}_j}{{\Sigma }_{j=1}^m{c}_j}*{\Sigma }_{j=1+m}^L{c}_j,$

其中，c表示选定的最相似的类中心，那么cj表示离散序列c的第j项。

本发明的有益效果是：本发明创新性地进行app下载量预测，在app领域需 求明显，并且具有良好拓展性，在其他电商领域具有十分广泛的应用前景，并且， 本发明在考虑app下载曲线特性的基础上修改K-means算法，并优化求解效率。 整个聚类过程可以在线下完成，而下载量的预测值计算在线上完成，优化了用户 体验。本发明通过预测app刚上架的数据预测其在之后一段时间的总下载量，从 app开发者和相关利益方的角度来考虑，如果能从刚上架的app中发现有成为热 门潜质的优质app，并针对性地进行展示和营销，无疑能带来更好的收益，此外， 该方法也同样适用于其他电子商务领域，具有良好的拓展性。

附图说明

图1为本发明的整体架构图。

图2为本发明的模块聚类的过程示意图。

具体实施方式

参照附图。

本发明的下载量预测方法包括以下步骤：

1)从后台数据获得待预测app的历史数据，包括该app在已知的m天内的 下载量；

2)源数据处理，对步骤1)中的数据进行处理，生成长度为L的离散时间 序列x以表示每一个app的下载曲线，至此所有app的下载曲线组成一个离散时 间序列训练数据集，具体包括以下步骤：

所述步骤2)具体包括以下步骤：

(1)给定下载阈值thr；thr为人为指定的参数，默认thr＝0.1.在thr确定的 基础上可以计算得到整个训练数据集的L₁和L₂，一般调节thr使得L₁+L₂不小于 原序列长度的2/3。

(2)为离散时间序列数据集中的每一条离散时间序列x，计算相应的L₁(x) 和L₂(x)，其中L₁(x)表示从L_p开始往左数日下载量第一次下降到thr*v_p所用的天 数，相应的，L₂(x)用表示从L_p开始往右数日下载量第一次下降到thr*v_p所用的 天数；L_p为序列中指定的一天，v_p为下载量的峰值。

(3)计算所有训练数据集中L₁(x)和L₂(x)的平均值L₂和L₂。加：截取每条 离散序列峰值所在日前L₁天和后L₂天的下载数据，左边截取天数不足L₁时，用右 侧数据填充。相应的，用左侧数据填补右侧数据的不足。以确保所有序列的长度 均为L(L＝L₁+L₂)。至此，源数据被处理为长度均为L的离散时间序列。

3)模式聚类，将步骤2)中生成的离散时间序列数据集进行聚类，得到k 个下载模式，具体包括以下步骤：

(1)设定训练数据集中模式聚类的个数k；k为人工指定的参数，默认k＝6， 其具体值根据聚类效果进行调整。

(2)从训练数据集中随机指定k条曲线为k个聚类的中心，计算每个非中 心离散时间序列x到k个中心的曲线距离d(x,c)；

d(x,c)表示x与某一个聚类中心的距离，c专门指代聚类中心(center)，根 据d(x,c)将该离散序列划分到离它最近的聚类中心所在的类。

(3)更新聚类中心k，每次聚类中心更新的目标变为最小化F；

在给定的类划分下，聚类更新的目标为最小化类中每一条离散时间序列到类 中心的距离平方的和。

$F=\underset{k=1}{\overset{K}{\Sigma }}\underset{x_i\in C_k}{\Sigma }d{(x_i,{\mu }_k)}^2---\left(1\right)$

其中μ_k，C_k分别为第k个类的中心以及归属于第k类的曲线。

根据公式(1)可以导出每次第k类更新的值：

${\mu }_k^{*}=\underset{\mu }{\arg \min }\underset{x_i\in C_k}{\Sigma }d{(x_i,\mu )}^2---\left(2\right)$

其中为更新之后第k类中心的值。

$\left(4\right)\alpha =\frac{x_i^T\mu }{{\left|\right|\mathrm{xi}\left|\right|}^2}$

α是另一根离散序列纵坐标的缩放系数。

${\mu }_k^{*}=\underset{\mu }{\arg \min }\frac{1}{{\left|\right|\mu \left|\right|}^2}\underset{x_i\in C_k}{\Sigma }{\left|\right|(\frac{x_i{x}_i^T}{{\left|\right|\mathrm{xi}\left|\right|}^2}-I)\mu \left|\right|}^2---\left(3\right)$

进一步由公式3可以先后导出公式4：

${\mu }_k^{*}=\underset{\mu }{\arg \min }\frac{1}{{\left|\right|\mu \left|\right|}^2}{\mu }^T\underset{x_i\in C_k}{\Sigma }(I-\frac{x_i{x}_i^T}{{\left|\right|\mathrm{xi}\left|\right|}^2})\mu ---\left(4\right)$

令$M=\underset{x_i\in C_k}{\Sigma }(I-\frac{x_i{x}_i^T}{{\left|\right|x_i\left|\right|}^2}),$可以得到最终的计算方式：

${\mu }_k^{*}=\underset{\mu }{\arg \min }\frac{{\mu }^T\mathrm{M\mu }}{{\left|\right|\mu \left|\right|}^2}$

因此，就是矩阵M最小特征值对应的特征向量。

其中，T表示对矩阵进行转置，C_k表示当前划分中归属于第k类的曲线集合。 x_i表示离散序列x中的第i项，M的值只于x_i相关，没有特定的物理意义，I是 一个常数，对应x中的第i项，u表示各类中心形成的矩阵。

模式聚类所用算法类似于k-means，每一次迭代分为两步。与k-means所用 欧式距离不同的是，此处使用定义中的曲线距离计算方式。

用求特征向量的方式进行聚类中心的更新使得算法的实现更加简单，同时也 有效的降低了求解的复杂度。

4)下载量预测，给定一个app在m天内的下载曲线，与k个下载模式进行 匹配，计算之后(L-m)天的总下载量，得到预测结果，具体包括以下步骤：

(1)给定一个app，其前m天的下载曲线是长度为m的离散时间序列test， 计算test和每个中心(聚类中心本身就是一条长度为L的离散序列)前m天构 成的离散序列的余弦相似度，选择最相似的类中心c；

(2)该其后的L-m天的下载量总和pred预测如下：

$\mathrm{pred}=\frac{{\Sigma }_{j=1}^m{\mathrm{test}}_j}{{\Sigma }_{j=1}^m{c}_j}*{\Sigma }_{j=1+m}^L{c}_j,$

其中，c表示选定的最相似的类中心，那么cj表示离散序列c的第j项。