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

What are outliers?

An out-lier 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. 
 
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 out-lier.
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 expectation-maximization 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(Phase-1) and Iteration(Phase-2).
Initialization (Phase-1):
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 (Phase-2):
In the iteration phase, i.e. maximization (M) step, for each point labeled as non-out-lier, its label is exchanged with each of the k outliers and the entropy objective is re-evaluated. If the entropy decreases, the point’s non out-lier label is exchanged with the out-lier label of the point that achieved the new best value and the algorithm proceeds to the next object. When all non-out-lier 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:
  1. https://arxiv.org/ftp/cs/papers/0503/0503081.pdf 
  2. https://math.stackexchange.com/questions/219264/are-outliers-possible-with-categorical-data

Comments

Post a Comment

Popular posts from this blog

Designing Distributed File Storage Systems - Explained with Google File System(GFS) - Part 1

-
Image
Part 2: Replication-Explained: Designing Distributed systems Overview: Original paper: The Google File System Authors: Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung A distributed file system(DFS) is a file system that allows you to access files stored in multiple hosts distributed across them. In contrast to other data stores like MySQL or NoSQL which can also be made distributed, the data is DFS is stored in raw form and as files instead of a table or a fixed-document format. The use cases where DFS is used are very vast. From storing media content like Youtube videos to Instagram images to blogs like these, anything that can be stored as a file, is big and is not suitable to store in other data stores, DFS is generally a preferred choice for everyone. Key points to consider while designing a DFS: Understanding from the perspective of using a distributed file system, there are some characteristics that need to be considered while choosing the data store and tweaked according to
Read more

Automating the Machine Learning Workflow - AutoML

-
Motivation: Using Machine Learning will not require expert knowledge. All machine learning tasks follow the same basic flow. Difficult to find best fit hyper parameters. Hard to make hand made features. Fun. Automatic Machine Learning in progress: My motivation to write blog on this topic was Google's new project - AutoML . Google's AutoML project focuses on deep learning , a technique that involves passing data through layers of neural networks . Creating these layers is complicated, so Google’s idea was to create AI that could do it for them. There are many other open source projects, like AutoML and Auto-SKLEARN working towards a similar goal. Goal: The goal is to design the perfect machine learning “black box” capable of performing all model selection and hyper-parameter tuning without any human intervention.  AutoML draws on many disciplines of machine learning, prominently including Bayesian optimization - It is a sequential design strategy for gl
Read more

Replication Explained - Designing Distributed Systems (Part 2)

-
Image
For Part 1, check this out Designing Distributed File Storage Systems - Explained with Google File System(GFS) Overview: Replication in distributed systems involves the process in which we can have multiple copies of data at various locations to guard against unknown and random hardware failures, hence ensuring the availability of the system as a whole. While considering replication, we have to consider the basic assumption that machines will have uncorrelated failures , otherwise, replication will not help in any way. Replication should be considered or not, the number of replicas, etc all depends on the use case and the amount of inconvenience or how much it will cost you if you lose the data and compute power at a given point in time. Replication is achieved, intuitively , when we have two servers, one primary and a replica server, and we have to keep them in synchronize in a way if the primary server fails at any point in time, the replica server should have everything it needs t
Read more