Search

As a leading graph clustering technique, spectral clustering is one of the most widely used clustering methods to capture complex clusters in data. Some additional prior information can help it to further reduce the difference between its clustering results and users' expectations. However, it is hard to get the prior information under unsupervised scene to guide the clustering process. To solve this problem, we propose a self-constrained spectral clustering algorithm. In this algorithm, we extend the objective function of spectral clustering by adding pairwise and label self-constrained terms to it. We provide the theoretical analysis to show the roles of the self-constrained terms and the extensibility of the proposed algorithm. Based on the new objective function, we build an optimization model for self-constrained spectral clustering so that we can simultaneously learn the clustering results and constraints. Furthermore, we propose an iterative method to solve the new optimization problem. Compared to other existing versions of spectral clustering algorithms, the new algorithm can discover a high-quality cluster structure of a data set without prior information. Extensive experiments on benchmark data sets illustrate the effectiveness of the proposed algorithm.

We consider the problem of reducing the false discovery rate in multiple high-dimensional interventional datasets under unknown targets. Traditional algorithms merged directly multiple causal graphs learned, which ignores the contradictions of different datasets, leading to lots of inconsistent directions of edges. For reducing the contradictory information, we propose a new algorithm, which first learns an interventional Markov equivalence class (I-MEC) before merging multiple graphs. It utilizes the full power of the constraints available in interventional data and combines ideas from local learning, intervention, and search-and-score techniques in a principled and effective way in different intervention experiments. Specifically, local learning on multiple datasets is used to build a causal skeleton. Perfect intervention destroys some possible triangles, leading to the identification of more possible V-structures. And then a theoretically correct I-MEC is learned. Search and scoring techniques based on the learned I-MEC further identify the remaining unoriented edges. Both theoretical analysis and experiments on benchmark Bayesian networks with the number of variables from 20 to 724 validate that the effectiveness of our algorithm in reducing the false discovery rate in high-dimensional interventional data.

How to get a good value estimation is one of the key problems in reinforcement learning (RL). Current off-policy methods, such as Maxmin Q-learning, TD3 and TADD, suffer from the underestimation problem when solving the overestimation problem. In this paper, we propose the Quasi-Median Operation, a novel way to mitigate the underestimation bias by selecting the quasi-median from multiple state-action values. Based on the quasi-median operation, we propose Quasi-Median Q-learning (QMQ) for the discrete action tasks and Quasi-Median Delayed Deep Deterministic Policy Gradient (QMD3) for the continuous action tasks. Theoretically, the underestimation bias of our method is improved while the estimation variance is significantly reduced compared to Maxmin Q-learning, TD3 and TADD. We conduct extensive experiments on the discrete and continuous action tasks, and results show that our method outperforms the state-of-the-art methods.

In this paper, we consider the problem of lacking theoretical foundation and low execution efficiency of the instance selection methods based on the k-nearest neighbour rule when processing large-scale data. We point out that the core idea of these methods can be explained from the perspective of Bayesian decision theory, that is, to find which instances are reducible, irreducible, and deleterious. Then, based on the percolation theory, we establish the relationship between these three types of instances and local homogeneous cluster (i.e., a set of instances with the same labels). Finally, we propose a method based on an accelerated k-means algorithm to construct local homogeneous clusters and remove the superfluous instances. The performance of our method is studied on extensive synthetic and benchmark data sets. Our proposed method can handle large-scale data more effectively than the state-of-the-art instance selection methods. All code and data results are available at https://github.com/CQQXY161120/Instance-Selection.

Graph neural networks (GNNs) have made great progress in graph-based semi-supervised learning (GSSL). However, most existing GNNs are confronted with the oversmoothing issue that limits their expressive ability. A key factor that leads to this problem is the excessive aggregation of information from other classes when updating the node representation. To alleviate this limitation, we propose an effective method called GUIded Dropout over Edges (GUIDE) for training deep GNNs. The core of the method is to reduce the influence of nodes from other classes by removing a certain number of inter-class edges. In GUIDE, we drop edges according to the edge strength, which is defined as the time an edge acts as a bridge along the shortest path between node pairs. We find that the stronger the edge strength, the more likely it is to be an inter-class edge. In this way, GUIDE can drop more inter-class edges and keep more intra-class edges. Therefore, nodes in the same community or class are more similar, whereas different classes are more separated in the embedded space. In addition, we perform some theoretical analysis of the proposed method, which explains why it is effective in alleviating the oversmoothing problem. To validate its rationality and effectiveness, we conduct experiments on six public benchmarks with different GNNs backbones. Experimental results demonstrate that GUIDE consistently outperforms state-of-the-art methods in both shallow and deep GNNs.

We consider the problem of distinguishing direct causes from direct effects of a target variable of interest from multiple manipulated datasets with unknown manipulated variables and nonidentical data distributions. Recent studies have shown that datasets attained from manipulated experiments (i.e., manipulated data) contain richer causal information than observational data for causal structure learning. Thus, in this article, we propose a new algorithm, which makes full use of the interventional properties of a causal model to discover the direct causes and direct effects of a target variable from multiple datasets with different manipulations. It is more suited to real-world cases and is also a challenge to be addressed in this article. First, we apply the backward framework to learn parents and children (PC) of a given target from multiple manipulated datasets. Second, we orient some edges connected to the target in advance through the assumption that the target variable is not manipulated and then orient the remaining undirected edges by finding invariant V-structures from multiple datasets. Third, we analyze the correctness of the proposed algorithm. To the best of our knowledge, the proposed algorithm is the first that can identify the local causal structure of a given target from multiple manipulated datasets with unknown manipulated variables. Experimental results on standard Bayesian networks validate the effectiveness of our algorithm.

Recently, graph convolutional networks (GCN) have made substantial progress in semi-supervised learning (SSL). However, established GCN-based methods have two major limitations. First, GCN-based methods are restricted by the oversmoothing issue that limits their ability to extract knowledge from distant but informative nodes. Second, most available GCN-based methods exploit only the feature information of unlabeled nodes, and the pseudo-labels of unlabeled nodes, which contain important information about the data distribution, are not fully utilized. To address these issues, we propose a novel end-to-end ensemble framework, which is named mixed-order graph convolutional networks (MOGCN). MOGCN consists of two modules. (1) It constructs multiple simple GCN learners with multi-order adjacency matrices, which can directly capture the high-order connectivity among the nodes to alleviate the problem of oversmoothing. (2) To efficiently combine the results from multiple GCN learners, MOGCN employs a novel ensemble module, in which the pseudo-labels of unlabeled nodes from various GCN learners are used to augment the diversity among the learners. We conduct experiments on three public benchmark datasets to evaluate the performance of MOGCN on semi-supervised node classification tasks. The experimental results demonstrate that MOGCN consistently outperforms state-of-the-art methods.

In most of the existing metric learning methods, the relation is fixed throughout the metric learning process. However, the fixed relation may be harmful to learn a good metric. The adversarial metric learning implements a dynamic update of the pairwise constraints. Inspired by the idea of dynamically updating constraints, we propose in this paper a metric learning model with clustering-based constraints (ML-CC), wherein the triple constraints of large margin are iteratively generated with the clusters of data points. The proposed method can overcome the shortage of the fixed triple constraints constructed under the Euclidian distance. The experimental results on synthetic and real datasets indicate that the performance of the ML-CC is superior to that of the existing state-of-the-art metric learning methods.

Logic reasoning is a significant ability of human intelligence and also an important task in artificial intelligence. The existing logic reasoning methods, quite often, need to design some reasoning patterns beforehand. This has led to an interesting question: can logic reasoning patterns be directly learned from given data? The problem is termed as a data concept logic. In this study, a learning logic task from images, called a LiLi task, first is proposed. This task is to learn and reason the logic relation from images, without presetting any reasoning patterns. As a preliminary exploration, we design six LiLi data sets (Bitwise And, Bitwise Or, Bitwise Xor, Addition, Subtraction and Multiplication), in which each image is embedded with a n-digit number. It is worth noting that a learning model beforehand does not know the meaning of the n-digit numbers embedded in images and the relation between the input images and the output image. In order to tackle the task, in this work we use many typical neural network models and produce fruitful results. However, these models have the poor performances on the difficult logic task. For furthermore addressing this task, a novel network framework called a divide and conquer model by adding some label information is designed, achieving a high testing accuracy.

Feature selection is an essential preprocessing requirement when solving a classification problem. In this respect, the Relief algorithm and its derivatives have been demonstrated to be a class of successful feature selectors. However, the computational cost of these algorithms is very high when large-scale datasets are processed. To solve this problem, we propose the fast ReliefF algorithm based on the information granulation of instances (IG-FReliefF). The algorithm uses K-means to granulate the dataset and selects the significant granules among them using the criteria defined by information entropy and information granulation, and then evaluates each feature on the dataset composed of the selected granules. Extensive experiments show that the proposed algorithm is more efficient than the existing representative algorithms, especially on large-scale data sets, and the proposed algorithm is almost the same as the comparison algorithm in terms of classification performance.

In matrix-object data, an object (or a sample) is described by more than one feature vector (record) and all of those feature vectors are responsible for the observed classification of the object. A task for matrix-object data is to cluster it into a set of groups by analyzing and utilizing the information of feature vectors. Matrix-object data are widespread in many real applications. Previous studies typically address data sets that an object is generally represented by a feature vector, which may be violated in many real-world tasks. In this paper, we propose a k-multi-numeric-values-representatives (abbr. k-Mnv-Rep) algorithm to cluster numeric matrix-object data. In this algorithm, a new dissimilarity measure between two numeric matrix-objects is defined and a new heuristic method of updating cluster centers is given. Furthermore, we also propose a k-multi-values-representatives (abbr. k-Mv-Rep) algorithm to cluster hybrid matrix-object data. The two proposed algorithms break the limitations of the previous studies, and can be applied to address matrix-object data sets that exist widely in many real-world tasks. The benefits and effectiveness of the two algorithms are shown by some experiments on real and synthetic data sets.

The pure accuracy measure is used to eliminate random consistency from the accuracy measure. Biases to both majority and minority classes in the pure accuracy are lower than that in the accuracy measure. In this paper, we demonstrate that compared with the accuracy measure and F-measure, the pure accuracy measure is class distribution insensitive and discriminative for good classifiers. The advantages make the pure accuracy measure suitable for traditional classification. Further, we mainly focus on two points: exploring a tighter generalization bound on pure accuracy based learning paradigm and designing a learning algorithm based on the pure accuracy measure. Particularly, with the self-bounding property, we build an algorithm-independent generalization bound on the pure accuracy measure, which is tighter than the existing bound of an order O(1/√N) (N is the number of instances). The proposed bound is free from making a smoothness or convex assumption on the hypothesis functions. In addition, we design a learning algorithm optimizing the pure accuracy measure and use it in the selective ensemble learning setting. The experiments on sixteen benchmark data sets and four image data sets demonstrate that the proposed method statistically performs better than the other eight representative benchmark algorithms.

In real world, multi-attribute group decision making (MAGDM) is a complicated cognitive process that involves expression, fusion and analysis of multi-source uncertain information. Among diverse soft computing tools for addressing MAGDM, the ones from granular computing (GrC) frameworks perform excellently via efficient strategies for multi-source uncertain information. However, they usually lack convincing semantic interpretations for MAGDM due to extreme information fusion rules and instabilities of information analysis mechanisms. This work adopts a typical GrC framework named multigranulation probabilistic models to enrich semantic interpretations for GrC-based MAGDM approaches, and constructs MAGDM-oriented multigranulation probabilistic models with dual hesitant fuzzy (DHF) information in light of the MULTIMOORA (Multi-Objective Optimization by Ratio Analysis plus the full MULTIplicative form) method. After reviewing several basic knowledge, we first put forward four types of DHF multigranulation probabilistic models. Then, according to the MULTIMOORA method, a DHF MAGDM algorithm is designed via the proposed theoretical models in the context of person-job (P-J) fit. Finally, an illustrative case study for P-J fit is investigated, and corresponding validity tests and comparative analysis are conducted as well to demonstrate the rationality of the presented models.

Cluster ensemble is an important research content of ensemble learning, which is used to aggregate several base clusterings to generate a single output clustering with improved robustness and quality. Since clustering is unsupervised, where the “accuracy” does not have a clear meaning, most of existing ensemble methods try to obtain the most consistent clustering result with base clusterings. However, it is difficult for these methods to realize “Multi-weaks equal to a Strong”. For example, on a data set with nonlinearly separable clusters, if the base clusterings are produced by some linear clusterers, these methods generally cannot integrate them to obtain a good nonlinear clustering. In this paper, we select k-means as a base clusterer and provide an ensemble clusterer (algorithm) of multiple k-means clusterings based on a local hypothesis. In the new algorithm, we study the extraction of the local-credible labels from a base clustering, the production of different base clusterings, the construction of cluster relation and the final assignment of each object. The proposed ensemble clusterer not only inherits the scalability of k-means but also overcomes its limitation that it only can find linearly separable clusters. Finally, the experimental results illustrate its effectiveness and efficiency.

Collaborative filtering is a fundamental technique in recommender systems, for which memory-based and matrix-factorization-based collaborative filtering are the two types of widely used methods. However, the performance of these two types of methods is limited in the case of sparse data, particularly with extremely sparse data. To improve the effectiveness of the methods in a sparse scenario, this paper proposes a multi-factor similarity measure that captures linear and nonlinear correlations between users resulting from extreme behavior. Subsequently, a fusion method that simultaneously considers the multi-factor similarity and the global rating information in a probability matrix factorization framework is proposed. In our framework, users’ local relations are integrated into the global ratings optimization process, so that prediction accuracy and robustness are improved in sparse data, particularly in extremely sparse data. To verify the performance of the proposed methods, we conduct experiments on four public datasets. The experimental results show that the fusion method is superior to the typical matrix factorization models used in collaborative filtering and significantly improves both the prediction results and robustness in sparse data.

Due to the complex structure of the real-world data, nonlinearly separable clustering is one of popular and widely studied clustering problems. Currently, various types of algorithms, such as kernel k-means, spectral clustering and density clustering, have been developed to solve this problem. However, it is difficult for them to balance the efficiency and effectiveness of clustering, which limits their real applications. To get rid of the deficiency, we propose a three-level optimization model for nonlinearly separable clustering which divides the clustering problem into three sub-problems: a linearly separable clustering on the object set, a nonlinearly separable clustering on the cluster set and an ensemble clustering on the partition set. An iterative algorithm is proposed to solve the optimization problem. The proposed algorithm can use low computational cost to effectively recognize nonlinearly separable clusters. The performance of this algorithm has been studied on synthetical and real data sets. Comparisons with other nonlinearly separable clustering algorithms illustrate the efficiency and effectiveness of the proposed algorithm.

With the increasing complexity of decision-making problems and environment, the integration and fusion of three-way decisions, rough set and multi-attribute group decision-making (MAGDM) have become a major trend in the field of decision analysis. Although many researchers have presented various MAGDM methods under different environments, there are still some imperfections, such as the weight information is not comprehensive or flexible enough, the decision results lack interpretability, and the impact of risk attitude is not fully taken into account. In order to overcome the above shortcomings and improve the scientificity and rationality of decision-making, a novel data-driven MAGDM method under interval-valued intuitionistic uncertain linguistic environment is established based on the idea of multi-granulation and three-way decisions. Our contributions can be identified as follows: (1) The multi-granulation weight mining and fusion methods for experts and attributes are proposed, respectively; (2) The coarse-granulation grading information based on three-way decisions is developed to enhance the interpretability and reference value of decision results; (3) The expected value with risk attitude factor is defined to compare interval-valued intuitionistic uncertain linguistic variables (IVIULVs) and then is used to grade and rank alternatives under different risk attitudes. To illustrate the feasibility and practicality of the proposed method, a case of logistics supplier selection in e-commerce enterprises is demonstrated. Furthermore, the advantages and characteristics of the proposed method are highlighted via detailed comparison and thorough analysis.

Multi-attribute group decision making (MAGDM) is a common activity for multi-variable complicated decision making situations by integrating collective wisdom. Aiming at fusing granular computing with three-way decisions (3WD) to study scheme synthesis and analysis of solution space, multi-granularity three-way decisions (MG-3WD) provide multi-dimension problem solving methods for MAGDM problems. By using MG-3WD frameworks, this paper intends to study viable strategies of processing consensus and conflicting opinions provided by different decision makers in the interval-valued hesitant fuzzy (IVHF) MAGDM problem. More specifically, after reviewing the relevant literature, four kinds of IVHF multigranulation decision-theoretic rough sets (MG-DTRSs) over two universes are proposed according to different risk appetites of experts firstly. Then, we explore some fundamental propositions of newly proposed models. Afterwards, solutions to MAGDM problems in the context of mergers and acquisitions (M&A) target selections by using the presented IVHF MG-DTRSs over two universes are constructed. At last, a M&A target selection case study, along with a sensitivity analysis and a comparative analysis, is applied to illustrate the established decision making approaches.

The notion of hesitant fuzzy linguistic term sets (HFLTSs), which enables experts to utilize a few possible linguistic terms to evaluate varieties of common qualitative information, plays a significant role in handling situations in cases where these experts are hesitant in offering linguistic expressions. For addressing the challenges of information analysis and information fusion in hesitant fuzzy linguistic (HFL) group decision making, in accordance with the multi-granularity three-way decisions paradigm, the primary purpose of this study is to develop the notion of multigranulation decision-theoretic rough sets (MG-DTRSs) into the HFL background within the two-universe framework. Having revisited the relevant literature, we first propose a hybrid model named adjustable HFL MG-DTRSs over two universes by introducing an adjustable parameter for the expected risk appetite of experts, in which both optimistic and pessimistic versions of HFL MG-DTRSs over two universes are special cases of the adjustable version. Second, some of the fundamental properties of the proposed model are discussed. Then, on the basis of the presented hybrid model, a group decision making approach within the HFL context is further constructed. Finally, a practical example, a comparative analysis, and a validity test concerning person-job fit problems are explored to reveal the rationality and practicability of the constructed decision making rule.

Multi-modal classification (MMC) aims to integrate the complementary information from different modalities to improve classification performance. Existing MMC methods can be grouped into two categories: traditional methods and deep learning-based methods. The traditional methods often implement fusion in a low-level original space. Besides, they mostly focus on the inter-modal fusion and neglect the intra-modal fusion. Thus, the representation capacity of fused features induced by them is insufficient. The deep learning-based methods implement the fusion in a high-level feature space where the associations among features are considered, while the whole process is implicit and the fused space lacks interpretability. Based on these observations, we propose a novel interpretative association-based fusion method for MMC, named AF. In AF, both the association information and the high-order information extracted from feature space are simultaneously encoded into a new feature space to help to train an MMC model in an explicit manner. Moreover, AF is a general fusion framework, and most existing MMC methods can be embedded into it to improve their performance. Finally, the effectiveness and the generality of AF are validated on 22 datasets, four typically traditional MMC methods adopting best modality, early, late and model fusion strategies and a deep learning-based MMC method.

Rough set theory is an efficient tool for dealing with inexact and uncertain information. Numerous studies have focused on rough set theory and associated methodologies, and in recent decades, various models and algorithms have been proposed. To clarify the application of information fusion in rough set theory, this paper presents an overview of existing information fusion approaches and methods for multi-source, multi-modality, multi-scale, and multi-view information systems from the perspective of objects, attributes, rough approximations, attribute reduction, and decision making. We provide a survey of recent applications of these theories and methods in various fields, and identify some potential challenges that require further research.

Detecting protein complexes from available protein–protein interaction (PPI) networks is an important task, and several related algorithms have been proposed. These algorithms usually consider a single topological metric and ignore the rich topological characteristics and inherent organization information of protein complexes. However, the effective use of such information is crucial to protein complex detection. To overcome this deficiency, this study presents a heuristic clustering algorithm to identify protein complexes by fully exploiting the topological information of PPI networks. By considering the clustering coefficient and the node degree, a new nodal metric is proposed to quantify the importance of each node within a local subgraph. An iterative paradigm is used to incrementally identify seed proteins and expand each seed to a cluster. First, among the unclustered nodes, the node with the highest nodal metric is selected as a new seed. Then, the seed is expanded to a cluster by adding candidate nodes recursively from its neighbors according to both the density of the cluster and the connection between a candidate node and the cluster. The experimental results demonstrate that the proposed algorithm outperforms other competing algorithms in terms of F-measure and accuracy.

Data stream mining problem has caused widely concerns in the area of machine learning and data mining. In some recent studies, ensemble classification has been widely used in concept drift detection, however, most of them regard classification accuracy as a criterion for judging whether concept drift happening or not. Information entropy is an important and effective method for measuring uncertainty. Based on the information entropy theory, a new algorithm using information entropy to evaluate a classification result is developed. It uses ensemble classification techniques, and the weight of each classifier is decided through the entropy of the result produced by an ensemble classifiers system. When the concept in data streams changing, the classifiers' weight below a threshold value will be abandoned to adapt to a new concept in one time. In the experimental analysis section, six databases and four proposed algorithms are executed. The results show that the proposed method can not only handle concept drift effectively, but also have a better classification accuracy and time performance than the contrastive algorithms.