Improving Association Rule Mining Using Clustering-Based Data Mining Model for Traffic Accidents

2.1 Association rule

Association rule mining is an important branch of data mining research. Association rule mining used to find an association hidden in the interest of large data sets.

The topic of mining association rules was first proposed by Agrawal et al. [3] and others in 1993. The association rules mining process mainly consists of two steps [5]. In the first step, all items whose support is greater than the minimum support are found in the transaction database, i.e. all frequent itemsets. In the second step, the expected association rules are generated from these frequent itemsets.

The principle of the search for association rules is based on three basic factors: support, confidence, and lift. Its goal is to reduce the very large number of association rules generated, some of which are not important [6].

Support [7]: it is the number of transactions that contain elements in the {X} and {Y} parts of the rule, as a percentage of the total number of transactions, it is defined by the following rule:

$\text { Support }=\frac{\operatorname{Count}(X U Y)}{N}$

onfidence [7]: Measures how often each element in Y occurs in transactions that also contain elements in X and is defined by the following rule:

$\text { Confidence }=\frac{\operatorname{Count}(X U Y)}{\operatorname{Count}(X)}$

Lift [7]: It is a measure of the importance of the rule and is defined by the following rule:

$\operatorname{Lift}(X \rightarrow Y)=\frac{\operatorname{Support}(X U Y)}{\operatorname{Support}(X) * \operatorname{Support}(Y)}$

Based on the previous rules, association rules are generated that achieve a support value greater than a threshold called minsup, and the user defines a confidence value greater than a threshold called minconf.

2.2 FP-Growth algorithm

It is one of the most important algorithms in the field of association rules, which is a further development of the Apriori algorithm. The resulting tree structure aims to store compressed and important information about recurrent data to develop an effective FP -growth tree for recurrent models [6]. This algorithm differs from Apriori algorithm in that it reduces the size and time required to generate the rules [8].

The FP-growth algorithm scans the database only twice. FP -growth algorithm is a depth-first search algorithm combined with direct counting and uses the recursive strategy of pattern growth. It does not need to generate candidate sets, instead the transaction database is compressed into a tree structure that stores only the frequent elements. All frequent elements are obtained by recursive mining the FP tree [6].

In this chapter, we will explain the methodology that aims to design a workflow whose task is to use data mining methods to access the factors that cause accidents. The problem with using algorithms for correlation rules for traffic accidents is always that there are rules for a certain classification of data that can be useful and valuable, and therefore cannot be observed in the number of a large number of extracted rules, which is the main obstacle for decision makers.

We used RapidMiner software to design the processes we will apply to the extracted data. RapidMiner is a data science software platform developed by the company of the same name that provides an integrated environment for data preparation, machine learning, deep learning, text mining, and predictive analytics. It is used for business and commercial applications as well as for research, education, training, rapid prototyping and application development and supports all steps of the machine learning process, including data preparation, visualization results, model validation and optimization.

4.1 Methodology design

Table 2. Time category

Before we start designing the system, we will transform some data types to prepare the data:

1- The age of the driver and the age of the vehicle are converted from numerical form to textual form, so that each set of ages is converted to a textual form that expresses in decades. An example of this is to convert the age between 20 and 30 to the third decade and so on.

2- Convert the accident time into eight sections instead of the time value, as shown in Table 2.

Association rules are generated based on the K-Means algorithm cluster to separate data after each clustering and then generate a dataset for each clustering, and it is designed by RapidMiner application. Our proposed methodology will follow four basic steps:

1- Using the K-Means algorithm to extract clusters.

2- Extracting the data table for each cluster.

3- Traversing each table and extracting the association rules by the FP -Growth algorithm for each cluster.

4- Collecting the association rules in one place.

In this design, the following methodology was followed:

4.1.1 Preparing data as shown in Figure 1

1. Load dataset:

Retrieve traffic accidents data from the database.

2. Select Attributes:

Select the elements to determine the common attributes between the elements. The following elements have been selected which are among the most important elements: (severity of the accident, age of the driver, gender of the driver, time of the accident).

1.png

Figure 1. Initializing the data, applying the methodology

2.png

Figure 2. Illustrates the sub-process of applying clustering and generating data for each cluster

3.png

Figure 3. Filter clusters by cluster value

4.png

Figure 4. Applying FP-Growth to each cluster dataset

5.png

Figure 5. Applying the FP -growth algorithm to each cluster dataset

6.png

Figure 6. Create association rules

7.png

Figure 7. Collect rules in one dataset

3. Filter examples:

Filtering data and selecting fatal and serious accidents and their number 2941 rows.

4. Nominal to Numeric:

Converts the specified non-numeric values to a numeric type.

4.1.2 Apply methodology:

The process of applying the methodology:

1. Clustering using the K-Means algorithm:

Selection of the Euclidean distance and generation of data tables for each cluster as shown. Figures 2 and 3.

2. FP-Growth Process:

Passing through each data table of each cluster to perform the process of generating the association rules as shown in Figure 4.

3. FP-Growth:

Extract the repeated models using the FP-Growth algorithm to generate the FP-Tree growth tree with minsup=0.1 as shown in Figure 5.

4. Create Association Rule:

Generate association rules from the resulting tree, using the confidence scale to determine the required rule strength with minconf = 0.7, as shown in Figure 6.

5. Collect rules:

In this process, there is a for loop for each result of the generation association rule to collect all the rules in one dataset as shown in Figure 7.

4.2 Methodology result

By applying the previous design to the UK data by choosing the number of clusters K=2, 271 rules were generated, with two clusters generated, the first cluster containing the male incidents and the second cluster containing the female incidents. The clusters were generated within 1 second and the following results in Figure 8 were generated for the clusters:

8.png

Figure 8. Cluster results for K=2

Table 3 shows the first 10 rules generated by the proposed methodology, sorted by the lift value. From the clustering results, female accidents account for about 20% of the total accidents. However, we have three rules related to females due to the application of the previous methodology.

Using this methodology, we can generate more interesting association rules by increasing the number of clusters. For example, the methodology was implemented with a number of clusters K=6, and the clusters were generated within 1 second, as shown in Figure 9.

Table 3. The first ten rules generated by the set K=2

Table 4. The first ten rules generated by set K=6

9.png

Figure 9. Cluster results for K=6

We were able to generate 1387 rules. Table 4 shows the first ten rules generated by the proposed methodology with the set K=6, sorted by the lift value.