章 蓉 ， 陳 誼 ， 張夢(mèng)錄 ， 孟可欣

(1. 北京工商大學(xué)計(jì)算機(jī)與信息工程學(xué)院 食品安全大數(shù)據(jù)技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室，北京 100048；2. 武漢理工大學(xué)信息工程學(xué)院，湖北 武漢 430070)

聚類算法作為數(shù)據(jù)分析中的一種重要挖掘手段，能夠根據(jù)相似性度量對(duì)混亂、無規(guī)律的原始數(shù)據(jù)自動(dòng)分組，其結(jié)果反映了數(shù)據(jù)內(nèi)部的分布特征和結(jié)構(gòu)模式。并極大地降低了分析人員探索位置數(shù)據(jù)的認(rèn)知負(fù)擔(dān)。馬昱欣等[1]對(duì)比了數(shù)據(jù)挖掘與可視化提取知識(shí)的流程發(fā)現(xiàn)，加入可視化方法后，用戶可以通過視覺通道從結(jié)果中發(fā)現(xiàn)和提取符合需求的數(shù)據(jù)特征和模式[2-3]。同時(shí)視覺模型可以利用交互方式接受用戶的反饋并生成新的可視化結(jié)果，用戶的專業(yè)知識(shí)和任務(wù)需求得到了很好地考慮[4]。SEO和SHNEIDERMAN[5]早在 2002年就提出了一個(gè) Hierarchical Clustering Explorer的交互式可視化工具來探索聚類結(jié)果。隨后，研究者們又陸續(xù)提出了多種交互式聚類可視分析系統(tǒng)[6-9]，將分析的上下文和分析任務(wù)的目標(biāo)與期望相結(jié)合，以幫助用戶更高效地進(jìn)行聚類分析。

越來越多維數(shù)眾多且結(jié)構(gòu)復(fù)雜數(shù)據(jù)的涌現(xiàn)加大了傳統(tǒng)的聚類方法處理這類數(shù)據(jù)的復(fù)雜性和計(jì)算成本，許多更具擴(kuò)展性和交互性的數(shù)據(jù)聚類可視分析系統(tǒng)[10-13]相繼被提出。面對(duì)日益復(fù)雜的海量數(shù)據(jù)，可視分析通過對(duì)聚類算法選擇、模型參數(shù)設(shè)定和分析結(jié)果展示等不同方面進(jìn)行融合，相對(duì)于數(shù)據(jù)挖掘和統(tǒng)計(jì)學(xué)方法，在挖掘聚類結(jié)果和理解聚類過程方面有更大的優(yōu)勢(shì)。許多綜述文章[14-17]大多是針對(duì)數(shù)據(jù)量大為數(shù)據(jù)聚類帶來的問題對(duì)算法進(jìn)行歸納總結(jié)，忽略了高維數(shù)據(jù)“維度詛咒(curse of dimensionality)”問題也為聚類分析提出了不少挑戰(zhàn)。這些挑戰(zhàn)既存在于算法選擇方面，也存在于可視化設(shè)計(jì)方面。本文從高維數(shù)據(jù)進(jìn)行數(shù)據(jù)聚類時(shí)存在的問題出發(fā)，回顧了近10年高維數(shù)據(jù)聚類可視分析取得的研究成果并進(jìn)行了總結(jié)，其主要貢獻(xiàn)為：

(1) 總結(jié)了高維數(shù)據(jù)聚類過程中常用的數(shù)據(jù)處理方法，并對(duì)其性能進(jìn)行了比較。

(2) 總結(jié)了近10年來高維數(shù)據(jù)聚類的2類可視分析方法，包括基于降維及子空間聚類的可視分析方法。

(3) 對(duì)目前高維數(shù)據(jù)聚類可視分析中存在的機(jī)遇與挑戰(zhàn)進(jìn)行了討論。

1 高維數(shù)據(jù)聚類可視分析的基本流程

研究人員進(jìn)行聚類分析的目的主要有2種：①為了減少數(shù)據(jù)量，將聚類結(jié)果作為其他算法的預(yù)處理過程，之后將諸如分類、特征學(xué)習(xí)等算法在檢測(cè)到的簇中進(jìn)行操作；②為了更好地理解數(shù)據(jù)，通過探索有意義的簇及其特征空間來認(rèn)識(shí)數(shù)據(jù)的內(nèi)在結(jié)構(gòu)[18]。前者追求較好的聚類結(jié)果是為了更好地進(jìn)行后續(xù)的分類及特征學(xué)習(xí)，主要是側(cè)重于設(shè)計(jì)和改進(jìn)聚類算法以更好地匹配數(shù)據(jù)集。后者需要研究人員能夠深入數(shù)據(jù)內(nèi)部，發(fā)現(xiàn)和展示數(shù)據(jù)內(nèi)部規(guī)律及隱藏的模式特征。本文主要針對(duì)后者對(duì)近年來高維數(shù)據(jù)聚類可視分析方法進(jìn)行總結(jié)。

聚類本身是一個(gè)探索過程，并且其數(shù)據(jù)通常都是無標(biāo)簽的。在大數(shù)據(jù)時(shí)代，人們對(duì)于收集和存儲(chǔ)原始數(shù)據(jù)的屬性和內(nèi)在結(jié)構(gòu)并不了解，甚至十分陌生，很難直接知曉數(shù)據(jù)集中是否存在聚類模式以及其反映的數(shù)據(jù)內(nèi)部是怎樣的數(shù)據(jù)特征和規(guī)律。即使研究人員根據(jù)領(lǐng)域知識(shí)提前知道數(shù)據(jù)集中可能存在聚類模式，但在聚類算法的選擇和模型參數(shù)的設(shè)定等方面也面臨著巨大的組合空間。高維數(shù)據(jù)的維度可以從幾十維到幾百維不等，在進(jìn)行聚類分析時(shí)不僅需要解決數(shù)據(jù)量大的問題，其自身高維性帶來的“維度詛咒”問題[19]也會(huì)使得傳統(tǒng)聚類算法的結(jié)果非常不理想。除此之外，由于人類自身難以直接構(gòu)建和快速識(shí)別超過三維空間中數(shù)據(jù)的結(jié)構(gòu)和特征，對(duì)高維數(shù)據(jù)的聚類結(jié)果進(jìn)行有效可視化也存在著許多挑戰(zhàn)[20]。例如平行坐標(biāo)是一種常用的多維數(shù)據(jù)可視化方法，但是隨著數(shù)據(jù)量和維度的增加，其視覺紊亂現(xiàn)象會(huì)變得十分嚴(yán)重。同時(shí)平行坐標(biāo)難以呈現(xiàn)非相鄰維度之間數(shù)據(jù)的分布特點(diǎn)。盡管文獻(xiàn)[21-22]對(duì)平行坐標(biāo)做了改進(jìn)，但是單一的可視化方法難以滿足日益增長(zhǎng)的聚類分析需求。

圖1為高維數(shù)據(jù)聚類可視分析的流程圖。高維數(shù)據(jù)聚類可視分析可分為2步: 第1步數(shù)據(jù)建模，即對(duì)高維數(shù)據(jù)進(jìn)行聚類，挖掘數(shù)據(jù)中存在的聚類模式。高維數(shù)據(jù)中“維度詛咒”問題為數(shù)據(jù)聚類帶來最直接的影響是時(shí)間和空間復(fù)雜度呈指數(shù)上升趨勢(shì)以及使度量樣本間相似性的距離度量失去意義。除此之外，“高維性”這一特點(diǎn)也使得數(shù)據(jù)中簇的形成并非依賴于所有維度，而是在部分維度上呈現(xiàn)出聚類模式，且由不同的特征空間構(gòu)成。這些問題都為高維數(shù)據(jù)聚類帶來了許多挑戰(zhàn)。如何從這類具有高維性的復(fù)雜數(shù)據(jù)[23]中挖掘出合適的聚類結(jié)果是高維數(shù)據(jù)聚類可視分析的首要問題。降維和子空間聚類算法是用來有效挖掘高維數(shù)據(jù)中聚類模式的2種數(shù)據(jù)處理方法。其可以幫助研究人員排除高維數(shù)據(jù)中不相干維度的影響，同時(shí)挖掘其中隱藏的聚類模式。

圖1 高維數(shù)據(jù)聚類可視分析流程圖

在挖掘出聚類模式后，高維數(shù)據(jù)聚類可視分析的第2步是利用可視化技術(shù)幫助用戶分析和理解聚類結(jié)果，揭示數(shù)據(jù)內(nèi)部隱藏的結(jié)構(gòu)和關(guān)系。

(1) 聚類結(jié)果分析。其主要針對(duì)無標(biāo)簽數(shù)據(jù)，由于缺乏一致、定量的指標(biāo)評(píng)價(jià)聚類結(jié)果好壞，用戶需要根據(jù)其任務(wù)和自身的專業(yè)知識(shí)來判斷聚類結(jié)果是否符合需求。除此之外，聚類算法、樣本和屬性的不同組合會(huì)對(duì)聚類結(jié)果產(chǎn)生較大的影響，甚至由于算法隨機(jī)挑選的初始點(diǎn)不同，在算法、參數(shù)和樣本等都一致的情況下聚類結(jié)果也可能會(huì)發(fā)生改變。這都為用戶分析和比較不同聚類結(jié)果帶來了挑戰(zhàn)。利用可視化技術(shù)分析聚類結(jié)果能夠?yàn)橛脩敉瑫r(shí)呈現(xiàn)數(shù)據(jù)的不同聚類結(jié)果，通過交互手段幫助用戶比較其異同，發(fā)現(xiàn)其區(qū)別和聯(lián)系，進(jìn)而獲得較好的聚類結(jié)果。然后通過簡(jiǎn)潔交互界面的設(shè)計(jì)發(fā)現(xiàn)簇內(nèi)數(shù)據(jù)點(diǎn)之間的關(guān)聯(lián)關(guān)系[24]，并幫助用戶直觀的了解數(shù)據(jù)項(xiàng)之間的聯(lián)系。

(2) 特征空間分析。簇在特征空間中的分布情況反映了數(shù)據(jù)內(nèi)部的結(jié)構(gòu)和規(guī)律，對(duì)數(shù)據(jù)進(jìn)行聚類分析的目的也是為了幫助用戶自動(dòng)、高效地發(fā)現(xiàn)原始數(shù)據(jù)集中的這些結(jié)構(gòu)和規(guī)律。為此需要探索特征空間維度間的相關(guān)關(guān)系并發(fā)現(xiàn)數(shù)據(jù)在空間中的分布特點(diǎn)[25]。由于聚類算法主要是通過用戶自定義的相似性度量對(duì)數(shù)據(jù)進(jìn)行自動(dòng)分組，這會(huì)使挖掘出的聚類結(jié)果可能存在相互之間沒有實(shí)際關(guān)系或規(guī)律的數(shù)據(jù)被聚集到同一個(gè)簇中。此外高維數(shù)據(jù)中的聚類模式往往不存在于全局空間中，這些都要求用戶能夠準(zhǔn)確發(fā)現(xiàn)并認(rèn)識(shí)不同簇內(nèi)數(shù)據(jù)在其特征空間中的分布。利用可視化技術(shù)，用戶可以直觀的比較不同簇內(nèi)數(shù)據(jù)在其特征空間中的分布情況。同時(shí)通過交互方法可以比較同一簇在不同特征空間的分布情況，并分析和比較其區(qū)別和聯(lián)系，進(jìn)而正確認(rèn)識(shí)數(shù)據(jù)的內(nèi)部結(jié)構(gòu)和規(guī)律。

2 數(shù)據(jù)建模

高維數(shù)據(jù)聚類可視分析的數(shù)據(jù)建模過程是為了幫助用戶挖掘高維數(shù)據(jù)中存在的聚類模式并獲得聚類結(jié)果。在這個(gè)過程中，用戶首先需要對(duì)原始數(shù)據(jù)集進(jìn)行篩選并構(gòu)造特征矩陣，為數(shù)據(jù)處理提供可靠的待分析數(shù)據(jù)；然后對(duì)其進(jìn)行聚類，挖掘數(shù)據(jù)中存在的聚類模式。為了解決這些問題并獲得聚類結(jié)果，目前常用的處理方法是降維和子空間聚類2種。

降維是通過線性或非線性變換，將數(shù)據(jù)從原始的高維空間嵌入至低維空間，在剔除不相干維度影響的同時(shí)使數(shù)據(jù)在低維空間中盡可能保持高維空間中的結(jié)構(gòu)。經(jīng)典的降維方法包括主成分分析[26](principal component analysis，PCA)、線性判別法[27](linear discriminant analysis，LDA)、多維尺度縮放[28](multidimensional scaling，MDS)、等度量映射[29](isometric mapping，isomap)、局部線性嵌入[30](local linear embedding，LLE)、t-SNE[31]等。上節(jié)討論的“維度詛咒”問題是影響高維數(shù)據(jù)聚類的一個(gè)重要因素，通過對(duì)數(shù)據(jù)進(jìn)行降維處理，研究人員可以將高維空間中稀疏的數(shù)據(jù)映射至一個(gè)低維稠密空間，使其空間樣本點(diǎn)之間的距離變得有意義，并作為聚類算法中的相似性度量對(duì)數(shù)據(jù)進(jìn)行自動(dòng)分組。對(duì)降維后的數(shù)據(jù)應(yīng)用諸如 k-means、DBSCAN、層次聚類算法等主流的聚類算法，挖掘數(shù)據(jù)在原高維空間中存在的聚類模式。例如對(duì)于一個(gè)具有500維的數(shù)據(jù)集，首先利用 PCA方法將該數(shù)據(jù)從原始空間降維至10維空間，然后對(duì)其數(shù)據(jù)應(yīng)用DBSCAN的聚類方法獲得聚類結(jié)果。聚類算法用于降維后的數(shù)據(jù)，大大降低了算法的時(shí)間和空間復(fù)雜度。

子空間聚類[32-33]旨在探索存在于高維數(shù)據(jù)子空間中的簇。通過將數(shù)據(jù)的原始特征空間分成不同的子空間以保留原數(shù)據(jù)集中的不同特征，減少了不相關(guān)維度和特征的影響，能夠幫助用戶同時(shí)挖掘數(shù)據(jù)中的簇及其特征空間。在子空間聚類算法中，一般采用2種策略來避免檢索有意義的子空間和發(fā)現(xiàn)聚類模式之間的循環(huán)依賴關(guān)系。根據(jù)策略將子空間聚類算法分為：自底向上搜索網(wǎng)格方法[34-38]和自頂向下搜索迭代方法[39-43]。

3 可視化方法

通過對(duì)高維數(shù)據(jù)聚類可視分析的數(shù)據(jù)建模過程進(jìn)行討論可以看到，降維和子空間聚類這 2種數(shù)據(jù)處理手段都可以用來解決高維數(shù)據(jù)聚類過程中遇到的問題并為用戶提供聚類結(jié)果。但 2種手段解決高維數(shù)據(jù)聚類問題的原理和最后獲得的聚類結(jié)果且有很大的不同，這也會(huì)為后續(xù)分析和理解聚類結(jié)果并認(rèn)識(shí)數(shù)據(jù)內(nèi)部結(jié)構(gòu)和規(guī)律提出不同的需求。

利用降維方法挖掘高維數(shù)據(jù)中的聚類模式，主要目的是通過保持?jǐn)?shù)據(jù)特征在高維空間和低維空間的一致性，使得主流的聚類算法能夠在一個(gè)低維稠密空間挖掘數(shù)據(jù)在原始高維空間中存在的聚類模式，降低由于“高維性”為聚類算法帶來的長(zhǎng)時(shí)間和空間復(fù)雜度。利用子空間聚類方法挖掘高維數(shù)據(jù)中的聚類模式則不需要將高維數(shù)據(jù)映射到低維空間，正如上節(jié)討論的，通過自頂向下或者自底向上的搜索策略能夠直接挖掘出高維數(shù)據(jù)中的聚類模式，同時(shí)用戶還能獲取每個(gè)簇的特征空間。這也是子空間聚類幫助高維數(shù)據(jù)聚類獲得聚類結(jié)果區(qū)別于降維方法的地方，因?yàn)閿?shù)據(jù)從原始高維空間映射至低維空間后，聚類算法在低維空間中所使用的相似性度量涉及到的維度已經(jīng)失去了原有的意義，其可解釋性較差[44]。因此用戶不能獲得構(gòu)成該聚類模式的特征空間。這種差異也為后續(xù)分析聚類結(jié)果提出了不同的要求。

表1對(duì)比了利用降維和子空間聚類方法對(duì)高維數(shù)據(jù)進(jìn)行聚類的性能?？梢钥吹浇稻S方法適用于同一特征空間中的數(shù)據(jù)簇，其為研究人員提供一個(gè)很好的全局概覽。但結(jié)果難以解釋，且用戶很難同時(shí)獲得與該簇相關(guān)的維度集合[45]。一旦維數(shù)增加，全局降維技術(shù)就不是最優(yōu)的，更好的方法是發(fā)現(xiàn)與局部聚類任務(wù)最相關(guān)的子空間[46]。而且利用降維和主流聚類算法的組合挖掘高維數(shù)據(jù)的聚類模式對(duì)聚類結(jié)果的好壞有很大的影響。WENSKOVITCH等[47]已對(duì)可聚類分析中降維和聚類算法的選擇以及應(yīng)用等方面做了總結(jié)。除此之外，降維后的數(shù)據(jù)并不能完全保留高維空間中數(shù)據(jù)項(xiàng)之間的所有關(guān)系，因此在降維過程中很難確定應(yīng)該保留數(shù)據(jù)中的哪個(gè)特征更有利于下一步分析[48]。特別是非線性降維，不同參數(shù)設(shè)置會(huì)顯示哪些數(shù)據(jù)特性都是難以回答的[49]。該問題在利用子空間聚類挖掘高維數(shù)據(jù)中的聚類模式時(shí)則不會(huì)出現(xiàn)，相反的，用戶可以通過子空間聚類挖掘出高維數(shù)據(jù)中可能存在的所有聚類模式并獲得各個(gè)簇的特征空間。盡管子空間聚類的這種優(yōu)勢(shì)可以保證用戶不丟失高維數(shù)據(jù)中的信息，但容易產(chǎn)生冗余信息，例如挖掘出的不同子空間中簇存在重疊現(xiàn)象。其造成更多的計(jì)算時(shí)間，并加大了用戶的認(rèn)知負(fù)擔(dān)，用戶還需從這些結(jié)果中辨別具有意義的聚類結(jié)果。

表1 降維與子空間聚類方法的性能比較

考慮到降維和子空間聚類方法的不同運(yùn)行機(jī)制以及利用2種方法獲得的聚類結(jié)果對(duì)于后續(xù)分析的關(guān)注點(diǎn)不同，本文將高維數(shù)據(jù)聚類可視分析方法分為：基于降維和基于子空間的聚類可視分析方法2大類。

3.1 基于降維的聚類可視分析方法

SEDLMAIR等[50]設(shè)計(jì)了一個(gè)工作流模型，用二維、三維散點(diǎn)圖和散點(diǎn)圖矩陣的可視化技術(shù)來編碼數(shù)據(jù)，并利用矩陣熱圖的形式比較3種技術(shù)對(duì)于數(shù)據(jù)可分性的性能，指導(dǎo)用戶在驗(yàn)證高維數(shù)據(jù)中的聚類結(jié)果可分性時(shí)選擇更好的可視化編碼。GRIPARIS等[51]利用降維方法對(duì)地球觀測(cè)檔案進(jìn)行探索，旨在識(shí)別具有相似語義的內(nèi)容。

通過高亮三維投影空間的數(shù)據(jù)點(diǎn)能幫助用戶發(fā)現(xiàn)具有相似結(jié)構(gòu)的數(shù)據(jù)項(xiàng)，如圖2所示。WANG等[52]提出了一個(gè)感知驅(qū)動(dòng)的線性降維方法，并將其結(jié)果以二維散點(diǎn)圖的可視化形式與其他降維方法進(jìn)行了比較，發(fā)現(xiàn)該方法彌補(bǔ)了監(jiān)督降維方法未考慮到人類的感知能力而導(dǎo)致一些類結(jié)構(gòu)未被研究人員觀察到的情況。

圖2 地球觀測(cè)檔案聚類結(jié)果可視化[51]

隨著維度的增加和數(shù)據(jù)結(jié)構(gòu)也變得更加復(fù)雜，單一的可視化展示已經(jīng)難以滿足分析需求。同時(shí)通過降維和聚類算法對(duì)初始參數(shù)設(shè)定往往不能直接得到較好的結(jié)果，需要研究人員進(jìn)行迭代分析。文獻(xiàn)[46]設(shè)計(jì)了TripAdvisorN-D的可視分析系統(tǒng)(圖3)，該系統(tǒng)從一個(gè)初始的投影散點(diǎn)圖開始，為用戶提供了交互式工具對(duì)數(shù)據(jù)進(jìn)行全局導(dǎo)航和局部探索，分析和認(rèn)識(shí)高維數(shù)據(jù)中簇的分布情況。隨后 WANG和 MUELLER[53]考慮到人們?nèi)狈φ嬲斫獬^三個(gè)維度空間的能力，在 TripAdvisorN-D的基礎(chǔ)上設(shè)計(jì)并開發(fā)了一個(gè)Subspace Voyager系統(tǒng)。該系統(tǒng)為用戶生成一組連續(xù)的三維子空間并將數(shù)據(jù)投影到其中，顯示為軌跡球。用戶可以通過旋轉(zhuǎn)、跳轉(zhuǎn)、拖拽、保存等手段對(duì)高維數(shù)據(jù)進(jìn)行可視化聚類分析。但這些都過于依賴用戶手動(dòng)調(diào)整參數(shù)，缺乏指導(dǎo)性意見來幫助用戶發(fā)現(xiàn)分析簇。XIA等[54]提出了基于投票的投影推薦框架并開發(fā)了一個(gè)可視分析系統(tǒng)。用戶在初始投影中發(fā)現(xiàn)聚類模式后，可以選定該簇，這時(shí)系統(tǒng)會(huì)自動(dòng)推薦一個(gè)效果更佳的投影讓用戶識(shí)別出該簇。當(dāng)系統(tǒng)沒有更好地推薦時(shí)，用戶可以人為地調(diào)整投影結(jié)果。圖 4為該系統(tǒng)的一個(gè)實(shí)例分析過程。與其類似，LAI等[55]希望通過增強(qiáng)局部投影探索高維數(shù)據(jù)，為此開發(fā)了FocusChanger系統(tǒng)，該系統(tǒng)能夠半自動(dòng)地幫助用戶進(jìn)行聚類分析，使人的分析能力充分和機(jī)器的計(jì)算能力相結(jié)合。

圖3 TripAdvisorN-D系統(tǒng)界面[46]

將深度學(xué)習(xí)模型的隱藏層作為降維的一種特殊形式也受到廣泛關(guān)注。ZHANG等[56]通過無監(jiān)督深度學(xué)習(xí)框架發(fā)現(xiàn)的簇反映了鄰域的深層特征。HAN等[57]首次將深度學(xué)習(xí)技術(shù)應(yīng)用到流數(shù)據(jù)的特征學(xué)習(xí)中,并提出將 FlowNet網(wǎng)絡(luò)的輸入集劃分為簇，這些簇中蘊(yùn)藏著最能捕獲底層流特性和模式的子集，圖5為FlowNet網(wǎng)絡(luò)框架圖，圖6為結(jié)果可視化效果圖。

通過文獻(xiàn)可知，基于降維的高維數(shù)據(jù)聚類可視分析方法主要是通過散點(diǎn)圖或以散點(diǎn)圖為主視圖，其他視圖輔助的多視圖協(xié)同技術(shù)分析高維數(shù)據(jù)的聚類結(jié)果。在早期，研究人員通過散點(diǎn)圖的各種形式如二維散點(diǎn)圖、散點(diǎn)圖矩陣等方式對(duì)聚類結(jié)果進(jìn)行投影，投影圖中點(diǎn)與點(diǎn)之間的位置關(guān)系反映了各點(diǎn)之間的相似程度，而用戶也能很好地通過位置關(guān)系來辨別不同降維和聚類算法組合獲得的聚類結(jié)果之間的好壞。隨著數(shù)據(jù)集及維度數(shù)量變大，更具交互和指導(dǎo)性的可視化方案設(shè)計(jì)出現(xiàn)，這也正是本節(jié)開始討論的利用降維方法解決高維數(shù)據(jù)聚類問題帶來的挑戰(zhàn)決定的。根據(jù)表1可以看到，研究人員很難直接知道降維后的數(shù)據(jù)對(duì)于數(shù)據(jù)在原始高維空間中特征的保留情況，特別是隨著數(shù)據(jù)量和維度數(shù)量的增加以及目前對(duì)于深度學(xué)習(xí)的火熱研究，更加大了該問題的難度。因此能夠提供指導(dǎo)信息來引導(dǎo)研究人員下一步操作的半自動(dòng)化可視分析方案變得越來越重要。同時(shí)設(shè)計(jì)多個(gè)視圖來輔助研究人員分析當(dāng)前狀態(tài)下聚類結(jié)果反映的數(shù)據(jù)特征，以提供交互方法來調(diào)整算法參數(shù)并獲得更好的聚類結(jié)果的需求也變得更加重要。

圖4 文獻(xiàn)[54]實(shí)例分析過程圖

圖5 FlowNet網(wǎng)絡(luò)框架圖[57]

圖6 FlowNet實(shí)例結(jié)果圖[57]

3.2 基于子空間聚類的可視分析方法

ASSENT等[58]指出現(xiàn)有的子空間聚類方法缺乏交互可視化，同時(shí)目前算法對(duì)子空間的維數(shù)存在偏倚，即未考慮到不同子空間中維度的密度是不可比的。在此基礎(chǔ)上，作者提出了維數(shù)無偏子空間聚類和子空間簇的距離函數(shù)，同時(shí)設(shè)計(jì)了 2個(gè)可視化工具允許用戶瀏覽整個(gè)子空間集群，放大到單個(gè)對(duì)象，深入分析子空間集群特征。該系統(tǒng)的不足之處是不支持相應(yīng)子空間中數(shù)據(jù)分布的可視化比較。Heidi Matrix[59]基于每個(gè)子空間中k個(gè)最近鄰點(diǎn)的計(jì)算，使用二維矩陣加以顏色映射呈現(xiàn)數(shù)據(jù)集中的簇，同時(shí)還比較了這些簇在不同的特征空間中是否有重疊的數(shù)據(jù)分布情況。FERDOSI等[60]提出了一種用于聚類子空間排序方法，克服了許多聚類算法要求用戶在沒有任何指導(dǎo)原則的情況下，設(shè)置大量的參數(shù)和難以反映當(dāng)前集群的數(shù)量或集群的重要性等問題，其設(shè)計(jì)的可視化系統(tǒng)以樹形結(jié)構(gòu)幫助用戶交互選擇各個(gè)子空間，并對(duì)其數(shù)據(jù)分布情況進(jìn)行呈現(xiàn)。YUAN等[61]提出了層次化的交互式子空間可視分析方法，圖7為Dimension Projection Matrix/Tree工作流程圖。該方法包括 2種新的探索視圖，其一是維度投影矩陣，在矩陣中，每行或每列表示一組維度，每

個(gè)單元格顯示具有相應(yīng)維度的數(shù)據(jù)的維度投影；其二是維度投影樹，其中每個(gè)節(jié)點(diǎn)是維度投影矩陣。該方法能夠同時(shí)探索高維數(shù)據(jù)的數(shù)據(jù)相關(guān)關(guān)系和維度間的相關(guān)關(guān)系。

圖7 維度投影矩陣/樹工作流程圖[61]

簇的特征空間分析在聚類分析中也是一個(gè)非常重要的研究工作，其能幫助用戶發(fā)現(xiàn)數(shù)據(jù)內(nèi)部結(jié)構(gòu)和分布規(guī)律。2015年 WATANABE等[62]基于雙聚類技術(shù)提出一種提取特征子空間的新方法。與傳統(tǒng)方法不同，高相關(guān)的維度被自動(dòng)分組形成子空間。在傳統(tǒng)的平行坐標(biāo)上，通過增加聚類的平行坐標(biāo)圖(Clustered PCP)和聚合的平行坐標(biāo)圖(Contracted PCP)來幫助用戶對(duì)特征空間進(jìn)行比較。夏佳志等[63]認(rèn)為維度間的相關(guān)性往往存在著數(shù)據(jù)上局部性，即不同數(shù)據(jù)子集體現(xiàn)出不同的維度相關(guān)性。在全局相關(guān)性分析時(shí)，這種維度局部相關(guān)性往往被掩蓋，為此，提出一種基于子空間聚類的局部相關(guān)性可視分析方法。幫助用戶發(fā)現(xiàn)簇內(nèi)維度之間的局部相關(guān)關(guān)系。圖8為其系統(tǒng)圖。隨后 XIA等[64]又提出一種基于維度相關(guān)性的子空間聚類可視方法，其開發(fā)的系統(tǒng)使用戶能不斷挑選相關(guān)性較高的維度構(gòu)成子空間并可視化數(shù)據(jù)在子空間中的分布情況。不僅能幫助用戶了解各維度間相關(guān)性大小，同時(shí)還能比較同一個(gè)簇在不同子空間中的分布情況。圖9為該系統(tǒng)的實(shí)例分析過程。值得一提的是，在進(jìn)行子空間聚類時(shí)，有一些簇可能在數(shù)據(jù)的原始維度中難以發(fā)現(xiàn)，但在一些重構(gòu)的維度構(gòu)成的空間中發(fā)現(xiàn)。ZHOU等[65]提出了一種基于維度重建的高維數(shù)據(jù)子空間聚類可視分析方法。該方法能夠從子空間的數(shù)據(jù)投影中重建新維度，以保留有趣的集群信息。圖10為文獻(xiàn)[65]提出的交互式子空間分析的維度重建概念圖，重建的維度包含在具有原始維度的分析工作流程中，以幫助用戶構(gòu)建能夠清楚地顯示聚類模式的子空間。為了避免子空間聚類算法挖掘出冗余信息，LEHMANN和THEISEL[66]提出了一種尋找相關(guān)投影的新方法。通過定義一個(gè)度量來衡量加入新的維度構(gòu)成的子空間投影中簇類效果是否會(huì)增加，如果有則成為新的投影，否則舍棄。這樣很好地避免了子空間聚類出現(xiàn)冗余的問題。

通過上述文獻(xiàn)可以看到，基于子空間的高維數(shù)據(jù)聚類可視分析方法同樣是以散點(diǎn)圖的形式來分析聚類結(jié)果，用戶可以通過點(diǎn)與點(diǎn)之間的距離直觀、快速地獲得數(shù)據(jù)內(nèi)部簇的分布情況。與基于降維的高維數(shù)據(jù)可視分析方法不同，由于子空間聚類本身可以發(fā)現(xiàn)高維數(shù)據(jù)內(nèi)部所有可能存在的聚類模式，不會(huì)產(chǎn)生信息丟失的情況，而且在發(fā)現(xiàn)聚類模式的同時(shí)還能抽取出相應(yīng)的特征空間，因此用戶不用像采用降維的方法那樣，去分析聚類結(jié)果中保留了哪種數(shù)據(jù)特征和降維過程中會(huì)產(chǎn)生哪些信息的丟失。相反的，在基于子空間聚類的分析中用戶需要辨別聚類結(jié)果中的冗余信息，比較不同簇之間是否存在折疊、交叉等情況，這導(dǎo)致在設(shè)計(jì)可視化方案時(shí)需要提供更多便捷的交互方法以觀察數(shù)據(jù)在不同特征空間的分布情況。除此之外，由于子空間聚類算法的運(yùn)行機(jī)制，即自頂向下和自底向上的搜索機(jī)制帶有一定的層次結(jié)構(gòu)，特別是自底向上的搜索機(jī)制，因此在基于子空間聚類的高維數(shù)據(jù)聚類可視分析中，也常常會(huì)出現(xiàn)樹形或類樹形的可視化方案來幫助用戶發(fā)現(xiàn)不同層面的子空間中簇內(nèi)數(shù)據(jù)的分布情況。

圖8 基于子空間聚類的局部相關(guān)性可視分析系統(tǒng)[63]

圖9 基于維度相關(guān)性的子空間聚類可視方法實(shí)例分析過程

圖10 交互式子空間分析的維度重建概念圖[65]

4 小 結(jié)

通過總結(jié)高維數(shù)據(jù)聚類過程中常用的數(shù)據(jù)處理方法及其可視化方法?？梢钥吹浇换ナ娇梢暦治瞿軌驇椭芯咳藛T從多角度對(duì)高維數(shù)據(jù)的聚類過程和結(jié)果進(jìn)行探索和分析，并發(fā)現(xiàn)其內(nèi)部規(guī)律和分布特征。表2對(duì)高維數(shù)據(jù)聚類可視分析方法進(jìn)行了總結(jié)。

由表2可以看到，基于降維的聚類可視分析方法主要是分析通過降維后挖掘出的聚類結(jié)果是否很好地保留了其在原始空間中的特征以及保留了哪種特征，進(jìn)而幫助用戶獲得較好的聚類結(jié)果。盡管線性和非線性降維都可以找到低維空間并從中挖掘聚類模式，但是線性降維是通過尋找一個(gè)線性函數(shù)將數(shù)據(jù)從高維空間映射至低維空間，并平衡了全局?jǐn)?shù)據(jù)，但會(huì)導(dǎo)致一些數(shù)據(jù)項(xiàng)在低維空間處于錯(cuò)誤位置，造成這些點(diǎn)的周圍信息丟失，使得原始高維空間中一些特征沒有很好地保留下來。利用可視化方法對(duì)其聚類結(jié)果進(jìn)行分析時(shí)，用戶需要獲得原始空間對(duì)于降維后空間的影響程度，且通過調(diào)整維度的重要性來修改降維過程保留的特征，通過設(shè)計(jì)一個(gè)較為連續(xù)的變化視圖來觀察維度重要性的變化對(duì)于聚類結(jié)果的影響，使得這些錯(cuò)誤信息得到修正。而非線性降維是通過保留數(shù)據(jù)項(xiàng)的周圍信息將數(shù)據(jù)從高維空間映射至低維空間，且未考慮全局?jǐn)?shù)據(jù)之間的關(guān)系，致使原始空間中的維度對(duì)于降維后空間的影響作用也難以獲得，同時(shí)加大了其結(jié)果解釋性的難度。用戶對(duì)參數(shù)進(jìn)行設(shè)置較困難，研究人員很難回答不同的參數(shù)設(shè)置會(huì)保留哪些數(shù)據(jù)特征。

基于子空間聚類的可視分析方法不僅可以獲得高維數(shù)據(jù)中所有的聚類模式，同時(shí)可以獲得簇的特征空間，在這個(gè)過程中極少甚至不會(huì)存在信息丟失，為用戶分析數(shù)據(jù)內(nèi)部結(jié)構(gòu)和規(guī)律提供了可靠的模式來源。但是在子空間聚類的2種不同搜索策略下，獲得的聚類結(jié)果也會(huì)有差異。通過自頂向下的搜索策略可將數(shù)據(jù)集初始化分為k個(gè)部分，并賦予每個(gè)簇相同權(quán)值，然后重復(fù)采用某種策略對(duì)初始簇不斷改進(jìn)并更新權(quán)值，最終獲得聚類結(jié)果。利用該搜索策略進(jìn)行的子空間聚類不會(huì)產(chǎn)生重復(fù)的簇。而自底向上的搜索策略則是利用了關(guān)聯(lián)規(guī)則中的先驗(yàn)性質(zhì)，即如果一個(gè)k維單元存在聚類模式，那么在k–1維空間中也存在聚類模式。反之，如果一個(gè)k維單元不存在聚類模式，那么在k–1維空間中也不存在聚類模式。從一維開始，不斷向上搜索，最后獲得聚類結(jié)果。通過這種搜索策略對(duì)數(shù)據(jù)集的全面挖掘，不會(huì)失去任何一個(gè)簇信息，但是這樣也極易挖掘出冗余信息。相比于自頂向下的子空間聚類算法，自底向上的子空間聚類算法設(shè)計(jì)的可視化方案，除了能夠幫助用戶深入不同子空間分析簇內(nèi)數(shù)據(jù)的分布，比較其分布之間的差異，在獲得正確認(rèn)識(shí)數(shù)據(jù)內(nèi)部結(jié)構(gòu)之外，還需要避免冗余信息的挖掘，降低認(rèn)知負(fù)擔(dān)，使得用戶能夠更高效地認(rèn)識(shí)數(shù)據(jù)。

表2 高維數(shù)據(jù)聚類可視分析方法總結(jié)

5 機(jī)遇與挑戰(zhàn)

利用交互式可視化方法對(duì)高維數(shù)據(jù)進(jìn)行聚類分析，可以充分結(jié)合人的認(rèn)知能力和計(jì)算機(jī)強(qiáng)大的計(jì)算存儲(chǔ)能力，幫助研究人員認(rèn)識(shí)和了解數(shù)據(jù)的內(nèi)部結(jié)構(gòu)以及數(shù)據(jù)規(guī)律。然而隨著收集到高維數(shù)據(jù)的數(shù)據(jù)量不斷增加，維度間的關(guān)系更加錯(cuò)綜復(fù)雜，高維數(shù)據(jù)聚類可視分析仍具有重要的研究意義：

(1) 研究聚類可視分析過程中的不確定性。該研究需求來自于基于降維的高維數(shù)據(jù)可視分析方法。降維方法不可避免地會(huì)產(chǎn)生數(shù)據(jù)信息丟失問題，是由于維度對(duì)于影響降維后空間重要性的不確定性造成的，其影響了降維過程中特征的保留。這種不確定性對(duì)于用戶來說都是透明的，即使用戶能夠感知到這些失真和丟失信息[67]，但難以通過交互手段來控制和調(diào)整這些錯(cuò)誤[68]，進(jìn)而導(dǎo)致其結(jié)果不能令人信服[69-70]。除此之外，由于聚類本身是一個(gè)無監(jiān)督的學(xué)習(xí)方法，主要針對(duì)無標(biāo)簽數(shù)據(jù),并且不同領(lǐng)域的用戶對(duì)于同一個(gè)數(shù)據(jù)集會(huì)出現(xiàn)不同分析需求，這都加大了算法選擇和參數(shù)設(shè)定的不確定性。例如對(duì)于電子健康記錄進(jìn)行聚類分析，心臟病專家希望通過心血管癥狀對(duì)其進(jìn)行分組，而教練可能希望通過與其運(yùn)動(dòng)技能相關(guān)的特征進(jìn)行分組[71]。因此通過研究不確定性，用戶可以根據(jù)自身的需求接受當(dāng)前聚類結(jié)果或重新調(diào)整參數(shù)以獲得更優(yōu)的聚類結(jié)果。

(2) 優(yōu)化交互方式。其主要是針對(duì)基于子空間聚類的高維數(shù)據(jù)可視分析方法。子空間聚類可以為用戶挖掘出高維數(shù)據(jù)中所有的聚類模式及其特征空間，并且在這個(gè)過程中不會(huì)發(fā)生損失。但是也會(huì)帶來信息冗余的問題，這大大加重了用戶的認(rèn)識(shí)負(fù)擔(dān)。同時(shí)可造成挖掘出的一些聚類模式?jīng)]有實(shí)際意義，相互之間存在重疊等問題。因此需要設(shè)計(jì)出便捷的交互方案來幫助用戶識(shí)別、篩選出有意義的聚類模式并分析模式反映的數(shù)據(jù)特征，進(jìn)而更好地認(rèn)識(shí)和了解數(shù)據(jù)內(nèi)部結(jié)構(gòu)。目前，對(duì)于同時(shí)探索數(shù)據(jù)集中的簇及其特征空間時(shí)常常采用不同的方法，解釋不同方法挖掘到的簇及其特征空間也會(huì)增加研究人員的認(rèn)知識(shí)別負(fù)擔(dān)[72]。需要設(shè)計(jì)一致的可視化表示與平滑的交互方法來探索和發(fā)現(xiàn)簇及其特征空間。

(3) 設(shè)計(jì)更具指導(dǎo)性的可視分析系統(tǒng)其對(duì)于基于降維和基于子空間聚類的高維數(shù)據(jù)聚類可視分析來說都是有用的。對(duì)于普通用戶而言，直接對(duì)各種參數(shù)進(jìn)行設(shè)定并獲得正確的結(jié)果是很難的，哪怕對(duì)具有極高專業(yè)知識(shí)的研究人員而言也不是一個(gè)簡(jiǎn)單的事情。設(shè)計(jì)具指導(dǎo)性的可視分析系統(tǒng)能夠幫助用戶更高效地進(jìn)行分析。XIA等[73]提出了一個(gè)探索性的可視化分析方法LDSScanner，為用戶提供了選擇適當(dāng)模型所需的上下文信息。SACHA等[74]開發(fā)的SOMFlow系統(tǒng)提供了一個(gè)自定義的度量，以指導(dǎo)用戶的下一步行動(dòng)。文獻(xiàn)[11]提出了一個(gè) the Clustering Tour的新特征，該特征可以根據(jù)集群配置、數(shù)據(jù)特性和用戶反饋為用戶進(jìn)行推薦。TATU等[75]通過定義子空間相似性來處理子空間冗余的問題?？梢钥吹皆O(shè)計(jì)和實(shí)現(xiàn)更具指導(dǎo)性的聚類可視分析系統(tǒng)能更好地幫助用戶有效地在空間中進(jìn)行搜索，理解數(shù)據(jù)的內(nèi)部結(jié)構(gòu)，避免一些無用工作的進(jìn)行。

6 結(jié) 束 語

可視分析技術(shù)是高維數(shù)據(jù)聚類分析的一個(gè)有效的手段。本文首先總結(jié)了高維數(shù)據(jù)聚類過程中常用的數(shù)據(jù)處理方法并對(duì)其性能進(jìn)行了比較；隨之對(duì)近 10年高維數(shù)據(jù)聚類可視分析的研究成果進(jìn)行了總結(jié)；最后指出了該領(lǐng)域存在的機(jī)遇與挑戰(zhàn)。