waashk/dblp huggingface dataset:
clump: a scalable and robust framework for structure discovery. we introduce a robust and efficient framework called clump (clustering using multiple prototypes) for unsupervised discovery of structure in data. clump relies on finding multiple prototypes that summarize the data. clustering the prototypes enables our algorithm to scale up to extremely large and high-dimensional domains such as text data. other desirable properties include robustness to noise and parameter choices. in this paper, we describe the approach in detail, characterize its performance on a variety of datasets, and compare it to some existing model selection approaches.
training support vector machines using gilbert's algorithm. support vector machines are classifiers designed around the computation of an optimal separating hyperplane. this hyperplane is typically obtained by solving a constrained quadratic programming problem, but may also be located by solving a nearest point problem. gilbert's algorithm can be used to solve this nearest point problem but is unreasonably slow. in this paper we present a modified version of gilbert's algorithm for the fast computation of the support vector machine hyperplane. we then compare our algorithm with the nearest point algorithm and with sequential minimal optimization.
a theory of inductive query answering. we introduce the boolean inductive query evaluationproblem, which is concerned with answering inductivequeries that are arbitrary boolean expressions over monotonicand anti-monotonic predicates. secondly, we developa decomposition theory for inductive query evaluation inwhich a boolean query q is reformulated into k sub-queriesq_i= q_a\wedge q_mthat are the conjunction of a monotonicand an anti-monotonic predicate. the solution to each sub-querycan be represented using a version space. we investigatehow the number of version spaces k needed to answerthe query can be minimized. thirdly, for the pattern domainof strings, we show how the version spaces can berepresented using a novel data structure, called the versionspace tree, and can be computed using a variant of the famousapriori algorithm. finally, we present some experi-mentsthat validate the approach.
a graph-ranking algorithm for geo-referencing documents. this paper presents an application of pagerank for assigning documents with a corresponding geographical scope. we describe the technique in detail, together with its theoretical formulation. experimental results are promising, comparing favorably with previous proposals.
mining significant associations in large scale text corpora. mining large-scale text corpora is an essential step in extractingthe key themes in a corpus. we motivate a quanti-tativemeasure for significant associations through the distributionsof pairs and triplets of co-occurring words. weconsider the algorithmic problem of efficiently enumerat-ingsuch significant associations and present pruning algorithmsfor these problems, with theoretical as well as empiricalanalyses. our algorithms make use of two novel miningmethods: (1) matrix mining, and (2) shortened documents.we present evidence from a diverse set of documents that ourmeasure does in fact elicit interesting co-occurrences.
correlation preserving discretization. discretization is a crucial preprocessing primitive for a variety of data warehousing and mining tasks. in this article we present a novel pca-based unsupervised algorithm for the discretization of continuous attributes in multivariate datasets. the algorithm leverages the underlying correlation structure in the dataset to obtain the discrete intervals, and ensures that the inherent correlations are preserved. the approach also extends easily to datasets containing missing values. we demonstrate the efficacy of the approach on real datasets and as a preprocessing step for both classification and frequent itemset mining tasks. we also show that the intervals are meaningful and can uncover hidden patterns in data.
neural analysis of mobile radio access network. the self-organizing map (som) is an efficient tool for visualization and clustering of multidimensional data. it transforms the input vectors on two-dimensional grid of prototype vectors and orders them. the ordered prototype vectors are easier to visualize and explore than the original data. mobile networks produce a huge amount of spatio-temporaldata. the data consists of parameters of base stations (bs)and quality information of calls. there are two alternatives in starting the data analysis. we can build either a general one-cell-model trained using state vectors from all cells, or a model of the network using state vectors with parameters from all mobile cells. in both methods,further analysis is needed to understand the reasons for various operational states of the entire network.
mining semantic networks for knowledge discovery. this paper addresses the problem of mining a class ofsemantic networks, called concept frame graphs (cfg's),for knowledge discovery from text. this new representationis motivated by the need to capture richer text content sothat non-trivial mining tasks can be performed. we firstdefine the cfg representation and then describe a rule-basedalgorithm for constructing a cfg from text documents.treating the cfg as a networked knowledge base,we propose new methods for text mining. on a specific taskof discovering the top companies in an area, we observe thatour approach leads to simpler content mining algorithms,once the cfg has been constructed. moreover, exploitingthe network structure of cfg results in significant improvementsin precision and recall.
active feature-value acquisition for classifier induction. many induction problems include missing data that can be acquired at a cost. for building accurate predictive models, acquiring complete information for all instances is often expensive or unnecessary, while acquiring information for a random subset of instances may not be most effective. active feature-value acquisition tries to reduce the cost of achieving a desired model accuracy by identifying instances for which obtaining complete information is most informative. we present an approach in which instances are selected for acquisition based on the current model's accuracy and its confidence in the prediction. experimental results demonstrate that our approach can induce accurate models using substantially fewer feature-value acquisitions as compared to alternative policies.
rdf: a density-based outlier detection method using vertical data representation. outlier detection can lead to discovering unexpected and interesting knowledge, which is critical important to some areas such as monitoring of criminal activities in electronic commerce, credit card fraud, etc. in this paper, we developed an efficient density-based outlier detection method for large datasets. our contributions are: a) we introduce a relative density factor (rdf); b) based on rdf, we propose an rdf-based outlier detection method which can efficiently prune the data points which are deep in clusters, and detect outliers only within the remaining small subset of the data; c) the performance of our method is further improved by means of a vertical data representation, p-trees. we tested our method with nhl and nba data. our method shows an order of magnitude speed improvement compared to the contemporary approaches.
privacy-sensitive bayesian network parameter learning. this paper considers the problem of learning the parameters of a bayesian network, assuming the structure of the network is given, from a privacy-sensitive dataset that is distributed between multiple parties. for a binary-valued dataset, we show that the count information required to estimate the conditional probabilities in a bayesian network can be obtained as a solution to a set of linear equations involving some inner product between the relevantdifferent feature vectors. we consider a random projection-based method that was proposed elsewhere to securely compute the inner product (with a modified implementation of that method).
discovery of association rules in tabular data. in this paper we address the problem of finding all association rules in tabular data. an algorithm, ara, for finding rules, that satisfy clearly specified constraints, in tabular data is presented. ara is based on the dense miner algorithm but includes an additional constraintand an improved method of calculating support. ara is tested and compared with our implementation of dense miner ;it is conclude that ara is usually more efficient than dense miner and is often considerably more so.we also consider the potential for modifying the constraints used in ara in order to find more generalrules.
toward xml-based knowledge discovery systems. inductive databases are intended to be general purposedatabases in which both source data and mined patterns canbe represented, retrieved and manipulated; however, theheterogeneity of models for mined patterns makes difficult torealize them. in this paper, we explore the feasibility of usingxml as the unifying framework for inductive databases,introducing a suitable data model called xdm (xml fordata mining). xdm is designed to describe source rawdata, heterogeneous mined patterns and data mining statements,so that they can be stored inside a unique xml-basedinductive database.
theory and applications of attribute decomposition. this paper examines the attribute decomposition approach with simple bayesian combination for dealing with classi£cation problems that contain high number ofattributes and moderate numbers of records. according to the attribute decomposition approach, the set of input attributes is automatically decomposed into several subsets. classi£cation model is built for each subset, then all the models are combined using simple bayesian combination.this paper presents theoretical and practical foundation for the attribute decomposition approach. a greedyprocedure, called d-ifn, is developed to decompose the input attributes set into subsets and build a classi£cation model for each subset separately. the results achieved in theempirical comparison testing with well-known classi£cationmethods (like c4.5)indicate the superiority of the decomposition approach.
privacy-preserving distributed clustering using generative models. we present a framework for clustering distributed datain unsupervised and semi-supervised scenarios, taking intoaccount privacy requirements and communication costs.rather than sharing parts of the original or perturbed data,we instead transmit the parameters of suitable generativemodels built at each local data site to a central location.we mathematically show that the best representative of allthe data is a certain "mean" model, and empirically showthat this model can be approximated quite well by generatingartificial samples from the underlying distributions usingmarkov chain monte carlo techniques, and then fittinga combined global model with a chosen parametric form tothese samples. we also propose a new measure that quantifiesprivacy based on information theoretic concepts, andshow that decreasing privacy leads to a higher quality of thecombined model and vice versa. we provide empirical resultson different data types to highlight the generality of ourframework. the results show that high quality distributedclustering can be achieved with little privacy loss and lowcommunication cost.
flexpat: flexible extraction of sequential patterns. this paper addresses sequential data mining, a sub-area of data mining where the data to be analyzed is organized in sequences. in many problem domains a natural ordering exists over data. examples of sequential databases (sdbs) include: (a)collections of temporal data sequences, such as chronologicalseries of daily stock indices or multimedia data (sound, music, video..); and (b) macromolecule banks, where aminoacid or proteic sequences are represented as strings.in a sdb it is often valuable to detect regularities through one or several sequences. in particular, finding exact or approximate repetitions of segments ca be utilized directly (e.g.for determining the biochemical activity of a protein region) or indirectly, e.g. for prediction in finance. to this end, we present concepts and an algorithm for automatically extracting sequential patterns from a sequential database. such a patter is defined as a group of significantly similar segments from one or several sequences. appropriate functions for measuringsimilarity between sequence segments are proposed, generalizing the edit distance framework. there is a trade off here between flexibility, particularly in sequence data representation and in associated similarity metrics, and computational efficiency. wedesigned the flexpat algorithm to satisfactorily cope with this trade-off. flexpat's complexity is in practice lesser than quadratic in the total length of the sdb analyzed, while allowinghigh flexibility. some experimental results obtained with flexpat on music data are presented and commented.
change profiles. in this paper we introduce a generalization of associationrules: change profiles. we analyze their properties, describetheir relationship to other structures in pattern discoveryand sketch their possible applications. we studyhow the frequent patterns can be clustered based on theirchange profiles and propose methods for approximating thefrequencies of the patterns from the approximate changeprofiles and bounding the intervals where the frequencies ofthe patterns are guaranteed to be. we evaluate empiricallythe methods for estimating the frequencies and the stabilityof their frequency estimates under different kinds of noise.
integrating customer value considerations into predictive modeling. the success of prediction models for business purposesshould not be measured by their accuracy only. theirevaluation should also take into account the higherimportance of precise prediction for "valuable"customers. we illustrate this idea through the example ofchurn modeling in telecommunications, where it isobviously much more important to identify potentialchurn among valuable customers. we discuss, boththeoretically and empirically, the optimal use of"customer value" data in the model training, modelevaluation and scoring stages. our main conclusion isthat a non-trivial approach of using "decayed" value-weightsfor training is usually preferable to the twoobvious approaches of either using non-decayed customervalues as weights or ignoring them.
o-cluster: scalable clustering of large high dimensional data sets. clustering large data sets of high dimensionality hasalways been a challenge for clustering algorithms. manyrecently developed clustering algorithms have attemptedto address either handling data sets with a very largenumber of records and/or with a very high number ofdimensions. this paper provides a discussion of theadvantages and limitations of existing algorithms whenthey operate on very large multidimensional data sets. tosimultaneously overcome both the "curse ofdimensionality" and the scalability problems associatedwith large amounts of data, we propose a new clusteringalgorithm called o-cluster. o-cluster combines a novelactive sampling technique with an axis-parallelpartitioning strategy to identify continuous areas of highdensity in the input space. the method operates on alimited memory buffer and requires at most a single scanthrough the data. we demonstrate the high quality of theobtained clustering solutions, their robustness to noise,and o-cluster's excellent scalability.
ranking-based evaluation of regression models. we suggest the use of ranking-based evaluation measures for regression models, as a complement to the commonly used residual-based evaluation. we argue that in some cases, such as the case study we present, ranking can be the main underlying goal in building a regression model, and ranking performance is the correct evaluation metric. however, even when ranking is not the contextually correct performance metric, the measures we explore still have significant advantages: they are robust against extreme outliers in the evaluation set; and they are interpretable. the two measures we consider correspond closely to non-parametric correlation coefficients commonly used in data analysis (spearman's ρ and kendall's τ); and they both have interesting graphical representations, which, similarly to roc curves, offer useful "partial" model performance views, in addition to a one-number summary in the area under the curve. we illustrate our methods on a case study of evaluating it wallet size estimation models for ibm's customers.
a heterogeneous field matching method for record linkage. record linkage is the process of determining that two records refer to the same entity. a key subprocess is evaluating how well the individual fields, or attributes, of the records match each other. one approach to matching fields is to use hand-written domain-specific rules. this "expert systems" approach may result in good performance for specific applications, but it is not scalable. this paper describes a new machine learning approach that creates expert-like rules for field matching. in our approach, the relationship between two field values is described by a set of heterogeneous transformations. previous machine learning methods used simple models to evaluate the distance between two fields. however, our approach enables more sophisticated relationships to be modeled, which better capture the complex domain specific, common-sense phenomena that humans use to judge similarity. we compare our approach to methods that rely on simpler homogeneous models in several domains. by modeling more complex relationships we produce more accurate results.
quantitative association rules based on half-spaces: an optimization approach. we tackle the problem of finding association rules for quantitative data. whereas most of the previous approaches operate on hyperrectangles, we propose a representation based on half-spaces. consequently, the left-hand side and right-hand side of an association rule does not contain a conjunction of items or intervals, but a weighted sum of variables tested against a threshold. since the downward closure property does not hold for such rules, we propose an optimization setting for finding locally optimal rules. a simple gradient descent algorithm optimizes a parameterized score function, where iterations optimizing the first separating hyperplane alternate with iterations optimizing the second. experiments with two real-world data sets show that the approach finds non-random patterns and scales up well. we therefore propose quantitative association rules based on half-spaces as an interesting new class of patterns with a high potential for applications.
employing discrete bayes error rate for discretization and feature selection. the tasks of discretization and feature selection are frequentlyused to improve classification accuracy. in this paper,we use discrete approximation of bayes error rate toperform discretization on the features. the discretizationprocedure targets minimization of bayes error rate withineach partition. a class-pair discriminatory measure can bedefined on discretized partitions which forms the basis offeature selection algorithm. small value of this measure fora class-pair indicates that the class-pair in considerationis confusing and the features which distinguish them wellshould be chosen first. a video classification problem ona large database is considered for showing the comparisonof a classifier using our discretization and feature selectiontasks with svm, neural network classifier, decision treesand k-nearest neighbor classifier
incremental learning with support vector machines. support vector machines (svms) have become a popular tool for machine learning with large amounts of high dimensional data. in this paper an approach for incremental learning with support vector machines is presented, that improves the existing approach of [3 ]. also, some insight into the interpretability of support vectors s given.
using sequential and non-sequential patterns in predictive web usage mining tasks. we describe an efficient framework for web personalizationbased on sequential and non-sequential pattern discov-eryfrom usage data. our experimental results performedon real usage data indicate that more restrictive patterns,such as contiguous sequential patterns (e.g., frequent navigationalpaths) are more suitable for predictive tasks, suchas web prefetching, which involve predicting which item isaccessed next by a user), while less constrained patterns,such as frequent itemsets or general sequential patterns aremore effective alternatives in the context of web personalizationand recommender systems.
on a capacity control using boolean kernels for the learning of boolean functions. this paper concerns the classification task discrete attribute spaces, but consider the task in a more fundamental framework: the learning of boolean functions.the purpose of this paper is to present a new learning algorithm for boolean functions called boolean kernel classifier (bkc) employing capacity control using boolean kernels.bkc uses support vector machines (svms) as learning engines and boolean kernels are primarily used for running svms in feature spaces spanned by conjunctions of boolean literals.however, another inportant role of boolean kernels is to appropriately control the size of its hypothesis space to avoid overfitting.after applying a svm to learn a classifier f in a feature space h induced by a boolean kernel f k of f onto a subspace hk of h spanned by conjunctions with length at most k, bkc can determine the smallest k such that f k is as accurate as f and learn another f' in hk expected to have lower error for unseen data.by an empirical study on learning of randomly generated boolean functions, it is shown that the capacity control is effective, and bkc outperforms c4.5 and naive bayes classifiers.
feature selection algorithms: a survey and experimental evaluation. in view of the substantial number of existing feature selection algorithms, the need arises to count on criteria that enables to adequately decide which algorithm to us in certain situations.this work assess the performance of several fundamental algorithms found in the literature in a controlled scenario.a scoring measure ranks the algorithms by taking into account the amount of relevance, irrelevance and redundance on sample data sets.this measure computer the degree of matching between the output given by the algorithm and the know optimal solution.sample size effects are also studied.
interestingness preprocessing. as the size of databases increases, the number of rules mined from them also increases, often to a extent that overwhelms users. to address this problem, an important part of the kdd process is dedicated to determining which of these patterns is interesting. in this paper we define the interestingness preprocessing step, and introduce a new framework for interestingness analysis. in asimilar fashion to data-preprocessing, this preprocessing should always be applied prior to interestingness processing. a strictrequirement, and the biggest challenge, in defining interestingness preprocessing techniques is that the preprocessing will not eliminate any potentially interesting patterns. that is, the preprocessing methods must be domain-,task-and user-independent. this property differentiates the preprocessing methods from existing interestingness criteria, and, since they can be applied automatically, makes them very useful. this generic nature also makes them rare: preprocessing methods are very challenging to define.we also define in this paper the first two preprocessing techniques, and present the empirical results of applying them to six databases. the results indicate that interestingness preprocessing step is very powerful: in most cases, an average of half the rules mined were eliminated by the application of the two interestingness preprocessing techniques. these results are particularly significant since no user-interaction is required to achieve them.