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 }