An Experimental Evaluation on Utility Prediction of Integrated Child Development Services

Authors [5] proposed an ensemble approach for diagnosis of heart disorders. The data of 215 samples were collected and evaluated using the ensemble method and obtained 96 % of specificity and 95.9 % of sensitivity. Resul Das, et al. [6] developed an ensemble neural network model by combining predicted values and obtained the accuracy of 97.4 % using a heart disease dataset consisting of 215 instances. In paper [7] the author had proposed a model for SVM structured learning which deals with larger datasets. Nair et al. [8] discussed on stock market trend prediction system using a hybrid SVM approach. The performance of the system is compared with Naïve Bayes classifier [9] and neural network. Their proposed model achieved high prediction accuracy. Authors in the paper [10] proposed a classification model for predicting the employee performance. They adopted CRISP-DM classification model to predict the performance of 130 employees from various companies.

Ling Liu, Zijiang Yang [11] discussed a few different algorithms in data mining for the identification of fraudulent online transactions. They obtained data set from 2009 San Diego data mining contest consisting of 94682 instances. The results obtained from the data mining approaches such as Naive Bayes, Bagging, Naive Bayes Multinomial and Classification via Regression. These approaches cannot identify the effective fraud cases. They introduced LDA method to deal with the unbalanced data. LDA produces low accurate results than the other approaches. Rajinikanth TV et al. [12] had proposed a model with various data mining techniques to analyze the metrological data which is suited for Indian weather environments. 

The experiment was carried based on time series analysis during 1955 to 1965 with algorithms such as k-means is used for grouping the related data, J48 is used for classification and decision tree algorithm is used to predict the observations. Authors [13] developed a hybrid SVM model to analyse and predict the weather in Guntur district region. Authors [14] proposed a model to identify the unknown high dimensional distributions with SVM algorithm. In paper [15] the authors proposed an ensemble classification approach to detect stress from software employees. They collected the data from 918 software employees from various companies. They also adopted AdaBoost and Pegasos optimization algorithm to improve the classification performance and compared with different existing classifiers. Authors [16] proposed a novel ensemble method for heart disease analysis using majority voting. The result shows that Naïve Bayes classifier better than ensemble model achieved best combination with 92 % of accuracy. In paper [17] proposed a hybrid data mining model for predicting heart disease and achieved 82.54 % accuracy. Authors [18] proposed a novel approach for predicting heart disease failures using LSTM models. They used word embedding and one-hot encoding vectors to represent the patient diagnostic events. The proposed method is compared with AdaBoost, RF and LR models and achieved better classification accuracy.

Support Vector Machine (SVM is used for data classification draws an optimal hyperplane which works as a divider between two classes. This separator gives a maximum margin between two classes and also called as a maximum margin classifier. The larger the margin between the hyperplanes provides a good generalization for classification of data.

2.png

Figure 2. Data discrimination with support vectors

The margin corresponds the minimum distance between the data points that are closer to the points on the hyperplane. The following figure shows the optimal hyperplane. Hyperplane is expressed as

$wv^t X+b=0$     (1)

where $wv = {wv_1,wv_2,…,wv_n}$ are the weighted vectors. b is a scalar and $X = {x_1,x_2,…,x_n}$ are the attribute values. R* is the geometrical distance from X* to the optimal hyperplane. Kernel functions of SVM are used when the datasets are non-linearly separable. The various kinds of Kernel functions are explained is as follows;

Linear kernel: It is used for mapping unnecessary data to a higher dimensional space and it outperforms when the large numbers of features are compared to the size of the data. This Linear kernel is defined as

$K(x,x_i)=(1+x^T.x_i)$        (2)

Sigmoid Kernel: This kernel is commonly used in neural networks. This kernel is having “S” shaped curve and often refers to logistic function and it is defined as

$K(x,x_i)=tanh(kx^T.x_i-σ)$        (3)

Polynomial Kernel: This kernel is commonly used in Support Vector Machines that characterizes the likeness between trained instances in a feature space over original polynomial variables. This Kernel is defined as

$K(x,x_i)=(1+x.x_i^T)^p$        (4)

Radial Basis Kernel: This kernel is popular kernel used in various learning algorithms and also known as Gaussian kernel.

$K(x_i, x_j)= exp (-γ|x_i-x_j |^2)$       (5)

Normalized Polynomial Kernel: This kernel defines the standard polynomial kernel that is normalized in its feature space. This kernel function in SVM is defined as

$K(x_i,x_j)=(x_{i.T}.x_j+1)^P/sqrt(x_{i.T+1}+x_{j.T+1})$      (6)

Stochastic Gradient Descent (SGD): SGD is very simple and efficient to fit linear models and specifically used for very large samples. SGD is also called as incremental gradient descent (IGD) method which is an optimization method for minimizing an objective function. The objective function is formed as P(x), where x is the minimized parameter.

$P(x)= ∑_{i=1}^nP_i (x)$         (7)

$P_i$ is summand function with ith observation used to train the dataset. In some problems, sum-minimization problems arise empirical risk minimization. In such a case, $P_i (x)$ defines the loss function value at ith iteration and the empirical risk is denoted as P(x).

$x=x-δ∇P(x)=x-δ∑_{i=1}^n∇P_i (x)$        (8)

Pegasos is a stochastic gradient descent machine learning algorithm, works strongly for optimization in Support Vector Machines. SGD is a variant of primal methods used to solve SVM problems faster. For training the data, this algorithm depends on mini-batches with a batch size specified by user parameter k. This enables solver to differ between sub gradient projection and stochastic gradient descent. When k=1, SGD is augmented with a projection step. When k=n, number of examples simply defines the sub-gradient projection.  

Algorithmic Steps:

Initially choose k examples for training at every iteration.

With these k examples, update the weight of the vector by evaluating the objective function with its sub gradient.

Finally, the vector is projected onto a radius ball 1/√(λ) and holds the optimal solution.

When the objective of SVM is unconstrained, hinge loss function is used for replacing linear constraints. The solution accuracy is obtained with good projection step in {$O R^2/λ_ϵ$} iterations, where⋋ is the regularization parameter.

The following steps illustrate the algorithm for Pegasos.

Input data: X,λ, n,k,

Set v1 = 0

for t=1,2,…n

Choose $V_t⊆X$. Where$ |V_t |=k$.

Set $V_t^+={(i,j)∈V_t ∶j〈v_1,i〉<1}η=1/ϑ$

Set $v_{i+1/2}=(1-η_1λ) v_1+  η_t/k ∑_{(i,j)∈V_t^+}ij$

return vt+1

where n represents the number of iterations, k represents number of examples and on each iteration n, vt+1 is calculated by avoiding the examples from $V_t$ from set $V_t$ with size k.

Loss Functions: A loss function maps values of one or variables onto a real number that denotes cost associated with that value. The Optimization problem seeks to reduce the loss function. In SGD, there are various types of loss functions and is used to measure the degree of fitting.

$L*=min_{f∈μ_k } ||L||^2+∑_xl(j_x,L(i_x ))$          (9)

where l is the hinge loss function used by Pegasos in support vector machines.

Table 1. Various loss functions

In stochastic gradient descent methods, the general optimization problems are used in various algorithms for different purposes. Some of them are shown in the Table 1. SVM classifier with Hinge loss function works well since the margins are avoided. This hinge loss functions are suitable only for classification models but not for regression models. The hinge loss function is defined as

$min_v= γ/2||v||^2+1/n ∑_{(i,j)∈T}P(v;(i,j))$         (10)

$P(v;(i,j))=max\left\{ 0,1-j<v,i> \right\}$       (11)

The above equation with the pair (i, j) stands for the hinge loss. This hinge loss function in SVM is good in separating cases and also finds the largest margin between two instances in each class. Algorithm for proposed PEGASOS with Hinge loss function in support vector machines is as follows.

Input data: X,λ, n,k,ε

Randomly select v1 and show $||v^{(1)}||≤1/√(λ)$

for t=1,2,3,….,n do

Set $η_t=  1/λ^t$

Select $Vt⊆X, where | Vt| = k$

$ρ=  1/|X| ∑_{(i,j)∈V_t}(j-〈v_t,i〉),∀i$

$V_t^+={(i,j)∈V_t:j(〈v_t,i〉+ρ)<1},∀i$

$v_{t+1/2}=v_t-η_t (λv_t-1/k ∑_{(i,j)∈V_t^+}ij)$

${{v}_{t+1}}=min\left\{ 1,\frac{1/\sqrt{\lambda }}{\text{ }\!\!|\!\!\text{  }\!\!|\!\!\text{ }{{v}_{t+1/2}}\text{ }\!\!|\!\!\text{  }\!\!|\!\!\text{ }} \right\}{{v}_{t+1/2}}$

if $‖v_{t+1}-v_t ‖≤ε$

then

return $(v_{t+1},1/|X|  ∑_{(i,j)∈X}(j-〈v_t,i〉))$

end

end

return $v_{t+1},1/|X|  ∑_{(i,j)∈X}(j-〈v_t,i〉))$

In the above Algorithm, “for” loop is defined where projection steps and gradient are taken and “if” is taken as a condition that terminates the execution if there is a difference between two v vectors which are <∈. The whole dataset is denoted as X and n number of samples is selected randomly at every iteration for the computation of sub-gradient. The bias ρ is not a part of objective and it just returns convenient representation of decision function as

$j=sgn (〈v,i〉+ρ)$          (12)

The results of hinge loss within Pegasos algorithm is provided by starting the optimization point with new loss function. The sub-gradient of the objective is defined as follows

After refinement to new loss function, the above equation is represented as follows

$Δ_t= λv_t-1/|V_t|[∑_{(i,j)∈V_t^+}yx-∑_{(i,j)∈V_t^-}βij]$         (13)

where $Δ_t$ depends on the parameter β and $V_t^-$ is the subset of Vt where $j〈v,i〉>1$.

4.1 Ensemble boosted SVM approach

Ensemble approach in Machine learning selects a classifier from various algorithms and trains the algorithm with Sample training data. In this study, AdaBoost is another classifier used as classifier ensemble. This algorithm in machine learning has become one of the most powerful ensemble methods. The following Figure 3 depicts the architecture of SVM-Pegasos and AdaBoost ensemble. This ensemble approach of both SVM-Pegasos and AdaBoost optimizes the weight vector and mainly focuses on training samples which contain more valuable information that builds the classifier with good learning performance. The boosting method in AdaBoost algorithm improves the classifier learning accuracy by performing the random iterations. For each iteration, initially, all the uniform weights for all training samples are distributed and then adjusted for training samples when the classifier is completed. If there are any misclassified samples, then the weights are increased as the weights of classified samples are decreased. In such case, the weak classifier is forced to focus on all the hard samples in the training data.

${{W}_{i+1}}(x)=\frac{{{W}_{i}}(x)exp(-{{b}_{x}}{{a}_{i}}{{c}_{i}}({{a}_{x}}))}{{{N}_{i}}}$           (14)

where $a_x$ belongs to some sample space A with each label $b_x$ which is in a label set $B.W_i (x)$ denotes the new attribute which is added to new sample and $N_i$ represents the normalization constant. The above equation (2) denotes the weighted values with a parameter $α_i$ as a learning ability for hypothesis $c_i (a_x )$. The estimated function for all the training samples are computed when the parameter $α_i=(ln⁡[((1-F_i ))/F_i ])/2$, then the function can be as

$g(a)=∑_{i=1}^{i_{max}}α_i  c_i (a)$        (15)

where $i_{max}$ reduces the maximum error rate, when it is large it degrades the performance of the classifier and may lead to over fitting problems.

3.png

Figure 3. Architecture of the proposed ensemble approach

The proposed algorithm describes the ensemble approach by combining SVM-Pegasos with AdaBoost classifiers.

Input: $(a_1,b_1 ),…,(a_n,b_n)$

Initialize the weights of all training samples $W_1 (x)=1/l$

for  i=1,2,3,…,I{

Train SVM classifier on weighted distribution of training samples $W_d$;

Predict the samples with SVM-P learner:

$c_i=A→{-1,+1}$;

Update the weight of sample by computing $α_i$ using error rate;

${{W}_{i+1}}(x)=\frac{{{W}_{i}}(x)exp(-{{b}_{x}}{{a}_{i}}{{c}_{i}}({{a}_{x}}))}{{{N}_{i}}}$}

Output: $A(a)=sign∑_{i=1}^Iα_i  c_i (a)$

Initially, the input of training samples $(a_1,b_1 ),…,(a_n,b_n)$ are given with a label of $b_x$. The output is generated by the combined classifier with a predicted value. The important information from all the training samples of $W_i (x)$ is added to the SVM-Pegasos classifier. The weights with the same values are initialized before training the classifier. The initial step is to select the training samples from the dataset by performing random iterations according to their weighted values. After the SVM-Pegasos algorithm runs as a learner by moving it into the learning part. Then the SVM-Pegasos classifier generates the error $F_i$ in prediction with the training samples. Finally, the sample with significant information is selected and then moves to the next iteration. Similarly, this process is continued until all iterations for the training samples are completed. The final outcome of this classifier is to predict the labels of samples by combining all the classifiers ($a$) into a single classifier.