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)

551

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] 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.
[2] 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.
[3] 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.
[4] 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.
[5] 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.
[6] JI Xingquan, HAN Guozheng, LI Kejun, FU Rongrong, ZHU Yanghe. Application of improved K-means clustering algorithm based on density in distribution network block partitioning [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(4): 41-46.
[7] LI Shuo, SHI Yuliang. The method of spot cluster recommendation in location-based social networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(3): 44-50.
[8] JIANG Feng, DU Junwei, LIU Guozhu, SUI Yuefei. A weight-based initial centers selection algorithm for K-modes clustering [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(2): 29-34.
[9] FAN Shuyan, DING Shifei. An improved multi-scale Graph cut algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(1): 28-33.
[10] XU Pingan, TANG Yan, SHI Jiaokai, ZHANG Huirong. K-Means clustering algorithm based on the Schrödinger equation [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(1): 34-41.
[11] ZHU Hong, DING Shifei. Twice clustering method based on variable granularity [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(3): 1-6.
[12] DONG Hongbin, ZHANG Guangjiang, PANG Jinwei, HAN Qilong. A clustering ensemble algorithm based on co-evolution [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(2): 1-9.
[13] HAO Qingbo, MU Shaomin, YIN Chuanhuan, CHANG Tengteng, CUI Wenbin. An algorithm of fast local support vector machine based on clustering [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(1): 13-18.
[14] SI Junshu, ZHU Wenxing*, SHA Yonghe. A comprehensive method for traffic lights detection in complex background [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(2): 64-68.
[15] CHEN Wen-qiang1, LIN Chen1,2, CHEN Ke3, CHEN Jin-xiu1, ZOU Quan1,2*. Distributed affinity propagation clustering algorithm based on GraphLab [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2013, 43(5): 13-18.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd