# Fuzzy Covering-Based Three-Way Clustering

Authors: Dandan Yang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

This paper investigates the three-way clustering involving fuzzy covering, thresholds acquisition, and boundary region processing. First of all, a valid fuzzy covering of the universe is constructed on the basis of an appropriate fuzzy similarity relation, which helps capture the structural information and the internal connections of the dataset from the global perspective. Due to the advantages of valid fuzzy covering, we explore the valid fuzzy covering instead of the raw dataset for RFCM algorithm-based three-way clustering. Subsequently, from the perspective of semantic interpretation of balancing the uncertainty changes in fuzzy sets, a method of partition thresholds acquisition combining linear and nonlinear fuzzy entropy theory is proposed. Furthermore, boundary regions in three-way clustering correspond to the abstaining decisions and generate uncertain rules. In order to improve the classification accuracy, thek-nearest neighbor (kNN) algorithm is utilized to reduce the objects in the boundary regions. The experimental results show that the performance of the proposed three-way clustering based on fuzzy covering and kNN-FRFCM algorithm is better than the compared algorithms in most cases.


---

## Body

## 1. Introduction

Three-way decisions (3WD) proposed by Yao [1, 2] is a hot topic in various fields in recent years. Since it was put forward, the idea of tripartition has attracted many scholars to do research. Especially recently, great progress has been made in the theoretical research and model building of three-way decisions based on rough sets. For example, Liang and Liu et al. [3–6] proposed fuzzy three-way decision models and stochastic three-way decision models to deal with real-valued or linguistic-valued decision-making problems. Qian et al. [7] established multigranulation decision-theoretic rough set model based on granular computing theory. Hu [8, 9] introduced the concept of three-way decision space and established a three-way decision model based on partially ordered sets. Qi et al. [10] investigated the 3WD model in the framework of lattice theory. Li et al. [11] have constructed a cost-sensitive sequential three-way decision model to simulate the decision-making process from coarse granularity (high cost) to fine granularity (low cost) and please refer [12–14] for further generalizations and applications of this model. Yao et al. [15] construct an optimization-based framework for three-way approximations of fuzzy sets. In the meanwhile, for dynamic objects and attributes, some algorithms and incremental 3WD models are designed for classification of dynamic data [16, 17]. From the viewpoint of application, three-way decisions have been widely used in research fields such as pattern recognition [18, 19], artificial intelligence [20–22], engineering, managements [23], and social communities [24].Based on the above backgrounds and work in three-way decisions, a novel method for three-way clustering based on fuzzy covering is discussed. First, the fuzzy covering of the dataset according to the reasonable fuzzy similarity relation is constructed. The fuzzy covering of the universe requires that the more similar the objects in the universe are, the more similar the corresponding fuzzy classes are. The fuzzy covering established in this way can better reflect the intrinsic relationship between objects in the universe. Therefore, clustering results will have more accuracy with valid fuzzy covering. One of the inevitable problems of clustering is threshold calculation. As is well known, for most of the three-way decision models mentioned above, we first need to obtain the pair of partition thresholdsα and β. Different thresholds lead to different decision results. The appropriate partition thresholds make the decision more accurate, whereas the inappropriate thresholds distort the decision. Traditionally, the partition thresholds are usually selected according to the experts experience in advance [25–27]. According to the loss function, Yao et al. [1] proposed a method to determine the thresholds by Bayesian risk decision theory. By using Shannon entropy as a measure of uncertainty, Deng et al. [28] present an information-theoretic approach to explain and calculate the thresholds. Zhou et al. [29] explore the shadowed set to automatically obtain the partition thresholds of the three-way decisions but cannot theoretically give a reasonable semantic explanation. To address this issue, inspired by the idea of balancing the uncertainty change of fuzzy sets, a threshold calculation method combining linear fuzzy entropy with nonlinear fuzzy entropy is proposed. This method provides a new scientific explanation for the generation of thresholds. And then, the boundary regions of three-way clustering are processed by the kNN algorithm to reduce uncertainty and improve decision accuracy.The structure of the rest of this paper is as follows:Section 2 briefly introduces the necessary notions of three-way decisions. Section 3 focuses on constructing the fuzzy covering of the raw dataset according to the fuzzy similarity relation and some necessary conditions and discusses its related properties. In Section 4, a novel rough fuzzy C-means (FRFCM) algorithm based on valid fuzzy covering is established. Then, we investigate the partition thresholds by combining the linear and nonlinear fuzzy entropy. Furthermore, the framework for processing the boundary region of three-way clustering using the kNN algorithm is introduced. In Section 5, the validity and practicability of the algorithm are evaluated by experiment. Concluding remarks are given in Section 6.


## 2. Preliminaries

The basic concepts on three-way decisions are briefly reviewed in this section.An information system is defined as a 4-tupleS=U,At=C∪D,V,f, where U=x1,x2,…,xn denotes a finite nonempty universe, C is a nonempty finite of condition attributes, D is a nonempty finite of decision attributes, and V=∪a∈AtVa, where Va is a domain of attribute a; f:U×C⟶V is an information function such that fx,a∈Va for every x∈U,a∈At. If Va is a membership function value, then the value of object x under attribute a can be expressed as μax∈0,1.The trisecting-and-acting framework of three-way decisions is an extension of binary decision in order to overcome some shortcomings of binary decision. The traditional binary decision model only has acceptance and rejection options, which can easily lead to errors when the information available is insufficient to make an accurate judgment. Sometimes, the cost of wrong decisions is very high. Therefore, deferment decision is necessary, which allows decision makers to collect more information and make more accurate judgment. This is a strategy that people often adopt in the decision-making process, and deferment decision is consistent with human cognition. A three-way decision model based on the evaluation function and a pair of thresholds is shown as follows.Definition 1.
(see [30]). Let U be a finite nonempty universe, v be an evaluation function, and α,β a pair of thresholds, 0≤β<α≤1, then the positive, negative, and boundary regions of any subset A⊆U are defined as follows:(1)POSα,βA=x∈UvAx≥α,NEGα,βA=x∈UvAx≤β,BNDα,βA=x∈Uβ<vAx<α.
Evaluation function is the key of decision. The result of decision-making is different with different evaluation functions. There are various evaluation functions that can be adopted. If a fuzzy membership functionμA is used as an evaluation function, then the induced three regions are defined by the following equations [31]:(2)POSα,βμA=x∈UμAx≥α,NEGα,βμA=x∈UμAx≤β,BNDα,βμA=x∈Uβ<μAx<α.
The three-valued approximations of a fuzzy set is described by Zadeh [32] as follows: (1) xbelongs toA, if μAx≥α; (2) x does not belong to A, if μAx≤β; (3) and x has an indeterminate status relative to A, if β<μAx<α. These three cases correspond to the three-way decisions of the above fuzzy set. When α=1 and β=0, we obtain the qualitative three-way decisions of a fuzzy set. However, the qualitative decision model of fuzzy set is very restrictive, and we generally do not select these two thresholds.


## 3. Fuzzy Covering and Its Validity

The focus of this section is on the method of constructing valid fuzzy covering of raw data and discusses the properties of the fuzzy covering. Let us first recall some concepts that help us to better understand fuzzy covering.Definition 2.
(see [33, 34]). Let U=x1,x2,…,xN be a finite universe and FU be the fuzzy power set of U. For each γ∈0,1, we call P=P1,P2,…,Pm with Pi∈FUi=1,2,…,m, a fuzzy γ-covering of U, if ∪i=1mPix≥γ for each x∈U. U,P is called a fuzzy γ-covering approximation space. If ∑i=1mPix≥1 for each x∈U, then P is called a fuzzy covering of U. U,P is called a fuzzy covering approximation space. ∑i=1mPix=1 for each x∈U, then P is called a fuzzy partition of U. We call U,P a fuzzy partition approximation space.Definition 3.
(see [35]). Let σ be a mapping σ:FU×FU⟶0,1. σA,B is called the degree of similarity between fuzzy sets A and B, if σA,B satisfies the following properties:(1)
σA,A=1,∀A∈FU(2)
σA,B = σB,A(3)
ifA⊆B⊆C, then σA,C≤σA,B∧σB,C
Some similarity measures are listed as follows:(3)σ1A,B=∑i=1NμAxi∧μBxi∑i=1NμAxi∨μBxi,σ2A,B=2∑i=1NμAxi∧μBxi∑i=1NμAxi+μBxi,σ3A,B=1−1N∑i=1NμAxi−μBxi.
The fuzzy set in this paper is constructed by fuzzy similarity relationR which satisfies the following properties. For any x,y∈U,(1)
0≤Rx,y≤1(2)
Rx,y=Ry,x
For a fuzzy similarity relationR∈FU×U, ∀xi∈U, and xiR∈FU, the membership of xj belonging to fuzzy set xiR is denoted as(4)xiRxj=Rxi,xj,xj∈U.
Obviously, ifRxi,xj=1, it means that xj certainly belongs to xiR. Conversely, if Rxi,xj=0, it indicates that xj certainly does not belong to xiR. xiR is also called a fuzzy similarity class associated with R on U. Therefore, the set of fuzzy similarity classes xiR:i=1,2,…,U constructed by relation R is a fuzzy covering of universe U.
In the following, we investigate the validity and related properties of the fuzzy covering of the raw dataset.Definition 4.
LetU=x1,x2,…,xN be a universe. R is the fuzzy similarity relation on U, and σ is the similarity relation on FU. P=x1,x2,…,xN is a fuzzy covering of U constructed by fuzzy similarity relation R. For any xi∈U, Mi=xjRσxi,xj,Rxi,xj≥φ,xj∈U,j≥i,φ∈0.5,1 is the set of similarity objects with xi. P is defined as a valid fuzzy covering of U with respect to θ, if the following condition holds:(5)IP=2⋅∑i=1NcardMiNN+1≥θ,where θ∈0.5,1.
It is easy to know that the value ofIP depends on σ and R and the choice of φ. φ is generally assigned no less than 0.8. The closer the IP is to 1, the more relation the R expresses the structure of sample space. If θ is less than 0.5, the fuzzy covering of the universe is invalid. The fuzzy covering P=x1,x2,…,xN satisfies that similar objects in U have corresponding similar fuzzy classes, so the fuzzy covering P more fully reflects the original distribution of objects in U.Proposition 1.
Letφ1<φ2, then Iφ1C≥Iφ2C.Proof.
It can be easily verified by the definition.Remark 1.
LetP1 and P2 be two valid fuzzy coverings of U with respect to the same θ. We choose fuzzy covering with a larger validity index I. as research data.


## 4. Three-Way Clustering

### 4.1. Rough Fuzzy C-Means Algorithm Based on Fuzzy Covering

In this section, we discuss the rough fuzzy C-means algorithm with fuzzy covering. The reason for clustering with fuzzy covering is that each fuzzy similarity class can reflect the relationship with the whole dataset, avoiding the disadvantage of excessive loss of clustering information with raw data.The combination of fuzzy set and rough set provides an important direction for uncertain reasoning. Lingras [36] developed rough C-means (RCM) by combining the C-means clustering algorithm with rough set theory. The new clustering center is only related to the positive region and the boundary region, unlike fuzzy C-means (FCM) [37], which is related to all objects. Since there is no membership involved, rough C-means (RCM) cannot effectively deal with the uncertainty caused by overlapping boundaries. In such circumstances, Mitra et al. [25] proposed a rough fuzzy C-means (RFCM) algorithm in which it combines the advantages of both fuzzy set and rough set into the framework of the C-means clustering algorithm. When dividing objects into approximation regions, replacing the absolute distance with a fuzzy membership is the innovation of the rough fuzzy C-means. This adjustment enhances the robustness of the clustering to deal with overlapping situations. Maji et al. [26] modified the calculation of the new clustering center in the RFCM model by assuming that the objects in the lower approximation have definite weights and the objects in the boundary have fuzzy weights. In what follows, we discuss the rough fuzzy C-means of fuzzy covering (FRFCM) algorithm, which is an RFCM algorithm based on fuzzy covering of the universe.SupposeSA=x1,x2,…,xNT is a valid fuzzy covering of U=x1,x2,…,xN. The cluster centers are denoted as V=v1,v2,…,vC⊂ℜN. In the FRFCM algorithm, SA is divided into C clusters Q1,Q2,…,QC. The membership of xj to the cluster i is(6)μij=1∑k=1Cdij/dkj2/m−1,where dij is the distance between xj and vi, μij∈0,1, and ∑i=1Cμij=1. The parameter m is the fuzzifier greater than 1.A two-category dataset is taken to explain the influence of different parametersm on classification. The membership degree of each object belonging to each cluster can be considered as a function which is related to relative distances and the fuzzifier parameter. Then, formula (6) translates to the following form:(7)μa,m=11+a/1−a2/m−1,a∈0,1,0,a=1,where a denotes the relative distance of an object with respect to one of the clusters.The uncertainty caused by different fuzzifier parameterm can be illustrated in Figure 1.Figure 1
The approximate regions with different values ofm.It is easily to obtain that if the value ofm tends to 1, the memberships are most crisp, as well as the uncertainty of the system is reduced which is suitable for three-way clustering. In this circumstance, only objects that are approximately the same distance from each cluster center are divided into boundary regions. In addition, the parameter m cannot be assigned with a very large value because as the value increases, the memberships of objects around the center of the cluster will be assigned to 1 and most objects are divided into boundary region which will increase the uncertainty of the system and the error rate of decision-making. Furthermore, the positive region of cluster may become empty.The center vectorsv1,v2,…,vC are updated as follows:(8)vi=wilAi+wibBi,ifR¯Qi≠∅∧RbQi≠∅,Bi,ifR¯Qi=∅∧RbQi≠∅,Ai,ifR¯Qi≠∅∧RbQi=∅,where Ai=∑xj∈R¯Qiμijmxj/∑xj∈R¯Qiμijm and Bi=∑xj∈RbQiμijmxj/∑xj∈RbQiμijm can be considered as the contributions to the center vi by the fuzzy lower region and fuzzy boundary region, respectively. RbQi=R¯Qi−R¯Qi denotes the boundary region of cluster Gi, where R¯Qi and R¯Qi are the lower and upper approximations of cluster Qi with respect to relation R, respectively. The weighted values wil and wib usually satisfy wil+wib=1 and wil>wib. In this paper, we take wil=cardR¯Qi/cardR¯Qi+cardRbQi and wib=cardRbQi/cardR¯Qi+cardRbQi.The approximation regions are determined by the FRFCM algorithm with the following principles: ifμpj−μqj≤δ, where p=minldvl,xj and q=minl≠pdvl,xj, then xj∈R¯Qpandxj∈R¯Qq, It also means xj∈R¯Qpandxj∈R¯Qq. In this case, xj cannot be divided into the positive region of any clusters. Otherwise, xj∈R¯Qp and xj∈R¯Qp. Due to the particularity structure of the fuzzy covering of U, the results of fuzzy covering clustering can well reflect the clustering results of the raw dataset through the above FRFCM algorithm.


### 4.2. Acquisition of Thresholds for Three-Way Clustering

In this section, we firstly review the shadowed set model for computing thresholds. Then, a novel method of calculating thresholds is proposed by combining the linear and nonlinear fuzzy entropy.The FRFCM algorithm is an important tool to deal with imprecise, incomplete, and inconsistent data. The thresholds in FRFCM which determines the formation of approximation regions should be carefully selected. The unreasonable thresholds may cause the partition of approximate regions to be distorted, and clustering centers may deviate from the expected locations. Therefore, we should compute the partition thresholds scientifically according to some principles.There are many methods to obtain the thresholds, and the most popular method is the shadowed set [38]. In fact, the shadowed set adopts the method of elevating and reducing membership degree, which divides the domain of fuzzy set into three regions. The corresponding membership function is as follows:(9)SAx=1,μAx≥α,0,μAx≤β,0,1,β<μAx<α,where μA is the membership function of fuzzy set A.In the following study, only discrete fuzzy systems are considered, and similar models and conclusions can be obtained for continuous fuzzy systems. According to shadowed sets theory, the following formula is proposed to calculate the minimumV value to obtain the optimal thresholds α and β:(10)V=∑μAx≤βμAxdx+∑μAx≥α1−μAxdx−cardx|β<μAx<α.However, the semantic interpretation of obtaining threshold pairs by using the above method is not very clear. Because the shadowed set model can not reasonably explain the relationship between the obtained shadowed set and the fuzziness of the raw fuzzy set, further research is needed. Various methods for measuring uncertainty are described in the literature [39]. Fuzzy entropy is an important tool to measure the uncertainty of fuzzy set and meets the following requirements.Definition 5.
(see [40]). Let A=xi,μAxi,xi∈U be a fuzzy set on the universe of discourse U=x1,x2,...,xN. The fuzzy entropy of fuzzy set A is the mapping E:FU⟶R+, which satisfies the following four conditions:(1)
EA=0 if A∈PU(2)
E1/2U=maxA∈FUEA(3)
∀A,B∈FU, if μB≥μA≥1/2 or μB≤μA≤1/2, then EA≥EB(4)
EAc=EA,∀A∈FU
It is easy to verify that, for anyxi∈U, μAxi=0 or μAxi=1, the value of corresponding entropy function is 0, then the fuzzy entropy of the fuzzy set equals 0; i.e., the uncertainty of the fuzzy set is the minimum. When μAxi=1/2 holds for any xi∈U, the value of corresponding entropy function is 1, then the fuzzy set has maximum uncertainty. The commonly used linear and nonlinear fuzzy entropy functions are listed as follows [41–43]:(11)EA1x=1−2μAx−1,x∈U,EA2x=sinπμAx,x∈U,EA3x=2minμAx,1−μAx,x∈U,EA4x=−1log2μAxlogμAx+1−μAxlog1−μAx,x∈U.
With the above fuzzy entropy functions of fuzzy measure, the corresponding fuzzy entropy of the fuzzy setA can be easily obtained as follows:(12)EjA=∑x∈UEAjx,j=1,2,3,4.
The basic idea of calculating the thresholds by fuzzy entropy is to reduce the uncertainty of the membership of the objects which are the elevating or reducing operation in the shadowed set to 0, while the membership of objects corresponding to the middle part in the shadowed set is adjusted to the maximal uncertainty; i.e., the fuzzy degree increases to 1. In what follows, we propose a flexible fuzzy entropy method which combines the linear fuzzy entropy functionEA1xi and nonlinear fuzzy entropy function EA2xi to obtain the clustering thresholds. Then, the calculation model is as follows:(13)αopt,βopt=argminα,βλ∑xi∈UμAxi≥αμAxi≤βEA1xi−∑xi∈Uβ<μAxi<α1−EA1xi+1−λ∑xi∈UμAxi≥αμAxi≤βEA2xi−∑xi∈Uβ<μAxi<α1−EA2xi,where λ∈0,1 is a parameter adjusting the impacts of linear entropy and nonlinear entropy.
In equation (13), when λ=1, only linear fuzzy entropy function EA1xi is used to calculate the thresholds. If λ=0, only nonlinear fuzzy entropy function EA2xi is used to calculate the thresholds. The smaller the value of λ, the more the influence brought from the linear fuzzy entropy, and vice versa. In the subsequent experiments of this study, we assign λ=0.5.
Figure2 illustrates the increase and decrease in fuzzy degree of the fuzzy entropy function by taking the linear fuzzy entropy function EA1x, the nonlinear fuzzy entropy function EA2x, and the fuzzy entropy function EACx which is combined by EA1x and EA2x with equal weight as examples.
It can be seen from Figure2 that the curve of flexible fuzzy entropy function lies between the curve of linear and nonlinear entropy functions. The method of using flexible fuzzy entropy to obtain the thresholds can prevent the uncertainty of fuzzy set measured by linear or nonlinear fuzzy entropy from being too small or too large, which leads to the partition thresholds unreasonable.
Thresholds used in RFCM and its related algorithms are usually user-defined. However, the threshold calculated by the above model can not only be interpreted from the change in fuzzy degree of fuzzy set but also be adjusted and optimized automatically.
According toαopt and βopt, the positive, boundary, and negative regions of each cluster Qi can be expressed as(14)POSQi=xjμij≥αopt,BNDQi=xjβopt<μij<αopt,NEGQi=U−POSQi−BNDQi=xjμij≤βopt,where μij is the membership degree of the jth object belonging to the ith class.Figure 2
The operations of fuzzy entropy functionsEA1x, EA2x, and EACx.


### 4.3. Boundary Region Processing of Three-Way Clustering Based on kNN Algorithm

Following the above discussion on automatically selecting the optimal partition thresholds based on fuzzy entropy theory, this section will present the object processing in the boundary regions of three-way clustering.In the three-way clustering, the boundary region objects are rarely further processed.k-nearest neighbor (kNN) algorithm [44] is a well-known nonparametric classifier, which is considered as one of the simplest methods in data mining and pattern recognition. The principle of the kNN algorithm is to find k nearest neighbors of a query in dataset and then predicts the query with the major class in the k nearest neighbors. In this paper, the kNN algorithm will be utilized to process the objects in the boundary regions. If the object does not find a positive region, it is still classified to the boundary region. Therefore, the uncertainty of the boundary region decreases with the decrease in the number of objects in the boundary region, and reclassifying the objects in the boundary region can improve the accuracy of the three-way clustering.The details of updating the boundary region with the kNN algorithm are as follows.Because the kNN algorithm mainly relies on limited adjacent objects for classification, it is more suitable than other methods for the overlap of class domain or the object set to be classified at the boundary region. Therefore, Algorithm1 can handle the uncertain arising from the boundary region. Of course, dealing with the boundary region with the k-nearest neighbor algorithm will add extra computing burden and may also face the risk of misclassification of objects.Algorithm 1: Processing the boundary regions of three-way clustering based on the kNN algorithm.
Input: a set of objects U=x1,x2,⋯,xN, the cluster centers V=v1,v2,…,vC, the positive region POS=∪i=1CPOSQi, boundary region BND=∪i=1CBNDQi, and the optimal value of k.Output: the updated positive region POSX and boundary region BNDXStep1: calculate the distance between xi and other objects, where xi∈BND;Step2: find the region where the k points with the smallest distance are located;Step3: nQi is the number of k objects in the positive region of class Qi, where i=1,2,⋯C. nQC+1 is the number of k objects in the boundary region, and nQ1+nQ2+⋯+nQC+nQC+1=k. If there is only one cluster Qj, such that nQj=maxi∈1,2,…,C+1nQi, then POSQj=POSQj∪xi and BND=BND−xi else xi∈BNDStep4: repeat Steps 1–3 until all boundary objects have been computed.In what follows, based on valid fuzzy covering, FRFCM and kNN algorithms, we proposed a three-way clustering algorithm, which is called the kNN-FRFCM algorithm, and it can be formed, as shown in Algorithm2.Algorithm 2: kNN-FRFCM algorithm-based three-way clustering.
Input: the valid fuzzy covering of universe xii=1,2,…,N, the cluster centers vii=1,2,…,C, and the initial fuzzy membership degrees μiji=1,2,…,C,j=1,2,…,N;Output: the positive, boundary, and negative regions of each cluster, respectively.Step1: compute the optimal partition thresholds αiopt and βiopt for each cluster Qi using formula (13);Step2: according to formula (14), determine the positive region POSQi, boundary region BNDQi, and NEGQi for each cluster Qi by αiopt, βiopt, and fuzzy partition matrix μijC×N;Step3: update each clustering region by Algorithm 1;Step4: update the membership partition matrix μijN×N by formula (6);Step5: update the cluster center vii=1,2,…,C with formula (8);Step6: repeat Step 1 to Step 5 until convergence is reached;Step7: the results of fuzzy covering clustering are replaced by the corresponding objects in the universe.Thus, according to Algorithm2, we obtain three-way clustering results of the original dataset by using the valid fuzzy covering.


## 4.1. Rough Fuzzy C-Means Algorithm Based on Fuzzy Covering

In this section, we discuss the rough fuzzy C-means algorithm with fuzzy covering. The reason for clustering with fuzzy covering is that each fuzzy similarity class can reflect the relationship with the whole dataset, avoiding the disadvantage of excessive loss of clustering information with raw data.The combination of fuzzy set and rough set provides an important direction for uncertain reasoning. Lingras [36] developed rough C-means (RCM) by combining the C-means clustering algorithm with rough set theory. The new clustering center is only related to the positive region and the boundary region, unlike fuzzy C-means (FCM) [37], which is related to all objects. Since there is no membership involved, rough C-means (RCM) cannot effectively deal with the uncertainty caused by overlapping boundaries. In such circumstances, Mitra et al. [25] proposed a rough fuzzy C-means (RFCM) algorithm in which it combines the advantages of both fuzzy set and rough set into the framework of the C-means clustering algorithm. When dividing objects into approximation regions, replacing the absolute distance with a fuzzy membership is the innovation of the rough fuzzy C-means. This adjustment enhances the robustness of the clustering to deal with overlapping situations. Maji et al. [26] modified the calculation of the new clustering center in the RFCM model by assuming that the objects in the lower approximation have definite weights and the objects in the boundary have fuzzy weights. In what follows, we discuss the rough fuzzy C-means of fuzzy covering (FRFCM) algorithm, which is an RFCM algorithm based on fuzzy covering of the universe.SupposeSA=x1,x2,…,xNT is a valid fuzzy covering of U=x1,x2,…,xN. The cluster centers are denoted as V=v1,v2,…,vC⊂ℜN. In the FRFCM algorithm, SA is divided into C clusters Q1,Q2,…,QC. The membership of xj to the cluster i is(6)μij=1∑k=1Cdij/dkj2/m−1,where dij is the distance between xj and vi, μij∈0,1, and ∑i=1Cμij=1. The parameter m is the fuzzifier greater than 1.A two-category dataset is taken to explain the influence of different parametersm on classification. The membership degree of each object belonging to each cluster can be considered as a function which is related to relative distances and the fuzzifier parameter. Then, formula (6) translates to the following form:(7)μa,m=11+a/1−a2/m−1,a∈0,1,0,a=1,where a denotes the relative distance of an object with respect to one of the clusters.The uncertainty caused by different fuzzifier parameterm can be illustrated in Figure 1.Figure 1
The approximate regions with different values ofm.It is easily to obtain that if the value ofm tends to 1, the memberships are most crisp, as well as the uncertainty of the system is reduced which is suitable for three-way clustering. In this circumstance, only objects that are approximately the same distance from each cluster center are divided into boundary regions. In addition, the parameter m cannot be assigned with a very large value because as the value increases, the memberships of objects around the center of the cluster will be assigned to 1 and most objects are divided into boundary region which will increase the uncertainty of the system and the error rate of decision-making. Furthermore, the positive region of cluster may become empty.The center vectorsv1,v2,…,vC are updated as follows:(8)vi=wilAi+wibBi,ifR¯Qi≠∅∧RbQi≠∅,Bi,ifR¯Qi=∅∧RbQi≠∅,Ai,ifR¯Qi≠∅∧RbQi=∅,where Ai=∑xj∈R¯Qiμijmxj/∑xj∈R¯Qiμijm and Bi=∑xj∈RbQiμijmxj/∑xj∈RbQiμijm can be considered as the contributions to the center vi by the fuzzy lower region and fuzzy boundary region, respectively. RbQi=R¯Qi−R¯Qi denotes the boundary region of cluster Gi, where R¯Qi and R¯Qi are the lower and upper approximations of cluster Qi with respect to relation R, respectively. The weighted values wil and wib usually satisfy wil+wib=1 and wil>wib. In this paper, we take wil=cardR¯Qi/cardR¯Qi+cardRbQi and wib=cardRbQi/cardR¯Qi+cardRbQi.The approximation regions are determined by the FRFCM algorithm with the following principles: ifμpj−μqj≤δ, where p=minldvl,xj and q=minl≠pdvl,xj, then xj∈R¯Qpandxj∈R¯Qq, It also means xj∈R¯Qpandxj∈R¯Qq. In this case, xj cannot be divided into the positive region of any clusters. Otherwise, xj∈R¯Qp and xj∈R¯Qp. Due to the particularity structure of the fuzzy covering of U, the results of fuzzy covering clustering can well reflect the clustering results of the raw dataset through the above FRFCM algorithm.


## 4.2. Acquisition of Thresholds for Three-Way Clustering

In this section, we firstly review the shadowed set model for computing thresholds. Then, a novel method of calculating thresholds is proposed by combining the linear and nonlinear fuzzy entropy.The FRFCM algorithm is an important tool to deal with imprecise, incomplete, and inconsistent data. The thresholds in FRFCM which determines the formation of approximation regions should be carefully selected. The unreasonable thresholds may cause the partition of approximate regions to be distorted, and clustering centers may deviate from the expected locations. Therefore, we should compute the partition thresholds scientifically according to some principles.There are many methods to obtain the thresholds, and the most popular method is the shadowed set [38]. In fact, the shadowed set adopts the method of elevating and reducing membership degree, which divides the domain of fuzzy set into three regions. The corresponding membership function is as follows:(9)SAx=1,μAx≥α,0,μAx≤β,0,1,β<μAx<α,where μA is the membership function of fuzzy set A.In the following study, only discrete fuzzy systems are considered, and similar models and conclusions can be obtained for continuous fuzzy systems. According to shadowed sets theory, the following formula is proposed to calculate the minimumV value to obtain the optimal thresholds α and β:(10)V=∑μAx≤βμAxdx+∑μAx≥α1−μAxdx−cardx|β<μAx<α.However, the semantic interpretation of obtaining threshold pairs by using the above method is not very clear. Because the shadowed set model can not reasonably explain the relationship between the obtained shadowed set and the fuzziness of the raw fuzzy set, further research is needed. Various methods for measuring uncertainty are described in the literature [39]. Fuzzy entropy is an important tool to measure the uncertainty of fuzzy set and meets the following requirements.Definition 5.
(see [40]). Let A=xi,μAxi,xi∈U be a fuzzy set on the universe of discourse U=x1,x2,...,xN. The fuzzy entropy of fuzzy set A is the mapping E:FU⟶R+, which satisfies the following four conditions:(1)
EA=0 if A∈PU(2)
E1/2U=maxA∈FUEA(3)
∀A,B∈FU, if μB≥μA≥1/2 or μB≤μA≤1/2, then EA≥EB(4)
EAc=EA,∀A∈FU
It is easy to verify that, for anyxi∈U, μAxi=0 or μAxi=1, the value of corresponding entropy function is 0, then the fuzzy entropy of the fuzzy set equals 0; i.e., the uncertainty of the fuzzy set is the minimum. When μAxi=1/2 holds for any xi∈U, the value of corresponding entropy function is 1, then the fuzzy set has maximum uncertainty. The commonly used linear and nonlinear fuzzy entropy functions are listed as follows [41–43]:(11)EA1x=1−2μAx−1,x∈U,EA2x=sinπμAx,x∈U,EA3x=2minμAx,1−μAx,x∈U,EA4x=−1log2μAxlogμAx+1−μAxlog1−μAx,x∈U.
With the above fuzzy entropy functions of fuzzy measure, the corresponding fuzzy entropy of the fuzzy setA can be easily obtained as follows:(12)EjA=∑x∈UEAjx,j=1,2,3,4.
The basic idea of calculating the thresholds by fuzzy entropy is to reduce the uncertainty of the membership of the objects which are the elevating or reducing operation in the shadowed set to 0, while the membership of objects corresponding to the middle part in the shadowed set is adjusted to the maximal uncertainty; i.e., the fuzzy degree increases to 1. In what follows, we propose a flexible fuzzy entropy method which combines the linear fuzzy entropy functionEA1xi and nonlinear fuzzy entropy function EA2xi to obtain the clustering thresholds. Then, the calculation model is as follows:(13)αopt,βopt=argminα,βλ∑xi∈UμAxi≥αμAxi≤βEA1xi−∑xi∈Uβ<μAxi<α1−EA1xi+1−λ∑xi∈UμAxi≥αμAxi≤βEA2xi−∑xi∈Uβ<μAxi<α1−EA2xi,where λ∈0,1 is a parameter adjusting the impacts of linear entropy and nonlinear entropy.
In equation (13), when λ=1, only linear fuzzy entropy function EA1xi is used to calculate the thresholds. If λ=0, only nonlinear fuzzy entropy function EA2xi is used to calculate the thresholds. The smaller the value of λ, the more the influence brought from the linear fuzzy entropy, and vice versa. In the subsequent experiments of this study, we assign λ=0.5.
Figure2 illustrates the increase and decrease in fuzzy degree of the fuzzy entropy function by taking the linear fuzzy entropy function EA1x, the nonlinear fuzzy entropy function EA2x, and the fuzzy entropy function EACx which is combined by EA1x and EA2x with equal weight as examples.
It can be seen from Figure2 that the curve of flexible fuzzy entropy function lies between the curve of linear and nonlinear entropy functions. The method of using flexible fuzzy entropy to obtain the thresholds can prevent the uncertainty of fuzzy set measured by linear or nonlinear fuzzy entropy from being too small or too large, which leads to the partition thresholds unreasonable.
Thresholds used in RFCM and its related algorithms are usually user-defined. However, the threshold calculated by the above model can not only be interpreted from the change in fuzzy degree of fuzzy set but also be adjusted and optimized automatically.
According toαopt and βopt, the positive, boundary, and negative regions of each cluster Qi can be expressed as(14)POSQi=xjμij≥αopt,BNDQi=xjβopt<μij<αopt,NEGQi=U−POSQi−BNDQi=xjμij≤βopt,where μij is the membership degree of the jth object belonging to the ith class.Figure 2
The operations of fuzzy entropy functionsEA1x, EA2x, and EACx.


## 4.3. Boundary Region Processing of Three-Way Clustering Based on kNN Algorithm

Following the above discussion on automatically selecting the optimal partition thresholds based on fuzzy entropy theory, this section will present the object processing in the boundary regions of three-way clustering.In the three-way clustering, the boundary region objects are rarely further processed.k-nearest neighbor (kNN) algorithm [44] is a well-known nonparametric classifier, which is considered as one of the simplest methods in data mining and pattern recognition. The principle of the kNN algorithm is to find k nearest neighbors of a query in dataset and then predicts the query with the major class in the k nearest neighbors. In this paper, the kNN algorithm will be utilized to process the objects in the boundary regions. If the object does not find a positive region, it is still classified to the boundary region. Therefore, the uncertainty of the boundary region decreases with the decrease in the number of objects in the boundary region, and reclassifying the objects in the boundary region can improve the accuracy of the three-way clustering.The details of updating the boundary region with the kNN algorithm are as follows.Because the kNN algorithm mainly relies on limited adjacent objects for classification, it is more suitable than other methods for the overlap of class domain or the object set to be classified at the boundary region. Therefore, Algorithm1 can handle the uncertain arising from the boundary region. Of course, dealing with the boundary region with the k-nearest neighbor algorithm will add extra computing burden and may also face the risk of misclassification of objects.Algorithm 1: Processing the boundary regions of three-way clustering based on the kNN algorithm.
Input: a set of objects U=x1,x2,⋯,xN, the cluster centers V=v1,v2,…,vC, the positive region POS=∪i=1CPOSQi, boundary region BND=∪i=1CBNDQi, and the optimal value of k.Output: the updated positive region POSX and boundary region BNDXStep1: calculate the distance between xi and other objects, where xi∈BND;Step2: find the region where the k points with the smallest distance are located;Step3: nQi is the number of k objects in the positive region of class Qi, where i=1,2,⋯C. nQC+1 is the number of k objects in the boundary region, and nQ1+nQ2+⋯+nQC+nQC+1=k. If there is only one cluster Qj, such that nQj=maxi∈1,2,…,C+1nQi, then POSQj=POSQj∪xi and BND=BND−xi else xi∈BNDStep4: repeat Steps 1–3 until all boundary objects have been computed.In what follows, based on valid fuzzy covering, FRFCM and kNN algorithms, we proposed a three-way clustering algorithm, which is called the kNN-FRFCM algorithm, and it can be formed, as shown in Algorithm2.Algorithm 2: kNN-FRFCM algorithm-based three-way clustering.
Input: the valid fuzzy covering of universe xii=1,2,…,N, the cluster centers vii=1,2,…,C, and the initial fuzzy membership degrees μiji=1,2,…,C,j=1,2,…,N;Output: the positive, boundary, and negative regions of each cluster, respectively.Step1: compute the optimal partition thresholds αiopt and βiopt for each cluster Qi using formula (13);Step2: according to formula (14), determine the positive region POSQi, boundary region BNDQi, and NEGQi for each cluster Qi by αiopt, βiopt, and fuzzy partition matrix μijC×N;Step3: update each clustering region by Algorithm 1;Step4: update the membership partition matrix μijN×N by formula (6);Step5: update the cluster center vii=1,2,…,C with formula (8);Step6: repeat Step 1 to Step 5 until convergence is reached;Step7: the results of fuzzy covering clustering are replaced by the corresponding objects in the universe.Thus, according to Algorithm2, we obtain three-way clustering results of the original dataset by using the valid fuzzy covering.


## 5. Experiment Analysis

Three-way clustering method based on fuzzy covering proposed in this paper is suitable for dataset with less data and dimension or data with similar amount of data and dimension. Otherwise, clustering with the fuzzy covering constructing by the data with a large amount of data and few dimension will cause the curse of dimensionality. In this paper, six datasets include Iris, Breast Cancer Wisconsin (Original) (BCWO) which eliminates the missing data, New thyroid, Seeds, Forest-type mapping (FTM), and CT from UCI Machine Learning Repository [45] for empirical study. On these datasets and their corresponding fuzzy covering, the results of clustering methods including FCM, RCM, RFCM, kNN-RCM, and kNN-RFCM are compared. In order to distinguish the results of the raw dataset and the fuzzy covering with the same algorithm, the clustering algorithms of the fuzzy covering are expressed as FFCM, FRCM, FRFCM, kNN-FRCM, and kNN-FRFCM, respectively. Details of the six datasets are described in Table 1.Table 1
Description of datasets.
No.Datasets# objects# attributes# classes1Iris150432BCWO6831023New thyroid215534Seeds210735FTM3262746CT221362The partition threshold related to RCM and its related algorithms is set as 0.001.φ and θ involved in fuzzy covering are set as 0.8 and 0.9, respectively. The value of k in the kNN algorithm is assigned as 7, and the evaluation indexes such as the normalized mutual information (NMI) [47], ACC [48], and rand index (RI) [49] are utilized to investigate the validity of the algorithm. Furthermore, the reasonable values of fuzzifier m involved in all comparison algorithms are greater than 1. m=1.03 and m=1.1 are selected, and the experimental comparison results are listed in Tables 2–7.Table 2
The comparative validity results (m = 1.03).
IrisSeedsNMIACCRINMIACCRIFCM0.74190.88670.87370.69490.89520.8744RCM0.73280.84000.88910.66700.88570.8666RFCM0.74190.88670.87370.66700.88570.8666kNN-RCM0.77770.90000.88590.67430.89050.8693kNN-RFCM0.74190.88670.87370.67430.89050.8693FFCM0.82260.93330.91950.67480.89520.8713FRCM0.77670.91330.91240.67480.89520.8713FRFCM0.81120.92670.91600.67770.89520.8742kNN-FRCM0.79190.92670.91240.67480.89520.8713kNN-FRFCM0.82260.93330.91950.68520.90000.8770Table 3
The comparative validity results (m = 1.03).
BCWONew thyroidNMIACCRINMIACCRIFCM0.74780.96050.92400.49450.86050.7908RCM0.73680.95020.92770.55850.87440.8203RFCM0.75850.96050.93120.59660.88840.8180kNN-RCM0.73680.95900.92770.55630.90230.7913kNN-RFCM0.75460.96190.92670.59660.88840.8180FFCM0.77590.96490.93210.62450.89770.8329FRCM0.77590.96490.93210.65010.90700.8531FRFCM0.77590.96490.93210.64480.90230.8523kNN-FRCM0.77590.96490.93210.65830.91160.8540kNN-FRFCM0.77590.96490.93210.65830.91160.8540Table 4
The comparative validity results (m = 1.03).
FTMCTNMIACCRINMIACCRIFCM0.72710.89390.90310.31180.81450.6964RCM0.74750.89900.90390.32960.82350.7080RFCM0.74110.89900.90180.33090.81900.7133kNN-RCM0.74750.89900.90390.32960.82350.7080kNN-RFCM0.74110.89900.90180.35500.83260.7234FFCM0.78230.90910.91530.43270.83710.7260FRCM0.78230.90910.91530.43270.83710.7260FRFCM0.76770.89900.91280.42670.82810.7234kNN-FRCM0.78230.90910.91530.43270.83710.7260kNN-FRFCM0.79060.91410.92000.42440.83260.7200Table 5
The comparative validity results (m = 1.1).
IrisSeedsNMIACCRINMIACCRIFCM0.75820.89330.87970.69490.89520.8744RCM0.73280.84000.88910.66700.88570.8666RFCM0.73600.87330.87140.67690.88570.8746kNN-RCM0.77770.90000.88590.67430.89050.8693kNN-RFCM0.75820.89330.87970.67280.89050.8740FFCM0.80240.92670.91240.66290.89050.8694FRCM0.77670.91330.91240.67480.89520.8713FRFCM0.79910.92000.91970.63450.87620.8643kNN-FRCM0.79190.92670.91240.67480.89520.8713kNN-FRFCM0.81360.93330.91970.64800.88570.8622Table 6
The comparative validity results (m = 1.1).
BCWONew thyroidNMIACCRINMIACCRIFCM0.74780.96050.92400.49450.86050.7908RCM0.73680.95020.92770.55850.87440.8203RFCM0.73910.95170.92680.60580.88840.8250kNN-RCM0.73680.95900.92770.55630.90230.7913kNN-RFCM0.73470.95750.91860.60580.88840.8250FFCM0.77590.96490.93210.62450.89770.8329FRCM0.77590.96490.93210.65010.90700.8531FRFCM0.77780.96490.93400.64480.90230.8523kNN-FRCM0.77590.96490.93210.65830.91160.8540kNN-FRFCM0.78890.96780.93760.65830.91160.8540Table 7
The comparative validity results (m = 1.1).
FTMCTNMIACCRINMIACCRIFCM0.72710.89390.90310.31180.81450.6964RCM0.74750.89900.90390.32960.82350.7080RFCM0.74110.89900.90180.30230.79190.6954kNN-RCM0.74750.89900.90390.32960.82350.7080kNN-RFCM0.74110.89900.90180.32740.81900.7055FFCM0.77460.90400.91070.43270.83710.7260FRCM0.78230.90910.91530.43270.83710.7260FRFCM0.76320.88380.91100.43380.81000.7374kNN-FRCM0.78230.90910.91530.43270.83710.7260kNN-FRFCM0.80740.91920.92460.47250.84160.7350From Tables2–7, it can be easily concluded that the selected fuzzy parameters have a significant impact on the performance of all comparison algorithms when dealing with the same dataset. Since the boundary region is the main cause of system uncertainty, thus, too large boundary regions are not required for three-way clustering and we need to pay attention to the uncertainty caused by the fuzzifier m in the implementation of the algorithms. Moreover, the clustering results show that kNN-FRFCM algorithm has better performance than the other algorithms in most of cases. This is mainly because it can reduce the uncertainty of the system by reprocessing the objects in the boundary regions. From the clustering results, we can also obtain that the results of clustering based on fuzzy covering are mostly better than the results of clustering with raw data. Therefore, the valid fuzzy covering can replace the raw dataset for clustering, and the clustering results are better than the raw dataset. The premise that fuzzy covering can replace the raw dataset for clustering is to select the appropriate fuzzy similarity relation [46].


## 6. Conclusions

In this paper, a valid fuzzy covering of the raw dataset is constructed by some principles. Because the similarity between fuzzy similarity classes in the valid fuzzy covering can be used to measure the similarity between objects in the raw dataset, each fuzzy similarity class reflects the connection with the whole dataset, so valid fuzzy covering instead of the raw data for clustering can improve the precision of clustering. From the perspective of semantic explanation of uncertainty change in fuzzy sets, we investigate the method of combining linear fuzzy entropy with nonlinear fuzzy entropy to obtain decision threshold pairs. The advantage of calculating thresholds method in this paper not only objectively obtains the classification thresholds based on the objects intrinsic relations but also the formula is simple and easy to understand, as well as the method of calculating the thresholds avoids the inappropriate subjective assignment. Additionally, the objects in the boundary region obtained by the FRFCM algorithm are reprocessed by the kNN algorithm to reduce the uncertainty of the system.Furthermore, we will continue to investigate the method of thresholds acquisition and the processing method of boundary region for three-way clustering following the idea of this paper. The three-way clustering in incremental information system is one of the future research directions too.



---

*Source: 2901210-2020-07-31.xml*