Как использовать широту / долготу для кластеризации на основе плотности в алгоритме OPTICS

Question

Я хочу кластеризовать твиты на основе долготы и широты и работать с алгоритмом OPTICS (реализация Java), так как это кажется лучшим выбором для кластеризации на основе плотности. Алгоритм принимает входной файл для точек, которые необходимо учитывать. Каждый из этих файлов является вектором. Набор данных, который у меня есть, содержит широту и долготу твитов. Могу ли я использовать широту и долготу напрямую для извлечения кластера или мне нужно преобразовать широту и долготу в какую-то другую форму, прежде чем я смогу использовать их для кластеризации с использованием OPTICS.

Заранее спасибо.

Пример входного файла, который у меня есть:

37.3456227 -121.8847222
37.3904943 -121.8854337
37.2589827 -121.8847222
37.3558627 -121.8505679
37.3189149 -121.9416226
37.3052272 -121.9871217
37.3716914 -121.8619539
37.2876164 -121.9857002
37.2876164 -121.9857002
37.2876164 -121.9857002
37.2876164 -121.9857002
37.2876164 -121.9857002
37.2876164 -121.9857002
37.2876164 -121.9857002
37.2876164 -121.9857002
37.2876164 -121.9857002

Фрагмент кода алгоритма ОПТИКА:

/**
     * Run the OPTICS algorithm
     * 
     * @param inputFile
     *            an input file path containing a list of vectors of double
     *            values
     * @param minPts
     *            the minimum number of points (see DBScan article)
     * @param epsilon
     *            the epsilon distance (see DBScan article)
     * @param seaparator
     *            the string that is used to separate double values on each line
     *            of the input file (default: single space)
     * @return a list of clusters (some of them may be empty)
     * @throws IOException
     *             exception if an error while writing the file occurs
     */
    public List<DoubleArrayOPTICS> computerClusterOrdering(String inputFile,
            int minPts, double epsilon, String separator)
            throws NumberFormatException, IOException {

        // record the start time
        timeExtractClusterOrdering = 0;
        long startTimestampClusterOrdering = System.currentTimeMillis();

        // Structure to store the vectors from the file
        List<DoubleArray> points = new ArrayList<DoubleArray>();

        // read the vectors from the input file
        BufferedReader reader = new BufferedReader(new FileReader(inputFile));
        String line;
        // for each line until the end of the file
        while (((line = reader.readLine()) != null)) {
            // if the line is a comment, is empty or is a
            // kind of metadata
            if (line.isEmpty() == true || line.charAt(0) == '#'
                    || line.charAt(0) == '%' || line.charAt(0) == '@') {
                continue;
            }
            line = line.trim();
            // split the line by spaces
            String[] lineSplited = line.split(separator);
            // create a vector of double
            double[] vector = new double[lineSplited.length];
            // for each value of the current line
            for (int i = 0; i < lineSplited.length; i++) {
                // convert to double
                double value = Double.parseDouble(lineSplited[i]);
                // add the value to the current vector
                vector[i] = value;
            }
            // add the vector to the list of vectors
            points.add(new DoubleArrayOPTICS(vector));
        }
        // close the file
        reader.close();

        // build kd-tree
        kdtree = new KDTree();
        kdtree.buildtree(points);

        // For debugging, you can print the KD-Tree by uncommenting the
        // following line:
        // System.out.println(kdtree.toString());

        // Variable to store the order of points generated by OPTICS
        clusterOrdering = new ArrayList<DoubleArrayOPTICS>();

        // For each point in the dataset
        for (DoubleArray point : points) {
            // if the node is already visited, we skip it
            DoubleArrayOPTICS pointDBS = (DoubleArrayOPTICS) point;
            if (pointDBS.visited == false) {
                // process this point
                expandClusterOrder(pointDBS, clusterOrdering, epsilon, minPts);
            }
        }

        // check memory usage
        MemoryLogger.getInstance().checkMemory();

        // record end time
        timeExtractClusterOrdering = System.currentTimeMillis()
                - startTimestampClusterOrdering;

        kdtree = null;

        // return the clusters
        return clusterOrdering;
    }

Answer 1

Стандартная реализация OPTICS в среде ELKI очень хорошо работает на расстоянии большого круга. Так что да, это возможно.

Смотрите, например, этот ответ для деталей:

Как индексировать с помощью ELKI - OPTICS кластеризация

Эта реализация также поддерживает индексы и является действительно быстрой.