Group method of data handling
Encyclopedia
Group method of data handling (GMDH) is a family of inductive algorithms for computer-based mathematical modeling of multi-parametric datasets that features fully automatic structural and parametric optimization of models.
GMDH is used in such fields as data mining
, knowledge discovery
, prediction
, complex systems
modeling, optimization
and pattern recognition
.
GMDH algorithms are characterized by inductive procedure that performs sorting-out of gradually complicated polynomial models and selecting the best solution by means of the so-called external criterion.
A GMDH model with multiple inputs and one output is a subset of components of the base function (1):
where f are elementary functions dependent on different sets of inputs, a are coefficients and m is the number of the base function components.
In order to find the best solution GMDH algorithm consider various component subsets of the base function (1) called partial models. Coefficients of these models estimated by the least squares
method. GMDH algorithm gradually increase the number of partial model components and find a model structure with optimal complexity indicated by the minimum value of an external criterion. This process is called self-organization of models.
The most popular base function used in GMDH is the gradually complicated Kolmogorov-Gabor polynomial (2):
GMDH is used in such fields as data mining
Data mining
Data mining , a relatively young and interdisciplinary field of computer science is the process of discovering new patterns from large data sets involving methods at the intersection of artificial intelligence, machine learning, statistics and database systems...
, knowledge discovery
Knowledge discovery
Knowledge discovery is a concept of the field of computer science that describes the process of automatically searching large volumes of data for patterns that can be considered knowledge about the data . It is often described as deriving knowledge from the input data...
, prediction
Forecasting
Forecasting is the process of making statements about events whose actual outcomes have not yet been observed. A commonplace example might be estimation for some variable of interest at some specified future date. Prediction is a similar, but more general term...
, complex systems
Complex systems
Complex systems present problems in mathematical modelling.The equations from which complex system models are developed generally derive from statistical physics, information theory and non-linear dynamics, and represent organized but unpredictable behaviors of systems of nature that are considered...
modeling, optimization
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
and pattern recognition
Pattern recognition
In machine learning, pattern recognition is the assignment of some sort of output value to a given input value , according to some specific algorithm. An example of pattern recognition is classification, which attempts to assign each input value to one of a given set of classes...
.
GMDH algorithms are characterized by inductive procedure that performs sorting-out of gradually complicated polynomial models and selecting the best solution by means of the so-called external criterion.
A GMDH model with multiple inputs and one output is a subset of components of the base function (1):
where f are elementary functions dependent on different sets of inputs, a are coefficients and m is the number of the base function components.
In order to find the best solution GMDH algorithm consider various component subsets of the base function (1) called partial models. Coefficients of these models estimated by the least squares
Least squares
The method of least squares is a standard approach to the approximate solution of overdetermined systems, i.e., sets of equations in which there are more equations than unknowns. "Least squares" means that the overall solution minimizes the sum of the squares of the errors made in solving every...
method. GMDH algorithm gradually increase the number of partial model components and find a model structure with optimal complexity indicated by the minimum value of an external criterion. This process is called self-organization of models.
The most popular base function used in GMDH is the gradually complicated Kolmogorov-Gabor polynomial (2):
-
GMDH is also known as polynomialPolynomialIn mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
neural networksArtificial neural networkAn artificial neural network , usually called neural network , is a mathematical model or computational model that is inspired by the structure and/or functional aspects of biological neural networks. A neural network consists of an interconnected group of artificial neurons, and it processes...
and statistical learning networks thanks to implementation of the corresponding algorithms in several commercial software products.
History
The method was originated in 1968 by Prof. Alexey G. Ivakhnenko
Alexey Grigorevich IvakhnenkoAlexey Grigorevich Ivakhnenko was a Ukrainian mathematician. He was an Academician of the National Academy of Sciences of Ukraine....
in the Institute of Cybernetics in KievKievKiev or Kyiv is the capital and the largest city of Ukraine, located in the north central part of the country on the Dnieper River. The population as of the 2001 census was 2,611,300. However, higher numbers have been cited in the press....
(Ukraine).
This approach from the very beginning was a computer-based method so, a set of computer programs and algorithms were the primary practical results achieved at the base of the new theoretical principles. Thanks to the author's policy of open code sharing the method was quickly settled in the large number of scientific laboratories world wide. At that time code sharing was quite a physical action since the Internet is at least 5 years younger than GMDH. Despite this fact the first investigation of GMDH outside the Soviet Union had been made soon by R.Shankar in 1972. Later on different GMDH variants were published by Japanese and Polish scientists.
Period 1968-1971 is characterized by application of only regularity criterion for solving of the problems of identification, pattern recognition and short-term forecasting. As reference functions polynomials, logical nets, fuzzy Zadeh sets and Bayes probability formulas were used. Authors were stimulated by very high accuracy of forecasting with the new approach. Noiseimmunity was not investigated.
Period 1972-1975. The problem of modeling of noised data and incomplete information basis was solved. Multicriteria selection and utilization of additional priory information for noiseimmunity increasing were proposed. Best experiments showed that with extended definition of the optimal model by additional criterion noise level can be ten times more than signal. Then it was improved using Shannon's Theorem of General Communication theory.
Period 1976-1979. The convergence of multilayered GMDH algorithms was investigated. It was shown that some multilayered algorithms have "multilayerness error" - analogous to static error of control systems. In 1977 a solution of objective systems analysis problems by multilayered GMDH algorithms was proposed. It turned out that sorting-out by criteria ensemble finds the only optimal system of equations and therefore to show complex object elements, their main input and output variables.
Period 1980-1988. Many important theoretical results were received. It became clear that full physical models cannot be used for long-term forecasting. It was proved, that non-physical models of GMDH are more accurate for approximation and forecast than physical models of regression analysis. Two-level algorithms which use two different time scales for modeling were developed.
Since 1989 the new algorithms (AC, OCC, PF) for non-parametric modeling of fuzzy objects and SLP for expert systems were developed and investigated. Present stage of GMDH development can be described as blossom out of twice-multilayered neuronets and parallel combinatorial algorithms for multiprocessor computers.
External criteria
External criterion is one of the key features of GMDH. Criterion describes requirements to the model, for example minimization of Least squaresLeast squaresThe method of least squares is a standard approach to the approximate solution of overdetermined systems, i.e., sets of equations in which there are more equations than unknowns. "Least squares" means that the overall solution minimizes the sum of the squares of the errors made in solving every...
. It is always calculated with a separate part of data sample that have not been used for estimation of coefficients. There are several popular criteria:
- Criterion of Regularity (CR) - Least squaresLeast squaresThe method of least squares is a standard approach to the approximate solution of overdetermined systems, i.e., sets of equations in which there are more equations than unknowns. "Least squares" means that the overall solution minimizes the sum of the squares of the errors made in solving every...
of a model at the sample B. - Criterion of Unbiasdness - Sum of CR value and special CR for which A is B and B is A. Ratio of sample lengthes must be 1:1 i.e. size of A must be the same as size of B.
If a criterion does not define the number of observations for external dataset then the problem of data dividing ratio appears because the forecasting abilities of identified model are very dependent on the dividing ratio.
GMDH-type neural networks
There are many different ways to choose an order for partial models consideration. The very first consideration order used in GMDH and originally called multilayered inductive procedure is the most popular one. It is a sorting-out of gradually complicated models generated from Kolmogorov-Gabor polinomial. The best model is indicated by the minimum of the external criterion characteristic. Multilayered procedure is equivalent to the Artificial Neural NetworkArtificial neural networkAn artificial neural network , usually called neural network , is a mathematical model or computational model that is inspired by the structure and/or functional aspects of biological neural networks. A neural network consists of an interconnected group of artificial neurons, and it processes...
with polynomial activation function of neurons. Therefore the algorithm with such an approach usually referred as GMDH-type Neural Network or Polynomial Neural Network.
Combinatorial GMDH
Another important approach to partial models consideration that becomes more and more popular is a brute force combinatorial search that is either limited or full. This approach has some advantages against Polynomial Neural Networks but requires considerable computational power and thus is not effective for objects with more than 30 inputs in case of full search. An important achievement of Combinatorial GMDH is that it fully outperforms linear regression approach if noise level in the input data is greater than zero.
Basic combinatorial algorithm makes the following steps:
- Divides data sample onto parts A and B.
- Generates structures for partial models.
- Estimates coefficients of partial models using Least squaresLeast squaresThe method of least squares is a standard approach to the approximate solution of overdetermined systems, i.e., sets of equations in which there are more equations than unknowns. "Least squares" means that the overall solution minimizes the sum of the squares of the errors made in solving every...
method and sample A. - Calculates value of external criterion for partial models using sample B.
- Chooses the best model (set of models) indicated by minimal value of the criterion.
In contrast to GMDH-type neural networks Combinatorial algorithm can't be stopped at the certain level of complexity because a point of increase of criterion value can be simply a local minimum, see Fig.1.
Algorithms
- Combinatorial (COMBI)
- Multilayered Iterative (MIA)
- GN
- Objective System Analysis (OSA)
- Harmonical
- Two-level (ARIMAD)
- Multiplicative-Additive (MAA)
- Objective Computer Clusterization (OCC);
- Pointing Finger (PF) clusterization algorithm;
- Analogues Complexing (AC)
- Harmonical Rediscretization
- Algorithm on the base of Multilayered Theory of Statistical Decisions (MTSD)
- Group of Adaptive Models Evolution (GAME)
List of software
- KnowledgeMiner - Commercial product.
- PNN Discovery client - Commercial product.
- GMDH Shell - Commercial product with free version.
- FAKE GAME Project - Open source.
- Sciengy RPF! - Freeware, open source.
- GEvom http://research.guilan.ac.ir/gevom/ Free upon request for academic use
- wGMDH - Weka plugin, Open source.
External links
- www.gmdh.net — Articles, books and software.
- www.opengmdh.org — GMDH wiki and code development
- Criterion of Regularity (CR) - Least squares