• 
    

    
    

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

      譜聚類算法及其應(yīng)用綜述

      2016-05-14 15:49:00李玲俐
      軟件導(dǎo)刊 2016年7期
      關(guān)鍵詞:應(yīng)用研究

      李玲俐

      摘要:由于性能優(yōu)越,譜聚類成為近年來聚類算法研究的熱點。譜聚類算法可以在任意形狀的樣本空間上聚類,并能獲得全局最優(yōu)解。介紹了譜圖的基本理論及其劃分準則,探討了譜聚類算法,并針對當(dāng)前譜聚類應(yīng)用展望了未來研究方向。

      關(guān)鍵詞關(guān)鍵詞:譜聚類;譜圖理論;圖劃分;應(yīng)用研究

      DOIDOI:10.11907/rjdk.161229

      中圖分類號:TP312文獻標識碼:A文章編號文章編號:16727800(2016)007005403

      0引言

      聚類就是按照事物的某些特征,把事物分成若干類或簇,使得在同一個類內(nèi)的對象之間最大程度相似,而不同類之間的對象最大程度不同。聚類分析在數(shù)據(jù)挖掘、空間數(shù)據(jù)處理、金融數(shù)據(jù)分類和入侵檢測技術(shù)等領(lǐng)域中都得到了廣泛應(yīng)用。傳統(tǒng)的聚類算法,如Kmeans和模糊C均值算法(Fuzzy CMeans,F(xiàn)CM)等大都建立在凸球形樣本空間上,如果樣本空間不為凸,算法就會陷入局部最優(yōu)。因此,學(xué)者們開始研究一種新的聚類方法——譜聚類(Spectral Clustering,SC)算法。該算法由給定的樣本數(shù)據(jù)集定義一個描述數(shù)據(jù)點之間相似度的親和矩陣,并計算矩陣的特征值和特征向量,再選擇合適的特征向量聚類不同的數(shù)據(jù)點。譜聚類算法是一個判別式算法,其思想相對簡單易于實現(xiàn),具有識別非凸分布的聚類能力,適合處理許多實際應(yīng)用問題。本文著重介紹譜聚類的基本理論、算法描述、當(dāng)前應(yīng)用及未來研究方向。

      1譜聚類基本理論與算法描述

      1.1圖劃分原理

      譜聚類是一種基于圖論的聚類方法。譜圖理論是將數(shù)據(jù)聚類問題轉(zhuǎn)化成圖的多路劃分問題,通過分割子圖來聚類數(shù)據(jù)點。譜聚類能對任意形狀的樣本空間聚類,并能獲得全局最優(yōu)解,其基本思想是通過對樣本數(shù)據(jù)的Laplacian(拉普拉斯)矩陣進行特征分解而得到的特征向量進行聚類。

      4結(jié)語

      針對kmeans算法易受初始聚類中心影響的問題,首先用人工魚群算法的全局尋優(yōu)能力搜索初始聚類中心。

      為了處理大規(guī)模數(shù)據(jù),本文提出基于Mapreduce的afsa_km算法。實驗結(jié)果表明,并行化的afsa_km算法比kmeans算法有更高的準確率,基于Mapreduce實現(xiàn)的afsa_km算法具有良好的加速比和擴展性,效率也有很大提高。 假定將每個數(shù)據(jù)樣本看作圖中的頂點V,且樣本中的數(shù)據(jù)對之間都有一定的相似性,由樣本間的相似度,將頂點間的邊E賦權(quán)重值W,得到一個無向加權(quán)圖G=(V,E),V={v1,v2,...vn}表示點集。圖G中,可將聚類問題轉(zhuǎn)化為在圖G上的圖劃分問題。圖論中的劃分準則一般有Minimum Cut、Average Cut、Normalized Cut、Minmax Cut、Ratio Cut、MN Cut等,劃分準則的好壞對聚類結(jié)果的優(yōu)劣產(chǎn)生很大影響。

      1.1.1最小割集準則(Minimum Cut)

      譜圖分割過程中,圖的邊值代表頂點之間的相關(guān)性大小,假設(shè)G被劃分為A、B兩個子圖,最小割集的代價函數(shù)為:Cut(A,B)=∑i∈A,j∈BWij其中,A∩B=φ,A∪B=V,權(quán)重Wij表示Vi與Vj之間的關(guān)系。屬于子圖A的頂點和屬于子圖B的頂點之間的所有邊的和最小化,表示兩個子圖之間的相關(guān)性越小。Wu和Leahy[2]提出最小化上述Cut值來劃分圖G,即最小割集準則,是最常見也是最簡單的評價方法。用該準則對一些圖像進行分割也能產(chǎn)生不錯的效果。該準則的缺點是分割圖像時容易出現(xiàn)偏向小區(qū)域的情況。

      1.1.2規(guī)范割集準則(Normalized Cut)

      根據(jù)譜圖理論,Shi和Malik[3]提出新的目標代價函數(shù)NCut為:NCut(A,B)=Cut(A,B)Vol(A,V)+Cut(A,B)Vol(B,V)其中,Vol(A,V)

      規(guī)范割集準則即最小化NCut函數(shù)。與Minimum Cut相比,該準則能平衡類內(nèi)樣本間的相似度,也能平衡類間樣本間的相異度,即可以避免偏向小區(qū)域分割。一般的聚類算法中,采用NCut準則的情況比較多。

      1.1.3比例割集準則(Ratio Cut)

      為兼顧孤立點和均衡化問題,Hagen和Kahng[4]提出了比例割集準則,其目標代價函數(shù)RCut為:RCut(A,B)=Cut(A,B)min(|A|,|B|)其中,|A|、|B|分別表示子圖A、B中頂點的個數(shù),Cut(A,B)是最小割集準則的代價函數(shù)。最小化RCut函數(shù)引入了一個規(guī)模參數(shù)作為分母,加大了類間相似性,減低了過分分割的可能性,這是優(yōu)于最小割集準則的方面,但該準則會使運行速度降低。

      1.1.4平均割集準則(Average Cut)

      Sarkar和Soundararajan[5]提出平均割集準則,其目標函數(shù)AvCut為:AvCut=Cut(A,B)|A|+Cut(A,B)|B|AvCut同NCut函數(shù)一樣,最小化目標函數(shù)都能產(chǎn)生較準確的劃分,兩個都考慮了邊界損失與分割區(qū)域之間的相關(guān)性比例。而AvCut準則更容易導(dǎo)致欠分割或易分割出只包含幾個少數(shù)頂點的極小子圖的缺點。

      1.1.5最小最大割集準則(MinMax Cut)

      最大最小割集準則[6]是為了能夠使類內(nèi)頂點的連接度強,類間的連續(xù)強度能夠最小化,其目標函數(shù)MCut為:MCut=Cut(A,B)Vol(A,A)+Cut(A,B)Vol(B,B)可以看出,最小化MCut函數(shù)不僅要最小化Cut(A,B),還需要最大化Vol(A,A)和Vol(B,B)。該函數(shù)不易出現(xiàn)分割出只包含幾個頂點的較小子圖,傾向于產(chǎn)生平衡割集,可以有效避免孤立點的出現(xiàn),但實現(xiàn)速度較慢。

      1.1.6多路規(guī)范割集準則(Multiway Normalized Cut)

      Meila和Xu[7]在NCut割集函數(shù)的基礎(chǔ)上,將圖G分割成k個子圖,將規(guī)范割集準則擴展到k類,這就是多路規(guī)范割集準則。其目標函數(shù)為:MNCut=Cut(A1,V-A1)Vol(A1,V)+Cut(A2,V-A2)Vol(A2,V)+...

      +Cut(Ak,V-Ak)Vol(Ak,V)可以看出,當(dāng)k值為2,即分割成2個子圖,聚類成兩類時,MNCut函數(shù)和NCut函數(shù)是相同的。多路規(guī)范割集準則在實際應(yīng)用中更有效、合理,只是優(yōu)化問題和最小化問題比較難于解決。

      1.2譜聚類算法描述

      譜聚類算法大多處理兩類問題,多類聚類一般通過兩路劃分方法來實現(xiàn)。假定k是最終分類個數(shù)。譜聚類算法不是直接對數(shù)據(jù)點集的親密度矩陣S進行分析而得出分類結(jié)果,而是要先計算k個最大的特征值和特征向量,沒有充分利用包含有用劃分信息的其它特征向量,其計算量較大,計算效率低,并且需要由用戶事先給出聚類個數(shù)k。然后,用這些特征向量構(gòu)造一個對稱矩陣Q,最后對Q進行親密度分析才得到數(shù)據(jù)集的最終聚類。因此,譜聚類算法得到的矩陣Q只是原始親密度矩陣S的一個近似,近似的程度與k值相關(guān),k越大,Q和S的誤差越小。Q對比S的優(yōu)勢主要體現(xiàn)在對Q進行親密度分析,比對S直接進行分析以實現(xiàn)的分類要容易。

      目前,已經(jīng)出現(xiàn)了許多譜聚類模型和算法,如PF算法、SM算法、SLH算法、KVV算法、MCut算法等幾種迭代譜聚類算法;還有多路譜聚類算法,包括MS算法和NJW算法等。

      2當(dāng)前研究和應(yīng)用

      2.1圖像分割應(yīng)用

      譜聚類算法最初應(yīng)用在圖像分割中。Shi和Malik采用2way NCut的譜聚類算法對圖進行迭代分割,得到滿意的聚類效果。但傳統(tǒng)譜聚類算法易受到彩色圖像大小和相似性測度的影響,會導(dǎo)致計算量大和分割精度低的問題。文獻提出了一種譜聚類分割算法,該算法基于超像素集測地線特征。先對彩色圖像進行預(yù)分割得到超像素集,以超像素集為基礎(chǔ)構(gòu)造加權(quán)圖,利用測地線距離特征和顏色特征構(gòu)造權(quán)值矩陣,再應(yīng)用NJW算法得到最終的分割結(jié)果,實驗表明該算法在分割精度和計算復(fù)雜度上都有較大改善。

      2.2半監(jiān)督學(xué)習(xí)應(yīng)用

      文獻提出了一種有約束的半監(jiān)督譜聚類特征向量選擇算法。該算法通過大量的監(jiān)督信息尋找能體現(xiàn)數(shù)據(jù)結(jié)構(gòu)特征的向量組合,來獲得優(yōu)于傳統(tǒng)譜聚類算法的聚類性能,采用MNIST手寫體數(shù)據(jù)集和UCI標準數(shù)據(jù)集進行仿真實驗,結(jié)果驗證了該算法的有效性和魯棒性。

      2.3大數(shù)據(jù)分析應(yīng)用

      李斌等提出了一種新的聚類算法NGKCA。首先利用譜聚類NJW算法對大數(shù)據(jù)集進行列降維和數(shù)據(jù)歸一化處理,其次引入對初始值不敏感的粒子群算法對數(shù)據(jù)集進行行降維從而選出臨時的聚類中心集,接著通過全局kmeans算法獲取聚類中心點,最后使用粒子群算法調(diào)整聚類中心點獲取最終的聚類劃分。實驗結(jié)果表明,該算法具有更好的穩(wěn)定性和更高的檢測率、更優(yōu)的時間復(fù)雜度,適用于解決大數(shù)據(jù)環(huán)境下的聚類問題。

      2.4其它應(yīng)用

      朱正偉提出基于譜聚類的入侵檢測技術(shù),采用KDD CUP99數(shù)據(jù)集實驗,結(jié)果表明譜聚類的檢測率和誤報率普遍優(yōu)于Kmeans和層次聚類算法。周林等提出基于譜聚類的聚類集成算法。先利用譜聚類的內(nèi)在特性構(gòu)造多樣性的聚類成員,然后用連接三元組算法計算相似度矩陣,再對該矩陣使用譜聚類算法以得到集成結(jié)果。最后,用Nystrom采樣算法有效降低了算法的計算復(fù)雜度,使得算法能擴展到大規(guī)模應(yīng)用。實驗結(jié)果表明,較之其它常見的聚類集成算法,該算法更優(yōu)越、更有效,能較好地解決數(shù)據(jù)聚類、圖像分割等問題。

      3研究展望

      譜聚類算法是應(yīng)用矩陣譜分析理論得到聚類數(shù)據(jù)的新特征,利用新的數(shù)據(jù)特征對原數(shù)據(jù)進行聚類。從國內(nèi)外研究現(xiàn)狀來看,譜聚類算法已被廣泛運用于各個領(lǐng)域,并取得很好的效果。但是,譜聚類算法仍然存在一些亟待深入研究的問題:

      (1)如何智能地確定需要聚類的個數(shù)。這不僅僅是譜聚類,也是其它很多聚類算法所面臨的困難和挑戰(zhàn)。目前已有的譜聚類算法中,如RCut、NLDR(Nonlinear Dimensionality Reduction,非線性降維)算法能夠自適應(yīng)確定聚類個數(shù),但是聚類效果并不是很理想,亟需改進。

      (2)如何解決模糊聚類問題。譜聚類算法來源于譜圖分割領(lǐng)域,圖分割后一般子圖與子圖之間是不重疊的。譜聚類算法在面對這種情況時往往聚類效果不佳。

      (3)如何運用到海量數(shù)據(jù)中。譜聚類算法涉及到求解大型矩陣的特征值分解問題,其計算復(fù)雜度高、計算量和存儲量太大,不利于在大規(guī)模數(shù)據(jù)中計算和擴展,這對譜聚類的應(yīng)用前景非常不利。雖然己經(jīng)有研究者提出優(yōu)化這一問題的方法,但仍然是未來研究的方向。

      (4)如何與深度學(xué)習(xí)相融合。近年來深度學(xué)習(xí)發(fā)展迅猛,文獻介紹了譜算法中算子譜刻畫映射的能力,學(xué)者們開始思考將譜聚類算法與深度學(xué)習(xí)相結(jié)合并幫助提高算法效率。

      參考文獻:

      蔡曉妍,戴冠中,楊黎斌.譜聚類算法綜述[J].計算機科學(xué),2008,35(7):1418.

      WU Z,LEAHY R.An optimal graph theoretic approach to data clustering:theory and its application to image segmentation[J].IEEE Trans on PAMI,1993,15(11):11011113.

      SHI J,MALIK J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):888905.

      HAGEN L,KAHNG A B.New spectral methods for ratio cut partitioning and clustering[J].ComputerAided Design,1992,11(9):10741085.

      SARKAR S,SOUNDARARAJAN P.Supervised learning of large perceptual organization:Graph spectral partitioning and learning automata[J].IEEE Transaction on Pattern Analysis and Machine Intelligence,2000,22(5):504525.

      猜你喜歡
      應(yīng)用研究
      節(jié)奏訓(xùn)練在初中音樂課程教學(xué)中的應(yīng)用研究
      高校數(shù)碼鋼琴教學(xué)模式的構(gòu)建與應(yīng)用研究
      旅游管理教學(xué)中情境教學(xué)法的應(yīng)用研究
      科技視界(2016年18期)2016-11-03 23:23:07
      無線傳感器網(wǎng)絡(luò)優(yōu)化的應(yīng)用與研究
      科技視界(2016年18期)2016-11-03 22:35:48
      電力信息采集系統(tǒng)中對載波現(xiàn)場測試儀的應(yīng)用
      現(xiàn)代機械制造工藝與精密加工技術(shù)的應(yīng)用分析
      PPP模式在我國基礎(chǔ)設(shè)施建設(shè)中的應(yīng)用研究
      時代金融(2016年23期)2016-10-31 13:58:17
      “黑農(nóng)”大豆育種技術(shù)及應(yīng)用研究
      進駐數(shù)字課堂的新興教學(xué)媒體
      AG接入技術(shù)在固網(wǎng)NGN的應(yīng)用研究
      桐梓县| 岱山县| 汽车| 浑源县| 高密市| 凌海市| 海南省| 建德市| 德令哈市| 余江县| 定日县| 青海省| 武功县| 车险| 台湾省| 屏东市| 克什克腾旗| 吉安县| 绩溪县| 尚义县| 广河县| 江门市| 广昌县| 九台市| 和田市| 水富县| 潜江市| 铜陵市| 万荣县| 大关县| 栾川县| 南汇区| 台东市| 乌拉特前旗| 陇西县| 义马市| 车险| 二连浩特市| 广平县| 定南县| 福建省|