计算机应用 ›› 2017, Vol. 37 ›› Issue (2): 329-334.DOI: 10.11772/j.issn.1001-9081.2017.02.0329

• 第33届中国数据库学术会议(NDBC 2016) • 上一篇    下一篇

基于中医方剂数据库的Top-Rank-k频繁模式挖掘算法

秦琦冰1, 谭龙1,2   

  1. 1. 黑龙江大学 计算机科学技术学院, 哈尔滨 150080;
    2. 黑龙江省数据库与并行计算重点实验室(黑龙江大学), 哈尔滨 150080
  • 收稿日期:2016-08-12 修回日期:2016-09-08 出版日期:2017-02-10 发布日期:2017-02-11
  • 通讯作者: 谭龙,tanlong@hlju.edu.cn
  • 作者简介:秦琦冰(1990-),男,山东潍坊人,硕士研究生,主要研究方向:机器学习、数据仓库、数据挖掘;谭龙(1971-),男,黑龙江哈尔滨人,副教授,硕士,CCF会员,主要研究方向:机器学习、传感器网络、数据挖掘。
  • 基金资助:

    国家自然科学基金面上项目(81273649);黑龙江省自然科学基金面上项目(F201434);黑龙江大学研究生创新科研项目重点项目(YJSCX2016-018HLJU)。

Top-Rank-k frequent patterns mining algorithm based on TCM prescription database

QIN Qibing1, TAN Long1,2   

  1. 1. College of Computer Science and Technology, Heilongjiang University, Harbin Heilongjiang 150080, China;
    2. Key Laboratory of Database and Parallel Computing of Heilongjiang Province(Heilongjiang University), Harbin Heilongjiang 150080, China
  • Received:2016-08-12 Revised:2016-09-08 Online:2017-02-10 Published:2017-02-11
  • Supported by:

    This work is partially supported by the National Natural Science Foundation of China (81273649), Natural Science Foundation of Heilongjiang Province (F201434), Graduate Student Innovation and Research Item of Heilongjiang University (YJSCX2016-018HLJU).

摘要:

为降低中医(TCM)方剂频繁模式挖掘过程中对经验参数的依赖,提高挖掘结果的准确性,针对中医方剂的数据特点,提出一种基于带权无向图的Top-Rank-k频繁模式挖掘算法。该算法可以直接挖掘出频繁k-itemset(k≥3)而无需产生1-itemset和2-itemset,并随之快速回溯到核心药物组合的频繁项集所对应的方剂信息;此外,采用一种动态位向量(DBV)的压缩机制对无向图中边的权重进行压缩存储,以有效地提高算法的空间存储效率。分别对中医方剂数据集、真实数据集(Chess、Pumsb和Retail)和合成数据集(T10I4D100K和Test2K50KD1)进行测试和比较,结果表明该算法与iNTK和BTK相比具有更高的时间和空间效率,而且也可以应用于其他类型的数据集。

关键词: 中医方剂, Top-Rank-k, 频繁模式, 带权无向图, 动态位向量

Abstract:

The dependency of the empirical parameters in frequent patterns mining of Traditional Chinese Medicine (TCM) prescriptions should be reduced to improve the accuracy of mining results. Aiming at the characteristics of TCM prescription data, an efficient Top-Rank-k frequent patterns mining algorithm based on Weighted Undirected Graph (WUG) was proposed. The new algorithm can directly mining frequent k-itemset (k≥3) without mining 1-times and 2-times, and then quikly backtrack to the corresponding prescription of the frequent itemsets of core drugs combination. Besides, the compression mechanism of Dynamic Bit Vector (DBV) was used to store the edge weights in undirected graph to improve the spatial storage efficiency of the algorithm. Experiments were conducted on TCM prescription datasets, real datasets (Chess, Pumsb and Retail) and synthetic datasets (T10I4D100K and Test2K50KD1). The experimental results show that compared with iNTK (improved Node-list Top-Rank-K) and BTK (B-list Top-Rank-K), the proposed algorithm has better performance in terms of time and space, and it can be applied to other types of data sets.

Key words: Traditional Chinese Medicine (TCM) prescription, Top-Rank-k, frequent pattern, Weighted Undirected Graph (WUG), Dynamic Bit Vector (DBV)

中图分类号: