Cluster-based Kriging Approximation Algorithms for Complexity Reduction
  Kriging or Gaussian Process Regression is applied in many fields as a
non-linear regression model as well as a surrogate model in the field of
evolutionary computation. However, the computational and space complexity of
Kriging, that is cubic and quadratic in the number of data points respectively,
becomes a major bottleneck with more and more data available nowadays. In this
paper, we propose a general methodology for the complexity reduction, called
cluster Kriging, where the whole data set is partitioned into smaller clusters
and multiple Kriging models are built on top of them. In addition, four Kriging
approximation algorithms are proposed as candidate algorithms within the new
framework. Each of these algorithms can be applied to much larger data sets
while maintaining the advantages and power of Kriging. The proposed algorithms
are explained in detail and compared empirically against a broad set of
existing state-of-the-art Kriging approximation methods on a well-defined
testing framework. According to the empirical study, the proposed algorithms
consistently outperform the existing algorithms. Moreover, some practical
suggestions are provided for using the proposed algorithms.
