Suchismita Das
email: suchismitasimply@gmail.com

Nikhil R Pal

An Unsupervised Fuzzy Rule-based Method for Structure Preserving Dimensionality Reduction with Prediction Ability

Keywords: Dimensionality reduction, fuzzy rules, predictability, Sammon's mapping

We propose an unsupervised fuzzy rule-based system to learn structure preserving data projection. Although, the framework is quite general and any structure preserving measure can be used, we use Sammon's stress, an extensively used objective function for dimensionality reduction. Unlike Sammon's method, it can predict the projection for new test points. To extract fuzzy rules, we perform fuzzy c-means clustering on the input data and translate the clusters to the antecedent parts of the rules. Initially, we set the consequent parameters of the rules with random values. We estimate the parameters of the rule base minimizing the Sammon's stress error function using gradient descent. We explore both Mamdani-Assilian and Takagi-Sugeno type fuzzy rulebased systems. An additional advantage of the proposed system over a neural network based generalization of the Sammon's method is that the proposed system can reject the test data that are far from the training data used to design the system. We use both synthetic as well as real-world datasets to validate the proposed scheme.

Introduction

We come across high dimensional datasets in various real-world problems related to finance, meteorology, computer vision, medical imaging, multimedia information processing, text mining, and many more [START_REF] Álvarez-Meza | Kernelbased dimensionality reduction using renyi's α-entropy measures of similarity[END_REF][START_REF] Talwalkar | Large-scale manifold learning[END_REF][START_REF] Van Der Maaten | Dimensionality reduction: a comparative[END_REF][START_REF] Wang | A perception-driven approach to supervised dimensionality reduction for visualization[END_REF]. Handling high dimensional data is difficult as it demands more storage space, more processing time, and increased system complexity. For many applications, visualization of the structure in the data is important which is difficult for high dimensional data. Dimensionality reduction (DR) is a process that addresses these problems by representing a high dimensional data into a lower dimensional space, keeping the relevant information as intact as possible. DR schemes can be broadly categorized into two groups: feature selection (FS) and feature extraction (FE). FS chooses a small but important subset of features, whereas, FE constructs a smaller number of new features from the original features. Methods of FE are more appropriate when the system does not bother about the physical meaning of the extracted features and focuses principally on preserving the local or global structure present in the original data.

We mathematically formulate FE as follows. Let the input data be represented by the set X = {x i ∈ R D : i ∈ {1, 2, • • • , n}}. Here, n is the number of instances and D is the dimensionality of the data. The vector x i represents the ith instance of the data and x ik represents the value of the kth feature associated with the ith instance. Then, ∀x i ∈ X , the corresponding lower dimensional representation is y i ∈ R D , D < D. Let us represent the output dataset as

Y = {y i ∈ R D : i ∈ {1, 2, • • • , n}}.
FE is finding an implicit or explicit mapping, φ : R D → R D , such that, an objective ψ is minimized/maximized. Usually, ψ is a function of X and Y, where y i = φ (x i ) , ∀i. Then, the obtained optimal mapping φ = arg min φ {ψ (X , Y)}.

The Sammon's method [START_REF] Sammon | A nonlinear mapping for data structure analysis[END_REF] is a popular nonlinear FE technique that does not learn the mapping function φ explicitly. It aims to preserve certain geometric properties of the data by preserving the inter-point distances in the original higher dimensional space as the inter-point distances in the extracted lower dimensional space as much as possible. It reduces the following error function E (i.e., ψ):

E = 1 n-1 i=1 n j=i+1 d * ij n-1 i=1 n j=i+1 d * ij -d ij 2 d * ij (1)
Here, d ij and d * ij are the Euclidean distances between x i and x j ; and y i and y j ; respectively. The error function, E, is called Sammon's stress. To minimize E, Sammon's method employs the steepest descent method. Note that, for a fixed pair of points i and j, Sammon's strss multiplies a factor 1

/d * ij to d * ij -d ij 2 .
As a result, the method pays more attention in preserving short pairwise distances, and hence, preserves the local structure. The Sammon's method is a corner-stone method in structure preserving dimensionaity reduction. However, it has a drawback: it does not learn the mapping function φ(•) explicitly. After learning a mapping from n points, when a new point occurs, the Sammon's method needs to repeat the whole optimization process considering the (n + 1) points. From (1) we observe that, every iteration in the steepest descent search requires computation of n(n-1) /2 distances. When n is large, computations involved may be prohibitive. Another disadvantage of Sammon's method is that it optimizes a non-convex objective. So, it is possible that the method may get stuck at some local minima on the error surface. To avoid such a situation and to obtain a good solution the method needs to try several initializations. This again adds to the computational overhead.

To reduce the computational cost associated with Sammon's method, some attempts have been made to learn an explicit mapping with the Sammon's objective function. Jain and Mao [START_REF] Jain | Artificial neural network for nonlinear projection of multivariate data[END_REF][START_REF] Mao | Artificial neural networks for feature extraction and multivariate data projection[END_REF] have used a multilayer feed-forward network to learn Sammon's projection based explicit mapping. The number of input nodes and the number of output nodes of the neural network are set to D and D , respectively. A pair of inputs x i and x j is applied one after another and their corresponding outputs y i and y j are used to define the error function E. A problem with neural network based methods is that they predict outputs even when the test points are far away from the training data. Again, in [START_REF] Pal | Fuzzy logic approaches to structure preserving dimensionality reduction[END_REF], a supervised fuzzy rule-based model has been proposed to learn the Sammon's projection parametrically. This method first generates the Sammon's projection of the input data. Then, a fuzzy rule base is learnt using a supervised learning scheme, where the obtained output from Sammon's projection is used as the target. An advantage of this method [START_REF] Pal | Fuzzy logic approaches to structure preserving dimensionality reduction[END_REF] over the neural network based methods [START_REF] Jain | Artificial neural network for nonlinear projection of multivariate data[END_REF][START_REF] Mao | Artificial neural networks for feature extraction and multivariate data projection[END_REF] is that it can be used to detect test instances that are far away from the training data. However, it [START_REF] Pal | Fuzzy logic approaches to structure preserving dimensionality reduction[END_REF] has the following drawback. The computational cost for this method comprises the computational cost for obtaining Sammon's projection and computational cost for learning the fuzzy system.

The objective of this paper is to propose a method for structure preserving dimensionality reduction. Although, any stress function can be used, we use here Sammon's error, such that, it should avoid the additional computational overheads associated with the methods in [START_REF] Sammon | A nonlinear mapping for data structure analysis[END_REF][START_REF] Pal | Fuzzy logic approaches to structure preserving dimensionality reduction[END_REF]. Additionally unlike [START_REF] Jain | Artificial neural network for nonlinear projection of multivariate data[END_REF][START_REF] Mao | Artificial neural networks for feature extraction and multivariate data projection[END_REF], it should decline to produce outcomes when the test points are far away from the training data. To achieve our objectives, here, we have contributed in the following ways:

1. We have proposed a fuzzy rule-based method which learns an explicit mapping function with the objective of Sammon's method in an unsupervised fashion. It is unsupervised as there are no target values provided for the inputs. It is quite general and other objectives can also be used. 2. We have equipped the Sammon's method with predictability, and hence, have cut down the computational cost associated with Sammon's method to project new points. 3. The proposed system can indicate when its projection may not be reliable.

Proposed Method

The proposed method has the following major steps.

1. Form an initial fuzzy rule base R. 2. Project input dataset X with R to obtain corresponding output Y. 3. Modify R to reduce the Sammon's stress defined by X and Y. 4. Repeat steps 2 and 3 until convergence. 5. Use R to project new points.

Next, we discuss the rule-based system used in this work, and then, we discuss the above steps with further details

The Rule-based System

We explore both Mamdani-Assilian (MA) and Takagi-Sugeno (TS) type fuzzy rule-based systems. Let there be r rules in the rule base. Let, for the ith sample x i , the mth output feature produced by the kth rule be y

k im . Here, m ∈ {1, 2, • • • , D }; k ∈ {1, 2, • • • , r}; and i ∈ {1, 2, • • • , n}.
For MA and TS models, the rules are denoted by R M A km and R T S km , respectively. They are defined as follows.

R M A km :If x i1 is A k1 and x i2 is A k2 and • • • x iD is A kD then y k im is B km . (2) R T S km :If x i1 is A k1 and x i2 is A k2 and • • • x iD is A kD then y k im = u km (x i ). (3)
Here, A kl is the kth fuzzy set (linguistic value) on the lth input feature and B km is the kth output fuzzy set on the mth output variable; u km () : R D → R is a mapping function associated with the kth rule for the mth output feature.

Let, α k i be the firing strength of the kth fuzzy rule for the ith input x i . The rule firing strength is computed as the conjunction of D atomic clauses in (2)/(3) using a T -norm [START_REF] Gupta | Theory of t-norms and fuzzy inference methods[END_REF] over the fuzzy sets A k1 , A k2 , • • • A kD . We use the product operator here. For both MA and TS models, the output

y i = (y i1 , y i2 , • • • , y iD ) T is given by y im = r k=1 α k i y k im r k=1 α k i . (4)
We shall explain later how for the MA model we get the value of y k im from B km . We note here that, for MA models, more involved method of defuzzification can be used [START_REF] Driankov | An introduction to fuzzy control[END_REF].

Initial Rule Base Formation

When both input-output data are provided there are many ways of generating an initial rule base and its refinement [START_REF] Wang | Generating fuzzy rules by learning from examples[END_REF][START_REF] Cordón | A two-stage evolutionary process for designing tsk fuzzy rule-based systems[END_REF][START_REF] Mitra | Neuro-fuzzy rule generation: survey in soft computing framework[END_REF][START_REF] Pal | Fuzzy logic approaches to structure preserving dimensionality reduction[END_REF][START_REF] Pal | Simultaneous structure identification and fuzzy rule generation for takagi-sugeno models[END_REF][START_REF] Chen | An integrated mechanism for feature selection and fuzzy rule extraction for classification[END_REF]. Some of the popular methods use clustering [START_REF] Pal | Fuzzy logic approaches to structure preserving dimensionality reduction[END_REF][START_REF] Pal | Simultaneous structure identification and fuzzy rule generation for takagi-sugeno models[END_REF][START_REF] Chen | An integrated mechanism for feature selection and fuzzy rule extraction for classification[END_REF] of input-output data. The philosophy behind the use of clustering is that if there is cluster in the input space with centroid v k ∈ R D , for a smooth input-output relationship, the points in the output space are likely to form cluster around u k (which is the lower dimensional representation of v k ). But here, we do not have any output data. We, however, use the clustering approach on the input data. We use the fuzzy c-means clustering algorithm [START_REF] Bezdek | Fcm: The fuzzy c-means clustering algorithm[END_REF] to find r clusters in the input data X . The cluster centroids are denoted by

v k = (v k1 , v k2 , • • • , v kD ) T ∈ R D ; k ∈ {1, 2, • • • , r}.
The kth cluster is translated into the antecedent of the kth rule as follows.

If x i1 is close to v k1 and
x i2 is close to v k2 and . . .

x iD is close to v kD . (5)
Here, x il is close to v kl is modeled using a Gaussian membership function centered at m kl with spread σ kl . The membership for x il is

µ ikl = exp - (x il -v kl ) 2 2σ 2 kl . (6)
Here, v kl s and σ kl s are the antecedent parameters of the rules.

For both MA and TS model, though we use the same fashion to define the rule-antecedents, we use different types of consequents. We discuss this next.

For MA model the rule-consequents are fuzzy sets in the output feature space. For each rule the output is a fuzzy set and the union of these fuzzy sets constitutes the fuzzy output which can be defuzzified using several methods [START_REF] Driankov | An introduction to fuzzy control[END_REF]. For simplicity, here we use the height method of defuzzification [START_REF] Driankov | An introduction to fuzzy control[END_REF]. Let B km be either a symmetric triangular or Gaussian membership function with center at h km . According to the height method the output of the rule R M A km is taken as h km . Note that this becomes equivalent to the zeroth order TS model.

For the TS model, a consequent denotes an input-output mapping. For the first order TS model, this input-output mapping is a linear one and is described as follows.

y k im = u km (x i ) = c km0 + D l=1 c kml x il (7)
Thus, the kth rule for TS model becomes

R T S km : If x i1 is close to v k1 and x i2 is close to v k2 . . . x iD is close to v kD then y k im = c km0 + D l=1 c kml x il . (8)
For formation of the initial rule base, we randomly initialize the consequent parameters (h km s for the MA model and c kml s for the TS model).

Training the Rule Base

We estimate the rule base parameters that minimizes the Sammon's stress E in (1) using gradient-descent optimization. The learning rules for this are as follows.

v km (t + 1) = v km (t) -η v ∂E ∂v km (9)
σ km (t + 1) = σ km (t) -η σ ∂E ∂σ km (10)
h km (t + 1) = h km (t) -η h ∂E ∂h km (11)
c kml (t + 1) = c kml (t) -η c ∂E ∂c kml (12)
Here, t indicates the iteration number. η v , η σ , η h and η c are learning rates for v, σ, h, and c, respectively.

Rejection of Outputs

An interesting feature of the proposed method is that it can reject test points for which it may not produce correct output. As shown in (4), the mth feature of ith output, y im , is computed as a convex sum of the rule outputs y k im s. Each rule output (y k im ) is multiplied by the firing strength (α k i ) of the corresponding rule. The rule that fires with the maximum strength, primarily characterizes the output. The profile of the maximum rule firing strength on the training data may help in rejection of test points in a desired manner. For test points far away from the training data, no rule is expected to fire strongly. Possibly, none of the rules are appropriate to model those test points. Thus, we can reject a test point when the maximum value of the firing strength associated with a test point is less than a given threshold. We choose the value of this threshold based on only the training data.

Experimentation

Dataset Descriptions and Experimental Settings

We use two synthetic datasets: S-Curve and Swiss Roll shown in Figs. 1a and2a, respectively. Both of them are three dimensional data consisting of 1000 points. They are generated using scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF] package (version 0.19.2) of Python. We also use a real-world dataset, Iris. Iris has 150 datapoints from three classes in four dimensional space, such that, in each class there are 50 points.

We choose the number of fuzzy rules or the number of clusters as 0.05n, where n is the number of points. In FCM clustering algorithm, the value of the fuzzifier and the maximum number of iterations are set to 2 and 200, respectively. We initialize the consequent parameters randomly in [-0.5, 0.5]. The spreads of the Gaussian membership functions in [START_REF] Driankov | An introduction to fuzzy control[END_REF] are initialized as 0.2β l and 0.3β l . Here, β l indicates the difference between the maximum and the minimum values of the lth feature. We repeat each experiment five times for each of these two initializations of the spreads. Out of these ten runs, the one with the minimum error (measured using (1)) is chosen as the output of the proposed algorithm. Note that, it is done automatically without any human intervention. To optimize the objective function in (1) using stochastic gradient descent, we use an optimizer, train.GradientDescentOptimizer, from a standard machine learning framework called TensorFlow [START_REF] Abadi | Tensorflow: A system for large-scale machine learning[END_REF]. The parameter learning rate is set to 2.0 and 0.1, respectively, for the MA and TS models. Thus, in experiments with MA models, all the three involved learning rates η v , η σ , and η h are equal to 2.0. Similarly for experiments with TS models,all the three involved learning rates η v , η σ , and η c are equal to 0.1.

Results and Discussions

Figures 1b, 2b and 3a show the results with Sammon's method [START_REF] Sammon | A nonlinear mapping for data structure analysis[END_REF] on S-Curve, Swiss Roll and Iris datasets, respectively. The results of the proposed method with the MA model on the three datasets are illustrated in Figs. 1c,2c, and 3b ,2, and 3, we observe that the proposed methods, both with MA and TS models, project the three datasets faithfully to a two dimensional space. For the synthetic datasets, we observe that the proposed method successfully preserves the underlying geometries as preserved in their Sammon's projection. We note that for S Curve, the MA model (with height method) produces somewhat better outcome than the TS model, whereas for Swiss Roll the TS model generates better projection than the MA model. In case of Iris dataset, separability of classes in the projected space is important. As seen in Figs. 3b and3c the separability between the three classes are similar as in the case of Sammon's method (Fig. 3a). We note here that different initializations and use of different number of rules may produce different results. In addition to the graphical results, to asses the quality of the projection, we present the value of the Pearson's correlation coefficient between pairwise distances in the input space and in the output space in Table 1. For all the three data sets we obtained quite high value of the correlation coefficients. This indicates that the relation among the pairwise distances of the inputs are mostly preserved in the obtained projections.

(a) (b) (c) (d)
To illustrate the predictability of the proposed model, we perform an experiment with the S-Curve dataset. A contiguous portion of the dataset containing 50 points is removed and the rest of the points form a training dataset (see Fig.

Conclusion

In this work, we have proposed a fuzzy rule-based scheme for learning Sammon's map explicitly. We have explored the MA model along with the height method of defuzzification. We have also used the TS model where consequents are a linear combination of input variables. For both the models the antecedent part is constructed by clustering the given input data. Antecedent and consequent parameters are modified using gradient descent search to obtain optimal values for minimizing the Sammon's stress. The obtained results depict that the proposed system successfully produce the structure-preserving projection as that of the original Sammon's method. It can also project the new (test) points in an expected manner. The framework is quite general and we can use objectives other than Sammon's stress. An issue with the proposed method is that the performance of the proposed method depends on the chosen number of clusters. Here, we have chosen the number of clusters based on our initial ad-hoc experiments. In future, we plan to investigate to address this issue. In our future works, we also plan to introduce regularizers to improve the quality of predictability. We have not investigated how the proposed method performs when it should reject the outputs. All these are left for our future work.

Fig. 1 :

 1 Fig. 1: Visualization of the S Curve data: (a) original, (b) Sammon's projection, (c) proposed method with MA model, (d) proposed method with TS model.

Fig. 2 :

 2 Fig. 2: Visualization of the Swiss Roll data: (a)original, (b)Sammon's projection, (c)proposed method with MA model, (d)proposed method with TS model.

Fig. 3 :

 3 Fig. 3: Visualization of the Iris data: (a) Sammon's projection, (b) proposed method with MA model, (c) proposed method with TS model.

  4a). The removed 50 points serve as the test dataset. The MA model and the TS model based proposed schemes are used to learn the training data. The corresponding outputs are shown in Figs. 4c and 4e respectively. The full dataset

Fig. 4 :

 4 Fig. 4: Visualization in the original space (a) training data, (b) full data. Visualization using proposed method with MA model, (c) training data (d) full data with prediction. Visualization using proposed method with TS model, (e) training data, (f) full data with prediction.

Table 1 :

 1 Pearson's correlation coefficient between the pairwise distances in the input and output spaces

	Dataset MA Model TS Model
	S-Curve	0.9653	0.9620
	Swiss Roll 0.8514	0.8594
	Iris	0.9978	0.9969

Table 2 :

 2 Pearson's correlation coefficient between the pairwise distances in the input and output spaces containing both the training and the test points, is shown in Fig. 4b. To differentiate the training and the test points, we represent them by circle (o) and plus (+) signs, respectively. The predictions for the test points obtained by the MA model and the TS model based proposed method are shown in Figs. 4dand 4f, respectively. We observe that irrespective of the types of the model, the proposed method projects test points in the expected region. However, the prediction by the MA model based method seems more appropriate than that of the TS model based method. In Table2, the values Pearson's correlation coefficient between pairwise distances in input and output spaces for the training set and the training and test set together are presented. For both MA and TS models the correlations for the training data are similar to those for the cases when the training and test data are taken together.

	Set	MA Model TS Model
	Train	0.9667	0.9611
	Train and test together 0.9649	0.9565


Giannis Maniadis

Konstantinos N Vavliakis
email: kvavliak@issel.ee.auth.gr

Andreas L Symeonidis

Banner Personalization for e-commerce

Keywords: Banner Personalization, e-Commerce, LDA, ANN

Real-time website personalization is a concept that is being discussed for more than a decade, but has only recently been applied in practice, according to new marketing trends. These trends emphasize on delivering user-specific content based on behavior and preferences. In this context, banner recommendation in the form of personalized ads is an approach that has attracted a lot of attention. Nevertheless, banner recommendation in terms of e-commerce main page sliders and static banners is even today an underestimated problem, as traditionally only large e-commerce stores deal with it. In this paper we propose an integrated framework for banner personalization in e-commerce that can be applied in small-medium e-retailers. Our approach combines topic-models and a neural network, in order to recommend and optimally rank available banners of an e-commerce store to each user separately. We evaluated our framework against a dataset from an active e-commerce store and show that it outperforms other popular approaches.

Introduction

Personalization allows e-retailers to understand consumers' concerns and propose the right products, at the right time, while not spending exaggerated effort to understand each customer's wills and needs. Personalization techniques became increasingly popular in recent years and are considered key elements in the modern e-commerce world. Many ecommerce stores use large banner or billboard graphics in their designs. Visitors make decisions about a new site in less than a second, so creating a positive first impression and making sure visitors know exactly that they're in the right place is crucial for e-commerce. Banners allow directing customers to the most compelling offers and increase attention to a specific product or brand, resulting to users being showered with hundreds of advertisements on a daily basis. As a result, they often pay little attention to banners appearing on a web page, unless there is increased correspondence between their interests and the subject of the displayed advertisement. But, not all customers are interested in all offers, as gender, age, past views and purchases are only some of the factors that affect users' interests. Thus, increasing the correlation between user interests and the subject of the displayed banners is necessary. Increasing this correspondence can be achieved by personalizing the banners displayed to each customer, which in turn is expected to increase effectiveness [START_REF] Adams | Intelligent advertising[END_REF]; the right person should receive the right message.

In the last years, personalized advertising, also known as interest-based advertising, has attracted a lot of attention. It is practically the main tool for improving advertising relevance for users and for increasing return-of-investment for advertisers. Corporations like Google, Amazon and Alibaba are making inferences about a user's interests based on the sites and products they visit and applications they use and then target their campaigns according to these interests, providing an improved experience for both users and advertisers. At first glance, matching users with advertisements they like may sound like a simple problem, however the task of developing an efficient recommender system is extremely challenging. Training, optimizing, evaluating and deploying personalization solutions require specialized expertise in analytics, applied machine learning, software engineering, and systems operations to name a few.

In this paper we propose a compact banner recommendation framework that is appropriate for e-commerce SMSs. Our work focuses to small and medium sized e-commerce sites that, on the one hand have enough traffic for data analysis (0.1-10 million pageviews/month), but on the other hand, have limited processing and manpower resources, thus complex or resource inefficient solutions are not appropriate. Our focus lies especially on banners, sliders or fixed-position billboard graphics, rather than ads such as Google Ads. The main difference is that the available banners in an e-commerce store is limited and usually their position is fixed, whereas the number of available ads is enormous, thus near realtime decisions should be taken for matching thousands or millions of users with millions of advertisements. On the other hand, banner recommendations require matching thousands or in a case of a large e-commerce store, millions of users with a few dozen banners, where the main goal is to display the most interesting banners in the right order (in case of a slider) to users. Towards this end, we propose a banner recommendation framework that clusters products based on their textual representation and user's session-based information like clicks and purchases. The result of this process is used for training a neural network that optimally matches available banners with users. In addition, we propose four new evaluation metrics, to act as key performance indicators (KPIs), as traditional classification and ranking metrics cannot fully describe the effectiveness of banner recommendation methods for SMEs.

The remainder of this paper is structured as follows: Related work on personalization and banner recommendation is discussed in Section 2. Section 3 introduces four KPIs for evaluation in case of banner recommendations, while Section 4 discusses in detail the proposed framework for banner recommendations in e-commerce and evaluation takes place in Section 5. Finally, Section 6 summarizes work done, discusses future work and concludes the paper.

Related Work

A profusion of papers has been written laying down the fundamental principles of web personalization and surveying the most popular approaches in an effort to define a taxonomy of existing approaches in the field of e-commerce. In [START_REF] Salonen | Web personalization: The state of the art and future avenues for research and practice[END_REF], Salonen and Karjaluoto discuss areas of interest, research gaps and future directions for web personalization. Their work includes a literature review of the top 20 marketing and information systems journals published during the period of 2005-2015 that shows active research output and the domination of information systems publications. A number of studies have shown that web personalization is well worth the investment in capital and work hours, as it has been observed that website personalization can lead to increased user satisfactions, increased revenue and customer loyalty [START_REF] Senecal | The influence of online product recommendations on consumers' online choices[END_REF]. Other surveys [START_REF]Trends in personalization[END_REF] have indicated that web personalization is a major priority for organizations with an online presence.

Personalization naturally starts with collecting information about the individuals one wishes to reach. This information can be explicit or implicit. Explicit information is what a user offers directly and includes ratings, answers to questionnaires, reviews, personal information etc. Implicit information refers to data that the website gathers based on a user's interactions with the website. This process is a discipline of Web Mining [START_REF] Kosala | Web mining research: A survey[END_REF] and includes monitoring, storing and processing a user's actions in order to reveal potentially useful underlying data (e.g. browsing and/or purchasing patterns). In this line of research there are many approaches in terms of the data that are collected, the ways by which that is done, and how the collected data may be used [START_REF] Pierrakos | Web usage mining as a tool for personalization: A survey[END_REF]. Nevertheless, this type of mining has become controversial in the last years, as it can be regarded intrusive in terms of the amount of user data collected with limited or without user consent. The lack of transparency raises concerns about privacy and security, thus recent regulations such as GDPR [START_REF] Datoo | Data in the post-gdpr world[END_REF] try to adjust the excessive use of personal data. Although various aspects of the legislation and their implementation remain uncertain [START_REF] Sirur | Are we there yet? understanding the challenges faced in complying with the general data protection regulation (GDPR)[END_REF], the fact remains that various practices mentioned in previous sources might have to be revised to allow for user consent, or even be rejected altogether as non-compliant with the new regulatory frameworks.

As far as the problem of personalized recommendations is concerned, the main objective is to use available data to create recommendations that promote different content to every individual, according to his or her distinct interests. Several papers have been written that analyze and survey recommender systems in the field of web personalization [START_REF] Bobadilla | Recommender systems survey[END_REF]. Furthermore, various approaches have been proposed in the context of e-commerce, such as statistical approaches [START_REF] Qudah | Personalized e-advertisement and experience: Recommending user targeted ads[END_REF] and machine learning frameworks. Algorithms such as Collaborative Filtering [START_REF] Wang | Research on personalized recommendation based on web usage mining using collaborative filtering technique[END_REF], Deep Learning Neural Networks [START_REF] Hidasi | Recurrent neural networks with top-k gains for sessionbased recommendations[END_REF] and SVM models [START_REF] Lin | A recommender for targeted advertisement of unsought products in e-commerce[END_REF] have been widely used in personalized content recommendation systems. Although most of these methods have shown promising results, other methods have focused on the cold-start problem, that is the case where no prior knowledge exists (e.g. the first visit of a new customer). In this case association rules [START_REF] Osadchiy | Recommender system based on pairwise association rules[END_REF] have been used with satisfactory results. Dealing with infrequent items is also another problem that requires special treatment. These items usually are treating as outliers and excluded in the preprocessing phase [START_REF] Lin | A recommender for targeted advertisement of unsought products in e-commerce[END_REF]. Another interesting problem in the field are Top-N recommenders, which aim to produce N ordered recommendations, rather than a single one. Top-N recommender algorithms sometimes are considered a distinct problem due to sometimes increased computational load required, as well as differences in the ways they are evaluated [START_REF] Hu | A user similarity-based top-n recommendation approach for mobile in-application advertising[END_REF].

On the other hand, recommending advertisements has attracted increased attention during the past years. Yuan and Tsao [START_REF] Yuan | A recommendation mechanism for contextualized mobile advertising[END_REF] proposed a personalized contextualized mobile advertising infrastructure for the advertisement of commercial and non-commercial activities that minimize users' inputs by using implicit browsing behaviors and recommends Top-N scored advertisements using a two-level Neural Network. In a different approach, Wang et al. [START_REF] Wang | Interactive ads recommendation with contextual search on product topic space[END_REF] propose an interactive service recommendation based on contextual search by building an ad domain-based concept hierarchy to make the most of the product details over the e-commerce sites. In [START_REF] Anastasakos | A collaborative filtering approach to ad recommendation using the query-ad click graph[END_REF] Anastasakos et al. explore search engine logs to determine the relevance of an ad document for a search query by using a graph with several million edges. Last but not least, Papadopoulos et al. [START_REF] Papadopoulos | Lexical graphs for improved contextual ad recommendation[END_REF] study the problem of recommending a small set of ads to a user based solely on the currently viewed web page and propose the use of lexical graphs created from web corpora as a means of computing improved content similarity metrics between ads and web pages.

Obviously, a lot of progress has been made in personalization and recommendation systems; however, most of the existing solutions focus on product or ads recommendation. In our case, we deal with the problem of e-commerce banner recommendation, especially focusing in small and medium e-commerce sites. In this case the pool of available recommendations is limited and available banner positions are fixed, while available data and resources are also limited. Our proposed solution is a Top-N recommendation framework for selecting the most appropriate banners in e-commerce. Advancing the state-of-the-art we propose an integrated solution that combines topic analysis and neural networks, a combination that not only achieves better results, but is also more adaptable to data changes.

Proposed Evaluation Metrics

To measure the effectiveness of recommender systems and compare different approaches, various metrics have been applied such as Classification Accuracy, Logarithmic Loss, Confusion Matrix, Area under Curve, Recall, F1 Score, Mean Absolute Error and Mean Squared Error [START_REF] Tsoumakas | Multi-label classification: An overview[END_REF]. Nevertheless, our problem presents some differences from typical classification or ranking problems, as in our case there are difficulties in separating good and bad recommendations, due to the fact that available classes and/or banners for recommendation may be limited and may not match the user's interests. Thereafter, in our case we may have to recommended the best of a few bad choices. For this reason, we propose four new metrics to act as KPIs (Key Performance Indicators) in our problem: a) Recall-TopN , b) Recall-Purchases, c) Min-1 and d) Pos-Error. We argue that these new metrics are more suitable for evaluating the performance of banner recommendations systems and we believe can improve the evaluation procedure. a) Recall-TopN In the field of Information Retrieval, Recall (also known as sensitivity) is the fraction of relevant instances that have been retrieved over the total amount of relevant instances. We propose a variation of the Recall metric that we call Recall-TopN (Equation 1), where N is the number of recommendations, S the total number of sessions, P i the number of categories that the system predicted correctly (true positives) for session i and C i the number of categories the user showed interest for (relevant elements).

Recall -T opN = 1 S * S i=1 P i max(C i , N ) (1)
This adjustment is necessary, as even if the user is interested in multiple categories, there will be only N recommendations regardless of the number of relevant items. Traditionally, recall would penalize this behavior as in our case the number of true positives cannot never exceed N . b) Recall-Purchases Next, we propose Recall-Purchases (Equation 2), a metric that intends to evaluate the percentage of recommendations that potentially can lead to actual conversions. In Equation 2, M is the number of sessions that lead to a purchase, B i , is the number of categories of which products were purchased for session i, and P i is the number of categories recommended. Recall-Purchases may be more important than Recall-TopN , as conversions is the definite target in e-commerce.

Recall -P urchases = 1 M * M i=1 P i max(B i , N ) (2)
c) Min-1 Another KPI (Key Performance Indicator) that is necessary in ecommerce is determining where a recommendation set is useful or completely irrelevant. Towards this end we define Min-1, which is the percentage of sessions where at least one of Top-N recommended categories was interesting for the user. While, not a particularly strict criterion, it is important in determining how many recommendation sets are even minimally useful.

d) Pos-Error Recommendation systems should not only provide relevant recommendations, but also rank them properly. Thus, we propose a metric we call Pos-Error that calculates the degree to which recommendations are not only relevant, but also optimally ranked. An intuitive description would be that Pos-Error increases when all banners belonging to user's top-N interests are optimally ranked. Pos-Error is defined in Algorithm 1, where S is the number of sessions, C is the number of categories, P is a N XC matrix with the predictions of the recommender regarding user interest per session per tag, and C is a N XC matrix with the actual user interested displayed in the corresponding sessions. According to Algorithm 1, Pos-Error increases as the distance between predicted and the ground truth positions increases. Pos-Error captures the fact that prediction mismatches about categories the user is more interested are more important than prediction mismatches for less preferred categories. Logarithmic values are used to smooth out results.

Algorithm 1 Pos-Error

Proposed Framework

In this Section we propose an integrated framework for banner recommendations as depicted in Figure 1. Our framework processes product textual information, user history and categories (classes) that users express interest for. Latent Dirichlet allocation (LDA) [START_REF] Blei | Latent dirichlet allocation[END_REF] is used employed for clustering products based on their textual description (name, description etc.). Then products clusters and user history data are processed in order to calculate user's session-based interest to specific categories. Finally, we use a neural network that processes the sessionbased interests and produces banner recommendations.

In every e-commerce system there are data that consist of user ids (customer ids or cookie ids in case of registered or unregistered visitors respectively), products, user pageviews, purchases and categories. Moreover, products are categorized based on brand, attributes or general interest, so by categories (classification classes) we mean the general user interests (brand, category or class). First, we apply LDA for extracting semantic information from products and cluster them into topic themes, based on the similarities of their textual descriptions. Topic modeling is based on the assumption that each document d i is described as a random mixture of topics and each topic as a focused multinomial distribution over terms. LDA builds a set of thematic topics from terms that tend to co-occur in a given set of documents. The result of the process is a set of N Θ topics, each expressed with a set of N W terms. The number of topics N Θ and the number of LDA discovers a mixture of topics P (θ|d) for each document d i , where each topic is described as a mixture of terms P (w|θ) following another probability distribution as given in Equation 3. The probability of the w i term describing a given document d is P (w i |d), where θ i is the latent topic, and P (w i |θ i=j ) is the probability of w i , within topic j. The probability of picking a term from topic j in a document is P (θ i = j|d).

P (w i ) = N θ j=1 P (w i |θ i=j )P (θ i = j|d) (3)
LDA estimates the topic-term distribution P (w|θ) and the document-topic distribution P (θ|d) from an unlabeled corpus of documents using Dirichlet priors for the distributions and a fixed number of topics. The Gibbs sampler [START_REF] Casella | Explaining the gibbs sampler[END_REF] iterates multiple times over each term w i in document d i and samples a new topic j.

P (θ i=j |w i , d i , θ -i ) ∝ C W θ Wij + β w C W θ W j + W β x C Dθ dij + α θ C Dθ diθ + θα (4)
The Gibbs sampler sets the complexity of topic modeling to O(N Θ N I), where of N Θ is the number of topics, N the number of documents (movies) and I is the number of the sampler's iterations. The most common way to evaluate a probabilistic model is to measure the log-likelihood of a held-out test set, thus we use perplexity [START_REF] Blei | Latent dirichlet allocation[END_REF] for determining the optimal number of clusters, which is monotonically decreasing in the likelihood of the test data, and is algebraically equivalent to the inverse of the geometric mean per-word likelihood. A lower perplexity score indicates better generalization performance. More formally, for a test set of N documents, the perplexity is described in Equation 5.

perplexity = exp - N i=1 log(p(w i )) N i=1 d i (5)
After we assign each product to a topic cluster via LDA, we group user actions into sessions. We use an arbitrary time limit of T hours, which means that a session consists of actions of the same user, all of which happened within T hours of the previous one. For each session we count the instances a category was viewed. Thus, for each session a vector of length C is created, with each slot containing the number of times the respective category or product was viewed. In case of product views, we consider that products are assigned to one or more categories. Thus, a matrix V cat is created with dimensions (N, C), where N is the number of sessions examined and C is the number of categories. Following the same process, purchase statistics are calculated and matrix P cat is created (Algorithm 2). Having created matrices V cat and P cat for pageviews and purchases respectively, we repeat the process for views and purchases of products with regard to their assignments to LDA clusters. Each session is assigned two vectors of zeros, one for views and one for purchases, where each slot is related to an LDA group. For each view or purchase, the respective LDA vector is added to the total views and purchases of the accordingly . Thus, two more matrixes V lda and P lda are created according to Algorithm 3. Next, we normalize each matrix in order to contain values in the range [0,1] according to the relevant interest degree for each category in every session. After that, V cat and P cat are aggregated according to Equation 6 where α and β are weight factors as purchases are a stronger signal that product views. Then, matrices Scat and Slda are concatenated to form matrix S.

Algorithm 2 Calculate session-based Category interest

Algorithm 3 Calculate Category interest based on LDA clusters

F or each session i :

Scat i = α * V cat i + β * P cat i (6)
Having calculated session-based category interest for each user, we estimate user interests taking into account the entire user-history as the mean category interest for each sessions, which results to a matrix H that we use as input of the neural network for predicting the output matrix Scat. In other words, the proposed framework will predict user interests at session s using the available information of that user's actions before session s, as described by their historical data in array H.

Evaluation

In this Section we evaluate the proposed solution using a dataset coming from a live e-commerce store. Our evaluation dataset contains anonymous data of 4,292,495 unique clicks, 10,167 products, 83,467 unique customers and 146,803 product purchases. After some preprocessing, we grouped available data into sessions, where in our case each session consisted of actions of the same user for a period of T = 2 hours. We also clustered products into 50 topic-clusters using LDA after evaluating the optimal number of clusters using the perplexity metric. In our case we found out that 13 out of the available 68 categories (classes) were too generic, covering more than 80% of the products, so we treated these 13 categories as outliers and removed them, the number of products remained unchanged. Then, we performed a five-fold cross validation evaluation test for determining the optimal hyper-parameters of our neural network. Our neural network, built with Python and Tensorflow, used the Relu activator and neuron weights initialized with the Glorot initialization function [START_REF] Glorot | Understanding the difficulty of training deep feedforward neural networks[END_REF]. We tested hyperparameter values in order to find the optimal combination using various combinations of the following hyperparameter values:

-Learning Rate = {0.1, 0.01, 0.001, 0.0001, 0.00001, 0.000001} -Layers = {2, 3, 4, 5, 6, 10} -Neurons per Layer = {236, 354, 472, 590, 708} -Regularization Factor = {0.1, 0.01, 0.001} -Loss Function = {Mean Squared Error, Categorical Cross Entropy} -Optimizer = {Stochastic Gradient Descent, Adam} -Batch Size = {64, 32, 16} A sample of our experiment set is available in Table 1, the duration of each ANN training run was between 90 and 120 minutes, depending on the learning rate, number of layers and neurons per layer, on an Intel i7 6700K computer with a GeForce GTX 970. The following hyperparameters: Learning Rate=0.0001, Layers=3, Neurons=590, Loss Function=Categorical Cross entropy, Optimizer=Adam, Batch Size=32 and Regularization Factor=0.1 resulted in Recall Top-N = 0.333, which was the best result in our tests, thus we used these values in the next step. Next, we evaluated our proposed framework against four approaches. First, we wanted to test more machine learning approaches, so we replaced the neural network in the processing step with a random forest (with 100 estimators and a maximum depth of 10), as well as k-nearest neighbors (KNN) [START_REF] Dudani | The distance-weighted k-nearest-neighbor rule[END_REF] algorithm. Finally, we evaluated our approach against two baseline solutions, we set N = 5 most popular categories and then randomly selected N = 5 categories. According to the results of our tests which are depicted in Table 2, our approach achieves higher scores in all four evaluation metrics, up to 17.45% in case of random forests and up to 77.36% in case of randomly showing banners, which is the case for the majority of existing e-commerce sites.

Conclusion

In this paper, we introduced a compact integrated system for personalized banner recommendations that is specially targeted to e-commerce stores. We proposed a framework that employs latent dirichlet allocation and neural networks for processing user history and product's textual information in order to produce and rank recommendations from a limited pool of available banners that can be displayed in specific banner positions of an e-commerce store. We evaluated the proposed approach on a dataset coming from an active e-commerce store against other approaches and showed that our solution can provided up to 17.45% better results than random forest methods and improve up 77.36% than baseline solutions, which is the case for most small and medium e-commerce stores. Our future work includes further experimentation on discovering the optimal parameters for LDA and our neural network. We also plan to evaluate our approach against more recommendation algorithms, as well as test the proposed solution live in an e-commerce store via A/B testing.

  S do Ps = argsort ( P[i,] ) Cs = argsort ( C[i,] ) For j=1 to N do p = arg ( Ps== Cs[j] ) if j > p do Append to error log(P (c,s) -R (c,s) )/log(R (C,s) ) Pos-Error = [mean(Error)] -1

Fig. 1 .

 1 Fig. 1. Proposed Framework for Banner Recommendations

For

  i=1 to Number of Sessions do V = Category Pageviews related to session i P = Category Purchases related to session i For j=1 to C do Vcat [i,j] = Number of V entries related to category j Pcat [i,j] = Number of P entries related to category j

For

  i=1 to Number of Sessions do Pv = Product Pageviews related to session i Pb = Product Purchases related to session i For j=1 to Sizeof Pv do Lda_var = LDA memberships for product Pv [j] Vlda [i] += Lda_var For j=1 to Sizeof Pb do Lda_var = LDA memberships for product Pb [j] Plda [i] += Lda_var

Table 1 .

 1 Evaluation of various hyperparameters for our neural network.

	Learning Rate	Layers	Neurons per Layer	Regularization Factor	Loss Function	Optimizer	Batch Size	Recall Top-N
	0.100000 2	236	0.100	CCE	SGD	32	0.3179
	0.100000 3	354	0.010	CCE	SGD	16	0.3097
	0.100000 4	472	0.100	MSE	Adam	32	0.0665
	0.010000 6	708	0.100	CCE	Adam	32	0.2849
	0.010000 6	708	0.001	CCE	Adam	16	0.2377
	0.001000 2	236	0.001	CCE	SGD	32	0.2908
	0.001000 2	354	0.001	MSE	Adam	16	0.3118
	0.000100 4	472	0.100	CCE	Adam	32	0.3290
	0.000010 3	354	0.100	MSE	Adam	32	0.2876
	0.000001 3	354	0.100	CCE	Adam	32	0.2840

Table 2 .

 2 Evaluation of various hyperparameters for our neural network. TopN 0.3803 0.3640 -4.29% 0.3153 -17.08% 0.2806 -26.21% 0.1016 -73.28% Recall-Purch. 0.4597 0.3795 -17.45% 0.3474 -24.44% 0.2417 -47.42% 0.1041 -77.36% Min-1 0.5284 0.5205 -1.48% 0.4756 -9.99% 0.4441 -15.95% 0.18386 -65.21% Pos-Error 0.5391 0.5326 -1.20% 0.4959 -8.01% 0.4875 -9.57% 0.4022 -25.39%

		NN	Ran. Forest	KNN	Popular	Random
	Metric	Value Value % Diff. Value % Diff. Value % Diff. Value	% Diff.
	Recall-

Acknowledgements

This work was partially funded by an IKY scholarship funded by the "Strengthening of Post-Academic Researchers" Act from the resources of the OP "Human Resources Development, Education and Lifelong Learning" with Priority Axes 6,8,9 and co-funded by the European Social Fund ECB and the Greek government.


Suvra Jyoti Choudhury

Nikhil R Pal

Classification of incomplete data using autoencoder and evidential reasoning

Keywords: Belief functions, Classification, Evidential reasoning, Fuzzyc-means, Latent space representation, Missing Data, Neural Network

To classify data with missing values, we propose a method exploiting autoencoders and evidence theory. We augment the complete data by deleting each feature once and imputing it using the nearest neighbor to a set of predefined points generated using a new scheme. We train an autoencoder with the complete data set to get a latent space representation of the input. The network is retrained with the augmented data to get a better latent space representation. Now for each class, we train a support vector machine (SVM) with a one-vs-all strategy using the latent space representation of the complete data set. For an r-class problem, the output of each of the r SVMs is used to define a Basic Probability Assignment (BPA). The BPAs are combined using Dempster's rule of combination to make the final decision. Now to classify any test instance with missing values, we make an initial guess of the missing values using the nearest neighbor rule. We take the latent space representation of that imputed instance and pass it through each trained SVM. As done earlier, using each SVM output, we generate a BPA and the r BPAs are aggregated to get a composite BPA. The class label of the test point is then determined using the Pignistic probabilities. We have compared the proposed method with four state-of-the-art techniques using three experiments with artificial and real datasets. The proposed method is found to perform better.

Introduction

Missing data is a common problem for machine learning and data mining. Let, x k be the k th data point or datum with p features, x k ∈ X ⊆ R p , where X is the data set. So, if x k for some k has q ∈ {1, 2, • • • , p} missing values, then X is called an incomplete dataset. Many real life systems [START_REF] Dicesare | Imputation, estimation and missing data in finance[END_REF][START_REF] Jerez | Missing data imputation in breast cancer prognosis[END_REF][START_REF] Le Gruenwald | Estimating missing values in related sensor data streams[END_REF][START_REF] Liu | An analysis of missing data treatment methods and their application to health care dataset[END_REF][START_REF] Mohammed | An ensemble technique to handle missing data from sensors[END_REF] are affected due to missing data [START_REF] García-Laencina | Pattern classification with missing data: a review[END_REF]. Missing data are typically characterized into three types [START_REF] Little | Statistical analysis with missing data[END_REF]: (1) MCAR (missing completely at random), (2) MAR (missing at random) and (3) NMAR (not missing at random). Most missing value prediction methods are for MCAR and MAR types of missing data.

The simplest way to deal with MCAR and MAR type of missing data is to analyze [START_REF] Little | Statistical analysis with missing data[END_REF][START_REF] Schafer | Analysis of incomplete multivariate data[END_REF] the data points without any missing value. Here, each data point with a missing value(s) is deleted from the datasets and the rest are analyzed. This procedure, however, is effective only when a small number of instances have missing values.

The second family of methods for handling missing data first predicts (imputes) missing values, and then, analyses the entire data. In [START_REF] García-Laencina | Pattern classification with missing data: a review[END_REF] authors categorized imputation techniques into two groups: statistical imputation methods and machine learning based imputation methods. In statistical imputation methods, the missing values are replaced by usual statistical techniques [START_REF] Allison | Missing data: Sage university papers series on quantitative applications in the social sciences (07-136[END_REF][START_REF] Little | Statistical analysis with missing data[END_REF][START_REF] Schafer | Analysis of incomplete multivariate data[END_REF]. For example, the missing value of a particular feature can be replaced by the average of the features of the data points without any missing value (mean imputation). Sometimes, missing values are predicted by a regression model. If k features have missing values, then we need k-regression models. Cold and hot deck imputation [START_REF] Kalton | Compensating for missing survey data[END_REF] is another type of statistical technique where a missing value is imputed using the feature value of the closest complete data point; which is determined based on the existing features from the same (sometimes from different) data sources. In multiple imputations, a missing value is replaced by a set of possible values. Thus, the missing values are imputed multiple times and multiple datasets are created. Then, these imputed datasets are analyzed by using standard procedures and the results are combined for imputing missing values.

Machine learning based procedures are also used to impute missing data. As an example, k-nearest neighbor (k-NN) [START_REF] Dixon | Pattern recognition with partly missing data[END_REF] is a common procedure where the missing value is replaced by the corresponding value of the nearest neighbor (k-NNI). Here, distances are computed using the observed subspace. In [START_REF] Morin | A reappraisal of distance-weighted k-nearest neighbor classification for pattern recognition with missing data[END_REF], the k-NN rule is modified where the distance-weighted k-nearest neighbor rule is used to classify data with missing values. In singular value decomposition imputation (SVDI) [START_REF] Dixon | Pattern recognition with partly missing data[END_REF] missing values are imputed using the k-most significant eigenvectors. Missing values are also imputed using some other machine learning techniques like self-organizing maps (SOMs), and multilayer perceptron (MLP) [START_REF] Fessant | Self-organising map for data imputation and correction in surveys[END_REF][START_REF] Gautam | Counter propagation auto-associative neural network based data imputation[END_REF][START_REF] Gautam | Data imputation via evolutionary computation, clustering and a neural network[END_REF][START_REF] Nowicki | Rough neuro-fuzzy structures for classification with missing data[END_REF][START_REF] Samad | Self-organization with partial data[END_REF][START_REF] Silva-Ramírez | Single imputation with multilayer perceptron and multiple imputation combining multilayer perceptron and k-nearest neighbours for monotone patterns[END_REF][START_REF] Silva-Ramírez | Missing value imputation on missing completely at random data using multilayer perceptrons[END_REF][START_REF] Westin | Missing data and the preprocessing perceptron[END_REF].

Evidential reasoning is an effective approach to dealing with different types of uncertainty. It has been used in many areas including classification, clustering, and decision-making. Recently, in [START_REF] Liu | A new incomplete pattern classification method based on evidential reasoning[END_REF] evidential reasoning has been used to classify incomplete data. Here, first, for each class, a prototype is formed. Then the incomplete data are imputed using all prototypes. So, if r is the total number of classes, for an incomplete data r number of complete data points are generated. Now, each new data points is classified using a classifier. Then the results of the classification are fused based on a new prototype-based credal classification (PCC) method to find the right class label for the incomplete data point. After imputing missing values, in many cases, a test data point may provide evidence to belong to more than one class. Considering this, in [START_REF] Liu | A new incomplete pattern classification method based on evidential reasoning[END_REF], the authors defined two types of errors. One is miss-classification error and the other one is belongingness of a test point to more than one class, which includes the actual class the point belongs to.

In this article, we propose an evidential reasoning-based classification technique to classify the MCAR type of missing data. For this, first, an autoencoder is trained using the complete data set and then by an augmented complete data set. Now, if there are the r classes, r classifiers (as SVM is a good classifier for classification we use r SVMs here) are trained using the latent space representation of the complete data. When a test point with missing values appears, we first impute it using our proposed method. Then, we use the latent space representation of the test data point and classify it using the r trained classifiers. Thus, from each of the r classifiers, we get a probabilistic output for each test point. We take these probabilistic outputs and combine them using the proposed evidential framework. We compute classification errors as in [START_REF] Liu | A new incomplete pattern classification method based on evidential reasoning[END_REF]. We have done three experiments to check the performance of our algorithm. To check the efficiency of our algorithm with respect to others, we compared the results of the proposed algorithm with four state-of-the-art techniques. Our results have revealed that the performance of the proposed method is better compared to other methods in most of the cases.

The main contributions of the proposed method are three folds. First, the traditional 1-nearest-neighbor for imputing missing data is modified here. Then, the entire dataset is projected into a suitable latent space. Moreover, we have proposed a new mass function to join r probabilistic outputs from r SVMs.

The remaining part of the article is organized as follows. Basic evidential reasoning is described in Section 2. Section 3 describes the proposed method. Experimental results and analysis are demonstrated in Section 4. Section 5 concludes the paper.

Basics of evidential reasoning

Consider an r class classification problem where any input x ∈ R p belongs to one of the r classes. Let, Ω be the set of classes; Ω = {ω 1 , ω 2 , • • • , ω r }. Due to imprecision or some other uncertainty asociated with the input, the available evidence may suggest a data point to belong to more than one class. So, a test point may belong to one of the 2 Ω sets of classes. For example, let there be three classes. They are Ω = {ω 1 , ω 2 , ω 3 }. Now, a test point may belong to any one of 2 Ω possibilities:

2 Ω = {∅, {ω 1 }, {ω 2 }, {ω 3 }, {ω 1 , ω 2 }, {ω 1 , ω 3 }, {ω 2 , ω 3 }, {ω 1 , ω 2 , ω 3 }}.
Thus, a test point may belong to meta-classes or in no class.

In evidential reasoning basic belief assignment (BBA) is a function m(•) : 2 Ω → [0, 1] satisfying two properties: A∈2 Ω m(A) = 1 and m(∅) = 0. Belief function Bel(•) and plausibility function P l(•) are the lower and upper bounds of imprecise probability associated with BBAs ∀A ∈ 2 Ω and are defined as,

Bel(A) = B⊆A m(B); P l(A) = B∩A =∅ m(B). (1)
Bel(•) and P l(•) may be used for decision-making when it is necessary. Dempster [START_REF] Shafer | A mathematical theory of evidence[END_REF] proposed a rule to combine multiple evidences represented by BBAs. This is usually known as Dempster-Shafer (DS) rule and denoted by the ⊕ symbol. Let, m 1 (•) and m 2 (•) be two BBAs over 2 Ω then the combined basic probability analysis(BPA) m = m 1 ⊕ m 2 is defined by DS rule as follows:

m(A) = [m 1 ⊕ m 2 ](A) = B∩C=A m1(B)m2(C) 1-B∩C=∅ m1(B)m2(C) (2)
The determinator of ( 2) is used here for normalization, whereas,

B∩C=∅ m 1 (B)m 2 (C)
assesses the total conflicting belief mass. This combination rule does not produce intuitively desirable results in high conflicting cases. To overcome this, later many other combinational rules have been introduced [START_REF] Sentz | Combination of evidence in Dempster-Shafer theory[END_REF] which we do not consider for our investigation.

Proposed algorithm

Here, we use an autoencoder for feature extraction. First, we use the original and the modified data sets (which is described later) to train the autoencoder. Then, we use the extracted features from the autoencoder to train class-wise (one verses all) SVMs. We use the trained class-wise SVMs to obtain the probabilistic outputs for a test point. With the obtained probabilistic outputs we construct mass functions for the test point. Using the mass functions, we find the class label of the particular test point. Below, we discuss the steps with further details.

The architecture of the autoencoder

We consider linear nodes in the input layer, which is described as follows:

S (x ki ) = x ki ; i = 1, 2, • • • , p; (3)
S (x k0 ) = 1; ∀k. (4)
Here, S(•) denotes the activation function of a node; and x k and p are as defined earlier. We consider a single hidden layer with sigmoidal nodes as follows:

z kh = p i=0 w I ih S (x ki ) ; h = 1, 2, • • • , q; (5)
z kh = S (z kh ) = 1 1 + e -z kh ; h = 1, 2, • • • , q; (6)
S (z k0 ) = 1, ∀k. (7)
Here, for x k , z kh is the net input to the h th hidden node and S (z kh ) is the output from the h th hidden node. Moreover, w I ih is the weight connecting the i th input node to the h th hidden node and w I 0h , ∀h, is a bias. We consider an output layer with sigmoidal nodes as follows:

y kj = q h=0 w H hj z kh ; j = 1, 2, • • • , p; (8)
S (y kj ) = 1 1 + e -y kj ; j = 1, 2, • • • , p. (9)
Here, for x k , y kj is the net input to the j th output node and S (y kj ) is the output from the j th output node. Furthermore, w H hj is the weight connecting the h th hidden node to the j th output node and w H 0j , ∀j, is a bias. The system error for the k th training pattern is as follows:

E k = 1 2 p j=1 (x kj -S (y kj )) 2 . ( 10
)

The learning

Since we are dealing with a classification problem, for every x ∈ R p , there is an associated class label l ∈ {1, 2, • • • , r}.

Let X T R be the training data with n instances, which does not have any missing value. In X T R there are data points from all r classes; X T R = ∪ r i=1 Xi , where Xi = {x|x ∈ X T R and x belongs to the i th class}. Now we find the i th class center v i as

v i = 1 | Xi| x∈ Xi x. (11)
In this way, we produce r class centers

V = { v 1 , v 2 , • • • , v r } ; v i ∈ R p .
We also cluster each Xi ; i = 1, 2, • • • , r; into n c clusters using the k-means algorithm. In this way, we produce (n c ×r)

cluster centers V = v1 , v2 , • • • , v(nc×r) ; vi ∈ R p .
Then, by combing V and V , we obtain V = V ∪ V . In this way, we produce (r+n c ×r)

cluster centers V = v 1 , v 2 , • • • , v (r+nc×r) ; v i ∈ R p . Now from X T R we generate p modified data sets X k , k ∈ {1, 2, • • • , p}, as follows. To generate X k , for x ∈ X T R , we replace x k by v lk if l = argmin k ||x -v k || 2 * .
Here, we assume that the k th feature is missing. We imputed the missing value by the k th feature value of the centroid which is closest to x in terms of the distance measure ||.|| * . Here, ||.|| * is computed using all but the k th feature. Now, we train an autoencoder using X T R for N 1 epoches. Next, we retrain the same network for N 2 epoches with the data set

X T otal = X T R ∪ {X 1 ∪ X 2 ∪ • • • ∪ X p }.
For any x ∈ X T R as well as any x ∈ X k , the target vector is taken as x ∈ X T R . Note that the training of the auto encoder does not use the class labels. We explain this method of training in Algorithm 1.

After training the autoencoder, we pass [START_REF] García-Laencina | Pattern classification with missing data: a review[END_REF]. It is indeed the output from the hidden layer of the trained autoencoder. Thus, we obtain the latent space representation of the entire training data set X T R as

x k ∈ X T R , k ∈ {1, 2, • • • , n} to find the latent space representation z k = ( z k1 , z k2 , • • • , z kq ) T of x k using
Z = { z 1 , z 2 , • • • , z n }.
We use Z to train r number of SVMs using the one-versesall strategy.

Decision making for a test point

Let the set of test points be X T E . For each test data point

x i ∈ X T E , i ∈ {1, 2, • • • , N }; N = |X T E | atmost (p -1)
features may be missing. We impute the missing values of x i using v l , (l = 1, 2, • • • , (r + n c × r)) as follows. The k th missing value of x i , x ik , is imputed by

v lk if l = argmin j ||x i -v j || 2 * .
Here 2: for i=1 to r do 3:

Set Xi = {x|x ∈ X T R and x belongs to the i th class}.

4:

Set vi = 1 | Xi | x∈ Xi
x.

5:

V = V ∪ vi.

6:

Using k-means clustering algorithm cluster Xi into nc clusters and generate nc new cluster centers Vi = {vi1, vi2,

• • • , vinc } ; vi ∈ R p .
7:

V = V ∪ Vi.
8: end for 9: Set V = V ∪ V . 10: for k=1 to p do 11:

To generate X k for every x ∈ X T R , replace

x k by v lk if l = argmin k ||x -v k || 2 *
, where ||.|| * is computed using all but the k th feature.

12: end for 13: Train an autoencoder using X T R for N1 epoches. 14: Retrain the same network for N2 epoches with the data set

X T otal = X T R ∪{X 1 ∪X 2 ∪• • •∪X p }.
For any x ∈ X T R and its corresponding x k ∈ X k , the target vector is x ∈ X T R . END ||.|| * is computed using all but the missing feature values of x i . We pass x i with the imputed values through the trained autoencoder and take the output of the hidden layer, z i = ( z i1 , z i2 , • • • , z iq ) T as the latent space representation using (6). Then we use z i in the trained r SVMs. Let, the probabilistic outputs [START_REF] Platt | Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods[END_REF] from the k th SVM for the k th class and the remaining (r -1) classes be P 1 ik and P 0 ik , respectively. Then, we define the k th BPA as follows: m k ({k}) = P 1 ik and m k ({Ω -k}) = P 0 ik ; k = 1, 2, • • • , r. We now use Dempsters rule [START_REF] Shafer | A mathematical theory of evidence[END_REF] to combine these r BPAs as discussed in Section 2 to obtain the composit BPA m(•).

Now for class k, we compute the Pignistic probability [START_REF] Cobb | A comparison of methods for transforming belief function models to probability models[END_REF] as follows:

P m,x {k} = A⊆Ω,k∈A m(A)/|A| (12)
Thus, we have a set of Pignistic probabilities

P = {P m,x {1}, P m,x {2}, • • • , P m,x {r}}. Let, l = argmax i {P m,x {i}; ∀i = 1, 2, • • • , r} and d = argmax i {P m,x {i}; ∀i = 1, 2, • • • , r; i = l}. Now, if (P m,
x {l} -P m,x {d}) > , we decide that x belongs to the class l. Otherwise, we say that x belongs to both the classes l and d. Here, is a user defined threshold.

Experiments

As in [START_REF] Liu | A new incomplete pattern classification method based on evidential reasoning[END_REF], to test the effectiveness of the proposed method, we divide our experiments into three parts and compare our method with four methods. For this comparison, we use miss-classification error as used in [START_REF] Liu | A new incomplete pattern classification method based on evidential reasoning[END_REF] and the results provided in [START_REF] Liu | A new incomplete pattern classification method based on evidential reasoning[END_REF].

Experimental set up

Based on a few trial experiments, for all datasets, we use the following architecture of the autoencoder: (p) -(10 × p) -(p), where p is the number of features in the dataset. We consider the learning rate η = 0.9 and the number of clusters in each class n c = (r × 5). Based on a few trials and errors experiments for all datasets, we choose N 1 = N 2 = 10000. We repeat the process 10 times with 10 different weight initializations and report the average results. We compare the proposed method with four algorithms and with two classifiers: prototypebased credal classification (PCC) with evidential k-nearest neighbors (EK-NN), PCC with evidential neural network (ENN), k-nn imputation (KNNI) method with EK-NN, KNNI method with ENN, FCM imputation (FCMI) with EK-NN, FCMI with ENN, mean imputation (MI) with EK-NN and MI with ENN. The detailed description of these methods can be found in [START_REF] Liu | A new incomplete pattern classification method based on evidential reasoning[END_REF].

Experiment 1

Same as experiment-1 in [START_REF] Liu | A new incomplete pattern classification method based on evidential reasoning[END_REF] we consider a three-class data set for experiment-1. Each class contains 305 training and 305 test samples from inside a circular disk. The radius of each circle is 3 units, and the centers of three circles are c 1 = (3, 3) T , c 2 = (13, 3) T and c 3 = (8, 8) T . As in [START_REF] Liu | A new incomplete pattern classification method based on evidential reasoning[END_REF] the values in the second dimension corresponding to y-coordinate of test samples are all missing. Thus there is only one known value, i.e., the first dimension corresponding to the xcoordinate for each test sample. As in [START_REF] Liu | A new incomplete pattern classification method based on evidential reasoning[END_REF] we use different meta-class selection thresholds = 0.30 and = 0.45 to show their influence on the results. Using Fig. 1 we also show the classification results of our method with = 0.45. In Table 1 we report the results with = 0.30 and = 0.45 for our method and PCC. These results show that we obtain the best results by our method and PCC with = 0.45. These experiments establish the importance of choosing the threshold. It also shows the superior performance of the proposed method compared to FCMI with EK-NN, KNNI with EK-NN, and MI with EK-NN.

Experiment 2

In this experiment, we use a three-dimensional synthetic dataset generated using three four-dimensional Gaussian distributions with the following charac- 2 shows the results of different methods. For the proposed method, we use = 0.30. With this above process, we generate ten datasets for each of the six cases and repeat the learning process ten times for each of them. We report the average misclassification accuracies in Table 2. Table 2 depicts that the proposed method performs better than other methods.

Experiment 3

Following experiment-4 in [START_REF] Liu | A new incomplete pattern classification method based on evidential reasoning[END_REF], in this experiment, we use the same four real data sets which are summarized in Table 3. Moreover, following [START_REF] Liu | A new incomplete pattern classification method based on evidential reasoning[END_REF], here we perform two-fold cross-validation and consider the same number of missing values for different datasets. The last column of Table 3 lists the considered number of missing values. Similar to Experiment-2, for the proposed method, we use = 0.30. We repeat the experiment ten times and report the obtained average classification errors in Table 4. Table 4 reveals that our method performs the best in 10 out of 12 cases. The proposed method performs the worst on the Seed dataset when five and six values are missing. In these two cases, it ranks the third and the fifth among the nine competing algorithms.

Conclusion

Here, we have presented a new method using the evidential framework to deal with missing values for the classification problem. For a r class problem, we train r classifiers using the latent space representation of each training data.

To get the latent space representation first we train an autoencoder with the complete data. Then, we augment the complete data by deleting each feature once and imputing it using the nearest neighbor to a set of predefined points obtained using a clustering-based scheme. Then, we retrain the network using the modified dataset with a view to getting a better latent space representation. If a test point suffers from missing values we make an initial guess of the missing value using the nearest neighbor rule and take the latent space representation of that test point using the trained autoencoder. Then that representation is classified using all r trained classifiers. Each classifier gives some confidence that a given point belongs to the associated class. This confidence is then translated into a BPA. The BPAs are then aggregated using Dempster rule. Finally, the Pignistic probability is used to make the final decision. To check the performance of the proposed method we compare our method with four state-of-the-art techniques using three sets of experiments. From these experiments, we find that overall our method performs better than the compared methods. In the future, we intend to propose new methods to choose meta-class selection thresholds dy- namically. We also like to propose different methods to assign BPAs from the SVMs outputs.

Algorithm 1 : 1 :

 11 Training of the proposed method INPUT: Training data (X T R ), number of features (p), number of clusters in each class (nc), number of classes (r), number of epochs for the first training phase (N1), number of epochs for the second training phase (N2). BEGIN Set V = ∅, V = ∅.

Fig. 1 .

 1 Fig. 1. Miss-classification result of our method of three class data set

Table 1 .

 1 Miss-classification error (%) for different methods on the three class synthetic datasets associated with Experiment 1

	Method	= 0.30 = 0.45
	Our	1.75	0.87
	PCC (EK-NN)	1.75	0.87
	FCMI (EK-NN)	4.15
	KNNI (EK-NN)	4.15
	MI (EK-NN)	8.52
	Minimum	0.87

Table 2 .

 2 Miss-classification error (%) for different methods on the three class synthetic datasets associated with Experiment 2

		(100, 1) (100, 2) (100, 3) (200, 1) (200, 2)	(200, 3)
	Our	0.32 (±0.11)	3.30 (±0.74)	21.77 (±2.12)	0.44 (±0.10)	3.76 (±0.42)	20.95 (±1.58)
	PCC (EK-NN)	11.67	16.72	29.00	12.65	15.73	29.82
	PCC (ENN)	14.67	16.85	27.70	15.17	18.27	29.67
	FCMI (EK-NN) 18.17	24.27	40.06	18.81	24.90	39.59
	FCMI (ENN)	17.50	24.13	38.43	17.50	23.22	37.85
	KNNI (EK-NN) 18.28	24.57	41.00	18.83	25.00	40.86
	KNNI (ENN)	17.99	24.32	39.91	17.60	23.52	38.99
	MI (EK-NN)	19.24	25.94	41.85	19.62	28.06	41.34
	MI (ENN)	19.33	25.20	40.57	17.83	23.85	39.90
	Minimum	0.32	3.30	21.77	0.44	3.76	20.95
	We provide standard deviations for the proposed method within parenthsis

Table 3 .

 3 Data Sets Description

	Name Class # Attributes # Instances # Missing Values
	Breast	2	9	699	{3, 5, 7}
	Seeds	3	7	210	{3, 5, 6}
	Wine	3	13	178	{3, 6, 10}
	Yeast	3	8	1050	{1, 3, 5}

Table 4 .

 4 Misclassification error (%) considering different number of missing values for different methods on the four real-world datasets associated with Experiment 3 .26 2.99 7.07 13.70 18.64 4.86 11.67 23.43 1.91 4.66 23.48 PCC (EK-NN) 4.10 4.38 7.91 34.36 34.71 33.46 7.14 9.67 16.79 26.05 26.62 25.84 PCC (ENN) 3.81 3.81 6.88 32.67 34.19 32.29 9.05 9.52 16.19 26.97 27.53 27.53 FCMI (EK-NN) 3.95 5.07 13.00 38.54 45.95 51.11 12.46 20.08 21.75 30.15 32.12 32.30 FCMI (ENN) 3.81 5.27 11.42 36.19 41.33 46.00 13.33 20.00 20.95 26.97 32.02 31.46 KNNI (EK-NN) 6.10 8.15 14.35 38.13 44.29 50.95 9.68 12.54 25.87 26.59 25.84 30.90 KNNI (ENN) 3.95 5.76 11.54 36.70 40.90 49.22 11.19 12.14 25.71 26.97 28.09 31.18 MI (EK-NN) 4.71 8.20 38.33 37.59 45.08 51.16 21.03 33.49 40.71 30.71 34.93 39.23 MI (ENN) 4.25 6.44 14.64 37.71 42.10 49.33 21.43 31.43 39.52 29.78 33.71 37.64 Minimum 0.56 1.26 2.99 7.07 13.70 18.64 4.86 9.52 16.19 1.91 4.66 23.48 B-#: Breast-#; Y-#: Yeast-#; S-#: Seeds-#; W-#: Wine-#; #: No of missing features.

	DataSet	B-3 B-5 B-7 Y-1 Y-3 Y-5 S-3 S-5 S-6 W-3 W-6 W-10
	Our	0.56 1