Search

Periodicity is a frequently happening phenomenon for social interactions in temporal networks. Mining periodic communities are essential to understanding periodic group behaviors in temporal networks. Unfortunately, most previous studies for community mining in temporal networks ignore the periodic patterns of communities. In this paper, we study the problem of seeking periodic communities in a temporal network, where each edge is associated with a set of timestamps. We propose novel models, including $\sigma$ σ -periodic $k$ k -core and $\sigma$ σ -periodic $k$ k -clique, that represent periodic communities in temporal networks. Specifically, a $\sigma$ σ -periodic $k$ k -core (or $\sigma$ σ -periodic $k$ k -clique) is a $k$ k -core (or clique with size larger than $k$ k ) that appears at least $\sigma$ σ times periodically in the temporal graph. The problem of searching periodic core is efficient but the resulting communities may be not enough cohesive; the problem of enumerating all periodic cliques is not efficient (NP-hard) but the resulting communities are very cohesive. To compute all of them efficiently, we first develop two effective graph reduction techniques to significantly prune the temporal graph. Then, we transform the temporal graph into a static graph and prove that mining the periodic communities in the temporal graph equals mining communities in the transformed graph. Subsequently, we propose a decomposition algorithm to search maximal $\sigma$ σ -periodic $k$ k -core, a Bron-Kerbosch style algorithm to enumerate all maximal $\sigma$ σ -periodic $k$ k -cliques, and a branch-and-bound style algorithm to find the maximum $\sigma$ σ -periodic clique. The results of extensive experiments on five real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]

A schedule-based system is a system that operates on or contains within a schedule of events and breaks at particular time intervals. Entities within the system show presence or absence in these events by entering or exiting the locations of the events. Given radio frequency identification (RFID) data from a schedule-based system, what can we learn about the system (the events and entities) through data mining? Which data mining methods can be applied so that one can obtain rich actionable insights regarding the system and the domain? The research goal of this paper is to answer these posed research questions, through the development of a framework that systematically produces actionable insights for a given schedule-based system. We show that through integrating appropriate data mining methodologies as a unified framework, one can obtain many insights from even a very simple RFID dataset, which contains only very few fields. The developed framework is general, and is applicable to any schedule-based system, as long as it operates under certain basic assumptions. The types of insights are also general, and are formulated in this paper in the most abstract way. The applicability of the developed framework is illustrated through a case study, where real world data from a schedule-based system is analyzed using the introduced framework. Insights obtained include the profiling of entities and events, the interactions between entity and events, and the relations between events. [ABSTRACT FROM AUTHOR]

Visually analyzing citation networks poses challenges to many fields of the data mining research. How can we summarize a large citation graph according to the user’s interest? In particular, how can we illustrate the impact of a highly influential paper through the summarization? Can we maintain the sensory node-link graph structure while revealing the flow-based influence patterns and preserving a fine readability? The state-of-the-art influence maximization algorithms can detect the most influential node in a citation network, but fail to summarize a graph structure to account for its influence. On the other hand, existing graph summarization methods fold large graphs into clustered views, but can not reveal the hidden influence patterns underneath the citation network. In this paper, we first formally define the Influence Graph Summarization problem on citation networks. Second, we propose a matrix decomposition based algorithm pipeline to solve the IGS problem. Our method can not only highlight the flow-based influence patterns, but also easily extend to support the rich attribute information. A prototype system called VEGAS implementing this pipeline is also developed. Third, we present a theoretical analysis on our main algorithm, which is equivalent to the kernel k-mean clustering. It can be proved that the matrix decomposition based algorithm can approximate the objective of the proposed IGS problem. Last, we conduct comprehensive experiments with real-world citation networks to compare the proposed algorithm with classical graph summarization methods. Evaluation results demonstrate that our method significantly outperforms the previous ones in optimizing both the quantitative IGS objective and the quality of the visual summarizations. [ABSTRACT FROM PUBLISHER]

Hyperspectral image (HSI) clustering is a challenging task due to the complex characteristics in HSI data, such as spatial-spectral structure, high-dimension, and large spectral variability. In this paper, we propose a novel deep spatial-spectral subspace clustering network (DS3C-Net), which explores spatial-spectral information via the multi-scale auto-encoder and collaborative constraint. Considering the structure correlations of HSI, the multi-scale auto-encoder is first designed to extract spatial-spectral features with different-scale pixel blocks which are selected as the inputs. Then, the collaborative constrained self-expressive layers are introduced between the encoder and decoder, to capture the self-expressive subspace structures. By designing a self-expressiveness similarity constraint, the proposed network is trained collaboratively, and the affinity matrices of the feature representation are learned in an end-to-end manner. Based on the affinity matrices, the spectral clustering algorithm is utilized to obtain the final HSI clustering result. Experimental results on three widely used hyperspectral image datasets demonstrate that the proposed method outperforms state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Many time series data mining problems can be solved with repeated use of distance measure. Examples of such tasks include similarity search, clustering, classification, anomaly detection and segmentation. For over two decades it has been known that the Dynamic Time Warping (DTW) distance measure is the best measure to use for most tasks, in most domains. Because the classic DTW algorithm has quadratic time complexity, many ideas have been introduced to reduce its amortized time, or to quickly approximate it. One of the most cited approximate approaches is FastDTW. The FastDTW algorithm has well over a thousand citations and has been explicitly used in several hundred research efforts. In this work, we make a surprising claim. In any realistic data mining application, the approximate FastDTW is much slower than the exact DTW. This fact clearly has implications for the community that uses this algorithm: allowing it to address much larger datasets, get exact results, and do so in less time. [ABSTRACT FROM AUTHOR]

Sparse modeling representative selection (SMRS) has been recently introduced for selecting the most relevant examples in data sets. SMRS exploits data self-representativeness coding in order to infer a coding matrix with block sparsity constraint. The relevance scores of samples are then derived from the estimated matrix of coefficients. Since SMRS is based on a linear model for data self-representation, it cannot always provide good relevant samples. Besides, most of its selected samples can be found in dense areas in input space. In this paper, we propose to overcome the SMRS method’s shortcomings that are related to the coding matrix estimation. We introduce two nonlinear data self-representativeness coding schemes that are based on Hilbert space and column generation. Experimental evaluation is carried out on summarizing a video movie and on summarizing training image data sets used for classification tasks. These experiments demonstrated that the proposed nonlinear methods can outperform state-of-the art selection methods. [ABSTRACT FROM AUTHOR]

This paper formulates a multi-graph learning task. In our problem setting, a bag contains a number of graphs and a class label. A bag is labeled positive if at least one graph in the bag is positive, and negative otherwise. In addition, the genuine label of each graph in a positive bag is unknown, and all graphs in a negative bag are negative. The aim of multi-graph learning is to build a learning model from a number of labeled training bags to predict previously unseen test bags with maximum accuracy. This problem setting is essentially different from existing multi-instance learning (MIL), where instances in MIL share well-defined feature values, but no features are available to represent graphs in a multi-graph bag. To solve the problem, we propose a Multi-Graph Feature based Learning ( gMGFL) algorithm that explores and selects a set of discriminative subgraphs as features to transfer each bag into a single instance, with the bag label being propagated to the transferred instance. As a result, the multi-graph bags form a labeled training instance set, so generic learning algorithms, such as decision trees, can be used to derive learning models for multi-graph classification. Experiments and comparisons on real-world multi-graph tasks demonstrate the algorithm performance. [ABSTRACT FROM AUTHOR]

Accurate and efficient methods for large-scale urban reconstruction are of significant importance to the computer vision and computer graphics communities. Although rapid acquisition techniques such as airborne LiDAR have been around for many years, creating a useful and functional virtual environment from such data remains difficult and labor intensive. This is due largely to the necessity in present solutions for data dependent user defined parameters. In this paper we present a new solution for automatically converting large LiDAR data pointcloud into simplified polygonal 3D models. The data is first divided into smaller components which are processed independently and concurrently to extract various metrics about the points. Next, the extracted information is converted into tensors. A robust agglomerate clustering algorithm is proposed to segment the tensors into clusters representing geospatial objects e.g., roads, buildings, etc. Unlike previous methods, the proposed tensor clustering process has no data dependencies and does not require any user-defined parameter. The required parameters are adaptively computed assuming a Weibull distribution for similarity distances. Lastly, to extract boundaries from the clusters a new multi-stage boundary refinement process is developed by reformulating this extraction as a global optimization problem. We have extensively tested our methods on several pointcloud datasets of different resolutions which exhibit significant variability in geospatial characteristics e.g., ground surface inclination, building density, etc and the results are reported. The source code for both tensor clustering and global boundary refinement will be made publicly available with the publication on the author's website. [ABSTRACT FROM AUTHOR]

Revealing complex relations between entities (e.g., items within or between transactions) is of great significance for business optimization, prediction, and decision making. Such relations include not only co-occurrence-based explicit relations but also nonco-occurrence-based implicit ones. Explicit relations have been substantially studied by rule mining-based approaches, including association rule mining and causal rule discovery. In contrast, implicit relations have received much less attention but could be more actionable. In this paper, we focus on the implicit relations between items which rarely or never co-occur while each of them co-occurs with other identical items (link items) with a high probability. A framework integrates both explicit and hidden item dependencies and a corresponding efficient algorithm IRRMiner captures such implicit relations with implicit rule inference. Experimental results show that IRRMiner not only infers implicit rules of various sizes consisting of both frequent and infrequent items effectively, it also runs at least four times faster than IARMiner, a typical indirect association rule mining algorithm which can only mine size-2 indirect association rules between frequent items. IRRMiner is applied to make recommendations and shows that the identified implicit rules can increase recommendation reliability. [ABSTRACT FROM AUTHOR]

Grid condition information extraction is very important for converter control systems in order to perform special functionalities, especially grid support during low voltage ride through (LVRT). As a part of grid condition detection, the voltage sag detection provides information about the start of a fault and obtains indices that determine the behavior of the whole control system of the converter during a fault. Estimation of the magnitude of voltage sag (MoVS) is essential for obtaining proper grid support. This paper presents an algorithm for MoVS (as defined in IEEE Std 1564-2014) prediction. The existence of correlation between magnitudes of a set of low-order harmonics during the transient of voltage PQ events with MoVS is for the first time determined and statistically proved. Correlation is mathematically formulated and the prediction function is obtained on the basis of real grid measurements. Complete algorithm for magnitude prediction is explained, and its possible application in distributed generation control is prese-nted. It is shown that significant time gain is achieved, which may be used as an additional benefit in LVRT operation. [ABSTRACT FROM AUTHOR]

The ability of an algorithm to extract power quality parameters on a low-end digital controller with constrained resources and computational capacity can promote comprehensive adoption of power quality control and monitoring infrastructure because of reduced cost and thus improve operational ability in a microgrid or distribution grid and support more in-depth integration of renewable energy. Since conventional harmonic extraction for single-phase grid mostly operate on Fourier transform, lock-in amplifier and their derivative algorithms, they demand large memory and computational power which are available with high-end application-specific processors, digital signal processors (DSPs) and field programmable gate arrays (FPGAs). In this paper, a computationally efficient harmonic extraction algorithm is proposed, which can be implemented on commercially available microcontrollers with ease, without compromising accuracy. A detailed theoretical analysis of the proposed method, along with various simulation and the experimental results are presented. Workarounds for minor implementation issues on digital controllers are discussed as well. [ABSTRACT FROM AUTHOR]

A large-scale deployment of phasor measurement units (PMUs) that reveal the inherent physical laws of power systems from a data perspective enables an enhanced awareness of power system operation. However, the high-granularity and non-stationary nature of PMU data and imperfect data quality could bring great technical challenges for real-time system event identification. To address these challenges, this paper proposes a two-stage learning-based framework. In the first stage, a Markov transition field (MTF) algorithm is exploited to extract the latent data features by encoding temporal dependency and transition statistics of PMU data in graphs. Then, a spatial pyramid pooling (SPP)-aided convolutional neural network (CNN) is established to efficiently and accurately identify power events. The proposed method fully builds on and is also tested on a large real-world dataset from several tens of PMU sources (and the corresponding event logs), located across the U.S., with a time span of two consecutive years. The numerical results validate that our method has high identification accuracy while showing good robustness against poor data quality. [ABSTRACT FROM AUTHOR]

We compile baselines, along with dataset split, for multimodal sentiment analysis. In this paper, we explore three different deep-learning-based architectures for multimodal sentiment classification, each improving upon the previous. Further, we evaluate these architectures with multiple datasets with fixed train/test partition. We also discuss some major issues, frequently ignored in multimodal sentiment analysis research, e.g., the role of speaker-exclusive models, the importance of different modalities, and generalizability. This framework illustrates the different facets of analysis to be considered while performing multimodal sentiment analysis and, hence, serves as a new benchmark for future research in this emerging field. [ABSTRACT FROM AUTHOR]

Intangible Cultural Heritage (ICH) creations include, amongst other, music, dance, singing, theatre, human skills, and craftsmanship. These cultural expressions are usually transmitted orally and/or using gestures and are modified over a period of time, through a process of collective recreation. As the world becomes more interconnected and many different cultures come into contact, local communities run the risk of losing important elements of their ICH, while young people find it difficult to maintain the connection with the cultural heritage treasured by their elders. In this paper, we present a novel holistic approach for the safeguarding and transmission of ICH that goes beyond the mere digitization of ICH content. Based on multisensory technology for the capturing of ICH, the proposed approach enables the generation of completely novel cultural content. High-level semantics are extracted from the acquired data, enabling researchers to identify possible implicit or hidden correlations between different ICH expressions or interpretation styles and study the evolution of a specific ICH. These data, coupled with other cultural resources, are accessible through the i-Treasures Web-platform, which provides the means for supporting knowledge exchange between researchers as well as know-how transmission from ICH bearers to apprentices. [ABSTRACT FROM AUTHOR]

This paper presents a dynamic predictive-optimization framework of a nonlinear temporal process. Data-mining (DM) and evolutionary strategy algorithms are integrated in the framework for solving the optimization model. DM algorithms learn dynamic equations from the process data. An evolutionary strategy algorithm is then applied to solve the optimization problem guided by the knowledge extracted by the DM algorithm. The concept presented in this paper is illustrated with the data from a power plant, where the goal is to maximize the boiler efficiency and minimize the limestone consumption. This multiobjective optimization problem can be either transformed into a single-objective optimization problem through preference aggregation approaches or into a Pareto-optimal optimization problem. The computational results have shown the effectiveness of the proposed optimization framework. [ABSTRACT FROM AUTHOR]

Class imbalance is a problem that is common to many application domains. When examples of one class in a training data set vastly outnumber examples of the other class(es), traditional data mining algorithms tend to create suboptimal classification models. Several techniques have been used to alleviate the problem of class imbalance, including data sampling and boosting. In this paper, we present a new hybrid sampling/boosting algorithm, called RUSBoost, for learning from skewed training data. This algorithm provides a simpler and faster alternative to SMOTEBoost, which is another algorithm that combines boosting and data sampling. This paper evaluates the performances of RUSBoost and SMOTEBoost, as well as their individual components (random undersampling, synthetic minority oversampling technique, and AdaBoost). We conduct experiments using 15 data sets from various application domains, four base learners, and four evaluation metrics. RUSBoost and SMOTEBoost both outperform the other procedures, and RUSBoost performs comparably to (and often better than) SMOTEBoost while being a simpler and faster technique. Given these experimental results, we highly recommend RUSBoost as an attractive alternative for improving the classification performance of learners built using imbalanced data. [ABSTRACT FROM AUTHOR]

In this paper, we present a subcategory-aware recognition framework to boost category level object classification performance. Different from the existing monolithic model approaches, we aim to automatically leverage the embedded subcategory structure to assist the further category level recognition. Motivated by the observation of considerable intra-class diversities and inter-class ambiguities in many current object classification data sets, we explicitly split data into subcategories by ambiguity-guided subcategory mining. The resulting subcategories are seamlessly integrated into the state-of-the-art detection-assisted classification framework. In particular, we build the instance affinity graph by combining both intra-class similarity and inter-class ambiguity. Visual subcategories, which correspond to the dense subgraphs, are detected by the graph shift algorithm. We then train an individual model for each subcategory rather than an attempt to represent an object category with a monolithic model. Related samples, which are informative for subcategory classification, are utilized to regularize each subcategory model. Finally, the responses from subcategory models are aggregated by subcategory-aware kernel regression. The extensive experiments over the PASCAL visual object challenge (VOC) 2007 and PASCAL VOC 2010 databases show the state-of-the-art performance from our framework. [ABSTRACT FROM PUBLISHER]

Spatial co-location patterns are subsets of spatial features usually located together in geographic space. Recent literature has provided different approaches to discover co-location patterns over point spatial data. However, most approaches consider the neighborhood relationship among spatial objects as binary and are mainly designed for point spatial features, thus are not appropriate for extended spatial features such as line strings and polygons, the neighborhood relationship among which is naturally continuous. This paper adopts a buffer-based model for measuring the spatial relationship of extended objects and mining co-location patterns. While the buffer-based model has several advantages for extended spatial features, it involves high computational complexity due to the expensive buffer-level overlay operation. To tackle this challenge, we introduce a coarse-level co-location mining framework, which follows a filter-and-refine paradigm. Within the framework, we develop a serious of rigorous upper bounds based on geometric property and progressively prune search space with these upper bounds. Moreover, we develop a join-less schema to further reduce computation cost of size-k(k > 2) co-location patterns. Finally, we conduct experiments with large-scale spatial data to validate the efficiency of the developed algorithms against several state-of-art methods. All experimental results demonstrate the superiority of our methods. [ABSTRACT FROM AUTHOR]

A novel primary object discovery (POD) algorithm, which uses reliable object proposals while exploiting the recurrence property of a primary object in a video sequence, is proposed in this paper. First, we generate both color-based and motion-based object proposals in each frame, and extract the feature of each proposal using the random walk with restart simulation. Next, we estimate the foreground confidence for each proposal to remove unreliable proposals. By superposing the features of the remaining reliable proposals, we construct the primary object models. To this end, we develop the evolutionary primary object modeling technique, which exploits the recurrence property of the primary object. Then, using the primary object models, we choose the main proposal in each frame and find the location of the primary object by merging the main proposal with candidate proposals selectively. Finally, we refine the discovered bounding boxes by exploiting temporal correlations of the recurring primary object. Extensive experimental results demonstrate that the proposed POD algorithm significantly outperforms conventional algorithms. [ABSTRACT FROM PUBLISHER]

Twitter sentiment analysis has become a hot research topic in recent years. Most of existing solutions to Twitter sentiment analysis basically only consider textual information of Twitter messages, and struggle to perform well when facing short and ambiguous Twitter messages. Recent studies show that sentiment diffusion patterns on Twitter have close relationships with sentiment polarities of Twitter messages. Therefore, in this paper, we focus on how to fuse textual information of Twitter messages and sentiment diffusion patterns to obtain better performance of sentiment analysis on Twitter data. To this end, we first analyze sentiment diffusion by investigating a phenomenon called sentiment reversal, and find some interesting properties of sentiment reversals. Then, we consider the inter-relationships between textual information of Twitter messages and sentiment diffusion patterns, and propose an iterative algorithm called SentiDiff to predict sentiment polarities expressed in Twitter messages. To the best of our knowledge, this work is the first to utilize sentiment diffusion patterns to help improve Twitter sentiment analysis. Extensive experiments on real-world dataset demonstrate that compared with state-of-the-art textual information based sentiment analysis algorithms, our proposed algorithm yields PR-AUC improvements between 5.09 and 8.38 percent on Twitter sentiment classification tasks. [ABSTRACT FROM AUTHOR]

A method to find the minimized state machine cover of live and safe Petri nets (PNs) is proposed in this paper. It is required that a cover be obtained in some implementation methods of PN-based control algorithms and other applications such as data mining. Most of the known methods of its computation have at least exponential time and space complexity; this is true not only for the methods which guarantee a minimal cover is obtained but also for some methods of finding approximate solutions. The proposed algorithm is an approximation algorithm and has polynomial computational complexity. The experimental verification shows a very high efficiency of the presented technique. The proposed method is especially valuable in the case of large systems where a solution is obtained hundreds of times quicker than by other methods. [ABSTRACT FROM AUTHOR]

In an $(H,r)$ combination network, a single content library is serving for ${\binom{H}{ r}}$ users through $H$ relays, where each user has local cache memories and simultaneously accesses a subset of $r$ relays on orthogonal non-interfering and error-free channels. The combinatorial placement delivery array (CPDA in short) can be used to realize a coded caching scheme for combination networks. In this paper, a new algorithm used to realize a scheme for combination networks based on a CPDA is proposed. Based on the fixed CPDA, the scheme realized by our algorithm has smaller subpacketization. Then we focus on directly constructing CPDAs for any positive integers $H$ and $r$ with $r< H$ and obtain two new classes of CPDAs. Compared with the previously known CPDAs, the schemes realized by our CPDAs have significant advantages on the subpacketization levels with some costing of transmission rates. [ABSTRACT FROM AUTHOR]

Some methods developed in reversible data hiding (RDH) make use of prediction for data embedding for original pixel estimation. Predicators may also be exploited in RDH in encrypted image (RDHEI); this has become a research interest in recent years because of the development of cloud computing and a need for content owner privacy. This paper presents a high-capacity reversible data hiding in encrypted image (RDHEI) that employs local difference predictor. In this algorithm, an image is divided into non-overlapping blocks. In each block, the central pixel of the block is considered as the leader pixel and others as follower ones. The prediction errors between the intensity of the follower pixels and leader one are calculated using local difference predictor and analyzed to determine a label for block embedding capacity. This label indicates the amount of data that can be embedded in a block after encryption. Using this pre-processing for all blocks, we vacate rooms before the encryption of the original image to achieve high embedding capacity. Also, using these labels, embedded data is extracted and the original image is losslessly reconstructed at the decoding phase. Comparing to existent RDHEI algorithms, not only embedding capacity is increased by the proposed algorithm, but also a perfect reconstruction of the original image is realized by content owner without having data hider key. Experimental results confirm that the proposed algorithm outperforms state of the art RDHEI methods. [ABSTRACT FROM AUTHOR]

The low-rank matrix completion problem is fundamental to a number of tasks in data mining, machine learning, and signal processing. This paper considers the problem of adaptive matrix completion in time-varying scenarios. Given a sequence of incomplete and noise-corrupted matrices, the goal is to recover and track the underlying low rank matrices. Motivated from the classical least-mean square (LMS) algorithms for adaptive filtering, three LMS-like algorithms are proposed for estimating and tracking low-rank matrices. Performance of the proposed algorithms is provided in form of nonasymptotic bounds on the tracking mean-square error. Tracking performance of the algorithms is also studied via detailed simulations over real-world datasets. [ABSTRACT FROM PUBLISHER]

A Sequence OLAP (S-OLAP) system provides a platform on which pattern-based aggregate (PBA) queries on a sequence database are evaluated. In its simplest form, a PBA query consists of a pattern template $T$ and an aggregate function $F$ . A pattern template is a sequence of variables, each is defined over a domain. Each variable is instantiated with all possible values in its corresponding domain to derive all possible patterns of the template. Sequences are grouped based on the patterns they possess. The answer to a PBA query is a sequence cuboid (s-cuboid), which is a multidimensional array of cells. Each cell is associated with a pattern instantiated from the query's pattern template. The value of each s-cuboid cell is obtained by applying the aggregate function $F$ to the set of data sequences that belong to that cell. Since a pattern template can involve many variables and can be arbitrarily long, the induced s-cuboid for a PBA query can be huge. For most analytical tasks, however, only iceberg cells with very large aggregate values are of interest. This paper proposes an efficient approach to identifying and evaluating iceberg cells of s-cuboids. Experimental results show that our algorithms are orders of magnitude faster than existing approaches. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of mining frequent sequences under the rigorous differential privacy model. We explore the possibility of designing a differentially private frequent sequence mining (FSM) algorithm which can achieve both high data utility and a high degree of privacy. We found, in differentially private FSM, the amount of required noise is proportionate to the number of candidate sequences. If we could effectively prune those unpromising candidate sequences, the utility and privacy tradeoff can be significantly improved. To this end, by leveraging a sampling-based candidate pruning technique, we propose PFS $^2$, a novel differentially private FSM algorithm. It is the first algorithm that supports the general gap-constrained FSM in the context of differential privacy. The gap constraints in FSM can be used to limit the mining results to a controlled set of frequent sequences. In our PFS$^2$ algorithm, the core is to utilize sample databases to prune the candidate sequences generated based on the downward closure property. In particular, we use the noisy local support of candidate sequences in the sample databases to estimate which candidate sequences are potentially frequent. To improve the accuracy of such private estimations, a gap-aware sequence shrinking method is proposed to enforce the length constraint on the sample databases. Moreover, to calibrate the amount of noise required by differential privacy, a gap-aware sensitivity computation method is proposed to obtain the sensitivity of the local support computations with different gap constraints. Furthermore, to decrease the probability of misestimating frequent sequences as infrequent, a threshold relaxation method is proposed to relax the user-specified threshold for the sample databases. Through formal privacy analysis, we show that our PFS $^2$ algorithm is $\epsilon$ -differentially private. Extensive experiments on real datasets illustrate that our PFS$^2$ algorithm can privately find frequent sequences with high accuracy. [ABSTRACT FROM PUBLISHER]

In this paper, we study a new problem of continuous learning from doubly-streaming data where both data volume and feature space increase over time. We refer to the doubly-streaming data as trapezoidal data streams and the corresponding learning problem as online learning from trapezoidal data streams. The problem is challenging because both data volume and data dimension increase over time, and existing online learning [1] , [2] , online feature selection [3] , and streaming feature selection algorithms [4] , [5] are inapplicable. We propose a new Online Learning with Streaming Features algorithm (OLSF for short) and its two variants, which combine online learning [1] , [2] and streaming feature selection [4] , [5] to enable learning from trapezoidal data streams with infinite training instances and features. When a new training instance carrying new features arrives, a classifier updates the existing features by following the passive-aggressive update rule [2] and updates the new features by following the structural risk minimization principle. Feature sparsity is then introduced by using the projected truncation technique. We derive performance bounds of the OLSF algorithm and its variants. We also conduct experiments on real-world data sets to show the performance of the proposed algorithms. [ABSTRACT FROM PUBLISHER]

Crowdedness spot is a crowded area with an abnormal number of objects. Detecting the crowdedness spots of moving vehicles in an urban area is essential to many applications. An intuitive method is to cluster the objects in areas to get the density information. Unfortunately, the data capturing vehicle mobility possesses some new features, such as highly mobile environments, supremely limited size of sample objects, and nonuniform biased samples, and all these features have raised new challenges that make traditional density-based clustering algorithms fail to retrieve the real clustering property of objects, making the results less meaningful. In this paper, we propose a novel nondensity-based approach called mobility-based clustering. The key idea is that sample objects are employed as “sensors” to perceive the vehicle crowdedness in nearby areas using their instant mobility rather than the “object representatives.” As such, the mobility of samples is naturally incorporated. Several key factors beyond the vehicle crowdedness have been identified, and techniques to compensate these effects are accordingly proposed. Furthermore, taking the detected crowdedness spots as a label of the taxi, we can identify one particular taxi to be a crowdedness taxi that crosses a number of different crowdedness spots. We evaluate the performance of our methods and baseline approaches based on real traffic situations (to retrieve the real traffic crowdedness) and real-life data sets. Finally, the interesting findings are provided for further discussions. [ABSTRACT FROM PUBLISHER]

Discretization is an essential preprocessing technique used in many knowledge discovery and data mining tasks. Its main goal is to transform a set of continuous attributes into discrete ones, by associating categorical values to intervals and thus transforming quantitative data into qualitative data. In this manner, symbolic data mining algorithms can be applied over continuous data and the representation of information is simplified, making it more concise and specific. The literature provides numerous proposals of discretization and some attempts to categorize them into a taxonomy can be found. However, in previous papers, there is a lack of consensus in the definition of the properties and no formal categorization has been established yet, which may be confusing for practitioners. Furthermore, only a small set of discretizers have been widely considered, while many other methods have gone unnoticed. With the intention of alleviating these problems, this paper provides a survey of discretization methods proposed in the literature from a theoretical and empirical perspective. From the theoretical perspective, we develop a taxonomy based on the main properties pointed out in previous research, unifying the notation and including all the known methods up to date. Empirically, we conduct an experimental study in supervised classification involving the most representative and newest discretizers, different types of classifiers, and a large number of data sets. The results of their performances measured in terms of accuracy, number of intervals, and inconsistency have been verified by means of nonparametric statistical tests. Additionally, a set of discretizers are highlighted as the best performing ones. [ABSTRACT FROM AUTHOR]

Role assignment is a critical task in role-based collaboration. It has three steps, i.e., agent evaluation, group role assignment, and role transfer, where group role assignment is a time-consuming process. This paper clarifies the group role assignment problem (GRAP), describes a general assignment problem (GAP), converts a GRAP to a GAP, proposes an efficient algorithm based on the Kuhn–Munkres (K-M) algorithm, conducts numerical experiments, and analyzes the solutions' performances. The results show that the proposed algorithm significantly improves the algorithm based on exhaustive search. The major contributions of this paper include formally defining the GRAPs, giving a general efficient solution for them, and expanding the application scope of the K-M algorithm. This paper offers an efficient enough solution based on the K-M algorithm that outperforms significantly the exhaustive search approach. [ABSTRACT FROM PUBLISHER]

This paper compares the performance of several boosting and bagging techniques in the context of learning from imbalanced and noisy binary-class data. Noise and class imbalance are two well-established data characteristics encountered in a wide range of data mining and machine learning initiatives. The learning algorithms studied in this paper, which include SMOTEBoost, RUSBoost, Exactly Balanced Bagging, and Roughly Balanced Bagging, combine boosting or bagging with data sampling to make them more effective when data are imbalanced. These techniques are evaluated in a comprehensive suite of experiments, for which nearly four million classification models were trained. All classifiers are assessed using seven different performance metrics, providing a complete perspective on the performance of these techniques, and results are tested for statistical significance via analysis-of-variance modeling. The experiments show that the bagging techniques generally outperform boosting, and hence in noisy data environments, bagging is the preferred method for handling class imbalance. [ABSTRACT FROM PUBLISHER]

In many real applications, graph data is subject to uncertainties due to incompleteness and imprecision of data. Mining such uncertain graph data is semantically different from and computationally more challenging than mining conventional exact graph data. This paper investigates the problem of mining uncertain graph data and especially focuses on mining frequent subgraph patterns on an uncertain graph database. A novel model of uncertain graphs is presented, and the frequent subgraph pattern mining problem is formalized by introducing a new measure, called expected support. This problem is proved to be NP-hard. An approximate mining algorithm is proposed to find a set of approximately frequent subgraph patterns by allowing an error tolerance on expected supports of discovered subgraph patterns. The algorithm uses efficient methods to determine whether a subgraph pattern can be output or not and a new pruning method to reduce the complexity of examining subgraph patterns. Analytical and experimental results show that the algorithm is very efficient, accurate, and scalable for large uncertain graph databases. To the best of our knowledge, this paper is the first one to investigate the problem of mining frequent subgraph patterns from uncertain graph data. [ABSTRACT FROM AUTHOR]

In this paper, we first study an important but unsolved dilemma in the literature of subspace clustering, which is referred to as "information overlapping-data coverage" challenge. Current solutions of subspace clustering usually invoke a grid-based Apriori-like procedure to identify dense regions and construct subspace clusters afterward. Due to the nature of monotonicity property in Apriori- like procedures, it is inherent that if a region is identified as dense, all its projected regions are also identified as dense, causing overlapping/redundant clustering information to be inevitably reported to users when generating clusters from such highly correlated regions. However, naive methods to filter redundant clusters will incur a challenging problem in the other side of the dilemma, called the "data coverage" issue. Note that two clusters may have highly correlated dense regions but their data members could be highly different to each other. Arbitrarily removing one of them may lose the coverage of data with clustering information, thus likely reporting an incomplete and biased clustering result. In this paper, therefore, we further propose an innovative algorithm, called "NOnRedundant Subspace Cluster mining" (NORSC), to efficiently discover a succinct collection of subspace clusters while also maintaining the required degree of data coverage. NORSC not only avoids generating the redundant clusters with most of the contained data covered by higher dimensional clusters to resolve the information overlapping problem but also limits the information loss to cope with the data coverage problem. As shown by our experimental results, NORSC is very effective in identifying a concise and small set of subspace clusters, while incurring time complexity in orders of magnitude better than that of previous works. [ABSTRACT FROM AUTHOR]

The concept of anticipatory control applied to wind turbines is presented. Anticipatory control is based on the model predictive control (MPC) approach. Unlike the MPC method, non-controllable variables (such as wind speed) are directly considered in the dynamic equations presented in the paper to predict response variables, e.g., rotor speed and turbine power output. To determine future states of the power drive with the dynamic equations, a time series model was built for wind speed. The time series model was fused with the dynamic equations to predict the response variables over a certain prediction horizon. Based on these predictions, an optimization model was solved to find the optimal control settings to improve the power output without incurring large rotor speed changes. As both the dynamic equations and time series model were built by data mining algorithms, no gradient information is available. A modified evolutionary strategy algorithm was used to solve a nonlinear constrained optimization problem. The proposed approach has been tested on the data collected from a 1.5 MW wind turbine. [ABSTRACT FROM AUTHOR]

One-versus-all (OVA) classifiers learn κ individual binary classifiers, each distinguishing the instances of a single class from the instances of all other classes. To classify a new instance, the κ classifiers are run, and the one that returns the highest confidence is chosen. Thus, OVA is different from existing data stream classification schemes whose majority use multiclass classifiers, each discriminating among all the classes. This paper advocates some outstanding advantages of OVA for data stream classification. First, there is low error correlation and, hence, high diversity among OVA's component classifiers, which leads to high classification accuracy. Second, OVA is adept at accommodating new class labels that often appear in data streams. However, there also remain many challenges to deploy traditional OVA for classifying data streams. First, traditional OVA does not handle concept change, a key feature of data streams. Second, as every instance is fed to all component classifiers, OVA is known as an inefficient model. Third, OVA's classification accuracy is adversely affected by the imbalanced class distributions in data streams. This paper addresses those key challenges and consequently proposes a new OVA scheme that is adapted for data stream classification. Theoretical analysis and empirical evidence reveal that the adapted OVA can offer faster training, faster updating, and higher classification accuracy than many existing popular data stream classification algorithms. We expect these results to be of interest to researchers and practitioners because they suggest a simple but very elegant and effective alternative to existing classification schemes for data streams. [ABSTRACT FROM AUTHOR]

To efficiently and effectively mine massive amounts of data in the time series, approximate representation of the data is one of the most commonly used strategies. Piecewise Linear Approximation is such an approach, which represents a time series by dividing it into segments and approximating each segment with a straight line. In this paper, we first propose a new segmentation criterion that improves computing efficiency. Based on this criterion, two novel online piecewise linear segmentation methods are developed, the feasible space window method and the stepwise feasible space window method. The former usually produces much fewer segments and is faster and more reliable in the runtime than other methods. The latter can reduce the representation error with fewer segments. It achieves the best overall performance on the segmentation results compared with other methods. Extensive experiments on a variety of real-world time series have been conducted to demonstrate the advantages of our methods. [ABSTRACT FROM AUTHOR]

In many practical data mining applications such as text classification, unlabeled training examples are readily available, but labeled ones are fairly expensive to obtain. Therefore, semisupervised learning algorithms have aroused considerable interests from the data mining and machine learning fields. In recent years, graph-based semisupervised learning has been becoming one of the most active research areas in the semisupervised learning community. In this paper, a novel graph-based semisupervised learning approach is proposed based on a linear neighborhood model, which assumes that each data point can be linearly reconstructed from its neighborhood. Our algorithm, named Linear Neighborhood Propagation (LNP), can propagate the labels from the labeled points to the whole data set using these linear neighborhoods with sufficient smoothness. A theoretical analysis of the properties of LNP is presented in this paper. Furthermore, we also derive an easy way to extend LNP to out-of-sample data. Promising experimental results are presented for synthetic data, digit, and text classification tasks. [ABSTRACT FROM AUTHOR]

Maximal biclique (also known as complete bipartite) subgraphs can model many applications in Web mining, business, and bioinformatics. Enumerating maximal biclique subgraphs from a graph is a computationally challenging problem, as the size of the output can become exponentially large with respect to the vertex number when the graph grows. In this paper, we efficiently enumerate them through the use of closed patterns of the adjacency matrix of the graph. For an undirected graph G without self-loops, we prove that 1) the number of closed patterns in the adjacency matrix of G is even, 2) the number of the closed patterns is precisely double the number of maximal biclique subgraphs of G, and 3) for every maximal biclique subgraph, there always exists a unique pair of closed patterns that matches the two vertex sets of the subgraph. Therefore, the problem of enumerating maximal bicliques can be solved by using efficient algorithms for mining closed patterns, which are algorithms extensively studied in the data mining field. However, this direct use of existing algorithms causes a duplicated enumeration. To achieve high efficiency, we propose an O(mn) time delay algorithm for a nonduplicated enumeration, in particular, for enumerating those maximal bicliques with a large size, where m and n are the number of edges and vertices of the graph, respectively. We evaluate the high efficiency of our algorithm by comparing it to state- of-the-art algorithms on three categories of graphs: randomly generated graphs, benchmarks, and a real-life protein interaction network. In this paper, we also prove that if self-loops are allowed in a graph, then the number of closed patterns in the adjacency matrix is not necessarily even, but the maximal bicliques are exactly the same as those of the graph after removing all the self-loops. [ABSTRACT FROM AUTHOR]

In multilabel learning, each instance in the training set is associated with a set of labels and the task is to output a label set whose size is unknown a priori for each unseen instance. In this paper, this problem is addressed in the way that a neural network algorithm named BP-MLL, i.e., Backpropagation for Multilabel Learning, is proposed. It is derived from the popular Backpropagation algorithm through employing a novel error function capturing the characteristics of multilabel learning, i.e., the labels belonging to an instance should be ranked higher than those not belonging to that instance. Applications to two real-world multilabel learning problems, i.e., functional genomics and text categorization, show that the performance of BP-MLL is superior to that of some well-established multilabel learning algorithms. [ABSTRACT FROM AUTHOR]

A shortcoming of univariate decision tree learners is that they do not learn intermediate concepts and select only one of the input features in the branching decision at each intermediate tree node. It has been empirically demonstrated that cascading other classification methods, which learn intermediate concepts, with decision tree learners can alleviate such representational bias of decision trees and potentially improve classification performance. However, a more complex model that fits training data belier may not necessarily perform better on unseen data, commonly referred to as the overfitting problem. To find the most appropriate degree of such cascade generalization, a decision forest (i.e., a set of decision trees with other classification models cascaded to different degrees) needs to be generated, from which the best decision tree can then be identified. In this paper, the authors pro- pose an efficient algorithm for generating such decision forests. The algorithm uses an extended decision tree data structure and constructs any node that is common to multiple decision trees only once. The authors have empirically evaluated the algorithm using 32 data sets for classification problems from the University of California, Irvine (UCI) machine learning repository and report on results demonstrating the efficiency of the algorithm in this paper. [ABSTRACT FROM AUTHOR]

The problem addressed in this paper is to discover the frequently occurred sequential patterns from databases. Although much work has been devoted to this subject, to the best of our knowledge, no previous research was able to find sequential patterns from d-dimensional sequence data, where d > 2. Without such a capability, many practical data would be impossible to mine. For example, an online stock-trading site may have a customer database, where each customer may visit a Web site in a series of days; each day takes a series of sessions and each session visits a series of Web pages. Then, the data for each customer forms a 3-dimensional list, where the first dimension is days, the second is sessions, and the third is visited pages. To mine sequential patterns from this kind of sequence data, two efficient algorithms have been developed in this paper. [ABSTRACT FROM AUTHOR]

In this paper, we explore a new problem of mining general temporal association rules in publication databases. In essence, a publication database is a set of transactions where each transaction T is a set of items of which each item contains an individual exhibition period. The current model of association rule mining is not able to handle the publication database due to the following fundamental problems, i.e., 1) lack of consideration of the exhibition period of each individual item and 2) lack of an equitable support counting basis for each item. To remedy this, we propose an innovative algorithm Progressive-Partition-Miner (abbreviated as PPM) to discover general temporal association rules in a publication database. The basic idea of PPM is to first partition the publication database in light of exhibition periods of items and then progressively accumulate the occurrence count of each candidate 2-itemset; based on the intrinsic partitioning characteristics. Algorithm PPM is also designed to employ a filtering threshold in each partition to early prune out those cumulatively infrequent 2-itemsets. The feature that the number of candidate 2-itemsets generated by PPM is very close to the number of frequent 2-itemsets allows us to employ the scan reduction technique to effectively reduce the number of database scans. Explicitly, the execution time of PPM is, in orders of magnitude, smaller than those required by other competitive schemes that are directly extended from existing methods. The correctness of PPM is proven and some of its theoretical properties are derived. Sensitivity analysis of various parameters is conducted to provide many insights into Algorithm PPM. [ABSTRACT FROM AUTHOR]

Textual documents created and distributed on the Internet are ever changing in various forms. Most of existing works are devoted to topic modeling and the evolution of individual topics, while sequential relations of topics in successive documents published by a specific user are ignored. In this paper, in order to characterize and detect personalized and abnormal behaviors of Internet users, we propose Sequential Topic Patterns (STPs) and formulate the problem of mining User-aware Rare Sequential Topic Patterns (URSTPs) in document streams on the Internet. They are rare on the whole but relatively frequent for specific users, so can be applied in many real-life scenarios, such as real-time monitoring on abnormal user behaviors. We present a group of algorithms to solve this innovative mining problem through three phases: preprocessing to extract probabilistic topics and identify sessions for different users, generating all the STP candidates with (expected) support values for each user by pattern-growth, and selecting URSTPs by making user-aware rarity analysis on derived STPs. Experiments on both real (Twitter) and synthetic datasets show that our approach can indeed discover special users and interpretable URSTPs effectively and efficiently, which significantly reflect users’ characteristics. [ABSTRACT FROM PUBLISHER]

Graph classification aims to learn models to classify structure data. To date, all existing graph classification methods are designed to target one single learning task and require a large number of labeled samples for learning good classification models. In reality, each real-world task may only have a limited number of labeled samples, yet multiple similar learning tasks can provide useful knowledge to benefit all tasks as a whole. In this paper, we formulate a new multi-task graph classification (MTG) problem, where multiple graph classification tasks are jointly regularized to find discriminative subgraphs shared by all tasks for learning. The niche of MTG stems from the fact that with a limited number of training samples, subgraph features selected for one single graph classification task tend to overfit the training data. By using additional tasks as evaluation sets, MTG can jointly regularize multiple tasks to explore high quality subgraph features for graph classification. To achieve this goal, we formulate an objective function which combines multiple graph classification tasks to evaluate the informativeness score of a subgraph feature. An iterative subgraph feature exploration and multi-task learning process is further proposed to incrementally select subgraph features for graph classification. Experiments on real-world multi-task graph classification datasets demonstrate significant performance gain. [ABSTRACT FROM PUBLISHER]

CANDECOMP/PARAFAC (CP) approximates multiway data by sum of rank-1 tensors. Unlike matrix decomposition, the procedure which estimates the best rank-R tensor approximation through R sequential best rank-1 approximations does not work for tensors, because the deflation does not always reduce the tensor rank. In this paper, we propose a novel deflation method for the problem. When one factor matrix of a rank-R CP decomposition is of full column rank, the decomposition can be performed through (R-1) rank-1 reductions. At each deflation stage, the residue tensor is constrained to have a reduced multilinear rank. For decomposition of order-3 tensors of size R\times R\times R and rank-R, estimation of one rank-1 tensor has a computational cost of \cal O(R^3) per iteration which is lower than the cost \cal O(R^4) of the ALS algorithm for the overall CP decomposition. The method can be extended to tracking one or a few rank-one tensors of slow changes, or inspect variations of common patterns in individual datasets. [ABSTRACT FROM PUBLISHER]

Training fault detection model requires advanced data-mining algorithms when the growth rate of the process data is notably high and normal-class data overwhelm fault-class data in number. Most standard classification algorithms, such as support vector machines (SVMs), can handle moderate sizes of training data and assume balanced class distributions. When the class sizes are highly imbalanced, the standard algorithms tend to strongly favor the majority class and provide a notably low detection of the minority class as a result. In this paper, we propose an online fault detection algorithm based on incremental clustering. The algorithm accurately finds wafer faults even in severe class distribution skews and efficiently processes massive sensor data in terms of reductions in the required storage. We tested our algorithm on illustrative examples and an industrial example. The algorithm performed well with the illustrative examples that included imbalanced class distributions of Gaussian and non-Gaussian types and process drifts. In the industrial example, which simulated real data from a plasma etcher, we verified that the performance of the algorithm was better than that of the standard SVM, one-class SVM and three instance-based fault detection algorithms that are typically used in the literature. [ABSTRACT FROM AUTHOR]

By the ordered tree inclusion we will check whether a pattern tree P can be included in a target tree T, where the order of siblings in both P and T matters. This problem has many applications in practice, such as retrieval of documents, data mining, and RNA structure matching. In this paper, we propose an efficient algorithm for this problem. Its time complexity is bounded by ${\text{O}(\vert }T\vert \cdot \;min\{h_{P}{,\;\vert \text{leaves(}}P)\vert \})$O(|T|·min{hP,|leaves(P)|}), with ${\text{O}(\vert }T\vert + \vert P\vert)$O(|T|+|P|) space being used, where hP (hT) represents the height of P (resp., T) and leaves (P) stands for the set of the leaves of P. Up to now the best algorithm for this problem needs $\Theta (\vert T\vert \cdot \vert leaves(P)\vert)$Θ(|T|·|leaves(P)|) time and ${\text{O}(\vert }P\vert + \vert T\vert)$O(|P|+|T|) space. Extensive experiments have been done, which show that the new algorithm can perform much better than the existing ones in practice. [ABSTRACT FROM AUTHOR]

Bearing is an important machine detail that appears in almost all mechanical systems. Estimating its operating condition online in order to hold the initiative in exploiting the systems, therefore, is one of the most urgent requirements. In this paper, we propose an online bearing damage identifying method named ASSBDIM based on adaptive neuro-fuzzy inference system (ANFIS), singular spectrum analysis (SSA), and sparse filtering (SF). It is an online process with offline and online phases. In the offline phase, by applying SSA and SF to the measured data stream typed big data with noise, both preprocessing data and extracting valuable information are implemented to build two offline databases signed Off_DaB and Off_testDaB. The ANFIS identifies the dynamic response of the mechanical system via Off_DaB. Based on Off_testDaB, the parameters of the ASSBDIM are then optimized. In the online phase, at each time, another database called On_DaB is built in the way similar to the one used for building the input space of the two offline databases. On_DaB participates as inputs of the ANFIS to estimate its outputs, which are then compared with the corresponding encoded outputs to specify bearing real status at this time. Survey results based on different data sources showed the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]