waashk/dblp huggingface dataset:
provably fast training algorithms for support vector machines. support vector machines are a family of data analysis algorithms, based on convex quadratic programming. we focus on their use for classification that case the svm algorithms work by maximizing the margin of a classifying hyperplane in a feature space. the feature space is handled by means of kernels f the problems are formulated in dual form. random sampling techniques successfully used for similar problems are studied here. the main contribute onis a random zed algorithm for training svms for which we can formally prove an upper bound on the expected running time that is quasilinear on the number of data points. to ourknowledge, this is the first algorithm for training svms in dual formulation and with kernels for which such a quasi-linear time bound has been formally proved.
inexact field learning: an approach to induce high quality rules from low quality data. to avoid low quality problem caused by low quality data, this paper introduces an inexactfield learning approach which derives rules by working on the fields of attributes with respect to classes, rather than on individual point values of attributes. the experimental results show that field learning achieved a higher prediction accuracy rate on new unseen test cases which is particularly true when the learning is performed on large low qualitydata.
a lazy approach to pruning classification rules. associative classification is a promising technique forthe generation of highly precise classifiers. previous workspropose several clever techniques to prune the huge set ofgenerated rules, with the twofold aim of selecting a smallset of high quality rules, and reducing the chance of overfitting.in this paper, we argue that pruning should be reducedto a minimum and that the availability of a large rule basemay improve the precision of the classifier, without affectingits performance. in l3 (live and let live), a new algorithmfor associative classification, a lazy pruning technique iterativelydiscards all rules that only yield wrong case classifications.classification is performed in two steps. initially, ruleswhich have already correctly classified at least one trainingcase, sorted by confidence, are considered. if the caseis still unclassified, the remaining rules (unused during thetraining phase) are considered, again sorted by confidence.extensive experiments on 26 databases from the ucimachine learning database repository show that l3 improvesthe classification precision with respect to previousapproaches.
clustering on demand for multiple data streams. in the data stream environment, the patterns generated by the mining techniques are usually distinct at different time because of the evolution of data. in order to deal with various types of multiple data streams and to support flexible mining requirements, we devise in this paper a clustering on demand framework, abbreviated as cod framework, to dynamically cluster multiple data streams. while providing a general framework of clustering on multiple data streams, the cod framework has two major features, namely one data scan for online statistics collection and compact multi-resolution approximations, which are designed to address, respectively, the time and the space constraints in a data stream environment. furthermore, with the multi-resolution approximations of data streams, flexible clustering demands can be supported.
detecting patterns of appliances from total load data using a dynamic programming approach. nonintrusive appliance load monitoring (nialm) systems require sufficient accurate total load data to separate the load into its major appliances. the most available solutions separate the whole electric energy consumption based on the measurement of all three voltages and currents. aside from the cost for special measuring devices, the intrusion into the local installation is the main problem for reaching a high market distribution. the use of standard digital electricity meters could avoid this problem but the loss of information of the measured data has to be compensated by more intelligent algorithms and implemented rules to disaggregate the total load trace of only the active power measurements. the paper presents a new nialm approach to analyse data, collected form a standard digital electricity meter. to disaggregate the consumption of the entire active power into its major electrical end uses, an algorithm consisting of clustering methods, a genetic algorithm and a dynamic programming approach is presented. the genetic algorithm is used to combine frequently occuring events to create hypothetical finite state machines to model detectable appliances. the time series of each finite state machine is optimized using a dynamic programming method similar to the viterbi algorithm.
feature selection for clustering - a filter solution. processing applications with a large number of dimensionshas been a challenge to the kdd community. featureselection, an effective dimensionality reduction technique,is an essential pre-processing method to remove noisy features.in the literature there are only a few methods proposedfor feature selection for clustering. and, almost all ofthose methods are wrapper' techniques that require a clusteringalgorithm to evaluate the candidate feature subsets.the wrapper approach is largely unsuitable in real-worldapplications due to its heavy reliance on clustering algorithmsthat require parameters such as number of clusters,and due to lack of suitable clustering criteria to evaluateclustering in different subspaces. in this paper we proposea filter' method that is independent of any clustering algorithm.the proposed method is based on the observationthat data with clusters has very different point-to-point distancehistogram than that of data without clusters. usingthis we propose an entropy measure that is low if data hasdistinct clusters and high otherwise. the entropy measure issuitable for selecting the most important subset of featuresbecause it is invariant with number of dimensions, and isaffected only by the quality of clustering. extensive performanceevaluation over synthetic, benchmark, and realdatasets shows its effectiveness.
mining relevant text from unlabelled documents. automatic classification of documents is an importantarea of research with many applications in the fields of documentsearching, forensics and others. methods to performclassification of text rely on the existence of a sample of documentswhose class labels are known. however, in manysituations, obtaining this sample may not be an easy (oreven possible) task. in this paper we focus on the classificationof unlabelled documents into two classes: relevant andirrelevant, given a topic of interest. by dividing the set ofdocuments into buckets (for instance, answers returned bydifferent search engines), and using association rule miningto find common sets of words among the buckets, we can efficientlyobtain a sample of documents that has a large percentageof relevant ones. this sample can be used to trainmodels to classify the entire set of documents. we prove, viaexperimentation, that our method is capable of filtering relevantdocuments even in adverse conditions where the percentageof irrelevant documents in the buckets is relativelyhigh.
efficient yet accurate clustering. in this paper we show that most hierarchical agglomerativeclustering (hac)algorithms follow a 90-10 rule where roughly 90%iterations from the beginning merge cluster pairs with dissimilarity less than 10%of the maximumdissimilarity. we propose two algorithms - 2-phase andnested - based on partially overlapping partitioning (pop).to handle high-dimensional data efficiently, we propose a tree structure particularly suitable for pop. extensive experimentsshow that the proposed algorithms reduce the time andmemory requirement of existing hac algorithms significantly without compromising in accuracy.
classifier fusion using shared sampling distribution for boosting. we present a new framework for classifier fusion that uses a shared sampling distribution for obtaining a weighted classifier ensemble. the weight update process is self regularizing as subsequent classifiers trained on the disjoint views rectify the bias introduced by any classifier in preceding iterations. we provide theoretical guarantees that our approach indeed provides results which are better than the case when boosting is performed separately on different views. the results are shown to outperform other classifier fusion strategies on a well known texture image database.
mining frequent spatio-temporal sequential patterns. many applications track the movement of mobile objects, which can be represented as sequences of timestamped locations. given such a spatio-temporal series, we study the problem of discovering sequential patterns, which are routes frequently followed by the object. sequential pattern mining algorithms for transaction data are not directly applicable for this setting. the challenges to address are (i) the fuzziness of locations in patterns, and (ii) the identification of non-explicit pattern instances. in this paper, we define pattern elements as spatial regions around frequent line segments. our method first transforms the original sequence into a list of sequence segments, and detects frequent regions in a heuristic way. then, we propose algorithms to find patterns by employing a newly proposed substring tree structure and improving apriori technique. a performance evaluation demonstrates the effectiveness and efficiency of our approach.
using rough sets theory and database operations to construct a good ensemble of classifiers for data mining applications. in this paper we present a new approach to construct a good ensemble of classifiers using rough sets theory and database operations. ensembles of classifiers is formulated precisely within the framework of rough sets theory and constructed very efficiently by using set-oriented database operations. our method first computes a set of reductswhich include all the indispensable attributes required for the decision categories. for each reduct, a reduct table is generated by removing those attributes which are not in the reduct. next, a novel rule induction algorithm is used to compute the maximal generalized rules for each reducttable and a set of reduct classifiers is formed based on thecorresponding reducts. the distinctive features of our method as compared to other methods of constructing ensembles of classifiers are:(1) present a theoretical model to explain the mechanism of constructing ensemble of classifiers, (2) each reduct is a minimum subset of attributes, has the same classification ability as the entire attributes,(3)ea h reduct classifier constructed from the corresponding reduct has a minimal set of classification rules, and is as accurate andcomplete as possible and at the same time as diverse as possible from the other classifiers, (4)the test indicates that the number of classifiers used to improve the accuracy is muchless than other methods
subspace selection for clustering high-dimensional data. in high-dimensional feature spaces traditional clustering algorithms tend to break down in terms of efficiency and quality. nevertheless, the data sets often contain clusters which are hidden in various subspaces of the original feature space. in this paper, we present a feature selection technique called surfing (subspaces relevant for clustering) that finds all subspaces interesting for clustering and sorts them by relevance. the sorting is based on a quality criterion for the interestingness of a subspace using the k-nearest neighbor distances of the objects. as our method is more or less parameterless, it addresses the unsupervised notion of the data mining task "clustering" in a best possible way. a broad evaluation based on synthetic and real-world data sets demonstrates that surfing is suitable to find all relevant subspaces in high dimensional, sparse data sets and produces better results than comparative methods.
towards simple, easy-to-understand, yet accurate classifiers. we design a method for weighting linear support vectormachine classifiers or random hyperplanes, to obtain classifierswhose accuracy is comparable to the accuracy of anon-linear support vector machine classifier, and whose resultscan be readily visualized. we conduct a simulationstudy to examine how our weighted linear classifiers behavein the presence of known structure. the results show thatthe weighted linear classifiers might perform well comparedto the non-linear support vector machine classifiers, whilethey are more readily interpretable than the non-linear classifiers.
mining a set of coregulated rna sequences. post-transcriptional regulation, though less studied, isan important research topic in bioinformatics. in a set ofpost-transcriptionally coregulated rnas, the basepair interactionscan organize the molecules into domains andprovide a framework for functional interactions. their consensusmotifs may represent the binding sites of rna regulatoryproteins. unlike dna motifs, rna motifs are moreconserved in structures than in sequences. knowing thestructural motifs can help us better understand the regulationactivities. in this paper, we propose a novel data miningapproach to rna secondary structure prediction. todemonstrate the performance of our new approach, we firsttested it on the same data sets previously used and publishedin literature. secondly, to show the flexibility of ournew approach, we also tested it on a data set that containspseudoknot motifs that most current systems cannot identify.
improving automatic query classification via semi-supervised learning. accurate topical classification of user queries allows for increased effectiveness and efficiency in general-purpose web search systems. such classification becomes critical if the system is to return results not just from a general web collection but from topic-specific back-end databases as well. maintaining sufficient classification recall is very difficult as web queries are typically short, yielding few features per query. this feature sparseness coupled with the high query volumes typical for a large-scale search service makes manual and supervised learning approaches alone insufficient. we use an application of computational linguistics to develop an approach for mining the vast amount of unlabeled data in web query logs to improve automatic topical web query classification. we show that our approach in combination with manual matching and supervised learning allows us to classify a substantially larger proportion of queries than any single technique. we examine the performance of each approach on a real web query stream and show that our combined method accurately classifies 46% of queries, outperforming the recall of best single approach by nearly 20%, with a 7% improvement in overall effectiveness.
extraction techniques for mining services from web sources. the web has established itself as the dominantmedium for doing electronic commerce. consequentlythe number of service providers, bothlarge and small, advertising their services on theweb continues to proliferate. in this paper we describenew extraction algorithms for mining servicedirectories from web pages. we develop anovel propagation technique for identifying andaccumulating all of the attributes related to a serviceentity in a web page. we provide experimentalresults of the effectiveness of our extractiontechniques by mining a database of veterinarianservice providers from web sources.
neighborgram clustering interactive exploration of cluster neighborhoods. we describe an interactive way to generate a set of clustersfor a given data set. the clustering is done by constructinglocal histograms, which can then be used to visualize,select, and fine-tune potential cluster candidates.the accompanying algorithmcan also generate clusters automatically,allowing for an automatic or semi-automaticclustering process where the user only occasionally interactswith the algorithm. we illustrate the ability to automaticallyidentify and visualize clusters using nci's aidsantiviral screen data set.
findings from a practical project concerning web usage mining. in a practical project a statistical analysis of the weblog files of the domain www.volkswagen.de was carriedout by using the crisp-dm procedure. for the preprocessingphase, more profound findings could be gainedthan are usually described in many studies. since the aimwas to deduce significant statements while measuring theeffect, tests of significance for e-metrics were used inaddition to the commonly described procedure.
who links to whom: mining linkage between web sites. previous studies of the web graph structure have focused on the graph structure at the level of individual pages. in actuality the web is a hierarchically nested graph, with domains, hosts and web sites introducing intermediate levels of affiliation and administrativecontrol. to better understand the growth of the web we need to understand its macro-structure, in terms of the linkage between web sites. in this paper e approximate this by studying the graph of the linkage between hosts on the web. this as done based on snapshots of the web taken by google in oct 1999,aug 2000 and jun 2001.the connectivity between hosts is represented by a directed graph, with hosts as nodes and weighted edges representingthe count of hyperlinks between pages on the corresponding hosts. we demonstrate how such a "hostgraph" an be used to study connectivity properties of hosts and domains over time, anddiscuss a modified "copy model" too explain observed link eight distributions as a function of subgraph size. we discuss changes in the web over time in the size and connectivity of web sites and country domains. we also describe a data mining application of the hostgraph: a related host finding algorithm which achieves a precision of 0.65 at rank 3.
a new algorithm for learning parameters of a bayesian network from distributed data. we present a novel approach for learning parametersof a bayesian network from distributed heterogeneousdataset. in this case, the whole dataset is distributedin several sites and each site contains observations fora different subset of features. the new method usesthe collective learning approach proposed in our earlierwork and substantially reduces the computational andtransmission overhead. theoretical analysis is givenand experimental results are provided to illustrate theaccuracy and efficiency of our method.
pairwise symmetry decomposition method for generalized covariance analysis. we propose a new theoretical framework for generalizing the traditional notion of covariance. first, we discuss the role of pairwise cross-cumulants by introducing a cluster expansion technique for the cumulant generating function. next, we introduce a novel concept of symmetry decomposition of probability density functions according to the c_4v group. by utilizing the irreducible representations, generalized covariances are explicitly defined, and their utility is demonstrated using an analytically solvable model.
vivo: visual vocabulary construction for mining biomedical images. given a large collection of medical images of several conditions and treatments, how can we succinctly describe the characteristics of each setting? for example, given a large collection of retinal images from several different experimental conditions (normal, detached, reattached, etc.), how can data mining help biologists focus on important regions in the images or on the differences between different experimental conditions? if the images were text documents, we could find the main terms and concepts for each condition by existing ir methods (e.g., tf/idf and lsi). we propose something analogous, but for the much more challenging case of an image collection: we propose to automatically develop a visual vocabulary by breaking images into n × n tiles and deriving key tiles ("vivos") for each image and condition. we experiment with numerous domain-independent ways of extracting features from tiles (color histograms, textures, etc.), and several ways of choosing characteristic tiles (pca, ica). we perform experiments on two disparate biomedical datasets. the quantitative measure of success is classification accuracy: our "vivos" achieve high classification accuracy (up to 83% for a nine-class problem on feline retinal images). more importantly, qualitatively, our "vivos" do an excellent job as "visual vocabulary terms": they have biological meaning, as corroborated by domain experts; they help spot characteristic regions of images, exactly like text vocabulary terms do for documents; and they highlight the differences between pairs of images.
webspade: a parallel sequence mining algorithm to analyze web log data. enterprise-class web sites receive a large amountof traffic, from both registered and anonymous users.data warehouses are built to store and help analyze the click streams within this traffic to providecompanies with valuable insights into the behaviorof their customers. this article proposes a parallelsequence mining algorithm, webspade, to analyzethe click streams found in site web logs. in this process, raw web logs are first cleaned and inserted intoa data warehouse. the click streams are then minedby webspade. an innovative web-based front-endis used to visualize and query the sequence miningresults. the webspade algorithm is currently usedby verizon to analyze the daily traffic of the verizon.com web site.
semi-supervised mixture of kernels via lpboost methods. we propose an algorithmto construct classification models with a mixture of kernels from labeled and unlabeled data. the derived classifier is a mixture of models, each based on one kernel choice from a library of kernels. the sparse-favoring 1-norm regularization method is employed to restrict the complexity of mixture models and to achieve the sparsity of solutions. by modifying the column generation boosting algorithm lpboost to a more general linear programming formulation, we are able to efficiently solve mixture-of-kernel problems and automatically select kernel basis functions centered at labeled data as well as unlabeled data. the effectiveness of the proposed approach is proved by experimental results on benchmark datasets.
kernel-density-based clustering of time series subsequences using a continuous random-walk noise model. noise levels in time series subsequence data are typically very high, and properties of the noise differ from those of white noise. the proposed algorithm incorporates a continuous random-walk noise model into kernel-density-based clustering. evaluation is done by testing to what extent the resulting clusters are predictive of the process that generated the time series. it is shown that the new algorithm not only outperforms partitioning techniques that lead to trivial and unsatisfactory results under the given quality measure, but also improves upon other density-based algorithms. the results suggest that the noise elimination properties of kernel-density-based clustering algorithms can be of significant value for the use of clustering in preprocessing of data.
a levelwise search algorithm for interesting subspace clusters. we present a levelwise search algorithm for finding subspace clusters in high dimensional data satisfying various properties besides the commonly used minimum density property. a set of such properties are summarized and a user can choose any of these properties. a lattice is built with all the discovered clusters which enables further analysis and discovery of useful knowledge about the clusters and their inter-relationships.