矩陣視覺化

本文的閱讀等級:初級

矩陣通常以其儲存的數字陣列形式呈現,除非是天賦異稟的奇才,一般人很難洞察大尺寸矩陣的內部構造。矩陣視覺化是指利用色彩表示元的數值,雖然並不十分精確,但適合觀察矩陣的分塊結構,具有「見林不見樹」的效果。

 
考慮 n 個資料點散布於平面上 (或任何高維空間內),設 n\times n 階距離矩陣 A 的每個元 a_{ij} 表示點 i 與點 j 的距離,顯然 a_{ji}=a_{ij}A 是對稱矩陣,且 a_{ij}\ge 0a_{ii}=0。下圖是一個 100\times 100 階距離矩陣的像素圖,顏色較深 (淺) 的像素對應數值較小 (大) 的元,深色主對角線表示 a_{ii}=0 (點圖可放大)。

original-matrix

距離矩陣像素圖

 
我們想重新排序這 100 個資料點,目的是讓編號鄰近的資料點間距離較小,也就是說,鄰近編號的資料點在平面上群聚一塊。這個問題叫做群聚分析 (cluster analysis),在此並不深究。假設我們執行了群聚分析得到資料點的新排序,那該如何轉換原本的距離矩陣 A?很簡單,使用排列矩陣計算便可以搞定。

 
我們稱 n\times n 階矩陣 P 稱為排列 (permutation) 矩陣, 若 P 的每一行和每一列恰有一個元為 1,其他元為 0,例如,

P=\begin{bmatrix}    1&0&0\\    0&0&1\\    0&1&0    \end{bmatrix}

顧名思義,排列矩陣的功用在於排列另一矩陣的列或行。在 n\times m 階矩陣 A 左乘 P 可重排 A 的列,正是因為此一功用,排列矩陣是高斯消去法所使用的一種基本矩陣,如

\begin{bmatrix}    1&0&0\\    0&0&1\\    0&1&0    \end{bmatrix}\begin{bmatrix}    2&2&4&4\\    0&0&0&0\\    1&1&1&1    \end{bmatrix}=\begin{bmatrix}    2&2&4&4\\    1&1&1&1\\    0&0&0&0    \end{bmatrix}

m\times n 階矩陣 B 右乘 P 可重排 B 的行,如

\begin{bmatrix}    2&3&4\\    2&0&1\\    2&0&1\\    2&0&1    \end{bmatrix}\begin{bmatrix}    1&0&0\\    0&0&1\\    0&1&0    \end{bmatrix}=\begin{bmatrix}    2&4&3\\    2&1&0\\    2&1&0\\    2&1&0    \end{bmatrix}

既然排列矩陣交換列或行,任何排列矩陣便對應一組排序,例如,上面 P 矩陣各列的 1 所在位置依序為 (1,3,2),故記作 P_{(1,3,2)}。排列矩陣很容易由對應的排序得到,只需要重新排列同階單位矩陣 I 的列向量即可,所以共有 3\times 2\times 1=63\times 3 階排列矩陣。

 
我們稱僅交換二列的排列矩陣為基本排列矩陣,如 P_{(1,3,2)} 交換第 2 列與第 3 列,單位矩陣雖未交換行列也仍視作基本排列矩陣。基本排列矩陣是對稱的,但非基本排列矩陣則否,例如,

P_{(3,1,2)}=\begin{bmatrix}    0&0&1\\    1&0&0\\    0&1&0    \end{bmatrix}

任何非基本排列矩陣都可由基本排列矩陣相乘而得,此例為

P_{(3,1,2)}=P_{(3,2,1)}P_{(2,1,3)}

排列矩陣是可逆矩陣。基本排列矩陣 P 本身即為其逆矩陣,又因為基本排列矩陣是對稱的,故基本排列矩陣的逆矩陣即為其轉置。上例的非基本排列矩陣的逆矩陣為

\begin{aligned}  P_{(3,1,2)}^{-1}&=(P_{(3,2,1)}P_{(2,1,3)})^{-1}=P_{(2,1,3)}^{-1}P_{(3,2,1)}^{-1}\\    &=P_{(2,1,3)}^TP_{(3,2,1)}^T=(P_{(3,2,1)}P_{(2,1,3)})^T=P_{(3,1,2)}^T\end{aligned}

由此歸納出任意排列矩陣 P 都滿足 P^T=P^{-1},亦即 P 是正交矩陣,P 的各行向量為單位向量,而且彼此正交。利用上述性質,\det P^T=\det P,以及 \det P^{-1}=(\det P)^{-1},推知 (\det P)^2=(\det P)(\det P^T)=(\det P)(\det P^{-1})=1,故 \det P=\pm 1

 
除了應用於消去法作為基本矩陣,排列矩陣的用途常在於重新命名變數。如果我們要將矩陣 A 的第 ij 列對調,同時也將第 ij 行對調,可利用基本排列矩陣執行以下的相似轉換:

A\rightarrow P^{T}AP

例如,

\begin{bmatrix}    1&0&0\\    0&0&1\\    0&1&0    \end{bmatrix}\begin{bmatrix}    1&2&3\\    4&5&6\\    7&8&9    \end{bmatrix}\begin{bmatrix}    1&0&0\\    0&0&1\\    0&1&0    \end{bmatrix}=\begin{bmatrix}    1&3&2\\    7&9&8\\    4&6&5    \end{bmatrix}

任何排列矩陣都為基本排列矩陣之積,即

P=P_1P_2\cdots P_k

就有

P^{T}AP=P_k^T\cdots (P_2^{T}(P_1^{T}AP_1)P_2)\cdots P_k

因此相似轉換 P^{T}AP 適用任何列行排序。

 
回到原來的問題,對於 100\times 100 階距離矩陣 A,總計有 100! 個合法的排列相似轉換 P^{T}AP 可供選擇。下面的距離矩陣像素圖 (點圖可放大) 係利用樹狀群聚分析 (tree clustering) 得到的排序,這 100 個資料點經重新命名排序後,粗分為四大群聚,分別對應深色的四個主對角分塊。

permutated-matrix

重新排序後的距離矩陣像素圖

 
第一個主對角分塊面積較小顏色較深,表示此群聚所含的資料點數較少且彼此距離相近。第三個分塊面積較大但分塊顏色較淺,這說明了此群聚包含的資料點數較多且散布範圍也較廣,仔細觀察不難發現這個大群聚由五個較小的群聚 (深色小主對角分塊) 所組成。另一方面,由非主對角分塊的顏色可以判斷不同群聚間的距離,從圖得知第二個群聚和第四個群聚較為接近。

 
看了上面這兩張圖難免會想起電影「駭客任務 (The matrix)」裡的超現實畫面,不過此文的 matrix (矩陣) 非電影指稱的 matrix (母體)。

This entry was posted in 線性代數專欄, 應用之道 and tagged , , , , , . Bookmark the permalink.

2 則回應給 矩陣視覺化

  1. ALeaf 說:

    Visualization of matrix is a wonderful presentation of clustering. Thanks for the great article.

  2. ccjou 說:

    u r welcome. im thinking of posting more practical stuffs that r not found in textbooks.

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s