Efficient Algorithm for Mining Non-Redundant High-Utility Association Rules

Abstract

In business, managers may use the association information among products to define promotion and competitive strategies. The mining of high-utility association rules (HARs) from high-utility itemsets enables users to select their own weights for rules, based either on the utility or confidence values. This approach also provides more information, which can help managers to make better decisions. Some efficient methods for mining HARs have been developed in recent years. However, in some decision-support systems, users only need to mine a smallest set of HARs for efficient use. Therefore, this paper proposes a method for the efficient mining of non-redundant high-utility association rules (NR-HARs). We first build a semi-lattice of mined high-utility itemsets, and then identify closed and generator itemsets within this. Following this, an efficient algorithm is developed for generating rules from the built lattice. This new approach was verified on different types of datasets to demonstrate that it has a faster runtime and does not require more memory than existing methods. The proposed algorithm can be integrated with a variety of applications and would combine well with external systems, such as the Internet of Things (IoT) and distributed computer systems. Many companies have been applying IoT and such computing systems into their business activities, monitoring data or decision-making. The data can be sent into the system continuously through the IoT or any other information system. Selecting an appropriate and fast approach helps management to visualize customer needs as well as make more timely decisions on business strategy.

Keywords: Internet of Things; data mining; high-utility association rule; high-utility itemset; lattice; non-redundant high-utility association rule.

Figure 1

Lattice of HUIs with closed and generator itemsets.

Figure 2

Runtime on the Chess dataset (a) with fixed min-util = 27% and various min-ucon and (b) with various min-util and fixed min-uconf = 70%.

Figure 3

Runtime on the Retail dataset (a) with fixed min-util = 0.03% and various min-uconf and (b) with various min-util and fixed min-uconf = 70%.

Figure 4

Runtime on the Mushroom dataset (a) with fixed min-util = 12% and various min-uconf and (b) with various min-util and fixed min-uconf = 70%.

Figure 5

Runtime on the Chainstore dataset (a) with fixed min-util = 0.01% and various min-uconf and (b) with various min-util and fixed min-uconf = 70%.

Figure 6

Runtime on the Accidents dataset (a) with fixed min-util = 11% and various min-uconf and (b) with various min-util and fixed min-uconf = 70%.

Figure 7

Memory usage on the Chess dataset (a) with fixed min-util = 27% and various min-uconf and (b) with various min-util and fixed min-uconf = 70%.

Figure 8

Memory usage on the Retail dataset (a) with fixed min-util = 0.03% and various min-uconf and (b) with various min-util and fixed min-uconf = 70%.

Figure 9

Memory usage on the Mushroom dataset (a) with fixed min-util = 12% and various min-uconf and (b) with various min-util and fixed min-uconf = 70%.

Figure 10

Memory usage on the Accidents dataset (a) with fixed min-util = 12% and various min-uconf and (b) with various min-util and fixed min-uconf = 70%.

Figure 11

Memory usage on the Chainstore dataset (a) with fixed min-util = 12% and various min-uconf and (b) with various min-util and fixed min-uconf = 70%.