组合推荐算法（精选八篇）
组合推荐算法 篇1
关键词：协同过滤,FP-Growth,组合算法
互联网时代的到来, 用户时常面对大量的数据信息, 然而却无法有效的从中获得对自己真正有用的那部分信息, 对信息的使用效率反而降低了, 这种现象就叫做信息超载。
其中, 最能解决信息超载问题的方法就是推荐系统。推荐系统根据用户的信息特征、兴趣、用户浏览和购买记录等, 预测用户可能感兴趣的产品, 然后将产品推荐给用户。使用户能够在大量的信息和产品数据中快速有效地找到自己感兴趣的产品。
对于各大电子商务的推荐网站来讲, 最为重要的是为用户推荐感兴趣的商品, 因此可以留住客户, 增加客户的忠诚度, 所以, 一个良好的推荐系统对于商家也是必须的。
1 推荐算法简介
1.1 协同过滤推荐算法
在推荐算法中, 协同过滤推荐是应用最为广泛的一种算法。它主要分为基于用户的协同过滤和基于项目的协同过滤两种。基于项目的推荐系统算法核心:搜索目标项目的最近邻居, 也就是计算目标项目与其他项目的相似度, 再利用用户对最近邻居项目的评分进行预测, 预测用户对目标推荐项目的评分, 产生前N个项目的推荐列表, 最后将推荐列表推荐给用户。
随着网站中用户数和商品数的日益增加, 协同过滤算法存在以下问题:
(1) 冷启动问题;
(2) 数据稀疏性;
(3) 可扩展性问题。
1.2 关联规则推荐算法
关联规则是数据挖掘领域的重要技术, 在推荐系统中, 就是应用数据挖掘技术从用户的浏览记录和购买历史等数据, 产生关联规则, 系统基于关联规则给出推荐。主要用于实现交叉销售, 帮助用户发现一些潜在的但是用户自己还没有发现的商品。
关联规则的算法主要有两种:Apriori算法和频繁项目增长模式 (FP_growth) 算法。
FP-Growth算法是一种基于频繁项集的关联规则算法。这种算法采用一种称为FP-Tree的特殊前缀索引树作为存储频繁项目集的数据结构, 在建树过程中不断将频繁项目压缩到这棵频繁树上, 这样可以大幅度的压缩频繁项目所占空间的大小。
FP-Growth算法主要通过两次扫描事务数据库, 第一次扫描用于构建头表, 第二次用于建立FP前缀树, 以此得到频繁项目集。然后, 为每个频繁项集构建它们的条件FP树, 最后, 对这些条件FP树进行递归的频繁项集挖掘。
2 推荐系统建模
推荐系统主要分为3部分:搜索用户行为信息记录模块, 根据这些信息数据分析用户喜好的分析模块, 以及推荐系统中最为核心也是决定推荐效果的推荐算法模块。
2.1 用户行为数据记录
用户的行为包括显性反馈行为和隐性反馈行为。其中, 显性反馈行为记录用户对商品相对明确的喜好行为, 例如评分、投票、转发等。面对网站给出的5分评分制, 用户比较喜欢用5分和1分, 其他的分数则很少有用户打。因为用户在浏览网站时, 有时并不喜欢对浏览的商品进行评分, 就会对商品进行模糊的评分, 就不能有效的反馈出用户对该商品的兴趣。隐性反馈行为数据弥补了显性评分行为的不足。用户浏览或者购买商品的行为就是一种隐性的行为。
对于推荐系统中的协同过滤算法和关联规则算法, 两种算法选取的数据源不太相同。其中, 基于协同过滤的推荐算法主要是根据用户的历史评分即显性行为反馈数据进行推荐, 而基于关联规则的推荐算法是挖掘用户的浏览记录和购买记录即隐性行为反馈数据, 产生关联规则, 然后进行推荐。
2.2 推荐的基本流程
首先经过数据的抽取、转换、清洗等一系列的操作, 从原本的业务数据中提取出用户属性信息、产品属性信息以及用户偏好信息, 建立用户模型和产品模型。然后利用单个推荐算法或者多种推荐算法组合成的推荐算法产生初始推荐集, 推荐集可以直接推荐给用户, 也可以经过排序或过滤后将Top-N个产品形成推荐列表推荐给用户。
2.3 组合算法推荐
在推荐系统中, 其算法都有一定的缺点, 会导致推荐的准确率降低。为了取其优点, 去其缺点, 推荐算法中经常使用组合算法来优化单一的推荐算法。对于组合算法, Robin了提出了加权、变换、混合、层叠等几种组合方法。
在本论文中, 为了优化协同过滤推荐算法带来的稀疏性和冷启动的问题, 将在协同过滤推荐算法中引入关联规则算法, 将两种算法进行组合, 其思路如下:用户对产品进行评分后, 更新用户的评分矩阵, 同时运用基于项目的协同过滤推荐算法, 计算各个项目之间的相似性, 根据项目之间的相似性和用户的评分历史行为为用户生成推荐列表。而对于用户没有产生评分但有购买历史的产品, 系统采用FP-Growth算法, 计算出项目频繁项, 产生关联规则, 然后为用户生成评推荐列表。
3 结束语
在本论文中针对单一的推荐系统的缺点, 提出了一种针对协同过滤和关联规则的组合推荐算法。但是随着互联网的快速发展, 推荐系统中数据源也是越来越庞大, 考虑到推荐结果的准确率, 可以在以后的工作中引入hadoop中的Map Reduce框架, 利用Map Reduce框架的分布式并行计算的能力, 对推荐系统中的数据进行高效的分析与计算, 使得推荐系统能够对用户进行更进一步的良好的推荐。
参考文献
[1]王国霞, 刘贺平.个性化推荐系统综述[J].计算机工程与应用, 2012 (07) :66-76.
[2]项亮.推荐系统实践[M].北京:人民邮电出版社, 2012 (06) .
[3]B Mobasher, HDai, TLuo.Discovery of Aggregate Usage Profiles for Web Personalization.In Proceedings of the Web Mining for E-Commerce Work shop (WebK DD’2000) , 2000, 7 (04) :584-595.
本月推荐基金组合 篇2
依据对市场与基金投资操作分析，对上期基金组合进行如下调整，并建立本期基金组合：
积极型组合：维持对易方达策略成长、中邮核心优选，嘉实主题精选等基金投资，将近期调整基金经理的上投摩根中国优势和进行拆分的泰信先行策略两只股票型基金替换为业绩持续优秀的汇添富优势和广发稳健两只混合型基金产品，降低基金组台的总体股票仓位水平以控制风险。
防御型组合：维持对鹏华普天收益、广发小盘成长、华安宏利、嘉实债券等基金投资，将进行大比例分红促销的大成蓝筹稳健基金替换为银华优质增长基金。
绝对收益组合：维持上期组合。
封闭式基金组合：维持对基金兴华、景阳和金盛等三只基金的投资，将已进行中期分红的基金裕隆替换为尚未分红且套利空间相对较大的基金鸿阳，将短期涨幅过快导致折价快速下降的基金隆元替换为剩余期限相对较短(2009年到期)，折价较高且尚未进行中期分红的基金天华。
上期基金组合表现分析
受益于股票市场大涨以及对市场结构(绩优蓝筹股行情)的把握，上期进攻型组合、防御型组合收益率分别达到23.78％和14.98％，战胜对应同业基准4.84％和2.57％。
绝对收益组合继续保持稳定，本期收益1.23％，高出对应基准0.92％。
粒子群算法求解组合投资问题 篇3
Markowitz在1952年发表的经典论文《组合证券选择》[1]标志着现代证券组合理论的开端。投资者总是希望找到一组投资,在风险一定的情况下,以最大的可能实现预期收益,所以提出了一种概率准则意义下的最优组合投资模型[2,3,4]。模型以实现预期收益的概率为目标函数在满足约束的条件下,选择投资比例,使目标函数达到最大。或者是在实现预期收益的情况下,承担最小的风险,投资者根据最小风险原则来确定投资比例。在以往的文献中,出现过用收益率矩阵和加权行和为指标迭代运算来求解最优投资组合,也有人提出了求解最优投资组合的树形算法、禁忌搜索算法、遗传算法等。本文提出了一种基于粒子群优化算法的组合投资求解方案。
粒子群优化算法是一种进化计算技术。算法首先初始化一组随机粒子(随机解),然后通过迭代找到最优解。迭代过程中,粒子在解空间追随最优粒子进行搜索[5]。
本文首先用传统方法求解正态性假设下概率准则的最优组合证券投资模型,其后根据粒子群优化算法给出了该模型的求解算法,并用C++语言实现。
1 问题数学模型[6]
假定投资者选定n种风险证券以分散投资风险,用ri和μi分别表示第i种证券持有期收益率和预期收益率,则有μi=E(ri),(i=1,2,…n)。用xi表示用于第i种证券的
投资额占总投资额的比例,则令:
r=(r1,r2,…,rn)T,r:N(μ,σ)
其中,μ=(μ1,μ2,…μn)T,σ为向量r的协方差阵,通常以方差作为证券风险的度量指标。所以组合证券的收益为令x=(x1,x2,…xn)T,则有Y:N(μTx,xTσx)。在无卖空制度的证券市场中,最优组合证券模型可
以写成:
其中,R为组合证券的预期收益率,P(Y≥R)表示证券组合收益率不低于预期水平的概率。根据文献[7],将模型(1)中的目标函数作如下变换,因为则U:N(0,1)所以:
则,目标函数变形为型(1)可以表示为下面形式:
2 粒子群优化算法
粒子群算法模拟鸟群的捕食行为,并用于解决组
合优化问题。算法初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次迭代中,粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值pBest。另一个极值是整个种群目前找到的最优解。这个极值是全局极值gBest。另外,也可以不用整个种群,而只是用其中一部分作为粒子的邻居,那么在所有邻居中的极值就是局部极值。在找到这两个最优值时,粒子根据如下的公式来更新自己的速度和新的位置。Vid=Vid+c1×rand()×(pBestid-xid)+c2×rand()×(g Bestid-xid)
其中,V[]为粒子的速度,rand()为(0,1)之间的随机数,c1,c2为学习因子,一般取为2。每一维粒子的速度都会被限制在一个最大速度Vmax下,如果某一维更新后的速度超过用户设定的Vmax,那么这一维的速度就被定为Vmax。
2.1 算法的实现过程
(1)参数选择。学习因子c1,c2,最大迭代次数NG,粒子数N,每一维最大速度Vmax。
(2)初始化粒子。本文采用实数编码,对每一个粒子的初始值(x1,x2…xn)的每一分量xi都取为(0,1)之间的随机数,然后根据进行归一化处理。其中xi表示第i种证券的投资比例。
(3)适应值函数的选取。适应值与目标解的距离直接相关,本文将模型(2)中的目标函数f(x)变换到适应值函数F(x)=M-f(x),M为足够大的值,保证适应值非负。
(4)粒子速度和位置的更新。根据上面的粒子速度更新公式(3)和位置的更新公式(4)进行。
(5)停止准则。达到规定的迭代次数就停止。
2.2 实例应用
对于上述粒子群优化算法,本文使用C++语言实现。假设证券的收益率服从正态分布N(μ,σ),利用参考文献[2]给出的一个7种证券组合模型进行计算。
各种证券的期望收益率:
其中,收益率方差矩阵σ为:
证券组合的预期收益率R=0.1。学习因子c1,c2均取为2,粒子数取为20,最大速度Vmax取为0.2,适应值函数取为F(x)=100-f(x)。同时,在更新粒子时,通过给变为负值的分量循环加上一个很小的值(文中采用0.0005),直到它为一个接近零的值,保证xi为正。并且每次更新后都重新进行了归一化处理。实验结果比较如表1。表中前面三种算法的实验数据皆来自参考文献。
总的来说,粒子群算法少了遗传算法的交叉、变异等操作,实现起来更为简单,但是效果却比遗传算法来的好。而且据文献[7]中所述,遗传算法到的92代才开始收敛。而本文中迭代次数仅设为50。因此粒子群算法的收敛性和计算效率要比遗传算法来的好。
3 结束语
本文分析了一种在概率准则意义下组合投资模型,介绍了其传统的求解方法,并根据粒子群优化算法的思想,给出了一个新的求解方案。然后用C++编程实现,并结合实例与传统求解方法(理论值)、随机模拟结合遗传算法、遗传-禁忌算法等进行比较,验证了文中采用算法的可行性,其较高的收敛性和计算效率为组合证券投资者提供了一种高效的决策方法,具有较高的实用价值。
摘要：本文在分析概率准则下的组合投资问题模型的基础上,提出了一种基于粒子群优化算法的求解方案,并用C++加以实的收敛性和计算效率,为组合证券投资者提供了一种高效的决策方法。现,然后结合实例,和传统方法、随机模拟结合遗传算法,遗传—禁忌算法等进行比较。证明了文中采用算法具有较高
关键词：组合投资,粒子群优化算法,概率准则
参考文献
[1]Markowitz H.Portfolio selection[J].Journal of Finance,1-952(3):77-91.
[2]梁建峰,唐万生.有交易费用的组合证券投资的概率准则模型[J].长沙:系统工程,2001,19:5-10.
[3]Tang Wansheng,Han Qiheng,Liguangquan.Cash management decision with probability criterion[J].Proc IEEE/SMC,2001:26-70-2673.
[4]Tang Wansheng Han Qiheng,Li Guangquan.The portfolio se-lection problems with chance-constrained[J].Proc IEEE/SMC,2001:2674-2679
[5]胡晓辉.粒子群优化算法介绍[z].http://icdweb.cc.purdue.edu/hux.2002-04.
[6]王竹芳,潘德惠.用遗传-禁忌搜索混合算法求解组合投资问题[J].沈阳:东北大学学报(自然科学版),2006,27:111-114.
[7]王燕青,唐万生,韩其恒.基于遗传算法的概率准则组合证券模拟求解[J].天津:管理科学学报,2002(6):29-33.
组合推荐算法 篇4
输电网络规划分为静态规划和动态规划, 静态规划只关心某一负荷水平年的线路架设方案, 不考虑线路在何时进行架设的问题;动态规划在规划期内分为多个水平年, 需要考虑何时何地架设多少线路, 并且还要考虑到规划期内不同水平年之间的过渡问题, 这种规划一般用于输电系统的长期规划[1]。动态输电网络规划问题并不能简单地看作多个静态规划问题的组合, 因为其存在如下一些问题:1) 前一阶段架设的线路必定在后续阶段延续;2) 不同阶段内的投资需要考虑到资金的时间效益。动态输电网络规划较静态规划问题复杂很多。
输电网络规划研究的对象是网络的结构, 各待选支路都需要作为独立的决策变量来考虑, 特别是动态规划问题还要考虑各支路在何时架设线路, 其解空间的维度和组合空间规模都十分巨大。并且需要在各个阶段都满足多个约束条件 (如线路的容量, 支路线路的上限等) , 具有离散、非线性、多峰、不可微[2]等复杂的数学特征。人工智能算法在近几十年内得到了快速发展, 出现了:遗传算法[3,4]、进化算法[5]、粒子群算法[6]、蜜蜂算法[7]、鱼群算法[8]、食物链算法[9]、植物生长算法[10]等诸多智能算法。人工智能算法提供了一种通用的计算方法, 其不依赖于问题的具体领域[11], 对具有离散、不可微等复杂数学特征的问题也能够进行求解。人工智能算法从解空间的全局进行随机有向搜索, 同时从深度和广度两个方面进行, 理论上能给出问题的全局最优解。
自1975年Holland创立遗传算法以来, 遗传算法作为强有力且运用广泛的随机搜索和优化方法, 其可能是当今影响最为广泛的智能算法之一[12]。在求解多阶段输电网络规划问题过程中需要考虑时间决策量, 针对此问题文[4, 10]采用了相应的编码方式, 但都各自存在一定的缺陷。为此本文提出了组合编码法。组合编码将多阶段输电网络规划问题的动态特征隐含其中, 计算过程无需再单独考虑时间决策量, 使得动态规划问题能够类似静态问题一样使用遗传算法进行求解。针对多阶段输电网络规划问题, 采用了算术交叉、分段变异、减小罚系数等方法对遗传算法进行了改进。以19节点系统对算法进行验证, 结果表明所提方法能够在较短的迭代次数内得到最优解。
1 遗传算法及其改进
遗传算法是从问题潜在解集的一个随机种群开始的, 而一个种群则由经过基因编码的一定数目的染色体组成。每个染色体实际上是带有特征属性的一个解。染色体作为遗传物质的主要载体, 即多个基因的集合, 其编码 (基因型空间) 是某种基因的组合, 它决定了染色体所代表的解 (表现型空间) 。遗传算法需要实现从表现型到基因型的映射即编码工作, 由于仿照基因编码的工作很复杂, 我们往往进行简化。随机生成若干个染色体构成初始种群, 之后按照适者生存和优胜劣汰的生物学进化原理, 通过逐代演化产生越来越好的解。
遗传算法的基本组成部分由Michalewicz归纳[12]为:1) 问题的解的遗传表示, 即问题解的表现型空间如何通过合理的编码映射到染色体的基因型空间;2) 创建解的初始种群, 一般采用在基因型空间内按种群染色体数量随机生成;3) 构建评价染色体优劣的适应度函数, 一般针对最小化或者最大化问题进行相应的函数变换来构建;4) 由父代染色体遗传产生子代染色体的遗传算子, 一般包括选择、交叉和变异;5) 遗传算法的参数设定, 由于遗传算法属于随机算法, 因此参数的选择一般只能采用试探的方法。
1.1 组合编码
如何将问题的解编码成为染色体是遗传算法使用中关键的一环。当染色体解码为相应的解时其基因型空间到表现型空间的映射性质存在1对1, 1对n, n对1三种情况。我们最希望的是1对1映射, 因为该映射能够保证在产生后代时不会存在无价值的操作[12]。染色体基因型空间的距离与表现型空间的距离要尽量一致, 若编码方法不合理, 一个在表现型空间相邻的解编码为染色体时在基因型空间距离却是最远时, 那么称为出现了Hamming悬崖[12], 此时会严重影响遗传算法的性能。
动态问题与静态问题的区别在于支路中线路的架设还包含有架设时间这个决策变量, 需要考虑各支路在哪个阶段架设多少线路。文献[4]中以每条线路架设的阶段作为变量, 并且采用二进制数编码。该编码方式存在比较严重的冗余问题。冗余的原因在于:1) 同一支路的各条线路之间并没有区别, 该编码方式却将其单独处理, 编码的结果会导致同一个表现型对应多个基因型;2) 阶段的数量用二进制表示时存在冗余, 例如有4个规划阶段, 那么表示1、2、3、4、5 (5表示在整个阶段都不建设) 这5个状态则需要3个二进制位, 而3位二进制可以表示8个状态, 因此出现了冗余的无效染色体。文献[10]采用了实数编码, 染色体的每一位代表一条线路, 对应位的数值表示架设的阶段。该编码方式虽然能避免产生无效的冗余染色体, 但是与文献[4]一样, 多个染色体会对应同一个架设方案, 也出现了基因型空间到表现型空间n对1的缺陷。
为了实现基因型空间到表现型空间1对1, 以及基因型空间中没有无效染色体的目的, 提出了组合编码法。由于每条支路所增设线路都有一定的上限, 且该上限一般较小, 因此每条支路在整个规划期内各个阶段的架设方案的组合数量较少。增设上限为2条线路的支路在4个阶段内的组合数量是15, 增设上限为3条线路的支路在4个阶段内的组合数量也不过是35, 从而可以通过枚举法将各个支路在给定阶段的规划方案的组合单独求出。编码过程中, 首先找出可架设线路的支路, 基因的每一位表示一条可增设线路的支路;然后按一定的组合规律计算出各支路在规划期内独立的组合方案, 对应位的值表示该支路的规划方案编号。以增设上限为2条线路的支路为例, 表1中枚举出该支路的15种组合方案, 那么对应的基因位的取值为[1, 15]内的整数。
这样的编码方式能够保证基因型到表现型的1对1映射, 表1中的编码结果也清晰表明表现型空间与基因型空间避免了Hamming悬崖的问题, 在基因型空间相邻的2个编码在表现型空间对应的2个解也是相邻的。该编码方式将多阶段的规划方案变成了各个支路在整个阶段的规划方案的组合问题, 架设时间的决策变量已经隐含在编码中不需要另做考虑。完成编码后, 将资金的时间效益考虑进来就可以采用类似于静态规划问题的方法进行求解。
1.2 适应度函数及惩罚系数的设定
动态输电网络规划问题的组合数量庞大, 为加快遗传算法的收敛速度, 参照文献[3]中采用的指数变换法对目标函数进行构造, 其中线路的容量约束采用式 (1) 所示的罚方法并入目标函数, 将其转化为无约束问题。
其中:C为线路在多个阶段的投资费用的贴现值, 计算方法在下文给出;Op为网络在各个规划阶段的过负荷量的总和, 其采用直流潮流模型进行潮流计算求出;Kpunish为网络出现过负荷的惩罚系数;Cav是种群中C*的平均值;β是一个给定的系数;M为遗传算法的进化的代数;U为适应度函数。
为了准确评估规划方案的优劣, 理论上惩罚系数应选择较大的值。但是最优解可能依赖某些过负荷的方案通过交叉变异得到, 有些接近最优解的次优解染色体可能在交叉变异过程中导致过负荷, 这些染色体携带了优良的基因信息, 为了保留这些染色体, 惩罚系数又不能选的过大, 否则很难得到最优解而收敛到那些有冗余线路的次优解。为了更好地收敛到最优解, 在迭代的初期选择适当小一点的罚系数, 随着迭代的进行再逐渐增加。为此在进化过程中, 将种群中不过负荷且投资最小的方案作为最终迭代结束的待选方案, 当进化过程中出现不过负荷且投资更小的方案时替换上一次的待选方案, 在进化结束时就能得到进化过程中出现过的最好的方案。
1.3 算术交叉
文中使用的组合式的实值 (整数) 编码方式, 其交叉有离散交叉, 算术交叉等方式。动态输电网络规划问题的编码每一位代表的是对应支路在整个规划期内的规划方案, 其每一位的状态数相对于2进制编码较多, 上述2条待选线路的支路在4个阶段的规划期内的规划方案有15种, 因此应采用算术交叉方式。常用的算术交叉方式为:λY+ (1-λ) Z。其中Y, Z表示2个染色体向量, λ为[-d, 1+d]上的随机数[12]。由于多阶段输电网络问题的染色体向量维度较多, 若对整个向量作一次性的交叉效果不佳, 本文对染色体的每一位进行均匀的算术杂交, 然后对其取整。 (d的取值一般为0~1, 本文取0.25) 。
举例如下:
解空间: ([1, 5];[1, 5];[1, 5];[1, 35];[1, 15];[1, 35])
染色体Y:5|1|3|9|13|20
染色体Z:3|1|2|20|9|16
子代1:3.24|1|2.68|8.78|12.60|15.08取整后为3|1|3|9|13|15
子代2:4.44|1|1.85|6.80|10.52|17.08取整后为4|1|2|7|11|17
1.4 分段变异
变异本身具有很强的全局搜索能力, 往往通过变异能产生新的基因片段, 从而可能产生新的较优染色体。变异方式的选择非常重要, 在输电网络规划中采取的变异方式是每次变异只随机选择2位或者1位进行变异。
在进化 (迭代) 的初期, 主要是进化那些投资费用大且过负荷也很严重的适应度很差的染色体。当某一基因位发生变异时, 表现为该支路在各阶段的组合方案发生变化, 此时网络的结构在该支路发生变化后可能会出现过负荷或者冗余等问题。若另外一条支路的方案也做相应调整, 这样就可能相互之间弥补。因此初期采取成对变异是合适的。随着进化的推进, 线路投资和过负荷达到较好的状况时, 如果继续进行成对变异则会对最优解的搜索带来不良影响, 可能难以得到最优解。一般来说, 次优解相对于最优解可能存在冗余线路, 因此在进化的末期适合采用1位变异来实现对某些冗余线路的规划方案进行改变以获得最优解。简而言之:在进化的初期采用成对变异, 进化的后期采用单独变异。
2 动态输电网络规划模型
以式 (4) 所示的规划期内投资费用的贴现值作为目标函数;并满足式 (5) 、式 (6) 线路容量约束, 式 (7) 支路可增设线路数量约束。
目标函数为
约束条件为
式 (4) 中:lc为第l条支路增设1条线路的费用;nl, t为第l条支路在阶段t时线路数量;α为银行的年利率;C为规划方案对应的投资费用;T为各阶段的水平年;Ω为可增设线路的支路集合。式 (5) 中:lP, t为阶段t时支路l通过的有功功率;ln, y为第l条支路在y阶段增设的线路数量;ln0为支路l规划前的线路数;Plmax为支路l每条线路的容量。式 (6) 中:δli, t, δlj, t分别为支路l首端i和末端j在阶段t时的相角;lx为支路l每条线路的电抗。式 (7) 中:nl, t与式 (5) 中的ln, y相同;nl, max为支路i可增设线路的上限。
3 计算流程
步骤1原始数据读取、编码预处理:按1.1节的方法对各支路可架设线路数量在给定的规划阶段内分别枚举出架设方案得到基因型空间到表现型空间的编码表。
步骤2初始化种群:根据各支路的方案组合数量随机生成基因, 在满足网络结构连通性 (各阶段都要满足) 的约束下, 生成给定种群规模的染色体初始种群。
步骤3适应度计算:种群中每个染色体表示一个规划方案, 通过直流潮流计算, 分析各个染色体构成的网络在各个阶段的潮流, 从而计算出各支路在不同阶段的过负荷总量。然后计算各个染色体对应方案的投资费用, 利用适应度函数计算出种群中各个染色体的适应度值。将适应度值高的10%~15%染色体作为精英放入精英库。
步骤4轮盘赌选择:将种群各个染色体的适应度值形成生存概率表, 根据生存概率表构成轮盘, 通过多次轮盘赌, 选择出待交叉变异的染色体。
步骤5交叉变异:将选择出来的染色体按1.3节给出的方式进行交叉, 以一定的随机概率按1.4节给出的方式进行变异, 从而产生新的子代染色体, 子代中的糟粕染色体用精英库中的染色体代替。
步骤6收敛性判断:产生的子代代替父代进行迭代进化, 进化过程中保留无过负荷且投资费用最小的染色体作为待选的最优解。按一定的收敛条件判断终止迭代, 如设定一定的迭代次数上限。满足条件时输出迭代进化过程中最优的方案以及对应的投资费用。
4 算例分析
如图1所示为19节点测试系统[13], 其包含有4个规划阶段, 有12条支路共21条线路可以增设。对每条支路在规划期内各阶段的增设方案进行枚举, 图1所示支路2-3有3条线路可以增设, 在4个规划阶段内有35种规划方案, 该基因位对应解空间内的一个维度, 该维度的取值范围为[1, 35]之间的整数。该测试系统的解空间为: ([1, 35];[1, 5];[1, 15];[1, 35];[1, 35];[1, 5];[1, 35];[1, 5];[1, 5];[1, 5];[1, 5];[1, 5]) 。算法参数设定:种群规模为80;变异率为0.16;交叉系数d为0.25;惩罚系数初值设定为69, 并随进化代数T按69+30ln (T) 逐渐增加;精英比例为10%。按照上节给出的流程计算, 迭代进化次数的上限设定为120次。图2所示为经过92次迭代后搜索到最优解的投资费用进化图, 其投资总费用的贴现值为649.921 9万元, 该方案的基因型为:30|3|7|22|12|1|7|1|1|1|1|1, 解码后如表2所示。按上述参数重复进行20次测试, 结果如图3所示。有4次得到最优解649.921 9万元, 其余是与最优解非常接近的次优解, 投资费用的平均值为659.568 3万元。表明在较少的迭代进化次数下能够得到最优解或与最优解接近的次优解。
5 结论
本文采用组合编码法将多阶段输电网络规划问题中需要考虑的时间决策变量包含进来, 从而解决了各个阶段之间复杂的协调耦合问题。该编码方式满足基因型到表现型的1对1映射, 以及基因型空间和表现型空间距离的一致性, 从而使得遗传算法求解过程中不会存在重复和无效的编码且不存在Hamming悬崖, 保证了算法的搜索效率。针对多阶段输电网络规划的具体问题采用了算术交叉、分段变异、减小罚系数等方法对遗传算法进行了改进, 改进后的算法性能有了进一步的提高。以19节点系统为例验证了所提方法的可行性。
摘要：针对动态输电网络规划过程中需要考虑时间决策量的问题, 提出了组合编码方式。组合编码方式将多阶段输电网络规划中的时间决策量隐含在编码中, 从而使得多阶段的动态输电网络规划问题能够转换成静态规划问题进行求解。该编码方式满足表现型和基因型的1对1映射, 及表现型空间与基因型空间距离上的一致性, 从而保证了遗传算法的搜索效率。此外, 针对动态输电网络规划的特点, 对遗传算法的交叉算子、变异方式、适应度函数、惩罚系数等方面进行了改进, 进一步改善了遗传算法求解多阶段输电网络规划问题的性能。以19节点系统为例对算法进行了验证, 结果表明能够在较短的进化代数内得到问题的最优解。
基于遗传算法的Web服务组合优化 篇5
关键词：Web服务,Web组合服务,遗传算法,服务质量
0 引言
据《中国B2C市场趋势预测2006—2010》中的数据显示,到2010年中国B2C市场规模将达到188.3亿元,从2006年到2010年B2C市场规模的年均复合增长率为49.89%。随着电子商务的迅速发展,具有良好封闭性、松散耦合和高度可集成等特点的Web服务技术便应运而生,不少企业把应用、资源和技术加入到Web服务中去,一个EDS全球顾问公司发现年销售额在低于5,000万元到高于10亿万元的企业(这些企业覆盖了20个纵向行业领域)中有75%已经布署了一个或多个Web服务。
为了充分利用已有的Web服务,近年来国内外学术界和行业界围绕着服务组合开展了大量的研究工作,并发布了一系列用来描述Web服务组合的语言,如:微软公司的XLANG,IBM公司的WSFL,BEA公司的WSCI,IBM、微软和BEA公司联合推出的BPEL4WS,乔治亚大学提出的DAML2S等。这些研究在Web组合服务的功能实施方面取得了很大的成就,然而,组合服务的质量QoS(Quality of Service)却往往被忽略,如何提高组合服务的质量是一个非常具有挑战性的问题,它对于Web服务组合的成败起着决定性的作用。本文提出了基于遗传算法的Web服务组合优化的策略,给出了构建Web服务及选择最佳服务的方法,从而可以提高组合服务的QoS,并使Web服务组合的满足个性化需求。
1 遗传算法概述
遗传算法GA(Genetic Algorithm)是由美国Holland教授于1975年根据生物进化理论和遗传变异理论提出的一种基于种群搜索的优化算法,其思想是通过选择、交叉和变异等作用使种群不断进化,最终收敛到优化解。
遗传算法可用于复杂系统的优化计算[1],它主要有下述几个特点:
(1)以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值来进行优化计算,而遗传算法是以决策变量的某种形式的编码为运算对象。这种对决策变量的编码处理方式,使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念,模仿自然界中生物的遗传和进化等机理,对那些无数值概念或很难有数值概念,而只有代码概念的优化问题,编码处理方式更显示出了其独特的优越性。
(2)直接以目标函数值作为搜索信息。传统的优化算法不仅需要利用目标函数值,而且往往需要目标导数的导数值等其他一些辅助信息才能确定搜索方向;遗传算法使用由目标函数位变换得到的适应度函数值来确定进一步的搜索方向和搜索范围,无需目标函数的导数值等其他一些辅助信息。从而可以使得我们把搜索范围集中到适应度较高的部分搜索空间中,提高了搜索效率。
(3)同时使用多个搜索点的搜索信息。传统的优化算法往往是从解空间中的一个初始点开始最优解的迭代搜索过程。单个搜索点所提供的搜索信息毕竟不多,所以搜索效率不高,有时甚至使搜索过程陷于局部最优解而停滞不前;遗传算法不是从一个单一的个体开始搜索,而是从由很多个体所组成的一个初始群体开始最优解的搜索过程,对这个群体所进行的选择、交叉、变异等运算,产生出新一代的群体,在这之中包括了很多群体信息。这些信息可以避免搜索一些不必搜索的点,所以实际上相当于搜索了更多的点,这是遗传算法所特有的一种隐含并行性。
(4)使用概率搜索技术。传统的优化算法往往使用的是确定性的搜索方法,一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系,这种确定性往往也有可能使得搜索永远达不到最优点,这就使算法的应用范围受到限制。而遗传算法属于一种自适应概率搜索技术,其选择、交叉、变异等运算都是以一种概率的方式来进行的,从而增加了其搜索过程的灵活性。
2 基于遗传算法的Web服务组合
2.1 Web组合服务的描述
假设一个完整的Web组合服务可以由n个Web子服务ws1,ws2,ws3,…,wsn组成,每个子服务包括m个服务质量属性,可用下式来描述一个组合服务。
其中,表示实现Web服务的第i个功能的子服务;qij表示第i个子服务的第j个服务质量属性。
2.2 Web服务的QoS度量
在文献[2]中,对语义Web服务的质量参数进行了详细的描述,语义Web服务质量通常可以定义二种参数:Web服务质量通用参数和Web服务质量领域相关参数。
通用参数,又称为领域无关的参数,是指与Web服务领域特性无关的性能指标,通常有以下内容:
(1)时间:Web服务完成指定任务所花费的时间,其测量指标主要包括响应时间、执行时间、延迟时间;
(2)成本:Web服务占用的资源、用户为服务支出的费用,其测量指标主要包括成本、系统开销、吞吐率;
(3)可靠性:表示能够成功完成Web服务的概率,其测量指标主要包括成功率(或故障率);
(4)安全性:表示Web服务的可信赖程度,其测量指标主要包括身份验证、授权、保密性等;
(5)可用性:可用性指Web服务是否已就绪可供立即使用服务可用性、网络可用性等;
(6)信誉度:描述服务使用者对所调用的Web服务的评价,其测量指标主要包括点击率、用户满意度;
领域相关的参数,领域相关的参数反映了与特定领域中的业务内容、业务上下文以及服务提供商等相关的信息,例如所购置的商务礼品的制作质量和包装质量,物品设计的风格和品味等,它是服务用户在衡量Web服务的服务质量以及选择Web服务时的重要参考因素。领域相关的参数没有标准或统一的规定,一般由领域内的专家或设计者根据自己的经验制定,也可以从行业界已经存在的领域本体中学习得到。
描述Web服务QoS属性,可以有两种方法。一种是通过扩展WSDL协议,增加对QoS的支持。如文献[3]中介绍在WSDL中的tport元素中加人一个tOperationInst属性,用以描述Web服务的responseTime (响应时间)、availability (可用性)、concurrency(支持并发事务的数量)、price(使用该服务的价格)、fine(服务代理、提供商和客户之间违约而需支付的罚金)、securityLevel(服务的安全等级)六个QoS属性。另一种方法是开发用于描述QoS属性的协议。目前主要有由BEA、IBM、Microsoft及SAP开发的WS-Policy Frameworrk、由OASIS XACML技术委员会下的一个小组创建的WSPL(WebServices Policy Language)和由W3CWeb服务描述工作组创建的WSDL2.0 features and properties。但这些Web服务QoS的规范目前尚未成为标准,Web服务QoS描述一般仍以扩展WSDL为主。
2.3 基于QoS的Web服务组合模型
组合服务中的子服务选择问题可以表述为:假设组合服务需要完成n项任务,对应于某项特定的任务,存在多个子服务,优化目标就是为每项任务选择一个最佳的子服务。该问题的形式化描述如下:
设:Y={yi|i∈[1,n]},表示组合服务的所有n项任务的集合;
Xi={Xij|j∈[1,mi]}(i=1,2,…,n),表示可以完成任务yi的候选子服务的集合,mi为可以完成任务yi的候选子服务的数量;
组合服务Y完成任务yi的质量参数为:tij(时间),cij(成本),rij(可靠性),sij(安全性),aij(可用性)和rpij(信誉度)等通用参数,根据需要用户还可以选择其它领域相关参数;T,C,R,S,A,Rp分别表示完成所有任务的总体时间、成本、可靠性、安全性、可用性和信誉度。则该问题的优化目标就是要选择一组子服务:
F={f1,f2…,fn},且F∩Xi={fi},使得:
这是一个多目标优化问题。为此,可以采用如下优化目标函数:
maxZ=w1T'+w2C'+w3R+w4S+w5 A+w6Rp (4)式中,wi为各项指标的权重,用户可以根据自己的经验来确定,也可以通过专家评分法、层次分析法(AHP)、熵值法等进行确定。权重的约束条件为:
为了进行统一运算,须将T',C',R,S,A,Rp化为无量纲单位的数值。
tmax,Cmax,rmax,smax,amax和rpmax,表示所有子服务完成各自任务的相应性能参数中的最大值;
另外,由用户还可以根据各自的偏好和需要来定义组合服务的最大执行时间、最大成本、最低可靠性要求、最低的安全要求、最低的可用性要求和最低的信誉度要求。所产生的约束条件:
式中,Tmax、Cmax、Qmin、Smin、Amin、Rmin为用户根据实际需要指定的组合服务的最大执行时间、最大成本、最低可靠性要求、最低的安全要求、最低的可用性要求和最低的信誉度要求。
2.4 用遗传算法对模型求解
步骤1染色体编码
采用二进制编码方式,每条染色体可以表示为图1所示的代码串,表示一种子服务的组合方案,代码串中的每一位xij代表一个候选子服务的状态,xij=1表示任务yj第i个候选服务被选中参与服务组合,xij=0表示未被选中。
步骤2初始化群体
组合数组Y,根据子服务所能完成的任务进行分类,生成初始化的种群,保证每个任务中初始化一位。在种群中,串的长度是相同的,种群的大小根据需要按经验或专家提供的建议给出。
步骤3计算当前种群每个个体的适应度
本问题的适应度函数可定义为:
式中,fi表示第i个质量属性指标与用户要求的误差的绝对值;wi表示第i个质量属性指标在组件服务质量要求中重要程度的权值;f是所有指标与用户要求的误差绝对值之和。
排序适应度函数,就是将同一代群体中的n个染色体按目标函数值从大到小进行排序。
步骤4选择
选择操作建立在对个体的适应度进行评价的基础之上。选择操作的主要目的是为了避免基因缺失、提高全局收敛性和计算效率。我们在这里采用的是精英选择策略,即当前群体中适应度最好的个体不参与交叉运算和变异运算,而是用它来替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最差的个体,这首先保证父代中最优的个体在子代中至少出现一次,然后按照标准的轮盘赌方式进行选择操作。这样可以保证最优秀的染色体被保留到下一代。
步骤5交叉和变异
利用文献[4]所提出的一种交叉和变异概率的自适应调整规则进行交叉和变异,使每个个体按其适应度大小选择不同的交叉概率Pc和变异概率Pm。而且,在遗传过程中根据适应度的变化自动调节这两个控制参数。这样,群体中每个个体对环境的变化就具有自适应调节能力。
在遗传过程中,设较差个体的交叉概率为Pc0,最优个体的交叉概率为Pc1(Pc1<Pc0),较差个体的变异概率为Pm0,最优个体的变异概率为Pm1(Pm1<Pm0),则自适应交叉和变异概率可以表示为:
式中:f是两个执行交叉操作个体适应度中较小的一个;fmax为群体中的最大适应度;为群体的平均适应度;f'为执行变异操作个体的适应度。
交叉概率和变异概率可以自适应调整,对适应度小的个体采用较大的交叉概率,加速其更新速度;对适应度大的个体采用较小的交叉概率,使这些较优的解不易丢失。若群体中的个体趋于相同时,个体的适应度就接近群体的平均适应度,由式(21)可知,每个个体的变异概率也较大,因此很快得到新个体,从而保证了群体的多样性,并克服了算法的早熟现象,将交叉变异后产生的新种群作为下一代群体,并将上一代群体中的最优个体保留到下一代。
步骤6终止
采用最大迭代次数法则作为终止条件,并将具有最大适应度的个体作为最优解。
3 结束语
由于遗传算法具有以决策变量的编码作为运算对象、直接以目标函数值作为搜索信息、同时使用多个搜索点的搜索信息和使用概率搜索技术等特点,使我们把搜索范围集中到适应度较高的部分搜索空间中,大大提高了搜索效率,增加了搜索过程的灵活性,将遗传算法应用到Web服务组合中,不仅可以提高组合效率和组合质量,还可以使所提供的组合服务更具个性化。目前这项研究仅在仿真实验阶段,下一阶段,我们将尝试以易购365购物网站作为该技术的实际应用平台进行进一步的实证研究。
参考文献
[1]Godberg D E.Genetic Algorithms in search,Optimization and Machine Learning[M].Addison-Wesley,1989.
[2]吴金红，殷之明，等．基于OWL-S语义的Web服务质量描述框架．情报杂志，2007，10．
[3]陈彦萍，李增智，等．Web服务组合中基于服务质量的服务选择算法[J]．西安交通大学学报，2006，40(8)．
[4]代颖．基于遗传算法的供应链联盟伙伴选择．西南交通大学学报，2004，39(4)．
一种分阶段组合测试数据生成算法 篇6
关键词：组合测试,混沌优化算法,Tent映射,测试数据生成
0 引 言
软件测试在构建可信软件的过程中有着举足轻重的作用,占到整个软件开发总成本的一半以上。测试数据生成是软件测试的核心,穷尽测试在测试过程中无法做到,如何在保证测试效果的前提下,减少测试数据规模,节约测试成本,已成为软件测试中的一个热点问题。
组合测试的概念最早由Mandl于1985年在测试Ada编译程序时提出,后来kuhn等人通过缺陷分析报告分析发现了组合覆盖强度和缺陷检测间的关系,两两组合测试可以发现70%的缺陷[1],Cohen等人应用两两覆盖测试技术对Unix中的“sort”命令进行了测试,测试结果为模块覆盖率93.5%,判断覆盖率83%。因此,两两组合测试是软件测试中的一种行之有效的测试方法,能够在保证错误检出率的前提下采用较少的测试数据。
两两组合覆盖的测试数据生成问题是一个NP-hard问题,在实际的测试中,人们一般都利用启发式算法、贪心算法和一些数学代数等方法近似求解。近年来,两种或两种以上算法结合的混合算法也被引入用来解决测试数据生成问题,坎皮纳斯州立计算机学院的Thaise Yano等人提出的变长度多目标进化算法搜索测试数据[2],清华大学的PMyra Cohen等提出数据输入时间序列的覆盖矩阵抽样生成测试用例[3],南京大学的陈翔等提出基于蚁群算法的变力度交互生成组合测试数据,这些方法具有不同的特点,针对特定问题可以产生较好的效果。
混沌是存在于很多非线性确定系统中的一种普遍的现象,在一定范围内混沌变量的变化具有随机性、遍历性和规律性。利用混沌变量的这些特征进行优化搜索,能使算法跳出局部最优,保持多样性,改善算法的全局搜优性能。
本文在生成测试数据过程中采取了分阶段生成的思维方法,第一阶段用Tent映射定位因素值快速生成测试数据,随着测试数据的生成,迭代次数到达一定值后没有新的测试数据生成,陷入了局部收敛状态,此时停止Tent映射生成方法。进入第二阶段,从未覆盖的两两覆盖对入手,统计各个因素中出现取值的概率情况,选取该因素中概率最大的取值,依次选择生成一条测试数据,更新两两覆盖对集合,重新计算因素取值概率再选取,直至覆盖掉两两覆盖对中所有的因素值,测试数据生成结束。
1 测试数据生成问题
在软件测试中,根据待测软件系统SUT(Software Under Test)中测试和测试对象的基本特征和基本关系进行抽象,假设影响待测软件系统SUT的因素有k个,形成有限集P=(f1,f2,…,fk),这些因素可以是SUT的配置参数、内部事件、外部输入等, SUT的每个因素可在有限离散点集vt中取值,vi中有k(|Vi|=li,1≤i≤k)个元素,记为Vi={Vi1,Vi2,…,Vi1i},li称为参数vi的水平数[4]。
定义1 如果x1∈V1,x2∈V2,…,xk∈Vk则称k元组(x1,x2,…,xk)为待测软件SUT的一条测试数据。
定义2 由定义1生成的某个SUT的测试数据集合称为该SUT的测试数据集,简称测试集。
定义3 对于某个SUT的测试集,如果该测试集覆盖了这个SUT的任意两个因素的所有可能取值的两两组合,称该测试集为两两组合覆盖测试集。
例如,对于某个SUT有34 的测试输入,即有4个输入因素,每个因素有3个离散的取值,依次用,f1:v11,v12,v13;f2:v21,v22,v23;f3:v31,v32,v33;f4:v41,v42,v43表示,完全测试该系统,需要34=81条测试数据,但是如果采用两两覆盖测试准则,只需要9条测试数据(v11,v22,v31,v42),(v12,v21,v32,v42),(v13,v22,v31,v41),(v12,v22,v33,v41),(v11,v21,v33,v43),(v11,v23,v32,v41),(v13,v23,v33,v42),(v12,v23,v31,v43),(v13,v22,v32,v43)。第一条测试数据可以覆盖到两两组合对(v11,v22)、(v11,v31)、(v11,v42)、(v22,v31)、(v22,v42)、(v31,v42),依次,9条测试数据便可覆盖任意两个因素的所有取值组合[5]。
2 Tent映射及Tent序列
不同的混沌序列产生方法对于混沌寻优过程有较大的影响,Tent映射比Logistic映射具有更好的遍历均匀性[6],Tent映射具有均匀的分布函数,产生混沌序列的概率密度分布函数的初值敏感性不强,产生的混沌序列具有全局遍历性,且其迭代过程适合于计算机实现。因此本文的混沌序列产生采用Tent映射,Tent映射又称帐篷映射,是较为经典的一维混沌序列,Tent映射经过贝努力变换后可以表示为:
初值取0到1之间的数,g(x)的取值由x位于1/2左右位置来选择函数决定,假设将g(x)本次的结果作为下次产生g(x)1的x1,依次类推,产生x={x1,x2,…,xn}序列。
在迭代过程中,有两种非正常状态,当xi={0,0.25,0.5,0.75}时,分析迭代序列发现,x1之后将出现全0,此时陷入了Tent映射的不动点,当xi={0.2,0.4,0.6,0.8},迭代序列表明,x1之后重复0.2,0.4,0.6,0.8四个数,此时序列落入了Tent映射的小周期循环[6]。
下面给出Tent映射产生Tent序列的算法步骤:
Step 1 取初值x0= rand(0,1)(x0避免落入Tent的不动点和小周期点内),记入标志组z,取较小的修正值ϵ,z1=x0,i=j=1;
Step 2 以式(1)进行迭代,i自增1,产生X序列;
Step 3 If 迭代达到最大次数,则跳到Step 5;
Else if xi{0,0.25,0.5,0.75}或xi{0.2,0.4,0.6,0.8}则进入Step 4;
Else 回到Step 2;
Step 4 改变迭代初值xi=zj+1=zj+ϵ,j=j+i,返回Step 2;
Step 5 终止运行,保存X序列。
至此,得到由Tent映射产生的Tent序列X={x1,x2,…,xn}。
3 Tent映射分阶段生成测试数据
对于任意因素个数和水平数的测试输入,生成的组合测试数据集中某一因素值出现的概率满足同一因素下等概率分布的规律。由于Tent映射生成的序列具有遍历均匀的特点,因此,考虑将Tent序列引入到测试数据生成中,达到搜寻测试数据时迅速收敛的目标。由于覆盖对中各因素的混沌产生是独立的,没有考虑因素之间的组合关系,虽然各因素的取值均等出现,但是有可能出现重复覆盖和没有完全覆盖所有因素对,因此很有必要在后阶段统计尚未覆盖的两两覆盖对中某个因素值出现的概率来生成测试数据,迅速生两两没有被两两覆盖对覆盖到的测试数据。
3.1 Tent映射生成测试数据
由测试数据定义可得,在k个因素f1,f2,…,fk中,从每个因素f中取一个取值v,组成一个k元组,这个k元组就是一条测试数据。如何决定从fi的li个值中取哪一个,这是Tent映射生成组合测试数据的关键,贪心算法,各种代数方法以及仿生物学的方法在生成组合测试数据时区别就在于此。Tent映射所产生的X序列是分布于0到1间的连续性数值,与组合覆盖模型结合后,转化成离散的映射,从而定位在某一因素的具体取值上。从第i个因素里选k元组的第i项,其中,第i个因素有li个取值,定义因素fi的取值之间距离d=1/li,即把fi因素的值空间划分为li-1个长度为1/li的距离段,对应li个值的数据序列为D={d1,d2,…,dli}={1/li,2/li,…,li/li},然后根据当前混沌序列X里的x值对因素fi的取值序列映射,当x<d1,fi=vi1,当x=dj,fi=vilj,当dj-1>x>dj,比较x-dj-i和dj-x的大小,取dj和dj-1中距离x更近的元素对应的v值,fi=Vilj={lj|min(x-dj-1,dj-x)},对k个因素数依次用k个Tent的序列映射产生一条k元组的测试数据,称为一次迭代,再根据该条测试数据中两两覆盖所占的比例判断其优劣,决定是否保留该条测试数据。保留则添加测试数据并删除未被覆盖的两两覆盖对集合中的两两覆盖对,否则什么也不做,选取k个Tent映射中序列值L时,在前一次位置标记的基础上加上步长值,然后继续搜寻产生下一条测试数据,重复之前操作,直至未被覆盖的两两覆盖对集合为空[7]。
3.2 计算未覆盖因素值概率生成测试数据
尽管Tent映射产生Tent序列的过程适合计算机的计算处理,特别在因素数和水平数较大的情况,能达到简单快速的效果,在测试数据搜索初期迅速收敛,但到了后期,由于已产生的测试数据达到了较高的覆盖率,因此为了搜寻到具有满意覆盖率的测试数据,会不断重复迭代,导致迭代次数迅速增大,而且此时未覆盖的两两覆盖对已经很少,这时,从未覆盖的因素取值出现的概率入手,主要研究未被覆盖的两两覆盖对集,由这些因素值构造测试数据,可迅速生对两两覆盖对达到全覆盖且数目较少的测试集。
计算未覆盖因素取值生成组合测试数据的算法思想为:计算目前未覆盖的两两覆盖对中每个因素取值出现的概率并记录该值所属的因素名,若(vix,vjy)(1≤i≤k,1≤j≤k,x≤li,y≤lj)为尚未覆盖的两两覆盖对中的一个覆盖对,值vili为因素fi数中的一个值,vjlj值为因素fj数中的一个值,扫描未覆盖的两两覆盖对,记录每个因素数f中每个水平数出现的次数,若fi中的vim(1≤m≤li)出现tm次,则计算出每个因素数中每个值的概率,
现有组合测试模型f1:v11,v12,v13;f2:v21,v22,v23,v24;f3:v31,v32,v33,两两覆盖对集合中的二维组合对有(v11,v21)、(v21,v32)、(v12,v31),经统计可得到数据如图1所示。
在两两覆盖对中,因素f1中v11出现的概率为0.5,V12出现的概率为0.5,f2中v21出现的概率为1,f3中v31出现的概率为0.5,v32出现的概率为0.5,在扫描每个因素时,选取出现概率最大的因素值组成测试数据如(v11,v21,v31),将该条测试数据添加入测试数据集,更新两两覆盖对集合,即删除(v11,v21)和(v12,v31),重新统计两两覆盖对集合中因素值的概率,v12在f1中占1.0,f2中没有出现在未覆盖的两两覆盖对中的因素值,因素f中v32所占的比例为1.0,选取每个因素中值出现概率最大的,对于没有出现的,按因素下标顺序轮流选取该因素中所有值,此处可取v21,下次可选择v22。生成测试数据(v12,v21,v32),加入测试数据集,删除两两覆盖对集合中覆盖掉的对,至此,两两覆盖集合为空,计算未覆盖因素值概率生成测试数据阶段结束。
3.3 分阶段生成测试数据
综上所述,本算法将测试数据生成分为两个阶段:第一阶段,Tent映射生成测试数据,一次生成m条,然后根据每条测试数据对未覆盖的用例对集合中测试对的覆盖情况选出覆盖率最大的测试数据,添加到测试数据集,同时更新未覆盖的两两覆盖对集合,删除那些已被新添加测试数据覆盖到的覆盖对,直至测试数据随迭代次数增加无明显增加;第二阶段,计算未覆盖的两两覆盖对中每个因素取值出现的概率,在选取该因素值时按值的概率由大到小选择生成新的测试数据,更新两两覆盖对集合,删除新生成的测试数据覆盖到的两两覆盖对,再重新统计计算筛选,直至两两覆盖对集合为空。
基于Tent映射的分阶段组合测试数据生成的步骤描述如图2所示。
Step1 根据因素数个数k,生成k个Tent序列。
根据式(1)x∈(0,1),在避免序列中值落入不动点和陷入最小周期循环的情况下,生成k个Tent序列,X=(xi1,xi2,…,xm)(1≤i≤k,n=Nmax),其中,Nmax为保证经过多次迭代能够产生满足需要数量的测试数据的数值。整个X序列会因为初值x0和修正值ε的值不同产生差异。
Step2 两两覆盖对集合的生成。
两两覆盖对集合用来判断生成的某一条测试数据的优劣和测试数据生成是否该结束,这是一个排列组合的问题,对于k个因素的测试模型,两两覆盖集合中两两覆盖对的数目由每个因素的水平数决定,即所有因素取值的两两组合数。
Step3 用Tent序列进行一条组合测试数据的生成。
在k个因素中对第i个因素取值选取时,由第i个Tent序列进行选取,当前的序列选取标记定位出待选的xij,xij∈(0,1),构造序列D,具有和因素fi同样多的元素个数,元素值是以0为首项,1为末项,1/li为等差的等差数列,由xij定位出与D序列值中大小最为接近的值的位置,同位置映射到fi的值序列中,vixj为本次搜寻的结果,然后进入下一个位置因素的水平数选择,直至k个因素扫描完毕,生成一条k元组,作为本次迭代生成的一条测试数据。用如此方法一共生成m条测试数据,从中选出覆盖目前两两覆盖对集合中数据对数目最多的一条测试数据。
Step4 判断一条测试数据是否保留。
计算该条测试数据对两两覆盖对集合中的覆盖率,如果能够达到该条测试数据的所有两两覆盖对个数的α以上(定义一个满意的量化标准,后边β同此),可以选择保留,当迭代次数较大时,可将比率α调整稍低,添加该条测试数据时删除两两覆盖对集合中已被该条测试数据覆盖到的两两覆盖对。继续step 3,直到随着迭代次数增加没有新的测试数据被加入。具体条件可定为当迭代次数增加在β次以上,且没有新的测试数据生成,可以判定Tent映射的方法在本次测试数据生成中的优势已基本发挥完毕,由概率计算的方法生成剩余测试数据。
Step5 以未覆盖的因素取值出现次数为概率生成测试数据。
根据未覆盖两两覆盖对中出现因素概率值最大的取值作为该因素下被选中的取值,生成一条测试数据后更新未覆盖的两两覆盖对,然后继续统计两两覆盖对中因素取值的概率,生成新的测试数据,再更新未覆盖的两两覆盖对,直至未覆盖的两两覆盖对为空。
Step6 结束。
4 实例分析
为了比较Tent映射和分阶段Tent映射在生成两两覆盖组合测试数据集问题上的效果,我们分别进行了多次实验测试,同时引入文献[4]与其中的同输入参数的算法进行对比,算法自身参数设置如下:由于Tent序列对初值的敏感性较大,选择了随机生成的0到1间的浮点数产生Tent序列的初值X0,进行多次实验取平均值,ε= 0.00001,步长值L为59,一次生成200条测试数据,再根据覆盖率是否满足测试数据两两组合对的70%以上作为保留测试数据的量化标准,当迭代次数增加50次后,没有新的测试数据生成,则认为Tent混沌序列的优势发挥殆尽,用概率分析进入第二阶段生成测试数据,统计未覆盖的两两组合对中因素值的概率,当待取参数没有需要覆盖的值时,按照值在参数中的顺序轮流取一遍,以达到更高的覆盖率。
本文Tent映射算法和分阶段Tent映射生成两两覆盖组合测试数据集和现有方法AETG、PAIRTEST、NetWork、PSST进行测试集规模上的比较如表1所示。
表格中数据分析:输入参数和水平数采用正交表示方法,34表示有4个因素,每个因素具有3个离散的取值;(41×339×235)表示输入中有1个4取值的因素,39个3取值的因素,35个2取值的因素。从表格中的数据看出,Tent映射生成测试数据较之别的方法在数据集规模上可达到中下的水平,但是引入概率分析的分阶段Tent映射后比单纯用Tent映射有明显的改进,能够达到与其他算法相当的结果。
比较完其他方法与Tent映射、分阶段Tent映射生成的测试数据集规模后,我们比较一下Tent映射和分阶段Tent映射生成测试数据集在迭代次数上的不同,设置输入参数为(41×31×22),根据组合排列可知,两两组合测试集合中的用例对个数为(4×3+4×2+4×2+3×2+3×2+2×2)= 44个,由图3可以看出,在两两覆盖对集合中约有30(=44×70%)个对之前,Tent映射和分阶段的Tent映射是一致的,之后,Tent映射继续用Tent序列迭代产生测试数据,所以到后期,迭代次数急剧增加,而分阶段Tent映射从未覆盖的两两组合测试数据集合入手,分析未覆盖因素值出现概率,直接生成测试数据,能够在迭代次数较少的情况下,满足覆盖要求,整体计算量少。
5 结 语
本文提出分阶段的Tent映射混沌优化算法通过Tent映射和概率分析来产生测试数据,Tent映射生成Tent序列的过程适于计算机操作处理,可快速产生用来生成测试数据,后期,用概率分析的方法,采取与前期生成测试数据的逆向思维,直接从未覆盖的两两覆盖对中因素值入手,每次选择当前因素里取值出现概率最大的值组合生成测试数据,保证了该阶段生成的测试数据满足两两覆盖对情况下数目较少。实验表明,分阶段的Tent映射方法在快速生成测试数据和保证覆盖率上是有效的,可以作为已有数学方法、启发式算法和仿生学算法的一个补充。
目前,软件测试所受的关注程度与日俱增,组合测试作为软件测试的关键备受关注,同时取得了较好的成果,但是还有一些问题。随着维数的增加,多维组合覆盖的项数也极大地增加,多维组合覆盖表的构造是一个NP-hard问题,其次,满足二维以上的组合覆盖虽然能够更大程度地发现缺陷,但是以此做研究的尚少,因此,未来工作定位在对更高维的组合覆盖生成测试数据的研究上。
参考文献
[1]陈翔,顾庆,王新平,等.组合测试研究进展[J].计算机科学,2010,37(3):1-5.
[2]Thaise Yano,Eliane Martins,Fabiano Luis De sousa.A multi-Objec-tive evolutionary algorithm to obtain test cases with variable length[C]//Proceedings of the 13thannual conference on genetic and evolu-tionary computation,New York,2011:1875-1882.
[3]Xun Y,Myra Cohen,Patif M Memon.Covering array sampling of inputevent sequences for automated gui testing[C]//Proceedings of the 22thIEEE/ACM international conference of Automated software engineer-ing,New York,2007:405-408.
[4]查日军,张德平,聂长海,等.组合测试数据生成的交叉熵与粒子群算法比较[J].计算机学报,2010,33(10):1896-1908.
[5]Tai K C,Yu L.A test generation strategy for pairwise testing[J].IEEETransactions on Software Engineering,2002,28(1):1-3.
[6]张浩,沈继红,张铁男.一种基于混沌映射的粒子群优化算法及性能[J].系统仿真学报,2008,20(20):5462-5470.
[7]单梁,强浩,李军,等,基于Tent映射的混沌优化算法[J].控制与决策,2005,20(2):179-182.
[8]Chen X,Gu Q,Li A.Variable Strength Interaction Testing with anAnt Colony System Approach[C]//Proceedings of the 16th Asia-Pacif-ic Software Engineering Conference,Malaysia,2009:160-167.
低成本组合导航系统的数据融合算法 篇7
1 器件选择
本文所研究的是通用的基于传感器的惯导系统,所用器件均是市场上能够买到的产品。其中,MEMS陀螺和加速度计以中星测控有限公司、美国ANALOG公司、BEI公司生产的产品为主,GPS接收机以市面上的常见品牌的性能为主要参考依据。
2 数学模型
本文选择地理坐标系作为导航坐标系,在该坐标系下,惯性导航系统的位置、速度、姿态变换矩阵的微分方程为:
式中:
式中:r为载体的位置;V为载体的对地速度;RBL为姿态变换矩阵;RN为卯酉圈的曲率半径;RM为子午圈的曲率半径;Re为椭球的长半轴;f为地球的扁率;h为载体所在处的海拔高度;ΨBiB为陀螺敏感到的角速度ωbib的反对称矩阵;ΨLiL是载体相对惯性空间的角速度在导航坐标系中的投影ωLiL的反对称矩阵。
整个数据融合的思路基于间接卡尔曼滤波,因为直接卡尔曼滤波易导致导航计算系统的死锁。融合思路如图1所示。
由图1可知,这种松耦合的闭环组合模式的优点是简单、适应性强,基于该思路的卡尔曼滤波器构建需要考虑三个问题:
(1)时间同步问题,主要是指GPS信号和INS输出信号的同步;
(2)模型阶次的选择问题;
(3)状态变量的可观性问题。
因为这三个问题关系着数据融合系统的收敛性。其中信号的同步问题在导航数据的输出速率要求不是特别高的场合可以通过硬件或软件的方法解决,此处不在赘述。为了解决第二个问题和第三个问题,下面给出数据融合滤波器的状态方程。位置偏差的方程为:地理系中位置的矢量表示为rL=(φ,λ,h)T,其中φ为纬度,λ为经度。基于式(1)得到位置误差的具体表达式为:
速度误差方程为:
式(3)中:φ为姿态偏差;f为加速度计敏感到的比力信息。
姿态偏差的微分方程为:
式中:ωLiL为地理坐标系相对惯性坐标系的角速度在地理坐标系中的投影;RbL为姿态变换矩阵。
姿态偏差微分方程具体的标量形式为:
GPS接收机的信息包括位置和速度,而且其位置信息和速度信息在组合时已被转换到当地地理坐标系中,时间的延迟问题已通过软件的手段解决。
3 可观性分析和阶次优化
由上述分析和讨论可知,系统的可观性对状态估计的影响可谓举足轻重[5,6,7,8]。因此,在这节里专门研究组合导航的数据融合卡尔曼滤波器的可观性问题和模型的阶数选择问题。
由文献[7,9]可知,离散卡尔曼滤波器的可观性随载体的运动状态而定,在载体作纯线加速运动或匀角速度转动时,系统可以认为是线性时不变系统,而当载体进行非纯线加速或匀角速度转动时,卡尔曼滤波器方程就变为线性时变系统。因此,鉴于前人对线性时不变系统的研究成果,本文只研究线性时变系统的可观性和状态估计的敛散性的问题。
系统原始的模型如下:
式中:X=[δP,δV,ε,dx,dy,dz,bx,by,bz]T,δP包括经度偏差、纬度偏差和高度偏差;δV包括东向速度偏差、北向速度偏差和天向速度偏差;φ代表SINS计算出的姿态角与理想姿态角的偏差;d代表加速度计的零偏,b代表陀螺的零漂,这两项均按一阶高斯-马尔科夫过程建模。观测信息有两种取法:第一种观测信息是来自SINS和GPS的位置差,第二种观测信息来自SINS和GPS的位置差、速度差。
加速度计的零偏模型为:
陀螺的零漂模型为:
式中:τd为加速度计零偏过程的时间常数;τb是陀螺的零漂过程的时间常数;wd和wb为零均值的高斯白噪声。
基于的组合导航系统的可观性分析过程首先是将系统模型离散化,在假设离散周期很短和载体动态变化不剧烈的条件下,依据分段线性化的手段进行系统的可观性矩阵的秩的计算,如果满足:
则称该系统完全可观。当然,可观性只是滤波器收敛的必要条件。
具体离散化时需要计算的传递矩阵的计算方法文献[10]。
把方程(6)离散化之后,随机线性系统的可观性按照式(9)的思路可以有好几种判定方法,选择的是文献[10]中的方法。此时,分析分为两种情况:
(1)系统选择15个状态变量,观测信息选择3个;
(2)系统选择15个状态变量,观测信息选取3个位置和3个速度信息。
4 数学仿真
基于第一种情况的数学仿真:
静止状态初值的选择:经度120.234°,纬度从30.000°～40.000°,海拔高度为100～600 m,初速度为0,三个姿态偏差角均为0°～1°之间,加速度计零偏的时间常数为(200 s,200 s,300 s),陀螺零漂的时间常数为(100 s,150 s,200 s)。
运动状态处置的选择:此时载体的对地速度不为0,其值为(160 m/s,40 m/s,5 m/s),其余和静止状态的处置一致。
在静止条件下和运动条件下,采样频率均为100 Hz,系统经过离散后导出可观性矩阵,据此来分析和判断系统的一致可观性。这里选择两种方法来比对,一种是通过可观性矩阵的秩来比对,另一种是选择可观性矩阵的奇异值来比对。
基于第二种情况的数学仿真:
初值的选择同第一种情况。惟一不同的是测量矩阵有所改变。采样频率仍设定为100 Hz,系统经过离散后导出可观性矩阵,据此来分析和判断系统的一致可观性。在此仍然采用可观性矩阵的秩和奇异值来比对。
仿真结论如下:
(1)基于扩展卡尔曼滤波的数据融合方案对GPS/SINS是适合的。
()对运动状态下的多种情形进行了仿真分析,结果表明:即使在运动条件下,一致可观性仍然不可能实时保证,因为可观性矩阵中的元素受运动状态的影响很明显。
(3)关于系统模型阶次优化,通过仿真得出的结论是,阶次高不见得估计效果好,而且计算量较大。合适的阶次选择应以实际测试验证结果为依据。
5 结语
本文通过选定的惯性传感器和GPS接收机组成的组合导航系统的仿真,可以得出如下结论:低成本组合导航系统在适当的性能要求下是可以工程实现的;低成本组合导航系统在进行数据融合时存在滤波器阶次的选择问题和滤波法散问题,针对这些问题,本文的研究结果可以作为参考;为了更进一步提高数据融合滤波器的稳定性,有必要利用无味卡尔曼滤波器,下一步工作将重点考虑无味卡尔曼滤波中的两个估计参数的优化选择对滤波性能的影响。
摘要：该低成本组合导航系统由基于MEMS器件的惯性导航系统和GPS组成。针对该系统,基于卡尔曼滤波的数据融合算法,提出了解决和分析系统状态的可观性问题、滤波器的阶次选择问题的方法,并进行了数学仿真,结果表明提出的思路和方法是可行的,具有工程参考价值。
关键词：低成本,组合导航,数据融合,可观性
参考文献
[1]蔡春龙,刘翼,刘一薇.MEMS惯性仪表组合导航系统的发展现状与趋势[J].中国惯性技术学报,2009,17(5):562-567.
[2]祝彬,郑娟.美国惯性导航与制导技术的新进展[J].中国航天,2008(1):43-45.
[3]秦永元.惯性导航[M].北京:科学出版社,2006.
[4]乔国栋,倪茂林,李铁寿.基于能观度分析的信息融合自主导航算法[J].宇航学报,2008,29(3):883-888.
[5]刘智平,邵小兵.基于Matlab的捷联惯导的仿真系统研究[J].现代电子技术,2010,33(12):78-80,84.
[6]SIMON D.Optimal state estimation[M].[S.l.]:JohnWiley&Sons Inc.,2006.
[7]IHNSOEK R,MAMOUN F A,SPEYER J L.Observabili-ty of integrated GPS/INS during maneuvers[J].IEEETransactions on Aerospace and Electronic Systems,2004,40(2):526-534.
[8]CRASSIDIS J L.Sigma point Kalman filtering for integrat-ed GPS and inertial navigation[J].IEEE Transactions onAerospace and Electronic Systems,2006,42(2):750-756.
[9]陈永冰,钟斌.惯性导航原理[M].北京:国防工业出版社,2007.
基于组合相似度的优化协同过滤算法 篇8
关键词：推荐系统,协同过滤,组合相似度
0 引言
随着电子商务的快速发展, 信息过载现象越来越严重, 大量的商品信息增加了客户购买所需物品的难度, 消费者很难快速且有效地做出决策。为了让顾客在购买产品时尽可能少地浏览无关信息, 解决信息过载问题, 个性化推荐技术应运而生[1,2,3,4,5]。协同过滤是目前电子商务推荐系统中应用最广泛的推荐算法之一, 其核心思想是基于目标用户的邻居用户的资料来获得目标用户的推荐, 首先在用户群中找到指定用户的邻居 (兴趣) 用户, 然后根据邻居用户的评分预测目标用户对商品项的评分值, 选择评分项最高的前N项商品反馈给目标用户。协同过滤技术的最大优点在于能够处理非结构化的复杂对象, 但随着用户数量和项目数量的增加, 协同过滤面临着稀疏性、冷启动、可扩展性和算法健壮性等问题。围绕这些研究课题, 许多学者进行了深入研究并取得了一系列出色的研究成果[6,7,8,9,10,11,12,13,14,15]。
在电子商务系统中, 由于用户评价过的项目占全体项目数量的比例很小, 导致评分数据极为稀疏, 因此计算用户最近邻居不准确, 降低了推荐质量。因此, 数据稀疏性的问题是协同过滤系统中的一个主要挑战。为解决数据稀疏性问题, 一些学者在传统相似性度量方法的基础上提出了新的相似性计算方法。如Hyung[10]综合考虑了邻近性、影响性和偏好性三个参数, 提出了一种探索式的PIP相关度计算方法, PIP算法在解决冷启动问题时表现出了优于传统方法的性能。Buhwan[11]等提出了一种基于迭代消息传递过程的相似度改进算法。Anand等[12]利用局部和全局的相似度组合来解决数据稀疏导致的相似度精确问题, 认为数据极度稀疏时全局相似度优于局部相似度。邓爱林等[6]针对用户评分数据极端稀疏的情况, 提出了一种基于项目评分预测的协同过滤推荐算法, 采用了一种新的相似度计算方法。周军锋等[13]在引入项目评分预测的基础上, 采用修正的条件概率方法计算项目相似度。邢春晓[14]等针对协同过滤算法不能及时反映用户兴趣变化的问题, 提出两种改进度量:基于时间的数据权重和基于资源相似度的数据权重。徐翔[15]等针对3类填充方法构建的评分数据集, 分析传统相似度和基于云模型的相似度, 为各填充方法选取最有效的相似度优化方案。沈键[16]等提出了一种基于二阶段相似度学习的协同过滤推荐算法, 一定程度上解决了评分矩阵中大部分元素缺失问题。
本文针对数据稀疏导致计算相似度准确度问题展开研究, 充分考虑用户之间在项目集上评分的集合数等结构信息, 将传统相似度与结构相似度相结合, 提出了6种不同的组合相似度计算方法。在Movie Lens公开数据集上的实验结果表明, 本文提出的组合相似度与传统相似度相比, 可以获得更好的推荐质量。
1 协同过滤算法概述
在一个基于协同过滤算法的推荐系统中, 输入数据为用户评分矩阵, 记作R (m, n) , 如表1所示。该评分矩阵记载了用户对项目的主观评分, 要么由用户显示确定, 要么由系统隐式推断得出。一旦了确定了评分矩阵, 推荐系统就能够做出用户对未评分项目的预测评分, 从而产生推荐。
协同过滤算法的第一步是根据用户对项目的评分矩阵计算用户之间的相似度。用户u和v之间的相似度记为sim (u, v) 。设Rui、Rvi分别表示用户u、v对i的评分。用户u、v在项目集I上共同评分的项目集为Iuv={i∈I|Rui≠0∩Rvi≠0} (I为全部项目集) 。通常, 计算两个用户之间的相似度主要有3种方法:余弦相似性、修正余弦相似性、Pearson相关相似性[9]。
余弦相似性CC (Cosine Correlation) :用户对n个项目的评分可视为n维向量, 用户u和用户v的相似性即为相应两个n维向量的夹角余弦:
用余弦相似性计算相似度, 计算速度较快, 实现起来简单。但是, 这种度量方法未考虑用户评分尺度的问题, 计算出的邻居数据不够准确。
修正余弦相似性ACC (Adjusted Cosine Correlation) :修正余弦相似性考虑了用户的评分尺度问题, 可由如下公式定义:
其中表示用户u的平均评分表示用户v的平均评分。修正余弦考虑用户的平均评分, 可以较好地保证寻找邻居的准确性。
Pearson相关相似性PC (Pearson Correlation) :在这类方法中, 通过计算两个用户的Pearson相关系数来确定它们之间的相似性。Pearson相关相似性可由如下公式计算得到:
其中表示用户u的平均评分表示用户v的平均评分。
协同过滤算法的第二步是根据计算得到的相似度, 找到当前用户的最近邻居并产生预测值。对目标用户u而言, 在整个评分矩阵空间中搜索出m个相似度最高的用户即可以组成其最近邻居集合V={v1, v2, …, vm}。
最后根据当前用户m个最近邻居对项目的评分信息预测当前用户对其未评分项目的评分, 以此产生Top N推荐。用户u对未评分项目i的预测评分Pui可以通过用户u的最近邻居集合S (u) (即V) 对i的评分得到, 计算方法如下:
2 基于组合相似度的优化协同过滤算法
2.1 结构相似度
第1节给出的3种相似度依赖用户的评分数值计算来实现, 用户的相似度也蕴含在用户标签和内容信息中, 但是用户的信息难以收集。为此, 还可同时考虑用户或项之间的结构相似度[17,18]。结构相似度只考虑用户之间在项目集上评分的集合数和项目被用户评分的集合数, 而不需考虑具体的评分数值。
Jaccard系数, 又称为Jaccard相关性系数[19], 用来比较样本集中的相似性和分散性的一个概率, 其值等于样本交集与样本集并集的比值。给定用户u和用户v, 中N (u) 表示用户u的评分项集合, N (v) 表示用户v的评分项集合。可通过如下公式计算用户u和v的兴趣相似度:
Salton系数是由Salton和Mc Gill提出的表征两个邻域之间关系程度的标准化系数[20]。Salton系数的计算公式如下:
其中N (u) 表示用户u的评分项集合, N (v) 表示用户v的评分项集合。
John S.Breese在论文中提出了IUF (Inverse User Frequence) , 即用户活跃度对数的倒数的参数[21]。他认为活跃用户对相似度的贡献应该小于不活跃的用户, 具体可由如下公式计算用户的兴趣相似度:
其中, N (i) 表示项目i所有用户评分的集合。可以看到, 该公式通过惩罚了用户u和用户v共同兴趣列表中热门物品对他们相似度的影响。
2.2 组合相似度
通常情况下, 在大量的项目中, 用户只会对极少数项目进行评分, 从而造成大部分评分数据缺失的问题。利用传统相似度计算方法来度量用户的相似性时, 可能会出现这样的情况:两个用户共同评分的项目个数很少, 但是由于他们的评分非常接近, 因此计算的相似性很高。实际上这种情况可能会高估用户的相似性, 因为如果两个用户同时感兴趣的项目个数很少, 那么他们的兴趣爱好可能很不相似。所以, 在选择共同评分数据的前提下, 还要考虑共同评分的项目个数, 这样才能更准确地表示用户兴趣爱好的相似程度。为此, 本文将传统相似度与结构相似度 (Salton系数、Jaccard系数和IUF系数) 进行组合, 以期能更好地度量用户之间的相似性。
组合相似度就是将传统的基于分值的相似度和结构相似度进行线性组合。为了平衡传统基于分值的相似度和结构相似度, 我们引入平衡参数α (取值范围为[0, 1]) , 用以反映结构相似度对组合相似度的贡献。设传统基于分值的相似度为S1, 结构相似度为S2, 则组合相似度为S= (1-α) S1+αS2。本文采用的6种组合相似度定义如下:
其中ACCJ、ACCS、ACCIUF为调整余弦相似度和Salton系数、Jaccard系数、IUF系数相组合得到的组合相似度计算公式, PCJ、PCS和PCIUF为Pearson相似度与Salton系数、Jaccard系数、IUF系数相组合得到的组合相似度计算公式。
2.3 算法步骤
基于式 (8) -式 (13) 给出的六种组合相似度的优化协同过滤算法的主要步骤如下:
输入:评分矩阵R;
输出:预测矩阵Rpre。
(1) 在原始稀疏矩阵R上计算基于分值的用户的相似度矩阵, 得到用户调整余弦相似度系数ACC和Pearson系数PC。
(2) 在原始稀疏矩阵R上分别计算用户之间的结构相似度Salton系数、Jaccard系数和IUF系数, 分别得到用户Salton系数、Jaccard系数和IUF系数。
(3) 将基于分值的用户相似度矩阵和结构相似度矩阵利用平衡参数组合得到组合相似度ACCJ, ACCS, ACCIUF, PCJ, PCS, PCIUF。
(4) 使用组合相似度, 产生m个最近邻居, 使用式 (4) 计算用户u对未评分项i的预测评分, 得到预测矩阵Rpre。
在Movie Lens数据集上进行实验, 根据输出的预测矩阵Rpre, 采用相关的评测指标进行度量。
3 实验结果和分析
本节首先介绍实现算法所采用的数据集和度量标准, 然后在该数据集上进行MAE、RMSE、准确率、覆盖率、召回率等指标的度量。
3.1 数据集和度量标准
本实验使用目前常用的Movie Lens数据集作为测试数据, 该数据集由美国Minnesota大学的Group Lens研究小组提供ML100k数据集, 该数据集包含了943个用户对1682部电影在连续7个月内的评分数据, 其中每个用户至少对20部电影进行了评分。实验需要将整个数据集划分为训练集和测试集, 本实验对ML100k提供的10万条评分数据, 随机选取其中80%用作训练集, 另外20%用作测试集, 数据集的稀疏等级 (未知评分在整个数据集所占的比例) 为:1-100 000/943×1682=93.7%。
评分预测的预测准确度一般通过均方根误差 (RMSE) 和平均绝对误差 (MAE) 计算, 均方根误差和平均绝对偏差越小, 预测的准确度越高。对于测试集中的一个用户u和物品i, 令rui是用户u对物品i的实际评分, 而pui是推荐算法给出的预测评分, 那么RMSE的定义为:
MAE采用绝对值计算预测误差, 它的定义为:
网站在通过推荐服务时, 一般返回给用户一个推荐列表, 这种推荐叫做Top N推荐。Top N推荐的预测准确率一般通过准确率 (Precision) 、召回率 (Recall) 和覆盖率 (Coverage) 度量。
假设系统的用户的集合为U, 令R (u) 是根据用户u在训练集上的行为给用户做出的推荐列表, 而T (u) 是用户u在测试集上的行为列表, I为总物品集合。那么, 推荐结果的召回率定义为:
推荐结果的准确率定义为:
覆盖率 (Coverage) 描述的是一个推荐系统对物品长尾的发掘能力。覆盖率有不同的定义方法, 最简单的定义为推荐系统能够推荐出来的物品占总物品集合的比例。假设系统的用户的集合为U, 推荐系统给每个用户推荐一个长度为N的物品列表R (u) 。那么推荐系统的覆盖率可以通过下面的公式计算:
3.2 实验结果和分析
首先, 以平均绝对偏差MAE和均方根误差RMSE最小化为目标确定出组合相似度式 (8) -式 (13) 中的参数α。其次, 将基于6种组合相似度的优化协同过滤算法与传统算法在MAE和RMSE上进行比较。最后采用Top N实验, 在召回率、准确率和覆盖率三个指标上对基于组合相似度式 (8) -式 (10) 的优化算法与传统算法进行了比较。
(1) 确定平衡参数α值
为了得到最优组合相似度S= (1-α) S1+αS2, 首先应得到最优的组合平衡参数α。我们将α从0开始每递增0.1直到1为止, 利用用户-项目评分矩阵, 分别计算调整余弦组合相似度 (ACCJ, ACC, ACCIUF) 及Pearson组合相似度 (PCJ, PCS, PCI-UF) 对应算法的预测精度MAE, RMSE值。实验结果如图1-图4所示。
在图1-图4中, 横轴表示平衡参数α, 纵轴分别为平均绝对偏差MAE和均方根误差RMSE。曲线ACCJ、ACCS、ACCIUF分别代表传统基于分值的调整余弦相似度与Jaccard系数、Salton系数和IUF系数组合的相似度算法。曲线PCJ、PCS、PCIUF分别代表传统基于分值的Pearson相似度和Jaccard系数、Salton系数和IUF系数组合的相似度算法。
对于调整余弦 (ACC) 的组合相似度, 从图1中可以看出:当平衡参数α=0.5时, ACCJ对应的MAE最小;α=0.6时, ACCS对应的MAE最小;α=0.9时, ACCIUF对应的MAE最小。图2中可以得出:当平衡参数α=0.7时, ACCJ对应的RMSE最小;α=0.6时对应的RMSE最小;α=0.9时, ACCIUF对应的RMSE达到最小。对于Pearson (PC) 的组合相似度, 从图3、图4中可以看出:当平衡参数α=0.9时, PCJ对应的MAE和RMSE最小;α=0.8时, PCS对应的MAE和RMSE最小;α=1时, ACCIUF对应的MAE和RMSE最小 (注:当α=1或者α=0时, 组合相似度其实就是对应的结构相似度或传统基于分值的相似度) 。
通过前面的实验我们得到:在以平均绝对偏差MAE为指标的测量中, 当α=0.5时, ACCJ组合相似度0.5-ACCJ最优。在以均方根误差RMSE为指标的测量中, 当α=0.7时, ACCJ组合相似度0.7-ACCJ最优。同理, 根据最优平衡参数α得到调整余弦组合相似度和Pearson组合相似度的最优情况。在以平均绝对偏差MAE为指标的测量中, 调整余弦组合相似度最优情况为0.5-ACCJ, 0.6-ACCS, 0.9-ACCIUF;Pearson组合相似度最优情况为0.9-PCJ, 0.8-PCS, 1-PCIUF。同理, 得到在以均方根误差RMSE为指标的测量中的最优组合相似度。
(2) 算法MAE和RMSE的比较
得到了最优平衡参数α后, 我们将基于组合相似度式 (8) -式 (13) 的优化协同过滤算法与基于调整余弦相似度 (ACC) 和Pearson相似度 (PC) 的传统协同算法进行对比, 结果如图5-图8所示。
在图5-图8中, 横轴为取用户最近邻的个数K, 纵轴分别为平均绝对偏差MAE和均方根误差RMSE, 曲线ACC代表基于调整余弦相似度的协同过滤算法, 而曲线α-ACCJ、α-ACCS和α-ACCIUF分别对应三种组合相似度的算法。曲线PC代表基于Pearson系数的协同过滤算法, 而曲线α-PCJ、α-PCS和α-PCIUF分别对应三种组合相似度的算法。图5-图8显示, α-ACCJ、α-ACCS和α-ACCIUF曲线的MAE、RMSE值明显低于ACC曲线, α-PCJ、α-PCS和α-PCIUF曲线的MAE、RMSE值也明显低于PC曲线。实验结果表明, 选取合适的平衡参数α, 基于组合相似度的协同过滤算法的推荐性能与传统算法相比, 都有较显著的提高, 能够较好地改善推荐精度。
(3) 召回率、准确率和覆盖率的比较
在接下来的Top N实验中, 我们选择基于调整余弦的组合相似度 (0.5-ACC, 0.6-ACCS, 0.9-ACCIUF) 算法与传统的基于ACC相似度算法在召回率、准确率、覆盖率等指标上进行比较。同样我们选择基于Pearson的组合相似度 (0.9-PCJ, 0.8-PCS, 1-PCIUF) 算法与传统基于PC相似度算法在召回率、准确率、覆盖率等指标上进行比较。实验结果如图9-图14所示。
在图9-图14中, 横轴代表推荐列表长度N, 纵轴分别为召回率、准确率和覆盖率。图9-图11中, 每个N值对应的三条柱状图从左往右依次是ACC (传统基于分值的调整余弦相似度) 、0.5-ACCJ (基于Jaccard系数平衡参数为0.5的组合相似度) 、0.6-ACCS (基于Salton系数平衡参数为0.6的组合相似度) 和0.9-ACCIUF (基于IUF系数平衡参数为0.9的组合相似度) 。图12-14中每个N值对应的三条柱状图从左往右依次是PC (传统基于分值的Pearson相似度) 、0.9-PCJ (基于Jaccard系数平衡参数为0.9的组合相似度) 、0.8-PCS (基于Salton系数平衡参数为0.8的组合相似度) 和1-PCIUF (基于IUF系数平衡参数为1的组合相似度) 。
由图可以看出, 在每一个推荐列表长度N上, 选择合适平衡参数的基于组合相似度的优化协同过滤算法的召回率、准确率和覆盖率都要高于传统基于分值的协同过滤算法, 能够有效地改善推荐质量。
4 结语