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.