Random Histogram Forest For Unsupervised Anomaly Detection

Random Histogram Forestfor Unsupervised Anomaly DetectionAndrian PUTINA, Mauro SOZIODario ROSSI, José M. NAVARROTelecom Paris, Paris, Francename.surname@telecom-paris.frHuawei Technologies SASU, Paris, Francename.surname@huawei.comAbstract—Roughly speaking, anomaly detection consists ofidentifying instances whose features significantly deviate from therest of input data. It is one of the most widely studied problems inunsupervised machine learning, boasting applications in networkintrusion detection, healthcare and many others. Several methodshave been developed in recent years, however, a satisfactorysolution is still missing to the best of our knowledge. We presentRandom Histogram Forest an effective approach for unsupervisedanomaly detection. Our approach is probabilistic, which hasbeen proved to be effective in identifying anomalies. Moreover,it employs the fourth central moment (aka kurtosis), so as toidentify potential anomalous instances. We conduct an extensiveexperimental evaluation on 38 datasets including all benchmarksfor anomaly detection, as well as the most successful algorithmsfor unsupervised anomaly detection, to the best of our knowledge.We evaluate all the approaches in terms of the average precisionof the area under the precision-recall curve (AP). Our evaluationshows that our approach significantly outperforms all otherapproaches in terms of AP while boasting linear running time.I. I NTRODUCTIONHawkins [1] defines an anomaly (aka outlier) as “an observation, which deviates so much from other observationsas to arouse suspicions that it was generated by a differentmechanism.” Identifying those anomalies is crucial in manyapplications, as it might reveal an unauthorized access incomputer networks or a disease in a patient, for example.Thus, anomaly detection boasts applications in networkintrusion detection, fraud detection, healthcare, and manyothers, while providing a valuable tool in data cleaning.It is one of the most widely studied problems in bothunsupervised and supervised machine learning. Because of thedifficulties in obtaining large amounts of labeled data, as wellas, in dealing with high class imbalance [2], unsupervisedapproaches preserve their appeal. As a result, unsupervisedanomaly detection has received increasing attention in recentyears (e.g. Isolation Forest [3], OCSVM [4], LOF [5]). Amongthe supervised approaches we mention random forest [6] andautoencoders [7].One of the most effective algorithms for unsupervisedanomaly detection is Isolation Forest (iForest), as confirmedalso by our experimental evaluation. In our work, we presentRandom Histogram Forest (RHF) an effective approach forunsupervised anomaly detection. Similarly to iForest, ourapproach is probabilistic while relying on an “ensemble”of “weak” building blocks (trees) for effectively identifyinganomalies. This has been proved to be effective for a widerange of tasks (e.g. Random Forest [6], Isolation Forest [3]).Our approach builds a random forest based on all inputinstances, whereas iForest builds a random forest based solelyon some random samples of the data. The latter strategyhas the drawback that some anomalies might be neglectedentirely in the construction of the forest, thereby impairingthe capability of the algorithm of finding those anomalies.Nevertheless, our algorithm boasts linear running time in thesize of the input. Another key idea of our algorithm is toemploy the fourth central moment (aka kurtosis), so as to guidethe search for anomalous instances. Our algorithm computesa score for every instance, measuring the likelihood of suchan instance of being an anomaly. Such a score is defined asthe Shannon’s information content of the leaf containing thecorresponding instance.We conduct an extensive experimental evaluation on 38datasets including all benchmarks for anomaly detection,as well as the most successful algorithms for unsupervisedanomaly detection, to the best of our knowledge. We evaluateall the approaches in terms of the average precision of thearea under the precision-recall curve (AP). We observe that assuggested in [8], ROC might not reflect the real performancesof the algorithm, in that, anomalies typically represent a smallfraction of the input data.Our experimental evaluation shows that RHF outperformsall other approaches in terms of AP. In particular, it outperforms iForest in terms of AP by a factor of 10% on averageand up to a factor of 2 in some datasets. Moreover, it showsthat the performances of our algorithm are consistently goodover a wide range of parameter values, which allows for aneffective parameter tuning.The rest of the paper is organized as follows. We startby overviewing top performer anomaly detection algorithmsin section II and introduce the Random Histogram Forestalgorithm in section III. We then describe our experimentalevaluation and results in section IV. Finally, we discuss andsummarize our main findings in section V.II. R ELATED W ORKSeveral unsupervised anomaly detection algorithms havebeen developed in recent years. We can classify the relatedwork as follows: (i) Probabilistic/Linear based methods (e.g.

density of each instance against the local density of neighbors.Ensemble/Isolation based methods isolate anomalies instead of profiling normal instances by recursively splitting thedata through a random tree and generating so isolation forests.Isolation Forest [3]: builds a forest of randomly generatedtrees and assigns to each instance x X the average pathlength from the root to the node containing x as anomaly score.The authors show empirically that shorter path lengths arerepresentative of anomalies as they are more easily to isolatewith respect to normal data.Based on the most recent comparison studies [9], [10], [15],the algorithms previously described have proven to be amongthe best in regards anomaly detection. In general both [10] and[15] suggest iForest to be, on average, the best one closelyfollowed [10] by PPCA and OCSVM.PPCA, HBOS, OCSVM, etc.); (ii) Proximity/Nearest-Neighborbased methods (e.g. K-NN, K th -NN, Local Outlier Factor);(iii) Ensemble/Isolation based methods (e.g. Isolation Forest).Among the most recent comparative studies of unsupervisedtechniques, [9] compares most of the existing proximity-basedmethods on 10 different datasets and conclude that it is of greatimportance the initial assumption whether the anomalies in thedatasets are global or local: they recommend to use a globalanomaly detection methods if there is no further knowledgeabout the nature of anomalies in the dataset to be analyzed.[10] compares 14 methods belonging to all the groups previously described on 15 different datasets (12 publicly availableand 3 private ones). However, their study assesses if the modelsare able to generalize to future instances, so they perform aMonte Carlo cross validation of 5 iterations, using 80% of thedata for the training phase and 20% for the prediction whichindicates a semi-supervised setup to our understanding. While[9] study does not include the latest methods presented (e.g.Isolation Forest, thought to be the state-of-art), [10] describesthe models generalization capacity using labels that most ofthe time are not available. We compare the methods whichhave proven to be the best in previous studies [9], [10] usingdefault or reasonable parameters and use labels only to assesstheir performance in a completely unsupervised environment.Probabilistic based methods estimate the parameters θ ofthe dataset X and assigns to each instance x X an anomalyscore equal to the likelihood P (X θ).Probabilistic Principal Component Analysis (PPCA) [11]:estimates the principal components of the data and projectsthe d-dimensional dataset to a q-dimensional one estimatingthe latent variables by iteratively maximizing the likelihoodusing an expectation-maximimation algorithm.Histogram-based Outlier Score (HBOS) [12]: generates ahistogram for each feature assuming they are independent.Similar to the Naive Bayes approach in which all the independent feature probabilities are multiplied, HBOS outputs ananomaly score given by the multiplication of the inverse heightof the bins of all the features.One-Class SVM [4]: determines a separating hyperplanein a higher dimensional space by maximizing the distancefrom the hyperplane to the origin. The ν parameter acts asa regularization parameter as determines an upper bound onthe percentage of data falling outside the boundary and a lowerbound on the number of support vectors.Proximity/Nearest-Neighbor based methods compute theneighborhood of all the instances x X and uses the distancesof each instance x to describe abnormality.K-NN [13] and Kth-NN [14]: Both K-NN and K th -NNcompute the distances for each instance x X to the knearest-neighbors and assign them either the mean distance(K-NN) or the max one (k th -NN).Local Outlier Factor (LOF) [5]: introduced first the ideaof local anomalies and detects them by comparing the localIII. R ANDOM H ISTOGRAM F OREST (RHF)RHF is an ensemble model apt at splitting the dataset into ηdifferent groups. The algorithm randomly partitions the inputpoints by means of several splits drawn at random. Intuitively,points that end up in a relatively large group are less likely tobe anomalies. By iterating such a process multiple times, wecan measure how likely a point is an anomaly.To put this idea into practice, RHF splits the data into ηdifferent bins by means of a Random Histogram Tree (RHT).Each RHT is built by recursively splitting the whole dataset:each splitting decision is done selecting an attribute a to splitaccording to its kurtosis score and a split value randomlyselected from its support. By setting the parameter max heighth, each RHT produces at most η 2h leafs corresponding toη bins in which all the instances are grouped. Finally, theanomaly score of each instance x X is the informationcontent (aka self-entropy) of its terminating leaf Q aggregatedover all the trees.Random Histogram Tree: Given a dataset X Rn d , wheren is the number of instances and d the number of features orattributes, a RHT is a binary tree in which a node Qi is eitheran internal node with exactly two children or a leaf node withno children. In the former case, the node splits the datasetinto a left branch XQL and a right one XQR , according to thekurtosis Split. A RHT contains at most η 2h leafs, where his the maximum height of the tree.kurtosis Split: a kurtosis split chooses according to whichattribute a d to split the dataset X by assigning higherprobability to features whose kurtosis scores are higher. Givena random variable X , the kurtosis score is defined as:" K[X ] EX µσ 4 #hi4E (X µ)µ4 hi2 4 ,σ2E (X µ)(1)where µ4 is the fourth central moment and σ the standarddeviation, measures the tailedness of X . Equation (1) denotes2