Data mining and classification for traffic systems using genetic network programming

Created by W.Langdon from gp-bibliography.bib Revision:1.7642

@PhdThesis{HuiyuZhou:thesis,

• author = "Huiyu Zhou",
• title = "Data mining and classification for traffic systems using genetic network programming",
• school = "Waseda University",
• year = "2011",
• address = "Japan",
• month = feb,
• keywords = "genetic algorithms, genetic programming, genetic network programming",
• URL = "http://jairo.nii.ac.jp/0069/00020480/en",
• URL = "http://dspace.wul.waseda.ac.jp/dspace/bitstream/2065/36316/3/Honbun-5575_00.pdf",
• URL = "http://dspace.wul.waseda.ac.jp/dspace/bitstream/2065/36316/1/Gaiyo-5575.pdf",
• URL = "http://dspace.wul.waseda.ac.jp/dspace/bitstream/2065/36316/2/Shinsa-5575.pdf",
• URL = "http://dspace.wul.waseda.ac.jp/dspace/bitstream/2065/36316/4/Honbun-5575_01.pdf",
• size = "141 pages",
• abstract = "Since the increase of the road traffic in modern metropolis, the need for traffic prediction systems becomes significant, while the traffic prediction aims at an accurate estimate of the traffic flow as an important item in recent traffic control systems. Concretely, the traffic prediction system analyses data, especially real-time traffic data, predicts traffic situations, and its major role is to forecast the congestion levels in advance of hours and even days. Therefore, the traffic prediction system is becoming the key issue in the advanced traffic management and information systems, which reduces traffic congestion and improve traffic mobility.

  Vast amount of traffic data are currently available using various components of the intelligent transportation system(ITS). Satellite-based automatic vehicle location technologies such as Global Positioning System (GPS) and cellular phones can determine the vehicle positions at frequent time intervals. These equipments collect the information on the vehicle positions and speeds, which are archived in a large amount of databases, enabling further analysis of the data about the traffic situations such as traffic density patterns.

  The evolutionary computation method named Genetic Network Programming (GNP) has been proposed as an extension of typical evolutionary computation methods, such as Genetic Algorithm (GA) and Genetic Programming (GP). GNP-based data mining has been already proposed to deal with high density databases with large amount of attributes. In order to further extend the proposed data mining method using GNP to the real-time traffic system, time related association rule mining methods have been proposed and studied in this thesis. The extracted time related rules are stored though generations in a rule pool and analysed to build a classifier, based on which the future traffic density information can be provided to the optimal route search algorithm of the navigation systems. Simulation studies on the prediction accuracy of extracted rules and the average travelling time of the optimal route using the future traffic information are carried out to verify the efficiency and effectiveness of the proposed mechanisms. Some analyses of the proposed methods are studied based on these simulation results comparing to the conventional methods.

  Unlike the other traffic density prediction methods, the main task of GNP based time related data mining is to allow the GNP individuals to self evolve and extract association rules as many as possible. What's more, GNP uses evolved individuals (directed graphs of GNP) just as a tool to extract candidate association rules. Thus, the structure of GNP individuals does not necessarily represent the association relations of the database. Instead, the extracted association rules are stored together in the rule pool separated from the individuals. As a result, the structures of GNP individuals are less restricted than the structures of GA and GP, thus GNP-based data mining becomes capable of producing a large number of association rules.",

• abstract = "In chapter 2, a method of association rule mining using Genetic Network Programming (GNP) with time series processing mechanism and attributes accumulation mechanism was proposed in order to find time related sequence rules efficiently in association rule extraction systems. In this chapter, GNP is applied to generate candidate association rules using the database consisting of a large number of time related attributes. In order to deal with a large number of attributes, GNP individual accumulates fitter attributes gradually during rounds, and the rules of each round are stored in a Small Rule Pool using a hash method, then the rules are finally stored in a Big Rule Pool after the check of the overlap at the end of each round. The aim of this chapter is to propose a method to better handle association rule extraction of the databases in a variety of time-related applications, especially in the traffic prediction problems. The algorithm which can find the important time related association rules is described and several experimental results are presented considering a traffic prediction problem.

  In chapter 3, an algorithm capable of finding important time related association rules is proposed, where Genetic Network Programming (GNP) with not only Attribute Accumulation Mechanism (AAM) but also Extraction Mechanism at Stages (EMS) is used. Then, the classification system imitating the public voting process based on extracted time related association rules in the rule pool is proposed to estimate to which class the current traffic data belong. Using this kind of classification mechanism, the traffic prediction is available since the extracted rules are based on time sequences. Furthermore, the experimental results on the traffic prediction problem using the proposed mechanism are presented by the simple traffic simulator.

  In chapter 4, further improvements have been proposed for the time related association rule mining using generalised GNP with Multi-Branches and Full-Paths (MBFP) algorithm. For fully using the potential ability of GNP structure, the mechanism of Generalised GNP with MBFP is studied. The aim of this algorithm is to better handle association rule extraction from the databases with high efficiency in variety of time-related applications, especially in the traffic density prediction problems. The generalised algorithm which can find the important time related association rules is described and experimental results are presented considering the traffic prediction problem.

  Chapter 5 is devoted to a further advanced method for extracting important time related association rules using evolutionary algorithm named Genetic Network Programming (GNP), where Accuracy Validation algorithm is applied to further improve the prediction accuracy. The proposed method provides more useful mean to investigate the future traffic density of traffic networks and hence further help to develop traffic navigation systems. The aim of this algorithm is to better handle association rule extraction using prediction accuracy as one of the criteria and guide the whole evolution process more efficiently, then the adaptability of the proposed mechanism is studied considering the real-time traffic situations using a large scale simulator SOUND/4U. The experiments deal with a traffic density prediction problem using the database provided by the large scale simulator.",

• abstract = "Chapter 6 describes a methodology for extracting important time related association rules using an evolutionary algorithm named fixed step GNPbased association rule mining. And based on the rule pool of the fixed prediction step, it is also proposed that the prediction of the future traffic is combined with a classical routing algorithm. The routing algorithm and BibTeX entry too long. Truncated

Genetic Programming entries for Huiyu Zhou

Citations