XdCxRhDW54/Service/CgDbScan/DBSCAN.cs

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CheckServer
{
    public class DBSCAN
    {
        private double eps;
        private int minPts;
        private List<double[]> dataset;
        bool[] visited;

        /// <summary>
        /// 
        /// </summary>
        /// <param name="eps">邻域半径</param>
        /// <param name="minPts">邻域内最小点数</param>
        /// <param name="dataset">数据集</param>
        public DBSCAN(double eps, int minPts, List<double[]> dataset)
        {
            this.eps = eps;
            this.minPts = minPts;
            this.dataset = dataset;
        }
        public List<int> Run()
        {
            int n = dataset.Count;
            visited = new bool[n];
            List<int> cluster = new List<int>();
            for (int i = 0; i < n; i++)
            {
                if (!visited[i])
                {
                    List<int> neighbors = RegionQuery(i);
                    if (neighbors.Count < minPts)
                    {
                        visited[i] = true;
                    }
                    else
                    {
                        cluster.Add(ExpandCluster(i, neighbors));
                    }
                }
            }
            return cluster;
        }
        //查询给定点邻域内所有点
        private List<int> RegionQuery(int i)
        {
            List<int> neighbors = new List<int>();
            for (int j = 0; j < dataset.Count; j++)
            {
                if (i != j && Distance(dataset[i], dataset[j]) <= eps)
                {
                    neighbors.Add(j);
                }
            }
            return neighbors;
        }
        //扩展簇
        private int ExpandCluster(int i, List<int> neighbors)
        {
            int clusterId = i;
            visited[i] = true;
            List<int> seeds = new List<int>(neighbors);
            while (seeds.Count > 0)
            {
                int current = seeds[0];
                seeds.RemoveAt(0);
                List<int> currentNeighbors = RegionQuery(current);
                if (currentNeighbors.Count >= minPts)
                {
                    foreach (var neighbor in currentNeighbors)
                    {
                        if (!visited[neighbor])
                        {
                            seeds.Add(neighbor);
                        }
                    }
                }
                if (!visited[current])
                {
                    visited[current] = true;
                    clusterId = current;
                }

            }
            return clusterId;
        }
        private double Distance(double[] a, double[] b)
        {
            double sum = 0;
            for (int i = 0; i < a.Length; i++)
            {
                sum += Math.Pow(a[i] - b[i], 2);
            }
            return Math.Sqrt(sum);
        }
    }
}