5. 帶約束的概率半監(jiān)督聚類

在某些聚類任務(wù)中冻押,可以以成對(duì)約束的形式獲得有限的監(jiān)督梨睁,即標(biāo)記為屬于相同或不同簇的實(shí)例對(duì)鬓椭。由此產(chǎn)生的問(wèn)題稱為半監(jiān)督聚類(semi-supervised clustering)颠猴,這是一個(gè)源于傳統(tǒng)的無(wú)監(jiān)督學(xué)習(xí)環(huán)境的半監(jiān)督學(xué)習(xí)實(shí)例。利用約束形式的監(jiān)督提高聚類質(zhì)量的算法有多種小染。這些算法通常利用成對(duì)約束來(lái)修改聚類目標(biāo)函數(shù)或?qū)W習(xí)聚類失真度量翘瓮。本章介紹了一種將隱馬爾可夫隨機(jī)域(HMRFS)作為半監(jiān)督聚類的概率生成模型的方法,從而為將基于約束的監(jiān)督納入基于原型的聚類提供了一個(gè)原則性框架裤翩∽手眩基于HMRF的模型允許使用廣泛的聚類失真度量,包括Bregman發(fā)散(例如踊赠,平方歐幾里得距離呵扛、Kullback-Leibler發(fā)散)和方向距離度量(例如,余弦距離)筐带,使其適用于許多領(lǐng)域今穿。該模型引入了HMRF-kmeans算法,該算法將從模型的聯(lián)合概率中導(dǎo)出的目標(biāo)函數(shù)最小化伦籍,并允許統(tǒng)一基于約束和基于距離的半監(jiān)督聚類方法蓝晒。此外,在查詢驅(qū)動(dòng)框架中選擇信息性成對(duì)約束的兩階段主動(dòng)學(xué)習(xí)算法是從HMRF模型中派生出來(lái)的鸽斟,這有助于提高集群性能拔创,同時(shí)用戶的監(jiān)督相對(duì)較少。

5.1 簡(jiǎn)介

本章主要研究帶約束的半監(jiān)督聚類富蓄,即當(dāng)以成對(duì)約束的形式提供有限監(jiān)督時(shí)剩燥,將一組數(shù)據(jù)點(diǎn)劃分成特定數(shù)量的簇的問(wèn)題。雖然傳統(tǒng)上認(rèn)為聚類是無(wú)監(jiān)督學(xué)習(xí)的一種形式,因?yàn)闆](méi)有給出類標(biāo)簽灭红,但包含成對(duì)約束使其成為半監(jiān)督學(xué)習(xí)任務(wù)侣滩,無(wú)監(jiān)督聚類算法的性能可以使用有限的訓(xùn)練數(shù)據(jù)得到改善。

成對(duì)監(jiān)督通常作為必須鏈接和不能鏈接數(shù)據(jù)點(diǎn)上的約束提供:必須鏈接約束表示對(duì)中的兩個(gè)點(diǎn)應(yīng)放置在同一個(gè)簇中变擒,而不能鏈接約束表示對(duì)中的兩個(gè)點(diǎn)應(yīng)屬于不同的簇君珠。斯特斯〗堪撸或者策添,必須鏈接和不能鏈接約束有時(shí)分別稱為等價(jià)約束和非等價(jià)約束。通常毫缆,約束是“軟”的唯竹,也就是說(shuō),違反約束的集群是不可取的苦丁,但不是禁止的浸颓。

在某些應(yīng)用中,類標(biāo)簽形式的監(jiān)督可能不可用旺拉,同時(shí)很容易獲得成對(duì)的約束产上,從而需要利用此類監(jiān)督的方法。例如蛾狗,完整的類標(biāo)簽可能在對(duì)話中的說(shuō)話人識(shí)別聚類(Bar Hillel等人晋涣,2003)或車道搜索的GPS數(shù)據(jù)聚類(Wagstaff等人,2001)中是未知的沉桌。在某些領(lǐng)域姻僧,成對(duì)約束自然發(fā)生,例如蒲牧,生物學(xué)中的相互作用蛋白質(zhì)(DIP)數(shù)據(jù)庫(kù)數(shù)據(jù)集包含有關(guān)過(guò)程中共同發(fā)生的蛋白質(zhì)的信息撇贺,可以看作是在聚類過(guò)程中必須鏈接的約束。此外冰抢,在交互式學(xué)習(xí)設(shè)置中松嘶,非領(lǐng)域?qū)<业挠脩粲袝r(shí)可以以“必須鏈接”的形式提供反饋,并且不能比類標(biāo)簽更容易地鏈接約束挎扰,因?yàn)樘峁┘s束并不要求用戶對(duì)數(shù)據(jù)集中的類別具有重要的先驗(yàn)知識(shí)翠订。

提出的半監(jiān)督聚類方法分為兩類,即基于約束和基于距離遵倦【〕基于約束的方法使用提供的監(jiān)督來(lái)指導(dǎo)算法進(jìn)行避免違反約束的數(shù)據(jù)分區(qū)(Demiriz等人,1999梧躺;Wagstaff等人似谁,2001傲绣;Basu等人,2002)巩踏。在基于距離的方法中秃诵,使用了一種使用點(diǎn)之間特定距離函數(shù)的現(xiàn)有聚類算法;但是塞琼,距離函數(shù)是參數(shù)化的菠净,并且學(xué)習(xí)了參數(shù)值,將必須鏈接的點(diǎn)集合在一起彪杉,并使不能鏈接的點(diǎn)進(jìn)一步分離(Bilenko和Mooney毅往,2003;Cohn等人派近,2003煞抬;Klein等人,2002年构哺;Xing等人,2003年)战坤。

本章描述了一種基于隱馬爾可夫隨機(jī)域(HMRFS)的半監(jiān)督聚類方法曙强,該方法將基于約束和基于距離的方法結(jié)合在一個(gè)統(tǒng)一的概率模型中。概率公式導(dǎo)致從觀測(cè)數(shù)據(jù)點(diǎn)的聯(lián)合概率途茫、它們的聚類分配和生成模型參數(shù)中導(dǎo)出一個(gè)聚類目標(biāo)函數(shù)碟嘴,該目標(biāo)函數(shù)可以使用期望最大化(em)型聚類算法進(jìn)行優(yōu)化。hmrf kmeans囊卜,即找到目標(biāo)函數(shù)的局部最小值娜扇。HMRF-kmeans可用于使用廣泛的畸變(距離)函數(shù)(1,即Bregman發(fā)散)執(zhí)行半監(jiān)督聚類(Banerjee等人栅组,2005b)雀瓢,其中包括各種有用距離,例如kl發(fā)散玉掸、平方歐幾里得距離刃麸、i發(fā)散和Itakuro-s。A到距離司浪。在許多應(yīng)用中泊业,例如基于向量空間模型的文本聚類,基于向量間角度余弦的方向距離測(cè)量更為合適(Baeza Yates和Ribeiro Neto啊易,1999)吁伺。已經(jīng)開(kāi)發(fā)出聚類算法,利用適合方向數(shù)據(jù)的畸變測(cè)量(Dhillon和Modha租谈,2001篮奄;Banerjee等人,2005 a),并且HMRF-kmeans框架自然地?cái)U(kuò)展了它們宦搬。

帶有約束的半監(jiān)督集群的一個(gè)實(shí)際方面是如何在現(xiàn)實(shí)環(huán)境中獲得最大程度的信息約束牙瓢,在這種環(huán)境中,可以在交互式學(xué)習(xí)環(huán)境中向用戶發(fā)出有限的查詢集(McCallum和Nigam间校,1998年b)矾克。在這種情況下,應(yīng)該向用戶提出較少的查詢憔足,以獲得能夠顯著提高聚類準(zhǔn)確性的約束胁附。為此,本文提出了一種新的主動(dòng)學(xué)習(xí)方法滓彰,通過(guò)向表單用戶詢問(wèn)“這兩個(gè)例子在同一類還是不同類中控妻?”,為半監(jiān)督聚類選擇了良好的成對(duì)約束條件揭绑」颍“提高了聚類性能。

5.2?半監(jiān)督聚類的HMRF模型

基于分區(qū)原型的集群是正在考慮的底層無(wú)監(jiān)督聚類設(shè)置他匪。在這樣的設(shè)置中菇存,一組數(shù)據(jù)點(diǎn)被劃分成預(yù)先指定數(shù)量的簇,其中每個(gè)簇都有一個(gè)代表性的(或“原型”)邦蜜,這樣一個(gè)定義良好的成本函數(shù)(包括點(diǎn)和簇代表之間的失真度量)被最小化依鸥。一個(gè)眾所周知的無(wú)監(jiān)督聚類算法,遵循這個(gè)框架是k-均值(Macqueen悼沈,1967)贱迟。

我們的半監(jiān)督學(xué)習(xí)模型考慮一個(gè)n 數(shù)據(jù)點(diǎn)X=(x_1,...,x_n)的樣本,每一個(gè)?x_i \in R^d為一個(gè) d-維 向量絮供,其中?x_{im}?代表它的第 m 個(gè)成分衣吠。該模型依賴于用于計(jì)算點(diǎn)之間距離的畸變測(cè)度d_AR^d \times R^d \rightarrow R,其中?A是畸變測(cè)度參數(shù)的集合壤靶。監(jiān)督作為兩組成對(duì)約束條件提供:must-link 限制?C_{ML}=\{(x_i,x_j) \}和 cannot-link 限制?C_{CL}=\{(x_i,x_j) \}蒸播,其中(x_i,x_j)\in C_{ML}?表示?x_i?和?x_j?被標(biāo)記屬于同一個(gè)簇,而?(x_i,x_j)\in C_{CL}表示x_i?和?x_j?被標(biāo)記屬于不同簇萍肆。約束可能伴隨著相關(guān)的違反成本W袍榆,其中W_{ij}表示違反約束點(diǎn)x_i和x_j之間的約束,如果存在這樣的約束塘揣,也就是包雀,(x_i,x_j)\in C_{ML}(x_i,x_j)\in C_{CL}。任務(wù)是將數(shù)據(jù)點(diǎn)集X劃分為K個(gè)不相交的簇(X_1,...,X_K)以便根據(jù)給定的失真度量d_A最小化點(diǎn)和相應(yīng)的集群代表之間的總失真亲铡,而約束沖突保持最小才写。

5.2.1 HMRF 模型組件

半監(jiān)督限制聚類的 HMRF 概率框架由以下組件組成:

a.?一個(gè)可觀測(cè)集X=(x_1,...,x_n)對(duì)應(yīng)于給定的數(shù)據(jù)點(diǎn)X葡兑。請(qǐng)注意,我們重載了符號(hào)赞草,并使用X引用給定的數(shù)據(jù)點(diǎn)集及其相應(yīng)的隨機(jī)變量纹冤。

b. 一個(gè)不可觀測(cè)(隱藏)集?Y=(y_1,...,y_n)對(duì)應(yīng)于X中數(shù)據(jù)點(diǎn)的聚類分配歇攻。每個(gè)隱藏變量y_i編碼點(diǎn)x_i的簇標(biāo)簽丛肮,并從聚類索引集合中獲取值(1,...,K)轩娶。

c.?一組不可觀測(cè)(隱藏)的生成模型參數(shù)\Theta ,由畸變測(cè)度參數(shù)A和代表M=(\mu_1,...,\mu_K)\Theta = \{A,M  \}沾凄。

d.?一組可觀測(cè)的約束變量C=(c_{12},c_{13},...,c_{(n-1)n})梗醇。每個(gè)c_{ij}是從集合中取值的三次變量(-1,0,1),其中c_{ij}=1表示(x_i,x_j)\in C_{ML}撒蟀,c_{ij}=-1表示:(x_i,x_j)\in C_{CL}叙谨,c_{ij}=0對(duì)應(yīng)于不受約束的對(duì)(x_i,x_j)

由于約束是完全觀察到的保屯,并且所描述的模型并不試圖對(duì)它們進(jìn)行生成建模手负,因此X,Y的聯(lián)合概率是以C編碼的約束為條件的。

圖5.1 顯示了一個(gè)簡(jiǎn)單的 HMRF 示例姑尺。X由五個(gè)數(shù)據(jù)點(diǎn)和相應(yīng)的變量(x_1,...,x_5)組成竟终,具有聚類標(biāo)簽Y=(y_1,...,y_5),每個(gè)值(1,2,3)表示三個(gè)聚類股缸。提供了三個(gè)成對(duì)約束:兩個(gè)必須鏈接約束(x_1,x_2)(x_1,x_4),一個(gè)不能鏈接約束(x_2,x_3)吱雏。相應(yīng)的約束變量是c_{12}=1,c_{14}=1c_{23}=-1敦姻;C中的所有其他變量都設(shè)置為零。任務(wù)是將五個(gè)點(diǎn)分成三個(gè)聚類歧杏。圖5.1展示了一種可能的聚類配置镰惦,它不違反任何約束。必須鏈接的點(diǎn)x_1,x_2x_4屬于聚類 1犬绒;不能與x_2鏈接的點(diǎn)x_3分配給集群2旺入;不涉及任何約束的點(diǎn)x_5屬于集群3

5.2.2 標(biāo)簽上的馬爾科夫隨機(jī)場(chǎng)

每一個(gè)隱藏的隨機(jī)變量y_i\in Y代表x_i \in X的簇標(biāo)簽與一組鄰居N_i相關(guān)聯(lián)凯力。鄰居集合定義為x_i必須鏈接或不能鏈接的所有點(diǎn):N_i=\{y_j|(x_i,x_j)\in C_{ML} or (x_i,x_j) \in C_{CL}   \}茵瘾。


圖 5.1 一個(gè)隱馬爾科夫隨機(jī)場(chǎng)

在隱變量Y上定義的結(jié)果隨機(jī)場(chǎng)是一個(gè)馬爾可夫隨機(jī)場(chǎng),其中隱變量上的條件概率分布服從馬爾可夫性質(zhì)咐鹤。

\forall i,P(y_i|Y-\{y_i    \},\Theta,C)=P(y_i|N_i,\Theta,C)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(5.1)

因此拗秘,給定模型參數(shù)和約束集的每一個(gè)x_iy_i的條件概率,僅取決于必須鏈接或不能鏈接到x_i的觀測(cè)變量的簇標(biāo)簽祈惶。然后雕旨,根據(jù)Hammersley-Clifford定理(Hammersley和Clifford扮匠,1971),特定標(biāo)簽配置y的先驗(yàn)概率可以表示為吉布斯分布(Geman和Geman凡涩,1984)棒搜,因此

P(Y|\Theta,C)=\frac{1}{Z} exp(-v(Y))=\frac{1}{Z} \bigg(-\sum_{N_i\in N} v_{N_i}(Y)\bigg)? ? ? ? ? ? ? ? ? ? ? ? ?(5.2)

其中,N是所有鄰域的集合活箕,Z是分區(qū)函數(shù)(規(guī)范化項(xiàng))力麸,v(Y)是整體標(biāo)簽配置勢(shì)函數(shù),可以分解為函數(shù)v_{N_i}(Y)的總和讹蘑,每個(gè)函數(shù)表示標(biāo)簽配置Y中每個(gè)鄰域N_i的潛力末盔。因?yàn)槊總€(gè)鄰域的勢(shì)都是基于C中的成對(duì)約束(和模型參數(shù)\Theta),

標(biāo)簽配置可以進(jìn)一步分解為

P(Y|\Theta,C)=\frac{1}{Z} \bigg(-\sum_{i,j} v(i,j)\bigg)?座慰,? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (5.3)

其中每個(gè)約束勢(shì)函數(shù)?v(i,j)有以下形式:

 v(i,j)= \begin{cases} w_{ij}f_{ML}(i,j)\quad if \ c_{ij}=1 \ and \ y_i \neq y_j,\\w_{ij}f_{CL}(i,j) \quad if \ c_{ij}= -1 \ and \ y_i = y_j,\\ 0 \quad otherwise . \end{cases} ? ? ? ? ? ? ? ? ? ? ?(5.4)

懲罰函數(shù)f_{ML}f_{CL}編碼觀察Y配置的概率降低陨舱,其中違反了C編碼的約束。為此版仔,函數(shù)f_{ML}懲罰違反必須鏈接約束游盲,函數(shù)f_{CL}懲罰違反不能鏈接約束。通過(guò)采用相同的模型參數(shù)\Theta蛮粮,選擇這些功能與畸變測(cè)度相對(duì)應(yīng)益缎,并將在第5.3節(jié)中詳細(xì)描述∪幌耄總的來(lái)說(shuō)莺奔,觀察標(biāo)簽分配Y的公式導(dǎo)致分配給配置的概率更高,在這些配置中变泄,集群分配不會(huì)違反提供的約束令哟。

5.2.3 隱馬爾科夫隨機(jī)場(chǎng)(HMRF)中的聯(lián)合概率

在所描述的HMRF模型中,給定C妨蛹,X屏富、Y和\Theta的聯(lián)合概率可分解如下:

P(X,Y,\Theta|C)=P(\Theta|C)P(Y|\Theta,C)P(X|Y,\Theta,C)? ? ? ? ? ? ? ? ? ? ? ? ? (5.5)


圖 5.2?變相關(guān)圖形板模型

圖5.2顯示了HMRF中隨機(jī)變量之間相關(guān)性的圖形板模型(Buntine,1994年)蛙卤,其中無(wú)陰影節(jié)點(diǎn)表示隱藏變量狠半,陰影節(jié)點(diǎn)是觀察變量,定向鏈接顯示變量之間的相關(guān)性颤难,而兩個(gè)變量之間缺少邊意味著條件獨(dú)立神年。假設(shè)的先驗(yàn)概率與C無(wú)關(guān)。觀察標(biāo)簽配置Y的概率取決于約束C和當(dāng)前生成模型參數(shù)\Theta行嗤。對(duì)應(yīng)于變量X的觀測(cè)數(shù)據(jù)點(diǎn)是使用基于聚類標(biāo)簽Y的模型參數(shù)生成的瘤袖,獨(dú)立于約束C。變量x被假定為相互獨(dú)立的:每個(gè)x_i是從條件概率分布P(x|y|\Theta)生成的昂验。那么捂敌,條件概率P(X|Y,\Theta,C)可以寫成

P(X|Y,\Theta,C)=P(X|Y,\Theta)=\prod_{i=1}^n  P(x_i|y_i,\Theta)? ? ? ? ? ? ? ? ? ? ? ? ? ? (5.6)

其中艾扮,p(\cdot|y_i,\Theta)是第y_i群的參數(shù)化概率密度函數(shù),由此生成x_i占婉。該概率密度與聚類畸變測(cè)度d_A有關(guān)泡嘴,如下文第5.2.4節(jié)所述。

從 等式 5.3逆济,5.5 和 5.6 酌予,最大化HMRF上的聯(lián)合概率等于最大化

P(X,Y,\Theta|C)=P(\Theta)\bigg(\frac{1}{Z} exp \Bigg(\sum_{c_{ij}\in C}v(i,j) \Bigg)\bigg)\bigg(\prod_{i=1}^n p(x_i|y_i,\Theta)\bigg)? ?(5.7)

方程 5.7 中的聯(lián)合概率有三個(gè)因素。第一個(gè)因素描述了模型參數(shù)上的概率分布奖慌,防止它們收斂到退化值抛虫,從而提供正則化。第二個(gè)因素是在給定的約束條件下觀察特定標(biāo)簽配置的條件概率简僧,有效地為集群分配不違反約束條件的配置分配更高的概率建椰。最后,第三個(gè)因素是根據(jù)標(biāo)簽和參數(shù)生成觀測(cè)數(shù)據(jù)點(diǎn)的條件概率:如果在HMRF上進(jìn)行最大似然(ML)估計(jì)岛马,目標(biāo)是隔離地最大化該項(xiàng)棉姐。

總的來(lái)說(shuō),最大化(5.7)中的聯(lián)合HMRF概率相當(dāng)于共同最大化從模型生成數(shù)據(jù)點(diǎn)的可能性和遵守約束的標(biāo)簽分配的概率啦逆,同時(shí)規(guī)范化模型參數(shù)伞矩。

5.2.4?基于HMRF的半監(jiān)督聚類目標(biāo)函數(shù)

公式5.7提出了將約束合并到集群中的一般框架。在框架的特定實(shí)例中夏志,條件概率p(x|y,\Theta)的選擇直接與適合于集群任務(wù)的失真度量的選擇相關(guān)乃坤。

當(dāng)考慮條件概率p(x_i|y_i,\Theta)-從第y_i個(gè)簇生成數(shù)據(jù)點(diǎn)x_i的概率時(shí),我們的注意力僅限于指數(shù)族的概率密度沟蔑,其中對(duì)應(yīng)于第y_i個(gè)簇的期望參數(shù)是\mu_{y_i}——該簇的點(diǎn)的平均值湿诊。規(guī)則指數(shù)分布和規(guī)則布列格曼發(fā)散之間的雙射(Banerjee等人,2005b)溉贿,觀測(cè)數(shù)據(jù)的條件密度可以表示為

p(x_i|y_i,\Theta)=\frac{1}{Z_{\Theta}} exp(-d_A(x_i,\mu_h ))? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (5.8)

其中枫吧,d_A(x_i,\mu_{y_i})x_i\mu_{y_i}之間的Brgman散度浦旱,對(duì)應(yīng)于指數(shù)密度p宇色,Z_{\Theta}是正規(guī)化器。不同的聚類模型屬于這種指數(shù)形式:

a.?如果x_i\mu_{y_i}是歐幾里得空間中的向量颁湖,則d_A是由半正定權(quán)矩陣A(d_A(x_i,\mu_{y_i})=||x_i - \mu_{y_i}||_A^2)所參數(shù)的L_2范數(shù)的平方宣蠕,則聚類條件概率是由A^{-1}編碼的協(xié)方差的高斯分布(卡恩斯等人,1997)甥捺;

b.?如果x_i\mu_{y_i}是概率分布抢蚀,d_A是KL散度(d_A(x_i,\mu_{y_i})=\sum\nolimits_{m=1}^d x_{im}log \frac{x_{im}}{\mu_{y_im}} ),則聚類條件概率是多項(xiàng)式分布(DHyon and Cuin镰禾,2003)皿曲。

式5.8中的關(guān)系成立唱逢,即使d_A不是布列格曼散度,而是方向距離測(cè)度屋休,如余弦距離坞古。例如,如果x_i\mu_{y_i}是單位長(zhǎng)度的向量劫樟,而d_A是向量(d_A(x_i,\mu_{y_i})=1- \frac{\sum\nolimits_{m=1}^d x_{im}\mu_{y_im} }{||x_i||||\mu_{y_i}||} )的點(diǎn)積的一個(gè)減數(shù)痪枫,那么簇條件概率是具有單位濃度參數(shù)的馮\cdot米塞斯Fisher(VMF)分布(BANEJEEE等人,2005年A)叠艳,這實(shí)質(zhì)上是高斯分布的球面模擬奶陈。第5.3.3節(jié)更詳細(xì)地討論了本章研究的特定畸變測(cè)量值與其相應(yīng)的集群條件概率之間的關(guān)系。

將式5.8代入5.7附较,取對(duì)數(shù)吃粒,得到如下聚類目標(biāo)函數(shù),將其最小化翅睛,等于在式5.7中最大化HMRF上的聯(lián)合概率声搁。

J_{obj}=\sum_{x_i \in X} d_A(x_i,\mu_{y_i})+\sum_{c_{ij} \in C}v(i,j) - logP(\Theta) +logZ +nlogZ_{\Theta}? ? ?(5.9)

因此,任務(wù)是最小化隱變量Y\Theta上的 J_{obj}(注意捕发,給定Y疏旨,平均值M=(\mu_1,...,\mu_K)是唯一確定的)。

5.3 HMRF-KMeans 算法

由于集群分配和生成模型參數(shù)在集群設(shè)置中是未知的扎酷,最小化等式5.9是一個(gè)“不完整的數(shù)據(jù)問(wèn)題”檐涝。這種問(wèn)題的一種常用解決方法是期望最大化(EM)算法(Dempster等人,1977)法挨。已知k-均值 算法(Macqueen谁榜,1967)在某些假設(shè)下相當(dāng)于具有硬聚類分配的EM算法(Kearns等人,1997凡纳;Basu等人窃植,2002;Banerjee等人荐糜,2005b)巷怜。本節(jié)描述了一種k-均值類型的硬分割聚類算法HMRF-KMeans,它在等式5.9中找到了半監(jiān)督聚類目標(biāo)函數(shù)J_{obj}的局部最小值暴氏。

5.3.1?歸一化分量估計(jì)

在描述聚類算法的細(xì)節(jié)之前延塑,重要的是要考慮規(guī)范化組件:等式5.9中的MRF分區(qū)函數(shù)logZ和失真函數(shù)歸一化 logZ_{\Theta}。對(duì)于大多數(shù)非平凡的依賴結(jié)構(gòu)答渔,分區(qū)函數(shù)的估計(jì)不能以封閉的形式進(jìn)行关带,計(jì)算時(shí)必須采用近似推理方法(Wainwright 和 Jordan,2003)沼撕。

畸變歸一化logZ_{\Theta}的估計(jì)取決于在模型使用的畸變測(cè)度d_A宋雏。這一章認(rèn)為三參數(shù)參數(shù)化的畸變測(cè)度:參數(shù)化的平方歐氏距離芜飘,參數(shù)化余弦距離和參數(shù)化 KL 散度。對(duì)歐氏距離磨总,Z_{\Theta}可以在封閉的形式中估計(jì)燃箭,這種估計(jì)是在最小化 式 5.9 中的聚類目標(biāo)函數(shù)J_{obj}的同時(shí)進(jìn)行的。對(duì)其他畸變測(cè)度舍败,畸變歸一化的估計(jì)不能在封閉的形式中進(jìn)行招狸,而且必須再次使用近似推理(Banerjee等人,2005年)邻薯。

由于近似推理方法的計(jì)算量非常昂貴裙戏,因此可以做出兩個(gè)簡(jiǎn)化假設(shè):在聚類過(guò)程中,可以將MRF分區(qū)函數(shù)視為常量厕诡,對(duì)于不提供近似估計(jì)的所有畸變測(cè)度累榜,可以將畸變歸一化器假定為常量。有了這些假設(shè)灵嫌,等式5.9中的目標(biāo)函數(shù)J_{obj}不再精確對(duì)應(yīng)于HMRF上的聯(lián)合概率壹罚。然而,最小化這個(gè)簡(jiǎn)化的目標(biāo)已經(jīng)證明在經(jīng)驗(yàn)上是有效的(Bilenko等人寿羞,2004年猖凛;Basu等人,2004b)绪穆。然而辨泳,如果在某些應(yīng)用中保留底層聯(lián)合概率模型的語(yǔ)義很重要,那么規(guī)范化器ZZ_{\Theta}必須通過(guò)近似推理方法進(jìn)行估計(jì)玖院。

5.3.2?參數(shù)優(yōu)先級(jí)

根據(jù)第5.2.1節(jié)中\Theta的定義菠红,式5.9 中的先前項(xiàng)logP(\Theta)和隨后的方程可以分解為以下等式:

logP(\Theta)=log(P(A)P(M))=logP(A) + P_M

其中畸變參數(shù)?A?被假設(shè)獨(dú)立于簇類的中心?M=(\mu_1,...,\mu_K)难菌,被看作是簇的形心上的一致先驗(yàn)(導(dǎo)致常數(shù)項(xiàng)?P_M)试溯。對(duì)不同的畸變測(cè)度,可能存在導(dǎo)致優(yōu)化問(wèn)題退化解的參數(shù)值郊酒。例如遇绞,對(duì)平方歐式距離而言,0 矩陣?A=0就是一個(gè)這樣的解猎塞。為了避免退化解试读,P(A)被用來(lái)通過(guò)使用一個(gè)先驗(yàn)分布正則化參數(shù)的值杠纵。

如果標(biāo)準(zhǔn)高斯先驗(yàn)分布被用于畸變函數(shù)的參數(shù)荠耽,就會(huì)允許這些參數(shù)取負(fù)值。由于需要將參數(shù)值約束為非負(fù)值比藻,因此更適合使用瑞利分布(Papulis和Pillai铝量,2001)倘屹。假設(shè)參數(shù)a_{ij}\in A獨(dú)立,基于瑞利分布的先驗(yàn)項(xiàng)為:

P(A)=\prod_{a_{ij}\in A} \frac{a_{ij}exp\bigg(-\frac{a_{ij}^2}{s^2} \bigg)}{s^2} ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(5.10)

其中s是寬度參數(shù)慢叨。

5.3.3 自適應(yīng)畸變測(cè)度

為一個(gè)聚類任務(wù)選擇一個(gè)適當(dāng)?shù)幕儨y(cè)度d_A通常涉及到特定領(lǐng)域和數(shù)據(jù)集的屬性知識(shí)纽匙。例如,平方歐幾里得距離是最適合分布接近高斯分布的低維數(shù)據(jù)的拍谐,而余弦距離最能捕捉高維空間中向量描述的數(shù)據(jù)之間的距離烛缔,在高維空間中,角度差異很重要轩拨,但向量長(zhǎng)度不重要践瓷。

本章考慮了兩個(gè)族的畸變測(cè)度:Bregman 散度(Banerjee等人,2005b)亡蓉,其中包括參數(shù)化的歐幾里得距離和KL分歧晕翠,以及基于方向相似函數(shù)的畸變測(cè)量,其中包括余弦相似性和皮爾遜相關(guān)(Mardia和Jupp砍濒,2000)淋肾。方向函數(shù)的畸變測(cè)度被選擇為從足夠大的常量中減去方向相似性度量,這樣得到的值是非負(fù)的爸邢。對(duì)于布列格曼散度和余弦距離樊卓,存在有效的k-均值迭代重定位算法,使相應(yīng)的聚類目標(biāo)最小化(Banerjee等人杠河,2005a简识,b),HMRF-k means自然擴(kuò)展到包含成對(duì)監(jiān)督感猛。

對(duì)于許多實(shí)際的數(shù)據(jù)集七扰,現(xiàn)成的畸變測(cè)度可能無(wú)法在聚類設(shè)置中捕獲正確的相似性概念。雖然一些無(wú)監(jiān)督的度量陪白,如平方歐幾里得距離和皮爾遜距離試圖使用數(shù)據(jù)集的全局平均值和方差來(lái)校正失真估計(jì)颈走,但如果屬性對(duì)距離的真正貢獻(xiàn)與它們的方差不相關(guān),這些度量可能仍然無(wú)法準(zhǔn)確地估計(jì)距離咱士。存在幾種包含自適應(yīng)畸變測(cè)度的半監(jiān)督聚類方法立由,包括Jensen-Shannon發(fā)散參數(shù)化(Cohn等人,2003)和平方歐幾里得距離(Bar-Hillel等人序厉,2003锐膜;Xing等人,2003)弛房。然而道盏,這些技術(shù)僅使用約束來(lái)學(xué)習(xí)畸變測(cè)度參數(shù),并從參數(shù)學(xué)習(xí)步驟中排除未標(biāo)記的數(shù)據(jù),以及將參數(shù)學(xué)習(xí)步驟與聚類過(guò)程分離荷逞。

更進(jìn)一步媒咳,HMRF模型提供了一個(gè)集成框架,該框架包括學(xué)習(xí)畸變測(cè)度參數(shù)和約束敏感的簇類分配种远。在 HMRF-KMeans 中涩澡,隨著聚類的進(jìn)行,利用未標(biāo)記的數(shù)據(jù)和成對(duì)的約束坠敷,迭代地學(xué)習(xí)畸變測(cè)度的參數(shù)妙同。修改參數(shù)以減少違反的必須鏈接約束之間的參數(shù)化距離,并增加違反的不能鏈接約束之間的參數(shù)化距離膝迎,同時(shí)允許違反約束(如果它們伴隨更具內(nèi)聚性的聚類)渐溶。

本節(jié)介紹了三個(gè)用于 HMRF-KMeans 的畸變函數(shù)及其參數(shù)化示例:平方歐幾里得距離、余弦距離和kl發(fā)散弄抬。通過(guò)參數(shù)化茎辐,這些函數(shù)中的每一個(gè)都在半監(jiān)督的集群設(shè)置中變得自適應(yīng),允許不同形狀的集群掂恕。

一旦為給定的領(lǐng)域選擇一個(gè)畸變測(cè)度拖陆,函數(shù)?f_{ML}f_{CL}?,第5.2.2節(jié)中介紹的懲罰必須鏈接懊亡,不能鏈接違反約束的行為依啰,相應(yīng)地,必須被定義店枣。這些函數(shù)通常遵循與相應(yīng)畸變測(cè)度相同或相似的函數(shù)形式速警,選擇如下:

f_{ML}(i,j) = \varphi (i,j) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(5.11)

f_{CL}=\varphi^{max} -\varphi(i,j)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(5.12)

其中?\varphi:X \times X \rightarrow R^+?是一個(gè)懲罰違反限制的非負(fù)函數(shù),\varphi^{max}?是數(shù)據(jù)集中任意一對(duì)點(diǎn)上\varphi?最大值的上界鸯两;具體畸變函數(shù)的此類界限示例如下所示闷旧。選擇函數(shù)\varphi與畸變測(cè)度相關(guān),對(duì)畸變測(cè)度的當(dāng)前參數(shù)值距離較遠(yuǎn)的點(diǎn)之間違反必須鏈接約束的行為給予更高的懲罰钧唐。相反忙灼,對(duì)違反的“不能鏈接”約束的懲罰對(duì)于距離較短的點(diǎn)來(lái)說(shuō)更高。使用懲罰函數(shù)的這種公式钝侠,約束沖突會(huì)導(dǎo)致試圖修正沖突的失真度量參數(shù)發(fā)生變化该园。下節(jié)將討論針對(duì)不同聚類畸變測(cè)量的\varphi函數(shù)。

相應(yīng)的地帅韧,(5.4) 中的勢(shì)函數(shù)?v(i,j)變成

 v(i,j)= \begin{cases} w_{ij}\varphi(x_i,x_j)\quad \quad \quad \quad  \quad if \ c_{ij}=1 \ and \ y_i \neq y_j,\\w_{ij}(\varphi^{max}-\varphi(x_i,x_j))\quad if \ c_{ij}= -1 \ and \ y_i = y_j,\\ \quad \quad \quad  0 \quad \ \ \ \quad \quad \quad \quad \quad  otherwise . \end{cases} ? ? ? ? (5.13)

(5.9)中的半監(jiān)督聚類的目標(biāo)函數(shù)可以被記為

J_{obj}=\sum_{x_i\in X} d_A(x_i,\mu(i)) +\sum_{(x_i,x_j)\in C_{ML} \atop s.t. y_i\neq y_j} w_{ij}\varphi(x_i,x_j) \\+ \sum_{(x_i,x_j)\in C_{CL} \atop s.t. y_i = y_j} w_{ij}(\varphi^{max}-\varphi(x_i,x_j))-logP(A) + nlogZ_{\Theta}(5.14)? ? ??

注意里初,如第5.3.1節(jié)所述,MRF分區(qū)函數(shù)項(xiàng)logZ已從目標(biāo)函數(shù)中刪除忽舟。

5.3.3.1 參數(shù)化平方歐幾里得距離

平方歐幾里得距離使用一個(gè)對(duì)稱正定矩陣?A?參數(shù)化如下:

d_{euc_A}(x_i,x_j)=||x_i-x_j||_A^2=(x_i-x_j)^T A (x_i-x_j)? ? ? ? ? ? ? ? ? ?(5.15)

參數(shù)化的平方歐幾里得距離的形式等價(jià)于Mahalanobis距離双妨,用一個(gè)任意的半正定權(quán)矩陣A代替協(xié)方差逆矩陣淮阐,它以前被(Xing et al.,2003)和(Bar Hillel et al.斥难,2003)用于半監(jiān)督聚類。這種公式也可以看作是每個(gè)實(shí)例xA^{1/2}所跨越的空間上的投影:x \rightarrow A^{1/2} x帘饶。

利用參數(shù)化平方歐氏距離作為聚類的自適應(yīng)畸變測(cè)度哑诊,將懲罰違反懲罰的\varphi函數(shù)定義為\varphi(x_i,x_j) = d_{euc_A}(x_i,x_j)。無(wú)法鏈接懲罰的上界的一個(gè)可能初始化是\varphi_{euc_A}^{max} = \sum\nolimits_{(x_i,x_j) \in C_{CL}}d_{euc_A}(x_i,x_j)及刻,它保證懲罰始終為正镀裤。利用這些定義以及(5.14),對(duì)于具有自適應(yīng)平方歐幾里得距離的半監(jiān)督聚類缴饭,得到以下目標(biāo)函數(shù):

J_{euc_A}=\sum_{x_i \in X} d_{euc_A}(x_i,\mu(i))+\sum_{(x_i,x_j)\in C_{ML} \atop s.t. y_i\neq y_j} w_{ij}d_{euc_A}(x_i,x_j) \\ + \sum_{(x_i,x_j)\in C_{CL} \atop s.t. y_i= y_j}w_{ij}(\varphi_{euc_A}^{max}-d_{euc_A}(x_i,x_j))-logP(A) - n log \ det(A) .? (5.16)

請(qǐng)注意暑劝,如第5.3.1節(jié)所述,log \ Z_{\Theta}項(xiàng)可在閉式格式中計(jì)算協(xié)方差矩陣A^{-1}的高斯分布颗搂,協(xié)方差矩陣a?1是參數(shù)化平方歐幾里德距離的基本簇條件概率分布担猛。在這種情況下,log \ det(A)術(shù)語(yǔ)(5.16)與log \ Z_{\Theta}項(xiàng)相對(duì)應(yīng)丢氢。

5.3.3.2 參數(shù)化余弦距離

余弦距離可以使用對(duì)稱正定矩陣A參數(shù)化傅联,這將導(dǎo)致以下畸變測(cè)量:

d_{cos_A}(x_i,x_j)=1-\frac{x_i^TAx_j}{||x_i||_A||x_j||_A} ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (5.17)

因?yàn)閷?duì)于實(shí)數(shù)的高維域,計(jì)算全矩陣A的計(jì)算代價(jià)很高疚察,所以在這種情況下蒸走,考慮對(duì)角矩陣,這樣a=diag(A)是正權(quán)重的向量貌嫡。

利用參數(shù)化平方歐氏距離作為聚類的自適應(yīng)畸變測(cè)度比驻,將\varphi函數(shù)定義為\varphi(x_i,x_j)=d_{cos_A}(x_i,x_j)。將該定義與等式5.14結(jié)合岛抄,將極大值\varphi^{max} = 1設(shè)為上界\varphi(x_i,x_j)别惦,得到了具有自適應(yīng)余弦距離的半監(jiān)督聚類的目標(biāo)函數(shù):

J_{cos_A} = \sum_{x_i \in X} d_{cos_A}(x_i,\mu(i)) + \sum_{(x_i,x_j)\in C_{ML} \atop s.t. y_i \neq y_j}w_{ij}d_{cos_A}(x_i,x_j) \\ + \sum_{(x_i,x_j)\in C_{CL} \atop s.t. y_i = y_j}w_{ij}(1-d_{cos_A}(x_i,x_j))-log \ P(A)? ?(5.18)

注意,如第5.3.1節(jié)所述夫椭,很難以閉合形式計(jì)算參數(shù)化余弦距離的對(duì)數(shù)log \ Z_{\Theta}項(xiàng)步咪。因此,簡(jiǎn)化假設(shè)在聚類過(guò)程中對(duì)數(shù)Z_{\Theta}是常數(shù)益楼,規(guī)范化項(xiàng)從(5.18)中去掉猾漫。

5.3.3.3 參數(shù)化 KL 散度

在確定的領(lǐng)域,數(shù)據(jù)可以描述為概率分布感凤,如悯周,文本文檔可以表示成由多項(xiàng)式模型生成的詞的概率分布(Pereira 等 1993)。KL 散度是廣泛應(yīng)用于此類數(shù)據(jù)的距離測(cè)度:d_{KL}(x_i,x_j)=\sum\nolimits_{m=1}^d x_{im}log \ \frac{x_{im}}{x_{jm}} 陪竿,其中?x_i?和?x_j?是d?事件上的概率分布:\sum\nolimits_{m=1}^d x_{im}=\sum\nolimits_{m=1}^d x_{jm} = 1禽翼。在先前的研究中屠橄,Cohn等人(2003)通過(guò)將第 m 分量乘以權(quán)重\gamma_m = d_{KL}^\prime (x_i,x_j) = \sum\nolimits_{m=1}^d \gamma_mx_{im} \ log \ \frac{x_{im}}{x_{jm}} 來(lái)參數(shù)化kl散度。

在我們的框架中闰挡,KL 距離通過(guò)一個(gè)對(duì)角化矩陣?A?來(lái)參數(shù)化锐墙,其中?a = diag \ (A)?是一個(gè)正權(quán)重的向量。A對(duì)KL的參數(shù)化將其轉(zhuǎn)換為I散度长酗,該函數(shù)也屬于Bregman散度類(Banerjee等人溪北,2005b)。I
?散度 有這樣的形式:d_I(x_i,x_j)=\sum\nolimits_{m=1}^d x_{im} \ log \ \frac{x_{im}}{x_{jm}} -\sum\nolimits_{m=1}^d (x_{im}-x_{jm})夺脾,其中x_i和?x_j?不再需要是概率分布可以是任何非負(fù)向量之拨。使用以下參數(shù)化KL:

d_{I_A}(x_i,x_j)=\sum_{m=1}^d a_mx_{im} \ log \ \frac{x_{im}}{x_{jm}} -\sum_{m=1}^d a_m(x_{im}-x_{jm}),? ? ? ? ? ? ? (5.19)

它可以解釋為用A的相應(yīng)分量中包含的權(quán)重縮放原始概率分布的每個(gè)分量咧叭,然后在轉(zhuǎn)換后的分布之間取I散度蚀乔。

對(duì)于每個(gè)畸變測(cè)度,第5.2.4節(jié)中描述的集群框架要求定義一個(gè)適當(dāng)?shù)膶?duì)稱約束勢(shì)函數(shù)菲茬,因?yàn)榧s束對(duì)是無(wú)序的吉挣。為了滿足這一要求,使用從x_ix_j到平均矢量\frac{x_i+x_j}{2} 的加權(quán)I散度的和婉弹。這一參數(shù)化的平均值I散度d_{IM_A}類似于Jensen-Shannon散度(Cover和Thomas听想,1991),對(duì)稱的平均值KL散度马胧,定義如下:

d_{IM_A}(x_i,x_j)=\sum_{m=1}^d a_m(x_{im} \ log \ \frac{2x_{im}}{x_{im}+x_{jm}} +x_{jm} \ log \ \frac{2x_{jm}}{x_{im}+x_{jm}} ? ? ? ?(5.20)

利用參數(shù)化平方歐氏距離作為聚類的自適應(yīng)失真測(cè)度汉买,將\varphi函數(shù)定義為\varphi(x_i,x_j) = d_{IM_A}(x_i,x_j)。利用該定義以及等式5.14佩脊,得到了具有自適應(yīng)KL距離的半監(jiān)督聚類的以下目標(biāo)函數(shù):J_{I_A}=\sum_{x_i \in X} d_{I_A}(x_i,\mu(i))+\sum_{(x_i,x_j \in C_{ML} \atop s.t. \ y_i \neq y_j} w_{ij}d_{IM_A}(x_i,x_j) \\ +\sum_{(x_i,x_j)\in C_{CL} \atop s.t. \ y_i = y_j} w_{ij}(d_{IM_A}^{max} \ - d_{IM_A}(x_i,x_j)) \ - \ log \ P(A).?(5.21)

上界d_{IM_A}^{max} 可以初始化為d_{IM_A}^{max} =\sum\nolimits_{m=1}^d a_m蛙粘,這是由于未加權(quán)的Jensen-Shannon散度的上界為1(Lin淀散,1991)撩轰。

注意员淫,如第5.3.1節(jié)所述拴竹,很難以閉合形式計(jì)算參數(shù)化KL距離的log \ Z_{\Theta}項(xiàng)。因此道宅,與參數(shù)化余弦距離情況類似湃交,簡(jiǎn)化假設(shè)log \ Z_{\Theta}在聚類過(guò)程中是常數(shù)镀首,該項(xiàng)從等式5.21中去掉豹缀。

5.3.4 EM 框架

如本節(jié)之前討論的伯复,J_{obj}可以通過(guò) K-Means 型的迭代算法 HMRF-KMeans 最小化。算法概述見(jiàn)算法5.1邢笙。HMRF-KMeans 的基本思想是:使用約束條件對(duì)聚類進(jìn)行良好的初始化啸如。然后,在E步驟中氮惯,考慮到當(dāng)前簇的代表性叮雳,每個(gè)數(shù)據(jù)點(diǎn)都被重新分配給簇想暗,從而最小化對(duì)J_{obj}的貢獻(xiàn)。在 M 步驟中帘不,簇代表?M=(\mu_1,...,\mu_K)?根據(jù)群集分配被重新估計(jì)说莫,以最小化當(dāng)前分配的J_{obj}。然后在M步中更新聚類畸變測(cè)度d_A寞焙,通過(guò)修改畸變測(cè)度的參數(shù)A來(lái)降低目標(biāo)函數(shù)储狭。

請(qǐng)注意,這對(duì)應(yīng)于廣義EM算法(Neal和Hinton棺弊,1998晶密;Dempster等人擒悬,1977)模她,其中目標(biāo)函數(shù)在M步驟中減少但不一定最小化。有效地懂牧,E步驟使集群分配Y上的J_{obj}最小化侈净,M
步驟(A)使集群代表M
上的J_{obj}最小化,M
步驟(B
)在畸變測(cè)度d_A的參數(shù)A上減少J_{obj}僧凤。重復(fù)E步和M步畜侦,直到達(dá)到指定的收斂標(biāo)準(zhǔn)。E步驟和M步驟的具體細(xì)節(jié)將在以下章節(jié)中討論躯保。

5.3.5 初始化

良好的初始質(zhì)心對(duì)于K均值等分割聚類算法的成功至關(guān)重要旋膳。在初始化期間,從約束和未標(biāo)記的數(shù)據(jù)中推斷出良好的質(zhì)心途事。為此验懊,使用兩階段初始化過(guò)程。

算法 5.1 HMRF-KMeans 算法

input:數(shù)據(jù)點(diǎn)集?X=(x_1,...,x_n)尸变,簇的數(shù)量?K义图,限制集?C,限制違反損失?W召烂,畸變測(cè)度?D碱工。

output:分離?K-分區(qū)(X_1,...,X_K),滿足式3.9 目標(biāo)函數(shù)?J_{obj}是局部最小化的奏夫。

Method:

1.?初始化?K?個(gè)簇的質(zhì)心?M^{(0)}=(\mu_1^{(0)},...,\mu_K^{(0)})怕篷,設(shè)?t\leftarrow 0

2.?重復(fù)直到收斂

2a.?E-step:給定質(zhì)心?M^{(t)}和畸變參數(shù)?A^{(t)}酗昼,通過(guò)在?X上最小化J_{obj}重新分配簇標(biāo)簽?Y^{(t+1)}=(y_1^{(t+1)},...,y_n^{(t+1)})匙头。

2b. M-step(A):給定簇標(biāo)簽?Y^{(t+1)}和畸變參數(shù)?A^{(t+1)},根據(jù)最小化J_{obj}重新計(jì)算質(zhì)心?M^{(t+1)}=(\mu_1^{(t+1)},...,\mu_K^{(t+1)})?仔雷。

2c. M-step(B):給定簇標(biāo)簽?Y^{(t+1)}?和質(zhì)心?M^{(t+1)}蹂析,重新估算畸變測(cè)度的參數(shù)A^{(t+1)}去降低J_{obj}舔示。

2d.?t \leftarrow t+1

鄰域推理? ? ? 首先采用必鏈接約束的傳遞閉包,得到由必鏈接連接的點(diǎn)組成的連接分量电抚。假設(shè)存在用于創(chuàng)建\lambda鄰域的\lambda連接組件惕稻。這些對(duì)應(yīng)于MRF中隱藏的集群變量上的必須鏈接的鄰居。

簇選擇? ? 利用第一階段產(chǎn)生的\lambda鄰域集對(duì)HMRF均值算法進(jìn)行初始化蝙叛。?如果\lambda=K俺祠,則用所有\lambda鄰域集的形心初始化\lambda簇中心。如果\lambda < K借帘,則從鄰域初始化\lambda簇蜘渣,剩余的K - \lambda簇用由X
的全局質(zhì)心隨機(jī)擾動(dòng)獲得的點(diǎn)初始化。如果\lambda > K肺然,則將最遠(yuǎn)第一次遍歷的加權(quán)變量(Hochbaum和Shmoys蔫缸,1985)應(yīng)用于\lambda鄰域的質(zhì)心,其中每個(gè)質(zhì)心的權(quán)重質(zhì)心與相應(yīng)鄰域的大小成正比际起。加權(quán)最遠(yuǎn)優(yōu)先遍歷選擇距離較遠(yuǎn)拾碌、規(guī)模較大的鄰域,并將所選鄰域設(shè)置為hmrfkmeans的K初始簇形心街望。

總的來(lái)說(shuō)校翔,這兩個(gè)階段的初始化過(guò)程能夠同時(shí)考慮未標(biāo)記和標(biāo)記的數(shù)據(jù),以獲得提供良好的數(shù)據(jù)集初始分區(qū)的集群代表灾前。

5.3.6 E 步驟

E 步驟中防症,使用聚類代表的當(dāng)前估計(jì)更新聚類的數(shù)據(jù)點(diǎn)分配。在一般的無(wú)監(jiān)督K 均值算法中哎甲,聚類標(biāo)簽之間沒(méi)有交互作用蔫敲,而E步是根據(jù)聚類畸變測(cè)度,將每個(gè)點(diǎn)簡(jiǎn)單地分配給最接近的聚類代表烧给。相比之下燕偶,HMRF 模型結(jié)合了由隱藏變量上的隨機(jī)場(chǎng)定義的簇標(biāo)簽之間的交互作用。因此础嫡,在任何非平凡的HMRF模型中指么,計(jì)算將數(shù)據(jù)點(diǎn)分配給聚類代表以找到目標(biāo)函數(shù)的全局最小值(給定集群中心),與其他圖形模型(如MRF和信念網(wǎng)絡(luò))類似榴鼎,都是NP-hard 的(Roth伯诬,1996)。

在這個(gè)框架中巫财,有幾種計(jì)算集群分配的技術(shù)近似于最優(yōu)解決方案盗似,如,迭代條件模式(ICM)(Besag, 1986; Zhang?等, 2001)平项,信仰傳播(Pearl赫舒,1988悍及;Segal?等 2003b),及線性規(guī)劃松弛(Kleinberg?和?Tardos接癌,1999)心赶。ICM是一種貪婪的策略,它按順序更新每個(gè)點(diǎn)的集群分配缺猛,保持其他點(diǎn)的分配不變缨叫。在許多情況下,它的性能與更昂貴的全局近似技術(shù)相當(dāng)荔燎,但計(jì)算效率更高耻姥;它與Bilenko和Basu(2004)的其他幾種方法進(jìn)行了比較,而在最近的研究中有咨,Lange等人(2005)描述了一種基于平均場(chǎng)近似的替代有效方法琐簇。ICM按照隨機(jī)順序?qū)λ悬c(diǎn)執(zhí)行順序集群分配。每個(gè)點(diǎn)x_i被分配到簇代表\mu_h摔吏,它最小化了點(diǎn)對(duì)目標(biāo)函數(shù)J_{obj}(x_i,\mu_h)的貢獻(xiàn):J_{obj}(x_i,\mu_h)=d_A(x_i,\mu_h)+\sum_{(x_i,x_j\in C_{ML}^i \atop s.t. \ y_i \neq y_j} w_{ij}\varphi(x_i,x_j) \\+\sum_{(x_i,x_j \in C_{CL}^i \atop s.t. \ y_i = y_j}w_{ij}(\varphi^{max}-\varphi(x_i,x_j))-log \ P(A),  ? (5.22)

其中C_{ML}^iC_{CL}^i分別是C_{ML}C_{CL}的子集鸽嫂,對(duì)應(yīng)x_i出現(xiàn)的約束纵装。每個(gè)點(diǎn)的最佳分配將點(diǎn)與其聚類代表(J_{obj}的第一項(xiàng))之間的失真降至最低征讲,同時(shí)對(duì)由此分配(J_{obj}的第二和第三項(xiàng))導(dǎo)致的約束違反也將受到最低的懲罰。分配完所有點(diǎn)后橡娄,隨機(jī)重新排序诗箍,并重復(fù)分配過(guò)程。這個(gè)過(guò)程一直進(jìn)行挽唉,直到在兩個(gè)連續(xù)的迭代之間沒(méi)有任何點(diǎn)改變它的聚類分配滤祖。

總的來(lái)說(shuō),將點(diǎn)分配給聚類包含成對(duì)的監(jiān)督瓶籽,通過(guò)按嚴(yán)重性的比例抑制約束沖突匠童,從而引導(dǎo)算法實(shí)現(xiàn)對(duì)數(shù)據(jù)的理想分區(qū)。

5.3.7?M?步驟

算法的M步分為質(zhì)心重估計(jì)和畸變測(cè)度參數(shù)更新兩部分塑顺。

5.3.7.1?M?步驟A:質(zhì)心重估計(jì)

M步驟的第一部分中汤求,從當(dāng)前分配給它們的點(diǎn)重新估計(jì)簇形心M,以減少等式5.9中的目標(biāo)函數(shù)J_{obj}严拒。對(duì)于Bregman散度和余弦距離扬绪,在EM
算法的M步中計(jì)算的簇代表性等于該簇中各點(diǎn)的期望值,等于它們的算術(shù)平均值(Banerjee等人裤唠,2005a挤牛,b)。此外种蘸,實(shí)驗(yàn)證明墓赴,對(duì)于基于分布的度量(如KL發(fā)散)的集群竞膳,使用確定性退火調(diào)度之前平滑集群代表會(huì)帶來(lái)相當(dāng)大的改進(jìn)(Dhillon和Guan,2003)诫硕。當(dāng)d_{I_A}為畸變測(cè)度值時(shí)顶猜,平滑由正參數(shù)\alpha控制,每個(gè)代表\mu_h的簇估計(jì)如下:

\mu_h^{(I_A)}=\frac{1}{1+\alpha} \bigg(\frac{\sum\nolimits_{x_i \in X_h}x_i }{|X_h|} + \frac{\alpha}{n} 1\bigg)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (5.23)

對(duì)于方向測(cè)度痘括,每個(gè)聚類代表的是投影到單位球體上的算術(shù)平均數(shù)(Banerjee等人长窄,2005a)「倬考慮到畸變參數(shù)挠日,當(dāng)d_{cos_A}是畸變測(cè)度時(shí),質(zhì)心估計(jì)如下:

\frac{\mu_h^{(cos_A)}}{||\mu_h^{(cos_A)}||_A} =\frac{\sum\nolimits_{x_i\in X_h}x_i }{||\sum\nolimits_{x_i\in X_h}x_i ||_A} ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(5.24)

5.3.7.2?M步驟?B :?畸變參數(shù)更新

在 M 步驟的第二部分翰舌,對(duì)參數(shù)化畸變測(cè)度的參數(shù)進(jìn)行了更新嚣潜,以減小目標(biāo)函數(shù)。一般來(lái)說(shuō)椅贱,對(duì)于具有一般參數(shù)先驗(yàn)的參數(shù)化 Bregman 散度或方向距離懂算,很難對(duì)能夠最小化目標(biāo)函數(shù)的畸變測(cè)度參數(shù)進(jìn)行封閉式更新。梯度下降為畸變測(cè)量參數(shù)的學(xué)習(xí)提供了一種新的途徑庇麦。

對(duì)平方歐幾里德距離计技,在梯度下降過(guò)程中,使用以下規(guī)則更新全參數(shù)矩陣A:A= A+\eta \frac{\partial{J_{euc_A}}}{\partial A} ?(其中?\eta?為學(xué)習(xí)率)山橄。根據(jù)式(5.16)垮媒,\frac{\partial{J_{euc_A}}}{\partial A} ?可以表示為:

\frac{\partial{J_{euc_A}}}{\partial A}  = \sum_{x_i\in X} \frac{\partial{d_{euc_A}(x_i,\mu(i))}}{\partial A} + \sum_{(x_i,x_j)\in C_{ML} \atop s.t. \ y_i\neq y_j} w_{ij}\frac{\partial{d_{euc_A}(x_i,x_j)}}{\partial A}\\ + \sum_{(x_i,x_j)\in C_{CL} \atop s.t. y_i=y_j} w_{ij}\bigg[\frac{\partial \varphi_{euc_A}^{max}}{\partial A} -\frac{\partial d_{euc_A}(x_i,x_j)}{\partial A} \bigg] - \frac{\partial log \ P(A)}{\partial A} - n\frac{\partial log \ det(A)}{\partial A} ? (5.25)

參數(shù)化平方歐幾里德距離的梯度由下式給出

\frac{\partial d_{euc_A}(x_i,x_j)}{\partial A} = (x_i-x_j)(x_i-x_j)^T

根據(jù)第5.3.3.1節(jié)所述,上界\varphi_{euc_A}^{max}的導(dǎo)數(shù)為\frac{\partial \varphi_{euc_A}^{max}}{\partial A} \sum\nolimits_{(x_i,x_j)\in C_{CL}} (x_i-x_j)(x_i-x_j)^T航棱。

當(dāng)在參數(shù)A上使用瑞利先驗(yàn)時(shí)睡雇,對(duì)數(shù)先驗(yàn)對(duì)每個(gè)參數(shù)的偏導(dǎo)數(shù)a_m \in A\frac{\partial log \ P(A)}{\partial a_m} 由下式給出

\frac{\partial log \ P(A)}{\partial a_m} = \frac{1}{a_m} - \frac{a_m}{s^2} ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(5.26)

畸變規(guī)范化項(xiàng)?log \ det(A)?的梯度如下:

\frac{\partial log \ det(A)}{\partial A} = 2A^{-1} - diag(A^{-1})? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?( 5.27 )

對(duì)于參數(shù)化余弦距離和KL散度饮醇,考慮了對(duì)角參數(shù)矩陣A它抱,其中a=diag(A)是正權(quán)向量。梯度下降期間朴艰,每個(gè)權(quán)重?a_m?是單獨(dú)更新的?a_m = a_m + \eta \frac{\partial J_{obj}}{\partial a_m} ?(\eta ?是學(xué)習(xí)率)观蓄。根據(jù) (5.14), \frac{\partial J_{obj}}{\partial a_m} ? 可以表示為

 \frac{\partial J_{obj}}{\partial a_m}  = \sum_{x_i\in X} \frac{\partial d_A(x_i,\mu(i))}{\partial a_m} + \sum_{(x_i,x_j)\in C_{CL} \atop s.t. y_i \neq y_j} w_{ij}\frac{\partial \varphi(x_i,x_j)}{\partial a_m} \\ +\sum_{(x_i,x_j) \in C_{CL} \atop s.t. y_i = y_j} w_{ij}\bigg[\frac{\partial \varphi^{max}}{\partial a_m} - \frac{\partial \varphi(x_i,x_j)}{\partial a_m} \bigg]- \frac{\partial log \ P(A)}{\partial a_m} ? (5.28)

用對(duì)角矩陣A參數(shù)化的余弦距離和KL散度的梯度\frac{\partial J_{obj}}{\partial a_m} 的計(jì)算需要相應(yīng)的畸變測(cè)度和約束勢(shì)函數(shù)的梯度呵晚,即

當(dāng)參數(shù)化余弦的上界\frac{\partial \varphi^{max}}{\partial a_m} 的梯度為0蜘腌,參數(shù)化KL發(fā)散的上界的梯度為1時(shí),從第5.3.3.2和5.3.3.3節(jié)中這些常數(shù)的表達(dá)式中可以看出饵隙。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末撮珠,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌芯急,老刑警劉巖勺届,帶你破解...
    沈念sama閱讀 223,002評(píng)論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異娶耍,居然都是意外死亡免姿,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評(píng)論 3 400
  • 文/潘曉璐 我一進(jìn)店門榕酒,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)胚膊,“玉大人,你說(shuō)我怎么就攤上這事想鹰∥赏瘢” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,787評(píng)論 0 365
  • 文/不壞的土叔 我叫張陵辑舷,是天一觀的道長(zhǎng)喻犁。 經(jīng)常有香客問(wèn)我,道長(zhǎng)何缓,這世上最難降的妖魔是什么肢础? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,237評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮碌廓,結(jié)果婚禮上传轰,老公的妹妹穿的比我還像新娘。我一直安慰自己氓皱,他們只是感情好路召,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,237評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布勃刨。 她就那樣靜靜地躺著波材,像睡著了一般。 火紅的嫁衣襯著肌膚如雪身隐。 梳的紋絲不亂的頭發(fā)上廷区,一...
    開(kāi)封第一講書(shū)人閱讀 52,821評(píng)論 1 314
  • 那天,我揣著相機(jī)與錄音贾铝,去河邊找鬼隙轻。 笑死,一個(gè)胖子當(dāng)著我的面吹牛垢揩,可吹牛的內(nèi)容都是我干的玖绿。 我是一名探鬼主播,決...
    沈念sama閱讀 41,236評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼叁巨,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼斑匪!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起锋勺,我...
    開(kāi)封第一講書(shū)人閱讀 40,196評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤蚀瘸,失蹤者是張志新(化名)和其女友劉穎狡蝶,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體贮勃,經(jīng)...
    沈念sama閱讀 46,716評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡贪惹,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,794評(píng)論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了寂嘉。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片奏瞬。...
    茶點(diǎn)故事閱讀 40,928評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖泉孩,靈堂內(nèi)的尸體忽然破棺而出丝格,到底是詐尸還是另有隱情,我是刑警寧澤棵譬,帶...
    沈念sama閱讀 36,583評(píng)論 5 351
  • 正文 年R本政府宣布显蝌,位于F島的核電站,受9級(jí)特大地震影響订咸,放射性物質(zhì)發(fā)生泄漏曼尊。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,264評(píng)論 3 336
  • 文/蒙蒙 一脏嚷、第九天 我趴在偏房一處隱蔽的房頂上張望骆撇。 院中可真熱鬧,春花似錦父叙、人聲如沸神郊。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,755評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)涌乳。三九已至,卻和暖如春甜癞,著一層夾襖步出監(jiān)牢的瞬間夕晓,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,869評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工悠咱, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留蒸辆,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,378評(píng)論 3 379
  • 正文 我出身青樓析既,卻偏偏與公主長(zhǎng)得像躬贡,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子眼坏,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,937評(píng)論 2 361