Difference between revisions of "Algorithms for Clustering data"

Revision as of 18:49, 25 February 2015

Introduction

Clustering refers to finding groups of objects such that the objects in a group will be similar (or related) to one another and different from (or unrelated to) the objects in other groups.

Kmeans algorithm:

| Kmeans is a flat clustering algorithm. It's an iterative algorithm, whose first step is to select k initial centroids (also called seeds), which are randomly selected data points. In the second step, k clusters are formed by assigning all points to their closest centroid, and the centroid of each cluster is recomputed. This is done iteratively until a stopping criterion is met (for example: the centroids don't change).

The closeness can be measured by various distance measurements, or similarity measurements or correlation. Different distance measurements were experimented for our case, and gave similar results. Thus, results were generated with Euclidean as the chosen distance measurement.

Another parameter to the kmeans algorithm is the number of clusters. Since our data is small (a matrix of size 39*49), we selected two as the number of clusters. The output of the kmeans clustering is validated with the domain knowledge and is shown to give meaningful results.

Anomaly Detection

A typical problem definition of anomaly detection is: Given a dataset D, find all the data points x belonging to D having the top-n largest anomaly scores calculated by a predetermined function f(x). It is associated with numerous challenges, such as:

• How does one define normal, and define deviations from it?
• How many outliers are there?
• How can anomalies be validated as either real or noise?
• How does one determine when all the anomalies have been caught?

Some of the application areas include credit card fraud detection, telecommunication fraud detection, network intrusion detection, fault detection.

The general steps for any anomaly detection algorithms include:

• Building a profile of the “normal” behavior. An example of a profile could be a pattern or a characteristic.
• Using the “normal” profile to detect anomalies. Anomalies are generally defined as data points, whose characteristics differ significantly from the rest of the data.

Some popular types of anomaly detection methods are:

• Graphical and Statistical-based
• Distance-based
• Model-based

Distance-based Method

In this method, data is represented as a vector of features. The three major approaches in this method include:

• Nearest-neighbor based
• Density based
• Clustering based

Nearest-Neighbor Based Approach

In the nearest-neighbor based approach, the distance of each data point with every other point is computed, and the outliers are define based on any chosen metric. Some metrics could be:

• Find points which have less than m neighboring points within a distance D.
• Find points whose distance to the kth nearest neighbor is greatest.
• Find points whose average distance to the k nearest neighbors is greatest.

Density-based: LOF approach

A research paper on the density-based LOF approach may be found here.

• For each point, compute the density of its local neighborhood.
• Compute local outlier factor (LOF) of a sample p as the average of the ratios of the density of sample p and the density of its nearest neighbors.
• Outliers are points with largest LOF value.

Clustering-Based

Parzen Window Density based

Non-classical Multidimensional Scaling (MDS)

Association Mining