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_A$ ： $R^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}=1$ 和 $c_{23}=-1$ 敦姻； $C$ 中的所有其他變量都設(shè)置為零。任務(wù)是將五個(gè)點(diǎn)分成三個(gè)聚類歧杏。圖5.1展示了一種可能的聚類配置镰惦，它不違反任何約束。必須鏈接的點(diǎn) $x_1,x_2$ 和 $x_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_i$ 的 $y_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ī)范化器 $Z$ 和 $Z_{\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í)例 $x$ 在 $A^{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_i$ 和 $x_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}^i$ 和 $C_{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á)式中可以看出饵隙。

最后編輯于：2019.06.20 16:54:06

?著作權(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
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布勃刨。她就那樣靜靜地躺著波材，像睡著了一般。火紅的嫁衣襯著肌膚如雪身隐。梳的紋絲不亂的頭發(fā)上廷区，一...
開(kāi)封第一講書(shū)人閱讀 52,821評(píng)論 1贊 314
城市分裂傳說(shuō)
那天，我揣著相機(jī)與錄音贾铝，去河邊找鬼隙轻。笑死，一個(gè)胖子當(dāng)著我的面吹牛垢揩，可吹牛的內(nèi)容都是我干的玖绿。我是一名探鬼主播，決...
沈念sama閱讀 41,236評(píng)論 3贊 424
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼叁巨，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼斑匪！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起锋勺，我...
開(kāi)封第一講書(shū)人閱讀 40,196評(píng)論 0贊 277
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤蚀瘸，失蹤者是張志新（化名）和其女友劉穎狡蝶，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體贮勃，經(jīng)...
沈念sama閱讀 46,716評(píng)論 1贊 320
?護(hù)林員之死
正文獨(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
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布显蝌，位于F島的核電站，受9級(jí)特大地震影響订咸，放射性物質(zhì)發(fā)生泄漏曼尊。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 42,264評(píng)論 3贊 336
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一脏嚷、第九天我趴在偏房一處隱蔽的房頂上張望骆撇。院中可真熱鬧，春花似錦父叙、人聲如沸神郊。這莊子的主人今日做“春日...
開(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