The nearest neighbor rule is a classic yet essential classification model, particularly in problems where the supervising information is given by pairwise dissimilarities and the embedding function are not easily obtained. Prototype selection provides means of generalization and improving efficiency of the nearest neighbor model, but many existing methods assume and rely on the analyses of the input vector space. In this paper, we explore a dissimilarity-based, parametrized model of the nearest neighbor rule. In the proposed model, the selection of the nearest prototypes is influenced by the parameters of the respective prototypes. It provides a formulation for minimizing the violation of the extended nearest neighbor rule over the training set in a tractable form to exploit numerical techniques. We show that the minimization problem reduces to a large-margin principle learning and demonstrate its advantage by empirical comparisons with other prototype selection methods.

One of the effective methodologies for time series classification is to identify informative subsequence patterns in time series and exploit them as discriminative features. Previous studies on this methodology have achieved promising results using a small number of individually selected patterns. However, there remain difficulties in finding a set of related patterns or patterns of a minor class, which can be critical in real-world applications. In this paper, we exploit the sparse learning technique for the support vector machine (SVM) to identify informative and exemplary patterns. We first present a representation of time series as a vector of distances to exemplary patterns. It allows a structural SVM to handle distance space data and function as the nearest neighbor classifier, the combination of which is known to be highly competitive in time series classification. We then extend the zero-norm approximation method for the structural SVM, which can eliminate non-essential patterns from the classification model. The resulting model makes predictions by a simple modified nearest neighbor rule, yet has a strong mathematical support for empirical risk minimization and feature selection. We conduct an empirical study on real-world behavior and sequential data to evaluate the effectiveness of the proposed method and graphically examine the exemplary patterns.

In this paper, we address a classification task under a time-sensitive setting, in which the amount of observation required to make a prediction is viewed as a practical cost. Such a setting is intrinsic in many systems where the potential reward of the action against the predicted event depends on the response time, e.g., surveillance/warning and diagnostic applications. Meanwhile, predictions are usually less reliable when based on fewer observations, i.e., there exists a trade-off between such temporal cost and the accuracy. We address the task as a classification of subsequences in a time series. The goal is to predict the occurrences of events from subsequent observations and to learn when to commit to the prediction considering the trade-off. We propose an ensemble of classifiers which respectively makes predictions based on subsequences of different lengths. The prediction of the ensemble is given by the earliest confident prediction among the individual classifiers. We propose a cutting-plane algorithm for jointly training an ensemble of linear classifiers considering their temporal dependence. We compare the proposed algorithm against conventional approaches over a collection of behavioral trajectory data.

Learning from dyadic and relational data is a fundamental problem for IR and KDD applications in web and social media domain. Basic behaviors and characteristics of users and documents are typically described by a collection of dyads, i.e., pairs of entities. Discriminative features extracted from such data are essential in exploratory and discriminatory analyses. Relational properties of the entities reflect pair-wise similarities and their collective community structure which are also valuable for discriminative learning. A challenging aspect of learning from the relational data in many domains, is that the generative process of relational links appears noisy and is not well described by a stochastic model.

Behavior analysis using trajectory data presents a practical and interesting challenge for KDD. Conventional analyses address discriminative tasks of behaviors, e.g., classification and clustering typically using the subsequences extracted from the trajectory of an object as a numerical feature representation. In this paper, we explore further to identify the difference in the high-level semantics of behaviors such as roles and address the task in a cross-domain learning approach. The trajectory, from which the features are sampled, is intuitively viewed as a domain, and we assume that its intrinsic structure is characterized by the underlying role associated with the tracked object. We propose a novel hybrid method of spectral clustering and density approximation for comparing clustering structures of two independently sampled trajectory data and identifying patterns of behaviors unique to a role. We present empirical evaluations of the proposed method in two practical settings using real-world robotic trajectories.

This paper addresses an application of anomaly detection from subsequences of time series (STS) to autonomous robots' behaviors. An important aspect of mining sequential data is selecting the temporal parameters, such as the subsequence length and the degree of smoothing. For example in the task at hand, the patterns of the robot's velocity, which is one of its fundamental features, vary significantly subject to the interval for measuring the displacement. Selecting the time scale and resolution is difficult in unsupervised settings, and is often more critical than the choice of the method. In this paper, we propose an ensemble framework for aggregating anomaly detection from different perspectives, i.e., settings of user-defined, temporal parameters. In the proposed framework, each behavior is labeled whether it is an anomaly in multiple settings. The set of labels are used as meta-features of the respective behaviors. Cluster analysis in a meta-feature space partitions anomalous behaviors pertained to a specific range of parameters. The framework also includes a scalable implementation of the instance-based anomaly detection. We evaluate the proposed framework by ROC analysis, in comparison to conventional ensemble methods for anomaly detection.

The central challenge in temporal data analysis is to obtain knowledge about its underlying dynamics. In this paper, we address the observation of noisy, stochastic processes and attempt to detect temporal segments that are related to inconsistencies and irregularities in its dynamics. Many conventional anomaly detection approaches detect anomalies based on the distance between patterns, and often provide only limited intuition about the generative process of the anomalies. Meanwhile, model-based approaches have difficulty in identifying a small, clustered set of anomalies.

In real-world data mining applications, one often has access to multiple datasets that are relevant to the task at hand. However, learning from such datasets can be difficult as they are often drawn from different domains, i.e., not identically distributed or differ in class or feature sets. In this paper, we consider the problem of learning the class structures %, unique and shared, of related domains in an unsupervised manner. Its setting generalizes that of information filtering and novelty detection applications which addresses both known and unknown classes. We propose a co-clustering framework for estimating and adapting the class structures of two related domains, {enabling the analyses of shared and unique classes.} We define an objective function using interaction information to take account of the divergence between the corresponding clusters of respective domains. We present an iterative algorithm which alternates object and feature clustering and converges to a local minimum of the objective function. We present empirical results using text benchmarks, comparing the proposed algorithm and combinations of conventional approaches in problems of partitioning documents and detecting unknown topics.

Speciation is an important concept in evolutionary computation. It refers to an enhancements of evolutionary algorithms to generate a set ofdiverse solutions. The concept is studied intensively in the evolutionary design of neural network ensembles. Thediversity and cooperation of individual networks are among the essential criteria of the design.This paper proposes a speciation framework for ensemble design which integratesa collection of new techniques. Its characteristic features are:(a) the population of networks are speciated as such thatthe mutual information between the networks' outputs and genotypic representations is preserved. (b) The ensemble is designed incrementally,upon discovery of a species of networks which enhances the ensembleperformance. (c) Multiple species are evolved andindividual networks are evaluated according to therole of their respective species in the ensemble.This framework provides an implementation of evolutionary algorithm which performs simultaneous single-objective optimizations.The new algorithm is evaluated with a series of classification benchmarks andshows an improvement over other evolutionary training strategiesand a statistical algorithm.

Identifying atypical objects is one of the traditional topics in machine learning. Recently, novel approaches, e.g., Minority Detection and One-class clustering, have explored further to identify clusters of atypical objects which strongly contrast from the rest of the data in terms of their distribution or density. This paper analyzes such tasks from an information theoretic perspective. Based on Information Bottleneck formalization, these tasks interpret to increasing the averaged atypicalness of the clusters while reducing the complexity of the clustering. This formalization yields a unifying view of the new approaches as well as the classic outlier detection. We also present a scalable minimization algorithm which exploits the localized form of the cost function over individual clusters. The proposed algorithm is evaluated using simulated datasets and a text classification benchmark, in comparison with an existing method.

This paper discusses a structure of multi-objective optimization problems, which cause deception for conventional multi-objective genetic algorithms (MOGAs). Further, we propose a distributed multi-objective genetic algorithm (DMOGA), which employs a multiple subpopulation implementation and a replacement scheme based on the information theoretic entropy, to improve the performance of MOGA in such deceptive problems. Several studies have reported that the conventional MOGAs' have difficulties in generating marginal segments of the Pareto front in a combinatorial optimization problems, though structural causes of their behaviors have not yet been thoroughly studied. Our analysis of the conventional MOGAs' behaviors in two test deceptive problems suggests that the use of the local density in the selection causes an implicit bias which results in a premature convergence. DMOGA is a distributed implementation of MOGA, which emphasizes the diversity of the subpopulations by the entropy of the objective functions. This approach alleviates the premature convergence and enables MOGA to effectively generate Pareto fronts for complex objective functions. In a set of simulated experiments, the proposed method generated more comprehensive Pareto fronts than the conventional MOGAs, i.e., NSGA-II and SPEA2 in the deceptive test functions, and also achieved comparable performance in the standard multi-objective benchmarks.

Detection of rare and exceptional occurrences in large- scale databases have become an important practice in the field of knowledge discovery and information retrieval. Many databases include large amount of noise or irrelevant data, whose distribution often overlaps with the subsets of exceptional data containing useful knowledge. This paper addresses the problem of finding a small subset of "minority" data whose distribution overlaps with, but are exceptional to or inconsistent with that of the majority of the database. In such a case, conventional distance-based or density-based approaches in Outlier Detection are ineffective due to their dependence on the structure of the majority or the prerequisite of critical parameters. We formalize the task as an estimation of a model of the minority subset which provides a simple description of the subset and yet maintains divergence from that of the majority. This estimation is formalized as a minimization problem using an information theoretic framework of Rate Distortion theory. We further introduce conditions of the majority to derive an objective function which factorizes the property of the minority and dependence to the structure of the majority. The proposed method shows improvements from conventional approaches in artificial data and a promising result in document retrieval problem.

We proposed a selection scheme called sample-based crowding, which is aimed to improve the performance of genetic algorithms for multimodal optimization in ill-scaled and locally multimodal domains. These domains can be problematic for conventional approaches, but are commonly found in real-world optimization problems. The principle of crowding is to apply a tournament selection to a parent-child pair with a high similarity. In the sample-based crowding, we determine such pairs based on a statistical comparison of the fitness values, which are sampled from the region between the pairs. Further, we take into account the ranks of the parents among the sampled values in the selection process, to determine their indispensability. These measurements are scale-invariant, which enables the proposed method to search a domain without presuming the distance between the optima or the scaling and the correlation of the variables. The proposed approach is evaluated in two benchmark problems with an ill-scaled and a locally multimodal landscape. The proposed method has a substantial advantage in terms of comprehensiveness compared to the conventional approaches, despite the additional cost of evaluations.

We propose a selection scheme called Fitness-based Neighbor Selection (FNS) for multimodal optimization. The FNS is aimed for ill-scaled and locally multimodal domain, both found in real-world numerical optimization problem.In FNS, selection is applied to parent-child pair that most likely belong to the same attractor. We determine such pair with statistical comparison of the fitness values sampled from region between the pairs, instead of conventional Euclidean distance. In addition, the ranks of a parent among sampled values are used to determine if the parent is replaceable. These measurements makes the algorithm scale-invariant thus robust in ill-scaled domain.

In this paper, we propose a GA model called Adaptive Isolation Model(AIM), for multimodal optimization. It uses a data clustering algorithm to detect clusters in GA population, which identifies the attractors in the fitness landscape. Then, subpopulations which makes-up the clusters are isolated and optimized independently. Meanwhile, the region of the isolated subpopulations in the original landscape are suppressed. The isolation increases comprehensiveness, i.e., the probability of finding weaker attractors, and the overall efficiency of multimodal search. The advantage of the AIM is that it does not require distance between the optima as a presumed parameter, as it is estimated from the variance/covariance matrix of the subpopulation.Further, AIM's behavior and efficiency is equivalent to basic GA in unimodal landscape, in terms of number of evaluation. Therefore, it is applied recursively to all subpopulations until they converge to a suboptima. This makes AIM suitable for locally-multimodal landscapes, which have closely located attractors that are difficult to distinguish in the initial run.The performance of AIM is evaluated in several benchmark problems and compared to iterated hill-climbing methods.

This paper proposes a method to capture the dynamics of gene expression data using S-system formalism and construct genetic network models. The proposed method exploits the probabilistic heuristic search and divide-and-conquer approach to generate candidate network structures. In evaluating the network structure, we attempt a primitive integration of other knowledge to the statistical criterion. The robustness analysis uses Z-score to identify significant parameters from results of stochastic search. We evaluated the proposed method on artificial generated data and E.coli mRNA expression data.

Constructing genetic network model from microarray data is an important approach to understanding the functions of the genes. Proposed in this paper is the use of pair-wise correlation analysis to capture regulation and co-regulation among genes. It considers pair-wise p-metrics correlation between the expression of the genes and also the change in expression of the genes. The method is used alongside meta heuristic approach to construct gene regulatory networks of difference and differential equation model from microarray data. The evolutionary algorithms are used to find the structure of the model with highest criteria. Using the result of the analysis improves the performance of the meta heuristics and allows us to extract relations from gene expression of E. coli and S. cerevisiae.

This paper proposes an ant algorithm implemented with stack count for the purpose of designing suffix representations of tree structures. The algorithm is applied to the problem of reconstructing an evolutionary tree from nucleotide sequences. The algorithm shows compatible results in simulated experiment and alignment of protein sequences from 15 species against the existing algorithms.

We present an evolutionary modeling method for modeling genetic regulatory networks. The method features a hybrid algorithm of genetic programming with statistical analysis to derive systems of differential equations. Genetic programming and the least mean squares method were combined to identify a concise form of regulation between the variables from a given set of time series. Results of multiple runs were statistically analyzed to indicate the term with robust and significant influence. Our approach was evaluated in artificial data and real world data.

Presents an application of genetic algorithms (GAs) to the gene network inference problem; this is one of the active topics in recent bioinformatics. The objective is to predict a regulating network structure of the interacting genes from the observed outcome, i.e. expression pattern. The task consists of modeling the rules of regulation and inferring the network structure from the observed data. The GA is applied to training the model with observed data in order to predict the regulatory pathways, represented as an influence matrix. We have implemented a reverse engineering method based on GAs in a quantitative and linear biological framework. The merit of this approach is that it can be applied with a small amount of data, it can optimize large numbers of parameters simultaneously and it can be applied to nonlinear models. The GA implementation includes multi-stage evolution and matrix chromosomes. This method has been applied to both simulated and experimentally observed gene expression patterns. In this research, we used the knowledge of designing an electric circuit by a GA.

This paper proposes a system of evolving analog circuits based on a variable length chromosome. Methods featured are the chromosome of a component list, the multi-stage evolution, and the pressure on the circuit size. A set of experiments are described to confirm the system's robustness, the scalability of a circuit, and the efficiency of time and the memory consumption. The first experiment shows the robustness supplied by the evolutionary method. The second one compares several types of chromosome implementation schemes. We also provide experiments to evaluate the multi-stage and scaling methods.