正則化低秩子空間譜聚類算法

《正則化低秩子空間譜聚類算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、正則化低秩子空間譜聚類算法　　摘要：為解決缺損數(shù)據(jù)譜聚類中的不適定問題，提出一種正則化低秩子空間譜聚類算法。首先根據(jù)數(shù)據(jù)集建立核范數(shù)正則化低秩矩陣分解模型，然后用迭代法求解模型得出系數(shù)矩陣，由此構(gòu)造相似矩陣，最后利用譜聚類算法得出聚類結(jié)果。實(shí)驗(yàn)表明，該算法在一定程度上可以解決缺損數(shù)據(jù)的譜聚類問題，抑制噪聲，獲得質(zhì)量較高的聚類結(jié)果。　　關(guān)鍵詞：聚類分析；譜聚類；低秩子空間；不適定；正則化　　DOIDOI：10.11907/rjdk.162025　　中圖分類號(hào)：TP311　　文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-7800（2016）012-

2、0022-03　　0引言　　聚類分析是數(shù)據(jù)挖掘的一個(gè)重要研究領(lǐng)域，在統(tǒng)計(jì)學(xué)、生物學(xué)、模式識(shí)別、機(jī)器學(xué)習(xí)和社會(huì)科學(xué)中有著極為廣泛的應(yīng)用。所謂聚類就是將數(shù)據(jù)對(duì)象分組成為多個(gè)類或簇，使得在同一簇中的對(duì)象之間具有較高的相似度，而不同簇中的對(duì)象差別較大。k-均值聚類是聚類分析中最經(jīng)典的算法，算法簡(jiǎn)單，可用于多種類型數(shù)據(jù)的聚類。但當(dāng)數(shù)據(jù)集為非凸時(shí)，k-均值聚類往往陷于局部最優(yōu)，聚類效果欠佳。另外，對(duì)于大小或密度不均勻的簇，k-均值聚類通常無法處理[1]。6　　譜聚類是一種新型的聚類分析方法，可以克服k-均值聚類等經(jīng)典方法的一些缺陷[2]。譜聚類

3、方法以圖論中的譜圖理論為基礎(chǔ)，將聚類問題轉(zhuǎn)化為圖的最優(yōu)劃分問題。在眾多圖的最優(yōu)劃分準(zhǔn)則中，歸一化割集準(zhǔn)則的劃分效果相對(duì)較好，是譜聚類中常用的劃分準(zhǔn)則[3]。對(duì)于給定的劃分準(zhǔn)則和聚類數(shù)目k，譜聚類通常采用多路譜聚類算法將數(shù)據(jù)集劃分為k個(gè)簇[4]?！　∽钤绲淖V聚類算法是Ng，Bach和Jordan[4-5]提出的多路譜聚類方法。代表性的譜聚類算法還有Meila[6]提出的多路歸一化割譜聚類方法；Vidal[7]提出的子空間譜聚類方法；Wang等[8]提出的多流形譜聚類方法；Cheng等[9]提出的低秩譜聚類方法；Elhamifar等[1

4、0]提出的稀疏子空間譜聚類方法。　　在眾多譜聚類算法中，低秩稀疏子空間譜聚類越來越受到學(xué)者的重視。在有些實(shí)際問題中，數(shù)據(jù)并不符合混合子空間的假設(shè)，分析這種數(shù)據(jù)具有很大的挑戰(zhàn)性。研究表明，基于譜聚類的方法是處理該類問題的有效方法。雖然這類數(shù)據(jù)本身無法使用相互表示的方式，但是數(shù)據(jù)的特征可相互線性表示，且表示系數(shù)具有稀疏性或低秩性的特點(diǎn)。目前，這種低秩表示方法已被擴(kuò)展用于圖像處理。　　本文在低秩子空間譜聚類算法的基礎(chǔ)上，引入正則化過程以解決不適定問題，并根據(jù)數(shù)值實(shí)驗(yàn)對(duì)該算法進(jìn)行性能測(cè)試。　　1譜聚類矩陣　　譜聚類的基本思想是將聚類問題轉(zhuǎn)化

5、為圖的最優(yōu)劃分問題，利用圖的最優(yōu)劃分準(zhǔn)則，使劃分出的子圖之間的邊權(quán)之和較小，而子圖內(nèi)的邊權(quán)之和較大。下面簡(jiǎn)要介紹本文算法設(shè)計(jì)過程中涉及到的譜聚類矩陣。6　　上述譜聚類矩陣性質(zhì)類似但又有差異，不同的譜聚類算法可以選用不同的譜聚類矩陣?！　?正則化低秩子空間譜聚類算法　　2.1不適定問題與正則化　　問題的適定性最早由法國數(shù)學(xué)家Hadamard[11]指出問題的解存在且唯一。不適定性通常包含兩重含義：?jiǎn)栴}解的多重性和問題對(duì)擾動(dòng)的敏感性。在很長一段時(shí)間內(nèi)，人們認(rèn)為研究不適定問題沒有意義。直到1956年，人們逐漸發(fā)現(xiàn)適定問題并不能正確描述許多

6、自然現(xiàn)象，許多現(xiàn)象均具有不適定性。至此，不適定問題的研究才引起相關(guān)學(xué)者的重視?！　∧壳?，對(duì)于不適定問題，已有PST、GPST、MonteCarlo、最佳攝動(dòng)量、正則化等方法。其中，正則化是求解不適定問題的主要方法。不適定問題的正則化最早由前蘇聯(lián)數(shù)學(xué)家吉洪諾夫提出，其基本思想是：將所研究問題的解和相應(yīng)空間加以適當(dāng)限制，以保證當(dāng)原始數(shù)據(jù)有缺損或擾動(dòng)時(shí)，問題的近似解與真解具有較高的近似度。由于這種方法是通過對(duì)原問題附加“規(guī)則”，從而保證解的存在性和數(shù)值穩(wěn)定性，因而稱之為“正則化”方法。　　2.2低秩矩陣分解　　大部分圖像中都含有一些公共模

7、式，這些基本模式稱為基底或字典。通過這些基底的線性組合，可以表示出幾乎所有的圖像。在許多情況下，基底的數(shù)量是較少的，即許多圖像的數(shù)據(jù)矩陣是低秩或近似低秩的。因?yàn)榈椭染仃嚳梢员挥成涞降途S空間進(jìn)行分析，這就給圖像處理帶來了極大便利。6　　但在有些情況下，由于數(shù)據(jù)缺損及噪聲影響，破壞了矩陣的低秩性。因?yàn)樵肼曂欠植枷∈璧?，為了恢?fù)矩陣的低秩性，可將略低數(shù)據(jù)矩陣D分解為兩個(gè)矩陣A與E之和，其中第一個(gè)矩陣A低秩，第二個(gè)矩陣E稀疏。具體分解模型如下[13]：　　3數(shù)值實(shí)驗(yàn)　　為了檢驗(yàn)正則化低秩子空間譜聚類算法的性能，本文選取了兩組典型的譜聚類

8、仿真數(shù)據(jù)和兩個(gè)人在不同光照下的共20幅人臉圖像進(jìn)行實(shí)驗(yàn)?！　D1是視覺重建中的問題。特征提取是視覺重建的一個(gè)關(guān)鍵環(huán)節(jié)，圖1中的十字的位置信息已經(jīng)提取出來，為了確定十字的中心位置，要求將十字中的點(diǎn)按照“橫”和“豎”分為兩類?！　D2為一