waashk/dblp huggingface dataset:
alpha galois lattices. in many applications there is a need to represent a large number of data by clustering them in a hierarchy of classes. our basic representation is a galois lattice, a structure that exhaustively represents the whole set of concepts that are distinguishable given the instance set and the representation language. what we propose here is a method to reduce the size of the lattice, and thus simplify our view of the data, while conserving its formal structure and exhaustivity. for that purpose we use a preliminary partition of the instance set, representing the association of a "type" to each instance. by redefining the notion of extent of a term in order to cope, to a certain degree (denoted as ¿), with this partition, we define a particular family of galois lattices denoted as alpha galois lattices. we also discuss the related implication rules defined as inclusion of such ¿-extents.
class decomposition via clustering: a new framework for low-variance classifiers. we propose a pre-processing step to classification thatapplies a clustering algorithm to the training set to discoverlocal patterns in the attribute or input space. wedemonstrate how this knowledge can be exploited to enhancethe predictive accuracy of simple classifiers. our focusis mainly on classifiers characterized by high bias butlow variance (e.g., linear classifiers); these classifiers experiencedifficulty in delineating class boundaries over theinput space when a class distributes in complex ways. decomposingclasses into clusters makes the new class distributioneasier to approximate and provides a viable way toreduce bias while limiting the growth in variance. experimentalresults on real-world domains show an advantagein predictive accuracy when clustering is used as a pre-processingstep to classification.
predicting rare events in temporal domains. temporal data mining aims at finding patterns in historicaldata. our work proposes an approach to extract temporalpatterns from data to predict the occurrence of targetevents, such as computer attacks on host networks, or fraudulenttransactions in financial institutions. our problemformulation exhibits two major challenges: 1) we assumeevents being characterized by categorical features and displayinguneven inter-arrival times; such an assumption fallsoutside the scope of classical time-series analysis, 2) weassume target events are highly infrequent; predictive techniquesmust deal with the class-imbalance problem. we pro-posean efficient algorithm that tackles the challenges aboveby transforming the event prediction problem into a searchfor all frequent eventsets preceding target events. the classimbalance problem is overcome by a search for patterns onthe minority class exclusively; the discrimination power ofpatterns is then validated against other classes. patternsare then combined into a rule-based model for prediction.our experimental analysis indicates the types of event sequenceswhere target events can be accurately predicted.
bootstrapping rule induction. most rule learning systems posit hard decision boundariesfor continuous attributes and point estimates of ruleaccuracy, with no measures of variance, which may seemarbitrary to a domain expert. these hard boundaries/pointschange with small perturbations to the training data. moreover,rule induction typically produces a large number ofrules that must be filtered and interpreted by an analyst.this paper describes a method of combining rules over multiplebootstrap replications of rule induction so as to reducethe total number of rules presented to an analyst and to providemeasures of variance to continuous attribute decisionboundaries and accuracy-point estimates. the method isillustrated with perioperative data.
interactive visualization and navigation in large data collections using the hyperbolic space. we propose the combination of two recently introducedmethods for the interactive visual data mining of largecollections of data. both, hyperbolic multi-dimensionalscaling (hmds) and hyperbolic self-organizing maps(hsom) employ the extraordinary advantages of the hyperbolicplane (h2): (i) the underlying space grows exponentiallywith its radius around each point - ideal for embeddinghigh-dimensional (or hierarchical) data; (ii) thepoincaré model of the ih2 exhibits a fish-eye perspectivewith a focus area and a context preserving surrounding; (iii)the mouse binding of focus-transfer allows intuitive interactivenavigation.the hmds approach extends multi-dimensional scalingand generates a spatial embedding of the data representingtheir dissimilarity structure as faithfully as possible. itis very suitable for interactive browsing of data object collections,but calls for batch precomputation for larger collectionsizes.the hsom is an extension of kohonen's self-organizingmap and generates a partitioning of the data collection assignedto an ih2 tessellating grid. while the algorithm'scomplexity is linear in the collection size, the data browsingis rigidly bound to the underlying grid.by integrating the two approaches we gain the synergetic effectof adding advantages of both. and the hybrid architectureuses consistently the ih2 visualization and navigationconcept. we present the successfully application to a textmining example involving the reuters-21578 text corpus.
alpha-surface and its application to mining protein data. given a finite set of points in three dimensional euclidean space r3, the subset that forms its surface could bedifferent when observed in different levels of details. in thispaper, we introduce a notion called a-surface. we presentan algorithm that extracts the a-surface from a finite set ofpoints in r3. we apply the algorithm to extracting the a-surfaces of proteins and discover patterns from these surface structures, using the pattern discovery algorithm wedeveloped earlier. we then use these patterns to classify theproteins. experimental results show the good performanceof the proposed approach.
delta b+ tree: indexing 3d point sets for pattern discovery. three-dimensional point sets can be used to representdata in different domains. given a database of 3d pointsets, pattern discovery looks for similar subsets that occurin multiple point sets. geometric hashing proved to be aneffective technique in discovering patterns in 3d point sets.however, there are also known shortcomings. we proposea new indexing technique called \delta b+trees. it is an extensionof b+-trees that stores point triplet information. itovercomes the shortcomings of the geometric hashing technique.we introduce four different ways of constructing thekey from a triplet. we give analytical comparison betweenthe new index structure and the geometric hashing technique.we also conduct experiments on both synthetic dataand real data to evaluate the performance.
classification through maximizing density. this paper presents a novel method for classification, which makes use of the models builtby the lattice machine (lm) [1,3 ]. the lm approximates data resulting in, as a model of data, a set of hyper tuples that are equilabelled, supported and maximal . the method presentedin this paper uses the lm model of data to classify new data with a view to maximising the density of the model. experiments show that this method, when used with the lm, outperforms the c2 algorithm in [3 ] and it is comparable to the c5.0 classification algorithm.
template-based privacy preservation in classification problems. in this paper, we present a template-based privacy preservation to protect against the threats caused by data mining abilities. the problem has dual goals: preserve the information for a wanted classification analysis and limit the usefulness of unwanted sensitive inferences that may be derived from the data. sensitive inferences are specified by a set of "privacy templates". each template specifies the sensitive information to be protected, a set of identifying attributes, and the maximum association between the two. we show that suppressing the domain values is an effective way to eliminate sensitive inferences. for a large data set, finding an optimal suppression is hard, since it requires optimization over all suppressions. we present an approximate but scalable solution. we demonstrate the effectiveness of this approach on real life data sets.
maintenance of sequential patterns for record deletion. in the past, we proposed an incremental mining algorithm for maintenance of sequential patterns based on the concept of pre-large sequences as new records were inserted. in this paper, we attempt to apply the concept of pre-large sequences to maintain sequentialpatterns as records are deleted. pre-large sequences are defined by a lower support threshold and an upper support threshold. they act as buffers to avoid the movements of sequential patterns directly from large to small and vice-versa. our proposed algorithm does notrequire rescanning original databases until the accumulative amount of deleted customer sequences exceeds a safety bound, which depends on database size. as databases grow larger, the numbers of deleted customer sequences allowed before database rescanningis required also grow. the proposed approach is thus efficient for a large database.
maintenance of sequential patterns for record modification using pre-large sequences. in the past, we proposed incremental miningalgorithms for maintenance of sequential patterns basedon the concept of pre-large sequences as records wereinserted or deleted. although maintenance of sequentialpatterns for record modification can be performed byusage of the deletion procedure and then the insertionprocedure, twice computation time of a single procedureis needed. in this paper, we thus attempt to apply theconcept of pre-large sequences to maintain sequentialpatterns as records are modified. the proposed algorithmdoes not require rescanning original databases until theaccumulative amount of modified customer sequencesexceeds a safety bound derived by pre-large concept. asdatabases grow larger, the numbers of modified customersequences allowed before database rescanning isrequired also grow.
an immune neural network used for classification. based on analyzing the immune phenomena in nature and utilizing performances of ann, a novel network model, i.e., an immune neural network (inn), is proposed which integrates the immune mechanism and the function of neural information processing. the learning algorithm of inn is mainly about the selection of an excitation function and an adaptive algorithm of the network.
summary: efficiently summarizing transactions for clustering. frequent itemset mining was initially proposed and has been studied extensively in the context of association rule mining. in recent years, several studies have also extended its applicationto the transaction (or document) classification and clustering. however, most of the frequent-itemset based clustering algorithms need to first mine a large intermediate set of frequent itemsets in order to identify a subset of the most promising ones that can be used for clustering. in this paper, we study how to directly find a subset of high quality frequent itemsets that can be used as a concise summary of the transaction database and to clusterthe categorical data. by exploring some properties of the subset of itemsets that we are interested in, we proposed several search space pruning methods and designed an efficient algorithm called summary. our empirical results have shown that summary runs very fast even when the minimum support is extremely low and scales very well with respect to the database size, and surprisingly, as a pure frequent itemset mining algorithm it is very effectivein clustering the categorical data and smmarizing the dense transaction databases.
mining associations by pattern structure in large relational tables. association rule mining aims at discovering patternswhose support is beyond a given threshold. mining patternscomposed of items described by an arbitrary subset ofattributes in a large relational table represents a new challengeand has various practical applications, including theevent management systems that motivated this work. theattribute combinations that define the items in a pattern providethe structural information of the pattern. current associationalgorithms do not make full use of the structuralinformation of the patterns: the information is either lostafter it is encoded with attribute values, or is constrainedby a given hierarchy or taxonomy. pattern structures conveyimportant knowledge about the patterns. in this paper,we present a novel architecture that organizes the miningspace based on pattern structures. by exploiting the inter-relationshipsamong pattern structures, execution times formining can be reduced significantly. this advantage isdemonstrated by our experiments using both synthetic andreal-life datasets.
comparison of lazy bayesian rule and tree-augmented bayesian learning. the naive bayes classifier is widely used in interactiveapplications due to its computational efficiency, direct theoreticalbase, and competitive accuracy. however, its attributeindependence assumption can result in sub-optimalaccuracy. a number of techniques have explored simple relaxationsof the attribute independence assumption in or-derto increase accuracy. among these, the lazy bayesianrule () and the tree-augmented naive bayes ()have demonstrated strong prediction accuracy. however,their relative performance has never been evaluated. thispaper compares and contrasts these two techniques, findingthat they have comparable accuracy and hence shouldbe selected according to computational profile. lbr is desirablewhen small numbers of objects are to be classifiedwhile tan is desirable when large numbers of objects areto be classified.
approximate inverse frequent itemset mining: privacy, complexity, and approximation. in order to generate synthetic basket datasets for better benchmark testing, it is important to integrate characteristics from real-life databases into the synthetic basket datasets. the characteristics that could be used for this purpose include the frequent itemsets and association rules. the problem of generating synthetic basket datasets from frequent itemsets is generally referred to as inverse frequent itemset mining. in this paper, we show that the problem of approximate inverse frequent itemset mining is np-complete. then we propose and analyze an approximate algorithm for approximate inverse frequent itemset mining, and discuss privacy issues related to the synthetic basket dataset. in particular, we propose an approximate algorithm to determine the privacy leakage in a synthetic basket dataset.
on reducing classifier granularity in mining concept-drifting data streams. many applications use classification models on streaming data to detect actionable alerts. due to concept drifts in the underlying data, how to maintain a model's up-to-dateness has become one of the most challenging tasks in mining data streams. state of the art approaches, including both the incrementally updated classifiers and the ensemble classifiers, have proved that model update is a very costly process. in this paper, we introduce the concept of model granularity. we show that reducing model granularity will reduce model update cost. indeed, models of fine granularity enable us to efficiently pinpoint local components in the model that are affected by the concept drift. it also enables us to derive new components that can easily integrate with the model to reflect the current data distribution, thus avoiding expensive updates on a global scale. experiments on real and synthetic data show that our approach is able to maintain good prediction accuracy at a fraction of model updating cost of state of the art approaches.
ssdt: a scalable subspace-splitting classifier for biased data. decision trees are one of the most extensively used data mining models. recently, a number of efficient, scalable algorithms for constructing decision trees on large disk-resident dataset have been introduced. in this paper, we study the problem of learning scalable decision trees from datasets with biased class distribution. our objective is to build decision trees that are ore concise and oreinterpretable while maintaining the scalability of the model.to achieve this, our approach searches for subspace clusters of data cases of the biased class to enable multivariate splittings based on weighted distances to such clusters. in orderto build concise and interpretable models, other approaches including multivariate decision trees and association rules, often introduce scalability and performance issues. the ssdt algorithm we present achieves the objective without loss in efficiency, scalability, and accuracy.
bottom-up generalization: a data mining solution to privacy protection. the well-known privacy-preserved data mining modifies existing data mining techniques to randomized data. in this paper, we investigate data mining as a technique for masking data, therefore, termed data mining based privacy protection. this approach incorporates partially the requirement of a targeted data mining task into the process of masking data so that essential structure is preserved in the masked data. the idea is simple but novel: we explore the data generalization concept from data mining as a way to hide detailed information, rather than discover trends and patterns. once the data is masked, standard data mining techniques can be applied without modification. our work demonstrated another positive use of data mining technology: not only can it discover useful patterns, but also mask private information. we consider the following privacy problem: a data holder wants to release a version of datafor building classification models, but wants to protect against linking the released data to an external source for inferring sensitive information. we adapt an iterative bottom-up generalization from data mining to generalize the data. the generalized data remains useful to classification but becomes difficult to link to other sources. the generalization space is specified by a hierarchical structure of generalizations. a key is identifying the best generalization to climb up the hierarchy at each iteration. enumerating all candidate generalizations is impractical. we present a scalable solution that examines at most one generalization in each iteration for each attribute involved in the linking.
concept tree based clustering visualization with shaded similarity matrices. one of the problems with existing clustering methods isthat the interpretation of clusters may be difficult. two differentapproaches have been used to solve this problem:conceptual clustering in machine learning and clusteringvisualization in statistics and graphics. the purpose of thispaper is to investigate the benefits of combining clusteringvisualization and conceptual clustering to obtain bettercluster interpretations. in our research we have combinedconcept trees for conceptual clustering with shaded similaritymatrices for visualization. experimentation shows thatthe two interpretation approaches can complement eachother to help us understand data better.
meta-patterns: revealing hidden periodic patterns. discovery of periodic patterns in time series data has become an active research area with many applications. these patterns can be hierarchical in nature, where higher level pattern may consist of repetitions of lower level patterns.unfortunately, the presence of noise m y prevent these higher level patterns from being recognized in the sense that two portions (of data sequence) that support the same (high level) pattern may have different layouts of occurrences of basic symbols. there may not exist any common representation in terms of raw symbol combinations; and hence such (high level) pattern may not be expressed by any previous model (defined on raw symbols or symbol combinations) and would not be properly recognized by any existing method. in this paper, we propose novel model, namely meta-pattern, to capture these high level patterns. as more flexible model, the number of potential meta-patterns could be very large. a substantial difficulty lies on how to identify the proper pattern candidates. however, the well-known apriori property is not able to provide sufficient pruning power. a new property, namely component location property, is identified and used to conduct the candidate generation so that an efficient computation-based mining algorithm can be developed. last but not least, we apply our algorithm to some real and synthetic sequences and some interesting patterns are discovered.
a bernoulli relational model for nonlinear embedding. the notion of relations is extremely important in mathematics. in this paper, we use relations to describe the embedding problem and propose a novel stochastic relational model for nonlinear embedding. given some relation among points in a high-dimensional space, we start from preserving the same relation in a low embedded space and model the relation as probabilistic distributions over these two spaces, respectively. we illustrate that the stochastic neighbor embedding and the gaussian process latent variable model can be derived from our relational model. moreover we devise a new stochastic embedding model and refer to it as bernoulli relational embedding (bre). bre's ability in nonlinear dimensionality reduction is illustrated on a set of synthetic data and collections of bitmaps of handwritten digits and face images.
mining quantitative frequent itemsets using adaptive density-based subspace clustering. a novel approach to subspace clustering is proposed to exhaustively and efficiently mine quantitative frequent itemsets (qfis) from massive transaction data¹. for the computational tractability, our approach introduces adaptive density-based and apriori-like algorithm. its outstanding performance is shown through numerical experiments.
atomic wedgie: efficient query filtering for streaming times series. in many applications it is desirable to monitor a streaming time series for predefined patterns. in domains as diverse as the monitoring of space telemetry, patient intensive care data, and insect populations, where data streams at a high rate and the number of predefined patterns is large, it may be impossible for the comparison algorithm to keep up. we propose a novel technique that exploits the commonality among the predefined patterns to allow monitoring at higher bandwidths, while maintaining a guarantee of no false dismissals. our approach is based on the widely used envelope-based lower bounding technique. extensive experiments demonstrate that our approach achieves tremendous improvements in performance in the offline case, and significant improvements in the fastest possible arrival rate of the data stream that can be processed with guaranteed no false dismissal.
using boosting to simplify classification models. ensemble classification techniques such as bagging ,boosting and arcingalgorithms have been shown to lead to reduced classification error on unseencases and seem immune t the problem of overfitting. several explanations forthe reduction in generalisation error have been presented, with authors morerecently defining and applying diagnostics such as edge and margin [4,9,10 ].these measures pr vide insight into the behaviour of ensemble classifiers but can they be exploited further?
an incremental approach to building a cluster hierarchy. in this paper we present a novel incremental hierarchicalclustering (ihc) algorithm. our approach aims to constructa hierarchy that satisfies the homogeneity and themonotonicity properties. working in a bottom-up fashion,a new instance is placed in the hierarchy and a sequence ofhierarchy restructuring process is performed only in regionsthat have been affected by the presence of the new instance.the experimental results on a variety of domains demonstratethat our algorithm is not sensitive to input ordering,can produce a quality cluster hierarchy, and is efficient interms of its computational time.