waashk/dblp huggingface dataset:
robust time-referenced segmentation of moving object trajectories. trajectory segmentation is the process of partitioning a given trajectory into a small number of homogeneous segments w.r.t. some criteria. conventional segmentation techniques only focus on the spatial features of the movement and could lead to spatially homogeneous segments but with presumably dissimilar temporal structures. furthermore, trajectories could be over-segmented in the presence of outliers. in this paper, we propose a family of three trajectory segmentation methods that takes into account both geospatial and temporal structures of movement for the segmentation and is also robust with respect to time-referenced spatial outliers. the effectiveness of our methods is empirically demonstrated over three real-world datasets.
text mining in radiology reports. medical text mining has gained increasing interest in recent years. radiology reports contain rich information describing radiologist’s observations on the patient’s medical conditions in the associated medical images. however, as most reports are in free text format, the valuable information contained in those reports cannot be easily accessed and used, unless proper text mining has been applied. in this paper, we propose a text mining system to extract and use the information in radiology reports. the system consists of three main modules: a medical finding extractor, a report and image retriever, and a text-assisted image feature extractor. in evaluation, the overall precision and recall for medical finding extraction are 95.5% and 87.9% respectively, and for all modifiers of the medical findings 88.2% and 82.8% respectively. the overall result of report and image retrieval module and text-assisted image feature extraction module is satisfactory to radiologists.
a shrinkage approach for modeling non-stationary relational autocorrelation. recent research has shown that collective classification in relational data often exhibit significant performance gains over conventional approaches that classify instances individually. this is primarily due to the presence of autocorrelation in relational datasets, meaning that the class labels of related entities are correlated and inferences about one instance can be used to improve inferences about linked instances. statistical relational learning techniques exploit relational autocorrelation by modeling global autocorrelation dependencies under the assumption that the level of autocorrelation is stationary throughout the dataset. to date, there has been no work examining the appropriateness of this stationarity assumption. in this paper, we examine two real-world datasets and show that there is significant variance in the autocorrelation dependencies throughout the relational data graphs. we develop a shrinkage technique for modeling this non-stationary autocorrelation and show that it achieves significant accuracy gains over competing techniques that model either local or global autocorrelation dependencies in isolation.
isolation forest. most existing model-based approaches to anomaly detection construct a profile of normal instances, then identify instances that do not conform to the normal profile as anomalies. this paper proposes a fundamentally different model-based method that explicitly isolates anomalies instead of profiles normal points. to our best knowledge, the concept of isolation has not been explored in current literature. the use of isolation enables the proposed method, iforest, to exploit sub-sampling to an extent that is not feasible in existing methods, creating an algorithm which has a linear time complexity with a low constant and a low memory requirement. our empirical evaluation shows that iforest performs favourably to orca, a near-linear time complexity distance-based method, lof and random forests in terms of auc and processing time, and especially in large data sets. iforest also works well in high dimensional problems which have a large number of irrelevant attributes, and in situations where training set does not contain any anomalies.
inlier-based outlier detection via direct density ratio estimation. we propose a new statistical approach to the problem of inlier-based outlier detection, i.e.,finding outliers in the test set based on the training set consisting only of inliers. our key idea is to use the ratio of training and test data densities as an outlier score; we estimate the ratio directly in a semi-parametric fashion without going through density estimation. thus our approach is expected to have better performance in high-dimensional problems. furthermore, the applied algorithm for density ratio estimation is equipped with a natural cross-validation procedure, allowing us to objectively optimize the value of tuning parameters such as the regularization parameter and the kernel width. the algorithm offers a closed-form solution as well as a closed-form formula for the leave-one-out error. thanks to this, the proposed outlier detection me thod is computationally very efficient and is scalable to massive datasets. simulations with benchmark and real-world datasets illustrate the usefulness of the proposed approach.
overlapping matrix pattern visualization: a hypergraph approach. in this work, we study a visual data mining problem: given a set of discovered overlapping submatrices of interest, how can we order the rows and columns of the data matrix to best display these submatrices and their relationships? we find this problem can be converted to the hypergraph ordering problem, which generalizes the traditional minimal linear arrangement (or graph ordering) problem and then we are able to prove the np-hardness of this problem. we propose a novel iterative algorithm which utilize the existing graph ordering algorithm to solve the optimal visualization problem. this algorithm can always converge to a local minimum. the detailed experimental evaluation using a set of publicly available transactional datasets demonstrates the effectiveness and efficiency of the proposed algorithm.
experimental evaluation of the value of structure: how to efficiently exploit interdependencies in sequence labeling. many problems in natural language processing, information extraction or bioinformatics consist in predicting a label for each element of a sequence of observations. the sequence of labels generally presents multiple dependencies that restrict the possible labels the elements can take. therefore, relations between labels intuitively provide information valuable for the prediction. several approaches have been proposed to take advantage of this additional information. however, experimental results show that taking relations into account does not always improve prediction performances, while it significantly increases the computational cost of both learning and prediction. in this work, we aim at both explaining these surprising results and proposing a simple but computationnaly efficient approach for labeling sequences.
a conservative feature subset selection algorithm with missing data. this paper introduces a novel conservative feature subset selection method with incomplete data sets. the method is conservative in the sense that it selects the minimal subset of features that renders the rest of the features independent of the target (the class variable) without making any assumption about the missing data mechanism. this is achieved in the context of determining the markov blanket of the target that reflects the worst-case assumption about the missing data mechanism, including the case when data is not missing at random. an application of the method on synthetic incomplete data is carried out to illustrate its practical relevance. the method is compared against state-of-the-art approaches such as the {expectation maximization} (em) algorithm and the available case technique.
multi-label classification using ensembles of pruned sets. this paper presents a pruned sets method (ps) for multi-label classification. it is centred on the concept of treating sets of labels as single labels. this allows the classification process to inherently take into account correlations between labels. by pruning these sets, ps focuses only on the most important correlations, which reduces complexity and improves accuracy. by combining pruned sets in an ensemble scheme (eps), new label sets can be formed to adapt to irregular or complex data. the results from experimental evaluation on a variety of multi-label datasets show that [e]ps can achieve better performance and train much faster than other multi-label methods.
why stacked models perform effective collective classification. collective classification techniques jointly infer all class labels of a relational data set, using the inferences about one class label to influence inferences about related class labels. kou and cohen recently introduced an efficient relational model based on stacking that, despite its simplicity, has equivalent accuracy to more sophisticated joint inference approaches. using experiments on both real and synthetic data, we show that the primary cause for the performance of the stacked model is the reduction in bias from learning the stacked model on inferred labels rather than true labels. the reduction in variance due to conditional inference also contributes to the effect but it is not as strong. in addition, we show that the performance of the joint inference and stacked learners can be attributed to an implicit weighting of local and relational features at learning time.
stream sequential pattern mining with precise error bounds. sequential pattern mining is an interesting data mining problem with many real-world applications. this problem has been studied extensively in static databases. however, in recent years, emerging applications have introduced a new form of data called data stream. in a data stream, new elements are generated continuously. this poses additional constraints on the methods used for mining such data: memory usage is restricted, the infinitely flowing original dataset cannot be scanned multiple times, and current results should be available on demand.this paper introduces two effective methods for mining sequential patterns from data streams: the ss-be method and the ss-mb method. the proposed methods break the stream into batches and only process each batch once. the two methods use different pruning strategies that restrict the memory usage but can still guarantee that all true sequential patterns are output at the end of any batch. both algorithms scale linearly in execution time as the number of sequences grows, making them effective methods for sequential pattern mining in data streams. the experimental results also show that our methods are very accurate in that only a small fraction of the patterns that are output are false positives. even for these false positives, ss-be guarantees that their true support is above a pre-defined threshold.
space efficient string mining under frequency constraints. let $\db_1$ and $\db_2$ be two databases (i.e. multisets) of $d$ strings, over an alphabet $\sigma$, with overall length $n$. we study the problem of mining discriminative patterns between $\db_1$ and $\db_2$ --- e.g., patterns that are frequent in one database but not in the other, emerging patterns, or patterns satisfying other frequency-related constraints. using the algorithmic framework by hui (cpm 1992), one can solve several variants of this problem in the optimal linear time with the aid of suffix trees or suffix arrays. this stands in high contrast to other pattern domains such as itemsets or subgraphs, where super-linear lower bounds are known. however, the space requirement of existing solutions is $o(n \log n)$ bits, which is not optimal for $|\sigma
comparative evaluation of anomaly detection techniques for sequence data. we present a comparative evaluation of a large number of anomaly detection techniques on a variety of publicly available as well as artificially generated data sets. many of these are existing techniques while some are slight variants and/or adaptations of traditional anomaly detection techniques to sequence data.
semi-supervised learning from general unlabeled data. we consider the problem of semi-supervised learning (ssl) from general unlabeled data, which may contain irrelevant samples. within the binary setting, our model manages to better utilize the information from unlabeled data by formulating them as a three-class ($-1,+1, 0$) mixture, where class $0$ represents the irrelevant data. this distinguishes our work from the traditional ssl problem where unlabeled data are assumed to contain relevant samples only, either $+1$ or $-1$, which are forced to be the same as the given labeled samples. this work is also different from another family of popular models, universum learning (universum means "irrelevant" data), in that the universum need not to be specified beforehand. one significant contribution of our proposed framework is that such irrelevant samples can be automatically detected from the available unlabeled data, even though they are mixed with relevant data. this hence presents a general ssl framework that does not force "clean" unlabeled data.more importantly, we formulate this general learning framework as a semi-definite programming problem, making it solvable in polynomial time. a series of experiments demonstrate that the proposed framework can outperform the traditional ssl on both synthetic and real data.
similarity learning for nearest neighbor classification. in this paper, we propose an algorithm for learning a general class of similarity measures for knn classification. this class encompasses, among others, the standard cosine measure, as well as the dice and jaccard coefficients. the algorithm we propose is an extension of the voted perceptron algorithm and allows one to learn different types of similarity functions (either based on diagonal, symmetric or asymmetric similarity matrices). the results we obtained show that learning similarity measures yields significant improvements on several collections, for two prediction rules: the standard knn rule, which was our primary goal, and a symmetric version of it.
active learning of equivalence relations by minimizing the expected loss using constraint inference. selecting promising queries is the key to effective active learning. in this paper, we investigate selection techniques for the task of learning an equivalence relation where the queries are about pairs of objects. as the target relation satisfies the axioms of transitivity, from one queried pair additional constraints can be inferred. we derive both the upper and lower bound on the number of queries needed to converge to the optimal solution. besides restricting the set of possible solutions, constraints can be used as training data for learning a similarity measure. for selecting queries that result in a large number of meaningful constraints, we present an approximative optimal selection technique that greedily minimizes the expected loss in each round of active learning. this technique makes use of inference of expected constraints. besides the theoretical results, an extensive evaluation for the application of record linkage shows empirically that the proposed selection method leads to both interesting and a high number of constraints.
efficient discovery of statistically significant association rules. searching statistically significant association rules is an important but neglected problem. traditional association rules do not capture the idea of statistical dependence and the resulting rules can be spurious, while the most significant rules may be missing. this leads to erroneous models and predictions which often become expensive.the problem is computationally very difficult, because the significance is not a monotonic property. however, in this paper we prove several other properties, which can be used for pruning the search space. the properties are implemented in the statapriori algorithm, which searches statistically significant, non-redundant association rules. based on both theoretical and empirical observations, the resulting rules are very accurate compared to traditional association rules. in addition, statapriori can work with extremely low frequencies, thus finding new interesting rules.
pseudolikelihood em for within-network relational learning. in this work, we study the problem of \emph{within-network} relational learning and inference, where models are learned on a partially labeled relational dataset and then are applied to predict the classes of unlabeled instances in the same graph. we categorize recent work in statistical relational learning into three alternative approaches for this setting: disjoint learning with disjoint inference, disjoint learning with collective inference, and collective learning with collective inference. models from each of these categories has been employed previously in different settings, but to our knowledge there has been no systematic comparison of models from all three categories. in this paper, we develop a novel pseudolikelihood em method that facilitates more general \emph{collective learning} and \emph{collective inference} on partially labeled relational networks. we then compare this method to competing methods from the other categories on both synthetic and real-world data. we show that collective learning and inference with the pseudolikelihood em approach achieves significantly higher accuracy than the other types of models when there are a moderate number of labeled examples in the data graph.
rtm: laws and a recursive generator for weighted time-evolving graphs. how do real, weighted graphs change over time? what patterns, if any, do they obey? earlier studies focus on unweighted graphs, and, with few exceptions, they focus on static snapshots. here, we report patterns we discover on several real, weighted, time-evolving graphs. the reported patterns can help in detecting anomalies in natural graphs, in making link prediction and in providing more criteria for evaluation of synthetic graph generators. we further propose an intuitive and easy way to construct weighted, time-evolving graphs. in fact, we prove that our generator will produce graphs which obey many patterns and laws observed to date. we also provide empirical evidence to support our claims.
start globally, optimize locally, predict globally: improving performance on imbalanced data. class imbalance is a ubiquitous problem in supervised learning and has gained wide-scale attention in the literature. perhaps the most prevalent solution is to applysampling to training data in order improve classiﬁer performance. the typical approach will apply uniform levels of sampling globally. however, we believe that datais typically multi-modal, which suggests sampling shouldbe treated locally rather than globally. it is the purposeof this paper to propose a framework which ﬁrst identiﬁes meaningful regions of data and then proceeds to ﬁndoptimal sampling levels within each. this paper demonstrates that a global classiﬁer trained on data locally sampled produces superior rank-orderings on a wide range ofreal-world and artiﬁcial datasets as compared to contemporary global sampling methods.
spotting significant changing subgraphs in evolving graphs. graphs are popularly used to model structural relationships between objects. in many application domains such as social networks, sensor networks and telecommunication, graphs evolve over time. in this paper, we study a new problem of discovering the subgraphs that exhibit significant changes in evolving graphs. this problem is challenging since it is hard to define changing regions that are closely related to the actual changes (i.e., additions/deletions of edges/nodes) in graphs. we formalize the problem, and design an efficient algorithm that is able to identify the changing subgraphs incrementally. our experimental results on real datasets show that our solution is very efficient and the resultant subgraphs are of high quality.
inscy: indexing subspace clusters with in-process-removal of redundancy. subspace clustering aims at detecting clusters in any subspace projection of a high dimensional space. as the number of projections is exponential in the number of dimensions, efficiency is crucial. moreover, the resulting subspace clusters are often highly redundant, i.e. many clusters are detected multiply in several projections. we propose a novel index for efficient subspace clustering in a novel depth-first processing with in-process-removal of redundant clusters for better pruning. thorough experiments on real and synthetic data show that inscy yields substantial efficiency and quality improvements.
a novel method of combined feature extraction for recognition. multimodal recognition is an emerging technique to overcome the non-robustness of the unimodal recognition in real applications. canonical correlation analysis (cca) has been employed as a powerful tool for feature fusion in the realization of such multimodal system. however, cca is the unsupervised feature extraction and it does not utilize the class information of the samples, resulting in the constraint of the recognition performance. in this paper, the class information is incorporated into the framework of cca for combined feature extraction, and a novel method of combined feature extraction for multimodal recognition, called discriminative canonical correlation analysis (dcca), is proposed. the experiments show that dcca outperforms some related methods of both unimodal recognition and multimodal recognition.
nonparametric monotone classification with moca. we describe a monotone classification algorithm called moca that attemptsto minimize the mean absolute prediction error for classification problems with ordered class labels.we first find a monotone classifier with minimum l1 loss on the training sample, and then use a simpleinterpolation scheme to predict the class labels for attribute vectors not present in the training data.we compare moca to the ordinal stochastic dominance learner (osdl), on artificial as well asreal data sets. we show that moca often outperforms osdl with respect to mean absolute prediction error.
efficient feature selection in the presence of multiple feature classes. we present an information theoretic approach to feature selection when the data possesses feature classes. feature classes are pervasive in real data. for example, in gene expression data, the genes which serve as features may be divided into classes based on their membership in gene families or pathways. when doing word sense disambiguation or named entity extraction, features fall into classes including adjacent words, their parts of speech, and the topic and venue of the document the word is in. when predictive features occur predominantly in a small number of feature classes, our information theoretic approach significantly improves feature selection. experiments on real and synthetic data demonstrate substantial improvement in predictive accuracy over the standard $l_0$ penalty-based stepwise and stream wise feature selection methods as well as over lasso and elastic nets, all of which are oblivious to the existence of feature classes.
cleansing noisy data streams. in this paper, we identify a new research problem on cleansing noisy data streams which contain incorrectly labeled training examples. the objective is to accurately identify and remove mislabeled data, such that the prediction models built from the cleansed streams can be more accurate than the ones trained from the raw noisy streams. for this purpose, we first use bias-variance decomposition to derive a maximum variance margin (mvm) principle for stream data cleansing. following this principle, we further propose a local and global filtering (lgf) framework to combine the strength of local noise filtering (within one single data chunk) and global noise filtering (across a number of adjacent data chunks) to identify erroneous data. experimental results on six data streams (including two real-world data streams) demonstrate that lgf significantly outperforms simple methods in identifying noisy examples.