waashk/dblp huggingface dataset:
large-scale sparse logistic regression. logistic regression is a well-known classification method that has been used widely in many applications of data mining, machine learning, computer vision, and bioinformatics. sparse logistic regression embeds feature selection in the classification framework using the l1-norm regularization, and is attractive in many applications involving high-dimensional data. in this paper, we propose lassplore for solving large-scale sparse logistic regression. specifically, we formulate the problem as the l1-ball constrained smooth convex optimization, and propose to solve the problem using the nesterov's method, an optimal first-order black-box method for smooth convex optimization. one of the critical issues in the use of the nesterov's method is the estimation of the step size at each of the optimization iterations. previous approaches either applies the constant step size which assumes that the lipschitz gradient is known in advance, or requires a sequence of decreasing step size which leads to slow convergence in practice. in this paper, we propose an adaptive line search scheme which allows to tune the step size adaptively and meanwhile guarantees the optimal convergence rate. empirical comparisons with several state-of-the-art algorithms demonstrate the efficiency of the proposed lassplore algorithm for large-scale problems.
towards combining web classification and web information extraction: a case study. web content analysis often has two sequential and separate steps: web classification to identify the target web pages, and web information extraction to extract the metadata contained in the target web pages. this decoupled strategy is highly ineffective since the errors in web classification will be propagated to web information extraction and eventually accumulate to a high level. in this paper we study the mutual dependencies between these two steps and propose to combine them by using a model of conditional random fields (crfs). this model can be used to simultaneously recognize the target web pages and extract the corresponding metadata. systematic experiments in our project ofcourse for online course search show that this model significantly improves the f1 value for both of the two steps. we believe that our model can be easily generalized to many web applications.
open standards and cloud computing: kdd-2009 panel report. at kdd-2009 in paris, a panel on open standards and cloud computing addressed emerging trends for data mining applications in science and industry. this report summarizes the answers from a distinguished group of thought leaders representing key software vendors in the data mining industry. supporting open standards and the predictive model markup language (pmml) in particular, the panel members discuss topics regarding the adoption of prevailing standards, benefits of interoperability for business users, and the practical application of predictive models. we conclude with an assessment of emerging technology trends and the impact that cloud computing will have on applications as well as licensing models for the predictive analytics industry.
characteristic relational patterns. research in relational data mining has two major directions: finding global models of a relational database and the discovery of local relational patterns within a database. while relational patterns show how attribute values co-occur in detail, their huge numbers hamper their usage in data analysis. global models, on the other hand, only provide a summary of how different tables and their attributes relate to each other, lacking detail of what is going on at the local level. in this paper we introduce a new approach that combines the positive properties of both directions: it provides a detailed description of the complete database using a small set of patterns. more in particular, we utilise a rich pattern language and show how a database can be encoded by such patterns. then, based on the mdlprinciple, the novel rdb-krimp algorithm selects the set of patterns that allows for the most succinct encoding of the database. this set, the code table, is a compact description of the database in terms of local relational patterns. we show that this resulting set is very small, both in terms of database size and in number of its local relational patterns: a reduction of up to 4 orders of magnitude is attained.
measuring the effects of preprocessing decisions and network forces in dynamic network analysis. social networks have become a major focus of research in recent years, initially directed towards static networks but increasingly, towards dynamic ones. in this paper, we investigate how different pre-processing decisions and different network forces such as selection and influence affect the modeling of dynamic networks. we also present empirical justification for some of the modeling assumptions made in dynamic network analysis (e.g., first-order markovian assumption) and develop metrics to measure the alignment between links and attributes under different strategies of using the historical network data. we also demonstrate the effect of attribute drift, that is, the importance of individual attributes in forming links change over time.
analyzing patterns of user content generation in online social networks. various online social networks (osns) have been developed rapidly on the internet. researchers have analyzed different properties of such osns, mainly focusing on the formation and evolution of the networks as well as the information propagation over the networks. in knowledge-sharing osns, such as blogs and question answering systems, issues on how users participate in the network and how users "generate/contribute" knowledge are vital to the sustained and healthy growth of the networks. however, related discussions have not been reported in the research literature. in this work, we empirically study workloads from three popular knowledge-sharing osns, including a blog system, a social bookmark sharing network, and a question answering social network to examine these properties. our analysis consistently shows that (1) users' posting behavior in these networks exhibits strong daily and weekly patterns, but the user active time in these osns does not follow exponential distributions; (2) the user posting behavior in these osns follows stretched exponential distributions instead of power-law distributions, indicating the influence of a small number of core users cannot dominate the network; (3) the distributions of user contributions on high-quality and effort-consuming contents in these osns have smaller stretch factors for the stretched exponential distribution. our study provides insights into user activity patterns and lays out an analytical foundation for further understanding various properties of these osns.
category detection using hierarchical mean shift. many applications in surveillance, monitoring, scientific discovery, and data cleaning require the identification of anomalies. although many methods have been developed to identify statistically significant anomalies, a more difficult task is to identify anomalies that are both interesting and statistically significant. category detection is an emerging area of machine learning that can help address this issue using a "human-in-the-loop" approach. in this interactive setting, the algorithm asks the user to label a query data point under an existing category or declare the query data point to belong to a previously undiscovered category. the goal of category detection is to bring to the user's attention a representative data point from each category in the data in as few queries as possible. in a data set with imbalanced categories, the main challenge is in identifying the rare categories or anomalies; hence, the task is often referred to as rare category detection. we present a new approach to rare category detection based on hierarchical mean shift. in our approach, a hierarchy is created by repeatedly applying mean shift with an increasing bandwidth on the data. this hierarchy allows us to identify anomalies in the data set at different scales, which are then posed as queries to the user. the main advantage of this methodology over existing approaches is that it does not require any knowledge of the dataset properties such as the total number of categories or the prior probabilities of the categories. results on real-world data sets show that our hierarchical mean shift approach performs consistently better than previous techniques.
network anomaly detection based on eigen equation compression. this paper addresses the issue of unsupervised network anomaly detection. in recent years, networks have played more and more critical roles. since their outages cause serious economic losses, it is quite significant to monitor their changes over time and to detect anomalies as early as possible. in this paper, we specifically focus on the management of the whole network. in it, it is important to detect anomalies which make great impact on the whole network, and the other local anomalies should be ignored. further, when we detect the former anomalies, it is required to localize nodes responsible for them. it is challenging to simultaneously perform the above two tasks taking into account the nonstationarity and strong correlations between nodes. we propose a network anomaly detection method which resolves the above two tasks in a unified way. the key ideas of the method are: (1)construction of quantities representing feature of a whole network and each node from the same input based on eigen equation compression, and (2)incremental anomalousness scoring based on learning the probability distribution of the quantities. we demonstrate through the experimental results using two benchmark data sets and a simulation data set that anomalies of a whole network and nodes responsible for them can be detected by the proposed method.
tell me something i don't know: randomization strategies for iterative data mining. there is a wide variety of data mining methods available, and it is generally useful in exploratory data analysis to use many different methods for the same dataset. this, however, leads to the problem of whether the results found by one method are a reflection of the phenomenon shown by the results of another method, or whether the results depict in some sense unrelated properties of the data. for example, using clustering can give indication of a clear cluster structure, and computing correlations between variables can show that there are many significant correlations in the data. however, it can be the case that the correlations are actually determined by the cluster structure. in this paper, we consider the problem of randomizing data so that previously discovered patterns or models are taken into account. the randomization methods can be used in iterative data mining. at each step in the data mining process, the randomization produces random samples from the set of data matrices satisfying the already discovered patterns or models. that is, given a data set and some statistics (e.g., cluster centers or co-occurrence counts) of the data, the randomization methods sample data sets having similar values of the given statistics as the original data set. we use metropolis sampling based on local swaps to achieve this. we describe experiments on real data that demonstrate the usefulness of our approach. our results indicate that in many cases, the results of, e.g., clustering actually imply the results of, say, frequent pattern discovery.
frequent pattern mining with uncertain data. this paper studies the problem of frequent pattern mining with uncertain data. we will show how broad classes of algorithms can be extended to the uncertain data setting. in particular, we will study candidate generate-and-test algorithms, hyper-structure algorithms and pattern growth based algorithms. one of our insightful observations is that the experimental behavior of different classes of algorithms is very different in the uncertain case as compared to the deterministic case. in particular, the hyper-structure and the candidate generate-and-test algorithms perform much better than tree-based algorithms. this counter-intuitive behavior is an important observation from the perspective of algorithm design of the uncertain variation of the problem. we will test the approach on a number of real and synthetic data sets, and show the effectiveness of two of our approaches over competitive techniques.
genre-based decomposition of email class noise. corruption of data by class-label noise is an important practical concern impacting many classification problems. studies of data cleaning techniques often assume a uniform label noise model, however, which is seldom realized in practice. relatively little is understood, as to how the natural label noise distribution can be measured or simulated. using email spam-filtering data, we demonstrate that class noise can have substantial content specific bias. we also demonstrate that noise detection techniques based on classifier confidence tend to identify instances that human assessors are likely to label in error. we show that genre modeling can be very informative in identifying potential areas of mislabeling. moreover, we are able to show that genre decomposition can also be used to substantially improve spam filtering accuracy, with our results outperforming the best published figures for the trec05-p1 and ceas-2008 benchmark collections.
optimizing web traffic via the media scheduling problem. website traffic varies through time in consistent and predictable ways, with highest traffic in the middle of the day. when providing media content to visitors, it is important to present repeat visitors with new content so that they keep coming back. in this paper we present an algorithm to balance the need to keep a website fresh with new content with the desire to present the best content to the most visitors at times of peak traffic. we formulate this as the media scheduling problem, where we attempt to maximize total clicks, given the overall traffic pattern and the time varying clickthrough rates of available media content. we present an efficient algorithm to perform this scheduling under certain conditions and apply this algorithm to real data obtained from server logs, showing evidence of significant improvements in traffic from our algorithmic schedules. finally, we analyze the click data, presenting models for why and how the clickthrough rate for new content declines as it ages.
opinionminer: a novel machine learning system for web opinion mining and extraction. merchants selling products on the web often ask their customers to share their opinions and hands-on experiences on products they have purchased. unfortunately, reading through all customer reviews is difficult, especially for popular items, the number of reviews can be up to hundreds or even thousands. this makes it difficult for a potential customer to read them to make an informed decision. the opinionminer system designed in this work aims to mine customer reviews of a product and extract high detailed product entities on which reviewers express their opinions. opinion expressions are identified and opinion orientations for each recognized product entity are classified as positive or negative. different from previous approaches that employed rule-based or statistical techniques, we propose a novel machine learning approach built under the framework of lexicalized hmms. the approach naturally integrates multiple important linguistic features into automatic learning. in this paper, we describe the architecture and main components of the system. the evaluation of the proposed method is presented based on processing the online product reviews from amazon and other publicly available datasets.
cross domain distribution adaptation via kernel mapping. when labeled examples are limited and difficult to obtain, transfer learning employs knowledge from a source domain to improve learning accuracy in the target domain. however, the assumption made by existing approaches, that the marginal and conditional probabilities are directly related between source and target domains, has limited applicability in either the original space or its linear transformations. to solve this problem, we propose an adaptive kernel approach that maps the marginal distribution of target-domain and source-domain data into a common kernel space, and utilize a sample selection strategy to draw conditional probabilities between the two domains closer. we formally show that under the kernel-mapping space, the difference in distributions between the two domains is bounded; and the prediction error of the proposed approach can also be bounded. experimental results demonstrate that the proposed method outperforms both traditional inductive classifiers and the state-of-the-art boosting-based transfer algorithms on most domains, including text categorization and web page ratings. in particular, it can achieve around 10% higher accuracy than other approaches for the text categorization problem. the source code and datasets are available from the authors.
quantification and semi-supervised classification methods for handling changes in class distribution. in realistic settings the prevalence of a class may change after a classifier is induced and this will degrade the performance of the classifier. further complicating this scenario is the fact that labeled data is often scarce and expensive. in this paper we address the problem where the class distribution changes and only unlabeled examples are available from the new distribution. we design and evaluate a number of methods for coping with this problem and compare the performance of these methods. our quantification-based methods estimate the class distribution of the unlabeled data from the changed distribution and adjust the original classifier accordingly, while our semi-supervised methods build a new classifier using the examples from the new (unlabeled) distribution which are supplemented with predicted class values. we also introduce a hybrid method that utilizes both quantification and semi-supervised learning. all methods are evaluated using accuracy and f-measure on a set of benchmark data sets. our results demonstrate that our methods yield substantial improvements in accuracy and f-measure.
co-evolution of social and affiliation networks. in our work, we address the problem of modeling social network generation which explains both link and group formation. recent studies on social network evolution propose generative models which capture the statistical properties of real-world networks related only to node-to-node link formation. we propose a novel model which captures the co-evolution of social and affiliation networks. we provide surprising insights into group formation based on observations in several real-world networks, showing that users often join groups for reasons other than their friends. our experiments show that the model is able to capture both the newly observed and previously studied network properties. this work is the first to propose a generative model which captures the statistical properties of these complex networks. the proposed model facilitates controlled experiments which study the effect of actors' behavior on the evolution of affiliation networks, and it allows the generation of realistic synthetic datasets.
consensus group stable feature selection. stability is an important yet under-addressed issue in feature selection from high-dimensional and small sample data. in this paper, we show that stability of feature selection has a strong dependency on sample size. we propose a novel framework for stable feature selection which first identifies consensus feature groups from subsampling of training samples, and then performs feature selection by treating each consensus feature group as a single entity. experiments on both synthetic and real-world data sets show that an algorithm developed under this framework is effective at alleviating the problem of small sample size and leads to more stable feature selection results and comparable or better generalization performance than state-of-the-art feature selection algorithms. synthetic data sets and algorithm source code are available at http://www.cs.binghamton.edu/~lyu/kdd09/.
migration motif: a spatial - temporal pattern mining approach for financial markets. a recent study by two prominent finance researchers, fama and french, introduces a new framework for studying risk vs. return: the migration of stocks across size-value portfolio space. given the financial events of 2008, this first attempt to disentangle the relationships between migration behavior and stock returns is especially timely. their work, however, derives results only for market segments, not individual companies, and only for one-year moves. thus, we see a new challenge for financial data mining: how to capture and categorize the migration of individual companies, and how such behavior affects their returns. we propose a novel data mining approach to study the multi-year movement of individual companies. specifically, we address the question: "how does one discover frequent migration patterns in the stock market?" we present a new trajectory mining algorithm to discover migration motifs in financial markets. novel features of this algorithm are its handling of approximate pattern matching through a graph theoretical method, maximal clique identification, and incorporation of temporal and spatial constraints. we have performed a detailed study of the nasdaq, nyse, and amex stock markets, over a 43-year span. we successfully find migration motifs that confirm existing finance theories and other motifs that may lead to new financial models.
mining discrete patterns via binary matrix factorization. mining discrete patterns in binary data is important for subsampling, compression, and clustering. we consider rank-one binary matrix approximations that identify the dominant patterns of the data, while preserving its discrete property. a best approximation on such data has a minimum set of inconsistent entries, i.e., mismatches between the given binary data and the approximate matrix. due to the hardness of the problem, previous accounts of such problems employ heuristics and the resulting approximation may be far away from the optimal one. in this paper, we show that the rank-one binary matrix approximation can be reformulated as a 0-1 integer linear program (ilp). however, the ilp formulation is computationally expensive even for small-size matrices. we propose a linear program (lp) relaxation, which is shown to achieve a guaranteed approximation error bound. we further extend the proposed formulations using the regularization technique, which is commonly employed to address overfitting. the lp formulation is restricted to medium-size matrices, due to the large number of variables involved for large matrices. interestingly, we show that the proposed approximate formulation can be transformed into an instance of the minimum s-t cut problem, which can be solved efficiently by finding maximum flows. our empirical study shows the efficiency of the proposed algorithm based on the maximum flow. results also confirm the established theoretical bounds.