An incremental approach to genetic-algorithms-based classification.

Incremental learning has been widely addressed in the machine learning literature to cope with learning tasks where the learning environment is ever changing or training samples become available over time. However, most research work explores incremental learning with statistical algorithms or neural networks, rather than evolutionary algorithms. The work in this paper employs genetic algorithms (GAs) as basic learning algorithms for incremental learning within one or more classifier agents in a multiagent environment. Four new approaches with different initialization schemes are proposed. They keep the old solutions and use an "integration" operation to integrate them with new elements to accommodate new attributes, while biased mutation and crossover operations are adopted to further evolve a reinforced solution. The simulation results on benchmark classification data sets show that the proposed approaches can deal with the arrival of new input attributes and integrate them with the original input space. It is also shown that the proposed approaches can be successfully used for incremental learning and improve classification rates as compared to the retraining GA. Possible applications for continuous incremental training and feature selection are also discussed.     

A lattice-free concept lattice update algorithm

Upon a change of input data, one usually wants an update of output computed from the data rather than recomputing the whole output over again. In Formal Concept Analysis, update of concept lattice of input data when introducing new objects to the data can be done by any of the so-called incremental algorithms for computing concept lattice. The algorithms use and update the lattice while introducing new objects to input data one by one. The present concept lattice of input data without the new objects is thus required by the computation. However, the lattice can be large and may not fit into memory. In this paper, we propose an efficient algorithm for updating the lattice from the present and new objects only, not requiring the possibly large concept lattice of present objects. The algorithm results as a modification of the Close-by-One algorithm for computing the set of all formal concepts, or its modifications like Fast Close-by-One, Parallel Close-by-One or Parallel Fast Close-by-One, to compute new and modified formal concepts and the changes of the lattice order relation only. The algorithm can be used not only for updating the lattice when new objects are introduced but also when some existing objects are removed from the input data or attributes of the objects are changed. We describe the algorithm, discuss efficiency issues and present an experimental evaluation of its performance and a comparison with the AddIntent incremental algorithm for computing concept lattice.     

Incremental computation of time-varying query expressions

We present and analyze algorithms for the incremental computation of time-varying queries in which selection predicates refer to the state of a clock. Such queries occur naturally in many situations where temporal data are processed. Incremental techniques for query computation have proven to be more efficient than other techniques in many situations. However, all existing incremental techniques for query computation assume that old query results remain valid if no intermediate changes are made to the underlying database. Unfortunately, this assumption does not hold for time-varying queries whose results may change just because time passes. In order to solve this problem, we introduce the notion of a superview which contains all current tuples that will eventually satisfy the selection predicate of a time-varying selection. Based on the notion of superview, we develop efficient algorithms for the incremental computation of time-varying selections. Our algorithms, combined with existing incremental algorithms, allow complex time-varying queries to benefit from the proven efficiency of incremental techniques. It is important to notice that without our algorithms, the existing algorithms for incremental computation would be useless for any time-varying query expression     

基于属性的概念格快速渐进式构造算法

提出了一种新的基于属性的概念格快速渐进式构造算法,通过不断地渐增属性来构造概念格。以往的渐进式算法嘟是基于对象的,当数据库属性数目发生变化时,需要重新构造概念格。该算法不但解决了这个问题,而且提供了一种渐进式构造概念格的新方法和思路。给出了该算法的实例,用来说明形式背景在新添加属性后概念格的更新过程。实例与实验表明基于属性的概念格快速渐进式构造算法是快捷有效的。     

信息系统属性增量约简算法的设计与实现

信息系统是一种重要的知识表达形式,对它的增量算法研究主要集中在对象的动态增加上。论文分析了信息系统核和约简在增加属性后的变化规律,设计并实现了信息系统的属性增量约简算法。实验表明,该算法能够有效利用原信息系统的知识,快速、准确地计算出新信息系统的核和约简。     

An efficient approach for the maintenance of user behaviours

Mining sequential patterns is to discover sequential purchasing behaviours for most of the customers from a large number of customer transactions. The strategy of mining sequential patterns focuses on discovering frequent sequences. A frequent sequence is an ordered list of the itemsets purchased by a sufficient number of customers. The previous approaches for mining sequential patterns need to repeatedly scan the database so that they take a large amount of computation time to find frequent sequences. The customer transactions will grow rapidly in a short time, and some of the customer transactions may be antiquated. Consequently, the frequent sequences may be changed due to the insertion of new customer transactions or the deletion of old customer transactions from the database. It may require rediscovering all the patterns by scanning the entire updated customer transaction database. In this paper, we propose an incremental updating technique to maintain the discovered sequential patterns when transactions are inserted into or deleted from the database. Our approach partitions the database into some segments and scans the database segment by segment. For each segment scan, our approach prunes those sequences that cannot be frequent sequences any more to accelerate the finding process of the frequent sequences. Therefore, the number of database scans can be significantly reduced by our approach. The experimental results show that our algorithms are more efficient than other algorithms for the maintenance of mining sequential patterns.     

Incremental Learning with Respect to New Incoming Input Attributes

Neural networks are generally exposed to a dynamic environment where the training patterns or the input attributes (features) will likely be introduced into the current domain incrementally. This Letter considers the situation where a new set of input attributes must be considered and added into the existing neural network. The conventional method is to discard the existing network and redesign one from scratch. This approach wastes the old knowledge and the previous effort. In order to reduce computational time, improve generalization accuracy, and enhance intelligence of the learned models, we present ILIA algorithms (namely ILIA1, ILIA2, ILIA3, ILIA4 and ILIA5) capable of Incremental Learning in terms of Input Attributes. Using the ILIA algorithms, when new input attributes are introduced into the original problem, the existing neural network can be retained and a new sub-network is constructed and trained incrementally. The new sub-network and the old one are merged later to form a new network for the changed problem. In addition, ILIA algorithms have the ability to decide whether the new incoming input attributes are relevant to the output and consistent with the existing input attributes or not and suggest to accept or reject them. Experimental results show that the ILIA algorithms are efficient and effective both for the classification and regression problems.     

Multi-view Incremental Discriminant Analysis

In recent years, the use of multi-view data has attracted much attention resulting in many multi-view batch learning algorithms. However, these algorithms prove expensive in terms of training time and memory when used on the incremental data. In this paper, we propose Multi-view Incremental Discriminant Analysis (MvIDA), which updates the trained model to incorporate new data samples. MvIDA requires only the old model and newly added data to update the model. Depending on the nature of the increments, MvIDA is presented as two cases, sequential MvIDA and chunk MvIDA. We have compared the proposed method against the batch Multi-view Discriminant Analysis (MvDA) for its discriminability, order independence, the effect of the number of views, training time, and memory requirements. We have also compared our method with single-view Incremental Linear Discriminant Analysis (ILDA) for accuracy and training time. The experiments are conducted on four datasets with a wide range of dimensions per view. The results show that through order independence and faster construction of the optimal discriminant subspace, MvIDA addresses the issues faced by the batch multi-view algorithms in the incremental setting.     

DEMON: mining and monitoring evolving data

Data mining algorithms have been the focus of much research. In practice, the input data to a data mining process resides in a large data warehouse whose data is kept up-to-date through periodic or occasional addition and deletion of blocks of data. Most data mining algorithms have either assumed that the input data is static, or have been designed for arbitrary insertions and deletions of data records. We consider a dynamic environment that evolves through systematic addition or deletion of blocks of data. We introduce a new dimension, called the data span dimension, which allows user-defined selections of a temporal subset of the database. Taking this new degree of freedom into account, we describe efficient model maintenance algorithms for frequent item sets and clusters. We then describe a generic algorithm that takes any traditional incremental model maintenance algorithm and transforms it into an algorithm that allows restrictions on the data span dimension. We also develop an algorithm for automatically discovering a specific class of interesting block selection sequences. In a detailed experimental study, we examine the validity and performance of our ideas on synthetic and real datasets     

Incremental learning methods with retrieving of interfered patterns

There are many cases when a neural-network-based system must memorize some new patterns incrementally. However, if the network learns the new patterns only by referring to them, it probably forgets old memorized patterns, since parameters in the network usually correlate not only to the old memories but also to the new patterns. A certain way to avoid the loss of memories is to learn the new patterns with all memorized patterns. It needs, however, a large computational power. To solve this problem, we propose incremental learning methods with retrieval of interfered patterns (ILRI). In these methods, the system employs a modified version of a resource allocating network (RAN) which is one variation of a generalized radial basis function (GRBF). In ILRI, the RAN learns new patterns with a relearning of a few number of retrieved past patterns that are interfered with the incremental learning. We construct ILRI in two steps. In the first step, we construct a system which searches the interfered patterns from past input patterns stored in a database. In the second step, we improve the first system in such a way that the system does not need the database. In this case, the system regenerates the input patterns approximately in a random manner. The simulation results show that these two systems have almost the same ability, and the generalization ability is higher than other similar systems using neural networks and k-nearest neighbors.     

基于改进区分矩阵的决策表增量式属性约简

针对属性在不断增加的决策表,为了快速准确地计算出属性约简,提出一种增量式属性约简算法。以正域为约简的标准,利用贪心算法思想,以属性区分能力为选择标准,逐渐构造近似的属性约简,从中删减掉不必要的属性,最终得到属性约简。经复杂度分析与实验数据测试,证明该算法的复杂度低并且约简结果准确。     

A Group Incremental Reduction Algorithm with Varying Data Values

Attribute reduction based on rough set theory has attracted much attention recently. In real‐life applications, many decision tables may vary dynamically with time, e.g., the variation of attributes, objects, and attribute values. The reduction of decision tables may change on the alteration of attribute values. The paper focuses on dynamic maintenance of attribute reduction when varying data values of multiple objects. Incremental mechanisms for knowledge granularity are proposed first, which aims to update attribute reduction effectively. Then, a group incremental reduction algorithm with varying data values is developed. When attribute values of multiple objects have been replaced by new ones in decision table, the proposed incremental algorithm can find the new reduct in a much shorter time. The time complexity analysis and experiments on different data sets from UCI have validated that the proposed incremental algorithms are efficient and effective to update the reduction with the variation of attribute values.     

多准则分类问题中近似集的增量更新方法

在优势关系粗糙集方法(DRSA)的框架下,优势关系可用于处理带有序关系属性(准则)的数据,并且已经被广泛用于处理多准则决策问题。然而在实际应用中,当属性集和对象集发生变化时,信息系统会随之不断更新。在这种动态环境下,DRSA中用于属性约简、规则提取以及决策制定的近似集需要得到相应的更新。针对对象集发生变化时(增加或删除一个对象)的多准则分类问题,采用增量方法来更新近似集并提出两种相应的更新算法DRSA1和DRSA2。同时,对不同情况下的更新原则进行了讨论并给出了相关的理论结果与详细的证明。最后给出算例,并在UCI数据集上进行大量的实验,与非增量的方法(传统的DRSA)进行对比,结果充分体现了所提增量方法的有效性与可扩展性。     

Incremental feature selection based on rough set in dynamic incomplete data

Feature selection plays a vital role in many areas of pattern recognition and data mining. The effective computation of feature selection is important for improving the classification performance. In rough set theory, many feature selection algorithms have been proposed to process static incomplete data. However, feature values in an incomplete data set may vary dynamically in real-world applications. For such dynamic incomplete data, a classic (non-incremental) approach of feature selection is usually computationally time-consuming. To overcome this disadvantage, we propose an incremental approach for feature selection, which can accelerate the feature selection process in dynamic incomplete data. We firstly employ an incremental manner to compute the new positive region when feature values with respect to an object set vary dynamically. Based on the calculated positive region, two efficient incremental feature selection algorithms are developed respectively for single object and multiple objects with varying feature values. Then we conduct a series of experiments with 12 UCI real data sets to evaluate the efficiency and effectiveness of our proposed algorithms. The experimental results show that the proposed algorithms compare favorably with that of applying the existing non-incremental methods.     

Attributed graph mining in the presence of automorphism

Attributed directed graphs are directed graphs in which nodes are associated with sets of attributes. Many data from the real world can be naturally represented by this type of structure, but few algorithms are able to directly handle these complex graphs. Mining attributed graphs is a difficult task because it requires combining the exploration of the graph structure with the identification of frequent itemsets. In addition, due to the combinatorics on itemsets, subgraph isomorphisms (which have a significant impact on performances) are much more numerous than in labeled graphs. In this paper, we present a new data mining method that can extract frequent patterns from one or more directed attributed graphs. We show how to reduce the combinatorial explosion induced by subgraph isomorphisms thanks to an appropriate processing of automorphic patterns.     

Ordered incremental training with genetic algorithms

Incremental training has been used for genetic algorithm (GA)‐based classifiers in a dynamic environment where training samples or new attributes/classes become available over time. In this article, ordered incremental genetic algorithms (OIGAs) are proposed to address the incremental training of input attributes for classifiers. Rather than learning input attributes in batch as with normal GAs, OIGAs learn input attributes one after another. The resulting classification rule sets are also evolved incrementally to accommodate the new attributes. Furthermore, attributes are arranged in different orders by evaluating their individual discriminating ability. By experimenting with different attribute orders, different approaches of OIGAs are evaluated using four benchmark classification data sets. Their performance is also compared with normal GAs. The simulation results show that OIGAs can achieve generally better performance than normal GAs. The order of attributes does have an effect on the final classifier performance where OIGA training with a descending order of attributes performs the best. © 2004 Wiley Periodicals, Inc. Int J Int Syst 19: 1239–1256, 2004.     

一种基于改进差别矩阵的核增量式更新算法

提出一种基于改进差别矩阵的核增量式更新算法,主要考虑对象动态增加情况下核的更新问题．该算法在更新差别矩阵时仅须插入某一行及某一列,或删除某一行并修改相应的列,因而可有效地提高核的更新效率．理论分析和实验结果表明,该算法是有效可行的．     

An incremental decision tree algorithm based on rough sets and its application in intrusion detection

As we know, learning in real world is interactive, incremental and dynamical in multiple dimensions, where new data could be appeared at anytime from anywhere and of any type. Therefore, incremental learning is of more and more importance in real world data mining scenarios. Decision trees, due to their characteristics, have been widely used for incremental learning. In this paper, we propose a novel incremental decision tree algorithm based on rough set theory. To improve the computation efficiency of our algorithm, when a new instance arrives, according to the given decision tree adaptation strategies, the algorithm will only modify some existing leaf node in the currently active decision tree or add a new leaf node to the tree, which can avoid the high time complexity of the traditional incremental methods for rebuilding decision trees too many times. Moreover, the rough set based attribute reduction method is used to filter out the redundant attributes from the original set of attributes. And we adopt the two basic notions of rough sets: significance of attributes and dependency of attributes, as the heuristic information for the selection of splitting attributes. Finally, we apply the proposed algorithm to intrusion detection. The experimental results demonstrate that our algorithm can provide competitive solutions to incremental learning.     

A robust incremental learning method for non-stationary environments

Recent machine learning challenges require the capability of learning in non-stationary environments. These challenges imply the development of new algorithms that are able to deal with changes in the underlying problem to be learnt. These changes can be gradual or trend changes, abrupt changes and recurring contexts. As the dynamics of the changes can be very different, existing machine learning algorithms exhibit difficulties to cope with them. Several methods using, for instance, ensembles or variable length windowing have been proposed to approach this task.In this work we propose a new method, for single-layer neural networks, that is based on the introduction of a forgetting function in an incremental online learning algorithm. This forgetting function gives a monotonically increasing importance to new data. Due to the combination of incremental learning and increasing importance assignment the network forgets rapidly in the presence of changes while maintaining a stable behavior when the context is stationary.The performance of the method has been tested over several regression and classification problems and its results compared with those of previous works. The proposed algorithm has demonstrated high adaptation to changes while maintaining a low consumption of computational resources.