Search

Granular computing (GrC) is a methodology for reducing the complexity of problem solving and includes two basic aspects: granulation and granular-based computing. Strongly connected components (SCCs) are a significant subgraph structure in digraphs. In this paper, two new granulation strategies were devised to improve the efficiency of computing SCCs. Firstly, four SCC correlations between the vertices were found, which can be divided into two classes. Secondly, two granulation strategies were designed based on correlations between two classes of SCCs. Thirdly, according to the characteristics of the granulation results, the parallelization of computing SCCs was realized. Finally, a parallel algorithm based on granulation strategy for computing SCCs of simple digraphs named GPSCC was proposed. Experimental results show that GPSCC performs with higher computational efficiency than algorithms. [ABSTRACT FROM AUTHOR]

As one of the key topics in the development of neighborhood rough set, attribute reduction has attracted extensive attentions because of its practicability and interpretability for dimension reduction or feature selection. Although the random sampling strategy has been introduced in attribute reduction to avoid overfitting, uncontrollable sampling may still affect the efficiency of search reduct. By utilizing inherent characteristics of each label, Multi-label learning with Label specIfic FeaTures (Lift) algorithm can improve the performance of mathematical modeling. Therefore, here, it is attempted to use Lift algorithm to guide the sampling for reduce the uncontrollability of sampling. In this paper, an attribute reduction algorithm based on Lift and random sampling called ARLRS is proposed, which aims to improve the efficiency of searching reduct. Firstly, Lift algorithm is used to choose the samples from the dataset as the members of the first group, then the reduct of the first group is calculated. Secondly, random sampling strategy is used to divide the rest of samples into groups which have symmetry structure. Finally, the reducts are calculated group-by-group, which is guided by the maintenance of the reducts' classification performance. Comparing with other 5 attribute reduction strategies based on rough set theory over 17 University of California Irvine (UCI) datasets, experimental results show that: (1) ARLRS algorithm can significantly reduce the time consumption of searching reduct; (2) the reduct derived from ARLRS algorithm can provide satisfying performance in classification tasks. [ABSTRACT FROM AUTHOR]

Symmetry is one of the most important aesthetic criteria on graph drawing. It is quite necessary to measure the extent to which the drawings can be considered symmetric. For this purpose, a symmetric metric based on vertex coordinate calculation is proposed in this paper. It is proven theoretically and experimentally that the proposed metric is robust to contraction, expansion, and rotation of drawings. This robustness conforms to human perception of symmetry. Star-subgraphs and cycles are two common structures in digraphs. Both of them have inherent symmetry which should be displayed in drawings. For this purpose, a force-directed algorithm named FDS is proposed which can draw star-subgraphs and cycles as symmetrically as possible. FDS algorithm draws cycles as circles whose positions are fixed to provide a scaffolding for overall layout, renders non-leaf vertices by a standard force-directed layout, and places leaf vertices on concentric circles via a deterministic strategy. A series of experiments are carried out to test FDS algorithm. The results show that FDS algorithm draws digraphs more symmetrically than the existing state-of-the-art algorithms and performs efficiency comparable to O(nlog⁡n) YFHu algorithm. [ABSTRACT FROM AUTHOR]

As an extension of Pawlak’s rough sets, rough fuzzy sets are proposed to deal with fuzzy target concept. As we know, the uncertainty of Pawlak’s rough sets is rooted in the objects contained in the boundary region, while the uncertainty of rough fuzzy sets comes from three regions (positive region, boundary region, and negative region). In addition, in the view of traditional uncertainty measures, the two rough approximation spaces with the same uncertainty are not necessarily equivalent, and they cannot be distinguished. In this paper, firstly, a fuzziness-based uncertainty measure is proposed. Meanwhile, the essence of the uncertainty for rough fuzzy sets and its three regions in a hierarchical granular structure is revealed. Then, from the perspective of fuzzy distance, we introduce a modified uncertainty measure based on the fuzziness-based uncertainty measure and present that our method not only is strictly monotonic with finer approximation spaces, but also can distinguish the two rough approximation spaces with the same uncertainty. Finally, a case study is introduced to demonstrate that the modified uncertainty measure is more suitable for evaluating the significance of attributes. These works are useful for further study on rough sets theory and promote the development of uncertain artificial intelligence. [ABSTRACT FROM AUTHOR]

Rough sets theory is not good at discovering knowledge from digraphs which is a kind of relational data. In order to solve this problem, we introduce binary relations derived from simple digraphs and propose a new concept of k -step R -related set in the framework of generalized rough sets theory. In addition, we first investigate the relationships between generalized rough sets theory and graph theory on the basis of mutual representation between binary relations and digraphs. The relationships established in this work make it possible to use generalized rough sets theory to find strongly connected components of simple directed graphs, which previously can be solved only by graph algorithms. An algorithm is correspondingly developed based on the above works, especially k -step R -related set. A series of experiments are carried out to test the proposed algorithm. The results show that our algorithm provides comparable performance to the classical Tarjan algorithm. In addition, the proposed algorithm can be implemented in parallel. And its parallel performance is comparable to existing state-of-the-art parallel algorithms. [ABSTRACT FROM AUTHOR]

Attribute reduction is a core technique in the rough set domain and an important step in data preprocessing. Researchers have proposed numerous innovative methods to enhance the capability of attribute reduction, such as the emergence of multi-granularity rough set models, which can effectively process distributed and multi-granularity data. However, these innovative methods still have numerous shortcomings, such as addressing complex constraints and conducting multi-angle effectiveness evaluations. Based on the multi-granularity model, this study proposes a new method of attribute reduction, namely using multi-granularity neighborhood information gain ratio as the measurement criterion. This method combines both supervised and unsupervised perspectives, and by integrating multi-granularity technology with neighborhood rough set theory, constructs a model that can adapt to multi-level data features. This novel method stands out by addressing complex constraints and facilitating multi-perspective effectiveness evaluations. It has several advantages: (1) it combines supervised and unsupervised learning methods, allowing for nuanced data interpretation and enhanced attribute selection; (2) by incorporating multi-granularity structures, the algorithm can analyze data at various levels of granularity. This allows for a more detailed understanding of data characteristics at each level, which can be crucial for complex datasets; and (3) by using neighborhood relations instead of indiscernibility relations, the method effectively handles uncertain and fuzzy data, making it suitable for real-world datasets that often contain imprecise or incomplete information. It not only selects the optimal granularity level or attribute set based on specific requirements, but also demonstrates its versatility and robustness through extensive experiments on 15 UCI datasets. Comparative analyses against six established attribute reduction algorithms confirms the superior reliability and consistency of our proposed method. This research not only enhances the understanding of attribute reduction mechanisms, but also sets a new benchmark for future explorations in the field. [ABSTRACT FROM AUTHOR]

As a key part of data preprocessing, namely attribute reduction, is effectively applied in the rough set field. The purpose of attribute reduction is to prevent too many attributes from affecting classifier operations and reduce the dimensionality of data space. Presently, in order to further improve the simplification performance of attribute reduction, numerous researchers have proposed a variety of methods. However, given the current findings, the challenges are: to reasonably compress the search space of candidate attributes; to fulfill multi-perspective evaluation; and to actualize attribute reduction based on guidance. In view of this, forward greedy searching to κ -reduct based on granular ball is proposed, which has the following advantages: (1) forming symmetrical granular balls to actualize the grouping of the universe; (2) continuously merging small universes to provide guidance for subsequent calculations; and (3) combining supervised and unsupervised perspectives to enrich the viewpoint of attribute evaluation and better improve the capability of attribute reduction. Finally, based on three classifiers, 16 UCI datasets are used to compare our proposed method with six advanced algorithms about attribute reduction and an algorithm without applying any attribute reduction algorithms. The experimental results indicate that our method can not only ensure the result of reduction has considerable performance in the classification test, but also improve the stability of attribute reduction to a certain degree. [ABSTRACT FROM AUTHOR]

Label-specific feature learning has become a hot topic as it induces classification models by accounting for the underlying features of each label. Compared with single-label annotations, multi-label annotations can describe samples from more comprehensive perspectives. It is generally believed that the compelling classification features of a data set often exist in the aggregation of label distribution. In this in-depth study of a multi-label data set, we find that the distance between all samples and the sample center is a Gaussian distribution, which means that the label distribution has the tendency to cluster from the center and spread to the surroundings. Accordingly, the double annulus field based on this distribution trend, named DEPT for double annulusfield and label-specific features for multi-label classification, is proposed in this paper. The double annulus field emphasizes that samples of a specific size can reflect some unique features of the data set. Through intra-annulus clustering for each layer of annuluses, the distinctive feature space of these labels is captured and formed. Then, the final classification model is obtained by training the feature space. Contrastive experiments on 10 benchmark multi-label data sets verify the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In the era of big data for exploring attribute reduction/rough set-based feature selection related problems, to design efficient strategies for deriving reducts and then reduce the dimensions of data, two fundamental perspectives of Granular Computing may be taken into account: breaking up the whole into pieces and gathering parts into a whole. From this point of view, a novel strategy named label-specific guidance is introduced into the process of searching reduct. Given a formal description of attribute reduction, by considering the corresponding constraint, we divide it into several label-specific based constraints. Consequently, a sequence of these label-specific based constraints can be obtained, it follows that the reduct related to the previous label-specific based constraint may have guidance on the computation of that related to the subsequent label-specific based constraint. The thinking of this label-specific guidance runs through the whole process of searching reduct until the reduct over the whole universe is derived. Compared with five state-of-the-art algorithms over 20 data sets, the experimental results demonstrate that our proposed acceleration strategy can not only significantly accelerate the process of searching reduct but also offer justifiable performance in the task of classification. This study suggests a new trend concerning the problem of quickly deriving reduct. [ABSTRACT FROM AUTHOR]

Attribute reduction is a critical topic in the field of rough set theory. Currently, to further enhance the stability of the derived reduct, various attribute selectors are designed based on the framework of ensemble selectors. Nevertheless, it must be pointed out that some limitations are concealed in these selectors: (1) rely heavily on the distribution of samples; (2) rely heavily on the optimal attribute. To generate the reduct with higher stability, a novel beam-influenced selector (BIS) is designed based on the strategies of random partition and beam. The scientific novelty of our selector can be divided into two aspects: (1) randomly partition samples without considering the distribution of samples; (2) beam-based selections of features can save the selector from the dependency of the optimal attribute. Comprehensive experiments using 16 UCI data sets show the following: (1) the stability of the derived reducts may be significantly enhanced by using our selector; (2) the reducts generated based on the proposed selector can provide competent performance in classification tasks. [ABSTRACT FROM AUTHOR]

In the context of recent advances in Graph Convolutional Networks (GCNs) for semi-supervised learning, a significant highlight is the potential of Graph Contrastive Learning (GCL). Many established GCL-based GCNs focus on developing various augmentation strategies and learning architectures to efficiently generate and learn self-supervised information. Unfortunately, the node representation fusion is often neglected in the process of learning representation. To address the issue, we propose a novel end-to-end GCL framework called Perturbation-augmented Graph Convolutional Networks (PA-GCN), by simultaneously considering supervised information and self-supervised information of graphs to fuse node representations from the input graph and the augmentation graphs. Essentially, PA-GCN develops a perturbation augmentation strategy based on original graph relations, serving as a basis to generate diverse node information and self-supervised information. Additionally, PA-GCN introduces three main components: A encoder for node representation learning; an attention mechanism for effective node representation fusion; and a discriminator capable of learning self-supervised information from unlabeled nodes, thereby enabling joint learning of supervised information, node representation fusion, and self-supervised information. We conduct experiments on five real world datasets to evaluate the performance of PA-GCN in semi-supervised node classification tasks. The experimental results demonstrate the strong adaptability of PA-GCN for base encoders and the superiority of PA-GCN over the most advanced methods. [ABSTRACT FROM AUTHOR]

Abstract As an extension of Pawlak's rough sets, rough fuzzy sets is proposed to deal with the target concept which is typically fuzzy or uncertain. It is worthwhile to introduce cost-sensitive learning into granular computing, as the granularity with the optimal cost can be selected. In the terms of decision making, test cost and decision cost are the most popular cost types. In the sequential three-way decisions (S3WD) models, the granularity is sensitive to the test cost. Meanwhile, the accuracy is sensitive to the decision cost. Selecting an optimal cost-sensitive granularity for problem solving is helpful for achieving optimal results at the lowest total cost in S3WD. However, it is difficult to evaluate test cost precisely and objectively in real-life applications, and existing works only focus on searching for the total cost as the objective function. In this paper, we firstly present a sequential three-way decisions model with rough fuzzy sets (S3WDRFS). Then, for S3WDRFS and its three regions, the changing rules of their decision cost are revealed in a hierarchical granular structure. By considering user requirements, we propose an optimization mechanism to achieve the optimal cost-sensitive granularity selection based on S3WDRFS model. Finally, the experimental results demonstrate that exemplary optimal granularities can be obtained for high quality decision-making under certain constraints. [ABSTRACT FROM AUTHOR]