Keywords

1 Introduction

Three-way classifications are constructed based on the notions of acceptance, rejection and non-commitment if the classifications are used for decision making [14, 15]. Given U as a finite nonempty set of objects and C as a undefinable target concept, the aim of three-way classifications is to partition U based on C into three disjoint regions [14]. The three-way classifications can be formulated from different models or theories, such as rough sets and its extensions, fuzzy sets, shadow sets, interval sets [15]. We focus on the three-way classifications in the context of rough sets in this research. The determination of rough sets based three-way classification regions is a critical research question. In order to solve this question, we need some criteria or measures, such as accuracy, confidence, generality, coverage, cost, and uncertainty, to evaluate the three-way classifications [2, 20]. These criteria evaluate three-way classifications from different views. When multiple criteria are involved to determine three-way classifications, especially, the involved criteria are conflicting to each other, we have to find an approach to balance them or to reach a compromise among them.

Determining three-way classifications based on multiple criteria can be formulated as a typical multiple criteria decision making (MCDM) problem. MCDM deals with complicated decision making problems which involve multiple conflicting criteria [19]. It aims to obtain a suitable solution among various options based on the performance of evaluation on multiple criteria, and the selected solution can represent a tradeoff among the involved criteria. Many concepts, techniques and approaches have been proposed to resolve MCDM problems, including: analytic hierarchy process [9], dominance-based rough set approach [4], weighted sum model [11], and others [10]. Typically, an MCDM problem contains four basic elements: a set of criteria, a set of alternatives or actions, the outcomes of involved criteria, and a preference structure of criteria [18]. The set of alternatives represents different decision options. The set of criteria is used to evaluate alternatives. The outcomes of involved criteria mean the evaluations for the set of alternatives based on multiple criteria. The preference structure guides in selecting an appropriate alternative [18].

Game theory is a mathematical tool to study the conflict and cooperation among decision makers [6]. MCDM problems can be formulated as competitive games with multiple players and strategies. Using game theory to solve MCDM problems has been attracting much attention [3, 7]. Game-theoretic rough set model (GTRS) is an advancement in determining suitable partition of three-way regions by formulating competitive or coordinative games between multiple measures [12, 13]. The essential idea of GTRS is to implement games to obtain suitable three-way classifications in the rough set context when multiple measures are involved to evaluate three regions [1]. GTRS combine game theory and rough sets to solve MCDM problems in rough sets and three-way classifications. In this problem solving process, the selection of game players, the configuration of strategies and the definition of payoff functions are investigated in detail [5, 13]. The aim of GTRS is to improve the rough sets based decision making by finding a compromise among the involved measures.

In this paper, we apply GTRS to determine three-way classifications with the presence of multiple criteria. This process contains three stages, i.e., competitive game formulation, repetition learning, and decision making based on equilibrium. Compared with the conventional MCDM methods, the advantage of applying GTRS in multi-criteria based three-way classifications is twofold. On the one hand, GTRS do not require the predefined weights for criteria or compound decision objectives as the conventional MCDM methods. On the other hand, GTRS are inherently suitable for a competitive environment where involved criteria maximize their benefits and the payoff of each criterion is influenced by other’s strategies, while the conventional MCDM methods ignore that the behaviors of other decision makers may effect their payoffs.

2 Background Knowledge

In this section, we briefly introduce the background concepts about three-way classifications in the context of rough sets, and the criteria of evaluating three-way classifications.

2.1 Rough Sets Based Three-Way Classifications

The three-way classification theory was outlined by Yao in [14, 15]. It classifies the universe of objects U into three disjoint regions based on a undefinable target concept C. We can construct three-way classifications with rough sets and its extensions. Suppose the universe of objects U is a finite nonempty set. Let \(E\subseteq U \times U\) be an equivalence relation on U, where E is reflexive, symmetric, and transitive [8]. For an element \(x\in U\), the equivalence class containing x is given by \([x]=\{y\in U|xEy\}\). The family of all equivalence classes defines a partition of the universe and is denoted by \(U/E = \{[x] | x\in U\}\), that is the intersection of any two elements is an empty set and the union of all elements are the universe U [8]. For an undefinable target concept \(C\subseteq U\), probabilistic rough sets utilize conditional probability Pr(C|[x]) as evaluation function and thresholds \((\alpha , \beta )\) to define three-way regions of C, i.e., positive, negative, and boundary regions of the concept C [16]:

$$\begin{aligned} POS_{(\alpha ,\beta )}(C)&=\bigcup \{[x]\mid [x] \in U/E, Pr(C|[x]) \ge \alpha \},\nonumber \\ NEG_{(\alpha ,\beta )}(C)&=\bigcup \{[x]\mid [x] \in U/E, Pr(C|[x]) \le \beta \}, \nonumber \\ BND_{(\alpha ,\beta )}(C)&=\bigcup \{[x]\mid [x] \in U/E, \beta< Pr(C|[x]) < \alpha \}. \end{aligned}$$
(1)

These three-way regions are pair-wise disjoint and their union is the universe of objects U according to Eq. (1). They form a tripartition of the universe U. The family of the three regions constitute a three-way classification model:

$$\begin{aligned} \pi _{(\alpha ,\beta )}(C)=\{POS_{(\alpha ,\beta )}(C), BND_{(\alpha ,\beta )}(C), NEG_{(\alpha ,\beta )}(C)\} \end{aligned}$$
(2)

When we use this three-way classification to classify objects, acceptance and rejection decision rules can be induced from positive and negative regions, respectively.

2.2 Evaluating Three-Way Classifications

Given a target concept C and a pair of probabilistic thresholds \((\alpha , \beta )\), we can obtain a three-way classification according to Eq. (1). Many criteria or measures have been proposed to evaluate three-way classifications [17, 20]. The accuracy and coverage are two most commonly used measures to evaluate the performance of three-way classifications [21].

The criterion accuracy intends to capture the degree of classification correctness of three-way classifications. It is calculated as the ratio of the number of correctly classified objects by a three-way classification model and the number of objects that can be classified by this model. The range of an accuracy value is between 0 and 1. The accuracy of a three-way classification \(\pi _{(\alpha , \beta )}(C)\) is defined as:

$$\begin{aligned} Acc(\pi _{(\alpha , \beta )}(C))=\frac{|C\bigcap POS_{(\alpha , \beta )}(C)|+|C^c\bigcap NEG_{(\alpha , \beta )}(C)|}{|POS_{(\alpha , \beta )}(C)|+|NEG_{(\alpha , \beta )}(C)|}. \end{aligned}$$
(3)

The criterion coverage intends to express the applicability of three-way classifications. It is the ratio of the number of objects that can be classified by a three-way classification to the number of objects in the universe U. It expresses the proportions of objects that can be classified by a three-way classification model. The coverage of a three-way classification \(\pi _{(\alpha , \beta )}(C)\) is defined as:

$$\begin{aligned} Cov(\pi _{(\alpha , \beta )}(C))=\frac{|POS_{(\alpha , \beta )}(C)|+|NEG_{(\alpha , \beta )}(C)|}{|U|}. \end{aligned}$$
(4)

We would like to obtain a high level of classification accuracy and a high level of classification coverage for three-way classifications. A high level of accuracy means we can make more accurate classification decisions based on this three-way classification model. A high level of coverage means we can classify more objects by using this three-way classification model. In general, a more accurate three-way classification model tends to be weaker in applicability or coverage. Similarly, three-way classifications with a high coverage level may not be very accurate. It may not be wise to consider only one criterion and ignore the others in order to obtain suitable three-way classifications. Please note that three-way classifications can be constructed from many different methods or theories, and it is independent on rough sets and its extensions. The measures discussed here can be used to evaluate three-way classifications formulated by other theories.

3 Applying GTRS in Multi-criteria Based Three-Way Classifications

Determining three-way classifications based on multiple criteria can be formulated as a multi-criteria decision making problem. In order to make the problem easy to understand and solve, assuming that two criteria \(c_1\) and \(c_2\) are considered to determine the partition of three regions in a three-way classification. When more than two criteria are involved, the problem solving process is similar. The four elements of this MCDM problem are:

  • The set of criteria contains two criteria \(c_1\) and \(c_2\);

  • The set of alternatives contains all possible probabilistic threshold pairs \((\alpha _1,\) \( \beta _1),(\alpha _2, \beta _2),..., (\alpha _k, \beta _k)\), where \(0\le \beta _i\le 0.5\le \alpha _i\le 1\) and \(1\le i\le k\);

  • The outcomes of criteria with different alternatives represent the values of two criteria \(c_1\) and \(c_2\) under all possible probabilistic threshold pairs;

  • The preference of decision makers is to maximize their own criteria values.

These MCDM elements can match the elements of a game defined in GTRS. Applying GTRS in multi-criteria based three-way classifications includes three stages, namely competitive game formulation, repetition learning process, and decision making based on equilibrium, respectively. Each stage contains different tasks and some of tasks are covered in two stages, as shown in Fig. 1.

Fig. 1.
figure 1

The three stages of applying GTRS

Full size image

3.1 Competitive Game Formulation

In game-theoretic rough sets, there are three elements when formulating a game G, that is, game players set O, strategy sets performed by the players S, and the payoff set of players u, and \(G=\{O, S, u\}\) [5]. In the game formulation stage, the three elements of a game are specified. In fact, the elements of a game correspond to the basic elements of MCDM problems.

Game Players. The set of game players contains two criteria \(c_1\) and \(c_2\), that is \(O=\{c_{1}, c_{2}\}\). The game players represent the criteria that are used to evaluate three-way classifications. Each player evaluates three-way classifications from its own perception, and they have opposite interests when evaluating a three-way classification.

Initial Thresholds. The initial thresholds \((\alpha ,\beta )\) are defined and they can be any thresholds values that satisfy the constraint \(0\le \beta \le 0.5 \le \alpha \le 1\). For example, we can set initial thresholds as \((\alpha ,\beta )=(0.5, 0)\). Two players start from the initial thresholds and perform their strategies to change the initial thresholds. The setting of initial thresholds can directly influence the strategies of players. For example, when initial thresholds are set as \((\alpha ,\beta )=(0.5, 0)\), which means \(\alpha \) and \(\beta \) get the minimum values in their own limits, the strategies can only be set as increasing \(\alpha \) and \(\beta \). Similarly, if initial thresholds are set as \((\alpha ,\beta )=(1, 0.5)\), which means \(\alpha \) and \(\beta \) get the maximum values in their own limits, the strategies can only be set as decreasing \(\alpha \) and \(\beta \).

Strategies. The set of strategies or actions S contains two sets of strategies performed by the game players, i.e., \(S=\{S_{1}, S_{2}\}\), where \(S_{1}=\{s_1,s_2,...,s_{k1}\}\) is a set of possible strategies or actions for player \(c_{1}\) , and \(S_{2}=\{t_1,t_2,...,t_{k2}\}\) is a set of possible strategies or actions for player \(c_{2}\). All these strategies are the changes of probabilistic thresholds \(\alpha \) and \(\beta \). Two players may have different strategies. For example, the player \(c_1\)’s strategies can be the increase of \(\alpha \), \(S_{1}=\{ \alpha \text { increases } 0.05\), \(\alpha \text { increases }0.1\), \(\alpha \text { increases }0.15\}\). The player \(c_2\)’s strategies can be the increase of \(\beta \), \(S_{2}=\{\beta \text { increases } 0.05\), \(\beta \text { increases }0.1\), \(\beta \text { increases }0.15\}\).

A strategy profile \(p = \{p_1, p_2\}\) is a particular play of a game, in which player \(c_1\) performs the strategy or action \(p_1\) and player \(c_2\) performs the strategy or action \(p_2\), here \(p_1\in S_{1}\) and \(p_2\in S_{2}\).

Payoff Functions. The set of payoff functions results from players performing strategies \(u=\{u_{1}, u_{2}\}\). The payoff of player \(c_1\) under the strategy profile \(p = \{p_1, p_2\}\) is denoted as \(u_1(p)=u_1(p_1, p_2)\). The payoff of player \(c_2\) under the strategy profile \(p = \{p_1, p_2\}\) is denoted as \(u_2(p)=u_2(p_1, p_2)\). The payoff functions of two players are defined by the criteria they are representing. The payoff of each player depends on the strategies or actions performed by both game players. The strategy performed by one game player can influence the payoff of the other player. For example, if the initial thresholds are \((\alpha ,\beta )=(0.5,0)\), the player \(c_1\) performs the strategy \(s_1\), i.e., \(\alpha \text { increases } 0.05\) and the player \(c_2\) performs the strategy \(t_3\), i.e., \(\beta \text { increases }0.15\). The probabilistic thresholds under the strategy profile \(p = \{s_1, t_3\}\) is \((\alpha ,\beta )=(0.55,0.15)\). The payoffs of players are the values of the criteria they represent when \((\alpha ,\beta )=(0.55,0.15)\).

Payoff Tables. For a two-player game, we can build a payoff table to represent the game. The Table 1 shows a payoff table. Each cell of the payoff table corresponds to a strategy profile and contains a pair of payoff values based on that strategy profile.

Table 1. A payoff table of a two-player game
Full size table

3.2 Repetition Learning Mechanism

The second stage formulates competitive games repeatedly with different initial thresholds and strategies to approach a balanced solution. In other words, if the values of thresholds obtained in the current game are not good enough to apply in decision making, we can repeat the game with the new thresholds. This stage first analyzes pure strategy equilibrium of the game and then check if the stop condition is satisfied.

Pure Strategy Equilibrium. The game solution of pure strategy Nash equilibrium is typically used to determine possible game outcomes in GTRS. In a two-player game, the strategy profile \((s_i, t_j)\) is a pure strategy Nash equilibrium, if for players \(c_{1}\) and \(c_{2}\), \(s_i\) and \(t_j\) are the best responses to each other. This is expressed as [6],

$$\begin{aligned} \forall s_i^{'} \in S_1,\;\;\; u_1(s_i, t_{j})&\geqslant u_1(s_i^{'},t_{j}), \,\,\,\, \text { where } s_i \in S_1 \text { and } s_i^{'} \ne s_i,\nonumber \\ \forall t_j^{'} \in S_2,\;\;\; u_2(s_i, t_{j})&\geqslant u_2(s_i,t_j^{'}), \,\,\,\, \text { where } t_j \in S_2 \text { and } t_j^{'} \ne t_j. \end{aligned}$$
(5)

Equation (5) may be interpreted as a strategy profile such that no player would like to change his strategy or they would loss benefit if deriving from this strategy profile, provided this player has the knowledge of other player’s strategies.

After analyzing the equilibrium, we check if the stop condition is satisfied. If the stop condition is not satisfied, new thresholds values will be set as initial thresholds and another game will be formulated. For example, the initial thresholds are \((\alpha , \beta )\), equilibrium analysis shows that the result thresholds are \((\alpha ^{\prime }, \beta ^{\prime })\) and the stop condition is not satified. In the subsequent iteration of the game, the initial thresholds will be set as \((\alpha ^{\prime }, \beta ^{\prime })\).

3.3 Making Decision Based on Equilibrium

The last stage contains setting the stop conditions and making the final decision based on the equilibrium.

Stop Conditions. We need to stop the iterations at the proper time in order to obtain the balanced thresholds. This requires proper stop conditions be defined. There are many possible stop conditions, for example, thresholds \((\alpha ,\beta )\) violate the constraint \(0\le \beta \le 0.5 \le \alpha \le 1\), the payoffs of players are beyond some specific values, a subsequent iteration does not improve previous configurations, or the gain of one player’s payoff is less than the loss of the other player’s payoff in the current game.

Decision Making. The final three-way classification can be defined by the initial thresholds used in the last game.

4 Illustrative Example

In this section, we present an example to demonstrate that a balanced three-way classification can be obtained by applying GTRS when two criteria are involved to evaluate this three-way classification. In the experiment, we use a random generator to generate the probabilistic information of experimental data. The probability \(Pr(X_{i})\) is a random number between 0.001 and 0.1, and the sum of all \(Pr(X_{i})\) is 1. The condition probability \(Pr(C|X_{i})\) is a random number between 0 and 1. Table 2 summarizes probabilistic data about a concept C. There are 20 equivalence classes denoted by \(X_{i} (i=1, 2, ..., 20)\), which are listed in a decreasing order of the conditional probabilities \(Pr(C|X_i)\) for convenient computations.

Table 2. Summary of the experimental data
Full size table

Two criteria accuracy and coverage are used to evaluate three-way classifications defined by different probabilistic thresholds. We can set these two criteria accuracy and coverage as game players, i.e., \(O=\{acc, cov\}\). The strategy set is \(S=\{S_{acc}, S_{cov}\}\). The possible strategies of two players are the changes of thresholds. The initial thresholds are \((\alpha , \beta )=(1, 0.5)\). The player acc tries to decrease \(\beta \), so its strategy set is \(S_{acc}=\{\beta \text { doesn't change}\), \(\beta \text { decreases } 0.05\), \(\beta \text { decreases }0.1\}\). Under these strategies, the corresponding \(\beta \) values are 0.5, 0.45, and 0.4, respectively. The player cov tries to decrease \(\alpha \), so its strategy set is \(S_{cov}= \{\alpha \text { doesn't change}\), \(\alpha \text { decreases }0.05\), \(\alpha \text { decreases }0.1\}\). The corresponding \(\alpha \) values are 1, 0.95, and 0.9, respectively. The payoff functions of two players are defined by the criteria they are representing, i.e., the Eqs. (3) and (4).

Table 3. The payoff table
Full size table

The payoff table is shown in Table 3. The strategy profile \((\beta \text { decreases }0.1\), \(\alpha \) decreases 0.1) is the equilibrium. We set the stop condition as the gain of one player’s payoff is less than the loss of the other player’s payoff in the current game. When the thresholds change from (1, 0.5) to (0.9, 0.4), the accuracy increases from 0.8349 to 0.8825 and the coverage increases from 0.566 to 0.666. We repeat the game by setting \((\alpha ,\beta )=(0.9,0.4)\) as initial thresholds. In the second iteration of the game, the initial thresholds is \((\alpha , \beta )=(0.9, 0.4)\), two players’ strategy sets are \(S_{acc}=\{\beta \text { doesn't change }, \beta \text { decreases } 0.05 ,\beta \text { decreases }0.1\}\) and \(S_{cov}=\{\alpha \text { doesn't change },\alpha \text { decreases }0.05, \alpha \text { decreases }0.1\}\), respectively. The competition will be repeated three times. The result is shown in Table 4. In the third iteration, we can see that the gain of the payoff values of player acc is 0.0021 which is less than the loss of payoff values of player cov 0.025. The repetition of game is stopped and the final result is the initial thresholds of the third competitive game \((\alpha , \beta )=(0.8, 0.3)\).

Table 4. The repetition of games
Full size table

5 Conclusion

We use game-theoretic rough sets to determine multi-criteria based three-way classifications. When multiple criteria are involved to determine three-way classifications, we formulate this problem as a multi-criteria decision making problem. Within the GTRS framework, multiple criteria that are used to evaluate three-way classifications are set as game players. The competitive games are formulated to solve the conflict among criteria. The strategies of both players are the changes of thresholds. Both players can gradually approach the balanced probabilistic thresholds by repeatedly modifying the initial thresholds and finding the pure strategy equilibrium of repeated games. GTRS provide a feasible and effective method for multi-criteria based three-way classifications in the context of rough sets. GTRS accommodate and meet the rough sets related special requirements when formulating games between criteria. GTRS do not rely on any predefined knowledge about criteria or compound objective functions. Moreover, GTRS are more suitable to solve a competitive situation where involved criteria have opposite interest and the payoff of each criterion is influenced by other criteria’s strategies.