Abstract This paper provides a unified description of Widening, a framework for the use of parallel (or otherwise abundant) computational resources to improve model quality. We discuss different theoretical approaches to Widening with and without consideration of diversity. We then soften some of the underlying constraints so that Widening can be implemented in real world algorithms. We summarize earlier experimental results demonstrating the potential impact as well as promising implementation strategies before concluding with a survey of related work.

Index investing has an advantage over active investment strategies, because less frequent trading results in lower expenses, yielding higher long-term returns. Index tracking is a popular investment strategy that attempts to find a portfolio replicating the performance of a collection of investment vehicles. This paper considers index tracking from the perspective of solution space exploration. Three search space heuristics in combination with three portfolio tracking error methods are compared in order to select a tracking portfolio with returns that mimic a benchmark index. Experimental results conducted on real-world datasets show that Widening, a metaheuristic using diverse parallel search paths, finds superior solutions than those found by the reference heuristics. Presented here are the first results using Widening on time-series data.

Given a large bipartite graph that represents objects and their properties, how can we automatically extract semantic information that provides an overview of the data and -- at the same time -- enables us to drill down to specific parts for an in-depth analysis? In this work, we propose extracting a taxonomy that models the relation between the properties via an is a hierarchy. The extracted taxonomy arranges the properties from general to specific providing different levels of abstraction. Our proposed method has the following desirable properties: (a) it requires no user-defined parameters, by exploiting the principle of minimum description length, (b) it is effective, by utilizing the inheritance of objects when representing the hierarchy, and (c) it is scalable, being linear in the number of edges. We demonstrate the effectiveness and scalability of our method on a broad spectrum of real, publicly available graphs from drug-property graphs to social networks with up to 22 million vertices and 286 million edges.

BACKGROUND: Cheminformaticians have to routinely process and analyse libraries of small molecules. Among other things, that includes the standardization of molecules, calculation of various descriptors, visualisation of molecular structures, and downstream analysis. For this purpose, scientific workflow platforms such as the Konstanz Information Miner can be used if provided with the right plug-in. A workflow-based cheminformatics tool provides the advantage of ease-of-use and interoperability between complementary cheminformatics packages within the same framework, hence facilitating the analysis process. RESULTS: KNIME-CDK comprises functions for molecule conversion to/from common formats, generation of signatures, fingerprints, and molecular properties. It is based on the Chemistry Development Toolkit and uses the Chemical Markup Language for persistence. A comparison with the cheminformatics plug-in RDKit shows that KNIME-CDK supports a similar range of chemical classes and adds new functionality to the framework. We describe the design and integration of the plug-in, and demonstrate the usage of the nodes on ChEBI, a library of small molecules of biological interest. CONCLUSIONS: KNIME-CDK is an open-source plug-in for the Konstanz Information Miner, a free workflow platform. KNIME-CDK is build on top of the open-source Chemistry Development Toolkit and allows for efficient cross-vendor structural cheminformatics. Its ease-of-use and modularity enables researchers to automate routine tasks and data analysis, bringing complimentary cheminformatics functionality to the workflow environment.

This work addresses two challenges in combination: learning with a very limited number of labeled training examples (active learning) and learning in the presence of multiple views for each object where the global model to be learned is spread out over some or all of these views (learning in parallel universes). We propose a new active learning approach which selects the best samples to query the label with the goal of improving overall model accuracy and determining which universe contributes most to the local model. The resulting combination and class-specific weighting of universes provides a significantly better classification accuracy than traditional active learning methods.

In this paper we propose two methods to derive two different kinds of node similarities in a network based on their neighborhood. The first similarity measure focuses on the overlap of direct and indirect neighbors. The second similarity compares nodes based on the structure of their - possibly also very distant - neighborhoods. Instead of using standard node measures, both similarities are derived from spreading activation patterns over time. Whereas in the first method the activation patterns are directly compared, in the second method the relative change of activation over time is compared. We apply both methods to a real-world graph dataset and discuss the results.

In this paper we introduce a modular, highly flexible, open-source environment for data generation. Using an existing graphical data flow tool, the user can combine various types of modules for numeric and categorical data generators. Additional functionality is added via the data processing framework in which the generator modules are embedded. The resulting data flows can be used to document, deploy, and reuse the resulting data generators. We describe the overall environment and individual modules and demonstrate how they can be used for the generation of a sample, complex customer/product database with corresponding shopping basket data, including various artifacts and outliers.

Distance aware tag clouds add visualization of relations between terms to standard tag clouds. In addition to term importance (which is usually depicted through font size) the placement of terms represents the relation between words in the corpus. These relations are modeled as similarities between words and are visualized via the distance between the corresponding tags in the tag cloud. In this paper a modified multi-dimensional scaling (MDS) approach for tag positioning is presented. Applying standard MDS results in unsatisfying and unusable representations due to two problems. The first problem stems from word overlap which is orthogonal to the second problem: excessive empty space. Both of these shortcomings are addressed by introducing methods for overlap removal and empty space reduction. We show that these two modifications only moderately increase the resulting MDS stress value of the new positioning while they remove most of the overlaps and reduce the amount of white space.

Almost every application of spreading activation is accompanied by its own set of often heuristic restrictions on the dynamics. We show that in constraint-free scenarios spreading activation would actually yield query-independent results, so that the specific choice of restrictions is not only a pragmatic computational issue, but crucially determines the outcome.

Genetic algorithms are often applied to combinatorial opti-mization problems, the most popular one probably being the traveling salesperson problem. In contrast to permutations used for TSP, the selection of a subset from a larger set has so far gained surprisingly little interest. One intriguing ex-ample of this type of problems occurs in diversity selection for virtual high throughput screening, where k molecules need to be selected from a set of n while optimizing certain constraints. In this paper we present a novel representation for k-subsets and several genetic operators for it.

At KDD-2009 in Paris, a panel on open standards and cloud computing addressed emerging trends for data mining applications in science and industry. This report summarizes the answers from a distinguished group of thought leaders representing key software vendors in the data mining industry.

This paper presents two approaches to visually analyze the topic shift of a pool of documents over a given period of time. The first of the proposed methods is based on a multi-dimensional scaling algorithm, which places vectors representing terms occurring in certain years (period-frequency-vectors) in a spatial, two-dimensional space. This kind of visualization enables the detection of terms occurring in documents, published in particular years, or terms spread over different years. The second method uses a graph based approach. Publishing dates of documents, as well as their terms are represented by the vertices of a graph. Terms related to a specific publishing year are connected to the vertex of the year via an edge. By usage of activation spreading techniques, terms frequently occurring in documents published in particular years can be discovered visually. We tested both approaches with 2431 abstracts of papers published in the IEEE Transactions on SMC-A, SMC-B, and SMC-C in the years 1996 to 2006. Our experiments indicate that a number of interesting terms can be nicely separated in clumps according to individual years or periods of time. In addition, one can visualize the emergence of specific terms over certain periods of time and how these and other terms fade away again later.

This paper presents an approach to visualizing and exploring high-dimensional rules in two-dimensional views. The proposed method uses multi-dimensional scaling to place the rule centers and subsequently extends the rules' regions to depict their overlap. This results not only in a visualization of the rules' distribution but also enables the relationship to their immediate neighbors to be judged. The proposed technique is illustrated and discussed on a number of well-known benchmark data sets.

In this paper, we present a Dynamic Load Balancing (DLB) policy for problems characterized by a highly irregular search tree, whereby no reliable workload prediction is available. DLB approaches based on global statistics are known to provide optimal load balancing performance, while randomized techniques provide high scalability. The proposed method combines both advantages and adopts distributed job-pools and a randomized polling policy. The method has been successfully adopted in a parallel search algorithm for sugbraph mining. The work load distribution process of the parallel application is based on a dynamic partitioning of the search space and a peer-to-peer communication framework. The effectiveness of the DLB method has been evaluated on a molecular biology dataset. The distributed application with the novel DLB method has shown good scalability and close-to linear speedup in a distributed network of workstations. Moreover, fault tolerance and dynamic resource aggregation make it suitable for largescale, multi-domain, heterogeneous environments, such as computational Grids.

In molecular biology, it is often desirable to find common properties in large numbers of drug candidates. One family of methods stems from the data mining community, where algorithms to find frequent graphs have received increasing attention over the past years. However, the computational complexity of the underlying problem and the large amount of data to be explored essentially render sequential algorithms useless. In this paper, we present a distributed approach to the frequent subgraph mining problem to discover interesting patterns in molecular compounds. This problem is characterized by a highly irregular search tree, whereby no reliable workload prediction is available. We describe the three main aspects of the proposed distributed algorithm, namely, a dynamic partitioning of the search space, a distribution process based on a peer-to-peer communication framework, and a novel receiver-initiated load balancing algorithm. The effectiveness of the distributed method has been evaluated on the well-known National Cancer Institute's HIV-screening data set, where we were able to show close-to linear speedup in a network of workstations. The proposed approach also allows for dynamic resource aggregation in a nondedicated computational environment. These features make it suitable for large-scale, multidomain, heterogeneous environments, such as computational grids

In this paper, we show how an existing fuzzy rule induction algorithm can incorporate missing values in the training procedure in a very natural way. The underlying algorithm generates rules which restrict the feature space only along a few, important attributes. This property can be used to limit the algorithm's three major steps to the reduced feature space for each training instance, which allows the features for which no values are known to be ignored. Hence no replacement is necessary and the algorithm simply uses all available knowledge from each training instance. We demonstrate on data sets from the UCI repository that this method works well, generates rule sets that have comparable classification accuracy, and are, at times, even smaller than the rule sets generated by the original algorithm

Most learning algorithms operate in a clearly defined feature space and assume that all relevant structure can be found in this one, single space. For many local learning methods, especially the ones working on distance metrics (e.g. clustering algorithms) this poses a serious limitation. We discuss an algorithm that directly finds a set of cluster centers based on an analysis of the distribution of patterns in the local neighborhood of each potential cluster center through the use of so-called Neighborgrams. This type of cluster construction makes it feasible to find clusters in several feature spaces in parallel, effectively finding the optimal feature space for each cluster independently. We demonstrate how the algorithm works on an artificial data set and show its usefulness using a well-known benchmark data set.

Often, it is desirable to represent a set of time series through typical shapes in order to detect common patterns. The algorithm presented here compares pieces of a different time series in order to find such similar shapes. The use of a fuzzy clustering technique based on fuzzy c-means allows us to detect shapes that belong to a certain group of typical shapes with a degree of membership. Modifications to the original algorithm also allow this matching to be invariant with respect to a scaling of the time series. The algorithm is demonstrated on a widely known set of data taken from the electrocardiogram (ECG) rhythm analysis experiments performed at the Massachusetts Institute of Technology (MIT) laboratories and on data from protein mass spectrography. © 2004 Wiley Periodicals, Inc.

We describe an interactive method to generate a set of fuzzy clusters for classes of interest of a given, labeled data set. The presented method is therefore best suited for applications where the focus of analysis lies on a model for the minority class or for small- to medium-size data sets. The clustering algorithm creates one-dimensional models of the neighborhood for a set of patterns by constructing cluster candidates for each pattern of interest and then chooses the best subset of clusters that form a global model of the data. The accompanying visualization of these neighborhoods allows the user to interact with the clustering process by selecting, discarding, or fine-tuning potential cluster candidates. Clusters can be crisp or fuzzy and the latter leads to a substantial improvement of the classification accuracy. We demonstrate the performance of the underlying algorithm on several data sets from the StatLog project.

Exploratory data analysis heavily relies on methods to visualize data and models in a user friendly and interpretable manner. We show how models consisting of a collection of fuzzy points can be visualized in parallel coordinates. In contrast to existing techniques that display only lines representing centroids or shaded areas showing the general variance of cluster centers, the proposed technique shows the spread of the fuzzy membership in each dimension in detail. This allows for a better interpretation of overlap in fuzzy rules.

It is often desirable to summarize a set of time series through typical shapes in order to analyze them. The algorithm presented here compares pieces of different time series in order to find similar shapes. The use of a fuzzy clustering technique based on fuzzy c-means allows us to consider such subsets belonging to typical shapes with a degree of membership. Additionally, this matching is invariant with respect to a scaling of the time series. The algorithm is demonstrated on a widely known set of data taken from the ECG rhythm analysis experiments performed at MIT laboratories.

We describe an interactive way to generate a set of clusters for a given data set. The clustering is done by constructing local histograms, which can then be used to visualize, select, and fine-tune potential cluster candidates. The accompanying algorithm can also generate clusters automatically, allowing for an automatic or semi-automatic clustering process where the user only occasionally interacts with the algorithm. We illustrate the ability to automatically identify and visualize clusters using NCI's AIDS Antiviral Screen data set.

We present an algorithm to find fragments in a set of molecules that help to discriminate between different classes of for instance, activity in a drug discovery context. Instead of carrying out a brute-force search, our method generates fragments by embedding them in all appropriate molecules in parallel and prunes the search tree based on a local order of the atoms and bonds, which results in substantially faster search by eliminating the need for frequent, computationally expensive reembeddings and by suppressing redundant search. We prove the usefulness of our algorithm by demonstrating the discovery of activity-related groups of chemical compounds in the well-known National Cancer Institute's HIV-screening dataset.

Many clustering algorithms have been proposed in recent years. Most methods operate in an iterative manner and aim to optimize a specific energy function. We present an algorithm that directly finds a set of cluster centers based on an analysis of the distribution of patterns in the local neighborhood of each potential cluster center through the use of so-called neighborgrams. In addition, this analysis can be carried out in several feature spaces in parallel, effectively finding the optimal set of features for each cluster independently. We demonstrate how the algorithm works on an artificial data set and show its usefulness using a well-known benchmark data set.

Many real-world applications have very high dimensionality and require very complex decision borders. In this case, the number of fuzzy rules can proliferate, and the easy interpretability of fuzzy models can progressively disappear. An important part of the model interpretation lies on the evaluation of the effectiveness of the input features on the decision process. In this paper, we present a method that quantifies the discriminative power of the input features in a fuzzy model. The separability among all the rules of the fuzzy model produces a measure of the information available in the system. Such measure of information is calculated to characterize the system before and after each input feature is used for classification. The resulting information gain quantifies the discriminative power of that input feature. The comparison among the information gains of the different input features can yield better insights into the selected fuzzy classification strategy, even for very high dimensional cases, and can lead to a possible reduction of the input space dimension. Several artificial and real-world data analysis scenarios are reported as examples in order to illustrate the characteristics and potentialities of the proposed method.

Methods to build function approximators from example data have gained considerable interest in the past. Especially methodologies that build models that allow an interpretation have attracted attention. Most existing algorithms, however, are either complicated to use or infeasible for high-dimensional problems. This article presents an efficient and easy to use algorithm to construct fuzzy graphs from example data. The resulting fuzzy graphs are based on locally independent fuzzy rules that operate solely on selected, important attributes. This enables the application of these fuzzy graphs also to problems in high dimensional spaces. Using illustrative examples and a real world data set it is demonstrated how the resulting fuzzy graphs offer quick insights into the structure of the example data, that is, the underlying model. The underlying algorithm is demonstrated using several Java applets, which can be found under ‘Electronic annexes’ on www.elsevier.com/locate/ida.

In this paper a technique is proposed to tolerate missing values based on a system of fuzzy rules for classification. The presented method is mathematically solid but nevertheless easy and efficient to implement. Three possible applications of this methodology are outlined: the classification of patterns with an incomplete feature vector, the completion of the input vector when a certain class is desired, and the training or automatic construction of a fuzzy rule set based on incomplete training data. In contrast to a static replacement of the missing values, here the evolving model is used to predict the most possible values for the missing attributes. Benchmark datasets are used to demonstrate the capability of the presented approach in a fuzzy learning environment.

Radial Basis Function (RBF) Networks, also known as networks of locally-tuned processing units (see [6]) are well known for their ease of use. Most algorithms used to train these types of net(cid:173) works, however, require a fixed architecture, in which the number of units in the hidden layer must be determined before training starts. The RCE training algorithm, introduced by Reilly, Cooper and Elbaum (see [8]), and its probabilistic extension, the P-RCE algorithm, take advantage of a growing structure in which hidden units are only introduced when necessary. The nature of these al(cid:173) gorithms allows training to reach stability much faster than is the case for gradient-descent based methods. Unfortunately P-RCE networks do not adjust the standard deviation of their prototypes individually, using only one global value for this parameter. This paper introduces the Dynamic Decay Adjustment (DDA) al(cid:173) gorithm which utilizes the constructive nature of the P-RCE al(cid:173) gorithm together with independent adaptation of each prototype's decay factor. In addition, this radial adjustment is class dependent and distinguishes between different neighbours. It is shown that networks trained with the presented algorithm perform substan(cid:173) tially better than common RBF networks. 522 Michael R. Berthold, Jay Diamond