視覺(jué)聚類機(jī)-一種基于視覺(jué)心理學(xué)的新方法

視覺(jué)聚類機(jī):

一種基于視覺(jué)心理學(xué)的新方法徐宗本:8080/web/zbxu西安交通大學(xué)信息與系統(tǒng)科學(xué)研究所綱要1234聚類問(wèn)題與進(jìn)展概述生物視覺(jué)的啟示視覺(jué)聚類機(jī)試驗(yàn)與應(yīng)用whatwhyhowHowbetter1.聚類問(wèn)題與進(jìn)展概述根據(jù)相似性把對(duì)象（數(shù)據(jù)）分組的過(guò)程數(shù)據(jù)挖掘中一個(gè)基本問(wèn)題是模式識(shí)別與知識(shí)發(fā)現(xiàn)的基礎(chǔ)被廣泛的應(yīng)用于計(jì)算機(jī)視覺(jué)與機(jī)器學(xué)習(xí)領(lǐng)域圖像分割地理數(shù)據(jù)聚類文本挖掘基因數(shù)據(jù)

什么叫相似？多么相似才可歸為一類？1.聚類問(wèn)題與進(jìn)展概述聚類算法（按聚類形式劃分）分裂方法和層次方法分裂方法：通過(guò)極小化一個(gè)代價(jià)函數(shù)來(lái)獲得數(shù)據(jù)集的分割，是一個(gè)迭代優(yōu)化過(guò)程。代價(jià)函數(shù)通常根據(jù)極大化類內(nèi)相似性和極小化類間相似性的原則確定。優(yōu)點(diǎn)：計(jì)算簡(jiǎn)單；存儲(chǔ)量??；對(duì)凸數(shù)據(jù)效果佳.

缺陷：需預(yù)先指定類數(shù)，對(duì)非凸數(shù)據(jù)效果差.

代表性方法：K-Means[R.Dues,1976];spectral-Ng[N.Y.Ng,2001];Min-cut[E.L.Johson,1993];層次方法：引進(jìn)一個(gè)層次尺度和歸并原則，在每一個(gè)層次上使用分裂方法，形成數(shù)據(jù)的一個(gè)層次化聚類結(jié)構(gòu)。優(yōu)點(diǎn)：提供多尺度聚類結(jié)果,可解決聚類有效性問(wèn)題。缺陷：計(jì)算代價(jià)高.

代表性方法：CURE[S.Guha,1998];ROCK[S.Guha;2000];Chameleon[G.Krypis,computer,1999];ScaleSpaceFiltering[Y.Leung,J.S.Zhang,Z.B.Xu,2000];1.聚類問(wèn)題與進(jìn)展概述基于密度的方法：利用數(shù)據(jù)集的密度估計(jì)和不同的密度區(qū)域的描述進(jìn)行聚類。優(yōu)點(diǎn)：在密度估計(jì)正確的前提下效果好.缺陷：聚類結(jié)果依賴于對(duì)數(shù)據(jù)密度估計(jì)的好壞.

代表性方法：ScaleSpaceFiltering[Y.Leung,J.S.Zhang,Z.B.Xu,PAMI2000];MeanShift[D.Comaniciu,P.Meer,2002]

基于圖的方法：根據(jù)數(shù)據(jù)集和相似性產(chǎn)生連通圖，利用圖的分割原理進(jìn)行聚類。優(yōu)點(diǎn)：直觀；易解釋；不受數(shù)據(jù)密度與形狀的限制。缺陷：對(duì)相似性定義十分敏感.

代表性方法：Min-cut[E.L.Johson,Mathprogramming1993];optimalgraphtheoretic[Z.Wu,PAMI1993];Chameleon[G.Krypis,computer,1999]

基于譜的方法：利用相似性構(gòu)造拉普拉斯矩陣(A=相似性矩陣;D=行對(duì)角陣;L=D-A)，利用此矩陣分解進(jìn)行降維以達(dá)到聚類的目的.優(yōu)點(diǎn)：簡(jiǎn)單易操作，不受數(shù)據(jù)集密度與形狀的限制。缺陷：類數(shù)需預(yù)先給定,對(duì)相似性定義十分敏感.

。代表性方法：spectral-Ng[N.Y.Ng,Neur.Infor.procsys2001];spectral-shi[J.shi,PAMI2000]聚類算法（按建模方法劃分）1.聚類問(wèn)題與進(jìn)展概述主要挑戰(zhàn)非均衡數(shù)據(jù)數(shù)量上的不均衡密度上的不均衡類的形狀多樣，結(jié)構(gòu)復(fù)雜數(shù)據(jù)集包含大量的噪聲和異常點(diǎn)經(jīng)典算法的評(píng)價(jià):

1各有自己的優(yōu)勢(shì)，某些算法有成功的應(yīng)用；2對(duì)先驗(yàn)的依賴較強(qiáng),自動(dòng)化程度不高(密度,類數(shù),參數(shù)的選擇等等)，難以處理復(fù)雜結(jié)構(gòu)(流行,重疊等等)2.生物視覺(jué)的啟示visualmodeling基本思想：了解視覺(jué)系統(tǒng)的工作原理，并用計(jì)算機(jī)模擬其功能解決數(shù)據(jù)聚類問(wèn)題預(yù)期目標(biāo)：

自動(dòng)聚類(類別、參數(shù)等);結(jié)構(gòu)復(fù)雜數(shù)據(jù)(符合視覺(jué)認(rèn)識(shí))2.生物視覺(jué)的啟示（宏觀）人類視覺(jué)系統(tǒng)以及信息流視覺(jué)系統(tǒng)由兩部分組成：視網(wǎng)膜和視皮層視網(wǎng)膜分為三層，最內(nèi)層光感受器和最外層的神經(jīng)節(jié)細(xì)胞視皮層分為初級(jí)視皮層和高級(jí)視皮層，各自掌管不同的功能視覺(jué)信息處理抽象為：多層的特征提取+特征整合(基于注意、記憶等的概念識(shí)別)特征提取特征整合2.生物視覺(jué)的啟示（微觀）感受野(RF)

:影響一個(gè)神經(jīng)元響應(yīng)的區(qū)域稱為該神經(jīng)元的感受野(兩種理解)。而感受野上的響應(yīng)模式稱為感受野函數(shù)。每一層上的神經(jīng)元收集前面神經(jīng)元所傳來(lái)的信息，而響應(yīng)強(qiáng)度可由感受野函數(shù)（RFf）進(jìn)行描述注：1

層次化的特征提取過(guò)程

2感受野函數(shù)即為濾波器H.B.Barlow,1953;Hubel,1962視覺(jué)信息處理的基本方式2.生物視覺(jué)的啟示感受野形狀的多樣性神經(jīng)元對(duì)刺激的選擇性注：感受野的范圍及響應(yīng)模式與刺激模式有關(guān)感受野、感受野函數(shù)以及響應(yīng)強(qiáng)度：

感受野的形狀和響應(yīng)模式放電強(qiáng)度與刺激模式的關(guān)系2.生物視覺(jué)的啟示圖像上的特征提取過(guò)程……注：卷積核中可以融入尺度參數(shù)、方向參數(shù)等等去提取斯蒂各種各樣的特征2.生物視覺(jué)的啟示格式塔組織原理：

物體更容易作為一個(gè)整體被感知鄰近率：相鄰的物體容易看做一類連續(xù)率：整體趨于某種形狀的對(duì)象趨于看成一類相似率：有相似屬性(顏色、形狀、紋理等)的更容易歸為一類封閉率:不封閉的物體更容易理解為封閉的對(duì)稱率：對(duì)稱的物體更容易歸為一類鄰近率連續(xù)率相似率封閉率對(duì)稱率高層認(rèn)知原理3.視覺(jué)聚類機(jī)視覺(jué)聚類機(jī)基本思想模擬視覺(jué)心理學(xué)原理處理數(shù)據(jù)聚類通過(guò)模擬視覺(jué)的分層特征提取功能與特征整合原理進(jìn)行聚類通過(guò)提取數(shù)據(jù)結(jié)構(gòu)特征定義合適的感受野函數(shù)以提取數(shù)據(jù)圖像的多尺度特征通過(guò)格式塔原理進(jìn)行特征整合3.視覺(jué)聚類機(jī)J.M.SantosandJ.Marquares,2005密度特征：一個(gè)數(shù)據(jù)鄰域內(nèi)的分布密度特征(鄰近率+相似率)

連通特征：一個(gè)數(shù)據(jù)集局部密集點(diǎn)在整體上所形成的流形結(jié)構(gòu)特征（連續(xù)率）結(jié)構(gòu)方向特征：數(shù)據(jù)連通特征所呈現(xiàn)的整體方向特征（連續(xù)率+相似率）數(shù)據(jù)集的結(jié)構(gòu)特征3.視覺(jué)聚類機(jī)數(shù)據(jù)集看作一個(gè)抽象圖像單個(gè)感受野或周圍多個(gè)感受野的相互影響能充分體現(xiàn)數(shù)據(jù)聚類的三個(gè)結(jié)構(gòu)特征感受野函數(shù)采用高斯類型(對(duì)特定應(yīng)用而言)感受野函數(shù)模型：①②②:流行向量①：各向異性矩陣基于數(shù)據(jù)特征的感受野函數(shù)(RFf)建模3.視覺(jué)聚類機(jī)流行向量的計(jì)算步驟1：構(gòu)建近鄰圖步驟2：計(jì)算鄰近兩點(diǎn)的最短距離步驟3：計(jì)算流行向量

流行向量：注：1.最近距離采用Floyd經(jīng)典算法

2.最近距離可以使得連通區(qū)域的相似性最大1.數(shù)據(jù)的連通性建模3.視覺(jué)聚類機(jī)2.

數(shù)據(jù)的方向性建模各向異性矩陣的計(jì)算步驟1：協(xié)方差矩陣的計(jì)算步驟2：計(jì)算各向異性矩陣各向異性矩陣(描述數(shù)據(jù)點(diǎn)局部區(qū)域的方向)：注：1.各向異性矩陣可以描述點(diǎn)的初始區(qū)域的范圍

2.參數(shù)是一個(gè)極小的數(shù)，僅為保證矩陣可逆3.視覺(jué)聚類機(jī)3.數(shù)據(jù)的結(jié)構(gòu)密度建模各向異性矩陣的計(jì)算步驟1：計(jì)算每一對(duì)近鄰點(diǎn)的有向響應(yīng)強(qiáng)度步驟2：獲得每一對(duì)近鄰點(diǎn)之間的無(wú)向響應(yīng)強(qiáng)度對(duì)稱感受野函數(shù)矩陣：注：同質(zhì)區(qū)域內(nèi)鄰近點(diǎn)信息傳遞強(qiáng)度大，而非同質(zhì)區(qū)域鄰近點(diǎn)信息傳遞強(qiáng)度則弱3.視覺(jué)聚類機(jī)數(shù)據(jù)結(jié)構(gòu)的特征提取

(濾波過(guò)程)類的組織與識(shí)別算法的收斂性視覺(jué)聚類機(jī)框架注：該濾波過(guò)程滿足半群性質(zhì)，可以寫(xiě)成一個(gè)層次化的濾波過(guò)程3.視覺(jué)聚類機(jī)視覺(jué)聚類機(jī)算法框架數(shù)據(jù)圖像的分層表達(dá)類的識(shí)別有效類的識(shí)別原始數(shù)據(jù)圖像數(shù)據(jù)圖像的分層表達(dá)3.視覺(jué)聚類機(jī)算子G1：獲得分層聚類結(jié)果通過(guò)讀取每一層的數(shù)據(jù)圖像，識(shí)別單層聚類的結(jié)果，每一個(gè)聚合點(diǎn)即可視為一個(gè)類別以達(dá)到自動(dòng)識(shí)別類數(shù)的目的。注：本步的實(shí)現(xiàn)的前提是算法正則收斂，類數(shù)單調(diào)減少的（理論分析中給出證明）t時(shí)刻的一次劃分3.視覺(jué)聚類機(jī)算子G2：通過(guò)分層聚類獲得有效聚類結(jié)果類的壽命*：類的產(chǎn)生到消失所經(jīng)歷的時(shí)間段通過(guò)分層聚類的結(jié)果，引入類壽命的概念來(lái)識(shí)別出最穩(wěn)定的類結(jié)果*Y.Leung,J.S.ZhangandZ.B.Xu,clusteringbyscale-spacefiltering,PAMI2000.類的壽命有效聚類結(jié)果一次劃分的壽命生成有效聚類的時(shí)刻3.視覺(jué)聚類機(jī)視覺(jué)聚類算法流程圖步驟1:

為每一點(diǎn)計(jì)算感受野函數(shù)（響應(yīng)與數(shù)據(jù)集有關(guān)），并構(gòu)造濾波矩陣步驟2:

層次化聚類步驟2.1:

多層的濾波過(guò)程步驟2.2:

利用算子G1識(shí)別類步驟2.3:

返回2.1直到滿足終止條件步驟3:

利用算子G2識(shí)別最終類別3.視覺(jué)聚類機(jī)算法的計(jì)算復(fù)雜性聚類算法的性質(zhì)分析收斂性：算法總是正則收斂，并且單調(diào)非增的收斂到最終的一類或者幾個(gè)連通分支4.試驗(yàn)與應(yīng)用

算法的可行性

算法的有效性

算法的魯棒性

應(yīng)用4.試驗(yàn)與應(yīng)用(可行性)可行性：對(duì)一個(gè)非平衡密度特征的數(shù)據(jù)集進(jìn)行聚類，聚類過(guò)程再次表明新算法是可行的原始數(shù)據(jù)集分層聚類過(guò)程分層聚類識(shí)別有效聚類結(jié)果4.試驗(yàn)與應(yīng)用(有效性)視覺(jué)聚類算法的有效性：選擇一組具有代表性的二維數(shù)據(jù)集以及真實(shí)數(shù)據(jù)集去測(cè)試各種算法的聚類結(jié)果測(cè)試算法包括各種典型方法：基于密度、圖、譜等算法4.試驗(yàn)與應(yīng)用(有效性)視覺(jué)聚類機(jī)結(jié)果4.試驗(yàn)與應(yīng)用(有效性)尺度空間濾波的結(jié)果；PAMI20004.試驗(yàn)與應(yīng)用(有效性)Chameleon結(jié)果Clutosoftware4.試驗(yàn)與應(yīng)用(有效性)Spectral-Ng算法的結(jié)果4.試驗(yàn)與應(yīng)用(有效性)在真實(shí)數(shù)據(jù)集上的算法有效性比較：數(shù)據(jù)集來(lái)自于UCI和USPS數(shù)據(jù)庫(kù)，精度采用NMI衡量4.試驗(yàn)與應(yīng)用(魯棒性)參數(shù)的魯棒性近鄰參數(shù)的改變對(duì)結(jié)果的影響隱參數(shù)特意人工選擇，測(cè)試其改變對(duì)結(jié)果的影響噪聲的魯棒性：比較的算法為抗噪效果較好的典型算法小噪聲下的精度比較大噪聲的結(jié)果比較算法的魯棒性試驗(yàn)設(shè)計(jì)：目的是測(cè)試參數(shù)的穩(wěn)定性以及對(duì)噪聲的魯棒性4.試驗(yàn)與應(yīng)用(參數(shù)的穩(wěn)定性)穩(wěn)定的結(jié)果近鄰值大于35的結(jié)果隱參k=4的結(jié)果隱參k=3的結(jié)果4.試驗(yàn)與應(yīng)用(噪聲魯棒性)小噪聲的魯棒性：原始數(shù)據(jù)集的生成帶有高斯噪聲，然后不斷的在原始數(shù)據(jù)集上加入5%，40%和100%的噪聲比較各算法的聚類精度測(cè)試的算法包括：spectral-Ng,self-tuningspectralclustering,noiserobustspectralclustering4.試驗(yàn)與應(yīng)用(噪聲的魯棒性)大背景噪聲下的聚類結(jié)果比較（200%背景噪聲）VClustSpectral-NgChameleonDBScanNoiserobustspectralclustering4.試驗(yàn)與應(yīng)用圖像分割：強(qiáng)紋理、顏色漸變4.試驗(yàn)與應(yīng)用第一幅圖像素點(diǎn)分布聚