如何加速图数据集中边间权重和的计算

Question

版本：

• Python 3.10.8
• 麻木 1.22.3

我目前正在尝试从“Sadrfaridpour、Ehsan、Talayeh Razzaghi 和 Ilya Safro”实施代数多重网格粗化。“设计快速多级支持向量机。”机器学习 108 (2019)：1879-1917。在 python 中。

我有一个当前表示为图形的数据集，每个点在它和它的 10 个最近邻居之间都有一条边。

我有一个被认为“重要”的要点列表。确定哪些点是重要的有两个步骤，在我的程序的这一步我已经完成了第一步并计算了“主要”重要点。我现在想继续第二步并计算“次要”重要点，这需要计算数据框中每个点与任何重要点之间的权重总和。

例如，我确定以下几点是“重要的”：

importantPoints = [2, 567, 81]

我还有两个 numpy 数组：它们的形状都是 (n*10) 矩阵，所以每一行代表数据集中的一个点，每一列都是它的 K 近邻。

Neighbor Matrix 具有作为邻居的每个点的索引：

邻居矩阵：

邻居1	邻居 2	邻居 3	----
81点	第 3 点	256点
第 1 点	第 56 点	点427

权重矩阵由每个相邻点之间的边上的权重组成，因此例如第 0 行第 1 列将是点 0 和它最近的邻居之间的边的权重。

权重矩阵：

邻居1	邻居 2	邻居 3	----
0.99	0.5	0.38
0.87	0.56	0.22

我尝试做的是以下内容：

 for i in range(KNeighbors.shape[0])
    neighbors = np.argwhere(np.isin(KNeighbors[i], importantPoints)).ravel()
    sumWeights = np.take(Weights[i], neighbors).sum()

在上面的代码中，我首先测试重要的点是否在邻居列表中，使用“argwhere”找到这些点所在的索引，然后在权重矩阵中找到相应的权重并将它们相加。这段代码有效，但它太慢了。

我研究过向量化代码，但问题是在对权重求和后我对值执行计算以查看当前点是否应添加到“importantPoints”列表中，这意味着该点将是用于下一次 sumWeights 的计算。

我确定这不是执行此操作的最有效方法，因此我将不胜感激有关如何重写代码或重新制定代码以使其运行得更快的任何建议。

Answer 1

我最终做的是用布尔值字典替换 np.argwhere 和 np.isin。

indices = [i for i in range(len(points))]
pointsDict = {k:0 for k in indices}

for s in importantPoints:
    if s in pointsDict.keys():
        pointsDict[s] = 1

然后当我想对权重求和时，我可以遍历邻居并检查它们的字典值是否为 1。

for i in range(KNeighbors.shape[0]):
    sumSeeds = 0
    for j in range(len(KNeighbors[i])):
        if seedDict[KNeighbors[i,j]] == 1:
            sumSeeds = sumSeeds + Weights[i,j]

仍然感觉有点笨拙，但这比尝试搜索 KNeighbors 矩阵中的每个列表要快得多。