waashk/dblp huggingface dataset:
on the lower bound of local optimums in k-means algorithm. the k-means algorithm is a popular clustering method used in many different fields of computer science, such as data mining, machine learning and information retrieval. however, the k-means algorithm is very likely to converge to some local optimum which is much worse than the desired global optimal solution. to overcome this problem, current k-means algorithm and its variants usually run many times with different initial centers to avoid being trapped in local optimums that are of unacceptable quality. in this paper, we propose an efficient method to compute a lower bound on the cost of the local optimum from the current center set. after every k-means iteration, k-means algorithm can halt the procedure if the lower bound of the cost at the future local optimum is worse than the best solution that has already been computed so far. although such a lower bound computation incurs some extra time consumption in the iterations, extensive experiments on both synthetic and real data sets show that this method can greatly prune the unnecessary iterations and improve the efficiency of the algorithm in most of the data sets, especially with high dimensionality and large k.
dimension reduction for supervised ordering. ordered lists of objects are widely used as representational forms. such ordered objects include web search results and best-seller lists. techniques for processing such ordinal data are being developed, particularly methods for a supervised ordering task: i.e., learning functions used to sort objects from sample orders. in this article, we propose two dimension reduction methods specifically designed to improve prediction performance in a supervised ordering task.
boosting for learning multiple classes with imbalanced class distribution. classification of data with imbalanced class distribution has posed a significant drawback of the performance attainable by most standard classifier learning algorithms, which assume a relatively balanced class distribution and equal misclassification costs. this learning difficulty attracts a lot of research interests. most efforts concentrate on bi-class problems. however, bi-class is not the only scenario where the class imbalance problem prevails. reported solutions for bi-class applications are not applicable to multi-class problems. in this paper, we develop a cost-sensitive boosting algorithm to improve the classification performance of imbalanced data involving multiple classes. one barrier of applying the cost-sensitive boosting algorithm to the imbalanced data is that the cost matrix is often unavailable for a problem domain. to solve this problem, we apply genetic algorithm to search the optimum cost setup of each class. empirical tests show that the proposed cost-sensitive boosting algorithm improves the classification performances of imbalanced data sets significantly.
bitspade: a lattice-based sequential pattern mining algorithm using bitmap representation. sequential pattern mining allows to discover temporal relationship between items within a database. the patterns can then be used to generate association rules. when the databases are very large, the execution speed and the memory usage of the mining algorithm become critical parameters. previous research has focused on either one of the two parameters. in this paper, we present bitspade, a novel algorithm that combines the best features of spam, one of the fastest algorithm, and spade, one of the most memory efficient algorithm. moreover, we introduce a new pruning strategy that enables bitspade to reach high performances. experimental evaluations showed that bitspade ensures an efficient tradeoff between speed and memory usage by outperforming spade by both speed and memory usage factors more than 3.4 and spam by a memory consumption factor up to more than an order of magnitude.
fast relevance discovery in time series. in this paper, we propose to model time series from a new angle: state transition points. when fluctuation of values in a time series crosses a certain point, it may trigger state transition in the system, which may lead to abrupt changes in many other time series. the concept of state transition points is essential in understanding the behavior of the time series and the behavior of the system. the new measure is robust and is capable of discovering correlations that pearson's coefficient cannot reveal. we propose efficient algorithms to identify state transition points and to compute correlation between two time series. we also introduce some triangular inequalities to efficiently find highly correlated time series among many time series.
cluster ranking with an application to mining mailbox networks. we initiate the study of a new clustering framework, called cluster ranking. rather than simply partitioning a network into clusters, a cluster ranking algorithm also orders the clusters by their strength. to this end, we introduce a novel strength measure for clusters&#x2014;the integrated cohesion&#x2014;which is applicable to arbitrary weighted networks. we then present a new cluster ranking algorithm, called c-rank. we provide extensive theoretical and empirical analysis of c-rank and show that it is likely to have high precision and recall. a main component of c-rank is a heuristic algorithm for finding sparse vertex separators. at the core of this algorithm is a new connection between vertex betweenness and multicommodity flow. our experiments focus on mining mailbox networks. a mailbox network is an egocentric social network, consisting of contacts with whom an individual exchanges email. edges between contacts represent the frequency of their co&#x2013;occurrence on message headers. c-rank is well suited to mine such networks, since they are abundant with overlapping communities of highly variable strengths. we demonstrate the effectiveness of c-rank on the enron data set, consisting of 130 mailbox networks.
window-based tensor analysis on high-dimensional and multi-aspect streams. data stream values are often associated with multiple aspects. for example, each value from environmental sensors may have an associated type (e.g., temperature, humidity, etc) as well as location. aside from timestamp, type and location are the two additional aspects. how to model such streams? how to simultaneously find patterns within and across the multiple aspects? how to do it incrementally in a streaming fashion? in this paper, all these problems are addressed through a general data model, tensor streams, and an effective algorithmic framework, window-based tensor analysis (wta). two variations of wta, independent-window tensor analysis (iw) and moving-window tensor analysis (mw), are presented and evaluated extensively on real datasets. finally, we illustrate one important application, multi-aspect correlation analysis (maca), which uses wta and we demonstrate its effectiveness on an environmental monitoring application.
p3c: a robust projected clustering algorithm. projected clustering has emerged as a possible solution to the challenges associated with clustering in high dimensional data. a projected cluster is a subset of points together with a subset of attributes, such that the cluster points project onto a small range of values in each of these attributes, and are uniformly distributed in the remaining attributes. existing algorithms for projected clustering rely on parameters whose appropriate values are difficult to set by the user, or are unable to identify projected clusters with few relevant attributes. in this paper, we present a robust algorithm for projected clustering that can effectively discover projected clusters in the data while minimizing the number of parameters required as input. in contrast to all previous approaches, our algorithm can discover, under very general conditions, the true number of projected clusters. we show through an extensive experimental evaluation that our algorithm: (1) significantly outperforms existing algorithms for projected clustering in terms of accuracy; (2) is effective in detecting very low-dimensional projected clusters embedded in high dimensional spaces; (3) is effective in detecting clusters with varying orientation in their relevant subspaces; (4) is scalable with respect to large data sets and high number of dimensions.
on trajectory representation for scientific features. in this article, we present trajectory representation algorithms for tangible features found in temporally varying scientific datasets. rather than modeling the features as points, we take attributes like shape and extent of the feature into account. our contention is that these attributes play an important role in understanding the temporal evolution and interactions among features. the proposed representation scheme is based on motion and shape parameters including linear velocity, angular velocity, etc. we use these parameters to segment the trajectory instead of relying on the geometry of the trajectory. we evaluate our algorithms on real datasets originating from different domains. we show the accuracy of the motion and shape parameter estimation by reconstructing the trajectories with high accuracy. finally, we present performance and scalability results.
exploratory under-sampling for class-imbalance learning. under-sampling is a class-imbalance learning method which uses only a subset of major class examples and thus is very efficient. the main deficiency is that many major class examples are ignored. we propose two algorithms to overcome the deficiency. easyensemble samples several subsets from the major class, trains a learner using each of them, and combines the outputs of those learners. balancecascade is similar to easyensemble except that it removes correctly classified major class examples of trained learners from further consideration. experiments show that both of the proposed algorithms have better auc scores than many existing class-imbalance learning methods. moreover, they have approximately the same training time as that of under-sampling, which trains significantly faster than other methods.
searching for pattern rules. we address the problem of finding a set of pattern rules, from a transaction dataset given a statistical metric. a new data structure, called an incrementally counting suffix tree (icst), is proposed for online computation of estimates of the support of any pattern or itemset. using an icst, our approach directly generates a set of pattern rules by a single scan of the whole dataset in partitions without the generation of frequent itemsets. non-redundant rules can be found by removing redundancies from the pattern rules. the ppmcr algorithm first finds pattern rules and then non-redundant rules by generating valid candidates while traversing the icst. experimental results show that the ppmcr algorithm can be used for efficiently mining fewer non-redundant rules.
dstree: a tree structure for the mining of frequent sets from data streams. with advances in technology, a flood of data can be produced in many applications such as sensor networks and web click streams. this calls for efficient techniques for extracting useful information from streams of data. in this paper, we propose a novel tree structure, called dstree (data stream tree), that captures important data from the streams. by exploiting its nice properties, the dstree can be easily maintained andmined for frequent itemsets as well as various other patterns like constrained itemsets.
decision trees for functional variables. classification problems with functionally structured in- put variables arise naturally in many applications. in a clinical domain, for example, input variables could include a time series of blood pressure measurements. in a financial setting, different time series of stock returns might serve as predictors. in an archaeological application, the 2-d pro- file of an artifact may serve as a key input variable. in such domains, accuracy of the classifier is not the only reason- able goal to strive for; classifiers that provide easily inter- pretable results are also of value. in this work, we present an intuitive scheme for extending decision trees to handle functional input variables. our results show that such deci- sion trees are both accurate and readily interpretable.
trias - an algorithm for mining iceberg tri-lattices. in this paper, we present the foundations for mining frequent tri-concepts, which extend the notion of closed itemsets to three-dimensional data to allow for mining folk-sonomies. we provide a formal definition of the problem, and present an efficient algorithm for its solution as well as experimental results on a large real-world example.
ac-close: efficiently mining approximate closed itemsets by core pattern recovery. recent studies have proposed methods to discover approximate frequent itemsets in the presence of random noise. by relaxing the rigid requirement of exact frequent pattern mining, some interesting patterns, which would previously be fragmented by exact pattern mining methods due to the random noise or measurement error, are successfully recovered. unfortunately, a large number of "uninteresting" candidates are explored as well during the mining process, as a result of the relaxed pattern mining methodology. this severely slows down the mining process. even worse, it is hard for an end user to distinguish the recovered interesting patterns from these uninteresting ones. in this paper, we propose an efficient algorithm ac-close to recover the approximate closed itemsets from "core patterns". by focusing on the so-called core patterns, integrated with a top-down mining and several effective pruning strategies, the algorithm narrows down the search space to those potentially interesting ones. experimental results show that ac-close substantially outperforms the previously proposed method in terms of efficiency, while delivers a similar set of interesting recovered patterns.
subjectivity categorization of weblog with part-of-speech based smoothing. experts from different domains try to mine users' comments on weblogs for different reasons such as politics or commerce. all these needs necessitate automatically distinguishing subjective weblog contents from objective ones, namely subjectivity categorization. since weblogs contain various topics from different domains, limited training data can hardly cover all the topics and "unseen words" becomes a serious problem for categorization tasks. in this paper, part-of-speech (pos) based smoothing is proposed to alleviate the "unseen words" problem. in conjunction with a naïve bayes model constructed from limited training data, the probability of an unseen word in a new domain can be well smoothed by the probability of its pos result. empirical studies on five datasets show that our approach consistently outperforms the basic naïve bayes with laplace smoothing. in a cross-domain experiment, our approach achieves 22.0% improvement in macro f1 and 24.4% in micro f1 over basic naïve bayes. these verify that pos based smoothing can indeed benefit subjectivity categorization, especially in the cases with a large number of unseen words.
what is the dimension of your binary data? many 0/1 datasets have a very large number of variables; however, they are sparse and the dependency structure of the variables is simpler than the number of variables would suggest. defining the effective dimensionality of such a dataset is a nontrivial problem. we consider the problem of defining a robust measure of dimension for 0/1 datasets, and show that the basic idea of fractal dimension can be adapted for binary data. however, as such the fractal dimension is difficult to interpret. hence we introduce the concept of normalized fractal dimension. for a dataset d, its normalized fractal dimension counts the number of independent columns needed to achieve the unnormalized fractal dimension of d. the normalized fractal dimension measures the degree of dependency structure of the data. we study the properties of the normalized fractal dimension and discuss its computation. we give empirical results on the normalized fractal dimension, comparing it against pca.
entropy-based concept shift detection. when monitoring sensory data (e.g., from a wearable device) the context oftentimes changes abruptly: people move from one situation (e.g., working quietly in their office) to another (e.g., being interrupted by one's manager). these context changes can be treated like concept shifts, since the underlying data generator (the concept) changes while moving from one context situation to another. we present an entropy based measure for data streams that is suitable to detect concept shifts in a reliable, noise-resistant, fast, and computationally efficient way. we assess the entropy measure under different concept shift conditions. to support our claims we illustrate the concept shift behavior of the stream entropy. we also present a simple algorithm control approach to show how useful and reliable the information obtained by the entropy measure is compared to a ensemble learner as well as an experimentally inferred upper limit. our analysis is based on three large synthetic data sets representing real, virtual, and a combination of both concept drifts under different noise conditions (up to 50%). last but not least, we demonstrate the usefulness of the entropy based measure context switch indication in a real world application in the context-awareness/wearable computing domain.
improving personalization solutions through optimal segmentation of customer bases. on the web, where the search costs are low and the competition is just a mouse click away, it is crucial to segment the customers intelligently in order to offer more personalized products and services to them. traditionally, customer segmentation is achieved using statistics-based methods that compute a set of statistics from the customer data and group customers into segments by applying distance-based clustering algorithms in the space of these statistics. in this paper, we present a direct grouping based approach to computing customer segments that groups customers in terms of optimally combining transactional data of several customers to build a predictive model of customer behavior for each group. we consider customer segmentation as a combinatorial optimization problem of finding the best partitioning of the customer base into disjoint groups and show that finding an optimal customer partition is np-hard. we propose several suboptimal direct grouping segmentation methods, empirically compares them against traditional statistics-based hierarchical and affinity propagation based segmentation, and 1-to-1 methods across multiple experimental conditions. we show that the best direct grouping method builds mostly small sized customer segments and significantly dominates the statistics-based and 1-to-1 approaches across most of the experimental conditions, while still being computationally tractable.
a framework for regional association rule mining in spatial datasets. the immense explosion of geographically referenced data calls for efficient discovery of spatial knowledge. one of the special challenges for spatial data mining is that information is usually not uniformly distributed in spatial datasets. consequently, the discovery of regional knowledge is of fundamental importance for spatial data mining. this paper centers on discovering regional association rules in spatial datasets. in particular, we introduce a novel framework to mine regional association rules relying on a given class structure. a reward-based regional discovery methodology is introduced, and a divisive, grid-based supervised clustering algorithm is presented that identifies interesting subregions in spatial datasets. then, an integrated approach is discussed to systematically mine regional rules. the proposed framework is evaluated in a real-world case study that identifies spatial risk patterns from arsenic in the texas water supply.
mining complex time-series data by learning markovian models. in this paper, we propose a novel and general approach for time-series data mining. as an alternative to traditional ways of designing specific algorithm to mine certain kind of pattern directly from the data, our approach extracts the temporal structure of the time-series data by learning markovian models, and then uses well established methods to efficiently mine a wide variety of patterns from the topology graph of the learned models. we consolidate the approach by explaining the use of some well-known markovian models on mining several kinds of patterns. we then present a novel high-order hidden markov model, the variable-length hidden markov model (vlhmm), which combines the advantages of well-known markovian models and has the superiority in both efficiency and accuracy. therefore, it can mine a much wider variety of patterns than each of prior markovian models. we demonstrate the power of vlhmm by mining four kinds of interesting patterns from 3d motion capture data, which is typical for the high-dimensionality and complex dynamics.
top-cop: mining top-k strongly correlated pairs in large databases. recently, there has been considerable interest in computing strongly correlated pairs in large databases. most previous studies require the specification of a minimum correlation threshold to perform the computation. however, it may be difficult for users to provide an appropriate threshold in practice, since different data sets typically have different characteristics. to this end, we propose an alternative task: mining the top-k strongly correlated pairs. in this paper, we identify a 2-d monotone property of an upper bound of pearson's correlation coefficient and develop an efficient algorithm, called top-cop to exploit this property to effectively prune many pairs even without computing their correlation coefficients. our experimental results show that the top-cop algorithm can be orders of magnitude faster than brute-force alternatives for mining the top-k strongly correlated pairs.
keyphrase extraction using semantic networks structure analysis. keyphrases play a key role in text indexing, summarization and categorization. however, most of the existing keyphrase extraction approaches require human-labeled training sets. in this paper, we propose an automatic keyphrase extraction algorithm, which can be used in both supervised and unsupervised tasks. this algorithm treats each document as a semantic network. structural dynamics of the network are used to extract keyphrases (key nodes) unsupervised. experiments demonstrate the proposed algorithm averagely improves 50% in effectiveness and 30% in efficiency in unsupervised tasks and performs comparatively with supervised extractors. moreover, by applying this algorithm to supervised tasks, we develop a classifier with an overall accuracy up to 80%.
mining maximal generalized frequent geographic patterns with knowledge constraints. in frequent geographic pattern mining a large amount of patterns is well known a priori. this paper presents a novel approach for mining frequent geographic patterns without associations that are previously known as non-interesting. geographic dependences are eliminated during the frequent set generation using prior knowledge. after the dependence elimination maximal generalized frequent sets are computed to remove redundant frequent sets. experimental results show a significant reduction of both the number of frequent sets and the computational time for mining maximal frequent geographic patterns.