2019 IEEE DATA MINING

Comments Mining With TF-IDF the Inherent Bias and Its Removal

Abstract: Text mining has gained great momentum in recent years, with user-generated content becoming widely available. One key use is comment mining, with much attention being given to sentiment analysis and opinion mining. An essential step in the process of comment mining is text pre-processing; a step in which each linguistic term is assigned with a weight that commonly increases with its appearance in the studied text, yet is offset by the frequency of the term in the domain of interest. A common practice is to use the well-known tf-idf formula to compute these weights. This paper reveals the bias introduced by between-participants’ discourse to the study of comments in social media, and proposes an adjustment. We find that content extracted from discourse is often highly correlated, resulting in dependency structures between observations in the study, thus introducing a statistical bias. Ignoring this bias can manifest in a non-robust analysis at best and can lead to an entirely wrong conclusion at worst. We propose an adjustment to tf-idf that accounts for this bias. We illustrate the effects of both the bias and correction with with seven Face book fan pages data, covering different domains, including news, finance, politics, sport, shopping, and entertainment.

Collaborative Optimization of Service Composition for Data-Intensive Applications in a Hybrid Cloud

Abstract: The multi-valued evaluations of quality of service (QoS), the complicated constraints between cloud services (CSs) and the collaborative resource assignments add many difficulties to the problem of CS composition for data-intensive applications (DiA) in a hybrid cloud (CSCD-HC). Solving the CSCD-HC problem has become a challenging task due to the uncertain QoS, the diverse hardware configurations and the flexible pricing about CSs. This paper proposes a collaborative optimization approach for CSCD-HC. This approach models a DiA as a role-based collaboration (RBC) system and employs the environments – classes, agents, roles, groups, and objects (E-CARGO) model to formalize the CSCD-HC problem with complicated constraints. To deal with the multi-valued QoS evaluations, this paper exploits the cloud model theory to analyze the performance of CSs, and presents a new method utilizing the Mahalanobis distance to improve the similarity calculation of QoS cloud models. Based on it, the qualification of candidate CSs can be precisely measured for supporting CS composition. A solution via the IBM ILOG CPLEX optimization package is put forward to solve the CSCD-HC problem. The experimental results demonstrate that the proposed approach is effective and feasible for optimizing CSCD-HC.

Cause Infer Automated End-to-End Performance Diagnosis with Hierarchical Causality Graph in Cloud Environment

Abstract: Modern computing systems especially cloud-based and cloud-centric systems always consist of a mass of components running in large distributed environments with complicated interactions. They are vulnerable to performance problems due to the highly dynamic runtime environment changes (e.g., overload and resource contention) or software bugs (e.g., memory leak). Unfortunately, it is notoriously difficult to diagnose the root causes of these performance problems in a fine granularity due to complicated interactions and a large cardinality of potential cause set. In this paper, we build an automated, black-box and end-to-end cause inference system named Cause Infer to pinpoint the root causes or at least provide some hints. Cause Infer can automatically map a distributed system to a two-layer hierarchical causality graph and infer the root causes along the causal paths in the causality graph. Cause Infer models the fault propagation paths in an explicit way and works without instrumentation to the running production system, which makes Cause Infer more effective and practical than previous approaches. The experimental evaluations in two benchmark systems show that Cause Infer can identify the root causes in a high accuracy. Compared to several state-of-the-art approaches, Cause Infer can achieve over 10% improvement. Moreover, Cause Infer is lightweight and flexible enough to readily scale out in large distributed systems. With Cause Infer, the mean time to recovery (MTTR) of the cloud systems can be significantly reduced.

Chameleon A Hybrid, Proactive Auto-Scaling Mechanism on a Level-Playing Field

Abstract: Auto-scalars for clouds promise stable service quality at low costs when facing changing workload intensity. The major public cloud providers provide trigger-based auto-scalars based on thresholds. However, trigger-based auto-scaling has reaction times in the order of minutes. Novel auto-scalars from literature try to overcome the limitations of reactive mechanisms by employing proactive prediction methods. However, the adoption of proactive auto-scalars in production is still very low due to the high risk of relying on a single proactive method. This paper tackles the challenge of reducing this risk by proposing a new hybrid auto-scaling mechanism, called Chameleon, combining multiple different proactive methods coupled with a reactive fallback mechanism. Chameleon employs on-demand, automated time series-based forecasting methods to predict the arriving load intensity in combination with run-time service demand estimation to calculate the required resource consumption per work unit without the need for application instrumentation. We benchmark Chameleon against five different state-of-the-art proactive and reactive auto-scalars one in three different private and public cloud environments. We generate five different representative workloads each taken from different real-world system traces. Overall, Chameleon achieves the best scaling behavior based on user and elasticity performance metrics, analyzing the results from 400 hours aggregated experiment time.

An Efficient Semi-Supervised Multi-label Classifier Capable of Handling Missing Labels

Abstract: Multi-label classification has received considerable interest in recent years. Multi-label classifiers usually need to address many issues including: handling large-scale datasets with many instances and a large set of labels, compensating missing label assignments in the training set, considering correlations between labels, as well as exploiting unlabeled data to improve prediction performance. To tackle datasets with a large set of labels, embedding-based methods represent the label assignments in a low dimensional space. Many state-of-the-art embedding-based methods use a linear dimensionality reduction to map the label assignments to a low-dimensional space. However, by doing so, these methods actually neglect the tail labels - labels that are infrequently assigned to instances. In this paper, we propose an embedding-based method that non-linearly embeds the label vectors using a stochastic approach, thereby predicting the tail labels more accurately. Moreover, the proposed method has excellent mechanisms for handling missing labels, dealing with large-scale datasets, as well as exploiting unlabeled data. Experiments on real-world datasets show that our method outperforms state-of-the-art multi-label classifiers by a large margin, in terms of prediction performance, as well as training time. Our implementation of the proposed method is available online.

Automated Discovery of Process Models from Event Logs Review and Benchmark

Abstract:  Process mining allows analysts to exploit logs of historical executions of business processes to extract insights regarding the actual performance of these processes. One of the most widely studied process mining operations is automated process discovery. An automated process discovery method takes as input an event log, and produces as output a business process model that captures the control-flow relations between tasks that are observed in or implied by the event log. Various automated process discovery methods have been proposed in the past two decades, striking different tradeoffs between scalability, accuracy and complexity of the resulting models. However, these methods have been evaluated in an ad-hoc manner, employing different datasets, experimental setups, evaluation measures and baselines, often leading to incomparable conclusions and sometimes un reproducible results due to the use of closed datasets. This article provides a systematic review and comparative evaluation of automated process discovery methods, using an open-source benchmark and covering twelve publicly-available real-life event logs, twelve proprietary real-life event logs, and nine quality metrics. The results highlight gaps and unexplored tradeoffs in the field, including the lack of scalability of some methods and a strong divergence in their performance with respect to the different quality metrics used.

Budget and Deadline Aware e-Science Workflow Scheduling in Clouds

Abstract: Basic science is becoming ever more computationally intensive, increasing the need for large-scale compute and storage resources, be they within a High Performance Computer cluster, or more recently within the cloud. In most cases, large scale scientific computation is represented as a workflow for scheduling and runtime provisioning. Such scheduling become an even more challenging problem on cloud systems due to the dynamic nature of the cloud, in particular, the elasticity, the pricing models (both static and dynamic), the non-homogeneous resource types, the vast array of services, and Virtualization. This mapping of workflow tasks on to a set of provisioned instances is an example of the general scheduling problem and is NP-complete. In addition, we also need to ensure that certain runtime constraints are met - the most typical being the cost of the computation and the time which that computation requires to complete. In this article, we introduce a new heuristic scheduling algorithm, Budget Deadline Aware Scheduling (BDAS) that addresses eScience workflow scheduling under budget and deadline constraints in Infrastructure as a Service (IaaS) clouds. The novelty of our work is satisfying both budget and deadline constraints while introducing a tunable cost-time trade off over heterogeneous instances. In addition, we study the stability and robustness of our algorithm by performing sensitivity analysis. The results demonstrate that overall BDAS finds a viable schedule for more than 40000 test cases accomplishing both defined constraints. Budget and deadline. Moreover, our algorithm achieves a 17:0 􀀀 23:8% higher success rate when compared to state of the art algorithms.

Adversarial Deep Learning Models with Multiple Adversaries

Abstract: We develop an adversarial learning algorithm for supervised classification in general and Convolutional Neural Networks (CNN) in particular. The algorithm’s objective is to produce small changes to the data distribution defined over positive and negative class labels so that the resulting data distribution is misclassified by the CNN. The theoretical goal is to determine a manipulating change on the input data that finds learner decision boundaries where many positive labels become negative labels. Then we propose a CNN which is secure against such unforeseen changes in data. The algorithm generates adversarial manipulations by formulating a multiplayer stochastic game targeting the classification performance of the CNN. The multiplayer stochastic game is expressed in terms of multiple two-player sequential games. Each game consists of interactions between two players – an intelligent adversary and the learner CNN – such that a player’s payoff function increases with interactions. Following the convergence of a sequential non co operative Stackel berg game, each two-player game is solved for the Nash equilibrium. The Nash equilibrium finds a pair of strategies (learner weights and evolutionary operations) from which there is no incentive for either learner or adversary to deviate. We then retrain the learner over all the adversarial manipulations generated by multiple players to propose a secure CNN which is robust to subsequent adversarial data manipulations. The adversarial data and corresponding CNN performance is evaluated on MNIST handwritten digits data. The results suggest that game theory and evolutionary algorithms are very effective in securing deep learning models against performance vulnerabilities simulated as attack scenarios from multiple adversaries.

Adaptive Distributed RDF Graph Fragmentation and Allocation based on Query Workload

Abstract: As massive volumes of Resource Description Framework (RDF) data are growing, designing a distributed RDF database system to manage them is necessary. In designing this system, it is very common to partition the RDF data into some parts, called fragments, which are then distributed. Thus, the distribution design comprises two steps: fragmentation and allocation. In this study, we explore the workload for fragmentation and allocation, which aims to reduce the communication cost during SPARQL query processing. Specifically, we adaptively maintain some frequent access patterns (FAPs) to reflect the characteristics of the workload while ensuring the data integrity and approximation ratio. Based on these frequent access patterns, we propose three fragmentation strategies, namely vertical, horizontal and mixed fragmentation, to divide RDF graphs while meeting different types of query processing objectives. After fragmentation, we discuss how to allocate these fragments to various sites while balancing the fragments. Finally, we discuss how to process queries based on the results of fragmentation and allocation. Experiments over large RDF datasets confirm the superior performance of our proposed solutions.

A Comparative Study of Ontology Matching Systems via Inferential Statistics

Abstract: Comparing ontology matching systems are typically performed by comparing their average performances over multiple datasets. However, this paper examines the alignment systems using statistical inference since averaging is statistically unsafe and inappropriate. The statistical tests for comparison of two or multiple alignment systems are theoretically and empirically reviewed. For comparison of two systems, the Wilcox on signed-rank and McNamara’s mid-p and asymptotic tests are recommended due to their robustness and statistical safety in different circumstances. The Friedman and Quade tests with their corresponding post-hoc procedures are studied for comparison of multiple systems, and their [dis]advantages are discussed. The statistical methods are then applied to benchmark and multiform tracks from the ontology matching evaluation initiative (OAEI) 2015 and their results are reported and visualized by critical difference diagrams.

A General Theory of IR Evaluation Measures

Abstract:  Interval scales are assumed by several basic descriptive statistics, such as mean and variance, and by many statistical significance tests which are daily used in IR to compare systems. Unfortunately, so far, there has not been any systematic and formal study to discover the actual scale properties of IR measures. Therefore, in this paper, we develop a theory of IR evaluation measures, based on the representational theory of measurements, to determine whether and when IR measures are interval scales. We found that common set-based retrieval measures – namely Precision, Recall, and F-measure – always are interval scales in the case of binary relevance while this happens also in the case of multi-graded relevance only when the relevance degrees themselves are on a ratio scale and we define a specific partial order among systems. In the case of rank-based retrieval measures – namely AP, gRBP, DCG, and ERR – only gRPB is an interval scale when we choose a specific value of the parameter p and define a specific total order among systems while all the other IR measures are not interval scales. Besides the formal framework itself and the proof of the scale properties of several commonly used IR measures, the paper also defines some brand new set-based and rank-based IR evaluation measures which ensure to be interval scales.

A New Formulation of Linear Discriminant Analysis for Robust Dimensionality Reduction

Abstract: Dimensionality reduction is a critical technology in the domain of pattern recognition, and linear discriminator analysis (LDA) is one of the most popular supervised dimensionality reduction methods. However, whenever its distance criterion of objective function uses L2-norm, it is sensitive to outliers. In this paper, we propose a new formulation of linear discriminant analysis via joint L2;1-norm minimization on objective function to induce robustness, so as to efficiently alleviate the influence of outliers and improve the robustness of proposed method. An efficient iterative algorithm is proposed to solve the optimization problem and proved to be convergent. Extensive experiments are performed on an artificial data set, on UCI data sets and on four face data sets, which sufficiently demonstrates the efficiency of comparing to other methods and robustness to outliers of our approach.

A Note on the Behavior of Majority Voting in Multi-Class Domains with Biased Annotators

Abstract: Majority voting is a popular and robust strategy to aggregate different opinions in learning from crowds, where each worker labels examples according to their own criteria. Although it has been extensively studied in the binary case, its behavior with multiple classes is not completely clear, specifically when annotations are biased. This paper attempts to fill that gap. The behavior of the majority voting strategy is studied in-depth in multi-class domains, emphasizing the effect of annotation bias. By means of a complete experimental setting, we show the limitations of the standard majority voting strategy. The use of three simple techniques that infer global information from the annotations and annotators allows us to put the performance of the majority voting strategy in context.

A Rapid Hybrid Clustering Algorithm for Large Volumes of High Dimensional Data

Abstract: Clustering large volumes of high-dimensional data is a challenging task. Many clustering algorithms have been developed to address either handling datasets with a very large sample size or with a very high number of dimensions, but they are often impractical when the data is large in both aspects. To simultaneously overcome both the ‘curse of dimensionality’ problem due to high dimensions and scalability problems due to large sample size, we propose a new fast clustering algorithm called FensiVAT. FensiVAT is a hybrid, ensemble-based clustering algorithm which uses fast data-space reduction and an intelligent sampling strategy. In addition to clustering, FensiVAT also provides visual evidence that is used to estimate the number of clusters (cluster tendency assessment) in the data. In our experiments, we compare FensiVAT with nine state-of-the-art approaches which are popular for large sample size or high-dimensional data clustering. Experimental results suggest that FensiVAT, which can cluster large volumes of high-dimensional datasets in a few seconds, is the fastest and most accurate method of the ones tested.