c++ - 找到 vector 中所有值之间的相似距离并将它们子集化

Question

给定一个具有 double 值的 vector 。我想知道这个 vector 的任何元素之间的哪些距离彼此具有相似的距离。在最好的情况下，结果是原始值子集的 vector ，其中子集应至少有 n 个成员。

//given
vector<double> values = {1,2,3,4,8,10,12}; //with simple values as example

//some algorithm

//desired result as:
vector<vector<double> > subset;
//in case of above example I would expect some result like:
//subset[0] = {1,2,3,4}; //distance 1
//subset[1] = {8,10,12}; //distance 2
//subset[2] = {4,8,12}; // distance 4
//subset[3] = {2,4};    //also distance 2 but not connected with subset[1]
//subset[4] = {1,3};    //also distance 2 but not connected with subset[1] or subset[3]
//many others if n is just 2. If n is 3 (normally the minimum) these small subsets should be excluded.

这个例子被简化了，因为整数的距离可以迭代和测试 vector ，而 double 或 float 不是这种情况。

到目前为止我的想法

我想到了一些类似计算距离并将它们存储在 vector 中的方法。创建一个差分距离矩阵并对该矩阵进行阈值处理，以获得相似距离的一些容差。

//Calculate distances: result is a vector
vector<double> distances;
for (int i = 0; i < values.size(); i++)
    for (int j = 0; j < values.size(); j++)
    {
        if (i >= j)
            continue;
        distances.push_back(abs(values[i] - values[j]));
    }
//Calculate difference of these distances: result is a matrix
Mat DiffDistances = Mat::zero(Size(distances.size(), distances.size()), CV_32FC1);
for (int i = 0; i < distances.size(); i++)
    for (int j = 0; j < distances.size(); j++)
    {
        if (i >= j)
            continue;
        DiffDistances.at<float>(i,j) = abs(distances[i], distances[j]);
    }
//threshold this matrix with some tolerance in difference distances
threshold(DiffDistances, DiffDistances, maxDistTol, 255, CV_THRESH_BINARY_INV);
//get points with similar distances
vector<Points> DiffDistancePoints;
findNonZero(DiffDistances, DiffDistancePoints);

在这一点上，我无法找到与我的相似距离相对应的原始值。应该是可以找到的，但是追溯索引好像很复杂，不知道有没有更简单的方法解决这个问题。

Answer 1

这是一个有效的解决方案，只要没有分支意味着没有比 2*threshold 更接近的值。这是有效的相邻区域，因为如果我对@Phann 的理解正确的话，相邻键的差异应该小于阈值。

该解决方案绝对不是最快也不是最好的解决方案。但您可以将其用作起点:

#include <iostream>
#include <vector>
#include <algorithm>

int main(){
    std::vector< double > values = {1,2,3,4,8,10,12};
    const unsigned int nValues = values.size();
    std::vector< std::vector< double > > distanceMatrix(nValues - 1);
    // The distanceMatrix has a triangular shape
    // First vector contains all distances to value zero
    // Second row all distances to value one for larger values
    // nth row all distances to value n-1 except those already covered
    std::vector< std::vector< double > > similarDistanceSubsets;
    double threshold = 0.05;

    std::sort(values.begin(), values.end());

    for (unsigned int i = 0; i < nValues-1; ++i) {
        distanceMatrix.at(i).resize(nValues-i-1);
        for (unsigned j = i+1; j < nValues; ++j){
            distanceMatrix.at(i).at(j-i-1) = values.at(j) - values.at(i);
        }
    }

    for (unsigned int i = 0; i < nValues-1; ++i) {
        for (unsigned int j = i+1; j < nValues; ++j) {
            std::vector< double > thisSubset;
            double thisDist = distanceMatrix.at(i).at(j-i-1);

            // This distance already belongs to another cluster
            if (thisDist < 0) continue;

            double minDist  = thisDist - threshold;
            double maxDist  = thisDist + threshold;
            thisSubset.push_back(values.at(i));
            thisSubset.push_back(values.at(j));
            //Indicate that this is already clustered
            distanceMatrix.at(i).at(j-i-1) = -1;

            unsigned int lastIndex = j;
            for (unsigned int k = j+1; k < nValues; ++k) {
                thisDist = distanceMatrix.at(lastIndex).at(k-lastIndex-1);

                // This distance already belongs to another cluster
                if (thisDist < 0) continue;

                // Check if you found a new valid pair
                if ((thisDist > minDist) && (thisDist < maxDist)){
                    // Update the valid distance interval
                    minDist = thisDist - threshold;
                    minDist = thisDist - threshold;
                    // Add the newly found point
                    thisSubset.push_back(values.at(k));
                    // Indicate that this is already clustered
                    distanceMatrix.at(lastIndex).at(k-lastIndex-1) = -1;
                    // Continue the search from here 
                    lastIndex = k;
                }
            }
            if (thisSubset.size() > 2) {
                similarDistanceSubsets.push_back(thisSubset);
            }
        }
    }
    for (unsigned int i = 0; i < similarDistanceSubsets.size(); ++i) {
        for (unsigned int j = 0; j < similarDistanceSubsets.at(i).size(); ++j) {
            std::cout << similarDistanceSubsets.at(i).at(j);
            if (j != similarDistanceSubsets.at(i).size()-1) {
                std::cout << " ";
            }
            else {
                std::cout << std::endl;
            }
        }
    }
}

这个想法是预先计算距离，然后从最小和较大的邻居开始寻找每一对粒子，如果在它上面还有另一对有效粒子的话。如果是这样，这些都收集在一个子集中，并将其添加到子集 vector 中。对于每个新值，必须更新有效相邻区域以确保相邻距离的差异小于阈值。之后，程序继续处理下一个最小值及其较大的邻居，依此类推。