According to an IBM research [13] there were 2,7 zettabytes of data in the digital universe at April 2012 and this amount is doubling approximately every 40 months.
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 [1,23]. Despite it can be formalised as a binary classification, it entails different issues and challenges than those in supervised classification. For example, anomalous events often adapt to appear normally and even normal behaviour evolve over time. Furthermore, defining a normal regions is very difficult, especially when the boundary between normal and anomalous is not always precise.
For the purposes of this paper consider anomalies equal to outliers as defined by Hawkins [11]: " An outlier is an observation which deviates so much from the other observations as to arouse suspicions that it was generated by a different mechanism."
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 [10], bioinformatics [24] or financial fraud detection [22] to the astronomy and space exploration [9].
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 [21] we proposed method of anomaly explanation based upon specifically trained ensembles of decision trees called sapling random forest (SRF). The main idea behind it is to view the explanation as a feature selection and classification problem. Specifically, the goal is to find features in which the margin betweenı anomalous sample and the normal samples is maximised. Therefore, SRF returns subset of features, respectively rules on these features describing why this sample has been identified as an anomaly.
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 mea-sures of association rules are presented in Section 5. Experimental evaluation is described in Section 6 and Section 7 concludes the paper.
For more information about the anomaly detection we refer to the recent book of Aggarwall [1]. This book provides an exhaustive listing of anomaly detection algorithms and their applications in different domains. Another source may be [5], which is briefer but very well written. To our best knowledge, there have been only few works addressing not only identification of anomalies, but also their explanation.
Knorr et al. [15] focused on what kind of knowledge should be extracted and provided to the user. Strong and weak outliers were defined and searched within data by distance-based algorithms described in detail in [14].
Dang et al. [7] presented an algorithm identifying and explaining anomalies. The algorithm starts by selecting a set of neighbouring samples based on quadratic entropy that are presented to a Fisher linear discriminant classifier to seek for an optimal half-space, in which a detected anomaly is well separated. The process of interpretation is entangled with the presented method of identification of anomalies. The difference to our work is that SRF can be used after an arbitrary anomaly detection algorithm to interpret its results.
The most similar to our approach and most recent is [20]. Their approach, as well as ours, can interpret output of an arbitrary anomaly detector as a subset of features. They use classification accuracy for outlier ranking. The main drawback of this approach is that it needs balanced training sets which are created by sampling artificial samples around the anomalous point. With respect to this work, our approach can handle unbalanced training sets easily and returns not only feature subsets but feature subsets with rules on them, providing even more information about the anomaly. Furthermore, we simplify the analysis by clustering, which enables to interpret similar anomalies at once [16].
On the other hand, there are many papers about association rules. This paper was inspired mainly by [3], which is about measuring redundancy and information quality of sets of association rules. The author presents a measure called confidence boost and an algorithm to produce a small set of association rules using this measure. A really extensive list of interestingness measures can be found in [12]. There is a lot of inspiration for our future work.
An alternative approach, well described in [6], may be so called subjective measures. A typical example is the novelty, sometimes called unexpectedness, of a rule with respect to user provided domain knowledge or against the another rule set. Because these terms are ambiguous there are multiple approaches of measuring them. An approach in [18] inspired us for our future work.
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 [21]. It is a random forest of specifically trained decision trees. Because produced trees are small they are called saplings rather than trees. Produced explanations show features in which inspected samples differ the most from the rest of data. These features are used to produce association rules, which are more informative than only a set of features. An outline of the whole method is at Algorithm 1.
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)
Dataset X = {x 1 , x 2 , . . . , x l }, where x ∈ R d , 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 x a 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 x a from X n . This strategy is sensible for algorithms detecting local anomalies, as according to [8] they are more general than algorithms detecting global anomalies. The drawback of this strategy is a computational complexity.
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 [21].
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 x a 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 [19], if the analysed sample is an anomaly, it should be separated easily from the rest of data, resulting again into small trees. Therefore, if the height of a sapling is higher than expected it should be taken into consideration that the explained sample may not be an anomaly.
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
where S is the subset of the training set T reaching the leaf being split, S L (h) = {x ∈ S|h(x) = +1} and S R (h) = {x ∈ S|h(x) = −1} and H(S) is an entropy of S.
The second commonly used approach involves minimising the Gini impurity.
For experiments presented in this paper we used information gain.
Once a sapling is grown, it is used to explain the anomaly x a . Let h j 1 ,θ 1 , . . . , h j d ,θ d be the set of splitting functions, with features j 1 , . . . , j d and threshold θ 1 , . . . , θ d , used in the inner nodes on the path from the root to the leaf with the anomaly x a . Then x a is explained as a conjunction of atomic conditions :
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 j 1 and greater than θ 2 in feature j 2 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 to be 0.90 or 0.95. Using the adopted notation, k is determined as
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 .
By this approach we obtain one representative rule for each feature set f as:
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 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:
where n is a maximal index in the itemset f .
For this kind of rules support [2] is calculated as:
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.
Another frequently used measure is confidence [2]:
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 [4]:
which measures how many times more often the antecedent c and consequent y occur together than expected if they were statistically independent. Lift does not suffer from the rare items problem. Because in our experiments the consequent will always the same frequency there is no need to measure both Finally, confidence boost introduced by Balcázar [3] is calculated as:
where σ is support threshold and r f ≡ r f denotes the inequivalence of rules r f and r f , which for our simple case where all consequents are the same, means that f = f . From ( 13) is evident that f ⊂ f .
If the set of confidences in denominator is empty, the confidence boost is by convention set to infinity.
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 [17].
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 r 5 − r 8 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 supp lift β r 1 = x 1 > −0.33 ∧ x 2 > −0.39 0.38 1.64 0.27 r 2 = x 1 > −0.33 ∧ x 2 < 0.3 0.37 1.60 0.27 r 3 = x 1 < 0.4 ∧ x 2 < 0.34 0.37 1.49 0.25 r 4 = x 1 < 0.37 ∧ x 2 > −0.37 0.37 1.57 0.26 r 5 = x 2 > 2.2 0.02 6.00 1.00 r 6 = x 1 > 2.3 0.02 6.00 1.00
0.01 6.00 1.00
0.01 6.00 1.00
Table 1: Aggregated rules with their quality measures for the three layer donut dataset, sorted by their respective supports.
- 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 r 1 and r 3 or r 2 and r 4 .
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 supp lift β r 1 = x 1 > 6 ∧ x 4 > 1.7 0.25 3.00 1.00 r 2 = x4 > 2 0.19 3.00 1.00 r 3 = x 3 > 5.5 0.17 3.00 1.00 r 4 = x 2 < 2.8 ∧ x 4 > 1.6 0.06 3.00 1.00 r 5 = x 1 > 7.3 0.05 3.00 1.00 r 6 = x 2 < 2.2 0.03 0.75 0.25 Table 2: Aggregated rules with their quality measures for the iris dataset , sorted by their respective supports.
Figure 2: The iris dataset with r 1 plotted as a filled rectangle, and rules r 2 and r 5 as half-planes delimited by solid lines.
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 r 1 , r 2 and r 5 .
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 3: Rules extracted from Letter recognition by SRF with support higher than 0.10 with their quality measures sorted by their respective supports.
(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 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.
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 ČR) grant 13-17187S.