盧 穎，張志豪,2，張軍平,2+

1.復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，上海 200433

2.上海市智能信息處理重點(diǎn)實(shí)驗(yàn)室，上海 200433

1 引言

聚類是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)的重要研究方向之一，旨在按照一定的準(zhǔn)則將無標(biāo)簽數(shù)據(jù)劃分成不同的類或簇。在處理高維數(shù)據(jù)聚類時(shí)，常將數(shù)據(jù)映射到低維空間，再通過可視分析來完成聚類。然而，如果可分性不好，或數(shù)據(jù)本身有重疊問題時(shí)，單純依靠聚類算法不能對(duì)數(shù)據(jù)形成好的分析結(jié)果。

因此，人們期望結(jié)合機(jī)器學(xué)習(xí)和可視化以及人機(jī)交互的優(yōu)點(diǎn)，提出一種可以輔助聚類分析的方法。具體來說，本文提出了一個(gè)用于聚類分析的可視化交互系統(tǒng)。首先通過維數(shù)約簡(jiǎn)的方法將數(shù)據(jù)點(diǎn)降到二維進(jìn)行可視化，然后計(jì)算出感興趣區(qū)域內(nèi)投影點(diǎn)的主方向，再通過拉伸主方向和其垂直方向上的數(shù)據(jù)點(diǎn)距離與數(shù)據(jù)進(jìn)行交互，減少投影點(diǎn)的堆疊現(xiàn)象，改善聚類分析的效果。

本文的主要貢獻(xiàn)包括：

（1）提出了一個(gè)用于聚類分析的可視化交互系統(tǒng)。系統(tǒng)利用維數(shù)約簡(jiǎn)的方法將數(shù)據(jù)投影到二維平面可視化，讓用戶與數(shù)據(jù)自由地交互，進(jìn)行聚類分析。

（2）創(chuàng)新性地利用局部主方向的方法指導(dǎo)聚類。本文提出的“局部主方向+交互”的聚類方法，在可視化領(lǐng)域是一種全新的方法，其充分利用了交互性的優(yōu)勢(shì)，提升用戶在聚類問題中的參與度；同時(shí)該方法又結(jié)合了機(jī)器學(xué)習(xí)領(lǐng)域中局部主方向?qū)?shù)據(jù)方向性的直觀反映，增強(qiáng)了聚類分析的效果。用戶可以先查看所選投影點(diǎn)主方向及其垂直方向上的頻數(shù)直方圖，再調(diào)節(jié)主方向和垂直方向上的比例參數(shù)，對(duì)投影點(diǎn)之間的距離在兩個(gè)方向上進(jìn)行縮放，使得投影點(diǎn)沿著主方向和垂直方向移動(dòng)，減少重疊現(xiàn)象，增加數(shù)據(jù)的可分性，達(dá)到更好的可視化聚類效果。

（3）通過實(shí)驗(yàn)的方法，綜合評(píng)估討論了局部主方向方法對(duì)交互式可視化聚類分析的影響和有效性。該方法可以有效地改善投影點(diǎn)的可分性，在實(shí)現(xiàn)相似聚類效果的同時(shí)，減少降維算法的迭代次數(shù)，提升聚類分析效率。

（4）使用用戶調(diào)研的方法，采訪記錄用戶的使用體驗(yàn)，探討整個(gè)交互式可視化系統(tǒng)和局部主方向方法對(duì)聚類分析的幫助。結(jié)果表明，基于局部主方向的交互式可視分析方法是行之有效的。

2 相關(guān)工作介紹

本章將簡(jiǎn)要介紹聚類算法和減輕高維數(shù)據(jù)低維投影點(diǎn)重疊的研究。

粗略來講，聚類算法可劃分為5類[1]。

第一類是基于劃分的聚類算法，如K-均值（K-means）算法和CLARANS（clustering algorithm based on randomized search）算法[2]等。這類算法旨在將數(shù)據(jù)點(diǎn)分成若干個(gè)小團(tuán)，每個(gè)小團(tuán)代表一個(gè)類，通常假設(shè)數(shù)據(jù)服從某個(gè)分布。

第二類是基于層次的聚類算法，典型的層次聚類算法有BIRCH（balanced iterative reducing and clustering using hierarchies）算法[3]和 CURE（clustering using representatives）算法[4]等。這類算法將給定的數(shù)據(jù)集分解成若干層次，直至滿足條件為止。其主要缺點(diǎn)是一旦進(jìn)行層次分離或合并操作，這一操作將無法撤銷。

第三類是基于密度的聚類算法，如DBSCAN（density-based spatial clustering of applications with noise）算法[5]和OPTICS（ordering point to identify the cluster structure）算法[6]等。這類算法能發(fā)現(xiàn)離群點(diǎn)和任意形狀的簇。

第四類是基于網(wǎng)格的聚類算法，典型的算法有Wave-Cluster算法[7]和 STING（statistical information grid-based method）算法[8]。這類算法因?yàn)榫垲愡^程不依賴于具體的數(shù)據(jù)點(diǎn)，網(wǎng)格的數(shù)量又通常遠(yuǎn)小于數(shù)據(jù)點(diǎn)數(shù)，一般運(yùn)行速度較快。但是數(shù)據(jù)分布不規(guī)則時(shí)，這類算法效果不是很好。

第五類是基于模型的聚類算法，如期望最大化（expectation maximization）算法[9]和自組織映射（selforganizing maps，SOM）算法[10]等。這類算法假設(shè)數(shù)據(jù)由若干潛在的概率分布組合而成，通過不斷優(yōu)化模型讓模型和真實(shí)的數(shù)據(jù)分布相符。模型既可以是統(tǒng)計(jì)模型，也可以是神經(jīng)網(wǎng)絡(luò)。

盡管聚類算法在很多方面都取得了好的效果，但在處理高維數(shù)據(jù)時(shí)受維數(shù)災(zāi)難問題影響，往往難以獲得直觀且好的聚類效果。一種策略是通過維數(shù)約簡(jiǎn)投影到低維，通過可視化由人來進(jìn)行后期評(píng)估。其原因是，按格式塔理論[11]，人的視覺系統(tǒng)具有很強(qiáng)的聚類能力，可以將相似的目標(biāo)自動(dòng)聚成團(tuán)。然而，可視分析的難易度受數(shù)據(jù)點(diǎn)投影的重疊程度影響。如果聚類算法不能得到好的可分性，數(shù)據(jù)則有可能在低維產(chǎn)生混疊，導(dǎo)致隨后的分析變得困難。

為了減少數(shù)據(jù)點(diǎn)重疊給后期分析帶來的困難，研究者做了大量相關(guān)研究，這些研究可劃分成4類。

第一類工作是通過增加視覺通道來改善視覺效果，比如為散點(diǎn)圖的數(shù)據(jù)點(diǎn)選擇不同的尺寸、透明度、形狀和布局等。Woodruff等人[12]通過繪制尺寸不同的投影點(diǎn)來增強(qiáng)可視化的視覺效果。Dang等人[13]則是通過改變數(shù)據(jù)點(diǎn)的布局來解決二維平面上的重疊問題。這類做法雖然直觀和簡(jiǎn)單，但增加的視覺編碼可能會(huì)給用戶造成視覺假象，影響其對(duì)數(shù)據(jù)屬性的理解。

第二類工作的主要思想是對(duì)投影點(diǎn)進(jìn)行密度估計(jì)，計(jì)算密度場(chǎng)，建立顏色和密度之間的映射關(guān)系。Bachthaler等人[14]提出了一個(gè)嚴(yán)格、精確、通用的數(shù)學(xué)模型來創(chuàng)建連續(xù)的散點(diǎn)圖。但是在同一視圖內(nèi)對(duì)多個(gè)密度場(chǎng)進(jìn)行顏色編碼對(duì)用戶具有一定的誤導(dǎo)性。

第三類工作試圖將高密度區(qū)域的投影點(diǎn)移動(dòng)到其他空間較大的區(qū)域，以此緩解投影點(diǎn)重疊的問題?；谶@一想法，Janetzko等人[15]提出可以用橢球像素分布改變?cè)纪队包c(diǎn)的分布，減少投影點(diǎn)的重疊。但這種可視化方式會(huì)改變低維空間中投影點(diǎn)的分布情況和拓?fù)浣Y(jié)構(gòu)，使得用戶無法從低維空間中獲得高維數(shù)據(jù)的真實(shí)情況。

第四類工作是借助諸如放縮（zoom）、魚眼（fisheye）、上下文聚焦（focus+context）等交互的方法探索重疊的投影點(diǎn)。這類典型的工作有Yuan等人[16]提出的交互探索分析高維數(shù)據(jù)子空間的方法。Chen等人[17]綜合運(yùn)用了上述4種交互技巧，提出了一種基于多類藍(lán)噪聲采樣[18]的方法，在盡量保留數(shù)據(jù)點(diǎn)的分布和相對(duì)密度的同時(shí)，解決重疊問題。

數(shù)據(jù)投影點(diǎn)的重疊使得聚類的邊界變得模糊，容易困擾甚至誤導(dǎo)用戶，并使其最終做出錯(cuò)誤的判斷。而可視分析中的交互技術(shù)賦予了用戶與投影點(diǎn)交互的能力，讓用戶直接參與到聚類的探索過程中，對(duì)整個(gè)聚類過程有較好的掌控。受文獻(xiàn)[19]的啟發(fā)，本文選取局部主方向作為提示信息給用戶，幫助其進(jìn)行交互探索。局部主方向作為數(shù)據(jù)點(diǎn)的局部朝向，可以編碼為一個(gè)新的可視通道，從而幫助用戶區(qū)分不同類別。鑒于此，本文提出了一種基于局部主方向的交互式可視聚類分析方法。

3 基于局部主方向的交互式聚類可視化

本章分五部分來介紹基于局部主方向的交互式聚類可視化方法。

3.1 可視分析方法

用戶利用整個(gè)系統(tǒng)進(jìn)行聚類分析的過程如下：

如算法1所示，用戶首先選擇一種降維方法得到數(shù)據(jù)集的初始可視化效果。降維方法的選取依賴于先驗(yàn)知識(shí)或是多次對(duì)比嘗試。

算法1初始可視化算法

輸入：數(shù)據(jù)集dataset，降維方法f。

輸出：初始可視化結(jié)果，數(shù)據(jù)點(diǎn)平面坐標(biāo)result。

在初始可視化效果基礎(chǔ)上，用戶選取感興趣的區(qū)域（如投影密度較大的區(qū)域）進(jìn)行進(jìn)一步探索（見算法2）。

算法2興趣區(qū)探索

輸入：興趣區(qū)數(shù)據(jù)點(diǎn)平面坐標(biāo)data，主方向上直方圖組數(shù)b1，主方向垂直方向上直方圖組數(shù)b2，主方向上縮放比例k1，主方向垂直方向上縮放比例k2。

探索過程中，用戶通過查看該區(qū)域主方向及其垂直方向，以及兩個(gè)方向上的頻數(shù)直方圖，從直觀上了解區(qū)域內(nèi)投影點(diǎn)的分布情況。在此基礎(chǔ)上，用戶可以縮放主方向及其垂直方向上的點(diǎn)點(diǎn)距離，減少數(shù)據(jù)點(diǎn)的重疊，便于聚類分析。

用戶還可以對(duì)不同的類進(jìn)行著色，增強(qiáng)視覺效果。為了避免距離縮放導(dǎo)致的數(shù)據(jù)點(diǎn)重合問題和非選區(qū)內(nèi)數(shù)據(jù)點(diǎn)干擾縮放效果問題，探索過程中用戶可以隱藏選區(qū)外的數(shù)據(jù)點(diǎn)，獲得更好的用戶體驗(yàn)。

3.2 友好的交互界面

如圖1所示，系統(tǒng)主要分為三部分：信息欄、可視化探索區(qū)域、主方向參數(shù)欄。為了讓用戶專注于數(shù)據(jù)探索和聚類分析，可視化探索區(qū)域的面積較大，且處于視覺聚焦的中間位置。

（1）信息欄。如圖2所示，信息欄中包含的信息有數(shù)據(jù)集、降維方法、降維方法中所用距離度量信息。用戶可以導(dǎo)入不同的數(shù)據(jù)集進(jìn)行探索。由于數(shù)據(jù)集的性質(zhì)各不相同，用戶需要選擇合適的降維方法和距離度量才能獲得一個(gè)比較好的初始可視化效果。除此之外，信息欄還提供當(dāng)前用戶已經(jīng)標(biāo)注的類別標(biāo)記信息。為了防止誤操作，提供刪除標(biāo)記功能。

（2）可視化探索區(qū)域。圖3中的可視化探索區(qū)域主要分為兩部分：數(shù)據(jù)顯示區(qū)域和輔助按鈕區(qū)域。

在數(shù)據(jù)顯示區(qū)域內(nèi)，用戶可以通過點(diǎn)擊數(shù)據(jù)點(diǎn)與數(shù)據(jù)交互，查看高維空間中的原始信息。對(duì)于圖像類數(shù)據(jù)（如MNIST），提示框內(nèi)會(huì)顯示原始的圖像；對(duì)于數(shù)值類型的數(shù)據(jù)，提示框內(nèi)則顯示各個(gè)維度上的數(shù)值信息。

Fig.1 User interface of system圖1 系統(tǒng)界面

Fig.2 Information column圖2 信息欄

Fig.3 Visual exploration area圖3 可視化探索區(qū)域

利用輔助按鈕區(qū)域的按鈕，用戶可以和數(shù)據(jù)進(jìn)行更多的交互操作。用戶可以選擇查看或隱藏?cái)?shù)據(jù)的原始標(biāo)簽。系統(tǒng)為用戶提供多邊形筆刷來選中感興趣的區(qū)域。用戶還可以隱藏未選中的數(shù)據(jù)點(diǎn)，便于探索。對(duì)于選區(qū)內(nèi)的數(shù)據(jù)點(diǎn)，用戶可以標(biāo)注成一個(gè)類，也可以利用主方向方法進(jìn)一步探索。方便起見，系統(tǒng)提供了一鍵復(fù)位的按鈕，可以讓用戶將所有數(shù)據(jù)點(diǎn)放回原位。

（3）主方向參數(shù)欄。圖4中右側(cè)的主方向參數(shù)欄包含與主方向方法相關(guān)的一些輔助按鈕和信息。在可視化探索區(qū)域確定選區(qū)后，用戶可以選擇顯示或是隱藏該區(qū)域內(nèi)數(shù)據(jù)的主方向和垂直方向，兩者分別用紅色箭頭和藍(lán)色箭頭表示。如果沒有進(jìn)行區(qū)域選取操作，則默認(rèn)計(jì)算所有數(shù)據(jù)點(diǎn)的主方向。在查看主方向的同時(shí)，用戶可以通過兩個(gè)方向上的頻數(shù)直方圖來獲得數(shù)據(jù)分布信息，并且可以通過調(diào)節(jié)頻數(shù)直方圖的組數(shù)來獲得更好的分析體驗(yàn)。此外，用戶可以調(diào)節(jié)主方向及其垂直方向上的縮放比例，令選區(qū)內(nèi)數(shù)據(jù)點(diǎn)沿著兩個(gè)方向移動(dòng)，減少數(shù)據(jù)點(diǎn)的重疊，獲得更好的聚類效果。

Fig.4 Selected data and corresponding principal direction column圖4 選中數(shù)據(jù)區(qū)域和對(duì)應(yīng)的主方向欄

3.3 降維方法的選擇

在整個(gè)系統(tǒng)的使用過程中，用戶首先需要選擇一種降維方法得到較好的初始可視化效果。

降維方法分為線性降維方法和非線性降維方法。線性降維方法如主成分分析（principal component analysis，PCA）[20]、多維標(biāo)度分析（multidimensionalscaling，MDS）[21]等；非線性降維方法包括t-SNE（t-distributed stochastic neighbor embedding）[22]、LLE（local linear embedding）[23]等。線性降維方法的降維結(jié)果通常是原本維度的線性組合，而非線性降維方法的結(jié)果可能難以解釋。但在聚類分析中，并不關(guān)心降維結(jié)果的實(shí)際意義，只是關(guān)心數(shù)據(jù)在約簡(jiǎn)后維度上的可分性和離群點(diǎn)的保留情況。

對(duì)于同一數(shù)據(jù)集，不同降維方法產(chǎn)生的可視化效果不同，比如在MNIST[24]數(shù)據(jù)集上，t-SNE[22]的可視化效果比MDS[25]的效果好。同樣的降維方法，在不同的數(shù)據(jù)集上效果也各不相同。與MNIST[24]數(shù)據(jù)集上相反，在UCI的wine數(shù)據(jù)集[25]上，MDS[21]方法可以獲得比較好的可視化效果，而t-SNE[22]的效果卻并不理想。

基于此，系統(tǒng)提供了多種降維方法供用戶選擇，以減少單一降維方法可能導(dǎo)致的初始可視化結(jié)果不夠理想的問題。

3.4 主方向的意義和計(jì)算

3.4.1 主方向

在二維平面上，如果樣本點(diǎn)在某個(gè)方向上的投影的方差最大，則稱該方向?yàn)橹鞣较颉募夹g(shù)上來說，計(jì)算主方向等價(jià)于對(duì)二維平面上點(diǎn)坐標(biāo)進(jìn)行主成分分析，找到最大化投影點(diǎn)方差的方向。

記原坐標(biāo)系為x-y坐標(biāo)系，記以主方向與其垂直方向?yàn)檎换淖鴺?biāo)系為xmd-ymd坐標(biāo)系，對(duì)坐標(biāo)系x-y中的樣本X=(x1,x2,…,xn)∈?2×n，經(jīng)變換后得到在xmd-ymd坐標(biāo)系下的樣本：

其中，W∈?2×2為變換矩陣；Z∈?2×n是樣本在xmdymd坐標(biāo)系下的表達(dá)。

坐標(biāo)變換后的樣本點(diǎn)的方差為要使方差最大化，也即：

求解W的過程也就是進(jìn)行主成分分析的過程（見算法3）。

算法3獲取主方向和垂直方向

輸入：數(shù)據(jù)D={d1,d2,…,dn}。

輸出：主方向md及其垂直方向mdv。

v為特征值和特征向量*/

顯然，在主方向上所有數(shù)據(jù)點(diǎn)滿足最近重構(gòu)性和最大可分性，相比其他方向，在主方向上樣本點(diǎn)的可分性比較好。

3.4.2 拉伸變換

因?yàn)橹鞣较蚓哂凶畲罂煞中?，在該方向上?shù)據(jù)點(diǎn)的投影能夠盡可能地分開，所以令初始數(shù)據(jù)點(diǎn)沿著主方向進(jìn)行變換可以減少數(shù)據(jù)點(diǎn)的重疊，增加視覺上的可分性。如圖5所示，對(duì)主方向和其垂直方向上單位長(zhǎng)度大小進(jìn)行變換（見算法4），圖中紅色的方向?yàn)橹鞣较?，藍(lán)色的方向?yàn)榇怪狈较?，步驟②中主方向上縮放比例為229%，垂直方向上為443%。可以在保持選區(qū)內(nèi)數(shù)據(jù)點(diǎn)結(jié)構(gòu)的同時(shí)，減少數(shù)據(jù)點(diǎn)的堆疊現(xiàn)象，使數(shù)據(jù)變得可分。

Fig.5 Stretching demo along principal direction圖5 沿主方向拉伸的示意圖

算法4收縮拉伸點(diǎn)點(diǎn)距離

輸入：數(shù)據(jù)D={(x1,y1),(x2,y2),…,(xn,yn)}，主方向上拉伸倍數(shù)k1，主方向垂直方向上拉伸倍數(shù)k2，主方向md，主方向垂直方向mdv。

輸出：變換后數(shù)據(jù)坐標(biāo)D′={(x1′,y1′),(x2′,y2′),…,(xn′,yn′)}。

如圖6所示，記原始坐標(biāo)系為x-y坐標(biāo)系，以主方向與其垂直方向?yàn)檎换淖鴺?biāo)系為xmd-ymd坐標(biāo)系。在x-y坐標(biāo)系下，原點(diǎn)為O，對(duì)點(diǎn)P(x,y)，記OP=r，OP與x軸的夾角為α，顯然有：

點(diǎn)P(x,y)在xmd-ymd坐標(biāo)系下的坐標(biāo)P(xmd,ymd)：

設(shè)拉伸變換Sk1,k2(P(x,y))表示點(diǎn)P(x,y)在xmd-ymd坐標(biāo)系下，沿主方向xmd擴(kuò)大k1倍，沿垂直方向ymd擴(kuò)大k2倍，也即變換后的點(diǎn)P′(x′,y′)=Sk1,k2(P(x,y))在xmd-ymd坐標(biāo)系下的坐標(biāo)為P′(k1xmd,k2ymd)，則點(diǎn)P′在x-y坐標(biāo)系下的坐標(biāo)P′(x′,y′)：

Fig.6 Stretching transformation圖6 拉伸變換

3.5 頻數(shù)直方圖的使用

頻數(shù)直方圖可以反映主方向和其垂直方向上數(shù)據(jù)點(diǎn)的分布情況。通過頻數(shù)直方圖，用戶可以直觀地感受到數(shù)據(jù)的一些內(nèi)在信息，從而更好地進(jìn)行聚類分析。

如圖7所示，右側(cè)的主方向欄中的主方向頻數(shù)直方圖中有兩個(gè)峰值，這說明主方向上有兩塊區(qū)域數(shù)據(jù)點(diǎn)比較密集，可能存在兩個(gè)類；左側(cè)的數(shù)據(jù)點(diǎn)的顏色標(biāo)簽對(duì)應(yīng)了數(shù)據(jù)的類別，可以看出大致有紅藍(lán)兩類，與頻數(shù)直方圖反應(yīng)出的數(shù)據(jù)信息相一致。

Fig.7 Selected data and corresponding principal direction histogram and tangent direction histogram圖7 選中區(qū)域數(shù)據(jù)點(diǎn)的主方向頻數(shù)直方圖和垂直方向頻數(shù)直方圖

圖8能夠反映出直方圖組數(shù)的選取對(duì)判斷數(shù)據(jù)分布情況的影響。圖8是圖7中數(shù)據(jù)點(diǎn)在主方向上的頻數(shù)直方圖。對(duì)比組數(shù)k=10時(shí)得到的直方圖和組數(shù)k=20時(shí)得到的直方圖，可知組數(shù)k=20時(shí)的直方圖中的雙峰更為明顯；而當(dāng)k=100時(shí)，由于分組過多，直方圖上更像是有3個(gè)類。如果直方圖的組數(shù)k選取不當(dāng)，偏大或者偏小，都不能達(dá)到較好的輔助數(shù)據(jù)分析的目的。但是直方圖組數(shù)的選取并沒有一個(gè)通用的標(biāo)準(zhǔn)，需要根據(jù)具體情況、具體數(shù)據(jù)來決定。因此系統(tǒng)中設(shè)置了可以更改組數(shù)的滑動(dòng)條，令用戶能夠根據(jù)實(shí)際情況對(duì)直方圖的組數(shù)進(jìn)行調(diào)整，獲得較好的效果。

4 實(shí)驗(yàn)與結(jié)果

4.1 人工合成數(shù)據(jù)集

第一組實(shí)驗(yàn)采用了一個(gè)人工合成的數(shù)據(jù)集。該數(shù)據(jù)集共有492個(gè)數(shù)據(jù)點(diǎn)，7個(gè)分類，每個(gè)數(shù)據(jù)點(diǎn)有4個(gè)維度和1個(gè)標(biāo)簽。數(shù)據(jù)集內(nèi)包含了3組高維的平行線和一些隨機(jī)噪聲點(diǎn)。

在降維方法的選取上，分別選擇了MDS[21]方法和t-SNE[22]方法來進(jìn)行實(shí)驗(yàn)。

Fig.8 Different bin numbers cause different visual effects圖8 不同組數(shù)對(duì)頻數(shù)直方圖效果的影響

使用了MDS降維后得到的數(shù)據(jù)點(diǎn)如圖9所示，對(duì)中間的一塊直線區(qū)域進(jìn)行探索。通過拉伸垂直方向的點(diǎn)點(diǎn)距離，可以清楚地看出所選區(qū)域內(nèi)數(shù)據(jù)點(diǎn)的可分性有了顯著的提升，原本堆疊在一起的數(shù)據(jù)點(diǎn)大致分成了兩條直線，還有一些噪聲點(diǎn)。觀察這次實(shí)驗(yàn)中主方向和垂直方向上的頻數(shù)直方圖，可以發(fā)現(xiàn)主方向的頻數(shù)直方圖上有4個(gè)峰值，垂直方向的頻數(shù)直方圖上僅有一個(gè)峰值。結(jié)合實(shí)際的數(shù)據(jù)標(biāo)簽來看，頻數(shù)直方圖只能從某種程度上反映出有限的數(shù)據(jù)信息，并不能完全依賴于直方圖進(jìn)行聚類，沿著主方向和垂直方向進(jìn)行拉伸的操作更為有效。

使用了t-SNE降維后得到的數(shù)據(jù)點(diǎn)如圖10所示，對(duì)其中的一塊區(qū)域進(jìn)行探索。從原始標(biāo)記中可以看出，選中區(qū)域內(nèi)除了噪聲（粉色）之外有兩個(gè)類。但是經(jīng)過t-SNE的降維，噪聲點(diǎn)和數(shù)據(jù)點(diǎn)混合均勻，甚至兩個(gè)類的數(shù)據(jù)點(diǎn)均勻混合，頻數(shù)直方圖上的信息用途有限。利用拉伸方法進(jìn)行調(diào)節(jié)后，可視化效果并沒有得到很明顯的改善。這說明了選取合適降維方法的重要性，也說明了提供若干降維方法供用戶選擇的合理性。

4.2 MNIST數(shù)據(jù)集

第二組實(shí)驗(yàn)采用了MNIST[24]手寫數(shù)字?jǐn)?shù)據(jù)集。由于原始數(shù)據(jù)集過大，考慮到實(shí)驗(yàn)的需求，本文選取一個(gè)MNIST的子集來近似模擬在MNIST全局上的聚類過程，其中包含了1 797個(gè)數(shù)據(jù)點(diǎn)。使用t-SNE來可視化MNIST數(shù)據(jù)集可以得到非常好的可視化效果，但是由于需要迭代到收斂，t-SNE的運(yùn)行速度較慢。針對(duì)t-SNE的運(yùn)行速度較慢這一問題，有很多加速t-SNE的方法，如Barnes-Hut-SNE[26]和LargeVis[27]等。但是這些優(yōu)化都是從算法層面進(jìn)行時(shí)間開銷的優(yōu)化，從而提升收斂速度。收斂之前計(jì)算出的中間信息是否有用？是否可能在收斂之前提前結(jié)束迭代，通過可視化的交互探索手段，達(dá)到同樣的聚類效果？實(shí)驗(yàn)證明，減少40%的迭代次數(shù)，再通過沿主方向調(diào)整的方法，也可以得到較好的聚類結(jié)果。

Fig.9 Choosing MDS as initial dimension reduction method on artificial dataset圖9 使用MDS作為初始降維方法對(duì)人工合成數(shù)據(jù)集進(jìn)行探索

Fig.10 Choosing t-SNE as initial dimension reduction method on artificial dataset圖10 使用t-SNE作為初始降維方法對(duì)人工合成數(shù)據(jù)集進(jìn)行探索

圖11是在MNIST數(shù)據(jù)集上t-SNE迭代到收斂所得到的效果圖。經(jīng)過實(shí)驗(yàn)證明，這個(gè)過程大約需要迭代140次。以下實(shí)驗(yàn)指出，只需要迭代80次，再加上適當(dāng)?shù)闹鞣较蚶觳僮?，就能夠?qū)崿F(xiàn)比較好的聚類效果。

首先讓t-SNE迭代80次得到一個(gè)初步的可視化結(jié)果。顯然，此時(shí)得到的圖12可分性相比圖11較為糟糕，只能在右圖中找到8個(gè)類。通過對(duì)兩塊數(shù)據(jù)密集的區(qū)域（4號(hào)區(qū)域和7號(hào)區(qū)域）利用主方向進(jìn)行探索（見圖13和圖14），可以將兩個(gè)看似重疊的類分離開來，找到10個(gè)類。

Fig.11 Visualization result of applying t-SNE to MNIST dataset until convergence圖11 MNIST數(shù)據(jù)集利用t-SNE迭代到收斂的可視化結(jié)果

4.3 分析與討論

本文提出的交互式聚類方法的有效性主要體現(xiàn)在兩點(diǎn)：一是使用維數(shù)約簡(jiǎn)對(duì)數(shù)據(jù)進(jìn)行可視分析的有效性；二是利用交互式方法減輕投影重疊，提升聚類分析效率的有效性。

高維數(shù)據(jù)因?yàn)榫S數(shù)過多，各維度之間通常存在冗余，且數(shù)據(jù)點(diǎn)在高維空間內(nèi)過于稀疏，難以挖掘數(shù)據(jù)的本質(zhì)信息和結(jié)構(gòu)。對(duì)高維數(shù)據(jù)進(jìn)行維數(shù)約簡(jiǎn)，不僅可以壓縮數(shù)據(jù)，去除數(shù)據(jù)中噪聲的影響，同時(shí)也可以盡可能地在低維空間保留數(shù)據(jù)在高維空間的一些結(jié)構(gòu)和統(tǒng)計(jì)特性，從而比較好地提升數(shù)據(jù)的可分性，使得聚類分析能夠取得比較好的效果。

Fig.12 Visualization result of applying t-SNE to MNIST dataset(80 iteration times)圖12MNIST數(shù)據(jù)集用t-SNE迭代了80次后的可視化結(jié)果

Fig.13 ExploringArea 4 in Fig.12 with principal direction圖13 利用主方向?qū)D12中的區(qū)域4進(jìn)行探索

Fig.14 ExploringArea 7 in Fig.12 with principal direction圖14 利用主方向?qū)D12中的區(qū)域7進(jìn)行探索

采用可視化的方法對(duì)維數(shù)約簡(jiǎn)后的數(shù)據(jù)在低維空間中進(jìn)行展示，能夠讓用戶對(duì)數(shù)據(jù)的結(jié)構(gòu)和分布有更為直觀的理解。用戶對(duì)數(shù)據(jù)的理解在交互式的探索中有著至關(guān)重要的作用。

投影重疊的問題一方面來自于選取的降維方法不當(dāng)，低維空間的數(shù)據(jù)點(diǎn)不能有效地保持高維空間數(shù)據(jù)的結(jié)構(gòu)性質(zhì)和分布規(guī)律；另一方面來自于低維空間的點(diǎn)點(diǎn)距離不是均勻分布的，為了在有限的空間內(nèi)可視化所有數(shù)據(jù)點(diǎn)，并且保持相對(duì)距離與高維空間相符，距離較近的數(shù)據(jù)點(diǎn)之間會(huì)產(chǎn)生視覺上的重疊，令用戶難以觀察數(shù)據(jù)的局部相對(duì)距離和局部性質(zhì)，影響聚類分析的效果。

局部主方向能夠反映出局部數(shù)據(jù)的方向性，由于主方向具有最大可分性，在該方向上數(shù)據(jù)點(diǎn)的投影能夠盡可能地分開。在局部主方向上采用頻數(shù)直方圖來表征數(shù)據(jù)的分布，能一定程度上體現(xiàn)出數(shù)據(jù)的總體趨勢(shì)和統(tǒng)計(jì)規(guī)律。而采用沿局部主方向改變點(diǎn)點(diǎn)距離的交互手段，數(shù)據(jù)點(diǎn)移動(dòng)的過程能夠讓用戶對(duì)數(shù)據(jù)的局部主方向有比較清晰的認(rèn)識(shí)。拉伸點(diǎn)點(diǎn)距離能夠調(diào)節(jié)局部數(shù)據(jù)點(diǎn)距離之間的差異性，使得原本在視覺上堆疊的數(shù)據(jù)點(diǎn)被區(qū)分開來，令用戶對(duì)數(shù)據(jù)的局部結(jié)構(gòu)和性質(zhì)有比較深刻的了解，從而更好地輔助其進(jìn)行聚類分析。交互式的探索方法能夠提升用戶在聚類分析任務(wù)中的興趣和參與度，充分利用視覺系統(tǒng)的聚類能力，提升聚類分析的效率以及聚類分析結(jié)果和算法的可解釋性。

4.4 局限與不足

本文的交互式聚類方法需要降維方法提供一個(gè)初始的可視化效果。圖15為在MNIST數(shù)據(jù)集上使用不同降維方法后的初始可視化效果，降維方法分別 為 Isomap[28]、LLE[23]、Random Projection、Spectral Embedding[29]、LTSA[30]、MDS[21]、t-SNE[22]。不同的降維方法初始可視化效果差異較大，對(duì)后續(xù)交互式聚類會(huì)造成不同的影響。比如隨機(jī)投影的初始化效果較差，幾乎所有的數(shù)據(jù)點(diǎn)都均勻地混雜在一起，給用戶的局部數(shù)據(jù)點(diǎn)選取和后續(xù)的聚類分析都造成了比較大的困難。

5 用戶調(diào)研

本文采用了用戶調(diào)研的方法，邀請(qǐng)了11位參與者使用該系統(tǒng)進(jìn)行聚類分析并進(jìn)行一定的評(píng)估。采用t-SNE算法在MNIST數(shù)據(jù)集上迭代80次的結(jié)果作為初始的可視化效果。參與者們?cè)诖酥皩?duì)該系統(tǒng)沒有任何的先驗(yàn)知識(shí)。調(diào)研設(shè)置了3個(gè)有具體選項(xiàng)的問題和1次對(duì)系統(tǒng)的綜合評(píng)估采訪，詢問他們使用該系統(tǒng)進(jìn)行聚類分析的體驗(yàn)。

當(dāng)問及系統(tǒng)對(duì)用戶進(jìn)行聚類分析時(shí)的幫助時(shí)，有72.7%（8/11）的調(diào)查對(duì)象選擇了“有幫助”或“很有幫助”，另外3名調(diào)查對(duì)象則選擇了“中立”。3名選擇“中立”的參與者表示，他們隨意選取了3~5個(gè)數(shù)據(jù)點(diǎn)比較密集的區(qū)域，利用主方向的方法進(jìn)行探索，但并沒有發(fā)現(xiàn)更多的類別或是有趣的離群點(diǎn)，因而認(rèn)為該系統(tǒng)的作用比較有限。讓覺得系統(tǒng)“有幫助”和“很有幫助”的參與者對(duì)頻數(shù)直方圖和拉伸方法的幫助度進(jìn)行滿分為5分的數(shù)值評(píng)價(jià)，頻數(shù)直方圖得分均值為3.250。方差為0.188；拉伸方法得分均值為3.625，方差為0.484（見圖16）。由此看來，拉伸方法相對(duì)更有效。在采訪中，參與者表達(dá)出了這樣的困惑：一開始先從哪個(gè)區(qū)域開始探索？探索到什么程度能夠中止？當(dāng)潛在的可探索區(qū)域較多時(shí)，參與者表示并不是非常愿意對(duì)所有的區(qū)域進(jìn)行探索?？傊?，盡管仍有需要改進(jìn)之處，大部分參與者們認(rèn)為該系統(tǒng)對(duì)于輔助聚類分析是有效的，并且認(rèn)可了頻數(shù)直方圖和局部主方向的方法在可視化聚類分析中的重要性。

Fig.15 Initial visualization of MNIST using different dimension reduction methods圖15 在MNIST數(shù)據(jù)集上使用不同降維方法后的初始可視化效果

Fig.16 Comparison between stretching method and histogram method based on mean and standard deviation圖16 頻數(shù)直方圖和拉伸方法得分均值和方差比較

6 總結(jié)與展望

本文創(chuàng)新性地提出了一種基于局部主方向的交互式可視化聚類方法，幫助用戶進(jìn)行聚類分析任務(wù)。同時(shí)提出了一個(gè)用于聚類分析的可視化交互系統(tǒng)。在系統(tǒng)中利用降維方法將數(shù)據(jù)投影到二維平面，然后對(duì)于用戶感興趣區(qū)域內(nèi)的數(shù)據(jù)，提供主方向及其垂直方向上的頻數(shù)直方圖，讓用戶了解數(shù)據(jù)投影的分布情況。用戶可以通過調(diào)節(jié)主方向和垂直方向上的縮放比例參數(shù)，拉伸距離，使得數(shù)據(jù)點(diǎn)沿著主方向和垂直方向移動(dòng)，減少數(shù)據(jù)堆疊的情況，增加數(shù)據(jù)點(diǎn)的可分性。利用本文系統(tǒng)在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行了多組實(shí)驗(yàn)，獲得了較好的效果。并且通過用戶調(diào)研，證明了本文方法的有效性。

本文方法還存在一些局限性，這也是下一步工作中需要考慮解決的問題。首先是初始可視化結(jié)果對(duì)降維方法的依賴。一個(gè)不好的降維方法會(huì)帶來比較糟糕的用戶體驗(yàn)和聚類結(jié)果，增加用戶進(jìn)行聚類分析的難度。其次，數(shù)據(jù)探索區(qū)域的選取依靠用戶的先驗(yàn)知識(shí)或是興趣愛好，沒有一個(gè)統(tǒng)一的標(biāo)準(zhǔn)；縮放的比例也沒有統(tǒng)一的大小，也需要依靠用戶的先驗(yàn)知識(shí)或是多次嘗試。再者，根據(jù)用戶的反饋情況，系統(tǒng)缺乏對(duì)用戶的引導(dǎo)，需要添加對(duì)用戶的啟發(fā)性指導(dǎo)，幫助用戶開始和停止探索。

:

[1]Fahad A,Alshatri N,Tari Z,et al.A survey of clustering algorithms for big data:taxonomy and empirical analysis[J].IEEE Transactions on Emerging Topics in Computing,2014,2(3):267-279.

[2]Ng R T,Han Jiawei.CLARANS:a method for clustering objects for spatial data mining[J].IEEE Transactions on Knowledge and Data Engineering,2002,14(5):1003-1016.

[3]Zhang Tian,Ramakrishnan R,Livny M.BIRCH:an efficient data clustering method for very large databases[C]//Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data,Montreal,Jun 4-6,1996.New York:ACM,1996:103-114.

[4]Guha S,Rastogi R,Shim K.CURE:an efficient clustering algorithm for large databases[C]//Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data,Seattle,Jun 2-4,1998.New York:ACM,1998:73-84.

[5]Ester M,Kriegel H P,Sander J,et al.A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining,Portland,Aug 2-4,1996.Menlo Park:AAAI,1996:226-231.

[6]Ankerst M,Breunig M M,Kriegel H P,et al.OPTICS:ordering points to identify the clustering structure[C]//Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data,Philadelphia,Jun 1-3,1999.New York:ACM,1999:49-60.

[7]Sheikholeslami G,Chatterjee S,Zhang Aidong.WaveCluster:a multi-resolution clustering approach for very large spatial databases[C]//Proceedings of the 24th International Conference on Very Large Data Bases,New York,Aug 24-27,1998.San Mateo:Morgan Kaufmann,1998:428-439.

[8]Wang Wei,Yang Jiong,Muntz R R.STING:a statistical information grid approach to spatial data mining[C]//Proceedings of the 23rd International Conference on Very Large Data Bases,Athens,Aug 25-29,1997.San Mateo:Morgan Kaufmann,1997:186-195.

[9]Dempster A P,Laird N M,Rubin D B.Maximum likelihood from incomplete data via the EM algorithm[J].Journal of the Royal Statistical Society:Series B Methodological,1977,39(1):1-38.

[10]Kohonen T.The self-organizing map[J].Neurocomputing,1998,21(1/3):1-6.

[11]Arnheim R.The Gestalt theory of expression[J].Psychological Review,1949,56(3):156-171.

[12]Woodruff A,Landay J A,Stonebraker M.Constant density visualizations of non-uniform distributions of data[C]//Proceedings of the 11th Annual ACM Symposium on User Interface Software and Technology,San Francisco,Nov 1-4,1998.New York:ACM,1998:19-28.

[13]Dang T N,Wilkinson L,Anand A.Stacking graphic elements to avoid over-plotting[J].IEEE Transactions on Visualization and Computer Graphics,2010,16(6):1044-1052.

[14]Bachthaler S,Weiskopf D.Continuous scatterplots[J].IEEE Transactions on Visualization and Computer Graphics,2008,14(6):1428-1435.

[15]Janetzko H,Hao M C,Mittelst?dt S,et al.Enhancing scatter plots using ellipsoid pixel placement and shading[C]//Proceedings of the 46th Hawaii International Conference on System Sciences,Wailea,Jan 7-10,2013.Washington:IEEE Computer Society,2013:1522-1531.

[16]Yuan Xiaoru,Ren Donghao,Wang Zuchao,et al.Dimension projection matrix/tree:interactive subspace visual exploration and analysis of high dimensional data[J].IEEE Transactions on Visualization and Computer Graphics,2013,19(12):2625-2633.

[17]Chen Haidong,Chen Wei,Mei Honghui,et al.Visual abstraction and exploration of multi-class scatterplots[J].IEEE Transactions on Visualization and Computer Graphics,2014,20(12):1683-1692.

[18]Wei Liyi.Multi-class blue noise sampling[J].ACM Transactions on Graphics,2010,29(4):79.

[19]Zhang Junping,Wang Xiaodan,Krüger U,et al.Principal curve algorithms for partitioning high-dimensional data spaces[J].IEEE Transactions on Neural Networks,2011,22(3):367-380.

[20]Jolliffe I.Principal component analysis[M].New York:John Wiley&Sons,Inc,2002.

[21]Brandes U,Pich C.Eigensolver methods for progressive multidimensional scaling of large data[C]//LNCS 4372:Proceedings of the 14th International Symposium on Graph Drawing,Karlsruhe,Sep 18-20,2006.Berlin,Heidelberg:Springer,2006:42-53.

[22]van der Maaten L,Hinton G.Visualizing data using t-SNE[J].Journal of Machine Learning Research,2008,9(11):2579-2605.

[23]Roweis S T,Saul L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500):2323-2326.

[24]LeCun Y,Cortes C,Burges C J C.The MNIST database of handwritten digits[EB/OL].AT&T Labs.(2010-02)[2017-03-31].http://yann.lecun.com/exdb/mnist.

[25]Forina M,Aeberhard S,Leardi R.Wine data set[EB/OL].(1991-07-01)[2017-03-31].http://archive.ics.uci.edu/ml/datasets/Wine.

[26]van der Maaten L.Accelerating t-SNE using tree-based algorithms[J].Journal of Machine Learning Research,2014,15(1):3221-3245.

[27]Tang Jian,Liu Jingzhou,Zhang Ming,et al.Visualizing largescale and high-dimensional data[C]//Proceedings of the 25th International Conference on World Wide Web,Montreal,Apr 11-15,2016.New York:ACM,2016:287-297.

[28]Tenenbaum J B,de Silva V,Langford J C.A global geometric framework for nonlinear dimensionality reduction[J].Science,2000,290(5500):2319-2323.

[29]Belkin M,Niyogi P.Laplacian eigenmaps for dimensionality reduction and data representation[J].Neural Computation,2003,15(6):1373-1396.

[30]Zhang Zhenyue,Zha Hongyuan.Principal manifolds and nonlinear dimensionality reduction via tangent space alignment[J].SIAM Journal on Scientific Computing,2004,26(1):313-338.