在某些聚類任務(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)的樣本,每一個(gè)?
為一個(gè) d-維 向量絮供,其中?
?代表它的第 m 個(gè)成分衣吠。該模型依賴于用于計(jì)算點(diǎn)之間距離的畸變測(cè)度
:
,其中?
是畸變測(cè)度參數(shù)的集合壤靶。監(jiān)督作為兩組成對(duì)約束條件提供:must-link 限制?
和 cannot-link 限制?
蒸播,其中
?表示?
?和?
?被標(biāo)記屬于同一個(gè)簇,而?
表示
?和?
?被標(biāo)記屬于不同簇萍肆。約束可能伴隨著相關(guān)的違反成本
袍榆,其中
表示違反約束點(diǎn)
和x_j之間的約束,如果存在這樣的約束塘揣,也就是包雀,
或
。任務(wù)是將數(shù)據(jù)點(diǎn)集
劃分為
個(gè)不相交的簇
以便根據(jù)給定的失真度量
最小化點(diǎn)和相應(yīng)的集群代表之間的總失真亲铡,而約束沖突保持最小才写。
5.2.1 HMRF 模型組件
半監(jiān)督限制聚類的 HMRF 概率框架由以下組件組成:
a.?一個(gè)可觀測(cè)集對(duì)應(yīng)于給定的數(shù)據(jù)點(diǎn)
葡兑。請(qǐng)注意,我們重載了符號(hào)赞草,并使用
引用給定的數(shù)據(jù)點(diǎn)集及其相應(yīng)的隨機(jī)變量纹冤。
b. 一個(gè)不可觀測(cè)(隱藏)集?對(duì)應(yīng)于
中數(shù)據(jù)點(diǎn)的聚類分配歇攻。每個(gè)隱藏變量
編碼點(diǎn)
的簇標(biāo)簽丛肮,并從聚類索引集合中獲取值
轩娶。
c.?一組不可觀測(cè)(隱藏)的生成模型參數(shù),由畸變測(cè)度參數(shù)
和代表
:
沾凄。
d.?一組可觀測(cè)的約束變量梗醇。每個(gè)
是從集合中取值的三次變量
,其中
表示
撒蟀,
表示:
叙谨,
對(duì)應(yīng)于不受約束的對(duì)
。
由于約束是完全觀察到的保屯,并且所描述的模型并不試圖對(duì)它們進(jìn)行生成建模手负,因此的聯(lián)合概率是以
編碼的約束為條件的。
圖5.1 顯示了一個(gè)簡(jiǎn)單的 示例姑尺。
由五個(gè)數(shù)據(jù)點(diǎn)和相應(yīng)的變量
組成竟终,具有聚類標(biāo)簽
,每個(gè)值
表示三個(gè)聚類股缸。提供了三個(gè)成對(duì)約束:兩個(gè)必須鏈接約束
和
,一個(gè)不能鏈接約束
吱雏。相應(yīng)的約束變量是
和
敦姻;
中的所有其他變量都設(shè)置為零。任務(wù)是將五個(gè)點(diǎn)分成三個(gè)聚類歧杏。圖5.1展示了一種可能的聚類配置镰惦,它不違反任何約束。必須鏈接的點(diǎn)
和
屬于聚類
犬绒;不能與
鏈接的點(diǎn)
分配給集群
旺入;不涉及任何約束的點(diǎn)
屬于集群
。
5.2.2 標(biāo)簽上的馬爾科夫隨機(jī)場(chǎng)
每一個(gè)隱藏的隨機(jī)變量代表
的簇標(biāo)簽與一組鄰居
相關(guān)聯(lián)凯力。鄰居集合定義為
必須鏈接或不能鏈接的所有點(diǎn):
茵瘾。
在隱變量上定義的結(jié)果隨機(jī)場(chǎng)是一個(gè)馬爾可夫隨機(jī)場(chǎng),其中隱變量上的條件概率分布服從馬爾可夫性質(zhì)咐鹤。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(5.1)
因此拗秘,給定模型參數(shù)和約束集的每一個(gè)的
的條件概率,僅取決于必須鏈接或不能鏈接到
的觀測(cè)變量的簇標(biāo)簽祈惶。然后雕旨,根據(jù)Hammersley-Clifford定理(Hammersley和Clifford扮匠,1971),特定標(biāo)簽配置y的先驗(yàn)概率可以表示為吉布斯分布(Geman和Geman凡涩,1984)棒搜,因此
? ? ? ? ? ? ? ? ? ? ? ? ?(5.2)
其中,是所有鄰域的集合活箕,
是分區(qū)函數(shù)(規(guī)范化項(xiàng))力麸,
是整體標(biāo)簽配置勢(shì)函數(shù),可以分解為函數(shù)
的總和讹蘑,每個(gè)函數(shù)表示標(biāo)簽配置
中每個(gè)鄰域
的潛力末盔。因?yàn)槊總€(gè)鄰域的勢(shì)都是基于
中的成對(duì)約束(和模型參數(shù)
),
標(biāo)簽配置可以進(jìn)一步分解為
?座慰,? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (5.3)
其中每個(gè)約束勢(shì)函數(shù)?有以下形式:
? ? ? ? ? ? ? ? ? ? ?(5.4)
懲罰函數(shù)和
編碼觀察
配置的概率降低陨舱,其中違反了
編碼的約束。為此版仔,函數(shù)
懲罰違反必須鏈接約束游盲,函數(shù)
懲罰違反不能鏈接約束。通過(guò)采用相同的模型參數(shù)
蛮粮,選擇這些功能與畸變測(cè)度相對(duì)應(yīng)益缎,并將在第5.3節(jié)中詳細(xì)描述∪幌耄總的來(lái)說(shuō)莺奔,觀察標(biāo)簽分配
的公式導(dǎo)致分配給配置的概率更高,在這些配置中变泄,集群分配不會(huì)違反提供的約束令哟。
5.2.3 隱馬爾科夫隨機(jī)場(chǎng)(HMRF)中的聯(lián)合概率
在所描述的HMRF模型中,給定C妨蛹,X屏富、Y和的聯(lián)合概率可分解如下:
? ? ? ? ? ? ? ? ? ? ? ? ? (5.5)
圖5.2顯示了HMRF中隨機(jī)變量之間相關(guān)性的圖形板模型(Buntine,1994年)蛙卤,其中無(wú)陰影節(jié)點(diǎn)表示隱藏變量狠半,陰影節(jié)點(diǎn)是觀察變量,定向鏈接顯示變量之間的相關(guān)性颤难,而兩個(gè)變量之間缺少邊意味著條件獨(dú)立神年。假設(shè)的先驗(yàn)概率與無(wú)關(guān)。觀察標(biāo)簽配置
的概率取決于約束
和當(dāng)前生成模型參數(shù)
行嗤。對(duì)應(yīng)于變量
的觀測(cè)數(shù)據(jù)點(diǎn)是使用基于聚類標(biāo)簽
的模型參數(shù)生成的瘤袖,獨(dú)立于約束
。變量x被假定為相互獨(dú)立的:每個(gè)
是從條件概率分布
生成的昂验。那么捂敌,條件概率
可以寫成
? ? ? ? ? ? ? ? ? ? ? ? ? ? (5.6)
其中艾扮,是第
群的參數(shù)化概率密度函數(shù),由此生成
占婉。該概率密度與聚類畸變測(cè)度
有關(guān)泡嘴,如下文第5.2.4節(jié)所述。
從 等式 5.3逆济,5.5 和 5.6 酌予,最大化HMRF上的聯(lián)合概率等于最大化
? ?(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í)例中夏志,條件概率的選擇直接與適合于集群任務(wù)的失真度量的選擇相關(guān)乃坤。
當(dāng)考慮條件概率-從第
個(gè)簇生成數(shù)據(jù)點(diǎn)
的概率時(shí),我們的注意力僅限于指數(shù)族的概率密度沟蔑,其中對(duì)應(yīng)于第
個(gè)簇的期望參數(shù)是
——該簇的點(diǎn)的平均值湿诊。規(guī)則指數(shù)分布和規(guī)則布列格曼發(fā)散之間的雙射(Banerjee等人,2005b)溉贿,觀測(cè)數(shù)據(jù)的條件密度可以表示為
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (5.8)
其中枫吧,是
和
之間的Brgman散度浦旱,對(duì)應(yīng)于指數(shù)密度
宇色,
是正規(guī)化器。不同的聚類模型屬于這種指數(shù)形式:
a.?如果和
是歐幾里得空間中的向量颁湖,則
是由半正定權(quán)矩陣
所參數(shù)的
范數(shù)的平方宣蠕,則聚類條件概率是由
編碼的協(xié)方差的高斯分布(卡恩斯等人,1997)甥捺;
b.?如果和
是概率分布抢蚀,
是KL散度
,則聚類條件概率是多項(xiàng)式分布(DHyon and Cuin镰禾,2003)皿曲。
式5.8中的關(guān)系成立唱逢,即使不是布列格曼散度,而是方向距離測(cè)度屋休,如余弦距離坞古。例如,如果
和
是單位長(zhǎng)度的向量劫樟,而
是向量
的點(diǎn)積的一個(gè)減數(shù)痪枫,那么簇條件概率是具有單位濃度參數(shù)的馮
米塞斯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)合概率声搁。
? ? ?(5.9)
因此,任務(wù)是最小化隱變量和
上的
(注意捕发,給定
疏旨,平均值
是唯一確定的)。
5.3 HMRF-KMeans 算法
由于集群分配和生成模型參數(shù)在集群設(shè)置中是未知的扎酷,最小化等式5.9是一個(gè)“不完整的數(shù)據(jù)問(wèn)題”檐涝。這種問(wèn)題的一種常用解決方法是期望最大化(EM)算法(Dempster等人,1977)法挨。已知k-均值 算法(Macqueen谁榜,1967)在某些假設(shè)下相當(dāng)于具有硬聚類分配的算法(Kearns等人,1997凡纳;Basu等人窃植,2002;Banerjee等人荐糜,2005b)巷怜。本節(jié)描述了一種k-均值類型的硬分割聚類算法
,它在等式5.9中找到了半監(jiān)督聚類目標(biāo)函數(shù)
的局部最小值暴氏。
5.3.1?歸一化分量估計(jì)
在描述聚類算法的細(xì)節(jié)之前延塑,重要的是要考慮規(guī)范化組件:等式5.9中的分區(qū)函數(shù)
和失真函數(shù)歸一化
。對(duì)于大多數(shù)非平凡的依賴結(jié)構(gòu)答渔,分區(qū)函數(shù)的估計(jì)不能以封閉的形式進(jìn)行关带,計(jì)算時(shí)必須采用近似推理方法(Wainwright 和 Jordan,2003)沼撕。
畸變歸一化的估計(jì)取決于在模型使用的畸變測(cè)度
宋雏。這一章認(rèn)為三參數(shù)參數(shù)化的畸變測(cè)度:參數(shù)化的平方歐氏距離芜飘,參數(shù)化余弦距離和參數(shù)化 KL 散度。對(duì)歐氏距離磨总,
可以在封閉的形式中估計(jì)燃箭,這種估計(jì)是在最小化 式 5.9 中的聚類目標(biāo)函數(shù)
的同時(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ù)不再精確對(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ī)范化器
和
必須通過(guò)近似推理方法進(jìn)行估計(jì)玖院。
5.3.2?參數(shù)優(yōu)先級(jí)
根據(jù)第5.2.1節(jié)中的定義菠红,式5.9 中的先前項(xiàng)
和隨后的方程可以分解為以下等式:
,
其中畸變參數(shù)??被假設(shè)獨(dú)立于簇類的中心?
难菌,被看作是簇的形心上的一致先驗(yàn)(導(dǎo)致常數(shù)項(xiàng)?
)试溯。對(duì)不同的畸變測(cè)度,可能存在導(dǎo)致優(yōu)化問(wèn)題退化解的參數(shù)值郊酒。例如遇绞,對(duì)平方歐式距離而言,0 矩陣?
就是一個(gè)這樣的解猎塞。為了避免退化解试读,
被用來(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ù)獨(dú)立,基于瑞利分布的先驗(yàn)項(xiàng)為:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(5.10)
其中是寬度參數(shù)慢叨。
5.3.3 自適應(yīng)畸變測(cè)度
為一個(gè)聚類任務(wù)選擇一個(gè)適當(dāng)?shù)幕儨y(cè)度通常涉及到特定領(lǐng)域和數(shù)據(jù)集的屬性知識(shí)纽匙。例如,平方歐幾里得距離是最適合分布接近高斯分布的低維數(shù)據(jù)的拍谐,而余弦距離最能捕捉高維空間中向量描述的數(shù)據(jù)之間的距離烛缔,在高維空間中,角度差異很重要轩拨,但向量長(zhǎng)度不重要践瓷。
本章考慮了兩個(gè)族的畸變測(cè)度:Bregman 散度(Banerjee等人,2005b)亡蓉,其中包括參數(shù)化的歐幾里得距離和分歧晕翠,以及基于方向相似函數(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ù)?和
?,第5.2.2節(jié)中介紹的懲罰必須鏈接懊亡,不能鏈接違反約束的行為依啰,相應(yīng)地,必須被定義店枣。這些函數(shù)通常遵循與相應(yīng)畸變測(cè)度相同或相似的函數(shù)形式速警,選擇如下:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(5.11)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(5.12)
其中??是一個(gè)懲罰違反限制的非負(fù)函數(shù),
?是數(shù)據(jù)集中任意一對(duì)點(diǎn)上
?最大值的上界鸯两;具體畸變函數(shù)的此類界限示例如下所示闷旧。選擇函數(shù)
與畸變測(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è)量的
函數(shù)。
相應(yīng)的地帅韧,(5.4) 中的勢(shì)函數(shù)?變成
? ? ? ? (5.13)
(5.9)中的半監(jiān)督聚類的目標(biāo)函數(shù)可以被記為
(5.14)? ? ??
注意里初,如第5.3.1節(jié)所述,MRF分區(qū)函數(shù)項(xiàng)已從目標(biāo)函數(shù)中刪除忽舟。
5.3.3.1 參數(shù)化平方歐幾里得距離
平方歐幾里得距離使用一個(gè)對(duì)稱正定矩陣??參數(shù)化如下:
? ? ? ? ? ? ? ? ? ?(5.15)
參數(shù)化的平方歐幾里得距離的形式等價(jià)于Mahalanobis距離双妨,用一個(gè)任意的半正定權(quán)矩陣代替協(xié)方差逆矩陣淮阐,它以前被(Xing et al.,2003)和(Bar Hillel et al.斥难,2003)用于半監(jiān)督聚類。這種公式也可以看作是每個(gè)實(shí)例
在
所跨越的空間上的投影:
帘饶。
利用參數(shù)化平方歐氏距離作為聚類的自適應(yīng)畸變測(cè)度哑诊,將懲罰違反懲罰的函數(shù)定義為
。無(wú)法鏈接懲罰的上界的一個(gè)可能初始化是
及刻,它保證懲罰始終為正镀裤。利用這些定義以及(5.14),對(duì)于具有自適應(yīng)平方歐幾里得距離的半監(jiān)督聚類缴饭,得到以下目標(biāo)函數(shù):
? (5.16)
請(qǐng)注意暑劝,如第5.3.1節(jié)所述,項(xiàng)可在閉式格式中計(jì)算協(xié)方差矩陣
的高斯分布颗搂,協(xié)方差矩陣a?1是參數(shù)化平方歐幾里德距離的基本簇條件概率分布担猛。在這種情況下,
術(shù)語(yǔ)(5.16)與
項(xiàng)相對(duì)應(yīng)丢氢。
5.3.3.2 參數(shù)化余弦距離
余弦距離可以使用對(duì)稱正定矩陣參數(shù)化傅联,這將導(dǎo)致以下畸變測(cè)量:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (5.17)
因?yàn)閷?duì)于實(shí)數(shù)的高維域,計(jì)算全矩陣的計(jì)算代價(jià)很高疚察,所以在這種情況下蒸走,考慮對(duì)角矩陣,這樣
是正權(quán)重的向量貌嫡。
利用參數(shù)化平方歐氏距離作為聚類的自適應(yīng)畸變測(cè)度比驻,將函數(shù)定義為
。將該定義與等式5.14結(jié)合岛抄,將極大值
設(shè)為上界
别惦,得到了具有自適應(yīng)余弦距離的半監(jiān)督聚類的目標(biāo)函數(shù):
? ?(5.18)
注意,如第5.3.1節(jié)所述夫椭,很難以閉合形式計(jì)算參數(shù)化余弦距離的對(duì)數(shù)項(xiàng)步咪。因此,簡(jiǎn)化假設(shè)在聚類過(guò)程中對(duì)數(shù)
是常數(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è)度:陪竿,其中?
?和?
?是
?事件上的概率分布:
禽翼。在先前的研究中屠橄,Cohn等人(2003)通過(guò)將第 m 分量乘以權(quán)重
來(lái)參數(shù)化kl散度。
在我們的框架中闰挡,KL 距離通過(guò)一個(gè)對(duì)角化矩陣??來(lái)參數(shù)化锐墙,其中?
?是一個(gè)正權(quán)重的向量。
對(duì)
的參數(shù)化將其轉(zhuǎn)換為
散度长酗,該函數(shù)也屬于Bregman散度類(Banerjee等人溪北,2005b)。
?散度 有這樣的形式:
夺脾,其中
和?
?不再需要是概率分布可以是任何非負(fù)向量之拨。使用以下參數(shù)化KL:
,? ? ? ? ? ? ? (5.19)
它可以解釋為用的相應(yīng)分量中包含的權(quán)重縮放原始概率分布的每個(gè)分量咧叭,然后在轉(zhuǎn)換后的分布之間取
散度蚀乔。
對(duì)于每個(gè)畸變測(cè)度,第5.2.4節(jié)中描述的集群框架要求定義一個(gè)適當(dāng)?shù)膶?duì)稱約束勢(shì)函數(shù)菲茬,因?yàn)榧s束對(duì)是無(wú)序的吉挣。為了滿足這一要求,使用從和
到平均矢量
的加權(quán)
散度的和婉弹。這一參數(shù)化的平均值
散度
類似于Jensen-Shannon散度(Cover和Thomas听想,1991),對(duì)稱的平均值
散度马胧,定義如下:
? ? ? ?(5.20)
利用參數(shù)化平方歐氏距離作為聚類的自適應(yīng)失真測(cè)度汉买,將函數(shù)定義為
。利用該定義以及等式5.14佩脊,得到了具有自適應(yīng)
距離的半監(jiān)督聚類的以下目標(biāo)函數(shù):
?(5.21)
上界可以初始化為
蛙粘,這是由于未加權(quán)的Jensen-Shannon散度的上界為1(Lin淀散,1991)撩轰。
注意员淫,如第5.3.1節(jié)所述拴竹,很難以閉合形式計(jì)算參數(shù)化距離的
項(xiàng)。因此道宅,與參數(shù)化余弦距離情況類似湃交,簡(jiǎn)化假設(shè)
在聚類過(guò)程中是常數(shù)镀首,該項(xiàng)從等式5.21中去掉豹缀。
5.3.4 EM 框架
如本節(jié)之前討論的伯复,可以通過(guò) K-Means 型的迭代算法 HMRF-KMeans 最小化。算法概述見(jiàn)算法5.1邢笙。HMRF-KMeans 的基本思想是:使用約束條件對(duì)聚類進(jìn)行良好的初始化啸如。然后,在E步驟中氮惯,考慮到當(dāng)前簇的代表性叮雳,每個(gè)數(shù)據(jù)點(diǎn)都被重新分配給簇想暗,從而最小化對(duì)
的貢獻(xiàn)。在 M 步驟中帘不,簇代表?
?根據(jù)群集分配被重新估計(jì)说莫,以最小化當(dāng)前分配的
。然后在
步中更新聚類畸變測(cè)度
寞焙,通過(guò)修改畸變測(cè)度的參數(shù)
來(lái)降低目標(biāo)函數(shù)储狭。
請(qǐng)注意,這對(duì)應(yīng)于廣義算法(Neal和Hinton棺弊,1998晶密;Dempster等人擒悬,1977)模她,其中目標(biāo)函數(shù)在
步驟中減少但不一定最小化。有效地懂牧,
步驟使集群分配
上的
最小化侈净,
步驟(
)使集群代表
上的
最小化,
步驟(
)在畸變測(cè)度
的參數(shù)
上減少
僧凤。重復(fù)
步和
步畜侦,直到達(dá)到指定的收斂標(biāo)準(zhǔn)。
步驟和
步驟的具體細(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)集?尸变,簇的數(shù)量?K义图,限制集?C,限制違反損失?W召烂,畸變測(cè)度?D碱工。
output:分離?K-分區(qū),滿足式3.9 目標(biāo)函數(shù)?
是局部最小化的奏夫。
Method:
1.?初始化?K?個(gè)簇的質(zhì)心?怕篷,設(shè)?
。
2.?重復(fù)直到收斂
2a.?E-step:給定質(zhì)心?和畸變參數(shù)?
酗昼,通過(guò)在?X上最小化
重新分配簇標(biāo)簽?
匙头。
2b. M-step(A):給定簇標(biāo)簽?和畸變參數(shù)?
,根據(jù)最小化
重新計(jì)算質(zhì)心?
?仔雷。
2c. M-step(B):給定簇標(biāo)簽??和質(zhì)心?
蹂析,重新估算畸變測(cè)度的參數(shù)
去降低
舔示。
2d.?
鄰域推理? ? ? 首先采用必鏈接約束的傳遞閉包,得到由必鏈接連接的點(diǎn)組成的連接分量电抚。假設(shè)存在用于創(chuàng)建鄰域的
連接組件惕稻。這些對(duì)應(yīng)于MRF中隱藏的集群變量上的必須鏈接的鄰居。
簇選擇? ? 利用第一階段產(chǎn)生的鄰域集對(duì)HMRF均值算法進(jìn)行初始化蝙叛。?如果
俺祠,則用所有
鄰域集的形心初始化
簇中心。如果
借帘,則從鄰域初始化
簇蜘渣,剩余的
簇用由
的全局質(zhì)心隨機(jī)擾動(dòng)獲得的點(diǎn)初始化。如果
肺然,則將最遠(yuǎn)第一次遍歷的加權(quán)變量(Hochbaum和Shmoys蔫缸,1985)應(yīng)用于
鄰域的質(zhì)心,其中每個(gè)質(zhì)心的權(quán)重質(zhì)心與相應(yīng)鄰域的大小成正比际起。加權(quán)最遠(yuǎn)優(yōu)先遍歷選擇距離較遠(yuǎn)拾碌、規(guī)模較大的鄰域,并將所選鄰域設(shè)置為hmrfkmeans的
初始簇形心街望。
總的來(lái)說(shuō)校翔,這兩個(gè)階段的初始化過(guò)程能夠同時(shí)考慮未標(biāo)記和標(biāo)記的數(shù)據(jù),以獲得提供良好的數(shù)據(jù)集初始分區(qū)的集群代表灾前。
5.3.6 E 步驟
在 步驟中防症,使用聚類代表的當(dāng)前估計(jì)更新聚類的數(shù)據(jù)點(diǎn)分配。在一般的無(wú)監(jiān)督K 均值算法中哎甲,聚類標(biāo)簽之間沒(méi)有交互作用蔫敲,而
步是根據(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)被分配到簇代表
摔吏,它最小化了點(diǎn)對(duì)目標(biāo)函數(shù)
的貢獻(xiàn):
? (5.22)
其中和
分別是
和
的子集鸽嫂,對(duì)應(yīng)
出現(xiàn)的約束纵装。每個(gè)點(diǎn)的最佳分配將點(diǎn)與其聚類代表(
的第一項(xiàng))之間的失真降至最低征讲,同時(shí)對(duì)由此分配(
的第二和第三項(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ì)
在步驟的第一部分中汤求,從當(dāng)前分配給它們的點(diǎn)重新估計(jì)簇形心
,以減少等式5.9中的目標(biāo)函數(shù)
严拒。對(duì)于Bregman散度和余弦距離扬绪,在
算法的
步中計(jì)算的簇代表性等于該簇中各點(diǎn)的期望值,等于它們的算術(shù)平均值(Banerjee等人裤唠,2005a挤牛,b)。此外种蘸,實(shí)驗(yàn)證明墓赴,對(duì)于基于分布的度量(如
發(fā)散)的集群竞膳,使用確定性退火調(diào)度之前平滑集群代表會(huì)帶來(lái)相當(dāng)大的改進(jìn)(Dhillon和Guan,2003)诫硕。當(dāng)
為畸變測(cè)度值時(shí)顶猜,平滑由正參數(shù)
控制,每個(gè)代表
的簇估計(jì)如下:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (5.23)
對(duì)于方向測(cè)度痘括,每個(gè)聚類代表的是投影到單位球體上的算術(shù)平均數(shù)(Banerjee等人长窄,2005a)「倬考慮到畸變參數(shù)挠日,當(dāng)是畸變測(cè)度時(shí),質(zhì)心估計(jì)如下:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(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:?(其中?
?為學(xué)習(xí)率)山橄。根據(jù)式(5.16)垮媒,
?可以表示為:
? (5.25)
參數(shù)化平方歐幾里德距離的梯度由下式給出
根據(jù)第5.3.3.1節(jié)所述,上界的導(dǎo)數(shù)為
航棱。
當(dāng)在參數(shù)A上使用瑞利先驗(yàn)時(shí)睡雇,對(duì)數(shù)先驗(yàn)對(duì)每個(gè)參數(shù)的偏導(dǎo)數(shù),
由下式給出
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(5.26)
畸變規(guī)范化項(xiàng)??的梯度如下:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?( 5.27 )
對(duì)于參數(shù)化余弦距離和散度饮醇,考慮了對(duì)角參數(shù)矩陣
它抱,其中
是正權(quán)向量。梯度下降期間朴艰,每個(gè)權(quán)重?
?是單獨(dú)更新的?
?(
?是學(xué)習(xí)率)观蓄。根據(jù) (5.14),
? 可以表示為
? (5.28)
用對(duì)角矩陣參數(shù)化的余弦距離和
散度的梯度
的計(jì)算需要相應(yīng)的畸變測(cè)度和約束勢(shì)函數(shù)的梯度呵晚,即
當(dāng)參數(shù)化余弦的上界的梯度為0蜘腌,參數(shù)化
發(fā)散的上界的梯度為1時(shí),從第5.3.3.2和5.3.3.3節(jié)中這些常數(shù)的表達(dá)式中可以看出饵隙。