Discovering anomalies within data is nowadays very important, because it helps to uncover interesting events. Consequently, a considerable amount of anomaly detection algorithms was proposed in the last few years. Only a few papers about anomaly detection at least mentioned why some samples were labelled as anomalous. Therefore, we proposed a method allowing to extract rules explaining the anomaly from an ensemble of specifically trained decision trees, called sapling random forest. Our method is able to interpret the output of an arbitrary anomaly detector. The explanation is given as conjunctions of atomic conditions, which can be viewed as antecedents of association rules. In this work we focus on selection, post processing and evaluation of those rules. The main goal is to present a small number of the most important rules. To achieve this, we use quality measures such as lift and confidence boost. The resulting sets of rules are experimentally and empirically evaluated on two artificial datasets and one real-world dataset.
According to an IBM research [
Not only it is almost impossible to process such huge
amounts of data, we are actually not interested in the
raw data, but rather in the salient knowledge and
interesting patterns contained in them. This is the reason why
anomaly detection, especially unsupervised anomaly
detection, becomes more and more important [
For the purposes of this paper consider anomalies equal
to outliers as defined by Hawkins [
The more formal definition would necessarily reduce the amount of plausible anomaly detectors and/or application domains. This is in conflict with our goal to provide a solution as general as possible.
Even though anomaly detection techniques are aimed at
only a minority of samples, the importance and demand
for them grows rapidly. The real world applications range
from the network security [
The identification of anomalies is only a half of the whole task. The second and equally important half is the interpretation. In high dimensional domains, like the network security or bioinformatics, where hundreds or even thousands of features are common, the proper interpretation is crucial.Therefore, anomalies have to be interpreted clearly, as a feature subset that explains its deviation from ordinary data, or even better as a set of association rules.
In [
The main drawback of the direct rule extraction from our sapling random forests is the big number of rules with some of them introduced by unfortunate training set selection. Partially, these issues can be solved by confidence and / or support thresholds. But for our ultimate goal to present the minimal number of rules containing the maximal amount of useful information, such a simple approach is insufficient. Therefore, in this paper we focus on proper selection, post processing and evaluation of rulesets extracted from sapling random forests during anomaly explanation. We tested association rules quality measures such as lift and confidence boost. This paper is work in progress and we would like to extend the number of tested quality measures by some subjective measures like novelty.
The rest of this paper is organised as follows. The next section briefly reviews related work. Section 3 describes the SRF principles and its training followed by the rule extraction process in Section 4. The selected quality measures of association rules are presented in Section 5. Experimental evaluation is described in Section 6 and Section 7 concludes the paper. 2
For more information about the anomaly detection we
refer to the recent book of Aggarwall [
Knorr et al. [
Dang et al. [
The most similar to our approach and most recent
is [
On the other hand, there are many papers about
association rules. This paper was inspired mainly by [
An alternative approach, well described in [
This section outlines principles of sapling random forests.
SRF is a method able to explain an output of an
arbitrary anomaly detector, proposed by us in [
Algorithm 1 Algorithm summary y ← anomalyDetector(data) for all data(y ==anomaly) do
T ← createTrainingSet(size, method) t ← trainTree(T )
SRF ← t end for extractRules(SRF ) 3.1
Dataset X = {x1, x2, . . . , xl }, where x ∈ Rd , can be split
into two disjoint sets X a, containing anomalous samples,
and X n,containing normal samples. Then, a training set T
contains the anomaly xa as one class and a subset of X n
as the other. The first strategy of creating training sets is
to select k nearest neighbours of xa from X n. This
strategy is sensible for algorithms detecting local anomalies,
as according to [
The second strategy is to select k samples randomly
from X n with uniform probability. The advantage of this
approach is a possibility to generate more than one
training set per anomaly by repeating the sampling process.
More training sets lead to more saplings per anomaly and
to more robust explanation, but at the expense of the more
complicated aggregation of rules extracted from them (see
Section 4). A comparison of both approaches can be found
in [
For simplicity consider sapling a binary decision tree with
typical height 1-3. In the SRF method, there are always
two leaves at the maximal depth, one of which contains
only an anomaly xa and the other containing only normal
samples. The saplings small height has two reasons. First,
training sets are relatively small. Second, according to the
anomaly isolation approach [
The standard procedure, to find the splitting function h for a new internal node, is maximising an information gain over the space of all possible splitting functions H as arg max − h∈H
∑ b∈{L,R} |Sb(h)| H(Sb), |S| where S is the subset of the training set T reaching the leaf being split, SL(h) = {x ∈ S|h(x) = +1} and SR(h) = {x ∈ S|h(x) = −1} and H(S) is an entropy of S.
The second commonly used approach involves minimising the Gini impurity.
arg min ∑ h∈H b∈{L,R} 1 −
|xa| (Sb(h)) 2 −
|xn| (Sb(h)) 2
For experiments presented in this paper we used information gain. 4
Once a sapling is grown, it is used to explain the anomaly xa. Let h j1,θ1 , . . . , h jd,θd be the set of splitting functions, with features j1, . . . , jd and threshold θ1, . . . , θd , used in the inner nodes on the path from the root to the leaf with the anomaly xa. Then xa is explained as a conjunction of atomic conditions : c = (x j1 > θ1) ∧ (x j2 > θ2) ∧ . . . ∧ (x jd > θd ), (3) which is the output of the algorithm. This conjunction can be read as “the sample is anomalous because it is greater than threshold θ1 in feature j1 and greater than θ2 in feature j2 and . . . than majority (or nearest neighbour) samples.” Because resulting trees are very small, the explanation is compact.
The situation is more difficult, when more saplings per anomaly have been grown, as each sapling provides one conjunction of type (3). Using more than one sapling per anomaly improves robustness for training sets created by uniform sampling. The problem is that returning set of all conjunctions C is undesirable, as the primary objective — explanation of the anomaly to a human — would not be met. Hence, the algorithm needs to aggregate conjunctions in C.
For simplicity of the following notation consider 2d items, in such a way that 2 items are assigned to each feature, one for "<" rules, the other for ">" rules. Denote this 2d set of items F . Then we can group rules into the rule sets R f according to the item set f ⊆ F they share.
Based on |R f | the algorithm discards groups of low importance by sorting them in descend order, and then using only the first k groups such, that their cumulative frequency is greater than a threshold τ , which we recommend r f = c f → y, where c is a conjunction of atomic conditions like (3), y = x ∈ X a and f ⊆ F . The r f in its full form then look as: r f (x) = x f1 > θ f1 ∧ x f2 > θ f2 ∧ . . . ∧ x fn > θ fn → x ∈ X a, (8) where n is a maximal index in the itemset f .
For this kind of rules support [
a supp(y) = |X | . (10) |X | and gives the proportion of data points which satisfy the antecedent c, respectively the consequent y. It is used to measure the importance of a rule or as a frequency constrain. The disadvantage of support is that infrequent rules are often discarded. This is much bigger problem than it could seem because we are generating rules for anomalies, which are rare by definition. to be 0.90 or 0.95. Using the adopted notation, k is determined as
1 k k = arg min ∑ |R fi | > τ ,
k ∑ f ∈F |R f | i=1
By this approach we obtain one representative rule for each feature set f as:
c¯f = x j1 > θ¯1 ∧ x j2 > θ¯2 ∧ . . . ∧ x jt > θ¯t . 5
This section reviews selected quality measures of association rules. Typical association rules are in the form A → Y , where A, Y are item sets. In rules extracted from SRF, items are atomic conditions and Y always means: “is anomalous”. Therefore, our rules are in the form: where it is assumed, that R f are sorted according to their size to simplify the notation. We have also investigated the complementary approach, where groups are selected, if they were used with a frequency higher than a specified threshold. But the presented strategy based on the cumulative frequency showed more consistent results in our experiments.
Once the set of groups with decision rules is selected, we create one rule r ¯f for every rule set R f .Thresholds for each item f j are calculated as an average of all thresholds within the rule set R f .
θ¯j = 1 |R fi |
∑ θi, j |R f | i=1 (1) (2) (4) (5) (6) (7) (9)
Another frequently used measure is confidence [
It estimates the conditional probability of the consequent being true on condition that the antecendent is true. The trouble with confidence is caused by its sensitivity to the frequency of y. Because all rules extracted from SRF have the same consequent the rule ranking produced by lift a confidence would be the same.
The third measure we used is lift [
Finally, confidence boost introduced by Balcázar [
conf(r f ) β (r f ) = max{conf(r0 f 0 )|supp(r0 f 0 ) > σ , r f 6≡ r0 f 0 , f 0 ⊆ f } (13) where σ is support threshold and r f 6≡ r0 f 0 denotes the inequivalence of rules r f and r0f 0 , which for our simple case where all consequents are the same, means that f 6= f 0. From (13) is evident that f 0 ⊂ f .
If the set of confidences in denominator is empty, the confidence boost is by convention set to infinity. , 6
For the experimental evaluation we used the synthetical
three layer donut, the well known Fisher’s iris and the
Letter recognition data set from the UCI repository [
The three layer donut dataset contains 1000 normal samples forming the two dimensional toroid (donut). There are 200 anomalies, one half inside the toroid and the second half out of it. For this dataset we created 10 rules per anomaly, using SRF, resulting in 2000 rules. After the simple aggregation, described in Section 4, only 8 rules left. All of them printed in Table 1, sorted by their respective support. All rules before aggregation were used to calculate confidence boost. Otherwise, many rules would have confidence boost equal to infinity because there are no rules defined on any subset of their item sets f .
The fact is that rules r5 − r8 have quite small support but, according to the other measures and our intuition, they are very important. The small supports is due to the small rule r1 = x1 > −0.33 ∧ x2 > −0.39 r2 = x1 > −0.33 ∧ x2 < 0.3 r3 = x1 < 0.4 ∧ x2 < 0.34 r4 = x1 < 0.37 ∧ x2 > −0.37 r5 = x2 > 2.2 r6 = x1 > 2.3 r7 = x2 < −2.4 r8 = x1 < −2.4 supp 0.38 0.37 0.37 0.37 0.02 0.02 0.01 0.01 number of data points explained, lets recall that anomalies are only one sixth of all data points in this dataset. Both, lift and confidence boost, mostly reflects our subjective expectations.
All rules are depicted at Figure 1. Its evident that presented rules cannot separate anomalies from normal samples perfectly. Especially difficult are anomalies inside the donut. To separate those inner anomalies perfectly it would be necessary to combine more rules together, for example r1 and r3 or r2 and r4. The virginica species were selected as anomalous class for the iris data set. Five rules per anomaly were produced using SRF, resulting in 250 rules. After aggregation we have got 6 rules. They are written in Table 2 with their respective quality measures. Confidence boost was calculated using all 250 rules.
The main problem with all those rules is that almost every one of them can sufficiently separate anomalies from rule r1 = x1 > 6 ∧ x4 > 1.7 r2 = x4 > 2 r3 = x3 > 5.5 r4 = x2 < 2.8 ∧ x4 > 1.6 r5 = x1 > 7.3 r6 = x2 < 2.2 normal samples. No one of presented measures could help in selecting the most informative, yet small as possible, set of rules. Because presented rules are seen informationally equivalent by all quality measures. This doesn’t say much about difference between the quality measures but it justifies the rule extraction process, because all generated rules have high score.
Figure 2 shows the iris dataset with rules r1, r2 and r5. 6.3
This dataset was created as a classification problem with 26 classes, one class for each letter in the English alphabet. The charactersÒ were obtained from 20 different fonts and randomly distorted to produce 20,000 unique samples presented as 16 dimensional numerical vectors. Letter X was selected as the anomaly class. SRF produced more than 15,000 rules, which were reduced by aggregation to 1955. Aggregated rules with support higher than 0.10 are presented in Table 3. The ranking of those rules is plotted at Figure 3. Its evident that the ranking given by lift and confidence boost differs substantially.
It is nearly impossible to evaluate all rules. Therefore, we have selected only those with confidence boost higher than one (202 rules) and those with lift higher than one lift confidence boost 25 20 15 g n i k n a r 10 5 00
rules 5 10 15 20 25 (446 rules). The confidence boost selected the smaller rule set where almost all rules looked plausible. On the other hand, they missed some really interesting ones most highly rated by lift. The confidence boost tend to choose shorter more similar rules, whereas lift prefer richer and more heterogenous rules. Therefore, from our point of view the top 10 lift rules x8 < 1.8 ∧ x15 > 7.8 x2 < 1.8 ∧ x3 > 4.5 ∧ x9 > 8.8 x5 > 6.8 ∧ x8 < 1.8 ∧ x15 > 7 x5 > 5 ∧ x9 > 8.2 ∧ x10 < 5.2 x4 < 2.2 ∧ x6 > 8.2 ∧ x9 > 7.8 x2 < 5.6 ∧ x3 > 7.2 ∧ x8 < 1.2 x1 > 4.5 ∧ x8 < 1.8 ∧ x15 > 7.8 x7 < 5.8 ∧ x8 < 2.5 ∧ x15 > 7.8 x2 < 4.8 ∧ x9 > 8 ∧ x11 > 9.8 x11 > 9 ∧ x14 > 13 top 10 β rules x4 < 1.2 ∧ x9 > 8 x2 < 1.5 ∧ x9 > 8.8 x8 < 1.2 ∧ x9 > 8.8 x9 > 8 ∧ x14 < 5.2 x11 > 12 ∧ x16 < 4.5 x6 > 9.8 ∧ x8 < 1.2 x4 > 8.8 ∧ x14 < 5.2 x5 > 8.5 ∧ x14 < 5.2 x8 < 1.2 ∧ x16 > 9.9 x12 > 10 ∧ x16 < 5.2 best selection strategy is choosing top k rules according to the lift ranking. The top 10 rules chosen from the whole set by lift and confidence boost, regardless their support, are in Table 4.
Still there are too much rules to make some conclusions, in our future work we are going to investigate more measures of interestingness and novelty, which will hopefully help us to reduce the amount of extracted rules even more. 7
In this paper, we presented a novel approach for the explanation of an output of an arbitrary anomaly detector using sapling random forests. The explanation is given as conjunctions of atomic conditions, which can be viewed as antecedents of association rules. Due to an extraction method, the individual rules are short and comprehensible. The main drawback was that the rule sets for the bigger dataset were large and redundant. Therefore, we applied multiple quality measures to evaluate them and select those rules with desired properties. Performed experiments showed that no one of presented measures reflect our expectation. From the considered measures the lift looks the most promising. But this paper is just a work in progress and we don’t view this observation as a final conclusion.
For our future work we would like to have a measure that will rate the novelty of a rule with respect to the set of previously selected rules. The first idea is to chose those rules that describe anomalies not covered by the already selected rules. The second idea is to select rules which may describe already covered anomalies but using completely different set of features. The last thing we would like to work on is finding a way of concatenating mined rules to make smaller yet precise rule sets.
The research reported in this paper has been supported by the Czech Science Foundation (GA Cˇ R) grant 13-17187S.