Research Paper Summary  Detecting Outliers in Categorical Data
Original Paper: An Optimization Model for Outlier Detection in Categorical Data
Authors : Zengyou He, Xiaofei Xu, Shengchun Deng
Example:
Suppose you have 1000 people choose between apples and oranges. If 999 choose oranges and only one person chooses apple, I would say that that person is an outlier.
We use measurement as a way to detect anomalies. With categorical data you have to explain why choosing an apple is considered an anomaly (that data point does not behave as the rest 99.9% of the population).
Reference:
Authors : Zengyou He, Xiaofei Xu, Shengchun Deng
What are outliers?
An outlier is an observation that lies at an abnormal
distance from other values in a random sample from a population.
Before abnormal observations can be singled out, it is necessary to
characterize normal observations.
There
are many ways to detect outliers in continuous variables but there
exist only few techniques which can detect outliers in categorical
variables.
Suppose you have 1000 people choose between apples and oranges. If 999 choose oranges and only one person chooses apple, I would say that that person is an outlier.
We use measurement as a way to detect anomalies. With categorical data you have to explain why choosing an apple is considered an anomaly (that data point does not behave as the rest 99.9% of the population).
One technique
to detect outliers in categorical variables is using an optimization
model called Local Search Algorithm which is based on
expectationmaximization algorithm.
Local Search Algorithm
The Local Search Algorithm(LSA) takes number of desired
outlier's k as an input and iteratively improves the value of objective
function. The objective function here is the decrease in entropy after
removing the total 'k' number of outliers. The algorithm proceeds in two phases : Initialization(Phase1) and Iteration(Phase2).
Initialization (Phase1):
Initially, we randomly select k points and
label them as outliers. The Expectation (E) step here is to calculate
the decrease in entropy after removing the points labeled as
outliers.
Iteration (Phase2):
In the iteration phase, i.e. maximization (M) step, for
each point labeled as nonoutlier, its label is exchanged with each
of the k outliers and the entropy objective is reevaluated. If the
entropy decreases, the point’s non outlier label is exchanged with
the outlier label of the point that achieved the new best value and
the algorithm proceeds to the next object. When all nonoutlier
points have been checked for possible improvements, a sweep is
completed. If at least one label is exchanged in the sweep, we
initiate a new sweep. The algorithm terminates when a full sweep does
not change any labels, thereby indicating that a local optimum is
reached.
Reference:

https://arxiv.org/ftp/cs/papers/0503/0503081.pdf

https://math.stackexchange.com/questions/219264/areoutlierspossiblewithcategoricaldata
Comments
Post a Comment