Systematization and grouping of information about objects allows improving the quality of decisions. This paper discusses using of pattern recognition methods in medical monitoring systems. The analysis of clustering methods for processing biomedical data was carried out. The problem of stratification of patients using the c-means method, a feature of which is the possibility of designing clusters that intersect, is considered. Particular attention is paid to the choice of the structure and parameters of fuzzifiers to achieve the best clustering accuracy.
In medicine clustering is one of the tools of experimental data and clinical
observations analyzing. This mathematical instrument is widely used for diagnostic purposes,
for the classification problems solving and the search for new patterns, and for
formulating new scientific hypotheses [
Currently there are many different approaches and specific heuristic algorithms for
solving cluster analysis problems (taxonomies, or classifications without a teacher)
when it is necessary to find natural groups of similar objects (clusters) according to a
given sample of their vector descriptive descriptions [
The problem of automatic objects classification consists of dividing the whole set of
analyzed objects into a relatively small number of homogeneous, in a certain sense,
classes. Different methods can be used for this purpose. One of them is based on
constructing a hierarchy of classes, which is defined as the sequence of embedded
partitions [
The algorithms for organizing data of this type proceed from the fact that some kind of objects is characterized by a certain degree of connectivity. It is assumed to have attached groups (clusters of different order). Algorithms, in their turn, are divided into agglomerative (unifying) and divisive (separating). In separating clustering all the initial data sets are considered as one cluster, which splits into two, those in their turn for two more etc., until each of them will consist of a single object.
In agglomerate clustering the hierarchical tree is also formed, but by combining objects into larger clusters of smaller ones. First each object of the initial set is treated as a separate cluster, then two objects are searched, the distance between which is minimal, and are combined into one and so on. This procedure continues until all the objects are assembled into a single cluster. The disadvantages of this approach include the lack of clear recommendations for choosing the number of clusters, the relatively large amount of computations and the impossibility of individual accounting of certain elements when clustering is combined.
Another approach to solving the automatic classification problem is given by
probabilistic clustering models [
The EM algorithm [
The EM-algorithm is simple and easy to implement, not sensitive to isolated objects and quick converges with successful initialization. However, it requires indication of the clusters number k for initialization, which implies the presence of priori knowledge about the data. In addition, if the initialization fails, the convergence of the algorithm may be slow or a poor result can be obtained. Obviously, such algorithms are not applicable to spaces with high dimensionality since in this case it is extremely difficult to assume a mathematical model of data distribution in this space.
Among the fast-acting algorithms using the concept of the masses center the most
common algorithms are k-means and the FOREL algorithm. The FOREL algorithm
(FORmal ELement) proposed by Zagoruiko and Yolkina [
The k-means algorithm [
The general idea of the algorithm: the given fixed number k of observation clusters is compared to the clusters so that the averages in the clusters (for all variables) differ as much as possible from each other. The algorithm disadvantage is that the algorithm is too sensitive to emissions, which can distort the average; slow work at large databases; it is needed to set the clusters number.
The considered clustering algorithms provide the separation of objects into disjoint sets, while medical data have the property of overlaying one another. This disadvantage is deprived of fuzzy clustering algorithms, for example, the c-means algorithm, the application of which for medical and biological data is considered in this article.
Application of the k-means fuzzy clustering method for the patient’s state recognition problems in the medical monitoring systems As an example of a complex system the medical-biological system is considered, this includes the following elements: a physician, patients and a subsystem diagnosing patients.
The system model of the diagnostic process of the medical and biological system is
presented in Fig. 1. Designations in the picture are: S is an inputs adder, Controller is
a control body, which is an attending medical doctor, who develops patient care
scenarios, u are control variables, f is external influences (perturbation), Object of control
- the object of control (patients), Z is variable of patients states, W is criteria for the
quality of patients states. The beginning and end of the stages of the patient's
lifecycle will be determined as the set of end-states of patients. The number of states
accepted for consideration is set by an expert in the subject area based on the results
of the clustering analysis. It is accepted hypothesis of local equilibrium as working,
according to which the patient's state is uniquely determined by the fundamental
system of its variables. We will assume that a critical condition on a set of end states is a
resistant state in which the patient loses control in the process of treatment due to the
progressive development of defects in functional parts. The objective problem is that
there is no structural decision rule for the transition to a resistant state for the patient
under consideration.
for a batch or sequential processing of information [
The initial information is a sample of observations generated from the ndimensional vector of factors
= { (1), (2), … , ( )}, ( ) ∈ , = 1,2, … , .
The result of the method is to split the initial data array into classes with a certain level ( ) of belonging to the k-th vector of factors of the j-th cluster. The objective function to be minimized is: (w( ), c) = ∑ =1 ∑ =1 ( ) 2( ( ), ) →
with limitations:
∑ =1 ( ) = 1,
= 1, … , , 0 < ∑ =1 ( ) < , = 1, … , .
Here ( ) ∈ [
The work of the algorithm begins with the definition of the initial random matrix of fuzzy partition 0
. According to its values, the initial set of prototype centers 0 is calculated according to the formula = ∑ =1 ( ) ( )
∑ =1
( ) = ( 2( ( ), ))1− ∑ =1( 2( ( ), ))1− 1
1 , (1) (2) (3) (4) (5) Based on the calculated prototype centers 0, the matrix 1 is calculated in accordance with the formula: After that a batch mode 1, 2, … , , , +1, … calculates, until the difference between the current and the next values of the matrix W is not be less than the Another method of calculating the coefficients of the matrix (denoted by its μ-matrix) was also used in the work: = 1 2 2( ( ), ( )) 1− ] 1 , = min‖ − ‖ given threshold of accuracy. Thus, all available sample data is processed multiple times.
As a result of the algorithm, we obtain a matrix of fuzzy clustering, in which patients will be divided into clusters (diagnoses). The shape of the clusters can vary from the hypersphere to the hyperellipsoid, depending on the form of the input data, that is from the choice of the distance between ( ) and : 2( ( ), ) = √( ( ) − ) ( ( ) − ) (6) (7) where is a matrix that can be defined as the inverse fuzzy covariance matrix of each cluster.
If, as a matrix , we take a unit matrix, then the result is an Euclidean distance 2( ( ), ) = √( ( ) − ) ( ( ) − ) and the shape of the clusters will be rounded (hypersphere). tive and = −1, where
To give clusters the form of hyperellipsoids as a matrix , one can use a symmetric positive definite matrix, that is a matrix in which all eigenvalues are real and posi = ∑ =1 ( )( ( )− )( ( )− ) ∑ =1 ( ) .
As a result of the clustering algorithm, we obtain the division of our data into homogeneous clusters, which may take the form of arbitrarily-oriented hyperellipsoid in the space and are able to intersect in the space of signs. Also, as a result of the algorithm's operation, the degree of belonging of each object to each of the clusters ( ) will be known.
The training sample consisted of 180 objects, which are data from laboratory
studies of patients aged from 46 to 78 years old, where 50 belonged to the class "healthy"
- benign tumor, 45 people belonged to the “nonmetastable class ", 52 people to the
class" metastasize "and 33 people to the class "hormone-resistant "[
The data was transformed to a normalized form to improve the algorithm's performance. As data has been normalized, the Mahalanobis distance instead of the Euclidean distance can be used (suppose that there are no correlations between variables).
Three datasets were selected for conducting experiments. The first dataset contains the Prostate cancer data (the main sample), the second one is Fischer's irises and the third is the breast cancer data. The first experiment was performed on a Prostate cancer data containing 25 parameters, 4 groups of patients and 180 samples. In addition, it was decided to choose different methods for calculating fuzzy clustering matrix (Wmatrix and μ-matrix). To verify the accuracy of clustering with a fuzzy c-means method the obtained clustering is compared in percentage to the original dataset by the number of samples of the particular disease stage.
In the first case with the W matrix, 43 patients of «Without Metastases» group of 45 were included in the first cluster (95% accuracy), the second - 31 patients from «With Metastases» group from 52 with 52 (60% accuracy), in the third - 49 patients in the «Healthy» group from 50 (98% accuracy) and in the fourth - 13 patients in the group "4th" from 33 (39% accuracy). This clustering was performed with an accuracy of 72.3%. In the second case with the μ matrix, 34 patients from the Without Metastases group from 45 (75% accuracy), the second - 14 patients in the group "4th" from 33 (42% accuracy), in the third - 25 patients with the "With Metastases" group from 52 were in the first cluster (49% accuracy) and in the fourth - 50 patients of the "Healthy" group from 50 (100% accuracy). This clustering was carried out with an accuracy of 66.5%.
The fuzzifier was chosen manually to select the best result, therefore, on the basis of experiments with the fuzzifier, the best result was found in the matrix W in the values of 1.1, in the case of the matrix μ fuzzifier β= - 2. The choice of the fuzzifier depends on the sample data and the matrix. Сlusterization results for diagnosing prostate cancer are shown in Figure 2. From the experiments conducted, we can conclude that clustering with a W matrix gives better results. Therefore, it was decided to finally accept the W matrix for further experiments.
The second experiment was conducted on a Irises dataset, which contains 4 parameters, 3 groups of the iris type and 150 samples. In the second experiment different fuzzifier values were used. In the first case with fuzzifier 1.1, 36 flowers from 50 of the group "virginica" were in included the first cluster (72% accuracy), in the second 50 flowers from 50 of setosa group (100% accuracy) and in the third - 47 flowers from 50 of the group "versicolor" (94% accuracy). This clustering was carried out with an accuracy of hit 87%. In the second case with the fuzzifier 2, 50 flowers of the setosa group from 50 were included in the first cluster (100% accuracy), the second 43 flowers from 50 of the group "versicolor" (86% accuracy) and in the third - 45 flowers from 50 of the group "virginica" (90% accuracy). This clustering was performed with an accuracy of 92%. The experiment showed that using the fuzzifier 2 for the sample with irises is more accurate. Сlusterization results for the Irises dataset are shown in Figure 3. Then let us consider the latest experiment with breast cancer data. The second experiment was conducted on a sample of cancer patients, containing 30 parameters, 2 groups of tumor type and 569 samples. In the first case with the fuzzifier 2, 350 patients from 357 of the "benign" group (98% accuracy) were included in the first cluster, the other 142 patients from 212 of the "malignant" group (66% accuracy) were included in the second cluster. This clustering was performed at an accuracy of 82%. In the second case with the fuzzifier 3, 324 patients from 357 of the "benign" group (90% accuracy) and the other 171 patients from 212 of the "malignant" group (80% accuracy) were in the second cluster. This clustering was performed with an accuracy of 85%. The experiment has shown that using the fuzzifier 3 for a cancer patients dataset is more accurate. Сlusterization results for the breast cancer data are shown in Figure 4. The problem of stratification of patients in medical monitoring systems using of the of c-means fuzzy clustering method has been considered. The two models of membership grade have been investigated. It is shown that the W-matrix model is more effective in terms of image recognition. From the experiments carried out, it has been concluded that using different values of the distance fuzzifier allows improving the quality of clustering, as well as obtaining a more accurate picture of the conducted clustering. As it can be seen from the three experiments, the quality of clustering depends not only on the fuzzifier, but also on the set of data and the number of clusters. This is the reason for a more detailed study of the method, its modifications, and the choice of the fuzzifier. 6