waashk/dblp huggingface dataset:
phrase-based document similarity based on an index graph model. document clustering techniques mostly rely on singleterm analysis of the document data set, such as the vectorspace model. to better capture the structure of documents,the underlying data model should be able to represent thephrases in the document as well as single terms. we presenta novel data model, the document index graph, which indexesweb documents based on phrases, rather than singleterms only. the semi-structured web documents helpin identifying potential phrases that when matched withother documents indicate strong similarity between the documents.the document index graph captures this informa-tion,and finding significant matching phrases between documentsbecomes easy and efficient with such model. thesimilarity between documents is based on both single termweights and matching phrases weights. the combined similaritiesare used with standard document clustering techniquesto test their effect on the clustering quality. experimentalresults show that our phrase-based similarity, combinedwith single-term similarity measures, enhances webdocument clustering quality significantly.
query-driven support pattern discovery for classification learning. we propose a novel query-driven lazy learning algorithm which attempts to discover useful local patterns, called support patterns, for classifying a given query. the learning is customized to the query to avoid the horizon effect. we show that this query-driven learning algorithm can guarantee to discover all support patterns with perfect expected accuracy in polynomial time. the experimental results on benchmark data sets also demonstrate that our learning algorithm really has prominent learning performance.
pixelmaps: a new visual data mining approach for analyzing large spatial data sets. pixelmaps are a new pixel-oriented visual data miningtechnique for large spatial datasets. they combine kernel-density-based clustering with pixel-oriented displays to emphasizeclusters while avoiding overlap in locally densepoint sets on maps. because a full evaluation of densityfunctions is prohibitively expensive, we also propose an efficientapproximation, fast-pixelmap, based on a synthesisof the quadtree and gridfile data structures.
mining top-k frequent closed patterns without minimum support. in this paper, we propose a new mining task: mining top-kfrequent closed patterns of length no less than min_l, wherek is the desired number of frequent closed patterns to bemined, and min _l is the minimal length of each pattern.an efficient algorithm, called tfp, is developed for mining such patterns without minimum support. two methods, closed_node_count and descendant_sum are proposedto effiectively raise support threshold and prune fp-tree bothduring and after the construction of fp-tree. during themining process, a novel top-down and bottom-up combinedfp-tree mining strategy is developed to speed-up support-raising and closed frequent pattern discovering. in addition,a fast hash-based closed pattern verification scheme has beenemployed to check efficiently if a potential closed pattern isreally closed.our performance study shows that in most cases, tfpoutperforms closet and charm, two efficient frequentclosed pattern mining algorithms, even when both are running with the best tuned min_support. furthermore, themethod can be extended to generate association rules andto incorporate user-specified constraints. thus we concludethat for frequent pattern mining, mining top-k frequent closedpatterns without min support is more preferable than thetraditional min_support-based mining.
an online algorithm for segmenting time series. in recent years, there has been an explosion of interest in mining time series databases. as with most computer science problems, representation of the data is the key to efficient and effective solutions. one of the most commonly used representations is piecewise linear approximation. this representation has been used by various researchers to support clustering, classification, indexing and association rule mining of t me series data. a variety of algorithms have been proposed to obtain this representation, with several algorithms having been independently rediscovered several times. in this paper, we undertake the first extensive review and empirical comparison of all proposed techniques. we show that allthese algorithms have fatal flaws from a data mining perspective. we introduce a novel algorithm that we empirically show to be super or to all others n the literature.
discovering representative episodal association rules from event sequences using frequent closed episode sets and event constraints. discovering association rules from time-series data is an important data mining problem. the number of potential rules grows quickly as the number of items in the antecedent grows. it is therefore difficult for an expert to analyze the rules and identify the useful. an approach for generating representative association rules for transactions that uses only a subset of the set of frequent itemsets called frequent closed itemsets was presented in [6 ]. we employ formalconcept analysis to develop the notion of frequent closed episodes. the concept of representative association rules is formalized in the context of event sequences. applying constraints to target highly significant rules further reduces the number of rules. our approach results in a significant reduction of the number of rules generated, while maintaining the minimum set of relevant association rules and retaining the ability to generate the entire set of association rules with respect to the given constraints. we show how our method can be used to discover associations in a drought risk management decision support system and use multiple climatology datasets related to automated weather stations1
hot sax: efficiently finding the most unusual time series subsequence. in this work, we introduce the new problem of finding time series discords. time series discords are subsequences of a longer time series that are maximally different to all the rest of the time series subsequences. they thus capture the sense of the most unusual subsequence within a time series. time series discords have many uses for data mining, including improving the quality of clustering, data cleaning, summarization, and anomaly detection. as we will show, discords are particularly attractive as anomaly detectors because they only require one intuitive parameter (the length of the subsequence) unlike most anomaly detection algorithms that typically require many parameters. we evaluate our work with a comprehensive set of experiments. in particular, we demonstrate the utility of discords with objective experiments on domains as diverse as space shuttle telemetry monitoring, medicine, surveillance, and industry, and we demonstrate the effectiveness of our discord discovery algorithm with more than one million experiments, on 82 different datasets from diverse domains.
automatic topic identification using webpage clustering. grouping webpage into distinct topics is one way to organize the large amount of retrieved information on the web. in this paper, we report that based on similaritymetric which incorporates textual information, hyperlinkstructure and co-citation relations, an unsupervised clustering method can automatically and effectively identify relevant topics, a shown in experiments on several retrieved sets of webpages. the clustering method is a state-of-art spectral graph partitioning method based on normalized cutcriterion first developed for image segmentation.
clustering of time series subsequences is meaningless: implications for previous and future research. time series data is perhaps the most frequently encountered typeof data examined by the data mining community. clustering isperhaps the most frequently used data mining algorithm, beinguseful in it's own right as an exploratory technique, and also as asubroutine in more complex data mining algorithms such as rulediscovery, indexing, summarization, anomaly detection, andclassification. given these two facts, it is hardly surprising thattime series clustering has attracted much attention. the data to beclustered can be in one of two formats: many individual timeseries, or a single time series, from which individual time seriesare extracted with a sliding window. given the recent explosion ofinterest in streaming data and online algorithms, the latter casehas received much attention.in this work we make an amazing claim. clustering of streamingtime series is completely meaningless. more concretely, clustersextracted from streaming time series are forced to obey a certainconstraint that is pathologically unlikely to be satisfied by anydataset, and because of this, the clusters extracted by anyclustering algorithm are essentially random. while this constraintcan be intuitively demonstrated with a simple illustration and issimple to prove, it has never appeared in the literature.we can justify calling our claim surprising, since it invalidatesthe contribution of dozens of previously published papers. we willjustify our claim with a theorem, illustrative examples, and acomprehensive set of experiments on reimplementations ofprevious work.
improving home automation by discovering regularly occurring device usage patterns. the data stream captured by recording inhabitant-deviceinteractions in an environment can be mined todiscover significant patterns, which an intelligent agentcould use to automate device interactions. however, thisknowledge discovery problem is complicated by severalchallenges, such as excessive noise in the data, data thatdoes not naturally exist as transactions, a need tooperate in real time, and a domain where frequency maynot be the best discriminator. in this paper, we propose anovel data mining technique that addresses thesechallenges and discovers regularly-occurringinteractions with a smart home. we also discuss a casestudy that shows the data mining technique can improvethe accuracy of two prediction algorithms, thusdemonstrating multiple uses for a home automationsystem. finally, we present an analysis of the algorithmand results obtained using inhabitant interactions.
feature-based prediction of unknown preferences for nearest-neighbor collaborative filtering. recommendation systems analyze user preferences and recommend items to a user by predicting the user's preference for those items.among various kinds of recommendation methods, collaborative filtering (cf) has been widely used and successfully applied to practical applications.however, collaborative filtering has two inherent problems: data sparseness and the cold-start problems.in this paper, we propose a method of integrating additional feature information of users and items into cf to overcome the difficulties caused by sparseness and improve the accuracy of recommendation. several experimental results that show the effectiveness of the proposed method are also presented.
amiot: induced ordered tree mining in tree-structured databases. frequent subtree mining has become increasingly important in recent years. in this paper, we present amiot algorithm to discover all frequent ordered subtrees in a tree-structured database. in order to avoid the generation of infrequent candidate trees, we propose the techniques such as right-and-left tree join and serial tree extension. proposed methods enumerate only the candidate trees with high probability of being frequent without any duplications. the experiments on synthetic dataset and xml database show that amiot reduces redundant candidate trees and outperforms freqt algorithm by up to five times in execution time.
aine: an immunological approach to data mining. an investigation has been undertaken to repeat previous work on an artificial immune system for data analysis called aine (artificial immune network).the previous work was limited to testing the algorithm on relatively small data sets. the aim of this investigation is two fold,firstly to corroborate the results presented in previous work and secondly, to test the algorithm on a larger and more complex data set. a new re-implementation of aine is then described and differences in behaviour are identified and explained. it is argued that the behaviourseen in the new implementation is more accurate than that seen in previous work and an in-depth analysis of the algorithm structure is undertaken in order to confirm theseobservations. the algorithm is also tested on new data and the results of this are presented. comparisons are draw with other similar techniques for data mining and it is argued that aine is an effective data-mining algorithm.
dependencies between transcription factor binding sites: comparison between ica, nmf, plsa and frequent sets. gene expression of eucaryotes is regulated through transcription factors, which are molecules able to attach to the binding sites in the dna sequence. these binding sites are small pieces of dna usually found upstream from the gene they regulate. as the binding sites play an important role in the gene expression, it is of interest to find out their characteristics. in this paper we look for dependencies and independencies between these binding sites using independent component analysis (ica), non-negative matrix factorization (nmf), probabilistic latent semantic analysis (plsa) and the method of frequent sets. the data used are human gene upstream regions and possible binding sites listed in a biological database. also, results on the baker's yeast (s.cerevisiae) upstream regions are briefly discussed for comparison. ica, nmf and plsa are latent variable methods that decompose the observed data into smaller components. of these, ica and nmf were originally aimed for continuous data. we show that these methods can be successfully used on discrete dna data as well. plsa and the method of frequent sets were created for discrete data sets. the above methods reveal partially overlapping sets of possible binding sites such that the binding sites within a set are dependent of each other. the methods of frequent sets and nmf give a good overview of the most common data structures, whereas using ica and plsa we find large sets that are surprisingly frequent. that is, sets of very frequently occurring possible binding sites can be found near hundreds or thousands of genes; also interesting but less frequent ones co-occur surprisingly often.
orthogonal neighborhood preserving projections. orthogonal neighborhood preserving projections (onpp) is a linear dimensionality reduction technique which attempts to preserve both the intrinsic neighborhood geometry of the data samples and the global geometry. the proposed technique constructs a weighted data graph where the weights are constructed in a data-driven fashion, similarly to locally linear embedding (lle). a major difference with the standard lle where the mapping between the input and the reduced spaces is implicit, is that onpp employs an explicit linear mapping between the two. as a result, and in contrast with lle, handling new data samples becomes straightforward, as this amounts to a simple linear transformation. onpp shares some of the properties of locality preserving projections (lpp). both onpp and lpp rely on a k-nearest neighbor graph in order to capture the data topology. however, our algorithm inherits the characteristics of lle in preserving the structure of local neighborhoods, while lpp aims at preserving only locality without specifically aiming at preserving the geometric structure. this feature makes onpp an effective method for data visualization. we provide ample experimental evidence to demonstrate the advantageous characteristics of onpp, using well known synthetic test cases as well as real life data from computational biology and computer vision.
focused community discovery. we present a new approach to community discovery. community discovery usually partitions the graph into communities or clusters. focused community discovery allows the searcher to specify start points of interest, and find the community of those points. focused search allows for a much more scalable algorithm in which the time depends only on the size of the community, and not on the number of nodes in the graph, and so is scalable to arbitrarily large graphs. furthermore, our algorithm is robust to imperfect data, such as extra or missing edges in the graph. we show the effectiveness of our algorithm using both synthetic graphs and on the real-life livejournal friends graph, a publicly-available social network consisting of over two million users and 13 million edges.
higher-order web link analysis using multilinear algebra. linear algebra is a powerful and proven tool in web search. techniques, such as the pagerank algorithm of brin and page and the hits algorithm of kleinberg, score web pages based on the principal eigenvector (or singular vector) of a particular non-negative matrix that captures the hyperlink structure of the web graph. we propose and test a new methodology that uses multilinear algebra to elicit more information from a higher-order representation of the hyperlink graph. we start by labeling the edges in our graph with the anchor text of the hyperlinks so that the associated linear algebra representation is a sparse, three-way tensor. the first two dimensions of the tensor represent the web pages while the third dimension adds the anchor text. we then use the rank-1 factors of a multilinear parafac tensor decomposition, which are akin to singular vectors of the svd, to automatically identify topics in the collection along with the associated authoritative web pages.
time series segmentation for context recognition in mobile devices. recognizing the context of se is important in making mobile devices as simple to use as possible. finding out what the user's situation is can help the device andunderlying service in providing an adaptive and personalized user interface. the device can infer parts of the context of the user from sensor data: the mobile device can includesensors for acceleration, noise level, luminosity, humidity, etc. in this paper we consider context recognition by unsupervisedsegmentation of time series produced by sensors.dynamic programming can be used to find segments that minimize the intra-segment variances. while this method produces optimal solutions, it is too slow for long sequencesof data. we present and analyze randomized variations of the algorithm. one of them, global iterative replacement or gir, gives approximately optimal results in a fraction of the time required by dynamic programming. wedemonstrate the se of time series segmentation in contextrecognition for mobile phone applications.
dynamic weighted majority: a new ensemble method for tracking concept drift. algorithms for tracking concept drift are important formany applications. we present a general method basedon the weighted majority algorithm for using any on-linelearner for concept drift. dynamic weighted majority(dwm) maintains an ensemble of base learners, predictsusing a weighted-majority vote of these "experts",and dynamically creates and deletes experts in response tochanges in performance. we empirically evaluated two experimentalsystems based on the method using incrementalnaive bayes and incremental tree inducer (iti) as experts.for the sake of comparison, we also included blum's implementationof weighted majority. on the stagger conceptsand on the sea concepts, results suggest that the ensemblemethod learns drifting concepts almost as well as the basealgorithms learn each concept individually. indeed, we reportthe best overall results for these problems to date.
suppressing data sets to prevent discovery of association rules. enterprises have been collecting data for many reasons including better customer relationship management, and high-level decision making. public safety was another motivation for large-scale data collection efforts initiated by government agencies. however, such widespread data collection efforts coupled with powerful data analysis tools raised concerns about privacy. this is due to the fact that collected data may contain confidential information. one method to ensure privacy is to selectively hide confidential information from the data sets to be disclosed. in this paper, we focus on hiding confidential correlations. we introduce a heuristic to reduce the information loss and propose a blocking method that prevents discovery of confidential correlations while preserving the usefulness of the data set.
making logistic regression a core data mining tool with tr-irls. binary classification is a core data mining task. for large datasets or real-time applications, desirable classifiersare accurate, fast, and need no parameter tuning. we present a simple implementation of logistic regression that meets these requirements. a combination of regularization, truncated newton methods, and iteratively re-weighted least squares make it faster and more accurate than modern svm implementations, and relatively insensitive to parameters. it is robust to linear dependencies and some scaling problems, making most data preprocessing unnecessary.
indiscernibility degree of objects for evaluating simplicity of knowledge in the clustering procedure. this paper presents a new, rough sets-based clusteringmethod that enables evaluation of simplicity of classification knowledge during the clustering procedure. the method iteratively refines equivalence relations so that they become more simple set of relations that give adequately coarse classification to the objects. at each step ofiteration, importance of the equivalence relation is evaluated on the basis of the newly introduced measure, indiscernibility degree. an indiscernibility degree is defined as a ratio of equivalence relations that classify the two objects into the same equivalence class. if an equivalence relation hasability to discern the two objects that have high indiscernibility degree, it is considered to perform too fine classification and then modified to regard them as indiscernible objects. the refinement is repeated decreasing the threshold level ofindiscernibility degree, and finally simple clusters can beobtained. experimental results on the artificial data showed that iterative refinement of equivalence relation lead tosuccessful generation of coarse clusters that can be representedby simple knowledge.
recognition of common areas in a web page using visual information: a possible application in a page classification. extracting and processing information from webpages is an important task in many areas likeconstructing search engines, information retrieval, anddata mining from the web. common approach in theextraction process is to represent a page as a "bag ofwords" and then to perform additional processing onsuch a flat representation. in this paper we propose anew, hierarchical representation that includes browserscreen coordinates for every html object in a page.using visual information one is able to define heuristicsfor the recognition of common page areas such asheader, left and right menu, footer and center of a page.we show in initial experiments that using our heuristicsdefined objects are recognized properly in 73% of cases.finally, we show that a naive bayes classifier, takinginto account the proposed representation, clearlyoutperforms the same classifier using only informationabout the content of documents.