DEX Methodology: Three Decades of Qualitative Multi-Attribute Modeling

Headnote

Keywords: decision support, multi-criteria decision making, qualitative multi-attribute modeling

Received: December 11, 2012

DEX is a qualitative multi-attribute decision modeling methodology that integrates multi-criteria decision modeling with rule-based expert systems. The method was conceived in 1979. Since, it has been continuously developed and implemented in a wide range of computer programs that have been applied in hundreds of practical decision-making studies. Here we present its main methodological concepts, contributions to the theory and practice of decision support, and outline a history of its development and evolution.

Povzetek: V prispevku predstavljamo najpomembnejse koncepte metodologije DEX, njene prispevke k teoriji in praksi podpore pri odloèanju ter orisemo njen zgodovinski razvoj.

(ProQuest: ... denotes formula omitted.)

1 Introduction

DEX is a qualitative decision support methodology for the evaluation and analysis of decision alternatives. Conceived more than thirty years ago, the methodology has a long history of scientific, technical and practical contributions. It represents a pioneering approach of combining the "classical" numerical multi-criteria decision modeling with rule-based expert systems. This approach led to a development of new algorithms and techniques for acquisition and representation of decision knowledge and evaluation and analysis of decision alternatives. DEX was implemented in three generations of software - called DECMAK, DEX and DEXi - and embedded into many other computer programs and systems. It was used in hundreds of practical applications, nationally and internationally. Despite its age, DEX is still very much alive: it is actively used in international projects and cited in international scientific publications, it is taught in schools, there are ongoing new developments and strong plans for future work. Taking all this into account, DEX can be rightly considered an important long-term achievement of Slovenian research in artificial intelligence and decision support.

2 On origins and evolution of DEX

The foundations of what eventually became DEX were set up in Durham, UK, by Efstathiou and Rajkoviè (1979). Influenced by fuzzy set theory, they proposed to use words rather than numbers in decision models. They proposed a tabular representation of utility relations, one of the key concepts of DEX methodology. Further development (Figure 1) continued in Slovenia, mainly through collaboration of Vladislav Rajkoviè and Marko Bohanec. In the 1980's, the methodology was called DECMAK (Bohanec et al., 1983). The original idea was conceptually extended to cope with hierarchies of attributes (Rajkoviè, Bohanec, 1980) and to facilitate the acquisition and explanation of decision knowledge (Rajkoviè, Bohanec, 1988a; Rajkoviè et al., 1988). The approach was successfully used in several important applications, such as evaluation of computer systems (Bohanec et al., 1983), personnel management (Rajkoviè et al., 1988) and enrolment into nursery schools (Olave et al., 1989).

The name DEX (Decision EXpert) was coined in 1987 when the method was implemented as an expert system shell for decision making (Bohanec, Rajkoviè, 1990). This was a state-of-the-art implementation of the complete methodology. In the 1990's, DEX contributed to solution of complex decision making problems in industry (Bohanec, Rajkoviè, 1999), health-care (Bohanec et al., 2000a), project evaluation (Bohanec et al., 1995), housing (Bohanec et al., 2001), and sports (Bohanec et al., 2000b). An important related achievement was also HINT, a method for automatic problem decomposition (Zupan et al., 1999). Used as a machine learning algorithm, HINT is capable of developing DEX models from data.

The third distinctive period begun in year 2000 with the implementation of DEXi (Jereb et al., 2003), a stripped-down and user-friendly computer program aimed primarily at education. This paved the DEX's way into Slovenian secondary schools and universities (Krapez, Rajkovic, 2003). In spite of its simplicity, DEXi turned out extremely useful even for most difficult decision-making tasks. Some outstanding international applications included European projects Sol-Eu-Net on data mining and decision support integration (Mladenic et al., 2003), Healthreats on health threats and crises management (Znidarsic et al., 2009), ECOGEN, SIGMEA and Co-Extra on genetically modified crops (Bohanec et al., 2008; Znidarsic et al., 2008, Bohanec et al., 2013), and e-LICO on data mining workflows (Znidarsic et al., 2012). Other applications of DEX include studies in public administration (Leben et al., 2006), medicine (Sustersic et al., 2009), agronomy (Griffiths et al., 2010; Pavlovic et al., 2011; Pelzer et al., 2012) and tourism (Stubelj Ars, Bohanec, 2010). In this period we also proposed a new method for automatic revision of DEX models (Znidarsic, Bohanec, 2007), conceived a DSS tool for modeling uncertain knowledge called proDEX (Znidarsic et al., 2006), and developed new methods for option ranking based on copulas (Mileva-Boshkoska, Bohanec, 2012).

3 Principles of DEX

The basic principles of DEX are intentionally kept very simple. The decision maker is requested to define a qualitative multi-attribute model, with which decision alternatives are evaluated and analyzed. In principle, the model represents a decomposition of the decision problem into smaller, less complex subproblems. The decomposition is represented by a hierarchy of attributes. The DEX model consists of:

* Attributes: variables that represent basic features and assessed values of decision alternatives.

* Scales of attributes: these are qualitative and consist of a set of words, such as: 'excellent', 'acceptable', 'inappropriate', etc. Usually, scales are ordered preferentially, i.e., from bad to good values.

* Hierarchy of attributes: represents the decomposition of the decision problem and relations between attributes; higher-level attributes depend on lower-level ones.

* Decision rules: tabular representation of a mapping from lower-level attributes to higher-level ones. In principle, a table should specify a value of the higher-level attribute for all combinations of values of its lower-level attributes.

Figures 2 and 3 illustrate these components on a simple model for the evaluation of cars (Bohanec, 2012).

The hierarchy in Figure 2 consists of ten attributes. There are six input attributes representing observed features of cars: BUY.PRICE, MAINT.PRICE, #PERS, #DOORS, LUGGAGE and SAFETY. These are aggregated through three intermediate attributes COMFORT, TECH.CHAR. and PRICE into the overall evaluation, which is represented by the root attribute CAR.

Figure 3 shows decision rules that correspond to the CAR attribute. The rules map all the combinations of values of PRICE and TECH.CHAR. into the values of CAR. The attributes PRICE and TECH.CHAR. have three and four values, respectively, so the number of rows in the table is 3¡Ñ4=12. Each row provides a value of CAR for one combination of the values of PRICE and TECH.CHAR. Interpreted as an elementary decision rule, the fifth row, for example, means that

...

Decision rules, such as the ones in Figure 3, have to be defined for all aggregate attributes in the model. The CAR model thus contains three more rule sets that correspond to the intermediate attributes COMFORT, TECH.CHAR. and PRICE. See Bohanec (2012) for further details.

Decision alternatives (i.e., cars in this example) are evaluated by aggregation that is performed from input attributes towards the root of the DEX model. Figure 4 shows the evaluation of three cars: the values corresponding to the attributes COMFORT, TECH.CHAR, PRICE and CAR were evaluated by DEX according to input data provided by the decision maker (i.e., values corresponding to the leaves of the hierarchy) and corresponding decision rule sets. The evaluation of Car3 in Figure 4 illustrates the DEX's way of handling missing information: unknown SAFETY (denoted by '*') is handled by considering all possible values of this attribute, what results in a set of values (rather than a single value) assigned to attributes TECH.CHAR. and CAR.

In the final stage, DEX models are typically used for various analyses of alternatives, such as 'what-if' and sensitivity analysis. For example, a typical DEX's analysis is called "plus-minus-1", which investigates the effects of changing each input attribute by one step down (-1) or up (+1) in the attribute scale. Figure 5 shows the results for Car2, which has been originally evaluated as 'good'. Small changes of BUY.PRICE severely affect this evaluation, which becomes 'unacc' and 'exc' when buying price increases or decreases by one step, respectively. Two other attributes, MAINT.PRICE and SAFETY, have the same influence, while the evaluation is unaffected by changes of #PERS, #DOORS and LUGGAGE.

4 Important concepts

Conceptually, DEX is a combination of two approaches: multi-criteria decision analysis (MCDA) and expert systems. From MCDA (Figueira et al., 2005; Bouyssou et al., 2006), DEX borrows the idea of evaluation and analysis of decision alternatives using a hierarchically structured model. DEX departs from using numerical variables and weight-based utility functions by introducing concepts from expert systems: qualitative (symbolic, linguistic) variables, if-then rules, dealing with uncertainty, high emphasis on transparency of models and explanation of evaluation results. DEX has some similarities with two other independently developed approaches: DRSA (Greco et al., 2001) and Doctus (Baracskai, Dörfler, 2003).

Very early in DEX's history it became clear that working directly with model components was not practical and that additional tools were needed to acquire and validate model components, as well as to evaluate, analyze and explain the alternatives. The following concepts and principles were the most important for practical adoption of DEX.

Acquisition of decision rules: Direct definition of tables, such as the one in Figure 3, is tedious and errorprone, and computer-based assistance becomes vital, particularly when rule sets are large. In its early days, DECMAK offered an interactive command-line ASK/ANSWER dialogue. Now, DEXi supports three strategies for the definition of decision rules: direct, 'use scale orders', and 'use weights' (Bohanec, 2012, p. 35).

Validating rules: In comparison with common expert systems, DEXi rules are simple and restricted by the scales of the corresponding attributes, making them suitable for validation of completeness (to which extent they define the mapping) and consistency (are they in conflict with each other). This improves the overall quality of models.

"The user is always right" principle: In spite of consistency checking, DEX gives precedence to information provided by the decision maker. Thus, any decision rule, even if inconsistent, is taken literally and never modified by DEX. In case of inconsistency, the user is given a warning, though.

Dynamic aspects of model creation: The model as shown in Figures 2 and 3 is static. However, in practice, such models are continuously modified and improved: parts of the model are created, extended, moved around or deleted. There are many such operations, such as deleting or adding an attribute, reordering attributes, removing a scale value, etc. All these operations must be supported by appropriate algorithms so that the information already contained in the model is retained as much as possible after each operation. It is particularly important to properly handle decision rules. DEX does implement these operations and typically handles them transparently "behind the scenes".

Bridging the gap between qualitative and quantitative MCDA: The traditional MCDA heavily relies on weights to define the importance of attributes. Naturally, there are no weights in decision rules. However, it turned out to be practically important to deal with weights, so these were included into DEX, too. A partial transformation between attribute weights and rules is possible in both ways (Bohanec, 2012): (1) weights are estimated from defined rules by linear approximation, and (2) the values of undefined decision rules are determined on the basis of already defined rules and user-specified weights.

Handling uncertainty in alternatives and rules: By definition, an expert system must be able to deal with incomplete and uncertain knowledge. The early DECMAK was already able to evaluate incompletely defined alternatives using fuzzy and probabilistic aggregation (Bohanec et al., 1983). In most of the later implementations, the uncertainty in rules was only partly modeled by value intervals. Znidarsic et al. (2008) extended this approach to using probabilistic distributions in decision rules.

Transparency and explanation: For practice, it is essential that DEX models appear transparent and comprehensible to the user. DEX always provided mechanisms for presenting decision rules in a userfriendly way, from ID3-based decision tree learning algorithms in the early software, to advanced rule generators in the modern DEXi.

Analyses of alternatives: In addition to the mere evaluation of alternatives, the decision support methodology has to provide advanced tools for the analysis of alternatives. For this purpose, DEX includes a number of methods, such as "what-if" analysis, "plusminus- 1" analysis (Figure 5) and selective explanation.

5 Software

Three main generations of qualitative modeling computer programs have been developed so far:

1. DECMAK was released in 1981 for operating systems RT-11, VAX/VMS and later for MS DOS. The program had an interactive command-line interface and facilitated the development of a tree of attributes, fuzzy evaluation of alternatives, ASK/ANSWER rule acquisition dialogue, and representing rule tables with complex rules and decision trees. Eventually, due to memory limitations of computers at that time, additional programs were developed separately to form a software suite, which supported functions such as analysis and ranking of alternatives, graphical presentation of decision rules and calculation of weights. In its final form, the DECMAK suite consisted of 19 programs (Bohanec, Rajkoviè, 1988b).

2. DEX was released in 1987 as an integrated interactive computer program for MS DOS. DEX facilitated interactive model creation and editing, probabilistic and fuzzy evaluation of alternatives, report generation, and selective explanation of evaluation results. In 1995, a supplementary program for ranking of alternatives called Vredana was implemented for MS Windows (Set et al., 1995).

3. DEXi, released in 2000, is an interactive educational program for MS Windows. It supports model creation and editing, tabular acquisition of rules, value-set-based evaluation of alternatives, "what-if" analysis, "plus-minus-1" analysis, selective explanation and comparison of options, textual and graphical reports. DEXi is publicly available (http://kt.ijs.si/MarkoBohanec/dexi.html) and its use is free for non-commercial applications.

DEXi is further extended with supporting tools, each related to a specific methodological aspect. They include proDEX (implementation of some DEX extensions, for example using probabilistic values in decision rules), JDEXi (an open-source Java library for evaluation of alternatives), DEXiEval (a command-line utility program for evaluation of alternatives), and DEXiTree (a program for pretty drawing of DEXi trees).

The evaluation part of DEX was often embedded into other software systems. Typical examples include:

* Talent, a system for advising children into sports (Bohanec et al., 2000b),

* a system for risk assessment of diabetic foot care (Bohanec et al., 2000a),

* ESQI: a web page on ECOGEN soil quality index (http://kt.ijs.si/MarkoBohanec/ESQI/ESQI.php),

* SMAC, an advisory system on maize co-existence (Bohanec et al., 2007), and

* a motorway traffic management system (Omercevic et al., 2008).

6 Applications

Ability to tackle complex, real-life problems, is one of DEX's strongest points. In its early days, we kept records of its applications and counted as many as thirty until 1988 (Bohanec, Rajkovic, 1988a). The number of applications continued to grow, but their recording became more and more difficult with the spread of the method and free use of the software. Today, we roughly estimate that DEX has been applied to several hundreds of real-life decision support projects. Considering prototypes and student work, the number of all developed DEX models likely exceeds several thousands.

The areas of DEX applications are very diverse. So far, DEX was used to evaluate technologies, companies, projects, and services. Important problem areas include health care, public administration, agronomy, food production, ecology, land use planning, tourism, housing, traffic control, sports and finance.

Practical experience indicates that DEX is particularly suitable for solving complex decision problems that require judgment and qualitative knowledge-based reasoning, dealing with inaccurate and/or missing data, as well as the analysis and justification of evaluation results. Typically, these problems require large models (with 15 or more attributes) and/or involve many alternatives (10 or more).

7 Future of DEX

Currently, the main software tool for developing DEX models is DEXi. Even after 12 years since its first release, it still seems suitable for education and typical decision making problems, and will - with proper maintenance - continue to serve for these purposes in the future. However, really difficult decision problems require a more powerful methodology and more advanced software (Znidarsic et al., 2008). The advances in software engineering require new architectures, such as web-based, cloud-based and mobile. There is a need for a DEX library, DEX services and a set of tools for embedding DEX models into other systems, such as information systems, web portals and services, and mobile devices.

For these reasons, we plan to extend the DEX methodology and implement it in a new generation of software (Trdin, Bohanec, 2012). The most challenging methodological advances include:

* Introduction of numeric attributes, facilitating the use and interplay of both qualitative and quantitative attributes in an integrated model.

* Full implementation of probabilistic and fuzzy distributions for characterization of decision rules and alternatives.

* Supporting attribute hierarchies, that is, directed acyclic graphs rather than trees.

* General aggregation functions to facilitate the use of all types of aggregation functions known in MCDA.

* Relational models that extend the methodology from "flat" to relational alternatives, that is, alternatives composed of sets of subcomponents.

References

References

[1] Baracskai, Z., Dörfler, V. (2003): Automated fuzzy clustering for Doctus expert system. Proc. Int. Conf. on Computational Cybernetics, Siófok, Hungary.

[2] Bohanec, M., Bratko, I., Rajkovic, V. (1983): An expert system for decision making. Processes and Tools for Decision Making (ed. H.G. Sol), North- Holland, 235-248.

[3] Bohanec, M., Rajkovic, V. (1988a): Knowledge acquisition and explanation for multi-attribute decision making, Proc. 8th Int Workshop "Expert Systems and Their Applications AVIGNON 88", Vol. 1, 59-78, Avignon.

[4] Bohanec, M., Rajkovic, V. (1988b): DECMAK: An expert system shell for multi-attribute decision making. Report DP-5031, Ljubljana: Jozef Stefan Institute.

[5] Bohanec, M., Rajkovic, V. (1990): DEX: An expert system shell for decision support, Sistemica 1(1), 145-157.

[6] Bohanec, M., Rajkovic, V., Semolic, B., Pogacnik, A. (1995): Knowledge-based portfolio analysis for project evaluation, Information & Management 28, 293-302.

[7] Bohanec, M., Rajkovic, V. (1999): Multi-attribute decision modeling: Industrial applications of DEX, Informatica 23, 487-491.

[8] Bohanec, M., Zupan, B., Rajkovic, V. (2000a): Applications of qualitative multi-attribute decision models in health care, International Journal of Medical Informatics 58-59, 191-205.

[9] Bohanec, M., Rajkovic, V., Leskosek, B., Kapus, V. (2000b): Expert knowledge management for sports talent identification and advising process. Decision Support through Knowledge Management (eds. S.A. Carlsson, P. Brezillon, P. Humphreys, B.G. Lundberg, A.M. McCosh, V. Rajkovic, V.), IFIP, 46-59.

[10] Bohanec, M., Cestnik, B., Rajkovic, V. (2001): Qualitative multi-attribute modeling and its application in housing. Journal of Decision Systems 10, 175-193.

[11] Bohanec, M., Messéan, A., Angevin, F., Znidarsic, M. (2007): SMAC advisor: A decision-support tool on maize co-existence. GMCC-07, Third International Conference on Coexistence between Genetically Modified (GM) an non-GM based Agricultural Supply Chains. Seville, Spain, 20th- 21st November 2007. Luxembourg: European Commission, 119-122.

[12] Bohanec, M., Messéan, A., Scatasta, S., Angevin, F., Griffiths, B., Krogh, P.H. (2008): A qualitative multi-attribute model for economic and ecological assessment of genetically modified crops. Ecological Modelling 215, 247-261.

[13] Bohanec, M. (2012): DEXi: Program for Multi- Attribute Decision Making, User's Manual, Ver. 3.04. IJS Report DP-11153, Ljubljana: Institut Jozef Stefan.

[14] Bohanec, M., Bertheau, Y., Brera, C., Gruden, K., Holst-Jensen, A., Kok, E.J., Lécroart, B., Messéan, A., Miraglia, M., Onori, R., Prins, T.W., Soler, L.- G., Znidarsic, M. (2013): The Co-Extra decision support system: A model-based integration of project results. Genetically modified and nongenetically modified food supply chains: Coexistence and traceability (ed. Bertheau, Y.), 461- 489, Wiley-Blackwell.

[15] Bouyssou, D., Marchant, T., Pirlot, M., Tsoukias, A., Vincke, P. (2006): Evaluation and Decision Models with Multiple Criteria. Springer.

[16] Efstathiou, J., Rajkovic, V. (1979): Multiattribute decisionmaking using a fuzzy heuristic approach. IEEE Trans. on Systems, Man, and Cybernetics, SMC-9, 326-333.

[17] Figueira, J., Greco, S., Ehrgott, M. (2005): Multi criteria decision analysis: State of the art surveys. Springer.

[18] Greco, S., Mattarazzo, B., Slowinski, R. (2001): Rough sets theory for multicriteria decision analysis. European Journal of Operational Research 129, 1-47.

[19] Griffiths, B.S., Ball, B.C., Daniell, T.J., Hallett, P.D., Neilson, R., Wheatley, R.E., Osler, G., Bohanec, M. (2010): Integrating soil quality changes to arable agricultural systems following organic matter addition, or adoption of a ley-arable rotation. Applied Soil Ecology 46(1), 43-53.

[20] Jereb, E., Bohanec, M., Rajkovic, V. (2003): DEXi: Racunalniski program za vecparametrsko odlocanje, Moderna organizacija, Kranj.

[21] Krapez, A., Rajkovic, V. (2003): Tehnologije znanja pri predmetu informatika. Zavod RS za solstvo.

[22] Leben, A., Kunstelj, M., Bohanec, M., Vintar, M. (2006): Evaluating public administration e-portals. Information polity 11(3/4), 207-225.

[23] Mileva-Boshkoska, B., Bohanec, M. (2012): Ranking of qualitative decision option using copulas. Operations research proceedings 2011 (eds. D. Klatte, H.-J. Lüthi, K. Schmedders). Springer, 103-108.

[24] Mladenic, D., Lavrac, N., Bohanec, M., Moyle, S. (eds.) (2003): Data mining and decision support: Integration and collaboration. Kluwer Academic Publishers.

[25] Olave, M., Rajkovic, V., Bohanec, M. (1989): An application for admission in public school systems. Expert Systems in Public Administration (eds. I.Th.M. Snellen, W.B.H.J. van de Donk, J.-P. Baquiast), Elsevier, 145-160.

[26] Omercevic, D., Zupancic, M., Bohanec, M., Kastelic, T. (2008): Intelligent response to highway traffic situations and road incidents. Proc. TRA 2008, 21-24 April 2008, Ljubljana, 1-6.

[27] Pavlovic, M., Cerenak, A., Pavlovic, V., Rozman, C., Pazek, K., Bohanec, M. (2011): Development of DEX-HOP multi-attribute decision model for preliminary hop hybrids assessment. Computers and Electronics in Agriculture 75, 181-189.

[28] Pelzer, E., Fortino, G., Bockstaller, C., Angevin, F., Lamine, C., Moonen, C., Vasileiadis, V., Guérin, D., Guichard, L., Reau, R., Messéan, A. (2012): Assessing innovative cropping systems with DEXiPM, a qualitative multi-criteria assessment tool derived from DEXi. Ecological Indicators 18, 171-182.

[29] Rajkovic, V., Bohanec, M. (1980): A cybernetic model of the computer aided decision making process. 9th Int. Congress on Cybernetics, Namur, 8-13th September, 185-199.

[30] Rajkovic, V., Bohanec, M., Batagelj, V. (1988): Knowledge engineering techniques for utility identification. Acta Psychologica 68(1-3), 271- 286.

[31] Stubelj Ars, M., Bohanec, M. (2010): Towards the ecotourism: A decision support model for the assessment of sustainability of mountain huts in the Alps. Journal of Environmental Management 91(12), 2554-2564.

[32] Set, A., Bohanec, M., Krisper, M. (1995): Vredana: Program za vrednotenje in analizo variant v vecparametrskem odlocanju [Vredana: A program for evaluation and analysis of alternatives in multiattribute decision making]. Proceedings of the Fourth International Electrotechnical and Computer Science Conference ERK-95, Portoroz, Slovenia. Ljubljana: Slovenska sekcija IEEE, 157- 160.

[33] Sustersic, O., Rajkovic, U., Dinevski, D., Jereb, E., Rajkovic, V. (2009): Evaluating patient's health using a hierarchical multi-attribute decision model. Journal of International Medical Research 37, 1646-1654.

[34] Trdin, N., Bohanec, M. (2012): Extending the multi-criteria decision making method DEX. Proc. 4th Jozef Stefan International Postgraduate School Students Conference (eds. D. Petelin, A. Tavcar, B. Kaluza), 25 May 2012, Ljubljana, Slovenija, 182- 187.

[35] Zupan, B., Bohanec, M., Demsar, J., Bratko, I. (1999): Learning by discovering concept hierarchies, Artificial Intelligence 109, 211-242.

[36] Znidarsic, M., Bohanec, M., Zupan, B. (2006): proDEX - A DSS tool for environmental decisionmaking. Environmental Modelling & Software 21, 1514-1516.

[37] Znidarsic, M., Bohanec, M. (2007): Automatic revision of qualitative multi-attribute decision models. Foundations of Computing and Decision Sciences 32(4), 315-326.

[38] Znidarsic, M., Bohanec, M., Zupan, B. (2008): Modelling impacts of cropping systems: Demands and solutions for DEX methodology. European Journal of Operational Research 189, 594-608.

[39] Znidarsic, M., Bohanec, M., Lavrac, N., Cestnik, B. (2009): Project self-evaluation methodology: The Healthreats project case study. Proc. Information Society 2009, Ljubljana, 85-88.

[40] Znidarsic, M., Bohanec, M., Trdin, N. (2012): Qualitative assessment of data-mining workflows. Fusing decision support systems into the fabric of the context (eds. A. Respício, F. Burstein). Amsterdam: IOS Press, 75-88.