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]

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]

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]

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 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]

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]

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]

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]

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]

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]

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]

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]

Today, many scientific data sets are open to the public. For their operators, it is important to know what the users are interested in. In this paper, we study the problem of extracting and analyzing patterns from the query log of a database. We focus on design errors (antipatterns), which typically lead to unnecessary SQL statements. Such antipatterns do not only have a negative effect on performance. They also introduce bias on any subsequent analysis of the SQL log. We propose a framework designed to discover patterns and antipatterns in arbitrary SQL query logs and to clean antipatterns. To study the usefulness of our approach and to reveal insights regarding the existence of antipatterns in real-world systems, we examine the SQL log of the SkyServer project, containing more than 40 million queries. Among the top 15 patterns, we have found six antipatterns. This result as well as other ones gives way to the conclusion that antipatterns might falsify refactoring and any other downstream analyses. [ABSTRACT FROM AUTHOR]

In this paper, we propose SUbsequence Matching framework with cell MERgence (SUMMER) for online subsequence matching between histogram-based stream synopsis structures under the dynamic time warping distance. Given a query synopsis pattern, SUMMER continuously identifies all the matching subsequences for a stream as the bins are generated. To effectively reduce the computation time, we design a Weighted Dynamic Time Warping (WDTW) algorithm, which computes the warping distance directly between two histogram-based synopses. Furthermore, a Stack-based Overlapping Filter Algorithm (SOFA) is provided to remove the overlapping subsequences to avoid the redundant information. Finally, we design an optional refinement module to relax the subsequence range limit and improve the matching accuracy. Our experiments on real datasets show that the proposed method significantly speeds up the pattern matching without compromising the accuracy required when compared with other approaches. [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]

In industrial areas, understanding the preference of customers is one of the important considerations for establishing profitable product manufacturing plans. As one of the approaches in pattern mining, high utility pattern mining has been employed to find a set of products creating high profits by considering the purchase quantity and price of each product. In this regard, high utility pattern mining can be useful to establish profitable product manufacturing plans that allow a corporation to maximize its revenue. For establishing manufacturing plans, we also need to understand the recent preference of customers from stream data, which are continually generated without limitations. In this paper, we propose a novel algorithm and list structure for finding high utility patterns over data streams on the basis of a sliding window mode. Unlike existing algorithms, the proposed algorithm does not consume huge computational resources for verifying candidate patterns because it can avoid the generation of candidate patterns. Therefore, the algorithm efficiently works in complex dynamic systems. Experimental results obtained from various tests using real-world dataset show that the proposed algorithm outperforms state-of-the-art methods in terms of runtime, memory usage, and scalability. [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]

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]

In this paper, an online data-driven approach is proposed for the detection of low-quality synchrophasor measurements. The proposed method leverages the spatio-temporal similarities among multiple-time-instant synchrophasor measurements and formulates the low-quality synchrophasor data as spatio-temporal outliers. A density-based local outlier detection technique is proposed to detect the spatio-temporal outliers. This data-driven approach involves no system modeling information. The detection algorithm can operate under both normal and fault-on system conditions, with fast computation speed suitable for online applications. Case studies on both synthetic and real-world synchrophasor data verify the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

This paper considers an unsupervised learning algorithm that can automatically discover key behavior patterns to characterize a complex video scene. For behavior features (bFs) extracted at multiple spatial-temporal scales, an optimization problem is formulated to cluster bFs in their scales while establishing a collaborative nonlinear relationship in the form of a kernel regression function among clustered bFs across different spatial scales. The relationship allows features extracted in one scale to be considered as contextual information in the analysis of another scale. This optimization problem is solved using linear programming to reduce computational complexity. The proposed algorithm is evaluated on four crowded traffic scenes and two sports video data sets. Experimental results show that the proposed algorithm achieves a better performance compared with the current state-of-the-art algorithms in terms of video segmentation accuracy. [ABSTRACT FROM AUTHOR]

The identification of network motifs has important applications in numerous domains, such as pattern detection in biological networks and graph analysis in digital circuits. However, mining network motifs is computationally challenging, as it requires enumerating subgraphs from a real-life graph, and computing the frequency of each subgraph in a large number of random graphs. In particular, existing solutions often require days to derive network motifs from biological networks with only a few thousand vertices. To address this problem, this paper presents a novel study on network motif discovery using Graphical Processing Units (GPUs). The basic idea is to employ GPUs to parallelize a large number of subgraph matching tasks in computing subgraph frequencies from random graphs, so as to reduce the overall computation time of network motif discovery. We explore the design space of GPU-based subgraph matching algorithms, with careful analysis of several crucial factors (such as branch divergences and memory coalescing) that affect the performance of GPU programs. Based on our analysis, we develop a GPU-based solution that (i) considerably differs from existing CPU-based methods in how it enumerates subgraphs, and (ii) exploits the strengths of GPUs in terms of parallelism while mitigating their limitations in terms of the computation power per GPU core. With extensive experiments on a variety of biological networks, we show that our solution is up to two orders of magnitude faster than the best CPU-based approach, and is around $20$ times more cost-effective than the latter, when taking into account the monetary costs of the CPU and GPUs used. [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]

Point-of-Interest recommendation is an essential means to help people discover attractive locations, especially when people travel out of town or to unfamiliar regions. While a growing line of research has focused on modeling user geographical preferences for POI recommendation, they ignore the phenomenon of user interest drift across geographical regions, i.e., users tend to have different interests when they travel in different regions, which discounts the recommendation quality of existing methods, especially for out-of-town users. In this paper, we propose a latent class probabilistic generative model Spatial-Temporal LDA (ST-LDA) to learn region-dependent personal interests according to the contents of their checked-in POIs at each region. As the users’ check-in records left in the out-of-town regions are extremely sparse, ST-LDA incorporates the crowd’s preferences by considering the public’s visiting behaviors at the target region. To further alleviate the issue of data sparsity, a social-spatial collective inference framework is built on ST-LDA to enhance the inference of region-dependent personal interests by effectively exploiting the social and spatial correlation information. Besides, based on ST-LDA, we design an effective attribute pruning (AP) algorithm to overcome the curse of dimensionality and support fast online recommendation for large-scale POI data. Extensive experiments have been conducted to evaluate the performance of our ST-LDA model on two real-world and large-scale datasets. The experimental results demonstrate the superiority of ST-LDA and AP, compared with the state-of-the-art competing methods, by making more effective and efficient mobile recommendations. [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]

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]

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 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]

This paper introduces and solves a novel type of spatial queries, namely, Optimal-Location-Selection (OLS) search, which has many applications in real life. Given a data object set DA, a target object set DB, a spatial region R, and a critical distance dc in a multidimensional space, an OLS query retrieves those target objects in DB that are outside R but have maximal optimality. Here, the optimality of a target object b ∈ DB located outside R is defined as the number of the data objects from DA that are inside R and meanwhile have their distances to b not exceeding dc. When there is a tie, the accumulated distance from the data objects to b serves as the tie breaker, and the one with smaller distance has the better optimality. In this paper, we present the optimality metric, formalize the OLS query, and propose several algorithms for processing OLS queries efficiently. A comprehensive experimental evaluation has been conducted using both real and synthetic data sets to demonstrate the efficiency and effectiveness of the proposed algorithms. [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]

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]

Data Mining, or knowledge discovery, is the computer-assisted process of digging through and analyzing large quantity of data in order to extract meaningful knowledge. Data mining methods are used in many studies to identify phenomena quicker and better than human experts. One class of these methods was designed for dealing with time series data. However, when several channels of data are collected simultaneously, data mining algorithms encounter numerous difficulties since channels may be measured in different units, may be recorded at different sampling-rates, or may have completely different characteristics. Furthermore, as the size of these data increases, the amount of irrelevant data usually increases as well and the process becomes impractical. Hence, in such cases, the analyst must be capable of focusing on the informational parts while ignoring the noise data. These kinds of difficulties complicate the analysis of multi- channel data as compared to the analysis of single-channel data. This paper presents a useful technique for preprocessing multi channel data. Our technique supplies tools for coping with all the above-mentioned difficulties, and prepares the data for further analysis (using common algorithms, especially from the data mining field). The paper is divided as follows. After the introduction (Section I) we describe the state of the art (Section II), follows by the main section-methodology (Section III) which is divided to four steps (3.2-3.5). The results are described in a separate section (Section IV). Then, a discussion and conclusions of the proposed methodology are given in (Sections V and VI). Acknowledgements and the references follow. [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]

In the context of sharing video surveillance data, a significant threat to privacy is face recognition software, which can automatically identify known people, such as from a database of drivers' license photos, and thereby track people regardless of suspicion. This paper introduces an algorithm to protect the privacy of individuals in video surveillance data by de-identifying faces such that many facial characteristics remain but the face cannot be reliably recognized. A trivial solution to de-identifying faces involves blacking out each face. This thwarts any possible face recognition, but because all facial details are obscured, the result is of limited use. Many ad hoc attempts, such as covering eyes, fail to thwart face recognition because of the robustness of face recognition methods. This paper presents a new privacy-enabling algorithm, named k-Same, that guarantees face recognition software cannot reliably recognize de-identified faces, even though many facial details are preserved. The algorithm determines similarity between faces based on a distance metric and creates new faces by averaging image components, which may be the originat image pixels (k-Same-Pixel) or eigenvectors (k-Same-Eigen). Results are presented on a standard collection of real face images with varying k. [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]

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]

To increase efficacy in traditional classroom courses as well as in Massive Open Online Courses (MOOCs), automated systems supporting the instructor are needed. One important problem is to automatically detect students that are going to do poorly in a course early enough to be able to take remedial actions. Existing grade prediction systems focus on maximizing the accuracy of the prediction while overseeing the importance of issuing timely and personalized predictions. This paper proposes an algorithm that predicts the final grade of each student in a class. It issues a prediction for each student individually, when the expected accuracy of the prediction is sufficient. The algorithm learns online what is the optimal prediction and time to issue a prediction based on past history of students’ performance in a course. We derive a confidence estimate for the prediction accuracy and demonstrate the performance of our algorithm on a dataset obtained based on the performance of approximately 700 UCLA undergraduate students who have taken an introductory digital signal processing over the past seven years. We demonstrate that for 85% of the students we can predict with 76% accuracy whether they are going do well or poorly in the class after the fourth course week. Using data obtained from a pilot course, our methodology suggests that it is effective to perform early in-class assessments such as quizzes, which result in timely performance prediction for each student, thereby enabling timely interventions by the instructor (at the student or class level) when necessary. [ABSTRACT FROM AUTHOR]

Fine-grained image categorization is a challenging task aiming at distinguishing objects belonging to the same basic-level category, e.g., leaf or mushroom. It is a useful technique that can be applied for species recognition, face verification, and so on. Most of the existing methods either have difficulties to detect discriminative object components automatically, or suffer from the limited amount of training data in each sub-category. To solve these problems, this paper proposes a new fine-grained image categorization model. The key is a dense graph mining algorithm that hierarchically localizes discriminative object parts in each image. More specifically, to mimic the human hierarchical perception mechanism, a superpixel pyramid is generated for each image. Thereby, graphlets from each layer are constructed to seamlessly capture object components. Intuitively, graphlets representative to each super-/sub-category is densely distributed in their feature space. Thus, a dense graph mining algorithm is developed to discover graphlets representative to each super-/sub-category. Finally, the discovered graphlets from pairwise images are integrated into an image kernel for fine-grained recognition. Theoretically, the learned kernel can generalize several state-of-the-art image kernels. Experiments on nine image sets demonstrate the advantage of our method. Moreover, the discovered graphlets from each sub-category accurately capture those tiny discriminative object components, e.g., bird claws, heads, and bodies. [ABSTRACT FROM PUBLISHER]