Sorting multi-attribute objects with a reduction of space dimension

Размещено на http://www.allbest.ru/

Institute for Systems Analysis, Russian Academy of Sciences

Sorting multi-attribute objects with a reduction of space dimension

Alexey B. Petrovsky, Gregory V. Royzenson

Abstract

The paper describes a new approach to a successive reduction of attribute space dimension. The space reduction allows us to simplify sorting multiple criteria alternatives and to diminish a complexity and labour-consumption of classification procedure.

Keywords: verbal decision analysis, ordinal classification, multiple criteria alternatives, attributes aggregation, reduction of attribute space dimension

1. Introduction

Sorting objects into several ordered classes by their properties is one of the typical problems in multiple criteria decision aiding, pattern recognition, and other areas. Usually the objects are characterized with many diverse attributes. In real-life situations, the number of such attributes can be large enough (tens and hundreds). The direct sorting alternatives, which are described with a huge number of attributes, is rather difficult and labor-consuming procedure for a decision maker (DM) and requires to use special techniques (Doumpos and Zopounidis, 2002). Additional difficulties appear in the case of verbal attributes, which convolution is impossible and mathematically incorrect. Examples of such problems are the competitive selection of R&D projects estimated by several experts on many qualitative criteria (Petrovsky and Shepelev, 1993), an evaluation of credit quality for commercial banks (Asanov et al., 2001).

In this paper, the new approach to sorting multi-attribute objects is presented. The interactive procedure for constructing the aggregated classification rules combines a successive reduction of multi-attribute space dimension and various methods of verbal decision analysis (Larichev, 2006). Thus, a large number of initial attributes are combined into a small number of criteria with verbal scales that correspond to the demanded classes. The suggested procedure has a block structure, which depends on DM preferences. The method provides for a simple construction of decision rules for sorting multi-attribute objects with a high efficiency, and allows us to explain the final object assignment.

2. Ordinal classification of multicriteria alternatives

The problem of multicriteria ordinal classification is formulated as follows. The given set of alternatives A₁,…,A_p is estimated upon many criteria K₁,…,K_m. Each criterion K_i has an ordered discrete scale X_i={x_i¹,…,x_i^gi}, i=1,…,m. The ordered classes (categories) C₁,…,C_q are given. It is required to divide an initial collection of multiple criteria alternatives into the classes.

Let us consider some of methodological approaches to solving this problem. In the ELECTRE TRI method (Roy and Bouyssou, 1993) alternatives estimated upon many criteria with numerical scales and different weights are assigned to the given classes. The assignment of an alternative to a class is based on the category boundaries, which are constructed using special indexes of concordance and discordance by pair-wised comparing alternatives. These indexes are calculated in the process of problem solution where DM appoints criteria weights. This procedure has no strict verification.

An interactive classification, where DM preferences are represented by a linear utility function as a weighted sum of many scalar criteria, has been proposed in (Kцksalan and Ulu, 2003). A determination of criteria weights is a very hard problem for DM. Applications of methods with many criteria convolution to solving classification tasks of large dimension do not allow us to explain the obtained results due to an impossibility to recover input data by aggregated figures.

In the rough set approach to sorting multicriteria alternatives (Greco et al., 2002), DM preferences are described with decision rules, which suggest an assignment of the alternative to a given classes with different approximations. The rough set technique operates with a rather big collection of sorting decision rules that is difficult for DM analysis and demands specific learning on training samples

Methodology of the verbal decision analysis (Larichev and Olson, 2001), (Larichev, 2006) suggests another approach to ordinal classification of multicriteria alternatives, which are represented as corteges of verbal criteria estimates in the space X₁?…?X_m. DM preferences are checked on consistency, and the revealed inconsistencies are excluded. While building of large dimension classification it is very important to take into account possibilities of human being. According to psychological experiments (Larichev, 2006), persons usually use various simplified strategies with only part of criteria for sorting alternatives if a number of criteria is more than 5, a rate of criteria is more than 4, and a number of decision classes is more than 5.

The above difficulties may be overcome by reducing of multi-attribute space dimension. The suggested approach is based on a successive hierarchical aggregation of attributes into a small number of criteria with verbal ordinal scales, and various tools of verbal decision analysis.

3. Reduction of Space Dimension

The problem of reduction of multi-attribute space dimension is formally as follows:

X₁…X_m Y₁…Y_n, n<m,

where X₁,…,X_m are sets of initial attributes, Y₁,…,Y_n are sets of new attributes, m and n are dimensions of initial and new attribute spaces. Attribute sets X_i={x_i¹,…,x_i^gi}, i=1,… m, and Y_j={y_j¹,…,y_j^hj}, j=1,…,n are ordered.

The offered approach to attributes' aggregation is based on DM preferences. First of all, a collection of initial characteristics for the objects considered is to be formed in the collaboration with DM. These characteristics depend on the problem specificity and may be given beforehand or generated in the course of problem analysis. Further, basing on DM experience and intuition, initial characteristics are combined into groups of criteria with a small number (3-5) of verbal grades on ordinal scales. The content of criteria and rating scales are defined by DM. Criteria scales should reflect, on the one hand, the aggregated qualities of objects, and, on the other hand, be clear to DM in the final classification of objects.

The ISKRA method (Russian abbreviation of the words: Hierarchical Structuring CRiteria and Attributes) includes following steps (Royzenson, 2005). The enumeration of all basis indicators (for example, a list of object technical characteristics), which form the lower level of hierarchical system of initial attributes, is prepared. The scale with numerical (point-wise, interval) or verbal estimates is formed for each basis indicator. Rating scales of basis indicators may coincide with usually used on practice, or to be constructed specially. DM defines a number, structure and content of criteria for the every hierarchy level. DM establishes also which basis indicators are to be considered as independent criteria and which basis indicators are combined within complex criteria. DM may use different procedures for composing scales of complex criteria.

The simplest way for composing a scale of complex criterion is a stratification technique that is based on cutting a multi-attribute space with parallel hyperplanes. Every layer consists of initial estimates' combination and represents one of generalized estimate on the scale of complex criterion. A number of layers (scale grades) is determined by DM. For instance, initial estimates may be combined into the generalized estimate as follows: the best initial estimates compose the best generalized estimate, average initial estimates compose average generalized estimates, and the worst initial estimates compose the worst generalized estimate.

A more complicated composition of complex scale is based on verbal decision analysis methods (Larichev, 2006), where all possible combinations of initial estimates in the attributes space are considered as multi-attribute alternatives. The ZAPROS method allows us to construct a joint ordinal scale of complex criterion from estimates of basis indicators. The ORCLASS and CYCLE methods are intended for building a full and consistent classification of corteges of initial estimates where classes form an ordinal scale of complex criterion.

The procedure of attributes' aggregation has a successive character. The obtained groups of criteria may be combined, in turn, into new groups (the following level of hierarchy) and so on. Various approaches for composing scales of complex criteria may be used on the different stages of procedure. For example, the stratification technique may be used for generating some complex criteria, and multicriteria ordinal classification for another criteria.

attribute space dimension classification

4. Construction of classification rules

In the case of sorting multicriteria alternatives, the procedure of attributes' aggregation possesses a hierarchical structure and consists of several unified blocks of classification executed successively step by step. DM selects these blocks depending on the problem specificity.

Every classification block of the i-th hierarchical level includes any attribute set and one complex criterion. Corteges of estimates on attribute scales represent classified objects. Decision classes of the i-th level are grades on a scale of complex criterion. In the classification block of the next hierarchical level, complex criteria of the i-th level are considered as attributes, which estimate corteges represent new classified objects in the reduced attribute space, and decision classes of the (i+1)-th level will be now grades on a scale of new complex criterion.

The procedure is repeated up to a single complex criterion of the top hierarchical level, which rating scale provides for the required ordered classes C₁,…,C_q. Thereby a correspondence between classes C₁,…,C_q and a collection of initial attributes' corteges (that is a set X₁…X_m of all possible combinations of estimate grades on scales of criteria K₁,…,K_m) is established. The found boundaries of classes allow us to sort easily the real multiple criteria alternatives A₁,…,A_p.

Let us consider a model procedure of building classification rules when alternatives are described by 8 basis attributes K₁,…,K₈. A scale X_i of attribute K_i has two or three verbal ordinal estimates 0,1,2, where 0 designates the best estimate, 1 - average (or the worst), 2 - the worst. A set of alternatives is to be divided into five ordered classes C₁,…,C₅ (see Fig.1).

For example, the attribute K₁ characterizes “Degree of the problem performance” that may be estimated as follows: 0 - the problem is solved completely, 1 - the problem is solved partially, 2 - the problem is not solved. The attribute K₃ estimates “Timely goal achievement” as follows: 0 - really, 1 - non-really. The complex criterion of top level is “Productivity”, which grades on estimate scale (high, good, average, low, unsatisfactory) define 5 ordered decision classes.

Fig. 1 The scheme of constructing complex criteria and composing rating scales

Suppose also that DM has decided to aggregate the initial basis attributes K₁, K₂, K₃ into a complex criterion AK₁, the attributes K₅, K₆, K₇ into a complex criterion AK₂, and the attributes K₄, K₈ into a complex criterion AK₃. The complex criteria AK₁, AK₂, AK₃ have ordinal scales with three grades as Y₁={0,1,2}; Y₂={0,1,2}; Y₃={0,1,2}. Here values 0,1,2 designate verbal estimates, which names depend on a content of corresponding complex criteria, and represent decision classes of the first hierarchical level.

In order to construct scales of complex criteria AK₁, AK₂, AK₃, DM has used, for instance, the stratification technique. According DM preferences, for the complex criteria AK₁ the class 0 (the grade y₁¹=0) includes the following estimate combinations: (000),(001),(010),(100); the class 1 (the grade y₁²=1) includes the estimates (011),(021),(101),(111),(201),(110),(200),(020),(210), (120); the class 2 (the grade y₁³=2) includes the estimates (121),(211),(221),(220). For the complex criteria AK₂ the class 0 (the grade y₂¹=0) consists of the best estimates (000); the class 1 (the grade y₂²=1) consists of the average estimates (001),(011),(101),(100),(010),(110); the class 2 (the grade y₂³=2) consists of the worst estimates (111). For the complex criteria AK₃ the class 0 (the grade y₃¹=0) includes the estimates (00); the class 1 (the grade y₃²=1) includes the estimates (01),(10),(02),(11),(20); the class 2 (the grade y₃³=2) includes the estimates (12),(21),(22).

Consider now the collections of all estimates (y₁^a,y₂^b,y₃^c) by the complex criteria AK₁, AK₂, AK₃ as new classified objects of the next hierarchical level where decision classes C₁,…,C₅ are the grades of scale Z={z¹,z²,z³,z⁴,z⁵} of the top level complex criterion. Combining analogously the attributes (criteria) AK₁, AK₂, AK₃, one may obtain the following results: the class C₁ (the grade z¹) consists of the best estimates (000); the class C₂ (the grade z²) consists of the estimates (100),(010),(001),(002),(101),(011),(200),(110),(020); the class C₃ (the grade z³) consists of the estimates (102),(012),(201),(111),(021),(210),(120); the class C₄ (the grade z⁴) consists of the estimates (202),(112),(022),(211),(121),(220),(212),(122),(221); the class C₅ (the grade z⁵) consists of the worst estimates (222).

Thus, the real alternatives estimated by initial criteria are assigned directly to the generated decision classes. Note that this procedure requires essentially less effort than other methods of multicriteria ordinal classification.

5. Conclusion

The new approach to ordinal classification of alternatives estimated by many criteria with verbal scales is suggested. The developed procedure of hierarchical aggregation of initial attributes allows us to reduce considerably a dimension of attribute space, and to diminish essentially time that DM spends for solving a problem. The procedure provides for a possibility to generate different collections of criteria and find the best quality solution.

This approach helps to investigate systematically the available information, analyze and explain the final decision. The procedure of reducing attribute space dimension has been applied to an evaluation of credit quality for commercial banks (Asanov et al., 2001) and a multicriteria choice of high-performance computing clusters (Royzenson, 2005).

References

1. Asanov, A.A., P.V.Borisenkov, O.I.Larichev, E.V.Naryzhny, G.V.Royzenzon (2001); The CYCLE multiple criteria classification method and its application to analyzing credit risk; Economic-Mathematical Methods, Vol. 37, No 2 (pp. 14-21) (in Russian).

2. Doumpos, M. and C.Zopounidis (2002); Multicriteria Decision Aid Classification Methods; Kluwer Academic Publishers, Dordrecht.

3. Greco, S., B.Matarazzo, R.Slowinski (2002); Rough sets methodology for sorting problems in presence of multiple attributes and criteria; European Journal of Operational Research, Vol.138 (pp. 247-259).

4. Kцksalan, M. and C.Ulu (2003); An interactive approach for placing alternatives in preference classes; European Journal of Operational Research, Vol.144 (pp. 429-439).

5. Larichev, O.I. and D.L.Olson (2001); Multiple Criteria Analysis in Strategic Siting Problems; Kluwer Academic Publishers, Boston.

6. Larichev, O.I. (2006); Verbal Decision Analysis; Nauka, Moscow (in Russian).

7. Petrovsky, A.B. and G.I.Shepelev (1993); Competitive selection of R&D projects by a decision support system; User-Oriented Methodology and Techniques of Decision Analysis and Support (ed. J.Wessel, A.Wierzbicki); Springer Verlag, Berlin (pp. 288-293).

8. Roy, B. and D.Bouyssou (1993); Aide Multicritere a la Decision: Methodes et Cas; Economica, Paris.

9. Royzenson, G.V. (2005); Method of reducing attribute space dimension for a description of complex systems in decision making problems; News of Artificial Intelligence; No 1 (pp. 18-28) (in Russian).

Размещено на Allbest.ru