Data-driven sequential three-way decisions for unlabeled information system

Abstract

Based on the granular computing and three-way decisions theory, the sequential three-way decisions (S3WD) model implements the idea of progressive computing. However, almost S3WD models are established based on labeled information system, and there is still a lack of S3WD model for processing unlabeled information system (UIS). In this paper, to solve the issue of given accepted number for UIS, a data-driven sequential three-way decisions (DDS3WD) model is proposed. Firstly, from the perspective of similarity computed by TOPSIS, a general three-way decisions model for UIS based on decision risk is presented and its shortcomings are analyzed. Then, a concept of optimal density difference is defined to establish the DDS3WD model for UIS by updating attributes. Finally, the related experiments show that DDS3WD is feasible and effective for dealing with UIS under the condition of given accepted number of objects.

Keywords

Sequential three-way decisions unlabeled information system data-driven optimal density difference

1 Introduction

Based on both probabilistic rough sets [30, 31] and decision theory, the three-way decisions (3WD) model was proposed by Yao [32, 33] in the view of decision risk. A domain is divided into three disjoint regions (positive region, negative region and boundary region) by considering the minimum decision risk in 3WD model. The rules generated from the positive region represent the action of acceptance; the rules generated from the negative region represent the action of rejection; the rules generated from the boundary region represent the action of deferment. The theory of 3WD extends the semantics of probabilistic rough set and simulates the human thinking mode in solving problems [34]. In recent years, the 3WD model is studied by many scholars in various fields and many achievements have been achieved, such as decision making [12, 13], three-way decisions spaces [4, 8], cognitive concept learning [10, 22] social networks [7], classification [11, 37], clustering [25, 36] and recommendation [38].

As well know, the cognitive mechanism of “large-scale priority” [2] is utilized to solve complex problem by human, that is, a problem is gradually computed by employing coarse-to-fine information granularity, which is called progressive computation [23]. As a typical multi-step approach in granular computing (GrC) theory [1 , 34], the sequential three-way decisions (S3WD) model [35] is introduced by Yao based on 3WD theory, which implements the human multi-granularity thinking to solve complex problems. In S3WD model, the problem can be processed in multi-granularity spaces by gradually switching the granularity layer from coarser to finer. In the view of multi-granularity rough sets (MGRS) [17, 18], with the granularity being finer, the information granules will gradually become smaller in S3WD model. Recently, a great deal of research works on S3WD were achieved [3 , 41]. Yang [27] established a general framework of S3WD and further proposed a multilevel incremental mechanism for complex problem solving. Zhang [41] constructed the optimistic and pessimistic S3WD models with intuitionistic fuzzy number by considering both cost parameters and attribute values. By considering user requirements, Yang [26] developed an optimization mechanism to select granularity based on S3WD model with rough fuzzy sets. Hu [5 , 20] pointed that the existing three-way decisions are the special examples of three-way decisions spaces and further established the multi-granulation three-way decisions space. In the aspect of application, Ju [9] proposed a novel sequential three-way classifier by considering the principle of justifiable granularity. Savchenko [21] presented an algorithm based on S3WD to address the issue of insufficient speed in image recognition when the number of classes is rather large. Zhang [39] introduced a S3WD model by extracting a multi-granularity feature set to balance misclassification cost and time cost in autoencoder. However, the threshold pairs of each granularity space in the almost S3WD models mentioned above are acquired by approximating a target concept of information system. That is, these models are established for processing labeled information system. However, to date, for unlabeled information systems (UIS), few existing models for making sequential three-way decisions are proposed in the research filed.

As shown in Fig. 1, in the process of selecting excellent employees from 10 employees, a company plans to use 2 opportunities to improve the ability of employees by training course. According to the final skill score from high to low, the top 5 employees need to be selected from 10 employees as the excellent employees. Herein, Skill1, Skill2 and Skill3 denote the scores of three skills of employees, and the blue, gray and green region denotes the accepted, deferred and rejected decisions in Fig. 1. In Fig. 1, each skill score would be updated 2 times according to each examination, and the classification results (the employees are divided into three pair-wise disjoint regions as accepted, deferred and rejected region) need to be obtained. In order to decrease the cost of examinations and training course, the company only further trains and tests the employees in deferred region, that is, the skill score of employees in accepted and rejected region will not be updated. Suppose the accepted employees are {x₁, x₂} → {x₁, x₂, x₃} → {x₁, x₂, x₃, x₄, x₅} with respect to each selection, finally, 5 excellent employees are selected. However, in the above process, how to obtain the threshold pairs to divide the universe into three regions and achieve the progressive selection until the top 5 are selected is still an issue. By considering dynamic decision making with updating attribute values, the aim of this paper is to establish a sequential three-way decisions model for UIS when the accepted number of objects is given. There are two assumptions in this paper as follows:(1) The higher (lower) attribute value of an object, the higher (lower) chance to be an excellent object;(2) The attribute value of an object is improved after each update. Obviously, the above assumptions are in accord with practical application.

Fig. 1

Progressive selection for excellent employees.

As well known, technique for order preference by similarity to an ideal solution (TOPSIS) [4] is one of the multi-attributes decision-making methods, which make use of original data to accurately evaluate objects in an information system. In this paper, to satisfy the above assumptions, the unlabeled information system is preprocessed by TOPSIS. Based on our previous works [26, 40], a data-driven sequential three-way decision model for UIS is proposed. The two main contributions of this paper are as follows: (1) From the perspective of similarity computed by TOPSIS, a general three-way decisions model based on decision risk for UIS is presented, which provide a new way for processing UIS by 3WD theory. (2) For solving the case of given accepted number of objects, based on the concept of optimal density difference, a data-driven sequential three-way decisions (DDS3WD) model for UIS is further proposed, which is adaptive to the updating attribute values.

The remainder of this paper is organized as follows. Related preliminary concepts are introduced in Section 2. In Section 3, a general three-way decisions model for UIS based on decision risk is presented. In Section 4, a concept of optimal density difference is defined and a data-driven sequential three-way decisions (DDS3WD) model for UIS by updating attribute is further proposed. In Section 5, related experiments are provided to verify the effectiveness of DD-S3WD model. Finally, conclusions are drawn in Section 6.

2 Preliminaries

As well known, an information system with label data is also called a decision system. In this paper, we denote a decision system by IS = (U, A = C ∪ D, V, f), where U is a non-empty finite domain, V is the set of all attribute values, C is the set of condition attributes, D is the decision attribute and f : U × A → V is an information function. Similarly, we can define an unlabeled information system as follows,

Definition 1. (Unlabeled Information System) [14, 15] An unlabeled information system is denoted by UIS = (U, C, V, f), where U is a non-empty finite domain, C is the set of condition attributes, V is the set of all attribute values and f : U × C → V is an information function.

Rough sets theory [14] is an effective mathematical tool for handling uncertain concept by using the given information granulation. For an uncertain concept, it can be described by a pair of lower and upper approximation sets.

Definition 2. (Rough Sets) [14, 15] Given a decision system IS = (U, C ∪ D, V, f), R ⊆ C and X ⊆ U, the lower and upper approximation sets of X are defined as follows: $\begin{matrix} \underline{R} (X) = {x \in U | [x]_{R} \subseteq X}, \\ \bar{R} (X) = {x \in U | [x]_{R} \cap X \neq \emptyset}, \end{matrix}$ where [x] _R denotes the equivalence class induced by the equivalence relation U/R, namely, U/R = {[x] _R} = {[x] ₁, [x] ₂, ⋯ , [x] _n}, which is also called a granularity space.

If $\bar{R} (X) = \underline{R} (X)$ , X is a definable set, otherwise X is a rough set. The universe U is divided by positive region, boundary region and negative region, which are defined respectively as follows, $\begin{matrix} PO S_{R} (X) = \underline{R} (X), \\ BN D_{R} (X) = \bar{R} (X) - \underline{R} (X), \\ NE G_{R} (X) = U - \bar{R} (X) . \end{matrix}$

Definition 3. (Probabilistic Rough Sets (PRS)) [30, 31] Given a decision system IS = (U, C ∪ D, V, f) with a pair of threshold α, β (0 ≤ β ≤ α ≤ 1), R ⊆ C and X ⊆ U, the lower and upper approximation sets of X are defined as follows: $\begin{matrix} {\underline{R}}^{(α, β)} (X) = {x \in U | μ ([x]) \geq α}, \\ {\bar{R}}^{(α, β)} (X) = {x \in U | μ ([x]) > β}, \end{matrix}$ where, $μ ([x]) = \frac{| [x] \cap X |}{| [x] |}$ . The universe U is divided by positive region, boundary region and negative region, which can be defined as follows, $\begin{matrix} {POS}_{R}^{(α, β)} (X) & = {x \in U | \bar{μ} ([x]) \geq α} = {\underline{R}}^{(α, β)} (X), \\ {BND}_{R}^{(α, β)} (X) & = {x \in U | β < \bar{μ} ([x]) < α} \\ = {\bar{R}}^{(α, β)} (X) - {\underline{R}}^{(α, β)} (X), \\ {NEG}_{R}^{(α, β)} (X) & = {x \in U | \bar{μ} ([x]) \leq β} \\ = U - {\bar{R}}^{(α, β)} (X) . \end{matrix}$

Take the excellent employees selection for example, the objects in the positive region are all collections of “excellent” objects, and the objects in negative region are all collections of “inferior” objects, while the objects in boundary region are needed to further observation. Based on the definition of positive region, boundary region and negative in region Definition 3, we have the following definition,

Definition 4. (Three-ways Decision Rules) [32, 33] The acceptance, delay and rejection decision rules can be expressed as follows:

If μ ([x]) ≥ α,decide [x] ∈ POS^(α,β);

If β ≤ μ ([x]) < α, decide [x] ∈ BND^(α,β);

If μ ([x]) < β, decide [x] ∈ NEG^(α,β).

From Definition 4, when the threshold pair are determined, objects can then be divided into positive, boundary, or negative regions.

3 A general sequential three-way decisions model for UIS

According to the discussion in Section 1, there is still a lack of 3WD model for UIS under the condition of given accepted number. As well known, for labeled information system, in order to obtain α and β, the classical three-way decisions model [32, 33] is proposed based on the decisions-theoretic rough sets theory according to the minimum expected overall decision risk. 3WD model brings new insight into the problem of parameter setting for the probabilistic rough sets [30]. Similarly, based on the idea of 3WD model [32], a general three-way decisions mode for unlabeled information system is defined in this section. Firstly, TOPSIS [4] is adopted to preprocess the UIS and acquire the membership degree of objects in UIS. The details of TOPSIS is shown in Algorithm 1.

Algorithm 1 Algorithm of TOPSIS

Require: An information system UIS₀ = (U₀, C, V₀, f₀), where U₀ = {x_o1, x_o2, …, x_on} and C = {a₁, a₂, …, a_m}.

Ensure: U_d = {x₁, x₂, …, x_n}.

1: for j = 1 : m do

2: if a_i is a reverse index then

3: $M = max_{1 \leq i \leq n} {f (x_{i}, a_{j})}$ ;

4: X_ij = M - f (x_i, a_j);

5: else X_ij = f (x_i, a_j);

6: end if

7: end for

8: for j = 1 : m do

9: for i = 1 : n $Z_{ij} = X_{ij} / \sqrt{\sum_{i} X_{ij}^{2}}$ ; do

10: end for

11: end for

12: $Z^{+} = (Z_{1}^{+}, Z_{2}^{+}, \dots, Z_{m}^{+}) = (max_{1 \leq i \leq n} {Z_{i 1}}, max_{1 \leq i \leq n} {Z_{i 2}}, \dots, max_{1 \leq i \leq n} {Z_{im}})$ ;

13: $Z^{-} = (Z_{1}^{-}, Z_{2}^{-}, \dots, Z_{m}^{-}) = (min_{1 \leq i \leq n} {Z_{i 1}}, min_{1 \leq i \leq n} {Z_{i 2}}, \dots, min_{1 \leq i \leq n} {Z_{im}})$ ;

14: for i = 1 : n do

15: $D_{i}^{+} = \sqrt{\sum_{j} {(Z_{ij} - Z_{j}^{+})}^{2}}$ ;

16: $D_{i}^{-} = \sqrt{\sum_{j} {(Z_{ij} - Z_{j}^{-})}^{2}}$ ;

17: $s (x_{oi}) = \frac{D_{i}^{-}}{D_{i}^{+} + D_{i}^{-}}$ ;

18: end for

19: Obtain U_d = {x₁, x₂, …, x_n} by sorting U₀ according to s (x_oi) in descend order;

20: Return U_d = {x₁, x₂, …, x_n} and S = {s (x₁) , s (x₂) , …, s (x_n)}.

In this paper, Algorithm 1 is used as data preprocess, which aim to achieve the score set of all objects and the final ranking by this score set. In essence, the score acquired by TOPSIS reflect the similarity between the object and the idealized object, which can be understood as the membership degree to the idealized target. Obviously, for an unlabeled information system, the larger the score of an object is, the more likely an object is to be ideal; inversely, the smaller the score of an object is, the less likely an object is to be ideal. In essence, the score of an object reflects the membership degree that belong to idealized target. Based on the decision risk in 3WD model proposed by Yao, from the perspective of the score, we proposed a three-way decisions model for UIS as follows,

Definition 5. (Three-way Decisions Model for UIS) Suppose an unlabeled information system UIS = (U, C, V, f) with a pair of threshold α, β (0 ≤ β ≤ α ≤ 1), the lower and upper approximation sets are defined as ${\underline{apr}}^{(α, β)} = {x \in U | s (x) \geq α}$ and ${\bar{apr}}^{(α, β)} = {x \in U | s (x) > β}$ . The domain U is divided by positive region, boundary region and negative region, which can be defined as follows: $\begin{matrix} POS = {x \in U | s (x) \geq α} = {\underline{apr}}^{(α, β)}, \\ BND = {x \in U | β < s (x) < α} \\ = {\bar{apr}}^{(α, β)} - {\underline{apr}}^{(α, β)}, \\ NEG = {x \in U | s (x) \leq β} = U - {\bar{apr}}^{(α, β)} . \end{matrix}$

Suppose the action set A = {a_P, a_B, a_N} represents three kinds of actions which are acceptation, rejection and deferred decisions. λ_PP, λ_BP, λ_NP denote the losses incurred for taking actions a_P, a_B, a_N when an object belongs to the accepted objects, respectively. λ_PN, λ_BN, λ_NN denote the losses incurred for taking these actions when an object does not belong to the accepted objects, respectively. Thus, the expected losses associated with taking different actions with object can be expressed as follows, $\begin{matrix} R (a_{P} | x) = λ_{PP} s (x) + λ_{PN} (1 - s (x)), \\ R (a_{B} | x) = λ_{BP} s (x) + λ_{BN} (1 - s (x)), \\ R (a_{N} | x) = λ_{NP} s (x) + λ_{NN} (1 - s (x)) . \end{matrix}$

According to the Bayesian decision rule, the minimum-risk decision rules can be obtained as follows,

(P) If $R (a_{P} | x) \leq R (a_{N} | x)$ and $R (a_{P} | x) \leq R (a_{B} | x)$ , decide x ∈ POS;

(B) If $R (a_{B} | x) \leq R (a_{N} | x)$ and $R (a_{B} | x) \leq R (a_{P} | x)$ , decide x ∈ BND;

(N) If $R (a_{N} | x) \leq R (a_{B} | x)$ and $R (a_{N} | x) \leq R (a_{P} | x)$ , decide x ∈ NEG.

Obviously, the above rules are only related to the loss functions and s (x). Furthermore, similar to the traditional 3WD model, 0 ≤ λ_PP ≤ λ_BP ≤ λ_NP ≤ 1 and 0 ≤ λ_NN ≤ λ_BN ≤ λ_PN ≤ 1 are two reasonable assumptions for constructing our 3WD model. The decision rules can be re-expressed as follows,

(P1) $s (x) \geq \frac{(λ_{PN} - λ_{BN})}{(λ_{PN} - λ_{BN}) + (λ_{BP} - λ_{PP})}$ and $s (x) \geq \frac{(λ_{PN} - λ_{NN})}{(λ_{PN} - λ_{NN}) + (λ_{NP} - λ_{PP})}$ ;

(B1) $s (x) \leq \frac{(λ_{PN} - λ_{BN})}{(λ_{PN} - λ_{BN}) + (λ_{BP} - λ_{PP})}$ and $s (x) \geq \frac{(λ_{BN} - λ_{NN})}{(λ_{BN} - λ_{NN}) + (λ_{NP} - λ_{BP})}$ ;

(N1) $s (x) \leq \frac{(λ_{PN} - λ_{NN})}{(λ_{PN} - λ_{NN}) + (λ_{NP} - λ_{PP})}$ and $s (x) \leq \frac{(λ_{BN} - λ_{NN})}{(λ_{BN} - λ_{NN}) + (λ_{NP} - λ_{BP})}$ .

Combining with the above rules (P1),(B1) and (N1), we can obtain the three parameters α, β, γ respectively,

For rule(P1) $\begin{matrix} α & = \frac{(λ_{PN} - λ_{BN})}{(λ_{PN} - λ_{BN}) + (λ_{BP} - λ_{PP})} \\ = (1 + \frac{λ_{BP} - λ_{PP}}{λ_{PN} - λ_{BN}})^{- 1}, \end{matrix}$ For rule(B1) $\begin{matrix} β & = \frac{(λ_{BN} - λ_{NN})}{(λ_{BN} - λ_{NN}) + (λ_{NP} - λ_{BP})} \\ = (1 + \frac{λ_{NP} - λ_{BP}}{λ_{BN} - λ_{NN}})^{- 1}, \end{matrix}$ For rule(N1) $\begin{matrix} γ & = \frac{(λ_{PN} - λ_{NN})}{(λ_{PN} - λ_{NN}) + (λ_{NP} - λ_{PP})} \\ = (1 + \frac{λ_{NP} - λ_{PP}}{λ_{PN} - λ_{NN}})^{- 1} . \end{matrix}$

From rule (B1), we have β < α; then $\frac{λ_{BP} - λ_{PP}}{λ_{PN} - λ_{BN}} < \frac{λ_{NP} - λ_{BP}}{λ_{BN} - λ_{NN}}$ . Moreover, because $\frac{b}{a} > \frac{d}{c} \Rightarrow \frac{b}{a} > \frac{b + d}{a + c} > \frac{d}{c}$ (a, b, c, d > 0), we have $\frac{λ_{BP} - λ_{PP}}{λ_{PN} - λ_{BN}} < \frac{λ_{NP} - λ_{PP}}{λ_{PN} - λ_{NN}} < \frac{λ_{NP} - λ_{BP}}{λ_{BN} - λ_{NN}}$ .Therefore, 0 ≤ β < γ < α ≤ 1. In this case, the decision rules can be re-expressed as follows:

(P2) If s (x) ≥ α,decide x ∈ POS;

(B2) If β ≤ s (x) < α, decide x ∈ BND;

(N2) If s (x) < β, decide x ∈ NEG.

For simplify, suppose λ_PP = λ_NN = 0, that is, the correct classification cost is equal to 0, and we have $α = \frac{λ_{PN} - λ_{BN}}{λ_{PN} - λ_{BN} + λ_{BP}}$ and $β = \frac{λ_{BN}}{λ_{BN} + λ_{NP} - λ_{BP}}$ . The decision cost from the three regions can be defined as follows, $\begin{matrix} DC (NEG) = \sum_{x \in NEG} s (x) λ_{NP}, \\ DC (BND) = \sum_{x \in BND} s (x) λ_{BP} + (1 - s (x)) λ_{BN}, \\ DC (POS) = \sum_{x \in POS} (1 - s (x)) λ_{PN} . \end{matrix}$ Then, the decision cost DC^(α,β) can be defined as follows, $\begin{matrix} D C & = DC (NEG) + DC (BND) + DC (POS) \\ = \sum_{x \in NEG (X)} s (x) λ_{NP} + \sum_{x \in BND (X)} (s (x) λ_{BP} \\ + (1 - s (x)) λ_{BN}) + \sum_{x \in POS (X)} (1 - s (x)) λ_{PN} . \end{matrix}$

The decision cost DC^(α,β) comes from three regions: positive region, boundary region and negative region. The semantic of DC (POS^(α,β)) is the decision cost when we obtain (P2) rule. Similar semantic could be applied to DC (BND^(α,β)) and DC (NEG^(α,β)).

Definition 6. (Sequential Three-way Decisions Model for UIS) Suppose UIS_i = (U, C, V_i, f_i) be an unlabeled information system, where i = 1, 2, …, M. V_i denotes the i-th updated attribute value. Given a m-levels granular structure GS = (UIS₁, UIS₂, …, UIS_M), the three regions at the i-th level of GS can be defined as follows: $\begin{matrix} {POS}_{i} = {x \in U | s (x) \geq α_{i}}, \\ {BND}_{i} = {x \in U | β_{i} < s (x) < α_{i}}, \\ {NEG}_{i} = {x \in U | s (x) \leq β_{i}}, \end{matrix}$ where, α_i, β_i are two thresholds at the i-th level of GS.

From Definition 6, for an unlabeled information system, the threshold pairs can be obtained from the perspective of similarity. Similar to the classical 3WD model [32], the decision risk is acquired in Definition 5 by computing the the score of objects, in an unlabeled information system. However, for the case of the given accepted number of objects, the acquired threshold pairs will not change with the different UIS as the threshold pairs depend on the loss parameters λ_PP, λ_BP, λ_NP, λ_PN, λ_BN, λ_NN, that is, the threshold pairs are not adaptive, which is not suitable to make sequential three-way decisions model for UIS. Therefore, to solve this problem, from the perspective of similarity, we proposed a novel three-way decision model for UIS based on data-driven in next section.

Example 1. Table 1 is an information table of student academic record. English,Math,Chinese and Sports are condition attributes, which denote the different subjects, respectively.

Table 1
An information table of student performance

Object English Math Chinese Sports

x _o1 96 90 83 82

x _o2 70 70 73 75

x _o3 98 92 87 92

x _o4 70 87 82 60

x _o5 76 94 70 68

x _o6 75 74 66 68

x _o7 67 55 60 45

x _o8 40 45 50 60

Object	English	Math	Chinese	Sports
x _o1	96	90	83	82
x _o2	70	70	73	75
x _o3	98	92	87	92
x _o4	70	87	82	60
x _o5	76	94	70	68
x _o6	75	74	66	68
x _o7	67	55	60	45
x _o8	40	45	50	60

From Table 1, U₀ = {x_o1, x_o2, …, x_on}. According to Algorithm 1, we have the score set of Table 1 in descending order as follows, $\begin{matrix} S_{8} & = {s (x_{1}), s (x_{2}), \dots, s (x_{8})} \\ = {0 . 98, 0 . 88, 0 . 64, 0 . 58, 0 . 56, 0 . 54, 0 . 28, 0 . 15} \end{matrix}$ Based on the traditional 3WD model, we list several threshold pairs to obtain the three region as follows: When α = 0.9, β = 0.1, we have $\begin{matrix} POS = {x_{1}}, \\ BND = {x_{2}, x_{3}, x_{4}, x_{5}, x_{6}, x_{7}, x_{8}}, \\ NEG = \emptyset . \end{matrix}$

When α = 0.8, β = 0.2, we have $\begin{matrix} POS = {x_{1}, x_{2}}, \\ BND = {x_{3}, x_{4}, x_{5}, x_{6}, x_{7}}, \\ NEG = {x_{8}} . \end{matrix}$

When α = 0.6, β = 0.3, we have $\begin{matrix} POS = {x_{1}, x_{2}, x_{3}}, \\ BND = {x_{4}, x_{5}, x_{6}}, \\ NEG = {x_{7}, x_{8}} . \end{matrix}$

From the above example, it exists some problems, for example, when α = 0.9, β = 0.1, the score of x₇ and x₈ is too low to be placed in boundary region, because their potential for improvement is very low. When α = 0.6, β = 0.3, the score of x₃ is not suitable to be placed in positive region directly. Therefore, various decision regions can be obtained according to the different threshold pairs, which is not objective. Furthermore, for the issue of given accepted number, it is not suitable to make two-way decisions by selecting the top k.

4 Data-driven sequential three-way decisions model for UIS

According to the discussion in Section 3, the 3WD model for UIS based on decision risk is not suitable to handle the case of the given accepted number of objects. Moreover, the given threshold is not objective to some extent. To solve the above issues, we proposed a data-driven sequential three-way decisions (DDS3WD) model for UIS in this section. Firstly, a concept of expected density difference according to the mathematical characteristics of a numerical set is defined as follows:

Definition 7. (Expected Density Difference) Let S_n-1 = {s (x₁) , s (x₂) , ⋯ , s (x_n-1)} and S_n = {s (x₁) , s (x₂) , ⋯ , s (x_n-1) , s (x_n)} be two score sets. ${\bar{S}}_{n - 1} = \frac{1}{n - 1} \sum_{i = 1}^{n - 1} s (x_{i})$ and ${\bar{S}}_{n} = \frac{1}{n} \sum_{i = 1}^{n} s (x_{i})$ denote the mean value of S_n-1 and S_n, respectively. $ρ_{n - 1} = \frac{1}{n - 1} \sum_{i = 1}^{n - 1} e^{- {(\frac{s (x_{i}) - {\bar{S}}_{n - 1}}{n - 1})}^{2}}$ and $ρ_{n} = \frac{1}{n} \sum_{i = 1}^{n} e^{- {(\frac{s (x_{i}) - {\bar{S}}_{n}}{n})}^{2}}$ are called expected density of S_n-1 and S_n, respectively. Then, the expected density difference is defined as follows: $\begin{matrix} Δ_{n} & = ρ_{n} - ρ_{n - 1} \\ = \frac{1}{n - 1} \sum_{i = 1}^{n - 1} e^{- {(\frac{s (x_{i}) - {\bar{S}}_{n - 1}}{n - 1})}^{2}} - \frac{1}{n} \sum_{i = 1}^{n} e^{- {(\frac{s (x_{i}) - {\bar{S}}_{n}}{n})}^{2}} \end{matrix}$ (1)

According to Definition 6, S_n-1 possesses one less element s (x_n) than S_n. The expected density may be changed when an element s (x_n) is added to S_n-1. Therefore, the expected density difference reflects the influence degree when an element s (x_n) is added to S_n-1. That is, the following conclusions holds:

Δ_n > 0 denotes s (x_n) has a positive effect;

Δ_n < 0 denotes s (x_n) has a negative effect;

Δ_n = 0 denotes s (x_n) has no effect.

Based on Algorithm 1, we proposed an algorithm for constructing the data-driven three-way decision model (DD3WD) for UIS, which is defined as follows:

Algorithm 2 Algorithm for constructing DD3WD

Require: (1) An information system UIS₀ = (U₀, C, V₀, f₀), where U₀ = {x_o1, x_o2, …, x_on};(2) The accepted number k.

Ensure: Three regions POS_seq, BND_seq, NEG_seq.

1: Δ¹ = Δ² =∅,POS = BND = NEG =∅;

2: Obtain U_d = {x₁, x₂, …, x_n} and S = {s (x₁) , s (x₂) , …, s (x_n)}; // According to Algorithm 1

3: Compute Δ_i of x_i (x_i ∈ U_{d
₁}, where U_{d
₁} = {x₁, x₂, …, x_k}) by formula (1), Δ¹ = Δ¹ ∪ {Δ_i};

4: $t_{1} = \underset{i}{arg} max {Δ_{1}}$

5: α = s (x_{t
₁});

6: Compute Δ_i of x_i(x_i ∈ U_{d
₁}, where U_{d
₂} = {x_k+1, x_k+2, …, x_n}) by formula (1),Δ² = Δ² ∪ {Δ_i};

7: $t_{2} = \underset{i}{arg} max {Δ_{2}}$

8: α = s (x_{t
₂})

9: for i = 1 to n do

10: If s (x_i) ≥ α,POS = POS ∪ {x_i};

11: If α > s (x_i) ≥ β,BND = BND ∪ {x_i};

12: If s (x_i) < β,NEG = NEG ∪ {x_i}.

13: end for

14: Return POS, BND, NEG.

In Algorithm 2, U_d = {x₁, x₂, …, x_n} and S = {s (x₁) , s (x₂) , …, s (x_n)} are the output of Algorithm 1. Figure 2 describes the algorithm intuitively. s (x_k) is considered as the classification point of U. Obviously, this classification point ensures that the number of objects in the accepted region is less than k, that is α ≥ s (x_k) ≥ β.

Fig. 2

Data-driven three-way decisions model.

(continued) Example 1.

According to k = 4, the object set S₈ = {s (x₁) , s (x₂) , ⋯ , s (x₈)} is divided into two subsets {s (x₁) , s (x₂) ,

s (x₃) , s (x₄)} and {s (x₅) , s (x₆) , s (x₇) , s (x₈)}.

The expected density and expected density difference of each object in Table 1 obtained using Algorithm 2 is shown in Table 2.

Table 2

Result of Table 1 by Algorithm 2

Object	Score	ρ	Δ
x ₁	0.98	1	0
x ₂	0.88	0.998	0.0013
x ₃	0.64	0.989	0.0088
x ₄	0.58	0.986	0.0033
x ₅	0.56	1	0
x ₆	0.54	1	0
x ₇	0.28	0.992	0.0078
x ₈	0.15	0.985	0.0071

Therefore, α = 0.877, β = 0.286. Then, we have $\begin{matrix} POS = {x_{1}, x_{2}}, \\ BND = {x_{3}, x_{4}, x_{5}, x_{6}}, \\ NEG = {x_{7}, x_{8}} . \end{matrix}$

As well known, almost the three-way decisions will eventually degenerate to two-way decisions in real applications. Therefore, it is necessary to further establish the sequential three-way decisions model to classify the objects in boundary region constantly until the number in the positive region is equal to the given accepted number k. With respect to a series of unlabeled information system UIS_i = (U_i, C, V_i, f_i) with a pair of threshold α_i, β_i (0 ≤ β_i ≤ α_i ≤ 1), i = 1, 2, …, M, a sequential three-way decisions can be established based on Algorithm 2. Therefore, based on Algorithm 2, we proposed an algorithm for constructing the data-driven sequential three-way decisions model (DDS3WD) for UIS by considering dynamic decision making with updating attribute values.

In Algorithm 3, UIS_i denotes the ith update unlabeled information system. According to Algorithm 3, the thresholds α and β need to be recalculated with the update of the scores. Figure 3 describes the algorithm intuitively. Obviously, BND₁ ≥ BND₂ ≥ ⋯ ≥ BND_M holds.

Fig. 3

Data-driven sequential three-way decisions model.

Algorithm 3 Algorithm for constructing DDS3WD

Require: (1) An information system UIS₀ = (U₀, C, V₀, f₀), where U₀ = {x_o1, x_o2, …, x_on};(2) The accepted number k.

Ensure: Three regions POS_seq, BND_seq, NEG_seq.

1: UIS _ temp ← UIS₀ = (U₀, C, V₀, f₀) and POS₀← ∅;

2: i = 1;

3: while |POS_i-1| < k do

4: Obtain POS_i,BND_i,NEG_i by Algorithm 2 // Take UIS _ temp as the input of Algorithm 2;

5: POS_seq = POS_seq ∪ {POS_i},BND_seq = BND_seq ∪ {BND_i} and NEG_seq = NEG_seq ∪ {NEG_i};

6: k = k - |POS_seq|, U_i = BND_i;

7: UIS _ temp ← UIS_i = (U_i, C, V_i, f_i);// UIS_i denotes the ith update information system

8: i++.

9: end while

10: Return POS_seq, BND_seq, NEG_seq.

5 Experiments and analysis

In Section 4, we have discussed the data-driven sequential three-way decisions (DDS3WD) model for UIS by updating attributes from the perspective of similarity. In this section, related experiments are carried out to verify the effectiveness of DDS3WD. The experimental environments are Windows 7, Intel Core (TM) I5-4590 CPU (3.30 GHz) and 8GB RAM. The experimental platform is Matlab 2015b. Nine regression datasets from UCI [5] are listed in Table 3. The label of each dataset is used as the real score, and the final result of selection is ranked by descending order. Firstly, the three evaluation functions: Recall, UCR and UM are defined as follows: $\begin{matrix} Recall = \frac{| POS \cap {s (x_{i}) \geq s_{γ}} |}{n} . \end{matrix}$ (2)

Table 3

The descriptions of datasets

ID	Dataset	Attribute characteristics	Instances	Condition attributes
1	Air Quality	Real	9358	10
2	Auto MPG	Mixed	392	7
3	Concrete	Integer	699	9
4	ENB2012	Real	768	8
5	Automobile	Real	197	7
6	Students	Categorical	395	12
7	Airfoil	Real	1503	5
8	QSAR	Mixed	908	6
9	Forestfires	Real	157	8

In formula (2), $γ = \frac{k}{n}$ is called upper quantile. Recall reflects the number of positive objects that are selected correctly in the universe.

For the total update times T of each dataset, suppose that the ratio of update times is $τ = \frac{t}{T}$ , the update cost rate is defined as follows, $\begin{matrix} UCR = \frac{\sum_{i = 1}^{t} | BN D_{t} |}{nt} . \end{matrix}$ (3)

In formula (3), UCR reflects the total update cost to some extent. $\begin{matrix} UM = \frac{1}{n} \sum_{i = 1}^{n} \frac{arctan (- \frac{1}{s (x_{i})} {log}_{2} s (x_{i}))}{π / 2} . \end{matrix}$ (4)

In formula (4), UM denotes the uncertainty measure of each granularity layer.

In our experiments, for simplicity, we focus on comparing the three methods based on three models (two-way decisions model, DDS3WD and DDS3WD with updating all attribute values) are denoted by Method1, Method2 and Method3, respectively. As shown in Fig. 4, we compute the changing trend of Recall of three methods with the changing $γ = \frac{k}{n}$ on each dataset, and these values are described in a coordinate system. Obviously, the Recall of Method2 on each dataset is close to the one of Method3, and they are both higher than the one of Method1, because Method2 and Method3 are sequential and the Recall of them is close to the reality with the increase of update times. In addition, the value of Recall increases with changing $γ = \frac{k}{n}$ on each datasets.

Fig. 4

The Recall with the changing $γ = \frac{k}{n}$ on each dataset.

Figure 5 shows the changing trend of UCR of Method2 with the different γ and τ. Obviously, the update time increases with the increasing k in the case of the total number n unchanged, therefore, the UCR of Method2 will be decrease with the increasing γ.

Fig. 5

The UCR versus with the changing $τ = \frac{t}{T}$ and $γ = \frac{k}{n}$ on each dataset.

Figure 6 shows the UM versus with the changing $τ = \frac{t}{T}$ and $γ = \frac{k}{n}$ on each dataset. The UM will decrease with the increasing τ, because the size of boundary region will be reduced with the increasing update time under the condition of unchanged T.

Fig. 6

The UM versus with the changing $τ = \frac{t}{T}$ and $γ = \frac{k}{n}$ on each dataset.

6 Conclusion

Based on the granular computing and three-way decisions theory, the sequential three-way decisions (S3WD) model implements the idea of progressive computing. In essence, S3WD solves problems by gradually switching the granularity layer from coarser to finer, which means that the same problem can be processed in a hierarchical granular structure. However, almost S3WD models are established based on labeled information system, and there is still a lack of S3WD model for processing unlabeled information system (UIS). To solve the issue of given accepted number for UIS, a concept of optimal density difference is defined to establish the data-driven sequential three-way decisions (DDS3WD) model for UIS by updating attributes in this paper. Three evaluation functions are designed to verify that DDS3WD is feasible and effective for dealing with UIS under the condition of given accepted number of objects. In the next step, we will further study sequential three branch decision-making from the perspective of granularity optimization and attribute reduction.In the next step, we will further study sequential three branch decision-making from the perspective of granularity optimization and attribute reduction.

Footnotes

Acknowledgment

This work is supported by the National Science Foundation of China (No. 62066049), Innovation and exploration project of Guizhou Province (QKHPTRC [2017] 572706), Open fund of Chongqing Key Laboratory of Computational Intelligence (2020FF05), PHD Training Program of Chongqing University of Posts and Telecommunication (No. BYJS201902).

References

Cabrerizo

F.J.

, Al-Hmouz

, Morfeq

, et al., Estimating incomplete information in group decision making: A framework of granular computing, Applied Soft Computing, 2020.

Chen

, Topological structure in visual perception, Science 218 (1982), 4573.

Fang

, Gao

and Yao

Y.Y

, Granularity-driven sequential three-way decisions, Information Sciences 507 (2020), 644–644.

B.Q.

, Three-way decisions space and three-way decisions, Information Sciences.

B.Q.

, Three-way decision spaces based on partially ordered sets and three-way decisions based on hesitant fuzzy sets, Knowledge-Based Systems 91 (2015).

B.Q.

, Three-way decisions based on semi-three-way decision spaces, Information Sciences 382-383 (2017), 415–440.

Jia

X.Y.

, Deng

, Min

, et al., Three-way decisions based feature fusion for chinese irony detection, International Journal of Approximate Reasoning 113 (2019), 324–335.

Jia

Z.H.

and Qiao

J.S.

, On decision evaluation functions in three-way decision spaces derived from overlap and grouping functions, Soft Computing 24 (2020), 15159–151.

H.R.

, Pedrycz

, Li

H.X.

, et al., Sequential three-way classifier with justifiable granularity, Knowledge-Based Systems 163 (2019), 103–119.

10.

J.H.

, Huang

C.C.

, Qi

J.J.

, et al., Three-way cognitive concept learning via multi-granularity, Information Sciences 378 (2017), 244–263.

11.

Y.F.

, Zhang

L.B.

, Xu

, et al., Enhancing binary classification by modeling uncertain boundary in three-way decisions, IEEE Transactions on Knowledge and Data Engineering 7(29) (2017), 1438–1451.

12.

Liu

, Wang

, Jia

, et al., A multiple attribute decision making three-way model for intuitionistic fuzzy numbers, International Journal of Approximate Reasoning 119 (2020), 177–203.

13.

Pang

, Guan

, Liang

, et al., Multi-attribute group decision-making method based on multi-granulation weights and three-way decisions, International Journal of Approximate Reasoning 117 (2019), 122–147.

14.

Pawlak

, Rough sets, International Journal of Computer and Information Sciences 11(5) (1982), 341–356.

15.

Pawlak

, Rough classification, International Journal of Man-Machine Studies 20(5) (1984), 469–483.

16.

Pedrycz

and Homenda

, Building the fundamentals of granular computing: A principle of justifiable granularity, Applied Soft Computing 13(10) (2013), 4209–4218.

17.

Qian

Y.H.

, Liang

J.Y.

and Dang

C.Y.

, Incomplete multi-granulations rough set, IEEE Transaction on System, Man and Cybernic 40(2) (2010), 420–431.

18.

Qian

Y.H.

, Liang

J.Y.

and Yao

Y.Y.

, Mgrs: A multi-granulation rough set, Information Sciences 180(6) (2010), 949–970.

19.

Qiao

J.S.

and Hu

B.Q.

, On transformations from semi-three-way decision spaces to three-way decision spaces based on triangular norms and triangular conorms, Information Sciences 432 (2018), 22–51.

20.

Qiao

J.S.

and Hu

B.Q.

, On decision evaluation functions in generalized three-way decision spaces, Information Sciences 507 (2020), 733–754.

21.

Savchenko

A.V.

, Sequential three-way decisions in multi-category image recognition with deep features based on distance factor, Information Sciences 489 (2019), 18–36.

22.

Singh

P.K.

, Three-way fuzzy concept lattice representation using neutrosophic set, International Journal of Machine Learning and Cybernetics 8(1) (2017), 69–79.

23.

Wang

G.Y.

, Data-driven granular cognitive computing. In International Joint Conference on Rough Sets, 2017.

24.

Wang

G.Y

, Yang

and Xu

, Granular computing: from granularity optimization to multi-granularity joint problem solving, Granular Computing 2(3) (2017), 1–16.

25.

Wang

P.X.

and Yao

Y.Y.

, A three-way clustering method based on ensemble strategy and three-way decision, Knowledge-Based System 155 (2018), 54–65.

26.

Yang

, Wang

G.Y.

, Zhang

Q.H.

, et al., Optimal granularity selection based on cost-sensitive sequential three-way decisions with rough fuzzy sets, Knowledge-Based Systems 163 (2019), 131–144.

27.

Yang

, Li

T.R.

, Fujita

, et al., A unified model of sequential three-way decisions and multilevel incremental processing, Knowledge-Based Systems 134(10) (2017), 172–188.

28.

Yang

, Li

T.R.

, Fujita

, et al., A sequential three-way approach to multi-class decision, International Journal of Approximate Reasoning 104 (2019), 108–125.

29.

Yao

J.T.

, Vasilakos

A.V.

and Pedrycz

, Granular computing: perspectives and challenges, IEEE Transactions on Cybernetics 43(6) (2013), 1977–1989.

30.

Yao

Y.Y.

, Probabilistic approaches to rough sets, Expert Systems, 2010.

31.

Yao

Y.Y.

, Probabilistic rough set approximations, International Journal of Approximate Reasoning 49(2) (2008), 255–271.

32.

Yao

Y.Y.

, Three-way decisions with probabilistic rough sets, Information Sciences 180(3) (2010), 341–353.

33.

Yao

Y.Y.

, The superiority of three-way decisions in probabilistic rough set models, Information Sciences 181(6) (2011), 1080–1096.

34.

Yao

Y.Y.

, Three-way decision and granular computing, International Journal of Approximate Reasoning 103 (2018), 107–123.

35.

Yao

Y.Y.

, Deng

X.F.

, Sequential three-way decisions with probabilistic rough sets, IEEE International Conference on Cognitive Informatics and Cognitive Computing (2011), pages 120–125.

36.

, Wang

G.Y

, et al., Symnmf: nonnegative low-rank approximation of a similarity matrix for graph clustering, Information Sciences 62(3) (2015), 545–574.

37.

Yue

X.D.

, Chen

Y.F.

, Miao

D.Q.

and Fujita

, Fuzzy neighborhood covering for three-way classification, Information Sciences 507 (2018), 795–808.

38.

Zhang

H.R.

, Min

and Shi

, Regression-based three-way recommendation, Information Sciences 378 (2017), 444–461.

39.

Zhang

, Li

, Zhou

, et al., Sequential three-way decision based on multi-granular autoencoder features, Information Sciences 507 (2020), 630–643.

40.

Zhang

Q.H.

, Lv

G.X.

, Chen

Y.H.

, et al., A dynamic three-way decision model based on the updating of attribute values, 142(2) (2018), 71–84.

41.

Zhang

Q.H.

, Yang

C.C.

and Wang

G.Y.

, A sequential three-way decision model with intuitionistic fuzzy numbers, IEEE transactions on Systems, Man, and Cybernetics, 2019.

Data-driven sequential three-way decisions for unlabeled information system

Abstract

Keywords

1 Introduction

3 A general sequential three-way decisions model for UIS

Table 1 An information table of student performance Object English Math Chinese Sports x o1 96 90 83 82 x o2 70 70 73 75 x o3 98 92 87 92 x o4 70 87 82 60 x o5 76 94 70 68 x o6 75 74 66 68 x o7 67 55 60 45 x o8 40 45 50 60

Footnotes

Acknowledgment

References

Table 1
An information table of student performance

Object English Math Chinese Sports

x _o1 96 90 83 82

x _o2 70 70 73 75

x _o3 98 92 87 92

x _o4 70 87 82 60

x _o5 76 94 70 68

x _o6 75 74 66 68

x _o7 67 55 60 45

x _o8 40 45 50 60