Qiming Li
email: qimingli@shmtu.edu.cn

Chen Huang

Zeyu Li

Yimin Chen

Lizhuang Ma

HCI based on Gesture Recognition in an Augmented Reality System for Diagnosis Planning and Training

Keywords: gesture recognition, augmented reality, human computer interaction

An Augmented Reality System for Coronary Artery Diagnosis Planning and Training (ARS-CADPT) is designed and realized in this paper. As the characteristic of ARS-CADPT, the algorithms of static gesture recognition and dynamic gesture spotting and recognition are presented to realize the real-time and friendly Human-Computer Interaction (HCI). The experimental results show that, with the use of ARS-CADPT, the HCI is natural and fluent, which improves the user's immersion and improves the diagnosis and training effects.

Introduction

Presently, 64 multi-slices computed tomographic coronary angiography technology has been considered as an effective way to diagnose coronary heart disease [START_REF] Miller | Diagnostic Performance of Coronary Angiography by 64-row CT[END_REF]. In the preoperative diagnosis planning process, the doctors are not accustomed to carry on the interactive diagnosis with computer by using the mouse and keyboard. 3D reconstruction based on Computed Tomography (CT) image sequence combined with augmented reality (AR) technology can effectively solve the above problems. AR is a new technology that strengthens the user's perception of the real world by superimposing the virtual 3D information generated by the computer system onto the real scene. In fact, medicine is one of the earliest application fields of AR technology. State Andrei et al. [START_REF] State | Case Study: Observing a Volume Rendered Fetus within a Pregnant Patient[END_REF] can draw a virtual 3D fetus on its abdomen position by ultrasonic scanning a pregnant woman. The doctor can understand the move and kick ability of the fetus through the Helmet-Mounted Displays (HMD) in 1994. AR technology can be used as an auxiliary means of surgical visualization. The 3D data of patient can be collected through Magnetic Resonance Imaging (MRI), CT or ultrasound images. According to the data, the corresponding virtual information can be rendered in real time. Combining with the actual situation of patient, the doctors can get more complete information, and improve the operation finally [START_REF] Tang | Augmented reality systems for medical applications: Improving surgical procedures by enhancing the surgeon's 'view' of the patient[END_REF]. Wu J. R. [START_REF] Wu | Real-time advanced spinal surgery via visible patient model and augmented reality system[END_REF] implements a spine surgery AR system, in which the surgeons can make use of 3D virtual model of preoperative patients to carry out spinal surgery simulation practice. In minimally invasive surgery, AR technology enables doctors to obtain the clairvoyant ability and improve the quality of surgery [START_REF] Paolis | Augmented reality in minimally invasive surgery[END_REF]. AR can also be used for medical training. According to statistics, over 50% of the augmented virtual reality application system are used in medical training, the most of which are realized based on virtual reality (VR) technology [START_REF] Ivelina | Animations of medical training scenarios in immersive virtual environments[END_REF]. The amount of application system based on AR is relatively less. The AR based aid medical training system [START_REF] Ana | Realistic simulation of deformation for medical training applications[END_REF] is used to achieve medical training and examination through human body modeling.

The natural and real-time HCI is one of the three important features of AR system [START_REF] Azuma | A survey of augmented reality[END_REF]. However, the traditional interaction mode such as using the mouse and keyboard cannot meet the application requirements. People are eager to realize the HCI in a very natural way. Gesture is just the most natural and intuitive way of interaction in human communication except language. Therefore, HCI based on gesture recognition has become a hot research topic. Gestures are usually defined as hand shapes and movements produced by the combination of palms, fingers, and even arms. The task of HCI based on gesture recognition is: firstly, recognize the meaning of the gesture correctly according to the data captured in real time, then trigger the corresponding instruction, and make the system feedback finally.

An AR system used for coronary artery diagnosis planning and training is designed and realized in this paper, which is called ARS-CADPT in the following paragraph. The system is very complicated, but the HCI based on gesture recognition is mainly discussed in this paper. The operating user or the lecturer can interact with the 3D model of the coronary arteries in a natural and intuitive manner with the defined gestures, and can perform simulation measurement of radius of vessels, and thus achieve a comprehensive and intuitive presentation and an accurate and detailed explanation of the patient's situation. The interns or students can understand and study the patient's coronary detail situation on a large tiled screen.

2

System Architecture

The Hardware Architecture of ARS-CADPT

As shown in Fig. 1, ARS-CADPT is constructed based on cluster architecture. It consists of several high-performance workstations, a parallel rendering and tiled display subsystem and a series of equipment for interaction data capture. Server 1 is used for 3D reconstruction of coronary artery based on CT images and storage the 3D coronary artery model database of all the previous patients. Server 2 is the surveillance and control center of the system. Server 3 is used for processing the lecturer's interaction data which is captured by the equipment such as Leap Motion, magnetic tracker, Microsoft Hololens, and so on. The display subsystem is consists of 5 parallel rendering nodes and a tiled screen, which is used for study, view and emulate for the student and intern users.

Fig. 2. The workflow and functions of the ARS-CADPT

The ARS-CADPT is realized based on multi-thread technique. The main thread is used for the diagnosis and training process, the HCI thread is used for the real-time interaction with the 3D coronary artery model, and the feedback is displayed to the users via the display thread. Therefore, the system mainly includes three function modules. 3D coronary artery reconstruction based on CT images, real-time HCI based on gesture recognition and synchronous display based on parallel rendering. Hereinto, the HCI module is the characteristic of the system. The interaction gestures used in the system are defined firstly. Then the algorithms for static gesture recognition, dynamic gesture spotting and recognition are proposed. The corresponding interaction operations are triggered according to the gesture recognition results finally.

Real-time HCI

As shown in Fig. 2, the HCI module serves the main process of diagnosis and training. It is the bridge between the operating user and the system. The HCI in the system is accomplished based on the coordination of static and dynamic gesture recognition. The Leap Motion manufactured by Leap Company is used to capture the hand shape and motion trajectory.

Gesture Definition

Gesture includes static gesture and dynamic gesture. Considering a right-hander, the static gestures used in ARS-CADPT are defined in Table 1 and illustrated in Fig. 3.

Table 1. The static gestures and the corresponding HCI functions in ARS-CADPT Legend Class HCI function Fig. 3 a 1 System input Left mouse button down Fig. 3 b 2 right mouse button down Fig. 3 c 3 capture the hand trajectory as the trajectory of cursor The gestures can be divided into two categories: system input and model control. The former is used to achieve all kinds of system input instructions by gestures instead of mouse and keyboard, and the latter is used to manipulate and control the 3D models directly. Hereinto, the static gestures of class 1~3 are used for system input, and the static gestures of class 4~10 are used for model control.

In addition, the accurate measurement of vessel diameter, confirming the location and extent of stenosis and the situation of collateral circulation formation are objective gist for determining the diameter of stent during interventional treatment. However, in clinical practice, the measurement of vessel stenosis is mainly based on visual estimation, and its accuracy needs to be further improved. In ARS-CADPT, the oper-ating user can interactively scale the virtual model freely and measure the radius of the blood vessel with the gesture shown in Fig. 3f.

There are two ways of interacting with the 3D model in ARS-CADPT. The full synchronization mode is to make the movement of 3D model completely consistent with the hand of which the static gesture is class 4 (shown in Fig. 3d), while the fine adjustment interaction mode is used for the slight, accurate and complex operations. The fine adjustment interaction mode is mainly realized by recognizing a series of dynamic gestures formed by the hand trajectory of which the static gesture is class 5 (shown in Fig. 3e). Therefore, the dynamic gestures needed in ARS-CADPT are defined in Table 2, and some examples are illustrated in Fig. 4. Hereinto, the translation gestures can be used for both system input and model control. The rotation and zoom gestures are used for model control only.

Static Gesture Recognition

The static gesture recognition algorithm based on rough sets theory was proposed.

The static gesture recognition is considered as a decision table, denoted as DT= (U, C∪D, V, f). Hereinto, U is a nonempty finite set of all the static gesture instances, called universe. C and D are also nonempty finite sets, C is called condition-attribute set, and D is called decision-attribute set. V= , V a is the range of attribute a. f:

U×A V is called the information function, which assigns a value to each attribute.

The data of static gestures are mainly captured by Leap Motion. The distance between the fingertips and the distance between the fingertips and the palms center are considered as the major factors influencing the static gestures, which are belong to C. The distance is discretized into five values, so V C = {1,2,3,4,5}. There is only one decision attribute: the static gesture (denoted as d), i.e. D= {d}. According to Table1, there is V d ={1,2,3,4,5,6,7,8,9,10,11(undefined)}. To sum up, the decision table of static gesture recognition can be modeled as shown in Table 3.

Table 3. decision table of static gesture recognition

U C D 1 2 … 10 i ii … v d x 1 v 1,1 v 1,2 … v 1,10 v 1,i v 1,ii … v 1,v v 1,d x 2 v 2,1 v 2,2 … v 2,10 V 2,i V 2,ii … V 2,v v 2,d … … … … … … … … … … x n v n,1 v n,2 … v n,10 V n,i V n,ii … V n,v v n,d
Hereinto, x j (j=1,2,…,n) is the j-th static instance, U={ x 1 , x 2 ,…, x n } is the set of static instance, and v j,a is the value of attribute a(a∈C∪D) in the j-th static instance.

The decision table is constructed according to the selected sample set. Then, the attribute reduction algorithm based on Skowron discernibility matrix and discernibility function is adopted: Firstly, construct the discernibility matrix; Secondly, construct the discernibility function; Thirdly, simplify the discernibility function using the absorption law; Finally, the conjunctive normal forms in the minimal disjunctive normal form of the discernibility function are all the D-reduct of C.

The classical reduction algorithm of attribute values is based on the value core concept. At first, calculate the value core of every instance in the decision table after attribute reduction; then get the minimal reduct from the value core table; finally, obtain the decision rules.

At last, the rules can be used to recognize the user's static gesture in real time.

Dynamic Gesture Spotting

Pavlovic V. I. et al. [START_REF] Pavlovic | Visual Interpretation of Hand Gestures for Human-Computer Interaction: A Review[END_REF] divide the movements of the hand into two categories. One is the gesture that conveys the user's intention, and the other is meaningless action. Therefore, the starting point and termination point of each dynamic gesture must be located in the acquired continuous gesture data stream. It is the premise and foundation of dynamic gesture recognition. However, the existing dynamic gesture recogni-tion methods usually assume either known spatial spotting or known temporal spotting, or both [START_REF] Jonathan | A unified framework for gesture recognition and spatiotemporal gesture segmentation[END_REF], which is unrealistic in the practical applications.

According to the data captured by Leap Motion, a segment of right hand motion trajectory is drawn in Fig. 5a. It can be seen the intervals of points are different. That means the speed is changing during the gestures. The curve shown in Fig. 5b is the speed variation during the gestures in Fig. 5a. It is clearly illustrated that the speed climbs up and then declines for several times. Each speed jump corresponds to a wave crest on the speed curve. There are five obvious wave crests which exactly correspond to five gestures. So, a simple method is to set a threshold. If speed is above the threshold, a gesture is detected. But this method would arouse some problems. One is that some noise points exist. Another is that the speed of dynamic gestures varies from person to person, and setting a threshold is not-so-flexible. In fact, the dynamic gestures defined in our system are all completed in a speed jump. Therefore, we could think that a dynamic gesture is generated only by judging an upward tendency of speed. Thirty data points are enough to represent the tendency from the experiment. We define the upward tendency, which is the speed at any moment is higher than before. The fuzzy set of the standard upward tendency is denoted as A, and a new fuzzy set B is obtained every time, and compute the close degree between A and B using Hamming close degree. The equation is:

N H (A, B)=1-d(A, B)/n=1-δ(A, B).
(

Where

      n i i B i A x x B A d 1 ) ( ) ( ,   ,         Max y Max y x i i i 0 1  ,        Max y Max i or Max y y Max i i i 1 .
The lower the close degree is, the greater likelihood it is an upward tendency. If the close degree is less than 0.3, we believe the set B represents the upward tendency.

Dynamic Gesture Recognition

After the gesture spotting, a series of independent dynamic gesture trajectories can be obtained in real time.

1. Single-hand gesture Let C={c 1 ,c 2 ,…,c n } be the set composed of the n classes dynamic gestures, and A={a 1 ,a 2 ,…,a m } be the set composed of the m attributes influencing dynamic ges-tures. s k is the k-th gesture sample to be recognized. After s k was recognized by all the attribute classifiers, a decision matrix is obtained and denoted as:

DM(s k )=((f 11 k , f 21 k , …, f m1 k ) T , (f 12 k , f 22 k , …, f m2 k ) T , …, (f 1n k , f 2n k , …, f mn k ) T ). (2)
Hereinto, the row vector

f i = (f i1 k , f i2 k , …, f in k )(i=1,2,…,m)
is the recognition results of s k by attribute classifier a i with respect to the m classes, while the column vector

f j =(f 1j k , f 2j k , …, f mj k ) T (j=1,2,…,n)
is the recognition results of s k by all the attribute classifiers with respect to the c j -th class. then the intersection of the function f j :A→[0,1](if the output of classifier is not in the interval [0,1], it can be satisfied according to normalization) and the vector f i , f ij k , indicates the degree of certainty that s k is recognized as the c j -th class by the attribute classifier a i .

Let g be the fuzzy measure defined over P(A), the power set of A. The fuzzy measure on the single-point set, i.e. fuzzy density g i =g({a i })(i=1,2,…,m) represents the degree of credibility that the attribute classifier a i makes decision. If X∈P(A), g(X) represents the degree of credibility that the attribute classifier X makes decision. However, as the single attribute classifiers are designed for a certain attribute feature of dynamic gestures, they should have different degrees of credibility for different gestures, namely, the single attribute classifiers should have different fuzzy densities. Let g j =(g 1j , g 2j ,..., g ij ..., g mj ) be the fuzzy density vector of class c j , where g ij represents the degree of credibility of the attribute classifier a i with respect to class c j . Then the fuzzy integral over A of the function f j k with respect to the fuzzy measure g j is the overall objective estimate for s k belonging to class c j . In the way, for a certain gesture sample s k , the system gives an integral value for every class, and the class that the greatest integral value corresponds with will be adopted as the recognition result.

Two-handed gesture

As for the two-handed dynamic gestures, the positions of the palm center at the beginning and end of the gesture are captured. ) be the coordinates of both hands at the beginning and end of the gesture respectively, then the lengths of line segment B l B r and line segment E l E r (denoted as d b and d e respectively)and the angle between them (denoted as φ) can be calculated. By projecting φ to plane YOZ, XOZ and XOY respectively, the three direction angles (denoted as α, β and γ) can be calculated. At last, the current gesture can be recognized by the following rules:

IF

Experimental Results

The related experiments are carried out based on the system platform. Hereinto, the recognition rate for static gesture achieves an average performance of 97.3%. After the dynamic gesture spotting, the continuous dynamic gesture stream is divided into a set of isolated dynamic gestures. The system achieves an average performance of 92.4% for the dynamic gestures according to the algorithm proposed in section 3.4.

The system is used for coronary artery diagnosis planning and teaching. As shown in fig. 6, the lecturer is controlling the 3D coronary artery model in a natural and intuitive manner with the defined gestures, and thus achieves a comprehensive and intuitive presentation and an accurate and detailed explanation of the patient's situation. At the same time, the student users or interns can study and understand the patient's coronary detail situation on a large tiled screen. Fig. 6. System running instance: the lecturer is interacting with the 3D coronary artery model.

Conclusion and the Future Work

This paper presented an augmented reality system for coronary artery diagnosis planning and training. One of its advantages is to realize the real-time and friendly HCI by using the algorithms of static gesture recognition and dynamic gesture spotting and recognition. It can be concluded that the proposed solutions make the HCI more natural and convenient, make the explanation clearer and more intuitive, and finally achieve a better effect for the preoperative diagnosis planning and training. It also can be concluded that the AR technology has great potential to apply to the computer-aided medical system. Some examples of AR-based surgical applications have been presented in the literatures [START_REF] Chen | Development of a surgical navigation system based on augmented reality using an optical see-through head-mounted display[END_REF][START_REF] Chen | Development of a surgical navigation system based on 3D Slicer for intraoperative implant placement surgery[END_REF]. Meanwhile, there are still some technical challenges for further research and exploration. For example, the gesture set defined in ARS-CADPT is just a little subset of the human gesture set, and the gestures people used in daily life are much more complicated. This puts forward higher requirements to the gesture recognition algorithms. Moreover, there is still a lot of work to do before ARS-CADPT can be applied to real-time surgery.

Fig. 1 .

 1 Fig. 1. The hardware of ARS-CADPT

FigFig. 3 .

 3 Fig.3 d 4

Table 2 .Fig. 4 .

 24 Fig. 4. Some examples of the dynamic gestures defined in ARS-CADPT: a. left translation (at default scale), b. right translation at scale I, c. right rotation at scale II, d. zoom out at scale IV, e. right translation by left hand (at default scale)

Fig. 5 .

 5 Fig. 5. A segment of dynamic gesture: a. Trajectory, b. Speed curve

  Let B l =( b x l

  φ<θ 1 AND (d ed b )> σ (<σ), THEN class(g)= zoom in (out) IF φ>θ 2 AND max(α, β, γ)= α | β | γ, THEN class(g)= Rotate around the X|Y|Z axis Where θ 1 , θ 2 and σ are thresholds predefined.

Acknowledgement

This work is supported by Natural Science Foundation of China (Grant No.: 61472245) and Shanghai Municipal Natural Science Foundation (Grant No.: 14ZR1419700 and 13ZR1455600).


Changming Zhu
email: cmzhu@shmtu.edu.cn

Entropy-Based Support Matrix Machine

Keywords: Support Matrix Machine, Entropy, Fuzzy Membership, Imbalanced Data Set, Pattern Recognition

diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Support Vector Machine (SVM) constructs a hyperplane or set of hyperplanes in a high-or infinite-dimensional space, which can be used for classification, regression, or other tasks. Intuitively, a good separation is achieved by the hyperplane that has the largest distance to the nearest training-data point of any class (so-called functional margin), since in general the larger the margin the lower the generalization error of the classifier [START_REF]Support Vector Machine[END_REF]. Conventional SVM can be used in many tasks including text and hypertext categorization, classification of images, classifying proteins in medical science, and recognizing hand-written characters. Although SVM has been validated effect on these applications, it still has two disadvantages. One is that SVM cannot process matrix patterns and another is that it cannot process imbalanced problem.

• Matrix patterns which dimensions are m × n (where m and n are both larger than 1) are the basic of matrix learning. For example, video and images are both matrix patterns. In order to process matrix patterns, matrix-patternoriented learning machine (MatC), i.e., matrix learning machine, has been developed. Classical learning machines include matrix-pattern-oriented Ho-Kashyap learning machine with regularization learning (MatMHKS) [START_REF] Chen | Matrix-pattern-oriented Ho-Kashyap classifier with regularization learning[END_REF], new least squares support vector classification based on matrix patterns (MatLSSVC) [START_REF] Wang | New least squares support vector machines based on matrix patterns[END_REF], and oneclass support vector machines based on matrix patterns (OCSVM) [START_REF] Yan | One-class support vector machines based on matrix patterns[END_REF]. Besides those matrix learning machines, Xie et. al have proposed a Support Matrix Machine (SMM) [START_REF] Xie | Support Matrix Machines[END_REF] so as to replace SVM. SMM can leverage the structure of the data matrices and has the grouping effect property. But all of these matrix learning machines cannot process imbalanced problem.

• As is known to all, in many real-world classification problems, such as e-mail foldering [START_REF] Dai | Class Imbalance Learning via a Fuzzy Total Margin based Support Vector Machine[END_REF], fault diagnosis [START_REF] Deng | Nonlinear Process Fault Pattern Recognition Using Statistics Kernel PCA Similarity Factor[END_REF], detection of oil spills [START_REF] Guo | Oil Spill Detection Using Synthetic Aperture Radar Images and Feature Selection in Shape Space[END_REF], and medical diagnosis [START_REF] Ozcift | Classifier Ensemble Construction with Rotation Forest to Improve Medical Diagnosis Performance of Machine Learning Algorithms[END_REF], we can always divide a data set into two classes, one is positive class and the other is negative class. When the size of positive class is much smaller than that of negative class, imbalanced problem occurs. Since most standard classification learning machines including Support Vector Machine (SVM) and Neural Network (NN) are proposed with the assumption on the balanced class distributions or equal misclassification costs [START_REF] Brown | An Experimental Comparison of Classification Algorithms for Imbalanced Credit Scoring Data Sets[END_REF], so they fail to properly represent the distributive characteristics of patterns and result in the unfavorable performance when they are adopted to process imbalanced problem. In order to overcome such a disadvantage, Fuzzy SVM (FSVM) [START_REF] Lin | Fuzzy Support Vector Machines[END_REF] and Bilateral-weighted FSVM (B-FSVM) [START_REF] Wang | A New Fuzzy Support Vector Machine to Evaluate Credit Risk[END_REF] are proposed. FSVM applies a fuzzy membership to each input pattern and reformulates SVM such that different input patterns can make different contributions to the learning of decision surface. B-FSVM treats every pattern as both positive and negative classes, but with different memberships due to we can not say one pattern belongs to one class absolutely. But for both of them, how to determine the fuzzy membership function is the key point. Furthermore, both of them cannot process matrix patterns.

In this paper, we try to propose a learning machine which can process matrix patterns and imbalanced problem. First, in order to process matrix patterns, we adopt SMM as a basic. Then in order to process imbalanced problem, we adopt the notion of FSVM, namely, applies a fuzzy membership to each input pattern. Furthermore, for the fuzzy membership, we propose a new fuzzy membership evaluation approach which assigns the fuzzy membership of each pattern based on its class certainty. In this paper, class certainty demonstrates the certainty of pattern labeled to a certain class. Due to the entropy is an effective measure of certainty, we adopt the entropy to evaluate the class certainty of each pattern. In doing so, the entropy-based fuzzy membership evaluation approach is proposed. This approach determines the fuzzy membership of training patterns based on their corresponding entropies. By adopting the entropy-based fuzzy membership evaluation and SMM, the Entropy-based Support Matrix Machine (ESMM) is proposed to process the imbalanced data sets. In practice, as the importance of positive class is higher than that of negative class in imbalanced data sets, i.e., the learning machine should pay more attention to positive patterns than negative ones. Thus, positive patterns are assigned to relatively large fuzzy memberships to guarantee the importance of positive class here. While, the fuzzy memberships of negative patterns are determined by the entropy-based fuzzy membership evaluation approach, i.e., patterns with lower class certainty are assigned to small fuzzy memberships based on the criterion that patterns with lower class certainty are more insensitive to noise, and easily mislead the decision surface, thus their importance should be weakened on imbalanced data sets. After evaluating the fuzzy membership of all training patterns, ESMM is adopted to classify imbalanced data sets.

The contributions of this paper can be highlighted as follows:

(1) A new entropy-based fuzzy membership evaluation approach is proposed. This approach adopts entropy to evaluate class certainty of a pattern and determines the corresponding fuzzy membership based on class certainty. In doing so, the learning machine can pay more attention to the patterns with higher class certainty to result in more robust decision surface.

(2) To guarantee the importance of positive class, the positive patterns are assigned to the relatively large fuzzy memberships, which results in the decision surface paying more attention to the positive class so as to increase generalization of learning machine.

The rest of this paper is given below. Section II introduces the proposed entropy-based fuzzy membership evaluation approach, then give the details of ESMM. In Section III, several experiments on real-world imbalanced data sets and matrix patterns including images are conducted to validate the effectiveness of ESMM. Following that, conclusions are given in Section IV.

2 Entropy-based matrix learning machine (ESMM)

Entropy-based fuzzy membership

When we process imbalanced data sets, positive class is always more important than negative class. Thus, in the proposed entropy-based fuzzy membership evaluation approach, we assign positive patterns to a relatively high fuzzy membership, e.g., 1.0, to guarantee the importance of positive class. As to the negative class, we fuzzify negative patterns based on their class certainties.

In information theory, entropy is always used to characterize the certainty of source of information. If entropy is smaller, then information is more certain [START_REF] Shannon | A Mathematical Theory of Communication[END_REF]. By employing this character of entropy, we can evaluate the class certainty of a pattern in the training class. After getting the class certainty of each pattern, we assign fuzzy membership of each training pattern based on class certainty. In practice, the patterns with higher class certainty, i.e., lower entropy, are assigned to higher fuzzy memberships to enhance their contributions to the decision surface, and vice versa.

Suppose that there are N training patterns, {x i , y i } where i = 1, 2, ..., N and y i ∈ {+1, -1} is the class label. When y i = 1, pattern x i belongs to the positive class, otherwise, it belongs to the negative class. The probabilities of x i belonging to positive and negative class are p +i and p -i respectively. The entropy of x i is H i = -p +i ln(p +i )p -i ln(p -i ) where ln represents the natural logarithm operator. Due to neighbors of a pattern can determine local information of it, thus the probability evaluation is based on its k nearest neighbors. For a pattern

x i , we select its k nearest neighbors {x i1 , x i2 , ..., x ik } at first. Then we count the number of both positive and negative class in these k selected patterns and denote the numbers of patterns belonging to positive and negative class are num +i and num -i respectively. Finally, the probabilities of x i belonging to positive and negative class are calculated with p +i = num+i k and p -i = num-i k .

After evaluating the class probabilities of x i , we can calculate its entropy.

By adopting the above entropy evaluation approach, the entropy of the negative patterns are H = {H -1 , H -2 , ..., H -n-}, where n -is the number of the negative patterns. H min and H max are the minimum and maximum entropy of H. The entropy-based fuzzy memberships for negative patterns are evaluated as follows.

Firstly, separate the negative patterns into m subsets based on their entropy as described in Table 1, i.e., {Sub k } where k = 1, 2, ..., m.

k=1:m Up=Hmax - k-1 m (Hmax -H min ) Low=Hmax -k m (Hmax -H min ) For i=1:n - if Low<H -i ≤Up negative pattern x i is distributed into the subset Sub k . End End
Then, fuzzy memberships of patterns in each subset are set as:

F M k = 1.0 -α × (k -1), k = 1, 2, 3, ..., m (1)
where F M k is the fuzzy membership for patterns distributed in subset Sub k , the fuzzy membership parameter α ∈ (0, 1 m-1 ) since F M k is positive and not larger than 1.0. It should be declared that patterns in the same subset are set to same fuzzy membership so that these patterns selected in the same subsets have same importance to the decision surface. Finally, the fuzzy membership s i for a training pattern x i is assigned as: if y i = +1, then s i = 1.0, else if y i = -1 and x i ∈ Sub k , then s i = F M k . So far, the entropy-based fuzzy membership for the training patterns are evaluated.

Entropy-based support matrix machine

By adopting the evaluated entropy-based fuzzy membership which is given before, we propose the entropy-based support matrix machine (ESMM). The detailed description on ESMM is given below.

Suppose that there is a binary-class classification problem with N matrix patterns (A i , y i , s i ), i = 1, 2, ..., N . Here A i ∈ R m×n is the matrix representation of x i and its class label is y i ∈ {+1, -1}. If y i = +1, x i or A i belongs to class +1 or positive class, and then if y i = -1, the pattern belongs to class -1 or negative class. s i is the entropy-based fuzzy membership.

The corresponding criterion function of ESMM is defined below.

minL(W, b) = 1 2 tr(W T W ) + θ ||W || ⋆ + (2)
C N i=1 (s i (1 -y i [tr(W T A i ) + b i ]))
where W ∈ R m×n is the matrix of regression coefficients and its nuclear norm is ||W || ⋆ . θ is the coefficient. tr is the trace of matrix. b i is a loose variable for pattern

A i . C (C ∈ R, C ≥
b i (k + 1) = b i (k) + ρ(e i (k) + |e i (k)|) (3)
where the error vector e at k -th iteration of A i , i.e., e i (k) should be W (k) T A i -1b i (k) and W (k) and b i (k) are k-th component of W and b i . Then we adopt the similar method of SMM to get the optimal W b here. After that, we can get the discriminant function of ESMM as below.

g(A i ) = W T A i (4)
If g(A i ) > 0, then we label A i as a positive pattern, then if g(A i ) < 0, we label A i as a negative pattern.

Experiments

In this section, we adopt 25 real-world imbalanced data sets and 5 image data sets for examples and the compared learning machines are SVM, FSVM, MatMHKS, B-FSVM, SMM. The used 25 real-world imbalanced data sets are selected from the KEEL imbalanced benchmark ones [START_REF] Alcala-Fdez | A Software Tool to Assess Evolutionary Algorithms for Data Mining Problems[END_REF][START_REF] Alcala-Fdez | A Software Tool to Assess Evolutionary Algorithms for Data Mining Problems[END_REF]. Information of these data sets are given in Tables 2 and3.

Experimental settings

In terms of the compared learning machines and ESMM, the experimental settings are given here. For the SVM-based learning machines, the used kernel is Radial Basis Function (RBF) kernel ker(x i , x j ) = exp(-

||xi-xj|| 2 2 σ 2
) where σ is selected from the set {10 -3 , 10 -2 , ..., 100, 1000}. For MatMHKS, the experimental setting can be found in [START_REF] Chen | Matrix-pattern-oriented Ho-Kashyap classifier with regularization learning[END_REF]. For SMM, the experimental setting can be found in [START_REF] Xie | Support Matrix Machines[END_REF]. For ESMM, its setting is similar with SMM. Moreover, for ESMM, the number of the separated subsets m = 10 and the fuzzy membership parameter α = 0.05 which results in the fuzzy membership 0.5 ≤ s i ≤ 1.0. The reason of restricting s i ∈ [0.5, 1.0] is that the class label of x i should not be neglected when determining the fuzzy membership, i.e., x i is more likely to be classified to the class which is indicated by its class label. As to negative class patterns, we set s i > 0.5 to indicate that a negative pattern x i is more likely to belong to the negative class. Moreover, the number of nearest neighbors k for calculating the class probability is selected from {1, 2, 3, ..., 18, 19, 20}. In order to measure the performance of compared learning machines on imbalanced data sets, the values of Area Under the ROC Curve (AUC) [START_REF] Huang | Using AUC and Accuracy in Evaluating Learning Algorithms[END_REF] is given. Besides those, maxIter = 500 represents the maximal size of the iteration. One-against-one classification strategy is used for multi-class problems here [START_REF] Milgram | One Against One" or "One Against All", Which One is Better for Handwriting Recognition with SVMs?[END_REF][START_REF] Debnath | A decision based one-against-one method for multi-class support vector machine[END_REF][START_REF] Hsu | A comparison of methods for multiclass support vector machines[END_REF][START_REF] Cortes | Support vector machine[END_REF]. The 10-fold cross validation approach [START_REF] Braga-Neto | Is Cross-validation Valid for Small-sample Microarray Classification?[END_REF] is adopted for the parameter selection. The computations are performed on Intel Core 2 processors with 2.66GHz, 8G RAM, Microsoft Windows 7, and Matlab environment.

Experiments on real-world imbalanced data sets

For experiments, the AUC values are presented in Table 4. The average AUC on all used data sets are presented. Moreover, the average ranks of the learning machines on the used data sets are listed. From the experimental results, it is found that: (1) ESMM results in the best classification performance on 12 of 30 imbalanced data sets which indicates that the our proposal outperforms the compared learning machines; (2) ESMM outperforms the traditional MatMHKS on 26 of 30 imbalanced data sets; (3) The average AUC of ESMM is respectively greater than B-FSVM, FSVM, and SVM on about 5%, 9%, and 10%, which demonstrates that ESMM is of significate advantage in processing imbalanced data sets compared to SVM, FSVM, and B-FSVM; (4) It is found that for some data sets, for example, COIL-20, the three matrix-pattern-oriented approaches perform worse than SVM. We think it is the coincidence due to the training part is gotten in random. But according to the average result, we still find that our proposed ESMM outperforms others in average; [START_REF] Xie | Support Matrix Machines[END_REF] For the used 25 vector data sets, ESMM performs best on the 9 data sets of them. For others, ESMM performs better in average and it does not perform worst on any vector data set. This phenomenon can explain the superiority of the ESMM on the vector data sets; (6) As we said before, ESMM and FSVM both adopt fuzzy membership to each input pattern. Now from the experiments, it is found that compared with FSVM, the better performance of ESMM validates that the proposed entropy-based fuzzy membership evaluation approach boosts the performance of a learning machine.

Influence of parameter k on the performance of ESMM

In ESMM, the entropy-based fuzzy membership is evaluated based on the class probability of each training pattern. Thus, the number of nearest neighbors k might have some influence on the class probability. To further investigate the effectiveness of ESMM, here, we study the influence of k on the classification performance. All data sets given in Table 2 are used and related experimental results are given in Fig. 1. The figure shows AUC on the testing sets of the adopted real-world imbalanced data sets and image data sets with respect to k.

It is found that: (1) the number of the selected nearest neighbors for calculating the class probability, i.e., k, has some influence on the classification performance since AUC curves fluctuate with respect to k on most data sets; (2) on some data sets, the classification performances are sensitive to the variation of k, since AUC curves on these data sets fluctuate greatly while on some data sets, are not; (3) in generally, with k from 8 to 12, ESMM always gets best performance. Such a result can give us a guidance that how to determine an appropriate k in practical use.

Comparison between ESMM and entropy-based MatMHKS (EMatMHKS)

Here, we give the comparison between ESMM and our previous proposed learning machine, entropy-based MatMHKS (EMatMHKS) [START_REF] Zhu | Entropy-based matrix learning machine for imbalanced data sets[END_REF] which is also an entropybased matrix learning machine.

Conclusion

There are two hot spots of present research, one is imbalanced problem and the other is matrix learning. Imbalanced problem occurs when the size of positive class is more smaller than that of negative class. However, most standard classification learning machines result in unfavorable performance on imbalanced data sets since they are originally designed for processing balanced problems.

Although SVM can process imbalanced data sets in some extent, it assigns the same importance to each training pattern. This results in the decision surfaces biasing toward the negative class. In order to overcome the disadvantage of SVM, some researchers propose FSVM and B-FSVM by applying fuzzy memberships to the training patterns to reflect different importance of them. Since the key point in FSVM and B-FSVM is how to determine the fuzzy membership, so this paper presents an entropy-based fuzzy membership evaluation approach for imbalanced data sets. Moreover, matrix patterns cannot be solved by those traditional learning machines including SVM well, so some scholars have developed 2 or Table 3.

MatMHKS and SMM. This paper adopts the entropy-based fuzzy membership and SMM, and then proposes ESMM. ESMM can not only guarantee importance of the positive class, but also pay more attentions to the patterns with higher class certainties. Thus, ESMM can results in more flexible decision surfaces than both conventional SVM, FSVM, B-FSVM, and MatMHKS on the imbalanced data sets. To validate the effectiveness of ESMM, we adopt 25 real-world imbalanced data sets and 5 image data sets for experiments. Experimental results demonstrates that ESMM outperforms the compared learning machines on realworld imbalanced data sets and the images. Moreover, in the process of ESMM, k has some influence on the classification performance.

For

  0) is the regularization parameter that adjusts the tradeoff between model complexity and training error. Here, b = [b 1 , ..., b i , ..., b N ] T and b i is started as b i ≥ 0. The iteration for b is given in Eq. (3).

Fig. 1 .

 1 Fig.1. Variation of AUC values of ESMM with respect to k on the adopted imbalanced data sets and image data sets. Here, in the legend, each number denotes one data set which is given in Table2or Table3.

Table 1 .

 1 Algorithm of negative class separation.

Table 2 .

 2 Information of real-world imbalanced data sets (IR represents the imbalanced ratio of the corresponding data set).

	Order	Data set	Attributes Training Testing IR
	1	Wisconsin	9	546	137	1.86
	2	Haberman	3	245	61	2.78
	3	Newthyroid2	5	172	43	5.14
	4	Ecoli3	7	269	67	8.6
	5	Ecoli046vs5	6	162	41	9.15
	6	Yeast2vs4	8	411	103	9.08
	7	Ecoli067vs5	6	176	44	10
	8	Led7digit02456789vs1	7	354	89	10.97
	9		9	171	43	11.59
	10	Yeast1vs7	7	367	92	14.3
	11	Pageblocks13vs4	10	378	94	15.86
	12	Glass016vs5	9	147	37	19.44
	13	Yeast2vs8	8	386	96	23.1
	14	Yeast1289vs7	8	758	189	30.57
	15	Yeast6	8	1187	297	41.4
	16	Pima	8	614	154	1.87
	17	Ecoli1	7	269	67	3.36
	18	Segment0	19	1846	462	6.02
	19	Ecoli034vs5	7	160	40	9
	20	Ecoli01vs235	7	195	49	9.17
	21	Yeast05679vs4	8	422	106	9.35
	22	Glass016vs2	9	154	38	10.29
	23	Glass0146vs2	9	164	41	11.06
	24	Cleveland0vs4	13	138	35	12.31
	25	Ecoli4	7	269	67	15.8

Table 3 .

 3 Information of image data sets. Imbalanced ratio of each image data set is 9.0.

	Order	Data set	Attributes Training Testing
	26	COIL-20 [16]	32×32	1296	144
	27	Letter [17]	24×18	450	50
	28	ORL [18]	32×20	360	40
	29	PubFig [19]	74×74	52917	5880
	30	Gaze [20]	5184×3456	5292	588

Table 4 .

 4 AUC values (%) of the compared learning machines on real-world imbalanced data sets and image data sets. The best k for each data sets of ESMM is presented. (Note that the average AUC values and the average ranks of the compared learning machines are listed in the last two rows. Best result for each data set is in bold.)

	Data set	k	ESMM	SMM	MatMHKS	B-FSVM	FSVM	SVM
	1	9	94.05 ± 2.37	94.02 ± 2.30	89.98 ± 3.33	91.30 ± 3.03 96.10 ± 2.41	93.64 ± 3.67
	2	13	64.42 ± 1.96	64.47 ± 1.98 67.06 ± 1.40 61.58 ± 1.44	58.00 ± 2.05	54.08 ± 1.65
	3	11	93.28 ± 1.87	91.47 ± 1.89	89.78 ± 2.57	92.44 ± 2.32	93.43 ± 2.33 97.12 ± 2.90
	4	17	87.66 ± 2.41	87.37 ± 2.41	93.67 ± 2.70 94.55 ± 2.54	76.83 ± 2.36	65.74 ± 1.80
	5	14	98.61 ± 2.73 97.15 ± 2.74	92.59 ± 2.91	89.07 ± 3.15	86.61 ± 1.06	82.43 ± 1.91
	6	7	93.84 ± 2.95	94.33 ± 2.94 91.79 ± 1.47	87.37 ± 2.11	87.32 ± 1.85	83.77 ± 2.14
	7	5	97.12 ± 2.94 98.67 ± 2.87 90.79 ± 1.71	94.39 ± 1.97	78.90 ± 2.28	74.15 ± 2.52
	8	17	92.80 ± 2.62	90.53 ± 2.58	88.30 ± 2.29 93.43 ± 2.35	87.66 ± 2.14	81.64 ± 2.87
	9	18	81.33 ± 2.22 80.07 ± 2.20	68.12 ± 1.66	66.99 ± 1.74	69.21 ± 2.09	51.76 ± 1.51
	10	18 78.41 ± 2.53	76.58 ± 2.50	58.24 ± 1.95	68.95 ± 1.85	61.56 ± 2.14	67.10 ± 2.20
	11	15	79.86 ± 2.36	79.29 ± 2.29	77.65 ± 1.93	80.99 ± 2.37 92.11 ± 2.67	91.22 ± 3.32
	12	14 87.24 ± 2.27	85.75 ± 2.21	73.53 ± 2.07	80.66 ± 1.91	74.85 ± 2.18	75.31 ± 1.74
	13	15 71.30 ± 1.67	69.28 ± 1.69	67.12 ± 1.55	56.86 ± 1.20	57.62 ± 1.87	62.45 ± 1.52
	14	10	91.00 ± 2.24	91.62 ± 2.22 92.81 ± 3.17	87.97 ± 2.80	71.63 ± 1.54	71.64 ± 2.13
	15	5	72.58 ± 1.31 72.84 ± 1.32 71.15 ± 2.13	69.81 ± 2.38	68.65 ± 1.53	71.50 ± 1.75
	16	3	90.36 ± 1.72	89.80 ± 1.72	81.80 ± 2.18 93.74 ± 2.44 85.40 ± 2.59	78.11 ± 2.36
	17	10	80.62 ± 2.19	78.88 ± 2.20	82.32 ± 2.82	83.40 ± 2.01	98.24 ± 2.03 99.72 ± 2.25
	18	6	93.52 ± 3.00	91.50 ± 2.89	87.46 ± 1.91	83.81 ± 1.88	89.61 ± 2.98	77.26 ± 2.20
	19	18	92.35 ± 2.69 93.72 ± 2.73	92.22 ± 3.10	91.20 ± 2.19	74.69 ± 2.30	82.43 ± 2.18
	20	19 83.26 ± 1.96	81.00 ± 1.99	78.59 ± 2.28	79.42 ± 2.16	64.48 ± 2.02	66.34 ± 1.74
	21	5	75.38 ± 2.08 75.26 ± 2.06	69.36 ± 2.09	55.51 ± 1.57	61.42 ± 1.84	53.73 ± 1.52
	22	16	91.84 ± 2.19	91.08 ± 2.18	85.21 ± 2.01 95.55 ± 3.40	87.28 ± 2.53	94.66 ± 2.85
	23	4	81.49 ± 2.00	80.37 ± 2.00	59.32 ± 1.60	71.62 ± 2.15	66.51 ± 2.05	55.52 ± 1.35
	24	1	74.72 ± 2.07	74.44 ± 2.01	63.24 ± 1.72	60.41 ± 1.21	68.05 ± 1.76 77.90 ± 1.86
	25	12	95.59 ± 2.79 96.65 ± 2.81	95.98 ± 2.51	92.53 ± 2.80	84.58 ± 1.72	77.94 ± 2.37
	26	5	65.40 ± 1.78	64.90 ± 1.74	59.33 ± 1.97 71.77 ± 1.76	71.07 ± 1.76	69.50 ± 2.37
	27	18 66.08 ± 2.15	65.88 ± 2.15	57.58 ± 1.01	60.62 ± 1.50	49.37 ± 1.45	48.94 ± 1.32
	28	20 90.19 ± 2.06	88.54 ± 2.01	86.21 ± 3.07	79.27 ± 2.02	79.82 ± 1.71	82.30 ± 2.10
	29	8	92.89 ± 2.01	93.59 ± 1.99	88.12 ± 2.36 95.14 ± 3.19 89.48 ± 2.26	81.30 ± 2.45
	30	18 94.78 ± 1.70	92.15 ± 1.68	90.61 ± 2.56	87.60 ± 2.02	66.13 ± 1.23	85.69 ± 2.21
	AVG.	11.72 85.06 ± 2.23	84.37 ± 2.21	79.66 ± 2.20	80.60 ± 2.18	76.55 ± 2.02	75.16 ± 2.16
	AVG.rank		2.07	2.53	4.03	3.50	4.30	4.57

  Table 5 shows the comparison between ESMM and EMatMHKS. ↑ (↓) represents that ESMM performance better (worse) than EMatMHKS and (⋆) represents that the AUC value of ESMM is ⋆ larger or smaller than the one of EMatMHKS. From this table, we find that ESMM performs better than EMatMHKS in average.

Table 5 .

 5 Comparison between ESMM and EMatMHKS on AUC values (%).

	Data set		Data set		Data set		Data set		Data set		Data set
	1	↑(1.02)	2	↑(0.03)	3	↑(2.11)	4	↑(0.02)	5	↑(1.01)	6	↑(0.78)
	7	↓(0.23)	8	↑(1.02)	9	↑(2.98)	10	↑(6.18)	11	↓(0.03)	12	↑(3.91)
	13	↑(0.82)	14	↑(0.56)	15	↑(0.81)	16	↑(2.87)	17	↓(0.12)	18	↑(1.98)
	19	↑(0.04)	20	↑(1.23)	21	↑(3.12)	22	↑(2.91)	23	↑(8.19)	24	↑(2.12)
	25	↑(0.01)	26	↑(2.01)	27	↑(2.10)	28	↑(1.81)	29	↑(1.07)	30	↑(0.91)

Acknowledgment

This work is supported by Natural Science Foundation of Shanghai under grant number 16ZR1414500 and National Natural Science Foundation of China under grant number 61602296 and 51575336, and the authors would like to thank their supports.


Xiaoshuang Liu
email: xsliu@sues.edu.cn

Zhijun Fang
email: zjfang@sues.edu.cn

Xiang Liu
email: xliu@sues.edu.cn

Xiangxiang Zhang

Jianrong Gu

Qi Xu
email: qixu@shmtu.edu.cn

Driver Fatigue Detection Using Multitask Cascaded Convolutional Networks

Keywords: Fatigue detection, Cascaded convolutional neural network, Face alignment, PERCLOS

Driving fatigue is one of the main reasons of traffic accidents. In this paper, we apply the multitask cascaded convolutional networks to face detection and alignment in order to ensure the accuracy and real-time of the algorithm. Afterwards another convolution neural network (CNN) is used for eye state recognition. Finally, we calculate the percentage of eyelid closure (PERCLOS) to detect the fatigue. The experimental results show that the proposed method has high recognition accuracy of eye state and can detect the fatigue effectively in real-time.

Introduction

Along with the development of the auto industry and the transportation industry, traffic accidents have caused great loss in the property and damage to the society. Amongst these traffic accidents more than 20% of these traffic accidents are caused by fatigue driving. Safe driving has become a hot issue in today's society, Therefore, it is of great significance to develop a real-time and accurate fatigue detection system to send fatigue warning information when the driver is tired, which can effectively reduce the occurrence of traffic accidents. At present, fatigue testing contains three main directions. First, fatigue detection based on the vehicle state detection method, mainly through the turning angle, vehicle driving speed to detect whether the driver fatigue, this method is subject to external interference, the detection accuracy has a greater impact. Second, based on driver's physiological information [START_REF] Liu | Driving Fatigue Detection Based on EEG Signal[END_REF], mainly by detecting the driver's heart rate, pulse and other physiological signals to determine whether the driver is in a state of fatigue, This method requires the driver to carry a lot of testing equipment, very cumbersome, and the driver has a great interference. Third, fatigue detection methods based on computer vision [6][8-10], this method is a non-intrusive way, the facial features can be calculated by analyzing the changes of facial expression, such as eye closure duration, yawning and so on.

In the fatigue detection, driver face detection and alignment are important. The multitask cascaded convolutional networks to face detection and alignment [START_REF] Zhang | Joint Face Detection and Alignment Using Multitask Cascaded Convolutional Networks[END_REF] has proven to be an effective method. Another very important step is the detection of human eye state. Compared to the traditional active infrared radiation method [START_REF] Zhang | Driver Fatigue Detection Based on Eye State Recognition[END_REF], normal camera image employs a safer passive way. To detect the state of eyes, There are many methods, such as AdaBoost classifier [START_REF] Shi-Feng | Eyes state detection based on adaboost algorithm[END_REF], SVM classifier [START_REF] Li | Eyes state detection method based on LBP[END_REF] and so on. However, their ability of expressing features is limited. Recently, convolutional neural network (CNN) achieve remarkable progresses in a variety of computer vision tasks. In our paper, we design a driver fatigue detection system using multitask cascaded convolutional networks. As shown in Figure 1, the method mainly includes five parts: Joint face detection and alignment using multitask cascaded convolutional networks, normalize the current image and ground truth shape according to the scaled mean shape, extract the area of eye, state of eye recognition, fatigue detection.

2

Joint Face Detection and Alignment Using Multitask Cascaded Convolutional Networks Stage 3: This stage is similar to the second stage, but in this stage we aim to identify face regions with more supervision. In particular, the network will output five facial landmarks' positions.

3

Extraction Area Eye

Face normalization

In order to accurately extract the eye areas, we need to calculate the average face .Then normalize the current image and ground truth shape according to the scaled mean shape, this process is 2D affine transformation .The 2D affine transformation is a method used to change the rotation angle, the scale, and the location of a shape. The transformation can be represented as equation [START_REF] Zhang | Joint Face Detection and Alignment Using Multitask Cascaded Convolutional Networks[END_REF].

x ax by c y dx ey f

           (1)
Where is the coordinate of the th feature point on the average face,  

, T ii xy i i 1 0 0 1 1 1 i i i i i i x a b c x x y d e f y M y                                            (2)
For convenience, equation ( 2) can be rewritten as equation [START_REF] Shi-Feng | Eyes state detection based on adaboost algorithm[END_REF].

U Kh  (3)
Where is the feature point matrix of the average face, is the feature point matrix of the detected face.

is affine transformation matrix. It can be Calculated with least squares solution. Then, the solution of can be obtained as equation ( 4).

 

1 TT h K K K U   (4)
Normalize the current image and ground truth shape.

Fig. 3. Normalize the current image and ground truth shape according to the scaled mean According to the scaled mean shape aimed at change the detected faces' rotation angle, the scale, and the location of a shape. As shown in Figure 3.

Eye area extraction

In this paper, we extract the area of eyes based on the facial landmarks after normalization as shown in Figure 4 .The eye area has a size of 32×32.

Eye state recognition

CNN expresses features more better, avoiding the manual feature selection. So we used convolutional neural network to detect the state of eyes.

Convolutional neural network

To

Activation Functions

Sigmoid function and tanh function are commonly used non-linear activation functions, but these functions exist the gradient vanishing, So we use the ReLU function (Rectified linear unit) which is defined as equation ( 5). 0 () 0 0

x if x fx if x       (5)
ReLU can effectively alleviate the problem of gradient vanishing, So as to train the deep neural network directly in a supervised manner. The network can get sparse expression after the ReLU function, with the advantage of unilateral suppression.

Fatigue detection based on PERCLOS

After eye area extraction, the next step is to detect driver fatigue based on PERCLOS (percentage of eyelid closure over the pupil over time). PERCLOS is an established parameter to detect the level of drowsiness. Level of drowsiness can be judged based on the PERCLOS threshold value, PERCLOS is a parameter that is used to detect driver fatigue [START_REF] Wierwille | Research on vehicle-based driver status performance monitoring: development, validation, and refinement of algorithms for detection of driver drowsiness[END_REF]. It is calculated as [START_REF] Liu | A practical driver fatigue detection algorithm based on eye state[END_REF].

100% close PERCLOS total n f N  (6)
Let be the number of eye-close frames over a period time.

is the total number of frames over a period time. When the driver is in a state of fatigue, the driver's PERCLOS value will be higher than normal. We set the PERCLOS threshold, when the driver's PERCLOS value is higher than this threshold, then the current driver is considered fatigue.

Experiment and results

VS2013,running on a Win7 system with Intel (R) Core(TM) i7-6700HQ,CPUs (3.40GHz), 32GB memory,GPU NVNID GeForce GTX 1070

Train

In order to overcome the influence of light on image, the training data must contain data for different light intensities to enhance the robustness of the network, as shown in Figure 6. Since we perform eye state recognition, here we use the following two different kinds of data annotation in our training process:

(1) negatives: 36×36 sample area was randomly intercepted near the eye area, regions whose the intersection-over-union (IoU) ratio is less than 0.4 to any ground-truth eyes as shown in Figure 7.

Training results

We select images including eye images of open and closed as positives samples, and randomly crop several patches to collect negatives samples. We select 120000 images as training samples. The eye state recognition rate of the network has an increase in the number of iterations when training the samples, the result is shown in Figure 9. With the increase of the iteration number, the accuracy rate gradually increased, the final accuracy rate between 0.995 to 0.996 fluctuations. In order to test the performance of the network, we collected three sections of video data, respectively, the accuracy rate shown in the Table 1.

Fatigue detection based on PERCLOS

When the driver is in a state of fatigue, the driver's PERCLOS value will be higher than normal, by setting the PERCLOS threshold, when the driver's PERCLOS value is higher than this threshold, then the current driver is considered fatigue. In this paper, the PERCLOS threshold is set to 0.30, when the driver is fatigue, the PERCLOS value is bigger than 0.30, Figure 10 shows PERCLOS result. Figure 11 shows the Sample images of detection results.

Conclusion

In this paper we propose a driver fatigue detection system. This system uses the multitask cascaded convolutional networks to face detection and alignment. And then use another convolution neural network (CNN) for eye state recognition. Finally we calculate the percentage of eyelid closure (PERCLOS) to detect the fatigue. The method of eye state recognition provides high accuracy and can detect the fatigue effectively in real-time. Tests show that the system implementation is successful and the system does indeed infer fatigue reliably.

FatigueFig. 1 .

 1 Fig. 1. Algorithm block diagrams.

Fig. 2 .

 2 Fig. 2. Joint face detection and alignment using multitask cascaded convolutional networks.

  coordinate of the th feature point on the detected face. It has a matrix representation shown as equation[START_REF] Zhang | Driver Fatigue Detection Based on Eye State Recognition[END_REF].

Fig. 4 .

 4 Fig. 4. The extraction result of the eye area.

Fig. 5 .

 5 Fig. 5. Structure of the convolution neural network.

Fig. 6 .

 6 Fig. 6. Different light intensities of Parts of the training samples.

Fig. 7 .

 7 Fig. 7. Negatives training samples. (2) positives: Positive samples are divided into two types, open eyes samples and closed eyes samples, their IoU above 0.6 to a ground truth face, as shown in Figure 8.

Fig. 8 .

 8 Fig. 8. Positives training samples.

Fig. 9 .

 9 Fig. 9. The result of recognition rate.

Fig. 10 .

 10 Fig. 10. The PERCLOS value.

Fig. 11 .

 11 Fig. 11. Driver Fatigue Detection system.

Table 1 .

 1 The test result of eye state. test videos includes 1239 frames of 320 * 240 images, computing the average time-consuming of the method include each module and overall time. Table2is the time-consuming result. The method complies with the requirement of real-time.

	Video	Number of frames	Accuracy
	Test1	243	97.11%
	Test2	239	95.39%
	Test3	249	98.39%
	Test1	243	97.11%
	Test2	239	95.39%
	Through statistical 5

Table 2 .

 2 The test of Time consuming.

	Video	Face detection , align-	State recognition	Total (ms)
		ment and Eye area extrac-	(ms)
		tion (ms)
	Test1	23.41	6.57	34.92
	Test2	24.50	7.10	36.63
	Test3	23.12	7.09	34.76
	Test4	23.42	6.51	34.09
	Test5	22.13	6.98	33.46

Acknowledgments. This research was partially supported by the National Nature Science Foundation of China (No.61461021) and Local Colleges Faculty Construction of Shanghai MSTC (No. 15590501300).


Jinming Wu

Zhong Liu

Guangquan Cheng

Qi Wang

Jincai Huang

Online Shopping Recommendation with Bayesian Probabilistic Matrix Factorization

Keywords: Recommendation system, Bayesian Probabilistic Matrix Factorization, Monte Carlo Markov Chain

Recommendation system plays a crucial role in demand prediction, arousing attention from industry, business, government and academia. Widely employed in recommendation system, matrix factorization can well capture the potential relationships between users, items and latent variables. In this paper, we focus on a specific recommendation task on the large scale opinion-sharing online dataset called Epinions. We carried out recommendation experiments with the Bayesian probabilistic matrix factorization algorithm and the final results showed the superior performance in comparison to six representative recommendation algorithms. Meanwhile, the Bayesian probabilistic matrix factorization was investigated in depth and the potential advantage was explained from the model flexibility in parameters' adjustment. The findings would guide further research on applications of Bayesian probabilistic matrix factorization and inspire more researchers to contribute in this domain.

Introduction

The past several decades have witnessed the great necessity in designing novel recommendation systems, keeping pace with the fast development of information technologies. The increasing popularity of recommendation systems has influenced human life in many aspects. The potential value of recommendation is being excavated in fruitful applications, such as online social voting recommendation on social networks like Facebook, research paper recommendation for accelerating the speed of crucial scientific findings [START_REF] Beel | Research-paper recommender systems: a literature survey[END_REF], multimedia recommendation for satisfying users' interest [START_REF] Lee | Incorporating contextual information and collaborative filtering methods for multimedia recommendation in a mobile environment[END_REF], citation recommendation for sorting relevant papers [START_REF] Liu | Context-Based Collaborative Filtering for Citation Recommendation[END_REF]. Interestingly, these commercial or academic applications have generalized well and at the same time brought us convenience in a personalized way. However, the demand has already confronted difficulties and challenges from both data quality and volume, requiring more novel algorithms or frameworks to deal with. A specific instance in recommendation research lies in that the ratings on items by users tend to be sparse and imbalanced, leading to the cold start phenomenon in the domain. On the other hand, the boom of internet allows the interactive behaviors like rating the goods bought before or feeding back the preferences of items such as foods, movies or music. In China, some famous corporations including Alibaba, Xiecheng Company have perceived the importance of feed-backing comments from customers and there is no doubt that accurate predictions on customers' preferences no matter in the future or later would bring much profits. It is obvious that the potential relationships between the users we take interests in may contribute to the recommendation in some sense and such social information involved in the model forms the representative family of recommendation algorithms as collaborative filtering.

To address these issues, we firstly make a brief survey regarding the probabilistic matrix factorization (PMF) algorithm which is proved to be effective in sparse and imbalanced recommendation dataset with the social information well exploited [START_REF] Fuchs | Multi-criteria Ratings for Recommender Systems: An Empirical Analysis in the Tourism Domain[END_REF]. Distinguished from the traditional methodologies which mainly capture the information from the user-item ratings, we combined the social information with the rating circumstances for the performance promotion in our study and a superior adaptive Bayesian based model was employed in shopping recommendation.

The remainders of paper are arranged as follows. Section2 elaborates the related developments of probabilistic matrix factorization and Bayesian based recommendation system. The experiments on the collected dataset using Bayesian probabilistic matrix factorization are described in section3 with some detailed analysis. Section4 summarizes our work and light the direction in our future research.

Related Work and Employed Methodology

Review on Probabilistic Matrix Factorization

Probabilistic matrix factorization (PMF) is regarded as one of the outstanding algorithms in several recommendation competitions like Netflix Prize, compared to several collaborative filtering methodologies. The essence of the PMF is to make use of the low rank approximation and assume the potential distribution of dataset, overcoming the shortness of matrix factorization model. After both of user and item feature matrix obtained by low-rank approximating the rating matrix, we utilize the feature matrix to complete the potential missing ratings. Such model maintains well prediction accuracies in practice. Due to the advantages of PMF, it has successfully attracted researchers' attention as well as interest. D. Dueck et al. proposed a probabilistic sparse matrix factorization algorithm, which well explained the uncertainty of noise in different extents [START_REF] Dueck | Probabilistic Sparse Matrix Factorization[END_REF]. Based on the matrix factorization ideology, R. Salakhutdinov et al. made assumption that userfeature matrix, item-feature matrix and user-item matrix were Gaussian in prior distribution, and then by modelling the latent variables, the PMF were derived in first time [START_REF] Salakhutdinov | Probabilistic Matrix Factorization[END_REF]. Multiple rating indexes were integrated into a user-item weighted matrix, assuming the latent matrix obeyed the Gaussian distribution and density probabilistic distribution conditionally correlated with user-feature and item-feature matrixes [START_REF] Yang | A survey of collaborative filtering based social recommender systems[END_REF]. Another adaptation on the PMF was SoRec recommendation model [START_REF] Ma | SoRec:social recommendation using probabilistic matrix factorization[END_REF], where user-feature vectors from both PMF model and confidence based matrix factorization model were combined to enhance the performance. Apart from the theoretical research on the PMF, some applications have also driven the interest of adaptation on PMF. Kernel probabilistic matrix factorization [START_REF] Yang | A survey of collaborative filtering based social recommender systems[END_REF][9].

A Brief introduction to the Bayesian Probabilistic Matrix Factorization

In this section, we would focus our attention on the mechanism of Bayesian probabilistic matrix factorization (BPMF) algorithm proposed by R Salakhutdinov et al. [START_REF] Salakhutdinov | Bayesian probabilistic matrix factorization using Markov chain Monte Carlo[END_REF] and the essence of the recommendation algorithm would be elaborated.

The PMF is the basic model for the BPMF. Generally speaking, the PMF is a linear probabilistic model for solving recommendation tasks with some plausible information containing N users, M items and N*M rating matrix as R. Missing elements in R are ratings which the user never response to the item. The element r ij in R records the preference score of the user i towards the item j.

We apply the low rank approximation to the rating matrix R and then obtain two matrix in low dimensions as

R ≅ U 𝑇 * 𝑉(1)
Where the D*N matrix U and D*M matrix V are respectively user-feature matrix and item-feature matrix in low rank representations, describing the latent representations of users and items respectively.

The probabilistic graphical model for PMF can be translated in the Fig1. Assuming that the difference between the actual rating r ij and the predicted rating r ij ~ obeys the Gaussian distribution with mean 0 and variance σ, we derive

r ij -𝑈 𝑖 𝑇 𝑉 𝑗 ~𝐺𝑎𝑢𝑠𝑠𝑖𝑎𝑛(0, 𝜎 2 )(2)
By the constant shifting, the distribution of rating r ij can be represented as

r ij ~𝐺𝑎𝑢𝑠𝑠𝑖𝑎𝑛(𝑈 𝑖 𝑇 𝑉 𝑗 , 𝜎 2 )(3)
Meanwhile, the assumption on the prior distribution on both latent user and latent item is the Gaussian distribution as follows:

p(U|σ u 2 ) = Π 𝑖=1 𝑁 𝑁(𝑈 𝑖 |0, 𝜎 𝑈 2 𝐼)(4) p(V|σ V 2 ) = Π 𝑗=1 𝑀 𝑁(𝑉 𝑗 |0, 𝜎 𝑉 2 𝐼)(5)
Based on the Bayesian inference, we can acquire the loss function by minimizing the log of the posterior distribution accompanied with quadratic regularization terms.

E = 1 2 Σ 𝑖=1 𝑁 Σ 𝑗=1 𝑀 𝐼 𝑖𝑗 (𝑟 𝑖𝑗 -𝑈 𝑖 𝑇 𝑉 𝑗 ) 2 + 𝜆 𝑈 2 Σ 𝑖=1 𝑁 ||𝑈 𝑖 || 𝐹𝑟𝑜 2 + 𝜆 𝑉 2 Σ 𝑗=1 𝑀 ||𝑉 𝑗 || 𝐹𝑟𝑜 2 (6)
Where the equations follow

λ U = σ 2 σ U 2 and λ V = 𝜎 2 𝜎 𝑉 2 .
During the past years in the research, the adaptations on the feature dimension D and prior distribution's assignment make great improvements on the capability of PMF's generalization.

For the BPMF, the U and V are assumed to follow the Gaussian distributions instead of constants.

p(U|μ U , Ζ 𝑈 ) = Π 𝑖=1 𝑁 𝑁(𝑈 𝑖 |𝜇 𝑈 , Ζ 𝑈 -1 )(7) p(V|μ V , 𝑍 𝑉 ) = Π 𝑗=1 𝑀 𝑁(𝑉 𝑗 |𝜇 𝑉 , Ζ 𝑉 -1 )(8)
Furthermore, the Wishart distribution W 0 is introduced as the priors for hyperparameters Θ U = {𝜇 𝑈 , Ζ 𝑈 } and Θ V = {𝜇 𝑉 , Ζ 𝑉 }. p(Θ U |𝜇 0 , 𝑣 0 , 𝑊 0 ) = 𝑝(𝜇 𝑈 |Ζ 𝑈 )𝑝(Ζ 𝑈 ) [START_REF] Zhou | Kernelized Probabilistic Matrix Factorization: Exploiting Graphs and Side Information[END_REF] p(Θ V |𝜇 0 , 𝑣 0 , 𝑊 0 ) = 𝑝(𝜇 𝑉 |Ζ 𝑉 )𝑝(Ζ 𝑉 ) [START_REF] Salakhutdinov | Bayesian probabilistic matrix factorization using Markov chain Monte Carlo[END_REF] Where we set v 0 = 𝐷, μ 0 = 0 and W 0 = I D . In the prediction process of BPMF, the rating can be obtained by marginalizing over model parameters and hyper parameters as follows. In our research, the Monte Carlo approximation is utilized for the computation.

p(r ij * |𝑅, 𝜇 0 , 𝑣 0 , 𝑊 0 ) ≈ 1 𝐾 Σ 𝑘=1 𝐾 𝑝(𝑟 𝑖𝑗 * |𝑈 𝑖 𝑘 , 𝑉 𝑗 𝑘 )(12)
Where the samples {𝑈 𝑖 𝑘 , 𝑉 𝑗 𝑘 } are generated from a Markov chain. Detailed information on MCMC's application to the BPMF refers to [START_REF] Salakhutdinov | Bayesian probabilistic matrix factorization using Markov chain Monte Carlo[END_REF].

Experiments and Analysis

Evaluation Metrics and Selected Dataset

In our research, the root means square error (RMSE) is chosen as the evaluation metric. More specifically, for the rating r ij which measures the user i's preference towards the item j and the predicted rating r ij ~ derived by the recommendation system, the RMSE is computed as

RMSE = (Σ i,j∈T (𝑟 𝑖𝑗 -𝑟 𝑖𝑗 ~)2 ) 1 2 /|𝑇|(13)
Due to the severe penalty on inaccurate predictions using square error in RMSE, the evaluation metric is regarded as a strict but reasonable criteria. The dataset in our experiments is from the electronic business website as Epions (www.Epinions.com). The ratings reflecting the preference of users towards items are collected, processed and prepared in user-item matrix. Another crucial information matrix describes the friend relationship between users is also provided in Table1. In comparison to the commonly used dataset like Movielens and IMBD, the Epnions behaves rather sparse in social relationships.

Results and Analysis

To verify the effectiveness of the BPMF, we selected some frequently used popular algorithms which were believed to perform well in several recommendation tasks as baselines. Specifically, they were SVD [START_REF] Kim | Using Web Usage Mining and SVD to Improve E-commerce Recommendation Quality[END_REF], NMF [START_REF] Luo | An Efficient Non-Negative Matrix-Factorization-Based Approach to Collaborative Filtering for Recommender Systems[END_REF], BaselineOnly [START_REF] Koren | Factor in the neighbors: Scalable and accurate collaborative filtering[END_REF], Slop-erOne [START_REF] Sun | SlopeOne Collaborative Filtering Recommendation Algorithm Based on Dynamic k-Nearest-Neighborhood[END_REF], KNNBaseline [START_REF] Koren | Factor in the neighbors: Scalable and accurate collaborative filtering[END_REF] and CoClustering [START_REF] George | A scalable collaborative filtering framework based on co-clustering[END_REF]. In the experiments, both of the parameters λ U and λ V were set as 0.002 and the turns of iteration was 200. Some other parameters were selected as the default. Aiming at determining the optimal feature dimension D, we ranged the parameter from 5 to 20 at the step width 5 and the 5-fold cross validation was performed in final selection. The results were arrange in the Ta-ble2. From the table, we can notice that the value of RMSE decreased steadily in the small interval while such metric fluctuated severely when D was over 15. So 15 was chosen as the optimal value for the feature dimension.

A persuasive metric is the k-fold evaluation to average the testing results, in which the k-1 folds are prepared for model fitting with the last fold for testing and such manipulation is performed k times in one turn by ranging all of k-1 folds.

Furthermore, we carried out experiments using the above-mentioned seven algorithms in 10 independent turns and provided the results in average. The fold partition ranged from 1 to 5 with the step width 1. The Table3 recorded the averaged RMSE in ten turns using various algorithms in different folds and it revealed the superior performance of BPMF with the lowest RMSE. To further validate the outstanding performance of BPMF in statistics, the paired ttest was introduced to test the results of 10 independent turns with seven algorithms in the case when the 5-fold RMSE was chosen as the metric. Specifically, the 10 results in each turn obtained by BPMF were compared with those derived by NFM, SVD, BaselineOnly, SlopeOne, KNNBaseline and Coclustering respectively with the help of SPSS. The testing results indicated the BPMF outperformed others significantly. And the compared results were mapped into three element tuple as win\tie\loss. Then the counts of win\tie\loss in 10 turns with some baseline algorithm were summarized in the Table4 as follows. The potential reason for obtaining satisfying results using BPMF was that the Bayesian framework was more flexible in searching optimal hyper parameters and the model maintained high complexity to fit the dataset of high volume.

Conclusions

In the end, the Bayesian probabilistic matrix factorization was employed in online item recommendation backgrounded in the opinion-sharing platform. The BPMF showed its superiority in recommendation task, deriving the lowest RMSE in comparison to six representative algorithms. The conclusions were supported by the paired t-test in ten independent experiments and the persuasive results motivated us to research in depth in other applications. In the future, we would design more variant matrix factorization algorithms incorporating the other social information to promote the performance in recommendations.

Fig. 1 .

 1 Fig. 1. The probabilistic graphical model of PMF

  p(r ij * |𝑅, 𝜇 0 , 𝑣 0 , 𝑊 0 ) = ∫ ∫ 𝑝(𝑟 𝑖𝑗 * |𝑈 𝑖 , 𝑉 𝑗 )𝑝(𝑈, 𝑉|𝑅, 𝜇 𝑈 , Ζ 𝑈 , 𝜇 𝑉 , Ζ 𝑉 )𝑝(𝜇 𝑈 , Ζ 𝑈 , 𝜇 𝑉 , Ζ 𝑉 |𝜇 0 , 𝑣 0 , 𝑊 0 )𝑑{𝜇 𝑈 , Ζ 𝑈 , 𝜇 𝑉 , Ζ 𝑉 }(11)

Table 1 .

 1 Related information about Epinions

	Total	Total	Density of	Density of	Aver-	Aver-
	Users	Items	Ratings	User Relation-	aged	aged
				ships	Ratings	Friends
					on Items
	49289	139738	664824	487183	4.76	9.88
			(0.0097%)	(0.0201%)

Table 2 .

 2 The RMSE in different D value

	D	5	10	15	20
	BPMF	1.2232	1.1678	0.9978	1.4471

Table 3 .

 3 Averaged k-fold RMSE in different algorithms

		Fold 1	Fold 2	Fold 3	Fold 4	Fold 5
	NMF	1.1168	1.1186	1.1173	1.1153	1.1151
	SVD	1.0914	1.0941	1.0969	1.0926	1.0935
	Base-	1.1084	1.1086	1.108	1.1094	1.1091
	lineOnly
	SlopeOne	1.1062	1.1061	1.1067	1.1082	1.1057
	KNNBase-	1.0963	1.0942	1.0967	1.0936	1.0933
	line
	CoCluster-	1.1155	1.1169	1.1163	1.1142	1.1128
	ing
	BPMF	0.9959	0.9955	0.9951	0.9952	0.9954

Table 4 .

 4 Win\Tie\Loss Statistical Results in Comparison Experiments

		NM	SV	Base-	Slope	KNNBase	CoClus
	F	D		lineOnly	One	line	tering
	BPM	9\1\0	8\1\	10\0\	9\0\1	8\2\0	10\0\0
	F		1	0


Zhigang Lian
email: lianzg@sdju.edu.cn

Lihua Lu
email: lulihua@sdju.edu.cn

Yangquan Chen

A New Cuckoo Search

Keywords: Cuckoo search, Lévy distribution, Particle swarm optimization

In this paper, we intend to formulate a new Cuckoo Search (NC-S) for solving optimization problems. This algorithm is based on the obligate brood parasitic behavior of some cuckoo species in combination with the Lévy flight behavior of some birds and fruit flies, at the same time, combine particle swarm optimization (PSO), evolutionary computation technique. It is tested with a set of benchmark continuous functions and compared their optimization results, and we validate the proposed NCS against test functions with big size and then compare its performance with those of PSO and original Cuckoo search. Finally, we discuss the implication of the results and suggestion for further research.

Introduction

In factual production and management, there are many complicated optimization problems. So many scientists have constantly proposed the new intelligent algorithms to solve them. For example, PSO was inspired by fish and bird swarm intelligence [START_REF] Eberhart | A New Optimizer Using Particle Swarm Theory[END_REF] [START_REF] Kennedy | Particle Swarm Optimization[END_REF]. These nature-inspired metaheuristic algorithms have been used in a wide range of optimization problems including NP-hard problems such as the travelling salesman problem (TSP) and scheduling problems [START_REF] Zhigang | A Discrete Particle Swarm Optimization Algorithm for Job-Shop Scheduling Problem to Maximizing production[END_REF] [START_REF] Zhigang | A United Search Particle Swarm Optimization Algorithm for Multi-Objective Scheduling Problem[END_REF]. Based on the interesting breeding behavior such as brood parasitism of certain species of cuckoos, Yang and Deb [START_REF] Yang | Cuckoo search via Lvy flights[END_REF] has formulated the Cuckoo Search (CS) algorithm. Yang and Deb in [START_REF] Yang | Suash Deb: Cuckoo search: recent advances and applications[END_REF] review the fundamental ideas of CS and the latest developments as well as its applications. They analyze the algorithm, gain insight into its search mechanisms and find out why it is efficient.

In this paper, we intend to formulate a new Cuckoo Search (NCS) with different evolution mode, for solving function optimization problems. The NCS is based on the obligate brood parasitic behavior of some cuckoo species in combination with the Lévy flight behavior of some birds and fruit flies. Moreover it integrates the PSO with some evolutionary computation technique. The PSO has particularly gained prominence due to its relative ease of operation and capability to quickly arrive at an optimal/near-optimal solution. This algorithm is considered with the advantages of CS and PSO, avoid tendency to get stuck in a near optimal solution in reaching optimum solutions especially for middle or large size optimization problems. This work differs from existing ones at least in three aspects:

it proposes the iterative formula of NCS, in which combines the iterative equations of CS and PSO. it finds the best combine parameters of NCS for different size optimization problems.

by strictly analyzes the performance of NCS, we validate it against test functions and then compare its performance with those of PSO and CS with different random coefficient generate.

Finally, we discuss the implication of the results and suggestion for further research.

The new CS

The model of new CS algorithm

Yang [START_REF] Yang | Cuckoo Search and Firefly Algorithm: Overview and Analysis. Cuckoo Search and Firefly Algorithm[END_REF] provides an overview of CS and firefly algorithm as well as their latest developments and applications. In this paper, we research on different random distribution number and their influence for algorithm. Furthermore, we also present a new CS with evolutionary pattern. A New Cuckoo Search (NCS) combining CS and PSO is presented in this paper, in which is based on the obligate brood parasitic behavior of some cuckoo species and considered with the Lévy flight behavior of some birds and fruit flies. In the process of evolution, nests/particles/solutions of next generation share the historical and global best of the ith nests/particles/solutions. NCS improves upon the PSO and CS variation to increase accuracy of solution without sacrificing the speed of search solution significantly, and its detailed information will be given in following.

Suppose that the searching space is D-dimensional and m nests/particles/solutions form the colony. The ith nest/particle represents a D-dimensional vector X i = (x i1 , x i2 , . . . , x iD ), (i = 1, 2, . . . , m), and it means that the ith nest/particle located at X i in the searching is a potential solution. Calculate the nest/particle/solution fitness by putting it into a designated objective function. The historical best of the ith nests/particles/solutions denotes as P i = (p i1 , p i2 , . . . , p iD ), called IBest, and the best of the global as P g = (p 1 , p 2 , . . . , p D ), called GBest respectively. At the same time, some of the new nest/particle/solution should be generated combining Lévy walk around the best solution obtained so far. It will speed up the local search.

After finding above two best values, and with Lévy flight the nests/particles/solutions of NCS updates as formulas [START_REF] Eberhart | A New Optimizer Using Particle Swarm Theory[END_REF].

X (t+1) i = X (t) i +α⊕δ * L ′ evy(λ)+(1-δ)(R 1 (P (t) i -X (t) i )+R 2 (P (t) g -X (t) i )); (1)
In [START_REF] Eberhart | A New Optimizer Using Particle Swarm Theory[END_REF], Lévy is same as (??) and its step size follows a random walk Lévy distribution. A part from distant random position solution is far from the optimal solution, so it can make sure that the system does not fall into local optimal solution. Where the δ ∈ [0, 1] is weight index that is chosen according to different optimization problem. It reflects relatively important degree of the t generation Lévy fly, the best nests/particles/solutions of individual historical P (t) i and the best nest/particle/solution of global P (t) g . In addition, the NCS evolution process, the global best nest/particle/solution P (t) g may in K% forced preserved, K ∈ (0, 100). Others parameters such as α and R 1 , R 2 ∈ (0, 1) are same as the ones in [START_REF] Kennedy | Particle Swarm Optimization[END_REF].

The search is a repeated process, and the stop criteria are that the maximum iteration number is reached or the minimum error condition is satisfied. The stop condition depends on the problem to be optimized. In the NCS evolution process, the nests/particles/solutions will be mainly updated through the three parts:

-Lévy walk; the distance between the best nests/particles/solutions of individual historical

P (t) i
and its current nests/particles/solutions; the distance between the best nest/particle/solution of individual historical

P (t) i
and its current nest/particle/solution There are some significant differences of NCS, CS and PSO. Firstly, their iterative equations are not the same. The NCS integrates the advantages of CS and P-SO algorithm, which share the excellent information of nests/particles/solutions. It uses some sort of elitism and/or selection which is similar to the ones used in harmony search (HS). Secondly, the randomization is more efficient as the step length is heavy-tailed, and any large step is possible. Thirdly, the parameter δ is to be turned and easy to find the highest efficiency parameters which are adapted to a wider class of optimization problems. In addition, the NCS can thus be extended to the type of meta-population algorithm.

Pseudo code of the NCS Algorithm

3 Numerical simulation

Test functions

To proof-test the effectiveness of NCS for optimization problems, 14 representative benchmark functions with different dimensions are employed to compare with CS and PSO described in Table 1, where the f 10 is given as formula [START_REF] Kennedy | Particle Swarm Optimization[END_REF]. Griewank : f 8 (x); Generalized P enalized : f 9 (x); f 10 (x)

f 10 (x) =0.1{(sin(πy 1 )) 2 + n-1 ∑ i=1 (y i -1) 2 × [1 + 10(sin(πy i+1 )) 2 ] + (y n -1) 2 } + n ∑ i=1 u(x i , 10, 100, 4) (2
β = 3/2; 16: σ = (gamma(1 + β) * sin(π * β/2)/(gamma(1 + β)/2) * β * 2 ((β-1)/2))) (1/β) ; 17: µ = randn() * σ, υ = randn(); 18: step = µ./abs(ϱ). (1/beta) ; 19: stepsize = 0.01 * step. * (X (t) i -P (t) g ); 20: X (t+1) i = X (t) i + δ * stepsize. * randn() + (1 -δ) * (randn() * (P (t) g -X (t) i ))
Axis parallel hyper -ellipsoid : f 11 (x); Sum of dif f erent power : f 12 (x); M ichalewicz : f 13 (x);

Schaf f er f 7 : f 14 (x);

where

u(x i , a, k, m) =      k(x i -a) m , x i > a 0, -a ≤ x i ≤ a, y i = 1 + 1 4 (x i + 1), x i ∈ [-50, 50] k(-x i -a) m , x i < -a (3)

Experimental results and comparison used against test function with big size

To more scientifically evaluate the proposed algorithm, we run the algorithm 32 times and compare their minimum values, mean values and standard deviations searched by NCS, CS and PSO. For each test function, the parameters and results used in experiments are listed in table 2. The better solutions and corresponding parameters found in NCS algorithm are illustrated with bold letters. The best minimum average and standard deviation are shown in italic and underline respectively.

From table 2, in general it can observe that the δ ∈ [0.5, 0.8] has the highest performance since using them have smaller minimum and arithmetic mean in relation to solutions obtained by others. Especially the δ ≈ 0.5 has better search efficiency. In NCS, to optimize different problem should select various parameter δ, as a whole, it is better when δ ≈ 0.5. The CS optimization function f 4 and f 12 is almost divergence. The NCS in all kinds of function optimization show excellent performance. In above function tests, the minimum value of NCS searched is NS and PSO searched 1/1000, or even 1/10000. Especially for large size problem, and function argument value in large range, optimal is strong search ability. NCS From simulation results we can obtain that the NCS is clearly better than PSO and CS for continuous non-linear function optimization problem. The NCS algorithm searches performance is strong, which can get better the minimum, mean and standard deviation relatively, but it computes more part (1 -δ) * (randn() * (P

(t) i -X (t) i ) + randn() * (P (t) g -X (t) i ))
, therefore more cost of hardware resources, although each running use a little more time, which is negligible. The convergence figures of most effective, distribution figures of run 32 times to search the optimal value of NCS comparing with PSO and CS for 14 instances are shown in Figure 1 Figure 4.

From Figure 1 Figure 4, it can discover that the convergence rate of NCS is clearly faster than the PSO and CS on every benchmark function. Especially it is more efficacious than PSO for middle and large size optimization problem. Accordingly, we can do state that the NCS is more effective than PSO and CS.

Conclusions and perspectives

According to shortcoming of CS and PSO algorithm especially solving the middle or large size problem, we proposed NCS. Using 14 representative instances with different dimensions and compared with the PSO and CS, the performance of the NCS shows that is efficacious for solving optimization problems.

The proposed NCS algorithm can be considered as effective mechanisms from this point of view. There are a number of research directions which can be regarded as useful extensions of this research. Although this algorithm is tested with 14 representative instances, a more comprehensive computational study should be made to measure it. In the future it is maybe do experiments with different parameters and evaluate the performance of NCS. Furthermore, it finds the best parameters and usage scenarios such as TSP, scheduling, etc.

Fig. 1 .Fig. 2 .Fig. 3 .Fig. 4 .

 1234 Fig. 1. Convergence figure of NCS comparing with PSO and CS for f1 -f4.

)

  Algorithm 1 Pseudo code of NCS: Part 1

	Require:
	1: nests/particles/solutions population size: PS;
	2: maximum of generation Endgen;
	3: weight index δ;
	4: forced preserved percent;
	5: step size α;
	Ensure: optimization results;
	6: procedure
	7:	Generate stochastically PS size initial population;
	8:	Evaluate each nest/particle/solutions fitness/quality;
	9:	Generate initial global best population P g (t)	with the lowest fitness
		nest/particle/solution in the whole population;
	10:	Generate randomly initial individual historical best population P i ; (t)
	11:	t:=0;
	12:	while (t ¡ Endge) or (stop criterion) do
	13:	t:=t+1;
	14:	Generate next nests/particle/solutions by equations (1);
	15:

Table 1 .

 1 Benchmark functions

	;

Table 2 .

 2 The comparison results of the PSO,CS[START_REF] Yang | Suash Deb: Cuckoo search: recent advances and applications[END_REF]and the NCS algorithm In table 2, the parameters of Fun and Dim denote function and its dimension respectively. The Best is this functions optimum value. The PS and EG indicate algorithm population size and their terminate generation number.

	F un = f 1		δ	Min/Average/Std	F un = f 2		δ	Min/Average/Std
	Dim=100 Best=0	NCS	0.2 0.5	0.0407/5.3738/6.1344 4.1881/4.1752/4.1881	Dim=50 Best=0	NCS	0.2 0.5	5.5837/136.355/104.5021 2.2119/112.231/103.8505
	PS=200		0.8	0.0161/3.2514/2.9194	PS=200		0.8	3.3954/109.8777/116.003
	EG=2000	PSO	4.2734e+4/6.4205e+4/1.7802e+4 EG=2000	PSO	8.0679e+3/1.837e+4/5.6383e+3
		CS	1.4453e+3/ 1.9655e+3/311.6468		CS	9.8117e+3/1.1428e+4/938.2576
	F un = f 3		δ	Min/Average/Std	F un = f 4		δ	Min/Average/Std
	Dim=50 Best=0	NCS	0.2 0.5	0.041/0.2531/0.14356.1344 0.0439/0.2491/0.1356	Dim=50 Best=0	NCS	0.2 0.5	3.3818/173.9222/140.0647 22.6772/148.6759/88.6797
	PS=200		0.8	0.0678/0.2543/0.106	PS=200		0.8	6.7335/147.4183/81.444
	EG=2000	PSO	2.8602e+3/1.7809e+4/7.2644e+3 EG=2000	PSO	9.4946e+3/1.8978e+4/7.0683e+3
		CS	18.5934/20.3249/1.2497		CS	1.0000e+10/1.0000e+10/0
	F un = f 5		δ	Min/Average/Std	F un = f 6		δ	Min/Average/Std
	Dim=30 Best=-12569.5	NCS	0.2 0.5	-12569.5/-12565.5/4.8859 -12569.5/-12567/2.7239	Dim=50 Best=0	NCS	0.2 0.5	0.0394/1.1456/1.0407 0.0244/0.9167/0.7278
	PS=200		0.8	-12569.5/-12566/4.0731	PS=200		0.8	0.0204/1.1315/0.9799
	EG=2000	PSO	0/1.2656e+4/4.9802e+4	EG=2000	PSO	1.0071e+5/1.0272e+5/1.1186e+3
		CS	-9.5134e+3/-8.9445e+3/199.3234		CS	166.4727/203.5985/16.2855
	F un = f 7		δ	Min/Average/Std	F un = f 8		δ	Min/Average/Std
	Dim=100 Best=0	NCS	0.2 0.5	2.5087/51.0446/29.1489 0.0328/0.4947/0.3140	Dim=100 Best=0	NCS	0.2 0.5	0.0944/0.7814/0.3262 0.2225/0.8737/0.2328
	PS=200		0.8	0.0437/0.4701/0.3093	PS=200		0.8	0.0777/0.8240/0.2938
	EG=2000	PSO	6.6817e+4/8.8147e+4/9.6893e+3 EG=2000	PSO	4.3883e+4/1.0700e+6/5.1800e+5
		CS	13.0822/16.9746/1.3364		CS	9.1896/11.6123/1.2995
	F un = f 9		δ	Min/Average/Std	F un = f 10		δ	Min/Average/Std
	Dim=100 Best=0	NCS	0.2 0.5	4.9369e-5/0.0045/0.0038 1.0745e-4/0.0034/4.9369e-5	Dim=100 Best=0	NCS	0.2 0.5	2.1331e-4/0.0084/0.0061 9.1625e-4/0.0075/0.006
	PS=200		0.8	2.5771e-5/0.0034/0.0037	PS=200		0.8	1.8272e-5/0.0119/0.0156
	EG=2000	PSO	2.391e+4/5.0278e+4/1.5785e+4 EG=2000	PSO	1.1415e+4/5.3205e+4/1.6434e+4
		CS	8.3128/10.159/0.8293		CS	24.833/31.9707/3.7447
	F un = f 11		δ	Min/Average/Std	F un = f 12		δ	Min/Average/Std
	Dim=100 Best=0	NCS	0.2 0.5	0.0129/0.6487/0.8072 0.0057/0.4278/0.3422	Dim=100 Best=0	NCS	0.2 0.5	1.7951e-4/0.0069 /0.0077 6.4493e-5/0.0069/0.0114
	PS=200		0.8	0.0176/0.5174/0.4947	PS=200		0.8	1.4869e-5/0.0064/0.0064
	EG=2000	PSO	2.1285e+5/2.1521e+5/1.7257e+3 EG=2000	PSO	1.6815e+4/4.8188e+4/1.6373e+4
		CS	57.2611/80.8869/10.0869		CS	1.0000e+10/1.0000e+10/0
	F un = f 13		δ	Min/Average/Std	F un = f 14		δ	Min/Average/Std
	Dim=100 Best=?	NCS	0.2 0.5	-39.6594/-35.0528/1.7772 -39.3823/-35.7054/1.9454	Dim=100 Best=0	NCS	0.2 0.5	0.0014/0.098/0.0852 6.1878e-4/0.1044/0.0954
	PS=200		0.8	-39.5466/-35.3446/1.8935	PS=200		0.8	0.0012/0.0822/0.0723
	EG=2000	PSO	2.2069e+5/2.2175e+5/493.2826	EG=2000	PSO	3.7512e+4/7.1659e+4/1.6774e+4
		CS	-34.8234l/-32.8746/0.9454		CS	168.0519/199.9071/9.6655

In CS, the pα=0.25, and in NCS the pα =0.25 and k = 10%(e ∼ n is × 10 n )

Acknowledgements

This work is supported by Academic Discipline Project of Shanghai Dianji University (Number: 16YSXK04) the Shanghai Natural Science Foundation (Number: 14ZR1417300).