An improved approach for association rule mining using a multi-criteria decision support system: a case study in road safety

Data mining is defined as a non-trivial process of identifying valid, novel, potentially useful and ultimately understandable patterns in data [1]. Indeed, it is a vital part of business analytics and the most important trends in information technology. It involves many common classes of tasks (clustering, classification, association rules [2] etc.) which are designed for knowledge discovery in databases (KDD).

Data mining techniques are widely used in several research domains and have provided useful results to guide decision makers. Many researchers [3‐7] have studied the application of data mining techniques in the domain of road accidents through association rules mining. The association rule is a powerful data mining technique for discovering a correlation between variables in the database. It is based on statistical analysis and artificial intelligence. This technique is particularly appropriate for studying road accident data by considering conditional interactions between input datasets, extracting frequent itemsets and then generating the association rules by satisfying certain parameters such as the minimum support and the minimum confidence. In this paper, the goal of the proposed approach is not to optimize road safety, but to generate insights and sufficient knowledge to enable decision makers to make the right optimization decision to avoid dangerous routes and improve road safety. This approach consists of two major steps; a rules generator using the Apriori algorithm to extract association rules, and multi-criteria decision analysis to evaluate and select the interesting rules from the large set extracted.

The rest of the paper is organized as follows: Section 2 describes the related work of data mining and machine learning techniques for accident analysis, while Section 3 describes the proposed methodology for extracting association rules and the integration of multi-criteria decision analysis approach within the KDD process. Section 4 presents the results and a discussion of these. In the last section, we conclude by summarizing the work done in the study and describe the contributions of this work.

According to the World Health Organization (WHO) [8], 1.24 million people die each year on the world’s roads, and as many as 50 million are injured. In addition, the Centers for Disease Control and Prevention (CDCP) have announced that road accidents cost 100 billion in medical care every year. Furthermore, the Ministry of Equipment, Transport and Logistics of Morocco [9] gives the statistics of road accidents between 2004 and 2014, as shown in Table 1. Road accidents involve not only loss of human life but also property damage.

As a review of the literature shows, many data mining techniques have been proposed to analyze road accidents. In this context, Kuhnert et al. used CART and MARS to analyze an epidemiological case-control study of injuries resulting from motor vehicle accidents. They also identified potential areas of risk, largely caused by the driver situation [10]. Ossenbruggen et al. [3] used logistic regression models to analyze the factors involved in accidents, and found that shopping areas were more dangerous than village sites. Sohn et al. [11] used the three data mining techniques of decision trees, neural networks and logistic regression to discover significant factors affecting the severity of Korean road traffic. Subsequently, Mio et al. [12] used a decision tree to analyze the severity of traffic accidents. They found that fatal injury was caused by many factors, among them seat belts, alcohol, and lighting conditions.

Chang and Wong [13] developed a CART model to analyze the relationship between drivers, severity of injury and the highway environment. Sze and Wong [14] used binary logistic regression and logistic regression diagnostics to control for the influences of demographics and the road environment. In addition, Abugessaisa [15] used clustering and classification trees to carry out interactive explorations based on brushing and linking methods in order to detect and recognize interesting patterns. Moreover, Wong and Chang [16] used several methodologies to discover factors involved in the severity of accidents, and found that a dangerous accident was caused by a combination of different factors. Anderson [17] studied the spatial patterns of road accident injury and used the resultant patterns to create a classification system for road accident hotspots. Zelalem [18] studied driver responsibility using the ID3, J48, and multilayer perceptron (MLP) algorithms to discover the related factors, and found that many factors have a direct impact on the severity of accidents, such as license grades and the driver’s age and experience. Pakgohar et al. [19] used CART and multinomial logistic regression (MLR) to explore the roles played by the characteristics of drivers, and found that the CART method provided relatively precise results. Demirel et al. [20] used remote sensing for regional scale analysis and effective management of environmental factors. They concluded that this technology could be useful in the prevention of some type of accidents. Wu et al. [21] used the global positioning system (GPS) in the prevention of collision accidents. Zhang et al. [22] concluded that the lack of use of seat belts and inadequate training were also two important factors. Sanmiquel [5] analyzed the main causes of accidents using Bayesian classifiers and a decision tree.

Other association rule mining algorithms have been widely used in the literature to extract frequent itemsets and build decision rules. These algorithms are based primarily on minimum support and the minimum confidence. However, most of them produce a large number of results, which prevents decision makers from making their own selection of the most relevant ones. It is therefore important to propose an approach that can help decision makers to make their choice. Multi-criteria decision analysis (MCDA) offers a powerful solution; its advantages include taking into account the decision makers’ preferences and a diversity of criteria. This paper proposes an approach to association rule mining-based MCDA for analyzing road accident data.

In this section, we discuss the various steps used in the construction of our proposed methodology. We start by developing the association rule mining, as described below.

Following data cleansing, we select a set of significant records which identify the factors related to road accidents. Then, we apply the proposed approach using two steps. The first is the extraction of association rules from datasets using the Apriori algorithm with the minimum support = 0.33 to extract frequent itemsets (see Fig. 8). This figure illustrates the itemsets by frequency. The results are sensitive to the minimum support introduced in the first step of Apriori algorithm. The second step is to generate the association rules from the frequent itemsets previously extracted. The extracted rules are given in Table 4.

To visualize the extracted rules, we use arulesViz [30] as an R package extension; this implements several known and novel visualization techniques such as matrix-, group-, and graph-based visualization. The frequent itemsets are shown in Fig. 8. The matrix-based visualization technique presents the antecedent and consequent items on the X and Y axes. This technique is enhanced using a grouped matrix, by grouping the extracted rules using clustering; an example of a grouped matrix-based visualization is given in Fig. 9. The group of the most interesting rules according to the lift (this measures how far the antecedent and consequent rules are from independence) are shown in the top left-hand corner of the plot. There is one rule which contains “Driver_sex = M”, and two other items in the antecedent (LHS); the consequent (RHS) is “Accident_type = Fatal”.

Graph-based visualization uses vertices and edges (see Fig. 10). The vertices typically represent items or itemsets, and edges indicate a relationship between rules. Interesting measures are typically added to the plot as labels for the edges.

The Apriori algorithm and its derivatives provide an effective solution for the extraction of association rules. However, these algorithms produce a large number of rules, preventing decision makers from making their own selection of the most interesting rules. To solve this problem, the integration of multi-criteria decision analysis approach is useful in practice for decision makers affected by redundancy in the extracted rules [29‐31]. In this context, we use the ELECTRE TRI method, considering a set of extracted rules as the alternatives and support, confidence and lift as the criteria.

The support used in the first step is to count frequent itemsets using the Apriori algorithm, which satisfies the minimum support requirements defined by the user. This step is generally expensive due to the use of multiple passes over the database. For the second step, after the extraction of association rules in the form of A → B, the support, confidence, and lift of each extracted rule is computed using the Apriori algorithm. We use multi-criteria decision support to prioritize the extracted rules; each method in MCDS is based on the decision matrix (evaluation table), where the values of this table are given by the decision makers (domain expert) according to their preferences. In this case, we used minimum support = 0.33 to count frequent itemsets, and for the MCDS we used the values computed by the algorithm as the preference of decision makers in order to determine the performance of our approach.

Table 5 gives the decision matrix (evaluation table), which lists the rules as rows of the table and the criteria as columns. Then, each rule/criteria combination is scored, with a weight determined by the relative importance of the criteria, and these scores are added to give an overall score for each option. The scores for support and confidence vary between 0 and 1.

Decision matrix analysis is a useful technique for making a decision. It is particularly powerful where there are a number of good alternatives to choose from and many different factors to take into account. Decision matrix analysis helps in deciding between several options where many different criteria are involved.

The second step of ELECTRE TRI is to define a set of profiles according to the decision makers’ preferences; the profiles b ₁ and b ₂ are the limits between categories A and B and categories B and C (see Table 6).

Each alternative is compared to the profiles; the importance of each criterion in decision making is reflected in predefined threshold scores. The preference threshold p, the indifference q, and the veto threshold v are given in Table 7. Moreover, each criterion has a weight k, reflecting its contribution to the final decision.

The third step is the computation of the concordance indexes c _j (a,b _h ) as in Eq. (3) and the discordance indexes d _j (a,b _k ) as in Eq. (5). The results are the outranking relations, which determine the relationship between the rules and profiles. The parameter that determines the preferred situation between the association rules and the profiles b _h is known as the cutting level, and its default value is λ = 0.76. The evaluation of the association rules using assignment procedures is shown in Table 8.

In many countries, road transport often involves accidents, and this affects transport and shipping services. Understanding road traffic is extremely important in improving road safety. In this paper, we propose an effective method for mining strong and relevant association rules from a road accident database. With the objective of identifying the hidden relationships between the most common accidents, the road accident dataset is analyzed using the association rules technique. The proposed method uses efficient mining of association rules. Furthermore, the integration of MCDA within the association rule mining process provides a sustainable solution by selecting only the most interesting rules according to the decision makers’ preferences. In particular, we study a set of rules extracted from the road accidents database, considering the criteria most commonly used in the literature. We conclude that the application of multi-criteria decision analysis to a set of extracted rules can contribute to solving the problem that arises when using traditional algorithms, in terms of redundancy and a lack of interesting rules. Furthermore, the results indicate that human and behavioral characteristics play an important role in the occurrence of all traffic accidents. Finally, the results show that the proposed approach serves its purpose and can provide meaningful information which can help in developing suitable prevention policies for improving road safety.

In further work, a new methodology combining this approach with other optimization methods will be applied in the context of big data, using VANETs, Apache Kafka for streaming, and machine learning to build a predictive model for road safety.