text.
Nowadays, the problem of creating decision support systems (DSS), which are increasingly used in solving complex, difficult formalized problems, which are, in particular, the task of diagnosing various diseases in medicine [1-5]. The task of decision-making is complicated by the need to take into account a large number of different factors. This is primarily due to the difficulty of gathering and analyzing the large amount of information needed to make the right and informed decision.
In determining the diagnosis of the disease is of great importance the need to take into account the mutual influence of different parameters on each other, the reliability of the original data, the completeness of information about the studied patients. Uncertainty arises not only because of the difficulty of creating the model of the object, but also because the developer does not have a clear idea of the relationship of possible solutions, the quality of heuristics used, as well as other difficult factors. The greater the degree of uncertainty about the effectiveness of possible alternative solutions and the importance of the various criteria that evaluate these alternatives, the more important is the expert assessment made by him on the basis of experience and intuition, rather than accurate knowledge. Since it is impossible for experts to diagnose the disease in a large number of people, the application of mathematical methods that have found application in modern clinical decision support systems (CDSS) can help [6, 7].
The CDSS is designed to improve health care delivery by improving medical decisions through focused clinical knowledge, patient information, and other medical information. Traditional CDSS consists of software designed to directly assist in clinical decision-making, in which the characteristics of an individual patient are compared with a computerized clinical knowledge base, and then clinical assessments or recommendations for a particular patient are transmitted to the physician [8, 9]. The range of functions provided by CDSS is wide, including diagnostics, alarm systems, disease treatment, medication, medication and more. They can take the form of computerized alerts and reminders, computerized manuals, order sets, patient reports, documentation templates and clinical workflow tools, and more.
There are several approaches to building a CDSS [10, 11]: 1. Providing the doctor with relevant information sources that help him to make decisions independently.
2. The use of clinical pathways, so-called technological maps [12], which are prescriptive models of standard health care procedures that must be made for a specific sample of patients; 3, Development of a wide range of private narrow-profile CDSS, in particular Sky-Chain [13], which offers trained neural networks for the analysis of diagnostic images of various diseases; 4. Building a cognitive system capable of self-learning and learning directly from informal text sources, such as the IBM Watson [14] system, which is based on explicit knowledge; 5. Construction of DSS on the basis of a precedent approach [15], which is based on implicit empirical knowledge and according to which it is proposed to form clinical data banks, find cases in them precedents similar to the current one, and recommend treatment and diagnostic measures based on found precedents.
The main limitations of known methods and technologies currently used in DSS are to solve difficult formalized problems due to insufficient efficiency in solving problems of learning, setting up and adapting to the problem area, processing incomplete and inaccurate source information, interpreting data and accumulating expert knowledge, the same presentation of information coming from different sources, etc. These limitations in DSS can be addressed using the synergies between multi-agent systems (MAS) and case-based reasoning (CBR). Thus, DSS research based on MAS, which uses CBR, to increase the effectiveness of the implementation of mechanisms for learning and adaptation to the specifics of the problem environment are important and relevant.
The paper aims to develop intelligent CDSS using multi-agent technologies, which is to study methods aimed at integrating agents into CDSS, as well as algorithms for using precedent-based reasoning to increase the ability of agents to make decisions. The result of the study is the creation of a software architecture that increases the efficiency of information processing in intelligent CDSS and allows the use of the developed methods and software systems that correspond to specific applications. The proposed methods and algorithms can be used in solving specific decision-making problems in medicine.
The general structure of multi-agent CDSS for diagnosing diseases is shown in Fig. 1 and consists of an interface module, an execution module and a knowledge module [16, 17]:
The interface module includes interface agents that provide access to decision agents. Access to the execution module and the knowledge module is restricted only to the agents who are there.
The execution module mainly provides services and calculations that may be needed to solve a particular problem and includes: a coordinating agent, a decision-making agent, and a reporting agent.
The knowledge module contains domains and domain-independent problem-solving knowledge. At this level is the database agent, which provides the data that is needed for other agents.
The model of multiagent DSS is represented as follows [18]:
H Y , (1) where H (i) HD (i) , ( i 1, M ) – matrix representation of initial treatment and diagnostic data, Y YD , (Y ) .
For value Y made a plural of problems, the solution of which pertain to the set D ={ DH, DMAS }, where DH={Par1, Par2,…, Par14} – task of processing medical-diagnostic data of measuring devices; DMAS ={DPr, DPlan,, DCoord, DReport}, where DPr={Dident, Dmatch, Dselect }, where Dident, – feature identification task; Dmatch – matching task; Dselect – resolution selection task (selection or ranking); DPlan – the task of building a plan to solve current problems, DCoord – the task of coordinating group actions of agents; DReport – services for generating various reports. The result of the DMAS problem is a set:
MAS={A,E,Res}, (2) where agents A represented as
E – the environment in which the connections between agents and the environment are implemented; Res is a service-oriented environment that provides a Service to support the identification of possible heart disease Case.
Reflection T : HD YD allows for everyone HD (i) discover Yj YD ( j 1,Q , Q – quantity of diseases), which is the resolve to the task DΞ.
Value Yj YD used to formulate decisions about a person's health and to develop further behavioral tactics. As a result of solving the problem DΞ, a service is provided Service( H ,Y ) Fasaa(T( HD ,YD ))
The criterion for the effectiveness of development is the satisfaction of requirements k : ( Di D )( p max ) &( r max , where Di – is the subproblem of the combined problem
Multi-agent technology is used to obtain, reuse and adapt precedents in the CBR system. The structure that combines MAS and CBR technology to support dynamic knowledge sharing is shown in Fig. 2. Each agent is represented using the following set in the CBR MAS (2):
Ai ( Aia ,Eie ,Fae, Ais ,Fses,Fse ) (3) where Aia – agents actions set: i=Search: search agent ASearch – if a new task is introduced, the search agent solves the function of finding the case most similar to the problem. The search ends when the agent finds, indexes of all cases relevant to the problem; i=Adapt: adaptation agent АAdapt – determines the difference between the selected cases and the problem, and if necessary apply a set of necessary regulations to make the used resolve best suited to the renewed task; i=Improvе: improvement agent АImprovе – he criticizes the adapted solution against the previous results. Comparing it with similar solutions in previous cases is the best way. If there is a known error for the derivative solution, the system then decides whether the similarity is sufficient to suspect that the new solution will fail; i=Exe: execution agent АExe – after the decision is criticized, the executor applies a refined solution to the current problem; i=Estim: evaluator АEstim – if the results are as expected, no further analysis is performed and the cases and their solutions are saved or used to solve future problems. If not, the decision will be reconsidered; i=User: user interface agent АUser; i=Coord: coordinator agent ACoord; i=Dec: decisionmaking agent ADec; i=Report: report agent AReport; i=DB: database agent ADB; Eie – set of environmena tal conditions; Fae :Aai Eei 2 A i – functions of environmental behavior; Asi – multiple internal states of agents (transmits, receives or waits for messages); Fses :Asi E ei Asi – agent recovery functions; Fse :Asi E ei – decision-making functions for the agent to act on the current internal state:
The precedent search agent ASearch deals with the process of finding a precedent similar to a new task, which can be focused on different purposes, for example: to find such a precedent so that the resulting diagnosis is the most reliable; find a precedent with a diagnosis that has a minimum execution time; find a precedent for which the time to obtain a new solution will be minimal (minimum modifications); find a precedent that reflects the most modern (late) experience, etc. As a rule, the task of finding a precedent DPr is divided into three subtasks: 1) Dident, – the choice of properties for comparison (feature identification); 2) Dmatch – comparison; 3) Dselect – choice of solution (selection or ranking).
The first subtask involves the selection of properties that should be taken into account when finding a better precedent. Precedent-based diagnostic systems typically use a goal, an initial state, and sometimes a description of failures that may arise when solving a problem. The subtask of the comparison is to find one or more diagnoses that (partially) match the selected properties with the current problem. The comparison can be performed in several different ways. The most common are full comparison and use of similarity measures (sometimes, similarity metrics). When fully comparing, a search is made for precedents in which the selected properties exactly match the corresponding properties of the new task. If the system does not find the desired solution, then the generalization of the selected properties of the new task is performed and then again an attempt is made to find a precedent.
A similarity measure is a function that calculates the degree of similarity between a given precedent and a new problem. The simplest measure of similarity can be defined as the number of common subgoals. More flexible similarity measures calculate the weighted sum of the total sub-goals and the degree of similarity of the initial states. Scales are used to balance the importance and usefulness of tasks. Weights can be determined by constants for all precedents at once, but in more complex subject areas, each precedent has its own weight vector.
As a result of the operation of the precedent search agent, several relevant precedents can be found. In this case, the planner must select one or more of them. When using similarity measures, this problem is solved automatically. But other methods can be used, based, for example, on the degree of generalization of the precedent (the more specific the precedent, the less effort will be required to adapt).
Consider ways to submit and remove precedents. At the first stage of the CBR-cycle - obtaining precedents - the degree of similarity of the current situation with precedents from the base of precedents (BP) is determined and then removed in order to solve this new problem situation. For the successful implementation of precedent-based reasoning, it is necessary to ensure the correct extraction of precedents from the BP. The choice of the method of obtaining precedents is directly related to the method of setting precedents and, accordingly, to the organization of the BP.
BP can be part of the knowledge base of intelligent CDSS, but can also act as an independent component of the system. The structure of the BP significantly affects the various indicators of the system and, in particular, the time of search and retrieval of precedents. There are different ways of presenting and storing precedents - from simple (linear) to complex hierarchical [19]. It should be noted that simple methods, which are usually based on relational database technology, require a much lower costs of implementation, as well as for the maintenance and support of PSUs than complex ones. However, it may take much longer to find a solution in the simple presentation of precedents than in other more complex ways of presenting and preserving precedents.
The precedent in the general case may include the following components [19, 20]: task description (problem situation); problem solving (diagnosing the problem situation and DM recommendations); the result (or forecast) of the application of the solution. The main ways of presenting precedents can be divided into the following groups: parametric; object-oriented; special (in the form of trees, graphs, logical formulas, etc.). In most cases, for the presentation of precedents is a simple parametric representation, the representation of the precedent in the form of a set of parameters with specific values and solutions (diagnosis and recommendations of DM):
CASE (x1,..., xn , R) , (4) where x1, ..., xn ‒ parameters of the situation which describes the given precedent; x1∈X1, ..., xn∈Xn; n ‒ parameters number of the precedent; X1, ..., Xn ‒ valid values range of respective parameters; R ‒ diagnose and recommendations of the DM. Additionally, description of the found resolution use description and comments may be present.
There are a number of methods for extracting precedents and their modifications, the most common of which are: Nearest Neighbor (NN), decision tree method, knowledge-based method, artificial neural networks, etc. [10], which can use different metrics. The method of NN is used in the work, which allows to easily calculate the degree of similarity of the current problem situation and precedents with BP.
Let the given precedent C and the current problem situation T be given in the n-dimensional space of signs (properties, qualities). Then the degree of similarity or proximity S (C, T) of the precedent C and the current situation T can be determined using one of the metrics that determine the distance between two points xiC and xiT , in particular, the Euclidean distance:
n dCT (xiC xiT )2 . (5)
i1
Next, according to the selected metric, the distance from the target point corresponding to the current problem situation to the points representing the precedents from the BP is determined, and the closest point to the target is selected. To determine the value of the degree of similarity S (C, T) it is necessary to find the maximum distance dmax in the selected metric, using the boundary of the parameter ranges to describe the initial xi,in, in and final xi,fin, precedents, i = 1, ..., n. Then you can calculate the value of the degree of similarity:
S(C,T ) 1 dCT dmax , (6) which can take values from 0 to 1.
The work of the adaptation agent АAdapt will consist of two parts: first, in substituting the purpose and initial conditions of the selected precedent for the purpose and initial conditions of the new task; secondly, in ensuring the correctness of the diagnosis after replacement. After substituting the goal and the initial conditions of the diagnosis may require changes. Some steps of the diagnosis may be unnecessary, as the goal they served to disappear has disappeared. New goals may emerge, and changing the initial conditions may make a number of steps unsuitable. Correction of the diagnosis can be performed either automatically or by the user.
The result of the search and adaptation phases is a plan to solve the current problem. To close the CBR cycle and replenish the knowledge system, it is necessary to maintain the current planning of the experience. Training is based on observations of the appropriate response to the plan.
After the execution agent applies the solution found to the current problem, the evaluation agent analyzes the results and if the results are as expected, no further analysis is performed and the cases and their solutions are stored or used to solve future problems. If not, the decision will be reconsidered.
The user interface agent АUser can be divided into many agents, depending on the needs of the system. The hospital is most successful in using the division into two types of users: 1) engineers (this type of users is engaged in setting up and monitoring the work of the decision-making system); 2) doctors (this type of users analyzes patients' data).
Each of the different users has its own interface agent. Typically, a user interface agent is a web interface that allows users to interact with CDSS, but there can be several different types of such interfaces, for example, it can be: a desktop application or a mobile application. With this interface, users can fill out online forms to interact with CDSS, download documents, and perform data analysis. The physician can provide hospital patient data for analysis using a decision system, and the engineer can download additional data. The user interface agent is responsible for receiving data from users and providing results. It also tracks user settings, can customize the interface depending on the role of the user and his goals, for example, the interface agent can hide some engineering information from doctors.
The user agent interface module contains methods for inter-agent communication as well as receiving input from the user. The process module contains scripts and methods for capturing user input and passing it to the CDSS coordinating agent. The functions of the interface agent provide a web interface for interaction with the user, a web page for user input and description of problems, settings are provided, a web page with information about the status of analysis, providing feedback on the status of various processes, a web page containing final results, dynamic creation of HTML-documents with special formatting depending on the user, etc.
The coordinator agent Acoord is responsible for coordination different tasks, which need to be completed while solving cooperative tasks. After getting task from user of interface agent, coordinator agent identifies respected criteria’s, determines alternative, which need to be evaluated, and generates action plan, which is like rating of alternatives. These alternatives can include identification of respectful data sources, query services of other agents and generating reports.
Task of action planning DPlan can be described in the next way:
AP { Aai ,P api ,I api,ap ,t ap,0} (7) where Papi – the set of the agent's perception of the state of the environment; I api – a subset of the internal states of the agent that is part of the set of internal states I I apiI' ; ap PapiI apiI apiAia ; – conversion ratio, which determines that the perception Papi current perception of environment and current internal state of the plan t api ; tap,0I api – starting agents state.
The result of planning is a set of chains of transitions of agents from the initial state to the final, which realizes the goal.
After receiving a request from the coordinating agent for a decision, the process module determines what actions need to be taken to successfully process the request from the user. To do this, it can send requests to the database agent to find additional knowledge about the subject area, and it also sends a request to the decision agent with information about the problem.
The decision-making agent ADec stores in the knowledge module information about possible agents who are able to solve the problem. Using this information and depending on the type of application, the agent must determine, based on the metadata stored in the knowledge module, the module that best handles it, and send it a request for a solution. In our system, such a module is one, it is a decisionmaking module using CBR.
The report agent AReport is located in the execution module and provides users with services for generating various reports on the operation of the system. These can be both text reports and various charts: bar and bar charts; graphics; pie charts; histograms; area diagrams; scatter charts; surface diagrams; pie charts; bubble charts, etc. These reports are based on the information that the agent receives from the database agent and may include a variety of information about the parameters of the distribution of data in the knowledge base.
As an example, these can be histograms of heart disease, shown in Fig. 3. Such information can be very important for the analysis of symptoms that can lead to heart disease. For example, if we construct a histogram of the distribution of various attributes of people in whom heart disease was detected, as shown in Fig. 3, we can see that the number of people with the disease increases sharply after 50 years. All this can be very useful for further diagnosis of heart disease.
The database agent ADB is responsible for tracking what data is stored in the database. The database agent interface module provides a public interface to existing databases. This improves the relationship and allows users to access various data sources that might otherwise be unavailable. The process module provides special and predefined data retrieval capabilities. Based on the user's request, the corresponding requests are created and executed in the data warehouse. The results of these queries are passed to the user or other agents.
The database agent can use multiple sources to generate a response to a query. These can be: SQL databases; NoSQL database; text files of various formats (XML, JSON); external data services, etc. The functions of a database agent are interoperability between agents, a database interface, support for local and global schema, and formatting query results according to user needs. 2.3.
To combine CDSS agents and CBR agents, you need to connect the search agent to the decision agent. The architecture of the system is shown in Fig. 4, and the sequence diagram is shown in Fig. 5. In the CBR system itself, the application first goes to a search agent, which solves the function of finding cases most similar to the problem. It then passes the result to the adaptation agent, which determines the difference between the selected cases and the problem and, if necessary, applies a set of necessary rules to make the old solution best suited to the new problem. The enhancement agent then criticizes the adapted solution against the previous results, and after the solution is criticized, the execution agent applies the refined solution to the current problem. At the end, the evaluator stores the result in the precedent database for further use and sends the result to the decision agent, who in turn returns the result to the user through the coordination agent.
The task of supporting the identification of possible heart disease requires effectively organized information that reflects the experience and knowledge of specialists (experts) in knowledge bases, forecasting possible solutions, their analysis and evaluation, which allows the decision maker (DMP) to more reasonably choose one of possible diagnoses [3]. When determining the diagnosis, the specificity of the bases of diagnoses is that they include heterogeneous knowledge of the subject area, knowledge of many different parameters (age, gender, type of pain, blood pressure, blood sugar, electrocardiogram result, maximum heart rate, etc.), which affect the outcome of the decision. Therefore, the feasibility of designing a multi-agent system to ensure the most rational decision-making has been shown. LEADSTO, Leads to Editor is used to model and implement the interactions between agents of a multiagent system in decision-making for timely response, TTL (Temporal Trace Language) dynamic apparatus to demonstrate the dynamics of agents’ behavior.
For the test system for the diagnosis of heart disease, a data set was used, which has more than 300 records and has 14 attributes: 1. Age 2. Sex (1 – man; 0 – woman) 3. SP – type of chest pain: value 1 – typical stenocardia; value 2 – atypical stenocardia; value 3 – non-anginal pain; value 4 – asymptomatic. 4. Trestbps – blood pressure at rest (in mm Hg. On admission to the hospital). 5. Chol – serum cholesterol in mg/dl. 6. Fbs – blood sugar > 120 mg / dl: 1 – true; 0 – false. 7. Restecg – electrocardiographic result: value 0 – normal; value 1 – the presence of an anomaly of ST-T waves (inversion of T-waves and / or increase in
ST or depression> 0.05 mV); value 2 – showing probable or definite left ventricular hypertrophy according to Estes criteria. 8. Thalach – the maximum heart rate is reached. 9. Exang – exercise-induced stenocardia: 1 – true; 0 – false. 10. Oldpeak – ST depression caused by exercise relative to rest. 11. Slope – the slope of the peak training segment ST: value 1 – rise; value 2 – direct; value 3 – recession. 12. CA – number of large vessels stained by fluoroscopy. 13. Thal – thallium heart scan: 3 ‒ normal (without cold spots); 6 ‒ fixed defect (cold spots during rest and exercise); 7 ‒ reverse defect (when cold spots appear only during training). 14. Pred_attribute – diagnosis of heart disease (condition of angiographic disease): value of 0: < 50% of the narrowing of the diameter; value of 1: > 50% narrowing of the diameter.
To start the system, you must send a request to the interface agent. Then the system begins its work, which will result in the selection of the four most appropriate precedents, in order of increasing distance from the original. Four possible solutions to the problem have been provided for ATS, including a precedent with complete similarity. Therefore, based on the obtained data, it can be concluded that although there is a precedent, which is similar to the initial one with heart disease, but based on the work of CDSS, the chance of diagnosing the disease in a person with these indicators is low. The distribution of time between agents for decision making is shown in Fig. 6. To make one decision, the system needs about 170 milliseconds, as shown in Fig. 6, which is a good indicator, but can be improved if additional decision-making agents are added to the system, which will allow to horizontally scale the resulting system.
Analyzing the obtained data on the distribution of time for decision-making, we can conclude that the decision-making agent occupies about 40% of all calculations in the system. And if we remember that the disadvantages of the CBR include the increase in the search time of the nearest precedents, it turns out that it is necessary to conduct a comparative analysis of the search time depending on the size of the precedent database. The result of testing the performance of the system depending on the number of precedents in the database is shown in Fig. 7.
As a result of testing, we can say that although with the increase in the number of precedents in the database, the execution time really increases, but it is slow and does not significantly affect the overall running time. Despite these shortcomings, the experiment showed the ability of CDSS, so it can be used to make decisions in real conditions.
CDSS is proposed, which is designed to improve health care delivery by improving medical decisions through focused clinical knowledge, patient information, and other medical information. CDSS is based on the use of multi-agent approach and Case-Based Reasoning and consists of modules of interface, execution and knowledge that include various agents. Agents are intelligent and complex software systems that have the ability to adapt to a particular circumstance that causes a change in their behavior or characteristics, to ensure the ability to adapt and ultimately solve the problem before them.
Multi-agent technology is used to obtain, reuse and adapt precedents in the CBR system. The CBR system removes cases related to an existing disease from the database of precedents and solves the issue of deciding the diagnosis of the disease based on the results of previous data on such a disease.
Experimental studies of the proposed CDSS to support the identification of possible heart disease. For the test system for the diagnosis of heart disease, a data set was used, which has more than 300 records and has 14 attributes. The obtained data on the distribution of time for decision-making showed that the decision-making agent occupies about 40% of all calculations in the system. The result of testing the performance of the system, depending on the number of precedents showed that with increasing number of precedents in the database execution time increases, but this is slow and does not significantly affect the overall operating time. Experimental studies show the effectiveness of the proposed solutions: reducing the response time of the system by an average of 15%.