18
$\begingroup$

tl;dr

  • What is the recommended way to deal with discrete data when performing anomaly detection?
  • What is the recommended way to deal with categorical data when performing anomaly detection?
  • This answer suggests using discrete data to just filter the results.
  • Perhaps replace the category value with the perctage chance of observation?

Intro

This is my first time posting on here, so please, if anything doesn't seem technically correct, either in the formatting, or the use of correct definitions, I'm interested to know what should've been used instead.

Onwards.

I've recently been taking part of the Machine Learning class by Andrew Ng

For anomaly detection we've been taught to determine what the Normal/Gaussian distribution parameters are for a given feature/variable, ${x_i}$ within a data set, and then determine the probability of a chosen set of training example's/observation's value given that particular Gaussian distribution, and then taking the product of the probabilities of the features.

Method

Choose $x_i$ features/variables that we think explain the activity in question: $$\{x_1, x_2,\dots,x_i\}$$

Fit the parameters of the Gaussian for each feature: $$\mu_j = \frac{1}{m}\sum_{i = 1}^m x_j^{(i)}$$ $$\sigma^2 = \frac{1}{m}\sum_{i = 1}^m (x_j^{(i)} - \mu_j)^2$$

For each training example, $x$, compute: $$p(x) = \prod_{j = 1}^n \ p(x_j; \mu_j, \sigma_j^2)$$

We then flag as an anomaly ($y = 1$), given: $$y = \left\{ \begin{array}{l l} 1 & \quad p(x) < \epsilon\\ 0 & \quad p(x) \geq \epsilon \end{array} \right.$$

This gives us the method with which to determine if an example requires further inspection.

My Question(s)

This seems fine for continuous variables/features, but discrete data is not addressed.

What about dummy variables, e.g. a gender flag feature, possibly called [IsMale] that can be of the value $0, 1$? To take a dummy feature into account would we use the binomial distribution instead to calculate $p(x)$?

What about categorical data such as car colour? While we could map colours to numerical values, e.g. $red \to 1, blue \to 2$, the distribution of such a categorical feature could be close to uniform (i.e. equally likely chance to be any of the colours), and further, as any numerical mapping that occurs (i.e. $red$ having the value $1$, etc) is not ordinal, does it make sense to try and transform any non-normal distribution of frequencies for colours to be normally distributed (does it even matter that it is not ordinal??)? For example, to me, it wouldn't make sense to do a $log()$ transform as the data is neither continuous nor ordinal. So perhaps it would be best to find a discrete distribution that fits the feature, as opposed to "torturing" the data to fit the Gaussian?

Questions: (updated: 2015-11-24)

  • Can binary variables be modeled with a binomial probability distribution and become another factor in the $p(x)$ calculation?
  • Should categorical variables should be modeled with a discrete probability distribution instead of a Gaussian, and become another factor in the $p(x)$ calculation?
  • Is there another method altogether that takes into account what I'm asking here that I can further research/learn about?
  • What is the recommended way to deal with discrete data when performing anomaly detection?
  • What is the recommended way to deal with categorical data when performing anomaly detection?

Edit: 2017-05-03

  • This answer suggests using discrete data to just filter the results.
  • Perhaps replace the category value with the perctage chance of observation?
$\endgroup$
  • $\begingroup$ <disclaimer> I'm someone with just enough stats background to be dangerous. </disclaimer> So lets get dangerous.... My intuition agrees with yours that the Gaussian isn't the way to handle non-continuous data. For continuous data one value on the number line has a different sort of relationship with all other values than does a number on an integer line, or a binary variable. Binomial distributions describe binary variables. Multinomial distributions describe multinomial variables. Aren't these all exponential family members? $\endgroup$ – EngrStudent - Reinstate Monica Jun 19 '13 at 13:30
  • $\begingroup$ Something to read: Handling Nominal Features in Anomaly Intrusion Detection Problems $\endgroup$ – Adrian Torrie Jun 28 '13 at 9:43
  • $\begingroup$ Another that may add to any discussion: Topic: categorical outliers? $\endgroup$ – Adrian Torrie Jun 28 '13 at 9:45
  • $\begingroup$ @iValueValue What is $p$ in your fourth formula? Is it $p(x;\mu,\sigma^2)=\frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{(x-\mu)^2}{2\sigma^2}}$? $\endgroup$ – Alessandro Jacopson Jul 26 '14 at 10:08
  • $\begingroup$ @uvts_cvs yes the probability density function of the gaussaian is what is used. $\endgroup$ – Adrian Torrie Aug 4 '14 at 3:51
4
$\begingroup$

In general, for both discrete* & categorical features, this method isn't particularly amenable to outlier analysis. Since there is no magnitude associated with categorical predictors, we are working with:

  • Frequency of the category being observed in the global data
  • Frequency of the category being observed within subspaces of the data

Note that neither of these qualities can be analyzed in isolation, as your Gaussian method requires. Instead, we need a method that contextualizes categorical features & considers the correlational nature of the data.

Here are some techniques for categorical & mixed attribute data, based on Outlier Analysis by Aggarwal:

  • If you can define a similarity function which builds a positive semidefinite matrix across all observations (regardless of data types), compute the similarity matrix $S$, find its diagonalization $S=Q_k\lambda_k^2Q_k^T$, and use the non-zero eigenvectors $Q_k$ to compute a feature embedding $E = Q_k\lambda_k$ . For each row (observation) in $E$, compute its distance from the centroid; this is your outlier score, and you can use univariate methods to determine outliers.
  • If you have purely categorical features, fit a mixture model to the raw categorical data. Anomalous points have lowest generative probability.
  • Use one-hot encoding for categorical predictors and optionally latent variable analysis** for ordinal variables with non-apparent continuous mappings
    • Standardize the non-one-hot features (one-hot features are already implicitly standardized) and perform Principal Component Analysis. Perform dimensionality reduction using the top principal components (or a soft PCA approach where eigenvectors are weighted by eigenvalues) and run a typical continuous outlier analysis method (e.g. a mixture model or your Gaussian method)
    • Perform an angle-based analysis. For each observation, compute cosine similarities between all pairs of points. Observations with the smallest variance of these similarities (known as the "Angle-Based Outlier Factor") are most likely outliers. May require a final analysis of the empirical distribution of ABOF to determine what is anomalous.
    • If you have labelled outliers: Fit a predictive model to the engineered data (logistic regression, SVM, etc.).

*Discrete features could possibly be handled approximately in your Gaussian method. Under the right conditions, a feature may be well approximated by a normal distribution (e.g. binomial random variable with npq > 3). If not, handle them as ordinals described above.

**This is similar to your idea of "replace the category value with the percentage chance of observation"

$\endgroup$
  • $\begingroup$ How do you fit a mixture model to the raw categorical data? Do you just have $K=1$? And it works for multiple categorical features? $\endgroup$ – Akababa Sep 19 '18 at 23:55
  • $\begingroup$ @Akababa You can, for example, compute MLEs on multinomial parameters using the EM algorithm. Assuming independence of the multinomial RVs, this approach generalizes to arbitrary categorical predictor sets. Example here $\endgroup$ – khol Sep 21 '18 at 0:24
0
$\begingroup$

Andrew Ng class math handles "discrete" data quite like it handles "non-discrete" data. All we have to do is empirically estimate normal distribution parameters, and it can be perfectly done for discrete data.

If you think about it, machine learning always deals with discrete data anyways: the number of data points is not infinite and the number of bits handled by computers is not infinite.

If discrete data points can be compared between each other then there is no fundamental difference for machine learning methods when dealing with, say, length: 1.15 ft 1.34 ft 3.4 ft

or how many branches are on the tree: 1 2 3 5

You can sum and average floating point or whole numbers just the same.

Now, to categorical data. Categorical data points cannot be compared {car vs motorcycle vs boat). How do we handle this?

The number of categories has to be at least two to make sense, otherwise what's the point in constant feature? In case of 2 categories, we can represent a category feature as a binary feature {0, 1}. 0 and 1 can be used for math, so see above.

If number of categories (K) is [3.. inf], we map our single feature to K binary mutually exclusive features . For example, "motorcycle" category becomes a combination of binary features { IsCar: 0, IsMotorcycle: 1, IsBoat: 0}, Boat point becomes { IsCar: 0, IsMotorcycle: 0, IsBoat: 1} and so on.

We can estimate empirical distribution parameters from these new features. We will simply have more dimensions, that's all.

$\endgroup$
  • 1
    $\begingroup$ This is explaining dummy encoding but that's not an answer to the question $\endgroup$ – Pieter Aug 7 '17 at 6:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.