Реализация быстрого DBSCAN в C#

Question

Я пытался реализовать DBSCAN в C#, используя kd-деревья. Я следил за реализацией: http://www.yzuzun.com/2015/07/dbscan-clustering-algorithm-and-c-implementation/

public class DBSCANAlgorithm
{
    private readonly Func<PointD, PointD, double> _metricFunc;


    public DBSCANAlgorithm(Func<PointD, PointD, double> metricFunc)
    {
        _metricFunc = metricFunc;
    }

    public void ComputeClusterDbscan(ScanPoint[] allPoints, double epsilon, int minPts, out HashSet<ScanPoint[]> clusters)
    {
        clusters = null;
        var allPointsDbscan = allPoints.Select(x => new DbscanPoint(x)).ToArray();

        var tree = new KDTree.KDTree<DbscanPoint>(2);
        for (var i = 0; i < allPointsDbscan.Length; ++i)
        {
            tree.AddPoint(new double[] { allPointsDbscan[i].ClusterPoint.point.X, allPointsDbscan[i].ClusterPoint.point.Y }, allPointsDbscan[i]);
        }

        var C = 0;
        for (int i = 0; i < allPointsDbscan.Length; i++)
        {
            var p = allPointsDbscan[i];
            if (p.IsVisited)
                continue;
            p.IsVisited = true;

            DbscanPoint[] neighborPts = null;
            RegionQuery(tree, p.ClusterPoint.point, epsilon, out neighborPts);
            if (neighborPts.Length < minPts)
                p.ClusterId = (int)ClusterIds.NOISE;
            else
            {
                C++;
                ExpandCluster(tree, p, neighborPts, C, epsilon, minPts);
            }
        }
        clusters = new HashSet<ScanPoint[]>(
            allPointsDbscan
                .Where(x => x.ClusterId > 0)
                .GroupBy(x => x.ClusterId)
                .Select(x => x.Select(y => y.ClusterPoint).ToArray())
            );

        return;
    }

    private void ExpandCluster(KDTree.KDTree<DbscanPoint> tree, DbscanPoint p, DbscanPoint[] neighborPts, int c, double epsilon, int minPts)
    {
        p.ClusterId = c;
        for (int i = 0; i < neighborPts.Length; i++)
        {
            var pn = neighborPts[i];
            if (!pn.IsVisited)
            {
                pn.IsVisited = true;
                DbscanPoint[] neighborPts2 = null;
                RegionQuery(tree, pn.ClusterPoint.point, epsilon, out neighborPts2);
                if (neighborPts2.Length >= minPts)
                {
                    neighborPts = neighborPts.Union(neighborPts2).ToArray();
                }
            }
            if (pn.ClusterId == (int)ClusterIds.UNCLASSIFIED)
                pn.ClusterId = c;
        }
    }

    private void RegionQuery(KDTree.KDTree<DbscanPoint> tree, PointD p, double epsilon, out DbscanPoint[] neighborPts)
    {
        int totalCount = 0;
        var pIter = tree.NearestNeighbors(new double[] { p.X, p.Y }, 10, epsilon);
        while (pIter.MoveNext())
        {
            totalCount++;
        }
        neighborPts = new DbscanPoint[totalCount];
        int currCount = 0;
        pIter.Reset();
        while (pIter.MoveNext())
        {
            neighborPts[currCount] = pIter.Current;
            currCount++;
        }

        return;
    }
}

//Dbscan clustering identifiers
public enum ClusterIds
{
    UNCLASSIFIED = 0,
    NOISE = -1
}

//Point container for Dbscan clustering
public class DbscanPoint
{
    public bool IsVisited;
    public ScanPoint ClusterPoint;
    public int ClusterId;

    public DbscanPoint(ScanPoint point)
    {
        ClusterPoint = point;
        IsVisited = false;
        ClusterId = (int)ClusterIds.UNCLASSIFIED;
    }
}

и модифицируя regionQuery(P, eps) вызвать функцию ближайшего соседа kd-дерева. Для этого я использовал kd-sharp библиотека для C#, которая является одной из самых быстрых реализаций дерева kd.

Тем не менее, когда дан набор данных около 20000 2d точек, его производительность составляет около 40 с, по сравнению с scikit-learn Реализация DBSCAN на python, которая имеет те же параметры, занимает около 2 секунд.

Поскольку этот алгоритм предназначен для программы на C#, которую я пишу, я застрял на C#. Таким образом, я хотел бы узнать, что я все еще упускаю с точки зрения оптимизации алгоритма?