Minimum Threshold Determination Method based on Dataset Characteristics in Association Rule Mining

The process of extracting data to obtain useful information is known as data mining. Furthermore, one of the promising and widely used techniques for this extraction process is association rule mining. This technique is used to identify interesting relationships between sets of items in a dataset and predict associative behavior for new data. The first step in association rule mining is the determination of the frequent item set that will be involved in the rule formation process. In this step, a threshold is used to eliminate items excluded in the frequent itemset which is also known as the minimum support. Furthermore, the threshold provides an important role in determining the number of rules generated. However, setting the wrong threshold leads to the failure of the association rule mining to obtain rules. Currently, the minimum support value is determined by the user. This leads to a challenge that becomes worse for a user that is ignorant of the dataset characteristics. In this study, a method was proposed to determine the minimum support value based on the characteristics of the dataset. Furthermore, this required certain criteria to be used as thresholds which led to more adaptive rules according to the needs of the user. The results of this study showed that 6 from 8 datasets, obtained a rule with lift ratio>1 using the minimum threshold value that was determined through this method.


Introduction
The current developments led to large quantities of data growth which were accessible from various locations everywhere at all times [1]. Data availability is a huge asset for an organization because it contains a lot of useful information. Therefore, Data Mining is a way to extract this useful information and patterns [1][2][3][4][5][6]. Furthermore, the Association rule is one of the most basic study topics widely used in Data Mining [1][2][3][4][5][7][8][9][10][11]. It is an important data analysis method that discovers and identifies interesting relationships between sets of items in a dataset and predicts association relationships for new data [7,8,12].
The basic concept of the association rule is to generate rules based on items with frequent occurrence in a transaction. This includes two main processes, namely the determination of frequent itemset and the process of forming rules. A frequent itemset is a collection of items that have a higher frequency of occurrence compared to the threshold value specified in the transaction. This value is also known as the minimum support. The real-time applications of the association rule have several challenges ranging from the presence of very large, multiple, and heterogeneous data sources to difficulty in the determination of the minimum support [7]. Furthermore, the first step in the association rule is to determine the minimum support value [13,14]. Currently, this value is determined by the user despite the difficulty associated with this process. Another difficulty is that the user is ignorant of the dataset characteristics to be searched during this process [3,6,11,[15][16][17][18].
The minimum support value has an important role in determining the value of several rules generated [3]. However, determining a wrong value leads to the failure of the association rule to obtain the required rule [19]. Furthermore, determining a value that is too low leads to the involvement of too many items in the rule formation process.
Conversely, when a value that is too high is obtained, fewer items are involved which leads to the loss of a lot of information. The minimum support values when compared in terms of two factors namely, time and memory showed that a value that is too low will require more of these two factors when compared to a higher value [6,11,20]. Currently, the method used to determine the minimum support is based on the intuitiveness of the user.
The association rule process is repeated through the change of the minimum support value when the rule obtained does not match. However, this does not guarantee that a rule will be generated with the input minimum support value.
Decision-makers are required to make the right strategic choices which lead to the adjustment of current conditions which are full of volatility, uncertainty, complexity, and ambiguity. This is known as the VUCA (Volatility, Uncertainty, Complexity, Ambiguity) world [21]. Furthermore, the current conditions also demand the adaptive transformation of the association rules to meet the needs of the users. Decision-makers have different criteria which are used to obtain the information they need. Therefore the rule formation process should pay attention to the criteria desired by the users to obtain adaptive Rules [22]. Furthermore, to meet these needs, the determination of frequent itemset should not only be based on the frequency of occurrence of an item but also involve another criterion called item utility [10,[23][24][25]. Therefore, the resulting rule will be adaptive according to the criteria desired by the user.
This study which proposes a method to determine the minimum support value based on the characteristics of the dataset and other criteria can also be used as assessments in the process of forming the rule. The main contributions of this study include: 1. The proposition of a method to determine the minimum support value based on the characteristics of the dataset.
2. The generation of a minimum support value-based not only on the frequency of occurrence of items but also based on certain criteria affecting the rule formation process such as price, profit, or item usability value.
3. The generation of a minimum support value certainly forms a rule that does not require the user to determine this value at the beginning.
This study is divided into several parts. Parts II, III, IV and V describe and explains related studies, proposed methods, experimental results and discussion and conclusions respectively.

Association Rule
The association rule mining was first proposed in a study by Agrawal [26,27]. This study developed a focus on different topics ranging from high utility itemset [23,25,[28][29][30][31], Top-K [5,11,32], Skyline [6,10,33], Multicriteria [34][35][36] and Meta association rules [37][38][39]. Furthermore, the main concept of association rule mining can be formally defined as follows: I = {i1, i2, . . ., im} is a set of items and D is a set of transactions T, where a set of transactions T is also a set of items, therefore, T ⊆ I. Furthermore, provided that A is a set of items, Transaction T is said to contain A if and only if A ⊆ T. Association rules are from A  B, where A ⊆ I, B ⊆ I, and A ∩ B = Ø. In addition, rule A  B has support in transaction set D provided that s% of transactions in D contain A ∪ B [4,22,40]. This support is shown by the occurrence frequency of items which is calculated by observing the ratio between the frequency of transactions containing itemset A divided by the total transactions. In general, it can be seen in the formula below [37]: Confidence is another threshold used in determining the rule apart from the support value. It is the ratio between the number of transactions containing items A and B divided by transactions containing item A for rule AB.
The confidence value of rule A  B is obtained by the formula [37]: Where: The general framework of the association rule is to extract a rule with a support value for an item that exceeds the minimum support and confidence value. Therefore, this rule exceeds the minimum confidence value specified by the user. In this case, it can be stated that A  B is included in the frequent and confidence category (strong rule) provided that Supp(AB) ≥ minsupp and Conf(AB) ≥ minconf respectively.
To evaluate rule, lift ratio can be used [35,36,[41][42][43][44][45][46][47][48]. Lift ratio is the ratio between the support value of the rule with the antecedent and consequent support value. The higher of lift ratio value, the more interest rule or called the strong rule. A rule is called interest and strong rule if the lift ratio value > 1 because it shows that is a positive correlation between the premise and conclusion of this association rule [36,48]. The lift ratio value can be calculated by the formula [36,[41][42][43]47,48]:

Minimum Support
The basic concept of the association rule requires the user to specify a minimum support value at the beginning.
This value usually applies uniformly to all items, although in reality, different items may have different criteria for assessing them. Therefore, studies about multiple minimum support which state that the support value should vary for different items have emerged [9,23,49,50]. However, the implementation of this system adds a task for the user, which is to determine the minimum support for each item.
Furthermore, the difficulty of determining the minimum support value by the user has led to a new field of study, namely association rules without the use of minimum support such as Top-K [5,11,19,32,51] and Skyline [6,10,33,52]. The Top-k association rule does not require the minimum support value because in this method the user is only asked to determine the k value, which is the number of rules that will be generated in the rule formation process. Therefore, it is easier for users to determine the k value because they explicitly know the number of rule results they want to obtain.
The Skyline algorithm was first proposed by Borzsony [52] and later developed by Goyal [33]. It is a point that is not dominated by other points [52]. This algorithm was combined by Jerry Chun-Wei Lin [10] and Jeng-Shyang Pan [6] to produce association rules. Furthermore, this study does not use minimum support but instead makes use of the maximum utility (utilmax) obtained from each iteration performed by the utility list structure.
Based on the results of the previous review [20], the association rules require a minimum support value to reduce the items involved in the rule formation process. Furthermore, the existence of this threshold can reduce the time and memory required in the rule formation process. Therefore, regardless of the term, starting from Minimum Utility, Maximum Utility to Minimum Support, this threshold is required for the association rule process. Meanwhile, processes without the threshold will involve all the items present and require more time and memory, which will lead to rules that may not be as desired.

The Proposed Model
To determine the minimum support value in the association rule, a special method is needed to determine the value according to the characteristics of the dataset which involves certain criteria according to the desires of the user. This study proposed an adaptive support method to answer these needs, as shown in Figure 1.

Algorithm.1 Adaptive Support Algorithm
In the adaptive support model, the determination of the minimum support value is based on several factors which include:

Characteristics of the dataset
In determining the minimum support value, the user should know in advance, the characteristics of the dataset that will be processed for rule formation. This is because several characteristic factors of the dataset will affect the suitable minimum support value. Furthermore, for an adaptive support mode, the factor used to determine the minimum support value is shown from the number of items contained in the transaction, the number of transactions, the average number of items in each transaction, and the support value for each item.

Specific criteria (utility for each item)
To be able to produce adaptive rules, a criterion is required as an assessment for an item known as a frequent itemset with the right to be involved in the rule formation process. Furthermore, these criteria can be determined by the user and each item has its own criteria values. For example, a user who wants to get a rule for the most expensive item has an involved criterion such as, the item price. In addition, another example is when a user wants a rule with the biggest profit then, the criterion for the item involved is the profit from each item.
Based on both types of inputs, the calculation process is carried out according to algorithm 1 to obtain adaptive support. The calculation stages are as follows: 1. Calculation of the support value for each item in the dataset with the following formula: 2. Calculation of the utility for each item in the dataset with the following formula: 3. Calculation of the average utility for the entire transaction with the following formula: () sup ||

Util d ave D
  [6] 4. Calculation of the minimum threshold value used for the rule formation process which is the average utility value divided by the total existing transactions through the following formula: sup min sup || ave D  [7] 5. Performance of the rule formation process with existing methods through the apriori algorithm, fpgrowth, or other algorithms

Data Experiment
The special dataset for the association rule case used in this study was obtained from SPMF [53]. The dataset criteria used can be seen in table 1.

Result
The proposed adaptive support method was carried out on 8 datasets according to  The trial of the proposed adaptive support method used two basic algorithms in the association rule, namely Apriori and Fpgrowth [10]. The Apriori algorithm used a level-wise approach and generated candidate items for each level [26]. Meanwhile, the fpgrowth algorithm used the pattern growth method but did not generate candidates for each level. After the elimination of itemset with minimum support, the next step was to obtain a Frequent Pattern-Tree [54]. The trial was carried out from the highest minimum support value at 100% and then repeated while a reduction of this value occurred. All minimum support values are not tested on all datasets because the number of rules is different. The more rules that are generated, the more difficult it will be in the decision-making process. For example, in the connect dataset with a minimum support value of 70%, it produces a rule 392,469,141 using the fpgrowth algorithm and consumes a lot of resources (runtime and memory) so the test is stopped. Table 3-6 shows the test results of each dataset for each minimum support value using the a priori and fpgrowth algorithms. The blue color in the table is the minimum support value proposed by the adaptive support method.     0  0  175  0  10%  1213180  0  0  168  0  20%  37757  0  1058700  0  77  0  30%  73  0  64794  0  44  0  40%  4  0  6297  0  7  0  50%  1431849  3  0  816  0  7  0  60%  121658  0  0  159  0  7  0  70%  6125  0  0  35  996275  0  4  0  80%  367  0  0  22  45541  0  0  0  90%  4  0  0  9  546  0  0  0  100%  0  0  0  2  0  0  0  0 Based on tables 3-6, it was shown that for each different dataset, the same minimum support value led to a varied number of rules. This was because of the dataset characteristics consisting of the number of items, the average item in each transaction, and the different density values. Furthermore, the trials that have been carried out showed that the higher minimum support value led to a smaller number of rules and runtimes and vice versa. The minimum support value generated by the adaptive rule method when compared with the results of trials using the fpgrowth and apriori algorithms is shown in Figure 2. adaptive support can generate a rule and if viewed from the quality, adaptive support produces a rule that has a lift ratio value > 1. In addition, with the proposed adaptive support value, users no longer need to guess the appropriate minimum support value that can generate rules. So that there is no longer a possibility that with the specified minimum support value, it does not get a rule, or the number of rules is 0 and must repeat the experiment with another minimum support value. Figure 3 shows that the smaller the minimum support value, the more rules are generated. The red line in Figure   3 shows the proposed minimum support value based on the adaptive support method.

Conclusion and Future Work
The minimum support value is important and has a big influence on the rule formation process in the association rule. The errors obtained when determining this resulting rule were not desired. Furthermore, the determination of this value was difficult especially if the user is ignorant of the dataset characteristics as a factor which was used as a reference in determining the minimum support value. This is because datasets with a high level of density required a larger minimum support value when compared to datasets with low density. This density level is the average value of the occurrence frequency of each item in the dataset. Therefore, an adaptive support model which determined the minimum support value based on the characteristics of the dataset was proposed. In addition, certain criteria leading to adaptive rules following the desires of the user were included.
From the study results on 9 datasets, 8 datasets obtained a rule based on the minimum support value suggested by the adaptive support model. In the future, the author will integrate the multicriteria system model [55] and this adaptive support method to obtain a completely adaptive rule model [22].