waashk/dblp huggingface dataset:
frequent sub-structure-based approaches for classifying chemical compounds. in this paper we study the problem of classifying chemical compounddatasets. we present a sub-structure-based classificationalgorithm that decouples the sub-structure discovery processfrom the classification model construction and uses frequentsubgraph discovery algorithms to find all topological and geometricsub-structures present in the dataset. the advantage ofour approach is that during classification model construction, allrelevant sub-structures are available allowing the classifier tointelligently select the most discriminating ones. the computationalscalability is ensured by the use of highly efficient frequentsubgraph discovery algorithms coupled with aggressive featureselection. our experimental evaluation on eight different classificationproblems shows that our approach is computationallyscalable and on the average, outperforms existing schemes by10% to 35%.
multi-view clustering. we consider clustering problems in which the available attributes can be split into two independent subsets, such that either subset suffices for learning. example applications of this multi-view setting include clustering of web pages which have an intrinsic view (the pages themselves) and an extrinsic view (e.g., anchor texts of inbound hyperlinks); multi-view learning has so far been studied in the context of classification. we develop and study partitioning and agglomerative, hierarchical multi-view clustering algorithms for text data. we find empirically that the multi-view versions of k-means and em greatly improve on their single-view counterparts. by contrast, we obtain negative results for agglomerative hierarchical multi-view clustering. our analysis explains this surprising phenomenon.
information theoretic clustering of sparse co-occurrence data. a novel approach to clustering co-occurrence data posesit as an optimization problem in information theory whichminimizes the resulting loss in mutual information. a divisiveclustering algorithm that monotonically reduces thisloss function was recently proposed. in this paper we showthat sparse high-dimensional data presents special challengeswhich can result in the algorithm getting stuck atpoor local minima. we propose two solutions to this problem:(a) a "prior" to overcome infinite relative entropy valuesas in the supervised naive bayes algorithm, and (b)local search to escape local minima. finally, we combinethese solutions to get a robust algorithm that is computationallyefficient. we present experimental results to showthat the proposed method is effective in clustering documentcollections and outperforms previous information-theoreticclustering approaches.
adaptive product normalization: using online learning for record linkage in comparison shopping. the problem of record linkage focuses on determining whether two object descriptions refer to the same underlying entity. addressing this problem effectively has many practical applications, e.g., elimination of duplicate records in databases and citation matching for scholarly articles. in this paper, we consider a new domain where the record linkage problem is manifested: internet comparison shopping. we address the resulting linkage setting that requires learning a similarity function between record pairs from streaming data. the learned similarity function is subsequently used in clustering to determine which records are co-referent and should be linked. we present an online machine learning method for addressing this problem, where a composite similarity function based on a linear combination of basis functions is learned incrementally. we illustrate the efficacy of this approach on several real-world datasets from an internet comparison shopping site, and show that our method is able to effectively learn various distance functions for product data with differing characteristics. we also provide experimental results that show the importance of considering multiple performance measures in record linkage evaluation.
iterative clustering of high dimensional text data augmented by local search. the k-means algorithm with cosine similarity, alsoknown as the spherical k-means algorithm, is a popularmethod for clustering document collections. however,spherical k-means can often yield qualitatively poor results,especially when cluster sizes are small, say 25-30 documentsper cluster, where it tends to get stuck at a localmaximum far away from the optimal solution. in this paper,we present a local search procedure, which we call"first-variation" that refines a given clustering by incrementallymoving data points between clusters, thus achievinga higher objective function value. an enhancement offirst variation allows a chain of such moves in a kernighan-linfashion and leads to a better local maximum. combiningthe enhanced first-variation with spherical k-meansyields a powerful "ping-pong" strategy that often qualitativelyimproves k-means clustering and is computationallyefficient. we present several experimental results to high-lightthe improvement achieved by our proposed algorithmin clustering high-dimensional and sparse text data.
better rules, few features: a semantic approach to selecting features from text. the choice of features used to represent a domain has a profound effect on the quality of the model produced; yet, few researchers have investigated the relationship between the features used to represent text and the quality of the final model. we explored this relationship formedical texts by comparing association rules based on features with three different semantic levels: (1) words (2) manually assigned keywords and (3) automatically selected medical concepts. our preliminary findings indicate that bi-directional association rules based onconcepts or keywords are more plausible and more useful than those based on word features. the concept and keyword representations also required 90% fewer features than the word representation. this drastic dimensionality reduction suggests that this approach is well suited to large textual corpus of medical text, such as parts of the web.
cluster merging and splitting in hierarchical clustering algorithms. hierarchical clustering constructs a hierarchy of clusterseither repeatedly mer in two smaller clusters into alarger one or splittin a larger cluster into smaller ones. the crucial step is how to best select the next cluster(s)to split or merge. here we provide a comprehensiveanalysis of selection methods and propose several newmethods. we perform extensive clustering experimentsto test 8 selection methods, and ?nd that the averagesimilarity is the best method in divisive clustering andminmax linkage is the best in agglomerativecluster balance is a key factor to achieve goodperformance. we also introduce the concept of objective function saturation and clustering target distanceto effectively assess the quality of clustering.
a user-driven and quality-oriented visualization for mining association rules. on account of the enormous amounts of rules that canbe produced by data mining algorithms, knowledgevalidation is one of the most problematic steps in anassociation rule discovery process.in order to findrelevant knowledge for decision-making, the user needs toreally rummage through the rules.visualization can bevery beneficial to support him/her in this task byimproving the intelligibility of the large rule sets andenabling the user to navigate inside them.in this article,we propose to answer the association rule validationproblem by designing a human-centered visualizationmethod for the rule rummaging task.this new approachbased on a specific rummaging model relies on ruleinterestingness measures and on interactive rule subsetfocusing and mining.we have implemented ourrepresentation by developing a first experimentalprototype called arvis.
a biobjective model to select features with good classification quality and low cost. in this paper we address a multi-group classification problem in which we want to take into account, together with the generalization ability, cots associated with the features. this cost is not limited to an economical payment, but can also refer to risk, computational effort, space requirements, etc. in order to get a good generalization ability, we use support vector machines (svm) as the basic mechanism by considering the maximization of the margin. we formulate the problem as a biobjective mixed integer problem, for which pareto optimal solutions can be obtained.
convex hull ensemble machine. we propose a new ensemble algorithm called "convexhull ensemble machine (chem)." chem in hilbert spaceis developed first and it is modified to regression and clas-sificationproblems. empirical studies show that in classi-ficationproblems chem has similar prediction accuracyas adaboost, but chem is much more robust to outputnoise. in regression problems, chem works competitivelywith other ensemble methods such as gradient boost andbagging.
using information-theoretic measures to assess association rule interestingness. assessing rules with interestingness measures is the cornerstone of successful applications of association rule discovery. however, there exists no information-theoretic measure which is adapted to the semantics of association rules. in this article, we present the directed information ratio (dir), a new rule interestingness measure which is based on information theory. dir is specially designed for association rules, and in particular it differentiates two opposite rules a → b and a → \mathop b\limits^ - . moreover, to our knowledge, dir is the only rule interestingness measure which rejects both independence and (what we call) equilibrium, i.e. it discards both the rules whose antecedent and consequent are negatively correlated, and the rules which have more counter-examples than examples. experimental studies show that dir is a very filtering measure, which is useful for association rule post-processing.
a min-max cut algorithm for graph partitioning and data clustering. an important application of graph partitioning is data clustering using a graph model - the pairwise similarities between all data objects form a weighted graph adjacency matrix that contains all necessary information for clustering. here we propose a new algorithm for graph partition with an objective function that follows the min-max clustering principle. the relaxed version of the optimization of the min-max cut objective function leads to the fiedler vector in spectral graph partition. theoretical analyses of min-max cut indicate that it leads to balanced partitions, and lower bonds are derived. the min-max cut algorithm is tested on news-group datasets and is found to outperform other current popular partitioning/clustering methods. the linkage-based refinements in the algorithm further improve the quality of clustering substantially. we also demonstrate that the linearized search order based on linkage differential is better than that based on the fiedler vector, providing another effectivepartition method.
text classification by boosting weak learners based on terms and concepts. document representations for text classification are typically based on the classical bag-of-words paradigm. this approach comes with deficiencies that motivate the integration of features on a higher semantic level than single words. in this paper we propose an enhancement of the classical document representation through concepts extracted from background knowledge. boosting is used for actual classification. experimental evaluations on two well known text corpora support our approach through consistent improvement of the results.
adaptive dimension reduction for clustering high dimensional data. it is well-known that for high dimensional data clustering, standard algorithms such as em and the k -meansare often trapped in local minimum. many initializationmethods were proposed to tackle this problem, but withonly limited success. in this paper we propose newapproach to resolve this problem by repeated dimension reductions such that k-means or em are performedonly in very low dimensions.cluster membership is utilized as a bridge between the reduced dimensional sub-space and the original space, providing flexibility andease of implementation. clustering analysis performedon highly overlapped gaussians, dna gene expressionprofiles and internet newsgroups demonstrate the effectiveness of the proposed algorithm.
high performance data mining using the nearest neighbor join. the similarity join has become an important database primitiveto support similarity search and data mining. a similarity joincombines two sets of complex objects such that the result containsall pairs of similar objects. well-known are two types of thesimilarity join, the distance range join where the user defines adistance threshold for the join, and the closest point query ork-distance join which retrieves the k most similar pairs. in thispaper, we investigate an important, third similarity join operationcalled k-nearest neighbor join which combines each point ofone point set with its k nearest neighbors in the other set. it hasbeen shown that many standard algorithms of knowledge discoveryin databases (kdd) such as k-means and k-medoid clustering,nearest neighbor classification, data cleansing, postprocessingof sampling-based data mining etc. can be implementedon top of the k-nn join operation to achieve performance improvementswithout affecting the quality of the result of these algorithms.we propose a new algorithm to compute the k-nearestneighbor join using the multipage index (mux), a specialized indexstructure for the similarity join. to reduce both cpu and i/ocost, we develop optimal loading and processing strategies.
incremental support vector machine construction. svms suffer from the problem of large memory requirement and cpu time when trained in batch mode on large data sets. we overcome these limitations, and at the same time make svms suitable for learning with data streams, by constructing incremental learning algorithms.we first introduce and compare different incremental learning techniques, and show that they are capable of producing performance results similar to the batch algorithm, and in some cases superior condensation properties. we then consider the problem of training svms using stream data. our objective is to maintain an updated representation of recent batches of data. we apply incremental schemes to the problem and show that their accuracy is comparable to the batch algorithm.
density connected clustering with local subspace preferences. many clustering algorithms tend to break down in high-dimensional feature spaces, because the clusters often exist only in specific subspaces (attribute subsets) of the original feature space. therefore, the task of projected clustering (or subspace clustering) has been defined recently. as a novel solution to tackle this problem, we propose the concept of local subspace preferences, which captures the main directions of high point density. using this concept we adopt density-based clustering to cope with high-dimensional data. in particular, we achieve the following advantages over existing approaches: our proposed method has a determinate result, does not depend on the order of processing, is robust against noise, performs only one single scan over the database, and is linear in the number of dimensions. a broad experimental evaluation shows that our approach yields results of significantly better quality than recent work on clustering high-dimensional data.
extensible markov model. a markov chain is a popular data modeling tool. this paper presents a variation of markov chain, namely extensible markov model (emm). by providing a dynamically adjustable structure, emm overcomes the problems caused by the static nature of the traditional markov chain. therefore, emms are particularly well suited to model spatiotemporal data such as network traffic, environmental data, weather data, and automobile traffic. performance studies using emms for spatiotemporal prediction problems show the advantages of this approach.
significance tests for patterns in continuous data. in this paper we consider the question of uncertainty of detected patterns in data mining. in particular, we develop statistical tests for patterns found in continuous data, indicating the significance of these patterns in terms of the probability that they have occurred by chance. we examine the performance of these tests on patterns detected in several large data sets, including a data set describing the locations of earthquakes in california and another describing flow cytometry measurements on phytoplankton.
modal-style operators in qualitative data analysis. we explore the usage of the modal possibility operator (andits dual necessity operator) in qualitative data analysis, andshow that it - quite literally - complements the derivationoperator of formal concept analysis; we also propose a newgeneralization of the rough set approximation operators. asan example for the applicability of the concepts we investigatethe morse data set which has been frequently studiedin multidimensional scaling procedures.
examiner: optimized level-wise frequent pattern mining with monotone constraint. the key point of this paper is that, in frequent patternmining, the most appropriate way of exploiting monotoneconstraints in conjunction with frequency is to use them inorder to reduce the problem input together with the searchspace. following this intuition, we introduce examiner, alevel-wise algorithm which exploits the real synergy of anti-monotoneand monotone constraints: the total benefit isgreater than the sum of the two individual benefits. examinergeneralizes the basic idea of the preprocessing algorithmexante, embedding such ideas at all levels ofan apriori-like computation. the resulting algorithm is thegeneralization of the apriori algorithm when a conjunctionof monotone constraints is conjoined to the frequency anti-monotoneconstraint. experimental results confirm that thisis, so far, the most efficient way of attacking the computationalproblem in analysis.
using representative-based clustering for nearest neighbor dataset editing. the goal of dataset editing in instance-based learning is to remove objects from a training set in order to increase the accuracy of a classifier. for example, wilson editing removes training examples that are misclassified by a nearest neighbor classifier so as to smooth the shape of the resulting decision boundaries. this paper revolves around the use of representative-based clustering algorithms for nearest neighbor dataset editing. we term this approach supervised clustering editing. the main idea is to replace a dataset by a set of cluster prototypes. a novel clustering approach called supervised clustering is introduced for this purpose. our empirical evaluation using eight uci datasets shows that both wilson and supervised clustering editing improve accuracy on more than 50% of the datasets tested. however, supervised clustering editing achieves four times higher compression rates than wilson editing.
on closed constrained frequent pattern mining. constrained frequent patterns and closed frequent patterns are two paradigms aimed at reducing the set of extracted patterns to a smaller, more interesting, subset. although a lot of work has been done with both these paradigms, there is still confusion around the mining problem obtained by joining closed and constrained frequent patterns in a unique framework. in this paper we shed light on this problem by providing a formal definition and a thorough characterization. wealso study computational issues and show how to combine the most recent results in both paradigms, providing a very efficient algorithm which exploits the two requirements (satisfying constraints and being closed) together at mining time in order to reduce the computation as much as possible.
usage-based pagerank for web personalization. recommendation algorithms aim at proposing "next" pages to a user based on her current visit and the past users' navigational patterns. in the vast majority of related algorithms, only the usage data are used to produce recommendations, whereas the structural properties of the web graph are ignored. we claim that taking also into account the web structure and using link analysis algorithms ameliorates the quality of recommendations. in this paper we present upr, a novel personalization algorithm which combines usage data and link analysis techniques for ranking and recommending web pages to the end user. using the web site's structure and its usage data we produce personalized navigational graph synopses (prng) to be used for applying upr and produce personalized recommendations. experimental results show that the accuracy of the recommendations is superior to pure usage-based approaches.
mining molecular fragments: finding relevant substructures of molecules. we present an algorithm to find fragments in a setof molecules that help to discriminate between differentclasses of, for instance, activity in a drug discovery context.instead of carrying out a brute-force search, our methodgenerates fragments by embedding them in all appropriatemolecules in parallel and prunes the search tree based ona local order of the atoms and bonds, which results in substantiallyfaster search by eliminating the need for frequent,computationally expensive reembeddings and by suppressingredundant search. we prove the usefulness of our algorithmby demonstrating the discovery of activity-relatedgroups of chemical compounds in the well-known nationalcancer institute's hiv-screening dataset.
bifold constraint-based mining by simultaneous monotone and anti-monotone checking. mining for frequent itemsets can generate an overwhelming number of patterns, often exceeding the size of the original transactional database. one way to deal with this issue is to set filters and interestingness measures. others advocate the use of constraints to apply to the patterns, either on the form of the patterns or on descriptors of the items in the patterns. however, typically the filtering of patterns based on these constraints is done as a post-processing phase. filtering the patterns post-mining adds a significant overhead, still suffers from the sheer size of the pattern set and loses the opportunity to exploit those constraints. in this paper we propose an approach that allows the efficientmining of frequent itemsets patterns, while pushing simultaneously both monotone and anti-monotone constraints during and at different strategic stages of the mining process. our implementation shows a significant improvement when considering the constraints early and a better performance over dualminer which also considers both types of constraints.
shortest-path kernels on graphs. data mining algorithms are facing the challenge to deal with an increasing number of complex objects. for graph data, a whole toolbox of data mining algorithms becomes available by defining a kernel function on instances of graphs. graph kernels based on walks, subtrees and cycles in graphs have been proposed so far. as a general problem, these kernels are either computationally expensive or limited in their expressiveness. we try to overcome this problem by defining expressive graph kernels which are based on paths. as the computation of all paths and longest paths in a graph is np-hard, we propose graph kernels based on shortest paths. these kernels are computable in polynomial time, retain expressivity and are still positive definite. in experiments on classification of graph models of proteins, our shortest-path kernels show significantly higher classificationaccuracy than walk-based kernels.