Machine Learning for User Modeling

At first blush, user modeling appears to be a prime candidate for straightforward application of standard machine learning techniques. Observations of the user's behavior can provide training examples that a machine learning system can use to form a model designed to predict future actions. However, user modeling poses a number of challenges for machine learning that have hindered its application in user modeling, including: the need for large data sets; the need for labeled data; concept drift; and computational complexity. This paper examines each of these issues and reviews approaches to resolving them.  

一种基于混合模型的用户兴趣漂移方法

针对个性化服务的系统中，如何将新发现的用户兴趣和原有兴趣合并为用户的新兴趣的问题，提出了一种基于概念相关性的用户兴趣漂移方法。采用混合模型，将用户兴趣分为长期兴趣和短期兴趣，对短期兴趣采用滑动窗口处理更新，对长期兴趣采用基于概念相关的渐进遗忘方法，实验表明，该方法不仅能够较为准确地跟踪用户的兴趣变化，而且能够预测用户的兴趣，具有较好的效率。  

Tracking Context Changes through Meta-Learning

The article deals with the problem of learning incrementally (on-line) in domains where the target concepts are context-dependent, so that changes in context can produce more or less radical changes in the associated concepts. In particular, we concentrate on a class of learning tasks where the domain provides explicit clues as to the current context (e.g., attributes with characteristic values). A general two-level learning model is presented that effectively adjusts to changing contexts by trying to detect (via meta-learning) contextual clues and using this information to focus the learning process. Context learning and detection occur during regular on-line learning, without separate training phases for context recognition. Two operational systems based on this model are presented that differ in the underlying learning algorithm and in the way they use contextual information: METAL(B) combines meta-learning with a Bayesian classifier, while METAL(IB) is based on an instance-based learning algorithm. Experiments with synthetic domains as well as a number of real-world problems show that the algorithms are robust in a variety of dimensions, and that meta-learning can produce substantial increases in accuracy over simple object-level learning in situations with changing contexts.  

Extracting Hidden Context

Concept drift due to hidden changes in context complicates learning in many domains including financial prediction, medical diagnosis, and communication network performance. Existing machine learning approaches to this problem use an incremental learning, on-line paradigm. Batch, off-line learners tend to be ineffective in domains with hidden changes in context as they assume that the training set is homogeneous. An off-line, meta-learning approach for the identification of hidden context is presented. The new approach uses an existing batch learner and the process of contextual clustering to identify stable hidden contexts and the associated context specific, locally stable concepts. The approach is broadly applicable to the extraction of context reflected in time and spatial attributes. Several algorithms for the approach are presented and evaluated. A successful application of the approach to a complex flight simulator control task is also presented.  

基于多分类器的数据流中的概念漂移挖掘

数据流中概念漂移的检测是当前数据挖掘领域的重要研究分支, 近年来得到了广泛的关注. 本文提出了一种称为 M_ID4 的数据流挖掘算法. 它是在大容量数据流挖掘中, 通过尽量少的训练样本来实现概念漂移检测的快速方法. 利用多分类器综合技术, M_ID4 实现了数据流中概念漂移的增量式检测和挖掘. 实验结果表明, M_ID4 算法在处理数据流的概念漂移上表现出比已有同类算法更高的精确度和适应性.  

基于子空间集成的概念漂移数据流分类算法

具有概念漂移的复杂结构数据流分类问题已成为数据挖掘领域研究的热点之一。提出了一种新颖的子空间分类算法，并采用层次结构将其构成集成分类器用于解决带概念漂移的数据流的分类问题。在将数据流划分为数据块后，在每个数据块上利用子空间分类算法建立若干个底层分类器，然后由这几个底层分类器组成集成分类模型的基分类器。同时，引入数理统计中的参数估计方法检测概念漂移，动态调整模型。实验结果表明：该子空间集成算法不但能够提高分类模型对复杂类别结构数据流的分类精度，而且还能够快速适应概念漂移的情况。  

Tracking Drifting Concepts By Minimizing Disagreements

In this paper we consider the problem of tracking a subset of a domain (called thetarget) which changes gradually over time. A single (unknown) probability distribution over the domain is used to generate random examples for the learning algorithm and measure the speed at which the target changes. Clearly, the more rapidly the target moves, the harder it is for the algorithm to maintain a good approximation of the target. Therefore we evaluate algorithms based on how much movement of the target can be tolerated between examples while predicting with accuracy . Furthermore, the complexity of the classH of possible targets, as measured byd, its VC-dimension, also effects the difficulty of tracking the target concept. We show that if the problem of minimizing the number of disagreements with a sample from among concepts in a classH can be approximated to within a factork, then there is a simple tracking algorithm forH which can achieve a probability of making a mistake if the target movement rate is at most a constant times ²/(k(d +k) ln 1/), whered is the Vapnik-Chervonenkis dimension ofH. Also, we show that ifH is properly PAC-learnable, then there is an efficient (randomized) algorithm that with high probability approximately minimizes disagreements to within a factor of 7d + 1, yielding an efficient tracking algorithm forH which tolerates drift rates up to a constant times ²/(d ² ln 1/). In addition, we prove complementary results for the classes of halfspaces and axisaligned hyperrectangles showing that the maximum rate of drift that any algorithm (even with unlimited computational power) can tolerate is a constant times ²/d.