文章名：The Grassmannian Atlas: A General Framework for Exploring Linear Projections of High-Dimensional Data
期刊：《Computer Graphics Forum》
隨著信息技術(shù)的發(fā)展，數(shù)據(jù)的維度越來越高，數(shù)據(jù)的量越來越大。如何幫助用戶理解和感知高維數(shù)據(jù)成為了一個重要的挑戰(zhàn)。將高維數(shù)據(jù)投影到二維平面上，是探索高維數(shù)據(jù)的最常用的方式之一。高維數(shù)據(jù)的二維投影不僅僅限于原始數(shù)據(jù)維度的兩兩組合，可以說高維數(shù)據(jù)的二維線性投影是無窮的。探索這么多投影是非常耗時的，于是給投影加個度量值 ，選擇度量值高的投影來觀察，成為一個有效的途徑。但是存在的問題：度量值比較低的投影含有豐富的信息量也被忽略了，即關(guān)注全局最大值，而忽略了局部最大值。文章提出了基于Grassmannian流形的模型和框架，使用戶能夠觀察所有線性投影在重要性度量下的全局結(jié)構(gòu)，同時用戶能夠交互探索備選的二維投影。
文章為了實現(xiàn)上述想法，文章首先對原始數(shù)據(jù)采樣，構(gòu)建Knn Graph近似于Grassmannian流形；對采樣生成的投影計算質(zhì)量度量；構(gòu)建Topological Spines對數(shù)據(jù)進(jìn)行可視化。下圖所示為文章提出的一個系統(tǒng)框架。
1.數(shù)據(jù)采樣
投影在仿射變換下產(chǎn)生等效的散點圖構(gòu)成線性子空間，所以線性子空間構(gòu)成的空間遠(yuǎn)小于投影的空間，不會受到冗余的影響。二維線性子空間構(gòu)成的空間被稱為Grassmannian流形，表示為Gr(2,n)。Gr(2,n)上的一個點代表一個線性子空間，通常用正交基來參數(shù)化表示。采樣時文章采樣線性子空間，而不是投影子空間。為了得到表示線性子空間的正交基，文章使用高斯隨機(jī)矩陣經(jīng)過QR分解得到旋轉(zhuǎn)矩陣，從而得到正交基。
采樣時的標(biāo)準(zhǔn)：均勻性，密集型。在高維數(shù)據(jù)中，某個樣本點到其最近鄰居點和最遠(yuǎn)鄰居點之間的距離趨于相等，從而導(dǎo)致數(shù)據(jù)趨于的的均勻分布。采樣不密集的話，采樣距離過大會遺漏一些信息量大的投影，即局部最大值。對于一個高維數(shù)據(jù)，采樣數(shù)量的選擇對后續(xù)分析至關(guān)重要，于是文章對數(shù)據(jù)維度，采樣大小，采樣密度進(jìn)行了分析。如下圖所示，實驗結(jié)果反映了高維數(shù)據(jù)空間的本真稀疏性，文章采樣時滿足均勻性和密集性的。
2.投影質(zhì)量度量
文章采用了三個策略：Scagnostics、投影追蹤指數(shù)、降維函數(shù)
Scagnostics通過對二維投影散點圖的形狀進(jìn)行分析給出度量。主要基于三個圖形，最小生成樹，凸包，非凸包，如下圖所示 。在三個圖形的基礎(chǔ)上定義了九個度量，文章實驗用了六個，分別是Clumpy、Outlying、Monotic、Sparse、Skinny、Striated。
投影追蹤指數(shù)：Central Mass和Hole，分別衡量投影中央密度和投影中間有“Hole”。
降維函數(shù)：LDA和MDS，其中線性判別分析函數(shù)，用來衡量聚類的分離程度；多維尺度分析函數(shù)用來衡量從高維空間到二維空間相似度保留程度。
上述幾種二維投影散點圖的質(zhì)量度量的詳細(xì)細(xì)節(jié)可以查看文章的引用論文，這里不詳加累述。
3.構(gòu)建Topological Spines
給定在平滑流形上定義的莫爾斯函數(shù)f：M->R。f的積分線是M中的路徑，其切線向量與沿著路徑的每個點處的梯度一致。積分線以f的局部最小值開始，以局部最大值結(jié)束。這樣下降流形（周圍有局部最大值）被構(gòu)造為具有共同目的地的積分線群。下降流形形成一個分區(qū)M的單元格復(fù)合體，稱為莫爾斯復(fù)合體。莫爾斯復(fù)合體與地形圖的對應(yīng)關(guān)系如下圖所示。
盡管莫爾斯復(fù)合體能識別出f的局部最大值，它們對應(yīng)于f地形中的結(jié)構(gòu)不同的區(qū)域，但是不容易可視化。而Topological Spines有很好的地形隱喻，可以達(dá)到上述目的。地形圖與對應(yīng)的Topological Spine如下圖所示。
文章給出的可視化效果如下圖所示，由兩部分組成。左側(cè)是衡量持久性和穩(wěn)定性的圖。X軸代表穩(wěn)定性閾值，在Knn Graph中離某點最近的鄰居點的距離來定量衡量；Y軸代表局部最大值個數(shù)，即是圖中折線段中階梯的個數(shù)；長階梯隱喻著存在穩(wěn)定的局部最大值，也就是用戶感興趣的投影。右側(cè)圖是Topological Spine，顏色代表穩(wěn)定小大小，間接隱喻著全局最大值和局部最大值；寬度代表包含采樣點的個數(shù)。當(dāng)穩(wěn)定性閾值逐漸增大時，小于穩(wěn)定性閾值的局部最大值不會可視化出來。
4.實驗結(jié)果
4.1 E. coli dataset
E.coil數(shù)據(jù)集的實驗結(jié)果如下圖所示。黑色：細(xì)胞質(zhì)和細(xì)胞器；紫色：沒有信號序列的內(nèi)膜；橙色：含有不修改信號序列的內(nèi)膜；棕色：外膜脂蛋白(只有5個點)；淺綠：對應(yīng)于外膜；深綠：對應(yīng)于周質(zhì)，細(xì)胞內(nèi)膜和細(xì)菌外膜之間的空間中的濃縮凝膠狀基質(zhì)。在全局最大值處的投影捕獲黑色和（淺色和深色）綠色點之間的清晰分離，將這部分細(xì)胞物質(zhì)分為靠近細(xì)胞內(nèi)膜和靠近細(xì)胞外膜。.圖中兩個投影將紫色和橙色點組合成一個包含有關(guān)細(xì)胞內(nèi)膜信息的聚類。
4.2 Housing dataset
Housing數(shù)據(jù)集的實驗結(jié)果如下圖所示，使用Outlying度量得到的投影，揭示社會經(jīng)濟(jì)不均衡與地理位置的關(guān)系。其中的異常值用黑色小圓圈框選出來了。在右邊投影里，我們能夠發(fā)現(xiàn)與犯罪率相對較高的城鎮(zhèn)相對應(yīng)的異常值。在左側(cè)的投影，我們可以看到與平均房間數(shù)量相關(guān)的某些異常值。異常值里每個住宅有8-9個房間，而最小值卻只有3.5個房間。
4.3 Word2Vec dataset
Word2Vec數(shù)據(jù)集的實驗結(jié)果如下圖所示。這種數(shù)據(jù)集的分析和可視化方法是非常有限的。通常使用t-SNE這種非線性的可視化方法，但Word2Vec中的大多數(shù)關(guān)系本質(zhì)上是線性的。下圖使用Clumpy度量得到的投影。右邊的投影對應(yīng)于將城市和國家與所有其他單詞清晰分開的預(yù)測，并且分離各自的大陸（例如，北美的橙色，歐洲的深綠色，南美的藍(lán)色）。左邊的投影對城市和國家的影響不大，但很好地分開剩余的單詞組。例如：形容詞、副詞、名詞等。在以質(zhì)量度量排名選擇投影的方法中，左邊的投影會被忽略，從而印證文章方法的有效性。
5.結(jié)論
優(yōu)點：
1.文章提出的方法能夠確定局部最優(yōu)預(yù)測，并獲得對質(zhì)量度量本身的拓?fù)浣Y(jié)構(gòu)的直觀理解。
2.文中的方法能夠在多個質(zhì)量措施之間進(jìn)行比較，還有助于指導(dǎo)新質(zhì)量措施的設(shè)計和提供基準(zhǔn)。
不足：
1.隨著維度越來越大，維數(shù)災(zāi)難也不可避免，導(dǎo)致采樣消耗過大。目前Grassmannian的有效抽樣仍然是一個開放的問題。
2.文章的可視化手段雖然能提供對線性投影一個全局的視角，但是在于用戶的交互上還有待欠缺。
原作者：S. Liu等
筆記撰寫人：高樂
