This case study explains the use of association rules for outlining the main spots and zones which are highly prone to accidents in Belgium. According to the statistics, the rate of traffic accidents in Belgium was as high as 50,000 causing injury to around 70,000 people and resulting in deaths of approximately 1,500 people. These high rates of accidents not only resulted in increase of insecurity on roads but also affected the economic costs associated with these accidents. Therefore, traffic safety became a serious issue of concern for the Belgium government.
Initially, statistical methods were being used to analyze the accidents registered but soon it was realized that association rules is a better alternative for finding the relevant variables which can help in understanding the situations in which the accidents took place.
Data:
The data under the study is about the traffic accidents that occurred in the region of Flanders (Belgium) in the year 1999. This data was obtained from the National Institute of Statistics (NIS) and had 34,353 accident records for analysis. This data stored information about the course of the accident along with various traffic, environmental, human, road and geographical conditions. The various attributes of these conditions amounted to the total of 45 on average. Maximum speed, weather, time of accident, road obstacles, alcohol, location, etc, were some of those attributes. When this data was first analyzed, it became clear that some of the attributes in the dataset have a constant value for all the accidents but this will have no effect on the association rules discovered because the association rule discovery algorithms count the frequency of the attributes in the dataset.
Mining Process:
The mining process was divided into three steps: Pre-processing step in which the data was prepared in the form which could be used by the association algorithm, Mining step in which all the association rules were generated and the Post-processing step in which the interesting association rules were identified.
These steps in detail are as follows:
a) Pre-processing Step:
The very first step in pre-processing involved the assignment of a location parameter to each accident so that the high frequency accident locations could be outlined from low frequency accident locations. This location parameter corresponds to a unique geographical location. This step was carried out by assigning the unique road identification number and the kilometer mark to accidents which took place either in district or in province. The other accidents were assigned a location using the name of the street and the city in which the accident took place.
Second step included the selection of two different datasets in order to determine association between the different accidents attributes. The first analysis was done on the data related to high frequency accident locations and the second on the data corresponding to low frequency accident locations. The comparison of the analysis of these two different datasets helped in determining the accident variables prevalent in the high frequency accident locations. For the first analysis, the criterion of five accidents per location was set for identifying the locations which are highly prone to accidents which resulted in the total of 3368 traffic accidents. The remaining accident records amounting to 30,985 were included in the second analysis for low frequency accident locations.
In the next step, all the continuous variables that existed in the dataset was separated into individual variables for generating the association rules in the second step of mining process. A continuous attribute was divided into different intervals or discrete attribute by grouping them into partitions. These intervals for the attribute were either obtained from the knowledge of some expert or were generated from the method called Equal Frequency Binning.
Lastly, the pre-processing of the nominal values was performed by converting those values into binary equivalent for the attributes.
b) Association Rules Generation:
Minimum support (minsup) and minimum confidence (minconf) are the foremost requirements for the generation of association rules. Using the trial and error methods it was decided that the minimum support for the analysis of two datasets will be 5% and the minimum confidence will be 30%. This means that only those itemsets will be considered frequent which occurs at least 165 times in the accidents. The minimum support was set too high so that only non-trivial rules are generated. Also, only those rules will be considered reliable whose consequent occurs at least once out of the three times that the antecedent appears.
After applying the association algorithm on both the data sets, the results obtained for the high frequency accident locations included “187,829 frequent item sets of maximum size 4 for which 598.584 association rules could be generated”. The result obtained from analysis of second dataset for low frequency accident locations included “183.730 frequent item sets of maximum size 4 for which 575.974 association rules could be generated”.
c) Post-processing of Association Rules:
The last step in mining process was the post processing step in which the generated association rules in the previous step were further evaluated based on the interestingness criteria in order to narrow down the number of association rules initially generated. After carrying out the post process step using the lift value and eliminating the trivial rules, only 14,690 association rules were left for the high frequency accident locations and 77,282 association rules were left for the low frequency accident locations. But still the problem for finding the discriminating factor between the high and low frequency accident locations remained. So, a measure based on deviation of rules discovered for different accident locations was used to evaluate the interestingness of the rule. This measure is as follows:
“ I = Sh-Sl
___________
Max{Sl,Sh}” [pdf10]
Here I stand for interest. “The nominator Sh-Sl measures the difference in support for the rules in the high frequency accident data set (Sh) and the low frequency accident data set (Sl). The expression max {Sl, Sh} is called the normalizing factor as it normalizes the interestingness measure onto the scale [-1, 1]”.
Results:
After the analysis of the two datasets, the association rules obtained, which were common to both high frequency accident locations and low frequency accident locations, were further post-processed on the basis of interestingness measure which resulted in the total of 50 discriminating association rules. These results showed that the rule having high interestingness value may have low lift value and vice versa, thus lacking correlation. Exhibit 3 and Exhibit 4 explained that rules having high lift value and low interestingness value were common to both high and low frequency accident locations.
Exhibit 4 divided the association rules according to three categories which are: highest interestingness, low lift value and high life value. In the first section, the 10 rules based on highest interestingness values indicated that the geographical conditions was one of the most discriminating variable between high and low frequent accident locations. For example, the roadways outside the inner city having separated lanes are a characteristic of black spots and black zones. It was also interpreted from the result that the driver involved in accidents should be between 30 to 45 years of age. The second section includes 10 association rules based on high lift value. These rules indicated accident characteristics like number of people involved in accident and mostly apply to low frequency accident locations than that to high frequency. The 10 association rules in the third section based on small lift value explained that the accident patterns mainly correspond to human characteristics and discriminates a little between high and low frequency accident locations. From the observation of the support factor in all these parts of the table, it was clear that support remains stable in the case of low frequency accident locations but it was quite high for high frequency accident locations in first section and quite low for the second and third parts. Therefore, an increase in the interest value and discriminating characteristic of these rules are features contributing to the occurrence of accidents in high frequency accident locations. Apart from this, there were some association rules which mainly related to high frequency accident locations and do not apply to low frequency accident locations and so are called as discriminating characteristics between high and low frequency accident locations.
Conclusion:
The case study was concluded stating that the analysis of the datasets helped in finding out the combination of attributes which are together responsible for the occurrence of accidents in the high frequency accident locations. However, a lot more is still left to be discovered which include extent of casualties from these accidents. It also gave scope for future research on the discriminating factors between high and low frequency accident locations. As of now, the only suggestion was to appoint special traffic police in areas that are highly prone to accidents under special circumstances in which these accidents take place. These circumstances were described in the form of rules in tables.
Showing posts with label Applicatons of Association Rule. Show all posts
Showing posts with label Applicatons of Association Rule. Show all posts
Tuesday, September 30, 2008
CASE STUDY 1
Retail organizations generate large volume of data called POS (Point of Sale) data through daily transactions. This data when collected and analyzed can be used to make important business decisions and plan strategies for innovations and competitive edge over their competitors. It is not possible to analyze this data manually and hence techniques such as data mining are used. To analyze these data it is necessary to use an appropriate framework, tool or environment. In this case study we discuss the use of Association rules to find the associations that exist between products in the market basket data.
Association rules technique has been widely used in retail industry with the name “Market Basket Analysis”. This technique when applied can deliver measurable benefits to the organizations such as improved profitability and improved quality of service. The transactional data can be quite challenging for the Data Mining approach due to it’s:
Massiveness: The transactional data collected is vast with thousands of transactions.
Sparseness: A basket contains only a small fraction of the total possible items.
Heterogeneity: Variability in purchasing behavior across different individual and purchasing pattern of an individual over a certain period of time.
Strategy:
Due to the massive amount of data collected it is difficult to explore it for analysis purpose as we can have as many as 4 trillion possible rules generated from 10,000 transactions. In other words, if the transactions are accumulated over a longer period of time then it will become all the more difficult to analyze the collected data. To overcome this situation the divide-and-conquer strategy can be powerful. It is based on problem decomposition, solution and aggregation. This means that it will be more advantageous if data is collected over smaller time intervals and then analyzed. The output is collected over each of these small intervals and then combined to solve the entire problem. All this is done by creating a separate database to store the results collected over smaller intervals and then retrieving interesting rules. A rule is interesting if it remains stable and satisfies a minimum threshold within a specific number of intervals. This strategy allows extraction of interesting rules with good support and confidence on a daily basis. Also, it helps in dumping the raw data after analysis, which can reduce the unwanted data in the database.
This strategy was applied to two supermarket stores in Porto Alegre, Brazil. Data corresponding to the purchases made by consumers over a period of one hundred and twenty days were used.
Mining Process:
The transactional data were recorded and associations were generated on a daily basis. Certain criterions were defined to reduce the number of rules discovered. The aggregation level was defined to treat products mainly on their functions and far from brand and major physical aspects. This approach enabled to reduce the number of transactions to 4500 and thus reducing the total number of possible rules to 10 million. But as a trade of to this, the approach required transformation of each product prior to mining. This considerably reduced the time spent on analysis although including extra time to get the data ready. Also, by the time of this conversion, all the operational transactions were removed to leave behind only the useful information for data mining.
In order to exclude the products that are not important in the total sales of the stores, the daily extracted rules were minimized by setting the extraction support parameter to a minimum limit of 1%. Therefore, the products below this minimum limit were excluded and were not considered for the rule formation. This step was also helpful in excluding the groups that didn’t represent 1% of the total number of transaction for that day. The products in the special offers were excluded from the base of rules for the number of days the products were in the special offer. The products in special offer were analyzed in a separate database so that they do not affect the final results of associations.
Results:
The resulting rules base stored more than 6000 extracted rules. The rules differed in the frequency of their occurrence. The resulting rules for both the stores were compared. In this the first store was selected as a reference to select the associations and then their presence was checked in the second store. There were many associations found common to both the rules base but for space constraints only six associations were shown. The associations were classified as “Usual and Non-usual”. Usual products are the one with shared use or application which justifies the choice of consumers whereas Non-usual products have no direct link between the associated product in terms of application or use. It is seen that both the “Usual and Non-usual products” have different usage patterns and intensities in both the stores. For the Usual products the stability in both the stores is recorded as around 100%. But the average of the confidence differs for both the stores. This indicates that the associations though stable in both the stores had different intensities. In case of the Non-usual products both the stability and confidence factors fluctuate considerably. In store A the associations for Non-usual products were greater than 95% whereas in store B the associations were well below the 95% suggested for a stable association. This study of the Non-usual products reveals that their associations are peculiar to the store in which they’ve been found and may not be found in another store. It also reveals that the Usual products’ associations can repeat themselves in the stores around the same culture. Thus, it can be concluded that the associations for the usual products tend to repeat themselves in a group of consumers of similar profile whereas for the association of the Non-usual products is specific to the store following the same degree of consumer specifics. The results also revealed that there were huge fluctuations in the occurrences of the associations of both “Usual and Non-usual products” in store B as compared to store A. But there are no significant differences in the confidence of the products in both Store A and Store B. This meant that confidence cannot be used as a classification criterion.
Conclusion:
From the above case study, it was concluded that association rules enable the retail organizations to analyze the data collected from the transactions to make intelligent decisions. The technique can be helpful in finding interesting associations from their transaction data. It can also be useful in cross selling of the associated products and carefully plan promotions for the products. It also helps in setting up the margins of profits of the associated products. But it is difficult to classify customers into specific classes and to set commercial value for the customers. The technique does not provide precise information, as the quantity involved is not addressed. This inclusion of quantity in the analysis can lead to better promotions and even increased profits.
Association rules technique has been widely used in retail industry with the name “Market Basket Analysis”. This technique when applied can deliver measurable benefits to the organizations such as improved profitability and improved quality of service. The transactional data can be quite challenging for the Data Mining approach due to it’s:
Massiveness: The transactional data collected is vast with thousands of transactions.
Sparseness: A basket contains only a small fraction of the total possible items.
Heterogeneity: Variability in purchasing behavior across different individual and purchasing pattern of an individual over a certain period of time.
Strategy:
Due to the massive amount of data collected it is difficult to explore it for analysis purpose as we can have as many as 4 trillion possible rules generated from 10,000 transactions. In other words, if the transactions are accumulated over a longer period of time then it will become all the more difficult to analyze the collected data. To overcome this situation the divide-and-conquer strategy can be powerful. It is based on problem decomposition, solution and aggregation. This means that it will be more advantageous if data is collected over smaller time intervals and then analyzed. The output is collected over each of these small intervals and then combined to solve the entire problem. All this is done by creating a separate database to store the results collected over smaller intervals and then retrieving interesting rules. A rule is interesting if it remains stable and satisfies a minimum threshold within a specific number of intervals. This strategy allows extraction of interesting rules with good support and confidence on a daily basis. Also, it helps in dumping the raw data after analysis, which can reduce the unwanted data in the database.
This strategy was applied to two supermarket stores in Porto Alegre, Brazil. Data corresponding to the purchases made by consumers over a period of one hundred and twenty days were used.
Mining Process:
The transactional data were recorded and associations were generated on a daily basis. Certain criterions were defined to reduce the number of rules discovered. The aggregation level was defined to treat products mainly on their functions and far from brand and major physical aspects. This approach enabled to reduce the number of transactions to 4500 and thus reducing the total number of possible rules to 10 million. But as a trade of to this, the approach required transformation of each product prior to mining. This considerably reduced the time spent on analysis although including extra time to get the data ready. Also, by the time of this conversion, all the operational transactions were removed to leave behind only the useful information for data mining.
In order to exclude the products that are not important in the total sales of the stores, the daily extracted rules were minimized by setting the extraction support parameter to a minimum limit of 1%. Therefore, the products below this minimum limit were excluded and were not considered for the rule formation. This step was also helpful in excluding the groups that didn’t represent 1% of the total number of transaction for that day. The products in the special offers were excluded from the base of rules for the number of days the products were in the special offer. The products in special offer were analyzed in a separate database so that they do not affect the final results of associations.
Results:
The resulting rules base stored more than 6000 extracted rules. The rules differed in the frequency of their occurrence. The resulting rules for both the stores were compared. In this the first store was selected as a reference to select the associations and then their presence was checked in the second store. There were many associations found common to both the rules base but for space constraints only six associations were shown. The associations were classified as “Usual and Non-usual”. Usual products are the one with shared use or application which justifies the choice of consumers whereas Non-usual products have no direct link between the associated product in terms of application or use. It is seen that both the “Usual and Non-usual products” have different usage patterns and intensities in both the stores. For the Usual products the stability in both the stores is recorded as around 100%. But the average of the confidence differs for both the stores. This indicates that the associations though stable in both the stores had different intensities. In case of the Non-usual products both the stability and confidence factors fluctuate considerably. In store A the associations for Non-usual products were greater than 95% whereas in store B the associations were well below the 95% suggested for a stable association. This study of the Non-usual products reveals that their associations are peculiar to the store in which they’ve been found and may not be found in another store. It also reveals that the Usual products’ associations can repeat themselves in the stores around the same culture. Thus, it can be concluded that the associations for the usual products tend to repeat themselves in a group of consumers of similar profile whereas for the association of the Non-usual products is specific to the store following the same degree of consumer specifics. The results also revealed that there were huge fluctuations in the occurrences of the associations of both “Usual and Non-usual products” in store B as compared to store A. But there are no significant differences in the confidence of the products in both Store A and Store B. This meant that confidence cannot be used as a classification criterion.
Conclusion:
From the above case study, it was concluded that association rules enable the retail organizations to analyze the data collected from the transactions to make intelligent decisions. The technique can be helpful in finding interesting associations from their transaction data. It can also be useful in cross selling of the associated products and carefully plan promotions for the products. It also helps in setting up the margins of profits of the associated products. But it is difficult to classify customers into specific classes and to set commercial value for the customers. The technique does not provide precise information, as the quantity involved is not addressed. This inclusion of quantity in the analysis can lead to better promotions and even increased profits.
Subscribe to:
Posts (Atom)