waashk/dblp huggingface dataset:
opportunistic scheduling with reliability guarantees in cognitive radio networks. we develop opportunistic scheduling policies for cognitive radio networks that maximize the throughput utility of the secondary (unlicensed) users subject to maximum collision constraints with the primary (licensed) users. we consider a cognitive network with static primary users and potentially mobile secondary users. we use the technique of lyapunov optimization to design an online flow control, scheduling, and resource allocation algorithm that meets the desired objectives and provides explicit performance guarantees.
embracing interference in ad hoc networks using joint routing and scheduling with multiple packet reception. we present an approach that takes advantage of multi-packet reception (mpr) to reduce the negative effects of multiple access interference and therefore increase the capacity of an ad hoc network. we analyze the performance upper bound of joint routing and scheduling for ad hoc networks that embrace interference by using mpr. we formulate the optimization problem under a deterministic model and seek to maximize the aggregate network throughput subject to minimum rate requirements. we then propose a polynomial-time heuristic algorithm aimed at approximating the optimal solution to the joint routing and channel access problem under mpr. we show the effectiveness of our heuristic algorithm by comparing its performance with the upper bound.
relational markov models and their application to adaptive web navigation. relational markov models (rmms) are a generalization of markov models where states can be of different types, with each type described by a different set of variables. the domain of each variable can be hierarchically structured, and shrinkage is carried out over the cross product of these hierarchies. rmms make effective learning possible in domains with very large and heterogeneous state spaces, given only sparse data. we apply them to modeling the behavior of web site users, improving prediction in our proteus architecture for personalizing web sites. we present experiments on an e-commerce and an academic web site showing that rmms are substantially more accurate than alternative methods, and make good predictions even when applied to previously-unvisited parts of the site.
fast nonlinear regression via eigenimages applied to galactic morphology. astronomy increasingly faces the issue of massive, unwieldly data sets. the sloan digital sky survey (sdss) [11] has so far generated tens of millions of images of distant galaxies, of which only a tiny fraction have been morphologically classified. morphological classification in this context is achieved by fitting a parametric model of galaxy shape to a galaxy image. this is a nonlinear regression problem, whose challenges are threefold, 1) blurring of the image caused by atmosphere and mirror imperfections, 2) large numbers of local minima, and 3) massive data sets.our strategy is to use the eigenimages of the parametric model to form a new feature space, and then to map both target image and the model parameters into this feature space. in this low-dimensional space we search for the best image-to-parameter match. to search the space, we sample it by creating a database of many random parameter vectors (prototypes) and mapping them into the feature space. the search problem then becomes one of finding the best prototype match, so the fitting process a nearest-neighbor search.in addition to the savings realized by decomposing the original space into an eigenspace, we can use the fact that the model is a linear sum of functions to reduce the prototypes further: the only prototypes stored are the components of the model function. a modified form of nearest neighbor is used to search among them.additional complications arise in the form of missing data and heteroscedasticity, both of which are addressed with weighted linear regression. compared to existing techniques, speed-ups ach-ieved are between 2 and 3 orders of magnitude. this should enable the analysis of the entire sdss dataset.
cccs: a top-down associative classifier for imbalanced class distribution. in this paper we propose cccs, a new algorithm for classification based on association rule mining. the key innovation in cccs is the use of a new measure, the "complement class support (ccs)" whose application results in rules which are guaranteed to be positively correlated. furthermore, the anti-monotonic property that ccs possesses has very different semantics vis-a-vis the traditional support measure. in particular, "good" rules have a low ccs value. this makes ccs an ideal measure to use in conjunction with a top-down algorithm. finally, the nature of ccs allows the pruning of rules without the setting of any threshold parameter! to the best of our knowledge this is the first threshold-free algorithm in association rule mining for classification.
a statistical theory for quantitative association rules. association rules are a key data-mining tool and as such have been well researched. so far, this research has focused predominantly on databases containing categorical data only. however, many real-world databases contain quantitative attributes and current solutions for this case are so far inadequate. in this paper we introduce a new definition of quantitative association rules based on statistical inference theory. our definition reflects the intuition that the goal of association rules is to find extraordinary and therefore interesting phenomena in databases. we also introduce the concept of sub-rules which can be applied to any type of association rule. rigorous experimental evaluation on real-world datasets is presented, demonstrating the usefulness and characteristics of rules mined according to our definition.
sequential pattern mining using a bitmap representation. we introduce a new algorithm for mining sequential patterns. our algorithm is especially efficient when the sequential patterns in the database are very long. we introduce a novel depth-first search strategy that integrates a depth-first traversal of the search space with effective pruning mechanisms.our implementation of the search strategy combines a vertical bitmap representation of the database with efficient support counting. a salient feature of our algorithm is that it incrementally outputs new frequent itemsets in an online fashion.in a thorough experimental evaluation of our algorithm on standard benchmark data from the literature, our algorithm outperforms previous work up to an order of magnitude.
adaptive duplicate detection using learnable string similarity measures. the problem of identifying approximately duplicate records in databases is an essential step for data cleaning and data integration processes. most existing approaches have relied on generic or manually tuned distance metrics for estimating the similarity of potential duplicates. in this paper, we present a framework for improving duplicate detection using trainable measures of textual similarity. we propose to employ learnable text distance functions for each database field, and show that such measures are capable of adapting to the specific notion of similarity that is appropriate for the field's domain. we present two learnable text similarity measures suitable for this task: an extended variant of learnable string edit distance, and a novel vector-space based measure that employs a support vector machine (svm) for training. experimental results on a range of datasets show that our framework can improve duplicate detection accuracy over traditional techniques.
random projection in dimensionality reduction: applications to image and text data. random projections have recently emerged as a powerful method for dimensionality reduction. theoretical results indicate that the method preserves distances quite nicely; however, empirical results are sparse. we present experimental results on using random projection as a dimensionality reduction tool in a number of cases, where the high dimensionality of the data would otherwise lead to burden-some computations. our application areas are the processing of both noisy and noiseless images, and information retrieval in text documents. we show that projecting the data onto a random lower-dimensional subspace yields results comparable to conventional dimensionality reduction methods such as principal component analysis: the similarity of data vectors is preserved well under random projection. however, using random projections is computationally significantly less expensive than using, e.g., principal component analysis. we also show experimentally that using a sparse random matrix gives additional computational savings in random projection.
group formation in large social networks: membership, growth, and evolution. the processes by which communities come together, attract new members, and develop over time is a central research issue in the social sciences - political movements, professional organizations, and religious denominations all provide fundamental examples of such communities. in the digital domain, on-line groups are becoming increasingly prominent due to the growth of community and social networking sites such as myspace and livejournal. however, the challenge of collecting and analyzing large-scale time-resolved data on social groups and communities has left most basic questions about the evolution of such groups largely unresolved: what are the structural features that influence whether individuals will join communities, which communities will grow rapidly, and how do the overlaps among pairs of communities change over time.here we address these questions using two large sources of data: friendship links and community membership on livejournal, and co-authorship and conference publications in dblp. both of these datasets provide explicit user-defined communities, where conferences serve as proxies for communities in dblp. we study how the evolution of these communities relates to properties such as the structure of the underlying social networks. we find that the propensity of individuals to join communities, and of communities to grow rapidly, depends in subtle ways on the underlying network structure. for example, the tendency of an individual to join a community is influenced not just by the number of friends he or she has within the community, but also crucially by how those friends are connected to one another. we use decision-tree techniques to identify the most significant structural determinants of these properties. we also develop a novel methodology for measuring movement of individuals between communities, and show how such movements are closely aligned with changes in the topics of interest within the communities.
topics in 0--1 data. large 0--1 datasets arise in various applications, such as market basket analysis and information retrieval. we concentrate on the study of topic models, aiming at results which indicate why certain methods succeed or fail. we describe simple algorithms for finding topic models from 0--1 data. we give theoretical results showing that the algorithms can discover the epsilon-separable topic models of papadimitriou et al. we present empirical results showing that the algorithms find natural topics in real-world data sets. we also briefly discuss the connections to matrix approaches, including nonnegative matrix factorization and independent component analysis.
robust information-theoretic clustering. how do we find a natural clustering of a real world point set, which contains an unknown number of clusters with different shapes, and which may be contaminated by noise? most clustering algorithms were designed with certain assumptions (gaussianity), they often require the user to give input parameters, and they are sensitive to noise. in this paper, we propose a robust framework for determining a natural clustering of a given data set, based on the minimum description length (mdl) principle. the proposed framework, robust information-theoretic clustering (ric), is orthogonal to any known clustering algorithm: given a preliminary clustering, ric purifies these clusters from noise, and adjusts the clusterings such that it simultaneously determines the most natural amount and shape (subspace) of the clusters. our ric method can be combined with any clustering technique ranging from k-means and k-medoids to advanced methods such as spectral clustering. in fact, ric is even able to purify and improve an initial coarse clustering, even if we start with very simple methods such as grid-based space partitioning. moreover, ric scales well with the data set size. extensive experiments on synthetic and real world data sets validate the proposed ric framework.
an iterative hypothesis-testing strategy for pattern discovery. pattern discovery has emerged as a direct result of increased data storage and analytic capabilities available to the data analyst. without a massive amount of data, we do not have the evidence to support the discovery of the local deterministic structures that we call patterns. as such, pattern discovery is one of the few areas of data mining that cannot be considered simply as a 'scaling-up' of current statistical methodology to analyze large data sets. however, the philosophies of hypothesis testing and modeling in traditional statistics do lend themselves to forming a framework for pattern discovery, and we can also draw from ideas relating to outlier discovery and residual analysis to discover patterns. we illustrate an iterative strategy in a statistical framework by way of its application to one simulated and two real data sets.
clustering time series from arma models with clipped data. clustering time series is a problem that has applications in a wide variety of fields, and has recently attracted a large amount of research. in this paper we focus on clustering data derived from autoregressive moving average (arma) models using k-means and k-medoids algorithms with the euclidean distance between estimated model parameters. we justify our choice of clustering technique and distance metric by reproducing results obtained in related research. our research aim is to assess the affects of discretising data into binary sequences of above and below the median, a process known as clipping, on the clustering of time series. it is known that the fitted ar parameters of clipped data tend asymptotically to the parameters for unclipped data. we exploit this result to demonstrate that for long series the clustering accuracy when using clipped data from the class of arma models is not significantly different to that achieved with unclipped data. next we show that if the data contains outliers then using clipped data produces significantly better clusterings. we then demonstrate that using clipped series requires much less memory and operations such as distance calculations can be much faster. finally, we demonstrate these advantages on three real world data sets.
ann quality diagnostic models for packaging manufacturing: an industrial data mining case study. world steel trade becomes more competitive every day and new high international quality standards and productivity levels can only be achieved by applying the latest computational technologies. data driven analysis of complex processes is necessary in many industrial applications where analytical modeling is not possible. this paper presents the deployment of kdd technology in one real industrial problem: the development of new tinplate quality diagnostic models.the electrodeposition of tin on steel strips is the most critical stage of a complex process that involves a great amount of variables and operating conditions. its optimization is not only a great commercial and economic challenge but also a compulsion due to the social impact of the tinplate product-more than 90% of the production is used for food packaging. the necessary certification with standards, like iso 9000, requires the use of diagnostic models to minimize the costs and the environmental impact. this aim has been achieved following the multi-stage dm methodology crisp-dm and a novel application of pro-active maintenance methods, as fmea, for the identification of the specific process anomalies. three dm tools have been used for the development of the models. the final results include two ann tinplate quality diagnostic models, that provide the estimated quality of the final product just seconds after its production and only based on the process data. the results have much better performance than the classical faraday's models widely used for the estimation.
the architecture of complexity: the structure and the dynamics of networks, from the web to the cell. networks with complex topology describe systems as diverse as the cell, the world wide web or the society. the emergence of most networks is driven by self-organizing processes that are governed by simple but generic laws. the analysis of the cellular network of various organisms shows that cells and complex man-made networks, such as the internet or the world wide web, and many social and collaboration networks share the same large-scale topology. i will show that the scale-free topology of these complex webs have important consequences on their robustness against failures and attacks, with implications on drug design, the internet's ability to survive attacks and failures, and the ability of ideas and innovations to spread on the network.
cross channel optimized marketing by reinforcement learning. the issues of cross channel integration and customer life time value modeling are two of the most important topics surrounding customer relationship management (crm) today. in the present paper, we describe and evaluate a novel solution that treats these two important issues in a unified framework of markov decision processes (mdp). in particular, we report on the results of a joint project between ibm research and saks fifth avenue to investigate the applicability of this technology to real world problems. the business problem we use as a testbed for our evaluation is that of optimizing direct mail campaign mailings for maximization of profits in the store channel. we identify a problem common to cross-channel crm, which we call the cross-channel challenge, due to the lack of explicit linking between the marketing actions taken in one channel and the customer responses obtained in another. we provide a solution for this problem based on old and new techniques in reinforcement learning. our in-laboratory experimental evaluation using actual customer interaction data show that as much as 7 to 8 per cent increase in the store profits can be expected, by employing a mailing policy automatically generated by our methodology. these results confirm that our approach is valid in dealing with the cross channel crm scenarios in the real world.
a generalized maximum entropy approach to bregman co-clustering and matrix approximation. co-clustering, or simultaneous clustering of rows and columns of a two-dimensional data matrix, is rapidly becoming a powerful data analysis technique. co-clustering has enjoyed wide success in varied application domains such as text clustering, gene-microarray analysis, natural language processing and image, speech and video analysis. in this paper, we introduce a partitional co-clustering formulation that is driven by the search for a good matrix approximation---every co-clustering is associated with an approximation of the original data matrix and the quality of co-clustering is determined by the approximation error. we allow the approximation error to be measured using a large class of loss functions called bregman divergences that include squared euclidean distance and kl-divergence as special cases. in addition, we permit multiple structurally different co-clustering schemes that preserve various linear statistics of the original data matrix. to accomplish the above tasks, we introduce a new minimum bregman information (mbi) principle that simultaneously generalizes the maximum entropy and standard least squares principles, and leads to a matrix approximation that is optimal among all generalized additive models in a certain natural parameter space. analysis based on this principle yields an elegant meta algorithm, special cases of which include most previously known alternate minimization based clustering algorithms such as kmeans and co-clustering algorithms such as information theoretic (dhillon et al., 2003b) and minimum sum-squared residue co-clustering (cho et al., 2004). to demonstrate the generality and flexibility of our co-clustering framework, we provide examples and empirical evidence on a variety of problem domains and also describe novel co-clustering applications such as missing value prediction and compression of categorical data matrices.
an iterative method for multi-class cost-sensitive learning. cost-sensitive learning addresses the issue of classification in the presence of varying costs associated with different types of misclassification. in this paper, we present a method for solving multi-class cost-sensitive learning problems using any binary classification algorithm. this algorithm is derived using hree key ideas: 1) iterative weighting; 2) expanding data space; and 3) gradient boosting with stochastic ensembles. we establish some theoretical guarantees concerning the performance of this method. in particular, we show that a certain variant possesses the boosting property, given a form of weak learning assumption on the component binary classifier. we also empirically evaluate the performance of the proposed method using benchmark data sets and verify that our method generally achieves better results than representative methods for cost-sensitive learning, in terms of predictive performance (cost minimization) and, in many cases, computational efficiency.
generative model-based clustering of directional data. high dimensional directional data is becoming increasingly important in contemporary applications such as analysis of text and gene-expression data. a natural model for multi-variate directional data is provided by the von mises-fisher (vmf) distribution on the unit hypersphere that is analogous to the multi-variate gaussian distribution in rd. in this paper, we propose modeling complex directional data as a mixture of vmf distributions. we derive and analyze two variants of the expectation maximization (em) framework for estimating the parameters of this mixture. we also propose two clustering algorithms corresponding to these variants. an interesting aspect of our methodology is that the spherical kmeans algorithm (kmeans with cosine similarity) can be shown to be a special case of both our algorithms. thus, modeling text data by vmf distributions lends theoretical validity to the use of cosine similarity which has been widely used by the information retrieval community. as part of experimental validation, we present results on modeling high-dimensional text and gene-expression data as a mixture of vmf distributions. the results indicate that our approach yields superior clusterings especially for difficult clustering tasks in high-dimensional spaces.