南京大学学报(自然科学版) ›› 2020, Vol. 56 ›› Issue (1): 74–84.doi: 10.13232/j.cnki.jnju.2020.01.009

• • 上一篇    下一篇

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

信统昌,刘兆伟()   

  1. 烟台大学计算机与控制工程学院，烟台，264005
  • 收稿日期:2019-08-20 出版日期:2020-01-30 发布日期:2020-01-10
  • 通讯作者: 刘兆伟 E-mail:lzw@ytu.edu.cn
  • 基金资助:
    山东省重点研发计划(2015GSF115009);国家自然科学基金(61403328)

Learning of multi⁃valued acyclic CP⁃nets based on Bayesian⁃genetic method

Tongchang Xin,Zhaowei Liu()   

  1. School of Computer and Control Engineering，Yantai University，Yantai，264005，China
  • Received:2019-08-20 Online:2020-01-30 Published:2020-01-10
  • Contact: Zhaowei Liu E-mail:lzw@ytu.edu.cn

RichHTML

8

PDF (PC)

1028

摘要：

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

关键词: 多值属性, 贝叶斯方法, 遗传算法, 无 环, CP?nets

Abstract:

Conditional preference network （CP?net） is a graph model describing conditional preferences among attributes. Multi?valued acyclic CP?nets learning is an important research direction. Different from the traditional CP?nets learning method，a multi?valued acyclic CP?nets learning method based on Bayesian method and genetic algorithm is proposed. In preference processing，the complete partial order relationship of multi?valued attributes is used as conditional preferences to determine the correlation relationship. This method uses single parent attribute to deduce the relativity under multi?parent attributes and to learn CP?nets structure. Genetic algorithm is used to search in the search space of CP?nets structure to find the optimal structure. Delink algorithm is used to de?loop and complete acyclic CP?nets learning. The validity of the algorithm is validated on sushi data set. The experimental results show that the algorithm based on Bayesian?genetic algorithm is effective. CP?nets learning algorithm can obtain local optimal acyclic CP?nets in limited time.

Key words: multi?valued attributes, Bayesian method, genetic algorithm, acyclic, CP?nets

中图分类号: 

  • TP181

图1

一种出行方式的CP?net"

表1

A条件下属性D的偏好对"

Value of X1Value of X2Preference Pair
a1d1d2a1d1?a1d2
a1d1d3a1d1?a1d3
a1d1d4a1d1?a1d4
a1d2d3a1d2?a1d3
a1d2d4a1d2?a1d4
a1d3d4a1d3?a1d4
a2d1d2a2d1?a2d2
a2d1d3a2d1?a2d3
a2d1d4a2d1?a2d4
a2d2d3a2d2?a2d3
a2d2d4a2d2?a2d4
a2d3d4a2d3?a2d4

表2

A条件下属性D的偏好关系"

Value of X1Preference Relationship
a1a1d4?a1d3?a1d1?a1d2
a2a1d4?a1d3?a1d2?a1d1

图2

CP?nets及其结构矩阵"

图3

交叉算法"

图4

有环结构及其入度值"

图5

无环CP?nets"

表3

不同属性个数下的结构正确性"

VCorrect
60.9453
80.8915
100.8590

图6

不同数据大小下的相似度"

图7

不同属性个数下CP?nets学习时间"

图8

不同偏好数据库与数据大小下的相似度"

图9

不同噪声水平下的相似度"

表4

贝叶斯?遗传CP?nets学习算法与其他算法的比较"

实验方法噪声处理父属性结构环路
Dimopouols不可处理1有环
卡方检验可处理1有环
G方检验可处理2|V|-1有环
贝叶斯?遗传方法可处理n|V|-1无环
1 Banawan K，Ulukus S. Multi?message private information retrieval：capacity results and near?optimal schemes. IEEE Transactions on Information Theory，2018，64(10)：6842-6862.
2 Li L Y，Xu Q L，Gan T，et al. A probabilistic model of social working memory for information retrieval in social interactions. IEEE Transactions on Cybernetics，2018，48(5)：1540-1552.
3 Chung H，Kogelmann B. Diversity and rights：a social choice?theoretic analysis of the possibility of public reason. Synthese，2018，doi：0.1007/s11229?018?1737?4.
doi: 0.1007/s11229?018?1737?4
4 Han D，Li J Q，LI W T，et al. An app usage recommender system：improving prediction accuracy for both warm and cold start users. Multimedia Systems，2019，doi：10.1007/s00530?018?0601?1.
doi: 10.1007/s00530?018?0601?1
5 Lu H，Su S，Tian Z H，et al. A novel search engine for internet of everything based on dynamic prediction. China Communications，2019，16(3)：42-52.
6 Lui R，Au C H. I. S. educational game：adoption in teaching search engine optimization (SEO). Journal of Computer Information Systems，2018，doi：10.1080/08874417.2018.1461034.
doi: 10.1080/08874417.2018.1461034
7 辛冠琳，刘惊雷. 基于精确P值计算学习无环CP?nets. 南京大学学报(自然科学)，2017，53(3)：450-461.
Xin G L，Liu J LLearning acyclic CP?nets based on exact P?value computation. Journal of Nanjing University (Natural Science)，2017，53(3)：450-461.
8 辛冠琳，刘惊雷. 基于G方检验的CP?nets学习. 南京大学学报(自然科学)，2015，51(4)：781-795.
Xin G L，Liu J LLearning CP?nets based on G2 test. Journal of Nanjing University (Natural Science)，2015，51(4)：781-795.
9 刘兆伟，仲兆琳，王磊等. 机器人的CP?nets优化类人轨迹规划. 控制理论与应用，2018，35(12)：1772-1778.
Liu Z W，Zhong Z L，Wang L，et al. Optimal human?like trajectory planning of CP?nets for robot. Control Theory and Application，2018，35(12)：1772-1778.
10 刘兆伟. 基于偏好数据库的无环CP?nets结构学习方法研究. 博士学位论文. 泰安：山东大学，2018.
Liu Z W.R Research on structure learning methods of acyclic CP?nets based on preference database. Ph.D Dissertation. Taian：Shandong University，2018.
11 刘惊雷，廖士中. CP?nets学习的复杂度. 计算机科学，2018，45(6)：211-215.
Liu J L，Liao S ZComplexity of CP?nets learning. Computer Science，2018，45(6)：211-215.
12 辛冠琳，刘惊雷. 从偏好数据库中挖掘Ceteris Paribus偏好. 计算机应用，2016，36(8)：2092-2098，2108.
Xin G L，Liu J LMining ceteris paribus preference from preference database. Journal of Computer Application，2016，36(8)：2092-2098，2108.
13 De Amo S，Bueno M L P，Alves G，et al. CPrefMiner：An algorithm for mining user contextual preferences based on Bayesian networks∥IEEE International Conference on Tools with Artificial Intelligence. Athens，Greece：IEEE Computer Society，2012：114-121.
14 刘惊雷. CP?nets及其表达能力研究. 自动化学报，2011，37(3)：290-302.
Liu J LCP?nets and its expressive ability research. Acta automatica sinica，2011，37(3)：290-302.
15 Gao X G，Yang Y，Guo Z G，et al. Bayesian approach to learn Bayesian networks using data and constraints∥Proceedings of the 23rd International Conference on Pattern Recognition. Cancun，Mexico：IEEE，2017：3667-3672.
16 Foley B R，Marjoram P. Sure enough：efficient Bayesian learning and choice. Animal Cognition，2017，20(5)：867-880.
17 Kordestani M，Samadi M F，Saif M，et al. A new fault prognosis of MFS system using integrated extended Kalman filter and Bayesian method. IEEE Transactions on Industrial Informatics，2015，doi：10.1109/TII.2018.2815036.
doi: 10.1109/TII.2018.2815036
18 Larranaga P，Kuijper C M H，Murga R H，et al. Learning bayesian network structures by searching for the best ordering with genetic algorithms. IEEE Transactions on Systems，Man，and Cybernetics?Part A：Systems and Humans，1996，26(4)：487-493.
19 Contaldi C，Vafaee F，Nelson P C. Bayesian network hybrid learning using an elite?guided genetic algorithm. Artificial Intelligence Review，2019，52(1)：245-272.
20 Li T Z，Li Y X，Yang X L. Rock burst prediction based on genetic algorithms and extreme learning machine. Journal of Central South University，2017，24(9)：2105-2113.
21 Dimopoulos Y，Michael L，Athienitou F. Ceteris Paribus preference elicitation with predictive guarantees∥Proceedings of the 21st International Joint Conference on Artifical Intelligence. Pasadena，CA，USA：Morgan Kaufmann Publishers Inc，2009：1890-1895.
22 Liu J T，Yao Z J，Xiong Y，et al. Learning conditional preference network from noisy samples using hypothesis testing. Knowledge?Based Systems，2013，40：7-16.
[1] 王卫星,刘兆伟,石敬华. 基于时间敏感滑动窗口的CP⁃nets结构学习[J]. 南京大学学报(自然科学版), 2020, 56(2): 175-185.
[2] 张玉州,张子为,江克勤. 多跑道进离港地面等待问题建模及协同优化[J]. 南京大学学报(自然科学版), 2020, 56(1): 132-141.
[3] 李二超，马玉泉. 基于就近取值策略的离散多目标优化[J]. 南京大学学报(自然科学版), 2018, 54(6): 1216-1224.
[4] 吴家豪1，彭志平2*，崔得龙2，李启锐2，何杰光2. 基于多Agent系统的粒子群遗传优化云工作流调度算法[J]. 南京大学学报(自然科学版), 2017, 53(6): 1114-.
[5]  倪玲玲，王　栋*，王远坤，陶雨薇，王艳磊.  基于贝叶斯方法的太湖沉积物多环芳烃的生态风险评价[J]. 南京大学学报(自然科学版), 2017, 53(5): 871-.
[6]  骆乾坤1，吴剑锋2*，杨　运2，3，吴吉春2，马淑芬4.  基于DREAM算法的含水层渗透系数空间变异特征识别[J]. 南京大学学报(自然科学版), 2016, 52(3): 448-455.
[7]  杨　蕴1，朱　琳2*，林　锦3，王锦国1.  考虑地面沉降约束的地下水模拟优化管理模型[J]. 南京大学学报(自然科学版), 2016, 52(3): 470-478.
[8] 周 涛1,2，陆惠玲1*，张艳宁2，马 苗2,3. 基于Rough Set的高维特征选择混合遗传算法研究[J]. 南京大学学报(自然科学版), 2015, 51(4): 880-893.
[9] 骆乾坤*，吴剑锋2，杨运3，钱家忠1. 渗透系数空间变异程度对进化算法优化结果影响评价[J]. 南京大学学报(自然科学版), 2015, 51(1): 60-66.
[10] 程春玲;李阳;张登银;. 基于遗传算法的层次化云资源监测方法[J]. 南京大学学报(自然科学版), 2013, 49(4): 491-499.
[11]  Markushev Dragan1，Rabasovic Mihailo1，Lukic Mladena2
Cojbasic Zarko3，Todorovic Dragan4
.  实时脉冲光声法用于分子弛豫时间的测定[J]. 南京大学学报(自然科学版), 2013, 49(1): 5-12.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1]  于文1，倪培1**，王国光1，商力1，江来利2，王波华3，张怀东3
.  安徽金寨县沙坪沟
斑岩钥矿床成矿流体演化特征*[J]. 南京大学学报(自然科学版), 2012, 48(3): 240 -255 .
[2] 李丽*，张宇昂，傅玉祥，潘红兵，韩峰. 三维众核片上处理器存储架构研究[J]. 南京大学学报(自然科学版), 2014, 50(3): 330 .
[3]  王　彪1，2*，蒋亚立1，戴跃伟1.  基于l0范数的匹配场源定位方法[J]. 南京大学学报(自然科学版), 2017, 53(4): 675 .
[4] 张弘,申俊峰,董国臣,刘圣强,王冬丽,王伟清. 云南来利山锡矿锡石标型特征及其找矿意义[J]. 南京大学学报(自然科学版), 2019, 55(6): 888 -897 .
[5] 陈超逸,林耀进,唐莉,王晨曦. 基于邻域交互增益信息的多标记流特征选择算法[J]. 南京大学学报(自然科学版), 2020, 56(1): 30 -40 .

版权所有 © 2021 《南京大学学报(自然科学)》

地址：江苏省南京市鼓楼区汉口路22号，南京大学学报编辑部，210093

电话：025-83592704 , 传真：025-83592704        技术支持：北京玛格泰克科技发展有限公司