Utilizing LSTM and K-NN for Anatomical Localization of Tuberculosis: A Solution for Incomplete Data

Data mining is the process of extracting, identifying, and analyzing various information to find patterns in data using mathematical techniques, artificial intelligence, statistics, and machine learning. Based on the tasks that can be performed, data mining is grouped into several parts, namely decryption, prediction, estimation, classification, clustering, and association [13]. The term data mining is often referred to as knowledge discovery in database (KDD), the following stages in the data mining process are shown in the Figure 1.

1.jpg

Figure 1. Stages of data mining

In Figure 1, there are several stages of the process of data mining. The first stage is the collection of the dataset that will be used, then continued with the pre-processing stage and the third stage is the data mining process using the existing dataset. Then, the last stage is an evaluation to determine the performance results of the method proposed in this study.

2.1 Data

The diagnosis of TB is carried out by undergoing a bacteriological examination to confirm TB disease. Bacteriological examination refers to the examination of smears from biological preparations (sputum or other specimens), examination of cultures, and identification of Mycobacterium tuberculosis. Currently, the TCM test with Xpert MTB/RIF is the only molecular test that covers all the necessary reaction elements, including all the reagents needed for the PCR (Polymerase Chain Reaction) process.

The features or criteria used for the classification process are explained respectively as follows:

(1) Age, in the form of a numerical feature that contains information about the age of each sample. Based on age group, the older a person is, the higher the risk of developing TB. The older the age, the immune system will also decrease so that it is easy to catch the disease [14].

(2) The sex criterion is a category data feature that contains information on the patient sample's gender. Judging from the analysis, men are also susceptible to TB disease because it is seen from smoking habits that cause TB disease [14].

(3) Chest X-ray, in the form of a category feature that contains information about the results of the chest X-ray test. Positive if TB is found and negative if not found. This is done to ensure the coexistence of pulmonary TB [15].

(4) HIV status, in the form of a category feature that contains information about the HIV status of each patient. Positive if you have HIV and negative if you don't. Tuberculosis in HIV/AIDS (TB-HIV) patients is often found with a prevalence of 29-37 times more than TB without HIV [8].

(5) Diabetes history, in the form of a category feature that contains information about the sample patient's history of diabetes. Diabetes is one of the most common risk factors in pulmonary TB patients. Currently, the prevalence of pulmonary TB is increasing along with the increasing prevalence of diabetes patients. The frequency of diabetes in TB patients is reported to be around 10-15% and the prevalence of this infectious disease is 2-5 times higher in diabetic patients compared to non-diabetics [8].

(6) Whereas the TCM result feature is in the form of a category feature that contains information on the results of the TCM test for each individual sample with a value; resistant rif, sensitive rif, and negative. Rif-resistant TB patients are patients who experience resistance to the antibiotic drug rifampicin. Sensitive rif is a test that has confirmed TB but is not resistant to antibiotics. Negative, namely the result that no TB bacteria are found in the lungs.

This research was conducted to be able to classify the types of TB disease based on the anatomical location suffered by individuals by using features in the dataset used to determine the type of TB suffered. Extrapulmonary TB cases are almost always non-infectious, unless the patient also has pulmonary TB because 50-60% of HIV-positive people infected with TB will develop pulmonary TB disease [8]. Meanwhile, to find out if an individual has extrapulmonary TB, it is necessary to carry out a bacteriological test by carrying out a direct microscopic examination, TCM TB [8]. The results of chest x-rays are also needed to be able to classify an individual as a patient with pulmonary TB or extrapulmonary TB.

2.2 Data pre-processing

Data pre-processing starts with data transformation to convert categorical data into numeric so that later the data can be processed. The next process is data imputation to overcome the missing value condition. After the imputation of data, the next step is to normalize the data so that the data used has a value range of 0 to 1.

2.3 Data transformation

Data transformation is a change in the scale of data to other forms so that the data has a distribution as expected. Each data will perform the same mathematical operation on the original data [16]. Changes to all data are intended to keep differences between data relatively constant. If the data exceeds one variable, all variables will be transformed so that the relationship between the data does not change. The data transformation carried out in this study is to change the value in the categorical dataset to be converted to numeric data.

2.4 Imputation missing value

The missing value is a condition where there is value or information on a subject that is missing. The causes of this missing value vary, it can be due to an error in data collection or the data is not readable in the system so the value is considered missing [6]. There are several methods to overcome the missing value condition, one of which is the imputation process using the KNN (K-Nearest Neighbor) method.

KNN is an imputation method that is based on data by finding the shortest distance to the object data [17]. By implementing this method, it aims to determine the value of a new object based on attribute values and training samples besides that because this method classifies based on the closest distance which is implemented in a simple formulation

The closest distance is calculated using the Euclidean formula with the following equation:

$d(a, b)=\sum_{i=1}^n(X i-Y i)^2$               (1)

where,

d(a, b): Euclidean distance

X_i: first data

Y_i: second data

i: Attribute i

n: Number of attributes

2.5 Data normalization

Data normalization is a process to change several variables so that they have the same value range, no data is too large or too small so it will be easier to perform statistical analysis. The method used to normalize tuberculosis data is the Min-Max Normalization method [18]. The equation below is a formula for the min-max normalization method.

$z=\frac{x-\min (x)}{[\max (x)-\min (x)]}$               (2)

where,

z: normalization result

x: value x (original)

min(x): the minimum value for the variable x

max(x): the maximum value for the variable x

2.6 Data mining process

In this study, the data mining process involves the process of balancing data and sharing training data and test data. Data balancing is a process to equalize the amount of data in each class to improve the accuracy of the system during the learning process [19]. In this stage, learning the classification model was carried out, namely grouping TB data into pulmonary and extrapulmonary class categories. The number of TB patient data is 985, the extrapulmonary class is 271, while the pulmonary class has a larger number with a total of 714 data. There is no specific size for a dataset that is said to be unbalanced data, but if you look at the data used in this study there are large and very striking differences in the amount of data for each class. So that it can be said for the data used in this study is data with an unbalanced number of classes. On this occasion, the oversampling technique was used to balance the data using the SMOTE (Synthetic Minority Oversampling Technique) method. The way the SMOTE method works is by replicating the data randomly by choosing k closest neighbors as the determinant, then the minority data set will be balanced with the majority data.

From this explanation, it can be formulated into the following formula [20].

dist $=\sqrt{\left(X_1-X_1\right)^2+\left(X_2-X_2\right)^2+\cdots+\left(X_n-X_n\right)^2}$               (3)

$X_{s y n}=X_i+\left(X_{k n n}-X_i\right) \delta$               (4)

where,

X_i=vector of features in the minority class

X_knn=k-nearest neighbors for X_i

$\delta$=random number between 0 to 1

After balancing the data, the next step is to divide the data set into k to n partitions.Splitting this data is known as K-Fold Cross Validation and is a popular method of solving statistical data where the data is divided into two subsets, namely training data for the learning process and test data for validation or assessment used to assess performance models, methods, or algorithms [19]. K-Fold cross validation can be selected based on dataset size. Usually K-Fold is used to reduce computation time and also maintain the accuracy of the estimation. The size of the shared data depends on the specified K value. In this study, a k-fold value of 10 is used. In each iteration, the original dataset provided is divided randomly by cross-validation into training sets, which are used to train the machine learning algorithm, and tests are determined to evaluate its performance [21, 22].

In the data mining process, various methods can be used to build a classification model to be applied to a TB disease diagnosis system, including Naive Bayes, Support Vector Machines, or the application of branches of deep learning methods such as LSTM and Backpropagation.

2.7 Naive Bayes

A technique derived from Bayes' theorem for classifying data is the Naive Bayes Classifier. This method can predict future data based on past data or existing data by calculating odds from test data with data stored in the training process [23, 24]. Its main feature is a very strong (naive) assumption of independence, regardless of any circumstances or events [10]. Bayes theorem is the basis of this method. So, before we get into the explanation of Nave Bayes, let's first explain Bayes' theorem. If there are two separate events in Bayes' theorem (e.g., A and B), then Bayes' theorem can be written using the following formula:

$P(A \mid B)=\frac{P(A)}{P(B)} P(B \mid A)$               (5)

where,

A: Classless data

B: Data hypothesis

P(B|A): Probability of hypothesis B against condition A

P(B): Probability hypothesis B

P(A|B): Probability of A based on condition of B

P(A): Probability A

The application of the law of total probability Bayes theorem can be developed into the following equation:

$P(A \mid B)=\frac{P(A) P(B \mid A)}{\sum_{1-1}^n P(B \mid A)}$               (6)

where, the variables F1 through Fn represent the characteristics of the statements required to complete the classification, while the variable C is a class. Thus, the above formula shows that the probability of including a sample with certain characteristics in class C is equal to the probability of class C occurring (before the sample was included, or what is called a prior) multiplied by the probability of occurrence of the global one Sample characteristics (evidence). Therefore, the equation x above can be formulated using the following equation:

$Posterior=\frac{\text { prior } x \text { likehood }}{\text { evidence }} v$               (7)

The value of evidence is always fixed for each class in one sample. The value of the Posterior will be compared with the Posterior values of other classes to determine to what class a sample will be classified.

2.8 Support vector machine

SVM (Support Vector Machine) is one method for predicting, both regression and classification cases [18]. The basic principle of SVM uses a linear classifier. A linear classifier is a classification case that is separated linearly, but SVM has evolved to work in non-linear cases by using the kernel concept in high-dimensional workspaces. Hyperplanes are used for high-dimensional spaces that aim to maximize the distance (margin) between data classes [25]. The best separator function (hyperplane) must be found among the unlimited number of other hyperplanes in order to find the optimal separator function (classifier) and separate two different classes. The best hyperplane is the one that is right between two sets of objects of two classes.A hyperplane can be said to be the best if it is located right between two sets of objects from two classes. Figure 2 shows how SVM maximizes the distance between two different sets of classes (margins) by determining the best hyperplane.

2.png

Figure 2. SVM finds the best hyperplane to separate class-1 from class+1

Figure 2 shows how the hyperplane is used as a separator of two different classes in the classification process to achieve good results, by measuring the hyperplane margin and determining the maximum point. The distance between the hyperplane and the closest pattern of each class is called the margin [26]. In the Figure 2, the dotted line represents the pattern closest to the hyperplane, which is called the support vector. A hyperplane will be used as the largest class separator by the SVM algorithm. The dividing line between the two classes forms an equation:

$\begin{aligned} & x_i \cdot w+b \geq 1 \,\,\,\,\,\,\,\, \text { untuk } y_i=+1 \\ & x_i \cdot w+b \leq 1 \,\,\,\,\,\,\,\, \text { untuk } y_i=-1\end{aligned}$               (8)

From these equations, it can be seen that the data that falls into the first-class category is data that has a larger equation value, while the data that enters the second-class category is data that has a smaller equation value. The value of the margin or the value of the distance between the boundary planes based on the formula for the distance of the line to the center point can be represented by the equation below:

$\frac{1-b-(-1-b)}{\|w\|}=\frac{2}{\|w\|}$               (9)

Then this margin value will be maximized by minimizing the value of $\|w\|$ as the denominator. This can be formulated as Quadratic Programming. If the two boundary planes are represented as Eq. (9), the search for the dividing line with the largest boundary can be formulated as follows:

$y_i \left(x_i \cdot w+b\right)-1 \geq 0$               (10)

$\min \frac{1}{2}\|w\|^2$               (11)

This problem can be solved by existing computational techniques, such as the Lagrange multiplier expressed in Eq. (12).

$L(w, b, a)=\frac{1}{2\|w\|^2}-\sum_{i=1}^l a_i\left(y_i((\vec{x} \vec{w}+. .+\mathrm{b})-1)\right)$               (12)

$\sum_{i=1}^l a_i-\frac{1}{2} \sum_{i, l=1}^l a_i a_j y_i y_j x_i, x_j$               (13)

where,

$a_i \geq 0 (i=1,2, \ldots l) \sum_{i, l=1}^l a_i y_i=0$               (14)

where,

w: weight vector

x: attribute input value

b: bias

a_i: support vector

y_i: data class

If the data cannot be separated linearly, it can be said that the classes in the input space cannot be separated perfectly. This causes the constraint in Eq. (9) is not met, so the optimization cannot be done. To overcome these problems, SVM is formulated using the soft margin technique, the following is the mathematical equation:

$y_i \left(x_i \cdot w+b\right) \geq 1-\varepsilon_i$               (15)

Thus, Eq. (15) is converted into an equation as below:

$\min _w=\frac{1}{2}\|w\|^2+c \sum_{i=1}^l \varepsilon_i$               (16)

where,

w=weight vector

x=attribute input value

b=bias

$\varepsilon_i$=error value

c=constant value

In general, the problems that exist rarely have linear separable data and most of them are non-linear. Solving the non-linear SVM problem is to map the x data by a function $\phi(x)$ to a vector space with a higher dimension. In the new vector space, a hyperplane that separates the two classes can be constructed. Then do the dot product calculation from the data that has been transformed in a higher dimensional space, namely $\phi\left(x_i\right)$. $\phi\left(x_i\right)$. However, in general, the transformation $\phi$ is difficult to understand, therefore the dot product value search can be replaced with a kernel function as in the following equation:

$K\left(x_i, x_j \phi\left(x_i\right) \cdot \phi\left(x_j\right)\right)$               (17)

The following are kernel functions that are commonly used to classify non-linear data [11]:

1. Linear Kernel

$K\left(x_i, x\right)=x_i^T x$

2. Kernel Polynomial

$K\left(x_i, x\right)=\left(\gamma x_i^T+r\right)^p, \gamma>0$

3. Kernel RBF or Radial Based Function

$\mathrm{K}\left(x_i, x\right)=\exp \left(-\gamma\left\|x-x_i\right\|^2\right)$

4. Sigmoid Kernel

$K\left(x_i, x\right)=\tanh \left(\gamma x_i^T+r\right)$

2.9 Backpropagation

Backpropagation is a supervised learning algorithm that uses multiple layers to change the weights connected to the neurons in the hidden layer [27]. The Backpropagation algorithm minimizes errors in the output generated by the network by changing the value of its weights in the backward direction using the output error. To get the error output, the forward step must be done first. In the Backpropagation algorithm, the training process is carried out in two phases, namely the forward propagation and backward propagation stages [27]. The following is the algorithm flow of backpropagation in each phase.

Phase 1: Forward Propagation

(1) Initialize the weight with a small random value, maximum Epoch value, error value, and learning rate.

(2) Perform the steps below when the epoch value is smaller than the maximum value.

(3) Each input unit receives the signal and forwards it to the hidden unit.

(4) Calculate all outputs on hidden units z_k (j=1, 2, …, p).

$z_{-}net_j=v_{j o}+\sum_{i=1}^n x_i+v_i$               (18)

$z_j=f\left(z_{-} n e t_j\right)=\frac{1}{1+e^{-z_{-} n e t}}$               (19)

•Calculate all network outputs in units of y_k (k=1, 2, …, m)

$y_{-} n e t_k=w_{k o}+\sum_{j=1}^p z_i+w_{k j}$               (20)

$y_k=f\left(y_{-} n e t_j\right)=\frac{1}{1+e^{-y \_n e t}}$               (21)

Phase 2: Backward Propagation

•Calculate the output unit factor based on the error value for each output unit y_k (k=1, 2, ..., m).

$\delta_k=\left(t_k-y_k\right) f^{\prime} Ynet _j=\left(t_k-y_k\right) y_k\left(1-y_k\right)$               (22)

•Calculate the weight correction using the formula below.

$\Delta W_{j k}=\mathrm{a} \delta_k z_y ; k=1,2, \ldots, m ; j=0,1, \ldots p$               (23)

•Calculate the weight correction using the formula below y_k (k=1, 2, ..., m).

$\delta_{-} n e t j=\sum_{k=1}^m \delta_k W_{k j}$               (24)

$\delta_j=\delta_{\_} n e t_j f^{\prime} Znet_j=\delta_{n e t j} Z_j\left(1-z_j\right)$               (25)

•Calculate the weight correction using the formula below.

$\Delta V_{j i}=\mathrm{a} \delta_j x_j ; j=1,2, \ldots, m ; i=0,1, \ldots p$               (26)

•Add up the change in weight of the line leading to the output unit.

$\begin{gathered}W_{j k}(\text { new })=W_{j k}(\text { old })+\Delta W_{j k}; \\ k=1,2, \ldots, m ; j=0,1, \ldots p\end{gathered}$               (27)

Add up the change in weight of the line leading to the hidden unit.

$\begin{gathered}\Delta V_{j i}(\text { baru })=V_{j i}(\text { lama })+ \Delta V_{j i} ; \\ \quad j=1,2, \ldots, m ; i=0,1, \ldots p\end{gathered}$               (28)

where,

w_0k: bias weight on output unit y_k

v_0j: bias weight on hidden unit z_j

v_ij: line weight from unit to hidden unit z_j

w_jk: line weight from z_j to output unit y_k

f_k: activation function on the hidden unit to output

_fj: activation function on input unit to hidden

z_j: j-th hidden unit

y_k: k-th output unit

i: 1…, n

j: 1…, p

k: 1…, l

n: number of input units

p: number of hidden units

l: number of output units

2.10 Long Term Short Memory (LSTM)

Long Term Short Memory (LSTM) is a development of a neural network that is used to model data in a certain time series. This method can also overcome long-term dependence on the input. Cells in the LSTM store a value, either for a long or a short period of time. The memory block in the LSTM determines which value will be selected as the relevant output for the given input [12]. This LSTM method is proposed as a solution to overcome the vanishing gradient problem on the RNN when processing long sequential data.

Figure 3 illustrates the architecture of the LSTM. There are four activation function processes at each input to neurons, hereinafter referred to as gate units. The gate units are forgotten gates, input gates, cell gates, and output gates [9]:

3.png

Figure 3. LSTM architecture

1. Forgot gates

The input data will be processed and it will be chosen which one will be used or discarded in the memory cells. The sigmoid activation function is used in this gate, which results in a value between 0 and 1 [16]. If the output is 1 then all data will be stored and vice versa if the output is 0 then all data will be discarded. With the following formula [28]:

$f t=\sigma\left(W_f\left[h_{t-1}, x_t\right]+b_f\right)$               (29)

where,

ft: forget gate

$\sigma$: sigmoid activation function

W_f: weights forget gate

x_t: input cell

h_t-1: output cell previously

b_f: bias forget gate

2. Input gates

The 2 gates are in the input state, which must first decide which value to replace using the sigmoid function. Then, the tanh activation function will create a new value vector and store it in the memory cell. With the following formula:

$i_t=\sigma\left(W_i\left[h_{t-1}, x_t\right]+b_i\right)$               (30)

$c_t=\tanh \left(W_c\left[h_{t-1}, x_t\right]+b_c\right)$               (31)

where,

i_t: input gate

w_i: weights input

b_i: bias input gate

C_t: candidate

tanh: tanh activation function

W_c: weights candidate

3. Cell gates

The cell gates replace the value in the previous memory cell with the new memory cell value. This value is obtained by combining the values contained in the forget gate and the input gate. With the following formula:

$\left.c_t=f_t * c_{t-1}+i_t * c_t\right)$               (32)

where,

c_t: cell state

c_t−1: cell state previously

4. Output gates

Two gates must be implemented at the output gates. First, the sigmoid activation function is used to decide which part of the memory cell value to output. Next, the value is inserted into the memory cell using the activation function tanh. Finally, the two gates are multiplied to give the value to be output. With the following formula:

$o_t=\tanh \left(W_o\left[h_{t-1}, x_t\right]+b_o\right)$               (33)

$h_t=o_t * \tanh$               (34)

where,

O_t: output gate

W_o: weights output gate

b_o: bias output gate

h_t: the hidden layer

2.11 Evaluation

In modeling the classification process, it is necessary to evaluate the performance of the system to measure how well the method used [29]. The method commonly used in evaluating the system is the confusion matrix. A confusion matrix is one method of evaluating the calculation of the level of accuracy, precision results, recall, and f-measure of the algorithm used in research and is measured from the results of testing data that have been predicted [30].

Accuracy is the value of the effectiveness of the overall results of the classification process, following the formula:

(1) Accuracy is the value of the effectiveness of the overall results of the classification process, following the formula:

$Accuracy=\frac{T P+T N}{T P+T N+F P+F N}$               (35)

(2) Precision is the result of the percentage of positive classification data labels, following the formula:

$Precision=\frac{T P}{T P+F P} \times 100 \%$               (36)

(3) The recall is the result of the effectiveness of the classification process for the identification of positive labels, the following formula is:

$Recall=\frac{T N}{T N+F N} \times 100 \%$               (37)

F-measure is the result of mean recall and precision, where the range of f-measure itself is 0-1.

$F-measure=2 \times \frac{\text { Recall } \times \text { Precision }}{\text { Recall }+ \text { Precision }} \times 100 \%$               (38)

where,

TP: the number of data correctly predicted positive.

TN: the number of data with the original class is positive but the prediction result is negative.

FN: the number of data correctly predicted negative.

FP: the number of data with the original class is negative but the prediction result is positive.

Our research results yield several critical conclusions. Firstly, the proposed model in this study effectively addresses the problem of missing values in TB data at Syarifah Ambami Rato Ebu Bangkalan Hospital, utilizing the K-NN method. This approach significantly enhances the integrity and accuracy of the dataset.

Secondly, the application of the Synthetic Minority Over-sampling Technique (SMOTE) has been demonstrated to improve the performance of the model, albeit without a significant increase in accuracy compared to the application of datasets without SMOTE. This finding is particularly evident when considering the computation time required. The use of SMOTE demands more time due to the generation of synthetic data to counterbalance the minority data class.

Thirdly, it is concluded that Long Short-Term Memory (LSTM) is highly efficacious in classifying TB disease. Utilizing the GridSearch method, the best accuracy results manifest in several test scenarios, yielding a stable accuracy value of 100% in experiments using 10-fold cross-validation, a learning rate of, and the application of the Tanh activation function on 100 neurons, irrespective of the use of SMOTE.

Fourthly, a comparison of the LSTM method with other methods, such as Naive Bayes, SVM, and backpropagation, establishes the superiority of LSTM in terms of accuracy. LSTM achieves a perfect score of 100%, compared to Naive Bayes (99.4%), SVM (99.3%), and backpropagation (99.7%).

Lastly, our research successfully models a classification of TB disease based on anatomical locations, namely the lungs and extrapulmonary sites, using the LSTM method, thereby enhancing the performance of the algorithm to achieve optimal accuracy. This study contributes to research development by formulating a classification model that can be applied to TB data and offer valuable recommendations to hospitals regarding pulmonary and extrapulmonary classes and significant features of TB disease.

Based on these conclusions, several recommendations emerge for future research. As the next step in system development, it would be beneficial to construct a classification model utilizing another imputation method capable of combining two different types of data. This approach could potentially offer more nuanced and accurate classifications.

Moreover, subsequent research should consider expanding the volume of data and features used to build the classification model. This expansion could enhance the performance of the model, granted that the number of missing values and class balance in the utilized dataset is adequately considered.