Search

This paper presents a new information acquisition problem motivated by business applications where customer data has to be acquired with a specific modeling objective in mind. In the last two decades, there has been substantial work in two different fields—optimal experimental design and machine learning—that has addressed the issue of acquiring data in a selective manner with a specific objective in mind. We show that the problem presented here is different from the classic model-based data acquisition problems considered thus far in the literature in both fields. Building on work in optimal experimental design and in machine learning, we develop a new active learning technique for the information acquisition problem presented in this paper. We demonstrate that the proposed method performs well based on results from applying this method across 20 Web usage and machine learning data sets. [ABSTRACT FROM AUTHOR]

One-versus-all (OVA) classifiers learn κ individual binary classifiers, each distinguishing the instances of a single class from the instances of all other classes. To classify a new instance, the κ classifiers are run, and the one that returns the highest confidence is chosen. Thus, OVA is different from existing data stream classification schemes whose majority use multiclass classifiers, each discriminating among all the classes. This paper advocates some outstanding advantages of OVA for data stream classification. First, there is low error correlation and, hence, high diversity among OVA's component classifiers, which leads to high classification accuracy. Second, OVA is adept at accommodating new class labels that often appear in data streams. However, there also remain many challenges to deploy traditional OVA for classifying data streams. First, traditional OVA does not handle concept change, a key feature of data streams. Second, as every instance is fed to all component classifiers, OVA is known as an inefficient model. Third, OVA's classification accuracy is adversely affected by the imbalanced class distributions in data streams. This paper addresses those key challenges and consequently proposes a new OVA scheme that is adapted for data stream classification. Theoretical analysis and empirical evidence reveal that the adapted OVA can offer faster training, faster updating, and higher classification accuracy than many existing popular data stream classification algorithms. We expect these results to be of interest to researchers and practitioners because they suggest a simple but very elegant and effective alternative to existing classification schemes for data streams. [ABSTRACT FROM AUTHOR]

Purpose – The purpose of this paper is to estimate Google search engine’s ranking function from a search engine optimization (SEO) perspective. Design/methodology/approach – The paper proposed an estimation function that defines the query match score of a search result as the weighted sum of scores from a limited set of factors. The search results for a query are re-ranked according to the query match scores. The effectiveness was measured by comparing the new ranks with the original ranks of search results. Findings – The proposed method achieved the best SEO effectiveness when using the top 20 search results for a query. The empirical results reveal that PageRank (PR) is the dominant factor in Google ranking function. The title follows as the second most important, and the snippet and the URL have roughly equal importance with variations among queries. Research limitations/implications – This study considered a limited set of ranking factors. The empirical results reveal that SEO effectiveness can be assessed by a simple estimation of ranking function even when the ranks of the new and original result sets are quite dissimilar. Practical implications – The findings indicate that web marketers should pay particular attention to a webpage’s PR, and then place the keyword in URL, the page title, and snippet. Originality/value – There have been ongoing concerns about how to formulate a simple strategy that can help a website get ranked higher in search engines. This study provides web marketers much needed empirical evidence about a simple way to foresee the ranking success of an SEO effort. [ABSTRACT FROM AUTHOR]

With the growing number of document sets accessible online, tracking their evolution over time (story tracking) became an increasingly interesting problem. In this paper we propose a story tracking method based on the dynamics of keyword-association graphs. We create a graph representation of the story evolution that we call story graphs, and investigate how graph structure can be used for detecting and discovering new developments in the story. First we investigate the possibly interesting graph properties for development detection. We continue by investigating how graph structure can be linked to the sentences representing developments. For this we create an evaluation framework which bridges the gap between temporal text mining patterns and sentences. We apply this framework to evaluate our method against other temporal text mining methods. Our experiments show that story graphs perform at similar levels overall, but provide distinctive advantages in some settings. [ABSTRACT FROM AUTHOR]

The steady growth in the size of textual document collections is a key progress-driver for modern information retrieval techniques whose effectiveness and efficiency are constantly challenged. Given a user query, the number of retrieved documents can be overwhelmingly large, hampering their efficient exploitation by the user. In addition, retaining only relevant documents in a query answer is of paramount importance for an effective meeting of the user needs. In this situation, the query expansion technique offers an interesting solution for obtaining a complete answer while preserving the quality of retained documents. This mainly relies on an accurate choice of the added terms to an initial query. Interestingly enough, query expansion takes advantage of large text volumes by extracting statistical information about index terms co-occurrences and using it to make user queries better fit the real information needs. In this respect, a promising track consists in the application of data mining methods to the extraction of dependencies between terms. In this paper, we present a novel approach for mining knowledge supporting query expansion that is based on association rules. The key feature of our approach is a better trade-off between the size of the mining result and the conveyed knowledge. Thus, our association rules mining method implements results from Galois connection theory and compact representations of rules sets in order to reduce the huge number of potentially useful associations. An experimental study has examined the application of our approach to some real collections, whereby automatic query expansion has been performed. The results of the study show a significant improvement in the performances of the information retrieval system, both in terms of recall and precision, as highlighted by the carried out significance testing using the Wilcoxon test. [ABSTRACT FROM AUTHOR]

In view of today's information avalanche, recent progress in data mining research has led to the development of numerous efficient and scalable methods for mining interesting patterns in large databases. The focus of data analysis and data mining tools in biomedical research highlights the current state of research in the key biomedical research areas such as, medical informatics, public health informatics and biomedical imaging. Medicine and biomedical sciences have become data-intensive fields, which, at the same time, enable the application of data-driven approaches and require sophisticated data analysis and data mining methods. Biomedical informatics provides a proper interdisciplinary context to integrate data and knowledge when processing available information, with the aim of giving effective decision-making support in clinics and translational research. Biomedical text data mining is concerned with automated methods for analyzing the content of these documents and discovering and extracting the knowledge in them. Numerical data mining has long been used to uncover patterns in numerical data and make predictions based on those patterns. Text data mining builds on the success of numerical data mining but presents additional challenges. The amount of available biomedical data continues to grow in an exponential rate; however, the impact of utilizing such resources remains minimal. The development of innovative tools to integrate, analyze and mine such data sources is a key step towards achieving larger impact levels. In this Paper, we analyze how data mining may help bio-medical data analysis and outlined some research problems that may motivate the further developments of data mining tools for bio-data analysis and representation of Knowledge. [ABSTRACT FROM AUTHOR]

Effective distance functions in high-dimensional data space, such as those used for clustering, nearest neighbor search, and indexing, are very important in solutions for many data mining problems. Recent research has shown that if the Pearson variation of the distance distribution converges to zero with increasing dimensionality, the distance function will become unstable (or meaningless) in high-dimensional space, even with the commonly used Lp, metric in the euclidean space. However, the necessary condition for unstability of a distance function, which is required for function design, remains unknown. In this paper, we shall prove that the following conditions are equivalent to unstability: 1) the Pearson variation of the distance distribution for any given query converges to 0 with increasing dimensionality, 2) the ratio of the distances of any two points to th query converges in probability to 1 with increasing dimensionality, and 3) the second moment coefficient converges to 1 with increasing dimensionality. With these results, we have the necessary and the sufficient conditions for unstability, whose negatives imply the sufficient and necessary conditions for stability. Based on these theoretical results, we employ some effective and valid indices for testing the stability of a distance function. In addition, this theoretical analysis inspires us that unstable phenomena are rooted in variation of the distance distribution. To demonstrate the theoretical results, we design a meaningful distance function, called the Shrinkage-Divergence Proximity (SDP), based on a given distance function. It is shown empirically that the SDP significantly outperforms other measures in terms of stability in high-dimensional data space, and is thus more suitable for distance-based applications. [ABSTRACT FROM AUTHOR]

Retrieval efficiencies of paper-based references in journals and other serials containing 10 scientific names of fossil amphibians were determined for seven major search engines. Retrievals were compared to the number of references obtained covering the period 1895-2006 by a Comprehensive Search. The latter was primarily a traditional library-based search which involved intensive work from 2002-2007. Only a few references originally obtained by search engines were included. Retrieval efficiencies were calculated by comparison to the number obtained through the Comprehensive Search (assumed to be 100%). All percent retrievals were quite low (mean = 11.3%, range = 4.0-22.9%). For all seven search engines combined (duplicate references excluded), the percent retrieval was only 40.7%. There was also retrieval inefficiency and bias of the search engines in: sampling over time, the top five journals containing the most references, the top five most prolific authors, and non-English references. Consequently, all seven search engines were unsatisfactory for retrieval of references for our scientific research. [ABSTRACT FROM AUTHOR]

The importance of query processing over uncertain data has recently arisen due to its wide usage in many real-world applications. In the context of uncertain databases, previous works have studied many query types such as nearest neighbor query, - range query, top-k query, skyline query, and similarity join. In this paper, we focus on another important query, namely, probabilistic group nearest neighbor (PGNN) query, in the uncertain database, which also has many applications. Specifically, given a set, Q, of query points, a PGNN query retrieves data objects that minimize the aggregate distance (e.g., sum, mm, and max) to query set Q. Due to the inherent uncertainty of data objects, previous techniques to answer group nearest neighbor (GNN) query cannot be directly applied to our PGNN problem. Motivated by this, we propose effective pruning methods, namely, spatial pruning and probabilistic pruning, to reduce the PGNN search space, which can be seamlessly integrated into our PGNN query procedure. Extensive experiments have demonstrated the efficiency and effectiveness of our proposed approach, in terms of the wall clock time and the speed-up ratio against linear scan. [ABSTRACT FROM AUTHOR]

Organizations and firms are capturing increasingly more data about their customers, suppliers, competitors, and business environment. Most of this data is multiattribute (multidimensional) and temporal in nature. Data mining and business intelligence techniques are often used to discover patterns in such data; however, mining temporal relationships typically is a complex task. We propose a new data analysis and visualization technique for representing trends in multiattribute temporal data using a clustering- based approach. We introduce Cluster-based Temporal Representation of EveNt Data (C-TREND), a system that implements the temporal cluster graph construct, which maps multiattribute temporal data to a two-dimensional directed graph that identifies trends in dominant data types over time. In this paper, we present our temporal clustering-based technique, discuss its algorithmic implementation and performance, demonstrate applications of the technique by analyzing data on wireless networking technologies and baseball batting statistics, and introduce a set of metrics for further analysis of discovered trends. [ABSTRACT FROM AUTHOR]

We explore in this paper a novel sampling algorithm, referred to as algorithm PAS (standing for Proportion Approximation Sampling), to generate a high-quality online sample with the desired sample rate. The sampling quality refers to the consistency between the population proportion and the sample proportion of each categorical value in the database. Note that the state-of-the-art sampling algorithm to preserve the sampling quality has to examine the population proportion of each categorical value in a pilot sample a priori and is thus not applicable to incremental mining applications. To remedy this, algorithm PAS adaptively determines the inclusion probability of each incoming tuple in such a way that the sampling quality can be sequentially preserved while also guaranteeing the sample rate close to the user specified one. Importantly, PAS not only guarantees the proportion consistency of each categorical value but also excellently preserves the proportion consistency of multivariate statistics, which will be significantly beneficial to various data mining applications. For better execution efficiency, we further devise an algorithm, called algorithm EQAS (standing for Efficient Quality-Aware Sampling), which integrates PAS and random sampling to provide the flexibility of striking a compromise between the sampling quality and the sampling efficiency. As validated in experimental results on real and synthetic data, algorithm PAS can stably provide high-quality samples with corresponding computational overhead, whereas algorithm EQAS can flexibly generate samples with the desired balance between sampling quality and sampling efficiency. In addition, while applying the sample generated by algorithms PAS and EQAS to incremental mining applications, a significant efficiency improvement can be obtained without compromising the resulting precision, showing the prominent advantage of both proposed algorithms to be the quality-aware sampling means for incremental mining applications. [ABSTRACT FROM AUTHOR]

Purpose - The paper aims to review all the techniques for developing scenarios that have appeared in the literature, along with comments on their utility, strengths and weaknesses. Design/methodology/approach - The study was carried out through an electronic search using internet search engines and online databases and indexes. Findings - The paper finds eight categories of techniques that include a total of 23 variations used to develop scenarios. There are descriptions and evaluations for each. Practical implications - Futurists can use this list to broaden their repertoire of scenario techniques. Originality/value - Scenario development is the stock-in-trade of futures studies, but no catalog of the techniques used has yet been published. This list is the start at developing a consensus list of techniques that can be refined as the field matures. [ABSTRACT FROM AUTHOR]

This paper studies a problem of robust rule-based classification, i.e., making predictions in the presence of missing values in data. This study differs from other missing value handling research in that it does not handle missing values but builds a rule-based classification model to tolerate missing values. Based on a commonly used rule-based classification model, we characterize the robustness of a hierarchy of rule sets as k-optimal rule sets with the decreasing size corresponding to the decreasing robustness. We build classifiers based on k-optimal rule sets and show experimentally that they are more robust than some benchmark rule-based classifiers, such as C4.5rules and CBA. We also show that the proposed approach is better than two well-known missing value handling methods for missing values in test data. [ABSTRACT FROM AUTHOR]

Process mining techniques have recently received notable attention in the literature for their ability to assist in the (re)design of complex processes by automatically discovering models that explain the events registered in some log traces provided as input. Following this line of research, the paper investigates an extension of such basic approaches, where the identification of different variants for the process is explicitly accounted for, based on the clustering of log traces. Indeed, modeling each group of similar executions with a different schema allows us to single out "conformant" models, which, specifically, minimize the number of modeled enactments that are extraneous to the process semantics. Therefore, a novel process mining framework is introduced and some relevant computational issues are deeply studied. As finding an exact solution to such an enhanced process mining problem is proven to require high computational costs, in most practical cases, a greedy approach is devised. This is founded on an iterative, hierarchical, refinement of the process model, where, at each step, traces sharing similar behavior patterns are clustered together and equipped with a specialized schema. The algorithm guarantees that each refinement leads to an increasingly sound model, thus attaining a monotonic search. Experimental results evidence the validity of the approach with respect to both effectiveness and scalability. [ABSTRACT FROM AUTHOR]

Document keyphrases provide a concise summary of a document's content, offering semantic metadata summarizing a document. They can be used in many applications related to knowledge management and text mining, such as automatic text summarization, development of search engines, document clustering, document classification, thesaurus construction, and browsing interfaces. Because only a small portion of documents have keyphrases assigned by authors, and it is time-consuming and costly to manually assign keyphrases to documents, it is necessary to develop an algorithm to automatically generate keyphrases for documents. This paper describes a Keyphrase Identification Program (KIP), which extracts document keyphrases by using prior positive samples of human identified phrases to assign weights to the candidate keyphrases. The logic of our algorithm is: The more keywords a candidate keyphrase contains and the more significant these keywords are, the more likely this candidate phrase is a keyphrase. KIP's learning function can enrich the glossary database by automatically adding new identified keyphrases to the database. KIP's personalization feature will let the user build a glossary database specifically suitable for the area of his/her interest. The evaluation results show that KIP's performance is better than the systems we compared to and that the learning function is effective. [ABSTRACT FROM AUTHOR]

Graph-based modeling has emerged as a powerful abstraction capable of capturing in a single and unified framework many of the relational, spatial, topological, and other characteristics that are present in a variety of datasets and application areas. Computationally efficient algorithms that find patterns corresponding to frequently occurring subgraphs play an important role in developing data mining-driven methodologies for analyzing the graphs resulting from such datasets. This paper presents two algorithms, based on the horizontal and vertical pattern discovery paradigms, that find the connected subgraphs that have a sufficient number of edge-disjoint embeddings in a single large undirected labeled sparse graph. These algorithms use three different methods for determining the number of edge-disjoint embeddings of a subgraph and employ novel algorithms for candidate generation and frequency counting, which allow them to operate on datasets with different characteristics and to quickly prune unpromising subgraphs. Experimental evaluation on real datasets from various domains show that both algorithms achieve good performance, scale well to sparse input graphs with more than 120,000 vertices or 110,000 edges, and significantly outperform previously developed algorithms. [ABSTRACT FROM AUTHOR]

In data mining area, weight based sequential pattern mining has been suggested to find important sequential patterns by considering the weights of sequential patterns. More extensions with weight constraints have been proposed such as mining weighted association rules, weighted sequential patterns, weighted closed patterns, frequent patterns with dynamic weights, weighted graphs, weighted sub-trees or sub structures, and so on. In previous approach of weighted frequent sequential pattern mining, weighted supports of sequential patterns are exactly matched to prune weighted infrequent sequential patterns. However, in the noisy environment, the small change in weights or supports of items affects the result sets seriously. This may make the weighted sequential patterns less useful in the noisy environment. In this paper, we propose the robust concept of mining weighted approximate sequential patterns. Based on the framework of weight based sequential pattern mining, an approximate factor is defined to relax the requirement for exact equality between weighted supports of sequential patterns and a minimum threshold. After then, we address the concept of mining weighted approximate sequential frequent patterns to find important sequential patterns with/without the noisy data. We analyze the characteristics of weighted approximate sequential patterns and run extensive performance tests. [ABSTRACT FROM AUTHOR]

In Data Mining, the usefulness of association rules is strongly limited by the huge amount of delivered rules. To overcome this drawback, several methods were proposed in the literature such as itemset concise representations, redundancy reduction, and postprocessing. However, being generally based on statistical information, most of these methods do not guarantee that the extracted rules are interesting for the user. Thus, it is crucial to help the decision-maker with an efficient postprocessing step in order to reduce the number of rules. This paper proposes a new interactive approach to prune and filter discovered rules. First, we propose to use ontologies in order to improve the integration of user knowledge in the postprocessing task. Second, we propose the Rule Schema formalism extending the specification language proposed by Liu et al. for user expectations. Furthermore, an interactive framework is designed to assist the user throughout the analyzing task. Applying our new approach over voluminous sets of rules, we were able, by integrating domain expert knowledge in the postprocessing step, to reduce the number of rules to several dozens or less. Moreover, the quality of the filtered rules was validated by the domain expert at various points in the interactive process. [ABSTRACT FROM AUTHOR]

Named Entities Recognition (NER) has become one of the major issues in Information Retrieval (IR), knowledge extraction, and document classification. This paper addresses a particular case of NER, acronym expansion (or definition) when this expansion does not exist in the document using the acronym. Since acronyms may obviously expand into several distinct sets of words, this paper provides nine quality measures of the relevant definition prediction based on mutual information (MI), cubic MI (MI3), and Dice's coefficient. A combinaison of these statistical measures with the cosine approach is proposed. Experiments have been run on biomedical domain where acronyms are numerous. The results on our biomedical corpus showed that the proposed measures were accurate devices to predict relevant definitions. [ABSTRACT FROM AUTHOR]

The knowledge discovery and data mining (KDDM) process models describe the various phases (e.g. business understanding, data understanding, data preparation, modeling, evaluation and deployment) of the KDDM process. They act as a roadmap for implementation of the KDDM process by presenting a list of tasks for executing the various phases. The checklist approach of describing the tasks is not adequately supported by appropriate tools, which specify 'how' the particular task can be implemented. This may result in tasks not being implemented. Another disadvantage is that the long checklist does not capture or leverage the dependencies that exist among the various tasks of the same and different phases. This not only makes the process cumbersome to implement, but also hinders possibilities for semi-automation of certain tasks. Given that each task in the process model serves an important goal and even affects the execution of related tasks due to the dependencies, these limitations are likely to negatively affect the efficiency and effectiveness of KDDM projects. This paper proposes an improved KDDM process model that overcomes these shortcomings by prescribing tools for supporting each task as well as identifying and leveraging dependencies among tasks for semi-automation of tasks, wherever possible. [ABSTRACT FROM AUTHOR]

The frequent pattern tree (FP-tree. is an efficient data structure for association-rule mining without generation of candidate itemsets. It was used to compress a database into a tree structure which stored only large items. It, however, needed to process all transactions in a batch way. In the past, we proposed a Fast Updated FP-tree (FUFP-tree. structure to efficiently handle new transactions and to make the tree update process become easier. In this paper, we propose the structure of prelarge trees to incrementally mine association rules based on the concept of pre-large itemsets. Due to the properties of pre-large concepts, the proposed approach does not need to rescan the original database until a number of new transactions have been inserted. The proposed approach can thus achieve a good execution time for tree construction especially when a small number of transactions are inserted each time. Experimental results also show that the proposed approach has a good performance for incrementally handling new transactions. [ABSTRACT FROM AUTHOR]

This paper develops tests and validates a model for the antecedents of open source software (OSS) defects, using Data and Text Mining. The public archives of OSS projects are used to access historical data on over 5,000 active and mature OSS projects. Using domain knowledge and exploratory analysis, a wide range of variables is identified from the process, product, resource, and end-user characteristics of a project to ensure that the model is robust and considers all aspects of the system. Multiple Data Mining techniques are used to refine the model and data is enriched by the use of Text Mining for knowledge discovery from qualitative information. The study demonstrates the suitability of Data Mining and Text Mining for model building. Results indicate that project type, end-user activity, process quality, team size and project popularity have a significant impact on the defect density of operational OSS projects. Since many organizations, both for profit and not for profit, are beginning to use Open Source Software as an economic alternative to commercial software, these results can be used in the process of deciding what software can be reasonably maintained by an organization. [ABSTRACT FROM AUTHOR]

In recent years, a number of indirect data collection methodologies have led to the proliferation of uncertain data. Such databases are much more complex because of the additional challenges of representing the probabilistic information. In this paper, we provide a survey of uncertain data mining and management applications. We will explore the various models utilized for uncertain data representation. In the field of uncertain data management, we will examine traditional database management methods such as join processing, query processing, selectivity estimation, OLAP queries, and indexing. In the field of uncertain data mining, we will examine traditional mining problems such as frequent pattern mining, outlier detection, classification, and clustering. We discuss different methodologies to process and mine uncertain data in a variety of forms. [ABSTRACT FROM AUTHOR]

A variety of real-world applications heavily rely on an adequate analysis of transient data streams. Due to the rigid processing requirements of data streams, common analysis techniques as known from data mining are not directly applicable. A fundamental building block of many data mining and analysis approaches is density estimation. It provides a well-defined estimation of a continuous data distribution, a fact which makes its adaptation to data streams desirable. A convenient method for density estimation utilizes kernels. The computational complexity of kernel density estimation, however, renders its application to data streams impossible. In this paper, we tackle this problem and propose our Cluster Kernel approach, which provides continuously computed kernel density estimators over streaming data. Not only do Cluster Kernels meet the rigid processing requirements of data streams, but they also allocate only a constant amount of memory, even with the opportunity to adapt it dynamically to changing system resources. For this purpose, we develop an intelligent merge scheme for Cluster Kernels and utilize continuously collected local statistics to resample already processed data. We validate the efficacy of Cluster Kernels for a variety of real-world data streams in an extensive experimental study. [ABSTRACT FROM AUTHOR]

A number of algorithms have been proposed for the discovery of temporal patterns. However, since the number of generated patterns can be large, selecting which patterns to analyze can be nontrivial. There is thus a need for algorithms and tools that can assist in the selection of discovered patterns so that subsequent analysis can be performed in an efficient and, ideally, interactive manner. In this paper, we propose a signature-based indexing method to optihiize the storage and retrieval of a large collection of relative temporal patterns. [ABSTRACT FROM AUTHOR]

Generally speaking, to implement Apriori-based association rule mining in hardware, one has to load candidate iten~sets and a database into the hardware. Since the capacity of the hardware architecture is fixed, if the number of candidate itemsets dr the number of items in the database is larger than the hardware capacity, the items are loaded into the hardware separately. The time complexity of those steps that need to load candidate itemsets or database items into the hardware is in proportion to the number of candidate itemsets multiplied by the number of items in the database. Too many candidate itemsets and a large database would create a performance bottleneck. In this paper, we propose a HAsh-based and PiPellned (abbreviated as HAPPI) architecture for hardware- enhanced association rule mining. We apply the pipeline methodology in the HAPPI architecture to compare itemsets with the database and collect useful information for reducing the number of candidate itemsets and items in the database simultaneou~ly. When the database is fed into the hardware, candidate itemsets are ~ompared with the items in the database to find frequent itemsets. At the same time, trimming information is collected from each transaction. In addition, itemsets are generated from transactions and hashed into a hash table. The useful trimming information and the hash table enable us to reduce the number of items in the database and the number of candidate itemsets. Therefore, we can effectively reduce the frequency of loading the database into the hardware. As such, HAPPI solves the bottleneck problem in a priori-based hardware schemes. We also derive some properties to investigate the performance of this hardware implementation. As shown by the experiment results, HAPPI significantly outperforms the previous hardware approach and the software algorithm in terms of execution time. [ABSTRACT FROM AUTHOR]

We examine the problem of efficient distance-based similarity search over high-dimensional data. We show that a promising approach to this problem is to reduce dimensions and allow fast approximation. Conventional reduction approaches, however, entail a significant shortcoming: The approximation volume extends across the dataspace, which causes overestimation of retrieval sets and impairs performance. This paper focuses on a new criterion for dimensionality reduction methods: bounded approximation. We show that this requirement can be accomplished by a novel nonlinear transformation scheme that extracts t~vo important parameters from the data. We devise two approximation formulations, namely, rectangular and spherical range search, each corresponding to a closed volume around the original search sphere. We discuss in detail how we can derive tight bounds for the parameters and prove further results, as well as highlight insights into the problems and our proposed solutions. To demonstrate, the benefits of the new criterion, we study the effects of (un)boundedness on approximation performance, including selectivity, error toleration, and efficiency. Extensive experiments confirm the superiority of this technique over recent state-of-the-art schemes. [ABSTRACT FROM AUTHOR]

There is significant interest in the data mining and network management communities about the need to improve existing techniques for clustering multivariate network traffic flow records so that we can quickly infer underlying traffic patterns. In this paper, we investigate the use of clustering techniques to identify interesting traffic patterns from network traffic data in an efficient manner~ We develop a framework to deal with mixed type attributes including numerical, categorical, and hierarchical attributes for a one-pass hierarchical clustering algorithm. We demonstrate the improved accuracy and efficiency of our approach in comparison to previous work on clustering network traffic. [ABSTRACT FROM AUTHOR]

Similarity-based search has been a key factor for many applications, such as multimedia retrieval, data mining, web search and retrieval, and so on. There are two important issues related to the the similarity search, namely the design of a distance function to measure the similarity, and improving the search efficiency. Many distance functions have been proposed that attempt to closely mimic human recognition. Unfortunately, some of these well-designed distance functions do not follow the triangle inequality, and are, therefore, non-metric. As a consequence, efficient retrieval using these non-metric distance functions becomes more challenging, since most existing index structures assume that the indexed distance functions are metric. In this paper, we address this challenging problem by proposing an efficient method, local constant embedding (LCE), which divides the data set into disjoint groups, so that the triangle inequality holds within each group by constant shifting. Furthermore, we design a pivot selection approach for the converted metric distance and create an index structure to speed up the retrieval efficiency. Extensive experiments show that, our method works well on various non-metric distance functions and improves the retrieval efficiency by an order of magnitude compared to the linear scan and existing retrieval approaches with no false dismissals. [ABSTRACT FROM AUTHOR]

We study a new data mining problem concerning the discovery of frequent agreement subtrees (FASTs) from a set of phylogenetic trees. A phylogenetic tree, or phylogeny, is an unordered tree in which the order among siblings is unimportant. Furthermore, each leaf in the tree has a label representing a taxon (species or organism) name, whereas internal nodes are unlabeled. The tree may have a root, representing the common ancestor of all species in the tree, or may be unrooted. An unrooted phylogeny arises due to the lack of sufficient evidence to infer a common ancestor of the taxa in the tree. The FAST problem addressed here is a natural extension of the maximum agreement subtree (MAST) problem widely studied in the computational phylogenetics community. The paper establishes a framework for tackling the FAST problem for both rooted and unrooted phylogenetic trees using data mining techniques. We first develop a novel canonical form for rooted trees together with a phylogeny-aware tree expansion scheme for generating candidate subtrees level by level. Then, we present an efficient algorithm to find all FASTs in a given set of rooted trees, through an Apriori-like approach. We show the correctness and completeness of the proposed method. Finally, we discuss the extensions of the techniques to unrooted trees. Experimental results demonstrate that the proposed methods work well, and are capable of finding interesting patterns in both synthetic data and real phylogenetic trees. [ABSTRACT FROM AUTHOR]

In this paper, we deal with mining sequential patterns in multiple time sequences. Building on a state-of-the-art sequential pattern mining algorithm PrefixSpan for mining transaction databases, we propose MILE (MIning in muLtiple sEquences), an efficient algorithm to facilitate the mining process. MILE recursively utilizes the knowledge of existing patterns to avoid redundant data scanning, and therefore can effectively speed up the new patterns' discovery process. Another unique feature of MILE is that it can incorporate prior knowledge of the data distribution in time sequences into the mining process to further improve the performance. Extensive empirical results show that MILE is significantly faster than PrefixSpan. As MILE consumes more memory than PrefixSpan, we also present a solution to trade time efficiency in memory constrained environments. [ABSTRACT FROM AUTHOR]

Patent documents contain important research results. They are often collectively analyzed and organized in a visual way to support decision making. However, they are lengthy and rich in technical terminology, and thus require a lot of human effort for analysis. Automatic tools for assisting patent engineers or decision makers in patent analysis are in great demand. This paper describes a summarization method for patent surrogate extraction, intended to efficiently and effectively support patent mapping, which is an important subtask of patent analysis. Six patent maps were used to evaluate its relative usefulness. The experimental results confirm that the machine generated summaries do preserve more important content words than some other patent sections or even than the full patent texts when only a few terms are to be considered for classification and mapping. The implication is that if one were to determine a patent's category based on only a few terms at a quick pace, one could begin by reading the section summaries generated automatically. [ABSTRACT FROM AUTHOR]

Since its foundation in the early 1980's, Formal ConceptAnalysis (FCA) has been used in many applications in data analysis, information retrieval, and knowledge discovery. In this paper, we suggest to exploit the framework of relational database model (RDM) and rough relational database model (RRDM) for Formal Concept Analysis. The basic idea is as follows. We firstly treat any relation (R,A) of RDM as a many-valued context of FCA. But for the rough relations of RRDM, we define a special kind of many-valued context – rough-relational context in FCA (In this kind of context, every attribute value is a subset, but not an element, of the corresponding attribute domain), and treat any rough relation (R,A) of RRDMas a rough-relational context of FCA. Correspondingly, the definitions for concepts or rough concepts in context or rough-relational context (R,A) are given. The basic properties about these concepts or rough concepts in (R,A) are also discussed. [ABSTRACT FROM AUTHOR]

In this paper, we mainly address the problem of loading transaction datasets into main memory and estimating the density of such datasets. We propose BOOLLOADER, an algorithm dedicated to these tasks; it relies on a compressed representation of all the transactions of the dataset. For sake of efficiency, we have chosen Decision Diagrams as the main data structure to the representation of datasets into memory. We give an experimental evaluation of our algorithm on both dense and sparse datasets. Experiments have shown that BOOLLOADER is efficient for loading some dense datasets and gives a partial answer about the nature of the dataset before time-consuming pattern extraction tasks. We further investigate the use of Algebraic Decision Diagrams by studying the feasibility of current Data Mining operations, as for instance computing the support of an itemset and even mining frequent itemsets. [ABSTRACT FROM AUTHOR]

Text documents are the most common means for exchanging formal knowledge among people. Text is a rich medium that can contain a vast range of information, but text can be difficult to decipher automatically. Many organizations have vast repositories of textual data but with few means of automatically mining that text. Text mining methods seek to use an understanding of natural language text to extract information relevant to user needs. This article evaluates a new text mining methodology: prototype-matching for text clustering, developed by the authors' research group. The methodology was applied to four applications: clustering documents based on their abstracts, analyzing financial data, distinguishing authorship, and evaluating multiple translation similarity. The results are discussed in terms of common business applications and possible future research. [ABSTRACT FROM AUTHOR]

Recently, relevance feedback (RF) in content-based image retrieval (CBIR) has been implemented as an online binary classifier to separate the positive samples from the negative samples, where both sets of samples are labeled by the user. In many applications, it is reasonable to assume that all the positive samples are alike and thus that the region of the feature space occupied by the positive samples can be described by a single hypersurface. However, for the negative samples, previous RF methods either treat each one of the negative samples as an isolated point or assume the whole negative set can be described by a single convex hypersurface. In this paper, we argue that these treatments of the negative samples are not sound. Our belief is all positive samples are included in a set and the negative samples split into a small number of subsets, each one of which has a simple distribution. Therefore, we first cluster the negative samples into several groups; for each such negative group, we build a marginal convex machine (MCM) subclassifier between it and the single positive group which results in a series of subclassifiers. These subclassifiers are then incorporated into a biased MOM (BMCM) for RF. Experiments were carried out to prove the advantages of BMCM-based RF over previous methods for RF. [ABSTRACT FROM AUTHOR]

In many applications that track and analyze spatiotemporal data, movements obey periodic patterns; the objects follow the same routes (approximately) over regular time intervals. For example, people wake up at the same time and follow more or less the same route to their work everyday. The discovery of hidden periodic patterns in spatiotemporal data could unveil important information to the data analyst. Existing approaches for discovering periodic patterns focus on symbol sequences. However, these methods cannot directly be applied to a spatiotemporal sequence because of the fuzziness of spatial locations in the sequence. In this paper, we define the problem of mining periodic patterns in spatiotemporal data and propose an effective and efficient algorithm for retrieving maximal periodic patterns. In addition, we study two interesting variants of the problem. The first is the retrieval of periodic patterns that are frequent only during a continuous subinterval of the whole history. The second problem is the discovery of periodic patterns, whose instances may be shifted or distorted. We demonstrate how our mining technique can be adapted for these variants. Finally, we present a comprehensive experimental evaluation, where we show the effectiveness and efficiency of the proposed techniques. [ABSTRACT FROM AUTHOR]

Mining frequent patterns on streaming data is a new challenging problem for the data mining community since data arrives sequentially in the form of continuous rapid streams. In this paper we propose a new approach for mining itemsets. Our approach has the following advantages: an efficient representation of items and a novel data structure to maintain frequent patterns coupled with a fast pruning strategy. At any time, users can issue requests for frequent itemsets over an arbitrary time interval. Furthermore our approach produces an approximate answer with an assurance that it will not bypass user-defined frequency and temporal thresholds. Finally the proposed method is analyzed by a series of experiments on different datasets. [ABSTRACT FROM AUTHOR]

Association rule is one of the data mining techniques involved in discovering information that represents the association among data. Data in the database sometimes appear infrequent but highly associated with a specific data. This paper proposes a technique for significant rare data by introducing second support in discovering the association rules of such data. We show that the proposed approach provides better performance as compared to standard association rules techniques. [ABSTRACT FROM AUTHOR]

In many data mining applications that address classification problems, feature and model selection are considered as key tasks. That is, appropriate input features of the classifier must be selected from a given (and often large) set of possible features and structure parameters of the classifier must be adapted with respect to these features and a given data set. This paper describes an evolutionary algorithm (EA) that performs feature and model selection simultaneously for radial basis function (RBF) classifiers. In order to reduce the optimization effort, various techniques are integrated that accelerate and improve the EA significantly: hybrid training of RBF networks, lazy evaluation, consideration of soft constraints by means of penalty terms, and temperature-based adaptive control of the EA. The feasibility and the benefits of the approach are demonstrated by means of four data mining problems: intrusion detection in computer networks, biometric signature verification, customer acquisition with direct marketing methods, and optimization of chemical production processes. It is shown that, compared to earlier EA-based RBF optimization techniques, the runtime is reduced by up to 99% while error rates are lowered by up to 86%, depending on the application. The algorithm is independent of specific applications so that many ideas and solutions can be transferred to other classifier paradigms. [ABSTRACT FROM AUTHOR]

Data mining techniques provide people with new power to research and manipulate the existing large volume of data. A data mining process discovers interesting information from the hidden data that can either be used for future prediction and/or intelligently summarising the details of the data. There are many achievements of applying data mining techniques to various areas such as marketing, medical, and financial, although few of them can be currently seen in software engineering domain. In this paper, a proposed data mining application in software engineering domain is explained and experimented. The empirical results demonstrate the capability of data mining techniques in software engineering domain and the potential benefits in applying data mining to this area. [ABSTRACT FROM AUTHOR]

K-optimal rule discovery finds the k rules that optimize a user-specified measure of rule value with respect to a set of sample data and user-specified constraints. This approach avoids many limitations of the frequent itemset approach of association rule discovery. This paper presents a scalable algorithm applicable to a wide range of k-optimal rule discovery tasks and demonstrates its efficiency. [ABSTRACT FROM AUTHOR]

Copyright of El Profesional de la Información is the property of EPI SCP and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Frequent-pattern mining has been studied extensively and has many useful applications. However, frequent-pattern mining often generates too many patterns to be truly efficient or effective. In many applications, it is sufficient to generate and examine frequent patterns with a sufficiently good approximation of the support frequency instead of in full precision. Such a compact but “close-enough” frequent-pattern base is called acondensed frequent-pattern base.In this paper, we propose and examine several alternatives for the design, representation, and implementation of such condensed frequent-pattern bases. Several algorithms for computing such pattern bases are proposed. Their effectiveness at pattern compression and methods for efficiently computing them are investigated. A systematic performance study is conducted on different kinds of databases, and demonstrates the effectiveness and efficiency of our approach in handling frequent-pattern mining in large databases. [ABSTRACT FROM AUTHOR]

TopCat (Topic Categories) is a technique for identifying topics that recur in articles in a text corpus. Natural language processing techniques are used to identify key entities in individual articles, allowing us to represent an article as a set of items. This allows us to view the problem in a database/data mining context: Identifying related groups of items. This paper presents a novel method for identifying related items based on traditional data mining techniques. Frequent itemsets are generated from the groups of items, followed by clusters formed with a hypergraph partitioning scheme. We present an evaluation against a manually categorized ground truth news corpus; it shows this technique is effective in identifying topics in collections of news articles. [ABSTRACT FROM AUTHOR]

The automated analysis of transcriptional profiling data promises a wealth of information that may be used to develop a more complete understanding of gene function and interactions. Moreover, it may improve the effectiveness of complex diagnostic tasks. This article discusses important data mining and management techniques to analyse genome-wide expression data. It reviews some of the major discovery goals, methods and applications in a number of biomedical domains. Finally, this paper highlights key problems that need to be approached by a new generation of computational solutions. [ABSTRACT FROM AUTHOR]

In this era of web, we have a huge amount of information overload over internet. To extract useful information, filtering is required. Search engines help to solve this problem to some extent but they do not provide personalization of data. Hence, there is a need of recommendation engine. With the help of recommender software the preferences of user for a particular product can be foreseen. Recommender systems help in pinpointing the required information thereby deescalating unwanted information. Collaborative filtering is the most efficient approach to create recommendations so that the identified choices of a user's group can be used to envisage the preferences for other users which are not yet known to them. Through this paper we endeavor to present a thorough survey of collaborative filtering methods that can help in future for further research in this field and thereby propose a solution to enhance the precision and recall measures of recommendations. [ABSTRACT FROM AUTHOR]

Introduces a series of articles on advances in the area of data mining and knowledge discovery with evolutionary algorithms. Information on classification as a task of data mining; Algorithm for knowledge discovery from texts; Data reduction in knowledge discovery in databases.