# Building Expert Medical Prognostic Systems Using Voronoi Diagram

Authors: Maria A. Ivanchuk; Igor V. Malyk
Journal: International Journal of Computational Mathematics
 (2015)

---

## Abstract

The method of building expert systems for medical prediction of severity in patients is purposed. The method is based on using Voronoi diagrams. Examples of using the method are described in the paper.


---

## Body

## 1. Introduction

Development of mathematical approaches for prediction in medicine was developed by Fisher, the father of the linear discriminant analysis [1]. Currently, there are many approaches to solving this problem such as cluster analysis [2], the construction of predictive tables [3], image recognition, and linear programming. Cluster analysis is commonly used for solving the tasks of medical prediction. The aim of a cluster analysis is to partition a given set of data or objects into clusters. This partition should have the homogeneity within the clusters and heterogeneity between clusters [4]. But cluster analysis has a significant disadvantage. It refers to the methods without teacher.We purpose the method of building the prognostic system, which uses available information for teaching the expert system.Let us have two sets of pointsA={ai=(ai1,ai2,…,ain),i=1,mA¯} and B={bi=(bi1,bi2,…,bin),i=1,mB¯} in Euclidean space Rn, where m is the number of points in the set. Set A is the training sample, which includes the patients with severity; set B is the training sample, which includes the patients without severity. There are n parameters (factors which affect the severity) known for each patient. Our task is to separate the space Rn into two half-spaces RAn (patients with severity) and RBn (patients without severity) that for each point xi∈Rn determine its belonging to one of the half-spaces with predetermined significance level α. We will check the expert system using the control sample Z={zi=(zi1,zi2,…,zin),i=1,mZ¯}.We must use a smaller number of parameters to obtain the largest plausibility value for expert system.


## 2. Methods

We will use the Voronoi diagram [5] to solve the task of expert system’s building. Let us concatenate sets A and B and build Voronoi diagram for the set D=A∪B. Let us have a point di∈D, i=1,mA+mB¯. Let di∈A. The same reasoning will be for di∈B.LetVi be Voronoi polygon for point di. The points for which Voronoi polygons have neighboring facets with polygon Vi will be calledpointdi’s nearest neighbors. The set of all point di’s nearest neighbors will be denoted by NVi.Pointdi will be calledthe internal point of set A if all its nearest neighbors belong to set A(1)∀x∈NVi:x∈A.There are the following cases for Voronoi polygonVi.(1)
All pointdi’s nearest neighborhoods belong to set A(2)∀x∈NVi:x∈A.In this case pointdi is the internal point of set A.(2)
All pointdi’s nearest neighborhoods belong to set B(3)∀x∈NVi:x∈B.In this case pointdi is the outlier of set A.(3)
There are points belonging to setA and the points belong to set B among point di’s nearest neighborhoods. In this case point di is the boundary point of set A or point di with one or several neighborhoods being the outliers of set A.If there is a way from pointdi to any internal point of set A passing only through the points of set A, point di is theboundary point of set A. In a different case point di is theoutlier of set A.Let us eject outliers from setA (patients with severity) and build new Voronoi diagram. The diagram separates space Rn into two half-spaces RAn (patients with severity) and RBn (patients without severity). We will assign patient z from control set Z to the patients with severity if point z is in the Voronoi polygon of any point of set A; in the different case we will assign patient z to the set of patients without severity.Let us sort parameters according to Kulbak’s information measure [3] and build Voronoi diagrams for different space dimension ni=2,…,n. To find the best of expert systems we will use Zagoruiko’s likelihood measure [6].Let pointz∈Z. Euclidian distance between point z and the nearest point ai∈A is equal to R(z,ai). Euclidian distance between point z and the nearest point bj∈B is equal to R(z,bj). Than similarity signed measure (charge) of point z and set A is
(4)FA/Bz=Rz,bj-Rz,aiRz,ai+Rz,bj.
Similarity measure FA/B(z) may range from −1 to 1. Point z is assigned as the part of set A if FA/B(z)>0. The high value of the measure FA/B(z) indicates the high similarity between point z and set A.LetZA be the set of control group patients with severity; ZB is the set of control group patients without severity, Z=ZA∪ZB.We denoteZA+ is the set of patients of ZA which were correctly assigned as the patients with severity; ZA- is the set of patients of ZA which were incorrectly assigned as the patients without severity (underdiagnosis cases); ZB+ is the set of patients of ZB which were correctly assigned as the patients without severity; ZB+ is the set of patients of ZB which were incorrectly assigned as the patients with severity (overdiagnosis cases).ThenFZA+ is the sum of similarity measures of the points of set ZA+ and set A:
(5)FZA+=∑i=1mZA+FA/B(zi),zi∈ZA+,FZB+ is the sum of similarity measures of the points of set ZB+ and set B:
(6)FZB+=∑i=1mZB+FB/A(zi),zi∈ZB+,FZA- is the sum of similarity measures of the points of set ZA- and set B:
(7)FZA-=∑i=1mZA-FB/A(zi),zi∈ZA-,
and FZB- is the sum of similarity measures of the points of set ZB- and set A:
(8)FZB-=∑i=1mZB-FA/B(zi),zi∈ZB-.
The likelihood measure of the expert system is
(9)F=FZA++FZB+mZA++mZB+-FZA-+FZB-mZA-+mZB-,
if the aim of the expert system is the differential diagnostic of two similar diagnoses.And(10)F=FZA+mZA+-FZA-mZA-,
if the aim of the expert system is finding the patients with severity.We will use the Akaike information criterion [7]
(11)AIC=2n-2ln⁡⁡F
to find the optimal ratio of the likelihood of model and the quantity of using parameters. The best expert system is the system with the least value of AIC. In other words, the best expert system is the system which uses the least number of parameters to have the greatest likelihood.Let us formulate the following.Algorithm for Modelling the Prognostic System
(1)
Sort parameters using Kulbak’s information measure [3].
(2)
For eachni=2,…,n,
(i)
build Voronoi diagram for the setD=A∪B in the space Rni;
(ii)
eject the outliers of setA;
(iii)
build the new Voronoi diagram;
(iv)
if ther are no outliers in setA go to step (v); else return to step (ii);
(v)
check the system on the control setZ;
(vi)
calculate the likelihood measureF of the expert system;
(vii)
calculate the Akaike information criterionAICni.
(3)
Findn*:AICn*=min⁡ni=2,…,n(AICni).
(4)
As the expert system use Voronoi diagram in the spaceRn*. If point z∈RAn*, assign it to set A. If point z∈RBn*, assign it to set B.Let us calculate the complexity of the algorithm. There are several ways to find Voronoi diagrams, one of which is known as Fortune’s algorithm [8]. Its complexity is O(mlog⁡⁡m), where m=m1+m2. The complexity of finding the likelihood measure F is O(mZlog⁡⁡m), because we must find the similarity measure FA/B(z) for each point z∈Z. Step (2) is repeated n-1 times and the complexity of the algorithm is O((n-1)mlog⁡⁡m). Since n≪m, the total complexity of the algorithm is O(mlog⁡⁡m).


## 3. Results

### 3.1. The Expert System of Predicting the Presence of Severity in Abdominal Surgery Patients

We built expert system using 8 parameters. Training sample consists of 28 patients with severity and 15 patients without severity. Control test consists of 8 patients with severity and 5 patients without severity. The level of significance wasα=0,01. In this case the aim of the expert system is finding the patients with severity; therefore we use formula (10) to find likelihood measure.Voronoi diagram forn=2 is represented on Figure 1. The results of calculations are represented in Table 1.Table 1
Building the expert system for abdominal surgery patients.
n
Outliers
F
AIC
Underdiagnosis cases
Overdiagnosis cases
2
1 (1.4%)
0.575
3.108
1  (16%)
2 (40%)
3
0 (0%)
0.389
4.889
1 (16%)
0 (0%)
4
0 (0%)
0.352
6.091
1 (16%)
0 (0%)
5
0 (0%)
0.627
5.933
2 (30%)
0 (0%)
6
0 (0%)
0.639
6.897
2 (30%)
0 (0%)
7
0 (0%)
0.684
7.761
2 (30%)
0 (0%)
8
0 (0%)
0.611
8.987
2 (30%)
1 (20%)
The best expert system was built usingn=2 parameters.Voronoi diagram for abdominal surgery patients before (a) and after (b) ejecting the outliers,n=2.
(a)
(b)


### 3.2. Researching the Anthropological Parameters in Teenagers

We built expert system using 8 parameters. Training sample consists of 38 girls and 14 boys. Control test consists of 8 girls and 5 boys. The level of significance wasα=0,01. In this case the aim of the expert system is the differential diagnostic of two similar diagnoses; therefore we use formula (9) to find likelihood measure.Voronoi diagram forn=2 is represented on Figure 2. The results of calculations are represented in Table 2.Table 2
Building the expert system for researching the anthropological parameters in teenagers.
n
Outliers
F
AIC
Errors in the control sample
2
2 (4.2%)
0.0271
9.216
2 (15.4%)
3
0 (0%)
0.1147
7.331
2 (15.4%)
4
0 (0%)
0.1007
8.591
2 (15.4%)
5
0 (0%)
0.1212
9.221
2 (15.4%)
6
0 (0%)
0.2587
8.704
3 (23%)
7
0 (0%)
0.2121
10.101
3 (23%)
8
0 (0%)
0.1946
11.274
3 (23%)
The best expert system was built usingn=3 parameters.Voronoi diagram for anthropological parameters in teenagers before (a) and after (b) ejecting the outliers,n=2.
(a)
(b)


## 3.1. The Expert System of Predicting the Presence of Severity in Abdominal Surgery Patients

We built expert system using 8 parameters. Training sample consists of 28 patients with severity and 15 patients without severity. Control test consists of 8 patients with severity and 5 patients without severity. The level of significance wasα=0,01. In this case the aim of the expert system is finding the patients with severity; therefore we use formula (10) to find likelihood measure.Voronoi diagram forn=2 is represented on Figure 1. The results of calculations are represented in Table 1.Table 1
Building the expert system for abdominal surgery patients.
n
Outliers
F
AIC
Underdiagnosis cases
Overdiagnosis cases
2
1 (1.4%)
0.575
3.108
1  (16%)
2 (40%)
3
0 (0%)
0.389
4.889
1 (16%)
0 (0%)
4
0 (0%)
0.352
6.091
1 (16%)
0 (0%)
5
0 (0%)
0.627
5.933
2 (30%)
0 (0%)
6
0 (0%)
0.639
6.897
2 (30%)
0 (0%)
7
0 (0%)
0.684
7.761
2 (30%)
0 (0%)
8
0 (0%)
0.611
8.987
2 (30%)
1 (20%)
The best expert system was built usingn=2 parameters.Voronoi diagram for abdominal surgery patients before (a) and after (b) ejecting the outliers,n=2.
(a)
(b)


## 3.2. Researching the Anthropological Parameters in Teenagers

We built expert system using 8 parameters. Training sample consists of 38 girls and 14 boys. Control test consists of 8 girls and 5 boys. The level of significance wasα=0,01. In this case the aim of the expert system is the differential diagnostic of two similar diagnoses; therefore we use formula (9) to find likelihood measure.Voronoi diagram forn=2 is represented on Figure 2. The results of calculations are represented in Table 2.Table 2
Building the expert system for researching the anthropological parameters in teenagers.
n
Outliers
F
AIC
Errors in the control sample
2
2 (4.2%)
0.0271
9.216
2 (15.4%)
3
0 (0%)
0.1147
7.331
2 (15.4%)
4
0 (0%)
0.1007
8.591
2 (15.4%)
5
0 (0%)
0.1212
9.221
2 (15.4%)
6
0 (0%)
0.2587
8.704
3 (23%)
7
0 (0%)
0.2121
10.101
3 (23%)
8
0 (0%)
0.1946
11.274
3 (23%)
The best expert system was built usingn=3 parameters.Voronoi diagram for anthropological parameters in teenagers before (a) and after (b) ejecting the outliers,n=2.
(a)
(b)


## 4. Conclusions

The method of building expert medical prognostic systems is brought forward. The method is based on building Voronoi diagram in Euclidean spaces of different dimensions. The resulting expert systems are checked on the test samples. The expert system with the least value of the Akaike information criterion is accepted as the best system.The described method is applied in practice to predict the presence of severity in abdominal surgery patients and gives 84% correct results for the patients with severity from the control sample. The expert system for researching the anthropological parameters in teenagers with 84.6% correct results was built, using the introduced method.



---

*Source: 415146-2015-02-17.xml*