###### tags: `Machine Learning` `Nonnegative Matrix Fractorization` `Orthogonal Nonnegative Matrix Fractorization` `Clustering` `Paper Survey`
# Deep orthogonal matrix fractorization as a hierarchical clustering technique
## Pierre De Handschutter and Nicolas Gillis
> 1. 深度正交矩陣分解
> 2. 階層式分群法Hierarchical Clustering
> 3. 正交優點:
> * 解的唯一性
> * 嚴格聚類詮釋
> 加上正交約束的非負矩陣分解之目標函式:
> 
> 以上是對矩陣G作正交約束，即對X做行聚類。
>

### Abstract
本篇論文中，作者會解釋為甚麼正交矩陣分解可被詮釋為由下往上的層次聚類方法
#### 論文主要貢獻
1. 作者提出的方法是對於深度正交矩陣分解簡單而有效的貪婪初始化策略。
2. 作者將提出的方法應用在高光譜圖片資料及分解上。

### 1. Introduction
* 給予一個矩陣，其中每個行向量皆為資料點(總共為m維)

其中

* 而每個資料點皆可以被表示為:
代表每個資料點皆為一個r維的基本向量的線性組合。

* 近似值準確度是由最小二乘法做評估標準:

* 為了確保這些模型的可解釋性與唯一性，通常會對變數W與H施加約束式，像是稀疏成分分析和非負矩陣分解。
* 而在變數矩陣H的非負性的基礎上加上正交性，則會得到正交的非負矩陣分解，以下統稱(ONMF)，可表示為:
其中為維度r的單位矩陣。
* 近幾年矩陣分解已被擴展到輸入的矩陣可被分解為兩個以上的變數矩陣的情況。
* 舉例來說以下是L層矩陣分解的情況，分解秩為
其中當 時
* 因此矩陣X才會近似於
* 此模型被稱為多層矩陣分解或深度矩陣分解。
* 若為多層矩陣分解則其最小化目標函式的方式為Sequential，其中
* 而深度矩陣分解使用的分解方法則是將反向傳播(Backpropgation)步驟納入考量。而此種方法則包含了最小化此損失函數:
* 而經過有序性的(Sequential)多層矩陣分解後，參數會被用Block Coodinate Descent迭代的更新，然而對於淺層矩陣分解來說則是需要對這些因素施加額外的約束，使其有意義。
* 舉例來說對於變數施加非負與正交性則會使其成為深度正交矩陣分解，也是此論文的主旨。

### 2. Deep ONMF is Equivalent to HC

* 標準的非負矩陣分解可被詮釋為軟性聚類工具，事實上，矩陣Ｈ中每個行向量的和都被約束控制在1。對應為資料點與第k個基本向量。
* 因為每列皆有正交約束，ONMF會更加嚴謹，矩陣的非負性加上正交性導致矩陣Ｈ的每列最多只能有一個非零元素，因為兩個非負與正交的向量必須不相交。

>H的列正交性保證H的每一行只能有一個非零元素，意味著每一個數據樣本只屬於一個類。這就是Hard-Clustering（K-means）。

>近似正交性放鬆了這個條件，每個數據樣本可能屬於多個類。這就是Soft-Clustering。

* 因此ONMF將每個數據點關聯到一個基本向量，並進行硬聚類，則可以證明ONMF等同於球型K-Means(a weighted variant of spherical k-means)最小化數據點和其相關中心點之間的角度，而K-Means則最小化了它們的歐式距離。
* 而深度正交非負矩陣分解(Deep ONMF)為正交非負矩陣分解(ONMF)之多層推廣，其中。

* 在深度ONMF中，隨著矩陣分解的展開，其分解秩會需要減少，也就是:

* 倘若分解秩並沒有減少，也就是對於某些l:，並滿足:
其中**0**矩陣為適於矩陣**W**的維度。
* 在上述的性質中，深度ONMF可被詮釋為Hierarchical Clustering (HC)模型，也因為它是透過聚集聚類來合併資料點，故被稱為由下往上的HC或稱其為聚合分類法(Agglomerative Clustering)。

> Agglomerative Clustering聚合分類法:（agglomerative）：是一種 “ bottom-up” 的方法，也就是先準備好解決問題可能所需的基本元件或方案，再將這些基本元件組合起來，由小而大最後得到整體。因此在階層式分群法中，就是將每個資料點都視為一個個體，在一一聚合。
階層式分群法Hierarchical Clustering:僅需要資料點 倆倆之間的距離，便可達到分群的效果。

* 作法如下：
* 第一層會先將矩陣Ｘ的行向量拆到聚類中;第二層則是將矩陣Ｗ的中心拆到聚類中，後續也是一樣。
* 事實上，當分解秩為，則其每層矩陣分解皆會合併兩個聚類類別(前兩個)變成一個聚類類別，其餘的聚類皆無改變。
* 因此，ONMF為HC工具的一種，其聚類的標準為加權球型K-Means，其與深度K-Means有關。因為它們都會強迫的每個行向量有一個非零元素並且其總和為1。

> Spherical K-means故名思議，意思應該是我們的數據點集全部分佈在一個球面上，然後進行聚類。因此在採用這個算法的時候，需要對每個數據點歸一化處理，使得我們要聚類的數據，分佈在一個球面上，然後我的個人理解這一個球面聚類，應該是用了余弦相似度度量替代了歐式距離度量（具體沒有細看，只是個人淺薄理解，可能有誤）。

### 3. Greedy Initialization of Deep ONMF
* 通常來說，深度ONMF在每層都會滿足，也就是

* 然而在本節中解釋，當時，有可能在第一層得到深度ONMF的閉式最優解，或者說對於的深度ONMF，也有可能得到閉式最優解。(Section 3A)

#### 作者動機
* 作者在此篇論文提出了一個貪婪深度ONMF的初始化(Section 3B)。此方法與大多數聚類方法一樣深度ONMF依賴於迭代方法，因此對初始化非常敏感。

#### 3A. Solving ONMF for r=n-1
* 考慮一個資料矩陣，接著將代入公式(1):因為ONMF需要分配n個資料點進n-1個聚類，故只有兩個資料點會合併至同個聚類中，令合併的資料點為第i與第j個資料點。
* 假設我們知道i與j，將重建的誤差函數最小化，則需要找到標量，以及新的資料中心點(Centroid)，也就是將下式最小化:並且要滿足以下條件:

* 使用一階優化條件，, 

* 接下來合併兩條等式與，並且將代入後，便得到:
* 假設不失一般性，則。
* 而在的情況，，反之則 。
其中。
* 也就是說ONMF r=n-1的最佳解會合併滿足損失函數中產出最小值的資料點。
* 最後在每個資料點兩兩排列組合後，作者假設，在不失一般性的情況下，存在ONMF最佳解，其最佳解形式如下:，損失函數為。
#### Algorithm 1
> 演算法1的目的是將兩個距離會產生最小的損失函數值資料點合併。
Input:兩個資料點: 
Output:基本向量係數 誤差值
1:

> ***Conclusion***
> 這篇論文主要在講如何使用非負矩陣分解的正交性去使用聚類，因為聚類是使用兩個資料點之間的距離遠近去分類，故作者提出的演算法也是將正交逼近法做優化。
> 作者方法是將初始化做優化。