CN105404666A - 一种序列化信息推荐方法 - Google Patents

Abstract

本发明涉及信息推荐领域，提供一种序列化信息推荐的方法，包括如下步骤：（1）生成序列元素特征点；（2）以历史数据作为样本集，生成序列元素特征点利用概率，作为推荐序列的评价基础指标；（3）生成序列信息，（4）计算序列活动图中潜在的空载序列距离期望值，选择潜在空载距离期望值最小者作为最优推荐序列。本发明方法针对序列元素的特征设定权重，根据序列特征约束进行个性化推荐，解决序列化信息推荐精度不高和效率低下等技术问题。

Description

一种序列化信息推荐方法

技术领域

本发明涉及信息推荐领域，特别涉及一种序列化信息推荐的方法及其优化方法，支持具有序列化特征的信息推荐。

背景技术

随着信息社会化、社会信息化，信息生产与消费促进了信息产业和信息技术的飞速发展，互联网已经成为人们获取信息的重要来源。然而互联网规模和信息资源的迅猛增长带来了信息过载的问题，人们面临“信息虽然丰富，但有用信息获取困难”的窘境，在此基础上进行数据分析、处理和筛选，并向用户进行实用的，个性化的推荐已成为新的应用方向。

许多信息都是通过特征点方式，以线性序列化的方式呈现的。特征点是指序列中具有某种特定功能，满足某种特定条件或者具备某种特殊属性且可向用户推荐的序列的组成元素，例如用户浏览商品信息的历史记录序列，在校生的学习轨迹序列，出租车行驶的位置序列等。根据特征点，分析和挖掘待推荐的序列化信息所独有的特性，例如偏好、频率、距离、位置等信息，能够使个性化推荐的准确度得到较大的提升。例如，在基于位置的个性化推荐服务（LBS，LocationBasedServices）中，由于用户的行进路线具有序列化的特征，因此可通过用户所在位置信息和用户的行进路线特征来判断该用户是否会有某一种行为出现（如有购物、娱乐或餐饮等行为），此等应用均建立在对序列化模式的深层理解之上。有很多应用可以抽象成序列化模式下的推荐问题，如用户的购物喜好推荐，学生的学习过程推荐，出租车线路推荐等。

序列化信息推荐将传统对点的推荐扩展到一个序列的推荐上，但由于这种类型的推荐受到时间、空间、频率、偏好等各种特征的约束，因此可归结为带有约束的最优或近似最优的序列化信息推荐问题，现有技术存在的主要缺点有：第一，没有利用历史数据去寻找潜在的特征点（例如学习分析中潜在的影响学习效果的行为，出租车线路推荐中的潜在载客点）以及没有评估这些特征点的利用概率（例如学习计划推荐中学生较为关注的知识点出现的概率，出租车线路推荐中的载客概率等）；第二，现有寻找推荐序列的方法没有进行优化。上述两点造成了现有推荐技术中精度不高，效率低下的问题。

发明内容

本发明的目的在于针对上述问题与不足，提供一种序列化信息推荐及其优化的方法，针对序列元素的特征设定权重，根据序列特征约束进行个性化推荐，解决序列化信息推荐精度不高和效率低下等技术问题。

为达到上述目的，本发明采用如下的技术方案。

一种序列化信息推荐方法，包括以下步骤：

（1）生成序列元素特征点；根据历史数据使用聚类方法，如K-means或K近邻等得到N个簇，选取每个簇的几何中心作为潜在的特征点集合；生成一个潜在的特征点集合C，用点表示特征点，C中包含n个潜在特征点c_i，集合C中的元素为所有特征点{c₁,c₂,c₃,c₄,……,c_n}；相比盲目的选取一些点作为潜在特征点，通过聚类的方法得到的点可以大幅度提高特征点的准确性，减少了点的数量，能较大幅度提高精度和缩减计算规模；

（2）以历史数据作为样本集，生成序列元素特征点利用概率，作为推荐序列的评价基础指标；特征点的利用概率计算方法为：首先对聚类结果进行分析，获得每个类簇的区域点覆盖，然后根据覆盖中包含的点，统计该区域所包含的点的利用频数记为Q，设置所有区域中所包含点的可能的利用总频数为归一化参数T，则该区域所对应簇的利用概率为Q/T，例如在出租车路径推荐问题中，Q可看作是在某一区域里被出租的车辆数量，T可设定为租车公司的车辆总数；在学习分析问题中，Q可看作是某一聚类中学生较为关注例如关注频次超过某一阈值的知识点的数量，T则为知识点总数，对于每一个潜在特征点，把该特征点所代表的簇的利用概率近似作为该点的利用概率；根据样本分析，赋予每个特征点一个不同的利用概率p_i，用浮点数表示利用概率，得到一个概率集合P，P中元素p_i的值为0到1之间的一个随机小数，即P中的元素为{p₁,p_2,p_3,……，p_n},0≤p_i≤1（1≤i≤n）；

（3）生成序列信息，即序列活动图；序列活动图定义为三元组：（C,P,E），其中C表示特征点集合，P表示每个特征点对应的利用概率集合，E表示边集，E中包含m条边e_i，即两个特征点之间的序列，E中的元素为{e₁,e₂,e₃,……，e_m}，E中元素e_i定义为（c_a,c_b,d_i），其中c_a,c_b（1≤a,b≤n）为表示起点和终点的两个特征点，d_i为边的长度，即权重，首先生成边即相邻特征点之间所组成的连线的长度，边的长度由待解决问题所关注的焦点结合实际情况来决定，例如租车路径推荐问题中，边的长度可定义为特征点所代表地理位置之间的物理距离，然后结合步骤（1）、（2）所获得的特征点集和概率集构成序列活动图；

根据序列活动图，可以生成序列；生成序列集合R，R中包含k条完整的序列r_i，用点的集合形式表示，即R中的元素为{r₁,r₂,r₃,……，r_k}，R中元素r_i的长度设为r_c，r_i实际形式为（c_a,c_b……c_rc）,c_a,c_b……c_rc（1≤a,b，rc≤n）为序列中的紧邻的点，c_a为起始点，c_rc为结束点，为了控制序列长度r_c，r_c取1到n的开平方之间的一个随机整数，即1≤rc≤sqrt（n）；

（4）计算序列活动图中潜在的空载序列距离期望值，结合活动点如出租车路径推荐问题中的出租车位置的当前位置选择并推荐最优序列，如出租车路径推荐问题中的出租车行驶线路等；空载序列指，若某一特征点没有得到利用，例如出租车在该点没有接到顾客，客户没有购买某件商品，学生没有学习某个知识点等，那么该点被认为是无价值的，由若干无价值的点构成的序列，称为空载序列；最优序列的选择方法基于潜在的空载序列距离期望值，空载序列距离期望值计算方法如下：假设点A到点B之间有一条长度为dist的序列，A为活动点位置，点B的利用概率为P_b，若在B点可以得以应用，那么由A到B构成的序列可看作是有价值的，反之，若B点没有得到利用，则需要前往下一个潜在特征点，那么由A到B构成的序列是无用的，假设较坏的情况，即前往的下一个潜在特征点是无用的，将这段序列的消耗记为CostA，计算方式如下：

即这段序列的消耗等于两点之间的长度乘以B点不利用的概率，对于点B的选取，根据A得到与之最近的k个点作为待判定点，对其预估的消耗为对应的CostA的值，选取其中CostA值最小者向后构造后继序列，依此类推，建立一个消耗值为L的有向序列，作为所求的推荐序列候选；将集合C中N个特征点依次作为活动点起始位置来生成M条消耗为L的推荐序列候选集合，计算每一条序列的潜在空载距离期望值，并在此基础上选择潜在空载距离期望值最小者作为最优推荐序列。

在上述技术方案中，对所述的空载序列距离期望值计算方法进行优化，具体过程如下：

对于当前位置PoCab，有k条完整的序列，分别为r₁,r₂,r₃,……，r_k，每条序列记为（c_1,a,c_1，b……c_1，rc），（c_2,a,c_2，b……c_2，rc），（c_3,a,c_3，b……c_3，rc），……，（c_k,a,c_k，b……c_k，rc），首先计算序列PoCab→c_1,a→c_1，b→……→c_1，rc的空载序列期望，并存放为最小值变量min中；然后再依次计算其他序列，若计算得到的其他序列的空载序列期望小于当前min值时，将此值存入当前min变量中，如此不断迭代，当出现在计算某一序列的过程中，其中间结果值超过min值时，便不再继续计算，舍弃此序列进行剪枝。

本发明方法与现有技术相比具有以下优点：第一，在历史数据中找到潜在特征点，并对这些特征点的利用概率进行评价，用于推荐特征点序列的生成，以提高推荐精度；第二，根据筛选后的特征点结合优化最优序列推荐的方法，以提高推荐效率。

具体实施方式

下面结合具体实施例对本发明作进一步的描述。

本实施例提供一种序列化信息推荐方法，具体实施步骤如下：

第一步，生成推荐序列

假设n为潜在特征点的数目，m为构成活动图中的序列即活动图中的边的数目，k为活动点遍历序列的数目。

具体步骤如下：

第一，生成特征点信息。生成一个潜在特征点集合C，用点表示特征点，C中包含n个潜在特征点c_i。集合C中的元素为所有特征点{c₁,c₂,c₃,c₄,……,c_n}。

第二，生成特征点的利用概率信息。根据样本获得每个特征点的利用概率p_i，用浮点数表示利用概率，得到一个概率集合P，P中元素p_i的值为0到1之间的一个随机小数。即P中的元素为{p₁,p₂,p₃,……，p_n},0≤p_i≤1（1≤i≤n）。

第三，生成序列信息即序列活动图。根据特征点生成序列集合E，E中包含m条边e_i，即两个特征点之间的序列，边的长度即权重为d_i。即E中的元素为{e₁,e₂,e₃,……，e_m}。E中元素e_i的实际形式为（c_a,c_b,d_i）,c_a,c_b（1≤a,b≤n）分别为边的起始点和结束点，d_i为边的长度。

根据以上数据，可以生成活动点遍历轨迹所得到的序列。生成序列集合R，R中包含k条完整的序列r_i，即活动点的序列，用点的集合形式表示。即R中的元素为{r₁,r₂,r₃,……，r_k}。R中元素r_i的长度(权重)设为r_c，r_i实际形式为（c_a,c_b……c_rc）,c_a,c_b……c_rc（1≤a,b，rc≤n）为序列中的紧邻的点，c_a为起始点，c_rc为结束点。为了控制序列长度(权重)r_c，r_c取1到n的开平方之间的一个随机整数，即1≤r_c≤sqrt（n）。

第二步，选择最优序列

计算每一条序列的潜在空载距离期望值，并在此基础上选择潜在空载距离期望值最小者作为最优推荐序列。具体算法如下。

算法1：给出一条序列，计算从序列中给定位置开始到序列结束点的空载距离期望值。

输入：一条需要计算的序列，为一条有序的点集，其中每个点有一个特征点的利用概率属性；给定开始位置在序列中的序号；

输出：空载距离期望值

calF(route,PoCab)//输入序列和序列中给定位置开始计算空载距离期望值

result=0//初始化空载序列望值

dtmp=PoCab//初始化当前距离

ptmp=1.0//初始化起点概率

ptmp2=0//初始化当前点的概率

for(pointinroute)//遍历整个序列

ptmp2=ptmp*point.Probability//计算当前点的概率

result=result+ptmp2*dtmp//计算当前点的空载距离期望值

dtmp=dtmp+route.nextPointDistance//计算下个点的距离

ptmp=ptmp*(1–point.Probability)//计算下个点的概率

ptmp2=ptmp*lastPoint.Probability()//计算最后一个点利用的概率

result=result+ptmp2*dtmp//计算当前空载距离期望值

ptmp2=ptmp*(1–lastPoint.Probability)//计算最后一个点不利用的概率

result=result+ptmp2*(dtmp+dinf)//计算最终空载距离期望值

returnresult//返回空载距离期望值

算法2：在序列集合中选择最优序列，即该序列的空载距离期望值最小。

输入：潜在特征点集合、推荐序列集合、特征点的利用概率集合

输出：最优序列

minF()//选择最优序列

Initsetpoints//初始化潜在特征点集合

Initsetroutes//初始化推荐序列集合

MinResult=MAX_VALUE//初始化为最大值

BestRoute=null//初始化最优序列

Foreach(routeinroutes)//遍历所有推荐序列

result=calF(route,PoCab)//对于每一条推荐序列计算空载距离期望值

ifresult<MinResult//找到最小空载距离期望值

MinResult=result//最小值为当前空载距离期望值

BestResult=route//最优序列为当前序列

returnBestResult//返回最优序列

第三步，方法优化

在算法1、算法2的基础上进行优化，优化过程如下。

算法3：给出一条序列，计算从序列中给定位置开始的空载距离期望值。

输入：一条需要计算的序列，为一条有序的点集，其中每个点有一个特征点的利用概率属性；给定开始位置在序列中的序号；

输出：序列的空载距离期望值

calF(route,PoCab,MinResult)//输入序列和序列中给定位置开始计算空载距离期望值

result=0//初始化空载序列的期望值

dtmp=PoCab//初始化当前距离

ptmp=1.0//初始化起点概率

ptmp2=0//初始化当前点的概率

foreach(pointinroute)//遍历整个序列

ptmp2=ptmp*point.Probability//计算当前点的概率

result=result+ptmp2*dtmp//计算当前点的空载距离期望值

ifresult>MinResult//如果当前空载距离期望值大于当前最小距离

returnMAX_VALUE//返回最大距离

dtmp=dtmp+route.nextPointDistance//计算下个点的距离

ptmp=ptmp*(1–point.Probability)//计算下个点的概率

ptmp2=ptmp*lastPoint.Probability()//计算最后一个点利用的概率

result=result+ptmp2*dtmp//计算当前空载距离期望值

ptmp2=ptmp*(1–lastPoint.Probability)//计算最后一个点不利用的概率

result=result+ptmp2*(dtmp+dinf)//计算最终空载距离期望值

returnresult//返回空载距离期望值

算法4：在序列集合中选择最优序列，即该序列空载距离期望值最小。

输入：潜在特征点集合、推荐序列集合、特征点的利用概率集合

输出：最优序列

minF()//选择最优序列

Initsetpoints//初始化潜在特征点集合

Initsetroutes//初始化推荐序列集合

MinResult=MAX_VALUE//初始化为最大值

BestRoute=null//初始化最优序列

foreach(routeinroutes)//遍历所有推荐序列

result=calF(route,PoCab,MinResult)//对于每一条推荐序列计算空载距离期望值

ifresult<MinResult//找到最小的空载距离期望值

MinResult=result//最小值为当前空载距离期望值

BestResult=route//最优序列为当前序列

returnBestResult//返回最优序列

本发明的实验效果描述：

使用随机生成的无向图模拟待解决问题，图中包含10000个点，100000条边，随机生成5000条序列。假设边的长度(权重)都为1，节点的利用概率采用随机方法自动生成。

设定的实验效果判定准则是：使用本方法并作优化后，若每次向活动点使用者进行序列推荐的平均时间低于0.1秒，则本方法包括优化方法满足“用户体验好”这一指标。

首先，根据算法1和算法2进行最优序列选择，在所进行的1000次推荐用时51.23s；使用优化后的方法进行最优序列选择，所进行1000次推荐用时10.22s。使用优化后的方法进行最佳序列选择，每次推荐平均用时为0.00151562s。

由上可知，本发明方法并优化后将每次推荐时间控制在了可以接受的范围（0.1s）之内，满足较好的用户体验指标，解决了序列化信息推荐问题效率低下这一技术问题。

结论分析：

第一，本发明的方法及其优化方法，其效率优势主要体现在：（1）从潜在特征点集合中得出空载序列生成活动点序列，并依此构造活动点活动图；（2）结合活动点当前所在位置，通过对计算空载距离期望值过程的优化，减少了计算次数。

第二，对于算法2的时间复杂度分析：设生成序列集合中包含M个元素，每个元素为一个序列。其中最长（权重之和最大）的序列包含S个潜在特征点。假设在计算序列的空载距离期望值的过程中，每次迭代计算点的代价为1，那么minF函数的时间复杂度为。calF遍历集合M中所有元素，所以calF的时间复杂度为。

第三，对于算法3和算法4的综合分析：采用剪枝优化分析，算法3和4在算法1和2的基础上设定了一个目标，使得之后每次计算逐渐向最优目标逼近，这样可以在计算过程中将很多无效序列排除，在算法1和2的基础上降低了计算次数，提高了计算效率。

第四，本方法中优化方法的有效性可用构造法加以证明：即在本发明中的方法计算某一个序列r_p时，在计算PoCab→c_p,a→c_p，b→……→c_p，rc的空载序列期望的过程中，当计算到c_p，q时，得到空载序列期望值大于min值时，舍去此结果，不再继续计算这个序列，开始下一个序列的计算，此序列省去的计算次数为（r_c-q），若此序列一直计算完毕得到的结果仍比min值小，则此序列省去的计算次数为（r_c-r_c），即0次。若从第二条序列开始，每个序列分别计算到q₁，q₂,……，q_k-1（q₁，q₂,……，q_k-1均小于等于r_c）点时计算终止,则本发明方法总共减少次数为(r_c-q₁+r_c-q₂+……+r_c-q_k-1)。

Claims (2)

1.一种序列化信息推荐方法，其特征在于该方法包括以下步骤：

（1）生成序列元素特征点；根据历史数据使用聚类方法得到N个簇，选取每个簇的几何中心作为潜在的特征点集合；生成一个潜在的特征点集合C，用点表示特征点，C中包含n个潜在特征点c_i，集合C中的元素为所有特征点{c₁,c₂,c₃,c₄,……,c_n}；

（2）以历史数据作为样本集，生成序列元素特征点利用概率，作为推荐序列的评价基础指标；特征点的利用概率计算方法为：首先对聚类结果进行分析，获得每个类簇的区域点覆盖，然后根据覆盖中包含的点，统计该区域所包含的点的利用频数记为Q，设置所有区域中所包含点的可能的利用总频数为归一化参数T，则该区域所对应簇的利用概率为Q/T，对于每一个潜在特征点，把该特征点所代表的簇的利用概率近似作为该点的利用概率；根据样本分析，赋予每个特征点一个不同的利用概率p_i，用浮点数表示利用概率，得到一个概率集合P，P中元素p_i的值为0到1之间的一个随机小数，即P中的元素为{p₁,p_2,p_3,……，p_n},0≤p_i≤1（1≤i≤n）；

（3）生成序列信息，即序列活动图；序列活动图定义为三元组：（C,P,E），其中C表示特征点集合，P表示每个特征点对应的利用概率集合，E表示边集，E中包含m条边e_i，即两个特征点之间的序列，E中元素e_i定义为（c_a,c_b,d_i），其中c_a,c_b（1≤a,b≤n）为表示起点和终点的两个特征点，d_i为边的长度，首先生成边的长度，边的长度由待解决问题所关注的焦点结合实际情况来决定，然后结合步骤（1）、（2）所获得的特征点集和概率集构成序列活动图；

根据序列活动图生成序列；生成序列集合R，R中包含k条完整的序列r_i，用点的集合形式表示，即R中的元素为{r₁,r₂,r₃,……，r_k}，R中元素r_i的长度设为r_c，r_i实际形式为（c_a,c_b……c_rc）,c_a,c_b……c_rc（1≤a,b，rc≤n）为序列中的紧邻的点，c_a为起始点，c_rc为结束点，为了控制序列长度r_c，r_c取1到n的开平方之间的一个随机整数，即1≤rc≤sqrt（n）；

（4）计算序列活动图中潜在的空载序列距离期望值，结合活动点的当前位置选择并推荐最优序列；最优序列的选择方法基于潜在的空载序列距离期望值，空载序列距离期望值计算方法如下：假设点A到点B之间有一条长度为dist的序列，A为活动点位置，点B的利用概率为P_b，若在B点可以得以应用，那么由A到B构成的序列可看作是有价值的，反之，若B点没有得到利用，则需要前往下一个潜在特征点，那么由A到B构成的序列是无用的，假设较坏的情况，即前往的下一个潜在特征点是无用的，将这段序列的消耗记为CostA，计算方式如下：

即这段序列的消耗等于两点之间的长度乘以B点不利用的概率，对于点B的选取，根据A得到与之最近的k个点作为待判定点，对其预估的消耗为对应的CostA的值，选取其中CostA值最小者向后构造后继序列，依此类推，建立一个消耗值为L的有向序列，作为所求的推荐序列候选；将集合C中N个特征点依次作为活动点起始位置来生成M条消耗为L的推荐序列候选集合，计算每一条序列的潜在空载距离期望值，并在此基础上选择潜在空载距离期望值最小者作为推荐序列。

2.根据权利要求1所述的序列化信息推荐方法，其特征在于步骤（4）中所述的空载序列距离期望值计算方法的优化方法，具体过程如下：

对于当前位置PoCab，有k条完整的序列，分别为r₁,r₂,r₃,……，r_k，每条序列记为（c_1,a,c_1，b……c_1，rc），（c_2,a,c_2，b……c_2，rc），（c_3,a,c_3，b……c_3，rc），……，（c_k,a,c_k，b……c_k，rc），首先计算序列PoCab→c_1,a→c_1，b→……→c_1，rc的空载序列期望，并存放为最小值变量min中；然后再依次计算其他序列，若计算得到的其他序列的空载序列期望小于当前min值时，将此值存入当前min变量中，如此不断迭代，当出现在计算某一序列的过程中，其中间结果值超过min值时，便不再继续计算，舍弃此序列进行剪枝。