Problem In The Domain Of Renal Transplantation Biology Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

The aim of this thesis is to address an acute problem in the domain of renal transplantation. Kidney transplants are by a long way the most general transplant. Regrettably, the demand for kidneys far exceeds supply. In United States of America in 2005, 4,052 people died waiting for a life-saving kidney transplant. During this time, almost 30,000 people were added to the national waiting list, while only 9913 people left the list after receiving a deceased donor kidney [1]. The waiting list currently has over 80,000 people, and the mean waiting time ranges from 2 to 5 years, depending on blood type. Every year, a large number of patients waiting for a kidney transplant, die. As this problem gets worse, it is upon us that we devise smarter and more efficient ways of making kidney transplants happen and sustain. The need of the day is to come up with a way to facilitate quicker and successful kidney transplants. A rational answer to satisfy this would be to develop algorithms that help us speed up the rate of kidney transplants; and also ensure that these transplants give optimum or favorable outcomes.

Surveying and coming up with better pairing/matching algorithms for kidney transplant would invariably lead to the development of an enhanced decision making tool for carrying out kidney transplants.

Several recent papers have used simulation and market-clearing algorithms to explore the impact of a national kidney exchange [5, 3, 6, 7]. For example, using Edmond's maximum-matching algorithm [2] shows that "a national pair wise - exchange market (using length-2 cycles only) would result in more transplants, reduced waiting time, and savings of $750 million in health care costs over 5 years. Those results are conservative in two ways. Firstly, the simulated market contained only 4,000 initial patients, with 250 patients added every 3 months. It has been reported to us that the market could be almost double this size. Secondly, the exchanges were restricted to length-2 cycles. Allowing length-3 cycles leads to additional significant gains. This has been demonstrated on kidney exchange markets with 100 patients by using CPLEX to solve an integer-program encoding of the clearing problem [7]." In another prominent study, Gentry and surgeon Segev demonstrated, "that a national matching program for kidney paired donation, also called paired kidney exchange, would ensure the best possible kidney for the greatest number of recipients who have incompatible donors"[4][7].

Existing methods can be profiled as follows:

In the paper by the researchers at Carnegie Mellon University [1], an alternative algorithm (Column generation algorithm) for this problem is suggested that can clear markets with over 10,000 patients (and that same number of willing donors).

There are disadvantages like the online aspect of the problem as well as the limited-information aspect of the problem. They are explained below.

The online aspect: Donors and recipients will be coming into the system over time, and it may not be the best practice to find an instant best match from the existing database; because in the future, there might come along a donor who is a suitable match for the current recipient; while the current donor could be a suitable match for a very critical recipient in the near future.

The limited-information aspect is that, the data provided as input is not entirely accurate: a number of donor-recipient pairs understood to be compatible turn out to be incompatible when more expensive last-minute tests are carried out. For instance, a medical procedure called Virtual Cross-match tells doctors how good a match is, but later on doing a real cross-match, the match sometimes turns out to be incompatible.

Therefore, it would be advantageous to execute an optimization with this in mind, such as outputting a "robust" result to be examined prior to the final match being produced, or to have a contingency plan in the event of failure.

1.3 An Algorithmic Approach to Paired-Kidney Matching

What is needed is to have an algorithm which does not finalize the first match found as the best possible match, an algorithm which considers all possible matches and then after a thorough comparison finds the best match and goes ahead with that.

A pictorial representation of these very words is shown in Fig.1-1 and Fig.1-2.

Figure 1-1: Sub-optimal matching approach

Figure 1-2: Optimal matching approach

1.4 Detailed Explanation of Proposed Approach

A donor-recipient pair comes to a hospital. After doing standard tests, they are deemed incompatible. The pair is advised to join the database maintained for kidney donors and recipients. The goal is to predict the quality of the donor as Good, Average or Bad which would eventually indicate whether the donor is an optimal match for new and existing recipients in the database.

The pair can be entered into the system's databases and then the system can go ahead with finding the recipient of the pair an optimal match for kidney transplant.

This prediction system could be a part of a bigger system that eventually finds a best match for a recipient. Say 'R1' and 'D1' are the recipient and donor and are entered into the 'R dB' (Recipient Database) and 'D dB' (Donor Database) respectively. Similarly R2, R3,...,Rn will be entered into R dB and D2, D3,...,Dn will be entered into D dB.

Additionally, when multiple matches are generated for a recipient, the donor-quality characteristic would aid the process of finding an optimal match. In case of multiple optimal matches it would be wise not to pick 'Good' quality donors and instead save them for future matches. Here it is assumed that 'Good' quality donors could prove to be appropriate matches for recipients with rare characteristics that might come into the system in the future.

To initialize the kidney transplant process, data is obtained from the donor and recipient. However the system makes predictions based on a subset of this data. Based on these attributes, it will try to predict if a new recipient R1 added to the database is likely to generate matches. Once this kidney transplant process or chain has been initialized, the system will demonstrate the cyclic manner in which it functions. The user (doctor) starts looking for a match for a recipient. The system will display all possible matches and after optimally matching and deciding, the user (doctor) clicks on a donor to execute a transplant with. Once this match has been approved, the system will automatically load the corresponding recipient's information as next recipient in the chain and prompt the user (doctor) to generate a match for this recipient.

This can be summarized as follows:

R1  D5

R5  D90

R90  D178

R178  D1000

And so on…

Doctors' judgments say that it would be ideal for the last donor of the chain to be an altruistic donor. An altruistic donor means a person who is willing to donate a kidney and does not have a recipient pair needing a kidney. If this happens, then there will be a complete chain of transplants. But due to the lack of altruistic kidney donors, doctors say that it is still alright for the last donor in the chain to be a 'Good' donor and have a blood group 'O'.

1.5 Organization

The remainder of this document is organized as follows. Chapter 2 discusses data handling aspects of this research. Chapter 3 shows the implementation technique that was applied in building this system. Chapter 4 talks about the various performance enhancement tunings carried out. Chapter 5 gives the details and screenshots of the user interface designed for the developed application. Chapter 6 concludes the work done and throws light on future research related to this research.

Chapter 2

Data Handling

2.1 Data Representation

For developing this system, a donor dataset with 1000 donors as well as a recipient dataset with 1000 recipients was taken. The system was run for matching the entire donor dataset against the entire recipient dataset in order to find out the number of matches each donor generates. For every match generated, the donor got 1 match point. Assessing the match points each donor generated, donors were classified into three 'donor quality' categories viz. 'Good', 'Average' and 'Bad'.

2.2 Reconfiguring Dataset

Fig.2-1 shows that the donor dataset was reconfigured by removing 'gender', 'ethnicity' and 'donor_ID' as these attributes did not play a direct role in classification of donors in this system. The 'match points' attribute was also removed since it has a direct mapping with the classification class i.e. 'donor quality'.

(a)

(b)(Numeric) (Nominal) (Nominal) (Nominal) (Nominal) (Nominal) (Nominal) (Nominal)

Figure 2-1: Reconfiguring data from (a) to (b)

HLA stands for human leukocyte antigen system. Epstein-Barr virus (EBV) and Cytomegalovirus (CMV) are common viruses that cause infectious mononucleosis (IM).

2.3 Using the Attribute-Relation File Format

A file with the extension arff (Attribute-Relation File Format) is nothing but an ASCII text file to facilitate explanation of a listing of instances sharing a set of characteristics. The arff header of the final donor database used is shown as follows:

@relation 'donorDB'

@attribute age numeric

@attribute HLA_A1 {A10,A28,A9,A19}

@attribute HLA_A2 {A10,A9,A19,A28}

@attribute HLA_B1 {B21,B22,B40,B12,B14,B15,B16,B17,B5}

@attribute HLA_B2 {B12,B14,B15,B16,B5,B22,B17,B21,B40}

@attribute HLA_DRB1 {N,Y}

@attribute Center {WA,CA,CO,OH,TX,NY}

@attribute CMV {+,-}

@attribute EBV {+,-}

@attribute bloodGroup {A,AB,B,O}

@attribute donorQuality {Bad,Average,Good}

Chapter 3

Machine Learning - Implementation Technique

In this chapter, key aspects like baseline comparison, error analysis and comparative analysis are discussed in detail.

3.1 Baseline Comparison

Weka is a machine learning suite which will be used for algorithm comparisons, error analyses and performance optimizations. The donor data is split into two parts: training set and development set. The first 750 instances are taken as the training set (donorDB-Train.csv) and the rest 250 instances are considered as a part of development set (donorDB-Dev.csv). The files are then converted into arff format (donorDB-Train.arff) and (donorDB-Dev.arff) to increase compatibility with Weka.

Fig.4 shows performance of donorDB-Train.arff using different algorithms with 10 fold cross validation in Weka's Explorer. Bayes algorithm, Linear classification algorithm (SMO) and Tree based algorithm (J48) were compared to maintain diversity and perform a broad analysis.

Throughout the discussion Kappa statistic is used as the comparison and evaluation parameter. Kappa is a chance-corrected measure of agreement between the classifications and the true classes. It is calculated by taking the agreement expected by chance away from the observed agreement and dividing by the maximum possible agreement. A value greater than 0 means that classifier is doing better than chance. Higher the kappa value, better the quality.

A confusion matrix is a means for visualizing and is used in supervised learning. Columns of the matrix correspond to instances in a predicted class, whereas rows stand for the instances in an actual class. With a confusion matrix it is simple to observe if a system is confusing two classes.

Naive Bayes SMO J48

Kappa value: 0.7075 Kappa value: 0.8669 Kappa value: 0.8871

Figure 3-1: Confusion Matrices for Naïve Bayes, SMO and J48

By analyzing individual Kappa statistic and confusion matrix the following is observed:

None of the algorithms make dramatic errors like classifying a Good donor as Bad and vice versa. This conclusion can be directly mapped from individual confusion matrices generated by Weka's Explorer.

Naïve Bayes shows some bias towards Average and Good donors. This is observed in the confusion matrix where 70 donors are classified as Average instead of Bad and 51 donors are classified as Good instead of Average.

SMO and J48 performed fairly similar on the given data. The kappa statistic is high and the difference between the individual kappas is very small. However, by only observing the individual confusion matrices it cannot be concluded whether or not this difference is significant. So Weka's Experimenter is used to determine statistical significance.

Fig.3-2 shows the significance analyzed using Weka's Experimenter.

Figure 3-2: Experimenter results showing percent correct for J48, SMO and Naïve Bayes

Fig.5 indicates that Naïve Bayes clearly underperforms with percent correct of 83.20 in comparison with J48 with percent correct of 93.47 and SMO with percent correct of 92.27. However, the experimenter does not show any significant difference between performance with SMO and J48. The system would then consider SMO with default Weka settings as its baseline algorithm.

Also it was seen in Weka's Explorer that Naïve Bayes was underperforming with a low kappa value of 0.7075. Linear models like SMO, can find a good split on the data if the split exists. They will find it wherever it is.

Another reason for picking SMO as the baseline is that the system demands iterative learning on the donorDB. Iterative learning algorithms that approximate the solution of support vector machines (SVMs) have two potential advantages. First, they allow for online and active learning. Second, for large datasets, computing the exact SVM solution may be too time consuming and an efficient approximation is preferable. The powerful LaSVM (an online SVM algorithm based on a single pass through the data) iteratively approaches the exact SVM solution using sequential minimal optimization (SMO). It allows for efficient online and active learning.

However, linear functions have two problems:

If linear functions cannot find a good split, the results will be poor.

They cannot learn interactions between attributes.

To account for these shortcomings and analyze any problems that exist in the model, error analysis is performed.

3.2 Horizontal Error Analysis of SMO

To begin with, the confusion matrix of SMO with donorDB-Train.arff is again analyzed. As shown in Fig.3-3, the horizontal analysis says that 20 instances are being misclassified as 'Average' instead of 'Bad' (indicated in first row of confusion matrix) and 19 instances are being misclassified as 'Good' instead of 'Average' (indicated in second row of confusion matrix). Further in the horizontal analysis it is tried to understand what makes the instances different from correctly classified instances of the same class.

Figure 3-3: Confusion matrix showing horizontal error analysis

3.3 Understanding Instance Misclassification in Horizontal Error Analysis

In order to analyze the reasons for wrong classification, the domain knowledge is checked with. Tissue typing is performed during the assessment of a kidney transplant. This involves sampling blood and analyzing it for markers on white blood cells which are used for matching a donor with a probable recipient. HLA-A1, HLA-A2, HLA-B1, HLA-B2 and HLA-DRB1 are usually identified antigens playing a pivotal role in tissue typing.

Epstein-Barr virus (EBV) and Cytomegalovirus (CMV) are common viruses that cause infectious mononucleosis (IM). CMV and EBV presence proves to be an essential factor in transplants as the virus strains multiply genetically in the recipient's body after transplant. EBV/CMV infects around 90% of the world's population and can stick with a human in a latent form following primary infection. Hence, it is preferable to have a donor free from active or passive EBV and CMV strains.

In this process there is an analysis of the features that could have made the wrongly classified instances different from the instances of the class they were classified in. One such feature could be relation between attributes.

The donor characteristics include attributes that are related to each other such as;

HLA-A1 and HLA-A2

HLA A has two parts A1 and A2. If HLA-A1 and HLA-A2 are same, then the donor does not offer any diversity, hence might not be a good match for potential recipients.

HLA-B1 and HLA-B2

Similarly HLA B has two parts B1 and B2. If HLA-B1 and HLA-B2 are same, then the donor does not offer any diversity, hence might not be a good match for potential recipients.

CMV and EBV

If both CMV and EBV are positive then it is highly unlikely for the donor to be a good match for a recipient, except the case where the recipient himself is CMV and EBV positive.

3.4 Visualizing Error in Horizontal Error Analysis

In Fig.3-4, screen shot of Weka's classifier errors visualizer, it is observed that many instances that had same HLA-A1 and HLA-A2 or same HLA-B1 and HLA-B2 or both were usually 'Average' or 'Bad' donors but were misclassified by SMO as 'Good'. It is possible that the mismatch is due to the fact that SMO did not consider the relationship between HLAs.

Figure 3-4: Screen 1, classifier errors visualizer for donorDB-Train.arff with SMO classifier

In Fig.3-5 it is tried to analyze if the relationship between CMV and EBV are captured by SMO. As mentioned earlier, a donor is very unlikely to be good if both CMV and EBV are positive, but as observed in Fig.8, SMO was unable to capture this relation between CMV and EBV.

Figure 3-5: Screen 2, classifier errors visualizer for donorDB-Train.arff with SMO classifier

3.5 Vertical Error Analysis of SMO

Figure 3-6: Confusion matrix showing vertical error analysis

The confusion matrix of SMO with donorDB-Train.arff is further analyzed. As shown in Fig.3-6, the vertical analysis says that 20 instances are being misclassified as 'Average' instead of 'Bad' (indicated in second column of confusion matrix) and 19 instances are being misclassified as 'Good' instead of 'Average' (indicated in third column of confusion matrix).

3.6 Understanding Instance Misclassification in Vertical Error Analysis

In this section, it is tried to understand what makes the instances similar to the instances of the class they were misclassified into.

Table 3.1: Blood group compatibility for organ transplant

BLOOD TYPE COMPATIBILITY

Donor can be type:

If the blood type of the recipient is:

O

O or A or B or AB

A

A or AB

B

B or AB

AB

AB

From Table 3.1 it can be derived that if the donor has blood group 'O' then the donor is very likely to be a good donor.

Since SMO is a good linear classifier, it will classify across blood groups easily. With each function, what is learnt is like a single split in a decision tree. SMO generates a function such as;

F(x) = C0 + C1X1 + C2X2 + C3X3

where,

X1-Xn are attributes

C0...Cn are coefficients / weights

Therefore SMO assigns very high coefficient to attribute Blood Group = 'O' while classifying between 'Good' and 'Average' donors.

This could be one reason that certain donors are always classified as 'Good' ignoring the equally important relationships with CMV, EBV and HLA's. Fig.3-7 confirms this fact.

Figure 3-7: Screen 3, classifier errors visualizer for donorDB-Train.arff with SMO classifier

Therefore, SMO might possibly not be the optimal algorithm for the system to be built around. To make this conclusion more robust, error analysis is performed on the development set.

3.7 Error Analysis of SMO on Development Set

This section describes the error analysis of the donorDB-Dev.arff dataset trained using SMO. The confusion matrix in Fig.3-8 is first observed to find that similar errors are occurring where the algorithm confuses between 'Bad' and 'Average' instances and also 'Good' and 'Average' instances.

Figure 3-8: Confusion matrix for error analysis of SMO on development set

While visualizing classifier errors in Fig.3-9 and Fig.3-10, it is observed that error patterns similar to the ones existing in the training set are being repeated.

Figure 3-9: Screen 1, classifier errors visualizer for donorDB-Dev.arff with SMO classifier

Figure 3-10: Screen 2, classifier errors visualizer for donorDB-Dev.arff with SMO classifier

To sum it up from figures 3-9 and 3-10, the SMO algorithm ignores important relations between CMV, EBV and HLAs and pays major focus on blood group, which leads to misclassification of many instances.

3.8 Comparative Analysis of Tree and Rule based Models

The error analysis done in section 3.7 concluded that a model which is more efficient in considering the relationships between attributes is needed. It is known that Tree and Rule based models are very effective in capturing attribute relationships.

Tree based learning is based on 'divide and conquer'. Decision is based on what will have the biggest overall effect on "purity" at leaf nodes. Rule based learning is based on 'separate-and-conquer'. It considers only one class at a time (usually starting with smallest). It analyzes what separates this class from the default class.

Fig.3-11 shows comparison between one rule based and one tree based algorithm.

JRip (rule based) J48 (tree based)

Kappa value: 0.8283 Kappa value: 0.8871

Figure 3-11: Comparison of confusion matrices for JRip and J48

3.9 Performance of JRip

JRip performed poorer compared to SMO and J48 with respect to Kappa Statistic which is considered as the metric for comparison in the system. This could be because Rule learning is more prone to over-fitting.

Fig.3-12 displays the rules generated by JRip on the given data. One can observe the following:

JRip does a good job considering the relations between EBV and CMV while classifying 'Bad' donors which does lead to correct classifications.

JRip uses default rules for 'Average' donor quality which leads to many misclassifications.

JRip does not consider any other attribute except blood group while classifying 'Good' donors.

JRip does not consider the relationships between HLA attributes.

Figure 3-12: JRip rules generated for donorDB-Train.arff

3.10 Performance of J48

Fig.3-13 is the tree structure constructed by Weka's tree visualizer. This tree structure is studied in order to analyze the performance of J48.

Figure 3-13: J48 tree generated for donorDB-Train.arff

It is noticed that the tree in Fig.3-13 does not consider the relationship between HLA A and HLA B parameters. Hence it does not add much significant value to the classification that was being provided by the baseline SMO.

Fig.3-14 shows a subsection of Fig.16 created from the branch 'O' at the node 'blood group'. This is the rightmost branch of the tree shown in Fig.16. This subsection of the J48 tree indicates that J48 does consider the EBV and CMV attributes in relation to each other while classifying the results. However, EBV and CMV still have low impact while classifying the donor with blood group 'O' as a 'Bad' donor.

Figure 3-14: Subsection of J48 tree generated for donorDB-Train.arff

Fig.3-15 shows that J48's predictions created errors similar to SMO's predictions. Although donor quality was 'Average', J48 classified it as 'Good'.

Figure 3-15: Classifier errors visualizer for donorDB-Train.arff with J48 classifier

3.11 Evaluating Significance of J48, SMO and JRip

In Fig.3-16, Weka's Experimenter's results are analyzed to compare significance of J48, SMO and JRip.

Figure 3-16: Comparing significance of J48, SMO and JRip

Fig.3-16 shows the kappa statistic of the three algorithms. The kappa for J48 is 0.89, kappa for SMO is 0.87 and kappa for JRip is 0.83. JRip has a significantly low kappa value. Therefore, JRip is not a suitable candidate.

Since J48 and SMO did not show any significant difference in their Kappa values, the system's model should be built by fine tuning and comparing J48 and SMO results.

Hence going forward, J48 and SMO are fine-tuned and compared.

Chapter 4

Performance Enhancement: Tuning of J48 and SMO

In this section, characteristics of J48 and SMO such as minimum number of instances per leaf, confidence factor, complexity parameter, kappa value and confusion matrix are being analyzed for enhancing performance.

Algorithm: J48

Base Settings: Performance on entire dataset with default settings

Minimum number of instances per leaf = 2

Confidence factor = 0.25

Performance: Kappa value: 0.8871

Confusion Matrix:

Algorithm: SMO

Base Settings: Performance on entire dataset with default settings

Complexity Parameter = 1.0

Performance: Kappa value = 0.8669

Confusion Matrix:

4.1 Deciding Settings of Variants for J48

In order to enhance the performance of J48 the confidence factor (c) and minimum number of instances per leaf (m) should be varied.

The confidence factor is used for pruning (smaller values incur more pruning).

A pessimistic guess of the actual classification error is taken based on the training data. If a given node is labeled 'positive' and contains 1 positive and 1 negative (incorrectly classified) instance, its error is 50%. The actual error, however, for classifying future instances at this node could be anywhere between 25% and 75% with a confidence factor of 0.25.

The default value of confidence factor for J48 is 0.25. Studies have shown that performance of the classifier on the testing set increased as the confidence factor increased up to about 0.5 after which the classifier exhibited effects of over-training. These effects are seen by a decrease in classification accuracy with a confidence factor above 0.5.

Thus, two values of confidence factor, c=0.25 and c=0.5, are analyzed to determine which provides better performance.

The goal of tree pruning by minimum number of instances per leaf parameter is to remove the instances whose duplicates/similars occur as frequently or less frequently in coming test sets. But the tree is desired to be more complete while considering other attributes that it did not consider before; therefore the minimum number of instances per leaf parameter can be altered from 2 to a lower value.

Thus, two values of minimum number of instances per leaf, m=1 and m=2, are analyzed to determine which provides better performance.

Thus there are the following variations of the algorithm:

Default (A1D) : J48 with c = 0.25 and m = 2

Variation1 (A1V1) : J48 with c = 0.25 and m = 1

Variation2 (A1V2) : J48 with c = 0.50 and m = 2

Variation3 (A1V3) : J48 with c = 0.50 and m = 1

4.2 Optimization for J48

To perform optimization, the data is first divided into five train-test pairs using Unstratified Remove Folds Filter. Unstratified implies unsupervised. This particular filter is used because the train-test pairs should be divided randomly i.e. without finding any logical relation between data.

To estimate tuned performance, on each fold, all of the algorithm versions are tested over training data to find the optimal one for that fold.

Figure 4-1: Weka Experimenter's results for optimization of J48

In Fig.4-1, the rows show kappa statistics for the four variants over five instances of training the donorDB. Since Fig.4-1 showed many cases which were statistically insignificant, other factors such as 'percent correct' were also considered to make the final decision about the optimal setting. In some cases all factors were inconclusive; so the simplest form (which is the default setting) A1D was considered.

Table 4.1 illustrates system performance over training data as generated by Weka's Experimenter.

Table 4.1: Performance of the four J48 variants over each fold of training data

Fold

Train Set

Performance

For

C = 0.25

M = 2

(A1D)

(default)

Train Set

Performance

For

C = 0.25

M = 1

(A1V1)

Train Set

Performance

For

C = 0.50

M = 2

(A1V2)

Train Set

Performance

For

C = 0.50

M = 1

(A1V3)

Optimal

Setting

Test Set

Performance

(From Table.3)

1

0.67

0.68

0.63

0.66

A1V1

0.8075

2

0.87

0.86

0.86

0.86

A1D

0.8794

3

0.91

0.89

0.90

0.89

A1D

0.8087

4

0.85

0.85

0.85

0.85

A1D

0.8553

5

0.87

0.86

0.87

0.85

A1D

0.9330

4.3 Optimization Evaluation for J48

To evaluate performance over testing data, each algorithm variant is trained using training data and the performance is tested on new test data. Table 4.2 illustrates performance of the four variants of J48 on the new test data.

Table 4.2: Performance of the four J48 variants on new test data

Fold

Test Set

Performance

For

C = 0.25

M = 2

(A1D)

(default)

Test Set

Performance

For

C = 0.25

M = 1

(A1V1)

Test Set

Performance

For

C = 0.50

M = 2

(A1V2)

Test Set

Performance

For

C = 0.50

M = 1

(A1V3)

1

0.8300

0.8075

0.8300

0.8670

2

0.8794

0.9034

0.8794

0.8670

3

0.8087

0.8077

0.8066

0.8187

4

0.8553

0.8528

0.8314

0.8199

5

0.9330

0.9330

0.9330

0.9330

Avg.

0.8613

0.8609

0.8561

0.8611

It is observed that the algorithm gives optimal performance over the Testing Data in two folds (highlighted in green) and gives sub-optimal performance for three folds (highlighted in red).

Now the averages across each variation are computed to choose the version of the algorithm that best optimizes the performance. Table 4.2 shows that out of all the four variants of J48, variant A1D has best kappa of 0.8613 shown in column 1. Therefore, going forward, it is chosen for comparison with SMO algorithm.

Algorithm: J48 A1D

Settings: Minimum number of instances per leaf = 2

Confidence factor = 0.25

4.4 Deciding Settings of Variants for SMO

Performance of SMO is analyzed by tuning the complexity parameter (C parameter).

Complexity parameter represents the strictness of classification. Setting a small C parameter increases the strictness of the model leading to crisp classification and making it bigger may lead to under fitting due to broader classification. The complexity parameter is used by SMO to build the 'hyperplane' between any two target classes. It is known that a support vector machine makes a hyperplane or set of hyperplanes in a high or infinite dimensional space, which is useful for classification. Instinctively, a good quality separation is achieved by the hyperplane that has the most distance to the nearest training data points of any class, since larger the margin, the lower the generalization error of the classifier. So C controls how soft the class margins are.

Typical values for C are exponents of 10, for example 0.01, 0.1, 1.0, 10.0, 100.0. The following variations for C parameter are considered to determine if optimal performance can be achieved C = 1.0, C = 10.0 and C = 100.0

Thus there are the following variations of the algorithm:

Default (A2D) : SMO with C = 1.0

Variation1 (A2V1) : SMO with C = 10.0

Variation2 (A2V2) : SMO with C = 100.0

4.5 Optimization for SMO

To perform optimization, five train pairs and five test pairs that were obtained previously using Unstratified Remove Folds Filter are used.

To estimate tuned performance, on each fold, all versions of algorithm are tested over training data to find optimal one for that fold.

Figure 4-2: Weka's Experimenter results for optimization of SMO

In Fig.4-2, the rows show kappa statistics for the three variants over five instances of training the donorDB. Since Fig.4-2 showed many cases which were statistically insignificant, other factors such as 'percent correct' were also considered to make the final decision about the optimal setting. In some cases all factors were inconclusive; so the simplest form that is the default setting A2D was considered.

Table 4.3 shows that A2D (default SMO) gives best performance on training data.

Table 4.3 Performance of the three SMO variants over each fold of training data

Fold

Train Set

Performance

For

C = 1.0

(A2D)

(default)

Train Set

Performance

For

C = 10.0

(A2V1)

Train Set

Performance

For

C = 100.0

(A2V2)

Optimal

Setting

Test Set

Performance

1

0.56

0.44

0.44

A2D

0.8671

2

0.84

0.83

0.84

A2D

0.9274

3

0.90

0.88

0.84

A2D

0.7750

4

0.86

0.85

0.83

A2D

0.9287

5

0.85

0.84

0.80

A2D

0.9221

4.6 Optimization Evaluation for SMO

To Evaluate Performance over testing data each algorithm variant is trained using training data and the performance is tested on new test data.

Table 4.4 illustrates performance of the three variants of SMO on the new test data.

Table 4.4: Performance of the three SMO variants on new test data

Fold

Test Set

Performance

For

C = 1.0

(A2D)

(default)

Test Set

Performance

For

C = 10.0

(A2V1)

Test Set

Performance

For

C = 100.0

(A2V2)

1

0.8671

0.9880

1.0

2

0.9274

0.9158

0.8255

3

0.7750

0.7966

0.8054

4

0.9287

0.9408

0.8963

5

0.9221

0.8853

0.8514

Avg.

0.8841

0.9053

0.8757

Table 4.4 shows that A2D did not give optimal performance on test data with a kappa of 0.8841. A2V1 gave the best performance with a kappa of 0.9053.

It is observed in Table 4.4 that the algorithm gives optimal performance over the Testing Data in two folds (highlighted in green) and gives sub-optimal performance for three folds (highlighted in red).

The averages across each variation are now computed to choose the version of the algorithm that best optimizes the performance. Table 4.4 shows that out of all the three variants of SMO, variant A2V1 has best kappa of 0.9053 shown in column 1. Therefore, going forward, it is chosen for comparison with J48 A1D.

Algorithm: SMO A2V1

Settings: Complexity Parameter = 10.0

4.7 Comparison between J48 A1D, SMO A2V1 and SMO Default

Finally, the performances of the two optimal versions of algorithms are compared to the baseline (SMO default). In other words, the best variant of J48 and the best variant of SMO are being compared to the existing baseline i.e. the default SMO.

Figure 4-3 indicates that Weka's Experimenter results do not show any major significant improvement over SMO (default). But it is still observed that J48 (A1D) has the best kappa. Therefore, it is the best choice.

Figure 4-3: Comparing A2V1 and A1D to SMO default

Even though Weka's Experimenter's results do not show any significant improvement, the results of A1D (J48 default) were slightly better than that of the baseline (SMO default). Also in the error analysis, it was observed that J48 also takes into account factors such as CMV and EBV while performing classification. Presence of CMV and EBV in a donor brings down the donor-quality. This key factor was accounted for by J48 in its classification. Such factors were not considered by SMO or other algorithms.

Thus the final model will be constructed using Decision Tree based learning algorithm - J48 with optimized settings: Minimum number of instances per leaf as 2 and Confidence factor as 0.25.

As a final proof of evaluation, the algorithm will be trained over the training set and tested over the development set.

Note: The development set was never used throughout the optimization process. It was only used once in error analysis to verify the error analysis done for baseline performance. Thus this evaluation might give pessimistic results.

Fig. 4-4 shows the results of J48 A1D. The results are very positive.

The confusion matrix showed that only 2 instances were misclassified as Average instead of Bad and only 5 instances were misclassified as Good instead of Average.

It gave a Kappa of 0.9567.

It classified instances with an accuracy of 97.18%.

Figure 4-4: Final performance of J48.

Chapter 5

System Implementation

This chapter illustrates the complete system developed in Java, based on J48 algorithm. The system is programmed using Java Swings and Core Java and establishes connectivity to SQL database using MySQL server. The system also incorporates Weka's libraries to classify and predict the output.

This system aids the matching between kidney donors and recipients by visually displaying donor blood group and predicted donor-quality.

The goal was to predict the quality of the donor of a pair which would eventually indicate whether the donor could be an optimal kidney match either in the existing donor database or in the future. This was accomplished through machine learning.

Additionally, a system capable of handling donor and recipient pairs and optimizing the matching process by introducing the element of donor quality prediction was implemented.

The system starts the cycle with a new recipient and donor pair being entered into the system's database. Say 'R1' and 'D1' are the recipient and donor and are entered into the 'R dB' and 'D dB' respectively.

Now the system predicts matches for the newly entered recipient. When multiple matches are generated for a recipient, the quality characteristic aids the process of finding an optimal match. In case of multiple optimal matches it would be wise not to pick 'Good' quality donors and instead save them for future matches.

Here the procedural steps of the system are being illustrated with an example showing initial data gathering from donor and recipient, followed by an optimal match being searched for recipient R1002. An optimal match is found with donor D374. Automatically, R374 is selected for matching with an optimal donor. This shows the cyclic manner in which the system works.

Following screen shots give a step by step visualization of the entire system:

STEP 1: Enter new Donor's details.

STEP 2: Click 'New' to fill Recipient's details.

STEP 3: Enter new Recipient's details.

STEP 4: Click on 'Save Data' to save Recipients data.

STEP 5: Recipient ID is generated and auto- populated on donor screen.

STEP 6: Click on 'Save Data' to save donor's data along with paired recipient ID.

STEP 7: Click on 'Generate Match' to generate matches for recipient.

STEP 8: System generates matches for R1002 based on criteria in Appendix A. System displays donor's blood group and also generates 'Predicted donor Quality' based on predictions done using J48 algorithm*.

* Uses J48 default settings and 10 fold cross validation to create model. Code provided in Appendix C.

STEP 9: One can now analyze the matched donors and select a donor (Double click) which is Average or Bad in case of multiple matches.

Reasoning: A good donor could possibly be a good match for another recipient as well.

STEP 10: System loads the data of the selected donor along with his/her paired recipient ID.

STEP 11: One can now continue the cycle and find suitable matches for R374 by clicking on 'Generate Match'.

STEP 12: System generates matches along with the donor quality results. In this way the cyclic loop continues until no matches are found for a particular recipient or the search ends at an altruistic donor *

*An altruistic donor is a donor without a paired recipient.

Chapter 6

Conclusion and Future Work

A prediction system for optimizing paired kidney transplants has been built. Various algorithms were compared on performance metrics such as kappa statistics and correctly classified instances. Decision tree based machine learning algorithm J48 was the clear winner and hence was chosen for implementation in the system. Weka's libraries were integrated with the Java based kidney transplant system, to train the model and predict outcomes based on real-time data. The system performed with an accuracy of 97.18%. These predictions would definitely facilitate paired kidney transplants and optimize outcomes.

Possible future works on this project are given as follows:

To develop an interface for visualizing depth in transplant chains. A good design project could arise out of this aspect. Visualizing these chains would further add to the efficacy in communicating results or interpreted data to doctors and patients alike.

To extend the number of parameters to the classification rationale of the system. Also there could be additions to the values an attribute can have. For example, this system considers values A9, A10, A19 and A28 as acceptable values for the attribute HLA A. There could be more variants of HLA A that the system could accept.

To use this classification system along with other classifying parameters to predict what type of donors generally fall out of transplant chains. This would help doctors in making decisions about individual transplant chains generated.

J48's performance can be visualized as a tree as depicted in Fig.16. A fuzzy decision tree could be made out of this and could open up yet another vista for further research in Fuzzy logic.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.