稀疏矩阵乘法加法等的java实现
2024-08-22 00:43:46
原创声明：本文系作者原创，转载请写明出处。
一、前言
前几天由于科研需要，一直在搞矩阵的稀疏表示的乘法，不过最近虽然把程序写出来了，还是无法处理大规模的矩阵（虽然已经是稀疏了）。原因可能是结果不够稀疏。或者相乘的矩阵本来也不稀疏。
还是把实现的程序放在这里。以供以后研究使用。
二、程序实现功能
首先封装稀疏矩阵为三元组形式。
程序的主要功能有：
稀疏矩阵的转置
稀疏矩阵的乘法
稀疏矩阵的加法
以及相应的导入文本文件（矩阵）等。
三、代码展示
以下程序由eclipse下编写的java
package others; import java.io.BufferedReader;
import java.io.File;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry; import weka.clusterers.SimpleKMeans;
import weka.core.DistanceFunction;
import weka.core.Instances;
import weka.core.converters.ArffLoader;
import Jama.Matrix;
/*
* 本类可实现稀疏矩阵三元组表示下的矩阵乘法和矩阵加法，以及矩阵转置等。结果也是三元组存储。
* 但是当数据量非常庞大时，乘积的结果无法存储，会出现内存溢出的现象。
*/
public class SMatrix { public Map<ArrayList<Integer>,Integer> Triples;//矩阵的三元组表示
public int rowNum;//矩阵行数
public int colNum;//矩阵列数 public int getRowNum() {
return rowNum;
} public void setRowNum(int rowNum) {
this.rowNum = rowNum;
} public int getColNum() {
return colNum;
} public void setColNum(int colNum) {
this.colNum = colNum;
} /*
* 构造函数1
*/
public SMatrix(){ } /*
* 构造函数2
*/
public SMatrix(Map<ArrayList<Integer>, Integer> triples, int rowNum, int colNum) { Triples = triples;
this.rowNum = rowNum;
this.colNum = colNum;
} /*
* 构造函数3
*/
public SMatrix(Map<ArrayList<Integer>, Integer> triples) { Triples = triples;
} /*
* 稀疏矩阵相乘函数
*/
public SMatrix Multiply(SMatrix M,SMatrix N){
if(M.colNum != N.rowNum){
System.out.println("矩阵相乘不满足条件");
return null;
} Map<ArrayList<Integer>,Integer> triples = new HashMap<ArrayList<Integer>,Integer>();
Iterator<Map.Entry<ArrayList<Integer>, Integer>> it1 = M.Triples.entrySet().iterator(); int iter = 0;
while(it1.hasNext()){
iter++;
// System.out.println("迭代次数："+iter);
Entry<ArrayList<Integer>, Integer> entry = it1.next();
ArrayList<Integer> position = entry.getKey();
// System.out.println("检查程序：" + position);
int value = entry.getValue();
int flag = 0;
Iterator<Map.Entry<ArrayList<Integer>, Integer>> it2 = N.Triples.entrySet().iterator();
while(it2.hasNext()){
Entry<ArrayList<Integer>,Integer> entry2 = it2.next();
ArrayList<Integer> position2 = entry2.getKey();
int value2 = entry2.getValue(); if(position.get(1) == position2.get(0)){
flag = 1;
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.add(position.get(0));
temp.add(position2.get(1));
int v = value * value2;
if(triples.containsKey(temp)){
triples.put(temp, triples.get(temp) + v);
System.out.println(temp+ "\t"+(triples.get(temp) + v)); }
else{
triples.put(temp, v);
System.out.println(temp + "\t" + v);
}
} }
}
SMatrix s = new SMatrix(triples,M.rowNum,N.colNum);
return s;
} /*
* 稀疏矩阵相加函数
*/
public static SMatrix Add(SMatrix M,SMatrix N){
if(M.colNum != N.colNum || M.rowNum != N.rowNum){
System.out.println("矩阵相加不满足条件");
return null;
}
SMatrix s = new SMatrix();
Map<ArrayList<Integer>,Integer> triples = new HashMap<ArrayList<Integer>,Integer>();
Iterator<Map.Entry<ArrayList<Integer>, Integer>> it1 = M.Triples.entrySet().iterator();
Iterator<Map.Entry<ArrayList<Integer>, Integer>> it2 = N.Triples.entrySet().iterator(); while(it1.hasNext()){
Entry<ArrayList<Integer>, Integer> entry = it1.next();
ArrayList<Integer> position = entry.getKey();
int value = entry.getValue();
if(triples.containsKey(position)){
triples.put(position, triples.get(position) + value);
}else{
triples.put(position, value);
} } while(it2.hasNext()){
Entry<ArrayList<Integer>,Integer> entry = it2.next();
ArrayList<Integer> position = entry.getKey();
int value = entry.getValue();
if(triples.containsKey(position)){
triples.put(position, triples.get(position) + value);
}else{
triples.put(position, value);
} }
return s;
} /*
* 稀疏矩阵求转置矩阵函数
*/
public SMatrix Transposition(){ Map<ArrayList<Integer>,Integer> triples = new HashMap<ArrayList<Integer>,Integer>();
Iterator<Map.Entry<ArrayList<Integer>, Integer>> it = this.Triples.entrySet().iterator();
while(it.hasNext()){
Entry<ArrayList<Integer>, Integer> entry = it.next();
ArrayList<Integer> position = entry.getKey();
int value = entry.getValue();
ArrayList<Integer> transP = new ArrayList<Integer>();
transP.add(position.get(1));
transP.add(position.get(0)); triples.put(transP, value); }
SMatrix s = new SMatrix(triples,this.colNum,this.rowNum);
return s;
} /*
* 加载文本数据为稀疏矩阵三元组形式的函数
*/
public SMatrix Load(String file, String delimeter){ Map<ArrayList<Integer>,Integer> triples = new HashMap<ArrayList<Integer>,Integer>(); try{
File f = new File(file);
FileReader fr = new FileReader(f);
BufferedReader br = new BufferedReader(fr); String line; while((line = br.readLine()) != null){
String[] str = line.trim().split(delimeter); ArrayList<Integer> s = new ArrayList<Integer>();
for(int i = 0;i < str.length - 1; i++){
s.add(Integer.parseInt(str[i]));
} triples.put(s, Integer.parseInt(str[str.length - 1])); } br.close();
fr.close(); }catch(IOException e){
e.printStackTrace();
}
SMatrix sm = new SMatrix(triples);
return sm;
}
/*
* 打印稀疏矩阵（三元组形式）
*/
public void Print(){
Map<ArrayList<Integer>, Integer> triples = this.Triples;
Iterator<Map.Entry<ArrayList<Integer>, Integer>> it = triples.entrySet().iterator();
int num = 0;
while(it.hasNext()){
Entry<ArrayList<Integer>, Integer> entry = it.next();
ArrayList<Integer> position = entry.getKey();
num++;
System.out.print(num+":");
for(Integer in:position){
System.out.print(in + "\t");
} System.out.println(entry.getValue());
} } public static void main(String[] args){ /*
* 测试程序 String testS = "data/me";
int k = 3;
SMatrix te = new SMatrix();
te = te.Load(testS,"\t");
te.rowNum = 4;
te.colNum = 6;
System.out.println("打印原矩阵");
te.Print();
System.out.println("打印原矩阵的转置矩阵");
te.Transposition().Print(); System.out.println("打印乘积矩阵");
SMatrix A2 = new SMatrix(); A2 = te.Multiply(te, te.Transposition());
A2.Print();
*/ long start = System.currentTimeMillis(); String file1 = "data/AT.txt";//author to term 的稀疏矩阵
String file2 = "data/CA.txt";//conference to author 的稀疏矩阵
String delimeter = " ";
int k = 11;
SMatrix M = new SMatrix();
SMatrix MT = new SMatrix(); SMatrix N = new SMatrix();
SMatrix NT = new SMatrix();
SMatrix P = new SMatrix();
SMatrix Q = new SMatrix(); M = M.Load(file1, delimeter);
M.colNum = 9225;
M.rowNum = 6456;
System.out.println("打印矩阵M");
M.Print();
MT = M.Transposition();
System.out.println("打印矩阵MT");
MT.Print(); System.out.println("计算M和MT的乘积");
System.out.println(M.rowNum);
P = M.Multiply(M, MT);
System.out.println("打印矩阵M与矩阵M转置的乘积");
P.Print(); N = N.Load(file2, delimeter);
N.colNum = 6456;
N.rowNum = 20;
System.out.println("打印矩阵N");
N.Print();
NT = N.Transposition(); System.out.println("打印矩阵NT：");
NT.Print(); System.out.println("计算NT 和 N的乘积");
System.out.println(NT.colNum);
System.out.println(N.rowNum);
Q = M.Multiply(NT, N);
Q.Print(); SMatrix A = new SMatrix();
A = A.Load("data/AA.txt"," "); SMatrix A1 = new SMatrix();
SMatrix A2 = new SMatrix();
System.out.println("计算矩阵A1=P+Q:");
A1 = SMatrix.Add(Q, P); System.out.println("打印矩阵A1：");
A1.Print();
A2 = SMatrix.Add(A1, A);//得到了比较全面的author to author 矩阵三元组 A2.Print(); double[][] matrix = new double[A2.rowNum][A2.colNum]; for(int i = 0;i < A2.rowNum;i++){
for (int j = 0; j < A2.colNum; j++) { ArrayList<Integer> list = new ArrayList<Integer>();
list.add(i);
list.add(j); if (A2.Triples.containsKey(list)) {
matrix[i][j] = A2.Triples.get(list);
}
else{
matrix[i][j] = 0;
} }
} for(int i = 0;i<A2.rowNum;i++){
for(int j = 0;j < A2.colNum;j++){
System.out.print(matrix[i][j]+"\t");
}
System.out.println();
}
Matrix Author = new Matrix(matrix); //第二步：求矩阵的特征值eigValue及其相应的特征向量矩阵，取前K个（最大的）
Matrix diagA = Author.eig().getD(); diagA.print(4, 2);
int m = diagA.getRowDimension();
int n = diagA.getColumnDimension(); Matrix eigVector = Author.eig().getV(); eigVector.print(eigVector.getRowDimension(),4); //将特征向量输出到文本中。
String outFile = "data/eigenVector.txt";
try{
File f = new File(outFile);
FileOutputStream fout = new FileOutputStream(f); fout.write("@RELATION\teigenVector\n".getBytes());
for(int i = n-k;i<n;i++){
fout.write(("@ATTRIBUTE\t"+i + "\tREAL\n").getBytes());
}
fout.write("@DATA\n".getBytes());
if(k <= n){
for(int i = 0;i < m;i++){
for(int j = n-k;j<n;j++){
Double temp = new Double(eigVector.getArray()[i][j]);
String tem = temp.toString();
fout.write((tem + "\t").getBytes()); }
fout.write(("\n").getBytes());
}
}
}
catch(IOException e){
e.printStackTrace();
}
//第三步：对特征向量矩阵进行kmeans聚类
Instances ins = null; SimpleKMeans KM = null; // 目前没有使用到，但是在3.7.10的版本之中可以指定距离算法
// 默认是欧几里得距离
DistanceFunction disFun = null; try {
// 读入样本数据
File file = new File("data/eigenVector.txt");
ArffLoader loader = new ArffLoader();
loader.setFile(file);
ins = loader.getDataSet(); // 初始化聚类器 （加载算法）
KM = new SimpleKMeans();
KM.setNumClusters(2); //设置聚类要得到的类别数量 KM.setMaxIterations(100);
KM.buildClusterer(ins); //开始进行聚类
System.out.println(KM.preserveInstancesOrderTipText());
// 打印聚类结果
System.out.println(KM.toString()); // for(String option : KM.getOptions()) {
// System.out.println(option);
// }
// System.out.println("CentroIds:" + tempIns);
} catch(Exception e) {
e.printStackTrace();
} System.out.println("程序正常结束"); long end = System.currentTimeMillis();
System.out.println(end - start); } }
最新文章
- Android项目架构之业务组件化
- NSIS打包（二）第一个安装包
- javascript中数组Array的方法
- BZOJ 2292 永远挑战
- webpack学习笔记—webpack安装、基本配置
- python学习第一天内容整理
- Android简单逐帧动画Frame的实现（二）
- 压缩感知重构算法之压缩采样匹配追踪（CoSaMP）
- 菜鸟谈谈C#中的构造函数和析构函数
- git基础命令学习总结
- 前端笔记之jQuery（上）加载函数的区别&对象&操作HTML/CSS&动画&选择器
- vivado 创建PS工程
- Mac book Pro BootCamp驱动下载地址
- mysql索引类型-方法-形式-使用时机-不足之处--注意事项
- mybatis通用mapper源码解析（一）
- C#对Mongodb数组对象操作
- Runloop原理
- 【BZOJ】1095: [ZJOI2007]Hide 捉迷藏 括号序列+线段树
- Coding 代码管理快速入门(转)
- Implementation：Bellman-ford