using System;
using System.Collections.Generic;
///
/// Contains an implementation of the DBSCAN algorithm. This class cannot be inherited.
///
public class DbscanAlgorithm
{
#region constructors
private DbscanAlgorithm()
{
}
#endregion
#region methods
///
/// Clusters the specified points using the specified value and minimum points to form a cluster.
///
/// The points to cluster.
/// The value to use to find neighoring points.
/// The minimum number of points to form a cluster.
/// The number of clusters created from the collection.
public static int Dbscan(IDbscanPoint[] points, double eps, int minimumClusterCount)
{
int cid = 0;
foreach (IDbscanPoint p in points)
{
if (!p.IsVisited)
{
p.IsVisited = true;
IDbscanPoint[] neighbors = DbscanAlgorithm.GetNeighors(points, p, eps);
if (neighbors.Length < minimumClusterCount)
p.IsNoise = true;
else
{
cid++;
DbscanAlgorithm.ExpandCluster(points, p, neighbors, cid, eps, minimumClusterCount);
}
}
}
return cid;
}
private static void ExpandCluster(IDbscanPoint[] points, IDbscanPoint p, IDbscanPoint[] neighbors, int cid, double eps, int minimumClusterCount)
{
p.ClusterId = cid;
Queue> q = new Queue>(neighbors);
while (q.Count > 0)
{
IDbscanPoint n = q.Dequeue();
if (!n.IsVisited)
{
n.IsVisited = true;
IDbscanPoint[] ns = DbscanAlgorithm.GetNeighors(points, n, eps);
if (ns.Length >= minimumClusterCount)
foreach (IDbscanPoint item in ns)
q.Enqueue(item);
}
else if (!n.ClusterId.HasValue)
n.ClusterId = cid;
}
}
private static IDbscanPoint[] GetNeighors(IDbscanPoint[] points, IDbscanPoint point, double eps)
{
List> neighbors = new List>();
neighbors.Add(point);
foreach (IDbscanPoint p in points)
if (point.IsNeighbor(p, eps))
neighbors.Add(p);
return neighbors.ToArray();
}
#endregion
}
///
/// Contains an implementation of the interface
/// using types for the X and Y components.
///
[System.Diagnostics.DebuggerDisplay(@"\{X={X}, Y={Y}\}")]
public class DbscanPoint : IDbscanPoint
{
#region properties
///
/// Gets or sets the X component of the point.
///
public double X { get; set; }
///
/// Gets or sets the Y component of the point.
///
public double Y { get; set; }
///
/// Gets or sets a value indicating whether the point is noise.
///
public bool IsNoise { get; set; }
///
/// Gets or sets a value indicating whether the point was visited.
///
public bool IsVisited { get; set; }
///
/// Gets or sets a value indicating the cluster id.
///
public int? ClusterId { get; set; }
#endregion
#region constructors
///
/// Initializes a new instance of the class.
///
public DbscanPoint()
{
}
///
/// Initializes a new instance of the class with the specified values.
///
/// The X component of the point.
/// The Y component of the point.
public DbscanPoint(double x, double y)
{
this.X = x;
this.Y = y;
}
#endregion
#region methods
///
/// Determines whether the specified point neighbors the current instance using the specified value.
///
/// The point to test as a neighor.
/// The value to use to find neighoring points.
/// True if the point is a neighbor; otherwise, false.
public bool IsNeighbor(IDbscanPoint point, double eps)
{
return (Math.Pow(point.X - this.X, 2) + Math.Pow(point.Y - this.Y, 2) < Math.Pow(eps, 2));
}
#endregion
}
///
/// Contains the functionality an object requires to perform a DBSCAN.
///
public interface IDbscanPoint
{
#region properties
///
/// Gets or sets the X component of the point.
///
XType X { get; set; }
///
/// Gets or sets the Y component of the point.
///
YType Y { get; set; }
///
/// Gets or sets a value indicating whether the point is noise.
///
bool IsNoise { get; set; }
///
/// Gets or sets a value indicating whether the point was visited.
///
bool IsVisited { get; set; }
///
/// Gets or sets a value indicating the cluster id.
///
int? ClusterId { get; set; }
#endregion
#region methods
///
/// Determines whether the specified point neighbors the current instance using the specified value.
///
/// The point to test as a neighor.
/// The value to use to find neighoring points.
/// True if the point is a neighbor; otherwise, false.
bool IsNeighbor(IDbscanPoint point, double eps);
#endregion
}