Genetic algorithm based approach in attribute weighting for a medical data set

Research Article Genetic Algorithm Based Approach in Attribute Weighting for a Medical Data Set Kirsi Varpa, Kati Iltanen, and Martti Juhola Computer Science, School of Information Sciences, University of Tampere, 33014 Tampere, Finland Correspondence should be addressed to Martti Juhola; [email protected]ta.fi Received 28 May 2014; Revised 30 July 2014; Accepted 6 August 2014; Published 3 September 2014 Academic Editor: Martin J. Murphy Copyright © 2014 Kirsi Varpa et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Genetic algorithms have been utilized in many complex optimization and simulation tasks because of their powerful search method. In this research we studied whether the classification performance of the attribute weighted methods based on the nearest neighbour search can be improved when using the genetic algorithm in the evolution of attribute weighting. The attribute weights in the starting population were based on the weights set by the application area experts and machine learning methods instead of random weight setting. The genetic algorithm improved the total classification accuracy and the median true positive rate of the attribute weighted k-nearest neighbour method using neighbour’s class-based attribute weighting. With other methods, the changes after genetic algorithm were moderate. 1. Introduction One of the most commonly used simple classification methods is the nearest neighbour (NN) method that classifies a new case into the class of its nearest neighbour case [1]. The nearest neighbour method is an instance-based learning methodthatsearchesforthemostsimilarcaseofthetestcase fromthetrainingdatabysomedistancemeasure,usuallywith the Euclidean distance. A natural extension to NN is the knearest neighbour (k-NN) method that assigns the majority class of the knearest training cases for the test case [2]. Different refinements and extensions have been proposed for k-NN in order to improve classification results and overcome classification problems, for example, distance-weighting of neighbours [2], extensions using properties of the data set [3], weighting of attributes [2,4,5], and attribute weight optimization with genetic algorithms (GA) [6–11]. Genetic algorithms [12,13]andotherevolutionalgorithms [14,15]havebeenutilizedinvariouscomplexoptimization and simulation problems because of their powerful search and optimization capabilities. A search method of a genetic algorithm is a combination of directed and stochastic search and the search can be done multidirectionally because GA maintains a population of potential solutions from the search space [14]. The basics of the search method of GA underlie in natural selection and genetic inheritance [12]; individualsofthepopulationareusedinthereproductionof new solutions by means of crossover and mutation. Genetic algorithms have been used with various machine learning methods to optimize weighting properties of the method. Since our research is based on the nearest neighbour search applying machine learning methods, we concentrate on related works where GAs have been applied only with the knearest neighbour method. Kelly and Davis [6]combinedthe GA with a weighted k-nearest neighbour (wk-NN) method in the algorithm called GA-WKNN in order to find a single attributeweightvectorthatwouldimprovetheclassification results of the wk-NN. A similar kind of approach was used in [7] where GA was combined with the wk-NN and a parallel processing environment in order to optimize classification of large data sets. In both studies, a set of real-valued weights for attributes to discriminate all classes of data were achieved as aresultafterGAruns.ThestudyofHusseinetal.[8]showed that GA can be applied successfully in setting a real-valued weight set for 1-NN classifier but the improvement of accuracy happened at the expense of increase in processing time. Results showed that GA methods combining the wk-NN outperformed the basic k-NN [6–8]. However, a single set of weightsforallclassesisnotalwaysthebestsolutionbecause attributes have a different effect on classes [11]. Therefore, Hindawi Publishing Corporation Journal of Computational Medicine Volume 2014, Article ID 526801, 11 pages http://dx.doi.org/10.1155/2014/526801 2Journal of Computational Medicine solutions for searching for a weight for each class and attribute have been developed. Lee et al. [9]combinedthe GA-based attribute weighting method with a modified kNN, thus, forming an adaptive feature weighting method A3FW-MNN that used different sets of attribute weights for different classes. Also, Mateos-Garc´ ıa et al. [10]assigned different weights to every attribute depending on each class in their evolutionary algorithm called Label Dependent Feature Weighting (LDFW) algorithm. In this research we studied whether the classification performance of the attribute weighted machine learning methods based on the nearest neighbour search can be improved when using the genetic algorithm in the evolution of attribute weighting based on the experts and machine learning methods when runs were made with a medical data set. This medical data has been our test data in our previous researches [16,17]. 2. Material In this research an otoneurological data set having 951 cases from seven different vertigo diseases (classes) (Table 1)was used. The data was collected over a decade starting from the 1990s in the Department of Otorhinolaryngology at Helsinki University Central Hospital, Finland, where experienced specialists confirmed all the diagnoses. The distribution of the disease classes is imbalanced; over one-third of the cases belong to the Meni` ere’s disease class (36.8%), whereas the smallest disease class benign recurrent vertigo has only 2.1% of the cases. In total, the data includes 176 attributes concerning a patient’s health status: occurring symptoms, medical history, and clinical findings in otoneurologic, audiologic, and imaging tests [18,19]. Clinical testing has not been done to every patient and, therefore, there are several test results that have missing values of the attributes. Attributes with low frequencies of available values were left outside this research. After leaving out the attributes having over 35% missing values, 94 attributes remained to be used in this research: 17 quantitative (integer or real value) and 77 qualitative attributes (of which 54 were binary (yes/no), 20 were ordinal, and 3 were nominal). Genetic algorithm runs were done with the data including missing attribute values. 3. Genetic Algorithm The basic idea of the genetic algorithm is the following: in the beginning, a population of individuals is formed either randomly or with information about the application domain. Traditionally, a binary representation of the individuals has been used but in multidimensional and numerical problems real-valued representation is nowadays used [14]. In each generation, the individuals of the population are evaluated with an objective evaluation function, thus, giving the individual its fitness rate. A selection method is used to find the fittest individuals for a new population. Some individuals of the new population undergo reproduction by means of crossover and mutation. In the crossover, the information of the individuals Table 1: The frequency distribution of vertigo disease classes. Disease name Abbreviation Frequency % 1 Acoustic neurinoma ANE 131 13.8 2 Benign positional vertigo BPV 173 18.2 3Meni ` ere’s disease MEN 350 36.8 4 Sudden deafness SUD 47 4.9 5 Traumatic vertigo TRA 73 7.7 6 Vestibular neuritis VNE 157 16.5 7 Benign recurrent vertigo BRV 20 2.1 Total 951 100 is swapped in their corresponding elements. Mutation alters one or more elements of the individual arbitrarily. Elitism is a commonly applied survivor selection method. It keeps the current fittest individual unchanged in the population so the high-performance individuals are not lost from one generation to the next [20]. The GA can be ended after a fixed number of iterationsor if no further improvement is observed after some number of generations. We utilized the genetic algorithm in the evolution of the attribute weight values. A pseudocode of the used genetic algorithm is given in Pseudocode 1.Apopulationcontained 21 individuals that used real-valued representation instead of binary presentation because the attribute weight values were described with real-valued numbers, not just with 0 and 1. Each individual consisted of seven different attribute weight sets for 94 attributes. The individuals of the starting population were based on the weights set by the experts and machine learning methods. The starting population is defined more accurately in Section 3.1.Thegeneticalgorithmused a roulette-wheel selection in parent selection and a uniform crossover with discrete recombination in offspring creation. The crossover was done in 80.0% probability (𝑝𝑐=0.8)and the crossover points were selected randomly and independently for each gene (a field on an individual). Mutation was done in 1.0% probability (𝑝𝑚=0.01)forthegeneanditwas done also in a uniform manner: a random value was drawn from the range [0,1]whichwassetasanewvalueinthecurrent position. In addition, elitism was used in order to keep thebestindividualwithinthepopulationduringruns.Wedid not want to lose the best performing weight set during the evolution.Ifthenumberoftheindividualswashigherthan 21 in the end of the generation, a survivor selection was used. The individuals were ordered by their classification performance and the individuals with the lowest accuracy were discarded from the population. The genetic algorithm ended after 20 generations or if the best classification accuracy maintained the same during 10 successive generations. Furthermore, if all the individuals were the same in the population, the evaluation ended. The parameters used in the GA runs are described in Table 2. The genetic algorithm runs were done separately with three different machine learning methods used in the population evaluation: with the nearest pattern method of the otoneurological expert system (ONE), with the Journal of Computational Medicine 3 data 𝐷= [𝐶𝑎𝑠𝑒1 . . . 𝐶𝑎𝑠𝑒951]=[[𝑐1,1,...,𝑐1,94] . . . [𝑐951,1,...,𝑐951,94]] population 𝑊𝑒𝑖𝑔ℎ𝑡𝑠= [𝑊𝑒𝑖𝑔ℎ𝑡1 . . . 𝑊𝑒𝑖𝑔ℎ𝑡21]=[[𝑤1,1,1,...,𝑤1,1,94;...;𝑤1,7,1,...,𝑤1,7,94] . . . [𝑤21,1,1,...,𝑤21,1,94;...;𝑤21,7,1,...,𝑤21,7,94]] population size =21 𝑝𝑐=0.8 //Crossover rate 𝑝𝑚=0.01 //Mutation rate divide data 𝐷into 10 equally-sized subsets for cv round =1to10do divide training data D-𝑑𝑐V𝑟𝑜𝑢𝑛𝑑 into train (6 subsets) and test (3 subsets) data initialize methods with train data: cwk-NN and wk-NN OVA: HVDM initialization ONE: fitness value calculation for values of attributes evaluate starting population Weights with test data and ONE/cwk-NN/wk-NN OVA while ending terms of GA are not fulfilled do //Survivor selection: Elitism search for the individual with the highest fitness rate from the population //Parent selection: Roulette-wheel selection with fitness-proportionate selection for each individual in the population do calculate individual’s fitness proportionate rate = individual‘s fitness rate/sum of individuals’ fitness rates calculate individual’s cumulative fitness proportionate rate end for while nr of individuals in the mating pool is smaller than population size do generate a random number rfrom [0,1] search for the jth individual that has smaller cumulative fitness proportionate rate than 𝑟 add the jth individual in the mating pool end while //Crossover: Uniform crossover with discrete recombination for each individual in the mating pool do generate a random number sfrom [0,1] if 𝑠is smaller than 𝑝𝑐then add the individual in the parent pool else add the individual in the new population (offspring is a direct copy of its parent) end if end for while two individuals can be taken from the parent pool do if two individuals are exactly the same then add the first individual into the new population take new individual from the parent pool to use in the crossover end if for each disease class weight set do select the crossover points randomly swap information of two individuals in the corresponding crossover points (create children) end for add children in the new population end while //Mutation: Uniform mutation for each individual in the new population do for each gene of individual do generate a random number 𝑡from [0,1] if 𝑡is smaller than 𝑝𝑚then select a random value Vfrom the range [0,1] set the value vas a new value of the gene end if end for end for Pseudocode 1: Continued. 4Journal of Computational Medicine evaluate children and mutated individuals in the new population with test data and ONE/𝑐𝑤𝑘-NN/𝑤𝑘-NN 𝑂𝑉𝐴 add the elite individual without changes into the new population //Survivor Selection if nr of individuals in the new population is larger than population size then sort cases descending by their fitness rate discard the last cases in order to have correct nr of individuals in the population else if nr of individuals in the new population is smaller than population size then select randomly missing cases from the old population end if end while initialize methods with training data D-𝑑𝑐V𝑟𝑜𝑢𝑛𝑑: cwk-NN and wk-NN OVA: HVDM initialization ONE: fitness value calculation for values of attributes evaluate the individual with the highest fitness rate after GA with testing data 𝑑𝑐V𝑟𝑜𝑢𝑛𝑑 and ONE/cwk-NN/wk-NN OVA end for Pseudocode 1: Pseudocode of the genetic algorithm used in the evolution of the attribute weight values with 10-fold cross-validation. Table2:Parametersusedwiththegeneticalgorithm. Genetic algorithm parameters Crossover rate 0.8 Mutation rate 0.01 Population size 21 Generation 20 (and 100 for ONE) Elitism Yes (1 individual) attribute weighted k-nearest neighbour method using neighbour’s class based attribute weighting (cwk-NN), and with the attribute weighted k-nearest neighbour method using one-versus-all the other (OVA) classifiers (wk-NN OVA). The evaluation methods are defined more accurately in Section 3.2. During the genetic algorithm runs, for each individual in the population its fitness rate was calculated with the method at hand; that is, the individual was evaluated against the method. Within the methods cwk-NN and ONE, the fitness rate for the individual was defined with a total classification accuracy (ACC) and within the wk-NN OVA withatruepositiverate(TPR).Thetotalclassification accuracy was used with the ONE and the cwk-NN because all seven disease classes were classified at the same time whereas the wk-NN OVA concentrated on one disease class (and its weight set) at a time. During GA wk-NN OVA runs, it was more important to find the weight set that separated well the cases of the disease class at hand from the others than to classify the other cases also well. The total classification accuracy showed the percentage of all correctly classified cases within the data set: ACC =100𝑡pos 𝑛cases %,(1) where 𝑡pos wasthetotalnumberofcasescorrectlyclassified within classes and 𝑛cases was the total number of cases used intheclassification.Thetruepositiverateexpressedthepercentage of correctly inferred cases within the class as TPR =100𝑡pos𝑐 𝑛cases𝑐 %,(2) where 𝑡pos𝑐was the number of correctly classified cases in class 𝑐and 𝑛cases𝑐was the number of all cases in class 𝑐.With the cwk-NN and wk-NN OVA methods, the classification performance was calculated from the seven nearest neighbour method (7-NN) results and with the ONE from the first diagnosis suggestion (ONE1). However, for disease class benign recurrent vertigo (BRV) with the wk-NN OVA method it was necessary to use the TPR of three nearest neighbours (3-NN) as the fitness rate because of the small size of the disease class at hand. Otherwise the TPR for classifying BRV would have always been zero. Nonetheless, if there occurred a situation where TPR of 3-NN was zero with all individuals in the starting population, a new population was created randomly and evaluated. Random new population was created at most ten times and if the TPR did not change during 10 runs, GA run was ended. A 10-fold cross-validation (CV) [2]wasusedinevaluating the classification performance of the genetic algorithm. The data was randomly divided into 10 subsets of approximately equal size. The division was made in a stratified manner to ensure that the class distribution of each subset resembled the skewed class distribution of the entire data set. In the beginning, one cross-validation partition (10% of the data) was left aside to test the performance of the found best individual after genetic algorithm run. The nine cross-validation partitions (90%) were used during the training process. In order to calculate the fitness rate for each individual in the population during genetic algorithm runs, the training data was further divided into two parts: six cross-validation parts were used for training and three cross-validation parts were used fortestingthecurrentmachinelearningmethodusedinthe fitness rate calculation. Thus, during the genetic algorithm Journal of Computational Medicine 5 run 60%–30% data division was used. After the genetic algorithm run, the individual having the highest fitness rate was declared as a result of weight combination and it was then tested with the left aside test data subset. The 10-fold crossvalidation was repeated ten times. In total, there were 100 test runs per each evaluation method used in the genetic algorithm. The same cross-validation divisions were used with all the evaluation methods—that is, each method had the same training and testing sets used during the genetic algorithm runs. 3.1. Starting Population. The starting population consisted of 21 individuals. Each individual included seven different attribute weight sets (weights for 94 attributes), one set for each disease class. Instead of selecting the starting individuals at random, we decided to use good “guesses” as a starting point. Therefore, the starting individuals were based on the attribute weights defined by the domain experts (three different weight set versions) and learnt by three machine learning methods (the Scatter method [21–23]andtheweighting method of the instance-based learning algorithm IB4 [24] and its variant IB1w). Based on the weight sets defined by the experts and the machine learning methods, two different modifications were created from weight sets with 50% random mutation, thus having 18 weight sets in total. In addition to these, three totally random weight sets were createdintothestartingpopulation. The weight values were computed with the machine learning methods from the imputed data set, that is, from the data set where the missing values of attributes were substituted with the class-wise modes of the qualitative and the class-wise medians of the quantitative attributes. In total, 10.1% of the values of attributes were missing in the data set. The imputation was done class-wise on the basis of the whole data prior to data division into training and testing sets. The calculation of the weights was repeated 10 times for each CV training set in the Scatter, IB4, and IB1w methods and the mean weights of the 10 repetitions were used in the classification to handle the randomness in these methods. The weights defined by the application area experts were the same for each CV training set. The experts’ weights were based on three different combinations. The first weight set included the original attribute weights defined by a group of experienced otoneurological physicians for the decision support system ONE made in the 1990s [25]. The second and the third weight sets were defined bytwodomainspecialistsduringtheupgradeprocessofthe decision support system in the 2000s [16]. The Scatter method is normally used for attribute importance evaluation [21–23]. It calculates a scatter value for an attribute that expresses the attributes’ power to separate classes in the data set. For attribute weighting purposes, the scatter values were calculated for each attribute in different class versus other classes’ situations. In order to use the scatter values as attribute weights, it was necessary to take inverses of scatter values. The weight calculation method of the IB4 classification method computes attribute weights independently for each class with a simple performance feedback algorithm [24]. The attribute weights of IB4 reflect the relative relevancies of the attributes in the class. The difference between IB4 and its simpler version IB1w is that IB1w saves all processed cases in its class descriptions and does not discard any cases from the class descriptions during runs. Also, the cases with poor classification records are kept in class descriptions with IB1w whereas IB4 discards these cases based on their past performance during classification. More detailed description of the machine learning methods Scatter, IB4, and IB1w and their use in weight formation will be given in the paper [17]. In order to have different weight sets comparable to each other during the genetic algorithm runs, the attribute weights were normalized into range [0,1]. The values of each weight set were divided by the highest weight value occurring in the weight calculation method at issue. 3.2. Evaluation Methods 3.2.1. Nearest Pattern Method of ONE. The first method used within the genetic algorithm to evaluate the performance of the individuals in the population was the inference mechanism of the otoneurological decision support system ONE [26]. Its inference mechanism resembles the nearest neighbourmethodsofpatternrecognition.Insteadofsearchingfor the nearest case from the training set, it searches for the most fitting class for a new case from its knowledge base. IntheknowledgebaseofONE,apatternisgiventoeach class that corresponds to one vertigo disease. The pattern can be considered a profile of a disease as it describes its related symptoms and signs. Each class in the knowledge base is described with a set of attributes with weight values expressing their significance for the class. In addition, a fitness value for each attribute value is given to describe how it fits the class. The fitness values for attribute values were computed on the basis of the 60% part of training data. Fitness values can have valuesbetween0and100.Thefitnessvalue0meansthatthe attribute value does not fit the class, whereas the fitness value 100 shows that the value fits the class perfectly. The weight values for attributes were given in the population in the GA; thus, the weight values varied from 0 to 1. The greater the weight value is, the more important the attribute is for the class. The inference mechanism calculates scores for the classes from the weight and fitness values of the attributes. The score 𝑆(𝑐)for a class 𝑐is calculated in the following way: 𝑆(𝑐)=∑𝐴(𝑐) 𝑎=1 𝑥(𝑎)𝑤(𝑐,𝑎)𝑓(𝑐,𝑎,𝑗) ∑𝐴(𝑐) 𝑎=1 𝑥(𝑎)𝑤(𝑐,𝑎),(3) where 𝐴(𝑐)is the number of the attributes associated with class 𝑐,𝑥(𝑎)is 1 if the value of attribute 𝑎is known and otherwise 0, 𝑤(𝑐,𝑎)is the weight of the attribute 𝑎for class 𝑐,and 𝑓(𝑐,𝑎,𝑗)is the fitness value for the value 𝑗of the attribute 𝑎 for class 𝑐[26].Inthecaseofquantitativeattributes,thefitness values are interpolated by using the attribute values in the knowledge base as interpolation points. The fitness values are altered to the range of 0 to 1 during the inference process. 6Journal of Computational Medicine In addition to the score, the minimum and maximum scores arecalculatedfortheclassesusingthelowestandthehighest fitness values for the attributes having missing values. The classes are ordered primarily by the score and secondarily by the difference of the minimum and maximum score. If the classes have the same score but one class has a smaller difference between the minimum and maximum scores than the others, the class having the smallest difference is placed higher in order. If the classes have the same score and the minimum and maximum score difference, their order is selected randomly. The class having the highest score is referred to as the best diagnosis suggestion. Some vertigo diseases resemble each other by having a similar kind of symptoms with other diseases during some phase of the disease and, in addition, some patients can actually have two (or more) vertigo diseases present concurrently [27]. Therefore, it is good to check the classification results of ONEwithmorethanonediseasesuggestion.Intheend,the final diagnostic choice must be made by the physician based on the information given on all alternative diseases [27]. 3.2.2. Attribute Weighted k-Nearest Neighbour Method Using Neighbour’s Class-Based Attribute Weighting. The other method used in the population evaluation was the attribute weighted k-nearest neighbour method using neighbour’s class-based attribute weighting (cwk-NN). The distance measure of the basic k-nearest neighbour method [1]was expanded to take the attribute weighting into account [6]. Lee et al. [9] used a similar class-dependent attribute weighting with their modified k-nearest neighbour method where different attribute weight sets for different classes were determined with the adaptive-3FW feature weighting method. With our cwk-NN the attribute weighting depends on the disease class of the neighbour case. Thus, there ought to be as many attribute weights sets available as there are classes. The distance measure used with the cwk-NN was the Heterogeneous Value Difference Metric (HVDM) [28] expanded with the attribute weighting. HVDM was used because it can handle both qualitative and quantitative attributes in the data set. The attribute weighted HVDM is defined as weighted HVDM (𝑥,𝑦)=√𝑚 ∑ 𝑎=1 𝑤𝑐𝑎𝑑𝑎(𝑥𝑎,𝑦𝑎)2,(4) where 𝑚isthenumberofattributes,𝑐is the disease class of the case 𝑦,𝑤𝑐𝑎 is the weight of the attribute 𝑎in class 𝑐,and 𝑑𝑎(𝑥𝑎,𝑦𝑎)is the distance between the values 𝑥𝑎and 𝑦𝑎for attribute 𝑎.Thedistancefunction𝑑𝑎(𝑥𝑎,𝑦𝑎)is defined as 𝑑𝑎(𝑥𝑎,𝑦𝑎) ={ { { { {1, if 𝑥or 𝑦is unknown normalized vdm𝑎(𝑥𝑎,𝑦𝑎), if 𝑎is qualitative normalized diff𝑎(𝑥𝑎,𝑦𝑎), otherwise.(5) Because HVDM computes distances to qualitative and other attributes with different measurement ranges, it is necessary toscaletheirresultsintoapproximatelythesamerangein order to give each attribute a similar influence on the overall distance [28]. The normalized distance to a quantitative attribute is calculated with (6): normalized diff𝑎(𝑥𝑎,𝑦𝑎)=󵄨󵄨󵄨󵄨𝑥𝑎−𝑦𝑎󵄨󵄨󵄨󵄨 4𝜎𝑎,(6) where 𝜎𝑎is the standard deviation of the numeric values of attribute 𝑎in the training set of the current classifier, and to a nominal attribute with (7): normalized vdm𝑎(𝑥𝑎,𝑦𝑎)=√𝐶 ∑ 𝑐=1 󵄨󵄨󵄨󵄨󵄨󵄨󵄨󵄨󵄨󵄨𝑁𝑎,𝑥,𝑐 𝑁𝑎,𝑥 −𝑁𝑎,𝑦,𝑐 𝑁𝑎,𝑦 󵄨󵄨󵄨󵄨󵄨󵄨󵄨󵄨󵄨󵄨 2,(7) where 𝐶isthenumberofoutputclassesintheproblem domain (in this case 𝐶=7), 𝑁𝑎,𝑥(𝑦),𝑐 isthenumberofcasesin 𝑇that have a value 𝑥(or a value 𝑦)forattribute𝑎and the output class 𝑐,and𝑁𝑎,𝑥(𝑦) isthenumberofcasesin𝑇that have avalue𝑥(or a value 𝑦)forattribute𝑎[28]. In other words, we are calculating the conditional probabilities to have the output class 𝑐when having attribute 𝑎with the value 𝑥(or the value 𝑦). Thisapproachallowedmodificationsofalltheweightsat thesametime. 3.2.3. Attribute Weighted k-Nearest Neighbour Method Using One-versus-All Classifiers. In addition to the neighbour’s class-based attribute weighting the attribute weighted knearest neighbour method was tested with one-versus-all classifiers (wk-NN OVA). Within this method, the multiclass classification problem was converted into multiple binary classifiers—that is, the 𝑚class problem was divided into 𝑚 binary problems [29]. Each binary OVA classifier was trained to separate a class from all the other classes by marking the casesofthisoneclassasmembercasesandthecasesofthe other classes as nonmember cases in the training set. The attribute weighted k-NN OVA is an instance-based learning method that searches for the kmost similar cases (neighbours) of a new case from each classifier separately. There is one classifier per each class and each classifier gives a vote for the case being a member or nonmember of the class based on the majority class of the kneighbours. The final class of the new case is assigned from a classifier suggesting the case being a member of a class. There can occur a situation in which the new case gets more than one member of a class vote (a tie situation) or all of the classifiers vote for the other class (the case to be a nonmember of all the classes). In a tie situation the class of the new case is determined by searching for the most similar member case from the member voting classifiers. The case gets the class of the member case with the shortest distance to it. When all the classifiers vote for the case to be a nonmember, the basic 1-nearest neighbour classifier using the whole training data containing the original disease classes is employed to find the most similar case (and its class) for the new case. The distance measure used in the wk-NN OVA was also the HVDM measure. The difference in the HVDM description in (4)isthatthe𝑐is the class of the classifier at issue, not Journal of Computational Medicine 7 Table 3: Example evaluation computation time of one population (21 individuals, one generation) in GA runs with different computers. Example one population evaluation time Computer GAONE GAcwk-NN GAwk-NNOVA Specifications C1 3 min 25 s 48 min 54 s 4 h 57 min 8 s W7 Intel Core i7-3540M 3.00 GHz, 16 GB RAM C2 — 49 min 53 s 6 h 59 min 16 s I3-530 2.93 GHz, 12 GB RAM C3 — 3 h 47 min 41 s 9 h 41 min 9 s Q6600 2.4 GHz, 8 GB RAM C4 — 3 h 12 min 41 s 21 h 14 min 0 s HP ProLiant DL580 G7 server: 4∗Intel Xeon X7560 2.26 GHz, 1 TB RAM C5 — 3 h 4 min 58 s 7 h 22 min 52 s DL785 G5 server: 8∗AMD Opteron 8360 SE 2.5 GHz, 512 GB RAM C6 — — 10 h 34 min 55 s Intel Core2 Duo E6750 2.66 GHz, 2 GB RAM Table 4: The ending time of the genetic algorithm runs within different evaluation methods. Genetic algorithm GAONE GAcwk-NN GAwk-NNOVA GAONE100 Ended before 20th generation [%] 75.0 18.0 82.9 39.0∗ Ended on 10th generation [%] 48.0 6.0 54.9 12.0∗ Ended on 20th generation [%] 25.0 82.0 17.1 61.0∗ ∗The ending generations of the GA ONE100 runs was examined before 100th generation, on 50th generation and on 100th generation. the class of the case 𝑦. In addition, in (7)wk-NN OVA has two output classes (𝐶=2). The data in the learning set 𝑇of the classifier is divided into the member and nonmember classes. 4. Results The results of the GA runs with ONE and cwk-NN as an evaluation method were the averages of the 10 times repeated 10-fold cross-validation whereas the results with the wk-NN OVA were the averages of the 5 times repeated 10-fold crossvalidation. The 10-fold cross-validation was repeated only five times with the GA wk-NN OVA due to its huge computation time. For example, the evaluation of a population (21 individuals in one generation in a GA run) in one cross-validation set with the GA ONE lasted 3 minutes and 25 seconds, with the GA cwk-NN 48 minutes and 54 seconds, and with the GA wk-NN OVA 4hours,57minutes,and8secondswhen running the GA with the computer C1 (Table 3). With the other computers, the computation was even slower. Thus, at worst, the computation time of one cross-validation set lasting 20 generations with the computer C1 and GA wk-NN OVA was over four days (over 12 days with C4) assuming that within each generation all individuals were evaluated. In practice, the number of evaluated individuals varied within generations due to the crossover and the mutation. Notice that computers C4 and C5 were servers having several other users simultaneously and, thus, we had only minor part of their CPU in use. During GA cwk-NN and GA wk-NN OVA runs, the GA was run parallel in five computers, thus, having at best 11 parallel GA runs in process. GA ONE was run only with the computer C1. The number of generations in the GA runs with all used evaluation methods varied from 10 to 20. In total, 75.0%, 18.0%, and 82.9% of GA runs ended before the 20th generation due to having the same best accuracy (GA ONE and GA cwk-NN)orTPR(GA wk-NN OVA)in10consecutive GA runs with ONE method, cwk-NN, and wk-NN OVA, respectively (Table 4). With the GA wk-NN OVA,allthe GA runs with the disease classes sudden deafness, traumatic vertigo, and benign recurrent vertigo ended before the 20th generation and with the other classes from 58.0% to 88.0% of the runs. If the number of ending generation was 10, this meant that the best ACC or TPR in the population did not change at all during the GA run and, therefore, the run was ended. GA cwk-NN ended after 10 generations only in 6.0% of the GA runs whereas GA ONE and GA wk-NN OVA ended during the GA runs around half of runs (in 48.0% and 54.9% of runs, resp.). In the GA wk-NN OVA runs, this happened especially with disease class traumatic vertigo where all CV runs ended after 10 generations and with sudden deafness (96.0%) and benign recurrent vertigo (94.0%). The other disease classes ended during the GA wk-NN OVA runs after 10 generations from 12.0% (acoustic neurinoma) to 34.0% (vestibular neuritis) of the runs. Most of the GA cwk-NN runs lasted 20 generations (82.0%) whereas only a fourth of the GA ONE runs and 17.1% of the GA wk-NN OVA runs went through 20 generations. Within the GA wk-NN OVA runs of the disease class benign recurrent vertigo occurred situations where the TPRs in the starting population were zero regardless of using the TPR of 3-NN instead in population evaluation. The TPR of 3-NNwasusedwithBRVinsteadof7-NNbecauseofthe smallsizeofthediseaseclass.TheTPRsofstartingindividuals were zero in 30 out of 50 cross-validation sets within the GA wk-NN OVA run concentrating on the BRV. In this case, new starting individuals were created randomly. Random individual creation was repeated in different cross-validation sets from one to five and nine times. The GA wk-NN OVA run ended if the TPR of starting population stayed zero ten times. This happened in 14 (28.0%) cross-validation sets only with the disease class benign recurrent vertigo. In order to see the effect of genetic algorithm on the population, we examined the worst and the best total classification accuracies of individuals (the attribute weight vectors) in the beginning and in the end of the genetic algorithm run. The meanworstandthemeanbesttotalaccuraciesandtheir standard deviations with GA runs using ONE and cwk-NN as 8Journal of Computational Medicine Table 5: The mean and its standard deviation of the best and worst total classification accuracies of individuals in the starting and ending populations occurring during different GA runs within 10 times (in GA wk-NN OVA 5 times) repeated 10-fold cross-validation. Method Population Best accuracy [%] Worst accuracy [%] Mean Std dev. Mean Std dev. GA ONE (ONE1) start 74.0 0.8 49.8 1.6 end 73.8 0.7 61.4 2.8 end 100 73.9 0.9 66.5 2.0 GA cwk-NN (7-NN) start 63.6 1.6 27.9 2.2 end 68.3 1.9 56.2 2.2 GA wk-NN OVA (7-NN) start 79.2 0.5 75.3 0.5 end 78.6 0.9 78.7 0.8 Table 6: The starting point of the genetic algorithm using ONE inference (GA ONE), the attribute weighted 𝑘-nearest neighbour method with neighbour’s class-based attribute weighting (GA cwk-NN) and with OVA classifiers (GA wk-NN OVA) as evaluation method. The true positive rates (TPR) of seven disease classes and the total classification accuracies of the best individual from the starting population are given in percentages (%) from 10 times (five times with GA wk-NN OVA) repeated 10-fold cross-validation. Disease ANE BPV MEN SUD TRA VNE BRV Median TPR Total accuracy Cases 131 173 350 47 73 157 20 951 GA ONE ONE1 63.5 55.0 91.1 67.4 84.0 67.5 37.0 67.4 74.0 ONE12 76.0 84.7 96.6 97.0 96.3 75.4 69.5 84.7 87.5 ONE123 88.1 94.7 98.1 99.6 99.9 84.6 86.0 94.7 93.8 GA cwk-NN 1-NN 47.6 50.2 75.7 28.7 59.0 55.0 10.5 50.2 58.8 3-NN 48.9 52.5 82.2 24.0 58.9 57.0 9.0 52.5 61.9 5-NN 49.0 54.4 85.1 21.1 57.0 56.5 8.5 54.4 62.9 7-NN 48.9 55.0 86.6 19.6 56.3 57.8 5.5 55.0 63.6 9-NN 49.2 56.0 87.8 16.4 53.4 57.5 3.5 53.4 63.7 GA wk-NN OVA 1-NN 70.4 73.5 85.0 67.2 62.7 78.2 19.0 70.4 75.8 3-NN 71.1 75.8 91.8 73.2 61.1 79.4 18.0 73.2 79.2 5-NN 70.7 75.7 92.8 74.5 62.5 79.5 15.0 74.5 79.6 7-NN 69.9 74.7 93.0 73.2 60.0 80.1 15.0 73.2 79.2 9-NN 68.9 73.2 93.2 71.9 58.1 80.5 16.0 71.9 78.7 an evaluation method were calculated from 10 times repeated 10-fold cross-validation and with GA runs using wk-NN OVA from 5 times repeated 10-fold cross-validation (Table 5). The mean best accuracies stayed approximately the same with the GA ONE,whereasthemeanbestaccuracyincreased4.7% with the GA cwk-NN and decreased 0.6% with the GA wkNN OVA.Theimprovementcanbeseenfromthemeanworst classification accuracies: the worst accuracy occurring in the population increased during GA runs, especially with the GA cwk-NN (28.3%). With the GA ONE, the mean worst accuracy improved 11.6% when using at most 20 generations and 16.7% when using at most 100 generations. With the GA wk-NN OVA, the improvement was moderate (3.4%) but one must notice that its mean worst classification accuracy was already over 75% in the starting population, which was better than the mean best accuracies of the other methods. The more detailed results of the GA ONE,theGA cwk-NN, and the GA wk-NN OVA runs in the beginning and in the end with the best individual occurring in the population are given in Tables 6and 7.Thetruepositiveratesofthediseaseclasses are shown with GA ONE for the first (ONE1), the first and second (ONE12), and the first, second, and third (ONE123) diagnosis suggestions of ONE and with GA cwk-NN and GA wk-NN OVA for one, three, five, seven, and nine nearest neighbours (1-NN–9-NN). During cross-validation runs in GA, the individuals were evaluated by the total classification accuracy of the ONE1 with the GA ONE and of the 7-NN with the GA cwk-NN andbythetruepositiverateofthe7-NNwith the GA wk-NN OVA (except with disease class BRV that used the TPR of 3-NN).The true positive rate was used as a fitness rate with the GA wk-NN OVA instead of the total accuracy because it concentrated on classifying one disease class at a time whereas GA ONE and GA cwk-NN classified all seven disease classes at the same time. Within 20 generations lasting GA, the best improvement between the start population and the end population was yielded with the GA cwk-NN that improved the total classification accuracies and the mean true positive rates when using one to nine nearest neighbours in the classification. Total classification accuracy of the GA cwk-NN rose at best 5.1% Journal of Computational Medicine 9 Table 7: The end result of the genetic algorithm using ONE inference (GA ONE), the attribute weighted 𝑘-nearest neighbour method with neighbour’s class-based attribute weighting (GA cwk-NN) and with OVA classifiers (GA wk-NN OVA)asevaluationmethodinpopulation evaluation after at most 20 generations. The true positive rates (TPR) of seven disease classes and the total classification accuracies of the best individual in the end population are given in percentages (%) from 10 times (five times with GA wk-NN OVA) repeated 10-fold crossvalidation. Disease ANE BPV MEN SUD TRA VNE BRV Median TPR Total accuracy Cases 131 173 350 47 73 157 20 951 GA ONE ONE1 63.5 55.4 90.8 66.2 83.0 68.0 31.5 66.2 73.8 ONE12 77.0 82.7 96.4 93.6 96.2 76.2 62.0 82.7 87.0 ONE123 87.6 92.8 98.0 98.5 99.5 84.4 84.5 92.8 93.2 GA cwk-NN 1-NN 70.2 50.0 68.4 30.6 70.0 60.3 15.0 60.3 61.1 3-NN 70.8 53.9 78.1 27.7 72.5 62.9 14.5 62.9 65.9 5-NN 70.5 56.1 81.5 23.2 71.9 63.8 12.0 63.8 67.4 7-NN 69.5 56.6 84.7 21.1 71.0 63.9 8.5 63.9 68.3 9-NN 69.0 57.5 86.6 18.1 69.7 64.1 6.0 64.1 68.8 GA wk-NN OVA 1-NN 71.5 74.1 84.6 67.2 67.1 77.8 18.0 71.5 76.2 3-NN 71.6 75.3 91.7 74.9 66.8 78.7 16.0 74.9 79.5 5-NN 70.4 73.6 92.2 77.0 63.6 79.2 14.0 73.6 79.1 7-NN 70.4 71.8 92.6 77.0 59.5 79.6 13.0 71.8 78.6 9-NN 70.5 72.4 92.7 74.9 59.7 79.6 13.0 72.4 78.7 (in9-NN)andmedianTPR10.7%(in9-NN).TheGAhada smaller effect on the results of the GA ONE and the GA wkNN OVA. The results in the start population and in the end population stayed quite near each other. Small improvement in the mean total classification accuracy and the mean TPR canbeseenwiththeGA wk-NN OVA using one or three nearest neighbours in the classification. Otherwise, the total classification accuracies decreased a bit when using the GA ONE and with the GA wk-NN OVA using five or seven nearest neighbours in the classification. Changes within the true positive rates of disease classes compared to the start and end results varied between methods. The GA cwk-NN mainly increased the TPRs. During GA runs,itincreasedthemosttheTPRofacousticneurinoma (22.6% in 1-NN) and traumatic vertigo (16.3% in 9-NN). Meni` ere’s disease was the only class where the TPR decreased (at worst −7.3% in 1-NN) during GA cwk-NN runs. With the GA ONE, the TPRs of classes mainly decreased. It decreased themosttheTPRofbenignrecurrentvertigo(−7.5 % in ONE12) and sudden deafness (−3.4% in ONE12). However, smallincreaseinTPRcanbeseenwithacousticneurinoma (1.0% in ONE12) and with vestibular neuritis (0.8% with ONE12). With the GA wk-NN OVA,someTPRsincreasedand some decreased. The TPR increased the most with traumatic vertigo (5.8% in 3-NN) and sudden deafness (3.8% in 7-NN) and decreased the most with benign recurrent vertigo (−3.0% in 9-NN) and benign positional vertigo (−2.9% in 7-NN). Because the computation time with the ONE method was so much faster than with the k-nearest neighbour methods, the evolution of the population with GA ONE runs was tested also with 100 generations in addition to the 20 generations. The ending condition was also changed: the GA run ended if themaximumaccuracystayedthesamein50successiveruns or 100 generations were run. In total, 39.0% of the GA ONE100 Table 8: The end result of the genetic algorithm using ONE inference in population evaluation after at most 100 generations. True positive rates and the total classification accuracies of the best individual in the end populationare given in percentages [%] from 10 times repeated 10-fold cross-validation. Disease Cases GA ONE 100 ONE1 ONE12 ONE123 ANE 131 67.1 79.9 89.6 BPV 173 56.9 82.0 92.8 MEN 350 89.9 96.1 97.9 SUD 47 61.7 90.9 97.0 TRA 73 80.3 96.4 99.7 VNE 157 69.6 78.7 86.0 BRV 20 23.0 53.5 75.0 Median TPR 67.1 82.0 92.8 Total accuracy 951 73.9 87.3 93.5 runs ended before the 100th generation and within 12.0% of therunstherewasnochangeinthebesttotalclassification accuracy during 50 generations (Table 4). The classification results of the GA ONE100 runs are given in Table 8. The increase of generations from 20 to 100 did not affect much the mean total classification accuracy nor the mean median TPR. Within disease classes, benign recurrent vertigo suffered the most from the generation increase: its true positive rate decreased at worst −16.0% (ONE12) compared to the starting population and −9.5% (ONE123) compared to the 20th generation. The best TPR increase was achieved with acoustic neurinoma: 3.9% from the starting population and 3.6% from the 20th generation.