MTR算法

⑴ java实现矩阵相加、相乘，判断是否上（下）三角矩阵、对称矩阵、相等的算法

class Matrix
{
private int value[][]; //存储矩阵元素的二维数组

public Matrix(int m, int n) //构造m行n列的空矩阵
{
this.value=new int[m][n];
}

public Matrix(int n) //构造n行n列的空矩阵
{
this(n,n);
}

public Matrix()
{
this(10,10);
}

public Matrix(int mat[][]) //构造矩阵，由数组mat提供矩阵元素
{
this(mat.length,mat[0].length);
for (int i=0; i<mat.length; i++)
for (int j=0; j<mat[i].length; j++)
this.value[i][j] = mat[i][j];
}

public int get(int i, int j) //获得矩阵第i行第j列的元素，O(1)
{
return value[i][j];
}

public void set(int i, int j, int k) //设置矩阵第i行第j列的元素，O(1)
{
value[i][j]=k;
}

public void add(Matrix b) //this和b两个矩阵相加，改变当前矩阵
{
for (int i=0; i<this.value.length; i++)
for (int j=0; j<this.value[i].length; j++)
this.value[i][j] += b.value[i][j];
}

public String toString() //行主序遍历，访问矩阵全部元素
{
String str="";
for (int i=0; i<value.length; i++)
{
for (int j=0; j<value[i].length; j++)
str += " "+value[i][j];
str += "\n";
}
return str;
}

public Matrix transpose() //矩阵的转置
{
Matrix trans = new Matrix(value[0].length, value.length);
for (int i=0; i<this.value.length; i++)
for (int j=0; j<this.value[i].length; j++)
trans.value[j][i]=this.value[i][j];
return trans;
}

//判断一个矩阵是否为上三角矩阵
public boolean isUpperTriangularMatrix() {
int i, j = 0;
int c = this.value[1][0];

for(i=1; i<this.value.length; i++)
for(j=0; j<i; j++)
if(this.value[i][j] != c)
break;
if(i>=this.value.length)
return true;
return false;
}

//判断一个矩阵是否为下三角矩阵
public boolean isLowerTriangularMatrix() {
int i, j = 0;
int c = this.value[0][1];

for(i=0; i<this.value.length-1; i++)
for(j=i+1; j<this.value[0].length; j++)
if(this.value[i][j] != c)
break;
if(i>=this.value.length-1)
return true;
return false;
}

//判断一个矩阵是否为对称矩阵
public boolean isSymmetricMatrix () {
int i, j = 0;

for(i=1; i<this.value.length; i++)
for(j=0; j<i; j++)
if(this.value[i][j] != this.value[j][i])
break;
if(i>=this.value.length)
return true;
return false;
}

//比较两个矩阵是否相等
public boolean equals(Matrix b) {
int i, j = 0;

if(this.value.length != b.value.length || this.value[0].length != b.value[0].length)
return false;

for(i=0; i<this.value.length; i++)
for(j=0; j<this.value[0].length; j++)
if(this.value[i][j] != b.value[j][i])
break;
if(i>=this.value.length)
return true;
return false;
}

//计算两个矩阵的乘积
public Matrix multiply(Matrix b){
int i, j, k;
int sum;
Matrix mtr;

if(this.value[0].length != b.value.length) {
return null;
}

mtr = new Matrix(this.value.length, b.value[0].length);

for(i=0; i<this.value.length; i++)
{
for(k=0; k<b.value[0].length; k++){
for(sum=0,j=0; j<this.value[0].length; j++){
sum += this.value[i][j] * b.value[j][k];
mtr.value[i][k] = sum;
}
}
}

return mtr;
}
}

public class Test
{
public static void main(String args[])
{
int m1[][]={{1,2,3},{4,5,6}};
Matrix a=new Matrix(m1);
int m2[][]={{1,0,0},{0,1,0}};
Matrix b=new Matrix(m2);
System.out.print("Matrix a:\n"+a.toString());
System.out.print("Matrix b:\n"+b.toString());
a.add(b);
System.out.print("Matrix a:\n"+a.toString());
System.out.println("a的转置矩阵：\n"+a.transpose().toString());

int m3[][] = {{1,2,1},{0,3,1},{0,0,2}};
int m4[][] = {{1,0,0},{2,1,0},{3,2,1}};
int m5[][] = {{1,0,2},{0,1,0},{2,0,2}};
Matrix mtr1 = new Matrix(m3);
Matrix mtr2 = new Matrix(m4);
Matrix mtr3 = new Matrix(m5);
if(mtr1.isUpperTriangularMatrix())
System.out.println("上三角矩阵：\n" + mtr1.toString());

if(mtr2.isLowerTriangularMatrix())
System.out.println("下三角矩阵：\n" + mtr2.toString());

if(mtr3.isSymmetricMatrix())
System.out.println("对称矩阵：\n" + mtr3.toString());

System.out.println(mtr1.toString() + "\n乘以\n" + mtr2.toString() + "\n=\n");
Matrix tempM = mtr1.multiply(mtr2);
System.out.println(tempM.toString());
}
}

⑵ 多视图谱聚类算法介绍

假设给出了具有多个视图的数据 。

视图v的相似度矩阵：

视图v的拉普拉斯矩阵：

单视图聚类算法解决了归一化图拉普拉斯算子 如下的优化问题：

其中的tr代表求矩阵的迹。

矩阵 的行是数据点的嵌入，就是说一行对应一个数据，一共有n行，然后用k均值算法进行聚类。

作者的多视图谱聚类框架建立在标准谱聚类基础上，增加了半监督学习中的共正则化框架增加单一视图。

半监督学习中的共正则化基本上是通过使不同数据视图中的学习的假设在未标记数据上一致。

框架成功采用了两个主要假设：(a)每个视图中的真实目标函数应该就未标记数据的标签(兼容性)达成一致;(b)视图在类标签(条件独立性)下是独立的。

兼容性假设允许我们通过进搜索通过仅搜索兼容的函数来缩小可能的目标假设的空间。

作者提出了两种基于共正则化的方法，使得不同视图的聚类假设彼此一致。同时作者构建包含所有数据视图的拉普拉斯算子，同时在拉普拉斯算子的基础上进行了规范化，使得每个拉普拉斯算子得到的聚类结构在每个视图中一致。

第一个共正则化强制一个视图对 的特征向量应该具有高度的成对相似性(使用成对的正则化标准)。第二个共正则化方案是通过将他们规范化为共同的共识(基于中心的共正则化)来强制使视图特定的特征向量看起来相似。

在多视图的情况下，我们希望每个视图的特征向量矩阵是相似的。相当于在强制使所有视图中的谱聚类假设相同。

先讨论双视图情况。

提出以下损失函数作为两个视图之间聚类结果是否一致性的度量。

其中的 是 的相似矩阵。

进行除法的意义在于进行归一化使得两个视图具有可比较性。

然后作者选择了线性核作为相似性的度量方式。

从而得出：

选择线性核的原因：

因为 对上面的代价函数进行化简最终的到

然后我们在其中增加各个视图之间的谱聚类目标函数，得到以下的最大化问题：

然后我们可以通过不断的进行迭代去最大化上面的式子。

例如当给定 时，上式的优化目标就变成了：

这时候就化简成了普通的单视图的优化目标函数的形式。它的拉普拉斯矩阵为 。

上面的拉普拉斯矩阵是一种自适应(随着每次迭代，拉普拉斯算子会改变)的，结合内核和拉普拉斯算子的方法。

然后我们可以交替最大化使得算法得到最大值。但是同时要注意选择合适的初始化值从而避免陷入局部最大值。迭代开始时，可以选择最具有信息性的视图开始进行迭代。

对固定的 和 ，可以保证算法收敛。实践中通过观察连续迭代之间的目标值的差值来监视是否收敛，当低于某一阈值时，停止迭代。

我们扩展上一节中提出的共正则化谱聚类。对于m个视图，我们有：

在这里，对所有的共正则化部分使用了共同的 进行平衡。然后优化方法和双视图情况类似。

给定一个视图的 ，优化目标如下所示：

然后我们可以通过迭代对它进行不断优化。

这里提出的正则化方案是对上面的正则化方案的一种替代。将所有视图的特征向量 朝向共同的中心 (类似一组共同的特征向量)。这样可以减少正则化项的对数(m对)。

目标函数可以写为：

这个目标函数平衡各个谱聚类目标与每个视图特定特征向量 和共有特征向量 之间的折中。同时与第一种共正则化方法不同的是，我们可以对每一个正则化项设置一个参数来反映它的重要性。

这里的优化方法和上面的还是一样的，通过固定其他特征向量对单个特征向量进行优化。不同的地方在于需要对 进行优化，我们可以固定其他变量，然后对他进行优化。

只有对 进行优化时，和第一种共正则化方法不同，需要优化以下式子：

然后由矩阵的迹的性质tr(AB)=tr(BA)和tr(mA+nB)=mtr(A)+ntr(B)可以得到：

然后就又将这个问题转化成了单视图谱聚类的目标函数形式。对应的拉普拉斯矩阵为：

使用第二种基于中心的共正则化和第一种共正则化的另一个差别在于这种方法可以直接得到最终的特征向量集合 ，然后可以直接对他应用k均值等聚类算法进行聚类。而第一种共正则化方法需要对得出的所有特征向量集合进行拼接等处理步骤。

基于中心的共正则化方法一个缺点是容易受到有噪声的视图的影响，为了解决这个问题，需要仔细的选择每个视图对应的权重 。

参考论文：Co-regularized Spectral Clustering，Abhishek Kumar∗，Piyush Rai∗，Hal Daum ́e III.