基于密度峰值的云變換加速機制

楊 潔，王國胤，龐紫玲

1(重慶郵電大學 計算智能重慶市重點實驗室，重慶 400065)

2(遵義師范學院 物理與電子科學學院，貴州 遵義 563002)

1 引 言

粒計算[1]是基于多層次粒結構研究思維方式、問題求解方法、信息處理模式的理論.早在1997年，Zadeh教授[2]就提出了粒計算是模糊信息粒化、粗糙集理論和區間計算的超集，是粒數學的子集.粒計算并不是個具體的計算理論模型或方法，而是一種方法論.在粒計算的“大傘”之下，粒計算包含了很多具體的粒化模型，如模糊集[2]、粗糙集[3]、商空間[4]、云模型[5]等.這幾種粒化模型分別從不同的角度描述人類從不同粒度解決問題的能力，有著嚴謹的約束條件，但是同時也具有一定的局限性.

云模型[5]是李德毅院士于1995年在概率論和模糊理論兩者的基礎上提出的定性概念與其定量表現形式的雙向轉換模型.其中，正向云變換(Forward Cloud Transformation，FCT)和逆向云變換(Backward Cloud Transformation，BCT)是實現雙向認知變換的重要工具.如圖1所示，通過FCT和BCT，云模型可以實現內涵與外延的雙向轉換.

圖1 云模型雙向認知轉換圖Fig.1 Bidirectional cognitive transformation of cloud model

與其他粒化模型對信息的硬劃分不同，由于定性概念的外延往往是不確定的、模糊的、變化的，涉及到隨機性和模糊性兩種不確定性，云模型將模糊理論與概率論相結合，通過三個特征參數：(Ex，En，He)，可以度量一個定性概念的信息粒度，可以實現對信息的軟劃分.其中，Ex代表期望，可以作為概念粒度的基本確定性衡量；En代表熵，可以作為粒度的不確定性度量，由概念的隨機性和模糊性共同決定;He代表超熵，可以將定性概念的隨機性約束弱化為某種“泛正態分布”，反映定性概念所對應的隨機變量偏離正態分布的程度.通過En和He可以構建概念含混度用來衡量概念的共識程度，為一個基本概念的表征，計算和度量提供了基礎.由于這種粒化方式考慮了數據的概率分布，獲取的知識具有更強的泛化能力，而且利用云模型進行粒化不需要先驗知識，它可以從原始數據中統計規律，實現定量到定性概念的轉換.

自適應高斯云變換 (Adaptive Gaussian cloud transform，AGCT)[6]，是眾多云模型粒計算機制中最為合理的一種方法.AGCT可以根據不確定性概念在不同粒度層次上的不同表現形式，建立了一種多粒度的推理模型與方法，該方法直接從數據中獲得不同粒度層次的云概念，從數據擬合的角度實現了從細粒度概念到粗粒度概念的躍升.但AGCT只能通過逐層學習達到概念層次躍升.當數據樣本較龐大時，采用逐層變粒度的方法必然比較耗時，時間復雜度為O(m2N)，其中m為初始波峰數,N為樣本個數.因此，AGCT很難滿足時限約束條件下的變粒度有效計算.如果能利用關鍵信息粒進行加速計算，實現跨層的變粒度機制，那么對于概念的提取將在很大程度上減少時間的損耗.

2014年在《Science》發表的論文“Clustering by fast search and find of density peaks[7]，DPC”(密度峰值聚類)提出的局部密度和相對距離這兩個假設能夠有效、快速的發現任意形狀的簇.該方法融合K-medoids[8]，DBSCAN[9]和mean-shift[10]聚類的特點，簡潔新穎.密度峰值算法的提出引起學界廣泛關注，并且已經應用于許多領域，包括圖像中人物的年齡估計[11]、計算機視覺中的基礎矩陣估計[12]、分析化學[13]、社交網絡[14].因此，DPC新穎而簡潔思路可以為我們解決AGCT時間復雜度過高的問題提供思路.

本文第2節簡要介紹了密度峰值、高斯云變換的一些基本知識，并分析了AGCT存在的問題.第3節圍繞這些基本問題，分析了利用密度峰值的思想改進AGCT的可行性并給出改進算法；第4節通過實驗驗證了改進算法的優越性；最后是研究展望與總結.

2 相關定義

2.1 密度峰值聚類

密度峰值聚類算法的核心思想在對于聚類中心的刻畫上.文獻[7]認為聚類中心同時具有以下兩個特點：

1)本身的密度大，即被比它密度小的鄰居點包圍；

2)與比它密度更大的數據點之間的距離相對更大.

在這樣的模型中，密度峰值聚類主要有兩個需要計算的量：第一，局部密度ρ；第二，相對距離δ.局部密度和相對距離的定義分別如下：

定義1[7].樣本點i的局部密度，定義如下

(1)

其中

定義2[7].樣本點i的相對距離

(2)

其中，指標集

如圖2(a)所示，為二維散點圖，其中樣本點編號代表自身的局部密度，不同的顏色代表不同的類.圖2(b)為以局部密度為橫坐標和相對距離為縱坐標產生的圖2(a)的數據對應的決策圖，決策圖為我們提供了一種手動選取聚類中心的啟發式方法.在圖2(b)中選擇局部密度ρ和相對距離δ同時相對較大的(矩形虛線內的點)，由于這些點的密度較大，鄰域中的鄰居點較多，并且與比它密度更大的點的距離較遠，所以將這些點標記聚類中心.

圖2 中心點選取例子Fig.2 Example of choosing centers

2.2 高斯云變換

概念層次在數據挖掘中有著重要的作用.通過自動生成概念層次，可有效地提高數據挖掘的效率，在不同層次上發現知識[15].由于數據庫中大量存在各種數值型屬性，傳統的一些概念層次生成算法[16-18]都只能對論域進行硬劃分，并不能很好的反映數據的分布狀況.同時，這些算法都只能生成概念樹，且概念爬升比較機械，不能反映定性概念的模糊性、隨機性以及不同層次概念之間的多隸屬關系.由于基于云模型的粒化方式考慮了數據的概率分布，獲取的知識具有更強的泛化能力.因此，結合虛擬泛概念樹的躍升原理，建立多層次、多粒度的概念外延空間成為云模型研究的一個方向.

圖3 AGCT對院士群體聚類形成的多粒度概念[6]Fig.3 Multi-granularity concepts of academician group by AGCT

劉玉超和李德毅等[6]根據不確定性概念在不同粒度層次上的不同表現形式，提出了自適應高斯云變換(AGCT)，建立了一種多粒度的推理模型與方法，該方法直接從數據中獲得不同粒度層次的云概念，從數據擬合的角度實現了從細粒度概念到粗粒度概念的躍升.圖3為利用AGCT對中國工程院院士群體進行云變換得到的不同概念層次.

因此，高斯云變換是一個聚類的過程，也是一個變粒度計算的過程，甚至可以說是一個深度學習的過程.與單純的逆向云算法比較，對于任意一個給定的數據集而言，難以僅用一個定性概念來描述，則通過高斯云變換可生成多個不同粒度的概念，這比用逆向云算法生成的單個概念更具有普遍性.

圖4 利用AGCT進行粒度空間優化Fig.4 Granular optimization by AGCT

圖4展示了一個利用AGCT實現粒度空間優化的例子，通過實際約束條件調節概念含混度，可以實現不同粒度層次上對遙感圖像進行圖像分割，使其不同的概念層次具有不同的分割結果，最終提取符合人類認知的概念個數，從而實現了概念數量，粒層和層次的生成，選擇和優化問題.

3 基于密度峰值的云變換加速機制

3.1 跨層機制

面對大數據分析帶來的挑戰，數據分析的重心從算法的研究轉移到數據表達模型的研究.以往的計算方法以算法為中心，重點在于降低算法的時間復雜度，但在大數據環境下，即使是具有較低時間復雜度的算法仍然難以保證計算的有效性.將計算方法轉變為以數據為中心，研究變粒度機制，可以實現數據的多粒度表達，做到將數據規模變小，從而提供“有效”計算.其中，利用關鍵信息粒加速計算可以再很大程度上減少不必要的時間損耗，其目的是在較低粒層上依據信息粒的價值度量識別出關鍵信息粒，由其狀態的改變，直接觸發高層信息粒的改變，實現跨層機制，從而做出決策，采取行動，為建立滿足時限約束條件的變粒度有效計算模型提供條件.

如圖5所示的整個粒空間結構中，Layerk表示最細粒度的粒層，其中各個小圓點代表最細粒度數據，具有同類關系的數據構成信息粒.Layert是粒空間結構中的某一粒層，通過利用該層中關鍵信息粒實現跨層機制，從而無需經過Layers層直接躍升到Layerr層，在一定程度上減少了變粒度過程所需的時間.

3.2 自適應云變換加速機制

由第2.1節可知，基于對聚類中心點的假設，密度峰值聚類算法可以快速尋找中心點，但是要尋找中心點必須要計算每個樣本點的局部密度，而計算局部密度的距離矩陣代價時間復雜度較大，需要O(N2).AGCT根據數據樣本的的頻度來進行數據擬合，通過去抖動后得到波峰數及其位置信息分別作為初始云模型的數目和期望，文獻[6]認為數據樣本點的頻率與其對概念的貢獻度成正比，即高頻率的數據對概念的貢獻較大；反之，低頻率的數據對概念的貢獻較小.受密度峰值聚類思想啟發，對于灰度直方圖來說，那些頻度相對較大且離比它頻度大的點相對遠的數據點才是概念的主要貢獻點.因此，在AGCT算法中，通過選取這樣的數據點為初始云概念提供先驗知識，可以很大程度上降低云變換的時間復雜度.

圖5 跨層機制示意圖Fig.5 Schematic of cross layer mechanism

本文基于自適應高斯云變換通過統計樣本頻度進行云變換的原理，借鑒密度峰值的思想，通過遍歷計算每個樣本點的頻度，把它們各自的頻度當成是DPC中的局部密度來快速尋找中心點，為AGCT的初始峰值的選取提供先驗信息，直接從細粒度躍升到較粗粒度上面進行變粒度機制，從而實現云變換加速機制.由于距離矩陣是基于論域的，而通常情況下，尤其是對于圖像來說，論域的取值范圍遠遠小于樣本點個數，因此，計算論域取值之間的距離代價也相對較小.該算法在保證概念抽象精度的前提下，從很大程度上減少時間復雜度.如算法1所示，為本文基于密度峰值提出的啟發式云變換加速機制(Heuristic Gaussian Cloud Transfromation based on Density peaks，HGCT_DP)

算法1.基于密度峰值的啟發式云變換(HGCT_DP)

輸入：數據樣本集X{xi|i=1，2，…，N}的頻率直方圖p(xi)以及論域{yj|j=1，2，…，N′}

輸出：m個高斯云C(Exk，Enk，Hek)|k=1，2，…，m′

①根據p(xi)計算論域中每個取值yj的頻度ρi以及相對距離δj；

②通過p(xi)和δj輸出決策圖，選取聚類中心centerk|k=1，2，…，m，并記錄這個m個點的信息，作為概念數量的初始值.

③將②中m個中心點的信息作為高斯變換的輸入，并轉換成m個高斯分布；

G(μk，δk)|k=1，2，…，m′

④對于第k個高斯分布，計算其標準差的縮放比αk，則第k個表征概念的高斯云參數為：

Exk=μk

Enk=(1+αk)*σk/2

Hek=(1-αk)*σk/6

CDk=(1-αk)/(1+αk)

從而得到k個云模型.

在算法1中，m′的選取我們采用冗余法，選取3～5倍直觀中心點的個數.

算法2.自適應云變換加速機制(AGCT_acc)

輸入：數據樣本集X{xi|i=1，2，…，N}，概念含混度閾值β

輸出：M個高斯云模型

① 統計數據樣本集X{xi|i=1，2，…，N}的頻率直方圖p(xi)

②利用HGCT_DP算法將數據集X{xi|i=1，2，…，N}聚類成m個高斯云C(Exk，Enk，Hek)|k=1，2，…，m′；

③ 按含混度順序，對每m個高斯云的含混度CD進行判斷，如果CDk>β，k=1，2，…，m′，則概念數m′=m′-1，跳轉至②；否則，輸出M個含混度小于等于β的高斯云：

C(Exk，Enk，Hek)|k=1，2，…，M

由算法2可知，本文提出的AGCT_acc通過直接在較粗粒度上進行概念躍升，雖然減少了時間復雜度，同時也減少了逐層學習的次數，但較AGCT而言，AGCT_acc的精度未必會損失很大，尤其是當數據集規模較大時，可以在保證精度的前提下從很大程度上減少時間損耗，對于實際應用是有必要的.圖6為利用AGCT_acc對兩張不同的圖片進行云變換時對應的決策圖以及最終生成的云概念.我們利用AGCT_acc在大量數據集上進行概念抽象得到初始中心點個數的經驗值約為顯著點個數(圖6(b)為2個，圖6(e) 為4個)的3～5倍.

圖6 不同圖片對應的AGCT_acc的決策圖及其云概念Fig.6 Decision graph and cloud concepts of different pictures by AGCT_DPC

由于本文采用的統計論域是每個取值的頻度，并把頻度當成是DPC中的局部密度來計算.因此，假設論域有N′個取值，則計算距離矩陣時間復雜度為O(N′2).由于N′=N，所以O(N′2)可以忽略不計.再者，由于通過DPC的思想可以為AGCT的初始峰值的選取提供先驗信息，從而可以直接從較粗粒度上面實現概念躍升.假設初始選取m′個峰值點，則AGCT_acc總的時間復雜度為O(N′2)+O(m′2N)≈O(m′2N)，其中N為數據樣本點個數.由第1節分析可知，AGCT的時間復雜度約為O(m2N)，由于m′2?m2，所以O(m′2N)?O(m2N).因此，AGCT_acc的時間復雜度遠低于AGCT.

4 實驗仿真分析

本實驗的硬件配置為Intel i5-2430M的CPU，8G內存，操作系統為Windows7 64bit OS的臺式機，采用MATLAB2014軟件進行仿真.

4.1 圖像分割中過渡區發現

人類不僅能從有確定目標的圖像中獲取知識，而且可以從不確定目標的圖像提取概念，但這些不確定圖像傳遞的信息是模糊的，不能直觀的進行理解，而這些信息往往在某些領域(工業、空間探測、醫學等)又是比較重要的.基于云模型在處理不確定性以及雙向認知方面所具有的優勢，本文以工業中常見的激光熔覆圖像為例，對這類圖像進行分割，以提取出所符合認知的目標概念.

激光熔覆圖是一種新的表面改性技術，在工業中具有廣泛的應用前景.在該工藝中，如何從激光熔覆圖像獲取精確的激光高度是關鍵點之一[19].如果只考慮圖像的灰度值屬性，那么圖7 (a)顯示了一幅256×256像素、灰度值在[0，255]之間的激光熔覆圖，白色區域為高能密度的激光，黑色區域為背景顏色，同時在前景和背景之間存在一個過渡區域.以圖像中像素點的灰度值作為數據集合，通過采用本文提出的AGCT_acc算法對圖像進行概念提取的結果，得到3個概念如表1所示.

圖7(b)A為GCT算法對激光熔覆圖進行分割得到的三色圖；圖7 (c)為IS-IE算法[19](基于粗糙直方圖的云模型圖像分割算法)所獲得的三個概念所對應的三色圖，圖7 (d)為AGCT_acc算法所獲得的三個概念所對應的三色圖，其中灰色部分對應概念C1，黑色部分為概念C2，白色部分為概念C3.實驗證明，本文提出的AGCT_acc算法也能對激光熔覆圖的三個區域同時進行劃分，而且不確定性區域較小，從直觀上更符合人的認知特點.但由于對此類實驗結果當前不存在衡量標準，因此這里不將三種算法得到的三色圖進行數據上的對比.

表1 AGCT_acc圖5(a)上聚類形成的3個概念Table 1 Comparison of two granularity concepts

圖7 AGCT、IS-IE與AGCT_acc分割結果對比Fig.7 Comparison of segmentation results by AGCT，S-IE and AGCT_acc

4.2 多粒度圖像分割

由于文獻[6]已經通過驗證了AGCT算法在圖像分割方面的性能，因此，本文著重對比提出的算法AGCT_acc與AGCT兩種算法在多粒度圖像分割的效果和時間損耗上的差異.

圖8 一幅灰度特征明顯的photo圖像Fig.8 A photo image with distinct gray features

如圖8所示，圖8 (a)是一幅圖像分割中的經典圖像，直觀上感覺圖像從大尺度上應分為兩類，因為人和相機明顯區別于其他背景信息.圖像的其灰度直方圖如圖8(b)，本文以圖8(a)為實驗對象，分別利用AGCT_acc與AGCT對對圖8(a)進行概念抽象，形成不同粒度、不同層次的云概念，從不同粒度對圖像進行分割，從分割效果和時間損耗兩方面對AGCT_acc與AGCT兩種方法進行對比.

圖9 AGCT_acc與AGCT變粒度對比圖Fig.9 Comparison of variable granularity by AGCT_acc and AGCT

如圖9所示，為AGCT_acc與AGCT變粒度對比圖，從上至下，依次采用概念外圍區不交疊、基本區不交疊、骨干區不交疊的粒度變換策略，基于AGCT_acc與AGCT的圖像分割先從大尺度對全局信息進行粗粒度分割，形成整體上劃分的兩個概念，再從較細度上發現相機支架、草地等局部特征信息，最后對天空、遠處建筑等區域進行較細粒度的劃分.從圖中可以看出，AGCT_acc與AGCT的分割效果基本上是一致的.

表2 AGCT_acc與AGCT在圖8(a)=上聚類形成的2個粒度概念對比Table 2 Comparison of two granularity concepts generated on fig.8(a) by AGCT_acc and AGCT

表2、表3和表4分別給出了不同粒度對應的云概念參數以及時間損耗，可以看出AGCT_acc比AGCT形成同一粒度上云概念的時間損耗非常接近，從而保證了兩種方法在圖8(a)的分割效果一致.

表3 AGCT_acc與AGCT在圖8 (a)上聚類形成的3個粒度概念對比Table 3 Comparison of three granularity concepts generated on fig.8 (a) by AGCT_acc and AGCT

5 展望與總結

作為一種簡單有效的數據分析方法，密度峰值聚類算法思想新穎而簡潔，通過算法的假設條件可以快速尋找中心點.基于高斯云變換統計樣本頻度進行概念躍升的特點，本文利用密度峰值的思想提出一種云變換加速機制，用于加速高斯云變換中變粒度過程，實現概念的快速躍升，并從理論上證明本文提出的AGCT_acc算法的時間復雜度遠小于AGCT.通過圖片數據集上的實驗顯示，進一步驗證了本文提出的算法的時間損耗遠低于AGCT.雖然AGCT_acc減少了逐層學習的次數，但得到的概念與AGCT非常相似，即精度并未很大程度的損耗.總結全文，我們認為本文提出的算法還可以從以下幾個方面進行深入研究：

表4 AGCT_acc與AGCT在圖8 (a)上聚類形成的5個粒度概念對比Table 4 Comparison of five granularity concepts generated on fig.8 (a) by AGCT_acc and AGCT

1)本文提出的AGCT_acc算法的不足之處之一是在選取中心點個數時需要人的參與，即該算法是啟發式算法，因此有必要研究如何利用密度峰值聚類算法中樣本點γ值(γ=δ*ρ)的漸變關系自適應選取中心點以及獲取中心點個數，使AGCT_acc算法自適應化.

2)高斯云變換以高斯混合模型為基礎，保證其數學理論上的科學性和嚴謹性，從特定問題出發，通過調節概念含混度優化概念數目，粒度大小，層次關系等，可以模擬人類認知中的變粒度過程[6].目前的高斯云變換只能實現從細粒度到粗粒度的合成機制，無法實現從粗粒度到細粒度的分解機制.如果能實現分解機制，對于某些特定的情形可以避免云模型迭代次數過高的問題，從而進一步降低時間復雜度.

：

[1] Pedrycz W.Granular computing：analysis and design of intelligent systems[M].CRC Press，2013.

[2] Zadeh L A.Fuzzy sets[J].Information & Control ( Inf & Contr)，1965，8(65)：338-353.

[3] Pawlak Z.Rough sets[J].International Journal of Computer & Information Sciences，1982，11(5)：341-356.

[4] Zhang Yan-ping，Zhang Ling，Wu Tao.The representation of different granular worlds：a quotient space[J].Chinese Journal of Computers，2004，27(3)：328-333.

[5] Li De-yi，Meng Hai-jun.Membership and membership cloud generator[J].Journal of Computer Research and Development，1995，32(6)：15-20.

[6] Liu Y C，Li D Y，He W，et al.Granular computing based on gaussian cloud transformation[J].Fundamenta Informaticae，2013，127(14)：385-398.

[7] Rodriguez A，Laio A.Machine learning clustering by fast search and find of density peaks[J].Science，2014，344(6191)：1492-1496.

[8] Park H S，Jun C H.A simple and fast algorithm for K-medoids clustering[J].Expert Systems with Applications (Expert Syst Appl)，2009，36(2)：3336-3341.

[9] Saragih J M，Lucey S，Cohn J F.Deformable model fitting by regularized landmark mean-shift[J].International Journal of Computer Vision，2011，91(2)：200-215.

[10] Sun K，Geng X，Ji L.Exemplar component analysis：a fast band selection method for hyperspectral imagery[J].IEEE Geoscience & Remote Sensing Letters (IEEE Geosci Remote S)，2015，12(5)：998-1002.

[11] Chen Y W，Lai D H，Qi H，et al.A new method to estimate ages of facial image for large database[J].Multimedia Tools & Applications，2016，75(5)：1-19.

[12] Wu H，Wan Y.Clustering assisted fundamental matrix estimation[J].Computer Science，2015.

[13] Dean K M，Davis L M，Lubbeck J L，et al.High-speed multiparameter photophysical analyses of fluorophore libraries[J].Analytical Chemistry，2015，87(10)：5026-5030.

[14] Wang M，Zuo W，Wang Y.An improved density peaks-based clustering method for social circle discovery in social networks[J].Neurocomputing，2015，179(29)：219-227.

[15] Jiang Rong，Li De-yi，Fan Jian-hua.An automatic generation method for the generalized concept tree of numerical data[J].Chinese Journal of Computers，2000，23(5)：470-476.

[16] Cheung D，Fu A，Han J.Knowledge discovery in databases：arule-based attribute-oriented approach[C].Proceedings of the International Symposum on M ethodologies for Intelligent Systems，Charlotte，NC，1994：164-173.

[17] Lu Y.Concept hierarchy in data mining：specification，generation and implementation[D].Simon Fraser University，1997.

[18] Han J，Fu Y.Discovery of multiple-level association rules from large databases[C].Proceeding of the 21st VLDB Conference，Zurich,Swizevland,1995.

[19] Yao Hong.Research on image segmentation method based on the concept of connotation and denotation bidirectional cognitive transformation[D].Chongqing：Chongqing University of Posts and Telecommunications，2013.

附中文參考文獻：

[4] 張燕平，張 鈴，吳 濤.不同粒度世界的描述法—商空間法[J].計算機學報，2004，27(3)：328-333.

[5] 李德毅，孟海軍.隸屬云和隸屬云發生器[J].計算機研究與發展，1995，32(6)：15-20.

[15] 蔣 嶸，李德毅，范建華.數值型數據的泛概念樹的自動生成方法[J].計算機學報，2000，23(5)：470-476.

[19] 姚 紅.基于概念內涵與外延雙向認知變換的圖像分割方法研究[D].重慶：重慶郵電大學，2013.