我需要“标准化”一个大型稀疏矩阵，以便每行中的条目之和为 1。对于具有一些非零条目的行，每个条目除以行总和。对于全零的行，每个条目都替换为 1/numberOfColumns(使矩阵大大减少稀疏)。
如果重要的话，我的矩阵是方形的，并且是对称的。我首先使用一个“小”测试样本，其中我的矩阵大小约为 32K x 32K - 但我们最终需要它来处理更大的矩阵。时间和内存效率都很重要(内存比时间更重要)。在标准化之前，大约 1% 的条目非零。
对n x n矩阵进行归一化后，需要乘以一系列n x k密集矩阵，其中k是一个小数(<10)
我目前正在使用 la4j 矩阵包，但我与它没有任何联系。
我在下面包含了我的标准化代码。在我的 32K x 32K 测试用例中，速度非常慢。我从一些实验中知道，花费最多时间的部分是重新设置 T 矩阵的行(下面是我的 t.setRow 行)。
三个问题:
1)是否有更好的包或更好的方法来有效地做到这一点？
2)我不应该为此使用稀疏矩阵表示吗？
3)最好不要替换零行，而只是跟踪哪些行为零，然后相应地修改矩阵乘法？
提前致谢!
SparseMatrix t = new CRSMatrix(n, n);
// in between non-zero entries in t are added one at a time
double uniformWeight = (double) 1 / n; // used when the rowSum is zero
for (int i = 0; i < n; i++) {
Vector row = t.getRow(i);
double rowSum = row.sum();
if (rowSum > 0) {
row = row.divide(rowSum);
t.setRow(i,row);
} else {
row.assign(uniformWeight); // Assigns all elements of this vector to given value
t.setRow(i, row);
}
}
更新1
这是我尝试过的方法，确实加快了速度。我还没有尝试过弗拉基米尔的建议，但我会在下周回到这个项目时添加这些建议。现在，我保留一个 boolean 数组，其中行为零行，并且在矩阵乘法期间应将其视为统一行，现在是使用我的 hackMultiply 方法完成的。我很感激 Vladimir(或其他人)关于避免在该方法中使用 getRow 和 setRow 的额外建议。请注意，m2(第二个被乘数)和 m3(结果矩阵)不是稀疏的(如果这很重要的话)。提前致谢!
boolean[] zeroRows = new boolean[n]; // all values default to false
for (int i = 0; i < n; i++) {
Vector row = t.getRow(i); // haven't had a chance to try Vladimir's
double rowSum = row.sum(); // improvements here yet
if (rowSum > 0) {
row = row.divide(rowSum); // or here
t.setRow(i,row); // ...
} else {
// instead of setting to uniform weight, just keep track
zeroRows[i] = true;
}
}
/**
* Multiplies the given matrices m1 (Sparse) and m2, with the following modifications
* For every row in m1 for which the corrresponding entry in zeroRows is true
* use uniformVector instead of the actual contents of the row for the multiplication
* (Meant for the case when the replaced rows are all zeros, and we don't want
* to actually replace them in the SparseMatrix because then it wouldn't be sparse
* anymore.)
*
* @param m1 First multiplicand
* @param m2 Second multiplicand
* @param zeroRows boolean array indicating which rows of m1 should be logically replaced by uniformVector
* @param uniformVector vector to replace all the zeroRows with during the multiplication
* @return the result of the hacked multiplication
*/
public static Matrix hackMultiply(SparseMatrix m1, Matrix m2, boolean[] zeroRows, Vector uniformVector) {
// for "efficiency" I'm assuming I get passed in things of appropriate sizes, no checking
int a = m1.rows();
int b = m2.columns();
int c = m1.columns(); // must == m2.rows() for the matrix multiplication to work
Matrix m3 = new Basic2DMatrix(a,b);
Vector v1;
for (int i = 0; i < a; i++) {
if (zeroRows[i]) {
v1 = uniformVector;
} else {
v1 = m1.getRow(i);
}
m3.setRow(i, v1.multiply(m2));
}
return m3;
}
更新2
我真的很感谢@Vladimir 和@mikera 提供的所有帮助。就其值(value)而言，使用 la4j 和 hackMultiply 方法的版本在时间使用上与使用 vectorz 版本 0.26.0 的版本几乎相同。看起来 0.27.0 中的升级会给它带来一些优势，但我还没有尝试过。对于内存使用，带有 hack 的 la4j 版本比 vectorz 版本要好得多，至少是我现在编写代码的方式。我怀疑 0.27.0 版本也可能对此有所帮助。
最佳答案
如果您不依赖 la4j，Vectorz软件包(我维护的)有一些工具可以非常有效地执行此类操作。这是可能的，因为有两个特性:
- 数据稀疏存储
- 轻量级可变“ View ”，因此您可以将矩阵的行作为 vector 就地进行变异
我会使用的策略是:
- 创建一个
VectorMatrixMN将矩阵存储为稀疏 vector 行的集合 - 对每行使用
SparseIndexedVector，这是一种对于大部分为零的数据的有效格式
然后可以使用以下代码对矩阵的行进行归一化:
VectorMatrixMN m = ....
for (int i=0; i<SIZE; i++) {
AVector row=m.getRow(i);
double sum=row.elementSum();
if (sum>0) {
row.divide(sum);
} else {
m.setRow(i, new RepeatedElementVector(SIZE,1.0/SIZE));
}
}
请注意，此代码正在就地修改行，因此您不需要执行“setRow”之类的操作来将数据放回矩阵中。
使用具有 32,000 x 32,000 稀疏矩阵和每行 100 个非零值密度的配置，我将其计时在 32 毫秒以内，以使用此代码对整个矩阵进行归一化(即每个非零元素大约 10 纳秒 = = 每个矩阵元素 0.03ns :因此，您显然通过利用稀疏性获得了巨大的好处)。
您还可以选择对全零的行使用 ZeroVector (这会更快，但会施加一些额外的约束，因为 ZeroVector 是不可变的......)
编辑:
我编写了一个完整的示例，演示了如何在与此问题非常相似的用例中使用稀疏矩阵:
关于java - Java中稀疏矩阵行的高效修改，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20767397/