JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE) ›› 2014, Vol. 44 ›› Issue (6): 38-46.doi: 10.6040/j.issn.1672-3961.2.2013.284

Previous Articles     Next Articles

AC_SAR: actionable clustering algorithm based on strong association rule

YAO Huachuan1, WANG Lizhen2, WU Pingping2, ZOU Muquan1   

  1. 1. Department of Computer Science and Engineering, School of Information Science and Engineering, Yunnan University, Kunming 650091, Yunnan, China;
    2. Department of Computer Science and Engineering, Dianchi College, Yunnan University, Kunming 650091, Yunnan, China
  • Received:2014-05-23 Revised:2014-07-02 Online:2014-12-20 Published:2014-05-23

PDF (PC)

691

Abstract: An actionable clustering algorithm based on strong association rules (AC_SAR) was proposed. The AC_SAR algorithm looked for strong associated objects for each object, and then some relevant rules were deleted and merged by the anti-symmetric principle and the connectivity principle. The connected sub-graphs (clusters) related to all objects in transaction database were discovered finally. Compared with the traditional algorithms, the AC_SAR algorithm did not need to set the thresholds by user, and there were not redundant rules in the results. Moreover, the intermediate mined results and the final generated clusters could solve the problems in many fields effectively. A large number of experiments showed that the AC_SAR algorithm had higher efficiency, higher accuracy, and stronger action.

Key words: clustering, actionable, strong relevance principle, connectivity principle, strong association rules, anti-symmetry principle

CLC Number: 

  • TP311
[1] HAN Jiawei, KAMBER M. 数据挖掘概念与技术 [M]. 2版.范明, 孟小峰, 译. 北京:机械工业出版社, 2007:146-183.
[2] 朱孝宇, 王理东, 汪光阳. 一种改进的Apriori挖掘关联规则算法[J].计算机技术与发展, 2006, 16(12):89-90. ZHU Xiaoyu, WANG Lidong, WANG Guangyang. An improvement of Apriori algorithm for mining association rules[J]. Computer Technology and Development, 2006, 16(12):89-90.
[3] 邵峰晶, 于忠清. 数据挖掘原理与算法[M]. 北京:中国水利水电出版社, 2003:123-135.
[4] 刘以安, 羊斌. 关联规则挖掘中对Apriori算法的一种改进研究[J]. 计算机应用, 2007, 27(2):418-420. LIU Yian, YANG Bin. Research of an improved Apriori algorithm in mining association rules[J]. Computer Applications, 2007, 27(2):418-420.
[5] 袁万莲, 郑诚, 翟明清. 一种改进的Apriori算法[J]. 计算机技术与发展, 2008,18(5):51-53. YUAN Wanlian, ZHENG Cheng, ZHAI Mingqing. An improved Apriori algorithm[J]. Computer Technology and Development, 2008, 18(5):51-53.
[6] HAN Jiawei, PEI Jian, YIN Yiwen. Mining frequent patterns without candidate generation:a frequent-pattern tree approach[C]//Proceedings of International Conference on Data Mining and Knowledge Discovery. New York, USA:ACM, 2004:53-87.
[7] 李志云,周国祥.一种基于MFP树的快速关联规则挖掘算法[J].计算机技术与发展,2007(6):94-100. LI Zhiyun, ZHOU Guoxiang. A fast association rule mining algorithm based on MFP tree[J]. Computer Technology and Development, 2007(6):94-100.
[8] 徐前方,阔建杰,李永春,等.一种具有时序特征的告警关联规则挖掘算法[J].微电子学与计算机,2007(24):23-26. XU Qianfang, KUO Jianjie, LI Yongchum, et al. An algorithm for mining time-series alarm association rules[J]. Microelectronics and Computer, 2007(24):23-26.
[9] 宋余庆,朱玉全,孙志辉,等.基于FP-Tree的最大频繁项目集挖掘及更新算法[J].软件学报,2003, 14(9):1586-1592. SONG Yuqing, ZHU Yuquan, SUN Zhihui, et al. An algorithm and its updating algorithm based on FP-Tree for mining maximum frequent itemsets[J]. Journal of Software, 2003, 14(9):1586-1592.
[10] 冯霞,李娟娟,闫冠男. 关联规则挖掘在航空安全报告分析中的应用[J]. 计算机工程与设计, 2011, 32(1):218-220. FENG Xia, LI Juanjuan, YAN Guannan. Applications of association rules mining in aviation safety reports analysis[J]. Computer Engineering and Design, 2011, 32(1):218-220.
[11] 钱冬云. 基于用户兴趣导向的关联规则数据挖掘[J]. 微计算机信息, 2007(21):207-209. QIAN Dongyun. Algorithms based user transmits of association rules in data mining[J]. Microcomputer Information, 2007(21):207-209.
[12] 戴臻,费洪晓,谢文彪,等. 基于特定模式树的用户行为关联规则挖掘算法[J]. 计算机系统应用, 2007(5):56-59. DAI Zhen, FEI Hongxiao, XIE Wenbiao, et al. The algorithm of users behavior associate rules mining based on specific pattern tree[J]. Computer Systems Applications, 2007(5):56-59.
[13] 宋江春,沈钧毅,宋擒豹. 一个基于关联规则的多层文档聚类算法[J].计算机应用, 2005, 25(7):1571-1572. SONG Jiangchun, SHEN Junyi, SONG Qinbao. Multi-level document clustering algorithm based on association rules[J]. Computer Applications, 2005, 25(7):1571-1572.
[14] 曾利军,李泽军,柳佳刚. 基于矩阵加权关联规则的区间模糊C均值聚类[J]. 计算机工程, 2010, 36(22):52-54. ZENG Lijun, LI Zejun, LIU Jiagang. Inter borough fuzzy C-means clustering based on matrix-weighted association rules[J]. Computer Engineering, 2010, 36(22):52-54.
[15] 苑森淼, 程晓青. 数量关联规则发现中的聚类方法研究[J],计算机学报, 2000, 23(8):866-871. YUAN Senmiao, CHENG Xiaoqing. Clustering method for mining quantitative association rules[J]. Chinese Journal of Computer, 2000, 23(8):866-871.
[16] 周霆, 张伟, 张泽洪. 基于关联规则的映射聚类算法[J]. 微电子学与计算机, 2006, 23(3):26-33. ZHOU Ting, ZHANG Wei, ZHANG Zehong. Association rules-based projected clustering algorithm[J]. Microelectronics and Computer, 2006, 23(3):26-33.
[17] 龙昊, 冯剑, 琳李曲. R-means:以关联规则为簇中心的文本聚类[J].计算机科学, 2005, 32(9):156-159. LONG Hao, FENG Jian, LIN Liqu. R-means:exploiting association rules as means for text clustering[J]. Computer Science, 2005, 32(9):156-159.
[18] Lotfi Admane, Karima Benatchba, Mouloud Koudi, et al. AntPart:an algorithm for the unsupervised classification problem using ants[J].Applied Mathematics and Computation, 2006, 180(1):16-28.
[19] DORIGO M, BONABEAU E, THERAULAZ G. Ant algorithms and stifmergy[J]. Future Generation Computer Systerns, 2000, 16(8):851-871.
[20] LUMER E, FAIETA B. Diversity and adaptation in populations of clustering ants[C]//Proceedings of the Third International Conference on Simulation of Adaptive Behavior:From Animals to Animals. MA:MIT Press, 1994:499-508.
[21] 吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报, 2001(12):1328-1333. WU Bin, SHI Zhongzhi. An ant colony algorithm based partition algorithm for TSP[J]. Chinese Journal of Computers, 2001(12):1328-1333.
[22] 沙露,鲍培明,李尼格.基于蚁群系统的聚类算法研究[J]. 山东大学学报:工学版, 2010(3):13-18. SHA Lu, BAO Peiming, LI Nige. Clustering algorithm based on ant colony system[J]. Journal of Shandong University: Engineering Science, 2010(3):13-18.
[23] CAO Longbin, ZHANG Chengqi. Knowledge actionability:satisfying technical and business interestingness[J]. International Journal of Business Intelligence and Data Mining, 2007, 2(4):496-514.
[24] CAO Longbin, ZHANG Chengqi. Domain-driven actionable knowledge discovery in the real world[C]//Proceedings of the 10th Pacific-Asi Conf. on Advances in Knowledge Discovery and Data mining (PAKDD 2006). Berlin Heidelberg:Springer, LNAI 3918, 2006:821-830.
[25] CAO Longbing, ZHAO Yanchang, ZHANG Chengqi. Mining impact-targeted activity patterns in imbalanced data[J]. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(8):1053-1066.
[1] LI Xiaohui, LIU Xiaofei, SUN Weitong, ZHAO Yi, DONG Yuan, JIN Yinli. An inspection task assignment and path planning algorithm based on vehicles-UAVs collaboration [J]. Journal of Shandong University(Engineering Science), 2025, 55(5): 101-109.
[2] CHEN Sugen, ZHAO Zhizhong. Density peak clustering combining local truncation distance and small clusters merging [J]. Journal of Shandong University(Engineering Science), 2025, 55(2): 58-70.
[3] ZHU Hengdong, MA Yingcang, DAI Xuezhen. Adaptive semi-supervised neighborhood clustering algorithm [J]. Journal of Shandong University(Engineering Science), 2021, 51(4): 24-34.
[4] ZHU Changming, YUE Wen, WANG Panhong, SHEN Zhenyu, ZHOU Rigui. Global and local multi-view multi-label learning with active three-way clustering [J]. Journal of Shandong University(Engineering Science), 2021, 51(2): 34-46.
[5] XIE Ziqi, WANG Lihong, LI Man. Active learning of pairwise constraints in block diagonal subspace clustering [J]. Journal of Shandong University(Engineering Science), 2021, 51(2): 65-73.
[6] Bei LI,Song ZHAO,Zhijia XIE,Meng NIU. Electric vehicle virtual energy storage available capacity modeling [J]. Journal of Shandong University(Engineering Science), 2020, 50(6): 101-111.
[7] Xinyu DONG,Hanyue CHEN,Jiaguo LI,Qingyan MENG,Shihe XING,Liming ZHANG. An unsupervised color image segmentation method based on fusion of multiple methods [J]. Journal of Shandong University(Engineering Science), 2019, 49(2): 96-101.
[8] Jun QIN,Yuanpeng ZHANG,Yizhang JIANG,Wenlong HANG. Transfer fuzzy clustering based on self-constraint of multiple medoids [J]. Journal of Shandong University(Engineering Science), 2019, 49(2): 107-115.
[9] Yingxue ZHU,Ruizhang HUANG,Can MA. A short text dynamic clustering approach bias on new topic [J]. Journal of Shandong University(Engineering Science), 2018, 48(6): 8-18.
[10] Qiyue SONG, Xuewen MU, Huan CHENG. Segmentation of connected characters based on improved drop-fall algorithm [J]. Journal of Shandong University(Engineering Science), 2018, 48(6): 89-94.
[11] ZHANG Peirui, YANG Yan, XING Huanlai, YU Xiuying. Incremental multi-view clustering algorithm based on kernel K-means [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 48-53.
[12] DU Xixi, LIU Huafeng, JING Liping. An additive co-clustering for recommendation of integrating social network [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 96-102.
[13] YANG Tianpeng, XU Kunpeng, CHEN Lifei. Coefficient of variation clustering algorithm for non-uniform data [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 140-145.
[14] PANG Renming, WANG Bo, YE Hao, ZHANG Haifeng, LI Mingliang. Clustering of blast furnace historical data based on PCA similarity factor and spectral clustering [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(5): 143-149.
[15] ZHOU Wang, ZHANG Chenlin, WU Jianxin. Qualitative balanced clustering algorithm based on Hartigan-Wong and Lloyd [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(5): 37-44.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] LI Kan . Empolder and implement of the embedded weld control system[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(4): 37 -41 .
[2] SHI Lai-shun,WAN Zhong-yi . Synthesis and performance evaluation of a novel betaine-type asphalt emulsifier[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(4): 112 -115 .
[3] LAI Xiang . The global domain of attraction for a kind of MKdV equations[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(1): 87 -92 .
[4] YU Jia yuan1, TIAN Jin ting1, ZHU Qiang zhong2. Computational intelligence and its application in psychology[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 1 -5 .
[5] CHEN Rui, LI Hongwei, TIAN Jing. The relationship between the number of magnetic poles and the bearing capacity of radial magnetic bearing[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(2): 81 -85 .
[6] WANG Bo,WANG Ning-sheng . Automatic generation and combinatory optimization of disassembly sequence for mechanical-electric assembly[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 52 -57 .
[7] ZHANG Ying,LANG Yongmei,ZHAO Yuxiao,ZHANG Jianda,QIAO Peng,LI Shanping . Research on technique of aerobic granular sludge cultivationby seeding EGSB anaerobic granular sludge[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(4): 56 -59 .
[8] Yue Khing Toh1， XIAO Wendong2， XIE Lihua1. Wireless sensor network for distributed target tracking: practices via real test bed development[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 50 -56 .
[9] WANG Jing,LI Yu-jiang,ZHANG Xiao-jin,BI Yan-jun,CHEN Wei-suo . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(6): 100 -103 .
[10] SUN Weiwei， WANG Yuzhen. Finite gain stabilization of singlemachine infinite bus system subject to saturation[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 69 -76 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd