waashk/dblp huggingface dataset:
combining proactive and reactive predictions for data streams. mining data streams is important in both science and commerce. two major challenges are (1) the data may grow without limit so that it is difficult to retain a long history; and (2) the underlying concept of the data may change over time. different from common practice that keeps recent raw data, this paper uses a measure of conceptual equivalence to organize the data history into a history of concepts. along the journey of concept change, it identifies new concepts as well as re-appearing ones, and learns transition patterns among concepts to help prediction. different from conventional methodology that passively waits until the concept changes, this paper incorporates proactive and reactive predictions. in a proactive mode, it anticipates what the new concept will be if a future concept change takes place, and prepares prediction strategies in advance. if the anticipation turns out to be correct, a proper prediction model can be launched instantly upon the concept change. if not, it promptly resorts to a reactive mode: adapting a prediction model to the new data. a system repro is proposed to implement these new ideas. experiments compare the system with representative existing prediction methods on various benchmark data sets that represent diversified scenarios of concept change. empirical evidence demonstrates that the proposed methodology is an effective and efficient solution to prediction for data streams.
topic-conditioned novelty detection. automated detection of the first document reporting each new event in temporally-sequenced streams of documents is an open challenge. in this paper we propose a new approach which addresses this problem in two stages: 1) using a supervised learning algorithm to classify the on-line document stream into pre-defined broad topic categories, and 2) performing topic-conditioned novelty detection for documents in each topic. we also focus on exploiting named-entities for event-level novelty detection and using feature-based heuristics derived from the topic histories. evaluating these methods using a set of broadcast news stories, our results show substantial performance gains over the traditional one-level approach to the novelty detection problem.
simultaneous record detection and attribute labeling in web data extraction. recent work has shown the feasibility and promise of template-independent web data extraction. however, existing approaches use decoupled strategies - attempting to do data record detection and attribute labeling in two separate phases. in this paper, we show that separately extracting data records and attributes is highly ineffective and propose a probabilistic model to perform these two tasks simultaneously. in our approach, record detection can benefit from the availability of semantics required in attribute labeling and, at the same time, the accuracy of attribute labeling can be improved when data records are labeled in a collective manner. the proposed model is called hierarchical conditional random fields. it can efficiently integrate all useful features by learning their importance, and it can also incorporate hierarchical interactions which are very important for web data extraction. we empirically compare the proposed model with existing decoupled approaches for product information extraction, and the results show significant improvements in both record detection and attribute labeling.
mining web logs for prediction models in www caching and prefetching. web caching and prefetching are well known strategies for improving the performance of internet systems. when combined with web log mining, these strategies can decide to cache and prefetch web documents with higher accuracy. in this paper, we present an application of web log mining to obtain web-document access patterns and use these patterns to extend the well-known gdsf caching policies and prefetching policies. using real web logs, we show that this application of data mining can achieve dramatic improvement to web-access performance.
efficient elastic burst detection in data streams. burst detection is the activity of finding abnormal aggregates in data streams. such aggregates are based on sliding windows over data streams. in some applications, we want to monitor many sliding window sizes simultaneously and to report those windows with aggregates significantly different from other periods. we will present a general data structure for detecting interesting aggregates over such elastic windows in near linear time. we present applications of the algorithm for detecting gamma ray bursts in large-scale astrophysical data. detection of periods with high volumes of trading activities and high stock price volatility is also demonstrated using real time trade and quote (taq) data from the new york stock exchange (nyse). our algorithm beats the direct computation approach by several orders of magnitude.
anonymity-preserving data collection. protection of privacy has become an important problem in data mining. in particular, individuals have become increasingly unwilling to share their data, frequently resulting in individuals either refusing to share their data or providing incorrect data. in turn, such problems in data collection can affect the success of data mining, which relies on sufficient amounts of accurate data in order to produce meaningful results. random perturbation and randomized response techniques can provide some level of privacy in data collection, but they have an associated cost in accuracy. cryptographic privacy-preserving data mining methods provide good privacy and accuracy properties. however, in order to be efficient, those solutions must be tailored to specific mining tasks, thereby losing generality.in this paper, we propose efficient cryptographic techniques for online data collection in which data from a large number of respondents is collected anonymously, without the help of a trusted third party. that is, our solution allows the miner to collect the original data from each respondent, but in such a way that the miner cannot link a respondent's data to the respondent. an advantage of such a solution is that, because it does not change the actual data, its success does not depend on the underlying data mining problem. we provide proofs of the correctness and privacy of our solution, as well as experimental data that demonstrates its efficiency. we also extend our solution to tolerate certain kinds of malicious behavior of the participants.
gpca: an efficient dimension reduction scheme for image compression and retrieval. recent years have witnessed a dramatic increase in the quantity of image data collected, due to advances in fields such as medical imaging, reconnaissance, surveillance, astronomy, multimedia etc. with this increase has come the need to be able to store, transmit, and query large volumes of image data efficiently. a common operation on image databases is the retrieval of all images that are similar to a query image. for this, the images in the database are often represented as vectors in a high-dimensional space and a query is answered by retrieving all image vectors that are proximal to the query image in this space, under a suitable similarity metric. to overcome problems associated with high dimensionality, such as high storage and retrieval times, a dimension reduction step is usually applied to the vectors to concentrate relevant information in a small number of dimensions. principal component analysis (pca) is a well-known dimension reduction scheme. however, since it works with vectorized representations of images, pca does not take into account the spatial locality of pixels in images. in this paper, a new dimension reduction scheme, called generalized principal component analysis (gpca), is presented. this scheme works directly with images in their native state, as two-dimensional matrices, by projecting the images to a vector space that is the tensor product of two lower-dimensional vector spaces. experiments on databases of face images show that, for the same amount of storage, gpca is superior to pca in terms of quality of the compressed images, query precision, and computational cost.
idr/qr: an incremental dimension reduction algorithm via qr decomposition. dimension reduction is a critical data preprocessing step for many database and data mining applications, such as efficient storage and retrieval of high-dimensional data. in the literature, a well-known dimension reduction algorithm is linear discriminant analysis (lda). the common aspect of previously proposed lda-based algorithms is the use of singular value decomposition (svd). due to the difficulty of designing an incremental solution for the eigenvalue problem on the product of scatter matrices in lda, there has been little work on designing incremental lda algorithms that can efficiently incorporate new data items as they become available. in this paper, we propose an lda-based incremental dimension reduction algorithm, called idr/qr, which applies qr decomposition rather than svd. unlike other lda-based algorithms, this algorithm does not require the whole data matrix in main memory. this is desirable for large data sets. more importantly, with the insertion of new data items, the idr/qr algorithm can constrain the computational cost by applying efficient qr-updating techniques. finally, we evaluate the effectiveness of the idr/qr algorithm in terms of classification error rate on the reduced dimensional space. our experiments on several real-world data sets reveal that the classification error rate achieved by the idr/qr algorithm is very close to the best possible one achieved by other lda-based algorithms. however, the idr/qr algorithm has much less computational cost, especially when new data items are inserted dynamically.
analytical view of business data. this paper describes a logical extension to microsoft business framework (mbf) called analytical view (av). av consists of three components: model service for design time, business intelligence entity (bie) for programming model, and intelldrill for runtime navigation between oltp and olap data sources. av feature-set fulfills enterprise application requirements for analysis and decision support, complementing the transactional feature-set currently provided by mbf. model service automatically transforms an "object oriented model (transactional view)" to a "multi-dimensional model (analytical view)" without the traditional extraction/transformation/loading (etl) overhead and complexity. it infers dimensionality from the object layer where richer metadata is stored, eliminating the "guesswork" that a traditional data warehousing process requires when going through physical database schema. bi entities are classes code-generated by model service. as an intrinsic part of the framework, bi entities enable a consistent object oriented way of programming model with strong types and rich semantics for olap, similar to what mbf object persistence technology does for oltp data. more importantly, data contained in bi entities have a higher degree of "application awareness," such as the integrated application level security and customizability. intellidrill links together all the information islands in mbf using metadata. because of the automatic transformation from transactional view to analytical view enabled by model service, we have the ability to understand natively what kind of drill-ability an object would have, thus making information navigation in mbf fully discover-able with built-in ontology.
eliminating noisy information in web pages for data mining. a commercial web page typically contains many information blocks. apart from the main content blocks, it usually has such blocks as navigation panels, copyright and privacy notices, and advertisements (for business purposes and for easy user access). we call these blocks that are not the main content blocks of the page the noisy blocks. we show that the information contained in these noisy blocks can seriously harm web data mining. eliminating these noises is thus of great importance. in this paper, we propose a noise elimination technique based on the following observation: in a given web site, noisy blocks usually share some common contents and presentation styles, while the main content blocks of the pages are often diverse in their actual contents and/or presentation styles. based on this observation, we propose a tree structure, called style tree, to capture the common presentation styles and the actual contents of the pages in a given web site. by sampling the pages of the site, a style tree can be built for the site, which we call the site style tree (sst). we then introduce an information based measure to determine which parts of the sst represent noises and which parts represent the main contents of the site. the sst is employed to detect and eliminate noises in any web page of the site by mapping this page to the sst. the proposed technique is evaluated with two data mining tasks, web page clustering and classification. experimental results show that our noise elimination technique is able to improve the mining results significantly.
show me the money!: deriving the pricing power of product features by mining consumer reviews. the increasing pervasiveness of the internet has dramatically changed the way that consumers shop for goods. consumer-generated product reviews have become a valuable source of information for customers, who read the reviews and decide whether to buy the product based on the information provided. in this paper, we use techniques that decompose the reviews into segments that evaluate the individual characteristics of a product (e.g., image quality and battery life for a digital camera). then, as a major contribution of this paper, we adapt methods from the econometrics literature, specifically the hedonic regression concept, to estimate: (a) the weight that customers place on each individual product feature, (b) the implicit evaluation score that customers assign to each feature, and (c) how these evaluations affect the revenue for a given product. towards this goal, we develop a novel hybrid technique combining text mining and econometrics that models consumer product reviews as elements in a tensor product of feature and evaluation spaces. we then impute the quantitative impact of consumer reviews on product demand as a linear functional from this tensor product space. we demonstrate how to use a low-dimension approximation of this functional to significantly reduce the number of model parameters, while still providing good experimental results. we evaluate our technique using a data set from amazon.com consisting of sales data and the related consumer reviews posted over a 15-month period for 242 products. our experimental evaluation shows that we can extract actionable business intelligence from the data and better understand the customer preferences and actions. we also show that the textual portion of the reviews can improve product sales prediction compared to a baseline technique that simply relies on numeric data.
cross-relational clustering with user's guidance. clustering is an essential data mining task with numerous applications. however, data in most real-life applications are high-dimensional in nature, and the related information often spreads across multiple relations. to ensure effective and efficient high-dimensional, cross-relational clustering, we propose a new approach, called crossclus, which performs cross-relational clustering with user's guidance. we believe that user's guidance, even likely in very simple forms, could be essential for effective high-dimensional clustering since a user knows well the application requirements and data semantics. crossclus is carried out as follows: a user specifies a clustering task and selects one or a small set of features pertinent to the task. crossclus extracts the set of highly relevant features in multiple relations connected via linkages defined in the database schema, evaluates their effectiveness based on user's guidance, and identifies interesting clusters that fit user's needs. this method takes care of both quality in feature extraction and efficiency in clustering. our comprehensive experiments demonstrate the effectiveness and scalability of this approach.
integration of semantic-based bipartite graph representation and mutual refinement strategy for biomedical literature clustering. we introduce a novel document clustering approach that overcomes those problems by combining a semantic-based bipartite graph representation and a mutual refinement strategy. the primary contributions of this paper are the following. first, we introduce a new representation of documents using a bipartite graph between documents and co-occurrence concepts in the documents. second, we show how to enhance clustering quality by applying the mutual refinement strategy to the initial clustering results. third, through the experiments on medline documents, we show that our integrated method significantly enhances cluster quality and clustering reliability compared to existing clustering methods. our approach improves on the average 29.5 cluster quality and 26.3 clustering reliability, in terms of misclassification index, over bisecting k-means with the best parameters.
new algorithms for fast discovery of association rules. association rule discovery has emerged as an important problem in knowledge discovery and data mining. the association mining task consists of identifying the frequent itemsets, and then forming conditional implication rules among them. in this paper we present efficient algorithms for the discovery of frequent itemsets, which forms the compute intensive phase of the task. the algorithms utilize the structural properties of frequent itemsets to facilitate fast discovery. the related database items are grouped together into clusters representing the potential maximal frequent itemsets in the database. each cluster induces a sub-lattice of the itemset lattice. efficient lattice traversal techniques are presented, which quickly identify all the true maximal frequent itemsets, and all their subsets if desired. we also present the effect of using different database layout schemes combined with the proposed clustering and traversal techniques. the proposed algorithms scan a (pre-processed) database only once, addressing the open question in association mining, whether all the rules can be efficiently extracted in a single database pass. we experimentally compare the new algorithms against the previous approaches, obtaining improvements of more than an order of magnitude for our test databases.
automated cyclone discovery and tracking using knowledge sharing in multiple heterogeneous satellite data. current techniques for cyclone detection and tracking employ ncep (national centers for environmental prediction) models from in-situ measurements. this solution does not provide true global coverage, unlike remote satellite observations. however it is impractical to use a single earth orbiting satellite to detect and track events such as cyclones in a continuous manner due to limited spatial and temporal coverage. one solution to alleviate such persistent problems is to utilize heterogeneous sensor data from multiple orbiting satellites. however, this solution requires overcoming other new challenges such as varying spatial and temporal resolution between satellite sensor data, the need to establish correspondence between features from different satellite sensors, and the lack of definitive indicators for cyclone events in some sensor data. we describe an automated cyclone discovery and tracking approach using heterogeneous near real-time sensor data from multiple satellites. this approach addresses the unique challenges associated with knowledge discovery and mining from heterogeneous satellite data streams. we consider two remote sensor measurements in our current implementation, namely: quikscat wind satellite measurements, and merged precipitation data from trmm and other satellites. more satellites will be incorporated in the near future and our solution is sufficiently powerful that it generalizes to multiple sensor measurement modalities. our approach consists of three main components: (i) feature extraction from each sensor measurement, (ii) an ensemble classifier for cyclone discovery, and (iii) knowledge sharing between the different remote sensor measurements based on a linear kalman filter for predictive cyclone tracking. experimental results on historical hurricane datasets demonstrate the superior performance of our approach compared to previous work.
density-based spam detector. the volume of mass unsolicited electronic mail, often known as spam, has recently increased enormously and has become a serious threat to not only the internet but also to society. this paper proposes a new spam detection method which uses document space density information. although it requires extensive e-mail traffic to acquire the necessary information, an unsupervised learning engine with a short white list can achieve a 98% recall rate and 100% precision. a direct-mapped cache method contributes handling of over 13,000 e-mails per second. experimental results, which were conducted using over 50 million actual e-mails of traffic, are also reported in this paper.
on-board analysis of uncalibrated data for a spacecraft at mars. analyzing data on-board a spacecraft as it is collected enables several advanced spacecraft capabilities, such as prioritizing observations to make the best use of limited bandwidth and reacting to dynamic events as they happen. in this paper, we describe how we addressed the unique challenges associated with on-board mining of data as it is collected: uncalibrated data, noisy observations, and severe limitations on computational and memory resources. the goal of this effort, which falls into the emerging application area of spacecraft-based data mining, was to study three specific science phenomena on mars. following previous work that used a linear support vector machine (svm) on-board the earth observing 1 (eo-1)spacecraft, we developed three data mining techniques for use on-board the mars odyssey spacecraft. these methods range from simple thresholding to state-of-the-art reduced-set svm technology. we tested these algorithms on archived data in a flight software testbed. we also describe a significant, serendipitous science discovery of this data mining effort: the confirmation of a water ice annulus around the north polar cap of mars. we conclude with a discussion on lessons learned in developing algorithms for use on-board a spacecraft.
svm selective sampling for ranking with application to data retrieval. learning ranking (or preference) functions has been a major issue in the machine learning community and has produced many applications in information retrieval. svms (support vector machines) - a classification and regression methodology - have also shown excellent performance in learning ranking functions. they effectively learn ranking functions of high generalization based on the "large-margin" principle and also systematically support nonlinear ranking by the "kernel trick". in this paper, we propose an svm selective sampling technique for learning ranking functions. svm selective sampling (or active learning with svm) has been studied in the context of classification. such techniques reduce the labeling effort in learning classification functions by selecting only the most informative samples to be labeled. however, they are not extendable to learning ranking functions, as the labeled data in ranking is relative ordering, or partial orders of data. our proposed sampling technique effectively learns an accurate svm ranking function with fewer partial orders. we apply our sampling technique to the data retrieval application, which enables fuzzy search on relational databases by interacting with users for learning their preferences. experimental results show a significant reduction of the labeling effort in inducing accurate ranking functions.