• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      基于ε-鄰域和拉普拉斯矩陣秩約束的譜聚類算法

      2020-05-18 11:48:28朱恒東馬盈倉
      關(guān)鍵詞:拉普拉斯范數(shù)約束

      朱恒東,馬盈倉,楊 婷,張 要

      (西安工程大學(xué) 理學(xué)院,陜西 西安 710048)

      0 引 言

      聚類[1]是將一群不相關(guān)的對象劃分為相似對象的過程。其中建立在譜圖理論基礎(chǔ)上的譜聚類算法是目前研究較多、理論基礎(chǔ)深厚、應(yīng)用廣泛的聚類方法[2],其本質(zhì)是將聚類問題轉(zhuǎn)化為圖形最優(yōu)切分問題,相較于傳統(tǒng)的聚類算法,可以更好地處理非凸分布等復(fù)雜數(shù)據(jù)。在過去幾十年中,譜聚類在機(jī)器學(xué)習(xí)[3]、圖像處理[4]、計(jì)算機(jī)視覺[5]以及系統(tǒng)辨識(shí)[6]等領(lǐng)域都有著廣泛的應(yīng)用。譜聚類算法作為近年來熱門聚類方法之一[7],很多學(xué)者們提出了不同的譜聚類[8],如傳統(tǒng)的N-cut算法[9]和R-cut算法,也有最新的基于二部圖的快速聚類算法[10]等。

      譜聚類算法可以簡單分為3 個(gè)步驟:①構(gòu)建相似矩陣;②譜分析;③應(yīng)用k-means等算法聚類。其中至少存在2個(gè)問題。首先,相似矩陣的構(gòu)造方法很多,不同方法直接影響聚類結(jié)果,構(gòu)造合適的相似矩陣成為了一個(gè)問題[11]。Ng等[12]提出了NJW算法,考慮采用高斯核函數(shù)來構(gòu)造相似矩陣。采用全連接構(gòu)造方法,數(shù)據(jù)點(diǎn)之間的相似度保留過多影響聚類效果,為了滿足稀疏性,文獻(xiàn)[13]引入了K-近鄰思想。為了避免δ參數(shù)的不確定性對聚類結(jié)果的影響,Tulin等[14]提出了NC算法,以自適應(yīng)的方式自行調(diào)整參數(shù)。文獻(xiàn)[15]引入深度學(xué)習(xí)中的S型函數(shù)來構(gòu)造相似矩陣。雖然取得了一定效果,但也容易被“錯(cuò)誤”的數(shù)據(jù)影響[16]。其次,在譜聚類過程中,一般先是求解特征矩陣,然后對特征矩陣進(jìn)行K-means得到聚類結(jié)果。對于大規(guī)模數(shù)據(jù)聚類問題,譜聚類在譜分析處理中由于涉及大圖構(gòu)建、特征分解等高計(jì)算度復(fù)雜操作[9,12,17],使得求解難度增加,并且即使求解出特征矩陣,也并不能直接得到聚類結(jié)果,而是要進(jìn)行離散化處理得到結(jié)果,使得運(yùn)行效率不高。導(dǎo)致難以直接使用譜聚類算法解決大規(guī)模數(shù)據(jù)聚類問題。文獻(xiàn)[18]不通過求解特征矩陣來聚類,而是采用對拉普拉斯矩陣進(jìn)行秩約束,保證圖有K個(gè)連通分支數(shù)目,進(jìn)而選擇對最后學(xué)習(xí)到的相似矩陣直接聚類。近年來關(guān)于譜聚類的研究雖然取得了一定進(jìn)展,但總體上仍處于初級(jí)探索階段,該算法仍然有很大的深入研究空間。

      基于以上情況,本文提出新的譜聚類方法。首先,在采用傳統(tǒng)高斯核函數(shù)構(gòu)建相似矩陣過程中,引入ε-鄰域思想,對親和矩陣進(jìn)行稀疏化處理,可以有效利用數(shù)據(jù)點(diǎn)的局部信息[19],剔除大量不相關(guān)點(diǎn)的信息,還可以降低譜分析過程中的計(jì)算量;其次,在譜分析過程中,對相似矩陣的拉普拉斯矩陣加上秩約束[20],并且對相似矩陣加上l2,1范數(shù)作為正則項(xiàng)來修正模型,保證圖的結(jié)構(gòu)性;然后利用學(xué)習(xí)到的相似矩陣來直接聚類。建立基于ε-鄰域和拉普拉斯矩陣秩約束的譜聚類算法(spectral clustering algorithmε-nearest neighbors based on and Laplace matrix rank constraint,簡寫為ε-RSC)。

      1 預(yù)備知識(shí)

      1.1 譜聚類

      譜聚類的原理是首先利用樣本數(shù)據(jù)X={x1,x2,…,xn},X∈Rn×k,得到鄰接矩陣,然后根據(jù)鄰接矩陣求得拉普拉斯矩陣,再對拉普拉斯矩陣進(jìn)行特征分解得到特征向量,最后對特征矩陣進(jìn)行聚類。常采用高斯核函數(shù)[21]構(gòu)造鄰接矩陣A,即

      (1)

      (2)

      進(jìn)而得到新的函數(shù)

      (3)

      1.2 l2,1范數(shù)

      使用l2范數(shù)的平方作為損失函數(shù)對較小的異常值不敏感,但對較大的異常值敏感;使用l1范數(shù)作為損失函數(shù)對較大的異常值不敏感,對較小的異常值敏感。由文獻(xiàn)[22]可知l2,1范數(shù)綜合了l2范數(shù)和l1范數(shù)的優(yōu)點(diǎn),既無論異常值的大小,l2和l1范數(shù)的魯棒性均可被利用。

      性質(zhì)1[23]對于矩陣X,其中有

      ‖X‖2,1=tr(XTDX)

      (4)

      式中:D是對角矩陣,對角元素為

      2 模型的建立及求解

      2.1 模型建立

      譜聚類原始目標(biāo)函數(shù)為

      min tr(FTLSF)
      st.FTF=1

      (5)

      (6)

      為了不求解特征矩陣F,采用對相似矩陣S聚類。對拉普拉斯矩陣加上秩約束,即rank(LS)=n-K,通過保證圖有K個(gè)連通分支,保證圖的結(jié)構(gòu)性,最終迭代得到聚類結(jié)果。式(6)轉(zhuǎn)化為

      (7)

      式中:λ為常數(shù);A為采用1.1節(jié)方法構(gòu)造的相似矩陣;S為最終學(xué)習(xí)的相似矩陣。

      2.2 模型求解

      將式(7)變化為如下模型:

      (8)

      式中:A為親和矩陣;S為要學(xué)習(xí)的相似矩陣。對于S,存在一個(gè)函數(shù)fi∈Rc×1[20],使得

      (9)

      此時(shí)采用交替迭代優(yōu)化算法求解,具體步驟為

      1) 當(dāng)S固定時(shí),式(8)變?yōu)?/p>

      min tr(FTLSF)
      st.FTF=1,F∈Rn×k

      (10)

      對拉普拉斯矩陣LS進(jìn)行特征分解,求解K個(gè)最小特征值對應(yīng)的特征向量,得到F。

      2) 當(dāng)F固定時(shí),結(jié)合式(9),式(8)變?yōu)?/p>

      (11)

      (12)

      根據(jù)1.2中l(wèi)2,1范數(shù)的性質(zhì)1,得

      (13)

      (14)

      (15)

      再根據(jù)拉格朗日乘子法,得

      (16)

      對si求偏導(dǎo),并令其偏導(dǎo)數(shù)等于0,得

      Dsi-pi-η1-αi=0

      (17)

      對其中每個(gè)數(shù)據(jù),有

      dijsij-pij-η-αij=0

      (18)

      令dijsij=0,根據(jù)KKT條件,得

      (19)

      其中(v)+=max(0,v),根據(jù)η定義函數(shù)

      (20)

      gi(η)=0

      (21)

      式中:gi(η)為分段單調(diào)遞增函數(shù),可用牛頓法迭代求解。值得說明的是,由于在算法過程中借用牛頓迭代法,因此是收斂的。

      經(jīng)過以上交替迭代優(yōu)化算法計(jì)算后,得到最終學(xué)習(xí)到的相似矩陣。在迭代過程中,因?yàn)榧尤肓死绽咕仃囍燃s束,通過保證特征矩陣的秩為K個(gè),從而保證圖有K個(gè)連通分支數(shù)目,進(jìn)而可以直接對相似矩陣直接聚類,得到聚類結(jié)果。

      2.3 算法流程

      根據(jù)2.2模型求解,總結(jié)梳理ε-RSC算法流程如下:

      輸入 親和矩陣A∈Rn×n,聚類數(shù)K,常數(shù)λ

      1) 計(jì)算親和矩陣A;

      3) for iter=1,2,…,最大迭代次數(shù) do;

      4) while不收斂do;

      5) 固定F,由F求解vi,初始化S;

      6) fori=1,2,…,n;

      8) end for;

      9) 固定S,由S求解拉普拉斯矩陣,求解F,完成更新F;

      10) end while;

      11) end for;

      12) 解出S,利用圖的K個(gè)連通分支聚類。

      3 實(shí) 驗(yàn)

      為驗(yàn)證算法有效性,將本文ε-RSC算法與K均值(K-means)算法、LRR方法、SR方法以及文獻(xiàn)[22]中CLR-L方法進(jìn)行對比,數(shù)據(jù)集選取人造數(shù)據(jù)集和真實(shí)數(shù)據(jù)集。

      3.1 評(píng)價(jià)指標(biāo)

      以聚類準(zhǔn)確率和標(biāo)準(zhǔn)化互信息評(píng)價(jià)算法聚類性能。聚類準(zhǔn)確率

      (22)

      式中:ri和si分別為聚類算法得到的類標(biāo)簽和數(shù)據(jù)集真實(shí)的類標(biāo)簽;n為樣本個(gè)數(shù);函數(shù)δ(x,y)在當(dāng)x=y時(shí)為1,否則為0;map(ri)是一個(gè)排列匹配函數(shù),將ri標(biāo)簽映射成與si匹配的等效標(biāo)簽。A值在[0,1]之間,值越大越好。

      標(biāo)準(zhǔn)化互信息用于確定聚類的質(zhì)量,其公式為

      (23)

      3.2 人造數(shù)據(jù)集

      人造數(shù)據(jù)集選取Cdata04數(shù)據(jù)集和雙月數(shù)據(jù)集。Cdata04數(shù)據(jù)集由4個(gè)環(huán)型簇組成,形狀如四葉草,如圖1所示。葉子交匯的地方,由于數(shù)據(jù)間聯(lián)系緊密,給聚類分析帶來一定難度。雙月型數(shù)據(jù)集是一類典型的非線性數(shù)據(jù)集,形狀如兩輪彎月,如圖2所示。由于雙月型數(shù)據(jù)的特殊分布,很多聚類算法容易將中間嵌入的地方混聚一類。

      圖 1 Cdata04數(shù)據(jù)集Fig.1 Cdata04 data set

      圖3~4分別為Cdata04權(quán)重連接圖和雙月權(quán)重連接圖,均以初始親和矩陣為原始權(quán)重,將數(shù)據(jù)重新連接整理,將數(shù)據(jù)聚類問題轉(zhuǎn)變?yōu)樽V聚類圖形最優(yōu)切分問題??梢园l(fā)現(xiàn),整個(gè)權(quán)重圖連線緊密,所有的點(diǎn)被劃為一塊。

      圖 3 Cdata04權(quán)重連接圖Fig.3 Weight connection diagram of Cdata04

      圖 4 雙月權(quán)重連接圖Fig.4 Bimonthly weight connection diagram

      圖5~6分別為ε-RSC算法對2種數(shù)據(jù)集的聚類結(jié)果圖??梢园l(fā)現(xiàn),Cdata04數(shù)據(jù)集和雙月型數(shù)據(jù)集被很好地切分。這說明ε-RSC算法得到的相似矩陣是合理的。

      圖 5 Cdata04數(shù)據(jù)集的切分結(jié)果Fig.5 Segmentation result of Cdata04 data sets

      圖 6 雙月數(shù)據(jù)集的切分結(jié)果Fig.6 Segmentation results of bi-monthly data sets

      3.3 真實(shí)數(shù)據(jù)集

      真實(shí)數(shù)據(jù)集選取zoo-uni, blanlance, solar-uni以及ecoli-uni等4個(gè)常用UCI真實(shí)數(shù)據(jù)集,見表1。用A,I評(píng)價(jià)不同算法在4個(gè)數(shù)據(jù)集上的聚類結(jié)果,見表2~3。數(shù)據(jù)加粗代表算法性能最優(yōu),數(shù)據(jù)加下劃線代表算法性能次優(yōu)。

      表 1 真實(shí)數(shù)據(jù)集Tab.1 Real datasets

      表 2 不同算法在多個(gè)數(shù)據(jù)集下的A值比較Tab.2 Comparison of A value of different algorithms in multiple data sets

      表 3 不同算法在多個(gè)數(shù)據(jù)集下的I值比較Tab.3 Comparison fo I value of different algorithms in multiple data set

      從表2~3可看出,本文ε-RSC算法對S直接聚類,有著良好的聚類效果。在實(shí)驗(yàn)的4個(gè)數(shù)據(jù)集以及2個(gè)評(píng)價(jià)指標(biāo)上,ε-RSC算法基本都比其他4種算法性能更優(yōu)。這主要是因?yàn)棣?RSC算法在構(gòu)造親和矩陣時(shí)很合理,且加上l2,1范數(shù)的約束,使得譜分析過程中,能夠從整體和局部綜合考慮,對數(shù)據(jù)合理切分。

      4 結(jié) 語

      本文提出了一種新的譜聚類方法ε-RSC,在構(gòu)造親和矩陣時(shí),采用ε-鄰域思想,加強(qiáng)了對數(shù)據(jù)局部信息的利用,并且對相似矩陣加上l2,1范數(shù)的約束,使得模型在聚類時(shí)可以更好地處理異常值。在多個(gè)數(shù)據(jù)集上的聚類結(jié)果均很好。后續(xù)將進(jìn)一步探究親和矩陣的構(gòu)造方法以及約束相似矩陣的方法。

      猜你喜歡
      拉普拉斯范數(shù)約束
      “碳中和”約束下的路徑選擇
      約束離散KP方程族的完全Virasoro對稱
      基于加權(quán)核范數(shù)與范數(shù)的魯棒主成分分析
      矩陣酉不變范數(shù)H?lder不等式及其應(yīng)用
      基于超拉普拉斯分布的磁化率重建算法
      適當(dāng)放手能讓孩子更好地自我約束
      人生十六七(2015年6期)2015-02-28 13:08:38
      一類具有準(zhǔn)齊次核的Hilbert型奇異重積分算子的范數(shù)及應(yīng)用
      位移性在拉普拉斯變換中的應(yīng)用
      含有一個(gè)參數(shù)的p-拉普拉斯方程正解的存在性
      二部雙圈圖的拉普拉斯系數(shù)
      嵩明县| 隆回县| 丽江市| 吐鲁番市| 呼玛县| 平谷区| 阿拉善盟| 万宁市| 高尔夫| 五大连池市| 探索| 固安县| 永修县| 伊春市| 武夷山市| 邵阳市| 荔波县| 屯门区| 元氏县| 阿拉善盟| 苗栗县| 东乡| 康保县| 黄冈市| 辰溪县| 青川县| 峨眉山市| 千阳县| 岗巴县| 昌宁县| 义乌市| 游戏| 建水县| 石首市| 确山县| 宁海县| 万荣县| 轮台县| 安仁县| 大冶市| 长治市|