标签: distance-matrix

简介:首先,作为介绍,我很自豪地在StackOverflow上提出我的第一个问题.我希望我能帮助别人,就像他们帮助我一样.

算法:

我正在用CUDA编写一个程序,问题如下:

• 两个矩阵A(n*128)和B(m*128)

• 我取A的第一行,然后逐个计算该向量与B的所有行之间的距离.

• 我在矩阵C的一行上写出每个距离的结果,因此C的元素C(i,j)包含A的行i和B的行j之间的距离.

• 然后我继续下一行A.

我用这种方式实现了它:我有一个由(n*m)个块组成的网格,每个块有128个线程.(1*128).

问题:程序成功运行并带有预期结果,但执行时间仅比单线程CPU版本快5到10倍.所以我想知道如何在减少之前增加每个线程的工作量以提高性能.

内核代码(原始:未优化)

 __global__ void EuclideanDistances( float *A, float *B , float *C , int n , int m)
{
    // SIZE is equal to 128
__shared__ float accumResult[SIZE];
float sA;
float sB;

    // MAPPING
int bx = blockIdx.x;  // n
int by = blockIdx.y;  // m
int ty = threadIdx.y; // 128
int tx = threadIdx.x; // 1


sA = A [bx * SIZE + ty];
sB …

我的代码中的瓶颈是我计算成对距离矩阵的区域.由于这是迄今为止最慢的部分,我花了很多时间来加速我的代码.

我发现许多加速在线使用文章,但收益微乎其微.所以,我正在寻找一种方法来使用我的GPU创建距离矩阵,以进一步加快速度.但是,我对使用GPU进行计算知之甚少. 任何人都可以帮我这样做吗？

在我的研究中,我发现了以下内容,但没有一个使用GPU:

1. 这篇文章很有用,但加速很少.
2. 这篇文章提供了有关如何使用cython和numba的信息.

以下是如何计算成对距离矩阵的示例摘录:

import numpy as np
from scipy import spatial

rows = 1000
cols = 10
mat = np.random.randn(rows, cols)
d_mat = spatial.distance.cdist(mat, mat)

我的显卡是Nvidia Quadro M2000M

我已经尝试过对样本进行配对,但是它需要大量的内存,因为100个样本会导致9900个样本的成本更高.什么是在火花中分布式环境中计算距离矩阵的更有效方法

这是我正在尝试的伪代码片段

val input = (sc.textFile("AirPassengers.csv",(numPartitions/2)))
val i = input.map(s => (Vectors.dense(s.split(',').map(_.toDouble))))
val indexed = i.zipWithIndex()                                                                       //Including the index of each sample
val indexedData = indexed.map{case (k,v) => (v,k)}

val pairedSamples = indexedData.cartesian(indexedData)

val filteredSamples = pairedSamples.filter{ case (x,y) =>
(x._1.toInt > y._1.toInt)  //to consider only the upper or lower trainagle
 }
filteredSamples.cache
filteredSamples.count

上面的代码创建了对,但即使我的数据集包含100个样本,通过配对filteredSamples(上面)会产生4950样本,这对于大数据来说可能非常昂贵

我正在开发我的第一个Cuda应用程序,并且我的内核具有"低于预期的吞吐量",这似乎是目前最大的瓶颈.

内核的任务是计算N×N大小的矩阵(DD),其包含数据矩阵上所有元素之间的平方距离.数据矩阵(Y)的大小为N×D(支持多维数据)并存储为行主要.

资源:

__global__ void computeSquaredEuclideanDistance(const float * __restrict__ Y, float * __restrict__ DD, const int N, const int D) {
    int index = blockIdx.x * blockDim.x + threadIdx.x;
    int stride = blockDim.x * gridDim.x;

    for (int i = index; i < N * N; i += stride) {
        const int m = i / N;
        const int n = i % N;
        float tmp = 0;
        for (int d = 0; d < D; ++d) …

是否有可能转换的邻接矩阵所定义的一和零的 这里为距离矩阵所定义的在这里 ，其中每个链路将是单位长度1的？

我想对地理数据进行聚类，以对我所在区域内的景观类型进行分类。

我的数据由规则网格每个字段的五个变量（温度、温度幅度、降水量、海拔和土壤类型）组成。我有超过 100 万个字段（=数据框中的行）。

其中四个变量是数字，土壤类型是用数字描述的分类变量。（数值数据已经标准化。）我决定计算高尔距离相异矩阵，并在此矩阵上执行 PCA 和层次聚类。然而，数据太大了。

   SOIL  PREC     TEMP     ALT      AMP
0  6     1.000    1.146    0.157   -0.579
1  6     0.948    1.224    0.154   -0.579
2  5     1.000    1.146    0.201   -0.662
3  6     1.078    1.093    0.177   -0.620
4  6     1.000    1.146    0.182   -0.620
5  6     1.000    1.146    0.186   -0.599

我不想采样，因为变量是梯度的。我尝试计算频率并对较小的数据执行高尔距离，但它仍然太大。

我想我可能（1）手动对大数据集进行分块，（2）向每个分块矩阵添加两行额外的行，其中变量的最大值和最小值作为距离分析的每个变量范围的“描述”，（3）使用gower.dist函数计算每个块的相异矩阵，(4) 删除多余的行，(5) 将所有块相异矩阵合并为一个大相异矩阵。

您认为这是正确且可行的方式吗？您对如何处理这个问题还有其他建议吗？

对相异矩阵进行 PCA 是否正确？

我dist在 R 中使用了该函数，我想知道它的时间复杂度。

我知道层次聚类有N^2*logN时间复杂度。层次聚类由两部分组成，R中代码如下：

> d <- dist(as.matrix(mtcars))   # find distance matrix 
> hc <- hclust(d)                # apply hirarchical clustering 
> plot(hc)                       # plot the dendrogram

在应用层次聚类之前，需要计算距离矩阵。我认为这需要N^2复杂性？

我找到了一个 R 包Rlof，它使用多线程来计算距离矩阵，它做得很好。

但是，该函数的输出distmc是向量而不是矩阵。应用as.matrix到这个“dist”对象比距离的多线程计算要昂贵得多。

查看函数 help，打印对角线和上三角形的选项在那里，但我不明白应该在哪里使用它们。

有没有办法as.matrix以某种方式节省时间？

可重现的例子：

set.seed(42)
M1 = matrix(rnorm(15000*20), nrow = 15000, ncol =20)
system.time({dA = distmc(M1, method = "euclidean", diag = TRUE,
                         upper = TRUE, p = 2)})
system.time(A = as.matrix(dA))

我有一个 csv 文件，其中包含 2000 多个农场的坐标位置列表，结构如下；

FarmID | Latidue | Longitude |  
------ |---------|-----------|  
   1   |    y1   |     x1    |
   2   |    y2   |     x2    |
   3   |    y3   |     x3    |

....... 我想从这个数据中创建一个欧几里得距离矩阵，显示所有农场对之间的距离，所以我得到一个结果矩阵，如：

     1     |    2    |     3     |
-----------|---------|-----------|
1    0     |  2.236  |   3.162   |
2  2.236   |    0    |   2.236   |
3  3.162   |  2.236  |     0     |

有了更多的农场和数据框中的坐标，我需要能够以某种方式迭代所有农场对并创建一个像上面那样的距离矩阵。任何有关如何在 R 中执行此操作的帮助将不胜感激。谢谢！

在 R 中，我有一个 data.frame 显示节点对之间的距离：

dl <- data.frame(
  a = c('a','a','a','b','b','c'),
  b = c('b','c','d','c','d','d'),
  dist = c(1,2,3,2,1,2)
)

我想将其转换为距离矩阵，对角线设置为零，上三角形设置为 NA，因为距离是对称的：

dm <- data.frame(
  a = c(0,2,3,2),
  b = c(NA, 0, 2, 1),
  c = c(NA, NA, 0, 2),
  d = c(NA, NA, NA, 0),
  row.names = c('a','b','c','d')
) %>% as.matrix()

我的真实数据非常大，所以计算效率是关键。我自己能想到的唯一解决方案涉及循环或使用igraph首先将列表转换为图形，然后将该图形转换为矩阵，考虑到我的数据大小，这并不是非常理想。输入是一个 data.frame，因为节点 ID 是文本，而距离是数字，并且所需的输出是一个矩阵，因为速度是关键。

我想知道如何从距离矩阵中提取第一个对角线的值.

例如:

> mymatrix
     [,1] [,2]
[1,]    1    2
[2,]    3    4
[3,]    6    4
[4,]    8    6

> dist(mymatrix)

         1        2        3
2 2.828427                  
3 5.385165 3.000000         
4 8.062258 5.385165 2.828427

我想在向量中得到值: 2.828427, 3.000000, 2.828427

谢谢!

在 https://www.npmjs.com/package/google-distance-matrix 示例中,我们可以添加多个destincation作为latlong对,

服务器端代码就像

string Test = "http://maps.googleapis.com/maps/api/distancematrix/json?origins=Lat1,long1&destinations=Lat2,long2&sensor=false"

现在问题是如何在多个原始目标模式中使用它我们可以像

string Test = "http://maps.googleapis.com/maps/api/distancematrix/json?origins=Lat1,long1,lat2,long2&destinations=Lat3,long3,Lat4,long4&sensor=false"

例

http://maps.googleapis.com/maps/api/distancematrix/json?origins=23.020284,72.4396566&destinations=22.3039702,70.7671403&sensor=false http://maps.googleapis.com/maps/api/distancematrix/json?origins = 23.027100,72.508000&目的地= 22.999500,72.600300&传感器=假

这两个组合

http://maps.googleapis.com/maps/api/distancematrix/json?origins=23.020284,72.4396566,23.027100,72.508000&destinations=22.3039702,70.7671403,22.999500,72.600300&sensor=false