Изменение алгоритма DBSCAN

Я пытаюсь настроить алгоритм DBSCAN так, чтобы он также запускал новый кластер, если расстояние между двумя точками только в направлении x больше некоторого числа, или если расстояние между двумя точками только в направлении Y больше некоторого числа. Тем не менее, у меня есть некоторые проблемы с этим.

Вот мой код:

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

        int clusterId = 0;
        for (int i = 0; i < allPointsDbscan.Length - 1 ; i++)
        {
            int j = i + 1;
            DbscanPoint p = allPointsDbscan[i];
            if (p.IsVisited)
                continue;
            p.IsVisited = true;
            DbscanPoint[] neighborPts = null;
            RegionQuery(allPointsDbscan, p.ClusterPoint, epsilon, out neighborPts);

            //calculate distance between points in x and y directions
            double xDirection = Math.Abs(allPointsDbscan[j].ClusterPoint.X - allPointsDbscan[i].ClusterPoint.X);
            double yDirection = Math.Abs(allPointsDbscan[j].ClusterPoint.Y - allPointsDbscan[i].ClusterPoint.Y);
            if (xDirection > 0.299 | yDirection > 0.199)
            {
                //begin new cluster
            }

            if (neighborPts.Length < minPts)
                p.ClusterId = (int)ClusterIds.Noise;
            else
            {
                clusterId++;
                ExpandCluster(allPointsDbscan, p, neighborPts, clusterId, epsilon, minPts);
            }
        }
        clusters = new HashSet<DatasetItem[]>(
            allPointsDbscan
                .Where(x => x.ClusterId > 0)
                .GroupBy(x => x.ClusterId)
                .Select(x => x.Select(y => y.ClusterPoint).ToArray())
            );
    }

person John    schedule 04.12.2015    source источник
comment
Этот вопрос устарел, поэтому, надеюсь, вы решили проблему. Но вам нужно добавить сравнение dx и dy в функцию RegionQuery, а не в функцию ComputeClusterDbScan. RegionQuery определяет, может ли какая-либо данная точка принадлежать переданному кластеру точек. Он делает это, добавляя каждую точку в список соседей, когда она отвечает всем критериям для того, чтобы считаться соседом. В вашем случае, в дополнение к необходимости находиться в пределах указанного расстояния эпсилон, вы дополнительно проверите, что каждая точка находится в пределах проективных расстояний x/y. Если нет, не добавляйте в список соседей.   -  person Dunk    schedule 08.09.2016


Ответы (1)


Вам не нужно модифицировать DBSCAN для этого.

Три решения:

  1. Масштабируйте набор данных так, чтобы пороговые значения x и y были сопоставимы друг с другом, а затем используйте максимальную норму. т.е. если у вас есть eps_x и eps_y, умножьте координаты x на 1/eps_x, координаты y на 1/eps_y, а затем используйте eps=1 с максимальной нормой.
  2. Использовать взвешенную максимальную норму
  3. Используйте обобщенный DBSCAN. Например. в реализации ELKI легко добавить новый предикат соседа, который имеет два параметра эпсилон. Возьмем Intersection(neighbors_x, Neighbours_y) в качестве соседства.

По сути, все эти подходы изменяют результат «regionQuery».

person Has QUIT--Anony-Mousse    schedule 05.12.2015
comment
Ни одно из этих решений не решает мою проблему. Масштабировать точно не получится, т.к. я проверяю расстояния; и уменьшение масштаба данных даст мне только ложные срабатывания. - person John; 08.12.2015
comment
Вы должны масштабировать данные точно, чтобы они соответствовали желаемым пороговым значениям. Я не говорю о нормализации их до [0;1]. Поверьте мне, все три из них будут работать, если все сделано правильно. - person Has QUIT--Anony-Mousse; 09.12.2015
comment
Извините, я не понимаю, что вы имеете в виду; Пожалуйста, покажите мне. - person John; 12.12.2015
comment
Чтобы разместить вес w на оси x, умножьте x на w. Чтобы поместить вес u на ось y, умножьте y на u! - person Has QUIT--Anony-Mousse; 14.12.2015
comment
лол, я прекрасно понимаю, как использовать скалярные множители, но это НЕ поможет мне с моим набором данных. Пожалуйста, имейте в виду, я хочу знать, больше ли расстояние (только в направлении x, чем какое-то число по моему выбору... скажем, 0,5) ИЛИ если расстояние (только в направлении y больше, чем, скажем, 1,5). И если он больше, в любом направлении, то запустите новый кластер. В этом случае масштабирование не поможет... оно только разорвет мои данные, когда я попытаюсь вычислить расстояния. - person John; 17.12.2015
comment
Вот для чего предназначена а) максимальная норма или б) GDBSCAN, если бы вы прочитали весь мой ответ. И не пытайся доказать, что я ошибаюсь, когда я пытаюсь тебе помочь. - person Has QUIT--Anony-Mousse; 17.12.2015
comment
Кроме того, имейте в виду, когда я говорю расстояние, оно строго одномерно... иначе x2 - x1 = расстояние между точками в направлении x, y2 - y1 = расстояние между точками в направлении y. В качестве примечания; Я также использую OxyPlot для просмотра своих данных. У меня есть алгоритм DBScan, помогающий мне раскрашивать кластеры, когда они проходят через алгоритм. И это не кластеризация со слишком хорошей точностью, поэтому я хочу реализовать этот дополнительный уровень проверки, так сказать... и определить, следует ли запускать новый кластер. - person John; 17.12.2015
comment
Пожалуйста, поймите, я бы хотел, чтобы вы были правы. - person John; 17.12.2015
comment
Не знаю... может я чего-то не понимаю. В своем решении вы говорите, что используйте eps=1 с максимальной нормой. Зачем использовать eps=1? и что именно вы имеете в виду под макс. норма? - person John; 17.12.2015
comment
Я не использую Java... ELKI не подходит. - person John; 17.12.2015