Please wait a minute...

Frontiers of Computer Science

Current Issue

, Volume 12 Issue 2 Previous Issue   
For Selected: View Abstracts Toggle Thumbnails
Binary relevance for multi-label learning: an overview
Min-Ling ZHANG, Yu-Kun LI, Xu-Ying LIU, Xin GENG
Front. Comput. Sci.. 2018, 12 (2): 191-202.
Abstract   PDF (435KB)

Multi-label learning deals with problems where each example is represented by a single instance while being associated with multiple class labels simultaneously. Binary relevance is arguably the most intuitive solution for learning from multi-label examples. It works by decomposing the multi-label learning task into a number of independent binary learning tasks (one per class label). In view of its potential weakness in ignoring correlations between labels, many correlation-enabling extensions to binary relevance have been proposed in the past decade. In this paper, we aim to review the state of the art of binary relevance from three perspectives. First, basic settings for multi-label learning and binary relevance solutions are briefly summarized. Second, representative strategies to provide binary relevancewith label correlation exploitation abilities are discussed. Third, some of our recent studies on binary relevance aimed at issues other than label correlation exploitation are introduced. As a conclusion, we provide suggestions on future research directions.

References | Supplementary Material | Related Articles | Metrics
Set-based discrete particle swarm optimization and its applications: a survey
Wei-Neng CHEN, Da-Zhao TAN
Front. Comput. Sci.. 2018, 12 (2): 203-216.
Abstract   PDF (487KB)

Particle swarm optimization (PSO) is one of the most popular population-based stochastic algorithms for solving complex optimization problems. While PSO is simple and effective, it is originally defined in continuous space. In order to take advantage of PSO to solve combinatorial optimization problems in discrete space, the set-based PSO (SPSO) framework extends PSO for discrete optimization by redefining the operations in PSO utilizing the set operations. Since its proposal, S-PSO has attracted increasing research attention and has become a promising approach for discrete optimization problems. In this paper, we intend to provide a comprehensive survey on the concepts, development and applications of S-PSO. First, the classification of discrete PSO algorithms is presented. Then the S-PSO framework is given. In particular, we will give an insight into the solution construction strategies, constraint handling strategies, and alternative reinforcement strategies in S-PSO together with its different variants. Furthermore, the extensions and applications of S-PSO are also discussed systemically. Some potential directions for the research of S-PSO are also discussed in this paper.

References | Supplementary Material | Related Articles | Metrics
A survey on one-bit compressed sensing: theory and applications
Zhilin LI, Wenbo XU, Xiaobo ZHANG, Jiaru LIN
Front. Comput. Sci.. 2018, 12 (2): 217-230.
Abstract   PDF (512KB)

In the past few decades, with the growing popularity of compressed sensing (CS) in the signal processing field, the quantization step in CS has received significant attention. Current research generally considers multi-bit quantization. For systems employing quantization with a sufficient number of bits, a sparse signal can be reliably recovered using various CS reconstruction algorithms.

Recently, many researchers have begun studying the onebit case for CS. As an extreme case of CS, onebit CS preserves only the sign information of measurements, which reduces storage costs and hardware complexity. By treating one-bit measurements as sign constraints, it has been shown that sparse signals can be recovered using certain reconstruction algorithms with a high probability. Based on the merits of one-bit CS, it has been widely applied to many fields, such as radar, source location, spectrum sensing, and wireless sensing network.

In this paper, the characteristics of one-bit CS and related works are reviewed. First, the framework of one-bit CS is introduced. Next, we summarize existing reconstruction algorithms. Additionally, some extensions and practical applications of one-bit CS are categorized and discussed. Finally, our conclusions and the further research topics are summarized.

References | Supplementary Material | Related Articles | Metrics
Mobile crowd sensing task optimal allocation: a mobility pattern matching perspective
Liang WANG, Zhiwen YU, Bi GUO, Fei YI, Fei XIONG
Front. Comput. Sci.. 2018, 12 (2): 231-244.
Abstract   PDF (658KB)

With the proliferation of sensor-equipped portable mobile devices, Mobile CrowdSensing (MCS) using smart devices provides unprecedented opportunities for collecting enormous surrounding data. In MCS applications, a crucial issue is how to recruit appropriate participants from a pool of available users to accomplish released tasks, satisfying both resource efficiency and sensing quality. In ordern to meet these two optimization goals simultaneously, in this paper, we present a novel MCS task allocation framework by aligning existing task sequence with users’ moving regularity as much as possible. Based on the process of mobility repetitive pattern discovery, the original task allocation problem is converted into a pattern matching issue, and the involved optimization goals are transformed into pattern matching length and support degree indicators. To determine a trade-off between these two competitive metrics, we propose greedybased optimal assignment scheme search approaches, namely MLP, MDP, IU1 and IU2 algorithm, with respect to matching length-preferred, support degree-preferred and integrated utility, respectively. Comprehensive experiments on realworld open data set and synthetic data set clearly validate the effectiveness of our proposed framework on MCS task optimal allocation.

References | Supplementary Material | Related Articles | Metrics
Online clustering of streaming trajectories
Jiali MAO, Qiuge SONG, Cheqing JIN, Zhigang ZHANG, Aoying ZHOU
Front. Comput. Sci.. 2018, 12 (2): 245-263.
Abstract   PDF (1560KB)

With the increasing availability of modern mobile devices and location acquisition technologies, massive trajectory data of moving objects are collected continuously in a streaming manner. Clustering streaming trajectories facilitates finding the representative paths or common moving trends shared by different objects in real time. Although data stream clustering has been studied extensively in the past decade, little effort has been devoted to dealing with streaming trajectories. The main challenge lies in the strict space and time complexities of processing the continuously arriving trajectory data, combined with the difficulty of concept drift. To address this issue, we present two novel synopsis structures to extract the clustering characteristics of trajectories, and develop an incremental algorithm for the online clustering of streaming trajectories (called OCluST). It contains a micro-clustering component to cluster and summarize the most recent sets of trajectory line segments at each time instant, and a macro-clustering component to build large macro-clusters based on micro-clusters over a specified time horizon. Finally, we conduct extensive experiments on four real data sets to evaluate the effectiveness and efficiency of OCluST, and compare it with other congeneric algorithms. Experimental results show that OCluST can achieve superior peformance in clustering streaming trajectories.

References | Supplementary Material | Related Articles | Metrics
Efficient software product-line model checking using induction and a SAT solver
Fei HE, Yuan GAO, Liangze YIN
Front. Comput. Sci.. 2018, 12 (2): 264-279.
Abstract   PDF (541KB)

Software product line (SPL) engineering is increasingly being adopted in safety-critical systems. It is highly desirable to rigorously show that these systems are designed correctly. However, formal analysis for SPLs is more difficult than for single systems because an SPL may contain a large number of individual systems. In this paper, we propose an efficient model-checking technique for SPLs using induction and a SAT (Boolean satisfiability problem) solver. We show how an induction-based verification method can be adapted to the SPLs, with the help of a SAT solver. To combat the state space explosion problem, a novel technique that exploits the distinguishing characteristics of SPLs, called feature cube enlargement, is proposed to reduce the verification efforts. The incremental SAT mechanism is applied to further improve the efficiency. The correctness of our technique is proved. Experimental results show dramatic improvement of our technique over the existing binary decision diagram (BDD)-based techniques.

References | Supplementary Material | Related Articles | Metrics
Combined classifier for cross-project defect prediction: an extended empirical study
Yun ZHANG, David LO, Xin XIA, Jianling SUN
Front. Comput. Sci.. 2018, 12 (2): 280-296.
Abstract   PDF (564KB)

To facilitate developers in effective allocation of their testing and debugging efforts, many software defect prediction techniques have been proposed in the literature. These techniques can be used to predict classes that are more likely to be buggy based on the past history of classes, methods, or certain other code elements. These techniques are effective provided that a sufficient amount of data is available to train a prediction model. However, sufficient training data are rarely available for new software projects. To resolve this problem, cross-project defect prediction, which transfers a prediction model trained using data from one project to another, was proposed and is regarded as a new challenge in the area of defect prediction. Thus far, only a few cross-project defect prediction techniques have been proposed. To advance the state of the art, in this study, we investigated seven composite algorithms that integrate multiple machine learning classifiers to improve cross-project defect prediction. To evaluate the performance of the composite algorithms, we performed experiments on 10 open-source software systems from the PROMISE repository, which contain a total of 5,305 instances labeled as defective or clean. We compared the composite algorithms with the combined defect predictor where logistic regression is used as the meta classification algorithm (CODEPLogistic), which is the most recent cross-project defect prediction algorithm in terms of two standard evaluation metrics: cost effectiveness and F-measure. Our experimental results show that several algorithms outperform CODEPLogistic: Maximum voting shows the best performance in terms of F-measure and its average F-measure is superior to that of CODEPLogistic by 36.88%. Bootstrap aggregation (BaggingJ48) shows the best performance in terms of cost effectiveness and its average cost effectiveness is superior to that of CODEPLogistic by 15.34%.

References | Supplementary Material | Related Articles | Metrics
On the selection of solutions for mutation in differential evolution
Yong WANG, Zhi-Zhong LIU, Jianbin LI, Han-Xiong LI, Jiahai WANG
Front. Comput. Sci.. 2018, 12 (2): 297-315.
Abstract   PDF (1062KB)

Differential evolution (DE) is a kind of evolutionary algorithms, which is suitable for solving complex optimization problems. Mutation is a crucial step in DE that generates new solutions from old ones. It was argued and has been commonly adopted in DE that the solutions selected for mutation should have mutually different indices. This restrained condition, however, has not been verified either theoretically or empirically yet. In this paper, we empirically investigate the selection of solutions for mutation in DE. From the observation of the extensive experiments, we suggest that the restrained condition could be relaxed for some classical DE versions as well as some advanced DE variants. Moreover, relaxing the restrained condition may also be useful in designing better future DE algorithms.

References | Supplementary Material | Related Articles | Metrics
Sequential quadratic programming enhanced backtracking search algorithm
Wenting ZHAO, Lijin WANG, Yilong YIN, Bingqing WANG, Yuchun TANG
Front. Comput. Sci.. 2018, 12 (2): 316-330.
Abstract   PDF (2190KB)

In this paper, we propose a new hybrid method called SQPBSA which combines backtracking search optimization algorithm (BSA) and sequential quadratic programming (SQP). BSA, as an exploration search engine, gives a good direction to the global optimal region, while SQP is used as a local search technique to exploit the optimal solution. The experiments are carried on two suits of 28 functions proposed in the CEC-2013 competitions to verify the performance of SQPBSA. The results indicate the proposed method is effective and competitive.

References | Supplementary Material | Related Articles | Metrics
Evolutionary under-sampling based bagging ensemble method for imbalanced data classification
Bo SUN, Haiyan CHEN, Jiandong WANG, Hua XIE
Front. Comput. Sci.. 2018, 12 (2): 331-350.
Abstract   PDF (549KB)

In the class imbalanced learning scenario, traditional machine learning algorithms focusing on optimizing the overall accuracy tend to achieve poor classification performance especially for the minority class in which we are most interested. To solve this problem, many effective approaches have been proposed. Among them, the bagging ensemble methods with integration of the under-sampling techniques have demonstrated better performance than some other ones including the bagging ensemble methods integrated with the over-sampling techniques, the cost-sensitive methods, etc. Although these under-sampling techniques promote the diversity among the generated base classifiers with the help of random partition or sampling for the majority class, they do not take any measure to ensure the individual classification performance, consequently affecting the achievability of better ensemble performance. On the other hand, evolutionary under-sampling EUS as a novel undersampling technique has been successfully applied in searching for the best majority class subset for training a goodperformance nearest neighbor classifier. Inspired by EUS, in this paper, we try to introduce it into the under-sampling bagging framework and propose an EUS based bagging ensemble method EUS-Bag by designing a new fitness function considering three factors to make EUS better suited to the framework. With our fitness function, EUS-Bag could generate a set of accurate and diverse base classifiers. To verify the effectiveness of EUS-Bag, we conduct a series of comparison experiments on 22 two-class imbalanced classification problems. Experimental results measured using recall, geometric mean and AUC all demonstrate its superior performance.

References | Supplementary Material | Related Articles | Metrics
A formal model for plastic human computer interfaces
Abdelkrim CHEBIEB, Yamine AIT AMEUR
Front. Comput. Sci.. 2018, 12 (2): 351-375.
Abstract   PDF (1129KB)

The considerable and significant progress achieved in the design and development of new interaction devices between man and machine has enabled the emergence of various powerful and efficient input and/or output devices. Each of these new devices brings specific interaction modes.With the emergence of these devices, new interaction techniques and modes arise and new interaction capabilities are offered. New user interfaces need to be designed or former ones need to evolve. The design of so called plastic user interfaces contributes to handling such evolutions. The key requirement for the design of such a user interface is that the new obtained user interface shall be adapted to the application and have, at least, the same behavior as the previous (adapted) one. This paper proposes to address the problem of user interface evolution due to the introduction of new interaction devices and/or new interaction modes. More, precisely, we are interested by the study of the design process of a user interface resulting from the evolution of a former user interface due to the introduction of new devices and/or new interaction capabilities. We consider that interface behaviors are described by labelled transition systems and comparison between user interfaces is handled by an extended definition of the bi-simulation relationship to compare user interface behaviors when interaction modes are replaced by new ones.

References | Supplementary Material | Related Articles | Metrics
Decomposition for a new kind of imprecise information system
Shaobo DENG, Sujie GUAN, Min LI, Lei WANG, Yuefei SUI
Front. Comput. Sci.. 2018, 12 (2): 376-395.
Abstract   PDF (409KB)

In this paper, we first propose a new kind of imprecise information system, in which there exist conjunctions (∧’s), disjunctions (∨’s) or negations (¬’s). Second, this paper discusses the relation that only contains ∧’s based on relational database theory, and gives the syntactic and semantic interpretation for ∧ and the definitions of decomposition and composition and so on. Then, we prove that there exists a kind of decomposition such that if a relation satisfies some property then it can be decomposed into a group of classical relations (relations do not contain ∧) that satisfy a set of functional dependencies and the original relation can be synthesized from this group of classical relations. Meanwhile, this paper proves the soundness theorem and the completeness theorem for this decomposition.Consequently, a relation containing ∧’s can be equivalently transformed into a group of classical relations that satisfy a set of functional dependencies. Finally, we give the definition that a relation containing ∧’s satisfies a set of functional dependencies. Therefore, we can introduce other classical relational database theories to discuss this kind of relation.

References | Related Articles | Metrics
Comments on “Some new distance measures for type-2 fuzzy sets and distance measure based ranking for group decision making problems”
Sukhveer SINGH, Harish GARG
Front. Comput. Sci.. 2018, 12 (2): 396-400.
Abstract   PDF (236KB)

In this article, we have pointed out that some propositions corresponding to the distance measure between the type-2 fuzzy sets (T2FSs) as provided by Singh (Frontiers of Computer Science, 2014, 8(5), 741–752), are incorrect by a counterexample. Further, these propositions have been corrected in the present manuscript by giving a correct relation between the T2FSs and validating it with a numerical example.

References | Related Articles | Metrics
13 articles