Vulnerability assessment—a critical issue for networks—attempts to foresee unexpected destructive events or hostile attacks in the whole system. In this article, we consider a new Markov global connectivity metric—Kemeny constant, and take its derivative called Markov criticality to identify critical links. Markov criticality allows us to find links that are most influential on the derivative of Kemeny constant. Thus, we can utilize it to identity a critical link ( i , j ) from node i to node j , such that removing it leads to a minimization of networks’ global connectivity, i.e., the Kemeny constant. Furthermore, we also define a novel vulnerability index to measure the average speed by which we can disconnect a specified ratio of links with network decomposition. Our method is of high efficiency, which can be easily employed to calculate the Markov criticality in real-life networks. Comprehensive experiments on several synthetic and real-life networks have demonstrated our method’s better performance by comparing it with state-of-the-art baseline approaches.

The design of fusion engines is a subject of great importance in a variety of fields. In this paper, we focus on the problem of linear fusion at the feature level for multiple signal matrices with noises, with the features being extremal eigenvectors. When given multiple similarity matrices, the objective is to find an estimate of the latent signal eigenspace. The concentration result for the inner product of features from different matrix samples is developed, utilizing the random matrix theory. Based on of the theoretical results, we proposed an efficient algorithm,EigFuse, to solve the constrained data-driven optimization problem with different level of noises. Our method is of high efficiency by comparing it with state-of-the-art baseline approaches with multiple noise levels. Comprehensive experiments on several synthetic as well as real-life networks demonstrate our method’s superior performance.

In human concept learning, people can naturally combine a handful of labeled data with abundant unlabeled data when they make classification decisions, which is also known as semi-supervised learning (SSL) in machine learning. Especially, human concept learning not only is a static process in human cognition but also can vary gradually with dynamic environments. Nevertheless, the classical SSL algorithms must be redesigned to accommodate newly input data. In this sense, concept-cognitive learning may be a good choice, as it can implement dynamic processes by imitating human cognitive processes. Meanwhile, numerous SSL methods were designed based on the feature vector information of instances, while ignoring concept structural information that is a very important process in human knowledge organization. Based on this idea, a novel SSL method, named semi-supervised concept learning method (S2CL), is proposed for dynamic SSL by employing concept spaces, in which knowledge is represented by hierarchical concept structures. Moreover, to make full use of the global and local conceptual information, we further propose an extended version of S2CL (namely,$\text{S2CL}^{\alpha }$) for concept learning. More specifically, to effectively exploit the unlabeled data, this paper first shows some new related theories for S2CL (or$\text{S2CL}^{\alpha }$) based on a regular formal decision context; then a novel SSL framework is designed, and its corresponding algorithm is developed. Finally, we conduct some experiments on various datasets to demonstrate the effectiveness of our methods, which include concept classification and incremental learning under a large quantity of unlabeled data.

With the explosion of social media networks, many modern applications are concerning about people's connections, which leads to the so-called social computing. An elusive question is to study how opinion communities form and evolve in real-world networks with great individual diversity and complex human connections. In this scenario, the classic K-means technique and its extended versions could not be directly applied, as they largely ignore the relationship among interactive objects. On the other side, traditional community detection approaches in statistical physics would be neither adequate nor fair: they only consider the network topological structure but ignore the heterogeneous-objects' attributive information. To this end, we attempt to model a realistic social media network as a discrete-time dynamical system, where the opinion matrix and the community structure could mutually affect each other. In this paper, community detection in social media networks is naturally formulated as a multi-objective optimization problem (MOOP), i.e., finding a set of densely connected components with similar opinion vectors. We propose a novel and powerful graph K-means framework, which is composed of three coupled phases in each discrete-time period. Specifically, the first phase uses a fast heuristic approach to identify those opinion leaders who have relatively high local reputation; the second phase adopts a novel dynamic game model to find the locally Pareto-optimal community structure; and the final phase employs a robust opinion dynamics model to simulate the evolution of the opinion matrix. We conduct a series of comprehensive experiments on real-world benchmark networks to validate the performance of GK-means through comparisons with the state-of-the-art graph clustering technologies.

Multimedia data available in various disciplines are usually heterogeneous, containing representations in multi-views, where the cross-modal search techniques become necessary and useful. It is a challenging problem due to the heterogeneity of data with multiple modalities, multi-views in each modality and the diverse data categories. In this paper, we propose a novel multi-view cross-modal hashing method named Multi-view Collective Tensor Decomposition (MCTD) to fuse these data effectively, which can exploit the complementary feature extracted from multi-modality multi-view while simultaneously discovering multiple separated subspaces by leveraging the data categories as supervision information. Our contributions are summarized as follows: 1) we exploit tensor modeling to get better representation of the complementary features and redefine a latent representation space; 2) a block-diagonal loss is proposed to explicitly pursue a more discriminative latent tensor space by exploring supervision information; 3) we propose a new feature projection method to characterize the data and to generate the latent representation for incoming new queries. An optimization algorithm is proposed to solve the objective function designed for MCTD, which works under an iterative updating procedure. Experimental results prove the state-of-the-art precision of MCTD compared with competing methods.

Network embedding is a promising topic that maps the vertices to the latent space while keeps the structural proximity in the original space. The network embedding task is difficult since the network vertices have no specific time or space orders. Models that used to extract information from images and texts with regular space or time structures can not be directly applied in network heading. The key feature of network embedding methods should be further exploited. Previous network embedding reviews mainly focus on the models and algorithms used in different methods. In this survey, we review the network embedding works in the stochastic perspective either in data side or model side. Roughly, the network embedding methods fall into three main categories: matrix based methods, random walk based methods and aggregated based methods. We focus on the applications of stochastic models in solving the challenges of network embedding in data processing and modeling following the line of the three categories.

Learning from label proportions (LLP) is a new kind of learning problem which has attracted wide interest in the field of machine learning. Different from the well-known supervised learning, the training data of LLP is in form of bags and only the proportion of each class in each bag is available. Actually, many modern applications can be abstracted to this problem such as modeling voting behaviors and spam filtering. In this paper, we propose an end-to-end LLP model based on convolutional neural network called IDLLP, which employs the the idea of inverting a classifier calibration process to learn a classifier from bag probabilities. Firstly, convolutional neural network regression is used to estimate the values obtained by inverting the probability of each bag. Secondly, stochastic gradient descent based on batch is adapt to train the model, where the batch size depends on the bag size. At last, experiments demonstrate that our algorithm can obtain the best accuracies on image data compared with several recently developed methods.

In large-scale learning problem, the scalability of learning algorithms is usually the key factor affecting the algorithm practical performance, which is determined by both the time complexity of the learning algorithms and the amount of supervision information (i.e., labeled data). Learning with label proportions (LLP) is a new kind of machine learning problem which has drawn much attention in recent years. Different from the well-known supervised learning, LLP can estimate a classifier from groups of weakly labeled data, where only the positive/negative class proportions of each group are known. Due to its weak requirements for the input data, LLP presents a variety of real-world applications in almost all the fields involving anonymous data, like computer vision, fraud detection and spam filtering. However, even through the required labeled data is of a very small amount, LLP still suffers from the long execution time a lot due to the high time complexity of the learning algorithm itself. In this paper, we propose a very fast learning method based on inversing output scaling process and extreme learning machine, namely Inverse Extreme Learning Machine (IELM), to address the above issues. IELM can speed up the training process by order of magnitudes for large datasets, while achieving highly competitive classification accuracy with the existing methods at the same time. Extensive experiments demonstrate the significant speedup of the proposed method. We also demonstrate the feasibility of IELM with a case study in real-world setting: modeling image attributes based on ImageNet Object Attributes dataset.

Ordinal regression has received increasing interest in the past years. It aims to classify patterns by an ordinal scale. With the the explosive growth of data, the method of SVM with ordinal partitioning called SVMOP highlights its advantages due to its convenience of dealing with large scale data. However, the method of SVMOP for ordinal regression has not been exploited much. As we know, the costs should be different when dealing with mislabeled samples and how to use them plays a dominant role in model building. However, L2-loss which could enlarge the cost sensitivity has not been applied into SVM ordinal partition yet. In this paper, we propose the method of SVMOP with L2-loss for ordinal regression. Numerical results show that our approach outperforms the method of SVMOP with L1-loss and other ordianl regression models.

In credit card client classification problem, reducing misclassified rate is regarded as a key issue. Unfortunately, existing machine learning methods cannot be successfully applied to this problem. This paper introduces a classification model based on multiple criteria and multiple constraint levels linear programming (MC2LP), which equips two intervals of cutoff in the model. Two parallel hyperplanes are employed to indicate the relative positions between the points and hyperplanes. Then, we discuss the correctness of new model in error correction. Matrix representations of relevant models are also offered. Finally, compared to original MCLP, known MC2LP, Logistic Regression (LR) and Support Vector Machine (SVM), the propsed model shows superiority in solving two types of error related data mining problem.

Mining communities or clusters in networks is valuable in analyzing, designing, and optimizing many natural and engineering complex systems, e.g., protein networks, power grid, and transportation systems. Most of the existing techniques view the community mining problem as an optimization problem based on a given quality function(e.g., modularity), however none of them are grounded with a systematic theory to identify the central nodes in the network. Moreover, how to reconcile the mining efficiency and the community quality still remains an open problem. In this paper, we attempt to address the above challenges by introducing a novel algorithm. First, a kernel function with a tunable influence factor is proposed to measure the leadership of each node, those nodes with highest local leadership can be viewed as the candidate central nodes. Then, we use a discrete-time dynamical system to describe the dynamical assignment of community membership; and formulate the serval conditions to guarantee the convergence of each node's dynamic trajectory, by which the hierarchical community structure of the network can be revealed. The proposed dynamical system is independent of the quality function used, so could also be applied in other community mining models. Our algorithm is highly efficient: the computational complexity analysis shows that the execution time is nearly linearly dependent on the number of nodes in sparse networks. We finally give demonstrative applications of the algorithm to a set of synthetic benchmark networks and also real-world networks to verify the algorithmic performance.

Credit Reference Centre (CRC) of People's Bank of China (PBC) has built a big data: the largest personal credit database in the world with 800 million people's accounts collected from all commercial banks in China since 2003. From June 2006 to Sept 2009, Research Centre on Fictitious Economy and Data Science, Chinese Academy of Sciences (CASFEDS) and CRC jointly developed China's National Personal Credit Scoring System, known as "China Score", which is a unique and advanced KDD application under intelligent knowledge management on this big data. The system will be eventually serving all 1.3 billion population of China for their daily financial activities, such as bank accounts, credit card application, mortgage, personal loans, etc. It can become one of the most influential events of KDD techniques to human kind. This talk will introduce the key components of China Score project that includes objectives, modeling process, KDD techniques used in the projects, intelligent knowledge management and experience of the project development. In addition, the talk will also outline a number of policy recommendations based on China Score project which has been potentially impacting Chinese Government on its strategic decision making for China's economic developments.

Extracting knowledge from the transaction records and the personal data of credit card holders has great profit potential for the banking industry. The challenge is to detect/predict bankrupts and to keep and recruit the profitable customers. However, grouping and targeting credit card customers by traditional data-driven mining often does not directly meet the needs of the banking industry, because data-driven mining automatically generates classification outputs that are imprecise, meaningless, and beyond users' control. In this paper, we provide a novel domain-driven classification method that takes advantage of multiple criteria and multiple constraint-level programming for intelligent credit scoring. The method involves credit scoring to produce a set of customers' scores that allows the classification results actionable and controllable by human interaction during the scoring process. Domain knowledge and experts' experience parameters are built into the criteria and constraint functions of mathematical programming and the human and machine conversation is employed to generate an efficient and precise solution. Experiments based on various data sets validated the effectiveness and efficiency of the proposed methods.

A new kernel-based learning algorithm called kernel affine subspace nearest point (KASNP) approach is proposed in this paper. Inspired by the geometrical explanation of support vector machines (SVMs) and its nearest point problem in convex hulls, we extend the convex hull of each class to its corresponding affine subspace in high dimensional space induced by kernel. In two class affine subspaces, KASNP finds the nearest points and then constructs a separating hyperplane, which bisects the line segment joining them. The nearest point problem of KASNP is only an unconstrained optimal problem whose solution can be directly computed. Compared with SVM, KASNP avoids solving convex quadratic programming. Experiments on two-spiral dataset, two UCI credit datasets, and face recognition datasets show that our proposed KASNP is effective for data classification.

In this paper, we identify a new research problem on cleansing noisy data streams which contain incorrectly labeled training examples. The objective is to accurately identify and remove mislabeled data, such that the prediction models built from the cleansed streams can be more accurate than the ones trained from the raw noisy streams. For this purpose, we first use bias-variance decomposition to derive a maximum variance margin (MVM) principle for stream data cleansing. Following this principle, we further propose a local and global filtering (LgF) framework to combine the strength of local noise filtering (within one single data chunk) and global noise filtering (across a number of adjacent data chunks) to identify erroneous data. Experimental results on six data streams (including two real-world data streams) demonstrate that LgF significantly outperforms simple methods in identifying noisy examples.

Mining concept drifting data streams is a defining challenge for data mining research. Recent years have seen a large body of work on detecting changes and building prediction models from stream data, with a vague understanding on the types of the concept drifting and the impact of different types of concept drifting on the mining algorithms. In this paper, we first categorize concept drifting into two scenarios: Loose Concept Drifting (LCD) and Rigorous Concept Drifting (RCD), and then propose solutions to handle each of them separately. For LCD data streams, because concepts in adjacent data chunks are sufficiently close to each other, we apply kernel mean matching (KMM) method to minimize the discrepancy of the data chunks in the kernel space. Such a minimization process will produce weighted instances to build classifier ensemble and handle concept drifting data streams. For RCD data streams, because genuine concepts in adjacent data chunks may randomly and rapidly change, we propose a new Optimal Weights Adjustment (OWA) method to determine the optimum weight values for classifiers trained from the most recent (up-to-date) data chunk, such that those classifiers can form an accurate classifier ensemble to predict instances in the yet-to-come data chunk. Experiments on synthetic and real-world datasets will show that weighted instance approach is preferable when the concept drifting is mainly caused by the changing of the class prior probability; whereas the weighted classifier approach is preferable when the concept drifting is mainly triggered by the changing of the conditional probability.

Data mining is concerned with important aspects related to both database techniques and AI/machine learning mechanisms, and provides an excellent opportunity for exploring the interesting relationship between retrieval and inference/reasoning, a fundamental issue concerning the nature of data mining. In the data mining context, this relationship can be restated as connection and differences between data retrieval and data mining. In this paper we explore this relationship by examining time series data indexed through R*-trees, and study the issues of (1) retrieval of data similar to a given query (which is a plain data retrieval task), and (2) clustering of the data based on similarity (which is a data mining task). Along the way of examination of our central theme, we also report new algorithms and new results related to these two issues. We have developed a software package consisting of a similarity analysis tool and two implemented clustering algorithms: KMeans-R and Hierarchy-R. A sketch of experimental results is also provided

This work reveals that instead of the polynomial bounds in previous literatures there exists a sharper bound of exponential form for the L2norm of an arbitrary shaped random matrix. Based on the newly elaborated bound, a nonuniform sampling method is presented to succinctly approximate a matrix with a sparse binary one, and thus relieves the computation loads ofk-NN classifier in both time and storage. The method is also pass-efficient because sampling and quantizing are combined together in a single step and the whole process can be completed within one pass over the input matrix. In the evaluations on compression ratio and reconstruction error, the sampling method exhibits impressive capability in providing succinct and tight approximations for the input matrices. The most significant finding in the classification experiment is that thek-NN classifier based on the approximation can even outperform the standard one. This provides another strong evidence for the claim that our method is especially capable in capturing intrinsic characteristics.

In this paper, we address a new research problem on active learning from data streams where data volumes grow continuously and labeling all data is considered expensive and impractical. The objective is to label a small portion of stream data from which a model is derived to predict newly arrived instances as accurate as possible. In order to tackle the challenges raised by data streams' dynamic nature, we propose a classifier ensembling based active learning framework which selectively labels instances from data streams to build an accurate classifier. A minimal variance principle is introduced to guide instance labeling from data streams. In addition, a weight updating rule is derived to ensure that our instance labeling process can adaptively adjust to dynamic drifting concepts in the data. Experimental results on synthetic and real-world data demonstrate the performances of the proposed efforts in comparison with other simple approaches.

Existing data analysis techniques have difficulty in handling multidimensional data. Multidimensional data has been a challenge for data analysis because of the inherent sparsity of the points. In this paper, we first present a novel data preprocessing technique called shrinking which optimizes the inherent characteristic of distribution of data. This data reorganization concept can be applied in many fields such as pattern recognition, data clustering, and signal processing. Then, as an important application of the data shrinking preprocessing, we propose a shrinking-based approach for multidimensional data analysis which consists of three steps: data shrinking, cluster detection, and cluster evaluation and selection. The process of data shrinking moves data points along the direction of the density gradient, thus generating condensed, widely-separated clusters. Following data shrinking, clusters are detected by finding the connected components of dense cells (and evaluated by their compactness). The data-shrinking and cluster-detection steps are conducted on a sequence of grids with different cell sizes. The clusters detected at these scales are compared by a cluster-wise evaluation measurement, and the best clusters are selected as the final result. The experimental results show that this approach can effectively and efficiently detect clusters in both low and high-dimensional spaces.