waashk/dblp huggingface dataset:
op-cluster: clustering by tendency in high dimensional space. clustering is the process of grouping a set of objects intoclasses of similar objects. because of unknownness of thehidden patterns in the data sets, the definition of similarityis very subtle. until recently, similarity measures are typicallybased on distances, e.g euclidean distance and cosinedistance. in this paper, we propose a flexible yet powerfulclustering model, namely op-cluster (order preservingcluster). under this new model, two objects are similaron a subset of dimensions if the values of these twoobjects induce the same relative order of those dimensions.such a cluster might arise when the expression levels of (co-regulated)genes can rise or fall synchronously in responseto a sequence of environment stimuli. hence, discovery ofop-cluster is essential in revealing significant gene regulatorynetworks. a deterministic algorithm is designed andimplemented to discover all the significant op-clusters. aset of extensive experiments has been done on several realbiological data sets to demonstrate its effectiveness and efficiencyin detecting co-regulated patterns.
efficient progressive sampling for association rules. in data mining, sampling has often been suggested as aneffective tool to reduce the size of the dataset operated atsome cost to accuracy. however, this loss to accuracy isoften difficult to measure and characterize since the exactnature of the learning curve (accuracy vs. sample size) isparameter and data dependent, i.e., we do not know aprioriwhat sample size is needed to achieve a desired accuracyon a particular dataset for a particular set of parameters.in this article we propose the use of progressive sampling todetermine the required sample size for association rule mining.we first show that a naive application of progressivesampling is not very efficient for association rule mining.we then present a refinement based on equivalence classes,that seems to work extremely well in practice and is able toconverge to the desired sample size very quickly and veryaccurately. an additional novelty of our approach is thedefinition of a support-sensitive, interactive measure of accuracyacross progressive samples.
rpcl-based local pca algorithm. mining local structure is important in data analysis.gaussian mixture is able to describe local structurethrough the covariance matrices, but when used on high dimensional data, fitly specifying such a large number of d(d + 1)=2 free elements in each covariance matrix is difficult. in this paper, by constraining the covariance matrixin decomposed orthonormal form, we propos a local pcaalgorithm to tackle this problem in help of rpcl competitivelearning, which can automatically determine the number of local structure.
efficient discovery of common substructures in macromolecules. biological macromolecules play a fundamental role indisease; therefore, they are of great interest to fields such aspharmacology and chemical genomics. yet due to macromolecules'complexity, development of effective techniquesfor elucidating structure-function macromolecular relationshipshas been ill explored. previous techniques have eitherfocused on sequence analysis, which only approximatesstructure-function relationships, or on small coor-dinatedatasets, which does not scale to large datasets orhandle noise. we present a novel scalable approach toefficiently discover macromolecule substructures based onthree-dimensional coordinate data, without domain-specificknowledge. the approach combines structure-based frequentpattern discovery with search space reduction andcoordinate noise handling. we analyze computational performancecompared to traditional approaches, validate thatour approach can discover meaningful substructures innoisy macromolecule data by automated discovery of primaryand secondary protein structures, and show that ourtechnique is superior to sequence-based approaches at determiningstructural, and thus functional, similarity be-tweenproteins.
text representation: from vector to tensor. in this paper, we propose a text representation model, tensor space model (tsm), which models the text by multilinear algebraic high-order tensor instead of the traditional vector. supported by techniques of multilinear algebra, tsm offers a potent mathematical framework for analyzing the multifactor structures. tsm is further supported by certain introduced particular operations and presented tools, such as the high-order singular value decomposition (hosvd) for dimension reduction and other applications. experimental results on the 20 newsgroups dataset show that tsm is constantly better than vsm for text classification.
protecting sensitive knowledge by data sanitization. in this paper, we address the problem of protecting somesensitive knowledge in transactional databases. the challengeis on protecting actionable knowledge for strategicdecisions, but at the same time not losing the great benefitof association rule mining. to accomplish that, we introducea new, efficient one-scan algorithm that meets privacyprotection and accuracy in association rule mining, withoutputting at risk the effectiveness of the data mining per se.
learning conditional independence tree for ranking. accurate ranking is desired in many real-world data mining applications. traditional learning algorithms, however, aim only at high classification accuracy. it has been observed that both traditional decision trees and naive bayes produce good classification accuracy but poor probability estimates. in this paper, we use a new model, conditional independence tree (citree), which is a combination of decision tree and naive bayes and more suitable for ranking and more learnable in practice. we propose a novel algorithm for learning citree for ranking, and the experiments show that the citree algorithm outperforms the state-of-the-art decision tree learning algorithm c4.4 and naive bayes significantly in yielding accurate rankings. our work provides an effective data mining algorithm for applications in which an accurate ranking is required.
closing the loop: an agenda- and justification-based framework for selecting the next discovery task to perform. we propose and evaluate an agenda-and justification-basedarchitecture for discovery systems that selects the next tasks to perform. this framework has manydesirable properties: (1) it facilitates the encoding of general discovery strategies using a variety of backgroundknowledge, (2) t reasons about the appropriateness of the tasks being considered, and (3) it tailors its behavior toward a user 's interests. a prototype discovery program called hamb demonstrates that both reasons andestimates of interestingness contribute to performance in the domains of protein crystallization and patient rehabilitation.
peruse: an unsupervised algorithm for finding recurrig patterns in time series. this paper describes peruse, an unsupervised algorithm for finding recurring patterns in time series.it was initially developed and tested with sensor data from a mobile robot, i.e. noisy, re-valued, multivariate time series with variable intervals between observations.the pattern discovery problem is decomposed into two sub-problems: (1) a supervised learning problem in which a teacher provised exemplars of patterns and labels time series according to whether they contain the patterns; (2)an un supervised learning problem in which the time series are used to generate an approximation to the teacher.experimental results show that peruse can discover patterns in audio data corresponding to qualitatively distinct outcomes of taking actions.
sparse kernel least squares classifier. in this paper, we propose a new learning algorithm for constructing kernel least squares classifier. the new algorithm adopts a recursive learning way and a novel two-step sparsification procedure is incorporated into learning phase. these two most importantfeatures not only provide a feasible approach for large-scale problems as it is not necessary to store the entire kernel matrix, but also produce a very sparse model with fast training and testing time. experimental results on a number of data classification problems are presented to demonstrate the competitiveness of new proposed algorithm.
mining motifs in massive time series databases. the problem of efficiently locating previously knownpatterns in a time series database (i.e., query by content) hasreceived much attention and may now largely be regardedas a solved problem. however, from a knowledge discoveryviewpoint, a more interesting problem is the enumeration ofpreviously unknown, frequently occurring patterns. we callsuch patterns "motifs", because of their close analogy totheir discrete counterparts in computation biology. anefficient motif discovery algorithm for time series would beuseful as a tool for summarizing and visualizing massivetime series databases. in addition it could be used as asubroutine in various other data mining tasks, including thediscovery of association rules, clustering and classification.in this work we carefully motivate, then introduce, a non-trivialdefinition of time series motifs. we propose anefficient algorithm to discover them, and we demonstrate theutility and efficiency of our approach on several real worlddatasets.
parsing without a grammar: making sense of unknown file formats. the thousands of specialized structured file formats inuse today present a substantial barrier to freely exchanginginformation between applications programs. we considerthe problem of deducing such basic features as thewhitespace characters, bracketing delimiter symbols, andself-delimiter characters of a given file format from one ormore example files. we demonstrate that for sufficientlylarge example files, we can typically identify the basic featuresof interest.
sequence modeling with mixtures of conditional maximum entropy distributions. we present a novel approach to modeling sequences usingmixtures of conditional maximum entropy (maxent) distributions.our method generalizes the mixture of first-ordermarkov models by including the "long-term" dependenciesin model components.the "long-term" dependenciesare represented by the frequently used in the naturallanguage processing (nlp) domain probabilistic triggersor rules (suc as "a occured k positions back" \longrightarrow"the current symbol is b" with probability p).the maxentframework is then used to create a coherent global probabilisticmodel from all selected triggers.in this paper, weenhance this formalism by using probabilistic mixtures withmaxent models as components, thus representing hidden orunobserved effects in the data.we demonstrate how ourmixture of conditional maxent models can be learned fromdata using the generalized em algorithm that scales linearlyin the dimensions of the data and the number of mixturecomponents.we present empirical results on the simulatedand real-world data sets and demonstrate that theproposed approach enables us to create better quality modelsthan the mixtures of first-order markov models and resistoverfitting and curse of dimensionality that would inevitablypresent themselves for the higher order markov models.
combining multiple clusterings by soft correspondence. combining multiple clusterings arises in various important data mining scenarios. however, finding a consensus clustering from multiple clusterings is a challenging task because there is no explicit correspondence between the classes from different clusterings. we present a new framework based on soft correspondence to directly address the correspondence problem in combining multiple clusterings. under this framework, we propose a novel algorithm that iteratively computes the consensus clustering and correspondence matrices using multiplicative updating rules. this algorithm provides a final consensus clustering as well as correspondence matrices that gives intuitive interpretation of the relations between the consensus clustering and each clustering from clustering ensembles. extensive experimental evaluations also demonstrate the effectiveness and potential of this framework as well as the algorithm for discovering a consensus clustering from multiple clusterings.
experimentation and self learning in continuous database marketing. we present a method for continuous database marketingthat identifies target customers for a number of marketingoffers using predictive models. the algorithm thenselects the appropriate offer for the customer. experimentaldesign principles are encapsulated to capturemore information that will be used to monitor and refinethe predictive models. the updated predictive models arethen used for the next round of marketing offers.
reviewing relief and its extensions: a new approach for estimating attributes considering high-correlated features. relief algorithm [4], [5] and its extensions [8], [9]are some of the most known filter methods for estimatingthe quality of attributes in classification problems dealingwith both dependent and independent features. thesemethods attend to find all meaningful features for eachproblem (both weakly and strongly ones [6]) so they areusually employed like a first stage for detecting irrelevantattributes. nevertheless, in this paper we checked thatrelief-family algorithms present some importantlimitations that could distort the selection of the finalfeatures' subset, specially in the presence of high-correlatedattributes. to overcome these difficulties, anew approach has been developed (wacsa algorithm),which performance and validity are verified on well-knowndata sets.
on computing condensed frequent pattern bases. frequent pattern mining has been studied extensively.however, the effectiveness and efficiency of this mining isoften limited, since the number of frequent patterns generatedis often too large. in many applications it is sufficientto generate and examine only frequent patterns with supportfrequency in close-enough approximation instead of in fullprecision. such a compact but close-enough frequent patternbase is called a condensed frequent patterns-base.in this paper, we propose and examine several alternativesat the design, representation, and implementation ofsuch condensed frequent pattern-bases. a few algorithmsfor computing such pattern-bases are proposed. their effectivenessat pattern compression and their efficient computationmethods are investigated. a systematic performancestudy is conducted on different kinds of databases,which demonstrates the effectiveness and efficiency of ourapproach at handling frequent pattern mining in largedatabases.
parallel algorithms for distance-based and density-based outliers. an outlier is an observation that deviates so much from other observations as to arouse suspicion that it was generated by a different mechanism. outlier detection has many applications, such as data cleaning, fraud detection and network intrusion. the existence of outliers can indicate individuals or groups that exhibit a behavior that is very different from most of the individuals of the dataset. in this paper we design two parallel algorithms, the first one is for finding out distance-based outliers based on nested loops along with randomization and the use of a pruning rule. the second parallel algorithm is for detecting density-based local outliers. in both cases data parallelism is used. we show that both algorithms reach near linear speedup. our algorithms are tested on four real-world datasets coming from the machine learning database repository at the uci.
h-mine: hyper-structure mining of frequent patterns in large databases. methods for efficient mining of frequent patterns have been studied extensively by many researchers. however, the previously proposed methods still encounter someperformance bottlenecks when mining databases with different data characteristics, such as dense vs. sparse, long vs. short patterns, memory-based vs. disk-based, etc.in this study, we propose a simple and novel hyper-linkeddata structure, h-struct , and a new mining algorithm, h-mine ,which takes advantage of this data structure anddynamically adjusts links in the mining process. a distinct feature of this method is that it has very limitedand precisely predictable space overhead and runs really fast in memory-based setting. moreover, it ca be scaled up to very large databases by database partitioning, and whenthe data set becomes dense,(conditional)fp-trees can be constructed dynamically as part of the mining process. our study shows that h-mine has high performance in various kinds of data, outperforms the previously developedalgorithms in different settings, and is highly scalable in mining large databases. this study also proposes a new datamining methodology, space-preserving mining ,which mayhave strong impact in the future development of efficient and scalable data mining methods.
algorithms for spatial outlier detection. a spatial outlier is a spatially referenced object whosenon-spatial attribute values are significantly different fromthe values of its neighborhood. identification of spatial outlierscan lead to the discovery of unexpected, interesting,and useful spatial patterns for further analysis. one drawbackof existing methods is that normal objects tend to befalsely detected as spatial outliers when their neighborhoodcontains true spatial outliers. in this paper, we proposea suite of spatial outlier detection algorithms to overcomethis disadvantage. we formulate the spatial outlier detectionproblem in a general way and design algorithms whichcan accurately detect spatial outliers. in addition, usinga real-world census data set, we demonstrate that our approachescan not only avoid detecting false spatial outliersbut also find true spatial outliers ignored by existing methods.
efficiently mining frequent closed partial orders. mining ordering information from sequence data is an important data mining task. sequential pattern mining [1] can be regarded as mining frequent segments of total orders from sequence data. however, sequential patterns are often insufficient to concisely capture the general ordering information.
anchor text mining for translation of web queries. this paper presents an approach to automatically extracting translations of web query terms through mining of web anchor texts and link structures. one of the existing difficulties in cross-language information retrieval (clir)and web search is the lack of the appropriate translations of new terminology and proper names. such a difficult problem can be effectively alleviated by our proposed approach, and the resource of anchor texts in the web is proven a valuable corpus for this kind of term translation.
maple: a fast algorithm for maximal pattern-based clustering. pattern-based clustering is important in many applications,such as dna micro-array data analysis, automaticrecommendation systems and target marketing systems.however, pattern-based clustering in large databasesis challenging. on the one hand, there can be a huge numberof clusters and many of them can be redundant and thusmake the pattern-based clustering ineffective. on the otherhand, the previous proposed methods may not be efficient orscalable in mining large databases.in this paper, we study the problem of maximal pattern-basedclustering. redundant clusters are avoided completelyby mining only the maximal pattern-based clusters.maple, an efficient and scalable mining algorithm is developed.it conducts a depth-first, divide-and-conquer searchand prunes unnecessary branches smartly. our extensiveperformance study on both synthetic data sets and real datasets shows that maximal pattern-based clustering is effective.it reduces the number of clusters substantially. moreover,maple is more efficient and scalable than the previouslyproposed pattern-based clustering methods in mininglarge databases.
bit reduction support vector machine. support vector machines are very accurate classifiers and have been widely used in many applications. however, the training and to a lesser extent prediction time of support vector machines on very large data sets can be very long. this paper presents a fast compression method to scale up support vector machines to large data sets. a simple bit reduction method is applied to reduce the cardinality of the data by weighting representative examples. we then develop support vector machines which may be trained on weighted data. experiments indicate that the bit reduction support vector machine produces a significant reduction in the time required for both training and prediction with minimum loss in accuracy. it is also shown to be more accurate than random sampling, when the data is not over-compressed.
schism: a new approach for interesting subspace mining. high-dimensional data pose challenges to traditional clustering algorithms due to their inherent sparsity and data tend to cluster in different and possibly overlapping subspaces of the entire feature space. finding such subspaces is called subspace mining. we present schism, a new algorithm for mining interesting subspaces, using the notions of support and chernoff-hoeffding bounds. we use a vertical representation of the dataset, and use a depth-first search with backtracking to find maximal interesting subspaces. we test our algorithm on a number of high-dimensional synthetic and real datasets to test its effectiveness.
mining mutually dependent patterns. in some domains, such as isolating problems in computer net-worksand discovering stock market irregularities, there is more interest inpatterns consisting of infrequent, but highly correlated items rather thanpatterns that occur frequently (as defined by minsup, the minimum supportlevel). herein, we describe the m-pattern, a new pattern that is definedin terms of minp, the minimum probability of mutual dependence of itemsin the pattern. we show that all infrequent m-pattern can be discovered byan efficient algorithm that makes use of: (a) a linear algorithm to qualifyan m-pattern; (b) an effective technique for candidate pruning based on anecessary condition for the presence of an m-pattern; and (c) a level-wisesearch for m-pattern discovery (which is possible because m-patterns aredownward closed). further, we consider frequent m-patterns, which aredefined in terms of both minp and minsup. using synthetic data, we studythe scalability of our algorithm. then, we apply our algorithm to data froma production computer network both to show the m-patterns present andto contrast with frequent patterns. we show that when minp_0, our algorithmis equivalent to finding frequent patterns. however, with a larger minp, our algorithm yields a modest number of highly correlated items, which makes it possible to mine for infrequent but highly correlated item-sets. to date, many actionable m-patterns have been discovered in production systems.
automatic web page classification in a dynamic and hierarchical way. automatic classification of web pages is an effectiveway to deal with the difficulty of retrieving informationfrom the internet. although there are many automaticclassification algorithms and systems that have beenproposed, most of them ignore the conflict between thefixed number of categories and the growing number ofweb pages going into the system. they also requiresearching through all existing categories to make anyclassification. we propose a dynamic and hierarchicalclassification system that is capable of adding newcategories as required, organizing the web pages into atree structure, and classifying web pages by searchingthrough only one path of the tree structure. our testresults show that our proposed single-path searchtechnique reduces the search complexity and increasesthe accuracy by 6% comparing to related algorithms. ourdynamic-category expansion technique also achievessatisfying results on adding new categories into oursystem as required.