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

doi:10.13232/j.cnki.jnju.2020.02.003

南京大学学报(自然科学版) ›› 2020, Vol. 56 ›› Issue (2): 175–185.doi: 10.13232/j.cnki.jnju.2020.02.003

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

王卫星¹,刘兆伟¹(),石敬华²

^1.烟台大学计算机与控制工程学院，烟台，264005
^2.山东省生态环境监测中心，济南，250101

收稿日期:2019-11-24 出版日期:2020-03-30 发布日期:2020-04-02
通讯作者: 刘兆伟 E-mail:lzw@ytu.edu.cn
基金资助:
国家自然科学基金(61403328);山东省重点研发计划(2015GSF115009)

Learning of CP⁃nets structure based on a time⁃sensitive sliding window

Weixing Wang¹,Zhaowei Liu¹(),Jinghua Shi²

^1.School of Computer and Control Engineering, Yantai University, Yantai, 264005, China
^2.Shandong Eco?environmental Monitoring Center, Ji'nan, 250101, China

Received:2019-11-24 Online:2020-03-30 Published:2020-04-02
Contact: Zhaowei Liu E-mail:lzw@ytu.edu.cn

摘要/Abstract

摘要：

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

关键词: CP?nets, 滑动窗口, 数据流, 频繁项集

Abstract:

With the development of artificial intelligence,the learning and representation of preference model CP?nets(Conditional Preference networks) has been widely studied. Previous researches mainly focused on mining users' conditional preferences from static databases. In many emerging applications,data is updated through the internet or sensor networks,and then preferences change. Extending the method of mining preferences to dynamic environments is a challenge,including fast processing of continuous data,huge amount of data and limited memory resources. For preference data streams,this paper proposes a time?sensitive sliding window model to mine conditional preference relations and learn the structure of CP?nets. This method includes a storage structure for obtaining all possible preference relationships and a data structure for cumulative counting of preference relationships. An algorithm for mining conditional preference relations based on time?sensitive sliding windows is proposed，comparing the size of the basic block and the sliding window according to the input preference data stream to insert and update the conditional preference relationship. The experimental results show that compared with other methods of learning CP?nets structure,this method needs less running time and gets more accurate structure of CP?nets.

Key words: CP?nets, sliding window, data stream, frequent itemsets

中图分类号:

TP181

王卫星,刘兆伟,石敬华. 基于时间敏感滑动窗口的CP⁃nets结构学习[J]. 南京大学学报(自然科学版), 2020, 56(2): 175–185.

Weixing Wang,Zhaowei Liu,Jinghua Shi. Learning of CP⁃nets structure based on a time⁃sensitive sliding window[J]. Journal of Nanjing University(Natural Sciences), 2020, 56(2): 175–185.

图/表 15

图1

表1

偏好事务流"

基本块	时间段	事务数量	偏好关系（计数）
B₁	09:00-09:59	27	$o 12 (11), o 43 (11), o 13 (20), o 15 (2)$
B₂	10:00-10:59	20	$o 12 (20), o 43 (20), o 15 (13), o 37 (13)$
B₃	11:00-11:59	27	$o 12 (19), o 43 (19), o 13 (8), o 15 (7), o 37 (7)$
B₄	12:00-12:59	23	$o 12 (10), o 43 (10), o 15 (3), o 65 (10), o 78 (10)$

表1

表2

扫描基本块B1之后TA，DT和PCP的更新结果"

TA	10.8	0	0
DT	B_ID	ID	$B c o u n t$
	1	1	11
	1	2	11
	1	3	20
*PCP*	(1, $o 12$ ,11,0) (2, $o 43$ ,11,0) (3, $o 13$ ,20,0)

表2

表3

扫描基本块B2之后TA，DT和PCP的更新结果"

TA	8	10.8	0
DT	B_ID	ID	$B c o u n t$
	1	1	11
	1	2	11
	1	3	20
	2	1	20
	2	2	20
	2	3	0
	2	4	13
	2	5	13
*PCP*	(1, $o 12$ ,31,0) (2, $o 43$ ,31,0) (3, $o 13$ ,20,0) (4, $o 15$ ,13,10) (5, $o 37$ ,13,10)

表3

表4

扫描基本块B3之后TA，DT和PCP的更新结果"

TA	10.8	8	10.8
DT	B_ID	ID	$B c o u n t$
	1	1	11
	1	2	11
	1	3	20
	2	1	20
	2	2	20
	2	3	0
	2	4	13
	2	5	13
	3	1	19
	3	2	19
	3	3	7
	3	4	7
	1	1	11
*PCP*	(1， $o 12$ ，50，0) (2， $o 43$ ，50，0) (3， $o 15$ ，20，10) (4， $o 37$ ，20，10)

表4

表5

扫描基本块B4之后TA，DT和PCP的更新结果"

TA	9.2	10.8	8
DT	B_ID	ID	$B c o u n t$
	2	1	20
	2	2	20
	2	3	0
	2	4	13
	2	5	13
	3	1	19
	3	2	19
	3	3	7
	3	4	7
	4	1	10
	4	2	10
	4	3	10
	4	4	10
*PCP*	(1, $o 12$ ,49,0) (1, $o 43$ ,49,0) (3, $o 78$ ,10,29) (4, $o 65$ ,10,29)

表5

图2

图3

图4

图5

图6

图7

表6

表7

表8

参考文献 24

1	朱蔚林，木伟民，金宗泽等.基于MR的高可靠分布式数据流统计模型.计算机技术与发展，2018，28(1)：6-10，16.
	Zhu W L，Mu W M，Jin Z Z， et al. Statistical model of distrubuted data strem with high reliability based on MR. Computer Technology and Development，2018，28(1)：6-10，16.
2	徐石磊，魏星，江红等.分布式数据库系统中的并行分组聚合实现.华东师范大学学报(自然科学版)，2018(5)：56-66.
	Xu S L，Wei X，Jiang H，et al.Implementation of the parallel groupby and aggregation functions in a distributed database system. Journal of East China Normal University (Natural Science)，2018(5)：56-66.
3	崔凌云，刘春玲，魏荣华.大数据技术在船舶监控系统数据管理中的应用.舰船科学技术，2018，41(2A)：142-144.
	Cui L Y，Liu C L，Wei R H.Application of large data technology in data management of ship monitoring system. Ship Science and Technology，2018，41(2A)：142-144.
4	Lughofer E，Pratama M.Online active learning in data stream regression using uncertainty sampling based on evolving generalized fuzzy models.IEEE Transactions on Fuzzy Systems，2018，26(1)：292-309.
5	Wu K H，Zhu Y Y，Quan L，et al.A distributed real?time data prediction framework for large?scale time?series data using stream processing.International Journal of Intelligent Computing and Cybernetics，2017，10(2)：145-165.
6	茹蓓，贺新征.高效的数据流完全频繁项集挖掘算法.计算机工程与设计，2017，38(10)：2759-2766.
	Ru B，He X Z.Efficient complete frequent itemsets mining algorithm of data stream. Computer Engineering and Design，2017，38(10)：2759-2766.
7	王玲，李树林，徐培培等.基于频繁项集树的时态关联规则挖掘算法.控制与决策，2018，33(4)：591-599. Wang L，Li S L，Xu P P，et al.Temporal association rules mining algorithm based on frequent item sets tree. Control and Decision，2018，33(4)：591-599.
8	Oulad?Naoui S，Cherroun H，Ziadi D.A formal series?based unification of the frequent itemset mining approaches.Knowledge and Information Systems，2017，53(2)：439-477.
9	Liu Z W，Zhong Z L，Zhang C H，et al.Learning CP?nets structure from preference data streams.IEEE Access，2018，6：56716-56726.
10	辛冠琳，刘惊雷.基于精确P值计算学习无环CP?nets.南京大学学报(自然科学)，2017，53(3)：450-461.Xin G L，Liu J L. Learning acyclic CP?nets based on exact P?value computation. Journal of Nanjing University (Natural Science)，2017，53(3)：450-461.
11	刘惊雷，廖士中.CP?nets学习的复杂度.计算机科学，2018，45(6)：211-215.
	Liu J L，Liao S Z.Complexity of CP?nets learning. Computer Science，2018，45(6)：211-215.
12	郑金芳，张继栋，陈烽.基于模糊频繁模式的数据流关联规则挖掘方法.湘潭大学自科学报，2017，39(3)：122-126.
	Zheng J F，Zhang J D，Chen F. Mining method of data stream association rules based on fuzzy frequent mode. Natural Science Journal of Xiangtan University，2017，39(3)：122-126.
13	Demaine E D，López?Ortiz A，Munro J I.Frequency estimation of internet packet streams with limited space∥European Symposium on Algorithms.Springer Berlin Heidelberg，2002：348-360.
14	Karp R M，Shenker S，Papadimitriou C H.A simple algorithm for finding frequent elements in streams and bags.ACM Transactions on Database Systems，2003，28(1)：51-55.
15	Manku G S，Motwani R.Approximate frequency counts over data streams∥Proceedings of the 28^th International Conference on Very Large Data Bases.Hong Kong，China：ACM，2002：346-357.
16	Cohen E,Strauss M J.Maintaining time?decaying stream aggregates.Journal of Algorithms,2006,59(1)：19-36.
17	Deypir M，Sadreddini M H.A dynamic layout of sliding window for frequent itemset mining over data streams.Journal of Systems and Software，2012，85(3)：746-759.
18	Li H F,Zhang N,Zhu J M,et al.Frequent itemset mining over time?sensitive streams.Chinese Journal of Computers,2012,35(11)：2283.
19	Boutilier C，Brafman R I，Domshlak C，et al.CP?nets：a tool for representing and reasoning with conditional ceteris paribus preference statements.Journal of Artificial Intelligence Research，2004，21：135-191.
20	刘惊雷，刘兆伟，孙雪姣等.CP?nets的代数表示及其模型求取算法.模式识别与人工智能，2011，24(6)：725-732.
	Liu J L，Liu Z W，Sun X J，et al. Algebraic representation and model solving algorithm for CP?nets. Pattern Recognition and Artificial Intelligence，2011，24(6)：725-732.）
21	辛冠琳，刘惊雷.从偏好数据库中挖掘Ceteris Paribus偏好.计算机应用，2016，36(8)：2092-2098，2108.
	Xin G L，Liu J L.Mining ceteris paribus preference from preference database. Journal of Computer Applications，2016，36(8)：2092-2098，2108.
22	陈寅.基于FP?Growth算法的关联规则挖掘算法研究.无线互联科技，2017(19)：118-121，141.
	Chen Y. Study on association rule mining algorithm based on FP?Growth algorithm. Wireless Internet Technology，2017(19)：118-121，141.
23	Liu J T，Xiong Y，Wu C H，et al.Learning conditional preference networks from inconsistent examples.IEEE Transactions on Knowledge and Data Engineering，2014，26(2)：376-390.
24	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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

样本数量	卡方检验	G方检验	精确P值计算	本文算法
200	0.6856	0.7682	0.7791	0.7687
400	0.7675	0.8056	0.8203	0.8094
800	0.8692	0.8961	0.8892	0.9027
1600	0.8938	0.9247	0.9346	0.9637

样本数量	卡方检验	G方检验	精确P值计算	本文算法
200	0.6813	0.7346	0.7464	0.7492
400	0.7469	0.8134	0.8201	0.8086
800	0.8271	0.8968	0.8889	0.8993
1600	0.8568	0.9467	0.9334	0.9789

限定时间（s）	卡方检验	G方检验	精确P值计算	本文算法
0.5	0.5855	0.6283	0.6401	0.8432
1.5	0.7143	0.7568	0.7456	0.8978
3	0.7964	0.8849	0.8932	0.9454
6	0.8576	0.9213	0.9350	0.9350

[1]	信统昌,刘兆伟. 基于贝叶斯⁃遗传算法的多值无环CP⁃nets学习[J]. 南京大学学报(自然科学版), 2020, 56(1): 74-84.
[2]	张银芳,于洪,王国胤,谢永芳. 一种用于数据流自适应分类的主动学习方法[J]. 南京大学学报(自然科学版), 2020, 56(1): 67-73.
[3]	宋威,刘明渊,李晋宏. 基于事务型滑动窗口的数据流中高效用项集挖掘算法[J]. 南京大学学报(自然科学版), 2014, 50(4): 494-.
[4]	汤克明^1,2，戴彩艳¹，陈峻^3.4** . 一种基于滑动窗口的不确定数据流Top一K 查询算法* [J]. 南京大学学报(自然科学版), 2012, 48(3): 351-359.
[5]	据春华，帅朝谦*，封毅 . 基于粒计算的商业数据流概念漂移特征选择[J]. 南京大学学报(自然科学版), 2011, 47(4): 391-397.
[6]	赵飞, 刘奇志** , 张剡, 柏文阳 . 一种大域数据流中缺失值的填充方法* [J]. 南京大学学报(自然科学版), 2011, 47(1): 32-39.
[7]	卞磊 * , 刘超, 金茂忠 . 一种面向审查的过程内数据流异常自动检测方法 [J]. 南京大学学报(自然科学版), 2010, 46(1): 71-76.

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

Learning of CP⁃nets structure based on a time⁃sensitive sliding window

RichHTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 24

相关文章 7

Metrics

本文评价

推荐阅读 5