An improved algorithm for normal parameter reduction of soft set

Abstract

The normal parameter reduction is used as a useful approach to identify the irrelevant parameters in soft set-based decision making systems. It finds a subset with least number of parameters that preserve the original classification of the decision alternatives. A number of algorithms have been developed for the normal parameter reduction of soft set but the case of repeated columns (i.e., e_i = e_j) was only considered by Danjuma et al. In this study, first we address the limitations of the Danjuma et al.’s approach to normal parameter reduction of soft set. Then, we propose a new algorithm for normal parameter reduction of soft set which is free of all such limitations. Moreover, we compare the proposed algorithm with some of the existing algorithms of normal parameter reduction of soft set to show its efficiency. Finally, the application of the proposed algorithm is elaborated by a medical diagnostic problem.

Keywords

Soft set normal parameter reduction decision making medical diagnosis

1. Introduction

Different types of uncertainties such as; randomness, vagueness, and roughness often occur in practical decision systems. To handle these uncertainties in a befitting manner, a number of mathematical theories have been developed by different authors such as; probability theory [20], fuzzy set theory [31], intuitionists fuzzy set theory [4], interval mathematics theory [10] and rough set theory [28]. Each of the afore-mentioned theory has its inherent difficulties, which are mentioned by Molodtsov in [27]. Therefore, Molodtsov [27] developed a completely new approach for modeling uncertainty and vagueness, which is called soft set theory. Soft set theory is basically based on the parameterization tool which makes this theory more simple and applicable as compared to the other existing theories.

The applications of soft sets in real-world problems are progressing rapidly and many algorithms have been developed for solving practical problems. Zhang et al. [38] introduced the concepts of fuzzy soft β-minimal (maximal) descriptions and developed four new types of fuzzy soft β-neighborhoods. Similarly, by means of fuzzy soft β-coverings based fuzzy rough set, a new algorithm was proposed by Zhang and Zhan in [37]. Further, by means of soft neighborhoods, Zhan and Wang introduced a novel type of soft rough covering in [35]. Moreover, in [32], five new types of soft coverings based rough sets were developed by Zhan and Alcantud, where the first two types were used to proposed two special algorithms based on soft coverings based rough sets. Similarly in many directions, the applications of soft sets have been explored by different authors such as; association rules mining [8, 13], medical diagnosis [1 , 30], incomplete data analysis [19, 40] and decision making [3 , 39].

In the last few years, the problems related to the parameterization reduction and decision making have been gained considerable attention in dealing with uncertainties. Some successful implementations have been made by different researchers to elaborate the applications of the soft set theory in parameter reduction and decision making. In this regard, the first attempt was made by Maji et al. [26] who used a rough set approach for dimensionality reduction and applied it to a decision making problem. Later in [5], Chen et al. mentioned that the technique of Maji et al. [26] may produce some wrong results because they do the reduction process before computing the choice values of the objects in a decision system. Moreover, according to Chen et al. [5], the parameters reduction in soft set theory is a different approach from the attributes reduction in rough set theory and they cannot be used interchangeably for computing the optimal object in soft set-based decision systems. Thus in [5], they developed a new parameter reduction technique for soft sets and find the optimal decision on a general Boolean data set. However, their technique was failed to maintain all the levels of the suboptimal choices during the reduction process.

According to Kang et al. [22], most of the methods related to soft set reduction (i.e. Maji et al. [26], Chen et al. [5] etc.) have only considered the optimal choice and they ignored suboptimal choices at the time of decision making. In many decision making problems (such as; sold products, demand products etc.), we select the optimal choice from the data set and delete the data of the optimal object from the corresponding data set. If we want to make next decision on the same data set where the data of optimal object are already deleted, usually we need a new reduction which obviously wastes our time. Similarly, in some cases, if the character of objects in soft set cannot be embodied by a given parameter set, then some more parameters are added to the given parameter set. After adding new parameters, we need to make a new reduction of soft set for decision making which is wastes too much time. To overcome these problems, Kong et al. [22] introduced the concept of normal parameter reduction (NPR) and proposed an algorithm for it. Normal parameter reduction has the ability to reduce the dimensionality of a data set without disturbing the original classification of its decision alternatives (objects). Since the NPR algorithm presented by Kong et al. [22] was based on the parameter importance degree, which was hard to compute and involve a great amount of computation. Therefore, the new efficient normal parameter reduction algorithm (NENPR) for soft sets was proposed by Ma et al. in [24]. In NENPR algorithm, the whole reduction process was based on oriented-parameter sum and there was no need to compute the parameter importance degrees and decision partitions. Further, the particle swarm optimization algorithm was used by Kong et al. [23] to give a proper mathematical representation to the problem of normal parameter reduction of soft sets. For more study about soft set reduction, we refer [2 , 33].

Since, all of the afore-mentioned algorithms have tried to reduce the running time and computational complexity of the normal parameter reduction process, however, they did not consider the case of repeated columns (i.e., the parameters e_i = e_j) in soft set data tables which can cause an extra computation burden on the reduction process. Therefore, in [7], Danjuma et al. addressed this issue and proposed a new algorithm called, the alternative normal parameter reduction algorithm (ANPR). Moreover, they compared the ANPR algorithm with some previous algorithms (i.e, NPR and NENPR algorithms) and also discussed some decision making problems. However, the ANPR algorithm proposed by Danjuma et al. is based on some miss conceptual results and cannot be considered as a legitimate approach to normal parameter reduction of soft set. The main contributions of this work are summarized as follows.

To highlight the deficiencies of the Danjuma et al.’s approach to normal parameter reduction of soft set.

To propose a new improved algorithm for normal parameter reduction of soft set.

To compare our proposed algorithm with some of the existing algorithms of normal parameter reduction of soft set.

To give an application of the proposed algorithm in a medical diagnostic problem.

The organization of the paper is given as follows. In Section 2, we review some basic concepts about rough set theory and soft set theory. In Section 3, we analyze the NPR and NENPR algorithms as presented in [22] and [24], respectively. Section 4 analyzes some limitations of the ANPR algorithm proposed in [7]. In Section 5, initially, we give some useful definitions and results and then provide an improved algorithm for normal parameter reduction of soft set. In Section 6, some comparison results are given between the proposed algorithm and some of the existing algorithms. Section 7 provides the application of the proposed algorithm in a medical diagnostic problem. Finally, Section 8 presents the conclusion of the paper.

2. Preliminaries

This section reviews some basic concepts about soft set and rough set. Throughout the paper, we take U as initial universe, E the set of parameters which may be some attributes, properties or some characteristics of the objects in U, and P (U) the set of all subsets of U.

Definition 2.1 [27] A pair (F, E) is said to be a soft set over U, where F is a mapping given by $F : E \to P (U) .$

Equivalently, the soft set (F, E) over U can be thought as a parameterized family obtained from P (U). The mapping F is named as the approximate function and its functional value i.e., F (e) is called the set of e-approximate elements of (F, E). To clarify the concept, consider the following example.

Example 2.1 A soft set (F, E) describes the attractiveness of the houses that Mr. Y is going to buy. Let U = {u₁, u₂, u₃, u₄, u₅, u₆} be the six houses and E = {e₁, e₂,. . . , e₁₀} are the corresponding parameters, where each parameter e_k, for k ∈ {1, 2,. . . , 10} represents; beautiful, new, reliable, in good location, wooden, cheap, in hilly areas, well furnished, in green surrounding and well decorated, respectively. Consider the mapping F from E to P (U) as defined by

F (e₁) = {u₁, u₂, u₅} , F (e₂) = {u₃, u₄, u₆} ,

F (e₃) = {u₂, u₃, u₆} , F (e₄) = {u₃, u₄, u₆} ,

F (e₅) = {u₁, u₂, u₅} , F (e₆) = {u₁, u₃, u₄} ,

F (e₇) = {u₁, u₄, u₆} , F (e₈) = {u₂, u₃, u₅, u₆} ,

F (e₉) = {u₁, u₂, u₃, u₄, u₅, u₆} and

F (e₁₀) = {u₃, u₄, u₆} .

Thus, (F, E) can be written as a parameterized family of subsets of U such as; $(F, E) = {\begin{matrix} beautiful houses = {u_{1}, u_{2}, u_{5}}, \\ new houses = {u_{3}, u_{4}, u_{6}}, \\ reliable houses = {u_{2}, u_{3}, u_{6}}, \\ houses in good location = {u_{3}, u_{4}, u_{6}}, \\ wooden houses = {u_{1}, u_{2}, u_{5}}, \\ cheap houses = {u_{1}, u_{3}, u_{4}}, \\ houses in hilly areas = {u_{1}, u_{4}, u_{6}}, \\ well furnished houses = {u_{2}, u_{3}, u_{5}, \\ u_{6}}, \\ houses in green surrounding = {u_{1}, \\ u_{2}, u_{3}, u_{4}, u_{5}, u_{6}}, \\ well decorated houses = {u_{3}, u_{4}, u_{6}} . \end{matrix}$

A soft set can also be represented by a Boolean-valued information system. The definition of an information system is given as follows.

Definition 2.2 [9] An information system is denoted by a 4-tuple S = (U, A, V, f), where U = {u₁, u₂,. . . , u_n} represents a finite universe, A = {a₁, a₂,. . . , a_m} represents a finite set of attributes, V = ∪ _a∈AV_a, where V_a denotes the set of values for attribute a and f denotes the information function defined by f : U × A → V such that for every (u, a) ∈ U × A, we have f (u, a) ∈ V_a.

An information system sometimes called a knowledge-based system that can be expressed by an information table. In particular, S is said to be a Boolean-valued information system if, V_a = {0, 1}.

Proposition 2.1 [24] A soft set (F, E) over U can be considered as a Boolean-valued information system S = (U, A, V_{0,1}, f).

Proof. The proof is given in [24].■

Thus, by Proposition 2.1, the soft set (F, E) as defined in Example 2.1 can be considered as a Boolean-valued information system and its Boolean table is given by Table 1.

Table 1
Tabular form of (F, E) given in Example 2.1

U e ₁ e ₂ e ₃ e ₄ e ₅ e ₆ e ₇ e ₈ e ₉ e ₁₀ f (.)

u ₁ 1 0 0 0 1 1 1 0 1 0 5

u ₂ 1 0 1 0 1 0 0 1 1 0 5

u ₃ 0 1 1 1 0 1 0 1 1 1 7

u ₄ 0 1 0 1 0 1 1 0 1 1 6

u ₅ 1 0 1 0 1 0 0 1 1 0 5

u ₆ 0 1 1 1 0 0 1 1 1 1 7

U	e ₁	e ₂	e ₃	e ₄	e ₅	e ₆	e ₇	e ₈	e ₉	e ₁₀	f (.)
u ₁	1	0	0	0	1	1	1	0	1	0	5
u ₂	1	0	1	0	1	0	0	1	1	0	5
u ₃	0	1	1	1	0	1	0	1	1	1	7
u ₄	0	1	0	1	0	1	1	0	1	1	6
u ₅	1	0	1	0	1	0	0	1	1	0	5
u ₆	0	1	1	1	0	0	1	1	1	1	7

3. Analysis of some previous algorithms for normal parameter reduction

This section analyzes the two well-known algorithms namely; normal parameter reduction algorithm (NPR) and new efficient normal parameter reduction algorithm (NENPR) proposed by Kong et al. [22] and Ma et al. [24], respectively.

3.1. The normal parameter reduction algorithm (NPR)

Let U = {u₁, u₂,. . . , u_n}, E = {e₁, e₂,. . . , e_m} and u_ij be the entries in the Boolean table of the soft set (F, E). For a soft set (F, E) over U, the choice value f_E (.) of an object u_i ∈ U is defined by f_E (u_i) = ∑_j (u_ij).

To describe the rank and partitions of the objects in U, an indiscernibility relation is defined as follows.

Definition 3.1. For a non-empty subset B ⊆ E, an indiscernibility relation IND (B) is defined by $IND (B) = {(u_{i}, u_{j}) \in U \times U | f_{B} (u_{i}) = f_{B} (u_{j})} .$

For the soft set (F, E) over U, the partition C_E = {{u₁, u₂,. . . , u_i} _{f
₁}, {u_i+1, u_i+2,. . . , u_j} _{f
₂},. . . , {u_k+i, u_k+2,. . . , u_n} _{f
_s}} is called the decision partition, which ranks the objects of U according to their choice values f_E (.). Further, if we delete a parameter e_i from E, then a new decision partition is obtained from C_E, which is denoted by $C_{E - e_{i}} = {{u_{\overset{´}{1}}, u_{\overset{´}{2}}, . . ., u_{\overset{´}{i}}}_{f_{\overset{´}{1}}}, {u_{i + \overset{´}{1}}, u_{i + \overset{´}{2}}, . . ., u_{\overset{´}{j}}}_{f_{\overset{´}{2}}}, . . ., {u_{\overset{´}{k}},$ $u_{k + \overset{´}{1}}, . . ., u_{\overset{´}{n}}}_{f_{\overset{´}{s}}}} .$ For simplicity, C_E and C_{E-e_i} can be denoted by C_E = {E_{f
₁}, E_{f
₂},. . . , E_{f
_s}} and $C_{E - e_{i}} = {{\bar{E - e_{i}}}_{f_{\overset{´}{1}}}, {\bar{E - e_{i}}}_{f_{\overset{´}{2}}}, . . ., {\bar{E - e_{i}}}_{f_{\overset{´}{s}}}}$ , respectively.

Definition 3.2. [22] For a soft set (F, E) over U, if there exists a subset $A = {{\bar{e}}_{1}, {\bar{e}}_{2}, . . ., {\bar{e}}_{p}} \subset E$ satisfying f_A (u₁) = f_A (u₂) = . . . = f_A (u_n), then A is dispensable, otherwise, A is indispensable. B ⊆ E is said to be a normal parameter reduction of E if B is indispensable and f_E-B (u₁) = f_E-B (u₂) = . . . = f_E-B (u_n), that is to say E - B is the maximal subset of E which keeps the value f_E-B (.) constant.

Definition 3.3. [22] For the soft set (F, E) over U, if C_E = {E_{f
₁}, E_{f
₂},. . . , E_{f
_s}} and $C_{E - e_{i}} = {{\bar{E - e_{i}}}_{f_{\overset{´}{1}}}, {\bar{E - e_{i}}}_{f_{\overset{´}{2}}}, . . ., {\bar{E - e_{i}}}_{f_{\overset{´}{s}}}}$ are the decision partition and the decision partition deleted e_i, respectively. Then, the parameter importance degree r_{e
_i} for each parameter e_i is defined by

$r_{e_{i}} = \frac{1}{| U |} (α_{1, e_{i}} + α_{2, e_{i}} + . . . + α_{s, e_{i}})$ , where

$α_{k}, e_{i} = {\begin{matrix} | E_{f_{k}} - {\bar{E - e_{i}}}_{f_{\overset{´}{z}}} |, & if there exits \overset{´}{z}, such that \\ f_{k} = f_{\overset{´}{z}}, 1 \leq \overset{´}{z} \leq \overset{´}{s}, \\ 1 \leq k \leq s; \\ | E_{f_{k}} |, & otherwise, \end{matrix}$

and | . | denotes the cardinality of set.

The NPR algorithm was proposed by Kong et al. [22] as given by Algorithm 1.

Algorithm 1	The NPR algorithm
Step 1.	Input the soft set (F, E) and the parameter set E;
Step 2.	Calculate r_{e _j} for all e_j, where (1 ≤ j ≤ m);
Step 3.	Search for a maximal subset $A = {{\bar{e}}_{1}, {\bar{e}}_{2}, . . ., {\bar{e}}_{p}}$ in E for which the sum of $r_{{\bar{e}}_{j}}$ , where (1 ≤ j ≤ p), is a non-negative integer and put it into the feasible parameter reduction set;
Step 4.	If the condition f_A (u₁) = f_A (u₂) = . . . = f_A (u_n) is satisfied for a subset A in the feasible parameter reduction set, then A is saved, otherwise it will be deleted from the feasible parameter reduction set;
Step 5.	Calculate E - A as the optimal normal parameter reduction of (F, E), where A has the maximum cardinality in the feasible parameter reduction set.

The following example will give a clear description of the NPR algorithm.

Example 3.1. Consider the soft set (F, E) as given by Table 1, then by Algorithm 1:

Step 1. Input the soft set (F, E) as given by Table 1.

Step 2. Compute the choice values for all u_i ∈ U by f_E (u_i) = ∑_j (u_ij), and write them as the last column in Table 1. Using the choice values, the decision partition C_E is given by: $C_{E} = {{u_{3}, u_{6}}_{7}, {u_{4}}_{6}, {u_{1}, u_{2}, u_{5}}_{5}} .$ (3.1) The e_j deleted partitions i.e., C_{E-e_j} are given by:

C_E–e₁ = {{u₃, u₆} ₇, {u₄} ₆, {u₁, u₂, u₅} ₄} ,

C_E–e₂ = {{u₃, u₆} ₆, {u₁, u₂, u₄, u₅} ₅} ,

C_E–e₃ = {{u₃, u₄, u₆} ₆, {u₁} ₅, {u₂, u₅} ₄} ,

C_E–e₄ = {{u₃, u₆} ₆, {u₁, u₂, u₄, u₅} ₅} ,

C_E–e₅ = {{u₃, u₆} ₇, {u₄} ₆, {u₁, u₂, u₅} ₄} ,

C_E–e₆ = {{u₆} ₇, {u₃} ₆, {u₂, u₄, u₅} ₅, {u₁} ₄} ,

C_E–e₇ = {{u₃} ₇, {u₆} ₆, {u₂, u₄, u₅} ₅, {u₁} ₄} ,

C_E–e₈ = {{u₃, u₄, u₆} ₆, {u₁} ₅, {u₂, u₅} ₄} ,

C_E–e₉ = {{u₃, u₆} ₆, {u₄} ₅, {u₁, u₂, u₅} ₄} ,

C_E–e₁₀ = {{u₃, u₆} ₆, {u₁, u₂, u₄, u₅} ₅} .

The importance degrees r_{e
_j}, ∀ e_j ∈ E are then computed as:

α_1,e₁ = | {u₃, u₆} – {u₃, u₆} |=0, α_2,e₁ = | {u₄} – {u₄} |=0, α_3,e₁ = | {u₁, u₂, u₅} – φ|=3.

Thus, $r_{e_{1}} = \frac{1}{6} (0 + 0 + 3) = \frac{3}{6}$ . In similar way, we can compute: $r_{e_{2}} = \frac{3}{6}$ , $r_{e_{3}} = \frac{4}{6}$ , $r_{e_{4}} = \frac{3}{6}$ , $r_{e_{5}} = \frac{3}{6}$ , $r_{e_{6}} = \frac{3}{6}$ , $r_{e_{7}} = \frac{3}{6}$ , $r_{e_{8}} = \frac{4}{6}$ , r_{e
₉} = 1, and $r_{e_{10}} = \frac{3}{6}$ .

Step 3. Find $A = {{\bar{e}}_{1}, {\bar{e}}_{2}, . . ., {\bar{e}}_{p}}$ as the maximum subset in E for which the sum of $r_{{\bar{e}}_{j}}$ , where (1 ≤ j ≤ p), is a non-negative integer and put A into the feasible parameter reduction set. In this way, we obtain the subsets such as; {e₂, e₄, e₅}, {e₁, e₂, e₄, e₅}, {e₅, e₆, e₇, e₁₀}, and so on.

Step 4. Filter the feasible parameter reduction set, if the condition f_A (u₁) = f_A (u₂) = . . . = f_A (u₆) is satisfied for the subset A, then A is saved, otherwise, A will be deleted. As a result, we get the subsets such as; {e₁, e₅}, {e₁, e₂, e₄, e₅}, {e₁, e₂, e₄, e₅, e₉}, and so on.

Step 5. Finally, select A = {e₁, e₂, e₄, e₅, e₉} as the maximum cardinality in the feasible parameter reduction set. Thus, E – A = {e₃, e₆, e₇, e₈, e₁₀} is the required optimal normal parameter reduction of (F, E) as given by Table 2.

Table 2

Normal parameter reduction of Table 1.

U	e ₃	e ₆	e ₇	e ₈	e ₁₀	f (.)
u ₁	0	1	1	0	0	2
u ₂	1	0	0	1	0	2
u ₃	1	1	0	1	1	4
u ₄	0	1	1	0	1	3
u ₅	1	0	0	1	0	2
u ₆	1	0	1	1	1	4

We see that the normal parameter reduction of (F, E) as given by Table 2 has the decision partition

$C_{E - A} = {{u_{3}, u_{6}}_{4}, {u_{4}}_{3}, {u_{1}, u_{2}, u_{5}}_{2}} .$ (3.2) From (3.1) and (3.2), it is clear that after the normal parameter reduction, the rank and classification of the objects in U (i.e, decision alternatives) does not changed during the decision making process. However, the NPR algorithm as given by Algorithm 1 is based on the parameter importance degree i.e. r_{e
_i}, which is difficult to understand and requires a great amount of computation. Therefore, Ma et al. [24] introduced the NENPR algorithm to reduced the level of computational complexity of the normal parameter reduction process.

3.2. The new efficient normal parameter reduction algorithm (NENPR)

This section briefly analyzes the new efficient normal parameter reduction algorithm (NENPR), proposed by Ma et al. [24]. The NENPR algorithm finds the oriented-parameter sum instead of parameter importance degree and compute the candidate parameter set. This makes the NENPR algorithm more simple and easily implementable as compared to the NPR algorithm.

Definition 3.4. For a soft set (F, E) over U, the oriented-object sum is defined by f_E (u_i) = ∑_jh_ij.

Definition 3.5. [24] For a soft set (F, E) over U, the oriented-parameter sum is defined by S (e_j) = ∑_ih_ij.

Definition 3.6. [24] For a soft set (F, E) over U, if u_1j = u_2j = u_3j = . . . . = u_nj = 1 for a parameter e_j ∈ E, then we denote e_j by $e_{j}^{1}$ .

Definition 3.7. [24] For a soft set (F, E) over U, if u_1j = u_2j = u_3j = . . . . = u_nj = 0 for a parameter e_j ∈ E, then we denote e_j by $e_{j}^{0}$ .

Definition 3.8. [24] For a soft set (F, E) over U, the overall sum for a subset A ⊆ E is defined by S_A = ∑_jS (e_j).

Theorem 3.1 [24] For a soft set (F, E), if there exists a subset $A = {{\bar{e}}_{1}, {\bar{e}}_{2}, . . ., {\bar{e}}_{p}} \subset E$ , such that E – A is the normal parameter reduction of E. Then we have S_A = qn, for q = {0, 1, 2,. . . , m}, where n is the number of the objects in the universe U.

Based on the above definitions and Theorem 3.1, the NENPR algorithm is given by Algorithm 2. The following example will give a clear description of the NENPR algorithm.

Algorithm 2	The NENPR algorithm
Step 1.	Input the soft set (F, E) and the parameter set E;
Step 2.	If there exist the parameters $e_{j}^{1}$ and $e_{j}^{0}$ , then put them into the reduced parameter set C and the new soft set will be established without $e_{j}^{1}$ and $e_{j}^{0}$ , where U = {u₁, u₂,. . . , u_n} and $\overset{´}{E} = {e_{\overset{´}{1}}, e_{\overset{´}{2}}, . . ., e_{\overset{´}{t}}}$ ;
Step 3.	Calculate $S (e_{\overset{´}{j}})$ for each $e_{\overset{´}{j}} \in \overset{´}{E}$ , where $(\overset{´}{1} \leq \overset{´}{j} \leq \overset{´}{t})$ ;
Step 4.	Find the subset $A = {{\bar{e}}_{1}, {\bar{e}}_{2}, . . ., {\bar{e}}_{p}}$ in $\overset{´}{E}$ for which S_A is the multiple of \|U\|, and put them into the candidate parameter reduction set;
Step 5.	Filter the candidate parameter reduction set, if f_A (u₁) = f_A (u₂) = . . . = f_A (u_n) is satisfied for a subset A then it will be saved; otherwise, will be deleted from the candidate parameter reduction set;
Step 6.	Compute E – A – C as the optimal normal parameter reduction of (F, E), where A has the maximum cardinality in the candidate parameter reduction set.

Example 3.2. Again, consider the soft set (F, E) as displayed in Table 1, then by Algorithm 2:

Step 1. Input the soft set (F, E) as given by Table 1.

Step 2. By Definitions 3.4 and 3.5, determine the parameters $e_{j}^{1}$ and $e_{j}^{0}$ in Table 1, which is $e_{9}^{1}$ and put itinto the reduced parameter set C, the new soft set $(F, \overset{´}{E})$ without $e_{9}^{1}$ is given by Table 3.

Step 3. Calculate $S (e_{\overset{´}{j}})$ for each $\overset{´}{e_{j}} \in \overset{´}{E}$ in Table 3.

Table 3
Tabular form of $(F, \overset{´}{E})$ in Example 3.2

U e ₁ e ₂ e ₃ e ₄ e ₅ e ₆ e ₇ e ₈ e ₁₀ f (.)

u ₁ 1 0 0 0 1 1 1 0 0 4

u ₂ 1 0 1 0 1 0 0 1 0 4

u ₃ 0 1 1 1 0 1 0 1 1 6

u ₄ 0 1 0 1 0 1 1 0 1 5

u ₅ 1 0 1 0 1 0 0 1 0 4

u ₆ 0 1 1 1 0 0 1 1 1 6

S _{e
_i} 3 3 4 3 3 3 3 4 3 29

U	e ₁	e ₂	e ₃	e ₄	e ₅	e ₆	e ₇	e ₈	e ₁₀	f (.)
u ₁	1	0	0	0	1	1	1	0	0	4
u ₂	1	0	1	0	1	0	0	1	0	4
u ₃	0	1	1	1	0	1	0	1	1	6
u ₄	0	1	0	1	0	1	1	0	1	5
u ₅	1	0	1	0	1	0	0	1	0	4
u ₆	0	1	1	1	0	0	1	1	1	6
S _{e _i}	3	3	4	3	3	3	3	4	3	29

Step 4. Select every $A = {{\bar{e}}_{1}, {\bar{e}}_{2}, . . ., {\bar{e}}_{p}}$ in $\overset{´}{E}$ for which S_A is the multiple of |U| and by Theorem 3.1, put A into the candidate parameter reduction set. As a result, we obtain the subsets such as; {e₂, e₄}, {e₁, e₂, e₄, e₅}, {e₄, e₅}, {e₁, e₂, e₄, e₅, e₆, e₇}, and so on.

Step 5. Filter the candidate parameter reduction set, if the condition f_A (u₁) = f_A (u₂) = . . . = f_A (u₆) is satisfied for the subset A, then A will be saved, otherwise, delete A from the candidate parameter reduction set. In this way we obtain the subsets such as; {e₄, e₅}, {e₁, e₂}, {e₁, e₂, e₄, e₅}, and so on.

Step 6. Finally, search for the maximum cardinality of A in the candidate parameter reduction set, which is A = {e₁, e₂, e₄, e₅}. Thus, E – A – C = {e₃, e₆, e₇, e₈, e₁₀} is the required optimal normal parameter reduction of (F, E) which is the same as given by Table 2.

The main setback of NENPR algorithm is that, it does not consider the issue of the repeated columns in soft set tables and performs the same process repeatedly which puts an extra computation burden on the reduction process. Therefore, to overcome this problem, Danjuma et al. [7] proposed the ANPR algorithm and applied it to some decision making problems. Since, the idea proposed in [7] was interesting but it has not been implemented so effectively to handle the afore-mentioned problem.

4. Some limitations of alternative normal parameter reduction algorithm (ANPR)

This section highlights the overall deficiencies of the alternative normal parameter reduction algorithm (ANPR) proposed by Danjuma et al. [7]. At the end of the section, an example is provided to show that the ANPR algorithm cannot be used for normal parameter reduction of soft sets.

Definition 4.1. For a soft set (F, E) over U, if there exist e_i = e_j and u_1j = u_2j = . . . = u_nj, then e_i or e_j is a special entry denoted as Q.

The dialectic subsets of the parameter set E can be defined in the following way.

Definition 4.2. [7] For a soft set (F, E) over U, the subsets $A = {{\bar{e}}_{1}, {\bar{e}}_{2}, . . ., {\bar{e}}_{p}}$ and $B = {{\bar{\bar{e}}}_{1}, {\bar{\bar{e}}}_{2}, . . ., {\bar{\bar{e}}}_{q}}$ are said to be dialectic subsets of E if

f_A (u₁) = f_A (u₂) = . . . = f_A (u_n) and

f_B (u₁) = f_B (u₂) = . . . = f_B (u_n).

The intersection of the dialectic subsets is defined as follows.

Definition 4.3. [7] For a soft set (F, E) over U, if there exit dialectic subsets A and B then $(A \cup B) - (A \cap B) = (F, \overset{´}{\overset{´}{E}}) .$

Based on Definitions 4.1, 4.2 and 4.3, the ANPR algorithm was proposed by Danjuma et al. as given by Algorithm 3.

Algorithm 3	The ANPR algorithm
Step 1.	Input the soft set (F, E) and the parameter set E;
Step 2.	If there exists the parameters e_i = e_j, choose one of them and put it in Q, if there exists $e_{j}^{1}$ , $e_{j}^{0}$ then put them into the reduced parameter set C. The new parameter set i.e., $\overset{´}{E}$ will be obtained as $\overset{´}{E} = E - C - Q$ ;
Step 3.	Calculate $S (e_{\overset{´}{j}})$ for each $e_{\overset{´}{j}} \in \overset{´}{E}$ ;
Step 4.	Check the candidate parameter reduction set for the subsets A and B such that; f_A (u₁) = f_A (u₂) = . . . = f_A (u_n) and f_B (u₁) = f_B (u₂) = . . . = f_B (u_n);
Step 5.	Compute (A ∪ B) – (A ∩ B), and put the intersection into the reduced parameter set D;
Step 6.	Find the maximum cardinality of the candidate parameter reduction set and compute E – C – Q – D as the alternative normal parameter reduction of (F, E).

If we consider Definitions 4.1, 4.2 and 4.3, then all of them are confusing and not very clear. For example, in Definition 4.1, the expression u_1j = u_2j = . . . = u_nj is used to represent the parameters e_i = e_j, which is incorrect. In fact, this kinds of expression can only be used for the parameters $e_{j}^{1}$ and $e_{j}^{0}$ (see Definitions 3.6 and 3.7). Thus, the right expression to be used there is u_ij = u_ik, where (1 ≤ i ≤ n) and (1 ≤ j, k ≤ m). Similarly in Definition 4.2, the expressions

f_A (u₁) = f_A (u₂) = . . . = f_A (u_n) and

f_B (u₁) = f_B (u₂) = . . . = f_B (u_n)

are used to define the dialectic subsets A and B of E which looks very strange because according to these two expressions, any two dispensable subsets of E are dialectic (see Definition 3.2). Later in Example 4 of [7] (in Step 4), it was observed that two subsets A and B of E are said to be dialectic if they are dispensable and have the same choice values for all u_i ∈ U. Thus, the appropriate expressions that should be used in Definition 4.2 are

f_A (u₁) = f_A (u₂) = . . . = f_A (u_n) = k and

f_B (u₁) = f_B (u₂) = . . . = f_B (u_n) = k,

where k is nonnegative integer.

Moreover, the expression $(A \cup B) - (A \cap B) = (F, \overset{´}{\overset{´}{E}})$ used in Definition 4.3 has no relation with the intersection of two dialectic subsets A and B of E. Thus, the expression (A ∪ B) – (A ∩ B) in Step 5 makes no sense and can be omitted from of the ANPR algorithm (see Step 4 of Example 4 in [7]).

On the other hand, if we consider Algorithm 3, then in Step 2, the authors reduce the parameters e_i = e_j from the parameter set E without providing any justifying result for it. We cannot directly remove two or more similar columns from a soft set table except $e_{j}^{1}$ and $e_{j}^{0}$ , otherwise, it will change the original classification of the objects during the reduction process (see Table 4). Further, in Step 5, the algorithm computes the intersection of the dialectic subsets A and B and puts the intersection into another reduced parameter set D. It is clear from Definition 4.2 that the dialectic subsets A and B are nothing but they are just dispensable subsets of E with an extra condition. Also we know that, if the intersection of two dispensable sets A and B is indispensable, then a parameter e_j ∈ A ∩ B cannot be deleted from E, otherwise the normal parameter reduction of E – e_j does not exist (see Theorem 3.5 in [23] on page 4814). Thus in Step 5, once again the authors have putted the parameters in A ∩ B into another reduced parameter set D without providing any proof for the dispensability of A ∩ B, which is incorrect. Thus, due to the afore-mentioned deficiencies, the ANPR algorithm is unable to maintain the rank and classification of the objects in U and cannot be used for the normal parameter reduction of soft sets. To clarify these facts, consider the following example.

Example 4.1. Consider the soft set (F, E) as displayed in Table 1, then by Algorithm 3:

Step 1. Input the soft set (F, E) as given by Table 1.

Step 2. Identify the parameters $e_{j}^{1}$ and $e_{j}^{0}$ in Table 1, which is $e_{9}^{1}$ and put it into the reduced parameter set C. Also, from Table 1, e₁ = e₅, e₂ = e₄ = e₁₀, and e₃ = e₈, so we can choose any one of them as special entry and the reaming are placed into the reduced parameter set Q. The new soft set $(F, \overset{´}{E})$ , where $\overset{´}{E} = E - C - Q$ is given by Table 4.

Step 3. Calculate $S (e_{\overset{´}{j}})$ for each $e_{\overset{´}{j}} \in \overset{´}{E}$ in Table 4. Then, find $A \subset \overset{´}{E}$ such that S_A is the multiple of |U|, and put A into the candidate parameter reduction set. Thus we obtain the subsets such as; {e₁, e₂}, {e₂, e₆}, {e₂, e₇}, and so on.

Step 4. Check the candidate parameter reduction set for the subsets A and B such that;

f_A (u₁) = f_A (u₂) = . . . = f_A (u₆) = k and

f_B (u₁) = f_B (u₂) = . . . = f_B (u₆) = k,

where k is a nonnegative integer. In this way we obtain only one subset A = {e₁, e₂} such that f_A (u₁) = f_A (u₂) = . . . = f_A (u₆) =1 and there is no other subset B which satisfy the given condition.

Step 5. Thus, A ∩ B = φ, and there is no parameter in the reduced parameter set D.

Step 6. Finally, $E - C - Q = {e_{1}, e_{2}, e_{3}, e_{6}, e_{7}} = \overset{´}{E}$ is the required optimal normal parameter reduction of (F, E) as given by Table 4.

Table 4
Tabular form of $(F, \overset{´}{E})$ in Example 4.1

U e ₁ e ₂ e ₃ e ₆ e ₇ f (.)

u ₁ 1 0 0 1 1 3

u ₂ 1 0 1 0 0 2

u ₃ 0 1 1 1 0 3

u ₄ 0 1 0 1 1 3

u ₅ 1 0 1 0 0 2

u ₆ 0 1 1 0 1 3

$S_{e_{\overset{´}{j}}}$ 3 3 4 3 3 16

U	e ₁	e ₂	e ₃	e ₆	e ₇	f (.)
u ₁	1	0	0	1	1	3
u ₂	1	0	1	0	0	2
u ₃	0	1	1	1	0	3
u ₄	0	1	0	1	1	3
u ₅	1	0	1	0	0	2
u ₆	0	1	1	0	1	3
$S_{e_{\overset{´}{j}}}$	3	3	4	3	3	16

According to Table 4, the decision partition is given by $C_{\overset{´}{E}} = {{u_{1}, u_{3}, u_{4}, u_{6}}_{3}, {u_{2}, u_{5}}_{2}} .$ (4.1) By comparing (3.1) with (4.1) we observe that the optimal and suboptimal choices for both the decision partitions are different from each other. This shows that the ANPR algorithm disturbed the original rank and classification of the objects in U and therefore cannot be used as a legitimate approach to normal parameter reduction of soft set.

5. The proposed approach to normal parameter reduction

In this section, first, we give some useful definitions and results and then provide a new algorithm for normal parameter reduction of soft set.

5.1. The proposed technique

Since in Definition 4.1, the expression u_1j = u_2j = . . . = u_nj used for the special entries is incorrect. In the following, we use a right expression for it and define an indiscernibility relation on the parameter set E.

Definition 5.1. For a soft set (F, E) over U, a parameter e_j is called indiscernible to e_k, denoted by e_j ∼ e_k, if u_ij = u_ik, where (1 ≤ i ≤ n) and (1 ≤ j, k ≤ m). Obviously, e_j ∼ e_j holds for all e_j ∈ E.

Definition 5.2. For a soft set (F, E) over U, the set of all indiscernible parameters to a parameter e is called the indiscernibility class of e, denoted by $C$ , i.e., $C = {\bar{e} \in E | e \sim \bar{e}}$ . The cardinality of the indiscernibility class $C$ is called length of the class, denoted by $L (C)$ .

The indiscernibility relation as defined in Definition 5.1 is an equivalence relation on the parameter set E. Moreover, based on the indiscernibility relation ∼, the parameter set E can be partitioned into disjoint indiscernibility classes $C_{1}, C_{2}, . . ., C_{ritsc}$ such that

$E = ⋃_{t = 1}^{r} C_{t},$

where t denotes the class label and r is the total number of the indiscernibility classes of E.

Definition 5.3. An indiscernibility class $C$ is called trivial, if $C$ has only one parameter, i.e., $L (C) = 1$ .

Proposition 5.1. For a soft set (F, E) over U, where E = {e₁, e₂,. . . , e_m}, if $C$ is any indiscernibility class of E, then $0 < L (C) \leq m$ .

Proof. The proof is straightforward.■

Theorem 5.1. Let (F, E) be a soft set over U and $A = {{\bar{e}}_{1}, {\bar{e}}_{2}, . . ., {\bar{e}}_{p}} \subset E$ such that the parameters ${\bar{e}}_{t}$ for (1 ≤ t ≤ p), are taken from p distinct indiscernibility classes ${\bar{C}}_{1}, {\bar{C}}_{2}, . . ., {\bar{C}}_{p}$ , respectively. If A is dispensable in E, then each |A|-tuple obtained from the cartesian product of indiscernibility classes ${\bar{C}}_{1}, {\bar{C}}_{2}, . . ., {\bar{C}}_{p}$ is also dispensable in E, where |A| denotes the cardinality of A.

Proof. Assume that (F, E) is a soft set over U and $A = {{\bar{e}}_{1}, {\bar{e}}_{2}, . . ., {\bar{e}}_{p}}$ is a dispensable set in E such that the parameters ${\bar{e}}_{t}$ for (1 ≤ t ≤ p), are taken from p distinct indiscernibility classes ${\bar{C}}_{1}, {\bar{C}}_{2}, . . ., {\bar{C}}_{p}$ , respectively. Since A is dispensable, by Definition 3.2, it must satisfy the condition f_A (u₁) = f_A (u₂) = . . . = f_A (u_n), which further satisfies the equations ${\begin{matrix} {\bar{u}}_{11} + {\bar{u}}_{12} + . . . + {\bar{u}}_{1 p} = q \\ {\bar{u}}_{21} + {\bar{u}}_{22} + . . . + {\bar{u}}_{2 p} = q \\ ⋮ \\ {\bar{u}}_{n 1} + {\bar{u}}_{n 2} + . . . + {\bar{u}}_{np} = q, \end{matrix}}$ (5.1) where q is a non-negative integer and q ≤ p. Suppose that the p distinct indiscernibility classes of E are given by

\begin{matrix} {\bar{C}}_{1} = {{\bar{e}}_{11}, {\bar{e}}_{12}, . . ., {\bar{e}}_{1 j}}, \\ {\bar{C}}_{2} = {{\bar{e}}_{21}, {\bar{e}}_{22}, . . ., {\bar{e}}_{2 k}}, \\ ⋮ \\ {\bar{C}}_{p} = {{\bar{e}}_{p 1}, {\bar{e}}_{p 2}, . . ., {\bar{e}}_{pl}}, \end{matrix}

and $T = ({\bar{e}}_{1 \overset{´}{j}}, {\bar{e}}_{2 \overset{´}{k}}, . . ., {\bar{e}}_{p \overset{´}{l}})$ is any arbitrary |A|-tuple obtained from the cartesian product of the given p distinct indiscernibility classes. ${\bar{e}}_{1} \in {\bar{C}}_{1}$ implies that ${\bar{e}}_{1} \sim {\bar{e}}_{1 \overset{´}{j}}$ and ${\bar{u}}_{i 1} = {\bar{u}}_{i \overset{´}{j}}$ , where (1 ≤ i ≤ n) and $(1 \leq \overset{´}{j} \leq j)$ . Similarly, ${\bar{e}}_{2} \in {\bar{C}}_{2}$ implies that ${\bar{e}}_{2} \sim {\bar{e}}_{2 \overset{´}{k}}$ and ${\bar{u}}_{i 2} = {\bar{u}}_{i \overset{´}{k}}$ , where $(1 \leq \overset{´}{k} \leq k)$ . Proceeding in the same way, we can write that ${\bar{e}}_{p} \sim {\bar{e}}_{p \overset{´}{l}}$ and ${\bar{u}}_{ip} = {\bar{u}}_{i \overset{´}{l}}$ , where (1 ≤ i ≤ n) and $(1 \leq \overset{´}{l} \leq l)$ . Thus, putting all these values in (5.1), we can get ${\begin{matrix} {\bar{u}}_{1 \overset{´}{j}} + {\bar{u}}_{1 \overset{´}{k}} + . . . + {\bar{u}}_{1 \overset{´}{l}} = q \\ {\bar{u}}_{2 \overset{´}{j}} + {\bar{u}}_{2 \overset{´}{k}} + . . . + {\bar{u}}_{2 \overset{´}{l}} = q \\ ⋮ \\ {\bar{u}}_{n \overset{´}{j}} + {\bar{u}}_{n \overset{´}{k}} + . . . + {\bar{u}}_{n \overset{´}{l}} = q, \end{matrix}}$ (5.2) which further implies that the condition

f_T (u₁) = f_T (u₂) = . . . = f_T (u_n)

also holds for T and hence by Definition 3.2, T is dispensable.■

We illustrate Theorem 5.1 by the following example.

Example 5.1. Consider the soft set (F, E) as displayed in Table 1, where e₁ ∼ e₅, e₂ ∼ e₄ ∼ e₁₀ and e₃ ∼ e₈. The total indiscernibility classes of E are given by: $C_{1} = {e_{1}, e_{5}}, C_{2} = {e_{2}, e_{4}, e_{10}}, C_{3} = {e_{3}, e_{8}}, C_{4} = {e_{6}}, C_{5} = {e_{7}}$ and $C_{6} = {e_{9}}$ , where $E = ⋃_{t = 1}^{6} C_{t}$ . If we take A = {e₁, e₄, e₉}, then A is dispensable because f_A (u₁) = f_A (u₂) = . . . = f_A (u₆) =2. Further, the total number of |A|-tuples (i.e., 3-tuples) generated from the cartesian product of $C_{1}$ , $C_{2}$ and $C_{6}$ are given by: $L (C_{1}) \times L (C_{2}) \times L (C_{6}) = 6$ , which are listed as: T₁ = (e₁, e₂, e₉), T₂ = (e₁, e₄, e₉), T₃ = (e₁, e₁₀, e₉), T₄ = (e₅, e₂, e₉), T₅ = (e₅, e₄, e₉), and T₆ = (e₅, e₁₀, e₉). From Table 1, we can check that the condition

f_{T
_i} (u₁) = f_{T
_i} (u₂) = . . . = f_{T
_i} (u₆) =2

is satisfied for all T_i, where (1 ≤ i ≤ 6). Thus, by Theorem 5.1, the |A|-tuples generated from the cartesian product of $C_{1}$ , $C_{2}$ and $C_{6}$ are also dispensable.

Theorem 5.2. For a soft set (F, E) over U, if A₁, A₂,. . . , A_p are disjoint dispensable subsets of E, then their union is also dispensable in E.

Proof. Let (F, E) be a soft set over U and A₁, A₂,. . . , A_p are the disjoint dispensable subsets of E. Then by Definition 3.2, the following equations must be satisfied for all A_i, where (1 ≤ i ≤ p), i.e.,

${\begin{cases} f_{A_{1}} (u_{1}) = f_{A_{1}} (u_{2}) = ... = f_{A_{1}} (u_{n}) \\ f_{A_{2}} (u_{1}) = f_{A_{2}} (u_{2}) = ... = f_{A_{2}} (u_{n}) \\ ⋮ \\ f_{A_{p}} (u_{1}) = f_{A_{p}} (u_{2}) = ... = f_{A_{p}} (u_{n}) . \end{cases}}$ (5.3) Since $⋂_{i = 1}^{p} A_{i} = φ$ , the above P equations further imply that f_K (u₁) = f_K (u₂) = . . . = f_K (u_n) , where $K = ⋃_{i = 1}^{p} A_{i}$ . Hence by Definition 3.2, the union of the disjoint dispensable subsets A₁, A₂,. . . , A_p of E is also dispensable, which completes the proof.■

Based on the above definitions and results, the proposed algorithm is given by Algorithm 4. For a clear description of the proposed algorithm, consider the following example.

Algorithm 4	Improved normal parameter reduction algorithm (INPR)
Step 1.	Input the soft set (F, E) and the parameter set E;
Step 2.	Identify the parameters $e_{j}^{1}$ and $e_{j}^{0}$ , and put them into the reduced parameter set C. The new soft set $(F, \overset{´}{E})$ will be established by $E - C = \overset{´}{E}$ ;
Step 3.	If there exist parameters e_i and e_j in $\overset{´}{E}$ such that e_i ∼ e_j for i ≠ j, then compute all the indiscernibility classes of $\overset{´}{E}$ , otherwise, go to Step 5;
Step 4.	Select only one parameter from each of the indiscernibility class of $\overset{´}{E}$ and the remaining are deleted from $\overset{´}{E}$ ;
Step 5.	Calculate $S (e_{\overset{´}{j}})$ for each $e_{\overset{´}{j}} \in \overset{´}{E}$ ;
Step 6.	Find $A \subset \overset{´}{E}$ such that S_A is the multiple of \|U\|, and put A into the candidate parameter reduction set;
Step 7.	Filter the candidate parameter reduction set, if f_A (u₁) = f_A (u₂) = . . . = f_A (u_n) is satisfied for A, then it will be saved; otherwise, it will be deleted;
Step 8.	If all the parameters in A belong to trivial indiscernibility classes, then find the maximum cardinality of A in the candidate parameter reduction set and compute E – C – A as the optimal normal parameter reduction of (F, E) otherwise, go to Step 9;
Step 9.	Replace the parameters in each A by their corresponding indiscernibility classes and compute \|A\|-tuples from their cartesian products. The total tuples obtained in this way will be listed in $T$ ;
Step 10.	Filter $T$ , if there exist disjoint tuples T_i, then replaced them by their union, otherwise, find T as the maximum cardinality in $T$ and compute E – C – T as the optimal normal parameter reduction of (F, E).

Example 5.2. Here we consider the same soft set (F, E) as given by Table 1. To find the normal parameter reduction of (F, E) by the proposed algorithm, we proceed as follows.

Step 1. Input the soft set (F, E) as given by Table 1.

Step 2. Determine the parameters $e_{j}^{1}$ and $e_{j}^{0}$ in Table 1 which is $e_{9}^{1}$ , and put it into the reduced parameter set C. The new soft set, i.e., $(F, \overset{´}{E})$ is given by Table 3.

Step 3. Since e₁ ∼ e₅, e₂ ∼ e₄ ∼ e₁₀, and e₃ ∼ e₈, compute the indiscernibility classes of $\overset{´}{E}$ , which can be obtained from Example 5.1 such as; $C_{1} = {e_{1}, e_{5}}$ , $C_{2} = {e_{2}, e_{4}, e_{10}}$ , $C_{3} = {e_{3}, e_{8}}$ , $C_{4} = {e_{6}}$ and $C_{5} = {e_{7}}$ .

Step 4. Select only one parameter from each of the indiscernibility class and delete the remaining to obtain $\overset{´}{E} = {e_{1}, e_{2}, e_{3}, e_{6}, e_{7}}$ .

Step 5. Calculate $S (e_{\overset{´}{j}})$ for each $e_{\overset{´}{j}} \in \overset{´}{E}$ , where $\overset{´}{j} \in {1, 2, 3, 6, 7}$ as shown in Table 5.

Table 5

Tabular form of $(F, \overset{´}{E})$ in Example 5.2

U	e ₁	e ₂	e ₃	e ₆	e ₇	f (.)
u ₁	1	0	0	1	1	3
u ₂	1	0	1	0	0	2
u ₃	0	1	1	1	0	3
u ₄	0	1	0	1	1	3
u ₅	1	0	1	0	0	2
u ₆	0	1	1	0	1	3
$S_{e_{\overset{´}{j}}}$	3	3	4	3	3	16

Step 6. Find $A \subset \overset{´}{E}$ such that S_A is the multiple of |U| and by Theorem 3.1, put A into the candidate parameter reduction set. Thus we obtain total 7 subsets such as; {e₁, e₂}, {e₁, e₆}, {e₁, e₇}, {e₂, e₆}, {e₂, e₇}, {e₆, e₇} and {e₁, e₂, e₆, e₇}.

Step 7. Filter the candidate parameter reduction set, if the condition f_A (u₁) = f_A (u₂) = . . . = f_A (u₆) is satisfied for the subset A, then it will be saved, otherwise delete A from the candidate parameter reduction set. Thus, we obtained only one subset such as; A = {e₁, e₂}.

Step 8. Since $e_{1} \in C_{1}$ and $e_{2} \in C_{2}$ , where $L (C 1) = 2$ and $L (C 2) = 3$ . Thus all the parameters in A belong to non-trivial indiscernibility classes. Replace the parameters in A by their corresponding indiscernibility classes and compute all the |A|-tuples from the cartesian product of the $C_{1}$ and $C_{2}$ . In this way, we obtain a total of 6 tuples, which are listed in $T$ as follows; $\begin{matrix} T = & {(e_{1}, e_{2}), (e_{1}, e_{4}), (e_{1}, e_{10}), (e_{5}, e_{2}), (e_{5}, e_{4}), \\ (e_{5}, e_{10})} . \end{matrix}$

Step 9. Filter $T$ for disjoint tuples and replace them by their union. Thus we obtain; $T = {(e_{1}, e_{10}), (e_{5}, e_{10}), (e_{1}, e_{2}, e_{4}, e_{5})} .$ Step 10. Select T = (e₁, e₂, e₄, e₅) as the maximum cardinality of the tuple in $T$ . Thus, E – C – T = {e₃, e₆, e₇, e₈, e₁₀} is the optimal normal parameter reduction of (F, E) as given by Table 2.

Remark 5.1. Here we remark two things. First, if there are no such parameters e_i and e_j in $\overset{´}{E}$ such that e_i ∼ e_j for i ≠ j, then Algorithm 4 does not need to compute the indiscernibility classes of E and works like Algorithm 2. Second, in Step 8 of Algorithm 4, if all the parameters in the candidate parameter reduction sets belong to the trivial indiscernibility classes, then the last two steps of Algorithm 4 (i.e,. Step 9 and Step 10) will be omitted (this case will be considered in Section 7).

5.2. The difference between the proposed algorithm and the NENPR Algorithm

The NENPR algorithm and the proposed algorithm follow the same footsteps to reach the optimal normal parameter reduction, however, they use different approaches to deal with the repeated columns (i.e., e_i = e_j) in soft set tables. The NENPR algorithm treats them separately in each step and do the same job repeatedly, which put an extra computation burden on the reduction process. While the proposed algorithm initially combines the parameters e_i = e_j into a single indiscernibility class and then selects only one parameter from each of the indiscernibility class to reduce the number of parameters in $\overset{´}{E}$ . Thus, unlike the NENPR algorithm, the proposed algorithm does not need to perform the same job (such as; finding the oriented-parameter sum, estimating the candidate parameter reduction set etc.,) repeatedly for the parameters e_i = e_j, which drastically reduced the computational complexity and workload of the normal parameter reduction process.

6. Comparison results

It was mentioned in [24] that NENPR algorithm performed well and has less computational complexity as compared to the NPR algorithm of [22]. Therefore, in this section, first we compare the proposed algorithm with the NENPR algorithm in terms of computational complexity. Then, we provide some experimental results to show that the proposed algorithm outperforms some state of the art algorithms while finding the normal parameter reduction in a Boolean data set.

Table 6
Comparison table

Comparison The NPR algorithm in [22] The NENPR algorithm in [24] The ANPR algorithm in [7] The proposed algorithm Remark

Optimal normal parameter reduction {e₃, e₆, e₇, e₈, e₁₀} {e₃, e₆, e₇, e₈, e₁₀} {e₁, e₂, e₃, e₆, e₇} {e₃, e₆, e₇, e₈, e₁₀} The output of the ANPR algorithm is not a normal parameter reduction

Entries accessed for estimating the PID/OPS 786 54 30 30 -

Accessed PID/OPS 6370 3177 31 31 -

The number of FPRS/CPRS before the filtration 127 63 7 7 -

The number of FPRS/CPRS after the filtration 15 7 Not certain 1 -

Operation involved Set operation, classification for PID Addition for estimating OPS Addition and set operation Classification, set operation All of the algorithms require certain set operations

Limitation Requires a great amount of computation for estimating PID Does not consider the same parameters e_i = e_j Partition and rank of the objects are not maintained Not suitable for those soft sets which have no similar parameters The proposed and NENPR algorithms give the same results if (F, A) has no similar parameters

Comparison	The NPR algorithm in [22]	The NENPR algorithm in [24]	The ANPR algorithm in [7]	The proposed algorithm	Remark
Optimal normal parameter reduction	{e₃, e₆, e₇, e₈, e₁₀}	{e₃, e₆, e₇, e₈, e₁₀}	{e₁, e₂, e₃, e₆, e₇}	{e₃, e₆, e₇, e₈, e₁₀}	The output of the ANPR algorithm is not a normal parameter reduction
Entries accessed for estimating the PID/OPS	786	54	30	30	-
Accessed PID/OPS	6370	3177	31	31	-
The number of FPRS/CPRS before the filtration	127	63	7	7	-
The number of FPRS/CPRS after the filtration	15	7	Not certain	1	-
Operation involved	Set operation, classification for PID	Addition for estimating OPS	Addition and set operation	Classification, set operation	All of the algorithms require certain set operations
Limitation	Requires a great amount of computation for estimating PID	Does not consider the same parameters e_i = e_j	Partition and rank of the objects are not maintained	Not suitable for those soft sets which have no similar parameters	The proposed and NENPR algorithms give the same results if (F, A) has no similar parameters

6.1. Computational complexity

6.1.1. Estimating the candidate parameter reduction set

Estimating the candidate parameter reduction set is a complex part of the normal parameter reduction process. To compute the candidate parameter reduction set, the NENPR algorithm first needs to compute the oriented-parameter sum for each parameter e_j ∈ E, where (1 ≤ j ≤ m), therefore the total number of access entries (i.e., u_ij) are given by m · n. Then, it checks every A ⊆ E for which S_A is a multiple of |U| and computes the equation S_A + S_{A
^c} = S_E for the multiplicity of its complement A^c. In this whole process, the number of access oriented-parameter sums are given by $C_{m}^{2} . 3 + C_{m}^{3} . 4 + . . . + C_{m}^{m / 2} . (m / 2) + 1$ (see in [24]). On the other hand, if there exist k parameters in E such that they are indiscernible to some other e_j ∈ E. Then the total number of indiscernibility classes of E will be r = m – k (see Example 5.1, where r = m – k = 10 – 4 =6). Thus for proposed algorithm, the number of access entries for estimating the oriented-parameter sums are given by r · n, which is less than m · n as k ≥ 0. Further, the proposed algorithm computes the combinations of the oriented-parameter sums from combination-1 to combination-r and finds all those subsets of E for which S_A is a multiple of |U|. The total number of the oriented-parameter sums access is given by $C_{r}^{1} + C_{r}^{2} + . . . + C_{r}^{r}$ . Thus, in both the cases, if the value of k increases, then the total number of access entries, as well as, access oriented-parameter sums for the proposed algorithm decreases as compared to the NENPR algorithm.

6.1.2. Filtering the candidate parameter reduction set

Suppose, the total number of the candidate parameter reduction sets of the proposed and NENPR algorithms are given by k and z, respectively. Let A = {e₁, e₂,. . . , e_p} is one of the k candidate parameter reduction sets for the proposed algorithm such that, the parameters e_j ∈ A, where (1 ≤ j ≤ p), are belongs to p distinct indiscernibility classes $C_{1}, C_{2}, . . ., C_{p}$ of E, respectively. If the length of each indiscernibility class is given by $L (C_{j}) = l_{j}$ , then the total number of |A|-tuples obtained from the cartesian product of the indiscernibility classes can be given by (l₁ × l₂ × . . . × l_p). Since, from Theorem 5.1, we know that if A is dispensable then all |A|-tuples obtained from the cartesian product of the indiscernibility classes are also dispensable. Therefore, there exists at least (l₁ × l₂ × . . . × l_p) subsets of E (i.e., |A|-tuples) which are included in z but not included in k. Thus, z ≥ (k + (l₁ × l₂ × . . . × l_p)).

6.2. Results and discussion

To discuss the efficiency of the proposed algorithm in capturing the normal parameter reduction in a Boolean data set. We applied the four algorithms that is, the proposed algorithm, the NPR algorithm of [22], the NENPR algorithm of [24], and the ANPR algorithm of [7] to the same Boolean data set that was given in Table 1. All algorithms were implemented in Python programming language and executed on Intel Core 2 Duo processer with 4 GB memory and Window 8 operating system. The experimental results obtained are summarized in Table 6, where the notations PID, OPS, FPRS and CPRS stand for the parameter importance degree, oriented-parameter sum, feasible parameter reduction set and candidate parameter reduction set, respectively. From Table 6, we see that the output obtained from the ANPR algorithm is not a normal parameter reduction and cannot be compared with our proposed algorithm. Moreover, from Table 6, it is clear that the proposed algorithm has accessed less number of entries and oriented-parameter sums as compared to the NPR and NENPR algorithm, respectively. Also, the proposed algorithm has only 7 subsets to check for the dispensability condition f_A (u₁) = f_A (u₂) = . . . = f_A (u_n), while the NPR and NENPR algorithms must check 127 and 63 subsets for the same dispensability condition, respectively. Thus, it is evident that the proposed algorithm has decreased the computational complexity at every stage of the reduction process, and efficiently captured the normal parameter reduction as compared to the other three algorithms. However, the proposed algorithm and the NENPR algorithm give the same results for a soft set having no similar parameters.

7. Application in decision making problem

This section deals with a real-life application of our proposed algorithm in a medical diagnostic problem. We reconsider the hiatal hernia disease problem that was discussed by Danjuma et al. in [7]. First we show that the given problem cannot be solved by the ANPR algorithm. Then we solve the same problem by our proposed algorithm and elaborate its application in decision making.

The hiatal hernia disease problem

The hiatal hernia disease can affect organs in the chest cavity and causes abnormalities of stomach and Acid reflux or Gastroesophageal reflux disease (GERD). Normally, it occurs when the diaphragm (a separating membrane between the chest and abdominal cavity) is affected by the enlargement of the upper part of the stomach. The data are collected from the Mariri comprehensive hospital in Kino stat, Nigeria, which is displayed in Table 7. According to Table 7, there are 50 patients where each patient is described with 13 different symptoms. Let U = {u₁, u₂,. . . , u₅₀} is the set of all patients and E = {e₁, e₂,. . . , e₁₃} is the set of symptoms where each e_i for (1 ≤ i ≤ 13), stands for heartburn, chest pain, nausea, vomiting, burping, water brush, appearance of a large amount of saliva, cough, difficulty in swallowing, passing black stool, abdominal pain, belching and fever, respectively. From the choice values given in Table 7, the doctors can decide that the patients at optimal choice such as; {u₇, u₈, u₂₆, u₂₇, u₄₇, u₅₀} are those who are affected with hiatal hernia disease. Meanwhile, the patients at suboptimal choice such as; {u₂, u₄, u₁₀, u₁₂, u₁₄, u₁₅, u₁₇, u₁₈, u₁₉, u₂₂, u₂₃, u₂₇, u₃₀, u₃₄, u₃₅, u₄₆, u₄₈} have the tendency of being affected with hiatal hernia disease, if the precautions have not been taken. Similarly for all other patients, the doctors can put their decision according to their level of choice values.

Table 7
Tabular form of (F, E) given in hiatal hernia disease problem

U e ₁ e ₂ e ₃ e ₄ e ₅ e ₆ e ₇ e ₈ e ₉ e ₁₀ e ₁₁ e ₁₂ e ₁₃ f (.)

u ₁ 1 1 1 1 0 1 1 0 0 1 0 1 0 8

u ₂ 0 1 1 1 1 1 1 1 0 1 0 1 0 9

u ₃ 1 1 0 0 1 1 1 0 0 1 1 0 0 7

u ₄ 1 1 1 1 0 1 1 1 0 1 0 1 0 9

u ₅ 0 1 1 1 1 0 1 0 0 1 1 1 0 8

u ₆ 1 1 0 0 1 1 1 0 0 1 1 0 0 7

u ₇ 1 1 1 1 1 0 1 1 0 0 1 1 1 10

u ₈ 1 1 1 1 1 0 1 1 0 0 1 1 1 10

u ₉ 1 1 1 1 1 1 1 0 0 0 0 1 0 8

u ₁₀ 1 1 0 0 1 1 1 1 0 1 1 0 1 9

u ₁₁ 0 1 0 1 1 1 1 1 0 1 0 0 0 7

u ₁₂ 1 1 1 1 0 0 1 1 0 1 1 1 0 9

u ₁₃ 1 1 0 1 1 1 1 1 0 0 0 0 0 7

u ₁₄ 0 0 1 1 1 1 1 1 0 1 1 1 0 9

u ₁₅ 0 1 1 1 1 1 1 1 0 1 0 1 0 9

u ₁₆ 1 1 0 0 1 1 1 0 0 1 1 0 0 7

u ₁₇ 1 1 1 1 0 0 1 1 0 1 1 1 0 9

u ₁₈ 1 1 1 1 0 0 1 1 0 1 1 1 0 9

u ₁₉ 1 1 1 1 0 0 1 1 0 1 1 1 0 9

u ₂₀ 1 0 1 1 0 1 1 0 0 1 1 1 0 8

u ₂₁ 1 1 0 0 1 1 1 0 0 1 1 0 0 7

u ₂₂ 1 0 1 1 0 1 1 1 0 1 1 1 0 9

u ₂₃ 1 1 1 1 0 0 1 1 0 1 1 1 0 9

u ₂₄ 1 1 0 0 1 1 1 0 0 1 1 0 0 7

u ₂₅ 1 1 1 1 1 1 1 0 0 0 0 1 0 8

u ₂₆ 1 1 1 1 1 1 1 1 0 0 0 1 1 10

u ₂₇ 1 1 1 0 1 1 1 0 0 1 1 1 0 9

u ₂₈ 1 1 0 1 1 1 1 1 0 0 0 0 0 7

u ₂₉ 1 1 1 1 1 1 1 0 0 0 0 1 0 8

u ₃₀ 1 1 1 1 1 1 1 1 0 0 0 1 0 9

u ₃₁ 0 1 1 1 1 0 1 0 0 1 1 1 0 8

u ₃₂ 1 1 0 0 1 1 1 0 0 1 1 0 0 7

u ₃₃ 1 1 1 1 1 1 1 0 0 0 0 1 0 8

u ₃₄ 0 1 1 1 1 0 1 1 0 1 1 1 0 9

u ₃₅ 1 1 1 1 1 1 1 0 0 0 0 1 0 9

u ₃₆ 0 0 1 1 1 1 1 0 0 1 1 1 0 8

u ₃₇ 1 1 0 0 1 1 1 0 0 1 1 0 0 7

u ₃₈ 1 1 0 0 1 1 1 0 0 1 1 0 0 7

u ₃₉ 1 1 0 0 1 1 1 0 0 1 1 0 0 7

u ₄₀ 1 0 1 1 1 1 1 0 0 0 1 1 0 8

u ₄₁ 0 0 1 1 1 1 1 0 0 1 1 1 0 8

u ₄₂ 0 1 1 1 1 1 1 0 0 1 0 1 0 8

u ₄₃ 1 1 0 0 1 1 1 0 0 1 1 0 0 7

u ₄₄ 0 1 0 1 1 0 1 0 0 1 1 0 0 6

u ₄₅ 1 0 0 1 0 1 1 1 0 1 1 0 0 7

u ₄₆ 0 0 1 1 1 1 1 1 0 1 1 1 0 9

u ₄₇ 1 1 1 1 1 1 1 1 0 0 0 1 1 10

u ₄₈ 0 1 1 1 1 1 1 1 0 1 0 1 0 9

u ₄₉ 1 1 0 0 1 1 1 0 0 1 1 0 0 7

u ₅₀ 1 1 1 1 1 1 1 1 0 0 0 1 1 10

U	e ₁	e ₂	e ₃	e ₄	e ₅	e ₆	e ₇	e ₈	e ₁₀	e ₁₁	e ₁₂	e ₁₃	f (.)
u ₁	1	1	1	1	0	1	1	0	1	0	1	0	8
u ₂	0	1	1	1	1	1	1	1	1	0	1	0	9
u ₃	1	1	0	0	1	1	1	0	1	1	0	0	7
u ₄	1	1	1	1	0	1	1	1	1	0	1	0	9
u ₅	0	1	1	1	1	0	1	0	1	1	1	0	8
u ₆	1	1	0	0	1	1	1	0	1	1	0	0	7
u ₇	1	1	1	1	1	0	1	1	0	1	1	1	10
u ₈	1	1	1	1	1	0	1	1	0	1	1	1	10
u ₉	1	1	1	1	1	1	1	0	0	0	1	0	8
u ₁₀	1	1	0	0	1	1	1	1	1	1	0	1	9
u ₁₁	0	1	0	1	1	1	1	1	1	0	0	0	7
u ₁₂	1	1	1	1	0	0	1	1	1	1	1	0	9
u ₁₃	1	1	0	1	1	1	1	1	0	0	0	0	7
u ₁₄	0	0	1	1	1	1	1	1	1	1	1	0	9
u ₁₅	0	1	1	1	1	1	1	1	1	0	1	0	9
u ₁₆	1	1	0	0	1	1	1	0	1	1	0	0	7
u ₁₇	1	1	1	1	0	0	1	1	1	1	1	0	9
u ₁₈	1	1	1	1	0	0	1	1	1	1	1	0	9
u ₁₉	1	1	1	1	0	0	1	1	1	1	1	0	9
u ₂₀	1	0	1	1	0	1	1	0	1	1	1	0	8
u ₂₁	1	1	0	0	1	1	1	0	1	1	0	0	7
u ₂₂	1	0	1	1	0	1	1	1	1	1	1	0	9
u ₂₃	1	1	1	1	0	0	1	1	1	1	1	0	9
u ₂₄	1	1	0	0	1	1	1	0	1	1	0	0	7
u ₂₅	1	1	1	1	1	1	1	0	0	0	1	0	8
u ₂₆	1	1	1	1	1	1	1	1	0	0	1	1	10
u ₂₇	1	1	1	0	1	1	1	0	1	1	1	0	9
u ₂₈	1	1	0	1	1	1	1	1	0	0	0	0	7
u ₂₉	1	1	1	1	1	1	1	0	0	0	1	0	8
u ₃₀	1	1	1	1	1	1	1	1	0	0	1	0	9
u ₃₁	0	1	1	1	1	0	1	0	1	1	1	0	8
u ₃₂	1	1	0	0	1	1	1	0	1	1	0	0	7
u ₃₃	1	1	1	1	1	1	1	0	0	0	1	0	8
u ₃₄	0	1	1	1	1	0	1	1	1	1	1	0	9
u ₃₅	1	1	1	1	1	1	1	0	0	0	1	0	9
u ₃₆	0	0	1	1	1	1	1	0	1	1	1	0	8
u ₃₇	1	1	0	0	1	1	1	0	1	1	0	0	7
u ₃₈	1	1	0	0	1	1	1	0	1	1	0	0	7
u ₃₉	1	1	0	0	1	1	1	0	1	1	0	0	7
u ₄₀	1	0	1	1	1	1	1	0	0	1	1	0	8
u ₄₁	0	0	1	1	1	1	1	0	1	1	1	0	8
u ₄₂	0	1	1	1	1	1	1	0	1	0	1	0	8
u ₄₃	1	1	0	0	1	1	1	0	1	1	0	0	7
u ₄₄	0	1	0	1	1	0	1	0	1	1	0	0	6
u ₄₅	1	0	0	1	0	1	1	1	1	1	0	0	7
u ₄₆	0	0	1	1	1	1	1	1	1	1	1	0	9
u ₄₇	1	1	1	1	1	1	1	1	0	0	1	1	10
u ₄₈	0	1	1	1	1	1	1	1	1	0	1	0	9
u ₄₉	1	1	0	0	1	1	1	0	1	1	0	0	7
u ₅₀	1	1	1	1	1	1	1	1	0	0	1	1	10

Now, Our problem is to find a least subset of E that can provide the same decision order for the patients as the entire set of parameters. In other words, we have to identify those parameters (symptoms) in E which are jointly sufficient and individually necessary for the original decision order of the patients. For this, let us apply the ANPR algorithm to the given soft set (F, E), then by Algorithm 3, the parameters {u₇, u₉} and {u₃} can be putted into the reduced parameter sets C and D, respectively. Further, there exist two subsets A = {e₁, e₄, e₅, e₁₀} and B = {e₂, e₄, e₆, e₁₁} such that;

f_A (u₁) = f_A (u₂) = . . . = f_A (u₅₀) =3, and

f_B (u₁) = f_B (u₂) = . . . = f_B (u₅₀) =3.

Thus A ∩ B = {e₄} is kept into the reduced parameter reduction set D. Finally, E – C – D – Q = {e₁, e₂, e₅, e₆, e₈, e₁₀, e₁₁, e₁₂, e₁₃} is the optimal normal parameter reduction as given by Table 8. From Table 8, the optimal and suboptimal choices for the reduced table are given by u₁₀ and {u₇, u₈, u₂₆, u₂₇, u₄₇, u₅₀}, respectively, which are different from Table 7. This implies that the ANPR algorithm was failed to provide a minimum subset of E that can provide the same decision ability as the entire set of parameters.

Table 8

Normal parameter reduction of (F, E) by ANPR algorithm

U	e ₁	e ₂	e ₅	e ₆	e ₈	e ₁₀	e ₁₁	e ₁₂	e ₁₃	f (.)
u ₁	1	1	0	1	0	1	0	1	0	5
u ₂	0	1	1	1	1	1	0	1	0	6
u ₃	1	1	1	1	0	1	1	0	0	6
u ₄	1	1	0	1	1	1	0	1	0	6
u ₅	0	1	1	0	0	1	1	1	0	5
u ₆	1	1	1	1	0	1	1	0	0	6
u ₇	1	1	1	0	1	0	1	1	1	7
u ₈	1	1	1	0	1	0	1	1	1	7
u ₉	1	1	1	1	0	0	0	1	0	5
u ₁₀	1	1	1	1	1	1	1	0	1	8
u ₁₁	0	1	1	1	1	1	0	0	0	5
u ₁₂	1	1	0	0	1	1	1	1	0	6
u ₁₃	1	1	1	1	1	0	0	0	0	5
u ₁₄	0	0	1	1	1	1	1	1	0	6
u ₁₅	0	1	1	1	1	1	0	1	0	6
u ₁₆	1	1	1	1	0	1	1	0	0	6
u ₁₇	1	1	0	0	1	1	1	1	0	6
u ₁₈	1	1	0	0	1	1	1	1	0	6
u ₁₉	1	1	0	0	1	1	1	1	0	6
u ₂₀	1	0	0	1	0	1	1	1	0	5
u ₂₁	1	1	1	1	0	1	1	0	0	6
u ₂₂	1	0	0	1	1	1	1	1	0	6
u ₂₃	1	1	0	0	1	1	1	1	0	6
u ₂₄	1	1	1	1	0	1	1	0	0	6
u ₂₅	1	1	1	1	0	0	0	1	0	5
u ₂₆	1	1	1	1	1	0	0	1	1	7
u ₂₇	1	1	1	1	0	1	1	1	0	7
u ₂₈	1	1	1	1	1	0	0	0	0	5
u ₂₉	1	1	1	1	0	0	0	1	0	5
u ₃₀	1	1	1	1	1	0	0	1	0	6
u ₃₁	0	1	1	0	0	1	1	1	0	5
u ₃₂	1	1	1	1	0	1	1	0	0	6
u ₃₃	1	1	1	1	0	0	0	1	0	5
u ₃₄	0	1	1	0	1	1	1	1	0	6
u ₃₅	1	1	1	1	0	0	0	1	0	6
u ₃₆	0	0	1	1	0	1	1	1	0	5
u ₃₇	1	1	1	1	0	1	1	0	0	6
u ₃₈	1	1	1	1	0	1	1	0	0	6
u ₃₉	1	1	1	1	0	1	1	0	0	6
u ₄₀	1	0	1	1	0	0	1	1	0	5
u ₄₁	0	0	1	1	0	1	1	1	0	5
u ₄₂	0	1	1	1	0	1	0	1	0	5
u ₄₃	1	1	1	1	0	1	1	0	0	6
u ₄₄	0	1	1	0	0	1	1	0	0	4
u ₄₅	1	0	0	1	1	1	1	0	0	5
u ₄₆	0	0	1	1	1	1	1	1	0	6
u ₄₇	1	1	1	1	1	0	0	1	1	7
u ₄₈	0	1	1	1	1	1	0	1	0	6
u ₄₉	1	1	1	1	0	1	1	0	0	6
u ₅₀	1	1	1	1	1	0	0	1	1	7

On the other hand, if we apply our proposed algorithm to the same problem, then we proceed as follows.

Step 1. Consider the soft set (F, E) as displayed in Table 7.

Step 2. Put the parameters $e_{7}^{1}$ and $e_{9}^{0}$ into the reduced parameter set C and obtained $\overset{´}{E} = E - C$ . That is, $\overset{´}{E} = {e_{1}, e_{2}, e_{3}, e_{4}, e_{5}, e_{6}, e_{8}, e_{10}, e_{11}, e_{12}, e_{13}}$ .

Step 3. Since e₃ ∼ e₁₂, we have to compute all the indiscernibility class of $\overset{´}{E}$ , which are listed as; $C_{1} = {e_{1}}$ , $C_{2} = {e_{2}}$ , $C_{3} = {e_{3}, e_{12}}$ , $C_{4} = {e_{4}}$ , $C_{5} = {e_{5}}$ , $C_{6} = {e_{6}}$ , $C_{7} = {e_{8}}$ , $C_{8} = {e_{10}}$ , $C_{9} = {e_{11}}$ , $C_{10} = {e_{13}}$ .

Step 4. Take only one parameter from each of the indiscernibility class and obtained the parameter set $\overset{´}{E}$ , i.e. $\overset{´}{E} = {e_{1}, e_{2}, e_{3}, e_{4}, e_{5}, e_{6}, e_{8}, e_{10}, e_{11}, e_{13}}$ .

Step 5. Calculate $S (e_{\overset{´}{j}})$ for each $e_{\overset{´}{j}} \in \overset{´}{E}$ as shown in Table 9.

Table 9

Tabular form of $(F, \overset{´}{E})$

U	e ₁	e ₂	e ₃	e ₄	e ₅	e ₆	e ₈	e ₁₀	e ₁₁	e ₁₃	f (.)
u ₁	1	1	1	1	0	1	0	1	0	0	6
u ₂	0	1	1	1	1	1	1	1	0	0	7
u ₃	1	1	0	0	1	1	0	1	1	0	6
u ₄	1	1	1	1	0	1	1	1	0	0	7
u ₅	0	1	1	1	1	0	0	1	1	0	6
u ₆	1	1	0	0	1	1	0	1	1	0	6
u ₇	1	1	1	1	1	0	1	0	1	1	8
u ₈	1	1	1	1	1	0	1	0	1	1	8
u ₉	1	1	1	1	1	1	0	0	0	0	6
u ₁₀	1	1	0	0	1	1	1	1	1	1	8
u ₁₁	0	1	0	1	1	1	1	1	0	0	6
u ₁₂	1	1	1	1	0	0	1	1	1	0	7
u ₁₃	1	1	0	1	1	1	1	0	0	0	6
u ₁₄	0	0	1	1	1	1	1	1	1	0	7
u ₁₅	0	1	1	1	1	1	1	1	0	0	7
u ₁₆	1	1	0	0	1	1	0	1	1	0	6
u ₁₇	1	1	1	1	0	0	1	1	1	0	7
u ₁₈	1	1	1	1	0	0	1	1	1	0	7
u ₁₉	1	1	1	1	0	0	1	1	1	0	7
u ₂₀	1	0	1	1	0	1	0	1	1	0	6
u ₂₁	1	1	0	0	1	1	0	1	1	0	6
u ₂₂	1	0	1	1	0	1	1	1	1	0	7
u ₂₃	1	1	1	1	0	0	1	1	1	0	7
u ₂₄	1	1	0	0	1	1	0	1	1	0	6
u ₂₅	1	1	1	1	1	1	0	0	0	0	6
u ₂₆	1	1	1	1	1	1	1	0	0	1	8
u ₂₇	1	1	1	0	1	1	0	1	1	0	7
u ₂₈	1	1	0	1	1	1	1	0	0	0	6
u ₂₉	1	1	1	1	1	1	0	0	0	0	8
u ₃₀	1	1	1	1	1	1	1	0	0	0	7
u ₃₁	0	1	1	1	1	0	0	1	1	0	6
u ₃₂	1	1	0	0	1	1	0	1	1	0	6
u ₃₃	1	1	1	1	1	1	0	0	0	0	6
u ₃₄	0	1	1	1	1	0	1	1	1	0	7
u ₃₅	1	1	1	1	1	1	0	0	0	0	7
u ₃₆	0	0	1	1	1	1	0	1	1	0	6
u ₃₇	1	1	0	0	1	1	0	1	1	0	6
u ₃₈	1	1	0	0	1	1	0	1	1	0	6
u ₃₉	1	1	0	0	1	1	0	1	1	0	6
u ₄₀	1	0	1	1	1	1	0	0	1	0	6
u ₄₁	0	0	1	1	1	1	0	1	1	0	6
u ₄₂	0	1	1	1	1	1	0	1	0	0	8
u ₄₃	1	1	0	0	1	1	0	1	1	0	6
u ₄₄	0	1	0	1	1	0	0	1	1	0	5
u ₄₅	1	0	0	1	0	1	1	1	1	0	6
u ₄₆	0	0	1	1	1	1	1	1	1	0	7
u ₄₇	1	1	1	1	1	1	1	0	0	1	8
u ₄₈	0	1	1	1	1	1	1	1	0	0	7
u ₄₉	1	1	0	0	1	1	0	1	1	0	6
u ₅₀	1	1	1	1	1	1	1	0	0	1	8
S _{e _i}	37	42	33	37	39	39	25	37	32	6

Step 6. Find $A \subseteq \overset{´}{E}$ , for which S_A is the multiple of |U|, and put A into the candidate parameter reduction set. Thus we obtained a total of 21 subsets such as; {e₂, e₃, e₈}, {e₂, e₄, e₆, e₁₁}, {e₁, e₄, e₅, e₁₀}, {e₁, e₂, e₃, e₄, e₅, e₈, e₁₀}, and so on.

Step 7. Filter the candidate parameter reduction set. If the condition f_A (u₁) = f_A (u₂) = . . . = f_A (u₅₀) is satisfied for a subset A then it will be saved, otherwise will be deleted from the candidate parameter reduction set. Thus, we obtained only two subsets such as, A = {e₂, e₄, e₆, e₁₁} and B = {e₁, e₄, e₅, e₁₀}.

Step 8. Since all the parameters in A as well as in B belong to the trivial indiscernibility classes because their lengths are equal to 1. Thus, we just need to find the maximum cardinality among the two candidate parameter reduction sets A and B. But |A| = |B|, this implies that we can select any one of them as our desired candidate parameter reduction set. Finally, E – C – B = {e₃, e₆, e₇, e₈, e₁₀} is computed as the required optimal normal parameter reduction of (F, E) as displayed in Table 10.

Table 10

Normal parameter reduction of (F, E) by the proposed algorithm

U	e ₂	e ₃	e ₆	e ₈	e ₁₁	e ₁₂	e ₁₃	f (.)
u ₁	1	1	1	0	0	1	0	4
u ₂	1	1	1	1	0	1	0	5
u ₃	1	0	1	0	1	0	0	3
u ₄	1	1	1	1	0	1	0	5
u ₅	1	1	0	0	1	1	0	4
u ₆	1	0	1	0	1	0	0	3
u ₇	1	1	0	1	1	1	1	6
u ₈	1	1	0	1	1	1	1	6
u ₉	1	1	1	0	0	1	0	4
u ₁₀	1	0	1	1	1	0	1	5
u ₁₁	1	0	1	1	0	0	0	3
u ₁₂	1	1	0	1	1	1	0	5
u ₁₃	1	0	1	1	0	0	0	3
u ₁₄	0	1	1	1	1	1	0	5
u ₁₅	1	1	1	1	0	1	0	5
u ₁₆	1	0	1	0	1	0	0	3
u ₁₇	1	1	0	1	1	1	0	5
u ₁₈	1	1	0	1	1	1	0	5
u ₁₉	1	1	0	1	1	1	0	5
u ₂₀	0	1	1	0	1	1	0	4
u ₂₁	1	0	1	0	1	0	0	3
u ₂₂	0	1	1	1	1	1	0	5
u ₂₃	1	1	0	1	1	1	0	5
u ₂₄	1	0	1	0	1	0	0	3
u ₂₅	1	1	1	0	0	1	0	4
u ₂₆	1	1	1	1	0	1	1	6
u ₂₇	1	1	1	0	1	1	0	5
u ₂₈	1	0	1	1	0	0	0	3
u ₂₉	1	1	1	0	0	1	0	4
u ₃₀	1	1	1	1	0	1	0	5
u ₃₁	1	1	0	0	1	1	0	4
u ₃₂	1	0	1	0	1	0	0	3
u ₃₃	1	1	1	0	0	1	0	4
u ₃₄	1	1	0	1	1	1	0	5
u ₃₅	1	1	1	0	0	1	0	5
u ₃₆	0	1	1	0	1	1	0	4
u ₃₇	1	0	1	0	1	0	0	3
u ₃₈	1	0	1	0	1	0	0	3
u ₃₉	1	0	1	0	1	0	0	3
u ₄₀	0	1	1	0	1	1	0	4
u ₄₁	0	1	1	0	1	1	0	4
u ₄₂	1	1	1	0	0	1	0	4
u ₄₃	1	0	1	0	1	0	0	3
u ₄₄	1	0	0	0	1	0	0	2
u ₄₅	0	0	1	1	1	0	0	3
u ₄₆	0	1	1	1	1	1	0	5
u ₄₇	1	1	1	1	0	1	1	6
u ₄₈	1	1	1	1	0	1	0	5
u ₄₉	1	0	1	0	1	0	0	3
u ₅₀	1	1	1	1	0	1	1	6

Now consider the reduced Table 10, then the optimal and suboptimal choices are given by {u₇, u₈, u₂₆, u₄₇, u₅₀} and {u₂, u₄, u₁₀, u₁₂, u₁₄, u₁₅, u₁₇, u₁₈, u₁₉, u₂₂, u₂₃, u₂₇, u₃₀, u₃₄, u₃₅, u₄₆, u₄₈}, respectively, which are same as that of Table 7. This shows that our proposed algorithm has the ability to find a subset of E with least number of symptoms that can provide the same decision order for the patients as the entire set of parameters. Thus, our algorithm helps the doctors in providing the same decision partition of the patients with limited number of symptoms and save their time.

8. Conclusion

Many algorithms have been developed for the normal parameter reduction of soft set, however, the case of repeated columns has not been gained considerable attention so far, although this phenomenon is very useful to reduce the workload of an algorithm. Recently in 2017, Danjuma et al. [7] consider this issue and proposed the ANPR algorithm for normal parameter reduction of soft sets. In this study, initially we discussed some drawbacks of the ANPR algorithm and shown that it has no mathematical existence. Then we presented an improved algorithm for normal parameter reduction of soft set that has overcome the previous problems of the ANPR algorithm. Some comparison results are given to show that the proposed algorithm has relatively less computational complexity and workload as compared to the existing algorithms of normal parameter reduction of soft set. Finally, the proposed algorithm is applied to the hiatal hernia disease problem to elaborate its application in a real-world problem. Since very limited practical applications of soft set-based parameter reduction can be found in the existing literature. Thus, the practical applications of soft set reduction require more attention and should be explored further.

Conflict of interest

The authors declare that there is no conflict of interest regarding the publication of this article.

Footnotes

Acknowledgments

This work is supported by the National Natural Science Foundation of China (Grant No. 61673011).

References

J.C.R.

Alcantud ,

Santos-García and

Hernändez-Galilea , Glaucoma diagnosis: A soft set based decision making procedure, In Conference of the Spanish Association for Artificial Intelligence, Springer, (2015), pp. 49–60.

M.I.

Ali , Another view on reduction of parameters in soft sets, Applied Soft Computing 12(6) (2012), 1814–1821.

A.O.

Atagün ,

Kamaci and

Oktay , Reduced soft matrices and generalized products with applications in decision making, Neural Computing and Applications 29(9) (2018), 445–456.

K.T.

Atanassov , Intuitionistic fuzzy sets, In Intuitionistic fuzzy sets, Springer, (1999), pp. 1–137.

Chen ,

Tsang ,

D.S.

Yeung and

Wang , The parameterization reduction of soft sets and its applications, Computers & Mathematics with Applications 49(5-6) (2005), 757–763.

Danjuma ,

Herawan ,

M.A.

Ismail ,

Chiroma ,

A.I.

Abubakar and

A.M.

Zeki , A review on soft set-based parameter reduction and decision making, IEEE Access 5 (2017), 4671–4689.

Danjuma ,

M.A.

Ismail and

Herawan , An alternative approach to normal parameter reduction algorithm for soft set theory, IEEE Access 5 (2017), 4732–4746.

Feng ,

Cho ,

Pedrycz ,

Fujita and

Herawan , Soft set based association rule mining, Knowledge-Based Systems 111 (2016), 268–282.

Feng ,

Li ,

Davvaz and

M.I.

Ali , Soft sets combined with fuzzy sets and rough sets: A tentative approach, Soft Computing 14(9) (2010), 899–911.

10.

M.B.

Gorzałczany , A method of inference in approximate reasoning based on interval-valued fuzzy sets, Fuzzy Sets and Systems 21(1) (1987), 1–17.

11.

Han , Comments on “normal parameter reduction in soft set based on particle swarm optimization algorithm”, Applied Mathematical Modelling 40(23-24) (2016), 10828–10834.

12.

Herawan , Soft set-based decision making for patients suspected influenza-like illness, In International Journal of Modern Physics: Conference Series, volume 1, (2010), pp. 1–5.

13.

Herawan and

M.M.

Deris , A soft set approach for association rules mining, Knowledge-Based Systems 24(1) (2011), 186–195.

14.

Jiang ,

Zhan and

Chen , Covering based variable precision (i, t)-fuzzy rough sets with applications to multiattribute decision-making, IEEE Transactions on Fuzzy Systems (2018).

15.

Kamaci ,

A.O.

Atagün and

Sönmezoğlu , Row-products of soft matrices with applications in multiple-disjoint decision making, Applied Soft Computing 62 (2018), 892–914.

16.

Kamaci ,

Saltik ,

Fulya Akiz and

A. Osman

Atagün , Cardinality inverse soft matrix theory and its applications in multicriteria group decision making, Journal of Intelligent & Fuzzy Systems 34(3) (2018), 2031–2049.

17.

A.Z.

Khameneh and

Kilicman , Parameter reduction of fuzzy soft sets: An adjustable approach based on the three-way decision, International Journal of Fuzzy Systems 20(3) (2018), 928–942.

18.

A.Z.

Khameneh ,

Kilicman and

A.R.

Salleh , An adjustable approach to multi-criteria group decision-making based on a preference relationship under fuzzy soft information, International Journal of Fuzzy Systems 19(6) (2017), 1840–1865.

19.

M.S.

Khan ,

M.A.

Al-Garadi ,

A.W.A.

Wahab and

Her-awan , An alternative data filling approach for prediction of missing data in soft sets (adfis), Springer Plus 5(1) (2016), 1348.

20.

Kolmogorov , Foundations of the Theory of Probability: Second English Edition.

21.

Kong ,

Ai ,

Wang ,

Li ,

Ma and

Lu , New normal parameter reduction method in fuzzy soft set theory, IEEE Access 7 (2019), 2986–2998.

22.

Kong ,

Gao ,

Wang and

Li , The normal parameter reduction of soft sets and its algorithm, Computers & Mathematics with Applications 56(12) (2008), 3029–3037.

23.

Kong ,

Jia ,

Zhang and

Wang , Normal parameter reduction in soft set based on particle swarm optimization algorithm, Applied Mathematical Modelling 39(16) (2015), 4808–4820.

24.

Ma ,

Sulaiman ,

Qin ,

Herawan and

J.M.

Zain , A new efficient normal parameter reduction algorithm of soft sets, Computers & Mathematics with Applications 62(2) (2011), 588–598.

25.

Ma ,

Zhan ,

M.I.

Ali and

Mehmood , A survey of decision making methods based on two classes of hybrid soft set models, Artificial Intelligence Review 49(4) (2018), 511–529.

26.

Maji ,

A.R.

Roy and

Biswas , An application of soft sets in a decision making problem, Computers & Mathematics with Applications 44(8-9) (2002), 1077–1083.

27.

Molodtsov , Soft set theory—first results, Computers & Mathematics with Applications 37(4-5) (1999), 19–31.

28.

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

29.

Renukadevi and

Sangeetha , Characterizations of normal parameter reductions of soft sets, Annals of Fuzzy Mathematics and Informatics (2015).

30.

Yuksel ,

Dizman ,

Yildizdan and

Sert , Application of soft sets to diagnose the prostate cancer risk, Journal of Inequalities and Applications 2013(1) (2013), 229.

31.

L.A.

Zadeh , et al., Fuzzy sets, Information and Control 8(3) (1965), 338–353.

32.

Zhan and

J.C.R.

Alcantud , A novel type of soft rough covering and its application to multicriteria group decision making, Artificial Intelligence Review (2018), 1–30.

33.

Zhan and

J.C.R.

Alcantud , A survey of parameter reduction of soft sets and corresponding algorithms, Artificial Intelligence Review (2018), 1–34.

34.

Zhan ,

Sun and

J.C.R.

Alcantud , Covering based multigranulation (i, t)-fuzzy rough set models and applications in multi-attribute group decision-making, Information Sciences 476 (2019), 290–318.

35.

Zhan and

Wang , Certain types of soft coverings based rough sets with applications, International Journal of Machine Learning and Cybernetics (2018), 1–12.

36.

Zhan and

Zhu , Reviews on decision making methods based on (fuzzy) soft sets and rough soft sets, Journal of Intelligent & Fuzzy Systems 29(3) (2015), 1169–1176.

37.

Zhang and

Zhan , Fuzzy soft β-covering based fuzzy rough sets and corresponding decision-making applications, International Journal of Machine Learning and Cybernetics, (2018), pp. 1–16.

38.

Zhang ,

Zhan and

J.C.R.

Alcantud , Novel classes of fuzzy soft β-coverings-based fuzzy rough sets with applications to multi-criteria fuzzy group decision making, Soft Computing (2018), 1–25.

39.

Zhang ,

Guo and

Martínez , Managing multi-granular linguistic distribution assessments in large-scale multiattribute group decision making, IEEE Transactions on Systems, Man, and Cybernetics: Systems 47(11) (2017), 3063–3076.

40.

Zou and

Xiao , Data analysis approaches of soft sets under incomplete information, Knowledge-Based Systems 21(8) (2008), 941–945.

An improved algorithm for normal parameter reduction of soft set

Abstract

Keywords

1. Introduction

2. Preliminaries

Table 1 Tabular form of (F, E) given in Example 2.1 U e 1 e 2 e 3 e 4 e 5 e 6 e 7 e 8 e 9 e 10 f (.) u 1 1 0 0 0 1 1 1 0 1 0 5 u 2 1 0 1 0 1 0 0 1 1 0 5 u 3 0 1 1 1 0 1 0 1 1 1 7 u 4 0 1 0 1 0 1 1 0 1 1 6 u 5 1 0 1 0 1 0 0 1 1 0 5 u 6 0 1 1 1 0 0 1 1 1 1 7

3.1. The normal parameter reduction algorithm (NPR)

Table 3 Tabular form of ( F , E ´ ) in Example 3.2 U e 1 e 2 e 3 e 4 e 5 e 6 e 7 e 8 e 10 f (.) u 1 1 0 0 0 1 1 1 0 0 4 u 2 1 0 1 0 1 0 0 1 0 4 u 3 0 1 1 1 0 1 0 1 1 6 u 4 0 1 0 1 0 1 1 0 1 5 u 5 1 0 1 0 1 0 0 1 0 4 u 6 0 1 1 1 0 0 1 1 1 6 S e i 3 3 4 3 3 3 3 4 3 29

Table 4 Tabular form of ( F , E ´ ) in Example 4.1 U e 1 e 2 e 3 e 6 e 7 f (.) u 1 1 0 0 1 1 3 u 2 1 0 1 0 0 2 u 3 0 1 1 1 0 3 u 4 0 1 0 1 1 3 u 5 1 0 1 0 0 2 u 6 0 1 1 0 1 3 S e j ´ 3 3 4 3 3 16

5.1. The proposed technique

6. Comparison results

6.1.1. Estimating the candidate parameter reduction set

6.1.2. Filtering the candidate parameter reduction set

6.2. Results and discussion

7. Application in decision making problem

The hiatal hernia disease problem

Conflict of interest

Footnotes

Acknowledgments

References

Table 1
Tabular form of (F, E) given in Example 2.1

U e ₁ e ₂ e ₃ e ₄ e ₅ e ₆ e ₇ e ₈ e ₉ e ₁₀ f (.)

u ₁ 1 0 0 0 1 1 1 0 1 0 5

u ₂ 1 0 1 0 1 0 0 1 1 0 5

u ₃ 0 1 1 1 0 1 0 1 1 1 7

u ₄ 0 1 0 1 0 1 1 0 1 1 6

u ₅ 1 0 1 0 1 0 0 1 1 0 5

u ₆ 0 1 1 1 0 0 1 1 1 1 7

Table 4
Tabular form of $(F, \overset{´}{E})$ in Example 4.1

U e ₁ e ₂ e ₃ e ₆ e ₇ f (.)

u ₁ 1 0 0 1 1 3

u ₂ 1 0 1 0 0 2

u ₃ 0 1 1 1 0 3

u ₄ 0 1 0 1 1 3

u ₅ 1 0 1 0 0 2

u ₆ 0 1 1 0 1 3

$S_{e_{\overset{´}{j}}}$ 3 3 4 3 3 16