如何實(shí)現(xiàn)大規(guī)模高維數(shù)據(jù)的可視化？
原創(chuàng)【51CTO.com原創(chuàng)稿件】數(shù)據(jù)可視化是脫胎于計算機(jī)圖形學(xué)的計算機(jī)學(xué)科領(lǐng)域，廣泛應(yīng)用于科學(xué)實(shí)驗(yàn)和互聯(lián)網(wǎng)商業(yè)應(yīng)用。它分為科學(xué)可視化和信息可視化兩個子領(lǐng)域。
科學(xué)可視化主要是針對化學(xué)、物理和醫(yī)學(xué)上的試驗(yàn)數(shù)據(jù)，將實(shí)驗(yàn)結(jié)果用美觀可讀的方式展現(xiàn)給科學(xué)工作者，方便其進(jìn)行后續(xù)的工作，美國的國家實(shí)驗(yàn)室比如 LLNL 都有專門的團(tuán)隊開展可視化方面的工作。
信息可視化更多的是針對互聯(lián)網(wǎng)和商業(yè)數(shù)據(jù)，主要是把數(shù)據(jù)用更清晰和直觀的方式傳遞給用戶，美國的紐約時報是這方面做得非常好的公司。
整個可視化領(lǐng)域的頂級會議是 IEEE Visualization。信息可視化領(lǐng)域的頂級會議是 IEEE InfoVis。可視化領(lǐng)域的頂級期刊是 IEEE TVCG (IEEE Transactions on Visualization and Computer Graphics)。美國猶他大學(xué)(University of Utah)的 SCI Institute 是全世界在可視化研究領(lǐng)域做得最好的研究機(jī)構(gòu)之一，在國際上享有盛名。
高維數(shù)據(jù)的可視化是可視化領(lǐng)域中非常具有挑戰(zhàn)性的一類問題。常見的解決方案包括 Parallel Coordinate，Star Plot，降維至低維空間進(jìn)行可視化等。Jian Tang 等在 WWW 2016 上發(fā)表了題為 Visualizing Large-Scale and High-Dimensional Data 的文章，講述了他們是如何解決大規(guī)模高維數(shù)據(jù)的可視化問題的。下面我們來看一下他們提出的方法，分為兩步：
第一步將高維空間的數(shù)據(jù)利用K-近鄰算法重新構(gòu)建社交網(wǎng)絡(luò)模型，第二步將新構(gòu)建的社交網(wǎng)絡(luò)模型映射到低維空間進(jìn)行可視化，參見下圖：
作者在執(zhí)行第一步時，采取了類似 t-SNE 算法中的方式，而在執(zhí)行第二步時采取了優(yōu)化最大似然函數(shù)的方式。
首先，定義高維空間中映射到低維空間的兩個點(diǎn)的坐標(biāo)是
定義在低維空間中兩個點(diǎn)之間存在一條邊的概率是：
f 函數(shù)可以按照如下方式進(jìn)行定義：
帶權(quán)邊的生成概率為
整個低維空間的社交網(wǎng)絡(luò)生成概率為：
通過對 O 的求解，我們可以得到高維空間數(shù)據(jù)在低維空間的映射。注意在生成概率公式中存在對于負(fù)邊概率的大量計算。因?yàn)樨?fù)邊的數(shù)量與節(jié)點(diǎn)的數(shù)量是成二次方關(guān)系的，因此作者對于負(fù)邊采取了負(fù)采樣的策略。也就是給定點(diǎn)i，隨機(jī)選取節(jié)點(diǎn) j 與之構(gòu)成負(fù)邊。選擇 j 的概率為
為了避免在梯度下降過程中難以選擇學(xué)習(xí)率的問題，作者采用了在其本人的其他文獻(xiàn)中提出的 Edge Sampling 優(yōu)化方法對似然函數(shù)進(jìn)行優(yōu)化。Edge Sampling 優(yōu)化方法將圖的每一條邊看作沒有權(quán)重的邊，在進(jìn)行梯度下降優(yōu)化的時候根據(jù)邊的權(quán)重對每一條邊進(jìn)行采樣。
后續(xù)，作者選取了文本數(shù)據(jù)，并且利用了 KNN 分類器對降維處理之后的數(shù)據(jù)進(jìn)行分類，從準(zhǔn)確性和時間兩方面對 t-SNE 和作者提出的算法進(jìn)行了對比，發(fā)現(xiàn)作者提出的方法要優(yōu)于經(jīng)典的 t-SNE 算法。
圖 1. 本文研究方法與 t-SNE 算法效果對比
下圖為英文 Wikipedia 文章的可視化。每篇文章被認(rèn)為是高維空間中的一個點(diǎn)。作者在 Wikipedia 數(shù)據(jù)集上進(jìn)行了聚類，并對不同的類染上了不同的顏色。
圖2. 英文 Wikipeida 文章可視化。不同的顏色代表不同的文章分類。
Jian Tang , Jingzhou Liu , Ming Zhang , Qiaozhu Mei , Visualizing Large-scale and High Dimensional Data
汪昊，恒昌利通大數(shù)據(jù)部負(fù)責(zé)人，美國猶他大學(xué)碩士，在百度，新浪，網(wǎng)易，豆瓣等公司有多年的研發(fā)和技術(shù)管理經(jīng)驗(yàn)，擅長機(jī)器學(xué)習(xí)，大數(shù)據(jù)，推薦系統(tǒng)，社交網(wǎng)絡(luò)分析，計算機(jī)圖形學(xué)，可視化等技術(shù)。在 TVCG 和 ASONAM 等國際會議和期刊發(fā)表論文 5 篇。本科畢業(yè)論文獲國際會議 IEEE SMI 2008 最佳論文獎。
【51CTO原創(chuàng)稿件，合作站點(diǎn)轉(zhuǎn)載請注明原文作者和出處為51CTO.com】
