waashk/dblp huggingface dataset:
frequent subgraph discovery. as data mining techniques are being increasingly applied to non-traditional domains, existing approaches for finding frequent itemsets cannot be used as they cannot model the requirement of these domains. an alternate way of modeling the objects in these data sets is to use graphs. within that model, the problem of finding frequent patterns becomes that of discovering subgraphs that occur frequently over the entire set of graphs. in this paper we present a computationally efficient algorithm for finding all frequent subgraphs in large graph databases. we evaluated the performance of the algorithm by experiments with synthetic datasets as well as a chemical compound dataset. the empirical results show that our algorithm scales linearly with the number of input transactions and it is able to discover frequent subgraphs from a set of graph transactions reasonably fast, even though we have to deal with computationally hard problems such as canonical labeling of graphs and subgraph isomorphism which are not necessary for traditional frequent itemset discovery.
feature selection via supervised model construction. relieff is a feature mining technique, which has been successfully used in data mining applications.however, relieff is sensitive to the definition of relevance that is used in its implementation and when handling a large data set, it is computationally expensive.this paper presents an optimisation (feature selection via supervised model construction) for data transformation and starter selection, and evaluates its effectiveness with c4.5.experiments indicate that the proposed method gave improvement of computation efficiency whilst maintaining classification accuracy of trial data sets.
discovering frequent geometric subgraphs. as data mining techniques are being increasingly appliedto non-traditional domains, existing approaches forfinding frequent itemsets cannot be used as they cannotmodel the requirement of these domains. an alternate wayof modeling the objects in these data sets, is to use a graphto model the database objects. within that model, the problemof finding frequent patterns becomes that of discoveringsubgraphs that occur frequently over the entire set ofgraphs. in this paper we present a computationally efficientalgorithm for finding frequent geometric subgraphs ina large collection of geometric graphs. our algorithm isable to discover geometric subgraphs that can be rotation,scaling and translation invariant, and it can accommodateinherent errors on the coordinates of the vertices. our experimentalresults show that our algorithms requires relativelylittle time, can accommodate low support values, andscales linearly on the number of transactions.
mining generalized association rules using pruning techniques. the goal of the paper is to mine generalizedassociation rules using pruning techniques. given a largetransaction database and a hierarchical taxonomy tree ofthe items, we try to find the association rules between theitems at different levels in the taxonomy tree under theassumption that original frequent itemsets and associationrules have already been generated beforehand. in theproposed algorithm gmar, we use join methods andpruning techniques to generate new generalizedassociation rules. through several comprehensiveexperiments, we find that the gmar algorithm is muchbetter than basic and cumulate algorithms.
grew-a scalable frequent subgraph discovery algorithm. existing algorithms that mine graph datasets to discover patterns corresponding to frequently occurring subgraphs can operate efficiently on graphs that are sparse, contain a large number of relatively small connected components, have vertices with low and bounded degrees, and contain well-labeled vertices and edges. however, for graphs that do not share these characteristics, these algorithms become highly unscalable. in this paper we present a heuristic algorithm called grew to overcome the limitations of existing complete or heuristic frequent subgraph discovery algorithms. grew is designed to operate on a large graph and to find patterns corresponding to connected subgraphs that have a large number of vertex-disjoint embeddings. our experimental evaluation shows that grew is efficient, can scale to very large graphs, and find non-trivial patterns.
association analysis with one scan of databases. mining frequent patterns with an fp-tree avoids costlycandidate generation and repeatedly occurrence frequencychecking against the support threshold. it thereforeachieves better performance and efficiency than apriori-likealgorithms. however, the database still needs tobe scanned twice to get the fp-tree. this can be verytime-consuming when new data are added to an existingdatabase because two scans may be needed for not only thenew data but also the existing data. this paper presentsa new data structure p-tree, pattern tree, and a new technique,which can get the p-tree through only one scan of thedatabase and can obtain the corresponding fp-tree with aspecified support threshold. updating a p-tree with newdata needs one scan of the new data only, and the existingdata do not need to be re-scanned.
statistical considerations in learning from data. in this paper we focus on statistics. classical statistics and bayesian statistics are both employed in data mining. both have advantages but both also have severe limitations in this context. we point out some of these limitations as well as s me of the advantages. the fact that we may need to take account of evidence both internal and external to the data set presents a difficulty for classical statistics. the need to incorporate an objective measure of reliability creates a difficulty for bayesian statistics.we outline an approach to uncertainty that promises to capture the best of both worlds by incorporating both background knowledge and objectivity.
triple jump acceleration for the em algorithm. this paper presents the triple jump framework for accelerating the em algorithm and other bound optimization methods. the idea is to extrapolate the third search point based on the previous two search points found by regular em. as the convergence rate of regular em becomes slower, the distance of the triple jump will be longer, and thus provide higher speedup for data sets where em converges slowly. experimental results show that the triple jump framework significantly outperforms em and other acceleration methods of em for a variety of probabilistic models, especially when the data set is sparse. the results also show that the triple jump framework is particularly effective for cluster models.
predicting density-based spatial clusters over time. most of existing clustering algorithms are designed to discover snapshot clusters that reflect only the current status of a database. snapshot clusters do not reveal the fact that clusters may either persist over a period of time, or slowly fade away as other clusters may gradually develop. predicting dynamic cluster evolutions and their occurring periods are important because this information can guide users to prepare appropriate actions toward the right areas during the right time for the most effective results. in this paper we developed a simple but effective approach in predicting the future distance among object pairs. objects that will be close in distance over different periods of time are then processed to discover density-based clusters that may occur or change over time.
hierarchy-regularized latent semantic indexing. organizing textual documents into a hierarchical taxonomy is a common practice in knowledge management. beside textual features, the hierarchical structure of directories reflect additional and important knowledge annotated by experts. it is generally desired to incorporate this information into text mining processes. in this paper, we propose hierarchy-regularized latent semantic indexing, which encodes the hierarchy into a similarity graph of documents and then formulates an optimization problem mapping each document into a low dimensional vector space. the new feature space preserves the intrinsic structure of the original taxonomy and thus provides a meaningful basis for various learning tasks like visualization and classification. our approach employs the information about class proximity and class specificity, and can naturally cope with multi-labeled documents. our empirical studies show very encouraging results on two real-world data sets, the new reuters (rcv1) benchmark and the swissprot protein database.
subject classification in the oxford english dictionary. the oxford english dictionary is a valuable source of lexical information and a rich testing ground for mining highly structured text.each entry is organized into a hierarchy of senses, which include definitions, labels and cited quotations.subject labels distinguish the subject classification of a sense, for example they signal how a word may be used in anthropology, music or computing.unfortunately subject labeling in the dictionary is incomplete. to overcome thisincompleteness, we attempt to classify the senses (i.e., definitions) in the dictionary by their subjects, using thecitations as an information guide.we report on four different approaches: k nearest neighbors, a standard classification technique; term weighting, an information retrieval method dealing with text; naïve bayes, a probabilistic method; and expectation maximization, an iterative probabilistic method.experimental performance of these methods is compared based on standard classification metrics.
a dynamic adaptive self-organising hybrid model for text clustering. clustering by document concepts is a powerful way ofretrieving information from a large number of documents.this task in general does not make any assumption on thedata distribution. in this paper, for this task we propose anew competitive self-organising (som) model, namelythe dynamic adaptive self-organising hybrid model(dash). the features of dash are a dynamic structure,hierarchical clustering, non-stationary data learning andparameter self-adjustment. all features are data-oriented:dash adjusts its behaviour not only by modifying itsparameters but also by an adaptive structure. thehierarchical growing architecture is a useful facility forsuch a competitive neural model which is designed fortext clustering. in this paper, we have presented a newtype of self-organising dynamic growing neural networkwhich can deal with the non-uniform data distributionand the non-stationary data sets and represent the innerdata structure by a hierarchical view.
partial elastic matching of time series. we consider the problem of elastic matching of time series. we propose an algorithm that determines a subsequence of a target time series that best matches a query series. in the proposed algorithm we map the problem of the best matching subsequence to the problem of a cheapest path in a dag (directed acyclic graph). the proposed approach allows us to also compute the optimal scale and translation of time series values, which is a nontrivial problem in the case of subsequence matching.
an efficient fuzzy c-means clustering algorithm. the fuzzy c-means (fcm) algorithm is commonly used for clustering.the performance of the fcm algorithm depends on the selection of the initial cluster center and/or the initial membership value.if a good initial cluster center that is close to the actual final clustercenter can be found, the fcm algorithm will converge very quickly and the processing time can be drastically.in this paper, we propose a novel algorithm for efficient clustering.this algorithm is a modified fcm called the psfcm algorithm, which significantly reduces the computation timerequired to partition a dataset into desired cluster.we find the actual cluster center by using a simplified set of the original complete dataset.it refines the initial value of the fcm algorithm to speed up the convergence time.our experiments show that the proposed psfcm algorithm isalgorithm.we also demonstrate that the quality of the proposed psfcm algorithm is the same as the fcm algorithm.
tree-structured partitioning based on splitting histograms of distances. we propose a novel clustering algorithm that is similar in spiritto classification trees. the data is recursively split using a criterionthat applies a discrete curve evolution method to the histogramof distances. the algorithm can be depicted throughtree diagrams with triple splits. leaf nodes represent eitherclusters or sets of observations that can not yet be clearly assignedto a cluster. after constructing the tree, unclassified datapoints are mapped to their closest clusters. the algorithm hasseveral advantages. first, it deals effectively with observationsthat can not be unambiguously assigned to a cluster by allowinga "margin of error". second, it automatically determinesthe number of clusters; apart from the margin of error the useronly needs to specify the minimal cluster size but not the numberof clusters. third, it is linear with respect to the number ofdata points and thus suitable for very large data sets. experimentsinvolving both simulated and real data from differentdomains show that the proposed method is effective and efficient.
mining generalized substructures from a set of labeled graphs. the problem of mining frequent itemsets in transactional data has been studied frequently and has yielded several algorithms that can find the itemsets within a limited amount of time. some of them can derive "generalized" frequent itemsets consisting of items at any level of a taxonomy. recently, several approaches have been proposed to mine frequent substructures (patterns) from a set of labeled graphs. the graph mining approaches are easily extended to mine generalized patterns where some vertices and/or edges have labels at any level of a taxonomy of the labels by extending the definition of "subgraph". however, the extended method outputs a massive set of the patterns most of which are over-generalized, which causes computation explosion. in this paper, an efficient and novel method is proposed to discover all frequent patterns which are not over-generalized from labeled graphs, when taxonomies on vertex and edge labels are available.
adapting classification rule induction to subgroup discovery. rule learning is typically used for solving classificationand prediction tasks. however, learning of classificationrules can be adapted also to subgroup discovery. this papershows how this can be achieved by modifying the coveringalgorithm and the search heuristic, performing probabilisticclassification of instances, and using an appropriatemeasure for evaluating the results of subgroup discovery.experimental evaluation of the cn2-sd subgroup discoveryalgorithm on 17 uci data sets demonstrates substantialreduction of the number of induced rules, increased rulecoverage and rule significance, as well as slight improvementsin terms of the area under the roc curve.
mining significant pairs of patterns from graph structures with class labels. in recent years, the problem of mining association rulesover frequent itemsets in transactional data has been frequentlystudied and yielded several algorithms that can findassociation rules within a limited amount of time. alsomore complex patterns have been considered such as orderedtrees, unordered trees, or labeled graphs. althoughsome approaches can efficiently derive all frequent subgraphsfrom a massive dataset of graphs, a subgraph orsubtree that is mathematically defined is not necessarily abetter knowledge representation. in this paper, we proposean efficient approach to discover significant rules to classifypositive and negative graph examples by estimating atight upper bound on the statistical metric. this approachabandons unimportant rules earlier in the computations,and thereby accelerates the overall performance. the performancehas been evaluated using real world datasets, andthe efficiency and effect of our approach has been confirmedwith respect to the amount of data and the computation time.
localized prediction of continuous target variables using hierarchical clustering. in this paper, we propose a novel technique for the efficientprediction of multiple continuous target variablesfrom high-dimensional and heterogeneous data sets usinga hierarchical clustering approach. the proposed approachconsists of three phases applied recursively:partitioning, localization and prediction. in thepartitioning step, similar target variables are groupedtogether by a clustering algorithm. in the localizationstep, a classification model is used to predict which groupof target variables is of particular interest. if theidentified group of target variables still contains a largenumber of target variables, the partitioning andlocalization steps are repeated recursively and theidentified group is further split into subgroups with moresimilar target variables. when the number of targetvariables per identified subgroup is sufficiently small, thethird step predicts target variables using localized predictionmodels built from only those data records thatcorrespond to the particular subgroup. experimentsperformed on the problem of damage prediction incomplex mechanical structures indicate that ourproposed hierarchical approach is computationally moreefficient and more accurate than straightforward methodsof predicting each target variable individually orsimultaneously using global prediction models.
fuzzy data mining: effect of fuzzy discretization. when we generate association rules, continuous attributes have to be discretized into intervals while our knowledge representation is not always based on such discretiztion.forexample, we usually use some linguistic terms (e.g., young, middle age, and old) for dividing our ages into somefuzzy categories.in this paper, we describe the extraction of linguistic association rules and examine the performanceof extracted rules.first we modify the definitions of the two basic measures (i.e., confidence and support) ofassociation rules for extracting linguistic association rules. the main difference between standard and linguistics association rules is the discretiztion of continuous attributes. we divide the domain interval of each attribute into some fuzzy discretiztion with standard on-fuzzy discretiztion through computer simulations on a pattern classificationproblem with many continuous attributes.the classification performance of extracted rules on unseen test patterns is examined under various conditions.simulation results show that linguistic association rules with rule weights have highgeneralization ability even when the domain of each continuous attribute is homogeneously partitioned.
clugo: a clustering algorithm for automated functional annotations based on gene ontology. we address the issue of providing highly informative and comprehensive annotations using information revealed by the structured vocabularies of gene ontology (go). for a target, a set of candidate terms for inferring target properties is collected and form a unique distribution on the go directed acyclic graph (dag). we propose a novel ontology-based clustering algorithm — clugo, which considers go hierarchical characteristics and the clustering of term distributions. by identifying significant groups in the distributions, clugo assigns comprehensive and correct annotations for a target. according to the results of experiments with automated sequence functional annotations, clugo represents a considerable improvement over our previous work — gomit in terms of recall while maintaining a similar level of precision. we conclude that given a go candidate term distribution, clugo is an efficient ontology-based clustering algorithm for selecting comprehensive and correct annotations.
extracting frequent subsequences from a single long data sequence: a novel anti-monotonic measure and a simple on-line algorithm. in this paper, we study frequent-subsequence extraction from a single very-long data-sequence. first we propose a novel frequency measure, called the total frequency, for counting multiple occurrences of a sequential pattern in a single data sequence. the total frequency is anti-monotonic, and makes it possible to count up pattern occurrences without duplication. moreover the total frequency has a good property for implementation based on the dynamic programming strategy. second we give a simple on-line algorithm for a specialized subsequence extraction problem, i.e., a problem with the infinite window-length. this specialized problem is considered to be a relaxation of the general-case problem, thus this fast on-line algorithm is important from the view of practical applications.
comine: efficient mining of correlated patterns. association rule mining often generates a huge numberof rules, but a majority of them either are redundantor don not reflect the tue correlation relationship amongdata objects.in this paper, we re-examine this problemand show that two interesting measures, all_confidence(denoted as \alpha) and coherence (denoted as \gamma), both disclosegenuine correlation relationships and can be computedefficiently.moreover, we propose two interestingalgorithms, comine(\alpha) and comine(\gamma), based onextensions of a pattern-growth methodology.our performancestudy shows that the comine algorithms havehigh performance in comparison with their apriori-basedcounterpart algorithms.
ad hoc association rule mining as sql3 queries. although there have been several encouraging attempts at developing methods for data mining using sql, simplicity and efficiency still remain significant impediments for furtherdevelopment. in this paper, we propose a significantly new approach and show that any object relational database can be mined for association rules without any restructuring orpreprocessing using only basic sql3 constructs and functions, and hence no additional machineries are necessary. in particular, we show that the cost of computing associationrules for a given database does not depend on support and confidence thresholds. more precisely, the set of large items can be computed using one simple join query and anaggregation once the set of all possible meets (least fix point) of item set patterns in the input table is known. the principal focus of this paper is to demonstrate that several sql3expressions exists for the mining of association rules.
finding maximal frequent itemsets over online data streams adaptively. due to the characteristics of a data stream, it is very important to confine the memory usage of a data mining process regardless of the amount of information generated in the data stream. for this purpose, this paper proposes a cp-tree (compressed-prefix tree)that can be effectively used in finding either frequent or maximal frequent itemsets over an online data stream. unlike a prefix tree, a node of a cp-tree can maintain the information of several itemsets together. based on this characteristic, the size of a cp-tree can be flexibly controlled by merging or splitting nodes. in this paper, a mining method employing a cp-tree is proposed and an adaptive memory utilization scheme is also presented in order to maximize the mining accuracy of the proposed method for confined memory space at all times. finally, the performance of the proposed method is analyzed by a series of experiments to identify its various characteristics.
implementation of a least fixpoint operator for fast mining of relational databases. recent research has focused on computing large item sets for association rule mining using sql3 least fixpoint computation, and by exploiting the monotonic nature of the sql3 aggregate functions such as sum and create view recursive constructs.such approaches allow us to view mining as an ad hoc querying exercise and treat the efficiency issue as an optimization problem.in this paper, we present a recursive implementation of a recently proposed least fixpoint operator for computing large item sets from object-relational databases.we present experimental evidence to show that our implementation compares well with several well-regarded and contemporary algorithms for large item set generation.