Konstantinos K Delibasis
email: kdelibasis@gmail.com

A New Topology-Preserving Distance Metric with Applications to Multi-dimensional Data Clustering

Keywords: distance metric, data manifolds, clustering

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Clustering high-dimensional data is an area that has attracted considerable research interest over the past two decades [START_REF] Agrawal | Automatic subspace clustering of high dimensional data[END_REF][START_REF] Kriegel | Clustering high-dimensional data: A survey on subspace clustering, pattern-based clustering, and correlation clustering[END_REF][START_REF] Tasoulis | Enhancing principal direction divisive clustering[END_REF]. The existence of irrelevant features and correlations between subsets of features, which are commonly encountered in such datasets, renders the task of identifying clusters much harder as distances between observations become less informative about the cluster structure. Dimensionality reduction and Feature Embedding is widely used to improve clustering performance and to enable the visualization of the resulting cluster structure in such data. Although well-established methods like Principal Component Analysis (PCA) and metric Multi-Dimensional Scaling (MDS) [START_REF] Cox | Multidimensional scaling[END_REF] have been successfully applied on a plethora of highdimensional applications, there is no guarantee that the cluster structure in the highdimensional space will be preserved in the low-dimensional subspace since in many cases clusters could be defined by highly non-linear structure. For this purpose nonlinear dimensionality reduction techniques have been explicitly designed to identify a lower dimensional manifold along which the data lie, and are therefore appropriate to distinguish nonlinearly separable clusters.

Kernel-based clustering is amongst the most popular methods for nonlinear clustering, based on the projection of the input data points into a high dimensional kernel space in order to make nonlinear clusters linearly separable [START_REF] Schoelkopf | Nonlinear component analysis as a kernel eigenvalue problem[END_REF]. In particular, kernel kmeans combines the k-means method with the kernel trick in an attempt to deal with nonlinearly separable data, however specifying a suitable kernel function and appropriate parameters most of the times is a hard task. Another widely used manifold learning method is isometric mapping (ISOMAP). Instead of using the Euclidean distance, Isomap is based on approximating geodesic distance along the manifold [START_REF] Tenenbaum | A global geometric framework for nonlinear dimensionality reduction[END_REF]. However, isomap operates on neighboring data-points defined by Euclidean threshold distance, which accelerates the algorithm but presents problems in case of outlier points. In [START_REF] Yu | An extended isomap by enhancing similarity for clustering[END_REF] the authors applied the k-means clustering algorithm after Isomap and proposed a modified definition of the geodesic distances but concluded that even their modified method was unsatisfactory in real-data cases where the data is noisy or the clusters are highly nonlinear.

In this work we propose a new topology preserving distance that follows the geodetic of the underlying manifold. Instead of imposing a threshold on distance between points, we construct a graph with all available points and impose a penalty function that penalizes distant points. The definition of distant points uses a characteristic distance parameter whose value is automatically estimated from the available dataset. Furthermore, we propose a modification of the k-means algorithm incorporating benefits of a newly introduced distance metric that preserves the topology of the data point manifold. A critical advantage of the proposed approach is the feasible robust parameterization of the algorithm. Extensive experiments on both simulated and real data sets employing the Purity and V-measure metrics for comparison, as described in [START_REF] Pavlidis | Minimum density hyperplanes[END_REF] provide further evidence on the wide applicability of the proposed method.

Methodology

The proposed topology-preserving distance metric

Let P be a data matrix of dimensions N×K, each row of which is a feature vector (equivalently a data point)

  K x x x ,..., , 2 1 
p of dimensionality K. Any given set of such points may be arranged on an unknown manifold in the K  space. Thus, the Euclidean distance metric between any two points may not represent their actual distance.

Let us define an auxiliary distance metric between any pair of data points as:

      0 0 , , d d d d d d D ij ij ij ij ij  (1)
where

j i p p   ij d
is the Euclidean distance between the two points, λ is a sufficiently big value and d 0 is a characteristic distance, whose value is estimated for the current dataset, as it will be described later. Let us stretch that D ij is not the distance metric proposed in this work, rather an auxiliary definition.

For a given set of data points

  N i P ,..., 2 , 1 ,   i p in K  , a fully connected graph   E P G , 
is defined with vertices P as the set of all data points and edges E as the set of all possible connections between vertices,

    N j i j i E ,..., 2 , 1 , , ,  
. Thus, each point is connected to all other points in the data set. The cost of the connection (edge) between any pair of points j i p p , is set equal to their auxiliary distance D ij , as defined in Eq.( 1). The proposed topology preserving distance between j i p p , is defined as the cost of the minimum-cost path ij  according to the well-known Dijk- tra's algorithm, between the two points.

    N j i A A ij ,..., 2 , 1 , , cost , ij     j i p p (2)
Since any generated path

M i i i ,..., , 2 1
, where

j i i i M   , 1
the proposed topology preserving distance between j i p p , is calculated as

(3)
The parameter d 0 is a characteristic length in K  that defines the scale of local linearity in a given set of data points. It is self-evident that any two points with Euclidean distance less than or equal to d 0 will be connected without any intermediate points. On the other hand, for any two points with Euclidean distance greater than d 0 , the proposed algorithm will generate a connecting path with intermediate points, if sufficient pairs of these points have Euclidean distance not greater than d 0 . Fig. 1 shows the paths generated by the Dijkstra's algorithm using the auxiliary distance D ij , in the case of data points generated using the Swiss roll data set [11], for λ=10 8 , d 0 =2, using one randomly selected point i 0 as the source for Dijkstra's algorithm (the point from which all other distances are calculated). The dataset is constructed to contain 2 classes (N c =2), 400 points each, denoted by different color. The points lie on a manifold that is defined by a parametric equation. The paths j , i 0  are also plotted as blue lines for all points j=1,2,…, 800, j≠ i 0 . As it can be observed, the selected value of d 0 generates shortest paths that lie on the manifold, rather than crossing the gap as it would be dictated by the Euclidean distance. The use of this propose distance metric in any clustering or classification process on this dataset is expected to significantly increase the achieved accuracy. for almost all pairs of points j i p p , , also resulting in a single-edge path, just as described previously.

 

M M m m m j i i j i i D A         , , cost 1 1 1 1 , j i,
Let i 0 be the index of a randomly selected point. The proposed algorithm is executed N-1 times connecting i 0 with all the rest N-1 points j p , calculating distance j i A 0 and generating the corresponding paths j i 0  . Let us denote the sequence of points that constitute the path from i 0 to j as  

M i i i ,..., , 2 1 with
M i j i i   , 1 0
and the series of

Euclidean distances   M m d m m i i ,..., 2 , 1 , 1 ,   . To simplify notation, let us use 1 , , 1    m m i i d d m m . Let   M m d d m m j i ,..., 2 , 1 , max 1 , max 0   
be the maximum Euclidean length of the steps in the path from i 0 to j. Then the average max 0 j i d can be calculated for the selected point i 0 over all other points j in the data set:

     N i j j j i i d N d , 1 max , 1 1 (4)
By its definition, i d is calculated for a selected point i 0 and it is a function of d 0 .

It is easily proven that when d 0 has very low values, below the minimum Euclidean distance d min in the dataset, i d is equal to the mean Euclidean distance between i 0 and all data points. In the case of data points being equally distributed (eg. on a regular grid), the quantity i d is expected to be monotonically increasing when d 0 in [d min , d max ]. When d 0 approaches values equal to d max , the i d becomes equal to the mean Euclidean distance between i 0 and all data points and remains constant for larger values of d 0 . In the case however of anisotropic data point distribution, i d drops sharply when d 0 has an appropriate intermediate value, since the proposed algorithm generates connecting paths between data points that consist of steps with smaller distances. Finally, when d 0 approaches values equal to the maximum Euclidean distance in the dataset d max , the i d becomes equal to the mean Euclidean distance between i 0 and all data points. Thus, for any point in the dataset i, the quantity is calculated for different values of 0 d and the value of

In the special case of data points lying on a manifold with shape of large scale concavities, then i d min has a value that indicates the characteristic length of the concavities. Thus, setting d 0 to a value less than i d min will cause the proposed algorithm to produce connecting paths between data points that do not cross the concavities, but lie on the manifold, thus behaving like geodetic curves. In order to obtain a good estimation of i d min , the calculation is repeated for many randomly selected points in the dataset and the average i d min is obtained. Figure 2 shows the The effect of d 0 is demonstrated in Fig. 4. One point is randomly selected from the dataset and the minimum cost connections with all other points are shown. The cost of the connecting path is calculated according to Eq. ( 3), as a function of d 0 . It can be observed that for very low or very high values of d 0 , the connecting paths cross the topological gap between points, whereas for intermediate values, the paths follow the manifold, as geodesic curves.

d 0 =0.5 d 0 =1 d 0 =2 d 0 =4 d 0 =8
Fig. 4. The minimum cost paths generated by the proposed algorithm applied on the Swiss roll dataset, for different values of d 0 . Intermediate values of d 0 , as suggested by the estimation of the average i d min , produce paths that follow the underlying manifold.

A k-means variant for the proposed topology-preserving distance metric

In this subsection a variant of the k-means clustering algorithm is proposed, that utilizes the proposed topology preserving distance metric. The main differences from the classic k-means algorithm can be summarized as following:

The N×N distance matrix is calculated using the proposed distance metric in Eq.(2) (it requires the characteristic length d 0 ):

      N j i A A ij ,..., 2 , 1 , , ,    j i p p A .
The class centers in each iteration are selected from the data points, so that they minimize the average (proposed metric) distance from the members of the specific class. The algorithm is terminated when all class centers remain unchanged in two consecutive iterations. The details of the proposed algorithm are given below.

Input: the data matrix P , the number of classes

Results

The proposed k-means variant that uses the proposed distance metric is evaluated against the classic k-means, the kernel k-means (implemented as in [START_REF] Gonen | Localized Data Fusion for Kernel k-Means Clustering with Application to Cancer Biology[END_REF]) and the spectral clustering (implemented in [10] and [START_REF] Von | A Tutorial on Spectral Clustering[END_REF]) in terms of purity of clustering, as well as V-measure. The proposed method has been executed for 20 times with random initialization and the resulting average purity, as well as the standard deviation are plotted for different values of d 0 in Fig. , the proposed algorithm behaves very similarly to the classic k-means. This is expected, since as described above the proposed distance definition becomes similar to the Euclidean one.

Fig. 6. The achieved purity and V-measure using the proposed method applied to the COIL dataset, for different values of d 0 , against the classic k-means, the kernel k-means [START_REF] Gonen | Localized Data Fusion for Kernel k-Means Clustering with Application to Cancer Biology[END_REF]. The spectral clustering [START_REF] Gonen | Localized Data Fusion for Kernel k-Means Clustering with Application to Cancer Biology[END_REF] produced worse results and it was therefore not included in the graph.

Table 1 shows the clustering purity and V-measure achieved by the proposed method, k-means, kernel k-means and spectral clustering. The values for the proposed method were calculated by using the corresponding value for d 0 slightly less than the estimated i d min . The standard Matlab implementation was used for the k-means method. Ker- nel k-means was used as provided in [START_REF] Gonen | Localized Data Fusion for Kernel k-Means Clustering with Application to Cancer Biology[END_REF]. Spectral clustering was used as provided in [10] and/or in [START_REF] Von | A Tutorial on Spectral Clustering[END_REF] that implements the algorithm described in [13].

Conclusions

A new distance metric for high-dimensional data has been presented that preserves the topology of the underlying manifold. A variant of the k-means clustering algorithm has been suggested that utilizes this metric. The value of the main parameter of the proposed distance metric can be obtained with a standard and efficient process.

The performance of the proposed method has been analyzed theoretically and validated experimentally, on a number of benchmark datasets. Comparative results with well-established clustering algorithms show that the proposed method is a competent alternative with consistent behavior that systematically performs equally well or better than the other techniques under comparison. Future work includes the algorithmic fine tuning of the proposed k-means variant and the extension of the application of the distance metric to visualization and dimensionality reduction techniques. Comparative results will also be expanded to include more optimized implementations of other state of the art methods.

  of an ordered series of data points with indices  

,Fig. 1 .

 1 Fig. 1. The paths generated by the proposed distance definition in the case of the Swiss Roll dataset, for d 0 =2. The points lie on a manifold and consist of two classes shown in green and red color

idFig. 2 .

 2 Fig. 2. The i d as a function of d 0 , for a number of data points and the determined i d min plot- ted as a green circle, for data points a) on a 2D regular grid and (b) randomly distributed.

Fig. 3 .

 3 Fig. 3. The shape of

cN

  , the N×N distance matrix A using the proposed metric.Experimentation shows (see Results section) that the proposed variant of the k-means method produces consistently optimal results for values of d 0 slightly smaller than the estimated i d min .

5 .

 5 The same quantities achieved by the classic k-means clustering, the kernel k-means and the spectral clustering are also shown. It can be observed that the proposed algorithm clearly outperforms the classic and the kernel k-means. The behavior of the proposed algorithm with respect to parameter d 0 is consistent with the estimated value of i d min : for values of less than the achieved clustering is consistently high. For values of

Fig. 5 .

 5 Fig. 5. The achieved purity and V-measure using the proposed method, applied to the Swiss roll dataset, for different values of d 0 , against the classic k-means, the kernel k-means [9] and the spectral clustering [10].

Fig. 6

 6 Fig.6shows the same results for the COIL dataset. The determination of i d min as shown in Fig.6(a) is unambiguous. The behavior of the proposed k-means variant with respect to d 0 , is also very consistent, with best performance occurring at values of d 0 slightly smaller than the estimated i d min . The proposed k-means variant with the suggested distance metric outperforms the other methods in comparison.

Table 1 .

 1 Dataset description, with the achieved clustering purity and V-measure by the proposed method, classic and kernel k-means and spectral clustering.

	Dataset Classes, Dim,	d	i	Proposed	K-means	Kernel K-m	Spectral Cl.
				min
		Num.			Pur. V-m Purity V-m.	Purity	V-m	Purity V-m
	Swiss Roll	4 3 1600	3.64 0.75 0.83 0.505 0.67	0.59	0.47	0.775 0.85
	Olivetti 10 4096 400	2057 0.57 0.75 0.47	0.68	0.25	0.43	0.30	0.551
	Umist 20,1030 4414	3808 0.7	0.84 0.58	0.66	0.23	0.251	0.19	0.22
	Isolet 26 617 1567	9.38 0.48 0.67 0.425 0.59	0.269	0.402	0.155 0.258
	Coil 20 2 16 1440	6950 0.64 0.81 0.407 0.595	0.44	0.565	0.285 0.480
	Phoneme 4 256 4509	40.27 0.65 0,61 0.565 0.395	0.779	0.691	0.302 0.104

Acknowledgement

The author wishes to acknowledge the partial support by the Interdepartmental Postgraduate Program "Computer Science and Computational Biomedicine" of the School of Science of the University of Thessaly


Stamatios-Aggelos N Alexandropoulos

Christos K Aridas

Sotiris B Kotsiantis

Michael N Vrahatis
email: vrahatis@math.upatras.gr

Stacking strong ensembles of classiers

Keywords: Decision support systems, Supervised machine learning, Ensembles of classiers

A variety of methods have been developed in order to tackle a classication problem in the eld of decision support systems. A hybrid prediction scheme which combines several classiers, rather than selecting a single robust method, is a good alternative solution. In order to address this issue, we have provided an ensemble of classiers to create a hybrid decision support system. This method based on stacking variant methodology that combines strong ensembles to make predictions.

The presented hybrid method has been compared with other knownensembles. The experiments conducted on several standard benchmark datasets showed that the proposed scheme gives promising results in terms of accuracy in most of the cases.

Introduction

An ensemble of classiers [START_REF] Murty | Combination of classiers[END_REF] combines the decision of individual classiers in some way in order to classify new instances. A various number of methods have been presented for the creation of such a set of classiers [START_REF] Dietterich | Ensemble methods in machine learning[END_REF]. The most common and widely used ways to create such a combination of classiers are the following three: (c) Using dierent learning methods.

One can reasonably be asked why an ensemble of classiers may provide better results than a single classier. The reasons are both representational, statistical and computational and are presented in [START_REF] Dietterich | Ensemble methods in machine learning[END_REF]. The training data cannot produce informative knowledge in some of the cases in order to select a single Supported by Hellenic State Scholarships Foundation (IKY).

classier. This may be a possible cause of the aforementioned issue since the training data is too small concerning the amount of the hypothesis space.

Despite the fact that the interest gathered about methods of ensembles in recent years is so big, further study is required since it is not clear which method is the best. In the present work, we have performed a hybrid scheme that combines the following ensemble methods: Random Forest [START_REF] Breiman | Random forests[END_REF], ExtraTrees [START_REF] Geurts | Extremely randomized trees[END_REF] and Gradient Boosting [START_REF] Friedman | Greedy function approximation: a gradient boosting machine[END_REF] algorithm using a stacking variant methodology. The proposed hybrid decision support system is compared with several ensembles methods on a variety of benchmark datasets. The results obtained showed that the provided method has better accuracy in most of the problems.

The rest of the paper is organized as follows. In the next section, we present well-known methods for creating ensembles of classiers, while in Section 3 we consider the proposed ensemble method. The conducted experiments and the comparisons with other ensemble methods are presented in Section 4. Finally, we conclude in Section 5 with a summary and further research remarks.

Well-known methods for creating ensembles

There are a plethora of methods using a single classier in order to solve a prediction problem. However, the need for models that will make a more accurate prediction is intense. This purpose, as mentioned in the introduction of our work, is served by a combination of classiers. In order to create a good ensemble of classiers, there are dierent methodologies. Each of these can provide a varied rate of correctly classied instances. Thus, the overall goal of the methods belonging in decision support systems is to achieve reliable and very accurate prediction results. This section presents widely used methods for building ensembles.

Bagging technique or Bootstrap aggregating [START_REF] Breiman | Bagging predictors[END_REF] A well-known meta-algorithm is also the Boosting approach [START_REF] Freund | Experiments with a new boosting algorithm[END_REF]. One could say that this method resembles with the bagging approach since several sub-samples are used for training a single learner. Moreover, this algorithm was based on the question Can a set of weak learners create a single strong learner? [START_REF] Kearns | Cryptographic limitations on learning boolean formulae and nite automata[END_REF]. Boosting method is directly related to this question as it focuses on the performance of a weak classier in order to enhance it, especially in cases where instances are not eectively been learned. Thus, rather than selecting the instances in a random way based on a distribution, the algorithm focuses on the training instances that have not been learned correctly. In order to create a strong classier, after several steps, the prediction is done through a weighted voting procedure. In detail, each classier prediction takes a weight according to the classication accuracy that it achieved.

Besides the aforementioned techniques that mostly train classiers in a subset of training data, there are methods that create a model using a set of learning algorithms on the entire training dataset. Then, by choosing an appropriate voting pattern, they combine the responses in order to obtain the nal prediction.

Through this process, dierent learning algorithms are used to increase the diversity of prediction errors of the models. This is because they dier in both the search process and the representation. In conclusion, the models that created are more likely to make mistakes at dierent points, as dierent learning biases are used. Finally, utilizing the majority of forecasts we easily end up in the nal decision, as no prior training is required.

A well-known method that uses the above-mentioned procedure is stacked generalization approach or Stacking [START_REF] Wolpert | Stacked generalization[END_REF]. In this method, the production of a strong, high-level learner with high generalized performance is the main goal. To obtain this, a set of dierent classiers are combined. To achieve an appropriate combination of the base predictions, a learning algorithm is used. In order to perform the nal forecast, the model is utilizing the following steps: (a) Level zero data. All the base learners run on the original dataset, (b) Level one data.

After the zero level, the predictions made by the classiers are considered as new data and (c) Final prediction. Another learning process takes place using the level one data as new inputs and as output, the nal prediction is gained.

An alternative idea was used by [START_REF] Ting | Issues in stacked generalization[END_REF]. The proposed method is an extension of the well-known stacking [START_REF] Wolpert | Stacked generalization[END_REF] and is based on class probability distributions rather than the predictions. Thus, each learner does not present a nal prediction for the class to which an example belongs. As a result, it gives an estimated probability for all classes. The authors, in order to achieve meta-level learning, used the Multi-response Linear Regression (MLR).

Several approaches have been provided in order to improve the performance of [START_REF] Ting | Issues in stacked generalization[END_REF]. In particular, in [START_REF] Dºeroski | Is combining classiers with stacking better than selecting the best one?[END_REF] adopted the same strategy except for the metalearning procedure. The authors, used model tree induction instead of MLR and the obtained results showed that better performance is achieved. Furthermore, another modication is proposed by [START_REF] Seewald | How to make stacking better and faster while also taking care of an unknown weakness[END_REF]. In this method, instead of the overall class probability distributions, only class probabilities concerning the true class are taking into account. The experimental results showed that by this variation the accuracy of this method seems to be improved.

In [START_REF] Menahem | Troikaan improved stacking schema for classication tasks[END_REF] another stacking algorithm, called Troika, is presented in order to tackle multi-class classication tasks. Specically, the proposed method instead of one meta-learner uses three layers of combining classiers: (a) The zero layer consists of base learners, (b) The rst one contains specialist classiers, (c) The second layer is composed by meta-learners and (d) In the last layer is met the super-classier which take the predictions of the previous layer in order to make the nal prediction of the model. The main comparison included the Troika method, the basic stacking scheme and an improvement of standard Stacking, the StackingC method. The experiments conducted showed that the presented method outperforms the other two methods in terms of accuracy irrespective of the base-classier binarization method that was selected.

Stacking ensemble methodology can be seen as a combinatorial optimization problem. This is because both base classiers and meta-classier have to be determined in an optimal way. In [START_REF] Chen | An ant colony optimization approach for stacking ensemble[END_REF] an adaptive metaheuristic search method was adopted in order to create a new stacking approach, called Ant Colony Optimization (ACO) Stacking algorithm. Thus, given a set of base learners, let B, which consists of n classiers, ACO algorithm [START_REF] Dorigo | Ant colony optimization: a new meta-heuristic[END_REF] determines a subset of B consisting of a smaller amount of learners. This set of classiers is expected to has better classication accuracy than the original. The authors compared ACO-Stacking approach with well-known ensembles such as Bagging, AdaBoost, StackingC and Random Forest. The experimental results showed that the performance of ACO-Stacking algorithm is promising.

A similar approach in which the problem of selecting the appropriate conguration of base learners and the meta-classier is proposed in [START_REF] Shunmugapriya | Optimization of stacking ensemble congurations through articial bee colony algorithm[END_REF]. The main dierence relating to [START_REF] Chen | An ant colony optimization approach for stacking ensemble[END_REF] concerns the swarm intelligent search algorithm that used for the optimization task. Particularly, the authors used the well-known Articial Bee Colony (ABC) algorithm [START_REF] Karaboga | An idea based on honey bee swarm for numerical optimization[END_REF] in order to build two dierent types of stacking. Thus, the optimal conguration of base learners is taking place in the beginning. In that phase, the meta-learner that considered is a xed learning algorithm. During the meta-phase, the ABC algorithm optimize at the same time the base learners and the meta-learner too. The ABC-Stacking approach was tested in several well-known benchmark datasets and compared with dierent predictive learners, basic ensemble techniques, such as GA-Stacking [START_REF] Ordóñez | Genetic approach for optimizing ensembles of classiers[END_REF] and ACO-Stacking. The experiments conducted by the authors showed that the provided approach has addressed eectively the conguration of base-classiers and the selection of meta-learner too. Moreover, the performance of ABC-Stacking is comparable to the best results cited so far.

In [START_REF] Puertas | Generalized multi-scale stacked sequential learning for multi-class classication[END_REF] a strategy which is similar to the Stacking methodology is adopted in order to apply a sequential learning algorithm in multi-class problems. For a more extensive study of Stacking methodology, Stacking methods and related with Stacking approaches that have been developed over the last 20 years the reader is referred to [START_REF] Sesmero | Generating ensembles of heterogeneous classiers using stacked generalization[END_REF]. [START_REF] Chen | An ant colony optimization approach for stacking ensemble[END_REF] Proposed hybrid scheme

As with any classier, adding new input features can improve classication accuracy when the new features contain new information about the class. This performance improvement isn't guaranteed because classiers are imperfect and may not be able to exploit the information. If the new features share information with existing features, the new features may or may not help. In all cases, the curse of dimensionality must be considered. The presence of more features can hurt many classiers and can increase opportunities for overtting. The situation is similar when adding new base classiers to a stacking setup, because the base classiers' outputs are features for the nal classier. All the same arguments from above hold here. In this case, these 'second level' features are likely correlated because all base classiers are all trying to predict the same case. However, they do it suboptimally. The hope is that they behave in dierent ways, so that the nal classier can combine the noisy predictions into a better nal prediction. Loosely, then, adding new base classiers has the best chance of helping when they do a good job and behave dierently than existing base classiers, but this isn't guaranteed. In all cases, the time of training must be considered.

In our case, we select to use three strong ensemble methods as base learners:

Random Forest, ExtraTrees and Gradient Boosting.

According to Brieman's denition in [START_REF] Breiman | Random forests[END_REF], a Random Forest is a classier that consists of a set of tree-structured classiers. A worth point is that in each tree the decisions are made by a random way when splitting a node, without taking all the features into account. In this process, each tree is trained in a sub-sample in a similar way with bagging and votes for the most popular class concerning a given input. This kind of decision trees using averaging can improve the prediction accuracy. In addition, can achieve the control of the overtting.

As in the Bootstrap aggregating the creation of the sub-samples is done with replacement and the size of each sub-sample is equal to the beginning sample.

A similar method to the Random Forests is the Extremely randomized Trees or ExtraTrees [START_REF] Geurts | Extremely randomized trees[END_REF]. This method is successfully applied and produces good results in terms of accuracy while eectively controls the overtting issue. The dierence with the Random Forests can be found in two points: (a) The training of each tree is made without using a bootstrap sample but a whole training set and (b)

The cut-point for splitting a node is selected by a fully random way.

Gradient Boosting [START_REF] Friedman | Greedy function approximation: a gradient boosting machine[END_REF] is a widely used approach for handling regression and classication tasks, which is mainly based on decision trees classiers. The main strategy of this method is similar to other boosting methods (such as AdaBoost or LogitBoost). In a rst phase build a set of weak learners in order to make an initiate prediction. In a second phase optimize the prediction accuracy of the model based on the minimization of a cost function. Specically, gradient boosting iteratively determining a function that points in the negative gradient direction.

In our stacking algorithm, the set of meta-data will consist of the predictions given by the base ensembles and the true class for each training case. Thus, the classier trained on this dataset is the so-called meta-learner. Our approach uses the class probabilities correlated with the true class rather than all class probabilities as in the standard Stacking.

Another point that is worth mention is the learning process. The goal is to build a fast learning procedure. This is achieved by reducing the dimensionality of meta-data set by a factor associated with the number of classes. Despite this reduction, the accuracy for the two-class problems remains unaected. More-over, the learning algorithm that we use at the meta-level is the well-known Logistic Model Tree classier [START_REF] Sumner | Speeding up logistic model tree induction[END_REF]. This is because piecewise linear approximations are gained through these models. The gure 1 illustrates the process that was adopted in order to create a strong classier, while the proposed method is illustrated in the Algorithm 1.

All level-1 predictions

Training folds

Validation fold Step 2 Learn a second-level classier

Learn a new classier p from the collection of {x i , yi}

Step 3 Re-learn rst-level learners for t ← 1 to 3 do Learn a classier pt based on S end for Return P f (x)

Comparisons and Experimental results

For our experiments, well-known datasets from UCI Machine Learning repository [START_REF] Dua | school of information and computer science[END_REF] were used. Specically, 38 problems from dierent elds were selected, which dier in both the number of their attributes and their classes. In Table 1, there is a brief description of these datasets such as the number of features, the number of instances and the number of output classes.

The accuracy of the classiers was evaluated according to the following procedure: The training dataset was divided into ten equally-sized subsets, and for each of them, the classier was trained in the remainder subsets. Then, for each method, we run the ve fold cross-validation procedure and the average value of ve fold cross validations was measured. The experiments have been conducted

with Python using the available implementations from the scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine learning in python[END_REF] and MLxtend library [START_REF] Raschka | Mlxtend: Providing machine learning and data science utilities and extensions to pythonâs scientic computing stack[END_REF]. In Table 2 the obtained results for our hybrid scheme and for methods which participate in the comparison are exhibited. The best performing scheme for each dataset is described using boldface writing. It can be easily seen that the proposed stacking ensemble method outperforms the other three well-known ensembles in most of the cases and thus we can say that the proposed method is more robust.

Furthermore, statistical tests have been performed in order to check the signicance of the results. In particular, due to the small number of comparison there are methods whose performance dierence was statistically signicant to the others. In Table 4, the obtained results of the post-hoc Holm test [START_REF] Holm | A simple sequentially rejective multiple test procedure[END_REF] are exhibited. Hybrid decision schemes seem to be a reliable and eective option in order to tackle decision-making tasks in several scientic elds. Compared to the accuracy that a single classier can achieve, an ensemble method seems to be able to reach better classication results. However, designing such a method is a dicult problem, as we have a plethora of basic classiers for use. Stacking methodology is an appropriate and accurate procedure in order to create a strong combination using the best over-all stacked classier. Despite the fact that a variety of ensemble methods have been designed, creating the best combination for solving specic classication problems remains a hot and ongoing project. In this paper, proposed a Stacking strong ensemble methodology using Logistic Model Trees and three well-known ensembles. The experimental results conducted over well-known datasets showed that the provided scheme gives promising results in most of the benchmark problems. Nevertheless, there are several issues that need further study, such as the rules that build a suitable set of classiers with the highest possible accuracy. Moreover, further comparisons of our method with well-known variations of Stacking such as [START_REF] Chen | An ant colony optimization approach for stacking ensemble[END_REF][START_REF] Ordóñez | Genetic approach for optimizing ensembles of classiers[END_REF] and implementation in regression problems could be an interesting task for future research.

( a )

 a Using an individual learning method and dierent subsets of training data. (b) Using an individual training algorithm and various training parameters.

  is one of the most known and widely used technique for creating ensembles of classiers. A key feature of this method is the training of each learner using dierent training sets. Specically, let N be a set of training data of size n. Bagging method selects from this set n random examples, creating a set of training subsets, let N i . The selection of instances is done using a distribution, for example the uniform distribution, while the examples are drawn with replacement. Since the building of the subsets is done in that way, it is possible some of the examples to be repeated in N i and some duplicates and omissions to contained in regard to the starting training set N . This execution produces a set of classiers. Then, a voting process is taking place in relation to the predictions of each classier. The result of the vote gives the nal decision.

Fig. 1 .

 1 Fig. 1. Stacking strong ensembles process

Table 1 .

 1 Collection of 38 multi-class datasets from the UCI Machine Learning Repository. The number of instances, the number of features as well as the number of classes,

	are exhibited.
	Dataset	#Instances	#Features	#Classes
	audiology	226	69	24
	autos	205	25	7
	badges	294	11	2
	balance-scale	625	4	3
	breast-cancer	286	9	2
	wisconsin-breast-cancer	699	9	2
	horse-colic	368	28	2
	credit-rating	690	15	2
	german-credit	1000	20	2
	pima-diabetes	768	8	2
	glass	214	9	6
	grub-damage	100	11	2
	haberman	306	3	2
	hear-cleveland	303	13	5
	heart-hungarian	294	12	2
	heart-statlog	270	13	2
	hepatitis	155	19	2
	hypothyroid	3772	30	2
	ionosphere	351	34	2
	iris	150	4	3
	labor	57	16	2
	lymphography	148	18	4
	monk1	556	7	2
	monk2	601	7	2
	monk3	554	7	2
	mushroom	8124	22	2
	primary-tumor	339	17	21
	students	344	11	2
	sick	3772	29	2
	sonar	208	60	2
	soybean	683	35	19
	relation	2201	3	2
	vehicle	846	18	4
	vote	435	16	2
	vowel	990	13	11
	waveform	5000	40	3
	wine	179	13	3
	zoo	101	17	7
	methods, the non-parametric Friedman test [11] has been conducted. There-
	fore, in Table 3 the Friedman test ranking is presented. Moreover, p-value in
	all the comparisons indicates that the null hypotheses should be rejected. Thus,

Table 2 .

 2 Classication accuracy and standard deviation of the compared methods,

	where ET denotes ExtraTrees, GB represents Gradient Boosting, while RF de-
	notes Random Forest.
	Dataset	Stacking	ET	GB	RF
	audiology	79.13±5.01	66.13±7.28	82.66±5.28	76.99±5.79
	autos	82.15±6.78	68.49±6.22	82.54±5.30	79.12±4.17
	badges	98.98±3.28	96.86±4.30	100.00±0.00	99.11±1.92
	balance-scale	89.38±1.30	78.78±2.93	87.33±2.01	81.66±2.41
	breast-cancer	70.55±4.20	64.07±6.71	69.58±5.87	71.82±3.81
	wisconsin-breast-cancer	96.42±1.71	94.56±2.00	96.17±1.74	95.91±1.83
	horse-colic	83.64±3.51	73.97±5.20	83.80±2.99	83.32±3.53
	credit-rating	86.70±1.97	79.19±4.01	86.14±1.95	86.09±2.13
	german-credit	75.92±2.53	66.70±2.79	75.52±2.40	74.10±2.70
	pima-diabetes	75.89±3.52	67.89±2.79	75.73±3.63	74.04±2.95
	glass	76.27±5.63	63.65±8.37	75.34±4.85	73.10±5.53
	grub-damage	41.81±6.68	40.13±6.39	38.97±7.73	41.29±7.90
	haberman	72.29±2.53	65.17±4.87	69.60±3.84	70.52±3.16
	hear-cleveland	80.34±5.07	76.38±4.63	80.80±4.66	79.81±5.60
	heart-hungarian	81.64±4.49	75.92±4.83	82.25±5.04	80.68±5.73
	heart-statlog	80.96±4.43	74.22±5.37	78.89±4.66	79.70±4.19
	hepatitis	83.10±5.98	78.19±7.41	81.94±5.59	81.94±6.45
	hypothyroid	99.49±0.29	94.18±1.02	99.46±0.31	99.14±0.32
	ionosphere	93.28±3.13	87.12±4.03	92.88±2.81	92.31±2.64
	iris	94.27±3.79	91.73±5.54	95.33±3.43	95.33±3.47
	labor	90.58±9.97	85.48±12.86	85.73±10.66	90.91±9.62
	lymphography	83.79±7.67	77.31±9.13	85.15±7.13	82.42±7.07
	monk1	98.71±3.03	74.69±12.95	98.87±2.75	86.15±6.52
	monk2	63.46±6.91	54.80±7.42	64.74±8.42	57.50±6.43
	monk3	91.65±4.01	82.69±7.32	91.17±4.20	90.66±5.19
	mushroom	100.00±0.00	99.99±0.02	99.99±0.05	100.00±0.00
	primary-tumor	42.48±3.29	34.28±4.69	39.82±4.68	40.81±4.22
	students	83.96±3.75	80.46±3.37	84.19±3.73	82.62±3.30
	sick	98.65±0.34	94.59±1.05	98.68±0.31	98.26±0.42
	sonar	83.38±6.26	69.80±5.79	82.51±6.14	79.46±7.22
	soybean	93.00±2.04	88.20±3.13	93.06±1.99	92.94±1.79
	relation	79.02±0.94	78.94±1.02	78.94±1.02	78.95±1.05
	vehicle	75.44±2.41	65.91±2.92	75.42±2.29	74.02±2.64
	vote	96.00±2.13	92.92±2.96	95.31±2.32	95.49±2.87
	vowel	92.93±1.93	75.82±3.31	89.78±2.09	91.37±2.03
	waveform	85.61±1.21	68.37±1.52	85.52±1.20	81.36±1.22
	wine	96.73±2.77	87.97±6.14	95.05±4.58	96.18±3.61
	zoo	93.65±4.70	88.70±7.69	89.30±4.46	94.89±4.09

Table 3 .

 3 Rankings of the algorithms using the Friedman test

	Stacking	1.48684
	Gradient Boosting	2.05263
	Random Forest	2.51316
	ExtraTree	3.94737

Table 4 .

 4 Post-hoc Holm test using Stacking as control method

		Comparison	Statistic	Adjusted p-value Result
		Stacking vs ExtraTree	8.30769	0.00000	H0 is rejected
		Stacking vs Random Forest	3.46524	0.00106	H0 is rejected
		Stacking vs Gradient Boosting	1.91033	0.04609	H0 is rejected
	5	Conclusions

Acknowledgements This research is co-nanced by Greece and the European Union (European Social Fund-ESF) through the Operational Programme Human Resources Development, Education and Lifelong Learningin the context of the project Strengthening Human Resources Research Potential via Doctorate Research (MIS-5000432), implemented by the State Scholarships Foundation (IKY).


Spyridon Blatsios

Ioannis Refanidis

Towards an Adaption and Personalisation Solution based on Multi Agent System Applied on Serious Games

Keywords: Adaption, Personalization, Game-based learning, Game Design

Serious games (SG) have the potential to become one of the most important future e-learning tools. The use of SG in education is a large deviation from the common education standards, which usually are based on mass systems of instruction, assessment, grading and reporting students' knowledge and skills. SG encourage self-directness and independency of student, thus providing a framework for self-learning activities. However, the benefits of using SG as a learning tool are maximized in a personalised and adaptive environment. Although it has been suggested in the past that SG can take advantage of Artificial Intelligence (AI) methods for automated adaptation to the learner, there is not so much research in the field.

Taking the above into consideration, this paper aims to provide a framework on adaptive and personalised SG using AI methods. The advances in technology have made it possible to trace and collect user generated data that we can use to capture essentially players' in-game behaviours and trace knowledge or skills acquired from the player during playing. This will actually be a two-step process, "User Identification" and "Content Adaptation" to learners' needs. In the proposed methodology "User Identification" will be implemented from data derived from "User Behaviour" and "System Feedback". That data will feed a Learner Agent supported by an Adaption and Personalisation engine, which will interact with both the "Instructional Content" and "Game Characteristics" in order to achieve the desired adaption. This paper will be used as a basis for further development of an adaptive and personalised SG.

Introduction

Game industry is one of the largest sections on entertainment industry. At 2018 was estimated that global games market reached $134.9 billion growing at a healthy pace of +10.9% from 2017, while 64% of households own a device that is used to play video games [START_REF] Paiva | TAGUS -A Learner and Learner Modeling Workbench[END_REF]. Currently computer games is the biggest sector of the entertainment industry in the U.S. and one of the biggest in the world [START_REF]ESSENTIAL FACTS About the computer and video game industry[END_REF]. The Serious Games (SG) industry produces games for niche target markets and specific audiences. Yet, the entertainment industry pushes forward the benchmarks on the quality of game development, at every new release, supported by large budgets and profits. The SG industry is thus faced with the problem of reaching these high expectations with reduced budgets, due to the smaller dimension of these niche markets [START_REF] Coehlo | Procedural Content Generation in Serious Games. Retrieved from News and Insights from EAI community blog[END_REF].

The first attempts to combine education with entertainment were in the 1990s and it was called edutainment. The assessments in edutainment, if any, were largely limited to (screen-based) testing or log files. There is a false assumption that if an edutainment is well designed, it somehow results in student learning [START_REF] Loh | Measuring the (Dis-)Similarity between Expert and Novice Behaviors as Serious Games Analytics[END_REF]. As the enthusiasm fizzles, edutainment fails because it is neither a good education nor a well-done game [START_REF] Van Eck | Digital Game-Based Learning: It's Not Just the Digital Natives Who Are Restless[END_REF]. The most widely used education research methodology of pre-tests vs. post-tests [START_REF] Bellotti | Assessment in and of Serious Games: An overview[END_REF] is not suitable for serious games assessment because 'testing-after-playing' threatens to take the fun out of game-based learning altogether [START_REF] Prensky | Serious games debate. Serious Games Summit[END_REF].

It is a challenge in any video game to teach a player how to play and to guide them through the game world; especially when dealing with a serious game, the challenge intensifies due to the inherent variations in student backgrounds, making the choice of how to guide the student from the start to the end of the game without direct instructor interactions a complex problem [START_REF] Tang | Solaris one -A serious game for thermodynamics[END_REF]. Furthermore even when SGs claimed to contain "measurable evidence of training or learning," the evidence presented is quite limited (to simple test score, number of mission accomplished, or best time) because there has yet to be any standardized performance metrics for SGs [START_REF] Loh | Measuring the (Dis-)Similarity between Expert and Novice Behaviors as Serious Games Analytics[END_REF]. A data-driven approach [START_REF] Thomas | Toward effective game-based social skills tutoring for children: An evaluation of a social adventure game[END_REF] and an evidence-centered design [START_REF] Shute | Modeling, Assessing, and Supporting Key Competencies Within Game Environments[END_REF] are much better assessment methods that will foster real adoption of serious games [START_REF] Ifenthaler | Assessment in Game-based Learning: Foundations, Innovations, and Perspectives[END_REF]. This can be resolved by endowing game AI with adaptive and/or personalized behaviour. There is a precise distinction between the term "personalized" and the related term "adaptive". Tailoring the game experience to a player is implemented by adapting part of the game. When game adaptations are not informed by the actual player in one way or the other, we refer to the game as being strictly adaptive. When, on the other hand, the adaptations are informed by the player, e.g. by determining automatically the difficulty level appropriate to the current player, we refer to the game as being personalised [START_REF] Bakkes | Personalised gaming[END_REF].

The Game Model Cycle

Serious games are usually seen as a compromise between games and education. Most of the times the educational game creator focuses on the educational part and misses the game factor. Games must be motivating and when missing the game factor, the learner is also missing the motivation. The goal is to have learners being self-directed and self-motivated, both because the activity is interesting in itself and because achieving the outcome is important. Figure 1 presents a tacit model of learning that is inherent in most studies of instructional games. First, the objective is to design an instructional program that incorporates certain features or characteristics of games. Second, these features trigger a cycle that includes user judgments or reactions such as enjoyment or interest, learner behaviours such as greater persistence or time on task, and further system feedback. To the extent that we are successful in pairing instructional content with appropriate game features, this cycle results in recurring and self-motivated game play. Finally, this engagement in game play leads to the achievement of training objectives and specific learning outcomes [START_REF] Garris | Games, Motivation, and Learning: A Research and Practice Model[END_REF].

The problem with this model is that it doesn't take into consideration the characteristics of the learner. It supposes that all learners respond in the same way on the Game Characteristics and, furthermore, they assimilate the Instructional Content in the same manner. The system feedback should be re-engineered in such way that includes both the Instructional Content and the Game Characteristics. In that way it could avoid the disengagement of the gamer from the game and keep him motivating much longer.

However, at this point another question is raised: what are the exact elements in the game that can be adapted and how might these impact different types of learners? [START_REF] Hendrix | Integrating Serious Games in Adaptive Hypermedia Applications for Personalised Learning Experiences[END_REF] It has been suggested that the adaptation process should involve two distinct challenges: User Identification and Content Adaptation [START_REF] Brisson | Artificial Intelligence and Personalization Opportunities for Serious Games[END_REF].

• User Identification is the process of identifying and inferring the characteristics of the person who plays the game. There are two sub topics that are extremely relevant for identifying a user and keep him actively involved in the interactive learning process: User Models for Interactive Learning and Detection of User Engagement.

• Content Adaptation can be used to provide an effective system response to who is playing the game, by presenting a personalized view of the game content and learning materials.

There have been suggested enough techniques on User identification in gaming. The RET scheme, which is based on the Kullback-Leibler divergence between idle time distributions, achieves higher than 90% accuracy with a 20 minute detection time given a 200 minute history size [START_REF] Chen | Learner identification based on game-play activity patterns[END_REF]. Gametrics ("Game-based biometrics"), is another User Identification mechanism based on the unique way the user solves such simple challenges captured by multiple features related to cognitive abilities and mouse dynamics [START_REF] Mohamed | Gametrics: towards attack-resilient behavioral authentication with simple cognitive games[END_REF].

The most basic kind of content adaptation found in games is based on changing difficulty based on a finite set of stereotypes (e.g. "novice", "intermediate" and "expert"). This helps a player find the golden mean between boredom and frustration [START_REF] Marchiori | A visual language for the creation of narrative educational games[END_REF]. A supporting user model should responsible for dynamically assigning the player to different learning styles and stereotypes. The appropriate strategies can then be applied by a specialized component (e.g. centralized AI managers, content generators, agent organization frameworks), which constructs and presents the personalized content to the player [START_REF] Brisson | Artificial Intelligence and Personalization Opportunities for Serious Games[END_REF].

Towards an Improved Game Model

In order to add the personalization and adaption stage we propose to modify the aforementioned Game Model Cycle with the development and deployment of intelligent agents (IA). An agent is defined as a computer system that is situated in some environment, and is capable of autonomous action in that environment in order to meet its design objectives [START_REF] Wooldridge | Intelligent agents: theory and practice[END_REF]. An intelligent agent (IA) is an autonomous entity which observes through sensors and acts upon an environment using actuators (i.e., it is an agent) and directs its activity towards achieving goals [START_REF]Wikipedia[END_REF].

Fig. 2. The improved and Personalised Game Model

The proposed solution (Fig. 2) is a multi-agent system (MAS), where the activities of the system are distributed. A multi-agent system (MAS or "self-organized system") is a computerized system composed of multiple interacting intelligent agents. Multi-agent systems can solve problems that are difficult or impossible for an individual agent or a monolithic system to solve [START_REF]Wikipedia. Retrieved from Multi-agent system[END_REF]. This MAS system turns the revised Game Model Cycle to a decision support system (DSS), since now it supports organisational decision-making activities. Intelligent agents appear in an increasing number of DSS applications and intelligent agents' properties can facilitate active decision making [START_REF] Xu | Intelligent Agent-Assisted Decision Support for Personalized Virtual Learning[END_REF]. Intelligent DSSs (IDSSs), incorporating knowledge-based methodology, are designed to aid the decision-making process through a set of recommendations reflecting domain expertise [START_REF] Wang | Intelligent agent assisted decision support systems: integration of knowledge discovery, knowledge analysis, and group decision support[END_REF].

System Design Architecture

Personalization in the above system was designed as personalized instructional content and also adaptive game characteristics. I order to be functional, we propose a framework for an IA-assisted DSS that targets achieving learning effectiveness and supports the major phases of personalization decision making [START_REF] Xu | Intelligent Agent-Assisted Decision Support for Personalized Virtual Learning[END_REF]. The personalisation model that we choose to follow in this research is based on previous research [START_REF] Wang | Intelligent agent assisted decision support systems: integration of knowledge discovery, knowledge analysis, and group decision support[END_REF][START_REF] Xu | Intelligent Agent-Assisted Decision Support for Personalized Virtual Learning[END_REF][START_REF] Xu | Intelligent agent supported personalization for virtual learning environments[END_REF] and follows a constructivist pedagogical principle. Constructivism is a learning theory found in psychology, which explains how people might acquire knowledge and learn.

The theory suggests that humans construct knowledge and meaning from their experiences [START_REF]The University of Sydney School of Education and Social Work[END_REF]. So learning is a learner-cantered and active process of knowledge construction. Learners can learn more effectively and meaningfully in a favourable environment where their ideas are explored, compared, criticized, and reinforced through talking with and listening to others [START_REF] Tsai | Relationships between student scientific epistemological beliefs and perceptions of constructivist learning environments[END_REF].

The Learner Agent

The Learner Agent is a simple intelligent agent that collects information from the learner, such as the basic identification data, prior skills, educational goals, game results, or any other appropriate data. It also records activities, such as mouse action (time and target), duration on a particular task, game score and any other user generated data. This information (Learner Data) is then passed to the Adaption and personalization engine.

The adaption and personalization model

The adaption and personalization engine design is based on Decision-Making Process Model for Personalized Virtual Learning Environment (VLE) [START_REF] Xu | Intelligent Agent-Assisted Decision Support for Personalized Virtual Learning[END_REF]. While working on personalised virtual learning systems, Xu & Gao designed a framework for an intelligent agent-assisted decision support system that targets achieving learning effectiveness and supports the major phases of personalization decision making that was based on learning and decision-making theories. More specific the model was based on the constructivist pedagogical principle. The main idea behind constructivism is to focus on guiding the learner to build or modify existing knowledge, rather than to rely on knowledge transmission [START_REF] Slavin | Educational Psychology: Theory and Practice, Tenth Edition[END_REF]. There are three different interpretations of constructivism that have been labelled as endogenous, exogenous and dialectical [START_REF] Moshman | Exogenous, endogenous, and dialectical constructivism[END_REF]. Endogenous constructivism emphasizes on the individual nature of each learner's knowledge construction process, exogenous constructivism emphasizes on formal instruction in conjunction with exercises and finally dialectical constructivism is the view that learning occurs through realistic experience [START_REF] Dalgarno | Interpretations of constructivism and consequences for Computer Assisted Learning[END_REF]. A SG is closer to the endogenous model since it provides a realistic context in which learners can explore and experiment and the interactivity of the SG allows learners to see immediate results. But when instructional material is to be used, an important element of instructional process is the provision of opportunities for the user to put his knowledge into practice and receive feedback on his knowledge constructions [START_REF] Dalgarno | Interpretations of constructivism and consequences for Computer Assisted Learning[END_REF]. So in order to follow that approach, the adaption and personalization engine should contain a content database with content suited to different types of stereotype learners and also different learning strategies.

The most famous constructivist model of the decision-making process, identifies four different phases -intelligence, design, choice, and review [START_REF] Simon | The new science of management decision[END_REF]. Based on that framework Gao and Xu created their own model of Decision-Making Model. However, they omitted the fourth phase, the review activity, the purpose of which is to assess the past decisions. Instead, they added a feedback loop that can be used to restart the decision-making process again (See Fig. 3).

Fig. 3. Personalization Decision-Making Process Model for VLE [39]

The intelligence phase incorporates agents that gather information from electronic sources and the user in order to inform the user and other agents and to detect developing problems and opportunities [START_REF] Vahidov | Pluralistic multi-agent decision support system: a framework and an empirical test[END_REF]. The most common form of computer "support" for this initial phase in designing a Personalised VLE is to provide convenient access to a variety of information sources, such as the learner's demographic information, preference information, learning activity history, and previous learning results [START_REF] Xu | Intelligent Agent-Assisted Decision Support for Personalized Virtual Learning[END_REF]. Automated gathering of relevant information is very crucial for competitive intelligence [START_REF] Teo | Assessing the impact of using the Internet for competitive intelligence[END_REF]. As long as the system collects all necessary information, it needs to create the learner profile based on learner's personal information and learning activities. When a leaner profile is built, a call for decision-making regarding personalization will be launched and passed to the next phase [START_REF] Xu | Intelligent Agent-Assisted Decision Support for Personalized Virtual Learning[END_REF]. It has been also suggested that learner profile should be portable across different games and even applications, particularly in the education field [START_REF] Bellotti | Assessment in and of Serious Games: An overview[END_REF].

In that phase the learner model will be abstracted based on the learner profile. To achieve this, it is necessary to first analyse the user profile generated from the intelligence phase. It is very important at this stage to assemble the information in order to calculate the overall knowledge level and time spent on the current topics. It is also important to take the learner's demographic (e.g., age and education level) and preference into account. After building or refining the learner model, it is passed to the next phase [START_REF] Xu | Intelligent Agent-Assisted Decision Support for Personalized Virtual Learning[END_REF]. Learner model is defined shortly as a description of learner's properties and it is the core of adaptive learning system [START_REF] Fröschl | Learner Model in Adaptive Learning[END_REF]. The Learner Model is usually confused with the User Model. Learner modelling though is more concerned with diagnosing learner misconceptions and user modelling is more relevant to natural language understanding [START_REF] Newzoo | Global Games Market Report[END_REF]. For the domain of modern video games, four approaches are deemed applicable to player behavioural modelling, namely (1) modelling actions, (2) modelling tactics, (3) modelling strategies, and (4) profiling a player [START_REF] Bakkes | Player Behavioural Modelling for Video Games[END_REF].

In the choice phase, after each individual player's activity is specified, the corresponding set of instructions will be provided. In conjunction with the content data-base, the individual learner plan that determines the appropriate instructional action based on the individual learner model is updated. These instructional actions are executed including the personalization content materials and game mechanics for each individual learner to match the individual's learner model [START_REF] Xu | Intelligent Agent-Assisted Decision Support for Personalized Virtual Learning[END_REF].

Architecture design for adaption and personalization engine

Based on the above model, the adaption and personalization agent should be consisted from three separate layers, the Learner Layer, the Agents Layer and the Repository Layer (see Fig. 4). The upper layer (Learner Layer) provides an adaptive interface for the gamer. The interface adaption should comprise two separate mechanisms, the Game Mechanics Adaption and the Content Personalization.

The main mechanism behind the Mechanics Adaption is Dynamic Difficulty Adaptation (DDA) and it is based on the mathematical analysis of structures and relationships within a game system [START_REF] Hunicke | The case for dynamic difficulty adjustment in games[END_REF] and on the player's flow experience [START_REF] Tremblay | Adaptive Game Mechanics for Learning Purposes -Making Serious Games Playable and Fun[END_REF]. DDA uses a system that changes the game mechanics without the player knowing it. These changes are made in order to keep the player challenged and interested [START_REF] Hunicke | AI for Dynamic Difficulty Adjustment in Games[END_REF]. The Learner Agent analyses the player's state of flow and sends its activities to the Activities Agent, in order to create the player's profile, and forwards it to the Modelling Agent. The Modelling Agent creates the player's model, which is then forwarded to the Planning Agent, who then notifies the Learner Agent on the changes on the Game Mechanics. Lastly, the Learner Agent applies the changes.

As an example consider the case when the player is having to answer a quiz or a set of questions in order to proceed to the game and he is having hard time to find the right answers. The game could be too difficult. The system then should decide to create a set of hints available to the player. One assumption is to make sure the player does not know about systems such as the DDA [START_REF] Hunicke | The case for dynamic difficulty adjustment in games[END_REF]. The system analyses the player's data based on the player's flow experience. However, one of the major problems with DDA is that the system bases its decisions on the player's flow state using only raw data. The raw data used represents the performance of the player, which is objective, while flow is subjective [START_REF] Chen | MFA in Interactive Media[END_REF]. Rule-based personalization can then be used to target instructional content and media to specific individuals based on their profile. Rule-based personalization can go many levels deeper, by tracking the students' knowledge [START_REF] Hung | Constructivism and e-learning: Balancing between the individual and social levels of cognition[END_REF]. By keeping a history of the students' activities, the SG adaption engine would be able to recommend the appropriate material for the students. It would also be able to recommend directions for the students, for example, possible assignments inside the SG when the student lacks certain knowledge on a field. This can be achieved by a local content database that will be attached to the system on the Planning Agent.

The middle layer (Fig. 5), in order to be consistent with the constructivist model that was analysed before, consists of a number of intelligent decision-making agents that support the personalisation and adaption [START_REF] Xu | Intelligent Agent-Assisted Decision Support for Personalized Virtual Learning[END_REF]. The Activity Agent records the Learner's activities, such as mouse action (time and target), answering time on a particular task, game score and other user generated data. Those activities are captured and stored in the learner profile by the Activity Agent. The Modelling Agent abstracts the learner model, based on the learner profile. The Learner model keeps updating as long as the player plays and it could be stored in order to be reused each time the specific player plays the game. The Planning agent analyses the current learning plan of the particular learner based on the learner model and the content model, and then updates the learning plan. As an example, the topic sequence may be updated. Meanwhile, the planning agent is also able to exhibit goal-directed behaviours by using the pro-activity. For example, when the planning agent determines that the online learner may fail a game, the agent may update his/her learning plan to prevent this unexpected problem happening. Fig. 5. Adaption and personalization engine, Agents Layer [START_REF] Xu | Intelligent agent supported personalization for virtual learning environments[END_REF] The Learner dynamically assembles personalized instructional materials for a particular online learner based on the learning plan. It also dynamically interacts with the Game Mechanics in order to adapt the game to the player.

The lower layer is the repository layer that contains four components: Learner Profile, Learner Model, Learning Plan and Content Model. Dynamic knowledge relevant to the Learning process (learner profile, model and plan), and static structured knowledge (course content) are stored in the knowledge repository for the knowledge manipulations [START_REF] Xu | Intelligent Agent-Assisted Decision Support for Personalized Virtual Learning[END_REF]. It is essential to design a set of autonomous types of behaviours for the agents to achieve personalization, including "reactive", "pro-active" and "co-operative" behaviours [START_REF] Wooldridge | Intelligent agents: theory and practice[END_REF].

Conclusion and future work

In this paper, we proposed an adaption and personalisation mechanisms framework for serious games and we described how to implement them. This has been achieved by reviewing existing literature on adaptive models for games and especially SGs, whereas we proposed a new adaptive approach based on Virtual Learning Environments. That new approach follows the constructivism pedagogic approach for the instructional content adaption. The game mechanics adaption on the other hand will be mainly based on the Dynamic Difficulty Adaption technique. The next steps in this project will be the creation of a SG in order to implement our adaptive mechanism and then to test it. We also plan to explore the different adaptive game mechanics. Implementing these models could help the design process for a new generation of serious games that are fun but also educating.

Fig. 1 .

 1 Fig.1. Input-Process-Outcome Game Model[START_REF] Garris | Games, Motivation, and Learning: A Research and Practice Model[END_REF]

Fig. 4 .

 4 Fig. 4. The Three Layer Adaption & Personalisation Design[START_REF] Xu | Intelligent agent supported personalization for virtual learning environments[END_REF]


Theodoros Iliou
email: tiliou@med.duth.gr

Georgia Konstantopoulou

Christina Lymperopoulou

Konstantinos Anastasopoulos

George Anastassopoulos

Dimitrios Margounakis
email: margounakis.dimitrios@ac.eap.gr

Dimitrios Lymberopoulos

Iliou Machine Learning Data Preprocessing Method for Suicide Prediction from Family History

Keywords: Data preprocessing, machine learning, data mining, classification algorithms, suicide, family history

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Suicide is considered as a major public health problem with increasing trends in many developed and developing countries. Suicide is among the ten leading causes of death for all age ranges [START_REF] Jacobs | Language Barriers in Health Care Settings: An Annotated Bibliography of the Research Literature[END_REF]. Factors that have been associated mainly with increased risk of suicide are socio-demographic factors, psychiatric morbidity, physical health problems and biological background. Suicidal behavior is defined as the behavior in which a person wants to harm himself in order to put an end to his life. It can be distinguished in suicide attempts, in which the person does not achieve his ultimate goal and suicides in which death is achieved [START_REF] De Leo | Definitions of Suicidal Behavior[END_REF]. Suicidal ideation concerns thoughts connected with desire, intention and method of suicide. According to O'Carroll et al. (1996), suicidal ideation refers to self-reported thoughts of committing suicide-related behavior. It includes thoughts of suicidal behaviors. Whereas, attempting suicide is the self-induced act of auto-harming committed with the intention of the person to end his life [START_REF] O'carroll | Beyond the Tower of Babel: A nomenclature for suicidology[END_REF]. Other mental disorders associated with suicide are schizophrenia, substance abuse, alcoholism, personality disorders (especially antisocial and borderline personality disorders), panic disorder, etc. Factors associated with increased rates of suicide include drug abuse, psychological states, cultural, family and social situations, and genetic predisposition [START_REF] Hawton | Self-harm and suicide in adolescents[END_REF]. Mental illness and drug use often co-exist [START_REF] Vijayakumar | Substance use and suicide[END_REF]. Other risk factors include: previous suicide attempts [START_REF] Chang | The depressed patient and suicidal patient in the emergency department: evidence-based management and treatment strategies[END_REF], the immediate access to an instrument which can help to commit suicide, a family history of suicide, or the presence of traumatic brain injury [START_REF] Simpson | Suicidality in people surviving a traumatic brain injury: prevalence, risk factors and implications for clinical management[END_REF]. For example, it has been found that suicide rates are higher in houses where there are weapons, than in those that do not have [START_REF] Miller | Suicide mortality in the United States: the importance of attending to method in understanding population-level disparities in the burden of suicide[END_REF]. Socioeconomic factors such as unemployment, poverty, homelessness and discrimination may trigger suicidal thoughts [START_REF] Qin | Suicide risk in relation to socioeconomic, demographic, psychiatric, and familial factors: a national register-based study of all suicides in Denmark, 1981-1997[END_REF]. Approximately 15-40% of victims leave a suicide note [START_REF] Gilliland | Crisis intervention strategies[END_REF]. Genetic susceptibility appears to represent 38% to 55% of suicidal behaviors [START_REF] Brent | Familial transmission of suicidal behavior[END_REF]. The war veterans are at greater risk of committing suicide and this is partly due to higher rates of mental illness and physical health problems associated with the war [START_REF] Rozanov | Suicide among war veterans[END_REF]. Family history of suicidal behavior greatly increases the risk for suicide. Also, the presence of parents' psychopathology and particularly depression and substance use were associated with suicide. Moreover, according to some studies, the suicide victims are more likely to come from families of divorced parents. This paper is structured as follows: Section 2 provides a review of the related literature regarding machine learning techniques used for classification or prediction. Section 3 describes the basic principles of the data preprocessing procedure and section 4 describes ILIOU preprocessing method. Finally, Section 5 presents the experimental results of this study, while Section 6 concludes this paper and describes future work.

RELATED WORK

In other paper we establish a novel data preprocessing method for improving the prognosis' possibilities of a patient suffering from depression to be leaded, to the suicide [START_REF] García | Data Preprocessing in Data Mining[END_REF]. For this reason, the effectiveness of many machine learning classification algorithms is measured, with and without the use of our suggested preprocessing method. The experimental results reveal that our novel proposed data preprocessing method markedly improved the overall performance on initial dataset comparing with Principal Component Analysis (PCA) and Evolutionary search feature selection methods. So this preprocessing method can be used for significantly boost classification algorithms performance in similar datasets and can be used for suicide tendency prediction [START_REF] García | Data Preprocessing in Data Mining[END_REF]. Traditional approaches to the prediction of suicide attempts have limited the accuracy and scale of risk detection for these dangerous behaviors [START_REF] Han | Data Mining: Concepts and Techniques[END_REF]. They sought to overcome these limitations by applying machine learning to electronic health records within a large medical database. Participants were 5,167 adult patients with a claim code for self-injury (i.e., ICD-9, E95x), expert review of records determined that 3,250 patients made a suicide attempt (i.e., cases), and 1,917 patients engaged in selfinjury that was nonsuicidal, accidental, or unverifiable (i.e., controls). We developed machine learning algorithms that accurately predicted future suicide attempts (AUC = 0.84, precision = 0.79, recall = 0.95, Brier score = 0.14). Moreover, accuracy improved from 720 days to 7 days before the suicide attempt, and predictor importance shifted across time. These findings represent a step toward accurate and scalable risk detection and provide insight into how suicide attempt risk shifts over time [START_REF] Zaki | Data Mining and Analysis: Fundamental Concepts and Algorithms[END_REF].

In this paper we had responses from 360 students, aged 18 to 24, and were collected during the clinical interview, which included the following questions: "Is there family history of psychopathology?", "Is there death incident in your family?" "There is abuse incident in your family?", "Is there a chronically ill or disabled person in your family?", "Is there a person in the family who attempted suicide or committed suicide?", "Is there in your family alcoholic or drug user?", "Do you have you thoughts of committing suicide?".

DATA PREPROCESSING

The set of techniques used prior to the application of a data mining method is named as data preprocessing for data mining [START_REF] Kohavi | A study of cross-validation and bootstrap for accuracy estimation and model selection[END_REF] and it is known to be one of the most meaningful issues within the famous Knowledge Discovery from Data process [START_REF]Waikato Environment for Knowledge Analysis, Data Mining Software in Java[END_REF][START_REF] Iliou | Machine Learning Preprocessing Method for Suicide Prediction[END_REF]. Since real world data are generally imperfect, incomplete (lacking attribute values, lacking certain attributes of interest, or containing only aggregate data), noisy (containing errors or outliers), inconsistent (containing discrepancies in codes or names) and contain redundancies, is not directly applicable for a starting a data mining process. We must also mention the fast growing of data generation rates and their size in business, industrial, academic and science applications. The bigger amounts of data collected require more sophisticated mechanisms to analyze it. Data preprocessing is able to adapt the data to the requirements posed by each data mining algorithm, enabling to process data that would be unfeasible otherwise. Data preprocessing includes (figure 1):

 Data cleaning: fill in missing values, smooth noisy data, identify or remove outliers, and resolve inconsistencies.  Data integration: using multiple databases or files.  Data transformation: normalization and aggregation.  Data reduction: reducing the features of the initial dataset but producing the same or similar analytical results.

ILIOU PREPROCESSING METHOD

In figure 1, a brief description of ILIOU method is presented. (3)

j m 3) (step m j m _row class RS_Median_ - ian total_Med _row an Final_Medi  (4)
(Equation 4)

j m 3) (step m j m _row ass RS_Mean_cl - n total_Mea _row Final_Mean  (3)
j m 3) (step m j m _row class RS_Median_ - ian total_Med _row an Final_Medi  (4)

EXPERIMENTAL RESULTS

For testing the generalization of our reprocessing method we used the repeated

CONCLUSIONS

Data have quality if they satisfy the requirements of the intended use. Factors, such as accuracy, completeness, consistency, timeliness, believability and interpretability, affect data quality. Given that large real-world databases and data warehouses often consist of "bad" quality data, preparation, cleaning and transformation of data comprises the majority of the work in a data mining procedure. Thus, data preprocessing is a vital procedure for data mining process so that "good" quality data lead us to "good" quality results. The innovation of our work is that ILIOU preprocessing method not only reduce the variables of the initial dataset as every preprocessing method do but significantly improves the classification results as well, comparing with PCA which is a wellknown preprocessing method.

In this paper we used 10 classification schemes. According to the classification results, Iliou data preprocessing method not only outperform PCA but also achieves 100% classification performance. Concluding, Iliou method can be used to importantly boost classification algorithms performance in similar datasets and seems to be the best preprocessing approach for suicide prediction based on family history.

In the future, a significant challenge for researchers, practitioners and data scientists would be to collaborate in order to create more and bigger databases, and test Iliou and other preprocessing methods with even more classification schemes. Furthermore, Iliou data preprocessing method could be modified so as achieve less classification time and could be ensembled in a classification algorithm.

Figure 1

 1 Figure 1. ILIOU preprocessing method (Equation 1) ) _row Mean_class _row Mean_class _row s (Mean_clas Total_Mean d m 2 m 1 m m d     

Figure 2 .

 2 Figure 2. Experimental Results

Table 1 . Original data results

 1

	As shown in Tables 1, 2 and 3 and in figure 2, Iliou data
	preprocessing method has remarkably improved the classification
	performance (Correctly Classified Instances %) for each classifier
	compared to PCA and initial dataset classification performance.
	Iliou method achieved 100% classification performance with
	Multilayer Perceptron (MLP) classifier, whereas PCA has almost
	the same classification results (71.34%) as initial data
	classification (72.47%). PCA achieved maximum classification
	performance using Naïve Bayes, while the best classification
	results with initial dataset achieved by J48 and SMO classification
	algorithms. Hence, Iliou data preprocessing method noticeably
	outperform PCA for each classification scheme. As we notice the
	Precision, Recall and ROC values we also observe that ILIOU
	method has much higher values in these parameters that's why
	ILIOU method has the best classification performance. According
	to k and MCC value we also observe that ILIOU method's values
	are close to 1, which means that the classification results are not
	accidental.

10-fold cross validation technique [19] during the classification procedure. For the classification results we used some well-known classification algorithms in WEKA 3.8 data mining software [20] by their default WEKA parameters. The performance of the classifiers was measured by Precision, Recall, Kappa statistics, Weighted Avg ROC area, Weighted Avg Precision Recall Curve (PRC) area, Matthews correlation coefficient (MCC) and F-measure metrics. The comparison of the aforementioned statistics and metrics of the initial data set, of transformed data set with PCA and with Iliou preprocessing method are illustrated in Table 1-3.

Table 2 . PCA results

 2

	Classifiers	Correctly	Pre	Rec k	ROC PRC	F-	TP	FP	MCC Root
		Classified				Area	Measure	Rate	Rate		mean
		Instances									squared
		(%)									error
	IB1	54.49	0.57 0.54 0.0	0.55	0.55	0.551	0.54	0.43	0.10	0.67
	J48	69.66	0.72 0.69 0.2	0.65	0.64	0.646	0.69	0.47	0.33	0.457
	Ran For	67.97	0.67 0.68 0.2	0.65	0.65	0.652	0.68	0.44	0.27	0.46
	MLP	68.53	0.68 0.68 0.2	0.65	0.65	0.656	0.68	0.44	0.29	0.46
	SMO	71.06	0.72 0.71 0.3	0.63	0.62	0.676	0.71	0.43	0.36	0.53
	Jrip	69.94	0.69 0.69 0.3	0.64	0.63	0.686	0.69	0.39	0.33	0.45
	RBF	70.78	0.70 0.70 0.3	0.67	0.62	0.685	0.70	0.41	0.34	0.44
	Naïve Bayes	71.34	0.77 0.71 0.3	0.70	0.69	0.705	0.71	0.36	0.37	0.5
	AdaBoostM1	69.66	0.69 0.69 0.28 0.67	0.67	0.667	0.69	0.43	0.32	0.44
	HMM	37.92	0.14 0.37 0	0.5	0.52	0.209	0.37	0.37	0	0.5

Table 3 . ILIOU method results

 3

	Classifiers	Correctly	Pre	Rec	k	ROC PRC	F-	TP	FP	MCC Root
		Classified					Area	Measure	Rate	Rate		mean
		Instances										squared
		(%)										error
	IB1	98.8	0.988 0.988 0.97 0.990 0.984 0.988	0.988 0.007 0.975 0.10
	J48	95.6	0.958 0.956 0.90 0.964 0.950 0.956	0.956 0.035 0.909 0.20
	Ran For	97.6	0.977 0.976 0.94 0.997 0.997 0.976	0.976 0.015 0.951 0.13
	MLP	100	1	1	1	1	1	1	1	0	1	0.01
	SMO	78.4	0.78	0.78	0.5	0.75	0.71	0.781	0.78	0.26	0.53	0.46
	Jrip	96	0.96	0.96	0.9	0.97	0.95	0.96	0.96	0.02	0.92	0.19
	RBF	85.6	0.89	0.85	0.7	0.92	0.91	0.858	0.85	0.08	0.74	0.31
	Naïve Bayes	75.2	0.74	0.75	0.4	0.86	0.86	0.745	0.75	0.31	0.45	0.47
	AdaBoostM1	92	0.92	0.92	0.8	0.96	0.95	0.921	0.92	0.06	0.83	0.23
	HMM	38	0.14	0.38	0	0.5	0.52	0.209	0.38	0.38	0	0.5