page_title: Group method of data handling
section_title: Combinatorial GMDH
hierarchical_section_title: Group method of data handling / Combinatorial GMDH
context_page_description: Group method of data handling 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 external criterion.
  A GMDH model with multiple inputs and one output is a subset of components of the base function:
  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 algorithms consider various component subsets of the base function called partial models. Coefficients of these models are estimated by the least squares method. GMDH algorithms 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.
context_section_description: Another important approach to partial models consideration that becomes more and more popular is a 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 a large number of inputs. 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. It guarantees that the most optimal model will be founded during exhaustive sorting.
  Basic Combinatorial algorithm makes the following steps:
  Divides data sample at least into two samples A and B.
  Generates subsamples from A according to partial models with steadily increasing complexity.
  Estimates coefficients of partial models at each layer of models complexity.
  Calculates value of external criterion for models on sample B.
  Chooses the best model (set of models) indicated by minimal value of the criterion.
  For the selected model of optimal complexity recalculate coefficients on a whole data sample.
  In contrast to GMDH-type neural networks Combinatorial algorithm usually does not stop at the certain level of complexity because a point of increase of criterion value can be simply a local minimum, see Fig.1.
caption: Fig.1. A typical distribution of minimal values of criterion of regularity for Combinatorial GMDH models with different complexity.
exif: {}