Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (1): 112-120.DOI: 10.11772/j.issn.1001-9081.2020060972

Special Issue: 第八届中国数据挖掘会议(CCDM 2020)

• China Conference on Data Mining 2020 (CCDM 2020) • Previous Articles     Next Articles

Generating CP-nets with bounded tree width based on Dandelion code

LI Congcong, LIU Jinglei   

  1. School of Computer and Control Engineering, Yantai University, Yantai Shandong 264005, China
  • Received:2020-05-31 Revised:2020-08-01 Online:2021-01-10 Published:2020-11-12
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61572419, 61773331, 61703360, 61801414).


李丛丛, 刘惊雷   

  1. 烟台大学 计算机与控制工程学院, 山东 烟台 264005
  • 通讯作者: 刘惊雷
  • 作者简介:李丛丛(1996-),女,山东济南人,硕士研究生,主要研究方向:图模型的随机生成算法、推理应用;刘惊雷(1970-),男,山西临猗人,教授,博士,主要研究方向:主要研究方向:人工智能、理论计算机科学。
  • 基金资助:

Abstract: Aiming at the problem of high time complexity of Conditional Preference networks (CP-nets) graph model in reasoning computation, a Generating CP-nets with Bounded Tree Width based on Dandelion code (BTW-CP-nets Gen) algorithm was proposed. First, through the principle of bidirectional mapping between Dandelion code and tree structure with tree width k (k-tree), the decoding and encoding algorithms between Dandelion code and k-tree were derived to realize the one-to-one mapping between code and tree structure. Second, the k-tree was used to constrain the tree width of CP-nets structure, and the k-tree feature tree was used to obtain the directed acyclic graph structure of CP-nets. Finally, the bijection of discrete multi-valued functions was used to calculate the conditional preference table of each CP-nets node, and the dominant query test was executed to the generated bounded tree-width CP-nets. Theoretical analysis and experimental data show that, compared with the Pruffer code generating k-tree (Pruffer code) algorithm, BTW-CP-nets Gen algorithm has the running time on generating simple and complex structures reduced by 21.1% and 30.5% respectively,and the node traversal ratio of the graph model generated by BTW-CP-nets Gen in the dominant query is 18.48% and 29.03% higher on simple structure and complex structure respectively; the smaller the time consumed by BTW-CP-nets Gen algorithm, the higher the traversal node ratio of the dominant query. It can be seen that BTW-CP-nets Gen algorithm can effectively improve the algorithm efficiency in graph model reasoning.

Key words: bounded tree-width, k-tree, Dandelion code, Conditional Preference networks (CP-nets), uniformity

摘要: 针对条件偏好网络(CP-nets)图模型在进行推理运算时的高时间复杂度的问题,提出了一种基于Dandelion编码生成有界树宽的CP-nets(BTW-CP-nets Gen)算法。首先,通过Dandelion编码与树宽为k的树结构(k-tree)之间的双向映射原理推导出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算法在图模型的推理中能够有效提高算法效率。

关键词: 有界树宽, k-tree, Dandelion 编码, 条件偏好网络, 均匀性

CLC Number: