一種基于灰關聯(lián)分析的譜聚類方法

1基于差異信息模型的灰關聯(lián)分析聚類分析是機械學習領域的一個重要研究方向。作為一種有效的數(shù)據(jù)分析方法，它已廣泛應用于機械工具、文本檢索、語音識別等領域。傳統(tǒng)的聚類算法（如k-mean算法、im算法等）當樣品接近凸球形時，聚類效果好，但當樣品呈任意形狀時，很容易陷入局部最優(yōu)的解。集群算法主要用于計算機視覺、vlasi設計等領域，后來擴展到機械學習。由于它能識別微凸分布，不受數(shù)據(jù)維數(shù)的影響，它可以收斂整體最優(yōu)解決的優(yōu)點，引起人們的注意，并迅速成為機械學習領域的研究熱點。然而，現(xiàn)有的集群算法對參數(shù)的變化非常敏感，并且微變化的參數(shù)值會影響集群的效果。不同數(shù)據(jù)集的最佳參數(shù)值不同，這會影響算法的適用性。灰色理論作為一種處理現(xiàn)實中存在的部分信息明確、部分信息不明確的“小樣本”、“貧信息”等不確定性問題的有力工具,已經在油氣勘探、工業(yè)控制、圖像處理、網絡安全、經濟預測、物流管理等多個學科領域得到廣泛應用.本文提出利用基于差異信息理論的灰關聯(lián)分析中均衡接近度的概念來測度數(shù)據(jù)點間的相似度,以改進現(xiàn)有譜聚類方法的性能,實驗證明新方法能夠得到更好的聚類結果.2灰關聯(lián)分析的應用灰色系統(tǒng)理論是由鄧聚龍教授于1982年提出的一種處理不確定性和非線性問題的系統(tǒng)理論,主要包括灰哲學、灰生成、灰分析、灰建模、灰預測、灰決策、灰控制、灰評估、灰數(shù)學等方面的內容.灰關聯(lián)分析是灰色系統(tǒng)分析中的一個重要內容,與數(shù)理統(tǒng)計中的回歸分析、方差分析和主成分分析不同,它對樣本的數(shù)量和分布規(guī)律不做要求,量化結果與定性分析的結果保持一致,因此特別適用于對小樣本、無明顯規(guī)律的數(shù)據(jù)進行研究.2.1生成線性助推式的線性范圍和灰關聯(lián)度定義1設序列集X={xi|xi=(xi(1),xi(2),…,xi(n)),i∈N},N={1,2,…,m},若X滿足1),xi(k)和xj(k)為同一數(shù)量級,Vk∈K,K={1,2,…,n},記為屬性ρ1;2)不同序列對應的分量間可以定義距離測度,簡稱為數(shù)值可接近性,記為屬性ρ2,則稱序列集X為因子集.定義2設序列集X=x{xi|xi=(xi(1),xi(2),…,xi((n)),i∈N},N={1,2,…,m},存在映射Ti=x→x,Ti可以采用以下形式稱Ti為序列的純量化算子.T1至T6分別稱為初始值化算子、均值化算子、最大值化算子、最小值化算子、區(qū)間值化算子和始點零化算子.定義3設X為灰關聯(lián)因子集,X=x{xi|xi=(xi(1),xi(2),…,xi(n)),i∈N},N={0,1,2,…,m},m≥2,K={1,2,…,n},n≥3,x0∈X為參考序列,而xi∈X為比較序列,若存在一個非負實數(shù)γ(x0(k),xi(k))為X上一定環(huán)境下的比較測度,且令非負實數(shù)則當其滿足規(guī)范性、偶對稱性、整體性、接近性時,稱γ(x0(k),xi(k))為xi對x0在k點的灰關聯(lián)系數(shù),稱γ(x0,xi)為xi對x0的灰關聯(lián)度.2.2灰關聯(lián)熵-均衡距離度張岐山教授以灰朦朧集為背景,從差異信息的角度建立了一套信息序列的熵理論,并以此為基礎研究了灰色系統(tǒng)中若干重要理論問題.在灰關聯(lián)分析方面,通過引入灰關聯(lián)熵,克服了傳統(tǒng)灰關聯(lián)分析可能造成局部點關聯(lián)傾向的問題.定義4灰關聯(lián)密度:設X為灰關聯(lián)因子集,X={xi|i∈N},N={0,1,2,…,m},m≥2,xi=(xi(1),xi(2),…,xi(k)),k∈K={1,2,…,n},n≥3,x0為參考序列,xi為比較序列,ri=(γ(x0(k),xi(k)))為第i個比較序列的灰關聯(lián)系數(shù)序列,C={ri|i∈N}為灰關聯(lián)系數(shù)序列集,則稱映射為灰關聯(lián)系數(shù)分布映射,映射值v(x0(k),xi(k))為第i個比較序列在第k點的灰關聯(lián)密度值.此比較序列的所有關聯(lián)密度值的全體構成灰關聯(lián)密度序列,記為vi.定義5灰關聯(lián)熵:設X為灰關聯(lián)因子集,X={xi|i∈N},N={0,1,2,…,m},m≥2,xi=(xi(1),xi(2),…,xi(k)),k∈K={1,2,…,n},n≥3,x0為參考序列,xi為比較序列,ri=(γ(x0(k),xi(k)))為第i個比較序列的灰關聯(lián)系數(shù)序列,C={ri|i∈N}為灰關聯(lián)系數(shù)序列集,V={vi|i∈N}為灰關聯(lián)密度序列集,則稱函數(shù)為第i個比較序列的灰關聯(lián)熵.定義6熵關聯(lián)度:設I(vi)為第i個比較序列的灰關聯(lián)熵,Im為灰關聯(lián)系數(shù)序列的最大關聯(lián)熵,則稱為第i個比較序列的熵關聯(lián)度.定義7均衡接近度:設γ(x0,xi)和E(x0,xi)分別為第i個比較序列的灰關聯(lián)度和熵關聯(lián)度,則稱為第i個比較序列的均衡接近度.由于均衡接近度既考慮了灰關聯(lián)因子序列間點的距離接近性,又考慮了整體的無差異性接近,因此可以克服點關聯(lián)強傾向問題.3多路規(guī)范割準則譜聚類算法的思想來源于譜圖劃分理論.如果將數(shù)據(jù)集看成一個無向完全圖G=(V,E),數(shù)據(jù)點作為圖的頂點,將數(shù)據(jù)點間的相似度量化作為頂點連接邊的權值,則聚類問題就轉化為圖的劃分問題.要使聚類效果達到最優(yōu)也就是設計一種劃分準則,使劃分后的子圖間的相似度最小,而子圖內部的相似度最大.因此,劃分準則的好壞對聚類效果有直接影響.目前常用的劃分準則主要有規(guī)范割準則(Normalizedcut)、比例割準則(Ratiocut)、平均割準則(Averagecut)、多路規(guī)范割準則(Multi-waynormalizedcut)等.其中,規(guī)范割準則是求目標函數(shù)的最小值.其中是子圖A中的頂點與圖V中所有頂點間的連接邊的權值的總和,assoc(B,V)也仿此定義.從公式(12)可以看出,規(guī)范割準則同時考慮簇內數(shù)據(jù)相似度最高和簇間數(shù)據(jù)相異度最低,因此其劃分效果比較好.但是,由于它是一種2路劃分法,當簇數(shù)大于2時需要進行遞歸劃分.Meila和Shi擴展了2路劃分法,提出多路規(guī)范割準則(Multi-waynormalizedcut),其目標函數(shù)為MNcut可以將圖G同時劃分為k個子圖.可以證明,求圖的最優(yōu)劃分是一個NP難問題.但是,通過放松問題的約束條件,對由相似矩陣S生成的Laplacian矩陣L進行譜分解,可以在多項式時間內逼近最優(yōu)解.Laplacian矩陣的形式主要有三種其中,矩陣D是一個對角矩陣,其對角線元素為各頂點的度.D一般被稱為度矩陣.目前典型的譜聚類算法有Perona和Freeman提出的PF算法,Shi和Malik提出的Ncut算法,Kannan等提出的KVV算法,Ng,Jordan和Weiss提出的NJW算法,Meila和Shi提出的MNcut算法,等等.不同的算法采用不同的Laplacian矩陣生成方法,如:Ncut算法使用公式(14),MNcut算法使用公式(15),NJW算法用的是公式(16).在描述數(shù)據(jù)點間的相似度方面,多數(shù)算法采用形如的高斯核函數(shù).其中,si代表數(shù)據(jù)點,σ是算法的參數(shù).譜算法的基本步驟可以歸納為1)構建相似矩陣S.2)從公式(14)至公式(16)中選擇一種構建Laplacian矩陣L.3)求矩陣L的特征值和特征向量.4)子圖劃分.(a)2路劃分:根據(jù)矩陣L的第二小特征值對應的特征向量將數(shù)據(jù)點劃分成兩個簇,在劃分好的兩個簇上再遞歸進行2路劃分,直到找到指定數(shù)量的簇.(b)多路劃分:根據(jù)矩陣L的前k個正交特征向量組成特征矩陣,應用K-Means算法或其它的聚類算法對其進行聚類.譜聚類算法在取得廣泛成功的同時也存在一些亟待解決的問題,如:聚類的效果對參數(shù)σ的變化非常敏感,將其應用于大規(guī)模學習問題時計算量太大,如何自動確定聚類數(shù)目,等等.4基于灰關聯(lián)分析的相關研究傳統(tǒng)譜聚類算法中的相似性測度采用的是高斯核函數(shù),需要確定參數(shù)σ.從灰關聯(lián)分析的角度,可以將每個數(shù)據(jù)點表示為由其屬性組成的屬性序列,通過計算屬性序列間的均衡接近度從整體上衡量數(shù)據(jù)點之間的相似程度.當由于相似度完全由數(shù)據(jù)點自身的屬性值描述,不需要引入額外參數(shù),消除了參數(shù)對算法的影響.基于此可以設計一個基于灰關聯(lián)分析的譜聚類算法,即GSC(Greyspectralclustering)算法.4.1計算相似度矩陣及特征向量1)輸入簇數(shù)參數(shù)k和數(shù)據(jù)集,構建數(shù)據(jù)矩陣Datan×m(每個行向量代表一個數(shù)據(jù)點);2)確定數(shù)據(jù)點屬性序列si={si1,si2,…,sin},i=1,2,…,n;3)計算所有屬性序列的均衡接近度,構建相似度矩陣Sn×n;4)根據(jù)公式(14)至公式(16)構建Laplacian矩陣,計算L的特征值和特征向量,取前k個最大特征值對應的特征向量x1,x2,…,xk,構造矩陣X=[x1,x2,…,xk]∈Rn×k;5)將矩陣X的每個行向量看作一個數(shù)據(jù)點,用K-Means算法對將其劃分成k個簇;6)若矩陣X的第i行被劃分到簇j,則也將對應原始數(shù)據(jù)點si劃分到簇j;7)輸出聚類結果.4.2算法的時間復雜度GSC算法中,構建數(shù)據(jù)矩陣需要O(n×m)的時間,計算任意兩個屬性序列的均衡接近度的時間復雜度為O(m),因此構建相似度矩陣T需要的時間為O(n2×m).求矩陣特征值的時間復雜度一般為O(n3),但當矩陣是稀疏對稱陣時,用Lanczos方法可以將時間減少到O(C×n),其中C為求解過程中需要用到的矩陣-向量計算的次數(shù)的最大值,一般C=o(n).K-Means算法的時間復雜度為O(k×m×n),因此,整個算法在最壞情況下的時間復雜度為O(n3).算法中矩陣S和矩陣L占用的空間均為O(n2),矩陣X占用的空間為O(k×n),因此整個算法的空間復雜度為O(n2).5實驗結果與分析為了驗證新算法的聚類性能,在一臺硬件配置為1.66GHzCPU、2GB內存,軟件配置為WindowsXPSP2的PC機上進行實驗,從UCI機器學習數(shù)據(jù)集倉庫中選取6個有代表性的數(shù)據(jù)集與Ncut算法和NJW算法做對比,表1給出測試數(shù)據(jù)集的相關信息.實驗采用精確度(Accuracy)指標和F-測度(F-measure)指標對GSC算法、Ncut算法和NJW算法的性能進行評測,精確度指標從整體上衡量一個算法的聚類效果,其定義如下:其中,N1為正確分類的實例數(shù),N2為全部實例數(shù).F-測度指標著重于通過衡量每個類的聚類質量來綜合評價算法的聚類效果,其定義如下:其中,T(i)表示正確分到第i個類的實例數(shù),Cluster(i)表示第i個簇的實例數(shù),Class(i)表示第i個類的實例數(shù).每個算法在每個數(shù)據(jù)集上重復測試100次,取其平均值為實驗結果.由于GSC算法的聚類性能還受到灰關聯(lián)分析中純量化算子的影響,實驗中使用的是使評測值最高的算子.精確度實驗結果如表2所示.從表2可以看出,GSC算法在前5個數(shù)據(jù)集上的聚類精確度都優(yōu)于對比算法,僅在最后一個Ecoli數(shù)據(jù)集上略差于NJW算法,這表明在多樣化的應用環(huán)境中,基于均衡接近度的相似性測度比基于高斯核函數(shù)的相似性測度更能反映數(shù)據(jù)點間的整體相似程度,從而獲得更好的聚類結果.而且,由于均衡接近度的計算完全依據(jù)數(shù)據(jù)點自身的信息,不需要引入額外的相似度參數(shù),克服了外部參數(shù)對算法性能的影響.F-測度實驗結果如表3所示.表3的實驗結果表明:即使從微觀的角度衡量每個類的聚類質量,也可以得出與精確度實驗相似的結論GSC算