# Granular Description of Uncertain Data for Classification Rules in Three-Way Decision
## 2 Problem Formulation
### Data Classification via FCM  
(1) Unlabeled data  
To describe the uncertainty of classification, fuzzy classifiers are superior to certain classifiers. Therefore, we propose to apply FCM in classification. Since FCM is a typical unsupervised classification algorithm in pattern recognition, it is primarily used for unlabeled datasets. Assuming a dataset \(\{\mathbf{x}_{k}\}_{k}\)\(\in\)\(R^{n}\), \(k=1\), \(2\),..., \(N\)] with \(c\) categories, it can be partitioned by FCM via the membership matrix \(\mathbf{U}\) and \(c\) prototypes. The definition of the membership matrix is expressed in the following formula:  
\[\mathbf{U}=[u_{ik}]_{c\times N};u_{ik}=\frac{1}{\sum\limits_{j=1}^{c}\left(\frac{ \left\|\mathbf{x}_{k}-\mathbf{v}_{j}\right\|}{\left\|\mathbf{x}_{k}-\mathbf{v}_{j}\right\|} \right)^{2/(m-1)}} \tag{1}\]  
where \(\mathbf{x}_{k}\) is a point in the given dataset; \(\mathbf{v}_{i}\) is \(i\)th prototype; \(u_{ik}\) is the membership to the \(i\)th cluster; \(m\) is a parameter controlling the fuzzification degree. The \(i\)th prototype, namely the cluster center of the \(i\)th fuzzy cluster, can be calculated as seen below.  
\[\mathbf{v}_{i}=\sum\limits_{k=1}^{N}u_{ik}^{m}\mathbf{x}_{k}/\sum\limits_{k=1}^{N}u_{ ik}^{m} \tag{2}\]  
Combining Formulas (1) and (2), the objective function \(\sum\limits_{k=1}^{N}\sum\limits_{j=1}^{c}u_{ik}^{m}\left\|\mathbf{x}_{k}-\mathbf{v}_{ i}\right\|^{2}\) can be minimized via iterative optimization. It is seen that the values of \(u_{ik}\) satisfy \(0\leq u_{ik}\leq 1\) and \(\sum\limits_{i=1}^{c}u_{ik}=1\). Through the partition matrix \(\mathbf{U}\), unsupervised classification rules are constructed by memberships.  
(2) Labeled data  
For labeled datasets, their category labels are given in advance. By utilizing FCM clustering on data \(\{\mathbf{x}_{k}\}\), new labels are generated according to the above processes, which may be in conflict with given labels \(\{\mathbf{y}_{k}\}\). To copy labeled data with FCM, we modified its objective function as seen below.  
\[\sum\limits_{k=1}^{N}\sum\limits_{i=1}^{c}u_{ik}^{m}\left\|\mathbf{x}_{k}-\mathbf{v}_{ i}\right\|^{2}+C\sum\limits_{k=1}^{N}\sum\limits_{i=1}^{c}\left\|\mathbf{y}_{k}-\mathbf{y} _{\mathbf{v}_{i}}\right\|^{2} \tag{3}\]  
where \(\mathbf{y}_{k}\) is the actual label of data point \(\mathbf{x}_{k};\mathbf{y}_{ij}\) is the label of prototype \(\mathbf{v}_{i}\); \(C\) is a penalty factor. The new objective function has two parts. The first part is the general objective function for clustering unlabeled data in FCM. The second part is defined by only the label variable \(y_{k}\); its purpose is to group data points with the same labels into a cluster. The value of \(C\) is determined according to application requirements. For example, when \(C=0\), the formula (3) degenerates for the generic FCM clustering on unlabeled data. When \(C=1\), we could regard the process as FCM clustering on dataset \(\{(\mathbf{x}_{k},\mathbf{y}_{k})\}\)\(\in\)\(k=1\), \(2\),..., \(N\)]. When \(C\) is  
Figure 1: Diagram of uncertain data distribution in decision-making. (**a**) labeled data; (**b**) unlabeled data; (**c**) semi-labeled data.  
extremely large, the influence of the first part of (3) will be ignored, then (3) degenerates as the objective function for supervised classification. Usually, to apply FCM clustering more appropriately on labeled data, a suitable value of C is selected for considering the penalty in misclassification on the label variable.  
For semi-labeled datasets, there are two ways to apply FCM in classification. The first way is mentioned above, which processes the labeled part first and classifies the unlabeled part second. The second way is to apply the FCM algorithm for all data points by modifying the objective function. Similar as the FCM clustering on labeled data, we can also add the penalty on the labeled part as (3) to construct the objective function.