In this work we deal with the problem of detecting and explaining exceptional behaving values in categorical datasets by perceiving an attribute value as anomalous if its frequency occurrence is exceptionally typical or un-typical within the distribution of frequencies occurrences of any other attribute value. The notion of frequency occurrence is provided by specialising the Kernel Density Estimation method to the domain of frequency values and an outlierness measure is de ned by leveraging the cdf of such a density. This measure is able to simultaneously identify two kinds of anomalies called lower outliers and upper outliers, namely exceptionally low or high frequent values. Moreover, data values labeled as outliers come with an interpretable explanations for their abnormality, which is a desirable feature of any knowledge discovery technique.
An outlying observation is one that appears to deviate markedly from other members of the sample in which it occurs. Such rare events can be even more interesting than the more regularly occurring ones as they are suspected of not being generated by the same mechanisms as the rest of the data.
We deal with categorical data and, speci cally, we perceive an attribute value as anomalous if its frequency occurrence is exceptionally typical or un-typical within the distribution of frequencies occurrences of any other attribute value. To quantify such a frequency occurrence we specialize the classical Kernel Density Estimation technique to the domain of frequency values and get to the concept of soft frequency occurrence. The cumulated frequency distribution of the above density estimate is used to decide if the frequency of a certain value is anomalous when compared to the other values' frequencies. In particular, we are able to identify two kind of anomalies, namely lower outliers and upper outliers. A lower outlier is a value whose frequency is low while, typically, the dataset objects assume a few similar values, namely the frequencies of the other values are high. An upper outlier is a value whose frequency is high while, typically, the dataset objects assume almost distinct values, namely the frequencies of the other values are low. Note that the measure detects both scenarios and to automatically characterizes the target value as a lower or upper outlier.
A value can show exceptional behaviour only when we restrict our attention to a subset of the whole population. Thus, we design our technique to output the so-called explanation-property pairs (E; p), where E denotes a condition used to determine the target subpopulation and p represents an attribute pa and a value pv such that the pv is exceptionally frequent or infrequent within the subpopulation selected by the explanation E.
The rest of the work is organised as follows. Section 2 discusses work related with the present one. Section 3 introduces the frequency occurrence function. Section 4 describes the outlierness function for ranking categorical values. Section 5 describes experimental results. 2
Categorical data has received relatively little attention as compared to
quantitative data because detecting anomalies in categorical domain is a challenging
problem [
We start by noting that there is little literature about outlier explanation [
Among traditional outlier detection methods explored in the context of
numerical data[
An example of distance-based method is discussed in [
Detecting local anomalies, i.e. observations having outlying behavior in local
areas, is another interesting discovery problem. Local anomaly detection
methods for categorical data include the k-LOF [
The rst one is an extension of Local Anomalies Factor (LOF) method [
Both distance and density are taken into account by the ROAD algorithm
[
With regard to the outlier explanation, [
In this section we give same preliminary de nitions and introduce the notation employed throughout the paper.
A dataset D on a set of categorical attributes A is a set of objects o assuming values on the attributes in A. By o[a] we denote the value of o on the attribute a 2 A. D[a] denotes the multiset fo[a] j o 2 Dg. Given a multiset V , the frequency fvV of the value v 2 V is the number of occurrences of v in V . A condition C is a set of pairs (a; v) where each a is an attribute and each v 2 D[a]. By DC we denote the new dataset fo 2 D j o[a] = v; 8(a; v) 2 C)g. De nition 1 (Frequency distribution). A frequency distribution H is a multiset of the form H = ff1(1); : : : ; f1(w1); : : : ; fn(1); : : : ; fn(wn)g where each fi(j) 2 N is a distinct frequency, fi(j) = fi(k) = fi for each 1 j; k wi, and wi denotes the number of occurrences of the frequency fi. By N (H) (or simply N whenever H is clear from the context) we denote w1 f1 + : : : + wn fn. For the sake of simplicity, we will refer to a frequency distribution as a set H = ff1; f2; : : : ; fng and to the number of occurrences wi of fi as w(fi).
Now we de ne the notion of frequency occurrence as a tool for quantifying how frequent is a certain frequency.
De nition 2 (Hard frequency occurrence). Given a frequency distribution H, the frequency occurrence FH(fi) of fi, also denoted by F (fi) whenever H is clear from the context, is the product wi fi.
The above de nition allows us to associate with each distinct value in D[a] a score that is related not only to its frequency in the dataset but also to how many other values have its same frequency. However, close frequency values do not interact with each other, e.g. having fi = 49; wi = 1 and fi+1 = 51; wi+1 = 1 is completely di erent from fi0 = 50; wi0 = 2, as in the former case F (fi) = 49 and F (fi+1) = 51 while in the latter we have F (fi0) = 100 that is about twice the previous case. Intuitively, we do not desire a similar small variation in the frequency distribution to impact so largely on the frequency occurrence values. To force close frequency values to in uence each other in order and jointly contribute to the frequency occurrence we design an ad-hoc density estimation method inspired to Kernel Density Estimation (KDE).
A (discrete) kernel function Kfi with parameter fi is a probability mass function having the property that supf 0 Kfi (f ) = Kfi (fi). Given an interval I = [fl; fu] of frequencies, a frequency fi, and a kernel function K, the volume of Kfi in I, denoted as VI (Kfi ), is given by Pfu f=fl Kfi (f ). The following expression F (f ) =
( n )
X X wi fi Kfi (') : '2I(f) i=1 (1) where I(f ) represents an interval of frequencies centred in f , provides the density estimate of the frequency occurrence of the frequency f .
Since Kfi ( ) is a probability mass function, the frequency fi provides a contribution to the frequency occurrence of f corresponding to the portion of the volume of Kfi which is contained in I(f ), that is VI(f)(Kfi ).
It is possible to eliminate the dependence from I(f ) by properly weighting the contribution of Kfi ( ) based on its distance from the target frequency f . Such a weight can be directly obtained from the associated kernel as the ratio between the probability of observing frequency f and the probability of observing fi, when such frequencies are realization of a random variable distributed according to Kfi ( ). This allow us to rewrite equation 1 as follows: (2) (3) F (f ) = X ( n
X
Note that the summation over the domain of all Kfi ( ) values is equal to 1 since it is a probability mass function. Moreover, as F represents a notion of density function associated with frequency occurrences, it is preferable that its volume evaluated in the frequencies H = ff1; : : : ; fng evaluates to N (H). This leads to the following nal form of the frequency occurrence function. De nition 3 (Soft occurrence function). Given a frequency distribution H, the frequency occurrence FH(fi) of fi, also denoted by F (fi) whenever H is clear from the context, is given by the following expression
As for the kernel selection we exploit the binomial distribution binopdf (f ; n; p) with parameter n, denoting the number of independent trials, equal to N (H), and parameter p, denoting the success probability, equal to p = fi=N (H). 4
The idea behind the measure we will discuss in the following is that an object in a categorical dataset can be considered an outlier with respect to an attribute if the frequency of the value assumed by this object on such an attribute is rare if compared to the frequencies associated with the other values assumed on the same attribute by the other objects of the dataset. We are interested in two relevant kinds of anomalies referring to two di erent scenarios.
Lower Outlier. An object o is anomalous since for a given attribute a the value that o assumes in a is rare (its frequency is low) while, typically, the dataset objects assume a few similar values, namely the frequencies of the other values are high. Upper Outlier. An object o is anomalous since for a given attribute a the value that o assumes in a is usual (its frequency is high) while, typically, the dataset objects assume almost distinct values, namely the frequencies of the other values are low.
In order to discover outliers, we exploit the cumulated frequency distribution associated with the estimated density.
De nition 4 (Cumulated frequency distribution). Given a frequency distribution H = ff1; : : : ; fng, the associated cumulated frequency distribution H is
H(f ) = X
FH(fj ): fj f In the following, we refer to the value H(fi) also as to Hi.
To quantify the degree of anomaly associated with a certain frequency, we use the area above and below the curve of the cumulated frequency distribution. Intuitively, the larger the area A"(fi) above the portion of the curve included from a certain frequency fi to the maximum frequency fmax, and the more fi di ers from frequencies that are greater than fi. Thus, this area is exploited to associate lower outlier score out#(fi) to the target frequecy fi. At the same time, the larger the area A#(fi) below the portion of the curve included from the minimum frequency fmin and a certain frequency fi, and the more fi di ers from frequencies that are smaller than fi. This area can be used to associate an uppper outlier score out"(fi) to fi.
The outlierness associated with the frequency fi is a combined measure of
the above two normalised areas and exceptional values for an attribute a, are
those associated with large values of outlierness. More details are available in[
7 f 1 2 3 4 5 6
7 f
It must be pointed out that very often a value emerges as exceptional for a certain attribute only when we restrict our attention to a subset of the whole population. This intuition leads to the de nition of the notion of explanationproperty pair. 10 -2
Scalability Dataset size (a) 7 Attributes 14 Attributes 22 Attributes
De nition 5. An explanation-property pair (E; p), consists of condition E, also called explanation, and of an atomic condition p = f(pa; pv)g, also called property. By pa (pv, resp.) we denote the attribute (value, resp.) involved in the atomic condition p.
The outlierness of an explanation-property pair (E; p) is the outlierness score associated with of the value pv with respect the attribute pa in the dataset DE .
We implemented an algorithm that receives in input a dataset D and a depth
parameter 1, and returns all the pairs (E; p) among those composed of at
most atomic conditions. The algorithm analyzes explanations of length less or
equal than according to a depth- rst strategy that allows an e cient selection
of sub-populations exploiting an approach similar to the one described in [
First of all, to study the applicability of our method to real datasets, we have
tested its scalability. Then, to clarify the di erent nature of our anomalies with
those returned by other outlier detection methods, we compared our method
with traditional distance-based and density-based outlier detection approaches
and with a method tailored for categorical data. Here, the results obtained on
the Mushrooms dataset (n = 8;124 objects and m = 22 attributes) from UCI
ML Repository are reported. More experiments are discussed in [
Scalability. In the experiment reported in Figure 2a, we varied the number of objects n in f500, 1000, 2000, 5000, 8000g and the number of attributes m in f7, 14, 22g , while the depth parameter has been held xed to = 3. The dashed lines represent the trend of the linear growth estimated exploiting regression. This estimation con rms that the algorithm scales linearly with respect to the dataset size. As for the number of attributes, as expected for a given number of objects the execution time increases due to the growth of the associated search space. On the full dataset the execution time is very contained, as it amounts to about 2 minutes. In the experiment reported in Figure 2b, we varied both the number of objects n and the depth parameter in f1; 2; 3; 4g, while considering the full feature space. Also in this case the linear growth is represented by the dashed lines, and similar considerations can be drawn.
Comparison with outlier detection methods. We compare our method
with two of the main categories of outliers: (i ) distance-based approaches, that
are used to discover global outliers; (ii ) density-based approaches, which are
able to single out local outliers. As distance-based de nition, we use the average
KNN score, representing the average distance from the k-nearest neighbours
of the object. As density-based, we use Local Outlier Factor or LOF [
We ranked the dataset objects o by assigning to each of the them the largest outlierness of a pair such that o 2 D and we determined our top{10 outliers as the objects associated with the largest outliernesses; then we computed their outlier scores according to the KNN, LOF and ROAD de nitions. Note that all the chosen competitors require an input parameter k whose selection may be challanging, so we have computeted their scores for all the possible values of k and report the ranking positions associated with our top{10 outliers as a box-plots generated when k changes.
Mushrooms: lower outliers
Mushrooms: lower outliers
Mushrooms: lower outliers
The plots in g. 3 highlight that the median ranking associated with our outliers can be far away from the top and also that, within the whole ranking distribution, the same outlier can be ranked in very di erent positions. In general, it seems that lower outliers are likely to be ranked better than upper outliers by our competitors, and this witnesses for the peculiar nature of upper outliers. On the Mushrooms dataset some of our lower outliers are, on the average, ranked very high also by the other algorithms. Some of them are almost 8000 7000 6000 irknag45000000 n F LO3000 2000 1000
0 8000 7000 6000 irkgann54000000 F LO3000 2000 1000 0 2000 1500 nagAD irkn1000 RO500
0 5500 5000 4500 4000 irkangnAD332055000000 O R2000 1500 1000 500 always top outliers for all methods (see the top 1st, 2nd, 5th, and 7th outliers) thus witnessing that these outliers have both global and local nature. However, most of our outliers are not detected by these techniques.
Note that, the best rankings associated with the selected objects are obtained for very di erent values of the parameter k. Since, the output of the KNN, LOF and ROAD methods are determined for a selected value of k, it is very unlike that, even in presence of some agreement between our top outliers and local and global outliers, they are simultaneously ranked in high positions for the same provided value of k. 6
In this work we have provided a contribution to single out and explain anomalous values in categorical domains. We perceive frequencies of attribute values as samples of a distribution whose density has to be estimated. This lead to the notion of frequency occurrence we exploit to build our de nition of outlier. As a second contribution, our technique is able to provide interpretable explanations for the abnormal values discovered. Thus, the outliers we provide can be seen as a product of the knowledge mined, making the approach knowledge-centric rather than object centric.