CP-nets的可满足性序列求解算法研究

CP-nets是一种简单、直观的图形化偏好表示工具,成为近几年人工智能的一个研究热点。然而对于CP-nets的基础性质——可满足性序列的研究却较少。通过构造CP-nets导出图,利用改进的图的深度优先遍历算法实现二值网的强占优测试,对强占优测试得到的可达矩阵进行分析,得出任意结构CP-nets的可满足性序列个数关系;给出了生成全部可满足性序列的算法;强化和扩充了CP-nets的基本概念,深化了CP-nets的基础理论研究。

CP-nets的可满足性及一致性研究

CP-nets是一种简单而又直观的图形化偏好表示工具,成为近几年人工智能的一个研究热点,然而对于CP-nets的可满足性和一致性等相关性质的研究还很欠缺.既没有给出严格的定义,也没有探讨不同性质之间的联系,没有一个求可满足性序列的通用算法.从研究CP-nets的可满足性和一致性的关系着手,得出了任意结构二值CP-nets的可满足性判定算法及可满足性序列生成算法.首先通过构造CP-nets导出图及其性质的研究,得出CP-nets的可满足性及一致性的相关定理.再把不同性质结合起来分析,给出CP-nets可满足性等价于一致性的结论,从而利用拓扑排序的思想实现了任意结构二值CP-nets的可满足性序列的生成.强化和扩充了Boutilier所提出的一些概念,深化了CP-nets的基础理论研究.

一种基于UML和CP-net集成描述的面向对象软件的交互测试方法

面向对象技术在软件工程中的推广使用,使得传统的测试技术和方法受到了极大的冲击.对面向对象技术所引入的消息传递、数据抽象、封装、继承、多态等新特点,传统的测试技术已经无法有效的进行测试.对面向对象软件的测试,测试策略或方法都需要出现相应的变革或更新.本文给出一种基于UML和CP-net集成描述的面向对象软件的类集成测试方法,重点在于测试不同的类方法之间的交互行为.这种方法首先用UML和CP-net集成描述用户需求,然后基于这个描述模型,按照基本路径覆盖的标准自动产生测试例.

CP-nets学习的复杂度

CP-nets是一种简单且直观的图形化偏好表示工具,其表示、推理和学习是3个基本问题。不同于基于统计学习理论的研究方法,文中基于逻辑理论来研究二值CP-nets的学习问题。首先,建立命题公式的可满足性和CPnets表示的偏好公式之间的联系,将CP-nets的学习问题转化为命题的推理问题。随后,给出两类具有特殊结构的CP-nets的学习问题的计算复杂度,其中最复杂的无环CP-nets上的学习问题是NP-complete,而最简单的集合结构CP-nets上的学习问题是P。这些结论给出了CP-nets(如链结构、有界树宽)学习问题复杂度的上下界。

CP-nets的定性偏好决策及一致性推理

CP-nets是一种简单而又直观的图形化偏好表示工具,特别适合描述不完全信息下的具有依赖关系的多属性定性偏好决策。首先通过构造CP-nets导出图及对其性质的研究,得出强占优测试本质上是导出图上顶点之间的可达性问题,从而利用图的深度优先遍历算法实现了二值网的强占优测试;然后分别从无环图、有环图的角度给出CP-nets一致性的相关定理和性质,提出了判断一致性的3种方法,使得CP-nets的一致性问题得到解决;强化和扩充了Boutilier所提出的一些概念,深化了CP-nets的基础理论研究。

一种基于CP-nets的医疗资源配置方法

为了合理地配置医疗资源并保证医疗的公平,该文从医疗资源合理化配置角度,提出了一种基于条件偏好网(Conditional preference networks,CP-nets)模型的医疗资源需求表示方式。考虑到医疗机构整体效益最高及其内部对资源的竞争因素,该文采用CP-nets的强占优测试以及改进的占优测试对需求信息进行预处理,得到能够作为资源分配依据的数据。在此基础上,提出了CP-nets模型下的医疗资源分配算法,采用了波达计数法和带权集合覆盖思想,拓展了CP-nets的应用范围。实验表明:当以社会总效益为目标时,该文中采用的带有占优策略的带权集合覆盖算法不仅具有最优的性能,而且能适应更大规模的数据。

基于表决策略的CP-Nets可满足性序列的聚合

条件偏好网(CP-Nets)的可满足性序列是由决策者的偏好信息得到的一个关于所有配置的排序表,其中偏好关系具有不完备性和传递性.主要分析借鉴传统的表决策略来实现CP-Nets的可满足性序列的聚合的可行性,介绍"少数服从多数"和"与位置相关"策略在CP-Nets的可满足性序列的聚合的具体实现并进行性能分析.实现传统表决系统的一个从完备到非完备的推广应用.

机器人的CP-nets优化类人轨迹规划（英文）

机器人移动轨迹按照人的手臂来模拟是提高机器人安全性和人机交互能力的有效方法;特别是针对机器人抓取路径不唯一的场合,类人行为对于人机系统表现更加自然.此前,通常利用Kinect等设备,基于人工神经网络和K近邻算法等智能算法对类人轨迹进行规划,但无法获得未采样过的最优轨迹.本文基于CP-nets采用偏好模型研究类人运动轨迹,然后将该模型应用于机器人控制,在没有采样的情况下,也可得到最优的类人轨迹.实验结果表明,基于CP-nets的类人规划轨迹具有较高的效率和舒适性,符合人的运动特征.

CP-nets及其表达能力研究

偏好处理是人工智能中的一个重要研究内容,它的4个研究热点是偏好的表示、提取、聚合和推理.条件偏好网(Conditional preference networks,CP-nets)是一种简单直观的偏好表示的图形工具,但很少有工作研究CP-nets的表达能力.本文研究CP-nets的表达能力,详细研究了CP-nets表达偏好的完备性,其上构造的运算复杂度以及适用的场合.首先给出了CP-nets模型上的几个运算,利用改进的Warshall算法求出了二值网的强占优测试在最坏情况下的复杂度为O(4n).其次通过构造CP-nets导出图及其性质的研究,得出CP-nets特别适合不完全信息下的多属性定性偏好决策.当需要处理更完全信息时,可借助于与Agent的交互来完成.虽然我们给出了CP-nets的强占优测试的理论解,但其理论上可解,实际上不可解.为了解决强占优测试的指数级复杂度问题,本文最后给出了一种带有软约束的满足问题(Soft constraint satisfactionproblem,SCSP)的求解方法.它把CP-nets中的定性运算转为约束半环中的定量运算,从而将指数级的复杂度转化为多项式的复杂度,间接提高了部分CP-nets的表达能力.本文所做的工作是对Boutilier和Bistarelli工作的改进和提高.

基于时间敏感滑动窗口的CP-nets结构学习

随着人工智能的发展,条件偏好网(Conditional Preference networks,CP-nets)的学习和表示被广泛研究.此前的研究工作主要集中于从静态数据库中挖掘用户的条件偏好,而在许多新兴应用中,数据通过互联网或传感器网络流动,偏好也会随之发生变化.将挖掘偏好的方法扩展到动态环境是一个挑战,遇到的问题主要包括对连续数据进行的快速处理、庞大的数据量以及有限的内存资源等.针对偏好数据流,提出一种基于时间敏感的滑动窗口模型来挖掘条件偏好关系和学习CP-nets结构的方法,该方法包括一个用来获取所有可能偏好关系的存储结构以及一个对偏好关系进行累积计数的数据结构,并提出基于时间敏感滑动窗口的条件偏好关系挖掘算法,根据输入的偏好数据流比较基本块与滑动窗口的大小对条件偏好关系进行插入和更新.实验结果表明,与其他学习CP-nets结构的方法相比,该方法所需的运行时间少,得到的CP-nets的结构更准确.

利用SCSP实现CP-nets的强占优测试

基于"从CP-nets向SCSP规约"的思想来实现CP-nets的强占优测试,实现了CP-nets中的定性判断向约束半环中的定量判断的转换.通过重新定义转换规则,修正了刘惊雷提出的方法中的错误,文中阐述了具体的实现方法.

基于启发式算法的CP-nets学习研究

CP-nets(条件偏好网)是定性表达偏好关系的一种图形工具,作为一种表达能力的工具,CP-nets功能强大,能直观、自然地表达用户的偏好信息。但是对于CP-nets学习的研究还不够深入,在实际应用中,由于用户行为或者观测误差的随机性,可能导致数据集中存在噪声数据,使得许多传统的学习方法无法得到最优的CP-nets结构。本文提出基于启发式算法的学习方法来解决CP-nets的结构学习问题。与传统方法中直接学习CP-nets结构不同,本文将CP-nets的结构学习问题转化为寻找最短路径问题,利用启发式算法的能力来寻找最优的CP-nets。

基于特征选择的CP-nets结构学习

作为描述多属性之间定性条件偏好的一种图模型,条件偏好网(Conditional Preference networks,CP-nets)的结构学习问题在CP-nets的研究中起着重要的作用.不同于传统的CP-nets学习方法,提出基于信息论和特征选择的方法来研究偏好数据库上的CP-nets的结构学习问题.首先建立了偏好数据库上的互信息和条件互信息的求解方法,并将互信息看作一个属性和它的可行父亲之间的相关性,条件互信息看作可行父亲集中属性之间的冗余性,从而构造出极大相关极小冗余(Maximal Relevance Minimal Redundancy,mRMR)的目标函数,同时指出,一个属性的父亲集是由属性之间冗余度小,但对孩子属性的偏好却影响极大的属性子集组成的.随后基于特征选择中的mRMR方法来实现CP-nets的结构学习,并设计相应的算法来完成从偏好数据中学习CP-nets的结构.最后在电影推荐数据集上验证了算法的有效性.研究结果表明,基于mRMR的特征选择方法可有效获取变量之间的因果关系,从而求取出每个属性的父亲集合,进而获得CP-nets的结构.

结合反向矩阵和频繁模式树方法的CP-nets结构学习

提出一种基于反向矩阵结构在数据流上挖掘条件偏好和学习CP-nets的方法。利用反向矩阵的事务布局,减少了扫描数据库的次数,并且通过随机访问,在不到一次完整扫描的情况下得到频繁的偏好项。此外,通过建立频繁模式树FP-Tree,减少了候选项的生成。实验结果表明,与其他学习CP-nets结构的方法相比,该方法可以较快获得准确的CP-nets,在大型事务数据库方面表现出良好的性能,减少了内存需求。

基于滑动窗口的CP-nets增量式学习研究

偏好信息挖掘是人工智能领域数据挖掘中一个重要的研究内容,近年来得到了广泛的研究.随着当前社会发展和数字数据的急剧增长,实时应用中的偏好数据是以数据流的形式快速生成。然而,挖掘偏好的动态特性越来越需要适应流式数据变化的解决方案。造成这种情况的主要原因是用户的偏好不是静态的,可以随着时间的推移发生变化,而传统的偏好求取方法大多集中应用在静态数据集中,不能高效地处理数据流。本文主要采用基于窗口的CP-nets增量式学习算法处理偏好数据流。该算法在合成数据集和真实数据集上的实验结果表明本文提出的算法能够根据用户的上下文偏好信息得到与传统学习算法大体一致的较准确的用户CP-nets模型,并且与传统算法比较,该算法的时间复杂度低,算法效率更高。

基于CP-nets的多议题对称依赖关系的研究

为了进一步丰富CP-nets对偏好语言的描述能力,提出了一种名为SDCP-nets的图形工具。该工具利用效用矩阵,刻画议题间的对称依赖关系,在SDCP-nets中,条件偏好关系的刻画使得择优选择和搜索最佳方案更加有效,对称依赖关系的描述又进一步确保了算法结果的准确性。形式化定义了SDCP-nets的结构、语义和一致性,给出了关于SDCP-nets的择优选择算法和最佳方案选择算法。实验结果表明,利用SDCP-nets来描述用户的偏好语言具有较高的准确度。

基于CP-net偏好的关系数据库的Top-k实现

CP-net是一种简单而又直观的图形化的偏好表示工具,能够被用来描述在那些相对严密的、直观的、结构化的条件偏好信息中隐含的定性偏好关系,尤其适合信息不完整情况下的属性间具有依赖关系的多属性定性偏好决策.Top-k查询旨在检索出满足用户需求的前k个结果,从而提高检索效率,为此致力于实现具有CP-net偏好的关系数据库的Top-k查询.首先,CP-net被诱导成多个表来表示和存储;其次,将传统的帕累托复合拓展到模型中,以此保持偏好之间的严格的偏序关系;最后,基于“格”框架(Lattice)理论,实现了基于CP-net偏好的关系数据库的Top-k查询.

一种从偏好数据库中学习CP-nets结构的并行算法

不同于传统的条件偏好网络(conditional preference networks,CP-nets)结构学习方法,本文提出一种基于MapReduce框架的相关系数并行算法。首先建立了偏好数据库上的相关系数评分函数,对候选父亲结构并行地进行“评分+搜索”,随后基于序空间搜索得到各节点的局部最优,继而得到全局最优。同时指出,一个属性的父亲集是由属性之间冗余度小且偏好影响大的属性集所构成。实验结果表明,所提出的相关系数算法不仅能够快速有效地获取变量之间的因果关系,而且能求取出每个属性的可行父亲集,得到CP-nets的拓扑结构。

基于贝叶斯-遗传算法的多值无环CP-nets学习

条件偏好网(Conditional Preference networks,CP⁃nets)是描述属性间条件偏好的图模型,多值无环CP⁃nets学习是重要的研究方向之一.区别于传统的CP⁃nets学习方法,提出基于贝叶斯方法和遗传算法的多值无环CP⁃nets学习.在偏好处理上以多值属性的完整偏序关系作为条件偏好,进行相关性关系判定.随后,基于贝叶斯方法,以单一父属性推出多父属性下的相关性关系,进行CP⁃nets结构学习.采用遗传算法在CP⁃nets结构搜索空间中进行搜索,求解最优结构.通过Delink算法进行去环,完成无环CP⁃nets学习.在寿司数据集上验证算法的有效性,实验结果表明,基于贝叶斯⁃遗传算法的CP⁃nets学习算法能够在有限时间内学习得到局部最优无环CP⁃nets.

基于Dandelion编码生成有界树宽CP-nets

针对条件偏好网络(CP-nets)图模型在进行推理运算时的高时间复杂度的问题,提出了一种基于Dandelion编码生成有界树宽的CP-nets(BTW-CP-nets Gen)算法。首先,通过Dandelion编码与树宽为k的树结构(ktree)之间的双向映射原理推导出Dandelion编码与k-tree之间的解码与编码算法,实现编码与树结构的一对一映射;其次,利用k-tree来约束CP-nets结构的树宽,并利用k-tree的特征树得到了CP-nets的有向无环图结构;最后,利用离散多值函数的双射计算出各CP-nets结构节点的条件偏好表,然后针对生成的有界树宽CP-nets进行占优查询检测。理论分析和实验数据表明,与Pruffer编码生成k-tree(Pruffer code)算法相比,BTW-CP-nets Gen算法的运行时间在生成简单结构和复杂结构时的下降幅度分别为21.1%和30.5%;而BTW-CP-nets Gen算法所生成的图模型在进行占优查询时的节点遍历比在简单结构和复杂结构上分别提高了18.48%和29.03%。BTW-CP-nets Gen算法在更短的时间内,占优查询时遍历的节点率更高。可见,BTW-CP-nets Gen算法在图模型的推理中能够有效提高算法效率。