Please wait a minute...
Advanced Search
数据分析与知识发现  2019, Vol. 3 Issue (7): 85-93    DOI: 10.11925/infotech.2096-3467.2018.0999
  研究论文 本期目录 | 过刊浏览 | 高级检索 |
基于频次有效长度的加权关联规则挖掘算法研究 *
张勇,李树青(),程永上
南京财经大学信息工程学院 南京 210046
Mining Algorithm for Weighted Association Rules Based on Frequency Effective Length
Yong Zhang,Shuqing Li(),Yongshang Cheng
School of Information Engineering, Nanjing University of Finance and Economics, Nanjing 210046, China
全文: PDF(653 KB)   HTML ( 2
输出: BibTeX | EndNote (RIS)      
摘要 

目的】通过对数据库中项在重要程度上存在的差异性进行分析, 解决传统关联规则挖掘算法挖掘大量冗余无价值规则的问题。【方法】在具有时态约束的序列上, 结合频次有效长度方法挖掘非加权关联规则, 引入加权方法, 利用滑动窗口技术在时序序列上挖掘稀有加权关联规则。【结果】根据频次有效长度的加权关联规则挖掘算法所挖掘出的加权时序关联规则能够较为准确地进行推荐, 推荐预测的准确度由62%提升至69%。【局限】由于滑动窗口每次滑动一个单位长度, 加之窗口中生成的规则数量较多, 导致挖掘算法在进行规则挖掘时执行时间较长。【结论】本文方法所挖掘出的加权时序关联规则能使推荐精度得到提升, 并为关联规则挖掘方法提供新的研究思路。

服务
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章
张勇
李树青
程永上
关键词 数据挖掘关联规则频次长度滑动窗口    
Abstract

[Objective] This paper analyzes the differences in the importance of database items, aiming to address the issues of traditional association mining algorithm with redundant and worthless rules. [Methods] On the sequence with temporal constraints, we explored the non-weighted association rules with the frequency effective length and the weighting methods. Then, we used sliding window technique to study the rare weighted association rules on the time series. [Results] The accuracy of the prediction made by the proposed method increased to 69% from 62%. [Limitations] The mining algorithm took long time to extract the needed rules due to the sliding windows and the large number of rules generated. [Conclusions] The association rules of weighted time series improve the accuracy of recommendation, which also provides new directions for research method on association rules.

Key wordsData Mining    Association Rules    Frequency Length    Sliding Window
收稿日期: 2018-09-08     
中图分类号:  G354  
基金资助:*本文系国家社会科学基金项目“基于大数据分析的数字图书馆个性化服务模式创新研究”的研究成果之一(16BTQ030)
通讯作者: 李树青     E-mail: leeshuqing@163.com
引用本文:   
张勇,李树青,程永上. 基于频次有效长度的加权关联规则挖掘算法研究 *[J]. 数据分析与知识发现, 2019, 3(7): 85-93.
Yong Zhang,Shuqing Li,Yongshang Cheng. Mining Algorithm for Weighted Association Rules Based on Frequency Effective Length. Data Analysis and Knowledge Discovery, DOI:10.11925/infotech.2096-3467.2018.0999.
链接本文:  
http://manu44.magtech.com.cn/Jwk_infotech_wk3/CN/10.11925/infotech.2096-3467.2018.0999
用户 类型 评分
1 A,C,T,W 3, 1, 5, 0.5
2 C,D,T 1 , 0.5 ,5
3 A,C,W 3 , 1 , 1.5
4 A,C,D,W 4, 1, 2, 1
5 C,D,W 1, 2, 1
表1  电影类型及评分
类型 权值
A 0.6
C 0.3
D 0.3
T 0.6
W 0.2
表2  项目类型所对应的权值
用户 类型 计算过程 用户序列平均权值
1 A,C,T,W (0.6+0.3+0.6+0.2)/4 0.43
2 C,D,T (0.3+0.3+0.6)/3 0.4
3 A,C,W (0.6+0.3+0.2)/3 0.37
4 A,C,D,W (0.6+0.3+0.3+0.2)/4 0.35
5 C,D,W (0.3+0.3+0.2)/3 0.27
sum 1.82
表3  用户序列平均权值
频繁集 CT ACW CW
加权支持度(ws) 0.46 0.63 0.78
表4  频繁集与其加权支持度
用户 类型
1 [A,C,T,W,A,W,C,T],W
2 [D,T, T,W,A,W,C,A],W,C
3 [W, T, T,W,A,W,A,T],W,A,C
4 [A,C,D,W,T,A,C,W]
5 [C,D,W]
表5  用户序列与滑动窗口
用户 类型 滑窗中的用户序列平均权值
1 [A,C,T,W,A,W,C,T],W 0.45
2 C,[D,T, T,W,A,W,C,A],W 0.51
3 A,C,[W, T, T,W,A,W,A,T],W 0.56
4 [A,C,D,W,T,A,C,W] 0.38
5 [C,D,W] 0.20
sum 2.10
表6  滑动窗口中的用户序列平均权值
支持度
置信度
(0.20,0.25] (0.25,0.30] (0.30,0.35] (0.35,0.40]
(0.5,0.6] 0.0378 0.0319 0.0579 0.0287
(0.6,0.7] 0.0469 0.0432 0.0599 0.0433
(0.7,0.8] 0.0748 0.0802 0.0967 0.0830
(0.8,0.9] 0.1020 0.1174 0.0935 0.0667
(0.9,1.0] 0.0462 0.0272 0.0090 0.0066
表7  Apriori各区间准确度
支持度
置信度
(0.20,0.25] (0.25,0.30] (0.30,0.35] (0.35,0.40]
(0.5,0.6] 0.0031 0.0019 0.0012 0.0009
(0.6,0.7] 0.0091 0.0035 0.0026 0.0018
(0.7,0.8] 0.0190 0.0071 0.0039 0.0024
(0.8,0.9] 0.0543 0.0196 0.0059 0.0025
(0.9,1.0] 0.0826 0.0185 0.0029 0.0011
表8  Apriori各区间覆盖度
后续节点位置 命中率 后续节点位置 命中率
1 0.3750 6 0.3701
2 0.3722 7 0.3651
3 0.3725 8 0.3685
4 0.3704 9 0.3695
5 0.3853 10 0.3680
表9  后续各个节点位置的命中率
支持度
置信度
(0.20,0.25] (0.25,0.30] (0.30,0.35] (0.35,0.40]
(0.5,0.6] 0.0432 0.0455 0.0554 0.0308
(0.6,0.7] 0.1121 0.1079 0.0560 0.0975
(0.7,0.8] 0.2124 0.1594 0.1142 0.0994
(0.8,0.9] 0.1832 0.1730 0.1270 0.0903
(0.9,1.0] 0.0969 0.0534 0.0172 0.0156
表10  扩大预测范围后各区间准确度
支持度
置信度
(0.20,0.25] (0.25,0.30] (0.30,0.35] (0.35,0.40]
(0.5,0.6] 0.0047 0.0022 0.0018 0.0008
(0.6,0.7] 0.0162 0.0127 0.0049 0.0029
(0.7,0.8] 0.0310 0.0122 0.0065 0.0042
(0.8,0.9] 0.0761 0.0236 0.0097 0.0030
(0.9,1.0] 0.1285 0.0301 0.0054 0.0013
表11  扩大预测范围后各区间覆盖度
频次有效周期 误差率 频次有效周期 误差率
3 0.3201 8 0.2449
4 0.2995 9 0.2658
5 0.2831 10 0.2576
6 0.2769 11 0.2694
7 0.2769 12 0.2603
表12  频次有效周期与误差率
区间 准确度 区间 准确度 区间 准确度
(0.10,0.15] 0.69 (0.40,0.45] 0.38 (0.70,0.75] 0.45
(0.15,0.20] 0.55 (0.45,0.50] 0.40 (0.75,0.80] 0.07
(0.20,0.25] 0.53 (0.50,0.55] 0.42 (0.80,0.85] 0.15
(0.25,0.30] 0.49 (0.55,0.60] 0.20 (0.85,0.90] 0.11
(0.30,0.35] 0.52 (0.60,0.65] 0.14 (0.90,0.95] 0.10
(0.35,0.40] 0.43 (0.65,0.70] 0.23 (0.95,1.00] 0.01
表13  新方法各加权支持度区间的准确度
区间 覆盖度 区间 覆盖度 区间 覆盖度
(0.10,0.15] 0.40 (0.40,0.45] 0.35 (0.70,0.75] 0.31
(0.15,0.20] 0.41 (0.45,0.50] 0.33 (0.75,0.80] 0.31
(0.20,0.25] 0.36 (0.50,0.55] 0.22 (0.80,0.85] 0.27
(0.25,0.30] 0.38 (0.55,0.60] 0.34 (0.85,0.90] 0.22
(0.30,0.35] 0.37 (0.60,0.65] 0.30 (0.90,0.95] 0.25
(0.35,0.40] 0.36 (0.65,0.70] 0.31 (0.95,1.00] 0.08
表14  新方法加权支持度各区间的覆盖度
最小加权置信度阈值 准确度 最小加权置信度阈值 准确度
0.40 0.69 0.70 0.57
0.50 0.67 0.80 0.53
0.60 0.65 0.90 0.48
表15  最小加权置信度阈值所对应的准确度
图1  准确度方面对比
图2  覆盖度方面对比
图3  本文方法的准确度与已有方法对比
[1] Khan M S, Muyeba M, Coenen F. A Weighted Utility Framework for Mining Association Rules [C]// Proceedings of the 2nd UKSIM European Symposium on Computer Modeling and Simulation. 2008: 87-92.
[2] Forsati R, Meybodi M R . Effective Page Recommendation Algorithms Based on Distributed Learning Automata and Weighted Association Rules[J]. Expert Systems with Applications, 2010,37(2):1316-1330.
[3] Zhai Y, Wang L, Wang N. Efficient Weighted Association Rule Mining Using Lattice [C]// Proceedings of the 26th Chinese Control and Decision Conference. 2014: 4913-4917.
[4] Ouyang W. Mining Weighted Rare Association Rules Using Sliding Window over Data Streams [C]// Proceedings of the 2016 International Conference on Computer Science and Electronic Technology. 2016: 116-119.
[5] 李成军, 杨天奇 . 一种改进的加权关联规则挖掘方法[J]. 计算机工程, 2010,36(7):55-57.
( Li Chengjun, Yang Tianqi . Improved Weighted Association Rules Mining Method[J]. Computer Engineering, 2010,36(7):55-57.)
[6] 欧阳为民, 郑诚, 蔡庆生 . 数据库中加权关联规则的发现[J]. 软件学报, 2001,12(4):612-619.
( Ouyang Weimin, Zheng Cheng, Cai Qingsheng . Discovery of Weighted Association Rules in Databases[J]. Journal of Software, 2001,12(4):612-619.)
[7] Malarvizhi S P, Sathiyabhama B . Frequent Pagesets from Web Log by Enhanced Weighted Association Rule Mining[J]. Cluster Computing, 2016,19(1):1-9.
[8] 王涛伟, 任一波 . 基于加权关联规则的个性化推荐研究[J]. 计算机应用与软件, 2008,25(8):242-244.
( Wang Taowei, Ren Yibo . Study on Personalized Recommendation Based on Weighted Association Rule[J]. Computer Applications and Software, 2008,25(8):242-244.)
[9] 王斌, 丁祥斌 . 一种基于BUC的水平加权关联规则挖掘算法[J]. 计算机应用与软件, 2008,25(12):112-115.
( Wang Bin, Ding Xiangbin . A BUC-Based Mining Algorithm for Horizontal Weighted Association Rules[J]. Computer Applications and Software, 2008,25(12):112-115.)
[10] 龙舜, 蔡跳, 林佳雄 . 一个基于演化关联规则挖掘的个性化推荐模型[J]. 暨南大学学报: 自然科学与医学版, 2012,33(3):264-267.
( Long Shun, Cai Tiao, Lin Jiaxiong . A Personalized Recommendation Model Based on Evolving Association Rule Mining[J]. Journal of Jinan University: Natural Science & Medicine Edition, 2012,33(3):264-267.)
[11] 张佳乐, 梁吉业, 庞继芳 , 等. 基于行为和评分相似性的关联规则群推荐算法[J]. 计算机科学, 2014,41(3):36-40.
( Zhang Jiale, Liang Jiye, Pang Jifang , et al. Behavior and Score Similarity Based Algorithm for Association Rule Group Recommendation[J]. Computer Science, 2014,41(3):36-40.)
[1] 陆泉,朱安琪,张霁月,陈静. 中文网络健康社区中的用户信息需求挖掘研究*——以求医网肿瘤板块数据为例[J]. 数据分析与知识发现, 2019, 3(4): 22-32.
[2] 牟冬梅,法慧,王萍,孙晶. 基于结构方程模型的疾病危险因素研究*[J]. 数据分析与知识发现, 2019, 3(4): 80-89.
[3] 何跃,丰月,赵书朋,马玉凤. 基于知乎问答社区的内容推荐研究——以物流话题为例[J]. 数据分析与知识发现, 2018, 2(9): 42-49.
[4] 李勇男. 贝叶斯理论在反恐情报分类分析中的应用研究*[J]. 数据分析与知识发现, 2018, 2(10): 9-14.
[5] 牟冬梅,王萍,赵丹宁. 高维电子病历的数据降维策略与实证研究*[J]. 数据分析与知识发现, 2018, 2(1): 88-98.
[6] 何跃,王爱欣,丰月,王莉. 基于关联规则的门诊药房布局优化[J]. 数据分析与知识发现, 2018, 2(1): 99-108.
[7] 胡忠义,王超群,吴江. 融合多源网络评估数据及URL特征的钓鱼网站识别技术研究*[J]. 数据分析与知识发现, 2017, 1(6): 47-55.
[8] 卢晓航,王胜清,黄俊杰,陈文广,闫增旺. 一种基于滑动窗口模型的MOOCs辍学率预测方法*[J]. 数据分析与知识发现, 2017, 1(4): 67-75.
[9] 江思伟,谢振平,陈梅婕,蔡明. 混合特征数据的自解释归约建模方法*[J]. 数据分析与知识发现, 2017, 1(12): 92-100.
[10] 魏星,胡德华,易敏寒,朱启贞,朱文婕. 基于数据立方体挖掘疾病-基因-药物新关联*[J]. 数据分析与知识发现, 2017, 1(10): 94-104.
[11] 黄名选. 基于矩阵加权关联模式的印尼中跨语言信息检索模型*[J]. 数据分析与知识发现, 2017, 1(1): 26-36.
[12] 牟冬梅,任珂. 三种数据挖掘算法在电子病历知识发现中的比较*[J]. 现代图书情报技术, 2016, 32(6): 102-109.
[13] 李峰,李书宁,于静. 面向院系的高校毕业生图书馆记忆系统[J]. 现代图书情报技术, 2016, 32(5): 99-103.
[14] 阮光册, 夏磊. 基于关联规则的文本主题深度挖掘应用研究*[J]. 数据分析与知识发现, 2016, 32(12): 50-56.
[15] 杜思奇, 李红莲, 吕学强. 汉语组块分析在产品特征提取中的应用研究[J]. 现代图书情报技术, 2015, 31(9): 26-30.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
版权所有 © 2015 《数据分析与知识发现》编辑部
地址:北京市海淀区中关村北四环西路33号 邮编:100190
电话/传真:(010)82626611-6626,82624938
E-mail:jishu@mail.las.ac.cn