Association Rule Mining using Path Systems in Directed Graphs

  • Subramanian Arumugam Senior Professor (Research) Kalasalingam University Anand Nagar, Krishnankoil
  • S. Sabeen Department of Computer Applications, Jaya Engineering College, Chennai-600054, INDIA.

Abstract

A transaction database (TDB) consists of a set $I$ of items and a multiset $\mathcal{D}$ of nonempty subsets of $I,$ whose elements are called transactions. There are several algorithms for solving the popular and computationally expensive task of association rule mining from a TDB. In this paper we propose a data structure which consists of a directed graph $D$ (loops and multiple arcs are permitted) and a system of directed paths in $D$ to represent a TDB. We give efficient algorithms for generating the data structure, for extracting frequent patterns and  for association rule mining.  We also propose several graph theoretic parameters which lead to a better understanding of the system.

Author Biography

Subramanian Arumugam, Senior Professor (Research) Kalasalingam University Anand Nagar, Krishnankoil
National Centre for Advanced Research in Discrete Mathematics

References

R. Agrawal, T. Imielinski and A. Swami, Mining association rules between sets of items in large database, In Proc. of the ACM SIGMOD International Conference on Management of Data (ACM SIGMOD 93), Washington, USA, May 1993, 207-216.

G. Chartrand and L. Lesniak, Graphs and Digraphs, Chapman and Hall, CRC, 4th edition, 2005.

R. Agrawal and R. Srikant, Fast Algorithms for mining association rules, In Proc. of the 20th International Conference on Very Large Database (VLDB' 94), Santiago, Chile, June 1994.

J. Han, J. Pei and Y. Yin, Mining Frequent Patterns without Candidate Generation, In Proc. of the 2000 ACM SIGMOD International Conference on Management of Data, Dallas, Texas, USA, May 2000.
http://dx.doi.org/10.1145/342009.335372

S. Brin, R. Motwani, J.D. Ullman and S. Tsur, Dynamic itemset counting and implications rules for masket basket data, In Proc. of the ACM SIGMOD International Conference on Management Data, 1997.

M. Hontsma and A. Swami, Set oriented mining for association rules in relatrend database, The technical report RJ9567, IBM Almaden Research Centre, San Jose, California, October 1993. J. Han and M. Kamber, Data minining, Concepts and Applications, Elsevier Inc., (2006).
Published
2013-11-11
How to Cite
ARUMUGAM, Subramanian; SABEEN, S.. Association Rule Mining using Path Systems in Directed Graphs. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 8, n. 6, p. 791-799, nov. 2013. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/19>. Date accessed: 11 july 2020. doi: https://doi.org/10.15837/ijccc.2013.6.19.

Keywords

Directed graphs, path system, in-degree, out-degree, association rule mining, frequent patterns, data mining.