=Paper=
{{Paper
|id=Vol-1088/paper2
|storemode=property
|title=Learning Model Rules From High-Speed Data Streams
|pdfUrl=https://ceur-ws.org/Vol-1088/paper2.pdf
|volume=Vol-1088
|dblpUrl=https://dblp.org/rec/conf/ijcai/AlmeidaFG13
}}
==Learning Model Rules From High-Speed Data Streams==
https://ceur-ws.org/Vol-1088/paper2.pdf
Learning Model Rules from High-Speed Data Streams
Ezilda Almeida and Carlos Ferreira and João Gama
LIAAD - INESC Porto L.A., Portugal
Abstract minimizes the mean square error of the target attribute com-
puted from the set of examples covered by rule. This func-
Decision rules are one of the most expressive lan- tion might be either a constant, the mean of the target at-
guages for machine learning. In this paper we tribute, or a linear combination of the attributes. Each rule
present Adaptive Model Rules (AMRules), the first is equipped with an online change detector. It monitors the
streaming rule learning algorithm for regression mean square error using the Page-Hinkley test, providing in-
problems. In AMRules the antecedent of a rule is formation about the dynamics of the process generating data.
a conjunction of conditions on the attribute values, The paper is organized has follows. The next Section
and the consequent is a linear combination of at- presents the related work in learning regression trees and
tribute values. Each rule in AMRules uses a Page- rules from data focusing on streaming algorithms. Sec-
Hinkley test to detect changes in the process gener- tion 3 describe in detail the AMRules algorithm. Section 4
ating data and react to changes by pruning the rule presents the experimental evaluation using stationary and
set. In the experimental section we report the re- time-evolving streams. AMRules is compared against other
sults of AMRules on benchmark regression prob- regression systems. Last Section presents the lessons learned.
lems, and compare the performance of our algo-
rithm with other streaming regression algorithms. 2 Related Work
In this section we analyze the related work in two dimensions.
Keywords: Data Streams, Regression, Rule Learning, One dimension is related to regression algorithms, the other
Change Detection dimension is related to incremental learning of regression al-
gorithms.
1 Introduction In regression domains, [14] presented the system M5. It
builds multivariate trees using linear models at the leaves. In
Regression analysis is a technique for estimating a functional the pruning phase for each leaf a linear model is built. Later,
relationship between a dependent variable and a set of in- [5] have presented M50 a rational reconstruction of Quinlan’s
dependent variables. It has been widely studied in statistics, M5 algorithm. M50 first constructs a regression tree by re-
machine learning and data mining. Predicting numeric val- cursively splitting the instance space using tests on single at-
ues usually involves complicated regression formulae. Model tributes that maximally reduce variance in the target variable.
trees [14] and regression rules [15] are the most powerful data After the tree has been grown, a linear multiple regression
mining models. Trees and rules do automatic feature selec- model is built for every inner node, using the data associated
tion, being robust to outliers and irrelevant features; exhibit with that node and all the attributes that participate in tests
high degree of interpretability; and structural invariance to in the subtree rooted at that node. Then the linear regression
monotonic transformation of the independent variables. One models are simplified by dropping attributes if this results in
important aspect of rules is modularity: each rule can be in- a lower expected error on future data (more specifically, if the
terpreted per si [6]. decrease in the number of parameters outweighs the increase
In the data stream computational model [7] examples in the observed training error). After this has been done, ev-
are generated sequentially from time evolving distributions. ery subtree is considered for pruning. Pruning occurs if the
Learning from data streams require incremental learning, us- estimated error for the linear model at the root of a subtree
ing limited computational resources, and the ability to adapt is smaller or equal to the expected error for the subtree. Af-
to changes in the process generating data. In this paper we ter pruning terminates, M50 applies a smoothing process that
present Adaptive Model Rules, the first one-pass algorithm combines the model at a leaf with the models on the path to
for learning regression rule sets from time-evolving streams. the root to form the final model that is placed at the leaf.
AMRules can learn ordered and unordered rules. The an- Cubist [15] is a rule based model that is an extension of
tecedent of a rule is a set of literals (conditions based on the Quinlan’s M5 model tree. A tree is grown where the termi-
attribute values). The consequent of a rule is a function that nal leaves contain linear regression models. These models are
based on the predictors used in previous splits. Also, there are concept change. Even though unexpected observations should
intermediate linear models at each step of the tree. A predic- be removed only in the former but not in the latter case.
tion is made using the linear regression model at the terminal
node of the tree, but is smoothed by taking into account the Algorithm 1: AMRules Algorithm
prediction from the linear model in the previous node of the
tree (which also occurs recursively up the tree). The tree is Input:
S: Stream of examples
reduced to a set of rules, which initially are paths from the ordered-set: boolean flag
top of the tree to the bottom. Rules are eliminated via pruning Nmin : Minimum number of examples
and/or combined for simplification. λ: Constant to solve ties
α: the magnitude of changes that are allowed
2.1 Streaming Regression Algorithms j: rule index
Result: RS Set of Decision Rules
Many methods can be found in the literature for solving clas- begin
sification tasks on streams, but only a few exist for regres- Let RS ← {}
sion tasks. To the best of our knowledge, we note only two Let defaultRule {} → (L ← N U LL)
foreach example (xi , yi ) do
papers for online learning of regression and model trees. In foreach Rule r ∈ RSj do
the algorithm of [13] for incremental learning of linear model if r covers the example then
trees the splitting decision is formulated as hypothesis test- Let ŷi be the prediction of the rule r,
ing. The split least likely to occur under the null hypothesis computed using Lr
of non-splitting is considered the best one. The linear mod- Compute error =(ŷi − yi )2
els are computed using the RLS (Recursive Least Square) al- Call PHTest(error, α, λ)
gorithm that has a complexity, which is quadratic in the di- if Change is detected then
mensionality of the problem. This complexity is then multi- Remove the rule
plied with a user-defined number of possible splits per nu- else
Update sufficient statistics of r
merical attribute for which a separate pair of linear models is Update Perceptron of r
updated with each training example and evaluated. The Fast if Number of examples in Lr ≥ Nmin
Incremental Model Tree (FIMT) proposed in [10], is an in- then
cremental algorithm for any-time model trees learning from r ← ExpandRule(r)
evolving data streams with drift detection. It is based on the
Hoeffding tree algorithm, but implements a different splitting if ordered-set then
BREAK
criterion, using a standard deviation reduction (SDR) based
measure more appropriate to regression problems. The FIMT if none of the rules in RS triggers then
algorithm is able to incrementally induce model trees by pro- Update sufficient statistics of the default rule
cessing each example only once, in the order of their arrival. Update Perceptron of the default rule
Splitting decisions are made using only a small sample of the if Number of examples in L ≥ Nmin then
data stream observed at each node, following the idea of Ho- RS ← RS ∪ ExpandRule(def aultRule)
effding trees. Another data streaming issue addressed in [10]
is the problem of concept drift. Data streaming models capa-
ble of dealing with concept drift face two main challenges:
how to detect when concept drift has occurred and how to
adapt to the change. Change detection in the FIMT is carried 3 The AMRules Algorithm
out using the Page-Hinkley change detection test [11]. Adap- The problem of learning model rules from data streams raises
tation in FIMT involves growing an alternate subtree from the several issues. First, the dataset is no longer finite and avail-
node in which change was detected. able prior to learning, it is impossible to store all data in
IBLStreams (Instance Based Learner on Streams) is an ex- memory and learn from them as a whole. Second, multiple
tension of MOA that consists in an instance-based learning sequencial scans over the training data are not allowed. An
algorithm for classification and regression problems on data algorithm must therefore collect the relevant information at
streams by [1]; IBLStreams optimizes the composition and the speed it arrives and incrementally decide about splitting
size of the case base autonomously. On arrival of a new ex- decisions. Third the training dataset may consist of data from
ample (x0 , y0 ), this example is first added to the case base. different distributions. In this section we present an incremen-
Moreover, it is checked whether other examples might be re- tal algorithm for learning model rules to address these issues,
moved, either since they have become redundant or since they named Adaptive Model Rules from High-Speed Data Streams
are outliers. To this end, a set C of examples within a neigh- (AMRules).The pseudo code of the algorithm is given in Al-
borhood of x0 are considered as candidates. This neighbor- gorithm 1.
hood if given by the kc nearest neighbors of x0 , determined The algorithm begins with an empty rule set (RS), and a
according a distance measure ∆, and the candidate set C con- default rule {} → L, where L is initialized to NULL. L is a
sists of the examples within that neighborhood. The most re- data structure used to store the sufficient statistics required to
cent examples are excluded from removal due to the difficulty expand a rule and for prediction. Every time a new training
to distinguish potentially noisy data from the beginning of a example is available the algorithm proceeds with checking
v
Algorithm 2: Expandrule: Expanding one Rule
u
u1 X N N
1 X 2
Input: =t ( yi2 − ( yi) )
N i=1 N i=1
r: One Rule
τ : Constant to solve ties To make the actual decision regarding a split, the SDR
δ : Confidence measured for the best two potential splits are compared, by
Result: r0 : Expanded Rule
dividing the second-best value by the best one to generate
begin
Let Xa be the attribute with greater SDR a ratio r in the range 0 to 1. Having a predefined range for
Let Xb be the q
attribute with second greater SDR the values of the random variables, the Hoeffding probability
R2 ln(1/δ) bound () [17] can be used to obtain high confidence intervals
Compute = (Hoeffding bound)
2n for the true average of the sequence of random variables. The
SDR(Xb )
Compute r = SDR(Xa ) (Ratio of the SDR values for the value of is calculated using the formula:
best two splits) r
Compute U pperBound = r + R2 ln (1/δ)
if U pperBound < 1 ∨ < τ then =
Extend r with a new condition based on the best 2n
attribute Xa ≤ vj or Xa > vj The process to expand a rule by adding a new condition
Release sufficient statistics of Lr works as follows. For each attribute Xi , the value of the SDR
r ← r ∪ {Xa ≤ vj orXa > vj } is computed for each attribute value vj . If the upper bound
return r (r̄+ = r̄ + ) of the sample average is below 1 then the true
mean is also below 1. Therefore with confidence 1− the best
attribute over a portion of the data is really the best attribute.
whether for each rule from rule set (RS) the example is cov- In this case, the rule is expanded with condition Xa ≤ vj or
ered by any rule, that is if all the literals are true for the exam- Xa > vj . However, often two splits are extremely similar or
ple. The target values of the examples covered by a rule are even identical, in terms of their SDR values, and despite the
used to update the sufficient statistic of the rule (L). To detect intervals shrinking considerably as more examples are seen,
changes we propose to use the Page-Hinkley (PH) change de- it is still impossible to choose one split over the other. In these
tection test. If a change is detected the rule is removed from cases, a threshold (τ ) on the error is used. If falls below this
the rule set. Otherwise, the rule might be expanded. The ex- threshold and the splitting criterion is still not met, the split is
pansion of the rule is considered only after certain minimum made on the best split with a higher SDR value and the rule
number of examples (Nmin ). The expansion of a rule is ex- is expanded.
plained in Algorithm 2.
3.2 Prediction Strategies
The set of rules is learned in parallel, as described in Al-
gorithm 1. We consider two cases: learning ordered or un- The set of rules learned by AMRules can be ordered or
ordered set of rules. In the former case, every example up- unordered. They employ different prediction strategies to
dates statistics of the first rule that covers it. In the latter ev- achieve optimal prediction. In the former, only the first rule
ery example updates statistics of all the rules that covers it. that cover an example is used to predict the target example.
If an example is not covered by any rule, the default rule is In the latter, all rules covering the example are used for pre-
updated. diction and the final prediction is decided by using weighted
vote.
3.1 Expansion of a Rule Each rule in AMrules implements 3 prediction strategies: i)
the mean of the target attribute computed from the examples
Before discussing how rules are expanded, we will first covered by the rule; ii) a linear combination of the indepen-
discuss the evaluation measure used in the attribute selection dent attributes; iii) an adaptive strategy, that chooses between
process. [10] describe a standard deviation reduction measure the first two strategies, the one with lower MSE in the previ-
(SDR) for determining the merit of a given split. It can be ous examples.
efficiently computed in an incremental way. Given a leaf Each rule in AMRules contains a linear model, trained us-
where a sample of the dataset S of size N has been observed, ing an incremental gradient descent method, from the ex-
a hypothetical binary split hA over attribute A would divide amples covered by the rule. Initially, the weights are set to
the examples in S in two disjoint subsets SL and SR , with small random numbers in the range -1 to 1. When a new
sizes NL and NR respectively. The formula for SDR measure example arrives, the output is computed using the current
of the split hA is given below: weights. Each weight is then updated using the Delta rule:
wi ← wi + η(ŷ − y)xi , where ŷ is the output, y the real value
and η is the learning rate.
NL NR
SDR(hA ) = sd(S) − sd(SL ) − sd(SR ) 3.3 Change Detection
N N
v The AMRules uses the Page-Hinkley (PH) test [12] to moni-
u
u1 X N tor the error and signals a drift when a significant increase of
sd(S) = t ( (yi − ȳ)2 ) = this variable is observed. The PH test is a sequential analysis
N i=1 technique typically used for monitoring change detection in
signal processing. The PH test is designed to detect a change error is estimated from the same test sets. In scenarios with
in the average of a Gaussian signal [11]. This test considers concept drift, we use the prequential (predictive sequential)
a cumulative variable mT , defined as the accumulated differ- error estimate [8]. This evaluation method evaluates a model
ence between the observed error and the mean of the error till sequentially. When an example is available, the current re-
the current moment: gression model makes a prediction and the loss is computed.
T After the prediction the regression model is updated with that
mT =
X
(et − ēT − α) example.
t=1
Datasets
t
The experimental datasets include both artificial and real data,
P
where e¯T = 1/T et and α corresponds to the magnitude
t=1 as well sets with continuous attributes. We use ten regression
of changes that are allowed. datasets from the UCI Machine Learning Repository [3] and
The minimum value of this variable is also computed: other sources. The datasets used in our experimental work
MT = min(mt , t = 1 . . . T ). As a final step, the test moni- are:
tors the difference between MT and mT : P HT = mT − MT . 2dplanes this is an artificial data set described in [4]. Air-
When this difference is greater than a given threshold (λ) we lerons this data set addresses a control problem, namely fly-
signal a change in the distribution. The threshold λ depends ing a F16 aircraft. Puma8NH and Puma32H is a family of
on the admissible false alarm rate. Increasing λ will entail datasets synthetically generated from a realistic simulation of
fewer false alarms, but might miss or delay change detection. the dynamics of a Unimation Puma 560 robot arm. Pol this
is a commercial application described in [18].The data de-
4 Experimental Evaluation scribes a tele communication problem. Elevators this data
The main goal of this experimental evaluation is to study the set is also obtained from the task of controlling a F16 aircraft.
behavior of the proposed algorithm in terms of mean absolut Fried is an artificial data set used in Friedman (1991) and
error (MAE) and root mean squared error (RMSE). We are also described in Breiman (1996,p.139). Bank8FM a fam-
interested in studying the following scenarios: ily of datasets synthetically generated from a simulation of
how bank-customers choose their banks. Kin8nm this dataset
– How to grow the rule set? is concerned with the forward kinematics of an 8 link robot
• Update only the first rule that covers training ex- arm. Airline this dataset using the data from the Data Expo
amples. In this case the rule set is ordered, and the competition (2009). The dataset consists of a large amount of
corresponding prediction strategy uses only the first records, containing flight arrival and departure details for all
rule that covers test examples. the commercial flights within the USA, from October 1987
• Update all the rules that covers training examples. to April 2008. This is a large dataset with nearly 120 mil-
In this case the rule set is unordered, and the cor- lion records (11.5 GB memory size) [10]. Table 1 summarizes
responding prediction strategy uses a weighted sum the number of instances and the number of attributes of each
of all rules that covers test examples. dataset.
– How does AMRules compares against other streaming Table 1. Summary of datasets
algorithms?
– How does AMRules compares against other state-of-the- Datasets # Instances # Attributes Learning rate
2dplanes 40768 11 0.01
art regression algorithms? Airlerons 13750 41 0.01
– How does AMRules learned models evolve in time- Puma8NH 8192 9 0.01
changing streams? Puma32H 8192 32 0.01
Pol 15000 49 0.001
Elevators 8752 19 0.001
4.1 Experimental Setup Fried 40769 11 0.01
All our algorithms were implemented in java using Massive Bank8FM 8192 9 0.01
Kin8nm 8192 9 0.01
Online Analysis (MOA) data stream software suite [2]. For Airline 115Million 11 0.01
all the experiments, we set the input parameters of AMRules
to: Nmin = 200, τ = 0.05 and δ = 0.01. The parameters
for the Page-Hinkley test are λ = 50 and α = 0.005. Table 1
summarizes information about the datasets used and reports 4.2 Experimental Results
the learning rate used in the perceptron learning.
All of the results in the tables 2, 3 and 4 are averaged of In this section, we empirically evaluate the AMRules. The
ten-fold cross-validation [16]. The accuracy is measured us- results are described in four parts. In the first part we compare
ing the following metrics: Mean absolute error (MAE) and the AMRules variants, the second part we compare AMRules
root mean squared error (RMSE) [19]. We used two evalua- against other streaming algorithms and the third part compare
tion methods. When no concept drift is assumed, the evalua- AMRules against other state-of-the-art regression algorithms.
tion method we employ uses the traditional train and test sce- The last part presents the analysis of AMRules behavior in the
nario. All algorithms learn from the same training set and the context of time-evolving data streams.
Comparison between AMRules Variants Table 5. Average results from the evaluation of change detection
over ten experiments.
In this section we focus on two strategies that we found po-
tentially interesting. It is a combination of expanding only Algorithms Delay Size
one rule, the rule that first triggered, with predicting strat- AMRules 1484 56 (nr. Rules)
egy uses only the first rule that covers test examples. Obvi- FIMT 2096 290 (nr. Leaves)
IBLStreams - -
ously, for this approach it is necessary to use ordered rules
(AM Ruleso ). The second setting employs unordered rule
set, where all the covering rules expand and the correspond- Evaluation in Time-Evolving Data streams
ing prediction strategy uses a weighted sum of all rules that In this subsection we first study the evolution of the error
cover test examples (AM Rulesu ). measurements (MAE and RMSE) and evaluate the change de-
Ordered rule sets specializes one rule at a time, and as a tection method. After, we evaluate the streaming algorithms
result it often produces less rules than the unordered strat- on non-stationary streaming real-world problem, we use the
egy. Ordered rules need to consider the previous rules and re- Airline dataset from the DataExpo09 competition.
maining combinations, which might not be easy to interpret To simulate drift we use Fried dataset. The simulations al-
in more complex sets. Unordered rule sets are more modular, low us to control the relevant parameters and to evaluate the
because they can be interpreted alone. drift detection. Figure 1 and Figure 2 depict the MAE and
Table 2 summarize the mean absolute error and the root RMSE curves of the streaming algorithms using the dataset
mean squared error of these variants. Overall, the experimen- Fried. These figures also illustrate the point of drift and the
tal results points out the unordered rule sets are more compet- points where the change was detected. Only two of the algo-
itive than ordered rule sets in terms of MAE and RMSE. rithms – FIMT and AMRules – were able to detect a change.
Table 5 report the average results over ten experiments vary-
Table 2. Results of ten-fold cross-validation for AMRules algo- ing the seed of the Fried dataset. We measure the number of
rithms
nodes for FIMT, the number of rules AMrules and the the de-
Mean absolut error (variance) Root mean squared error (variance) lay (in terms of number of examples) in detection the drift.
Datasets AMRuleso AMRulesu AMRuleso AMRulesu The delay gives indication of how fast the algorithm will be
2dplanes 1.23E+00 (0.01) 1.16E+00 (0.01) 1.67E+00 (0.02) 1.52E+00 (0.01)
Airlerons 1.10E-04 (0.00) 1.00E-04 (0.00) 1.90E-04 (0.00) 1.70E-04 (0.00)
able to start the adaptation strategy. These two algorithms ob-
Puma8NH 3.21E+00 (0.04) 3.26E+00 (0.02) 4.14E+00 (0.05) 4.28E+00 (0.03) tained similar results. The general conclusions are that FIMT
Puma32H 1.10E-02 (0.00) 1.20E-02 (0.00) 1.60E-02 (0.00) 1.20E-02 (0.00) and AMRules algorithms are robust and have better results
Pol 14.0E+00 (25.1) 15.6E+00 (3.70) 23.0E00 (44.50) 23.3E00 (4.08)
Elevators 3.50E-03 (0.00) 1.90E-03 (0.00) 4.80E-03 (0.00) 2.20E-03 (0.00) than IBLStreams. Figures 3 and 4 show the evaluation of the
Fried 2.08E+00 (0.01) 1.13E+00 (0.01) 2.78E+00 (0.08) 1.67E+00 (0.25) MAE and the RMSE of the streaming algorithms on non-
Bank8FM 4.31E-02 (0.00) 4.30E-02 (0.00) 4.80E-02 (0.00) 4.30E-02 (0.00) stationary real-world problem. FIMT and AMRules obtain
Kin8nm 1.60E-01 (0.00) 1.50E-01 (0.00) 2.10E-01 (0.00) 2.00E-01 (0.00)
approximately similar behavior in terms of MAD and MSE.
Both exhibit somewhat better performance than IBLStreams,
but not significantly different.
Comparison with other Streaming Algorithms
We compare the performance of our algorithm with three
other streaming algorithms, FIMT and IBLStreams. FIMT is
an incremental algorithm for learning model trees, addressed
in [10]. IBLStreams is an extension of MOA that consists in
an instance-based learning algorithm for classification and re-
gression problems on data streams by [1].
The performance measures for these algorithms are given
in Table 3. The comparison of these streaming algorithms
shows that AMRules get better results.
Comparison with State-of-the-art Regression Algorithms
Another experiment which involves adaptive model rules is
shown in Table 4. We compare AMRules with other non-
incremental regression algorithms available in WEKA [9]. Fig. 1. Mean absolut error of streaming algorithms using the dataset
All these experiments using algorithms are performed us- Fried.
ing WEKA. We use the standard method of ten-fold cross-
validation, using the same folds for all the algorithms in-
cluded. 5 Conclusions
The comparison of these algorithms show that AMRules Learning regression rules from data streams is an interest-
is very competitive in terms of (MAE, RMSE) than all the ing approach that has not been explored by the stream mining
other methods, except M5Rules. AMRules is faster than all community. In this paper, we presented a new regression rules
the other algorithms considered in this study. These results approach for streaming data with change detection. The AM-
were somewhat expected, since these datasets are relatively Rules algorithm is able to learn very fast and the only mem-
small for the incremental algorithm. ory it requires is for storing sufficient statistics of the rules. To
Table 3. Results of ten-fold cross-validation for Streaming Algorithms
Mean absolut error (variance) Root mean squared error (variance)
Datasets AMRulesu FIMT IBLStreams AMRulesu FIMT IBLStreams
2dplanes 1.16E+00 (0.01) 8.00E-01 (0.00) 1.03E+00 (0.00) 1.52E+00 (0.01) 1.00E+00 (0.00) 1.30E+00 (0.00)
Airlerons 1.00E-04 (0.00) 1.90E-04 (0.00) 3.20E-04 (0.00) 1.70E-04 (0.00) 1.00E-09 (0.00) 3.00E-04 (0.00)
Puma8NH 2.66E+00 (0.01) 3.26E+00 (0.03) 3.27E+00 (0.01) 4.28E+00 (0.03) 12.0E+00 (0.63) 3.84E+00 (0.02)
Puma32H 1.20E-02 (0.00) 7.90E-03 (0.00) 2.20E-02 (0.00) 1.00E-04 (0.01) 1.20E-02 (0.00) 2.70E-02 (0.00)
Pol 15.6E+00 (3.70) 38.2E+00 (0.17) 29.7E+00 (0.55) 23.3E+00 (4.08) 1,75E+03 (1383) 50,7E+00 (0.71)
Elevators 1.90E-03 (0.00) 3.50E-03 (0.00) 5.00E-03 (0.00) 2.20E-03 (0.00) 3.00E-05 (0.00) 6.20E-03 (0.00)
Fried 1.13E+00 (0.01) 1.72E+00 (0.00) 2.10E+00 (0.00) 1.67E+00 (0.25) 4.79E+00 (0.01) 2.21E+00 (0.00)
Bank8FM 4.30E-02 (0.00) 3.30E-02 (0.00) 7.70E-02 (0.00) 4.30E-02 (0.00) 2.20E-03 (0.00) 9.60E-02 (0.00)
Kin8nm 1.60E-01 (0.00) 1.60E-01 (0.00) 9.50E-01 (0.00) 2.00E-01 (0.00) 2.10E-01 (0.00) 1.20E-01 (0.00)
Table 4. Results of ten-fold cross-validation for AMRulesu and others Regression Algorithms
Mean absolute error (variance) Root mean squared error (variance)
Datasets MRulesu M5Rules MLPerceptron LinRegression MRulesu M5Rules MLPerceptron LinRegression
2dplanes 1.16E+00 (0.01) 8.00E-01 (0.01) 8.70E-01 (0.01) 1.91E+00 (0.00) 1.52E+00 (0.01) 9.8E-01 (0.01) 1.09E+00 (0.01) 2.37E+00 (0.00)
Airlerons 1.00E-04 (0.00) 1.00E-04 (0.00) 1.40E-04 (0.00) 1.10E-04 (0.00) 1.70E-04 (0.00) 2.00E-04 (0.00) 1.71E-04 (0.00) 2.00E-04 (0.00)
Puma8NH 3.26E+00 (0.03) 2.46E+00 (0.00) 3.34E+00 (0.17) 3.64E+00 (0.01) 4.28E+00 (0.03) 3.19E+00 (0.01) 4.14E+00 (0.20) 4.45E+00 (0.01)
Puma32H 1.20E-02 (0.00) 6.80E-03 (0.00) 2.30E-02 (0.00) 2.00E-02 (0.00) 1.20E-02 (0.00) 8.60E-03 (0.00) 3.10E-02 (0.00) 2.60E-02 (0.00)
Pol 15.6E+00 (3.70) 2.79E+00 (0.05) 14.7E+00 (5.53) 26.5E+00 (0.21) 23.3E+00 (4.08) 6.56E+00 (0.45) 20.1E+00 (15.1) 30.5E+00 (0.16)
Elevators 1.90E-03 (0.00) 1.70E-03 (0.00) 2.10E-03 (0.00) 2.00E-03 (0.00) 2.20E-03 (0.00) 2.23E-03 (0.00) 2.23E-03 (0.00) 2.29E-03 (0.00)
Fried 1.13E+00 (0.01) 1.25E+00 (0.00) 1.35E+00 (0.03) 2.03E+00 (0.00) 1.67E+00 (0.25) 1.60E+00 (0.00) 1.69E+00 (0.04) 2.62E+00 (0.00)
Bank8FM 4.30E-02 (0.00) 2.20E-02 (0.00) 2.60E-02 (0.00) 2.90E-02 (0.00) 4.30E-02 (0.00) 3.10E-02 (0.00) 3.40E-02 (0.00) 3.80E-02 (0.00)
Kin8nm 1.60E-01 (0.00) 1.30E-01 (0.00) 1.30E-01 (0.00) 1.60E-01 (0.00) 2.00E-01 (0.00) 1.70E-01 (0.00) 1.60E-01 (0.00) 2.00E-01 (0.00)
Fig. 4. Root mean squared error of streaming algorithms using the
Fig. 2. Root mean squared error of streaming algorithms using the dataset Airlines.
dataset Fried.
the best of our knowledge, in the literature there is no other
method that addresses this issue.
AMRules learns ordered and unordered rule sets. The ex-
perimental results point out that unordered rule sets, in com-
parison to ordered rule sets, are more competitive in terms
of error metrics (MAE and RMSE). AMRules achieves bet-
ter results than the others algorithms even for medium sized
datasets. The AMRule algorithm is equipped with explicit
change detection mechanisms that signals change points dur-
ing the learning process. This information is relevant to un-
derstand the dynamics of evolving streams.
Acknowledgments:
Fig. 3. Mean absolut error of streaming algorithms using the dataset The authors acknowledge the financial support given by the
Airlines. projects FCT-KDUS (PTDC/EIA/098355/2008); FCOMP -
01-0124-FEDER-010053, the ERDF through the COMPETE
Programme and by Portuguese National Funds through FCT 19. C. J. Willmott and K. Matsuura. Advantages of the mean ab-
within the project FCOMP - 01-0124-FEDER-022701. solute error (mae) over the mean square error (rmse) in assess-
ing average model performance. Climate Research, 30:79–82,
2005.
References
1. S. Ammar and H. Eyke. Iblstreams: a system for instance-based
classification and regression on data streams. Evolving Systems,
3:235–249, 2012.
2. A. Bifet, G. Holmes, B. Pfahringer, P. Kranen, H. Kremer,
T. Jansen, and T. Seidl. Moa: Massive online analysis. Jour-
nal of Machine learning Research (JMLR), pages 1601–1604,
2010.
3. K. E. Blake and C. Merz. Uci repository of machine learning
databases. 1999.
4. L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classifica-
tion and Regression Trees. Wadsworth and Brooks, Monterey,
CA, 1984.
5. E. Frank, Y. Wang, S. Inglis, G. Holmes, and I. H. Witten. Using
model trees for classification. Machine Learning, 32(1):63–76,
1998.
6. J. Frnkranz, D. Gamberger, and N. Lavra. Foundations of Rule
Learning. Springer, 2012.
7. J. Gama. Knowledge Discovery from Data Streams. Chapman
& Hall, CRC Press, 2010.
8. J. Gama, R. Sebasti ao, and P. P. Rodrigues. Issues in evaluation
of stream learning algorithms. In Proceedings of the 15th ACM
SIGKDD international conference on Knowledge discovery and
data mining, KDD ’09, pages 329–338, New York, NY, USA,
2009. ACM.
9. M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann,
and I. H. Witten. The weka data mining software: an update.
SIGKDD Explor. Newsl., 11:10–18, 2009.
10. E. Ikonomovska, J. Gama, and S. Dzeroski. Learning model
trees from evolving data streams. Data Min. Knowl. Discov.,
23(1):128–168, 2011.
11. H. Mouss, D. Mouss, N. Mouss, and L. Sefouhi. Test f page-
hinckley, an approach for fault detection in an agro-alimentary
production system. In Proceedings of the Asian Control Con-
ference, 2:815–818, 2004.
12. E. S. Page. Continuous inspection schemes. Biometrika,
41(1):100–115, 1954.
13. D. Potts and C. Sammut. Incremental learning of linear model
trees. Machine Learning, 61(1-3):5–48, 2005.
14. J. R. Quinlan. Learning with continuous classes. In Aus-
tralian Joint Conference for Artificial Intelligence, pages 343–
348. World Scientific, 1992.
15. J. R. Quinlan. Combining instance-based and model-based
learning. pages 236–243. Morgan Kaufmann, 1993.
16. K. Ron. A study of cross-validation and bootstrap for accuracy
estimation and model selection. pages 1137–1143, 1995.
17. H. Wassily. Probability inequalities for sums of bounded ran-
dom variables. Journal of the American Statistical Association,
58(301):13–30, 1963.
18. S. M. Weiss and N. Indurkhya. Rule-based machine learning
methods for functional prediction. Journal of Artificial Intelli-
gence Research, 3:383–403, 1995.